* Add rbtree backend for storing bitmaps
@ 2011-03-17 18:50 Lukas Czerner
2011-03-17 18:50 ` [PATCH 1/4 v2] e2fsprogs: Add rbtree library Lukas Czerner
` (3 more replies)
0 siblings, 4 replies; 13+ messages in thread
From: Lukas Czerner @ 2011-03-17 18:50 UTC (permalink / raw)
To: linux-ext4; +Cc: tytso, sandeen
Hello,
this is my second attempt to introduce new e2fsprogs bitmap backed based on
rbtree. In this second version a couple of thing got better. First of all I
have fixed all the bugs I was able to fing in the rbtree backend itself and
now it passed many smoke tests as well as "make check" cleanly.
The second change is that this set of patches does not actually set rbtree
backend as default, but rather introduce new configuration interface (in
PATCH 3) to set backend for each and every one bitmap used by e2fsprogs
individually. This allows us to better see what backend might be more
suitable for what particular bitmap, more sophisticated benchmarking and
testing.
Also to enable even more detailed understanding of how e2fsprogs treats
bitmaps I have iontroduced (in PATCH 4) new macro for enabling statistics
gathering about bitmaps. If the macro is set (in compile time) the code
is enabled and data is gathered. Then, when the bitmap is freed information
is printed to the stderr, so we can clearly compare bitmaps with each other.
So far I have not done any comprehensive benchmarks other than last time
(http://www.spinics.net/lists/linux-ext4/msg22664.html). Rbtree still has
good results (memory saved) with reasonable filesystems, but it can get much
worse in case of very fragmented filesystem. Also note that enabling rbtree
(for all bitmaps) cause cca 30% (instead of almost 60% in previous version)
performance hit on regular filesystem, but it can really differ.
Important thing is that this commits should not change e2fsprogs behavior in
any way, since neither rbtree backend, nor stats collection is enabled by
default.
If there is anyone with some /unusual/ filesystem (huge, tons of files,
really fragmented, etc..) willing to try it out and share the results it
will be great!
Comments are highly appreciated!
Thanks!
-Lukas
---
[PATCH 1/4] e2fsprogs: Add rbtree library
[PATCH 2/4] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays
[PATCH 3/4] Add bitmap configuration interface
[PATCH 4/4] Add macro to enable collecting bitmap statistics
e2fsck/emptydir.c | 4 +-
e2fsck/pass1.c | 18 +-
e2fsck/pass1b.c | 2 +-
e2fsck/pass3.c | 6 +-
e2fsck/pass5.c | 4 +-
e2fsck/unix.c | 7 +
lib/ext2fs/Makefile.in | 28 ++-
lib/ext2fs/bitmaps.c | 21 +-
lib/ext2fs/blkmap64_ba.c | 8 +
lib/ext2fs/blkmap64_rb.c | 829 +++++++++++++++++++++++++++++++++++++++++++++
lib/ext2fs/bmap64.h | 32 ++
lib/ext2fs/check_desc.c | 2 +-
lib/ext2fs/ext2fs.h | 40 ++-
lib/ext2fs/ext2fsP.h | 7 +-
lib/ext2fs/gen_bitmap64.c | 248 +++++++++++++-
lib/ext2fs/icount.c | 5 +-
lib/ext2fs/initialize.c | 18 +-
lib/ext2fs/rbtree.c | 451 ++++++++++++++++++++++++
lib/ext2fs/rbtree.h | 179 ++++++++++
lib/ext2fs/rw_bitmaps.c | 17 +-
lib/ext2fs/tst_iscan.c | 6 +-
misc/e2image.c | 4 +-
misc/tune2fs.c | 2 +-
resize/resize2fs.c | 6 +-
24 files changed, 1869 insertions(+), 75 deletions(-)
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/4 v2] e2fsprogs: Add rbtree library
2011-03-17 18:50 Add rbtree backend for storing bitmaps Lukas Czerner
@ 2011-03-17 18:50 ` Lukas Czerner
2011-03-17 19:34 ` Andreas Dilger
2011-03-17 18:50 ` [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays Lukas Czerner
` (2 subsequent siblings)
3 siblings, 1 reply; 13+ messages in thread
From: Lukas Czerner @ 2011-03-17 18:50 UTC (permalink / raw)
To: linux-ext4; +Cc: tytso, sandeen, Lukas Czerner
This commit adds rbtree library into e2fsprogs so it can be used for
various internal data structures. The rbtree implementation is ripped of
kernel rbtree implementation with small changes needed for it to work
outside kernel.
Signed-off-by: Lukas Czerner <lczerner@redhat.com>
---
lib/ext2fs/Makefile.in | 11 +-
lib/ext2fs/rbtree.c | 451 ++++++++++++++++++++++++++++++++++++++++++++++++
lib/ext2fs/rbtree.h | 179 +++++++++++++++++++
3 files changed, 639 insertions(+), 2 deletions(-)
create mode 100644 lib/ext2fs/rbtree.c
create mode 100644 lib/ext2fs/rbtree.h
diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 9c1c273..b24a53a 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -80,7 +80,8 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \
unix_io.o \
unlink.o \
valid_blk.o \
- version.o
+ version.o \
+ rbtree.o
SRCS= ext2_err.c \
$(srcdir)/alloc.c \
@@ -155,7 +156,8 @@ SRCS= ext2_err.c \
$(srcdir)/unlink.c \
$(srcdir)/valid_blk.c \
$(srcdir)/version.c \
- $(srcdir)/write_bb_file.c
+ $(srcdir)/write_bb_file.c \
+ $(srcdir)/rbtree.c \
HFILES= bitops.h ext2fs.h ext2_io.h ext2_fs.h ext2_ext_attr.h ext3_extents.h \
tdb.h
@@ -762,3 +764,8 @@ write_bb_file.o: $(srcdir)/write_bb_file.c $(srcdir)/ext2_fs.h \
$(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
$(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
$(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h
+rbtree.o: $(srcdir)/rbtree.c $(srcdir)/ext2_fs.h \
+ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
+ $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
+ $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
+ $(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h
diff --git a/lib/ext2fs/rbtree.c b/lib/ext2fs/rbtree.c
new file mode 100644
index 0000000..0b638cf
--- /dev/null
+++ b/lib/ext2fs/rbtree.c
@@ -0,0 +1,451 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+ (C) 2002 David Woodhouse <dwmw2@infradead.org>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/lib/rbtree.c
+*/
+
+#include "rbtree.h"
+
+static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *right = node->rb_right;
+ struct rb_node *parent = rb_parent(node);
+
+ if ((node->rb_right = right->rb_left))
+ rb_set_parent(right->rb_left, node);
+ right->rb_left = node;
+
+ rb_set_parent(right, parent);
+
+ if (parent)
+ {
+ if (node == parent->rb_left)
+ parent->rb_left = right;
+ else
+ parent->rb_right = right;
+ }
+ else
+ root->rb_node = right;
+ rb_set_parent(node, right);
+}
+
+static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *left = node->rb_left;
+ struct rb_node *parent = rb_parent(node);
+
+ if ((node->rb_left = left->rb_right))
+ rb_set_parent(left->rb_right, node);
+ left->rb_right = node;
+
+ rb_set_parent(left, parent);
+
+ if (parent)
+ {
+ if (node == parent->rb_right)
+ parent->rb_right = left;
+ else
+ parent->rb_left = left;
+ }
+ else
+ root->rb_node = left;
+ rb_set_parent(node, left);
+}
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *parent, *gparent;
+
+ while ((parent = rb_parent(node)) && rb_is_red(parent))
+ {
+ gparent = rb_parent(parent);
+
+ if (parent == gparent->rb_left)
+ {
+ {
+ register struct rb_node *uncle = gparent->rb_right;
+ if (uncle && rb_is_red(uncle))
+ {
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_right == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_left(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ __rb_rotate_right(gparent, root);
+ } else {
+ {
+ register struct rb_node *uncle = gparent->rb_left;
+ if (uncle && rb_is_red(uncle))
+ {
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_left == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_right(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ __rb_rotate_left(gparent, root);
+ }
+ }
+
+ rb_set_black(root->rb_node);
+}
+
+static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+ struct rb_root *root)
+{
+ struct rb_node *other;
+
+ while ((!node || rb_is_black(node)) && node != root->rb_node)
+ {
+ if (parent->rb_left == node)
+ {
+ other = parent->rb_right;
+ if (rb_is_red(other))
+ {
+ rb_set_black(other);
+ rb_set_red(parent);
+ __rb_rotate_left(parent, root);
+ other = parent->rb_right;
+ }
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
+ {
+ rb_set_red(other);
+ node = parent;
+ parent = rb_parent(node);
+ }
+ else
+ {
+ if (!other->rb_right || rb_is_black(other->rb_right))
+ {
+ rb_set_black(other->rb_left);
+ rb_set_red(other);
+ __rb_rotate_right(other, root);
+ other = parent->rb_right;
+ }
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
+ rb_set_black(other->rb_right);
+ __rb_rotate_left(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ else
+ {
+ other = parent->rb_left;
+ if (rb_is_red(other))
+ {
+ rb_set_black(other);
+ rb_set_red(parent);
+ __rb_rotate_right(parent, root);
+ other = parent->rb_left;
+ }
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
+ {
+ rb_set_red(other);
+ node = parent;
+ parent = rb_parent(node);
+ }
+ else
+ {
+ if (!other->rb_left || rb_is_black(other->rb_left))
+ {
+ rb_set_black(other->rb_right);
+ rb_set_red(other);
+ __rb_rotate_left(other, root);
+ other = parent->rb_left;
+ }
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
+ rb_set_black(other->rb_left);
+ __rb_rotate_right(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ }
+ if (node)
+ rb_set_black(node);
+}
+
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *child, *parent;
+ int color;
+
+ if (!node->rb_left)
+ child = node->rb_right;
+ else if (!node->rb_right)
+ child = node->rb_left;
+ else
+ {
+ struct rb_node *old = node, *left;
+
+ node = node->rb_right;
+ while ((left = node->rb_left) != NULL)
+ node = left;
+
+ if (rb_parent(old)) {
+ if (rb_parent(old)->rb_left == old)
+ rb_parent(old)->rb_left = node;
+ else
+ rb_parent(old)->rb_right = node;
+ } else
+ root->rb_node = node;
+
+ child = node->rb_right;
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (parent == old) {
+ parent = node;
+ } else {
+ if (child)
+ rb_set_parent(child, parent);
+ parent->rb_left = child;
+
+ node->rb_right = old->rb_right;
+ rb_set_parent(old->rb_right, node);
+ }
+
+ node->rb_parent_color = old->rb_parent_color;
+ node->rb_left = old->rb_left;
+ rb_set_parent(old->rb_left, node);
+
+ goto color;
+ }
+
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (child)
+ rb_set_parent(child, parent);
+ if (parent)
+ {
+ if (parent->rb_left == node)
+ parent->rb_left = child;
+ else
+ parent->rb_right = child;
+ }
+ else
+ root->rb_node = child;
+
+ color:
+ if (color == RB_BLACK)
+ __rb_erase_color(child, parent, root);
+}
+
+static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
+{
+ struct rb_node *parent;
+
+up:
+ func(node, data);
+ parent = rb_parent(node);
+ if (!parent)
+ return;
+
+ if (node == parent->rb_left && parent->rb_right)
+ func(parent->rb_right, data);
+ else if (parent->rb_left)
+ func(parent->rb_left, data);
+
+ node = parent;
+ goto up;
+}
+
+/*
+ * after inserting @node into the tree, update the tree to account for
+ * both the new entry and any damage done by rebalance
+ */
+void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
+{
+ if (node->rb_left)
+ node = node->rb_left;
+ else if (node->rb_right)
+ node = node->rb_right;
+
+ rb_augment_path(node, func, data);
+}
+
+/*
+ * before removing the node, find the deepest node on the rebalance path
+ * that will still be there after @node gets removed
+ */
+struct rb_node *rb_augment_erase_begin(struct rb_node *node)
+{
+ struct rb_node *deepest;
+
+ if (!node->rb_right && !node->rb_left)
+ deepest = rb_parent(node);
+ else if (!node->rb_right)
+ deepest = node->rb_left;
+ else if (!node->rb_left)
+ deepest = node->rb_right;
+ else {
+ deepest = rb_next(node);
+ if (deepest->rb_right)
+ deepest = deepest->rb_right;
+ else if (rb_parent(deepest) != node)
+ deepest = rb_parent(deepest);
+ }
+
+ return deepest;
+}
+
+/*
+ * after removal, update the tree to account for the removed entry
+ * and any rebalance damage.
+ */
+void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
+{
+ if (node)
+ rb_augment_path(node, func, data);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first(const struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_left)
+ n = n->rb_left;
+ return n;
+}
+
+struct rb_node *rb_last(const struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_right)
+ n = n->rb_right;
+ return n;
+}
+
+struct rb_node *rb_next(const struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a right-hand child, go down and then left as far
+ as we can. */
+ if (node->rb_right) {
+ node = node->rb_right;
+ while (node->rb_left)
+ node=node->rb_left;
+ return (struct rb_node *)node;
+ }
+
+ /* No right-hand children. Everything down and left is
+ smaller than us, so any 'next' node must be in the general
+ direction of our parent. Go up the tree; any time the
+ ancestor is a right-hand child of its parent, keep going
+ up. First time it's a left-hand child of its parent, said
+ parent is our 'next' node. */
+ while ((parent = rb_parent(node)) && node == parent->rb_right)
+ node = parent;
+
+ return parent;
+}
+
+struct rb_node *rb_prev(const struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a left-hand child, go down and then right as far
+ as we can. */
+ if (node->rb_left) {
+ node = node->rb_left;
+ while (node->rb_right)
+ node=node->rb_right;
+ return (struct rb_node *)node;
+ }
+
+ /* No left-hand children. Go up till we find an ancestor which
+ is a right-hand child of its parent */
+ while ((parent = rb_parent(node)) && node == parent->rb_left)
+ node = parent;
+
+ return parent;
+}
+
+void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root)
+{
+ struct rb_node *parent = rb_parent(victim);
+
+ /* Set the surrounding nodes to point to the replacement */
+ if (parent) {
+ if (victim == parent->rb_left)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else {
+ root->rb_node = new;
+ }
+ if (victim->rb_left)
+ rb_set_parent(victim->rb_left, new);
+ if (victim->rb_right)
+ rb_set_parent(victim->rb_right, new);
+
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+}
diff --git a/lib/ext2fs/rbtree.h b/lib/ext2fs/rbtree.h
new file mode 100644
index 0000000..8820e28
--- /dev/null
+++ b/lib/ext2fs/rbtree.h
@@ -0,0 +1,179 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree.h
+
+ To use rbtrees you'll have to implement your own insert and search cores.
+ This will avoid us to use callbacks and to drop drammatically performances.
+ I know it's not the cleaner way, but in C (not in C++) to get
+ performances and genericity...
+
+ Some example of insert and search follows here. The search is a plain
+ normal search over an ordered tree. The insert instead must be implemented
+ in two steps: First, the code must insert the element in order as a red leaf
+ in the tree, and then the support library function rb_insert_color() must
+ be called. Such function will do the not trivial work to rebalance the
+ rbtree, if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * rb_search_page_cache(struct inode * inode,
+ unsigned long offset)
+{
+ struct rb_node * n = inode->i_rb_page_cache.rb_node;
+ struct page * page;
+
+ while (n)
+ {
+ page = rb_entry(n, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ n = n->rb_left;
+ else if (offset > page->offset)
+ n = n->rb_right;
+ else
+ return page;
+ }
+ return NULL;
+}
+
+static inline struct page * __rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
+ struct rb_node * parent = NULL;
+ struct page * page;
+
+ while (*p)
+ {
+ parent = *p;
+ page = rb_entry(parent, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ p = &(*p)->rb_left;
+ else if (offset > page->offset)
+ p = &(*p)->rb_right;
+ else
+ return page;
+ }
+
+ rb_link_node(node, parent, p);
+
+ return NULL;
+}
+
+static inline struct page * rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct page * ret;
+ if ((ret = __rb_insert_page_cache(inode, offset, node)))
+ goto out;
+ rb_insert_color(node, &inode->i_rb_page_cache);
+ out:
+ return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef _LINUX_RBTREE_H
+#define _LINUX_RBTREE_H
+
+#include <stdlib.h>
+
+#undef offsetof
+#ifdef __compiler_offsetof
+#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
+#else
+#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
+#endif
+
+#define container_of(ptr, type, member) ({ \
+ const typeof( ((type *)0)->member ) *__mptr = (ptr); \
+ (type *)( (char *)__mptr - offsetof(type,member) );})
+
+struct rb_node
+{
+ unsigned long rb_parent_color;
+#define RB_RED 0
+#define RB_BLACK 1
+ struct rb_node *rb_right;
+ struct rb_node *rb_left;
+} __attribute__((aligned(sizeof(long))));
+ /* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct rb_root
+{
+ struct rb_node *rb_node;
+};
+
+
+#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
+#define rb_color(r) ((r)->rb_parent_color & 1)
+#define rb_is_red(r) (!rb_color(r))
+#define rb_is_black(r) rb_color(r)
+#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
+#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+ rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void rb_set_color(struct rb_node *rb, int color)
+{
+ rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
+#define RB_ROOT (struct rb_root) { NULL, }
+#define rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
+#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
+#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
+
+extern void rb_insert_color(struct rb_node *, struct rb_root *);
+extern void rb_erase(struct rb_node *, struct rb_root *);
+
+typedef void (*rb_augment_f)(struct rb_node *node, void *data);
+
+extern void rb_augment_insert(struct rb_node *node,
+ rb_augment_f func, void *data);
+extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);
+extern void rb_augment_erase_end(struct rb_node *node,
+ rb_augment_f func, void *data);
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *rb_next(const struct rb_node *);
+extern struct rb_node *rb_prev(const struct rb_node *);
+extern struct rb_node *rb_first(const struct rb_root *);
+extern struct rb_node *rb_last(const struct rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root);
+
+static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
+ struct rb_node ** rb_link)
+{
+ node->rb_parent_color = (unsigned long )parent;
+ node->rb_left = node->rb_right = NULL;
+
+ *rb_link = node;
+}
+
+#endif /* _LINUX_RBTREE_H */
--
1.7.4
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays
2011-03-17 18:50 Add rbtree backend for storing bitmaps Lukas Czerner
2011-03-17 18:50 ` [PATCH 1/4 v2] e2fsprogs: Add rbtree library Lukas Czerner
@ 2011-03-17 18:50 ` Lukas Czerner
2011-03-17 19:56 ` Andreas Dilger
2011-03-17 18:50 ` [PATCH 3/4] Add bitmap configuration interface Lukas Czerner
2011-03-17 18:50 ` [PATCH 4/4] Add macro to enable collecting bitmap statistics Lukas Czerner
3 siblings, 1 reply; 13+ messages in thread
From: Lukas Czerner @ 2011-03-17 18:50 UTC (permalink / raw)
To: linux-ext4; +Cc: tytso, sandeen, Lukas Czerner
For a long time we had a bitarray backend for storing filesystem
metadata bitmaps, however today this approach might hit its limits with
todays huge data storage devices, because of its memory utilization.
Bitarrays stores bitmaps as ..well, as bitmaps. But this is in most
cases highly unefficient because we need to allocate memory even for the
big parts of bitmaps we will never use, resulting in high memory
utilization especially for huge filesystem, when bitmaps might occupy
gigabytes of space.
This commit adds another backend to store bitmaps. It is based on
rbtrees and it stores just used extents of bitmaps. It means that it can
be more memory efficient in most cases.
I have done some limited benchmarking and it shows that rbtree backend
consumes approx 65% less memory that bitarray on 312GB filesystem aged
with Impression (default config). This number may grow significantly
with the filesystem size, but also it may be a lot lower (even negative)
with a lot bigger number of inodes (need more benchmarking).
This commit itself does not enable the use of rbtree backend.
Signed-off-by: Lukas Czerner <lczerner@redhat.com>
---
lib/ext2fs/Makefile.in | 2 +
lib/ext2fs/blkmap64_rb.c | 751 +++++++++++++++++++++++++++++++++++++++++++++
lib/ext2fs/bmap64.h | 1 +
lib/ext2fs/ext2fsP.h | 1 +
lib/ext2fs/gen_bitmap64.c | 4 +
5 files changed, 759 insertions(+), 0 deletions(-)
create mode 100644 lib/ext2fs/blkmap64_rb.c
diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index b24a53a..29d1994 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -27,6 +27,7 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \
bitmaps.o \
bitops.o \
blkmap64_ba.o \
+ blkmap64_rb.o \
blknum.o \
block.o \
bmap.o \
@@ -94,6 +95,7 @@ SRCS= ext2_err.c \
$(srcdir)/bitmaps.c \
$(srcdir)/bitops.c \
$(srcdir)/blkmap64_ba.o \
+ $(srcdir)/blkmap64_rb.c \
$(srcdir)/block.c \
$(srcdir)/bmap.c \
$(srcdir)/check_desc.c \
diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
new file mode 100644
index 0000000..8f121b3
--- /dev/null
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -0,0 +1,751 @@
+/*
+ * blkmap64_rb.c --- Simple rb-tree implementation for bitmaps
+ *
+ * (C)2010 Red Hat, Inc., Lukas Czerner <lczerner@redhat.com>
+ *
+ * %Begin-Header%
+ * This file may be redistributed under the terms of the GNU Public
+ * License.
+ * %End-Header%
+ */
+
+#include <stdio.h>
+#include <string.h>
+#if HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+#include <fcntl.h>
+#include <time.h>
+#if HAVE_SYS_STAT_H
+#include <sys/stat.h>
+#endif
+#if HAVE_SYS_TYPES_H
+#include <sys/types.h>
+#endif
+
+#include "ext2_fs.h"
+#include "ext2fsP.h"
+#include "bmap64.h"
+#include "rbtree.h"
+
+#include <limits.h>
+
+struct bmap_rb_extent {
+ struct rb_node node;
+ __u64 start;
+ __u32 count;
+};
+
+struct ext2fs_rb_private {
+ struct rb_root root;
+ struct bmap_rb_extent **wcursor;
+ struct bmap_rb_extent **rcursor;
+};
+
+static int rb_insert_extent(__u64 start, __u64 count,
+ struct ext2fs_rb_private *);
+static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64);
+
+/*#define DEBUG_RB*/
+
+#ifdef DEBUG_RB
+static void print_tree(struct rb_root *root)
+{
+ struct rb_node *node = NULL;
+ struct bmap_rb_extent *ext;
+
+ printf("\t\t\t=================================\n");
+ node = rb_first(root);
+ for (node = rb_first(root); node != NULL; node=rb_next(node)) {
+ ext = rb_entry(node, struct bmap_rb_extent, node);
+ printf("\t\t\t--> (%llu -> %llu)\n",
+ ext->start, ext->start + ext->count);
+ }
+ printf("\t\t\t=================================\n");
+}
+
+static int check_tree(struct rb_root *root, const char *msg)
+{
+ struct rb_node *new_node, *node, *next;
+ struct bmap_rb_extent *ext, *old = NULL;
+
+ for (node = rb_first(root); node; node = rb_next(node)) {
+ ext = rb_entry(node, struct bmap_rb_extent, node);
+ if (ext->count <= 0) {
+ printf("Tree Error: count is crazy\n");
+ printf("extent: %llu -> %llu (%llu)\n", ext->start,
+ ext->start + ext->count, ext->count);
+ goto err_out;
+ }
+ if (ext->start < 0) {
+ printf("Tree Error: start is crazy\n");
+ printf("extent: %llu -> %llu (%llu)\n", ext->start,
+ ext->start + ext->count, ext->count);
+ goto err_out;
+ }
+
+ if (old) {
+ if (old->start > ext->start) {
+ printf("Tree Error: start is crazy\n");
+ printf("extent: %llu -> %llu (%llu)\n",
+ old->start, old->start + old->count,
+ old->count);
+ printf("extent next: %llu -> %llu (%llu)\n",
+ ext->start, ext->start + ext->count,
+ ext->count);
+ goto err_out;
+ }
+ if ((old->start + old->count) >= ext->start) {
+ printf("Tree Error: extent is crazy\n");
+ printf("extent: %llu -> %llu (%llu)\n",
+ old->start, old->start + old->count,
+ old->count);
+ printf("extent next: %llu -> %llu (%llu)\n",
+ ext->start, ext->start + ext->count,
+ ext->count);
+ goto err_out;
+ }
+ }
+ old = ext;
+ }
+ return 0;
+
+err_out:
+ printf("%s\n", msg);
+ print_tree(root);
+ exit(1);
+}
+#else
+#define check_tree(root, msg) 0
+#define print_tree(root, msg) 0
+#endif
+
+static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start,
+ __u64 count)
+{
+ struct bmap_rb_extent *new_ext;
+ int retval;
+
+ retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
+ &new_ext);
+ if (retval) {
+ perror("ext2fs_get_mem");
+ exit(1);
+ }
+
+ new_ext->start = start;
+ new_ext->count = count;
+ *ext = new_ext;
+}
+
+inline
+static void rb_free_extent(struct ext2fs_rb_private *bp,
+ struct bmap_rb_extent *ext)
+{
+ if (*bp->wcursor == ext)
+ *bp->wcursor = NULL;
+ if (*bp->rcursor == ext)
+ *bp->rcursor = NULL;
+ ext2fs_free_mem(&ext);
+}
+
+static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
+{
+ struct ext2fs_rb_private *bp;
+ errcode_t retval;
+
+ retval = ext2fs_get_mem(sizeof (struct ext2fs_rb_private), &bp);
+ if (retval)
+ return retval;
+
+ bp->root = RB_ROOT;
+ retval = ext2fs_get_mem(sizeof(struct bmap_rb_extent *), &bp->rcursor);
+ if (retval)
+ return retval;
+ retval = ext2fs_get_mem(sizeof(struct bmap_rb_extent *), &bp->wcursor);
+ if (retval)
+ return retval;
+ *bp->rcursor = NULL;
+ *bp->wcursor = NULL;
+
+ bitmap->private = (void *) bp;
+ return 0;
+}
+
+static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
+ ext2fs_generic_bitmap bitmap)
+{
+ errcode_t retval;
+
+ retval = rb_alloc_private_data (bitmap);
+ if (retval)
+ return retval;
+
+ return 0;
+}
+
+static void rb_free_tree(struct rb_root *root)
+{
+ struct bmap_rb_extent *ext;
+ struct rb_node *node, *next;
+
+ for (node = rb_first(root); node; node = next) {
+ next = rb_next(node);
+ ext = rb_entry(node, struct bmap_rb_extent, node);
+ rb_erase(node, root);
+ ext2fs_free_mem(&ext);
+ }
+}
+
+static void rb_free_bmap(ext2fs_generic_bitmap bitmap)
+{
+ struct ext2fs_rb_private *bp;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+
+ rb_free_tree(&bp->root);
+ ext2fs_free_mem(&bp->rcursor);
+ ext2fs_free_mem(&bp->wcursor);
+ ext2fs_free_mem(&bp);
+ bp = 0;
+}
+
+static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src,
+ ext2fs_generic_bitmap dest)
+{
+ struct ext2fs_rb_private *src_bp, *dest_bp;
+ struct bmap_rb_extent *src_ext, *dest_ext;
+ struct rb_node *dest_node, *src_node, *dest_last, **n;
+ errcode_t retval = 0;
+
+ retval = rb_alloc_private_data (dest);
+ if (retval)
+ return retval;
+
+ src_bp = (struct ext2fs_rb_private *) src->private;
+ dest_bp = (struct ext2fs_rb_private *) dest->private;
+ *src_bp->rcursor = NULL;
+ *dest_bp->rcursor = NULL;
+
+ src_node = rb_first(&src_bp->root);
+ while (src_node) {
+ src_ext = rb_entry(src_node, struct bmap_rb_extent, node);
+ retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
+ &dest_ext);
+ if (retval)
+ break;
+
+ memcpy(dest_ext, src_ext, sizeof(struct bmap_rb_extent));
+
+ dest_node = &dest_ext->node;
+ n = &dest_bp->root.rb_node;
+
+ dest_last = NULL;
+ if (*n) {
+ dest_last = rb_last(&dest_bp->root);
+ n = &(dest_last)->rb_right;
+ }
+
+ rb_link_node(dest_node, dest_last, n);
+ rb_insert_color(dest_node, &dest_bp->root);
+
+ src_node = rb_next(src_node);
+ }
+
+ return retval;
+}
+
+static void rb_truncate(__u64 new_max, struct rb_root *root)
+{
+ struct bmap_rb_extent *ext;
+ struct rb_node *node;
+
+ node = rb_last(root);
+ while (node) {
+ ext = rb_entry(node, struct bmap_rb_extent, node);
+
+ if ((ext->start + ext->count - 1) <= new_max)
+ break;
+ else if (ext->start > new_max) {
+ rb_erase(node, root);
+ ext2fs_free_mem(&ext);
+ node = rb_last(root);
+ continue;
+ } else
+ ext->count = new_max - ext->start + 1;
+ }
+}
+
+static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
+ __u64 new_end, __u64 new_real_end)
+{
+ struct ext2fs_rb_private *bp;
+
+ if (new_real_end >= bmap->real_end) {
+ bmap->end = new_end;
+ bmap->real_end = new_real_end;
+ return 0;
+ }
+
+ bp = (struct ext2fs_rb_private *) bmap->private;
+ *bp->rcursor = NULL;
+ *bp->wcursor = NULL;
+
+ /* truncate tree to new_real_end size */
+ rb_truncate(new_real_end, &bp->root);
+
+ bmap->end = new_end;
+ bmap->real_end = new_real_end;
+ return 0;
+
+}
+
+inline static int
+rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
+{
+ struct bmap_rb_extent *rcursor;
+ struct rb_node *parent = NULL;
+ struct rb_node **n = &bp->root.rb_node;
+ struct bmap_rb_extent *ext;
+ int i=0;
+
+ rcursor = *bp->rcursor;
+ if (!rcursor)
+ goto search_tree;
+
+ if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
+ return 1;
+
+ rcursor = *bp->wcursor;
+ if (!rcursor)
+ goto search_tree;
+
+ if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
+ return 1;
+
+search_tree:
+
+ while (*n) {
+ parent = *n;
+ ext = rb_entry(parent, struct bmap_rb_extent, node);
+ if (bit < ext->start)
+ n = &(*n)->rb_left;
+ else if (bit >= (ext->start + ext->count))
+ n = &(*n)->rb_right;
+ else {
+ *bp->rcursor = ext;
+ return 1;
+ }
+ }
+ return 0;
+}
+
+static int rb_insert_extent(__u64 start, __u64 count,
+ struct ext2fs_rb_private *bp)
+{
+ struct rb_root *root = &bp->root;
+ struct rb_node *parent = NULL, **n = &root->rb_node;
+ struct rb_node *new_node, *node, *next;
+ struct bmap_rb_extent *new_ext;
+ struct bmap_rb_extent *ext;
+ int retval = 0;
+
+ ext = *bp->wcursor;
+ if (ext) {
+ if (start >= ext->start &&
+ start <= (ext->start + ext->count))
+ goto got_extent;
+ }
+
+ while (*n) {
+ parent = *n;
+ ext = rb_entry(parent, struct bmap_rb_extent, node);
+
+ if (start < ext->start) {
+ n = &(*n)->rb_left;
+ } else if (start > (ext->start + ext->count)) {
+ n = &(*n)->rb_right;
+ } else {
+got_extent:
+ if ((start + count) <= (ext->start + ext->count))
+ return 1;
+
+ if ((ext->start + ext->count) == start)
+ retval = 0;
+ else
+ retval = 1;
+
+ count += (start - ext->start);
+ start = ext->start;
+ new_ext = ext;
+ new_node = &ext->node;
+
+ goto skip_insert;
+ }
+ }
+
+ rb_get_new_extent(&new_ext, start, count);
+
+ new_node = &new_ext->node;
+ rb_link_node(new_node, parent, n);
+ rb_insert_color(new_node, root);
+ *bp->wcursor = new_ext;
+
+ node = rb_prev(new_node);
+ if (node) {
+ ext = rb_entry(node, struct bmap_rb_extent, node);
+ if ((ext->start + ext->count) == start) {
+ start = ext->start;
+ count += ext->count;
+ rb_erase(node, root);
+ rb_free_extent(bp, ext);
+ }
+ }
+
+skip_insert:
+ /* See if we can merge extent to the right */
+ for (node = rb_next(new_node); node != NULL; node = next) {
+ next = rb_next(node);
+ ext = rb_entry(node, struct bmap_rb_extent, node);
+
+ if ((ext->start + ext->count) <= start)
+ continue;
+
+ /* No more merging */
+ if ((start + count) < ext->start)
+ break;
+
+ /* ext is embedded in new_ext interval */
+ if ((start + count) >= (ext->start + ext->count)) {
+ rb_erase(node, root);
+ rb_free_extent(bp, ext);
+ continue;
+ } else {
+ /* merge ext with new_ext */
+ count += ((ext->start + ext->count) -
+ (start + count));
+ rb_erase(node, root);
+ rb_free_extent(bp, ext);
+ break;
+ }
+ }
+
+ new_ext->start = start;
+ new_ext->count = count;
+
+ return retval;
+}
+
+static int rb_remove_extent(struct bmap_rb_extent *del_ext,
+ struct ext2fs_rb_private *bp)
+{
+ struct rb_root *root = &bp->root;
+ struct rb_node *parent = NULL, **n = &root->rb_node;
+ struct rb_node *node;
+ struct bmap_rb_extent *ext;
+ __u64 start, count;
+ int retval = 0;
+
+ if (RB_EMPTY_ROOT(root))
+ return 0;
+
+ start = del_ext->start;
+ count = del_ext->count;
+
+ while (*n) {
+ parent = *n;
+ ext = rb_entry(parent, struct bmap_rb_extent, node);
+ if (start < ext->start) {
+ n = &(*n)->rb_left;
+ continue;
+ } else if (start >= (ext->start + ext->count)) {
+ n = &(*n)->rb_right;
+ continue;
+ }
+
+ if ((start > ext->start) &&
+ (start + count) < (ext->start + ext->count)) {
+ /* We have to split extent into two */
+ del_ext->start = start + count;
+ del_ext->count = (ext->start + ext->count) -
+ del_ext->start;
+
+ ext->count = start - ext->start;
+
+ rb_insert_extent(del_ext->start, del_ext->count, bp);
+ ext2fs_free_mem(&del_ext);
+ return 1;
+ }
+
+ if ((start + count) >= (ext->start + ext->count))
+ ext->count = start - ext->start;
+
+ if (0 == ext->count) {
+ parent = rb_next(&ext->node);
+ rb_erase(&ext->node, root);
+ rb_free_extent(bp, ext);
+ break;
+ }
+
+ if (start == ext->start) {
+ ext->start += count;
+ ext->count -= count;
+ return retval;
+ }
+ }
+
+ /* See if we should delete or truncate extent on the right */
+ for (; parent != NULL; parent = node) {
+ node = rb_next(parent);
+ ext = rb_entry(parent, struct bmap_rb_extent, node);
+ if ((ext->start + ext->count) <= start)
+ continue;
+
+ /* No more merging */
+ if ((start + count) < ext->start)
+ break;
+
+ /* ext is embedded in new_ext interval */
+ if ((start + count) >= (ext->start + ext->count)) {
+ rb_erase(parent, root);
+ rb_free_extent(bp, ext);
+ continue;
+ } else {
+ /* merge ext with new_ext */
+ ext->count -= ((start + count) - ext->start);
+ ext->start = start + count;
+ break;
+ }
+ }
+
+ return retval;
+}
+
+static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
+{
+ struct ext2fs_rb_private *bp;
+ int i;
+
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+ arg -= bitmap->start;
+
+ return rb_insert_extent(arg, 1, bp);
+}
+
+static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
+{
+ struct ext2fs_rb_private *bp;
+ struct bmap_rb_extent *del_ext;
+ int retval;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+ arg -= bitmap->start;
+
+ rb_get_new_extent(&del_ext, arg, 1);
+
+ retval = rb_remove_extent(del_ext, bp);
+ if (!retval)
+ ext2fs_free_mem(&del_ext);
+ check_tree(&bp->root, __func__);
+
+ return retval;
+}
+
+inline
+static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
+{
+ struct ext2fs_rb_private *bp;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+ arg -= bitmap->start;
+
+ return rb_test_bit(bp, arg);
+}
+
+static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
+ unsigned int num)
+{
+ struct ext2fs_rb_private *bp;
+ struct bmap_rb_extent *new_ext;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+ arg -= bitmap->start;
+
+ rb_insert_extent(arg, num, bp);
+}
+
+static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
+ unsigned int num)
+{
+ struct ext2fs_rb_private *bp;
+ struct bmap_rb_extent *del_ext;
+ int ret;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+ arg -= bitmap->start;
+
+ rb_get_new_extent(&del_ext, arg, num);
+ rb_remove_extent(del_ext, bp);
+ check_tree(&bp->root, __func__);
+}
+
+static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
+ __u64 start, unsigned int len)
+{
+ struct rb_node *parent = NULL, **n;
+ struct rb_node *node, *next;
+ struct ext2fs_rb_private *bp;
+ struct bmap_rb_extent *ext;
+ int retval = 1;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+ n = &bp->root.rb_node;
+ start -= bitmap->start;
+
+ if ((len == 0) ||
+ RB_EMPTY_ROOT(&bp->root))
+ return 1;
+
+ /*
+ * If we find nothing, we should examine whole extent, but
+ * when we find match, the extent is not clean, thus be return
+ * false.
+ */
+ while (*n) {
+ parent = *n;
+ ext = rb_entry(parent, struct bmap_rb_extent, node);
+ if (start < ext->start) {
+ n = &(*n)->rb_left;
+ } else if (start >= (ext->start + ext->count)) {
+ n = &(*n)->rb_right;
+ } else {
+ /*
+ * We found extent int the tree -> extent is not
+ * clean
+ */
+ return 0;
+ }
+ }
+
+ node = parent;
+ while (node) {
+ next = rb_next(node);
+ ext = rb_entry(node, struct bmap_rb_extent, node);
+ node = next;
+
+ if ((ext->start + ext->count) <= start)
+ continue;
+
+ /* No more merging */
+ if ((start + len) <= ext->start)
+ break;
+
+ retval = 0;
+ break;
+ }
+ return retval;
+}
+
+static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
+ __u64 start, size_t num, void *in)
+{
+ struct ext2fs_rb_private *bp;
+ size_t i;
+ int ret;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+
+ for (i = 0; i < num; i++) {
+ ret = ext2fs_test_bit(i, in);
+ if (ret)
+ rb_insert_extent(start + i - bitmap->start, 1, bp);
+ }
+
+ return 0;
+}
+
+static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
+ __u64 start, size_t num, void *out)
+{
+
+ struct rb_node *parent = NULL, *next, **n;
+ struct ext2fs_rb_private *bp;
+ struct bmap_rb_extent *ext;
+ __u64 pos;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+ n = &bp->root.rb_node;
+ start -= bitmap->start;
+
+ if (RB_EMPTY_ROOT(&bp->root)) {
+ return 0;
+ }
+
+ while (*n) {
+ parent = *n;
+ ext = rb_entry(parent, struct bmap_rb_extent, node);
+ if (start < ext->start) {
+ n = &(*n)->rb_left;
+ } else if (start >= (ext->start + ext->count)) {
+ n = &(*n)->rb_right;
+ } else
+ break;
+ }
+
+ pos = start;
+ for (; parent != NULL; parent = next) {
+ next = rb_next(parent);
+ ext = rb_entry(parent, struct bmap_rb_extent, node);
+
+ while (((pos - start) < num) &&
+ (pos < ext->start)) {
+ ext2fs_fast_clear_bit64((pos - start), out);
+ pos++;
+ }
+
+ if ((pos - start) >= num)
+ return 0;
+
+ while (((pos - start) < num) &&
+ (pos < (ext->start + ext->count))) {
+ ext2fs_fast_set_bit64((pos - start), out);
+ pos++;
+ }
+ }
+
+ while ((pos - start) < num) {
+ ext2fs_fast_clear_bit64((pos - start), out);
+ pos++;
+ }
+
+ return 0;
+}
+
+static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
+{
+ struct ext2fs_rb_private *bp;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+
+ rb_free_tree(&bp->root);
+ *bp->rcursor = NULL;
+ *bp->wcursor = NULL;
+}
+
+struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
+ .type = EXT2FS_BMAP64_RBTREE,
+ .new_bmap = rb_new_bmap,
+ .free_bmap = rb_free_bmap,
+ .copy_bmap = rb_copy_bmap,
+ .resize_bmap = rb_resize_bmap,
+ .mark_bmap = rb_mark_bmap,
+ .unmark_bmap = rb_unmark_bmap,
+ .test_bmap = rb_test_bmap,
+ .test_clear_bmap_extent = rb_test_clear_bmap_extent,
+ .mark_bmap_extent = rb_mark_bmap_extent,
+ .unmark_bmap_extent = rb_unmark_bmap_extent,
+ .set_bmap_range = rb_set_bmap_range,
+ .get_bmap_range = rb_get_bmap_range,
+ .clear_bmap = rb_clear_bmap,
+};
diff --git a/lib/ext2fs/bmap64.h b/lib/ext2fs/bmap64.h
index b0aa84c..31021b9 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -59,3 +59,4 @@ struct ext2_bitmap_ops {
};
extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray;
+extern struct ext2_bitmap_ops ext2fs_blkmap64_rbtree;
diff --git a/lib/ext2fs/ext2fsP.h b/lib/ext2fs/ext2fsP.h
index ab9ee76..aa45c43 100644
--- a/lib/ext2fs/ext2fsP.h
+++ b/lib/ext2fs/ext2fsP.h
@@ -108,6 +108,7 @@ extern void ext2fs_numeric_progress_close(ext2_filsys fs,
*/
#define EXT2FS_BMAP64_BITARRAY 1
+#define EXT2FS_BMAP64_RBTREE 2
extern errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
int type, __u64 start, __u64 end,
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index df095ac..84065ea 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -91,6 +91,9 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
case EXT2FS_BMAP64_BITARRAY:
ops = &ext2fs_blkmap64_bitarray;
break;
+ case EXT2FS_BMAP64_RBTREE:
+ ops = &ext2fs_blkmap64_rbtree;
+ break;
default:
return EINVAL;
}
@@ -158,6 +161,7 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
bmap->description = 0;
}
bmap->magic = 0;
+ ext2fs_free_mem(&bmap);
}
errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
--
1.7.4
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH 3/4] Add bitmap configuration interface
2011-03-17 18:50 Add rbtree backend for storing bitmaps Lukas Czerner
2011-03-17 18:50 ` [PATCH 1/4 v2] e2fsprogs: Add rbtree library Lukas Czerner
2011-03-17 18:50 ` [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays Lukas Czerner
@ 2011-03-17 18:50 ` Lukas Czerner
2011-03-17 21:03 ` Andreas Dilger
2011-03-17 18:50 ` [PATCH 4/4] Add macro to enable collecting bitmap statistics Lukas Czerner
3 siblings, 1 reply; 13+ messages in thread
From: Lukas Czerner @ 2011-03-17 18:50 UTC (permalink / raw)
To: linux-ext4; +Cc: tytso, sandeen, Lukas Czerner
Add a possibility for user to configure what bitmap backed will be used
for what bitmap. It is also useful for testing and benchmarking
different bitmap backends and its behaviour.
Setting can be done via usual config file with new section [bitmaps]
with subnames defining particular bitmaps. Argument is simply number of
the backend. All backends are defined in ext2fsP.h like this:
enum ext2fs_bmap_backends {
EXT2FS_BMAP64_BITARRAY = 0,
EXT2FS_BMAP64_RBTREE,
EXT2FS_BMAP64_COUNT,
};
Here is an example of bitmap configuration, with the list of all
supported bitmaps.
[bitmaps]
generic_bitmap = 1
inode_used_map = 1
inode_bad_map = 1
inode_dir_map = 0
inode_bb_map = 1
inode_imagic_map = 0
inode_reg_map = 1
block_found_map = 0
block_dup_map = 1
block_ea_map = 0
empty_dir_blocks = 1
empty_dir_map = 0
block_bitmap = 0
inode_bitmap = 1
check_desc_map = 0
bad_block_map = 1
touched_map = 0
block_scramble_map = 1
block_to_move = 0
block_reserved = 1
block_meta_data = 0
inode_dup_map = 1
inode_done_map = 0
inode_loop_map = 1
Note that EXT2FS_BMAP64_BITARRAY is still left as a default bitmap
backend, so nothing is changed for the user, unless bitmap configuration
section is used.
This feature requires interface change of ext2fs_alloc_generic_bmap()
and its definition now is:
errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
int type, __u64 start, __u64 end,
__u64 real_end,
ext2fs_generic_bitmap *ret)
Also note that this does work for 64-bit bitmaps only.
Signed-off-by: Lukas Czerner <lczerner@redhat.com>
---
e2fsck/emptydir.c | 4 +-
e2fsck/pass1.c | 18 ++++----
e2fsck/pass1b.c | 2 +-
e2fsck/pass3.c | 6 ++-
e2fsck/pass5.c | 4 +-
e2fsck/unix.c | 7 +++
lib/ext2fs/Makefile.in | 17 ++++++-
lib/ext2fs/bitmaps.c | 21 +++++----
lib/ext2fs/check_desc.c | 2 +-
lib/ext2fs/ext2fs.h | 36 +++++++++++++-
lib/ext2fs/ext2fsP.h | 8 ++-
lib/ext2fs/gen_bitmap64.c | 118 ++++++++++++++++++++++++++++++++++++++++++++-
lib/ext2fs/icount.c | 5 +-
lib/ext2fs/initialize.c | 18 ++-----
lib/ext2fs/rw_bitmaps.c | 17 ++-----
lib/ext2fs/tst_iscan.c | 6 +-
misc/e2image.c | 4 +-
misc/tune2fs.c | 2 +-
resize/resize2fs.c | 6 +-
19 files changed, 227 insertions(+), 74 deletions(-)
diff --git a/e2fsck/emptydir.c b/e2fsck/emptydir.c
index cf9b521..10dd3a7 100644
--- a/e2fsck/emptydir.c
+++ b/e2fsck/emptydir.c
@@ -53,12 +53,12 @@ empty_dir_info init_empty_dir(e2fsck_t ctx)
if (retval)
goto errout;
- retval = ext2fs_allocate_block_bitmap(ctx->fs, _("empty dirblocks"),
+ retval = ext2fs_allocate_block_bitmap(ctx->fs, EXT2_EMPTY_DIR_BLOCKS,
&edi->empty_dir_blocks);
if (retval)
goto errout;
- retval = ext2fs_allocate_inode_bitmap(ctx->fs, _("empty dir map"),
+ retval = ext2fs_allocate_inode_bitmap(ctx->fs, EXT2_EMPTY_DIR_MAP,
&edi->dir_map);
if (retval)
goto errout;
diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index 67dd986..7c2792c 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
@@ -593,7 +593,7 @@ void e2fsck_pass1(e2fsck_t ctx)
/*
* Allocate bitmaps structures
*/
- pctx.errcode = ext2fs_allocate_inode_bitmap(fs, _("in-use inode map"),
+ pctx.errcode = ext2fs_allocate_inode_bitmap(fs, EXT2_INODE_USED_MAP,
&ctx->inode_used_map);
if (pctx.errcode) {
pctx.num = 1;
@@ -602,7 +602,7 @@ void e2fsck_pass1(e2fsck_t ctx)
return;
}
pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
- _("directory inode map"), &ctx->inode_dir_map);
+ EXT2_INODE_DIR_MAP, &ctx->inode_dir_map);
if (pctx.errcode) {
pctx.num = 2;
fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
@@ -610,14 +610,14 @@ void e2fsck_pass1(e2fsck_t ctx)
return;
}
pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
- _("regular file inode map"), &ctx->inode_reg_map);
+ EXT2_INODE_REG_MAP, &ctx->inode_reg_map);
if (pctx.errcode) {
pctx.num = 6;
fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
ctx->flags |= E2F_FLAG_ABORT;
return;
}
- pctx.errcode = ext2fs_allocate_block_bitmap(fs, _("in-use block map"),
+ pctx.errcode = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_FOUND_MAP,
&ctx->block_found_map);
if (pctx.errcode) {
pctx.num = 1;
@@ -1271,7 +1271,7 @@ static void mark_inode_bad(e2fsck_t ctx, ino_t ino)
clear_problem_context(&pctx);
pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
- _("bad inode map"), &ctx->inode_bad_map);
+ EXT2_INODE_BAD_MAP, &ctx->inode_bad_map);
if (pctx.errcode) {
pctx.num = 3;
fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
@@ -1293,7 +1293,7 @@ static void alloc_bb_map(e2fsck_t ctx)
clear_problem_context(&pctx);
pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
- _("inode in bad block map"),
+ EXT2_INODE_BB_MAP,
&ctx->inode_bb_map);
if (pctx.errcode) {
pctx.num = 4;
@@ -1313,7 +1313,7 @@ static void alloc_imagic_map(e2fsck_t ctx)
clear_problem_context(&pctx);
pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
- _("imagic inode map"),
+ EXT2_INODE_IMAGIC_MAP,
&ctx->inode_imagic_map);
if (pctx.errcode) {
pctx.num = 5;
@@ -1340,7 +1340,7 @@ static _INLINE_ void mark_block_used(e2fsck_t ctx, blk64_t block)
if (ext2fs_fast_test_block_bitmap2(ctx->block_found_map, block)) {
if (!ctx->block_dup_map) {
pctx.errcode = ext2fs_allocate_block_bitmap(ctx->fs,
- _("multiply claimed block map"),
+ EXT2_BLOCK_DUP_MAP,
&ctx->block_dup_map);
if (pctx.errcode) {
pctx.num = 3;
@@ -1440,7 +1440,7 @@ static int check_ext_attr(e2fsck_t ctx, struct problem_context *pctx,
/* If ea bitmap hasn't been allocated, create it */
if (!ctx->block_ea_map) {
pctx->errcode = ext2fs_allocate_block_bitmap(fs,
- _("ext attr block map"),
+ EXT2_BLOCK_EA_MAP,
&ctx->block_ea_map);
if (pctx->errcode) {
pctx->num = 2;
diff --git a/e2fsck/pass1b.c b/e2fsck/pass1b.c
index 155fcba..95c7bea 100644
--- a/e2fsck/pass1b.c
+++ b/e2fsck/pass1b.c
@@ -217,7 +217,7 @@ void e2fsck_pass1_dupblocks(e2fsck_t ctx, char *block_buf)
clear_problem_context(&pctx);
pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
- _("multiply claimed inode map"), &inode_dup_map);
+ EXT2_INODE_DUP_MAP, &inode_dup_map);
if (pctx.errcode) {
fix_problem(ctx, PR_1B_ALLOCATE_IBITMAP_ERROR, &pctx);
ctx->flags |= E2F_FLAG_ABORT;
diff --git a/e2fsck/pass3.c b/e2fsck/pass3.c
index c067164..0ac7282 100644
--- a/e2fsck/pass3.c
+++ b/e2fsck/pass3.c
@@ -73,7 +73,7 @@ void e2fsck_pass3(e2fsck_t ctx)
/*
* Allocate some bitmaps to do loop detection.
*/
- pctx.errcode = ext2fs_allocate_inode_bitmap(fs, _("inode done bitmap"),
+ pctx.errcode = ext2fs_allocate_inode_bitmap(fs, EXT2_INODE_DONE_MAP,
&inode_done_map);
if (pctx.errcode) {
pctx.num = 2;
@@ -317,7 +317,9 @@ static int check_directory(e2fsck_t ctx, ext2_ino_t dir,
if (inode_loop_detect)
ext2fs_clear_inode_bitmap(inode_loop_detect);
else {
- pctx->errcode = ext2fs_allocate_inode_bitmap(fs, _("inode loop detection bitmap"), &inode_loop_detect);
+ pctx->errcode = ext2fs_allocate_inode_bitmap(fs,
+ EXT2_INODE_LOOP_MAP,
+ &inode_loop_detect);
if (pctx->errcode) {
pctx->num = 1;
fix_problem(ctx,
diff --git a/e2fsck/pass5.c b/e2fsck/pass5.c
index b423d28..8a9df37 100644
--- a/e2fsck/pass5.c
+++ b/e2fsck/pass5.c
@@ -272,7 +272,7 @@ redo_counts:
else
bitmap = ext2fs_fast_test_block_bitmap2(fs->block_map, i);
- if (actual == bitmap)
+ if ((actual && bitmap) || (!actual && !bitmap))
goto do_counts;
if (!actual && bitmap) {
@@ -504,7 +504,7 @@ redo_counts:
bitmap = actual;
else if (!skip_group)
bitmap = ext2fs_fast_test_inode_bitmap2(fs->inode_map, i);
- if (actual == bitmap)
+ if ((actual && bitmap) || (!actual && !bitmap))
goto do_counts;
if (!actual && bitmap) {
diff --git a/e2fsck/unix.c b/e2fsck/unix.c
index 73cc2cf..f883a6a 100644
--- a/e2fsck/unix.c
+++ b/e2fsck/unix.c
@@ -860,6 +860,13 @@ static errcode_t PRS(int argc, char *argv[], e2fsck_t *ret_ctx)
profile_set_syntax_err_cb(syntax_err_report);
profile_init(config_fn, &ctx->profile);
+ retval = ext2fs_prepare_bmap_definitions(ctx->profile);
+ if (retval) {
+ com_err("ext2fs_prepare_bmap_definitions", retval,
+ _("while setting bitmaps"));
+ fatal_error(ctx, 0);
+ }
+
if (flush) {
fd = open(ctx->filesystem_name, O_RDONLY, 0);
if (fd < 0) {
diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 29d1994..cd6c470 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -82,7 +82,8 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \
unlink.o \
valid_blk.o \
version.o \
- rbtree.o
+ rbtree.o \
+ profile.o
SRCS= ext2_err.c \
$(srcdir)/alloc.c \
@@ -160,6 +161,8 @@ SRCS= ext2_err.c \
$(srcdir)/version.c \
$(srcdir)/write_bb_file.c \
$(srcdir)/rbtree.c \
+ $(top_srcdir)/e2fsck/profile.c
+
HFILES= bitops.h ext2fs.h ext2_io.h ext2_fs.h ext2_ext_attr.h ext3_extents.h \
tdb.h
@@ -200,6 +203,15 @@ COMPILE_ET=../et/compile_et --build-tree
DISTFILES= Makefile *.c *.h image
+profile.o:
+ $(E) " CC $<"
+ $(Q) $(COMPILE_ET) $(top_srcdir)/e2fsck/prof_err.et
+ $(Q) $(CP) -f $(srcdir)/prof_err.h $(top_srcdir)/e2fsck/
+ $(Q) $(CC) -c $(ALL_CFLAGS) $(top_srcdir)/e2fsck/profile.c -o $@
+@PROFILE_CMT@ $(Q) $(CC) $(ALL_CFLAGS) -g -pg -o profiled/profile.o -c \
+@PROFILE_CMT@ $(top_srcdir)/e2fsck/profile.c
+
+
ext2_err.et: $(DEP_SUBSTITUTE) $(srcdir)/ext2_err.et.in
$(E) " SUBST $@"
$(Q) $(SUBSTITUTE) $(srcdir)/ext2_err.et.in ext2_err.et
@@ -387,7 +399,8 @@ clean::
mostlyclean:: clean
distclean:: clean
$(RM) -f .depend ext2_err.c ext2_err.h Makefile ext2fs.pc \
- $(srcdir)/TAGS $(srcdir)/Makefile.in.old
+ $(srcdir)/TAGS $(srcdir)/Makefile.in.old \
+ $(srcdir)/prof_err.h
#
# Hack to parallel makes recognize dependencies correctly.
#
diff --git a/lib/ext2fs/bitmaps.c b/lib/ext2fs/bitmaps.c
index c53d61e..4063f47 100644
--- a/lib/ext2fs/bitmaps.c
+++ b/lib/ext2fs/bitmaps.c
@@ -48,13 +48,15 @@ void ext2fs_set_bitmap_padding(ext2fs_generic_bitmap map)
ext2fs_set_generic_bmap_padding(map);
}
-errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs,
- const char *descr,
+errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs, int type,
ext2fs_inode_bitmap *ret)
{
__u64 start, end, real_end;
+ int backend;
EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
+ if (type >= EXT2_BMAP_COUNT || type < 0)
+ return EINVAL;
fs->write_bitmaps = ext2fs_write_bitmaps;
@@ -66,8 +68,7 @@ errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs,
if (fs->flags & EXT2_FLAG_64BITS)
return (ext2fs_alloc_generic_bmap(fs,
EXT2_ET_MAGIC_INODE_BITMAP64,
- EXT2FS_BMAP64_BITARRAY,
- start, end, real_end, descr, ret));
+ type, start, end, real_end, ret));
/* Otherwise, check to see if the file system is small enough
* to use old-style 32-bit bitmaps */
@@ -76,17 +77,20 @@ errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs,
return (ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_INODE_BITMAP, fs,
start, end, real_end,
- descr, 0,
+ NULL, 0,
(ext2fs_generic_bitmap *) ret));
}
errcode_t ext2fs_allocate_block_bitmap(ext2_filsys fs,
- const char *descr,
+ int type,
ext2fs_block_bitmap *ret)
{
__u64 start, end, real_end;
+ int backend;
EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
+ if (type >= EXT2_BMAP_COUNT || type < 0)
+ return EINVAL;
fs->write_bitmaps = ext2fs_write_bitmaps;
@@ -98,15 +102,14 @@ errcode_t ext2fs_allocate_block_bitmap(ext2_filsys fs,
if (fs->flags & EXT2_FLAG_64BITS)
return (ext2fs_alloc_generic_bmap(fs,
EXT2_ET_MAGIC_BLOCK_BITMAP64,
- EXT2FS_BMAP64_BITARRAY,
- start, end, real_end, descr, ret));
+ type, start, end, real_end, ret));
if ((end > ~0U) || (real_end > ~0U))
return EXT2_ET_CANT_USE_LEGACY_BITMAPS;
return (ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_BLOCK_BITMAP, fs,
start, end, real_end,
- descr, 0,
+ NULL, 0,
(ext2fs_generic_bitmap *) ret));
}
diff --git a/lib/ext2fs/check_desc.c b/lib/ext2fs/check_desc.c
index 7929cd9..85b6adb 100644
--- a/lib/ext2fs/check_desc.c
+++ b/lib/ext2fs/check_desc.c
@@ -41,7 +41,7 @@ errcode_t ext2fs_check_desc(ext2_filsys fs)
EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
- retval = ext2fs_allocate_block_bitmap(fs, "check_desc map", &bmap);
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_CHECK_DESC_MAP, &bmap);
if (retval)
return retval;
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index a204eb7..8621bf6 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -562,6 +562,37 @@ typedef struct ext2_icount *ext2_icount_t;
#define EXT2_LIB_SOFTSUPP_INCOMPAT (0)
#define EXT2_LIB_SOFTSUPP_RO_COMPAT (0)
+
+enum ext2_bitmap_type {
+ EXT2_GENERIC_MAP =0,
+ EXT2_INODE_USED_MAP, /* Inodes which are in use */
+ EXT2_INODE_BAD_MAP, /* Inodes which are bad somehow */
+ EXT2_INODE_DIR_MAP, /* Inodes which are directories */
+ EXT2_INODE_BB_MAP, /* Inodes which are in bad blocks */
+ EXT2_INODE_IMAGIC_MAP, /* AFS inodes */
+ EXT2_INODE_REG_MAP, /* Inodes which are regular files*/
+ EXT2_INODE_MAP,
+ EXT2_INODE_DUP_MAP,
+ EXT2_INODE_DONE_MAP,
+ EXT2_INODE_LOOP_MAP,
+
+ EXT2_BLOCK_FOUND_MAP, /* Blocks which are in use */
+ EXT2_BLOCK_DUP_MAP, /* Blks referenced more than once */
+ EXT2_BLOCK_EA_MAP, /* Blocks which are used by EA's */
+ EXT2_BLOCK_MAP,
+ EXT2_BLOCK_BAD_MAP,
+ EXT2_BLOCK_SCRAMBLE,
+ EXT2_BLOCK_TO_MOVE,
+ EXT2_BLOCK_RESERVED,
+ EXT2_BLOCK_METADATA,
+
+ EXT2_EMPTY_DIR_BLOCKS,
+ EXT2_EMPTY_DIR_MAP,
+ EXT2_CHECK_DESC_MAP,
+ EXT2_TOUCHED_MAP,
+ EXT2_BMAP_COUNT, /* Stop mark */
+};
+
/*
* function prototypes
*/
@@ -673,10 +704,10 @@ extern errcode_t ext2fs_write_block_bitmap (ext2_filsys fs);
extern errcode_t ext2fs_read_inode_bitmap (ext2_filsys fs);
extern errcode_t ext2fs_read_block_bitmap(ext2_filsys fs);
extern errcode_t ext2fs_allocate_block_bitmap(ext2_filsys fs,
- const char *descr,
+ int type,
ext2fs_block_bitmap *ret);
extern errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs,
- const char *descr,
+ int type,
ext2fs_inode_bitmap *ret);
extern errcode_t ext2fs_fudge_inode_bitmap_end(ext2fs_inode_bitmap bitmap,
ext2_ino_t end, ext2_ino_t *oend);
@@ -1086,7 +1117,6 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap);
errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
int type, __u64 start, __u64 end,
__u64 real_end,
- const char *descr,
ext2fs_generic_bitmap *ret);
errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
ext2fs_generic_bitmap *dest);
diff --git a/lib/ext2fs/ext2fsP.h b/lib/ext2fs/ext2fsP.h
index aa45c43..0a620d4 100644
--- a/lib/ext2fs/ext2fsP.h
+++ b/lib/ext2fs/ext2fsP.h
@@ -107,13 +107,15 @@ extern void ext2fs_numeric_progress_close(ext2_filsys fs,
* 64-bit bitmap support
*/
-#define EXT2FS_BMAP64_BITARRAY 1
-#define EXT2FS_BMAP64_RBTREE 2
+enum ext2fs_bmap_backends {
+ EXT2FS_BMAP64_BITARRAY = 0,
+ EXT2FS_BMAP64_RBTREE,
+ EXT2FS_BMAP64_COUNT,
+};
extern errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
int type, __u64 start, __u64 end,
__u64 real_end,
- const char * description,
ext2fs_generic_bitmap *bmap);
extern void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap);
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index 84065ea..4c69244 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -28,6 +28,7 @@
#include "ext2_fs.h"
#include "ext2fsP.h"
#include "bmap64.h"
+#include "profile.h"
/*
* Design of 64-bit bitmaps
@@ -77,17 +78,128 @@ static void warn_bitmap(ext2fs_generic_bitmap bitmap,
}
+#define EXT2_DEFAULT_BITMAP_BACKEND EXT2FS_BMAP64_BITARRAY
+
+static char *ext2_bmap_profile_value[EXT2_BMAP_COUNT] = {
+ [EXT2_GENERIC_MAP] = "generic_bitmap",
+ [EXT2_INODE_USED_MAP] = "inode_used_map",
+ [EXT2_INODE_BAD_MAP] = "inode_bad_map",
+ [EXT2_INODE_DIR_MAP] = "inode_dir_map",
+ [EXT2_INODE_BB_MAP] = "inode_bb_map",
+ [EXT2_INODE_IMAGIC_MAP] = "inode_imagic_map",
+ [EXT2_INODE_REG_MAP] = "inode_reg_map",
+ [EXT2_INODE_MAP] = "inode_bitmap",
+ [EXT2_INODE_DUP_MAP] = "inode_dup_map",
+ [EXT2_INODE_DONE_MAP] = "inode_done_map",
+ [EXT2_INODE_LOOP_MAP] = "inode_loop_map",
+
+ [EXT2_BLOCK_FOUND_MAP] = "block_found_map",
+ [EXT2_BLOCK_DUP_MAP] = "block_dup_map",
+ [EXT2_BLOCK_EA_MAP] = "block_ea_map",
+ [EXT2_BLOCK_MAP] = "block_bitmap",
+ [EXT2_BLOCK_BAD_MAP] = "bad_block_map",
+ [EXT2_BLOCK_SCRAMBLE] = "block_scramble_map",
+ [EXT2_BLOCK_TO_MOVE] = "block_to_move",
+ [EXT2_BLOCK_RESERVED] = "block_reserved",
+ [EXT2_BLOCK_METADATA] = "block_meta_data",
+
+ [EXT2_EMPTY_DIR_BLOCKS] = "empty_dir_blocks",
+ [EXT2_EMPTY_DIR_MAP] = "empty_dir_map",
+ [EXT2_CHECK_DESC_MAP] = "check_desc_map",
+ [EXT2_TOUCHED_MAP] = "touched_map",
+};
+
+struct ext2_bmap_definition {
+ int backend;
+ char *descr;
+};
+
+const
+static struct ext2_bmap_definition ext2_bmap_default[EXT2_BMAP_COUNT] = {
+ [EXT2_GENERIC_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "generic bitmap"},
+ [EXT2_INODE_USED_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "in-use inode map"},
+ [EXT2_INODE_BAD_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "bad inode map"},
+ [EXT2_INODE_DIR_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "directory inode map"},
+ [EXT2_INODE_BB_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "inode in bad block map"},
+ [EXT2_INODE_IMAGIC_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "imagic inode map"},
+ [EXT2_INODE_REG_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "regular file inode map"},
+ [EXT2_INODE_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "inode bitmap"},
+ [EXT2_INODE_DUP_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "multiply claimed inode map"},
+ [EXT2_INODE_DONE_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "inode done bitmap"},
+ [EXT2_INODE_LOOP_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "inode loop detection bitmap"},
+
+ [EXT2_BLOCK_FOUND_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "in-use block map"},
+ [EXT2_BLOCK_DUP_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND,"multiply claimed block map"},
+ [EXT2_BLOCK_EA_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "ext attr block map"},
+ [EXT2_BLOCK_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "block bitmap"},
+ [EXT2_BLOCK_BAD_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "bad block map"},
+ [EXT2_BLOCK_SCRAMBLE] = {EXT2_DEFAULT_BITMAP_BACKEND, "scrambled block map"},
+ [EXT2_BLOCK_TO_MOVE] = {EXT2_DEFAULT_BITMAP_BACKEND, "blocks to be moved"},
+ [EXT2_BLOCK_RESERVED] = {EXT2_DEFAULT_BITMAP_BACKEND, "reserved blocks"},
+ [EXT2_BLOCK_METADATA] = {EXT2_DEFAULT_BITMAP_BACKEND, "meta-data blocks"},
+
+ [EXT2_EMPTY_DIR_BLOCKS] = {EXT2_DEFAULT_BITMAP_BACKEND, "empty dir blocks"},
+ [EXT2_EMPTY_DIR_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "empty dir map"},
+ [EXT2_CHECK_DESC_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "check desc map"},
+ [EXT2_TOUCHED_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "touched map"},
+};
+
+static struct ext2_bmap_definition *bmap_defs = NULL;
+
+errcode_t ext2fs_prepare_bmap_definitions(profile_t profile)
+{
+ char *cp;
+ errcode_t retval = 0;
+ int i, backend;
+
+ if (!bmap_defs)
+ retval = ext2fs_get_mem(EXT2_BMAP_COUNT *
+ sizeof(struct ext2_bmap_definition),
+ &bmap_defs);
+ if (retval)
+ return retval;
+
+ for (i = 0; i < EXT2_BMAP_COUNT; i++) {
+ retval = profile_get_integer(profile, "bitmaps",
+ ext2_bmap_profile_value[i],
+ NULL, ext2_bmap_default[i].backend,
+ &backend);
+ if (retval)
+ goto out;
+
+ if (backend >= EXT2FS_BMAP64_COUNT ||
+ backend < 0)
+ backend = ext2_bmap_default[i].backend;
+
+ bmap_defs[i].backend = backend;
+ bmap_defs[i].descr = ext2_bmap_default[i].descr;
+ }
+
+ if (retval)
+ ext2fs_free_mem(bmap_defs);
+
+out:
+ return retval;
+}
+
errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
int type, __u64 start, __u64 end,
__u64 real_end,
- const char *descr,
ext2fs_generic_bitmap *ret)
{
ext2fs_generic_bitmap bitmap;
struct ext2_bitmap_ops *ops;
errcode_t retval;
+ char *descr = NULL;
+ int backend;
+
+ if (!bmap_defs)
+ ext2fs_prepare_bmap_definitions(NULL);
+
+ descr = bmap_defs[type].descr;
+ backend = bmap_defs[type].backend;
- switch (type) {
+ switch (backend) {
case EXT2FS_BMAP64_BITARRAY:
ops = &ext2fs_blkmap64_bitarray;
break;
@@ -102,6 +214,7 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
&bitmap);
if (retval)
return retval;
+ memset(bitmap, 0, sizeof(struct ext2fs_struct_generic_bitmap));
/* XXX factor out, repeated in copy_bmap */
bitmap->magic = magic;
@@ -185,6 +298,7 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
&new_bmap);
if (retval)
return retval;
+ memset(new_bmap, 0, sizeof(struct ext2fs_struct_generic_bitmap));
/* Copy all the high-level parts over */
new_bmap->magic = src->magic;
diff --git a/lib/ext2fs/icount.c b/lib/ext2fs/icount.c
index 43cc53e..f6b1646 100644
--- a/lib/ext2fs/icount.c
+++ b/lib/ext2fs/icount.c
@@ -103,12 +103,13 @@ static errcode_t alloc_icount(ext2_filsys fs, int flags, ext2_icount_t *ret)
return retval;
memset(icount, 0, sizeof(struct ext2_icount));
- retval = ext2fs_allocate_inode_bitmap(fs, 0, &icount->single);
+ retval = ext2fs_allocate_inode_bitmap(fs, EXT2_GENERIC_MAP,
+ &icount->single);
if (retval)
goto errout;
if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
- retval = ext2fs_allocate_inode_bitmap(fs, 0,
+ retval = ext2fs_allocate_inode_bitmap(fs, EXT2_GENERIC_MAP,
&icount->multiple);
if (retval)
goto errout;
diff --git a/lib/ext2fs/initialize.c b/lib/ext2fs/initialize.c
index 4cf0863..dd1df1d 100644
--- a/lib/ext2fs/initialize.c
+++ b/lib/ext2fs/initialize.c
@@ -96,7 +96,6 @@ errcode_t ext2fs_initialize(const char *name, int flags,
int rsv_gdt;
int csum_flag;
int io_flags;
- char *buf = 0;
char c;
if (!param || !ext2fs_blocks_count(param))
@@ -359,24 +358,16 @@ ipg_retry:
* count.
*/
- retval = ext2fs_get_mem(strlen(fs->device_name) + 80, &buf);
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_MAP,
+ &fs->block_map);
if (retval)
goto cleanup;
- strcpy(buf, "block bitmap for ");
- strcat(buf, fs->device_name);
- retval = ext2fs_allocate_block_bitmap(fs, buf, &fs->block_map);
+ retval = ext2fs_allocate_inode_bitmap(fs, EXT2_INODE_MAP,
+ &fs->inode_map);
if (retval)
goto cleanup;
- strcpy(buf, "inode bitmap for ");
- strcat(buf, fs->device_name);
- retval = ext2fs_allocate_inode_bitmap(fs, buf, &fs->inode_map);
- if (retval)
- goto cleanup;
-
- ext2fs_free_mem(&buf);
-
retval = ext2fs_get_array(fs->desc_blocks, fs->blocksize,
&fs->group_desc);
if (retval)
@@ -442,7 +433,6 @@ ipg_retry:
*ret_fs = fs;
return 0;
cleanup:
- free(buf);
ext2fs_free(fs);
return retval;
}
diff --git a/lib/ext2fs/rw_bitmaps.c b/lib/ext2fs/rw_bitmaps.c
index 3031b7d..83feb87 100644
--- a/lib/ext2fs/rw_bitmaps.c
+++ b/lib/ext2fs/rw_bitmaps.c
@@ -139,7 +139,6 @@ static errcode_t read_bitmaps(ext2_filsys fs, int do_inode, int do_block)
{
dgrp_t i;
char *block_bitmap = 0, *inode_bitmap = 0;
- char *buf;
errcode_t retval;
int block_nbytes = EXT2_BLOCKS_PER_GROUP(fs->super) / 8;
int inode_nbytes = EXT2_INODES_PER_GROUP(fs->super) / 8;
@@ -160,15 +159,11 @@ static errcode_t read_bitmaps(ext2_filsys fs, int do_inode, int do_block)
EXT4_FEATURE_RO_COMPAT_GDT_CSUM))
csum_flag = 1;
- retval = ext2fs_get_mem(strlen(fs->device_name) + 80, &buf);
- if (retval)
- return retval;
if (do_block) {
if (fs->block_map)
ext2fs_free_block_bitmap(fs->block_map);
- strcpy(buf, "block bitmap for ");
- strcat(buf, fs->device_name);
- retval = ext2fs_allocate_block_bitmap(fs, buf, &fs->block_map);
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_MAP,
+ &fs->block_map);
if (retval)
goto cleanup;
if (do_image)
@@ -185,9 +180,8 @@ static errcode_t read_bitmaps(ext2_filsys fs, int do_inode, int do_block)
if (do_inode) {
if (fs->inode_map)
ext2fs_free_inode_bitmap(fs->inode_map);
- strcpy(buf, "inode bitmap for ");
- strcat(buf, fs->device_name);
- retval = ext2fs_allocate_inode_bitmap(fs, buf, &fs->inode_map);
+ retval = ext2fs_allocate_inode_bitmap(fs, EXT2_INODE_MAP,
+ &fs->inode_map);
if (retval)
goto cleanup;
retval = ext2fs_get_mem(do_image ? fs->blocksize :
@@ -196,7 +190,6 @@ static errcode_t read_bitmaps(ext2_filsys fs, int do_inode, int do_block)
goto cleanup;
} else
inode_nbytes = 0;
- ext2fs_free_mem(&buf);
if (fs->flags & EXT2_FLAG_IMAGE_FILE) {
blk = (fs->image_header->offset_inodemap / fs->blocksize);
@@ -306,8 +299,6 @@ cleanup:
ext2fs_free_mem(&inode_bitmap);
if (block_bitmap)
ext2fs_free_mem(&block_bitmap);
- if (buf)
- ext2fs_free_mem(&buf);
return retval;
}
diff --git a/lib/ext2fs/tst_iscan.c b/lib/ext2fs/tst_iscan.c
index 64246d3..7795497 100644
--- a/lib/ext2fs/tst_iscan.c
+++ b/lib/ext2fs/tst_iscan.c
@@ -95,21 +95,21 @@ static void setup(void)
"While allocating tables for test filesystem");
exit(1);
}
- retval = ext2fs_allocate_block_bitmap(test_fs, "bad block map",
+ retval = ext2fs_allocate_block_bitmap(test_fs, EXT2_BLOCK_BAD_MAP,
&bad_block_map);
if (retval) {
com_err("setup", retval,
"While allocating bad_block bitmap");
exit(1);
}
- retval = ext2fs_allocate_block_bitmap(test_fs, "touched map",
+ retval = ext2fs_allocate_block_bitmap(test_fs, EXT2_TOUCHED_MAP,
&touched_map);
if (retval) {
com_err("setup", retval,
"While allocating touched block bitmap");
exit(1);
}
- retval = ext2fs_allocate_inode_bitmap(test_fs, "bad inode map",
+ retval = ext2fs_allocate_inode_bitmap(test_fs, EXT2_INODE_BAD_MAP,
&bad_inode_map);
if (retval) {
com_err("setup", retval,
diff --git a/misc/e2image.c b/misc/e2image.c
index 003ac5a..0e4b2a5 100644
--- a/misc/e2image.c
+++ b/misc/e2image.c
@@ -465,7 +465,7 @@ static void write_raw_image_file(ext2_filsys fs, int fd, int scramble_flag)
errcode_t retval;
char * block_buf;
- retval = ext2fs_allocate_block_bitmap(fs, "in-use block map",
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_FOUND_MAP,
&meta_block_map);
if (retval) {
com_err(program_name, retval, "while allocating block bitmap");
@@ -473,7 +473,7 @@ static void write_raw_image_file(ext2_filsys fs, int fd, int scramble_flag)
}
if (scramble_flag) {
- retval = ext2fs_allocate_block_bitmap(fs, "scramble block map",
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_SCRAMBLE,
&scramble_block_map);
if (retval) {
com_err(program_name, retval,
diff --git a/misc/tune2fs.c b/misc/tune2fs.c
index bcada11..a2a980a 100644
--- a/misc/tune2fs.c
+++ b/misc/tune2fs.c
@@ -1472,7 +1472,7 @@ static int resize_inode(ext2_filsys fs, unsigned long new_size)
*/
fs->super->s_state &= ~EXT2_VALID_FS;
- retval = ext2fs_allocate_block_bitmap(fs, _("blocks to be moved"),
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_TO_MOVE,
&bmap);
if (retval) {
fputs(_("Failed to allocate block bitmap when "
diff --git a/resize/resize2fs.c b/resize/resize2fs.c
index 216a626..26ebb30 100644
--- a/resize/resize2fs.c
+++ b/resize/resize2fs.c
@@ -580,7 +580,7 @@ static errcode_t adjust_superblock(ext2_resize_t rfs, blk64_t new_size)
ext2fs_mark_bb_dirty(fs);
ext2fs_mark_ib_dirty(fs);
- retval = ext2fs_allocate_block_bitmap(fs, _("reserved blocks"),
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_RESERVED,
&rfs->reserve_blocks);
if (retval)
return retval;
@@ -788,12 +788,12 @@ static errcode_t blocks_to_move(ext2_resize_t rfs)
if (ext2fs_blocks_count(old_fs->super) > ext2fs_blocks_count(fs->super))
fs = rfs->old_fs;
- retval = ext2fs_allocate_block_bitmap(fs, _("blocks to be moved"),
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_TO_MOVE,
&rfs->move_blocks);
if (retval)
return retval;
- retval = ext2fs_allocate_block_bitmap(fs, _("meta-data blocks"),
+ retval = ext2fs_allocate_block_bitmap(fs, EXT2_BLOCK_METADATA,
&meta_bmap);
if (retval)
return retval;
--
1.7.4
^ permalink raw reply related [flat|nested] 13+ messages in thread
* [PATCH 4/4] Add macro to enable collecting bitmap statistics
2011-03-17 18:50 Add rbtree backend for storing bitmaps Lukas Czerner
` (2 preceding siblings ...)
2011-03-17 18:50 ` [PATCH 3/4] Add bitmap configuration interface Lukas Czerner
@ 2011-03-17 18:50 ` Lukas Czerner
2011-03-17 21:19 ` Andreas Dilger
3 siblings, 1 reply; 13+ messages in thread
From: Lukas Czerner @ 2011-03-17 18:50 UTC (permalink / raw)
To: linux-ext4; +Cc: tytso, sandeen, Lukas Czerner
This commit adds a new preprocessor macro BMAP_STATS, which can be
defined in ext2fs.h. Setting this macro, the code for statistic
collection of bitmap handling is enabled and once the bitmap shall be
freed collected information is printed to the stderr.
This feature is especially useful for better understanding how e2fsprogs
tools (mainly e2fsck) treats bitmaps and what bitmap backend can be most
suitable for particular bitmap. Backend itself (if implemented) can
provide statistics of its own as well.
I was thinking about enabling this feature simply by setting program
parameter, however collecting of the statistic, even conditional, means
unnecessary overhead. And since information provided is usually relevant
only for e2fsprogs developers, I decided to use preprocessor macro
instead.
Obviously this feature is off by default.
Signed-off-by: Lukas Czerner <lczerner@redhat.com>
---
lib/ext2fs/blkmap64_ba.c | 8 +++
lib/ext2fs/blkmap64_rb.c | 82 ++++++++++++++++++++++++++++-
lib/ext2fs/bmap64.h | 31 +++++++++++
lib/ext2fs/ext2fs.h | 4 ++
lib/ext2fs/gen_bitmap64.c | 126 ++++++++++++++++++++++++++++++++++++++++++++-
5 files changed, 248 insertions(+), 3 deletions(-)
diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 395aba9..72d775e 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -309,6 +309,13 @@ static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
(size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
}
+static void ba_print_stats(ext2fs_generic_bitmap bitmap)
+{
+ fprintf(stderr, "%16lu Bytes used by bitarray\n",
+ ((bitmap->real_end - bitmap->start) >> 3) + 1 +
+ sizeof(struct ext2fs_ba_private_struct));
+}
+
struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
.type = EXT2FS_BMAP64_BITARRAY,
.new_bmap = ba_new_bmap,
@@ -324,4 +331,5 @@ struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
.set_bmap_range = ba_set_bmap_range,
.get_bmap_range = ba_get_bmap_range,
.clear_bmap = ba_clear_bmap,
+ .print_stats = ba_print_stats,
};
diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 8f121b3..c9f77a6 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -40,6 +40,10 @@ struct ext2fs_rb_private {
struct rb_root root;
struct bmap_rb_extent **wcursor;
struct bmap_rb_extent **rcursor;
+#ifdef BMAP_STATS
+ __u64 mark_hit;
+ __u64 test_hit;
+#endif
};
static int rb_insert_extent(__u64 start, __u64 count,
@@ -168,6 +172,11 @@ static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
*bp->rcursor = NULL;
*bp->wcursor = NULL;
+#ifdef BMAP_STATS
+ bp->test_hit = 0;
+ bp->mark_hit = 0;
+#endif
+
bitmap->private = (void *) bp;
return 0;
}
@@ -313,8 +322,12 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
if (!rcursor)
goto search_tree;
- if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
+ if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) {
+#ifdef BMAP_STATS
+ bp->test_hit++;
+#endif
return 1;
+ }
rcursor = *bp->wcursor;
if (!rcursor)
@@ -353,8 +366,12 @@ static int rb_insert_extent(__u64 start, __u64 count,
ext = *bp->wcursor;
if (ext) {
if (start >= ext->start &&
- start <= (ext->start + ext->count))
+ start <= (ext->start + ext->count)) {
+#ifdef BMAP_STATS
+ bp->mark_hit++;
+#endif
goto got_extent;
+ }
}
while (*n) {
@@ -733,6 +750,66 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
*bp->wcursor = NULL;
}
+#ifdef BMAP_STATS
+static void rb_print_stats(ext2fs_generic_bitmap bitmap)
+{
+ struct ext2fs_rb_private *bp;
+ struct rb_node *node = NULL;
+ struct bmap_rb_extent *ext;
+ __u64 count = 0;
+ __u64 max_size = 0;
+ __u64 min_size = ULONG_MAX;
+ __u64 size = 0, avg_size = 0;
+ __u64 mark_all, test_all;
+ double eff, m_hit = 0.0, t_hit = 0.0;
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+
+ node = rb_first(&bp->root);
+ for (node = rb_first(&bp->root); node != NULL; node=rb_next(node)) {
+ ext = rb_entry(node, struct bmap_rb_extent, node);
+ count++;
+ if (ext->count > max_size)
+ max_size = ext->count;
+ if (ext->count < min_size)
+ min_size = ext->count;
+ size += ext->count;
+ }
+
+ if (count)
+ avg_size = size / count;
+ if (min_size == ULONG_MAX)
+ min_size = 0;
+ eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) /
+ (bitmap->real_end - bitmap->start);
+ mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count;
+ test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count;
+ if (mark_all)
+ m_hit = ((double)bp->mark_hit / mark_all) * 100;
+ if (test_all)
+ t_hit = ((double)bp->test_hit / test_all) * 100;
+
+ fprintf(stderr, "%16llu cache hits on test (%.2f%)\n"
+ "%16llu cache hits on mark (%.2f%)\n",
+ bp->test_hit, t_hit, bp->mark_hit, m_hit);
+ fprintf(stderr, "%16llu extents\n%16llu Bytes per extent\n",
+ count, sizeof(struct bmap_rb_extent));
+ fprintf(stderr, "%16llu Bytes used by rbtree\n"
+ "%16llu bits minimum size\n",
+ count * sizeof(struct bmap_rb_extent) +
+ sizeof(struct ext2fs_rb_private), min_size);
+ fprintf(stderr, "%16llu bits maximum size\n"
+ "%16llu bits average size\n",
+ max_size, avg_size);
+ fprintf(stderr, "%16llu bits mapped by extents\n", size);
+ fprintf(stderr, "%16llu bitmap size\n"
+ "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
+ bitmap->real_end - bitmap->start, eff);
+}
+#else
+static void rb_print_stats(ext2fs_generic_bitmap bitmap){}
+#endif
+
struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
.type = EXT2FS_BMAP64_RBTREE,
.new_bmap = rb_new_bmap,
@@ -748,4 +825,5 @@ struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
.set_bmap_range = rb_set_bmap_range,
.get_bmap_range = rb_get_bmap_range,
.clear_bmap = rb_clear_bmap,
+ .print_stats = rb_print_stats,
};
diff --git a/lib/ext2fs/bmap64.h b/lib/ext2fs/bmap64.h
index 31021b9..fdb5ace 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -9,6 +9,33 @@
* %End-Header%
*/
+struct ext2_bmap_statistics {
+ int type;
+ struct timeval created;
+ struct timeval destroyed;;
+
+ unsigned long copy_count;
+ unsigned long resize_count;
+ unsigned long mark_count;
+ unsigned long unmark_count;
+ unsigned long test_count;
+ unsigned long mark_ext_count;
+ unsigned long unmark_ext_count;
+ unsigned long test_ext_count;
+ unsigned long set_range_count;
+ unsigned long get_range_count;
+ unsigned long clear_count;
+
+ blk64_t last_marked;
+ blk64_t last_tested;
+ blk64_t mark_back;
+ blk64_t test_back;
+
+ unsigned long mark_seq;
+ unsigned long test_seq;
+};
+
+
struct ext2fs_struct_generic_bitmap {
errcode_t magic;
ext2_filsys fs;
@@ -19,6 +46,9 @@ struct ext2fs_struct_generic_bitmap {
char *description;
void *private;
errcode_t base_error_code;
+#ifdef BMAP_STATS
+ struct ext2_bmap_statistics stats;
+#endif
};
#define EXT2FS_IS_32_BITMAP(bmap) \
@@ -56,6 +86,7 @@ struct ext2_bitmap_ops {
errcode_t (*get_bmap_range)(ext2fs_generic_bitmap bitmap,
__u64 start, size_t num, void *out);
void (*clear_bmap)(ext2fs_generic_bitmap bitmap);
+ void (*print_stats)(ext2fs_generic_bitmap);
};
extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray;
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 8621bf6..eb35ad8 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1113,6 +1113,10 @@ extern errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
void *in);
/* gen_bitmap64.c */
+
+/* Generate and print bitmap usage statistics */
+/* #define BMAP_STATS */
+
void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap);
errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
int type, __u64 start, __u64 end,
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index 4c69244..e2d3a09 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -77,6 +77,12 @@ static void warn_bitmap(ext2fs_generic_bitmap bitmap,
#endif
}
+#ifdef BMAP_STATS
+#define INC_STAT(map, name) map->stats.name
+#else
+#define INC_STAT(map, name) ;;
+#endif
+
#define EXT2_DEFAULT_BITMAP_BACKEND EXT2FS_BMAP64_BITARRAY
@@ -216,6 +222,15 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
return retval;
memset(bitmap, 0, sizeof(struct ext2fs_struct_generic_bitmap));
+#ifdef BMAP_STATS
+ if (gettimeofday(&bitmap->stats.created,
+ (struct timezone *) NULL) == -1) {
+ perror("gettimeofday");
+ return 1;
+ }
+ bitmap->stats.type = type;
+#endif
+
/* XXX factor out, repeated in copy_bmap */
bitmap->magic = magic;
bitmap->fs = fs;
@@ -245,8 +260,8 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
if (retval) {
- ext2fs_free_mem(&bitmap);
ext2fs_free_mem(&bitmap->description);
+ ext2fs_free_mem(&bitmap);
return retval;
}
@@ -254,6 +269,62 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
return 0;
}
+#ifdef BMAP_STATS
+void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap bitmap)
+{
+ struct ext2_bmap_statistics *stats = &bitmap->stats;
+ float mark_seq_perc = 0.0, test_seq_perc = 0.0;
+ float mark_back_perc = 0.0, test_back_perc = 0.0;
+ double inuse;
+
+ if (stats->test_count) {
+ test_seq_perc = ((float)stats->test_seq /
+ stats->test_count) * 100;
+ test_back_perc = ((float)stats->test_back /
+ stats->test_count) * 100;
+ }
+
+ if (stats->mark_count) {
+ mark_seq_perc = ((float)stats->mark_seq /
+ stats->mark_count) * 100;
+ mark_back_perc = ((float)stats->mark_back /
+ stats->mark_count) * 100;
+ }
+
+ inuse = (double) stats->destroyed.tv_sec + \
+ (((double) stats->destroyed.tv_usec) * 0.000001);
+ inuse -= (double) stats->created.tv_sec + \
+ (((double) stats->created.tv_usec) * 0.000001);
+
+ fprintf(stderr, "\n[+] %s bitmap\n", bmap_defs[stats->type].descr);
+ fprintf(stderr, "=================================================\n");
+ fprintf(stderr, "%16d type\n%16d backend\n",
+ stats->type, bmap_defs[stats->type].backend);
+ fprintf(stderr, "%16d bits long\n",
+ bitmap->real_end - bitmap->start);
+ fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
+ stats->copy_count, stats->resize_count);
+ fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
+ stats->mark_count, stats->unmark_count);
+ fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
+ stats->test_count, stats->mark_ext_count);
+ fprintf(stderr, "%16lu unmark_bmap_extent\n"
+ "%16lu test_clear_bmap_extent\n",
+ stats->unmark_ext_count, stats->test_ext_count);
+ fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
+ stats->set_range_count, stats->get_range_count);
+ fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%)\n",
+ stats->clear_count, stats->test_seq, test_seq_perc);
+ fprintf(stderr, "%16lu contiguous bit mark (%.2f%)\n"
+ "%16lu bits tested backwards (%.2f%)\n",
+ stats->mark_seq, mark_seq_perc,
+ stats->test_back, test_back_perc);
+ fprintf(stderr, "%16lu bits marked backwards (%.2f%)\n"
+ "%16.2f seconds in use\n",
+ stats->mark_back, mark_back_perc, inuse);
+}
+#endif
+
void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
{
if (!bmap)
@@ -267,6 +338,16 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
if (!EXT2FS_IS_64_BITMAP(bmap))
return;
+#ifdef BMAP_STATS
+ if (gettimeofday(&bmap->stats.destroyed,
+ (struct timezone *) NULL) == -1) {
+ perror("gettimeofday");
+ return;
+ }
+ ext2fs_print_bmap_statistics(bmap);
+ bmap->bitmap_ops->print_stats(bmap);
+#endif
+
bmap->bitmap_ops->free_bmap(bmap);
if (bmap->description) {
@@ -300,6 +381,17 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
return retval;
memset(new_bmap, 0, sizeof(struct ext2fs_struct_generic_bitmap));
+
+#ifdef BMAP_STATS
+ src->stats.copy_count++;
+ if (gettimeofday(&new_bmap->stats.created,
+ (struct timezone *) NULL) == -1) {
+ perror("gettimeofday");
+ return 1;
+ }
+ new_bmap->stats.type = src->stats.type;
+#endif
+
/* Copy all the high-level parts over */
new_bmap->magic = src->magic;
new_bmap->fs = src->fs;
@@ -346,6 +438,8 @@ errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
if (!EXT2FS_IS_64_BITMAP(bmap))
return EINVAL;
+ INC_STAT(bmap, resize_count);
+
return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
}
@@ -432,6 +526,15 @@ int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
if (!EXT2FS_IS_64_BITMAP(bitmap))
return 0;
+#ifdef BMAP_STATS
+ if (arg == bitmap->stats.last_marked + 1)
+ bitmap->stats.mark_seq++;
+ if (arg < bitmap->stats.last_marked)
+ bitmap->stats.mark_back++;
+ bitmap->stats.last_marked = arg;
+ bitmap->stats.mark_count++;
+#endif
+
if ((arg < bitmap->start) || (arg > bitmap->end)) {
warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
return 0;
@@ -458,6 +561,8 @@ int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
if (!EXT2FS_IS_64_BITMAP(bitmap))
return 0;
+ INC_STAT(bitmap, unmark_count);
+
if ((arg < bitmap->start) || (arg > bitmap->end)) {
warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
return 0;
@@ -484,6 +589,15 @@ int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
if (!EXT2FS_IS_64_BITMAP(bitmap))
return 0;
+#ifdef BMAP_STATS
+ bitmap->stats.test_count++;
+ if (arg == bitmap->stats.last_tested + 1)
+ bitmap->stats.test_seq++;
+ if (arg < bitmap->stats.last_tested)
+ bitmap->stats.test_back++;
+ bitmap->stats.last_tested = arg;
+#endif
+
if ((arg < bitmap->start) || (arg > bitmap->end)) {
warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
return 0;
@@ -512,6 +626,8 @@ errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
if (!EXT2FS_IS_64_BITMAP(bmap))
return EINVAL;
+ INC_STAT(bmap, set_range_count);
+
return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
}
@@ -535,6 +651,8 @@ errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
if (!EXT2FS_IS_64_BITMAP(bmap))
return EINVAL;
+ INC_STAT(bmap, get_range_count);
+
return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
}
@@ -606,6 +724,8 @@ int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
if (!EXT2FS_IS_64_BITMAP(bmap))
return EINVAL;
+ INC_STAT(bmap, test_ext_count);
+
return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
}
@@ -628,6 +748,8 @@ void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
if (!EXT2FS_IS_64_BITMAP(bmap))
return;
+ INC_STAT(bmap, mark_ext_count);
+
if ((block < bmap->start) || (block+num-1 > bmap->end)) {
ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
bmap->description);
@@ -656,6 +778,8 @@ void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
if (!EXT2FS_IS_64_BITMAP(bmap))
return;
+ INC_STAT(bmap, unmark_ext_count);
+
if ((block < bmap->start) || (block+num-1 > bmap->end)) {
ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
bmap->description);
--
1.7.4
^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH 1/4 v2] e2fsprogs: Add rbtree library
2011-03-17 18:50 ` [PATCH 1/4 v2] e2fsprogs: Add rbtree library Lukas Czerner
@ 2011-03-17 19:34 ` Andreas Dilger
2011-03-18 9:46 ` Lukas Czerner
0 siblings, 1 reply; 13+ messages in thread
From: Andreas Dilger @ 2011-03-17 19:34 UTC (permalink / raw)
To: Lukas Czerner; +Cc: linux-ext4, tytso, sandeen
On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> +#undef offsetof
> +#ifdef __compiler_offsetof
> +#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
> +#else
> +#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
> +#endif
This may as well go into a more common header like lib/ext2fs/ext2fs.h, since I see offsetof() is #defined 5 separate times in the e2fsprogs code already.
> +#define container_of(ptr, type, member) ({ \
> + const typeof( ((type *)0)->member ) *__mptr = (ptr); \
> + (type *)( (char *)__mptr - offsetof(type,member) );})
Same.
> +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
> +#define rb_color(r) ((r)->rb_parent_color & 1)
> +#define rb_is_red(r) (!rb_color(r))
> +#define rb_is_black(r) rb_color(r)
> +#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
> +#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
> +
> +#define RB_ROOT (struct rb_root) { NULL, }
> +#define rb_entry(ptr, type, member) container_of(ptr, type, member)
The indenting here is a bit broken, but I see it is the same in the upstream kernel code, so it probably shouldn't be changed just for e2fsprogs.
Cheers, Andreas
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays
2011-03-17 18:50 ` [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays Lukas Czerner
@ 2011-03-17 19:56 ` Andreas Dilger
2011-03-18 9:55 ` Lukas Czerner
0 siblings, 1 reply; 13+ messages in thread
From: Andreas Dilger @ 2011-03-17 19:56 UTC (permalink / raw)
To: Lukas Czerner; +Cc: linux-ext4, tytso, sandeen
On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> +++ b/lib/ext2fs/blkmap64_rb.c
> +struct bmap_rb_extent {
> + struct rb_node node;
> + __u64 start;
> + __u32 count;
> +};
On 32-bit machines (where memory consumption is even more critical) this will pack better by arranging it with "count" aligned with rb_parent_color:
struct bmap_rb_extent {
__u64 start;
__u32 count;
struct rb_node node;
};
That will give a leaf size of 24 bytes on a 32-bit arch, instead of 32 bytes with padding. On a 64-bit arch it won't make any difference.
> static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
> + __u64 new_end, __u64 new_real_end)
> +{
> + struct ext2fs_rb_private *bp;
> +
> + if (new_real_end >= bmap->real_end) {
> + bmap->end = new_end;
> + bmap->real_end = new_real_end;
> + return 0;
> + }
> +
> + bp = (struct ext2fs_rb_private *) bmap->private;
> + *bp->rcursor = NULL;
> + *bp->wcursor = NULL;
> +
> + /* truncate tree to new_real_end size */
> + rb_truncate(new_real_end, &bp->root);
> +
> + bmap->end = new_end;
> + bmap->real_end = new_real_end;
> + return 0;
> +
> +}
This might be a bit better written as:
static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
__u64 new_end, __u64 new_real_end)
{
struct ext2fs_rb_private *bp;
if (new_real_end < bmap->real_end) {
bp = (struct ext2fs_rb_private *)bmap->private;
*bp->rcursor = NULL;
*bp->wcursor = NULL;
/* truncate tree to new_real_end size */
rb_truncate(new_real_end, &bp->root);
}
bmap->end = new_end;
bmap->real_end = new_real_end;
return 0;
}
> +inline static int
> +rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
> +{
> + struct bmap_rb_extent *rcursor;
> + struct rb_node *parent = NULL;
> + struct rb_node **n = &bp->root.rb_node;
> + struct bmap_rb_extent *ext;
> + int i=0;
> +
> + rcursor = *bp->rcursor;
> + if (!rcursor)
> + goto search_tree;
> +
> + if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
> + return 1;
> +
> + rcursor = *bp->wcursor;
> + if (!rcursor)
> + goto search_tree;
> +
> + if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
> + return 1;
> +
> +search_tree:
> +
> + while (*n) {
> + parent = *n;
> + ext = rb_entry(parent, struct bmap_rb_extent, node);
> + if (bit < ext->start)
> + n = &(*n)->rb_left;
> + else if (bit >= (ext->start + ext->count))
> + n = &(*n)->rb_right;
> + else {
> + *bp->rcursor = ext;
> + return 1;
> + }
> + }
> + return 0;
> +}
This seems quite large for a static inline? I guess it is only called by a single function, so maybe not a big deal.
> +inline
> +static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
> +{
> + struct ext2fs_rb_private *bp;
> +
> + bp = (struct ext2fs_rb_private *) bitmap->private;
> + arg -= bitmap->start;
> +
> + return rb_test_bit(bp, arg);
> +}
This definitely doesn't make sense to be static inline, since its only use is by ext2_bitmap_ops table, so it can't possibly be inline...
> @@ -158,6 +161,7 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
> bmap->description = 0;
> }
> bmap->magic = 0;
> + ext2fs_free_mem(&bmap);
> }
This is really a defect in the original e2fsprogs, so it might make sense to submit it independently in case Ted isn't going to apply this patch right away.
Cheers, Andreas
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH 3/4] Add bitmap configuration interface
2011-03-17 18:50 ` [PATCH 3/4] Add bitmap configuration interface Lukas Czerner
@ 2011-03-17 21:03 ` Andreas Dilger
2011-03-18 10:13 ` Lukas Czerner
0 siblings, 1 reply; 13+ messages in thread
From: Andreas Dilger @ 2011-03-17 21:03 UTC (permalink / raw)
To: Lukas Czerner; +Cc: linux-ext4, tytso, sandeen
On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> Add a possibility for user to configure what bitmap backed will be used
> for what bitmap. It is also useful for testing and benchmarking
> different bitmap backends and its behaviour.
>
> Setting can be done via usual config file with new section [bitmaps]
> with subnames defining particular bitmaps. Argument is simply number of
> the backend. All backends are defined in ext2fsP.h like this:
>
> enum ext2fs_bmap_backends {
> EXT2FS_BMAP64_BITARRAY = 0,
> EXT2FS_BMAP64_RBTREE,
> EXT2FS_BMAP64_COUNT,
> };
>
> Here is an example of bitmap configuration, with the list of all
> supported bitmaps.
>
> [bitmaps]
> generic_bitmap = 1
> inode_used_map = 1
> inode_bad_map = 1
I wonder if this is enough just for debugging (presumably very few people will actually set this) or if there should be some symbolic constants used, like "bitmap", "rbtree", ...? That avoids exposing arbitrary internal constants to userspace, that will need to be preserved indefinitely.
Also useful would be a "default =" option that changes all of the unspecified bitmap types at once, to avoid the need to list all bitmaps explicitly (which may change over time), or possibly if "inode_map=" and "block_map=" are specified they become the default types for all other unspecified inode and block bitmaps?
> This feature requires interface change of ext2fs_alloc_generic_bmap()
> and its definition now is:
>
> errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
> int type, __u64 start, __u64 end,
> __u64 real_end,
> ext2fs_generic_bitmap *ret)
I was going to write that this will break the ABI/API for e2fsprogs, so probably is not acceptable to Ted. However, looking at the "master" branch, I see that it already has an "int type" argument, along with 64-bit arguments.
What branch is this patch series against?
> -errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs,
> - const char *descr,
> +errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs, int type,
> ext2fs_inode_bitmap *ret)
> {
Ah, unlike your comment above, this is changing the ext2fs_allocate_{block,inode}_bitmap() functions, which definitely will break the ABI/API. The other confusing thing is that since the number of parameters hasn't changed (size unchanged on 32-bit) then this wouldn't break the ABI totally and it would only cause a crash if the bitmap allocation failed and "type" is interpreted as a char * pointer.
One option is to have a separate helper function that changes the default bitmap type in ext2_filsys (maybe separate defaults for inode and block bitmaps), and then call that before this function. Not ideal, but doesn't change the ABI/API, and is sufficient for most uses. Alternately, it would be possible to declare a new ext2fs_allocate_{block,inode}_bitmap2() function that has this new parameter, and make ext2fs_allocate_{block,inode}_bmap() call it with the default bitmap type.
> EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
> + if (type >= EXT2_BMAP_COUNT || type < 0)
> + return EINVAL;
Is EINVAL a valid error return for libext2fs? Anything returning an errcode_t should probably be using a new EXT2_ET_INVALID_BITMAP_TYPE error defined in lib/ext2fs/ext2_err.et.in.
> +enum ext2_bitmap_type {
> + EXT2_GENERIC_MAP =0,
> + EXT2_INODE_USED_MAP, /* Inodes which are in use */
> + EXT2_INODE_BAD_MAP, /* Inodes which are bad somehow */
> + EXT2_INODE_DIR_MAP, /* Inodes which are directories */
> + EXT2_INODE_BB_MAP, /* Inodes which are in bad blocks */
> + EXT2_INODE_IMAGIC_MAP, /* AFS inodes */
EXT2_INODE_IMAGIC_MAP, /* Inodes disconnected but used by AFS */
> + EXT2_INODE_REG_MAP, /* Inodes which are regular files*/
> + EXT2_INODE_MAP,
> + EXT2_INODE_DUP_MAP,
> + EXT2_INODE_DONE_MAP,
> + EXT2_INODE_LOOP_MAP,
Would be nice to have comments for the rest of these as well. I renamed a couple to be consistent with _INODE_ or _BLOCK_ in each name. Let's see:
EXT2_INODE_MAP, /* Inodes in use */
EXT2_INODE_DUP_MAP, /* Inodes with duplicate block usage */
EXT2_INODE_DONE_MAP, /* Dirs linked to root during e2fsck */
EXT2_INODE_LOOP_MAP, /* Dirs hit in path walk for e2fsck*/
EXT2_BLOCK_MAP, /* Blocks in use */
EXT2_BLOCK_BAD_MAP, /* Blocks marked bad via badblocks */
EXT2_BLOCK_SCRAMBLE, /* Blocks scrambled for e2image */
EXT2_BLOCK_TO_MOVE, /* Blocks to move for resize2fs */
EXT2_BLOCK_RESERVED, /* Blocks reserved for resize2fs */
EXT2_BLOCK_METADATA, /* Blocks for metadata for resize2fs */
EXT2_BLOCK_EMPTY_DIR, /* Blocks for lost+found expansion */
EXT2_INODE_EMPTY_DIR_MAP, /* ??? */
EXT2_BLOCK_CHECK_DESC_MAP, /* Blocks used for group descriptors */
EXT2_BLOCK_TOUCHED_MAP, /* Blocks accessed during tst_iscan */
> + EXT2_BMAP_COUNT, /* Stop mark */
> +};
It isn't quite clear whether we need to have explicit block bitmap definitions for programs like tst_iscan. If it isn't possible for a program to allocate arbitrary bitmaps without having to register them first, it will really be a pain. I'd instead suggest that the "type" just default to EXT2_BLOCK_MAP for obscure bitmaps like "TOUCHED_MAP", and again allow specifying a bitmap name.
> -#define EXT2FS_BMAP64_BITARRAY 1
> -#define EXT2FS_BMAP64_RBTREE 2
> +enum ext2fs_bmap_backends {
> + EXT2FS_BMAP64_BITARRAY = 0,
> + EXT2FS_BMAP64_RBTREE,
> + EXT2FS_BMAP64_COUNT,
For debugging purposes, it is preferable to have an enum not contain "0" as a valid value, since that allows one to see if the bitmap type is being specified correctly, or if it is unset. Maybe EXT2FS_BMAP64_UNSET = 0?
> +static char *ext2_bmap_profile_value[EXT2_BMAP_COUNT] = {
> + [EXT2_GENERIC_MAP] = "generic_bitmap",
> + [EXT2_INODE_USED_MAP] = "inode_used_map",
> + [EXT2_INODE_BAD_MAP] = "inode_bad_map",
> +
> +const
> +static struct ext2_bmap_definition ext2_bmap_default[EXT2_BMAP_COUNT] = {
> + [EXT2_GENERIC_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "generic bitmap"},
> + [EXT2_INODE_USED_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "in-use inode map"},
> + [EXT2_INODE_BAD_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "bad inode map"},
It is cumbersome to have to update 3 places for each bitmap. Could we just get rid of ext2_bmap_profile_value[] and only use ext2_bmap_default[]? Also, the strings here have now lost their i18n for error messages.
Cheers, Andreas
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH 4/4] Add macro to enable collecting bitmap statistics
2011-03-17 18:50 ` [PATCH 4/4] Add macro to enable collecting bitmap statistics Lukas Czerner
@ 2011-03-17 21:19 ` Andreas Dilger
2011-03-18 10:23 ` Lukas Czerner
0 siblings, 1 reply; 13+ messages in thread
From: Andreas Dilger @ 2011-03-17 21:19 UTC (permalink / raw)
To: Lukas Czerner; +Cc: linux-ext4, tytso, sandeen
On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> This commit adds a new preprocessor macro BMAP_STATS, which can be
> defined in ext2fs.h. Setting this macro, the code for statistic
> collection of bitmap handling is enabled and once the bitmap shall be
> freed collected information is printed to the stderr.
>
> This feature is especially useful for better understanding how e2fsprogs
> tools (mainly e2fsck) treats bitmaps and what bitmap backend can be most
> suitable for particular bitmap. Backend itself (if implemented) can
> provide statistics of its own as well.
>
> I was thinking about enabling this feature simply by setting program
> parameter, however collecting of the statistic, even conditional, means
> unnecessary overhead. And since information provided is usually relevant
> only for e2fsprogs developers, I decided to use preprocessor macro
> instead.
Being able to turn this on/off at runtime without needing to recompile is pretty important. It is fine to allow it to be #ifdef out entirely, but if it is enabled it is good to be able to turn it on/off via the command-line.
> @@ -245,8 +260,8 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
>
> retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
> if (retval) {
> - ext2fs_free_mem(&bitmap);
> ext2fs_free_mem(&bitmap->description);
> + ext2fs_free_mem(&bitmap);
This looks like a bug in the upstream code that should be submitted separately. However, I don't see this bug in my tree (it is correctly ordered already), and I don't see it being introduced by your patches... It again makes me wonder which branch these patches are against.
> + fprintf(stderr, "\n[+] %s bitmap\n", bmap_defs[stats->type].descr);
> + fprintf(stderr, "=================================================\n");
> + fprintf(stderr, "%16d type\n%16d backend\n",
> + stats->type, bmap_defs[stats->type].backend);
> + fprintf(stderr, "%16d bits long\n",
> + bitmap->real_end - bitmap->start);
> + fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
> + stats->copy_count, stats->resize_count);
> + fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
> + stats->mark_count, stats->unmark_count);
> + fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
> + stats->test_count, stats->mark_ext_count);
> + fprintf(stderr, "%16lu unmark_bmap_extent\n"
> + "%16lu test_clear_bmap_extent\n",
> + stats->unmark_ext_count, stats->test_ext_count);
> + fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
> + stats->set_range_count, stats->get_range_count);
> + fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%)\n",
> + stats->clear_count, stats->test_seq, test_seq_perc);
> + fprintf(stderr, "%16lu contiguous bit mark (%.2f%)\n"
> + "%16lu bits tested backwards (%.2f%)\n",
> + stats->mark_seq, mark_seq_perc,
> + stats->test_back, test_back_perc);
> + fprintf(stderr, "%16lu bits marked backwards (%.2f%)\n"
> + "%16.2f seconds in use\n",
> + stats->mark_back, mark_back_perc, inuse);
> +}
This should include the amount of memory used by the bitmap, which is one of the most important stats for this code.
> +#endif
> +
> void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
> {
> if (!bmap)
> @@ -267,6 +338,16 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
> if (!EXT2FS_IS_64_BITMAP(bmap))
> return;
>
> +#ifdef BMAP_STATS
> + if (gettimeofday(&bmap->stats.destroyed,
> + (struct timezone *) NULL) == -1) {
> + perror("gettimeofday");
> + return;
> + }
> + ext2fs_print_bmap_statistics(bmap);
> + bmap->bitmap_ops->print_stats(bmap);
> +#endif
> +
> bmap->bitmap_ops->free_bmap(bmap);
>
> if (bmap->description) {
> @@ -300,6 +381,17 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
> return retval;
> memset(new_bmap, 0, sizeof(struct ext2fs_struct_generic_bitmap));
>
> +
> +#ifdef BMAP_STATS
> + src->stats.copy_count++;
> + if (gettimeofday(&new_bmap->stats.created,
> + (struct timezone *) NULL) == -1) {
> + perror("gettimeofday");
> + return 1;
> + }
> + new_bmap->stats.type = src->stats.type;
> +#endif
> +
> /* Copy all the high-level parts over */
> new_bmap->magic = src->magic;
> new_bmap->fs = src->fs;
> @@ -346,6 +438,8 @@ errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
> if (!EXT2FS_IS_64_BITMAP(bmap))
> return EINVAL;
>
> + INC_STAT(bmap, resize_count);
> +
> return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
> }
>
> @@ -432,6 +526,15 @@ int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
> if (!EXT2FS_IS_64_BITMAP(bitmap))
> return 0;
>
> +#ifdef BMAP_STATS
> + if (arg == bitmap->stats.last_marked + 1)
> + bitmap->stats.mark_seq++;
> + if (arg < bitmap->stats.last_marked)
> + bitmap->stats.mark_back++;
> + bitmap->stats.last_marked = arg;
> + bitmap->stats.mark_count++;
> +#endif
> +
> if ((arg < bitmap->start) || (arg > bitmap->end)) {
> warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
> return 0;
> @@ -458,6 +561,8 @@ int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
> if (!EXT2FS_IS_64_BITMAP(bitmap))
> return 0;
>
> + INC_STAT(bitmap, unmark_count);
> +
> if ((arg < bitmap->start) || (arg > bitmap->end)) {
> warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
> return 0;
> @@ -484,6 +589,15 @@ int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
> if (!EXT2FS_IS_64_BITMAP(bitmap))
> return 0;
>
> +#ifdef BMAP_STATS
> + bitmap->stats.test_count++;
> + if (arg == bitmap->stats.last_tested + 1)
> + bitmap->stats.test_seq++;
> + if (arg < bitmap->stats.last_tested)
> + bitmap->stats.test_back++;
> + bitmap->stats.last_tested = arg;
> +#endif
> +
> if ((arg < bitmap->start) || (arg > bitmap->end)) {
> warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
> return 0;
> @@ -512,6 +626,8 @@ errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
> if (!EXT2FS_IS_64_BITMAP(bmap))
> return EINVAL;
>
> + INC_STAT(bmap, set_range_count);
> +
> return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
> }
>
> @@ -535,6 +651,8 @@ errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
> if (!EXT2FS_IS_64_BITMAP(bmap))
> return EINVAL;
>
> + INC_STAT(bmap, get_range_count);
> +
> return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
> }
>
> @@ -606,6 +724,8 @@ int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
> if (!EXT2FS_IS_64_BITMAP(bmap))
> return EINVAL;
>
> + INC_STAT(bmap, test_ext_count);
> +
> return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
> }
>
> @@ -628,6 +748,8 @@ void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
> if (!EXT2FS_IS_64_BITMAP(bmap))
> return;
>
> + INC_STAT(bmap, mark_ext_count);
> +
> if ((block < bmap->start) || (block+num-1 > bmap->end)) {
> ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
> bmap->description);
> @@ -656,6 +778,8 @@ void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
> if (!EXT2FS_IS_64_BITMAP(bmap))
> return;
>
> + INC_STAT(bmap, unmark_ext_count);
> +
> if ((block < bmap->start) || (block+num-1 > bmap->end)) {
> ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
> bmap->description);
> --
> 1.7.4
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
Cheers, Andreas
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH 1/4 v2] e2fsprogs: Add rbtree library
2011-03-17 19:34 ` Andreas Dilger
@ 2011-03-18 9:46 ` Lukas Czerner
0 siblings, 0 replies; 13+ messages in thread
From: Lukas Czerner @ 2011-03-18 9:46 UTC (permalink / raw)
To: Andreas Dilger; +Cc: Lukas Czerner, linux-ext4, tytso, sandeen
On Thu, 17 Mar 2011, Andreas Dilger wrote:
> On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> > +#undef offsetof
> > +#ifdef __compiler_offsetof
> > +#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
> > +#else
> > +#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
> > +#endif
>
> This may as well go into a more common header like lib/ext2fs/ext2fs.h, since I see offsetof() is #defined 5 separate times in the e2fsprogs code already.
>
> > +#define container_of(ptr, type, member) ({ \
> > + const typeof( ((type *)0)->member ) *__mptr = (ptr); \
> > + (type *)( (char *)__mptr - offsetof(type,member) );})
>
> Same.
>
> > +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
> > +#define rb_color(r) ((r)->rb_parent_color & 1)
> > +#define rb_is_red(r) (!rb_color(r))
> > +#define rb_is_black(r) rb_color(r)
> > +#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
> > +#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
> > +
> > +#define RB_ROOT (struct rb_root) { NULL, }
> > +#define rb_entry(ptr, type, member) container_of(ptr, type, member)
>
> The indenting here is a bit broken, but I see it is the same in the upstream kernel code, so it probably shouldn't be changed just for e2fsprogs.
>
>
> Cheers, Andreas
>
Hi Andreas,
thank you for the review! You're right I'll move those macros into
lib/ext2fs/ext2fs.h
Thanks!
-Lukas
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays
2011-03-17 19:56 ` Andreas Dilger
@ 2011-03-18 9:55 ` Lukas Czerner
0 siblings, 0 replies; 13+ messages in thread
From: Lukas Czerner @ 2011-03-18 9:55 UTC (permalink / raw)
To: Andreas Dilger; +Cc: Lukas Czerner, linux-ext4, tytso, sandeen
On Thu, 17 Mar 2011, Andreas Dilger wrote:
> On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> > +++ b/lib/ext2fs/blkmap64_rb.c
> > +struct bmap_rb_extent {
> > + struct rb_node node;
> > + __u64 start;
> > + __u32 count;
> > +};
>
> On 32-bit machines (where memory consumption is even more critical) this will pack better by arranging it with "count" aligned with rb_parent_color:
>
> struct bmap_rb_extent {
> __u64 start;
> __u32 count;
> struct rb_node node;
> };
>
> That will give a leaf size of 24 bytes on a 32-bit arch, instead of 32 bytes with padding. On a 64-bit arch it won't make any difference.
Oh, of course, do not know how I missed that.
>
> > static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
> > + __u64 new_end, __u64 new_real_end)
> > +{
> > + struct ext2fs_rb_private *bp;
> > +
> > + if (new_real_end >= bmap->real_end) {
> > + bmap->end = new_end;
> > + bmap->real_end = new_real_end;
> > + return 0;
> > + }
> > +
> > + bp = (struct ext2fs_rb_private *) bmap->private;
> > + *bp->rcursor = NULL;
> > + *bp->wcursor = NULL;
> > +
> > + /* truncate tree to new_real_end size */
> > + rb_truncate(new_real_end, &bp->root);
> > +
> > + bmap->end = new_end;
> > + bmap->real_end = new_real_end;
> > + return 0;
> > +
> > +}
>
> This might be a bit better written as:
>
> static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
> __u64 new_end, __u64 new_real_end)
> {
> struct ext2fs_rb_private *bp;
>
> if (new_real_end < bmap->real_end) {
> bp = (struct ext2fs_rb_private *)bmap->private;
> *bp->rcursor = NULL;
> *bp->wcursor = NULL;
>
> /* truncate tree to new_real_end size */
> rb_truncate(new_real_end, &bp->root);
> }
>
> bmap->end = new_end;
> bmap->real_end = new_real_end;
> return 0;
>
> }
Right that's definitely better.
>
> > +inline static int
> > +rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
> > +{
> > + struct bmap_rb_extent *rcursor;
> > + struct rb_node *parent = NULL;
> > + struct rb_node **n = &bp->root.rb_node;
> > + struct bmap_rb_extent *ext;
> > + int i=0;
> > +
> > + rcursor = *bp->rcursor;
> > + if (!rcursor)
> > + goto search_tree;
> > +
> > + if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
> > + return 1;
> > +
> > + rcursor = *bp->wcursor;
> > + if (!rcursor)
> > + goto search_tree;
> > +
> > + if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
> > + return 1;
> > +
> > +search_tree:
> > +
> > + while (*n) {
> > + parent = *n;
> > + ext = rb_entry(parent, struct bmap_rb_extent, node);
> > + if (bit < ext->start)
> > + n = &(*n)->rb_left;
> > + else if (bit >= (ext->start + ext->count))
> > + n = &(*n)->rb_right;
> > + else {
> > + *bp->rcursor = ext;
> > + return 1;
> > + }
> > + }
> > + return 0;
> > +}
>
> This seems quite large for a static inline? I guess it is only called by a single function, so maybe not a big deal.
It is actually called for two functions and since this is the most
called function, I think this it is worth it (there is approx. 1%
performance boost bound with this).
>
> > +inline
> > +static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
> > +{
> > + struct ext2fs_rb_private *bp;
> > +
> > + bp = (struct ext2fs_rb_private *) bitmap->private;
> > + arg -= bitmap->start;
> > +
> > + return rb_test_bit(bp, arg);
> > +}
>
> This definitely doesn't make sense to be static inline, since its only use is by ext2_bitmap_ops table, so it can't possibly be inline...
Right, I'll fix that.
>
> > @@ -158,6 +161,7 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
> > bmap->description = 0;
> > }
> > bmap->magic = 0;
> > + ext2fs_free_mem(&bmap);
> > }
>
> This is really a defect in the original e2fsprogs, so it might make sense to submit it independently in case Ted isn't going to apply this patch right away.
Yes, somehow I forgot about that. Thanks.
>
> Cheers, Andreas
>
Thanks!
-Lukas
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH 3/4] Add bitmap configuration interface
2011-03-17 21:03 ` Andreas Dilger
@ 2011-03-18 10:13 ` Lukas Czerner
0 siblings, 0 replies; 13+ messages in thread
From: Lukas Czerner @ 2011-03-18 10:13 UTC (permalink / raw)
To: Andreas Dilger; +Cc: Lukas Czerner, linux-ext4, tytso, sandeen
On Thu, 17 Mar 2011, Andreas Dilger wrote:
> On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> > Add a possibility for user to configure what bitmap backed will be used
> > for what bitmap. It is also useful for testing and benchmarking
> > different bitmap backends and its behaviour.
> >
> > Setting can be done via usual config file with new section [bitmaps]
> > with subnames defining particular bitmaps. Argument is simply number of
> > the backend. All backends are defined in ext2fsP.h like this:
> >
> > enum ext2fs_bmap_backends {
> > EXT2FS_BMAP64_BITARRAY = 0,
> > EXT2FS_BMAP64_RBTREE,
> > EXT2FS_BMAP64_COUNT,
> > };
> >
> > Here is an example of bitmap configuration, with the list of all
> > supported bitmaps.
> >
> > [bitmaps]
> > generic_bitmap = 1
> > inode_used_map = 1
> > inode_bad_map = 1
>
> I wonder if this is enough just for debugging (presumably very few people will actually set this) or if there should be some symbolic constants used, like "bitmap", "rbtree", ...? That avoids exposing arbitrary internal constants to userspace, that will need to be preserved indefinitely.
Yes, I thought about that, but it seemed unnecessary. However I can see
your point, I'll change that.
>
> Also useful would be a "default =" option that changes all of the unspecified bitmap types at once, to avoid the need to list all bitmaps explicitly (which may change over time), or possibly if "inode_map=" and "block_map=" are specified they become the default types for all other unspecified inode and block bitmaps?
Now that's very good idea, I'll take a look into it.
>
> > This feature requires interface change of ext2fs_alloc_generic_bmap()
> > and its definition now is:
> >
> > errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
> > int type, __u64 start, __u64 end,
> > __u64 real_end,
> > ext2fs_generic_bitmap *ret)
>
> I was going to write that this will break the ABI/API for e2fsprogs, so probably is not acceptable to Ted. However, looking at the "master" branch, I see that it already has an "int type" argument, along with 64-bit arguments.
>
> What branch is this patch series against?
It is based on master branch from
git://git.kernel.org/pub/scm/fs/ext2/e2fsprogs.git
>
> > -errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs,
> > - const char *descr,
> > +errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs, int type,
> > ext2fs_inode_bitmap *ret)
> > {
>
> Ah, unlike your comment above, this is changing the ext2fs_allocate_{block,inode}_bitmap() functions, which definitely will break the ABI/API. The other confusing thing is that since the number of parameters hasn't changed (size unchanged on 32-bit) then this wouldn't break the ABI totally and it would only cause a crash if the bitmap allocation failed and "type" is interpreted as a char * pointer.
>
> One option is to have a separate helper function that changes the default bitmap type in ext2_filsys (maybe separate defaults for inode and block bitmaps), and then call that before this function. Not ideal, but doesn't change the ABI/API, and is sufficient for most uses. Alternately, it would be possible to declare a new ext2fs_allocate_{block,inode}_bitmap2() function that has this new parameter, and make ext2fs_allocate_{block,inode}_bmap() call it with the default bitmap type.
Well I know that this breaks ABI/API and if that matters I can fix that.
However I have a question, is preserving ABI/API really that important
in e2fsprogs ? I guess it is when you are mentioning it, but I can not
really see why ?
>
> > EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
> > + if (type >= EXT2_BMAP_COUNT || type < 0)
> > + return EINVAL;
>
> Is EINVAL a valid error return for libext2fs? Anything returning an errcode_t should probably be using a new EXT2_ET_INVALID_BITMAP_TYPE error defined in lib/ext2fs/ext2_err.et.in.
You're right I'll fix that.
>
> > +enum ext2_bitmap_type {
> > + EXT2_GENERIC_MAP =0,
> > + EXT2_INODE_USED_MAP, /* Inodes which are in use */
> > + EXT2_INODE_BAD_MAP, /* Inodes which are bad somehow */
> > + EXT2_INODE_DIR_MAP, /* Inodes which are directories */
> > + EXT2_INODE_BB_MAP, /* Inodes which are in bad blocks */
> > + EXT2_INODE_IMAGIC_MAP, /* AFS inodes */
>
> EXT2_INODE_IMAGIC_MAP, /* Inodes disconnected but used by AFS */
>
> > + EXT2_INODE_REG_MAP, /* Inodes which are regular files*/
> > + EXT2_INODE_MAP,
> > + EXT2_INODE_DUP_MAP,
> > + EXT2_INODE_DONE_MAP,
> > + EXT2_INODE_LOOP_MAP,
>
> Would be nice to have comments for the rest of these as well. I renamed a couple to be consistent with _INODE_ or _BLOCK_ in each name. Let's see:
>
> EXT2_INODE_MAP, /* Inodes in use */
> EXT2_INODE_DUP_MAP, /* Inodes with duplicate block usage */
> EXT2_INODE_DONE_MAP, /* Dirs linked to root during e2fsck */
> EXT2_INODE_LOOP_MAP, /* Dirs hit in path walk for e2fsck*/
>
> EXT2_BLOCK_MAP, /* Blocks in use */
> EXT2_BLOCK_BAD_MAP, /* Blocks marked bad via badblocks */
> EXT2_BLOCK_SCRAMBLE, /* Blocks scrambled for e2image */
> EXT2_BLOCK_TO_MOVE, /* Blocks to move for resize2fs */
> EXT2_BLOCK_RESERVED, /* Blocks reserved for resize2fs */
> EXT2_BLOCK_METADATA, /* Blocks for metadata for resize2fs */
>
> EXT2_BLOCK_EMPTY_DIR, /* Blocks for lost+found expansion */
> EXT2_INODE_EMPTY_DIR_MAP, /* ??? */
> EXT2_BLOCK_CHECK_DESC_MAP, /* Blocks used for group descriptors */
> EXT2_BLOCK_TOUCHED_MAP, /* Blocks accessed during tst_iscan */
Thanks!
>
> > + EXT2_BMAP_COUNT, /* Stop mark */
> > +};
>
> It isn't quite clear whether we need to have explicit block bitmap definitions for programs like tst_iscan. If it isn't possible for a program to allocate arbitrary bitmaps without having to register them first, it will really be a pain. I'd instead suggest that the "type" just default to EXT2_BLOCK_MAP for obscure bitmaps like "TOUCHED_MAP", and again allow specifying a bitmap name.
Well I tried to cover all bitmaps in e2fsprogs tools. Now, if someone
would like to use some anonymous bitmap, or just do not want to create
new bitmap definitions, one can easily use EXT2_GENERIC_BITMAP.
>
> > -#define EXT2FS_BMAP64_BITARRAY 1
> > -#define EXT2FS_BMAP64_RBTREE 2
> > +enum ext2fs_bmap_backends {
> > + EXT2FS_BMAP64_BITARRAY = 0,
> > + EXT2FS_BMAP64_RBTREE,
> > + EXT2FS_BMAP64_COUNT,
>
> For debugging purposes, it is preferable to have an enum not contain "0" as a valid value, since that allows one to see if the bitmap type is being specified correctly, or if it is unset. Maybe EXT2FS_BMAP64_UNSET = 0?
Good point, I'll change that.
>
> > +static char *ext2_bmap_profile_value[EXT2_BMAP_COUNT] = {
> > + [EXT2_GENERIC_MAP] = "generic_bitmap",
> > + [EXT2_INODE_USED_MAP] = "inode_used_map",
> > + [EXT2_INODE_BAD_MAP] = "inode_bad_map",
> > +
> > +const
> > +static struct ext2_bmap_definition ext2_bmap_default[EXT2_BMAP_COUNT] = {
> > + [EXT2_GENERIC_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "generic bitmap"},
> > + [EXT2_INODE_USED_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "in-use inode map"},
> > + [EXT2_INODE_BAD_MAP] = {EXT2_DEFAULT_BITMAP_BACKEND, "bad inode map"},
>
> It is cumbersome to have to update 3 places for each bitmap. Could we just get rid of ext2_bmap_profile_value[] and only use ext2_bmap_default[]? Also, the strings here have now lost their i18n for error messages.
I was thinking about merging those two structures, maybe using macros,
I'll look into it. Yes, is has lost their i18n for error messages, do
you have any suggestion to preserve localization with statically
declared strings ?
>
> Cheers, Andreas
>
Thanks!
-Lukas
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH 4/4] Add macro to enable collecting bitmap statistics
2011-03-17 21:19 ` Andreas Dilger
@ 2011-03-18 10:23 ` Lukas Czerner
0 siblings, 0 replies; 13+ messages in thread
From: Lukas Czerner @ 2011-03-18 10:23 UTC (permalink / raw)
To: Andreas Dilger; +Cc: Lukas Czerner, linux-ext4, tytso, sandeen
On Thu, 17 Mar 2011, Andreas Dilger wrote:
> On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> > This commit adds a new preprocessor macro BMAP_STATS, which can be
> > defined in ext2fs.h. Setting this macro, the code for statistic
> > collection of bitmap handling is enabled and once the bitmap shall be
> > freed collected information is printed to the stderr.
> >
> > This feature is especially useful for better understanding how e2fsprogs
> > tools (mainly e2fsck) treats bitmaps and what bitmap backend can be most
> > suitable for particular bitmap. Backend itself (if implemented) can
> > provide statistics of its own as well.
> >
> > I was thinking about enabling this feature simply by setting program
> > parameter, however collecting of the statistic, even conditional, means
> > unnecessary overhead. And since information provided is usually relevant
> > only for e2fsprogs developers, I decided to use preprocessor macro
> > instead.
>
> Being able to turn this on/off at runtime without needing to recompile is pretty important. It is fine to allow it to be #ifdef out entirely, but if it is enabled it is good to be able to turn it on/off via the command-line.
The downside of this is that bitmaps are used by many tools, so it would
require change in all of those tools to use command-line option.
>
> > @@ -245,8 +260,8 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
> >
> > retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
> > if (retval) {
> > - ext2fs_free_mem(&bitmap);
> > ext2fs_free_mem(&bitmap->description);
> > + ext2fs_free_mem(&bitmap);
>
> This looks like a bug in the upstream code that should be submitted separately. However, I don't see this bug in my tree (it is correctly ordered already), and I don't see it being introduced by your patches... It again makes me wonder which branch these patches are against.
I can see this bug in master branch
git://git.kernel.org/pub/scm/fs/ext2/e2fsprogs.git
so I'll send it separately.
>
> > + fprintf(stderr, "\n[+] %s bitmap\n", bmap_defs[stats->type].descr);
> > + fprintf(stderr, "=================================================\n");
> > + fprintf(stderr, "%16d type\n%16d backend\n",
> > + stats->type, bmap_defs[stats->type].backend);
> > + fprintf(stderr, "%16d bits long\n",
> > + bitmap->real_end - bitmap->start);
> > + fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
> > + stats->copy_count, stats->resize_count);
> > + fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
> > + stats->mark_count, stats->unmark_count);
> > + fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
> > + stats->test_count, stats->mark_ext_count);
> > + fprintf(stderr, "%16lu unmark_bmap_extent\n"
> > + "%16lu test_clear_bmap_extent\n",
> > + stats->unmark_ext_count, stats->test_ext_count);
> > + fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
> > + stats->set_range_count, stats->get_range_count);
> > + fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%)\n",
> > + stats->clear_count, stats->test_seq, test_seq_perc);
> > + fprintf(stderr, "%16lu contiguous bit mark (%.2f%)\n"
> > + "%16lu bits tested backwards (%.2f%)\n",
> > + stats->mark_seq, mark_seq_perc,
> > + stats->test_back, test_back_perc);
> > + fprintf(stderr, "%16lu bits marked backwards (%.2f%)\n"
> > + "%16.2f seconds in use\n",
> > + stats->mark_back, mark_back_perc, inuse);
> > +}
>
> This should include the amount of memory used by the bitmap, which is one of the most important stats for this code.
Yes, it is the most important, however at this level we can not know
this kind of bitmap backend specific information. That's why there is
new bitmap operation print_stats() which is called right after
ext2fs_print_bmap_statistics() and should provide additional bitmap
backed specific information. Rbtree and bitarray does that with this
commit.
>
> > +#endif
> > +
> > void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
> > {
> > if (!bmap)
> > @@ -267,6 +338,16 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
> > if (!EXT2FS_IS_64_BITMAP(bmap))
> > return;
> >
> > +#ifdef BMAP_STATS
> > + if (gettimeofday(&bmap->stats.destroyed,
> > + (struct timezone *) NULL) == -1) {
> > + perror("gettimeofday");
> > + return;
> > + }
> > + ext2fs_print_bmap_statistics(bmap);
> > + bmap->bitmap_ops->print_stats(bmap);
> > +#endif
> > +
> > bmap->bitmap_ops->free_bmap(bmap);
> >
> > if (bmap->description) {
> > @@ -300,6 +381,17 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
> > return retval;
> > memset(new_bmap, 0, sizeof(struct ext2fs_struct_generic_bitmap));
> >
> > +
> > +#ifdef BMAP_STATS
> > + src->stats.copy_count++;
> > + if (gettimeofday(&new_bmap->stats.created,
> > + (struct timezone *) NULL) == -1) {
> > + perror("gettimeofday");
> > + return 1;
> > + }
> > + new_bmap->stats.type = src->stats.type;
> > +#endif
> > +
> > /* Copy all the high-level parts over */
> > new_bmap->magic = src->magic;
> > new_bmap->fs = src->fs;
> > @@ -346,6 +438,8 @@ errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
> > if (!EXT2FS_IS_64_BITMAP(bmap))
> > return EINVAL;
> >
> > + INC_STAT(bmap, resize_count);
> > +
> > return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
> > }
> >
> > @@ -432,6 +526,15 @@ int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
> > if (!EXT2FS_IS_64_BITMAP(bitmap))
> > return 0;
> >
> > +#ifdef BMAP_STATS
> > + if (arg == bitmap->stats.last_marked + 1)
> > + bitmap->stats.mark_seq++;
> > + if (arg < bitmap->stats.last_marked)
> > + bitmap->stats.mark_back++;
> > + bitmap->stats.last_marked = arg;
> > + bitmap->stats.mark_count++;
> > +#endif
> > +
> > if ((arg < bitmap->start) || (arg > bitmap->end)) {
> > warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
> > return 0;
> > @@ -458,6 +561,8 @@ int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
> > if (!EXT2FS_IS_64_BITMAP(bitmap))
> > return 0;
> >
> > + INC_STAT(bitmap, unmark_count);
> > +
> > if ((arg < bitmap->start) || (arg > bitmap->end)) {
> > warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
> > return 0;
> > @@ -484,6 +589,15 @@ int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
> > if (!EXT2FS_IS_64_BITMAP(bitmap))
> > return 0;
> >
> > +#ifdef BMAP_STATS
> > + bitmap->stats.test_count++;
> > + if (arg == bitmap->stats.last_tested + 1)
> > + bitmap->stats.test_seq++;
> > + if (arg < bitmap->stats.last_tested)
> > + bitmap->stats.test_back++;
> > + bitmap->stats.last_tested = arg;
> > +#endif
> > +
> > if ((arg < bitmap->start) || (arg > bitmap->end)) {
> > warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
> > return 0;
> > @@ -512,6 +626,8 @@ errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
> > if (!EXT2FS_IS_64_BITMAP(bmap))
> > return EINVAL;
> >
> > + INC_STAT(bmap, set_range_count);
> > +
> > return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
> > }
> >
> > @@ -535,6 +651,8 @@ errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
> > if (!EXT2FS_IS_64_BITMAP(bmap))
> > return EINVAL;
> >
> > + INC_STAT(bmap, get_range_count);
> > +
> > return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
> > }
> >
> > @@ -606,6 +724,8 @@ int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
> > if (!EXT2FS_IS_64_BITMAP(bmap))
> > return EINVAL;
> >
> > + INC_STAT(bmap, test_ext_count);
> > +
> > return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
> > }
> >
> > @@ -628,6 +748,8 @@ void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
> > if (!EXT2FS_IS_64_BITMAP(bmap))
> > return;
> >
> > + INC_STAT(bmap, mark_ext_count);
> > +
> > if ((block < bmap->start) || (block+num-1 > bmap->end)) {
> > ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
> > bmap->description);
> > @@ -656,6 +778,8 @@ void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
> > if (!EXT2FS_IS_64_BITMAP(bmap))
> > return;
> >
> > + INC_STAT(bmap, unmark_ext_count);
> > +
> > if ((block < bmap->start) || (block+num-1 > bmap->end)) {
> > ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
> > bmap->description);
> > --
> > 1.7.4
> >
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at http://vger.kernel.org/majordomo-info.html
>
>
> Cheers, Andreas
>
Thanks!
-Lukas
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2011-03-18 10:23 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2011-03-17 18:50 Add rbtree backend for storing bitmaps Lukas Czerner
2011-03-17 18:50 ` [PATCH 1/4 v2] e2fsprogs: Add rbtree library Lukas Czerner
2011-03-17 19:34 ` Andreas Dilger
2011-03-18 9:46 ` Lukas Czerner
2011-03-17 18:50 ` [PATCH 2/4 v2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays Lukas Czerner
2011-03-17 19:56 ` Andreas Dilger
2011-03-18 9:55 ` Lukas Czerner
2011-03-17 18:50 ` [PATCH 3/4] Add bitmap configuration interface Lukas Czerner
2011-03-17 21:03 ` Andreas Dilger
2011-03-18 10:13 ` Lukas Czerner
2011-03-17 18:50 ` [PATCH 4/4] Add macro to enable collecting bitmap statistics Lukas Czerner
2011-03-17 21:19 ` Andreas Dilger
2011-03-18 10:23 ` Lukas Czerner
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).