mtd/fs/jffs2 build.c,1.38,1.39 file.c,1.77,1.78 gc.c,1.80,1.81 nodelist.c,1.48,1.49 nodelist.h,1.76,1.77 read.c,1.24,1.25 readinode.c,1.75,1.76

Sun Sep 1 11:47:07 EDT 2002

Update of /home/cvs/mtd/fs/jffs2
In directory phoenix.infradead.org:/tmp/cvs-serv1880/fs/jffs2

Modified Files:
	build.c file.c gc.c nodelist.c nodelist.h read.c readinode.c 
Log Message:
Prepare for switching to rbtrees for fragment lists. Introduce 
jffs2_lookup_node_frag(), frag_first() and frag_next() to the generic 
code, with the initial list-based implemention unchanged for now. Add
comment /* RBTREE */ in the places I then need to change when we switch.


Index: build.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/build.c,v
retrieving revision 1.38
retrieving revision 1.39
diff -u -r1.38 -r1.39

--- build.c	23 Aug 2002 12:21:36 -0000	1.38
+++ build.c	1 Sep 2002 15:47:04 -0000	1.39
@@ -178,11 +178,12 @@
 		jffs2_free_tmp_dnode_info(metadata);
 	}
 	metadata = NULL;
-	
+
+	/* RBTREE */
 	while (fraglist) {
 		struct jffs2_node_frag *frag;
 		frag = fraglist;
-		fraglist = fraglist->next;
+		fraglist = fraglist->fnext;
 		
 		if (frag->node && !(--frag->node->frags)) {
 			jffs2_free_full_dnode(frag->node);

Index: file.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/file.c,v
retrieving revision 1.77
retrieving revision 1.78
diff -u -r1.77 -r1.78
--- file.c	20 Aug 2002 21:37:28 -0000	1.77
+++ file.c	1 Sep 2002 15:47:04 -0000	1.78
@@ -202,7 +202,7 @@
 
 	if (ivalid & ATTR_SIZE && inode->i_size > iattr->ia_size) {
 		vmtruncate(inode, iattr->ia_size);
-		jffs2_truncate_fraglist (c, &f->fraglist, iattr->ia_size);
+		jffs2_truncate_fraglist (c, &f->fragtree, iattr->ia_size);
 	}
 
 	if (ivalid & ATTR_SIZE && inode->i_size < iattr->ia_size) {

Index: gc.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/gc.c,v
retrieving revision 1.80
retrieving revision 1.81
diff -u -r1.80 -r1.81
--- gc.c	20 Aug 2002 21:37:28 -0000	1.80
+++ gc.c	1 Sep 2002 15:47:04 -0000	1.81
@@ -200,8 +200,9 @@
 		ret = jffs2_garbage_collect_metadata(c, jeb, f, fn);
 		goto upnout;
 	}
-	
-	for (frag = f->fraglist; frag; frag = frag->next) {
+
+	/* FIXME. Read node and do lookup? */
+	for (frag = frag_first(f->fragtree); frag; frag = frag_next(frag)) {
 		if (frag->node && frag->node->raw == raw) {
 			fn = frag->node;
 			end = frag->ofs + frag->size;
@@ -625,7 +626,8 @@
 		       je32_to_cpu(ri.ino));
 	});
 
-	for (frag = f->fraglist; frag; frag = frag->next) {
+	for (frag = jffs2_lookup_node_frag(f->fragtree, fn->ofs); 
+	     frag; frag = frag_next(frag)) {
 		if (frag->ofs > fn->size + fn->ofs)
 			break;
 		if (frag->node == fn) {

Index: nodelist.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/nodelist.c,v
retrieving revision 1.48
retrieving revision 1.49
diff -u -r1.48 -r1.49
--- nodelist.c	20 Aug 2002 21:37:28 -0000	1.48
+++ nodelist.c	1 Sep 2002 15:47:04 -0000	1.49
@@ -371,3 +371,13 @@
 	}
 }
 	
+struct jffs2_node_frag *jffs2_lookup_node_frag(struct jffs2_node_frag *fragtree, uint32_t offset)
+{
+	struct jffs2_node_frag *frag = fragtree;
+
+	while(frag && frag->ofs + frag->size  <= offset) {
+		D2(printk(KERN_DEBUG "skipping frag %d-%d; before the region we care about\n", frag->ofs, frag->ofs + frag->size));
+		frag = frag_next(frag);
+	}
+	return frag;
+}

Index: nodelist.h
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/nodelist.h,v
retrieving revision 1.76
retrieving revision 1.77
diff -u -r1.76 -r1.77
--- nodelist.h	20 Aug 2002 15:41:28 -0000	1.76
+++ nodelist.h	1 Sep 2002 15:47:04 -0000	1.77
@@ -146,12 +146,15 @@
 */
 struct jffs2_node_frag
 {
-	struct jffs2_node_frag *next;
+	struct jffs2_node_frag *fnext;
 	struct jffs2_full_dnode *node; /* NULL for holes */
 	uint32_t size;
 	uint32_t ofs; /* Don't really need this, but optimisation */
 };
 
+#define frag_next(f) ((f)->fnext)
+#define frag_first(f) (f)
+	
 struct jffs2_eraseblock
 {
 	struct list_head list;
@@ -248,6 +251,7 @@
 void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old);
 void jffs2_free_ino_caches(struct jffs2_sb_info *c);
 void jffs2_free_raw_node_refs(struct jffs2_sb_info *c);
+struct jffs2_node_frag *jffs2_lookup_node_frag(struct jffs2_node_frag *fragtree, uint32_t offset);
 
 /* nodemgmt.c */
 int jffs2_reserve_space(struct jffs2_sb_info *c, uint32_t minsize, uint32_t *ofs, uint32_t *len, int prio);

Index: read.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/read.c,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -r1.24 -r1.25
--- read.c	20 Aug 2002 21:37:28 -0000	1.24
+++ read.c	1 Sep 2002 15:47:04 -0000	1.25
@@ -151,16 +151,14 @@
 			   unsigned char *buf, uint32_t offset, uint32_t len)
 {
 	uint32_t end = offset + len;
-	struct jffs2_node_frag *frag = f->fraglist;
+	struct jffs2_node_frag *frag;
 	int ret;
 
 	D1(printk(KERN_DEBUG "jffs2_read_inode_range: ino #%u, range 0x%08x-0x%08x\n",
 		  f->inocache->ino, offset, offset+len));
 
-	while(frag && frag->ofs + frag->size  <= offset) {
-		D2(printk(KERN_DEBUG "skipping frag %d-%d; before the region we care about\n", frag->ofs, frag->ofs + frag->size));
-		frag = frag->next;
-	}
+	frag = jffs2_lookup_node_frag(f->fragtree, offset);
+
 	/* XXX FIXME: Where a single physical node actually shows up in two
 	   frags, we read it twice. Don't do that. */
 	/* Now we're pointing at the first frag which overlaps our page */
@@ -190,7 +188,7 @@
 			memset(buf, 0, holeend - offset);
 			buf += holeend - offset;
 			offset = holeend;
-			frag = frag->next;
+			frag = frag_next(frag);
 			continue;
 		} else {
 			uint32_t readlen;
@@ -206,7 +204,7 @@
 		}
 		buf += frag->size;
 		offset += frag->size;
-		frag = frag->next;
+		frag = frag_next(frag);
 		D2(printk(KERN_DEBUG "node read was OK. Looping\n"));
 	}
 	return 0;

Index: readinode.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/readinode.c,v
retrieving revision 1.75
retrieving revision 1.76
diff -u -r1.75 -r1.76
--- readinode.c	26 Aug 2002 14:20:48 -0000	1.75
+++ readinode.c	1 Sep 2002 15:47:04 -0000	1.76
@@ -22,14 +22,14 @@
 
 D1(void jffs2_print_frag_list(struct jffs2_inode_info *f)
 {
-	struct jffs2_node_frag *this = f->fraglist;
+	struct jffs2_node_frag *this = frag_first(f->fragtree);
 
 	while(this) {
 		if (this->node)
-			printk(KERN_DEBUG "frag %04x-%04x: 0x%08x on flash (*%p->%p)\n", this->ofs, this->ofs+this->size, this->node->raw->flash_offset &~3, this, this->next);
+			printk(KERN_DEBUG "frag %04x-%04x: 0x%08x on flash (*%p)\n", this->ofs, this->ofs+this->size, this->node->raw->flash_offset &~3, this);
 		else 
-			printk(KERN_DEBUG "frag %04x-%04x: hole (*%p->%p)\n", this->ofs, this->ofs+this->size, this, this->next);
-		this = this->next;
+			printk(KERN_DEBUG "frag %04x-%04x: hole (*%p)\n", this->ofs, this->ofs+this->size, this);
+		this = frag_next(this);
 	}
 	if (f->metadata) {
 		printk(KERN_DEBUG "metadata at 0x%08x\n", f->metadata->raw->flash_offset &~3);
@@ -45,7 +45,7 @@
 	int ret;
 	D1(printk(KERN_DEBUG "jffs2_add_full_dnode_to_inode(ino #%u, f %p, fn %p)\n", f->inocache->ino, f, fn));
 
-	ret = jffs2_add_full_dnode_to_fraglist(c, &f->fraglist, fn);
+	ret = jffs2_add_full_dnode_to_fraglist(c, &f->fragtree, fn);
 
 	D2(jffs2_print_frag_list(f));
 	return ret;
@@ -98,20 +98,21 @@
 		return 0;
 	}
 
+	/* RBTREE */
 	newfrag->ofs = fn->ofs;
 	newfrag->size = fn->size;
 	newfrag->node = fn;
 	newfrag->node->frags = 1;
-	newfrag->next = (void *)0xdeadbeef;
+	newfrag->fnext = (void *)0xdeadbeef;
 
 	/* Skip all the nodes which are completed before this one starts */
 	while(this && fn->ofs >= this->ofs+this->size) {
 		lastend = this->ofs + this->size;
 
-		D2(printk(KERN_DEBUG "j_a_f_d_t_f: skipping frag 0x%04x-0x%04x; phys 0x%08x (*%p->%p)\n", 
-			  this->ofs, this->ofs+this->size, this->node?(this->node->raw->flash_offset &~3):0xffffffff, this, this->next));
-		prev = &this->next;
-		this = this->next;
+		D2(printk(KERN_DEBUG "j_a_f_d_t_f: skipping frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n", 
+			  this->ofs, this->ofs+this->size, this->node?(this->node->raw->flash_offset &~3):0xffffffff, this));
+		prev = &this->fnext;
+		this = this->fnext;
 	}
 
 	/* See if we ran off the end of the list */
@@ -124,18 +125,18 @@
 				return -ENOMEM;
 			holefrag->ofs = lastend;
 			holefrag->size = fn->ofs - lastend;
-			holefrag->next = NULL;
+			holefrag->fnext = NULL;
 			holefrag->node = NULL;
 			*prev = holefrag;
-			prev = &holefrag->next;
+			prev = &holefrag->fnext;
 		}
-		newfrag->next = NULL;
+		newfrag->fnext = NULL;
 		*prev = newfrag;
 		return 0;
 	}
 
-	D2(printk(KERN_DEBUG "j_a_f_d_t_f: dealing with frag 0x%04x-0x%04x; phys 0x%08x (*%p->%p)\n", 
-		  this->ofs, this->ofs+this->size, this->node?(this->node->raw->flash_offset &~3):0xffffffff, this, this->next));
+	D2(printk(KERN_DEBUG "j_a_f_d_t_f: dealing with frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n", 
+		  this->ofs, this->ofs+this->size, this->node?(this->node->raw->flash_offset &~3):0xffffffff, this));
 
 	/* OK. 'this' is pointing at the first frag that fn->ofs at least partially obsoletes,
 	 * - i.e. fn->ofs < this->ofs+this->size && fn->ofs >= this->ofs  
@@ -157,37 +158,37 @@
 			   )
 			newfrag2->ofs = fn->ofs + fn->size;
 			newfrag2->size = (this->ofs+this->size) - newfrag2->ofs;
-			newfrag2->next = this->next;
+			newfrag2->fnext = this->fnext;
 			newfrag2->node = this->node;
 			if (this->node)
 				this->node->frags++;
-			newfrag->next = newfrag2;
-			this->next = newfrag;
+			newfrag->fnext = newfrag2;
+			this->fnext = newfrag;
 			this->size = newfrag->ofs - this->ofs;
 			return 0;
 		}
 		/* New node just reduces 'this' frag in size, doesn't split it */
 		this->size = fn->ofs - this->ofs;
-		newfrag->next = this->next;
-		this->next = newfrag;
-		this = newfrag->next;
+		newfrag->fnext = this->fnext;
+		this->fnext = newfrag;
+		this = newfrag->fnext;
 	} else {
 		D2(printk(KERN_DEBUG "Inserting newfrag (*%p) in before 'this' (*%p)\n", newfrag, this));
 		*prev = newfrag;
-	        newfrag->next = this;
+	        newfrag->fnext = this;
 	}
 	/* OK, now we have newfrag added in the correct place in the list, but
-	   newfrag->next points to a fragment which may be overlapping it
+	   newfrag->fnext points to a fragment which may be overlapping it
 	*/
 	while (this && newfrag->ofs + newfrag->size >= this->ofs + this->size) {
 		/* 'this' frag is obsoleted. */
 		old = this;
-		this = old->next;
+		this = old->fnext;
 		jffs2_obsolete_node_frag(c, old);
 	}
 	/* Now we're pointing at the first frag which isn't totally obsoleted by 
 	   the new frag */
-	newfrag->next = this;
+	newfrag->fnext = this;
 
 	if (!this || newfrag->ofs + newfrag->size == this->ofs) {
 		return 0;
@@ -205,7 +206,7 @@
 	while (*list) {
 		if ((*list)->ofs >= size) {
 			struct jffs2_node_frag *this = *list;
-			*list = this->next;
+			*list = this->fnext;
 			D1(printk(KERN_DEBUG "Removing frag 0x%08x-0x%08x\n", this->ofs, this->ofs+this->size));
 			jffs2_obsolete_node_frag(c, this);
 			continue;
@@ -213,7 +214,7 @@
 			D1(printk(KERN_DEBUG "Truncating frag 0x%08x-0x%08x\n", (*list)->ofs, (*list)->ofs + (*list)->size));
 			(*list)->size = size - (*list)->ofs;
 		}
-		list = &(*list)->next;
+		list = &(*list)->fnext;
 	}
 }
 
@@ -338,7 +339,7 @@
 			
 	case S_IFREG:
 		/* If it was a regular file, truncate it to the latest node's isize */
-		jffs2_truncate_fraglist(c, &f->fraglist, je32_to_cpu(latest_node->isize));
+		jffs2_truncate_fraglist(c, &f->fragtree, je32_to_cpu(latest_node->isize));
 		break;
 
 	case S_IFLNK:
@@ -360,14 +361,14 @@
 			jffs2_do_clear_inode(c, f);
 			return -EIO;
 		}
-		if (!f->fraglist) {
+		if (!frag_first(f->fragtree)) {
 			printk(KERN_WARNING "Argh. Special inode #%u with mode 0%o has no fragments\n", ino, je32_to_cpu(latest_node->mode));
 			up(&f->sem);
 			jffs2_do_clear_inode(c, f);
 			return -EIO;
 		}
 		/* ASSERT: f->fraglist != NULL */
-		if (f->fraglist->next) {
+		if (frag_next(frag_first(f->fragtree))) {
 			printk(KERN_WARNING "Argh. Special inode #%u with mode 0%o had more than one node\n", ino, je32_to_cpu(latest_node->mode));
 			/* FIXME: Deal with it - check crc32, check for duplicate node, check times and discard the older one */
 			up(&f->sem);
@@ -375,9 +376,9 @@
 			return -EIO;
 		}
 		/* OK. We're happy */
-		f->metadata = f->fraglist->node;
-		jffs2_free_node_frag(f->fraglist);
-		f->fraglist = NULL;
+		f->metadata = frag_first(f->fragtree)->node;
+		jffs2_free_node_frag(frag_first(f->fragtree));
+		f->fragtree = NULL;
 		break;
 	}
 
@@ -398,17 +399,18 @@
 
 	down(&f->sem);
 
-	frags = f->fraglist;
-	fds = f->dents;
 	if (f->metadata) {
 		if (f->inocache && !f->inocache->nlink)
 			jffs2_mark_node_obsolete(c, f->metadata->raw);
 		jffs2_free_full_dnode(f->metadata);
 	}
 
+	/* RBTREE */
+	frags = frag_first(f->fragtree);
+
 	while (frags) {
 		frag = frags;
-		frags = frag->next;
+		frags = frag_next(frag);
 		D2(printk(KERN_DEBUG "jffs2_do_clear_inode: frag at 0x%x-0x%x: node %p, frags %d--\n", frag->ofs, frag->ofs+frag->size, frag->node, frag->node?frag->node->frags:0));
 
 		if (frag->node && !(--frag->node->frags)) {
@@ -420,6 +422,9 @@
 		}
 		jffs2_free_node_frag(frag);
 	}
+
+	fds = f->dents;
+
 	while(fds) {
 		fd = fds;
 		fds = fd->next;



