How does Golang’s garbage collection handle interior pointer? Consider the code below:
type Foo struct {
a,b,c,d int
bar Bar
e,f,g,h int
}
type Bar struct {
a,b,c,d int
}
a := &Foo{}
b := &a.bar
a = nil
// b now points to a little part of `Foo`, but there is no pointer to `Foo` per se
During garbage collection process, Go needs to mark all live objects, and free dead objects. In the example above, We can only know that Bar is alive since there is a pointer to it. But, we can’t free it since we never allocate it. We can only free Foo, but technically, there is no pointer to Foo. How does the garbage collector knows that the address in b is actually came from an allocation to Foo instead to Bar?
I can think one possible way is: by checking the position of the pointer itself, if it belongs to a arena for 96-bytes-sized object, we can round it down to the nearest multiple of 96 to find the header. But, what if the Bar itself is part of a very large slice like this:
a := make([]Foo, 1000000)
b := &a[1000].bar
a = nil
How does Golang knows that b is actually coming from a? The size of the allocation itself is too large and can’t be put inside an arena for fixed-sized object.
I think you should read the implementation documentation of go, go’s gc is to decide whether to release object memory by marking variable objects, the runtime will check the context, reference the variable object, and when there is a variable that is not marked, it means that the variable will be released.
a := make([]Foo, 1000000)
b := &a[1000].bar
a = nil
ms := &runtime.MemStats{}
for {
fmt.Println(b.d) // b -> a so not free
// _ = b // nobody -> so a and b will free
time.Sleep(1 * time.Second)
runtime.GC()
runtime.ReadMemStats(ms)
fmt.Println(float64(ms.Alloc) / 1024 / 1024)
}
How does Golang know that b was allocated from a?
Let’s say a’s address is 0x17700. b address should be 0x2ee20. Now, when the GC runs, during mark phase, there is only one root, which is variable b and the value is 0x2ee20. So Go’s GC need to visit 0x2ee20. But, Go should mark 0x17700, instead of 0x2ee20. How does Go know that 0x2ee20 is actually an interior pointer of 0x17700?
Because the array slice produced by the first a will have a memory region, Go’s garbage collector will record the range of memory regions. As long as there is a pointer to any part of this memory region, the entire memory region is marked as reachable and is not reclaimed.
Because the array slice produced by the first a will have a memory region, Go’s garbage collector will record the range of memory regions. As long as there is a pointer to any part of this memory region, the entire memory region is marked as reachable and is not reclaimed.
Does that mean, for large object, knowing the header of a pointer is not O(1)? Since we need to iterate through all the allocated object to know for sure which one is the header.
Perhaps I was misleading you when I said that Go’s garbage collector is managed based on memory area scopes, not on specific variable objects. As long as there is a pointer to any part of a memory area, the memory area is marked as reachable and is not reclaimed.
Even though I’m talking about variable objects, the meaning is memory, not the abstract object, but the underlying memory.
For example, GC records a 0x1234 to 0x2345 as a memory area that is marked as active when a pointer to the 0x1333 appears.
However, in practice, it is only necessary to record the reference relationship between variable objects to understand the problem of when to release, which is also the most intuitive way of thinking, although this is not the case at the bottom level.
For example, GC records a 0x1234 to 0x2345 as a memory area that is marked as active when a pointer to the 0x1333 appears.
Yeah, but how do you get the 0x1234 from 0x1333. Do you scan the whole allocated region, and check if 0x1333 is between them? Something like this:
func markAddress(p uintptr) { // p = 0x1333
for _, memoryRegion := allMemoryRegionAllocated {
// this loop is O(N), where N is the number of alive memory region
if memoryRegion.start <= p && p < memoryRegion.end {
mark(memoryRegion)
}
}
}
This is the simplest implementation, but the actual source code is not so simple, if you want to dig deeper, you should check out the source code of this piece, this is the most straightforward way.
I just checked go’s runtime code. It’s quite huge, and have a lot of small details. But if I understand it correctly, it seems they use some kind of 2-level radix tree. Some part of the pointer is used to find the element in the radix tree. The element is a span metadata. This span metadata contains which page they belong to. A span normally used to store fixed size objects, and thus have information like the size class, number of element, etc. Large object is just a special case of a span with 1 element. I’m not sure whether I understand it correctly or not
I’m sorry, it’s been a long time since I last looked up the source code, because I’m usually working on the application layer and haven’t reviewed this knowledge. I don’t know exactly what happened now (with the substitution of versions), I only know the general idea of how it works, and I don’t have the energy to study it at the moment (by the way, my algorithmic skills are not very good).
You’ll need to do the rest of the exploration yourself, but if you’re struggling to read the source code, maybe it’s better to try analyzing the source code with the help of GPT or reading some blog posts.