Can custom mark procedures be incremental?

[civodul]

(I noticed that opendylan.org and the mailing list are down, so I'm writing here...)

I’m trying to write a custom mark procedure that follows these guidelines from <gc/gc_mark.h>:

--8<---------------cut here---------------start------------->8---
/* A client supplied mark procedure.  Returns new mark stack pointer.   */
/* Primary effect should be to push new entries on the mark stack.      */
/* Mark stack pointer values are passed and returned explicitly.        */
/* Global variables describing mark stack are not necessarily valid.    */
/* (This usually saves a few cycles by keeping things in registers.)    */
/* Assumed to scan about GC_PROC_BYTES on average.  If it needs to do   */
/* much more work than that, it should do it in smaller pieces by       */
/* pushing itself back on the mark stack.                               */
--8<---------------cut here---------------end--------------->8---

The code below shows my interpretation of this: the mark procedure scans at most GC_PROC_BYTES, it saves the index where it stopped scanning the object, and pushes the object back on the mark stack; on the next call, it resumes scanning at the index that it recorded. Here's the code:

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <pthread.h>

#include <gc.h>
#include <gc/gc_mark.h>

struct array
{
  size_t size;                /* number of entries */
  size_t mark_index;              /* index where we stopped marking */
  pthread_mutex_t mark_lock;
  int *entries[];
};

static int weak_kind;

static struct GC_ms_entry *
mark_array (GC_word *addr, struct GC_ms_entry *mark_stack_ptr,
         struct GC_ms_entry *mark_stack_limit, GC_word env)
{
  struct array *w = (struct array *) addr;
  int **entries = w->entries;
  unsigned long k, size = w->size;
  unsigned long credit = GC_PROC_BYTES / sizeof (GC_word);

  pthread_mutex_lock (&w->mark_lock);
  printf ("%s mark %p at %zi (thread %p)\n",
      __func__, addr, w->mark_index, (void *) pthread_self ());
  for (k = w->mark_index;
       credit > 0 && k < size;
       k++)
    if (entries[k] != NULL)
      {
        mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word *) entries[k],
                                           mark_stack_ptr, mark_stack_limit,
                                           NULL);
    credit--;
      }

  if (k == size)
    /* We marked ENTRIES till the end.  */
    w->mark_index = 0;
  else
    {
      /* Save the current index and push ADDR back on the mark stack so
     we can resume later.  */
      w->mark_index = k;
      mark_stack_ptr = GC_MARK_AND_PUSH (addr,
                     mark_stack_ptr, mark_stack_limit,
                     NULL);
    }
  pthread_mutex_unlock (&w->mark_lock);

  return mark_stack_ptr;
}

int
main ()
{
  GC_INIT ();

  weak_kind =
    GC_new_kind (GC_new_free_list (),
         GC_MAKE_PROC (GC_new_proc (mark_array), 0),
         0, 0);

  while (1)
    {
      struct array *w;
      unsigned int size = 777 * (random () % 1000);
      w = GC_GENERIC_OR_SPECIAL_MALLOC (sizeof (struct array)
                    + size * sizeof (int *),
                    weak_kind);

      w->size = size;
      w->mark_index = 0;
      pthread_mutex_init (&w->mark_lock, NULL);

      for (unsigned int i = 0; i < size; i++)
    {
      void *key = GC_MALLOC_ATOMIC (10);
      w->entries[i] = key;
    }

      for (unsigned int i = 0; i < size; i++)
    {
      if (w->entries[i] != NULL)
        /* Make sure the Ith entry is valid.  If 'GC_size' segfaults, then
           that means we have a dangling pointer.  */
        GC_size (w->entries[i]);
    }

      static unsigned int loops = 0;
      if (loops++ % 10 == 0)
    printf ("iteration %4u, heap size = %li MiB\n",
        loops, GC_get_heap_size () / (1024 * 1024));
    }
}

This approach doesn’t work: the GC_size call in main eventually segfaults, meaning that we stumbled upon an entry that was GC’d.

Is there an example of an incremental mark procedure? How’s one supposed to carry the appropriate mark state?

[civodul]

I wonder if users follow the GC_PROC_BYTES limit. For instance, the (now defunct) libjava in GCC had a _Jv_MarkArray function that marks each array element, regardless of its size.

[ivmai]

GC_new_kind (GC_new_free_list (), GC_MAKE_PROC (GC_new_proc (mark_array), 0), 0, 0)

BTW. This call is wrong: clear argument should be true (I have added an assertion about it - 43a6189)

Is there an example of an incremental mark procedure? How’s one supposed to carry the appropriate mark state? I wonder if users follow the GC_PROC_BYTES limit. For instance, the (now defunct) libjava in GCC had a _Jv_MarkArray function that marks each array element, regardless of its size.

@hboehm Could you please comment on this items?

[drmeister]

I am also trying to implement an incremental mark procedure. I wonder if the 'env' argument is supposed to be used to carry the mark state, the amount of marking work that has been done.

I'm looking for a function that can push a new descriptor onto the mark stack - something like this.

https://github.com/ivmai/bdwgc/blob/57b97be07c514fcc4b608b13768fd2bf637a5899/typd_mlc.c#L364

Question 2: I see above that civodul has a mutex in their object that they lock while they are marking it. Is this necessary in a multithreaded context? We use boehm with multiple threads in the conservative mode and I'd like to keep using it with multithreaded code when we add a precise mode for boehm.