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

[Artem Bityutskiy]

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.

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

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

-- 
Best Regards,
Artem Bityutskiy
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
URL: <http://lists.infradead.org/pipermail/linux-mtd/attachments/20120516/0e0841d3/attachment.sig>