Work on in-memory filesystem representation.

[bluesky.git] / dir.c

diff --git a/dir.c b/dir.c
new file mode 100644 (file)
index 0000000..c4cbec2
--- /dev/null
+++ b/dir.c
@@ -0,0 +1,122 @@
+/* Blue Sky: File Systems in the Cloud
+ *
+ * Copyright (C) 2009  The Regents of the University of California
+ * Written by Michael Vrable <mvrable@cs.ucsd.edu>
+ *
+ * TODO: Licensing
+ */
+
+#include <stdint.h>
+#include <glib.h>
+
+#include "bluesky.h"
+
+/* Core filesystem: handling of directories. */
+
+/* Hash a filename for a directory lookup.  The string is hashed to a 64-bit
+ * value.  It is guaranteed that the hash values 0, 1, and 2 are never returned
+ * (to allow the hash value to be used as an NFS cookie for a READDIR
+ * operation). */
+uint64_t bluesky_directory_hash(gchar *name)
+{
+    GChecksum *csum = g_checksum_new(G_CHECKSUM_MD5);
+    g_checksum_update(csum, (guchar *)name, -1);
+
+    guint64 hashbytes[2];
+    gsize hashsize = sizeof(hashbytes);
+    g_checksum_get_digest(csum, (guint8 *)hashbytes, &hashsize);
+
+    uint64_t hash = GUINT64_FROM_BE(hashbytes[0]);
+    if (hash < 3)
+        hash = 3;
+
+    g_checksum_free(csum);
+
+    return hash;
+}
+
+void bluesky_dirent_destroy(gpointer data)
+{
+    BlueSkyDirent *dirent = (BlueSkyDirent *)data;
+    g_free(dirent->name);
+    g_free(dirent);
+}
+
+static gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
+                                   gpointer unused)
+{
+    /* We can't simply subtract the hash values, since they are 64-bit and the
+     * result could overflow when converted to a gint. */
+    uint64_t hash1 = ((const BlueSkyDirent *)a)->hash;
+    uint64_t hash2 = ((const BlueSkyDirent *)b)->hash;
+
+    if (hash1 < hash2)
+        return -1;
+    else if (hash1 > hash2)
+        return 1;
+    else
+        return 0;
+}
+
+/* Perform a lookup for a file name within a directory.  Returns the inode
+ * number if found, or 0 if not (0 is never a valid inode number).  Should be
+ * called with the inode lock already held. */
+uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
+{
+    g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
+    g_return_val_if_fail(inode->dirents != NULL, 0);
+
+    /* First, construct a hash of the file name.  Search the directory for a
+     * match, then check to see if it does really match. */
+    uint64_t hash = bluesky_directory_hash(name);
+
+    BlueSkyDirent d = {name, hash, 0};
+    GSequenceIter *i = g_sequence_search(inode->dirents, &d,
+                                         bluesky_dirent_compare, NULL);
+    i = g_sequence_iter_prev(i);
+
+    if (g_sequence_iter_is_end(i))
+        return 0;
+    BlueSkyDirent *dirent = g_sequence_get(i);
+    g_print("Lookup(%s) -> 0x%016llx\n", name, dirent->hash);
+    if (dirent->hash != hash)
+        return 0;
+    if (g_strcmp0(name, dirent->name) != 0)
+        return 0;
+
+    return dirent->inum;
+}
+
+/* Insert a new entry into a directory.  Should be called with the inode lock
+ * already held. */
+gboolean bluesky_directory_insert(BlueSkyInode *dir, gchar *name, uint64_t inum)
+{
+    /* First, construct a hash of the file name.  Search the directory for a
+     * match, then check to see if it does really match. */
+    uint64_t hash = bluesky_directory_hash(name);
+
+    BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
+    d->name = name;
+    d->hash = hash;
+    d->inum = inum;
+
+    GSequenceIter *i = g_sequence_search(dir->dirents, d,
+                                         bluesky_dirent_compare, NULL);
+    g_sequence_insert_before(i, d);
+
+    return TRUE;
+}
+
+/* Dump the contents of a directory to stdout.  Debugging only. */
+void bluesky_directory_dump(BlueSkyInode *dir)
+{
+    g_print("Directory dump:\n");
+
+    GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
+
+    while (!g_sequence_iter_is_end(i)) {
+        BlueSkyDirent *d = g_sequence_get(i);
+        g_print("    0x%016llx [inum=%lld] %s\n", d->hash, d->inum, d->name);
+        i = g_sequence_iter_next(i);
+    }
+}