From 80485401a9a5e9df03bd3a1503bc5e59d1f2e5c1 Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Fri, 16 May 2014 23:06:33 +0200
Subject: libdiskfs: add diskfs_make_node_alloc to allocate fat nodes

libdiskfs has two kind of nodes, struct node and struct netnode.
struct node is used to store libdiskfs specific data, while struct
netnode contains user supplied data.  Previously, both objects were
allocated separatly, and a pointer from the node to the netnode
provided a mapping from the former to the latter.

Provide a function diskfs_make_node_alloc that allocates both nodes in
a contiguous region.

This reduces the memory allocation overhead when creating nodes.  It
also makes the relation between node and netnode a simple offset
calculation.  Provide two functions to compute the netnode address
from the node address and vice-versa.

Most notably, this makes implementing a cache on top of libdiskfs
easier.  Auxiliary data for the cache can be stored in the
user-defined netnode, and the fat node can be used as the value.

* libdiskfs/node-make.c (init_node): Move initialization here.
(diskfs_make_node): Use init_node.
(diskfs_make_node_alloc): New function to allocate fat nodes.
* libdiskfs/diskfs.h (diskfs_make_node_alloc): New declaration.
(_diskfs_sizeof_struct_node): Likewise.
(diskfs_node_disknode): Compute disknode address from node address.
(diskfs_disknode_node): And vice-versa.
* libdiskfs/init-init.c (_diskfs_sizeof_struct_node): New variable.
---
 libdiskfs/diskfs.h    | 27 +++++++++++++++++++++++++++
 libdiskfs/init-init.c |  4 ++++
 libdiskfs/node-make.c | 39 ++++++++++++++++++++++++++++++---------
 3 files changed, 61 insertions(+), 9 deletions(-)

diff --git a/libdiskfs/diskfs.h b/libdiskfs/diskfs.h
index ae1a1502..2c68aa34 100644
--- a/libdiskfs/diskfs.h
+++ b/libdiskfs/diskfs.h
@@ -686,6 +686,33 @@ diskfs_notice_filechange (struct node *np, enum file_changed_type type,
    The new node will have one hard reference and no light references.  */
 struct node *diskfs_make_node (struct disknode *dn);
 
+/* Create a new node structure.  Also allocate SIZE bytes for the
+   disknode.  The address of the disknode can be obtained using
+   diskfs_node_disknode.  The new node will have one hard reference
+   and no light references.  */
+struct node *diskfs_make_node_alloc (size_t size);
+
+/* To avoid breaking the ABI whenever sizeof (struct node) changes, we
+   explicitly provide the size.  The following two functions will use
+   this value for offset calculations.  */
+extern const size_t _diskfs_sizeof_struct_node;
+
+/* Return the address of the disknode for NODE.  NODE must have been
+   allocated using diskfs_make_node_alloc.  */
+static inline struct disknode *
+diskfs_node_disknode (struct node *node)
+{
+  return (struct disknode *) ((char *) node + _diskfs_sizeof_struct_node);
+}
+
+/* Return the address of the node for DISKNODE.  DISKNODE must have
+   been allocated using diskfs_make_node_alloc.  */
+static inline struct node *
+diskfs_disknode_node (struct disknode *disknode)
+{
+  return (struct node *) ((char *) disknode - _diskfs_sizeof_struct_node);
+}
+
 
 /* The library also exports the following functions; they are not generally
    useful unless you are redefining other functions the library provides. */
diff --git a/libdiskfs/init-init.c b/libdiskfs/init-init.c
index 35be7edd..7a7f2485 100644
--- a/libdiskfs/init-init.c
+++ b/libdiskfs/init-init.c
@@ -25,6 +25,10 @@ the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
 #include <stdio.h>
 #include <maptime.h>
 
+/* For safe inlining of diskfs_node_disknode and
+   diskfs_disknode_node.  */
+size_t const _diskfs_sizeof_struct_node = sizeof (struct node);
+
 mach_port_t diskfs_default_pager;
 mach_port_t diskfs_auth_server_port;
 volatile struct mapped_time_value *diskfs_mtime;
diff --git a/libdiskfs/node-make.c b/libdiskfs/node-make.c
index 2b6ef2af..ff0cc0d4 100644
--- a/libdiskfs/node-make.c
+++ b/libdiskfs/node-make.c
@@ -19,16 +19,9 @@
 #include <fcntl.h>
 
 
-/* Create a and return new node structure with DN as its physical disknode.
-   The node will have one hard reference and no light references.  */
-struct node *
-diskfs_make_node (struct disknode *dn)
+static struct node *
+init_node (struct node *np, struct disknode *dn)
 {
-  struct node *np = malloc (sizeof (struct node));
-
-  if (np == 0)
-    return 0;
-
   np->dn = dn;
   np->dn_set_ctime = 0;
   np->dn_set_atime = 0;
@@ -52,3 +45,31 @@ diskfs_make_node (struct disknode *dn)
 
   return np;
 }
+
+/* Create a and return new node structure with DN as its physical disknode.
+   The node will have one hard reference and no light references.  */
+struct node *
+diskfs_make_node (struct disknode *dn)
+{
+  struct node *np = malloc (sizeof (struct node));
+
+  if (np == 0)
+    return 0;
+
+  return init_node (np, dn);
+}
+
+/* Create a new node structure.  Also allocate SIZE bytes for the
+   disknode.  The address of the disknode can be obtained using
+   diskfs_node_disknode.  The new node will have one hard reference
+   and no light references.  */
+struct node *
+diskfs_make_node_alloc (size_t size)
+{
+  struct node *np = malloc (sizeof (struct node) + size);
+
+  if (np == NULL)
+    return NULL;
+
+  return init_node (np, diskfs_node_disknode (np));
+}
-- 
cgit v1.2.3


From 94fecd72f41542c8dfa82bdf7b47742f8c29b321 Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Sun, 18 May 2014 13:34:12 +0200
Subject: libnetfs: add netfs_make_node_alloc to allocate fat nodes

libnetfs has two kind of nodes, struct node and struct netnode.
struct node is used to store libnetfs specific data, while struct
netnode contains user supplied data.  Previously, both objects were
allocated separatly, and a pointer from the node to the netnode
provided a mapping from the former to the latter.

Provide a function netfs_make_node_alloc that allocates both nodes in
a contiguous region.

This reduces the memory allocation overhead when creating nodes.  It
also makes the relation between node and netnode a simple offset
calculation.  Provide two functions to compute the netnode address
from the node address and vice-versa.

Most notably, this makes implementing a cache on top of libnetfs
easier.  Auxiliary data for the cache can be stored in the
user-defined netnode, and the fat node can be used as the value.

* libnetfs/make-node.c (init_node): Move initialization here.
(netfs_make_node): Use init_node.
(netfs_make_node_alloc): New function to allocate fat nodes.
* libnetfs/netfs.h (netfs_make_node_alloc): New declaration.
(_netfs_sizeof_struct_node): Likewise.
(netfs_node_netnode): Compute netnode address from node address.
(netfs_netnode_node): And vice-versa.
* libnetfs/init-init.c (_netfs_sizeof_struct_node): New variable.
---
 libnetfs/init-init.c |  3 +++
 libnetfs/make-node.c | 29 +++++++++++++++++++++++------
 libnetfs/netfs.h     | 27 +++++++++++++++++++++++++++
 3 files changed, 53 insertions(+), 6 deletions(-)

diff --git a/libnetfs/init-init.c b/libnetfs/init-init.c
index e98b6562..a088ad51 100644
--- a/libnetfs/init-init.c
+++ b/libnetfs/init-init.c
@@ -21,6 +21,9 @@
 
 #include "netfs.h"
 
+/* For safe inlining of netfs_node_netnode and netfs_netnode_node.  */
+size_t const _netfs_sizeof_struct_node = sizeof (struct node);
+
 pthread_spinlock_t netfs_node_refcnt_lock = PTHREAD_SPINLOCK_INITIALIZER;
 
 struct node *netfs_root_node = 0;
diff --git a/libnetfs/make-node.c b/libnetfs/make-node.c
index f20ada18..6bd8109c 100644
--- a/libnetfs/make-node.c
+++ b/libnetfs/make-node.c
@@ -21,13 +21,9 @@
 #include "netfs.h"
 #include <hurd/fshelp.h>
 
-struct node *
-netfs_make_node (struct netnode *nn)
+static struct node *
+init_node (struct node *np, struct netnode *nn)
 {
-  struct node *np = malloc (sizeof (struct node));
-  if (! np)
-    return NULL;
-  
   np->nn = nn;
 
   pthread_mutex_init (&np->lock, NULL);
@@ -40,3 +36,24 @@ netfs_make_node (struct netnode *nn)
   
   return np;
 }
+
+struct node *
+netfs_make_node (struct netnode *nn)
+{
+  struct node *np = malloc (sizeof (struct node));
+  if (! np)
+    return NULL;
+
+  return init_node (np, nn);
+}
+
+struct node *
+netfs_make_node_alloc (size_t size)
+{
+  struct node *np = malloc (sizeof (struct node) + size);
+
+  if (np == NULL)
+    return NULL;
+
+  return init_node (np, netfs_node_netnode (np));
+}
diff --git a/libnetfs/netfs.h b/libnetfs/netfs.h
index aef4a3dd..fbe2c60d 100644
--- a/libnetfs/netfs.h
+++ b/libnetfs/netfs.h
@@ -372,6 +372,33 @@ extern int netfs_maxsymlinks;
    If an error occurs, NULL is returned.  */
 struct node *netfs_make_node (struct netnode *);
 
+/* Create a new node structure.  Also allocate SIZE bytes for the
+   netnode.  The address of the netnode can be obtained using
+   netfs_node_netnode.  The new node will have one hard reference and
+   no light references.  If an error occurs, NULL is returned.  */
+struct node *netfs_make_node_alloc (size_t size);
+
+/* To avoid breaking the ABI whenever sizeof (struct node) changes, we
+   explicitly provide the size.  The following two functions will use
+   this value for offset calculations.  */
+extern const size_t _netfs_sizeof_struct_node;
+
+/* Return the address of the netnode for NODE.  NODE must have been
+   allocated using netfs_make_node_alloc.  */
+static inline struct netnode *
+netfs_node_netnode (struct node *node)
+{
+  return (struct netnode *) ((char *) node + _netfs_sizeof_struct_node);
+}
+
+/* Return the address of the node for NETNODE.  NETNODE must have been
+   allocated using netfs_make_node_alloc.  */
+static inline struct node *
+netfs_netnode_node (struct netnode *netnode)
+{
+  return (struct node *) ((char *) netnode - _netfs_sizeof_struct_node);
+}
+
 /* Whenever node->references is to be touched, this lock must be
    held.  Cf. netfs_nrele, netfs_nput, netfs_nref and netfs_drop_node.  */
 extern pthread_spinlock_t netfs_node_refcnt_lock;
-- 
cgit v1.2.3


From 6349d15921134adb4491eb9ce87720a0281a7bd6 Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Sun, 18 May 2014 13:45:14 +0200
Subject: trans/fakeroot: use fat nodes to simplify the node cache

Previously, fakeroot stored netnodes in the hash table.  But we are
not interested in a cache for netnodes, we need a node cache.  So
fakeroot kept pointers to the associated node object in each netnode
object.

Use fat netfs nodes, which combine node and netnode objects.

* trans/fakeroot.c (struct netnode): Remove np.
(idport_ihash): Fix ihash location pointer offset.
(new_node): Allocate fat nodes, store the node pointer in the hash
table.
(netfs_node_norefs): Adjust accordingly.
(netfs_S_dir_lookup): Likewise.
---
 trans/fakeroot.c | 36 ++++++++++++------------------------
 1 file changed, 12 insertions(+), 24 deletions(-)

diff --git a/trans/fakeroot.c b/trans/fakeroot.c
index 4175b552..59f8a867 100644
--- a/trans/fakeroot.c
+++ b/trans/fakeroot.c
@@ -47,7 +47,6 @@ static auth_t fakeroot_auth_port;
 
 struct netnode
 {
-  struct node *np;		/* our node */
   hurd_ihash_locp_t idport_locp;/* easy removal pointer in idport ihash */
   mach_port_t idport;		/* port from io_identity */
   int openmodes;		/* O_READ | O_WRITE | O_EXEC */
@@ -64,7 +63,8 @@ struct netnode
 
 pthread_mutex_t idport_ihash_lock = PTHREAD_MUTEX_INITIALIZER;
 struct hurd_ihash idport_ihash
-  = HURD_IHASH_INITIALIZER (offsetof (struct netnode, idport_locp));
+= HURD_IHASH_INITIALIZER (sizeof (struct node)
+			  + offsetof (struct netnode, idport_locp));
 
 
 /* Make a new virtual node.  Always consumes the ports.  If
@@ -74,8 +74,9 @@ new_node (file_t file, mach_port_t idport, int locked, int openmodes,
 	  struct node **np)
 {
   error_t err;
-  struct netnode *nn = calloc (1, sizeof *nn);
-  if (nn == 0)
+  struct netnode *nn;
+  *np = netfs_make_node_alloc (sizeof *nn);
+  if (*np == 0)
     {
       mach_port_deallocate (mach_task_self (), file);
       if (idport != MACH_PORT_NULL)
@@ -84,6 +85,7 @@ new_node (file_t file, mach_port_t idport, int locked, int openmodes,
 	pthread_mutex_unlock (&idport_ihash_lock);
       return ENOMEM;
     }
+  nn = netfs_node_netnode (*np);
   nn->file = file;
   nn->openmodes = openmodes;
   if (idport != MACH_PORT_NULL)
@@ -97,35 +99,26 @@ new_node (file_t file, mach_port_t idport, int locked, int openmodes,
       if (err)
 	{
 	  mach_port_deallocate (mach_task_self (), file);
-	  free (nn);
+	  free (*np);
 	  return err;
 	}
     }
 
   if (!locked)
     pthread_mutex_lock (&idport_ihash_lock);
-  err = hurd_ihash_add (&idport_ihash, nn->idport, nn);
+  err = hurd_ihash_add (&idport_ihash, nn->idport, *np);
   if (err)
     goto lose;
 
-  *np = nn->np = netfs_make_node (nn);
-  if (*np == 0)
-    {
-      err = ENOMEM;
-      goto lose_hash;
-    }
-
   pthread_mutex_lock (&(*np)->lock);
   pthread_mutex_unlock (&idport_ihash_lock);
   return 0;
 
- lose_hash:
-  hurd_ihash_locp_remove (&idport_ihash, nn->idport_locp);
  lose:
   pthread_mutex_unlock (&idport_ihash_lock);
   mach_port_deallocate (mach_task_self (), nn->idport);
   mach_port_deallocate (mach_task_self (), file);
-  free (nn);
+  free (*np);
   return err;
 }
 
@@ -161,8 +154,6 @@ set_faked_attribute (struct node *np, unsigned int faked)
 void
 netfs_node_norefs (struct node *np)
 {
-  assert (np->nn->np == np);
-
   pthread_mutex_unlock (&np->lock);
   pthread_spin_unlock (&netfs_node_refcnt_lock);
 
@@ -172,7 +163,6 @@ netfs_node_norefs (struct node *np)
 
   mach_port_deallocate (mach_task_self (), np->nn->file);
   mach_port_deallocate (mach_task_self (), np->nn->idport);
-  free (np->nn);
   free (np);
 
   pthread_spin_lock (&netfs_node_refcnt_lock);
@@ -358,13 +348,12 @@ netfs_S_dir_lookup (struct protid *diruser,
      refcount lock so that, if a node is found, its reference counter cannot
      drop to 0 before we get our own reference.  */
   pthread_spin_lock (&netfs_node_refcnt_lock);
-  struct netnode *nn = hurd_ihash_find (&idport_ihash, idport);
-  if (nn != NULL)
+  np = hurd_ihash_find (&idport_ihash, idport);
+  if (np != NULL)
     {
-      assert (nn->np->nn == nn);
       /* We already know about this node.  */
 
-      if (nn->np->references == 0)
+      if (np->references == 0)
 	{
 	  /* But it might be in the process of being released.  If so,
 	     unlock the hash table to give the node a chance to actually
@@ -376,7 +365,6 @@ netfs_S_dir_lookup (struct protid *diruser,
 	}
 
       /* Otherwise, reference it right away.  */
-      np = nn->np;
       np->references++;
       pthread_spin_unlock (&netfs_node_refcnt_lock);
 
-- 
cgit v1.2.3


From f6730b267a90ad73116e50b027e869cbe0b01211 Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Sun, 18 May 2014 14:06:30 +0200
Subject: trans/fakeroot: use netfs_node_netnode instead of np->nn

When using fat nodes, expressions of the form E->nn can be rewritten
as netfs_node_netnode (E).  This is much faster as it only involves a
offset calculation.  For reference, I used the following semantic
patch to create the patch:

@@
expression E;
@@

- E->nn
+ netfs_node_netnode (E)

* trans/fakeroot.c: Use netfs_node_netnode instead of np->nn.
---
 trans/fakeroot.c | 99 ++++++++++++++++++++++++++++++--------------------------
 1 file changed, 53 insertions(+), 46 deletions(-)

diff --git a/trans/fakeroot.c b/trans/fakeroot.c
index 59f8a867..32a34ec4 100644
--- a/trans/fakeroot.c
+++ b/trans/fakeroot.c
@@ -125,7 +125,7 @@ new_node (file_t file, mach_port_t idport, int locked, int openmodes,
 static void
 set_default_attributes (struct node *np)
 {
-  np->nn->faked = FAKE_UID | FAKE_GID | FAKE_DEFAULT;
+  netfs_node_netnode (np)->faked = FAKE_UID | FAKE_GID | FAKE_DEFAULT;
   np->nn_stat.st_uid = 0;
   np->nn_stat.st_gid = 0;
 }
@@ -133,9 +133,9 @@ set_default_attributes (struct node *np)
 static void
 set_faked_attribute (struct node *np, unsigned int faked)
 {
-  np->nn->faked |= faked;
+  netfs_node_netnode (np)->faked |= faked;
 
-  if (np->nn->faked & FAKE_DEFAULT)
+  if (netfs_node_netnode (np)->faked & FAKE_DEFAULT)
     {
       /* Now that the node has non-default faked attributes, they have to be
 	 retained for future accesses.  Account for the hash table reference.
@@ -146,7 +146,7 @@ set_faked_attribute (struct node *np, unsigned int faked)
 	 easy enough if it's ever needed, although scalability could be
 	 improved.  */
       netfs_nref (np);
-      np->nn->faked &= ~FAKE_DEFAULT;
+      netfs_node_netnode (np)->faked &= ~FAKE_DEFAULT;
     }
 }
 
@@ -158,11 +158,11 @@ netfs_node_norefs (struct node *np)
   pthread_spin_unlock (&netfs_node_refcnt_lock);
 
   pthread_mutex_lock (&idport_ihash_lock);
-  hurd_ihash_locp_remove (&idport_ihash, np->nn->idport_locp);
+  hurd_ihash_locp_remove (&idport_ihash, netfs_node_netnode (np)->idport_locp);
   pthread_mutex_unlock (&idport_ihash_lock);
 
-  mach_port_deallocate (mach_task_self (), np->nn->file);
-  mach_port_deallocate (mach_task_self (), np->nn->idport);
+  mach_port_deallocate (mach_task_self (), netfs_node_netnode (np)->file);
+  mach_port_deallocate (mach_task_self (), netfs_node_netnode (np)->idport);
   free (np);
 
   pthread_spin_lock (&netfs_node_refcnt_lock);
@@ -245,7 +245,8 @@ error_t
 netfs_check_open_permissions (struct iouser *user, struct node *np,
 			      int flags, int newnode)
 {
-  return check_openmodes (np->nn, flags & (O_RDWR|O_EXEC), MACH_PORT_NULL);
+  return check_openmodes (netfs_node_netnode (np),
+			  flags & (O_RDWR|O_EXEC), MACH_PORT_NULL);
 }
 
 error_t
@@ -271,12 +272,12 @@ netfs_S_dir_lookup (struct protid *diruser,
 
   dnp = diruser->po->np;
 
-  mach_port_t dir = dnp->nn->file;
+  mach_port_t dir = netfs_node_netnode (dnp)->file;
  redo_lookup:
   err = dir_lookup (dir, filename,
 		    flags & (O_NOLINK|O_RDWR|O_EXEC|O_CREAT|O_EXCL|O_NONBLOCK),
 		    mode, do_retry, retry_name, &file);
-  if (dir != dnp->nn->file)
+  if (dir != netfs_node_netnode (dnp)->file)
     mach_port_deallocate (mach_task_self (), dir);
   if (err)
     return err;
@@ -380,7 +381,8 @@ netfs_S_dir_lookup (struct protid *diruser,
 	  pthread_mutex_unlock (&dnp->lock);
 	}
 
-      err = check_openmodes (np->nn, (flags & (O_RDWR|O_EXEC)), file);
+      err = check_openmodes (netfs_node_netnode (np),
+			     (flags & (O_RDWR|O_EXEC)), file);
       pthread_mutex_unlock (&idport_ihash_lock);
     }
   else
@@ -448,17 +450,17 @@ error_t
 netfs_validate_stat (struct node *np, struct iouser *cred)
 {
   struct stat st;
-  error_t err = io_stat (np->nn->file, &st);
+  error_t err = io_stat (netfs_node_netnode (np)->file, &st);
   if (err)
     return err;
 
-  if (np->nn->faked & FAKE_UID)
+  if (netfs_node_netnode (np)->faked & FAKE_UID)
     st.st_uid = np->nn_stat.st_uid;
-  if (np->nn->faked & FAKE_GID)
+  if (netfs_node_netnode (np)->faked & FAKE_GID)
     st.st_gid = np->nn_stat.st_gid;
-  if (np->nn->faked & FAKE_AUTHOR)
+  if (netfs_node_netnode (np)->faked & FAKE_AUTHOR)
     st.st_author = np->nn_stat.st_author;
-  if (np->nn->faked & FAKE_MODE)
+  if (netfs_node_netnode (np)->faked & FAKE_MODE)
     st.st_mode = np->nn_stat.st_mode;
 
   np->nn_stat = st;
@@ -528,7 +530,7 @@ netfs_attempt_chmod (struct iouser *cred, struct node *np, mode_t mode)
 
   /* We don't bother with error checking since the fake mode change should
      always succeed--worst case a later open will get EACCES.  */
-  (void) file_chmod (np->nn->file, mode);
+  (void) file_chmod (netfs_node_netnode (np)->file, mode);
   set_faked_attribute (np, FAKE_MODE);
   np->nn_stat.st_mode = mode;
   return 0;
@@ -543,7 +545,7 @@ netfs_attempt_mksymlink (struct iouser *cred, struct node *np, char *name)
   char trans[sizeof _HURD_SYMLINK + namelen];
   memcpy (trans, _HURD_SYMLINK, sizeof _HURD_SYMLINK);
   memcpy (&trans[sizeof _HURD_SYMLINK], name, namelen);
-  return file_set_translator (np->nn->file,
+  return file_set_translator (netfs_node_netnode (np)->file,
 			      FS_TRANS_EXCL|FS_TRANS_SET,
 			      FS_TRANS_EXCL|FS_TRANS_SET, 0,
 			      trans, sizeof trans,
@@ -562,7 +564,7 @@ netfs_attempt_mkdev (struct iouser *cred, struct node *np,
     return ENOMEM;
   else
     {
-      error_t err = file_set_translator (np->nn->file,
+      error_t err = file_set_translator (netfs_node_netnode (np)->file,
 					 FS_TRANS_EXCL|FS_TRANS_SET,
 					 FS_TRANS_EXCL|FS_TRANS_SET, 0,
 					 trans, translen + 1,
@@ -576,7 +578,7 @@ netfs_attempt_mkdev (struct iouser *cred, struct node *np,
 error_t
 netfs_attempt_chflags (struct iouser *cred, struct node *np, int flags)
 {
-  return file_chflags (np->nn->file, flags);
+  return file_chflags (netfs_node_netnode (np)->file, flags);
 }
 
 error_t
@@ -602,25 +604,25 @@ netfs_attempt_utimes (struct iouser *cred, struct node *np,
   else
     m.tv.tv_sec = m.tv.tv_usec = -1;
 
-  return file_utimes (np->nn->file, a.tvt, m.tvt);
+  return file_utimes (netfs_node_netnode (np)->file, a.tvt, m.tvt);
 }
 
 error_t
 netfs_attempt_set_size (struct iouser *cred, struct node *np, off_t size)
 {
-  return file_set_size (np->nn->file, size);
+  return file_set_size (netfs_node_netnode (np)->file, size);
 }
 
 error_t
 netfs_attempt_statfs (struct iouser *cred, struct node *np, struct statfs *st)
 {
-  return file_statfs (np->nn->file, st);
+  return file_statfs (netfs_node_netnode (np)->file, st);
 }
 
 error_t
 netfs_attempt_sync (struct iouser *cred, struct node *np, int wait)
 {
-  return file_sync (np->nn->file, wait, 0);
+  return file_sync (netfs_node_netnode (np)->file, wait, 0);
 }
 
 error_t
@@ -633,7 +635,7 @@ error_t
 netfs_attempt_mkdir (struct iouser *user, struct node *dir,
 		     char *name, mode_t mode)
 {
-  return dir_mkdir (dir->nn->file, name, mode | S_IRWXU);
+  return dir_mkdir (netfs_node_netnode (dir)->file, name, mode | S_IRWXU);
 }
 
 
@@ -645,7 +647,7 @@ netfs_attempt_mkdir (struct iouser *user, struct node *dir,
 error_t
 netfs_attempt_unlink (struct iouser *user, struct node *dir, char *name)
 {
-  return dir_unlink (dir->nn->file, name);
+  return dir_unlink (netfs_node_netnode (dir)->file, name);
 }
 
 error_t
@@ -653,22 +655,22 @@ netfs_attempt_rename (struct iouser *user, struct node *fromdir,
 		      char *fromname, struct node *todir,
 		      char *toname, int excl)
 {
-  return dir_rename (fromdir->nn->file, fromname,
-		     todir->nn->file, toname, excl);
+  return dir_rename (netfs_node_netnode (fromdir)->file, fromname,
+		     netfs_node_netnode (todir)->file, toname, excl);
 }
 
 error_t
 netfs_attempt_rmdir (struct iouser *user,
 		     struct node *dir, char *name)
 {
-  return dir_rmdir (dir->nn->file, name);
+  return dir_rmdir (netfs_node_netnode (dir)->file, name);
 }
 
 error_t
 netfs_attempt_link (struct iouser *user, struct node *dir,
 		    struct node *file, char *name, int excl)
 {
-  return dir_link (dir->nn->file, file->nn->file, name, excl);
+  return dir_link (netfs_node_netnode (dir)->file, netfs_node_netnode (file)->file, name, excl);
 }
 
 error_t
@@ -676,7 +678,7 @@ netfs_attempt_mkfile (struct iouser *user, struct node *dir,
 		      mode_t mode, struct node **np)
 {
   file_t newfile;
-  error_t err = dir_mkfile (dir->nn->file, O_RDWR|O_EXEC,
+  error_t err = dir_mkfile (netfs_node_netnode (dir)->file, O_RDWR|O_EXEC,
 			    real_from_fake_mode (mode), &newfile);
   pthread_mutex_unlock (&dir->lock);
   if (err == 0)
@@ -692,7 +694,8 @@ netfs_attempt_readlink (struct iouser *user, struct node *np, char *buf)
   char transbuf[sizeof _HURD_SYMLINK + np->nn_stat.st_size + 1];
   char *trans = transbuf;
   size_t translen = sizeof transbuf;
-  error_t err = file_get_translator (np->nn->file, &trans, &translen);
+  error_t err = file_get_translator (netfs_node_netnode (np)->file,
+				     &trans, &translen);
   if (err == 0)
     {
       if (translen < sizeof _HURD_SYMLINK
@@ -715,7 +718,8 @@ netfs_attempt_read (struct iouser *cred, struct node *np,
 		    off_t offset, size_t *len, void *data)
 {
   char *buf = data;
-  error_t err = io_read (np->nn->file, &buf, len, offset, *len);
+  error_t err = io_read (netfs_node_netnode (np)->file,
+			 &buf, len, offset, *len);
   if (err == 0 && buf != data)
     {
       memcpy (data, buf, *len);
@@ -728,7 +732,7 @@ error_t
 netfs_attempt_write (struct iouser *cred, struct node *np,
 		     off_t offset, size_t *len, void *data)
 {
-  return io_write (np->nn->file, data, *len, offset, len);
+  return io_write (netfs_node_netnode (np)->file, data, *len, offset, len);
 }
 
 error_t
@@ -744,7 +748,7 @@ netfs_get_dirents (struct iouser *cred, struct node *dir,
 		   mach_msg_type_number_t *datacnt,
 		   vm_size_t bufsize, int *amt)
 {
-  return dir_readdir (dir->nn->file, data, datacnt,
+  return dir_readdir (netfs_node_netnode (dir)->file, data, datacnt,
 		      entry, nentries, bufsize, amt);
 }
 
@@ -762,7 +766,7 @@ netfs_file_get_storage_info (struct iouser *cred,
 			     mach_msg_type_number_t *data_len)
 {
   *ports_type = MACH_MSG_TYPE_MOVE_SEND;
-  return file_get_storage_info (np->nn->file,
+  return file_get_storage_info (netfs_node_netnode (np)->file,
 				ports, num_ports,
 				ints, num_ints,
 				offsets, num_offsets,
@@ -795,8 +799,9 @@ netfs_S_file_exec (struct protid *user,
     return EOPNOTSUPP;
 
   pthread_mutex_lock (&user->po->np->lock);
-  err = check_openmodes (user->po->np->nn, O_EXEC, MACH_PORT_NULL);
-  file = user->po->np->nn->file;
+  err = check_openmodes (netfs_node_netnode (user->po->np),
+			 O_EXEC, MACH_PORT_NULL);
+  file = netfs_node_netnode (user->po->np)->file;
   if (!err)
     err = mach_port_mod_refs (mach_task_self (),
 			      file, MACH_PORT_RIGHT_SEND, 1);
@@ -806,7 +811,8 @@ netfs_S_file_exec (struct protid *user,
     {
       /* We cannot use MACH_MSG_TYPE_MOVE_SEND because we might need to
 	 retry an interrupted call that would have consumed the rights.  */
-      err = file_exec (user->po->np->nn->file, task, flags, argv, argvlen,
+      err = file_exec (netfs_node_netnode (user->po->np)->file,
+		       task, flags, argv, argvlen,
 		       envp, envplen, fds, MACH_MSG_TYPE_COPY_SEND, fdslen,
 		       portarray, MACH_MSG_TYPE_COPY_SEND, portarraylen,
 		       intarray, intarraylen, deallocnames, deallocnameslen,
@@ -838,7 +844,7 @@ netfs_S_io_map (struct protid *user,
   *rdobjtype = *wrobjtype = MACH_MSG_TYPE_MOVE_SEND;
 
   pthread_mutex_lock (&user->po->np->lock);
-  err = io_map (user->po->np->nn->file, rdobj, wrobj);
+  err = io_map (netfs_node_netnode (user->po->np)->file, rdobj, wrobj);
   pthread_mutex_unlock (&user->po->np->lock);
   return err;
 }
@@ -855,7 +861,7 @@ netfs_S_io_map_cntl (struct protid *user,
   *objtype = MACH_MSG_TYPE_MOVE_SEND;
 
   pthread_mutex_lock (&user->po->np->lock);
-  err = io_map_cntl (user->po->np->nn->file, obj);
+  err = io_map_cntl (netfs_node_netnode (user->po->np)->file, obj);
   pthread_mutex_unlock (&user->po->np->lock);
   return err;
 }
@@ -876,7 +882,8 @@ netfs_S_io_identity (struct protid *user,
   *idtype = *fsystype = MACH_MSG_TYPE_MOVE_SEND;
 
   pthread_mutex_lock (&user->po->np->lock);
-  err = io_identity (user->po->np->nn->file, id, fsys, fileno);
+  err = io_identity (netfs_node_netnode (user->po->np)->file,
+		     id, fsys, fileno);
   pthread_mutex_unlock (&user->po->np->lock);
   return err;
 }
@@ -891,7 +898,7 @@ netfs_S_##name (struct protid *user)		\
     return EOPNOTSUPP;				\
 						\
   pthread_mutex_lock (&user->po->np->lock);	\
-  err = name (user->po->np->nn->file);		\
+  err = name (netfs_node_netnode (user->po->np)->file);		\
   pthread_mutex_unlock (&user->po->np->lock);	\
   return err;					\
 }
@@ -913,7 +920,7 @@ netfs_S_io_prenotify (struct protid *user,
     return EOPNOTSUPP;
 
   pthread_mutex_lock (&user->po->np->lock);
-  err = io_prenotify (user->po->np->nn->file, start, stop);
+  err = io_prenotify (netfs_node_netnode (user->po->np)->file, start, stop);
   pthread_mutex_unlock (&user->po->np->lock);
   return err;
 }
@@ -928,7 +935,7 @@ netfs_S_io_postnotify (struct protid *user,
     return EOPNOTSUPP;
 
   pthread_mutex_lock (&user->po->np->lock);
-  err = io_postnotify (user->po->np->nn->file, start, stop);
+  err = io_postnotify (netfs_node_netnode (user->po->np)->file, start, stop);
   pthread_mutex_unlock (&user->po->np->lock);
   return err;
 }
@@ -971,7 +978,7 @@ netfs_demuxer (mach_msg_header_t *inp,
 	    | MACH_MSGH_BITS (MACH_MSG_TYPE_COPY_SEND,
 			      MACH_MSGH_BITS_REMOTE (inp->msgh_bits));
 	  inp->msgh_local_port = inp->msgh_remote_port;	/* reply port */
-	  inp->msgh_remote_port = cred->po->np->nn->file;
+	  inp->msgh_remote_port = netfs_node_netnode (cred->po->np)->file;
 	  err = mach_msg (inp, MACH_SEND_MSG, inp->msgh_size, 0,
 			  MACH_PORT_NULL, MACH_MSG_TIMEOUT_NONE,
 			  MACH_PORT_NULL);
-- 
cgit v1.2.3


From d0c565fc35e8dc3daa5fb6e9a514c34873e6b204 Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Wed, 28 May 2014 16:48:04 +0200
Subject: libdiskfs: remove the statistics code from the name cache

The current name cache lookup operation completes in O(n) time.  This
means that making the cache too large would decrease the performance.
Therefore it was required to tune the size, hence the need for
statistics.

We will use a data structure with worst case constant lookup times in
the future, removing the need to fine tune the cache size.

* libdiskfs/name-cache.c: Remove the statistics code from the name
cache.
---
 libdiskfs/name-cache.c | 66 +-------------------------------------------------
 1 file changed, 1 insertion(+), 65 deletions(-)

diff --git a/libdiskfs/name-cache.c b/libdiskfs/name-cache.c
index a212a6dc..25b5d0d9 100644
--- a/libdiskfs/name-cache.c
+++ b/libdiskfs/name-cache.c
@@ -45,29 +45,12 @@ struct lookup_cache
 
   /* Strlen of NAME.  If this is zero, it's an unused entry. */
   size_t name_len;
-
-  /* XXX */
-  int stati;
 };
 
 /* The contents of the cache in no particular order */
 static struct cacheq lookup_cache = { sizeof (struct lookup_cache) };
 
 static pthread_spinlock_t cache_lock = PTHREAD_SPINLOCK_INITIALIZER;
-
-/* Buffer to hold statistics */
-static struct stats
-{
-  long pos_hits;
-  long neg_hits;
-  long miss;
-  long fetch_errors;
-} statistics;
-
-#define PARTIAL_THRESH 100
-#define NPARTIALS MAXCACHE / PARTIAL_THRESH
-struct stats partial_stats [NPARTIALS];
-
 
 /* If there's an entry for NAME, of length NAME_LEN, in directory DIR in the
    cache, return its entry, otherwise 0.  CACHE_LOCK must be held.  */
@@ -85,10 +68,7 @@ find_cache (struct node *dir, const char *name, size_t name_len)
     if (c->name_len == name_len
 	&& c->dir_cache_id == dir->cache_id
 	&& c->name[0] == name[0] && strcmp (c->name, name) == 0)
-      {
-	c->stati = i / 100;
-	return c;
-      }
+      return c;
 
   return 0;
 }
@@ -152,46 +132,6 @@ diskfs_purge_lookup_cache (struct node *dp, struct node *np)
   pthread_spin_unlock (&cache_lock);
 }
 
-/* Register a negative hit for an entry in the Nth stat class */
-void
-register_neg_hit (int n)
-{
-  int i;
-
-  statistics.neg_hits++;
-
-  for (i = 0; i < n; i++)
-    partial_stats[i].miss++;
-  for (; i < NPARTIALS; i++)
-    partial_stats[i].neg_hits++;
-}
-
-/* Register a positive hit for an entry in the Nth stat class */
-void
-register_pos_hit (int n)
-{
-  int i;
-
-  statistics.pos_hits++;
-
-  for (i = 0; i < n; i++)
-    partial_stats[i].miss++;
-  for (; i < NPARTIALS; i++)
-    partial_stats[i].pos_hits++;
-}
-
-/* Register a miss */
-void
-register_miss ()
-{
-  int i;
-
-  statistics.miss++;
-  for (i = 0; i < NPARTIALS; i++)
-    partial_stats[i].miss++;
-}
-
-
 
 /* Scan the cache looking for NAME inside DIR.  If we don't know
    anything entry at all, then return 0.  If the entry is confirmed to
@@ -214,14 +154,12 @@ diskfs_check_lookup_cache (struct node *dir, const char *name)
       if (id == 0)
 	/* A negative cache entry.  */
 	{
-	  register_neg_hit (c->stati);
 	  pthread_spin_unlock (&cache_lock);
 	  return (struct node *)-1;
 	}
       else if (id == dir->cache_id)
 	/* The cached node is the same as DIR.  */
 	{
-	  register_pos_hit (c->stati);
 	  pthread_spin_unlock (&cache_lock);
 	  diskfs_nref (dir);
 	  return dir;
@@ -232,7 +170,6 @@ diskfs_check_lookup_cache (struct node *dir, const char *name)
 	  struct node *np;
 	  error_t err;
 
-	  register_pos_hit (c->stati);
 	  pthread_spin_unlock (&cache_lock);
 
 	  if (name[0] == '.' && name[1] == '.' && name[2] == '\0')
@@ -259,7 +196,6 @@ diskfs_check_lookup_cache (struct node *dir, const char *name)
 	}
     }
 
-  register_miss ();
   pthread_spin_unlock (&cache_lock);
 
   return 0;
-- 
cgit v1.2.3


From 2c7ecdc6ec8f9d9a27aa7e4e82fa2d84fa55fe9b Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Thu, 29 May 2014 02:03:03 +0200
Subject: libdiskfs: use a hash table for the name cache

Previously, name cache lookup operation completed in O(n) time.  This
means that making the cache too large would decrease the performance.
Therefore it was required to tune the size.

Implement the name cache using a hash table.

We use buckets of a fixed size.  We approximate the least-frequently
used cache algorithm by counting the number of lookups using
saturating arithmetic in the two lowest bits of the pointer to the
name.  Using this strategy we achieve a constant worst-case lookup and
insertion time.

Since we are not bound by the size of the cache anymore, increase its
size from 200 to 1024.

* libdiskfs/name-cache.c: Implement the name cache using a hash table.
(diskfs_enter_lookup_cache): Change accordingly.
(diskfs_purge_lookup_cache): Likewise.
(diskfs_check_lookup_cache): Likewise.  Also, hard code a
cache miss for the parent of the root directory and merge unlocking
and releasing of node references.
---
 libdiskfs/name-cache.c | 374 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 274 insertions(+), 100 deletions(-)

diff --git a/libdiskfs/name-cache.c b/libdiskfs/name-cache.c
index 25b5d0d9..d8f86b15 100644
--- a/libdiskfs/name-cache.c
+++ b/libdiskfs/name-cache.c
@@ -1,6 +1,6 @@
 /* Directory name lookup caching
 
-   Copyright (C) 1996, 1997, 1998 Free Software Foundation, Inc.
+   Copyright (C) 1996, 1997, 1998, 2014 Free Software Foundation, Inc.
    Written by Michael I. Bushnell, p/BSG, & Miles Bader.
 
    This file is part of the GNU Hurd.
@@ -20,118 +20,290 @@
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA. */
 
 #include "priv.h"
+#include <assert.h>
 #include <string.h>
-#include <cacheq.h>
 
-/* Maximum number of names to cache at once */
-#define MAXCACHE 200
+/* The name cache is implemented using a hash table.
 
-/* Maximum length of file name we bother caching */
-#define CACHE_NAME_LEN 100
+   We use buckets of a fixed size.  We approximate the
+   least-frequently used cache algorithm by counting the number of
+   lookups using saturating arithmetic in the two lowest bits of the
+   pointer to the name.  Using this strategy we achieve a constant
+   worst-case lookup and insertion time.  */
 
-/* Cache entry */
-struct lookup_cache
+/* Number of buckets.  Must be a power of two. */
+#define CACHE_SIZE	256
+
+/* Entries per bucket.  */
+#define BUCKET_SIZE	4
+
+/* A mask for fast binary modulo.  */
+#define CACHE_MASK	(CACHE_SIZE - 1)
+
+/* Cache bucket with BUCKET_SIZE entries.
+
+   The layout of the bucket is chosen so that it will be straight
+   forward to use vector operations in the future.  */
+struct cache_bucket
 {
-  struct cacheq_hdr hdr;
+  /* Name of the node NODE_CACHE_ID in the directory DIR_CACHE_ID.  If
+     NULL, the entry is unused.  */
+  unsigned long name[BUCKET_SIZE];
 
-  /* Used to indentify nodes to the fs dependent code.  0 for NODE_CACHE_ID
-     means a `negative' entry -- recording that there's definitely no node with
-     this name.  */
-  ino64_t dir_cache_id, node_cache_id;
+  /* The key.  */
+  unsigned long key[BUCKET_SIZE];
 
-  /* Name of the node NODE_CACHE_ID in the directory DIR_CACHE_ID.  Entries
-     with names too long to fit in this buffer aren't cached at all.  */
-  char name[CACHE_NAME_LEN];
+  /* Used to indentify nodes to the fs dependent code.  */
+  ino64_t dir_cache_id[BUCKET_SIZE];
 
-  /* Strlen of NAME.  If this is zero, it's an unused entry. */
-  size_t name_len;
+  /* 0 for NODE_CACHE_ID means a `negative' entry -- recording that
+     there's definitely no node with this name.  */
+  ino64_t node_cache_id[BUCKET_SIZE];
 };
 
-/* The contents of the cache in no particular order */
-static struct cacheq lookup_cache = { sizeof (struct lookup_cache) };
+/* The cache.  */
+static struct cache_bucket name_cache[CACHE_SIZE];
 
-static pthread_spinlock_t cache_lock = PTHREAD_SPINLOCK_INITIALIZER;
+/* Protected by this lock.  */
+static pthread_mutex_t cache_lock = PTHREAD_MUTEX_INITIALIZER;
 
-/* If there's an entry for NAME, of length NAME_LEN, in directory DIR in the
-   cache, return its entry, otherwise 0.  CACHE_LOCK must be held.  */
-static struct lookup_cache *
-find_cache (struct node *dir, const char *name, size_t name_len)
+/* Given VALUE, return the char pointer.  */
+static inline char *
+charp (unsigned long value)
 {
-  struct lookup_cache *c;
-  int i;
-
-  /* Search the list.  All unused entries are contiguous at the end of the
-     list, so we can stop searching when we see the first one.  */
-  for (i = 0, c = lookup_cache.mru;
-       c && c->name_len;
-       c = c->hdr.next, i++)
-    if (c->name_len == name_len
-	&& c->dir_cache_id == dir->cache_id
-	&& c->name[0] == name[0] && strcmp (c->name, name) == 0)
-      return c;
+  return (char *) (value & ~3L);
+}
 
-  return 0;
+/* Given VALUE, return the approximation of use frequency.  */
+static inline unsigned long
+frequ (unsigned long value)
+{
+  return value & 3;
 }
 
-/* Node NP has just been found in DIR with NAME.  If NP is null, that
-   means that this name has been confirmed as absent in the directory. */
-void
-diskfs_enter_lookup_cache (struct node *dir, struct node *np, const char *name)
+/* Add an entry in the Ith slot of the given bucket.  If there is a
+   value there, remove it first.  */
+static inline void
+add_entry (struct cache_bucket *b, int i,
+	   const char *name, unsigned long key,
+	   ino64_t dir_cache_id, ino64_t node_cache_id)
 {
-  struct lookup_cache *c;
-  size_t name_len = strlen (name);
+  if (b->name[i])
+    free (charp (b->name[i]));
 
-  if (name_len > CACHE_NAME_LEN - 1)
+  b->name[i] = (unsigned long) strdup (name);
+  assert ((b->name[i] & 3) == 0);
+  if (b->name[i] == 0)
     return;
 
-  pthread_spin_lock (&cache_lock);
+  b->key[i] = key;
+  b->dir_cache_id[i] = dir_cache_id;
+  b->node_cache_id[i] = node_cache_id;
+}
 
-  if (lookup_cache.length == 0)
-    /* There should always be an lru_cache; this being zero means that the
-       cache hasn't been initialized yet.  Do so.  */
-    cacheq_set_length (&lookup_cache, MAXCACHE);
+/* Remove the entry in the Ith slot of the given bucket.  */
+static inline void
+remove_entry (struct cache_bucket *b, int i)
+{
+  if (b->name[i])
+    free (charp (b->name[i]));
+  b->name[i] = 0;
+}
 
-  /* See if there's an old entry for NAME in DIR.  If not, replace the least
-     recently used entry.  */
-  c = find_cache (dir, name, name_len) ?: lookup_cache.lru;
+/* Check if the entry in the Ith slot of the given bucket is
+   valid.  */
+static inline int
+valid_entry (struct cache_bucket *b, int i)
+{
+  return b->name[i] != 0;
+}
+
+/* This is the Murmur3 hash algorithm.  */
+
+#define FORCE_INLINE inline __attribute__((always_inline))
+
+inline uint32_t rotl32 ( uint32_t x, int8_t r )
+{
+  return (x << r) | (x >> (32 - r));
+}
 
-  /* Fill C with the new entry.  */
-  c->dir_cache_id = dir->cache_id;
-  c->node_cache_id = np ? np->cache_id : 0;
-  strcpy (c->name, name);
-  c->name_len = name_len;
+#define ROTL32(x,y)     rotl32(x,y)
 
-  /* Now C becomes the MRU entry!  */
-  cacheq_make_mru (&lookup_cache, c);
+/* Block read - if your platform needs to do endian-swapping or can
+   only handle aligned reads, do the conversion here.  */
 
-  pthread_spin_unlock (&cache_lock);
+FORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i )
+{
+  return p[i];
+}
+
+/* Finalization mix - force all bits of a hash block to avalanche.  */
+
+FORCE_INLINE uint32_t fmix32 ( uint32_t h )
+{
+  h ^= h >> 16;
+  h *= 0x85ebca6b;
+  h ^= h >> 13;
+  h *= 0xc2b2ae35;
+  h ^= h >> 16;
+
+  return h;
+}
+
+/* The Murmur3 hash function.  */
+void MurmurHash3_x86_32 ( const void * key, int len,
+                          uint32_t seed, void * out )
+{
+  const uint8_t * data = (const uint8_t*)key;
+  const int nblocks = len / 4;
+
+  uint32_t h1 = seed;
+
+  const uint32_t c1 = 0xcc9e2d51;
+  const uint32_t c2 = 0x1b873593;
+
+  /* body */
+
+  const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
+
+  for(int i = -nblocks; i; i++)
+  {
+    uint32_t k1 = getblock32(blocks,i);
+
+    k1 *= c1;
+    k1 = ROTL32(k1,15);
+    k1 *= c2;
+
+    h1 ^= k1;
+    h1 = ROTL32(h1,13);
+    h1 = h1*5+0xe6546b64;
+  }
+
+  /* tail */
+
+  const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
+
+  uint32_t k1 = 0;
+
+  switch(len & 3)
+  {
+  case 3: k1 ^= tail[2] << 16;
+  case 2: k1 ^= tail[1] << 8;
+  case 1: k1 ^= tail[0];
+          k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
+  };
+
+  /* finalization */
+
+  h1 ^= len;
+
+  h1 = fmix32(h1);
+
+  *(uint32_t*)out = h1;
 }
 
-/* Purge all references in the cache to NP as a node inside
-   directory DP. */
-void
-diskfs_purge_lookup_cache (struct node *dp, struct node *np)
+/* If there is no best candidate to replace, pick any.  We approximate
+   any by picking the slot depicted by REPLACE, and increment REPLACE
+   then.  */
+static int replace;
+
+/* Lookup (DIR_CACHE_ID, NAME, KEY) in the cache.  If it is found,
+   return 1 and set BUCKET and INDEX to the item.  Otherwise, return 0
+   and set BUCKET and INDEX to the slot where the item should be
+   inserted.  */
+static inline int
+lookup (ino64_t dir_cache_id, const char *name, unsigned long key,
+	struct cache_bucket **bucket, int *index)
 {
-  struct lookup_cache *c, *next;
+  struct cache_bucket *b = *bucket = &name_cache[key & CACHE_MASK];
+  unsigned long best = 3;
+  int i;
 
-  pthread_spin_lock (&cache_lock);
-  for (c = lookup_cache.mru; c; c = next)
+  for (i = 0; i < BUCKET_SIZE; i++)
     {
-      /* Save C->hdr.next, since we may move C from this position. */
-      next = c->hdr.next;
+      unsigned long f = frequ (b->name[i]);
+
+      if (valid_entry (b, i)
+	  && b->key[i] == key
+	  && b->dir_cache_id[i] == dir_cache_id
+	  && strcmp (charp (b->name[i]), name) == 0)
+	{
+	  if (f < 3)
+	    b->name[i] += 1;
+
+	  *index = i;
+	  return 1;
+	}
 
-      if (c->name_len
-	  && c->dir_cache_id == dp->cache_id
-	  && c->node_cache_id == np->cache_id)
+      /* Keep track of the replacement candidate.  */
+      if (f < best)
 	{
-	  c->name_len = 0;
-	  cacheq_make_lru (&lookup_cache, c); /* Use C as the next free
-						 entry. */
+	  best = f;
+	  *index = i;
 	}
     }
-  pthread_spin_unlock (&cache_lock);
+
+  /* If there was no entry with a lower use frequency, just replace
+     any entry.  */
+  if (best == 3)
+    {
+      *index = replace;
+      replace = (replace + 1) & (BUCKET_SIZE - 1);
+    }
+
+  return 0;
+}
+
+/* Hash the directory cache_id and the name.  */
+static inline unsigned long
+hash (ino64_t dir_cache_id, const char *name)
+{
+  unsigned long h;
+  MurmurHash3_x86_32 (&dir_cache_id, sizeof dir_cache_id, 0, &h);
+  MurmurHash3_x86_32 (name, strlen (name), h, &h);
+  return h;
+}
+
+/* Node NP has just been found in DIR with NAME.  If NP is null, that
+   means that this name has been confirmed as absent in the directory. */
+void
+diskfs_enter_lookup_cache (struct node *dir, struct node *np, const char *name)
+{
+  unsigned long key = hash (dir->cache_id, name);
+  ino64_t value = np ? np->cache_id : 0;
+  struct cache_bucket *bucket;
+  int i = 0, found;
+
+  pthread_mutex_lock (&cache_lock);
+  found = lookup (dir->cache_id, name, key, &bucket, &i);
+  if (! found)
+    add_entry (bucket, i, name, key, dir->cache_id, value);
+  else
+    if (bucket->node_cache_id[i] != value)
+      bucket->node_cache_id[i] = value;
+
+  pthread_mutex_unlock (&cache_lock);
 }
 
+/* Purge all references in the cache to NP as a node inside
+   directory DP. */
+void
+diskfs_purge_lookup_cache (struct node *dp, struct node *np)
+{
+  int i;
+  struct cache_bucket *b;
+
+  pthread_mutex_lock (&cache_lock);
+
+  for (b = &name_cache[0]; b < &name_cache[CACHE_SIZE]; b++)
+    for (i = 0; i < BUCKET_SIZE; i++)
+      if (valid_entry (b, i)
+	  && b->dir_cache_id[i] == dp->cache_id
+	  && b->node_cache_id[i] == np->cache_id)
+	remove_entry (b, i);
+
+  pthread_mutex_unlock (&cache_lock);
+}
 
 /* Scan the cache looking for NAME inside DIR.  If we don't know
    anything entry at all, then return 0.  If the entry is confirmed to
@@ -140,27 +312,28 @@ diskfs_purge_lookup_cache (struct node *dp, struct node *np)
 struct node *
 diskfs_check_lookup_cache (struct node *dir, const char *name)
 {
-  struct lookup_cache *c;
-
-  pthread_spin_lock (&cache_lock);
-
-  c = find_cache (dir, name, strlen (name));
-  if (c)
+  unsigned long key = hash (dir->cache_id, name);
+  int lookup_parent = name[0] == '.' && name[1] == '.' && name[2] == '\0';
+  struct cache_bucket *bucket;
+  int i, found;
+
+  if (lookup_parent && dir == diskfs_root_node)
+    /* This is outside our file system, return cache miss.  */
+    return NULL;
+
+  pthread_mutex_lock (&cache_lock);
+  found = lookup (dir->cache_id, name, key, &bucket, &i);
+  if (found)
     {
-      int id = c->node_cache_id;
-
-      cacheq_make_mru (&lookup_cache, c); /* Record C as recently used.  */
+      ino64_t id = bucket->node_cache_id[i];
+      pthread_mutex_unlock (&cache_lock);
 
       if (id == 0)
 	/* A negative cache entry.  */
-	{
-	  pthread_spin_unlock (&cache_lock);
-	  return (struct node *)-1;
-	}
+	return (struct node *) -1;
       else if (id == dir->cache_id)
 	/* The cached node is the same as DIR.  */
 	{
-	  pthread_spin_unlock (&cache_lock);
 	  diskfs_nref (dir);
 	  return dir;
 	}
@@ -170,9 +343,7 @@ diskfs_check_lookup_cache (struct node *dir, const char *name)
 	  struct node *np;
 	  error_t err;
 
-	  pthread_spin_unlock (&cache_lock);
-
-	  if (name[0] == '.' && name[1] == '.' && name[2] == '\0')
+	  if (lookup_parent)
 	    {
 	      pthread_mutex_unlock (&dir->lock);
 	      err = diskfs_cached_lookup (id, &np);
@@ -181,14 +352,18 @@ diskfs_check_lookup_cache (struct node *dir, const char *name)
 	      /* In the window where DP was unlocked, we might
 		 have lost.  So check the cache again, and see
 		 if it's still there; if so, then we win. */
-	      c = find_cache (dir, "..", 2);
-	      if (!c || c->node_cache_id != id)
+	      pthread_mutex_lock (&cache_lock);
+	      found = lookup (dir->cache_id, name, key, &bucket, &i);
+	      if (! found
+		  || ! bucket->node_cache_id[i] != id)
 		{
+		  pthread_mutex_unlock (&cache_lock);
+
 		  /* Lose */
-		  pthread_mutex_unlock (&np->lock);
-		  diskfs_nrele (np);
+		  diskfs_nput (np);
 		  return 0;
 		}
+	      pthread_mutex_unlock (&cache_lock);
 	    }
 	  else
 	    err = diskfs_cached_lookup (id, &np);
@@ -196,7 +371,6 @@ diskfs_check_lookup_cache (struct node *dir, const char *name)
 	}
     }
 
-  pthread_spin_unlock (&cache_lock);
-
+  pthread_mutex_unlock (&cache_lock);
   return 0;
 }
-- 
cgit v1.2.3