Update.

2004-08-26  Ulrich Drepper  <drepper@redhat.com>

	* nscd/cache.c: Major rewrite.  The data is now optionally kept in
	a mmaped memory region which is automatically mirrored on disk.
	This implements persistent data storage.  The Memory handled
	needed to be completely revamped, it now uses a garbage collection
	mechanism instead of malloc.
	* nscd/connections.c: Likewise.
	* nscd/nscd.c: Likewise.
	* nscd/nscd.h: Likewise.
	* nscd/nscd_conf.c: Likewise.
	* nscd/nscd_stat.c: Likewise.
	* nscd/grpcache.c: Likewise.
	* nscd/hstcache.c:: Likewise.
	* nscd/pwdcache.c:: Likewise.
	* nscd/Makefile: Add rules to build mem.c.
	* nscd/mem.c: New file.
	* nscd/nscd.conf: Describe new configuration options.

13 files changed, 2366 insertions, 813 deletions

diff --git a/nscd/Makefile b/nscd/Makefile
index 7392e71509..cb82a2e06f 100644
--- a/nscd/Makefile
+++ b/nscd/Makefile
@@ -1,4 +1,4 @@
-# Copyright (C) 1998, 2000, 2002, 2003 Free Software Foundation, Inc.
+# Copyright (C) 1998, 2000, 2002, 2003, 2004 Free Software Foundation, Inc.
 # This file is part of the GNU C Library.
 
 # The GNU C Library is free software; you can redistribute it and/or
@@ -30,7 +30,7 @@ vpath %.c ../locale/programs
 
 nscd-modules := nscd connections pwdcache getpwnam_r getpwuid_r grpcache \
 		getgrnam_r getgrgid_r hstcache gethstbyad_r gethstbynm2_r \
-		dbg_log nscd_conf nscd_stat cache xmalloc xstrdup
+		dbg_log nscd_conf nscd_stat cache mem xmalloc xstrdup
 
 ifeq ($(have-thread-library),yes)
 
@@ -78,6 +78,7 @@ CFLAGS-nscd_stat.c = -fpie
 CFLAGS-cache.c = -fpie
 CFLAGS-xmalloc.c = -fpie
 CFLAGS-xstrdup.c = -fpie
+CFLAGS-mem.c = -fpie
 
 $(objpfx)nscd: $(addprefix $(objpfx),$(nscd-modules:=.o))
 	$(LINK.o) -pie -Wl,-O1 \
diff --git a/nscd/cache.c b/nscd/cache.c
index 446154880a..2d50d7794c 100644
--- a/nscd/cache.c
+++ b/nscd/cache.c
@@ -17,6 +17,7 @@
    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>
@@ -26,6 +27,7 @@
 #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>
@@ -33,44 +35,69 @@
 #include "nscd.h"
 #include "dbg_log.h"
 
+
+/* Number of times a value is reloaded without being used.  UINT_MAX
+   means unlimited.  */
+unsigned int reload_count = DEFAULT_RELOAD_LIMIT;
+
+
 /* 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 nsearched = 0;
+  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)
     {
       ++nsearched;
 
-      if (type == work->type && len == work->len
-	  && memcmp (key, work->key, len) == 0 && work->owner == owner)
+      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);
+
+	  /* 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;
+		}
 
-	  break;
+	      result = dh;
+	      break;
+	    }
 	}
 
-      work = work->next;
+      work = here->next;
     }
 
-  if (nsearched > table->maxnsearched)
-    table->maxnsearched = nsearched;
+  if (nsearched > table->head->maxnsearched)
+    table->head->maxnsearched = nsearched;
 
-  return work;
+  return result;
 }
 
 /* Add a new entry to the cache.  The return value is zero if the function
@@ -82,45 +109,57 @@ 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)
 {
-  unsigned long int hash = __nis_hash (key, len) % table->module;
+  if (__builtin_expect (debug_level >= 2, 0))
+    dbg_log (_("add new entry \"%s\" of type %s for %s to cache%s"),
+	     (const char *) key, 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));
+  /* If we cannot allocate memory, just do not do anything.  */
   if (newp == NULL)
-    error (EXIT_FAILURE, errno, _("while allocating hash table entry"));
+    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;
 
   /* 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;
-
-  /* Instead of slowing down the normal process for statistics
-     collection we accept living with some incorrect data.  */
-  unsigned long int nentries = ++table->nentries;
-  if (nentries > table->maxnentries)
-    table->maxnentries = nentries;
+  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;
+
+  return 0;
 }
 
 /* Walk through the table and remove all entries which lifetime ended.
@@ -136,13 +175,9 @@ cache_add (int type, void *key, size_t len, const void *packet, size_t total,
    free the data structures since some hash table entries share the same
    data.  */
 void
-prune_cache (struct database *table, time_t now)
+prune_cache (struct database_dyn *table, time_t now)
 {
-  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)
@@ -181,27 +216,112 @@ prune_cache (struct database *table, time_t now)
      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[cnt];
+  size_t first = cnt + 1;
+  size_t last = 0;
+  char *const data = table->data;
+  bool any = false;
+
   do
     {
-      struct hashentry *runp = table->array[--cnt];
-
-      mark[cnt] = 0;
+      ref_t run = table->head->array[--cnt];
 
-      while (runp != NULL)
+      while (run != ENDREF)
 	{
-	  if (runp->timeout < now)
+	  struct hashentry *runp = (struct hashentry *) (data + run);
+	  struct datahead *dh = (struct datahead *) (data + runp->packet);
+
+	  /* Check whether the entry timed out.  */
+	  if (dh->timeout < now)
 	    {
-	      ++mark[cnt];
-	      anything = 1;
+	      /* 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.  */
+		      switch (runp->type)
+			{
+			case GETPWBYNAME:
+			  readdpwbyname (table, runp, dh);
+			  break;
+
+			case GETPWBYUID:
+			  readdpwbyuid (table, runp, dh);
+			  break;
+
+			case GETGRBYNAME:
+			  readdgrbyname (table, runp, dh);
+			  break;
+
+			case GETGRBYGID:
+			  readdgrbygid (table, runp, dh);
+			  break;
+
+			case GETHOSTBYNAME:
+			  readdhstbyname (table, runp, dh);
+			  break;
+
+			case GETHOSTBYNAMEv6:
+			  readdhstbynamev6 (table, runp, dh);
+			  break;
+
+			case GETHOSTBYADDR:
+			  readdhstbyaddr (table, runp, dh);
+			  break;
+
+			case GETHOSTBYADDRv6:
+			  readdhstbyaddrv6 (table, runp, dh);
+			  break;
+
+			default:
+			  assert (! "should never happen");
+			}
+
+		      /* If the entry has been replaced, we might need
+			 cleanup.  */
+		      any |= !dh->usable;
+		    }
+		}
 	    }
-	  runp = runp->next;
+	  else
+	    assert (dh->usable);
+
+	  run = runp->next;
 	}
     }
   while (cnt > 0);
 
-  if (anything)
+  if (first <= last)
     {
       struct hashentry *head = NULL;
 
@@ -209,47 +329,57 @@ prune_cache (struct database *table, time_t now)
 	 the table.  */
       if (__builtin_expect (pthread_rwlock_trywrlock (&table->lock) != 0, 0))
 	{
-	  ++table->wrlockdelayed;
+	  ++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)
+	      while (run != ENDREF)
 		{
-		  table->array[first]->dellist = head;
-		  head = table->array[first];
-		  table->array[first] = head->next;
-		  --table->nentries;
-		  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];
-		      --table->nentries;
+		      /* 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;
+		    }
 		}
 	    }
+
 	  ++first;
 	}
 
       /* It's all done.  */
       pthread_rwlock_unlock (&table->lock);
 
+      /* Make sure the data is saved to disk.  */
+      if (table->persistent)
+	msync (table->head,
+	       table->data + table->head->first_free - (char *) table->head,
+	       MS_ASYNC);
+
       /* One extra pass if we do debugging.  */
       if (__builtin_expect (debug_level > 0, 0))
 	{
@@ -263,33 +393,20 @@ prune_cache (struct database *table, time_t now)
 	      if (runp->type == GETHOSTBYADDR || runp->type == GETHOSTBYADDRv6)
 		{
 		  inet_ntop (runp->type == GETHOSTBYADDR ? AF_INET : AF_INET6,
-			     runp->key, buf, sizeof (buf));
+			     table->data + runp->key, buf, sizeof (buf));
 		  str = buf;
 		}
 	      else
-		str = runp->key;
+		str = table->data + runp->key;
 
 	      dbg_log ("remove %s entry \"%s\"", serv2str[runp->type], str);
 
 	      runp = runp->dellist;
 	    }
 	}
-
-      /* And another run to free the data.  */
-      do
-	{
-	  struct hashentry *old = head;
-
-	  /* Free the data structures.  */
-	  if (old->data == (void *) -1)
-	    free (old->key);
-	  else if (old->last)
-	    free (old->data);
-
-	  head = head->dellist;
-
-	  free (old);
-	}
-      while (head != NULL);
     }
+
+  /* Run garbage collection if any entry has been removed or replaced.  */
+  if (any)
+    gc (table);
 }
diff --git a/nscd/connections.c b/nscd/connections.c
index 313ca0dc45..c3100816df 100644
--- a/nscd/connections.c
+++ b/nscd/connections.c
@@ -24,14 +24,15 @@
 #include <errno.h>
 #include <fcntl.h>
 #include <grp.h>
+#include <libintl.h>
 #include <pthread.h>
 #include <pwd.h>
 #include <resolv.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <unistd.h>
-#include <libintl.h>
 #include <arpa/inet.h>
+#include <sys/mman.h>
 #include <sys/param.h>
 #include <sys/poll.h>
 #include <sys/socket.h>
@@ -41,6 +42,11 @@
 #include "nscd.h"
 #include "dbg_log.h"
 
+
+/* Number of bytes of data we initially reserve for each hash table bucket.  */
+#define DEFAULT_DATASIZE_PER_BUCKET 1024
+
+
 /* Wrapper functions with error checking for standard functions.  */
 extern void *xmalloc (size_t n);
 extern void *xcalloc (size_t n, size_t s);
@@ -56,25 +62,11 @@ static gid_t *server_groups;
 #ifndef NGROUPS
 # define NGROUPS 32
 #endif
-static int server_ngroups = NGROUPS;
+static int server_ngroups;
 
 static void begin_drop_privileges (void);
 static void finish_drop_privileges (void);
 
-
-/* Mapping of request type to database.  */
-static const dbtype serv2db[LASTDBREQ + 1] =
-{
-  [GETPWBYNAME] = pwddb,
-  [GETPWBYUID] = pwddb,
-  [GETGRBYNAME] = grpdb,
-  [GETGRBYGID] = grpdb,
-  [GETHOSTBYNAME] = hstdb,
-  [GETHOSTBYNAMEv6] = hstdb,
-  [GETHOSTBYADDR] = hstdb,
-  [GETHOSTBYADDRv6] = hstdb,
-};
-
 /* Map request type to a string.  */
 const char *serv2str[LASTREQ] =
 {
@@ -92,43 +84,71 @@ const char *serv2str[LASTREQ] =
 };
 
 /* The control data structures for the services.  */
-struct database dbs[lastdb] =
+struct database_dyn dbs[lastdb] =
 {
   [pwddb] = {
     .lock = PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP,
     .enabled = 0,
     .check_file = 1,
+    .persistent = 0,
     .filename = "/etc/passwd",
-    .module = 211,
+    .db_filename = _PATH_NSCD_PASSWD_DB,
     .disabled_iov = &pwd_iov_disabled,
     .postimeout = 3600,
-    .negtimeout = 20
+    .negtimeout = 20,
+    .wr_fd = -1,
+    .ro_fd = -1,
+    .mmap_used = false
   },
   [grpdb] = {
     .lock = PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP,
     .enabled = 0,
     .check_file = 1,
+    .persistent = 0,
     .filename = "/etc/group",
-    .module = 211,
+    .db_filename = _PATH_NSCD_GROUP_DB,
     .disabled_iov = &grp_iov_disabled,
     .postimeout = 3600,
-    .negtimeout = 60
+    .negtimeout = 60,
+    .wr_fd = -1,
+    .ro_fd = -1,
+    .mmap_used = false
   },
   [hstdb] = {
     .lock = PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP,
     .enabled = 0,
     .check_file = 1,
+    .persistent = 0,
     .filename = "/etc/hosts",
-    .module = 211,
+    .db_filename = _PATH_NSCD_HOSTS_DB,
     .disabled_iov = &hst_iov_disabled,
     .postimeout = 3600,
-    .negtimeout = 20
+    .negtimeout = 20,
+    .wr_fd = -1,
+    .ro_fd = -1,
+    .mmap_used = false
   }
 };
 
+
+/* Mapping of request type to database.  */
+static struct database_dyn *const serv2db[LASTDBREQ + 1] =
+{
+  [GETPWBYNAME] = &dbs[pwddb],
+  [GETPWBYUID] = &dbs[pwddb],
+  [GETGRBYNAME] = &dbs[grpdb],
+  [GETGRBYGID] = &dbs[grpdb],
+  [GETHOSTBYNAME] = &dbs[hstdb],
+  [GETHOSTBYNAMEv6] = &dbs[hstdb],
+  [GETHOSTBYADDR] = &dbs[hstdb],
+  [GETHOSTBYADDRv6] = &dbs[hstdb]
+};
+
+
 /* Number of seconds between two cache pruning runs.  */
 #define CACHE_PRUNE_INTERVAL	15
 
+
 /* Number of threads to use.  */
 int nthreads = -1;
 
@@ -138,6 +158,9 @@ static int sock;
 /* Number of times clients had to wait.  */
 unsigned long int client_queued;
 
+/* Alignment requirement of the beginning of the data region.  */
+#define ALIGN 16
+
 
 /* Initialize database information structures.  */
 void
@@ -166,13 +189,256 @@ nscd_init (void)
     if (dbs[cnt].enabled)
       {
 	pthread_rwlock_init (&dbs[cnt].lock, NULL);
+	pthread_mutex_init (&dbs[cnt].memlock, NULL);
 
-	dbs[cnt].array = (struct hashentry **)
-	  calloc (dbs[cnt].module, sizeof (struct hashentry *));
-	if (dbs[cnt].array == NULL)
+	if (dbs[cnt].persistent)
 	  {
-	    dbg_log (_("while allocating cache: %s"), strerror (errno));
-	    exit (1);
+	    /* Try to open the appropriate file on disk.  */
+	    int fd = open (dbs[cnt].db_filename, O_RDWR);
+	    if (fd != -1)
+	      {
+		struct stat64 st;
+		void *mem;
+		size_t total;
+		struct database_pers_head head;
+		ssize_t n = TEMP_FAILURE_RETRY (read (fd, &head,
+						      sizeof (head)));
+		if (n != sizeof (head) || fstat64 (fd, &st) != 0)
+		  {
+		  fail_db:
+		    dbg_log (_("invalid persistent database file \"%s\": %s"),
+			     dbs[cnt].db_filename, strerror (errno));