Regarding UBI scalability

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.

Quoted 10 lines

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

Quoted 4 lines

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.

Quoted 3 lines

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.

Signature · 2 lines

Best regards,
Artem Bityutskiy (???????? ?????)

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

Hi
----- Original Message -----
From: "Artem Bityutskiy" <[email protected]>
To: <[email protected]>
Cc: <[email protected]>
Sent: Monday, February 02, 2009 3:01 PM
Subject: Re: Regarding UBI scalability

Quoted 38 lines · BRIJESH SINGH

Quoted 10 lines

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

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 8 lines

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.

Quoted 6 lines · Adrian Hunter

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.

Quoted 1 line

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.

Quoted 9 lines · Artem Bityutskiy

Quoted 7 lines · Adrian Hunter

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.

Quoted 3 lines

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.

Quoted 10 lines · Adrian Hunter

Quoted 9 lines · Artem Bityutskiy

Quoted 7 lines · Adrian Hunter

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.

Quoted 8 lines

Quoted 3 lines

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 ?

Quoted 12 lines · Corentin Chary

Quoted 10 lines · Adrian Hunter

Quoted 9 lines · Artem Bityutskiy

Quoted 7 lines · Adrian Hunter

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.

Quoted 8 lines

Quoted 8 lines

Quoted 3 lines

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

Quoted 2 lines · Artem Bityutskiy

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.

Quoted 10 lines · Corentin Chary

Quoted 8 lines · Adrian Hunter

Quoted 7 lines · Artem Bityutskiy

Quoted 6 lines · Adrian Hunter

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.

Quoted 8 lines

Quoted 8 lines

Quoted 4 lines

Quoted 1 line

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?

Quoted 3 lines

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

Quoted 31 lines · Brijesh Singh

Quoted 16 lines · Corentin Chary

Quoted 13 lines · Adrian Hunter

Quoted 11 lines · Artem Bityutskiy

Quoted 8 lines · Adrian Hunter

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.

Quoted 8 lines

Quoted 8 lines

Quoted 3 lines

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...

Quoted 6 lines

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.

Quoted 1 line

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.

Quoted 36 lines · Adrian Hunter

Quoted 23 lines · Brijesh Singh

Quoted 10 lines · Corentin Chary

Quoted 8 lines · Adrian Hunter

Quoted 7 lines · Artem Bityutskiy

Quoted 6 lines · Adrian Hunter

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.

Quoted 8 lines

Quoted 8 lines

Quoted 4 lines

Quoted 1 line

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...

Quoted 6 lines

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

Quoted 7 lines

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.

Quoted 1 line

Quoted 1 line

And how to update the table relatively efficiently?

Quoted 5 lines

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.

Quoted 55 lines · Brijesh Singh

Quoted 36 lines · Adrian Hunter

Quoted 23 lines · Brijesh Singh

Quoted 10 lines · Corentin Chary

Quoted 8 lines · Adrian Hunter

Quoted 7 lines · Artem Bityutskiy

Quoted 6 lines · Adrian Hunter

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.

Quoted 8 lines

Quoted 8 lines

Quoted 4 lines

Quoted 1 line

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...

Quoted 6 lines

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

Quoted 7 lines

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.

Quoted 6 lines

Quoted 1 line

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.

Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 5 lines

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?

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.

Quoted 5 lines · Corentin Chary

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.

= 512 B (sometime 2KB), a journal for map/unmap operation will take

Quoted 8 lines · Artem Bityutskiy

Quoted 5 lines · Corentin Chary

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

Quoted 1 line

= 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.

Quoted 8 lines · Artem Bityutskiy

Quoted 5 lines · Corentin Chary

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

Quoted 1 line

= 512 B (sometime 2KB), a journal for map/unmap operation will take

some time before being written.