(prune_cache): Print correct list when debugging.
[kopensolaris-gnu/glibc.git] / nscd / cache.c
1 /* Copyright (c) 1998, 1999, 2003, 2004 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    The GNU C Library is free software; you can redistribute it and/or
6    modify it under the terms of the GNU Lesser General Public
7    License as published by the Free Software Foundation; either
8    version 2.1 of the License, or (at your option) any later version.
9
10    The GNU C Library 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 GNU
13    Lesser General Public License for more details.
14
15    You should have received a copy of the GNU Lesser General Public
16    License along with the GNU C Library; if not, write to the Free
17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
18    02111-1307 USA.  */
19
20 #include <atomic.h>
21 #include <errno.h>
22 #include <error.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/param.h>
30 #include <sys/stat.h>
31 #include <sys/uio.h>
32
33 #include "nscd.h"
34 #include "dbg_log.h"
35
36 /* Search the cache for a matching entry and return it when found.  If
37    this fails search the negative cache and return (void *) -1 if this
38    search was successful.  Otherwise return NULL.
39
40    This function must be called with the read-lock held.  */
41 struct hashentry *
42 cache_search (request_type type, void *key, size_t len, struct database *table,
43               uid_t owner)
44 {
45   unsigned long int hash = __nis_hash (key, len) % table->module;
46   struct hashentry *work;
47   unsigned long int nsearched = 0;
48
49   work = table->array[hash];
50
51   while (work != NULL)
52     {
53       ++nsearched;
54
55       if (type == work->type && len == work->len
56           && memcmp (key, work->key, len) == 0 && work->owner == owner)
57         {
58           /* We found the entry.  Increment the appropriate counter.  */
59           if (work->data == (void *) -1)
60             ++table->neghit;
61           else
62             ++table->poshit;
63
64           break;
65         }
66
67       work = work->next;
68     }
69
70   if (nsearched > table->maxnsearched)
71     table->maxnsearched = nsearched;
72
73   return work;
74 }
75
76 /* Add a new entry to the cache.  The return value is zero if the function
77    call was successful.
78
79    This function must be called with the read-lock held.
80
81    We modify the table but we nevertheless only acquire a read-lock.
82    This is ok since we use operations which would be safe even without
83    locking, given that the `prune_cache' function never runs.  Using
84    the readlock reduces the chance of conflicts.  */
85 void
86 cache_add (int type, void *key, size_t len, const void *packet, size_t total,
87            void *data, int last, time_t t, struct database *table, uid_t owner)
88 {
89   unsigned long int hash = __nis_hash (key, len) % table->module;
90   struct hashentry *newp;
91
92   newp = malloc (sizeof (struct hashentry));
93   if (newp == NULL)
94     error (EXIT_FAILURE, errno, _("while allocating hash table entry"));
95
96   newp->type = type;
97   newp->len = len;
98   newp->key = key;
99   newp->owner = owner;
100   newp->data = data;
101   newp->timeout = t;
102   newp->packet = packet;
103   newp->total = total;
104
105   newp->last = last;
106
107   /* Put the new entry in the first position.  */
108   do
109     newp->next = table->array[hash];
110   while (atomic_compare_and_exchange_bool_acq (&table->array[hash], newp,
111                                                newp->next));
112
113   /* Update the statistics.  */
114   if (data == (void *) -1)
115     ++table->negmiss;
116   else if (last)
117     ++table->posmiss;
118
119   /* Instead of slowing down the normal process for statistics
120      collection we accept living with some incorrect data.  */
121   unsigned long int nentries = ++table->nentries;
122   if (nentries > table->maxnentries)
123     table->maxnentries = nentries;
124 }
125
126 /* Walk through the table and remove all entries which lifetime ended.
127
128    We have a problem here.  To actually remove the entries we must get
129    the write-lock.  But since we want to keep the time we have the
130    lock as short as possible we cannot simply acquire the lock when we
131    start looking for timedout entries.
132
133    Therefore we do it in two stages: first we look for entries which
134    must be invalidated and remember them.  Then we get the lock and
135    actually remove them.  This is complicated by the way we have to
136    free the data structures since some hash table entries share the same
137    data.  */
138 void
139 prune_cache (struct database *table, time_t now)
140 {
141   size_t cnt = table->module;
142   int mark[cnt];
143   int anything = 0;
144   size_t first = cnt + 1;
145   size_t last = 0;
146
147   /* If this table is not actually used don't do anything.  */
148   if (cnt == 0)
149     return;
150
151   /* If we check for the modification of the underlying file we invalidate
152      the entries also in this case.  */
153   if (table->check_file)
154     {
155       struct stat st;
156
157       if (stat (table->filename, &st) < 0)
158         {
159           char buf[128];
160           /* We cannot stat() the file, disable file checking if the
161              file does not exist.  */
162           dbg_log (_("cannot stat() file `%s': %s"),
163                    table->filename, strerror_r (errno, buf, sizeof (buf)));
164           if (errno == ENOENT)
165             table->check_file = 0;
166         }
167       else
168         {
169           if (st.st_mtime != table->file_mtime)
170             {
171               /* The file changed.  Invalidate all entries.  */
172               now = LONG_MAX;
173               table->file_mtime = st.st_mtime;
174             }
175         }
176     }
177
178   /* We run through the table and find values which are not valid anymore.
179
180      Note that for the initial step, finding the entries to be removed,
181      we don't need to get any lock.  It is at all timed assured that the
182      linked lists are set up correctly and that no second thread prunes
183      the cache.  */
184   do
185     {
186       struct hashentry *runp = table->array[--cnt];
187
188       mark[cnt] = 0;
189
190       while (runp != NULL)
191         {
192           if (runp->timeout < now)
193             {
194               ++mark[cnt];
195               anything = 1;
196               first = MIN (first, cnt);
197               last = MAX (last, cnt);
198             }
199           runp = runp->next;
200         }
201     }
202   while (cnt > 0);
203
204   if (anything)
205     {
206       struct hashentry *head = NULL;
207
208       /* Now we have to get the write lock since we are about to modify
209          the table.  */
210       if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
211         {
212           ++table->wrlockdelayed;
213           pthread_rwlock_wrlock (&table->lock);
214         }
215
216       while (first <= last)
217         {
218           if (mark[first] > 0)
219             {
220               struct hashentry *runp;
221
222               while (table->array[first]->timeout < now)
223                 {
224                   table->array[first]->dellist = head;
225                   head = table->array[first];
226                   table->array[first] = head->next;
227                   --table->nentries;
228                   if (--mark[first] == 0)
229                     break;
230                 }
231
232               runp = table->array[first];
233               while (mark[first] > 0)
234                 {
235                   if (runp->next->timeout < now)
236                     {
237                       runp->next->dellist = head;
238                       head = runp->next;
239                       runp->next = head->next;
240                       --mark[first];
241                       --table->nentries;
242                     }
243                   else
244                     runp = runp->next;
245                 }
246             }
247           ++first;
248         }
249
250       /* It's all done.  */
251       pthread_rwlock_unlock (&table->lock);
252
253       /* One extra pass if we do debugging.  */
254       if (__builtin_expect (debug_level > 0, 0))
255         {
256           struct hashentry *runp = head;
257
258           while (runp != NULL)
259             {
260               char buf[INET6_ADDRSTRLEN];
261               const char *str;
262
263               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
264                 {
265                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
266                              runp->key, buf, sizeof (buf));
267                   str = buf;
268                 }
269               else
270                 str = runp->key;
271
272               dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
273
274               runp = runp->dellist;
275             }
276         }
277
278       /* And another run to free the data.  */
279       do
280         {
281           struct hashentry *old = head;
282
283           /* Free the data structures.  */
284           if (old->data == (void *) -1)
285             free (old->key);
286           else if (old->last)
287             free (old->data);
288
289           head = head->dellist;
290
291           free (old);
292         }
293       while (head != NULL);
294     }
295 }