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: <4FB38FAA.4080603@nod.at>
Date:	Wed, 16 May 2012 13:29:46 +0200
From:	Richard Weinberger <richard@....at>
To:	dedekind1@...il.com
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 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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/