musl - Re: [PATCH] search: provide twalk

Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20230210210529.GC4163@brightrain.aerifal.cx>
Date: Fri, 10 Feb 2023 16:05:30 -0500
From: Rich Felker <dalias@...c.org>
To: Markus Wichmann <nullplan@....net>
Cc: musl@...ts.openwall.com,
	Bartosz Golaszewski <bartosz.golaszewski@...aro.org>
Subject: Re: [PATCH] search: provide twalk_r()

On Fri, Feb 10, 2023 at 09:07:45PM +0100, Markus Wichmann wrote:
> On Fri, Feb 10, 2023 at 09:35:02AM +0100, Bartosz Golaszewski wrote:
> > These extensions exist for a reason - they are simply useful and
> > programs do use them out in the wild. twalk() on its own is brain-dead
> > and only useful to small programs that can afford to have global
> > variables. If you have a variable that tries to hold no global
> > context, then the possibility to pass data to the walk callback is
> > absolutely required. This is a general problem with those hash-map,
> > binary tree etc. APIs in POSIX - they don't seem to be designed very
> > well. GNU extensions try to address some of those issues.
> >
> 
> Nobody ever questioned the usefulness of these extensions. The reason
> musl does not adopt them immediately, however, is that without
> standardization, we run the risk of future incompatible standardization,
> and therefore, musl developing quirks. musl cannot remove functionality
> without breaking ABI, and it is currently not built in a way that would
> allow breaking ABI. So only new functions can be added, old ones must
> remain indefinitely.
> 
> Case in point: qsort_r(). The BSDs had added another function of the
> same name, but with different argument order (both in the qsort_r() call
> and the comparison function). If musl had added the BSD version and then
> the GNU version got standardized, musl would have had to work around the
> incompatibility somehow. Or else be stuck with the nonconforming
> version.
> 
> I concur that the hashmap and binary tree POSIX APIs are not very well
> designed, and I question the need for them in libc. Personally, I would
> counsel against using anything from search.h, especially when it does
> not fit your needs. That would also get rid of the requirement for libc
> to support nonstandard APIs. I mean, we are talking about data
> structures here; it is not like there is a shortage of libraries
> implementing these for all sorts of things.

Thanks for explaining this. If folks want twalk_r, a good way to
approach this would be either proposing the GNU-compatible function to
one or more of the BSDs, or proposing it directly to POSIX with the
glibc implementation as precedent.

However, in the short term, an easy way to get it without any support
from the standard library is as a wraper for twalk, something like
this (untested):

static _Thread_local void (*action)(const void *, VISIT, void *);
static _Thread_local void *data;

static void wrapper_action(const void *p, VISIT v, int d)
{
	action(p, v, data);
}

void twalk_r(const void *root, void (*action)(const void *, VISIT, void *), void *data)
{
	void (*old_action)(const void *, VISIT, void *) = action;
	void *old_data = data;
	twalk(root, wrapper_action);
	data = old_data;
	action = old_action;
}

The only reason I put the old_* stuff there is to make it reentrant,
in case the action function itself calls twalk_r.

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