From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8969 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: Re: AVL tree: storing balances instead of heights Date: Mon, 7 Dec 2015 15:46:22 +0100 Message-ID: <20151207144621.GA23362@port70.net> References: <20151207130344.GZ23362@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1449499602 945 80.91.229.3 (7 Dec 2015 14:46:42 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 7 Dec 2015 14:46:42 +0000 (UTC) Cc: Ed Schouten To: musl@lists.openwall.com Original-X-From: musl-return-8982-gllmg-musl=m.gmane.org@lists.openwall.com Mon Dec 07 15:46:38 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1a5x3k-0006E4-Ig for gllmg-musl@m.gmane.org; Mon, 07 Dec 2015 15:46:36 +0100 Original-Received: (qmail 19798 invoked by uid 550); 7 Dec 2015 14:46:34 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 19771 invoked from network); 7 Dec 2015 14:46:34 -0000 Mail-Followup-To: musl@lists.openwall.com, Ed Schouten Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.24 (2015-08-30) Xref: news.gmane.org gmane.linux.lib.musl.general:8969 Archived-At: * 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. http://port70.net/~nsz/c/c11/n1570.html#6.3.2.3p7 the usage of void** is one of the problems with this interface. > > 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.)