Skip to contentSkip to conversation

lib/lcm.c: Ensure correct result whenever it fits

PATCH In review Rasmus Villemoes 3 participants 6 messages Dec 9, 2014 – Mar 30, 2015

Subsystems (3)
Block layer Library code Device mapper
lore
Share & tools
lore

Rasmus Villemoes

author
#0 lore raw

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

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 <[email protected]>
---
 lib/lcm.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/lcm.c +1 -1
index b9c8de461e9e..01b3aa922dda 100644
@@ -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;
Signature · 1 line
2.1.3
author
#1 lore raw

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

Return the mathematically correct answer when an argument is 0.

Signed-off-by Rasmus Villemoes <[email protected]>
---
 lib/lcm.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
lib/lcm.c +2 -4
index 01b3aa922dda..51cc6b13cd52 100644
@@ -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);
Signature · 1 line
2.1.3
#2 lore raw

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

Quoted 13 lines · Rasmus Villemoes

Return the mathematically correct answer when an argument is 0.

Signed-off-by Rasmus Villemoes <[email protected]>
---
 lib/lcm.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
lib/lcm.c +0 -0
index 01b3aa922dda..51cc6b13cd52 100644
@@ -8,9 +8,7 @@ unsigned long lcm(unsigned long a, unsigned long b)
 {

lib/lcm.c unsigned long lcm(unsigned long a, unsigned long b) · line 14

Quoted 10 lines
lib/lcm.c +2 -4
        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

#3 lore raw

PATCH 1/1 block: fix blk_stack_limits() regression due to lcm() change

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 <[email protected]>
Cc [email protected] # 3.19+
---
 block/blk-settings.c |    6 +++---
 include/linux/lcm.h  |    1 +
 lib/lcm.c            |   11 +++++++++++
 3 files changed, 15 insertions(+), 3 deletions(-)
block/blk-settings.c +3 -3
index 6ed2cbe..12600bf 100644
@@ -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;
 	}
include/linux/lcm.h +1 -0
index 7bf01d7..1ce79a7 100644
@@ -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 */
lib/lcm.c +11 -0
index e97dbd5..03d7fcb 100644
@@ -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);
Signature · 1 line
1.7.4.4
Acked-by on v1 1/1
#4 lore raw

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

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

"Mike" == Mike Snitzer <[email protected]> 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 <[email protected]>
Signature · 1 line
Martin K. Petersen	Oracle Linux Engineering
author
#5 lore raw

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

In reply to Mike Snitzer
Quoted 6 lines · Mike Snitzer
Quoted 3 lines · Rasmus Villemoes

Return the mathematically correct answer when an argument is 0.

Signed-off-by Rasmus Villemoes <[email protected]>
Quoted 8 lines

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