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

[Artem Bityutskiy]

On Tue, 2012-05-15 at 19:11 +0200, Richard Weinberger wrote:
> We observe that attaching by scanning depends on the total size N of the UBI
> device.It has a complexity of O(N).
> Whereas attaching by fastmap has a nearly constant attaching time.
> In the best case fastmap has to scan only one PEB.

The improvement is impressive, but again it is not O(1), strictly
speaking. It is still O(N).

> This case can happen if the complete fastmap fits into one PEB, the fastmap
> super block is the first PEB on the MTD partition and the fastmap pool is empty.
> On the other side, in the worst case fastmap has to scan UBI_FM_MAX_START +
> UBI_FM_MAX_BLOCKS + UBI_FM_MAX_POOL_SIZE PEBs.

When N -> inf, UBI_FM_MAX_BLOCKS -> inf as well. Each PEB requires
little space in the fastmap table.

O(N) would be: N -> inf, UBI_FM_MAX_BLOCKS -> C, where C is a constant.

Or did I completely forgot math basics?

> With the current default settings this would be 192 PEBs.
> So, attaching via fastmap has a complexity of O(1).

No :-) Again, for each PEB you have a little data structure in a fastmap
which you have to (a) store, (b) read, and (c) process when attaching
the device. The more PEBs you have, the more you do.

It is OK, and it is a great improvement anyway!

-- 
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/bc67f54e/attachment.sig>