bluesky/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 void bluesky_dirent_destroy(gpointer data)
  17 {
  18     BlueSkyDirent *dirent = (BlueSkyDirent *)data;
  19     g_free(dirent->name);
  20     g_free(dirent);
  21 }
  22
  23 gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
  24                             gpointer unused)
  25 {
  26     uint32_t hash1 = ((const BlueSkyDirent *)a)->cookie;
  27     uint32_t hash2 = ((const BlueSkyDirent *)b)->cookie;
  28
  29     if (hash1 < hash2)
  30         return -1;
  31     else if (hash1 > hash2)
  32         return 1;
  33     else
  34         return 0;
  35 }
  36
  37 /* Perform a lookup for a file name within a directory.  Returns the inode
  38  * number if found, or 0 if not (0 is never a valid inode number).  Should be
  39  * called with the inode lock already held. */
  40 uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
  41 {
  42     g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
  43     g_return_val_if_fail(inode->dirhash != NULL, 0);
  44
  45     BlueSkyDirent *d = g_hash_table_lookup(inode->dirhash, name);
  46     if (d == NULL)
  47         return 0;
  48     else
  49         return d->inum;
  50 }
  51
  52 /* Insert a new entry into a directory.  Should be called with the inode lock
  53  * already held. */
  54 gboolean bluesky_directory_insert(BlueSkyInode *dir, gchar *name, uint64_t inum)
  55 {
  56     g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
  57
  58     /* Check that no entry with the given name already exists. */
  59     if (g_hash_table_lookup(dir->dirhash, name) != NULL)
  60         return FALSE;
  61
  62     BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
  63     d->name = g_strdup(name);
  64     d->inum = inum;
  65
  66     GSequence *dirents = dir->dirents;
  67
  68     /* Pick an unused cookie value for the directory at random.  Restrict
  69      * ourselves to positive 32-bit values (even if treated as signed), and
  70      * keep the first four slots free. */
  71     while (1) {
  72         do {
  73             d->cookie = g_random_int() & 0x7fffffff;
  74         } while (d->cookie < 4);
  75
  76         /* If the directory is empty, we can't possibly have a collision, so
  77          * just go with the first key chosen. */
  78         if (g_sequence_get_length(dirents) == 0)
  79             break;
  80
  81         /* Otherwise, try looking up the generated cookie.  If we do not find a
  82          * match, we can use this cookie value, otherwise we need to generate a
  83          * new one and try again.  Because of the check above for an empty
  84          * directory, we know that the lookup will return something so no need
  85          * to worry about NULL. */
  86         GSequenceIter *i = g_sequence_search(dir->dirents, d,
  87                                              bluesky_dirent_compare, NULL);
  88         i = g_sequence_iter_prev(i);
  89         if (((BlueSkyDirent *)g_sequence_get(i))->cookie != d->cookie)
  90             break;
  91     }
  92
  93     /* Add the directory entry to both indices. */
  94     g_sequence_insert_sorted(dirents, d, bluesky_dirent_compare, NULL);
  95     g_hash_table_insert(dir->dirhash, d->name, d);
  96
  97     bluesky_inode_update_ctime(dir, 1);
  98
  99     return TRUE;
 100 }
 101
 102 /* Remove an from a directory.  Should be called with the inode lock already
 103  * held. */
 104 gboolean bluesky_directory_remove(BlueSkyInode *dir, gchar *name)
 105 {
 106     g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
 107
 108     BlueSkyDirent *d = g_hash_table_lookup(dir->dirhash, name);
 109     if (d == NULL) {
 110         return FALSE;
 111     }
 112
 113     g_hash_table_remove(dir->dirhash, name);
 114
 115     GSequenceIter *i = g_sequence_search(dir->dirents, d,
 116                                          bluesky_dirent_compare, NULL);
 117     i = g_sequence_iter_prev(i);
 118
 119     /* Assertion check, this ought to succeed */
 120     g_return_val_if_fail(g_sequence_get(i) == d, FALSE);
 121
 122     g_sequence_remove(i);
 123
 124     bluesky_dirent_destroy(d);
 125
 126     bluesky_inode_update_ctime(dir, 1);
 127
 128     return TRUE;
 129 }
 130
 131 /* Dump the contents of a directory to stdout.  Debugging only. */
 132 void bluesky_directory_dump(BlueSkyInode *dir)
 133 {
 134     g_print("Directory dump:\n");
 135
 136     GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
 137
 138     while (!g_sequence_iter_is_end(i)) {
 139         BlueSkyDirent *d = g_sequence_get(i);
 140         g_print("    0x%08x [inum=%lld] %s\n", d->cookie, d->inum, d->name);
 141         i = g_sequence_iter_next(i);
 142     }
 143 }