fatfs virtual inodes

[marco]

Hi,

Included with this mail is a patch for virt-inode.c. I have rewritten most
of its code so it uses hash tables. Marcus and I talked about this and he
made some notes about this (TODO in fatfs-0.4, in the top of virt-inode.c
in CVS)... Is this what you wanted Marcus (IOW, does this solve the
problems you had with this code)?

I also have a question about diskfs translators in the Hurd. There is a
function called inode_init in inode.c in most diskfs translators. Is this
code useless because the table will be initialized with 0's and who calls
this function? Looks like dead code to me, but I have used this in this
fatfs patch too be sure...

Thanks,
Marco Gerards

2003-05-01  Marco Gerards  <metgerards@student.han.nl>
        * virt-inode.c: (struct v_inode): Add members inode, hnext and
hnextkey.
        (struct table_page): Removed.
        (LOG2_TABLE_PAGE_SIZE): Likewise.
        (TABLE_PAGE_SIZE): Likewise.
        (v_inodehash): Add hashtable to lookup by inode number.
        (keyhash): Add hashtable to lookup by key.
        (vikey_hash): Add function.
        (v_inode_init): Likewise.
        (key_init): Likewise.
        (_vi_new): Rewritten to use the hashtables.
        (vi_lookup): Likewise.
        (vi_rlookup): Likewise.
        (vi_free): Likewise.

--- fatfs/virt-inode.c  2002-12-03 21:52:59.000000000 +0100
+++ fatfs.mg/virt-inode.c       2003-05-01 00:09:07.000000000 +0200
@@ -1,5 +1,5 @@
 /* Virtual Inode management routines
-   Copyright (C) 2002 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003 Free Software Foundation, Inc.
    Written by Marcus Brinkmann.

    This file is part of the GNU Hurd.
@@ -18,12 +18,6 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA. */

-/* TODO: Improve NEW by keeping a bitmap of free inodes.
-   TODO: Improve RLOOKUP by keeping an open hash for keys (need to change
-   CHANGE and FREE, too).
-   TODO: Improve FREE by keeping the highest inode in use and keep it
-   up-to-date. When a table page can be freed, do so.  */
-
 #include <stdlib.h>
 #include <assert.h>
 #include <string.h>
@@ -32,29 +26,61 @@

 /* Each virtual inode contains the UNIQUE key it belongs to,
    which must not be zero.  */
-
 vi_key_t vi_zero_key = {0, 0};

 struct v_inode
 {
   vi_key_t key;
+  ino_t inode;
+  /* Next entry in the inode hashtable.  */
+  struct v_inode *hnext;
+  /* Next entry in the key hashtable.  */
+  struct v_inode *hnextkey;
 };

-/* All inodes are stored in a table by their index number - 1.
-   Decrementing by one is necessary because inode numbers start from 1,
-   but our table is zero based.  */
-
-#define LOG2_TABLE_PAGE_SIZE 10
-#define TABLE_PAGE_SIZE (1 << LOG2_TABLE_PAGE_SIZE)
-
-struct table_page
-{
-  struct table_page *next;
-
-  struct v_inode vi[TABLE_PAGE_SIZE];
-};

-struct table_page *inode_table;
+#define VINOHSZ  1024
+#if     ((VINOHSZ&(VINOHSZ-1)) == 0)
+#define VINOHASH(v_ino)    ((v_ino)&(VINOHSZ-1))
+#else
+#define VINOHASH(v_ino)    (((unsigned)(v_ino))%VINOHSZ)
+#endif
+
+#define KEYHSZ  1024
+#if     ((KEYHSZ&(KEYHSZ-1)) == 0)
+#define KEYHASH(key)    ((key)&(KEYHSZ-1))
+#else
+#define KEYHASH(key)    (((unsigned)(key))%KEYHSZ)
+#endif
+
+static struct v_inode *v_inodehash[VINOHSZ];
+static struct v_inode *keyhash[KEYHSZ];
+static ino64_t lastalloc = 0;
+
+/* Calculate a hashkey from the vi key KEY.  */
+int
+vikey_hash (vi_key_t key)
+{
+  return KEYHASH (key.dir_inode + key.dir_offset * 123);
+}
+
+/* Initialize the inode hash table.  */
+void
+v_inode_init ()
+{
+  int n;
+  for (n = 0; n < VINOHSZ; n++)
+    v_inodehash[n] = 0;
+}
+
+/* Initialize the key hash table.  */
+void
+key_init ()
+{
+  int n;
+  for (n = 0; n < KEYHSZ; n++)
+    keyhash[n] = 0;
+}

 spin_lock_t inode_table_lock = SPIN_LOCK_INITIALIZER;

@@ -62,49 +88,19 @@ spin_lock_t inode_table_lock = SPIN_LOCK
 error_t
 _vi_new(vi_key_t key, ino_t *inode, inode_t *v_inode)
 {
-  struct table_page *table = inode_table;
-  struct table_page *prev_table = 0;
-  int page = 0;
-  int offset = 0;
-
-  while (table && memcmp(&vi_zero_key, &table->vi[offset].key,
sizeof(vi_key_t)))
-    {
-      offset++;
-      if (offset == TABLE_PAGE_SIZE)
-       {
-         offset = 0;
-         page++;
-         prev_table = table;
-         table = table->next;
-       }
-    }
+  inode_t newino = malloc (sizeof (struct v_inode));

-  if (table)
-    {
-      table->vi[offset].key = key;
-      /* See above for rationale of increment. */
-      *inode = (page << LOG2_TABLE_PAGE_SIZE) + offset + 1;
-      *v_inode = &table->vi[offset];
-    }
-  else
-    {
-      struct table_page **pagep;
+  *inode = ++lastalloc;
+  newino->key = key;
+  newino->inode = *inode;
+
+  /* Put the virtual inode in both hashtables.  */
+  v_inodehash[VINOHASH(*inode)] = newino;
+  keyhash[vikey_hash(key)] = newino;
+  newino->hnext = v_inodehash[VINOHASH(*inode)];
+  newino->hnextkey = keyhash[vikey_hash(key)];

-      if (prev_table)
-       pagep = &prev_table->next;
-      else
-       pagep = &inode_table;
-      *pagep = (struct table_page *) malloc (sizeof (struct table_page));
-      if (!*pagep)
-       {
-         return ENOSPC;
-       }
-      memset (*pagep, 0, sizeof (struct table_page));
-      (*pagep)->vi[0].key = key;
-      /* See above for rationale of increment. */
-      *inode = (page << LOG2_TABLE_PAGE_SIZE) + 1;
-      *v_inode = &(*pagep)->vi[0];
-    }
+  *v_inode = newino;

   return 0;
 }
@@ -138,26 +134,22 @@ vi_key(inode_t v_inode)
 inode_t
 vi_lookup(ino_t inode)
 {
-  struct table_page *table = inode_table;
-  /* See above for rationale of decrement. */
-  int page = (inode - 1) >> LOG2_TABLE_PAGE_SIZE;
-  int offset = (inode - 1) & (TABLE_PAGE_SIZE - 1);
-  inode_t v_inode = 0;
+  inode_t v_inode;

   spin_lock (&inode_table_lock);

-  while (table && page > 0)
+  for (v_inode = v_inodehash[VINOHASH(inode)]; v_inode;
+       v_inode = v_inode->hnext)
     {
-      page--;
-      table = table->next;
+      if (v_inode->inode == inode)
+       {
+         spin_unlock (&inode_table_lock);
+         return v_inode;
+       }
     }

-  if (table)
-    v_inode = &table->vi[offset];
-
   spin_unlock (&inode_table_lock);
-
-  return v_inode;
+  return 0;
 }

 /* Get the inode number and virtual inode belonging to key KEY.
@@ -167,38 +159,28 @@ error_t
 vi_rlookup(vi_key_t key, ino_t *inode, inode_t *v_inode, int create)
 {
   error_t err = 0;
-  struct table_page *table = inode_table;
-  int page = 0;
-  int offset = 0;
-
-  assert (memcmp(&vi_zero_key, &key, sizeof (vi_key_t)));
-
+  inode_t vi;
+
   spin_lock (&inode_table_lock);
-
-  while (table && memcmp(&table->vi[offset].key, &key, sizeof (vi_key_t)))
+
+  /* Search for the virtual inode.  */
+  for (vi = keyhash[vikey_hash(key)]; vi; vi = vi->hnextkey)
     {
-      offset++;
-      if (offset == TABLE_PAGE_SIZE)
+      if (!memcmp (&key, &vi->key, sizeof (vi_key_t)))
        {
-         offset = 0;
-         page++;
-         table = table->next;
+         *inode = vi->inode;
+         *v_inode = vi;
+         spin_unlock (&inode_table_lock);
+         return 0;
        }
     }

-  if (table)
-    {
-      /* See above for rationale of increment. */
-      *inode = (page << LOG2_TABLE_PAGE_SIZE) + offset + 1;
-      *v_inode = &table->vi[offset];
-    }
+  /* The virtual inode has not been found for this key, create one if create
+     was set.  */
+  if (create)
+    _vi_new (key, inode, v_inode);
   else
-    {
-      if (create)
-       err = _vi_new (key, inode, v_inode);
-      else
-       err = EINVAL;
-    }
+    err = EINVAL;

   spin_unlock (&inode_table_lock);

@@ -221,15 +203,39 @@ vi_key_t vi_change(inode_t v_inode, vi_k
 vi_key_t vi_free(inode_t v_inode)
 {
   vi_key_t key;
+  inode_t vi;
+
   spin_lock (&inode_table_lock);
   key = v_inode->key;
-  v_inode->key = vi_zero_key;
-  spin_unlock (&inode_table_lock);
-  return key;
-}
-

+  /* XXX: The previous virt. inode is not stored and has to be
+     found. This is not stored because there will be many virt. inodes
+     stored in memory (one for every file) and this costs a lot of
+     memory.  */
+
+  /* Remove the virt. inode from the key hashtable.  */
+  for (vi = keyhash[vikey_hash(key)]; vi; vi = vi->hnextkey)
+    {
+      if (vi->hnextkey->inode == v_inode->inode)
+       {
+         vi->hnextkey = v_inode->hnextkey;
+         break;
+       }
+    }

+  /* Remove the virt. inode from the inode hashtable.  */
+  for (vi = v_inodehash[VINOHASH(v_inode->inode)]; vi; vi = vi->hnext)
+    {
+      if (vi->hnext->inode == v_inode->inode)
+       {
+         vi->hnext = v_inode->hnext;
+         break;
+       }
+    }

+  spin_unlock (&inode_table_lock);

+  free (v_inode);

+  return key;
+}