nscd/cache.c

   1 /* Copyright (c) 1998, 1999, 2003, 2004, 2005 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     {
 119       const char *str;
 120       char buf[INET6_ADDRSTRLEN + 1];
 121       if (type == GETHOSTBYADDR || type == GETHOSTBYADDRv6)
 122         str = inet_ntop (type == GETHOSTBYADDR ? AF_INET : AF_INET6,
 123                          key, buf, sizeof (buf));
 124       else
 125         str = key;
 126
 127       dbg_log (_("add new entry \"%s\" of type %s for %s to cache%s"),
 128                str, serv2str[type], dbnames[table - dbs],
 129                first ? " (first)" : "");
 130     }
 131
 132   unsigned long int hash = __nis_hash (key, len) % table->head->module;
 133   struct hashentry *newp;
 134
 135   newp = mempool_alloc (table, sizeof (struct hashentry));
 136   /* If we cannot allocate memory, just do not do anything.  */
 137   if (newp == NULL)
 138     return -1;
 139
 140   newp->type = type;
 141   newp->first = first;
 142   newp->len = len;
 143   newp->key = (char *) key - table->data;
 144   assert (newp->key + newp->len <= table->head->first_free);
 145   newp->owner = owner;
 146   newp->packet = (char *) packet - table->data;
 147
 148   /* Put the new entry in the first position.  */
 149   do
 150     newp->next = table->head->array[hash];
 151   while (atomic_compare_and_exchange_bool_acq (&table->head->array[hash],
 152                                                (ref_t) ((char *) newp
 153                                                         - table->data),
 154                                                (ref_t) newp->next));
 155
 156   /* Update the statistics.  */
 157   if (packet->notfound)
 158     ++table->head->negmiss;
 159   else if (first)
 160     ++table->head->posmiss;
 161
 162   /* We depend on this value being correct and at least as high as the
 163      real number of entries.  */
 164   atomic_increment (&table->head->nentries);
 165
 166   /* It does not matter that we are not loading the just increment
 167      value, this is just for statistics.  */
 168   unsigned long int nentries = table->head->nentries;
 169   if (nentries > table->head->maxnentries)
 170     table->head->maxnentries = nentries;
 171
 172   if (table->persistent)
 173     // XXX async OK?
 174     msync ((void *) table->head,
 175            (char *) &table->head->array[hash] - (char *) table->head
 176            + sizeof (ref_t), MS_ASYNC);
 177
 178   return 0;
 179 }
 180
 181 /* Walk through the table and remove all entries which lifetime ended.
 182
 183    We have a problem here.  To actually remove the entries we must get
 184    the write-lock.  But since we want to keep the time we have the
 185    lock as short as possible we cannot simply acquire the lock when we
 186    start looking for timedout entries.
 187
 188    Therefore we do it in two stages: first we look for entries which
 189    must be invalidated and remember them.  Then we get the lock and
 190    actually remove them.  This is complicated by the way we have to
 191    free the data structures since some hash table entries share the same
 192    data.  */
 193 void
 194 prune_cache (struct database_dyn *table, time_t now)
 195 {
 196   size_t cnt = table->head->module;
 197
 198   /* If this table is not actually used don't do anything.  */
 199   if (cnt == 0)
 200     return;
 201
 202   /* If we check for the modification of the underlying file we invalidate
 203      the entries also in this case.  */
 204   if (table->check_file)
 205     {
 206       struct stat st;
 207
 208       if (stat (table->filename, &st) < 0)
 209         {
 210           char buf[128];
 211           /* We cannot stat() the file, disable file checking if the
 212              file does not exist.  */
 213           dbg_log (_("cannot stat() file `%s': %s"),
 214                    table->filename, strerror_r (errno, buf, sizeof (buf)));
 215           if (errno == ENOENT)
 216             table->check_file = 0;
 217         }
 218       else
 219         {
 220           if (st.st_mtime != table->file_mtime)
 221             {
 222               /* The file changed.  Invalidate all entries.  */
 223               now = LONG_MAX;
 224               table->file_mtime = st.st_mtime;
 225             }
 226         }
 227     }
 228
 229   /* We run through the table and find values which are not valid anymore.
 230
 231      Note that for the initial step, finding the entries to be removed,
 232      we don't need to get any lock.  It is at all timed assured that the
 233      linked lists are set up correctly and that no second thread prunes
 234      the cache.  */
 235   bool mark[cnt];
 236   size_t first = cnt + 1;
 237   size_t last = 0;
 238   char *const data = table->data;
 239   bool any = false;
 240
 241   do
 242     {
 243       ref_t run = table->head->array[--cnt];
 244
 245       while (run != ENDREF)
 246         {
 247           struct hashentry *runp = (struct hashentry *) (data + run);
 248           struct datahead *dh = (struct datahead *) (data + runp->packet);
 249
 250           /* Check whether the entry timed out.  */
 251           if (dh->timeout < now)
 252             {
 253               /* This hash bucket could contain entries which need to
 254                  be looked at.  */
 255               mark[cnt] = true;
 256
 257               first = MIN (first, cnt);
 258               last = MAX (last, cnt);
 259
 260               /* We only have to look at the data of the first entries
 261                  since the count information is kept in the data part
 262                  which is shared.  */
 263               if (runp->first)
 264                 {
 265
 266                   /* At this point there are two choices: we reload the
 267                      value or we discard it.  Do not change NRELOADS if
 268                      we never not reload the record.  */
 269                   if ((reload_count != UINT_MAX
 270                        && __builtin_expect (dh->nreloads >= reload_count, 0))
 271                       /* We always remove negative entries.  */
 272                       || dh->notfound
 273                       /* Discard everything if the user explicitly
 274                          requests it.  */
 275                       || now == LONG_MAX)
 276                     {
 277                       /* Remove the value.  */
 278                       dh->usable = false;
 279
 280                       /* We definitely have some garbage entries now.  */
 281                       any = true;
 282                     }
 283                   else
 284                     {
 285                       /* Reload the value.  We do this only for the
 286                          initially used key, not the additionally
 287                          added derived value.  */
 288                       switch (runp->type)
 289                         {
 290                         case GETPWBYNAME:
 291                           readdpwbyname (table, runp, dh);
 292                           break;
 293
 294                         case GETPWBYUID:
 295                           readdpwbyuid (table, runp, dh);
 296                           break;
 297
 298                         case GETGRBYNAME:
 299                           readdgrbyname (table, runp, dh);
 300                           break;
 301
 302                         case GETGRBYGID:
 303                           readdgrbygid (table, runp, dh);
 304                           break;
 305
 306                         case GETHOSTBYNAME:
 307                           readdhstbyname (table, runp, dh);
 308                           break;
 309
 310                         case GETHOSTBYNAMEv6:
 311                           readdhstbynamev6 (table, runp, dh);
 312                           break;
 313
 314                         case GETHOSTBYADDR:
 315                           readdhstbyaddr (table, runp, dh);
 316                           break;
 317
 318                         case GETHOSTBYADDRv6:
 319                           readdhstbyaddrv6 (table, runp, dh);
 320                           break;
 321
 322                         case GETAI:
 323                           readdhstai (table, runp, dh);
 324                           break;
 325
 326                         case INITGROUPS:
 327                           readdinitgroups (table, runp, dh);
 328                           break;
 329
 330                         default:
 331                           assert (! "should never happen");
 332                         }
 333
 334                       /* If the entry has been replaced, we might need
 335                          cleanup.  */
 336                       any |= !dh->usable;
 337                     }
 338                 }
 339             }
 340           else
 341             assert (dh->usable);
 342
 343           run = runp->next;
 344         }
 345     }
 346   while (cnt > 0);
 347
 348   if (first <= last)
 349     {
 350       struct hashentry *head = NULL;
 351
 352       /* Now we have to get the write lock since we are about to modify
 353          the table.  */
 354       if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
 355         {
 356           ++table->head->wrlockdelayed;
 357           pthread_rwlock_wrlock (&table->lock);
 358         }
 359
 360       while (first <= last)
 361         {
 362           if (mark[first])
 363             {
 364               ref_t *old = &table->head->array[first];
 365               ref_t run = table->head->array[first];
 366
 367               while (run != ENDREF)
 368                 {
 369                   struct hashentry *runp = (struct hashentry *) (data + run);
 370                   struct datahead *dh
 371                     = (struct datahead *) (data + runp->packet);
 372
 373                   if (! dh->usable)
 374                     {
 375                       /* We need the list only for debugging but it is
 376                          more costly to avoid creating the list than
 377                          doing it.  */
 378                       runp->dellist = head;
 379                       head = runp;
 380
 381                       /* No need for an atomic operation, we have the
 382                          write lock.  */
 383                       --table->head->nentries;
 384
 385                       run = *old = runp->next;
 386                     }
 387                   else
 388                     {
 389                       old = &runp->next;
 390                       run = runp->next;
 391                     }
 392                 }
 393             }
 394
 395           ++first;
 396         }
 397
 398       /* It's all done.  */
 399       pthread_rwlock_unlock (&table->lock);
 400
 401       /* Make sure the data is saved to disk.  */
 402       if (table->persistent)
 403         msync (table->head,
 404                table->data + table->head->first_free - (char *) table->head,
 405                MS_ASYNC);
 406
 407       /* One extra pass if we do debugging.  */
 408       if (__builtin_expect (debug_level > 0, 0))
 409         {
 410           struct hashentry *runp = head;
 411
 412           while (runp != NULL)
 413             {
 414               char buf[INET6_ADDRSTRLEN];
 415               const char *str;
 416
 417               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
 418                 {
 419                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
 420                              table->data + runp->key, buf, sizeof (buf));
 421                   str = buf;
 422                 }
 423               else
 424                 str = table->data + runp->key;
 425
 426               dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
 427
 428               runp = runp->dellist;
 429             }
 430         }
 431     }
 432
 433   /* Run garbage collection if any entry has been removed or replaced.  */
 434   if (any)
 435     gc (table);
 436 }