ubi: suspicious calculation in 'ubi_wl_get_peb'

ubi: suspicious calculation in 'ubi_wl_get_peb'

[Shmulik Ladkani]

Hi,

Sorry for a long post - this issue requires some detailed background.

It looks like a calculation within 'ubi_wl_get_peb' involved in
picking a candidate PEB is incorrect.

The function 'find_wl_entry(rb_root *root, int max)' finds a
wear-leveling entry closest to a certain erase counter.

The parameter 'max' is documented as "highest possible erase counter",
however it is actually "diff from first entry" - since initially, the
funtion adds first entry's EC to the given 'max':

	e = rb_entry(rb_first(root), struct ubi_wl_entry, u.rb);
	max += e->ec;

Almost all calls to 'find_wl_entry' follow the (undocumented)
convention, providing "diff from first" argument (where the absolute
'max' value seeked is calculated *internally* by 'find_wl_entry').
E.g. 4 of 5 calls are of the pattern:

	e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF);

However, there is one call where the caller seems to provide an actual
absolute "max" value, instead of a "diff from first".
The call is within 'ubi_wl_get_peb', quote:

	case UBI_UNKNOWN:
		/*
		 * For unknown data we pick a physical eraseblock with medium
		 * erase counter. But we by no means can pick a physical
		 * eraseblock with erase counter greater or equivalent than the
		 * lowest erase counter plus %WL_FREE_MAX_DIFF.
		 */
		first = rb_entry(rb_first(&ubi->free), struct ubi_wl_entry,
					u.rb);
		last = rb_entry(rb_last(&ubi->free), struct ubi_wl_entry, u.rb);

		if (last->ec - first->ec < WL_FREE_MAX_DIFF)
			e = rb_entry(ubi->free.rb_node,
					struct ubi_wl_entry, u.rb);
		else {
			medium_ec = (first->ec + WL_FREE_MAX_DIFF)/2;
			e = find_wl_entry(&ubi->free, medium_ec);
		}
		break;

Note calculation of 'medium_ec' - it does no seem as a "diff" value.
The *actual* resulting seeked EC is approximately 1.5*First + Diff/2.
Is it the intended behavior? it does not seem to fit the remark.

Deducting from the "last->ec - first->ec < WL_FREE_MAX_DIFF" condition,
it looks like it should have been:

-			e = find_wl_entry(&ubi->free, medium_ec);
+			e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF/2)

Did I get something wrong?

Looking forward for any comments.

Regards,
Shmulik

Re: ubi: suspicious calculation in 'ubi_wl_get_peb'

[Artem Bityutskiy]

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

On Fri, 2012-02-17 at 15:38 +0200, Shmulik Ladkani wrote:
> -			e = find_wl_entry(&ubi->free, medium_ec);
> +			e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF/2)
> 
> Did I get something wrong?

Yeah, I think you are right. Now I am completely convinced we should
remove this "short/long-term" stuff because this did even work
correctly :-)

CCint Richard - I happened to suggest the removal to him earlier today.

What do you think about these untested fixes (also attached):

From: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
Date: Wed, 7 Mar 2012 18:56:29 +0200
Subject: [PATCH 1/2] UBI: fix documentation and improve readability

The "max" parameter of 'find_wl_entry()' was documented incorrectly and
it actually means the maximum possible difference, not the maximum absolute
value. Rename it to "diff" instead, and amend the documentation.

Reported-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>
Signed-off-by: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
---
 drivers/mtd/ubi/wl.c |    9 +++++----
 1 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 0696e36..10d7b98 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -350,18 +350,19 @@ static void prot_queue_add(struct ubi_device *ubi, struct ubi_wl_entry *e)
 /**
  * find_wl_entry - find wear-leveling entry closest to certain erase counter.
  * @root: the RB-tree where to look for
- * @max: highest possible erase counter
+ * @diff: highest possible erase counter difference
  *
  * This function looks for a wear leveling entry with erase counter closest to
- * @max and less than @max.
+ * min + @diff, where min is the currently smallest erase counter.
  */
-static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int max)
+static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
 {
 	struct rb_node *p;
 	struct ubi_wl_entry *e;
+	int max;
 
 	e = rb_entry(rb_first(root), struct ubi_wl_entry, u.rb);
-	max += e->ec;
+	max = e->ec + diff;
 
 	p = root->rb_node;
 	while (p) {
-- 
1.7.9.1

From: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
Date: Wed, 7 Mar 2012 19:08:36 +0200
Subject: [PATCH 2/2] UBI: fix eraseblock picking criteria

The 'find_wl_entry()' function expects the maximum difference as the second
argument, not the maximum absolute value. So the "unknown" eraseblock picking
was incorrect, as Shmulik Ladkani spotted. This patch fixes the issue.

Reported-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>
Signed-off-by: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
Cc: stable@kernel.org
---
 drivers/mtd/ubi/wl.c |    8 +++-----
 1 files changed, 3 insertions(+), 5 deletions(-)

diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 10d7b98..051cb3a 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -390,7 +390,7 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
  */
 int ubi_wl_get_peb(struct ubi_device *ubi, int dtype)
 {
-	int err, medium_ec;
+	int err;
 	struct ubi_wl_entry *e, *first, *last;
 
 	ubi_assert(dtype == UBI_LONGTERM || dtype == UBI_SHORTTERM ||
@@ -437,10 +437,8 @@ retry:
 		if (last->ec - first->ec < WL_FREE_MAX_DIFF)
 			e = rb_entry(ubi->free.rb_node,
 					struct ubi_wl_entry, u.rb);
-		else {
-			medium_ec = (first->ec + WL_FREE_MAX_DIFF)/2;
-			e = find_wl_entry(&ubi->free, medium_ec);
-		}
+		else
+			e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF/2);
 		break;
 	case UBI_SHORTTERM:
 		/*
-- 
1.7.9.1

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: 0001-UBI-fix-documentation-and-improve-readability.patch --]
[-- Type: text/x-patch, Size: 1773 bytes --]

>From 369897e5f49052f78dea2f02a498390cd2459d43 Mon Sep 17 00:00:00 2001
Message-Id: <369897e5f49052f78dea2f02a498390cd2459d43.1331140361.git.artem.bityutskiy@linux.intel.com>
From: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
Date: Wed, 7 Mar 2012 18:56:29 +0200
Subject: [PATCH 1/2] UBI: fix documentation and improve readability

The "max" parameter of 'find_wl_entry()' was documented incorrectly and
it actually means the maximum possible difference, not the maximum absolute
value. Rename it to "diff" instead, and amend the documentation.

Reported-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>
Signed-off-by: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
---
 drivers/mtd/ubi/wl.c |    9 +++++----
 1 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 0696e36..10d7b98 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -350,18 +350,19 @@ static void prot_queue_add(struct ubi_device *ubi, struct ubi_wl_entry *e)
 /**
  * find_wl_entry - find wear-leveling entry closest to certain erase counter.
  * @root: the RB-tree where to look for
- * @max: highest possible erase counter
+ * @diff: highest possible erase counter difference
  *
  * This function looks for a wear leveling entry with erase counter closest to
- * @max and less than @max.
+ * min + @diff, where min is the currently smallest erase counter.
  */
-static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int max)
+static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
 {
 	struct rb_node *p;
 	struct ubi_wl_entry *e;
+	int max;
 
 	e = rb_entry(rb_first(root), struct ubi_wl_entry, u.rb);
-	max += e->ec;
+	max = e->ec + diff;
 
 	p = root->rb_node;
 	while (p) {
-- 
1.7.9.1


[-- Attachment #3: 0002-UBI-fix-eraseblock-picking-criteria.patch --]
[-- Type: text/x-patch, Size: 1810 bytes --]

>From b874a16e244d21ce2e6b7d1ab81538f5b0a5968d Mon Sep 17 00:00:00 2001
Message-Id: <b874a16e244d21ce2e6b7d1ab81538f5b0a5968d.1331140361.git.artem.bityutskiy@linux.intel.com>
In-Reply-To: <369897e5f49052f78dea2f02a498390cd2459d43.1331140361.git.artem.bityutskiy@linux.intel.com>
References: <369897e5f49052f78dea2f02a498390cd2459d43.1331140361.git.artem.bityutskiy@linux.intel.com>
From: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
Date: Wed, 7 Mar 2012 19:08:36 +0200
Subject: [PATCH 2/2] UBI: fix eraseblock picking criteria

The 'find_wl_entry()' function expects the maximum difference as the second
argument, not the maximum absolute value. So the "unknown" eraseblock picking
was incorrect, as Shmulik Ladkani spotted. This patch fixes the issue.

Reported-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>
Signed-off-by: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
Cc: stable@kernel.org
---
 drivers/mtd/ubi/wl.c |    8 +++-----
 1 files changed, 3 insertions(+), 5 deletions(-)

diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 10d7b98..051cb3a 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -390,7 +390,7 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
  */
 int ubi_wl_get_peb(struct ubi_device *ubi, int dtype)
 {
-	int err, medium_ec;
+	int err;
 	struct ubi_wl_entry *e, *first, *last;
 
 	ubi_assert(dtype == UBI_LONGTERM || dtype == UBI_SHORTTERM ||
@@ -437,10 +437,8 @@ retry:
 		if (last->ec - first->ec < WL_FREE_MAX_DIFF)
 			e = rb_entry(ubi->free.rb_node,
 					struct ubi_wl_entry, u.rb);
-		else {
-			medium_ec = (first->ec + WL_FREE_MAX_DIFF)/2;
-			e = find_wl_entry(&ubi->free, medium_ec);
-		}
+		else
+			e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF/2);
 		break;
 	case UBI_SHORTTERM:
 		/*
-- 
1.7.9.1

Re: ubi: suspicious calculation in 'ubi_wl_get_peb'

[Artem Bityutskiy]

On Wed, 2012-03-07 at 19:20 +0200, Artem Bityutskiy wrote:
> On Fri, 2012-02-17 at 15:38 +0200, Shmulik Ladkani wrote:
> > -			e = find_wl_entry(&ubi->free, medium_ec);
> > +			e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF/2)
> > 
> > Did I get something wrong?
> 
> Yeah, I think you are right. Now I am completely convinced we should
> remove this "short/long-term" stuff because this did even work
> correctly :-)

Sorry, s/did even/did NOT even/

-- 
Best Regards,
Artem Bityutskiy

Re: ubi: suspicious calculation in 'ubi_wl_get_peb'

[Shmulik Ladkani]

On Wed, 07 Mar 2012 19:20:08 +0200 Artem Bityutskiy <dedekind1@gmail.com> wrote:
> On Fri, 2012-02-17 at 15:38 +0200, Shmulik Ladkani wrote:
> > -			e = find_wl_entry(&ubi->free, medium_ec);
> > +			e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF/2)
> > 
> > Did I get something wrong?
> 
> Yeah, I think you are right. Now I am completely convinced we should
> remove this "short/long-term" stuff because this did even work
> correctly :-)

I would not jump into this conclusion just yet :-)

Note the bug affects UBI_UNKNOWN requests, which are supposed to be
general-purpose 'ubi_wl_get_peb' requests... troubling...

UBI_LONGTERM/UBI_SHORTTERM seem to work just fine.

Re: ubi: suspicious calculation in 'ubi_wl_get_peb'

[Artem Bityutskiy]

On Wed, 2012-03-07 at 22:08 +0200, Shmulik Ladkani wrote:
> On Wed, 07 Mar 2012 19:20:08 +0200 Artem Bityutskiy <dedekind1@gmail.com> wrote:
> > On Fri, 2012-02-17 at 15:38 +0200, Shmulik Ladkani wrote:
> > > -			e = find_wl_entry(&ubi->free, medium_ec);
> > > +			e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF/2)
> > > 
> > > Did I get something wrong?
> > 
> > Yeah, I think you are right. Now I am completely convinced we should
> > remove this "short/long-term" stuff because this did even work
> > correctly :-)
> 
> I would not jump into this conclusion just yet :-)
> 
> Note the bug affects UBI_UNKNOWN requests, which are supposed to be
> general-purpose 'ubi_wl_get_peb' requests... troubling...
> 
> UBI_LONGTERM/UBI_SHORTTERM seem to work just fine.

UBI_UNKNOWN is used most of the time. And long/short are kind of
optimizations. UBIFS uses them but these are more like guesses and UBIFS
my tell the LEB is short term but it may easily be long term. And this
is not much of an optimization.

-- 
Best Regards,
Artem Bityutskiy

Re: ubi: suspicious calculation in 'ubi_wl_get_peb'

[Shmulik Ladkani]

> From: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
> Date: Wed, 7 Mar 2012 18:56:29 +0200
> Subject: [PATCH 1/2] UBI: fix documentation and improve readability
> 
> The "max" parameter of 'find_wl_entry()' was documented incorrectly and
> it actually means the maximum possible difference, not the maximum absolute

maybe better:
it actually means the maximum possible difference from smallest erase counter

> value. Rename it to "diff" instead, and amend the documentation.
> 
> Reported-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>
> Signed-off-by: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
> ---
>  drivers/mtd/ubi/wl.c |    9 +++++----
>  1 files changed, 5 insertions(+), 4 deletions(-)
> 
> diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
> index 0696e36..10d7b98 100644
> --- a/drivers/mtd/ubi/wl.c
> +++ b/drivers/mtd/ubi/wl.c
> @@ -350,18 +350,19 @@ static void prot_queue_add(struct ubi_device *ubi, struct ubi_wl_entry *e)
>  /**
>   * find_wl_entry - find wear-leveling entry closest to certain erase counter.
>   * @root: the RB-tree where to look for
> - * @max: highest possible erase counter
> + * @diff: highest possible erase counter difference

again (add: "from smallest...") - unless you think its cumbersome

>   *
>   * This function looks for a wear leveling entry with erase counter closest to
> - * @max and less than @max.
> + * min + @diff, where min is the currently smallest erase counter.
>   */
> -static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int max)
> +static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
>  {
>  	struct rb_node *p;
>  	struct ubi_wl_entry *e;
> +	int max;
>  
>  	e = rb_entry(rb_first(root), struct ubi_wl_entry, u.rb);
> -	max += e->ec;
> +	max = e->ec + diff;
>  
>  	p = root->rb_node;
>  	while (p) {

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

Re: ubi: suspicious calculation in 'ubi_wl_get_peb'

[Shmulik Ladkani]

On Wed, 07 Mar 2012 19:20:08 +0200 Artem Bityutskiy <dedekind1@gmail.com> wrote:
> From: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
> Date: Wed, 7 Mar 2012 19:08:36 +0200
> Subject: [PATCH 2/2] UBI: fix eraseblock picking criteria
> 
> The 'find_wl_entry()' function expects the maximum difference as the second
> argument, not the maximum absolute value. So the "unknown" eraseblock picking
> was incorrect, as Shmulik Ladkani spotted. This patch fixes the issue.
> 
> Reported-by: Shmulik Ladkani <shmulik.ladkani@gmail.com>
> Signed-off-by: Artem Bityutskiy <artem.bityutskiy@linux.intel.com>
> Cc: stable@kernel.org
> ---
>  drivers/mtd/ubi/wl.c |    8 +++-----
>  1 files changed, 3 insertions(+), 5 deletions(-)
> 
> diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
> index 10d7b98..051cb3a 100644
> --- a/drivers/mtd/ubi/wl.c
> +++ b/drivers/mtd/ubi/wl.c
> @@ -390,7 +390,7 @@ static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int diff)
>   */
>  int ubi_wl_get_peb(struct ubi_device *ubi, int dtype)
>  {
> -	int err, medium_ec;
> +	int err;
>  	struct ubi_wl_entry *e, *first, *last;
>  
>  	ubi_assert(dtype == UBI_LONGTERM || dtype == UBI_SHORTTERM ||
> @@ -437,10 +437,8 @@ retry:
>  		if (last->ec - first->ec < WL_FREE_MAX_DIFF)
>  			e = rb_entry(ubi->free.rb_node,
>  					struct ubi_wl_entry, u.rb);
> -		else {
> -			medium_ec = (first->ec + WL_FREE_MAX_DIFF)/2;
> -			e = find_wl_entry(&ubi->free, medium_ec);
> -		}
> +		else
> +			e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF/2);
>  		break;
>  	case UBI_SHORTTERM:
>  		/*

Unfortunately, currently unable to give it a runtime test, sorry.

Also, I suspect the remark:
		 * erase counter. But we by no means can pick a physical
		 * eraseblock with erase counter greater or equivalent than the
		 * lowest erase counter plus %WL_FREE_MAX_DIFF.

Should be fixed as well:
-		 * lowest erase counter plus %WL_FREE_MAX_DIFF.
+		 * lowest erase counter plus %WL_FREE_MAX_DIFF/2.

Other than that, looks correct.

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