blob: 1ca1ffbb14fdc830e6dd0bb6efb9d59ec396fbd3 [file] [log] [blame] [edit]
// Copyright 2018 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "dawn/native/RingBufferAllocator.h"
#include <utility>
#include "dawn/common/Math.h"
// Note: Current RingBufferAllocator implementation uses two indices (start and end) to implement a
// circular queue. However, this approach defines a full queue when one element is still unused.
//
// For example, [E,E,E,E] would be equivelent to [U,U,U,U].
// ^ ^
// S=E=1 S=E=1
//
// The latter case is eliminated by counting used bytes >= capacity. This definition prevents
// (the last) byte and requires an extra variable to count used bytes. Alternatively, we could use
// only two indices that keep increasing (unbounded) but can be still indexed using bit masks.
// However, this 1) requires the size to always be a power-of-two and 2) remove tests that check
// used bytes.
namespace dawn::native {
RingBufferAllocator::RingBufferAllocator() = default;
RingBufferAllocator::RingBufferAllocator(uint64_t maxSize) : mMaxBlockSize(maxSize) {}
RingBufferAllocator::RingBufferAllocator(const RingBufferAllocator&) = default;
RingBufferAllocator::~RingBufferAllocator() = default;
RingBufferAllocator& RingBufferAllocator::operator=(const RingBufferAllocator&) = default;
void RingBufferAllocator::Deallocate(ExecutionSerial lastCompletedSerial) {
// Reclaim memory from previously recorded blocks.
for (Request& request : mInflightRequests.IterateUpTo(lastCompletedSerial)) {
mUsedStartOffset = request.endOffset;
mUsedSize -= request.size;
}
// Dequeue previously recorded requests.
mInflightRequests.ClearUpTo(lastCompletedSerial);
}
uint64_t RingBufferAllocator::GetSize() const {
return mMaxBlockSize;
}
uint64_t RingBufferAllocator::GetUsedSize() const {
return mUsedSize;
}
bool RingBufferAllocator::Empty() const {
return mInflightRequests.Empty();
}
// Sub-allocate the ring-buffer by requesting a chunk of the specified size.
// This is a serial-based resource scheme, the life-span of resources (and the allocations) get
// tracked by GPU progress via serials. Memory can be reused by determining if the GPU has
// completed up to a given serial. Each sub-allocation request is tracked in the serial offset
// queue, which identifies an existing (or new) frames-worth of resources. Internally, the
// ring-buffer maintains offsets of 3 "memory" states: Free, Reclaimed, and Used. This is done
// in FIFO order as older frames would free resources before newer ones.
uint64_t RingBufferAllocator::Allocate(uint64_t allocationSize,
ExecutionSerial serial,
uint64_t offsetAlignment) {
// Check if the buffer is full by comparing the used size.
// If the buffer is not split where waste occurs (e.g. cannot fit new sub-alloc in front), a
// subsequent sub-alloc could fail where the used size was previously adjusted to include
// the wasted.
if (mUsedSize >= mMaxBlockSize) {
return kInvalidOffset;
}
// Ensure adding allocationSize does not overflow.
const uint64_t remainingSize = (mMaxBlockSize - mUsedSize);
if (allocationSize > remainingSize) {
return kInvalidOffset;
}
uint64_t startOffset = kInvalidOffset;
uint64_t currentRequestSize = 0u;
// Compute an alignment offset for the buffer if allocating at the end.
const uint64_t alignmentOffset = Align(mUsedEndOffset, offsetAlignment) - mUsedEndOffset;
const uint64_t alignedUsedEndOffset = mUsedEndOffset + alignmentOffset;
// Check if the buffer is NOT split (i.e sub-alloc on ends)
if (mUsedStartOffset <= mUsedEndOffset) {
// Order is important (try to sub-alloc at end first).
// This is due to FIFO order where sub-allocs are inserted from left-to-right (when not
// wrapped).
if (alignedUsedEndOffset + allocationSize <= mMaxBlockSize) {
startOffset = alignedUsedEndOffset;
mUsedSize += allocationSize + alignmentOffset;
currentRequestSize = allocationSize + alignmentOffset;
} else if (allocationSize <= mUsedStartOffset) { // Try to sub-alloc at front.
// Count the space at the end so that a subsequent
// sub-alloc cannot fail when the buffer is full.
const uint64_t requestSize = (mMaxBlockSize - mUsedEndOffset) + allocationSize;
startOffset = 0;
mUsedSize += requestSize;
currentRequestSize = requestSize;
}
} else if (alignedUsedEndOffset + allocationSize <= mUsedStartOffset) {
// Otherwise, buffer is split where sub-alloc must be in-between.
startOffset = alignedUsedEndOffset;
mUsedSize += allocationSize + alignmentOffset;
currentRequestSize = allocationSize + alignmentOffset;
}
if (startOffset != kInvalidOffset) {
mUsedEndOffset = startOffset + allocationSize;
Request request;
request.endOffset = mUsedEndOffset;
request.size = currentRequestSize;
mInflightRequests.Enqueue(std::move(request), serial);
}
return startOffset;
}
} // namespace dawn::native