3 ms·

You got that wrong. For example, a fully thread-safe binary tree would be a tree data structure which allows concurrent insert operations on the same tree inst

You got that wrong. For example, a fully thread-safe binary tree would be a tree data structure which allows concurrent insert operations on the same tree instance. Whereas a reentrant binary tree allows concurrent inserts, but not on the same tree instance. So, your typical reentrant function takes care not to depend on or modify global state. But it might read from and/or write to an implementation-specific datastructure. Run a "zgrep -l reentrant /usr/share/man/man3/*.gz" which will convince you that's the usual notion. In particular, look at the manpage of qsort / qsort_r. You can see that making a function reentrant means typically converting static data dependencies into dynamic ones. The straightforward and very often simple approach is using function arguments (plus a contract that the arguments are not shared between "threads"). Making dependencies thread-local is another approach, and "errno" is a good example for that.

kazinator 11y ago
No kidding! For instance, the memcpy function is reentrant: but only as long as two contexts don't call it at the same time, and pass pointers to the same memory. It is not unconditionally reentrant. Some functions are; those that don't take pointers to anything as arguments. I covered that in my comment. An absolutely reentrant function could use memcpy internally (for instance to copy one object stack on its stack to another), so in other words, memcpy doesn't have bad properties that prevent it from being integrated into fully reentrant situation. An insert function that doesn't handle two threads inserting into the same tree isn't reentrant when called that way. It execution cannot be suspended and re-entered, except with different objects. The posix _r doesn't mean "absolutely reentrant"; it just means "this function doesn't do stupid things under the hood with globals that would prevent it from being used in reentrant code".
- jstimpfle 11y ago
  Why do you insist? Please argue with the POSIX people writing these manpages (and correct Wikipedia) if you think that they are all wrong and your nomenclature is the right one. What you talk about are pure functions.
  - kazinator 11y ago
    Only pure functions are absolutely reentrant. Reentrancy is logically weaker than thread safety. For instance, malloc is thread safe in POSIX, right? Yet, you cannot call it from a signal handler, at least not an asynchronous one. This is because it isn't reentrant. (POSIX would call it "async signal safe", but that's totally POSIX-specific terminology. POSIX uses some terms in POSIX specific ways, unsurprisingly. And "async signal safe" is something less than reentrant because functions can be made async signal safe by manipulating signal masks to avoid being re-entered.) I'm not the one who made this discussion about POSIX; my original comment wasn't about how POSIX uses "reentrant" (and I don't care, for that matter).
    - jstimpfle 11y ago
      > Reentrancy is logically weaker than thread safety. It isn't; neither is an implication of the other. If you mistrust manpages, lookup the definition on Wikipedia. But in many contexts "reentrant" is the better "thread-safe", as in "what you actually want" (give up mandatory locks to get scalability, composability...).
      - kazinator 11y ago
        Do you have an example of a function inherently reentrant (pure function), or a function or object used in a reentrant manner, that isn't also thread-safe? Wikipedia's first paragraph on Reentrancy completely agrees with me; I'm not inclined to change a word. POSIX doesn't define "reentrancy" or "reentrant", though it uses those terms. They are not defined in the documents it includes by normative reference. ISO C is one of those references and also throws the word around. ISO C refers to a document called ISO 2382, whose Part 1 gives a technical vocabulary; it might be defined there. By POSIX, of course I don't mean the man pages on a Linux system, but the actual specification. I refer the online version from time to time, specifically this one: http://pubs.opengroup.org/onlinepubs/9699919799/ http://pubs.opengroup.org/onlinepubs/9699919799/

kazinator 11y ago

No kidding! For instance, the memcpy function is reentrant: but only as long as two contexts don't call it at the same time, and pass pointers to the same memory. It is not unconditionally reentrant. Some functions are; those that don't take pointers to anything as arguments. I covered that in my comment. An absolutely reentrant function could use memcpy internally (for instance to copy one object stack on its stack to another), so in other words, memcpy doesn't have bad properties that prevent it from being integrated into fully reentrant situation. An insert function that doesn't handle two threads inserting into the same tree isn't reentrant when called that way. It execution cannot be suspended and re-entered, except with different objects. The posix _r doesn't mean "absolutely reentrant"; it just means "this function doesn't do stupid things under the hood with globals that would prevent it from being used in reentrant code".

jstimpfle 11y ago
Why do you insist? Please argue with the POSIX people writing these manpages (and correct Wikipedia) if you think that they are all wrong and your nomenclature is the right one. What you talk about are pure functions.
- kazinator 11y ago
  Only pure functions are absolutely reentrant. Reentrancy is logically weaker than thread safety. For instance, malloc is thread safe in POSIX, right? Yet, you cannot call it from a signal handler, at least not an asynchronous one. This is because it isn't reentrant. (POSIX would call it "async signal safe", but that's totally POSIX-specific terminology. POSIX uses some terms in POSIX specific ways, unsurprisingly. And "async signal safe" is something less than reentrant because functions can be made async signal safe by manipulating signal masks to avoid being re-entered.) I'm not the one who made this discussion about POSIX; my original comment wasn't about how POSIX uses "reentrant" (and I don't care, for that matter).
  - jstimpfle 11y ago
    > Reentrancy is logically weaker than thread safety. It isn't; neither is an implication of the other. If you mistrust manpages, lookup the definition on Wikipedia. But in many contexts "reentrant" is the better "thread-safe", as in "what you actually want" (give up mandatory locks to get scalability, composability...).
    - kazinator 11y ago
      Do you have an example of a function inherently reentrant (pure function), or a function or object used in a reentrant manner, that isn't also thread-safe? Wikipedia's first paragraph on Reentrancy completely agrees with me; I'm not inclined to change a word. POSIX doesn't define "reentrancy" or "reentrant", though it uses those terms. They are not defined in the documents it includes by normative reference. ISO C is one of those references and also throws the word around. ISO C refers to a document called ISO 2382, whose Part 1 gives a technical vocabulary; it might be defined there. By POSIX, of course I don't mean the man pages on a Linux system, but the actual specification. I refer the online version from time to time, specifically this one: http://pubs.opengroup.org/onlinepubs/9699919799/ http://pubs.opengroup.org/onlinepubs/9699919799/