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 <assert.h>
  21 #include <atomic.h>
  22 #include <errno.h>
  23 #include <error.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>
  34
  35 #include "nscd.h"
  36 #include "dbg_log.h"
  37
  38
  39 /* Number of times a value is reloaded without being used.  UINT_MAX
  40    means unlimited.  */
  41 unsigned int reload_count = DEFAULT_RELOAD_LIMIT;
  42
  43
  44 /* Search the cache for a matching entry and return it when found.  If
  45    this fails search the negative cache and return (void *) -1 if this
  46    search was successful.  Otherwise return NULL.
  47
  48    This function must be called with the read-lock held.  */
  49 struct datahead *
  50 cache_search (request_type type, void *key, size_t len,
  51               struct database_dyn *table, uid_t owner)
  52 {
  53   unsigned long int hash = __nis_hash (key, len) % table->head->module;
  54
  55   unsigned long int nsearched = 0;
  56   struct datahead *result = NULL;
  57
  58   ref_t work = table->head->array[hash];
  59   while (work != ENDREF)
  60     {
  61       ++nsearched;
  62
  63       struct hashentry *here = (struct hashentry *) (table->data + work);
  64
  65       if (type == here->type && len == here->len
  66           && memcmp (key, table->data + here->key, len) == 0
  67           && here->owner == owner)
  68         {
  69           /* We found the entry.  Increment the appropriate counter.  */
  70           struct datahead *dh
  71             = (struct datahead *) (table->data + here->packet);
  72
  73           /* See whether we must ignore the entry.  */
  74           if (dh->usable)
  75             {
  76               /* We do not synchronize the memory here.  The statistics
  77                  data is not crucial, we synchronize only once in a while
  78                  in the cleanup threads.  */
  79               if (dh->notfound)
  80                 ++table->head->neghit;
  81               else
  82                 {
  83                   ++table->head->poshit;
  84
  85                   if (dh->nreloads != 0)
  86                     dh->nreloads = 0;
  87                 }
  88
  89               result = dh;
  90               break;
  91             }
  92         }
  93
  94       work = here->next;
  95     }
  96
  97   if (nsearched > table->head->maxnsearched)
  98     table->head->maxnsearched = nsearched;
  99
 100   return result;
 101 }
 102
 103 /* Add a new entry to the cache.  The return value is zero if the function
 104    call was successful.
 105
 106    This function must be called with the read-lock held.
 107
 108    We modify the table but we nevertheless only acquire a read-lock.
 109    This is ok since we use operations which would be safe even without
 110    locking, given that the `prune_cache' function never runs.  Using
 111    the readlock reduces the chance of conflicts.  */
 112 int
 113 cache_add (int type, const void *key, size_t len, struct datahead *packet,
 114            bool first, struct database_dyn *table,
 115            uid_t owner)
 116 {
 117   if (__builtin_expect (debug_level >= 2, 0))
 118     dbg_log (_("add new entry \"%s\" of type %s for %s to cache%s"),
 119              (const char *) key, serv2str[type], dbnames[table - dbs],
 120              first ? " (first)" : "");
 121
 122   unsigned long int hash = __nis_hash (key, len) % table->head->module;
 123   struct hashentry *newp;
 124
 125   newp = mempool_alloc (table, sizeof (struct hashentry));
 126   /* If we cannot allocate memory, just do not do anything.  */
 127   if (newp == NULL)
 128     return -1;
 129
 130   newp->type = type;
 131   newp->first = first;
 132   newp->len = len;
 133   newp->key = (char *) key - table->data;
 134   assert (newp->key + newp->len <= table->head->first_free);
 135   newp->owner = owner;
 136   newp->packet = (char *) packet - table->data;
 137
 138   /* Put the new entry in the first position.  */
 139   do
 140     newp->next = table->head->array[hash];
 141   while (atomic_compare_and_exchange_bool_acq (&table->head->array[hash],
 142                                                (ref_t) ((char *) newp
 143                                                         - table->data),
 144                                                (ref_t) newp->next));
 145
 146   /* Update the statistics.  */
 147   if (packet->notfound)
 148     ++table->head->negmiss;
 149   else if (first)
 150     ++table->head->posmiss;
 151
 152   /* We depend on this value being correct and at least as high as the
 153      real number of entries.  */
 154   atomic_increment (&table->head->nentries);
 155
 156   /* It does not matter that we are not loading the just increment
 157      value, this is just for statistics.  */
 158   unsigned long int nentries = table->head->nentries;
 159   if (nentries > table->head->maxnentries)
 160     table->head->maxnentries = nentries;
 161
 162   return 0;
 163 }
 164
 165 /* Walk through the table and remove all entries which lifetime ended.
 166
 167    We have a problem here.  To actually remove the entries we must get
 168    the write-lock.  But since we want to keep the time we have the
 169    lock as short as possible we cannot simply acquire the lock when we
 170    start looking for timedout entries.
 171
 172    Therefore we do it in two stages: first we look for entries which
 173    must be invalidated and remember them.  Then we get the lock and
 174    actually remove them.  This is complicated by the way we have to
 175    free the data structures since some hash table entries share the same
 176    data.  */
 177 void
 178 prune_cache (struct database_dyn *table, time_t now)
 179 {
 180   size_t cnt = table->head->module;
 181
 182   /* If this table is not actually used don't do anything.  */
 183   if (cnt == 0)
 184     return;
 185
 186   /* If we check for the modification of the underlying file we invalidate
 187      the entries also in this case.  */
 188   if (table->check_file)
 189     {
 190       struct stat st;
 191
 192       if (stat (table->filename, &st) < 0)
 193         {
 194           char buf[128];
 195           /* We cannot stat() the file, disable file checking if the
 196              file does not exist.  */
 197           dbg_log (_("cannot stat() file `%s': %s"),
 198                    table->filename, strerror_r (errno, buf, sizeof (buf)));
 199           if (errno == ENOENT)
 200             table->check_file = 0;
 201         }
 202       else
 203         {
 204           if (st.st_mtime != table->file_mtime)
 205             {
 206               /* The file changed.  Invalidate all entries.  */
 207               now = LONG_MAX;
 208               table->file_mtime = st.st_mtime;
 209             }
 210         }
 211     }
 212
 213   /* We run through the table and find values which are not valid anymore.
 214
 215      Note that for the initial step, finding the entries to be removed,
 216      we don't need to get any lock.  It is at all timed assured that the
 217      linked lists are set up correctly and that no second thread prunes
 218      the cache.  */
 219   bool mark[cnt];
 220   size_t first = cnt + 1;
 221   size_t last = 0;
 222   char *const data = table->data;
 223   bool any = false;
 224
 225   do
 226     {
 227       ref_t run = table->head->array[--cnt];
 228
 229       while (run != ENDREF)
 230         {
 231           struct hashentry *runp = (struct hashentry *) (data + run);
 232           struct datahead *dh = (struct datahead *) (data + runp->packet);
 233
 234           /* Check whether the entry timed out.  */
 235           if (dh->timeout < now)
 236             {
 237               /* This hash bucket could contain entries which need to
 238                  be looked at.  */
 239               mark[cnt] = true;
 240
 241               first = MIN (first, cnt);
 242               last = MAX (last, cnt);
 243
 244               /* We only have to look at the data of the first entries
 245                  since the count information is kept in the data part
 246                  which is shared.  */
 247               if (runp->first)
 248                 {
 249
 250                   /* At this point there are two choices: we reload the
 251                      value or we discard it.  Do not change NRELOADS if
 252                      we never not reload the record.  */
 253                   if ((reload_count != UINT_MAX
 254                        && __builtin_expect (dh->nreloads >= reload_count, 0))
 255                       /* We always remove negative entries.  */
 256                       || dh->notfound
 257                       /* Discard everything if the user explicitly
 258                          requests it.  */
 259                       || now == LONG_MAX)
 260                     {
 261                       /* Remove the value.  */
 262                       dh->usable = false;
 263
 264                       /* We definitely have some garbage entries now.  */
 265                       any = true;
 266                     }
 267                   else
 268                     {
 269                       /* Reload the value.  We do this only for the
 270                          initially used key, not the additionally
 271                          added derived value.  */
 272                       switch (runp->type)
 273                         {
 274                         case GETPWBYNAME:
 275                           readdpwbyname (table, runp, dh);
 276                           break;
 277
 278                         case GETPWBYUID:
 279                           readdpwbyuid (table, runp, dh);
 280                           break;
 281
 282                         case GETGRBYNAME:
 283                           readdgrbyname (table, runp, dh);
 284                           break;
 285
 286                         case GETGRBYGID:
 287                           readdgrbygid (table, runp, dh);
 288                           break;
 289
 290                         case GETHOSTBYNAME:
 291                           readdhstbyname (table, runp, dh);
 292                           break;
 293
 294                         case GETHOSTBYNAMEv6:
 295                           readdhstbynamev6 (table, runp, dh);
 296                           break;
 297
 298                         case GETHOSTBYADDR:
 299                           readdhstbyaddr (table, runp, dh);
 300                           break;
 301
 302                         case GETHOSTBYADDRv6:
 303                           readdhstbyaddrv6 (table, runp, dh);
 304                           break;
 305
 306                         default:
 307                           assert (! "should never happen");
 308                         }
 309
 310                       /* If the entry has been replaced, we might need
 311                          cleanup.  */
 312                       any |= !dh->usable;
 313                     }
 314                 }
 315             }
 316           else
 317             assert (dh->usable);
 318
 319           run = runp->next;
 320         }
 321     }
 322   while (cnt > 0);
 323
 324   if (first <= last)
 325     {
 326       struct hashentry *head = NULL;
 327
 328       /* Now we have to get the write lock since we are about to modify
 329          the table.  */
 330       if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
 331         {
 332           ++table->head->wrlockdelayed;
 333           pthread_rwlock_wrlock (&table->lock);
 334         }
 335
 336       while (first <= last)
 337         {
 338           if (mark[first])
 339             {
 340               ref_t *old = &table->head->array[first];
 341               ref_t run = table->head->array[first];
 342
 343               while (run != ENDREF)
 344                 {
 345                   struct hashentry *runp = (struct hashentry *) (data + run);
 346                   struct datahead *dh
 347                     = (struct datahead *) (data + runp->packet);
 348
 349                   if (! dh->usable)
 350                     {
 351                       /* We need the list only for debugging but it is
 352                          more costly to avoid creating the list than
 353                          doing it.  */
 354                       runp->dellist = head;
 355                       head = runp;
 356
 357                       /* No need for an atomic operation, we have the
 358                          write lock.  */
 359                       --table->head->nentries;
 360
 361                       run = *old = runp->next;
 362                     }
 363                   else
 364                     {
 365                       old = &runp->next;
 366                       run = runp->next;
 367                     }
 368                 }
 369             }
 370
 371           ++first;
 372         }
 373
 374       /* It's all done.  */
 375       pthread_rwlock_unlock (&table->lock);
 376
 377       /* Make sure the data is saved to disk.  */
 378       if (table->persistent)
 379         msync (table->head,
 380                table->data + table->head->first_free - (char *) table->head,
 381                MS_ASYNC);
 382
 383       /* One extra pass if we do debugging.  */
 384       if (__builtin_expect (debug_level > 0, 0))
 385         {
 386           struct hashentry *runp = head;
 387
 388           while (runp != NULL)
 389             {
 390               char buf[INET6_ADDRSTRLEN];
 391               const char *str;
 392
 393               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
 394                 {
 395                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
 396                              table->data + runp->key, buf, sizeof (buf));
 397                   str = buf;
 398                 }
 399               else
 400                 str = table->data + runp->key;
 401
 402               dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
 403
 404               runp = runp->dellist;
 405             }
 406         }
 407     }
 408
 409   /* Run garbage collection if any entry has been removed or replaced.  */
 410   if (any)
 411     gc (table);
 412 }