[PATCH] (preliminary) new fragtree build method

[Artem B. Bityuckiy]

Hello,

I've implemented a new fragtree build algorithm which should optimize
and speed-up the the JFFS2 checking process.

I'd like to recall, that just after mount, JFFS2 checks all the inodes
it has found during the initial flash scan. The checking process' goal
is to (1) check the header/data CRCs of the inode's nodes and (2) to
detect and drop obsolete nodes (NAND-specific).

The checking process, in fact, is a "fake" inode build invocation for
each inode in the filesystem. During the check of the regular file
inodes (I further will talk only about the regular file inodes) JFFS2
does the following:

1. Read nodes, checks their data and header CRC.
2. Build the temporary RB-tree with the key = the node version (this
used to be the temporary list, not tree, until recently). The whole
point of this is to sort nodes in the order of increasing versions.
3. Build the fragtree, taking nodes from the temporary RB-tree one-by-
one, in the increasing node version. While this fragtree is being built,
obsolete nodes are detected (NAND-specific).

The drawback of this approach is that we read the data of *all* nodes at
step 1. and check the data CRC of all nodes, even though they will be
recognized as obsolete at step 3 and dropped.

My patch changes is algorithm:

1. Read only the node headers, checks their CRC (data are not read and
are not checked).
2. Build the temporary RB-tree with the key = node version. The whole
point of this is to sort nodes in the order of *decreasing* versions.
3. Builds the fragtree, taking nodes from the temporary RB-tree one-by-
one, in the *decreasing* node version. Just before we have found that
the node should be inserted, we check its data CRC. If we have found
that the node is obsolete, we do not check it, just mark it obsolete and
drop.

Thus, we avoid reading and checking data of obsolete nodes.

The patch may be found at:
http://www.infradead.org/~dedekind/reverse-version-prelim-01.diff

Please, review it, try it. It changes the vital part of JFFS2, so it
would be nice if people try it on their systems before we may commit it.

Note: on NOR the patch does not optimize anything, but I'd be very
appreciated if someone try it, just to be sure it is OK.

Note: I've left some temporary debugging stuff there, it'll be removed.

Thanks.

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.