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