LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits
@ 2014-12-09 21:03 Rasmus Villemoes
  2014-12-09 21:03 ` [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n Rasmus Villemoes
  0 siblings, 1 reply; 7+ messages in thread
From: Rasmus Villemoes @ 2014-12-09 21:03 UTC (permalink / raw)
  To: Andrew Morton; +Cc: Rasmus Villemoes, linux-kernel

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


^ permalink raw reply	[flat|nested] 7+ messages in thread

* [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n
  2014-12-09 21:03 [PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits Rasmus Villemoes
@ 2014-12-09 21:03 ` Rasmus Villemoes
  2015-03-29  2:44   ` Mike Snitzer
  0 siblings, 1 reply; 7+ messages in thread
From: Rasmus Villemoes @ 2014-12-09 21:03 UTC (permalink / raw)
  To: Andrew Morton; +Cc: Rasmus Villemoes, linux-kernel

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


^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n
  2014-12-09 21:03 ` [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n Rasmus Villemoes
@ 2015-03-29  2:44   ` Mike Snitzer
  2015-03-30 17:39     ` [PATCH] block: fix blk_stack_limits() regression due to lcm() change Mike Snitzer
  2015-03-30 19:38     ` [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n Rasmus Villemoes
  0 siblings, 2 replies; 7+ messages in thread
From: Mike Snitzer @ 2015-03-29  2:44 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Andrew Morton, linux-kernel, Martin K. Petersen,
	device-mapper development, Jens Axboe

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* [PATCH] block: fix blk_stack_limits() regression due to lcm() change
  2015-03-29  2:44   ` Mike Snitzer
@ 2015-03-30 17:39     ` Mike Snitzer
  2015-03-30 20:53       ` Martin K. Petersen
  2015-03-30 19:38     ` [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n Rasmus Villemoes
  1 sibling, 1 reply; 7+ messages in thread
From: Mike Snitzer @ 2015-03-30 17:39 UTC (permalink / raw)
  To: Jens Axboe
  Cc: Andrew Morton, dm-devel, linux-kernel, Martin K. Petersen,
	Rasmus Villemoes

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


^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n
  2015-03-29  2:44   ` Mike Snitzer
  2015-03-30 17:39     ` [PATCH] block: fix blk_stack_limits() regression due to lcm() change Mike Snitzer
@ 2015-03-30 19:38     ` Rasmus Villemoes
  1 sibling, 0 replies; 7+ messages in thread
From: Rasmus Villemoes @ 2015-03-30 19:38 UTC (permalink / raw)
  To: Mike Snitzer
  Cc: Andrew Morton, linux-kernel, Martin K. Petersen,
	device-mapper development, Jens Axboe

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [PATCH] block: fix blk_stack_limits() regression due to lcm() change
  2015-03-30 17:39     ` [PATCH] block: fix blk_stack_limits() regression due to lcm() change Mike Snitzer
@ 2015-03-30 20:53       ` Martin K. Petersen
  0 siblings, 0 replies; 7+ messages in thread
From: Martin K. Petersen @ 2015-03-30 20:53 UTC (permalink / raw)
  To: Mike Snitzer
  Cc: Jens Axboe, Andrew Morton, dm-devel, linux-kernel,
	Martin K. Petersen, Rasmus Villemoes

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

^ permalink raw reply	[flat|nested] 7+ messages in thread

* [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n
  2013-12-17 14:46 [PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits Rasmus Villemoes
@ 2013-12-17 14:46 ` Rasmus Villemoes
  0 siblings, 0 replies; 7+ messages in thread
From: Rasmus Villemoes @ 2013-12-17 14:46 UTC (permalink / raw)
  To: linux-kernel; +Cc: Rasmus Villemoes

Return the mathematically correct answer when an argument is 0.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
I don't think there is any instance of lcm(0,n) in the kernel, but at
least this reduces code size a little.

 lib/lcm.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/lib/lcm.c b/lib/lcm.c
index 01b3aa9..51cc6b1 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);
-- 
1.8.4.rc3.2.g61bff3f


^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, other threads:[~2015-03-30 20:53 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-12-09 21:03 [PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits Rasmus Villemoes
2014-12-09 21:03 ` [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n Rasmus Villemoes
2015-03-29  2:44   ` Mike Snitzer
2015-03-30 17:39     ` [PATCH] block: fix blk_stack_limits() regression due to lcm() change Mike Snitzer
2015-03-30 20:53       ` Martin K. Petersen
2015-03-30 19:38     ` [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n Rasmus Villemoes
  -- strict thread matches above, loose matches on Subject: below --
2013-12-17 14:46 [PATCH 1/2] lib/lcm.c: Ensure correct result whenever it fits Rasmus Villemoes
2013-12-17 14:46 ` [PATCH 2/2] lib/lcm.c: lcm(n,0)=lcm(0,n) is 0, not n Rasmus Villemoes

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).