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

View as plain text