Use GPL, not LGPL.
[kopensolaris-gnu/glibc.git] / nscd / cache.c
1 /* Copyright (c) 1998, 1999, 2003, 2004, 2005 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   /* If we check for the modification of the underlying file we invalidate
202      the entries also in this case.  */
203   if (table->check_file)
204     {
205       struct stat64 st;
206
207       if (stat64 (table->filename, &st) < 0)
208         {
209           char buf[128];
210           /* We cannot stat() the file, disable file checking if the
211              file does not exist.  */
212           dbg_log (_("cannot stat() file `%s': %s"),
213                    table->filename, strerror_r (errno, buf, sizeof (buf)));
214           if (errno == ENOENT)
215             table->check_file = 0;
216         }
217       else
218         {
219           if (st.st_mtime != table->file_mtime)
220             {
221               /* The file changed.  Invalidate all entries.  */
222               now = LONG_MAX;
223               table->file_mtime = st.st_mtime;
224             }
225         }
226     }
227
228   /* We run through the table and find values which are not valid anymore.
229
230      Note that for the initial step, finding the entries to be removed,
231      we don't need to get any lock.  It is at all timed assured that the
232      linked lists are set up correctly and that no second thread prunes
233      the cache.  */
234   bool mark[cnt];
235   size_t first = cnt + 1;
236   size_t last = 0;
237   char *const data = table->data;
238   bool any = false;
239
240   if (__builtin_expect (debug_level > 2, 0))
241     dbg_log (_("pruning %s cache; time %ld"),
242              dbnames[table - dbs], (long int) now);
243
244   do
245     {
246       ref_t run = table->head->array[--cnt];
247
248       while (run != ENDREF)
249         {
250           struct hashentry *runp = (struct hashentry *) (data + run);
251           struct datahead *dh = (struct datahead *) (data + runp->packet);
252
253           /* Some debug support.  */
254           if (__builtin_expect (debug_level > 2, 0))
255             {
256               char buf[INET6_ADDRSTRLEN];
257               const char *str;
258
259               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
260                 {
261                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
262                              data + runp->key, buf, sizeof (buf));
263                   str = buf;
264                 }
265               else
266                 str = data + runp->key;
267
268               dbg_log (_("considering %s entry \"%s\", timeout %" PRIu64),
269                        serv2str[runp->type], str, dh->timeout);
270             }
271
272           /* Check whether the entry timed out.  */
273           if (dh->timeout < now)
274             {
275               /* This hash bucket could contain entries which need to
276                  be looked at.  */
277               mark[cnt] = true;
278
279               first = MIN (first, cnt);
280               last = MAX (last, cnt);
281
282               /* We only have to look at the data of the first entries
283                  since the count information is kept in the data part
284                  which is shared.  */
285               if (runp->first)
286                 {
287
288                   /* At this point there are two choices: we reload the
289                      value or we discard it.  Do not change NRELOADS if
290                      we never not reload the record.  */
291                   if ((reload_count != UINT_MAX
292                        && __builtin_expect (dh->nreloads >= reload_count, 0))
293                       /* We always remove negative entries.  */
294                       || dh->notfound
295                       /* Discard everything if the user explicitly
296                          requests it.  */
297                       || now == LONG_MAX)
298                     {
299                       /* Remove the value.  */
300                       dh->usable = false;
301
302                       /* We definitely have some garbage entries now.  */
303                       any = true;
304                     }
305                   else
306                     {
307                       /* Reload the value.  We do this only for the
308                          initially used key, not the additionally
309                          added derived value.  */
310                       switch (runp->type)
311                         {
312                         case GETPWBYNAME:
313                           readdpwbyname (table, runp, dh);
314                           break;
315
316                         case GETPWBYUID:
317                           readdpwbyuid (table, runp, dh);
318                           break;
319
320                         case GETGRBYNAME:
321                           readdgrbyname (table, runp, dh);
322                           break;
323
324                         case GETGRBYGID:
325                           readdgrbygid (table, runp, dh);
326                           break;
327
328                         case GETHOSTBYNAME:
329                           readdhstbyname (table, runp, dh);
330                           break;
331
332                         case GETHOSTBYNAMEv6:
333                           readdhstbynamev6 (table, runp, dh);
334                           break;
335
336                         case GETHOSTBYADDR:
337                           readdhstbyaddr (table, runp, dh);
338                           break;
339
340                         case GETHOSTBYADDRv6:
341                           readdhstbyaddrv6 (table, runp, dh);
342                           break;
343
344                         case GETAI:
345                           readdhstai (table, runp, dh);
346                           break;
347
348                         case INITGROUPS:
349                           readdinitgroups (table, runp, dh);
350                           break;
351
352                         default:
353                           assert (! "should never happen");
354                         }
355
356                       /* If the entry has been replaced, we might need
357                          cleanup.  */
358                       any |= !dh->usable;
359                     }
360                 }
361             }
362           else
363             assert (dh->usable);
364
365           run = runp->next;
366         }
367     }
368   while (cnt > 0);
369
370   if (first <= last)
371     {
372       struct hashentry *head = NULL;
373
374       /* Now we have to get the write lock since we are about to modify
375          the table.  */
376       if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
377         {
378           ++table->head->wrlockdelayed;
379           pthread_rwlock_wrlock (&table->lock);
380         }
381
382       while (first <= last)
383         {
384           if (mark[first])
385             {
386               ref_t *old = &table->head->array[first];
387               ref_t run = table->head->array[first];
388
389               while (run != ENDREF)
390                 {
391                   struct hashentry *runp = (struct hashentry *) (data + run);
392                   struct datahead *dh
393                     = (struct datahead *) (data + runp->packet);
394
395                   if (! dh->usable)
396                     {
397                       /* We need the list only for debugging but it is
398                          more costly to avoid creating the list than
399                          doing it.  */
400                       runp->dellist = head;
401                       head = runp;
402
403                       /* No need for an atomic operation, we have the
404                          write lock.  */
405                       --table->head->nentries;
406
407                       run = *old = runp->next;
408                     }
409                   else
410                     {
411                       old = &runp->next;
412                       run = runp->next;
413                     }
414                 }
415             }
416
417           ++first;
418         }
419
420       /* It's all done.  */
421       pthread_rwlock_unlock (&table->lock);
422
423       /* Make sure the data is saved to disk.  */
424       if (table->persistent)
425         msync (table->head,
426                data + table->head->first_free - (char *) table->head,
427                MS_ASYNC);
428
429       /* One extra pass if we do debugging.  */
430       if (__builtin_expect (debug_level > 0, 0))
431         {
432           struct hashentry *runp = head;
433
434           while (runp != NULL)
435             {
436               char buf[INET6_ADDRSTRLEN];
437               const char *str;
438
439               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
440                 {
441                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
442                              data + runp->key, buf, sizeof (buf));
443                   str = buf;
444                 }
445               else
446                 str = data + runp->key;
447
448               dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
449
450               runp = runp->dellist;
451             }
452         }
453     }
454
455   /* Run garbage collection if any entry has been removed or replaced.  */
456   if (any)
457     gc (table);
458 }