[9fans] replica bug

[9fans] replica bug

[rod]

The replica utilities use an avl tree to store sets of filenames and
attributes. When new trees are created, the function "mkavltree" is
called. It's argument is the comparison routine "entrycmp" in db.c.
"entrycmp" in turn uses "strcmp" to do it's donkey work, and returns
that value directly.  The avl code requires that it's comparison
function returns -1, 0 or 1.  Strcmp is guaranteed only to return an
integer whose sign reflects the comparison result. Whilst on the 386
strcmp does indeed return -1, 0 or 1, on the arm platform this isn't
necessarily the case, leading to bad things.

in db.c:

60a61
> 	int r;
64c65,66
< 	return strcmp(ea->name, eb->name);
---
> 	r = strcmp(ea->name, eb->name);
> 	return r > 0 ? 1 : r < 0 ? -1 : 0;

Rod

;-----------------

PS. Subsequently I wondered if this problem occured elsewhere in the
system. The only other place I can find avl trees being used is in
venti/copy. The actual avl library is used here, rather than the
nearly-the-same-as-the-library file that the replica utilities use.
The function "scoretreecmp" does seem to me to have the potential to
return non (-1,0,1) values. The return value can derive not only from
memcmp, but also from the difference between the two score types.  As
it happens "memcmp" is "safe" for both 386 and arm, and I am guessing
that the latter comparison rarely happens. I also note anyway that the
avl tree is only created and used if the undocumented -m option is
specified on the command line.  It seems that the chance of provoking
the problem here is small...

Re: [9fans] replica bug

[erik quanstrom]

excellent find.  i'd forgotten about this pointy thing.

the problem of course is that the avl library uses the return value directly
as an index into a 3 element array.  this all comes to tears if the compare
function can return something other than {-1, 0, 1}.

On Thu Mar  3 07:26:22 EST 2011, rod@hemiola.co.uk wrote:
> that value directly.  The avl code requires that it's comparison
> function returns -1, 0 or 1.  Strcmp is guaranteed only to return an
> integer whose sign reflects the comparison result.
[...]
>
> PS. Subsequently I wondered if this problem occured elsewhere in the
> system.

i ran into this problem with nupas.  i also fixed the problem in replica
last april.  i tried to submit it, also deleting the private copy of the
avl library.  that wasn't accepted.  though i never saw it, the worry was
that there were some subtle yet important differences.

> memcmp, but also from the difference between the two score types.  As
> it happens "memcmp" is "safe" for both 386 and arm, and I am guessing
> that the latter comparison rarely happens. I also note anyway that the
> avl tree is only created and used if the undocumented -m option is
> specified on the command line.  It seems that the chance of provoking
> the problem here is small...

that function is clearly wrong, and worth fixing.  there's no reason to
leave a land mine around to trip on one day.  if the code is truely never
going to be used, then it should be removed.  otherwise, let's send in
the bomb disposal unit.  here's what i have for both in reverse order.

static int
scoretreecmp(Avl *va, Avl *vb)
{
	ScoreTree *a, *b;
	int i;

	a = (ScoreTree*)va;
	b = (ScoreTree*)vb;

	i = memcmp(a->score, b->score, VtScoreSize);
	if(i == 0)
		i = a->type - b->type;
	if(i > 0)
		i = 1;
	if(i < 0)
		i = -1;
	return i;
}

static int
entrycmp(Avl *a, Avl *b)
{
	int n;
	Entry *ea, *eb;

	ea = (Entry*)a;
	eb = (Entry*)b;

	n = strcmp(ea->name, eb->name);
	if(n > 0)
		n = 1;
	else if(n < 0)
		n = -1;
	return n;
}

- erik

Re: [9fans] replica bug

[Russ Cox]

please fix the avl code, not the callers.
thanks.