From 8fabed4a0f78623236c035de0984beeacb8096d8 Mon Sep 17 00:00:00 2001
From: Todd Poynor <tpoynor@mvista.com>
Date: Wed, 19 Jan 2005 19:22:04 +0000
Subject: [JFFS2] Avoid warning for empty filesystems

Avoid "Eep. No valid nodes for ino #1" message for just-created filesystem.

Signed-off-by: Todd Poynor <tpoynor@mvista.com>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 fs/jffs2/nodelist.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'fs/jffs2/nodelist.c')

diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c
index cd6a8bd13e0b..3c6d93c8ea0a 100644
--- a/fs/jffs2/nodelist.c
+++ b/fs/jffs2/nodelist.c
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: nodelist.c,v 1.90 2004/12/08 17:59:20 dwmw2 Exp $
+ * $Id: nodelist.c,v 1.92 2005/01/19 19:22:00 tpoynor Exp $
  *
  */
 
@@ -127,7 +127,7 @@ int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
 
 	valid_ref = jffs2_first_valid_node(f->inocache->nodes);
 
-	if (!valid_ref)
+	if (!valid_ref && (f->inocache->ino != 1))
 		printk(KERN_WARNING "Eep. No valid nodes for ino #%u\n", f->inocache->ino);
 
 	while (valid_ref) {
-- 
cgit v1.2.3


From 67e345d17ff8c2085a54c293001ae548f7be7b21 Mon Sep 17 00:00:00 2001
From: David Woodhouse <dwmw2@infradead.org>
Date: Sun, 27 Feb 2005 23:01:36 +0000
Subject: [JFFS2] Prevent ino cache removal for inodes in use

Don't remove inocache for inodes which are in read_inode() or
clear_inode() until they're done.

Signed-off-by: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 fs/jffs2/erase.c     |  7 ++-----
 fs/jffs2/nodelist.c  | 13 ++++++++++---
 fs/jffs2/nodelist.h  |  3 ++-
 fs/jffs2/nodemgmt.c  |  7 ++-----
 fs/jffs2/readinode.c | 10 ++++++++--
 5 files changed, 24 insertions(+), 16 deletions(-)

(limited to 'fs/jffs2/nodelist.c')

diff --git a/fs/jffs2/erase.c b/fs/jffs2/erase.c
index a3c6cc150497..d1ae565352a6 100644
--- a/fs/jffs2/erase.c
+++ b/fs/jffs2/erase.c
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: erase.c,v 1.71 2005/02/09 09:17:40 pavlov Exp $
+ * $Id: erase.c,v 1.72 2005/02/27 23:01:32 dwmw2 Exp $
  *
  */
 
@@ -277,11 +277,8 @@ static inline void jffs2_remove_node_refs_from_ino_list(struct jffs2_sb_info *c,
 		printk("\n");
 	});
 
-	if (ic->nodes == (void *)ic) {
-		D1(printk(KERN_DEBUG "inocache for ino #%u is all gone now. Freeing\n", ic->ino));
+	if (ic->nodes == (void *)ic)
 		jffs2_del_ino_cache(c, ic);
-		jffs2_free_inode_cache(ic);
-	}
 }
 
 static void jffs2_free_all_node_refs(struct jffs2_sb_info *c, struct jffs2_eraseblock *jeb)
diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c
index 3c6d93c8ea0a..b835a8652623 100644
--- a/fs/jffs2/nodelist.c
+++ b/fs/jffs2/nodelist.c
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: nodelist.c,v 1.92 2005/01/19 19:22:00 tpoynor Exp $
+ * $Id: nodelist.c,v 1.93 2005/02/27 23:01:32 dwmw2 Exp $
  *
  */
 
@@ -506,7 +506,7 @@ void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new
 void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
 {
 	struct jffs2_inode_cache **prev;
-	D2(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino));
+	D1(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino));
 	spin_lock(&c->inocache_lock);
 	
 	prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
@@ -518,6 +518,14 @@ void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
 		*prev = old->next;
 	}
 
+	/* Free it now unless it's in READING or CLEARING state, which
+	   are the transitions upon read_inode() and clear_inode(). The
+	   rest of the time we know nobody else is looking at it, and 
+	   if it's held by read_inode() or clear_inode() they'll free it
+	   for themselves. */
+	if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)
+		jffs2_free_inode_cache(old);
+
 	spin_unlock(&c->inocache_lock);
 }
 
@@ -530,7 +538,6 @@ void jffs2_free_ino_caches(struct jffs2_sb_info *c)
 		this = c->inocache_list[i];
 		while (this) {
 			next = this->next;
-			D2(printk(KERN_DEBUG "jffs2_free_ino_caches: Freeing ino #%u at %p\n", this->ino, this));
 			jffs2_free_inode_cache(this);
 			this = next;
 		}
diff --git a/fs/jffs2/nodelist.h b/fs/jffs2/nodelist.h
index 8c122838bf6d..57f675c2c97f 100644
--- a/fs/jffs2/nodelist.h
+++ b/fs/jffs2/nodelist.h
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: nodelist.h,v 1.127 2005/02/09 09:23:53 pavlov Exp $
+ * $Id: nodelist.h,v 1.128 2005/02/27 23:01:32 dwmw2 Exp $
  *
  */
 
@@ -135,6 +135,7 @@ struct jffs2_inode_cache {
 #define INO_STATE_CHECKEDABSENT	3	/* Checked, cleared again */
 #define INO_STATE_GC		4	/* GCing a 'pristine' node */
 #define INO_STATE_READING	5	/* In read_inode() */
+#define INO_STATE_CLEARING	6	/* In clear_inode() */
 
 #define INOCACHE_HASHSIZE 128
 
diff --git a/fs/jffs2/nodemgmt.c b/fs/jffs2/nodemgmt.c
index 5e1e8caf54e8..f9dcac1415ac 100644
--- a/fs/jffs2/nodemgmt.c
+++ b/fs/jffs2/nodemgmt.c
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: nodemgmt.c,v 1.117 2005/01/25 20:11:11 hammache Exp $
+ * $Id: nodemgmt.c,v 1.118 2005/02/27 23:01:32 dwmw2 Exp $
  *
  */
 
@@ -593,11 +593,8 @@ void jffs2_mark_node_obsolete(struct jffs2_sb_info *c, struct jffs2_raw_node_ref
 		*p = ref->next_in_ino;
 		ref->next_in_ino = NULL;
 
-		if (ic->nodes == (void *)ic) {
-			D1(printk(KERN_DEBUG "inocache for ino #%u is all gone now. Freeing\n", ic->ino));
+		if (ic->nodes == (void *)ic)
 			jffs2_del_ino_cache(c, ic);
-			jffs2_free_inode_cache(ic);
-		}
 
 		spin_unlock(&c->erase_completion_lock);
 	}
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index aca4a0b17bcd..a1980a9da531 100644
--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: readinode.c,v 1.117 2004/11/20 18:06:54 dwmw2 Exp $
+ * $Id: readinode.c,v 1.118 2005/02/27 23:01:33 dwmw2 Exp $
  *
  */
 
@@ -672,6 +672,9 @@ void jffs2_do_clear_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f)
 	down(&f->sem);
 	deleted = f->inocache && !f->inocache->nlink;
 
+	if (f->inocache && f->inocache->state != INO_STATE_CHECKING)
+		jffs2_set_inocache_state(c, f->inocache, INO_STATE_CLEARING);
+
 	if (f->metadata) {
 		if (deleted)
 			jffs2_mark_node_obsolete(c, f->metadata->raw);
@@ -688,8 +691,11 @@ void jffs2_do_clear_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f)
 		jffs2_free_full_dirent(fd);
 	}
 
-	if (f->inocache && f->inocache->state != INO_STATE_CHECKING)
+	if (f->inocache && f->inocache->state != INO_STATE_CHECKING) {
 		jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
+		if (f->inocache->nodes == (void *)f->inocache)
+			jffs2_del_ino_cache(c, f->inocache);
+	}
 
 	up(&f->sem);
 }
-- 
cgit v1.2.3


From 7d200960d4f3d1b50c3b9e9688408d9f81c66ff4 Mon Sep 17 00:00:00 2001
From: David Woodhouse <dwmw2@infradead.org>
Date: Wed, 13 Apr 2005 14:22:38 +0100
Subject: [JFFS2] Fix inode allocation race

Signed-off-by: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 fs/jffs2/README.Locking | 6 +++++-
 fs/jffs2/nodelist.c     | 6 +++++-
 fs/jffs2/write.c        | 7 +++----
 3 files changed, 13 insertions(+), 6 deletions(-)

(limited to 'fs/jffs2/nodelist.c')

diff --git a/fs/jffs2/README.Locking b/fs/jffs2/README.Locking
index 49771cf8513a..b7943439b6ec 100644
--- a/fs/jffs2/README.Locking
+++ b/fs/jffs2/README.Locking
@@ -1,4 +1,4 @@
-	$Id: README.Locking,v 1.9 2004/11/20 10:35:40 dwmw2 Exp $
+	$Id: README.Locking,v 1.12 2005/04/13 13:22:35 dwmw2 Exp $
 
 	JFFS2 LOCKING DOCUMENTATION
 	---------------------------
@@ -108,6 +108,10 @@ in-core jffs2_inode_cache objects (each inode in JFFS2 has the
 correspondent jffs2_inode_cache object). So, the inocache_lock
 has to be locked while walking the c->inocache_list hash buckets.
 
+This spinlock also covers allocation of new inode numbers, which is
+currently just '++->highest_ino++', but might one day get more complicated
+if we need to deal with wrapping after 4 milliard inode numbers are used.
+
 Note, the f->sem guarantees that the correspondent jffs2_inode_cache
 will not be removed. So, it is allowed to access it without locking
 the inocache_lock spinlock. 
diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c
index b835a8652623..c9157e1ea40a 100644
--- a/fs/jffs2/nodelist.c
+++ b/fs/jffs2/nodelist.c
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: nodelist.c,v 1.93 2005/02/27 23:01:32 dwmw2 Exp $
+ * $Id: nodelist.c,v 1.94 2005/04/13 13:22:35 dwmw2 Exp $
  *
  */
 
@@ -491,6 +491,10 @@ void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new
 	struct jffs2_inode_cache **prev;
 	D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
 	spin_lock(&c->inocache_lock);
+ 	if (!new->ino)
+ 		new->ino = ++c->highest_ino;
+ 
+ 	D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
 	
 	prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
 
diff --git a/fs/jffs2/write.c b/fs/jffs2/write.c
index f3910dc1c2c8..69100615d9ae 100644
--- a/fs/jffs2/write.c
+++ b/fs/jffs2/write.c
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: write.c,v 1.91 2005/03/01 10:34:03 dedekind Exp $
+ * $Id: write.c,v 1.92 2005/04/13 13:22:35 dwmw2 Exp $
  *
  */
 
@@ -35,13 +35,12 @@ int jffs2_do_new_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, uint
 	f->inocache = ic;
 	f->inocache->nlink = 1;
 	f->inocache->nodes = (struct jffs2_raw_node_ref *)f->inocache;
-	f->inocache->ino = ++c->highest_ino;
 	f->inocache->state = INO_STATE_PRESENT;
 
-	ri->ino = cpu_to_je32(f->inocache->ino);
 
-	D1(printk(KERN_DEBUG "jffs2_do_new_inode(): Assigned ino# %d\n", f->inocache->ino));
 	jffs2_add_ino_cache(c, f->inocache);
+	D1(printk(KERN_DEBUG "jffs2_do_new_inode(): Assigned ino# %d\n", f->inocache->ino));
+	ri->ino = cpu_to_je32(f->inocache->ino);
 
 	ri->magic = cpu_to_je16(JFFS2_MAGIC_BITMASK);
 	ri->nodetype = cpu_to_je16(JFFS2_NODETYPE_INODE);
-- 
cgit v1.2.3


From 7d27c8143c8234e1cae8285fd2d43c19dad69bde Mon Sep 17 00:00:00 2001
From: Thomas Gleixner <tglx@tglx.tec.linutronix.de>
Date: Sun, 22 May 2005 21:47:19 +0200
Subject: [JFFS2] Whitespace cleanup. Fix missing debug message

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 fs/jffs2/erase.c    |  1 +
 fs/jffs2/nodelist.c | 12 ++++++------
 2 files changed, 7 insertions(+), 6 deletions(-)

(limited to 'fs/jffs2/nodelist.c')

diff --git a/fs/jffs2/erase.c b/fs/jffs2/erase.c
index 088faadf8f38..6a4c0a3685da 100644
--- a/fs/jffs2/erase.c
+++ b/fs/jffs2/erase.c
@@ -48,6 +48,7 @@ static void jffs2_erase_block(struct jffs2_sb_info *c,
 #else /* Linux */
 	struct erase_info *instr;
 
+	D1(printk(KERN_DEBUG "jffs2_erase_block(): erase block %#x (range %#x-%#x)\n", jeb->offset, jeb->offset, jeb->offset + c->sector_size));
 	instr = kmalloc(sizeof(struct erase_info) + sizeof(struct erase_priv_struct), GFP_KERNEL);
 	if (!instr) {
 		printk(KERN_WARNING "kmalloc for struct erase_info in jffs2_erase_block failed. Refiling block for later\n");
diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c
index c9157e1ea40a..8a8e4b863824 100644
--- a/fs/jffs2/nodelist.c
+++ b/fs/jffs2/nodelist.c
@@ -489,13 +489,13 @@ struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t
 void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
 {
 	struct jffs2_inode_cache **prev;
-	D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
+
 	spin_lock(&c->inocache_lock);
- 	if (!new->ino)
- 		new->ino = ++c->highest_ino;
- 
- 	D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
-	
+	if (!new->ino)
+		new->ino = ++c->highest_ino;
+
+	D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
+
 	prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
 
 	while ((*prev) && (*prev)->ino < new->ino) {
-- 
cgit v1.2.3


From 9dee7503ce3fc38911b9873216619190cf688128 Mon Sep 17 00:00:00 2001
From: David Woodhouse <dwmw2@infradead.org>
Date: Tue, 5 Jul 2005 22:03:10 +0100
Subject: [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>
---
 fs/jffs2/nodelist.c  | 73 ++++++++++++++++++++++++++++++++++++++--------------
 fs/jffs2/nodelist.h  |  6 ++---
 fs/jffs2/readinode.c | 36 ++++++++++++++++++++++----
 3 files changed, 88 insertions(+), 27 deletions(-)

(limited to 'fs/jffs2/nodelist.c')

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 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: nodelist.c,v 1.94 2005/04/13 13:22:35 dwmw2 Exp $
+ * $Id: nodelist.c,v 1.95 2005/07/05 21:03:07 dwmw2 Exp $
  *
  */
 
@@ -58,27 +58,61 @@ void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new
 /* 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)
+
+static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct rb_root *list)
 {
-	struct jffs2_tmp_dnode_info **prev = list;
-	
-	while ((*prev) && (*prev)->version < tn->version) {
-		prev = &((*prev)->next);
-	}
-	tn->next = (*prev);
-        *prev = tn;
+	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 jffs2_tmp_dnode_info *tn)
+static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
 {
-	struct jffs2_tmp_dnode_info *next;
+	struct rb_node *this;
+	struct jffs2_tmp_dnode_info *tn;
+
+	this = list->rb_node;
 
-	while (tn) {
-		next = tn;
-		tn = tn->next;
-		jffs2_free_full_dnode(next->fn);
-		jffs2_free_tmp_dnode_info(next);
+	/* 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;
+
+			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 @@ static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_r
    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 @@ int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
 	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;
 }
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 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: nodelist.h,v 1.130 2005/04/09 10:46:59 dedekind Exp $
+ * $Id: nodelist.h,v 1.131 2005/07/05 21:03:07 dwmw2 Exp $
  *
  */
 
@@ -161,7 +161,7 @@ struct jffs2_full_dnode
 */
 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 @@ static inline struct jffs2_node_frag *frag_last(struct rb_root *root)
 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);
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 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: readinode.c,v 1.119 2005/03/01 10:34:03 dedekind Exp $
+ * $Id: readinode.c,v 1.120 2005/07/05 21:03:07 dwmw2 Exp $
  *
  */
 
@@ -500,7 +500,9 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
 					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 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
 	}
 	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 @@ static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
 			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));
-- 
cgit v1.2.3


From 6430a8def12edebc1c9c7c2621d33ca0e8653c33 Mon Sep 17 00:00:00 2001
From: "Artem B. Bityuckiy" <dedekind@infradead.org>
Date: Wed, 6 Jul 2005 15:43:18 +0100
Subject: [JFFS2] Simplify the tree insert code.

It isn't _normal_ that we allow key collision in rbtrees,
but it does not matter as long as the two nodes with the same
version are together.

Signed-off-by: Artem B. Bityuckiy <dedekind@infradead.org>
Signed-off-by: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 fs/jffs2/nodelist.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

(limited to 'fs/jffs2/nodelist.c')

diff --git a/fs/jffs2/nodelist.c b/fs/jffs2/nodelist.c
index be38cc5c35cd..c7bbdeec93a6 100644
--- a/fs/jffs2/nodelist.c
+++ b/fs/jffs2/nodelist.c
@@ -7,7 +7,7 @@
  *
  * For licensing information, see the file 'LICENCE' in this directory.
  *
- * $Id: nodelist.c,v 1.95 2005/07/05 21:03:07 dwmw2 Exp $
+ * $Id: nodelist.c,v 1.97 2005/07/06 15:18:41 dwmw2 Exp $
  *
  */
 
@@ -69,12 +69,11 @@ static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct rb_root
 		parent = *p;
 		this = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
 
+		/* There may actually be a collision here, but it doesn't
+		   actually matter. As long as the two nodes with the same
+		   version are together, it's all fine. */
 		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;
         }
-- 
cgit v1.2.3