Source file src/runtime/map_fast64.go

Documentation: runtime

     1  // Copyright 2018 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  package runtime
     6  
     7  import (
     8  	"runtime/internal/sys"
     9  	"unsafe"
    10  )
    11  
    12  func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
    13  	if raceenabled && h != nil {
    14  		callerpc := getcallerpc()
    15  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast64))
    16  	}
    17  	if h == nil || h.count == 0 {
    18  		return unsafe.Pointer(&zeroVal[0])
    19  	}
    20  	if h.flags&hashWriting != 0 {
    21  		throw("concurrent map read and map write")
    22  	}
    23  	var b *bmap
    24  	if h.B == 0 {
    25  		// One-bucket table. No need to hash.
    26  		b = (*bmap)(h.buckets)
    27  	} else {
    28  		hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
    29  		m := bucketMask(h.B)
    30  		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    31  		if c := h.oldbuckets; c != nil {
    32  			if !h.sameSizeGrow() {
    33  				// There used to be half as many buckets; mask down one more power of two.
    34  				m >>= 1
    35  			}
    36  			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    37  			if !evacuated(oldb) {
    38  				b = oldb
    39  			}
    40  		}
    41  	}
    42  	for ; b != nil; b = b.overflow(t) {
    43  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
    44  			if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) {
    45  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize))
    46  			}
    47  		}
    48  	}
    49  	return unsafe.Pointer(&zeroVal[0])
    50  }
    51  
    52  func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) {
    53  	if raceenabled && h != nil {
    54  		callerpc := getcallerpc()
    55  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast64))
    56  	}
    57  	if h == nil || h.count == 0 {
    58  		return unsafe.Pointer(&zeroVal[0]), false
    59  	}
    60  	if h.flags&hashWriting != 0 {
    61  		throw("concurrent map read and map write")
    62  	}
    63  	var b *bmap
    64  	if h.B == 0 {
    65  		// One-bucket table. No need to hash.
    66  		b = (*bmap)(h.buckets)
    67  	} else {
    68  		hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
    69  		m := bucketMask(h.B)
    70  		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    71  		if c := h.oldbuckets; c != nil {
    72  			if !h.sameSizeGrow() {
    73  				// There used to be half as many buckets; mask down one more power of two.
    74  				m >>= 1
    75  			}
    76  			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    77  			if !evacuated(oldb) {
    78  				b = oldb
    79  			}
    80  		}
    81  	}
    82  	for ; b != nil; b = b.overflow(t) {
    83  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
    84  			if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) {
    85  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)), true
    86  			}
    87  		}
    88  	}
    89  	return unsafe.Pointer(&zeroVal[0]), false
    90  }
    91  
    92  func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
    93  	if h == nil {
    94  		panic(plainError("assignment to entry in nil map"))
    95  	}
    96  	if raceenabled {
    97  		callerpc := getcallerpc()
    98  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast64))
    99  	}
   100  	if h.flags&hashWriting != 0 {
   101  		throw("concurrent map writes")
   102  	}
   103  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   104  
   105  	// Set hashWriting after calling alg.hash for consistency with mapassign.
   106  	h.flags ^= hashWriting
   107  
   108  	if h.buckets == nil {
   109  		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   110  	}
   111  
   112  again:
   113  	bucket := hash & bucketMask(h.B)
   114  	if h.growing() {
   115  		growWork_fast64(t, h, bucket)
   116  	}
   117  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   118  
   119  	var insertb *bmap
   120  	var inserti uintptr
   121  	var insertk unsafe.Pointer
   122  
   123  bucketloop:
   124  	for {
   125  		for i := uintptr(0); i < bucketCnt; i++ {
   126  			if isEmpty(b.tophash[i]) {
   127  				if insertb == nil {
   128  					insertb = b
   129  					inserti = i
   130  				}
   131  				if b.tophash[i] == emptyRest {
   132  					break bucketloop
   133  				}
   134  				continue
   135  			}
   136  			k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8)))
   137  			if k != key {
   138  				continue
   139  			}
   140  			insertb = b
   141  			inserti = i
   142  			goto done
   143  		}
   144  		ovf := b.overflow(t)
   145  		if ovf == nil {
   146  			break
   147  		}
   148  		b = ovf
   149  	}
   150  
   151  	// Did not find mapping for key. Allocate new cell & add entry.
   152  
   153  	// If we hit the max load factor or we have too many overflow buckets,
   154  	// and we're not already in the middle of growing, start growing.
   155  	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
   156  		hashGrow(t, h)
   157  		goto again // Growing the table invalidates everything, so try again
   158  	}
   159  
   160  	if insertb == nil {
   161  		// all current buckets are full, allocate a new one.
   162  		insertb = h.newoverflow(t, b)
   163  		inserti = 0 // not necessary, but avoids needlessly spilling inserti
   164  	}
   165  	insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
   166  
   167  	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8)
   168  	// store new key at insert position
   169  	*(*uint64)(insertk) = key
   170  
   171  	h.count++
   172  
   173  done:
   174  	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize))
   175  	if h.flags&hashWriting == 0 {
   176  		throw("concurrent map writes")
   177  	}
   178  	h.flags &^= hashWriting
   179  	return val
   180  }
   181  
   182  func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   183  	if h == nil {
   184  		panic(plainError("assignment to entry in nil map"))
   185  	}
   186  	if raceenabled {
   187  		callerpc := getcallerpc()
   188  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_fast64))
   189  	}
   190  	if h.flags&hashWriting != 0 {
   191  		throw("concurrent map writes")
   192  	}
   193  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   194  
   195  	// Set hashWriting after calling alg.hash for consistency with mapassign.
   196  	h.flags ^= hashWriting
   197  
   198  	if h.buckets == nil {
   199  		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   200  	}
   201  
   202  again:
   203  	bucket := hash & bucketMask(h.B)
   204  	if h.growing() {
   205  		growWork_fast64(t, h, bucket)
   206  	}
   207  	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   208  
   209  	var insertb *bmap
   210  	var inserti uintptr
   211  	var insertk unsafe.Pointer
   212  
   213  bucketloop:
   214  	for {
   215  		for i := uintptr(0); i < bucketCnt; i++ {
   216  			if isEmpty(b.tophash[i]) {
   217  				if insertb == nil {
   218  					insertb = b
   219  					inserti = i
   220  				}
   221  				if b.tophash[i] == emptyRest {
   222  					break bucketloop
   223  				}
   224  				continue
   225  			}
   226  			k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*8)))
   227  			if k != key {
   228  				continue
   229  			}
   230  			insertb = b
   231  			inserti = i
   232  			goto done
   233  		}
   234  		ovf := b.overflow(t)
   235  		if ovf == nil {
   236  			break
   237  		}
   238  		b = ovf
   239  	}
   240  
   241  	// Did not find mapping for key. Allocate new cell & add entry.
   242  
   243  	// If we hit the max load factor or we have too many overflow buckets,
   244  	// and we're not already in the middle of growing, start growing.
   245  	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
   246  		hashGrow(t, h)
   247  		goto again // Growing the table invalidates everything, so try again
   248  	}
   249  
   250  	if insertb == nil {
   251  		// all current buckets are full, allocate a new one.
   252  		insertb = h.newoverflow(t, b)
   253  		inserti = 0 // not necessary, but avoids needlessly spilling inserti
   254  	}
   255  	insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
   256  
   257  	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8)
   258  	// store new key at insert position
   259  	*(*unsafe.Pointer)(insertk) = key
   260  
   261  	h.count++
   262  
   263  done:
   264  	val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize))
   265  	if h.flags&hashWriting == 0 {
   266  		throw("concurrent map writes")
   267  	}
   268  	h.flags &^= hashWriting
   269  	return val
   270  }
   271  
   272  func mapdelete_fast64(t *maptype, h *hmap, key uint64) {
   273  	if raceenabled && h != nil {
   274  		callerpc := getcallerpc()
   275  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast64))
   276  	}
   277  	if h == nil || h.count == 0 {
   278  		return
   279  	}
   280  	if h.flags&hashWriting != 0 {
   281  		throw("concurrent map writes")
   282  	}
   283  
   284  	hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   285  
   286  	// Set hashWriting after calling alg.hash for consistency with mapdelete
   287  	h.flags ^= hashWriting
   288  
   289  	bucket := hash & bucketMask(h.B)
   290  	if h.growing() {
   291  		growWork_fast64(t, h, bucket)
   292  	}
   293  	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   294  	bOrig := b
   295  search:
   296  	for ; b != nil; b = b.overflow(t) {
   297  		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
   298  			if key != *(*uint64)(k) || isEmpty(b.tophash[i]) {
   299  				continue
   300  			}
   301  			// Only clear key if there are pointers in it.
   302  			if t.key.kind&kindNoPointers == 0 {
   303  				memclrHasPointers(k, t.key.size)
   304  			}
   305  			v := add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize))
   306  			if t.elem.kind&kindNoPointers == 0 {
   307  				memclrHasPointers(v, t.elem.size)
   308  			} else {
   309  				memclrNoHeapPointers(v, t.elem.size)
   310  			}
   311  			b.tophash[i] = emptyOne
   312  			// If the bucket now ends in a bunch of emptyOne states,
   313  			// change those to emptyRest states.
   314  			if i == bucketCnt-1 {
   315  				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
   316  					goto notLast
   317  				}
   318  			} else {
   319  				if b.tophash[i+1] != emptyRest {
   320  					goto notLast
   321  				}
   322  			}
   323  			for {
   324  				b.tophash[i] = emptyRest
   325  				if i == 0 {
   326  					if b == bOrig {
   327  						break // beginning of initial bucket, we're done.
   328  					}
   329  					// Find previous bucket, continue at its last entry.
   330  					c := b
   331  					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
   332  					}
   333  					i = bucketCnt - 1
   334  				} else {
   335  					i--
   336  				}
   337  				if b.tophash[i] != emptyOne {
   338  					break
   339  				}
   340  			}
   341  		notLast:
   342  			h.count--
   343  			break search
   344  		}
   345  	}
   346  
   347  	if h.flags&hashWriting == 0 {
   348  		throw("concurrent map writes")
   349  	}
   350  	h.flags &^= hashWriting
   351  }
   352  
   353  func growWork_fast64(t *maptype, h *hmap, bucket uintptr) {
   354  	// make sure we evacuate the oldbucket corresponding
   355  	// to the bucket we're about to use
   356  	evacuate_fast64(t, h, bucket&h.oldbucketmask())
   357  
   358  	// evacuate one more oldbucket to make progress on growing
   359  	if h.growing() {
   360  		evacuate_fast64(t, h, h.nevacuate)
   361  	}
   362  }
   363  
   364  func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) {
   365  	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
   366  	newbit := h.noldbuckets()
   367  	if !evacuated(b) {
   368  		// TODO: reuse overflow buckets instead of using new ones, if there
   369  		// is no iterator using the old buckets.  (If !oldIterator.)
   370  
   371  		// xy contains the x and y (low and high) evacuation destinations.
   372  		var xy [2]evacDst
   373  		x := &xy[0]
   374  		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
   375  		x.k = add(unsafe.Pointer(x.b), dataOffset)
   376  		x.v = add(x.k, bucketCnt*8)
   377  
   378  		if !h.sameSizeGrow() {
   379  			// Only calculate y pointers if we're growing bigger.
   380  			// Otherwise GC can see bad pointers.
   381  			y := &xy[1]
   382  			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
   383  			y.k = add(unsafe.Pointer(y.b), dataOffset)
   384  			y.v = add(y.k, bucketCnt*8)
   385  		}
   386  
   387  		for ; b != nil; b = b.overflow(t) {
   388  			k := add(unsafe.Pointer(b), dataOffset)
   389  			v := add(k, bucketCnt*8)
   390  			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 8), add(v, uintptr(t.valuesize)) {
   391  				top := b.tophash[i]
   392  				if isEmpty(top) {
   393  					b.tophash[i] = evacuatedEmpty
   394  					continue
   395  				}
   396  				if top < minTopHash {
   397  					throw("bad map state")
   398  				}
   399  				var useY uint8
   400  				if !h.sameSizeGrow() {
   401  					// Compute hash to make our evacuation decision (whether we need
   402  					// to send this key/value to bucket x or bucket y).
   403  					hash := t.key.alg.hash(k, uintptr(h.hash0))
   404  					if hash&newbit != 0 {
   405  						useY = 1
   406  					}
   407  				}
   408  
   409  				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap
   410  				dst := &xy[useY]                 // evacuation destination
   411  
   412  				if dst.i == bucketCnt {
   413  					dst.b = h.newoverflow(t, dst.b)
   414  					dst.i = 0
   415  					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
   416  					dst.v = add(dst.k, bucketCnt*8)
   417  				}
   418  				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
   419  
   420  				// Copy key.
   421  				if t.key.kind&kindNoPointers == 0 && writeBarrier.enabled {
   422  					if sys.PtrSize == 8 {
   423  						// Write with a write barrier.
   424  						*(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k)
   425  					} else {
   426  						// There are three ways to squeeze at least one 32 bit pointer into 64 bits.
   427  						// Give up and call typedmemmove.
   428  						typedmemmove(t.key, dst.k, k)
   429  					}
   430  				} else {
   431  					*(*uint64)(dst.k) = *(*uint64)(k)
   432  				}
   433  
   434  				typedmemmove(t.elem, dst.v, v)
   435  				dst.i++
   436  				// These updates might push these pointers past the end of the
   437  				// key or value arrays.  That's ok, as we have the overflow pointer
   438  				// at the end of the bucket to protect against pointing past the
   439  				// end of the bucket.
   440  				dst.k = add(dst.k, 8)
   441  				dst.v = add(dst.v, uintptr(t.valuesize))
   442  			}
   443  		}
   444  		// Unlink the overflow buckets & clear key/value to help GC.
   445  		if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
   446  			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
   447  			// Preserve b.tophash because the evacuation
   448  			// state is maintained there.
   449  			ptr := add(b, dataOffset)
   450  			n := uintptr(t.bucketsize) - dataOffset
   451  			memclrHasPointers(ptr, n)
   452  		}
   453  	}
   454  
   455  	if oldbucket == h.nevacuate {
   456  		advanceEvacuationMark(h, t, newbit)
   457  	}
   458  }
   459  

View as plain text