Skip to contentSkip to conversation

UBI: introduce sequential counter

PATCH In review Artem Bityutskiy 4 participants 11 messages Feb 8, 2007 – Feb 13, 2007

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 UBI: introduce sequential counter

From: Artem Bityutskiy <[email protected]>
Subject: [PATCH] UBI: introduce sequential counter

This patch introduces the global sequence counter - a 64-bit number which is increased every time a LEB is mapped to a PEB. When a VID header is written, the current global sequence counter value is saved there and the counter is increased. So it each VID header contains unique sequence number and for any 2 PBS we can say which one is newer. The counter is 64-bit and we assume it never overflows.

To store the sequance number, a new 'sqnum' field was added to the VID header. The padding area is used so it is compatible with older UBI versions.

Now, when the sequence counter is here, we do not need the 'leb_ver' field any longer but it was preserved for compatibility - so new UBI binaries understand old UBI versions and old UBI binaries understands new UBI images. But eventually we can remove the 'leb_ver' altogether.

Essentially, 'leb_ver' is the same as 'sqnum' but 'leb_ver' it is per-LEB. The following are advantages and motivation for 'sqnum':

1. it is not necessary to keep leb_ver field for in _each_ EBA table entry;
2. id does not overflow, so we do not have to do different perversions to make sure we handle this properly
3. in the wear-leveling code we can distinguish between LEBs which were written to long time ago and recently. Indeed, if the sequential number is close to the current one, it was written recently. This provides us an opportunity to distinguish between LEBs with static data vs. LEBs with not really static data (e.g., we have just recently taken a LEB with low erase counter and wrote data there). This is useful for WL.

---
 include/mtd/ubi-header.h |   71 ++++++++++++++++++++++++++++++++-------------
 1 files changed, 50 insertions(+), 21 deletions(-)
include/mtd/ubi-header.h +52 -23
Index: ubi-2.6.git/include/mtd/ubi-header.h
===================================================================
@@ -166,34 +166,61 @@ struct ubi_Ev_hdr {
  * %UBI_COMPAT_IGNORE, %UBI_COMPAT_PRESERVE, or %UBI_COMPAT_REJECT)
  * @vol_id: ID of this volume
  * @lnum: logical eraseblock number
- * @leb_ver: eraseblock copy number
  * @data_size: how many bytes of data this eraseblock contains
  * @used_ebs: total number of used logical eraseblocks in this volume
  * @data_pad: how many bytes at the end of this eraseblock are not used
  * @data_crc: CRC checksum of the data stored in this eraseblock
  * @padding1: reserved for future, zeroes
+ * @sqnum: sequence number
+ * @padding2: reserved for future, zeroes
  * @hdr_crc: volume identifier header CRC checksum
  *
- * The @leb_ver and the @copy_flag fields are used to distinguish between older
- * and newer copies of the logical eraseblock, as well as to guarantee
- * robustness against unclean reboots. As UBI erases logical eraseblocks
- * asynchronously, in background, it has to distinguish between older and newer
- * copies of logical eraseblocks. This is done using the @version field. On the
- * other hand, when UBI moves data of an eraseblock, its version is also
- * increased and the @copy_flag is set to 1. Additionally, when moving data of
- * eraseblocks, UBI calculates data CRC and stores it in the @data_crc field,
- * even for dynamic volumes.
- *
- * Thus, if there are 2 physical eraseblocks belonging to the logical
- * eraseblock (same volume ID and logical eraseblock number), UBI uses the
- * following algorithm to pick one of them. It first picks the one with larger
- * version (say, A). If @copy_flag is not set, then A is picked. If @copy_flag
- * is set, UBI checks the CRC of data of this physical eraseblock (@data_crc).
- * This is needed to ensure that the copying was finished. If the CRC is all
- * right, A is picked. If not, the older physical eraseblock is picked.
- *
- * Note, the @leb_ver field may overflow. Thus, if you have 2 versions X and Y,
- * then X > Y if abs(X-Y) < 0x7FFFFFFF, otherwise X < Y.
+ * The @sqnum is the value of the global sequence counter at the time when this
+ * VID header was created. The global sequence counter only grows and is
+ * incremented each time UBI writes a new VID header to the flash, i.e. when it
+ * maps a logical eraseblock to a new physical eraseblock. The global sequence
+ * counter is an unsigned 64-bit integer and we assume it never overflows. The
+ * @sqnum (sequence number) is used to distinguish between older and newer
+ * versions of logical eraseblocks.
+ *
+ * There are 2 situations when there may be more then one physical eraseblock
+ * corresponding to the same logical eraseblock, i.e., having the same @vol_id
+ * and @lnum values in the volume identifier header. Suppose we have a logical
+ * eraseblock L and it is mapped to the physical eraseblock P.
+ *
+ * 1. Because UBI may erase physical eraseblocks asynchronously, the following
+ * situation may take place: L is asynchronously erased, P is scheduled for
+ * erasure, L is written to, so mapped to another physical eraseblock P1, so P1
+ * is written to, then an unclean reboot happens. Result - there are 2 physical
+ * eraseblocks P and P1. But P1 has greater sequence number, so UBI pick P1.
+ *
+ * 2. From time to time UBI moves the the contents of logical eraseblocks to
+ * other physical eraseblocks for wear-leveling reasons. If, for example, UBI
+ * moves the contents of L from P to P1, and an unclean reboot happens before P
+ * is physically erased, there are two physical eraseblocks P and P1
+ * corresponding to L and UBI has to select one of them. The @ts field says
+ * which PEB is the original (obviously P will have lower @ts) and the copy.
+ * But it is not enough to select the physical eraseblock with the higher
+ * version, because the unclean reboot could have happen in the middle of the
+ * copying process, so the data in P is corrupted. It is also not enough to
+ * just select the physical eraseblock with lower version, because the data
+ * there may be old (consider a case if more data was added to P1 after the
+ * copying). Moreover, the unclean reboot may happen when the erasure of P was
+ * just started, so it may result in unstable P, which is "mostly" OK, but
+ * still has unstable data or is corrupted.
+ *
+ * UBI uses the @copy_flag field to indicate that this physical eraseblock is a
+ * copy of some other physical eraseblock. UBI also calculates data CRC when
+ * the data is moved and stores it at the @data_crc field of the copy (P1). So
+ * when there is a need to pick one physical eraseblock of two (P or P1), the
+ * @copy_flag of the newer one (P1) is examined. If it is cleared, the situation
+ * is simple and just the newer one is picked. If it is set, the data CRC of
+ * the copy (P1) is examined. If the CRC checksum is correct, this physical
+ * eraseblock is selected (P1). Otherwise the older one (P) is selected.
+ *
+ * Note, there is an obsolete @leb_ver field which was used instead of @ts in
+ * the past. But it is not used anymore and we keep it in order to be able to
+ * deal with old UBI images. It will be removed at some point.
  *
  * There are 2 sorts of volumes in UBI: user volumes and internal volumes.
  * Internal volumes are not seen from outside and are used for various internal
@@ -244,12 +271,14 @@ struct ubi_vid_hdr {
 	uint8_t compat;
 	ubi32_t vol_id;
 	ubi32_t lnum;
-	ubi32_t leb_ver;
+	ubi32_t leb_ver; /* obsolete, to be removed */
 	ubi32_t data_size;
 	ubi32_t used_ebs;
 	ubi32_t data_pad;
 	ubi32_t data_crc;
-	uint8_t padding1[24];
+	uint8_t padding1[4];
+	ubi64_t sqnum;
+	uint8_t padding2[12];
 	ubi32_t hdr_crc;
 } __attribute__ ((packed));
 
drivers/mtd/ubi/scan.h +20 -17
Index: ubi-2.6.git/drivers/mtd/ubi/scan.h
===================================================================
@@ -201,7 +201,7 @@ struct ubi_scan_volume {
  * @pnum: physical eraseblock number
  * @lnum: logical eraseblock number
  * @scrub: if this physical eraseblock needs scrubbing
- * @leb_ver: version of this logical eraseblock
+ * @sqnum: sequence number
  * @u.rb: link in the per-volume RB-tree of &struct ubi_scan_leb objects
  * @u.list: link in one of the eraseblock lists
  *
@@ -213,11 +213,12 @@ struct ubi_scan_leb {
 	int pnum;
 	int lnum;
 	int scrub;
-	uint32_t leb_ver;
+	uint64_t sqnum;
 	union {
 		struct rb_node rb;
 		struct list_head list;
 	} u;
+	uint32_t leb_ver; /* obsolete, to be removed */
 };
 
 /**
@@ -236,6 +237,7 @@ struct ubi_scan_leb {
  * @is_empty: a flag indicating whether the flash device is empty or not
  * @min_ec: the lowest found erase counter value
  * @max_ec: the highest found erase counter value
+ * @max_sn: the highest sequence number value
  * @mean_ec: mean erase counter value
  * @ec_sum: a temporary variable used when calculating @mean_ec
  * @ec_count: a temporary variable used when calculating @mean_ec
@@ -259,21 +261,22 @@ struct ubi_scan_leb {
  * erased are put to the @erase list.
  */
 struct ubi_scan_info {
-	struct rb_root volumes;  /* public  */
-	struct list_head corr;   /* public  */
-	struct list_head free;   /* public  */
-	struct list_head erase;  /* public  */
-	struct list_head alien;  /* public  */
-	int vols_found;          /* public  */
-	int highest_vol_id;      /* public  */
-	int bad_peb_count;       /* public  */
-	int alien_peb_count;     /* public  */
-	int is_empty;            /* public  */
-	int min_ec;              /* public  */
-	int max_ec;              /* public  */
-	int mean_ec;             /* public  */
-	int ec_sum;              /* private */
-	int ec_count;            /* private */
+	struct rb_root volumes; /* public  */
+	struct list_head corr;  /* public  */
+	struct list_head free;  /* public  */
+	struct list_head erase; /* public  */
+	struct list_head alien; /* public  */
+	int vols_found;         /* public  */
+	int highest_vol_id;     /* public  */
+	int bad_peb_count;      /* public  */
+	int alien_peb_count;    /* public  */
+	int is_empty;           /* public  */
+	int min_ec;             /* public  */
+	int max_ec;             /* public  */
+	uint64_t max_sqnum;     /* public  */
+	int mean_ec;            /* public  */
+	int ec_sum;             /* private */
+	int ec_count;           /* private */
 };
 
 #endif /* !__UBI_SCAN_H__ */
drivers/mtd/ubi/eba.c +43 -20

183 lines not on this page · raw message

drivers/mtd/ubi/eba.h +10 -3
Index: ubi-2.6.git/drivers/mtd/ubi/eba.h
===================================================================
@@ -287,13 +287,12 @@ void ubi_eba_close(const struct ubi_info
  * struct ubi_eba_tbl_rec - a record in the eraseblock association table.
  *
  * @pnum: physical eraseblock number
- * @leb_ver: logical eraseblock version
  *
  * This structure represents a record in the eraseblock association table.
  */
 struct ubi_eba_tbl_rec {
 	int pnum;
-	uint32_t leb_ver;
+	uint32_t leb_ver; /* obsolete, to be removed */
 };
 
 /**
@@ -335,7 +334,8 @@ struct ubi_eba_ltree_entry {
  * struct ubi_eba_info - UBI EBA unit description data structure.
  *
  * @eba_tbl: the eraseblock association table
- * @eba_tbl_lock: protects the EBA table
+ * @global_sq_cnt: global sequence counter
+ * @eba_tbl_lock: protects the EBA table and the global sequence counter
  * @ltree: the lock tree
  * @ltree_lock: protects the lock tree
  * @num_volumes: number of volumes mapped by the EBA table
@@ -347,9 +347,16 @@ struct ubi_eba_ltree_entry {
  * The lock tree is an RB-tree which refers all the currently locked logical
  * eraseblocks. The lock tree elements are &struct ubi_eba_ltree_entry objects.
  * They are indexed by (@vol_id,@lnum) pairs.
+ *
+ * The global sequence counter is incremented each time a logical eraseblock is
+ * mapped to a physical eraseblock and it is stored in the volume identifier
+ * header. This means that each VID header has a unique sequence number. The
+ * sequence number is only increased an we assume 64 bit is enough to never
+ * overflow.
  */
 struct ubi_eba_info {
 	struct ubi_eba_tbl_volume *eba_tbl; /* private */
+	uint64_t global_sq_cnt;             /* private */
 	spinlock_t eba_tbl_lock;            /* private */
 	struct rb_root ltree;               /* private */
 	spinlock_t ltree_lock;              /* private */
drivers/mtd/ubi/debug.c +5 -0
Index: ubi-2.6.git/drivers/mtd/ubi/debug.c
===================================================================
@@ -796,6 +796,8 @@ void ubi_dbg_dump_vid_hdr(const struct u
 	dump_msg("data_size %d",   ubi32_to_cpu(vid_hdr->data_size));
 	dump_msg("used_ebs  %d",   ubi32_to_cpu(vid_hdr->used_ebs));
 	dump_msg("data_pad  %d",   ubi32_to_cpu(vid_hdr->data_pad));
+	dump_msg("sqnum     %llu",
+		 (unsigned long long)ubi64_to_cpu(vid_hdr->sqnum));
 	dump_msg("hdr_crc   %08x", ubi32_to_cpu(vid_hdr->hdr_crc));
 	dump_msg("volume identifier header hexdump:");
 	ubi_dbg_hexdump_nolock(vid_hdr, UBI_VID_HDR_SIZE_CRC);
@@ -890,6 +892,9 @@ void ubi_dbg_dump_seb(const struct ubi_s
 	switch (type) {
 		case 0:
 			dump_msg("lnum     %d", seb->lnum);
+			dump_msg("scrub    %d", seb->scrub);
+			dump_msg("sqnum    %llu",
+				 (unsigned long long)seb->sqnum);
 			dump_msg("leb_ver  %u", seb->leb_ver);
 			break;
 		case 1:
#1 lore raw
Quoted 9 lines · Artem Bityutskiy

From: Artem Bityutskiy <[email protected]>
Subject: [PATCH] UBI: introduce sequential counter

This patch introduces the global sequence counter - a 64-bit number which is increased every time a LEB is mapped to a PEB. When a VID header is written, the current global sequence counter value is saved there and the counter is increased. So it each VID header contains unique sequence number and for any 2 PBS we can say which one is newer. The counter is 64-bit and we assume it never overflows.

Do image creation tools now how to understand how to increment the counter for each block in a binary image that would be flashed onto the card raw? Or do you leave the counter in all the VID headers as 0 for such images?

Quoted 4 lines

Now, when the sequence counter is here, we do not need the 'leb_ver' field any longer but it was preserved for compatibility - so new UBI binaries understand old UBI versions and old UBI binaries understands new UBI images. But eventually we can remove the 'leb_ver' altogether.

If a new kernel is run with an older UBI image, will it automatically start using the field and increment the counter values? (If yes, that makes my first question go away I think.)

Quoted 8 lines

Essentially, 'leb_ver' is the same as 'sqnum' but 'leb_ver' it is per-LEB. The following are advantages and motivation for 'sqnum':

1. it is not necessary to keep leb_ver field for in _each_ EBA table entry;
2. id does not overflow, so we do not have to do different perversions to make sure we handle this properly
3. in the wear-leveling code we can distinguish between LEBs which were written to long time ago and recently. Indeed, if the sequential number

No you can't. You cannot determine time and rate from a simple counter number. All you can determine is that LEB N is older than LEB M. It could be older by 40 seconds, or older by 5 years.

Quoted 4 lines

is close to the current one, it was written recently. This provides us an opportunity to distinguish between LEBs with static data vs. LEBs with not really static data (e.g., we have just recently taken a LEB with low erase counter and wrote data there). This is useful for WL.

Yes, this might help wear-leveling. But if the data is used, I would recommend being very conservative about using the counter value to distinguish between "static" and "non-static" data.

Quoted 10 lines
---
 include/mtd/ubi-header.h |   71 ++++++++++++++++++++++++++++++++-------------
 1 files changed, 50 insertions(+), 21 deletions(-)

Index: ubi-2.6.git/include/mtd/ubi-header.h
===================================================================

include/mtd/ubi-header.h struct ubi_Ev_hdr { · line 169

Quoted 4 lines
include/mtd/ubi-header.h +0 -1
@@ -166,34 +166,61 @@ struct ubi_Ev_hdr {
  * %UBI_COMPAT_IGNORE, %UBI_COMPAT_PRESERVE, or %UBI_COMPAT_REJECT)
  * @vol_id: ID of this volume
  * @lnum: logical eraseblock number
- * @leb_ver: eraseblock copy number

Please don't remove this until the member is actually removed.

Quoted 37 lines
include/mtd/ubi-header.h +10 -20
  * @data_size: how many bytes of data this eraseblock contains
  * @used_ebs: total number of used logical eraseblocks in this volume
  * @data_pad: how many bytes at the end of this eraseblock are not used
  * @data_crc: CRC checksum of the data stored in this eraseblock
  * @padding1: reserved for future, zeroes
+ * @sqnum: sequence number
+ * @padding2: reserved for future, zeroes
  * @hdr_crc: volume identifier header CRC checksum
  *
- * The @leb_ver and the @copy_flag fields are used to distinguish between older
- * and newer copies of the logical eraseblock, as well as to guarantee
- * robustness against unclean reboots. As UBI erases logical eraseblocks
- * asynchronously, in background, it has to distinguish between older and newer
- * copies of logical eraseblocks. This is done using the @version field. On the
- * other hand, when UBI moves data of an eraseblock, its version is also
- * increased and the @copy_flag is set to 1. Additionally, when moving data of
- * eraseblocks, UBI calculates data CRC and stores it in the @data_crc field,
- * even for dynamic volumes.
- *
- * Thus, if there are 2 physical eraseblocks belonging to the logical
- * eraseblock (same volume ID and logical eraseblock number), UBI uses the
- * following algorithm to pick one of them. It first picks the one with larger
- * version (say, A). If @copy_flag is not set, then A is picked. If @copy_flag
- * is set, UBI checks the CRC of data of this physical eraseblock (@data_crc).
- * This is needed to ensure that the copying was finished. If the CRC is all
- * right, A is picked. If not, the older physical eraseblock is picked.
- *
- * Note, the @leb_ver field may overflow. Thus, if you have 2 versions X and Y,
- * then X > Y if abs(X-Y) < 0x7FFFFFFF, otherwise X < Y.
+ * The @sqnum is the value of the global sequence counter at the time when this
+ * VID header was created. The global sequence counter only grows and is
+ * incremented each time UBI writes a new VID header to the flash, i.e. when it
+ * maps a logical eraseblock to a new physical eraseblock. The global sequence
+ * counter is an unsigned 64-bit integer and we assume it never overflows. The
+ * @sqnum (sequence number) is used to distinguish between older and newer
+ * versions of logical eraseblocks.
+ *

include/mtd/ubi-header.h struct ubi_Ev_hdr { · line 195

Quoted 10 lines
include/mtd/ubi-header.h +10 -0
+ * There are 2 situations when there may be more then one physical eraseblock
+ * corresponding to the same logical eraseblock, i.e., having the same @vol_id
+ * and @lnum values in the volume identifier header. Suppose we have a logical
+ * eraseblock L and it is mapped to the physical eraseblock P.
+ *
+ * 1. Because UBI may erase physical eraseblocks asynchronously, the following
+ * situation may take place: L is asynchronously erased, P is scheduled for
+ * erasure, L is written to, so mapped to another physical eraseblock P1, so P1
+ * is written to, then an unclean reboot happens. Result - there are 2 physical
+ * eraseblocks P and P1. But P1 has greater sequence number, so UBI pick P1.

"... so UBI picks P1"

include/mtd/ubi-header.h struct ubi_Ev_hdr { · line 202

Quoted 7 lines
include/mtd/ubi-header.h +7 -0
+ *
+ * 2. From time to time UBI moves the the contents of logical eraseblocks to
+ * other physical eraseblocks for wear-leveling reasons. If, for example, UBI
+ * moves the contents of L from P to P1, and an unclean reboot happens before P
+ * is physically erased, there are two physical eraseblocks P and P1
+ * corresponding to L and UBI has to select one of them. The @ts field says
+ * which PEB is the original (obviously P will have lower @ts) and the copy.

What is @ts?

Quoted 9 lines
include/mtd/ubi-header.h +9 -0
+ * But it is not enough to select the physical eraseblock with the higher
+ * version, because the unclean reboot could have happen in the middle of the
+ * copying process, so the data in P is corrupted. It is also not enough to
+ * just select the physical eraseblock with lower version, because the data
+ * there may be old (consider a case if more data was added to P1 after the
+ * copying). Moreover, the unclean reboot may happen when the erasure of P was
+ * just started, so it may result in unstable P, which is "mostly" OK, but
+ * still has unstable data or is corrupted.
+ *

include/mtd/ubi-header.h struct ubi_Ev_hdr { · line 221

Quoted 10 lines
include/mtd/ubi-header.h +10 -0
+ * UBI uses the @copy_flag field to indicate that this physical eraseblock is a
+ * copy of some other physical eraseblock. UBI also calculates data CRC when
+ * the data is moved and stores it at the @data_crc field of the copy (P1). So
+ * when there is a need to pick one physical eraseblock of two (P or P1), the
+ * @copy_flag of the newer one (P1) is examined. If it is cleared, the situation
+ * is simple and just the newer one is picked. If it is set, the data CRC of
+ * the copy (P1) is examined. If the CRC checksum is correct, this physical
+ * eraseblock is selected (P1). Otherwise the older one (P) is selected.
+ *
+ * Note, there is an obsolete @leb_ver field which was used instead of @ts in

Again with @ts... I think you mean @seqnum?

Quoted 9 lines
include/mtd/ubi-header.h +2 -0
+ * the past. But it is not used anymore and we keep it in order to be able to
+ * deal with old UBI images. It will be removed at some point.
  *
  * There are 2 sorts of volumes in UBI: user volumes and internal volumes.
  * Internal volumes are not seen from outside and are used for various internal
@@ -244,12 +271,14 @@ struct ubi_vid_hdr {
 	uint8_t compat;
 	ubi32_t vol_id;
 	ubi32_t lnum;

include/mtd/ubi-header.h struct ubi_vid_hdr { · line 281

Quoted 10 lines
include/mtd/ubi-header.h +4 -2
-	ubi32_t leb_ver;
+	ubi32_t leb_ver; /* obsolete, to be removed */
 	ubi32_t data_size;
 	ubi32_t used_ebs;
 	ubi32_t data_pad;
 	ubi32_t data_crc;
-	uint8_t padding1[24];
+	uint8_t padding1[4];
+	ubi64_t sqnum;
+	uint8_t padding2[12];

Can't you add the field at the bottom before hdr_crc so you don't have split padding like that?

josh

#2 lore raw
Quoted 5 lines · Josh Boyer
Quoted 3 lines

3. in the wear-leveling code we can distinguish between LEBs which were written to long time ago and recently. Indeed, if the sequential number

No you can't.

Yes, you can. :)

Quoted 3 lines

You cannot determine time and rate from a simple counter number. All you can determine is that LEB N is older than LEB M. It could be older by 40 seconds, or older by 5 years.

This is an unusual way of looking at time, but it is perfectly valid. Whether an LEB is 40 seconds or 40 million years old is completely inconsequential. What matters is not how much wall-clock time has passed, but how much other data was written. "Bytes of data written" is a valid unit of time, really, and a very useful one. Esp. for wear leveling decisions.

Congratulations, Artem!

Quoted 3 lines

Yes, this might help wear-leveling. But if the data is used, I would recommend being very conservative about using the counter value to distinguish between "static" and "non-static" data.

Having a hard distinction between static and non-static data sounds bad, agreed. What this can (and will, in LogFS) be used for is not doing GC on new data, if possible. The newer your data, the higher the chances of it becoming obsolete in the near future anyway. So letting it sit until it ages a little makes sense.

UBI is a bit coarser, as it has no clue about the LEB contents, but a similar strategy may still make sense.

Jörn

Signature · 2 lines
tglx1 thinks that joern should get a (TM) for "Thinking Is Hard"
-- Thomas Gleixner
#3 lore raw
Quoted 6 lines · Jörn Engel

This is an unusual way of looking at time, but it is perfectly valid. Whether an LEB is 40 seconds or 40 million years old is completely inconsequential. What matters is not how much wall-clock time has passed, but how much other data was written. "Bytes of data written" is a valid unit of time, really, and a very useful one. Esp. for wear leveling decisions.

Yes, and the sequential counter is basically how many eraseblock were written to, which is close.

Signature · 2 lines
Best regards,
Artem Bityutskiy (Битюцкий Артём)
#4 lore raw
In reply to Josh Boyer

Hello Josh,

Quoted 4 lines · Josh Boyer

Do image creation tools now how to understand how to increment the counter for each block in a binary image that would be flashed onto the card raw? Or do you leave the counter in all the VID headers as 0 for such images?

They don't and they should be updated. But yes, they write zeroes to the sqnum and UBI is happy.

Quoted 3 lines

If a new kernel is run with an older UBI image, will it automatically start using the field and increment the counter values? (If yes, that makes my first question go away I think.)

Yes. Both are used, incremented, etc.

Quoted 3 lines

No you can't. You cannot determine time and rate from a simple counter number. All you can determine is that LEB N is older than LEB M. It could be older by 40 seconds, or older by 5 years.

Here is an example:

I know the number of PEBs on the media N and I may introduce an empirical criteria of oldness M = F(N). For example, M=kN, k is a natural number. Its a subject for an investigation.

I know the highest sqnum (= the current global sequence counter) H, and any LEB with sqnum=S is treated it as old if S < H-M, and as "fresh" otherwise.

When I move a PEB with low EC, and I need to pick the target PEB (T), where I move the data to. I pick T with the highest EC if the data is old, and I pick T with an average EC if the data is fresh.

Quoted 9 lines
Quoted 5 lines

is close to the current one, it was written recently. This provides us an opportunity to distinguish between LEBs with static data vs. LEBs with not really static data (e.g., we have just recently taken a LEB with low erase counter and wrote data there). This is useful for WL.

Yes, this might help wear-leveling. But if the data is used, I would recommend being very conservative about using the counter value to distinguish between "static" and "non-static" data.

Yes, this has to be carefully thought of.

Quoted 3 lines
Quoted 1 line

+ * eraseblocks P and P1. But P1 has greater sequence number, so UBI pick P1.

"... so UBI picks P1"

Yup, Tx.

Quoted 3 lines
Quoted 1 line

+ * which PEB is the original (obviously P will have lower @ts) and the copy.

What is @ts?

I first wanted to call it "time stamp", but store sequence number. Leftovers, tx.

Quoted 3 lines
Quoted 1 line

+ * Note, there is an obsolete @leb_ver field which was used instead of @ts in

Again with @ts... I think you mean @seqnum?

Yup, tx.

Quoted 8 lines

include/mtd/ubi-header.h struct ubi_vid_hdr { · line 281

Quoted 5 lines
include/mtd/ubi-header.h +3 -1
 	ubi32_t data_crc;
-	uint8_t padding1[24];
+	uint8_t padding1[4];
+	ubi64_t sqnum;
+	uint8_t padding2[12];

Can't you add the field at the bottom before hdr_crc so you don't have split padding like that?

No, it is 64-bit and I want it to be aligned.

Signature · 2 lines
Best regards,
Artem Bityutskiy (Битюцкий Артём)
#5 lore raw
Quoted 10 lines · Artem Bityutskiy

Hello Josh,

Quoted 4 lines · Josh Boyer

Do image creation tools now how to understand how to increment the counter for each block in a binary image that would be flashed onto the card raw? Or do you leave the counter in all the VID headers as 0 for such images?

They don't and they should be updated. But yes, they write zeroes to the sqnum and UBI is happy.

If writing zeroes to the field for all LEBs is valid, then I don't think the tools need updating. At least not the image creation tools. We've already declared the padding fields to be zero filled.

The unubi tool will need updating though.

Quoted 6 lines

Here is an example:

I know the number of PEBs on the media N and I may introduce an empirical criteria of oldness M = F(N). For example, M=kN, k is a natural number. Its a subject for an investigation.

Quoted 7 lines

I know the highest sqnum (= the current global sequence counter) H, and any LEB with sqnum=S is treated it as old if S < H-M, and as "fresh" otherwise.

When I move a PEB with low EC, and I need to pick the target PEB (T), where I move the data to. I pick T with the highest EC if the data is old, and I pick T with an average EC if the data is fresh.

If you replace "old" with "stale" I agree. My stupid english thinking brain equates "old" with the passage of time, and that isn't what sqnum is tracking. It is valid to use stale though.

Quoted 10 lines
Quoted 8 lines

include/mtd/ubi-header.h struct ubi_vid_hdr { · line 281

Quoted 5 lines
include/mtd/ubi-header.h +3 -1
 	ubi32_t data_crc;
-	uint8_t padding1[24];
+	uint8_t padding1[4];
+	ubi64_t sqnum;
+	uint8_t padding2[12];

Can't you add the field at the bottom before hdr_crc so you don't have split padding like that?

No, it is 64-bit and I want it to be aligned.

Ah, aligned within on a 64-bit boundary... I see. Looks odd, but ok.

josh

#6 lore raw
Quoted 5 lines · Josh Boyer

If writing zeroes to the field for all LEBs is valid, then I don't think the tools need updating. At least not the image creation tools. We've already declared the padding fields to be zero filled.

The unubi tool will need updating though.

They should be updated because they should generate unique numbers to the sqnum field, do not use old 'leb_ver' stuff, because leb_ver stuff will go away eventually, say, in a year. Also boot-loaders should be eventually updated.

Quoted 7 lines
Quoted 3 lines

When I move a PEB with low EC, and I need to pick the target PEB (T), where I move the data to. I pick T with the highest EC if the data is old, and I pick T with an average EC if the data is fresh.

If you replace "old" with "stale" I agree. My stupid english thinking brain equates "old" with the passage of time, and that isn't what sqnum is tracking. It is valid to use stale though.

Just treat the steadily increasing sequential number as a kind of UBI time, then my terminology start making sense.

Quoted 1 line

Ah, aligned within on a 64-bit boundary... I see. Looks odd, but ok.

Nothing odd, actually. I do not want to deal with unaligned addresses.

Signature · 2 lines
Best regards,
Artem Bityutskiy (Битюцкий Артём)
#7 lore raw
Quoted 11 lines · Artem Bityutskiy
Quoted 5 lines · Josh Boyer

If writing zeroes to the field for all LEBs is valid, then I don't think the tools need updating. At least not the image creation tools. We've already declared the padding fields to be zero filled.

The unubi tool will need updating though.

They should be updated because they should generate unique numbers to the sqnum field, do not use old 'leb_ver' stuff, because leb_ver stuff will go away eventually, say, in a year. Also boot-loaders should be eventually updated.

Having them generate a unique number for seqnum isn't _required_ though right? UBI will see them all as 0 and still work if I understand correctly.

I agree the tools _should_ be changed. I just want to make sure that it's not a requirement before this patch goes in.

josh

#8 lore raw
Quoted 3 lines · Josh Boyer

Having them generate a unique number for seqnum isn't _required_ though right? UBI will see them all as 0 and still work if I understand correctly.

Yes. I is not required to be done immediately. But in order to be able to smoothly remove legacy stuff, it should be done better sooner then later.

Signature · 2 lines
Best regards,
Artem Bityutskiy (Битюцкий Артём)
#9 lore raw
In reply to Artem Bityutskiy

Hi Artem,

Quoted 4 lines · Artem Bityutskiy

They should be updated because they should generate unique numbers to the sqnum field, do not use old 'leb_ver' stuff, because leb_ver stuff will go away eventually, say, in a year. Also boot-loaders should be eventually updated.

The 64bit nature could complicate the compare code a little, and we are limited to those 4KiB as you know. Mhm. It should be than a comparission of a 64bit value instead of a 32bit one.

For us it is dangerous to exchange that code, since it is in NAND block 0 and where an interrupted write process would kill our system. It would be good to keep the old field for backward-compatibility reasons, so that we do not have to update this piece of the boot-code.

Frank

#10 lore raw
Quoted 3 lines · Frank Haverkamp

The 64bit nature could complicate the compare code a little, and we are limited to those 4KiB as you know. Mhm. It should be than a comparission of a 64bit value instead of a 32bit one.

With current 32 bit versions you have to take care of overflow. For example, version 1 is newer then version 0xFFFFFFFA. I doubt comparing 2 64-bit variable with _no_ need to look it overflow is more difficult and takes more code.

These 32 bit overflowing counters really introduce mess.

Signature · 2 lines
Best regards,
Artem Bityutskiy (Битюцкий Артём)