Thread-unsafe initialization problems in Guile

Thread-unsafe initialization problems in Guile

[Mark H Weaver]

It would be good to fix these before 2.0.7 is released, but I'm a bit
uncertain of how best to do so, and I don't have time at the moment.

./posix.c:1375:            make_rw_port = scm_c_private_variable ("ice-9 popen",
./debug.c:217:    local_eval_var = scm_c_public_variable ("ice-9 local-eval", "local-eval");
./strports.c:541:      eval_string = scm_c_public_lookup ("ice-9 eval-string", "eval-string");

     Mark

Re: Thread-unsafe initialization problems in Guile

[Ludovic Courtès]

Hi,

Mark H Weaver <mhw@netris.org> skribis:

> It would be good to fix these before 2.0.7 is released, but I'm a bit
> uncertain of how best to do so, and I don't have time at the moment.
>
> ./posix.c:1375:            make_rw_port = scm_c_private_variable ("ice-9 popen",
> ./debug.c:217:    local_eval_var = scm_c_public_variable ("ice-9 local-eval", "local-eval");
> ./strports.c:541:      eval_string = scm_c_public_lookup ("ice-9 eval-string", "eval-string");

I’m actually not sure what you mean here.

Anyway, I think we ought to release 2.0.7 now.  And yes, there will be a
2.0.8 with a number of additional fixes.  :-)

WDYT?

Ludo’.

Re: Thread-unsafe initialization problems in Guile

[Mark H Weaver]

ludo@gnu.org (Ludovic Courtès) writes:

> Mark H Weaver <mhw@netris.org> skribis:
>
>> It would be good to fix these before 2.0.7 is released, but I'm a bit
>> uncertain of how best to do so, and I don't have time at the moment.
>>
>> ./posix.c:1375:            make_rw_port = scm_c_private_variable ("ice-9 popen",
>> ./debug.c:217:    local_eval_var = scm_c_public_variable ("ice-9 local-eval", "local-eval");
>> ./strports.c:541:      eval_string = scm_c_public_lookup ("ice-9 eval-string", "eval-string");
>
> I’m actually not sure what you mean here.

Those are three bugs where a global static variable is lazily
initialized in a way that is not thread-safe.  The one in strports.c
actually caused a reproducible crash bug for a user who created multiple
threads, each of which called scm_eval_string.

Consider the bug in scm_local_eval, which I'm ashamed to say was written
by me before I educated myself on weakly-ordered memory models:

SCM
scm_local_eval (SCM exp, SCM env)
{
  static SCM local_eval_var = SCM_BOOL_F;

  if (scm_is_false (local_eval_var))
    local_eval_var = scm_c_public_variable ("ice-9 local-eval", "local-eval");

  return scm_call_2 (SCM_VARIABLE_REF (local_eval_var), exp, env);
}

The problem is that it's possible for a thread to see a non-#f value for
'local_eval_var' before it sees the memory it points to properly
initialized.

> Anyway, I think we ought to release 2.0.7 now.  And yes, there will be a
> 2.0.8 with a number of additional fixes.  :-)

Okay, that's fine.  We can fix these for 2.0.8.

    Thanks,
      Mark

Re: Thread-unsafe initialization problems in Guile

[Andy Wingo]

Hi,

On Thu 29 Nov 2012 23:42, Mark H Weaver <mhw@netris.org> writes:

> SCM
> scm_local_eval (SCM exp, SCM env)
> {
>   static SCM local_eval_var = SCM_BOOL_F;
>
>   if (scm_is_false (local_eval_var))
>     local_eval_var = scm_c_public_variable ("ice-9 local-eval", "local-eval");
>
>   return scm_call_2 (SCM_VARIABLE_REF (local_eval_var), exp, env);
> }
>
> The problem is that it's possible for a thread to see a non-#f value for
> 'local_eval_var' before it sees the memory it points to properly
> initialized.

scm_c_public_variable is not idempotent?

If it is, where is the problem?

Andy
-- 
http://wingolog.org/

Re: Thread-unsafe initialization problems in Guile

[Mark H Weaver]

Hi Andy,

Andy Wingo <wingo@pobox.com> writes:
> On Thu 29 Nov 2012 23:42, Mark H Weaver <mhw@netris.org> writes:
>
>> SCM
>> scm_local_eval (SCM exp, SCM env)
>> {
>>   static SCM local_eval_var = SCM_BOOL_F;
>>
>>   if (scm_is_false (local_eval_var))
>>     local_eval_var = scm_c_public_variable ("ice-9 local-eval", "local-eval");
>>
>>   return scm_call_2 (SCM_VARIABLE_REF (local_eval_var), exp, env);
>> }
>>
>> The problem is that it's possible for a thread to see a non-#f value for
>> 'local_eval_var' before it sees the memory it points to properly
>> initialized.
>
> scm_c_public_variable is not idempotent?

It is idempotent as far as I know, but that's not the problem.  The
problem is that in modern weakly-ordered memory models, there is no
guarantee that thread B will see writes in the same order as they were
performed by thread A.

For example, if (ice-9 local-eval) has not yet been loaded when thread A
calls 'scm_local_eval', then thread A will load the (ice-9 local-eval)
module, allocate and initialize the associated SCM variable objects, and
finally write 'local_eval_var' to point to one of these variable
objects.  However, in the absence of thread synchronization, thread B
may see 'local_eval_var' set to a non-#f value before it sees the writes
that initialized the variable object to which 'local_eval_var' points.
In other words, thread B may end up reading a SCM variable object that
has not yet been initialized in its timeline.

For a good introduction to what is needed to write robust multithreaded
code on modern weakly-ordered memory architectures, I recommend the
following article:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2480.html

   Regards,
     Mark

Re: Thread-unsafe initialization problems in Guile

[Mark H Weaver]

I wrote:
> For a good introduction to what is needed to write robust multithreaded
> code on modern weakly-ordered memory architectures, I recommend the
> following article:
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2480.html

and if you want a deeper understanding of what's going on in
the hardware to cause these problems, see Paul McKenney's paper
"Memory Barriers: a Hardware View for Software Hackers":

http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.06.07c.pdf

    Mark

Re: Thread-unsafe initialization problems in Guile

[Mark H Weaver]

Here's an article from a reputable source that backs up my claim that
the lazy-initialization pattern that we use in a few places is not
thread-safe:

  http://www.ibm.com/developerworks/java/library/j-dcl/index.html

Here are the thread-unsafe lazy initializations that I'm aware of:

./posix.c:1375:            make_rw_port = scm_c_private_variable ("ice-9 popen",
./debug.c:217:    local_eval_var = scm_c_public_variable ("ice-9 local-eval", "local-eval");
./strports.c:541:      eval_string = scm_c_public_lookup ("ice-9 eval-string", "eval-string");

In each of these cases, we have two options: (1) synchronize on every
access of the lazily-initialized variable (including reads), or (2)
abandon lazy initialization.

  Thoughts?
    Mark

[PATCH] Fix thread-unsafe lazy initializations

[Mark H Weaver]

[-- Attachment #1: Type: text/plain, Size: 79 bytes --]

Here's my proposed patch to fix these problems.
What do you think?

    Mark



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: [PATCH] Fix thread-unsafe lazy initializations --]
[-- Type: text/x-diff, Size: 4085 bytes --]

From dadcb1512569c1be039fc75f0a2967e370939e42 Mon Sep 17 00:00:00 2001
From: Mark H Weaver <mhw@netris.org>
Date: Thu, 28 Feb 2013 17:56:58 -0500
Subject: [PATCH] Fix thread-unsafe lazy initializations.

* libguile/debug.c (scm_local_eval):
  libguile/ports.c (scm_current_warning_port):
  libguile/strports.c (scm_eval_string_in_module): Perform
  lazy-initialization while holding a mutex.  Use SCM_UNDEFINED as the
  uninitialized value.  Use 'scm_c_*_variable'.

* doc/ref/api-modules.texi (Accessing Modules from C): Fix
  'my_eval_string' example to be thread-safe.
---
 doc/ref/api-modules.texi |   13 +++++++------
 libguile/debug.c         |    8 ++++++--
 libguile/ports.c         |   12 ++++++++----
 libguile/strports.c      |    9 ++++++---
 4 files changed, 27 insertions(+), 15 deletions(-)

diff --git a/doc/ref/api-modules.texi b/doc/ref/api-modules.texi
index 17ab462..3d111c4 100644
--- a/doc/ref/api-modules.texi
+++ b/doc/ref/api-modules.texi
@@ -942,14 +942,15 @@ the @var{name} is not bound in the module, signals an error.  Returns a
 variable, always.
 
 @example
-SCM my_eval_string (SCM str)
-@{
-  static SCM eval_string_var = SCM_BOOL_F;
+static SCM eval_string_var;
 
-  if (scm_is_false (eval_string_var))
-    eval_string_var =
-      scm_c_public_lookup ("ice-9 eval-string", "eval-string");
+void my_init (void)
+@{
+  eval_string_var = scm_c_public_lookup ("ice-9 eval-string", "eval-string");
+@}
 
+SCM my_eval_string (SCM str)
+@{
   return scm_call_1 (scm_variable_ref (eval_string_var), str);
 @}
 @end example
diff --git a/libguile/debug.c b/libguile/debug.c
index b1a90d8..9e6328b 100644
--- a/libguile/debug.c
+++ b/libguile/debug.c
@@ -211,10 +211,14 @@ SCM_DEFINE (scm_debug_hang, "debug-hang", 0, 1, 0,
 SCM
 scm_local_eval (SCM exp, SCM env)
 {
-  static SCM local_eval_var = SCM_BOOL_F;
+  static SCM local_eval_var = SCM_UNDEFINED;
+  static scm_i_pthread_mutex_t local_eval_var_mutex
+    = SCM_I_PTHREAD_MUTEX_INITIALIZER;
 
-  if (scm_is_false (local_eval_var))
+  scm_i_scm_pthread_mutex_lock (&local_eval_var_mutex);
+  if (SCM_UNBNDP (local_eval_var))
     local_eval_var = scm_c_public_variable ("ice-9 local-eval", "local-eval");
+  scm_i_pthread_mutex_unlock (&local_eval_var_mutex);
 
   return scm_call_2 (SCM_VARIABLE_REF (local_eval_var), exp, env);
 }
diff --git a/libguile/ports.c b/libguile/ports.c
index 55808e2..8737a76 100644
--- a/libguile/ports.c
+++ b/libguile/ports.c
@@ -418,10 +418,14 @@ SCM_DEFINE (scm_current_error_port, "current-error-port", 0, 0, 0,
 SCM
 scm_current_warning_port (void)
 {
-  static SCM cwp_var = SCM_BOOL_F;
-
-  if (scm_is_false (cwp_var))
-    cwp_var = scm_c_private_lookup ("guile", "current-warning-port");
+  static SCM cwp_var = SCM_UNDEFINED;
+  static scm_i_pthread_mutex_t cwp_var_mutex
+    = SCM_I_PTHREAD_MUTEX_INITIALIZER;
+
+  scm_i_scm_pthread_mutex_lock (&cwp_var_mutex);
+  if (SCM_UNBNDP (cwp_var))
+    cwp_var = scm_c_private_variable ("guile", "current-warning-port");
+  scm_i_pthread_mutex_unlock (&cwp_var_mutex);
   
   return scm_call_0 (scm_variable_ref (cwp_var));
 }
diff --git a/libguile/strports.c b/libguile/strports.c
index 14cc93f..d1b293c 100644
--- a/libguile/strports.c
+++ b/libguile/strports.c
@@ -534,13 +534,16 @@ SCM_DEFINE (scm_eval_string_in_module, "eval-string", 1, 1, 0,
             "procedure returns.")
 #define FUNC_NAME s_scm_eval_string_in_module
 {
-  static SCM eval_string = SCM_BOOL_F, k_module = SCM_BOOL_F;
+  static SCM eval_string = SCM_UNDEFINED, k_module = SCM_UNDEFINED;
+  static scm_i_pthread_mutex_t init_mutex = SCM_I_PTHREAD_MUTEX_INITIALIZER;
 
-  if (scm_is_false (eval_string))
+  scm_i_scm_pthread_mutex_lock (&init_mutex);
+  if (SCM_UNBNDP (eval_string))
     {
-      eval_string = scm_c_public_lookup ("ice-9 eval-string", "eval-string");
+      eval_string = scm_c_public_variable ("ice-9 eval-string", "eval-string");
       k_module = scm_from_locale_keyword ("module");
     }
+  scm_i_pthread_mutex_unlock (&init_mutex);
   
   if (SCM_UNBNDP (module))
     module = scm_current_module ();
-- 
1.7.10.4

Re: [PATCH] Fix thread-unsafe lazy initializations

[Ludovic Courtès]

Mark H Weaver <mhw@netris.org> skribis:

> From dadcb1512569c1be039fc75f0a2967e370939e42 Mon Sep 17 00:00:00 2001
> From: Mark H Weaver <mhw@netris.org>
> Date: Thu, 28 Feb 2013 17:56:58 -0500
> Subject: [PATCH] Fix thread-unsafe lazy initializations.
>
> * libguile/debug.c (scm_local_eval):
>   libguile/ports.c (scm_current_warning_port):
>   libguile/strports.c (scm_eval_string_in_module): Perform
>   lazy-initialization while holding a mutex.  Use SCM_UNDEFINED as the
>   uninitialized value.  Use 'scm_c_*_variable'.
>
> * doc/ref/api-modules.texi (Accessing Modules from C): Fix
>   'my_eval_string' example to be thread-safe.

Looks good to me.

> --- a/doc/ref/api-modules.texi
> +++ b/doc/ref/api-modules.texi
> @@ -942,14 +942,15 @@ the @var{name} is not bound in the module, signals an error.  Returns a
>  variable, always.
>  
>  @example
> -SCM my_eval_string (SCM str)
> -@{
> -  static SCM eval_string_var = SCM_BOOL_F;
> +static SCM eval_string_var;
>  
> -  if (scm_is_false (eval_string_var))
> -    eval_string_var =
> -      scm_c_public_lookup ("ice-9 eval-string", "eval-string");
> +void my_init (void)
> +@{
> +  eval_string_var = scm_c_public_lookup ("ice-9 eval-string", "eval-string");
> +@}
>  
> +SCM my_eval_string (SCM str)
> +@{
>    return scm_call_1 (scm_variable_ref (eval_string_var), str);
>  @}
>  @end example

The doc should say something about ‘my_init’, and perhaps mention
locking?

Ludo’.

Re: [PATCH] Fix thread-unsafe lazy initializations

[Mark H Weaver]

Hi Ludovic,

ludo@gnu.org (Ludovic Courtès) writes:

> Mark H Weaver <mhw@netris.org> skribis:
>
>> --- a/doc/ref/api-modules.texi
>> +++ b/doc/ref/api-modules.texi
>> @@ -942,14 +942,15 @@ the @var{name} is not bound in the module, signals an error.  Returns a
>>  variable, always.
>>  
>>  @example
>> -SCM my_eval_string (SCM str)
>> -@{
>> -  static SCM eval_string_var = SCM_BOOL_F;
>> +static SCM eval_string_var;
>>  
>> -  if (scm_is_false (eval_string_var))
>> -    eval_string_var =
>> -      scm_c_public_lookup ("ice-9 eval-string", "eval-string");
>> +void my_init (void)
>> +@{
>> +  eval_string_var = scm_c_public_lookup ("ice-9 eval-string", "eval-string");
>> +@}
>>  
>> +SCM my_eval_string (SCM str)
>> +@{
>>    return scm_call_1 (scm_variable_ref (eval_string_var), str);
>>  @}
>>  @end example
>
> The doc should say something about ‘my_init’, and perhaps mention
> locking?

Can you suggest some text?  'my_init' seems obvious to me, and given
that this is just an example for 'scm_c_*_lookup', it seems out of place
to talk about general locking issues here, but feel free to propose some
text to go here.

    Thanks,
      Mark

Re: Thread-unsafe initialization problems in Guile

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1145 bytes --]

I've only read the most recent article you posted, but if I understand
correctly, there is a third option: (3) somehow find a way to generate a
portable memory barrier instruction. Is that currently possible? I'm not
sure that it is. Probably option (2) is best if we can do it.

Noah


On Thu, Feb 28, 2013 at 4:07 PM, Mark H Weaver <mhw@netris.org> wrote:

> Here's an article from a reputable source that backs up my claim that
> the lazy-initialization pattern that we use in a few places is not
> thread-safe:
>
>   http://www.ibm.com/developerworks/java/library/j-dcl/index.html
>
> Here are the thread-unsafe lazy initializations that I'm aware of:
>
> ./posix.c:1375:            make_rw_port = scm_c_private_variable ("ice-9
> popen",
> ./debug.c:217:    local_eval_var = scm_c_public_variable ("ice-9
> local-eval", "local-eval");
> ./strports.c:541:      eval_string = scm_c_public_lookup ("ice-9
> eval-string", "eval-string");
>
> In each of these cases, we have two options: (1) synchronize on every
> access of the lazily-initialized variable (including reads), or (2)
> abandon lazy initialization.
>
>   Thoughts?
>     Mark
>
>

[-- Attachment #2: Type: text/html, Size: 1771 bytes --]

Re: [PATCH] Fix thread-unsafe lazy initializations

[Ludovic Courtès]

Mark H Weaver <mhw@netris.org> skribis:

> ludo@gnu.org (Ludovic Courtès) writes:
>
>> Mark H Weaver <mhw@netris.org> skribis:
>>
>>> --- a/doc/ref/api-modules.texi
>>> +++ b/doc/ref/api-modules.texi
>>> @@ -942,14 +942,15 @@ the @var{name} is not bound in the module, signals an error.  Returns a
>>>  variable, always.
>>>  
>>>  @example
>>> -SCM my_eval_string (SCM str)
>>> -@{
>>> -  static SCM eval_string_var = SCM_BOOL_F;
>>> +static SCM eval_string_var;
>>>  
>>> -  if (scm_is_false (eval_string_var))
>>> -    eval_string_var =
>>> -      scm_c_public_lookup ("ice-9 eval-string", "eval-string");
>>> +void my_init (void)
>>> +@{
>>> +  eval_string_var = scm_c_public_lookup ("ice-9 eval-string", "eval-string");
>>> +@}
>>>  
>>> +SCM my_eval_string (SCM str)
>>> +@{
>>>    return scm_call_1 (scm_variable_ref (eval_string_var), str);
>>>  @}
>>>  @end example
>>
>> The doc should say something about ‘my_init’, and perhaps mention
>> locking?
>
> Can you suggest some text?  'my_init' seems obvious to me, and given
> that this is just an example for 'scm_c_*_lookup', it seems out of place
> to talk about general locking issues here, but feel free to propose some
> text to go here.

Agreed.  Perhaps just something like: “Note that the program should
ensure that ‘my_init’ is called only once, and in a thread-safe way.”

Ludo’.

Re: [PATCH] Fix thread-unsafe lazy initializations

[Mark H Weaver]

ludo@gnu.org (Ludovic Courtès) writes:
> Agreed.  Perhaps just something like: “Note that the program should
> ensure that ‘my_init’ is called only once, and in a thread-safe way.”

Okay, I went ahead and pushed it to stable-2.0, with the code comment:
"It is important that the call to 'my_init' happens-before all calls to
'my_eval_string'."

    Thanks,
      Mark

Re: Thread-unsafe initialization problems in Guile

[Mark H Weaver]

Hi Noah,

I wrote:
>   In each of these cases, we have two options: (1) synchronize on every
>   access of the lazily-initialized variable (including reads), or (2)
>   abandon lazy initialization.

Noah Lavine <noah.b.lavine@gmail.com> writes:
> I've only read the most recent article you posted, but if I understand
> correctly, there is a third option: (3) somehow find a way to generate
> a portable memory barrier instruction. Is that currently possible?

If we were to do that, we'd have to add memory barriers in two places:
(1) after writing to the lazily-initialized variable, and (2) before
reading from it.  While memory barriers are somewhat more efficient than
mutexes, they are still very expensive.

As for portability, C11 is the first C standard to support memory
barriers.  For now, our best bet would probably be to use libatomic_ops,
which is also used by libgc.

> Probably option (2) is best if we can do it.

Agreed.  Unfortunately, in these cases option (2) would significantly
increase the number of modules that need to be loaded at initialization
time.  That's why I reluctantly chose option (1).

     Regards,
       Mark

Re: Thread-unsafe initialization problems in Guile

[Noah Lavine]

[-- Attachment #1: Type: text/plain, Size: 1833 bytes --]

Hello,


On Tue, Mar 5, 2013 at 10:24 PM, Mark H Weaver <mhw@netris.org> wrote:

> Hi Noah,
>
> Noah Lavine <noah.b.lavine@gmail.com> writes:
> > I've only read the most recent article you posted, but if I understand
> > correctly, there is a third option: (3) somehow find a way to generate
> > a portable memory barrier instruction. Is that currently possible?
>
> If we were to do that, we'd have to add memory barriers in two places:
> (1) after writing to the lazily-initialized variable, and (2) before
> reading from it.  While memory barriers are somewhat more efficient than
> mutexes, they are still very expensive.
>

I'm not sure I understand the issue, but I think I was imagining something
like

if (variable == SCM_BOOL_F) {
  acquire_mutex(var_mutex);
  if (variable == SCM_BOOL_F) {
    variable = initialize_variable();
    memory_barrier();
  }
  release_mutex(var_mutex);
}

That's really just a normal locking scheme with an added memory barrier to
make sure that all threads see an update after the first thread updates the
variable. Would that work?


> As for portability, C11 is the first C standard to support memory
> barriers.  For now, our best bet would probably be to use libatomic_ops,
> which is also used by libgc.
>

That means we already depend on libatomic_ops, which is good. However, I
see that the website for that library recommends using C11 instead. But I
really doubt that this issue is a big enough justification to use either
libatomic_ops or C11.


> > Probably option (2) is best if we can do it.
>
> Agreed.  Unfortunately, in these cases option (2) would significantly
> increase the number of modules that need to be loaded at initialization
> time.  That's why I reluctantly chose option (1).
>

That makes sense.

Thanks a lot for helping me understand these memory issues.

Noah

[-- Attachment #2: Type: text/html, Size: 2829 bytes --]

Re: Thread-unsafe initialization problems in Guile

[Mark H Weaver]

Noah Lavine <noah.b.lavine@gmail.com> writes:

> I'm not sure I understand the issue, but I think I was imagining
> something like
>
> if (variable == SCM_BOOL_F) {
>   acquire_mutex(var_mutex);
>   if (variable == SCM_BOOL_F) {
>     variable = initialize_variable();
>     memory_barrier();
>   }
>   release_mutex(var_mutex);
> }
>
> That's really just a normal locking scheme with an added memory
> barrier to make sure that all threads see an update after the first
> thread updates the variable. Would that work?

No.  There's no portable memory barrier that can be used only by the
writer of a shared variable.  The reader must also do synchronization in
order to prove the "happens-before" relationship.

    Regards,
      Mark