1 /** 2 * Contains a bitfield used by the GC. 3 * 4 * Copyright: D Language Foundation 2005 - 2021. 5 * License: $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0). 6 * Authors: Walter Bright, David Friedman, Sean Kelly 7 */ 8 module core.internal.gc.bits; 9 10 import core.internal.gc.os : os_mem_map, os_mem_unmap, HaveFork; 11 12 import core.bitop; 13 import core.stdc.string; 14 import core.stdc.stdlib; 15 import core.exception : onOutOfMemoryError; 16 17 // use version gcbitsSingleBitOperation to disable optimizations that use 18 // word operands on bulk operation copyRange, setRange, clrRange, etc. 19 // version = gcbitsSingleBitOperation; 20 21 struct GCBits 22 { 23 @nogc: 24 alias size_t wordtype; 25 26 enum BITS_PER_WORD = (wordtype.sizeof * 8); 27 enum BITS_SHIFT = (wordtype.sizeof == 8 ? 6 : 5); 28 enum BITS_MASK = (BITS_PER_WORD - 1); 29 enum BITS_0 = cast(wordtype)0; 30 enum BITS_1 = cast(wordtype)1; 31 enum BITS_2 = cast(wordtype)2; 32 33 wordtype* data; 34 size_t nbits; 35 36 void Dtor(bool share = false) nothrow 37 { 38 if (data) 39 { 40 static if (!HaveFork) 41 free(data); 42 else if (share) 43 os_mem_unmap(data, nwords * data[0].sizeof); 44 else 45 free(data); 46 data = null; 47 } 48 } 49 50 void alloc(size_t nbits, bool share = false) nothrow 51 { 52 this.nbits = nbits; 53 static if (!HaveFork) 54 data = cast(typeof(data[0])*)calloc(nwords, data[0].sizeof); 55 else if (share) 56 data = cast(typeof(data[0])*)os_mem_map(nwords * data[0].sizeof, true); // Allocate as MAP_SHARED 57 else 58 data = cast(typeof(data[0])*)calloc(nwords, data[0].sizeof); 59 if (!data) 60 onOutOfMemoryError(); 61 } 62 testGCBits63 wordtype test(size_t i) const scope @trusted pure nothrow @nogc 64 in 65 { 66 assert(i < nbits); 67 } 68 do 69 { 70 return core.bitop.bt(data, i); 71 } 72 setGCBits73 int set(size_t i) scope @trusted pure nothrow @nogc 74 in 75 { 76 assert(i < nbits); 77 } 78 do 79 { 80 return core.bitop.bts(data, i); 81 } 82 clearGCBits83 int clear(size_t i) scope @trusted pure nothrow @nogc 84 in 85 { 86 assert(i <= nbits); 87 } 88 do 89 { 90 return core.bitop.btr(data, i); 91 } 92 93 // return non-zero if bit already set setLockedGCBits94 size_t setLocked(size_t i) scope @trusted pure nothrow @nogc 95 { 96 version (GNU) 97 { 98 import gcc.builtins; 99 const pos = i >> BITS_SHIFT; 100 const mask = BITS_1 << (i & BITS_MASK); 101 mixin("auto val = __atomic_fetch_or_" ~ size_t.sizeof.stringof[0] 102 ~ "(cast(shared)(data + pos), mask, 3);"); 103 return (val & mask) != 0; 104 } 105 else version (LDC) 106 { 107 import ldc.intrinsics; 108 const pos = i >> BITS_SHIFT; 109 const mask = BITS_1 << (i & BITS_MASK); 110 auto val = llvm_atomic_rmw_or(cast(shared)(data + pos), mask); 111 return (val & mask) != 0; 112 } 113 else version (D_InlineAsm_X86) 114 { 115 asm pure @nogc nothrow { 116 mov EAX, this; 117 mov ECX, data[EAX]; 118 mov EDX, i; 119 lock; 120 bts dword ptr[ECX], EDX; 121 sbb EAX,EAX; 122 } 123 } 124 else version (D_InlineAsm_X86_64) 125 { 126 asm pure @nogc nothrow { 127 mov RAX, this; 128 mov RAX, data[RAX]; 129 mov RDX, i; 130 lock; 131 bts qword ptr[RAX], RDX; 132 sbb RAX,RAX; 133 } 134 } 135 else 136 { 137 auto pos = i >> BITS_SHIFT; 138 auto pdata = cast(shared)(data + pos); 139 auto mask = BITS_1 << (i & BITS_MASK); 140 auto state = *pdata; 141 if (state & mask) 142 return state; 143 144 import core.atomic; 145 auto newstate = state | mask; 146 while (!cas(pdata, state, newstate)) 147 { 148 state = *pdata; 149 if (state & mask) 150 return state; 151 newstate = state | mask; 152 } 153 return 0; 154 } 155 } 156 testAndSetGCBits157 template testAndSet(bool locked) 158 { 159 static if (locked) 160 alias testAndSet = setLocked; 161 else 162 alias testAndSet = set; 163 } 164 165 RangeVarsGCBits166 mixin template RangeVars() 167 { 168 size_t firstWord = (target >> BITS_SHIFT); 169 size_t firstOff = target & BITS_MASK; 170 size_t last = target + len - 1; 171 size_t lastWord = (last >> BITS_SHIFT); 172 size_t lastOff = last & BITS_MASK; 173 } 174 175 // extract loops to allow inlining the rest clearWordsGCBits176 void clearWords(size_t firstWord, size_t lastWord) nothrow 177 { 178 for (size_t w = firstWord; w < lastWord; w++) 179 data[w] = 0; 180 } 181 setWordsGCBits182 void setWords(size_t firstWord, size_t lastWord) nothrow 183 { 184 for (size_t w = firstWord; w < lastWord; w++) 185 data[w] = ~0; 186 } 187 copyWordsGCBits188 void copyWords(size_t firstWord, size_t lastWord, const(wordtype)* source) nothrow 189 { 190 for (size_t w = firstWord; w < lastWord; w++) 191 data[w] = source[w - firstWord]; 192 } 193 copyWordsShiftedGCBits194 void copyWordsShifted(size_t firstWord, size_t cntWords, size_t firstOff, const(wordtype)* source) nothrow 195 { 196 wordtype mask = ~BITS_0 << firstOff; 197 data[firstWord] = (data[firstWord] & ~mask) | (source[0] << firstOff); 198 for (size_t w = 1; w < cntWords; w++) 199 data[firstWord + w] = (source[w - 1] >> (BITS_PER_WORD - firstOff)) | (source[w] << firstOff); 200 } 201 202 // target = the biti to start the copy to 203 // destlen = the number of bits to copy from source copyRangeGCBits204 void copyRange(size_t target, size_t len, const(wordtype)* source) nothrow 205 { 206 version (gcbitsSingleBitOperation) 207 { 208 for (size_t i = 0; i < len; i++) 209 if (source[(i >> BITS_SHIFT)] & (BITS_1 << (i & BITS_MASK))) 210 set(target+i); 211 else 212 clear(target+i); 213 } 214 else 215 { 216 if (len > 0) 217 copyRangeZ(target, len, source); 218 } 219 } 220 copyRangeZGCBits221 void copyRangeZ(size_t target, size_t len, const(wordtype)* source) nothrow 222 { 223 mixin RangeVars!(); 224 225 if (firstWord == lastWord) 226 { 227 wordtype mask = ((BITS_2 << (lastOff - firstOff)) - 1) << firstOff; 228 data[firstWord] = (data[firstWord] & ~mask) | ((source[0] << firstOff) & mask); 229 } 230 else if (firstOff == 0) 231 { 232 copyWords(firstWord, lastWord, source); 233 234 wordtype mask = (BITS_2 << lastOff) - 1; 235 data[lastWord] = (data[lastWord] & ~mask) | (source[lastWord - firstWord] & mask); 236 } 237 else 238 { 239 size_t cntWords = lastWord - firstWord; 240 copyWordsShifted(firstWord, cntWords, firstOff, source); 241 242 wordtype src = (source[cntWords - 1] >> (BITS_PER_WORD - firstOff)); 243 if (lastOff >= firstOff) // prevent buffer overread 244 src |= (source[cntWords] << firstOff); 245 wordtype mask = (BITS_2 << lastOff) - 1; 246 data[lastWord] = (data[lastWord] & ~mask) | (src & mask); 247 } 248 } 249 copyRangeRepeatingGCBits250 void copyRangeRepeating(size_t target, size_t destlen, const(wordtype)* source, size_t sourcelen) nothrow 251 { 252 version (gcbitsSingleBitOperation) 253 { 254 for (size_t i=0; i < destlen; i++) 255 { 256 bool b; 257 size_t j = i % sourcelen; 258 b = (source[j >> BITS_SHIFT] & (BITS_1 << (j & BITS_MASK))) != 0; 259 if (b) set(target+i); 260 else clear(target+i); 261 } 262 } 263 else 264 { 265 while (destlen > sourcelen) 266 { 267 copyRange(target, sourcelen, source); 268 target += sourcelen; 269 destlen -= sourcelen; 270 } 271 copyRange(target, destlen, source); 272 } 273 } 274 275 unittest 276 { 277 // simulate broken array append test case in vibe.d 278 GCBits bits; 279 bits.alloc(10000); 280 auto data = bits.data; 281 282 GCBits src; 283 src.alloc(67); 284 src.data[0] = 0x4; 285 286 bits.copyRangeRepeating(2, 10000, src.data, 67); 287 288 foreach (i; 0 .. 10000) 289 if ((i - 2) % 67 == 2) 290 assert(bits.test(i)); 291 else 292 assert(!bits.test(i)); 293 } 294 setRangeGCBits295 void setRange(size_t target, size_t len) nothrow 296 { 297 version (gcbitsSingleBitOperation) 298 { 299 for (size_t i = 0; i < len; i++) 300 set(target+i); 301 } 302 else 303 { 304 if (len > 0) 305 setRangeZ(target, len); 306 } 307 } 308 setRangeZGCBits309 void setRangeZ(size_t target, size_t len) nothrow 310 { 311 mixin RangeVars!(); 312 313 if (firstWord == lastWord) 314 { 315 wordtype mask = ((BITS_2 << (lastOff - firstOff)) - 1) << firstOff; 316 data[firstWord] |= mask; 317 } 318 else 319 { 320 data[firstWord] |= ~BITS_0 << firstOff; 321 setWords(firstWord + 1, lastWord); 322 wordtype mask = (BITS_2 << lastOff) - 1; 323 data[lastWord] |= mask; 324 } 325 } 326 clrRangeGCBits327 void clrRange(size_t target, size_t len) nothrow 328 { 329 version (gcbitsSingleBitOperation) 330 { 331 for (size_t i = 0; i < len; i++) 332 clear(target+i); 333 } 334 else 335 { 336 if (len > 0) 337 clrRangeZ(target, len); 338 } 339 } 340 clrRangeZGCBits341 void clrRangeZ(size_t target, size_t len) nothrow 342 { 343 mixin RangeVars!(); 344 if (firstWord == lastWord) 345 { 346 wordtype mask = ((BITS_2 << (lastOff - firstOff)) - 1) << firstOff; 347 data[firstWord] &= ~mask; 348 } 349 else 350 { 351 data[firstWord] &= ~(~BITS_0 << firstOff); 352 clearWords(firstWord + 1, lastWord); 353 wordtype mask = (BITS_2 << lastOff) - 1; 354 data[lastWord] &= ~mask; 355 } 356 } 357 358 unittest 359 { 360 GCBits bits; 361 bits.alloc(1000); 362 auto data = bits.data; 363 364 bits.setRange(0,1); 365 assert(data[0] == 1); 366 367 bits.clrRange(0,1); 368 assert(data[0] == 0); 369 370 bits.setRange(BITS_PER_WORD-1,1); 371 assert(data[0] == BITS_1 << (BITS_PER_WORD-1)); 372 373 bits.clrRange(BITS_PER_WORD-1,1); 374 assert(data[0] == 0); 375 376 bits.setRange(12,7); 377 assert(data[0] == 0b0111_1111_0000_0000_0000); 378 379 bits.clrRange(14,4); 380 assert(data[0] == 0b0100_0011_0000_0000_0000); 381 382 bits.clrRange(0,BITS_PER_WORD); 383 assert(data[0] == 0); 384 385 bits.setRange(0,BITS_PER_WORD); 386 assert(data[0] == ~0); 387 assert(data[1] == 0); 388 389 bits.setRange(BITS_PER_WORD,BITS_PER_WORD); 390 assert(data[0] == ~0); 391 assert(data[1] == ~0); 392 assert(data[2] == 0); 393 bits.clrRange(BITS_PER_WORD/2,BITS_PER_WORD); 394 assert(data[0] == (BITS_1 << (BITS_PER_WORD/2)) - 1); 395 assert(data[1] == ~data[0]); 396 assert(data[2] == 0); 397 398 bits.setRange(8*BITS_PER_WORD+1,4*BITS_PER_WORD-2); 399 assert(data[8] == ~0 << 1); 400 assert(data[9] == ~0); 401 assert(data[10] == ~0); 402 assert(data[11] == cast(wordtype)~0 >> 1); 403 404 bits.clrRange(9*BITS_PER_WORD+1,2*BITS_PER_WORD); 405 assert(data[8] == ~0 << 1); 406 assert(data[9] == 1); 407 assert(data[10] == 0); 408 assert(data[11] == ((cast(wordtype)~0 >> 1) & ~1)); 409 410 wordtype[4] src = [ 0xa, 0x5, 0xaa, 0x55 ]; 411 412 void testCopyRange(size_t start, size_t len, int repeat = 1) 413 { 414 bits.setRange(0, bits.nbits); 415 if (repeat > 1) 416 bits.copyRangeRepeating(start, repeat * len, src.ptr, len); 417 else 418 bits.copyRange(start, len, src.ptr); 419 foreach (i; 0 .. start) 420 assert(bits.test(i)); 421 foreach (r; 0 .. repeat) 422 foreach (i; 0 .. len) 423 assert(!bits.test(start + r*len + i) == !core.bitop.bt(src.ptr, i)); 424 foreach (i; start + repeat*len .. 10*BITS_PER_WORD) 425 assert(bits.test(i)); 426 } 427 428 testCopyRange(20, 10); // short copy range within same word 429 testCopyRange(50, 20); // short copy range spanning two words 430 testCopyRange(64, 3 * BITS_PER_WORD + 3); // aligned copy range 431 testCopyRange(77, 2 * BITS_PER_WORD + 15); // unaligned copy range 432 testCopyRange(64, 127); // copy range within critical end alignment 433 434 testCopyRange(10, 4, 5); // repeating small range within same word 435 testCopyRange(20, 5, 10); // repeating small range spanning two words 436 testCopyRange(40, 21, 7); // repeating medium range 437 testCopyRange(73, 2 * BITS_PER_WORD + 15, 5); // repeating multi-word range 438 439 testCopyRange(2, 3, 166); // failed with assert 440 } 441 zeroGCBits442 void zero() nothrow 443 { 444 memset(data, 0, nwords * wordtype.sizeof); 445 } 446 setAllGCBits447 void setAll() nothrow 448 { 449 memset(data, 0xFF, nwords * wordtype.sizeof); 450 } 451 copyGCBits452 void copy(GCBits *f) nothrow 453 in 454 { 455 assert(nwords == f.nwords); 456 } 457 do 458 { 459 memcpy(data, f.data, nwords * wordtype.sizeof); 460 } 461 nwordsGCBits462 @property size_t nwords() const pure nothrow 463 { 464 return (nbits + (BITS_PER_WORD - 1)) >> BITS_SHIFT; 465 } 466 } 467 468 unittest 469 { 470 GCBits b; 471 472 b.alloc(786); 473 assert(!b.test(123)); 474 assert(!b.clear(123)); 475 assert(!b.set(123)); 476 assert(b.test(123)); 477 assert(b.clear(123)); 478 assert(!b.test(123)); 479 480 b.set(785); 481 b.set(0); 482 assert(b.test(785)); 483 assert(b.test(0)); 484 b.zero(); 485 assert(!b.test(785)); 486 assert(!b.test(0)); 487 488 GCBits b2; 489 b2.alloc(786); 490 b2.set(38); 491 b.copy(&b2); 492 assert(b.test(38)); 493 b2.Dtor(); 494 b.Dtor(); 495 } 496