bluesky/util.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 <glib.h>
  12 #include <string.h>
  13 #include <sys/mman.h>
  14
  15 #include "bluesky-private.h"
  16
  17 /* Miscellaneous useful functions that don't really fit anywhere else. */
  18
  19 bluesky_time_hires bluesky_now_hires()
  20 {
  21     struct timespec time;
  22
  23     if (clock_gettime(CLOCK_REALTIME, &time) != 0) {
  24         perror("clock_gettime");
  25         return 0;
  26     }
  27
  28     return (int64_t)(time.tv_sec) * 1000000000 + time.tv_nsec;
  29 }
  30
  31 /* Convert a UTF-8 string to lowercase.  This can be used to implement
  32  * case-insensitive lookups and comparisons, by normalizing all values to
  33  * lowercase first.  Returns a newly-allocated string as a result. */
  34 gchar *bluesky_lowercase(const gchar *s)
  35 {
  36     /* TODO: Unicode handling; for now just do ASCII. */
  37     return g_ascii_strdown(s, -1);
  38 }
  39
  40 gboolean bluesky_inode_is_ready(BlueSkyInode *inode)
  41 {
  42     if (inode == NULL)
  43         return FALSE;
  44
  45     g_mutex_lock(inode->lock);
  46     gboolean valid = (inode->type != BLUESKY_PENDING
  47                       && inode->type != BLUESKY_INVALID);
  48
  49     g_mutex_unlock(inode->lock);
  50
  51     return valid;
  52 }
  53
  54 /**** Reference-counted strings. ****/
  55
  56 /* Create and return a new reference-counted string.  The reference count is
  57  * initially one.  The newly-returned string takes ownership of the memory
  58  * pointed at by data, and will call g_free on it when the reference count
  59  * drops to zero. */
  60 BlueSkyRCStr *bluesky_string_new(gpointer data, gsize len)
  61 {
  62     BlueSkyRCStr *string = g_new(BlueSkyRCStr, 1);
  63     string->mmap = NULL;
  64     string->data = data;
  65     string->len = len;
  66     g_atomic_int_set(&string->refcount, 1);
  67     return string;
  68 }
  69
  70 /* Create a new BlueSkyRCStr from a GString.  The GString is destroyed. */
  71 BlueSkyRCStr *bluesky_string_new_from_gstring(GString *s)
  72 {
  73     gsize len = s->len;
  74     return bluesky_string_new(g_string_free(s, FALSE), len);
  75 }
  76
  77 /* Create a new BlueSkyRCStr from a memory-mapped buffer. */
  78 BlueSkyRCStr *bluesky_string_new_from_mmap(BlueSkyCacheFile *mmap,
  79                                            int offset, gsize len)
  80 {
  81     g_assert(offset + len <= mmap->len);
  82
  83     BlueSkyRCStr *string = g_new(BlueSkyRCStr, 1);
  84     string->mmap = mmap;
  85     g_atomic_int_inc(&mmap->mapcount);
  86     string->data = (char *)mmap->addr + offset;
  87     string->len = len;
  88     g_atomic_int_set(&string->refcount, 1);
  89     return string;
  90 }
  91
  92 void bluesky_string_ref(BlueSkyRCStr *string)
  93 {
  94     if (string == NULL)
  95         return;
  96
  97     g_atomic_int_inc(&string->refcount);
  98 }
  99
 100 void bluesky_string_unref(BlueSkyRCStr *string)
 101 {
 102     if (string == NULL)
 103         return;
 104
 105     if (g_atomic_int_dec_and_test(&string->refcount)) {
 106         if (string->mmap == NULL) {
 107             g_free(string->data);
 108         } else {
 109             bluesky_mmap_unref(string->mmap);
 110         }
 111         g_free(string);
 112     }
 113 }
 114
 115 /* Duplicate and return a new reference-counted string, containing a copy of
 116  * the original data, with a reference count of 1.  As an optimization, if the
 117  * passed-in string already has a reference count of 1, the original is
 118  * returned.   Can be used to make a mutable copy of a shared string.  For this
 119  * to truly be safe, it is probably needed that there be some type of lock
 120  * protecting access to the string. */
 121 BlueSkyRCStr *bluesky_string_dup(BlueSkyRCStr *string)
 122 {
 123     if (string == NULL)
 124         return NULL;
 125
 126     if (string->mmap != NULL) {
 127         BlueSkyRCStr *s;
 128         s = bluesky_string_new(g_memdup(string->data, string->len),
 129                                string->len);
 130         bluesky_string_unref(string);
 131         return s;
 132     }
 133
 134     if (g_atomic_int_dec_and_test(&string->refcount)) {
 135         /* There are no other shared copies, so return this one. */
 136         g_atomic_int_inc(&string->refcount);
 137         return string;
 138     } else {
 139         return bluesky_string_new(g_memdup(string->data, string->len),
 140                                   string->len);
 141     }
 142 }
 143
 144 /* Resize the data block used by a BlueSkyRCStr.  The data pointer might change
 145  * after making this call, so it should not be cached across calls to this
 146  * function.  To avoid confusing any other users, the caller probably ought to
 147  * hold the only reference to the string (by calling bluesky_string_dup first
 148  * if needed). */
 149 void bluesky_string_resize(BlueSkyRCStr *string, gsize len)
 150 {
 151     g_assert(string->mmap == NULL);
 152
 153     if (string->len == len)
 154         return;
 155
 156     g_warn_if_fail(string->refcount == 1);
 157
 158     string->data = g_realloc(string->data, len);
 159     string->len = len;
 160 }
 161
 162 /* Cache LRU list management functions.  These manage the doubly-linked list of
 163  * inodes sorted by accessed/modified time.  The FS lock should be held while
 164  * calling these.
 165  *
 166  * _remove will unlink an inode from the linked list.
 167  *
 168  * _prepend and _append insert an inode at the head or tail of the linked list,
 169  * and return a pointer to the linked list element (which should be stored in
 170  * the inode); the inode should not already be in the list.
 171  *
 172  * _head and _tail simply return the first or last item inode in the list. */
 173 void bluesky_list_unlink(GList *head, GList *item)
 174 {
 175     if (item == NULL)
 176         return;
 177
 178     if (head->prev == item)
 179         head->prev = item->prev;
 180     head->next = g_list_delete_link(head->next, item);
 181 }
 182
 183 GList *bluesky_list_prepend(GList *head, BlueSkyInode *inode)
 184 {
 185     head->next = g_list_prepend(head->next, inode);
 186     if (head->prev == NULL)
 187         head->prev = g_list_last(head->next);
 188     return head->next;
 189 }
 190
 191 GList *bluesky_list_append(GList *head, BlueSkyInode *inode)
 192 {
 193     if (head->next == NULL)
 194         return bluesky_list_prepend(head, inode);
 195
 196     g_assert(head->prev != NULL && head->prev->next == NULL);
 197
 198     GList *link = g_list_alloc();
 199     link->data = inode;
 200     link->next = NULL;
 201     link->prev = head->prev;
 202     head->prev->next = link;
 203     head->prev = link;
 204     return link;
 205 }
 206
 207 BlueSkyInode *bluesky_list_head(GList *head)
 208 {
 209     if (head->next == NULL)
 210         return NULL;
 211     else
 212         return (BlueSkyInode *)head->next->data;
 213 }
 214
 215 BlueSkyInode *bluesky_list_tail(GList *head)
 216 {
 217     if (head->prev == NULL)
 218         return NULL;
 219     else
 220         return (BlueSkyInode *)head->prev->data;
 221 }
 222
 223 /**** Range sets. ****/
 224
 225 /* These are a data structure which can track a set of discontiguous integer
 226  * ranges--such as the partitioning of the inode number space or the bytes in a
 227  * log file into objects.  This current prototype implementation just tracks
 228  * the starting offset with a hash table and doesn't track the length, but
 229  * should be extended later to track properly. */
 230
 231 struct BlueSkyRangeset {
 232     GSequence *seq;
 233 };
 234
 235 static gint compare64(gconstpointer a, gconstpointer b, gpointer user_data)
 236 {
 237     uint64_t x = *(uint64_t *)a;
 238     uint64_t y = *(uint64_t *)b;
 239
 240     if (x < y)
 241         return -1;
 242     else if (x > y)
 243         return 1;
 244     else
 245         return 0;
 246 }
 247
 248 BlueSkyRangeset *bluesky_rangeset_new()
 249 {
 250     BlueSkyRangeset *rangeset = g_new(BlueSkyRangeset, 1);
 251     rangeset->seq = g_sequence_new(g_free);
 252     return rangeset;
 253 }
 254
 255 void bluesky_rangeset_free(BlueSkyRangeset *rangeset)
 256 {
 257     g_sequence_free(rangeset->seq);
 258     g_free(rangeset);
 259 }
 260
 261 gboolean bluesky_rangeset_insert(BlueSkyRangeset *rangeset,
 262                                  uint64_t start, uint64_t length,
 263                                  gpointer data)
 264 {
 265     GSequenceIter *i;
 266     i = g_sequence_search(rangeset->seq, &start, compare64, NULL);
 267     i = g_sequence_iter_prev(i);
 268
 269     /* TODO: Checks that no other item overlaps. */
 270
 271     BlueSkyRangesetItem *item = g_new(BlueSkyRangesetItem, 1);
 272     item->start = start;
 273     item->length = length;
 274     item->data = data;
 275     g_sequence_insert_sorted(rangeset->seq, item, compare64, NULL);
 276
 277     return TRUE;
 278 }
 279
 280 const BlueSkyRangesetItem *bluesky_rangeset_lookup(BlueSkyRangeset *rangeset,
 281                                                    uint64_t offset)
 282 {
 283     GSequenceIter *i;
 284     i = g_sequence_search(rangeset->seq, &offset, compare64, NULL);
 285     i = g_sequence_iter_prev(i);
 286     if (g_sequence_iter_is_end(i))
 287         return NULL;
 288
 289     BlueSkyRangesetItem *item = (BlueSkyRangesetItem *)g_sequence_get(i);
 290     if (offset >= item->start && offset < item->start + item->length)
 291         return item;
 292     else
 293         return NULL;
 294 }
 295
 296 /* Look up the first rangeset item starting at or following the given address.
 297  * Can be used to iterate through a rangeset. */
 298 const BlueSkyRangesetItem *bluesky_rangeset_lookup_next(BlueSkyRangeset *rangeset, uint64_t offset)
 299 {
 300     GSequenceIter *i;
 301     i = g_sequence_search(rangeset->seq, &offset, compare64, NULL);
 302     i = g_sequence_iter_prev(i);
 303     if (g_sequence_iter_is_end(i))
 304         return NULL;
 305     BlueSkyRangesetItem *item = (BlueSkyRangesetItem *)g_sequence_get(i);
 306     if (item->start < offset) {
 307         i = g_sequence_iter_next(i);
 308         if (g_sequence_iter_is_end(i))
 309             item = NULL;
 310         else
 311             item = (BlueSkyRangesetItem *)g_sequence_get(i);
 312     }
 313     return item;
 314 }
 315
 316 /* Determine the full extent of a rangeset--the smallest offset covered and the
 317  * length needed to extend to the end of the last item. */
 318 void bluesky_rangeset_get_extents(BlueSkyRangeset *rangeset,
 319                                   uint64_t *start, uint64_t *length)
 320 {
 321     GSequenceIter *i;
 322     BlueSkyRangesetItem *item;
 323
 324     i = g_sequence_get_begin_iter(rangeset->seq);
 325     if (g_sequence_iter_is_end(i)) {
 326         *start = 0;
 327         *length = 0;
 328         return;
 329     }
 330
 331     item = (BlueSkyRangesetItem *)g_sequence_get(i);
 332     *start = item->start;
 333
 334     i = g_sequence_get_end_iter(rangeset->seq);
 335     i = g_sequence_iter_prev(i);
 336     item = (BlueSkyRangesetItem *)g_sequence_get(i);
 337     *length = (item->start + item->length) - *start;
 338 }
 339
 340 /**** Request response-time tracking. ****/
 341 /* TODO: Locking */
 342 typedef struct {
 343     bluesky_time_hires timestamp;
 344     char *message;
 345 } RTEvent;
 346
 347 BlueSkyProfile *bluesky_profile_new()
 348 {
 349     return g_new0(BlueSkyProfile, 1);
 350 }
 351
 352 void bluesky_profile_free(BlueSkyProfile *profile)
 353 {
 354     while (profile->events != NULL) {
 355         RTEvent *event = (RTEvent *)profile->events->data;
 356         g_free(event->message);
 357         g_free(event);
 358         profile->events = g_list_delete_link(profile->events, profile->events);
 359     }
 360     g_free(profile->description);
 361     g_free(profile);
 362 }
 363
 364 void bluesky_profile_add_event(BlueSkyProfile *profile, char *message)
 365 {
 366     g_return_if_fail(profile != NULL);
 367
 368     RTEvent *event = g_new(RTEvent, 1);
 369     event->timestamp = bluesky_now_hires();
 370     event->message = message;
 371     profile->events = g_list_prepend(profile->events, event);
 372 }
 373
 374 void bluesky_profile_print(BlueSkyProfile *profile)
 375 {
 376     g_return_if_fail(profile != NULL);
 377
 378     g_print("Event Timeline: %s\n", profile->description);
 379     GList *link = g_list_last(profile->events);
 380     bluesky_time_hires last_time = 0;
 381     while (link != NULL) {
 382         RTEvent *event = (RTEvent *)link->data;
 383         g_print("  [%"PRIi64" ns]: %s\n",
 384                 event->timestamp - last_time, event->message);
 385         last_time = event->timestamp;
 386         link = link->prev;
 387     }
 388 }
 389
 390 static GStaticPrivate per_thread_profile = G_STATIC_PRIVATE_INIT;
 391
 392 BlueSkyProfile *bluesky_profile_get()
 393 {
 394     return (BlueSkyProfile *)g_static_private_get(&per_thread_profile);
 395 }
 396
 397 void bluesky_profile_set(BlueSkyProfile *profile)
 398 {
 399     g_static_private_set(&per_thread_profile, profile, NULL);
 400 }