Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
#include "wasm/WasmStructLayout.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/HashFunctions.h"
#include "jstypes.h" // RoundUp
// This is a simple implementation of a layouter. It places the OOL pointer
// at the start of the IL payload area, regardless of whether an OOL area is
// actually necessary.
namespace js::wasm {
//=========================================================================
// BitVector
// See comment in WasmStructLayout.h for meaning of "byte", "offset" and
// "chunk".
#ifdef DEBUG
static bool Is8Aligned(uint32_t n) { return (n & 7) == 0; }
static bool IsWordAligned(uintptr_t x) { return (x % sizeof(void*)) == 0; }
#endif
static uint32_t IndexOfLeastSignificantZeroBit(uint8_t n) {
for (uint32_t i = 0; i < 8; i++) {
if (((n >> i) & 1) == 0) {
return i;
}
}
MOZ_CRASH();
}
static uint32_t IndexOfLeastSignificantZero2Bits(uint8_t n) {
for (uint32_t i = 0; i < 8; i += 2) {
if (((n >> i) & 3) == 0) {
return i;
}
}
MOZ_CRASH();
}
static uint32_t IndexOfLeastSignificantZero4Bits(uint8_t n) {
for (uint32_t i = 0; i < 8; i += 4) {
if (((n >> i) & 0xF) == 0) {
return i;
}
}
MOZ_CRASH();
}
static uint32_t IndexOfMostSignificantOneBit(uint8_t n) {
for (int32_t i = 7; i >= 0; i--) {
if (((n >> i) & 1) == 1) {
return uint32_t(i);
}
}
MOZ_CRASH();
}
#ifdef DEBUG
static uint32_t OffsetToChunkNumber(uint32_t offset) { return offset / 8; }
#endif
uint32_t BitVector::hashNonZero() const {
mozilla::HashNumber hash(42);
for (uint8_t b : chunks_) {
if (b != 0) {
hash = mozilla::AddToHash(hash, b);
}
}
return uint32_t(hash);
}
uint32_t BitVector::totalOffset() const {
if (chunks_.empty()) {
return 0;
}
// Find the highest non-zero chunk.
size_t i;
for (i = chunks_.length(); i >= 1; i--) {
if (chunks_[i - 1] != 0) {
break;
}
}
if (i == 0) {
// There are chunks, but none got used.
return 0;
}
i--;
MOZ_ASSERT(i < chunks_.length());
return 8 * uint32_t(i) + IndexOfMostSignificantOneBit(chunks_[i]) + 1;
}
BitVector::Result BitVector::addMoreChunks() {
for (uint32_t i = 0; i < LookbackLimit / 2; i++) {
if (!chunks_.append(0)) {
return Result::OOM;
}
}
return Result::OK;
}
BitVector::Result BitVector::init(uint32_t chunksReserved,
uint32_t chunksTotal) {
MOZ_ASSERT_IF(chunksReserved > 0, chunksReserved < chunksTotal);
if (!chunks_.resize(chunksTotal)) {
return Result::OOM;
}
for (uint32_t i = 0; i < chunksReserved; i++) {
chunks_[i] = 0xFF;
}
for (uint32_t i = chunksReserved; i < chunksTotal; i++) {
chunks_[i] = 0;
}
return Result::OK;
}
BitVector::Result BitVector::allocate(uint32_t size, uint32_t firstChunk,
uint32_t lastChunkPlus1,
uint32_t* offset) {
MOZ_ASSERT(firstChunk < lastChunkPlus1);
MOZ_ASSERT(lastChunkPlus1 <= chunks_.length());
// We don't want to re-scan the entire vector every search; that's
// expensive (quadratic). Instead just re-scan the last 24 chunks and
// accept that we'll miss out on the opportunity to use alignment holes
// more than 192 bytes back from the current "fill point" for the struct.
if (lastChunkPlus1 - firstChunk > LookbackLimit) {
firstChunk = lastChunkPlus1 - LookbackLimit;
}
// These are arranged in order of conceptually-simplest first.
switch (size) {
case 8: {
// Any chunk that is zero will do.
for (uint32_t i = firstChunk; i < lastChunkPlus1; i++) {
if (chunks_[i] == 0) {
*offset = i * 8;
chunks_[i] = 0xFF;
return Result::OK;
}
}
break;
}
case 16: {
// Any chunk-pair that is zero will do. Note this 8-aligns 16-byte
// requests, but we can't avoid that because the underlying JS heap
// allocator only provides 8-aligned addresses anyway.
for (uint32_t i = firstChunk + 1; i < lastChunkPlus1; i++) {
if (chunks_[i - 1] == 0 && chunks_[i] == 0) {
*offset = (i - 1) * 8;
chunks_[i - 1] = 0xFF;
chunks_[i] = 0xFF;
return Result::OK;
}
}
break;
}
// The 4, 2 and 1-byte cases are the most complex. We have to find a
// single chunk with that many consecutive, aligned bits, as zero.
case 1: {
// Any chunk that has an unset bit is fine.
for (uint32_t i = firstChunk; i < lastChunkPlus1; i++) {
if (chunks_[i] != 0xFF) {
uint32_t bitShift = IndexOfLeastSignificantZeroBit(chunks_[i]);
*offset = i * 8 + bitShift;
chunks_[i] |= (1 << bitShift);
return Result::OK;
}
}
break;
}
case 4: {
// Find a chunk in which either the upper or lower half is zero.
for (uint32_t i = firstChunk; i < lastChunkPlus1; i++) {
if ((chunks_[i] & (0xF << 0)) == 0 || (chunks_[i] & (0xF << 4)) == 0) {
uint32_t bitShift = IndexOfLeastSignificantZero4Bits(chunks_[i]);
*offset = i * 8 + bitShift;
chunks_[i] |= (0x0F << bitShift);
return Result::OK;
}
}
break;
}
case 2: {
// Find a chunk in which an adjacent bit-pair is zero.
for (uint32_t i = firstChunk; i < lastChunkPlus1; i++) {
if ((chunks_[i] & (3 << 0)) == 0 || (chunks_[i] & (3 << 2)) == 0 ||
(chunks_[i] & (3 << 4)) == 0 || (chunks_[i] & (3 << 6)) == 0) {
uint32_t bitShift = IndexOfLeastSignificantZero2Bits(chunks_[i]);
*offset = i * 8 + bitShift;
chunks_[i] |= (3 << bitShift);
return Result::OK;
}
}
break;
}
default: {
MOZ_CRASH();
}
}
return Result::Fail;
}
// Given that `offset` was allocated by a call to `allocate`
// (requesting size `size`), free up that area.
void BitVector::deallocate(uint32_t offset, uint32_t size) {
MOZ_ASSERT(OffsetToChunkNumber(offset + size - 1) < chunks_.length());
switch (size) {
case 8: {
MOZ_ASSERT((offset % 8) == 0);
uint32_t chunk = offset / 8;
MOZ_ASSERT(chunks_[chunk] == 0xFF);
chunks_[chunk] = 0;
break;
}
case 16: {
MOZ_ASSERT((offset % 8) == 0); // re 8, see comment on ::allocate
uint32_t chunk = offset / 8;
MOZ_ASSERT(chunk + 1 < chunks_.length());
MOZ_ASSERT(chunks_[chunk] == 0xFF);
MOZ_ASSERT(chunks_[chunk + 1] == 0xFF);
chunks_[chunk] = 0;
chunks_[chunk + 1] = 0;
break;
}
case 1: {
uint32_t chunk = offset / 8;
uint32_t shift = offset % 8; // 0, 1, 2, 3, 4, 5, 6 or 7
uint8_t mask = 1 << shift;
MOZ_ASSERT((chunks_[chunk] & mask) == mask);
chunks_[chunk] &= ~mask;
break;
}
case 4: {
MOZ_ASSERT((offset % 4) == 0);
uint32_t chunk = offset / 8;
uint32_t shift = offset % 8; // 0 or 4
uint8_t mask = 0xF << shift;
MOZ_ASSERT((chunks_[chunk] & mask) == mask);
chunks_[chunk] &= ~mask;
break;
}
case 2: {
MOZ_ASSERT((offset % 2) == 0);
uint32_t chunk = offset / 8;
uint32_t shift = offset % 8; // 0, 2, 4 or 6
uint8_t mask = 0x3 << shift;
MOZ_ASSERT((chunks_[chunk] & mask) == mask);
chunks_[chunk] &= ~mask;
break;
}
default: {
MOZ_CRASH();
}
}
}
//=========================================================================
// FixedSizeBitVector
BitVector::Result FixedSizeBitVector::init(uint32_t layoutBytesReserved,
uint32_t layoutBytesTotal) {
MOZ_ASSERT(layoutBytesTotal > 0);
MOZ_ASSERT(layoutBytesReserved < layoutBytesTotal);
MOZ_ASSERT(Is8Aligned(layoutBytesReserved));
MOZ_ASSERT(Is8Aligned(layoutBytesTotal));
chunksReserved_ = layoutBytesReserved / 8;
chunksTotal_ = layoutBytesTotal / 8;
return BitVector::init(chunksReserved_, chunksTotal_);
}
BitVector::Result FixedSizeBitVector::allocate(uint32_t size,
uint32_t* offset) {
return BitVector::allocate(size, chunksReserved_, chunksTotal_, offset);
}
//=========================================================================
// VariableSizeBitVector
BitVector::Result VariableSizeBitVector::init() {
// This initial size of 1 is important in that it needs to be less than
// ::LookbackLimit.
return BitVector::init(0, 1 /*see ::unused()*/);
}
BitVector::Result VariableSizeBitVector::allocate(uint32_t size,
uint32_t* offset) {
// First, try to find it given the chunks we already have.
Result res = BitVector::allocate(size, 0, chunks_.length(), offset);
if (res == Result::OOM) {
return Result::OOM;
}
if (res == Result::OK) {
used_ = true;
return res;
}
// That failed, so add some more (uncommitted) chunks on the end of `chunks_`
// and try again. This second attempt *must* succeed since we can make the
// OOL block arbitrarily large.
res = addMoreChunks();
if (res == Result::OOM) {
return Result::OOM;
}
res = BitVector::allocate(size, 0, chunks_.length(), offset);
if (res == Result::OOM) {
return Result::OOM;
}
MOZ_RELEASE_ASSERT(res == Result::OK);
used_ = true;
return Result::OK;
}
bool VariableSizeBitVector::unused() const { return !used_; }
uint32_t VariableSizeBitVector::totalOffset() const {
uint32_t res = BitVector::totalOffset();
MOZ_ASSERT(used_ == (res > 0));
return res;
}
//=========================================================================
// StructLayout
bool StructLayout::init(uint32_t firstUsableILOffset, uint32_t usableILSize) {
// Not actually necessary, but it would be strange if this wasn't so.
MOZ_ASSERT(IsWordAligned(firstUsableILOffset));
MOZ_ASSERT(IsWordAligned(usableILSize));
// Must have at least enough space to hold the OOL pointer
MOZ_ASSERT(usableILSize >= sizeof(void*));
oolptrILO_ = InvalidOffset;
BitVector::Result res = ilBitVector_.init(firstUsableILOffset,
firstUsableILOffset + usableILSize);
if (res == BitVector::Result::OOM) {
return false;
}
res = oolBitVector_.init();
if (res == BitVector::Result::OOM) {
return false;
}
return true;
}
// Add a field of the specified size, and get back its access path. The two
// release assertions together guarantee that the maximum offset that could be
// generated is roughly `16 * js::wasm::MaxStructFields`, so there is no need
// to use checked integers in the layout computations.
bool StructLayout::addField(uint32_t fieldSize, FieldAccessPath* path) {
MOZ_ASSERT(fieldSize == 16 || fieldSize == 8 || fieldSize == 4 ||
fieldSize == 2 || fieldSize == 1);
// Guard against field-offset overflow.
numFieldsProcessed_++;
MOZ_RELEASE_ASSERT(numFieldsProcessed_ <= js::wasm::MaxStructFields);
MOZ_RELEASE_ASSERT(fieldSize <= 16);
*path = FieldAccessPath();
// This is complex. In between calls to ::addField, we maintain the
// following invariant:
//
// (0) If the OOL area is not in use, then it is possible to allocate the OOL
// pointer in the IL area.
//
// With that in place, the code below deals with 4 cases:
//
// (1) The OOL area is unused, and both the field and a dummy OOL pointer fit
// into the IL area. Allocate the field IL and leave the OOL area
// unused. Because we just established that a dummy OOL pointer fits in
// IL after the field, and because of (N) below, (0) is true after the
// call.
//
// (2) The OOL area is unused, but the field and dummy OOL pointer don't both
// fit in the IL area. We need to bring the OOL area into use. Allocate
// the OOL pointer in the IL area (which due to (0) cannot fail), and
// allocate the field in the OOL area. This is a one-time transitional
// case that separates multiple occurrences of (1) from multiple
// occurrences of (3) and (4). This means the OOL area is now in use, so
// (0) is trivially true after the call.
//
// (3) The OOL area is in use, but the field fits in the IL area anyways,
// presumably because it falls into an alignment hole in the IL area.
// Just allocate it IL and leave everything else unchanged. Since the
// OOL area is in use, (0) is trivially true after the call.
//
// (4) The OOL area is in use, and the field doesn't fit in the IL area.
// Allocate it in the OOL area. Since the OOL area is in use, (0) is
// trivially true after the call.
//
// (N) Note: for (1) and (2) it is important to try for the allocation of the
// field first and the dummy OOL pointer second.
// For cases (1) and (2) we need to back out tentative allocations. Hash the
// current state so we can later assert it is unchanged after backouts.
mozilla::DebugOnly<uint32_t> initialHash = hash();
// These need to agree.
MOZ_ASSERT(oolBitVector_.unused() == (oolptrILO_ == InvalidOffset));
// Try for Case (1)
if (oolBitVector_.unused()) {
uint32_t fieldOffset = InvalidOffset;
BitVector::Result res = ilBitVector_.allocate(fieldSize, &fieldOffset);
if (res == BitVector::Result::OOM) {
return false;
}
// The field fits, now try for the dummy OOL pointer
mozilla::DebugOnly<uint32_t> hash2 = hash();
if (res == BitVector::Result::OK) {
uint32_t dummyOffset = InvalidOffset;
res = ilBitVector_.allocate(sizeof(void*), &dummyOffset);
if (res == BitVector::Result::OOM) {
return false;
}
if (res == BitVector::Result::OK) {
// Case (1) established -- they both fit.
// Back out the dummy OOL pointer allocation, and we're done.
MOZ_ASSERT(fieldOffset != dummyOffset);
ilBitVector_.deallocate(dummyOffset, sizeof(void*));
MOZ_ASSERT(hash() == hash2);
*path = FieldAccessPath(fieldOffset);
return true;
}
// The field fits, but the OOL pointer doesn't. Back out the field
// allocation, so that we have changed nothing.
ilBitVector_.deallocate(fieldOffset, fieldSize);
}
}
// "state is unchanged from when we started"
MOZ_ASSERT(hash() == initialHash);
MOZ_ASSERT(oolBitVector_.unused() == (oolptrILO_ == InvalidOffset));
// Try for Case (2)
if (oolBitVector_.unused()) {
// We need to bring the OOL area into use. First, try to allocate the OOL
// pointer field. This must succeed (apart from OOMing) because of (1).
uint32_t oolptrOffset = InvalidOffset;
BitVector::Result res = ilBitVector_.allocate(sizeof(void*), &oolptrOffset);
if (res == BitVector::Result::OOM) {
return false;
}
MOZ_ASSERT(res == BitVector::Result::OK);
// Case (2) established
oolptrILO_ = oolptrOffset;
// Allocate the field in the OOL area; it is the first item there.
uint32_t fieldOffset = InvalidOffset;
res = oolBitVector_.allocate(fieldSize, &fieldOffset);
if (res == BitVector::Result::OOM) {
return false;
}
// Allocation in the OOL area can't fail.
MOZ_RELEASE_ASSERT(res == BitVector::Result::OK);
MOZ_ASSERT(!oolBitVector_.unused());
// We expect this because this is the first item in the OOL area.
MOZ_ASSERT(fieldOffset == 0);
*path = FieldAccessPath(oolptrILO_, fieldOffset);
return true;
}
// "state is unchanged from when we started"
MOZ_ASSERT(hash() == initialHash);
MOZ_ASSERT(!oolBitVector_.unused() && oolptrILO_ != InvalidOffset);
// Cases (3) and (4). In both cases, the OOL area is in use.
// Re-try allocating the field IL. Note this is not redundant w.r.t. the
// logic above, since that involved trying to allocate both the field and
// the dummy OOL pointer; this only tries to allocate the field.
uint32_t fieldOffset = InvalidOffset;
BitVector::Result res = ilBitVector_.allocate(fieldSize, &fieldOffset);
if (res == BitVector::Result::OOM) {
return false;
}
if (res == BitVector::Result::OK) {
// Case (3) established
*path = FieldAccessPath(fieldOffset);
return true;
}
// Case (4) established
fieldOffset = InvalidOffset;
res = oolBitVector_.allocate(fieldSize, &fieldOffset);
if (res == BitVector::Result::OOM) {
return false;
}
// Allocation in the OOL area can't fail.
MOZ_RELEASE_ASSERT(res == BitVector::Result::OK);
*path = FieldAccessPath(oolptrILO_, fieldOffset);
return true;
}
uint32_t StructLayout::hash() const {
uint32_t h = ilBitVector_.hashNonZero();
h = (h << 16) | (h >> 16);
h ^= oolBitVector_.hashNonZero();
return h;
}
uint32_t StructLayout::totalSizeIL() const {
return js::RoundUp(ilBitVector_.totalOffset(), sizeof(void*));
}
bool StructLayout::hasOOL() const { return !oolBitVector_.unused(); }
uint32_t StructLayout::totalSizeOOL() const {
MOZ_ASSERT(hasOOL());
MOZ_ASSERT(oolptrILO_ != InvalidOffset);
return js::RoundUp(oolBitVector_.totalOffset(), sizeof(void*));
}
FieldAccessPath StructLayout::oolPointerPath() const {
MOZ_ASSERT(hasOOL());
MOZ_ASSERT(oolptrILO_ != InvalidOffset);
return FieldAccessPath(oolptrILO_);
}
} // namespace js::wasm