[PATCH]: deadlock in make_struct()

[PATCH]: deadlock in make_struct()

[Linas Vepstas]

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

Hi,

Here's a deadlock patch. When committing this patch, please copy
the text below into the source code commit message, as it provides
a record of what the patch does, and why it was made.

--linas


The patch below fixes a deadlock in the multi-threading code.
It fixes this by simply removing the CRITICAL_SECTION lock.
There does not seem to be any need for a lock on this section,
since all variables accessed are local, and all other literals
are compile-time constants.

A typical deadlock that was witnessed was:

thread 7 -- holding critical section lock, sleeping on &scm_i_sweep_mutex
            held in scm_make_struct() at struct.c:463,
            sleeping in increase_mtrigger() at  gc-malloc.c:234
thread 5 -- holding heap_mutex, sleeping on critical section
            held because thread is in guile mode
            sleeping in scm_c_catch() at throw.c:187
thread 12 -- holding &scm_i_sweep_mutex, sleeping on heap_mutex
             held in increase_mtrigger() at gc-malloc.c:234
             sleeping in scm_i_thread_put_to_sleep() at threads.c:1621

Signed-off-by: Linas Vepstas <linasvepstas@gmail.com>

---
 libguile/struct.c |   10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

Index: guile-1.8.5/libguile/struct.c
===================================================================
--- guile-1.8.5.orig/libguile/struct.c	2008-11-16 10:58:31.000000000 -0600
+++ guile-1.8.5/libguile/struct.c	2008-11-16 12:17:05.000000000 -0600
@@ -450,7 +450,14 @@ SCM_DEFINE (scm_make_struct, "make-struc
         goto bad_tail;
     }

-  SCM_CRITICAL_SECTION_START;
+  /* In guile 1.8.5 and earlier, everything below was covered by a
+     CRITICAL_SECTION lock. This leads to deadlocks in garbage collection,
+     since other threads might be holding the heap_mutex, while sleeping
+     on the CRITICAL_SECTION lock. There does not seem to be any need
+     for a lock on the section below, as it does not access or update
+     any globals. vtable, basic_size, tail_elts are all local variables,
+     scm_tc3_struct and scm_struct_i_* are all compile-time consts.
+     So the lock has been removed. */
   if (SCM_STRUCT_DATA (vtable)[scm_struct_i_flags] & SCM_STRUCTF_ENTITY)
     {
       data = scm_alloc_struct (basic_size + tail_elts,
@@ -466,7 +473,6 @@ SCM_DEFINE (scm_make_struct, "make-struc
   handle = scm_double_cell ((((scm_t_bits) SCM_STRUCT_DATA (vtable))
 			     + scm_tc3_struct),
 			    (scm_t_bits) data, 0, 0);
-  SCM_CRITICAL_SECTION_END;

   /* In guile 1.8.1 and earlier, the SCM_CRITICAL_SECTION_END above covered
      also the following scm_struct_init.  But that meant if scm_struct_init

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: deadlock-struct.patch --]
[-- Type: text/x-diff; name=deadlock-struct.patch, Size: 2746 bytes --]

Subject: [PATCH]: deadlock in make_struct()
Date: 16 Nov 2008
To: bug-guile@gnu.org

Hi, 

Here's a deadlock patch. When committing this patch, please copy
the text below into the source code commit message, as it provides
a record of what the patch does, and why it was made. 

--linas


The patch below fixes a deadlock in the multi-threading code.
It fixes this by simply removing the CRITICAL_SECTION lock.
There does not seem to be any need for a lock on this section,
since all variables accessed are local, and all other literals
are compile-time constants.

A typical deadlock that was witnessed was:

thread 7 -- holding critical section lock, sleeping on &scm_i_sweep_mutex
            held in scm_make_struct() at struct.c:463, 
            sleeping in increase_mtrigger() at  gc-malloc.c:234
thread 5 -- holding heap_mutex, sleeping on critical section
            held because thread is in guile mode
            sleeping in scm_c_catch() at throw.c:187
thread 12 -- holding &scm_i_sweep_mutex, sleeping on heap_mutex
             held in increase_mtrigger() at gc-malloc.c:234
             sleeping in scm_i_thread_put_to_sleep() at threads.c:1621

Signed-off-by: Linas Vepstas <linasvepstas@gmail.com>

---
 libguile/struct.c |   10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

Index: guile-1.8.5/libguile/struct.c
===================================================================
--- guile-1.8.5.orig/libguile/struct.c	2008-11-16 10:58:31.000000000 -0600
+++ guile-1.8.5/libguile/struct.c	2008-11-16 12:17:05.000000000 -0600
@@ -450,7 +450,14 @@ SCM_DEFINE (scm_make_struct, "make-struc
         goto bad_tail;
     }
     
-  SCM_CRITICAL_SECTION_START;
+  /* In guile 1.8.5 and earlier, everything below was covered by a
+     CRITICAL_SECTION lock. This leads to deadlocks in garbage collection,
+     since other threads might be holding the heap_mutex, while sleeping
+     on the CRITICAL_SECTION lock. There does not seem to be any need
+     for a lock on the section below, as it does not access or update
+     any globals. vtable, basic_size, tail_elts are all local variables,
+     scm_tc3_struct and scm_struct_i_* are all compile-time consts.
+     So the lock has been removed. */
   if (SCM_STRUCT_DATA (vtable)[scm_struct_i_flags] & SCM_STRUCTF_ENTITY)
     {
       data = scm_alloc_struct (basic_size + tail_elts,
@@ -466,7 +473,6 @@ SCM_DEFINE (scm_make_struct, "make-struc
   handle = scm_double_cell ((((scm_t_bits) SCM_STRUCT_DATA (vtable))
 			     + scm_tc3_struct),
 			    (scm_t_bits) data, 0, 0);
-  SCM_CRITICAL_SECTION_END;
 
   /* In guile 1.8.1 and earlier, the SCM_CRITICAL_SECTION_END above covered
      also the following scm_struct_init.  But that meant if scm_struct_init

Re: [PATCH]: deadlock in make_struct()

[Andy Wingo]

Hi Linas,

I was about to write about how your patch looked incorrect to me,
because GC could see a half-initialized struct (and potentially sweep
it, with a bad free function); but I just looked back and back into the
history, and could not find why the critical section was there. It has
been there since Jim Blandy imported the whole mess into CVS in 1996.

I would like to say that your patch is OK, but since you don't use
structs very much in your code AFAIK I'm a bit hesitant. Can anyone
think of a reason why this allocation codepath would have SCM_DEFER_INTS
around it?

Andy
-- 
http://wingolog.org/

Re: [PATCH]: deadlock in make_struct()

[Ludovic Courtès]

Hi Andy,

Andy Wingo <wingo@pobox.com> writes:

> I was about to write about how your patch looked incorrect to me,
> because GC could see a half-initialized struct (and potentially sweep
> it, with a bad free function); but I just looked back and back into the
> history, and could not find why the critical section was there. It has
> been there since Jim Blandy imported the whole mess into CVS in 1996.

Kevin asked the same question a while back:

  http://lists.gnu.org/archive/html/guile-devel/2007-02/msg00006.html

One we've had enough developers wondering why it's here, maybe we can
safely remove it.  :-)

Thanks,
Ludo'.

Re: [PATCH]: deadlock in make_struct()

[Neil Jerram]

2008/11/18 Ludovic Courtès <ludo@gnu.org>:

>
> Kevin asked the same question a while back:
>
>  http://lists.gnu.org/archive/html/guile-devel/2007-02/msg00006.html
>
> One we've had enough developers wondering why it's here, maybe we can
> safely remove it.  :-)

I agree.  I also can't see any reason for the critical section, so
would be happy to commit Linas's patch.

     Neil

Re: [PATCH]: deadlock in make_struct()

[Ludovic Courtès]

Hello!

"Neil Jerram" <neiljerram@googlemail.com> writes:

> 2008/11/18 Ludovic Courtès <ludo@gnu.org>:
>
>>
>> Kevin asked the same question a while back:
>>
>>  http://lists.gnu.org/archive/html/guile-devel/2007-02/msg00006.html
>>
>> One we've had enough developers wondering why it's here, maybe we can
>> safely remove it.  :-)
>
> I agree.  I also can't see any reason for the critical section, so
> would be happy to commit Linas's patch.

I just committed it, after re-reaching the conclusion that there's no
reason to have a critical section here AFAICS.

Thanks,
Ludo'.

Re: [PATCH]: deadlock in make_struct()

[Linas Vepstas]

2008/11/17 Andy Wingo <wingo@pobox.com>:
> Hi Linas,
>
> I was about to write about how your patch looked incorrect to me,
> because GC could see a half-initialized struct (and potentially sweep
> it, with a bad free function);

Well, I tried to think that through. I tried to find a need for a
"remember_up_to_here", but it didn't look like the code
needed it -- it seemed like everything was on stack or
in registers, and so would be safe from accidental GC.

I did not carefully audit all the routines that are called;
there may be problems in there.  Whether there is a
"global variable" lurking somewhere in there was also
unclear.

In general, I notice that "global variables" are not
highlighted in any way in the guile code, thus making it
hard to determine if one is manipulating something
which is completely local to the thread, or is possibly
accessed from multiple threads.   I'm thinking it would
be a wise long-term strategy to provide this kind of
markup, although I don't know how.

--linas

Re: [PATCH]: deadlock in make_struct()

[Han-Wen Nienhuys]

Linas Vepstas escreveu:
> 2008/11/17 Andy Wingo <wingo@pobox.com>:
>> Hi Linas,
>>
>> I was about to write about how your patch looked incorrect to me,
>> because GC could see a half-initialized struct (and potentially sweep
>> it, with a bad free function);
> 
> Well, I tried to think that through. I tried to find a need for a
> "remember_up_to_here", but it didn't look like the code
> needed it -- it seemed like everything was on stack or
> in registers, and so would be safe from accidental GC.

Our GC is lazy; if a function momentarily drops a reference, you´d have to 
have 2 GCs within the same function body to see bad effects.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen