1 // Copyright 2018 The Dawn Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "dawn_native/RingBufferAllocator.h" 16 17 // Note: Current RingBufferAllocator implementation uses two indices (start and end) to implement a 18 // circular queue. However, this approach defines a full queue when one element is still unused. 19 // 20 // For example, [E,E,E,E] would be equivelent to [U,U,U,U]. 21 // ^ ^ 22 // S=E=1 S=E=1 23 // 24 // The latter case is eliminated by counting used bytes >= capacity. This definition prevents 25 // (the last) byte and requires an extra variable to count used bytes. Alternatively, we could use 26 // only two indices that keep increasing (unbounded) but can be still indexed using bit masks. 27 // However, this 1) requires the size to always be a power-of-two and 2) remove tests that check 28 // used bytes. 29 namespace dawn_native { 30 RingBufferAllocator(uint64_t maxSize)31 RingBufferAllocator::RingBufferAllocator(uint64_t maxSize) : mMaxBlockSize(maxSize) { 32 } 33 Deallocate(ExecutionSerial lastCompletedSerial)34 void RingBufferAllocator::Deallocate(ExecutionSerial lastCompletedSerial) { 35 // Reclaim memory from previously recorded blocks. 36 for (Request& request : mInflightRequests.IterateUpTo(lastCompletedSerial)) { 37 mUsedStartOffset = request.endOffset; 38 mUsedSize -= request.size; 39 } 40 41 // Dequeue previously recorded requests. 42 mInflightRequests.ClearUpTo(lastCompletedSerial); 43 } 44 GetSize() const45 uint64_t RingBufferAllocator::GetSize() const { 46 return mMaxBlockSize; 47 } 48 GetUsedSize() const49 uint64_t RingBufferAllocator::GetUsedSize() const { 50 return mUsedSize; 51 } 52 Empty() const53 bool RingBufferAllocator::Empty() const { 54 return mInflightRequests.Empty(); 55 } 56 57 // Sub-allocate the ring-buffer by requesting a chunk of the specified size. 58 // This is a serial-based resource scheme, the life-span of resources (and the allocations) get 59 // tracked by GPU progress via serials. Memory can be reused by determining if the GPU has 60 // completed up to a given serial. Each sub-allocation request is tracked in the serial offset 61 // queue, which identifies an existing (or new) frames-worth of resources. Internally, the 62 // ring-buffer maintains offsets of 3 "memory" states: Free, Reclaimed, and Used. This is done 63 // in FIFO order as older frames would free resources before newer ones. Allocate(uint64_t allocationSize,ExecutionSerial serial)64 uint64_t RingBufferAllocator::Allocate(uint64_t allocationSize, ExecutionSerial serial) { 65 // Check if the buffer is full by comparing the used size. 66 // If the buffer is not split where waste occurs (e.g. cannot fit new sub-alloc in front), a 67 // subsequent sub-alloc could fail where the used size was previously adjusted to include 68 // the wasted. 69 if (mUsedSize >= mMaxBlockSize) { 70 return kInvalidOffset; 71 } 72 73 // Ensure adding allocationSize does not overflow. 74 const uint64_t remainingSize = (mMaxBlockSize - mUsedSize); 75 if (allocationSize > remainingSize) { 76 return kInvalidOffset; 77 } 78 79 uint64_t startOffset = kInvalidOffset; 80 81 // Check if the buffer is NOT split (i.e sub-alloc on ends) 82 if (mUsedStartOffset <= mUsedEndOffset) { 83 // Order is important (try to sub-alloc at end first). 84 // This is due to FIFO order where sub-allocs are inserted from left-to-right (when not 85 // wrapped). 86 if (mUsedEndOffset + allocationSize <= mMaxBlockSize) { 87 startOffset = mUsedEndOffset; 88 mUsedEndOffset += allocationSize; 89 mUsedSize += allocationSize; 90 mCurrentRequestSize += allocationSize; 91 } else if (allocationSize <= mUsedStartOffset) { // Try to sub-alloc at front. 92 // Count the space at the end so that a subsequent 93 // sub-alloc cannot not succeed when the buffer is full. 94 const uint64_t requestSize = (mMaxBlockSize - mUsedEndOffset) + allocationSize; 95 96 startOffset = 0; 97 mUsedEndOffset = allocationSize; 98 mUsedSize += requestSize; 99 mCurrentRequestSize += requestSize; 100 } 101 } else if (mUsedEndOffset + allocationSize <= 102 mUsedStartOffset) { // Otherwise, buffer is split where sub-alloc must be 103 // in-between. 104 startOffset = mUsedEndOffset; 105 mUsedEndOffset += allocationSize; 106 mUsedSize += allocationSize; 107 mCurrentRequestSize += allocationSize; 108 } 109 110 if (startOffset != kInvalidOffset) { 111 Request request; 112 request.endOffset = mUsedEndOffset; 113 request.size = mCurrentRequestSize; 114 115 mInflightRequests.Enqueue(std::move(request), serial); 116 mCurrentRequestSize = 0; // reset 117 } 118 119 return startOffset; 120 } 121 } // namespace dawn_native 122