[RFC v4] UBI: Fastmap support (aka checkpointing)

[Richard Weinberger]

On 16.05.2012 13:18, Artem Bityutskiy wrote:
> On Wed, 2012-05-16 at 14:09 +0300, Artem Bityutskiy wrote:
>>> The maximum size of a fastmap is limited to UBI_FM_MAX_BLOCKS.
>>> As I said, in worst case we'd have to scan 192 PEBs, which is a constant.
>>
>> In this case you cannot use O notation at all because it is just used
>> when talking about asymptotic things.
>
> OK, we are talking about different things. It is fine that you need to
> scan 192 eraseblocks, this is kind of your journal. And this part may be
> O(1). But there is another part as well.

Yeah, seems to.

> But as I already explained, you have a _table_ on the flash, and this
> table stores Erase Counter and LEB number for (roughly) each PEB. The
> more PEBs, the large is the table, linerarly.
>
> As I explained, you have to _read_ and _interpret_ each record in this
> table when attaching. And the more of these records you have, the longer
> it takes to attach. And this is where you have your O(N).

Okay, now I understand your point. :)

> So basically fastmap makes UBI's linerar dependency multiplier a lot
> smaller, so it is still a great improvement.

Yep.

Thanks,
//richard