15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file contains the implementation of the FencedAllocator class. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "gpu/command_buffer/client/fenced_allocator.h" 83551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 103551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "gpu/command_buffer/client/cmd_buffer_helper.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace gpu { 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 15c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace { 16c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Allocation alignment, must be a power of two. 18c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)const unsigned int kAllocAlignment = 16; 19c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 20c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Round down to the largest multiple of kAllocAlignment no greater than |size|. 21c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)unsigned int RoundDown(unsigned int size) { 22c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return size & ~(kAllocAlignment - 1); 23c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Round up to the smallest multiple of kAllocAlignment no smaller than |size|. 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)unsigned int RoundUp(unsigned int size) { 27c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return (size + (kAllocAlignment - 1)) & ~(kAllocAlignment - 1); 28c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 30c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} // namespace 31c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef _MSC_VER 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const FencedAllocator::Offset FencedAllocator::kInvalidOffset; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::FencedAllocator(unsigned int size, 374ad1aa43a48567659193a298fad74f55e00b3dd9Ben Murdoch CommandBufferHelper* helper, 384ad1aa43a48567659193a298fad74f55e00b3dd9Ben Murdoch const base::Closure& poll_callback) 393551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) : helper_(helper), 404ad1aa43a48567659193a298fad74f55e00b3dd9Ben Murdoch poll_callback_(poll_callback), 413551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bytes_in_use_(0) { 42c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Block block = { FREE, 0, RoundDown(size), kUnusedToken }; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.push_back(block); 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::~FencedAllocator() { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Free blocks pending tokens. 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].state == FREE_PENDING_TOKEN) { 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = WaitForTokenAndFreeBlock(i); 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 53cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 54cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) DCHECK_EQ(blocks_.size(), 1u); 55cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) DCHECK_EQ(blocks_[0].state, FREE); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for a non-allocated block that is big enough. Search in the FREE 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// blocks first (for direct usage), first-fit, then in the FREE_PENDING_TOKEN 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// blocks, waiting for them. The current implementation isn't smart about 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// optimizing what to wait for, just looks inside the block in order (first-fit 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// as well). 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::Offset FencedAllocator::Alloc(unsigned int size) { 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // size of 0 is not allowed because it would be inconsistent to only sometimes 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // have it succeed. Example: Alloc(SizeOfBuffer), Alloc(0). 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (size == 0) { 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return kInvalidOffset; 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 70c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Round up the allocation size to ensure alignment. 71c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) size = RoundUp(size); 72c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Try first to allocate in a free block. 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == FREE && block.size >= size) { 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return AllocInBlock(i, size); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No free block is available. Look for blocks pending tokens, and wait for 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // them to be re-usable. 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].state != FREE_PENDING_TOKEN) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = WaitForTokenAndFreeBlock(i); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].size >= size) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return AllocInBlock(i, size); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return kInvalidOffset; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for the corresponding block, mark it FREE, and collapse it if 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// necessary. 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::Free(FencedAllocator::Offset offset) { 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index = GetBlockByOffset(offset); 97f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK_NE(blocks_[index].state, FREE); 983551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Block &block = blocks_[index]; 993551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1003551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (block.state == IN_USE) 1013551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bytes_in_use_ -= block.size; 1023551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1033551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) block.state = FREE; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CollapseFreeBlock(index); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for the corresponding block, mark it FREE_PENDING_TOKEN. 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::FreePendingToken( 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FencedAllocator::Offset offset, int32 token) { 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index = GetBlockByOffset(offset); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 1123551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (block.state == IN_USE) 1133551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bytes_in_use_ -= block.size; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE_PENDING_TOKEN; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.token = token; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Gets the max of the size of the blocks marked as free. 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)unsigned int FencedAllocator::GetLargestFreeSize() { 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FreeUnused(); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int max_size = 0; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == FREE) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size = std::max(max_size, block.size); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return max_size; 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Gets the size of the largest segment of blocks that are either FREE or 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FREE_PENDING_TOKEN. 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)unsigned int FencedAllocator::GetLargestFreeOrPendingSize() { 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int max_size = 0; 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int current_size = 0; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == IN_USE) { 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size = std::max(max_size, current_size); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_size = 0; 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 141f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK(block.state == FREE || block.state == FREE_PENDING_TOKEN); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_size += block.size; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return std::max(max_size, current_size); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Makes sure that: 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - there is at least one block. 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - there are no contiguous FREE blocks (they should have been collapsed). 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - the successive offsets match the block sizes, and they are in order. 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool FencedAllocator::CheckConsistency() { 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_.size() < 1) return false; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size() - 1; ++i) { 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block ¤t = blocks_[i]; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &next = blocks_[i + 1]; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This test is NOT included in the next one, because offset is unsigned. 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.offset <= current.offset) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.offset != current.offset + current.size) 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (current.state == FREE && next.state == FREE) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1683551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// Returns false if all blocks are actually FREE, in which 1693551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// case they would be coalesced into one block, true otherwise. 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool FencedAllocator::InUse() { 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return blocks_.size() != 1 || blocks_[0].state != FREE; 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Collapse the block to the next one, then to the previous one. Provided the 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// structure is consistent, those are the only blocks eligible for collapse. 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::CollapseFreeBlock( 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index) { 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index + 1 < blocks_.size()) { 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &next = blocks_[index + 1]; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.state == FREE) { 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_[index].size += next.size; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.erase(blocks_.begin() + index + 1); 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index > 0) { 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &prev = blocks_[index - 1]; 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (prev.state == FREE) { 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev.size += blocks_[index].size; 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.erase(blocks_.begin() + index); 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --index; 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return index; 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Waits for the block's token, then mark the block as free, then collapse it. 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::WaitForTokenAndFreeBlock( 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index) { 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 200f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK_EQ(block.state, FREE_PENDING_TOKEN); 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) helper_->WaitForToken(block.token); 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE; 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CollapseFreeBlock(index); 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Frees any blocks pending a token for which the token has been read. 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::FreeUnused() { 2084ad1aa43a48567659193a298fad74f55e00b3dd9Ben Murdoch // Free any potential blocks that has its lifetime handled outside. 2094ad1aa43a48567659193a298fad74f55e00b3dd9Ben Murdoch poll_callback_.Run(); 2104ad1aa43a48567659193a298fad74f55e00b3dd9Ben Murdoch 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size();) { 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block& block = blocks_[i]; 2134ad1aa43a48567659193a298fad74f55e00b3dd9Ben Murdoch if (block.state == FREE_PENDING_TOKEN && 2144ad1aa43a48567659193a298fad74f55e00b3dd9Ben Murdoch helper_->HasTokenPassed(block.token)) { 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE; 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = CollapseFreeBlock(i); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++i; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If the block is exactly the requested size, simply mark it IN_USE, otherwise 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// split it and mark the first one (of the requested size) IN_USE. 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::Offset FencedAllocator::AllocInBlock(BlockIndex index, 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int size) { 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 228f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK_GE(block.size, size); 229f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK_EQ(block.state, FREE); 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Offset offset = block.offset; 2313551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bytes_in_use_ += size; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.size == size) { 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = IN_USE; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return offset; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block newblock = { FREE, offset + size, block.size - size, kUnusedToken}; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = IN_USE; 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.size = size; 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this is the last thing being done because it may invalidate block; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.insert(blocks_.begin() + index + 1, newblock); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return offset; 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The blocks are in offset order, so we can do a binary search. 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::GetBlockByOffset(Offset offset) { 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block templ = { IN_USE, offset, 0, kUnusedToken }; 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Container::iterator it = std::lower_bound(blocks_.begin(), blocks_.end(), 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) templ, OffsetCmp()); 249f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK(it != blocks_.end() && it->offset == offset); 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return it-blocks_.begin(); 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace gpu 254