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-private.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 /* Iterate through a directory listing.  This returns one directory entry at a
  71  * time, finding the first entry with a directory cookie value larger than the
  72  * supplied one.  Use a cookie of 0 to start reading from the start of a
  73  * directory. */
  74 BlueSkyDirent *bluesky_directory_read(BlueSkyInode *dir, uint32_t cookie)
  75 {
  76     BlueSkyDirent start = {NULL, NULL, cookie, 0};
  77     GSequenceIter *i = g_sequence_search(dir->dirents, &start,
  78                                          bluesky_dirent_compare, NULL);
  79
  80     if (g_sequence_iter_is_end(i))
  81         return NULL;
  82     else
  83         return g_sequence_get(i);
  84 }
  85
  86 /* Insert a new entry into a directory.  Should be called with the inode lock
  87  * already held. */
  88 gboolean bluesky_directory_insert(BlueSkyInode *dir,
  89                                   const gchar *name, uint64_t inum)
  90 {
  91     g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
  92
  93     /* Check that no entry with the given name already exists. */
  94     if (g_hash_table_lookup(dir->dirhash, name) != NULL)
  95         return FALSE;
  96
  97     BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
  98     d->name = g_strdup(name);
  99     d->name_folded = bluesky_lowercase(name);
 100     d->inum = inum;
 101
 102     GSequence *dirents = dir->dirents;
 103
 104     /* Pick an unused cookie value for the directory at random.  Restrict
 105      * ourselves to positive 32-bit values (even if treated as signed), and
 106      * keep the first four slots free. */
 107     while (1) {
 108         do {
 109             d->cookie = g_random_int() & 0x7fffffff;
 110         } while (d->cookie < 4);
 111
 112         /* If the directory is empty, we can't possibly have a collision, so
 113          * just go with the first key chosen. */
 114         if (g_sequence_get_length(dirents) == 0)
 115             break;
 116
 117         /* Otherwise, try looking up the generated cookie.  If we do not find a
 118          * match, we can use this cookie value, otherwise we need to generate a
 119          * new one and try again.  Because of the check above for an empty
 120          * directory, we know that the lookup will return something so no need
 121          * to worry about NULL. */
 122         GSequenceIter *i = g_sequence_search(dir->dirents, d,
 123                                              bluesky_dirent_compare, NULL);
 124         i = g_sequence_iter_prev(i);
 125         if (((BlueSkyDirent *)g_sequence_get(i))->cookie != d->cookie)
 126             break;
 127     }
 128
 129     /* Add the directory entry to both indices. */
 130     g_sequence_insert_sorted(dirents, d, bluesky_dirent_compare, NULL);
 131     g_hash_table_insert(dir->dirhash, d->name, d);
 132     g_hash_table_insert(dir->dirhash_folded, d->name_folded, d);
 133
 134     bluesky_inode_update_ctime(dir, 1);
 135     //bluesky_inode_do_sync(dir);     // TODO: Needed?
 136
 137     return TRUE;
 138 }
 139
 140 /* Remove an entry from a directory.  Should be called with the inode lock
 141  * already held. */
 142 gboolean bluesky_directory_remove(BlueSkyInode *dir, gchar *name)
 143 {
 144     g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
 145
 146     BlueSkyDirent *d = g_hash_table_lookup(dir->dirhash, name);
 147     if (d == NULL) {
 148         return FALSE;
 149     }
 150
 151     g_hash_table_remove(dir->dirhash, d->name);
 152     g_hash_table_remove(dir->dirhash_folded, d->name_folded);
 153
 154     GSequenceIter *i = g_sequence_search(dir->dirents, d,
 155                                          bluesky_dirent_compare, NULL);
 156     i = g_sequence_iter_prev(i);
 157
 158     /* Assertion check, this ought to succeed */
 159     g_return_val_if_fail(g_sequence_get(i) == d, FALSE);
 160
 161     g_sequence_remove(i);
 162
 163     bluesky_inode_update_ctime(dir, 1);
 164
 165     return TRUE;
 166 }
 167
 168 /* Rename a file.  If desired (if overwrite is true) and if the target already
 169  * exists, it will be unlinked first. */
 170 gboolean bluesky_rename(BlueSkyInode *dir1, gchar *name1,
 171                         BlueSkyInode *dir2, gchar *name2,
 172                         gboolean case_sensitive,
 173                         gboolean overwrite)
 174 {
 175     g_return_val_if_fail(dir1->type == BLUESKY_DIRECTORY, FALSE);
 176     g_return_val_if_fail(dir2->type == BLUESKY_DIRECTORY, FALSE);
 177
 178     BlueSkyDirent *d1, *d2;
 179
 180     d1 = g_hash_table_lookup(case_sensitive ? dir1->dirhash
 181                                             : dir1->dirhash_folded, name1);
 182     d2 = g_hash_table_lookup(case_sensitive ? dir2->dirhash
 183                                             : dir2->dirhash_folded, name2);
 184
 185     if (d1 == NULL)
 186         return FALSE;
 187
 188     uint64_t inum = d1->inum;
 189
 190     /* Check that this rename does not cause a directory to be moved into one
 191      * of its descendants, as that would create a loop of directories
 192      * disconnected from the root. */
 193     /* TODO */
 194
 195     if (d2 != NULL) {
 196         if (!overwrite)
 197             return FALSE;
 198
 199         bluesky_directory_remove(dir2, name2);
 200
 201         // TODO: Drop inode reference
 202     }
 203
 204     bluesky_directory_remove(dir1, name1);
 205     bluesky_directory_insert(dir2, name2, inum);
 206
 207     return TRUE;
 208 }
 209
 210 /* Dump the contents of a directory to stdout.  Debugging only. */
 211 void bluesky_directory_dump(BlueSkyInode *dir)
 212 {
 213     g_print("Directory dump:\n");
 214
 215     GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
 216
 217     while (!g_sequence_iter_is_end(i)) {
 218         BlueSkyDirent *d = g_sequence_get(i);
 219         g_print("    0x%08x [inum=%"PRIu64"] %s\n",
 220                 d->cookie, d->inum, d->name);
 221         i = g_sequence_iter_next(i);
 222     }
 223 }