blob: 386a3b5549b96e82d43b3346dc0b9ab1c0a9ac8e [file] [log] [blame]
// 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-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'
];
let kMaxMemPages = 10;
let gSharedMemory =
new WebAssembly.Memory({initial: 1, maximum: kMaxMemPages, shared: true});
let gSharedMemoryView = new Int32Array(gSharedMemory.buffer);
let gPrivateMemory =
new WebAssembly.Memory({initial: 1, maximum: kMaxMemPages, shared: true});
let gPrivateMemoryView = new Int32Array(gPrivateMemory.buffer);
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.addImportedMemory('m', 'imported_mem', 0, kMaxMemPages, 'shared');
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, {m: {imported_mem: gPrivateMemory}});
evalFun = Operation.exports[this.key];
}
evalFun(state.low, state.high, this.low_input, this.high_input);
let ta = gPrivateMemoryView;
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(
gSharedMemory.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: gSharedMemory});
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 sequences = [];
let results = [];
let builder = new WasmModuleBuilder();
builder.addImportedMemory('m', 'imported_mem', 0, kMaxMemPages, '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: gSharedMemory}});
// Spawn off the workers and run the sequences.
let workers = spawnWorkers();
// Set spin count.
gSharedMemoryView[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);
}