mtd/fs/jffs2 nodelist.c, 1.94, 1.95 nodelist.h, 1.130,
1.131 readinode.c, 1.119, 1.120
David Woodhouse
dwmw2 at infradead.org
Tue Jul 5 17:03:10 EDT 2005
Update of /home/cvs/mtd/fs/jffs2
In directory phoenix.infradead.org:/tmp/cvs-serv27187
Modified Files:
nodelist.c nodelist.h readinode.c
Log Message:
JFFS2: Optimise jffs2_add_tn_to_list to use an rbtree
instead of a simple linked list. We were wasting an amazing amount of
time in jffs2_add_tn_to_list(). Thanks to Artem Bityuckiy for noticing.
Signed-off-by: David Woodhouse <dwmw2 at infradead.org>
Index: nodelist.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/nodelist.c,v
retrieving revision 1.94
retrieving revision 1.95
diff -u -r1.94 -r1.95
--- nodelist.c 13 Apr 2005 13:22:35 -0000 1.94
+++ nodelist.c 5 Jul 2005 21:03:07 -0000 1.95
@@ -58,27 +58,61 @@
/* Put a new tmp_dnode_info into the list, keeping the list in
order of increasing version
*/
-static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct jffs2_tmp_dnode_info **list)
-{
- struct jffs2_tmp_dnode_info **prev = list;
-
- while ((*prev) && (*prev)->version < tn->version) {
- prev = &((*prev)->next);
- }
- tn->next = (*prev);
- *prev = tn;
-}
-static void jffs2_free_tmp_dnode_info_list(struct jffs2_tmp_dnode_info *tn)
+static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct rb_root *list)
{
- struct jffs2_tmp_dnode_info *next;
+ struct rb_node **p = &list->rb_node;
+ struct rb_node * parent = NULL;
+ struct jffs2_tmp_dnode_info *this;
+
+ while (*p) {
+ parent = *p;
+ this = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
+
+ if (tn->version < this->version)
+ p = &(*p)->rb_left;
+ else if (tn->version > this->version)
+ p = &(*p)->rb_right;
+ else if (tn < this)
+ p = &(*p)->rb_left;
+ else
+ p = &(*p)->rb_right;
+ }
+
+ rb_link_node(&tn->rb, parent, p);
+ rb_insert_color(&tn->rb, list);
+}
+
+static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
+{
+ struct rb_node *this;
+ struct jffs2_tmp_dnode_info *tn;
+
+ this = list->rb_node;
+
+ /* Now at bottom of tree */
+ while (this) {
+ if (this->rb_left)
+ this = this->rb_left;
+ else if (this->rb_right)
+ this = this->rb_right;
+ else {
+ tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb);
+ jffs2_free_full_dnode(tn->fn);
+ jffs2_free_tmp_dnode_info(tn);
+
+ this = this->rb_parent;
+ if (!this)
+ break;
- while (tn) {
- next = tn;
- tn = tn->next;
- jffs2_free_full_dnode(next->fn);
- jffs2_free_tmp_dnode_info(next);
+ if (this->rb_left == &tn->rb)
+ this->rb_left = NULL;
+ else if (this->rb_right == &tn->rb)
+ this->rb_right = NULL;
+ else BUG();
+ }
}
+ list->rb_node = NULL;
}
static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
@@ -108,12 +142,13 @@
with this ino, returning the former in order of version */
int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
- struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp,
+ struct rb_root *tnp, struct jffs2_full_dirent **fdp,
uint32_t *highest_version, uint32_t *latest_mctime,
uint32_t *mctime_ver)
{
struct jffs2_raw_node_ref *ref, *valid_ref;
- struct jffs2_tmp_dnode_info *tn, *ret_tn = NULL;
+ struct jffs2_tmp_dnode_info *tn;
+ struct rb_root ret_tn = RB_ROOT;
struct jffs2_full_dirent *fd, *ret_fd = NULL;
union jffs2_node_union node;
size_t retlen;
@@ -450,7 +485,7 @@
return 0;
free_out:
- jffs2_free_tmp_dnode_info_list(ret_tn);
+ jffs2_free_tmp_dnode_info_list(&ret_tn);
jffs2_free_full_dirent_list(ret_fd);
return err;
}
Index: nodelist.h
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/nodelist.h,v
retrieving revision 1.130
retrieving revision 1.131
diff -u -r1.130 -r1.131
--- nodelist.h 9 Apr 2005 10:46:59 -0000 1.130
+++ nodelist.h 5 Jul 2005 21:03:07 -0000 1.131
@@ -161,7 +161,7 @@
*/
struct jffs2_tmp_dnode_info
{
- struct jffs2_tmp_dnode_info *next;
+ struct rb_node rb;
struct jffs2_full_dnode *fn;
uint32_t version;
};
@@ -387,7 +387,7 @@
D2(void jffs2_print_frag_list(struct jffs2_inode_info *f));
void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list);
int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
- struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp,
+ struct rb_root *tnp, struct jffs2_full_dirent **fdp,
uint32_t *highest_version, uint32_t *latest_mctime,
uint32_t *mctime_ver);
void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state);
Index: readinode.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/readinode.c,v
retrieving revision 1.119
retrieving revision 1.120
diff -u -r1.119 -r1.120
--- readinode.c 1 Mar 2005 10:34:03 -0000 1.119
+++ readinode.c 5 Jul 2005 21:03:07 -0000 1.120
@@ -500,7 +500,9 @@
struct jffs2_inode_info *f,
struct jffs2_raw_inode *latest_node)
{
- struct jffs2_tmp_dnode_info *tn_list, *tn;
+ struct jffs2_tmp_dnode_info *tn = NULL;
+ struct rb_root tn_list;
+ struct rb_node *rb, *repl_rb;
struct jffs2_full_dirent *fd_list;
struct jffs2_full_dnode *fn = NULL;
uint32_t crc;
@@ -522,9 +524,10 @@
}
f->dents = fd_list;
- while (tn_list) {
- tn = tn_list;
+ rb = rb_first(&tn_list);
+ while (rb) {
+ tn = rb_entry(rb, struct jffs2_tmp_dnode_info, rb);
fn = tn->fn;
if (f->metadata) {
@@ -556,7 +559,30 @@
mdata_ver = tn->version;
}
next_tn:
- tn_list = tn->next;
+ BUG_ON(rb->rb_left);
+ repl_rb = NULL;
+ if (rb->rb_parent && rb->rb_parent->rb_left == rb) {
+ /* We were then left-hand child of our parent. We need
+ to move our own right-hand child into our place. */
+ repl_rb = rb->rb_right;
+ if (repl_rb)
+ repl_rb->rb_parent = rb->rb_parent;
+ } else
+ repl_rb = NULL;
+
+ rb = rb_next(rb);
+
+ /* Remove the spent tn from the tree; don't bother rebalancing
+ but put our right-hand child in our own place. */
+ if (tn->rb.rb_parent) {
+ if (tn->rb.rb_parent->rb_left == &tn->rb)
+ tn->rb.rb_parent->rb_left = repl_rb;
+ else if (tn->rb.rb_parent->rb_right == &tn->rb)
+ tn->rb.rb_parent->rb_right = repl_rb;
+ else BUG();
+ } else if (tn->rb.rb_right)
+ tn->rb.rb_right->rb_parent = NULL;
+
jffs2_free_tmp_dnode_info(tn);
}
D1(jffs2_sanitycheck_fragtree(f));
More information about the linux-mtd-cvs
mailing list