Source file src/runtime/mcentral.go

     1	// Copyright 2009 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// Central free lists.
     6	//
     7	// See malloc.go for an overview.
     8	//
     9	// The mcentral doesn't actually contain the list of free objects; the mspan does.
    10	// Each mcentral is two lists of mspans: those with free objects (c->nonempty)
    11	// and those that are completely allocated (c->empty).
    12	
    13	package runtime
    14	
    15	import "runtime/internal/atomic"
    16	
    17	// Central list of free objects of a given size.
    18	//
    19	//go:notinheap
    20	type mcentral struct {
    21		lock      mutex
    22		spanclass spanClass
    23		nonempty  mSpanList // list of spans with a free object, ie a nonempty free list
    24		empty     mSpanList // list of spans with no free objects (or cached in an mcache)
    25	
    26		// nmalloc is the cumulative count of objects allocated from
    27		// this mcentral, assuming all spans in mcaches are
    28		// fully-allocated. Written atomically, read under STW.
    29		nmalloc uint64
    30	}
    31	
    32	// Initialize a single central free list.
    33	func (c *mcentral) init(spc spanClass) {
    34		c.spanclass = spc
    35		c.nonempty.init()
    36		c.empty.init()
    37	}
    38	
    39	// Allocate a span to use in an mcache.
    40	func (c *mcentral) cacheSpan() *mspan {
    41		// Deduct credit for this span allocation and sweep if necessary.
    42		spanBytes := uintptr(class_to_allocnpages[c.spanclass.sizeclass()]) * _PageSize
    43		deductSweepCredit(spanBytes, 0)
    44	
    45		lock(&c.lock)
    46		traceDone := false
    47		if trace.enabled {
    48			traceGCSweepStart()
    49		}
    50		sg := mheap_.sweepgen
    51	retry:
    52		var s *mspan
    53		for s = c.nonempty.first; s != nil; s = s.next {
    54			if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
    55				c.nonempty.remove(s)
    56				c.empty.insertBack(s)
    57				unlock(&c.lock)
    58				s.sweep(true)
    59				goto havespan
    60			}
    61			if s.sweepgen == sg-1 {
    62				// the span is being swept by background sweeper, skip
    63				continue
    64			}
    65			// we have a nonempty span that does not require sweeping, allocate from it
    66			c.nonempty.remove(s)
    67			c.empty.insertBack(s)
    68			unlock(&c.lock)
    69			goto havespan
    70		}
    71	
    72		for s = c.empty.first; s != nil; s = s.next {
    73			if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
    74				// we have an empty span that requires sweeping,
    75				// sweep it and see if we can free some space in it
    76				c.empty.remove(s)
    77				// swept spans are at the end of the list
    78				c.empty.insertBack(s)
    79				unlock(&c.lock)
    80				s.sweep(true)
    81				freeIndex := s.nextFreeIndex()
    82				if freeIndex != s.nelems {
    83					s.freeindex = freeIndex
    84					goto havespan
    85				}
    86				lock(&c.lock)
    87				// the span is still empty after sweep
    88				// it is already in the empty list, so just retry
    89				goto retry
    90			}
    91			if s.sweepgen == sg-1 {
    92				// the span is being swept by background sweeper, skip
    93				continue
    94			}
    95			// already swept empty span,
    96			// all subsequent ones must also be either swept or in process of sweeping
    97			break
    98		}
    99		if trace.enabled {
   100			traceGCSweepDone()
   101			traceDone = true
   102		}
   103		unlock(&c.lock)
   104	
   105		// Replenish central list if empty.
   106		s = c.grow()
   107		if s == nil {
   108			return nil
   109		}
   110		lock(&c.lock)
   111		c.empty.insertBack(s)
   112		unlock(&c.lock)
   113	
   114		// At this point s is a non-empty span, queued at the end of the empty list,
   115		// c is unlocked.
   116	havespan:
   117		if trace.enabled && !traceDone {
   118			traceGCSweepDone()
   119		}
   120		n := int(s.nelems) - int(s.allocCount)
   121		if n == 0 || s.freeindex == s.nelems || uintptr(s.allocCount) == s.nelems {
   122			throw("span has no free objects")
   123		}
   124		// Assume all objects from this span will be allocated in the
   125		// mcache. If it gets uncached, we'll adjust this.
   126		atomic.Xadd64(&c.nmalloc, int64(n))
   127		usedBytes := uintptr(s.allocCount) * s.elemsize
   128		atomic.Xadd64(&memstats.heap_live, int64(spanBytes)-int64(usedBytes))
   129		if trace.enabled {
   130			// heap_live changed.
   131			traceHeapAlloc()
   132		}
   133		if gcBlackenEnabled != 0 {
   134			// heap_live changed.
   135			gcController.revise()
   136		}
   137		freeByteBase := s.freeindex &^ (64 - 1)
   138		whichByte := freeByteBase / 8
   139		// Init alloc bits cache.
   140		s.refillAllocCache(whichByte)
   141	
   142		// Adjust the allocCache so that s.freeindex corresponds to the low bit in
   143		// s.allocCache.
   144		s.allocCache >>= s.freeindex % 64
   145	
   146		return s
   147	}
   148	
   149	// Return span from an mcache.
   150	func (c *mcentral) uncacheSpan(s *mspan) {
   151		if s.allocCount == 0 {
   152			throw("uncaching span but s.allocCount == 0")
   153		}
   154	
   155		sg := mheap_.sweepgen
   156		stale := s.sweepgen == sg+1
   157		if stale {
   158			// Span was cached before sweep began. It's our
   159			// responsibility to sweep it.
   160			//
   161			// Set sweepgen to indicate it's not cached but needs
   162			// sweeping and can't be allocated from. sweep will
   163			// set s.sweepgen to indicate s is swept.
   164			atomic.Store(&s.sweepgen, sg-1)
   165		} else {
   166			// Indicate that s is no longer cached.
   167			atomic.Store(&s.sweepgen, sg)
   168		}
   169	
   170		n := int(s.nelems) - int(s.allocCount)
   171		if n > 0 {
   172			// cacheSpan updated alloc assuming all objects on s
   173			// were going to be allocated. Adjust for any that
   174			// weren't. We must do this before potentially
   175			// sweeping the span.
   176			atomic.Xadd64(&c.nmalloc, -int64(n))
   177	
   178			lock(&c.lock)
   179			c.empty.remove(s)
   180			c.nonempty.insert(s)
   181			if !stale {
   182				// mCentral_CacheSpan conservatively counted
   183				// unallocated slots in heap_live. Undo this.
   184				//
   185				// If this span was cached before sweep, then
   186				// heap_live was totally recomputed since
   187				// caching this span, so we don't do this for
   188				// stale spans.
   189				atomic.Xadd64(&memstats.heap_live, -int64(n)*int64(s.elemsize))
   190			}
   191			unlock(&c.lock)
   192		}
   193	
   194		if stale {
   195			// Now that s is in the right mcentral list, we can
   196			// sweep it.
   197			s.sweep(false)
   198		}
   199	}
   200	
   201	// freeSpan updates c and s after sweeping s.
   202	// It sets s's sweepgen to the latest generation,
   203	// and, based on the number of free objects in s,
   204	// moves s to the appropriate list of c or returns it
   205	// to the heap.
   206	// freeSpan reports whether s was returned to the heap.
   207	// If preserve=true, it does not move s (the caller
   208	// must take care of it).
   209	func (c *mcentral) freeSpan(s *mspan, preserve bool, wasempty bool) bool {
   210		if sg := mheap_.sweepgen; s.sweepgen == sg+1 || s.sweepgen == sg+3 {
   211			throw("freeSpan given cached span")
   212		}
   213		s.needzero = 1
   214	
   215		if preserve {
   216			// preserve is set only when called from (un)cacheSpan above,
   217			// the span must be in the empty list.
   218			if !s.inList() {
   219				throw("can't preserve unlinked span")
   220			}
   221			atomic.Store(&s.sweepgen, mheap_.sweepgen)
   222			return false
   223		}
   224	
   225		lock(&c.lock)
   226	
   227		// Move to nonempty if necessary.
   228		if wasempty {
   229			c.empty.remove(s)
   230			c.nonempty.insert(s)
   231		}
   232	
   233		// delay updating sweepgen until here. This is the signal that
   234		// the span may be used in an mcache, so it must come after the
   235		// linked list operations above (actually, just after the
   236		// lock of c above.)
   237		atomic.Store(&s.sweepgen, mheap_.sweepgen)
   238	
   239		if s.allocCount != 0 {
   240			unlock(&c.lock)
   241			return false
   242		}
   243	
   244		c.nonempty.remove(s)
   245		unlock(&c.lock)
   246		mheap_.freeSpan(s, false)
   247		return true
   248	}
   249	
   250	// grow allocates a new empty span from the heap and initializes it for c's size class.
   251	func (c *mcentral) grow() *mspan {
   252		npages := uintptr(class_to_allocnpages[c.spanclass.sizeclass()])
   253		size := uintptr(class_to_size[c.spanclass.sizeclass()])
   254	
   255		s := mheap_.alloc(npages, c.spanclass, false, true)
   256		if s == nil {
   257			return nil
   258		}
   259	
   260		// Use division by multiplication and shifts to quickly compute:
   261		// n := (npages << _PageShift) / size
   262		n := (npages << _PageShift) >> s.divShift * uintptr(s.divMul) >> s.divShift2
   263		s.limit = s.base() + size*n
   264		heapBitsForAddr(s.base()).initSpan(s)
   265		return s
   266	}
   267	

View as plain text