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