Back to index

glibc  2.9
mem.c
Go to the documentation of this file.
00001 /* Cache memory handling.
00002    Copyright (C) 2004, 2005, 2006, 2008 Free Software Foundation, Inc.
00003    This file is part of the GNU C Library.
00004    Contributed by Ulrich Drepper <drepper@redhat.com>, 2004.
00005 
00006    This program is free software; you can redistribute it and/or modify
00007    it under the terms of the GNU General Public License as published
00008    by the Free Software Foundation; version 2 of the License, or
00009    (at your option) any later version.
00010 
00011    This program is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014    GNU General Public License for more details.
00015 
00016    You should have received a copy of the GNU General Public License
00017    along with this program; if not, write to the Free Software Foundation,
00018    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
00019 
00020 #include <assert.h>
00021 #include <errno.h>
00022 #include <error.h>
00023 #include <fcntl.h>
00024 #include <inttypes.h>
00025 #include <libintl.h>
00026 #include <limits.h>
00027 #include <obstack.h>
00028 #include <stdlib.h>
00029 #include <string.h>
00030 #include <unistd.h>
00031 #include <sys/mman.h>
00032 #include <sys/param.h>
00033 
00034 #include "dbg_log.h"
00035 #include "nscd.h"
00036 
00037 
00038 /* Wrapper functions with error checking for standard functions.  */
00039 extern void *xmalloc (size_t n);
00040 extern void *xcalloc (size_t n, size_t s);
00041 
00042 
00043 static int
00044 sort_he (const void *p1, const void *p2)
00045 {
00046   struct hashentry *h1 = *(struct hashentry **) p1;
00047   struct hashentry *h2 = *(struct hashentry **) p2;
00048 
00049   if (h1 < h2)
00050     return -1;
00051   if (h1 > h2)
00052     return 1;
00053   return 0;
00054 }
00055 
00056 
00057 static int
00058 sort_he_data (const void *p1, const void *p2)
00059 {
00060   struct hashentry *h1 = *(struct hashentry **) p1;
00061   struct hashentry *h2 = *(struct hashentry **) p2;
00062 
00063   if (h1->packet < h2->packet)
00064     return -1;
00065   if (h1->packet > h2->packet)
00066     return 1;
00067   return 0;
00068 }
00069 
00070 
00071 /* Basic definitions for the bitmap implementation.  Only BITMAP_T
00072    needs to be changed to choose a different word size.  */
00073 #define BITMAP_T uint8_t
00074 #define BITS (CHAR_BIT * sizeof (BITMAP_T))
00075 #define ALLBITS ((((BITMAP_T) 1) << BITS) - 1)
00076 #define HIGHBIT (((BITMAP_T) 1) << (BITS - 1))
00077 
00078 
00079 static void
00080 markrange (BITMAP_T *mark, ref_t start, size_t len)
00081 {
00082   /* Adjust parameters for block alignment.  */
00083   assert ((start & BLOCK_ALIGN_M1) == 0);
00084   start /= BLOCK_ALIGN;
00085   len = (len + BLOCK_ALIGN_M1) / BLOCK_ALIGN;
00086 
00087   size_t elem = start / BITS;
00088 
00089   if (start % BITS != 0)
00090     {
00091       if (start % BITS + len <= BITS)
00092        {
00093          /* All fits in the partial byte.  */
00094          mark[elem] |= (ALLBITS >> (BITS - len)) << (start % BITS);
00095          return;
00096        }
00097 
00098       mark[elem++] |= ALLBITS << (start % BITS);
00099       len -= BITS - (start % BITS);
00100     }
00101 
00102   while (len >= BITS)
00103     {
00104       mark[elem++] = ALLBITS;
00105       len -= BITS;
00106     }
00107 
00108   if (len > 0)
00109     mark[elem] |= ALLBITS >> (BITS - len);
00110 }
00111 
00112 
00113 void
00114 gc (struct database_dyn *db)
00115 {
00116   /* We need write access.  */
00117   pthread_rwlock_wrlock (&db->lock);
00118 
00119   /* And the memory handling lock.  */
00120   pthread_mutex_lock (&db->memlock);
00121 
00122   /* We need an array representing the data area.  All memory
00123      allocation is BLOCK_ALIGN aligned so this is the level at which
00124      we have to look at the memory.  We use a mark and sweep algorithm
00125      where the marks are placed in this array.  */
00126   assert (db->head->first_free % BLOCK_ALIGN == 0);
00127 
00128   BITMAP_T *mark;
00129   bool mark_use_malloc;
00130   /* In prune_cache we are also using a dynamically allocated array.
00131      If the array in the caller is too large we have malloc'ed it.  */
00132   size_t stack_used = sizeof (bool) * db->head->module;
00133   if (__builtin_expect (stack_used > MAX_STACK_USE, 0))
00134     stack_used = 0;
00135   size_t nmark = (db->head->first_free / BLOCK_ALIGN + BITS - 1) / BITS;
00136   size_t memory_needed = nmark * sizeof (BITMAP_T);
00137   if (stack_used + memory_needed <= MAX_STACK_USE)
00138     {
00139       mark = (BITMAP_T *) alloca (memory_needed);
00140       mark_use_malloc = false;
00141       memset (mark, '\0', memory_needed);
00142       stack_used += memory_needed;
00143     }
00144   else
00145     {
00146       mark = (BITMAP_T *) xcalloc (1, memory_needed);
00147       mark_use_malloc = true;
00148     }
00149 
00150   /* Create an array which can hold pointer to all the entries in hash
00151      entries.  */
00152   memory_needed = 2 * db->head->nentries * sizeof (struct hashentry *);
00153   struct hashentry **he;
00154   struct hashentry **he_data;
00155   bool he_use_malloc;
00156   if (stack_used + memory_needed <= MAX_STACK_USE)
00157     {
00158       he = alloca (db->head->nentries * sizeof (struct hashentry *));
00159       he_data = alloca (db->head->nentries * sizeof (struct hashentry *));
00160       he_use_malloc = false;
00161       stack_used += memory_needed;
00162     }
00163   else
00164     {
00165       he = xmalloc (memory_needed);
00166       he_data = &he[db->head->nentries * sizeof (struct hashentry *)];
00167       he_use_malloc = true;
00168     }
00169 
00170   size_t cnt = 0;
00171   for (size_t idx = 0; idx < db->head->module; ++idx)
00172     {
00173       ref_t *prevp = &db->head->array[idx];
00174       ref_t run = *prevp;
00175 
00176       while (run != ENDREF)
00177        {
00178          assert (cnt < db->head->nentries);
00179          he[cnt] = (struct hashentry *) (db->data + run);
00180 
00181          he[cnt]->prevp = prevp;
00182          prevp = &he[cnt]->next;
00183 
00184          /* This is the hash entry itself.  */
00185          markrange (mark, run, sizeof (struct hashentry));
00186 
00187          /* Add the information for the data itself.  We do this
00188             only for the one special entry marked with FIRST.  */
00189          if (he[cnt]->first)
00190            {
00191              struct datahead *dh
00192               = (struct datahead *) (db->data + he[cnt]->packet);
00193              markrange (mark, he[cnt]->packet, dh->allocsize);
00194            }
00195 
00196          run = he[cnt]->next;
00197 
00198          ++cnt;
00199        }
00200     }
00201   assert (cnt == db->head->nentries);
00202 
00203   /* Go through the list of in-flight memory blocks.  */
00204   struct mem_in_flight *mrunp = mem_in_flight_list;
00205   while (mrunp != NULL)
00206     {
00207       /* NB: There can be no race between this test and another thread
00208         setting the field to the index we are looking for because
00209         this would require the other thread to also have the memlock
00210         for the database.
00211 
00212        NB2: we do not have to look at latter blocks (higher indices) if
00213        earlier blocks are not in flight.  They are always allocated in
00214        sequence.  */
00215       for (enum in_flight idx = IDX_result_data;
00216           idx < IDX_last && mrunp->block[idx].dbidx == db - dbs; ++idx)
00217        {
00218          assert (mrunp->block[idx].blockoff >= 0);
00219          assert (mrunp->block[idx].blocklen < db->memsize);
00220          assert (mrunp->block[idx].blockoff
00221                 + mrunp->block[0].blocklen <= db->memsize);
00222          markrange (mark, mrunp->block[idx].blockoff,
00223                    mrunp->block[idx].blocklen);
00224        }
00225 
00226       mrunp = mrunp->next;
00227     }
00228 
00229   /* Sort the entries by the addresses of the referenced data.  All
00230      the entries pointing to the same DATAHEAD object will have the
00231      same key.  Stability of the sorting is unimportant.  */
00232   memcpy (he_data, he, cnt * sizeof (struct hashentry *));
00233   qsort (he_data, cnt, sizeof (struct hashentry *), sort_he_data);
00234 
00235   /* Sort the entries by their address.  */
00236   qsort (he, cnt, sizeof (struct hashentry *), sort_he);
00237 
00238 #define obstack_chunk_alloc xmalloc
00239 #define obstack_chunk_free free
00240   struct obstack ob;
00241   obstack_init (&ob);
00242 
00243   /* Determine the highest used address.  */
00244   size_t high = nmark;
00245   while (high > 0 && mark[high - 1] == 0)
00246     --high;
00247 
00248   /* No memory used.  */
00249   if (high == 0)
00250     {
00251       db->head->first_free = 0;
00252       goto out;
00253     }
00254 
00255   /* Determine the highest offset.  */
00256   BITMAP_T mask = HIGHBIT;
00257   ref_t highref = (high * BITS - 1) * BLOCK_ALIGN;
00258   while ((mark[high - 1] & mask) == 0)
00259     {
00260       mask >>= 1;
00261       highref -= BLOCK_ALIGN;
00262     }
00263 
00264   /* Now we can iterate over the MARK array and find bits which are not
00265      set.  These represent memory which can be recovered.  */
00266   size_t byte = 0;
00267   /* Find the first gap.  */
00268   while (byte < high && mark[byte] == ALLBITS)
00269     ++byte;
00270 
00271   if (byte == high
00272       || (byte == high - 1 && (mark[byte] & ~(mask | (mask - 1))) == 0))
00273     /* No gap.  */
00274     goto out;
00275 
00276   mask = 1;
00277   cnt = 0;
00278   while ((mark[byte] & mask) != 0)
00279     {
00280       ++cnt;
00281       mask <<= 1;
00282     }
00283   ref_t off_free = (byte * BITS + cnt) * BLOCK_ALIGN;
00284   assert (off_free <= db->head->first_free);
00285 
00286   struct hashentry **next_hash = he;
00287   struct hashentry **next_data = he_data;
00288 
00289   /* Skip over the hash entries in the first block which does not get
00290      moved.  */
00291   while (next_hash < &he[db->head->nentries]
00292         && *next_hash < (struct hashentry *) (db->data + off_free))
00293     ++next_hash;
00294 
00295   while (next_data < &he_data[db->head->nentries]
00296         && (*next_data)->packet < off_free)
00297     ++next_data;
00298 
00299 
00300   /* Now we start modifying the data.  Make sure all readers of the
00301      data are aware of this and temporarily don't use the data.  */
00302   ++db->head->gc_cycle;
00303   assert ((db->head->gc_cycle & 1) == 1);
00304 
00305 
00306   /* We do not perform the move operations right away since the
00307      he_data array is not sorted by the address of the data.  */
00308   struct moveinfo
00309   {
00310     void *from;
00311     void *to;
00312     size_t size;
00313     struct moveinfo *next;
00314   } *moves = NULL;
00315 
00316   while (byte < high)
00317     {
00318       /* Search for the next filled block.  BYTE is the index of the
00319         entry in MARK, MASK is the bit, and CNT is the bit number.
00320         OFF_FILLED is the corresponding offset.  */
00321       if ((mark[byte] & ~(mask - 1)) == 0)
00322        {
00323          /* No other bit set in the same element of MARK.  Search in the
00324             following memory.  */
00325          do
00326            ++byte;
00327          while (byte < high && mark[byte] == 0);
00328 
00329          if (byte == high)
00330            /* That was it.  */
00331            break;
00332 
00333          mask = 1;
00334          cnt = 0;
00335        }
00336       /* Find the exact bit.  */
00337       while ((mark[byte] & mask) == 0)
00338        {
00339          ++cnt;
00340          mask <<= 1;
00341        }
00342 
00343       ref_t off_alloc = (byte * BITS + cnt) * BLOCK_ALIGN;
00344       assert (off_alloc <= db->head->first_free);
00345 
00346       /* Find the end of the used area.  */
00347       if ((mark[byte] & ~(mask - 1)) == (BITMAP_T) ~(mask - 1))
00348        {
00349          /* All other bits set.  Search the next bytes in MARK.  */
00350          do
00351            ++byte;
00352          while (byte < high && mark[byte] == ALLBITS);
00353 
00354          mask = 1;
00355          cnt = 0;
00356        }
00357       if (byte < high)
00358        {
00359          /* Find the exact bit.  */
00360          while ((mark[byte] & mask) != 0)
00361            {
00362              ++cnt;
00363              mask <<= 1;
00364            }
00365        }
00366 
00367       ref_t off_allocend = (byte * BITS + cnt) * BLOCK_ALIGN;
00368       assert (off_allocend <= db->head->first_free);
00369       /* Now we know that we can copy the area from OFF_ALLOC to
00370         OFF_ALLOCEND (not included) to the memory starting at
00371         OFF_FREE.  First fix up all the entries for the
00372         displacement.  */
00373       ref_t disp = off_alloc - off_free;
00374 
00375       struct moveinfo *new_move;
00376       if (stack_used + sizeof (*new_move) <= MAX_STACK_USE)
00377        {
00378          new_move = alloca (sizeof (*new_move));
00379          stack_used += sizeof (*new_move);
00380        }
00381       else
00382        new_move = obstack_alloc (&ob, sizeof (*new_move));
00383       new_move->from = db->data + off_alloc;
00384       new_move->to = db->data + off_free;
00385       new_move->size = off_allocend - off_alloc;
00386       /* Create a circular list to be always able to append at the end.  */
00387       if (moves == NULL)
00388        moves = new_move->next = new_move;
00389       else
00390        {
00391          new_move->next = moves->next;
00392          moves = moves->next = new_move;
00393        }
00394 
00395       /* The following loop will prepare to move this much data.  */
00396       off_free += off_allocend - off_alloc;
00397 
00398       while (off_alloc < off_allocend)
00399        {
00400          /* Determine whether the next entry is for a hash entry or
00401             the data.  */
00402          if ((struct hashentry *) (db->data + off_alloc) == *next_hash)
00403            {
00404              /* Just correct the forward reference.  */
00405              *(*next_hash++)->prevp -= disp;
00406 
00407              off_alloc += ((sizeof (struct hashentry) + BLOCK_ALIGN_M1)
00408                          & ~BLOCK_ALIGN_M1);
00409            }
00410          else
00411            {
00412              assert (next_data < &he_data[db->head->nentries]);
00413              assert ((*next_data)->packet == off_alloc);
00414 
00415              struct datahead *dh = (struct datahead *) (db->data + off_alloc);
00416              do
00417               {
00418                 assert ((*next_data)->key >= (*next_data)->packet);
00419                 assert ((*next_data)->key + (*next_data)->len
00420                        <= (*next_data)->packet + dh->allocsize);
00421 
00422                 (*next_data)->packet -= disp;
00423                 (*next_data)->key -= disp;
00424                 ++next_data;
00425               }
00426              while (next_data < &he_data[db->head->nentries]
00427                    && (*next_data)->packet == off_alloc);
00428 
00429              off_alloc += (dh->allocsize + BLOCK_ALIGN_M1) & ~BLOCK_ALIGN_M1;
00430            }
00431        }
00432       assert (off_alloc == off_allocend);
00433 
00434       assert (off_alloc <= db->head->first_free);
00435       if (off_alloc == db->head->first_free)
00436        /* We are done, that was the last block.  */
00437        break;
00438     }
00439   assert (next_hash == &he[db->head->nentries]);
00440   assert (next_data == &he_data[db->head->nentries]);
00441 
00442   /* Now perform the actual moves.  */
00443   if (moves != NULL)
00444     {
00445       struct moveinfo *runp = moves->next;
00446       do
00447        {
00448          assert ((char *) runp->to >= db->data);
00449          assert ((char *) runp->to + runp->size
00450                 <= db->data  + db->head->first_free);
00451          assert ((char *) runp->from >= db->data);
00452          assert ((char *) runp->from + runp->size
00453                 <= db->data  + db->head->first_free);
00454 
00455          /* The regions may overlap.  */
00456          memmove (runp->to, runp->from, runp->size);
00457          runp = runp->next;
00458        }
00459       while (runp != moves->next);
00460 
00461       if (__builtin_expect (debug_level >= 3, 0))
00462        dbg_log (_("freed %zu bytes in %s cache"),
00463                db->head->first_free
00464                - ((char *) moves->to + moves->size - db->data),
00465                dbnames[db - dbs]);
00466 
00467       /* The byte past the end of the last copied block is the next
00468         available byte.  */
00469       db->head->first_free = (char *) moves->to + moves->size - db->data;
00470 
00471       /* Consistency check.  */
00472       if (__builtin_expect (debug_level >= 3, 0))
00473        {
00474          for (size_t idx = 0; idx < db->head->module; ++idx)
00475            {
00476              ref_t run = db->head->array[idx];
00477              size_t cnt = 0;
00478 
00479              while (run != ENDREF)
00480               {
00481                 if (run + sizeof (struct hashentry) > db->head->first_free)
00482                   {
00483                     dbg_log ("entry %zu in hash bucket %zu out of bounds: "
00484                             "%" PRIu32 "+%zu > %zu\n",
00485                             cnt, idx, run, sizeof (struct hashentry),
00486                             (size_t) db->head->first_free);
00487                     break;
00488                   }
00489 
00490                 struct hashentry *he = (struct hashentry *) (db->data + run);
00491 
00492                 if (he->key + he->len > db->head->first_free)
00493                   dbg_log ("key of entry %zu in hash bucket %zu out of "
00494                           "bounds: %" PRIu32 "+%zu > %zu\n",
00495                           cnt, idx, he->key, (size_t) he->len,
00496                           (size_t) db->head->first_free);
00497 
00498                 if (he->packet + sizeof (struct datahead)
00499                     > db->head->first_free)
00500                   dbg_log ("packet of entry %zu in hash bucket %zu out of "
00501                           "bounds: %" PRIu32 "+%zu > %zu\n",
00502                           cnt, idx, he->packet, sizeof (struct datahead),
00503                           (size_t) db->head->first_free);
00504                 else
00505                   {
00506                     struct datahead *dh = (struct datahead *) (db->data
00507                                                          + he->packet);
00508                     if (he->packet + dh->allocsize
00509                        > db->head->first_free)
00510                      dbg_log ("full key of entry %zu in hash bucket %zu "
00511                              "out of bounds: %" PRIu32 "+%zu > %zu",
00512                              cnt, idx, he->packet, (size_t) dh->allocsize,
00513                              (size_t) db->head->first_free);
00514                   }
00515 
00516                 run = he->next;
00517                 ++cnt;
00518               }
00519            }
00520        }
00521     }
00522 
00523   /* Make sure the data on disk is updated.  */
00524   if (db->persistent)
00525     msync (db->head, db->data + db->head->first_free - (char *) db->head,
00526           MS_ASYNC);
00527 
00528 
00529   /* Now we are done modifying the data.  */
00530   ++db->head->gc_cycle;
00531   assert ((db->head->gc_cycle & 1) == 0);
00532 
00533   /* We are done.  */
00534  out:
00535   pthread_mutex_unlock (&db->memlock);
00536   pthread_rwlock_unlock (&db->lock);
00537 
00538   if (he_use_malloc)
00539     free (he);
00540   if (mark_use_malloc)
00541     free (mark);
00542 
00543   obstack_free (&ob, NULL);
00544 }
00545 
00546 
00547 void *
00548 mempool_alloc (struct database_dyn *db, size_t len, enum in_flight idx)
00549 {
00550   /* Make sure LEN is a multiple of our maximum alignment so we can
00551      keep track of used memory is multiples of this alignment value.  */
00552   if ((len & BLOCK_ALIGN_M1) != 0)
00553     len += BLOCK_ALIGN - (len & BLOCK_ALIGN_M1);
00554 
00555   pthread_mutex_lock (&db->memlock);
00556 
00557   assert ((db->head->first_free & BLOCK_ALIGN_M1) == 0);
00558 
00559   bool tried_resize = false;
00560   void *res;
00561  retry:
00562   res = db->data + db->head->first_free;
00563 
00564   if (__builtin_expect (db->head->first_free + len > db->head->data_size, 0))
00565     {
00566       if (! tried_resize)
00567        {
00568          /* Try to resize the database.  Grow size of 1/8th.  */
00569          size_t oldtotal = (sizeof (struct database_pers_head)
00570                           + roundup (db->head->module * sizeof (ref_t),
00571                                    ALIGN)
00572                           + db->head->data_size);
00573          size_t new_data_size = (db->head->data_size
00574                               + MAX (2 * len, db->head->data_size / 8));
00575          size_t newtotal = (sizeof (struct database_pers_head)
00576                           + roundup (db->head->module * sizeof (ref_t), ALIGN)
00577                           + new_data_size);
00578          if (newtotal > db->max_db_size)
00579            {
00580              new_data_size -= newtotal - db->max_db_size;
00581              newtotal = db->max_db_size;
00582            }
00583 
00584          if (db->mmap_used && newtotal > oldtotal
00585              /* We only have to adjust the file size.  The new pages
00586                become magically available.  */
00587              && TEMP_FAILURE_RETRY_VAL (posix_fallocate (db->wr_fd, oldtotal,
00588                                                    newtotal
00589                                                    - oldtotal)) == 0)
00590            {
00591              db->head->data_size = new_data_size;
00592              tried_resize = true;
00593              goto retry;
00594            }
00595        }
00596 
00597       if (! db->last_alloc_failed)
00598        {
00599          dbg_log (_("no more memory for database '%s'"), dbnames[db - dbs]);
00600 
00601          db->last_alloc_failed = true;
00602        }
00603 
00604       /* No luck.  */
00605       res = NULL;
00606     }
00607   else
00608     {
00609       /* Remember that we have allocated this memory.  */
00610       assert (idx >= 0 && idx < IDX_last);
00611       mem_in_flight.block[idx].dbidx = db - dbs;
00612       mem_in_flight.block[idx].blocklen = len;
00613       mem_in_flight.block[idx].blockoff = db->head->first_free;
00614 
00615       db->head->first_free += len;
00616 
00617       db->last_alloc_failed = false;
00618 
00619     }
00620 
00621   pthread_mutex_unlock (&db->memlock);
00622 
00623   return res;
00624 }