nscd/mem.c

   1 /* Cache memory handling.
   2    Copyright (C) 2004, 2005, 2006, 2008, 2009 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    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published
   8    by the Free Software Foundation; version 2 of the License, or
   9    (at your option) any later version.
  10
  11    This program 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
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software Foundation,
  18    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  19
  20 #include <assert.h>
  21 #include <errno.h>
  22 #include <error.h>
  23 #include <fcntl.h>
  24 #include <inttypes.h>
  25 #include <libintl.h>
  26 #include <limits.h>
  27 #include <obstack.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 /* Wrapper functions with error checking for standard functions.  */
  39 extern void *xmalloc (size_t n);
  40 extern void *xcalloc (size_t n, size_t s);
  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   assert ((start & BLOCK_ALIGN_M1) == 0);
  84   start /= BLOCK_ALIGN;
  85   len = (len + BLOCK_ALIGN_M1) / BLOCK_ALIGN;
  86
  87   size_t elem = start / BITS;
  88
  89   if (start % BITS != 0)
  90     {
  91       if (start % BITS + len <= BITS)
  92         {
  93           /* All fits in the partial byte.  */
  94           mark[elem] |= (ALLBITS >> (BITS - len)) << (start % BITS);
  95           return;
  96         }
  97
  98       mark[elem++] |= ALLBITS << (start % BITS);
  99       len -= BITS - (start % BITS);
 100     }
 101
 102   while (len >= BITS)
 103     {
 104       mark[elem++] = ALLBITS;
 105       len -= BITS;
 106     }
 107
 108   if (len > 0)
 109     mark[elem] |= ALLBITS >> (BITS - len);
 110 }
 111
 112
 113 void
 114 gc (struct database_dyn *db)
 115 {
 116   /* We need write access.  */
 117   pthread_rwlock_wrlock (&db->lock);
 118
 119   /* And the memory handling lock.  */
 120   pthread_mutex_lock (&db->memlock);
 121
 122   /* We need an array representing the data area.  All memory
 123      allocation is BLOCK_ALIGN aligned so this is the level at which
 124      we have to look at the memory.  We use a mark and sweep algorithm
 125      where the marks are placed in this array.  */
 126   assert (db->head->first_free % BLOCK_ALIGN == 0);
 127
 128   BITMAP_T *mark;
 129   bool mark_use_malloc;
 130   /* In prune_cache we are also using a dynamically allocated array.
 131      If the array in the caller is too large we have malloc'ed it.  */
 132   size_t stack_used = sizeof (bool) * db->head->module;
 133   if (__builtin_expect (stack_used > MAX_STACK_USE, 0))
 134     stack_used = 0;
 135   size_t nmark = (db->head->first_free / BLOCK_ALIGN + BITS - 1) / BITS;
 136   size_t memory_needed = nmark * sizeof (BITMAP_T);
 137   if (__builtin_expect (stack_used + memory_needed <= MAX_STACK_USE, 1))
 138     {
 139       mark = (BITMAP_T *) alloca_account (memory_needed, stack_used);
 140       mark_use_malloc = false;
 141       memset (mark, '\0', memory_needed);
 142     }
 143   else
 144     {
 145       mark = (BITMAP_T *) xcalloc (1, memory_needed);
 146       mark_use_malloc = true;
 147     }
 148
 149   /* Create an array which can hold pointer to all the entries in hash
 150      entries.  */
 151   memory_needed = 2 * db->head->nentries * sizeof (struct hashentry *);
 152   struct hashentry **he;
 153   struct hashentry **he_data;
 154   bool he_use_malloc;
 155   if (__builtin_expect (stack_used + memory_needed <= MAX_STACK_USE, 1))
 156     {
 157       he = alloca_account (memory_needed, stack_used);
 158       he_use_malloc = false;
 159     }
 160   else
 161     {
 162       he = xmalloc (memory_needed);
 163       he_use_malloc = true;
 164     }
 165   he_data = &he[db->head->nentries];
 166
 167   size_t cnt = 0;
 168   for (size_t idx = 0; idx < db->head->module; ++idx)
 169     {
 170       ref_t *prevp = &db->head->array[idx];
 171       ref_t run = *prevp;
 172
 173       while (run != ENDREF)
 174         {
 175           assert (cnt < db->head->nentries);
 176           he[cnt] = (struct hashentry *) (db->data + run);
 177
 178           he[cnt]->prevp = prevp;
 179           prevp = &he[cnt]->next;
 180
 181           /* This is the hash entry itself.  */
 182           markrange (mark, run, sizeof (struct hashentry));
 183
 184           /* Add the information for the data itself.  We do this
 185              only for the one special entry marked with FIRST.  */
 186           if (he[cnt]->first)
 187             {
 188               struct datahead *dh
 189                 = (struct datahead *) (db->data + he[cnt]->packet);
 190               markrange (mark, he[cnt]->packet, dh->allocsize);
 191             }
 192
 193           run = he[cnt]->next;
 194
 195           ++cnt;
 196         }
 197     }
 198   assert (cnt == db->head->nentries);
 199
 200   /* Sort the entries by the addresses of the referenced data.  All
 201      the entries pointing to the same DATAHEAD object will have the
 202      same key.  Stability of the sorting is unimportant.  */
 203   memcpy (he_data, he, cnt * sizeof (struct hashentry *));
 204   qsort (he_data, cnt, sizeof (struct hashentry *), sort_he_data);
 205
 206   /* Sort the entries by their address.  */
 207   qsort (he, cnt, sizeof (struct hashentry *), sort_he);
 208
 209 #define obstack_chunk_alloc xmalloc
 210 #define obstack_chunk_free free
 211   struct obstack ob;
 212   obstack_init (&ob);
 213
 214   /* Determine the highest used address.  */
 215   size_t high = nmark;
 216   while (high > 0 && mark[high - 1] == 0)
 217     --high;
 218
 219   /* No memory used.  */
 220   if (high == 0)
 221     {
 222       db->head->first_free = 0;
 223       goto out;
 224     }
 225
 226   /* Determine the highest offset.  */
 227   BITMAP_T mask = HIGHBIT;
 228   ref_t highref = (high * BITS - 1) * BLOCK_ALIGN;
 229   while ((mark[high - 1] & mask) == 0)
 230     {
 231       mask >>= 1;
 232       highref -= BLOCK_ALIGN;
 233     }
 234
 235   /* Now we can iterate over the MARK array and find bits which are not
 236      set.  These represent memory which can be recovered.  */
 237   size_t byte = 0;
 238   /* Find the first gap.  */
 239   while (byte < high && mark[byte] == ALLBITS)
 240     ++byte;
 241
 242   if (byte == high
 243       || (byte == high - 1 && (mark[byte] & ~(mask | (mask - 1))) == 0))
 244     /* No gap.  */
 245     goto out;
 246
 247   mask = 1;
 248   cnt = 0;
 249   while ((mark[byte] & mask) != 0)
 250     {
 251       ++cnt;
 252       mask <<= 1;
 253     }
 254   ref_t off_free = (byte * BITS + cnt) * BLOCK_ALIGN;
 255   assert (off_free <= db->head->first_free);
 256
 257   struct hashentry **next_hash = he;
 258   struct hashentry **next_data = he_data;
 259
 260   /* Skip over the hash entries in the first block which does not get
 261      moved.  */
 262   while (next_hash < &he[db->head->nentries]
 263          && *next_hash < (struct hashentry *) (db->data + off_free))
 264     ++next_hash;
 265
 266   while (next_data < &he_data[db->head->nentries]
 267          && (*next_data)->packet < off_free)
 268     ++next_data;
 269
 270
 271   /* Now we start modifying the data.  Make sure all readers of the
 272      data are aware of this and temporarily don't use the data.  */
 273   ++db->head->gc_cycle;
 274   assert ((db->head->gc_cycle & 1) == 1);
 275
 276
 277   /* We do not perform the move operations right away since the
 278      he_data array is not sorted by the address of the data.  */
 279   struct moveinfo
 280   {
 281     void *from;
 282     void *to;
 283     size_t size;
 284     struct moveinfo *next;
 285   } *moves = NULL;
 286
 287   while (byte < high)
 288     {
 289       /* Search for the next filled block.  BYTE is the index of the
 290          entry in MARK, MASK is the bit, and CNT is the bit number.
 291          OFF_FILLED is the corresponding offset.  */
 292       if ((mark[byte] & ~(mask - 1)) == 0)
 293         {
 294           /* No other bit set in the same element of MARK.  Search in the
 295              following memory.  */
 296           do
 297             ++byte;
 298           while (byte < high && mark[byte] == 0);
 299
 300           if (byte == high)
 301             /* That was it.  */
 302             break;
 303
 304           mask = 1;
 305           cnt = 0;
 306         }
 307       /* Find the exact bit.  */
 308       while ((mark[byte] & mask) == 0)
 309         {
 310           ++cnt;
 311           mask <<= 1;
 312         }
 313
 314       ref_t off_alloc = (byte * BITS + cnt) * BLOCK_ALIGN;
 315       assert (off_alloc <= db->head->first_free);
 316
 317       /* Find the end of the used area.  */
 318       if ((mark[byte] & ~(mask - 1)) == (BITMAP_T) ~(mask - 1))
 319         {
 320           /* All other bits set.  Search the next bytes in MARK.  */
 321           do
 322             ++byte;
 323           while (byte < high && mark[byte] == ALLBITS);
 324
 325           mask = 1;
 326           cnt = 0;
 327         }
 328       if (byte < high)
 329         {
 330           /* Find the exact bit.  */
 331           while ((mark[byte] & mask) != 0)
 332             {
 333               ++cnt;
 334               mask <<= 1;
 335             }
 336         }
 337
 338       ref_t off_allocend = (byte * BITS + cnt) * BLOCK_ALIGN;
 339       assert (off_allocend <= db->head->first_free);
 340       /* Now we know that we can copy the area from OFF_ALLOC to
 341          OFF_ALLOCEND (not included) to the memory starting at
 342          OFF_FREE.  First fix up all the entries for the
 343          displacement.  */
 344       ref_t disp = off_alloc - off_free;
 345
 346       struct moveinfo *new_move;
 347       if (__builtin_expect (stack_used + sizeof (*new_move) <= MAX_STACK_USE,
 348                             1))
 349         new_move = alloca_account (sizeof (*new_move), stack_used);
 350       else
 351         new_move = obstack_alloc (&ob, sizeof (*new_move));
 352       new_move->from = db->data + off_alloc;
 353       new_move->to = db->data + off_free;
 354       new_move->size = off_allocend - off_alloc;
 355       /* Create a circular list to be always able to append at the end.  */
 356       if (moves == NULL)
 357         moves = new_move->next = new_move;
 358       else
 359         {
 360           new_move->next = moves->next;
 361           moves = moves->next = new_move;
 362         }
 363
 364       /* The following loop will prepare to move this much data.  */
 365       off_free += off_allocend - off_alloc;
 366
 367       while (off_alloc < off_allocend)
 368         {
 369           /* Determine whether the next entry is for a hash entry or
 370              the data.  */
 371           if ((struct hashentry *) (db->data + off_alloc) == *next_hash)
 372             {
 373               /* Just correct the forward reference.  */
 374               *(*next_hash++)->prevp -= disp;
 375
 376               off_alloc += ((sizeof (struct hashentry) + BLOCK_ALIGN_M1)
 377                             & ~BLOCK_ALIGN_M1);
 378             }
 379           else
 380             {
 381               assert (next_data < &he_data[db->head->nentries]);
 382               assert ((*next_data)->packet == off_alloc);
 383
 384               struct datahead *dh = (struct datahead *) (db->data + off_alloc);
 385               do
 386                 {
 387                   assert ((*next_data)->key >= (*next_data)->packet);
 388                   assert ((*next_data)->key + (*next_data)->len
 389                           <= (*next_data)->packet + dh->allocsize);
 390
 391                   (*next_data)->packet -= disp;
 392                   (*next_data)->key -= disp;
 393                   ++next_data;
 394                 }
 395               while (next_data < &he_data[db->head->nentries]
 396                      && (*next_data)->packet == off_alloc);
 397
 398               off_alloc += (dh->allocsize + BLOCK_ALIGN_M1) & ~BLOCK_ALIGN_M1;
 399             }
 400         }
 401       assert (off_alloc == off_allocend);
 402
 403       assert (off_alloc <= db->head->first_free);
 404       if (off_alloc == db->head->first_free)
 405         /* We are done, that was the last block.  */
 406         break;
 407     }
 408   assert (next_hash == &he[db->head->nentries]);
 409   assert (next_data == &he_data[db->head->nentries]);
 410
 411   /* Now perform the actual moves.  */
 412   if (moves != NULL)
 413     {
 414       struct moveinfo *runp = moves->next;
 415       do
 416         {
 417           assert ((char *) runp->to >= db->data);
 418           assert ((char *) runp->to + runp->size
 419                   <= db->data  + db->head->first_free);
 420           assert ((char *) runp->from >= db->data);
 421           assert ((char *) runp->from + runp->size
 422                   <= db->data  + db->head->first_free);
 423
 424           /* The regions may overlap.  */
 425           memmove (runp->to, runp->from, runp->size);
 426           runp = runp->next;
 427         }
 428       while (runp != moves->next);
 429
 430       if (__builtin_expect (debug_level >= 3, 0))
 431         dbg_log (_("freed %zu bytes in %s cache"),
 432                  db->head->first_free
 433                  - ((char *) moves->to + moves->size - db->data),
 434                  dbnames[db - dbs]);
 435
 436       /* The byte past the end of the last copied block is the next
 437          available byte.  */
 438       db->head->first_free = (char *) moves->to + moves->size - db->data;
 439
 440       /* Consistency check.  */
 441       if (__builtin_expect (debug_level >= 3, 0))
 442         {
 443           for (size_t idx = 0; idx < db->head->module; ++idx)
 444             {
 445               ref_t run = db->head->array[idx];
 446               size_t cnt = 0;
 447
 448               while (run != ENDREF)
 449                 {
 450                   if (run + sizeof (struct hashentry) > db->head->first_free)
 451                     {
 452                       dbg_log ("entry %zu in hash bucket %zu out of bounds: "
 453                                "%" PRIu32 "+%zu > %zu\n",
 454                                cnt, idx, run, sizeof (struct hashentry),
 455                                (size_t) db->head->first_free);
 456                       break;
 457                     }
 458
 459                   struct hashentry *he = (struct hashentry *) (db->data + run);
 460
 461                   if (he->key + he->len > db->head->first_free)
 462                     dbg_log ("key of entry %zu in hash bucket %zu out of "
 463                              "bounds: %" PRIu32 "+%zu > %zu\n",
 464                              cnt, idx, he->key, (size_t) he->len,
 465                              (size_t) db->head->first_free);
 466
 467                   if (he->packet + sizeof (struct datahead)
 468                       > db->head->first_free)
 469                     dbg_log ("packet of entry %zu in hash bucket %zu out of "
 470                              "bounds: %" PRIu32 "+%zu > %zu\n",
 471                              cnt, idx, he->packet, sizeof (struct datahead),
 472                              (size_t) db->head->first_free);
 473                   else
 474                     {
 475                       struct datahead *dh = (struct datahead *) (db->data
 476                                                                  + he->packet);
 477                       if (he->packet + dh->allocsize
 478                           > db->head->first_free)
 479                         dbg_log ("full key of entry %zu in hash bucket %zu "
 480                                  "out of bounds: %" PRIu32 "+%zu > %zu",
 481                                  cnt, idx, he->packet, (size_t) dh->allocsize,
 482                                  (size_t) db->head->first_free);
 483                     }
 484
 485                   run = he->next;
 486                   ++cnt;
 487                 }
 488             }
 489         }
 490     }
 491
 492   /* Make sure the data on disk is updated.  */
 493   if (db->persistent)
 494     msync (db->head, db->data + db->head->first_free - (char *) db->head,
 495            MS_ASYNC);
 496
 497
 498   /* Now we are done modifying the data.  */
 499   ++db->head->gc_cycle;
 500   assert ((db->head->gc_cycle & 1) == 0);
 501
 502   /* We are done.  */
 503  out:
 504   pthread_mutex_unlock (&db->memlock);
 505   pthread_rwlock_unlock (&db->lock);
 506
 507   if (he_use_malloc)
 508     free (he);
 509   if (mark_use_malloc)
 510     free (mark);
 511
 512   obstack_free (&ob, NULL);
 513 }
 514
 515
 516 void *
 517 mempool_alloc (struct database_dyn *db, size_t len, int data_alloc)
 518 {
 519   /* Make sure LEN is a multiple of our maximum alignment so we can
 520      keep track of used memory is multiples of this alignment value.  */
 521   if ((len & BLOCK_ALIGN_M1) != 0)
 522     len += BLOCK_ALIGN - (len & BLOCK_ALIGN_M1);
 523
 524   if (data_alloc)
 525     pthread_rwlock_rdlock (&db->lock);
 526
 527   pthread_mutex_lock (&db->memlock);
 528
 529   assert ((db->head->first_free & BLOCK_ALIGN_M1) == 0);
 530
 531   bool tried_resize = false;
 532   void *res;
 533  retry:
 534   res = db->data + db->head->first_free;
 535
 536   if (__builtin_expect (db->head->first_free + len > db->head->data_size, 0))
 537     {
 538       if (! tried_resize)
 539         {
 540           /* Try to resize the database.  Grow size of 1/8th.  */
 541           size_t oldtotal = (sizeof (struct database_pers_head)
 542                              + roundup (db->head->module * sizeof (ref_t),
 543                                         ALIGN)
 544                              + db->head->data_size);
 545           size_t new_data_size = (db->head->data_size
 546                                   + MAX (2 * len, db->head->data_size / 8));
 547           size_t newtotal = (sizeof (struct database_pers_head)
 548                              + roundup (db->head->module * sizeof (ref_t), ALIGN)
 549                              + new_data_size);
 550           if (newtotal > db->max_db_size)
 551             {
 552               new_data_size -= newtotal - db->max_db_size;
 553               newtotal = db->max_db_size;
 554             }
 555
 556           if (db->mmap_used && newtotal > oldtotal
 557               /* We only have to adjust the file size.  The new pages
 558                  become magically available.  */
 559               && TEMP_FAILURE_RETRY_VAL (posix_fallocate (db->wr_fd, oldtotal,
 560                                                           newtotal
 561                                                           - oldtotal)) == 0)
 562             {
 563               db->head->data_size = new_data_size;
 564               tried_resize = true;
 565               goto retry;
 566             }
 567         }
 568
 569       if (data_alloc)
 570         pthread_rwlock_unlock (&db->lock);
 571
 572       if (! db->last_alloc_failed)
 573         {
 574           dbg_log (_("no more memory for database '%s'"), dbnames[db - dbs]);
 575
 576           db->last_alloc_failed = true;
 577         }
 578
 579       ++db->head->addfailed;
 580
 581       /* No luck.  */
 582       res = NULL;
 583     }
 584   else
 585     {
 586       db->head->first_free += len;
 587
 588       db->last_alloc_failed = false;
 589
 590     }
 591
 592   pthread_mutex_unlock (&db->memlock);
 593
 594   return res;
 595 }