A simple JFFS3 GC algorithm

A simple JFFS3 GC algorithm

[Ferenc Havasi]

Dear All,

We have been thinking about JFFS3 and its remaining parts (such us 
garbage collection), and described a simple idea for it. I don't think 
it is the best one, but relatively simple, may implemented in the 
first/prototype version of JFFS3. The document can be downloaded from here:

http://www.inf.u-szeged.hu/jffs2/documentation.php

Ferenc

Re: A simple JFFS3 GC algorithm

[Artem B. Bityutskiy]

Ferenc Havasi wrote:
> Dear All,
> 
> We have been thinking about JFFS3 and its remaining parts (such us 
> garbage collection), and described a simple idea for it. I don't think 
> it is the best one, but relatively simple, may implemented in the 
> first/prototype version of JFFS3. The document can be downloaded from here:
> 
Thanks Ferenc, I'll read this and send you my feedback.

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

Re: A simple JFFS3 GC algorithm

[Artem B. Bityutskiy]

Ferenc Havasi wrote:
> Dear All,
> 
> We have been thinking about JFFS3 and its remaining parts (such us 
> garbage collection), and described a simple idea for it. I don't think 
> it is the best one, but relatively simple, may implemented in the 
> first/prototype version of JFFS3. The document can be downloaded from here:
> 

Hi Ferenc,

Your proposal is based on a "map" which is basically a per-region table. 
This is unscalable solution. Do you have any other more scalable 
proposals? Let's for now consider this as a fall-back solution, OK?

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

Re: A simple JFFS3 GC algorithm

[Artem B. Bityutskiy]

Artem B. Bityutskiy wrote:
> Your proposal is based on a "map" which is basically a per-region table. 
> This is unscalable solution. Do you have any other more scalable 
> proposals? Let's for now consider this as a fall-back solution, OK?

And, BTW, how are you going to build this "map" when you mount the file 
system?


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

Re: A simple JFFS3 GC algorithm

[Ferenc Havasi]

Hi Artem,

> Your proposal is based on a "map" which is basically a per-region
> table. This is unscalable solution. Do you have any other more
> scalable proposals? Let's for now consider this as a fall-back
> solution, OK?

If we don't work with regions smaller than 256K, than a size of the map
of a 16G flash is about 786K, which I think is still OK, and also can be
cached.

I know this is not the best solution, we suggested it only for the first
variant of JFFS3 because it may work well on recent flash chips and make
the garbage collection absolutelly transparent, and relatively easy to
implement - there is no serious locking problems.

> And, BTW, how are you going to build this "map" when you mount the
> file system? 

It is stored on the flash somewhere (its position is in the superblock),
and the changes are logged into a separated journal. When this journal
is fulled, the new version of map will be written out. If the file
system is mounted the stored map will be loaded and the events stored in
the journal are replayed.

Anyway, we don't insist on this algorithm, it was only an idea, maybe
not usefull. We've started to implement a simplified user space
prototype of JFFS3, specially for testing different kind of garbage
collecting methods.

Bye,
Ferenc

Re: A simple JFFS3 GC algorithm

[Artem B. Bityutskiy]

On Tue, 2006-03-07 at 12:04 +0100, Ferenc Havasi wrote:
> If we don't work with regions smaller than 256K, than a size of the map
> of a 16G flash is about 786K, which I think is still OK, and also can be
> cached.
Providing this number is correct, indiid, not too much.

> It is stored on the flash somewhere (its position is in the superblock),
> and the changes are logged into a separated journal. When this journal
> is fulled, the new version of map will be written out. If the file
> system is mounted the stored map will be loaded and the events stored in
> the journal are replayed.
Hmm. Could you please add more detailed description to your document
about how we could maintain this map on flash, that journal, etc?

> Anyway, we don't insist on this algorithm, it was only an idea, maybe
> not usefull. We've started to implement a simplified user space
> prototype of JFFS3, specially for testing different kind of garbage
> collecting methods.
> 
Cool!

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

Re: A simple JFFS3 GC algorithm

[Artem B. Bityutskiy]

On Tue, 2006-03-07 at 14:24 +0300, Artem B. Bityutskiy wrote:
> Providing this number is correct, indiid, not too much.
I meant "indeed" :-)