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 5package runtime 6 7import ( 8 "runtime/internal/sys" 9 "unsafe" 10) 11 12func 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 } 78dohash: 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 107func 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 } 173dohash: 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 202func 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 223again: 224 bucket := hash & bucketMask(h.B) 225 if h.growing() { 226 growWork_faststr(t, h, bucket) 227 } 228 b := (*bmap)(unsafe.Pointer(uintptr(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 235bucketloop: 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 goto done 259 } 260 ovf := b.overflow(t) 261 if ovf == nil { 262 break 263 } 264 b = ovf 265 } 266 267 // Did not find mapping for key. Allocate new cell & add entry. 268 269 // If we hit the max load factor or we have too many overflow buckets, 270 // and we're not already in the middle of growing, start growing. 271 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { 272 hashGrow(t, h) 273 goto again // Growing the table invalidates everything, so try again 274 } 275 276 if insertb == nil { 277 // all current buckets are full, allocate a new one. 278 insertb = h.newoverflow(t, b) 279 inserti = 0 // not necessary, but avoids needlessly spilling inserti 280 } 281 insertb.tophash[inserti&(bucketCnt-1)] = top // mask inserti to avoid bounds checks 282 283 insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*sys.PtrSize) 284 // store new key at insert position 285 *((*stringStruct)(insertk)) = *key 286 h.count++ 287 288done: 289 elem := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*2*sys.PtrSize+inserti*uintptr(t.elemsize)) 290 if h.flags&hashWriting == 0 { 291 throw("concurrent map writes") 292 } 293 h.flags &^= hashWriting 294 return elem 295} 296 297func mapdelete_faststr(t *maptype, h *hmap, ky string) { 298 if raceenabled && h != nil { 299 callerpc := getcallerpc() 300 racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_faststr)) 301 } 302 if h == nil || h.count == 0 { 303 return 304 } 305 if h.flags&hashWriting != 0 { 306 throw("concurrent map writes") 307 } 308 309 key := stringStructOf(&ky) 310 hash := t.hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0)) 311 312 // Set hashWriting after calling t.hasher for consistency with mapdelete 313 h.flags ^= hashWriting 314 315 bucket := hash & bucketMask(h.B) 316 if h.growing() { 317 growWork_faststr(t, h, bucket) 318 } 319 b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) 320 bOrig := b 321 top := tophash(hash) 322search: 323 for ; b != nil; b = b.overflow(t) { 324 for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { 325 k := (*stringStruct)(kptr) 326 if k.len != key.len || b.tophash[i] != top { 327 continue 328 } 329 if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) { 330 continue 331 } 332 // Clear key's pointer. 333 k.str = nil 334 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.elemsize)) 335 if t.elem.ptrdata != 0 { 336 memclrHasPointers(e, t.elem.size) 337 } else { 338 memclrNoHeapPointers(e, t.elem.size) 339 } 340 b.tophash[i] = emptyOne 341 // If the bucket now ends in a bunch of emptyOne states, 342 // change those to emptyRest states. 343 if i == bucketCnt-1 { 344 if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { 345 goto notLast 346 } 347 } else { 348 if b.tophash[i+1] != emptyRest { 349 goto notLast 350 } 351 } 352 for { 353 b.tophash[i] = emptyRest 354 if i == 0 { 355 if b == bOrig { 356 break // beginning of initial bucket, we're done. 357 } 358 // Find previous bucket, continue at its last entry. 359 c := b 360 for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { 361 } 362 i = bucketCnt - 1 363 } else { 364 i-- 365 } 366 if b.tophash[i] != emptyOne { 367 break 368 } 369 } 370 notLast: 371 h.count-- 372 break search 373 } 374 } 375 376 if h.flags&hashWriting == 0 { 377 throw("concurrent map writes") 378 } 379 h.flags &^= hashWriting 380} 381 382func growWork_faststr(t *maptype, h *hmap, bucket uintptr) { 383 // make sure we evacuate the oldbucket corresponding 384 // to the bucket we're about to use 385 evacuate_faststr(t, h, bucket&h.oldbucketmask()) 386 387 // evacuate one more oldbucket to make progress on growing 388 if h.growing() { 389 evacuate_faststr(t, h, h.nevacuate) 390 } 391} 392 393func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { 394 b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) 395 newbit := h.noldbuckets() 396 if !evacuated(b) { 397 // TODO: reuse overflow buckets instead of using new ones, if there 398 // is no iterator using the old buckets. (If !oldIterator.) 399 400 // xy contains the x and y (low and high) evacuation destinations. 401 var xy [2]evacDst 402 x := &xy[0] 403 x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) 404 x.k = add(unsafe.Pointer(x.b), dataOffset) 405 x.e = add(x.k, bucketCnt*2*sys.PtrSize) 406 407 if !h.sameSizeGrow() { 408 // Only calculate y pointers if we're growing bigger. 409 // Otherwise GC can see bad pointers. 410 y := &xy[1] 411 y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) 412 y.k = add(unsafe.Pointer(y.b), dataOffset) 413 y.e = add(y.k, bucketCnt*2*sys.PtrSize) 414 } 415 416 for ; b != nil; b = b.overflow(t) { 417 k := add(unsafe.Pointer(b), dataOffset) 418 e := add(k, bucketCnt*2*sys.PtrSize) 419 for i := 0; i < bucketCnt; i, k, e = i+1, add(k, 2*sys.PtrSize), add(e, uintptr(t.elemsize)) { 420 top := b.tophash[i] 421 if isEmpty(top) { 422 b.tophash[i] = evacuatedEmpty 423 continue 424 } 425 if top < minTopHash { 426 throw("bad map state") 427 } 428 var useY uint8 429 if !h.sameSizeGrow() { 430 // Compute hash to make our evacuation decision (whether we need 431 // to send this key/elem to bucket x or bucket y). 432 hash := t.hasher(k, uintptr(h.hash0)) 433 if hash&newbit != 0 { 434 useY = 1 435 } 436 } 437 438 b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap 439 dst := &xy[useY] // evacuation destination 440 441 if dst.i == bucketCnt { 442 dst.b = h.newoverflow(t, dst.b) 443 dst.i = 0 444 dst.k = add(unsafe.Pointer(dst.b), dataOffset) 445 dst.e = add(dst.k, bucketCnt*2*sys.PtrSize) 446 } 447 dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check 448 449 // Copy key. 450 *(*string)(dst.k) = *(*string)(k) 451 452 typedmemmove(t.elem, dst.e, e) 453 dst.i++ 454 // These updates might push these pointers past the end of the 455 // key or elem arrays. That's ok, as we have the overflow pointer 456 // at the end of the bucket to protect against pointing past the 457 // end of the bucket. 458 dst.k = add(dst.k, 2*sys.PtrSize) 459 dst.e = add(dst.e, uintptr(t.elemsize)) 460 } 461 } 462 // Unlink the overflow buckets & clear key/elem to help GC. 463 if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 { 464 b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) 465 // Preserve b.tophash because the evacuation 466 // state is maintained there. 467 ptr := add(b, dataOffset) 468 n := uintptr(t.bucketsize) - dataOffset 469 memclrHasPointers(ptr, n) 470 } 471 } 472 473 if oldbucket == h.nevacuate { 474 advanceEvacuationMark(h, t, newbit) 475 } 476} 477