nscd/mem.c

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