fenced_allocator.cc revision c2e0dbddbe15c98d52c4786dac06cb8952a8ae6d
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) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../client/fenced_allocator.h" 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "../client/cmd_buffer_helper.h" 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace gpu { 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 13c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace { 14c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 15c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Allocation alignment, must be a power of two. 16c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)const unsigned int kAllocAlignment = 16; 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 18c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Round down to the largest multiple of kAllocAlignment no greater than |size|. 19c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)unsigned int RoundDown(unsigned int size) { 20c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return size & ~(kAllocAlignment - 1); 21c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 22c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 23c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Round up to the smallest multiple of kAllocAlignment no smaller than |size|. 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)unsigned int RoundUp(unsigned int size) { 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return (size + (kAllocAlignment - 1)) & ~(kAllocAlignment - 1); 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 27c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 28c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} // namespace 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef _MSC_VER 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const FencedAllocator::Offset FencedAllocator::kInvalidOffset; 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::FencedAllocator(unsigned int size, 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CommandBufferHelper *helper) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : helper_(helper) { 37c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Block block = { FREE, 0, RoundDown(size), kUnusedToken }; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.push_back(block); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::~FencedAllocator() { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Free blocks pending tokens. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].state == FREE_PENDING_TOKEN) { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = WaitForTokenAndFreeBlock(i); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // These checks are not valid if the service has crashed or lost the context. 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // GPU_DCHECK_EQ(blocks_.size(), 1u); 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // GPU_DCHECK_EQ(blocks_[0].state, FREE); 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for a non-allocated block that is big enough. Search in the FREE 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// blocks first (for direct usage), first-fit, then in the FREE_PENDING_TOKEN 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// blocks, waiting for them. The current implementation isn't smart about 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// optimizing what to wait for, just looks inside the block in order (first-fit 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// as well). 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::Offset FencedAllocator::Alloc(unsigned int size) { 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // size of 0 is not allowed because it would be inconsistent to only sometimes 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // have it succeed. Example: Alloc(SizeOfBuffer), Alloc(0). 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (size == 0) { 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return kInvalidOffset; 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 65c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Round up the allocation size to ensure alignment. 66c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) size = RoundUp(size); 67c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Try first to allocate in a free block. 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == FREE && block.size >= size) { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return AllocInBlock(i, size); 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No free block is available. Look for blocks pending tokens, and wait for 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // them to be re-usable. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].state != FREE_PENDING_TOKEN) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = WaitForTokenAndFreeBlock(i); 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].size >= size) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return AllocInBlock(i, size); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return kInvalidOffset; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for the corresponding block, mark it FREE, and collapse it if 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// necessary. 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::Free(FencedAllocator::Offset offset) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index = GetBlockByOffset(offset); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GPU_DCHECK_NE(blocks_[index].state, FREE); 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_[index].state = FREE; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CollapseFreeBlock(index); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for the corresponding block, mark it FREE_PENDING_TOKEN. 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::FreePendingToken( 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FencedAllocator::Offset offset, int32 token) { 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index = GetBlockByOffset(offset); 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE_PENDING_TOKEN; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.token = token; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Gets the max of the size of the blocks marked as free. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)unsigned int FencedAllocator::GetLargestFreeSize() { 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FreeUnused(); 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int max_size = 0; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == FREE) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size = std::max(max_size, block.size); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return max_size; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Gets the size of the largest segment of blocks that are either FREE or 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FREE_PENDING_TOKEN. 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)unsigned int FencedAllocator::GetLargestFreeOrPendingSize() { 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int max_size = 0; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int current_size = 0; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == IN_USE) { 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size = std::max(max_size, current_size); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_size = 0; 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GPU_DCHECK(block.state == FREE || block.state == FREE_PENDING_TOKEN); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_size += block.size; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return std::max(max_size, current_size); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Makes sure that: 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - there is at least one block. 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - there are no contiguous FREE blocks (they should have been collapsed). 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - the successive offsets match the block sizes, and they are in order. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool FencedAllocator::CheckConsistency() { 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_.size() < 1) return false; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size() - 1; ++i) { 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block ¤t = blocks_[i]; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &next = blocks_[i + 1]; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This test is NOT included in the next one, because offset is unsigned. 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.offset <= current.offset) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.offset != current.offset + current.size) 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (current.state == FREE && next.state == FREE) 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool FencedAllocator::InUse() { 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return blocks_.size() != 1 || blocks_[0].state != FREE; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Collapse the block to the next one, then to the previous one. Provided the 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// structure is consistent, those are the only blocks eligible for collapse. 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::CollapseFreeBlock( 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index) { 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index + 1 < blocks_.size()) { 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &next = blocks_[index + 1]; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.state == FREE) { 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_[index].size += next.size; 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.erase(blocks_.begin() + index + 1); 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index > 0) { 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &prev = blocks_[index - 1]; 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (prev.state == FREE) { 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev.size += blocks_[index].size; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.erase(blocks_.begin() + index); 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --index; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return index; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Waits for the block's token, then mark the block as free, then collapse it. 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::WaitForTokenAndFreeBlock( 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index) { 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GPU_DCHECK_EQ(block.state, FREE_PENDING_TOKEN); 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) helper_->WaitForToken(block.token); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE; 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CollapseFreeBlock(index); 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Frees any blocks pending a token for which the token has been read. 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::FreeUnused() { 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 last_token_read = helper_->last_token_read(); 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size();) { 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block& block = blocks_[i]; 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == FREE_PENDING_TOKEN && block.token <= last_token_read) { 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE; 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = CollapseFreeBlock(i); 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++i; 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If the block is exactly the requested size, simply mark it IN_USE, otherwise 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// split it and mark the first one (of the requested size) IN_USE. 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::Offset FencedAllocator::AllocInBlock(BlockIndex index, 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int size) { 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GPU_DCHECK_GE(block.size, size); 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GPU_DCHECK_EQ(block.state, FREE); 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Offset offset = block.offset; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.size == size) { 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = IN_USE; 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return offset; 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block newblock = { FREE, offset + size, block.size - size, kUnusedToken}; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = IN_USE; 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.size = size; 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this is the last thing being done because it may invalidate block; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.insert(blocks_.begin() + index + 1, newblock); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return offset; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The blocks are in offset order, so we can do a binary search. 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::GetBlockByOffset(Offset offset) { 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block templ = { IN_USE, offset, 0, kUnusedToken }; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Container::iterator it = std::lower_bound(blocks_.begin(), blocks_.end(), 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) templ, OffsetCmp()); 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GPU_DCHECK(it != blocks_.end() && it->offset == offset); 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return it-blocks_.begin(); 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace gpu 236