nscd/cache.c

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