bluesky/imap.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 <stdio.h>
  10 #include <stdint.h>
  11 #include <inttypes.h>
  12 #include <glib.h>
  13 #include <string.h>
  14
  15 #include "bluesky-private.h"
  16
  17 /* Inode maps.  There is both an in-memory representation as well as the
  18  * serialized form in the cloud.
  19  *
  20  * The inode map is broken up into pieces by partitioning in the inode number
  21  * space.  The checkpoint region will contain pointers to each of these map
  22  * ranges. */
  23
  24 /* Roughly how many inodes to try to put in each inode map range. */
  25 static int target_imap_size = 4096;
  26
  27 /* Comparison function for lookuping up inode map entries.  Reads a 64-bit
  28  * value from the pointed-to address to do the comparison, so we require that
  29  * the InodeMapEntry and InodeMapRange structures start with the 64-bit value
  30  * they are sorted by. */
  31 static gint compare(gconstpointer a, gconstpointer b, gpointer user_data)
  32 {
  33     uint64_t x = *(uint64_t *)a;
  34     uint64_t y = *(uint64_t *)b;
  35
  36     if (x < y)
  37         return -1;
  38     else if (x > y)
  39         return 1;
  40     else
  41         return 0;
  42 }
  43
  44 /* Look up the inode map entry for the given inode number.  If action is +1,
  45  * create a new entry if it does not already exist; if it is -1 then delete the
  46  * entry instead.  If 0, return the entry if it is already present.  A non-zero
  47  * action value will mark the inode map range as dirty. */
  48 InodeMapEntry *bluesky_inode_map_lookup(GSequence *inode_map, uint64_t inum,
  49                                         int action)
  50 {
  51     GSequenceIter *i;
  52
  53     /* First, scan through to find the inode map section that covers the
  54      * appropriate range.  Create one if it does not exist but we were asked to
  55      * create an entry. */
  56     InodeMapRange *range = NULL;
  57
  58     i = g_sequence_search(inode_map, &inum, compare, NULL);
  59     i = g_sequence_iter_prev(i);
  60     if (!g_sequence_iter_is_end(i))
  61         range = (InodeMapRange *)g_sequence_get(i);
  62     if (range == NULL || inum < range->start || inum > range->end) {
  63         if (action <= 0)
  64             return NULL;
  65
  66         /* Create a new range.  First, determine bounds on the range enpoints
  67          * based on neighboring ranges.  Then, shrink the size of the range to
  68          * a reasonable size that covers the needed inode number. */
  69         range = g_new0(InodeMapRange, 1);
  70         range->start = 0;
  71         range->end = G_MAXUINT64;
  72         range->map_entries = g_sequence_new(NULL);
  73         range->serialized = NULL;
  74
  75         g_print("Creating inode map range, 1: start=%"PRIu64" end=%"PRIu64"\n",
  76                 range->start, range->end);
  77
  78         if (!g_sequence_iter_is_begin(i) && !g_sequence_iter_is_end(i))
  79             range->start = ((InodeMapRange *)g_sequence_get(i))->end + 1;
  80         i = g_sequence_iter_next(i);
  81         if (!g_sequence_iter_is_end(i))
  82             range->end = ((InodeMapRange *)g_sequence_get(i))->start - 1;
  83
  84         g_print("Creating inode map range, 2: start=%"PRIu64" end=%"PRIu64"\n",
  85                 range->start, range->end);
  86         g_assert(inum >= range->start && inum <= range->end);
  87
  88         range->start = MAX(range->start,
  89                            inum & ~(uint64_t)(target_imap_size - 1));
  90         range->end = MIN(range->end, range->start + target_imap_size - 1);
  91
  92         g_print("Creating inode map range, 3: start=%"PRIu64" end=%"PRIu64"\n",
  93                 range->start, range->end);
  94
  95         g_sequence_insert_sorted(inode_map, range, compare, NULL);
  96     }
  97
  98     /* Next, try to find the entry within this range of the inode map. */
  99     InodeMapEntry *entry = NULL;
 100     i = g_sequence_search(range->map_entries, &inum, compare, NULL);
 101     i = g_sequence_iter_prev(i);
 102     if (!g_sequence_iter_is_end(i))
 103         entry = (InodeMapEntry *)g_sequence_get(i);
 104     if (entry == NULL || inum != entry->inum) {
 105         if (action <= 0)
 106             return NULL;
 107
 108         entry = g_new0(InodeMapEntry, 1);
 109         entry->inum = inum;
 110         g_sequence_insert_sorted(range->map_entries, entry, compare, NULL);
 111
 112         g_print("Created inode map entry for %"PRIu64"\n", inum);
 113     }
 114
 115     if (action != 0) {
 116         bluesky_cloudlog_unref(range->serialized);
 117         range->serialized = NULL;
 118     }
 119
 120     /* Were we requested to delete the item? */
 121     if (action < 0) {
 122         g_sequence_remove(i);
 123         entry = NULL;
 124     }
 125
 126     return entry;
 127 }
 128
 129 /* Convert a section of the inode map to serialized form, in preparation for
 130  * writing it out to the cloud. */
 131 static void bluesky_inode_map_serialize_section(BlueSkyFS *fs,
 132                                                 InodeMapRange *range)
 133 {
 134     if (range->serialized != NULL)
 135         return;
 136
 137     GString *buf = g_string_new("");
 138     BlueSkyCloudLog *log = bluesky_cloudlog_new(fs, NULL);
 139     log->type = LOGTYPE_INODE_MAP;
 140     log->inum = 0;
 141
 142     GSequenceIter *i = g_sequence_get_begin_iter(range->map_entries);
 143     while (!g_sequence_iter_is_end(i)) {
 144         InodeMapEntry *entry = (InodeMapEntry *)g_sequence_get(i);
 145         uint64_t inum = GUINT64_TO_LE(entry->inum);
 146         g_string_append_len(buf, (const char *)&inum, sizeof(inum));
 147         g_array_append_val(log->links, entry->item);
 148         i = g_sequence_iter_next(i);
 149     }
 150
 151     log->data = bluesky_string_new_from_gstring(buf);
 152     bluesky_cloudlog_unref(range->serialized);
 153     range->serialized = log;
 154 }
 155
 156 BlueSkyCloudLog *bluesky_inode_map_serialize(BlueSkyFS *fs)
 157 {
 158     GString *buf = g_string_new("");
 159     BlueSkyCloudLog *log = bluesky_cloudlog_new(fs, NULL);
 160     log->type = LOGTYPE_CHECKPOINT;
 161     log->inum = 0;
 162
 163     GSequenceIter *i = g_sequence_get_begin_iter(fs->inode_map);
 164     while (!g_sequence_iter_is_end(i)) {
 165         InodeMapRange *range = (InodeMapRange *)g_sequence_get(i);
 166         uint64_t inum = GUINT64_TO_LE(range->start);
 167         g_string_append_len(buf, (const char *)&inum, sizeof(inum));
 168         inum = GUINT64_TO_LE(range->end);
 169         g_string_append_len(buf, (const char *)&inum, sizeof(inum));
 170
 171         if (range->serialized == NULL)
 172             bluesky_inode_map_serialize_section(fs, range);
 173         bluesky_cloudlog_ref(range->serialized);
 174         g_array_append_val(log->links, range->serialized);
 175         i = g_sequence_iter_next(i);
 176     }
 177
 178     log->data = bluesky_string_new_from_gstring(buf);
 179     return log;
 180 }