diff options
Diffstat (limited to 'deps/v8/test/mjsunit/wasm/atomics64-stress.js')
-rw-r--r-- | deps/v8/test/mjsunit/wasm/atomics64-stress.js | 596 |
1 files changed, 596 insertions, 0 deletions
diff --git a/deps/v8/test/mjsunit/wasm/atomics64-stress.js b/deps/v8/test/mjsunit/wasm/atomics64-stress.js new file mode 100644 index 0000000000..e0ce2324ea --- /dev/null +++ b/deps/v8/test/mjsunit/wasm/atomics64-stress.js @@ -0,0 +1,596 @@ +// Copyright 2018 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Flags: --experimental-wasm-threads + +// This test might time out if the search space for a sequential +// interleaving becomes to large. However, it should never fail. +// Note that results of this test are flaky by design. While the test is +// deterministic with a fixed seed, bugs may introduce non-determinism. + +load("test/mjsunit/wasm/wasm-constants.js"); +load("test/mjsunit/wasm/wasm-module-builder.js"); + +const kDebug = false; + +const kSequenceLength = 256; +const kNumberOfWorker = 4; +const kNumberOfSteps = 10000000; + +const kFirstOpcodeWithInput = 4; +const kFirstOpcodeWithoutOutput = 4; +const kLastOpcodeWithoutOutput = 7; + +const opCodes = [ + kExprI64AtomicLoad, + kExprI64AtomicLoad8U, + kExprI64AtomicLoad16U, + kExprI64AtomicLoad32U, + kExprI64AtomicStore, + kExprI64AtomicStore8U, + kExprI64AtomicStore16U, + kExprI64AtomicStore32U, + kExprI64AtomicAdd, + kExprI64AtomicAdd8U, + kExprI64AtomicAdd16U, + kExprI64AtomicAdd32U, + kExprI64AtomicSub, + kExprI64AtomicSub8U, + kExprI64AtomicSub16U, + kExprI64AtomicSub32U, + kExprI64AtomicAnd, + kExprI64AtomicAnd8U, + kExprI64AtomicAnd16U, + kExprI64AtomicAnd32U, + kExprI64AtomicOr, + kExprI64AtomicOr8U, + kExprI64AtomicOr16U, + kExprI64AtomicOr32U, + kExprI64AtomicXor, + kExprI64AtomicXor8U, + kExprI64AtomicXor16U, + kExprI64AtomicXor32U, + kExprI64AtomicExchange, + kExprI64AtomicExchange8U, + kExprI64AtomicExchange16U, + kExprI64AtomicExchange32U +]; + +const opCodeNames = [ + "kExprI64AtomicLoad", + "kExprI64AtomicLoad8U", + "kExprI64AtomicLoad16U", + "kExprI64AtomicLoad32U", + "kExprI64AtomicStore", + "kExprI64AtomicStore8U", + "kExprI64AtomicStore16U", + "kExprI64AtomicStore32U", + "kExprI64AtomicAdd", + "kExprI64AtomicAdd8U", + "kExprI64AtomicAdd16U", + "kExprI64AtomicAdd32U", + "kExprI64AtomicSub", + "kExprI64AtomicSub8U", + "kExprI64AtomicSub16U", + "kExprI64AtomicSub32U", + "kExprI64AtomicAnd", + "kExprI64AtomicAnd8U", + "kExprI64AtomicAnd16U", + "kExprI64AtomicAnd32U", + "kExprI64AtomicOr", + "kExprI64AtomicOr8U", + "kExprI64AtomicOr16U", + "kExprI64AtomicOr32U", + "kExprI64AtomicXor", + "kExprI64AtomicXor8U", + "kExprI64AtomicXor16U", + "kExprI64AtomicXor32U", + "kExprI64AtomicExchange", + "kExprI64AtomicExchange8U", + "kExprI64AtomicExchange16U", + "kExprI64AtomicExchange32U" +]; + +const kMaxInt32 = (1 << 31) * 2; + +class Operation { + constructor(opcode, low_input, high_input, offset) { + this.opcode = opcode != undefined ? opcode : Operation.nextOpcode(); + this.size = Operation.opcodeToSize(this.opcode); + if (low_input == undefined) { + [low_input, high_input] = Operation.inputForSize(this.size); + } + this.low_input = low_input; + this.high_input = high_input; + this.offset = offset != undefined ? offset : Operation.offsetForSize( + this.size); + } + + static nextOpcode() { + let random = Math.random(); + return Math.floor(random * opCodes.length); + } + + static opcodeToSize(opcode) { + // Instructions are ordered in 64, 8, 16, 32 bits size + return [64, 8, 16, 32][opcode % 4]; + } + + static opcodeToAlignment(opcode) { + // Instructions are ordered in 64, 8, 16, 32 bits size + return [3, 0, 1, 2][opcode % 4]; + } + + static inputForSize(size) { + if (size <= 32) { + let random = Math.random(); + // Avoid 32 bit overflow for integer here :( + return [Math.floor(random * (1 << (size - 1)) * 2), 0]; + } + return [Math.floor(Math.random() * kMaxInt32), Math.floor(Math.random() * + kMaxInt32)]; + } + + static offsetForSize(size) { + // Pick an offset in bytes between 0 and 8. + let offset = Math.floor(Math.random() * 8); + // Make sure the offset matches the required alignment by masking out the lower bits. + let size_in_bytes = size / 8; + let mask = ~(size_in_bytes - 1); + return offset & mask; + } + + get wasmOpcode() { + // [opcode, alignment, offset] + return [opCodes[this.opcode], Operation.opcodeToAlignment(this.opcode), this.offset]; + } + + get hasInput() { + return this.opcode >= kFirstOpcodeWithInput; + } + + get hasOutput() { + return this.opcode < kFirstOpcodeWithoutOutput || this.opcode > + kLastOpcodeWithoutOutput; + } + + truncateResultBits(low, high) { + if (this.size == 64) return [low, high] + + // Shift the lower part. For offsets greater four it drops out of the visible window. + let shiftedL = this.offset >= 4 ? 0 : low >>> (this.offset * 8); + // The higher part is zero for offset 0, left shifted for [1..3] and right shifted + // for [4..7]. + let shiftedH = this.offset == 0 ? 0 : + this.offset >= 4 ? high >>> (this.offset - 4) * 8 : high << ((4 - + this.offset) * 8); + let value = shiftedL | shiftedH; + + switch (this.size) { + case 8: + return [value & 0xFF, 0]; + case 16: + return [value & 0xFFFF, 0]; + case 32: + return [value, 0]; + default: + throw "Unexpected size: " + this.size; + } + } + + static get builder() { + if (!Operation.__builder) { + let builder = new WasmModuleBuilder(); + builder.addMemory(1, 1, 1, false); + builder.exportMemoryAs("mem"); + Operation.__builder = builder; + } + return Operation.__builder; + } + + static get exports() { + if (!Operation.__instance) { + return {}; + } + return Operation.__instance.exports; + } + + static get memory() { + return Operation.exports.mem; + } + + static set instance(instance) { + Operation.__instance = instance; + } + + compute(state) { + let evalFun = Operation.exports[this.key]; + if (!evalFun) { + let builder = Operation.builder; + let body = [ + // Load address of low 32 bits. + kExprI32Const, 0, + // Load expected value. + kExprGetLocal, 0, + kExprI32StoreMem, 2, 0, + // Load address of high 32 bits. + kExprI32Const, 4, + // Load expected value. + kExprGetLocal, 1, + kExprI32StoreMem, 2, 0, + // Load address of where our window starts. + kExprI32Const, 0, + // Load input if there is one. + ...(this.hasInput ? [kExprGetLocal, 3, + kExprI64UConvertI32, + kExprI64Const, 32, + kExprI64Shl, + kExprGetLocal, 2, + kExprI64UConvertI32, + kExprI64Ior + ] : []), + // Perform operation. + kAtomicPrefix, ...this.wasmOpcode, + // Drop output if it had any. + ...(this.hasOutput ? [kExprDrop] : []), + // Return. + kExprReturn + ] + builder.addFunction(this.key, kSig_v_iiii) + .addBody(body) + .exportAs(this.key); + // Instantiate module, get function exports. + let module = new WebAssembly.Module(builder.toBuffer()); + Operation.instance = new WebAssembly.Instance(module); + evalFun = Operation.exports[this.key]; + } + evalFun(state.low, state.high, this.low_input, this.high_input); + let ta = new Int32Array(Operation.memory.buffer); + if (kDebug) { + print(state.high + ":" + state.low + " " + this.toString() + + " -> " + ta[1] + ":" + ta[0]); + } + return { + low: ta[0], + high: ta[1] + }; + } + + toString() { + return opCodeNames[this.opcode] + "[+" + this.offset + "] " + this.high_input + + ":" + this.low_input; + } + + get key() { + return this.opcode + "-" + this.offset; + } +} + +class State { + constructor(low, high, indices, count) { + this.low = low; + this.high = high; + this.indices = indices; + this.count = count; + } + + isFinal() { + return (this.count == kNumberOfWorker * kSequenceLength); + } + + toString() { + return this.high + ":" + this.low + " @ " + this.indices; + } +} + +function makeSequenceOfOperations(size) { + let result = new Array(size); + for (let i = 0; i < size; i++) { + result[i] = new Operation(); + } + return result; +} + +function toSLeb128(low, high) { + let result = []; + while (true) { + let v = low & 0x7f; + // For low, fill up with zeros, high will add extra bits. + low = low >>> 7; + if (high != 0) { + let shiftIn = high << (32 - 7); + low = low | shiftIn; + // For high, fill up with ones, so that we keep trailing one. + high = high >> 7; + } + let msbIsSet = (v & 0x40) || false; + if (((low == 0) && (high == 0) && !msbIsSet) || ((low == -1) && (high == + -1) && msbIsSet)) { + result.push(v); + break; + } + result.push(v | 0x80); + } + return result; +} + +function generateFunctionBodyForSequence(sequence) { + // We expect the int64* to perform ops on as arg 0 and + // the int64* for our value log as arg1. Argument 2 gives + // an int32* we use to count down spinning workers. + let body = []; + // Initially, we spin until all workers start running. + if (!kDebug) { + body.push( + // Decrement the wait count. + kExprGetLocal, 2, + kExprI32Const, 1, + kAtomicPrefix, kExprI32AtomicSub, 2, 0, + // Spin until zero. + kExprLoop, kWasmStmt, + kExprGetLocal, 2, + kAtomicPrefix, kExprI32AtomicLoad, 2, 0, + kExprI32Const, 0, + kExprI32GtU, + kExprBrIf, 0, + kExprEnd + ); + } + for (let operation of sequence) { + body.push( + // Pre-load address of results sequence pointer for later. + kExprGetLocal, 1, + // Load address where atomic pointers are stored. + kExprGetLocal, 0, + // Load the second argument if it had any. + ...(operation.hasInput ? [kExprI64Const, ...toSLeb128(operation + .low_input, operation.high_input)] : []), + // Perform operation + kAtomicPrefix, ...operation.wasmOpcode, + // Generate fake output in needed. + ...(operation.hasOutput ? [] : [kExprI64Const, 0]), + // Store read intermediate to sequence. + kExprI64StoreMem, 3, 0, + // Increment result sequence pointer. + kExprGetLocal, 1, + kExprI32Const, 8, + kExprI32Add, + kExprSetLocal, 1 + ); + } + // Return end of sequence index. + body.push( + kExprGetLocal, 1, + kExprReturn); + return body; +} + +function getSequence(start, end) { + return new Int32Array(memory.buffer, start, (end - start) / Int32Array.BYTES_PER_ELEMENT); +} + +function spawnWorkers() { + let workers = []; + for (let i = 0; i < kNumberOfWorker; i++) { + let worker = new Worker( + `onmessage = function(msg) { + if (msg.module) { + let module = msg.module; + let mem = msg.mem; + this.instance = new WebAssembly.Instance(module, {m: {imported_mem: mem}}); + postMessage({instantiated: true}); + } else { + let address = msg.address; + let sequence = msg.sequence; + let index = msg.index; + let spin = msg.spin; + let result = instance.exports["worker" + index](address, sequence, spin); + postMessage({index: index, sequence: sequence, result: result}); + } + }`, {type: 'string'} + ); + workers.push(worker); + } + return workers; +} + +function instantiateModuleInWorkers(workers) { + for (let worker of workers) { + worker.postMessage({ + module: module, + mem: memory + }); + let msg = worker.getMessage(); + if (!msg.instantiated) throw "Worker failed to instantiate"; + } +} + +function executeSequenceInWorkers(workers) { + for (i = 0; i < workers.length; i++) { + let worker = workers[i]; + worker.postMessage({ + index: i, + address: 0, + spin: 16, + sequence: 32 + ((kSequenceLength * 8) + 32) * i + }); + // In debug mode, keep execution sequential. + if (kDebug) { + let msg = worker.getMessage(); + results[msg.index] = getSequence(msg.sequence, msg.result); + } + } +} + +function selectMatchingWorkers(state) { + let matching = []; + let indices = state.indices; + for (let i = 0; i < indices.length; i++) { + let index = indices[i]; + if (index >= kSequenceLength) continue; + // We need to project the expected value to the number of bits this + // operation will read at runtime. + let [expected_low, expected_high] = sequences[i][index].truncateResultBits( + state.low, state.high); + let hasOutput = sequences[i][index].hasOutput; + if (!hasOutput || ((results[i][index * 2] == expected_low) && (results[ + i][index * 2 + 1] == expected_high))) { + matching.push(i); + } + } + return matching; +} + +function computeNextState(state, advanceIdx) { + let newIndices = state.indices.slice(); + let sequence = sequences[advanceIdx]; + let operation = sequence[state.indices[advanceIdx]]; + newIndices[advanceIdx]++; + let { + low, + high + } = operation.compute(state); + + return new State(low, high, newIndices, state.count + 1); +} + +function findSequentialOrdering() { + let startIndices = new Array(results.length); + let steps = 0; + startIndices.fill(0); + let matchingStates = [new State(0, 0, startIndices, 0)]; + while (matchingStates.length > 0) { + let current = matchingStates.pop(); + if (kDebug) { + print(current); + } + let matchingResults = selectMatchingWorkers(current); + if (matchingResults.length == 0) { + continue; + } + for (let match of matchingResults) { + let newState = computeNextState(current, match); + if (newState.isFinal()) { + return true; + } + matchingStates.push(newState); + } + if (steps++ > kNumberOfSteps) { + print("Search timed out, aborting..."); + return true; + } + } + // We have no options left. + return false; +} + +// Helpful for debugging failed tests. +function loadSequencesFromStrings(inputs) { + let reverseOpcodes = {}; + for (let i = 0; i < opCodeNames.length; i++) { + reverseOpcodes[opCodeNames[i]] = i; + } + let sequences = []; + let parseRE = /([a-zA-Z0-9]*)\[\+([0-9])\] ([\-0-9]*)/; + for (let input of inputs) { + let parts = input.split(","); + let sequence = []; + for (let part of parts) { + let parsed = parseRE.exec(part); + sequence.push(new Operation(reverseOpcodes[parsed[1]], parsed[3], + parsed[2] | 0)); + } + sequences.push(sequence); + } + return sequences; +} + +// Helpful for debugging failed tests. +function loadResultsFromStrings(inputs) { + let results = []; + for (let input of inputs) { + let parts = input.split(","); + let result = []; + for (let number of parts) { + result.push(number | 0); + } + results.push(result); + } + return results; +} + +let maxSize = 10; +let memory = new WebAssembly.Memory({ + initial: 1, + maximum: maxSize, + shared: true +}); +let memory_view = new Int32Array(memory.buffer); + +let sequences = []; +let results = []; + +let builder = new WasmModuleBuilder(); +builder.addImportedMemory("m", "imported_mem", 0, maxSize, "shared"); + +for (let i = 0; i < kNumberOfWorker; i++) { + sequences[i] = makeSequenceOfOperations(kSequenceLength); + builder.addFunction("worker" + i, kSig_i_iii) + .addBody(generateFunctionBodyForSequence(sequences[i])) + .exportAs("worker" + i); +} + +// Instantiate module, get function exports. +let module = new WebAssembly.Module(builder.toBuffer()); +let instance = new WebAssembly.Instance(module, { + m: { + imported_mem: memory + } +}); + +// Spawn off the workers and run the sequences. +let workers = spawnWorkers(); +// Set spin count. +memory_view[4] = kNumberOfWorker; +instantiateModuleInWorkers(workers); +executeSequenceInWorkers(workers); + +if (!kDebug) { + // Collect results, d8 style. + for (let worker of workers) { + let msg = worker.getMessage(); + results[msg.index] = getSequence(msg.sequence, msg.result); + } +} + +// Terminate all workers. +for (let worker of workers) { + worker.terminate(); +} + +// In debug mode, print sequences and results. +if (kDebug) { + for (let result of results) { + print(result); + } + + for (let sequence of sequences) { + print(sequence); + } +} + +// Try to reconstruct a sequential ordering. +let passed = findSequentialOrdering(); + +if (passed) { + print("PASS"); +} else { + for (let i = 0; i < kNumberOfWorker; i++) { + print("Worker " + i); + print(sequences[i]); + print(results[i]); + } + print("FAIL"); + quit(-1); +} |