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