gpu/command_buffer/client/fenced_allocator.cc

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