nscd/cache.c

   1 /* Copyright (c) 1998, 1999, 2003-2007, 2008 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), IDX_record_data);
 159   /* If we cannot allocate memory, just do not do anything.  */
 160   if (newp == NULL)
 161     {
 162       ++table->head->addfailed;
 163
 164       /* Mark the in-flight memory as unused.  */
 165       for (enum in_flight idx = 0; idx < IDX_record_data; ++idx)
 166         mem_in_flight.block[idx].dbidx = -1;
 167
 168       return -1;
 169     }
 170
 171   newp->type = type;
 172   newp->first = first;
 173   newp->len = len;
 174   newp->key = (char *) key - table->data;
 175   assert (newp->key + newp->len <= table->head->first_free);
 176   newp->owner = owner;
 177   newp->packet = (char *) packet - table->data;
 178
 179   /* Put the new entry in the first position.  */
 180   do
 181     newp->next = table->head->array[hash];
 182   while (atomic_compare_and_exchange_bool_acq (&table->head->array[hash],
 183                                                (ref_t) ((char *) newp
 184                                                         - table->data),
 185                                                (ref_t) newp->next));
 186
 187   /* Update the statistics.  */
 188   if (packet->notfound)
 189     ++table->head->negmiss;
 190   else if (first)
 191     ++table->head->posmiss;
 192
 193   /* We depend on this value being correct and at least as high as the
 194      real number of entries.  */
 195   atomic_increment (&table->head->nentries);
 196
 197   /* It does not matter that we are not loading the just increment
 198      value, this is just for statistics.  */
 199   unsigned long int nentries = table->head->nentries;
 200   if (nentries > table->head->maxnentries)
 201     table->head->maxnentries = nentries;
 202
 203   if (table->persistent)
 204     // XXX async OK?
 205     msync ((void *) table->head,
 206            (char *) &table->head->array[hash] - (char *) table->head
 207            + sizeof (ref_t), MS_ASYNC);
 208
 209   /* Perhaps the prune thread for the data is not running in a long
 210      time.  Wake it if necessary.  */
 211   time_t next_wakeup = table->wakeup_time;
 212   while (next_wakeup + CACHE_PRUNE_INTERVAL > packet->timeout)
 213     if (atomic_compare_and_exchange_bool_acq (&table->wakeup_time,
 214                                               packet->timeout,
 215                                               next_wakeup) == 0)
 216       {
 217         pthread_cond_signal (&table->prune_cond);
 218         break;
 219       }
 220     else
 221       next_wakeup = table->wakeup_time;
 222
 223   /* Mark the in-flight memory as unused.  */
 224   for (enum in_flight idx = 0; idx < IDX_last; ++idx)
 225     mem_in_flight.block[idx].dbidx = -1;
 226
 227   return 0;
 228 }
 229
 230 /* Walk through the table and remove all entries which lifetime ended.
 231
 232    We have a problem here.  To actually remove the entries we must get
 233    the write-lock.  But since we want to keep the time we have the
 234    lock as short as possible we cannot simply acquire the lock when we
 235    start looking for timedout entries.
 236
 237    Therefore we do it in two stages: first we look for entries which
 238    must be invalidated and remember them.  Then we get the lock and
 239    actually remove them.  This is complicated by the way we have to
 240    free the data structures since some hash table entries share the same
 241    data.  */
 242 time_t
 243 prune_cache (struct database_dyn *table, time_t now, int fd)
 244 {
 245   size_t cnt = table->head->module;
 246
 247   /* If this table is not actually used don't do anything.  */
 248   if (cnt == 0)
 249     {
 250       if (fd != -1)
 251         {
 252           /* Reply to the INVALIDATE initiator.  */
 253           int32_t resp = 0;
 254           writeall (fd, &resp, sizeof (resp));
 255         }
 256
 257       /* No need to do this again anytime soon.  */
 258       return 24 * 60 * 60;
 259     }
 260
 261   /* If we check for the modification of the underlying file we invalidate
 262      the entries also in this case.  */
 263   if (table->check_file && now != LONG_MAX)
 264     {
 265       struct stat64 st;
 266
 267       if (stat64 (table->filename, &st) < 0)
 268         {
 269           char buf[128];
 270           /* We cannot stat() the file, disable file checking if the
 271              file does not exist.  */
 272           dbg_log (_("cannot stat() file `%s': %s"),
 273                    table->filename, strerror_r (errno, buf, sizeof (buf)));
 274           if (errno == ENOENT)
 275             table->check_file = 0;
 276         }
 277       else
 278         {
 279           if (st.st_mtime != table->file_mtime)
 280             {
 281               /* The file changed.  Invalidate all entries.  */
 282               now = LONG_MAX;
 283               table->file_mtime = st.st_mtime;
 284             }
 285         }
 286     }
 287
 288   /* We run through the table and find values which are not valid anymore.
 289
 290      Note that for the initial step, finding the entries to be removed,
 291      we don't need to get any lock.  It is at all timed assured that the
 292      linked lists are set up correctly and that no second thread prunes
 293      the cache.  */
 294   bool *mark;
 295   size_t memory_needed = cnt * sizeof (bool);
 296   bool mark_use_alloca;
 297   if (__builtin_expect (memory_needed <= MAX_STACK_USE, 1))
 298     {
 299       mark = alloca (cnt * sizeof (bool));
 300       memset (mark, '\0', memory_needed);
 301       mark_use_alloca = true;
 302     }
 303   else
 304     {
 305       mark = xcalloc (1, memory_needed);
 306       mark_use_alloca = false;
 307     }
 308   size_t first = cnt + 1;
 309   size_t last = 0;
 310   char *const data = table->data;
 311   bool any = false;
 312
 313   if (__builtin_expect (debug_level > 2, 0))
 314     dbg_log (_("pruning %s cache; time %ld"),
 315              dbnames[table - dbs], (long int) now);
 316
 317 #define NO_TIMEOUT LONG_MAX
 318   time_t next_timeout = NO_TIMEOUT;
 319   do
 320     {
 321       ref_t run = table->head->array[--cnt];
 322
 323       while (run != ENDREF)
 324         {
 325           struct hashentry *runp = (struct hashentry *) (data + run);
 326           struct datahead *dh = (struct datahead *) (data + runp->packet);
 327
 328           /* Some debug support.  */
 329           if (__builtin_expect (debug_level > 2, 0))
 330             {
 331               char buf[INET6_ADDRSTRLEN];
 332               const char *str;
 333
 334               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
 335                 {
 336                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
 337                              data + runp->key, buf, sizeof (buf));
 338                   str = buf;
 339                 }
 340               else
 341                 str = data + runp->key;
 342
 343               dbg_log (_("considering %s entry \"%s\", timeout %" PRIu64),
 344                        serv2str[runp->type], str, dh->timeout);
 345             }
 346
 347           /* Check whether the entry timed out.  */
 348           if (dh->timeout < now)
 349             {
 350               /* This hash bucket could contain entries which need to
 351                  be looked at.  */
 352               mark[cnt] = true;
 353
 354               first = MIN (first, cnt);
 355               last = MAX (last, cnt);
 356
 357               /* We only have to look at the data of the first entries
 358                  since the count information is kept in the data part
 359                  which is shared.  */
 360               if (runp->first)
 361                 {
 362
 363                   /* At this point there are two choices: we reload the
 364                      value or we discard it.  Do not change NRELOADS if
 365                      we never not reload the record.  */
 366                   if ((reload_count != UINT_MAX
 367                        && __builtin_expect (dh->nreloads >= reload_count, 0))
 368                       /* We always remove negative entries.  */
 369                       || dh->notfound
 370                       /* Discard everything if the user explicitly
 371                          requests it.  */
 372                       || now == LONG_MAX)
 373                     {
 374                       /* Remove the value.  */
 375                       dh->usable = false;
 376
 377                       /* We definitely have some garbage entries now.  */
 378                       any = true;
 379                     }
 380                   else
 381                     {
 382                       /* Reload the value.  We do this only for the
 383                          initially used key, not the additionally
 384                          added derived value.  */
 385                       assert (runp->type < LASTREQ
 386                               && readdfcts[runp->type] != NULL);
 387
 388                       readdfcts[runp->type] (table, runp, dh);
 389
 390                       /* If the entry has been replaced, we might need
 391                          cleanup.  */
 392                       any |= !dh->usable;
 393                     }
 394                 }
 395             }
 396           else
 397             {
 398               assert (dh->usable);
 399               next_timeout = MIN (next_timeout, dh->timeout);
 400             }
 401
 402           run = runp->next;
 403         }
 404     }
 405   while (cnt > 0);
 406
 407   if (__builtin_expect (fd != -1, 0))
 408     {
 409       /* Reply to the INVALIDATE initiator that the cache has been
 410          invalidated.  */
 411       int32_t resp = 0;
 412       writeall (fd, &resp, sizeof (resp));
 413     }
 414
 415   if (first <= last)
 416     {
 417       struct hashentry *head = NULL;
 418
 419       /* Now we have to get the write lock since we are about to modify
 420          the table.  */
 421       if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
 422         {
 423           ++table->head->wrlockdelayed;
 424           pthread_rwlock_wrlock (&table->lock);
 425         }
 426
 427       while (first <= last)
 428         {
 429           if (mark[first])
 430             {
 431               ref_t *old = &table->head->array[first];
 432               ref_t run = table->head->array[first];
 433
 434               while (run != ENDREF)
 435                 {
 436                   struct hashentry *runp = (struct hashentry *) (data + run);
 437                   struct datahead *dh
 438                     = (struct datahead *) (data + runp->packet);
 439
 440                   if (! dh->usable)
 441                     {
 442                       /* We need the list only for debugging but it is
 443                          more costly to avoid creating the list than
 444                          doing it.  */
 445                       runp->dellist = head;
 446                       head = runp;
 447
 448                       /* No need for an atomic operation, we have the
 449                          write lock.  */
 450                       --table->head->nentries;
 451
 452                       run = *old = runp->next;
 453                     }
 454                   else
 455                     {
 456                       old = &runp->next;
 457                       run = runp->next;
 458                     }
 459                 }
 460             }
 461
 462           ++first;
 463         }
 464
 465       /* It's all done.  */
 466       pthread_rwlock_unlock (&table->lock);
 467
 468       /* Make sure the data is saved to disk.  */
 469       if (table->persistent)
 470         msync (table->head,
 471                data + table->head->first_free - (char *) table->head,
 472                MS_ASYNC);
 473
 474       /* One extra pass if we do debugging.  */
 475       if (__builtin_expect (debug_level > 0, 0))
 476         {
 477           struct hashentry *runp = head;
 478
 479           while (runp != NULL)
 480             {
 481               char buf[INET6_ADDRSTRLEN];
 482               const char *str;
 483
 484               if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
 485                 {
 486                   inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
 487                              data + runp->key, buf, sizeof (buf));
 488                   str = buf;
 489                 }
 490               else
 491                 str = data + runp->key;
 492
 493               dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
 494
 495               runp = runp->dellist;
 496             }
 497         }
 498     }
 499
 500   if (__builtin_expect (! mark_use_alloca, 0))
 501     free (mark);
 502
 503   /* Run garbage collection if any entry has been removed or replaced.  */
 504   if (any)
 505     gc (table);
 506
 507   /* If there is no entry in the database and we therefore have no new
 508      timeout value, tell the caller to wake up in 24 hours.  */
 509   return next_timeout == NO_TIMEOUT ? 24 * 60 * 60 : next_timeout - now;
 510 }