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