f4a9de530aeb8020faed643f9dd25fc72e8bc3e1
[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       /* If necessary mark the entry as unusable so that lookups will
165          not use it.  */
166       if (first)
167         packet->usable = false;
168
169       /* Mark the in-flight memory as unused.  */
170       for (enum in_flight idx = 0; idx < IDX_record_data; ++idx)
171         mem_in_flight.block[idx].dbidx = -1;
172
173       return -1;
174     }
175
176   newp->type = type;
177   newp->first = first;
178   newp->len = len;
179   newp->key = (char *) key - table->data;
180   assert (newp->key + newp->len <= table->head->first_free);
181   newp->owner = owner;
182   newp->packet = (char *) packet - table->data;
183
184   /* Put the new entry in the first position.  */
185   do
186     newp->next = table->head->array[hash];
187   while (atomic_compare_and_exchange_bool_acq (&table->head->array[hash],
188                                                (ref_t) ((char *) newp
189                                                         - table->data),
190                                                (ref_t) newp->next));
191
192   /* Update the statistics.  */
193   if (packet->notfound)
194     ++table->head->negmiss;
195   else if (first)
196     ++table->head->posmiss;
197
198   /* We depend on this value being correct and at least as high as the
199      real number of entries.  */
200   atomic_increment (&table->head->nentries);
201
202   /* It does not matter that we are not loading the just increment
203      value, this is just for statistics.  */
204   unsigned long int nentries = table->head->nentries;
205   if (nentries > table->head->maxnentries)
206     table->head->maxnentries = nentries;
207
208   if (table->persistent)
209     // XXX async OK?
210     msync ((void *) table->head,
211            (char *) &table->head->array[hash] - (char *) table->head
212            + sizeof (ref_t), MS_ASYNC);
213
214   /* Perhaps the prune thread for the data is not running in a long
215      time.  Wake it if necessary.  */
216   time_t next_wakeup = table->wakeup_time;
217   while (next_wakeup + CACHE_PRUNE_INTERVAL > packet->timeout)
218     if (atomic_compare_and_exchange_bool_acq (&table->wakeup_time,
219                                               packet->timeout,
220                                               next_wakeup) == 0)
221       {
222         pthread_cond_signal (&table->prune_cond);
223         break;
224       }
225     else
226       next_wakeup = table->wakeup_time;
227
228   /* Mark the in-flight memory as unused.  */
229   for (enum in_flight idx = 0; idx < IDX_last; ++idx)
230     mem_in_flight.block[idx].dbidx = -1;
231
232   return 0;
233 }
234
235 /* Walk through the table and remove all entries which lifetime ended.
236
237    We have a problem here.  To actually remove the entries we must get
238    the write-lock.  But since we want to keep the time we have the
239    lock as short as possible we cannot simply acquire the lock when we
240    start looking for timedout entries.
241
242    Therefore we do it in two stages: first we look for entries which
243    must be invalidated and remember them.  Then we get the lock and
244    actually remove them.  This is complicated by the way we have to
245    free the data structures since some hash table entries share the same
246    data.  */
247 time_t
248 prune_cache (struct database_dyn *table, time_t now, int fd)
249 {
250   size_t cnt = table->head->module;
251
252   /* If this table is not actually used don't do anything.  */
253   if (cnt == 0)
254     {
255       if (fd != -1)
256         {
257           /* Reply to the INVALIDATE initiator.  */
258           int32_t resp = 0;
259           writeall (fd, &resp, sizeof (resp));
260         }
261
262       /* No need to do this again anytime soon.  */
263       return 24 * 60 * 60;
264     }
265
266   /* If we check for the modification of the underlying file we invalidate
267      the entries also in this case.  */
268   if (table->check_file && now != LONG_MAX)
269     {
270       struct stat64 st;
271
272       if (stat64 (table->filename, &st) < 0)
273         {
274           char buf[128];
275           /* We cannot stat() the file, disable file checking if the
276              file does not exist.  */
277           dbg_log (_("cannot stat() file `%s': %s"),
278                    table->filename, strerror_r (errno, buf, sizeof (buf)));
279           if (errno == ENOENT)
280             table->check_file = 0;
281         }
282       else
283         {
284           if (st.st_mtime != table->file_mtime)
285             {
286               /* The file changed.  Invalidate all entries.  */
287               now = LONG_MAX;
288               table->file_mtime = st.st_mtime;
289             }
290         }
291     }
292
293   /* We run through the table and find values which are not valid anymore.
294
295      Note that for the initial step, finding the entries to be removed,
296      we don't need to get any lock.  It is at all timed assured that the
297      linked lists are set up correctly and that no second thread prunes
298      the cache.  */
299   bool *mark;
300   size_t memory_needed = cnt * sizeof (bool);
301   bool mark_use_alloca;
302   if (__builtin_expect (memory_needed <= MAX_STACK_USE, 1))
303     {
304       mark = alloca (cnt * sizeof (bool));
305       memset (mark, '\0', memory_needed);
306       mark_use_alloca = true;
307     }
308   else
309     {
310       mark = xcalloc (1, memory_needed);
311       mark_use_alloca = false;
312     }
313   size_t first = cnt + 1;
314   size_t last = 0;
315   char *const data = table->data;
316   bool any = false;
317
318   if (__builtin_expect (debug_level > 2, 0))
319     dbg_log (_("pruning %s cache; time %ld"),
320              dbnames[table - dbs], (long int) now);
321
322 #define NO_TIMEOUT LONG_MAX
323   time_t next_timeout = NO_TIMEOUT;
324   do
325     {
326       ref_t run = table->head->array[--cnt];
327
328       while (run != ENDREF)
329         {
330           struct hashentry *runp = (struct hashentry *) (data + run);
331           struct datahead *dh = (struct datahead *) (data + runp->packet);
332
333           /* Some debug support.  */
334           if (__builtin_expect (debug_level > 2, 0))
335             {
336               char buf[INET6_ADDRSTRLEN];
337               const char *str;
338
339               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
340                 {
341                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
342                              data + runp->key, buf, sizeof (buf));
343                   str = buf;
344                 }
345               else
346                 str = data + runp->key;
347
348               dbg_log (_("considering %s entry \"%s\", timeout %" PRIu64),
349                        serv2str[runp->type], str, dh->timeout);
350             }
351
352           /* Check whether the entry timed out.  */
353           if (dh->timeout < now)
354             {
355               /* This hash bucket could contain entries which need to
356                  be looked at.  */
357               mark[cnt] = true;
358
359               first = MIN (first, cnt);
360               last = MAX (last, cnt);
361
362               /* We only have to look at the data of the first entries
363                  since the count information is kept in the data part
364                  which is shared.  */
365               if (runp->first)
366                 {
367
368                   /* At this point there are two choices: we reload the
369                      value or we discard it.  Do not change NRELOADS if
370                      we never not reload the record.  */
371                   if ((reload_count != UINT_MAX
372                        && __builtin_expect (dh->nreloads >= reload_count, 0))
373                       /* We always remove negative entries.  */
374                       || dh->notfound
375                       /* Discard everything if the user explicitly
376                          requests it.  */
377                       || now == LONG_MAX)
378                     {
379                       /* Remove the value.  */
380                       dh->usable = false;
381
382                       /* We definitely have some garbage entries now.  */
383                       any = true;
384                     }
385                   else
386                     {
387                       /* Reload the value.  We do this only for the
388                          initially used key, not the additionally
389                          added derived value.  */
390                       assert (runp->type < LASTREQ
391                               && readdfcts[runp->type] != NULL);
392
393                       readdfcts[runp->type] (table, runp, dh);
394
395                       /* If the entry has been replaced, we might need
396                          cleanup.  */
397                       any |= !dh->usable;
398                     }
399                 }
400             }
401           else
402             {
403               assert (dh->usable);
404               next_timeout = MIN (next_timeout, dh->timeout);
405             }
406
407           run = runp->next;
408         }
409     }
410   while (cnt > 0);
411
412   if (__builtin_expect (fd != -1, 0))
413     {
414       /* Reply to the INVALIDATE initiator that the cache has been
415          invalidated.  */
416       int32_t resp = 0;
417       writeall (fd, &resp, sizeof (resp));
418     }
419
420   if (first <= last)
421     {
422       struct hashentry *head = NULL;
423
424       /* Now we have to get the write lock since we are about to modify
425          the table.  */
426       if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
427         {
428           ++table->head->wrlockdelayed;
429           pthread_rwlock_wrlock (&table->lock);
430         }
431
432       while (first <= last)
433         {
434           if (mark[first])
435             {
436               ref_t *old = &table->head->array[first];
437               ref_t run = table->head->array[first];
438
439               while (run != ENDREF)
440                 {
441                   struct hashentry *runp = (struct hashentry *) (data + run);
442                   struct datahead *dh
443                     = (struct datahead *) (data + runp->packet);
444
445                   if (! dh->usable)
446                     {
447                       /* We need the list only for debugging but it is
448                          more costly to avoid creating the list than
449                          doing it.  */
450                       runp->dellist = head;
451                       head = runp;
452
453                       /* No need for an atomic operation, we have the
454                          write lock.  */
455                       --table->head->nentries;
456
457                       run = *old = runp->next;
458                     }
459                   else
460                     {
461                       old = &runp->next;
462                       run = runp->next;
463                     }
464                 }
465             }
466
467           ++first;
468         }
469
470       /* It's all done.  */
471       pthread_rwlock_unlock (&table->lock);
472
473       /* Make sure the data is saved to disk.  */
474       if (table->persistent)
475         msync (table->head,
476                data + table->head->first_free - (char *) table->head,
477                MS_ASYNC);
478
479       /* One extra pass if we do debugging.  */
480       if (__builtin_expect (debug_level > 0, 0))
481         {
482           struct hashentry *runp = head;
483
484           while (runp != NULL)
485             {
486               char buf[INET6_ADDRSTRLEN];
487               const char *str;
488
489               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
490                 {
491                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
492                              data + runp->key, buf, sizeof (buf));
493                   str = buf;
494                 }
495               else
496                 str = data + runp->key;
497
498               dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
499
500               runp = runp->dellist;
501             }
502         }
503     }
504
505   if (__builtin_expect (! mark_use_alloca, 0))
506     free (mark);
507
508   /* Run garbage collection if any entry has been removed or replaced.  */
509   if (any)
510     gc (table);
511
512   /* If there is no entry in the database and we therefore have no new
513      timeout value, tell the caller to wake up in 24 hours.  */
514   return next_timeout == NO_TIMEOUT ? 24 * 60 * 60 : next_timeout - now;
515 }