(cache_add): Add new parameter to mempool_alloc call.
[kopensolaris-gnu/glibc.git] / nscd / cache.c
1 /* Copyright (c) 1998, 1999, 2003-2007, 2008 Free Software Foundation, Inc.
2    This file is part of the GNU C Library.
3    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998.
4
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published
7    by the Free Software Foundation; version 2 of the License, or
8    (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software Foundation,
17    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
18
19 #include <assert.h>
20 #include <atomic.h>
21 #include <errno.h>
22 #include <error.h>
23 #include <inttypes.h>
24 #include <limits.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <libintl.h>
28 #include <arpa/inet.h>
29 #include <rpcsvc/nis.h>
30 #include <sys/mman.h>
31 #include <sys/param.h>
32 #include <sys/stat.h>
33 #include <sys/uio.h>
34
35 #include "nscd.h"
36 #include "dbg_log.h"
37
38
39 /* Wrapper functions with error checking for standard functions.  */
40 extern void *xcalloc (size_t n, size_t s);
41
42
43 /* Number of times a value is reloaded without being used.  UINT_MAX
44    means unlimited.  */
45 unsigned int reload_count = DEFAULT_RELOAD_LIMIT;
46
47
48 static void (*const readdfcts[LASTREQ]) (struct database_dyn *,
49                                          struct hashentry *,
50                                          struct datahead *) =
51 {
52   [GETPWBYNAME] = readdpwbyname,
53   [GETPWBYUID] = readdpwbyuid,
54   [GETGRBYNAME] = readdgrbyname,
55   [GETGRBYGID] = readdgrbygid,
56   [GETHOSTBYNAME] = readdhstbyname,
57   [GETHOSTBYNAMEv6] = readdhstbynamev6,
58   [GETHOSTBYADDR] = readdhstbyaddr,
59   [GETHOSTBYADDRv6] = readdhstbyaddrv6,
60   [GETAI] = readdhstai,
61   [INITGROUPS] = readdinitgroups,
62   [GETSERVBYNAME] = readdservbyname,
63   [GETSERVBYPORT] = readdservbyport
64 };
65
66
67 /* Search the cache for a matching entry and return it when found.  If
68    this fails search the negative cache and return (void *) -1 if this
69    search was successful.  Otherwise return NULL.
70
71    This function must be called with the read-lock held.  */
72 struct datahead *
73 cache_search (request_type type, void *key, size_t len,
74               struct database_dyn *table, uid_t owner)
75 {
76   unsigned long int hash = __nis_hash (key, len) % table->head->module;
77
78   unsigned long int nsearched = 0;
79   struct datahead *result = NULL;
80
81   ref_t work = table->head->array[hash];
82   while (work != ENDREF)
83     {
84       ++nsearched;
85
86       struct hashentry *here = (struct hashentry *) (table->data + work);
87
88       if (type == here->type && len == here->len
89           && memcmp (key, table->data + here->key, len) == 0
90           && here->owner == owner)
91         {
92           /* We found the entry.  Increment the appropriate counter.  */
93           struct datahead *dh
94             = (struct datahead *) (table->data + here->packet);
95
96           /* See whether we must ignore the entry.  */
97           if (dh->usable)
98             {
99               /* We do not synchronize the memory here.  The statistics
100                  data is not crucial, we synchronize only once in a while
101                  in the cleanup threads.  */
102               if (dh->notfound)
103                 ++table->head->neghit;
104               else
105                 {
106                   ++table->head->poshit;
107
108                   if (dh->nreloads != 0)
109                     dh->nreloads = 0;
110                 }
111
112               result = dh;
113               break;
114             }
115         }
116
117       work = here->next;
118     }
119
120   if (nsearched > table->head->maxnsearched)
121     table->head->maxnsearched = nsearched;
122
123   return result;
124 }
125
126 /* Add a new entry to the cache.  The return value is zero if the function
127    call was successful.
128
129    This function must be called with the read-lock held.
130
131    We modify the table but we nevertheless only acquire a read-lock.
132    This is ok since we use operations which would be safe even without
133    locking, given that the `prune_cache' function never runs.  Using
134    the readlock reduces the chance of conflicts.  */
135 int
136 cache_add (int type, const void *key, size_t len, struct datahead *packet,
137            bool first, struct database_dyn *table,
138            uid_t owner)
139 {
140   if (__builtin_expect (debug_level >= 2, 0))
141     {
142       const char *str;
143       char buf[INET6_ADDRSTRLEN + 1];
144       if (type == GETHOSTBYADDR || type == GETHOSTBYADDRv6)
145         str = inet_ntop (type == GETHOSTBYADDR ? AF_INET : AF_INET6,
146                          key, buf, sizeof (buf));
147       else
148         str = key;
149
150       dbg_log (_("add new entry \"%s\" of type %s for %s to cache%s"),
151                str, serv2str[type], dbnames[table - dbs],
152                first ? _(" (first)") : "");
153     }
154
155   unsigned long int hash = __nis_hash (key, len) % table->head->module;
156   struct hashentry *newp;
157
158   newp = mempool_alloc (table, sizeof (struct hashentry), IDX_record_data);
159   /* If we cannot allocate memory, just do not do anything.  */
160   if (newp == NULL)
161     {
162       ++table->head->addfailed;
163
164       /* Mark the in-flight memory as unused.  */
165       for (enum in_flight idx = 0; idx < IDX_record_data; ++idx)
166         mem_in_flight.block[idx].dbidx = -1;
167
168       return -1;
169     }
170
171   newp->type = type;
172   newp->first = first;
173   newp->len = len;
174   newp->key = (char *) key - table->data;
175   assert (newp->key + newp->len <= table->head->first_free);
176   newp->owner = owner;
177   newp->packet = (char *) packet - table->data;
178
179   /* Put the new entry in the first position.  */
180   do
181     newp->next = table->head->array[hash];
182   while (atomic_compare_and_exchange_bool_acq (&table->head->array[hash],
183                                                (ref_t) ((char *) newp
184                                                         - table->data),
185                                                (ref_t) newp->next));
186
187   /* Update the statistics.  */
188   if (packet->notfound)
189     ++table->head->negmiss;
190   else if (first)
191     ++table->head->posmiss;
192
193   /* We depend on this value being correct and at least as high as the
194      real number of entries.  */
195   atomic_increment (&table->head->nentries);
196
197   /* It does not matter that we are not loading the just increment
198      value, this is just for statistics.  */
199   unsigned long int nentries = table->head->nentries;
200   if (nentries > table->head->maxnentries)
201     table->head->maxnentries = nentries;
202
203   if (table->persistent)
204     // XXX async OK?
205     msync ((void *) table->head,
206            (char *) &table->head->array[hash] - (char *) table->head
207            + sizeof (ref_t), MS_ASYNC);
208
209   /* Perhaps the prune thread for the data is not running in a long
210      time.  Wake it if necessary.  */
211   time_t next_wakeup = table->wakeup_time;
212   while (next_wakeup + CACHE_PRUNE_INTERVAL > packet->timeout)
213     if (atomic_compare_and_exchange_bool_acq (&table->wakeup_time,
214                                               packet->timeout,
215                                               next_wakeup) == 0)
216       {
217         pthread_cond_signal (&table->prune_cond);
218         break;
219       }
220     else
221       next_wakeup = table->wakeup_time;
222
223   /* Mark the in-flight memory as unused.  */
224   for (enum in_flight idx = 0; idx < IDX_last; ++idx)
225     mem_in_flight.block[idx].dbidx = -1;
226
227   return 0;
228 }
229
230 /* Walk through the table and remove all entries which lifetime ended.
231
232    We have a problem here.  To actually remove the entries we must get
233    the write-lock.  But since we want to keep the time we have the
234    lock as short as possible we cannot simply acquire the lock when we
235    start looking for timedout entries.
236
237    Therefore we do it in two stages: first we look for entries which
238    must be invalidated and remember them.  Then we get the lock and
239    actually remove them.  This is complicated by the way we have to
240    free the data structures since some hash table entries share the same
241    data.  */
242 time_t
243 prune_cache (struct database_dyn *table, time_t now, int fd)
244 {
245   size_t cnt = table->head->module;
246
247   /* If this table is not actually used don't do anything.  */
248   if (cnt == 0)
249     {
250       if (fd != -1)
251         {
252           /* Reply to the INVALIDATE initiator.  */
253           int32_t resp = 0;
254           writeall (fd, &resp, sizeof (resp));
255         }
256
257       /* No need to do this again anytime soon.  */
258       return 24 * 60 * 60;
259     }
260
261   /* If we check for the modification of the underlying file we invalidate
262      the entries also in this case.  */
263   if (table->check_file && now != LONG_MAX)
264     {
265       struct stat64 st;
266
267       if (stat64 (table->filename, &st) < 0)
268         {
269           char buf[128];
270           /* We cannot stat() the file, disable file checking if the
271              file does not exist.  */
272           dbg_log (_("cannot stat() file `%s': %s"),
273                    table->filename, strerror_r (errno, buf, sizeof (buf)));
274           if (errno == ENOENT)
275             table->check_file = 0;
276         }
277       else
278         {
279           if (st.st_mtime != table->file_mtime)
280             {
281               /* The file changed.  Invalidate all entries.  */
282               now = LONG_MAX;
283               table->file_mtime = st.st_mtime;
284             }
285         }
286     }
287
288   /* We run through the table and find values which are not valid anymore.
289
290      Note that for the initial step, finding the entries to be removed,
291      we don't need to get any lock.  It is at all timed assured that the
292      linked lists are set up correctly and that no second thread prunes
293      the cache.  */
294   bool *mark;
295   size_t memory_needed = cnt * sizeof (bool);
296   bool mark_use_alloca;
297   if (__builtin_expect (memory_needed <= MAX_STACK_USE, 1))
298     {
299       mark = alloca (cnt * sizeof (bool));
300       memset (mark, '\0', memory_needed);
301       mark_use_alloca = true;
302     }
303   else
304     {
305       mark = xcalloc (1, memory_needed);
306       mark_use_alloca = false;
307     }
308   size_t first = cnt + 1;
309   size_t last = 0;
310   char *const data = table->data;
311   bool any = false;
312
313   if (__builtin_expect (debug_level > 2, 0))
314     dbg_log (_("pruning %s cache; time %ld"),
315              dbnames[table - dbs], (long int) now);
316
317 #define NO_TIMEOUT LONG_MAX
318   time_t next_timeout = NO_TIMEOUT;
319   do
320     {
321       ref_t run = table->head->array[--cnt];
322
323       while (run != ENDREF)
324         {
325           struct hashentry *runp = (struct hashentry *) (data + run);
326           struct datahead *dh = (struct datahead *) (data + runp->packet);
327
328           /* Some debug support.  */
329           if (__builtin_expect (debug_level > 2, 0))
330             {
331               char buf[INET6_ADDRSTRLEN];
332               const char *str;
333
334               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
335                 {
336                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
337                              data + runp->key, buf, sizeof (buf));
338                   str = buf;
339                 }
340               else
341                 str = data + runp->key;
342
343               dbg_log (_("considering %s entry \"%s\", timeout %" PRIu64),
344                        serv2str[runp->type], str, dh->timeout);
345             }
346
347           /* Check whether the entry timed out.  */
348           if (dh->timeout < now)
349             {
350               /* This hash bucket could contain entries which need to
351                  be looked at.  */
352               mark[cnt] = true;
353
354               first = MIN (first, cnt);
355               last = MAX (last, cnt);
356
357               /* We only have to look at the data of the first entries
358                  since the count information is kept in the data part
359                  which is shared.  */
360               if (runp->first)
361                 {
362
363                   /* At this point there are two choices: we reload the
364                      value or we discard it.  Do not change NRELOADS if
365                      we never not reload the record.  */
366                   if ((reload_count != UINT_MAX
367                        && __builtin_expect (dh->nreloads >= reload_count, 0))
368                       /* We always remove negative entries.  */
369                       || dh->notfound
370                       /* Discard everything if the user explicitly
371                          requests it.  */
372                       || now == LONG_MAX)
373                     {
374                       /* Remove the value.  */
375                       dh->usable = false;
376
377                       /* We definitely have some garbage entries now.  */
378                       any = true;
379                     }
380                   else
381                     {
382                       /* Reload the value.  We do this only for the
383                          initially used key, not the additionally
384                          added derived value.  */
385                       assert (runp->type < LASTREQ
386                               && readdfcts[runp->type] != NULL);
387
388                       readdfcts[runp->type] (table, runp, dh);
389
390                       /* If the entry has been replaced, we might need
391                          cleanup.  */
392                       any |= !dh->usable;
393                     }
394                 }
395             }
396           else
397             {
398               assert (dh->usable);
399               next_timeout = MIN (next_timeout, dh->timeout);
400             }
401
402           run = runp->next;
403         }
404     }
405   while (cnt > 0);
406
407   if (__builtin_expect (fd != -1, 0))
408     {
409       /* Reply to the INVALIDATE initiator that the cache has been
410          invalidated.  */
411       int32_t resp = 0;
412       writeall (fd, &resp, sizeof (resp));
413     }
414
415   if (first <= last)
416     {
417       struct hashentry *head = NULL;
418
419       /* Now we have to get the write lock since we are about to modify
420          the table.  */
421       if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
422         {
423           ++table->head->wrlockdelayed;
424           pthread_rwlock_wrlock (&table->lock);
425         }
426
427       while (first <= last)
428         {
429           if (mark[first])
430             {
431               ref_t *old = &table->head->array[first];
432               ref_t run = table->head->array[first];
433
434               while (run != ENDREF)
435                 {
436                   struct hashentry *runp = (struct hashentry *) (data + run);
437                   struct datahead *dh
438                     = (struct datahead *) (data + runp->packet);
439
440                   if (! dh->usable)
441                     {
442                       /* We need the list only for debugging but it is
443                          more costly to avoid creating the list than
444                          doing it.  */
445                       runp->dellist = head;
446                       head = runp;
447
448                       /* No need for an atomic operation, we have the
449                          write lock.  */
450                       --table->head->nentries;
451
452                       run = *old = runp->next;
453                     }
454                   else
455                     {
456                       old = &runp->next;
457                       run = runp->next;
458                     }
459                 }
460             }
461
462           ++first;
463         }
464
465       /* It's all done.  */
466       pthread_rwlock_unlock (&table->lock);
467
468       /* Make sure the data is saved to disk.  */
469       if (table->persistent)
470         msync (table->head,
471                data + table->head->first_free - (char *) table->head,
472                MS_ASYNC);
473
474       /* One extra pass if we do debugging.  */
475       if (__builtin_expect (debug_level > 0, 0))
476         {
477           struct hashentry *runp = head;
478
479           while (runp != NULL)
480             {
481               char buf[INET6_ADDRSTRLEN];
482               const char *str;
483
484               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
485                 {
486                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
487                              data + runp->key, buf, sizeof (buf));
488                   str = buf;
489                 }
490               else
491                 str = data + runp->key;
492
493               dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
494
495               runp = runp->dellist;
496             }
497         }
498     }
499
500   if (__builtin_expect (! mark_use_alloca, 0))
501     free (mark);
502
503   /* Run garbage collection if any entry has been removed or replaced.  */
504   if (any)
505     gc (table);
506
507   /* If there is no entry in the database and we therefore have no new
508      timeout value, tell the caller to wake up in 24 hours.  */
509   return next_timeout == NO_TIMEOUT ? 24 * 60 * 60 : next_timeout - now;
510 }