Re: thread safe functions

Re: thread safe functions

[Ken Raeburn]

(switching to guile-devel from guile-user since I think this is more of a developers' issue)

On Aug 18, 2010, at 11:56, Andy Wingo wrote (quoting the manual):
>       Thus, you need to put in additional synchronizations when multiple
>    threads want to use a single hashtable, or any other mutable Scheme
>    object.

Unfortunately this applies to some internals of the implementation too.  For example, "set-object-property!" and friends use a hash table and assoc lists internally.  There's a "critical section" protecting the assoc list manipulation in set-object-property!, but nothing else; I doubt using it on two objects not already in the hash table is safe (in the sense of both concurrent calls taking effect, as if made serially in unspecified order), based on the text Andy quoted about hash tables.  But application code calling set-object-property! isn't explicitly operating on a mutable Scheme object (and a Scheme coder might reasonably assume that the properties were stored with the object, not in a global hash table), so the above advice from the manual doesn't seem to apply.

scm_c_issue_deprecation_warning and scm_c_register_extension don't look thread-safe to me (in the sense described above).  Both maintain linked lists without locking, and these aren't even implicitly Scheme objects.  Both risk losing the new list entries in the face of concurrent calls.

That's just from a spot check; I'm not even trying to be thorough.
And don't get me going on memory ordering models....

To be honest, I wouldn't trust libguile in a multithreaded application without much more careful analysis, not just of the code, but of the assumptions being made and whether they're actually valid for various processors (not just the relatively friendly x86) and compilers.  Without that sort of analysis, I think "use mutexes everywhere" is the only safe approach, and libguile certainly isn't doing that.

Ken

Re: thread safe functions

[Andy Wingo]

Hi Ken,

On Sat 21 Aug 2010 17:57, Ken Raeburn <raeburn@raeburn.org> writes:

> On Aug 18, 2010, at 11:56, Andy Wingo wrote (quoting the manual):
>> Thus, you need to put in additional synchronizations when multiple
>> threads want to use a single hashtable, or any other mutable Scheme
>>    object.
>
> Unfortunately this applies to some internals of the implementation too.
> For example, "set-object-property!" and friends use a hash table and
> assoc lists internally.

Fixed, thanks.

> scm_c_issue_deprecation_warning and scm_c_register_extension don't look
> thread-safe to me (in the sense described above).

Fixed also.

> That's just from a spot check; I'm not even trying to be thorough.

I await your more thorough check :)

> And don't get me going on memory ordering models....

I'm interested!

> To be honest, I wouldn't trust libguile in a multithreaded application
> without much more careful analysis, not just of the code, but of the
> assumptions being made and whether they're actually valid for various
> processors (not just the relatively friendly x86) and compilers.
> Without that sort of analysis, I think "use mutexes everywhere" is the
> only safe approach, and libguile certainly isn't doing that.

I think we agree, but I prefer to paint this in a more optimistic
light -- that things are mostly there, but bugs are possible. Bug fixes
are also possible :)

Cheers,

Andy
-- 
http://wingolog.org/

Re: thread safe functions

[Ken Raeburn]

On Aug 28, 2010, at 15:20, Andy Wingo wrote:
>> Unfortunately this applies to some internals of the implementation too.
>> For example, "set-object-property!" and friends use a hash table and
>> assoc lists internally.
> 
> Fixed, thanks.
> 
>> scm_c_issue_deprecation_warning and scm_c_register_extension don't look
>> thread-safe to me (in the sense described above).
> 
> Fixed also.

Thanks!

Though... looking at deprecation.c, I'd suggest not printing stuff while the lock is held; just keep track of whether it needs to be printed, and do the printing after releasing it.  Partly because locks should be held only briefly, and printing can block, but also if the error port can call back into other Scheme code, which may call a deprecated function, then you could get an error trying to acquire the lock (which we won't notice, because we never check), or deadlock.

I was starting to look through the port code for this, but got distracted by scm_ptobs, a pointer which appears to be dynamically reallocated as needed when scm_make_port_type is called.  Which means every function that reads it should be locking the same mutex used when updating it; in this case, that appears to be the generic "critical section" stuff, and it looks like we're not doing that.

So, hmm, where else do we use hash tables internally?

foreign.c: pointer_weak_refs is a weakly keyed hash table, which we add things to without locking.

gc.c: scm_protects is protected; good.

instructions.c: Can scm_lookup_instruction_by_name be called the "first" time from two threads concurrently?  It uses a hash table stored in a static variable, and the variable is updated before the hash table is filled in.  (Even if you simply assign to the variable afterwards, there's no requirement that the compiler or CPU not reorder those assignments.)  But, as an aside, do we need all that in C, or could instruction-list just export a big Scheme list that could be examined (or turned into a hash table) by Scheme versions of the other functions?

keywords.c: A critical section protects keyword_obarray; good.

modules.c: scm_pre_modules_obarray doesn't look protected.

ports.c: scm_i_port_weak_hash is protected in some places, others I haven't investigated further.  But in scm_c_port_for_each, it looks to me as though, if ports are being created while the function is setting up, you could end up raising an exception if scm_internal_hash_fold iterates over more ports than were in the hash table when the count was initially taken (and the vector size set).

procproc.c: There's a mutex to protect overrides, but it looks like set-procedure-property! doesn't use it correctly; it should look more like set-object-property! does.

properties.c: I'm not familiar with this code at all, but I'd guess properties_whash should be protected.  Though I wonder if the call-out from primitive-property-ref could invoke other primitive-property functions, causing a deadlock if it isn't done carefully.

smob.c: I don't think tramp_weak_map is adequately protected, but I'm not certain.

srcprop.c: scm_source_whash isn't protected; it also appears to be exposed by the name "source-whash" to Scheme code, which wouldn't be able to use a mutex defined and used purely in the C code.

(What's that, four different kinds of property-list mappings, all implemented separately?)

struct.c: Even calling struct-vtable-name can cause a hash table entry to be created, it appears.  So that's not thread-safe, never mind the call to actually change the name.

symbols.c: I don't think 'symbols' is handled safely.  But this code is all starting to run together in my mind. :-)

weaks.c: Is only making things for Scheme code, where we're making locking the user's problem.

It would be a bit easier if hash tables themselves were thread-safe.  A read/write lock might make more sense than a simple mutex though, if reading is more common than writing.  In my experience they sometimes perform worse than simple mutexes, so they're a win mainly for concurrent reading.

Of course, hash tables aren't the only places where we can have problems, and I'm not even touching on hash tables that might be created by Scheme code (but exposed to users with APIs that don't scream "unsafe hash table used here!"), but I've already spent my afternoon and evening on this.


>> That's just from a spot check; I'm not even trying to be thorough.
> 
> I await your more thorough check :)

Yeah, in my copious free time... :-(  Maybe some more next weekend, if I'm not doing the stuff I was supposed to get done last weekend.

>> And don't get me going on memory ordering models....
> 
> I'm interested!

There's a lot to read out there, and I'm no expert, but the main idea is, depending on the specific architecture, memory loads and stores can be almost arbitrarily reordered between CPUs unless you do something to prevent it.

So, if you do something like:
(preconditions: z is a pair visible to both threads; SCM_CAR(z) is a pair)
thread 1:
  allocate cons cell x
  SCM_SETCAR(x, v1)
  SCM_SETCDR(x, v2)
  SCM_SETCAR(z, x)
thread 2:
  t=SCM_CAR(z)
  read SCM_CAR(t)

Assuming that reads and writes of SCM values are atomic, thread 2 will read t as either the old value, or x.  If it's x, though, SCM_CAR(x) might *not* be read back as v1, but whatever garbage was in there when (or before) the cell was allocated.  And instead of the CAR slot could also be some bits in a non-immediate value that indicate a subtype, causing the reading thread to call the wrong routines to manipulate it.

Basically, any time you make an object handle visible to other threads, you need to make sure the object's contents have been stored first, and the other processor hasn't loaded that location yet -- or, if it might be cached, it knows to flush that entry.  (Multiple threads can run on one processor, or multiple cores sharing a cache, in which case it's probably not a problem.  A thread can also be moved between cores, but the OS is responsible for keeping things in sync in that case.)  Changing an object already visible to other threads probably requires at least as much caution, but given that malloc/free are likely to reuse storage, it's not even reasonable to assume that a location in a freshly allocated cell isn't cached by some other processor from back when it was part of some other object, so, I think actually the two problems are largely equivalent; a visible live object might merely be more likely to be in another cache.

According to the Wikipedia article on memory ordering, the Alpha has (some of them are still out there) a really interesting property: reordering dependent loads, i.e., loading data before loading the pointer to the data.  It isn't described in detail, but I assume it's related to speculative loading or something.

Mutexes encapsulate "something to prevent it" pretty well; hacks like "volatile" don't, though they can get the compiler somewhat out of the way.

Of course, adding a mutex to every non-immediate value is far too expensive in memory use, even if the almost complete lack of contention means the locking can probably be done with few context switches into the kernel.  Using one global mutex can work, but it basically means only one thread can be examining or manipulating Guile objects at a time.  For I/O or DNS lookups, that's probably fine, but we do want to be able to manipulate data structures concurrently.

There are lower-level facilities generally available, like memory-barrier instructions and atomic operations (usually compare-and-swap, or load-link/store-conditional), which could probably be used more efficiently; there are even lock-free algorithms for doing some simple data structures safely using these primitives.  But the details vary, and doing more synchronization than you're actually required to can hurt performance, so you really need to tune it well.  This is the sort of thing that kernel and C-library developers sometimes spend a lot of effort trying to get right, so that the kernel and libc facilities (e.g., mutexes) will be both correct and efficient.


To make it worse, the compiler can reorder memory access instructions if it can show there aren't aliasing problems (i.e., that the locations being accessed cannot be the same assuming the source code is following the rules of the language -- and that last clause may let a compiler reorder accesses via "int" and "double" types that happen to map to the same location!), and it can even write (or not write) intermediate values to an output location.

So, for example, in:

  register SCM x = ...;   // so it can't be aliased by memory accesses
  SCM_SETCDR(x, v1);
  SCM_SETCAR(x, v2);

the compiler could change the order of the writes, since it knows the locations are different (because there's a fixed nonzero offset between them), and under the specs of the C language there's no way to stop in between the two statements and examine the values stored, so the two versions are the same under the "as if" rule that says only the overall side effects matter.  The original order will often be retained to help with debugging, because no optimization benefit was found in reordering, etc., but you can't make your program's semantics depend on that.

Or:
  register int a, b, c;
  n = foo() + a*b*c;   // store to mem
could -- at least theoretically -- be implemented as:
  n = foo();
  tmp = a*b;
  tmp *= c;
  n += tmp;
though offhand I'm having a hard time thinking of a realistic case in which a compiler would be likely to do that.

This is where "volatile" would help a bit.  But simply making all non-immediate objects volatile would probably be overkill.


Now, how *much* is this a problem for user-mode programs in practice?  I don't know.  I've read a few papers, but haven't actually worked on code at this level or researched the architecture details of many processors and memory subsystems.  (The multiprocessing stuff I've done all used mutexes, if not always very efficiently.)  A couple of web pages I've run across have suggested that some published processor errata have pointed out memory ordering problems, so the actual requirements for a given processor family may be stricter than advertised by the architecture manuals.  And sometimes updates to the architecture manuals can change these specs.  I think we'd need someone with more low-level experience to help answer that.  I suspect many programs can run just fine for a long time without race conditions in them actually causing visible problems; then, the next day, maybe they'll crash.

I recommend the "Memory ordering" page at wikipedia as a good starting point for reading up on it, and the first couple of references at least.  Also Boehm's paper "Threads Cannot be Implemented as a Library" is an interesting read about the compiler interactions, though if we're trying to bypass having to use locks altogether, the problems we face are probably larger than the ones he describes.

> I think we agree, but I prefer to paint this in a more optimistic
> light -- that things are mostly there, but bugs are possible. Bug fixes
> are also possible :)

You might guess from the above that I don't think they're mostly there.  That bugs are possible, yes, that I'll grant you. ;-)

A real review should check:
 * any non-const static-storage variables defined in the library, and how they're used;
 * any functions modifying objects, to determine the effect of concurrent calls;
 * any uses of those functions or objects from our C or Scheme code, to see if we're presenting the correct semantics in the face of concurrent calls;
 * that we actually specify the semantics, or when results are undefined, clearly;
 * anything dealing with OS interfaces (or other library APIs) that aren't thread-safe;
And if those aren't going to take long enough already:
 * getting *real* answers to the memory ordering issues;
 * possibly reviewing every function manipulating memory for ordering issues;
 * probably more.

Then, I might have some confidence that "things are mostly there."  I don't think it's going to happen at all for 2.0, and I don't expect to have time myself to do anything more than little bits of work on the first part of the list, if even that much, in the near future.

My work today didn't do any of this; I just started with looking over the patches you checked in, and then ran "grep hash_ta *.[ch]" in libguile, to see where else we've got hash tables, since we've already seen that they're a problem in at least one other place.  But even with just that, I found quite a few things that I think need to be looked at.

Ken

Re: thread safe functions

[Andy Wingo]

Hey Ken,

I got tired of seeing your mail marked as starred in my inbox, so I
decided to take a look at it ;-)

You were writing about threadsafe access to global variables.

On Sun 29 Aug 2010 03:33, Ken Raeburn <raeburn@raeburn.org> writes:

> looking at deprecation.c, I'd suggest not printing stuff while the
> lock is held

Fixed, thanks.

> I was starting to look through the port code for this, but got
> distracted by scm_ptobs, a pointer which appears to be dynamically
> reallocated as needed when scm_make_port_type is called.  Which means
> every function that reads it should be locking the same mutex used when
> updating it; in this case, that appears to be the generic "critical
> section" stuff, and it looks like we're not doing that.

Yeah, and it is exported to users of libguile.  Fun, no?  I added a
comment to the header about its impending deprecation, but that's all I
have time for right now.

> foreign.c: pointer_weak_refs is a weakly keyed hash table, which we add
> things to without locking.

Fixed.

> instructions.c: Can scm_lookup_instruction_by_name be called the "first"
> time from two threads concurrently?

Yes; fixed.

> modules.c: scm_pre_modules_obarray doesn't look protected.

Doesn't need to be; added a comment to that effect.

> ports.c: scm_i_port_weak_hash is protected in some places, others I
> haven't investigated further.  But in scm_c_port_for_each, it looks to
> me as though, if ports are being created while the function is setting
> up, you could end up raising an exception if scm_internal_hash_fold
> iterates over more ports than were in the hash table when the count was
> initially taken (and the vector size set).

Fixed scm_c_port_for_each, and access to scm_i_port_weak_hash.  But the
scm_ptobs situation is as unresolved as ever.

> procproc.c: There's a mutex to protect overrides, but it looks like
> set-procedure-property! doesn't use it correctly; it should look more
> like set-object-property! does.

I'm going to punt on this one, since it cannot access the hash table in
an inconsistent state, and I don't care enough about what happens when
multiple threads start changing the same procedure property (a fairly
legacy interface) at once.  Furthermore there is always (assq-set!
(procedure-properties foo) 'bar) to contend with...

> properties.c: I'm not familiar with this code at all, but I'd guess
> properties_whash should be protected.  Though I wonder if the call-out
> from primitive-property-ref could invoke other primitive-property
> functions, causing a deadlock if it isn't done carefully.

I went ahead and deprecated this whole mess, it was only used for object
properties, which I reimplemented using weak hash tables and a lock.

> symbols.c: I don't think 'symbols' is handled safely.  But this code is
> all starting to run together in my mind. :-)

I think I fixed this one a month ago or so.

> smob.c: I don't think tramp_weak_map is adequately protected, but I'm
> not certain.
>
> srcprop.c: scm_source_whash isn't protected; it also appears to be
> exposed by the name "source-whash" to Scheme code, which wouldn't be
> able to use a mutex defined and used purely in the C code.
>
> (What's that, four different kinds of property-list mappings, all
> implemented separately?)

Tell me about it...

> struct.c: Even calling struct-vtable-name can cause a hash table entry
> to be created, it appears.  So that's not thread-safe, never mind the
> call to actually change the name.
>
> weaks.c: Is only making things for Scheme code, where we're making
> locking the user's problem.

At this point I got tired.  But sending this mail to the list will
requeue this work, so hey...

> It would be a bit easier if hash tables themselves were thread-safe.  A
> read/write lock might make more sense than a simple mutex though, if
> reading is more common than writing.  In my experience they sometimes
> perform worse than simple mutexes, so they're a win mainly for
> concurrent reading.

Yeah, that might be a good idea. For later, though.

> Of course, hash tables aren't the only places where we can have
> problems, and I'm not even touching on hash tables that might be created
> by Scheme code (but exposed to users with APIs that don't scream "unsafe
> hash table used here!"), but I've already spent my afternoon and evening
> on this.

Indeed, and I just spent some hours on it too...

>>> And don't get me going on memory ordering models....
>> 
>> I'm interested!

Thanks for the notes on this, it was an interesting read.

> A real review should check:
>  * any non-const static-storage variables defined in the library, and
> how they're used;
>  * any functions modifying objects, to determine the effect of
> concurrent calls;
>  * any uses of those functions or objects from our C or Scheme code, to
> see if we're presenting the correct semantics in the face of concurrent
> calls;
>  * that we actually specify the semantics, or when results are
> undefined, clearly;
>  * anything dealing with OS interfaces (or other library APIs) that
> aren't thread-safe;
> And if those aren't going to take long enough already:
>  * getting *real* answers to the memory ordering issues;
>  * possibly reviewing every function manipulating memory for ordering
> issues;
>  * probably more.
>
> Then, I might have some confidence that "things are mostly there."  I
> don't think it's going to happen at all for 2.0, and I don't expect to
> have time myself to do anything more than little bits of work on the
> first part of the list, if even that much, in the near future.

Indeed, it certainly won't all happen for 2.0.  Maybe during 2.0 and
changes for 2.2.  Keep the reviews coming, though...

Cheers,

Andy
-- 
http://wingolog.org/

Re: thread safe functions

[Ken Raeburn]

On Feb 10, 2011, at 17:19, Andy Wingo wrote:
> Hey Ken,
> 
> I got tired of seeing your mail marked as starred in my inbox, so I
> decided to take a look at it ;-)

Thanks! :-)
I'm sorry I haven't had time in a while to investigate more.

>> symbols.c: I don't think 'symbols' is handled safely.  But this code is
>> all starting to run together in my mind. :-)
> 
> I think I fixed this one a month ago or so.

Hmm... maybe.  It looks to me like it'll probably be okay, *if* you assume that updates aren't seen out-of-order by another thread.  If updates can be seen out of order, then the newly allocated vector in scm_i_rehash may still be seen as having garbage values in its data slots by the time SCM_SET_HASHTABLE_VECTOR makes it visible to other threads that aren't using any synchronization primitives.

BTW, I like this writeup: http://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html .  It shows how (on Alpha, with its weak memory ordering model) even an explicit memory barrier in the writing thread isn't enough to guarantee that a reading thread in another CPU will see changes "in order".

> At this point I got tired.  But sending this mail to the list will
> requeue this work, so hey...

Fair enough. :)

Ken

Re: thread safe functions

[Andy Wingo]

On Tue 15 Feb 2011 17:00, Ken Raeburn <raeburn@raeburn.org> writes:

> On Feb 10, 2011, at 17:19, Andy Wingo wrote:
>>> symbols.c: I don't think 'symbols' is handled safely.  But this code
> is
>>> all starting to run together in my mind. :-)
>> 
>> I think I fixed this one a month ago or so.
>
> Hmm... maybe.  It looks to me like it'll probably be okay, *if* you
> assume that updates aren't seen out-of-order by another thread.

Indeed, you are right.  Fixed.  Did not appear to have any performance
impact, either...

Andy
-- 
http://wingolog.org/

Re: thread safe functions

[Ken Raeburn]

On Feb 10, 2011, at 17:19, Andy Wingo wrote:
>> procproc.c: There's a mutex to protect overrides, but it looks like
>> set-procedure-property! doesn't use it correctly; it should look more
>> like set-object-property! does.
> 
> I'm going to punt on this one, since it cannot access the hash table in
> an inconsistent state, and I don't care enough about what happens when
> multiple threads start changing the same procedure property (a fairly
> legacy interface) at once.  Furthermore there is always (assq-set!
> (procedure-properties foo) 'bar) to contend with...

It doesn't need to be the same property; I think different threads setting different new properties on a procedure in parallel may lose.  Both read the old property list, then each in turn acquires the lock and sets a new property list consisting of the new property added to the original list.  So the second one "wins", and the first update disappears.

Ken

Re: thread safe functions

[Andy Wingo]

On Tue 15 Feb 2011 18:18, Ken Raeburn <raeburn@raeburn.org> writes:

> On Feb 10, 2011, at 17:19, Andy Wingo wrote:
>>> procproc.c: There's a mutex to protect overrides, but it looks like
>>> set-procedure-property! doesn't use it correctly; it should look more
>>> like set-object-property! does.
>> 
>> I'm going to punt on this one, since it cannot access the hash table
> in
>> an inconsistent state, and I don't care enough about what happens when
>> multiple threads start changing the same procedure property (a fairly
>> legacy interface) at once.  Furthermore there is always (assq-set!
>> (procedure-properties foo) 'bar) to contend with...
>
> It doesn't need to be the same property; I think different threads
> setting different new properties on a procedure in parallel may lose.

Indeed.  Fixed.

Andy
-- 
http://wingolog.org/

Re: thread safe functions

[Andy Wingo]

Hi Ken,

You mailed a long time ago with some threadsafety issues and I think
I've finally gotten to all of the ones you have mentioned.

You made good points regarding memory ordering also, but I'm going to
let that slide for now, as it didn't have specific bugs.  Should you be
motivated to review further, please send separate mails.  I know that
sounds silly but it looks less daunting that way.

On Thu 10 Feb 2011 23:19, Andy Wingo <wingo@pobox.com> writes:

> On Sun 29 Aug 2010 03:33, Ken Raeburn <raeburn@raeburn.org> writes:
>
>> I was starting to look through the port code for this, but got
>> distracted by scm_ptobs, a pointer which appears to be dynamically
>> reallocated as needed when scm_make_port_type is called.  Which means
>> every function that reads it should be locking the same mutex used when
>> updating it; in this case, that appears to be the generic "critical
>> section" stuff, and it looks like we're not doing that.
>
> Yeah, and it is exported to users of libguile.  Fun, no?  I added a
> comment to the header about its impending deprecation, but that's all I
> have time for right now.

Actually this bug is still present.

>> smob.c: I don't think tramp_weak_map is adequately protected, but I'm
>> not certain.

Fixed.

>> srcprop.c: scm_source_whash isn't protected; it also appears to be
>> exposed by the name "source-whash" to Scheme code, which wouldn't be
>> able to use a mutex defined and used purely in the C code.

Fixed also.

>> struct.c: Even calling struct-vtable-name can cause a hash table entry
>> to be created, it appears.  So that's not thread-safe, never mind the
>> call to actually change the name.

Fixed to a degree earlier; fixed more definitively now.

Happy hacking,

Andy
-- 
http://wingolog.org/