bluesky/bluesky-private.h

   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 /* Declarations internal to the BlueSky library.  This header file should not
  32  * be included by any users of the library (such as any filesystem
  33  * proxy)--external users should only include bluesky.h. */
  34
  35 #ifndef _BLUESKY_PRIVATE_H
  36 #define _BLUESKY_PRIVATE_H
  37
  38 #include "bluesky.h"
  39 #include <stdlib.h>
  40
  41 #ifdef __cplusplus
  42 extern "C" {
  43 #endif
  44
  45 extern int bluesky_verbose;
  46
  47 /* Target cache size levels. */
  48 extern int bluesky_watermark_low_dirty;
  49 extern int bluesky_watermark_medium_dirty;
  50 extern int bluesky_watermark_med2_dirty;
  51 extern int bluesky_watermark_high_dirty;
  52
  53 extern int bluesky_watermark_low_total;
  54 extern int bluesky_watermark_medium_total;
  55 extern int bluesky_watermark_med2_total;
  56 extern int bluesky_watermark_high_total;
  57
  58 /* TODO: Make this go away entirely. */
  59 BlueSkyFS *bluesky_new_fs(gchar *name);
  60
  61 void bluesky_inode_free_resources(BlueSkyInode *inode);
  62
  63 /* Linked list update functions for LRU lists. */
  64 void bluesky_list_unlink(GList *head, GList *item);
  65 GList *bluesky_list_prepend(GList *head, BlueSkyInode *inode);
  66 GList *bluesky_list_append(GList *head, BlueSkyInode *inode);
  67 BlueSkyInode *bluesky_list_head(GList *head);
  68 BlueSkyInode *bluesky_list_tail(GList *head);
  69
  70 /* Serialization and deserialization of filesystem data for storing to
  71  * persistent storage. */
  72 void bluesky_serialize_superblock(GString *out, BlueSkyFS *fs);
  73 BlueSkyFS *bluesky_deserialize_superblock(const gchar *buf);
  74 BlueSkyCloudLog *bluesky_serialize_inode(BlueSkyInode *inode);
  75 gboolean bluesky_deserialize_inode(BlueSkyInode *inode, BlueSkyCloudLog *item);
  76
  77 void bluesky_deserialize_cloudlog(BlueSkyCloudLog *item,
  78                                   const char *data,
  79                                   size_t len);
  80
  81 void bluesky_serialize_cloudlog(BlueSkyCloudLog *log,
  82                                 GString *encrypted,
  83                                 GString *authenticated,
  84                                 GString *writable);
  85
  86 /* Cryptographic operations. */
  87 #define CRYPTO_BLOCK_SIZE 16        /* 128-bit AES */
  88 #define CRYPTO_KEY_SIZE   16
  89 #define CRYPTO_HASH_SIZE  32        /* SHA-256 */
  90
  91 typedef struct BlueSkyCryptKeys {
  92     uint8_t encryption_key[CRYPTO_KEY_SIZE];
  93     uint8_t authentication_key[CRYPTO_HASH_SIZE];
  94 } BlueSkyCryptKeys;
  95
  96 void bluesky_crypt_init();
  97 void bluesky_crypt_hash_key(const char *keystr, uint8_t *out);
  98 void bluesky_crypt_random_bytes(guchar *buf, gint len);
  99 void bluesky_crypt_derive_keys(BlueSkyCryptKeys *keys, const gchar *master);
 100 BlueSkyRCStr *bluesky_crypt_encrypt(BlueSkyRCStr *in, const uint8_t *key);
 101 BlueSkyRCStr *bluesky_crypt_decrypt(BlueSkyRCStr *in, const uint8_t *key);
 102
 103 void bluesky_crypt_block_encrypt(gchar *cloud_block, size_t len,
 104                                  BlueSkyCryptKeys *keys);
 105 gboolean bluesky_crypt_block_decrypt(gchar *cloud_block, size_t len,
 106                                      BlueSkyCryptKeys *keys,
 107                                      gboolean allow_unauth);
 108 void bluesky_cloudlog_encrypt(GString *segment, BlueSkyCryptKeys *keys);
 109 void bluesky_cloudlog_decrypt(char *segment, size_t len,
 110                               BlueSkyCryptKeys *keys,
 111                               BlueSkyRangeset *items,
 112                               gboolean allow_unauth);
 113
 114 /* Storage layer.  Requests can be performed asynchronously, so these objects
 115  * help keep track of operations in progress. */
 116 typedef enum {
 117     STORE_OP_NONE,
 118     STORE_OP_GET,
 119     STORE_OP_PUT,
 120     STORE_OP_DELETE,
 121     STORE_OP_BARRIER,       // Waits for other selected operations to complete
 122 } BlueSkyStoreOp;
 123
 124 typedef enum {
 125     ASYNC_NEW,              // Operation not yet submitted to storage layer
 126     ASYNC_PENDING,          // Submitted to storage layer
 127     ASYNC_RUNNING,          // Operation is in progress
 128     ASYNC_COMPLETE,         // Operation finished, results available
 129 } BlueSkyAsyncStatus;
 130
 131 struct BlueSkyNotifierList;
 132 typedef struct BlueSkyStoreAsync BlueSkyStoreAsync;
 133 struct BlueSkyStoreAsync {
 134     BlueSkyStore *store;
 135
 136     GMutex *lock;
 137     GCond *completion_cond;     /* Used to wait for operation to complete. */
 138
 139     gint refcount;              /* Reference count for destruction. */
 140
 141     BlueSkyAsyncStatus status;
 142
 143     BlueSkyStoreOp op;
 144     gchar *key;                 /* Key to read/write */
 145     BlueSkyRCStr *data;         /* Data read/to write */
 146
 147     /* For range requests on reads: starting byte offset and length; len 0
 148      * implies reading to the end of the object.  At completion, the backend
 149      * should set range_done if a range read was made; if not set the entire
 150      * object was read and the storage layer will select out just the
 151      * appropriate bytes. */
 152     size_t start, len;
 153     gboolean range_done;
 154
 155     int result;                 /* Result code; 0 for success. */
 156     struct BlueSkyNotifierList *notifiers;
 157     gint notifier_count;
 158
 159     /* The barrier waiting on this operation.  Support for more than one
 160      * barrier for a single async is not well-supported and should be avoided
 161      * if possible. */
 162     BlueSkyStoreAsync *barrier;
 163
 164     bluesky_time_hires start_time;  /* Time operation was submitted. */
 165     bluesky_time_hires exec_time;   /* Time processing started on operation. */
 166
 167     gpointer store_private;     /* For use by the storage implementation */
 168
 169     /* If storage operations should be charged to any particular profile, which
 170      * one? */
 171     BlueSkyProfile *profile;
 172 };
 173
 174 /* Support for notification lists.  These are lists of one-shot functions which
 175  * can be called when certain events--primarily, competed storage
 176  * events--occur.  Multiple notifiers can be added, but no particular order is
 177  * guaranteed for the notification functions to be called. */
 178 struct BlueSkyNotifierList {
 179     struct BlueSkyNotifierList *next;
 180     GFunc func;
 181     BlueSkyStoreAsync *async;
 182     gpointer user_data;     // Passed to the function when called
 183 };
 184
 185 /* The abstraction layer for storage, allowing multiple implementations. */
 186 typedef struct {
 187     /* Create a new store instance and return a handle to it. */
 188     gpointer (*create)(const gchar *path);
 189
 190     /* Clean up any resources used by this store. */
 191     void (*destroy)(gpointer store);
 192
 193     /* Submit an operation (get/put/delete) to the storage layer to be
 194      * performed asynchronously. */
 195     void (*submit)(gpointer store, BlueSkyStoreAsync *async);
 196
 197     /* Clean up any implementation-private data in a BlueSkyStoreAsync. */
 198     void (*cleanup)(gpointer store, BlueSkyStoreAsync *async);
 199
 200     /* Find the lexicographically-largest file starting with the specified
 201      * prefix. */
 202     char * (*lookup_last)(gpointer store, const gchar *prefix);
 203 } BlueSkyStoreImplementation;
 204
 205 void bluesky_store_register(const BlueSkyStoreImplementation *impl,
 206                             const gchar *name);
 207
 208 char *bluesky_store_lookup_last(BlueSkyStore *store, const char *prefix);
 209 BlueSkyStoreAsync *bluesky_store_async_new(BlueSkyStore *store);
 210 gpointer bluesky_store_async_get_handle(BlueSkyStoreAsync *async);
 211 void bluesky_store_async_ref(BlueSkyStoreAsync *async);
 212 void bluesky_store_async_unref(BlueSkyStoreAsync *async);
 213 void bluesky_store_async_wait(BlueSkyStoreAsync *async);
 214 void bluesky_store_async_add_notifier(BlueSkyStoreAsync *async,
 215                                       GFunc func, gpointer user_data);
 216 void bluesky_store_async_mark_complete(BlueSkyStoreAsync *async);
 217 void bluesky_store_async_submit(BlueSkyStoreAsync *async);
 218 void bluesky_store_sync(BlueSkyStore *store);
 219
 220 void bluesky_store_add_barrier(BlueSkyStoreAsync *barrier,
 221                                BlueSkyStoreAsync *async);
 222
 223 void bluesky_inode_start_sync(BlueSkyInode *inode);
 224
 225 void bluesky_block_touch(BlueSkyInode *inode, uint64_t i, gboolean preserve);
 226 void bluesky_block_fetch(BlueSkyInode *inode, BlueSkyBlock *block,
 227                          BlueSkyStoreAsync *barrier);
 228 void bluesky_block_flush(BlueSkyInode *inode, BlueSkyBlock *block,
 229                          GList **log_items);
 230 void bluesky_file_flush(BlueSkyInode *inode, GList **log_items);
 231 void bluesky_file_drop_cached(BlueSkyInode *inode);
 232
 233 /* Writing of data to the cloud in log segments and tracking the location of
 234  * various pieces of data (both where in the cloud and where cached locally).
 235  * */
 236
 237 /* Eventually we'll want to support multiple writers.  But for now, hard-code
 238  * separate namespaces in the cloud for the proxy and the cleaner to write to.
 239  * */
 240 #define BLUESKY_CLOUD_DIR_PRIMARY 0
 241 #define BLUESKY_CLOUD_DIR_CLEANER 1
 242
 243 typedef struct {
 244     char bytes[16];
 245 } BlueSkyCloudID;
 246
 247 typedef struct {
 248     uint32_t directory;
 249     uint32_t sequence;
 250     uint32_t offset;
 251     uint32_t size;
 252 } BlueSkyCloudPointer;
 253
 254 typedef enum {
 255     LOGTYPE_INVALID = -1,
 256     LOGTYPE_UNKNOWN = 0,
 257     LOGTYPE_DATA = 1,
 258     LOGTYPE_INODE = 2,
 259     LOGTYPE_INODE_MAP = 3,
 260     LOGTYPE_CHECKPOINT = 4,
 261
 262     /* Used only as metadata in the local journal, not loaded as a
 263      * BlueSkyCloudLogState nor stored in the cloud */
 264     LOGTYPE_JOURNAL_MARKER = 16,
 265     LOGTYPE_JOURNAL_CHECKPOINT = 17,
 266 } BlueSkyCloudLogType;
 267
 268 /* Headers that go on items in local log segments and cloud log segments. */
 269 struct log_header {
 270     uint32_t magic;             // HEADER_MAGIC
 271     uint8_t type;               // Object type + '0'
 272     uint32_t offset;            // Starting byte offset of the log header
 273     uint32_t size1;             // Size of the data item (bytes)
 274     uint32_t size2;             //
 275     uint32_t size3;             //
 276     uint64_t inum;              // Inode which owns this data, if any
 277     BlueSkyCloudID id;          // Object identifier
 278 } __attribute__((packed));
 279
 280 struct log_footer {
 281     uint32_t magic;             // FOOTER_MAGIC
 282     uint32_t crc;               // Computed from log_header to log_footer.magic
 283 } __attribute__((packed));
 284
 285 struct cloudlog_header {
 286     char magic[4];
 287     uint8_t crypt_auth[CRYPTO_HASH_SIZE];
 288     uint8_t crypt_iv[CRYPTO_BLOCK_SIZE];
 289     uint8_t type;
 290     BlueSkyCloudID id;
 291     uint64_t inum;
 292     uint32_t size1, size2, size3;
 293 } __attribute__((packed));
 294
 295 // Rough size limit for a log segment.  This is not a firm limit and there are
 296 // no absolute guarantees on the size of a log segment.
 297 #define LOG_SEGMENT_SIZE (1 << 22)
 298
 299 #define JOURNAL_MAGIC "\nLog"
 300 #define CLOUDLOG_MAGIC "AgI-"
 301 #define CLOUDLOG_MAGIC_ENCRYPTED "AgI="     // CLOUDLOG_MAGIC[3] ^= 0x10
 302
 303 /* A record which tracks an object which has been written to a local log,
 304  * cached, locally, and/or written to the cloud. */
 305 #define CLOUDLOG_JOURNAL    0x01
 306 #define CLOUDLOG_CLOUD      0x02
 307 #define CLOUDLOG_CACHE      0x04
 308 #define CLOUDLOG_UNCOMMITTED 0x10
 309 struct BlueSkyCloudLog {
 310     gint refcount;
 311     GMutex *lock;
 312     GCond *cond;
 313
 314     BlueSkyFS *fs;
 315
 316     BlueSkyCloudLogType type;
 317
 318     // Bitmask of CLOUDLOG_* flags indicating where the object exists.
 319     int location_flags;
 320     int pending_read, pending_write;
 321
 322     // A stable identifier for the object (only changes when authenticated data
 323     // is written out, but stays the same when the in-cloud cleaner relocates
 324     // the object).
 325     BlueSkyCloudID id;
 326
 327     // The inode which owns this data, if any, and an offset.
 328     uint64_t inum;
 329     int32_t inum_offset;
 330
 331     // The size of encrypted object data, not including any headers
 332     int data_size;
 333
 334     // The location of the object in the cloud, if available.
 335     BlueSkyCloudPointer location;
 336
 337     // TODO: Location in journal/cache
 338     int log_seq, log_offset, log_size;
 339
 340     // Pointers to other objects.  Each link counts towards the reference count
 341     // of the pointed-to object.  To avoid memory leaks there should be no
 342     // cycles in the reference graph.
 343     GArray *links;
 344
 345     // Serialized data, if available in memory (otherwise NULL), and a lock
 346     // count which tracks if there are users that require the data to be kept
 347     // around.
 348     BlueSkyRCStr *data;
 349     int data_lock_count;
 350 };
 351
 352 /* Serialize objects into a log segment to be written to the cloud. */
 353 struct BlueSkyCloudLogState {
 354     GString *data;
 355     BlueSkyCloudPointer location;
 356     GList *inode_list;
 357     GSList *writeback_list;     // Items which are being serialized right now
 358     GList *pending_segments;    // Segments which are being uploaded now
 359
 360     int uploads_pending;        // Count of uploads in progress, not completed
 361     GMutex *uploads_pending_lock;
 362     GCond *uploads_pending_cond;
 363
 364     /* What is the most recent sequence number written by the cleaner which we
 365      * have processed and incorporated into our own log?  This gets
 366      * incorporated into the version vector written out with our checkpoint
 367      * records. */
 368     int latest_cleaner_seq_seen;
 369 };
 370
 371 gboolean bluesky_cloudlog_equal(gconstpointer a, gconstpointer b);
 372 guint bluesky_cloudlog_hash(gconstpointer a);
 373 BlueSkyCloudLog *bluesky_cloudlog_new(BlueSkyFS *fs, const BlueSkyCloudID *id);
 374 gchar *bluesky_cloudlog_id_to_string(BlueSkyCloudID id);
 375 BlueSkyCloudID bluesky_cloudlog_id_from_string(const gchar *idstr);
 376 void bluesky_cloudlog_threads_init(BlueSkyFS *fs);
 377 void bluesky_cloudlog_ref(BlueSkyCloudLog *log);
 378 void bluesky_cloudlog_unref(BlueSkyCloudLog *log);
 379 void bluesky_cloudlog_unref_delayed(BlueSkyCloudLog *log);
 380 void bluesky_cloudlog_erase(BlueSkyCloudLog *log);
 381 void bluesky_cloudlog_stats_update(BlueSkyCloudLog *log, int type);
 382 void bluesky_cloudlog_sync(BlueSkyCloudLog *log);
 383 void bluesky_cloudlog_insert(BlueSkyCloudLog *log);
 384 void bluesky_cloudlog_insert_locked(BlueSkyCloudLog *log);
 385 BlueSkyCloudLog *bluesky_cloudlog_get(BlueSkyFS *fs, BlueSkyCloudID id);
 386 void bluesky_cloudlog_prefetch(BlueSkyCloudLog *log);
 387 void bluesky_cloudlog_fetch(BlueSkyCloudLog *log);
 388 void bluesky_cloudlog_background_fetch(BlueSkyCloudLog *item);
 389 BlueSkyCloudPointer bluesky_cloudlog_serialize(BlueSkyCloudLog *log,
 390                                                BlueSkyFS *fs);
 391 void bluesky_cloudlog_flush(BlueSkyFS *fs);
 392
 393 /* Logging infrastructure for ensuring operations are persistently recorded to
 394  * disk. */
 395 #define BLUESKY_CRC32C_SEED (~(uint32_t)0)
 396 #define BLUESKY_CRC32C_VALIDATOR ((uint32_t)0xb798b438UL)
 397 uint32_t crc32c(uint32_t crc, const char *buf, unsigned int length);
 398 uint32_t crc32c_finalize(uint32_t crc);
 399
 400 struct BlueSkyLog {
 401     BlueSkyFS *fs;
 402     char *log_directory;
 403     GAsyncQueue *queue;
 404     int fd, dirfd;
 405     int seq_num;
 406     GSList *committed;
 407
 408     /* The currently-open log file. */
 409     BlueSkyCacheFile *current_log;
 410
 411     /* Cache of log segments which have been memory-mapped. */
 412     GMutex *mmap_lock;
 413     GHashTable *mmap_cache;
 414
 415     /* A count of the disk space consumed (in 1024-byte units) by all files
 416      * tracked by mmap_cache (whether mapped or not, actually). */
 417     gint disk_used;
 418
 419     /* The smallest journal sequence number which may still contain data that
 420      * must be preserved (since it it not yet in the cloud). */
 421     int journal_watermark;
 422 };
 423
 424 /* An object for tracking log files which are stored locally--either the
 425  * journal for filesystem consistency or log segments which have been fetched
 426  * back from cloud storage. */
 427 struct BlueSkyCacheFile {
 428     GMutex *lock;
 429     GCond *cond;
 430     gint refcount;
 431     int type;                   // Only one of CLOUDLOG_{JOURNAL,CLOUD}
 432     int log_dir;
 433     int log_seq;
 434     char *filename;             // Local filename, relateive to log directory
 435     gint mapcount;              // References to the mmaped data
 436     const char *addr;           // May be null if data is not mapped in memory
 437     size_t len;
 438     int disk_used;
 439     BlueSkyFS *fs;
 440     BlueSkyLog *log;
 441     gboolean fetching;          // Cloud data: downloading or ready for use
 442     gboolean complete;          // Complete file has been fetched from cloud
 443     int64_t atime;              // Access time, for cache management
 444     BlueSkyRangeset *items;     // Locations of valid items
 445     BlueSkyRangeset *prefetches;// Locations we have been requested to prefetch
 446 };
 447
 448 BlueSkyLog *bluesky_log_new(const char *log_directory);
 449 void bluesky_log_item_submit(BlueSkyCloudLog *item, BlueSkyLog *log);
 450 void bluesky_log_finish_all(GList *log_items);
 451 BlueSkyCloudLog *bluesky_log_get_commit_point(BlueSkyFS *fs);
 452 void bluesky_log_write_commit_point(BlueSkyFS *fs, BlueSkyCloudLog *marker);
 453
 454 BlueSkyRCStr *bluesky_cachefile_map_raw(BlueSkyCacheFile *cachefile,
 455                                         off_t offset, size_t size);
 456 BlueSkyRCStr *bluesky_log_map_object(BlueSkyCloudLog *item, gboolean map_data);
 457 void bluesky_mmap_unref(BlueSkyCacheFile *mmap);
 458 void bluesky_cachefile_unref(BlueSkyCacheFile *cachefile);
 459
 460 BlueSkyCacheFile *bluesky_cachefile_lookup(BlueSkyFS *fs,
 461                                            int clouddir, int log_seq,
 462                                            gboolean start_fetch);
 463 void bluesky_cachefile_gc(BlueSkyFS *fs);
 464
 465 void bluesky_replay(BlueSkyFS *fs);
 466
 467 /* Used to track log segments that are being written to the cloud. */
 468 typedef struct {
 469     BlueSkyFS *fs;
 470     char *key;                  /* File name for log segment in backend */
 471     GString *raw_data;          /* Data before encryption */
 472     BlueSkyRCStr *data;         /* Data after encryption */
 473     GSList *items;
 474     GMutex *lock;
 475     GCond *cond;
 476     gboolean complete;
 477 } SerializedRecord;
 478
 479 /***** Inode map management *****/
 480
 481 /* Mapping information for a single inode number.  These are grouped together
 482  * into InodeMapRange objects. */
 483 typedef struct {
 484     uint64_t inum;
 485
 486     /* A pointer to the cloud log entry for this inode.  This may or may not
 487      * actually have data loaded (it might just contain pointers to the data
 488      * location, and in fact this will likely often be the case). */
 489     BlueSkyCloudLog *item;
 490 } InodeMapEntry;
 491
 492 typedef struct {
 493     /* Starting and ending inode number values that fall in this section.
 494      * Endpoint values are inclusive. */
 495     uint64_t start, end;
 496
 497     /* A sorted list (by inode number) of InodeMapEntry objects. */
 498     GSequence *map_entries;
 499
 500     /* The serialized version of the inode map data. */
 501     BlueSkyCloudLog *serialized;
 502
 503     /* Have there been changes that require writing this section out again? */
 504     gboolean dirty;
 505 } InodeMapRange;
 506
 507 InodeMapEntry *bluesky_inode_map_lookup(GSequence *inode_map, uint64_t inum,
 508                                         int action);
 509 BlueSkyCloudLog *bluesky_inode_map_serialize(BlueSkyFS *fs);
 510 void bluesky_inode_map_minimize(BlueSkyFS *fs);
 511
 512 gboolean bluesky_checkpoint_load(BlueSkyFS *fs);
 513
 514 /* Merging of log state with the work of the cleaner. */
 515 void bluesky_cleaner_merge(BlueSkyFS *fs);
 516 void bluesky_cleaner_thread_launch(BlueSkyFS *fs);
 517
 518 #ifdef __cplusplus
 519 }
 520 #endif
 521
 522 #endif