Updated ggc anti fragmentation patchkit

Updated ggc anti fragmentation patchkit

[Andi Kleen]

I added a special fragmentation fallback to ggc-page to address
the earlier review comments.

-Andi

[PATCH 2/3] Free large chunks in ggc

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

This implements the freeing back of large chunks in the ggc madvise path
Richard Guenther asked for.  This way on systems with limited
address space malloc() and other allocators still have
a chance to get back at some of the memory ggc freed. The
fragmented pages are still just given back, but the address space
stays allocated.

I tried freeing only aligned 2MB areas to optimize for 2MB huge
pages, but the hit rate was quite low, so I switched to 1MB+
unaligned areas. The target size is a param now.

Passed bootstrap and testing on x86_64-linux

gcc/:
2011-10-18  Andi Kleen  <ak@linux.intel.com>

	* ggc-page (release_pages): First free large continuous
	chunks in the madvise path.
	* params.def (GGC_FREE_UNIT): Add.
	* doc/invoke.texi (ggc-free-unit): Add.
---
 gcc/doc/invoke.texi |    5 +++++
 gcc/ggc-page.c      |   48 ++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/params.def      |    5 +++++
 3 files changed, 58 insertions(+), 0 deletions(-)

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 4f55dbc..e622552 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -8858,6 +8858,11 @@ very large effectively disables garbage collection.  Setting this
 parameter and @option{ggc-min-expand} to zero causes a full collection
 to occur at every opportunity.
 
+@item  ggc-free-unit
+
+Continuous areas in OS pages to free back to OS immediately. Default is 256
+pages, which is 1MB with 4K pages. 
+
 @item max-reload-search-insns
 The maximum number of instruction reload should look backward for equivalent
 register.  Increasing values mean more aggressive optimization, making the
diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
index ba88e3f..eb0eeef 100644
--- a/gcc/ggc-page.c
+++ b/gcc/ggc-page.c
@@ -972,6 +972,54 @@ release_pages (void)
   page_entry *p, *start_p;
   char *start;
   size_t len;
+  size_t mapped_len;
+  page_entry *next, *prev, *newprev;
+  size_t free_unit = PARAM_VALUE (GGC_FREE_UNIT) * G.pagesize;
+
+  /* First free larger continuous areas to the OS.
+     This allows other allocators to grab these areas if needed.
+     This is only done on larger chunks to avoid fragmentation. 
+     This does not always work because the free_pages list is only
+     sorted over a single GC cycle. */
+
+  p = G.free_pages;
+  prev = NULL;
+  while (p)
+    {
+      start = p->page;
+      start_p = p;
+      len = 0;
+      mapped_len = 0;
+      newprev = prev;
+      while (p && p->page == start + len)
+        {
+          len += p->bytes;
+	  if (!p->discarded)
+	      mapped_len += p->bytes;
+	  newprev = p;
+          p = p->next;
+        }
+      if (len >= free_unit)
+        {
+          while (start_p != p)
+            {
+              next = start_p->next;
+              free (start_p);
+              start_p = next;
+            }
+          munmap (start, len);
+	  if (prev)
+	    prev->next = p;
+          else
+            G.free_pages = p;
+          G.bytes_mapped -= mapped_len;
+	  continue;
+        }
+      prev = newprev;
+   }
+
+  /* Now give back the fragmented pages to the OS, but keep the address 
+     space to reuse it next time. */
 
   for (p = G.free_pages; p; )
     {
diff --git a/gcc/params.def b/gcc/params.def
index 5e49c48..edbf0de 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -561,6 +561,11 @@ DEFPARAM(GGC_MIN_HEAPSIZE,
 #undef GGC_MIN_EXPAND_DEFAULT
 #undef GGC_MIN_HEAPSIZE_DEFAULT
 
+DEFPARAM(GGC_FREE_UNIT,
+	 "ggc-free-unit",
+	 "Continuous areas in OS pages to free back immediately",
+	 256, 0, 0)
+
 DEFPARAM(PARAM_MAX_RELOAD_SEARCH_INSNS,
 	 "max-reload-search-insns",
 	 "The maximum number of instructions to search backward when looking for equivalent reload",
-- 
1.7.5.4

[PATCH 1/3] Add missing page rounding of a page_entry

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

This one place in ggc forgot to round page_entry->bytes to the
next page boundary, which lead to all the heuristics in freeing to
check for continuous memory failing. Round here too, like all other
allocators already do. The memory consumed should be the same
for MMAP because the kernel would round anyways. It may slightly
increase memory usage when malloc groups are used.

This will also increase the hitrate on the free page list
slightly.

gcc/:

2011-10-18  Andi Kleen  <ak@linux.intel.com>

	* ggc-page.c (alloc_pages): Always round up entry_size.
---
 gcc/ggc-page.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
index 2da99db..ba88e3f 100644
--- a/gcc/ggc-page.c
+++ b/gcc/ggc-page.c
@@ -736,6 +736,7 @@ alloc_page (unsigned order)
   entry_size = num_objects * OBJECT_SIZE (order);
   if (entry_size < G.pagesize)
     entry_size = G.pagesize;
+  entry_size = ROUND_UP (entry_size, G.pagesize);
 
   entry = NULL;
   page = NULL;
-- 
1.7.5.4

[PATCH 3/3] Add a fragmentation fallback in ggc-page

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

There were some concerns that the earlier munmap patch could lead
to address space being freed that cannot be allocated again
by ggc due to fragmentation. This patch adds a fragmentation
fallback to solve this: when a GGC_QUIRE_SIZE sized allocation fails,
try again with a page sized allocation.

Passes bootstrap and testing on x86_64-linux with the fallback
forced artificially.

gcc/:
2011-10-20  Andi Kleen  <ak@linux.intel.com>

	* ggc-page (alloc_anon): Add check argument.
	(alloc_page): Add fallback to 1 page allocation.
	Adjust alloc_anon calls to new argument.
---
 gcc/ggc-page.c |   23 +++++++++++++++--------
 1 files changed, 15 insertions(+), 8 deletions(-)

diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
index eb0eeef..91cd450 100644
--- a/gcc/ggc-page.c
+++ b/gcc/ggc-page.c
@@ -482,7 +482,7 @@ static int ggc_allocated_p (const void *);
 static page_entry *lookup_page_table_entry (const void *);
 static void set_page_table_entry (void *, page_entry *);
 #ifdef USING_MMAP
-static char *alloc_anon (char *, size_t);
+static char *alloc_anon (char *, size_t, bool check);
 #endif
 #ifdef USING_MALLOC_PAGE_GROUPS
 static size_t page_group_index (char *, char *);
@@ -661,7 +661,7 @@ debug_print_page_list (int order)
    compile error unless exactly one of the HAVE_* is defined.  */
 
 static inline char *
-alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size)
+alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size, bool check)
 {
 #ifdef HAVE_MMAP_ANON
   char *page = (char *) mmap (pref, size, PROT_READ | PROT_WRITE,
@@ -674,6 +674,8 @@ alloc_anon (char *pref ATTRIBUTE_UNUSED, size_t size)
 
   if (page == (char *) MAP_FAILED)
     {
+      if (!check)
+        return NULL;
       perror ("virtual memory exhausted");
       exit (FATAL_EXIT_CODE);
     }
@@ -776,13 +778,18 @@ alloc_page (unsigned order)
 	 extras on the freelist.  (Can only do this optimization with
 	 mmap for backing store.)  */
       struct page_entry *e, *f = G.free_pages;
-      int i;
+      int i, entries;
 
-      page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE);
+      page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE, false);
+      if (page == NULL)
+     	{
+	  page = alloc_anon(NULL, G.pagesize, true);
+          entries = 1;
+	}
 
       /* This loop counts down so that the chain will be in ascending
 	 memory order.  */
-      for (i = GGC_QUIRE_SIZE - 1; i >= 1; i--)
+      for (i = entries - 1; i >= 1; i--)
 	{
 	  e = XCNEWVAR (struct page_entry, page_entry_size);
 	  e->order = order;
@@ -795,7 +802,7 @@ alloc_page (unsigned order)
       G.free_pages = f;
     }
   else
-    page = alloc_anon (NULL, entry_size);
+    page = alloc_anon (NULL, entry_size, true);
 #endif
 #ifdef USING_MALLOC_PAGE_GROUPS
   else
@@ -1648,14 +1655,14 @@ init_ggc (void)
      believe, is an unaligned page allocation, which would cause us to
      hork badly if we tried to use it.  */
   {
-    char *p = alloc_anon (NULL, G.pagesize);
+    char *p = alloc_anon (NULL, G.pagesize, true);
     struct page_entry *e;
     if ((size_t)p & (G.pagesize - 1))
       {
 	/* How losing.  Discard this one and try another.  If we still
 	   can't get something useful, give up.  */
 
-	p = alloc_anon (NULL, G.pagesize);
+	p = alloc_anon (NULL, G.pagesize, true);
 	gcc_assert (!((size_t)p & (G.pagesize - 1)));
       }
 
-- 
1.7.5.4

Re: [PATCH 3/3] Add a fragmentation fallback in ggc-page

[Jakub Jelinek]

On Fri, Oct 21, 2011 at 07:52:50AM +0200, Andi Kleen wrote:
> @@ -776,13 +778,18 @@ alloc_page (unsigned order)
>  	 extras on the freelist.  (Can only do this optimization with
>  	 mmap for backing store.)  */
>        struct page_entry *e, *f = G.free_pages;
> -      int i;
> +      int i, entries;
>  
> -      page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE);
> +      page = alloc_anon (NULL, G.pagesize * GGC_QUIRE_SIZE, false);
> +      if (page == NULL)
> +     	{
> +	  page = alloc_anon(NULL, G.pagesize, true);
> +          entries = 1;
> +	}
>  
>        /* This loop counts down so that the chain will be in ascending
>  	 memory order.  */
> -      for (i = GGC_QUIRE_SIZE - 1; i >= 1; i--)
> +      for (i = entries - 1; i >= 1; i--)

entries may be uninitialized here.  Plus indentantion is wrong
(missing space between alloc_anon and (, incorrect amount or kind
(tab vs. spaces) of leading whitespace.

	Jakub

Re: [PATCH 1/3] Add missing page rounding of a page_entry

[Richard Guenther]

On Fri, Oct 21, 2011 at 7:52 AM, Andi Kleen <andi@firstfloor.org> wrote:
> From: Andi Kleen <ak@linux.intel.com>
>
> This one place in ggc forgot to round page_entry->bytes to the
> next page boundary, which lead to all the heuristics in freeing to
> check for continuous memory failing. Round here too, like all other
> allocators already do. The memory consumed should be the same
> for MMAP because the kernel would round anyways. It may slightly
> increase memory usage when malloc groups are used.
>
> This will also increase the hitrate on the free page list
> slightly.

Ok.

Thanks,
RIchard.

> gcc/:
>
> 2011-10-18  Andi Kleen  <ak@linux.intel.com>
>
>        * ggc-page.c (alloc_pages): Always round up entry_size.
> ---
>  gcc/ggc-page.c |    1 +
>  1 files changed, 1 insertions(+), 0 deletions(-)
>
> diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
> index 2da99db..ba88e3f 100644
> --- a/gcc/ggc-page.c
> +++ b/gcc/ggc-page.c
> @@ -736,6 +736,7 @@ alloc_page (unsigned order)
>   entry_size = num_objects * OBJECT_SIZE (order);
>   if (entry_size < G.pagesize)
>     entry_size = G.pagesize;
> +  entry_size = ROUND_UP (entry_size, G.pagesize);
>
>   entry = NULL;
>   page = NULL;
> --
> 1.7.5.4
>
>

Re: [PATCH 1/3] Add missing page rounding of a page_entry

[Jakub Jelinek]

On Fri, Oct 21, 2011 at 11:42:26AM +0200, Richard Guenther wrote:
> On Fri, Oct 21, 2011 at 7:52 AM, Andi Kleen <andi@firstfloor.org> wrote:
> > From: Andi Kleen <ak@linux.intel.com>
> >
> > This one place in ggc forgot to round page_entry->bytes to the
> > next page boundary, which lead to all the heuristics in freeing to
> > check for continuous memory failing. Round here too, like all other
> > allocators already do. The memory consumed should be the same
> > for MMAP because the kernel would round anyways. It may slightly
> > increase memory usage when malloc groups are used.
> >
> > This will also increase the hitrate on the free page list
> > slightly.
> 
> > 2011-10-18  Andi Kleen  <ak@linux.intel.com>
> >
> >        * ggc-page.c (alloc_pages): Always round up entry_size.

As I said in the PR, ROUND_UP should make the previous
  if (entry_size < G.pagesize)
    entry_size = G.pagesize;
completely unnecessary.  Additionally, seeing what ROUND_UP does, it seems
horribly expensive when the second argument is not a constant.
#define ROUND_UP(x, f) (CEIL (x, f) * (f))
#define CEIL(x,y) (((x) + (y) - 1) / (y))
as G.pagesize is variable, I'm afraid the compiler has to divide and
multiply (or perhaps divide and modulo), there is nothing hinting that
G.pagesize is a power of two and thus
(entry_page_size + G.pagesize - 1) & (G.pagesize - 1);
will work.  ggc-page.c relies on G.pagesize to be a power of two though
(and I hope no sane host uses something else), as otherwise
G.lg_pagesize would be -1 and we shift by that amount, so that would be
undefined behavior.

> > diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
> > index 2da99db..ba88e3f 100644
> > --- a/gcc/ggc-page.c
> > +++ b/gcc/ggc-page.c
> > @@ -736,6 +736,7 @@ alloc_page (unsigned order)
> >   entry_size = num_objects * OBJECT_SIZE (order);
> >   if (entry_size < G.pagesize)
> >     entry_size = G.pagesize;
> > +  entry_size = ROUND_UP (entry_size, G.pagesize);
> >
> >   entry = NULL;
> >   page = NULL;
> > --
> > 1.7.5.4
> >
> >

	Jakub

Re: [PATCH 2/3] Free large chunks in ggc

[Richard Guenther]

On Fri, Oct 21, 2011 at 7:52 AM, Andi Kleen <andi@firstfloor.org> wrote:
> From: Andi Kleen <ak@linux.intel.com>
>
> This implements the freeing back of large chunks in the ggc madvise path
> Richard Guenther asked for.  This way on systems with limited
> address space malloc() and other allocators still have
> a chance to get back at some of the memory ggc freed. The
> fragmented pages are still just given back, but the address space
> stays allocated.
>
> I tried freeing only aligned 2MB areas to optimize for 2MB huge
> pages, but the hit rate was quite low, so I switched to 1MB+
> unaligned areas. The target size is a param now.
>
> Passed bootstrap and testing on x86_64-linux
>
> gcc/:
> 2011-10-18  Andi Kleen  <ak@linux.intel.com>
>
>        * ggc-page (release_pages): First free large continuous
>        chunks in the madvise path.
>        * params.def (GGC_FREE_UNIT): Add.
>        * doc/invoke.texi (ggc-free-unit): Add.
> ---
>  gcc/doc/invoke.texi |    5 +++++
>  gcc/ggc-page.c      |   48 ++++++++++++++++++++++++++++++++++++++++++++++++
>  gcc/params.def      |    5 +++++
>  3 files changed, 58 insertions(+), 0 deletions(-)
>
> diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
> index 4f55dbc..e622552 100644
> --- a/gcc/doc/invoke.texi
> +++ b/gcc/doc/invoke.texi
> @@ -8858,6 +8858,11 @@ very large effectively disables garbage collection.  Setting this
>  parameter and @option{ggc-min-expand} to zero causes a full collection
>  to occur at every opportunity.
>
> +@item  ggc-free-unit
> +
> +Continuous areas in OS pages to free back to OS immediately. Default is 256
> +pages, which is 1MB with 4K pages.
> +
>  @item max-reload-search-insns
>  The maximum number of instruction reload should look backward for equivalent
>  register.  Increasing values mean more aggressive optimization, making the
> diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
> index ba88e3f..eb0eeef 100644
> --- a/gcc/ggc-page.c
> +++ b/gcc/ggc-page.c
> @@ -972,6 +972,54 @@ release_pages (void)
>   page_entry *p, *start_p;
>   char *start;
>   size_t len;
> +  size_t mapped_len;
> +  page_entry *next, *prev, *newprev;
> +  size_t free_unit = PARAM_VALUE (GGC_FREE_UNIT) * G.pagesize;
> +
> +  /* First free larger continuous areas to the OS.
> +     This allows other allocators to grab these areas if needed.
> +     This is only done on larger chunks to avoid fragmentation.
> +     This does not always work because the free_pages list is only
> +     sorted over a single GC cycle. */

But release_pages is only called from ggc_collect, or what do you
mean with the above?  Would the hitrate using the quire size increase
if we change how we allocate from the freelist or is it real fragmentation
that causes it?

I'm a bit hesitant to approve the new param, I'd be ok if we just hard-code
quire-size / 2.

Richard.

> +
> +  p = G.free_pages;
> +  prev = NULL;
> +  while (p)
> +    {
> +      start = p->page;
> +      start_p = p;
> +      len = 0;
> +      mapped_len = 0;
> +      newprev = prev;
> +      while (p && p->page == start + len)
> +        {
> +          len += p->bytes;
> +         if (!p->discarded)
> +             mapped_len += p->bytes;
> +         newprev = p;
> +          p = p->next;
> +        }
> +      if (len >= free_unit)
> +        {
> +          while (start_p != p)
> +            {
> +              next = start_p->next;
> +              free (start_p);
> +              start_p = next;
> +            }
> +          munmap (start, len);
> +         if (prev)
> +           prev->next = p;
> +          else
> +            G.free_pages = p;
> +          G.bytes_mapped -= mapped_len;
> +         continue;
> +        }
> +      prev = newprev;
> +   }
> +
> +  /* Now give back the fragmented pages to the OS, but keep the address
> +     space to reuse it next time. */
>
>   for (p = G.free_pages; p; )
>     {
> diff --git a/gcc/params.def b/gcc/params.def
> index 5e49c48..edbf0de 100644
> --- a/gcc/params.def
> +++ b/gcc/params.def
> @@ -561,6 +561,11 @@ DEFPARAM(GGC_MIN_HEAPSIZE,
>  #undef GGC_MIN_EXPAND_DEFAULT
>  #undef GGC_MIN_HEAPSIZE_DEFAULT
>
> +DEFPARAM(GGC_FREE_UNIT,
> +        "ggc-free-unit",
> +        "Continuous areas in OS pages to free back immediately",
> +        256, 0, 0)
> +
>  DEFPARAM(PARAM_MAX_RELOAD_SEARCH_INSNS,
>         "max-reload-search-insns",
>         "The maximum number of instructions to search backward when looking for equivalent reload",
> --
> 1.7.5.4
>
>

Re: [PATCH 1/3] Add missing page rounding of a page_entry

[Andi Kleen]

On Fri, Oct 21, 2011 at 11:52:44AM +0200, Jakub Jelinek wrote:
> On Fri, Oct 21, 2011 at 11:42:26AM +0200, Richard Guenther wrote:
> > On Fri, Oct 21, 2011 at 7:52 AM, Andi Kleen <andi@firstfloor.org> wrote:
> > > From: Andi Kleen <ak@linux.intel.com>
> > >
> > > This one place in ggc forgot to round page_entry->bytes to the
> > > next page boundary, which lead to all the heuristics in freeing to
> > > check for continuous memory failing. Round here too, like all other
> > > allocators already do. The memory consumed should be the same
> > > for MMAP because the kernel would round anyways. It may slightly
> > > increase memory usage when malloc groups are used.
> > >
> > > This will also increase the hitrate on the free page list
> > > slightly.
> > 
> > > 2011-10-18  Andi Kleen  <ak@linux.intel.com>
> > >
> > >        * ggc-page.c (alloc_pages): Always round up entry_size.
> 
> As I said in the PR, ROUND_UP should make the previous
>   if (entry_size < G.pagesize)
>     entry_size = G.pagesize;
> completely unnecessary.  

AFAIK there are objects > pagesize in GGC, but not too many

But you're right it will be somewhat expensive (although the mmap
is not very common anyways and most other allocations
already do the roundup). I can drop it.

-Andi

Re: [PATCH 2/3] Free large chunks in ggc

[Andi Kleen]

> > diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
> > index ba88e3f..eb0eeef 100644
> > --- a/gcc/ggc-page.c
> > +++ b/gcc/ggc-page.c
> > @@ -972,6 +972,54 @@ release_pages (void)
> >   page_entry *p, *start_p;
> >   char *start;
> >   size_t len;
> > +  size_t mapped_len;
> > +  page_entry *next, *prev, *newprev;
> > +  size_t free_unit = PARAM_VALUE (GGC_FREE_UNIT) * G.pagesize;
> > +
> > +  /* First free larger continuous areas to the OS.
> > +     This allows other allocators to grab these areas if needed.
> > +     This is only done on larger chunks to avoid fragmentation.
> > +     This does not always work because the free_pages list is only
> > +     sorted over a single GC cycle. */
> 
> But release_pages is only called from ggc_collect, or what do you

If there was a spike in GC usage and we end up with lots of free
space in the free list afterward we free it back on the next GC cycle.
Then if there's a malloc or other allocator later it can grab
the address space we freed.

That was done to address your earlier concern.

This will only happen on ggc_collect of course.

So one difference from before the madvise patch is that different
generations of free pages can accumulate in the freelist. Before madvise
the freelist would never contain more than one generation.
Normally it's sorted by address due to the way GC works, but there's no 
attempt to keep the sort order over multiple generations.

The "free in batch" heuristic requires sorting, so it will only
work if all the pages are freed in a single gc cycle.

I considered sorting, but it seemed to be too slow.

I can expand the comment on that.


> mean with the above?  Would the hitrate using the quire size increase
> if we change how we allocate from the freelist or is it real fragmentation
> that causes it?

Not sure really about the hitrate. I haven't measured it. If hitrate
was a concern the free list should be probably split into an array.
I'm sure there are lots of other tunings that could be done on the GC,
but probably not by me for now :)

> 
> I'm a bit hesitant to approve the new param, I'd be ok if we just hard-code
> quire-size / 2.

Ok replacing it with a hardcoded value.

-Andi

Re: [PATCH 2/3] Free large chunks in ggc

[Richard Guenther]

On Fri, Oct 21, 2011 at 8:30 PM, Andi Kleen <andi@firstfloor.org> wrote:
>> > diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
>> > index ba88e3f..eb0eeef 100644
>> > --- a/gcc/ggc-page.c
>> > +++ b/gcc/ggc-page.c
>> > @@ -972,6 +972,54 @@ release_pages (void)
>> >   page_entry *p, *start_p;
>> >   char *start;
>> >   size_t len;
>> > +  size_t mapped_len;
>> > +  page_entry *next, *prev, *newprev;
>> > +  size_t free_unit = PARAM_VALUE (GGC_FREE_UNIT) * G.pagesize;
>> > +
>> > +  /* First free larger continuous areas to the OS.
>> > +     This allows other allocators to grab these areas if needed.
>> > +     This is only done on larger chunks to avoid fragmentation.
>> > +     This does not always work because the free_pages list is only
>> > +     sorted over a single GC cycle. */
>>
>> But release_pages is only called from ggc_collect, or what do you
>
> If there was a spike in GC usage and we end up with lots of free
> space in the free list afterward we free it back on the next GC cycle.
> Then if there's a malloc or other allocator later it can grab
> the address space we freed.
>
> That was done to address your earlier concern.
>
> This will only happen on ggc_collect of course.
>
> So one difference from before the madvise patch is that different
> generations of free pages can accumulate in the freelist. Before madvise
> the freelist would never contain more than one generation.
> Normally it's sorted by address due to the way GC works, but there's no
> attempt to keep the sort order over multiple generations.
>
> The "free in batch" heuristic requires sorting, so it will only
> work if all the pages are freed in a single gc cycle.
>
> I considered sorting, but it seemed to be too slow.
>
> I can expand the comment on that.

Ah, now I see ... but that's of course bad - I expect large regions to be
free only after multiple collections.  Can you measure what sorting would
make for a difference?

>
>> mean with the above?  Would the hitrate using the quire size increase
>> if we change how we allocate from the freelist or is it real fragmentation
>> that causes it?
>
> Not sure really about the hitrate. I haven't measured it. If hitrate
> was a concern the free list should be probably split into an array.
> I'm sure there are lots of other tunings that could be done on the GC,
> but probably not by me for now :)

Heh.  Yeah, I suppose the freelist could be changed into a list of
allocation groups with free pages and a bitmap.

Richard.

>>
>> I'm a bit hesitant to approve the new param, I'd be ok if we just hard-code
>> quire-size / 2.
>
> Ok replacing it with a hardcoded value.
>
> -Andi
>

Re: [PATCH 2/3] Free large chunks in ggc

[Richard Guenther]

On Sun, Oct 23, 2011 at 12:23 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Fri, Oct 21, 2011 at 8:30 PM, Andi Kleen <andi@firstfloor.org> wrote:
>>> > diff --git a/gcc/ggc-page.c b/gcc/ggc-page.c
>>> > index ba88e3f..eb0eeef 100644
>>> > --- a/gcc/ggc-page.c
>>> > +++ b/gcc/ggc-page.c
>>> > @@ -972,6 +972,54 @@ release_pages (void)
>>> >   page_entry *p, *start_p;
>>> >   char *start;
>>> >   size_t len;
>>> > +  size_t mapped_len;
>>> > +  page_entry *next, *prev, *newprev;
>>> > +  size_t free_unit = PARAM_VALUE (GGC_FREE_UNIT) * G.pagesize;
>>> > +
>>> > +  /* First free larger continuous areas to the OS.
>>> > +     This allows other allocators to grab these areas if needed.
>>> > +     This is only done on larger chunks to avoid fragmentation.
>>> > +     This does not always work because the free_pages list is only
>>> > +     sorted over a single GC cycle. */
>>>
>>> But release_pages is only called from ggc_collect, or what do you
>>
>> If there was a spike in GC usage and we end up with lots of free
>> space in the free list afterward we free it back on the next GC cycle.
>> Then if there's a malloc or other allocator later it can grab
>> the address space we freed.
>>
>> That was done to address your earlier concern.
>>
>> This will only happen on ggc_collect of course.
>>
>> So one difference from before the madvise patch is that different
>> generations of free pages can accumulate in the freelist. Before madvise
>> the freelist would never contain more than one generation.
>> Normally it's sorted by address due to the way GC works, but there's no
>> attempt to keep the sort order over multiple generations.
>>
>> The "free in batch" heuristic requires sorting, so it will only
>> work if all the pages are freed in a single gc cycle.
>>
>> I considered sorting, but it seemed to be too slow.
>>
>> I can expand the comment on that.
>
> Ah, now I see ... but that's of course bad - I expect large regions to be
> free only after multiple collections.  Can you measure what sorting would
> make for a difference?

I wonder if the free list that falls out of a single collection is sorted
(considering also ggc_free) - if it is, building a new one at each collection
and then merging the two sorted lists should be reasonably fast.

>>
>>> mean with the above?  Would the hitrate using the quire size increase
>>> if we change how we allocate from the freelist or is it real fragmentation
>>> that causes it?
>>
>> Not sure really about the hitrate. I haven't measured it. If hitrate
>> was a concern the free list should be probably split into an array.
>> I'm sure there are lots of other tunings that could be done on the GC,
>> but probably not by me for now :)
>
> Heh.  Yeah, I suppose the freelist could be changed into a list of
> allocation groups with free pages and a bitmap.
>
> Richard.
>
>>>
>>> I'm a bit hesitant to approve the new param, I'd be ok if we just hard-code
>>> quire-size / 2.
>>
>> Ok replacing it with a hardcoded value.
>>
>> -Andi
>>
>

Re: [PATCH 2/3] Free large chunks in ggc

[Andi Kleen]

On Sun, Oct 23, 2011 at 12:24:46PM +0200, Richard Guenther wrote:
> >> space in the free list afterward we free it back on the next GC cycle.
> >> Then if there's a malloc or other allocator later it can grab
> >> the address space we freed.
> >>
> >> That was done to address your earlier concern.
> >>
> >> This will only happen on ggc_collect of course.
> >>
> >> So one difference from before the madvise patch is that different
> >> generations of free pages can accumulate in the freelist. Before madvise
> >> the freelist would never contain more than one generation.
> >> Normally it's sorted by address due to the way GC works, but there's no
> >> attempt to keep the sort order over multiple generations.
> >>
> >> The "free in batch" heuristic requires sorting, so it will only
> >> work if all the pages are freed in a single gc cycle.
> >>
> >> I considered sorting, but it seemed to be too slow.
> >>
> >> I can expand the comment on that.
> >
> > Ah, now I see ... but that's of course bad - I expect large regions to be
> > free only after multiple collections.  Can you measure what sorting would
> > make for a difference?
> 
> I wonder if the free list that falls out of a single collection is sorted

The original author seemed to have assumed it is usually. The 
allocation part tries hard to insert sorted. So I thought it 
was ok to assume.

I stuck in an assert now nd it triggers in a bootstrap on the large
files, so it's not always true (so my earlier assumption was not fully correct)

I suppose it's just another heuristic which is often enough true.

So madvise may not may have it made that much worse.

> (considering also ggc_free) - if it is, building a new one at each collection

ggc_free does not put into the freelist I believe.

> and then merging the two sorted lists should be reasonably fast.

It's definitely not O(1). Ok one could assume it's usually sorted
and do a merge sort with max one pass only. But I'm sceptical 
it's worth the effort, at least without anyone having a test case.
At least for 64bit it's not needed anyways.

-Andi