gboolean complete;
} SerializedRecord;
+/***** Inode map management *****/
+
+/* Mapping information for a single inode number. These are grouped together
+ * into InodeMapRange objects. */
+typedef struct {
+ uint64_t inum;
+
+ /* The ID of the most recent version of the inode. */
+ BlueSkyCloudID id;
+
+ /* The location where that version is written in the cloud. */
+ BlueSkyCloudPointer location;
+
+ /* If the cloud log entry exists in memory, then a pointer to it, otherwise
+ * NULL. */
+ BlueSkyCloudLog *item;
+} InodeMapEntry;
+
+typedef struct {
+ /* Starting and ending inode number values that fall in this section.
+ * Endpoint values are inclusive. */
+ uint64_t start, end;
+
+ /* A sorted list (by inode number) of InodeMapEntry objects. */
+ GSequence *map_entries;
+
+ /* The location where this inode map section is stored in the cloud. */
+ BlueSkyCloudPointer location;
+
+ /* Have there been changes that require writing this section out again? */
+ gboolean dirty;
+} InodeMapRange;
+
+InodeMapEntry *bluesky_inode_map_lookup(GSequence *inode_map, uint64_t inum,
+ int action);
+
#ifdef __cplusplus
}
#endif
g_print("\n");
}
+
+void inode_map_dump(GSequence *inode_map)
+{
+ GSequenceIter *i, *j;
+
+ g_print("\nInode map dump:\n");
+ for (i = g_sequence_get_begin_iter(inode_map);
+ !g_sequence_iter_is_end(i); i = g_sequence_iter_next(i))
+ {
+ InodeMapRange *range = (InodeMapRange *)g_sequence_get(i);
+
+ g_print(" Range [%"PRIu64", %"PRIu64"]\n", range->start, range->end);
+
+ for (j = g_sequence_get_begin_iter(range->map_entries);
+ !g_sequence_iter_is_end(j); j = g_sequence_iter_next(j))
+ {
+ InodeMapEntry *entry = (InodeMapEntry *)g_sequence_get(j);
+ g_print(" Entry %"PRIu64"\n", entry->inum);
+ }
+ }
+}
/* Dump a summary of filesystem state as it is cached in memory. */
void bluesky_debug_dump(BlueSkyFS *fs)
{
g_print("\nJournal/Cache Files:\n");
g_hash_table_foreach(fs->log->mmap_cache, cache_dump, fs);
g_print("\n");
+
+ g_mutex_lock(fs->lock);
+ inode_map_dump(fs->inode_map);
+ g_mutex_unlock(fs->lock);
}
/* Statistics counters: for operation counts, bytes transferred, etc. */
--- /dev/null
+/* Blue Sky: File Systems in the Cloud
+ *
+ * Copyright (C) 2009 The Regents of the University of California
+ * Written by Michael Vrable <mvrable@cs.ucsd.edu>
+ *
+ * TODO: Licensing
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <glib.h>
+#include <string.h>
+
+#include "bluesky-private.h"
+
+/* Inode maps. There is both an in-memory representation as well as the
+ * serialized form in the cloud.
+ *
+ * The inode map is broken up into pieces by partitioning in the inode number
+ * space. The checkpoint region will contain pointers to each of these map
+ * ranges. */
+
+/* Roughly how many inodes to try to put in each inode map range. */
+static int target_imap_size = 4096;
+
+/* Comparison function for lookuping up inode map entries. Reads a 64-bit
+ * value from the pointed-to address to do the comparison, so we require that
+ * the InodeMapEntry and InodeMapRange structures start with the 64-bit value
+ * they are sorted by. */
+static gint compare(gconstpointer a, gconstpointer b, gpointer user_data)
+{
+ uint64_t x = *(uint64_t *)a;
+ uint64_t y = *(uint64_t *)b;
+
+ if (x < y)
+ return -1;
+ else if (x > y)
+ return 1;
+ else
+ return 0;
+}
+
+/* Look up the inode map entry for the given inode number. If action is +1,
+ * create a new entry if it does not already exist; if it is -1 then delete the
+ * entry instead. If 0, return the entry if it is already present. A non-zero
+ * action value will mark the inode map range as dirty. */
+InodeMapEntry *bluesky_inode_map_lookup(GSequence *inode_map, uint64_t inum,
+ int action)
+{
+ GSequenceIter *i;
+
+ /* First, scan through to find the inode map section that covers the
+ * appropriate range. Create one if it does not exist but we were asked to
+ * create an entry. */
+ InodeMapRange *range = NULL;
+
+ i = g_sequence_search(inode_map, &inum, compare, NULL);
+ i = g_sequence_iter_prev(i);
+ if (!g_sequence_iter_is_end(i))
+ range = (InodeMapRange *)g_sequence_get(i);
+ if (range == NULL || inum < range->start || inum > range->end) {
+ if (action <= 0)
+ return NULL;
+
+ /* Create a new range. First, determine bounds on the range enpoints
+ * based on neighboring ranges. Then, shrink the size of the range to
+ * a reasonable size that covers the needed inode number. */
+ range = g_new0(InodeMapRange, 1);
+ range->start = 0;
+ range->end = G_MAXUINT64;
+ range->map_entries = g_sequence_new(NULL);
+ range->dirty = TRUE;
+
+ g_print("Creating inode map range, 1: start=%"PRIu64" end=%"PRIu64"\n",
+ range->start, range->end);
+
+ if (!g_sequence_iter_is_begin(i) && !g_sequence_iter_is_end(i))
+ range->start = ((InodeMapRange *)g_sequence_get(i))->end + 1;
+ i = g_sequence_iter_next(i);
+ if (!g_sequence_iter_is_end(i))
+ range->end = ((InodeMapRange *)g_sequence_get(i))->start - 1;
+
+ g_print("Creating inode map range, 2: start=%"PRIu64" end=%"PRIu64"\n",
+ range->start, range->end);
+ g_assert(inum >= range->start && inum <= range->end);
+
+ range->start = MAX(range->start,
+ inum & ~(uint64_t)(target_imap_size - 1));
+ range->end = MIN(range->end, range->start + target_imap_size - 1);
+
+ g_print("Creating inode map range, 3: start=%"PRIu64" end=%"PRIu64"\n",
+ range->start, range->end);
+
+ g_sequence_insert_sorted(inode_map, range, compare, NULL);
+ }
+
+ /* Next, try to find the entry within this range of the inode map. */
+ InodeMapEntry *entry = NULL;
+ i = g_sequence_search(range->map_entries, &inum, compare, NULL);
+ i = g_sequence_iter_prev(i);
+ if (!g_sequence_iter_is_end(i))
+ entry = (InodeMapEntry *)g_sequence_get(i);
+ if (entry == NULL || inum != entry->inum) {
+ if (action <= 0)
+ return NULL;
+
+ entry = g_new0(InodeMapEntry, 1);
+ entry->inum = inum;
+ g_sequence_insert_sorted(range->map_entries, entry, compare, NULL);
+
+ g_print("Created inode map entry for %"PRIu64"\n", inum);
+ }
+
+ if (action != 0)
+ range->dirty = TRUE;
+
+ /* Were we requested to delete the item? */
+ if (action < 0) {
+ g_sequence_remove(i);
+ entry = NULL;
+ }
+
+ return entry;
+}
projects / bluesky.git / commitdiff