[RFC v2 1/2] compiler: use compiler to detect integer overflows

[RFC v2 1/2] compiler: use compiler to detect integer overflows

[Sasha Levin]

We've used to detect integer overflows by causing an overflow and testing the
result. For example, to test for addition overflow we would:

	if (a + b < a)
		/* Overflow detected */

While it works, this is actually an undefined behaviour and we're not
guaranteed to have integers overflowing this way. GCC5 has introduced
built in macros (which existed in Clang/LLVM for a while) to test for
addition, subtraction and multiplication overflows.

Rather than keep relying on the current behaviour of GCC, let's take
it's olive branch and test for overflows by using the builtin
functions.

Changing existing code is simple and can be done using Coccinelle:

@@ expression X; expression Y; constant C; @@
(
- X + Y < Y
+ check_add_overflow(X, Y)
|
- X - Y > X
+ check_sub_overflow(X, Y)
|
- X != 0 && Y > C / X
+ check_mul_overflow(X, Y, C)
)

Signed-off-by: Sasha Levin <sasha.levin@oracle.com>
---

Changes in V2:

 - Comments from Vegard Nossum
 - Comments from Andrey Ryabinin
 - Use a relevant example commit

 include/linux/compiler-gcc5.h |   17 +++++++++++++++++
 include/linux/compiler.h      |   23 +++++++++++++++++++++++
 2 files changed, 40 insertions(+)

diff --git a/include/linux/compiler-gcc5.h b/include/linux/compiler-gcc5.h
index c8c5659..0429519 100644
--- a/include/linux/compiler-gcc5.h
+++ b/include/linux/compiler-gcc5.h
@@ -63,3 +63,20 @@
 #define __HAVE_BUILTIN_BSWAP64__
 #define __HAVE_BUILTIN_BSWAP16__
 #endif /* CONFIG_ARCH_USE_BUILTIN_BSWAP */
+
+#define check_add_overflow(A, B)					\
+({									\
+	typeof((A) + (B)) __gcc_overflow_dummy;				\
+	__builtin_add_overflow((A), (B), &__gcc_overflow_dummy);	\
+})
+
+#define check_sub_overflow(A, B)					\
+({									\
+	typeof((A) - (B)) __gcc_overflow_dummy;				\
+	__builtin_sub_overflow((A), (B), &__gcc_overflow_dummy);	\
+})
+
+#define check_mul_overflow(A, B, C)					\
+	typeof((A) * (B)) __gcc_overflow_dummy;				\
+	__builtin_mul_overflow((A), (B), &__gcc_overflow_dummy);	\
+})
diff --git a/include/linux/compiler.h b/include/linux/compiler.h
index 934a834..bbe85ab 100644
--- a/include/linux/compiler.h
+++ b/include/linux/compiler.h
@@ -388,4 +388,27 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);
 # define __kprobes
 # define nokprobe_inline	inline
 #endif
+
+#ifndef check_add_overflow
+#define check_add_overflow(A, B)			\
+({							\
+	typeof(A) __tmp_A = (A);			\
+	 (((__tmp_A) + (B)) < (__tmp_A));		\
+})
+#endif
+#ifndef check_sub_overflow
+#define check_sub_overflow(A, B)			\
+({							\
+	typeof(A) __tmp_A = (A);			\
+	(((__tmp_A) - (B)) > (__tmp_A));		\
+})
+#endif
+#ifndef check_mul_overflow
+#define check_mul_overflow(A, B, C)			\
+({							\
+	typeof(A) __tmp_A = (A);			\
+	((__tmp_A) != 0 && (B) > (C) / (__tmp_A));	\
+})
+#endif
+
 #endif /* __LINUX_COMPILER_H */
-- 
1.7.10.4

[RFC v2 2/2] fs: correctly check for signed integer overflow in vfs_fallocate

[Sasha Levin]

Both "offset" and "len" are signed integers who's addition may overflow
and trigger undefined behaviour.

Signed-off-by: Sasha Levin <sasha.levin@oracle.com>
---
 fs/open.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/fs/open.c b/fs/open.c
index 813be03..33d5cae 100644
--- a/fs/open.c
+++ b/fs/open.c
@@ -287,7 +287,8 @@ int vfs_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
 		return -ENODEV;
 
 	/* Check for wrap through zero too */
-	if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len) < 0))
+	if (check_add_overflow(offset, len) ||
+	   (offset + len) > inode->i_sb->s_maxbytes)
 		return -EFBIG;
 
 	if (!file->f_op->fallocate)
-- 
1.7.10.4

Re: [RFC v2 1/2] compiler: use compiler to detect integer overflows

[Linus Torvalds]

On Wed, Nov 26, 2014 at 3:58 PM, Sasha Levin <sasha.levin@oracle.com> wrote:
> We've used to detect integer overflows by causing an overflow and testing the
> result. For example, to test for addition overflow we would:

So I don't like this, for a very simple reason: it doesn't work for
older gcc versions.

Your "check_add_overflow()" doesn't actually do it. It just
perpetuates any bugs you find. For unsigned additions, it's pointless,
and for signed additions it remains as buggy as it was before.

Also, your commit message is still *very*wrong*. You can't claim that
integer addition overflow is undefined. It's undefined onyl for
_signed_ integer types, and that's a big big difference.

So no. This still doesn't work.

                     Linus

Re: [RFC v2 1/2] compiler: use compiler to detect integer overflows

[Sasha Levin]

On 11/26/2014 07:33 PM, Linus Torvalds wrote:
> On Wed, Nov 26, 2014 at 3:58 PM, Sasha Levin <sasha.levin@oracle.com> wrote:
>> > We've used to detect integer overflows by causing an overflow and testing the
>> > result. For example, to test for addition overflow we would:
> So I don't like this, for a very simple reason: it doesn't work for
> older gcc versions.
> 
> Your "check_add_overflow()" doesn't actually do it. It just
> perpetuates any bugs you find. For unsigned additions, it's pointless,
> and for signed additions it remains as buggy as it was before.

I understand your point. It doesn't fix bugs but rather hides them on
newer compilers.

Since the way to fix this is by properly checking for overflow rather than
the old broken (a + b > a) conditional, how about something like the following
for the non-gcc5 case:

#define IS_UNSIGNED(A) (((typeof(A))-1) >= 0)
#define TYPE_MAX(A) ((typeof(A))(~0U>>1))
#define TYPE_MIN(A) (-TYPE_MAX(A) - 1)
#define check_add_overflow(A, B)                                        \
({                                                                      \
        typeof(A) __a = (A);                                            \
        typeof(B) __b = (B);                                            \
        typeof(sizeof(__a) > sizeof(__b) ? __a : __b) __min, __max;     \
        if (IS_UNSIGNED(__a) || IS_UNSIGNED(__b))                       \
                0;                                                      \
        __min = TYPE_MIN(__min);                                        \
        __max = TYPE_MAX(__max);                                        \
        (((__a > 0) && (typeof(__max))__b > (__max - ((typeof(__max))__a)))  ||\
                ((__a < 0) && (typeof(__max))__b < (__min - ((typeof(__max))__a))));\
})

> Also, your commit message is still *very*wrong*. You can't claim that
> integer addition overflow is undefined. It's undefined onyl for
> _signed_ integer types, and that's a big big difference.

Understood. I'll be specific it's only for signed integer overflows.


Thanks,
Sasha

Re: [RFC v2 1/2] compiler: use compiler to detect integer overflows

[Linus Torvalds]

On Wed, Nov 26, 2014 at 5:37 PM, Sasha Levin <sasha.levin@oracle.com> wrote:
>
> #define IS_UNSIGNED(A) (((typeof(A))-1) >= 0)
> #define TYPE_MAX(A) ((typeof(A))(~0U>>1))
> #define TYPE_MIN(A) (-TYPE_MAX(A) - 1)
> #define check_add_overflow(A, B)                                        \
> ({                                                                      \
>         typeof(A) __a = (A);                                            \
>         typeof(B) __b = (B);                                            \
>         typeof(sizeof(__a) > sizeof(__b) ? __a : __b) __min, __max;     \

That doesn't do what you think it does. The "typeof()" on a ternary
operator will not pick the type of the selected side, it will pick the
normal C integer promotion type of the right-hand sides. The actual
_conditional_ matters not at all for the final type.

Which actually ends up being the thing you want in this case, but the
thing is, it's much better written as

    typeof(__a + __b) __min, __max;

and leave it at that. That way __min and __max have the type of the
integer promotion of A and B.

>         if (IS_UNSIGNED(__a) || IS_UNSIGNED(__b))                       \
>                 0;                                                      \

And again, that's wrong for two reasons. I think you're trying to
"return" 0 from the statement expression, but that's not how it works.

Also, the logic itself is also wrong. If the smaller type is unsigned,
that doesn't help.

But once again, the C integer type promotion DTRT, and you should just then do

      if (IS_UNSIGNED(__a+__b))

but as mentioned, that "if (x) 0;" is not how you'd return 0 anyway.
You'd have to make it part of the next expression.


>         __min = TYPE_MIN(__min);                                        \
>         __max = TYPE_MAX(__max);                                        \
>         (((__a > 0) && (typeof(__max))__b > (__max - ((typeof(__max))__a)))  ||\
>                 ((__a < 0) && (typeof(__max))__b < (__min - ((typeof(__max))__a))));\
> })

.. which I didn't actually validate. And I suspect gcc won't be good
enough to optimize, so it probably generates horrendous code.

And the thing is, I think it's just *wrong* to do "overflow in signed
type". The code that does it shouldn't be helped to do it, it should
be fixed to use an unsigned type.

In other words - in this case, the lofft_t should probably just be a u64.

                   Linus

Re: [RFC v2 1/2] compiler: use compiler to detect integer overflows

[Sasha Levin]

On 11/26/2014 10:13 PM, Linus Torvalds wrote:
> .. which I didn't actually validate. And I suspect gcc won't be good
> enough to optimize, so it probably generates horrendous code.

That's correct. It's pretty bad.

> And the thing is, I think it's just *wrong* to do "overflow in signed
> type". The code that does it shouldn't be helped to do it, it should
> be fixed to use an unsigned type.
> 
> In other words - in this case, the lofft_t should probably just be a u64.

In this case it's very tied to userspace. One caller is the space allocation
ioctl, which gets this from userspace:

struct space_resv {
	[...]
        __s64           l_start;
        __s64           l_len;          /* len == 0 means until end of file */
        [...]
};

Since we can't just change those to unsigned, we'd still need to do an overflow
check with signed integers somewhere.


Thanks,
Sasha

Re: [RFC v2 1/2] compiler: use compiler to detect integer overflows

[Linus Torvalds]

On Sat, Nov 29, 2014 at 7:07 AM, Sasha Levin <sasha.levin@oracle.com> wrote:
>
> Since we can't just change those to unsigned

Sure we can. Just cast them. A signed start/len is bogus crap, it's a
random wrong type.

If you want to, add a "if (len < 0) return -EINVAL;" before the cast,
but treating negative numbers as big positive numbers sounds fine too.

> we'd still need to do an overflow
> check with signed integers somewhere.

Why? It's just a type. User space can't care, and signed values make
no sense anyway.

                 Linus

Re: [RFC v2 1/2] compiler: use compiler to detect integer overflows

[Sasha Levin]

On 11/29/2014 01:08 PM, Linus Torvalds wrote:
> On Sat, Nov 29, 2014 at 7:07 AM, Sasha Levin <sasha.levin@oracle.com> wrote:
>> >
>> > Since we can't just change those to unsigned
> Sure we can. Just cast them. A signed start/len is bogus crap, it's a
> random wrong type.

But this is going on everywhere in fs/! It uses loff_t for pretty much anything,
even stuff which are obviously are unsigned (inode.i_size for example). Do you
think it's worth the effort to switch is all to unsigned?


Thanks,
Sasha