Regarding UBI scalability

Regarding UBI scalability

[BRIJESH SINGH]

Hi,
    I have gone through UBI documentation which clearly mentions that UBI doesn't scale very well.(Boot time and Memory consumption increases with size of device.)This is very similar to JFFS2 scalability issues. Log, journal(like UBIFS LPT)  combination might surely help on this issue.

  I would like to work on this enhancement with the community. Before that I just wanted to check if any one is already working on it.
  As this a well known issue, I am sure somebody will have some design suggestions. Any design suggestions will be appreciated.
 
Thanks,
Brijesh
 

Re: Regarding UBI scalability

[Artem Bityutskiy]

On Fri, 2009-01-30 at 12:45 +0000, BRIJESH SINGH wrote:
> Hi,
>     I have gone through UBI documentation which clearly mentions that
> UBI doesn't scale very well.(Boot time and Memory consumption
> increases with size of device.)This is very similar to JFFS2
> scalability issues. Log, journal(like UBIFS LPT)  combination might
> surely help on this issue.

Right.

>   I would like to work on this enhancement with the community. Before
> that I just wanted to check if any one is already working on it.

No, I do not think so.

>   As this a well known issue, I am sure somebody will have some design
> suggestions. Any design suggestions will be appreciated.

You could look at the old JFFS3 design document:

http://www.linux-mtd.infradead.org/doc/JFFS3design.pdf

at the "The superblock" section, which describes the idea of how to have
a data structure which refers everything else in the media: journal,
root nodes of the trees, etc.

An then you should think about how to store the EBA table on flash. And
how to store the erase counters on the flash. Many ideas may be borrowed
from UBIFS in this area.

I may help you in terms of design suggestions / review, and some code
review. But I do not really have time to seriously work on this.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Regarding UBI scalability

[Amit Kumar Sharma]

Hi
----- Original Message ----- 
From: "Artem Bityutskiy" <dedekind@infradead.org>
To: <brij.singh@samsung.com>
Cc: <linux-mtd@lists.infradead.org>
Sent: Monday, February 02, 2009 3:01 PM
Subject: Re: Regarding UBI scalability


> On Fri, 2009-01-30 at 12:45 +0000, BRIJESH SINGH wrote:
>> Hi,
>>     I have gone through UBI documentation which clearly 
>> mentions that
>> UBI doesn't scale very well.(Boot time and Memory 
>> consumption
>> increases with size of device.)This is very similar to 
>> JFFS2
>> scalability issues. Log, journal(like UBIFS LPT) 
>> combination might
>> surely help on this issue.
>
> Right
>
>>   I would like to work on this enhancement with the 
>> community. Before
>> that I just wanted to check if any one is already working 
>> on it.
>
> No, I do not think so.
>
>>   As this a well known issue, I am sure somebody will 
>> have some design
>> suggestions. Any design suggestions will be appreciated.
>
> You could look at the old JFFS3 design document:
>
> http://www.linux-mtd.infradead.org/doc/JFFS3design.pdf
>
> at the "The superblock" section, which describes the idea 
> of how to have
> a data structure which refers everything else in the 
> media: journal,
> root nodes of the trees, etc.
>
> An then you should think about how to store the EBA table 
> on flash. And
> how to store the erase counters on the flash. Many ideas 
> may be borrowed
> from UBIFS in this area.
>
> I may help you in terms of design suggestions / review, 
> and some code
> review. But I do not really have time to seriously work on 
> this.
>
> -- 
> Best regards,
> Artem Bityutskiy (???????? ?????)

Thanks for your comments Brijesh will check all your 
suggestion and we will discuss final design with you for 
your comments.

Thanks
Amit
>
>
> ______________________________________________________
> Linux MTD discussion mailing list
> http://lists.infradead.org/mailman/listinfo/linux-mtd/
> 

Re: Regarding UBI scalability

[Artem Bityutskiy]

On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
> I would suggest an intermediate step.  Create UBI2 which is
> similar to UBI but stores eraseblock information in one place,
> instead of at the beginning of each eraseblock.  Such an approach
> might be OK up to as much as 64GiB, and would probably perform
> better than a fully scalable version.
> 
> Then look at creating UBI3, which is fully scalable.

Yes, I assume UBI2 should store mapping/erasure information in separate
tables, not in each eraseblock. So we should get rid of eraseblock
headers.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Regarding UBI scalability

[Adrian Hunter]

Amit Kumar Sharma wrote:
> Hi
> ----- Original Message -----
> From: "Artem Bityutskiy" <dedekind@infradead.org>
> To: <brij.singh@samsung.com>
> Cc: <linux-mtd@lists.infradead.org>
> Sent: Monday, February 02, 2009 3:01 PM
> Subject: Re: Regarding UBI scalability
> 
> 
>> On Fri, 2009-01-30 at 12:45 +0000, BRIJESH SINGH wrote:
>>> Hi,
>>>     I have gone through UBI documentation which clearly
>>> mentions that
>>> UBI doesn't scale very well.(Boot time and Memory
>>> consumption
>>> increases with size of device.)This is very similar to
>>> JFFS2
>>> scalability issues. Log, journal(like UBIFS LPT)
>>> combination might
>>> surely help on this issue.
>> Right
>>
>>>   I would like to work on this enhancement with the
>>> community. Before
>>> that I just wanted to check if any one is already working
>>> on it.
>> No, I do not think so.
>>
>>>   As this a well known issue, I am sure somebody will
>>> have some design
>>> suggestions. Any design suggestions will be appreciated.
>> You could look at the old JFFS3 design document:
>>
>> http://www.linux-mtd.infradead.org/doc/JFFS3design.pdf
>>
>> at the "The superblock" section, which describes the idea
>> of how to have
>> a data structure which refers everything else in the
>> media: journal,
>> root nodes of the trees, etc.
>>
>> An then you should think about how to store the EBA table
>> on flash. And
>> how to store the erase counters on the flash. Many ideas
>> may be borrowed
>> from UBIFS in this area.
>>
>> I may help you in terms of design suggestions / review,
>> and some code
>> review. But I do not really have time to seriously work on
>> this.
>>
>> --
>> Best regards,
>> Artem Bityutskiy (???????? ?????)
> 
> Thanks for your comments Brijesh will check all your
> suggestion and we will discuss final design with you for
> your comments.
> 
> Thanks
> Amit

I would suggest an intermediate step.  Create UBI2 which is
similar to UBI but stores eraseblock information in one place,
instead of at the beginning of each eraseblock.  Such an approach
might be OK up to as much as 64GiB, and would probably perform
better than a fully scalable version.

Then look at creating UBI3, which is fully scalable.

Re: Regarding UBI scalability

[Adrian Hunter]

Artem Bityutskiy wrote:
> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>> I would suggest an intermediate step.  Create UBI2 which is
>> similar to UBI but stores eraseblock information in one place,
>> instead of at the beginning of each eraseblock.  Such an approach
>> might be OK up to as much as 64GiB, and would probably perform
>> better than a fully scalable version.
>>
>> Then look at creating UBI3, which is fully scalable.
> 
> Yes, I assume UBI2 should store mapping/erasure information in separate
> tables, not in each eraseblock. So we should get rid of eraseblock
> headers.

Yes that is what I meant.  You could probably make do with as little as
12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
would need 1536KiB table, which could be read in a second or two, so
mount time is OK.

I have an idea for how to update the table relatively efficiently if you
are interested.

Re: Regarding UBI scalability

[Jamie Lokier]

You might also look at the method LogFS uses.  LogFS claims to be
scalable and very fast for large flashes already.

-- Jamie

Re: Regarding UBI scalability

[Corentin Chary]

On Mon, Feb 2, 2009 at 12:18 PM, Adrian Hunter
<ext-adrian.hunter@nokia.com> wrote:
> Artem Bityutskiy wrote:
>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>> I would suggest an intermediate step.  Create UBI2 which is
>>> similar to UBI but stores eraseblock information in one place,
>>> instead of at the beginning of each eraseblock.  Such an approach
>>> might be OK up to as much as 64GiB, and would probably perform
>>> better than a fully scalable version.
>>>
>>> Then look at creating UBI3, which is fully scalable.
>>
>> Yes, I assume UBI2 should store mapping/erasure information in separate
>> tables, not in each eraseblock. So we should get rid of eraseblock
>> headers.
>
> Yes that is what I meant.  You could probably make do with as little as
> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
> would need 1536KiB table, which could be read in a second or two, so
> mount time is OK.

Hi,
I was wondering how it is possible to get atomic operations using such tables ?
The first thing that come to my mind is TFAT (two tables, one for
operation in progress,
the other considered as always "valid"). But I'm not sure it' the good
way to do such a thing.



-- 
Corentin Chary
http://xf.iksaif.net

Re: Regarding UBI scalability

[Brijesh Singh]

On Tue, Feb 3, 2009 at 5:14 AM, Corentin Chary <corentin.chary@gmail.com> wrote:
> On Mon, Feb 2, 2009 at 12:18 PM, Adrian Hunter
> <ext-adrian.hunter@nokia.com> wrote:
>> Artem Bityutskiy wrote:
>>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>>> I would suggest an intermediate step.  Create UBI2 which is
>>>> similar to UBI but stores eraseblock information in one place,
>>>> instead of at the beginning of each eraseblock.  Such an approach
>>>> might be OK up to as much as 64GiB, and would probably perform
>>>> better than a fully scalable version.
>>>>
>>>> Then look at creating UBI3, which is fully scalable.
>>>
>>> Yes, I assume UBI2 should store mapping/erasure information in separate
>>> tables, not in each eraseblock. So we should get rid of eraseblock
>>> headers.
>>
>> Yes that is what I meant.  You could probably make do with as little as
>> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
>> would need 1536KiB table, which could be read in a second or two, so
>> mount time is OK.

Adrian,to my understanding, this is minimum info needed per physical
erase block...

Erase count                   -8 bytes
Lnum                             -4 bytes
Volume ID                      -4 byte(Can make it 1 byte for now as
vol limit=128)
Header CRC                   -4 bytes(Only for static volumes.)
i.e. Minimum 20 bytes.  Is there any other way to make it 12?
And how to update the table relatively efficiently?

> Hi,
> I was wondering how it is possible to get atomic operations using such tables ?
May be keeping a commit block and journal will help.(*Like UBIFS design)

Thanks,
Brijesh

Re: Regarding UBI scalability

[Artem Bityutskiy]

On Tue, 2009-02-03 at 00:44 +0100, Corentin Chary wrote:
> I was wondering how it is possible to get atomic operations using such tables ?
> The first thing that come to my mind is TFAT (two tables, one for
> operation in progress,
> the other considered as always "valid"). But I'm not sure it' the good
> way to do such a thing.

Journal + commit mechanisms should allow doing this.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Regarding UBI scalability

[Artem Bityutskiy]

On Tue, 2009-02-03 at 16:05 +0530, Brijesh Singh wrote:
> On Tue, Feb 3, 2009 at 5:14 AM, Corentin Chary <corentin.chary@gmail.com> wrote:
> > On Mon, Feb 2, 2009 at 12:18 PM, Adrian Hunter
> > <ext-adrian.hunter@nokia.com> wrote:
> >> Artem Bityutskiy wrote:
> >>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
> >>>> I would suggest an intermediate step.  Create UBI2 which is
> >>>> similar to UBI but stores eraseblock information in one place,
> >>>> instead of at the beginning of each eraseblock.  Such an approach
> >>>> might be OK up to as much as 64GiB, and would probably perform
> >>>> better than a fully scalable version.
> >>>>
> >>>> Then look at creating UBI3, which is fully scalable.
> >>>
> >>> Yes, I assume UBI2 should store mapping/erasure information in separate
> >>> tables, not in each eraseblock. So we should get rid of eraseblock
> >>> headers.
> >>
> >> Yes that is what I meant.  You could probably make do with as little as
> >> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
> >> would need 1536KiB table, which could be read in a second or two, so
> >> mount time is OK.
> 
> Adrian,to my understanding, this is minimum info needed per physical
> erase block...
> 
> Erase count                   -8 bytes
> Lnum                             -4 bytes
> Volume ID                      -4 byte(Can make it 1 byte for now as
> vol limit=128)
> Header CRC                   -4 bytes(Only for static volumes.)
> i.e. Minimum 20 bytes.  Is there any other way to make it 12?
> And how to update the table relatively efficiently?

For UBI2 I would just forget about static volumes support. They are not
so necessary, and a rare user needs them. This would simplify things.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Regarding UBI scalability

[Corentin Chary]

On Tue, Feb 3, 2009 at 11:46 AM, Artem Bityutskiy
<dedekind@infradead.org> wrote:
> On Tue, 2009-02-03 at 00:44 +0100, Corentin Chary wrote:
>> I was wondering how it is possible to get atomic operations using such tables ?
>> The first thing that come to my mind is TFAT (two tables, one for
>> operation in progress,
>> the other considered as always "valid"). But I'm not sure it' the good
>> way to do such a thing.
>
> Journal + commit mechanisms should allow doing this.

I'm asking some other questions, because in UFFS we are working on
something like that, but not for UBI2. But if I can help for UBI2,
I'll.

A journal node, would probably take less than 16 B. With min_io_size
>= 512 B (sometime 2KB), a journal for map/unmap operation will take
some time before being written.

I see two solutions, based on periodic journal write with padding to
have min_io_size bytes to write:
- based on time (every X ms)
- based on changes (every X changes)
- based on both

But there is probably more clever solutions.

One other thing is the table will have to move on the flash for wear
leveling, but for that we can use the "anchors" as defined in JFFS3
pdf.


-- 
Corentin Chary
http://xf.iksaif.net

Re: Regarding UBI scalability

[Enrico Scholz]

Artem Bityutskiy <dedekind@infradead.org> writes:

> For UBI2 I would just forget about static volumes support. They
> are not so necessary, and a rare user needs them

I store my kernel, the 2nd level bootloader and bootenv in such
volumes.  Having the number of used bytes available without
introducing special storage formats simplifies things in the
initial bootloader and when writing images into the volumes.

This is nothing which can not be changed, but static volumes are
not a rare needs imo.


Enrico

Re: Regarding UBI scalability

[Brijesh Singh]

On Tue, Feb 3, 2009 at 4:43 PM, Corentin Chary <corentin.chary@gmail.com> wrote:
> On Tue, Feb 3, 2009 at 11:46 AM, Artem Bityutskiy
> <dedekind@infradead.org> wrote:
>> On Tue, 2009-02-03 at 00:44 +0100, Corentin Chary wrote:
>>> I was wondering how it is possible to get atomic operations using such tables ?
>>> The first thing that come to my mind is TFAT (two tables, one for
>>> operation in progress,
>>> the other considered as always "valid"). But I'm not sure it' the good
>>> way to do such a thing.
>>
>> Journal + commit mechanisms should allow doing this.
>
> I'm asking some other questions, because in UFFS we are working on
> something like that, but not for UBI2. But if I can help for UBI2,
> I'll.
>
> A journal node, would probably take less than 16 B. With min_io_size
>>= 512 B (sometime 2KB), a journal for map/unmap operation will take
> some time before being written.
>
> I see two solutions, based on periodic journal write with padding to
> have min_io_size bytes to write:
> - based on time (every X ms)
> - based on changes (every X changes)
> - based on both
> But there is probably more clever solutions.
I will check this.As of now I don't find a way to skip writing journal
node.For consistency,
you have to.
>
> One other thing is the table will have to move on the flash for wear
> leveling, but for that we can use the "anchors" as defined in JFFS3
> pdf.
This will move on flash. In UBI,there is a small trick. Journal and
commit can be on internal volumes.
So it easily gets wear-leveled.

And the Super block will know where are they?Super block can be
logged. Fixed in 0-5 blocks.

Best Regards,
Brijesh

Re: Regarding UBI scalability

[Artem Bityutskiy]

On Tue, 2009-02-03 at 12:27 +0100, Enrico Scholz wrote:
> Artem Bityutskiy <dedekind@infradead.org> writes:
> 
> > For UBI2 I would just forget about static volumes support. They
> > are not so necessary, and a rare user needs them
> 
> I store my kernel, the 2nd level bootloader and bootenv in such
> volumes.  Having the number of used bytes available without
> introducing special storage formats simplifies things in the
> initial bootloader and when writing images into the volumes.
> 
> This is nothing which can not be changed, but static volumes are
> not a rare needs imo.

Ok, thanks for this information. Probably static volumes are not that
useless as I thought.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Regarding UBI scalability

[Artem Bityutskiy]

On Tue, 2009-02-03 at 12:13 +0100, Corentin Chary wrote:
> On Tue, Feb 3, 2009 at 11:46 AM, Artem Bityutskiy
> <dedekind@infradead.org> wrote:
> > On Tue, 2009-02-03 at 00:44 +0100, Corentin Chary wrote:
> >> I was wondering how it is possible to get atomic operations using such tables ?
> >> The first thing that come to my mind is TFAT (two tables, one for
> >> operation in progress,
> >> the other considered as always "valid"). But I'm not sure it' the good
> >> way to do such a thing.
> >
> > Journal + commit mechanisms should allow doing this.
> 
> I'm asking some other questions, because in UFFS we are working on
> something like that, but not for UBI2. But if I can help for UBI2,
> I'll.
> 
> A journal node, would probably take less than 16 B. With min_io_size
> >= 512 B (sometime 2KB), a journal for map/unmap operation will take
> some time before being written.

Well, to guarantee integrity, I do not see any other solution but doing
2x2KiB writes on 2KiB-page NAND: start update (1), (write the LEB
somewhere), end update (2), (erase the old PEB). That's the price you
pay.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Regarding UBI scalability

[Adrian Hunter]

Brijesh Singh wrote:
> On Tue, Feb 3, 2009 at 5:14 AM, Corentin Chary <corentin.chary@gmail.com> wrote:
>> On Mon, Feb 2, 2009 at 12:18 PM, Adrian Hunter
>> <ext-adrian.hunter@nokia.com> wrote:
>>> Artem Bityutskiy wrote:
>>>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>>>> I would suggest an intermediate step.  Create UBI2 which is
>>>>> similar to UBI but stores eraseblock information in one place,
>>>>> instead of at the beginning of each eraseblock.  Such an approach
>>>>> might be OK up to as much as 64GiB, and would probably perform
>>>>> better than a fully scalable version.
>>>>>
>>>>> Then look at creating UBI3, which is fully scalable.
>>>> Yes, I assume UBI2 should store mapping/erasure information in separate
>>>> tables, not in each eraseblock. So we should get rid of eraseblock
>>>> headers.
>>> Yes that is what I meant.  You could probably make do with as little as
>>> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
>>> would need 1536KiB table, which could be read in a second or two, so
>>> mount time is OK.
> 
> Adrian,to my understanding, this is minimum info needed per physical
> erase block...
> 
> Erase count                   -8 bytes
> Lnum                             -4 bytes
> Volume ID                      -4 byte(Can make it 1 byte for now as
> vol limit=128)
> Header CRC                   -4 bytes(Only for static volumes.)
> i.e. Minimum 20 bytes.  Is there any other way to make it 12?

8 bytes for erase counter is many more than needed i.e.
	SLC NAND 100,000 - 1,000,000 max. erase cycles
	MLC NAND 10000 - 10,000 max. erase cycles

Leave out the header CRC for dynamic volumes

Combine lnum and volume id.

Maybe go so far as to pack the information into bit fields
like LPT does. i.e. if the flash media only has a million
eraseblocks then only 20 bits are needed for lnum.  Maybe it
is MLC NAND, so say 15 bits for erase counter.  That leaves 5
bites for volume id, and fits into 5 bytes for dynmaic volumes.

> And how to update the table relatively efficiently?

Each update to UBI typically requires writing a whole NAND
page.  That page can be filled with unchanged information
from the first eraseblock of UBI information.  Hence after
enough updates the first eraseblock will end up containing
only out-of-date information and can then be unmapped.

Wash, rinse, repeat.

> 
>> Hi,
>> I was wondering how it is possible to get atomic operations using such tables ?
> May be keeping a commit block and journal will help.(*Like UBIFS design)
> 
> Thanks,
> Brijesh
> 

Re: Regarding UBI scalability

[Brijesh Singh]

On Wed, Feb 4, 2009 at 2:59 PM, Adrian Hunter
<ext-adrian.hunter@nokia.com> wrote:
> Brijesh Singh wrote:
>>
>> On Tue, Feb 3, 2009 at 5:14 AM, Corentin Chary <corentin.chary@gmail.com>
>> wrote:
>>>
>>> On Mon, Feb 2, 2009 at 12:18 PM, Adrian Hunter
>>> <ext-adrian.hunter@nokia.com> wrote:
>>>>
>>>> Artem Bityutskiy wrote:
>>>>>
>>>>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>>>>>
>>>>>> I would suggest an intermediate step.  Create UBI2 which is
>>>>>> similar to UBI but stores eraseblock information in one place,
>>>>>> instead of at the beginning of each eraseblock.  Such an approach
>>>>>> might be OK up to as much as 64GiB, and would probably perform
>>>>>> better than a fully scalable version.
>>>>>>
>>>>>> Then look at creating UBI3, which is fully scalable.
>>>>>
>>>>> Yes, I assume UBI2 should store mapping/erasure information in separate
>>>>> tables, not in each eraseblock. So we should get rid of eraseblock
>>>>> headers.
>>>>
>>>> Yes that is what I meant.  You could probably make do with as little as
>>>> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
>>>> would need 1536KiB table, which could be read in a second or two, so
>>>> mount time is OK.
>>
>> Adrian,to my understanding, this is minimum info needed per physical
>> erase block...
>>
>> Erase count                   -8 bytes
>> Lnum                             -4 bytes
>> Volume ID                      -4 byte(Can make it 1 byte for now as
>> vol limit=128)
>> Header CRC                   -4 bytes(Only for static volumes.)
>> i.e. Minimum 20 bytes.  Is there any other way to make it 12?
>
> 8 bytes for erase counter is many more than needed i.e.
>        SLC NAND 100,000 - 1,000,000 max. erase cycles
>        MLC NAND 10000 - 10,000 max. erase cycles
>
> Leave out the header CRC for dynamic volumes
>
> Combine lnum and volume id.
>
> Maybe go so far as to pack the information into bit fields
> like LPT does. i.e. if the flash media only has a million
> eraseblocks then only 20 bits are needed for lnum.  Maybe it
> is MLC NAND, so say 15 bits for erase counter.  That leaves 5
> bites for volume id, and fits into 5 bytes for dynmaic volumes.

Makes sense.

>> And how to update the table relatively efficiently?
>
> Each update to UBI typically requires writing a whole NAND
> page.  That page can be filled with unchanged information
> from the first eraseblock of UBI information.  Hence after
> enough updates the first eraseblock will end up containing
> only out-of-date information and can then be unmapped.

Does it mean there is no separate commit block?And do we move the
journal with valid entries when it is full?

I find some problems with it.
1) Why process extra information for each write?
2) We will need to scan the entire journal for each mount.
3) Will work well with only NAND.

Instead, if there is a separate commit block, this can be read once
and processed.

I was wondering, how about combining both the approaches. i.e. A
commit block and journal as you suggested?Commit time will be reduced
dramatically.(As One page now contains group info). And boot time will
be fixed for good unmounts. Besides, it is simple and can be easily
scaled.

Best Regards,
Brijesh

Re: Regarding UBI scalability

[Adrian Hunter]

Brijesh Singh wrote:
> On Wed, Feb 4, 2009 at 2:59 PM, Adrian Hunter
> <ext-adrian.hunter@nokia.com> wrote:
>> Brijesh Singh wrote:
>>> On Tue, Feb 3, 2009 at 5:14 AM, Corentin Chary <corentin.chary@gmail.com>
>>> wrote:
>>>> On Mon, Feb 2, 2009 at 12:18 PM, Adrian Hunter
>>>> <ext-adrian.hunter@nokia.com> wrote:
>>>>> Artem Bityutskiy wrote:
>>>>>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>>>>>> I would suggest an intermediate step.  Create UBI2 which is
>>>>>>> similar to UBI but stores eraseblock information in one place,
>>>>>>> instead of at the beginning of each eraseblock.  Such an approach
>>>>>>> might be OK up to as much as 64GiB, and would probably perform
>>>>>>> better than a fully scalable version.
>>>>>>>
>>>>>>> Then look at creating UBI3, which is fully scalable.
>>>>>> Yes, I assume UBI2 should store mapping/erasure information in separate
>>>>>> tables, not in each eraseblock. So we should get rid of eraseblock
>>>>>> headers.
>>>>> Yes that is what I meant.  You could probably make do with as little as
>>>>> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
>>>>> would need 1536KiB table, which could be read in a second or two, so
>>>>> mount time is OK.
>>> Adrian,to my understanding, this is minimum info needed per physical
>>> erase block...
>>>
>>> Erase count                   -8 bytes
>>> Lnum                             -4 bytes
>>> Volume ID                      -4 byte(Can make it 1 byte for now as
>>> vol limit=128)
>>> Header CRC                   -4 bytes(Only for static volumes.)
>>> i.e. Minimum 20 bytes.  Is there any other way to make it 12?
>> 8 bytes for erase counter is many more than needed i.e.
>>        SLC NAND 100,000 - 1,000,000 max. erase cycles
>>        MLC NAND 10000 - 10,000 max. erase cycles
>>
>> Leave out the header CRC for dynamic volumes
>>
>> Combine lnum and volume id.
>>
>> Maybe go so far as to pack the information into bit fields
>> like LPT does. i.e. if the flash media only has a million
>> eraseblocks then only 20 bits are needed for lnum.  Maybe it
>> is MLC NAND, so say 15 bits for erase counter.  That leaves 5
>> bites for volume id, and fits into 5 bytes for dynmaic volumes.
> 
> Makes sense.
> 
>>> And how to update the table relatively efficiently?
>> Each update to UBI typically requires writing a whole NAND
>> page.  That page can be filled with unchanged information
>> from the first eraseblock of UBI information.  Hence after
>> enough updates the first eraseblock will end up containing
>> only out-of-date information and can then be unmapped.
> 
> Does it mean there is no separate commit block?And do we move the
> journal with valid entries when it is full?

I was describing my idea for UBI2.  There would be no journal,
no commit.  When writing new mappings, also write some existing
mappings from one of the eraseblocks until it no longer
contains any needed information.  It is like garbage-collection
as you go.

> I find some problems with it.
> 1) Why process extra information for each write?
> 2) We will need to scan the entire journal for each mount.
> 3) Will work well with only NAND.
> Instead, if there is a separate commit block, this can be read once
> and processed.
> 
> I was wondering, how about combining both the approaches. i.e. A
> commit block and journal as you suggested?Commit time will be reduced
> dramatically.(As One page now contains group info). And boot time will
> be fixed for good unmounts. Besides, it is simple and can be easily
> scaled.

Are you talking here about UBI3?

Re: Regarding UBI scalability

[Brijesh Singh]

Hi,
  Sorry for delayed response.

On Thu, Feb 5, 2009 at 4:47 PM, Adrian Hunter
<ext-adrian.hunter@nokia.com> wrote:
> Brijesh Singh wrote:
>> On Wed, Feb 4, 2009 at 2:59 PM, Adrian Hunter
>> <ext-adrian.hunter@nokia.com> wrote:
>>> Brijesh Singh wrote:
>>>> On Tue, Feb 3, 2009 at 5:14 AM, Corentin Chary <corentin.chary@gmail.com>
>>>> wrote:
>>>>> On Mon, Feb 2, 2009 at 12:18 PM, Adrian Hunter
>>>>> <ext-adrian.hunter@nokia.com> wrote:
>>>>>> Artem Bityutskiy wrote:
>>>>>>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>>>>>>> I would suggest an intermediate step.  Create UBI2 which is
>>>>>>>> similar to UBI but stores eraseblock information in one place,
>>>>>>>> instead of at the beginning of each eraseblock.  Such an approach
>>>>>>>> might be OK up to as much as 64GiB, and would probably perform
>>>>>>>> better than a fully scalable version.
>>>>>>>>
>>>>>>>> Then look at creating UBI3, which is fully scalable.
>>>>>>> Yes, I assume UBI2 should store mapping/erasure information in separate
>>>>>>> tables, not in each eraseblock. So we should get rid of eraseblock
>>>>>>> headers.
>>>>>> Yes that is what I meant.  You could probably make do with as little as
>>>>>> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
>>>>>> would need 1536KiB table, which could be read in a second or two, so
>>>>>> mount time is OK.
>>>> Adrian,to my understanding, this is minimum info needed per physical
>>>> erase block...
>>>>
>>>> Erase count                   -8 bytes
>>>> Lnum                             -4 bytes
>>>> Volume ID                      -4 byte(Can make it 1 byte for now as
>>>> vol limit=128)
>>>> Header CRC                   -4 bytes(Only for static volumes.)
>>>> i.e. Minimum 20 bytes.  Is there any other way to make it 12?
>>> 8 bytes for erase counter is many more than needed i.e.
>>>        SLC NAND 100,000 - 1,000,000 max. erase cycles
>>>        MLC NAND 10000 - 10,000 max. erase cycles
>>>
>>> Leave out the header CRC for dynamic volumes
>>>
>>> Combine lnum and volume id.
>>>
>>> Maybe go so far as to pack the information into bit fields
>>> like LPT does. i.e. if the flash media only has a million
>>> eraseblocks then only 20 bits are needed for lnum.  Maybe it
>>> is MLC NAND, so say 15 bits for erase counter.  That leaves 5
>>> bites for volume id, and fits into 5 bytes for dynmaic volumes.
>>
>> Makes sense.
>>
>>>> And how to update the table relatively efficiently?
>>> Each update to UBI typically requires writing a whole NAND
>>> page.  That page can be filled with unchanged information
>>> from the first eraseblock of UBI information.  Hence after
>>> enough updates the first eraseblock will end up containing
>>> only out-of-date information and can then be unmapped.
>>
>> Does it mean there is no separate commit block?And do we move the
>> journal with valid entries when it is full?
>
> I was describing my idea for UBI2.  There would be no journal,
> no commit.  When writing new mappings, also write some existing
> mappings from one of the eraseblocks until it no longer
> contains any needed information.  It is like garbage-collection
> as you go.
OK.
>> I find some problems with it.
>> 1) Why process extra information for each write?
>> 2) We will need to scan the entire journal for each mount.
>> 3) Will work well with only NAND.
>> Instead, if there is a separate commit block, this can be read once
>> and processed.
>>
>> I was wondering, how about combining both the approaches. i.e. A
>> commit block and journal as you suggested?Commit time will be reduced
>> dramatically.(As One page now contains group info). And boot time will
>> be fixed for good unmounts. Besides, it is simple and can be easily
>> scaled.
>
> Are you talking here about UBI3?
No.Sorry,but I was looking at UBI2 in different way.I will write a
document then may be we can discuss this.It will take some time for
internal review.


Thanks and Regards,
Brijesh

Re: Regarding UBI scalability

[Artem Bityutskiy]

On Sun, 2009-02-08 at 19:31 +0900, Kyungmin Park wrote:
> One more requested feature.
> How about to scan ubi image and bad block table at simultaneously?
> Now there's two full device scan, bbt and ubi at booting time.
> As internal LEA mapping layout, how about to add bbt layout?
> 
> It's also helpful to MLC since MLC doesn't have read oob so it calls
> page read command to build bbt.
> As you know it takes long time.
> 
> I'm not sure if internal LEA maping is supported, it's meaningful work or not.
> 
> How do you think?

Well, doing scanning twice is not very good indeed. I guess what you
could do is to make MTD avoid scanning and building the bad block
table at all and build it lazily. But then you need 2 bits per
eraseblock, not just one. IOW, sure, it is possible to optimize this.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: Regarding UBI scalability

[Kyungmin Park]

Hi,

On Sun, Feb 8, 2009 at 6:48 PM, Corentin Chary <corentin.chary@gmail.com> wrote:
> On Thu, Feb 5, 2009 at 10:40 AM, Brijesh Singh <brij.singh@samsung.com> wrote:
>> On Wed, Feb 4, 2009 at 3:17 PM, Adrian Hunter
>> <ext-adrian.hunter@nokia.com> wrote:
>>> ext BRIJESH SINGH wrote:
>>>> Hi,
>>>>
>>>> Artem Bityutskiy wrote:
>>>>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>>>>> I would suggest an intermediate step.  Create UBI2 which is
>>>>>> similar to UBI but stores eraseblock information in one place,
>>>>>> instead of at the beginning of each eraseblock.  Such an approach
>>>>>> might be OK up to as much as 64GiB, and would probably perform
>>>>>> better than a fully scalable version.
>>>>>>
>>>>>> Then look at creating UBI3, which is fully scalable.
>>>>> Yes, I assume UBI2 should store mapping/erasure information in separate
>>>>> tables, not in each eraseblock. So we should get rid of eraseblock
>>>>> headers.
>>>>
>>>> Yes that is what I meant.  You could probably make do with as little as
>>>> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
>>>> would need 1536KiB table, which could be read in a second or two, so
>>>> mount time is OK.
>>>>
>>>> I have an idea for how to update the table relatively efficiently if you
>>>> are interested.
>>>>
>>>> I am definitely interested. But apart from on flash headers, I am also interested in memory consumption scaling.
>>>> UBIFS solved this problem quite interestingly. Can something similar be borrowed for UBI?
>>>>
>>>> Thanks and Regards,
>>>> Brijesh
>>>
>>> I would leave the memory consumption issue for UBI3.
>
> As you are working on UBI2, have you a git tree or something ? I may
> have some time to help :)
> Thanks
>

One more requested feature.
How about to scan ubi image and bad block table at simultaneously?
Now there's two full device scan, bbt and ubi at booting time.
As internal LEA mapping layout, how about to add bbt layout?

It's also helpful to MLC since MLC doesn't have read oob so it calls
page read command to build bbt.
As you know it takes long time.

I'm not sure if internal LEA maping is supported, it's meaningful work or not.

How do you think?

Thank you,
Kyungmin Park

Re: Regarding UBI scalability

[Corentin Chary]

On Thu, Feb 5, 2009 at 10:40 AM, Brijesh Singh <brij.singh@samsung.com> wrote:
> On Wed, Feb 4, 2009 at 3:17 PM, Adrian Hunter
> <ext-adrian.hunter@nokia.com> wrote:
>> ext BRIJESH SINGH wrote:
>>> Hi,
>>>
>>> Artem Bityutskiy wrote:
>>>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>>>> I would suggest an intermediate step.  Create UBI2 which is
>>>>> similar to UBI but stores eraseblock information in one place,
>>>>> instead of at the beginning of each eraseblock.  Such an approach
>>>>> might be OK up to as much as 64GiB, and would probably perform
>>>>> better than a fully scalable version.
>>>>>
>>>>> Then look at creating UBI3, which is fully scalable.
>>>> Yes, I assume UBI2 should store mapping/erasure information in separate
>>>> tables, not in each eraseblock. So we should get rid of eraseblock
>>>> headers.
>>>
>>> Yes that is what I meant.  You could probably make do with as little as
>>> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
>>> would need 1536KiB table, which could be read in a second or two, so
>>> mount time is OK.
>>>
>>> I have an idea for how to update the table relatively efficiently if you
>>> are interested.
>>>
>>> I am definitely interested. But apart from on flash headers, I am also interested in memory consumption scaling.
>>> UBIFS solved this problem quite interestingly. Can something similar be borrowed for UBI?
>>>
>>> Thanks and Regards,
>>> Brijesh
>>
>> I would leave the memory consumption issue for UBI3.

As you are working on UBI2, have you a git tree or something ? I may
have some time to help :)
Thanks

-- 
Corentin Chary
http://xf.iksaif.net

Re: Regarding UBI scalability

[Brijesh Singh]

On Wed, Feb 4, 2009 at 3:17 PM, Adrian Hunter
<ext-adrian.hunter@nokia.com> wrote:
> ext BRIJESH SINGH wrote:
>> Hi,
>>
>> Artem Bityutskiy wrote:
>>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>>> I would suggest an intermediate step.  Create UBI2 which is
>>>> similar to UBI but stores eraseblock information in one place,
>>>> instead of at the beginning of each eraseblock.  Such an approach
>>>> might be OK up to as much as 64GiB, and would probably perform
>>>> better than a fully scalable version.
>>>>
>>>> Then look at creating UBI3, which is fully scalable.
>>> Yes, I assume UBI2 should store mapping/erasure information in separate
>>> tables, not in each eraseblock. So we should get rid of eraseblock
>>> headers.
>>
>> Yes that is what I meant.  You could probably make do with as little as
>> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
>> would need 1536KiB table, which could be read in a second or two, so
>> mount time is OK.
>>
>> I have an idea for how to update the table relatively efficiently if you
>> are interested.
>>
>> I am definitely interested. But apart from on flash headers, I am also interested in memory consumption scaling.
>> UBIFS solved this problem quite interestingly. Can something similar be borrowed for UBI?
>>
>> Thanks and Regards,
>> Brijesh
>
> I would leave the memory consumption issue for UBI3.
>
> Do you have a target memory consumption in mind?
Yes,this needs to be done.I agree with the approach, better to keep it for UBI3.

Re: Regarding UBI scalability

[Adrian Hunter]

ext BRIJESH SINGH wrote:
> Hi,
> 
> Artem Bityutskiy wrote:
>> On Mon, 2009-02-02 at 13:07 +0200, Adrian Hunter wrote:
>>> I would suggest an intermediate step.  Create UBI2 which is
>>> similar to UBI but stores eraseblock information in one place,
>>> instead of at the beginning of each eraseblock.  Such an approach
>>> might be OK up to as much as 64GiB, and would probably perform
>>> better than a fully scalable version.
>>>
>>> Then look at creating UBI3, which is fully scalable.
>> Yes, I assume UBI2 should store mapping/erasure information in separate
>> tables, not in each eraseblock. So we should get rid of eraseblock
>> headers.
> 
> Yes that is what I meant.  You could probably make do with as little as
> 12 bytes per eraseblock so a 64GiB flash with 512KiB eraseblock size
> would need 1536KiB table, which could be read in a second or two, so
> mount time is OK.
> 
> I have an idea for how to update the table relatively efficiently if you
> are interested.
> 
> I am definitely interested. But apart from on flash headers, I am also interested in memory consumption scaling.
> UBIFS solved this problem quite interestingly. Can something similar be borrowed for UBI?
> 
> Thanks and Regards,
> Brijesh

I would leave the memory consumption issue for UBI3.

Do you have a target memory consumption in mind?