3 ms·

Does someone know why these are not reentrant without the GNU extension? It seems like a really weird choice to make a library for hash tables and then make the

Does someone know why these are not reentrant without the GNU extension? It seems like a really weird choice to make a library for hash tables and then make the state global like that.

kragen 2y ago
probably they were added in 2.9bsd or something when programs couldn't be more than about 5000 lines of code before you ran out of the 16-bit address space hmm, no, it doesn't seem to be in https://www.tuhs.org/Archive/Distributions/UCB/2.9BSD/ https://www.tuhs.org/Archive/Distributions/UCB/2.9BSD/ or even in https://www.tuhs.org/Archive/Distributions/UCB/4.2BSD/ https://www.tuhs.org/Archive/Distributions/UCB/4.2BSD/ or https://www.tuhs.org/Archive/Distributions/UCB/4.3BSD/ https://www.tuhs.org/Archive/Distributions/UCB/4.3BSD/. and https://man.freebsd.org/cgi/man.cgi?query=hsearch&apropos=0&sektion=3&manpath=FreeBSD+15.0-CURRENT&arch=default&format=html https://man.freebsd.org/cgi/man.cgi?query=hsearch&apropos=0&... says explicitly: > The hcreate(), hdestroy(), and hsearch() functions first appeared in AT&T System V UNIX. which... does seem a bit late for thinking it was a good idea to only support one hash table per process? that was in 01983, 6 years after the vax was introduced and 4 years after the 68000. i mean awk supported arbitrarily many hash tables in a single process in 7th edition unix, even before it had subroutines
- Someone 2y ago
  > i mean awk supported arbitrarily many hash tables in a single process This API supports that, too, as long as you don’t call one of the functions while another call is in progress. You get that for free if your process is single threaded. https://en.wikipedia.org/wiki/Thread_(computing)#Threading_models https://en.wikipedia.org/wiki/Thread_(computing)#Threading_m... says “History of threading models in Unix systems SunOS 4.x implemented light-weight processes or LWPs. NetBSD 2.x+, and DragonFly BSD implement LWPs as kernel threads (1:1 model)” According to Wikipedia, SunOS 4.0 is from 1988, NetBSD 2.0 from 2004, so I guess chances are good that AT&T System V UNIX didn’t support threads in user space programs.
  - p_l 2y ago
    Adding threading support is why there was a bunch of interest in using Mach microkernel in Unix systems.
  - kimixa 2y ago
    Or a signal handler? Even if there's a single kernel thread, if it can be interrupted while inside one of these functions you can hit the same sort of problem. Reentrancy was an issue on consumer devices well before multithreading was commonly supported there, after all
    - rdtsc 2y ago
      Good point. There are multiple levels of "safety". I think glibc API does a decent job marking and indicating which is which: https://sourceware.org/glibc/manual/2.40/html_node/POSIX-Safety-Concepts.html https://sourceware.org/glibc/manual/2.40/html_node/POSIX-Saf... Thread-Safe Async-Signal-Safe Async-Cancel-Safe (mostly limited to pthread_*cancel*) There is a host of other "safety" remarks also useful to keep in mind: https://sourceware.org/glibc/manual/2.40/html_node/Other-Safety-Remarks.html https://sourceware.org/glibc/manual/2.40/html_node/Other-Saf...
      - kragen 2y ago
        this isn't about safety, though; hcreate() and hsearch() don't support having two hash tables in the same process at the same time, not even in an unsafe way. that also makes them non-reentrant, but that isn't the main problem!
  - kragen 2y ago
    you seem to be discussing what does or doesn't support multiple threads, but what we were talking about is what does or doesn't support multiple simultaneously existing hash tables, which hcreate() doesn't. i've edited my comment upthread to clarify (it's also true, as kimixa points out, that a single-threaded process with signal handlers isn't really single-threaded, but i don't think that's really the important consideration in this context) for what it's worth, it's not very difficult to use alarm() to invoke a context-switching subroutine to get preemptive user-space multithreading on unix without any kernel support. in theory you have to write the context-switching subroutine in assembly language, which isn't difficult at all; here's one i wrote in arm assembly for the arm eabi, for cooperative multithreading: .thumb_func .globl einyield einyield: push {r0, r4-r11, lr} @ save all callee-saved regs plus r0 ldr r0, =current_task_pointer ldr r1, [r0] str sp, [r1] @ save stack pointer in current eintask ldr r1, [r1, #4] @ load pointer to next eintask str r1, [r0] ldr sp, [r1] @ switch to next eintask's stack pop {r0, r4-r11, pc} @ return into einyielded context there (from http://canonical.org/~kragen/sw/dev3/einkornix.S http://canonical.org/~kragen/sw/dev3/einkornix.S) but in practice you can usually just use longjmp() preemptive multithreading requires you to save all the registers, not just the callee-saved registers, but so does signal handling, so you can usually just use the signal-handling machinery and use the above code (or its equivalent on your vax or 68000 or whatever) to context-switch between signal-handler stack frames
- clbrmbr 2y ago
  Don’t key prefixes take care of the need for an arbitrary number of tables?
tedunangst 2y ago
Probably started as a function in one program. Somebody copied it into a second program. Somebody wanted it in a third program and copied it into a library.
loeg 2y ago
They're really, really old. Dating to System V Unix. At the time it was pretty common to have stateful libc functions.
layer8 2y ago
You can look them up here in System V Interface Definition Issue 2 from 1986: http://www.bitsavers.org/pdf/att/unix/SVID/System_V_Interface_Definition_Issue_2_Volume_1_1986.pdf http://www.bitsavers.org/pdf/att/unix/SVID/System_V_Interfac.... It has a note “Future Directions: The restriction on only having one hash search table active at any given time will be removed.” Which of course couldn’t be done without breaking compatibility. Most programs at the time probably didn’t need more than one hash table, and it made for a simpler interface. (A program could in principle also work around the limitation by storing multiple values per hash table entry.) Most Unix libraries worked with global state at the time, since multi-threading also didn’t exist yet. I remember running into the limitation of only being able to have one lexer/parser grammar (via lex/yacc) per program.
kelnos 2y ago
Back when these functions were created, it was normal and expected for libc to store global state for a variety of things. Reentrancy wasn't really an issue that was considered then. (Though this particular API has an even weirder limitation: you can only create a single hash table at a time in your entire program!)

Does someone know why these are not reentrant without the GNU extension? It seems like a really weird choice to make a library for hash tables and then make the state global like that.

kragen 2y ago

probably they were added in 2.9bsd or something when programs couldn't be more than about 5000 lines of code before you ran out of the 16-bit address space hmm, no, it doesn't seem to be in https://www.tuhs.org/Archive/Distributions/UCB/2.9BSD/ https://www.tuhs.org/Archive/Distributions/UCB/2.9BSD/ or even in https://www.tuhs.org/Archive/Distributions/UCB/4.2BSD/ https://www.tuhs.org/Archive/Distributions/UCB/4.2BSD/ or https://www.tuhs.org/Archive/Distributions/UCB/4.3BSD/ https://www.tuhs.org/Archive/Distributions/UCB/4.3BSD/. and https://man.freebsd.org/cgi/man.cgi?query=hsearch&apropos=0&sektion=3&manpath=FreeBSD+15.0-CURRENT&arch=default&format=html https://man.freebsd.org/cgi/man.cgi?query=hsearch&apropos=0&... says explicitly: > The hcreate(), hdestroy(), and hsearch() functions first appeared in AT&T System V UNIX. which... does seem a bit late for thinking it was a good idea to only support one hash table per process? that was in 01983, 6 years after the vax was introduced and 4 years after the 68000. i mean awk supported arbitrarily many hash tables in a single process in 7th edition unix, even before it had subroutines

Someone 2y ago
> i mean awk supported arbitrarily many hash tables in a single process This API supports that, too, as long as you don’t call one of the functions while another call is in progress. You get that for free if your process is single threaded. https://en.wikipedia.org/wiki/Thread_(computing)#Threading_models https://en.wikipedia.org/wiki/Thread_(computing)#Threading_m... says “History of threading models in Unix systems SunOS 4.x implemented light-weight processes or LWPs. NetBSD 2.x+, and DragonFly BSD implement LWPs as kernel threads (1:1 model)” According to Wikipedia, SunOS 4.0 is from 1988, NetBSD 2.0 from 2004, so I guess chances are good that AT&T System V UNIX didn’t support threads in user space programs.
- p_l 2y ago
  Adding threading support is why there was a bunch of interest in using Mach microkernel in Unix systems.
- kimixa 2y ago
  Or a signal handler? Even if there's a single kernel thread, if it can be interrupted while inside one of these functions you can hit the same sort of problem. Reentrancy was an issue on consumer devices well before multithreading was commonly supported there, after all
  - rdtsc 2y ago
    Good point. There are multiple levels of "safety". I think glibc API does a decent job marking and indicating which is which: https://sourceware.org/glibc/manual/2.40/html_node/POSIX-Safety-Concepts.html https://sourceware.org/glibc/manual/2.40/html_node/POSIX-Saf... Thread-Safe Async-Signal-Safe Async-Cancel-Safe (mostly limited to pthread_*cancel*) There is a host of other "safety" remarks also useful to keep in mind: https://sourceware.org/glibc/manual/2.40/html_node/Other-Safety-Remarks.html https://sourceware.org/glibc/manual/2.40/html_node/Other-Saf...
    - kragen 2y ago
      this isn't about safety, though; hcreate() and hsearch() don't support having two hash tables in the same process at the same time, not even in an unsafe way. that also makes them non-reentrant, but that isn't the main problem!
- kragen 2y ago
  you seem to be discussing what does or doesn't support multiple threads, but what we were talking about is what does or doesn't support multiple simultaneously existing hash tables, which hcreate() doesn't. i've edited my comment upthread to clarify (it's also true, as kimixa points out, that a single-threaded process with signal handlers isn't really single-threaded, but i don't think that's really the important consideration in this context) for what it's worth, it's not very difficult to use alarm() to invoke a context-switching subroutine to get preemptive user-space multithreading on unix without any kernel support. in theory you have to write the context-switching subroutine in assembly language, which isn't difficult at all; here's one i wrote in arm assembly for the arm eabi, for cooperative multithreading: .thumb_func .globl einyield einyield: push {r0, r4-r11, lr} @ save all callee-saved regs plus r0 ldr r0, =current_task_pointer ldr r1, [r0] str sp, [r1] @ save stack pointer in current eintask ldr r1, [r1, #4] @ load pointer to next eintask str r1, [r0] ldr sp, [r1] @ switch to next eintask's stack pop {r0, r4-r11, pc} @ return into einyielded context there (from http://canonical.org/~kragen/sw/dev3/einkornix.S http://canonical.org/~kragen/sw/dev3/einkornix.S) but in practice you can usually just use longjmp() preemptive multithreading requires you to save all the registers, not just the callee-saved registers, but so does signal handling, so you can usually just use the signal-handling machinery and use the above code (or its equivalent on your vax or 68000 or whatever) to context-switch between signal-handler stack frames
clbrmbr 2y ago
Don’t key prefixes take care of the need for an arbitrary number of tables?

tedunangst 2y ago

Probably started as a function in one program. Somebody copied it into a second program. Somebody wanted it in a third program and copied it into a library.

loeg 2y ago

They're really, really old. Dating to System V Unix. At the time it was pretty common to have stateful libc functions.

layer8 2y ago

You can look them up here in System V Interface Definition Issue 2 from 1986: http://www.bitsavers.org/pdf/att/unix/SVID/System_V_Interface_Definition_Issue_2_Volume_1_1986.pdf http://www.bitsavers.org/pdf/att/unix/SVID/System_V_Interfac.... It has a note “Future Directions: The restriction on only having one hash search table active at any given time will be removed.” Which of course couldn’t be done without breaking compatibility. Most programs at the time probably didn’t need more than one hash table, and it made for a simpler interface. (A program could in principle also work around the limitation by storing multiple values per hash table entry.) Most Unix libraries worked with global state at the time, since multi-threading also didn’t exist yet. I remember running into the limitation of only being able to have one lexer/parser grammar (via lex/yacc) per program.

kelnos 2y ago

Back when these functions were created, it was normal and expected for libc to store global state for a variety of things. Reentrancy wasn't really an issue that was considered then. (Though this particular API has an even weirder limitation: you can only create a single hash table at a time in your entire program!)