libgo/go/runtime/map_fast64.go

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