Bug#629244: gcc-4.1: miscompiles with -fwrapv

[Thorsten Glaser <tg@mirbsd.de>]

Source: gcc-4.1
Version: 4.1.1ds2-21

Just for reference: the standard compiler on Debian etch (i386)
miscompiles the attached test programme with -fwrapv -O2 and
-fwrapv -Os, but not with -fwrapv -O1 or without -fwrapv.

If there's a workaround I can apply to the source (texpand was
the function changed) please tell me.

/* Copyright (c) Thorsten Glaser. Part of mksh, under the MirOS Licence. */

#include <err.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BIT(i)		(1 << (i))	/* define bit in flag */
#define DEFINED		BIT(1)	/* is defined in block */
#define FINUSE		BIT(9)	/* function being executed */

#define	INIT_TBLS	8	/* initial table size (power of 2) */
#define PERTURB_SHIFT	5	/* see Python 2.5.4 Objects/dictobject.c */

#ifndef SIZE_MAX
#ifdef SIZE_T_MAX
#define SIZE_MAX	SIZE_T_MAX
#else
#define SIZE_MAX	((size_t)-1)
#endif
#endif
#define notoktoadd(val, cnst)	((val) > (SIZE_MAX - (cnst)))
#define checkoktoadd(val, cnst) do {					\
	if (notoktoadd((val), (cnst)))					\
		errx(1,"overflow");			\
} while (/* CONSTCOND */ 0)

struct lalloc {
	struct lalloc *next;
};
typedef struct lalloc Area;
typedef int32_t mksh_ari_t;
typedef uint32_t mksh_uari_t;
struct op;
typedef int Tflag;

struct table {
	Area *areap;		/* area to allocate entries */
	struct tbl **tbls;	/* hashed table items */
	uint32_t size;		/* table size (always 2^n) */
	uint32_t nfree;		/* free table entries */
};

struct tbl {			/* table item */
	Area *areap;		/* area to allocate from */
	union {
		char *s;		/* string */
		mksh_ari_t i;		/* integer */
		mksh_uari_t u;		/* unsigned integer */
		int (*f)(const char **); /* int function */
		struct op *t;		/* "function" tree */
	} val;			/* value */
	union {
		struct tbl *array;	/* array values */
		const char *fpath;	/* temporary path to undef function */
	} u;
	union {
		int field;	/* field with for -L/-R/-Z */
		int errno_;	/* CEXEC/CTALIAS */
	} u2;
	int type;		/* command type (see below), base (if INTEGER),
				 * or offset from val.s of value (if EXPORT) */
	Tflag flag;		/* flags */
	union {
		uint32_t hval;		/* hash(name) */
		uint32_t index;		/* index for an array */
	} ua;
	char name[4];		/* name -- variable length */
};


static void texpand(struct table *, size_t);

static void
texpand(struct table *tp, size_t nsize)
{
	size_t i, j, osize = tp->size, perturb;
	struct tbl *tblp, **pp;
	struct tbl **ntblp, **otblp = tp->tbls;

	i = 1;
	i <<= 30;
	if (nsize > i)
		errx(1, "hash table size limit reached");

	ntblp = malloc(nsize * sizeof(struct tbl *));
	memset(ntblp, 0, nsize * sizeof(struct tbl *));
	tp->size = nsize;
	if (nsize == i) {
		/* cannot be grown any more, use a fixed value */
		tp->nfree = i - 65536;
	} else /* (nsize < 2^30) */ {
		/* table can get 80% full */
		tp->nfree = (nsize * 4) / 5;
	}
	tp->tbls = ntblp;
	if (otblp == NULL)
		return;

	/* from here on nsize := mask */
	nsize--;
	for (i = 0; i < osize; i++)
		if ((tblp = otblp[i]) != NULL) {
			if ((tblp->flag & DEFINED)) {
				/* search for free hash table slot */
				j = (perturb = tblp->ua.hval) & nsize;
				goto find_first_empty_slot;
 find_next_empty_slot:
				j = (j << 2) + j + perturb + 1;
				perturb >>= PERTURB_SHIFT;
 find_first_empty_slot:
				pp = &ntblp[j & nsize];
				if (*pp != NULL)
					goto find_next_empty_slot;
				/* found an empty hash table slot */
				*pp = tblp;
				tp->nfree--;
			} else if (!(tblp->flag & FINUSE)) {
				free(tblp);
			}
		}
	free(otblp);
}

void
ktinit(struct table *tp, Area *ap, size_t tsize)
{
	tp->areap = ap;
	tp->tbls = NULL;
	tp->size = tp->nfree = 0;
	if (tsize)
		texpand(tp, tsize);
}

/* table, name (key) to search for, hash(name), rv pointer to tbl ptr */
static struct tbl *
ktscan(struct table *tp, const char *name, uint32_t h, struct tbl ***ppp)
{
	size_t j, perturb, mask;
	struct tbl **pp, *p;

	mask = tp->size - 1;
	/* search for hash table slot matching name */
	j = (perturb = h) & mask;
	goto find_first_slot;
 find_next_slot:
	j = (j << 2) + j + perturb + 1;
	perturb >>= PERTURB_SHIFT;
 find_first_slot:
	pp = &tp->tbls[j & mask];
	if ((p = *pp) != NULL && (p->ua.hval != h || !(p->flag & DEFINED) ||
	    strcmp(p->name, name)))
		goto find_next_slot;
	/* p == NULL if not found, correct found entry otherwise */
	if (ppp)
		*ppp = pp;
	return (p);
}

/* table, name (key) to enter, hash(n) */
struct tbl *
ktenter(struct table *tp, const char *n, uint32_t h)
{
	struct tbl **pp, *p;
	size_t len;

	if (tp->size == 0)
		texpand(tp, INIT_TBLS);
 Search:
	if ((p = ktscan(tp, n, h, &pp)))
		return (p);

	if (tp->nfree == 0) {
		/* too full */
		texpand(tp, 2 * tp->size);
		goto Search;
	}

	/* create new tbl entry */
	len = strlen(n);
	checkoktoadd(len, offsetof(struct tbl, name[0]) + 1);
	p = malloc(offsetof(struct tbl, name[0]) + ++len);
	p->flag = 0;
	p->type = 0;
	p->areap = tp->areap;
	p->ua.hval = h;
	p->u2.field = 0;
	p->u.array = NULL;
	memcpy(p->name, n, len);

	/* enter in tp->tbls */
	tp->nfree--;
	*pp = p;
	return (p);
}

int
main(void)
{
	struct table t;

	ktinit(&t, NULL, 64);
	ktenter(&t, "foo", 123);
	printf("ok\n");
	return (0);
}