Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #150171

Local variable hygiene for use with GC

Show all headers | View raw

I was browsing over the code for my parser combinations,

https://github.com/luser-dr00g/pcomb/tree/b302aa641c654f5b7c0c7131ae9d144f632a6368
https://github.com/luser-dr00g/pcomb/archive/b302aa641c654f5b7c0c7131ae9d144f632a6368.zip

I have an object organized as an array of (allocation record, 
discriminated union). The 'object' typedefs to a pointer to 
the middle of this array, so following the pointer gets you
straight to the object, but following the (&ob[-1]) pointer
gets you to an object's allocation record. The allocation 
records are linked together in a list.

And I've got a simple garbage collector to clean up unused
objects (of which the parsers generate o so many).


https://github.com/luser-dr00g/pcomb/blob/b302aa641c654f5b7c0c7131ae9d144f632a6368/pc9obj.c#L91

// Garbage Collector

void
add_global_root( object a ){
  global_roots = cons( a, global_roots );
}

int
garbage_collect( object local_roots ){
  mark_objects( local_roots );
  mark_objects( global_roots );
  return  sweep_objects( &allocation_list );
}

static tag *
mark( object a ){
  return  &a[-1].Header.t;
}

static void
mark_objects( list a ){
  if(  !valid(a) || *mark( a )  ) return;
  *mark( a ) = 1;
  switch(  a->t  ){
  case LIST:       mark_objects( a->List.a ); 
                   mark_objects( a->List.b );       break;
  case PARSER:     mark_objects( a->Parser.v );     break;
  case OPERATOR:   mark_objects( a->Operator.v );   break;
  case SYMBOL:     mark_objects( a->Symbol.data );  break;
  case SUSPENSION: mark_objects( a->Suspension.v ); break;
  }
}

static int
sweep_objects( list *po ){
  int count = 0;
  while(  *po  )
    if(  (*po)->t  ){
      (*po)->t = 0;
      po = &(*po)->Header.next;
    } else {
      object z = *po;
      *po = (*po)->Header.next;
      if(  z[1].t == STRING && z[1].String.disposable  )
        free( z[1].String.string );
      free( z );
      ++count;
    }
  return  count;
}

This works as long as I run the garbage collector from top-level code
with the discipline always to create a list of the working set of 
objects to pass to garbage_collect().

If the garbage collector were to be called by, say, the object allocator
somewhere deep in the call tree I'm pretty sure it would precipitate
utter disaster.

What soft of pattern or idiom can I use in functions that store
a reference to an object in local variables (automatic storage),
so I can call the garbage collector from the allocator?

My thought is to establish a set of rules or conventions that I can
do at the start and end of all relevant functions to maintain a
local_roots list as a global (static, file scope).

For a concrete example, how about the function trio that converts a 
list of ints which represent characters into a string. 


https://github.com/luser-dr00g/pcomb/blob/b302aa641c654f5b7c0c7131ae9d144f632a6368/pc9obj.c#L323

static int
count_ints( list o ){
  return  !o               ? 0 :
          o->t == SUSPENSION ? *o = *at_( o ), count_ints( o ) :
          o->t == INTEGER  ? 1 :
          o->t == LIST     ? count_ints( o->List.a ) + count_ints( o->List.b ) :
          0;
}

object
fill_string( char **s, list o ){
  return  !o    ? NULL :
          o->t == INTEGER  ? *(*s)++ = o->Int.i, NULL :
          o->t == LIST     ? fill_string( s, o->List.a ), fill_string( s, o->List.b ) :
          NULL;
}

object
string_from_chars( list o ){
  char *s = calloc( count_ints( o ) + 1, 1 );
  object z = String( s, 1 );
  return  fill_string( &s, o ), z;
}


The two helper functions don't have any local variables, so they're
safe I believe. As a matter of fact, this whole trio is therefore a
leaf, and therefore probably safe. But suppose we didn't know that
fill_string doesn't allocate any objects, then we need to add 
object z to the local_roots list and drop it again before returning.


static list local_roots = NULL;
object
string_from_chars( list o ){
  char *s = calloc( count_ints( o ) + 1, 1 );
  object z = String( s, 1 );
  local_roots = cons( z, local_roots );
      fill_string( &s, o );
  local_roots = drop( 1, local_roots );
  return z;
}


And possibly, it should do the same for the parameter list o, in 
case the parent function didn't store in a variable.

  local_roots = cons( o, cons( z, local_roots ) );
      fill_string( &s, o );
  local_roots = drop( 2, local_roots );

Does this seem correct? Workable? Too simple? Not simple enough?
Ideally ok but impossible to follow the required discipline?
Give up an use Boehm et al?

Back to comp.lang.c | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Local variable hygiene for use with GC luser droog <luser.droog@gmail.com> - 2020-02-22 20:09 -0800
  Re: Local variable hygiene for use with GC luser droog <luser.droog@gmail.com> - 2020-02-22 20:39 -0800
    Re: Local variable hygiene for use with GC luser droog <luser.droog@gmail.com> - 2020-02-22 20:51 -0800
      Re: Local variable hygiene for use with GC chad <cdalten@gmail.com> - 2020-02-22 23:01 -0800
        Re: Local variable hygiene for use with GC luser droog <luser.droog@gmail.com> - 2020-03-02 15:24 -0800
          Re: Local variable hygiene for use with GC chad <cdalten@gmail.com> - 2020-03-02 16:05 -0800

csiph-web