(cache_add): Take additional parameter specifying
[kopensolaris-gnu/glibc.git] / nscd / cache.c
index 6492092..2faaf34 100644 (file)
@@ -1,31 +1,33 @@
-/* Copyright (c) 1998, 1999, 2003 Free Software Foundation, Inc.
+/* Copyright (c) 1998, 1999, 2003-2007, 2008 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1998.
 
-   The GNU C Library is free software; you can redistribute it and/or
-   modify it under the terms of the GNU Lesser General Public
-   License as published by the Free Software Foundation; either
-   version 2.1 of the License, or (at your option) any later version.
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published
+   by the Free Software Foundation; version 2 of the License, or
+   (at your option) any later version.
 
-   The GNU C Library is distributed in the hope that it will be useful,
+   This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   Lesser General Public License for more details.
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
 
-   You should have received a copy of the GNU Lesser General Public
-   License along with the GNU C Library; if not, write to the Free
-   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
-   02111-1307 USA.  */
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
+#include <assert.h>
 #include <atomic.h>
 #include <errno.h>
 #include <error.h>
+#include <inttypes.h>
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
 #include <libintl.h>
 #include <arpa/inet.h>
 #include <rpcsvc/nis.h>
+#include <sys/mman.h>
 #include <sys/param.h>
 #include <sys/stat.h>
 #include <sys/uio.h>
 #include "nscd.h"
 #include "dbg_log.h"
 
+
+/* Wrapper functions with error checking for standard functions.  */
+extern void *xcalloc (size_t n, size_t s);
+
+
+/* Number of times a value is reloaded without being used.  UINT_MAX
+   means unlimited.  */
+unsigned int reload_count = DEFAULT_RELOAD_LIMIT;
+
+
+static void (*const readdfcts[LASTREQ]) (struct database_dyn *,
+                                        struct hashentry *,
+                                        struct datahead *) =
+{
+  [GETPWBYNAME] = readdpwbyname,
+  [GETPWBYUID] = readdpwbyuid,
+  [GETGRBYNAME] = readdgrbyname,
+  [GETGRBYGID] = readdgrbygid,
+  [GETHOSTBYNAME] = readdhstbyname,
+  [GETHOSTBYNAMEv6] = readdhstbynamev6,
+  [GETHOSTBYADDR] = readdhstbyaddr,
+  [GETHOSTBYADDRv6] = readdhstbyaddrv6,
+  [GETAI] = readdhstai,
+  [INITGROUPS] = readdinitgroups,
+  [GETSERVBYNAME] = readdservbyname,
+  [GETSERVBYPORT] = readdservbyport
+};
+
+
 /* Search the cache for a matching entry and return it when found.  If
    this fails search the negative cache and return (void *) -1 if this
    search was successful.  Otherwise return NULL.
 
    This function must be called with the read-lock held.  */
-struct hashentry *
-cache_search (request_type type, void *key, size_t len, struct database *table,
-             uid_t owner)
+struct datahead *
+cache_search (request_type type, void *key, size_t len,
+             struct database_dyn *table, uid_t owner)
 {
-  unsigned long int hash = __nis_hash (key, len) % table->module;
-  struct hashentry *work;
+  unsigned long int hash = __nis_hash (key, len) % table->head->module;
 
-  work = table->array[hash];
+  unsigned long int nsearched = 0;
+  struct datahead *result = NULL;
 
-  while (work != NULL)
+  ref_t work = table->head->array[hash];
+  while (work != ENDREF)
     {
-      if (type == work->type && len == work->len
-         && memcmp (key, work->key, len) == 0 && work->owner == owner)
+      ++nsearched;
+
+      struct hashentry *here = (struct hashentry *) (table->data + work);
+
+      if (type == here->type && len == here->len
+         && memcmp (key, table->data + here->key, len) == 0
+         && here->owner == owner)
        {
          /* We found the entry.  Increment the appropriate counter.  */
-         if (work->data == (void *) -1)
-           ++table->neghit;
-         else
-           ++table->poshit;
+         struct datahead *dh
+           = (struct datahead *) (table->data + here->packet);
 
-         return work;
+         /* See whether we must ignore the entry.  */
+         if (dh->usable)
+           {
+             /* We do not synchronize the memory here.  The statistics
+                data is not crucial, we synchronize only once in a while
+                in the cleanup threads.  */
+             if (dh->notfound)
+               ++table->head->neghit;
+             else
+               {
+                 ++table->head->poshit;
+
+                 if (dh->nreloads != 0)
+                   dh->nreloads = 0;
+               }
+
+             result = dh;
+             break;
+           }
        }
 
-      work = work->next;
+      work = here->next;
     }
 
-  return NULL;
+  if (nsearched > table->head->maxnsearched)
+    table->head->maxnsearched = nsearched;
+
+  return result;
 }
 
 /* Add a new entry to the cache.  The return value is zero if the function
@@ -76,39 +132,113 @@ cache_search (request_type type, void *key, size_t len, struct database *table,
    This is ok since we use operations which would be safe even without
    locking, given that the `prune_cache' function never runs.  Using
    the readlock reduces the chance of conflicts.  */
-void
-cache_add (int type, void *key, size_t len, const void *packet, size_t total,
-          void *data, int last, time_t t, struct database *table, uid_t owner)
+int
+cache_add (int type, const void *key, size_t len, struct datahead *packet,
+          bool first, struct database_dyn *table,
+          uid_t owner, bool prune_wakeup)
 {
-  unsigned long int hash = __nis_hash (key, len) % table->module;
+  if (__builtin_expect (debug_level >= 2, 0))
+    {
+      const char *str;
+      char buf[INET6_ADDRSTRLEN + 1];
+      if (type == GETHOSTBYADDR || type == GETHOSTBYADDRv6)
+       str = inet_ntop (type == GETHOSTBYADDR ? AF_INET : AF_INET6,
+                        key, buf, sizeof (buf));
+      else
+       str = key;
+
+      dbg_log (_("add new entry \"%s\" of type %s for %s to cache%s"),
+              str, serv2str[type], dbnames[table - dbs],
+              first ? _(" (first)") : "");
+    }
+
+  unsigned long int hash = __nis_hash (key, len) % table->head->module;
   struct hashentry *newp;
 
-  newp = malloc (sizeof (struct hashentry));
+  newp = mempool_alloc (table, sizeof (struct hashentry), IDX_record_data);
+  /* If we cannot allocate memory, just do not do anything.  */
   if (newp == NULL)
-    error (EXIT_FAILURE, errno, _("while allocating hash table entry"));
+    {
+      ++table->head->addfailed;
+
+      /* If necessary mark the entry as unusable so that lookups will
+        not use it.  */
+      if (first)
+       packet->usable = false;
+
+      /* Mark the in-flight memory as unused.  */
+      for (enum in_flight idx = 0; idx < IDX_record_data; ++idx)
+       mem_in_flight.block[idx].dbidx = -1;
+
+      return -1;
+    }
 
   newp->type = type;
+  newp->first = first;
   newp->len = len;
-  newp->key = key;
+  newp->key = (char *) key - table->data;
+  assert (newp->key + newp->len <= table->head->first_free);
   newp->owner = owner;
-  newp->data = data;
-  newp->timeout = t;
-  newp->packet = packet;
-  newp->total = total;
-
-  newp->last = last;
+  newp->packet = (char *) packet - table->data;
+  assert ((newp->packet & BLOCK_ALIGN_M1) == 0);
 
   /* Put the new entry in the first position.  */
   do
-    newp->next = table->array[hash];
-  while (atomic_compare_and_exchange_bool_acq (&table->array[hash], newp,
-                                              newp->next));
+    newp->next = table->head->array[hash];
+  while (atomic_compare_and_exchange_bool_acq (&table->head->array[hash],
+                                              (ref_t) ((char *) newp
+                                                       - table->data),
+                                              (ref_t) newp->next));
 
   /* Update the statistics.  */
-  if (data == (void *) -1)
-    ++table->negmiss;
-  else if (last)
-    ++table->posmiss;
+  if (packet->notfound)
+    ++table->head->negmiss;
+  else if (first)
+    ++table->head->posmiss;
+
+  /* We depend on this value being correct and at least as high as the
+     real number of entries.  */
+  atomic_increment (&table->head->nentries);
+
+  /* It does not matter that we are not loading the just increment
+     value, this is just for statistics.  */
+  unsigned long int nentries = table->head->nentries;
+  if (nentries > table->head->maxnentries)
+    table->head->maxnentries = nentries;
+
+  if (table->persistent)
+    // XXX async OK?
+    msync ((void *) table->head,
+          (char *) &table->head->array[hash] - (char *) table->head
+          + sizeof (ref_t), MS_ASYNC);
+
+  /* We do not have to worry about the pruning thread if we are
+     re-adding the data since this is done by the pruning thread.  We
+     also do not have to do anything in case this is not the first
+     time the data is entered since different data heads all have the
+     same timeout.  */
+  if (first && prune_wakeup)
+    {
+      /* Perhaps the prune thread for the table is not running in a long
+        time.  Wake it if necessary.  */
+      pthread_mutex_lock (&table->prune_lock);
+      time_t next_wakeup = table->wakeup_time;
+      bool do_wakeup = false;
+      if (next_wakeup > packet->timeout + CACHE_PRUNE_INTERVAL)
+       {
+         table->wakeup_time = packet->timeout;
+         do_wakeup = true;
+       }
+      pthread_mutex_unlock (&table->prune_lock);
+      if (do_wakeup)
+       pthread_cond_signal (&table->prune_cond);
+    }
+
+  /* Mark the in-flight memory as unused.  */
+  for (enum in_flight idx = 0; idx < IDX_last; ++idx)
+    mem_in_flight.block[idx].dbidx = -1;
+
+  return 0;
 }
 
 /* Walk through the table and remove all entries which lifetime ended.
@@ -123,26 +253,32 @@ cache_add (int type, void *key, size_t len, const void *packet, size_t total,
    actually remove them.  This is complicated by the way we have to
    free the data structures since some hash table entries share the same
    data.  */
-void
-prune_cache (struct database *table, time_t now)
+time_t
+prune_cache (struct database_dyn *table, time_t now, int fd)
 {
-  size_t cnt = table->module;
-  int mark[cnt];
-  int anything = 0;
-  size_t first = cnt + 1;
-  size_t last = 0;
+  size_t cnt = table->head->module;
 
   /* If this table is not actually used don't do anything.  */
   if (cnt == 0)
-    return;
+    {
+      if (fd != -1)
+       {
+         /* Reply to the INVALIDATE initiator.  */
+         int32_t resp = 0;
+         writeall (fd, &resp, sizeof (resp));
+       }
+
+      /* No need to do this again anytime soon.  */
+      return 24 * 60 * 60;
+    }
 
   /* If we check for the modification of the underlying file we invalidate
      the entries also in this case.  */
-  if (table->check_file)
+  if (table->check_file && now != LONG_MAX)
     {
-      struct stat st;
+      struct stat64 st;
 
-      if (stat (table->filename, &st) < 0)
+      if (stat64 (table->filename, &st) < 0)
        {
          char buf[128];
          /* We cannot stat() the file, disable file checking if the
@@ -165,107 +301,226 @@ prune_cache (struct database *table, time_t now)
 
   /* We run through the table and find values which are not valid anymore.
 
-   Note that for the initial step, finding the entries to be removed,
-   we don't need to get any lock.  It is at all timed assured that the
-   linked lists are set up correctly and that no second thread prunes
-   the cache.  */
-  do
+     Note that for the initial step, finding the entries to be removed,
+     we don't need to get any lock.  It is at all timed assured that the
+     linked lists are set up correctly and that no second thread prunes
+     the cache.  */
+  bool *mark;
+  size_t memory_needed = cnt * sizeof (bool);
+  bool mark_use_alloca;
+  if (__builtin_expect (memory_needed <= MAX_STACK_USE, 1))
     {
-      struct hashentry *runp = table->array[--cnt];
+      mark = alloca (cnt * sizeof (bool));
+      memset (mark, '\0', memory_needed);
+      mark_use_alloca = true;
+    }
+  else
+    {
+      mark = xcalloc (1, memory_needed);
+      mark_use_alloca = false;
+    }
+  size_t first = cnt + 1;
+  size_t last = 0;
+  char *const data = table->data;
+  bool any = false;
 
-      mark[cnt] = 0;
+  if (__builtin_expect (debug_level > 2, 0))
+    dbg_log (_("pruning %s cache; time %ld"),
+            dbnames[table - dbs], (long int) now);
 
-      while (runp != NULL)
+#define NO_TIMEOUT LONG_MAX
+  time_t next_timeout = NO_TIMEOUT;
+  do
+    {
+      ref_t run = table->head->array[--cnt];
+
+      while (run != ENDREF)
        {
-         if (runp->timeout < now)
+         struct hashentry *runp = (struct hashentry *) (data + run);
+         struct datahead *dh = (struct datahead *) (data + runp->packet);
+
+         /* Some debug support.  */
+         if (__builtin_expect (debug_level > 2, 0))
            {
-             ++mark[cnt];
-             anything = 1;
+             char buf[INET6_ADDRSTRLEN];
+             const char *str;
+
+             if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
+               {
+                 inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
+                            data + runp->key, buf, sizeof (buf));
+                 str = buf;
+               }
+             else
+               str = data + runp->key;
+
+             dbg_log (_("considering %s entry \"%s\", timeout %" PRIu64),
+                      serv2str[runp->type], str, dh->timeout);
+           }
+
+         /* Check whether the entry timed out.  */
+         if (dh->timeout < now)
+           {
+             /* This hash bucket could contain entries which need to
+                be looked at.  */
+             mark[cnt] = true;
+
              first = MIN (first, cnt);
              last = MAX (last, cnt);
+
+             /* We only have to look at the data of the first entries
+                since the count information is kept in the data part
+                which is shared.  */
+             if (runp->first)
+               {
+
+                 /* At this point there are two choices: we reload the
+                    value or we discard it.  Do not change NRELOADS if
+                    we never not reload the record.  */
+                 if ((reload_count != UINT_MAX
+                      && __builtin_expect (dh->nreloads >= reload_count, 0))
+                     /* We always remove negative entries.  */
+                     || dh->notfound
+                     /* Discard everything if the user explicitly
+                        requests it.  */
+                     || now == LONG_MAX)
+                   {
+                     /* Remove the value.  */
+                     dh->usable = false;
+
+                     /* We definitely have some garbage entries now.  */
+                     any = true;
+                   }
+                 else
+                   {
+                     /* Reload the value.  We do this only for the
+                        initially used key, not the additionally
+                        added derived value.  */
+                     assert (runp->type < LASTREQ
+                             && readdfcts[runp->type] != NULL);
+
+                     readdfcts[runp->type] (table, runp, dh);
+
+                     /* If the entry has been replaced, we might need
+                        cleanup.  */
+                     any |= !dh->usable;
+                   }
+               }
+           }
+         else
+           {
+             assert (dh->usable);
+             next_timeout = MIN (next_timeout, dh->timeout);
            }
-         runp = runp->next;
+
+         run = runp->next;
        }
     }
   while (cnt > 0);
 
-  if (anything)
+  if (__builtin_expect (fd != -1, 0))
+    {
+      /* Reply to the INVALIDATE initiator that the cache has been
+        invalidated.  */
+      int32_t resp = 0;
+      writeall (fd, &resp, sizeof (resp));
+    }
+
+  if (first <= last)
     {
       struct hashentry *head = NULL;
 
       /* Now we have to get the write lock since we are about to modify
         the table.  */
-      pthread_rwlock_wrlock (&table->lock);
+      if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
+       {
+         ++table->head->wrlockdelayed;
+         pthread_rwlock_wrlock (&table->lock);
+       }
 
       while (first <= last)
        {
-         if (mark[first] > 0)
+         if (mark[first])
            {
-             struct hashentry *runp;
+             ref_t *old = &table->head->array[first];
+             ref_t run = table->head->array[first];
 
-             while (table->array[first]->timeout < now)
+             assert (run != ENDREF);
+             do
                {
-                 table->array[first]->dellist = head;
-                 head = table->array[first];
-                 table->array[first] = head->next;
-                 if (--mark[first] == 0)
-                   break;
-               }
+                 struct hashentry *runp = (struct hashentry *) (data + run);
+                 struct datahead *dh
+                   = (struct datahead *) (data + runp->packet);
 
-             runp = table->array[first];
-             while (mark[first] > 0)
-               {
-                 if (runp->next->timeout < now)
+                 if (! dh->usable)
                    {
-                     runp->next->dellist = head;
-                     head = runp->next;
-                     runp->next = head->next;
-                     --mark[first];
+                     /* We need the list only for debugging but it is
+                        more costly to avoid creating the list than
+                        doing it.  */
+                     runp->dellist = head;
+                     head = runp;
+
+                     /* No need for an atomic operation, we have the
+                        write lock.  */
+                     --table->head->nentries;
+
+                     run = *old = runp->next;
                    }
                  else
-                   runp = runp->next;
+                   {
+                     old = &runp->next;
+                     run = runp->next;
+                   }
                }
+             while (run != ENDREF);
            }
+
          ++first;
        }
 
       /* It's all done.  */
       pthread_rwlock_unlock (&table->lock);
 
-      /* And another run to free the data.  */
-      do
+      /* Make sure the data is saved to disk.  */
+      if (table->persistent)
+       msync (table->head,
+              data + table->head->first_free - (char *) table->head,
+              MS_ASYNC);
+
+      /* One extra pass if we do debugging.  */
+      if (__builtin_expect (debug_level > 0, 0))
        {
-         struct hashentry *old = head;
+         struct hashentry *runp = head;
 
-         if (debug_level > 0)
+         while (runp != NULL)
            {
              char buf[INET6_ADDRSTRLEN];
              const char *str;
 
-             if ((old->type == GETHOSTBYADDR || old->type == GETHOSTBYADDRv6)
-                 && (old->last || old->data == (void *) -1))
+             if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
                {
-                 inet_ntop (old->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
-                            old->key, buf, sizeof (buf));
+                 inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
+                            data + runp->key, buf, sizeof (buf));
                  str = buf;
                }
              else
-               str = old->last ? old->key : (old->data == (void *) -1
-                                             ? old->key : "???");
+               str = data + runp->key;
+
+             dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
 
-             dbg_log ("remove %s entry \"%s\"", serv2str[old->type], str);
+             runp = runp->dellist;
            }
+       }
+    }
 
-         /* Free the data structures.  */
-         if (old->data == (void *) -1)
-           free (old->key);
-         else if (old->last)
-           free (old->data);
+  if (__builtin_expect (! mark_use_alloca, 0))
+    free (mark);
 
-         head = head->dellist;
+  /* Run garbage collection if any entry has been removed or replaced.  */
+  if (any)
+    gc (table);
 
-         free (old);
-       }
-      while (head != NULL);
-    }
+  /* If there is no entry in the database and we therefore have no new
+     timeout value, tell the caller to wake up in 24 hours.  */
+  return next_timeout == NO_TIMEOUT ? 24 * 60 * 60 : next_timeout - now;
 }