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  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  * 3. Neither the name of the University nor the names of its contributors
  15  *    may be used to endorse or promote products derived from this software
  16  *    without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  28  * SUCH DAMAGE.
  29  */
  30
  31 #include <stdint.h>
  32 #include <inttypes.h>
  33 #include <glib.h>
  34
  35 #include "bluesky-private.h"
  36
  37 /* Core filesystem: handling of directories. */
  38
  39 void bluesky_dirent_destroy(gpointer data)
  40 {
  41     BlueSkyDirent *dirent = (BlueSkyDirent *)data;
  42     g_free(dirent->name);
  43     g_free(dirent->name_folded);
  44     g_free(dirent);
  45 }
  46
  47 gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
  48                             gpointer unused)
  49 {
  50     uint32_t hash1 = ((const BlueSkyDirent *)a)->cookie;
  51     uint32_t hash2 = ((const BlueSkyDirent *)b)->cookie;
  52
  53     if (hash1 < hash2)
  54         return -1;
  55     else if (hash1 > hash2)
  56         return 1;
  57     else
  58         return 0;
  59 }
  60
  61 /* Perform a lookup for a file name within a directory.  Returns the inode
  62  * number if found, or 0 if not (0 is never a valid inode number).  Should be
  63  * called with the inode lock already held. */
  64 uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
  65 {
  66     g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
  67     g_return_val_if_fail(inode->dirhash != NULL, 0);
  68
  69     BlueSkyDirent *d = g_hash_table_lookup(inode->dirhash, name);
  70     if (d == NULL)
  71         return 0;
  72     else
  73         return d->inum;
  74 }
  75
  76 /* Case-insensitive lookup. */
  77 uint64_t bluesky_directory_ilookup(BlueSkyInode *inode, gchar *name)
  78 {
  79     g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
  80     g_return_val_if_fail(inode->dirhash_folded != NULL, 0);
  81
  82     name = bluesky_lowercase(name);
  83     BlueSkyDirent *d = g_hash_table_lookup(inode->dirhash_folded, name);
  84     g_free(name);
  85
  86     if (d == NULL)
  87         return 0;
  88     else
  89         return d->inum;
  90 }
  91
  92 /* Iterate through a directory listing.  This returns one directory entry at a
  93  * time, finding the first entry with a directory cookie value larger than the
  94  * supplied one.  Use a cookie of 0 to start reading from the start of a
  95  * directory. */
  96 BlueSkyDirent *bluesky_directory_read(BlueSkyInode *dir, uint32_t cookie)
  97 {
  98     BlueSkyDirent start = {NULL, NULL, cookie, 0};
  99     GSequenceIter *i = g_sequence_search(dir->dirents, &start,
 100                                          bluesky_dirent_compare, NULL);
 101
 102     if (g_sequence_iter_is_end(i))
 103         return NULL;
 104     else
 105         return g_sequence_get(i);
 106 }
 107
 108 /* Insert a new entry into a directory.  Should be called with the inode lock
 109  * already held. */
 110 gboolean bluesky_directory_insert(BlueSkyInode *dir,
 111                                   const gchar *name, uint64_t inum)
 112 {
 113     g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
 114
 115     /* Check that no entry with the given name already exists. */
 116     if (g_hash_table_lookup(dir->dirhash, name) != NULL)
 117         return FALSE;
 118
 119     BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
 120     d->name = g_strdup(name);
 121     d->name_folded = bluesky_lowercase(name);
 122     d->inum = inum;
 123
 124     GSequence *dirents = dir->dirents;
 125
 126     /* Pick an unused cookie value for the directory at random.  Restrict
 127      * ourselves to positive 32-bit values (even if treated as signed), and
 128      * keep the first four slots free. */
 129     while (1) {
 130         do {
 131             d->cookie = g_random_int() & 0x7fffffff;
 132         } while (d->cookie < 4);
 133
 134         /* If the directory is empty, we can't possibly have a collision, so
 135          * just go with the first key chosen. */
 136         if (g_sequence_get_length(dirents) == 0)
 137             break;
 138
 139         /* Otherwise, try looking up the generated cookie.  If we do not find a
 140          * match, we can use this cookie value, otherwise we need to generate a
 141          * new one and try again.  Because of the check above for an empty
 142          * directory, we know that the lookup will return something so no need
 143          * to worry about NULL. */
 144         GSequenceIter *i = g_sequence_search(dir->dirents, d,
 145                                              bluesky_dirent_compare, NULL);
 146         i = g_sequence_iter_prev(i);
 147         if (((BlueSkyDirent *)g_sequence_get(i))->cookie != d->cookie)
 148             break;
 149     }
 150
 151     /* Add the directory entry to both indices. */
 152     g_sequence_insert_sorted(dirents, d, bluesky_dirent_compare, NULL);
 153     g_hash_table_insert(dir->dirhash, d->name, d);
 154     g_hash_table_insert(dir->dirhash_folded, d->name_folded, d);
 155
 156     bluesky_inode_update_ctime(dir, 1);
 157     //bluesky_inode_do_sync(dir);     // TODO: Needed?
 158
 159     return TRUE;
 160 }
 161
 162 /* Remove an entry from a directory.  Should be called with the inode lock
 163  * already held. */
 164 gboolean bluesky_directory_remove(BlueSkyInode *dir, gchar *name)
 165 {
 166     g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
 167
 168     BlueSkyDirent *d = g_hash_table_lookup(dir->dirhash, name);
 169     if (d == NULL) {
 170         return FALSE;
 171     }
 172
 173     g_hash_table_remove(dir->dirhash, d->name);
 174     g_hash_table_remove(dir->dirhash_folded, d->name_folded);
 175
 176     GSequenceIter *i = g_sequence_search(dir->dirents, d,
 177                                          bluesky_dirent_compare, NULL);
 178     i = g_sequence_iter_prev(i);
 179
 180     /* Assertion check, this ought to succeed */
 181     g_return_val_if_fail(g_sequence_get(i) == d, FALSE);
 182
 183     g_sequence_remove(i);
 184
 185     bluesky_inode_update_ctime(dir, 1);
 186
 187     return TRUE;
 188 }
 189
 190 /* Rename a file.  If desired (if overwrite is true) and if the target already
 191  * exists, it will be unlinked first. */
 192 gboolean bluesky_rename(BlueSkyInode *dir1, gchar *name1,
 193                         BlueSkyInode *dir2, gchar *name2,
 194                         gboolean case_sensitive,
 195                         gboolean overwrite)
 196 {
 197     g_return_val_if_fail(dir1->type == BLUESKY_DIRECTORY, FALSE);
 198     g_return_val_if_fail(dir2->type == BLUESKY_DIRECTORY, FALSE);
 199
 200     BlueSkyDirent *d1, *d2;
 201
 202     d1 = g_hash_table_lookup(case_sensitive ? dir1->dirhash
 203                                             : dir1->dirhash_folded, name1);
 204     d2 = g_hash_table_lookup(case_sensitive ? dir2->dirhash
 205                                             : dir2->dirhash_folded, name2);
 206
 207     if (d1 == NULL)
 208         return FALSE;
 209
 210     uint64_t inum = d1->inum;
 211
 212     /* Check that this rename does not cause a directory to be moved into one
 213      * of its descendants, as that would create a loop of directories
 214      * disconnected from the root. */
 215     /* TODO */
 216
 217     if (d2 != NULL) {
 218         if (!overwrite)
 219             return FALSE;
 220
 221         bluesky_directory_remove(dir2, name2);
 222
 223         // TODO: Drop inode reference
 224     }
 225
 226     bluesky_directory_remove(dir1, name1);
 227     bluesky_directory_insert(dir2, name2, inum);
 228
 229     return TRUE;
 230 }
 231
 232 /* Dump the contents of a directory to stdout.  Debugging only. */
 233 void bluesky_directory_dump(BlueSkyInode *dir)
 234 {
 235     g_print("Directory dump:\n");
 236
 237     GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
 238
 239     while (!g_sequence_iter_is_end(i)) {
 240         BlueSkyDirent *d = g_sequence_get(i);
 241         g_print("    0x%08x [inum=%"PRIu64"] %s\n",
 242                 d->cookie, d->inum, d->name);
 243         i = g_sequence_iter_next(i);
 244     }
 245 }