runtime: add packed bitmap summaries

This change adds the concept of summaries and of summarizing a set of
pallocBits, a core concept in the new page allocator. These summaries
are really just three integers packed into a uint64. This change also
adds tests and a benchmark for generating these summaries.

Updates #35112.

Change-Id: I69686316086c820c792b7a54235859c2105e5fee
Reviewed-on: https://go-review.googlesource.com/c/go/+/190621
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
Reviewed-by: Cherry Zhang <cherryyz@google.com>

1 files changed, 74 insertions, 0 deletions

diff --git a/src/runtime/mpallocbits.go b/src/runtime/mpallocbits.go
index fe8cde9225..117a59bb3d 100644
--- a/src/runtime/mpallocbits.go
+++ b/src/runtime/mpallocbits.go
@@ -95,6 +95,80 @@ func (b *pageBits) clearAll() {
 // sake of documentation, 0s are free pages and 1s are allocated pages.
 type pallocBits pageBits
 
+// consec8tab is a table containing the number of consecutive
+// zero bits for any uint8 value.
+//
+// The table is generated by calling consec8(i) for each
+// possible uint8 value, which is defined as:
+//
+// // consec8 counts the maximum number of consecutive 0 bits
+// // in a uint8.
+// func consec8(n uint8) int {
+// 	n = ^n
+// 	i := 0
+// 	for n != 0 {
+// 		n &= (n << 1)
+// 		i++
+// 	}
+// 	return i
+// }
+var consec8tab = [256]uint{
+	8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
+	4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+	5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2,
+	4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2,
+	6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
+	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1,
+	5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1,
+	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1,
+	7, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3,
+	4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2,
+	5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1,
+	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1,
+	6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
+	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1,
+	5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1,
+	4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0,
+}
+
+// summarize returns a packed summary of the bitmap in mallocBits.
+func (b *pallocBits) summarize() pallocSum {
+	// TODO(mknyszek): There may be something more clever to be done
+	// here to make the summarize operation more efficient. For example,
+	// we can compute start and end with 64-bit wide operations easily,
+	// but max is a bit more complex. Perhaps there exists some way to
+	// leverage the 64-bit start and end to our advantage?
+	var start, max, end uint
+	for i := 0; i < len(b); i++ {
+		a := b[i]
+		for j := 0; j < 64; j += 8 {
+			k := uint8(a >> j)
+
+			// Compute start.
+			si := uint(bits.TrailingZeros8(k))
+			if start == uint(i*64+j) {
+				start += si
+			}
+
+			// Compute max.
+			if end+si > max {
+				max = end + si
+			}
+			if mi := consec8tab[k]; mi > max {
+				max = mi
+			}
+
+			// Compute end.
+			if k == 0 {
+				end += 8
+			} else {
+				end = uint(bits.LeadingZeros8(k))
+			}
+		}
+	}
+	return packPallocSum(start, max, end)
+}
+
 // find searches for npages contiguous free pages in pallocBits and returns
 // the index where that run starts, as well as the index of the first free page
 // it found in the search. searchIdx represents the first known free page and