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

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

[Richard Weinberger]

v1: https://lwn.net/Articles/481612/
v2: https://lwn.net/Articles/496586/
v3: Didn't release it to linux-mtd

Changes since v1:
        - renamed it to UBIVIS (at least in Kconfig)
        - UBIVIS parameters are now configurable via Kconfig
        - several bugs have been fixed (design and implementation bugs)
        - added lots of comments to make the review process easier
        - made checkpatch.pl happy

Changes since v2:
        - minor bugs have been fixed
        - renamed it to UBI fastmap (as Artem requested)

Changes since v3:
        - changed the on-flash layout (added padding fields, turned the
          EBA storage into an array)
        - fixed some corner cases (the protection queue needed some extra work)
	- removed the data type hint logic
	- rebased to Artems mtd tree

[PATCH 1/7] [RFC] UBI: Export next_sqnum()
[PATCH 2/7] [RFC] UBI: Export compare_lebs()
[PATCH 3/7] [RFC] UBI: Add fastmap on-flash layout
[PATCH 4/7] [RFC] UBI: Add fastmap structs to ubi_device
[PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware
[PATCH 6/7] [RFC] UBI: Implement fastmapping support
[PATCH 7/7] [RFC] UBI: Wire up fastmap support

git://git.kernel.org/pub/scm/linux/kernel/git/rw/ubi2.git ubi2/v4

Some benchmark numbers:

4GiB NAND
Erase block size: 1MiB
Page size: 4096
Total PEBs: 4081*

Attach method   Time**          #scanned PEBs
---------------------------------------------
scanning        0m4.568s        4081
fastmap         0m0.486s        3


2GiB NAND
Erase block size: 1MiB
Page size: 4096
Total PEBs: 2062*

Attach method   Time            #scanned PEBs
---------------------------------------------
scanning        0m2.440s        2062
fastmap         0m0.439s        3


1GiB NAND
Erase block size: 1MiB
Page size: 4096
Total PEBs: 1038*

Attach method   Time            #scanned PEBs
---------------------------------------------
scanning        0m1.351s        1038
fastmap         0m0.422s        4


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.
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.
With the current default settings this would be 192 PEBs.
So, attaching via fastmap has a complexity of O(1).
I think we can reduce UBI_FM_MAX_BLOCKS and UBI_FM_MAX_POOL_SIZE to a much
smaller value. On most real NAND chips the whole fastmap fits into one PEB.

TODO:
        - Artem is fully happy with the current on-flash layout,
          maybe I can merge the erase counters into the EBA table
        - Get a full review :)

Thanks,
//richard

*) Didn't use the full NAND for UBI because Kernel, U-Boot, DT needed also
some space.

**) Time was taken by: "time ubiattach -m 5"

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

[Richard Weinberger]

v1: https://lwn.net/Articles/481612/
v2: https://lwn.net/Articles/496586/
v3: Didn't release it to linux-mtd

Changes since v1:
        - renamed it to UBIVIS (at least in Kconfig)
        - UBIVIS parameters are now configurable via Kconfig
        - several bugs have been fixed (design and implementation bugs)
        - added lots of comments to make the review process easier
        - made checkpatch.pl happy

Changes since v2:
        - minor bugs have been fixed
        - renamed it to UBI fastmap (as Artem requested)

Changes since v3:
        - changed the on-flash layout (added padding fields, turned the
          EBA storage into an array)
        - fixed some corner cases (the protection queue needed some extra work)
	- removed the data type hint logic
	- rebased to Artems mtd tree

[PATCH 1/7] [RFC] UBI: Export next_sqnum()
[PATCH 2/7] [RFC] UBI: Export compare_lebs()
[PATCH 3/7] [RFC] UBI: Add fastmap on-flash layout
[PATCH 4/7] [RFC] UBI: Add fastmap structs to ubi_device
[PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware
[PATCH 6/7] [RFC] UBI: Implement fastmapping support
[PATCH 7/7] [RFC] UBI: Wire up fastmap support

git://git.kernel.org/pub/scm/linux/kernel/git/rw/ubi2.git ubi2/v4

Some benchmark numbers:

4GiB NAND
Erase block size: 1MiB
Page size: 4096
Total PEBs: 4081*

Attach method   Time**          #scanned PEBs
---------------------------------------------
scanning        0m4.568s        4081
fastmap         0m0.486s        3


2GiB NAND
Erase block size: 1MiB
Page size: 4096
Total PEBs: 2062*

Attach method   Time            #scanned PEBs
---------------------------------------------
scanning        0m2.440s        2062
fastmap         0m0.439s        3


1GiB NAND
Erase block size: 1MiB
Page size: 4096
Total PEBs: 1038*

Attach method   Time            #scanned PEBs
---------------------------------------------
scanning        0m1.351s        1038
fastmap         0m0.422s        4


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.
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.
With the current default settings this would be 192 PEBs.
So, attaching via fastmap has a complexity of O(1).
I think we can reduce UBI_FM_MAX_BLOCKS and UBI_FM_MAX_POOL_SIZE to a much
smaller value. On most real NAND chips the whole fastmap fits into one PEB.

TODO:
        - Artem is fully happy with the current on-flash layout,
          maybe I can merge the erase counters into the EBA table
        - Get a full review :)

Thanks,
//richard

*) Didn't use the full NAND for UBI because Kernel, U-Boot, DT needed also
some space.

**) Time was taken by: "time ubiattach -m 5"

[PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Richard Weinberger]

The fastmap mechanism needs to read the next sequence nummber
directly.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/eba.c |   18 +++++++++---------
 drivers/mtd/ubi/ubi.h |    1 +
 2 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/drivers/mtd/ubi/eba.c b/drivers/mtd/ubi/eba.c
index bd5fdbf..d75677d 100644
--- a/drivers/mtd/ubi/eba.c
+++ b/drivers/mtd/ubi/eba.c
@@ -57,7 +57,7 @@
  * global sequence counter value. It also increases the global sequence
  * counter.
  */
-static unsigned long long next_sqnum(struct ubi_device *ubi)
+unsigned long long ubi_next_sqnum(struct ubi_device *ubi)
 {
 	unsigned long long sqnum;
 
@@ -522,7 +522,7 @@ retry:
 		goto out_put;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	err = ubi_io_write_vid_hdr(ubi, new_pnum, vid_hdr);
 	if (err)
 		goto write_error;
@@ -633,7 +633,7 @@ int ubi_eba_write_leb(struct ubi_device *ubi, struct ubi_volume *vol, int lnum,
 	}
 
 	vid_hdr->vol_type = UBI_VID_DYNAMIC;
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	vid_hdr->vol_id = cpu_to_be32(vol_id);
 	vid_hdr->lnum = cpu_to_be32(lnum);
 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
@@ -694,7 +694,7 @@ write_error:
 		return err;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	ubi_msg("try another PEB");
 	goto retry;
 }
@@ -747,7 +747,7 @@ int ubi_eba_write_leb_st(struct ubi_device *ubi, struct ubi_volume *vol,
 		return err;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	vid_hdr->vol_id = cpu_to_be32(vol_id);
 	vid_hdr->lnum = cpu_to_be32(lnum);
 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
@@ -812,7 +812,7 @@ write_error:
 		return err;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	ubi_msg("try another PEB");
 	goto retry;
 }
@@ -864,7 +864,7 @@ int ubi_eba_atomic_leb_change(struct ubi_device *ubi, struct ubi_volume *vol,
 	if (err)
 		goto out_mutex;
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	vid_hdr->vol_id = cpu_to_be32(vol_id);
 	vid_hdr->lnum = cpu_to_be32(lnum);
 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
@@ -932,7 +932,7 @@ write_error:
 		goto out_leb_unlock;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	ubi_msg("try another PEB");
 	goto retry;
 }
@@ -1092,7 +1092,7 @@ int ubi_eba_copy_leb(struct ubi_device *ubi, int from, int to,
 		vid_hdr->data_size = cpu_to_be32(data_size);
 		vid_hdr->data_crc = cpu_to_be32(crc);
 	}
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 
 	err = ubi_io_write_vid_hdr(ubi, to, vid_hdr);
 	if (err) {
diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 75b9f1c..00c48f6 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -530,6 +530,7 @@ int ubi_eba_atomic_leb_change(struct ubi_device *ubi, struct ubi_volume *vol,
 int ubi_eba_copy_leb(struct ubi_device *ubi, int from, int to,
 		     struct ubi_vid_hdr *vid_hdr);
 int ubi_eba_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si);
+unsigned long long ubi_next_sqnum(struct ubi_device *ubi);
 
 /* wl.c */
 int ubi_wl_get_peb(struct ubi_device *ubi);
-- 
1.7.6.5

[PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Richard Weinberger]

The fastmap mechanism needs to read the next sequence nummber
directly.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/eba.c |   18 +++++++++---------
 drivers/mtd/ubi/ubi.h |    1 +
 2 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/drivers/mtd/ubi/eba.c b/drivers/mtd/ubi/eba.c
index bd5fdbf..d75677d 100644
--- a/drivers/mtd/ubi/eba.c
+++ b/drivers/mtd/ubi/eba.c
@@ -57,7 +57,7 @@
  * global sequence counter value. It also increases the global sequence
  * counter.
  */
-static unsigned long long next_sqnum(struct ubi_device *ubi)
+unsigned long long ubi_next_sqnum(struct ubi_device *ubi)
 {
 	unsigned long long sqnum;
 
@@ -522,7 +522,7 @@ retry:
 		goto out_put;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	err = ubi_io_write_vid_hdr(ubi, new_pnum, vid_hdr);
 	if (err)
 		goto write_error;
@@ -633,7 +633,7 @@ int ubi_eba_write_leb(struct ubi_device *ubi, struct ubi_volume *vol, int lnum,
 	}
 
 	vid_hdr->vol_type = UBI_VID_DYNAMIC;
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	vid_hdr->vol_id = cpu_to_be32(vol_id);
 	vid_hdr->lnum = cpu_to_be32(lnum);
 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
@@ -694,7 +694,7 @@ write_error:
 		return err;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	ubi_msg("try another PEB");
 	goto retry;
 }
@@ -747,7 +747,7 @@ int ubi_eba_write_leb_st(struct ubi_device *ubi, struct ubi_volume *vol,
 		return err;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	vid_hdr->vol_id = cpu_to_be32(vol_id);
 	vid_hdr->lnum = cpu_to_be32(lnum);
 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
@@ -812,7 +812,7 @@ write_error:
 		return err;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	ubi_msg("try another PEB");
 	goto retry;
 }
@@ -864,7 +864,7 @@ int ubi_eba_atomic_leb_change(struct ubi_device *ubi, struct ubi_volume *vol,
 	if (err)
 		goto out_mutex;
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	vid_hdr->vol_id = cpu_to_be32(vol_id);
 	vid_hdr->lnum = cpu_to_be32(lnum);
 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
@@ -932,7 +932,7 @@ write_error:
 		goto out_leb_unlock;
 	}
 
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 	ubi_msg("try another PEB");
 	goto retry;
 }
@@ -1092,7 +1092,7 @@ int ubi_eba_copy_leb(struct ubi_device *ubi, int from, int to,
 		vid_hdr->data_size = cpu_to_be32(data_size);
 		vid_hdr->data_crc = cpu_to_be32(crc);
 	}
-	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
+	vid_hdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
 
 	err = ubi_io_write_vid_hdr(ubi, to, vid_hdr);
 	if (err) {
diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 75b9f1c..00c48f6 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -530,6 +530,7 @@ int ubi_eba_atomic_leb_change(struct ubi_device *ubi, struct ubi_volume *vol,
 int ubi_eba_copy_leb(struct ubi_device *ubi, int from, int to,
 		     struct ubi_vid_hdr *vid_hdr);
 int ubi_eba_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si);
+unsigned long long ubi_next_sqnum(struct ubi_device *ubi);
 
 /* wl.c */
 int ubi_wl_get_peb(struct ubi_device *ubi);
-- 
1.7.6.5

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 3591 bytes --]

On Tue, 2012-05-15 at 19:11 +0200, Richard Weinberger wrote:
> The fastmap mechanism needs to read the next sequence nummber
> directly.
> 
> Signed-off-by: Richard Weinberger <richard@nod.at>

I started looking at the code, and made some notes at the same time and
few minor changes - here is the diff which you can apply on top of your
patches.

diff --git a/drivers/mtd/ubi/build.c b/drivers/mtd/ubi/build.c
index 2399511..2f5c362 100644
--- a/drivers/mtd/ubi/build.c
+++ b/drivers/mtd/ubi/build.c
@@ -869,15 +869,22 @@ static int attach_by_fastmap(struct ubi_device *ubi)
 
 	fm_start = ubi_find_fastmap(ubi);
 	if (fm_start < 0)
+		/* TODO: instead, return 1 which means that fall-back to
+		 * scanning is needed */
 		return -ENOENT;
 
+	/* TODO: we need to re-name scan.h to attach.h, scan_info to
+	 * attach_info, si to ai, seb to aeb, and so on - because we share the
+	 * same data structures between scanning and fastmap, so the word
+	 * "scan" is not very sensible to have in the name any more.
+	 */
 	si = ubi_read_fastmap(ubi, fm_start);
 	if (IS_ERR(si))
 		return PTR_ERR(si);
 
-	ubi->bad_peb_count = 0;
+	/* TODO: the rest looks very much like attach_by_scanning() - we
+	 * need to re-structure the code and avoid duplication */
 	ubi->good_peb_count = ubi->peb_count;
-	ubi->corr_peb_count = 0;
 	ubi->max_ec = si->max_ec;
 	ubi->mean_ec = si->mean_ec;
 	ubi_msg("max. sequence number:       %llu", si->max_sqnum);
@@ -888,6 +895,7 @@ static int attach_by_fastmap(struct ubi_device *ubi)
 		goto out_si;
 	}
 
+	/* TODO: the _scan suffix makes no sens anymore - kill it */
 	err = ubi_wl_init_scan(ubi, si);
 	if (err) {
 		ubi_err("ubi_wl_init_scan failed!");
@@ -1022,7 +1030,7 @@ int ubi_attach_mtd_dev(struct mtd_info *mtd, int ubi_num, int vid_hdr_offset)
 	err = attach_by_fastmap(ubi);
 	if (err) {
 		if (err != -ENOENT)
-			ubi_msg("falling back to attach by scanning mode!");
+			ubi_msg("falling back to attach by scanning");
 
 		ubi->attached_by_scanning = true;
 		err = attach_by_scanning(ubi);
diff --git a/drivers/mtd/ubi/fastmap.c b/drivers/mtd/ubi/fastmap.c
index 2ea1682..7c5f1f7 100644
--- a/drivers/mtd/ubi/fastmap.c
+++ b/drivers/mtd/ubi/fastmap.c
@@ -582,7 +582,12 @@ struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
 		goto out;
 	}
 
+	/* TODO: Before checking version - check the CRC.
+	 * I think you need to add a separate helper function in io.c, similar
+	 * to ubi_io_read_vid_hdr(). */
 	if (fmsb->version != UBI_FM_FMT_VERSION) {
+		/* TODO: we can fall back to scanning instead of saying good
+		 * bye! */
 		ubi_err("Unknown fastmap format version!");
 		si = ERR_PTR(-EINVAL);
 		kfree(fmsb);
@@ -606,6 +611,7 @@ struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
 	if (!fm_raw) {
 		si = ERR_PTR(-ENOMEM);
 		kfree(fmsb);
+		/* TODO: goto? */
 	}
 
 	vh = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
@@ -617,6 +623,9 @@ struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
 	}
 
 	for (i = 0; i < nblocks; i++) {
+		/* TODO: you basically perform the scanning here - you should
+		 * share the same code as we use in scan.c: use process_peb().
+		 */
 		ret = ubi_io_read_vid_hdr(ubi, be32_to_cpu(fmsb->block_loc[i]),
 			vh, 0);
 		if (ret) {
@@ -653,6 +662,7 @@ struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
 				i, be32_to_cpu(fmsb->block_loc[i]));
 			si = ERR_PTR(ret);
 
+			/* TODO: fsmb is not freed? */
 			goto free_vhdr;
 		}
 	}


-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 3591 bytes --]

On Tue, 2012-05-15 at 19:11 +0200, Richard Weinberger wrote:
> The fastmap mechanism needs to read the next sequence nummber
> directly.
> 
> Signed-off-by: Richard Weinberger <richard@nod.at>

I started looking at the code, and made some notes at the same time and
few minor changes - here is the diff which you can apply on top of your
patches.

diff --git a/drivers/mtd/ubi/build.c b/drivers/mtd/ubi/build.c
index 2399511..2f5c362 100644
--- a/drivers/mtd/ubi/build.c
+++ b/drivers/mtd/ubi/build.c
@@ -869,15 +869,22 @@ static int attach_by_fastmap(struct ubi_device *ubi)
 
 	fm_start = ubi_find_fastmap(ubi);
 	if (fm_start < 0)
+		/* TODO: instead, return 1 which means that fall-back to
+		 * scanning is needed */
 		return -ENOENT;
 
+	/* TODO: we need to re-name scan.h to attach.h, scan_info to
+	 * attach_info, si to ai, seb to aeb, and so on - because we share the
+	 * same data structures between scanning and fastmap, so the word
+	 * "scan" is not very sensible to have in the name any more.
+	 */
 	si = ubi_read_fastmap(ubi, fm_start);
 	if (IS_ERR(si))
 		return PTR_ERR(si);
 
-	ubi->bad_peb_count = 0;
+	/* TODO: the rest looks very much like attach_by_scanning() - we
+	 * need to re-structure the code and avoid duplication */
 	ubi->good_peb_count = ubi->peb_count;
-	ubi->corr_peb_count = 0;
 	ubi->max_ec = si->max_ec;
 	ubi->mean_ec = si->mean_ec;
 	ubi_msg("max. sequence number:       %llu", si->max_sqnum);
@@ -888,6 +895,7 @@ static int attach_by_fastmap(struct ubi_device *ubi)
 		goto out_si;
 	}
 
+	/* TODO: the _scan suffix makes no sens anymore - kill it */
 	err = ubi_wl_init_scan(ubi, si);
 	if (err) {
 		ubi_err("ubi_wl_init_scan failed!");
@@ -1022,7 +1030,7 @@ int ubi_attach_mtd_dev(struct mtd_info *mtd, int ubi_num, int vid_hdr_offset)
 	err = attach_by_fastmap(ubi);
 	if (err) {
 		if (err != -ENOENT)
-			ubi_msg("falling back to attach by scanning mode!");
+			ubi_msg("falling back to attach by scanning");
 
 		ubi->attached_by_scanning = true;
 		err = attach_by_scanning(ubi);
diff --git a/drivers/mtd/ubi/fastmap.c b/drivers/mtd/ubi/fastmap.c
index 2ea1682..7c5f1f7 100644
--- a/drivers/mtd/ubi/fastmap.c
+++ b/drivers/mtd/ubi/fastmap.c
@@ -582,7 +582,12 @@ struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
 		goto out;
 	}
 
+	/* TODO: Before checking version - check the CRC.
+	 * I think you need to add a separate helper function in io.c, similar
+	 * to ubi_io_read_vid_hdr(). */
 	if (fmsb->version != UBI_FM_FMT_VERSION) {
+		/* TODO: we can fall back to scanning instead of saying good
+		 * bye! */
 		ubi_err("Unknown fastmap format version!");
 		si = ERR_PTR(-EINVAL);
 		kfree(fmsb);
@@ -606,6 +611,7 @@ struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
 	if (!fm_raw) {
 		si = ERR_PTR(-ENOMEM);
 		kfree(fmsb);
+		/* TODO: goto? */
 	}
 
 	vh = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
@@ -617,6 +623,9 @@ struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
 	}
 
 	for (i = 0; i < nblocks; i++) {
+		/* TODO: you basically perform the scanning here - you should
+		 * share the same code as we use in scan.c: use process_peb().
+		 */
 		ret = ubi_io_read_vid_hdr(ubi, be32_to_cpu(fmsb->block_loc[i]),
 			vh, 0);
 		if (ret) {
@@ -653,6 +662,7 @@ struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
 				i, be32_to_cpu(fmsb->block_loc[i]));
 			si = ERR_PTR(ret);
 
+			/* TODO: fsmb is not freed? */
 			goto free_vhdr;
 		}
 	}


-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Richard Weinberger]

On 16.05.2012 15:01, Artem Bityutskiy wrote:
> I started looking at the code, and made some notes at the same time and
> few minor changes - here is the diff which you can apply on top of your
> patches.
>
> diff --git a/drivers/mtd/ubi/build.c b/drivers/mtd/ubi/build.c
> index 2399511..2f5c362 100644
> --- a/drivers/mtd/ubi/build.c
> +++ b/drivers/mtd/ubi/build.c
> @@ -869,15 +869,22 @@ static int attach_by_fastmap(struct ubi_device *ubi)
>
>   	fm_start = ubi_find_fastmap(ubi);
>   	if (fm_start<  0)
> +		/* TODO: instead, return 1 which means that fall-back to
> +		 * scanning is needed */

fm_start is the PEB number of the fastmap super block.
It will return 1 if the super block was found at PEB 1.
That's why it returns a negative values in case of an error.

> +	/* TODO: Before checking version - check the CRC.

The CRC covers only the fastmap data, not the super block.

>   	for (i = 0; i<  nblocks; i++) {
> +		/* TODO: you basically perform the scanning here - you should
> +		 * share the same code as we use in scan.c: use process_peb().
> +		 */

What exactly do you mean by that?
process_eb() will not help much because the fastmap data is written 
"raw" to the flash. (Without any interaction from the WL sub-system)

I'll release v6 now and address all other issues in v7.

Thanks,
//richard

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Richard Weinberger]

On 16.05.2012 15:01, Artem Bityutskiy wrote:
> I started looking at the code, and made some notes at the same time and
> few minor changes - here is the diff which you can apply on top of your
> patches.
>
> diff --git a/drivers/mtd/ubi/build.c b/drivers/mtd/ubi/build.c
> index 2399511..2f5c362 100644
> --- a/drivers/mtd/ubi/build.c
> +++ b/drivers/mtd/ubi/build.c
> @@ -869,15 +869,22 @@ static int attach_by_fastmap(struct ubi_device *ubi)
>
>   	fm_start = ubi_find_fastmap(ubi);
>   	if (fm_start<  0)
> +		/* TODO: instead, return 1 which means that fall-back to
> +		 * scanning is needed */

fm_start is the PEB number of the fastmap super block.
It will return 1 if the super block was found at PEB 1.
That's why it returns a negative values in case of an error.

> +	/* TODO: Before checking version - check the CRC.

The CRC covers only the fastmap data, not the super block.

>   	for (i = 0; i<  nblocks; i++) {
> +		/* TODO: you basically perform the scanning here - you should
> +		 * share the same code as we use in scan.c: use process_peb().
> +		 */

What exactly do you mean by that?
process_eb() will not help much because the fastmap data is written 
"raw" to the flash. (Without any interaction from the WL sub-system)

I'll release v6 now and address all other issues in v7.

Thanks,
//richard

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 741 bytes --]

On Mon, 2012-05-21 at 15:34 +0200, Richard Weinberger wrote:
> > +	/* TODO: Before checking version - check the CRC.
> 
> The CRC covers only the fastmap data, not the super block.

Everything should be protected with CRC.

> >   	for (i = 0; i<  nblocks; i++) {
> > +		/* TODO: you basically perform the scanning here - you should
> > +		 * share the same code as we use in scan.c: use process_peb().
> > +		 */
> 
> What exactly do you mean by that?
> process_eb() will not help much because the fastmap data is written 
> "raw" to the flash. (Without any interaction from the WL sub-system)

It still contains EC and VID headers. So you can use the existing code
for scanning it.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 741 bytes --]

On Mon, 2012-05-21 at 15:34 +0200, Richard Weinberger wrote:
> > +	/* TODO: Before checking version - check the CRC.
> 
> The CRC covers only the fastmap data, not the super block.

Everything should be protected with CRC.

> >   	for (i = 0; i<  nblocks; i++) {
> > +		/* TODO: you basically perform the scanning here - you should
> > +		 * share the same code as we use in scan.c: use process_peb().
> > +		 */
> 
> What exactly do you mean by that?
> process_eb() will not help much because the fastmap data is written 
> "raw" to the flash. (Without any interaction from the WL sub-system)

It still contains EC and VID headers. So you can use the existing code
for scanning it.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Richard Weinberger]

On 21.05.2012 16:00, Artem Bityutskiy wrote:
> On Mon, 2012-05-21 at 15:34 +0200, Richard Weinberger wrote:
>>> +	/* TODO: Before checking version - check the CRC.
>>
>> The CRC covers only the fastmap data, not the super block.
>
> Everything should be protected with CRC.

Okay, done. :)

>>>    	for (i = 0; i<   nblocks; i++) {
>>> +		/* TODO: you basically perform the scanning here - you should
>>> +		 * share the same code as we use in scan.c: use process_peb().
>>> +		 */
>>
>> What exactly do you mean by that?
>> process_eb() will not help much because the fastmap data is written
>> "raw" to the flash. (Without any interaction from the WL sub-system)
>
> It still contains EC and VID headers. So you can use the existing code
> for scanning it.

I use already ubi_io_read_vid_hdr() and ubi_io_read_ec_hdr() what should 
I reuse?
Also checking the image sequence would make sense.

Thanks,
//richard

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Richard Weinberger]

On 21.05.2012 16:00, Artem Bityutskiy wrote:
> On Mon, 2012-05-21 at 15:34 +0200, Richard Weinberger wrote:
>>> +	/* TODO: Before checking version - check the CRC.
>>
>> The CRC covers only the fastmap data, not the super block.
>
> Everything should be protected with CRC.

Okay, done. :)

>>>    	for (i = 0; i<   nblocks; i++) {
>>> +		/* TODO: you basically perform the scanning here - you should
>>> +		 * share the same code as we use in scan.c: use process_peb().
>>> +		 */
>>
>> What exactly do you mean by that?
>> process_eb() will not help much because the fastmap data is written
>> "raw" to the flash. (Without any interaction from the WL sub-system)
>
> It still contains EC and VID headers. So you can use the existing code
> for scanning it.

I use already ubi_io_read_vid_hdr() and ubi_io_read_ec_hdr() what should 
I reuse?
Also checking the image sequence would make sense.

Thanks,
//richard

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1069 bytes --]

On Mon, 2012-05-21 at 16:16 +0200, Richard Weinberger wrote:
> > It still contains EC and VID headers. So you can use the existing code
> > for scanning it.
> 
> I use already ubi_io_read_vid_hdr() and ubi_io_read_ec_hdr() what should 
> I reuse?

As I wrote: 'process_eb()'. Now it is named 'scan_peb()' after the
renames.

It does all the work to scan PEB headers. Create a _separate_ 'struct
ubi_attach_info' run 'scan_peb()' for each PEB of the fastmap. Check for
errors, and sanity (all headers are there, no errors, etc, may be an
extra self-check function would be appropriate here). Then go through
the resulting fastmap volume attach info, read and process the fastmap
_contents_. Of course you need the second (real) attach info for the
data you read from the fastmep. This is what I call "reuse the existing"
code.

How does this sound to you?

> Also checking the image sequence would make sense.

Yes, you should check everything. If you reuse the code, you will get
this automatically, no?

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1069 bytes --]

On Mon, 2012-05-21 at 16:16 +0200, Richard Weinberger wrote:
> > It still contains EC and VID headers. So you can use the existing code
> > for scanning it.
> 
> I use already ubi_io_read_vid_hdr() and ubi_io_read_ec_hdr() what should 
> I reuse?

As I wrote: 'process_eb()'. Now it is named 'scan_peb()' after the
renames.

It does all the work to scan PEB headers. Create a _separate_ 'struct
ubi_attach_info' run 'scan_peb()' for each PEB of the fastmap. Check for
errors, and sanity (all headers are there, no errors, etc, may be an
extra self-check function would be appropriate here). Then go through
the resulting fastmap volume attach info, read and process the fastmap
_contents_. Of course you need the second (real) attach info for the
data you read from the fastmep. This is what I call "reuse the existing"
code.

How does this sound to you?

> Also checking the image sequence would make sense.

Yes, you should check everything. If you reuse the code, you will get
this automatically, no?

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 675 bytes --]

On Mon, 2012-05-21 at 15:34 +0200, Richard Weinberger wrote:
> >       fm_start = ubi_find_fastmap(ubi);
> >       if (fm_start<  0)
> > +             /* TODO: instead, return 1 which means that fall-back
> to
> > +              * scanning is needed */
> 
> fm_start is the PEB number of the fastmap super block.
> It will return 1 if the super block was found at PEB 1.
> That's why it returns a negative values in case of an error 

OK, if 1 does not work - use 2, introduce your own constant. Using
-EINVAL is simply incorrect. Check what happens if the MTD driver
returns -EINVAL when you call 'ubi_io_read_vid_hdr()'.
-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 675 bytes --]

On Mon, 2012-05-21 at 15:34 +0200, Richard Weinberger wrote:
> >       fm_start = ubi_find_fastmap(ubi);
> >       if (fm_start<  0)
> > +             /* TODO: instead, return 1 which means that fall-back
> to
> > +              * scanning is needed */
> 
> fm_start is the PEB number of the fastmap super block.
> It will return 1 if the super block was found at PEB 1.
> That's why it returns a negative values in case of an error 

OK, if 1 does not work - use 2, introduce your own constant. Using
-EINVAL is simply incorrect. Check what happens if the MTD driver
returns -EINVAL when you call 'ubi_io_read_vid_hdr()'.
-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Shmulik Ladkani]

Hi Richard,

On Tue, 15 May 2012 19:11:05 +0200 Richard Weinberger <richard@nod.at> wrote:
> The fastmap mechanism needs to read the next sequence nummber
> directly.
> 
> Signed-off-by: Richard Weinberger <richard@nod.at>
> ---
>  drivers/mtd/ubi/eba.c |   18 +++++++++---------
>  drivers/mtd/ubi/ubi.h |    1 +
>  2 files changed, 10 insertions(+), 9 deletions(-)
> 
> diff --git a/drivers/mtd/ubi/eba.c b/drivers/mtd/ubi/eba.c
> index bd5fdbf..d75677d 100644
> --- a/drivers/mtd/ubi/eba.c
> +++ b/drivers/mtd/ubi/eba.c
> @@ -57,7 +57,7 @@
>   * global sequence counter value. It also increases the global sequence
>   * counter.
>   */
> -static unsigned long long next_sqnum(struct ubi_device *ubi)
> +unsigned long long ubi_next_sqnum(struct ubi_device *ubi)

Minor nit.

Comment above the function should have been changed too.
(look for the "next_sqnum - get next sequence number" comment)

Other than that,
Reviewed-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>

Regards,
Shmulik

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Shmulik Ladkani]

Hi Richard,

On Tue, 15 May 2012 19:11:05 +0200 Richard Weinberger <richard@nod.at> wrote:
> The fastmap mechanism needs to read the next sequence nummber
> directly.
> 
> Signed-off-by: Richard Weinberger <richard@nod.at>
> ---
>  drivers/mtd/ubi/eba.c |   18 +++++++++---------
>  drivers/mtd/ubi/ubi.h |    1 +
>  2 files changed, 10 insertions(+), 9 deletions(-)
> 
> diff --git a/drivers/mtd/ubi/eba.c b/drivers/mtd/ubi/eba.c
> index bd5fdbf..d75677d 100644
> --- a/drivers/mtd/ubi/eba.c
> +++ b/drivers/mtd/ubi/eba.c
> @@ -57,7 +57,7 @@
>   * global sequence counter value. It also increases the global sequence
>   * counter.
>   */
> -static unsigned long long next_sqnum(struct ubi_device *ubi)
> +unsigned long long ubi_next_sqnum(struct ubi_device *ubi)

Minor nit.

Comment above the function should have been changed too.
(look for the "next_sqnum - get next sequence number" comment)

Other than that,
Reviewed-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>

Regards,
Shmulik

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 370 bytes --]

On Wed, 2012-05-16 at 17:03 +0300, Shmulik Ladkani wrote:
> Comment above the function should have been changed too.
> (look for the "next_sqnum - get next sequence number" comment)

I do not think we should make these non-static. We should re-use the
entire scan_peb() function instead to scan the fastmap internal volume.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 370 bytes --]

On Wed, 2012-05-16 at 17:03 +0300, Shmulik Ladkani wrote:
> Comment above the function should have been changed too.
> (look for the "next_sqnum - get next sequence number" comment)

I do not think we should make these non-static. We should re-use the
entire scan_peb() function instead to scan the fastmap internal volume.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Shmulik Ladkani]

Hi Artem,

On Wed, 16 May 2012 17:27:37 +0300 Artem Bityutskiy <dedekind1@gmail.com> wrote:
> On Wed, 2012-05-16 at 17:03 +0300, Shmulik Ladkani wrote:
> > Comment above the function should have been changed too.
> > (look for the "next_sqnum - get next sequence number" comment)
> 
> I do not think we should make these non-static. We should re-use the
> entire scan_peb() function instead to scan the fastmap internal volume.

Sorry, couldn't follow you.

The new (outside eba.c) calls to 'ubi_next_sqnum' are from
'ubi_write_fastmap' (called from the 'ubi_update_fastmap' interface,
implemented in fastmap.c) - during construction of VID headers of the
FM_SB and FM_FATA.

IMO this is reasonable.

Do you suggest to somehow use existing ubi_eba_write_xxx functions?
Or place the FM_SB/FM_DATA peb writing funtions into eba.c?

Regards,
Shmulik

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Shmulik Ladkani]

Hi Artem,

On Wed, 16 May 2012 17:27:37 +0300 Artem Bityutskiy <dedekind1@gmail.com> wrote:
> On Wed, 2012-05-16 at 17:03 +0300, Shmulik Ladkani wrote:
> > Comment above the function should have been changed too.
> > (look for the "next_sqnum - get next sequence number" comment)
> 
> I do not think we should make these non-static. We should re-use the
> entire scan_peb() function instead to scan the fastmap internal volume.

Sorry, couldn't follow you.

The new (outside eba.c) calls to 'ubi_next_sqnum' are from
'ubi_write_fastmap' (called from the 'ubi_update_fastmap' interface,
implemented in fastmap.c) - during construction of VID headers of the
FM_SB and FM_FATA.

IMO this is reasonable.

Do you suggest to somehow use existing ubi_eba_write_xxx functions?
Or place the FM_SB/FM_DATA peb writing funtions into eba.c?

Regards,
Shmulik

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1200 bytes --]

On Thu, 2012-05-17 at 12:45 +0300, Shmulik Ladkani wrote:
> Hi Artem,
> 
> On Wed, 16 May 2012 17:27:37 +0300 Artem Bityutskiy <dedekind1@gmail.com> wrote:
> > On Wed, 2012-05-16 at 17:03 +0300, Shmulik Ladkani wrote:
> > > Comment above the function should have been changed too.
> > > (look for the "next_sqnum - get next sequence number" comment)
> > 
> > I do not think we should make these non-static. We should re-use the
> > entire scan_peb() function instead to scan the fastmap internal volume.
> 
> Sorry, couldn't follow you.
> 
> The new (outside eba.c) calls to 'ubi_next_sqnum' are from
> 'ubi_write_fastmap' (called from the 'ubi_update_fastmap' interface,
> implemented in fastmap.c) - during construction of VID headers of the
> FM_SB and FM_FATA.
> 
> IMO this is reasonable.
> 
> Do you suggest to somehow use existing ubi_eba_write_xxx functions?
> Or place the FM_SB/FM_DATA peb writing funtions into eba.c?

I think I meant the compare_lebs() exporting, not this one, replied to
wrong e-mail, sorry. Happens when I am in hurry - try to keep everyone
happy and make sure Richard is always busy with something :-)

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1200 bytes --]

On Thu, 2012-05-17 at 12:45 +0300, Shmulik Ladkani wrote:
> Hi Artem,
> 
> On Wed, 16 May 2012 17:27:37 +0300 Artem Bityutskiy <dedekind1@gmail.com> wrote:
> > On Wed, 2012-05-16 at 17:03 +0300, Shmulik Ladkani wrote:
> > > Comment above the function should have been changed too.
> > > (look for the "next_sqnum - get next sequence number" comment)
> > 
> > I do not think we should make these non-static. We should re-use the
> > entire scan_peb() function instead to scan the fastmap internal volume.
> 
> Sorry, couldn't follow you.
> 
> The new (outside eba.c) calls to 'ubi_next_sqnum' are from
> 'ubi_write_fastmap' (called from the 'ubi_update_fastmap' interface,
> implemented in fastmap.c) - during construction of VID headers of the
> FM_SB and FM_FATA.
> 
> IMO this is reasonable.
> 
> Do you suggest to somehow use existing ubi_eba_write_xxx functions?
> Or place the FM_SB/FM_DATA peb writing funtions into eba.c?

I think I meant the compare_lebs() exporting, not this one, replied to
wrong e-mail, sorry. Happens when I am in hurry - try to keep everyone
happy and make sure Richard is always busy with something :-)

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Richard Weinberger]

[-- Attachment #1: Type: text/plain, Size: 331 bytes --]

Am 17.05.2012 13:44, schrieb Artem Bityutskiy:
 > I think I meant the compare_lebs() exporting, not this one, replied to
> wrong e-mail, sorry. Happens when I am in hurry - try to keep everyone
> happy and make sure Richard is always busy with something :-)
>

Haha.
No need to keep me busy. :P

Thanks,
//richard




[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Richard Weinberger]

[-- Attachment #1: Type: text/plain, Size: 331 bytes --]

Am 17.05.2012 13:44, schrieb Artem Bityutskiy:
 > I think I meant the compare_lebs() exporting, not this one, replied to
> wrong e-mail, sorry. Happens when I am in hurry - try to keep everyone
> happy and make sure Richard is always busy with something :-)
>

Haha.
No need to keep me busy. :P

Thanks,
//richard




[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 618 bytes --]

On Thu, 2012-05-17 at 13:47 +0200, Richard Weinberger wrote:
> Am 17.05.2012 13:44, schrieb Artem Bityutskiy:
>  > I think I meant the compare_lebs() exporting, not this one, replied to
> > wrong e-mail, sorry. Happens when I am in hurry - try to keep everyone
> > happy and make sure Richard is always busy with something :-)
> >
> 
> Haha.
> No need to keep me busy. :P

By this I meant - give some review feed-back ASAP to make sure you have
something to do and think about. Surely it is better than giving a lot
more feed-back but with a couple of weeks delay?

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/7] [RFC] UBI: Export next_sqnum()

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 618 bytes --]

On Thu, 2012-05-17 at 13:47 +0200, Richard Weinberger wrote:
> Am 17.05.2012 13:44, schrieb Artem Bityutskiy:
>  > I think I meant the compare_lebs() exporting, not this one, replied to
> > wrong e-mail, sorry. Happens when I am in hurry - try to keep everyone
> > happy and make sure Richard is always busy with something :-)
> >
> 
> Haha.
> No need to keep me busy. :P

By this I meant - give some review feed-back ASAP to make sure you have
something to do and think about. Surely it is better than giving a lot
more feed-back but with a couple of weeks delay?

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[PATCH 2/7] [RFC] UBI: Export compare_lebs()

[Richard Weinberger]

The fastmap mechanism needs this funtion,
rename it to ubi_compare_lebs() and export it.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/scan.c |    8 ++++----
 drivers/mtd/ubi/ubi.h  |    4 ++++
 2 files changed, 8 insertions(+), 4 deletions(-)

diff --git a/drivers/mtd/ubi/scan.c b/drivers/mtd/ubi/scan.c
index c26b1ad..69be65f 100644
--- a/drivers/mtd/ubi/scan.c
+++ b/drivers/mtd/ubi/scan.c
@@ -295,7 +295,7 @@ static struct ubi_scan_volume *add_volume(struct ubi_scan_info *si, int vol_id,
 }
 
 /**
- * compare_lebs - find out which logical eraseblock is newer.
+ * ubi_compare_lebs - find out which logical eraseblock is newer.
  * @ubi: UBI device description object
  * @seb: first logical eraseblock to compare
  * @pnum: physical eraseblock number of the second logical eraseblock to
@@ -314,7 +314,7 @@ static struct ubi_scan_volume *add_volume(struct ubi_scan_info *si, int vol_id,
  *     o bit 2 is cleared: the older LEB is not corrupted;
  *     o bit 2 is set: the older LEB is corrupted.
  */
-static int compare_lebs(struct ubi_device *ubi, const struct ubi_scan_leb *seb,
+int ubi_compare_lebs(struct ubi_device *ubi, const struct ubi_scan_leb *seb,
 			int pnum, const struct ubi_vid_hdr *vid_hdr)
 {
 	void *buf;
@@ -503,7 +503,7 @@ int ubi_scan_add_used(struct ubi_device *ubi, struct ubi_scan_info *si,
 		 * sequence numbers. We still can attach these images, unless
 		 * there is a need to distinguish between old and new
 		 * eraseblocks, in which case we'll refuse the image in
-		 * 'compare_lebs()'. In other words, we attach old clean
+		 * 'ubi_compare_lebs()'. In other words, we attach old clean
 		 * images, but refuse attaching old images with duplicated
 		 * logical eraseblocks because there was an unclean reboot.
 		 */
@@ -519,7 +519,7 @@ int ubi_scan_add_used(struct ubi_device *ubi, struct ubi_scan_info *si,
 		 * Now we have to drop the older one and preserve the newer
 		 * one.
 		 */
-		cmp_res = compare_lebs(ubi, seb, pnum, vid_hdr);
+		cmp_res = ubi_compare_lebs(ubi, seb, pnum, vid_hdr);
 		if (cmp_res < 0)
 			return cmp_res;
 
diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 00c48f6..50c2af2 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -576,6 +576,10 @@ void ubi_do_get_device_info(struct ubi_device *ubi, struct ubi_device_info *di);
 void ubi_do_get_volume_info(struct ubi_device *ubi, struct ubi_volume *vol,
 			    struct ubi_volume_info *vi);
 
+/* scan.c */
+int ubi_compare_lebs(struct ubi_device *ubi, const struct ubi_scan_leb *seb,
+		      int pnum, const struct ubi_vid_hdr *vid_hdr);
+
 /*
  * ubi_rb_for_each_entry - walk an RB-tree.
  * @rb: a pointer to type 'struct rb_node' to use as a loop counter
-- 
1.7.6.5

[PATCH 2/7] [RFC] UBI: Export compare_lebs()

[Richard Weinberger]

The fastmap mechanism needs this funtion,
rename it to ubi_compare_lebs() and export it.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/scan.c |    8 ++++----
 drivers/mtd/ubi/ubi.h  |    4 ++++
 2 files changed, 8 insertions(+), 4 deletions(-)

diff --git a/drivers/mtd/ubi/scan.c b/drivers/mtd/ubi/scan.c
index c26b1ad..69be65f 100644
--- a/drivers/mtd/ubi/scan.c
+++ b/drivers/mtd/ubi/scan.c
@@ -295,7 +295,7 @@ static struct ubi_scan_volume *add_volume(struct ubi_scan_info *si, int vol_id,
 }
 
 /**
- * compare_lebs - find out which logical eraseblock is newer.
+ * ubi_compare_lebs - find out which logical eraseblock is newer.
  * @ubi: UBI device description object
  * @seb: first logical eraseblock to compare
  * @pnum: physical eraseblock number of the second logical eraseblock to
@@ -314,7 +314,7 @@ static struct ubi_scan_volume *add_volume(struct ubi_scan_info *si, int vol_id,
  *     o bit 2 is cleared: the older LEB is not corrupted;
  *     o bit 2 is set: the older LEB is corrupted.
  */
-static int compare_lebs(struct ubi_device *ubi, const struct ubi_scan_leb *seb,
+int ubi_compare_lebs(struct ubi_device *ubi, const struct ubi_scan_leb *seb,
 			int pnum, const struct ubi_vid_hdr *vid_hdr)
 {
 	void *buf;
@@ -503,7 +503,7 @@ int ubi_scan_add_used(struct ubi_device *ubi, struct ubi_scan_info *si,
 		 * sequence numbers. We still can attach these images, unless
 		 * there is a need to distinguish between old and new
 		 * eraseblocks, in which case we'll refuse the image in
-		 * 'compare_lebs()'. In other words, we attach old clean
+		 * 'ubi_compare_lebs()'. In other words, we attach old clean
 		 * images, but refuse attaching old images with duplicated
 		 * logical eraseblocks because there was an unclean reboot.
 		 */
@@ -519,7 +519,7 @@ int ubi_scan_add_used(struct ubi_device *ubi, struct ubi_scan_info *si,
 		 * Now we have to drop the older one and preserve the newer
 		 * one.
 		 */
-		cmp_res = compare_lebs(ubi, seb, pnum, vid_hdr);
+		cmp_res = ubi_compare_lebs(ubi, seb, pnum, vid_hdr);
 		if (cmp_res < 0)
 			return cmp_res;
 
diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 00c48f6..50c2af2 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -576,6 +576,10 @@ void ubi_do_get_device_info(struct ubi_device *ubi, struct ubi_device_info *di);
 void ubi_do_get_volume_info(struct ubi_device *ubi, struct ubi_volume *vol,
 			    struct ubi_volume_info *vi);
 
+/* scan.c */
+int ubi_compare_lebs(struct ubi_device *ubi, const struct ubi_scan_leb *seb,
+		      int pnum, const struct ubi_vid_hdr *vid_hdr);
+
 /*
  * ubi_rb_for_each_entry - walk an RB-tree.
  * @rb: a pointer to type 'struct rb_node' to use as a loop counter
-- 
1.7.6.5

Re: [PATCH 2/7] [RFC] UBI: Export compare_lebs()

[Shmulik Ladkani]

Hi Richard,

On Tue, 15 May 2012 19:11:06 +0200 Richard Weinberger <richard@nod.at> wrote:
> The fastmap mechanism needs this funtion,
> rename it to ubi_compare_lebs() and export it.
> 
> Signed-off-by: Richard Weinberger <richard@nod.at>
> ---
>  drivers/mtd/ubi/scan.c |    8 ++++----
>  drivers/mtd/ubi/ubi.h  |    4 ++++
>  2 files changed, 8 insertions(+), 4 deletions(-)

Reviewed-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>

Regards,
Shmulik

Re: [PATCH 2/7] [RFC] UBI: Export compare_lebs()

[Shmulik Ladkani]

Hi Richard,

On Tue, 15 May 2012 19:11:06 +0200 Richard Weinberger <richard@nod.at> wrote:
> The fastmap mechanism needs this funtion,
> rename it to ubi_compare_lebs() and export it.
> 
> Signed-off-by: Richard Weinberger <richard@nod.at>
> ---
>  drivers/mtd/ubi/scan.c |    8 ++++----
>  drivers/mtd/ubi/ubi.h  |    4 ++++
>  2 files changed, 8 insertions(+), 4 deletions(-)

Reviewed-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>

Regards,
Shmulik

[PATCH 3/7] [RFC] UBI: Add fastmap on-flash layout

[Richard Weinberger]

Specifies the fastmap on-flash layout.
The fastmap on-flash data structure consists of two major parts.
A super block (identified via UBI_FM_SB_VOLUME_ID) and
zero or more data blocks (identified via UBI_Fm_DATA_VOLUME_ID).
Data blocks are only used if whole checkpoint information does not fit
into the super block.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/ubi-media.h |  124 +++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 124 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi-media.h b/drivers/mtd/ubi/ubi-media.h
index 6fb8ec2..a23196f 100644
--- a/drivers/mtd/ubi/ubi-media.h
+++ b/drivers/mtd/ubi/ubi-media.h
@@ -375,4 +375,128 @@ struct ubi_vtbl_record {
 	__be32  crc;
 } __packed;
 
+/* UBI fastmap on-flash data structures */
+
+#define UBI_FM_SB_VOLUME_ID	(UBI_LAYOUT_VOLUME_ID + 1)
+#define UBI_FM_DATA_VOLUME_ID	(UBI_LAYOUT_VOLUME_ID + 2)
+
+/* fastmap on-flash data structure format version */
+#define UBI_FM_FMT_VERSION	1
+
+#define UBI_FM_SB_MAGIC		0x7B11D69F
+#define UBI_FM_HDR_MAGIC	0xD4B82EF7
+#define UBI_FM_VHDR_MAGIC	0xFA370ED1
+#define UBI_FM_POOL_MAGIC	0x67AF4D08
+#define UBI_FM_EBA_MAGIC	0xf0c040a8
+
+/* Semi-sane default values - TBR */
+#ifndef UBI_FM_MAX_POOL_SIZE
+#define UBI_FM_MAX_POOL_SIZE	128
+#endif
+#ifndef UBI_FM_MAX_BLOCKS
+#define UBI_FM_MAX_BLOCKS	32
+#endif
+#ifndef UBI_FM_MAX_START
+#define UBI_FM_MAX_START	64
+#endif
+
+/**
+ * struct ubi_fm_sb - UBI fastmap super block
+ * @magic: fastmap super block magic number (%UBI_FM_SB_MAGIC)
+ * @version: format version of this fastmap
+ * @data_crc: CRC over the fastmap data
+ * @nblocks: number of PEBs used by this fastmap
+ * @block_loc: an array containing the location of all PEBs of the fastmap
+ * @block_ec: the erase counter of each used PEB
+ * @sqnum: highest sequence number value at the time while taking the fastmap
+ *
+ */
+struct ubi_fm_sb {
+	__be32 magic;
+	__u8 version;
+	__u8 padding1[3];
+	__be32 data_crc;
+	__be32 nblocks;
+	__be32 block_loc[UBI_FM_MAX_BLOCKS];
+	__be32 block_ec[UBI_FM_MAX_BLOCKS];
+	__be64 sqnum;
+	__u8 padding2[32];
+} __packed;
+
+/**
+ * struct ubi_fm_hdr - header of the fastmap data set
+ * @magic: fastmap header magic number (%UBI_FM_HDR_MAGIC)
+ * @nfree: number of free PEBs known by this fastmap
+ * @nused: number of used PEBs known by this fastmap
+ * @nvol: number of UBI volumes known by this fastmap
+ */
+struct ubi_fm_hdr {
+	__be32 magic;
+	__be32 nfree;
+	__be32 nused;
+	__be32 nvol;
+	__u8 padding[16];
+} __packed;
+
+/* struct ubi_fm_hdr is followed by struct ubi_fm_scan_pool */
+
+/**
+ * struct ubi_fm_scan_pool - Fastmap pool PEBs to be scanned while attaching
+ * @magic: pool magic numer (%UBI_FM_POOL_MAGIC)
+ * @size: current pool size
+ * @pebs: an array containing the location of all PEBs in this pool
+ */
+struct ubi_fm_scan_pool {
+	__be32 magic;
+	__be32 size;
+	__be32 pebs[UBI_FM_MAX_POOL_SIZE];
+	__be32 padding[4];
+} __packed;
+
+/* struct ubi_fm_scan_pool is followed by nfree+nused struct ubi_fm_ec records */
+
+/**
+ * struct ubi_fm_ec - stores the erase counter of a PEB
+ * @pnum: PEB number
+ * @ec: ec of this PEB
+ */
+struct ubi_fm_ec {
+	__be32 pnum;
+	__be32 ec;
+} __packed;
+
+/**
+ * struct ubi_fm_volhdr - Fastmap volume header
+ * it identifies the start of an eba table
+ * @magic: Fastmap volume header magic number (%UBI_FM_VHDR_MAGIC)
+ * @vol_id: volume id of the fastmapped volume
+ * @vol_type: type of the fastmapped volume
+ * @data_pad: data_pad value of the fastmapped volume
+ * @used_ebs: number of used LEBs within this volume
+ * @last_eb_bytes: number of bytes used in the last LEB
+ */
+struct ubi_fm_volhdr {
+	__be32 magic;
+	__be32 vol_id;
+	__u8 vol_type;
+	__u8 padding1[3];
+	__be32 data_pad;
+	__be32 used_ebs;
+	__be32 last_eb_bytes;
+	__u8 padding2[8];
+} __packed;
+
+/* struct ubi_fm_volhdr is followed by one struct ubi_fm_eba records */
+
+/**
+ * struct ubi_fm_eba - denotes an association beween a PEB and LEB
+ * @magic EBA table magic number
+ * @nused: number of table entries
+ * @pnum: PEB number of LEB (LEB is the index)
+ */
+struct ubi_fm_eba {
+	__be32 magic;
+	__be32 nused;
+	__be32 pnum[0];
+} __packed;
 #endif /* !__UBI_MEDIA_H__ */
-- 
1.7.6.5

[PATCH 3/7] [RFC] UBI: Add fastmap on-flash layout

[Richard Weinberger]

Specifies the fastmap on-flash layout.
The fastmap on-flash data structure consists of two major parts.
A super block (identified via UBI_FM_SB_VOLUME_ID) and
zero or more data blocks (identified via UBI_Fm_DATA_VOLUME_ID).
Data blocks are only used if whole checkpoint information does not fit
into the super block.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/ubi-media.h |  124 +++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 124 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi-media.h b/drivers/mtd/ubi/ubi-media.h
index 6fb8ec2..a23196f 100644
--- a/drivers/mtd/ubi/ubi-media.h
+++ b/drivers/mtd/ubi/ubi-media.h
@@ -375,4 +375,128 @@ struct ubi_vtbl_record {
 	__be32  crc;
 } __packed;
 
+/* UBI fastmap on-flash data structures */
+
+#define UBI_FM_SB_VOLUME_ID	(UBI_LAYOUT_VOLUME_ID + 1)
+#define UBI_FM_DATA_VOLUME_ID	(UBI_LAYOUT_VOLUME_ID + 2)
+
+/* fastmap on-flash data structure format version */
+#define UBI_FM_FMT_VERSION	1
+
+#define UBI_FM_SB_MAGIC		0x7B11D69F
+#define UBI_FM_HDR_MAGIC	0xD4B82EF7
+#define UBI_FM_VHDR_MAGIC	0xFA370ED1
+#define UBI_FM_POOL_MAGIC	0x67AF4D08
+#define UBI_FM_EBA_MAGIC	0xf0c040a8
+
+/* Semi-sane default values - TBR */
+#ifndef UBI_FM_MAX_POOL_SIZE
+#define UBI_FM_MAX_POOL_SIZE	128
+#endif
+#ifndef UBI_FM_MAX_BLOCKS
+#define UBI_FM_MAX_BLOCKS	32
+#endif
+#ifndef UBI_FM_MAX_START
+#define UBI_FM_MAX_START	64
+#endif
+
+/**
+ * struct ubi_fm_sb - UBI fastmap super block
+ * @magic: fastmap super block magic number (%UBI_FM_SB_MAGIC)
+ * @version: format version of this fastmap
+ * @data_crc: CRC over the fastmap data
+ * @nblocks: number of PEBs used by this fastmap
+ * @block_loc: an array containing the location of all PEBs of the fastmap
+ * @block_ec: the erase counter of each used PEB
+ * @sqnum: highest sequence number value at the time while taking the fastmap
+ *
+ */
+struct ubi_fm_sb {
+	__be32 magic;
+	__u8 version;
+	__u8 padding1[3];
+	__be32 data_crc;
+	__be32 nblocks;
+	__be32 block_loc[UBI_FM_MAX_BLOCKS];
+	__be32 block_ec[UBI_FM_MAX_BLOCKS];
+	__be64 sqnum;
+	__u8 padding2[32];
+} __packed;
+
+/**
+ * struct ubi_fm_hdr - header of the fastmap data set
+ * @magic: fastmap header magic number (%UBI_FM_HDR_MAGIC)
+ * @nfree: number of free PEBs known by this fastmap
+ * @nused: number of used PEBs known by this fastmap
+ * @nvol: number of UBI volumes known by this fastmap
+ */
+struct ubi_fm_hdr {
+	__be32 magic;
+	__be32 nfree;
+	__be32 nused;
+	__be32 nvol;
+	__u8 padding[16];
+} __packed;
+
+/* struct ubi_fm_hdr is followed by struct ubi_fm_scan_pool */
+
+/**
+ * struct ubi_fm_scan_pool - Fastmap pool PEBs to be scanned while attaching
+ * @magic: pool magic numer (%UBI_FM_POOL_MAGIC)
+ * @size: current pool size
+ * @pebs: an array containing the location of all PEBs in this pool
+ */
+struct ubi_fm_scan_pool {
+	__be32 magic;
+	__be32 size;
+	__be32 pebs[UBI_FM_MAX_POOL_SIZE];
+	__be32 padding[4];
+} __packed;
+
+/* struct ubi_fm_scan_pool is followed by nfree+nused struct ubi_fm_ec records */
+
+/**
+ * struct ubi_fm_ec - stores the erase counter of a PEB
+ * @pnum: PEB number
+ * @ec: ec of this PEB
+ */
+struct ubi_fm_ec {
+	__be32 pnum;
+	__be32 ec;
+} __packed;
+
+/**
+ * struct ubi_fm_volhdr - Fastmap volume header
+ * it identifies the start of an eba table
+ * @magic: Fastmap volume header magic number (%UBI_FM_VHDR_MAGIC)
+ * @vol_id: volume id of the fastmapped volume
+ * @vol_type: type of the fastmapped volume
+ * @data_pad: data_pad value of the fastmapped volume
+ * @used_ebs: number of used LEBs within this volume
+ * @last_eb_bytes: number of bytes used in the last LEB
+ */
+struct ubi_fm_volhdr {
+	__be32 magic;
+	__be32 vol_id;
+	__u8 vol_type;
+	__u8 padding1[3];
+	__be32 data_pad;
+	__be32 used_ebs;
+	__be32 last_eb_bytes;
+	__u8 padding2[8];
+} __packed;
+
+/* struct ubi_fm_volhdr is followed by one struct ubi_fm_eba records */
+
+/**
+ * struct ubi_fm_eba - denotes an association beween a PEB and LEB
+ * @magic EBA table magic number
+ * @nused: number of table entries
+ * @pnum: PEB number of LEB (LEB is the index)
+ */
+struct ubi_fm_eba {
+	__be32 magic;
+	__be32 nused;
+	__be32 pnum[0];
+} __packed;
 #endif /* !__UBI_MEDIA_H__ */
-- 
1.7.6.5

[PATCH 4/7] [RFC] UBI: Add fastmap structs to ubi_device

[Richard Weinberger]

struct ubi_fastmap describes the currently used checkpoint.
Upon checkpoint recreation all currently used PEBs will be returned
to the wl subsystem.

struct ubi_fm_pool describes the fast pool.
All PEBs within this pool have to be rescanned after reading the fastmap.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/ubi.h |   46 ++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 46 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 50c2af2..6c89971 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -197,6 +197,39 @@ struct ubi_rename_entry {
 struct ubi_volume_desc;
 
 /**
+ * struct ubi_fastmap - in-memory fastmap data structure.
+ * @peb: PEBs used by the current fastamp
+ * @ec: the erase counter of each used PEB
+ * @size: size of the fastmap in bytes
+ * @used_blocks: number of used PEBs
+ */
+struct ubi_fastmap {
+	int peb[UBI_FM_MAX_BLOCKS];
+	unsigned int ec[UBI_FM_MAX_BLOCKS];
+	size_t size;
+	int used_blocks;
+};
+
+/**
+ * struct ubi_fm_pool - in-memory fastmap pool
+ * @pebs: PEBs in this pool
+ * @used: number of used PEBs
+ * @size: total number of PEBs in this pool
+ * @max_size: maximal size of the pool
+ *
+ * A pool gets filled with up to max_size.
+ * If all PEBs within the pool are used a new fastmap will be written
+ * to the flash and the pool gets refilled with empty PEBs.
+ *
+ */
+struct ubi_fm_pool {
+	int pebs[UBI_FM_MAX_POOL_SIZE];
+	int used;
+	int size;
+	int max_size;
+};
+
+/**
  * struct ubi_volume - UBI volume description data structure.
  * @dev: device object to make use of the the Linux device model
  * @cdev: character device object to create character device
@@ -331,6 +364,13 @@ struct ubi_wl_entry;
  * @ltree: the lock tree
  * @alc_mutex: serializes "atomic LEB change" operations
  *
+ * @fm: in-memory data structure of the currently used fastmap
+ * @old_fm: in-memory data structure old fastmap.
+ * 	    (only valid while writing a new one)
+ * @fm_pool: in-memory data structure of the fastmap pool
+ * @attached_by_scanning: this UBI device was attached by the old scanning
+ * 			  methold. All fastmap volumes have to be deleted.
+ *
  * @used: RB-tree of used physical eraseblocks
  * @erroneous: RB-tree of erroneous used physical eraseblocks
  * @free: RB-tree of free physical eraseblocks
@@ -422,6 +462,12 @@ struct ubi_device {
 	struct rb_root ltree;
 	struct mutex alc_mutex;
 
+	/* Fastmap stuff */
+	struct ubi_fastmap *fm;
+	struct ubi_fastmap *old_fm;
+	struct ubi_fm_pool fm_pool;
+	bool attached_by_scanning;
+
 	/* Wear-leveling sub-system's stuff */
 	struct rb_root used;
 	struct rb_root erroneous;
-- 
1.7.6.5

[PATCH 4/7] [RFC] UBI: Add fastmap structs to ubi_device

[Richard Weinberger]

struct ubi_fastmap describes the currently used checkpoint.
Upon checkpoint recreation all currently used PEBs will be returned
to the wl subsystem.

struct ubi_fm_pool describes the fast pool.
All PEBs within this pool have to be rescanned after reading the fastmap.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/ubi.h |   46 ++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 46 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 50c2af2..6c89971 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -197,6 +197,39 @@ struct ubi_rename_entry {
 struct ubi_volume_desc;
 
 /**
+ * struct ubi_fastmap - in-memory fastmap data structure.
+ * @peb: PEBs used by the current fastamp
+ * @ec: the erase counter of each used PEB
+ * @size: size of the fastmap in bytes
+ * @used_blocks: number of used PEBs
+ */
+struct ubi_fastmap {
+	int peb[UBI_FM_MAX_BLOCKS];
+	unsigned int ec[UBI_FM_MAX_BLOCKS];
+	size_t size;
+	int used_blocks;
+};
+
+/**
+ * struct ubi_fm_pool - in-memory fastmap pool
+ * @pebs: PEBs in this pool
+ * @used: number of used PEBs
+ * @size: total number of PEBs in this pool
+ * @max_size: maximal size of the pool
+ *
+ * A pool gets filled with up to max_size.
+ * If all PEBs within the pool are used a new fastmap will be written
+ * to the flash and the pool gets refilled with empty PEBs.
+ *
+ */
+struct ubi_fm_pool {
+	int pebs[UBI_FM_MAX_POOL_SIZE];
+	int used;
+	int size;
+	int max_size;
+};
+
+/**
  * struct ubi_volume - UBI volume description data structure.
  * @dev: device object to make use of the the Linux device model
  * @cdev: character device object to create character device
@@ -331,6 +364,13 @@ struct ubi_wl_entry;
  * @ltree: the lock tree
  * @alc_mutex: serializes "atomic LEB change" operations
  *
+ * @fm: in-memory data structure of the currently used fastmap
+ * @old_fm: in-memory data structure old fastmap.
+ * 	    (only valid while writing a new one)
+ * @fm_pool: in-memory data structure of the fastmap pool
+ * @attached_by_scanning: this UBI device was attached by the old scanning
+ * 			  methold. All fastmap volumes have to be deleted.
+ *
  * @used: RB-tree of used physical eraseblocks
  * @erroneous: RB-tree of erroneous used physical eraseblocks
  * @free: RB-tree of free physical eraseblocks
@@ -422,6 +462,12 @@ struct ubi_device {
 	struct rb_root ltree;
 	struct mutex alc_mutex;
 
+	/* Fastmap stuff */
+	struct ubi_fastmap *fm;
+	struct ubi_fastmap *old_fm;
+	struct ubi_fm_pool fm_pool;
+	bool attached_by_scanning;
+
 	/* Wear-leveling sub-system's stuff */
 	struct rb_root used;
 	struct rb_root erroneous;
-- 
1.7.6.5

[PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware

[Richard Weinberger]

Integrates fastmapping into the wl subsystem.
Fastmapping deals with PEBs, it has to tell the wl subsystem
which PEBs are currently used and must not touched by the wl thread.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/ubi.h |    3 +
 drivers/mtd/ubi/wl.c  |  141 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 144 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 6c89971..cf5cfaf 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -586,6 +586,9 @@ int ubi_wl_scrub_peb(struct ubi_device *ubi, int pnum);
 int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si);
 void ubi_wl_close(struct ubi_device *ubi);
 int ubi_thread(void *u);
+int ubi_wl_get_fm_peb(struct ubi_device *ubi, int max_pnum);
+int ubi_wl_put_fm_peb(struct ubi_device *ubi, int pnum, int torture);
+int ubi_is_fm_block(struct ubi_device *ubi, int pnum);
 
 /* io.c */
 int ubi_io_read(const struct ubi_device *ubi, void *buf, int pnum, int offset,
diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 64ce993..a329358 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -169,6 +169,25 @@ static int paranoid_check_in_pq(const struct ubi_device *ubi,
 #endif
 
 /**
+ *  ubi_ubi_is_fm_block - returns 1 if a PEB is currently used in a fastmap.
+ *  @ubi: UBI device description object
+ *  @pnum: the to be checked PEB
+ */
+int ubi_is_fm_block(struct ubi_device *ubi, int pnum)
+{
+	int i;
+
+	if (!ubi->fm)
+		return 0;
+
+	for (i = 0; i < ubi->fm->used_blocks; i++)
+		if (ubi->fm->peb[i] == pnum)
+			return 1;
+
+	return 0;
+}
+
+/**
  * wl_tree_add - add a wear-leveling entry to a WL RB-tree.
  * @e: the wear-leveling entry to add
  * @root: the root of the tree
@@ -375,6 +394,63 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
 
 /**
  * ubi_wl_get_peb - get a physical eraseblock.
+ * find_early_wl_entry - find wear-leveling entry with a low pnum.
+ * @root: the RB-tree where to look for
+ * @max_pnum: highest possible pnum
+ *
+ * This function looks for a wear leveling entry containing a eb which
+ * is in front of the memory.
+ */
+static struct ubi_wl_entry *find_early_wl_entry(struct rb_root *root,
+						int max_pnum)
+{
+	struct rb_node *p;
+	struct ubi_wl_entry *e, *victim = NULL;
+
+	ubi_rb_for_each_entry(p, e, root, u.rb) {
+		if (e->pnum < max_pnum) {
+			victim = e;
+			max_pnum = e->pnum;
+		}
+	}
+
+	return victim;
+}
+
+/**
+ * ubi_wl_get_fm_peb - find a physical erase block with a given maximal number.
+ * @ubi: UBI device description object
+ * @max_pnum: the highest acceptable erase block number
+ *
+ * The function returns a physical erase block with a given maximal number
+ * and removes it from the wl subsystem.
+ * Must be called with wl_lock held!
+ */
+int ubi_wl_get_fm_peb(struct ubi_device *ubi, int max_pnum)
+{
+	int ret = -ENOSPC;
+	struct ubi_wl_entry *e;
+
+	if (!ubi->free.rb_node) {
+		ubi_err("no free eraseblocks");
+
+		goto out;
+	}
+
+	e = find_early_wl_entry(&ubi->free, max_pnum);
+	if (!e)
+		goto out;
+
+	ret = e->pnum;
+
+	/* remove it from the free list,
+	 * the wl subsystem does no longer know this erase block */
+	rb_erase(&e->u.rb, &ubi->free);
+out:
+	return ret;
+}
+
+/**
  * @ubi: UBI device description object
  *
  * This function returns a physical eraseblock in case of success and a
@@ -596,6 +672,9 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 {
 	struct ubi_work *wl_wrk;
 
+	ubi_assert(e);
+	ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 	dbg_wl("schedule erasure of PEB %d, EC %d, torture %d",
 	       e->pnum, e->ec, torture);
 
@@ -612,6 +691,56 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 }
 
 /**
+ * ubi_wl_put_fm_peb - returns a PEB used in a fastmap to the wear-leveling 
+ * sub-system.
+ *
+ * see: ubi_wl_put_peb()
+ */
+int ubi_wl_put_fm_peb(struct ubi_device *ubi, int pnum, int torture)
+{
+	int i, err = 0;
+	struct ubi_wl_entry *e;
+
+	dbg_wl("PEB %d", pnum);
+	ubi_assert(pnum >= 0);
+	ubi_assert(pnum < ubi->peb_count);
+
+	spin_lock(&ubi->wl_lock);
+	e = ubi->lookuptbl[pnum];
+
+	/* This can happen if we recovered from a fastmap the very
+	 * frist time and writing now a new one. In this case the wl system
+	 * has never seen any PEB used by the original fastmap.
+	 */
+	if (!e) {
+		ubi_assert(ubi->old_fm);
+		e = kmem_cache_alloc(ubi_wl_entry_slab, GFP_ATOMIC);
+		if (!e) {
+			spin_unlock(&ubi->wl_lock);
+			return -ENOMEM;
+		}
+
+		e->pnum = pnum;
+		e->ec = 0;
+		/* use the ec value from the fastmap */
+		for (i = 0; i < UBI_FM_MAX_BLOCKS; i++) {
+			if (pnum == ubi->old_fm->peb[i]) {
+				e->ec = ubi->old_fm->ec[i];
+				break;
+			}
+		}
+		ubi_assert(e->ec);
+		ubi->lookuptbl[pnum] = e;
+	}
+
+	spin_unlock(&ubi->wl_lock);
+
+	err = schedule_erase(ubi, e, torture);
+
+	return err;
+}
+
+/**
  * wear_leveling_worker - wear-leveling worker function.
  * @ubi: UBI device description object
  * @wrk: the work object
@@ -988,6 +1117,8 @@ static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk,
 
 	dbg_wl("erase PEB %d EC %d", pnum, e->ec);
 
+	ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 	err = sync_erase(ubi, e, wl_wrk->torture);
 	if (!err) {
 		/* Fine, we've erased it successfully */
@@ -1422,6 +1553,9 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 
 		e->pnum = seb->pnum;
 		e->ec = seb->ec;
+
+		ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 		ubi->lookuptbl[e->pnum] = e;
 		if (schedule_erase(ubi, e, 0)) {
 			kmem_cache_free(ubi_wl_entry_slab, e);
@@ -1439,7 +1573,10 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 		e->pnum = seb->pnum;
 		e->ec = seb->ec;
 		ubi_assert(e->ec >= 0);
+		ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 		wl_tree_add(e, &ubi->free);
+
 		ubi->lookuptbl[e->pnum] = e;
 	}
 
@@ -1454,6 +1591,10 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 			e->pnum = seb->pnum;
 			e->ec = seb->ec;
 			ubi->lookuptbl[e->pnum] = e;
+
+			if (ubi_is_fm_block(ubi, seb->pnum))
+				continue;
+
 			if (!seb->scrub) {
 				dbg_wl("add PEB %d EC %d to the used tree",
 				       e->pnum, e->ec);
-- 
1.7.6.5

[PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware

[Richard Weinberger]

Integrates fastmapping into the wl subsystem.
Fastmapping deals with PEBs, it has to tell the wl subsystem
which PEBs are currently used and must not touched by the wl thread.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/ubi.h |    3 +
 drivers/mtd/ubi/wl.c  |  141 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 144 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 6c89971..cf5cfaf 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -586,6 +586,9 @@ int ubi_wl_scrub_peb(struct ubi_device *ubi, int pnum);
 int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si);
 void ubi_wl_close(struct ubi_device *ubi);
 int ubi_thread(void *u);
+int ubi_wl_get_fm_peb(struct ubi_device *ubi, int max_pnum);
+int ubi_wl_put_fm_peb(struct ubi_device *ubi, int pnum, int torture);
+int ubi_is_fm_block(struct ubi_device *ubi, int pnum);
 
 /* io.c */
 int ubi_io_read(const struct ubi_device *ubi, void *buf, int pnum, int offset,
diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 64ce993..a329358 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -169,6 +169,25 @@ static int paranoid_check_in_pq(const struct ubi_device *ubi,
 #endif
 
 /**
+ *  ubi_ubi_is_fm_block - returns 1 if a PEB is currently used in a fastmap.
+ *  @ubi: UBI device description object
+ *  @pnum: the to be checked PEB
+ */
+int ubi_is_fm_block(struct ubi_device *ubi, int pnum)
+{
+	int i;
+
+	if (!ubi->fm)
+		return 0;
+
+	for (i = 0; i < ubi->fm->used_blocks; i++)
+		if (ubi->fm->peb[i] == pnum)
+			return 1;
+
+	return 0;
+}
+
+/**
  * wl_tree_add - add a wear-leveling entry to a WL RB-tree.
  * @e: the wear-leveling entry to add
  * @root: the root of the tree
@@ -375,6 +394,63 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
 
 /**
  * ubi_wl_get_peb - get a physical eraseblock.
+ * find_early_wl_entry - find wear-leveling entry with a low pnum.
+ * @root: the RB-tree where to look for
+ * @max_pnum: highest possible pnum
+ *
+ * This function looks for a wear leveling entry containing a eb which
+ * is in front of the memory.
+ */
+static struct ubi_wl_entry *find_early_wl_entry(struct rb_root *root,
+						int max_pnum)
+{
+	struct rb_node *p;
+	struct ubi_wl_entry *e, *victim = NULL;
+
+	ubi_rb_for_each_entry(p, e, root, u.rb) {
+		if (e->pnum < max_pnum) {
+			victim = e;
+			max_pnum = e->pnum;
+		}
+	}
+
+	return victim;
+}
+
+/**
+ * ubi_wl_get_fm_peb - find a physical erase block with a given maximal number.
+ * @ubi: UBI device description object
+ * @max_pnum: the highest acceptable erase block number
+ *
+ * The function returns a physical erase block with a given maximal number
+ * and removes it from the wl subsystem.
+ * Must be called with wl_lock held!
+ */
+int ubi_wl_get_fm_peb(struct ubi_device *ubi, int max_pnum)
+{
+	int ret = -ENOSPC;
+	struct ubi_wl_entry *e;
+
+	if (!ubi->free.rb_node) {
+		ubi_err("no free eraseblocks");
+
+		goto out;
+	}
+
+	e = find_early_wl_entry(&ubi->free, max_pnum);
+	if (!e)
+		goto out;
+
+	ret = e->pnum;
+
+	/* remove it from the free list,
+	 * the wl subsystem does no longer know this erase block */
+	rb_erase(&e->u.rb, &ubi->free);
+out:
+	return ret;
+}
+
+/**
  * @ubi: UBI device description object
  *
  * This function returns a physical eraseblock in case of success and a
@@ -596,6 +672,9 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 {
 	struct ubi_work *wl_wrk;
 
+	ubi_assert(e);
+	ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 	dbg_wl("schedule erasure of PEB %d, EC %d, torture %d",
 	       e->pnum, e->ec, torture);
 
@@ -612,6 +691,56 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 }
 
 /**
+ * ubi_wl_put_fm_peb - returns a PEB used in a fastmap to the wear-leveling 
+ * sub-system.
+ *
+ * see: ubi_wl_put_peb()
+ */
+int ubi_wl_put_fm_peb(struct ubi_device *ubi, int pnum, int torture)
+{
+	int i, err = 0;
+	struct ubi_wl_entry *e;
+
+	dbg_wl("PEB %d", pnum);
+	ubi_assert(pnum >= 0);
+	ubi_assert(pnum < ubi->peb_count);
+
+	spin_lock(&ubi->wl_lock);
+	e = ubi->lookuptbl[pnum];
+
+	/* This can happen if we recovered from a fastmap the very
+	 * frist time and writing now a new one. In this case the wl system
+	 * has never seen any PEB used by the original fastmap.
+	 */
+	if (!e) {
+		ubi_assert(ubi->old_fm);
+		e = kmem_cache_alloc(ubi_wl_entry_slab, GFP_ATOMIC);
+		if (!e) {
+			spin_unlock(&ubi->wl_lock);
+			return -ENOMEM;
+		}
+
+		e->pnum = pnum;
+		e->ec = 0;
+		/* use the ec value from the fastmap */
+		for (i = 0; i < UBI_FM_MAX_BLOCKS; i++) {
+			if (pnum == ubi->old_fm->peb[i]) {
+				e->ec = ubi->old_fm->ec[i];
+				break;
+			}
+		}
+		ubi_assert(e->ec);
+		ubi->lookuptbl[pnum] = e;
+	}
+
+	spin_unlock(&ubi->wl_lock);
+
+	err = schedule_erase(ubi, e, torture);
+
+	return err;
+}
+
+/**
  * wear_leveling_worker - wear-leveling worker function.
  * @ubi: UBI device description object
  * @wrk: the work object
@@ -988,6 +1117,8 @@ static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk,
 
 	dbg_wl("erase PEB %d EC %d", pnum, e->ec);
 
+	ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 	err = sync_erase(ubi, e, wl_wrk->torture);
 	if (!err) {
 		/* Fine, we've erased it successfully */
@@ -1422,6 +1553,9 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 
 		e->pnum = seb->pnum;
 		e->ec = seb->ec;
+
+		ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 		ubi->lookuptbl[e->pnum] = e;
 		if (schedule_erase(ubi, e, 0)) {
 			kmem_cache_free(ubi_wl_entry_slab, e);
@@ -1439,7 +1573,10 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 		e->pnum = seb->pnum;
 		e->ec = seb->ec;
 		ubi_assert(e->ec >= 0);
+		ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 		wl_tree_add(e, &ubi->free);
+
 		ubi->lookuptbl[e->pnum] = e;
 	}
 
@@ -1454,6 +1591,10 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 			e->pnum = seb->pnum;
 			e->ec = seb->ec;
 			ubi->lookuptbl[e->pnum] = e;
+
+			if (ubi_is_fm_block(ubi, seb->pnum))
+				continue;
+
 			if (!seb->scrub) {
 				dbg_wl("add PEB %d EC %d to the used tree",
 				       e->pnum, e->ec);
-- 
1.7.6.5

[PATCH 6/7] [RFC] UBI: Implement fastmapping support

[Richard Weinberger]

Implements UBI fastmapping support.
It reduces the attaching time from O(N) to O(1).
Fastmaps are written on demand and upon changes of the volume layout.
If the recovery from a fastmap fails we fall back to scanning mode

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/Makefile  |    2 +-
 drivers/mtd/ubi/fastmap.c | 1107 +++++++++++++++++++++++++++++++++++++++++++++
 drivers/mtd/ubi/scan.c    |    6 +-
 drivers/mtd/ubi/ubi.h     |    6 +-
 4 files changed, 1118 insertions(+), 3 deletions(-)
 create mode 100644 drivers/mtd/ubi/fastmap.c

diff --git a/drivers/mtd/ubi/Makefile b/drivers/mtd/ubi/Makefile
index da71655..f4a4280 100644
--- a/drivers/mtd/ubi/Makefile
+++ b/drivers/mtd/ubi/Makefile
@@ -1,6 +1,6 @@
 obj-$(CONFIG_MTD_UBI) += ubi.o
 
 ubi-y += vtbl.o vmt.o upd.o build.o cdev.o kapi.o eba.o io.o wl.o scan.o
-ubi-y += misc.o debug.o
+ubi-y += misc.o debug.o fastmap.o
 
 obj-$(CONFIG_MTD_UBI_GLUEBI) += gluebi.o
diff --git a/drivers/mtd/ubi/fastmap.c b/drivers/mtd/ubi/fastmap.c
new file mode 100644
index 0000000..2ea1682
--- /dev/null
+++ b/drivers/mtd/ubi/fastmap.c
@@ -0,0 +1,1107 @@
+/*
+ * Copyright (c) 2012 Linutronix GmbH
+ * Author: Richard Weinberger <richard@nod.at>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
+ * the GNU General Public License for more details.
+ *
+ */
+
+#include <linux/crc32.h>
+#include "ubi.h"
+
+/**
+ * new_fm_vhdr - allocate a new volume header for fastmap usage.
+ * @ubi: UBI device description object
+ * @vol_id: the VID of the new header
+ */
+static struct ubi_vid_hdr *new_fm_vhdr(struct ubi_device *ubi, int vol_id)
+{
+	struct ubi_vid_hdr *new;
+
+	new = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!new)
+		goto out;
+
+	new->vol_type = UBI_VID_DYNAMIC;
+	new->vol_id = cpu_to_be32(vol_id);
+
+	/* the fastmap has be deleted on older kernels */
+	new->compat = UBI_COMPAT_DELETE;
+
+out:
+	return new;
+}
+
+/**
+ * add_seb - create and add a scan erase block to a given list.
+ * @si: UBI scan info object
+ * @list: the target list
+ * @pnum: PEB number of the new scan erase block
+ * @ec: erease counter of the new SEB
+ */
+static int add_seb(struct ubi_scan_info *si, struct list_head *list,
+		   int pnum, int ec)
+{
+	struct ubi_scan_leb *seb;
+
+	seb = kmem_cache_alloc(si->scan_leb_slab, GFP_KERNEL);
+	if (!seb)
+		return -ENOMEM;
+
+	seb->pnum = pnum;
+	seb->ec = ec;
+	seb->lnum = -1;
+	seb->scrub = seb->copy_flag = seb->sqnum = 0;
+
+	si->ec_sum += seb->ec;
+	si->ec_count++;
+
+	if (si->max_ec < seb->ec)
+		si->max_ec = seb->ec;
+
+	if (si->min_ec > seb->ec)
+		si->min_ec = seb->ec;
+
+	list_add_tail(&seb->u.list, list);
+
+	return 0;
+}
+
+/**
+ * add_vol - create and add a new scan volume to ubi_scan_info.
+ * @si: ubi_scan_info object
+ * @vol_id: VID of the new volume
+ * @used_ebs: number of used EBS
+ * @data_pad: data padding value of the new volume
+ * @vol_type: volume type
+ * @last_eb_bytes: number of bytes in the last LEB
+ */
+static struct ubi_scan_volume *add_vol(struct ubi_scan_info *si, int vol_id,
+				       int used_ebs, int data_pad, u8 vol_type,
+				       int last_eb_bytes)
+{
+	struct ubi_scan_volume *sv;
+	struct rb_node **p = &si->volumes.rb_node, *parent = NULL;
+
+	while (*p) {
+		parent = *p;
+		sv = rb_entry(parent, struct ubi_scan_volume, rb);
+
+		if (vol_id > sv->vol_id)
+			p = &(*p)->rb_left;
+		else if (vol_id > sv->vol_id)
+			p = &(*p)->rb_right;
+	}
+
+	sv = kmalloc(sizeof(struct ubi_scan_volume), GFP_KERNEL);
+	if (!sv)
+		goto out;
+
+	sv->highest_lnum = sv->leb_count = 0;
+	sv->vol_id = vol_id;
+	sv->used_ebs = used_ebs;
+	sv->data_pad = data_pad;
+	sv->last_data_size = last_eb_bytes;
+	sv->compat = 0;
+	sv->vol_type = vol_type;
+	sv->root = RB_ROOT;
+
+	rb_link_node(&sv->rb, parent, p);
+	rb_insert_color(&sv->rb, &si->volumes);
+
+out:
+	return sv;
+}
+
+/**
+ * assign_seb_to_sv - assigns a SEB to a given scan_volume and removes it
+ * from it's original list.
+ * @si: ubi_scan_info object
+ * @seb: the to be assigned SEB
+ * @sv: target scan volume
+ */
+static void assign_seb_to_sv(struct ubi_scan_info *si,
+			     struct ubi_scan_leb *seb,
+			     struct ubi_scan_volume *sv)
+{
+	struct ubi_scan_leb *tmp_seb;
+	struct rb_node **p = &si->volumes.rb_node, *parent = NULL;
+
+	p = &sv->root.rb_node;
+	while (*p) {
+		parent = *p;
+
+		tmp_seb = rb_entry(parent, struct ubi_scan_leb, u.rb);
+		if (seb->lnum != tmp_seb->lnum) {
+			if (seb->lnum < tmp_seb->lnum)
+				p = &(*p)->rb_left;
+			else
+				p = &(*p)->rb_right;
+
+			continue;
+		} else
+			break;
+	}
+
+	list_del(&seb->u.list);
+	sv->leb_count++;
+
+	rb_link_node(&seb->u.rb, parent, p);
+	rb_insert_color(&seb->u.rb, &sv->root);
+}
+
+/**
+ * update_vol - inserts or updates a LEB which was found a pool.
+ * @ubi: the UBI device object
+ * @si: scan info object
+ * @sv: the scan volume where this LEB belongs to
+ * @new_vh: the volume header derived from new_seb
+ * @new_seb: the SEB to be examined
+ */
+static int update_vol(struct ubi_device *ubi, struct ubi_scan_info *si,
+		      struct ubi_scan_volume *sv, struct ubi_vid_hdr *new_vh,
+		      struct ubi_scan_leb *new_seb)
+{
+	struct rb_node **p = &sv->root.rb_node, *parent = NULL;
+	struct ubi_scan_leb *seb, *victim;
+	int cmp_res;
+
+	while (*p) {
+		parent = *p;
+		seb = rb_entry(parent, struct ubi_scan_leb, u.rb);
+
+		if (be32_to_cpu(new_vh->lnum) != seb->lnum) {
+			if (be32_to_cpu(new_vh->lnum) < seb->lnum)
+				p = &(*p)->rb_left;
+			else
+				p = &(*p)->rb_right;
+
+			continue;
+		}
+
+		/* This case can happen if the fastmap gets written
+		 * because of a volume change (creation, deletion, ..).
+		 * Then a PEB can be within the persistent EBA and the pool.
+		 */
+		if (seb->pnum == new_seb->pnum) {
+			kmem_cache_free(si->scan_leb_slab, new_seb);
+
+			return 0;
+		}
+
+		cmp_res = ubi_compare_lebs(ubi, seb, new_seb->pnum, new_vh);
+		if (cmp_res < 0)
+			return cmp_res;
+
+		/* new_seb is newer */
+		if (cmp_res & 1) {
+			victim = kmem_cache_alloc(si->scan_leb_slab,
+				GFP_KERNEL);
+			if (!victim)
+				return -ENOMEM;
+
+			victim->ec = seb->ec;
+			victim->pnum = seb->pnum;
+			list_add_tail(&victim->u.list, &si->erase);
+
+			seb->ec = new_seb->ec;
+			seb->pnum = new_seb->pnum;
+			seb->copy_flag = new_vh->copy_flag;
+			kmem_cache_free(si->scan_leb_slab, new_seb);
+
+		/* new_seb is older */
+		} else {
+			ubi_msg("Vol %i: LEB %i's PEB %i is old, dropping it\n",
+				sv->vol_id, seb->lnum, new_seb->pnum);
+			list_add_tail(&new_seb->u.list, &si->erase);
+		}
+
+		return 0;
+	}
+	/* This LEB is new, let's add it to the volume */
+
+	if (sv->vol_type == UBI_STATIC_VOLUME)
+		sv->used_ebs++;
+
+	sv->leb_count++;
+
+	rb_link_node(&new_seb->u.rb, parent, p);
+	rb_insert_color(&new_seb->u.rb, &sv->root);
+
+	return 0;
+}
+
+/**
+ * process_pool_seb - we found a non-empty PEB in a pool
+ * @ubi: UBI device object
+ * @si: scan info object
+ * @new_vh: the volume header derived from new_seb
+ * @new_seb: the SEB to be examined
+ */
+static int process_pool_seb(struct ubi_device *ubi, struct ubi_scan_info *si,
+			    struct ubi_vid_hdr *new_vh,
+			    struct ubi_scan_leb *new_seb)
+{
+	struct ubi_scan_volume *sv, *tmp_sv = NULL;
+	struct rb_node **p = &si->volumes.rb_node, *parent = NULL;
+	int found = 0;
+
+	if (be32_to_cpu(new_vh->vol_id) == UBI_FM_SB_VOLUME_ID ||
+		be32_to_cpu(new_vh->vol_id) == UBI_FM_DATA_VOLUME_ID) {
+		kmem_cache_free(si->scan_leb_slab, new_seb);
+
+		return 0;
+	}
+
+	/* Find the volume this SEB belongs to */
+	while (*p) {
+		parent = *p;
+		tmp_sv = rb_entry(parent, struct ubi_scan_volume, rb);
+
+		if (be32_to_cpu(new_vh->vol_id) > tmp_sv->vol_id)
+			p = &(*p)->rb_left;
+		else if (be32_to_cpu(new_vh->vol_id) < tmp_sv->vol_id)
+			p = &(*p)->rb_right;
+		else {
+			found = 1;
+			break;
+		}
+	}
+
+	if (found)
+		sv = tmp_sv;
+	else {
+		ubi_err("Orphaned volume in fastmap pool!");
+
+		return -EINVAL;
+	}
+
+	ubi_assert(be32_to_cpu(new_vh->vol_id) == sv->vol_id);
+
+	return update_vol(ubi, si, sv, new_vh, new_seb);
+}
+
+/**
+ * scan_pool - scans a pool for changed (no longer empty PEBs)
+ * @ubi: UBI device object
+ * @si: scan info object
+ * @pebs: an array of all PEB numbers in the to be scanned pool
+ * @pool_size: size of the pool (number of entries in @pebs)
+ * @max_sqnum2: pointer to the maximal sequence number
+ */
+static int scan_pool(struct ubi_device *ubi, struct ubi_scan_info *si,
+	int *pebs, int pool_size, unsigned long long *max_sqnum2)
+{
+	struct ubi_vid_hdr *vh;
+	struct ubi_ec_hdr *ech;
+	struct ubi_scan_leb *new_seb;
+	int i;
+	int pnum;
+	int err;
+	int ret = 0;
+
+	ech = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL);
+	if (!ech)
+		return -ENOMEM;
+
+	vh = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vh) {
+		kfree(ech);
+		return -ENOMEM;
+	}
+
+	/*
+	 * Now scan all PEBs in the pool to find changes which have been made
+	 * after the creation of the fastmap
+	 */
+	for (i = 0; i < pool_size; i++) {
+		pnum = be32_to_cpu(pebs[i]);
+
+		err = ubi_io_read_vid_hdr(ubi, pnum, vh, 0);
+
+		if (err == UBI_IO_FF)
+			continue;
+		else if (err == 0) {
+			err = ubi_io_read_ec_hdr(ubi, pnum, ech, 0);
+			if (err) {
+				ret = err;
+
+				goto out;
+			}
+
+			new_seb = kmem_cache_alloc(si->scan_leb_slab,
+				GFP_KERNEL);
+			if (!new_seb) {
+				ret = -ENOMEM;
+
+				goto out;
+			}
+
+			new_seb->ec = be64_to_cpu(ech->ec);
+			new_seb->pnum = pnum;
+			new_seb->lnum = be32_to_cpu(vh->lnum);
+			new_seb->sqnum = be64_to_cpu(vh->sqnum);
+			new_seb->copy_flag = vh->copy_flag;
+			new_seb->scrub = 0;
+
+			err = process_pool_seb(ubi, si, vh, new_seb);
+			if (err) {
+				ret = err;
+
+				goto out;
+			}
+
+			if (*max_sqnum2 < new_seb->sqnum)
+				*max_sqnum2 = new_seb->sqnum;
+		} else {
+			/* We are paranoid and fall back to scanning mode */
+			ubi_err("Checkpoint pool PEBs contains damaged PEBs!");
+			ret = err;
+
+			goto out;
+		}
+
+	}
+
+out:
+	ubi_free_vid_hdr(ubi, vh);
+	kfree(ech);
+
+	return ret;
+}
+
+/**
+ * ubi_scan_fastmap - creates ubi_scan_info from a fastmap.
+ * @ubi: UBI device object
+ * @fm_raw: the fastmap it self as byte array
+ * @fm_size: size of the fastmap in bytes
+ */
+struct ubi_scan_info *ubi_scan_fastmap(struct ubi_device *ubi, char *fm_raw,
+				       size_t fm_size)
+{
+	struct list_head used;
+	struct ubi_scan_volume *sv;
+	struct ubi_scan_leb *seb, *tmp_seb, *_tmp_seb;
+	struct ubi_scan_info *si;
+	int i, j;
+
+	size_t fm_pos = 0;
+	struct ubi_fm_sb *fmsb;
+	struct ubi_fm_hdr *fmhdr;
+	struct ubi_fm_scan_pool *fmpl;
+	struct ubi_fm_ec *fmec;
+	struct ubi_fm_volhdr *fmvhdr;
+	struct ubi_fm_eba *fm_eba;
+
+	unsigned long long max_sqnum2 = 0;
+
+	si = kzalloc(sizeof(struct ubi_scan_info), GFP_KERNEL);
+	if (!si)
+		return ERR_PTR(-ENOMEM);
+
+	INIT_LIST_HEAD(&used);
+	INIT_LIST_HEAD(&si->corr);
+	INIT_LIST_HEAD(&si->free);
+	INIT_LIST_HEAD(&si->erase);
+	INIT_LIST_HEAD(&si->alien);
+	si->volumes = RB_ROOT;
+	si->min_ec = UBI_MAX_ERASECOUNTER;
+
+	si->scan_leb_slab = kmem_cache_create("ubi_scan_leb_slab",
+					      sizeof(struct ubi_scan_leb),
+					      0, 0, NULL);
+	if (!si->scan_leb_slab)
+		goto fail;
+
+	fmsb = (struct ubi_fm_sb *)(fm_raw);
+	si->max_sqnum = fmsb->sqnum;
+	fm_pos += sizeof(struct ubi_fm_sb);
+	if (fm_pos >= fm_size)
+		goto fail;
+
+	fmhdr = (struct ubi_fm_hdr *)(fm_raw + fm_pos);
+	fm_pos += sizeof(*fmhdr);
+	if (fm_pos >= fm_size)
+		goto fail;
+
+	if (fmhdr->magic != UBI_FM_HDR_MAGIC)
+		goto fail;
+
+	fmpl = (struct ubi_fm_scan_pool *)(fm_raw + fm_pos);
+	fm_pos += sizeof(*fmpl);
+	if (fm_pos >= fm_size)
+		goto fail;
+	if (fmpl->magic != UBI_FM_POOL_MAGIC)
+		goto fail;
+
+	/* read EC values from free list */
+	for (i = 0; i < be32_to_cpu(fmhdr->nfree); i++) {
+		fmec = (struct ubi_fm_ec *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*fmec);
+		if (fm_pos >= fm_size)
+			goto fail;
+
+		add_seb(si, &si->free, be32_to_cpu(fmec->pnum),
+			be32_to_cpu(fmec->ec));
+	}
+
+	/* read EC values from used list */
+	for (i = 0; i < be32_to_cpu(fmhdr->nused); i++) {
+		fmec = (struct ubi_fm_ec *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*fmec);
+		if (fm_pos >= fm_size)
+			goto fail;
+
+		add_seb(si, &used, be32_to_cpu(fmec->pnum),
+			be32_to_cpu(fmec->ec));
+	}
+
+	si->mean_ec = div_u64(si->ec_sum, si->ec_count);
+
+	/* Iterate over all volumes and read their EBA table */
+	for (i = 0; i < be32_to_cpu(fmhdr->nvol); i++) {
+		fmvhdr = (struct ubi_fm_volhdr *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*fmvhdr);
+		if (fm_pos >= fm_size)
+			goto fail;
+
+		if (fmvhdr->magic != UBI_FM_VHDR_MAGIC)
+			goto fail;
+
+		sv = add_vol(si, be32_to_cpu(fmvhdr->vol_id),
+			be32_to_cpu(fmvhdr->used_ebs),
+			be32_to_cpu(fmvhdr->data_pad),
+			fmvhdr->vol_type, be32_to_cpu(fmvhdr->last_eb_bytes));
+
+		if (!sv)
+			goto fail;
+
+		si->vols_found++;
+		if (si->highest_vol_id < be32_to_cpu(fmvhdr->vol_id))
+			si->highest_vol_id = be32_to_cpu(fmvhdr->vol_id);
+
+		fm_eba = (struct ubi_fm_eba *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*fm_eba) + (sizeof(__be32) * be32_to_cpu(fm_eba->nused));
+		if (fm_pos >= fm_size)
+			goto fail;
+
+		if (fm_eba->magic != UBI_FM_EBA_MAGIC)
+			goto fail;
+
+		for (j = 0; j < be32_to_cpu(fm_eba->nused); j++) {
+
+			if ((int)be32_to_cpu(fm_eba->pnum[j]) < 0)
+				continue;
+
+			seb = NULL;
+			list_for_each_entry(tmp_seb, &used, u.list) {
+				if (tmp_seb->pnum == be32_to_cpu(fm_eba->pnum[j]))
+					seb = tmp_seb;
+			}
+
+			/* Corner case, this PEB must be in the pool */
+			if (!seb)
+				continue;
+
+			seb->lnum = j;
+			assign_seb_to_sv(si, seb, sv);
+
+			dbg_bld("Inserting pnum %i (leb %i) to vol %i",
+				seb->pnum, seb->lnum, sv->vol_id);
+		}
+	}
+
+	/*
+	 * The remainning PEB in the used list are not used.
+	 * They lived in the fastmap pool but got never used.
+	 */
+	list_for_each_entry_safe(tmp_seb, _tmp_seb, &used, u.list) {
+		list_del(&tmp_seb->u.list);
+		list_add_tail(&tmp_seb->u.list, &si->free);
+	}
+
+	if (scan_pool(ubi, si, fmpl->pebs, be32_to_cpu(fmpl->size),
+			&max_sqnum2) < 0)
+		goto fail;
+
+	if (max_sqnum2 > si->max_sqnum)
+		si->max_sqnum = max_sqnum2;
+
+	return si;
+
+fail:
+	ubi_scan_destroy_si(si);
+	return NULL;
+}
+
+/**
+ * ubi_read_fastmap - read the fastmap
+ * @ubi: UBI device object
+ * @cb_sb_pnum: PEB number of the fastmap super block
+ */
+struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
+					  int cb_sb_pnum)
+{
+	struct ubi_fm_sb *fmsb;
+	struct ubi_vid_hdr *vh;
+	int ret, i, nblocks;
+	char *fm_raw;
+	size_t fm_size;
+	__be32 data_crc;
+	unsigned long long sqnum = 0;
+	struct ubi_scan_info *si = NULL;
+
+	fmsb = kmalloc(sizeof(*fmsb), GFP_KERNEL);
+	if (!fmsb) {
+		si = ERR_PTR(-ENOMEM);
+
+		goto out;
+	}
+
+	ret = ubi_io_read(ubi, fmsb, cb_sb_pnum, ubi->leb_start, sizeof(*fmsb));
+	if (ret) {
+		ubi_err("Unable to read fastmap super block");
+		si = ERR_PTR(ret);
+		kfree(fmsb);
+
+		goto out;
+	}
+
+	if (fmsb->magic != UBI_FM_SB_MAGIC) {
+		ubi_err("Super block magic does not match");
+		si = ERR_PTR(-EINVAL);
+		kfree(fmsb);
+
+		goto out;
+	}
+
+	if (fmsb->version != UBI_FM_FMT_VERSION) {
+		ubi_err("Unknown fastmap format version!");
+		si = ERR_PTR(-EINVAL);
+		kfree(fmsb);
+
+		goto out;
+	}
+
+	nblocks = be32_to_cpu(fmsb->nblocks);
+
+	if (nblocks > UBI_FM_MAX_BLOCKS || nblocks < 1) {
+		ubi_err("Number of fastmap blocks is invalid");
+		si = ERR_PTR(-EINVAL);
+		kfree(fmsb);
+
+		goto out;
+	}
+
+	fm_size = ubi->leb_size * nblocks;
+	/* fm_raw will contain the whole fastmap */
+	fm_raw = vzalloc(fm_size);
+	if (!fm_raw) {
+		si = ERR_PTR(-ENOMEM);
+		kfree(fmsb);
+	}
+
+	vh = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vh) {
+		si = ERR_PTR(-ENOMEM);
+		kfree(fmsb);
+
+		goto free_raw;
+	}
+
+	for (i = 0; i < nblocks; i++) {
+		ret = ubi_io_read_vid_hdr(ubi, be32_to_cpu(fmsb->block_loc[i]),
+			vh, 0);
+		if (ret) {
+			ubi_err("Unable to read fastmap block# %i (PEB: %i)",
+				i, be32_to_cpu(fmsb->block_loc[i]));
+			si = ERR_PTR(ret);
+
+			goto free_vhdr;
+		}
+
+		if (i == 0) {
+			if (be32_to_cpu(vh->vol_id) != UBI_FM_SB_VOLUME_ID) {
+				si = ERR_PTR(-EINVAL);
+
+				goto free_vhdr;
+			}
+		} else {
+			if (be32_to_cpu(vh->vol_id) != UBI_FM_DATA_VOLUME_ID) {
+				goto free_vhdr;
+
+				si = ERR_PTR(-EINVAL);
+			}
+		}
+
+		if (sqnum < be64_to_cpu(vh->sqnum))
+			sqnum = be64_to_cpu(vh->sqnum);
+
+		ret = ubi_io_read(ubi, fm_raw + (ubi->leb_size * i),
+			be32_to_cpu(fmsb->block_loc[i]),
+			ubi->leb_start, ubi->leb_size);
+
+		if (ret) {
+			ubi_err("Unable to read fastmap block# %i (PEB: %i)",
+				i, be32_to_cpu(fmsb->block_loc[i]));
+			si = ERR_PTR(ret);
+
+			goto free_vhdr;
+		}
+	}
+
+	kfree(fmsb);
+
+	fmsb = (struct ubi_fm_sb *)fm_raw;
+	data_crc = crc32_be(UBI_CRC32_INIT, fm_raw + sizeof(*fmsb),
+		fm_size - sizeof(*fmsb));
+	if (data_crc != fmsb->data_crc) {
+		ubi_err("Checkpoint data CRC is invalid");
+		si = ERR_PTR(-EINVAL);
+
+		goto free_vhdr;
+	}
+
+	fmsb->sqnum = sqnum;
+
+	si = ubi_scan_fastmap(ubi, fm_raw, fm_size);
+	if (!si) {
+		si = ERR_PTR(-EINVAL);
+
+		goto free_vhdr;
+	}
+
+	/* Store the fastmap position into the ubi_device struct */
+	ubi->fm = kmalloc(sizeof(struct ubi_fastmap), GFP_KERNEL);
+	if (!ubi->fm) {
+		si = ERR_PTR(-ENOMEM);
+		ubi_scan_destroy_si(si);
+
+		goto free_vhdr;
+	}
+
+	ubi->fm->size = fm_size;
+	ubi->fm->used_blocks = nblocks;
+
+	for (i = 0; i < UBI_FM_MAX_BLOCKS; i++) {
+		if (i < nblocks) {
+			ubi->fm->peb[i] = be32_to_cpu(fmsb->block_loc[i]);
+			ubi->fm->ec[i] = be32_to_cpu(fmsb->block_ec[i]);
+		} else {
+			ubi->fm->peb[i] = -1;
+			ubi->fm->ec[i] = 0;
+		}
+	}
+
+free_vhdr:
+	ubi_free_vid_hdr(ubi, vh);
+free_raw:
+	vfree(fm_raw);
+out:
+	return si;
+}
+
+/**
+ * ubi_find_fastmap - searches the first UBI_FM_MAX_START PEBs for the
+ * fastmap super block.
+ * @ubi: UBI device object
+ */
+int ubi_find_fastmap(struct ubi_device *ubi)
+{
+	int i, ret;
+	int fm_sb = -ENOENT;
+	struct ubi_vid_hdr *vhdr;
+
+	vhdr = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vhdr)
+		return -ENOMEM;
+
+	for (i = 0; i < UBI_FM_MAX_START; i++) {
+		ret = ubi_io_read_vid_hdr(ubi, i, vhdr, 0);
+		/* ignore read errors */
+		if (ret)
+			continue;
+
+		if (be32_to_cpu(vhdr->vol_id) == UBI_FM_SB_VOLUME_ID) {
+			fm_sb = i;
+			break;
+		}
+	}
+
+	ubi_free_vid_hdr(ubi, vhdr);
+	return fm_sb;
+}
+
+/**
+ * ubi_write_fastmap - writes a fastmap
+ * @ubi: UBI device object
+ * @new_fm: the to be written checkppoint
+ */
+static int ubi_write_fastmap(struct ubi_device *ubi,
+				struct ubi_fastmap *new_fm)
+{
+	int ret;
+	size_t fm_pos = 0;
+	char *fm_raw;
+	int i, j;
+
+	struct ubi_fm_sb *fmsb;
+	struct ubi_fm_hdr *cph;
+	struct ubi_fm_scan_pool *cppl;
+	struct ubi_fm_ec *cec;
+	struct ubi_fm_volhdr *cvh;
+	struct ubi_fm_eba *ceba;
+
+	struct rb_node *node;
+	struct ubi_wl_entry *wl_e;
+	struct ubi_volume *vol;
+
+	struct ubi_vid_hdr *svhdr, *dvhdr;
+
+	int nfree, nused, nvol;
+
+	fm_raw = vzalloc(new_fm->size);
+	if (!fm_raw) {
+		ret = -ENOMEM;
+
+		goto out;
+	}
+
+	svhdr = new_fm_vhdr(ubi, UBI_FM_SB_VOLUME_ID);
+	if (!svhdr) {
+		ret = -ENOMEM;
+
+		goto out_vfree;
+	}
+
+	dvhdr = new_fm_vhdr(ubi, UBI_FM_DATA_VOLUME_ID);
+	if (!dvhdr) {
+		ret = -ENOMEM;
+
+		goto out_kfree;
+	}
+
+	spin_lock(&ubi->volumes_lock);
+	spin_lock(&ubi->wl_lock);
+
+	fmsb = (struct ubi_fm_sb *)fm_raw;
+	fm_pos += sizeof(*fmsb);
+	ubi_assert(fm_pos <= new_fm->size);
+
+	cph = (struct ubi_fm_hdr *)(fm_raw + fm_pos);
+	fm_pos += sizeof(*cph);
+	ubi_assert(fm_pos <= new_fm->size);
+
+	fmsb->magic = UBI_FM_SB_MAGIC;
+	fmsb->version = UBI_FM_FMT_VERSION;
+	fmsb->nblocks = cpu_to_be32(new_fm->used_blocks);
+	/* the max sqnum will be filled in while *reading* the fastmap */
+	fmsb->sqnum = 0;
+
+	cph->magic = UBI_FM_HDR_MAGIC;
+	nfree = 0;
+	nused = 0;
+	nvol = 0;
+
+	cppl = (struct ubi_fm_scan_pool *)(fm_raw + fm_pos);
+	fm_pos += sizeof(*cppl);
+	cppl->magic = UBI_FM_POOL_MAGIC;
+	cppl->size = cpu_to_be32(ubi->fm_pool.size);
+
+	for (i = 0; i < ubi->fm_pool.size; i++)
+		cppl->pebs[i] = cpu_to_be32(ubi->fm_pool.pebs[i]);
+
+	for (node = rb_first(&ubi->free); node; node = rb_next(node)) {
+		wl_e = rb_entry(node, struct ubi_wl_entry, u.rb);
+		cec = (struct ubi_fm_ec *)(fm_raw + fm_pos);
+
+		cec->pnum = cpu_to_be32(wl_e->pnum);
+		cec->ec = cpu_to_be32(wl_e->ec);
+
+		nfree++;
+		fm_pos += sizeof(*cec);
+		ubi_assert(fm_pos <= new_fm->size);
+	}
+	cph->nfree = cpu_to_be32(nfree);
+
+	for (node = rb_first(&ubi->used); node; node = rb_next(node)) {
+		wl_e = rb_entry(node, struct ubi_wl_entry, u.rb);
+		cec = (struct ubi_fm_ec *)(fm_raw + fm_pos);
+
+		cec->pnum = cpu_to_be32(wl_e->pnum);
+		cec->ec = cpu_to_be32(wl_e->ec);
+
+		nused++;
+		fm_pos += sizeof(*cec);
+		ubi_assert(fm_pos <= new_fm->size);
+	}
+	cph->nused = cpu_to_be32(nused);
+
+	for (i = 0; i < UBI_MAX_VOLUMES + UBI_INT_VOL_COUNT; i++) {
+		vol = ubi->volumes[i];
+
+		if (!vol)
+			continue;
+
+		nvol++;
+
+		cvh = (struct ubi_fm_volhdr *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*cvh);
+		ubi_assert(fm_pos <= new_fm->size);
+
+		cvh->magic = UBI_FM_VHDR_MAGIC;
+		cvh->vol_id = cpu_to_be32(vol->vol_id);
+		cvh->vol_type = vol->vol_type;
+		cvh->used_ebs = cpu_to_be32(vol->used_ebs);
+		cvh->data_pad = cpu_to_be32(vol->data_pad);
+		cvh->last_eb_bytes = cpu_to_be32(vol->last_eb_bytes);
+
+		ubi_assert(vol->vol_type == UBI_DYNAMIC_VOLUME ||
+			vol->vol_type == UBI_STATIC_VOLUME);
+
+		ceba = (struct ubi_fm_eba *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*ceba) + (sizeof(__be32) * vol->used_ebs);
+		ubi_assert(fm_pos <= new_fm->size);
+
+		for (j = 0; j < vol->used_ebs; j++)
+			ceba->pnum[j] = cpu_to_be32(vol->eba_tbl[j]);
+
+		ceba->nused = cpu_to_be32(j);
+		ceba->magic = UBI_FM_EBA_MAGIC;
+	}
+	cph->nvol = cpu_to_be32(nvol);
+
+	svhdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
+	svhdr->lnum = 0;
+
+	spin_unlock(&ubi->wl_lock);
+	spin_unlock(&ubi->volumes_lock);
+
+	dbg_bld("Writing fastmap SB to PEB %i\n", new_fm->peb[0]);
+	ret = ubi_io_write_vid_hdr(ubi, new_fm->peb[0], svhdr);
+	if (ret) {
+		ubi_err("Unable to write vid_hdr to fastmap SB!\n");
+
+		goto out_kfree;
+	}
+
+	for (i = 0; i < UBI_FM_MAX_BLOCKS; i++) {
+		fmsb->block_loc[i] = cpu_to_be32(new_fm->peb[i]);
+		fmsb->block_ec[i] = cpu_to_be32(new_fm->ec[i]);
+	}
+
+	fmsb->data_crc = 0;
+	fmsb->data_crc = crc32_be(UBI_CRC32_INIT, fm_raw + sizeof(*fmsb),
+		new_fm->size - sizeof(*fmsb));
+
+	for (i = 1; i < new_fm->used_blocks; i++) {
+		dvhdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
+		dvhdr->lnum = cpu_to_be32(i);
+		dbg_bld("Writing fastmap data to PEB %i sqnum %llu\n",
+			new_fm->peb[i], be64_to_cpu(dvhdr->sqnum));
+		ret = ubi_io_write_vid_hdr(ubi, new_fm->peb[i], dvhdr);
+		if (ret) {
+			ubi_err("Unable to write vid_hdr to PEB %i!\n",
+				new_fm->peb[i]);
+
+			goto out_kfree;
+		}
+	}
+
+	for (i = 0; i < new_fm->used_blocks; i++) {
+		ret = ubi_io_write(ubi, fm_raw + (i * ubi->leb_size),
+			new_fm->peb[i], ubi->leb_start, ubi->leb_size);
+		if (ret) {
+			ubi_err("Unable to write fastmap to PEB %i!\n",
+				new_fm->peb[i]);
+
+			goto out_kfree;
+		}
+	}
+
+	ubi_assert(new_fm);
+	ubi->fm = new_fm;
+
+	dbg_bld("Checkpoint written!");
+
+out_kfree:
+	kfree(svhdr);
+out_vfree:
+	vfree(fm_raw);
+out:
+	return ret;
+}
+
+/**
+ * get_ec - returns the erase counter of a given PEB
+ * @ubi: UBI device object
+ * @pnum: PEB number
+ */
+static int get_ec(struct ubi_device *ubi, int pnum)
+{
+	struct ubi_wl_entry *e;
+
+	e = ubi->lookuptbl[pnum];
+
+	/* can this really happen? */
+	if (!e)
+		return ubi->mean_ec ?: 1;
+	else
+		return e->ec;
+}
+
+/**
+ * ubi_update_fastmap - will be called by UBI if a volume changes or
+ * a fastmap pool becomes full.
+ * @ubi: UBI device object
+ */
+int ubi_update_fastmap(struct ubi_device *ubi)
+{
+	int ret, i;
+	struct ubi_fastmap *new_fm;
+
+	if (ubi->ro_mode)
+		return 0;
+
+	new_fm = kmalloc(sizeof(*new_fm), GFP_KERNEL);
+	if (!new_fm)
+		return -ENOMEM;
+
+	ubi->old_fm = ubi->fm;
+	ubi->fm = NULL;
+
+	if (ubi->old_fm) {
+		spin_lock(&ubi->wl_lock);
+		new_fm->peb[0] = ubi_wl_get_fm_peb(ubi, UBI_FM_MAX_START);
+		spin_unlock(&ubi->wl_lock);
+		/* no fresh early PEB was found, reuse the old one */
+		if (new_fm->peb[0] < 0) {
+			struct ubi_ec_hdr *ec_hdr;
+
+			ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL);
+			if (!ec_hdr) {
+				kfree(new_fm);
+				return -ENOMEM;
+			}
+
+			/* we have to erase the block by hand */
+
+			ret = ubi_io_read_ec_hdr(ubi, ubi->old_fm->peb[0],
+				ec_hdr, 0);
+			if (ret) {
+				ubi_err("Unable to read EC header");
+
+				kfree(new_fm);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ret = ubi_io_sync_erase(ubi, ubi->old_fm->peb[0], 0);
+			if (ret < 0) {
+				ubi_err("Unable to erase old SB");
+
+				kfree(new_fm);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ec_hdr->ec += ret;
+			if (ret > UBI_MAX_ERASECOUNTER) {
+				ubi_err("Erase counter overflow!");
+				kfree(new_fm);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ret = ubi_io_write_ec_hdr(ubi, ubi->old_fm->peb[0],
+				ec_hdr);
+			kfree(ec_hdr);
+			if (ret) {
+				ubi_err("Unable to write new EC header");
+				kfree(new_fm);
+				return -EINVAL;
+			}
+
+			new_fm->peb[0] = ubi->old_fm->peb[0];
+			new_fm->ec[0] = ubi->old_fm->ec[0];
+		} else {
+			/* we've got a new early PEB, return the old one */
+			ubi_wl_put_fm_peb(ubi, ubi->old_fm->peb[0], 0);
+			new_fm->ec[0] = get_ec(ubi, new_fm->peb[0]);
+		}
+
+		/* return all other fastmap block to the wl system */
+		for (i = 1; i < UBI_FM_MAX_BLOCKS; i++) {
+			if (ubi->old_fm->peb[i] >= 0)
+				ubi_wl_put_fm_peb(ubi, ubi->old_fm->peb[i], 0);
+			else
+				break;
+		}
+	} else {
+		spin_lock(&ubi->wl_lock);
+		new_fm->peb[0] = ubi_wl_get_fm_peb(ubi, UBI_FM_MAX_START);
+		spin_unlock(&ubi->wl_lock);
+		if (new_fm->peb[0] < 0) {
+			ubi_err("Could not find an early PEB");
+			kfree(new_fm);
+			return -ENOSPC;
+		}
+		new_fm->ec[0] = get_ec(ubi, new_fm->peb[0]);
+	}
+
+	new_fm->size = sizeof(struct ubi_fm_hdr) + \
+			sizeof(struct ubi_fm_scan_pool) + \
+			(ubi->peb_count * sizeof(struct ubi_fm_ec)) + \
+			(sizeof(struct ubi_fm_eba) + \
+			(ubi->peb_count * sizeof(__be32))) + \
+			sizeof(struct ubi_fm_volhdr) * UBI_MAX_VOLUMES;
+	new_fm->size = roundup(new_fm->size, ubi->leb_size);
+
+	new_fm->used_blocks = new_fm->size / ubi->leb_size;
+
+	if (new_fm->used_blocks > UBI_FM_MAX_BLOCKS) {
+		ubi_err("Checkpoint too large");
+		kfree(new_fm);
+
+		return -ENOSPC;
+	}
+
+	/* give the wl subsystem a chance to produce some free blocks */
+	cond_resched();
+
+	for (i = 1; i < UBI_FM_MAX_BLOCKS; i++) {
+		if (i < new_fm->used_blocks) {
+			spin_lock(&ubi->wl_lock);
+			new_fm->peb[i] = ubi_wl_get_fm_peb(ubi, INT_MAX);
+			spin_unlock(&ubi->wl_lock);
+			if (new_fm->peb[i] < 0) {
+				ubi_err("Could not get any free erase block");
+
+				while (i--)
+					ubi_wl_put_fm_peb(ubi, new_fm->peb[i],
+						0);
+
+				kfree(new_fm);
+
+				return -ENOSPC;
+			}
+
+			new_fm->ec[i] = get_ec(ubi, new_fm->peb[i]);
+		} else {
+			new_fm->peb[i] = -1;
+			new_fm->ec[i] = 0;
+		}
+	}
+
+	kfree(ubi->old_fm);
+	ubi->old_fm = NULL;
+
+	return ubi_write_fastmap(ubi, new_fm);
+}
diff --git a/drivers/mtd/ubi/scan.c b/drivers/mtd/ubi/scan.c
index 69be65f..b4ab79f 100644
--- a/drivers/mtd/ubi/scan.c
+++ b/drivers/mtd/ubi/scan.c
@@ -1011,7 +1011,11 @@ static int process_eb(struct ubi_device *ubi, struct ubi_scan_info *si,
 	}
 
 	vol_id = be32_to_cpu(vidh->vol_id);
-	if (vol_id > UBI_MAX_VOLUMES && vol_id != UBI_LAYOUT_VOLUME_ID) {
+
+	if (vol_id > UBI_MAX_VOLUMES &&
+		vol_id != UBI_LAYOUT_VOLUME_ID &&
+		vol_id != UBI_FM_SB_VOLUME_ID &&
+		vol_id != UBI_FM_DATA_VOLUME_ID) {
 		int lnum = be32_to_cpu(vidh->lnum);
 
 		/* Unsupported internal volume */
diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index cf5cfaf..5ed03b5 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -624,11 +624,15 @@ int ubi_enumerate_volumes(struct notifier_block *nb);
 void ubi_do_get_device_info(struct ubi_device *ubi, struct ubi_device_info *di);
 void ubi_do_get_volume_info(struct ubi_device *ubi, struct ubi_volume *vol,
 			    struct ubi_volume_info *vi);
-
 /* scan.c */
 int ubi_compare_lebs(struct ubi_device *ubi, const struct ubi_scan_leb *seb,
 		      int pnum, const struct ubi_vid_hdr *vid_hdr);
 
+/* fastmap.c */
+int ubi_update_fastmap(struct ubi_device *ubi);
+struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi, int fm_sb_pnum);
+int ubi_find_fastmap(struct ubi_device *ubi);
+
 /*
  * ubi_rb_for_each_entry - walk an RB-tree.
  * @rb: a pointer to type 'struct rb_node' to use as a loop counter
-- 
1.7.6.5

[PATCH 6/7] [RFC] UBI: Implement fastmapping support

[Richard Weinberger]

Implements UBI fastmapping support.
It reduces the attaching time from O(N) to O(1).
Fastmaps are written on demand and upon changes of the volume layout.
If the recovery from a fastmap fails we fall back to scanning mode

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/Makefile  |    2 +-
 drivers/mtd/ubi/fastmap.c | 1107 +++++++++++++++++++++++++++++++++++++++++++++
 drivers/mtd/ubi/scan.c    |    6 +-
 drivers/mtd/ubi/ubi.h     |    6 +-
 4 files changed, 1118 insertions(+), 3 deletions(-)
 create mode 100644 drivers/mtd/ubi/fastmap.c

diff --git a/drivers/mtd/ubi/Makefile b/drivers/mtd/ubi/Makefile
index da71655..f4a4280 100644
--- a/drivers/mtd/ubi/Makefile
+++ b/drivers/mtd/ubi/Makefile
@@ -1,6 +1,6 @@
 obj-$(CONFIG_MTD_UBI) += ubi.o
 
 ubi-y += vtbl.o vmt.o upd.o build.o cdev.o kapi.o eba.o io.o wl.o scan.o
-ubi-y += misc.o debug.o
+ubi-y += misc.o debug.o fastmap.o
 
 obj-$(CONFIG_MTD_UBI_GLUEBI) += gluebi.o
diff --git a/drivers/mtd/ubi/fastmap.c b/drivers/mtd/ubi/fastmap.c
new file mode 100644
index 0000000..2ea1682
--- /dev/null
+++ b/drivers/mtd/ubi/fastmap.c
@@ -0,0 +1,1107 @@
+/*
+ * Copyright (c) 2012 Linutronix GmbH
+ * Author: Richard Weinberger <richard@nod.at>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
+ * the GNU General Public License for more details.
+ *
+ */
+
+#include <linux/crc32.h>
+#include "ubi.h"
+
+/**
+ * new_fm_vhdr - allocate a new volume header for fastmap usage.
+ * @ubi: UBI device description object
+ * @vol_id: the VID of the new header
+ */
+static struct ubi_vid_hdr *new_fm_vhdr(struct ubi_device *ubi, int vol_id)
+{
+	struct ubi_vid_hdr *new;
+
+	new = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!new)
+		goto out;
+
+	new->vol_type = UBI_VID_DYNAMIC;
+	new->vol_id = cpu_to_be32(vol_id);
+
+	/* the fastmap has be deleted on older kernels */
+	new->compat = UBI_COMPAT_DELETE;
+
+out:
+	return new;
+}
+
+/**
+ * add_seb - create and add a scan erase block to a given list.
+ * @si: UBI scan info object
+ * @list: the target list
+ * @pnum: PEB number of the new scan erase block
+ * @ec: erease counter of the new SEB
+ */
+static int add_seb(struct ubi_scan_info *si, struct list_head *list,
+		   int pnum, int ec)
+{
+	struct ubi_scan_leb *seb;
+
+	seb = kmem_cache_alloc(si->scan_leb_slab, GFP_KERNEL);
+	if (!seb)
+		return -ENOMEM;
+
+	seb->pnum = pnum;
+	seb->ec = ec;
+	seb->lnum = -1;
+	seb->scrub = seb->copy_flag = seb->sqnum = 0;
+
+	si->ec_sum += seb->ec;
+	si->ec_count++;
+
+	if (si->max_ec < seb->ec)
+		si->max_ec = seb->ec;
+
+	if (si->min_ec > seb->ec)
+		si->min_ec = seb->ec;
+
+	list_add_tail(&seb->u.list, list);
+
+	return 0;
+}
+
+/**
+ * add_vol - create and add a new scan volume to ubi_scan_info.
+ * @si: ubi_scan_info object
+ * @vol_id: VID of the new volume
+ * @used_ebs: number of used EBS
+ * @data_pad: data padding value of the new volume
+ * @vol_type: volume type
+ * @last_eb_bytes: number of bytes in the last LEB
+ */
+static struct ubi_scan_volume *add_vol(struct ubi_scan_info *si, int vol_id,
+				       int used_ebs, int data_pad, u8 vol_type,
+				       int last_eb_bytes)
+{
+	struct ubi_scan_volume *sv;
+	struct rb_node **p = &si->volumes.rb_node, *parent = NULL;
+
+	while (*p) {
+		parent = *p;
+		sv = rb_entry(parent, struct ubi_scan_volume, rb);
+
+		if (vol_id > sv->vol_id)
+			p = &(*p)->rb_left;
+		else if (vol_id > sv->vol_id)
+			p = &(*p)->rb_right;
+	}
+
+	sv = kmalloc(sizeof(struct ubi_scan_volume), GFP_KERNEL);
+	if (!sv)
+		goto out;
+
+	sv->highest_lnum = sv->leb_count = 0;
+	sv->vol_id = vol_id;
+	sv->used_ebs = used_ebs;
+	sv->data_pad = data_pad;
+	sv->last_data_size = last_eb_bytes;
+	sv->compat = 0;
+	sv->vol_type = vol_type;
+	sv->root = RB_ROOT;
+
+	rb_link_node(&sv->rb, parent, p);
+	rb_insert_color(&sv->rb, &si->volumes);
+
+out:
+	return sv;
+}
+
+/**
+ * assign_seb_to_sv - assigns a SEB to a given scan_volume and removes it
+ * from it's original list.
+ * @si: ubi_scan_info object
+ * @seb: the to be assigned SEB
+ * @sv: target scan volume
+ */
+static void assign_seb_to_sv(struct ubi_scan_info *si,
+			     struct ubi_scan_leb *seb,
+			     struct ubi_scan_volume *sv)
+{
+	struct ubi_scan_leb *tmp_seb;
+	struct rb_node **p = &si->volumes.rb_node, *parent = NULL;
+
+	p = &sv->root.rb_node;
+	while (*p) {
+		parent = *p;
+
+		tmp_seb = rb_entry(parent, struct ubi_scan_leb, u.rb);
+		if (seb->lnum != tmp_seb->lnum) {
+			if (seb->lnum < tmp_seb->lnum)
+				p = &(*p)->rb_left;
+			else
+				p = &(*p)->rb_right;
+
+			continue;
+		} else
+			break;
+	}
+
+	list_del(&seb->u.list);
+	sv->leb_count++;
+
+	rb_link_node(&seb->u.rb, parent, p);
+	rb_insert_color(&seb->u.rb, &sv->root);
+}
+
+/**
+ * update_vol - inserts or updates a LEB which was found a pool.
+ * @ubi: the UBI device object
+ * @si: scan info object
+ * @sv: the scan volume where this LEB belongs to
+ * @new_vh: the volume header derived from new_seb
+ * @new_seb: the SEB to be examined
+ */
+static int update_vol(struct ubi_device *ubi, struct ubi_scan_info *si,
+		      struct ubi_scan_volume *sv, struct ubi_vid_hdr *new_vh,
+		      struct ubi_scan_leb *new_seb)
+{
+	struct rb_node **p = &sv->root.rb_node, *parent = NULL;
+	struct ubi_scan_leb *seb, *victim;
+	int cmp_res;
+
+	while (*p) {
+		parent = *p;
+		seb = rb_entry(parent, struct ubi_scan_leb, u.rb);
+
+		if (be32_to_cpu(new_vh->lnum) != seb->lnum) {
+			if (be32_to_cpu(new_vh->lnum) < seb->lnum)
+				p = &(*p)->rb_left;
+			else
+				p = &(*p)->rb_right;
+
+			continue;
+		}
+
+		/* This case can happen if the fastmap gets written
+		 * because of a volume change (creation, deletion, ..).
+		 * Then a PEB can be within the persistent EBA and the pool.
+		 */
+		if (seb->pnum == new_seb->pnum) {
+			kmem_cache_free(si->scan_leb_slab, new_seb);
+
+			return 0;
+		}
+
+		cmp_res = ubi_compare_lebs(ubi, seb, new_seb->pnum, new_vh);
+		if (cmp_res < 0)
+			return cmp_res;
+
+		/* new_seb is newer */
+		if (cmp_res & 1) {
+			victim = kmem_cache_alloc(si->scan_leb_slab,
+				GFP_KERNEL);
+			if (!victim)
+				return -ENOMEM;
+
+			victim->ec = seb->ec;
+			victim->pnum = seb->pnum;
+			list_add_tail(&victim->u.list, &si->erase);
+
+			seb->ec = new_seb->ec;
+			seb->pnum = new_seb->pnum;
+			seb->copy_flag = new_vh->copy_flag;
+			kmem_cache_free(si->scan_leb_slab, new_seb);
+
+		/* new_seb is older */
+		} else {
+			ubi_msg("Vol %i: LEB %i's PEB %i is old, dropping it\n",
+				sv->vol_id, seb->lnum, new_seb->pnum);
+			list_add_tail(&new_seb->u.list, &si->erase);
+		}
+
+		return 0;
+	}
+	/* This LEB is new, let's add it to the volume */
+
+	if (sv->vol_type == UBI_STATIC_VOLUME)
+		sv->used_ebs++;
+
+	sv->leb_count++;
+
+	rb_link_node(&new_seb->u.rb, parent, p);
+	rb_insert_color(&new_seb->u.rb, &sv->root);
+
+	return 0;
+}
+
+/**
+ * process_pool_seb - we found a non-empty PEB in a pool
+ * @ubi: UBI device object
+ * @si: scan info object
+ * @new_vh: the volume header derived from new_seb
+ * @new_seb: the SEB to be examined
+ */
+static int process_pool_seb(struct ubi_device *ubi, struct ubi_scan_info *si,
+			    struct ubi_vid_hdr *new_vh,
+			    struct ubi_scan_leb *new_seb)
+{
+	struct ubi_scan_volume *sv, *tmp_sv = NULL;
+	struct rb_node **p = &si->volumes.rb_node, *parent = NULL;
+	int found = 0;
+
+	if (be32_to_cpu(new_vh->vol_id) == UBI_FM_SB_VOLUME_ID ||
+		be32_to_cpu(new_vh->vol_id) == UBI_FM_DATA_VOLUME_ID) {
+		kmem_cache_free(si->scan_leb_slab, new_seb);
+
+		return 0;
+	}
+
+	/* Find the volume this SEB belongs to */
+	while (*p) {
+		parent = *p;
+		tmp_sv = rb_entry(parent, struct ubi_scan_volume, rb);
+
+		if (be32_to_cpu(new_vh->vol_id) > tmp_sv->vol_id)
+			p = &(*p)->rb_left;
+		else if (be32_to_cpu(new_vh->vol_id) < tmp_sv->vol_id)
+			p = &(*p)->rb_right;
+		else {
+			found = 1;
+			break;
+		}
+	}
+
+	if (found)
+		sv = tmp_sv;
+	else {
+		ubi_err("Orphaned volume in fastmap pool!");
+
+		return -EINVAL;
+	}
+
+	ubi_assert(be32_to_cpu(new_vh->vol_id) == sv->vol_id);
+
+	return update_vol(ubi, si, sv, new_vh, new_seb);
+}
+
+/**
+ * scan_pool - scans a pool for changed (no longer empty PEBs)
+ * @ubi: UBI device object
+ * @si: scan info object
+ * @pebs: an array of all PEB numbers in the to be scanned pool
+ * @pool_size: size of the pool (number of entries in @pebs)
+ * @max_sqnum2: pointer to the maximal sequence number
+ */
+static int scan_pool(struct ubi_device *ubi, struct ubi_scan_info *si,
+	int *pebs, int pool_size, unsigned long long *max_sqnum2)
+{
+	struct ubi_vid_hdr *vh;
+	struct ubi_ec_hdr *ech;
+	struct ubi_scan_leb *new_seb;
+	int i;
+	int pnum;
+	int err;
+	int ret = 0;
+
+	ech = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL);
+	if (!ech)
+		return -ENOMEM;
+
+	vh = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vh) {
+		kfree(ech);
+		return -ENOMEM;
+	}
+
+	/*
+	 * Now scan all PEBs in the pool to find changes which have been made
+	 * after the creation of the fastmap
+	 */
+	for (i = 0; i < pool_size; i++) {
+		pnum = be32_to_cpu(pebs[i]);
+
+		err = ubi_io_read_vid_hdr(ubi, pnum, vh, 0);
+
+		if (err == UBI_IO_FF)
+			continue;
+		else if (err == 0) {
+			err = ubi_io_read_ec_hdr(ubi, pnum, ech, 0);
+			if (err) {
+				ret = err;
+
+				goto out;
+			}
+
+			new_seb = kmem_cache_alloc(si->scan_leb_slab,
+				GFP_KERNEL);
+			if (!new_seb) {
+				ret = -ENOMEM;
+
+				goto out;
+			}
+
+			new_seb->ec = be64_to_cpu(ech->ec);
+			new_seb->pnum = pnum;
+			new_seb->lnum = be32_to_cpu(vh->lnum);
+			new_seb->sqnum = be64_to_cpu(vh->sqnum);
+			new_seb->copy_flag = vh->copy_flag;
+			new_seb->scrub = 0;
+
+			err = process_pool_seb(ubi, si, vh, new_seb);
+			if (err) {
+				ret = err;
+
+				goto out;
+			}
+
+			if (*max_sqnum2 < new_seb->sqnum)
+				*max_sqnum2 = new_seb->sqnum;
+		} else {
+			/* We are paranoid and fall back to scanning mode */
+			ubi_err("Checkpoint pool PEBs contains damaged PEBs!");
+			ret = err;
+
+			goto out;
+		}
+
+	}
+
+out:
+	ubi_free_vid_hdr(ubi, vh);
+	kfree(ech);
+
+	return ret;
+}
+
+/**
+ * ubi_scan_fastmap - creates ubi_scan_info from a fastmap.
+ * @ubi: UBI device object
+ * @fm_raw: the fastmap it self as byte array
+ * @fm_size: size of the fastmap in bytes
+ */
+struct ubi_scan_info *ubi_scan_fastmap(struct ubi_device *ubi, char *fm_raw,
+				       size_t fm_size)
+{
+	struct list_head used;
+	struct ubi_scan_volume *sv;
+	struct ubi_scan_leb *seb, *tmp_seb, *_tmp_seb;
+	struct ubi_scan_info *si;
+	int i, j;
+
+	size_t fm_pos = 0;
+	struct ubi_fm_sb *fmsb;
+	struct ubi_fm_hdr *fmhdr;
+	struct ubi_fm_scan_pool *fmpl;
+	struct ubi_fm_ec *fmec;
+	struct ubi_fm_volhdr *fmvhdr;
+	struct ubi_fm_eba *fm_eba;
+
+	unsigned long long max_sqnum2 = 0;
+
+	si = kzalloc(sizeof(struct ubi_scan_info), GFP_KERNEL);
+	if (!si)
+		return ERR_PTR(-ENOMEM);
+
+	INIT_LIST_HEAD(&used);
+	INIT_LIST_HEAD(&si->corr);
+	INIT_LIST_HEAD(&si->free);
+	INIT_LIST_HEAD(&si->erase);
+	INIT_LIST_HEAD(&si->alien);
+	si->volumes = RB_ROOT;
+	si->min_ec = UBI_MAX_ERASECOUNTER;
+
+	si->scan_leb_slab = kmem_cache_create("ubi_scan_leb_slab",
+					      sizeof(struct ubi_scan_leb),
+					      0, 0, NULL);
+	if (!si->scan_leb_slab)
+		goto fail;
+
+	fmsb = (struct ubi_fm_sb *)(fm_raw);
+	si->max_sqnum = fmsb->sqnum;
+	fm_pos += sizeof(struct ubi_fm_sb);
+	if (fm_pos >= fm_size)
+		goto fail;
+
+	fmhdr = (struct ubi_fm_hdr *)(fm_raw + fm_pos);
+	fm_pos += sizeof(*fmhdr);
+	if (fm_pos >= fm_size)
+		goto fail;
+
+	if (fmhdr->magic != UBI_FM_HDR_MAGIC)
+		goto fail;
+
+	fmpl = (struct ubi_fm_scan_pool *)(fm_raw + fm_pos);
+	fm_pos += sizeof(*fmpl);
+	if (fm_pos >= fm_size)
+		goto fail;
+	if (fmpl->magic != UBI_FM_POOL_MAGIC)
+		goto fail;
+
+	/* read EC values from free list */
+	for (i = 0; i < be32_to_cpu(fmhdr->nfree); i++) {
+		fmec = (struct ubi_fm_ec *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*fmec);
+		if (fm_pos >= fm_size)
+			goto fail;
+
+		add_seb(si, &si->free, be32_to_cpu(fmec->pnum),
+			be32_to_cpu(fmec->ec));
+	}
+
+	/* read EC values from used list */
+	for (i = 0; i < be32_to_cpu(fmhdr->nused); i++) {
+		fmec = (struct ubi_fm_ec *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*fmec);
+		if (fm_pos >= fm_size)
+			goto fail;
+
+		add_seb(si, &used, be32_to_cpu(fmec->pnum),
+			be32_to_cpu(fmec->ec));
+	}
+
+	si->mean_ec = div_u64(si->ec_sum, si->ec_count);
+
+	/* Iterate over all volumes and read their EBA table */
+	for (i = 0; i < be32_to_cpu(fmhdr->nvol); i++) {
+		fmvhdr = (struct ubi_fm_volhdr *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*fmvhdr);
+		if (fm_pos >= fm_size)
+			goto fail;
+
+		if (fmvhdr->magic != UBI_FM_VHDR_MAGIC)
+			goto fail;
+
+		sv = add_vol(si, be32_to_cpu(fmvhdr->vol_id),
+			be32_to_cpu(fmvhdr->used_ebs),
+			be32_to_cpu(fmvhdr->data_pad),
+			fmvhdr->vol_type, be32_to_cpu(fmvhdr->last_eb_bytes));
+
+		if (!sv)
+			goto fail;
+
+		si->vols_found++;
+		if (si->highest_vol_id < be32_to_cpu(fmvhdr->vol_id))
+			si->highest_vol_id = be32_to_cpu(fmvhdr->vol_id);
+
+		fm_eba = (struct ubi_fm_eba *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*fm_eba) + (sizeof(__be32) * be32_to_cpu(fm_eba->nused));
+		if (fm_pos >= fm_size)
+			goto fail;
+
+		if (fm_eba->magic != UBI_FM_EBA_MAGIC)
+			goto fail;
+
+		for (j = 0; j < be32_to_cpu(fm_eba->nused); j++) {
+
+			if ((int)be32_to_cpu(fm_eba->pnum[j]) < 0)
+				continue;
+
+			seb = NULL;
+			list_for_each_entry(tmp_seb, &used, u.list) {
+				if (tmp_seb->pnum == be32_to_cpu(fm_eba->pnum[j]))
+					seb = tmp_seb;
+			}
+
+			/* Corner case, this PEB must be in the pool */
+			if (!seb)
+				continue;
+
+			seb->lnum = j;
+			assign_seb_to_sv(si, seb, sv);
+
+			dbg_bld("Inserting pnum %i (leb %i) to vol %i",
+				seb->pnum, seb->lnum, sv->vol_id);
+		}
+	}
+
+	/*
+	 * The remainning PEB in the used list are not used.
+	 * They lived in the fastmap pool but got never used.
+	 */
+	list_for_each_entry_safe(tmp_seb, _tmp_seb, &used, u.list) {
+		list_del(&tmp_seb->u.list);
+		list_add_tail(&tmp_seb->u.list, &si->free);
+	}
+
+	if (scan_pool(ubi, si, fmpl->pebs, be32_to_cpu(fmpl->size),
+			&max_sqnum2) < 0)
+		goto fail;
+
+	if (max_sqnum2 > si->max_sqnum)
+		si->max_sqnum = max_sqnum2;
+
+	return si;
+
+fail:
+	ubi_scan_destroy_si(si);
+	return NULL;
+}
+
+/**
+ * ubi_read_fastmap - read the fastmap
+ * @ubi: UBI device object
+ * @cb_sb_pnum: PEB number of the fastmap super block
+ */
+struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi,
+					  int cb_sb_pnum)
+{
+	struct ubi_fm_sb *fmsb;
+	struct ubi_vid_hdr *vh;
+	int ret, i, nblocks;
+	char *fm_raw;
+	size_t fm_size;
+	__be32 data_crc;
+	unsigned long long sqnum = 0;
+	struct ubi_scan_info *si = NULL;
+
+	fmsb = kmalloc(sizeof(*fmsb), GFP_KERNEL);
+	if (!fmsb) {
+		si = ERR_PTR(-ENOMEM);
+
+		goto out;
+	}
+
+	ret = ubi_io_read(ubi, fmsb, cb_sb_pnum, ubi->leb_start, sizeof(*fmsb));
+	if (ret) {
+		ubi_err("Unable to read fastmap super block");
+		si = ERR_PTR(ret);
+		kfree(fmsb);
+
+		goto out;
+	}
+
+	if (fmsb->magic != UBI_FM_SB_MAGIC) {
+		ubi_err("Super block magic does not match");
+		si = ERR_PTR(-EINVAL);
+		kfree(fmsb);
+
+		goto out;
+	}
+
+	if (fmsb->version != UBI_FM_FMT_VERSION) {
+		ubi_err("Unknown fastmap format version!");
+		si = ERR_PTR(-EINVAL);
+		kfree(fmsb);
+
+		goto out;
+	}
+
+	nblocks = be32_to_cpu(fmsb->nblocks);
+
+	if (nblocks > UBI_FM_MAX_BLOCKS || nblocks < 1) {
+		ubi_err("Number of fastmap blocks is invalid");
+		si = ERR_PTR(-EINVAL);
+		kfree(fmsb);
+
+		goto out;
+	}
+
+	fm_size = ubi->leb_size * nblocks;
+	/* fm_raw will contain the whole fastmap */
+	fm_raw = vzalloc(fm_size);
+	if (!fm_raw) {
+		si = ERR_PTR(-ENOMEM);
+		kfree(fmsb);
+	}
+
+	vh = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vh) {
+		si = ERR_PTR(-ENOMEM);
+		kfree(fmsb);
+
+		goto free_raw;
+	}
+
+	for (i = 0; i < nblocks; i++) {
+		ret = ubi_io_read_vid_hdr(ubi, be32_to_cpu(fmsb->block_loc[i]),
+			vh, 0);
+		if (ret) {
+			ubi_err("Unable to read fastmap block# %i (PEB: %i)",
+				i, be32_to_cpu(fmsb->block_loc[i]));
+			si = ERR_PTR(ret);
+
+			goto free_vhdr;
+		}
+
+		if (i == 0) {
+			if (be32_to_cpu(vh->vol_id) != UBI_FM_SB_VOLUME_ID) {
+				si = ERR_PTR(-EINVAL);
+
+				goto free_vhdr;
+			}
+		} else {
+			if (be32_to_cpu(vh->vol_id) != UBI_FM_DATA_VOLUME_ID) {
+				goto free_vhdr;
+
+				si = ERR_PTR(-EINVAL);
+			}
+		}
+
+		if (sqnum < be64_to_cpu(vh->sqnum))
+			sqnum = be64_to_cpu(vh->sqnum);
+
+		ret = ubi_io_read(ubi, fm_raw + (ubi->leb_size * i),
+			be32_to_cpu(fmsb->block_loc[i]),
+			ubi->leb_start, ubi->leb_size);
+
+		if (ret) {
+			ubi_err("Unable to read fastmap block# %i (PEB: %i)",
+				i, be32_to_cpu(fmsb->block_loc[i]));
+			si = ERR_PTR(ret);
+
+			goto free_vhdr;
+		}
+	}
+
+	kfree(fmsb);
+
+	fmsb = (struct ubi_fm_sb *)fm_raw;
+	data_crc = crc32_be(UBI_CRC32_INIT, fm_raw + sizeof(*fmsb),
+		fm_size - sizeof(*fmsb));
+	if (data_crc != fmsb->data_crc) {
+		ubi_err("Checkpoint data CRC is invalid");
+		si = ERR_PTR(-EINVAL);
+
+		goto free_vhdr;
+	}
+
+	fmsb->sqnum = sqnum;
+
+	si = ubi_scan_fastmap(ubi, fm_raw, fm_size);
+	if (!si) {
+		si = ERR_PTR(-EINVAL);
+
+		goto free_vhdr;
+	}
+
+	/* Store the fastmap position into the ubi_device struct */
+	ubi->fm = kmalloc(sizeof(struct ubi_fastmap), GFP_KERNEL);
+	if (!ubi->fm) {
+		si = ERR_PTR(-ENOMEM);
+		ubi_scan_destroy_si(si);
+
+		goto free_vhdr;
+	}
+
+	ubi->fm->size = fm_size;
+	ubi->fm->used_blocks = nblocks;
+
+	for (i = 0; i < UBI_FM_MAX_BLOCKS; i++) {
+		if (i < nblocks) {
+			ubi->fm->peb[i] = be32_to_cpu(fmsb->block_loc[i]);
+			ubi->fm->ec[i] = be32_to_cpu(fmsb->block_ec[i]);
+		} else {
+			ubi->fm->peb[i] = -1;
+			ubi->fm->ec[i] = 0;
+		}
+	}
+
+free_vhdr:
+	ubi_free_vid_hdr(ubi, vh);
+free_raw:
+	vfree(fm_raw);
+out:
+	return si;
+}
+
+/**
+ * ubi_find_fastmap - searches the first UBI_FM_MAX_START PEBs for the
+ * fastmap super block.
+ * @ubi: UBI device object
+ */
+int ubi_find_fastmap(struct ubi_device *ubi)
+{
+	int i, ret;
+	int fm_sb = -ENOENT;
+	struct ubi_vid_hdr *vhdr;
+
+	vhdr = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vhdr)
+		return -ENOMEM;
+
+	for (i = 0; i < UBI_FM_MAX_START; i++) {
+		ret = ubi_io_read_vid_hdr(ubi, i, vhdr, 0);
+		/* ignore read errors */
+		if (ret)
+			continue;
+
+		if (be32_to_cpu(vhdr->vol_id) == UBI_FM_SB_VOLUME_ID) {
+			fm_sb = i;
+			break;
+		}
+	}
+
+	ubi_free_vid_hdr(ubi, vhdr);
+	return fm_sb;
+}
+
+/**
+ * ubi_write_fastmap - writes a fastmap
+ * @ubi: UBI device object
+ * @new_fm: the to be written checkppoint
+ */
+static int ubi_write_fastmap(struct ubi_device *ubi,
+				struct ubi_fastmap *new_fm)
+{
+	int ret;
+	size_t fm_pos = 0;
+	char *fm_raw;
+	int i, j;
+
+	struct ubi_fm_sb *fmsb;
+	struct ubi_fm_hdr *cph;
+	struct ubi_fm_scan_pool *cppl;
+	struct ubi_fm_ec *cec;
+	struct ubi_fm_volhdr *cvh;
+	struct ubi_fm_eba *ceba;
+
+	struct rb_node *node;
+	struct ubi_wl_entry *wl_e;
+	struct ubi_volume *vol;
+
+	struct ubi_vid_hdr *svhdr, *dvhdr;
+
+	int nfree, nused, nvol;
+
+	fm_raw = vzalloc(new_fm->size);
+	if (!fm_raw) {
+		ret = -ENOMEM;
+
+		goto out;
+	}
+
+	svhdr = new_fm_vhdr(ubi, UBI_FM_SB_VOLUME_ID);
+	if (!svhdr) {
+		ret = -ENOMEM;
+
+		goto out_vfree;
+	}
+
+	dvhdr = new_fm_vhdr(ubi, UBI_FM_DATA_VOLUME_ID);
+	if (!dvhdr) {
+		ret = -ENOMEM;
+
+		goto out_kfree;
+	}
+
+	spin_lock(&ubi->volumes_lock);
+	spin_lock(&ubi->wl_lock);
+
+	fmsb = (struct ubi_fm_sb *)fm_raw;
+	fm_pos += sizeof(*fmsb);
+	ubi_assert(fm_pos <= new_fm->size);
+
+	cph = (struct ubi_fm_hdr *)(fm_raw + fm_pos);
+	fm_pos += sizeof(*cph);
+	ubi_assert(fm_pos <= new_fm->size);
+
+	fmsb->magic = UBI_FM_SB_MAGIC;
+	fmsb->version = UBI_FM_FMT_VERSION;
+	fmsb->nblocks = cpu_to_be32(new_fm->used_blocks);
+	/* the max sqnum will be filled in while *reading* the fastmap */
+	fmsb->sqnum = 0;
+
+	cph->magic = UBI_FM_HDR_MAGIC;
+	nfree = 0;
+	nused = 0;
+	nvol = 0;
+
+	cppl = (struct ubi_fm_scan_pool *)(fm_raw + fm_pos);
+	fm_pos += sizeof(*cppl);
+	cppl->magic = UBI_FM_POOL_MAGIC;
+	cppl->size = cpu_to_be32(ubi->fm_pool.size);
+
+	for (i = 0; i < ubi->fm_pool.size; i++)
+		cppl->pebs[i] = cpu_to_be32(ubi->fm_pool.pebs[i]);
+
+	for (node = rb_first(&ubi->free); node; node = rb_next(node)) {
+		wl_e = rb_entry(node, struct ubi_wl_entry, u.rb);
+		cec = (struct ubi_fm_ec *)(fm_raw + fm_pos);
+
+		cec->pnum = cpu_to_be32(wl_e->pnum);
+		cec->ec = cpu_to_be32(wl_e->ec);
+
+		nfree++;
+		fm_pos += sizeof(*cec);
+		ubi_assert(fm_pos <= new_fm->size);
+	}
+	cph->nfree = cpu_to_be32(nfree);
+
+	for (node = rb_first(&ubi->used); node; node = rb_next(node)) {
+		wl_e = rb_entry(node, struct ubi_wl_entry, u.rb);
+		cec = (struct ubi_fm_ec *)(fm_raw + fm_pos);
+
+		cec->pnum = cpu_to_be32(wl_e->pnum);
+		cec->ec = cpu_to_be32(wl_e->ec);
+
+		nused++;
+		fm_pos += sizeof(*cec);
+		ubi_assert(fm_pos <= new_fm->size);
+	}
+	cph->nused = cpu_to_be32(nused);
+
+	for (i = 0; i < UBI_MAX_VOLUMES + UBI_INT_VOL_COUNT; i++) {
+		vol = ubi->volumes[i];
+
+		if (!vol)
+			continue;
+
+		nvol++;
+
+		cvh = (struct ubi_fm_volhdr *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*cvh);
+		ubi_assert(fm_pos <= new_fm->size);
+
+		cvh->magic = UBI_FM_VHDR_MAGIC;
+		cvh->vol_id = cpu_to_be32(vol->vol_id);
+		cvh->vol_type = vol->vol_type;
+		cvh->used_ebs = cpu_to_be32(vol->used_ebs);
+		cvh->data_pad = cpu_to_be32(vol->data_pad);
+		cvh->last_eb_bytes = cpu_to_be32(vol->last_eb_bytes);
+
+		ubi_assert(vol->vol_type == UBI_DYNAMIC_VOLUME ||
+			vol->vol_type == UBI_STATIC_VOLUME);
+
+		ceba = (struct ubi_fm_eba *)(fm_raw + fm_pos);
+		fm_pos += sizeof(*ceba) + (sizeof(__be32) * vol->used_ebs);
+		ubi_assert(fm_pos <= new_fm->size);
+
+		for (j = 0; j < vol->used_ebs; j++)
+			ceba->pnum[j] = cpu_to_be32(vol->eba_tbl[j]);
+
+		ceba->nused = cpu_to_be32(j);
+		ceba->magic = UBI_FM_EBA_MAGIC;
+	}
+	cph->nvol = cpu_to_be32(nvol);
+
+	svhdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
+	svhdr->lnum = 0;
+
+	spin_unlock(&ubi->wl_lock);
+	spin_unlock(&ubi->volumes_lock);
+
+	dbg_bld("Writing fastmap SB to PEB %i\n", new_fm->peb[0]);
+	ret = ubi_io_write_vid_hdr(ubi, new_fm->peb[0], svhdr);
+	if (ret) {
+		ubi_err("Unable to write vid_hdr to fastmap SB!\n");
+
+		goto out_kfree;
+	}
+
+	for (i = 0; i < UBI_FM_MAX_BLOCKS; i++) {
+		fmsb->block_loc[i] = cpu_to_be32(new_fm->peb[i]);
+		fmsb->block_ec[i] = cpu_to_be32(new_fm->ec[i]);
+	}
+
+	fmsb->data_crc = 0;
+	fmsb->data_crc = crc32_be(UBI_CRC32_INIT, fm_raw + sizeof(*fmsb),
+		new_fm->size - sizeof(*fmsb));
+
+	for (i = 1; i < new_fm->used_blocks; i++) {
+		dvhdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
+		dvhdr->lnum = cpu_to_be32(i);
+		dbg_bld("Writing fastmap data to PEB %i sqnum %llu\n",
+			new_fm->peb[i], be64_to_cpu(dvhdr->sqnum));
+		ret = ubi_io_write_vid_hdr(ubi, new_fm->peb[i], dvhdr);
+		if (ret) {
+			ubi_err("Unable to write vid_hdr to PEB %i!\n",
+				new_fm->peb[i]);
+
+			goto out_kfree;
+		}
+	}
+
+	for (i = 0; i < new_fm->used_blocks; i++) {
+		ret = ubi_io_write(ubi, fm_raw + (i * ubi->leb_size),
+			new_fm->peb[i], ubi->leb_start, ubi->leb_size);
+		if (ret) {
+			ubi_err("Unable to write fastmap to PEB %i!\n",
+				new_fm->peb[i]);
+
+			goto out_kfree;
+		}
+	}
+
+	ubi_assert(new_fm);
+	ubi->fm = new_fm;
+
+	dbg_bld("Checkpoint written!");
+
+out_kfree:
+	kfree(svhdr);
+out_vfree:
+	vfree(fm_raw);
+out:
+	return ret;
+}
+
+/**
+ * get_ec - returns the erase counter of a given PEB
+ * @ubi: UBI device object
+ * @pnum: PEB number
+ */
+static int get_ec(struct ubi_device *ubi, int pnum)
+{
+	struct ubi_wl_entry *e;
+
+	e = ubi->lookuptbl[pnum];
+
+	/* can this really happen? */
+	if (!e)
+		return ubi->mean_ec ?: 1;
+	else
+		return e->ec;
+}
+
+/**
+ * ubi_update_fastmap - will be called by UBI if a volume changes or
+ * a fastmap pool becomes full.
+ * @ubi: UBI device object
+ */
+int ubi_update_fastmap(struct ubi_device *ubi)
+{
+	int ret, i;
+	struct ubi_fastmap *new_fm;
+
+	if (ubi->ro_mode)
+		return 0;
+
+	new_fm = kmalloc(sizeof(*new_fm), GFP_KERNEL);
+	if (!new_fm)
+		return -ENOMEM;
+
+	ubi->old_fm = ubi->fm;
+	ubi->fm = NULL;
+
+	if (ubi->old_fm) {
+		spin_lock(&ubi->wl_lock);
+		new_fm->peb[0] = ubi_wl_get_fm_peb(ubi, UBI_FM_MAX_START);
+		spin_unlock(&ubi->wl_lock);
+		/* no fresh early PEB was found, reuse the old one */
+		if (new_fm->peb[0] < 0) {
+			struct ubi_ec_hdr *ec_hdr;
+
+			ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL);
+			if (!ec_hdr) {
+				kfree(new_fm);
+				return -ENOMEM;
+			}
+
+			/* we have to erase the block by hand */
+
+			ret = ubi_io_read_ec_hdr(ubi, ubi->old_fm->peb[0],
+				ec_hdr, 0);
+			if (ret) {
+				ubi_err("Unable to read EC header");
+
+				kfree(new_fm);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ret = ubi_io_sync_erase(ubi, ubi->old_fm->peb[0], 0);
+			if (ret < 0) {
+				ubi_err("Unable to erase old SB");
+
+				kfree(new_fm);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ec_hdr->ec += ret;
+			if (ret > UBI_MAX_ERASECOUNTER) {
+				ubi_err("Erase counter overflow!");
+				kfree(new_fm);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ret = ubi_io_write_ec_hdr(ubi, ubi->old_fm->peb[0],
+				ec_hdr);
+			kfree(ec_hdr);
+			if (ret) {
+				ubi_err("Unable to write new EC header");
+				kfree(new_fm);
+				return -EINVAL;
+			}
+
+			new_fm->peb[0] = ubi->old_fm->peb[0];
+			new_fm->ec[0] = ubi->old_fm->ec[0];
+		} else {
+			/* we've got a new early PEB, return the old one */
+			ubi_wl_put_fm_peb(ubi, ubi->old_fm->peb[0], 0);
+			new_fm->ec[0] = get_ec(ubi, new_fm->peb[0]);
+		}
+
+		/* return all other fastmap block to the wl system */
+		for (i = 1; i < UBI_FM_MAX_BLOCKS; i++) {
+			if (ubi->old_fm->peb[i] >= 0)
+				ubi_wl_put_fm_peb(ubi, ubi->old_fm->peb[i], 0);
+			else
+				break;
+		}
+	} else {
+		spin_lock(&ubi->wl_lock);
+		new_fm->peb[0] = ubi_wl_get_fm_peb(ubi, UBI_FM_MAX_START);
+		spin_unlock(&ubi->wl_lock);
+		if (new_fm->peb[0] < 0) {
+			ubi_err("Could not find an early PEB");
+			kfree(new_fm);
+			return -ENOSPC;
+		}
+		new_fm->ec[0] = get_ec(ubi, new_fm->peb[0]);
+	}
+
+	new_fm->size = sizeof(struct ubi_fm_hdr) + \
+			sizeof(struct ubi_fm_scan_pool) + \
+			(ubi->peb_count * sizeof(struct ubi_fm_ec)) + \
+			(sizeof(struct ubi_fm_eba) + \
+			(ubi->peb_count * sizeof(__be32))) + \
+			sizeof(struct ubi_fm_volhdr) * UBI_MAX_VOLUMES;
+	new_fm->size = roundup(new_fm->size, ubi->leb_size);
+
+	new_fm->used_blocks = new_fm->size / ubi->leb_size;
+
+	if (new_fm->used_blocks > UBI_FM_MAX_BLOCKS) {
+		ubi_err("Checkpoint too large");
+		kfree(new_fm);
+
+		return -ENOSPC;
+	}
+
+	/* give the wl subsystem a chance to produce some free blocks */
+	cond_resched();
+
+	for (i = 1; i < UBI_FM_MAX_BLOCKS; i++) {
+		if (i < new_fm->used_blocks) {
+			spin_lock(&ubi->wl_lock);
+			new_fm->peb[i] = ubi_wl_get_fm_peb(ubi, INT_MAX);
+			spin_unlock(&ubi->wl_lock);
+			if (new_fm->peb[i] < 0) {
+				ubi_err("Could not get any free erase block");
+
+				while (i--)
+					ubi_wl_put_fm_peb(ubi, new_fm->peb[i],
+						0);
+
+				kfree(new_fm);
+
+				return -ENOSPC;
+			}
+
+			new_fm->ec[i] = get_ec(ubi, new_fm->peb[i]);
+		} else {
+			new_fm->peb[i] = -1;
+			new_fm->ec[i] = 0;
+		}
+	}
+
+	kfree(ubi->old_fm);
+	ubi->old_fm = NULL;
+
+	return ubi_write_fastmap(ubi, new_fm);
+}
diff --git a/drivers/mtd/ubi/scan.c b/drivers/mtd/ubi/scan.c
index 69be65f..b4ab79f 100644
--- a/drivers/mtd/ubi/scan.c
+++ b/drivers/mtd/ubi/scan.c
@@ -1011,7 +1011,11 @@ static int process_eb(struct ubi_device *ubi, struct ubi_scan_info *si,
 	}
 
 	vol_id = be32_to_cpu(vidh->vol_id);
-	if (vol_id > UBI_MAX_VOLUMES && vol_id != UBI_LAYOUT_VOLUME_ID) {
+
+	if (vol_id > UBI_MAX_VOLUMES &&
+		vol_id != UBI_LAYOUT_VOLUME_ID &&
+		vol_id != UBI_FM_SB_VOLUME_ID &&
+		vol_id != UBI_FM_DATA_VOLUME_ID) {
 		int lnum = be32_to_cpu(vidh->lnum);
 
 		/* Unsupported internal volume */
diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index cf5cfaf..5ed03b5 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -624,11 +624,15 @@ int ubi_enumerate_volumes(struct notifier_block *nb);
 void ubi_do_get_device_info(struct ubi_device *ubi, struct ubi_device_info *di);
 void ubi_do_get_volume_info(struct ubi_device *ubi, struct ubi_volume *vol,
 			    struct ubi_volume_info *vi);
-
 /* scan.c */
 int ubi_compare_lebs(struct ubi_device *ubi, const struct ubi_scan_leb *seb,
 		      int pnum, const struct ubi_vid_hdr *vid_hdr);
 
+/* fastmap.c */
+int ubi_update_fastmap(struct ubi_device *ubi);
+struct ubi_scan_info *ubi_read_fastmap(struct ubi_device *ubi, int fm_sb_pnum);
+int ubi_find_fastmap(struct ubi_device *ubi);
+
 /*
  * ubi_rb_for_each_entry - walk an RB-tree.
  * @rb: a pointer to type 'struct rb_node' to use as a loop counter
-- 
1.7.6.5

[PATCH 7/7] [RFC] UBI: Wire up fastmap support

[Richard Weinberger]

This commit enables fastmap per default.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/Kconfig     |   26 +++++++++++++++
 drivers/mtd/ubi/build.c     |   76 ++++++++++++++++++++++++++++++++++++++++++-
 drivers/mtd/ubi/scan.c      |    5 ++-
 drivers/mtd/ubi/ubi-media.h |   13 ++------
 drivers/mtd/ubi/wl.c        |   32 +++++++++++++++++-
 5 files changed, 137 insertions(+), 15 deletions(-)

diff --git a/drivers/mtd/ubi/Kconfig b/drivers/mtd/ubi/Kconfig
index 4dcc752..fd09f10 100644
--- a/drivers/mtd/ubi/Kconfig
+++ b/drivers/mtd/ubi/Kconfig
@@ -42,6 +42,32 @@ config MTD_UBI_BEB_RESERVE
 	  eraseblocks (e.g. NOR flash), this value is ignored and nothing is
 	  reserved. Leave the default value if unsure.
 
+config MTD_UBI_FM_POOL_SIZE
+	int "Max number of PEBs in a fastmap pool"
+	range 10 1024
+	default 128
+	help
+	   This is the number PEBs which have to be scanned while attaching.
+	   A low value means that attaching will be faster but if the value
+	   is too small the fastmap has to be written too often.
+	   Every time the pool is full a new fastmap is written to the MTD.
+	   Choose wisely!
+
+config MTD_UBI_FM_MAX_SIZE
+	int "Maximal size of a fastmap in PEBs"
+	range 10 128
+	default 32
+	help
+	   Maximale size of a checkpoint in PEBs.
+
+config MTD_UBI_FM_SB_POS
+	int "Fastmap super block position"
+	range 4 128
+	default 64
+	help
+	   The fastmap super block will be placed within the first N PEBs.
+	   Is this value too large it takes longer to find the checkpoint.
+
 config MTD_UBI_GLUEBI
 	tristate "MTD devices emulation driver (gluebi)"
 	help
diff --git a/drivers/mtd/ubi/build.c b/drivers/mtd/ubi/build.c
index 0fde9fc..2399511 100644
--- a/drivers/mtd/ubi/build.c
+++ b/drivers/mtd/ubi/build.c
@@ -148,6 +148,16 @@ int ubi_volume_notify(struct ubi_device *ubi, struct ubi_volume *vol, int ntype)
 
 	ubi_do_get_device_info(ubi, &nt.di);
 	ubi_do_get_volume_info(ubi, vol, &nt.vi);
+
+	switch (ntype) {
+	case UBI_VOLUME_ADDED:
+	case UBI_VOLUME_REMOVED:
+	case UBI_VOLUME_RESIZED:
+	case UBI_VOLUME_RENAMED:
+		if (ubi_update_fastmap(ubi))
+			ubi_err("Unable to update fastmap!");
+	}
+
 	return blocking_notifier_call_chain(&ubi_notifiers, ntype, &nt);
 }
 
@@ -852,6 +862,59 @@ static int autoresize(struct ubi_device *ubi, int vol_id)
 	return 0;
 }
 
+static int attach_by_fastmap(struct ubi_device *ubi)
+{
+	int fm_start, err;
+	struct ubi_scan_info *si;
+
+	fm_start = ubi_find_fastmap(ubi);
+	if (fm_start < 0)
+		return -ENOENT;
+
+	si = ubi_read_fastmap(ubi, fm_start);
+	if (IS_ERR(si))
+		return PTR_ERR(si);
+
+	ubi->bad_peb_count = 0;
+	ubi->good_peb_count = ubi->peb_count;
+	ubi->corr_peb_count = 0;
+	ubi->max_ec = si->max_ec;
+	ubi->mean_ec = si->mean_ec;
+	ubi_msg("max. sequence number:       %llu", si->max_sqnum);
+
+	err = ubi_read_volume_table(ubi, si);
+	if (err) {
+		ubi_err("ubi_read_volume_table failed");
+		goto out_si;
+	}
+
+	err = ubi_wl_init_scan(ubi, si);
+	if (err) {
+		ubi_err("ubi_wl_init_scan failed!");
+		goto out_vtbl;
+	}
+
+	err = ubi_eba_init_scan(ubi, si);
+	if (err) {
+		ubi_err("ubi_eba_init_scan failed!");
+		goto out_wl;
+	}
+
+	ubi_msg("successfully attached via fastmapping!");
+	ubi_scan_destroy_si(si);
+	return 0;
+
+out_wl:
+	ubi_wl_close(ubi);
+out_vtbl:
+	free_internal_volumes(ubi);
+	vfree(ubi->vtbl);
+out_si:
+	ubi_scan_destroy_si(si);
+
+	return err;
+}
+
 /**
  * ubi_attach_mtd_dev - attach an MTD device.
  * @mtd: MTD device description object
@@ -931,6 +994,9 @@ int ubi_attach_mtd_dev(struct mtd_info *mtd, int ubi_num, int vid_hdr_offset)
 	ubi->vid_hdr_offset = vid_hdr_offset;
 	ubi->autoresize_vol_id = -1;
 
+	ubi->fm_pool.used = ubi->fm_pool.size = 0;
+	ubi->fm_pool.max_size = ARRAY_SIZE(ubi->fm_pool.pebs);
+
 	mutex_init(&ubi->buf_mutex);
 	mutex_init(&ubi->ckvol_mutex);
 	mutex_init(&ubi->device_mutex);
@@ -953,7 +1019,15 @@ int ubi_attach_mtd_dev(struct mtd_info *mtd, int ubi_num, int vid_hdr_offset)
 	if (err)
 		goto out_free;
 
-	err = attach_by_scanning(ubi);
+	err = attach_by_fastmap(ubi);
+	if (err) {
+		if (err != -ENOENT)
+			ubi_msg("falling back to attach by scanning mode!");
+
+		ubi->attached_by_scanning = true;
+		err = attach_by_scanning(ubi);
+	}
+
 	if (err) {
 		dbg_err("failed to attach by scanning, error %d", err);
 		goto out_debugging;
diff --git a/drivers/mtd/ubi/scan.c b/drivers/mtd/ubi/scan.c
index b4ab79f..2408a0d 100644
--- a/drivers/mtd/ubi/scan.c
+++ b/drivers/mtd/ubi/scan.c
@@ -1014,8 +1014,9 @@ static int process_eb(struct ubi_device *ubi, struct ubi_scan_info *si,
 
 	if (vol_id > UBI_MAX_VOLUMES &&
 		vol_id != UBI_LAYOUT_VOLUME_ID &&
-		vol_id != UBI_FM_SB_VOLUME_ID &&
-		vol_id != UBI_FM_DATA_VOLUME_ID) {
+		((vol_id != UBI_FM_SB_VOLUME_ID &&
+		vol_id != UBI_FM_DATA_VOLUME_ID) ||
+		ubi->attached_by_scanning == true)) {
 		int lnum = be32_to_cpu(vidh->lnum);
 
 		/* Unsupported internal volume */
diff --git a/drivers/mtd/ubi/ubi-media.h b/drivers/mtd/ubi/ubi-media.h
index a23196f..19ddbba 100644
--- a/drivers/mtd/ubi/ubi-media.h
+++ b/drivers/mtd/ubi/ubi-media.h
@@ -389,16 +389,9 @@ struct ubi_vtbl_record {
 #define UBI_FM_POOL_MAGIC	0x67AF4D08
 #define UBI_FM_EBA_MAGIC	0xf0c040a8
 
-/* Semi-sane default values - TBR */
-#ifndef UBI_FM_MAX_POOL_SIZE
-#define UBI_FM_MAX_POOL_SIZE	128
-#endif
-#ifndef UBI_FM_MAX_BLOCKS
-#define UBI_FM_MAX_BLOCKS	32
-#endif
-#ifndef UBI_FM_MAX_START
-#define UBI_FM_MAX_START	64
-#endif
+#define UBI_FM_MAX_START	CONFIG_MTD_UBI_FM_SB_POS
+#define UBI_FM_MAX_BLOCKS	CONFIG_MTD_UBI_FM_MAX_SIZE
+#define UBI_FM_MAX_POOL_SIZE	CONFIG_MTD_UBI_FM_POOL_SIZE
 
 /**
  * struct ubi_fm_sb - UBI fastmap super block
diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index a329358..c94a84a 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -393,7 +393,6 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
 }
 
 /**
- * ubi_wl_get_peb - get a physical eraseblock.
  * find_early_wl_entry - find wear-leveling entry with a low pnum.
  * @root: the RB-tree where to look for
  * @max_pnum: highest possible pnum
@@ -451,12 +450,13 @@ out:
 }
 
 /**
+ * __ubi_wl_get_peb - get a physical eraseblock.
  * @ubi: UBI device description object
  *
  * This function returns a physical eraseblock in case of success and a
  * negative error code in case of failure. Might sleep.
  */
-int ubi_wl_get_peb(struct ubi_device *ubi)
+static int __ubi_wl_get_peb(struct ubi_device *ubi)
 {
 	int err;
 	struct ubi_wl_entry *e, *first, *last;
@@ -507,6 +507,34 @@ retry:
 	return e->pnum;
 }
 
+/* ubi_wl_get_peb - works exaclty like __ubi_wl_get_peb but keeps track of
+ * the fastmap pool.
+ */
+int ubi_wl_get_peb(struct ubi_device *ubi)
+{
+	struct ubi_fm_pool *pool = &ubi->fm_pool;
+
+	/* pool contains no free blocks, create a new one
+	 * and write a fastmap */
+	if (pool->used == pool->size || !pool->size) {
+		for (pool->size = 0; pool->size < pool->max_size;
+				pool->size++) {
+			pool->pebs[pool->size] = __ubi_wl_get_peb(ubi);
+			if (pool->pebs[pool->size] < 0)
+				break;
+		}
+
+		pool->used = 0;
+		ubi_update_fastmap(ubi);
+	}
+
+	/* we got not a single free PEB */
+	if (!pool->size)
+		return -1;
+
+	return pool->pebs[pool->used++];
+}
+
 /**
  * prot_queue_del - remove a physical eraseblock from the protection queue.
  * @ubi: UBI device description object
-- 
1.7.6.5

[PATCH 7/7] [RFC] UBI: Wire up fastmap support

[Richard Weinberger]

This commit enables fastmap per default.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/Kconfig     |   26 +++++++++++++++
 drivers/mtd/ubi/build.c     |   76 ++++++++++++++++++++++++++++++++++++++++++-
 drivers/mtd/ubi/scan.c      |    5 ++-
 drivers/mtd/ubi/ubi-media.h |   13 ++------
 drivers/mtd/ubi/wl.c        |   32 +++++++++++++++++-
 5 files changed, 137 insertions(+), 15 deletions(-)

diff --git a/drivers/mtd/ubi/Kconfig b/drivers/mtd/ubi/Kconfig
index 4dcc752..fd09f10 100644
--- a/drivers/mtd/ubi/Kconfig
+++ b/drivers/mtd/ubi/Kconfig
@@ -42,6 +42,32 @@ config MTD_UBI_BEB_RESERVE
 	  eraseblocks (e.g. NOR flash), this value is ignored and nothing is
 	  reserved. Leave the default value if unsure.
 
+config MTD_UBI_FM_POOL_SIZE
+	int "Max number of PEBs in a fastmap pool"
+	range 10 1024
+	default 128
+	help
+	   This is the number PEBs which have to be scanned while attaching.
+	   A low value means that attaching will be faster but if the value
+	   is too small the fastmap has to be written too often.
+	   Every time the pool is full a new fastmap is written to the MTD.
+	   Choose wisely!
+
+config MTD_UBI_FM_MAX_SIZE
+	int "Maximal size of a fastmap in PEBs"
+	range 10 128
+	default 32
+	help
+	   Maximale size of a checkpoint in PEBs.
+
+config MTD_UBI_FM_SB_POS
+	int "Fastmap super block position"
+	range 4 128
+	default 64
+	help
+	   The fastmap super block will be placed within the first N PEBs.
+	   Is this value too large it takes longer to find the checkpoint.
+
 config MTD_UBI_GLUEBI
 	tristate "MTD devices emulation driver (gluebi)"
 	help
diff --git a/drivers/mtd/ubi/build.c b/drivers/mtd/ubi/build.c
index 0fde9fc..2399511 100644
--- a/drivers/mtd/ubi/build.c
+++ b/drivers/mtd/ubi/build.c
@@ -148,6 +148,16 @@ int ubi_volume_notify(struct ubi_device *ubi, struct ubi_volume *vol, int ntype)
 
 	ubi_do_get_device_info(ubi, &nt.di);
 	ubi_do_get_volume_info(ubi, vol, &nt.vi);
+
+	switch (ntype) {
+	case UBI_VOLUME_ADDED:
+	case UBI_VOLUME_REMOVED:
+	case UBI_VOLUME_RESIZED:
+	case UBI_VOLUME_RENAMED:
+		if (ubi_update_fastmap(ubi))
+			ubi_err("Unable to update fastmap!");
+	}
+
 	return blocking_notifier_call_chain(&ubi_notifiers, ntype, &nt);
 }
 
@@ -852,6 +862,59 @@ static int autoresize(struct ubi_device *ubi, int vol_id)
 	return 0;
 }
 
+static int attach_by_fastmap(struct ubi_device *ubi)
+{
+	int fm_start, err;
+	struct ubi_scan_info *si;
+
+	fm_start = ubi_find_fastmap(ubi);
+	if (fm_start < 0)
+		return -ENOENT;
+
+	si = ubi_read_fastmap(ubi, fm_start);
+	if (IS_ERR(si))
+		return PTR_ERR(si);
+
+	ubi->bad_peb_count = 0;
+	ubi->good_peb_count = ubi->peb_count;
+	ubi->corr_peb_count = 0;
+	ubi->max_ec = si->max_ec;
+	ubi->mean_ec = si->mean_ec;
+	ubi_msg("max. sequence number:       %llu", si->max_sqnum);
+
+	err = ubi_read_volume_table(ubi, si);
+	if (err) {
+		ubi_err("ubi_read_volume_table failed");
+		goto out_si;
+	}
+
+	err = ubi_wl_init_scan(ubi, si);
+	if (err) {
+		ubi_err("ubi_wl_init_scan failed!");
+		goto out_vtbl;
+	}
+
+	err = ubi_eba_init_scan(ubi, si);
+	if (err) {
+		ubi_err("ubi_eba_init_scan failed!");
+		goto out_wl;
+	}
+
+	ubi_msg("successfully attached via fastmapping!");
+	ubi_scan_destroy_si(si);
+	return 0;
+
+out_wl:
+	ubi_wl_close(ubi);
+out_vtbl:
+	free_internal_volumes(ubi);
+	vfree(ubi->vtbl);
+out_si:
+	ubi_scan_destroy_si(si);
+
+	return err;
+}
+
 /**
  * ubi_attach_mtd_dev - attach an MTD device.
  * @mtd: MTD device description object
@@ -931,6 +994,9 @@ int ubi_attach_mtd_dev(struct mtd_info *mtd, int ubi_num, int vid_hdr_offset)
 	ubi->vid_hdr_offset = vid_hdr_offset;
 	ubi->autoresize_vol_id = -1;
 
+	ubi->fm_pool.used = ubi->fm_pool.size = 0;
+	ubi->fm_pool.max_size = ARRAY_SIZE(ubi->fm_pool.pebs);
+
 	mutex_init(&ubi->buf_mutex);
 	mutex_init(&ubi->ckvol_mutex);
 	mutex_init(&ubi->device_mutex);
@@ -953,7 +1019,15 @@ int ubi_attach_mtd_dev(struct mtd_info *mtd, int ubi_num, int vid_hdr_offset)
 	if (err)
 		goto out_free;
 
-	err = attach_by_scanning(ubi);
+	err = attach_by_fastmap(ubi);
+	if (err) {
+		if (err != -ENOENT)
+			ubi_msg("falling back to attach by scanning mode!");
+
+		ubi->attached_by_scanning = true;
+		err = attach_by_scanning(ubi);
+	}
+
 	if (err) {
 		dbg_err("failed to attach by scanning, error %d", err);
 		goto out_debugging;
diff --git a/drivers/mtd/ubi/scan.c b/drivers/mtd/ubi/scan.c
index b4ab79f..2408a0d 100644
--- a/drivers/mtd/ubi/scan.c
+++ b/drivers/mtd/ubi/scan.c
@@ -1014,8 +1014,9 @@ static int process_eb(struct ubi_device *ubi, struct ubi_scan_info *si,
 
 	if (vol_id > UBI_MAX_VOLUMES &&
 		vol_id != UBI_LAYOUT_VOLUME_ID &&
-		vol_id != UBI_FM_SB_VOLUME_ID &&
-		vol_id != UBI_FM_DATA_VOLUME_ID) {
+		((vol_id != UBI_FM_SB_VOLUME_ID &&
+		vol_id != UBI_FM_DATA_VOLUME_ID) ||
+		ubi->attached_by_scanning == true)) {
 		int lnum = be32_to_cpu(vidh->lnum);
 
 		/* Unsupported internal volume */
diff --git a/drivers/mtd/ubi/ubi-media.h b/drivers/mtd/ubi/ubi-media.h
index a23196f..19ddbba 100644
--- a/drivers/mtd/ubi/ubi-media.h
+++ b/drivers/mtd/ubi/ubi-media.h
@@ -389,16 +389,9 @@ struct ubi_vtbl_record {
 #define UBI_FM_POOL_MAGIC	0x67AF4D08
 #define UBI_FM_EBA_MAGIC	0xf0c040a8
 
-/* Semi-sane default values - TBR */
-#ifndef UBI_FM_MAX_POOL_SIZE
-#define UBI_FM_MAX_POOL_SIZE	128
-#endif
-#ifndef UBI_FM_MAX_BLOCKS
-#define UBI_FM_MAX_BLOCKS	32
-#endif
-#ifndef UBI_FM_MAX_START
-#define UBI_FM_MAX_START	64
-#endif
+#define UBI_FM_MAX_START	CONFIG_MTD_UBI_FM_SB_POS
+#define UBI_FM_MAX_BLOCKS	CONFIG_MTD_UBI_FM_MAX_SIZE
+#define UBI_FM_MAX_POOL_SIZE	CONFIG_MTD_UBI_FM_POOL_SIZE
 
 /**
  * struct ubi_fm_sb - UBI fastmap super block
diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index a329358..c94a84a 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -393,7 +393,6 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
 }
 
 /**
- * ubi_wl_get_peb - get a physical eraseblock.
  * find_early_wl_entry - find wear-leveling entry with a low pnum.
  * @root: the RB-tree where to look for
  * @max_pnum: highest possible pnum
@@ -451,12 +450,13 @@ out:
 }
 
 /**
+ * __ubi_wl_get_peb - get a physical eraseblock.
  * @ubi: UBI device description object
  *
  * This function returns a physical eraseblock in case of success and a
  * negative error code in case of failure. Might sleep.
  */
-int ubi_wl_get_peb(struct ubi_device *ubi)
+static int __ubi_wl_get_peb(struct ubi_device *ubi)
 {
 	int err;
 	struct ubi_wl_entry *e, *first, *last;
@@ -507,6 +507,34 @@ retry:
 	return e->pnum;
 }
 
+/* ubi_wl_get_peb - works exaclty like __ubi_wl_get_peb but keeps track of
+ * the fastmap pool.
+ */
+int ubi_wl_get_peb(struct ubi_device *ubi)
+{
+	struct ubi_fm_pool *pool = &ubi->fm_pool;
+
+	/* pool contains no free blocks, create a new one
+	 * and write a fastmap */
+	if (pool->used == pool->size || !pool->size) {
+		for (pool->size = 0; pool->size < pool->max_size;
+				pool->size++) {
+			pool->pebs[pool->size] = __ubi_wl_get_peb(ubi);
+			if (pool->pebs[pool->size] < 0)
+				break;
+		}
+
+		pool->used = 0;
+		ubi_update_fastmap(ubi);
+	}
+
+	/* we got not a single free PEB */
+	if (!pool->size)
+		return -1;
+
+	return pool->pebs[pool->used++];
+}
+
 /**
  * prot_queue_del - remove a physical eraseblock from the protection queue.
  * @ubi: UBI device description object
-- 
1.7.6.5

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

[Subodh Nijsure]

Hello Richard,

On 05/15/2012 10:11 AM, Richard Weinberger wrote:
> v1: https://lwn.net/Articles/481612/
> v2: https://lwn.net/Articles/496586/
> v3: Didn't release it to linux-mtd
Will kernel that has older UBI drivers be able to mount and update the 
UBI volumes that have been created with checkpointing feature?

Say I have bootrom that has 3.0.X kernel that has no knowledge of UBI 
checkpointing, and my flash /dev/mtd2 has UBI volume with checkpointing 
enabled. Will this bootrom be able to attach /dev/mtd2 and mount  UBI 
volume and read/write files on it?

-Subodh
> Changes since v1:
>          - renamed it to UBIVIS (at least in Kconfig)
>          - UBIVIS parameters are now configurable via Kconfig
>          - several bugs have been fixed (design and implementation bugs)
>          - added lots of comments to make the review process easier
>          - made checkpatch.pl happy
>
> Changes since v2:
>          - minor bugs have been fixed
>          - renamed it to UBI fastmap (as Artem requested)
>
> Changes since v3:
>          - changed the on-flash layout (added padding fields, turned the
>            EBA storage into an array)
>          - fixed some corner cases (the protection queue needed some extra work)
> 	- removed the data type hint logic
> 	- rebased to Artems mtd tree
>
> [PATCH 1/7] [RFC] UBI: Export next_sqnum()
> [PATCH 2/7] [RFC] UBI: Export compare_lebs()
> [PATCH 3/7] [RFC] UBI: Add fastmap on-flash layout
> [PATCH 4/7] [RFC] UBI: Add fastmap structs to ubi_device
> [PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware
> [PATCH 6/7] [RFC] UBI: Implement fastmapping support
> [PATCH 7/7] [RFC] UBI: Wire up fastmap support
>
> git://git.kernel.org/pub/scm/linux/kernel/git/rw/ubi2.git ubi2/v4
>
> Some benchmark numbers:
>
> 4GiB NAND
> Erase block size: 1MiB
> Page size: 4096
> Total PEBs: 4081*
>
> Attach method   Time**          #scanned PEBs
> ---------------------------------------------
> scanning        0m4.568s        4081
> fastmap         0m0.486s        3
>
>
> 2GiB NAND
> Erase block size: 1MiB
> Page size: 4096
> Total PEBs: 2062*
>
> Attach method   Time            #scanned PEBs
> ---------------------------------------------
> scanning        0m2.440s        2062
> fastmap         0m0.439s        3
>
>
> 1GiB NAND
> Erase block size: 1MiB
> Page size: 4096
> Total PEBs: 1038*
>
> Attach method   Time            #scanned PEBs
> ---------------------------------------------
> scanning        0m1.351s        1038
> fastmap         0m0.422s        4
>
>
> 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.
> 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.
> With the current default settings this would be 192 PEBs.
> So, attaching via fastmap has a complexity of O(1).
> I think we can reduce UBI_FM_MAX_BLOCKS and UBI_FM_MAX_POOL_SIZE to a much
> smaller value. On most real NAND chips the whole fastmap fits into one PEB.
>
> TODO:
>          - Artem is fully happy with the current on-flash layout,
>            maybe I can merge the erase counters into the EBA table
>          - Get a full review :)
>
> Thanks,
> //richard
>
> *) Didn't use the full NAND for UBI because Kernel, U-Boot, DT needed also
> some space.
>
> **) Time was taken by: "time ubiattach -m 5"
>
> ______________________________________________________
> Linux MTD discussion mailing list
> http://lists.infradead.org/mailman/listinfo/linux-mtd/

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

[Subodh Nijsure]

Hello Richard,

On 05/15/2012 10:11 AM, Richard Weinberger wrote:
> v1: https://lwn.net/Articles/481612/
> v2: https://lwn.net/Articles/496586/
> v3: Didn't release it to linux-mtd
Will kernel that has older UBI drivers be able to mount and update the 
UBI volumes that have been created with checkpointing feature?

Say I have bootrom that has 3.0.X kernel that has no knowledge of UBI 
checkpointing, and my flash /dev/mtd2 has UBI volume with checkpointing 
enabled. Will this bootrom be able to attach /dev/mtd2 and mount  UBI 
volume and read/write files on it?

-Subodh
> Changes since v1:
>          - renamed it to UBIVIS (at least in Kconfig)
>          - UBIVIS parameters are now configurable via Kconfig
>          - several bugs have been fixed (design and implementation bugs)
>          - added lots of comments to make the review process easier
>          - made checkpatch.pl happy
>
> Changes since v2:
>          - minor bugs have been fixed
>          - renamed it to UBI fastmap (as Artem requested)
>
> Changes since v3:
>          - changed the on-flash layout (added padding fields, turned the
>            EBA storage into an array)
>          - fixed some corner cases (the protection queue needed some extra work)
> 	- removed the data type hint logic
> 	- rebased to Artems mtd tree
>
> [PATCH 1/7] [RFC] UBI: Export next_sqnum()
> [PATCH 2/7] [RFC] UBI: Export compare_lebs()
> [PATCH 3/7] [RFC] UBI: Add fastmap on-flash layout
> [PATCH 4/7] [RFC] UBI: Add fastmap structs to ubi_device
> [PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware
> [PATCH 6/7] [RFC] UBI: Implement fastmapping support
> [PATCH 7/7] [RFC] UBI: Wire up fastmap support
>
> git://git.kernel.org/pub/scm/linux/kernel/git/rw/ubi2.git ubi2/v4
>
> Some benchmark numbers:
>
> 4GiB NAND
> Erase block size: 1MiB
> Page size: 4096
> Total PEBs: 4081*
>
> Attach method   Time**          #scanned PEBs
> ---------------------------------------------
> scanning        0m4.568s        4081
> fastmap         0m0.486s        3
>
>
> 2GiB NAND
> Erase block size: 1MiB
> Page size: 4096
> Total PEBs: 2062*
>
> Attach method   Time            #scanned PEBs
> ---------------------------------------------
> scanning        0m2.440s        2062
> fastmap         0m0.439s        3
>
>
> 1GiB NAND
> Erase block size: 1MiB
> Page size: 4096
> Total PEBs: 1038*
>
> Attach method   Time            #scanned PEBs
> ---------------------------------------------
> scanning        0m1.351s        1038
> fastmap         0m0.422s        4
>
>
> 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.
> 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.
> With the current default settings this would be 192 PEBs.
> So, attaching via fastmap has a complexity of O(1).
> I think we can reduce UBI_FM_MAX_BLOCKS and UBI_FM_MAX_POOL_SIZE to a much
> smaller value. On most real NAND chips the whole fastmap fits into one PEB.
>
> TODO:
>          - Artem is fully happy with the current on-flash layout,
>            maybe I can merge the erase counters into the EBA table
>          - Get a full review :)
>
> Thanks,
> //richard
>
> *) Didn't use the full NAND for UBI because Kernel, U-Boot, DT needed also
> some space.
>
> **) Time was taken by: "time ubiattach -m 5"
>
> ______________________________________________________
> Linux MTD discussion mailing list
> http://lists.infradead.org/mailman/listinfo/linux-mtd/

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

[Richard Weinberger]

Hi Subodh,

Am 15.05.2012 19:48, schrieb Subodh Nijsure:
> Hello Richard,
>
> On 05/15/2012 10:11 AM, Richard Weinberger wrote:
>> v1: https://lwn.net/Articles/481612/
>> v2: https://lwn.net/Articles/496586/
>> v3: Didn't release it to linux-mtd
> Will kernel that has older UBI drivers be able to mount and update the
> UBI volumes that have been created with checkpointing feature?

Of course!

> Say I have bootrom that has 3.0.X kernel that has no knowledge of UBI
> checkpointing, and my flash /dev/mtd2 has UBI volume with checkpointing
> enabled. Will this bootrom be able to attach /dev/mtd2 and mount UBI
> volume and read/write files on it?

Sure!
Your bootrom will scan the UBI volume and detect two unknown internal
volumes with compat=delete in their volume headers.
So, it will delete the two fastmap volumes and continue scanning.
It can alter the volume and so on.

Thanks,
//richard

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

[Richard Weinberger]

Hi Subodh,

Am 15.05.2012 19:48, schrieb Subodh Nijsure:
> Hello Richard,
>
> On 05/15/2012 10:11 AM, Richard Weinberger wrote:
>> v1: https://lwn.net/Articles/481612/
>> v2: https://lwn.net/Articles/496586/
>> v3: Didn't release it to linux-mtd
> Will kernel that has older UBI drivers be able to mount and update the
> UBI volumes that have been created with checkpointing feature?

Of course!

> Say I have bootrom that has 3.0.X kernel that has no knowledge of UBI
> checkpointing, and my flash /dev/mtd2 has UBI volume with checkpointing
> enabled. Will this bootrom be able to attach /dev/mtd2 and mount UBI
> volume and read/write files on it?

Sure!
Your bootrom will scan the UBI volume and detect two unknown internal
volumes with compat=delete in their volume headers.
So, it will delete the two fastmap volumes and continue scanning.
It can alter the volume and so on.

Thanks,
//richard

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

[Richard Weinberger]

Am 15.05.2012 19:11, schrieb Richard Weinberger:
> TODO:
>          - Artem is fully happy with the current on-flash layout,
>            maybe I can merge the erase counters into the EBA table

Whoops!
Artem is *not* fully happy...

Sorry,
//richard

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

[Richard Weinberger]

Am 15.05.2012 19:11, schrieb Richard Weinberger:
> TODO:
>          - Artem is fully happy with the current on-flash layout,
>            maybe I can merge the erase counters into the EBA table

Whoops!
Artem is *not* fully happy...

Sorry,
//richard

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

[Shmulik Ladkani]

Hi Richard,

Thanks for this important work.

On Tue, 15 May 2012 19:11:04 +0200 Richard Weinberger <richard@nod.at> wrote:
> TODO:
>         - Artem is fully happy with the current on-flash layout,
>           maybe I can merge the erase counters into the EBA table
>         - Get a full review :)

I'd be glad to take a deep look of the code.

Hopefully I'll get into it in the following days.

Regards,
Shmulik

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

[Shmulik Ladkani]

Hi Richard,

Thanks for this important work.

On Tue, 15 May 2012 19:11:04 +0200 Richard Weinberger <richard@nod.at> wrote:
> TODO:
>         - Artem is fully happy with the current on-flash layout,
>           maybe I can merge the erase counters into the EBA table
>         - Get a full review :)

I'd be glad to take a deep look of the code.

Hopefully I'll get into it in the following days.

Regards,
Shmulik

Fastmap - please, review and test

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 747 bytes --]

On Tue, 2012-05-15 at 22:46 +0300, Shmulik Ladkani wrote:
> On Tue, 15 May 2012 19:11:04 +0200 Richard Weinberger <richard@nod.at> wrote:
> > TODO:
> >         - Artem is fully happy with the current on-flash layout,
> >           maybe I can merge the erase counters into the EBA table
> >         - Get a full review :)
> 
> I'd be glad to take a deep look of the code.
> 
> Hopefully I'll get into it in the following days.

Thanks Shmulik - I appreciate any help as much as Richard. I am busy and
my job now has nothing to do with MTD/UBI/UBIFS, and I have limited time
for review.

There were many people who wanted faster UBI, and I'd ask them to
participate now - review, test, etc.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Fastmap - please, review and test

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 747 bytes --]

On Tue, 2012-05-15 at 22:46 +0300, Shmulik Ladkani wrote:
> On Tue, 15 May 2012 19:11:04 +0200 Richard Weinberger <richard@nod.at> wrote:
> > TODO:
> >         - Artem is fully happy with the current on-flash layout,
> >           maybe I can merge the erase counters into the EBA table
> >         - Get a full review :)
> 
> I'd be glad to take a deep look of the code.
> 
> Hopefully I'll get into it in the following days.

Thanks Shmulik - I appreciate any help as much as Richard. I am busy and
my job now has nothing to do with MTD/UBI/UBIFS, and I have limited time
for review.

There were many people who wanted faster UBI, and I'd ask them to
participate now - review, test, etc.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: Fastmap - please, review and test

[Richard Weinberger]

On 16.05.2012 08:54, Artem Bityutskiy wrote:
> On Tue, 2012-05-15 at 22:46 +0300, Shmulik Ladkani wrote:
>> On Tue, 15 May 2012 19:11:04 +0200 Richard Weinberger<richard@nod.at>  wrote:
>>> TODO:
>>>          - Artem is fully happy with the current on-flash layout,
>>>            maybe I can merge the erase counters into the EBA table
>>>          - Get a full review :)
>>
>> I'd be glad to take a deep look of the code.
>>
>> Hopefully I'll get into it in the following days.
>
> Thanks Shmulik - I appreciate any help as much as Richard. I am busy and
> my job now has nothing to do with MTD/UBI/UBIFS, and I have limited time
> for review.
>
> There were many people who wanted faster UBI, and I'd ask them to
> participate now - review, test, etc.
>

Before you shoot me, an hour ago I found an issue with static volumes 
that are not LEB aligned.
Looks like I'm calculating the volume length wrong.
I'll send as soon as possible a fix!

Thanks,
//richard

Re: Fastmap - please, review and test

[Richard Weinberger]

On 16.05.2012 08:54, Artem Bityutskiy wrote:
> On Tue, 2012-05-15 at 22:46 +0300, Shmulik Ladkani wrote:
>> On Tue, 15 May 2012 19:11:04 +0200 Richard Weinberger<richard@nod.at>  wrote:
>>> TODO:
>>>          - Artem is fully happy with the current on-flash layout,
>>>            maybe I can merge the erase counters into the EBA table
>>>          - Get a full review :)
>>
>> I'd be glad to take a deep look of the code.
>>
>> Hopefully I'll get into it in the following days.
>
> Thanks Shmulik - I appreciate any help as much as Richard. I am busy and
> my job now has nothing to do with MTD/UBI/UBIFS, and I have limited time
> for review.
>
> There were many people who wanted faster UBI, and I'd ask them to
> participate now - review, test, etc.
>

Before you shoot me, an hour ago I found an issue with static volumes 
that are not LEB aligned.
Looks like I'm calculating the volume length wrong.
I'll send as soon as possible a fix!

Thanks,
//richard

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

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1331 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1331 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 201 bytes --]

On Wed, 2012-05-16 at 12:38 +0300, Artem Bityutskiy wrote:
> O(N) would be: N -> inf, UBI_FM_MAX_BLOCKS -> C, where C is a constant.

O(1) of course, sorry.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 201 bytes --]

On Wed, 2012-05-16 at 12:38 +0300, Artem Bityutskiy wrote:
> O(N) would be: N -> inf, UBI_FM_MAX_BLOCKS -> C, where C is a constant.

O(1) of course, sorry.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Richard Weinberger]

On 16.05.2012 11:38, Artem Bityutskiy wrote:
  >> 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.

No, UBI_FM_MAX_BLOCKS does *not* depend on the MTD partition size.
When N -> inf, UBI_FM_MAX_BLOCKS is still a constant.
--> O(1)

> 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.

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.

Thanks,
//richard

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

[Richard Weinberger]

On 16.05.2012 11:38, Artem Bityutskiy wrote:
  >> 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.

No, UBI_FM_MAX_BLOCKS does *not* depend on the MTD partition size.
When N -> inf, UBI_FM_MAX_BLOCKS is still a constant.
--> O(1)

> 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.

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.

Thanks,
//richard

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

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1581 bytes --]

On Wed, 2012-05-16 at 12:50 +0200, Richard Weinberger wrote:
> On 16.05.2012 11:38, Artem Bityutskiy wrote:
>   >> 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.
> 
> No, UBI_FM_MAX_BLOCKS does *not* depend on the MTD partition size.
> When N -> inf, UBI_FM_MAX_BLOCKS is still a constant.
> --> O(1)

This cannot be true, you cannot fit information about infinite amount of
erase counters to a constant number of PEBs.

> 
> > 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.
> 
> 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.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1581 bytes --]

On Wed, 2012-05-16 at 12:50 +0200, Richard Weinberger wrote:
> On 16.05.2012 11:38, Artem Bityutskiy wrote:
>   >> 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.
> 
> No, UBI_FM_MAX_BLOCKS does *not* depend on the MTD partition size.
> When N -> inf, UBI_FM_MAX_BLOCKS is still a constant.
> --> O(1)

This cannot be true, you cannot fit information about infinite amount of
erase counters to a constant number of PEBs.

> 
> > 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.
> 
> 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.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1071 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 1071 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

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

[Richard Weinberger]

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

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

[Richard Weinberger]

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

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

[Richard Weinberger]

This is a bug-fix release. v4 handled static volumes wrong.
v6 will address everything that Artem pointed out.

v1: https://lwn.net/Articles/481612/
v2: https://lwn.net/Articles/496586/
v3: Didn't release it to linux-mtd
v4: http://article.gmane.org/gmane.linux.kernel/1297626

Changes since v1:
       - renamed it to UBIVIS (at least in Kconfig)
       - UBIVIS parameters are now configurable via Kconfig
       - several bugs have been fixed (design and implementation bugs)
       - added lots of comments to make the review process easier
       - made checkpatch.pl happy

Changes since v2:
       - minor bugs have been fixed
       - renamed it to UBI fastmap (as Artem requested)

Changes since v3:
       - changed the on-flash layout (added padding fields, turned the
         EBA storage into an array)
       - fixed some corner cases (the protection queue needed some extra work)
       - removed the data type hint logic
       - rebased to Artems mtd tree

Changes since v4:
       - fixed static volume handling (used_ebs and last_data_bytes contained
         bad values in some cases)
	
git://git.kernel.org/pub/scm/linux/kernel/git/rw/ubi2.git ubi2/v5

[PATCH 1/7] [RFC] UBI: Export next_sqnum()
[PATCH 2/7] [RFC] UBI: Export compare_lebs()
[PATCH 3/7] [RFC] UBI: Add fastmap on-flash layout
[PATCH 4/7] [RFC] UBI: Add fastmap structs to ubi_device
[PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware
[PATCH 6/7] [RFC] UBI: Implement fastmapping support
[PATCH 7/7] [RFC] UBI: Wire up fastmap support

Thanks,
//richard

[PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware

[Richard Weinberger]

Integrates fastmapping into the wl subsystem.
Fastmapping deals with PEBs, it has to tell the wl subsystem
which PEBs are currently used and must not touched by the wl thread.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/ubi.h |    3 +
 drivers/mtd/ubi/wl.c  |  141 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 144 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 6c89971..cf5cfaf 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -586,6 +586,9 @@ int ubi_wl_scrub_peb(struct ubi_device *ubi, int pnum);
 int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si);
 void ubi_wl_close(struct ubi_device *ubi);
 int ubi_thread(void *u);
+int ubi_wl_get_fm_peb(struct ubi_device *ubi, int max_pnum);
+int ubi_wl_put_fm_peb(struct ubi_device *ubi, int pnum, int torture);
+int ubi_is_fm_block(struct ubi_device *ubi, int pnum);
 
 /* io.c */
 int ubi_io_read(const struct ubi_device *ubi, void *buf, int pnum, int offset,
diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 64ce993..a329358 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -169,6 +169,25 @@ static int paranoid_check_in_pq(const struct ubi_device *ubi,
 #endif
 
 /**
+ *  ubi_ubi_is_fm_block - returns 1 if a PEB is currently used in a fastmap.
+ *  @ubi: UBI device description object
+ *  @pnum: the to be checked PEB
+ */
+int ubi_is_fm_block(struct ubi_device *ubi, int pnum)
+{
+	int i;
+
+	if (!ubi->fm)
+		return 0;
+
+	for (i = 0; i < ubi->fm->used_blocks; i++)
+		if (ubi->fm->peb[i] == pnum)
+			return 1;
+
+	return 0;
+}
+
+/**
  * wl_tree_add - add a wear-leveling entry to a WL RB-tree.
  * @e: the wear-leveling entry to add
  * @root: the root of the tree
@@ -375,6 +394,63 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
 
 /**
  * ubi_wl_get_peb - get a physical eraseblock.
+ * find_early_wl_entry - find wear-leveling entry with a low pnum.
+ * @root: the RB-tree where to look for
+ * @max_pnum: highest possible pnum
+ *
+ * This function looks for a wear leveling entry containing a eb which
+ * is in front of the memory.
+ */
+static struct ubi_wl_entry *find_early_wl_entry(struct rb_root *root,
+						int max_pnum)
+{
+	struct rb_node *p;
+	struct ubi_wl_entry *e, *victim = NULL;
+
+	ubi_rb_for_each_entry(p, e, root, u.rb) {
+		if (e->pnum < max_pnum) {
+			victim = e;
+			max_pnum = e->pnum;
+		}
+	}
+
+	return victim;
+}
+
+/**
+ * ubi_wl_get_fm_peb - find a physical erase block with a given maximal number.
+ * @ubi: UBI device description object
+ * @max_pnum: the highest acceptable erase block number
+ *
+ * The function returns a physical erase block with a given maximal number
+ * and removes it from the wl subsystem.
+ * Must be called with wl_lock held!
+ */
+int ubi_wl_get_fm_peb(struct ubi_device *ubi, int max_pnum)
+{
+	int ret = -ENOSPC;
+	struct ubi_wl_entry *e;
+
+	if (!ubi->free.rb_node) {
+		ubi_err("no free eraseblocks");
+
+		goto out;
+	}
+
+	e = find_early_wl_entry(&ubi->free, max_pnum);
+	if (!e)
+		goto out;
+
+	ret = e->pnum;
+
+	/* remove it from the free list,
+	 * the wl subsystem does no longer know this erase block */
+	rb_erase(&e->u.rb, &ubi->free);
+out:
+	return ret;
+}
+
+/**
  * @ubi: UBI device description object
  *
  * This function returns a physical eraseblock in case of success and a
@@ -596,6 +672,9 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 {
 	struct ubi_work *wl_wrk;
 
+	ubi_assert(e);
+	ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 	dbg_wl("schedule erasure of PEB %d, EC %d, torture %d",
 	       e->pnum, e->ec, torture);
 
@@ -612,6 +691,56 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 }
 
 /**
+ * ubi_wl_put_fm_peb - returns a PEB used in a fastmap to the wear-leveling 
+ * sub-system.
+ *
+ * see: ubi_wl_put_peb()
+ */
+int ubi_wl_put_fm_peb(struct ubi_device *ubi, int pnum, int torture)
+{
+	int i, err = 0;
+	struct ubi_wl_entry *e;
+
+	dbg_wl("PEB %d", pnum);
+	ubi_assert(pnum >= 0);
+	ubi_assert(pnum < ubi->peb_count);
+
+	spin_lock(&ubi->wl_lock);
+	e = ubi->lookuptbl[pnum];
+
+	/* This can happen if we recovered from a fastmap the very
+	 * frist time and writing now a new one. In this case the wl system
+	 * has never seen any PEB used by the original fastmap.
+	 */
+	if (!e) {
+		ubi_assert(ubi->old_fm);
+		e = kmem_cache_alloc(ubi_wl_entry_slab, GFP_ATOMIC);
+		if (!e) {
+			spin_unlock(&ubi->wl_lock);
+			return -ENOMEM;
+		}
+
+		e->pnum = pnum;
+		e->ec = 0;
+		/* use the ec value from the fastmap */
+		for (i = 0; i < UBI_FM_MAX_BLOCKS; i++) {
+			if (pnum == ubi->old_fm->peb[i]) {
+				e->ec = ubi->old_fm->ec[i];
+				break;
+			}
+		}
+		ubi_assert(e->ec);
+		ubi->lookuptbl[pnum] = e;
+	}
+
+	spin_unlock(&ubi->wl_lock);
+
+	err = schedule_erase(ubi, e, torture);
+
+	return err;
+}
+
+/**
  * wear_leveling_worker - wear-leveling worker function.
  * @ubi: UBI device description object
  * @wrk: the work object
@@ -988,6 +1117,8 @@ static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk,
 
 	dbg_wl("erase PEB %d EC %d", pnum, e->ec);
 
+	ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 	err = sync_erase(ubi, e, wl_wrk->torture);
 	if (!err) {
 		/* Fine, we've erased it successfully */
@@ -1422,6 +1553,9 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 
 		e->pnum = seb->pnum;
 		e->ec = seb->ec;
+
+		ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 		ubi->lookuptbl[e->pnum] = e;
 		if (schedule_erase(ubi, e, 0)) {
 			kmem_cache_free(ubi_wl_entry_slab, e);
@@ -1439,7 +1573,10 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 		e->pnum = seb->pnum;
 		e->ec = seb->ec;
 		ubi_assert(e->ec >= 0);
+		ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 		wl_tree_add(e, &ubi->free);
+
 		ubi->lookuptbl[e->pnum] = e;
 	}
 
@@ -1454,6 +1591,10 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 			e->pnum = seb->pnum;
 			e->ec = seb->ec;
 			ubi->lookuptbl[e->pnum] = e;
+
+			if (ubi_is_fm_block(ubi, seb->pnum))
+				continue;
+
 			if (!seb->scrub) {
 				dbg_wl("add PEB %d EC %d to the used tree",
 				       e->pnum, e->ec);
-- 
1.7.6.5

[PATCH 5/7] [RFC] UBI: Make wl subsystem fastmap aware

[Richard Weinberger]

Integrates fastmapping into the wl subsystem.
Fastmapping deals with PEBs, it has to tell the wl subsystem
which PEBs are currently used and must not touched by the wl thread.

Signed-off-by: Richard Weinberger <richard@nod.at>
---
 drivers/mtd/ubi/ubi.h |    3 +
 drivers/mtd/ubi/wl.c  |  141 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 144 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 6c89971..cf5cfaf 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -586,6 +586,9 @@ int ubi_wl_scrub_peb(struct ubi_device *ubi, int pnum);
 int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si);
 void ubi_wl_close(struct ubi_device *ubi);
 int ubi_thread(void *u);
+int ubi_wl_get_fm_peb(struct ubi_device *ubi, int max_pnum);
+int ubi_wl_put_fm_peb(struct ubi_device *ubi, int pnum, int torture);
+int ubi_is_fm_block(struct ubi_device *ubi, int pnum);
 
 /* io.c */
 int ubi_io_read(const struct ubi_device *ubi, void *buf, int pnum, int offset,
diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 64ce993..a329358 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -169,6 +169,25 @@ static int paranoid_check_in_pq(const struct ubi_device *ubi,
 #endif
 
 /**
+ *  ubi_ubi_is_fm_block - returns 1 if a PEB is currently used in a fastmap.
+ *  @ubi: UBI device description object
+ *  @pnum: the to be checked PEB
+ */
+int ubi_is_fm_block(struct ubi_device *ubi, int pnum)
+{
+	int i;
+
+	if (!ubi->fm)
+		return 0;
+
+	for (i = 0; i < ubi->fm->used_blocks; i++)
+		if (ubi->fm->peb[i] == pnum)
+			return 1;
+
+	return 0;
+}
+
+/**
  * wl_tree_add - add a wear-leveling entry to a WL RB-tree.
  * @e: the wear-leveling entry to add
  * @root: the root of the tree
@@ -375,6 +394,63 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
 
 /**
  * ubi_wl_get_peb - get a physical eraseblock.
+ * find_early_wl_entry - find wear-leveling entry with a low pnum.
+ * @root: the RB-tree where to look for
+ * @max_pnum: highest possible pnum
+ *
+ * This function looks for a wear leveling entry containing a eb which
+ * is in front of the memory.
+ */
+static struct ubi_wl_entry *find_early_wl_entry(struct rb_root *root,
+						int max_pnum)
+{
+	struct rb_node *p;
+	struct ubi_wl_entry *e, *victim = NULL;
+
+	ubi_rb_for_each_entry(p, e, root, u.rb) {
+		if (e->pnum < max_pnum) {
+			victim = e;
+			max_pnum = e->pnum;
+		}
+	}
+
+	return victim;
+}
+
+/**
+ * ubi_wl_get_fm_peb - find a physical erase block with a given maximal number.
+ * @ubi: UBI device description object
+ * @max_pnum: the highest acceptable erase block number
+ *
+ * The function returns a physical erase block with a given maximal number
+ * and removes it from the wl subsystem.
+ * Must be called with wl_lock held!
+ */
+int ubi_wl_get_fm_peb(struct ubi_device *ubi, int max_pnum)
+{
+	int ret = -ENOSPC;
+	struct ubi_wl_entry *e;
+
+	if (!ubi->free.rb_node) {
+		ubi_err("no free eraseblocks");
+
+		goto out;
+	}
+
+	e = find_early_wl_entry(&ubi->free, max_pnum);
+	if (!e)
+		goto out;
+
+	ret = e->pnum;
+
+	/* remove it from the free list,
+	 * the wl subsystem does no longer know this erase block */
+	rb_erase(&e->u.rb, &ubi->free);
+out:
+	return ret;
+}
+
+/**
  * @ubi: UBI device description object
  *
  * This function returns a physical eraseblock in case of success and a
@@ -596,6 +672,9 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 {
 	struct ubi_work *wl_wrk;
 
+	ubi_assert(e);
+	ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 	dbg_wl("schedule erasure of PEB %d, EC %d, torture %d",
 	       e->pnum, e->ec, torture);
 
@@ -612,6 +691,56 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 }
 
 /**
+ * ubi_wl_put_fm_peb - returns a PEB used in a fastmap to the wear-leveling 
+ * sub-system.
+ *
+ * see: ubi_wl_put_peb()
+ */
+int ubi_wl_put_fm_peb(struct ubi_device *ubi, int pnum, int torture)
+{
+	int i, err = 0;
+	struct ubi_wl_entry *e;
+
+	dbg_wl("PEB %d", pnum);
+	ubi_assert(pnum >= 0);
+	ubi_assert(pnum < ubi->peb_count);
+
+	spin_lock(&ubi->wl_lock);
+	e = ubi->lookuptbl[pnum];
+
+	/* This can happen if we recovered from a fastmap the very
+	 * frist time and writing now a new one. In this case the wl system
+	 * has never seen any PEB used by the original fastmap.
+	 */
+	if (!e) {
+		ubi_assert(ubi->old_fm);
+		e = kmem_cache_alloc(ubi_wl_entry_slab, GFP_ATOMIC);
+		if (!e) {
+			spin_unlock(&ubi->wl_lock);
+			return -ENOMEM;
+		}
+
+		e->pnum = pnum;
+		e->ec = 0;
+		/* use the ec value from the fastmap */
+		for (i = 0; i < UBI_FM_MAX_BLOCKS; i++) {
+			if (pnum == ubi->old_fm->peb[i]) {
+				e->ec = ubi->old_fm->ec[i];
+				break;
+			}
+		}
+		ubi_assert(e->ec);
+		ubi->lookuptbl[pnum] = e;
+	}
+
+	spin_unlock(&ubi->wl_lock);
+
+	err = schedule_erase(ubi, e, torture);
+
+	return err;
+}
+
+/**
  * wear_leveling_worker - wear-leveling worker function.
  * @ubi: UBI device description object
  * @wrk: the work object
@@ -988,6 +1117,8 @@ static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk,
 
 	dbg_wl("erase PEB %d EC %d", pnum, e->ec);
 
+	ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 	err = sync_erase(ubi, e, wl_wrk->torture);
 	if (!err) {
 		/* Fine, we've erased it successfully */
@@ -1422,6 +1553,9 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 
 		e->pnum = seb->pnum;
 		e->ec = seb->ec;
+
+		ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 		ubi->lookuptbl[e->pnum] = e;
 		if (schedule_erase(ubi, e, 0)) {
 			kmem_cache_free(ubi_wl_entry_slab, e);
@@ -1439,7 +1573,10 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 		e->pnum = seb->pnum;
 		e->ec = seb->ec;
 		ubi_assert(e->ec >= 0);
+		ubi_assert(!ubi_is_fm_block(ubi, e->pnum));
+
 		wl_tree_add(e, &ubi->free);
+
 		ubi->lookuptbl[e->pnum] = e;
 	}
 
@@ -1454,6 +1591,10 @@ int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 			e->pnum = seb->pnum;
 			e->ec = seb->ec;
 			ubi->lookuptbl[e->pnum] = e;
+
+			if (ubi_is_fm_block(ubi, seb->pnum))
+				continue;
+
 			if (!seb->scrub) {
 				dbg_wl("add PEB %d EC %d to the used tree",
 				       e->pnum, e->ec);
-- 
1.7.6.5