[musl] [PATCH] search: provide twalk_r()

[musl] [PATCH] search: provide twalk_r()

[Bartosz Golaszewski]

From: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>

Provide a variant of twalk() that allows callers to pass custom user
data to it without resorting to global variables.

Signed-off-by: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>
---
 include/search.h     |  1 +
 src/search/twalk_r.c | 24 ++++++++++++++++++++++++
 2 files changed, 25 insertions(+)
 create mode 100644 src/search/twalk_r.c

diff --git a/include/search.h b/include/search.h
index 02e407e3..95b4cdc2 100644
--- a/include/search.h
+++ b/include/search.h
@@ -53,6 +53,7 @@ struct qelem {
 	char q_data[1];
 };
 
+void twalk_r(const void *, void (*)(const void *, VISIT, void *), void *);
 void tdestroy(void *, void (*)(void *));
 #endif
 
diff --git a/src/search/twalk_r.c b/src/search/twalk_r.c
new file mode 100644
index 00000000..9497273f
--- /dev/null
+++ b/src/search/twalk_r.c
@@ -0,0 +1,24 @@
+#include <search.h>
+#include "tsearch.h"
+
+static void
+walk(const struct node *r, void (*action)(const void *, VISIT, void *), void *data)
+{
+	if (!r)
+		return;
+	
+	if (r->h == 1) {
+		action(r, leaf, data);
+	} else {
+		action(r, preorder, data);
+		walk(r->a[0], action, data);
+		action(r, postorder, data);
+		walk(r->a[1], action, data);
+		action(r, endorder, data);
+	}
+}
+
+void twalk_r(const void *root, void (*action)(const void *, VISIT, void *), void *data)
+{
+	walk(root, action, data);
+}
-- 
2.37.2

Re: [musl] [PATCH] search: provide twalk_r()

[Rich Felker]

On Thu, Feb 09, 2023 at 09:43:42PM +0100, Bartosz Golaszewski wrote:
> From: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>
> 
> Provide a variant of twalk() that allows callers to pass custom user
> data to it without resorting to global variables.
> 
> Signed-off-by: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>

Is there any precedent for this other than glibc, with matching
signature and behavior? Without that, it looks like it's subject to
the potential for conflicting definitions.

Rich

Re: [musl] [PATCH] search: provide twalk_r()

[Bartosz Golaszewski]

On Thu, Feb 9, 2023 at 10:16 PM Rich Felker <dalias@libc.org> wrote:
>
> On Thu, Feb 09, 2023 at 09:43:42PM +0100, Bartosz Golaszewski wrote:
> > From: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>
> >
> > Provide a variant of twalk() that allows callers to pass custom user
> > data to it without resorting to global variables.
> >
> > Signed-off-by: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>
>
> Is there any precedent for this other than glibc, with matching
> signature and behavior? Without that, it looks like it's subject to
> the potential for conflicting definitions.
>

Not sure what you mean. GLibc IS the precedent. This function has only
been around since glibc 2.30 (well, it's been 3 years) and requires
_GNU_SOURCE. It's a relatively new function but without it, twalk() is
quite useless.

The background for this patch is: I have a low-level C library that I
maintain for which I try to limit external dependencies and I used
twalk_r() in the new version only to find out it doesn't build with
musl.

Bart

Re: [musl] [PATCH] search: provide twalk_r()

[Khem Raj]

On Thu, Feb 9, 2023 at 1:26 PM Bartosz Golaszewski <brgl@bgdev.pl> wrote:
>
> On Thu, Feb 9, 2023 at 10:16 PM Rich Felker <dalias@libc.org> wrote:
> >
> > On Thu, Feb 09, 2023 at 09:43:42PM +0100, Bartosz Golaszewski wrote:
> > > From: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>
> > >
> > > Provide a variant of twalk() that allows callers to pass custom user
> > > data to it without resorting to global variables.
> > >
> > > Signed-off-by: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>
> >
> > Is there any precedent for this other than glibc, with matching
> > signature and behavior? Without that, it looks like it's subject to
> > the potential for conflicting definitions.
> >
>
> Not sure what you mean. GLibc IS the precedent. This function has only
> been around since glibc 2.30 (well, it's been 3 years) and requires
> _GNU_SOURCE. It's a relatively new function but without it, twalk() is
> quite useless.

musl uses posix as its guiding light and sparingly implement other functions

>
> The background for this patch is: I have a low-level C library that I
> maintain for which I try to limit external dependencies and I used
> twalk_r() in the new version only to find out it doesn't build with
> musl.

maybe you should carry it as a fallback in your library and use it when building
on libraries which do not provide it as a fall back.

>
> Bart

Re: [musl] [PATCH] search: provide twalk_r()

[Bartosz Golaszewski]

On Fri, Feb 10, 2023 at 3:18 AM Khem Raj <raj.khem@gmail.com> wrote:
>
> On Thu, Feb 9, 2023 at 1:26 PM Bartosz Golaszewski <brgl@bgdev.pl> wrote:
> >
> > On Thu, Feb 9, 2023 at 10:16 PM Rich Felker <dalias@libc.org> wrote:
> > >
> > > On Thu, Feb 09, 2023 at 09:43:42PM +0100, Bartosz Golaszewski wrote:
> > > > From: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>
> > > >
> > > > Provide a variant of twalk() that allows callers to pass custom user
> > > > data to it without resorting to global variables.
> > > >
> > > > Signed-off-by: Bartosz Golaszewski <bartosz.golaszewski@linaro.org>
> > >
> > > Is there any precedent for this other than glibc, with matching
> > > signature and behavior? Without that, it looks like it's subject to
> > > the potential for conflicting definitions.
> > >
> >
> > Not sure what you mean. GLibc IS the precedent. This function has only
> > been around since glibc 2.30 (well, it's been 3 years) and requires
> > _GNU_SOURCE. It's a relatively new function but without it, twalk() is
> > quite useless.
>
> musl uses posix as its guiding light and sparingly implement other functions
>

I understand the musl philosophy but it already provides tdestroy()
which also happens to be a GNU extension.

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.

> >
> > The background for this patch is: I have a low-level C library that I
> > maintain for which I try to limit external dependencies and I used
> > twalk_r() in the new version only to find out it doesn't build with
> > musl.
>
> maybe you should carry it as a fallback in your library and use it when building
> on libraries which do not provide it as a fall back.
>

That was my first thought but unfortunately struct node is not part of
the ABI and so user programs must not use it. In fact: it's not even
in the public header - callers only see a void pointer.

For me this means, that it's either limiting the availability of
libgpiosim to glibc, implementing my own binary search tree (that
would take up 300+ LOC for no reason and just end up copying existing
code anyway) or pulling in some library that provides it in C (which
would have to be something well maintained like GLib - which is huge)
just to get that single functionality which I'd really like to avoid.
In this context making musl provide twalk_r() upstream sounds like the
best solution and I'm sure my library is not the only user.

Please reconsider providing twalk_r() in musl.

Thanks
Bart

Re: [musl] [PATCH] search: provide twalk_r()

[Markus Wichmann]

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.

> For me this means, that it's either limiting the availability of
> libgpiosim to glibc, implementing my own binary search tree (that
> would take up 300+ LOC for no reason and just end up copying existing
> code anyway) or pulling in some library that provides it in C (which
> would have to be something well maintained like GLib - which is huge)
> just to get that single functionality which I'd really like to avoid.
> In this context making musl provide twalk_r() upstream sounds like the
> best solution and I'm sure my library is not the only user.

But rolling your own would allow you to tune the tree to your needs. 300
LOC? Seems excessive to me. One sec, let me see... yes, I found an
intrusive red-black tree in my archives which clocks in at 209 lines.
Admittedly without twalk_r()-equivalent, but the existing traversal
function can be turned into that with no additional line. Since it is
intrusive, it does not even call malloc(). It has absolutely no ties to
the system. It could work on bare metal if needed. Well, OK, my
insertion conflict resolution strategy is to define that they don't
happen by way of assert(), so that could be done better, but otherwise,
no external dependencies happen.

And it wouldn't be for no reason, it would be for the reason that the
POSIX interface is lacking and not all environments your library runs on
support the extension you need.

Rolling your own would also make your library portable beyond Linux.
Beyond POSIX, even. This may not matter to you right now. It would also
mean you don't have to make demands of other libraries to get your own
stuff to work.

Ciao,
Markus

Re: [musl] [PATCH] search: provide twalk_r()

[Rich Felker]

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