nscd/cache.c

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