From e26a903ddf80011e3b72a780d7392a8333c996af Mon Sep 17 00:00:00 2001 From: Michael Vrable Date: Thu, 25 Mar 2010 16:34:22 -0700 Subject: [PATCH] Add LRU lists for tracking inodes that are dirty/accessed. --- bluesky/bluesky-private.h | 7 +++++ bluesky/bluesky.h | 13 +++++++++ bluesky/cache.c | 4 +++ bluesky/debug.c | 12 ++++++++ bluesky/inode.c | 21 ++++++++++++-- bluesky/util.c | 61 +++++++++++++++++++++++++++++++++++++++ 6 files changed, 116 insertions(+), 2 deletions(-) diff --git a/bluesky/bluesky-private.h b/bluesky/bluesky-private.h index 7eaba1e..ccd57cb 100644 --- a/bluesky/bluesky-private.h +++ b/bluesky/bluesky-private.h @@ -22,6 +22,13 @@ extern "C" { /* TODO: Make this go away entirely. */ BlueSkyFS *bluesky_new_fs(gchar *name); +/* Linked list update functions for LRU lists. */ +void bluesky_list_unlink(GList *head, GList *item); +GList *bluesky_list_prepend(GList *head, BlueSkyInode *inode); +GList *bluesky_list_append(GList *head, BlueSkyInode *inode); +BlueSkyInode *bluesky_list_head(GList *head); +BlueSkyInode *bluesky_list_tail(GList *head); + /* Serialization and deserialization of filesystem data for storing to * persistent storage. */ void bluesky_serialize_superblock(GString *out, BlueSkyFS *fs); diff --git a/bluesky/bluesky.h b/bluesky/bluesky.h index 3fc1c6a..59a33c5 100644 --- a/bluesky/bluesky.h +++ b/bluesky/bluesky.h @@ -122,6 +122,13 @@ typedef struct { * data includes dirty data). Updates to these variables must be made * atomically. */ gint cache_total, cache_dirty; + + /* Linked list of inodes, sorted by access/modification times for cache + * management. Editing these lists is protected by the filesystem lock; to + * avoid deadlock do not attempt to take any other locks while the FS lock + * is held for list editing purposes. Items at the head of the list are + * most recently accessed/modified. */ + GList dirty_list, accessed_list; } BlueSkyFS; /* Inode number of the root directory. */ @@ -185,6 +192,12 @@ typedef struct { /* Additional state for tracking cache writeback status. */ uint64_t change_pending; /* change_count version currently being committed to storage */ + /* Pointers to the linked-list elements for this inode in the accessed and + * dirty linked lists. We re-use the GList structure, using ->next to + * point to the head of the list and ->prev to point to the tail. The data + * element is unused. */ + GList *accessed_list, *dirty_list; + int64_t atime; /* Microseconds since the Unix epoch */ int64_t ctime; int64_t mtime; diff --git a/bluesky/cache.c b/bluesky/cache.c index 1f10db0..f58a949 100644 --- a/bluesky/cache.c +++ b/bluesky/cache.c @@ -32,6 +32,10 @@ static void writeback_complete(gpointer a, gpointer i) if (inode->change_count == inode->change_commit) { /* If inode is no longer dirty... */ inode->change_time = 0; + g_mutex_lock(inode->fs->lock); + bluesky_list_unlink(&inode->fs->dirty_list, inode->dirty_list); + inode->dirty_list = NULL; + g_mutex_unlock(inode->fs->lock); } g_mutex_unlock(inode->lock); diff --git a/bluesky/debug.c b/bluesky/debug.c index 312a0e1..7cdd4fd 100644 --- a/bluesky/debug.c +++ b/bluesky/debug.c @@ -45,5 +45,17 @@ void bluesky_debug_dump(BlueSkyFS *fs) g_print("Cached inodes: %u\tNext inode: %"PRIu64"\n", g_hash_table_size(fs->inodes), fs->next_inum); + GList *item; + g_print("Dirty inode LRU list:"); + for (item = fs->dirty_list.next; item != NULL; item = item->next) { + g_print(" %"PRIu64";", ((BlueSkyInode *)item->data)->inum); + } + g_print("\n"); + g_print("Accessed inode LRU list:"); + for (item = fs->accessed_list.next; item != NULL; item = item->next) { + g_print(" %"PRIu64";", ((BlueSkyInode *)item->data)->inum); + } + g_print("\n"); + g_hash_table_foreach(fs->inodes, inode_dump, fs); } diff --git a/bluesky/inode.c b/bluesky/inode.c index 3e92e4f..ef6e75d 100644 --- a/bluesky/inode.c +++ b/bluesky/inode.c @@ -44,6 +44,13 @@ void bluesky_inode_update_ctime(BlueSkyInode *inode, gboolean update_mtime) if (bluesky_options.writethrough_cache) bluesky_file_flush(inode, NULL); + + g_mutex_lock(inode->fs->lock); + bluesky_list_unlink(&inode->fs->dirty_list, inode->dirty_list); + inode->dirty_list = bluesky_list_prepend(&inode->fs->dirty_list, inode); + bluesky_list_unlink(&inode->fs->accessed_list, inode->accessed_list); + inode->accessed_list = bluesky_list_prepend(&inode->fs->accessed_list, inode); + g_mutex_unlock(inode->fs->lock); } /* Unfortunately a glib hash table is only guaranteed to be able to store @@ -104,6 +111,7 @@ BlueSkyFS *bluesky_init_fs(gchar *name, BlueSkyStore *store) root->nlink = 1; root->mode = 0755; bluesky_insert_inode(fs, root); + bluesky_inode_update_ctime(root, TRUE); bluesky_inode_flush(fs, root); bluesky_superblock_flush(fs); @@ -124,10 +132,16 @@ void bluesky_inode_unref(BlueSkyInode *inode) inode->inum); /* Sanity check: Is the inode clean? */ - if (inode->change_commit < inode->change_count) { - g_warning("Dropping inode which is not clean (commit %"PRIi64" < change %"PRIi64")\n", inode->change_commit, inode->change_count); + if (inode->change_commit < inode->change_count + || inode->dirty_list != NULL) { + g_warning("Dropping inode which is not clean (commit %"PRIi64" < change %"PRIi64"; dirty_list = %p)\n", inode->change_commit, inode->change_count, inode->dirty_list); } + g_mutex_lock(inode->fs->lock); + bluesky_list_unlink(&inode->fs->accessed_list, inode->accessed_list); + bluesky_list_unlink(&inode->fs->dirty_list, inode->dirty_list); + g_mutex_unlock(inode->fs->lock); + /* Free file type specific data. It should be an error for there to be * dirty data to commit when the reference count has reaches zero. */ switch (inode->type) { @@ -328,6 +342,9 @@ static void complete_inode_fetch(BlueSkyStoreAsync *async, BlueSkyInode *inode) } inode->access_time = bluesky_get_current_time(); + g_mutex_lock(inode->fs->lock); + inode->accessed_list = bluesky_list_prepend(&inode->fs->accessed_list, inode); + g_mutex_unlock(inode->fs->lock); g_mutex_unlock(inode->lock); bluesky_inode_unref(inode); diff --git a/bluesky/util.c b/bluesky/util.c index 2e6f0aa..bd5ddd3 100644 --- a/bluesky/util.c +++ b/bluesky/util.c @@ -113,3 +113,64 @@ void bluesky_string_resize(BlueSkyRCStr *string, gsize len) string->data = g_realloc(string->data, len); string->len = len; } + +/* Cache LRU list management functions. These manage the doubly-linked list of + * inodes sorted by accessed/modified time. The FS lock should be held while + * calling these. + * + * _remove will unlink an inode from the linked list. + * + * _prepend and _append insert an inode at the head or tail of the linked list, + * and return a pointer to the linked list element (which should be stored in + * the inode); the inode should not already be in the list. + * + * _head and _tail simply return the first or last item inode in the list. */ +void bluesky_list_unlink(GList *head, GList *item) +{ + if (item == NULL) + return; + + if (head->prev == item) + head->prev = item->prev; + head->next = g_list_delete_link(head->next, item); +} + +GList *bluesky_list_prepend(GList *head, BlueSkyInode *inode) +{ + head->next = g_list_prepend(head->next, inode); + if (head->prev == NULL) + head->prev = g_list_last(head->next); + return head->next; +} + +GList *bluesky_list_append(GList *head, BlueSkyInode *inode) +{ + if (head->next == NULL) + return bluesky_list_prepend(head, inode); + + g_assert(head->prev != NULL && head->prev->next == NULL); + + GList *link = g_list_alloc(); + link->data = inode; + link->next = NULL; + link->prev = head->prev; + head->prev->next = link; + head->prev = link; + return link; +} + +BlueSkyInode *bluesky_list_head(GList *head) +{ + if (head->next == NULL) + return NULL; + else + return (BlueSkyInode *)head->next->data; +} + +BlueSkyInode *bluesky_list_tail(GList *head) +{ + if (head->prev == NULL) + return NULL; + else + return (BlueSkyInode *)head->prev->data; +} -- 2.20.1