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: }