]>
Commit | Line | Data |
---|---|---|
d4697bc9 | 1 | /* Copyright (c) 1998-2014 Free Software Foundation, Inc. |
67479a70 UD |
2 | This file is part of the GNU C Library. |
3 | Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998. | |
4 | ||
43bc8ac6 | 5 | This program is free software; you can redistribute it and/or modify |
2e2efe65 RM |
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. | |
67479a70 | 9 | |
43bc8ac6 | 10 | This program is distributed in the hope that it will be useful, |
67479a70 | 11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
43bc8ac6 UD |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | GNU General Public License for more details. | |
67479a70 | 14 | |
43bc8ac6 | 15 | You should have received a copy of the GNU General Public License |
59ba27a6 | 16 | along with this program; if not, see <http://www.gnu.org/licenses/>. */ |
67479a70 | 17 | |
a95a08b4 | 18 | #include <assert.h> |
4009bf40 | 19 | #include <atomic.h> |
67479a70 UD |
20 | #include <errno.h> |
21 | #include <error.h> | |
a757fda3 | 22 | #include <inttypes.h> |
67479a70 UD |
23 | #include <limits.h> |
24 | #include <stdlib.h> | |
25 | #include <string.h> | |
4360eafd | 26 | #include <libintl.h> |
e518937a | 27 | #include <arpa/inet.h> |
67479a70 | 28 | #include <rpcsvc/nis.h> |
a95a08b4 | 29 | #include <sys/mman.h> |
67479a70 UD |
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 | ||
a95a08b4 | 37 | |
30294ea4 UD |
38 | /* Wrapper functions with error checking for standard functions. */ |
39 | extern void *xcalloc (size_t n, size_t s); | |
40 | ||
41 | ||
a95a08b4 UD |
42 | /* Number of times a value is reloaded without being used. UINT_MAX |
43 | means unlimited. */ | |
44 | unsigned int reload_count = DEFAULT_RELOAD_LIMIT; | |
45 | ||
46 | ||
a4c7ea7b UD |
47 | static time_t (*const readdfcts[LASTREQ]) (struct database_dyn *, |
48 | struct hashentry *, | |
49 | struct datahead *) = | |
b21fa963 UD |
50 | { |
51 | [GETPWBYNAME] = readdpwbyname, | |
52 | [GETPWBYUID] = readdpwbyuid, | |
53 | [GETGRBYNAME] = readdgrbyname, | |
54 | [GETGRBYGID] = readdgrbygid, | |
55 | [GETHOSTBYNAME] = readdhstbyname, | |
56 | [GETHOSTBYNAMEv6] = readdhstbynamev6, | |
57 | [GETHOSTBYADDR] = readdhstbyaddr, | |
58 | [GETHOSTBYADDRv6] = readdhstbyaddrv6, | |
59 | [GETAI] = readdhstai, | |
60 | [INITGROUPS] = readdinitgroups, | |
61 | [GETSERVBYNAME] = readdservbyname, | |
684ae515 UD |
62 | [GETSERVBYPORT] = readdservbyport, |
63 | [GETNETGRENT] = readdgetnetgrent, | |
64 | [INNETGR] = readdinnetgr | |
b21fa963 UD |
65 | }; |
66 | ||
67 | ||
67479a70 UD |
68 | /* Search the cache for a matching entry and return it when found. If |
69 | this fails search the negative cache and return (void *) -1 if this | |
70 | search was successful. Otherwise return NULL. | |
71 | ||
72 | This function must be called with the read-lock held. */ | |
a95a08b4 | 73 | struct datahead * |
684ae515 | 74 | cache_search (request_type type, const void *key, size_t len, |
a95a08b4 | 75 | struct database_dyn *table, uid_t owner) |
67479a70 | 76 | { |
a95a08b4 | 77 | unsigned long int hash = __nis_hash (key, len) % table->head->module; |
67479a70 | 78 | |
a95a08b4 UD |
79 | unsigned long int nsearched = 0; |
80 | struct datahead *result = NULL; | |
67479a70 | 81 | |
a95a08b4 UD |
82 | ref_t work = table->head->array[hash]; |
83 | while (work != ENDREF) | |
67479a70 | 84 | { |
c86e6aec UD |
85 | ++nsearched; |
86 | ||
a95a08b4 UD |
87 | struct hashentry *here = (struct hashentry *) (table->data + work); |
88 | ||
89 | if (type == here->type && len == here->len | |
90 | && memcmp (key, table->data + here->key, len) == 0 | |
91 | && here->owner == owner) | |
67479a70 UD |
92 | { |
93 | /* We found the entry. Increment the appropriate counter. */ | |
a95a08b4 UD |
94 | struct datahead *dh |
95 | = (struct datahead *) (table->data + here->packet); | |
96 | ||
97 | /* See whether we must ignore the entry. */ | |
98 | if (dh->usable) | |
99 | { | |
100 | /* We do not synchronize the memory here. The statistics | |
101 | data is not crucial, we synchronize only once in a while | |
102 | in the cleanup threads. */ | |
103 | if (dh->notfound) | |
104 | ++table->head->neghit; | |
105 | else | |
106 | { | |
107 | ++table->head->poshit; | |
108 | ||
109 | if (dh->nreloads != 0) | |
110 | dh->nreloads = 0; | |
111 | } | |
67479a70 | 112 | |
a95a08b4 UD |
113 | result = dh; |
114 | break; | |
115 | } | |
67479a70 UD |
116 | } |
117 | ||
a95a08b4 | 118 | work = here->next; |
67479a70 UD |
119 | } |
120 | ||
a95a08b4 UD |
121 | if (nsearched > table->head->maxnsearched) |
122 | table->head->maxnsearched = nsearched; | |
c86e6aec | 123 | |
a95a08b4 | 124 | return result; |
67479a70 UD |
125 | } |
126 | ||
127 | /* Add a new entry to the cache. The return value is zero if the function | |
128 | call was successful. | |
129 | ||
130 | This function must be called with the read-lock held. | |
131 | ||
132 | We modify the table but we nevertheless only acquire a read-lock. | |
133 | This is ok since we use operations which would be safe even without | |
134 | locking, given that the `prune_cache' function never runs. Using | |
135 | the readlock reduces the chance of conflicts. */ | |
a95a08b4 UD |
136 | int |
137 | cache_add (int type, const void *key, size_t len, struct datahead *packet, | |
138 | bool first, struct database_dyn *table, | |
528741cb | 139 | uid_t owner, bool prune_wakeup) |
67479a70 | 140 | { |
a1ffb40e | 141 | if (__glibc_unlikely (debug_level >= 2)) |
418dfb12 UD |
142 | { |
143 | const char *str; | |
144 | char buf[INET6_ADDRSTRLEN + 1]; | |
145 | if (type == GETHOSTBYADDR || type == GETHOSTBYADDRv6) | |
146 | str = inet_ntop (type == GETHOSTBYADDR ? AF_INET : AF_INET6, | |
147 | key, buf, sizeof (buf)); | |
148 | else | |
149 | str = key; | |
150 | ||
151 | dbg_log (_("add new entry \"%s\" of type %s for %s to cache%s"), | |
152 | str, serv2str[type], dbnames[table - dbs], | |
11bf311e | 153 | first ? _(" (first)") : ""); |
418dfb12 | 154 | } |
a95a08b4 UD |
155 | |
156 | unsigned long int hash = __nis_hash (key, len) % table->head->module; | |
67479a70 UD |
157 | struct hashentry *newp; |
158 | ||
20e498bd | 159 | newp = mempool_alloc (table, sizeof (struct hashentry), 0); |
a95a08b4 | 160 | /* If we cannot allocate memory, just do not do anything. */ |
67479a70 | 161 | if (newp == NULL) |
f7685cef | 162 | { |
d0296640 UD |
163 | /* If necessary mark the entry as unusable so that lookups will |
164 | not use it. */ | |
165 | if (first) | |
166 | packet->usable = false; | |
167 | ||
f7685cef UD |
168 | return -1; |
169 | } | |
67479a70 UD |
170 | |
171 | newp->type = type; | |
a95a08b4 | 172 | newp->first = first; |
67479a70 | 173 | newp->len = len; |
a95a08b4 UD |
174 | newp->key = (char *) key - table->data; |
175 | assert (newp->key + newp->len <= table->head->first_free); | |
a1c542bf | 176 | newp->owner = owner; |
a95a08b4 | 177 | newp->packet = (char *) packet - table->data; |
528741cb | 178 | assert ((newp->packet & BLOCK_ALIGN_M1) == 0); |
67479a70 UD |
179 | |
180 | /* Put the new entry in the first position. */ | |
181 | do | |
a95a08b4 | 182 | newp->next = table->head->array[hash]; |
50158f95 | 183 | while (atomic_compare_and_exchange_bool_rel (&table->head->array[hash], |
a95a08b4 UD |
184 | (ref_t) ((char *) newp |
185 | - table->data), | |
186 | (ref_t) newp->next)); | |
67479a70 UD |
187 | |
188 | /* Update the statistics. */ | |
a95a08b4 UD |
189 | if (packet->notfound) |
190 | ++table->head->negmiss; | |
191 | else if (first) | |
192 | ++table->head->posmiss; | |
193 | ||
194 | /* We depend on this value being correct and at least as high as the | |
195 | real number of entries. */ | |
196 | atomic_increment (&table->head->nentries); | |
197 | ||
198 | /* It does not matter that we are not loading the just increment | |
199 | value, this is just for statistics. */ | |
200 | unsigned long int nentries = table->head->nentries; | |
201 | if (nentries > table->head->maxnentries) | |
202 | table->head->maxnentries = nentries; | |
203 | ||
cc46d02a UD |
204 | if (table->persistent) |
205 | // XXX async OK? | |
206 | msync ((void *) table->head, | |
207 | (char *) &table->head->array[hash] - (char *) table->head | |
208 | + sizeof (ref_t), MS_ASYNC); | |
209 | ||
528741cb UD |
210 | /* We do not have to worry about the pruning thread if we are |
211 | re-adding the data since this is done by the pruning thread. We | |
212 | also do not have to do anything in case this is not the first | |
213 | time the data is entered since different data heads all have the | |
214 | same timeout. */ | |
215 | if (first && prune_wakeup) | |
216 | { | |
217 | /* Perhaps the prune thread for the table is not running in a long | |
218 | time. Wake it if necessary. */ | |
219 | pthread_mutex_lock (&table->prune_lock); | |
220 | time_t next_wakeup = table->wakeup_time; | |
221 | bool do_wakeup = false; | |
222 | if (next_wakeup > packet->timeout + CACHE_PRUNE_INTERVAL) | |
223 | { | |
224 | table->wakeup_time = packet->timeout; | |
225 | do_wakeup = true; | |
226 | } | |
227 | pthread_mutex_unlock (&table->prune_lock); | |
228 | if (do_wakeup) | |
ffb1b882 | 229 | pthread_cond_signal (&table->prune_cond); |
528741cb | 230 | } |
ffb1b882 | 231 | |
a95a08b4 | 232 | return 0; |
67479a70 UD |
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 | |
ce85d65b | 246 | data. */ |
ffb1b882 | 247 | time_t |
902c4291 | 248 | prune_cache (struct database_dyn *table, time_t now, int fd) |
67479a70 | 249 | { |
a95a08b4 | 250 | size_t cnt = table->head->module; |
67479a70 | 251 | |
9514f4e6 UD |
252 | /* If this table is not actually used don't do anything. */ |
253 | if (cnt == 0) | |
902c4291 UD |
254 | { |
255 | if (fd != -1) | |
256 | { | |
257 | /* Reply to the INVALIDATE initiator. */ | |
258 | int32_t resp = 0; | |
259 | writeall (fd, &resp, sizeof (resp)); | |
260 | } | |
ffb1b882 UD |
261 | |
262 | /* No need to do this again anytime soon. */ | |
263 | return 24 * 60 * 60; | |
902c4291 | 264 | } |
9514f4e6 | 265 | |
67479a70 UD |
266 | /* If we check for the modification of the underlying file we invalidate |
267 | the entries also in this case. */ | |
319b9ad4 | 268 | if (table->check_file && now != LONG_MAX) |
67479a70 | 269 | { |
319b9ad4 | 270 | struct traced_file *runp = table->traced_files; |
67479a70 | 271 | |
319b9ad4 | 272 | while (runp != NULL) |
67479a70 | 273 | { |
319b9ad4 UD |
274 | #ifdef HAVE_INOTIFY |
275 | if (runp->inotify_descr == -1) | |
276 | #endif | |
3d08d800 | 277 | { |
319b9ad4 UD |
278 | struct stat64 st; |
279 | ||
280 | if (stat64 (runp->fname, &st) < 0) | |
281 | { | |
282 | char buf[128]; | |
283 | /* We cannot stat() the file, disable file checking if the | |
284 | file does not exist. */ | |
285 | dbg_log (_("cannot stat() file `%s': %s"), | |
286 | runp->fname, strerror_r (errno, buf, sizeof (buf))); | |
287 | if (errno == ENOENT) | |
288 | table->check_file = 0; | |
289 | } | |
290 | else | |
291 | { | |
292 | if (st.st_mtime != table->file_mtime) | |
293 | { | |
294 | /* The file changed. Invalidate all entries. */ | |
295 | now = LONG_MAX; | |
296 | table->file_mtime = st.st_mtime; | |
297 | } | |
298 | } | |
3d08d800 | 299 | } |
319b9ad4 UD |
300 | |
301 | runp = runp->next; | |
67479a70 UD |
302 | } |
303 | } | |
304 | ||
305 | /* We run through the table and find values which are not valid anymore. | |
306 | ||
c86e6aec UD |
307 | Note that for the initial step, finding the entries to be removed, |
308 | we don't need to get any lock. It is at all timed assured that the | |
309 | linked lists are set up correctly and that no second thread prunes | |
310 | the cache. */ | |
30294ea4 UD |
311 | bool *mark; |
312 | size_t memory_needed = cnt * sizeof (bool); | |
313 | bool mark_use_alloca; | |
a1ffb40e | 314 | if (__glibc_likely (memory_needed <= MAX_STACK_USE)) |
30294ea4 UD |
315 | { |
316 | mark = alloca (cnt * sizeof (bool)); | |
317 | memset (mark, '\0', memory_needed); | |
318 | mark_use_alloca = true; | |
319 | } | |
320 | else | |
321 | { | |
322 | mark = xcalloc (1, memory_needed); | |
323 | mark_use_alloca = false; | |
324 | } | |
a95a08b4 UD |
325 | size_t first = cnt + 1; |
326 | size_t last = 0; | |
327 | char *const data = table->data; | |
328 | bool any = false; | |
329 | ||
a1ffb40e | 330 | if (__glibc_unlikely (debug_level > 2)) |
a757fda3 UD |
331 | dbg_log (_("pruning %s cache; time %ld"), |
332 | dbnames[table - dbs], (long int) now); | |
333 | ||
f9e2261b UD |
334 | #define NO_TIMEOUT LONG_MAX |
335 | time_t next_timeout = NO_TIMEOUT; | |
67479a70 UD |
336 | do |
337 | { | |
a95a08b4 | 338 | ref_t run = table->head->array[--cnt]; |
67479a70 | 339 | |
a95a08b4 | 340 | while (run != ENDREF) |
67479a70 | 341 | { |
a95a08b4 UD |
342 | struct hashentry *runp = (struct hashentry *) (data + run); |
343 | struct datahead *dh = (struct datahead *) (data + runp->packet); | |
344 | ||
a757fda3 | 345 | /* Some debug support. */ |
a1ffb40e | 346 | if (__glibc_unlikely (debug_level > 2)) |
a757fda3 UD |
347 | { |
348 | char buf[INET6_ADDRSTRLEN]; | |
349 | const char *str; | |
350 | ||
351 | if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6) | |
352 | { | |
353 | inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6, | |
354 | data + runp->key, buf, sizeof (buf)); | |
355 | str = buf; | |
356 | } | |
357 | else | |
358 | str = data + runp->key; | |
359 | ||
360 | dbg_log (_("considering %s entry \"%s\", timeout %" PRIu64), | |
361 | serv2str[runp->type], str, dh->timeout); | |
362 | } | |
363 | ||
a95a08b4 UD |
364 | /* Check whether the entry timed out. */ |
365 | if (dh->timeout < now) | |
67479a70 | 366 | { |
a95a08b4 UD |
367 | /* This hash bucket could contain entries which need to |
368 | be looked at. */ | |
369 | mark[cnt] = true; | |
370 | ||
67479a70 UD |
371 | first = MIN (first, cnt); |
372 | last = MAX (last, cnt); | |
a95a08b4 UD |
373 | |
374 | /* We only have to look at the data of the first entries | |
375 | since the count information is kept in the data part | |
376 | which is shared. */ | |
377 | if (runp->first) | |
378 | { | |
379 | ||
380 | /* At this point there are two choices: we reload the | |
381 | value or we discard it. Do not change NRELOADS if | |
382 | we never not reload the record. */ | |
383 | if ((reload_count != UINT_MAX | |
384 | && __builtin_expect (dh->nreloads >= reload_count, 0)) | |
385 | /* We always remove negative entries. */ | |
386 | || dh->notfound | |
387 | /* Discard everything if the user explicitly | |
388 | requests it. */ | |
389 | || now == LONG_MAX) | |
390 | { | |
391 | /* Remove the value. */ | |
392 | dh->usable = false; | |
393 | ||
394 | /* We definitely have some garbage entries now. */ | |
395 | any = true; | |
396 | } | |
397 | else | |
398 | { | |
399 | /* Reload the value. We do this only for the | |
400 | initially used key, not the additionally | |
401 | added derived value. */ | |
b21fa963 UD |
402 | assert (runp->type < LASTREQ |
403 | && readdfcts[runp->type] != NULL); | |
404 | ||
a4c7ea7b UD |
405 | time_t timeout = readdfcts[runp->type] (table, runp, dh); |
406 | next_timeout = MIN (next_timeout, timeout); | |
a95a08b4 UD |
407 | |
408 | /* If the entry has been replaced, we might need | |
409 | cleanup. */ | |
410 | any |= !dh->usable; | |
411 | } | |
412 | } | |
67479a70 | 413 | } |
a95a08b4 | 414 | else |
02aa27fe UD |
415 | { |
416 | assert (dh->usable); | |
417 | next_timeout = MIN (next_timeout, dh->timeout); | |
418 | } | |
a95a08b4 UD |
419 | |
420 | run = runp->next; | |
67479a70 UD |
421 | } |
422 | } | |
423 | while (cnt > 0); | |
424 | ||
a1ffb40e | 425 | if (__glibc_unlikely (fd != -1)) |
902c4291 UD |
426 | { |
427 | /* Reply to the INVALIDATE initiator that the cache has been | |
428 | invalidated. */ | |
429 | int32_t resp = 0; | |
430 | writeall (fd, &resp, sizeof (resp)); | |
431 | } | |
432 | ||
a95a08b4 | 433 | if (first <= last) |
67479a70 UD |
434 | { |
435 | struct hashentry *head = NULL; | |
436 | ||
437 | /* Now we have to get the write lock since we are about to modify | |
438 | the table. */ | |
a1ffb40e | 439 | if (__glibc_unlikely (pthread_rwlock_trywrlock (&table->lock) != 0)) |
c86e6aec | 440 | { |
a95a08b4 | 441 | ++table->head->wrlockdelayed; |
c86e6aec UD |
442 | pthread_rwlock_wrlock (&table->lock); |
443 | } | |
67479a70 UD |
444 | |
445 | while (first <= last) | |
446 | { | |
a95a08b4 | 447 | if (mark[first]) |
67479a70 | 448 | { |
a95a08b4 UD |
449 | ref_t *old = &table->head->array[first]; |
450 | ref_t run = table->head->array[first]; | |
67479a70 | 451 | |
528741cb UD |
452 | assert (run != ENDREF); |
453 | do | |
67479a70 | 454 | { |
a95a08b4 UD |
455 | struct hashentry *runp = (struct hashentry *) (data + run); |
456 | struct datahead *dh | |
457 | = (struct datahead *) (data + runp->packet); | |
67479a70 | 458 | |
a95a08b4 | 459 | if (! dh->usable) |
67479a70 | 460 | { |
a95a08b4 UD |
461 | /* We need the list only for debugging but it is |
462 | more costly to avoid creating the list than | |
463 | doing it. */ | |
464 | runp->dellist = head; | |
465 | head = runp; | |
466 | ||
467 | /* No need for an atomic operation, we have the | |
468 | write lock. */ | |
469 | --table->head->nentries; | |
470 | ||
471 | run = *old = runp->next; | |
67479a70 UD |
472 | } |
473 | else | |
a95a08b4 UD |
474 | { |
475 | old = &runp->next; | |
476 | run = runp->next; | |
477 | } | |
67479a70 | 478 | } |
528741cb | 479 | while (run != ENDREF); |
67479a70 | 480 | } |
a95a08b4 | 481 | |
67479a70 UD |
482 | ++first; |
483 | } | |
484 | ||
485 | /* It's all done. */ | |
486 | pthread_rwlock_unlock (&table->lock); | |
487 | ||
a95a08b4 UD |
488 | /* Make sure the data is saved to disk. */ |
489 | if (table->persistent) | |
490 | msync (table->head, | |
a757fda3 | 491 | data + table->head->first_free - (char *) table->head, |
a95a08b4 UD |
492 | MS_ASYNC); |
493 | ||
c86e6aec | 494 | /* One extra pass if we do debugging. */ |
a1ffb40e | 495 | if (__glibc_unlikely (debug_level > 0)) |
67479a70 | 496 | { |
c86e6aec | 497 | struct hashentry *runp = head; |
67479a70 | 498 | |
c86e6aec | 499 | while (runp != NULL) |
8d8c6efa UD |
500 | { |
501 | char buf[INET6_ADDRSTRLEN]; | |
502 | const char *str; | |
503 | ||
c86e6aec | 504 | if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6) |
8d8c6efa | 505 | { |
c86e6aec | 506 | inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6, |
a757fda3 | 507 | data + runp->key, buf, sizeof (buf)); |
8d8c6efa UD |
508 | str = buf; |
509 | } | |
510 | else | |
a757fda3 | 511 | str = data + runp->key; |
8d8c6efa | 512 | |
c86e6aec UD |
513 | dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str); |
514 | ||
f3063fc7 | 515 | runp = runp->dellist; |
8d8c6efa | 516 | } |
c86e6aec | 517 | } |
67479a70 | 518 | } |
a95a08b4 | 519 | |
a1ffb40e | 520 | if (__glibc_unlikely (! mark_use_alloca)) |
30294ea4 UD |
521 | free (mark); |
522 | ||
a95a08b4 UD |
523 | /* Run garbage collection if any entry has been removed or replaced. */ |
524 | if (any) | |
525 | gc (table); | |
9636a217 | 526 | |
f9e2261b UD |
527 | /* If there is no entry in the database and we therefore have no new |
528 | timeout value, tell the caller to wake up in 24 hours. */ | |
529 | return next_timeout == NO_TIMEOUT ? 24 * 60 * 60 : next_timeout - now; | |
67479a70 | 530 | } |