[PATCH v2 12/23] nscd: Rewrite __nscd_cache_search using <concurrent_buffer.h>

[Florian Weimer]

This makes it somewhat clearer what is going on.  This still
does not implement a proper software TM snapshot.
---
 nscd/nscd_helper.c | 85 ++++++++++++++++++----------------------------
 1 file changed, 33 insertions(+), 52 deletions(-)

diff --git a/nscd/nscd_helper.c b/nscd/nscd_helper.c
index 2a60c3572e..9bd0e7818e 100644
--- a/nscd/nscd_helper.c
+++ b/nscd/nscd_helper.c
@@ -41,6 +41,7 @@
 #include "nscd-client.h"
 #include "nscd-dbtype.h"
 #include "nscd_proto.h"
+#include "concurrent_buffer.h"
 
 /* Extra time we wait if the socket is still receiving data.  This
    value is in milliseconds.  Note that the other side is nscd on the
@@ -527,71 +528,51 @@ __nscd_cache_search (request_type type, const char *key, size_t keylen,
 		     const struct mapped_database *mapped, size_t datalen)
 {
   unsigned long int hash = __nss_hash (key, keylen) % mapped->head->module;
-  size_t datasize = mapped->datasize;
+
+  struct concurrent_buffer cb = cb_create (mapped->data, mapped->datasize);
 
   ref_t trail = mapped->head->array[hash];
   ref_t work = trail;
-  size_t loop_cnt = datasize / (MINIMUM_HASHENTRY_SIZE
-				+ offsetof (struct datahead, data) / 2);
+  size_t loop_cnt = mapped->datasize / (MINIMUM_HASHENTRY_SIZE
+					+ offsetof (struct datahead, data) / 2);
   int tick = 0;
 
-  while (work != ENDREF && work + MINIMUM_HASHENTRY_SIZE <= datasize)
+  while (work != ENDREF)
     {
-      struct hashentry *here = (struct hashentry *) (mapped->data + work);
-      ref_t here_key, here_packet;
-
-      /* Although during garbage collection when moving struct hashentry
-	 records around we first copy from old to new location and then
-	 adjust pointer from previous hashentry to it, there is no barrier
-	 between those memory writes!!! This is extremely risky on any
-	 modern CPU which can reorder memory accesses very aggressively.
-	 Check alignment, both as a partial consistency check and to avoid
-	 crashes on targets which require atomic loads to be aligned.  */
-      if ((uintptr_t) here & (__alignof__ (*here) - 1))
-	return NULL;
-
-      if (type == here->type
-	  && keylen == here->len
-	  && (here_key = atomic_load_relaxed (&here->key)) + keylen <= datasize
-	  && memcmp (key, mapped->data + here_key, keylen) == 0
-	  && ((here_packet = atomic_load_relaxed (&here->packet))
-	      + sizeof (struct datahead) <= datasize))
+      /* First compare type and key.  */
+      if (type == cb_field (&cb, work, struct hashentry, type)
+	  && keylen == cb_field (&cb, work, struct hashentry, len))
 	{
-	  /* We found the entry.  Increment the appropriate counter.  */
-	  struct datahead *dh
-	    = (struct datahead *) (mapped->data + here_packet);
-
-	  if ((uintptr_t) dh & (__alignof__ (*dh) - 1))
-	    return NULL;
-
-	  /* See whether we must ignore the entry or whether something
-	     is wrong because garbage collection is in progress.  */
-	  if (dh->usable
-	      && here_packet + dh->allocsize <= datasize
-	      && (here_packet + offsetof (struct datahead, data) + datalen
-		  <= datasize))
-	    return dh;
+	  ref_t here_key = cb_field (&cb, work, struct hashentry, key);
+	  if (cb_memeq (&cb, here_key, key, keylen))
+	    {
+	      /* Data found.  Now validate the data reference.  */
+	      ref_t here_packet = cb_field (&cb, work,
+					    struct hashentry, packet);
+	      if ((here_packet & (__alignof__ (struct datahead) - 1)) == 0
+		  && cb_field (&cb, here_packet, struct datahead, usable))
+		{
+		  size_t allocsize = cb_field (&cb, here_packet,
+					       struct datahead, allocsize);
+		  if (cb_available (&cb, here_packet, allocsize))
+		      /* We found the entry.  */
+		      return (struct datahead *) (mapped->data + here_packet);
+		}
+	    }
 	}
 
-      work = atomic_load_relaxed (&here->next);
+      work = cb_field (&cb, work, struct hashentry, next);
+      if (cb_has_failed (&cb))
+	return NULL;
+
       /* Prevent endless loops.  This should never happen but perhaps
-	 the database got corrupted, accidentally or deliberately.  */
+	 the database got corrupted, accidentally or deliberately.
+	 Use both a loop count and a Floyd-style cycle detector
+	 (work is the hare, and trail is the tortoise).  */
       if (work == trail || loop_cnt-- == 0)
 	break;
       if (tick)
-	{
-	  struct hashentry *trailelem;
-	  trailelem = (struct hashentry *) (mapped->data + trail);
-
-	  /* We have to redo the checks.  Maybe the data changed.  */
-	  if ((uintptr_t) trailelem & (__alignof__ (*trailelem) - 1))
-	    return NULL;
-
-	  if (trail + MINIMUM_HASHENTRY_SIZE > datasize)
-	    return NULL;
-
-	  trail = atomic_load_relaxed (&trailelem->next);
-	}
+	trail = cb_field (&cb, trail, struct hashentry, next);
       tick = 1 - tick;
     }
 
-- 
2.53.0