[Bug other/50636] New: GC in large LTO builds cause excessive fragmentation in memory map

[Bug other/50636] New: GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

             Bug #: 50636
           Summary: GC in large LTO builds cause excessive fragmentation
                    in memory map
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: other
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: andi-gcc@firstfloor.org


When doing a very large LTO build I fail with "out of virtual memory"

Some investigation showed the problem was not actually running out of 
memory, but gcc excessively fragmenting its memory map. The Linux kernel
has a default limit of 64k mappings per process and the fragmentation 
exceeded that. This lead to gc mmap allocations failing and other problems.

A workaround is to increase /proc/sys/vm/max_map_count

Looking at /proc/$(pidof lto1)/maps I see there are lots of 1-3 page holes
between other anonymousmemory. I think that's caused by ggc-pages free_pages()
function freeing too early and in too small chunks
(and perhaps LTO garbage collecting too much?)

Re: [Bug other/50636] New: GC in large LTO builds cause excessive fragmentation in memory map

[Jan Hubicka]

> When doing a very large LTO build I fail with "out of virtual memory"
> 
> Some investigation showed the problem was not actually running out of 
> memory, but gcc excessively fragmenting its memory map. The Linux kernel
> has a default limit of 64k mappings per process and the fragmentation 
> exceeded that. This lead to gc mmap allocations failing and other problems.
> 
> A workaround is to increase /proc/sys/vm/max_map_count
> 
> Looking at /proc/$(pidof lto1)/maps I see there are lots of 1-3 page holes
> between other anonymousmemory. I think that's caused by ggc-pages free_pages()
> function freeing too early and in too small chunks
> (and perhaps LTO garbage collecting too much?)

In gcc-2.95 times ggc-page was probably not written with 8GB of memory use in
mind :) Perhaps ggc-page should simply increase the chunks as memory grows?
(i.e. release to system only when 20% of memory is unused & it exceeds some minimal
value)

Honza

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[hubicka at ucw dot cz]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #1 from Jan Hubicka <hubicka at ucw dot cz> 2011-10-06 19:20:45 UTC ---
> When doing a very large LTO build I fail with "out of virtual memory"
> 
> Some investigation showed the problem was not actually running out of 
> memory, but gcc excessively fragmenting its memory map. The Linux kernel
> has a default limit of 64k mappings per process and the fragmentation 
> exceeded that. This lead to gc mmap allocations failing and other problems.
> 
> A workaround is to increase /proc/sys/vm/max_map_count
> 
> Looking at /proc/$(pidof lto1)/maps I see there are lots of 1-3 page holes
> between other anonymousmemory. I think that's caused by ggc-pages free_pages()
> function freeing too early and in too small chunks
> (and perhaps LTO garbage collecting too much?)

In gcc-2.95 times ggc-page was probably not written with 8GB of memory use in
mind :) Perhaps ggc-page should simply increase the chunks as memory grows?
(i.e. release to system only when 20% of memory is unused & it exceeds some
minimal
value)

Honza

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-06 21:29:07 UTC ---
Perhaps on Linux, at least with recentish kernel, we could change release_pages
into keeping the pages in the G.free_pages chain, but call madvise
MADV_DONTNEED on the pages (and remember that we've done that so next
release_pages won't do it again unless we have since then alloc_page'd it).  At
least on 64-bit hosts where there is plenty of address space.  MADV_DONTNEED
will keep it around unless the kernel needs it for something else (something
e.g. glibc malloc uses too).

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #3 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-06 21:31:56 UTC ---
I would prefer to free in 2MB chunks if possible

I was experimenting with increasing the quire size from 1 to 2MB so that a
modern
kernel with transparent huge pages can always get a huge page.

If the freeing also happens in the same chunks the kernel can keep the 2MB
pages together.

But yes MADV_DONTNEED makes sense too.

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-06 21:41:41 UTC ---
Right now alloc_page will (usually) allocate in GGC_QUIRE_SIZE * G.pagesize
chunks, but release_pages will munmap individual pages immediately during
collection (well, using one munmap if there are consecutive free pages, but
that is not very likely everything is going to be freed from the whole 1MB
page).
Guess we could do MADV_DONTNEED on the individual pages immediately and if we
have consecutive 1MB region all free, munmap it (or, decide about that based on
how many free pages we have etc.).  I guess doubling GGC_QUIRE_SIZE is
reasonable too.

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #5 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-06 21:46:32 UTC ---
If it's a 2MB page then madvise MADV_DONTNEED will split it if it's not
2MB aligned. It would be good to optimize the freeing pattern so that this
happens
rarely.

I will try to do some numbers how much 2MB pages improves performance. If yes
we could also do a MADV_HUGEPAGE by default.

But short term fix would be simply to have a threshold for freepages before
freeing?

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #6 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-07 05:47:54 UTC ---
*** Bug 50302 has been marked as a duplicate of this bug. ***

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #7 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-07 05:50:40 UTC ---
*** Bug 50511 has been marked as a duplicate of this bug. ***

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-10-07 08:25:37 UTC ---
(In reply to comment #4)
> Right now alloc_page will (usually) allocate in GGC_QUIRE_SIZE * G.pagesize
> chunks, but release_pages will munmap individual pages immediately during
> collection (well, using one munmap if there are consecutive free pages, but
> that is not very likely everything is going to be freed from the whole 1MB
> page).
> Guess we could do MADV_DONTNEED on the individual pages immediately and if we
> have consecutive 1MB region all free, munmap it (or, decide about that based on
> how many free pages we have etc.).  I guess doubling GGC_QUIRE_SIZE is
> reasonable too.

I guess that's a good idea, separate from the 2mb page issue.  Do other systems
beside Linux have MADV_DONTNEED?  I suppose popular host platforms include
Windows and Mac OS today.

It also seems that we release pages we put on the free list when allocating
a GGC_QUIRE_SIZE * G.pagesize chunk (which we only do if we allocate exactly
one page, otherwise we map a random amount of memory).  Would probably be
interesting to add some instrumentation code to see how the map/munmap
patterns look like ...

But yes, it seems we should unmap only in groups but advise in smaller chunks.

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-07 10:01:32 UTC ---
(In reply to comment #2)
> Perhaps on Linux, at least with recentish kernel, we could change release_pages
> into keeping the pages in the G.free_pages chain, but call madvise
> MADV_DONTNEED on the pages (and remember that we've done that so next
> release_pages won't do it again unless we have since then alloc_page'd it).  At
> least on 64-bit hosts where there is plenty of address space.  MADV_DONTNEED
> will keep it around unless the kernel needs it for something else (something
> e.g. glibc malloc uses too).

Seems I misremembered what MADV_DONTNEED it, what I described was the proposed
and unfortunately shot down MADV_FREE.  MADV_DONTNEED zaps the pages
immediately, so you get new zeroed pages even if it is touched immediately
after the madvise call.  Still, even MADV_DONTNEED is useful, it will prevent
the excessive fragmentation.

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #10 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-07 14:44:10 UTC ---
To track the pattern you can simply use strace or ftrace (I did ftrace)

I checked the kernel code now and if the madvise is big enough it won't
split up the 2MB page. So doing it aggressively should be ok, but still
it may be beneficial to skip it for very scattered pages.

I suspect other OS don't have MADV_DONTNEED, they would probably need Honza's
pool idea.

I did a prototype patch now, will be testing it.

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #11 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-08 16:47:54 UTC ---
Created attachment 25445
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25445
patchkit

I tested this patchkit which implements most of the ideas from this bug,
unfortunately still the same problem (with 20% threshold and madvise)

>From the core file I see a lot of 2-3 page holes still:

65218 load65205     00019000  00002ae45c515000  0000000000000000  bfea1000 
2**12
                  CONTENTS, ALLOC, LOAD
65219 load65206     00018000  00002ae45c52f000  0000000000000000  bfeba000 
2**12
                  CONTENTS, ALLOC, LOAD
65220 load65207     00013000  00002ae45c548000  0000000000000000  bfed2000 
2**12
                  CONTENTS, ALLOC, LOAD
65221 load65208     00019000  00002ae45c55d000  0000000000000000  bfee5000 
2**12
                  CONTENTS, ALLOC, LOAD
65222 load65209     00001000  00002ae45c577000  0000000000000000  bfefe000 
2**12
                  CONTENTS, ALLOC, LOAD
65223 load65210     00044000  00002ae45c579000  0000000000000000  bfeff000 
2**12
                  CONTENTS, ALLOC, LOAD
65224 load65211     0003d000  00002ae45c5be000  0000000000000000  bff43000 
2**12
                  CONTENTS, ALLOC, LOAD
65225 load65212     00021000  00002ae45c5fc000  0000000000000000  bff80000 
2**12
                  CONTENTS, ALLOC, LOAD
65226 load65213     00006000  00002ae45c61e000  0000000000000000  bffa1000 
2**12
                  CONTENTS, ALLOC, LOAD
65227 load65214     0002d000  00002ae45c625000  0000000000000000  bffa7000 
2**12
                  CONTENTS, ALLOC, LOAD
65228 load65215     00041000  00002ae45c653000  0000000000000000  bffd4000 
2**12
                  CONTENTS, ALLOC, LOAD
65229 load65216     0000b000  00002ae45c695000  0000000000000000  c0015000 
2**12
                  CONTENTS, ALLOC, LOAD
65230 load65217     00001000  00002ae45c6a1000  0000000000000000  c0020000 
2**12
                  CONTENTS, ALLOC, LOAD
65231 load65218     0000f000  00002ae45c6a3000  0000000000000000  c0021000 
2**12
                  CONTENTS, ALLOC, LOAD
65232 load65219     00001000  00002ae45c6b3000  0000000000000000  c0030000 
2**12
                  CONTENTS, ALLOC, LOAD
65233 load65220     00031000  00002ae45c6b5000  0000000000000000  c0031000 
2**12
                  CONTENTS, ALLOC, LOAD
65234 load65221     0001a000  00002ae45c6e7000  0000000000000000  c0062000 
2**12
                  CONTENTS, ALLOC, LOAD
65235 load65222     0001c000  00002ae45c702000  0000000000000000  c007c000 
2**12
                  CONTENTS, ALLOC, LOAD

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

Andi Kleen <andi-gcc at firstfloor dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #25445|0                           |1
        is obsolete|                            |

--- Comment #12 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-08 19:54:59 UTC ---
Created attachment 25446
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25446
updated patchkit

This version seems to work. I am at under 1000 mappings now for the case
that failed previously.

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-08 20:14:14 UTC ---
In the 0001-initial-madvise.patch patch I think if you subtract the size
MADV_DONTNEEDed from G.bytes_mapped, then you should add it again in
alloc_page (i.e. replace
+      p->unmapped = false;
+
you've added there with:
+      if (p->unmapped)
+        G.bytes_mapped += p->bytes;
+      p->unmapped = false;
+
Not sure if it is enough as is with that change, or if more is needed - like
also keeping track of the size of currently MADV_DONTNEED bytes and if it grows
too much together with G.bytes_mapped, consider really munmapping some of the
pages (perhaps try to sort the free list by increasing size, so that further
allocations will prefer the smaller blocks over the larger ones, and if getting
close to filled address space, consider freeing some of the largest one in case
malloc would be requested.  Or alternatively, hook into xmalloc_failed and if
malloc fails, try to free some of the largest chunks and retry.  I'm just
worried if at some point during the compilation we need huge amount of GC
memory, close to filling 32-bit address space, then we GC collect lots of it,
but on the other side would need a lot of malloced memory.  But perhaps that is
unlikely to happen.

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #14 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-08 21:10:13 UTC ---
Thanks for the review. Fixed the accounting

I'll leave the xmalloc_failed hook out for now: it would need a retry
path which is somewhat complicated. If it's needed would probably just
add another separate threshold that forces munmapping.

BTW i also filed a bug on the glibc bug this triggered:
http://sourceware.org/bugzilla/show_bug.cgi?id=13276

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[ak at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

--- Comment #15 from ak at gcc dot gnu.org 2011-10-17 14:43:45 UTC ---
Author: ak
Date: Mon Oct 17 14:43:37 2011
New Revision: 180093

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=180093
Log:
Use MADV_DONTNEED for freeing in garbage collector

Use the Linux MADV_DONTNEED call to unmap free pages in the garbage
collector.Then keep the unmapped pages in the free list. This avoid
excessive memory fragmentation on large LTO bulds, which can lead
to gcc bumping into the Linux vm_max_map limit per process.

gcc/:

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

    PR other/50636
    * config.in, configure: Regenerate.
    * configure.ac (madvise): Add to AC_CHECK_FUNCS.
    * ggc-page.c (USING_MADVISE): Add.
    (page_entry): Add discarded field.
    (alloc_page): Check for discarded pages.
    (release_pages): Add USING_MADVISE branch.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config.in
    trunk/gcc/configure
    trunk/gcc/configure.ac
    trunk/gcc/ggc-page.c

[Bug other/50636] GC in large LTO builds cause excessive fragmentation in memory map

[andi-gcc at firstfloor dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50636

Andi Kleen <andi-gcc at firstfloor dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |FIXED

--- Comment #16 from Andi Kleen <andi-gcc at firstfloor dot org> 2011-10-20 00:10:57 UTC ---
Fixed now on Linux (when the kernel supports MADV_DONTNEED) 
Other OS still likely suffer from this likely though.