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