fail to collect references in release build

[mgood7123]

jump to #259 (comment)

i am unsure how to go about keeping roots alive as they get eligible for garbage collection immediately after creation

    ManagedObjState state;

    managed_obj_init(&state, MANAGED_OBJECT_DEFAULT_ARENA_SIZE);
    
    managed_obj_t p = managed_obj_make(&state, malloc(500));
    printf("p is %p\n", p);

    // managed_obj_describe(&state);

    printf("first collect, p should not be collected\n");
    managed_obj_collect(&state); // should not collect p

    printf("if p has been collected then we have not managed to track it correctly\n");
    p = (managed_obj_t) 0x6; // no longer referenced

    printf("second collect, p should be collected\n");
    managed_obj_collect(&state); // should collect the original pointer assigned to p

    printf("if p has NOT been collected then we have not managed to track it correctly\n");

    managed_obj_deinit(&state);

(i assume there would be more that needs to be done in my implementation (below) to correctly support the above tho i am unsure as to what would be needed)

first collect, p should not be collected

object 0x7ffbf7100000 with pointer 0x12ea080 is being freed.
Total Collection duration: 0 seconds, 0 milliseconds, 192 microseconds

if p has been collected then we have not managed to track it correctly

second collect, p should be collected

Total Collection duration: 0 seconds, 0 milliseconds, 70 microseconds

if p has NOT been collected then we have not managed to track it correctly

deinit
deinit - collect
Total Collection duration: 0 seconds, 0 milliseconds, 43 microseconds
deinit - shutdown

the complete .h and .c file is https://gist.github.com/mgood7123/8a25971c90faa61397701361a0dd8be5

[mgood7123]

welp i figured out a way, tho it is not scalable

    mps_root_t static_stack_root;
    mps_addr_t static_stack[200];
    int static_stack_counter;

    mps_res_t res = mps_reserve(&state->static_stack[state->static_stack_counter], state->ap, size);
    if (res != MPS_RES_OK) managed_obj_error("out of memory in make_pointer");
    // printf("reserved pointer %p\n", static_stack[static_stack_counter]);
    obj = (managed_obj_t)state->static_stack[state->static_stack_counter];
    obj->pointer.type = MANAGED_OBJECT_TYPE_POINTER;
    obj->pointer.pointer = pointer;
    // printf("pointer %p contains pointer %p\n", obj, obj->pointer.pointer);
  } while(!mps_commit(state->ap, state->static_stack[state->static_stack_counter], size));
  state->static_stack_counter++;
  if (state->static_stack_counter == 200)
    state->static_stack_counter = 0;

    /* Create an MPS arena.  There is usually only one of these in a process.
        It holds all the MPS "global" state and is where everything happens. */
    MPS_ARGS_BEGIN(args) {
        MPS_ARGS_ADD(args, MPS_KEY_ARENA_SIZE, arena_size);
        res = mps_arena_create_k(&state->arena, mps_arena_class_vm(), args);
    } MPS_ARGS_END(args);
    if (res != MPS_RES_OK) managed_obj_error("Couldn't create arena");

// ...

  res = mps_root_create_area(&state->static_stack_root, state->arena, mps_rank_exact(), 0,
                             state->static_stack, state->static_stack + 200, mps_scan_area, NULL);
  if(res != MPS_RES_OK) managed_obj_error("Couldn't register stack root");

void managed_obj_deinit(ManagedObjState * state) {
    printf("deinit\n");

    memset(state->static_stack, 0, sizeof(mps_addr_t)*200);

    printf("deinit - collect\n");
    managed_obj_collect(state);

    printf("deinit - shutdown\n");
    mps_arena_park(state->arena);        /* ensure no collection is running */
    mps_root_destroy(state->static_stack_root); /* destroy static stack root */
    // mps_root_destroy(state->stack_root); /* destroy stack root before thread */
    // mps_thread_dereg(state->thread);     /* deregister thread before ap */
    mps_ap_destroy(state->ap);       /* destroy ap before pool */
    mps_pool_destroy(state->pool);   /* destroy pool before fmt */
    mps_fmt_destroy(state->fmt);     /* destroy fmt before chain */
    mps_chain_destroy(state->chain); /* destroy chain before arena */
    mps_arena_destroy(state->arena);     /* last of all */

    memset(state, 0, sizeof(ManagedObjState));
}

[mgood7123]

is there a way we can make this more scalable to larger amounts of allocations?

[mgood7123]

how feasible would it be to just register and destroy gc root structures as they are passed around?

like 1 root for each gc allocation being tracked

[rptb1]

Hello!

We've look at your code, and it has a problem with the registration of the stack root. Your are registering the stack from within a function, and using that function's stack frame as the cold end of the stack. See https://gist.github.com/mgood7123/8a25971c90faa61397701361a0dd8be5#file-managed_object_obj-c-L434

This means that none of the functions calling managed_obj_make will have their stack frames included in the root, and objects they point to might be GC'd by the MPS.

The documentation section Thread Roots describes how the stack root must be created. All functions that have roots in registers must be called by the function that locates the cold end in the way shown.

In general, you do not need to create and destroy roots very often -- certainly not once per object. The MPS is designed so that you register roots, then store pointers to objects you want to keep alive in those roots. The typical case is that the roots are the stack and registers of your thread, and all objects (recursively) reachable from there are kept alive. Preserving objects is just a matter of storing pointers to memory.

You definitely could have a kind of C++ "root object" that had a call to mps_root_create in its constructor and mps_root_destroy in its destructor, but that's the sort of thing we expect you do rarely: typically only once per process run.

We can't quite see from your code what you're trying to achieve. Feel free to explain your application. We're curious and would like to help.

Also we recommend you study the Scheme Example to see how it creates roots.

There might be a misunderstanding of what we call a "root". See https://memory-pool-system.readthedocs.io/en/version-1.118/glossary/r.html#term-root . A root is not GC'd by the MPS. A root is a (set of) pointers to objects managed by the MPS. So your original question "how to keep a root alive" might be trying to ask "how to keep an object referenced by a root alive"? The answer is that the MPS preserves all objects referenced by roots. If an object is dying, it is not referenced by a root. That could be because of the cold end problem I mentioned above.

Thanks.

[mgood7123]

i tried using the stack bottom (GC_get_stack_base() from boehm) as the thread stack root

which works correctly in debug build

but fails in a release build (no GC takes place)

    res = mps_thread_reg(&state->thread, state->arena);
    if (res != MPS_RES_OK) managed_obj_error("Couldn't register thread");

    struct MANAGED_STACK_ADDRESS_BOEHM_GC_stack_base sb_end;
    memset(&sb_end, 0, sizeof(struct MANAGED_STACK_ADDRESS_BOEHM_GC_stack_base));

    int gcres = MANAGED_STACK_ADDRESS_BOEHM_GC_get_stack_base(&sb_end);
    if (gcres == MANAGED_STACK_ADDRESS_BOEHM_GC_SUCCESS) {
    } else if (gcres == MANAGED_STACK_ADDRESS_BOEHM_GC_UNIMPLEMENTED) {
      managed_obj_error("GC_get_stack_base(start) unimplemented\n");
    } else {
      managed_obj_error("GC_get_stack_base(start) failed: %d\n", gcres);
    }

    printf("thread stack bottom: %p\n", sb_end.mem_base);

    // res = mps_root_create_thread(&state->thread_stack_root, state->arena, state->thread, (void*)sb_end.mem_base);
    // if (res != MPS_RES_OK) managed_obj_error("Couldn't create stack root");

    res = mps_root_create_reg(&state->thread_stack_root, state->arena, mps_rank_ambig(), 0, state->thread, mps_stack_scan_ambig, sb_end.mem_base, 0);
    if (res != MPS_RES_OK) printf("Couldn't create root");

[mgood7123]

Hello!

We've look at your code, and it has a problem with the registration of the stack root. Your are registering the stack from within a function, and using that function's stack frame as the cold end of the stack. See https://gist.github.com/mgood7123/8a25971c90faa61397701361a0dd8be5#file-managed_object_obj-c-L434

This means that none of the functions calling managed_obj_make will have their stack frames included in the root, and objects they point to might be GC'd by the MPS.

The documentation section Thread Roots describes how the stack root must be created. All functions that have roots in registers must be called by the function that locates the cold end in the way shown.

In general, you do not need to create and destroy roots very often -- certainly not once per object. The MPS is designed so that you register roots, then store pointers to objects you want to keep alive in those roots. The typical case is that the roots are the stack and registers of your thread, and all objects (recursively) reachable from there are kept alive. Preserving objects is just a matter of storing pointers to memory.

You definitely could have a kind of C++ "root object" that had a call to mps_root_create in its constructor and mps_root_destroy in its destructor, but that's the sort of thing we expect you do rarely: typically only once per process run.

We can't quite see from your code what you're trying to achieve. Feel free to explain your application. We're curious and would like to help.

Also we recommend you study the Scheme Example to see how it creates roots.

There might be a misunderstanding of what we call a "root". See https://memory-pool-system.readthedocs.io/en/version-1.118/glossary/r.html#term-root . A root is not GC'd by the MPS. A root is a (set of) pointers to objects managed by the MPS. So your original question "how to keep a root alive" might be trying to ask "how to keep an object referenced by a root alive"? The answer is that the MPS preserves all objects referenced by roots. If an object is dying, it is not referenced by a root. That could be because of the cold end problem I mentioned above.

Thanks.

ultimately i would like to create an api with MPS that allows me to basically have a stateful GC object that can "attach" and "detach" from threads

for example

// data is shared between T1 T2 and T3
//
mps_gc_1 for threads 1 2 3

// data is shared between T2 T4 and T5
//
// NOTE: mps_gc_1 will not touch data allocated by mps_gc_2 even though both are attached to thread 2
//
mps_gc_2 for threads 4 2 5

// dedicated MPS GC for thread 7, data is known not to be shared between any other thread
//
//   it is possible to localize data by carefully attaching and detaching from threads as data moves between threads
//
mps_gc_3 for thread 7

mps_gc 1 and 2 can co-exist with mps_gc 3 due to them running on seperate threads
unlike a global gc which runs on all threads even if data only exists on a single thread

this should co-exist with other GC's as long as we use a stop-the-world approach

[mgood7123]

i tried

    ManagedObjState state;

    managed_obj_init(&state, MANAGED_OBJECT_DEFAULT_ARENA_SIZE);

void managed_obj_init(ManagedObjState * state, size_t arena_size) {
    if (state == NULL) {
        managed_obj_error("state cannot be null");
    }
    memset(state, 0, sizeof(ManagedObjState));

    mps_res_t res;

// ...

/*

        A risk of using tagged pointers in registers and on the stack
        is that in some circumstances, an optimizing compiler might
        optimize away the tagged pointer, keeping only the untagged
        version of the pointer. In this situation the pointer would be
        ignored and if it was the last reference to the object the MPS
        might incorrectly determine that it was dead. 

        #. Choose to tag pointers with zero, setting ``scan_area`` to
           :c:func:`mps_scan_area_tagged` and setting ``pattern`` to
           zero.

*/

    void *marker = state;

    res = mps_root_create_thread_tagged(
      &state->thread_stack_root, state->arena,
      mps_rank_ambig(), (mps_rm_t)0,
      state->thread, mps_scan_area_tagged,
      sizeof(mps_word_t) - 1, (mps_word_t)0,
      marker
    );

    if (res != MPS_RES_OK) printf("Couldn't create root");
}

but release build still fails to find the pointers where a debug build would successfully find the pointers

void managed_obj_init(ManagedObjState * state, size_t arena_size) {
    if (state == NULL) {
        managed_obj_error("state cannot be null");
    }
    memset(state, 0, sizeof(ManagedObjState));

    mps_res_t res;

    MPS_ARGS_BEGIN(args) {
        MPS_ARGS_ADD(args, MPS_KEY_ARENA_SIZE, arena_size);
        res = mps_arena_create_k(&state->arena, mps_arena_class_vm(), args);
    } MPS_ARGS_END(args);
    if (res != MPS_RES_OK) managed_obj_error("Couldn't create arena");

  
    /* Make sure we can pick up finalization messages. */
    mps_message_type_enable(state->arena, mps_message_type_finalization());

  MPS_ARGS_BEGIN(args) {
    MPS_ARGS_ADD(args, MPS_KEY_FMT_ALIGN, MANAGED_OBJECT_ALIGNMENT);
    MPS_ARGS_ADD(args, MPS_KEY_FMT_SCAN, managed_obj_scan);
    MPS_ARGS_ADD(args, MPS_KEY_FMT_SKIP, managed_obj_skip);
    MPS_ARGS_ADD(args, MPS_KEY_FMT_FWD, managed_obj_fwd);
    MPS_ARGS_ADD(args, MPS_KEY_FMT_ISFWD, managed_obj_isfwd);
    MPS_ARGS_ADD(args, MPS_KEY_FMT_PAD, managed_obj_pad);
    res = mps_fmt_create_k(&state->fmt, state->arena, args);
  } MPS_ARGS_END(args);
  if (res != MPS_RES_OK) managed_obj_error("Couldn't create obj format");

  res = mps_chain_create(&state->chain,
                         state->arena,
                         (sizeof(managed_obj_gen_params) / sizeof(managed_obj_gen_params[0])),
                         managed_obj_gen_params);
  if (res != MPS_RES_OK) managed_obj_error("Couldn't create obj chain");

  MPS_ARGS_BEGIN(args) {
    MPS_ARGS_ADD(args, MPS_KEY_CHAIN, state->chain);
    MPS_ARGS_ADD(args, MPS_KEY_FORMAT, state->fmt);
    res = mps_pool_create_k(&state->pool, state->arena, mps_class_amc(), args);
  } MPS_ARGS_END(args);
  if (res != MPS_RES_OK) managed_obj_error("Couldn't create obj pool");

  res = mps_ap_create_k(&state->ap, state->pool, mps_args_none);
  if (res != MPS_RES_OK) managed_obj_error("Couldn't create obj allocation point");

    void *marker = state;

    res = mps_root_create_thread_tagged(
      &state->thread_stack_root, state->arena,
      mps_rank_ambig(), (mps_rm_t)0,
      state->thread, mps_scan_area_tagged,
      sizeof(mps_word_t) - 1, (mps_word_t)0,
      marker
    );

    if (res != MPS_RES_OK) printf("Couldn't create root");
}

managed_obj_t managed_obj_make(ManagedObjState * state, void * pointer)
{
  mps_addr_t port_ref;
  managed_obj_t obj;
  size_t size = MANAGED_OBJECT_ALIGN_OBJ(sizeof(managed_obj_pointer_s));
  do {
    mps_res_t res = mps_reserve(&state->static_stack[state->static_stack_counter], state->ap, size);
    if (res != MPS_RES_OK) managed_obj_error("out of memory in make_pointer");
    obj = (managed_obj_t)state->static_stack[state->static_stack_counter];
    obj->pointer.type = MANAGED_OBJECT_TYPE_POINTER;
    obj->pointer.pointer = pointer;
  } while(!mps_commit(state->ap, state->static_stack[state->static_stack_counter], size));
  printf("reserved and comitted object %p with pointer %p\n", obj, obj->pointer.pointer);
  state->static_stack_counter++;
  if (state->static_stack_counter == 200)
    state->static_stack_counter = 0;
  state->total += sizeof(managed_obj_pointer_s);
  port_ref = obj;
  mps_finalize(state->arena, &port_ref);
  return obj;
}

void managed_obj_collect(ManagedObjState * state) {
    unsigned long collect_start = mps_clock();

    mps_arena_collect(state->arena);
    managed_obj_mps_chat(state);

    unsigned long collect_end = mps_clock();

    ManagedObjTime collect_duration_time = managed_obj_convert_to_time(collect_end - collect_start);

    printf("Total Collection duration: %d seconds, %d milliseconds, %d microseconds\n", collect_duration_time.seconds, collect_duration_time.milliseconds, collect_duration_time.microseconds);
}

void managed_obj_deinit(ManagedObjState * state) {
    printf("deinit\n");

    memset(state->static_stack, 0, sizeof(mps_addr_t)*200);

    printf("deinit - collect after memset\n");
    managed_obj_collect(state);
    printf("deinit - collected after memset\n");

    printf("deinit - shutdown\n");
    mps_arena_park(state->arena);        /* ensure no collection is running */
    mps_root_destroy(state->thread_stack_root); /* destroy stack root before thread */
    mps_thread_dereg(state->thread);     /* deregister thread before ap */
    mps_ap_destroy(state->ap);       /* destroy ap before pool */
    mps_pool_destroy(state->pool);   /* destroy pool before fmt */
    mps_fmt_destroy(state->fmt);     /* destroy fmt before chain */
    mps_chain_destroy(state->chain); /* destroy chain before arena */
    mps_arena_destroy(state->arena);     /* last of all */

    memset(state, 0, sizeof(ManagedObjState));
}

TEST(MPS_collect2, 1) {
    ManagedObjState state;

    managed_obj_init(&state, MANAGED_OBJECT_DEFAULT_ARENA_SIZE);
    
    managed_obj_t p1 = managed_obj_make(&state, malloc(500));
    managed_obj_t p2 = managed_obj_make(&state, malloc(500));
    printf("p1 is %p, &p = %p\n", p1, &p1);
    printf("p2 is %p, &p = %p\n", p2, &p2);

    printf("first collect, p should not be collected\n");
    managed_obj_collect(&state); // should not collect p

    printf("if p has been collected then we have not managed to track it correctly\n");
    p1 = (managed_obj_t) 0x6; // no longer referenced
    p2 = (managed_obj_t) 0x6; // no longer referenced

    printf("second collect, p should be collected\n");
    managed_obj_collect(&state); // should collect the original pointer assigned to p

    printf("if p has NOT been collected then we have not managed to track it correctly\n");

    managed_obj_deinit(&state);
}

[mgood7123]

if we build using gcc and g++ instead of clang and clang++ then a release build successfully finds our pointers and GC's them

in clang/clang++ this seems to happen at -O2 and higher

using https://github.com/Ravenbrook/mps/master

clang and clang++

testBuilder_add_include(gc_mps mps_master/code)
testBuilder_add_include(gc_mps include)
testBuilder_add_source(gc_mps mps_master/code/mps.c)
testBuilder_add_source(gc_mps src/managed_object_obj.c)
# CONFIG_VAR_COOL
# CONFIG_VAR_HOT
# CONFIG_VAR_RASH
testBuilder_add_compile_option(gc_mps "SHELL:-DCONFIG_VAR_COOL")
testBuilder_build_static_library(gc_mps)

valgrind output (debug) https://gist.github.com/mgood7123/a565343e2f0f26c2f49ca6849632ab5c

valgrind output (release) https://gist.github.com/mgood7123/008d9dd435cf8660dd305449ceec5331

debug build, variant COLD

[ RUN      ] MPS_collect2.1
reserved and comitted object 0x7fc3f691a000 with pointer 0xd7c1c0
reserved and comitted object 0x7fc3f691a018 with pointer 0xd7c3c0
p1 is 0x7fc3f691a000, &p = 0x7fff73cc7228
p2 is 0x7fc3f691a018, &p = 0x7fff73cc7220
first collect, p should not be collected
Total Collection duration: 0 seconds, 0 milliseconds, 554 microseconds
if p has been collected then we have not managed to track it correctly
second collect, p should be collected
object 0x7fc3f6980000 with pointer 0xd7c1c0 is being freed.
object 0x7fc3f6980018 with pointer 0xd7c3c0 is being freed.
Total Collection duration: 0 seconds, 1 milliseconds, 557 microseconds
if p has NOT been collected then we have not managed to track it correctly
deinit
deinit - collect after memset
Total Collection duration: 0 seconds, 0 milliseconds, 634 microseconds
deinit - collected after memset
deinit - shutdown
[       OK ] MPS_collect2.1 (16 ms)

release build, variant COLD

[ RUN      ] MPS_collect2.1
reserved and comitted object 0x7f4da271a000 with pointer 0x1b911c0
reserved and comitted object 0x7f4da271a018 with pointer 0x1b913c0
p1 is 0x7f4da271a000, &p = 0x7fff2f5e4700
p2 is 0x7f4da271a018, &p = 0x7fff2f5e46f8
first collect, p should not be collected
Total Collection duration: 0 seconds, 0 milliseconds, 83 microseconds
if p has been collected then we have not managed to track it correctly
second collect, p should be collected
Total Collection duration: 0 seconds, 0 milliseconds, 29 microseconds
if p has NOT been collected then we have not managed to track it correctly
deinit
deinit - collect after memset
Total Collection duration: 0 seconds, 0 milliseconds, 58 microseconds
deinit - collected after memset
deinit - shutdown
[       OK ] MPS_collect2.1 (1 ms)

[mgood7123]

if i make my pointer volatile then it gets collected at -O2 and -O3 but i cannot force other libraries to use volatile

    volatile managed_obj_t p1 = managed_obj_make(&state, malloc(500));
    volatile managed_obj_t p2 = managed_obj_make(&state, malloc(500));

// ...

    p1 = (managed_obj_t) 0x6; // no longer referenced
    p2 = (managed_obj_t) 0x6; // no longer referenced

// ...

    printf("second collect, p should be collected\n");
    managed_obj_collect(&state); // should collect the original pointer assigned to p

[mgood7123]

this seems like with optimizations, attempting to bring a variable into the local stack of a function MAY bind it to the frame, resulting in it being uncollectable until the frame ends

this in turn CAN be troublesome if we attempt to init and destroy the GC in the same frame, since the GC cannot reclaim a variable that is bound to the same frame as it (or even may leak to a parent frame variable)
(leaking would technically be UB as it would yield a reference that exists but is untracked since the GC has been destroyed and the reference was still alive at such point)

[mgood7123]

one solution would be to forcefully collect all references before the arena is destroyed (regardless of weather such are reachable or not)

but i do not know how to do this