Re: Ephemerons, self-referentality in weak hashtables

[Maxime Devos <maximedevos@telenet.be>]

[-- Attachment #1: Type: text/plain, Size: 2316 bytes --]

Christopher Lemmer Webber schreef op di 18-05-2021 om 11:46 [-0400]:
> Hello,
> 
> I'm finally taking some time to port Goblins to Guile, in-between other
> tasks anyway.  In Goblins there is a weak hashtable that maps current
> actor references to their current behavior.  I found that for
> self-referential actors, I needed ephemerons for GC stuff to work right.

Ephemeron SRFI: <https://srfi.schemers.org/srfi-124/srfi-124.html>

> In this old thread I found Wingo mentioning them:
> 
> Andy Wingo writes:
> 
> >   * If there is a possibility of a path from B to A, you need an
> >     ephemeron table, and Guile doesn't do that right now.  But it
> >     should!
> 
> Is there something ephemeron-like I should be doing?

Guile doesn't seem to have ephemerons, though it would be nice to
have them!

I've been looking at gc.h for how these could be implemented
(Guile uses BDW-GC for garbage collection).
The function GC_general_register_disappearing_link (void **link, const void *obj)
(https://github.com/ivmai/bdwgc/blob/master/include/gc.h#L1218) looks promising.
The idea is to have a C structure representing ephemerons

struct ephemeron {
  SCM key;
  SCM value; /* called ‘datum’in SRFI-124 */
}

do some magic to make ‘value’ and ‘keys’ ‘disguised pointers’ (i.e., tell BDW-GC that
‘key’ and ‘value’ doesn't really point to anything), and during construction
register ‘disappearing links’, such that ‘key’ and ‘value’ will be cleared
when ‘key’ becomes unreachable.

static void
initialise_ephemeron (struct ephemeron *eph, SCM key, SCM value)
{
  eph->key = key:
  eph->value = value;
  /* TODO: this can return an error */
  GC_general_register_disappearing_link (&eph->value, key);
  GC_general_register_disappearing_link (&eph->key, key);
}

Note that, according to the GC_general_register_disappearing_link docs,
reading eph->key and eph->value required holding th allocation lock,
so:

SCM
scm_ephemeron_key (SCM eph_scm)
{
  struct ephemeron *e = [type checks ...]
  SCM ret;
  [hold the lock]
  ret = e->key;
  [release the lock]
  return ret;
}

Likewise for ‘value’. Or maybe GC_general_register_disappearing_link
doesn't work that way ... requires testing!

Greetings,
Maxime.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 260 bytes --]