nscd/cache.c

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