aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Woodhouse <dwmw2@infradead.org>2005-07-05 17:03:10 -0400
committerThomas Gleixner <tglx@mtd.linutronix.de>2005-07-06 08:07:54 -0400
commit9dee7503ce3fc38911b9873216619190cf688128 (patch)
tree4a980e7afd14722a81472600ed13e147ff69f923
parent10c96f2ec37f5369a785cf8c5a065a15e323c743 (diff)
[JFFS2] Optimise jffs2_add_tn_to_list
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 and Jarkko Jlavinen for noticing. Signed-off-by: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
-rw-r--r--fs/jffs2/nodelist.c73
-rw-r--r--fs/jffs2/nodelist.h6
-rw-r--r--fs/jffs2/readinode.c36
3 files changed, 88 insertions, 27 deletions
diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c
index 8a8e4b863824..be38cc5c35cd 100644
--- a/fs/jffs2/nodelist.c
+++ b/fs/jffs2/nodelist.c
@@ -7,7 +7,7 @@
7 * 7 *
8 * For licensing information, see the file 'LICENCE' in this directory. 8 * For licensing information, see the file 'LICENCE' in this directory.
9 * 9 *
10 * $Id: nodelist.c,v 1.94 2005/04/13 13:22:35 dwmw2 Exp $ 10 * $Id: nodelist.c,v 1.95 2005/07/05 21:03:07 dwmw2 Exp $
11 * 11 *
12 */ 12 */
13 13
@@ -58,27 +58,61 @@ void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new
58/* Put a new tmp_dnode_info into the list, keeping the list in 58/* Put a new tmp_dnode_info into the list, keeping the list in
59 order of increasing version 59 order of increasing version
60*/ 60*/
61static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct jffs2_tmp_dnode_info **list) 61
62static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct rb_root *list)
62{ 63{
63 struct jffs2_tmp_dnode_info **prev = list; 64 struct rb_node **p = &list->rb_node;
64 65 struct rb_node * parent = NULL;
65 while ((*prev) && (*prev)->version < tn->version) { 66 struct jffs2_tmp_dnode_info *this;
66 prev = &((*prev)->next); 67
67 } 68 while (*p) {
68 tn->next = (*prev); 69 parent = *p;
69 *prev = tn; 70 this = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
71
72 if (tn->version < this->version)
73 p = &(*p)->rb_left;
74 else if (tn->version > this->version)
75 p = &(*p)->rb_right;
76 else if (tn < this)
77 p = &(*p)->rb_left;
78 else
79 p = &(*p)->rb_right;
80 }
81
82 rb_link_node(&tn->rb, parent, p);
83 rb_insert_color(&tn->rb, list);
70} 84}
71 85
72static void jffs2_free_tmp_dnode_info_list(struct jffs2_tmp_dnode_info *tn) 86static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
73{ 87{
74 struct jffs2_tmp_dnode_info *next; 88 struct rb_node *this;
89 struct jffs2_tmp_dnode_info *tn;
90
91 this = list->rb_node;
75 92
76 while (tn) { 93 /* Now at bottom of tree */
77 next = tn; 94 while (this) {
78 tn = tn->next; 95 if (this->rb_left)
79 jffs2_free_full_dnode(next->fn); 96 this = this->rb_left;
80 jffs2_free_tmp_dnode_info(next); 97 else if (this->rb_right)
98 this = this->rb_right;
99 else {
100 tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb);
101 jffs2_free_full_dnode(tn->fn);
102 jffs2_free_tmp_dnode_info(tn);
103
104 this = this->rb_parent;
105 if (!this)
106 break;
107
108 if (this->rb_left == &tn->rb)
109 this->rb_left = NULL;
110 else if (this->rb_right == &tn->rb)
111 this->rb_right = NULL;
112 else BUG();
113 }
81 } 114 }
115 list->rb_node = NULL;
82} 116}
83 117
84static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd) 118static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
@@ -108,12 +142,13 @@ static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_r
108 with this ino, returning the former in order of version */ 142 with this ino, returning the former in order of version */
109 143
110int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f, 144int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
111 struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp, 145 struct rb_root *tnp, struct jffs2_full_dirent **fdp,
112 uint32_t *highest_version, uint32_t *latest_mctime, 146 uint32_t *highest_version, uint32_t *latest_mctime,
113 uint32_t *mctime_ver) 147 uint32_t *mctime_ver)
114{ 148{
115 struct jffs2_raw_node_ref *ref, *valid_ref; 149 struct jffs2_raw_node_ref *ref, *valid_ref;
116 struct jffs2_tmp_dnode_info *tn, *ret_tn = NULL; 150 struct jffs2_tmp_dnode_info *tn;
151 struct rb_root ret_tn = RB_ROOT;
117 struct jffs2_full_dirent *fd, *ret_fd = NULL; 152 struct jffs2_full_dirent *fd, *ret_fd = NULL;
118 union jffs2_node_union node; 153 union jffs2_node_union node;
119 size_t retlen; 154 size_t retlen;
@@ -450,7 +485,7 @@ int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
450 return 0; 485 return 0;
451 486
452 free_out: 487 free_out:
453 jffs2_free_tmp_dnode_info_list(ret_tn); 488 jffs2_free_tmp_dnode_info_list(&ret_tn);
454 jffs2_free_full_dirent_list(ret_fd); 489 jffs2_free_full_dirent_list(ret_fd);
455 return err; 490 return err;
456} 491}
diff --git a/fs/jffs2/nodelist.h b/fs/jffs2/nodelist.h
index a65539f28b06..b34c397909ef 100644
--- a/fs/jffs2/nodelist.h
+++ b/fs/jffs2/nodelist.h
@@ -7,7 +7,7 @@
7 * 7 *
8 * For licensing information, see the file 'LICENCE' in this directory. 8 * For licensing information, see the file 'LICENCE' in this directory.
9 * 9 *
10 * $Id: nodelist.h,v 1.130 2005/04/09 10:46:59 dedekind Exp $ 10 * $Id: nodelist.h,v 1.131 2005/07/05 21:03:07 dwmw2 Exp $
11 * 11 *
12 */ 12 */
13 13
@@ -161,7 +161,7 @@ struct jffs2_full_dnode
161*/ 161*/
162struct jffs2_tmp_dnode_info 162struct jffs2_tmp_dnode_info
163{ 163{
164 struct jffs2_tmp_dnode_info *next; 164 struct rb_node rb;
165 struct jffs2_full_dnode *fn; 165 struct jffs2_full_dnode *fn;
166 uint32_t version; 166 uint32_t version;
167}; 167};
@@ -387,7 +387,7 @@ static inline struct jffs2_node_frag *frag_last(struct rb_root *root)
387D2(void jffs2_print_frag_list(struct jffs2_inode_info *f)); 387D2(void jffs2_print_frag_list(struct jffs2_inode_info *f));
388void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list); 388void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list);
389int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f, 389int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
390 struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp, 390 struct rb_root *tnp, struct jffs2_full_dirent **fdp,
391 uint32_t *highest_version, uint32_t *latest_mctime, 391 uint32_t *highest_version, uint32_t *latest_mctime,
392 uint32_t *mctime_ver); 392 uint32_t *mctime_ver);
393void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state); 393void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state);
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index ef552477c813..081656c1d49e 100644
--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -7,7 +7,7 @@
7 * 7 *
8 * For licensing information, see the file 'LICENCE' in this directory. 8 * For licensing information, see the file 'LICENCE' in this directory.
9 * 9 *
10 * $Id: readinode.c,v 1.119 2005/03/01 10:34:03 dedekind Exp $ 10 * $Id: readinode.c,v 1.120 2005/07/05 21:03:07 dwmw2 Exp $
11 * 11 *
12 */ 12 */
13 13
@@ -500,7 +500,9 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
500 struct jffs2_inode_info *f, 500 struct jffs2_inode_info *f,
501 struct jffs2_raw_inode *latest_node) 501 struct jffs2_raw_inode *latest_node)
502{ 502{
503 struct jffs2_tmp_dnode_info *tn_list, *tn; 503 struct jffs2_tmp_dnode_info *tn = NULL;
504 struct rb_root tn_list;
505 struct rb_node *rb, *repl_rb;
504 struct jffs2_full_dirent *fd_list; 506 struct jffs2_full_dirent *fd_list;
505 struct jffs2_full_dnode *fn = NULL; 507 struct jffs2_full_dnode *fn = NULL;
506 uint32_t crc; 508 uint32_t crc;
@@ -522,9 +524,10 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
522 } 524 }
523 f->dents = fd_list; 525 f->dents = fd_list;
524 526
525 while (tn_list) { 527 rb = rb_first(&tn_list);
526 tn = tn_list;
527 528
529 while (rb) {
530 tn = rb_entry(rb, struct jffs2_tmp_dnode_info, rb);
528 fn = tn->fn; 531 fn = tn->fn;
529 532
530 if (f->metadata) { 533 if (f->metadata) {
@@ -556,7 +559,30 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
556 mdata_ver = tn->version; 559 mdata_ver = tn->version;
557 } 560 }
558 next_tn: 561 next_tn:
559 tn_list = tn->next; 562 BUG_ON(rb->rb_left);
563 repl_rb = NULL;
564 if (rb->rb_parent && rb->rb_parent->rb_left == rb) {
565 /* We were then left-hand child of our parent. We need
566 to move our own right-hand child into our place. */
567 repl_rb = rb->rb_right;
568 if (repl_rb)
569 repl_rb->rb_parent = rb->rb_parent;
570 } else
571 repl_rb = NULL;
572
573 rb = rb_next(rb);
574
575 /* Remove the spent tn from the tree; don't bother rebalancing
576 but put our right-hand child in our own place. */
577 if (tn->rb.rb_parent) {
578 if (tn->rb.rb_parent->rb_left == &tn->rb)
579 tn->rb.rb_parent->rb_left = repl_rb;
580 else if (tn->rb.rb_parent->rb_right == &tn->rb)
581 tn->rb.rb_parent->rb_right = repl_rb;
582 else BUG();
583 } else if (tn->rb.rb_right)
584 tn->rb.rb_right->rb_parent = NULL;
585
560 jffs2_free_tmp_dnode_info(tn); 586 jffs2_free_tmp_dnode_info(tn);
561 } 587 }
562 D1(jffs2_sanitycheck_fragtree(f)); 588 D1(jffs2_sanitycheck_fragtree(f));