nscd/cache.c

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