nscd/mem.c

   1 /* Cache memory handling.
   2    Copyright (C) 2004 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Ulrich Drepper <drepper@redhat.com>, 2004.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #include <assert.h>
  22 #include <errno.h>
  23 #include <error.h>
  24 #include <inttypes.h>
  25 #include <libintl.h>
  26 #include <limits.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <unistd.h>
  30 #include <sys/mman.h>
  31 #include <sys/param.h>
  32
  33 #include "dbg_log.h"
  34 #include "nscd.h"
  35
  36
  37 /* Maximum alignment requirement we will encounter.  */
  38 #define BLOCK_ALIGN_LOG 3
  39 #define BLOCK_ALIGN (1 << BLOCK_ALIGN_LOG)
  40 #define BLOCK_ALIGN_M1 (BLOCK_ALIGN - 1)
  41
  42
  43 static int
  44 sort_he (const void *p1, const void *p2)
  45 {
  46   struct hashentry *h1 = *(struct hashentry **) p1;
  47   struct hashentry *h2 = *(struct hashentry **) p2;
  48
  49   if (h1 < h2)
  50     return -1;
  51   if (h1 > h2)
  52     return 1;
  53   return 0;
  54 }
  55
  56
  57 static int
  58 sort_he_data (const void *p1, const void *p2)
  59 {
  60   struct hashentry *h1 = *(struct hashentry **) p1;
  61   struct hashentry *h2 = *(struct hashentry **) p2;
  62
  63   if (h1->packet < h2->packet)
  64     return -1;
  65   if (h1->packet > h2->packet)
  66     return 1;
  67   return 0;
  68 }
  69
  70
  71 /* Basic definitions for the bitmap implementation.  Only BITMAP_T
  72    needs to be changed to choose a different word size.  */
  73 #define BITMAP_T uint8_t
  74 #define BITS (CHAR_BIT * sizeof (BITMAP_T))
  75 #define ALLBITS ((((BITMAP_T) 1) << BITS) - 1)
  76 #define HIGHBIT (((BITMAP_T) 1) << (BITS - 1))
  77
  78
  79 static void
  80 markrange (BITMAP_T *mark, ref_t start, size_t len)
  81 {
  82   /* Adjust parameters for block alignment.  */
  83   start /= BLOCK_ALIGN;
  84   len = (len + BLOCK_ALIGN_M1) / BLOCK_ALIGN;
  85
  86   size_t elem = start / BITS;
  87
  88   if (start % BITS != 0)
  89     {
  90       if (start % BITS + len <= BITS)
  91         {
  92           /* All fits in the partial byte.  */
  93           mark[elem] |= (ALLBITS >> (BITS - len)) << (start % BITS);
  94           return;
  95         }
  96
  97       mark[elem++] |= 0xff << (start % BITS);
  98       len -= BITS - (start % BITS);
  99     }
 100
 101   while (len >= BITS)
 102     {
 103       mark[elem++] = ALLBITS;
 104       len -= BITS;
 105     }
 106
 107   if (len > 0)
 108     mark[elem] |= ALLBITS >> (BITS - len);
 109 }
 110
 111
 112 void
 113 gc (struct database_dyn *db)
 114 {
 115   /* We need write access.  */
 116   pthread_rwlock_wrlock (&db->lock);
 117
 118   /* And the memory handling lock.  */
 119   pthread_mutex_lock (&db->memlock);
 120
 121   /* We need an array representing the data area.  All memory
 122      allocation is BLOCK_ALIGN aligned so this is the level at which
 123      we have to look at the memory.  We use a mark and sweep algorithm
 124      where the marks are placed in this array.  */
 125   assert (db->head->first_free % BLOCK_ALIGN == 0);
 126   BITMAP_T mark[(db->head->first_free / BLOCK_ALIGN + BITS - 1) / BITS];
 127   memset (mark, '\0', sizeof (mark));
 128
 129   /* Create an array which can hold pointer to all the entries in hash
 130      entries.  */
 131   struct hashentry *he[db->head->nentries];
 132   struct hashentry *he_data[db->head->nentries];
 133
 134   size_t cnt = 0;
 135   for (size_t idx = 0; idx < db->head->module; ++idx)
 136     {
 137       ref_t *prevp = &db->head->array[idx];
 138       ref_t run = *prevp;
 139
 140       while (run != ENDREF)
 141         {
 142           assert (cnt < db->head->nentries);
 143           he[cnt] = (struct hashentry *) (db->data + run);
 144
 145           he[cnt]->prevp = prevp;
 146           prevp = &he[cnt]->next;
 147
 148           /* This is the hash entry itself.  */
 149           markrange (mark, run, sizeof (struct hashentry));
 150
 151           /* Add the information for the data itself.  We do this
 152              only for the one special entry marked with FIRST.  */
 153           if (he[cnt]->first)
 154             {
 155               struct datahead *dh
 156                 = (struct datahead *) (db->data + he[cnt]->packet);
 157               markrange (mark, he[cnt]->packet, dh->allocsize);
 158             }
 159
 160           run = he[cnt]->next;
 161
 162           ++cnt;
 163         }
 164     }
 165   assert (cnt == db->head->nentries);
 166
 167   /* Sort the entries by the addresses of the referenced data.  All
 168      the entries pointing to the same DATAHEAD object will have the
 169      same key.  Stability of the sorting is unimportant.  */
 170   memcpy (he_data, he, cnt * sizeof (struct hashentry *));
 171   qsort (he_data, cnt, sizeof (struct hashentry *), sort_he_data);
 172
 173   /* Sort the entries by their address.  */
 174   qsort (he, cnt, sizeof (struct hashentry *), sort_he);
 175
 176   /* Determine the highest used address.  */
 177   size_t high = sizeof (mark);
 178   while (high > 0 && mark[high - 1] == 0)
 179     --high;
 180
 181   /* No memory used.  */
 182   if (high == 0)
 183     {
 184       db->head->first_free = 0;
 185       goto out;
 186     }
 187
 188   /* Determine the highest offset.  */
 189   BITMAP_T mask = HIGHBIT;
 190   ref_t highref = (high * BITS - 1) * BLOCK_ALIGN;
 191   while ((mark[high - 1] & mask) == 0)
 192     {
 193       mask >>= 1;
 194       highref -= BLOCK_ALIGN;
 195     }
 196
 197   /* No we can iterate over the MARK array and find bits which are not
 198      set.  These represent memory which can be recovered.  */
 199   size_t byte = 0;
 200   /* Find the first gap.  */
 201   while (byte < high && mark[byte] == ALLBITS)
 202     ++byte;
 203
 204   if (byte == high
 205       || (byte == high - 1 && (mark[byte] & ~(mask | (mask - 1))) == 0))
 206     /* No gap.  */
 207     goto out;
 208
 209   mask = 1;
 210   cnt = 0;
 211   while ((mark[byte] & mask) != 0)
 212     {
 213       ++cnt;
 214       mask <<= 1;
 215     }
 216   ref_t off_free = (byte * BITS + cnt) * BLOCK_ALIGN;
 217   assert (off_free <= db->head->first_free);
 218
 219   struct hashentry **next_hash = he;
 220   struct hashentry **next_data = he_data;
 221
 222   /* Skip over the hash entries in the first block which does not get
 223      moved.  */
 224   while (next_hash < &he[db->head->nentries]
 225          && *next_hash < (struct hashentry *) (db->data + off_free))
 226     ++next_hash;
 227
 228   while (next_data < &he_data[db->head->nentries]
 229          && (*next_data)->packet < off_free)
 230     ++next_data;
 231
 232
 233   /* We do not perform the move operations right away since the
 234      he_data array is not sorted by the address of the data.  */
 235   struct moveinfo
 236   {
 237     void *from;
 238     void *to;
 239     size_t size;
 240     struct moveinfo *next;
 241   } *moves = NULL;
 242
 243   while (byte < high)
 244     {
 245       /* Search for the next filled block.  BYTE is the index of the
 246          entry in MARK, MASK is the bit, and CNT is the bit number.
 247          OFF_FILLED is the corresponding offset.  */
 248       if ((mark[byte] & ~(mask - 1)) == 0)
 249         {
 250           /* No other bit set in the same element of MARK.  Search in the
 251              following memory.  */
 252           do
 253             ++byte;
 254           while (byte < high && mark[byte] == 0);
 255
 256           if (byte == high)
 257             /* That was it.  */
 258             break;
 259
 260           mask = 1;
 261           cnt = 0;
 262         }
 263       /* Find the exact bit.  */
 264       while ((mark[byte] & mask) == 0)
 265         {
 266           ++cnt;
 267           mask <<= 1;
 268         }
 269
 270       ref_t off_alloc = (byte * BITS + cnt) * BLOCK_ALIGN;
 271       assert (off_alloc <= db->head->first_free);
 272
 273       /* Find the end of the used area.  */
 274       if ((mark[byte] & ~(mask - 1)) == (BITMAP_T) ~(mask - 1))
 275         {
 276           /* All other bits set.  Search the next bytes in MARK.  */
 277           do
 278             ++byte;
 279           while (byte < high && mark[byte] == ALLBITS);
 280
 281           mask = 1;
 282           cnt = 0;
 283         }
 284       if (byte < high)
 285         {
 286           /* Find the exact bit.  */
 287           while ((mark[byte] & mask) != 0)
 288             {
 289               ++cnt;
 290               mask <<= 1;
 291             }
 292         }
 293
 294       ref_t off_allocend = (byte * BITS + cnt) * BLOCK_ALIGN;
 295       assert (off_allocend <= db->head->first_free);
 296       /* Now we know that we can copy the area from OFF_ALLOC to
 297          OFF_ALLOCEND (not included) to the memory starting at
 298          OFF_FREE.  First fix up all the entries for the
 299          displacement.  */
 300       ref_t disp = off_alloc - off_free;
 301
 302       struct moveinfo *new_move
 303         = (struct moveinfo *) alloca (sizeof (*new_move));
 304       new_move->from = db->data + off_alloc;
 305       new_move->to = db->data + off_free;
 306       new_move->size = off_allocend - off_alloc;
 307       /* Create a circular list to be always able to append at the end.  */
 308       if (moves == NULL)
 309         moves = new_move->next = new_move;
 310       else
 311         {
 312           new_move->next = moves->next;
 313           moves = moves->next = new_move;
 314         }
 315
 316       /* The following loop will prepare to move this much data.  */
 317       off_free += off_allocend - off_alloc;
 318
 319       while (off_alloc < off_allocend)
 320         {
 321           /* Determine whether the next entry is for a hash entry or
 322              the data.  */
 323           if ((struct hashentry *) (db->data + off_alloc) == *next_hash)
 324             {
 325               /* Just correct the forward reference.  */
 326               *(*next_hash++)->prevp -= disp;
 327
 328               off_alloc += ((sizeof (struct hashentry) + BLOCK_ALIGN_M1)
 329                             & ~BLOCK_ALIGN_M1);
 330             }
 331           else
 332             {
 333               assert (next_data < &he_data[db->head->nentries]);
 334               assert ((*next_data)->packet == off_alloc);
 335
 336               struct datahead *dh = (struct datahead *) (db->data + off_alloc);
 337               do
 338                 {
 339                   assert ((*next_data)->key >= (*next_data)->packet);
 340                   assert ((*next_data)->key + (*next_data)->len
 341                           <= (*next_data)->packet + dh->allocsize);
 342
 343                   (*next_data)->packet -= disp;
 344                   (*next_data)->key -= disp;
 345                   ++next_data;
 346                 }
 347               while (next_data < &he_data[db->head->nentries]
 348                      && (*next_data)->packet == off_alloc);
 349
 350               off_alloc += (dh->allocsize + BLOCK_ALIGN_M1) & ~BLOCK_ALIGN_M1;
 351             }
 352         }
 353       assert (off_alloc == off_allocend);
 354
 355       assert (off_alloc <= db->head->first_free);
 356       if (off_alloc == db->head->first_free)
 357         /* We are done, that was the last block.  */
 358         break;
 359     }
 360   assert (next_hash == &he[db->head->nentries]);
 361   assert (next_data == &he_data[db->head->nentries]);
 362
 363   /* Now perform the actual moves.  */
 364   if (moves != NULL)
 365     {
 366       struct moveinfo *runp = moves->next;
 367       do
 368         {
 369           assert ((char *) runp->to >= db->data);
 370           assert ((char *) runp->to + runp->size
 371                   <= db->data  + db->head->first_free);
 372           assert ((char *) runp->from >= db->data);
 373           assert ((char *) runp->from + runp->size
 374                   <= db->data  + db->head->first_free);
 375
 376           /* The regions may overlap.  */
 377           memmove (runp->to, runp->from, runp->size);
 378           runp = runp->next;
 379         }
 380       while (runp != moves->next);
 381
 382       if (__builtin_expect (debug_level >= 3, 0))
 383         dbg_log (_("freed %zu bytes in %s cache"),
 384                  db->head->first_free
 385                  - ((char *) moves->to + moves->size - db->data),
 386                  dbnames[db - dbs]);
 387
 388       /* The byte past the end of the last copied block is the next
 389          available byte.  */
 390       db->head->first_free = (char *) moves->to + moves->size - db->data;
 391
 392       /* Consistency check.  */
 393       if (__builtin_expect (debug_level >= 3, 0))
 394         {
 395           for (size_t idx = 0; idx < db->head->module; ++idx)
 396             {
 397               ref_t run = db->head->array[idx];
 398               size_t cnt = 0;
 399
 400               while (run != ENDREF)
 401                 {
 402                   if (run + sizeof (struct hashentry) > db->head->first_free)
 403                     {
 404                       dbg_log ("entry %zu in hash bucket %zu out of bounds: "
 405                                "%" PRIu32 "+%zu > %zu\n",
 406                                cnt, idx, run, sizeof (struct hashentry),
 407                                db->head->first_free);
 408                       break;
 409                     }
 410
 411                   struct hashentry *he = (struct hashentry *) (db->data + run);
 412
 413                   if (he->key + he->len > db->head->first_free)
 414                     dbg_log ("key of entry %zu in hash bucket %zu out of "
 415                              "bounds: %" PRIu32 "+%zu > %zu\n",
 416                              cnt, idx, he->key, he->len, db->head->first_free);
 417
 418                   if (he->packet + sizeof (struct datahead)
 419                       > db->head->first_free)
 420                     dbg_log ("packet of entry %zu in hash bucket %zu out of "
 421                              "bounds: %" PRIu32 "+%zu > %zu\n",
 422                              cnt, idx, he->packet, sizeof (struct datahead),
 423                              db->head->first_free);
 424                   else
 425                     {
 426                       struct datahead *dh = (struct datahead *) (db->data
 427                                                                  + he->packet);
 428                       if (he->packet + dh->allocsize
 429                           > db->head->first_free)
 430                         dbg_log ("full key of entry %zu in hash bucket %zu "
 431                                  "out of bounds: %" PRIu32 "+%zu > %zu",
 432                                  cnt, idx, he->packet, dh->allocsize,
 433                                  db->head->first_free);
 434                     }
 435
 436                   run = he->next;
 437                   ++cnt;
 438                 }
 439             }
 440         }
 441     }
 442
 443   /* Make sure the data on disk is updated.  */
 444   if (db->persistent)
 445     msync (db->head, db->data + db->head->first_free - (char *) db->head,
 446            MS_ASYNC);
 447
 448   /* We are done.  */
 449  out:
 450   pthread_mutex_unlock (&db->memlock);
 451   pthread_rwlock_unlock (&db->lock);
 452 }
 453
 454
 455 void *
 456 mempool_alloc (struct database_dyn *db, size_t len)
 457 {
 458   /* Make sure LEN is a multiple of our maximum alignment so we can
 459      keep track of used memory is multiples of this alignment value.  */
 460   if ((len & BLOCK_ALIGN_M1) != 0)
 461     len += BLOCK_ALIGN - (len & BLOCK_ALIGN_M1);
 462
 463   pthread_mutex_lock (&db->memlock);
 464
 465   assert ((db->head->first_free & BLOCK_ALIGN_M1) == 0);
 466
 467   bool tried_resize = false;
 468   void *res;
 469  retry:
 470   res = db->data + db->head->first_free;
 471
 472   if (__builtin_expect (db->head->first_free + len > db->head->data_size, 0))
 473     {
 474       if (! tried_resize)
 475         {
 476           /* Try to resize the database.  Grow size of 1/8th.  */
 477           size_t new_data_size = db->head->data_size + db->head->data_size / 8;
 478           size_t oldtotal = (sizeof (struct database_pers_head)
 479                              + db->head->module * sizeof (ref_t)
 480                              + db->head->data_size);
 481           size_t newtotal = (sizeof (struct database_pers_head)
 482                              + db->head->module * sizeof (ref_t)
 483                              + new_data_size);
 484
 485           if ((!db->mmap_used || ftruncate (db->wr_fd, newtotal) != 0)
 486               /* Try to resize the mapping.  Note: no MREMAP_MAYMOVE.  */
 487               && mremap (db->head, oldtotal, newtotal, 0) == 0)
 488             {
 489               db->head->data_size = new_data_size;
 490               tried_resize = true;
 491               goto retry;
 492             }
 493         }
 494
 495       if (! db->last_alloc_failed)
 496         {
 497           dbg_log (_("no more memory for database '%s'"), dbnames[db - dbs]);
 498
 499           db->last_alloc_failed = true;
 500         }
 501
 502       /* No luck.  */
 503       res = NULL;
 504     }
 505   else
 506     {
 507       db->head->first_free += len;
 508
 509       db->last_alloc_failed = false;
 510     }
 511
 512   pthread_mutex_unlock (&db->memlock);
 513
 514   return res;
 515 }