[Tux3] Patch: Recursive redirect prototype with unit test
Daniel Phillips
phillips at phunq.net
Sun Jan 25 16:04:56 PST 2009
This has most of the mechanism for btree modification with redirect.
When we want to change a btree leaf, we redirect all blocks in the
path, up to the first block that is already dirty. This recursive
redirect only happens in cache. We will only write out the modified
leaf and log records that describe the changes to index nodes.
The dirty check is disabled for this test, so that the redirect always
goes all the way to the root.
diff -r 7a16d6ca2cf4 user/balloc-dummy.c
--- a/user/balloc-dummy.c Mon Jan 26 08:37:37 2009 +0900
+++ b/user/balloc-dummy.c Sun Jan 25 15:59:31 2009 -0800
@@ -1,12 +1,13 @@ int balloc(struct sb *sb, unsigned block
int balloc(struct sb *sb, unsigned blocks, block_t *block)
{
- trace("-> %Lx\n", (L)sb->nextalloc);
*block = sb->nextalloc += blocks;
+ trace("-> %Lx", (L)*block);
+ sb->nextalloc += blocks;
return 0;
}
int bfree(struct sb *sb, block_t block, unsigned blocks)
{
- trace("<- %Lx, count %x\n", (L)block, blocks);
+ trace("<- %Lx, count %x", (L)block, blocks);
return 0;
}
diff -r 7a16d6ca2cf4 user/btree.c
--- a/user/btree.c Mon Jan 26 08:37:37 2009 +0900
+++ b/user/btree.c Sun Jan 25 15:59:31 2009 -0800
@@ -12,10 +12,11 @@
#include "tux3.h" /* include user/tux3.h, not user/kernel/tux3.h */
#ifndef trace
-#define trace trace_off
+#define trace trace_on
#endif
#include "balloc-dummy.c"
+#include "kernel/log.c"
#include "kernel/btree.c"
struct uleaf { u32 magic, count; struct uentry { u16 key, val; } entries[]; };
@@ -102,7 +103,7 @@ void *uleaf_resize(struct btree *btree,
goto out;
if (uleaf_free(btree, leaf) < one)
return NULL;
- printf("expand leaf at 0x%x by %i\n", at, one);
+ trace_off("expand leaf at 0x%x by %i", at, one);
vecmove(leaf->entries + at + one, leaf->entries + at, leaf->count++ - at);
out:
return leaf->entries + at;
@@ -146,6 +147,7 @@ static void tree_expand_test(struct curs
struct uentry *entry = tree_expand(btree, key, 1, cursor);
*entry = (struct uentry){ .key = key, .val = key + 0x100 };
mark_buffer_dirty(cursor_leafbuf(cursor));
+cursor_redirect(cursor, cursor->btree->root.depth);
block_t block = bufindex(cursor_leafbuf(cursor));
release_cursor(cursor);
@@ -156,11 +158,17 @@ static void tree_expand_test(struct curs
release_cursor(cursor);
}
+int errio(struct buffer_head *buffer, int write)
+{
+ return -EINVAL;
+}
+
int main(int argc, char *argv[])
{
struct dev *dev = &(struct dev){ .bits = 6 };
struct sb *sb = &(struct sb){ INIT_SB(dev), };
sb->volmap = rapid_open_inode(sb, NULL, 0);
+ sb->logmap = rapid_open_inode(sb, errio, 0);
init_buffers(dev, 1 << 20, 0);
sb->entries_per_node = (sb->blocksize - offsetof(struct bnode, entries)) / sizeof(struct index_entry);
printf("entries_per_node = %i\n", sb->entries_per_node);
@@ -181,12 +189,13 @@ int main(int argc, char *argv[])
int until_new_depth = sb->entries_per_node * btree.entries_per_leaf + 1;
for (int key = 0; key < until_new_depth; key++)
tree_expand_test(cursor, key);
- show_tree_range(&btree, 0, -1);
+ show_tree(&btree);
+exit(0);
tree_chop(&btree, &(struct delete_info){ .key = 0 }, 0);
for (int key = until_new_depth * 100; key >= 0; key -= 100)
tree_expand_test(cursor, key);
- show_tree_range(&btree, 0, -1);
+ show_tree(&btree);
free_cursor(cursor);
tree_chop(&btree, &(struct delete_info){ .key = 0 }, 0);
diff -r 7a16d6ca2cf4 user/commit.c
--- a/user/commit.c Mon Jan 26 08:37:37 2009 +0900
+++ b/user/commit.c Sun Jan 25 15:59:31 2009 -0800
@@ -13,54 +13,6 @@
#endif
#include "inode.c"
-
-int cursor_redirect(struct cursor *cursor, unsigned level)
-{
- struct btree *btree = cursor->btree;
- struct sb *sb = btree->sb;
- struct buffer_head *buffer = cursor->path[level].buffer;
- assert(buffer_clean(buffer));
-
- /* Redirect Block */
-
- block_t oldblock = bufindex(buffer), newblock;
- int err = balloc(sb, 1, &newblock);
- if (err)
- return err;
- struct buffer_head *clone = blockget(mapping(sb->volmap), newblock);
- if (!clone)
- return -ENOMEM; // ERR_PTR me!!!
- memcpy(bufdata(clone), bufdata(buffer), bufsize(clone));
- mark_buffer_dirty(clone);
- cursor->path[level].buffer = clone;
- cursor->path[level].next += bufdata(clone) - bufdata(buffer);
- log_redirect(sb, oldblock, newblock);
- defer_free(&sb->defree, oldblock, 1);
- brelse(buffer);
-
- /* Update Parent */
-
- if (level) {
- struct index_entry *entry = cursor->path[level - 1].next - 1;
- block_t parent = bufindex(cursor->path[level - 1].buffer);
- assert(oldblock == from_be_u64(entry->block));
- entry->block = to_be_u64(newblock);
- log_update(sb, newblock, parent, from_be_u64(entry->key));
- return 0;
- }
-
- if (btree != itable_btree(sb)) {
- struct inode *inode = btree_inode(btree);
- assert(oldblock == btree->root.block);
- btree->root.block = newblock;
- log_droot(sb, newblock, oldblock, inode->inum);
- return 0;
- }
-
- assert(oldblock == from_be_u64(sb->super.iroot));
- log_iroot(sb, newblock, oldblock);
- return 0;
-}
void replay(struct sb *sb)
{
diff -r 7a16d6ca2cf4 user/kernel/btree.c
--- a/user/kernel/btree.c Mon Jan 26 08:37:37 2009 +0900
+++ b/user/kernel/btree.c Sun Jan 25 15:59:31 2009 -0800
@@ -321,6 +321,58 @@ void show_tree(struct btree *btree)
void show_tree(struct btree *btree)
{
show_tree_range(btree, 0, -1);
+}
+
+int cursor_redirect(struct cursor *cursor, unsigned level)
+{
+ struct btree *btree = cursor->btree;
+ struct sb *sb = btree->sb;
+ while (1) {
+ struct buffer_head *buffer = cursor->path[level].buffer;
+// if (buffer_dirty(buffer))
+// return 0;
+
+ block_t oldblock = bufindex(buffer), newblock;
+ int err = balloc(sb, 1, &newblock);
+ if (err)
+ return err;
+ trace("redirect block %Lx to %Lx", oldblock, newblock);
+ struct buffer_head *clone = blockget(mapping(sb->volmap), newblock);
+ if (!clone)
+ return -ENOMEM; // ERR_PTR me!!!
+ mark_buffer_dirty(clone);
+ memcpy(bufdata(clone), bufdata(buffer), bufsize(clone));
+ cursor->path[level].buffer = clone;
+ cursor->path[level].next += bufdata(clone) - bufdata(buffer);
+ brelse(buffer);
+ log_redirect(sb, oldblock, newblock);
+ defer_free(&sb->defree, oldblock, 1);
+
+ if (!level--) {
+ trace("redirect root");
+ if (btree != itable_btree(sb)) {
+ assert(oldblock == btree->root.block);
+ btree->root.block = newblock;
+ log_droot(sb, newblock, oldblock, tux_inode(btree_inode(btree))->inum);
+ return 0;
+ }
+
+ assert(oldblock == from_be_u64(sb->super.iroot));
+ log_iroot(sb, newblock, oldblock);
+ return 0;
+ }
+
+ trace("update parent");
+ struct index_entry *entry = cursor->path[level].next - 1;
+ block_t parent = bufindex(cursor->path[level].buffer);
+ assert(oldblock == from_be_u64(entry->block));
+ entry->block = to_be_u64(newblock);
+ log_update(sb, newblock, parent, from_be_u64(entry->key));
+ /*
+ * Note: this may change a clean buffer which is then copied
+ * and discarded, which seems a little strange but does no harm.
+ */
+ }
}
/* Deletion */
@@ -665,8 +717,8 @@ int new_btree(struct btree *btree, struc
struct buffer_head *leafbuf = new_leaf(btree);
if (!rootbuf || !leafbuf)
goto eek;
- trace("root at %Lx\n", (L)bufindex(rootbuf));
- trace("leaf at %Lx\n", (L)bufindex(leafbuf));
+ trace("root at %Lx", (L)bufindex(rootbuf));
+ trace("leaf at %Lx", (L)bufindex(leafbuf));
struct bnode *rootnode = bufdata(rootbuf);
rootnode->entries[0].block = to_be_u64(bufindex(leafbuf));
rootnode->count = to_be_u32(1);
diff -r 7a16d6ca2cf4 user/kernel/tux3.h
--- a/user/kernel/tux3.h Mon Jan 26 08:37:37 2009 +0900
+++ b/user/kernel/tux3.h Sun Jan 25 15:59:31 2009 -0800
@@ -731,6 +731,11 @@ static inline int bufcount(struct buffer
return atomic_read(&buffer->b_count);
}
+static inline int buffer_clean(struct buffer_head *buffer)
+{
+ return !buffer_dirty(buffer) || buffer_uptodate(buffer);
+}
+
/* btree.c */
struct buffer_head *cursor_leafbuf(struct cursor *cursor);
void release_cursor(struct cursor *cursor);
@@ -827,6 +832,9 @@ unsigned encode_xsize(struct inode *inod
/* log.c */
void log_alloc(struct sb *sb, block_t block, unsigned count, unsigned alloc);
void log_update(struct sb *sb, block_t child, block_t parent, tuxkey_t key);
+void log_redirect(struct sb *sb, block_t newblock, block_t oldblock);
+void log_droot(struct sb *sb, block_t newroot, block_t oldroot, tuxkey_t key);
+void log_iroot(struct sb *sb, block_t newroot, block_t oldroot);
int defer_free(struct stash *defree, block_t block, unsigned count);
int retire_frees(struct sb *sb, struct stash *defree);
void destroy_defree(struct stash *defree);
_______________________________________________
Tux3 mailing list
Tux3 at tux3.org
http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3
More information about the Tux3
mailing list