(CFLAGS-nscd_setup_thread.c): Set to -fpie.
[kopensolaris-gnu/glibc.git] / 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   /* Now we start modifying the data.  Make sure all readers of the
234      data are aware of this and temporarily don't use the data.  */
235   ++db->head->gc_cycle;
236   assert ((db->head->gc_cycle & 1) == 1);
237
238
239   /* We do not perform the move operations right away since the
240      he_data array is not sorted by the address of the data.  */
241   struct moveinfo
242   {
243     void *from;
244     void *to;
245     size_t size;
246     struct moveinfo *next;
247   } *moves = NULL;
248
249   while (byte < high)
250     {
251       /* Search for the next filled block.  BYTE is the index of the
252          entry in MARK, MASK is the bit, and CNT is the bit number.
253          OFF_FILLED is the corresponding offset.  */
254       if ((mark[byte] & ~(mask - 1)) == 0)
255         {
256           /* No other bit set in the same element of MARK.  Search in the
257              following memory.  */
258           do
259             ++byte;
260           while (byte < high && mark[byte] == 0);
261
262           if (byte == high)
263             /* That was it.  */
264             break;
265
266           mask = 1;
267           cnt = 0;
268         }
269       /* Find the exact bit.  */
270       while ((mark[byte] & mask) == 0)
271         {
272           ++cnt;
273           mask <<= 1;
274         }
275
276       ref_t off_alloc = (byte * BITS + cnt) * BLOCK_ALIGN;
277       assert (off_alloc <= db->head->first_free);
278
279       /* Find the end of the used area.  */
280       if ((mark[byte] & ~(mask - 1)) == (BITMAP_T) ~(mask - 1))
281         {
282           /* All other bits set.  Search the next bytes in MARK.  */
283           do
284             ++byte;
285           while (byte < high && mark[byte] == ALLBITS);
286
287           mask = 1;
288           cnt = 0;
289         }
290       if (byte < high)
291         {
292           /* Find the exact bit.  */
293           while ((mark[byte] & mask) != 0)
294             {
295               ++cnt;
296               mask <<= 1;
297             }
298         }
299
300       ref_t off_allocend = (byte * BITS + cnt) * BLOCK_ALIGN;
301       assert (off_allocend <= db->head->first_free);
302       /* Now we know that we can copy the area from OFF_ALLOC to
303          OFF_ALLOCEND (not included) to the memory starting at
304          OFF_FREE.  First fix up all the entries for the
305          displacement.  */
306       ref_t disp = off_alloc - off_free;
307
308       struct moveinfo *new_move
309         = (struct moveinfo *) alloca (sizeof (*new_move));
310       new_move->from = db->data + off_alloc;
311       new_move->to = db->data + off_free;
312       new_move->size = off_allocend - off_alloc;
313       /* Create a circular list to be always able to append at the end.  */
314       if (moves == NULL)
315         moves = new_move->next = new_move;
316       else
317         {
318           new_move->next = moves->next;
319           moves = moves->next = new_move;
320         }
321
322       /* The following loop will prepare to move this much data.  */
323       off_free += off_allocend - off_alloc;
324
325       while (off_alloc < off_allocend)
326         {
327           /* Determine whether the next entry is for a hash entry or
328              the data.  */
329           if ((struct hashentry *) (db->data + off_alloc) == *next_hash)
330             {
331               /* Just correct the forward reference.  */
332               *(*next_hash++)->prevp -= disp;
333
334               off_alloc += ((sizeof (struct hashentry) + BLOCK_ALIGN_M1)
335                             & ~BLOCK_ALIGN_M1);
336             }
337           else
338             {
339               assert (next_data < &he_data[db->head->nentries]);
340               assert ((*next_data)->packet == off_alloc);
341
342               struct datahead *dh = (struct datahead *) (db->data + off_alloc);
343               do
344                 {
345                   assert ((*next_data)->key >= (*next_data)->packet);
346                   assert ((*next_data)->key + (*next_data)->len
347                           <= (*next_data)->packet + dh->allocsize);
348
349                   (*next_data)->packet -= disp;
350                   (*next_data)->key -= disp;
351                   ++next_data;
352                 }
353               while (next_data < &he_data[db->head->nentries]
354                      && (*next_data)->packet == off_alloc);
355
356               off_alloc += (dh->allocsize + BLOCK_ALIGN_M1) & ~BLOCK_ALIGN_M1;
357             }
358         }
359       assert (off_alloc == off_allocend);
360
361       assert (off_alloc <= db->head->first_free);
362       if (off_alloc == db->head->first_free)
363         /* We are done, that was the last block.  */
364         break;
365     }
366   assert (next_hash == &he[db->head->nentries]);
367   assert (next_data == &he_data[db->head->nentries]);
368
369   /* Now perform the actual moves.  */
370   if (moves != NULL)
371     {
372       struct moveinfo *runp = moves->next;
373       do
374         {
375           assert ((char *) runp->to >= db->data);
376           assert ((char *) runp->to + runp->size
377                   <= db->data  + db->head->first_free);
378           assert ((char *) runp->from >= db->data);
379           assert ((char *) runp->from + runp->size
380                   <= db->data  + db->head->first_free);
381
382           /* The regions may overlap.  */
383           memmove (runp->to, runp->from, runp->size);
384           runp = runp->next;
385         }
386       while (runp != moves->next);
387
388       if (__builtin_expect (debug_level >= 3, 0))
389         dbg_log (_("freed %zu bytes in %s cache"),
390                  db->head->first_free
391                  - ((char *) moves->to + moves->size - db->data),
392                  dbnames[db - dbs]);
393
394       /* The byte past the end of the last copied block is the next
395          available byte.  */
396       db->head->first_free = (char *) moves->to + moves->size - db->data;
397
398       /* Consistency check.  */
399       if (__builtin_expect (debug_level >= 3, 0))
400         {
401           for (size_t idx = 0; idx < db->head->module; ++idx)
402             {
403               ref_t run = db->head->array[idx];
404               size_t cnt = 0;
405
406               while (run != ENDREF)
407                 {
408                   if (run + sizeof (struct hashentry) > db->head->first_free)
409                     {
410                       dbg_log ("entry %zu in hash bucket %zu out of bounds: "
411                                "%" PRIu32 "+%zu > %zu\n",
412                                cnt, idx, run, sizeof (struct hashentry),
413                                db->head->first_free);
414                       break;
415                     }
416
417                   struct hashentry *he = (struct hashentry *) (db->data + run);
418
419                   if (he->key + he->len > db->head->first_free)
420                     dbg_log ("key of entry %zu in hash bucket %zu out of "
421                              "bounds: %" PRIu32 "+%zu > %zu\n",
422                              cnt, idx, he->key, he->len, db->head->first_free);
423
424                   if (he->packet + sizeof (struct datahead)
425                       > db->head->first_free)
426                     dbg_log ("packet of entry %zu in hash bucket %zu out of "
427                              "bounds: %" PRIu32 "+%zu > %zu\n",
428                              cnt, idx, he->packet, sizeof (struct datahead),
429                              db->head->first_free);
430                   else
431                     {
432                       struct datahead *dh = (struct datahead *) (db->data
433                                                                  + he->packet);
434                       if (he->packet + dh->allocsize
435                           > db->head->first_free)
436                         dbg_log ("full key of entry %zu in hash bucket %zu "
437                                  "out of bounds: %" PRIu32 "+%zu > %zu",
438                                  cnt, idx, he->packet, dh->allocsize,
439                                  db->head->first_free);
440                     }
441
442                   run = he->next;
443                   ++cnt;
444                 }
445             }
446         }
447     }
448
449   /* Make sure the data on disk is updated.  */
450   if (db->persistent)
451     msync (db->head, db->data + db->head->first_free - (char *) db->head,
452            MS_ASYNC);
453
454
455   /* Now we are done modifying the data.  */
456   ++db->head->gc_cycle;
457   assert ((db->head->gc_cycle & 1) == 0);
458
459   /* We are done.  */
460  out:
461   pthread_mutex_unlock (&db->memlock);
462   pthread_rwlock_unlock (&db->lock);
463 }
464
465
466 void *
467 mempool_alloc (struct database_dyn *db, size_t len)
468 {
469   /* Make sure LEN is a multiple of our maximum alignment so we can
470      keep track of used memory is multiples of this alignment value.  */
471   if ((len & BLOCK_ALIGN_M1) != 0)
472     len += BLOCK_ALIGN - (len & BLOCK_ALIGN_M1);
473
474   pthread_mutex_lock (&db->memlock);
475
476   assert ((db->head->first_free & BLOCK_ALIGN_M1) == 0);
477
478   bool tried_resize = false;
479   void *res;
480  retry:
481   res = db->data + db->head->first_free;
482
483   if (__builtin_expect (db->head->first_free + len > db->head->data_size, 0))
484     {
485       if (! tried_resize)
486         {
487           /* Try to resize the database.  Grow size of 1/8th.  */
488           size_t new_data_size = db->head->data_size + db->head->data_size / 8;
489           size_t oldtotal = (sizeof (struct database_pers_head)
490                              + db->head->module * sizeof (ref_t)
491                              + db->head->data_size);
492           size_t newtotal = (sizeof (struct database_pers_head)
493                              + db->head->module * sizeof (ref_t)
494                              + new_data_size);
495
496           if ((!db->mmap_used || ftruncate (db->wr_fd, newtotal) != 0)
497               /* Try to resize the mapping.  Note: no MREMAP_MAYMOVE.  */
498               && mremap (db->head, oldtotal, newtotal, 0) == 0)
499             {
500               db->head->data_size = new_data_size;
501               tried_resize = true;
502               goto retry;
503             }
504         }
505
506       if (! db->last_alloc_failed)
507         {
508           dbg_log (_("no more memory for database '%s'"), dbnames[db - dbs]);
509
510           db->last_alloc_failed = true;
511         }
512
513       /* No luck.  */
514       res = NULL;
515     }
516   else
517     {
518       db->head->first_free += len;
519
520       db->last_alloc_failed = false;
521     }
522
523   pthread_mutex_unlock (&db->memlock);
524
525   return res;
526 }