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