dir.c

   1 /* Blue Sky: File Systems in the Cloud
   2  *
   3  * Copyright (C) 2009  The Regents of the University of California
   4  * Written by Michael Vrable <mvrable@cs.ucsd.edu>
   5  *
   6  * TODO: Licensing
   7  */
   8
   9 #include <stdint.h>
  10 #include <glib.h>
  11
  12 #include "bluesky.h"
  13
  14 /* Core filesystem: handling of directories. */
  15
  16 /* Hash a filename for a directory lookup.  The string is hashed to a 64-bit
  17  * value.  It is guaranteed that the hash values 0, 1, and 2 are never returned
  18  * (to allow the hash value to be used as an NFS cookie for a READDIR
  19  * operation).  TODO: We perhaps should make this a keyed hash, and may want to
  20  * use something cheaper than MD5 to compute. */
  21 uint64_t bluesky_directory_hash(gchar *name)
  22 {
  23     GChecksum *csum = g_checksum_new(G_CHECKSUM_MD5);
  24     g_checksum_update(csum, (guchar *)name, -1);
  25
  26     guint64 hashbytes[2];
  27     gsize hashsize = sizeof(hashbytes);
  28     g_checksum_get_digest(csum, (guint8 *)hashbytes, &hashsize);
  29
  30     uint64_t hash = GUINT64_FROM_BE(hashbytes[0]);
  31     if (hash < 3)
  32         hash = 3;
  33
  34     g_checksum_free(csum);
  35
  36     return hash;
  37 }
  38
  39 void bluesky_dirent_destroy(gpointer data)
  40 {
  41     BlueSkyDirent *dirent = (BlueSkyDirent *)data;
  42     g_free(dirent->name);
  43     g_free(dirent);
  44 }
  45
  46 static gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
  47                                    gpointer unused)
  48 {
  49     /* We can't simply subtract the hash values, since they are 64-bit and the
  50      * result could overflow when converted to a gint. */
  51     uint64_t hash1 = ((const BlueSkyDirent *)a)->hash;
  52     uint64_t hash2 = ((const BlueSkyDirent *)b)->hash;
  53
  54     if (hash1 < hash2)
  55         return -1;
  56     else if (hash1 > hash2)
  57         return 1;
  58     else
  59         return 0;
  60 }
  61
  62 /* Perform a lookup for a file name within a directory.  Returns the inode
  63  * number if found, or 0 if not (0 is never a valid inode number).  Should be
  64  * called with the inode lock already held. */
  65 uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
  66 {
  67     g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
  68     g_return_val_if_fail(inode->dirents != NULL, 0);
  69
  70     /* First, construct a hash of the file name.  Search the directory for a
  71      * match, then check to see if it does really match. */
  72     uint64_t hash = bluesky_directory_hash(name);
  73
  74     BlueSkyDirent d = {name, hash, 0};
  75     GSequenceIter *i = g_sequence_search(inode->dirents, &d,
  76                                          bluesky_dirent_compare, NULL);
  77
  78     /* g_sequence_search will return an iterator pointing just beyond the
  79      * desired node if there is a match, so that when inserting the new node
  80      * will go after the match.  But we are trying to do a lookup, so back up
  81      * by one position. */
  82     i = g_sequence_iter_prev(i);
  83
  84     if (g_sequence_iter_is_end(i))
  85         return 0;
  86     BlueSkyDirent *dirent = g_sequence_get(i);
  87     if (dirent->hash != hash)
  88         return 0;
  89     if (g_strcmp0(name, dirent->name) != 0)
  90         return 0;
  91
  92     g_print("Lookup(%s) -> 0x%016llx\n", name, dirent->hash);
  93     return dirent->inum;
  94 }
  95
  96 /* Insert a new entry into a directory.  Should be called with the inode lock
  97  * already held. */
  98 gboolean bluesky_directory_insert(BlueSkyInode *dir, gchar *name, uint64_t inum)
  99 {
 100     /* First, construct a hash of the file name.  Search the directory for a
 101      * match, then check to see if it does really match. */
 102     uint64_t hash = bluesky_directory_hash(name);
 103
 104     BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
 105     d->name = g_strdup(name);
 106     d->hash = hash;
 107     d->inum = inum;
 108
 109     GSequenceIter *i = g_sequence_search(dir->dirents, d,
 110                                          bluesky_dirent_compare, NULL);
 111
 112     /* If a directory entry already exists, return failure.  The caller must
 113      * delete the old entry and try again.  TODO: We'll fail on a hash
 114      * collision; we should handle that case. */
 115     if (!g_sequence_iter_is_end(g_sequence_iter_prev(i))) {
 116         BlueSkyDirent *d2 = g_sequence_get(g_sequence_iter_prev(i));
 117         if (d2->hash == hash)
 118             return FALSE;
 119     }
 120
 121     g_sequence_insert_before(i, d);
 122     dir->change_count++;
 123
 124     return TRUE;
 125 }
 126
 127 /* Dump the contents of a directory to stdout.  Debugging only. */
 128 void bluesky_directory_dump(BlueSkyInode *dir)
 129 {
 130     g_print("Directory dump:\n");
 131
 132     GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
 133
 134     while (!g_sequence_iter_is_end(i)) {
 135         BlueSkyDirent *d = g_sequence_get(i);
 136         g_print("    0x%016llx [inum=%lld] %s\n", d->hash, d->inum, d->name);
 137         i = g_sequence_iter_next(i);
 138     }
 139 }