[PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits

[PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits

[Rasmus Villemoes]

Ensure that lcm(a,b) returns the mathematically correct result,
provided it fits in an unsigned long. The current version returns
garbage if a*b overflows, even if the final result would fit.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/lcm.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/lcm.c b/lib/lcm.c
index b9c8de461e9e..01b3aa922dda 100644
--- a/lib/lcm.c
+++ b/lib/lcm.c
@@ -7,7 +7,7 @@
 unsigned long lcm(unsigned long a, unsigned long b)
 {
 	if (a && b)
-		return (a * b) / gcd(a, b);
+		return (a / gcd(a, b)) * b;
 	else if (b)
 		return b;
 
-- 
2.1.3

[PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n

[Rasmus Villemoes]

Return the mathematically correct answer when an argument is 0.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/lcm.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/lib/lcm.c b/lib/lcm.c
index 01b3aa922dda..51cc6b13cd52 100644
--- a/lib/lcm.c
+++ b/lib/lcm.c
@@ -8,9 +8,7 @@ unsigned long lcm(unsigned long a, unsigned long b)
 {
 	if (a && b)
 		return (a / gcd(a, b)) * b;
-	else if (b)
-		return b;
-
-	return a;
+	else
+		return 0;
 }
 EXPORT_SYMBOL_GPL(lcm);
-- 
2.1.3

Re: [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n

[Mike Snitzer]

On Tue, Dec 9, 2014 at 4:03 PM, Rasmus Villemoes
<linux@rasmusvillemoes.dk> wrote:
> Return the mathematically correct answer when an argument is 0.
>
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
>  lib/lcm.c | 6 ++----
>  1 file changed, 2 insertions(+), 4 deletions(-)
>
> diff --git a/lib/lcm.c b/lib/lcm.c
> index 01b3aa922dda..51cc6b13cd52 100644
> --- a/lib/lcm.c
> +++ b/lib/lcm.c
> @@ -8,9 +8,7 @@ unsigned long lcm(unsigned long a, unsigned long b)
>  {
>         if (a && b)
>                 return (a / gcd(a, b)) * b;
> -       else if (b)
> -               return b;
> -
> -       return a;
> +       else
> +               return 0;
>  }
>  EXPORT_SYMBOL_GPL(lcm);

This change is the source of 3.19 regression for stacking device
limits, via commit 69c953c ("lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not
n").

Test:
# modprobe scsi_debug dev_size_mb=10 num_tgts=1 opt_blks=1536
# cat /sys/block/sde/queue/optimal_io_size
786432
# dmsetup create node --table "0 100 linear /dev/sde 0"

Before commit 69c953c:
# cat /sys/block/dm-5/queue/optimal_io_size
786432

After commit 69c953c:
# cat /sys/block/dm-5/queue/optimal_io_size
0

Rasmus, mathematical purity of lcm() aside, it'd have been nice if you
looked at the lcm() callers to determine whether you'd be breaking
them.

It looks like we need a new lcm_not_zero() and blk_stack_limits()
should be changed to use it, and the patch needs to cc stable.  Martin
and/or Jens, what do you think?

Mike

[PATCH] block: fix blk_stack_limits() regression due to lcm() change

[Mike Snitzer]

Linux 3.19 commit 69c953c ("lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n")
caused blk_stack_limits() to not properly stack queue_limits for stacked
devices (e.g. DM).

Fix this regression by establishing lcm_not_zero() and switching
blk_stack_limits() over to using it.

DM uses blk_set_stacking_limits() to establish the initial top-level
queue_limits that are then built up based on underlying devices' limits
using blk_stack_limits().  In the case of optimal_io_size (io_opt)
blk_set_stacking_limits() establishes a default value of 0.  With commit
69c953c, lcm(0, n) is no longer n, which compromises proper stacking of
the underlying devices' io_opt.

Test:
$ modprobe scsi_debug dev_size_mb=10 num_tgts=1 opt_blks=1536
$ cat /sys/block/sde/queue/optimal_io_size
786432
$ dmsetup create node --table "0 100 linear /dev/sde 0"

Before this fix:
$ cat /sys/block/dm-5/queue/optimal_io_size
0

After this fix:
$ cat /sys/block/dm-5/queue/optimal_io_size
786432

Signed-off-by: Mike Snitzer <snitzer@redhat.com>
Cc: stable@vger.kernel.org # 3.19+
---
 block/blk-settings.c |    6 +++---
 include/linux/lcm.h  |    1 +
 lib/lcm.c            |   11 +++++++++++
 3 files changed, 15 insertions(+), 3 deletions(-)

diff --git a/block/blk-settings.c b/block/blk-settings.c
index 6ed2cbe..12600bf 100644
--- a/block/blk-settings.c
+++ b/block/blk-settings.c
@@ -585,7 +585,7 @@ int blk_stack_limits(struct queue_limits *t, struct queue_limits *b,
 				     b->physical_block_size);
 
 	t->io_min = max(t->io_min, b->io_min);
-	t->io_opt = lcm(t->io_opt, b->io_opt);
+	t->io_opt = lcm_not_zero(t->io_opt, b->io_opt);
 
 	t->cluster &= b->cluster;
 	t->discard_zeroes_data &= b->discard_zeroes_data;
@@ -616,7 +616,7 @@ int blk_stack_limits(struct queue_limits *t, struct queue_limits *b,
 		    b->raid_partial_stripes_expensive);
 
 	/* Find lowest common alignment_offset */
-	t->alignment_offset = lcm(t->alignment_offset, alignment)
+	t->alignment_offset = lcm_not_zero(t->alignment_offset, alignment)
 		% max(t->physical_block_size, t->io_min);
 
 	/* Verify that new alignment_offset is on a logical block boundary */
@@ -643,7 +643,7 @@ int blk_stack_limits(struct queue_limits *t, struct queue_limits *b,
 						      b->max_discard_sectors);
 		t->discard_granularity = max(t->discard_granularity,
 					     b->discard_granularity);
-		t->discard_alignment = lcm(t->discard_alignment, alignment) %
+		t->discard_alignment = lcm_not_zero(t->discard_alignment, alignment) %
 			t->discard_granularity;
 	}
 
diff --git a/include/linux/lcm.h b/include/linux/lcm.h
index 7bf01d7..1ce79a7 100644
--- a/include/linux/lcm.h
+++ b/include/linux/lcm.h
@@ -4,5 +4,6 @@
 #include <linux/compiler.h>
 
 unsigned long lcm(unsigned long a, unsigned long b) __attribute_const__;
+unsigned long lcm_not_zero(unsigned long a, unsigned long b) __attribute_const__;
 
 #endif /* _LCM_H */
diff --git a/lib/lcm.c b/lib/lcm.c
index e97dbd5..03d7fcb 100644
--- a/lib/lcm.c
+++ b/lib/lcm.c
@@ -12,3 +12,14 @@ unsigned long lcm(unsigned long a, unsigned long b)
 		return 0;
 }
 EXPORT_SYMBOL_GPL(lcm);
+
+unsigned long lcm_not_zero(unsigned long a, unsigned long b)
+{
+	unsigned long l = lcm(a, b);
+
+	if (l)
+		return l;
+
+	return (b ? : a);
+}
+EXPORT_SYMBOL_GPL(lcm_not_zero);
-- 
1.7.4.4

Re: [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n

[Rasmus Villemoes]

On Sun, Mar 29 2015, Mike Snitzer <snitzer@redhat.com> wrote:

> On Tue, Dec 9, 2014 at 4:03 PM, Rasmus Villemoes
> <linux@rasmusvillemoes.dk> wrote:
>> Return the mathematically correct answer when an argument is 0.
>>
>> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
>
> This change is the source of 3.19 regression for stacking device
> limits, via commit 69c953c ("lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not
> n").
>
>
> Rasmus, mathematical purity of lcm() aside, it'd have been nice if you
> looked at the lcm() callers to determine whether you'd be breaking
> them.

I'm sorry about this. I thought I did check the callers, but evidently
not well enough.

Rasmus

Re: [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n

[Rasmus Villemoes]

On Sun, Mar 29 2015, Mike Snitzer <snitzer@redhat.com> wrote:

> On Tue, Dec 9, 2014 at 4:03 PM, Rasmus Villemoes
> <linux@rasmusvillemoes.dk> wrote:
>> Return the mathematically correct answer when an argument is 0.
>>
>> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
>
> This change is the source of 3.19 regression for stacking device
> limits, via commit 69c953c ("lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not
> n").
>
>
> Rasmus, mathematical purity of lcm() aside, it'd have been nice if you
> looked at the lcm() callers to determine whether you'd be breaking
> them.

I'm sorry about this. I thought I did check the callers, but evidently
not well enough.

Rasmus

Re: [PATCH] block: fix blk_stack_limits() regression due to lcm() change

[Martin K. Petersen]

>>>>> "Mike" == Mike Snitzer <snitzer@redhat.com> writes:

Mike> Linux 3.19 commit 69c953c ("lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not
Mike> n") caused blk_stack_limits() to not properly stack queue_limits
Mike> for stacked devices (e.g. DM).

Mike> Fix this regression by establishing lcm_not_zero() and switching
Mike> blk_stack_limits() over to using it.

I'm OK with that approach. The original lcm() behavior made sense when
we were the only user.

+unsigned long lcm_not_zero(unsigned long a, unsigned long b)
+{
+	unsigned long l = lcm(a, b);
+
+	if (l)
+		return l;
+
+	return (b ? : a);
+}

I always blink when I read b ?: a instead of b ? b : a. But no
biggie. That's just my personal preference.

Acked-by: Martin K. Petersen <martin.petersen@oracle.com>

-- 
Martin K. Petersen	Oracle Linux Engineering

Re: [PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits

[Rasmus Villemoes]

Rasmus Villemoes <linux@rasmusvillemoes.dk> writes:

Ping...

> Ensure that lcm(a,b) returns the mathematically correct result,
> provided it fits in an unsigned long. The current version returns
> garbage if a*b overflows, even if the final result would fit.
>
> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
> There are of course still plenty of cases where the return value is
> wrong.
>
>  lib/lcm.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/lib/lcm.c b/lib/lcm.c
> index b9c8de4..01b3aa9 100644
> --- a/lib/lcm.c
> +++ b/lib/lcm.c
> @@ -7,7 +7,7 @@
>  unsigned long lcm(unsigned long a, unsigned long b)
>  {
>  	if (a && b)
> -		return (a * b) / gcd(a, b);
> +		return (a / gcd(a, b)) * b;
>  	else if (b)
>  		return b;

[PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits

[Rasmus Villemoes]

Ensure that lcm(a,b) returns the mathematically correct result,
provided it fits in an unsigned long. The current version returns
garbage if a*b overflows, even if the final result would fit.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
There are of course still plenty of cases where the return value is
wrong.

 lib/lcm.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/lcm.c b/lib/lcm.c
index b9c8de4..01b3aa9 100644
--- a/lib/lcm.c
+++ b/lib/lcm.c
@@ -7,7 +7,7 @@
 unsigned long lcm(unsigned long a, unsigned long b)
 {
 	if (a && b)
-		return (a * b) / gcd(a, b);
+		return (a / gcd(a, b)) * b;
 	else if (b)
 		return b;
 
-- 
1.8.4.rc3.2.g61bff3f