1// Copyright 2017 Keybase Inc. All rights reserved.
2// Use of this source code is governed by a BSD
3// license that can be found in the LICENSE file.
4
5package cache
6
7import (
8	"math"
9	"reflect"
10)
11
12/*
13
14Following struct/const definitions are from src/runtime/hashmap.go. We don't
15use them directly, but the estimation of map size is based on them.
16
17const (
18	// Maximum number of key/value pairs a bucket can hold.
19  	bucketCntBits = 3
20  	bucketCnt     = 1 << bucketCntBits
21
22	// Maximum average load of a bucket that triggers growth.
23	loadFactor = 6.5
24	...
25)
26
27// A header for a Go map.
28type hmap struct {
29	// Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and
30	// ../reflect/type.go. Don't change this structure without also changing that code!
31	count     int // # live cells == size of map.  Must be first (used by len() builtin)
32	flags     uint8
33	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
34	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
35	hash0     uint32 // hash seed
36
37	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
38	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
39	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
40
41	// If both key and value do not contain pointers and are inline, then we mark bucket
42	// type as containing no pointers. This avoids scanning such maps.
43	// However, bmap.overflow is a pointer. In order to keep overflow buckets
44	// alive, we store pointers to all overflow buckets in hmap.overflow.
45	// Overflow is used only if key and value do not contain pointers.
46	// overflow[0] contains overflow buckets for hmap.buckets.
47	// overflow[1] contains overflow buckets for hmap.oldbuckets.
48	// The first indirection allows us to reduce static size of hmap.
49	// The second indirection allows to store a pointer to the slice in hiter.
50	overflow *[2]*[]*bmap
51}
52
53// A bucket for a Go map.
54type bmap struct {
55	// tophash generally contains the top byte of the hash value
56	// for each key in this bucket. If tophash[0] < minTopHash,
57	// tophash[0] is a bucket evacuation state instead.
58	tophash [bucketCnt]uint8
59	// Followed by bucketCnt keys and then bucketCnt values.
60	// NOTE: packing all the keys together and then all the values together makes the
61	// code a bit more complicated than alternating key/value/key/value/... but it allows
62	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
63	// Followed by an overflow pointer.
64}
65*/
66
67const (
68	// MB is a short cut for 1024 * 1024.
69	MB = 1024 * 1024
70
71	// PtrSize is the number of bytes a pointer takes.
72	PtrSize = 4 << (^uintptr(0) >> 63) // stolen from runtime/internal/sys
73	// IntSize is the number of bytes an int or uint takes.
74	IntSize = 4 << (^uint(0) >> 63)
75
76	hmapStructSize = IntSize + // count int
77		1 + 1 + 2 + 4 + // flags, B, noverflow, hash0
78		PtrSize*3 + // buckets, oldbuckets, nevacuate
79		PtrSize + 2*PtrSize // overflow (estimate; not counting the slice)
80
81	bucketSizeWithoutIndirectPointerOverhead = 1 << 3 // tophash only
82
83	mapLoadFactor = 6.5
84)
85
86func mapKeyOrValueSizeWithIndirectPointerOverhead(rawSize int) int {
87	if rawSize > 128 {
88		// In Go maps, if key or value is larger than 128 bytes, a pointer type
89		// is used.
90		return rawSize + PtrSize
91	}
92	return rawSize
93}
94
95// StaticSizeOfMap provides a best-effort estimate of number of bytes that a
96// map takes in memory. It only includes statically sized content (i.e. struct,
97// array, int types, pointer address itself, slice/map's reference address
98// itself, etc.). If needed, dynamic sized stuff (slice/map content, pointer
99// content should be calculated separately by caller.
100func StaticSizeOfMap(
101	zeroValueKey, zeroValueValue interface{}, count int) (bytes int) {
102	return StaticSizeOfMapWithSize(int(reflect.TypeOf(zeroValueKey).Size()),
103		int(reflect.TypeOf(zeroValueValue).Size()), count)
104}
105
106// StaticSizeOfMapWithSize is a slightly more efficient version of
107// StaticSizeOfMap for when the caller knows the static size of key and value
108// without having to use `reflect`.
109func StaticSizeOfMapWithSize(
110	keyStaticSize, valueStaticSize int, count int) (bytes int) {
111	keySize := mapKeyOrValueSizeWithIndirectPointerOverhead(keyStaticSize)
112	valueSize := mapKeyOrValueSizeWithIndirectPointerOverhead(valueStaticSize)
113
114	// See the comment of `B` field of `hmap` struct above.
115	B := math.Ceil(math.Log2(float64(count) / mapLoadFactor))
116	numBuckets := int(math.Exp2(B))
117
118	return hmapStructSize +
119		bucketSizeWithoutIndirectPointerOverhead*numBuckets +
120		(keySize+valueSize)*count
121}
122