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). */
  20 uint64_t bluesky_directory_hash(gchar *name)
  21 {
  22     GChecksum *csum = g_checksum_new(G_CHECKSUM_MD5);
  23     g_checksum_update(csum, (guchar *)name, -1);
  24
  25     guint64 hashbytes[2];
  26     gsize hashsize = sizeof(hashbytes);
  27     g_checksum_get_digest(csum, (guint8 *)hashbytes, &hashsize);
  28
  29     uint64_t hash = GUINT64_FROM_BE(hashbytes[0]);
  30     if (hash < 3)
  31         hash = 3;
  32
  33     g_checksum_free(csum);
  34
  35     return hash;
  36 }
  37
  38 void bluesky_dirent_destroy(gpointer data)
  39 {
  40     BlueSkyDirent *dirent = (BlueSkyDirent *)data;
  41     g_free(dirent->name);
  42     g_free(dirent);
  43 }
  44
  45 static gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
  46                                    gpointer unused)
  47 {
  48     /* We can't simply subtract the hash values, since they are 64-bit and the
  49      * result could overflow when converted to a gint. */
  50     uint64_t hash1 = ((const BlueSkyDirent *)a)->hash;
  51     uint64_t hash2 = ((const BlueSkyDirent *)b)->hash;
  52
  53     if (hash1 < hash2)
  54         return -1;
  55     else if (hash1 > hash2)
  56         return 1;
  57     else
  58         return 0;
  59 }
  60
  61 /* Perform a lookup for a file name within a directory.  Returns the inode
  62  * number if found, or 0 if not (0 is never a valid inode number).  Should be
  63  * called with the inode lock already held. */
  64 uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
  65 {
  66     g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
  67     g_return_val_if_fail(inode->dirents != NULL, 0);
  68
  69     /* First, construct a hash of the file name.  Search the directory for a
  70      * match, then check to see if it does really match. */
  71     uint64_t hash = bluesky_directory_hash(name);
  72
  73     BlueSkyDirent d = {name, hash, 0};
  74     GSequenceIter *i = g_sequence_search(inode->dirents, &d,
  75                                          bluesky_dirent_compare, NULL);
  76     i = g_sequence_iter_prev(i);
  77
  78     if (g_sequence_iter_is_end(i))
  79         return 0;
  80     BlueSkyDirent *dirent = g_sequence_get(i);
  81     g_print("Lookup(%s) -> 0x%016llx\n", name, dirent->hash);
  82     if (dirent->hash != hash)
  83         return 0;
  84     if (g_strcmp0(name, dirent->name) != 0)
  85         return 0;
  86
  87     return dirent->inum;
  88 }
  89
  90 /* Insert a new entry into a directory.  Should be called with the inode lock
  91  * already held. */
  92 gboolean bluesky_directory_insert(BlueSkyInode *dir, gchar *name, uint64_t inum)
  93 {
  94     /* First, construct a hash of the file name.  Search the directory for a
  95      * match, then check to see if it does really match. */
  96     uint64_t hash = bluesky_directory_hash(name);
  97
  98     BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
  99     d->name = name;
 100     d->hash = hash;
 101     d->inum = inum;
 102
 103     GSequenceIter *i = g_sequence_search(dir->dirents, d,
 104                                          bluesky_dirent_compare, NULL);
 105     g_sequence_insert_before(i, d);
 106
 107     return TRUE;
 108 }
 109
 110 /* Dump the contents of a directory to stdout.  Debugging only. */
 111 void bluesky_directory_dump(BlueSkyInode *dir)
 112 {
 113     g_print("Directory dump:\n");
 114
 115     GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
 116
 117     while (!g_sequence_iter_is_end(i)) {
 118         BlueSkyDirent *d = g_sequence_get(i);
 119         g_print("    0x%016llx [inum=%lld] %s\n", d->hash, d->inum, d->name);
 120         i = g_sequence_iter_next(i);
 121     }
 122 }