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

From: Richard Weinberger
Date: Wed May 16 2012 - 07:29:46 EST


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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/