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 <atomicity.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
  48   work = table->array[hash];
  49
  50   while (work != NULL)
  51     {
  52       if (type == work->type && len == work->len
  53           && memcmp (key, work->key, len) == 0 && work->owner == owner)
  54         {
  55           /* We found the entry.  Increment the appropriate counter.  */
  56           if (work->data == (void *) -1)
  57             ++table->neghit;
  58           else
  59             ++table->poshit;
  60
  61           return work;
  62         }
  63
  64       work = work->next;
  65     }
  66
  67   return NULL;
  68 }
  69
  70 /* Add a new entry to the cache.  The return value is zero if the function
  71    call was successful.
  72
  73    This function must be called with the read-lock held.
  74
  75    We modify the table but we nevertheless only acquire a read-lock.
  76    This is ok since we use operations which would be safe even without
  77    locking, given that the `prune_cache' function never runs.  Using
  78    the readlock reduces the chance of conflicts.  */
  79 void
  80 cache_add (int type, void *key, size_t len, const void *packet, size_t total,
  81            void *data, int last, time_t t, struct database *table, uid_t owner)
  82 {
  83   unsigned long int hash = __nis_hash (key, len) % table->module;
  84   struct hashentry *newp;
  85
  86   newp = malloc (sizeof (struct hashentry));
  87   if (newp == NULL)
  88     error (EXIT_FAILURE, errno, _("while allocating hash table entry"));
  89
  90   newp->type = type;
  91   newp->len = len;
  92   newp->key = key;
  93   newp->owner = owner;
  94   newp->data = data;
  95   newp->timeout = t;
  96   newp->packet = packet;
  97   newp->total = total;
  98
  99   newp->last = last;
 100
 101   /* Put the new entry in the first position.  */
 102   do
 103     newp->next = table->array[hash];
 104   while (! compare_and_swap ((volatile long int *) &table->array[hash],
 105                              (long int) newp->next, (long int) newp));
 106
 107   /* Update the statistics.  */
 108   if (data == (void *) -1)
 109     ++table->negmiss;
 110   else if (last)
 111     ++table->posmiss;
 112 }
 113
 114 /* Walk through the table and remove all entries which lifetime ended.
 115
 116    We have a problem here.  To actually remove the entries we must get
 117    the write-lock.  But since we want to keep the time we have the
 118    lock as short as possible we cannot simply acquire the lock when we
 119    start looking for timedout entries.
 120
 121    Therefore we do it in two stages: first we look for entries which
 122    must be invalidated and remember them.  Then we get the lock and
 123    actually remove them.  This is complicated by the way we have to
 124    free the data structures since some hash table entries share the same
 125    data.  */
 126 void
 127 prune_cache (struct database *table, time_t now)
 128 {
 129   size_t cnt = table->module;
 130   int mark[cnt];
 131   int anything = 0;
 132   size_t first = cnt + 1;
 133   size_t last = 0;
 134
 135   /* If this table is not actually used don't do anything.  */
 136   if (cnt == 0)
 137     return;
 138
 139   /* If we check for the modification of the underlying file we invalidate
 140      the entries also in this case.  */
 141   if (table->check_file)
 142     {
 143       struct stat st;
 144
 145       if (stat (table->filename, &st) < 0)
 146         {
 147           char buf[128];
 148           /* We cannot stat() the file, disable file checking if the
 149              file does not exist.  */
 150           dbg_log (_("cannot stat() file `%s': %s"),
 151                    table->filename, strerror_r (errno, buf, sizeof (buf)));
 152           if (errno == ENOENT)
 153             table->check_file = 0;
 154         }
 155       else
 156         {
 157           if (st.st_mtime != table->file_mtime)
 158             {
 159               /* The file changed.  Invalidate all entries.  */
 160               now = LONG_MAX;
 161               table->file_mtime = st.st_mtime;
 162             }
 163         }
 164     }
 165
 166   /* We run through the table and find values which are not valid anymore.
 167
 168    Note that for the initial step, finding the entries to be removed,
 169    we don't need to get any lock.  It is at all timed assured that the
 170    linked lists are set up correctly and that no second thread prunes
 171    the cache.  */
 172   do
 173     {
 174       struct hashentry *runp = table->array[--cnt];
 175
 176       mark[cnt] = 0;
 177
 178       while (runp != NULL)
 179         {
 180           if (runp->timeout < now)
 181             {
 182               ++mark[cnt];
 183               anything = 1;
 184               first = MIN (first, cnt);
 185               last = MAX (last, cnt);
 186             }
 187           runp = runp->next;
 188         }
 189     }
 190   while (cnt > 0);
 191
 192   if (anything)
 193     {
 194       struct hashentry *head = NULL;
 195
 196       /* Now we have to get the write lock since we are about to modify
 197          the table.  */
 198       pthread_rwlock_wrlock (&table->lock);
 199
 200       while (first <= last)
 201         {
 202           if (mark[first] > 0)
 203             {
 204               struct hashentry *runp;
 205
 206               while (table->array[first]->timeout < now)
 207                 {
 208                   table->array[first]->dellist = head;
 209                   head = table->array[first];
 210                   table->array[first] = head->next;
 211                   if (--mark[first] == 0)
 212                     break;
 213                 }
 214
 215               runp = table->array[first];
 216               while (mark[first] > 0)
 217                 {
 218                   if (runp->next->timeout < now)
 219                     {
 220                       runp->next->dellist = head;
 221                       head = runp->next;
 222                       runp->next = head->next;
 223                       --mark[first];
 224                     }
 225                   else
 226                     runp = runp->next;
 227                 }
 228             }
 229           ++first;
 230         }
 231
 232       /* It's all done.  */
 233       pthread_rwlock_unlock (&table->lock);
 234
 235       /* And another run to free the data.  */
 236       do
 237         {
 238           struct hashentry *old = head;
 239
 240           if (debug_level > 0)
 241             {
 242               char buf[INET6_ADDRSTRLEN];
 243               const char *str;
 244
 245               if ((old->type == GETHOSTBYADDR || old->type == GETHOSTBYADDRv6)
 246                   && (old->last || old->data == (void *) -1))
 247                 {
 248                   inet_ntop (old->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
 249                              old->key, buf, sizeof (buf));
 250                   str = buf;
 251                 }
 252               else
 253                 str = old->last ? old->key : (old->data == (void *) -1
 254                                               ? old->key : "???");
 255
 256               dbg_log ("remove %s entry \"%s\"", serv2str[old->type], str);
 257             }
 258
 259           /* Free the data structures.  */
 260           if (old->data == (void *) -1)
 261             free (old->key);
 262           else if (old->last)
 263             free (old->data);
 264
 265           head = head->dellist;
 266
 267           free (old);
 268         }
 269       while (head != NULL);
 270     }
 271 }