From a6d16121ebce069728e454b9bd4c5716d59c8809 Mon Sep 17 00:00:00 2001 From: Michael Vrable Date: Thu, 20 Aug 2009 17:15:41 -0700 Subject: [PATCH] Work on in-memory filesystem representation. --- Makefile | 8 +-- inode.h => bluesky.h | 21 +++++++- dir.c | 122 +++++++++++++++++++++++++++++++++++++++++++ inode.c | 65 +---------------------- main.c | 39 ++++++++++++++ 5 files changed, 185 insertions(+), 70 deletions(-) rename inode.h => bluesky.h (77%) create mode 100644 dir.c create mode 100644 main.c diff --git a/Makefile b/Makefile index 593f4d4..386cc23 100644 --- a/Makefile +++ b/Makefile @@ -1,17 +1,17 @@ -PACKAGES=glib-2.0 +PACKAGES=glib-2.0 gthread-2.0 DEBUG=-g CFLAGS=-O -Wall -D_FILE_OFFSET_BITS=64 $(DEBUG) \ $(shell pkg-config --cflags $(PACKAGES)) LDFLAGS=$(DEBUG) $(shell pkg-config --libs $(PACKAGES)) -SRCS=nfsd.c rpc.c mount.c mount_prot_xdr.c +SRCS=dir.c inode.c main.c OBJS=$(SRCS:.c=.o) -nfsproxy : $(OBJS) +bluesky : $(OBJS) $(CC) $(LDFLAGS) -o $@ $^ clean : - rm -f $(OBJS) nfsproxy + rm -f $(OBJS) bluesky dep : touch Makefile.dep diff --git a/inode.h b/bluesky.h similarity index 77% rename from inode.h rename to bluesky.h index 23361c5..068173f 100644 --- a/inode.h +++ b/bluesky.h @@ -1,5 +1,13 @@ -#ifndef _BLUESKY_INODE_H -#define _BLUESKY_INODE_H +/* Blue Sky: File Systems in the Cloud + * + * Copyright (C) 2009 The Regents of the University of California + * Written by Michael Vrable + * + * TODO: Licensing + */ + +#ifndef _BLUESKY_H +#define _BLUESKY_H #include #include @@ -70,6 +78,15 @@ typedef struct { uint64_t inum; } BlueSkyDirent ; +int64_t bluesky_get_current_time(); +uint64_t bluesky_fs_alloc_inode(BlueSkyFS *fs); +BlueSkyInode *bluesky_new_inode(uint64_t inum); + +void bluesky_dirent_destroy(gpointer dirent); uint64_t bluesky_directory_hash(gchar *name); +uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name); +gboolean bluesky_directory_insert(BlueSkyInode *dir, gchar *name, + uint64_t inum); +void bluesky_directory_dump(BlueSkyInode *dir); #endif diff --git a/dir.c b/dir.c new file mode 100644 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 + * + * TODO: Licensing + */ + +#include +#include + +#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); + } +} diff --git a/inode.c b/inode.c index 5f31326..ec90757 100644 --- a/inode.c +++ b/inode.c @@ -9,27 +9,13 @@ #include #include -#include "inode.h" +#include "bluesky.h" /* Core filesystem. Different proxies, such as the NFSv3 one, interface to * this, but the core actually tracks the data which is stored. So far we just * implement an in-memory filesystem, but eventually this will be state which * is persisted to the cloud. */ - -/* Hash a filename for a directory lookup. The string is hashed to a 64-bit - * value. */ -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); - return GUINT64_FROM_LE(hashbytes[0]); -} - /* Return the current time, in microseconds since the epoch. */ int64_t bluesky_get_current_time() { @@ -61,52 +47,3 @@ BlueSkyInode *bluesky_new_inode(uint64_t inum) return i; } - -void bluesky_dirent_destroy(BlueSkyDirent *dirent) -{ - g_free(dirent->name); - g_free(dirent); -} - -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); - - if (g_sequence_iter_is_end(i)) - return 0; - BlueSkyDirent *dirent = g_sequence_get(i); - if (dirent->hash != hash) - return 0; - if (g_strcmp0(name, dirent->name) != 0) - return 0; - - return dirent->inum; -} diff --git a/main.c b/main.c new file mode 100644 index 0000000..6ddc7b4 --- /dev/null +++ b/main.c @@ -0,0 +1,39 @@ +/* Blue Sky: File Systems in the Cloud + * + * Copyright (C) 2009 The Regents of the University of California + * Written by Michael Vrable + * + * TODO: Licensing + */ + +#include +#include +#include +#include + +#include "bluesky.h" + +/* Small test program for BlueSkyFS. Doesn't do much useful. */ + +int main(int argc, char *argv[]) +{ + g_thread_init(NULL); + + printf("BlueSkyFS starting...\n"); + + BlueSkyInode *root = bluesky_new_inode(1); + root->type = BLUESKY_DIRECTORY; + root->dirents = g_sequence_new(bluesky_dirent_destroy); + + bluesky_directory_insert(root, "foo", 2); + bluesky_directory_insert(root, "bar", 3); + bluesky_directory_insert(root, "baz", 4); + bluesky_directory_insert(root, "baz", 5); + + bluesky_directory_dump(root); + bluesky_directory_lookup(root, "foo"); + bluesky_directory_lookup(root, "bar"); + bluesky_directory_lookup(root, "baz"); + + return 0; +} -- 2.20.1