1 //go:build gc.conservative || gc.precise
2 3 package runtime
4 5 // This memory manager is a textbook mark/sweep implementation, heavily inspired
6 // by the MicroPython garbage collector.
7 //
8 // The memory manager internally uses blocks of 4 pointers big (see
9 // bytesPerBlock). Every allocation first rounds up to this size to align every
10 // block. It will first try to find a chain of blocks that is big enough to
11 // satisfy the allocation. If it finds one, it marks the first one as the "head"
12 // and the following ones (if any) as the "tail" (see below). If it cannot find
13 // any free space, it will perform a garbage collection cycle and try again. If
14 // it still cannot find any free space, it gives up.
15 //
16 // Every block has some metadata, which is stored at the end of the heap.
17 // The four states are "free", "head", "tail", and "mark". During normal
18 // operation, there are no marked blocks. Every allocated object starts with a
19 // "head" and is followed by "tail" blocks. The reason for this distinction is
20 // that this way, the start and end of every object can be found easily.
21 //
22 // Metadata is stored in a special area at the end of the heap, in the area
23 // metadataStart..heapEnd. The actual blocks are stored in
24 // heapStart..metadataStart.
25 //
26 // More information:
27 // https://aykevl.nl/2020/09/gc-moxie
28 // https://github.com/micropython/micropython/wiki/Memory-Manager
29 // https://github.com/micropython/micropython/blob/master/py/gc.c
30 // "The Garbage Collection Handbook" by Richard Jones, Antony Hosking, Eliot
31 // Moss.
32 33 import (
34 "internal/task"
35 "runtime/interrupt"
36 "unsafe"
37 )
38 39 const gcDebug = false
40 const needsStaticHeap = true
41 42 // Some globals + constants for the entire GC.
43 44 const (
45 wordsPerBlock = 4 // number of pointers in an allocated block
46 bytesPerBlock = wordsPerBlock * unsafe.Sizeof(heapStart)
47 stateBits = 2 // how many bits a block state takes (see blockState type)
48 blocksPerStateByte = 8 / stateBits
49 )
50 51 var (
52 metadataStart unsafe.Pointer // pointer to the start of the heap metadata
53 scanList *objHeader // scanList is a singly linked list of heap objects that have been marked but not scanned
54 freeRanges *freeRange // freeRanges is a linked list of free block ranges
55 endBlock gcBlock // the block just past the end of the available space
56 gcTotalAlloc uint64 // total number of bytes allocated
57 gcMallocs uint64 // total number of allocations
58 gcLock task.PMutex // lock to avoid race conditions on multicore systems
59 )
60 61 // zeroSizedAlloc is just a sentinel that gets returned when allocating 0 bytes.
62 var zeroSizedAlloc uint8
63 64 // Provide some abstraction over heap blocks.
65 66 // blockState stores the four states in which a block can be.
67 // It holds 1 bit in each nibble.
68 // When stored into a state byte, each bit in a nibble corresponds to a different block.
69 // For blocks A-D, a state byte would be laid out as 0bDCBA_DCBA.
70 type blockState uint8
71 72 const (
73 blockStateLow blockState = 1
74 blockStateHigh blockState = 1 << blocksPerStateByte
75 76 blockStateFree blockState = 0
77 blockStateHead blockState = blockStateLow
78 blockStateTail blockState = blockStateHigh
79 blockStateMark blockState = blockStateLow | blockStateHigh
80 blockStateMask blockState = blockStateLow | blockStateHigh
81 )
82 83 // blockStateEach is a mask that can be used to extract a nibble from the block state.
84 const blockStateEach = 1<<blocksPerStateByte - 1
85 86 // The byte value of a block where every block is a 'tail' block.
87 const blockStateByteAllTails = byte(blockStateTail) * blockStateEach
88 89 // String returns a human-readable version of the block state, for debugging.
90 func (s blockState) String() string {
91 switch s {
92 case blockStateFree:
93 return "free"
94 case blockStateHead:
95 return "head"
96 case blockStateTail:
97 return "tail"
98 case blockStateMark:
99 return "mark"
100 default:
101 // must never happen
102 return "!err"
103 }
104 }
105 106 // The block number in the pool.
107 type gcBlock uintptr
108 109 // blockFromAddr returns a block given an address somewhere in the heap (which
110 // might not be heap-aligned).
111 func blockFromAddr(addr uintptr) gcBlock {
112 if gcAsserts && (addr < heapStart || addr >= uintptr(metadataStart)) {
113 runtimePanic("gc: trying to get block from invalid address")
114 }
115 return gcBlock((addr - heapStart) / bytesPerBlock)
116 }
117 118 // Return a pointer to the start of the allocated object.
119 func (b gcBlock) pointer() unsafe.Pointer {
120 return unsafe.Pointer(b.address())
121 }
122 123 // Return the address of the start of the allocated object.
124 func (b gcBlock) address() uintptr {
125 addr := heapStart + uintptr(b)*bytesPerBlock
126 if gcAsserts && addr > uintptr(metadataStart) {
127 runtimePanic("gc: block pointing inside metadata")
128 }
129 return addr
130 }
131 132 // findHead returns the head (first block) of an object, assuming the block
133 // points to an allocated object. It returns the same block if this block
134 // already points to the head.
135 func (b gcBlock) findHead() gcBlock {
136 for {
137 // Optimization: check whether the current block state byte (which
138 // contains the state of multiple blocks) is composed entirely of tail
139 // blocks. If so, we can skip back to the last block in the previous
140 // state byte.
141 // This optimization speeds up findHead for pointers that point into a
142 // large allocation.
143 stateByte := b.stateByte()
144 if stateByte == blockStateByteAllTails {
145 b -= (b % blocksPerStateByte) + 1
146 continue
147 }
148 149 // Check whether we've found a non-tail block, which means we found the
150 // head.
151 state := b.stateFromByte(stateByte)
152 if state != blockStateTail {
153 break
154 }
155 b--
156 }
157 if gcAsserts {
158 if b.state() != blockStateHead && b.state() != blockStateMark {
159 runtimePanic("gc: found tail without head")
160 }
161 }
162 return b
163 }
164 165 // findNext returns the first block just past the end of the tail. This may or
166 // may not be the head of an object.
167 func (b gcBlock) findNext() gcBlock {
168 if b.state() == blockStateHead || b.state() == blockStateMark {
169 b++
170 }
171 for b.address() < uintptr(metadataStart) && b.state() == blockStateTail {
172 b++
173 }
174 return b
175 }
176 177 func (b gcBlock) stateByte() byte {
178 return *(*uint8)(unsafe.Add(metadataStart, b/blocksPerStateByte))
179 }
180 181 // Return the block state given a state byte. The state byte must have been
182 // obtained using b.stateByte(), otherwise the result is incorrect.
183 func (b gcBlock) stateFromByte(stateByte byte) blockState {
184 return blockState(stateByte>>(b%blocksPerStateByte)) & blockStateMask
185 }
186 187 // State returns the current block state.
188 func (b gcBlock) state() blockState {
189 return b.stateFromByte(b.stateByte())
190 }
191 192 // setState sets the current block to the given state, which must contain more
193 // bits than the current state. Allowed transitions: from free to any state and
194 // from head to mark.
195 func (b gcBlock) setState(newState blockState) {
196 stateBytePtr := (*uint8)(unsafe.Add(metadataStart, b/blocksPerStateByte))
197 *stateBytePtr |= uint8(newState << (b % blocksPerStateByte))
198 if gcAsserts && b.state() != newState {
199 runtimePanic("gc: setState() was not successful")
200 }
201 }
202 203 // objHeader is a structure prepended to every heap object to hold metadata.
204 type objHeader struct {
205 // next is the next object to scan after this.
206 next *objHeader
207 208 // layout holds the layout bitmap used to find pointers in the object.
209 layout gcLayout
210 }
211 212 // freeRange is a node on the outer list of range lengths.
213 // The free ranges are structured as two nested singly-linked lists:
214 // - The outer level (freeRange) has one entry for each unique range length.
215 // - The inner level (freeRangeMore) has one entry for each additional range of the same length.
216 // This two-level structure ensures that insertion/removal times are proportional to the requested length.
217 type freeRange struct {
218 // len is the length of this free range.
219 len uintptr
220 221 // nextLen is the next longer free range.
222 nextLen *freeRange
223 224 // nextWithLen is the next free range with this length.
225 nextWithLen *freeRangeMore
226 }
227 228 // freeRangeMore is a node on the inner list of equal-length ranges.
229 type freeRangeMore struct {
230 next *freeRangeMore
231 }
232 233 // insertFreeRange inserts a range of len blocks starting at ptr into the free list.
234 func insertFreeRange(ptr unsafe.Pointer, len uintptr) {
235 if gcAsserts && len == 0 {
236 runtimePanic("gc: insert 0-length free range")
237 }
238 239 // Find the insertion point by length.
240 // Skip until the next range is at least the target length.
241 insDst := &freeRanges
242 for *insDst != nil && (*insDst).len < len {
243 insDst = &(*insDst).nextLen
244 }
245 246 // Create the new free range.
247 next := *insDst
248 if next != nil && next.len == len {
249 // Insert into the list with this length.
250 newRange := (*freeRangeMore)(ptr)
251 newRange.next = next.nextWithLen
252 next.nextWithLen = newRange
253 } else {
254 // Insert into the list of lengths.
255 newRange := (*freeRange)(ptr)
256 *newRange = freeRange{
257 len: len,
258 nextLen: next,
259 nextWithLen: nil,
260 }
261 *insDst = newRange
262 }
263 }
264 265 // popFreeRange removes a range of len blocks from the freeRanges list.
266 // It returns nil if there are no sufficiently long ranges.
267 func popFreeRange(len uintptr) unsafe.Pointer {
268 if gcAsserts && len == 0 {
269 runtimePanic("gc: pop 0-length free range")
270 }
271 272 // Find the removal point by length.
273 // Skip until the next range is at least the target length.
274 remDst := &freeRanges
275 for *remDst != nil && (*remDst).len < len {
276 remDst = &(*remDst).nextLen
277 }
278 279 rangeWithLength := *remDst
280 if rangeWithLength == nil {
281 // No ranges are long enough.
282 return nil
283 }
284 removedLen := rangeWithLength.len
285 286 // Remove the range.
287 var ptr unsafe.Pointer
288 if nextWithLen := rangeWithLength.nextWithLen; nextWithLen != nil {
289 // Remove from the list with this length.
290 rangeWithLength.nextWithLen = nextWithLen.next
291 ptr = unsafe.Pointer(nextWithLen)
292 } else {
293 // Remove from the list of lengths.
294 *remDst = rangeWithLength.nextLen
295 ptr = unsafe.Pointer(rangeWithLength)
296 }
297 298 if removedLen > len {
299 // Insert the leftover range.
300 insertFreeRange(unsafe.Add(ptr, len*bytesPerBlock), removedLen-len)
301 }
302 return ptr
303 }
304 305 func isOnHeap(ptr uintptr) bool {
306 return ptr >= heapStart && ptr < uintptr(metadataStart)
307 }
308 309 // Initialize the memory allocator.
310 // No memory may be allocated before this is called. That means the runtime and
311 // any packages the runtime depends upon may not allocate memory during package
312 // initialization.
313 func initHeap() {
314 calculateHeapAddresses()
315 316 // Set all block states to 'free'.
317 metadataSize := heapEnd - uintptr(metadataStart)
318 memzero(unsafe.Pointer(metadataStart), metadataSize)
319 320 // Rebuild the free ranges list.
321 buildFreeRanges()
322 }
323 324 // setHeapEnd is called to expand the heap. The heap can only grow, not shrink.
325 // Also, the heap should grow substantially each time otherwise growing the heap
326 // will be expensive.
327 func setHeapEnd(newHeapEnd uintptr) {
328 if gcAsserts && newHeapEnd <= heapEnd {
329 runtimePanic("gc: setHeapEnd didn't grow the heap")
330 }
331 332 // Save some old variables we need later.
333 oldMetadataStart := metadataStart
334 oldMetadataSize := heapEnd - uintptr(metadataStart)
335 336 // Increase the heap. After setting the new heapEnd, calculateHeapAddresses
337 // will update metadataStart and the memcpy will copy the metadata to the
338 // new location.
339 // The new metadata will be bigger than the old metadata, but a simple
340 // memcpy is fine as it only copies the old metadata and the new memory will
341 // have been zero initialized.
342 heapEnd = newHeapEnd
343 calculateHeapAddresses()
344 memcpy(metadataStart, oldMetadataStart, oldMetadataSize)
345 346 // Note: the memcpy above assumes the heap grows enough so that the new
347 // metadata does not overlap the old metadata. If that isn't true, memmove
348 // should be used to avoid corruption.
349 // This assert checks whether that's true.
350 if gcAsserts && uintptr(metadataStart) < uintptr(oldMetadataStart)+oldMetadataSize {
351 runtimePanic("gc: heap did not grow enough at once")
352 }
353 354 // Rebuild the free ranges list.
355 buildFreeRanges()
356 }
357 358 // calculateHeapAddresses initializes variables such as metadataStart and
359 // numBlock based on heapStart and heapEnd.
360 //
361 // This function can be called again when the heap size increases. The caller is
362 // responsible for copying the metadata to the new location.
363 func calculateHeapAddresses() {
364 totalSize := heapEnd - heapStart
365 366 // Allocate some memory to keep 2 bits of information about every block.
367 metadataSize := (totalSize + blocksPerStateByte*bytesPerBlock) / (1 + blocksPerStateByte*bytesPerBlock)
368 metadataStart = unsafe.Pointer(heapEnd - metadataSize)
369 370 // Use the rest of the available memory as heap.
371 numBlocks := (uintptr(metadataStart) - heapStart) / bytesPerBlock
372 endBlock = gcBlock(numBlocks)
373 if gcDebug {
374 println("heapStart: ", heapStart)
375 println("heapEnd: ", heapEnd)
376 println("total size: ", totalSize)
377 println("metadata size: ", metadataSize)
378 println("metadataStart: ", metadataStart)
379 println("# of blocks: ", numBlocks)
380 println("# of block states:", metadataSize*blocksPerStateByte)
381 }
382 if gcAsserts && metadataSize*blocksPerStateByte < numBlocks {
383 // sanity check
384 runtimePanic("gc: metadata array is too small")
385 }
386 }
387 388 // alloc tries to find some free space on the heap, possibly doing a garbage
389 // collection cycle if needed. If no space is free, it panics.
390 //
391 //go:noinline
392 func alloc(size uintptr, layout unsafe.Pointer) unsafe.Pointer {
393 if size == 0 {
394 return unsafe.Pointer(&zeroSizedAlloc)
395 }
396 397 if interrupt.In() {
398 runtimePanicAt(returnAddress(0), "heap alloc in interrupt")
399 }
400 401 // Round the size up to a multiple of blocks, adding space for the header.
402 rawSize := size
403 size += align(unsafe.Sizeof(objHeader{}))
404 size += bytesPerBlock - 1
405 if size < rawSize {
406 // The size overflowed.
407 runtimePanicAt(returnAddress(0), "out of memory")
408 }
409 neededBlocks := size / bytesPerBlock
410 size = neededBlocks * bytesPerBlock
411 412 // Make sure there are no concurrent allocations. The heap is not currently
413 // designed for concurrent alloc/GC.
414 gcLock.Lock()
415 416 // Update the total allocation counters.
417 gcTotalAlloc += uint64(rawSize)
418 gcMallocs++
419 420 // Acquire a range of free blocks.
421 var ranGC bool
422 var grewHeap bool
423 var pointer unsafe.Pointer
424 for {
425 pointer = popFreeRange(neededBlocks)
426 if pointer != nil {
427 break
428 }
429 430 if !ranGC {
431 // Run the collector and try again.
432 freeBytes := runGC()
433 ranGC = true
434 heapSize := uintptr(metadataStart) - heapStart
435 if freeBytes < heapSize/3 {
436 // Ensure there is at least 33% headroom.
437 // This percentage was arbitrarily chosen, and may need to
438 // be tuned in the future.
439 growHeap()
440 }
441 continue
442 }
443 444 if gcDebug && !grewHeap {
445 println("grow heap for request:", uint(neededBlocks))
446 dumpFreeRangeCounts()
447 }
448 if growHeap() {
449 grewHeap = true
450 continue
451 }
452 453 // Unfortunately the heap could not be increased. This
454 // happens on baremetal systems for example (where all
455 // available RAM has already been dedicated to the heap).
456 runtimePanicAt(returnAddress(0), "out of memory")
457 }
458 459 // Set the backing blocks as being allocated.
460 block := blockFromAddr(uintptr(pointer))
461 block.setState(blockStateHead)
462 for i := block + 1; i != block+gcBlock(neededBlocks); i++ {
463 i.setState(blockStateTail)
464 }
465 466 // Create the object header.
467 header := (*objHeader)(pointer)
468 header.layout = parseGCLayout(layout)
469 470 // We've claimed this allocation, now we can unlock the heap.
471 gcLock.Unlock()
472 473 // Return a pointer to this allocation.
474 add := align(unsafe.Sizeof(objHeader{}))
475 pointer = unsafe.Add(pointer, add)
476 size -= add
477 memzero(pointer, size)
478 return pointer
479 }
480 481 func realloc(ptr unsafe.Pointer, size uintptr) unsafe.Pointer {
482 if ptr == nil {
483 return alloc(size, nil)
484 }
485 486 ptrAddress := uintptr(ptr)
487 endOfTailAddress := blockFromAddr(ptrAddress).findNext().address()
488 489 // this might be a few bytes longer than the original size of
490 // ptr, because we align to full blocks of size bytesPerBlock
491 oldSize := endOfTailAddress - ptrAddress
492 if size <= oldSize {
493 return ptr
494 }
495 496 newAlloc := alloc(size, nil)
497 memcpy(newAlloc, ptr, oldSize)
498 free(ptr)
499 500 return newAlloc
501 }
502 503 func free(ptr unsafe.Pointer) {
504 // TODO: free blocks on request, when the compiler knows they're unused.
505 }
506 507 // GC performs a garbage collection cycle.
508 func GC() {
509 gcLock.Lock()
510 runGC()
511 gcLock.Unlock()
512 }
513 514 // runGC performs a garbage collection cycle. It is the internal implementation
515 // of the runtime.GC() function. The difference is that it returns the number of
516 // free bytes in the heap after the GC is finished.
517 func runGC() (freeBytes uintptr) {
518 if gcDebug {
519 println("running collection cycle...")
520 }
521 522 // Mark phase: mark all reachable objects, recursively.
523 gcMarkReachable()
524 525 if baremetal && hasScheduler {
526 // Channel operations in interrupts may move task pointers around while we are marking.
527 // Therefore we need to scan the runqueue separately.
528 var markedTaskQueue task.Queue
529 runqueueScan:
530 runqueue := schedulerRunQueue()
531 for !runqueue.Empty() {
532 // Pop the next task off of the runqueue.
533 t := runqueue.Pop()
534 535 // Mark the task if it has not already been marked.
536 markRoot(uintptr(unsafe.Pointer(runqueue)), uintptr(unsafe.Pointer(t)))
537 538 // Push the task onto our temporary queue.
539 markedTaskQueue.Push(t)
540 }
541 542 finishMark()
543 544 // Restore the runqueue.
545 i := interrupt.Disable()
546 if !runqueue.Empty() {
547 // Something new came in while finishing the mark.
548 interrupt.Restore(i)
549 goto runqueueScan
550 }
551 *runqueue = markedTaskQueue
552 interrupt.Restore(i)
553 } else {
554 finishMark()
555 }
556 557 // If we're using threads, resume all other threads before starting the
558 // sweep.
559 gcResumeWorld()
560 561 // Sweep phase: free all non-marked objects and unmark marked objects for
562 // the next collection cycle.
563 sweep()
564 565 // Rebuild the free ranges list.
566 freeBytes = buildFreeRanges()
567 568 // Show how much has been sweeped, for debugging.
569 if gcDebug {
570 dumpHeap()
571 }
572 573 return
574 }
575 576 // markRoots reads all pointers from start to end (exclusive) and if they look
577 // like a heap pointer and are unmarked, marks them and scans that object as
578 // well (recursively). The starting address must be valid and aligned.
579 func markRoots(start, end uintptr) {
580 if gcDebug {
581 println("mark from", start, "to", end, int(end-start))
582 }
583 if gcAsserts {
584 if start >= end {
585 runtimePanic("gc: unexpected range to mark")
586 }
587 if start%unsafe.Alignof(start) != 0 {
588 runtimePanic("gc: unaligned start pointer")
589 }
590 }
591 592 // Scan the range conservatively.
593 scanConservative(start, end-start)
594 }
595 596 // scanConservative scans all possible pointer locations in a range and marks referenced heap allocations.
597 // The starting address must be valid and pointer-aligned.
598 func scanConservative(addr, len uintptr) {
599 for len >= unsafe.Sizeof(addr) {
600 root := *(*uintptr)(unsafe.Pointer(addr))
601 markRoot(addr, root)
602 603 addr += unsafe.Alignof(addr)
604 len -= unsafe.Alignof(addr)
605 }
606 }
607 608 func markCurrentGoroutineStack(sp uintptr) {
609 // This could be optimized by only marking the stack area that's currently
610 // in use.
611 markRoot(0, sp)
612 }
613 614 // finishMark finishes the marking process by scanning all heap objects on scanList.
615 func finishMark() {
616 for {
617 // Remove an object from the scan list.
618 obj := scanList
619 if obj == nil {
620 return
621 }
622 scanList = obj.next
623 624 // Check if the object may contain pointers.
625 if obj.layout.pointerFree() {
626 // This object doesn't contain any pointers.
627 // This is a fast path for objects like make([]int, 4096).
628 // It skips the length calculation.
629 continue
630 }
631 632 // Compute the scan bounds.
633 objAddr := uintptr(unsafe.Pointer(obj))
634 start := objAddr + align(unsafe.Sizeof(objHeader{}))
635 end := blockFromAddr(objAddr).findNext().address()
636 637 // Scan the object.
638 obj.layout.scan(start, end-start)
639 }
640 }
641 642 // mark a GC root at the address addr.
643 func markRoot(addr, root uintptr) {
644 // Find the heap block corresponding to the root.
645 if !isOnHeap(root) {
646 // This is not a heap pointer.
647 return
648 }
649 block := blockFromAddr(root)
650 651 // Find the head of the corresponding object.
652 if block.state() == blockStateFree {
653 // The to-be-marked object doesn't actually exist.
654 // This could either be a dangling pointer (oops!) but most likely
655 // just a false positive.
656 return
657 }
658 head := block.findHead()
659 660 // Mark the object.
661 if head.state() == blockStateMark {
662 // This object is already marked.
663 return
664 }
665 if gcDebug {
666 println("found unmarked pointer", root, "at address", addr)
667 }
668 head.setState(blockStateMark)
669 670 // Add the object to the scan list.
671 header := (*objHeader)(head.pointer())
672 header.next = scanList
673 scanList = header
674 }
675 676 // Sweep goes through all memory and frees unmarked memory.
677 func sweep() {
678 metadataEnd := unsafe.Add(metadataStart, (endBlock+(blocksPerStateByte-1))/blocksPerStateByte)
679 var carry byte
680 for meta := metadataStart; meta != metadataEnd; meta = unsafe.Add(meta, 1) {
681 // Fetch the state byte.
682 stateBytePtr := (*byte)(unsafe.Pointer(meta))
683 stateByte := *stateBytePtr
684 685 // Separate blocks by type.
686 // Split the nibbles.
687 // Each nibble is a mask of blocks.
688 high := stateByte >> blocksPerStateByte
689 low := stateByte & blockStateEach
690 // Marked heads are in both nibbles.
691 markedHeads := low & high
692 // Unmarked heads are in the low nibble but not the high nibble.
693 unmarkedHeads := low &^ high
694 // Tails are in the high nibble but not the low nibble.
695 tails := high &^ low
696 697 // Clear all tail runs after unmarked (freed) heads.
698 //
699 // Adding 1 to the start of a bit run will clear the run and set the next bit:
700 // (2^k - 1) + 1 = 2^k
701 // e.g. 0b0011 + 1 = 0b0100
702 // Bitwise-and with the original mask to clear the newly set bit.
703 // e.g. (0b0011 + 1) & 0b0011 = 0b0100 & 0b0011 = 0b0000
704 // This will not clear bits after the run because the gap stops the carry:
705 // e.g. (0b1011 + 1) & 0b1011 = 0b1100 & 0b1011 = 0b1000
706 // This can clear multiple runs in a single addition:
707 // e.g. (0b1101 + 0b0101) & 0b1101 = 0b10010 & 0b1101 = 0b0000
708 //
709 // In order to find tail run starts after unmarked heads we could use tails & (unmarkedHeads << 1).
710 // It is possible omit the bitwise-and because the clear still works if the next block is not a tail.
711 // A head is not a tail, so corresponding missing tail bit will stop the carry from a previous tail run.
712 // As such it will set the next bit which will be cleared back away later.
713 // e.g. HHTH: (0b0010 + (0b1101 << 1)) & 0b0010 = 0b11100 & 0b0010 = 0b0000
714 //
715 // Treat the whole heap as a single pair of integer masks.
716 // This is accomplished for addition by carrying the overflow to the next state byte.
717 // The unmarkedHeads << 1 is equivalent to unmarkedHeads + unmarkedHeads, so it can be merged with the sum.
718 // This does not require any special work for the bitwise-and because it operates bitwise.
719 tailClear := tails + (unmarkedHeads << 1) + carry
720 carry = tailClear >> blocksPerStateByte
721 tails &= tailClear
722 723 // Construct the new state byte.
724 *stateBytePtr = markedHeads | (tails << blocksPerStateByte)
725 }
726 }
727 728 // buildFreeRanges rebuilds the freeRanges list.
729 // This must be called after a GC sweep or heap grow.
730 // It returns how many bytes are free in the heap.
731 func buildFreeRanges() uintptr {
732 freeRanges = nil
733 block := endBlock
734 var totalBlocks uintptr
735 for {
736 // Skip backwards over occupied blocks.
737 for block > 0 && (block-1).state() != blockStateFree {
738 block--
739 }
740 if block == 0 {
741 break
742 }
743 744 // Find the start of the free range.
745 end := block
746 for block > 0 && (block-1).state() == blockStateFree {
747 block--
748 }
749 750 // Insert the free range.
751 len := uintptr(end - block)
752 totalBlocks += len
753 insertFreeRange(block.pointer(), len)
754 }
755 756 if gcDebug {
757 println("free ranges after rebuild:")
758 dumpFreeRangeCounts()
759 }
760 761 return totalBlocks * bytesPerBlock
762 }
763 764 func dumpFreeRangeCounts() {
765 for rangeWithLength := freeRanges; rangeWithLength != nil; rangeWithLength = rangeWithLength.nextLen {
766 totalRanges := uintptr(1)
767 for nextWithLen := rangeWithLength.nextWithLen; nextWithLen != nil; nextWithLen = nextWithLen.next {
768 totalRanges++
769 }
770 println("-", uint(rangeWithLength.len), "x", uint(totalRanges))
771 }
772 }
773 774 // dumpHeap can be used for debugging purposes. It dumps the state of each heap
775 // block to standard output.
776 func dumpHeap() {
777 println("heap:")
778 for block := gcBlock(0); block < endBlock; block++ {
779 switch block.state() {
780 case blockStateHead:
781 print("*")
782 case blockStateTail:
783 print("-")
784 case blockStateMark:
785 print("#")
786 default: // free
787 print("ยท")
788 }
789 if block%64 == 63 || block+1 == endBlock {
790 println()
791 }
792 }
793 }
794 795 // ReadMemStats populates m with memory statistics.
796 //
797 // The returned memory statistics are up to date as of the
798 // call to ReadMemStats. This would not do GC implicitly for you.
799 func ReadMemStats(m *MemStats) {
800 gcLock.Lock()
801 802 // Calculate the raw size of the heap.
803 heapEnd := heapEnd
804 heapStart := heapStart
805 m.Sys = uint64(heapEnd - heapStart)
806 m.HeapSys = uint64(uintptr(metadataStart) - heapStart)
807 metadataStart := metadataStart
808 // TODO: should GCSys include objHeaders?
809 m.GCSys = uint64(heapEnd - uintptr(metadataStart))
810 m.HeapReleased = 0 // always 0, we don't currently release memory back to the OS.
811 812 // Count live heads and tails.
813 var liveHeads, liveTails uintptr
814 endBlock := endBlock
815 metadataEnd := unsafe.Add(metadataStart, (endBlock+(blocksPerStateByte-1))/blocksPerStateByte)
816 for meta := metadataStart; meta != metadataEnd; meta = unsafe.Add(meta, 1) {
817 // Since we are outside of a GC, nothing is marked.
818 // A bit in the low nibble implies a head.
819 // A bit in the high nibble implies a tail.
820 stateByte := *(*byte)(unsafe.Pointer(meta))
821 liveHeads += uintptr(count4LUT[stateByte&blockStateEach])
822 liveTails += uintptr(count4LUT[stateByte>>blocksPerStateByte])
823 }
824 825 // Add heads and tails to count live blocks.
826 liveBlocks := liveHeads + liveTails
827 liveBytes := uint64(liveBlocks * bytesPerBlock)
828 m.HeapInuse = liveBytes
829 m.HeapAlloc = liveBytes
830 m.Alloc = liveBytes
831 832 // Subtract live blocks from total blocks to count free blocks.
833 freeBlocks := uintptr(endBlock) - liveBlocks
834 m.HeapIdle = uint64(freeBlocks * bytesPerBlock)
835 836 // Record the number of allocated objects.
837 gcMallocs := gcMallocs
838 m.Mallocs = gcMallocs
839 840 // Subtract live objects from allocated objects to count freed objects.
841 m.Frees = gcMallocs - uint64(liveHeads)
842 843 // Record the total allocated bytes.
844 m.TotalAlloc = gcTotalAlloc
845 846 gcLock.Unlock()
847 }
848 849 // count4LUT is a lookup table used to count set bits in a 4-bit mask.
850 // TODO: replace with popcnt when available
851 var count4LUT = [16]uint8{
852 0b0000: 0,
853 0b0001: 1,
854 0b0010: 1,
855 0b0011: 2,
856 0b0100: 1,
857 0b0101: 2,
858 0b0110: 2,
859 0b0111: 3,
860 0b1000: 1,
861 0b1001: 2,
862 0b1010: 2,
863 0b1011: 3,
864 0b1100: 2,
865 0b1101: 3,
866 0b1110: 3,
867 0b1111: 4,
868 }
869 870 func SetFinalizer(obj interface{}, finalizer interface{}) {
871 // Unimplemented.
872 }
873