Fix one more issue with the glob patch.
[glibc.git] / nscd / cache.c
blob3e6793df2f7dfc2bc3616345fb0cec2a6137c160
1 /* Copyright (c) 1998, 1999, 2003-2008, 2009 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998.
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.
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.
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. */
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>
35 #include "nscd.h"
36 #include "dbg_log.h"
39 /* Wrapper functions with error checking for standard functions. */
40 extern void *xcalloc (size_t n, size_t s);
43 /* Number of times a value is reloaded without being used. UINT_MAX
44 means unlimited. */
45 unsigned int reload_count = DEFAULT_RELOAD_LIMIT;
48 static void (*const readdfcts[LASTREQ]) (struct database_dyn *,
49 struct hashentry *,
50 struct datahead *) =
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
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.
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)
76 unsigned long int hash = __nis_hash (key, len) % table->head->module;
78 unsigned long int nsearched = 0;
79 struct datahead *result = NULL;
81 ref_t work = table->head->array[hash];
82 while (work != ENDREF)
84 ++nsearched;
86 struct hashentry *here = (struct hashentry *) (table->data + work);
88 if (type == here->type && len == here->len
89 && memcmp (key, table->data + here->key, len) == 0
90 && here->owner == owner)
92 /* We found the entry. Increment the appropriate counter. */
93 struct datahead *dh
94 = (struct datahead *) (table->data + here->packet);
96 /* See whether we must ignore the entry. */
97 if (dh->usable)
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
106 ++table->head->poshit;
108 if (dh->nreloads != 0)
109 dh->nreloads = 0;
112 result = dh;
113 break;
117 work = here->next;
120 if (nsearched > table->head->maxnsearched)
121 table->head->maxnsearched = nsearched;
123 return result;
126 /* Add a new entry to the cache. The return value is zero if the function
127 call was successful.
129 This function must be called with the read-lock held.
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. */
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, bool prune_wakeup)
140 if (__builtin_expect (debug_level >= 2, 0))
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;
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)") : "");
155 unsigned long int hash = __nis_hash (key, len) % table->head->module;
156 struct hashentry *newp;
158 newp = mempool_alloc (table, sizeof (struct hashentry), 0);
159 /* If we cannot allocate memory, just do not do anything. */
160 if (newp == NULL)
162 /* If necessary mark the entry as unusable so that lookups will
163 not use it. */
164 if (first)
165 packet->usable = false;
167 return -1;
170 newp->type = type;
171 newp->first = first;
172 newp->len = len;
173 newp->key = (char *) key - table->data;
174 assert (newp->key + newp->len <= table->head->first_free);
175 newp->owner = owner;
176 newp->packet = (char *) packet - table->data;
177 assert ((newp->packet & BLOCK_ALIGN_M1) == 0);
179 /* Put the new entry in the first position. */
181 newp->next = table->head->array[hash];
182 while (atomic_compare_and_exchange_bool_rel (&table->head->array[hash],
183 (ref_t) ((char *) newp
184 - table->data),
185 (ref_t) newp->next));
187 /* Update the statistics. */
188 if (packet->notfound)
189 ++table->head->negmiss;
190 else if (first)
191 ++table->head->posmiss;
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);
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;
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);
209 /* We do not have to worry about the pruning thread if we are
210 re-adding the data since this is done by the pruning thread. We
211 also do not have to do anything in case this is not the first
212 time the data is entered since different data heads all have the
213 same timeout. */
214 if (first && prune_wakeup)
216 /* Perhaps the prune thread for the table is not running in a long
217 time. Wake it if necessary. */
218 pthread_mutex_lock (&table->prune_lock);
219 time_t next_wakeup = table->wakeup_time;
220 bool do_wakeup = false;
221 if (next_wakeup > packet->timeout + CACHE_PRUNE_INTERVAL)
223 table->wakeup_time = packet->timeout;
224 do_wakeup = true;
226 pthread_mutex_unlock (&table->prune_lock);
227 if (do_wakeup)
228 pthread_cond_signal (&table->prune_cond);
231 return 0;
234 /* Walk through the table and remove all entries which lifetime ended.
236 We have a problem here. To actually remove the entries we must get
237 the write-lock. But since we want to keep the time we have the
238 lock as short as possible we cannot simply acquire the lock when we
239 start looking for timedout entries.
241 Therefore we do it in two stages: first we look for entries which
242 must be invalidated and remember them. Then we get the lock and
243 actually remove them. This is complicated by the way we have to
244 free the data structures since some hash table entries share the same
245 data. */
246 time_t
247 prune_cache (struct database_dyn *table, time_t now, int fd)
249 size_t cnt = table->head->module;
251 /* If this table is not actually used don't do anything. */
252 if (cnt == 0)
254 if (fd != -1)
256 /* Reply to the INVALIDATE initiator. */
257 int32_t resp = 0;
258 writeall (fd, &resp, sizeof (resp));
261 /* No need to do this again anytime soon. */
262 return 24 * 60 * 60;
265 /* If we check for the modification of the underlying file we invalidate
266 the entries also in this case. */
267 if (table->inotify_descr < 0 && table->check_file && now != LONG_MAX)
269 struct stat64 st;
271 if (stat64 (table->filename, &st) < 0)
273 char buf[128];
274 /* We cannot stat() the file, disable file checking if the
275 file does not exist. */
276 dbg_log (_("cannot stat() file `%s': %s"),
277 table->filename, strerror_r (errno, buf, sizeof (buf)));
278 if (errno == ENOENT)
279 table->check_file = 0;
281 else
283 if (st.st_mtime != table->file_mtime)
285 /* The file changed. Invalidate all entries. */
286 now = LONG_MAX;
287 table->file_mtime = st.st_mtime;
292 /* We run through the table and find values which are not valid anymore.
294 Note that for the initial step, finding the entries to be removed,
295 we don't need to get any lock. It is at all timed assured that the
296 linked lists are set up correctly and that no second thread prunes
297 the cache. */
298 bool *mark;
299 size_t memory_needed = cnt * sizeof (bool);
300 bool mark_use_alloca;
301 if (__builtin_expect (memory_needed <= MAX_STACK_USE, 1))
303 mark = alloca (cnt * sizeof (bool));
304 memset (mark, '\0', memory_needed);
305 mark_use_alloca = true;
307 else
309 mark = xcalloc (1, memory_needed);
310 mark_use_alloca = false;
312 size_t first = cnt + 1;
313 size_t last = 0;
314 char *const data = table->data;
315 bool any = false;
317 if (__builtin_expect (debug_level > 2, 0))
318 dbg_log (_("pruning %s cache; time %ld"),
319 dbnames[table - dbs], (long int) now);
321 #define NO_TIMEOUT LONG_MAX
322 time_t next_timeout = NO_TIMEOUT;
325 ref_t run = table->head->array[--cnt];
327 while (run != ENDREF)
329 struct hashentry *runp = (struct hashentry *) (data + run);
330 struct datahead *dh = (struct datahead *) (data + runp->packet);
332 /* Some debug support. */
333 if (__builtin_expect (debug_level > 2, 0))
335 char buf[INET6_ADDRSTRLEN];
336 const char *str;
338 if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
340 inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
341 data + runp->key, buf, sizeof (buf));
342 str = buf;
344 else
345 str = data + runp->key;
347 dbg_log (_("considering %s entry \"%s\", timeout %" PRIu64),
348 serv2str[runp->type], str, dh->timeout);
351 /* Check whether the entry timed out. */
352 if (dh->timeout < now)
354 /* This hash bucket could contain entries which need to
355 be looked at. */
356 mark[cnt] = true;
358 first = MIN (first, cnt);
359 last = MAX (last, cnt);
361 /* We only have to look at the data of the first entries
362 since the count information is kept in the data part
363 which is shared. */
364 if (runp->first)
367 /* At this point there are two choices: we reload the
368 value or we discard it. Do not change NRELOADS if
369 we never not reload the record. */
370 if ((reload_count != UINT_MAX
371 && __builtin_expect (dh->nreloads >= reload_count, 0))
372 /* We always remove negative entries. */
373 || dh->notfound
374 /* Discard everything if the user explicitly
375 requests it. */
376 || now == LONG_MAX)
378 /* Remove the value. */
379 dh->usable = false;
381 /* We definitely have some garbage entries now. */
382 any = true;
384 else
386 /* Reload the value. We do this only for the
387 initially used key, not the additionally
388 added derived value. */
389 assert (runp->type < LASTREQ
390 && readdfcts[runp->type] != NULL);
392 readdfcts[runp->type] (table, runp, dh);
394 /* If the entry has been replaced, we might need
395 cleanup. */
396 any |= !dh->usable;
400 else
402 assert (dh->usable);
403 next_timeout = MIN (next_timeout, dh->timeout);
406 run = runp->next;
409 while (cnt > 0);
411 if (__builtin_expect (fd != -1, 0))
413 /* Reply to the INVALIDATE initiator that the cache has been
414 invalidated. */
415 int32_t resp = 0;
416 writeall (fd, &resp, sizeof (resp));
419 if (first <= last)
421 struct hashentry *head = NULL;
423 /* Now we have to get the write lock since we are about to modify
424 the table. */
425 if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
427 ++table->head->wrlockdelayed;
428 pthread_rwlock_wrlock (&table->lock);
431 while (first <= last)
433 if (mark[first])
435 ref_t *old = &table->head->array[first];
436 ref_t run = table->head->array[first];
438 assert (run != ENDREF);
441 struct hashentry *runp = (struct hashentry *) (data + run);
442 struct datahead *dh
443 = (struct datahead *) (data + runp->packet);
445 if (! dh->usable)
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;
453 /* No need for an atomic operation, we have the
454 write lock. */
455 --table->head->nentries;
457 run = *old = runp->next;
459 else
461 old = &runp->next;
462 run = runp->next;
465 while (run != ENDREF);
468 ++first;
471 /* It's all done. */
472 pthread_rwlock_unlock (&table->lock);
474 /* Make sure the data is saved to disk. */
475 if (table->persistent)
476 msync (table->head,
477 data + table->head->first_free - (char *) table->head,
478 MS_ASYNC);
480 /* One extra pass if we do debugging. */
481 if (__builtin_expect (debug_level > 0, 0))
483 struct hashentry *runp = head;
485 while (runp != NULL)
487 char buf[INET6_ADDRSTRLEN];
488 const char *str;
490 if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
492 inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
493 data + runp->key, buf, sizeof (buf));
494 str = buf;
496 else
497 str = data + runp->key;
499 dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
501 runp = runp->dellist;
506 if (__builtin_expect (! mark_use_alloca, 0))
507 free (mark);
509 /* Run garbage collection if any entry has been removed or replaced. */
510 if (any)
511 gc (table);
513 /* If there is no entry in the database and we therefore have no new
514 timeout value, tell the caller to wake up in 24 hours. */
515 return next_timeout == NO_TIMEOUT ? 24 * 60 * 60 : next_timeout - now;