mtd/fs/jffs2 GNUmakefile,1.5,1.6 nodelist.c,1.50,1.51 nodelist.h,1.78,1.79 readinode.c,1.77,1.78
David Woodhouse
dwmw2 at infradead.org
Tue Sep 3 12:38:26 EDT 2002
Update of /home/cvs/mtd/fs/jffs2
In directory phoenix.infradead.org:/tmp/cvs-serv16115
Modified Files:
GNUmakefile nodelist.c nodelist.h readinode.c
Log Message:
Many rbtree fixes. Still not bugfree.
Index: GNUmakefile
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/GNUmakefile,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- GNUmakefile 20 May 2002 14:55:34 -0000 1.5
+++ GNUmakefile 3 Sep 2002 16:38:24 -0000 1.6
@@ -31,7 +31,7 @@
CC += -I$(shell pwd)/../../include
CONFIG_JFFS2_FS := m
-EXTRA_CFLAGS += -DCONFIG_JFFS2_FS_DEBUG=1 -g
+EXTRA_CFLAGS += -DCONFIG_JFFS2_FS_DEBUG=1 -g -Werror
ifeq ($(CONFIG_JFFS2_FS_NAND),y)
EXTRA_CFLAGS += -DCONFIG_JFFS2_FS_NAND=1
Index: nodelist.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/nodelist.c,v
retrieving revision 1.50
retrieving revision 1.51
diff -u -r1.50 -r1.51
--- nodelist.c 3 Sep 2002 00:08:51 -0000 1.50
+++ nodelist.c 3 Sep 2002 16:38:24 -0000 1.51
@@ -376,18 +376,25 @@
{
/* The common case in lookup is that there will be a node
which precisely matches. So we go looking for that first */
- rb_node_t *next = &(frag_first(fragtree))->rb;
- struct jffs2_node_frag *ret;
- struct jffs2_node_frag *frag;
+ rb_node_t *next;
+ struct jffs2_node_frag *prev = NULL;
+ struct jffs2_node_frag *frag = NULL;
+
+ D1(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset));
- D1(printk(KERN_DEBUG "jffs2_lookup_node_frag(%d)\n", offset));
+ next = fragtree->rb_node;
- do {
+ while(next) {
frag = rb_entry(next, struct jffs2_node_frag, rb);
+ D1(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n",
+ frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right));
if (frag->ofs + frag->size <= offset) {
D1(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n",
frag->ofs, frag->ofs+frag->size));
+ /* Remember the closest smaller match on the way down */
+ if (!prev || frag->ofs > prev->ofs)
+ prev = frag;
next = frag->rb.rb_right;
} else if (frag->ofs > offset) {
D1(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n",
@@ -398,47 +405,62 @@
frag->ofs, frag->ofs+frag->size));
return frag;
}
- } while(next);
+ }
/* Exact match not found. Go back up looking at each parent,
and return the closest smaller one */
- D1(printk(KERN_DEBUG "No match. Looking for closest previous frag\n"));
-
+ if (prev)
+ D1(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n",
+ prev->ofs, prev->ofs+prev->size));
+ else
+ D1(printk(KERN_DEBUG "Returning NULL, empty fragtree\n"));
+
+ return prev;
+#if 0
ret = frag;
while (frag) {
- D1(printk(KERN_DEBUG "Considering frag %d-%d.\n",
- frag->ofs, frag->ofs+frag->size));
+ D1(printk(KERN_DEBUG "Considering frag %d-%d (%p) as closest previous.\n",
+ frag->ofs, frag->ofs+frag->size, frag));
if (frag->ofs < offset && frag->ofs > ret->ofs)
ret = frag;
frag = frag_parent(frag);
}
- D1(printk(KERN_DEBUG "Returning frag %d,%d, closest previous\n",
- frag->ofs, frag->ofs+frag->size));
+
return ret;
+#endif
}
/* Pass 'c' argument to indicate that nodes should be marked obsolete as
they're killed. */
void jffs2_kill_fragtree(rb_root_t *root, struct jffs2_sb_info *c)
{
- struct jffs2_node_frag *frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
+ struct jffs2_node_frag *frag;
struct jffs2_node_frag *parent;
+ if (!root->rb_node)
+ return;
+
+ frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
+
while(frag) {
- if (frag_left(frag)) {
+ if (frag->rb.rb_left) {
+ D1(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n",
+ frag, frag->ofs, frag->ofs+frag->size));
frag = frag_left(frag);
continue;
}
- if (frag_right(frag)) {
+ if (frag->rb.rb_right) {
+ D1(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n",
+ frag, frag->ofs, frag->ofs+frag->size));
frag = frag_right(frag);
continue;
}
- D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n",
+ D1(printk(KERN_DEBUG "jffs2_kill_fragtree: 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));
@@ -451,10 +473,12 @@
jffs2_free_full_dnode(frag->node);
}
parent = frag_parent(frag);
- if (frag_left(parent) == frag)
- parent->rb.rb_left = NULL;
- else
- parent->rb.rb_right = NULL;
+ if (parent) {
+ if (frag_left(parent) == frag)
+ parent->rb.rb_left = NULL;
+ else
+ parent->rb.rb_right = NULL;
+ }
jffs2_free_node_frag(frag);
frag = parent;
@@ -466,13 +490,17 @@
rb_node_t *parent = &base->rb;
rb_node_t **link = &parent;
+ D1(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag,
+ newfrag->ofs, newfrag->ofs+newfrag->size, base));
+
while (*link) {
parent = *link;
base = rb_entry(parent, struct jffs2_node_frag, rb);
+ D1(printk(KERN_DEBUG "fragtree_insert considering frag at %d\n", base->ofs));
if (newfrag->ofs > base->ofs)
link = &base->rb.rb_right;
- else if (newfrag->ofs > base->ofs)
+ else if (newfrag->ofs < base->ofs)
link = &base->rb.rb_left;
else {
printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
Index: nodelist.h
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/nodelist.h,v
retrieving revision 1.78
retrieving revision 1.79
diff -u -r1.78 -r1.79
--- nodelist.h 3 Sep 2002 00:08:51 -0000 1.78
+++ nodelist.h 3 Sep 2002 16:38:24 -0000 1.79
@@ -248,8 +248,8 @@
#define rb_parent(rb) ((rb)->rb_parent)
#define frag_next(frag) rb_entry(rb_next(&(frag)->rb), struct jffs2_node_frag, rb)
#define frag_parent(frag) rb_entry(rb_parent(&(frag)->rb), struct jffs2_node_frag, rb)
-#define frag_left(frag) rb_entry(&(frag)->rb.rb_left, struct jffs2_node_frag, rb)
-#define frag_right(frag) rb_entry(&(frag)->rb.rb_right, struct jffs2_node_frag, rb)
+#define frag_left(frag) rb_entry((frag)->rb.rb_left, struct jffs2_node_frag, rb)
+#define frag_right(frag) rb_entry((frag)->rb.rb_right, struct jffs2_node_frag, rb)
#define frag_erase(frag, list) rb_erase(&frag->rb, list);
/* nodelist.c */
Index: readinode.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/readinode.c,v
retrieving revision 1.77
retrieving revision 1.78
diff -u -r1.77 -r1.78
--- readinode.c 3 Sep 2002 00:08:52 -0000 1.77
+++ readinode.c 3 Sep 2002 16:38:24 -0000 1.78
@@ -20,9 +20,9 @@
#include "nodelist.h"
-D1(void jffs2_print_frag_list(struct jffs2_inode_info *f)
+D1(static void jffs2_print_fragtree(rb_root_t *list)
{
- struct jffs2_node_frag *this = frag_first(&f->fragtree);
+ struct jffs2_node_frag *this = frag_first(list);
while(this) {
if (this->node)
@@ -31,6 +31,11 @@
printk(KERN_DEBUG "frag %04x-%04x: hole (*%p)\n", this->ofs, this->ofs+this->size, this);
this = frag_next(this);
}
+})
+D1(void jffs2_print_frag_list(struct jffs2_inode_info *f)
+{
+ jffs2_print_fragtree(&f->fragtree);
+
if (f->metadata) {
printk(KERN_DEBUG "metadata at 0x%08x\n", f->metadata->raw->flash_offset &~3);
}
@@ -47,7 +52,7 @@
ret = jffs2_add_full_dnode_to_fraglist(c, &f->fragtree, fn);
- D2(jffs2_print_frag_list(f));
+ D1(jffs2_print_frag_list(f));
return ret;
}
@@ -76,7 +81,7 @@
{
struct jffs2_node_frag *this;
struct jffs2_node_frag *newfrag;
- uint32_t lastend = 0;
+ uint32_t lastend;
newfrag = jffs2_alloc_node_frag();
if (!newfrag) {
@@ -101,12 +106,15 @@
/* Skip all the nodes which are completed before this one starts */
this = jffs2_lookup_node_frag(list, fn->ofs);
- D1(printk(KERN_DEBUG "j_a_f_d_t_f: Lookup gave 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));
-
-
- lastend = this->ofs + this->size;
-
+ if (this) {
+ D1(printk(KERN_DEBUG "j_a_f_d_t_f: Lookup gave 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));
+ lastend = this->ofs + this->size;
+ } else {
+ D1(printk(KERN_DEBUG "j_a_f_d_t_f: Lookup gave no frag\n"));
+ lastend = 0;
+ }
+
/* See if we ran off the end of the list */
if (lastend <= newfrag->ofs) {
/* We did */
@@ -118,20 +126,34 @@
holefrag->ofs = lastend;
holefrag->size = fn->ofs - lastend;
holefrag->node = NULL;
- /* By definition, the 'this' node has no right-hand child.
- And that's where we want to put the hole */
- rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right);
+ if (this) {
+ /* By definition, the 'this' node has no right-hand child,
+ because there are no frags with offset greater than it.
+ So that's where we want to put the hole */
+ D1(printk(KERN_DEBUG "Adding hole frag (%p) on right of node at (%p)\n", holefrag, this));
+ rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right);
+ } else {
+ D1(printk(KERN_DEBUG "Adding hole frag (%p) at root of tree\n", holefrag));
+ rb_link_node(&holefrag->rb, NULL, &list->rb_node);
+ }
rb_insert_color(&holefrag->rb, list);
this = holefrag;
}
- /* By definition, the 'this' node has no right-hand child.
- And that's where we want to put the new node */
- rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
+ if (this) {
+ /* By definition, the 'this' node has no right-hand child,
+ because there are no frags with offset greater than it.
+ So that's where we want to put the hole */
+ D1(printk(KERN_DEBUG "Adding new frag (%p) on right of node at (%p)\n", newfrag, this));
+ rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
+ } else {
+ D1(printk(KERN_DEBUG "Adding new frag (%p) at root of tree\n", newfrag));
+ rb_link_node(&newfrag->rb, NULL, &list->rb_node);
+ }
rb_insert_color(&newfrag->rb, list);
return 0;
}
- D2(printk(KERN_DEBUG "j_a_f_d_t_f: dealing with frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
+ D1(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 newfrag->ofs at least partially obsoletes,
@@ -152,24 +174,34 @@
else
printk("hole\n");
)
- /* Adjust size of original 'this' */
- this->size = newfrag->ofs - this->ofs;
- /* New second frag pointing to 'this's node */
+ /* New second frag pointing to this's node */
newfrag2->ofs = newfrag->ofs + newfrag->size;
newfrag2->size = (this->ofs+this->size) - newfrag2->ofs;
newfrag2->node = this->node;
if (this->node)
this->node->frags++;
- /* Now, we know there's no node with offset greater than newfrag2->ofs, for
- obvious reasons. So we can do a tree insert from this to insert newfrag,
- and a tree insert from newfrag to insert newfrag2. */
+ /* Adjust size of original 'this' */
+ this->size = newfrag->ofs - this->ofs;
+ printk("After munging of existing nodes:\n");
+ D1(jffs2_print_fragtree(list));
+
+ /* Now, we know there's no node with offset
+ greater than this->ofs but smaller than
+ newfrag2->ofs or newfrag->ofs, for obvious
+ reasons. So we can do a tree insert from
+ 'this' to insert newfrag, and a tree insert
+ from newfrag to insert newfrag2. */
jffs2_fragtree_insert(newfrag, this);
rb_insert_color(&newfrag->rb, list);
+ printk("After inserting newfrag:\n");
+ D1(jffs2_print_fragtree(list));
- jffs2_fragtree_insert(newfrag2, this);
+ jffs2_fragtree_insert(newfrag2, newfrag);
rb_insert_color(&newfrag2->rb, list);
+ printk("After inserting newfrag2:\n");
+ D1(jffs2_print_fragtree(list));
return 0;
}
@@ -180,6 +212,8 @@
jffs2_fragtree_insert(newfrag, this);
rb_insert_color(&newfrag->rb, list);
} else {
+ /* New frag starts at the same point as 'this' used to. Replace
+ it in the tree without doing a delete and insertion */
D2(printk(KERN_DEBUG "Inserting newfrag (*%p) in before 'this' (*%p)\n", newfrag, this));
struct jffs2_node_frag *parent = frag_parent(this);
@@ -219,12 +253,14 @@
D1(printk(KERN_DEBUG "Truncating fraglist to 0x%08x bytes\n", size));
/* We know frag->ofs <= size. That's what lookup does for us */
- if (frag && frag->ofs != size && frag->ofs+frag->size > size) {
- D1(printk(KERN_DEBUG "Truncating frag 0x%08x-0x%08x\n", frag->ofs, frag->ofs+frag->size));
- frag->size = size - frag->ofs;
+ if (frag && frag->ofs != size) {
+ if (frag->ofs+frag->size >= size) {
+ D1(printk(KERN_DEBUG "Truncating frag 0x%08x-0x%08x\n", frag->ofs, frag->ofs+frag->size));
+ frag->size = size - frag->ofs;
+ }
frag = frag_next(frag);
}
- while (frag) {
+ while (frag && frag->ofs >= size) {
struct jffs2_node_frag *next = frag_next(frag);
D1(printk(KERN_DEBUG "Removing frag 0x%08x-0x%08x\n", frag->ofs, frag->ofs+frag->size));
More information about the linux-mtd-cvs
mailing list