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.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, 8) {
		44  			if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) {
		45  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.elemsize))
		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.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, 8) {
		84  			if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) {
		85  				return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.elemsize)), 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.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_fast64(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  					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  		// 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*8)
	 168  	// store new key at insert position
	 169  	*(*uint64)(insertk) = key
	 170  
	 171  	h.count++
	 172  
	 173  done:
	 174  	elem := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+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_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.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_fast64(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  					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  		// 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*8)
	 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*8+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_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.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_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.ptrdata != 0 {
	 303  				if sys.PtrSize == 8 {
	 304  					*(*unsafe.Pointer)(k) = nil
	 305  				} else {
	 306  					// There are three ways to squeeze at one ore more 32 bit pointers into 64 bits.
	 307  					// Just call memclrHasPointers instead of trying to handle all cases here.
	 308  					memclrHasPointers(k, 8)
	 309  				}
	 310  			}
	 311  			e := add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.elemsize))
	 312  			if t.elem.ptrdata != 0 {
	 313  				memclrHasPointers(e, t.elem.size)
	 314  			} else {
	 315  				memclrNoHeapPointers(e, t.elem.size)
	 316  			}
	 317  			b.tophash[i] = emptyOne
	 318  			// If the bucket now ends in a bunch of emptyOne states,
	 319  			// change those to emptyRest states.
	 320  			if i == bucketCnt-1 {
	 321  				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
	 322  					goto notLast
	 323  				}
	 324  			} else {
	 325  				if b.tophash[i+1] != emptyRest {
	 326  					goto notLast
	 327  				}
	 328  			}
	 329  			for {
	 330  				b.tophash[i] = emptyRest
	 331  				if i == 0 {
	 332  					if b == bOrig {
	 333  						break // beginning of initial bucket, we're done.
	 334  					}
	 335  					// Find previous bucket, continue at its last entry.
	 336  					c := b
	 337  					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
	 338  					}
	 339  					i = bucketCnt - 1
	 340  				} else {
	 341  					i--
	 342  				}
	 343  				if b.tophash[i] != emptyOne {
	 344  					break
	 345  				}
	 346  			}
	 347  		notLast:
	 348  			h.count--
	 349  			// Reset the hash seed to make it more difficult for attackers to
	 350  			// repeatedly trigger hash collisions. See issue 25237.
	 351  			if h.count == 0 {
	 352  				h.hash0 = fastrand()
	 353  			}
	 354  			break search
	 355  		}
	 356  	}
	 357  
	 358  	if h.flags&hashWriting == 0 {
	 359  		throw("concurrent map writes")
	 360  	}
	 361  	h.flags &^= hashWriting
	 362  }
	 363  
	 364  func growWork_fast64(t *maptype, h *hmap, bucket uintptr) {
	 365  	// make sure we evacuate the oldbucket corresponding
	 366  	// to the bucket we're about to use
	 367  	evacuate_fast64(t, h, bucket&h.oldbucketmask())
	 368  
	 369  	// evacuate one more oldbucket to make progress on growing
	 370  	if h.growing() {
	 371  		evacuate_fast64(t, h, h.nevacuate)
	 372  	}
	 373  }
	 374  
	 375  func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) {
	 376  	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	 377  	newbit := h.noldbuckets()
	 378  	if !evacuated(b) {
	 379  		// TODO: reuse overflow buckets instead of using new ones, if there
	 380  		// is no iterator using the old buckets.	(If !oldIterator.)
	 381  
	 382  		// xy contains the x and y (low and high) evacuation destinations.
	 383  		var xy [2]evacDst
	 384  		x := &xy[0]
	 385  		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
	 386  		x.k = add(unsafe.Pointer(x.b), dataOffset)
	 387  		x.e = add(x.k, bucketCnt*8)
	 388  
	 389  		if !h.sameSizeGrow() {
	 390  			// Only calculate y pointers if we're growing bigger.
	 391  			// Otherwise GC can see bad pointers.
	 392  			y := &xy[1]
	 393  			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
	 394  			y.k = add(unsafe.Pointer(y.b), dataOffset)
	 395  			y.e = add(y.k, bucketCnt*8)
	 396  		}
	 397  
	 398  		for ; b != nil; b = b.overflow(t) {
	 399  			k := add(unsafe.Pointer(b), dataOffset)
	 400  			e := add(k, bucketCnt*8)
	 401  			for i := 0; i < bucketCnt; i, k, e = i+1, add(k, 8), add(e, uintptr(t.elemsize)) {
	 402  				top := b.tophash[i]
	 403  				if isEmpty(top) {
	 404  					b.tophash[i] = evacuatedEmpty
	 405  					continue
	 406  				}
	 407  				if top < minTopHash {
	 408  					throw("bad map state")
	 409  				}
	 410  				var useY uint8
	 411  				if !h.sameSizeGrow() {
	 412  					// Compute hash to make our evacuation decision (whether we need
	 413  					// to send this key/elem to bucket x or bucket y).
	 414  					hash := t.hasher(k, uintptr(h.hash0))
	 415  					if hash&newbit != 0 {
	 416  						useY = 1
	 417  					}
	 418  				}
	 419  
	 420  				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap
	 421  				dst := &xy[useY]								 // evacuation destination
	 422  
	 423  				if dst.i == bucketCnt {
	 424  					dst.b = h.newoverflow(t, dst.b)
	 425  					dst.i = 0
	 426  					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
	 427  					dst.e = add(dst.k, bucketCnt*8)
	 428  				}
	 429  				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
	 430  
	 431  				// Copy key.
	 432  				if t.key.ptrdata != 0 && writeBarrier.enabled {
	 433  					if sys.PtrSize == 8 {
	 434  						// Write with a write barrier.
	 435  						*(*unsafe.Pointer)(dst.k) = *(*unsafe.Pointer)(k)
	 436  					} else {
	 437  						// There are three ways to squeeze at least one 32 bit pointer into 64 bits.
	 438  						// Give up and call typedmemmove.
	 439  						typedmemmove(t.key, dst.k, k)
	 440  					}
	 441  				} else {
	 442  					*(*uint64)(dst.k) = *(*uint64)(k)
	 443  				}
	 444  
	 445  				typedmemmove(t.elem, dst.e, e)
	 446  				dst.i++
	 447  				// These updates might push these pointers past the end of the
	 448  				// key or elem arrays.	That's ok, as we have the overflow pointer
	 449  				// at the end of the bucket to protect against pointing past the
	 450  				// end of the bucket.
	 451  				dst.k = add(dst.k, 8)
	 452  				dst.e = add(dst.e, uintptr(t.elemsize))
	 453  			}
	 454  		}
	 455  		// Unlink the overflow buckets & clear key/elem to help GC.
	 456  		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
	 457  			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
	 458  			// Preserve b.tophash because the evacuation
	 459  			// state is maintained there.
	 460  			ptr := add(b, dataOffset)
	 461  			n := uintptr(t.bucketsize) - dataOffset
	 462  			memclrHasPointers(ptr, n)
	 463  		}
	 464  	}
	 465  
	 466  	if oldbucket == h.nevacuate {
	 467  		advanceEvacuationMark(h, t, newbit)
	 468  	}
	 469  }
	 470  

View as plain text