Observe wrapping variables in while loops

Observe wrapping variables in while loops

[Roel Kluin]

Inspired by your definition of 'if', I came up with something to test variable
wrapping in while loops, and was wondering if this was useful for the linux
kernel:

The source below is adapted to illustrate how it works. If you run it, this
will print:

 8 6 4 2 0 variable wraps at ../test.c:88:main(): -1!
...-2
 9 7 5 3 1 variable wraps at ../test.c:94:main(): -1!
...-1
 8 7 6 5 4 3 2 1 0 ...-1
 8 7 6 5 4 3 2 1 ...0
 21 22 23 24 25 26 27 28 29 30 ...31
 19 18 17 16 15 14 13 12 11 10 ...9
 4 3 2 1 0 -1 -2 -3 -4 -5 ...-6
 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ...11
 4 2 0 variable wraps at ../test.c:129:main(): -1!
...-2

In the first two loops and the last, a wrap occurs due to the double decrement.
Tests like 'while(i++ < 30)' and 'while(j-- > -5)' are boolean.

However, this may not work for a construction like this:

while ((ret = foo())) {
	do_stuff();
}
------------------------------>8-------------8<---------------------------------
#include <stdio.h>

struct while_data {
        const char *func;
        const char *file;
        unsigned line;
        unsigned long last;
};

int is_while_wrap(struct while_data *w, unsigned long val)
{
	if (w->last < val) {
		printf("variable wraps at %s:%u:%s(): %d!\n", w->file, w->line, w->func, val);
		return 0;
	}
	w->last = val;
	return val;
}

#define __while_check__(x) ({                             \
			static struct while_data			\
                                ______w = {                             \
                                .func = __func__,                       \
                                .file = __FILE__,                       \
                                .line = __LINE__,                       \
				.last = ULONG_MAX,			\
                        };                                              \
			printf(" ");					\
                        is_while_wrap(&______w, (x)); 	\
                })

#define while(x) 	while(__while_check__(x))


int main(int argc, char* argv[])
{
	unsigned int i=9;
	while(i--) {
		printf("%d", i);
		--i;
	}
	printf("...%d\n", i);
	i=10;
	while(--i) {
		printf("%d", i);
		--i;
	}
	printf("...%d\n", i);

	i=9;
	while(i--)
		printf("%d", i);
	printf("...%d\n", i);

	i=9;
	while(--i)
		printf("%d", i);
	printf("...%d\n", i);

	i=20;
	while(i++ < 30)
		printf("%d", i);
	printf("...%d\n", i);

	i=20;
	while(i-- > 10)
		printf("%d", i);
	printf("...%d\n", i);

	int j=5;
	while(j-- > -5)
		printf("%d", j);
	printf("...%d\n", j);
	while(j++ < 10)
		printf("%d", j);
	printf("...%d\n", j);

	j=5;
	while(j--) {
		printf("%d", j);
		j--;
	}
	printf("...%d\n", j);
}

Re: Observe wrapping variables in while loops

[Steven Rostedt]

On Sun, 8 Mar 2009, Roel Kluin wrote:

> Inspired by your definition of 'if', I came up with something to test variable
> wrapping in while loops, and was wondering if this was useful for the linux
> kernel:
> 
> The source below is adapted to illustrate how it works. If you run it, this
> will print:
> 
>  8 6 4 2 0 variable wraps at ../test.c:88:main(): -1!
> ...-2
>  9 7 5 3 1 variable wraps at ../test.c:94:main(): -1!
> ...-1
>  8 7 6 5 4 3 2 1 0 ...-1
>  8 7 6 5 4 3 2 1 ...0
>  21 22 23 24 25 26 27 28 29 30 ...31
>  19 18 17 16 15 14 13 12 11 10 ...9
>  4 3 2 1 0 -1 -2 -3 -4 -5 ...-6
>  -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ...11
>  4 2 0 variable wraps at ../test.c:129:main(): -1!
> ...-2
> 
> In the first two loops and the last, a wrap occurs due to the double decrement.
> Tests like 'while(i++ < 30)' and 'while(j-- > -5)' are boolean.
> 
> However, this may not work for a construction like this:

Interesting variation. Now the question is, how many bugs are we aware of 
that were caused by wraps? If there are a few, then I would say this is 
definitely something to look at. Otherwise, it may not be worth putting 
this in mainline.

-- Steve



> 
> while ((ret = foo())) {
> 	do_stuff();
> }
> ------------------------------>8-------------8<---------------------------------
> #include <stdio.h>
> 
> struct while_data {
>         const char *func;
>         const char *file;
>         unsigned line;
>         unsigned long last;
> };
> 
> int is_while_wrap(struct while_data *w, unsigned long val)
> {
> 	if (w->last < val) {
> 		printf("variable wraps at %s:%u:%s(): %d!\n", w->file, w->line, w->func, val);
> 		return 0;
> 	}
> 	w->last = val;
> 	return val;
> }
> 
> #define __while_check__(x) ({                             \
> 			static struct while_data			\
>                                 ______w = {                             \
>                                 .func = __func__,                       \
>                                 .file = __FILE__,                       \
>                                 .line = __LINE__,                       \
> 				.last = ULONG_MAX,			\
>                         };                                              \
> 			printf(" ");					\
>                         is_while_wrap(&______w, (x)); 	\
>                 })
> 
> #define while(x) 	while(__while_check__(x))
> 
> 
> int main(int argc, char* argv[])
> {
> 	unsigned int i=9;
> 	while(i--) {
> 		printf("%d", i);
> 		--i;
> 	}
> 	printf("...%d\n", i);
> 	i=10;
> 	while(--i) {
> 		printf("%d", i);
> 		--i;
> 	}
> 	printf("...%d\n", i);
> 
> 	i=9;
> 	while(i--)
> 		printf("%d", i);
> 	printf("...%d\n", i);
> 
> 	i=9;
> 	while(--i)
> 		printf("%d", i);
> 	printf("...%d\n", i);
> 
> 	i=20;
> 	while(i++ < 30)
> 		printf("%d", i);
> 	printf("...%d\n", i);
> 
> 	i=20;
> 	while(i-- > 10)
> 		printf("%d", i);
> 	printf("...%d\n", i);
> 
> 	int j=5;
> 	while(j-- > -5)
> 		printf("%d", j);
> 	printf("...%d\n", j);
> 	while(j++ < 10)
> 		printf("%d", j);
> 	printf("...%d\n", j);
> 
> 	j=5;
> 	while(j--) {
> 		printf("%d", j);
> 		j--;
> 	}
> 	printf("...%d\n", j);
> }
> 

Re: Observe wrapping variables in while loops

[Roel Kluin]

Steven Rostedt wrote:
> 
> 
> On Sun, 8 Mar 2009, Roel Kluin wrote:
> 
>> Inspired by your definition of 'if', I came up with something to test variable
>> wrapping in while loops, and was wondering if this was useful for the linux
>> kernel:

> Interesting variation. Now the question is, how many bugs are we aware of 
> that were caused by wraps? If there are a few, then I would say this is 
> definitely something to look at. Otherwise, it may not be worth putting 
> this in mainline.
> 
> -- Steve

Hi Steve, Andrew,

Below is a extended version, that does some more tests. it obviously isn't
finished, it requires more work done, but I think it may eventually provide very
interesting runtime debugging observations.

Roel
------------------------------>8-------------8<---------------------------------

/* (C) Roel Kluin, 2009 GPL v.2 */

#include <stdio.h>
#include <string.h>

#define ULONG_MAX       (~0UL)
typedef enum {false, true} bool;
#define NULL ((void *)0)

struct while_data {
        const char *func;
        const char *file;
        const char *str;
        unsigned line;
	bool signd;
	bool postfix;
	bool incr;
        unsigned long last;
	bool printed;
	struct while_data *next;
};

static struct while_data *while_data_head;

int while_unsigned(struct while_data *w, int val)
{
	if (!(w->printed & 1)) {
		w->next = while_data_head;
		while_data_head = w;
		w->signd = false;

		const char* decrstr = strstr(w->str, "--");
		if (decrstr != NULL) {
			if (strcmp(decrstr, "--") == 0) {
				w->incr = false;
				w->postfix = true;
			} else if (strcmp(decrstr, w->str) == 0) {
				/* FIXME: we have to ensure that
				   the first part is a variable name
				   and nothing else */
				w->incr = false;
				w->postfix = false;
			} else {
				printf("decrement not recognized.\n");
			}
		}
		else
			printf("no decrement found.\n");
		w->printed |= 1;
	}
	if (w->last < val && !(w->printed & 2)) {
		printf("variable wraps at %s:%u:%s()!\n", w->file, w->line, w->func);
		printf("while(%s) with a variable that is %d!\n", w->str, val);
		w->printed |= 2;
		return 0;
	}
	return val;
}


int while_int(struct while_data *w, int val)
{
	if (!(w->printed & 1)) {
		w->next = while_data_head;
		while_data_head = w;
		w->signd = true;

		const char* decrstr = strstr(w->str, "--");
		if (decrstr != NULL) {
			if (strcmp(decrstr, "--") == 0) {
				w->incr = false;
				w->postfix = true;
			} else if (strcmp(decrstr, w->str) == 0) {
				/* FIXME: we have to ensure that
				   the first part is a variable name
				   and nothing else */
				w->incr = false;
				w->postfix = false;
			} else {
				printf("decrement not recognized.\n");
			}
		}
		else
			printf("no decrement found.\n");
		w->printed |= 1;
	}
	/* other test for wrapping here */
	return val;
}

#define __while_check__(x) ({						\
	static struct while_data ______w = {				\
		.func = __func__,					\
		.file = __FILE__,					\
		.str = #x,						\
		.line = __LINE__,					\
		.last = ULONG_MAX,					\
		.printed = 0,						\
	};								\
	__builtin_choose_expr(						\
		__builtin_constant_p(x),				\
		(x),							\
	__builtin_choose_expr(						\
		__builtin_types_compatible_p(typeof(x), int),		\
		while_int(&______w, (x)),				\
	__builtin_choose_expr(						\
		__builtin_types_compatible_p(typeof(x), unsigned),	\
		while_unsigned(&______w, (x)),				\
		(x)							\
	)));								\
})

#define while(x)	while(__while_check__(x))


int check_if(int val, const char* test, const char* func, int line)
{
	struct while_data *w = while_data_head;

	if (strcmp(func, while_data_head->func) != 0)
		goto end;

	/* FIXME: we have to verify that the variable
	to the left is the same as the one used in
	the while loop */
	/* TODO: also test "!= 0", "== 0" (and variants)*/
	if (w->incr ) {
		if(w->postfix) {
			if (w->signd) {
				;
			} else {
				;
			}
		} else {
			if (w->signd) {
				;
			} else {
				;
			}
		}
	} else {
		if(w->postfix) {
			if (w->signd) {
				if (strstr(test, "< 0") != 0) {
					printf("after while(%s) at %s:%u:%s()\n", w->str,
					w->file, w->line, w->func);
					printf("if(%s) at line %u is off by one.\n", test, line);
				} else if (strstr(test, ">= 0") != 0){
					printf("after while(%s) at %s:%u:%s()\n", w->str,
					w->file, w->line, w->func);
					printf("if(%s) at line %u is off by one.\n", test, line);
				}
			} else {
				if (strstr(test, "< 0") != 0) {
					printf("if(%s) at line %u is always false, since variable is unsigned.\n", test, line);
				} else if (strstr(test, ">= 0") != 0){
					printf("if(%s) at line %u is always true, since variable is unsigned.\n", test, line);
				}
			}
		} else {
			if (w->signd) {
				if (strstr(test, "<= 0") != 0) {
					printf("after while(%s) at %s:%u:%s()\n", w->str,
					w->file, w->line, w->func);
					printf("if(%s) at line %u is off by one.\n", test, line);
				} else if (strstr(test, "> 0") != 0){
					printf("after while(%s) at %s:%u:%s()\n", w->str,
					w->file, w->line, w->func);
					printf("if(%s) at line %u is off by one.\n", test, line);
				}
			} else {
				if (strstr(test, "< 0") != 0) {
					printf("if(%s) at line %u is always false, since variable is unsigned.\n", test, line);
				} else if (strstr(test, ">= 0") != 0){
					printf("if(%s) at line %u is always true, since variable is unsigned.\n", test, line);
				} else if (strstr(test, "> 0") != 0){
					printf("if(%s) at line %u is off by one.\n", test, line);
				}
			}
		}
	}
end:
	return val;
}

#define __if_check__(x) ({						\
	check_if((x), #x, __func__, __LINE__);				\
})

#define if(x)	if(__if_check__(x))

int main(int argc, char* argv[])
{
	//#define x 0
	unsigned x = 10;
	int y;
	// these alternatives, should work

	while (x--)
		/*printf("in loop:%d\n", x)*/;

	if (x < 0)
		printf("won't print!\n");

	x = 10;
	while (--x)
		/*printf("in loop:%d\n", x)*/;

	printf("after loop:%d\n", x);

	if (x < 0)
		printf("won't print!\n");

	y = 10;
	while (y--)
		/*printf("in loop:%d\n", x)*/;

	if (y < 0)
		printf("will print.\n");

	y = 10;
	while (--y)
		/*printf("in loop:%d\n", x)*/;

	if (y < 0)
		printf("won't print!\n");

	return 0;
}