Black Lives Matter. Support the Equal Justice Initiative.

Source file src/runtime/map_fast32.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_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer {
    13  	if raceenabled && h != nil {
    14  		callerpc := getcallerpc()
    15  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast32))
    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.hasher(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, 4) {
    44  			if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) {
    45  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.elemsize))
    46  			}
    47  		}
    48  	}
    49  	return unsafe.Pointer(&zeroVal[0])
    50  }
    51  
    52  func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) {
    53  	if raceenabled && h != nil {
    54  		callerpc := getcallerpc()
    55  		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_fast32))
    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.hasher(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, 4) {
    84  			if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) {
    85  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.elemsize)), true
    86  			}
    87  		}
    88  	}
    89  	return unsafe.Pointer(&zeroVal[0]), false
    90  }
    91  
    92  func mapassign_fast32(t *maptype, h *hmap, key uint32) 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_fast32))
    99  	}
   100  	if h.flags&hashWriting != 0 {
   101  		throw("concurrent map writes")
   102  	}
   103  	hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   104  
   105  	// Set hashWriting after calling t.hasher 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_fast32(t, h, bucket)
   116  	}
   117  	b := (*bmap)(add(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  					inserti = i
   129  					insertb = b
   130  				}
   131  				if b.tophash[i] == emptyRest {
   132  					break bucketloop
   133  				}
   134  				continue
   135  			}
   136  			k := *((*uint32)(add(unsafe.Pointer(b), dataOffset+i*4)))
   137  			if k != key {
   138  				continue
   139  			}
   140  			inserti = i
   141  			insertb = b
   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  		// The current bucket and all the overflow buckets connected to it 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*4)
   168  	// store new key at insert position
   169  	*(*uint32)(insertk) = key
   170  
   171  	h.count++
   172  
   173  done:
   174  	elem := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.elemsize))
   175  	if h.flags&hashWriting == 0 {
   176  		throw("concurrent map writes")
   177  	}
   178  	h.flags &^= hashWriting
   179  	return elem
   180  }
   181  
   182  func mapassign_fast32ptr(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_fast32))
   189  	}
   190  	if h.flags&hashWriting != 0 {
   191  		throw("concurrent map writes")
   192  	}
   193  	hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   194  
   195  	// Set hashWriting after calling t.hasher 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_fast32(t, h, bucket)
   206  	}
   207  	b := (*bmap)(add(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  					inserti = i
   219  					insertb = b
   220  				}
   221  				if b.tophash[i] == emptyRest {
   222  					break bucketloop
   223  				}
   224  				continue
   225  			}
   226  			k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*4)))
   227  			if k != key {
   228  				continue
   229  			}
   230  			inserti = i
   231  			insertb = b
   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  		// The current bucket and all the overflow buckets connected to it 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*4)
   258  	// store new key at insert position
   259  	*(*unsafe.Pointer)(insertk) = key
   260  
   261  	h.count++
   262  
   263  done:
   264  	elem := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*4+inserti*uintptr(t.elemsize))
   265  	if h.flags&hashWriting == 0 {
   266  		throw("concurrent map writes")
   267  	}
   268  	h.flags &^= hashWriting
   269  	return elem
   270  }
   271  
   272  func mapdelete_fast32(t *maptype, h *hmap, key uint32) {
   273  	if raceenabled && h != nil {
   274  		callerpc := getcallerpc()
   275  		racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_fast32))
   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.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
   285  
   286  	// Set hashWriting after calling t.hasher for consistency with mapdelete
   287  	h.flags ^= hashWriting
   288  
   289  	bucket := hash & bucketMask(h.B)
   290  	if h.growing() {
   291  		growWork_fast32(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, 4) {
   298  			if key != *(*uint32)(k) || isEmpty(b.tophash[i]) {
   299  				continue
   300  			}
   301  			// Only clear key if there are pointers in it.
   302  			// This can only happen if pointers are 32 bit
   303  			// wide as 64 bit pointers do not fit into a 32 bit key.
   304  			if sys.PtrSize == 4 && t.key.ptrdata != 0 {
   305  				// The key must be a pointer as we checked pointers are
   306  				// 32 bits wide and the key is 32 bits wide also.
   307  				*(*unsafe.Pointer)(k) = nil
   308  			}
   309  			e := add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.elemsize))
   310  			if t.elem.ptrdata != 0 {
   311  				memclrHasPointers(e, t.elem.size)
   312  			} else {
   313  				memclrNoHeapPointers(e, t.elem.size)
   314  			}
   315  			b.tophash[i] = emptyOne
   316  			// If the bucket now ends in a bunch of emptyOne states,
   317  			// change those to emptyRest states.
   318  			if i == bucketCnt-1 {
   319  				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
   320  					goto notLast
   321  				}
   322  			} else {
   323  				if b.tophash[i+1] != emptyRest {
   324  					goto notLast
   325  				}
   326  			}
   327  			for {
   328  				b.tophash[i] = emptyRest
   329  				if i == 0 {
   330  					if b == bOrig {
   331  						break // beginning of initial bucket, we're done.
   332  					}
   333  					// Find previous bucket, continue at its last entry.
   334  					c := b
   335  					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
   336  					}
   337  					i = bucketCnt - 1
   338  				} else {
   339  					i--
   340  				}
   341  				if b.tophash[i] != emptyOne {
   342  					break
   343  				}
   344  			}
   345  		notLast:
   346  			h.count--
   347  			// Reset the hash seed to make it more difficult for attackers to
   348  			// repeatedly trigger hash collisions. See issue 25237.
   349  			if h.count == 0 {
   350  				h.hash0 = fastrand()
   351  			}
   352  			break search
   353  		}
   354  	}
   355  
   356  	if h.flags&hashWriting == 0 {
   357  		throw("concurrent map writes")
   358  	}
   359  	h.flags &^= hashWriting
   360  }
   361  
   362  func growWork_fast32(t *maptype, h *hmap, bucket uintptr) {
   363  	// make sure we evacuate the oldbucket corresponding
   364  	// to the bucket we're about to use
   365  	evacuate_fast32(t, h, bucket&h.oldbucketmask())
   366  
   367  	// evacuate one more oldbucket to make progress on growing
   368  	if h.growing() {
   369  		evacuate_fast32(t, h, h.nevacuate)
   370  	}
   371  }
   372  
   373  func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) {
   374  	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
   375  	newbit := h.noldbuckets()
   376  	if !evacuated(b) {
   377  		// TODO: reuse overflow buckets instead of using new ones, if there
   378  		// is no iterator using the old buckets.  (If !oldIterator.)
   379  
   380  		// xy contains the x and y (low and high) evacuation destinations.
   381  		var xy [2]evacDst
   382  		x := &xy[0]
   383  		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
   384  		x.k = add(unsafe.Pointer(x.b), dataOffset)
   385  		x.e = add(x.k, bucketCnt*4)
   386  
   387  		if !h.sameSizeGrow() {
   388  			// Only calculate y pointers if we're growing bigger.
   389  			// Otherwise GC can see bad pointers.
   390  			y := &xy[1]
   391  			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
   392  			y.k = add(unsafe.Pointer(y.b), dataOffset)
   393  			y.e = add(y.k, bucketCnt*4)
   394  		}
   395  
   396  		for ; b != nil; b = b.overflow(t) {
   397  			k := add(unsafe.Pointer(b), dataOffset)
   398  			e := add(k, bucketCnt*4)
   399  			for i := 0; i < bucketCnt; i, k, e = i+1, add(k, 4), add(e, uintptr(t.elemsize)) {
   400  				top := b.tophash[i]
   401  				if isEmpty(top) {
   402  					b.tophash[i] = evacuatedEmpty
   403  					continue
   404  				}
   405  				if top < minTopHash {
   406  					throw("bad map state")
   407  				}
   408  				var useY uint8
   409  				if !h.sameSizeGrow() {
   410  					// Compute hash to make our evacuation decision (whether we need
   411  					// to send this key/elem to bucket x or bucket y).
   412  					hash := t.hasher(k, uintptr(h.hash0))
   413  					if hash&newbit != 0 {
   414  						useY = 1
   415  					}
   416  				}
   417  
   418  				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap
   419  				dst := &xy[useY]                 // evacuation destination
   420  
   421  				if dst.i == bucketCnt {
   422  					dst.b = h.newoverflow(t, dst.b)
   423  					dst.i = 0
   424  					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
   425  					dst.e = add(dst.k, bucketCnt*4)
   426  				}
   427  				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
   428  
   429  				// Copy key.
   430  				if sys.PtrSize == 4 && t.key.ptrdata != 0 && writeBarrier.enabled {
   431  					// Write with a write barrier.
   432  					*(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k)
   433  				} else {
   434  					*(*uint32)(dst.k) = *(*uint32)(k)
   435  				}
   436  
   437  				typedmemmove(t.elem, dst.e, e)
   438  				dst.i++
   439  				// These updates might push these pointers past the end of the
   440  				// key or elem arrays.  That's ok, as we have the overflow pointer
   441  				// at the end of the bucket to protect against pointing past the
   442  				// end of the bucket.
   443  				dst.k = add(dst.k, 4)
   444  				dst.e = add(dst.e, uintptr(t.elemsize))
   445  			}
   446  		}
   447  		// Unlink the overflow buckets & clear key/elem to help GC.
   448  		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
   449  			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
   450  			// Preserve b.tophash because the evacuation
   451  			// state is maintained there.
   452  			ptr := add(b, dataOffset)
   453  			n := uintptr(t.bucketsize) - dataOffset
   454  			memclrHasPointers(ptr, n)
   455  		}
   456  	}
   457  
   458  	if oldbucket == h.nevacuate {
   459  		advanceEvacuationMark(h, t, newbit)
   460  	}
   461  }
   462  

View as plain text