GUILE_MAX_HEAP_SIZE

GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Hello,

I've implemented an env var GUILE_MAX_HEAP_SIZE (- some lilypond users were complaining that running lily on large sets of files keeps growing the heap forever, leading to trashing).

Please comment on the patch; it's in branch dev/hanwen on sv.git.gnu.org

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi Han-Wen,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> I've implemented an env var GUILE_MAX_HEAP_SIZE (- some lilypond users
> were complaining that running lily on large sets of files keeps
> growing the heap forever, leading to trashing).

Of course, the correct fix would be to help the GC be more reasonable,
as it's currently somewhat broken:

  http://thread.gmane.org/gmane.lisp.guile.devel/6699/focus=6832

You could also try setting `GUILE_MAX_SEGMENT_SIZE' to a smaller value,
as suggested there:

  http://thread.gmane.org/gmane.lisp.guile.devel/6699/focus=6836

> Please comment on the patch; it's in branch dev/hanwen on
> sv.git.gnu.org

The patch contains mostly unrelated indentation changes, can you fix
that?

Also, it gives me the impression that we've definitely lost control over
the GC code, and we're adding yet another configuration variable to work
around that.  :-(

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
> Hi Han-Wen,
> 
> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
> 
>> I've implemented an env var GUILE_MAX_HEAP_SIZE (- some lilypond users
>> were complaining that running lily on large sets of files keeps
>> growing the heap forever, leading to trashing).
> 
> Of course, the correct fix would be to help the GC be more reasonable,
> as it's currently somewhat broken:
> 
>   http://thread.gmane.org/gmane.lisp.guile.devel/6699/focus=6832
> 
> You could also try setting `GUILE_MAX_SEGMENT_SIZE' to a smaller value,
> as suggested there:
> 
>   http://thread.gmane.org/gmane.lisp.guile.devel/6699/focus=6836

I'll have a think about this. Perhaps we can add a more stateful approach to the GC thresholds.

>> Please comment on the patch; it's in branch dev/hanwen on
>> sv.git.gnu.org
> 
> The patch contains mostly unrelated indentation changes, can you fix
> that?

Sure.

> Also, it gives me the impression that we've definitely lost control over
> the GC code, and we're adding yet another configuration variable to work
> around that.  :-(

I'm not against initing it automatically to something like RAM * 0.8 or something, but that would run into portability issues.  In the end, the amount of RAM available is something that the current GC does not factor in, so it will happily grow the heap beyond that.  

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
> Hi Han-Wen,
> 
> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
> 
>> I've implemented an env var GUILE_MAX_HEAP_SIZE (- some lilypond users
>> were complaining that running lily on large sets of files keeps
>> growing the heap forever, leading to trashing).
> 
> Of course, the correct fix would be to help the GC be more reasonable,
> as it's currently somewhat broken:

I am trying to look into this, but can someone explain to me how I should be 
compiling GUILE?

After switching from the 1.8 branch to master, I get

  ./autogen.sh: line 22: gnulib-tool: command not found


I'm on Fedora 9.  Where do I get gnulib-tool ?	

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> After switching from the 1.8 branch to master, I get
>
>   ./autogen.sh: line 22: gnulib-tool: command not found
>
>
> I'm on Fedora 9.  Where do I get gnulib-tool ?	

With "git-clone git://git.sv.gnu.org/gnulib.git".  `gnulib-tool' is a
script that will install the right Gnulib modules into your Guile
directory.

Or you can use the 1.8 branch instead.

Thanks for looking into this!

Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[dsmich]

---- "Ludovic Courtès" <ludo@gnu.org> wrote: 
> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
> 
> > After switching from the 1.8 branch to master, I get
> >
> >   ./autogen.sh: line 22: gnulib-tool: command not found
> >
> >
> > I'm on Fedora 9.  Where do I get gnulib-tool ?	
> 
> With "git-clone git://git.sv.gnu.org/gnulib.git".  `gnulib-tool' is a
> script that will install the right Gnulib modules into your Guile
> directory.

This should probably be added to HACKING.

-Dale

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hey!

<dsmich@adelphia.net> writes:

> ---- "Ludovic Courtès" <ludo@gnu.org> wrote: 

>> With "git-clone git://git.sv.gnu.org/gnulib.git".  `gnulib-tool' is a
>> script that will install the right Gnulib modules into your Guile
>> directory.
>
> This should probably be added to HACKING.

You mean, that `gnulib-tool' is part of Gnulib, and that Gnulib is a GNU
library?  ;-)

(Just kidding, but yeah, could be added.)

Ludo'.

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
> Hi Han-Wen,
> 
> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
> 
>> I've implemented an env var GUILE_MAX_HEAP_SIZE (- some lilypond users
>> were complaining that running lily on large sets of files keeps
>> growing the heap forever, leading to trashing).
> 
> Of course, the correct fix would be to help the GC be more reasonable,
> as it's currently somewhat broken:
> 
>   http://thread.gmane.org/gmane.lisp.guile.devel/6699/focus=6832

> Also, it gives me the impression that we've definitely lost control over
> the GC code, and we're adding yet another configuration variable to work
> around that.  :-(

Hi,

I did a cleanup round over the GC code - see the dev/hanwen branch on
sv.gnu.org ; It seems to work ok, there is a just one annoyance: there
is a commented out assert that works most of the time, but once in a
while is off by a small amount in either direction.  Comments/insights
appreciated.

Unfortunately, I am not the patient type, and also not aflush with
free time, so the changes come as one big bunch, with layout,
refactoring and some bugfixes all lumped together.

(I intend to squash into a single commit before pushing to master).



Garbage collection cleanup.

* Remove data that might be out of date; remove
  scm_i_adjust_min_yield().  We don't store min_yields, since they
  are only accurate at one point in time (when the sweep finishes). 
  We decide the min yield at that point from min_yield_fraction and
  freelist->collected / freelist->swept

* Introduce scm_i_gc_heap_size_delta() replacing
  scm_i_gc_grow_heap_p().
  
* Remove foo_1 fields containing penultimate results.

* After GC, count mark bit vector to discover number of live
  objects. This simplifies hairy updates.

* Many formatting and layout cleanups.

* Fix in scm_i_sweep_card(): return the length of free_list returned,
  rather than number of deleted objects.

* For mtrigger GCs: do not also run a full sweep after the gc() call, as
  this is inconsistent with lazy sweeping.

* Remove scm_i_make_initial_segment().

* Use calloc in scm_i_make_empty_heap_segment() to save on init's.

* New function scm_i_sweep_for_freelist() which sweeps, with proper
  statistic variable updates.

* New segments are conceptually blocks with 100% reclaimable cells.

* Remove some useless constants/comments: SCM_HEAP_SIZE,
  SCM_INIT_HEAP_SIZE, SCM_EXPHEAP, SCM_HEAP_SEG_SIZE

* Do not increment scm_cells_allocated() from the
  scm_[double]cell(). This would be a race condition.

* Move some deprecation checks in separate functions to not distract
  from main code flow.




-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
> Ludovic Courtès escreveu:
>> Hi Han-Wen,
>>
>> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>>
>>> I've implemented an env var GUILE_MAX_HEAP_SIZE (- some lilypond users
>>> were complaining that running lily on large sets of files keeps
>>> growing the heap forever, leading to trashing).
>> Of course, the correct fix would be to help the GC be more reasonable,
>> as it's currently somewhat broken:
>>
>>   http://thread.gmane.org/gmane.lisp.guile.devel/6699/focus=6832
> 
>> Also, it gives me the impression that we've definitely lost control over
>> the GC code, and we're adding yet another configuration variable to work
>> around that.  :-(
> 
> Hi,
> 
> I did a cleanup round over the GC code - see the dev/hanwen branch on
> sv.gnu.org ; It seems to work ok, there is a just one annoyance: there
> is a commented out assert that works most of the time, but once in a
> while is off by a small amount in either direction.  Comments/insights
> appreciated.
> 
> Unfortunately, I am not the patient type, and also not aflush with
> free time, so the changes come as one big bunch, with layout,
> refactoring and some bugfixes all lumped together.
> 
> (I intend to squash into a single commit before pushing to master).
> 
> 
> 
> Garbage collection cleanup.
> 
> * Remove data that might be out of date; remove
>   scm_i_adjust_min_yield().  We don't store min_yields, since they
>   are only accurate at one point in time (when the sweep finishes). 
>   We decide the min yield at that point from min_yield_fraction and
>   freelist->collected / freelist->swept
> 
> * Introduce scm_i_gc_heap_size_delta() replacing
>   scm_i_gc_grow_heap_p().
>   
> * Remove foo_1 fields containing penultimate results.
> 
> * After GC, count mark bit vector to discover number of live
>   objects. This simplifies hairy updates.
> 
> * Many formatting and layout cleanups.
> 
> * Fix in scm_i_sweep_card(): return the length of free_list returned,
>   rather than number of deleted objects.
> 
> * For mtrigger GCs: do not also run a full sweep after the gc() call, as
>   this is inconsistent with lazy sweeping.
> 
> * Remove scm_i_make_initial_segment().
> 
> * Use calloc in scm_i_make_empty_heap_segment() to save on init's.
> 
> * New function scm_i_sweep_for_freelist() which sweeps, with proper
>   statistic variable updates.
> 
> * New segments are conceptually blocks with 100% reclaimable cells.
> 
> * Remove some useless constants/comments: SCM_HEAP_SIZE,
>   SCM_INIT_HEAP_SIZE, SCM_EXPHEAP, SCM_HEAP_SEG_SIZE
> 
> * Do not increment scm_cells_allocated() from the
>   scm_[double]cell(). This would be a race condition.
> 
> * Move some deprecation checks in separate functions to not distract
>   from main code flow.

Note that your 'stress' test runs 10k iterations in about 11mb constant 
RSS (13mb virtual)- this is consistent with its mem requirements; 
it uses 1.1M  cells which is ~8.8M of memory.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
> Hi,
> 
> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
> 
>> After switching from the 1.8 branch to master, I get
>>
>>   ./autogen.sh: line 22: gnulib-tool: command not found
>>
>>
>> I'm on Fedora 9.  Where do I get gnulib-tool ?	
> 
> With "git-clone git://git.sv.gnu.org/gnulib.git".  `gnulib-tool' is a
> script that will install the right Gnulib modules into your Guile
> directory.

I have a request: can you put the gnulib into the repository of GUILE itself?
Gnulib isn't packaged (at least not on fedora), and gnulib is linked/versioned
using the standard mechanisms - isn't this the recommended way to use gnulib 
(install the lib into your package, and only update by hand?)

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
> Ludovic Courtès escreveu:
>> Hi,
>>
>> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>>
>>> After switching from the 1.8 branch to master, I get
>>>
>>>   ./autogen.sh: line 22: gnulib-tool: command not found
>>>
>>>
>>> I'm on Fedora 9.  Where do I get gnulib-tool ?	
>> With "git-clone git://git.sv.gnu.org/gnulib.git".  `gnulib-tool' is a
>> script that will install the right Gnulib modules into your Guile
>> directory.
> 
> I have a request: can you put the gnulib into the repository of GUILE itself?
> Gnulib isn't packaged (at least not on fedora), and gnulib is linked/versioned
> using the standard mechanisms - isn't this the recommended way to use gnulib 
> (install the lib into your package, and only update by hand?)

Note that the current approach makes it impossible to generate a reproducible tarball
of the guile sources.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> I have a request: can you put the gnulib into the repository of GUILE itself?

Yeah, we could do that.

There's a discussion at
http://www.gnu.org/software/gnulib/manual/html_node/VCS-Issues.html .
I'm usually tempted to not include any generated file to the repository,
but Gnulib files are somewhat special.

> Gnulib isn't packaged (at least not on fedora), and gnulib is linked/versioned
> using the standard mechanisms - isn't this the recommended way to use gnulib 
> (install the lib into your package, and only update by hand?)

Gnulib is a *source code* library, see
http://www.gnu.org/software/gnulib/manual/html_node/Introduction.html .

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi Han-Wen,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> I did a cleanup round over the GC code - see the dev/hanwen branch on
> sv.gnu.org ; It seems to work ok, there is a just one annoyance: there
> is a commented out assert that works most of the time, but once in a
> while is off by a small amount in either direction.  Comments/insights
> appreciated.
>
> Unfortunately, I am not the patient type, and also not aflush with
> free time, so the changes come as one big bunch, with layout,
> refactoring and some bugfixes all lumped together.
>
> (I intend to squash into a single commit before pushing to master).

First of all, thanks for your work (I know it's not so much fun to hack
the GC), but I feel unhappy with your commit to both `master' and
`branch_release-1-8'.

As you probably know, it's not customary to commit anything non-trivial
there, especially in the stable branch, without waiting for review, and
while being conscious that the code is slightly broken (!).  We may need
to revert them before going any further.

I'll comment your commits in chronological order.  As their logs are
quite terse, I may be missing the point of some of them.


  * 2072309c1c39cf193687cd895348d2f817537a3e
    Whitespace and formatting fixes.

    I wouldn't do that in tricky code as it makes it harder to audit
    (I'm feeling like a broken record...).

  * 01621bf62ec16cb62260f0b7c9e926793718fd6d
    Include min-yields in gc-stats output.

    Good idea.

  * 51ef99f7fa9fb766fbb48619fc5863ab9914591d
    Fix memory corruption issue with hell[] array: realloc/calloc need to
    factor in sizeof(scm_t_bits)

    -  hell = scm_malloc (hell_size);
    +  hell = scm_calloc (hell_size * sizeof(scm_t_bits));

    Good catch, but it should read:

       hell = scm_calloc (hell_size * sizeof (*hell));

    `sizeof (*hell)' is actually `sizeof (scm_t_bits *)', which is equal
    to `sizeof (scm_t_bits)', but using `sizeof (*hell)' is clearer and
    less error-prone.

    Besides, is that code only used when the one changes the class of an
    instance?  How did you trigger it?

  * b61b5d0ebea924ee4b3930b2cba72e282d4751c7
    Do not include private-gc.h in srfi-60.

    Hmm, well, we really need an `SCM_MIN ()' somewhere.  I'd rather
    duplicate its definition than expand it as you did here, since that
    makes the code rather unreadable.

  * 569aa529d5379f3c942fa6eb01e8a1ad48ba9f77
    Use word_2 to store mark bits for freeing structs and vtables in the
    correct order.

    Can you explain this?  Suppose we have struct S whose vtable is V;
    V cannot be swept in the same GC cycle as S since it's still
    referenced by S.  Thus, I don't understand the need for
    special-casing here.

  * e89b7b36259edb20f60efc0e3e11fa83e5b35b89
    Remove unused macro UNMARKED_CELL_P()

    OK.

  * d09752ffd17688b33a1e828cf4c11f66b86c3c3c
    Introduce scm_i_marking to detect when GC mark bits are touched
    outside of marking stage.

    `ensure_marking ()' must be `static'.  The definition of
    `scm_i_marking' clearly doesn't belong in a header.  Besides, all
    this is unused, so what's the point?

  * b474ac33ee0e47ab14306c218cb060667f9af2db
    Remove comments about removed variables.

    OK.

Stopping here for now.

It's highly unpleasant to have to review things after the fact.  Looks
like both branches are on hold until we've sorted that out, and that
sucks.  Branching exists precisely so that people can work on separate
topics without interfering with each other.

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Han-Wen,

This patch:

  82ae1b8eb3413e6be6bd2aa032986fc7782e85ac
  Garbage collection cleanup.

  Makefile.am        |    8 
  gc-card.c          |  109 ++++++----
  gc-freelist.c      |  150 +++++++-------
  gc-malloc.c        |   24 +-
  gc-mark.c          |    8 
  gc-segment-table.c |  293 ++++++++++++++++++++++++++++
  gc-segment.c       |  545 ++++++++++++-----------------------------------------
  gc.c               |  261 ++++++++++---------------
  gc.h               |    2 
  inline.h           |   10 
  private-gc.h       |   92 +++-----
  11 files changed, 733 insertions(+), 769 deletions(-)

is kind of hard to review in a glimpse.  Does it just randomly "clean
things up" (whatever that means---it does not follow the GCS, for
instance), or does it fix anything?  It's hard to tell.  Can you
reproduce the heap usage graphs referred earlier in this thread?  Do
you have any evidence of improved behavior?  Is it this patch that
triggers the assertion failure you referred to in your first message?
Which assertion is it that fails?

I'm in favor or reverting it, possibly by changing the tip of the
affected branches so that the history remains clearer (sigh...).

When that is done, can you eventually resubmit it as a series of small
patches (like the ones you pushed), making it easier to identify the
fix, if there is one?

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi,

ludo@gnu.org (Ludovic Courtès) writes:

> First of all, thanks for your work (I know it's not so much fun to hack
> the GC), but I feel unhappy with your commit to both `master' and
> `branch_release-1-8'.

Ooops, I thought I had seen these changes on `branch_release-1-8'
through Gitweb but I can no longer see them.  Apologize for that
mistake.

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
>   * 01621bf62ec16cb62260f0b7c9e926793718fd6d
>     Include min-yields in gc-stats output.
> 
>     Good idea.

No, bad idea, and removed in subsequent commit.

> 
>   * 51ef99f7fa9fb766fbb48619fc5863ab9914591d
>     Fix memory corruption issue with hell[] array: realloc/calloc need to
>     factor in sizeof(scm_t_bits)
> 
>     -  hell = scm_malloc (hell_size);
>     +  hell = scm_calloc (hell_size * sizeof(scm_t_bits));
> 
>     Good catch, but it should read:
> 
>        hell = scm_calloc (hell_size * sizeof (*hell));
> 
>     `sizeof (*hell)' is actually `sizeof (scm_t_bits *)', which is equal
>     to `sizeof (scm_t_bits)', but using `sizeof (*hell)' is clearer and
>     less error-prone.
> 
>     Besides, is that code only used when the one changes the class of an
>     instance?  How did you trigger it?

valgrind. Fixed.


>   * b61b5d0ebea924ee4b3930b2cba72e282d4751c7
>     Do not include private-gc.h in srfi-60.
> 
>     Hmm, well, we really need an `SCM_MIN ()' somewhere.  I'd rather
>     duplicate its definition than expand it as you did here, since that
>     makes the code rather unreadable.

I called private-gc.h private for a reason.   Please do not include it 
unless you are called libguile/gc*c; feel free to transplant SCM_MIN to
someplace else.


>   * 569aa529d5379f3c942fa6eb01e8a1ad48ba9f77
>     Use word_2 to store mark bits for freeing structs and vtables in the
>     correct order.
> 
>     Can you explain this?  Suppose we have struct S whose vtable is V;
>     V cannot be swept in the same GC cycle as S since it's still
>     referenced by S.  Thus, I don't understand the need for
>     special-casing here.

Freeing S requires a function stored in V. Hence the subordering.  It used to 
abuse the GC bits for that, causing warning bells to go off in the new code.
(An alternative is reset the bits after they have been used.)

>   * d09752ffd17688b33a1e828cf4c11f66b86c3c3c
>     Introduce scm_i_marking to detect when GC mark bits are touched
>     outside of marking stage.
> 
>     `ensure_marking ()' must be `static'.  The definition of
>     `scm_i_marking' clearly doesn't belong in a header.  Besides, all
>     this is unused, so what's the point?

I'm not sure where to put the code, perhaps in a ifdef DEBUG or something:
the point was to extend SCM_GC_SET_MARK with ensure_marking() to catch illegal 
use of the mark bits.

> It's highly unpleasant to have to review things after the fact.  Looks
> like both branches are on hold until we've sorted that out, and that
> sucks.  Branching exists precisely so that people can work on separate
> topics without interfering with each other.

By rolling back changes, you have just robbed me of the opportunity to see
what it was I did wrong.  Can you remind me again of the sha1 of the stable 
branch?  AFAICR I only pushed trivial fixes there.

Also, if a core contributor apparently need some sort of review process to push 
code they feel comfortable with, can you please post a link to the process?

It's not that I see many reviews of your commits on the list passing by. 

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
> Han-Wen,
> 
> This patch:
> 
>   82ae1b8eb3413e6be6bd2aa032986fc7782e85ac
>   Garbage collection cleanup.
> 
>   Makefile.am        |    8 
>   gc-card.c          |  109 ++++++----
>   gc-freelist.c      |  150 +++++++-------
>   gc-malloc.c        |   24 +-
>   gc-mark.c          |    8 
>   gc-segment-table.c |  293 ++++++++++++++++++++++++++++
>   gc-segment.c       |  545 ++++++++++++-----------------------------------------
>   gc.c               |  261 ++++++++++---------------
>   gc.h               |    2 
>   inline.h           |   10 
>   private-gc.h       |   92 +++-----
>   11 files changed, 733 insertions(+), 769 deletions(-)
> 
> is kind of hard to review in a glimpse.  Does it just randomly "clean
> things up" (whatever that means---it does not follow the GCS, for

GCS?

> instance), or does it fix anything?  It's hard to tell.  Can you
> reproduce the heap usage graphs referred earlier in this thread?  Do

No, the memory usage is more stable now. 

> you have any evidence of improved behavior?  Is it this patch that
> triggers the assertion failure you referred to in your first message?
> Which assertion is it that fails?

This is fixed now.  See my message about our test-suite being broken 
by LD_LIBRARY_PATH.

> I'm in favor or reverting it, possibly by changing the tip of the
> affected branches so that the history remains clearer (sigh...).
> 
> When that is done, can you eventually resubmit it as a series of small
> patches (like the ones you pushed), making it easier to identify the
> fix, if there is one?

I had a look at pulling this change apart, but it is tricky since
many of the changes are interrelated.

I spent more than a day writing and debugging this code - approximately
16 hours over the weekend.  Please keep in mind that I write serious 
software for a living during my 40 hour work week, and don't much time
for GUILE to spare. 

If you think you need to roll back this change, please revoke my 
commit privilege and sort things out yourself.  The garbage collector
isn't that complicated after all.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
> I had a look at pulling this change apart, but it is tricky since
> many of the changes are interrelated.
> 

> If you think you need to roll back this change, please revoke my 
> commit privilege and sort things out yourself.  The garbage collector
> isn't that complicated after all.

Note that I don't mind clarifying any of the code with further commenting.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi Han-Wen,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Ludovic Courtès escreveu:

>> is kind of hard to review in a glimpse.  Does it just randomly "clean
>> things up" (whatever that means---it does not follow the GCS, for
>
> GCS?

"GNU Coding Standards", the thing we're supposed to adhere to when
writing code for the GNU Project:

  http://www.gnu.org/prep/standards/

>> instance), or does it fix anything?  It's hard to tell.  Can you
>> reproduce the heap usage graphs referred earlier in this thread?  Do
>
> No, the memory usage is more stable now. 

Can you show what the graph looks like, for comparison purposes?

>> you have any evidence of improved behavior?  Is it this patch that
>> triggers the assertion failure you referred to in your first message?
>> Which assertion is it that fails?
>
> This is fixed now.  See my message about our test-suite being broken 
> by LD_LIBRARY_PATH.

Which assertion is it that failed?  Was that due to an old
`libguile-i18n.so' being loaded?

> I had a look at pulling this change apart, but it is tricky since
> many of the changes are interrelated.

That's also why it's tricky to review.

> I spent more than a day writing and debugging this code - approximately
> 16 hours over the weekend.  Please keep in mind that I write serious 
> software for a living during my 40 hour work week, and don't much time
> for GUILE to spare. 

Well, I suppose most of us are in this situation, as you probably know.
That doesn't mean we never make mistakes, nor that peer review is
useless.

> If you think you need to roll back this change, please revoke my 
> commit privilege and sort things out yourself.

I tried and failed, and so did Kevin
(http://thread.gmane.org/gmane.lisp.guile.devel/6699/focus=6832).  AIUI,
both Kevin and I tried to identify the root of the problem (the "bug")
in a way that would allow us to fix the offending code as conservatively
as possible.

Conversely, the size and scope of your patch leaves me the impression
that you rewrote parts of the GC, without actually pinpointing what
was/is wrong with the code.  I'd have been much more confident with a
one-liner along with an explanation and sample program to determine
whether the problem is there.

> The garbage collector isn't that complicated after all.

Then the people, including me, who spent large amounts of time trying in
vain to fix the code must have been dumb.

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Ludovic Courtès escreveu:

>>   * 51ef99f7fa9fb766fbb48619fc5863ab9914591d
>>     Fix memory corruption issue with hell[] array: realloc/calloc need to
>>     factor in sizeof(scm_t_bits)
>> 
>>     -  hell = scm_malloc (hell_size);
>>     +  hell = scm_calloc (hell_size * sizeof(scm_t_bits));
>> 
>>     Good catch, but it should read:
>> 
>>        hell = scm_calloc (hell_size * sizeof (*hell));
>> 
>>     `sizeof (*hell)' is actually `sizeof (scm_t_bits *)', which is equal
>>     to `sizeof (scm_t_bits)', but using `sizeof (*hell)' is clearer and
>>     less error-prone.
>> 
>>     Besides, is that code only used when the one changes the class of an
>>     instance?  How did you trigger it?
>
> valgrind. Fixed.

Sorry, I meant: which Scheme code leads to the execution of that code?

>
>>   * b61b5d0ebea924ee4b3930b2cba72e282d4751c7
>>     Do not include private-gc.h in srfi-60.
>> 
>>     Hmm, well, we really need an `SCM_MIN ()' somewhere.  I'd rather
>>     duplicate its definition than expand it as you did here, since that
>>     makes the code rather unreadable.
>
> I called private-gc.h private for a reason.   Please do not include it 
> unless you are called libguile/gc*c; feel free to transplant SCM_MIN to
> someplace else.

I agree on that, but I also think that expanding `SCM_MIN ()' in-place
is not a good idea.

>
>>   * 569aa529d5379f3c942fa6eb01e8a1ad48ba9f77
>>     Use word_2 to store mark bits for freeing structs and vtables in the
>>     correct order.
>> 
>>     Can you explain this?  Suppose we have struct S whose vtable is V;
>>     V cannot be swept in the same GC cycle as S since it's still
>>     referenced by S.  Thus, I don't understand the need for
>>     special-casing here.
>
> Freeing S requires a function stored in V.

Right, but my understanding is that V is still reachable (via S) when S
becomes candidate for sweeping.  Is that right?

>>   * d09752ffd17688b33a1e828cf4c11f66b86c3c3c
>>     Introduce scm_i_marking to detect when GC mark bits are touched
>>     outside of marking stage.
>> 
>>     `ensure_marking ()' must be `static'.  The definition of
>>     `scm_i_marking' clearly doesn't belong in a header.  Besides, all
>>     this is unused, so what's the point?
>
> I'm not sure where to put the code, perhaps in a ifdef DEBUG or something:
> the point was to extend SCM_GC_SET_MARK with ensure_marking() to catch illegal 
> use of the mark bits.

But it's actually unused (at least in this commit), so I'd just remove
it.

> By rolling back changes, you have just robbed me of the opportunity to see
> what it was I did wrong.

I'd have preferred it if your changes had remained in your branch while
we discuss them.  We'd have been able to take time to understand them,
and I wouldn't have had to rush because the thing is already committed.

> Can you remind me again of the sha1 of the stable 
> branch?  AFAICR I only pushed trivial fixes there.

Right, my mistake.  The stable branch is `branch_release-1-8'.

> Also, if a core contributor apparently need some sort of review process to push 
> code they feel comfortable with, can you please post a link to the process?

There's no such document, just an observation of what has been common
practice since I follow Guile development (c. 2004).

> It's not that I see many reviews of your commits on the list passing by. 

Please, see the archive of `guile-devel'.  I rarely commit without
posting here first, and it's proved to be a good tool to improve
quality.

Thanks,
Ludo'.

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Ludovic Courtès escreveu:

>> 
>>   * 51ef99f7fa9fb766fbb48619fc5863ab9914591d
>>     Fix memory corruption issue with hell[] array: realloc/calloc need to
>>     factor in sizeof(scm_t_bits)
>> 
>>     -  hell = scm_malloc (hell_size);
>>     +  hell = scm_calloc (hell_size * sizeof(scm_t_bits));
>> 
>>     Good catch, but it should read:
>> 
>>        hell = scm_calloc (hell_size * sizeof (*hell));
>> 
>>     `sizeof (*hell)' is actually `sizeof (scm_t_bits *)', which is equal
>>     to `sizeof (scm_t_bits)', but using `sizeof (*hell)' is clearer and
>>     less error-prone.
>> 
>>     Besides, is that code only used when the one changes the class of an
>>     instance?  How did you trigger it?
>
> valgrind. Fixed.

Not quite actually: the "hell = scm_malloc (...)" bit is still broken.

BTW, can you please avoid pushing small topic branches like "nit" and
"dev/with-gnulib" to Savannah, as we can't distinguish them from "big"
branches like "vm"?

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Andy Wingo]

On Sun 17 Aug 2008 14:51, ludo@gnu.org (Ludovic Courtès) writes:

> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
>> I have a request: can you put the gnulib into the repository of GUILE itself?
>
> Yeah, we could do that.

I think this would be good; and call be ornery, but a simple import,
refreshed occaisionally, would be better than git submodules.

Andy
-- 
http://wingolog.org/

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:

> Not quite actually: the "hell = scm_malloc (...)" bit is still broken.

?

> BTW, can you please avoid pushing small topic branches like "nit" and
> "dev/with-gnulib" to Savannah, as we can't distinguish them from "big"
> branches like "vm"?

Sorry, - contrary to what may appear, I am still a bit novice with git,
in that some of the default behaviors for git branches were changed not 
too long ago.  The nit thing was an attempt at breaking master, but I 
forgot to remove it. 

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
> Ludovic Courtès escreveu:
> 
>> Not quite actually: the "hell = scm_malloc (...)" bit is still broken.
> 
> ?
> 
>> BTW, can you please avoid pushing small topic branches like "nit" and
>> "dev/with-gnulib" to Savannah, as we can't distinguish them from "big"
>> branches like "vm"?
> 
> Sorry, - contrary to what may appear, I am still a bit novice with git,
> in that some of the default behaviors for git branches were changed not 
> too long ago.  The nit thing was an attempt at breaking master, but I 
> forgot to remove it. 

[an attempt at not breaking master]

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:

>>>        hell = scm_calloc (hell_size * sizeof (*hell));
>>>
>>>     `sizeof (*hell)' is actually `sizeof (scm_t_bits *)', which is equal
>>>     to `sizeof (scm_t_bits)', but using `sizeof (*hell)' is clearer and
>>>     less error-prone.
>>>
>>>     Besides, is that code only used when the one changes the class of an
>>>     instance?  How did you trigger it?
>> valgrind. Fixed.
> 
> Sorry, I meant: which Scheme code leads to the execution of that code?

I have no idea. Some part of the test suite exercises it, but I think it is 
better not to leave such an obvious error there.


>>>     Hmm, well, we really need an `SCM_MIN ()' somewhere.  I'd rather
>>>     duplicate its definition than expand it as you did here, since that
>>>     makes the code rather unreadable.
>> I called private-gc.h private for a reason.   Please do not include it 
>> unless you are called libguile/gc*c; feel free to transplant SCM_MIN to
>> someplace else.
> 
> I agree on that, but I also think that expanding `SCM_MIN ()' in-place
> is not a good idea.

I agree with that, it's just that I prefer to let my responsibility end 
at the boundaries of the GC code.

>>>   * 569aa529d5379f3c942fa6eb01e8a1ad48ba9f77
>>>     Use word_2 to store mark bits for freeing structs and vtables in the
>>>     correct order.
>>>
>>>     Can you explain this?  Suppose we have struct S whose vtable is V;
>>>     V cannot be swept in the same GC cycle as S since it's still
>>>     referenced by S.  Thus, I don't understand the need for
>>>     special-casing here.
>> Freeing S requires a function stored in V.
> 
> Right, but my understanding is that V is still reachable (via S) when S
> becomes candidate for sweeping.  Is that right?

No, the freeing is all for unreachable objects. The problem is that unreachable
objects also may have an ordering: S needs to be freed before V, even if both are 
unreachable.

>>>     `ensure_marking ()' must be `static'.  The definition of
>>>     `scm_i_marking' clearly doesn't belong in a header.  Besides, all
>>>     this is unused, so what's the point?
>> I'm not sure where to put the code, perhaps in a ifdef DEBUG or something:
>> the point was to extend SCM_GC_SET_MARK with ensure_marking() to catch illegal 
>> use of the mark bits.
> 
> But it's actually unused (at least in this commit), so I'd just remove
> it.

Yes - it's not ideal.  I would vote for keeping the is_marking variable, and 
perhaps dropping the ensure_marking() function.  (My experience is that the 
#ifdef DEBUG sections are never exercised, because noone ever bothers to test
and use those secions.)


>> Also, if a core contributor apparently need some sort of review process to push 
>> code they feel comfortable with, can you please post a link to the process?
> 
> There's no such document, just an observation of what has been common
> practice since I follow Guile development (c. 2004).

FWIW, GUILE development seems from the outside very much stagnant, 
even if there are the occasional commits to the master branch.  Perhaps I have
various preconceptions because I also follow LilyPond development, which is 
more turbulent, with more mistakes going in at a higher pace, but also more
discussion and more bugfixing going in at a higher pace.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

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

Ludovic Courtès escreveu:
> Hi Han-Wen,
> 
> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
> 
>> Ludovic Courtès escreveu:
> 
>>> is kind of hard to review in a glimpse.  Does it just randomly "clean
>>> things up" (whatever that means---it does not follow the GCS, for
>> GCS?
> 
> "GNU Coding Standards", the thing we're supposed to adhere to when
> writing code for the GNU Project:

I've pretty religiously followed those for LilyPond although google's 
coding style now has me remove spaces before ( in function calls. 

The existing code was not following GCS by any standard (which was my
fault 7 years ago or so.)

Can you be more specific about this?

>>> instance), or does it fix anything?  It's hard to tell.  Can you
>>> reproduce the heap usage graphs referred earlier in this thread?  Do
>> No, the memory usage is more stable now. 
> 
> Can you show what the graph looks like, for comparison purposes?

See below - note that the old .scm file was pretty much broken, as it 
was using gc-live-object-stats which is only accurate just after the
mark phase.

> Which assertion is it that failed?  Was that due to an old
> `libguile-i18n.so' being loaded?

yes - the old version had a scm_cells_allocated++ inlined, which was
included in the .so file. Also, the 
old version was handling odd cases in scm_i_sweep_card differently. 

>> If you think you need to roll back this change, please revoke my 
>> commit privilege and sort things out yourself.
> 
> I tried and failed, and so did Kevin
> (http://thread.gmane.org/gmane.lisp.guile.devel/6699/focus=6832).  AIUI,
> both Kevin and I tried to identify the root of the problem (the "bug")
> in a way that would allow us to fix the offending code as conservatively
> as possible.

being conservative is a good basic attitude, but I just saw general brokenness
all around.

> Conversely, the size and scope of your patch leaves me the impression
> that you rewrote parts of the GC, without actually pinpointing what
> was/is wrong with the code.  I'd have been much more confident with a
> one-liner along with an explanation and sample program to determine
> whether the problem is there.

The problem is that the previous state of the GC was very much confused
with contradicting definitions within the code of what was being kept as 
statistics.  This is problematic since the allocation strategy (should 
I allocate more memory?) was based on these confused statistics.

This change simplifies and corrects this status.  It does 
not introduce more clever behavior; it just trims any excess intelligence
and confusion from the code.

The thread you quote remarks something odd
about live-cell-heap, which is not that surprising.
The gc-live-object-statistics show the state of the last GC round rather
than the current state. - so it tends to jump around at unpredictable times

Attached is a plot of alive/total, where you can see that it fluctuates between
0.6 and 0.95 - consistent with the 40% yield percentage. Note that summing segments
is misleading: the segments are memory addresses, while the rest uses cells for 
measuring memory allocations. I've included the .scm  (slightly revised because I
trimmed the gc-stats output as well).

>> The garbage collector isn't that complicated after all.
> 
> Then the people, including me, who spent large amounts of time trying in
> vain to fix the code must have been dumb.

Hopefully, with this change, things will become less confused. 

It's still somewhat kludgy - especially the way that gc-stats is 
constructed is asking for trouble.  We should really have a scm_t_gc_stats
struct and use nice OO patterns for dealing with that.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

[-- Attachment #2: foo.png --]
[-- Type: image/png, Size: 5551 bytes --]

[-- Attachment #3: stress.scm --]
[-- Type: text/plain, Size: 1091 bytes --]

(use-modules (srfi srfi-1)
             (srfi srfi-14))

(define (total-cell-heap)
  (assoc-ref (gc-stats) 'cell-heap-size))

(define (get-yields)
  (list 0 0))
  
\f
(setvbuf (current-output-port) _IOLBF)
(format #t "### plot '-' using 1:($2/$3) with lines title \"total/alive\"~%")


# plot 'out' using 1:($2/$3) with lines title "alive/total" 

(let loop ((iteration 0))
  (if (> iteration 1000)
      #t
      (begin
	; 100k cells, 
        (let ((lst (list-tabulate 1000
                                  (lambda (i)
                                    (char-set #\.)  ;; double-cell
                                    (make-list 100)))))

          (if (and (= (modulo iteration 1000) 0)
                   (> iteration 0))
              ;; sporadic heap-intensive job
	      ; 1M cells.
              (make-list 1000000)))

        (if (= 0 (modulo iteration 10))
            (let* ((total (total-cell-heap))
		   (alive (assoc-ref (gc-stats)  'cells-allocated)))
              (format #t "~a ~a ~a~%" iteration
                      alive total )))

        (loop (1+ iteration)))))

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:

>> (I intend to squash into a single commit before pushing to master).
> 
> First of all, thanks for your work (I know it's not so much fun to hack
> the GC), but I feel unhappy with your commit to both `master' and
> `branch_release-1-8'.

On the contrary, I think the GC is one of the more interesting parts. Only
the evaluator is more funky, but I lack the braincells to deal with that 
competently.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Ludovic Courtès escreveu:

> Can you be more specific about this?

Off the top of my head: incorrect indentation, missing spaces around
brackets, and more importantly comments (see (standards.info)Comments).

> See below - note that the old .scm file was pretty much broken, as it 
> was using gc-live-object-stats which is only accurate just after the
> mark phase.

Hmm, `gc-live-object-stats' may return information from the previous
cycle, but it shouldn't be *that* accurate, should it?

Interestingly, head-before-your-changes and 1.8 end up with
`cells-allocated' greater than `total-cell-heap', which I guess isn't
intended (`cells-allocated' and `scm_cells_allocated' are really the
total number of cells allocated since the last GC, right?).  In the case
of 1.8, it's only slightly greater; in the case of
head-before-your-changes, it's more than 80 times greater.  That does
seem to indicate brokenness...

> The problem is that the previous state of the GC was very much confused
> with contradicting definitions within the code of what was being kept as 
> statistics.  This is problematic since the allocation strategy (should 
> I allocate more memory?) was based on these confused statistics.

Which statistics were confused exactly?  Can you pinpoint the part of
your patch that fixes statistics computation?  Otherwise, I find it hard
to say whether it's actually "fixed".

> It's still somewhat kludgy - especially the way that gc-stats is 
> constructed is asking for trouble.  We should really have a scm_t_gc_stats
> struct and use nice OO patterns for dealing with that.

What would you think of using the Boehm et al. GC?

I'm willing to import the BGC-based Guile branch into Git when time
permits, so that we can compare them.

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

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


Ludovic Courtès escreveu:
>> Ludovic Courtès escreveu:
> 
>> Can you be more specific about this?
> 
> Off the top of my head: incorrect indentation, missing spaces around
> brackets, and more importantly comments (see (standards.info)Comments).

The code I went through should not have that; please point me to locations
where things are broken so I can fix them.

>> See below - note that the old .scm file was pretty much broken, as it 
>> was using gc-live-object-stats which is only accurate just after the
>> mark phase.
> 
> Hmm, `gc-live-object-stats' may return information from the previous
> cycle, but it shouldn't be *that* accurate, should it?

No; the current implementation uses a similar scheme to
gc-live-object-stats (counting in the bitvector) to determine the live
object count.  There is now no way that it can ever be larger than the
total heap size.

I also changed the code to not look at the penultimate GC stats, since
I couldn't invent a scenario where that would help, and IMO it only
confuses things.  This may have been a remnant of the pre-lazy sweep
code.


> Interestingly, head-before-your-changes and 1.8 end up with
> `cells-allocated' greater than `total-cell-heap', which I guess isn't
> intended (`cells-allocated' and `scm_cells_allocated' are really the
> total number of cells allocated since the last GC, right?).  In the case
> of 1.8, it's only slightly greater; in the case of
> head-before-your-changes, it's more than 80 times greater.  That does
> seem to indicate brokenness...

There was some confusion about cells vs. double cells vs. bytes, but I
think was mostly in my head and perhaps in your stress test.

If you really want to know, use git bisect.

A likely candidate is the patch from you that I applied. In
particular,
4c7016dc06525c7910ce6c99d97eb9c52c6b43e4

+
+  seg->freelist->collected += collected * seg->span;

looks fishy as this code is called multiple times for a given
card. 


>> The problem is that the previous state of the GC was very much confused
>> with contradicting definitions within the code of what was being kept as 
>> statistics.  This is problematic since the allocation strategy (should 
>> I allocate more memory?) was based on these confused statistics.
> 
> Which statistics were confused exactly?  Can you pinpoint the part of
> your patch that fixes statistics computation?  Otherwise, I find it hard
> to say whether it's actually "fixed".

The scm_t_sweep_statistics were sometimes passed into the sweep
function and sometimes not; I couldn't work out what the global
variables were supposed to mean exactly, and consequently, if their
updates were correct.  The reason I am confident about the statistics
now is the assert()s I added to scm_i_gc(), which compare exactly mark
bit counts, the sweep statistics and freelist statistics.  Some of the
changes I did were to make these numbers match up exactly.

>> It's still somewhat kludgy - especially the way that gc-stats is 
>> constructed is asking for trouble.  We should really have a scm_t_gc_stats
>> struct and use nice OO patterns for dealing with that.
> 
> What would you think of using the Boehm et al. GC?
> 
> I'm willing to import the BGC-based Guile branch into Git when time
> permits, so that we can compare them.

I think we've tried this before, and IIRC it was 50~100% performance
hit.  Of course we could try again, but since we have a much better
understanding of data is laid out, we can be faster.

Unfortunately I don't have time to look into this, but we also be
compact the heap (Bartlett's patents have or are soon to be expired).

I'd be interested in seeing benchmarks between Guile and PLT after my 
cleanup.  For a lot of benchmarks, GC time is an important factor, and
it might be that we can now beat PLT (they use BGC).


BTW, I'm attaching a new plot of the stress test, now up to iteration
10000 (the large allocation).  Interestingly, the large allocation is
cleaned up only once - (on iteration 1000), and remains 'live' after
that, so there may still be some bugs lurking.

BTW2 stress.scm says

                                    (char-set #\.)  ;; double-cell

char-sets are smobs and use single cells, AFAICT.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

[-- Attachment #2: plot.png --]
[-- Type: image/png, Size: 2604 bytes --]

GOOPS memory corruption in `go_to_hell ()'

[Ludovic Courtès]

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

Hi,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Ludovic Courtès escreveu:
>
>> Not quite actually: the "hell = scm_malloc (...)" bit is still broken.
>
> ?

I fixed it, added a ChangeLog and NEWS entry and a test case, and pushed
it to 1.8.

The simplest way to trigger a `go_to_hell ()' call is this:

  (define-class <foo> (<object>) (the-slot #:init-keyword #:value))
  (define f (make <foo> #:value 2))
  (define-class <foo> (<object>) (the-other-slot) (the-slot))
  (slot-ref f 'the-slot)   ;; -> via `TEST_CHANGE_CLASS ()'

The test case is a variation on this, to make it likely to be hit by
out-of-bound accesses to HELL.

Thanks!

Ludo'.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Complete-fix-of-hell-allocation-in-GOOPS.patch --]
[-- Type: text/x-patch, Size: 773 bytes --]

From bb764c0e3c6969bc34154b9212eb0cd04b5f8f87 Mon Sep 17 00:00:00 2001
From: =?utf-8?q?Ludovic=20Court=C3=A8s?= <ludo@gnu.org>
Date: Tue, 19 Aug 2008 19:08:29 +0200
Subject: [PATCH] Complete fix of `hell' allocation in GOOPS.

---
 libguile/goops.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/libguile/goops.c b/libguile/goops.c
index 8f298c5..c09932c 100644
--- a/libguile/goops.c
+++ b/libguile/goops.c
@@ -2995,7 +2995,7 @@ scm_init_goops_builtins (void)
 
   list_of_no_method = scm_permanent_object (scm_list_1 (sym_no_method));
 
-  hell = scm_calloc (hell_size * sizeof(scm_t_bits));
+  hell = scm_calloc (hell_size * sizeof (*hell));
   hell_mutex = scm_permanent_object (scm_make_mutex ());
 
   create_basic_classes ();
-- 
1.5.6.2


[-- Attachment #3: 0002-Add-ChangeLog-and-NEWS-entry-for-the-GOOPS-class-re.patch --]
[-- Type: text/x-patch, Size: 1478 bytes --]

From 4a1db3a91ff5f2b8947d144f4ed3486d1960b34c Mon Sep 17 00:00:00 2001
From: =?utf-8?q?Ludovic=20Court=C3=A8s?= <ludo@gnu.org>
Date: Tue, 19 Aug 2008 19:13:39 +0200
Subject: [PATCH] Add ChangeLog and NEWS entry for the GOOPS `class-redefinition' memory
 corruption fix.

---
 NEWS               |    1 +
 libguile/ChangeLog |    7 +++++++
 2 files changed, 8 insertions(+), 0 deletions(-)

diff --git a/NEWS b/NEWS
index fb5712a..c2bed17 100644
--- a/NEWS
+++ b/NEWS
@@ -57,6 +57,7 @@ This makes these internal functions technically not callable from
 application code.
 
 ** `guile-config link' now prints `-L$libdir' before `-lguile'
+** Fix memory corruption involving GOOPS' `class-redefinition'
 ** Fix build issue on Tru64 and ia64-hp-hpux11.23 (`SCM_UNPACK' macro)
 ** Fix build issue on mips, mipsel, powerpc and ia64 (stack direction)
 ** Fix build issue on hppa2.0w-hp-hpux11.11 (`dirent64' and `readdir64_r')
diff --git a/libguile/ChangeLog b/libguile/ChangeLog
index b4d3f87..15e6b4c 100644
--- a/libguile/ChangeLog
+++ b/libguile/ChangeLog
@@ -1,3 +1,10 @@
+2008-08-19  Han-Wen Nienhuys  <hanwen@lilypond.org>
+	    Ludovic Courtès  <ludo@gnu.org>
+
+	* goops.c (scm_init_goops_builtins, go_to_hell): Fix allocation
+	of `hell' by passing "hell_size * sizeof (*hell)" instead of
+	"hell_size" to `scm_malloc ()' and `scm_realloc ()'.
+
 2008-08-02  Neil Jerram  <neil@ossau.uklinux.net>
 
 	* numbers.c (scm_rationalize): Update docstring to match the
-- 
1.5.6.2


[-- Attachment #4: 0003-Add-test-case-for-the-GOOPS-class-redefinition-mem.patch --]
[-- Type: text/x-patch, Size: 4663 bytes --]

From 82d8d6d9e8ac6a2c36534d6085cd3f96d6278856 Mon Sep 17 00:00:00 2001
From: =?utf-8?q?Ludovic=20Court=C3=A8s?= <ludo@gnu.org>
Date: Wed, 20 Aug 2008 00:44:20 +0200
Subject: [PATCH] Add test case for the GOOPS `class-redefinition' memory corruption.

---
 test-suite/ChangeLog        |    5 +++
 test-suite/tests/goops.test |   75 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 78 insertions(+), 2 deletions(-)

diff --git a/test-suite/ChangeLog b/test-suite/ChangeLog
index 4c0d992..0d6b54c 100644
--- a/test-suite/ChangeLog
+++ b/test-suite/ChangeLog
@@ -1,3 +1,8 @@
+2008-08-19  Ludovic Courtès  <ludo@gnu.org>
+
+	* tests/goops.test (object update)[changing class, `hell' in
+	`goops.c' grows as expected]: New tests.
+
 2008-07-06  Ludovic Courtès  <ludo@gnu.org>
 
 	* standalone/test-asmobs, standalone/test-bad-identifiers,
diff --git a/test-suite/tests/goops.test b/test-suite/tests/goops.test
index e4c2df9..713132a 100644
--- a/test-suite/tests/goops.test
+++ b/test-suite/tests/goops.test
@@ -18,7 +18,8 @@
 ;;;; Boston, MA 02110-1301 USA
 
 (define-module (test-suite test-goops)
-  #:use-module (test-suite lib))
+  #:use-module (test-suite lib)
+  #:autoload   (srfi srfi-1)    (unfold))
 
 (pass-if "GOOPS loads"
 	 (false-if-exception
@@ -277,7 +278,77 @@
 	     (y #:accessor y #:init-value 456)
 	     (z #:accessor z #:init-value 789))
 	  (current-module))
-    (eval '(and (= (y foo) 456) (= (z foo) 789)) (current-module))))
+    (eval '(and (= (y foo) 456) (= (z foo) 789)) (current-module)))
+
+  (pass-if "changing class"
+    (let* ((c1 (class () (the-slot #:init-keyword #:value)))
+           (c2 (class () (the-slot #:init-keyword #:value)
+                         (the-other-slot #:init-value 888)))
+           (o1 (make c1 #:value 777)))
+      (and (is-a? o1 c1)
+           (not (is-a? o1 c2))
+           (equal? (slot-ref o1 'the-slot) 777)
+           (let ((o2 (change-class o1 c2)))
+             (and (eq? o1 o2)
+                  (is-a? o2 c2)
+                  (not (is-a? o2 c1))
+                  (equal? (slot-ref o2 'the-slot) 777))))))
+
+  (pass-if "`hell' in `goops.c' grows as expected"
+    ;; This snippet yielded a segfault prior to the 2008-08-19 `goops.c'
+    ;; fix (i.e., Guile 1.8.5 and earlier).  The root of the problem was
+    ;; that `go_to_hell ()' would not reallocate enough room for the `hell'
+    ;; array, leading to out-of-bounds accesses.
+
+    (let* ((parent-class (class ()
+                           #:name '<class-that-will-be-redefined>))
+           (classes
+            (unfold (lambda (i) (>= i 20))
+                    (lambda (i)
+                      (make-class (list parent-class)
+                                  '((the-slot #:init-value #:value)
+                                    (the-other-slot))
+                                  #:name (string->symbol
+                                          (string-append "<foo-to-redefine-"
+                                                         (number->string i)
+                                                         ">"))))
+                    (lambda (i)
+                      (+ 1 i))
+                    0))
+           (objects
+            (map (lambda (class)
+                   (make class #:value 777))
+                 classes)))
+
+      (define-method (change-class (foo parent-class)
+                                   (new <class>))
+        ;; Called by `scm_change_object_class ()', via `purgatory ()'.
+        (if (null? classes)
+            (next-method)
+            (let ((class  (car classes))
+                  (object (car objects)))
+              (set! classes (cdr classes))
+              (set! objects (cdr objects))
+
+              ;; Redefine the class so that its instances are eventually
+              ;; passed to `scm_change_object_class ()'.  This leads to
+              ;; nested `scm_change_object_class ()' calls, which increases
+              ;; the size of HELL and increments N_HELL.
+              (class-redefinition class
+                                  (make-class '() (class-slots class)
+                                              #:name (class-name class)))
+
+              ;; Use `slot-ref' to trigger the `scm_change_object_class ()'
+              ;; and `go_to_hell ()' calls.
+              (slot-ref object 'the-slot)
+
+              (next-method))))
+
+
+      ;; Initiate the whole `change-class' chain.
+      (let* ((class  (car classes))
+             (object (change-class (car objects) class)))
+        (is-a? object class)))))
 
 (with-test-prefix "object comparison"
   (pass-if "default method"
-- 
1.5.6.2

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hello,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Ludovic Courtès escreveu:

>> Off the top of my head: incorrect indentation, missing spaces around
>> brackets, and more importantly comments (see (standards.info)Comments).
>
> The code I went through should not have that; please point me to locations
> where things are broken so I can fix them.

E.g., from commit:

+/*
+  Classic MIT Hack, see e.g. http://www.tekpool.com/?cat=9
+ */
+int scm_i_uint_bit_count(unsigned int u)

(BTW, it'd make sense to use Gnulib's `count-one-bits' module, which is
able to use GCC's `__builtin_popcount ()'.)

+/*
+  Amount of cells marked in this cell, measured in 1-cells.
+ */
+int
+scm_i_card_marked_count (scm_t_cell *card, int span)

+  while (bvec < bvec_end) {
+    count += scm_i_uint_bit_count(*bvec);
+    bvec ++;
+  }

Other than that, the new `gc-segment-table.c' does look nice to the
eye.  ;-)

>>> See below - note that the old .scm file was pretty much broken, as it 
>>> was using gc-live-object-stats which is only accurate just after the
>>> mark phase.
>> 
>> Hmm, `gc-live-object-stats' may return information from the previous
>> cycle, but it shouldn't be *that* accurate, should it?

Sorry, that should have read "that inaccurate"...

> No; the current implementation uses a similar scheme to
> gc-live-object-stats (counting in the bitvector) to determine the live
> object count.  There is now no way that it can ever be larger than the
> total heap size.

OK.

> I also changed the code to not look at the penultimate GC stats, since
> I couldn't invent a scenario where that would help, and IMO it only
> confuses things.  This may have been a remnant of the pre-lazy sweep
> code.

Well, it's actually hard to "invent" things in that area without any
measurement to back them up.

> There was some confusion about cells vs. double cells vs. bytes, but I
> think was mostly in my head and perhaps in your stress test.
>
> If you really want to know, use git bisect.

I would have expected you to use such an approach when you volunteered
to fix things.

> A likely candidate is the patch from you that I applied. In
> particular,
> 4c7016dc06525c7910ce6c99d97eb9c52c6b43e4

Well, that's a good candidate since it's the last significant change
that was done to the GC on `master'.  However, Kevin's original post
compared 1.8 (which doesn't have this commit) to 1.6.

> +  seg->freelist->collected += collected * seg->span;
>
> looks fishy as this code is called multiple times for a given
> card. 

This very line was already there before the patch (see the diff).

> The scm_t_sweep_statistics were sometimes passed into the sweep
> function and sometimes not; I couldn't work out what the global
> variables were supposed to mean exactly, and consequently, if their
> updates were correct.  The reason I am confident about the statistics
> now is the assert()s I added to scm_i_gc(), which compare exactly mark
> bit counts, the sweep statistics and freelist statistics.  Some of the
> changes I did were to make these numbers match up exactly.

OK, let's hope for the best.  ;-)

> I'd be interested in seeing benchmarks between Guile and PLT after my 
> cleanup.  For a lot of benchmarks, GC time is an important factor, and
> it might be that we can now beat PLT (they use BGC).

Hmm, that seems unlikely to me, but that'd be good news.
>
> BTW, I'm attaching a new plot of the stress test, now up to iteration
> 10000 (the large allocation).  Interestingly, the large allocation is
> cleaned up only once - (on iteration 1000), and remains 'live' after
> that, so there may still be some bugs lurking.

Eh, how fun.

> char-sets are smobs and use single cells, AFAICT.

Right (but `SCM_NEWSMOB{2,3} ()' use double cells, though).

Thanks,
Ludo'.

Gnulib files now in the repository

[Ludovic Courtès]

Hello,

Andy Wingo <wingo@pobox.com> writes:

> On Sun 17 Aug 2008 14:51, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>>
>>> I have a request: can you put the gnulib into the repository of GUILE itself?
>>
>> Yeah, we could do that.
>
> I think this would be good; and call be ornery, but a simple import,
> refreshed occaisionally, would be better than git submodules.

Done!  Let me know if I forgot any files.

That should indeed facilitate testing and reproducibility.

Thanks,
Ludo'.

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
> Hello,
> 
> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
> 
>> Ludovic Courtès escreveu:
> 
>>> Off the top of my head: incorrect indentation, missing spaces around
>>> brackets, and more importantly comments (see (standards.info)Comments).
>> The code I went through should not have that; please point me to locations
>> where things are broken so I can fix them.
> 
> E.g., from commit:
> 
> +/*
> +  Classic MIT Hack, see e.g. http://www.tekpool.com/?cat=9
> + */
> +int scm_i_uint_bit_count(unsigned int u)
> 
> (BTW, it'd make sense to use Gnulib's `count-one-bits' module, which is
> able to use GCC's `__builtin_popcount ()'.)
> 
> +/*
> +  Amount of cells marked in this cell, measured in 1-cells.
> + */
> +int
> +scm_i_card_marked_count (scm_t_cell *card, int span)
> 
> +  while (bvec < bvec_end) {
> +    count += scm_i_uint_bit_count(*bvec);
> +    bvec ++;
> +  }

Yes, sorry about that.  Being at google means that the google style is now
native to me.



-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
>> A likely candidate is the patch from you that I applied. In
>> particular,
>> 4c7016dc06525c7910ce6c99d97eb9c52c6b43e4
> 
> Well, that's a good candidate since it's the last significant change
> that was done to the GC on `master'.  However, Kevin's original post
> compared 1.8 (which doesn't have this commit) to 1.6.

I did a big rewrite of the garbage collector between 1.6 and 1.8; See 

commit 06e80f59f976c8dda5161804f611f489ec2948a2
Author: Han-Wen Nienhuys <hanwen@lilypond.org>
Date:   Tue Dec 10 13:26:25 2002 +0000

and following commits.

This was undoubtedly the cause for this. I hope you don't want me to 
figure what it was I did 6 years ago that caused the breakage.


-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
> Ludovic Courtès escreveu:
>> Hello,
>>
>> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>>
>>> Ludovic Courtès escreveu:
>>>> Off the top of my head: incorrect indentation, missing spaces around
>>>> brackets, and more importantly comments (see (standards.info)Comments).
>>> The code I went through should not have that; please point me to locations
>>> where things are broken so I can fix them.
>> E.g., from commit:
>>
>> +/*
>> +  Classic MIT Hack, see e.g. http://www.tekpool.com/?cat=9
>> + */
>> +int scm_i_uint_bit_count(unsigned int u)
>>
>> (BTW, it'd make sense to use Gnulib's `count-one-bits' module, which is
>> able to use GCC's `__builtin_popcount ()'.)

Could you add the gnulib module? I'll do the rest.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> I did a big rewrite of the garbage collector between 1.6 and 1.8; See 
>
> commit 06e80f59f976c8dda5161804f611f489ec2948a2
> Author: Han-Wen Nienhuys <hanwen@lilypond.org>
> Date:   Tue Dec 10 13:26:25 2002 +0000
>
> and following commits.
>
> This was undoubtedly the cause for this. I hope you don't want me to 
> figure what it was I did 6 years ago that caused the breakage.

Eh.  ;-)

I was not implying you're guilty, just emphasizing that what triggered
the original thread was the difference in heap usage in 1.6 vs 1.8.

Ludo'.

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi,

I just added `master' to the daily build on x86-64 [0] and it fails
there:

  lt-guile: gc.c:609: scm_i_gc: Assertion `scm_i_gc_sweep_stats.collected + scm_cells_allocated == scm_i_gc_sweep_stats.swept' failed.

  http://autobuild.josefsson.org/guile/log-200808220956770665000.txt

GDB forensics:

  (gdb) bt
  #0  0x00002aaaab4fd07b in raise () from /lib/libc.so.6
  #1  0x00002aaaab4fe84e in abort () from /lib/libc.so.6
  #2  0x00002aaaab4f6af4 in __assert_fail () from /lib/libc.so.6
  #3  0x00002aaaaac117c3 in scm_i_gc (what=<value optimized out>) at gc.c:608
  #4  0x00002aaaaac11911 in scm_gc_for_newcell (freelist=0x2aaaaada6920, free_cells=0x5020f8) at gc.c:498
  #5  0x00002aaaaac4478e in make_stringbuf (len=7) at ../libguile/inline.h:178
  #6  0x00002aaaaac45419 in scm_i_c_make_symbol (name=0x2aaaaac7e0c2 "string=", len=23387, flags=6, hash=18446744073709551615, props=0x5b5b) at strings.c:430
  #7  0x00002aaaaac58d46 in scm_i_c_mem2symbol (name=0x2aaaaac7e0c2 "string=", len=7) at symbols.c:139
  #8  0x00002aaaaac36ad3 in scm_c_make_subr (name=0x2aaaaac7e0c2 "string=", type=85, fcn=<value optimized out>) at procs.c:66
  #9  0x00002aaaaac1d04f in create_gsubr (define=1, name=0x2aaaaac7e0c2 "string=", req=2, opt=4, rst=0, fcn=0x2aaaaac4f1c0 <scm_string_eq>) at gsubr.c:80
  #10 0x00002aaaaac4c3d1 in scm_init_srfi_13 () at ../libguile/srfi-13.x:28
  #11 0x00002aaaaac203ef in scm_i_init_guile (base=0x7fffffffe1f8) at init.c:529
  #12 0x00002aaaaac5b798 in scm_i_init_thread_for_guile (base=0x7fffffffe1f8, parent=0x0) at threads.c:661
  #13 0x00002aaaaac5b7cf in scm_i_with_guile_and_parent (func=0x2aaaaac201a0 <invoke_main_func>, data=0x7fffffffe220, parent=0x6) at threads.c:800
  #14 0x00002aaaaac20185 in scm_boot_guile (argc=<value optimized out>, argv=<value optimized out>, main_func=0x6, closure=0xffffffffffffffff) at init.c:353
  #15 0x0000000000400b70 in main (argc=1, argv=0x7fffffffe338) at guile.c:74
  (gdb) frame 3
  #3  0x00002aaaaac117c3 in scm_i_gc (what=<value optimized out>) at gc.c:608
  608       assert (scm_i_gc_sweep_stats.collected + scm_cells_allocated
  (gdb) p scm_i_gc_sweep_stats.collected
  $1 = 15079
  (gdb) p scm_cells_allocated 
  $2 = 3023
  (gdb) p scm_i_gc_sweep_stats.swept 
  $3 = 21147
  (gdb) p 15079 + 3023
  $4 = 18102

I don't observe this failure on my x86 (Core(TM)2 Duo) laptop.

Thanks,
Ludo'.

[0] http://autobuild.josefsson.org/guile/

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Hi,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Han-Wen Nienhuys escreveu:
>> Ludovic Courtès escreveu:

>>> +/*
>>> +  Classic MIT Hack, see e.g. http://www.tekpool.com/?cat=9
>>> + */
>>> +int scm_i_uint_bit_count(unsigned int u)
>>>
>>> (BTW, it'd make sense to use Gnulib's `count-one-bits' module, which is
>>> able to use GCC's `__builtin_popcount ()'.)
>
> Could you add the gnulib module? I'll do the rest.

I asked for re-licensing:

  http://thread.gmane.org/gmane.comp.lib.gnulib.bugs/14349

Once that is done, all you need is to add it to `m4/gnulib-cache.m4',
run "gnulib-tool --update", commit the module changes and additions, and
hack the thing.  You can post the patches before committing, too.  ;-)

Thanks,
Ludovic.

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

ludo@gnu.org (Ludovic Courtès) writes:

> I just added `master' to the daily build on x86-64 [0] and it fails
> there:
>
>   lt-guile: gc.c:609: scm_i_gc: Assertion `scm_i_gc_sweep_stats.collected + scm_cells_allocated == scm_i_gc_sweep_stats.swept' failed.
>
>   http://autobuild.josefsson.org/guile/log-200808220956770665000.txt

A bit of investigation shows that the problem appears starting at commit
82ae1b8eb3413e6be6bd2aa032986fc7782e85ac ("Garbage collection cleanup.")

Ludo'.

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:

> I don't observe this failure on my x86 (Core(TM)2 Duo) laptop.

Let me try to look at this during next week. As a kludge, you can #if 0 the asserts; although the stats will be off (as well as the allocation strategy), nothing bad should happen.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

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

Hi,

ludo@gnu.org (Ludovic Courtès) writes:

> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>> Han-Wen Nienhuys escreveu:
>>> Ludovic Courtès escreveu:
>
>>>> +/*
>>>> +  Classic MIT Hack, see e.g. http://www.tekpool.com/?cat=9
>>>> + */
>>>> +int scm_i_uint_bit_count(unsigned int u)
>>>>
>>>> (BTW, it'd make sense to use Gnulib's `count-one-bits' module, which is
>>>> able to use GCC's `__builtin_popcount ()'.)
>>
>> Could you add the gnulib module? I'll do the rest.
>
> I asked for re-licensing:
>
>   http://thread.gmane.org/gmane.comp.lib.gnulib.bugs/14349
>
> Once that is done, all you need is to add it to `m4/gnulib-cache.m4',
> run "gnulib-tool --update", commit the module changes and additions, and
> hack the thing.  You can post the patches before committing, too.  ;-)

I just did it (patch attached).

Thanks,
Ludo'.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: The patch --]
[-- Type: text/x-patch, Size: 3856 bytes --]

From a8db4a59c898598cc55dd3bd86a6fd8618721d10 Mon Sep 17 00:00:00 2001
From: =?utf-8?q?Ludovic=20Court=C3=A8s?= <ludo@gnu.org>
Date: Tue, 9 Sep 2008 22:46:04 +0200
Subject: [PATCH] Use Gnulib's `count-one-bits' as a replacement for `scm_i_uint_bit_count ()'.

* libguile/gc-card.c: Include <config.h> and <count-one-bits.h>.
  (scm_i_uint_bit_count): Remove.
  (scm_i_card_marked_count): Use `count_one_bits_l ()' instead
  of `scm_i_uint_bit_count ()'.

* libguile/gc-segment.c: Include <config.h> and <count-one-bits.h>.
  (scm_i_heap_segment_marked_count): Use `count_one_bits_l ()' instead
  of `scm_i_uint_bit_count ()'.

* libguile/private-gc.h (scm_i_uint_bit_count): Remove.
---
 libguile/gc-card.c    |   23 ++++++++---------------
 libguile/gc-segment.c |   10 ++++++++--
 libguile/private-gc.h |    1 -
 3 files changed, 16 insertions(+), 18 deletions(-)

diff --git a/libguile/gc-card.c b/libguile/gc-card.c
index 3511533..93e271a 100644
--- a/libguile/gc-card.c
+++ b/libguile/gc-card.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1995,1996,1997,1998,1999,2000,2001, 2002, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+/* Copyright (C) 1995,1996,1997,1998,1999,2000,2001, 2002, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -15,8 +15,14 @@
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  */
 
+#if HAVE_CONFIG_H
+# include <config.h>
+#endif
+
 #include <assert.h>
 #include <stdio.h>
+#include <count-one-bits.h>
+
 #include <gmp.h>
 
 #include "libguile/_scm.h"
@@ -294,19 +300,6 @@ scm_i_init_card_freelist (scm_t_cell *card, SCM *free_list,
 }
 
 /*
-  Classic MIT Hack, see e.g. http://www.tekpool.com/?cat=9
- */
-int scm_i_uint_bit_count (unsigned int u)
-{
-  unsigned int u_count = u 
-    - ((u >> 1) & 033333333333) 
-    - ((u >> 2) & 011111111111);
-  return 
-    ((u_count + (u_count >> 3)) 
-     & 030707070707) % 63;
-}
-
-/*
   Amount of cells marked in this cell, measured in 1-cells.
  */
 int
@@ -318,7 +311,7 @@ scm_i_card_marked_count (scm_t_cell *card, int span)
   int count = 0;
   while (bvec < bvec_end)
     {
-      count += scm_i_uint_bit_count (*bvec);
+      count += count_one_bits_l (*bvec);
       bvec ++;
     }
   return count * span;
diff --git a/libguile/gc-segment.c b/libguile/gc-segment.c
index 4f7b6d5..f53ec96 100644
--- a/libguile/gc-segment.c
+++ b/libguile/gc-segment.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1995,1996,1997,1998,1999,2000,2001, 2002, 2006 Free Software Foundation, Inc.
+/* Copyright (C) 1995,1996,1997,1998,1999,2000,2001, 2002, 2006, 2008 Free Software Foundation, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -15,10 +15,16 @@
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  */
 
+#if HAVE_CONFIG_H
+# include <config.h>
+#endif
+
 #include <assert.h> 
 #include <stdio.h>
 #include <string.h>
 
+#include <count-one-bits.h>
+
 #include "libguile/_scm.h"
 #include "libguile/pairs.h"
 #include "libguile/gc.h"
@@ -109,7 +115,7 @@ scm_i_heap_segment_marked_count (scm_t_heap_segment *seg)
   int count = 0;
   while (bvec < bvec_end)
     {
-      count += scm_i_uint_bit_count (*bvec);
+      count += count_one_bits_l (*bvec);
       bvec ++;
     }
   return count * seg->span;
diff --git a/libguile/private-gc.h b/libguile/private-gc.h
index d738665..93503ce 100644
--- a/libguile/private-gc.h
+++ b/libguile/private-gc.h
@@ -78,7 +78,6 @@
 #define SCM_GC_IN_CARD_HEADERP(x) \
   (scm_t_cell *) (x) <  SCM_GC_CELL_CARD (x) + SCM_GC_CARD_N_HEADER_CELLS
 
-int scm_i_uint_bit_count (unsigned int u);
 int scm_getenv_int (const char *var, int def);
 
 
-- 
1.6.0

Re: GUILE_MAX_HEAP_SIZE

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
> Hi,
> 
> ludo@gnu.org (Ludovic Courtès) writes:
> 
>> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>>> Han-Wen Nienhuys escreveu:
>>>> Ludovic Courtès escreveu:
>>>>> +/*
>>>>> +  Classic MIT Hack, see e.g. http://www.tekpool.com/?cat=9
>>>>> + */
>>>>> +int scm_i_uint_bit_count(unsigned int u)
>>>>>
>>>>> (BTW, it'd make sense to use Gnulib's `count-one-bits' module, which is
>>>>> able to use GCC's `__builtin_popcount ()'.)
>>> Could you add the gnulib module? I'll do the rest.
>> I asked for re-licensing:
>>
>>   http://thread.gmane.org/gmane.comp.lib.gnulib.bugs/14349
>>
>> Once that is done, all you need is to add it to `m4/gnulib-cache.m4',
>> run "gnulib-tool --update", commit the module changes and additions, and
>> hack the thing.  You can post the patches before committing, too.  ;-)
> 
> I just did it (patch attached).

Thanks.  

I'm confused though, 

commit 53f4876abcebf3f05d2a88bba3a898ddcda25a74
Merge: 69f2317... 242ebea...
Author: Ludovic Courtès <ludo@gnu.org>
Date:   Tue Sep 9 22:03:42 2008 +0200

    Merge branch 'master' into strftime-gnulib
    
    Conflicts:
        libguile/ChangeLog
        srfi/ChangeLog
        test-suite/ChangeLog


I thought we were supposed to keep the history linear; did I 
miss something?

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: GUILE_MAX_HEAP_SIZE

[Ludovic Courtès]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> commit 53f4876abcebf3f05d2a88bba3a898ddcda25a74
> Merge: 69f2317... 242ebea...
> Author: Ludovic Courtès <ludo@gnu.org>
> Date:   Tue Sep 9 22:03:42 2008 +0200
>
>     Merge branch 'master' into strftime-gnulib
>     
>     Conflicts:
>         libguile/ChangeLog
>         srfi/ChangeLog
>         test-suite/ChangeLog
>
>
> I thought we were supposed to keep the history linear; did I 
> miss something?

No, *I* did.

Strange, I didn't notice it in "git whatchanged", and I don't get why
there were conflicts in the first place since said files were left
untouched...

Thanks,
Ludo'.