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