nscd/cache.c

   1 /* Copyright (c) 1998, 1999, 2003 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->next;
 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 }