allocation within critical sections

allocation within critical sections

[Andy Wingo]

Hi,

FYI: Allocating memory can run finalizers, which can run arbitrary code.
So if you allocate memory from within a critical section, i.e. while a
mutex is held, you need to be really sure that there's no way a
finalizer would try to grab the lock you are already holding.

In some cases it's best to simply avoid allocation while holding a lock.

Andy, who got the following backtrace, with wip-threads-and-fork:

#0  0x00007f5daf443cec in __lll_lock_wait () from /lib/x86_64-linux-gnu/libpthread.so.0
#1  0x00007f5daf43f339 in _L_lock_926 () from /lib/x86_64-linux-gnu/libpthread.so.0
#2  0x00007f5daf43f15b in pthread_mutex_lock () from /lib/x86_64-linux-gnu/libpthread.so.0
#3  0x00007f5dafba8563 in finalize_port (ptr=0x3dac5a0, data=<optimized out>) at ports.c:575
#4  finalize_port (ptr=0x3dac5a0, data=<optimized out>) at ports.c:551
#5  0x00007f5daee5851e in GC_invoke_finalizers () at finalize.c:872
#6  0x00007f5daee5876e in GC_notify_or_invoke_finalizers () at finalize.c:951
#7  0x00007f5daee5ab4d in GC_generic_malloc_many (lb=16, k=1, result=0x7f5daf080d30) at mallocx.c:290
#8  0x00007f5daee640a1 in GC_malloc (bytes=16) at thread_local_alloc.c:177
#9  0x00007f5dafba690e in scm_cell (cdr=772, car=2052) at ../libguile/gc.h:204
#10 scm_cons (x=<optimized out>, y=0x304) at pairs.c:77
#11 0x00007f5dafb8cc6e in scm_make_list (n=<optimized out>, init=0x804) at list.c:120
#12 0x00007f5dafb82c39 in finalize_guarded (ptr=<optimized out>, finalizer_data=<optimized out>) at guardians.c:124
#13 0x00007f5daee5851e in GC_invoke_finalizers () at finalize.c:872
#14 0x00007f5daee5876e in GC_notify_or_invoke_finalizers () at finalize.c:951
#15 0x00007f5daee5ab4d in GC_generic_malloc_many (lb=16, k=1, result=0x7f5daf080d30) at mallocx.c:290
#16 0x00007f5daee640a1 in GC_malloc (bytes=16) at thread_local_alloc.c:177
#17 0x00007f5dafba690e in scm_cell (cdr=65961984, car=36468752) at ../libguile/gc.h:204
#18 scm_cons (x=<optimized out>, y=0x3ee8000) at pairs.c:77
#19 0x00007f5dafbf5b6f in lock_all_weak_tables (unused=<optimized out>) at weak-table.c:762
#20 0x00007f5dafbf8c97 in before_fork () at posix.c:1295
#21 scm_fork () at posix.c:1328

-- 
http://wingolog.org/

Re: allocation within critical sections

[Andy Wingo]

On Thu 09 Feb 2012 20:15, Andy Wingo <wingo@pobox.com> writes:

> Andy, who got the following backtrace, with wip-threads-and-fork:

I fixed that one.  Just got another interesting backtrace (appended).
FWIW, I'm running the threaded web server on guile master with
wip-threads-and-fork on my web site.  It seems to be doing OK, but I
suspect there are a few more deadlocks to unravel.  There are more than
on stable-2.0 because master has more locking.

Andy

Thread 1 (Thread 0x7fa7d4d3d700 (LWP 9369)):
#0  0x00007fa7d40ebcec in __lll_lock_wait () from /lib/x86_64-linux-gnu/libpthread.so.0
#1  0x00007fa7d40e7339 in _L_lock_926 () from /lib/x86_64-linux-gnu/libpthread.so.0
#2  0x00007fa7d40e715b in pthread_mutex_lock () from /lib/x86_64-linux-gnu/libpthread.so.0
#3  0x00007fa7d489d1a2 in scm_c_weak_set_add_x (set=<optimized out>, raw_hash=4279044819568792738, pred=0x7fa7d489c680 <eq_predicate>, 
    closure=0x4b4d720, obj=<optimized out>) at weak-set.c:825
#4  0x00007fa7d4850b33 in scm_c_make_port_with_encoding (tag=<optimized out>, mode_bits=<optimized out>, encoding=0x1ad91d0 "UTF-8", 
    handler=SCM_FAILED_CONVERSION_ERROR, stream=87907616) at ports.c:623
#5  0x00007fa7d487f171 in scm_mkstrport (pos=<optimized out>, str=<optimized out>, modes=327680, caller=<optimized out>) at strports.c:320
#6  0x00007fa7d487f3dc in scm_call_with_output_string (proc=0x4b4d740) at strports.c:410
#7  0x00007fa7d489a465 in vm_regular_engine (vm=0xfc7050, program=0x1092b40, argv=0xfc9c60, nargs=-1) at vm-i-system.c:892
#8  0x00007fa7d489c02e in scm_call_with_vm (vm=0xfc7050, proc=0x1092b40, args=<optimized out>) at vm.c:860
#9  0x00007fa7d4811b45 in scm_error_scm (key=0xf793c0, subr=<optimized out>, message=<optimized out>, args=<optimized out>, data=<optimized out>)
    at error.c:95
#10 0x00007fa7d4811bc0 in scm_error (key=0xf793c0, subr=0x7fa7d48b4f0a "scm_flush", message=<optimized out>, args=0x4b4f400, rest=0x4b4f440)
    at error.c:62
#11 0x00007fa7d4811c27 in scm_syserror (subr=0x7fa7d48b4f0a "scm_flush") at error.c:178
#12 0x00007fa7d481f799 in fport_flush (port=<optimized out>) at fports.c:858
#13 0x00007fa7d481f8d5 in fport_close (port=<optimized out>) at fports.c:891
---Type <return> to continue, or q <return> to quit---
#14 0x00007fa7d481f9e9 in fport_free (port=<optimized out>) at fports.c:915
#15 0x00007fa7d485025a in finalize_port (ptr=0x1f9d060, data=<optimized out>) at ports.c:571
#16 finalize_port (ptr=0x1f9d060, data=<optimized out>) at ports.c:551
#17 0x00007fa7d3b0051e in GC_invoke_finalizers () at finalize.c:872
#18 0x00007fa7d3b0076e in GC_notify_or_invoke_finalizers () at finalize.c:951
#19 0x00007fa7d3b01f0c in GC_generic_malloc (lb=976, k=0) at malloc.c:158
#20 0x00007fa7d3b02211 in GC_core_malloc_atomic (lb=976) at malloc.c:226
#21 0x00007fa7d489ca80 in resize_set (set=0xf41cc0) at weak-set.c:315
#22 0x00007fa7d489ccd0 in vacuum_weak_set (set=0xf41cc0) at weak-set.c:401
#23 do_vacuum_weak_set (set=<optimized out>) at weak-set.c:707
#24 0x00007fa7d489cea2 in weak_gc_callback (weak=<optimized out>) at weak-set.c:725
#25 weak_gc_hook (hook_data=<optimized out>, fn_data=<optimized out>, data=<optimized out>) at weak-set.c:734
#26 0x00007fa7d482dd6c in scm_c_hook_run (hook=0x7fa7d4b24020, data=0x0) at hooks.c:103
#27 0x00007fa7d4821d42 in after_gc_async_thunk () at gc.c:685
#28 0x00007fa7d489a471 in vm_regular_engine (vm=0xfc7050, program=0xf74620, argv=0xfc95f0, nargs=-1) at vm-i-system.c:889
#29 0x00007fa7d4803851 in scm_async_tick () at async.c:166
#30 0x00007fa7d489bbc1 in vm_regular_engine (vm=0xfc7050, program=0x1051cc0, argv=0xfc95a8, nargs=-1) at vm-i-system.c:1255
#31 0x00007fa7d4814cd3 in scm_primitive_eval (exp=0x1163ba0) at eval.c:684
#32 0x00007fa7d4814d33 in scm_eval (exp=0x1163ba0, module_or_state=0x10bb000) at eval.c:718
#33 0x00007fa7d489a455 in vm_regular_engine (vm=0xfc7050, program=0x1149300, argv=0xfc9248, nargs=-1) at vm-i-system.c:895
#34 0x00007fa7d4814637 in scm_call_1 (proc=0x1149300, arg1=0x1159440) at eval.c:485
#35 0x00007fa7d489a455 in vm_regular_engine (vm=0xfc7050, program=0x1051cc0, argv=0xfc91c8, nargs=-1) at vm-i-system.c:895
#36 0x00007fa7d4814cd3 in scm_primitive_eval (exp=0x1155e20) at eval.c:684
#37 0x00007fa7d4814d33 in scm_eval (exp=0x1155e20, module_or_state=0x10bb000) at eval.c:718
#38 0x00007fa7d48616af in scm_shell (argc=6, argv=0x7fffe8ab2938) at script.c:441
#39 0x00007fa7d4830cdd in invoke_main_func (body_data=0x7fffe8ab2810) at init.c:336
#40 0x00007fa7d480f62a in c_body (d=0x7fffe8ab2760) at continuations.c:522
#41 0x00007fa7d489a84f in vm_regular_engine (vm=0xfc7050, program=0x10914e0, argv=0xfc90c0, nargs=-1) at vm-i-system.c:960
#42 0x00007fa7d4814753 in scm_call_4 (proc=0x10914e0, arg1=<optimized out>, arg2=<optimized out>, arg3=<optimized out>, arg4=<optimized out>)
    at eval.c:506
#43 0x00007fa7d480fde3 in scm_i_with_continuation_barrier (body=0x7fa7d480f620 <c_body>, body_data=0x7fffe8ab2760, 
    handler=0x7fa7d480f9f0 <c_handler>, handler_data=0x7fffe8ab2760, pre_unwind_handler=<optimized out>, pre_unwind_handler_data=<optimized out>)
    at continuations.c:460
#44 0x00007fa7d480fe95 in scm_c_with_continuation_barrier (func=<optimized out>, data=<optimized out>) at continuations.c:556
#45 0x00007fa7d48834ca in with_guile_and_parent (base=0x7fffe8ab27c0, data=0x7fffe8ab27e0) at threads.c:897
#46 0x00007fa7d3b071d5 in GC_call_with_stack_base (fn=<optimized out>, arg=<optimized out>) at misc.c:1542
#47 0x00007fa7d4883678 in scm_i_with_guile_and_parent (parent=<optimized out>, data=<optimized out>, func=<optimized out>) at threads.c:940
#48 scm_with_guile (func=<optimized out>, data=<optimized out>) at threads.c:946
#49 0x00007fa7d4830de5 in scm_boot_guile (argc=<optimized out>, argv=<optimized out>, main_func=<optimized out>, closure=<optimized out>)
---Type <return> to continue, or q <return> to quit---
    at init.c:319
#50 0x0000000000400ada in main (argc=6, argv=0x7fffe8ab2938) at guile.c:81
(gdb) 


-- 
http://wingolog.org/

Re: allocation within critical sections

[Andy Wingo]

On Mon 13 Feb 2012 11:38, Andy Wingo <wingo@pobox.com> writes:

> On Thu 09 Feb 2012 20:15, Andy Wingo <wingo@pobox.com> writes:
>
>> Andy, who got the following backtrace, with wip-threads-and-fork:
>
> I fixed that one.  Just got another interesting backtrace (appended).

It goes much deeper than I thought:

  Destructors, Finalizers, and Synchronization
  Boehm, Hans-J.
  http://www.hpl.hp.com/techreports/2002/HPL-2002-335.pdf

I think the only sensible thing to do is for Guile 2.2 to run a separate
thread to invoke finalizers, as the JVM does.

Andy
-- 
http://wingolog.org/

Re: allocation within critical sections

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> Andy, who got the following backtrace, with wip-threads-and-fork:
>
> #0 0x00007f5daf443cec in __lll_lock_wait () from
> /lib/x86_64-linux-gnu/libpthread.so.0 #1 0x00007f5daf43f339 in
> _L_lock_926 () from /lib/x86_64-linux-gnu/libpthread.so.0 #2
> 0x00007f5daf43f15b in pthread_mutex_lock () from
> /lib/x86_64-linux-gnu/libpthread.so.0 #3 0x00007f5dafba8563 in
> finalize_port (ptr=0x3dac5a0, data=<optimized out>) at ports.c:575 #4
> finalize_port (ptr=0x3dac5a0, data=<optimized out>) at ports.c:551 #5
> 0x00007f5daee5851e in GC_invoke_finalizers () at finalize.c:872 #6
> 0x00007f5daee5876e in GC_notify_or_invoke_finalizers () at
> finalize.c:951 #7 0x00007f5daee5ab4d in GC_generic_malloc_many (lb=16,
> k=1, result=0x7f5daf080d30) at mallocx.c:290 #8 0x00007f5daee640a1 in
> GC_malloc (bytes=16) at thread_local_alloc.c:177 #9 0x00007f5dafba690e
> in scm_cell (cdr=772, car=2052) at ../libguile/gc.h:204 #10 scm_cons
> (x=<optimized out>, y=0x304) at pairs.c:77 #11 0x00007f5dafb8cc6e in
> scm_make_list (n=<optimized out>, init=0x804) at list.c:120 #12
> 0x00007f5dafb82c39 in finalize_guarded (ptr=<optimized out>,
> finalizer_data=<optimized out>) at guardians.c:124 #13
> 0x00007f5daee5851e in GC_invoke_finalizers () at finalize.c:872 #14
> 0x00007f5daee5876e in GC_notify_or_invoke_finalizers () at
> finalize.c:951 #15 0x00007f5daee5ab4d in GC_generic_malloc_many
> (lb=16, k=1, result=0x7f5daf080d30) at mallocx.c:290 #16
> 0x00007f5daee640a1 in GC_malloc (bytes=16) at thread_local_alloc.c:177
> #17 0x00007f5dafba690e in scm_cell (cdr=65961984, car=36468752) at
> ../libguile/gc.h:204 #18 scm_cons (x=<optimized out>, y=0x3ee8000) at
> pairs.c:77 #19 0x00007f5dafbf5b6f in lock_all_weak_tables
> (unused=<optimized out>) at weak-table.c:762 #20 0x00007f5dafbf8c97 in
> before_fork () at posix.c:1295 #21 scm_fork () at posix.c:1328

Can you explain what happens here?  Is it a deadlock?  What’s at ports.c:575?

Thanks,
Ludo’.

Re: allocation within critical sections

[Andy Wingo]

On Thu 16 Feb 2012 22:30, ludo@gnu.org (Ludovic Courtès) writes:

> Can you explain what happens here?  Is it a deadlock?  What’s at
> ports.c:575?

It was a deadlock, but I fixed it.  It was something that locked all
weak sets, but while doing so allocated memory.  Allocating memory ran
finalizers which tried to manipulate the port set, but that lock was
already taken: deadlock.

The solution will be to run finalizers in a separate thread, as the JVM
does.

Andy
-- 
http://wingolog.org/

Re: allocation within critical sections

[Mike Gran]

> From: Andy Wingo <wingo@pobox.com>

>>  Can you explain what happens here?  Is it a deadlock?  What’s at
>>  ports.c:575?
> 
> It was a deadlock, but I fixed it.  It was something that locked all
> weak sets, but while doing so allocated memory.  Allocating memory ran
> finalizers which tried to manipulate the port set, but that lock was
> already taken: deadlock.
> 
> The solution will be to run finalizers in a separate thread, as the JVM
> does.

As an aside, I can get a similar sort of deadlock during garbage
collection of SMOBs if my smob_free function calls a scheme function.
But the manual does note that you should not call any functions in 
SMOB GC finalizers, so that wouldn't happen if I actually followed the
instructions.

-Mike

Re: allocation within critical sections

[Andy Wingo]

On Fri 17 Feb 2012 03:46, Mike Gran <spk121@yahoo.com> writes:

>> From: Andy Wingo <wingo@pobox.com>
>
>>>  Can you explain what happens here?  Is it a deadlock?  What’s at
>>>  ports.c:575?
>> 
>> It was a deadlock, but I fixed it.  It was something that locked all
>> weak sets, but while doing so allocated memory.  Allocating memory ran
>> finalizers which tried to manipulate the port set, but that lock was
>> already taken: deadlock.
>> 
>> The solution will be to run finalizers in a separate thread, as the JVM
>> does.
>
> As an aside, I can get a similar sort of deadlock during garbage
> collection of SMOBs if my smob_free function calls a scheme function.
> But the manual does note that you should not call any functions in 
> SMOB GC finalizers, so that wouldn't happen if I actually followed the
> instructions.

Any Scheme function?  With Guile 2.0?  It should be possible to call
arbitrary code from finalizers, if we call finalizers from a separate
thread.

Andy
-- 
http://wingolog.org/

Re: allocation within critical sections

[Mike Gran]

> From: Andy Wingo <wingo@pobox.com>
 >>  As an aside, I can get a similar sort of deadlock during garbage
>>  collection of SMOBs if my smob_free function calls a scheme function.
>>  But the manual does note that you should not call any functions in 
>>  SMOB GC finalizers, so that wouldn't happen if I actually followed the
>>  instructions.
> 
> Any Scheme function?  With Guile 2.0?  It should be possible to call
> arbitrary code from finalizers, if we call finalizers from a separate
> thread.

Happens with any scheme function called in a SMOB's finalizer, with Guile 2.0,
in a memory constrained situation.
 
For example, Guile-ncurses has a SMOB finalizer that calls a guardian previously
created with 'make-guardian'.  This is in the <form> SMOB.
 
Here's the order of operations

- GC_invoke_finalizers calls the <form> SMOB's free function 'gc_form_free'

- my SMOB finalizer gc_form_free calls a guardian procedure with
scm_call_0 remove the guardian

- That kicks off a new scm_c_vm_run then calls scm_i_smob_apply_trampoline
 
- there is some mutex in the trampoline process

- A new trampoline causes a memory allocation with scm_hash_fn_create_handle_x

- Since memory is low, it calls GC_invoke_finalizers

- This ends up making a call to my finalizer gc_form_free.  (Don't know if this
is a recursive call to my SMOB finalizer or if it is a call to a different
<form>'s SMOB finalizer, since I have many forms)
 
- the gc_form_free calls a guardian with scm_call_0
 
- which kicks off a new scm_c_v_run

- which eventually gets you to scm_i_smob_apply_trampoline again

- which leads to a recursive mutex lock in scm_i_smob_apply_trampoline
 
-Mike

Re: allocation within critical sections

[Andy Wingo]

On Fri 17 Feb 2012 11:32, Mike Gran <spk121@yahoo.com> writes:

> - Since memory is low, it calls GC_invoke_finalizers

This doesn't necessarily occur when memory is low -- it occurs when
allocating new objects, and previously the collector decided that some
objects were finalizable.  It doesn't indicate hard times for the GC.

> - which leads to a recursive mutex lock in scm_i_smob_apply_trampoline

Ooooh, good one.  A bug in Guile, this one, and tricky to get around.
Of course, running finalizers in a separate thread will solve it.

Andy
-- 
http://wingolog.org/

Re: allocation within critical sections

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> Ooooh, good one.  A bug in Guile, this one, and tricky to get around.
> Of course, running finalizers in a separate thread will solve it.

It’s about differing user-provided finalizer execution, no?

What about using asyncs for that?  For instance, scm_i_finalize_smob
make a differed, instead of direct, call to the SMOB’s ‘free’, via
scm_i_queue_async_cell.

Thanks,
Ludo’.

Re: allocation within critical sections

[Andy Wingo]

On Fri 17 Feb 2012 23:59, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> skribis:
>
>> Ooooh, good one.  A bug in Guile, this one, and tricky to get around.
>> Of course, running finalizers in a separate thread will solve it.
>
> It’s about [deferring] user-provided finalizer execution, no?

I think that's a limiting way to look at the problem -- it's really
about running finalizers within a context in which no other locks are
held.  See the "Destructors, Finalizers, and Synchronization" paper from
Boehm.

> What about using asyncs for that?  For instance, scm_i_finalize_smob
> make a [deferred], instead of direct, call to the SMOB’s ‘free’, via
> scm_i_queue_async_cell.

It's an interesting idea.  I suspect that it only defers the problem,
though: if we start running finalizers through asyncs, we'll run into
problems with locks at the scheme level.

That is to say, just because you are in Scheme does not mean you can
acquire any lock without deadlock.

Andy
-- 
http://wingolog.org/

Re: allocation within critical sections

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> On Fri 17 Feb 2012 23:59, ludo@gnu.org (Ludovic Courtès) writes:

[...]

>> What about using asyncs for that?  For instance, scm_i_finalize_smob
>> make a [deferred], instead of direct, call to the SMOB’s ‘free’, via
>> scm_i_queue_async_cell.
>
> It's an interesting idea.  I suspect that it only defers the problem,
> though: if we start running finalizers through asyncs, we'll run into
> problems with locks at the scheme level.
>
> That is to say, just because you are in Scheme does not mean you can
> acquire any lock without deadlock.

Sure, but the libguile-level lock issue would go away, wouldn’t it?

Ludo’.

Re: allocation within critical sections

[Andy Wingo]

On Sun 19 Feb 2012 21:56, ludo@gnu.org (Ludovic Courtès) writes:

>>> What about using asyncs for that?  For instance, scm_i_finalize_smob
>>> make a [deferred], instead of direct, call to the SMOB’s ‘free’, via
>>> scm_i_queue_async_cell.
>>
>> It's an interesting idea.  I suspect that it only defers the problem,
>> though: if we start running finalizers through asyncs, we'll run into
>> problems with locks at the scheme level.
>>
>> That is to say, just because you are in Scheme does not mean you can
>> acquire any lock without deadlock.
>
> Sure, but the libguile-level lock issue would go away, wouldn’t it?

Does it?

  libguile takes a lock
  libguile calls a function within the lock (e.g. from a smob finalizer)
  an async runs while the scheme function runs
  a finalizer runs, potentially grabbing the lock that libguile has

Maybe this can be avoided somehow.  Don't call functions while holding
locks?  Seems very tricky, especially when you get third-party code into
the mix.

However I think that this discussion is not attacking the fundamental
problem.  It should be OK for Scheme code to take locks.  Or do you have
some other plan for concurrency in Guile?

Andy
-- 
http://wingolog.org/

Re: allocation within critical sections

[Andy Wingo]

Hi!

On Fri 17 Feb 2012 23:59, ludo@gnu.org (Ludovic Courtès) writes:

>> Of course, running finalizers in a separate thread will solve it.
>
> What about using asyncs for that?  For instance, scm_i_finalize_smob
> make a differed, instead of direct, call to the SMOB’s ‘free’, via
> scm_i_queue_async_cell.

I just pushed a patch to master that runs all finalizers asynchronously:
from asyncs, and, if threads are supported, from a separate thread.

Take a look; feedback appreciated!

Cheers,

Andy
-- 
http://wingolog.org/