atomicity.js (15328B)
1 // Test that wasm atomic operations implement correct mutual exclusion. 2 // 3 // We have several agents that attempt to hammer on a shared location with rmw 4 // operations in such a way that failed atomicity will lead to an incorrect 5 // result. Each agent attempts to clear or set specific bits in a shared datum. 6 7 // 1 for a little bit, 2 for a lot, 3 to quit before running tests 8 const DEBUG = 0; 9 10 // The longer we run, the better, really, but we don't want to time out. 11 const ITERATIONS = 100000; 12 13 // If you change NUMWORKERS you must also change the tables for INIT, VAL, and 14 // RESULT for all the operations, below, by adding or removing bits. 15 const NUMWORKERS = 2; 16 const NUMAGENTS = NUMWORKERS + 1; 17 18 // Need at least one thread per agent. 19 20 if (!wasmThreadsEnabled() || helperThreadCount() < NUMWORKERS) { 21 if (DEBUG > 0) 22 print("Threads not supported"); 23 quit(0); 24 } 25 26 // Unless there are enough actual cores the spinning threads will not interact 27 // in the desired way (we'll be waiting on preemption to advance), and this 28 // makes the test pointless and also will usually make it time out. So bail out 29 // if we can't have one core per agent. 30 31 if (getCoreCount() < NUMAGENTS) { 32 if (DEBUG > 0) 33 print("Fake or feeble hardware"); 34 quit(0); 35 } 36 37 // Most of the simulators have poor support for mutual exclusion and are anyway 38 // too slow; avoid intermittent failures and timeouts. 39 40 if (getBuildConfiguration("arm-simulator") || getBuildConfiguration("arm64-simulator") || 41 getBuildConfiguration("mips64-simulator") || getBuildConfiguration("riscv64-simulator") || 42 getBuildConfiguration("loong64-simulator")) 43 { 44 if (DEBUG > 0) 45 print("Atomicity test disabled on simulator"); 46 quit(0); 47 } 48 49 //////////////////////////////////////////////////////////////////////// 50 // 51 // Coordination code for bootstrapping workers - use spawn() to create a worker, 52 // send() to send an item to a worker. send() will send to anyone, so only one 53 // worker should be receiving at a time. spawn() will block until the worker is 54 // running; send() will block until the message has been received. 55 56 var COORD_BUSY = 0; 57 var COORD_NUMLOC = 1; 58 59 var coord = new Int32Array(new SharedArrayBuffer(COORD_NUMLOC*4)); 60 61 function spawn(text) { 62 text = ` 63 var _coord = new Int32Array(getSharedObject()); 64 Atomics.store(_coord, ${COORD_BUSY}, 0); 65 function receive() { 66 while (!Atomics.load(_coord, ${COORD_BUSY})) 67 ; 68 let x = getSharedObject(); 69 Atomics.store(_coord, ${COORD_BUSY}, 0); 70 return x; 71 } 72 ` + text; 73 setSharedObject(coord.buffer); 74 Atomics.store(coord, COORD_BUSY, 1); 75 evalInWorker(text); 76 while (Atomics.load(coord, COORD_BUSY)) 77 ; 78 } 79 80 function send(x) { 81 while(Atomics.load(coord, COORD_BUSY)) 82 ; 83 setSharedObject(x); 84 Atomics.store(coord, COORD_BUSY, 1); 85 while(Atomics.load(coord, COORD_BUSY)) 86 ; 87 } 88 89 ///////////////////////////////////////////////////////////////////////////////// 90 // 91 // The "agents" comprise one master and one or more additional workers. We make 92 // a separate module for each agent so that test values can be inlined as 93 // constants. 94 // 95 // The master initially sets a shared location LOC to a value START. 96 // 97 // Each agent then operates atomically on LOC with an operation OP and a value 98 // VAL. The operation OP is the same for all agents but each agent `i` has a 99 // different VAL_i. 100 // 101 // To make this more interesting, the value START is distributed as many times 102 // through the value at LOC as there is space for, and we perform several 103 // operations back-to-back, with the VAL_i appropriately shifted. 104 // 105 // Each agent then spin-waits for LOC to contain a particular RESULT, which is 106 // always (START OP VAL_0 OP VAL_1 ... VAL_k), again repeated throughout the 107 // RESULT as appropriate. 108 // 109 // The process then starts over, and we repeat the process many times. If we 110 // fail to have atomicity at any point the program will hang (LOC will never 111 // attain the desired value) and the test should therefore time out. 112 // 113 // (Barriers are needed to make this all work out.) 114 // 115 // The general principle for the values is that each VAL should add (or clear) a 116 // bit of the stored value. 117 // 118 // OP START VAL0 VAL1 VAL2 RESULT 119 // 120 // ADD[*] 0 1 2 4 7 121 // SUB 7 1 2 4 0 122 // AND 7 3 6 5 0 123 // OR 0 1 2 4 7 124 // XOR 0 1 2 4 7 // or start with 7 and end with 0 125 // CMPXCHG 0 1 2 4 7 // use nonatomic "or" to add the bit 126 // 127 // [*] Running the tests actually assumes that ADD works reasonably well. 128 // 129 // TODO - more variants we could test: 130 // 131 // - tests that do not drop the values of the atomic ops but accumulate them: 132 // uses different code generation on x86/x64 133 // 134 // - Xchg needs a different method, since here the atomic thing is that we read 135 // the "previous value" and set the next value atomically. How can we observe 136 // that that fails? If we run three agents, which all set the value to X, 137 // X+1, ..., X+n, with the initial value being (say) X-1, each can record the 138 // value it observed in a table, and we should be able to predict the counts 139 // in that table once postprocessed. eg, the counts should all be the same. 140 // If atomicity fails then a value is read twice when it shouldn't be, and 141 // some other value is not read at all, and the counts will be off. 142 // 143 // - the different rmw operations can usually be combined so that we can test 144 // the atomicity of operations that may be implemented differently. 145 // 146 // - the same tests, with test values as variables instead of constants. 147 148 function makeModule(id) { 149 let isMaster = id == 0; 150 let VALSHIFT = NUMAGENTS; // 1 bit per agent 151 152 function makeLoop(bits, name, op, loc, initial, val, expected) { 153 // Exclude high bit to avoid messing with the sign. 154 let NUMVALS32 = Math.floor(31/VALSHIFT); 155 let NUMVALS = bits == 64 ? 2 * NUMVALS32 : Math.floor(Math.min(bits,31)/VALSHIFT); 156 let BARRIER = "(i32.const 0)"; 157 let barrier = ` 158 ;; Barrier 159 (local.set $barrierValue (i32.add (local.get $barrierValue) (i32.const ${NUMAGENTS}))) 160 (drop (i32.atomic.rmw.add ${BARRIER} (i32.const 1))) 161 (loop $c1 162 (if (i32.lt_s (i32.atomic.load ${BARRIER}) (local.get $barrierValue)) 163 (then (br $c1)))) 164 ;; End barrier 165 `; 166 167 // Distribute a value `v` across a word NUMVALs times 168 169 function distribute(v) { 170 if (bits <= 32) 171 return '0x' + dist32(v); 172 return '0x' + dist32(v) + dist32(v); 173 } 174 175 function dist32(v) { 176 let n = 0; 177 for (let i=0; i < Math.min(NUMVALS, NUMVALS32); i++) 178 n = n | (v << (i*VALSHIFT)); 179 assertEq(n >= 0, true); 180 return (n + 0x100000000).toString(16).substring(1); 181 } 182 183 // Position a value `v` at position `pos` in a word 184 185 function format(val, pos) { 186 if (bits <= 32) 187 return '0x' + format32(val, pos); 188 if (pos < NUMVALS32) 189 return '0x' + '00000000' + format32(val, pos); 190 return '0x' + format32(val, pos - NUMVALS32) + '00000000'; 191 } 192 193 function format32(val, pos) { 194 return ((val << (pos * VALSHIFT)) + 0x100000000).toString(16).substring(1); 195 } 196 197 let width = bits < 32 ? '' + bits : ''; 198 let view = bits < 32 ? '_u' : ''; 199 let prefix = bits == 64 ? 'i64' : 'i32'; 200 return ` 201 (func ${name} (param $barrierValue i32) (result i32) 202 (local $n i32) 203 (local $tmp ${prefix}) 204 (local.set $n (i32.const ${ITERATIONS})) 205 (loop $outer 206 (if (local.get $n) 207 (then (block 208 ${isMaster ? `;; Init 209 (${prefix}.atomic.store${width} ${loc} (${prefix}.const ${distribute(initial)}))` : ``} 210 ${barrier} 211 212 ${(() => { 213 let s = `;; Do\n`; 214 for (let i=0; i < NUMVALS; i++) { 215 let bitval = `(${prefix}.const ${format(val, i)})` 216 // The load must be atomic though it would be better if it were relaxed, 217 // we would avoid fences in that case. 218 if (op.match(/cmpxchg/)) { 219 s += `(loop $doit 220 (local.set $tmp (${prefix}.atomic.load${width}${view} ${loc})) 221 (br_if $doit (i32.eqz 222 (${prefix}.eq 223 (local.get $tmp) 224 (${op} ${loc} (local.get $tmp) (${prefix}.or (local.get $tmp) ${bitval})))))) 225 `; 226 } else { 227 s += `(drop (${op} ${loc} ${bitval})) 228 `; 229 } 230 } 231 return s 232 })()} 233 (loop $wait_done 234 (br_if $wait_done (${prefix}.ne (${prefix}.atomic.load${width}${view} ${loc}) (${prefix}.const ${distribute(expected)})))) 235 ${barrier} 236 (local.set $n (i32.sub (local.get $n) (i32.const 1))) 237 (br $outer))))) 238 (local.get $barrierValue))`; 239 } 240 241 const ADDLOC = "(i32.const 256)"; 242 const ADDINIT = 0; 243 const ADDVAL = [1, 2, 4]; 244 const ADDRESULT = 7; 245 246 const SUBLOC = "(i32.const 512)"; 247 const SUBINIT = 7; 248 const SUBVAL = [1, 2, 4]; 249 const SUBRESULT = 0; 250 251 const ANDLOC = "(i32.const 768)"; 252 const ANDINIT = 7; 253 const ANDVAL = [3, 6, 5]; 254 const ANDRESULT = 0; 255 256 const ORLOC = "(i32.const 1024)"; 257 const ORINIT = 0; 258 const ORVAL = [1, 2, 4]; 259 const ORRESULT = 7; 260 261 const XORLOC = "(i32.const 1280)"; 262 const XORINIT = 0; 263 const XORVAL = [1, 2, 4]; 264 const XORRESULT = 7; 265 266 const CMPXCHGLOC = "(i32.const 1536)"; 267 const CMPXCHGINIT = 0; 268 const CMPXCHGVAL = [1, 2, 4]; 269 const CMPXCHGRESULT = 7; 270 271 return ` 272 (module 273 (import "" "memory" (memory 1 1 shared)) 274 (import "" "print" (func $print (param i32))) 275 276 ${makeLoop(8, "$test_add8", "i32.atomic.rmw8.add_u", ADDLOC, ADDINIT, ADDVAL[id], ADDRESULT)} 277 ${makeLoop(8, "$test_sub8", "i32.atomic.rmw8.sub_u", SUBLOC, SUBINIT, SUBVAL[id], SUBRESULT)} 278 ${makeLoop(8, "$test_and8", "i32.atomic.rmw8.and_u", ANDLOC, ANDINIT, ANDVAL[id], ANDRESULT)} 279 ${makeLoop(8, "$test_or8", "i32.atomic.rmw8.or_u", ORLOC, ORINIT, ORVAL[id], ORRESULT)} 280 ${makeLoop(8, "$test_xor8", "i32.atomic.rmw8.xor_u", XORLOC, XORINIT, XORVAL[id], XORRESULT)} 281 ${makeLoop(8, "$test_cmpxchg8", "i32.atomic.rmw8.cmpxchg_u", CMPXCHGLOC, CMPXCHGINIT, CMPXCHGVAL[id], CMPXCHGRESULT)} 282 283 ${makeLoop(16, "$test_add16", "i32.atomic.rmw16.add_u", ADDLOC, ADDINIT, ADDVAL[id], ADDRESULT)} 284 ${makeLoop(16, "$test_sub16", "i32.atomic.rmw16.sub_u", SUBLOC, SUBINIT, SUBVAL[id], SUBRESULT)} 285 ${makeLoop(16, "$test_and16", "i32.atomic.rmw16.and_u", ANDLOC, ANDINIT, ANDVAL[id], ANDRESULT)} 286 ${makeLoop(16, "$test_or16", "i32.atomic.rmw16.or_u", ORLOC, ORINIT, ORVAL[id], ORRESULT)} 287 ${makeLoop(16, "$test_xor16", "i32.atomic.rmw16.xor_u", XORLOC, XORINIT, XORVAL[id], XORRESULT)} 288 ${makeLoop(16, "$test_cmpxchg16", "i32.atomic.rmw16.cmpxchg_u", CMPXCHGLOC, CMPXCHGINIT, CMPXCHGVAL[id], CMPXCHGRESULT)} 289 290 ${makeLoop(32, "$test_add", "i32.atomic.rmw.add", ADDLOC, ADDINIT, ADDVAL[id], ADDRESULT)} 291 ${makeLoop(32, "$test_sub", "i32.atomic.rmw.sub", SUBLOC, SUBINIT, SUBVAL[id], SUBRESULT)} 292 ${makeLoop(32, "$test_and", "i32.atomic.rmw.and", ANDLOC, ANDINIT, ANDVAL[id], ANDRESULT)} 293 ${makeLoop(32, "$test_or", "i32.atomic.rmw.or", ORLOC, ORINIT, ORVAL[id], ORRESULT)} 294 ${makeLoop(32, "$test_xor", "i32.atomic.rmw.xor", XORLOC, XORINIT, XORVAL[id], XORRESULT)} 295 ${makeLoop(32, "$test_cmpxchg", "i32.atomic.rmw.cmpxchg", CMPXCHGLOC, CMPXCHGINIT, CMPXCHGVAL[id], CMPXCHGRESULT)} 296 297 ${makeLoop(64, "$test_add64", "i64.atomic.rmw.add", ADDLOC, ADDINIT, ADDVAL[id], ADDRESULT)} 298 ${makeLoop(64, "$test_sub64", "i64.atomic.rmw.sub", SUBLOC, SUBINIT, SUBVAL[id], SUBRESULT)} 299 ${makeLoop(64, "$test_and64", "i64.atomic.rmw.and", ANDLOC, ANDINIT, ANDVAL[id], ANDRESULT)} 300 ${makeLoop(64, "$test_or64", "i64.atomic.rmw.or", ORLOC, ORINIT, ORVAL[id], ORRESULT)} 301 ${makeLoop(64, "$test_xor64", "i64.atomic.rmw.xor", XORLOC, XORINIT, XORVAL[id], XORRESULT)} 302 ${makeLoop(64, "$test_cmpxchg64", "i64.atomic.rmw.cmpxchg", CMPXCHGLOC, CMPXCHGINIT, CMPXCHGVAL[id], CMPXCHGRESULT)} 303 304 (func (export "test") 305 (local $barrierValue i32) 306 (call $print (i32.const ${10 + id})) 307 (local.set $barrierValue (call $test_add8 (local.get $barrierValue))) 308 (local.set $barrierValue (call $test_sub8 (local.get $barrierValue))) 309 (local.set $barrierValue (call $test_and8 (local.get $barrierValue))) 310 (local.set $barrierValue (call $test_or8 (local.get $barrierValue))) 311 (local.set $barrierValue (call $test_xor8 (local.get $barrierValue))) 312 (local.set $barrierValue (call $test_cmpxchg8 (local.get $barrierValue))) 313 (call $print (i32.const ${20 + id})) 314 (local.set $barrierValue (call $test_add16 (local.get $barrierValue))) 315 (local.set $barrierValue (call $test_sub16 (local.get $barrierValue))) 316 (local.set $barrierValue (call $test_and16 (local.get $barrierValue))) 317 (local.set $barrierValue (call $test_or16 (local.get $barrierValue))) 318 (local.set $barrierValue (call $test_xor16 (local.get $barrierValue))) 319 (local.set $barrierValue (call $test_cmpxchg16 (local.get $barrierValue))) 320 (call $print (i32.const ${30 + id})) 321 (local.set $barrierValue (call $test_add (local.get $barrierValue))) 322 (local.set $barrierValue (call $test_sub (local.get $barrierValue))) 323 (local.set $barrierValue (call $test_and (local.get $barrierValue))) 324 (local.set $barrierValue (call $test_or (local.get $barrierValue))) 325 (local.set $barrierValue (call $test_xor (local.get $barrierValue))) 326 (local.set $barrierValue (call $test_cmpxchg (local.get $barrierValue))) 327 (call $print (i32.const ${40 + id})) 328 (local.set $barrierValue (call $test_add64 (local.get $barrierValue))) 329 (local.set $barrierValue (call $test_sub64 (local.get $barrierValue))) 330 (local.set $barrierValue (call $test_and64 (local.get $barrierValue))) 331 (local.set $barrierValue (call $test_or64 (local.get $barrierValue))) 332 (local.set $barrierValue (call $test_xor64 (local.get $barrierValue))) 333 (local.set $barrierValue (call $test_cmpxchg64 (local.get $barrierValue))) 334 )) 335 `; 336 } 337 338 function makeModule2(id) { 339 let text = makeModule(id); 340 if (DEBUG > 1) 341 print(text); 342 return new WebAssembly.Module(wasmTextToBinary(text)); 343 } 344 345 var mods = []; 346 mods.push(makeModule2(0)); 347 for ( let i=0; i < NUMWORKERS; i++ ) 348 mods.push(makeModule2(i+1)); 349 if (DEBUG > 2) 350 quit(0); 351 var mem = new WebAssembly.Memory({initial: 1, maximum: 1, shared: true}); 352 353 //////////////////////////////////////////////////////////////////////// 354 // 355 // Worker code 356 357 function startWorkers() { 358 for ( let i=0; i < NUMWORKERS; i++ ) { 359 spawn(` 360 var mem = receive(); 361 var mod = receive(); 362 function pr(n) { if (${DEBUG}) print(n); } 363 var ins = new WebAssembly.Instance(mod, {"":{memory: mem, print:pr}}); 364 if (${DEBUG} > 0) 365 print("Running ${i}"); 366 ins.exports.test(); 367 `); 368 send(mem); 369 send(mods[i+1]); 370 } 371 } 372 373 //////////////////////////////////////////////////////////////////////// 374 // 375 // Main thread code 376 377 startWorkers(); 378 function pr(n) { if (DEBUG) print(n); } 379 var ins = new WebAssembly.Instance(mods[0], {"":{memory: mem, print:pr}}); 380 if (DEBUG > 0) 381 print("Running master"); 382 ins.exports.test();