Discussion:
[Gc] Collect a little and continue reclaim in a loop: possible?
(too old to reply)
Ivan Maidanski
2017-01-11 19:51:39 UTC
Permalink
Raw Message
Hello Hans,

Looking into GC_allocobj, it has the following:
    while (*flh == 0) {
      ENTER_GC();
      /* Do our share of marking work */
      if (TRUE_INCREMENTAL) GC_collect_a_little_inner(1); // calls GC_mark_some which, in turn, sets some mark bits
      /* Sweep blocks for objects of this size */
      GC_continue_reclaim(gran, kind); // reclaims some objects with unset mark bits
      ...
    }

Is this ok to reclaim memory before finishing the collection?

I have added the assertions to reclaim.c functions which examine mark bits (see the attachment), and do gctest on linux/x64 as follows:
gcc -I include -DGC_ASSERTIONS  -DGC_TIME_LIMIT=1 -DGC_THREADS -I libatomic_ops/src tests/test.c extra/gc.c -lpthread -ldl
./a.out
Switched to incremental mode
Emulating dirty bits with mprotect/signals
Assertion failure: extra/../reclaim.c:335 // GC_allocobj -> GC_continue_reclaim -> GC_reclaim_small_nonempty_block

Regards,
Ivan
Hans Boehm
2017-01-13 06:54:31 UTC
Permalink
Raw Message
I think this is fine. Once we finish a GC cycle, we put blocks waiting to
be swept on the reclaim lists. We can start another incremental GC without
completely finishing the last sweep. No mark bits should get set in the
blocks still being reclaimed because we haven't allocated in them since the
last cycle. So nothing can become newly reachable (except as a result of
misidentified pointers). We do need to make sure that we don't clear any
mark bits as part of collection while blocks are still waiting to be
reclaimed, and that we don't add blocks to the reclaim lists until all
objects in them have been marked.

Hans
Post by Ivan Maidanski
Hello Hans,
while (*flh == 0) {
ENTER_GC();
/* Do our share of marking work */
if (TRUE_INCREMENTAL) GC_collect_a_little_inner(1); // calls
GC_mark_some which, in turn, sets some mark bits
/* Sweep blocks for objects of this size */
GC_continue_reclaim(gran, kind); // reclaims some objects with unset
mark bits
...
}
Is this ok to reclaim memory before finishing the collection?
I have added the assertions to reclaim.c functions which examine mark bits
gcc -I include -DGC_ASSERTIONS -DGC_TIME_LIMIT=1 -DGC_THREADS -I
libatomic_ops/src tests/test.c extra/gc.c -lpthread -ldl
./a.out
Switched to incremental mode
Emulating dirty bits with mprotect/signals
Assertion failure: extra/../reclaim.c:335 // GC_allocobj ->
GC_continue_reclaim -> GC_reclaim_small_nonempty_block
Regards,
Ivan
Bruce Hoult
2017-01-13 07:40:49 UTC
Permalink
Raw Message
we don't add blocks to the reclaim lists until all objects in them have
been marked

Which means that a mark phase has been run to completion, starting not only
from GC roots, but from all previously-marked objects?
I think this is fine. Once we finish a GC cycle, we put blocks waiting to
be swept on the reclaim lists. We can start another incremental GC without
completely finishing the last sweep. No mark bits should get set in the
blocks still being reclaimed because we haven't allocated in them since the
last cycle. So nothing can become newly reachable (except as a result of
misidentified pointers). We do need to make sure that we don't clear any
mark bits as part of collection while blocks are still waiting to be
reclaimed, and that we don't add blocks to the reclaim lists until all
objects in them have been marked.
Hans
Post by Ivan Maidanski
Hello Hans,
while (*flh == 0) {
ENTER_GC();
/* Do our share of marking work */
if (TRUE_INCREMENTAL) GC_collect_a_little_inner(1); // calls
GC_mark_some which, in turn, sets some mark bits
/* Sweep blocks for objects of this size */
GC_continue_reclaim(gran, kind); // reclaims some objects with
unset mark bits
...
}
Is this ok to reclaim memory before finishing the collection?
I have added the assertions to reclaim.c functions which examine mark
gcc -I include -DGC_ASSERTIONS -DGC_TIME_LIMIT=1 -DGC_THREADS -I
libatomic_ops/src tests/test.c extra/gc.c -lpthread -ldl
./a.out
Switched to incremental mode
Emulating dirty bits with mprotect/signals
Assertion failure: extra/../reclaim.c:335 // GC_allocobj ->
GC_continue_reclaim -> GC_reclaim_small_nonempty_block
Regards,
Ivan
--
This message has been scanned for viruses and
dangerous content by *MailScanner* <http://www.mailscanner.info/>, and is
believed to be clean.
_______________________________________________
bdwgc mailing list
https://lists.opendylan.org/mailman/listinfo/bdwgc
Ivan Maidanski
2017-01-13 14:37:18 UTC
Permalink
Raw Message
We do need to make sure that ... we don't add blocks to the reclaim lists until all objects in them have been marked.
So, adding assert GC_collection_in_progress()==FALSE to GC_reclaim_small_nonempty_block is correct, right?

Note that GC_reclaim_small_nonempty_block calls GC_reclaim_clear (indirectly) which, in turn, uses mark_bit_from_hdr (so, according to the current implementation, if an object has not been marked by GC_mark_some then the object is subject for being reclaimed by GC_continue_reclaim even it is live - this is what I described in https://github.com/ivmai/bdwgc/issues/137 )

Regards,
Ivan
 we don't add blocks to the reclaim lists until all objects in them have been marked
Which means that a mark phase has been run to completion, starting not only from GC roots, but from all previously-marked objects?
I think this is fine. Once we finish a GC cycle, we put blocks waiting to be swept on the reclaim lists. We can start another incremental GC without completely finishing the last sweep. No mark bits should get set in the blocks still being reclaimed because we haven't allocated in them since the last cycle. So nothing can become newly reachable (except as a result of misidentified pointers). We do need to make sure that we don't clear any mark bits as part of collection while blocks are still waiting to be reclaimed, and that we don't add blocks to the reclaim lists until all objects in them have been marked.
Hans
Post by Ivan Maidanski
Hello Hans,
    while (*flh == 0) {
      ENTER_GC();
      /* Do our share of marking work */
      if (TRUE_INCREMENTAL) GC_collect_a_little_inner(1); // calls GC_mark_some which, in turn, sets some mark bits
      /* Sweep blocks for objects of this size */
      GC_continue_reclaim(gran, kind); // reclaims some objects with unset mark bits
      ...
    }
Is this ok to reclaim memory before finishing the collection?
gcc -I include -DGC_ASSERTIONS  -DGC_TIME_LIMIT=1 -DGC_THREADS -I libatomic_ops/src tests/test.c extra/gc.c -lpthread -ldl
./a.out
Switched to incremental mode
Emulating dirty bits with mprotect/signals
Assertion failure: extra/../reclaim.c:335 // GC_allocobj -> GC_continue_reclaim -> GC_reclaim_small_nonempty_block
Regards,
Ivan
--
This message has been scanned for viruses and
dangerous content by MailScanner , and is
believed to be clean.
_______________________________________________
bdwgc mailing list
https://lists.opendylan.org/mailman/listinfo/bdwgc
_______________________________________________
bdwgc mailing list
https://lists.opendylan.org/mailman/listinfo/bdwgc
Ivan Maidanski
2017-01-25 18:27:05 UTC
Permalink
Raw Message
I found out that the existing code is correct:
Mark bits are cleared only when is_full_gc but in this case reclaim_all is called before initiating GC so continue_reclaim is a no-op in the given code if collection is in progress.
Regards,
Ivan 
--
Post by Ivan Maidanski
We do need to make sure that ... we don't add blocks to the reclaim lists until all objects in them have been marked.
So, adding assert GC_collection_in_progress()==FALSE to GC_reclaim_small_nonempty_block is correct, right?
Note that GC_reclaim_small_nonempty_block calls GC_reclaim_clear (indirectly) which, in turn, uses mark_bit_from_hdr (so, according to the current implementation, if an object has not been marked by GC_mark_some then the object is subject for being reclaimed by GC_continue_reclaim even it is live - this is what I described in https://github.com/ivmai/bdwgc/issues/137 )
Regards,
Ivan
 we don't add blocks to the reclaim lists until all objects in them have been marked
Which means that a mark phase has been run to completion, starting not only from GC roots, but from all previously-marked objects?
I think this is fine. Once we finish a GC cycle, we put blocks waiting to be swept on the reclaim lists. We can start another incremental GC without completely finishing the last sweep. No mark bits should get set in the blocks still being reclaimed because we haven't allocated in them since the last cycle. So nothing can become newly reachable (except as a result of misidentified pointers). We do need to make sure that we don't clear any mark bits as part of collection while blocks are still waiting to be reclaimed, and that we don't add blocks to the reclaim lists until all objects in them have been marked.
Hans
Post by Ivan Maidanski
Hello Hans,
    while (*flh == 0) {
      ENTER_GC();
      /* Do our share of marking work */
      if (TRUE_INCREMENTAL) GC_collect_a_little_inner(1); // calls GC_mark_some which, in turn, sets some mark bits
      /* Sweep blocks for objects of this size */
      GC_continue_reclaim(gran, kind); // reclaims some objects with unset mark bits
      ...
    }
Is this ok to reclaim memory before finishing the collection?
gcc -I include -DGC_ASSERTIONS  -DGC_TIME_LIMIT=1 -DGC_THREADS -I libatomic_ops/src tests/test.c extra/gc.c -lpthread -ldl
./a.out
Switched to incremental mode
Emulating dirty bits with mprotect/signals
Assertion failure: extra/../reclaim.c:335 // GC_allocobj -> GC_continue_reclaim -> GC_reclaim_small_nonempty_block
Regards,
Ivan
--
This message has been scanned for viruses and
dangerous content by MailScanner , and is
believed to be clean.
_______________________________________________
bdwgc mailing list
https://lists.opendylan.org/mailman/listinfo/bdwgc
_______________________________________________
bdwgc mailing list
https://lists.opendylan.org/mailman/listinfo/bdwgc
Loading...