runtime: reclaim memory used by huge array that is no longer referenced

[ibukanov]

Consider the following program that I run with Go 1.5.2 on 64-bit Fedora Linux:

package main
import "fmt"
func main() {
    a := make([]byte, 185 * 1024 * 1024)
    for i := 0; i < len(a); i += 4096 {
        a[i] = 'x'
    }
    fmt.Printf("%c\n", a[0])
}

It allocates 185MB byte array and then forces OS to commit memory to it via touching all the pages. This programs runs OK and prints expected x even if I restrict the size of available virtual memory per process to 200MB using ulimit:

~/s> ulimit -S -v 204800
~/s> go run test.go
x

Now consider its modification like:

package main
import "fmt"
func main() {
    a := make([]byte, 85 * 1024 * 1024)
    a = nil
    a = make([]byte, 150 * 1024 * 1024)
    for i := 0; i < len(a); i += 4096 {
        a[i] = 'x'
    }
    fmt.Printf("%c\n", a[0])
}

It allocates first 85MB, then clears the reference to the slice, and then allocates 150MB. This time under the same 200MB limit as set with ulimit it fails:

~/s> go run test.go
fatal error: runtime: out of memory

The same failure happens even with the explicit GC call after a = nil:

package main
import "fmt"
import "runtime"
func main() {
    a := make([]byte, 85 * 1024 * 1024)
    a = nil
    runtime.GC()
    a = make([]byte, 150 * 1024 * 1024)
    for i := 0; i < len(a); i += 4096 {
        a[i] = 'x'
    }
    fmt.Printf("%c\n", a[0])
}

Is it just a runtime bug? If not, how can I force the runtime to release a large allocation?

[ianlancetaylor]

This is sort of a dup of #5049.

[randall77]

This seems like a different bug to me.

Say the heap ends in 10 free pages. We try to allocate something 20 pages in size. Currently the code allocates 20 pages from the system to satisfy this request, because the request won't fit in 10 pages. We really only should ask for 10 pages, as they will (probably) be coalesced with the 10 free pages at the end of the heap, resulting in 20 contiguous free pages.

The "probably" in there depends on what the OS decides to give us. If it isn't coalesceable, then asking for only 10 pages doesn't help. In fact it hurts.

Maybe only if we would otherwise throw an out-of-memory error should we try and do this.

[ibukanov]

I thought that this was caused by imprecise GC or something. In any case, why Go cannot release memory back to the system if it knows that there is a big chunk of unused pages and the new allocation cannot be satisfied? Is it because by design heap never shrinks?

[randall77]

No, it is just that we wait some time before releasing pages back to the system, to amortize the cost of allocating them in the first place. What if we add another 85MB allocation to the end of your example?

[ibukanov]

@randall77 My comments was about releasing memory back to the OS when a new allocation fails, not in general. Also, how long Go waits before releasing the memory back to the system? If I modify the program to wait a minute before allocating again, it still fails:

~/s> cat test.go 
package main

import (
    "fmt"
    "runtime"
    "time"
)

func main() {
    a := make([]byte, 85 * 1024 * 1024)
    a = nil
    runtime.GC()
    time.Sleep(time.Minute)
    a = make([]byte, 150 * 1024 * 1024)
    for i := 0; i < len(a); i += 4096 {
        a[i] = 'x'
    }
    fmt.Printf("%c\n", a[0])
}
~/s> ulimit -S -v 204800
~/s> go run test.go 
fatal error: runtime: out of memory

runtime stack:

[randall77]

I see, if an allocation fails we should run a GC, trigger giving memory back to the OS, then try again. That seems reasonable.

I think we currently wait 5 minutes (after being freed by GC) before giving unused memory back to the OS.

[ibukanov]

I modified the program to wait 20 minutes, not one, after GC before trying to allocate again. It still reported out of memory.

[randall77]

That's because you're ulimiting the virtual address space, not the resident set size. When we give memory back to the OS, that just reduces the RSS, not the virtual memory use.

The runtime will need some sort of fix to reuse the virtual address space for the second allocation.

Virtual address size limits are in any case probably not what you want. Virtual address space is essentially free on a 64-bit system.

Also, you've allocated an 85MB chunk and then freed it again. There's no guarantee that the runtime (during runtime.GC or time.Sleep) doesn't allocate something small just after that 85MB chunk. In that case, there's no way to reuse the 85MB of virtual address space for the 150MB allocation.

[ibukanov]

@randall77 Right, restricting just the total amount of physical memory the process can use, not VM space, leads to the example working with timeouts slightly above 5 minutes. So this bug is really about releasing the memory to the OS on out-of-memory without waiting for 5 minutes.

[rsc]

Does debug.FreeOSMemory help?

[aclements]

I found that reproducing this is slightly more complicated now. To grow the RSS, it's necessary to touch the first allocation (otherwise the pages don't get faulted in):

package main

import (
    "fmt"
    "time"
)

func main() {
    a := make([]byte, 85*1024*1024)
    for i := 0; i < len(a); i += 4096 {
        a[i] = 'x'
    }
    a = nil
    //debug.FreeOSMemory()
    time.Sleep(time.Second)
    a = make([]byte, 150*1024*1024)
    for i := 0; i < len(a); i += 4096 {
        a[i] = 'x'
    }
    fmt.Printf("%c\n", a[0])
    time.Sleep(time.Minute)
}

With this code, the process' RSS grows to ~244 MB.

If you comment out the sleep (which allocates) between the two big allocations, we will in fact reuse the whole 85 MB region for the 150 MB region, so the RSS grows to just over 150 MB. I suspect that didn't happen in 1.5.2 when this was originally reported because we didn't trigger the GC aggressively enough before satisfying the second big allocation.

Uncommenting the FreeOSMemory does keep the RSS down, since this GCs the 85MB allocation and immediately scavenges those pages.

However, fixing this is not as simple as just scavenging if we get ENOMEM. For one, there are actually about a dozen places in the runtime where we check for out of memory (most are where we allocate off-heap runtime structures). We could (and possibly should) consolidate these, but then the problem becomes that the scavenger has locking requirements and out-of-memory is detected and handled at a very low level, when we're holding various different locks and when the heap structures may be in an inconsistent state. This mean we'd have to thread the failure up the stack further than we currently do in many places until we reached a point where we could reliably drop locks, call the scavenger, and retry the operation.

[aclements]

An alternative approach would be to get out in front of the problem. I haven't convinced myself if this is a good idea or not yet, but when sweeping frees a large object (for some value of large, probably at least 1 MB and maybe much more), it would be quite easy to release that memory back to the OS immediately. That would actively decouple the physical and virtual memory around large objects so the virtual address space fragmentation caused by large objects didn't cause over-retention of physical memory.

The cost would be releasing and later re-faulting that memory, which would be amortized over the cost of allocating and populating a large object. Faulting on my laptop takes about 70–200µs / MB, and releasing memory takes about 4–30µs / MB (the lower bound is for large pages, the upper bound for regular pages). In contrast, allocating a large object from already faulted memory and fully populating it takes about 450–500µs / MB. Hence, in the worst case, this would increase the cost of allocating large objects by ~46%, but if large pages are available the worst case is more like 16%. Costs in practice would probably be lower.

This solution would also be likely to reduce the running RSS of applications with large heaps, since it effectively makes the scavenger much more aggressive for large objects. This alone would be worth some cost.

Benchmark source

package main

import (
    "fmt"
    "log"
    "runtime"
    "runtime/debug"
    "syscall"
    "time"
)

func main() {
    const bytes = 64 << 20 // Use 1 MB for small pages, 32 MB+ for large pages
    const toMB = bytes / (1 << 20)

    debug.SetGCPercent(-1)

    for i := 0; i < 10; i++ {
        b, err := syscall.Mmap(-1, 0, bytes, syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_PRIVATE|syscall.MAP_ANONYMOUS)
        if err != nil {
            log.Fatal(err)
        }

        start := time.Now()
        for i := 0; i < len(b); i += 4096 {
            b[i] = 'x'
        }
        fault := time.Since(start)

        start = time.Now()
        syscall.Madvise(b, syscall.MADV_DONTNEED)
        release := time.Since(start)

        start = time.Now()
        for i := 0; i < len(b); i += 4096 {
            b[i] = 'x'
        }
        refault := time.Since(start)

        fmt.Println(fault/toMB, "/ MB fault,", release/toMB, "/ MB release,", refault/toMB, "/ MB refault")

        syscall.Munmap(b)
    }

    for i := 0; i < 10; i++ {
        runtime.GC()
        start := time.Now()
        b := make([]byte, bytes)
        for i := 0; i < len(b); i++ {
            b[i] = 'x'
        }
        alloc := time.Since(start)
        fmt.Println(alloc/toMB, "/ MB alloc")
    }
}

[aclements]

An alternative approach would be to get out in front of the problem.

Yet another way to get out in front of the problem would be to eagerly scavenge when we grow the heap or reuse freed memory. This would be less aggressive than my previous sweeping idea, so it would be less likely to free memory that's about to get reused. I think we're in a good position to do this now thanks to @RLH's free span treap, since that should let us quickly find a right-sized chunk of unused memory we can free.

[gopherbot]

Change https://golang.org/cl/138918 mentions this issue: runtime: add physical memory scavenging test

[gopherbot]

Change https://golang.org/cl/139837 mentions this issue: runtime: use only treaps for tracking spans

[gopherbot]

Change https://golang.org/cl/140198 mentions this issue: runtime: mark a span as sysUsed after trimming

[gopherbot]

Change https://golang.org/cl/139297 mentions this issue: runtime: de-duplicate span scavenging

[gopherbot]

Change https://golang.org/cl/144717 mentions this issue: runtime: add predecessor method to treap

[gopherbot]

Change https://golang.org/cl/144718 mentions this issue: runtime: add successor method to treap

[gopherbot]

Change https://golang.org/cl/145999 mentions this issue: runtime: scavenge an mspan's heapBits

[gopherbot]

Change https://golang.org/cl/156417 mentions this issue: runtime: scavenge before heap growth, not after

[gopherbot]

Change https://golang.org/cl/157837 mentions this issue: runtime: don't coalesce scavenged spans with unscavenged spans

[gopherbot]

Change https://golang.org/cl/158078 mentions this issue: runtime: don't coalesce scavenged spans with unscavenged spans

[gopherbot]

Change https://golang.org/cl/159500 mentions this issue: runtime: scavenge memory upon allocating scavenged memory