JFFS3 memory consumption

[Artem B. Bityuckiy]

Hi,

I have recently described the JFFS2 memory consumption problem. David has
suggested several ideas.

The best idea is the write-back cache, I think. But this touches the 
memory
consumption only by implication. It is really about IO speed improvement.
So, I think we may discuss how to implement this WB cache in another 
thread.
I think this would be *very* good JFFS3 attribute.

Another David's Idea about the maximum inode node size augmentation is 
also
pretty nice for me. The idea to implement zisofs-like read is very good, I 
think.
I've noted both of these, hope this will be in the JFFS3 design.

But I have another, more radical idea. It decreases the memory consumption 
better
in most cases. While we currently have the linear dependency on nodes 
number, my
idea changes this to the dependency on inodes number.

Most often the nodes number is much larger then the number of inodes. But 
there are
exceptions there and my proposal will not help in these cases much.

Before describing Idea, some definitions:

Summary node
~~~~~~~~~~~
The node which describes all other nodes in one block. Summaries are 
placed at the
end of each block. For each other node in this block summaries contain the 
following
information:

node offset within the block
node length
node type
for direntry nodes:
        direntry name
        direntry target/parent inode
for inode nodes:
        inode number
        data offset
...... may be something other.

Thus, if we want to know the block's layout, we may just read its summary 
node.

Inode checkpoint node (ICP)
~~~~~~~~~~~~~~~~~~~~~~~~~~
Checkpoint node describes all the nodes related to some inode. Checkpoints 
may
be placed anywhere within flash, as any other node. For each node related 
to
the inode the ICP contains:


node offset within the flash
node length
node type
for direntry nodes:
        direntry name
        direntry target/parent inode
for inode nodes:
        inode number
        data offset
...... may be something other.

Just almost the same as summary, but the per-inode information.


The Idea
~~~~~~~
Imagine we have file system, where each inode has ICP and each block has 
Summary.
Then we may keep in-core only the positions of ICPs for each inode.

In this case:
1. when we need per-inode nedes list, we read ICP and we have it!
2. when we need per block nodes list, we read Summary and we have it!

No need to keep the per-block and per-inode node_ref lists in-core 
anymore!

The per-inode list is only needed on the iget() call. After the iget() 
call
we will have the per-inode list in memory (say, in form of fragtree or the
dirent list).

The per-block list is only needed for the Garbage Collection.

When the file is opened and it is changed, wee build the ICP of this file 
in RAM.
We flush this ICP on iput() call. Summaries are also being formed in RAM 
and
flushed when the block is almost full.

So far so good. But there are a bundle of problems we must solve.
Just count some of them:

1. Unclean reboots. In this case we will have no up-to-date ICPs and 
Summaries.
I hope in this case we still will be ables to use old JFFS2 algorithms.
I suspect this case includes situations when we have no flash space to 
flush ICPs
or we are out of memory while forming it. We will just not write them then 
which
is similar to unclean reboot.

2. GC tends to merge non-pristine nodes. So it changes ICPs, and the GC 
process
will be slower.

3. Since we form ICPs of opened file in memory, we will possibly need to 
reserve some
flash space to be able to flush these ICPs on unmount. This needs very 
accurate
flash space accounting.

I believe these are not all problems, but think the biggest ones.
At the first glance all of them are solvable.

Thanks for your comments.

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