[RFC][PATCH 0/7] UBI checkpointing support

[RFC][PATCH 0/7] UBI checkpointing support

[Richard Weinberger]

The following patch set implements checkpointing support for
UBI. Checkpointing is an optional feature which stores the physical to
logical eraseblock relations in a checkpointing superblock to reduce
the initialization time of UBI. The current init time of UBI is
proportional to the number of physical erase blocks on the FLASH
device. With checkpointing enabled the scan time is limited to a fixed
number of blocks.

Checkpointing does not affect any of the existing UBI robustness
features and in fact the checkpointing code falls back into scanning
mode when the checkpoint superblock(s) are corrupted.

The checkpoints consist of two elements:

1) A primary checkpoint block, which contains merily a pointer to the
   erase block(s) which hold the real checkpointing data.

   This primary block is guaranteed to be held within the first N
   eraseblocks of a device. N is momentarily set to 16, but it might
   be necessary to make this configurable in some way.

2) The secondary checkpoint blocks, which contain the real
   checkpointing data (physical to logical eraseblock relations,
   erase counts, sequence numbers ...)

   Aside of that the checkpointing data contains a list of blocks
   which belong to the active working pool. The active working pool is
   a fixed number of blocks for shortterm, longterm and unknown
   storage time, which can be modified before the next checkpoint set
   is written to FLASH. These blocks need to be scanned in the
   conventional UBI scan mode.

   The reason for these pool blocks is to reduce the checkpoint
   updates to the necessary minimum to avoid accelerated device
   wearout in scenarios where data changes rapidly. The checkpoint
   data is updated whenever a working pool runs out of blocks.

   The number of pool blocks can be defined with a config option at
   the moment, but this could also be done at runtime via sysfs. In
   case of a change the checkpointing data would be reconstructed.

So the checkpoint scan consists of the following steps:

   1) Find the primary checkpoint block by scanning the start of the
      device.

   2) Read the real checkpoint data and construct the UBI device info
      structures.

   3) Scan the pool blocks.

All these operations scan a limited number of erase blocks which makes
the UBI init O(1) and independent of the device size.

The checkpoint functionality is fully compatible with existing UBI
deployments. If no checkpoint blocks can be found then the device is
scanned and the checkpoint blocks are created from the scanned
information.

Aside of review and testing it needs to be decided, whether the number
of pool blocks should be deduced from the device size (number of
physical eraseblocks) or made configurable at compile or runtime.

Thanks to the folks at CELF who sponsored this work!

[RFC][PATCH 1/7] MTD: UBI: Add checkpoint on-chip layout
[RFC][PATCH 2/7] MTD: UBI: Add checkpoint struct to ubi_device
[RFC][PATCH 3/7] MTD: UBI: Export next_sqnum()
[RFC][PATCH 4/7] MTD: UBI: Make wl subsystem checkpoint aware
[RFC][PATCH 5/7] MTD: UBI: Make process_eb() checkpoint aware
[RFC][PATCH 6/7] MTD: UBI: Implement checkpointing support
[RFC][PATCH 7/7] MTD: UBI: wire up checkpointing

[RFC][PATCH 1/7] MTD: UBI: Add checkpoint on-chip layout

[Richard Weinberger]

Specify the on-chip checkpoint layout.
The checkpoint consists of two major parts.
A super block (identified via UBI_CP_SB_VOLUME_ID) and
zero or more data blocks (identified via UBI_CP_DATA_VOLUME_ID).
Data blocks are only used if whole checkpoint information does not fit
into the super block.

Currently UBI_CP_MAX_START, UBI_CP_MAX_BLOCKS and UBI_CP_MAX_POOL_SIZE
are hard-coded.
In future this values may be configurable via Kconfig or sysfs.
All three checkpointing pools have the same size for now, this my also change.
An automatic calibration would be also nice to have.

Signed-off-by: Richard Weinberger <rw@linutronix.de>
---
 drivers/mtd/ubi/ubi-media.h |   81 +++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 81 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/ubi-media.h b/drivers/mtd/ubi/ubi-media.h
index 6fb8ec2..45f2b7b 100644
--- a/drivers/mtd/ubi/ubi-media.h
+++ b/drivers/mtd/ubi/ubi-media.h
@@ -375,4 +375,85 @@ struct ubi_vtbl_record {
 	__be32  crc;
 } __packed;
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+#define UBI_CP_SB_VOLUME_ID	(UBI_LAYOUT_VOLUME_ID + 1)
+#define UBI_CP_DATA_VOLUME_ID	(UBI_CP_SB_VOLUME_ID + 1)
+
+/* Checkoint format version */
+#define UBI_CP_FMT_VERSION	1
+
+#define UBI_CP_MAX_START	64
+#define UBI_CP_MAX_BLOCKS	32
+#define UBI_CP_MAX_POOL_SIZE	128
+#define UBI_CP_SB_MAGIC		0x7B11D69F
+#define UBI_CP_HDR_MAGIC	0xD4B82EF7
+#define UBI_CP_VHDR_MAGIC	0xFA370ED1
+#define UBI_CP_LPOOL_MAGIC	0x67AF4D08
+#define UBI_CP_SPOOL_MAGIC	0x67AF4D09
+#define UBI_CP_UPOOL_MAGIC	0x67AF4D0A
+
+struct ubi_cp_sb {
+	__be32 magic;
+	__u8 version;
+	__be32 data_crc;
+	__be32 nblocks;
+	__be32 block_loc[UBI_CP_MAX_BLOCKS];
+	__be32 block_ec[UBI_CP_MAX_BLOCKS];
+	__be64 sqnum;
+} __packed;
+
+/* first entry in the checkpoint (cp) data set */
+struct ubi_cp_hdr {
+	__be32 magic;
+	__be32 nfree;
+	__be32 nused;
+	__be32 nvol;
+} __packed;
+
+/* struct ubi_cp_hdr is followed by exactly three struct ub_cp_pool_* records 
+ * long, short and unknown pool */
+
+struct ubi_cp_long_pool {
+	__be32 magic;
+	__be32 size;
+	__be32 pebs[UBI_CP_MAX_POOL_SIZE];
+} __packed;
+
+struct ubi_cp_short_pool {
+	__be32 magic;
+	__be32 size;
+	__be32 pebs[UBI_CP_MAX_POOL_SIZE];
+} __packed;
+
+struct ubi_cp_unk_pool {
+	__be32 magic;
+	__be32 size;
+	__be32 pebs[UBI_CP_MAX_POOL_SIZE];
+} __packed;
+
+/* struct ub_cp_pool is followed by nfree+nused struct ubi_cp_ec records */
+
+/* erase counter per peb */
+struct ubi_cp_ec {
+	__be32 pnum;
+	__be32 ec;
+} __packed;
+
+/* identifies the start of a eba table */
+struct ubi_cp_volhdr {
+	__be32 magic;
+	__be32 vol_id;
+	__u8 vol_type;
+	__be32 data_pad;
+	__be32 used_ebs;
+	__be32 last_eb_bytes;
+} __packed;
+
+/* struct ubi_cp_volhdr is followed by nused struct ubi_cp_eba records */
+
+struct ubi_cp_eba {
+	__be32 lnum;
+	__be32 pnum;
+} __packed;
+#endif /* CONFIG_MTD_UBI_CHECKPOINT */
 #endif /* !__UBI_MEDIA_H__ */
-- 
1.7.7

[RFC][PATCH 2/7] MTD: UBI: Add checkpoint struct to ubi_device

[Richard Weinberger]

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

struct ubi_cp_pool describes a checkpoint pool.
All PEBs within this pool have to be rescanned after reading the checkpoint.
The pools are needed to handle the three types of PEBs which can be obtained
from the wl subsystem.
Longterm, shortterm and unknown.

Signed-off-by: Richard Weinberger <rw@linutronix.de>
---
 drivers/mtd/ubi/ubi.h |   23 ++++++++++++++++++++++-
 1 files changed, 22 insertions(+), 1 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index d51d75d..4fe3638 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -196,6 +196,22 @@ struct ubi_rename_entry {
 
 struct ubi_volume_desc;
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+struct ubi_checkpoint {
+	int peb[UBI_CP_MAX_BLOCKS];
+	unsigned int ec[UBI_CP_MAX_BLOCKS];
+	size_t size;
+	int used_blocks;
+};
+
+struct ubi_cp_pool {
+	int pebs[UBI_CP_MAX_POOL_SIZE];
+	int used;
+	int size;
+	int max_size;
+};
+#endif
+
 /**
  * struct ubi_volume - UBI volume description data structure.
  * @dev: device object to make use of the the Linux device model
@@ -425,7 +441,12 @@ struct ubi_device {
 	spinlock_t ltree_lock;
 	struct rb_root ltree;
 	struct mutex alc_mutex;
-
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+	struct ubi_checkpoint *cp;
+	struct ubi_cp_pool long_pool;
+	struct ubi_cp_pool short_pool;
+	struct ubi_cp_pool unk_pool;
+#endif
 	/* Wear-leveling sub-system's stuff */
 	struct rb_root used;
 	struct rb_root erroneous;
-- 
1.7.7

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

[Richard Weinberger]

The checkpointing subsystem needs to read the next sequence nummber
directly.

Signed-off-by: Richard Weinberger <rw@linutronix.de>
---
 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 cd26da8..4dae50c 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;
@@ -634,7 +634,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);
@@ -695,7 +695,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;
 }
@@ -750,7 +750,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);
@@ -815,7 +815,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;
 }
@@ -868,7 +868,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);
@@ -936,7 +936,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;
 }
@@ -1096,7 +1096,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 4fe3638..b4dca54 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -557,6 +557,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, int dtype);
-- 
1.7.7

[RFC][PATCH 4/7] MTD: UBI: Make wl subsystem checkpoint aware

[Richard Weinberger]

Integrates checkpointing into the wl subsystem.
Checkpointing 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 <rw@linutronix.de>
---
 drivers/mtd/ubi/ubi.h |    5 +
 drivers/mtd/ubi/wl.c  |  208 ++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 211 insertions(+), 2 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index b4dca54..4e8e8d2 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -567,6 +567,11 @@ 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_cp_peb(struct ubi_device *ubi, int max_pnum);
+int ubi_wl_put_cp_peb(struct ubi_device *ubi, int pnum, int torture);
+#define is_cp_block(__ubi__, __e__) __is_cp_block(__ubi__, __e__->pnum)
+int __is_cp_block(struct ubi_device *ubi, int pnum);
+void ubi_flush_prot_queue(struct ubi_device *ubi);
 
 /* 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 0696e36..b3884fa 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -175,6 +175,32 @@ static int paranoid_check_in_pq(const struct ubi_device *ubi,
 #define paranoid_check_in_pq(ubi, e) 0
 #endif
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+/**
+ *  __is_cp_block - returns 1 if a PEB is currently used for checkpointing
+ *  @ubi: UBI device description object
+ *  @pnum: The to be checked PEB
+ */
+int __is_cp_block(struct ubi_device *ubi, int pnum)
+{
+	int i;
+
+	if (!ubi->cp)
+		return 0;
+
+	for (i = 0; i < ubi->cp->used_blocks; i++)
+		if (ubi->cp->peb[i] == pnum)
+			return 1;
+
+	return 0;
+}
+#else
+int __is_cp_block(struct ubi_device *ubi, int pnum)
+{
+	return 0;
+}
+#endif
+
 /**
  * wl_tree_add - add a wear-leveling entry to a WL RB-tree.
  * @e: the wear-leveling entry to add
@@ -379,15 +405,74 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int max)
 	return e;
 }
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
 /**
- * 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_cp_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_cp_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;
+}
+#endif
+
+/**
+ * __ubi_wl_get_peb - get a physical eraseblock.
  * @ubi: UBI device description object
  * @dtype: type of data which will be stored in this physical eraseblock
  *
  * 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, int dtype)
+static int __ubi_wl_get_peb(struct ubi_device *ubi, int dtype)
 {
 	int err, medium_ec;
 	struct ubi_wl_entry *e, *first, *last;
@@ -473,6 +558,48 @@ retry:
 	return e->pnum;
 }
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+/* ubi_wl_get_peb - works exaclty like __ubi_wl_get_peb but keeps track of
+ * all checkpointing pools.
+ */
+int ubi_wl_get_peb(struct ubi_device *ubi, int dtype)
+{
+	struct ubi_cp_pool *pool;
+
+	if (dtype == UBI_LONGTERM)
+		pool = &ubi->long_pool;
+	else if (dtype == UBI_SHORTTERM)
+		pool = &ubi->short_pool;
+	else if (dtype == UBI_UNKNOWN)
+		pool = &ubi->unk_pool;
+	else
+		BUG();
+
+	/* pool contains no free blocks, create a new one and write a checkoint */
+	if (pool->used == pool->size) {
+		for (pool->size = 0; pool->size < pool->max_size; pool->size++) {
+			pool->pebs[pool->size] = __ubi_wl_get_peb(ubi, dtype);
+			if (pool->pebs[pool->size] < 0)
+				break;
+		}
+
+		pool->used = 0;
+		ubi_update_checkpoint(ubi);
+	}
+
+	/* we got not a single free PEB */
+	if (!pool->size)
+		return -1;
+
+	return pool->pebs[pool->used++];
+}
+#else
+int ubi_wl_get_peb(struct ubi_device *ubi, int dtype)
+{
+	return __ubi_wl_get_peb(ubi, dtype);
+}
+#endif
+
 /**
  * prot_queue_del - remove a physical eraseblock from the protection queue.
  * @ubi: UBI device description object
@@ -603,6 +730,21 @@ repeat:
 }
 
 /**
+ * ubi_flush_prot_queue - flushes the protection queue
+ * @ubi: UBI device description object
+ *
+ * This function flushes the protection queue such that checkpointing
+ * gets aware of them.
+ */
+void ubi_flush_prot_queue(struct ubi_device *ubi)
+{
+	int i;
+
+	for (i = 0; i < UBI_PROT_QUEUE_LEN; i++)
+		serve_prot_queue(ubi);
+}
+
+/**
  * schedule_ubi_work - schedule a work.
  * @ubi: UBI device description object
  * @wrk: the work to schedule
@@ -638,6 +780,9 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 {
 	struct ubi_work *wl_wrk;
 
+	ubi_assert(e);
+	ubi_assert(!is_cp_block(ubi, e));
+
 	dbg_wl("schedule erasure of PEB %d, EC %d, torture %d",
 	       e->pnum, e->ec, torture);
 
@@ -653,6 +798,53 @@ static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
 	return 0;
 }
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+/**
+ * ubi_wl_put_cp_peb - return a CP PEB to the wear-leveling sub-system
+ *
+ * see: ubi_wl_put_peb()
+ */
+int ubi_wl_put_cp_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 checkpoint 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 checkpoint.
+	 */
+	if (!e) {
+		e = kmem_cache_alloc(ubi_wl_entry_slab, GFP_ATOMIC);
+		if (!e) {
+			spin_unlock(&ubi->wl_lock);
+			return -ENOMEM;
+		}
+
+		e->pnum = pnum;
+		/* use the ec value from the checkpoint */
+		for (i = 0; i < UBI_CP_MAX_BLOCKS; i++) {
+			if (pnum == ubi->cp->peb[i]) {
+				e->ec = ubi->cp->ec[i];
+				break;
+			}
+		}
+	}
+
+	spin_unlock(&ubi->wl_lock);
+
+	err = schedule_erase(ubi, e, torture);
+
+	return err;
+}
+#endif
+
 /**
  * wear_leveling_worker - wear-leveling worker function.
  * @ubi: UBI device description object
@@ -1030,6 +1222,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(!is_cp_block(ubi, e));
+
 	err = sync_erase(ubi, e, wl_wrk->torture);
 	if (!err) {
 		/* Fine, we've erased it successfully */
@@ -1464,6 +1658,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(!is_cp_block(ubi, e));
+
 		ubi->lookuptbl[e->pnum] = e;
 		if (schedule_erase(ubi, e, 0)) {
 			kmem_cache_free(ubi_wl_entry_slab, e);
@@ -1481,7 +1678,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(!is_cp_block(ubi, e));
+
 		wl_tree_add(e, &ubi->free);
+
 		ubi->lookuptbl[e->pnum] = e;
 	}
 
@@ -1496,6 +1696,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 (__is_cp_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.7

[RFC][PATCH 5/7] MTD: UBI: Make process_eb() checkpoint aware

[Richard Weinberger]

If CONFIG_MTD_UBI_CHECKPOINT is not set, process_eb has to
remove all checkpointing volumes.

Signed-off-by: Richard Weinberger <rw@linutronix.de>
---
 drivers/mtd/ubi/scan.c |   10 +++++++++-
 1 files changed, 9 insertions(+), 1 deletions(-)

diff --git a/drivers/mtd/ubi/scan.c b/drivers/mtd/ubi/scan.c
index 0cb17d9..1d01fdc 100644
--- a/drivers/mtd/ubi/scan.c
+++ b/drivers/mtd/ubi/scan.c
@@ -1011,7 +1011,15 @@ 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) {
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+	if (vol_id > UBI_MAX_VOLUMES &&
+		vol_id != UBI_LAYOUT_VOLUME_ID &&
+		vol_id != UBI_CP_SB_VOLUME_ID &&
+		vol_id != UBI_CP_DATA_VOLUME_ID)
+#else
+	if (vol_id > UBI_MAX_VOLUMES && vol_id != UBI_LAYOUT_VOLUME_ID)
+#endif
+	{
 		int lnum = be32_to_cpu(vidh->lnum);
 
 		/* Unsupported internal volume */
-- 
1.7.7

[RFC][PATCH 6/7] MTD: UBI: Implement checkpointing support

[Richard Weinberger]

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

Signed-off-by: Richard Weinberger <rw@linutronix.de>
---
 drivers/mtd/ubi/Kconfig      |    7 +
 drivers/mtd/ubi/Makefile     |    1 +
 drivers/mtd/ubi/checkpoint.c |  975 ++++++++++++++++++++++++++++++++++++++++++
 drivers/mtd/ubi/ubi.h        |    6 +
 4 files changed, 989 insertions(+), 0 deletions(-)
 create mode 100644 drivers/mtd/ubi/checkpoint.c

diff --git a/drivers/mtd/ubi/Kconfig b/drivers/mtd/ubi/Kconfig
index 4dcc752..cae1419 100644
--- a/drivers/mtd/ubi/Kconfig
+++ b/drivers/mtd/ubi/Kconfig
@@ -51,6 +51,13 @@ config MTD_UBI_GLUEBI
 	   volume. This is handy to make MTD-oriented software (like JFFS2)
 	   work on top of UBI. Do not enable this unless you use legacy
 	   software.
+config MTD_UBI_CHECKPOINT
+	bool "UBI checkpointing (EXPERIMENTAL)"
+	depends on EXPERIMENTAL
+	default n
+	help
+	   This option enables UBI checkpointing - it allows attaching UBI
+	   devices without scanning the whole MTD device.
 
 config MTD_UBI_DEBUG
 	bool "UBI debugging"
diff --git a/drivers/mtd/ubi/Makefile b/drivers/mtd/ubi/Makefile
index c9302a5..845312a 100644
--- a/drivers/mtd/ubi/Makefile
+++ b/drivers/mtd/ubi/Makefile
@@ -3,5 +3,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
 
+ubi-$(CONFIG_MTD_UBI_CHECKPOINT) += checkpoint.o
 ubi-$(CONFIG_MTD_UBI_DEBUG) += debug.o
 obj-$(CONFIG_MTD_UBI_GLUEBI) += gluebi.o
diff --git a/drivers/mtd/ubi/checkpoint.c b/drivers/mtd/ubi/checkpoint.c
new file mode 100644
index 0000000..a0aa398
--- /dev/null
+++ b/drivers/mtd/ubi/checkpoint.c
@@ -0,0 +1,975 @@
+/*
+ * 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"
+
+/* Allocates a new VID header for the checkpoint itself */
+static struct ubi_vid_hdr *new_cp_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 checkpoint has be deleted on older kernels */
+	new->compat = UBI_COMPAT_DELETE;
+
+out:
+	return new;
+}
+
+/* Creates and adds a SEB to a given list */
+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;
+}
+
+/* Creates and adds a scan volume into ubi_scan_info */
+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;
+}
+
+/* Assigns a SEB to a given scan_volume and removes it from it's original list */
+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);
+}
+
+/* Inserts or updates a LEB which was found in the pool */
+static int update_vol(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;
+
+	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;
+		}
+
+		if (be32_to_cpu(new_vh->sqnum) && seb->sqnum == be32_to_cpu(new_vh->sqnum)) {
+			ubi_err("two LEBs with same sequence number %llu", seb->sqnum);
+			goto fail;
+		}
+
+		if (seb->sqnum > be32_to_cpu(new_vh->sqnum)) {
+			ubi_err("LEB on PEB %i is older than checkpoint?!", seb->pnum);
+
+			goto fail;
+		}
+
+		dbg_bld("Vol %i: Replacing LEB %i's PEB %i with PEB %i\n", sv->vol_id, seb->lnum, seb->pnum, new_seb->pnum);
+
+		victim = kmem_cache_alloc(si->scan_leb_slab, GFP_KERNEL);
+		if (!victim)
+			return -ENOMEM;
+
+		victim->copy_flag = 0;
+		victim->scrub = 0;
+		victim->ec = seb->ec;
+		victim->pnum = seb->pnum;
+		victim->lnum = seb->lnum;
+		list_add_tail(&victim->u.list, &si->erase);
+
+		seb->ec = new_seb->ec;
+		seb->pnum = new_seb->pnum;
+		kmem_cache_free(si->scan_leb_slab, new_seb);
+
+		return 0;
+	}
+
+	/* This LEB is new, let's add it to the volume */
+	dbg_bld("Vol %i (type = %i): SEB %i is new, adding it!\n", sv->vol_type, sv->vol_id, new_seb->lnum);
+
+	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;
+fail:
+	return -EINVAL;
+}
+
+/* Processes a SEB which was found in the pool */
+static int process_pool_seb(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_CP_SB_VOLUME_ID ||
+		be32_to_cpu(new_vh->vol_id) == UBI_CP_DATA_VOLUME_ID) {
+		kmem_cache_free(si->scan_leb_slab, new_seb);
+
+		return 0;
+	}
+
+	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 checkpoint pool!");
+		return -EINVAL;
+	}
+
+	ubi_assert(be32_to_cpu(new_vh->vol_id) == sv->vol_id);
+
+	return update_vol(si, sv, new_vh, new_seb);
+}
+
+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_scan_leb *new_seb;
+	int i;
+	int pnum;
+	int err;
+
+	vh = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vh)
+		return -ENOMEM;
+
+	/* 
+	 * Now scan all PEB in the pool to find changes which have been made 
+	 * after the creation of the checkpoint
+	 */
+	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) {
+			dbg_bld("PEB %i in pool is no longer free, scanning it! Vid %i", pnum, be32_to_cpu(vh->vol_id));
+
+			new_seb = kmem_cache_alloc(si->scan_leb_slab, GFP_KERNEL);
+			if (!new_seb) {
+				ubi_free_vid_hdr(ubi, vh);
+				return -ENOMEM;
+			}
+
+			new_seb->ec = -1;
+			new_seb->pnum = pnum;
+			new_seb->lnum = be32_to_cpu(vh->lnum);
+			new_seb->sqnum = be64_to_cpu(vh->sqnum);
+			new_seb->copy_flag = 0;
+			new_seb->scrub = 0;
+
+			err = process_pool_seb(si, vh, new_seb);
+			if (err) {
+				ubi_free_vid_hdr(ubi, vh);
+				return err;
+			}
+
+			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!");
+			ubi_free_vid_hdr(ubi, vh);
+			return err;
+		}
+		
+	}
+	ubi_free_vid_hdr(ubi, vh);
+
+	return 0;
+}
+
+/* Creates ubi_scan_info from the checkpoint */
+struct ubi_scan_info *ubi_scan_checkpoint(struct ubi_device *ubi,
+					  char *cp_raw,
+					  size_t cp_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 cp_pos = 0;
+	struct ubi_cp_sb *cpsb;
+	struct ubi_cp_hdr *cphdr;
+	struct ubi_cp_long_pool *cplpl;
+	struct ubi_cp_short_pool *cpspl;
+	struct ubi_cp_unk_pool *cpupl;
+	struct ubi_cp_ec *cpec;
+	struct ubi_cp_volhdr *cpvhdr;
+	struct ubi_cp_eba *cp_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->scan_leb_slab = kmem_cache_create("ubi_scan_leb_slab",
+					      sizeof(struct ubi_scan_leb),
+					      0, 0, NULL);
+	if (!si->scan_leb_slab)
+		goto out_si;
+
+	si->min_ec = UBI_MAX_ERASECOUNTER;
+
+	cpsb = (struct ubi_cp_sb *)(cp_raw);
+	si->max_sqnum = cpsb->sqnum;
+	cp_pos += sizeof(struct ubi_cp_sb);
+	if (cp_pos >= cp_size)
+		goto out_si;
+
+	cphdr = (struct ubi_cp_hdr *)(cp_raw + cp_pos);
+	cp_pos += sizeof(*cphdr);
+
+	if (cphdr->magic != UBI_CP_HDR_MAGIC)
+		goto out_si;
+
+	cplpl = (struct ubi_cp_long_pool *)(cp_raw + cp_pos);
+	cp_pos += sizeof(*cplpl);
+	if (cplpl->magic != UBI_CP_LPOOL_MAGIC)
+		goto out_si;
+
+	cpspl = (struct ubi_cp_short_pool *)(cp_raw + cp_pos);
+	cp_pos += sizeof(*cpspl);
+	if (cpspl->magic != UBI_CP_SPOOL_MAGIC)
+		goto out_si;
+
+	cpupl = (struct ubi_cp_unk_pool *)(cp_raw + cp_pos);
+	cp_pos += sizeof(*cpupl);
+	if (cpupl->magic != UBI_CP_UPOOL_MAGIC)
+		goto out_si;
+
+	/* read EC values from free list */
+	for (i = 0; i < be32_to_cpu(cphdr->nfree); i++) {
+		cpec = (struct ubi_cp_ec *)(cp_raw + cp_pos);
+		cp_pos += sizeof(*cpec);
+		if (cp_pos >= cp_size)
+			goto out_si;
+
+		add_seb(si, &si->free, be32_to_cpu(cpec->pnum),
+			be32_to_cpu(cpec->ec));
+	}
+
+	/* read EC values from used list */
+	for (i = 0; i < be32_to_cpu(cphdr->nused); i++) {
+		cpec = (struct ubi_cp_ec *)(cp_raw + cp_pos);
+		cp_pos += sizeof(*cpec);
+		if (cp_pos >= cp_size) goto out_si;
+	
+		add_seb(si, &used, be32_to_cpu(cpec->pnum),
+			be32_to_cpu(cpec->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(cphdr->nvol); i++) {
+		cpvhdr = (struct ubi_cp_volhdr *)(cp_raw + cp_pos);
+		cp_pos += sizeof(*cpvhdr);
+
+		dbg_bld("Found Volume %i! nused: %i\n", be32_to_cpu(cpvhdr->vol_id), be32_to_cpu(cpvhdr->used_ebs));
+
+		if (cpvhdr->magic != UBI_CP_VHDR_MAGIC)
+			goto out_si;
+
+		sv = add_vol(si, be32_to_cpu(cpvhdr->vol_id),
+			be32_to_cpu(cpvhdr->used_ebs),
+			be32_to_cpu(cpvhdr->data_pad),
+			cpvhdr->vol_type, be32_to_cpu(cpvhdr->last_eb_bytes));
+
+		if (!sv)
+			goto out_si;
+
+		si->vols_found++;
+		if (si->highest_vol_id < be32_to_cpu(cpvhdr->vol_id))
+			si->highest_vol_id = be32_to_cpu(cpvhdr->vol_id);
+
+		for (j = 0; j < be32_to_cpu(cpvhdr->used_ebs); j++) {
+			cp_eba = (struct ubi_cp_eba *)(cp_raw + cp_pos);
+			cp_pos += sizeof(*cp_eba);
+			if (cp_pos >= cp_size)
+				goto out_si;
+
+			if ((int)be32_to_cpu(cp_eba->pnum) < 0)
+				continue;
+
+			seb = NULL;
+			list_for_each_entry(tmp_seb, &used, u.list) {
+				if (tmp_seb->pnum == be32_to_cpu(cp_eba->pnum))
+					seb = tmp_seb;
+			}
+			
+			/* Not good, a EBA entry points to a PEB which is not in our used list */
+			if (!seb)
+				goto out_si;
+
+			seb->lnum = be32_to_cpu(cp_eba->lnum);
+			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 checkpoint 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, cplpl->pebs, be32_to_cpu(cplpl->size), &max_sqnum2) < 0)
+		goto out_si;
+	if (scan_pool(ubi, si, cpspl->pebs, be32_to_cpu(cpspl->size), &max_sqnum2) < 0)
+		goto out_si;
+	if (scan_pool(ubi, si, cpupl->pebs, be32_to_cpu(cpupl->size), &max_sqnum2) < 0)
+		goto out_si;
+
+	if (max_sqnum2 > si->max_sqnum)
+		si->max_sqnum = max_sqnum2;
+
+	return si;
+
+out_si:
+	ubi_scan_destroy_si(si);
+	return NULL;
+}
+
+/* Reads the checkpoint data from it's PEBs */
+struct ubi_scan_info *ubi_read_checkpoint(struct ubi_device *ubi, int cb_sb_pnum)
+{
+	struct ubi_cp_sb *cpsb;
+	struct ubi_vid_hdr *vh;
+	int ret, i, nblocks;
+	char *cp_raw;
+	size_t cp_size;
+	__be32 data_crc;
+	unsigned long long sqnum = 0;
+	struct ubi_scan_info *si = NULL;
+
+	cpsb = kmalloc(sizeof(*cpsb), GFP_KERNEL);
+	if (!cpsb) {
+		si = ERR_PTR(-ENOMEM);
+		goto out;
+	}
+
+	ret = ubi_io_read(ubi, cpsb, cb_sb_pnum, ubi->leb_start, sizeof(*cpsb));
+	if (ret) {
+		ubi_err("Unable to read checkpoint super block");
+		si = ERR_PTR(ret);
+		goto out;
+	}
+
+	if (cpsb->magic != UBI_CP_SB_MAGIC) {
+		ubi_err("Super block magic does not match");
+		si = ERR_PTR(-EINVAL);
+		goto free_sb;
+	}
+
+	if (cpsb->version != UBI_CP_FMT_VERSION) {
+		ubi_err("Unknown checkpoint format version!");
+		si = ERR_PTR(-EINVAL);
+		goto free_sb;
+	}
+
+	nblocks = be32_to_cpu(cpsb->nblocks);
+
+	if (nblocks > UBI_CP_MAX_BLOCKS || nblocks < 1) {
+		ubi_err("Number of checkpoint blocks is invalid");
+		si = ERR_PTR(-EINVAL);
+		goto free_sb;
+	}
+
+	cp_size = ubi->leb_size * nblocks;
+	/* cp_raw will contain the whole checkpoint */
+	cp_raw = vzalloc(cp_size);
+	if (!cp_raw) {
+		si = ERR_PTR(-ENOMEM);
+		goto free_sb;
+	}
+
+	vh = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vh) {
+		si = ERR_PTR(-ENOMEM);
+		goto free_raw;
+	}	
+
+	for (i = 0; i < nblocks; i++) {
+		ret = ubi_io_read_vid_hdr(ubi, be32_to_cpu(cpsb->block_loc[i]), vh, 0);
+		if (ret) {
+			ubi_err("Unable to read checkpoint block# %i (PEB: %i)", i, be32_to_cpu(cpsb->block_loc[i]));
+			si = ERR_PTR(ret);
+			goto free_vhdr;
+		}
+
+		if (i == 0) {
+			if (be32_to_cpu(vh->vol_id) != UBI_CP_SB_VOLUME_ID) {
+				si = ERR_PTR(-EINVAL);
+				goto free_vhdr;
+			}
+		} else {
+			if (be32_to_cpu(vh->vol_id) != UBI_CP_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, cp_raw + (ubi->leb_size * i),
+				  be32_to_cpu(cpsb->block_loc[i]), ubi->leb_start,
+				  ubi->leb_size);
+		
+		if (ret) {
+			ubi_err("Unable to read checkpoint block# %i (PEB: %i)", i, be32_to_cpu(cpsb->block_loc[i]));
+			si = ERR_PTR(ret);
+			goto free_vhdr;
+		}
+	}
+
+
+	cpsb = (struct ubi_cp_sb *)cp_raw;
+	data_crc = crc32_be(UBI_CRC32_INIT, cp_raw + sizeof(*cpsb), cp_size - sizeof(*cpsb));
+	if (data_crc != cpsb->data_crc){
+		ubi_err("Checkpoint data CRC is invalid");
+		si = ERR_PTR(-EINVAL);
+		goto free_vhdr;
+	}
+
+	cpsb->sqnum = sqnum;
+
+	si = ubi_scan_checkpoint(ubi, cp_raw, cp_size);
+	if (!si) {
+		si = ERR_PTR(-EINVAL);
+		goto free_vhdr;
+	}
+
+	/* Store the checkpoint position into the ubi_device struct */
+	ubi->cp = kmalloc(sizeof(struct ubi_checkpoint), GFP_KERNEL);
+	if (!ubi->cp) {
+		si = ERR_PTR(-ENOMEM);
+		ubi_scan_destroy_si(si);
+		goto free_vhdr;
+	}
+
+	ubi->cp->size = cp_size;
+	ubi->cp->used_blocks = nblocks;
+
+	for (i = 0; i < UBI_CP_MAX_BLOCKS; i++) {
+		if (i < nblocks) {
+			ubi->cp->peb[i] = be32_to_cpu(cpsb->block_loc[i]);
+			ubi->cp->ec[i] = be32_to_cpu(cpsb->block_ec[i]);
+		}
+		else {
+			ubi->cp->peb[i] = -1;
+			ubi->cp->ec[i] = 0;
+		}
+	}
+
+free_vhdr:
+	ubi_free_vid_hdr(ubi, vh);
+free_raw:
+	vfree(cp_raw);
+free_sb:
+	kfree(cpsb);
+out:
+	return si;
+}
+
+/* Searches the first UBI_CP_MAX_START PEBs for the checkpoint super block */
+int ubi_find_checkpoint(struct ubi_device *ubi)
+{
+	int i, ret;
+	int cp_sb = -ENOENT;
+	struct ubi_vid_hdr *vhdr;
+
+	vhdr = ubi_zalloc_vid_hdr(ubi, GFP_KERNEL);
+	if (!vhdr)
+		return -ENOMEM;
+
+	for (i = 0; i < UBI_CP_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_CP_SB_VOLUME_ID) {
+			cp_sb = i;
+			break;
+		}
+	}
+	
+	ubi_free_vid_hdr(ubi, vhdr);
+	return cp_sb;
+}
+
+static int ubi_create_checkpoint(struct ubi_device *ubi,
+				 struct ubi_checkpoint *new_cp)
+{
+	int ret;
+	size_t cp_pos = 0;
+	char *cp_raw;
+	int i, j;
+
+	struct ubi_cp_sb *cpsb;
+	struct ubi_cp_hdr *cph;
+	struct ubi_cp_long_pool *cplpl;
+	struct ubi_cp_short_pool *cpspl;
+	struct ubi_cp_unk_pool *cpupl;
+	struct ubi_cp_ec *cec;
+	struct ubi_cp_volhdr *cvh;
+	struct ubi_cp_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;
+
+	cp_raw = vzalloc(new_cp->size);
+	if (!cp_raw) {
+		ret = -ENOMEM;
+
+		goto out;
+	}
+
+	svhdr = new_cp_vhdr(ubi, UBI_CP_SB_VOLUME_ID);
+	if (!svhdr) {
+		ret = -ENOMEM;
+
+		goto out_vfree;
+	}
+	
+	dvhdr = new_cp_vhdr(ubi, UBI_CP_DATA_VOLUME_ID);
+	if (!dvhdr) {
+		ret = -ENOMEM;
+
+		goto out_kfree;
+	}
+
+	ubi_flush_prot_queue(ubi);
+
+	spin_lock(&ubi->volumes_lock);
+	spin_lock(&ubi->wl_lock);
+
+	cpsb = (struct ubi_cp_sb *)cp_raw;
+	cp_pos += sizeof(*cpsb);
+	ubi_assert(cp_pos <= new_cp->size);
+
+	cph = (struct ubi_cp_hdr *)(cp_raw + cp_pos);
+	cp_pos += sizeof(*cph);
+	ubi_assert(cp_pos <= new_cp->size);
+
+	cpsb->magic = UBI_CP_SB_MAGIC;
+	cpsb->version = UBI_CP_FMT_VERSION;
+	cpsb->nblocks = cpu_to_be32(new_cp->used_blocks);
+	/* the max sqnum will be filled in while *reading* the checkpoint */
+	cpsb->sqnum = 0;
+
+	cph->magic = UBI_CP_HDR_MAGIC;
+	nfree = 0;
+	nused = 0;
+	nvol = 0;
+
+	cplpl = (struct ubi_cp_long_pool *)(cp_raw + cp_pos);
+	cp_pos += sizeof(*cplpl);
+	cplpl->magic = UBI_CP_LPOOL_MAGIC;
+	cplpl->size = cpu_to_be32(ubi->long_pool.size);
+
+	cpspl = (struct ubi_cp_short_pool *)(cp_raw + cp_pos);
+	cp_pos += sizeof(*cpspl);
+	cpspl->magic = UBI_CP_SPOOL_MAGIC;
+	cpspl->size = cpu_to_be32(ubi->short_pool.size);
+
+	cpupl = (struct ubi_cp_unk_pool *)(cp_raw + cp_pos);
+	cp_pos += sizeof(*cpupl);
+	cpupl->magic = UBI_CP_UPOOL_MAGIC;
+	cpupl->size = cpu_to_be32(ubi->unk_pool.size);
+
+	for (i = 0; i < ubi->long_pool.size; i++)
+		cplpl->pebs[i] = cpu_to_be32(ubi->long_pool.pebs[i]);
+
+	for (i = 0; i < ubi->short_pool.size; i++)
+		cpspl->pebs[i] = cpu_to_be32(ubi->short_pool.pebs[i]);
+
+	for (i = 0; i < ubi->unk_pool.size; i++)
+		cpupl->pebs[i] = cpu_to_be32(ubi->unk_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_cp_ec *)(cp_raw + cp_pos);
+
+		cec->pnum = cpu_to_be32(wl_e->pnum);
+		cec->ec = cpu_to_be32(wl_e->ec);
+
+		nfree++;
+		cp_pos += sizeof(*cec);
+		ubi_assert(cp_pos <= new_cp->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_cp_ec *)(cp_raw + cp_pos);
+
+		cec->pnum = cpu_to_be32(wl_e->pnum);
+		cec->ec = cpu_to_be32(wl_e->ec);
+
+		nused++;
+		cp_pos += sizeof(*cec);
+		ubi_assert(cp_pos <= new_cp->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_cp_volhdr *)(cp_raw + cp_pos);
+		cp_pos += sizeof(*cvh);
+		ubi_assert(cp_pos <= new_cp->size);
+
+		cvh->magic = UBI_CP_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);
+
+		for (j = 0; j < vol->used_ebs; j++) {
+			ceba = (struct ubi_cp_eba *)(cp_raw + cp_pos);
+
+			ceba->lnum = cpu_to_be32(j);
+			ceba->pnum = cpu_to_be32(vol->eba_tbl[j]);
+
+			cp_pos += sizeof(*ceba);
+			ubi_assert(cp_pos <= new_cp->size);
+		}		
+	}
+	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 checkpoint SB to PEB %i\n", new_cp->peb[0]);
+	ret = ubi_io_write_vid_hdr(ubi, new_cp->peb[0], svhdr);	
+	if (ret) {
+		ubi_err("Unable to write vid_hdr to checkpoint SB!\n");
+		goto out_kfree;
+	}
+
+	for (i = 0; i < UBI_CP_MAX_BLOCKS; i++) {
+		cpsb->block_loc[i] = cpu_to_be32(new_cp->peb[i]);
+		cpsb->block_ec[i] = cpu_to_be32(new_cp->ec[i]);
+	}
+
+	cpsb->data_crc = 0;
+	cpsb->data_crc = crc32_be(UBI_CRC32_INIT, cp_raw + sizeof(*cpsb), new_cp->size - sizeof(*cpsb));
+
+	for (i = 1; i < new_cp->used_blocks; i++) {
+		dvhdr->sqnum = cpu_to_be64(ubi_next_sqnum(ubi));
+		dvhdr->lnum = cpu_to_be32(i);
+		dbg_bld("Writing checkpoint data to PEB %i sqnum %llu\n", new_cp->peb[i], be64_to_cpu(dvhdr->sqnum));
+		ret = ubi_io_write_vid_hdr(ubi, new_cp->peb[i], dvhdr);
+		if (ret) {
+			ubi_err("Unable to write vid_hdr to PEB %i!\n", new_cp->peb[i]);
+			goto out_kfree;
+		}
+	}
+
+	for (i = 0; i < new_cp->used_blocks; i++) {
+		ret = ubi_io_write(ubi, cp_raw + (i * ubi->leb_size), new_cp->peb[i], ubi->leb_start, ubi->leb_size);
+		if (ret) {
+			ubi_err("Unable to write checkpoint to PEB %i!\n", new_cp->peb[i]);
+			goto out_kfree;
+		}
+	}
+
+	ubi->cp = new_cp;
+
+	ubi_msg("Checkpoint written!");
+
+out_kfree:
+	kfree(svhdr);
+out_vfree:
+	vfree(cp_raw);
+out:
+	return ret;
+}
+
+/* Will be called by UBI upon volume creation/deletion/etc.. */
+int ubi_update_checkpoint(struct ubi_device *ubi)
+{
+	int ret, i;
+	struct ubi_checkpoint *new_cp, *old_cp;
+	struct ubi_wl_entry *e;
+
+	if (ubi->ro_mode)
+		return 0;
+
+	new_cp = kmalloc(sizeof(*new_cp), GFP_KERNEL);
+	if (!new_cp)
+		return -ENOMEM;
+
+	old_cp = ubi->cp;
+	ubi->cp = NULL;
+
+	if (old_cp) {
+		new_cp->peb[0] = ubi_wl_get_cp_peb(ubi, UBI_CP_MAX_START);
+		/* no fresh early PEB was found, reuse the old one */
+		if (new_cp->peb[0] < 0) {
+			struct ubi_ec_hdr *ec_hdr;
+
+			ec_hdr = kmalloc(sizeof(*ec_hdr), GFP_KERNEL);
+			if (!ec_hdr) {
+				kfree(new_cp);
+				return -ENOMEM;
+			}
+
+			/* we have to erase the block by hand */
+			ret = ubi_io_read_ec_hdr(ubi, old_cp->peb[0], ec_hdr, 0);
+			if (!ret) {
+				ubi_err("Unable to read EC header");
+
+				kfree(new_cp);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ret = ubi_io_sync_erase(ubi, new_cp->peb[0], 0);
+			if (ret < 0) {
+				ubi_err("Unable to erase old SB");
+
+				kfree(new_cp);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ec_hdr->ec += ret;
+			if (ret > UBI_MAX_ERASECOUNTER) {
+				ubi_err("Erase counter overflow!");
+				kfree(new_cp);
+				kfree(ec_hdr);
+				return -EINVAL;
+			}
+
+			ret = ubi_io_write_ec_hdr(ubi, old_cp->peb[0], ec_hdr);
+			kfree(ec_hdr);
+			if (ret) {
+				ubi_err("Unable to write new EC header");
+				kfree(new_cp);			
+				return -EINVAL;
+			}
+
+			new_cp->peb[0] = old_cp->peb[0];
+		}
+		else
+			/* we've got a new early PEB, return the old one */
+			ubi_wl_put_cp_peb(ubi, old_cp->peb[0], 0);
+
+		/* return all other checkpoint block to the wl system */
+		for (i = 1; i < UBI_CP_MAX_BLOCKS; i++) {
+			if (old_cp->peb[i] >= 0)
+				ubi_wl_put_cp_peb(ubi, old_cp->peb[i], 0);
+			else
+				break;
+		}
+	} else {
+		new_cp->peb[0] = ubi_wl_get_cp_peb(ubi, UBI_CP_MAX_START);
+		if (new_cp->peb[0] < 0) {
+			ubi_err("Could not find an early PEB");
+			kfree(new_cp);
+			return -ENOSPC;
+		}
+	}
+
+	new_cp->size = sizeof(struct ubi_cp_hdr) + \
+			sizeof(struct ubi_cp_long_pool) + \
+			sizeof(struct ubi_cp_short_pool) + \
+			sizeof(struct ubi_cp_unk_pool) + \
+			ubi->peb_count * (sizeof(struct ubi_cp_ec) + \
+			sizeof(struct ubi_cp_eba)) + \
+			sizeof(struct ubi_cp_volhdr) * UBI_MAX_VOLUMES;
+	new_cp->size = roundup(new_cp->size, ubi->leb_size);
+
+       	new_cp->used_blocks = new_cp->size / ubi->leb_size;
+
+	if (new_cp->used_blocks > UBI_CP_MAX_BLOCKS) {
+		ubi_err("Checkpoint too large");
+		kfree(new_cp);
+
+		return -ENOSPC;
+	}
+
+	/* give the wl subsystem a chance to produce some free blocks */
+	cond_resched();
+
+	for (i = 1; i < UBI_CP_MAX_BLOCKS; i++) {
+		if (i < new_cp->used_blocks) {
+			new_cp->peb[i] = ubi_wl_get_cp_peb(ubi, INT_MAX);
+			if (new_cp->peb[i] < 0) {
+				ubi_err("Could not get any free erase block");
+
+				while (i--)
+					ubi_wl_put_cp_peb(ubi, new_cp->peb[i], 0);
+
+				kfree(new_cp);
+
+				return -ENOSPC;
+			}
+			e = ubi->lookuptbl[new_cp->peb[i]];
+			ubi_assert(e);
+			new_cp->ec[i] = e->ec;
+		} else {
+			new_cp->peb[i] = -1;
+			new_cp->ec[i] = 0;
+		}
+	}
+	
+	kfree(old_cp);
+
+	return ubi_create_checkpoint(ubi, new_cp);
+}
diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index 4e8e8d2..a5aa2b1 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -608,6 +608,12 @@ 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);
 
+/* checkpoint.c */
+int ubi_update_checkpoint(struct ubi_device *ubi);
+struct ubi_scan_info *ubi_read_checkpoint(struct ubi_device *ubi, int cb_sb_pnum);
+int ubi_update_checkpoint(struct ubi_device *ubi);
+int ubi_find_checkpoint(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.7

[RFC][PATCH 7/7] MTD: UBI: wire up checkpointing

[Richard Weinberger]

Signed-off-by: Richard Weinberger <rw@linutronix.de>
---
 drivers/mtd/ubi/build.c |   83 +++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 83 insertions(+), 0 deletions(-)

diff --git a/drivers/mtd/ubi/build.c b/drivers/mtd/ubi/build.c
index 115749f..06c5c77 100644
--- a/drivers/mtd/ubi/build.c
+++ b/drivers/mtd/ubi/build.c
@@ -148,6 +148,17 @@ 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);
+
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+	switch (ntype) {
+		case UBI_VOLUME_ADDED:
+		case UBI_VOLUME_REMOVED:
+		case UBI_VOLUME_RESIZED:
+		case UBI_VOLUME_RENAMED:
+			if (ubi_update_checkpoint(ubi))
+				ubi_err("Unable to update checkpoint!");
+	}
+#endif
 	return blocking_notifier_call_chain(&ubi_notifiers, ntype, &nt);
 }
 
@@ -852,6 +863,61 @@ static int autoresize(struct ubi_device *ubi, int vol_id)
 	return 0;
 }
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+static int attach_by_checkpointing(struct ubi_device *ubi)
+{
+	int cp_start, err;
+	struct ubi_scan_info *si;
+
+	cp_start = ubi_find_checkpoint(ubi);
+	if (cp_start < 0)
+		return -ENOENT;
+
+	si = ubi_read_checkpoint(ubi, cp_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 recovered from checkpoint!");
+	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;
+}
+#endif
+
 /**
  * ubi_attach_mtd_dev - attach an MTD device.
  * @mtd: MTD device description object
@@ -931,6 +997,12 @@ 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;
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+	ubi->long_pool.used = ubi->long_pool.size = ubi->long_pool.max_size = ARRAY_SIZE(ubi->long_pool.pebs);
+	ubi->short_pool.used = ubi->short_pool.size = ubi->short_pool.max_size = ARRAY_SIZE(ubi->short_pool.pebs);
+	ubi->unk_pool.used = ubi->unk_pool.size = ubi->unk_pool.max_size = ARRAY_SIZE(ubi->unk_pool.pebs);
+#endif
+
 	mutex_init(&ubi->buf_mutex);
 	mutex_init(&ubi->ckvol_mutex);
 	mutex_init(&ubi->device_mutex);
@@ -957,7 +1029,18 @@ int ubi_attach_mtd_dev(struct mtd_info *mtd, int ubi_num, int vid_hdr_offset)
 	if (err)
 		goto out_free;
 
+#ifdef CONFIG_MTD_UBI_CHECKPOINT
+	err = attach_by_checkpointing(ubi);
+
+	if (err) {
+		if (err != -ENOENT)
+			ubi_msg("falling back to attach by scanning mode!\n");
+
+		err = attach_by_scanning(ubi);
+	}
+#else
 	err = attach_by_scanning(ubi);
+#endif
 	if (err) {
 		dbg_err("failed to attach by scanning, error %d", err);
 		goto out_debugging;
-- 
1.7.7

Re: [RFC][PATCH 7/7] MTD: UBI: wire up checkpointing

[Shmulik Ladkani]

On Tue, 14 Feb 2012 21:06:46 +0100 Richard Weinberger <rw@linutronix.de> wrote:
> +#ifdef CONFIG_MTD_UBI_CHECKPOINT
> +static int attach_by_checkpointing(struct ubi_device *ubi)
> +{
> +	int cp_start, err;
> +	struct ubi_scan_info *si;
> +
> +	cp_start = ubi_find_checkpoint(ubi);
> +	if (cp_start < 0)
> +		return -ENOENT;
> +
> +	si = ubi_read_checkpoint(ubi, cp_start);
> +	if (IS_ERR(si))
> +		return PTR_ERR(si);
> +
> +	ubi->bad_peb_count = 0;
> +	ubi->good_peb_count = ubi->peb_count;

Zero reported bad PEBs when checkpointing.
Seems that checkpointing does not remember number/location of bad PEBs.
Are we fine with that?

> +#ifdef CONFIG_MTD_UBI_CHECKPOINT
> +	err = attach_by_checkpointing(ubi);
> +
> +	if (err) {
> +		if (err != -ENOENT)
> +			ubi_msg("falling back to attach by scanning mode!\n");
> +
> +		err = attach_by_scanning(ubi);
> +	}

Code does not fit error message.
Message states "falling back to scanning" only if "err != -ENOENT".
However code calls 'attach_by_scanning' regardless 'err'.
Was it your intention?

Regards,
Shmulik

Re: [RFC][PATCH 7/7] MTD: UBI: wire up checkpointing

[Richard Weinberger]

Am 19.02.2012 14:57, schrieb Shmulik Ladkani:
> On Tue, 14 Feb 2012 21:06:46 +0100 Richard Weinberger<rw@linutronix.de>  wrote:
>> +#ifdef CONFIG_MTD_UBI_CHECKPOINT
>> +static int attach_by_checkpointing(struct ubi_device *ubi)
>> +{
>> +	int cp_start, err;
>> +	struct ubi_scan_info *si;
>> +
>> +	cp_start = ubi_find_checkpoint(ubi);
>> +	if (cp_start<  0)
>> +		return -ENOENT;
>> +
>> +	si = ubi_read_checkpoint(ubi, cp_start);
>> +	if (IS_ERR(si))
>> +		return PTR_ERR(si);
>> +
>> +	ubi->bad_peb_count = 0;
>> +	ubi->good_peb_count = ubi->peb_count;
>
> Zero reported bad PEBs when checkpointing.
> Seems that checkpointing does not remember number/location of bad PEBs.

Currently checkpointing cares only about used and free PEBs.
Bad PEBs are no longer visible to UBI after recovering from a checkpoint.

> Are we fine with that?

This patch is a RFC. :-)

>> +#ifdef CONFIG_MTD_UBI_CHECKPOINT
>> +	err = attach_by_checkpointing(ubi);
>> +
>> +	if (err) {
>> +		if (err != -ENOENT)
>> +			ubi_msg("falling back to attach by scanning mode!\n");
>> +
>> +		err = attach_by_scanning(ubi);
>> +	}
>
> Code does not fit error message.
> Message states "falling back to scanning" only if "err != -ENOENT".
> However code calls 'attach_by_scanning' regardless 'err'.
> Was it your intention?

Yes.
If recovering from a checkpoint fails the corresponding code prints
a human readable error message in any case.

Thanks,
//richard

Re: [RFC][PATCH 7/7] MTD: UBI: wire up checkpointing

[Shmulik Ladkani]

On Sun, 19 Feb 2012 15:08:44 +0100 Richard Weinberger <rw@linutronix.de> wrote:
> Am 19.02.2012 14:57, schrieb Shmulik Ladkani:
> > On Tue, 14 Feb 2012 21:06:46 +0100 Richard Weinberger<rw@linutronix.de>  wrote:
> >> +#ifdef CONFIG_MTD_UBI_CHECKPOINT
> >> +static int attach_by_checkpointing(struct ubi_device *ubi)
> >> +{
> >> +	int cp_start, err;
> >> +	struct ubi_scan_info *si;
> >> +
> >> +	cp_start = ubi_find_checkpoint(ubi);
> >> +	if (cp_start<  0)
> >> +		return -ENOENT;
> >> +
> >> +	si = ubi_read_checkpoint(ubi, cp_start);
> >> +	if (IS_ERR(si))
> >> +		return PTR_ERR(si);
> >> +
> >> +	ubi->bad_peb_count = 0;
> >> +	ubi->good_peb_count = ubi->peb_count;
> >
> > Zero reported bad PEBs when checkpointing.
> > Seems that checkpointing does not remember number/location of bad PEBs.
> 
> Currently checkpointing cares only about used and free PEBs.
> Bad PEBs are no longer visible to UBI after recovering from a checkpoint.

Ok.
However it is still reported to the log in 'ubi_attach_mtd_dev'
and as a sysfs attribute.
BTW, the counter is still incremented by WL subsystem, though.
Hence, reported value will be bad PEBs encountered since last attach
(where formerly, it was absolute total bad PEBs in the ubi device).
Maybe remove 'bad_peb_count' altogether.

Also, "ubi->good_peb_count = ubi->peb_count" results in different
'beb_rsvd_level' caculation, see 'ubi_calculate_reserved'.

> > Are we fine with that?
> 
> This patch is a RFC. :-)

So I noticed :-) 
Just trying to point out things which cause ubi system to behave
differently.

> Thanks,
> //richard

Wellcome. Will try to review the big stuff later on.

Regards,
Shmulik

Re: [RFC][PATCH 7/7] MTD: UBI: wire up checkpointing

[Richard Weinberger]

Am 19.02.2012 15:40, schrieb Shmulik Ladkani:
> On Sun, 19 Feb 2012 15:08:44 +0100 Richard Weinberger<rw@linutronix.de>  wrote:
>> Am 19.02.2012 14:57, schrieb Shmulik Ladkani:
>>> On Tue, 14 Feb 2012 21:06:46 +0100 Richard Weinberger<rw@linutronix.de>   wrote:
>>>> +#ifdef CONFIG_MTD_UBI_CHECKPOINT
>>>> +static int attach_by_checkpointing(struct ubi_device *ubi)
>>>> +{
>>>> +	int cp_start, err;
>>>> +	struct ubi_scan_info *si;
>>>> +
>>>> +	cp_start = ubi_find_checkpoint(ubi);
>>>> +	if (cp_start<   0)
>>>> +		return -ENOENT;
>>>> +
>>>> +	si = ubi_read_checkpoint(ubi, cp_start);
>>>> +	if (IS_ERR(si))
>>>> +		return PTR_ERR(si);
>>>> +
>>>> +	ubi->bad_peb_count = 0;
>>>> +	ubi->good_peb_count = ubi->peb_count;
>>>
>>> Zero reported bad PEBs when checkpointing.
>>> Seems that checkpointing does not remember number/location of bad PEBs.
>>
>> Currently checkpointing cares only about used and free PEBs.
>> Bad PEBs are no longer visible to UBI after recovering from a checkpoint.
>
> Ok.
> However it is still reported to the log in 'ubi_attach_mtd_dev'
> and as a sysfs attribute.
> BTW, the counter is still incremented by WL subsystem, though.
> Hence, reported value will be bad PEBs encountered since last attach
> (where formerly, it was absolute total bad PEBs in the ubi device).
> Maybe remove 'bad_peb_count' altogether.
>
> Also, "ubi->good_peb_count = ubi->peb_count" results in different
> 'beb_rsvd_level' caculation, see 'ubi_calculate_reserved'.

I can add these counters into the checkpoint.

>>> Are we fine with that?
>>
>> This patch is a RFC. :-)
>
> So I noticed :-)
> Just trying to point out things which cause ubi system to behave
> differently.
>

Thanks a lot for reviewing this feature!
//richard

Re: [RFC][PATCH 6/7] MTD: UBI: Implement checkpointing support

[Shmulik Ladkani]

On Tue, 14 Feb 2012 21:06:45 +0100 Richard Weinberger <rw@linutronix.de> wrote:
> Implements UBI checkpointing support.
> It reduces the attaching time from O(N) to O(1).
> Checkpoints are written on demand and upon changes of the volume layout.
> If the recovery from a checkpoint fails we fall back to scanning mode.

Partially reviewed the feature. Great work.
There's some tiny styling/coding issues, will send references if you'd
like.

I'll comment on the feature itself later on.

Meanwhile, there's a potential memleak/crash you might wanna fix.

> +/* Reads the checkpoint data from it's PEBs */
> +struct ubi_scan_info *ubi_read_checkpoint(struct ubi_device *ubi, int cb_sb_pnum)
> +{
> +	struct ubi_cp_sb *cpsb;
> +	struct ubi_vid_hdr *vh;
> +	int ret, i, nblocks;
> +	char *cp_raw;
> +	size_t cp_size;
> +	__be32 data_crc;
> +	unsigned long long sqnum = 0;
> +	struct ubi_scan_info *si = NULL;
> +
> +	cpsb = kmalloc(sizeof(*cpsb), GFP_KERNEL);
> +	if (!cpsb) {
> +		si = ERR_PTR(-ENOMEM);
> +		goto out;
> +	}
> +
> +	ret = ubi_io_read(ubi, cpsb, cb_sb_pnum, ubi->leb_start, sizeof(*cpsb));
> +	if (ret) {
> +		ubi_err("Unable to read checkpoint super block");
> +		si = ERR_PTR(ret);
> +		goto out;

s/goto out/goto free_sb/
(otherwise 'cpsb' not freed)

> +	/* cp_raw will contain the whole checkpoint */
> +	cp_raw = vzalloc(cp_size);

  ...

> +
> +	cpsb = (struct ubi_cp_sb *)cp_raw;

'cpsb' is overwritten, but formerly kmalloced (at the beginning of
ubi_read_checkpoint).
Should free 'cpsb' prior assignment, or alternatively use different
variable then 'cpsb'.

  ...

> +
> +free_vhdr:
> +	ubi_free_vid_hdr(ubi, vh);
> +free_raw:
> +	vfree(cp_raw);
> +free_sb:
> +	kfree(cpsb);

Freeing 'cp_raw' and 'cpsb', but in the normal flow, they point to the
same thing.

Regards,
Shmulik

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

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

On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
> The following patch set implements checkpointing support for
> UBI. Checkpointing is an optional feature which stores the physical to
> logical eraseblock relations in a checkpointing superblock to reduce
> the initialization time of UBI. The current init time of UBI is
> proportional to the number of physical erase blocks on the FLASH
> device. With checkpointing enabled the scan time is limited to a fixed
> number of blocks.

Notice, your patch-set has huge amount of checkpatch.pl complaints -
please fix them. This will also be consistent with the overall UBI
coding style where I honored checkpatch.pl limitations like identation
style and 80 chars per line.


-- 
Best Regards,
Artem Bityutskiy

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

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

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

On Wed, 2012-02-29 at 13:35 +0200, Artem Bityutskiy wrote:
> On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
> > The following patch set implements checkpointing support for
> > UBI. Checkpointing is an optional feature which stores the physical to
> > logical eraseblock relations in a checkpointing superblock to reduce
> > the initialization time of UBI. The current init time of UBI is
> > proportional to the number of physical erase blocks on the FLASH
> > device. With checkpointing enabled the scan time is limited to a fixed
> > number of blocks.
> 
> Notice, your patch-set has huge amount of checkpatch.pl complaints -
> please fix them. This will also be consistent with the overall UBI
> coding style where I honored checkpatch.pl limitations like identation
> style and 80 chars per line.

Just for reference:

--------------------------------------------------------------------------------

checkpatch.pl has some complaints:

--------------------------------------------------------------------------------

checkpatch.pl results for patch "[PATCH 1/7] MTD: UBI: Add checkpoint on-chip layout"

ERROR:TRAILING_WHITESPACE: trailing whitespace
#67: FILE: drivers/mtd/ubi/ubi-media.h:413:
+/* struct ubi_cp_hdr is followed by exactly three struct ub_cp_pool_* records $

total: 1 errors, 0 warnings, 85 lines checked

--------------------------------------------------------------------------------

checkpatch.pl results for patch "[PATCH 4/7] MTD: UBI: Make wl subsystem checkpoint aware"

WARNING:LONG_LINE: line over 80 characters
#83: FILE: drivers/mtd/ubi/wl.c:417:
+static struct ubi_wl_entry *find_early_wl_entry(struct rb_root *root, int max_pnum)

WARNING:LONG_LINE: line over 80 characters
#167: FILE: drivers/mtd/ubi/wl.c:578:
+       /* pool contains no free blocks, create a new one and write a checkoint */

WARNING:LONG_LINE: line over 80 characters
#169: FILE: drivers/mtd/ubi/wl.c:580:
+               for (pool->size = 0; pool->size < pool->max_size; pool->size++) {

ERROR:TRAILING_WHITESPACE: trailing whitespace
#249: FILE: drivers/mtd/ubi/wl.c:819:
+^I/* This can happen if we recovered from a checkpoint the very $

total: 1 errors, 3 warnings, 287 lines checked

--------------------------------------------------------------------------------

checkpatch.pl results for patch "[PATCH 5/7] MTD: UBI: Make process_eb() checkpoint aware"

WARNING:SUSPECT_CODE_INDENT: suspect code indent for conditional statements (8, 8)
#29: FILE: drivers/mtd/ubi/scan.c:1020:
+       if (vol_id > UBI_MAX_VOLUMES && vol_id != UBI_LAYOUT_VOLUME_ID)
[...]
+       {

total: 0 errors, 1 warnings, 16 lines checked

--------------------------------------------------------------------------------

checkpatch.pl results for patch "[PATCH 6/7] MTD: UBI: Implement checkpointing support"

WARNING:CONFIG_DESCRIPTION: please write a paragraph that describes the config symbol fully
#32: FILE: drivers/mtd/ubi/Kconfig:58:
+       help

ERROR:TRAILING_WHITESPACE: trailing whitespace
#154: FILE: drivers/mtd/ubi/checkpoint.c:100:
+^I$

WARNING:LONG_LINE: line over 80 characters
#159: FILE: drivers/mtd/ubi/checkpoint.c:105:
+/* Assigns a SEB to a given scan_volume and removes it from it's original list */

ERROR:TRAILING_WHITESPACE: trailing whitespace
#184: FILE: drivers/mtd/ubi/checkpoint.c:130:
+^I$

WARNING:LONG_LINE: line over 80 characters
#209: FILE: drivers/mtd/ubi/checkpoint.c:155:
+               if (be32_to_cpu(new_vh->sqnum) && seb->sqnum == be32_to_cpu(new_vh->sqnum)) {

WARNING:LONG_LINE: line over 80 characters
#210: FILE: drivers/mtd/ubi/checkpoint.c:156:
+                       ubi_err("two LEBs with same sequence number %llu", seb->sqnum);

WARNING:LONG_LINE: line over 80 characters
#215: FILE: drivers/mtd/ubi/checkpoint.c:161:
+                       ubi_err("LEB on PEB %i is older than checkpoint?!", seb->pnum);

WARNING:LONG_LINE: line over 80 characters
#220: FILE: drivers/mtd/ubi/checkpoint.c:166:
+               dbg_bld("Vol %i: Replacing LEB %i's PEB %i with PEB %i\n", sv->vol_id, seb->lnum, seb->pnum, new_seb->pnum);

WARNING:LONG_LINE: line over 80 characters
#241: FILE: drivers/mtd/ubi/checkpoint.c:187:
+       dbg_bld("Vol %i (type = %i): SEB %i is new, adding it!\n", sv->vol_type, sv->vol_id, new_seb->lnum);

WARNING:LONG_LINE: line over 80 characters
#257: FILE: drivers/mtd/ubi/checkpoint.c:203:
+static int process_pool_seb(struct ubi_scan_info *si, struct ubi_vid_hdr *new_vh,

ERROR:TRAILING_WHITESPACE: trailing whitespace
#310: FILE: drivers/mtd/ubi/checkpoint.c:256:
+^I/* $

ERROR:TRAILING_WHITESPACE: trailing whitespace
#311: FILE: drivers/mtd/ubi/checkpoint.c:257:
+^I * Now scan all PEB in the pool to find changes which have been made $

WARNING:LONG_LINE: line over 80 characters
#321: FILE: drivers/mtd/ubi/checkpoint.c:267:
+                       dbg_bld("PEB %i in pool is no longer free, scanning it! Vid %i", pnum, be32_to_cpu(vh->vol_id));

WARNING:LONG_LINE: line over 80 characters
#323: FILE: drivers/mtd/ubi/checkpoint.c:269:
+                       new_seb = kmem_cache_alloc(si->scan_leb_slab, GFP_KERNEL);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#350: FILE: drivers/mtd/ubi/checkpoint.c:296:
+^I^I$

ERROR:TRAILING_STATEMENTS: trailing statements should be on next line
#441: FILE: drivers/mtd/ubi/checkpoint.c:387:
+               if (cp_pos >= cp_size) goto out_si;

ERROR:TRAILING_WHITESPACE: trailing whitespace
#442: FILE: drivers/mtd/ubi/checkpoint.c:388:
+^I$

WARNING:LONG_LINE: line over 80 characters
#454: FILE: drivers/mtd/ubi/checkpoint.c:400:
+               dbg_bld("Found Volume %i! nused: %i\n", be32_to_cpu(cpvhdr->vol_id), be32_to_cpu(cpvhdr->used_ebs));

ERROR:TRAILING_WHITESPACE: trailing whitespace
#485: FILE: drivers/mtd/ubi/checkpoint.c:431:
+^I^I^I$

WARNING:LONG_LINE: line over 80 characters
#486: FILE: drivers/mtd/ubi/checkpoint.c:432:
+                       /* Not good, a EBA entry points to a PEB which is not in our used list */

WARNING:LONG_LINE: line over 80 characters
#493: FILE: drivers/mtd/ubi/checkpoint.c:439:
+                       dbg_bld("Inserting pnum %i (leb %i) to vol %i", seb->pnum, seb->lnum, sv->vol_id);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#500: FILE: drivers/mtd/ubi/checkpoint.c:446:
+^I */  $

WARNING:LONG_LINE: line over 80 characters
#506: FILE: drivers/mtd/ubi/checkpoint.c:452:
+       if (scan_pool(ubi, si, cplpl->pebs, be32_to_cpu(cplpl->size), &max_sqnum2) < 0)

WARNING:LONG_LINE: line over 80 characters
#508: FILE: drivers/mtd/ubi/checkpoint.c:454:
+       if (scan_pool(ubi, si, cpspl->pebs, be32_to_cpu(cpspl->size), &max_sqnum2) < 0)

WARNING:LONG_LINE: line over 80 characters
#510: FILE: drivers/mtd/ubi/checkpoint.c:456:
+       if (scan_pool(ubi, si, cpupl->pebs, be32_to_cpu(cpupl->size), &max_sqnum2) < 0)

WARNING:LONG_LINE: line over 80 characters
#524: FILE: drivers/mtd/ubi/checkpoint.c:470:
+struct ubi_scan_info *ubi_read_checkpoint(struct ubi_device *ubi, int cb_sb_pnum)

ERROR:TRAILING_WHITESPACE: trailing whitespace
#580: FILE: drivers/mtd/ubi/checkpoint.c:526:
+^I}^I$

WARNING:LONG_LINE: line over 80 characters
#583: FILE: drivers/mtd/ubi/checkpoint.c:529:
+               ret = ubi_io_read_vid_hdr(ubi, be32_to_cpu(cpsb->block_loc[i]), vh, 0);

WARNING:LONG_LINE: line over 80 characters
#585: FILE: drivers/mtd/ubi/checkpoint.c:531:
+                       ubi_err("Unable to read checkpoint block# %i (PEB: %i)", i, be32_to_cpu(cpsb->block_loc[i]));

WARNING:LONG_LINE: line over 80 characters
#606: FILE: drivers/mtd/ubi/checkpoint.c:552:
+                                 be32_to_cpu(cpsb->block_loc[i]), ubi->leb_start,

ERROR:TRAILING_WHITESPACE: trailing whitespace
#608: FILE: drivers/mtd/ubi/checkpoint.c:554:
+^I^I$

WARNING:LONG_LINE: line over 80 characters
#610: FILE: drivers/mtd/ubi/checkpoint.c:556:
+                       ubi_err("Unable to read checkpoint block# %i (PEB: %i)", i, be32_to_cpu(cpsb->block_loc[i]));

WARNING:LONG_LINE: line over 80 characters
#618: FILE: drivers/mtd/ubi/checkpoint.c:564:
+       data_crc = crc32_be(UBI_CRC32_INIT, cp_raw + sizeof(*cpsb), cp_size - sizeof(*cpsb));

ERROR:SPACING: space required before the open brace '{'
#619: FILE: drivers/mtd/ubi/checkpoint.c:565:
+       if (data_crc != cpsb->data_crc){

ERROR:ELSE_AFTER_BRACE: else should follow close brace '}'
#649: FILE: drivers/mtd/ubi/checkpoint.c:595:
+               }
+               else {

ERROR:TRAILING_WHITESPACE: trailing whitespace
#687: FILE: drivers/mtd/ubi/checkpoint.c:633:
+^I$

ERROR:TRAILING_WHITESPACE: trailing whitespace
#730: FILE: drivers/mtd/ubi/checkpoint.c:676:
+^I$

WARNING:LONG_LINE: line over 80 characters
#831: FILE: drivers/mtd/ubi/checkpoint.c:777:
+               ubi_assert(vol->vol_type == UBI_DYNAMIC_VOLUME || vol->vol_type == UBI_STATIC_VOLUME);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#841: FILE: drivers/mtd/ubi/checkpoint.c:787:
+^I^I}^I^I$

ERROR:TRAILING_WHITESPACE: trailing whitespace
#852: FILE: drivers/mtd/ubi/checkpoint.c:798:
+^Iret = ubi_io_write_vid_hdr(ubi, new_cp->peb[0], svhdr);^I$

WARNING:LONG_LINE: line over 80 characters
#864: FILE: drivers/mtd/ubi/checkpoint.c:810:
+       cpsb->data_crc = crc32_be(UBI_CRC32_INIT, cp_raw + sizeof(*cpsb), new_cp->size - sizeof(*cpsb));

WARNING:LONG_LINE: line over 80 characters
#869: FILE: drivers/mtd/ubi/checkpoint.c:815:
+               dbg_bld("Writing checkpoint data to PEB %i sqnum %llu\n", new_cp->peb[i], be64_to_cpu(dvhdr->sqnum));

WARNING:LONG_LINE: line over 80 characters
#872: FILE: drivers/mtd/ubi/checkpoint.c:818:
+                       ubi_err("Unable to write vid_hdr to PEB %i!\n", new_cp->peb[i]);

WARNING:LONG_LINE: line over 80 characters
#878: FILE: drivers/mtd/ubi/checkpoint.c:824:
+               ret = ubi_io_write(ubi, cp_raw + (i * ubi->leb_size), new_cp->peb[i], ubi->leb_start, ubi->leb_size);

WARNING:LONG_LINE: line over 80 characters
#880: FILE: drivers/mtd/ubi/checkpoint.c:826:
+                       ubi_err("Unable to write checkpoint to PEB %i!\n", new_cp->peb[i]);

WARNING:LONG_LINE: line over 80 characters
#927: FILE: drivers/mtd/ubi/checkpoint.c:873:
+                       ret = ubi_io_read_ec_hdr(ubi, old_cp->peb[0], ec_hdr, 0);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#957: FILE: drivers/mtd/ubi/checkpoint.c:903:
+^I^I^I^Ikfree(new_cp);^I^I^I$

ERROR:ELSE_AFTER_BRACE: else should follow close brace '}'
#963: FILE: drivers/mtd/ubi/checkpoint.c:909:
+               }
+               else

ERROR:CODE_INDENT: code indent should use tabs where possible
#992: FILE: drivers/mtd/ubi/checkpoint.c:938:
+       ^Inew_cp->used_blocks = new_cp->size / ubi->leb_size;$

WARNING:SPACE_BEFORE_TAB: please, no space before tabs
#992: FILE: drivers/mtd/ubi/checkpoint.c:938:
+       ^Inew_cp->used_blocks = new_cp->size / ubi->leb_size;$

WARNING:LEADING_SPACE: please, no spaces at the start of a line
#992: FILE: drivers/mtd/ubi/checkpoint.c:938:
+       ^Inew_cp->used_blocks = new_cp->size / ubi->leb_size;$

WARNING:LONG_LINE: line over 80 characters
#1011: FILE: drivers/mtd/ubi/checkpoint.c:957:
+                                       ubi_wl_put_cp_peb(ubi, new_cp->peb[i], 0);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1025: FILE: drivers/mtd/ubi/checkpoint.c:971:
+^I$

WARNING:LONG_LINE: line over 80 characters
#1040: FILE: drivers/mtd/ubi/ubi.h:613:
+struct ubi_scan_info *ubi_read_checkpoint(struct ubi_device *ubi, int cb_sb_pnum);

total: 21 errors, 33 warnings, 1006 lines checked

--------------------------------------------------------------------------------

checkpatch.pl results for patch "[PATCH 7/7] MTD: UBI: wire up checkpointing"

ERROR:SWITCH_CASE_INDENT_LEVEL: switch and case should be at the same indent
#21: FILE: drivers/mtd/ubi/build.c:153:
+       switch (ntype) {
+               case UBI_VOLUME_ADDED:
+               case UBI_VOLUME_REMOVED:
+               case UBI_VOLUME_RESIZED:
+               case UBI_VOLUME_RENAMED:

WARNING:LONG_LINE: line over 80 characters
#100: FILE: drivers/mtd/ubi/build.c:1001:
+       ubi->long_pool.used = ubi->long_pool.size = ubi->long_pool.max_size = ARRAY_SIZE(ubi->long_pool.pebs);

WARNING:LONG_LINE: line over 80 characters
#101: FILE: drivers/mtd/ubi/build.c:1002:
+       ubi->short_pool.used = ubi->short_pool.size = ubi->short_pool.max_size = ARRAY_SIZE(ubi->short_pool.pebs);

WARNING:LONG_LINE: line over 80 characters
#102: FILE: drivers/mtd/ubi/build.c:1003:
+       ubi->unk_pool.used = ubi->unk_pool.size = ubi->unk_pool.max_size = ARRAY_SIZE(ubi->unk_pool.pebs);

total: 1 errors, 3 warnings, 108 lines checked

--------------------------------------------------------------------------------

checkpatch.pl results for the entire squashed patch-set

ERROR:TRAILING_WHITESPACE: trailing whitespace
#67: FILE: drivers/mtd/ubi/ubi-media.h:413:
+/* struct ubi_cp_hdr is followed by exactly three struct ub_cp_pool_* records $

WARNING:LONG_LINE: line over 80 characters
#380: FILE: drivers/mtd/ubi/wl.c:417:
+static struct ubi_wl_entry *find_early_wl_entry(struct rb_root *root, int max_pnum)

WARNING:LONG_LINE: line over 80 characters
#464: FILE: drivers/mtd/ubi/wl.c:578:
+       /* pool contains no free blocks, create a new one and write a checkoint */

WARNING:LONG_LINE: line over 80 characters
#466: FILE: drivers/mtd/ubi/wl.c:580:
+               for (pool->size = 0; pool->size < pool->max_size; pool->size++) {

ERROR:TRAILING_WHITESPACE: trailing whitespace
#546: FILE: drivers/mtd/ubi/wl.c:819:
+^I/* This can happen if we recovered from a checkpoint the very $

WARNING:SUSPECT_CODE_INDENT: suspect code indent for conditional statements (8, 8)
#651: FILE: drivers/mtd/ubi/scan.c:1020:
+       if (vol_id > UBI_MAX_VOLUMES && vol_id != UBI_LAYOUT_VOLUME_ID)
[...]
+       {

WARNING:CONFIG_DESCRIPTION: please write a paragraph that describes the config symbol fully
#692: FILE: drivers/mtd/ubi/Kconfig:58:
+       help

ERROR:TRAILING_WHITESPACE: trailing whitespace
#814: FILE: drivers/mtd/ubi/checkpoint.c:100:
+^I$

WARNING:LONG_LINE: line over 80 characters
#819: FILE: drivers/mtd/ubi/checkpoint.c:105:
+/* Assigns a SEB to a given scan_volume and removes it from it's original list */

ERROR:TRAILING_WHITESPACE: trailing whitespace
#844: FILE: drivers/mtd/ubi/checkpoint.c:130:
+^I$

WARNING:LONG_LINE: line over 80 characters
#869: FILE: drivers/mtd/ubi/checkpoint.c:155:
+               if (be32_to_cpu(new_vh->sqnum) && seb->sqnum == be32_to_cpu(new_vh->sqnum)) {

WARNING:LONG_LINE: line over 80 characters
#870: FILE: drivers/mtd/ubi/checkpoint.c:156:
+                       ubi_err("two LEBs with same sequence number %llu", seb->sqnum);

WARNING:LONG_LINE: line over 80 characters
#875: FILE: drivers/mtd/ubi/checkpoint.c:161:
+                       ubi_err("LEB on PEB %i is older than checkpoint?!", seb->pnum);

WARNING:LONG_LINE: line over 80 characters
#880: FILE: drivers/mtd/ubi/checkpoint.c:166:
+               dbg_bld("Vol %i: Replacing LEB %i's PEB %i with PEB %i\n", sv->vol_id, seb->lnum, seb->pnum, new_seb->pnum);

WARNING:LONG_LINE: line over 80 characters
#901: FILE: drivers/mtd/ubi/checkpoint.c:187:
+       dbg_bld("Vol %i (type = %i): SEB %i is new, adding it!\n", sv->vol_type, sv->vol_id, new_seb->lnum);

WARNING:LONG_LINE: line over 80 characters
#917: FILE: drivers/mtd/ubi/checkpoint.c:203:
+static int process_pool_seb(struct ubi_scan_info *si, struct ubi_vid_hdr *new_vh,

ERROR:TRAILING_WHITESPACE: trailing whitespace
#970: FILE: drivers/mtd/ubi/checkpoint.c:256:
+^I/* $

ERROR:TRAILING_WHITESPACE: trailing whitespace
#971: FILE: drivers/mtd/ubi/checkpoint.c:257:
+^I * Now scan all PEB in the pool to find changes which have been made $

WARNING:LONG_LINE: line over 80 characters
#981: FILE: drivers/mtd/ubi/checkpoint.c:267:
+                       dbg_bld("PEB %i in pool is no longer free, scanning it! Vid %i", pnum, be32_to_cpu(vh->vol_id));

WARNING:LONG_LINE: line over 80 characters
#983: FILE: drivers/mtd/ubi/checkpoint.c:269:
+                       new_seb = kmem_cache_alloc(si->scan_leb_slab, GFP_KERNEL);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1010: FILE: drivers/mtd/ubi/checkpoint.c:296:
+^I^I$

ERROR:TRAILING_STATEMENTS: trailing statements should be on next line
#1101: FILE: drivers/mtd/ubi/checkpoint.c:387:
+               if (cp_pos >= cp_size) goto out_si;

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1102: FILE: drivers/mtd/ubi/checkpoint.c:388:
+^I$

WARNING:LONG_LINE: line over 80 characters
#1114: FILE: drivers/mtd/ubi/checkpoint.c:400:
+               dbg_bld("Found Volume %i! nused: %i\n", be32_to_cpu(cpvhdr->vol_id), be32_to_cpu(cpvhdr->used_ebs));

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1145: FILE: drivers/mtd/ubi/checkpoint.c:431:
+^I^I^I$

WARNING:LONG_LINE: line over 80 characters
#1146: FILE: drivers/mtd/ubi/checkpoint.c:432:
+                       /* Not good, a EBA entry points to a PEB which is not in our used list */

WARNING:LONG_LINE: line over 80 characters
#1153: FILE: drivers/mtd/ubi/checkpoint.c:439:
+                       dbg_bld("Inserting pnum %i (leb %i) to vol %i", seb->pnum, seb->lnum, sv->vol_id);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1160: FILE: drivers/mtd/ubi/checkpoint.c:446:
+^I */  $

WARNING:LONG_LINE: line over 80 characters
#1166: FILE: drivers/mtd/ubi/checkpoint.c:452:
+       if (scan_pool(ubi, si, cplpl->pebs, be32_to_cpu(cplpl->size), &max_sqnum2) < 0)

WARNING:LONG_LINE: line over 80 characters
#1168: FILE: drivers/mtd/ubi/checkpoint.c:454:
+       if (scan_pool(ubi, si, cpspl->pebs, be32_to_cpu(cpspl->size), &max_sqnum2) < 0)

WARNING:LONG_LINE: line over 80 characters
#1170: FILE: drivers/mtd/ubi/checkpoint.c:456:
+       if (scan_pool(ubi, si, cpupl->pebs, be32_to_cpu(cpupl->size), &max_sqnum2) < 0)

WARNING:LONG_LINE: line over 80 characters
#1184: FILE: drivers/mtd/ubi/checkpoint.c:470:
+struct ubi_scan_info *ubi_read_checkpoint(struct ubi_device *ubi, int cb_sb_pnum)

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1240: FILE: drivers/mtd/ubi/checkpoint.c:526:
+^I}^I$

WARNING:LONG_LINE: line over 80 characters
#1243: FILE: drivers/mtd/ubi/checkpoint.c:529:
+               ret = ubi_io_read_vid_hdr(ubi, be32_to_cpu(cpsb->block_loc[i]), vh, 0);

WARNING:LONG_LINE: line over 80 characters
#1245: FILE: drivers/mtd/ubi/checkpoint.c:531:
+                       ubi_err("Unable to read checkpoint block# %i (PEB: %i)", i, be32_to_cpu(cpsb->block_loc[i]));

WARNING:LONG_LINE: line over 80 characters
#1266: FILE: drivers/mtd/ubi/checkpoint.c:552:
+                                 be32_to_cpu(cpsb->block_loc[i]), ubi->leb_start,

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1268: FILE: drivers/mtd/ubi/checkpoint.c:554:
+^I^I$

WARNING:LONG_LINE: line over 80 characters
#1270: FILE: drivers/mtd/ubi/checkpoint.c:556:
+                       ubi_err("Unable to read checkpoint block# %i (PEB: %i)", i, be32_to_cpu(cpsb->block_loc[i]));

WARNING:LONG_LINE: line over 80 characters
#1278: FILE: drivers/mtd/ubi/checkpoint.c:564:
+       data_crc = crc32_be(UBI_CRC32_INIT, cp_raw + sizeof(*cpsb), cp_size - sizeof(*cpsb));

ERROR:SPACING: space required before the open brace '{'
#1279: FILE: drivers/mtd/ubi/checkpoint.c:565:
+       if (data_crc != cpsb->data_crc){

ERROR:ELSE_AFTER_BRACE: else should follow close brace '}'
#1309: FILE: drivers/mtd/ubi/checkpoint.c:595:
+               }
+               else {

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1347: FILE: drivers/mtd/ubi/checkpoint.c:633:
+^I$

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1390: FILE: drivers/mtd/ubi/checkpoint.c:676:
+^I$

WARNING:LONG_LINE: line over 80 characters
#1491: FILE: drivers/mtd/ubi/checkpoint.c:777:
+               ubi_assert(vol->vol_type == UBI_DYNAMIC_VOLUME || vol->vol_type == UBI_STATIC_VOLUME);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1501: FILE: drivers/mtd/ubi/checkpoint.c:787:
+^I^I}^I^I$

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1512: FILE: drivers/mtd/ubi/checkpoint.c:798:
+^Iret = ubi_io_write_vid_hdr(ubi, new_cp->peb[0], svhdr);^I$

WARNING:LONG_LINE: line over 80 characters
#1524: FILE: drivers/mtd/ubi/checkpoint.c:810:
+       cpsb->data_crc = crc32_be(UBI_CRC32_INIT, cp_raw + sizeof(*cpsb), new_cp->size - sizeof(*cpsb));

WARNING:LONG_LINE: line over 80 characters
#1529: FILE: drivers/mtd/ubi/checkpoint.c:815:
+               dbg_bld("Writing checkpoint data to PEB %i sqnum %llu\n", new_cp->peb[i], be64_to_cpu(dvhdr->sqnum));

WARNING:LONG_LINE: line over 80 characters
#1532: FILE: drivers/mtd/ubi/checkpoint.c:818:
+                       ubi_err("Unable to write vid_hdr to PEB %i!\n", new_cp->peb[i]);

WARNING:LONG_LINE: line over 80 characters
#1538: FILE: drivers/mtd/ubi/checkpoint.c:824:
+               ret = ubi_io_write(ubi, cp_raw + (i * ubi->leb_size), new_cp->peb[i], ubi->leb_start, ubi->leb_size);

WARNING:LONG_LINE: line over 80 characters
#1540: FILE: drivers/mtd/ubi/checkpoint.c:826:
+                       ubi_err("Unable to write checkpoint to PEB %i!\n", new_cp->peb[i]);

WARNING:LONG_LINE: line over 80 characters
#1587: FILE: drivers/mtd/ubi/checkpoint.c:873:
+                       ret = ubi_io_read_ec_hdr(ubi, old_cp->peb[0], ec_hdr, 0);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1617: FILE: drivers/mtd/ubi/checkpoint.c:903:
+^I^I^I^Ikfree(new_cp);^I^I^I$

ERROR:ELSE_AFTER_BRACE: else should follow close brace '}'
#1623: FILE: drivers/mtd/ubi/checkpoint.c:909:
+               }
+               else

ERROR:CODE_INDENT: code indent should use tabs where possible
#1652: FILE: drivers/mtd/ubi/checkpoint.c:938:
+       ^Inew_cp->used_blocks = new_cp->size / ubi->leb_size;$

WARNING:SPACE_BEFORE_TAB: please, no space before tabs
#1652: FILE: drivers/mtd/ubi/checkpoint.c:938:
+       ^Inew_cp->used_blocks = new_cp->size / ubi->leb_size;$

WARNING:LEADING_SPACE: please, no spaces at the start of a line
#1652: FILE: drivers/mtd/ubi/checkpoint.c:938:
+       ^Inew_cp->used_blocks = new_cp->size / ubi->leb_size;$

WARNING:LONG_LINE: line over 80 characters
#1671: FILE: drivers/mtd/ubi/checkpoint.c:957:
+                                       ubi_wl_put_cp_peb(ubi, new_cp->peb[i], 0);

ERROR:TRAILING_WHITESPACE: trailing whitespace
#1685: FILE: drivers/mtd/ubi/checkpoint.c:971:
+^I$

WARNING:LONG_LINE: line over 80 characters
#1700: FILE: drivers/mtd/ubi/ubi.h:613:
+struct ubi_scan_info *ubi_read_checkpoint(struct ubi_device *ubi, int cb_sb_pnum);

ERROR:SWITCH_CASE_INDENT_LEVEL: switch and case should be at the same indent
#1731: FILE: drivers/mtd/ubi/build.c:153:
+       switch (ntype) {
+               case UBI_VOLUME_ADDED:
+               case UBI_VOLUME_REMOVED:
+               case UBI_VOLUME_RESIZED:
+               case UBI_VOLUME_RENAMED:

WARNING:LONG_LINE: line over 80 characters
#1810: FILE: drivers/mtd/ubi/build.c:1001:
+       ubi->long_pool.used = ubi->long_pool.size = ubi->long_pool.max_size = ARRAY_SIZE(ubi->long_pool.pebs);

WARNING:LONG_LINE: line over 80 characters
#1811: FILE: drivers/mtd/ubi/build.c:1002:
+       ubi->short_pool.used = ubi->short_pool.size = ubi->short_pool.max_size = ARRAY_SIZE(ubi->short_pool.pebs);

WARNING:LONG_LINE: line over 80 characters
#1812: FILE: drivers/mtd/ubi/build.c:1003:
+       ubi->unk_pool.used = ubi->unk_pool.size = ubi->unk_pool.max_size = ARRAY_SIZE(ubi->unk_pool.pebs);

total: 24 errors, 40 warnings, 1616 lines checked

--------------------------------------------------------------------------------
[2012-02-29 13:23:49] test-patchset: Preserved tmpdir: /home/space/dedekind/aiaiai/test-patchset.kMgP

-- 
Best Regards,
Artem Bityutskiy

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

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Richard Weinberger]

Am 29.02.2012 12:35, schrieb Artem Bityutskiy:
> On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
>> The following patch set implements checkpointing support for
>> UBI. Checkpointing is an optional feature which stores the physical to
>> logical eraseblock relations in a checkpointing superblock to reduce
>> the initialization time of UBI. The current init time of UBI is
>> proportional to the number of physical erase blocks on the FLASH
>> device. With checkpointing enabled the scan time is limited to a fixed
>> number of blocks.
> 
> Notice, your patch-set has huge amount of checkpatch.pl complaints -
> please fix them. This will also be consistent with the overall UBI
> coding style where I honored checkpatch.pl limitations like identation
> style and 80 chars per line.
> 

All checkpatch.pl complaints will be fixed.
But first we have to discuss and address real problems.

By sending the second iteration of the patch-set I'll make checkpatch.pl
happy. :-)

Thanks,
//richard

-- 
Phone: +49 7556 91 98 91; Fax.: +49 7556 91 98 86

Firmensitz: 88690 Uhldingen, Auf dem Berg 3
Registergericht: Amtsgericht Freiburg i. Br., HRB 700 806;
StNr. 87007/07777; Ust-Id Nr.: DE252739476
Geschäftsführer: Heinz Egger, Thomas Gleixner

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

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

On Wed, 2012-02-29 at 12:40 +0100, Richard Weinberger wrote:
> Am 29.02.2012 12:35, schrieb Artem Bityutskiy:
> > On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
> >> The following patch set implements checkpointing support for
> >> UBI. Checkpointing is an optional feature which stores the physical to
> >> logical eraseblock relations in a checkpointing superblock to reduce
> >> the initialization time of UBI. The current init time of UBI is
> >> proportional to the number of physical erase blocks on the FLASH
> >> device. With checkpointing enabled the scan time is limited to a fixed
> >> number of blocks.
> > 
> > Notice, your patch-set has huge amount of checkpatch.pl complaints -
> > please fix them. This will also be consistent with the overall UBI
> > coding style where I honored checkpatch.pl limitations like identation
> > style and 80 chars per line.
> > 
> 
> All checkpatch.pl complaints will be fixed.
> But first we have to discuss and address real problems.

Sure, I just to not have time to look at real stuff now.

But yes, I assume you will come up with a good way to stress-test it.
You will look how the unstable bits problem affects the checkpointing. I
would suggest you to implement power-cut emulation in UBI just like we
have it in UBIFS, then run the integck test which already supports UBIFS
power cut emulation. This will allow to catch a lot of issues.

-- 
Best Regards,
Artem Bityutskiy

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

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

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

On Wed, 2012-02-29 at 12:40 +0100, Richard Weinberger wrote:
> > Notice, your patch-set has huge amount of checkpatch.pl complaints -
> > please fix them. This will also be consistent with the overall UBI
> > coding style where I honored checkpatch.pl limitations like identation
> > style and 80 chars per line.
> > 
> 
> All checkpatch.pl complaints will be fixed.
> But first we have to discuss and address real problems.

Note, I just have a maintainers script which takes the patch-set as
input, then checks bisectability, finds new warnings, checks with
sparse/smatch/coccinelle/checkpatch.pl etc. I just gave your patches to
my script and checkpatch.pl complaints were the only things identified
by the scripts.

-- 
Best Regards,
Artem Bityutskiy

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

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

Another not-so-technical comment.

On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
> The following patch set implements checkpointing support for
> UBI. Checkpointing is an optional feature which stores the physical to
> logical eraseblock relations in a checkpointing superblock to reduce
> the initialization time of UBI. 

So this is basically about improving scalability and "mount" time. This
has nothing to do with checkpointing most people are aware of.
Confusing...

Really, this tirm is already reserved by file-systems, things like
virtual machines where it means "freezing" the contents and doing COW
when changing the freezed blocks and guaranteeing the ability to
"roll-back" to the checkpointed data.

Please, consider an option of picking a different name. In JFFS2 a
"similar" thing was called "summaries", and even this is better than
"checkpoint", I think.

-- 
Best Regards,
Artem Bityutskiy

Re: [RFC][PATCH 1/7] MTD: UBI: Add checkpoint on-chip layout

[Artem Bityutskiy]

On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
> Specify the on-chip checkpoint layout.
> The checkpoint consists of two major parts.
> A super block (identified via UBI_CP_SB_VOLUME_ID) and
> zero or more data blocks (identified via UBI_CP_DATA_VOLUME_ID).
> Data blocks are only used if whole checkpoint information does not fit
> into the super block.

And superblock is also a more or less standard name used by file-system.
I easily imagine difficulties and confusion when discussing UBIFS and
UBI and mixing UBI and UBIFS supersblocks up. IMHO, anything unique is
much better, even if it does not make much sense. E.g., "boss block" or
"pomo block" (pomo = boss in Finnish).

Would you consider picking a different name as well please?

-- 
Best Regards,
Artem Bityutskiy

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

Just basic questions to make sure I understand things correctly.

Do you have plans to also change the user-space tools?

On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
> 1) A primary checkpoint block, which contains merily a pointer to the
>    erase block(s) which hold the real checkpointing data.
> 
>    This primary block is guaranteed to be held within the first N
>    eraseblocks of a device. N is momentarily set to 16, but it might
>    be necessary to make this configurable in some way.

Does it mean that you reserve the first 16 PEBs for the primary block? 

I guess we need to carefully look an this number and make the default to
be good enough for the general case.

> 2) The secondary checkpoint blocks, which contain the real
>    checkpointing data (physical to logical eraseblock relations,
>    erase counts, sequence numbers ...)

>    Aside of that the checkpointing data contains a list of blocks
>    which belong to the active working pool. The active working pool is
>    a fixed number of blocks for shortterm, longterm and unknown
>    storage time, which can be modified before the next checkpoint set
>    is written to FLASH. These blocks need to be scanned in the
>    conventional UBI scan mode.

BTW, WRT short-term etc - how about just killing these concepts? I am
really not sure they make much sense anyway and give any improvements. 

I guess this would simplify things for you as well. I'd vote for
removing them.

>    The reason for these pool blocks is to reduce the checkpoint
>    updates to the necessary minimum to avoid accelerated device
>    wearout in scenarios where data changes rapidly. The checkpoint
>    data is updated whenever a working pool runs out of blocks.
> 
>    The number of pool blocks can be defined with a config option at
>    the moment, but this could also be done at runtime via sysfs. In
>    case of a change the checkpointing data would be reconstructed.

Id suggest to introduce as few configuration knob as possible. My
experience show that they usually only hurt. I'd stick to this rule for
most cases: no user, no knob.

> So the checkpoint scan consists of the following steps:
> 
>    1) Find the primary checkpoint block by scanning the start of the
>       device.
> 
>    2) Read the real checkpoint data and construct the UBI device info
>       structures.
> 
>    3) Scan the pool blocks.
> 
> All these operations scan a limited number of erase blocks which makes
> the UBI init O(1) and independent of the device size.

Well, is it really true? The larger is the flash the more you read and
process anyway, and it is still linear, but the multiplier becomes very
small, so this is a huge improvement.

> The checkpoint functionality is fully compatible with existing UBI
> deployments. If no checkpoint blocks can be found then the device is
> scanned and the checkpoint blocks are created from the scanned
> information.
> 
> Aside of review and testing it needs to be decided, whether the number
> of pool blocks should be deduced from the device size (number of
> physical eraseblocks) or made configurable at compile or runtime.

I would go for automatic decisions. Manual configuration can always be
added later if needed.

> Thanks to the folks at CELF who sponsored this work!

Indeed thanks! And thank you Richard!

-- 
Best Regards,
Artem Bityutskiy

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Richard Weinberger]

Am 07.03.2012 17:04, schrieb Artem Bityutskiy:
> Another not-so-technical comment.
>
> On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
>> The following patch set implements checkpointing support for
>> UBI. Checkpointing is an optional feature which stores the physical to
>> logical eraseblock relations in a checkpointing superblock to reduce
>> the initialization time of UBI.
>
> So this is basically about improving scalability and "mount" time. This
> has nothing to do with checkpointing most people are aware of.
> Confusing...

Mostly because "checkpointing" is a buzzword. ;-)

> Really, this tirm is already reserved by file-systems, things like
> virtual machines where it means "freezing" the contents and doing COW
> when changing the freezed blocks and guaranteeing the ability to
> "roll-back" to the checkpointed data.
>
> Please, consider an option of picking a different name. In JFFS2 a
> "similar" thing was called "summaries", and even this is better than
> "checkpoint", I think.

What about "Erase block indexing"?
Basically a checkpoint is an index...

Thanks,
//richard

P.s: I'm really bad in picking names.

Re: [RFC][PATCH 1/7] MTD: UBI: Add checkpoint on-chip layout

[Richard Weinberger]

Am 07.03.2012 17:09, schrieb Artem Bityutskiy:
> On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
>> Specify the on-chip checkpoint layout.
>> The checkpoint consists of two major parts.
>> A super block (identified via UBI_CP_SB_VOLUME_ID) and
>> zero or more data blocks (identified via UBI_CP_DATA_VOLUME_ID).
>> Data blocks are only used if whole checkpoint information does not fit
>> into the super block.
>
> And superblock is also a more or less standard name used by file-system.
> I easily imagine difficulties and confusion when discussing UBIFS and
> UBI and mixing UBI and UBIFS supersblocks up. IMHO, anything unique is
> much better, even if it does not make much sense. E.g., "boss block" or
> "pomo block" (pomo = boss in Finnish).
>
> Would you consider picking a different name as well please?
>

Will do.

Thanks,
//richard

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Richard Weinberger]

Am 07.03.2012 17:33, schrieb Artem Bityutskiy:
> Just basic questions to make sure I understand things correctly.
>
> Do you have plans to also change the user-space tools?

Maybe ubiattach to make the attach method selectable.
Attaching by scanning or checkpointing...

> On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
>> 1) A primary checkpoint block, which contains merily a pointer to the
>>     erase block(s) which hold the real checkpointing data.
>>
>>     This primary block is guaranteed to be held within the first N
>>     eraseblocks of a device. N is momentarily set to 16, but it might
>>     be necessary to make this configurable in some way.
>
> Does it mean that you reserve the first 16 PEBs for the primary block?

The current implementation selects out one of the first 64 blocks.
I know I wrote 16 in the initial RFC, but it's 64.
But it does not reserve them.

While writing a new checkpoint it tries to select an other early block.
If no new early block is available it reuses the old one.

> I guess we need to carefully look an this number and make the default to
> be good enough for the general case.

Yep. The current number was chosen randomly. :D

>> 2) The secondary checkpoint blocks, which contain the real
>>     checkpointing data (physical to logical eraseblock relations,
>>     erase counts, sequence numbers ...)
>
>>     Aside of that the checkpointing data contains a list of blocks
>>     which belong to the active working pool. The active working pool is
>>     a fixed number of blocks for shortterm, longterm and unknown
>>     storage time, which can be modified before the next checkpoint set
>>     is written to FLASH. These blocks need to be scanned in the
>>     conventional UBI scan mode.
>
> BTW, WRT short-term etc - how about just killing these concepts? I am
> really not sure they make much sense anyway and give any improvements.

Good idea!

> I guess this would simplify things for you as well. I'd vote for
> removing them.
>
>>     The reason for these pool blocks is to reduce the checkpoint
>>     updates to the necessary minimum to avoid accelerated device
>>     wearout in scenarios where data changes rapidly. The checkpoint
>>     data is updated whenever a working pool runs out of blocks.
>>
>>     The number of pool blocks can be defined with a config option at
>>     the moment, but this could also be done at runtime via sysfs. In
>>     case of a change the checkpointing data would be reconstructed.
>
> Id suggest to introduce as few configuration knob as possible. My
> experience show that they usually only hurt. I'd stick to this rule for
> most cases: no user, no knob.

Yeah.

>> So the checkpoint scan consists of the following steps:
>>
>>     1) Find the primary checkpoint block by scanning the start of the
>>        device.
>>
>>     2) Read the real checkpoint data and construct the UBI device info
>>        structures.
>>
>>     3) Scan the pool blocks.
>>
>> All these operations scan a limited number of erase blocks which makes
>> the UBI init O(1) and independent of the device size.
>
> Well, is it really true? The larger is the flash the more you read and
> process anyway, and it is still linear, but the multiplier becomes very
> small, so this is a huge improvement.

Yes. :)

Using checkpointing UBI only has to scan a fixed (independent of the 
flash size!) number of blocks.

>> The checkpoint functionality is fully compatible with existing UBI
>> deployments. If no checkpoint blocks can be found then the device is
>> scanned and the checkpoint blocks are created from the scanned
>> information.
>>
>> Aside of review and testing it needs to be decided, whether the number
>> of pool blocks should be deduced from the device size (number of
>> physical eraseblocks) or made configurable at compile or runtime.
>
> I would go for automatic decisions. Manual configuration can always be
> added later if needed.
>
>> Thanks to the folks at CELF who sponsored this work!
>
> Indeed thanks! And thank you Richard!

Thanks,
//richard

Re: [RFC][PATCH 1/7] MTD: UBI: Add checkpoint on-chip layout

[Thomas Gleixner]

On Wed, 7 Mar 2012, Richard Weinberger wrote:

> Am 07.03.2012 17:09, schrieb Artem Bityutskiy:
> > On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
> > > Specify the on-chip checkpoint layout.
> > > The checkpoint consists of two major parts.
> > > A super block (identified via UBI_CP_SB_VOLUME_ID) and
> > > zero or more data blocks (identified via UBI_CP_DATA_VOLUME_ID).
> > > Data blocks are only used if whole checkpoint information does not fit
> > > into the super block.
> > 
> > And superblock is also a more or less standard name used by file-system.
> > I easily imagine difficulties and confusion when discussing UBIFS and
> > UBI and mixing UBI and UBIFS supersblocks up. IMHO, anything unique is
> > much better, even if it does not make much sense. E.g., "boss block" or
> > "pomo block" (pomo = boss in Finnish).
> > 
> > Would you consider picking a different name as well please?
> > 
> 
> Will do.

What about FASTMAP ?

That's what the whole story is about. Building the logical/physical
mappings (fast). Then call the "super block" FASTMAP_REF and the data
stuff FASTMAP_DATA.

That's the sanest I could come up with aside of smuggling in my
favourite buzzword ROADMAP :)

Of course we could stay with latin and name it: UBIUBI. ubiubi is latin
for: where the heck is it, but I guess that's stretching it a bit :)

Thanks,

	tglx

Re: [RFC][PATCH 1/7] MTD: UBI: Add checkpoint on-chip layout

[Thomas Gleixner]

On Wed, 7 Mar 2012, Thomas Gleixner wrote:
> On Wed, 7 Mar 2012, Richard Weinberger wrote:
> Of course we could stay with latin and name it: UBIUBI. ubiubi is latin
> for: where the heck is it, but I guess that's stretching it a bit :)

Digging more in my fading away latin:

	ubivis == everywhere

	UBIVIS == Unsorted Block Images Velocity Index System

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Shmulik Ladkani]

On Wed, 07 Mar 2012 22:19:00 +0100 Richard Weinberger <rw@linutronix.de> wrote:
> >> All these operations scan a limited number of erase blocks which makes
> >> the UBI init O(1) and independent of the device size.
> >
> > Well, is it really true? The larger is the flash the more you read and
> > process anyway, and it is still linear, but the multiplier becomes very
> > small, so this is a huge improvement.
> 
> Yes. :)
> 
> Using checkpointing UBI only has to scan a fixed (independent of the 
> flash size!) number of blocks.

But doesn't the CP data (sorry, UBIUBI data :) need to have one
'struct ubi_cp_ec' descriptor for each used/free PEB, and as such the
maximum number of 'ubi_cp_ec' descriptors is total device PEBs, meaning
CP data is still linearly scaled to device size (with a very small
multiplier)?

Regards,
Shmulik

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Richard Weinberger]

On 08.03.2012 08:08, Shmulik Ladkani wrote:
> But doesn't the CP data (sorry, UBIUBI data :) need to have one
> 'struct ubi_cp_ec' descriptor for each used/free PEB, and as such the
> maximum number of 'ubi_cp_ec' descriptors is total device PEBs, meaning
> CP data is still linearly scaled to device size (with a very small
> multiplier)?
>

It's UBIVIS data. :D

The size of the checkpoint depends on the number of free/used PEBs.
But in most cases the checkpoints fits into one or two PEBs.
Because larger devices have larger erase blocks...

Thanks,
//richard

-- 
Phone: +49 7556 91 98 91; Fax.: +49 7556 91 98 86

Firmensitz: 88690 Uhldingen, Auf dem Berg 3
Registergericht: Amtsgericht Freiburg i. Br., HRB 700 806;
StNr. 87007/07777; Ust-Id Nr.: DE252739476
Geschäftsführer: Heinz Egger, Thomas Gleixner

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

On Wed, 2012-03-07 at 22:01 +0100, Richard Weinberger wrote:
> > Please, consider an option of picking a different name. In JFFS2 a
> > "similar" thing was called "summaries", and even this is better than
> > "checkpoint", I think.
> 
> What about "Erase block indexing"?
> Basically a checkpoint is an index...

Index is also very loaded word already, and UBIFS has index, would be
nice to use a word UBIFS does not use. Thomas's suggestions like fastmap
or roadmap/milestone are fine with me. UBIUBI is clever, but probably
confusing a bit as well :-)

-- 
Best Regards,
Artem Bityutskiy

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

On Wed, 2012-03-07 at 22:19 +0100, Richard Weinberger wrote:
> Maybe ubiattach to make the attach method selectable.
> Attaching by scanning or checkpointing...

I guess this is also something not really needed unless there is a user.
Attach should just pick the fastest way automatically.

What I meant is actually ubiformat - that would be nice to change. But
this is not the first urgency thing as well.

> 
> > On Tue, 2012-02-14 at 21:06 +0100, Richard Weinberger wrote:
> >> 1) A primary checkpoint block, which contains merily a pointer to the
> >>     erase block(s) which hold the real checkpointing data.
> >>
> >>     This primary block is guaranteed to be held within the first N
> >>     eraseblocks of a device. N is momentarily set to 16, but it might
> >>     be necessary to make this configurable in some way.
> >
> > Does it mean that you reserve the first 16 PEBs for the primary block?
> 
> The current implementation selects out one of the first 64 blocks.
> I know I wrote 16 in the initial RFC, but it's 64.
> But it does not reserve them.

So you will need to update the primary block from time to time, right?
How is it done?

> While writing a new checkpoint it tries to select an other early block.

Would you please also stricten the terminology around word "block". In
UBI and UBIFS I tried hard to stick to:

PEB - physical eraseblock
LEB - logical eraseblock

I tried to not use "block" or "eraseblock" to keep things unambiguous.

I did not read your code through, but is my assumption correct:

primary PEB - the physical eraseblock withing the first 64 PEBs which
contains the primary block.

primary block - a data structure which is stored in the primary PEB.

I would imagine you write primary blocks to the primary PEB one after
another, and when there is no more space in the primary PEB, you have to
fine a new one or erase the old one. At least this is something I'd
probably do...

But I guess you just re-write whole primary PEB every time and do not
squeeze many primary blocks into one PEB, right?

Would be great if you maintained a text file somewhere and updated it so
that we had a reference doc with design basics/terminology available.
Not too detailed so it would not take too much time.

> If no new early block is available it reuses the old one.

Hmm, I would think it should work like this:

You need to update the primary block. You check its erase counter. 

If the erasecounter is too high ( > min. EC + some threshold), you have
to pick a different PEB, otherwise just keep using the old one.

Picking a different primary PEB: you first check if there is a free PEB
withing those 64 with not too high EC. If yes - great, pick it.

If no, check if there is any PEB withing 64 with suitable EC at all - if
yes, you move the data from this PEB somewhere else (beyond the first
64) and use it.

If there is no suitable PEB at all, you just do not do the checkpoint
(let's pick another name finally please) and print a scary warning.

Something like this I'd imagine...

> > BTW, WRT short-term etc - how about just killing these concepts? I am
> > really not sure they make much sense anyway and give any improvements.
> 
> Good idea!

So I can expect the removal patches? :-)

> > Well, is it really true? The larger is the flash the more you read and
> > process anyway, and it is still linear, but the multiplier becomes very
> > small, so this is a huge improvement.
> 
> Yes. :)
> 
> Using checkpointing UBI only has to scan a fixed (independent of the 
> flash size!) number of blocks.

Checkpoint has elements inside, and the larger is the flash, the more
elements it has. And eraseblock size grows much slower than flash size I
believe.


-- 
Best Regards,
Artem Bityutskiy

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Artem Bityutskiy]

On Thu, 2012-03-08 at 10:21 +0100, Richard Weinberger wrote:
> On 08.03.2012 08:08, Shmulik Ladkani wrote:
> > But doesn't the CP data (sorry, UBIUBI data :) need to have one
> > 'struct ubi_cp_ec' descriptor for each used/free PEB, and as such the
> > maximum number of 'ubi_cp_ec' descriptors is total device PEBs, meaning
> > CP data is still linearly scaled to device size (with a very small
> > multiplier)?
> >
> 
> It's UBIVIS data. :D

I have a suggestion for the property of the new term. Because your old
one can be both a noun and a verb (write a checkpoint, to checkpoint),
the new term should probably have the same property.

To write the ubibis and to ubibis? Hmm... not sure.

To write the fastmap and to fastmap or decide to not fastmap because all
PEBs within the first 64 have too high erasecounter? Sounds better IMO.

> The size of the checkpoint depends on the number of free/used PEBs.
> But in most cases the checkpoints fits into one or two PEBs.
> Because larger devices have larger erase blocks...

They do, but the eraseblock size grows much slower AFAICS.

-- 
Best Regards,
Artem Bityutskiy

Re: [RFC][PATCH 0/7] UBI checkpointing support

[Shmulik Ladkani]

On Thu, 08 Mar 2012 13:58:01 +0200 Artem Bityutskiy <dedekind1@gmail.com> wrote:
> To write the ubibis and to ubibis? Hmm... not sure.
> 
> To write the fastmap and to fastmap or decide to not fastmap because all
> PEBs within the first 64 have too high erasecounter? Sounds better IMO.

FWIW, fastmap sounds reasonable to me.

(aside from the fact that "fast" is the outcome of using the map,
whereas the map's definition is essentially a peb/leb map).

Anyways,

CONFIG_MTD_UBI_FASTMAP, ubi_find_fastmap(), ubi_scan_fastmap(),
ubi_read_fastmap(), ubi_update_fastmap() ...

all seem pretty explanatory IMO.

Using plain "map" (ubi_find_map, ubi_update_map) might also be an
option, however it might be less obvious.

Regards,
Shmulik