Dive into memory management in Go

struct MSpan
{
	MSpan	*next;		// in a span linked list
	MSpan	*prev;		// in a span linked list
	PageID	start;		// starting page number
	uintptr	npages;		// number of pages in span
	MLink	*freelist;	// list of free objects
...
}

MaxMHeapList = 1<<(20 - PageShift),	// Maximum page length for fixed-size list in MHeap.
HeapAllocChunk = 1<<20,		// Chunk size for heap growth

// Main malloc heap.
// The heap itself is the "free[]" and "large" arrays,
// but all the other global data is here too.
struct MHeap
{
	Lock;
	MSpan free[MaxMHeapList];	// free lists of given length, 256
	MSpan freelarge;		// free lists length >= MaxMHeapList
	MSpan busy[MaxMHeapList];	// busy lists of large objects of given length
	MSpan busylarge;		// busy lists of large objects length >= MaxMHeapList
	MSpan **allspans;		// all spans out there
	MSpan **sweepspans;		// copy of allspans referenced by sweeper
	uint32	nspan;
	uint32	nspancap;
	uint32	sweepgen;		// sweep generation, see comment in MSpan
	uint32	sweepdone;		// all spans are swept

	// span lookup
	MSpan**	spans; ///MSpan指针数组,每个Pageg一项
	uintptr	spans_mapped;

	// range of addresses we might see in the heap
	byte *bitmap;
	uintptr bitmap_mapped;
	byte *arena_start;
	byte *arena_used;
	byte *arena_end;
	bool arena_reserved;

	// central free lists for small size classes.
	// the padding makes sure that the MCentrals are
	// spaced CacheLineSize bytes apart, so that each MCentral.Lock
	// gets its own cache line.
	struct {
		MCentral;
		byte pad[CacheLineSize];
	} central[NumSizeClasses];

	FixAlloc spanalloc;	// allocator for Span*
	FixAlloc cachealloc;	// allocator for MCache*
	FixAlloc specialfinalizeralloc;	// allocator for SpecialFinalizer*
	FixAlloc specialprofilealloc;	// allocator for SpecialProfile*
	Lock speciallock; // lock for sepcial record allocators.

	// Malloc stats.
	uint64 largefree;	// bytes freed for large objects (>MaxSmallSize)
	uint64 nlargefree;	// number of frees for large objects (>MaxSmallSize)
	uint64 nsmallfree[NumSizeClasses];	// number of frees for small objects (<=MaxSmallSize)
};
extern MHeap runtime·mheap; ///全局heap对象

// Try to add at least npage pages of memory to the heap,
// returning whether it worked.
static bool
MHeap_Grow(MHeap *h, uintptr npage)
{
	// Create a fake "in use" span and free it, so that the
	// right coalescing happens.
	s = runtime·FixAlloc_Alloc(&h->spanalloc); ///分配MSpan对象
	runtime·MSpan_Init(s, (uintptr)v>>PageShift, ask>>PageShift);
	p = s->start;
	p -= ((uintptr)h->arena_start>>PageShift); ///address -> MSpan offset
	h->spans[p] = s;
	h->spans[p + s->npages - 1] = s;

// Central list of free objects of a given size.
struct MCentral
{
	Lock;
	int32 sizeclass;
	MSpan nonempty;	// list of spans with a free object
	MSpan empty;	// list of spans with no free objects (or cached in an MCache)
	int32 nfree;	// # of objects available in nonempty spans
};

///runtime/malloc.goc
void*
runtime·MHeap_SysAlloc(MHeap *h, uintptr n)
{
///...
	if(n <= h->arena_end - h->arena_used) { ///area空间足够
		// Keep taking from our reservation.
		p = h->arena_used;
		runtime·SysMap(p, n, h->arena_reserved, &mstats.heap_sys);
		h->arena_used += n;
		runtime·MHeap_MapBits(h); ///更新bitmap_mapped
		runtime·MHeap_MapSpans(h); ///更新spans_mapped
		if(raceenabled)
			runtime·racemapshadow(p, n);
		
		if(((uintptr)p & (PageSize-1)) != 0)
			runtime·throw("misrounded allocation in MHeap_SysAlloc");
		return p;
	}

static MSpan*
MHeap_AllocLocked(MHeap *h, uintptr npage, int32 sizeclass)
{
	uintptr n;
	MSpan *s, *t;
	PageID p;

	// To prevent excessive heap growth, before allocating n pages
	// we need to sweep and reclaim at least n pages.
	if(!h->sweepdone)
		MHeap_Reclaim(h, npage);
	///找到合适大小的链表
	// Try in fixed-size lists up to max.
	for(n=npage; n < nelem(h->free); n++) {
		if(!runtime·MSpanList_IsEmpty(&h->free[n])) {
			s = h->free[n].next;
			goto HaveSpan;
		}
	}

	// Best fit in list of large spans. >=1MB的对象
	if((s = MHeap_AllocLarge(h, npage)) == nil) {
		if(!MHeap_Grow(h, npage)) ///分配失败,则扩展heap
			return nil;
		if((s = MHeap_AllocLarge(h, npage)) == nil)
			return nil;
	}

HaveSpan:
	// Mark span in use.
	if(s->state != MSpanFree)
		runtime·throw("MHeap_AllocLocked - MSpan not free");
	if(s->npages < npage)
		runtime·throw("MHeap_AllocLocked - bad npages");
	runtime·MSpanList_Remove(s); ///从链表中移除s
	runtime·atomicstore(&s->sweepgen, h->sweepgen);
	s->state = MSpanInUse; ///MSpanInUse
	mstats.heap_idle -= s->npages<<PageShift;
	mstats.heap_released -= s->npreleased<<PageShift;
	if(s->npreleased > 0)
		runtime·SysUsed((void*)(s->start<<PageShift), s->npages<<PageShift);
	s->npreleased = 0;

	if(s->npages > npage) {/// s分成2个MSpan
		// Trim extra and put it back in the heap.
		t = runtime·FixAlloc_Alloc(&h->spanalloc);///分配一个新的MSpan
		runtime·MSpan_Init(t, s->start + npage, s->npages - npage);
		s->npages = npage;
		p = t->start;
		p -= ((uintptr)h->arena_start>>PageShift);
		if(p > 0)
			h->spans[p-1] = s;
		h->spans[p] = t;
		h->spans[p+t->npages-1] = t;
		t->needzero = s->needzero;
		runtime·atomicstore(&t->sweepgen, h->sweepgen);
		t->state = MSpanInUse;
		MHeap_FreeLocked(h, t); ///将剩余的MSpan放回空闲链
		t->unusedsince = s->unusedsince; // preserve age
	}
	s->unusedsince = 0;

	// Record span info, because gc needs to be
	// able to map interior pointer to containing span.
	s->sizeclass = sizeclass;
	s->elemsize = (sizeclass==0 ? s->npages<<PageShift : runtime·class_to_size[sizeclass]);
	s->types.compression = MTypes_Empty;
	p = s->start;
	p -= ((uintptr)h->arena_start>>PageShift);
	for(n=0; n<npage; n++)
		h->spans[p+n] = s; ///设置h->spans,指向相同的MSpan
	return s;
}

/// runtime/mheap.c
// Try to add at least npage pages of memory to the heap,
// returning whether it worked.
static bool
MHeap_Grow(MHeap *h, uintptr npage)
{
	uintptr ask;
	void *v;
	MSpan *s;
	PageID p;

	// Ask for a big chunk, to reduce the number of mappings
	// the operating system needs to track; also amortizes
	// the overhead of an operating system mapping.
	// Allocate a multiple of 64kB (16 pages).
	npage = (npage+15)&~15; //16个page的整数倍
	ask = npage<<PageShift;
	if(ask < HeapAllocChunk) ///至少1MB
		ask = HeapAllocChunk;

	v = runtime·MHeap_SysAlloc(h, ask);///从OS申请内存
	if(v == nil) {
		if(ask > (npage<<PageShift)) {
			ask = npage<<PageShift;
			v = runtime·MHeap_SysAlloc(h, ask);
		}
		if(v == nil) {
			runtime·printf("runtime: out of memory: cannot allocate %D-byte block (%D in use)\n", (uint64)ask, mstats.heap_sys);
			return false;
		}
	}

	// Create a fake "in use" span and free it, so that the
	// right coalescing happens.
	s = runtime·FixAlloc_Alloc(&h->spanalloc); ///分配MSpan对象
	runtime·MSpan_Init(s, (uintptr)v>>PageShift, ask>>PageShift);
	p = s->start;
	p -= ((uintptr)h->arena_start>>PageShift); ///address -> MSpan offset
	h->spans[p] = s;
	h->spans[p + s->npages - 1] = s;
	runtime·atomicstore(&s->sweepgen, h->sweepgen);
	s->state = MSpanInUse;
	MHeap_FreeLocked(h, s); ///加入空闲链表(freelarge)
	return true;
}

void*
runtime·mallocgc(uintptr size, uintptr typ, uint32 flag)
{
//...
		if(s->freelist == nil)
			s = runtime·MCache_Refill(c, sizeclass);
}

// Gets a span that has a free object in it and assigns it
// to be the cached span for the given sizeclass.  Returns this span.
MSpan*
runtime·MCache_Refill(MCache *c, int32 sizeclass)
{

	// Get a new cached span from the central lists.
	s = runtime·MCentral_CacheSpan(&runtime·mheap.central[sizeclass]);

	c->alloc[sizeclass] = s;
	m->locks--;
	return s;
}

//runtime/mcentral.c
// Allocate a span to use in an MCache.
MSpan*
runtime·MCentral_CacheSpan(MCentral *c)
{
///...
retry:
	for(s = c->nonempty.next; s != &c->nonempty; s = s->next) { ///有空闲空间MSpan链表
		// we have a nonempty span that does not require sweeping, allocate from it
		goto havespan;
	}

	// Replenish central list if empty.
	if(!MCentral_Grow(c)) {///从heap取一个MSpan
		runtime·unlock(c);
		return nil;
	}
	goto retry;
}

havespan:
	cap = (s->npages << PageShift) / s->elemsize;
	n = cap - s->ref;

	c->nfree -= n;
	runtime·MSpanList_Remove(s);
	runtime·MSpanList_InsertBack(&c->empty, s); ///加到非空闲链表
	s->incache = true;
	runtime·unlock(c);
	return s;
}

// FixAlloc is a simple free-list allocator for fixed size objects.
// Malloc uses a FixAlloc wrapped around SysAlloc to manages its
// MCache and MSpan objects.
//
// Memory returned by FixAlloc_Alloc is not zeroed.
// The caller is responsible for locking around FixAlloc calls.
// Callers can keep state in the object but the first word is
// smashed by freeing and reallocating.
struct FixAlloc
{
	uintptr	size; ///entry size
	void	(*first)(void *arg, byte *p);	// called first time p is returned
	void*	arg;
	MLink*	list;
	byte*	chunk; ///内存(还有空闲空间)
	uint32	nchunk; ///chunk所指内存大小
	uintptr	inuse;	// in-use bytes now
	uint64*	stat;
};

// A generic linked list of blocks.  (Typically the block is bigger than sizeof(MLink).)
struct MLink
{
	MLink *next;
};

///runtime/mfixalloc.c
void*
runtime·FixAlloc_Alloc(FixAlloc *f)
{
	void *v;
	
	if(f->list) {///链表有释放的entry(entry释放时,会加入该list)
		v = f->list;
		f->list = *(void**)f->list;///指向下一个entry
		f->inuse += f->size;
		return v;
	}
	if(f->nchunk < f->size) { ///内存不够,则分配一块新的内存
		f->chunk = runtime·persistentalloc(FixAllocChunk, 0, f->stat); ///从系统分配FixAllocChunk大小的内存
		f->nchunk = FixAllocChunk;///16KB
	}
	v = f->chunk;
	if(f->first)
		f->first(f->arg, v);
	f->chunk += f->size;
	f->nchunk -= f->size;
	f->inuse += f->size;
	return v;
}

// Free the object whose base pointer is v.
void
runtime·free(void *v)
{

int32
runtime·mlookup(void *v, byte **base, uintptr *size, MSpan **sp)
{
	s = runtime·MHeap_LookupMaybe(&runtime·mheap, v);
///...
}

MSpan*
runtime·MHeap_LookupMaybe(MHeap *h, void *v)
{
	MSpan *s;
	PageID p, q;

	p = (uintptr)v>>PageShift;
	q = p;
	q -= (uintptr)h->arena_start >> PageShift; ///offset from arena_start
	s = h->spans[q];
	return s;
}

// Free the object whose base pointer is v.
void
runtime·free(void *v)
{
///...
    if(sizeclass == 0) {
        // Large object.
        s->needzero = 1; ///大对象直接返给heap
            runtime·MHeap_Free(&runtime·mheap, s, 1);
        c->local_nlargefree++;
        c->local_largefree += size;
    }

// Return s to the heap.  s must be unused (s->ref == 0).  Unlocks c.
static void
MCentral_ReturnToHeap(MCentral *c, MSpan *s)
{
    s->needzero = 1

// Free the span back into the heap.
void
runtime·MHeap_Free(MHeap *h, MSpan *s, int32 acct)
{
	runtime·lock(h);
	mstats.heap_alloc += m->mcache->local_cachealloc;
	m->mcache->local_cachealloc = 0;
	mstats.heap_inuse -= s->npages<<PageShift;
	if(acct) {
		mstats.heap_alloc -= s->npages<<PageShift;
		mstats.heap_objects--;
	}
	MHeap_FreeLocked(h, s);
	runtime·unlock(h);
}
///已经调用runtime.lock(h)
static void
MHeap_FreeLocked(MHeap *h, MSpan *s)
{
	MSpan *t;
	PageID p;

	s->types.compression = MTypes_Empty;

	if(s->state != MSpanInUse || s->ref != 0 || s->sweepgen != h->sweepgen) {
		runtime·printf("MHeap_FreeLocked - span %p ptr %p state %d ref %d sweepgen %d/%d\n",
			s, s->start<<PageShift, s->state, s->ref, s->sweepgen, h->sweepgen);
		runtime·throw("MHeap_FreeLocked - invalid free");
	}
	mstats.heap_idle += s->npages<<PageShift;
	s->state = MSpanFree;  ///MSpanFree状态
	runtime·MSpanList_Remove(s); ///从链表删除
	// Stamp newly unused spans. The scavenger will use that
	// info to potentially give back some pages to the OS.
	s->unusedsince = runtime·nanotime(); ///更新unused time
	s->npreleased = 0;
	///尝试与前后MSpan合并
	// Coalesce with earlier, later spans.
	p = s->start;
	p -= (uintptr)h->arena_start >> PageShift;
	if(p > 0 && (t = h->spans[p-1]) != nil && t->state != MSpanInUse) {
		s->start = t->start;
		s->npages += t->npages;
		s->npreleased = t->npreleased; // absorb released pages
		s->needzero |= t->needzero;
		p -= t->npages;
		h->spans[p] = s;
		runtime·MSpanList_Remove(t);
		t->state = MSpanDead;
		runtime·FixAlloc_Free(&h->spanalloc, t);
	}
	if((p+s->npages)*sizeof(h->spans[0]) < h->spans_mapped && (t = h->spans[p+s->npages]) != nil && t->state != MSpanInUse) {
		s->npages += t->npages;
		s->npreleased += t->npreleased;
		s->needzero |= t->needzero;
		h->spans[p + s->npages - 1] = s;
		runtime·MSpanList_Remove(t);
		t->state = MSpanDead;
		runtime·FixAlloc_Free(&h->spanalloc, t);
	}

	// Insert s into appropriate list.
	if(s->npages < nelem(h->free))
		runtime·MSpanList_Insert(&h->free[s->npages], s);
	else ///大对象MSpan,放到large list
		runtime·MSpanList_Insert(&h->freelarge, s);
}