JFFS3 superblock search

JFFS3 superblock search

[Artem B. Bityuckiy]

Hello,

in order not to lose your attention I decided to announce that the JFFS3
design document (v0.1) now has a description of the Superblock
management scheme. It allows to solve the slow mount problem and admits
of locating the position of the Superblock for < 2ms (you'll find some
digits in the document). Any suggestions, criticism etc are appreciated.


P.S. Since the document has no description of the general approach of
storing data in JFFS3, I'll note that I'm thinking about a Reiser4-like
approach, i.e., storing all the FS data in one 4-level B+ tree. There
will be a superblock containing the FS description and admitting of very
fast JFFS3 mount.

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

Re: JFFS3 superblock search

[Artem B. Bityuckiy]

> in order not to lose your attention I decided to announce that the JFFS3
> design document (v0.1) now has a description of the Superblock
> management scheme. It allows to solve the slow mount problem and admits
> of locating the position of the Superblock for < 2ms (you'll find some
> digits in the document). Any suggestions, criticism etc are appreciated.

The document is here:
http://www.linux-mtd.infradead.org/tech/JFFS3design.pdf

Re: JFFS3 superblock search

[Jörn Engel]

On Mon, 6 June 2005 16:59:07 +0400, Artem B. Bityuckiy wrote:
> 
> P.S. Since the document has no description of the general approach of
> storing data in JFFS3, I'll note that I'm thinking about a Reiser4-like
> approach, i.e., storing all the FS data in one 4-level B+ tree. There
> will be a superblock containing the FS description and admitting of very
> fast JFFS3 mount.

You already know that I'm skeptical about the B+ tree.  But I'm even
more skeptical about a 4-level tree.  That could turn into a
bottleneck rather quickly.

Apart from that, I'd like to see some further details of the tree
design.

Jörn

-- 
Do not stop an army on its way home.
-- Sun Tzu

Re: JFFS3 superblock search

[Artem B. Bityuckiy]

Jörn Engel wrote:
> You already know that I'm skeptical about the B+ tree.  But I'm even
> more skeptical about a 4-level tree.  That could turn into a
> bottleneck rather quickly.
> 
Joern,

providing the key is 16 bytes and the pointer is 8 bytes, the 4-level 
B-tree is enough for (4096/24)^4 = 170^4 ~1E8. If this isn't enough we 
may use more levels as well.

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

Re: JFFS3 superblock search

[Jörn Engel]

On Mon, 6 June 2005 17:45:38 +0400, Artem B. Bityuckiy wrote:
> 
> providing the key is 16 bytes and the pointer is 8 bytes, the 4-level 
> B-tree is enough for (4096/24)^4 = 170^4 ~1E8. If this isn't enough we 
> may use more levels as well.

There are valid reasons to use 512 byte blocks instead.  Most likely I
will do just that for logfs, just as a hint.  Therefore, even with 8
byte keys, you'd be down to 32^4 or about a million.  Prepare for more
levels.

Jörn

-- 
I don't understand it. Nobody does.
-- Richard P. Feynman

Re: JFFS3 superblock search

[Artem B. Bityuckiy]

> There are valid reasons to use 512 byte blocks instead.  Most likely I
> will do just that for logfs, just as a hint.  Therefore, even with 8
> byte keys, you'd be down to 32^4 or about a million.  Prepare for more
> levels.

May be. Should think more.
If you're going to make use of the Tree-based approach, then why don't
you rename logfs to JFFS3 and we'll join :-) ?

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

Re: JFFS3 superblock search

[Jörn Engel]

On Mon, 6 June 2005 18:10:37 +0400, Artem B. Bityuckiy wrote:
> 
> > There are valid reasons to use 512 byte blocks instead.  Most likely I
> > will do just that for logfs, just as a hint.  Therefore, even with 8
> > byte keys, you'd be down to 32^4 or about a million.  Prepare for more
> > levels.
> 
> May be. Should think more.
> If you're going to make use of the Tree-based approach, then why don't
> you rename logfs to JFFS3 and we'll join :-) ?

I won't make use of a single tree.  And naming is jffs3 would just be
gross.  Image the name correctly describing the design?  Eew!  ;)

Jörn

-- 
There are two ways of constructing a software design: one way is to make
it so simple that there are obviously no deficiencies, and the other is
to make it so complicated that there are no obvious deficiencies.
-- C. A. R. Hoare

Re: JFFS3 superblock search

[Artem B. Bityuckiy]

> I won't make use of a single tree.  And naming is jffs3 would just be
> gross.  Image the name correctly describing the design?  Eew!  ;)

But the "JFFS3" name has better PR :-)

--
What's the difference between a horrid black rat and a nice white mouse?
The mouse's PR is better.

Re: JFFS3 superblock search

[Jörn Engel]

On Mon, 6 June 2005 18:22:02 +0400, Artem B. Bityuckiy wrote:
> 
> > I won't make use of a single tree.  And naming is jffs3 would just be
> > gross.  Image the name correctly describing the design?  Eew!  ;)
> 
> But the "JFFS3" name has better PR :-)

Maybe.  Whatever, I'll continue under my codename of logfs (which is
just as wrong as jffs - a natural successor) until I have something
usable.  At that point, a naming contest is scheduled anyway and
"JFFS3" could well be the name people decide upon.

Jörn

-- 
Premature optimization is the root of all evil.
-- Donald Knuth

Re: JFFS3 superblock search

[Jared Hulbert]

> Maybe.  Whatever, I'll continue under my codename of logfs (which is
> just as wrong as jffs - a natural successor) until I have something
> usable.  At that point, a naming contest is scheduled anyway and
> "JFFS3" could well be the name people decide upon.

So I'm missing out here.  What's logfs?

Re: JFFS3 superblock search

[Artem B. Bityuckiy]

Jared Hulbert wrote:
>>Maybe.  Whatever, I'll continue under my codename of logfs (which is
>>just as wrong as jffs - a natural successor) until I have something
>>usable.  At that point, a naming contest is scheduled anyway and
>>"JFFS3" could well be the name people decide upon.
> 
> 
> So I'm missing out here.  What's logfs?
This is an Flash FS which Joern is developing and didn't yet share.

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

Re: JFFS3 superblock search

[Artem B. Bityuckiy]

> There are valid reasons to use 512 byte blocks instead.  Most likely I
> will do just that for logfs, just as a hint.  Therefore, even with 8
> byte keys, you'd be down to 32^4 or about a million.  Prepare for more
> levels.
It might make sense to have leafs = 4K (like the RAM page) and non-leafs
= NAND page.

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

Re: JFFS3 superblock search

[Jörn Engel]

On Mon, 6 June 2005 18:17:16 +0400, Artem B. Bityuckiy wrote:
>
> It might make sense to have leafs = 4K (like the RAM page) and non-leafs
> = NAND page.

I prefer extends.

Jörn

-- 
Sometimes, asking the right question is already the answer.
-- Unknown