| Message ID | 1402694330-21211-1-git-send-email-abuchbinder@google.com (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
Hi Adam, (2014/06/14 6:18), Adam Buchbinder wrote: > When running with UndefinedBehaviorSanitizer, the tests produce the following > error: > > radix-tree.c:836:30: runtime error: shift exponent 18446744073709551613 > is too large for 64-bit type 'unsigned long' > > (That's a negative shift exponent represented as an unsigned long.) > > Even though the value is discarded in those cases, it's still undefined > behavior; see the C99 standard, section 6.5.7, paragraph three: "If the > value of the right operand is negative [...] the behavior is undefined." > > Signed-off-by: Adam Buchbinder <abuchbinder@google.com> It looks good to me. Reviewed-by: Satoru Takeuchi <takeuchi_satoru@jp.fujitsu.com> Thanks, Satoru > --- > radix-tree.c | 6 +++--- > 1 file changed, 3 insertions(+), 3 deletions(-) > > diff --git a/radix-tree.c b/radix-tree.c > index 4f295fc..7457944 100644 > --- a/radix-tree.c > +++ b/radix-tree.c > @@ -833,10 +833,10 @@ int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) > static unsigned long __maxindex(unsigned int height) > { > unsigned int tmp = height * RADIX_TREE_MAP_SHIFT; > - unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1; > + unsigned long index = ~0UL; > > - if (tmp >= RADIX_TREE_INDEX_BITS) > - index = ~0UL; > + if (tmp < RADIX_TREE_INDEX_BITS) > + index = (index >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1; > return index; > } > > -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Jun 18, 2014 at 03:20:30PM +0900, Satoru Takeuchi wrote: > Hi Adam, > > (2014/06/14 6:18), Adam Buchbinder wrote: > > When running with UndefinedBehaviorSanitizer, the tests produce the following > > error: > > > > radix-tree.c:836:30: runtime error: shift exponent 18446744073709551613 > > is too large for 64-bit type 'unsigned long' > > > > (That's a negative shift exponent represented as an unsigned long.) > > > > Even though the value is discarded in those cases, it's still undefined > > behavior; see the C99 standard, section 6.5.7, paragraph three: "If the > > value of the right operand is negative [...] the behavior is undefined." > > > > Signed-off-by: Adam Buchbinder <abuchbinder@google.com> > > It looks good to me. > > Reviewed-by: Satoru Takeuchi <takeuchi_satoru@jp.fujitsu.com> Thank you both. The file is taken from kernel/lib/radix-tree.c and has diverged a bit so it could be missing more bugfixes. -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi David, Adam, (2014/06/18 23:43), David Sterba wrote: > On Wed, Jun 18, 2014 at 03:20:30PM +0900, Satoru Takeuchi wrote: >> Hi Adam, >> >> (2014/06/14 6:18), Adam Buchbinder wrote: >>> When running with UndefinedBehaviorSanitizer, the tests produce the following >>> error: >>> >>> radix-tree.c:836:30: runtime error: shift exponent 18446744073709551613 >>> is too large for 64-bit type 'unsigned long' >>> >>> (That's a negative shift exponent represented as an unsigned long.) >>> >>> Even though the value is discarded in those cases, it's still undefined >>> behavior; see the C99 standard, section 6.5.7, paragraph three: "If the >>> value of the right operand is negative [...] the behavior is undefined." >>> >>> Signed-off-by: Adam Buchbinder <abuchbinder@google.com> >> >> It looks good to me. >> >> Reviewed-by: Satoru Takeuchi <takeuchi_satoru@jp.fujitsu.com> > > Thank you both. > > The file is taken from kernel/lib/radix-tree.c and has diverged a bit so > it could be missing more bugfixes. I confirmed the kenel doesn't have such problem. lib/radix-tree.c (kernel code): =============================================================================== static __init unsigned long __maxindex(unsigned int height) { unsigned int width = height * RADIX_TREE_MAP_SHIFT; int shift = RADIX_TREE_INDEX_BITS - width; if (shift < 0) return ~0UL; if (shift >= BITS_PER_LONG) return 0UL; return ~0UL >> shift; } =============================================================================== It's fixed at 430d275a399. =============================================================================== commit 430d275a399175c7c0673459738979287ec1fd22 Author: Peter Lund <firefly@vax64.dk> Date: Tue Oct 16 23:29:35 2007 -0700 avoid negative (and full-width) shifts in radix-tree.c ... =============================================================================== Adam, David, how about import this patch from kernel, rather than writing btrfs-progs's own patch? P.S. I consider It's better to regularly sync such utility code with the newest kernel code for the long term... Thanks, Satoru > -- > To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Jun 19, 2014 at 10:10:55AM +0900, Satoru Takeuchi wrote: > It's fixed at 430d275a399. > > =============================================================================== > commit 430d275a399175c7c0673459738979287ec1fd22 > Author: Peter Lund <firefly@vax64.dk> > Date: Tue Oct 16 23:29:35 2007 -0700 > > avoid negative (and full-width) shifts in radix-tree.c > ... > =============================================================================== > > Adam, David, how about import this patch from kernel, rather than > writing btrfs-progs's own patch? Well, I think there's non-trivial time spent by Adam on the patch so I'd rather keep the credit, even if a patch that backports the fix from kernel would look cleaner in git log. Such things happen, sometimes it makes sense to replace patches or do changes inline. The progs development is moving forward quickly, a clean patch history is most useful when there is a separate stable branch that receives bugfixes as it helps the backporters to identify complete fixes. Not the case for progs right now. > I consider It's better to regularly sync such utility code with > the newest kernel code for the long term... Yes. The radix- or rb- tree code does not change often though, we can do a sync now and be fine for some time. -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi David, (2014/06/19 22:28), David Sterba wrote: > On Thu, Jun 19, 2014 at 10:10:55AM +0900, Satoru Takeuchi wrote: >> It's fixed at 430d275a399. >> >> =============================================================================== >> commit 430d275a399175c7c0673459738979287ec1fd22 >> Author: Peter Lund <firefly@vax64.dk> >> Date: Tue Oct 16 23:29:35 2007 -0700 >> >> avoid negative (and full-width) shifts in radix-tree.c >> ... >> =============================================================================== >> >> Adam, David, how about import this patch from kernel, rather than >> writing btrfs-progs's own patch? > > Well, I think there's non-trivial time spent by Adam on the patch so I'd > rather keep the credit, even if a patch that backports the fix from > kernel would look cleaner in git log. Such things happen, sometimes it > makes sense to replace patches or do changes inline. > > The progs development is moving forward quickly, a clean patch history > is most useful when there is a separate stable branch that receives > bugfixes as it helps the backporters to identify complete fixes. Not the > case for progs right now. > >> I consider It's better to regularly sync such utility code with >> the newest kernel code for the long term... > > Yes. The radix- or rb- tree code does not change often though, we can do > a sync now and be fine for some time. OK, I see. Thank you for your clear explanation. Thanks, Satoru -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/radix-tree.c b/radix-tree.c index 4f295fc..7457944 100644 --- a/radix-tree.c +++ b/radix-tree.c @@ -833,10 +833,10 @@ int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) static unsigned long __maxindex(unsigned int height) { unsigned int tmp = height * RADIX_TREE_MAP_SHIFT; - unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1; + unsigned long index = ~0UL; - if (tmp >= RADIX_TREE_INDEX_BITS) - index = ~0UL; + if (tmp < RADIX_TREE_INDEX_BITS) + index = (index >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1; return index; }
When running with UndefinedBehaviorSanitizer, the tests produce the following error: radix-tree.c:836:30: runtime error: shift exponent 18446744073709551613 is too large for 64-bit type 'unsigned long' (That's a negative shift exponent represented as an unsigned long.) Even though the value is discarded in those cases, it's still undefined behavior; see the C99 standard, section 6.5.7, paragraph three: "If the value of the right operand is negative [...] the behavior is undefined." Signed-off-by: Adam Buchbinder <abuchbinder@google.com> --- radix-tree.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)