Updated to fedora-glibc-20080612T1619
[kopensolaris-gnu/glibc.git] / nscd / mem.c
1 /* Cache memory handling.
2    Copyright (C) 2004, 2005, 2006, 2008 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 (stack_used + memory_needed <= MAX_STACK_USE)
138     {
139       mark = (BITMAP_T *) alloca (memory_needed);
140       mark_use_malloc = false;
141       memset (mark, '\0', memory_needed);
142       stack_used += memory_needed;
143     }
144   else
145     {
146       mark = (BITMAP_T *) xcalloc (1, memory_needed);
147       mark_use_malloc = true;
148     }
149
150   /* Create an array which can hold pointer to all the entries in hash
151      entries.  */
152   memory_needed = 2 * db->head->nentries * sizeof (struct hashentry *);
153   struct hashentry **he;
154   struct hashentry **he_data;
155   bool he_use_malloc;
156   if (stack_used + memory_needed <= MAX_STACK_USE)
157     {
158       he = alloca (db->head->nentries * sizeof (struct hashentry *));
159       he_data = alloca (db->head->nentries * sizeof (struct hashentry *));
160       he_use_malloc = false;
161       stack_used += memory_needed;
162     }
163   else
164     {
165       he = xmalloc (memory_needed);
166       he_data = &he[db->head->nentries * sizeof (struct hashentry *)];
167       he_use_malloc = true;
168     }
169
170   size_t cnt = 0;
171   for (size_t idx = 0; idx < db->head->module; ++idx)
172     {
173       ref_t *prevp = &db->head->array[idx];
174       ref_t run = *prevp;
175
176       while (run != ENDREF)
177         {
178           assert (cnt < db->head->nentries);
179           he[cnt] = (struct hashentry *) (db->data + run);
180
181           he[cnt]->prevp = prevp;
182           prevp = &he[cnt]->next;
183
184           /* This is the hash entry itself.  */
185           markrange (mark, run, sizeof (struct hashentry));
186
187           /* Add the information for the data itself.  We do this
188              only for the one special entry marked with FIRST.  */
189           if (he[cnt]->first)
190             {
191               struct datahead *dh
192                 = (struct datahead *) (db->data + he[cnt]->packet);
193               markrange (mark, he[cnt]->packet, dh->allocsize);
194             }
195
196           run = he[cnt]->next;
197
198           ++cnt;
199         }
200     }
201   assert (cnt == db->head->nentries);
202
203   /* Go through the list of in-flight memory blocks.  */
204   struct mem_in_flight *mrunp = mem_in_flight_list;
205   while (mrunp != NULL)
206     {
207       /* NB: There can be no race between this test and another thread
208         setting the field to the index we are looking for because
209         this would require the other thread to also have the memlock
210         for the database.
211
212         NB2: we do not have to look at latter blocks (higher indices) if
213         earlier blocks are not in flight.  They are always allocated in
214         sequence.  */
215       for (enum in_flight idx = IDX_result_data;
216            idx < IDX_last && mrunp->block[idx].dbidx == db - dbs; ++idx)
217         {
218           assert (mrunp->block[idx].blockoff >= 0);
219           assert (mrunp->block[idx].blocklen < db->memsize);
220           assert (mrunp->block[idx].blockoff
221                   + mrunp->block[0].blocklen <= db->memsize);
222           markrange (mark, mrunp->block[idx].blockoff,
223                      mrunp->block[idx].blocklen);
224         }
225
226       mrunp = mrunp->next;
227     }
228
229   /* Sort the entries by the addresses of the referenced data.  All
230      the entries pointing to the same DATAHEAD object will have the
231      same key.  Stability of the sorting is unimportant.  */
232   memcpy (he_data, he, cnt * sizeof (struct hashentry *));
233   qsort (he_data, cnt, sizeof (struct hashentry *), sort_he_data);
234
235   /* Sort the entries by their address.  */
236   qsort (he, cnt, sizeof (struct hashentry *), sort_he);
237
238 #define obstack_chunk_alloc xmalloc
239 #define obstack_chunk_free free
240   struct obstack ob;
241   obstack_init (&ob);
242
243   /* Determine the highest used address.  */
244   size_t high = nmark;
245   while (high > 0 && mark[high - 1] == 0)
246     --high;
247
248   /* No memory used.  */
249   if (high == 0)
250     {
251       db->head->first_free = 0;
252       goto out;
253     }
254
255   /* Determine the highest offset.  */
256   BITMAP_T mask = HIGHBIT;
257   ref_t highref = (high * BITS - 1) * BLOCK_ALIGN;
258   while ((mark[high - 1] & mask) == 0)
259     {
260       mask >>= 1;
261       highref -= BLOCK_ALIGN;
262     }
263
264   /* Now we can iterate over the MARK array and find bits which are not
265      set.  These represent memory which can be recovered.  */
266   size_t byte = 0;
267   /* Find the first gap.  */
268   while (byte < high && mark[byte] == ALLBITS)
269     ++byte;
270
271   if (byte == high
272       || (byte == high - 1 && (mark[byte] & ~(mask | (mask - 1))) == 0))
273     /* No gap.  */
274     goto out;
275
276   mask = 1;
277   cnt = 0;
278   while ((mark[byte] & mask) != 0)
279     {
280       ++cnt;
281       mask <<= 1;
282     }
283   ref_t off_free = (byte * BITS + cnt) * BLOCK_ALIGN;
284   assert (off_free <= db->head->first_free);
285
286   struct hashentry **next_hash = he;
287   struct hashentry **next_data = he_data;
288
289   /* Skip over the hash entries in the first block which does not get
290      moved.  */
291   while (next_hash < &he[db->head->nentries]
292          && *next_hash < (struct hashentry *) (db->data + off_free))
293     ++next_hash;
294
295   while (next_data < &he_data[db->head->nentries]
296          && (*next_data)->packet < off_free)
297     ++next_data;
298
299
300   /* Now we start modifying the data.  Make sure all readers of the
301      data are aware of this and temporarily don't use the data.  */
302   ++db->head->gc_cycle;
303   assert ((db->head->gc_cycle & 1) == 1);
304
305
306   /* We do not perform the move operations right away since the
307      he_data array is not sorted by the address of the data.  */
308   struct moveinfo
309   {
310     void *from;
311     void *to;
312     size_t size;
313     struct moveinfo *next;
314   } *moves = NULL;
315
316   while (byte < high)
317     {
318       /* Search for the next filled block.  BYTE is the index of the
319          entry in MARK, MASK is the bit, and CNT is the bit number.
320          OFF_FILLED is the corresponding offset.  */
321       if ((mark[byte] & ~(mask - 1)) == 0)
322         {
323           /* No other bit set in the same element of MARK.  Search in the
324              following memory.  */
325           do
326             ++byte;
327           while (byte < high && mark[byte] == 0);
328
329           if (byte == high)
330             /* That was it.  */
331             break;
332
333           mask = 1;
334           cnt = 0;
335         }
336       /* Find the exact bit.  */
337       while ((mark[byte] & mask) == 0)
338         {
339           ++cnt;
340           mask <<= 1;
341         }
342
343       ref_t off_alloc = (byte * BITS + cnt) * BLOCK_ALIGN;
344       assert (off_alloc <= db->head->first_free);
345
346       /* Find the end of the used area.  */
347       if ((mark[byte] & ~(mask - 1)) == (BITMAP_T) ~(mask - 1))
348         {
349           /* All other bits set.  Search the next bytes in MARK.  */
350           do
351             ++byte;
352           while (byte < high && mark[byte] == ALLBITS);
353
354           mask = 1;
355           cnt = 0;
356         }
357       if (byte < high)
358         {
359           /* Find the exact bit.  */
360           while ((mark[byte] & mask) != 0)
361             {
362               ++cnt;
363               mask <<= 1;
364             }
365         }
366
367       ref_t off_allocend = (byte * BITS + cnt) * BLOCK_ALIGN;
368       assert (off_allocend <= db->head->first_free);
369       /* Now we know that we can copy the area from OFF_ALLOC to
370          OFF_ALLOCEND (not included) to the memory starting at
371          OFF_FREE.  First fix up all the entries for the
372          displacement.  */
373       ref_t disp = off_alloc - off_free;
374
375       struct moveinfo *new_move;
376       if (stack_used + sizeof (*new_move) <= MAX_STACK_USE)
377         {
378           new_move = alloca (sizeof (*new_move));
379           stack_used += sizeof (*new_move);
380         }
381       else
382         new_move = obstack_alloc (&ob, sizeof (*new_move));
383       new_move->from = db->data + off_alloc;
384       new_move->to = db->data + off_free;
385       new_move->size = off_allocend - off_alloc;
386       /* Create a circular list to be always able to append at the end.  */
387       if (moves == NULL)
388         moves = new_move->next = new_move;
389       else
390         {
391           new_move->next = moves->next;
392           moves = moves->next = new_move;
393         }
394
395       /* The following loop will prepare to move this much data.  */
396       off_free += off_allocend - off_alloc;
397
398       while (off_alloc < off_allocend)
399         {
400           /* Determine whether the next entry is for a hash entry or
401              the data.  */
402           if ((struct hashentry *) (db->data + off_alloc) == *next_hash)
403             {
404               /* Just correct the forward reference.  */
405               *(*next_hash++)->prevp -= disp;
406
407               off_alloc += ((sizeof (struct hashentry) + BLOCK_ALIGN_M1)
408                             & ~BLOCK_ALIGN_M1);
409             }
410           else
411             {
412               assert (next_data < &he_data[db->head->nentries]);
413               assert ((*next_data)->packet == off_alloc);
414
415               struct datahead *dh = (struct datahead *) (db->data + off_alloc);
416               do
417                 {
418                   assert ((*next_data)->key >= (*next_data)->packet);
419                   assert ((*next_data)->key + (*next_data)->len
420                           <= (*next_data)->packet + dh->allocsize);
421
422                   (*next_data)->packet -= disp;
423                   (*next_data)->key -= disp;
424                   ++next_data;
425                 }
426               while (next_data < &he_data[db->head->nentries]
427                      && (*next_data)->packet == off_alloc);
428
429               off_alloc += (dh->allocsize + BLOCK_ALIGN_M1) & ~BLOCK_ALIGN_M1;
430             }
431         }
432       assert (off_alloc == off_allocend);
433
434       assert (off_alloc <= db->head->first_free);
435       if (off_alloc == db->head->first_free)
436         /* We are done, that was the last block.  */
437         break;
438     }
439   assert (next_hash == &he[db->head->nentries]);
440   assert (next_data == &he_data[db->head->nentries]);
441
442   /* Now perform the actual moves.  */
443   if (moves != NULL)
444     {
445       struct moveinfo *runp = moves->next;
446       do
447         {
448           assert ((char *) runp->to >= db->data);
449           assert ((char *) runp->to + runp->size
450                   <= db->data  + db->head->first_free);
451           assert ((char *) runp->from >= db->data);
452           assert ((char *) runp->from + runp->size
453                   <= db->data  + db->head->first_free);
454
455           /* The regions may overlap.  */
456           memmove (runp->to, runp->from, runp->size);
457           runp = runp->next;
458         }
459       while (runp != moves->next);
460
461       if (__builtin_expect (debug_level >= 3, 0))
462         dbg_log (_("freed %zu bytes in %s cache"),
463                  db->head->first_free
464                  - ((char *) moves->to + moves->size - db->data),
465                  dbnames[db - dbs]);
466
467       /* The byte past the end of the last copied block is the next
468          available byte.  */
469       db->head->first_free = (char *) moves->to + moves->size - db->data;
470
471       /* Consistency check.  */
472       if (__builtin_expect (debug_level >= 3, 0))
473         {
474           for (size_t idx = 0; idx < db->head->module; ++idx)
475             {
476               ref_t run = db->head->array[idx];
477               size_t cnt = 0;
478
479               while (run != ENDREF)
480                 {
481                   if (run + sizeof (struct hashentry) > db->head->first_free)
482                     {
483                       dbg_log ("entry %zu in hash bucket %zu out of bounds: "
484                                "%" PRIu32 "+%zu > %zu\n",
485                                cnt, idx, run, sizeof (struct hashentry),
486                                (size_t) db->head->first_free);
487                       break;
488                     }
489
490                   struct hashentry *he = (struct hashentry *) (db->data + run);
491
492                   if (he->key + he->len > db->head->first_free)
493                     dbg_log ("key of entry %zu in hash bucket %zu out of "
494                              "bounds: %" PRIu32 "+%zu > %zu\n",
495                              cnt, idx, he->key, (size_t) he->len,
496                              (size_t) db->head->first_free);
497
498                   if (he->packet + sizeof (struct datahead)
499                       > db->head->first_free)
500                     dbg_log ("packet of entry %zu in hash bucket %zu out of "
501                              "bounds: %" PRIu32 "+%zu > %zu\n",
502                              cnt, idx, he->packet, sizeof (struct datahead),
503                              (size_t) db->head->first_free);
504                   else
505                     {
506                       struct datahead *dh = (struct datahead *) (db->data
507                                                                  + he->packet);
508                       if (he->packet + dh->allocsize
509                           > db->head->first_free)
510                         dbg_log ("full key of entry %zu in hash bucket %zu "
511                                  "out of bounds: %" PRIu32 "+%zu > %zu",
512                                  cnt, idx, he->packet, (size_t) dh->allocsize,
513                                  (size_t) db->head->first_free);
514                     }
515
516                   run = he->next;
517                   ++cnt;
518                 }
519             }
520         }
521     }
522
523   /* Make sure the data on disk is updated.  */
524   if (db->persistent)
525     msync (db->head, db->data + db->head->first_free - (char *) db->head,
526            MS_ASYNC);
527
528
529   /* Now we are done modifying the data.  */
530   ++db->head->gc_cycle;
531   assert ((db->head->gc_cycle & 1) == 0);
532
533   /* We are done.  */
534  out:
535   pthread_mutex_unlock (&db->memlock);
536   pthread_rwlock_unlock (&db->lock);
537
538   if (he_use_malloc)
539     free (he);
540   if (mark_use_malloc)
541     free (mark);
542
543   obstack_free (&ob, NULL);
544 }
545
546
547 void *
548 mempool_alloc (struct database_dyn *db, size_t len, enum in_flight idx)
549 {
550   /* Make sure LEN is a multiple of our maximum alignment so we can
551      keep track of used memory is multiples of this alignment value.  */
552   if ((len & BLOCK_ALIGN_M1) != 0)
553     len += BLOCK_ALIGN - (len & BLOCK_ALIGN_M1);
554
555   pthread_mutex_lock (&db->memlock);
556
557   assert ((db->head->first_free & BLOCK_ALIGN_M1) == 0);
558
559   bool tried_resize = false;
560   void *res;
561  retry:
562   res = db->data + db->head->first_free;
563
564   if (__builtin_expect (db->head->first_free + len > db->head->data_size, 0))
565     {
566       if (! tried_resize)
567         {
568           /* Try to resize the database.  Grow size of 1/8th.  */
569           size_t oldtotal = (sizeof (struct database_pers_head)
570                              + roundup (db->head->module * sizeof (ref_t),
571                                         ALIGN)
572                              + db->head->data_size);
573           size_t new_data_size = (db->head->data_size
574                                   + MAX (2 * len, db->head->data_size / 8));
575           size_t newtotal = (sizeof (struct database_pers_head)
576                              + roundup (db->head->module * sizeof (ref_t), ALIGN)
577                              + new_data_size);
578           if (newtotal > db->max_db_size)
579             {
580               new_data_size -= newtotal - db->max_db_size;
581               newtotal = db->max_db_size;
582             }
583
584           if (db->mmap_used && newtotal > oldtotal
585               /* We only have to adjust the file size.  The new pages
586                  become magically available.  */
587               && TEMP_FAILURE_RETRY_VAL (posix_fallocate (db->wr_fd, oldtotal,
588                                                           newtotal
589                                                           - oldtotal)) == 0)
590             {
591               db->head->data_size = new_data_size;
592               tried_resize = true;
593               goto retry;
594             }
595         }
596
597       if (! db->last_alloc_failed)
598         {
599           dbg_log (_("no more memory for database '%s'"), dbnames[db - dbs]);
600
601           db->last_alloc_failed = true;
602         }
603
604       /* No luck.  */
605       res = NULL;
606     }
607   else
608     {
609       /* Remember that we have allocated this memory.  */
610       assert (idx >= 0 && idx < IDX_last);
611       mem_in_flight.block[idx].dbidx = db - dbs;
612       mem_in_flight.block[idx].blocklen = len;
613       mem_in_flight.block[idx].blockoff = db->head->first_free;
614
615       db->head->first_free += len;
616
617       db->last_alloc_failed = false;
618
619     }
620
621   pthread_mutex_unlock (&db->memlock);
622
623   return res;
624 }