linux-kernel - Re: [RFC v4] UBI: Fastmap support (aka checkpointing)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1337161096.24809.36.camel@sauron.fi.intel.com>
Date:	Wed, 16 May 2012 12:38:16 +0300
From:	Artem Bityutskiy <dedekind1@...il.com>
To:	Richard Weinberger <richard@....at>
Cc:	linux-mtd@...ts.infradead.org, tglx@...utronix.de,
	linux-kernel@...r.kernel.org, Heinz.Egger@...utronix.de,
	tim.bird@...sony.com
Subject: Re: [RFC v4] UBI: Fastmap support (aka checkpointing)

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

Download attachment "signature.asc" of type "application/pgp-signature" (837 bytes)