Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 7 Dec 2015 15:46:22 +0100
From: Szabolcs Nagy <>
Cc: Ed Schouten <>
Subject: Re: Re: AVL tree: storing balances instead of heights

* Ed Schouten <> [2015-12-07 14:19:58 +0100]:
> 2015-12-07 14:03 GMT+01:00 Szabolcs Nagy <>:
> > and the (T**) cast is invalid in
> >
> >         void *tdelete(const void *restrict key, void **restrict rootp,
> >                       int (*compar)(const void *, const void *)) {
> >           void *result = (void *)1;
> >           tdelete_recurse(key, (struct __tnode **)rootp, compar, &result);
> >           return result;
> >         }
> Could you please elaborate this a bit further?

	void *a = 0;
	void **p = &a;
	T **q = (T**)p;

may be undefined behaviour (if T* and void* have
different alignment requirement) otherwise q has
some arbitrary value that is only meaningful if
it's converted back to (void**).

	T *b = *(T**)p;

is undefined behaviour.

in general it is not guaranteed that void* or void**
is represented the same way as other pointers, the
guarantee is that all object pointers can be converted
to/from void* and may be possible to convert to/from
other object pointers, but in either case you have to
convert the pointer back to the original type to get
a meaningful value that can be dereferenced.

the usage of void** is one of the problems with this

> > posix specifies to return a pointer to a node, not to an element
> > pointer, i think that's a bug in posix (otherwise the api would
> > be useless).
> Yes. On lines 40 and 44 the result pointer is set to the parent
> object. As __key is the first member of the structure, I could have
> written *n instead of &(*n)->__key, but this implementation does not
> strongly enforce it. I could put __key anywhere in the node structure
> and it would always return a pointer to a pointer to a key.

returning *n instead of &(*n)->key would be wrong, so the
musl implementation should be fixed, and the spec should
be fixed too because with the current wording the caller
cannot do anything with the return value.

same problem as above:

	struct node { void *key; } *n = ...;
	void **pkey = (void*)n;
	void *key = *pkey;

is ub, pkey may not be meaningful.

(i'd audit cloud libc for any use of pointer casts to
make sure there is no such bugs, this is one of the
reasons why musl very rarely uses casts.. in this case
the type-unsafe void* return value bit us though.)

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.