Re: bug in ggc-page?

[Zack Weinberg <zack at codesourcery dot com>]

Mark Mitchell <mark@codesourcery.com> writes:

> --On Monday, December 16, 2002 11:25:08 AM -0500 Daniel Berlin
> <dberlin@dberlin.org> wrote:
>
>> (I'm not quite sure who originally added the extra_order_size_table, and
>> the inverse_table, annotate tells me it's probably one of you three)
>
> Wasn't me. :-)

Ugh, I was meaning to respond to this.  It was me.

>> But they only occur if the page is for "order <x>" objects, where x > 31.
>
> I don't see anything *fundamentally* broken here, but there is some
> definite weirdness in the types uses.

The algorithm in use deliberately applies integer overflow on multiply
to perform division.  This is a performance hack - we used to have a
general divide op on the critical path for object marking, which is slow.
(The compiler does the same thing when generating code for division by
a constant, but in this case it doesn't know it's got a constant, so I
did the optimization by hand.)  The identity is p / q == (p*a) >> b,
for a,b determined by q and any p that q divides evenly, when all
operations are done using the rules for unsigned arithmetic in C.

You can see that when q is a power of 2, that identity reduces to 
p / q == (p*1) >> log2(q).  Most of the entries in the order table
are of this form.  In particular, *all* of the entries (on a 64-bit
system) with a size greater than 2^31 are of this form.  Thus, while
it's true that the multiplier field is not big enough to handle an
odd-sized object larger than 2^31 bytes ... we don't have any such,
so it shouldn't be a problem.

In fact it's possible to make an even stronger assertion, which is
right there in the code:

  /* There can be only one object per "page" in a bucket for sizes
     larger than half a machine page; it will always have offset
     zero.  */
  if (OBJECT_SIZE (order) > G.pagesize/2)
    {
      if (OBJECTS_PER_PAGE (order) != 1)
        abort ();

      DIV_MULT (order) = 1;
      DIV_SHIFT (order) = 0;
      return;
    }

G.pagesize is invariably much smaller than 2^31, so I honestly do not
see where the problem is coming from here.

Incidentally, there are two pretty huge opportunities for improvement
here.  We waste a *ton* of memory on internal fragmentation; I have
statistics (from back in May) that say that we'd do much better with
more intermediate bucket sizes, but I never got around to doing
anything with this.  (Gory details on request.)

The same statistics say that we almost never allocate any object
larger than half a page (not never; it does happen e.g. when
processing a large, dense switch statement) and it's quite clear that
rounding large objects up to a power of two wastes entire pages of
memory (all of which will be used, if poisoning is on).  It would make
sense to have just one 'large object' chain for things bigger than
half a page, whose sizes would be rounded only to a page boundary.

zw