Finding objects on C stack - alternate GCPRO

Finding objects on C stack - alternate GCPRO

[Dmitry Antipov]

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

Everyone agrees that GGPROs are ugly and painful. On the other side,
current C stack marking code introduces substantial overhead by
maintaining red-black tree. And, since C stack marking is
conservative, it becomes very tricky to implement GC that may
relocate live objects (copying or compacting approach).

But there is another method to implement GCPROs. It looks not very
portable beyond GNU C since it uses __attribute__ ((cleanup (function)))
and compound statement expressions C extensions. But it doesn't
require UNGCPRO and dumbs like 'struct gcpro gcpro1, struct gcpro2, ...'.
And I believe it should work across longjmps.

This idea is briefly illustrated by an attached example. As for the
Emacs, it would be enough to declare every local Lisp_Object which
should survive the GC with the stuff like FOOPTR from this example,
and we're ready for exact C stack marking with (hopefully) very small
overhead.

Dmitry

[-- Attachment #2: cleanup.c --]
[-- Type: text/plain, Size: 1906 bytes --]

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

typedef struct {
  int x;
  int y;
} foo_t;

typedef struct gcpro {
  void *addr;
  struct gcpro *next;
} gcpro_t;

gcpro_t *foo_root;

static foo_t * foo_add (gcpro_t *fl, void *fooaddr)
{
  /* printf ("New local var at %p\n", fooaddr); */
  fl->addr = fooaddr;
  fl->next = foo_root;
  foo_root = fl;
  return NULL;
}

static void foo_remove (void *fooaddr)
{
  /* printf ("Drop local var at %p\n", fooaddr); */
  if (fooaddr != foo_root->addr)
    abort ();
  foo_root = foo_root->next;
}

#define FOOPTR(name) \
  foo_t __attribute__ ((cleanup (foo_remove))) *name = \
    ({ gcpro_t *fl = alloca (sizeof (gcpro_t)); foo_add (fl, &name); })

void gc (int locals)
{
  gcpro_t *fl;

  /* We should print addresses of all live
     locals defined with FOOPTR. */
  printf ("In GC, expect %d locals at:\n", locals);
  for (fl = foo_root; fl; fl = fl->next)
    printf ("  %p\n", fl->addr);
  printf ("GC end\n");
}

int foofun (foo_t *f1, foo_t *f2)
{
  FOOPTR (fooptr3);
  int ret;

  printf ("In foofun, local var at %p\n", &fooptr3);

  fooptr3 = malloc (sizeof *fooptr3);
  fooptr3->x = f1->x + f2->x;
  fooptr3->y = f1->y - f2->y;

  if (fooptr3->x > 0)
    {
      FOOPTR (fooptr4);

      printf ("In foofun, inner local var at %p\n", &fooptr4);
      gc (4); /* Here we expect 4 fooptrs on C stack. */
    }

  ret = fooptr3->x + fooptr3->y;
  free (fooptr3);
  return ret;
}

int main (int argc, char *argv[])
{
  FOOPTR (fooptr1);
  FOOPTR (fooptr2);
  int val;

  printf ("In main, local vars at %p and %p\n", &fooptr1, &fooptr2);
  
  fooptr1 = malloc (sizeof *fooptr1);
  fooptr1->x = argc;
  fooptr1->y = argc + 1;

  fooptr2 = malloc (sizeof *fooptr2);
  fooptr2->x = argc * 2;
  fooptr2->y = argc * 2 + 1;

  val = foofun (fooptr1, fooptr2);
  free (fooptr1);
  free (fooptr2);
  
  gc (2); /* Here we expect 2 fooptrs on C stack. */
  return val;
}

Re: Finding objects on C stack - alternate GCPRO

[Helmut Eller]

* Dmitry Antipov [2011-11-16 10:07] writes:

> Everyone agrees that GGPROs are ugly and painful. On the other side,
> current C stack marking code introduces substantial overhead by
> maintaining red-black tree. And, since C stack marking is
> conservative, it becomes very tricky to implement GC that may
> relocate live objects (copying or compacting approach).
>
> But there is another method to implement GCPROs. It looks not very
> portable beyond GNU C since it uses __attribute__ ((cleanup (function)))
> and compound statement expressions C extensions. But it doesn't
> require UNGCPRO and dumbs like 'struct gcpro gcpro1, struct gcpro2, ...'.
> And I believe it should work across longjmps.

And we could use C++ with destructors.

Helmut

Re: Finding objects on C stack - alternate GCPRO

[Dmitry Antipov]

On 11/16/2011 02:18 PM, Helmut Eller wrote:

> And we could use C++ with destructors.

Sure, but I don't expect to see a lot of this idea's fans among this list's subscribers.

Dmitry

Re: Finding objects on C stack - alternate GCPRO

[Richard Stallman]

Please don't make Emacs use C++.  C++ is an ugly and clumsy language.

-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use free telephony http://directory.fsf.org/category/tel/

Re: Finding objects on C stack - alternate GCPRO

[Stephen J. Turnbull]

Richard Stallman writes:

 > Please don't make Emacs use C++.  C++ is an ugly and clumsy language.

Except where it isn't.

XEmacs code is required to compile with both C (specifically C89,
thought there has been discussion recently of preferring C99) and C++
(IIRC this dialect was named "Clean C" by Martin Buchholz).  This has
two advantages in our practice: (1) the stricter typing rules of C++
catch some bugs[1], and (2) some things that are impossible to express
cleanly in C (specifically, typeof(Emacs character) != EMACS_INT,
which has been very useful in completely preventing certain Mule bugs
that have regressed frequently in Emacs's implementation) can be
implemented in the C++ build, and therefore type-checked.

Granted, the code needed to implement such a type in C++ is very
redundant if not specifically ugly, but it's really a unit test for a
"unit" that pervades text manipulation code rather than being
modularized into a few files.  It's nice if test code can be clean and
pretty, but when necessary I don't have a problem with gymnastics in
test code.  On the other hand, the code that actually implements
XEmacs functionality still compiles (and works correctly! :-) with C
and "typedef EMACS_INT Ichar" (where Ichar is our typedef for the
internal representation of the character type).

If C++ makes it possible to write *functionally better* allocation and
garbage collection code in a clean and intelligible way, I would be in
favor of relaxing the prohibition of C++ for *specified* files and
*specified* C++ idioms.

Footnotes: 
[1]  I don't know if this is still true for the most recent, tighter C
standard, but in our code --std=C99 does not catch all the common bugs
that a C++ build does.

Re: Finding objects on C stack - alternate GCPRO

[Richard Stallman]

    If C++ makes it possible to write *functionally better* allocation and
    garbage collection code in a clean and intelligible way, I would be in
    favor of relaxing the prohibition of C++ for *specified* files and
    *specified* C++ idioms.

We can do the necessary jobs in C.


-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use free telephony http://directory.fsf.org/category/tel/

Re: Finding objects on C stack - alternate GCPRO

[Eli Zaretskii]

> Date: Wed, 16 Nov 2011 14:07:46 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> 
> Everyone agrees that GGPROs are ugly and painful.

Given that most platforms make GCPRO and UNGCPRO a no-op (and the only
2 platforms that don't are probably simply not maintained enough and
don't use GCC anyway), why is this important enough to waste energy on
it?

Re: Finding objects on C stack - alternate GCPRO

[Stephen Berman]

On Wed, 16 Nov 2011 06:06:14 -0500 Eli Zaretskii <eliz@gnu.org> wrote:

> Given that most platforms make GCPRO and UNGCPRO a no-op (and the only
> 2 platforms that don't are probably simply not maintained enough and
> don't use GCC anyway), why is this important enough to waste energy on
> it?

On Wed, 16 Nov 2011 09:41:36 -0500 Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> The problem is that the few platforms that don't use GCC are the ones
> that require GCPROs as well, so not only it would be a large change, but
> it would also require us dropping support for those non-gcc
> non-conservative-GC platforms.

In light of these two statements it seems like the Elisp manual (section
Writing Emacs Primitives) gives too much weight to GCPRO, e.g. where it
says:

      It suffices to ensure that at least one pointer to each object is
   GC-protected; that way, the object cannot be recycled, so all pointers
   to it remain valid.  Thus, a particular local variable can do without
   protection if it is certain that the object it points to will be
   preserved by some other pointer (such as another local variable which
   has a `GCPRO')(1).  Otherwise, the local variable needs a `GCPRO'.

If this is only needed on platforms that don't support gcc, shouldn't
the manual say that, or should GCPRO be mentioned at all?  Perhaps I'm
completely missing the point, since the only thing I know about GCPRO is
what's in the manual; if so, could someone elaborate on the role of
GCPRO, or if that's inappropriate here, point me to relevant places
(preferable comments) in the Emacs sources or relevant external
discussion?  Thanks.

Steve Berman

Re: Finding objects on C stack - alternate GCPRO

[Eli Zaretskii]

> From: Stephen Berman <stephen.berman@gmx.net>
> Date: Thu, 17 Nov 2011 13:50:11 +0100
> 
>       It suffices to ensure that at least one pointer to each object is
>    GC-protected; that way, the object cannot be recycled, so all pointers
>    to it remain valid.  Thus, a particular local variable can do without
>    protection if it is certain that the object it points to will be
>    preserved by some other pointer (such as another local variable which
>    has a `GCPRO')(1).  Otherwise, the local variable needs a `GCPRO'.
> 
> If this is only needed on platforms that don't support gcc, shouldn't
> the manual say that, or should GCPRO be mentioned at all?

As long as Emacs supports platforms that don't use conservative stack
marking, we cannot drop GCPROs from the sources, and we cannot stop
requesting that new code uses GCPROs where they are needed on those
few platforms.

Btw, it's not GCC that allows to make GCPRO a no-op, it's the fact
that the platform supports stack marking.  I only mentioned GCC
because the proposed alternative method does require GCC.

> Perhaps I'm completely missing the point, since the only thing I
> know about GCPRO is what's in the manual; if so, could someone
> elaborate on the role of GCPRO, or if that's inappropriate here,
> point me to relevant places (preferable comments) in the Emacs
> sources or relevant external discussion?  Thanks.

GCPRO is needed when the C sources have pointers extracted from Lisp
objects and want to preserve them across calls to `eval'.  E.g., if
you hold the pointer to the data of a Lisp_String in a C variable, and
then call a function that can directly or indirectly call `eval'.  In
such cases, you want to tell GC that the Lisp object cannot be GC'ed.

Re: Finding objects on C stack - alternate GCPRO

[Stefan Monnier]

> Everyone agrees that GGPROs are ugly and painful. On the other side,
> current C stack marking code introduces substantial overhead by
> maintaining red-black tree.

I don't think the red-black-tree is a big overhead, in general.
The only place where it is significant is when (de)allocating small
vectors, which we could solve by using a special allocator for
small vectors.

> And, since C stack marking is conservative, it becomes very tricky to
> implement GC that may relocate live objects (copying or compacting
> approach).

Making all objects relocatable would require not only "precise marking"
but also "exhaustive marking" which is currently not the case.
Given the bugs we bump into already for string relocation I'd expect
that making all objects relocatable would make for a lot of nasty
debugging unless we can get GC info to be exhaustive (including
C pointers into Elisp objects) in a fully automated way (i.e. without
any manual annotation, be it GCPRO or FOOPTR).

> But there is another method to implement GCPROs. It looks not very
> portable beyond GNU C since it uses __attribute__ ((cleanup (function)))
> and compound statement expressions C extensions. But it doesn't
> require UNGCPRO and dumbs like 'struct gcpro gcpro1, struct gcpro2, ...'.
> And I believe it should work across longjmps.

Interesting.  You'd need to adjust your macro so as to make sure that
the Lisp_Object variables are initialized before they're added to the
gcpro list, but otherwise it's indeed cleaner than our current macros.
On the performance side, it could be slower depending on how aggressively
gcc optimizes alloca and foo_remove calls and more importantly depending
on whether it handles longjmp for us (which would be less efficient,
tho I don't know if that would be significant).

> This idea is briefly illustrated by an attached example. As for the
> Emacs, it would be enough to declare every local Lisp_Object which
> should survive the GC with the stuff like FOOPTR from this example,
> and we're ready for exact C stack marking with (hopefully) very small
> overhead.

The problem is that the few platforms that don't use GCC are the ones
that require GCPROs as well, so not only it would be a large change, but
it would also require us dropping support for those non-gcc
non-conservative-GC platforms.

I guess this would only make sense if we decide to use this FOOPTR in
preference to conservative stack scanning.  But as it stands, I don't
see it happening, unless we have some compelling reason to do it
(e.g. benchmark showing there's a significant gain, or actual new
feature/code to take advantage of the extra gcpro info).


        Stefan

Re: Finding objects on C stack - alternate GCPRO

[Tom Tromey]

>>>>> "Dmitry" == Dmitry Antipov <dmantipov@yandex.ru> writes:

Dmitry> Everyone agrees that GGPROs are ugly and painful.
[...]
Dmitry> But there is another method to implement GCPROs.

If you really want GCPROs, you could write a GCC plugin to verify that
they are in all the right places.  This would work for all the code that
isn't platform-specific anyway.  Writing a GCC plugin to do custom
checks like this is pretty easy nowadays, you could do it in less than a
day.

I tend to think that GCPRO is worse than conservative marking.  What
advantage does GCPRO have?

Tom

Re: Finding objects on C stack - alternate GCPRO

[Ken Raeburn]

On Nov 16, 2011, at 05:07, Dmitry Antipov wrote:
> But there is another method to implement GCPROs. It looks not very
> portable beyond GNU C since it uses __attribute__ ((cleanup (function)))
> and compound statement expressions C extensions. But it doesn't
> require UNGCPRO and dumbs like 'struct gcpro gcpro1, struct gcpro2, ...'.
> And I believe it should work across longjmps.

I'm not terribly familiar with the cleanup attribute's implementation, but I'm curious to know how it would work in the face of longjmp, which tends to be pretty simple in how it operates and without regard for such things as exception handlers or object destructor functions (which I would expect the implementation of "cleanup" to piggy-back on).

Ken