<sys/queue.h> is broken in overlay mode

changed the description

Dislaimer: I'm not the/a maintainer, but I just submitted !12 (closed) so I thought I'd take a stab at this.

Comparing FreeBSD's queue.h (which libbsd uses) with glibc's, it seems that effectively the only two missing are the SIMPLEQ and CIRCLEQ variants. It would be easy to:

add an #include_next <sys/queue.h> at the top of the file, within the BSD overlay block, to include glibc's define first. This may be ugly and possibly risky, as we would be redefining glibc's identifiers later on.
add #defines for the two aforementioned variants, copied from either historical BSD code, or glibc.
add #defines to map SIMPLEQ to STAILQ and CIRCLEQ to TAILQ.

The question I have, however, is… why :) The purpose of the BSD overlay is to provide compatibility to compile unmodified programs that were originally targeted for BSD systems. None of FreeBSD, OpenBSD or NetBSD seem to support CIRCLEQ (and in it was very deliberately removed from FreeBSD in 2000). Mixing and matching glibc-specific and BSD-specific code seems like a bad idea in principle

That said, SIMPLEQ_ is something that OpenBSD and NetBSD support as well, so perhaps there is some value to adding compatibility defines for it.

Sorry @alejandro-colomar, been neglecting this one, because the situation with <queue.h> looked like a mess, and have had no time to look properly into it to form an opinion!

Thanks @paravoid for having dug up into this. I've now merged your MR locally updating the header, and I'm otherwise not convinced the macros explicitly removed upstream should be reintroduced, at least w/o a very strong argument supporting it. But I'd be fine adding support for SIMPLEQ_ I guess if one of the BSDs supports it.

SIMPLEQ is supported by glibc, NetBSD, OpenBSD. STAILQ is exactly equivalent, and supported by glibc, FreeBSD, OpenBSD, and NetBSD (and others). I don't know why would anyone use SIMPLEQ in their code -- perhaps we should just let it die, and if any software shows up, patch it by s/SIMPLEQ/STAILQ/ to offer maximum portability.

Alternatively, this should do it (untested):

#define	SIMPLEQ_CONCAT			STAILQ_CONCAT
#define	SIMPLEQ_EMPTY			STAILQ_EMPTY
#define	SIMPLEQ_END			STAILQ_END
#define	SIMPLEQ_ENTRY			STAILQ_ENTRY
#define	SIMPLEQ_FIRST			STAILQ_FIRST
#define	SIMPLEQ_FOREACH			STAILQ_FOREACH
#define	SIMPLEQ_FOREACH_SAFE		STAILQ_FOREACH_SAFE
#define	SIMPLEQ_HEAD			STAILQ_HEAD
#define	SIMPLEQ_HEAD_INITIALIZER	STAILQ_HEAD_INITIALIZER
#define	SIMPLEQ_INIT			STAILQ_INIT
#define	SIMPLEQ_INSERT_AFTER		STAILQ_INSERT_AFTER
#define	SIMPLEQ_INSERT_HEAD		STAILQ_INSERT_HEAD
#define	SIMPLEQ_INSERT_TAIL		STAILQ_INSERT_TAIL
#define	SIMPLEQ_LAST			STAILQ_LAST
#define	SIMPLEQ_NEXT			STAILQ_NEXT
#define	SIMPLEQ_REMOVE			STAILQ_REMOVE
#define	SIMPLEQ_REMOVE_AFTER		STAILQ_REMOVE_AFTER
#define	SIMPLEQ_REMOVE_HEAD		STAILQ_REMOVE_HEAD

I've verified that SIMPLEQ and STAILQ are equivalent in NetBSD (extract the two sections, then sed s/STAILQ/SIMPLEQ/g;s/stq/sq/g` it and diff). NetBSD does not ship STAILQ_REMOVE_AFTER though.

In OpenBSD, SIMPLEQ_INSERT_AFTER is different than STAILQ_INSERT_AFTER, but same as FreeBSD's STAILQ_INSERT_AFTER. OpenBSD does not have SIMPLEQ_LAST (which NetBSD has) and SIMPLEQ_REMOVE (which NetBSD and glibc have).

So the above will bring us a superset of compatibility, that noone else has.

Hi @guillem and @paravoid,

Thanks for your time!

Re: Why?: I don't use libbsd as a compatibility BSD layer. I use it because I like BSD functions that glibc refuses to add. But I also like to have functions that glibc provides and the BSDs don't. Libbsd seems to be my solution. Given that I have libbsd available on all systems that I normally use, I don't think it's such a bad idea. I could write those functions from scratch from glibc functions, but I'd have to maintain code that is already maintained by libbsd, so I prefer to have libbsd as a dependency. :-)

Re: 3 options:

I'd agree that redefining glibc's macros is risky.
Copying from explicitly removed BSD code doesn't make much sense. libbsd would have to maintain it. And copying from glibc might not be an option (I guess glibc uses GPL3 for that).
Remap CIRCLEQ->TAILQ, SIMPLEQ->STAILQ: interesting idea.

Re: SIMPLEQ: In never knew what it was. Never used it. Now that I've seen that it's simply STAILQ renamed, I wonder why it ever existed. Is there any historical reason for it? Moreover, glibc provides both, which makes no sense at all!

Re: Neglecting this one: Don't worry, I understand. I also found that same mess when I restructured the manual page in the Linux man-pages. Which by the way, if you want to copy back to FreeBSD or any other BSD, please feel free. I kept the BSD license. However, I changed to use man macros. See https://linux-man-pages.blogspot.com/2020/11/man-pages-509-is-released.html if you're interested. (There are more important changes coming with man-pages 5.11.)

Cheers,

Alex

Thanks so much for providing more insight into the specifics of your use case, that helps a lot! I guess a couple of follow-up questions if I may:

First, given that--as far as I understand this--is about your code rather than a third-party port... is your original problem addressed by using TAILQ instead of CIRCLEQ? Do you still have any reason to use CIRCLEQ?

Second, given that you don't use libbsd as a compatibility BSD layer, is there a reason why you're using the overlay mode rather than use #include <bsd/sys/queue.h> (which can be preceded or followed by #include <sys/queue.h>)? Thanks for any insight here!

Oops, I was about to talk about that in my previous answer, but forgot about it in the middle of the writing...

Re: Using TAILQ instead of CIRCLEQ: I found out that the BSDs had removed CIRCLEQ after reporting this bug (a few onths ago). Now I know the reasons (performance hell), yes, I'll either use TAILQ, or write a CIRCLEQ2 set of macros that don't have the problems of CIRCLEQ (basically, I'd remove the dummy head, which made CRICLEQ to not be continuously circular, but more like a belt). The only thing that doesn't convince me of TAILQ, is that it doesn't have a macro to loop from N to N-1 (I'd call that CIRCLEQ_FOREACH_FROM(), although AFAICT, it never existed in any of the BSDs (neither in glibc)).

Re: rationale for using CIRCLEQ: All this problem started for me when I tried to move some code from a circular queue that I wrote myself to the standard macros from queue.h, and the straightforward move was to use CIRCLEQ. But no, there's no strict reason to use CIRCLEQ. As I said, I'll either write a new CIRCLEQ2 (based on TAILQ code), or use TAILQ directly.

Re: <bsd/...>: Initially (long before using queue.h), I decided to use the overlay mode, so that my code would be easier to port to BSD. Also, if glibc ever adds some of the BSD functions, the transition would be transparent. However, now I think twice, removing 'bsd/' from the includes if I ever need it, wouldn't be a big problem, and it would solve much bigger problems, so I'll use <bsd/...>.

So, IMO this should be closed as WONTFIX. There's not much to gain from workarounding this. Even if glibc keeps CIRCLEQ for legacy reasons, new code should't use CIRCLEQ, so this should never be triggered.

Thanks,

Alex

BTW, I found some interesting historical info by reading through the sources:

FreeBSD added STAILQ on Mar 31, 1996, on commit (git) 088b8b1d26276d0b4d790c43c417fb166255d630.
NetBSD added SIMPLEQ on May 16, 1996, on commit (git) 0a21bae6491828b2e5534825fe8530bc2f73b021.
OpenBSD added SIMPLEQ on May 22, 1996, on commit (git) c5fc27f3057aea64f72c98938b79a964a41a7f35.
NetBSD added STAILQ on Dec 6, 2002, on commit (git) 6b1bf68d9bdbf22aec0c656958b033b145b79b0d. Commit msg:

Add STAILQ_*. Really the same as SIMPLEQ, but this syncs the API with FreeBSD.

P.S.: I prefer the STAILQ naming :)

Ok, so let's wrap this one up. But I think before closing, it would be nice to add the portability information (as in versions introducing the interfaces to the queue(3bsd) man page, within a HISTORY section as it is done in other man pages. @alejandro-colomar or @paravoid given that you have done the digging on these already, would you mind preparing a small patch for this? Thanks! :)

Hi Guillem!

I missed the message about the History section. I could do it. However, I feel that page is too huge to my taste (which is why I split it in the Linux man-pages. How about splitting it?

Cheers, Alex

BTW, I just checked the Linux man-pages to see if I added anything back then. It seems I did:

stailq(3):

SYNOPSIS
       [...]
       Note: Identical macros prefixed with SIMPLEQ instead of  STAILQ  exist;
       see NOTES.

[...]

NOTES
       Some  BSDs  provide SIMPLEQ instead of STAILQ.  They are identical, but
       for historical reasons they were named differently on  different  BSDs.
       STAILQ  originated  on  FreeBSD, and SIMPLEQ originated on NetBSD.  For
       compatibility reasons, some systems provide both sets of macros.  Glibc
       provides both STAILQ and SIMPLEQ, which  are  identical  except  for  a
       missing SIMPLEQ equivalent to STAILQ_CONCAT(3).

This could go to your page too.

BTW, that contradicts the STANDARDS section, which I believe is wrong (I think it's my fault):

stailq(3):

STANDARDS
       Not in POSIX.1, POSIX.1‐2001, or POSIX.1‐2008.   Present  on  the  BSDs
       (STAILQ macros first appeared in 4.4BSD).

That seems an accident from when I split the pages from the original queue(3):

STANDARDS
       Not in POSIX.1, POSIX.1‐2001, or POSIX.1‐2008.  Present  on  the  BSDs.
       <sys/queue.h> macros first appeared in 4.4BSD.

added overlay label

<sys/queue.h> is broken in overlay mode

Child items ...

Activity

Admin message

Admin message

<sys/queue.h> is broken in overlay mode

Activity