1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // This file contains the implementation of the FencedAllocator class.
6
7 #include "gpu/command_buffer/client/fenced_allocator.h"
8
9 #include <stdint.h>
10
11 #include <algorithm>
12
13 #include "gpu/command_buffer/client/cmd_buffer_helper.h"
14
15 namespace gpu {
16
17 namespace {
18
19 // Round down to the largest multiple of kAllocAlignment no greater than |size|.
RoundDown(uint32_t size)20 uint32_t RoundDown(uint32_t size) {
21 return size & ~(FencedAllocator::kAllocAlignment - 1);
22 }
23
24 // Round up to the smallest multiple of kAllocAlignment no smaller than |size|.
RoundUp(uint32_t size)25 base::CheckedNumeric<uint32_t> RoundUp(uint32_t size) {
26 return (base::CheckedNumeric<uint32_t>(size) +
27 (FencedAllocator::kAllocAlignment - 1)) &
28 ~(FencedAllocator::kAllocAlignment - 1);
29 }
30
31 } // namespace
32
FencedAllocator(uint32_t size,CommandBufferHelper * helper)33 FencedAllocator::FencedAllocator(uint32_t size, CommandBufferHelper* helper)
34 : helper_(helper), bytes_in_use_(0) {
35 Block block = { FREE, 0, RoundDown(size), kUnusedToken };
36 blocks_.push_back(block);
37 }
38
~FencedAllocator()39 FencedAllocator::~FencedAllocator() {
40 // All IN_USE blocks should be released at this point. There may still be
41 // FREE_PENDING_TOKEN blocks, the assumption is that the underlying memory
42 // will not be re-used without higher level synchronization.
43 DCHECK_EQ(bytes_in_use_, 0u);
44 }
45
46 // Looks for a non-allocated block that is big enough. Search in the FREE
47 // blocks first (for direct usage), first-fit, then in the FREE_PENDING_TOKEN
48 // blocks, waiting for them. The current implementation isn't smart about
49 // optimizing what to wait for, just looks inside the block in order (first-fit
50 // as well).
Alloc(uint32_t size)51 FencedAllocator::Offset FencedAllocator::Alloc(uint32_t size) {
52 // size of 0 is not allowed because it would be inconsistent to only sometimes
53 // have it succeed. Example: Alloc(SizeOfBuffer), Alloc(0).
54 if (size == 0) {
55 return kInvalidOffset;
56 }
57
58 // Round up the allocation size to ensure alignment.
59 uint32_t aligned_size = 0;
60 if (!RoundUp(size).AssignIfValid(&aligned_size)) {
61 return kInvalidOffset;
62 }
63
64 // Try first to allocate in a free block.
65 for (uint32_t i = 0; i < blocks_.size(); ++i) {
66 Block &block = blocks_[i];
67 if (block.state == FREE && block.size >= aligned_size) {
68 return AllocInBlock(i, aligned_size);
69 }
70 }
71
72 // No free block is available. Look for blocks pending tokens, and wait for
73 // them to be re-usable.
74 for (uint32_t i = 0; i < blocks_.size(); ++i) {
75 if (blocks_[i].state != FREE_PENDING_TOKEN)
76 continue;
77 i = WaitForTokenAndFreeBlock(i);
78 if (blocks_[i].size >= aligned_size)
79 return AllocInBlock(i, aligned_size);
80 }
81 return kInvalidOffset;
82 }
83
84 // Looks for the corresponding block, mark it FREE, and collapse it if
85 // necessary.
Free(FencedAllocator::Offset offset)86 void FencedAllocator::Free(FencedAllocator::Offset offset) {
87 BlockIndex index = GetBlockByOffset(offset);
88 Block &block = blocks_[index];
89 DCHECK_NE(block.state, FREE);
90 DCHECK_EQ(block.offset, offset);
91
92 if (block.state == IN_USE)
93 bytes_in_use_ -= block.size;
94
95 block.state = FREE;
96 CollapseFreeBlock(index);
97 }
98
99 // Looks for the corresponding block, mark it FREE_PENDING_TOKEN.
FreePendingToken(FencedAllocator::Offset offset,int32_t token)100 void FencedAllocator::FreePendingToken(FencedAllocator::Offset offset,
101 int32_t token) {
102 BlockIndex index = GetBlockByOffset(offset);
103 Block &block = blocks_[index];
104 DCHECK_EQ(block.offset, offset);
105 if (block.state == IN_USE)
106 bytes_in_use_ -= block.size;
107 block.state = FREE_PENDING_TOKEN;
108 block.token = token;
109 }
110
111 // Gets the max of the size of the blocks marked as free.
GetLargestFreeSize()112 uint32_t FencedAllocator::GetLargestFreeSize() {
113 FreeUnused();
114 uint32_t max_size = 0;
115 for (uint32_t i = 0; i < blocks_.size(); ++i) {
116 Block &block = blocks_[i];
117 if (block.state == FREE)
118 max_size = std::max(max_size, block.size);
119 }
120 return max_size;
121 }
122
123 // Gets the size of the largest segment of blocks that are either FREE or
124 // FREE_PENDING_TOKEN.
GetLargestFreeOrPendingSize()125 uint32_t FencedAllocator::GetLargestFreeOrPendingSize() {
126 uint32_t max_size = 0;
127 uint32_t current_size = 0;
128 for (uint32_t i = 0; i < blocks_.size(); ++i) {
129 Block &block = blocks_[i];
130 if (block.state == IN_USE) {
131 max_size = std::max(max_size, current_size);
132 current_size = 0;
133 } else {
134 DCHECK(block.state == FREE || block.state == FREE_PENDING_TOKEN);
135 current_size += block.size;
136 }
137 }
138 return std::max(max_size, current_size);
139 }
140
141 // Gets the total size of all blocks marked as free.
GetFreeSize()142 uint32_t FencedAllocator::GetFreeSize() {
143 FreeUnused();
144 uint32_t size = 0;
145 for (uint32_t i = 0; i < blocks_.size(); ++i) {
146 Block& block = blocks_[i];
147 if (block.state == FREE)
148 size += block.size;
149 }
150 return size;
151 }
152
153 // Makes sure that:
154 // - there is at least one block.
155 // - there are no contiguous FREE blocks (they should have been collapsed).
156 // - the successive offsets match the block sizes, and they are in order.
CheckConsistency()157 bool FencedAllocator::CheckConsistency() {
158 if (blocks_.size() < 1) return false;
159 for (uint32_t i = 0; i < blocks_.size() - 1; ++i) {
160 Block ¤t = blocks_[i];
161 Block &next = blocks_[i + 1];
162 // This test is NOT included in the next one, because offset is unsigned.
163 if (next.offset <= current.offset)
164 return false;
165 if (next.offset != current.offset + current.size)
166 return false;
167 if (current.state == FREE && next.state == FREE)
168 return false;
169 }
170 return true;
171 }
172
173 // Returns false if all blocks are actually FREE, in which
174 // case they would be coalesced into one block, true otherwise.
InUseOrFreePending()175 bool FencedAllocator::InUseOrFreePending() {
176 return blocks_.size() != 1 || blocks_[0].state != FREE;
177 }
178
GetBlockStatusForTest(Offset offset,int32_t * token_if_pending)179 FencedAllocator::State FencedAllocator::GetBlockStatusForTest(
180 Offset offset,
181 int32_t* token_if_pending) {
182 BlockIndex index = GetBlockByOffset(offset);
183 Block& block = blocks_[index];
184 if ((block.state == FREE_PENDING_TOKEN) && token_if_pending)
185 *token_if_pending = block.token;
186 return block.state;
187 }
188
189 // Collapse the block to the next one, then to the previous one. Provided the
190 // structure is consistent, those are the only blocks eligible for collapse.
CollapseFreeBlock(BlockIndex index)191 FencedAllocator::BlockIndex FencedAllocator::CollapseFreeBlock(
192 BlockIndex index) {
193 if (index + 1 < blocks_.size()) {
194 Block &next = blocks_[index + 1];
195 if (next.state == FREE) {
196 blocks_[index].size += next.size;
197 blocks_.erase(blocks_.begin() + index + 1);
198 }
199 }
200 if (index > 0) {
201 Block &prev = blocks_[index - 1];
202 if (prev.state == FREE) {
203 prev.size += blocks_[index].size;
204 blocks_.erase(blocks_.begin() + index);
205 --index;
206 }
207 }
208 return index;
209 }
210
211 // Waits for the block's token, then mark the block as free, then collapse it.
WaitForTokenAndFreeBlock(BlockIndex index)212 FencedAllocator::BlockIndex FencedAllocator::WaitForTokenAndFreeBlock(
213 BlockIndex index) {
214 Block &block = blocks_[index];
215 DCHECK_EQ(block.state, FREE_PENDING_TOKEN);
216 helper_->WaitForToken(block.token);
217 block.state = FREE;
218 return CollapseFreeBlock(index);
219 }
220
221 // Frees any blocks pending a token for which the token has been read.
FreeUnused()222 void FencedAllocator::FreeUnused() {
223 helper_->RefreshCachedToken();
224 for (uint32_t i = 0; i < blocks_.size();) {
225 Block& block = blocks_[i];
226 if (block.state == FREE_PENDING_TOKEN &&
227 helper_->HasCachedTokenPassed(block.token)) {
228 block.state = FREE;
229 i = CollapseFreeBlock(i);
230 } else {
231 ++i;
232 }
233 }
234 }
235
236 // If the block is exactly the requested size, simply mark it IN_USE, otherwise
237 // split it and mark the first one (of the requested size) IN_USE.
AllocInBlock(BlockIndex index,uint32_t size)238 FencedAllocator::Offset FencedAllocator::AllocInBlock(BlockIndex index,
239 uint32_t size) {
240 Block &block = blocks_[index];
241 DCHECK_GE(block.size, size);
242 DCHECK_EQ(block.state, FREE);
243 Offset offset = block.offset;
244 bytes_in_use_ += size;
245 if (block.size == size) {
246 block.state = IN_USE;
247 return offset;
248 }
249 Block newblock = { FREE, offset + size, block.size - size, kUnusedToken};
250 block.state = IN_USE;
251 block.size = size;
252 // this is the last thing being done because it may invalidate block;
253 blocks_.insert(blocks_.begin() + index + 1, newblock);
254 return offset;
255 }
256
257 // The blocks are in offset order, so we can do a binary search.
GetBlockByOffset(Offset offset)258 FencedAllocator::BlockIndex FencedAllocator::GetBlockByOffset(Offset offset) {
259 Block templ = { IN_USE, offset, 0, kUnusedToken };
260 Container::iterator it = std::lower_bound(blocks_.begin(), blocks_.end(),
261 templ, OffsetCmp());
262 DCHECK(it != blocks_.end());
263 return it-blocks_.begin();
264 }
265
266 } // namespace gpu
267