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: <1337167083.24809.49.camel@sauron.fi.intel.com>
Date:	Wed, 16 May 2012 14:18:03 +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 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

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