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->dirty = TRUE;
  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         range->dirty = TRUE;
 117
 118     /* Were we requested to delete the item? */
 119     if (action < 0) {
 120         g_sequence_remove(i);
 121         entry = NULL;
 122     }
 123
 124     return entry;
 125 }