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