Implementation defined behaviour in read_write.c

Implementation defined behaviour in read_write.c

[Rainer Weikusat]

The following code is in the function do_readv_writev in the file
fs/read_write.c (2.6.8.1):


	/*
	 * Single unix specification:
	 * We should -EINVAL if an element length is not >= 0 and fitting an
	 * ssize_t.  The total length is fitting an ssize_t
	 *
	 * Be careful here because iov_len is a size_t not an ssize_t
	 */
	tot_len = 0;
	ret = -EINVAL;
	for (seg = 0; seg < nr_segs; seg++) {
		ssize_t len = (ssize_t)iov[seg].iov_len;

		if (len < 0)	/* size_t not fitting an ssize_t .. */
			goto out;
		tot_len += len;
		if ((ssize_t)tot_len < 0) /* maths overflow on the ssize_t */
			goto out;
	}
	if (tot_len == 0) {
		ret = 0;
		goto out;
	}

There is a potential problem here, namely, that the result of the
conversion to ssize_t is implementation defined (ISO-C
6.3.1.3|3). This is not a problem with current gcc versions, but might
become a future one, because len need not be below zero after
attempting to convert a value too large for a ssize_t to that type. The
following patch would get rid off this (and corrects to errors in the
comment text ;-).

--- read_write.c.orig	2004-09-20 22:26:43.000000000 +0800
+++ read_write.c	2004-09-20 23:45:51.000000000 +0800
@@ -386,10 +386,10 @@
 	typedef ssize_t (*io_fn_t)(struct file *, char __user *, size_t, loff_t *);
 	typedef ssize_t (*iov_fn_t)(struct file *, const struct iovec *, unsigned long, loff_t *);
 
-	size_t tot_len;
+	size_t tot_len, cur_len;
 	struct iovec iovstack[UIO_FASTIOV];
 	struct iovec *iov=iovstack, *vector;
-	ssize_t ret;
+	ssize_t ret, x;
 	int seg;
 	io_fn_t fn;
 	iov_fn_t fnv;
@@ -425,22 +425,32 @@
 
 	/*
 	 * Single unix specification:
-	 * We should -EINVAL if an element length is not >= 0 and fitting an
-	 * ssize_t.  The total length is fitting an ssize_t
+	 * We should -EINVAL if an element length is not >= 0 and fitting a
+	 * ssize_t.  The total length is fitting a ssize_t
 	 *
-	 * Be careful here because iov_len is a size_t not an ssize_t
+	 * Be careful here because iov_len is a size_t not an ssize_t.
 	 */
 	tot_len = 0;
 	ret = -EINVAL;
 	for (seg = 0; seg < nr_segs; seg++) {
-		ssize_t len = (ssize_t)iov[seg].iov_len;
-
-		if (len < 0)	/* size_t not fitting an ssize_t .. */
-			goto out;
-		tot_len += len;
-		if ((ssize_t)tot_len < 0) /* maths overflow on the ssize_t */
+		cur_len = iov[seg].iov_len;
+		/* guard against overflows during the addition */
+		if (cur_len + tot_len < tot_len) goto out;
+		tot_len += cur_len;
 	}
+
+	/*
+	  This is as ISO-compliant as possible.
+	  If the value in tot_len changes when
+	  converted to a ssize_t and back,
+	  something 'implementation defined' happened
+	  because of an overflow.
+	*/
+	x = tot_len;
+	cur_len = x;
+	if (tot_len != cur_len) goto out;
+	
 	if (tot_len == 0) {
 		ret = 0;
 		goto out;

Re: Implementation defined behaviour in read_write.c

[Rainer Weikusat]

Rainer Weikusat <rweikusat@sncag.com> writes:
> +	if (tot_len != cur_len) goto out;

... and this is of course rubbish ... both tests (ie <0 and !=)

Re: Implementation defined behaviour in read_write.c

[Alan Cox]

On Llu, 2004-09-20 at 16:54, Rainer Weikusat wrote:
> The following code is in the function do_readv_writev in the file
> fs/read_write.c (2.6.8.1):

The 2.4.x kernel has part of this fixed. In particular it does the
overflow check differently because gcc 3.x in some forms did appear to
be making use of the undefined nature of the test and that was a
potential security hole. ("its undefined lets say its always false..")

The initial cast and test should be fine. The overflow problem was fixed
in the 2.4 tree and is handled by keeping tot_len unsigned so that the
overflow is a defined operation and then checking versus 0x7FFFFFFF or
0x7FFFFFFFFFFFFFFFUL according to BITS_PER_LONG. I guess the 2.4 code
should be merged into 2.6, perhaps using limits.h instead ?

Alan

Re: Implementation defined behaviour in read_write.c

[Rainer Weikusat]

Alan Cox <alan@lxorguk.ukuu.org.uk> writes:
> On Llu, 2004-09-20 at 16:54, Rainer Weikusat wrote:
>> The following code is in the function do_readv_writev in the file
>> fs/read_write.c (2.6.8.1):
>
> The 2.4.x kernel has part of this fixed. In particular it does the
> overflow check differently because gcc 3.x in some forms did appear to
> be making use of the undefined nature of the test and that was a
> potential security hole. ("its undefined lets say its always
> false.."). The initial cast and test should be fine.

I assume you mean the cast at the beginning of the loop. According to
the C-standard, both cases are exactly the same (they are both
conversions of potentially nonrepresentable values).

	6.3.1.3 Signed and unsigned integers

	When a value with integer type is converted to another integer
	type other than _Bool, if the value can be represented by the
	new type, it is unchanged.

	[...]

	Otherwise, the new type is signed and the value cannot be
	represented in it; either the result is implementation-defined
	or an implementation-defined signal is raised.

The requirement for implementation defined is that the implementation
documents the behaviour (which gcc at least up to 3.4.4 doesn't). This
not a problem with the current compiler, but I happen to know by
coincedence that some people of unknown relations to the gcc team
(like the person who wrote this advisory:
<URL:http://cert.uni-stuttgart.de/advisories/c-integer-overflow.php>)
would like to turn it into a problem, because they strongly believe it
is "the right thing to do", so it may be unwise to rely on gcc for
treating this sanely, ie so that it doesn't break idioms which are in
rather common use.

Re: Implementation defined behaviour in read_write.c

[Linus Torvalds]

On Wed, 22 Sep 2004, Rainer Weikusat wrote:
> 
> 	6.3.1.3 Signed and unsigned integers
> 
> 	When a value with integer type is converted to another integer
> 	type other than _Bool, if the value can be represented by the
> 	new type, it is unchanged.
> 
> 	[...]
> 
> 	Otherwise, the new type is signed and the value cannot be
> 	represented in it; either the result is implementation-defined
> 	or an implementation-defined signal is raised.
> 
> The requirement for implementation defined is that the implementation
> documents the behaviour (which gcc at least up to 3.4.4 doesn't).

They don't, because they do the only thing they _can_ do. Bit-for-bit copy 
of a 2's complement value. Anything else would be basically impossible for 
an optimizing compiler to do unless it actively _tried_ to screw the user 
over. In other words, you're likely to see something else only on a C 
simulator interface that does strict conformance testing (as opposed to 
test for working).

And you are correct to point out the difference between implementation- 
defined and un-defined. Implementation-defined means that it has some 
well-defined semantics, and quite frankly, Linux _does_ depend on 2's 
complement. I don't expect to ever see anything else (where "ever" is a 
long time, although obviously not really "forever"), but if we do, we'll 
have to consider that architecture something very special indeed.

> This
> not a problem with the current compiler, but I happen to know by
> coincedence that some people of unknown relations to the gcc team
> (like the person who wrote this advisory:
> <URL:http://cert.uni-stuttgart.de/advisories/c-integer-overflow.php>)
> would like to turn it into a problem, because they strongly believe it
> is "the right thing to do"

There are tons of people who have theoretical concerns that they try to
push on the real world. Too many of them have talked to the gcc people,
but I think the gcc people are basically sane. So I wouldn't worry _too_ 
much.

That said, there are other cases where signed integer arithmetic should be 
avoided. The signed<->unsigned conversions are safe due to their 
implementation-defined behaviour (and only one sane way to do them), but 
there _are_ cases like signed integer overflow that really is undefined, 
and where a compiler can actually generate code that differs because it 
"knows" that signed integers cannot overflow.

However, in this case that is not what is happening in read_write.c. All 
the arithmetic is done in proper unsigned types, and only the last check 
is done with a (well-defined) signed conversion.

Btw, to see other places where we do depend on this 2's complement 
behaviour, just look at "time_before()" and friends.

		Linus