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, 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CommandBufferHelper *helper) 383551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) : helper_(helper), 393551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bytes_in_use_(0) { 40c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Block block = { FREE, 0, RoundDown(size), kUnusedToken }; 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.push_back(block); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::~FencedAllocator() { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Free blocks pending tokens. 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].state == FREE_PENDING_TOKEN) { 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = WaitForTokenAndFreeBlock(i); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // These checks are not valid if the service has crashed or lost the context. 52f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // DCHECK_EQ(blocks_.size(), 1u); 53f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // DCHECK_EQ(blocks_[0].state, FREE); 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for a non-allocated block that is big enough. Search in the FREE 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// blocks first (for direct usage), first-fit, then in the FREE_PENDING_TOKEN 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// blocks, waiting for them. The current implementation isn't smart about 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// optimizing what to wait for, just looks inside the block in order (first-fit 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// as well). 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::Offset FencedAllocator::Alloc(unsigned int size) { 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // size of 0 is not allowed because it would be inconsistent to only sometimes 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // have it succeed. Example: Alloc(SizeOfBuffer), Alloc(0). 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (size == 0) { 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return kInvalidOffset; 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 68c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Round up the allocation size to ensure alignment. 69c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) size = RoundUp(size); 70c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Try first to allocate in a free block. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == FREE && block.size >= size) { 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return AllocInBlock(i, size); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No free block is available. Look for blocks pending tokens, and wait for 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // them to be re-usable. 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].state != FREE_PENDING_TOKEN) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = WaitForTokenAndFreeBlock(i); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_[i].size >= size) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return AllocInBlock(i, size); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return kInvalidOffset; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for the corresponding block, mark it FREE, and collapse it if 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// necessary. 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::Free(FencedAllocator::Offset offset) { 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index = GetBlockByOffset(offset); 95f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK_NE(blocks_[index].state, FREE); 963551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Block &block = blocks_[index]; 973551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 983551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (block.state == IN_USE) 993551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bytes_in_use_ -= block.size; 1003551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1013551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) block.state = FREE; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CollapseFreeBlock(index); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Looks for the corresponding block, mark it FREE_PENDING_TOKEN. 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::FreePendingToken( 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FencedAllocator::Offset offset, int32 token) { 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index = GetBlockByOffset(offset); 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 1103551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (block.state == IN_USE) 1113551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bytes_in_use_ -= block.size; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE_PENDING_TOKEN; 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.token = token; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Gets the max of the size of the blocks marked as free. 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)unsigned int FencedAllocator::GetLargestFreeSize() { 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FreeUnused(); 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int max_size = 0; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == FREE) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size = std::max(max_size, block.size); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return max_size; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Gets the size of the largest segment of blocks that are either FREE or 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FREE_PENDING_TOKEN. 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)unsigned int FencedAllocator::GetLargestFreeOrPendingSize() { 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int max_size = 0; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int current_size = 0; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size(); ++i) { 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[i]; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == IN_USE) { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size = std::max(max_size, current_size); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_size = 0; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 139f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK(block.state == FREE || block.state == FREE_PENDING_TOKEN); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_size += block.size; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return std::max(max_size, current_size); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Makes sure that: 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - there is at least one block. 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - there are no contiguous FREE blocks (they should have been collapsed). 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - the successive offsets match the block sizes, and they are in order. 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool FencedAllocator::CheckConsistency() { 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (blocks_.size() < 1) return false; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size() - 1; ++i) { 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block ¤t = blocks_[i]; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &next = blocks_[i + 1]; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This test is NOT included in the next one, because offset is unsigned. 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.offset <= current.offset) 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.offset != current.offset + current.size) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (current.state == FREE && next.state == FREE) 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1663551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// Returns false if all blocks are actually FREE, in which 1673551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// case they would be coalesced into one block, true otherwise. 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool FencedAllocator::InUse() { 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return blocks_.size() != 1 || blocks_[0].state != FREE; 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Collapse the block to the next one, then to the previous one. Provided the 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// structure is consistent, those are the only blocks eligible for collapse. 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::CollapseFreeBlock( 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index) { 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index + 1 < blocks_.size()) { 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &next = blocks_[index + 1]; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next.state == FREE) { 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_[index].size += next.size; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.erase(blocks_.begin() + index + 1); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index > 0) { 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &prev = blocks_[index - 1]; 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (prev.state == FREE) { 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev.size += blocks_[index].size; 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.erase(blocks_.begin() + index); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --index; 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return index; 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Waits for the block's token, then mark the block as free, then collapse it. 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::WaitForTokenAndFreeBlock( 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockIndex index) { 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 198f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK_EQ(block.state, FREE_PENDING_TOKEN); 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) helper_->WaitForToken(block.token); 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CollapseFreeBlock(index); 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Frees any blocks pending a token for which the token has been read. 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FencedAllocator::FreeUnused() { 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 last_token_read = helper_->last_token_read(); 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned int i = 0; i < blocks_.size();) { 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block& block = blocks_[i]; 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.state == FREE_PENDING_TOKEN && block.token <= last_token_read) { 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = FREE; 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = CollapseFreeBlock(i); 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++i; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If the block is exactly the requested size, simply mark it IN_USE, otherwise 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// split it and mark the first one (of the requested size) IN_USE. 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::Offset FencedAllocator::AllocInBlock(BlockIndex index, 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int size) { 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block &block = blocks_[index]; 223f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK_GE(block.size, size); 224f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK_EQ(block.state, FREE); 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Offset offset = block.offset; 2263551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bytes_in_use_ += size; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block.size == size) { 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = IN_USE; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return offset; 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block newblock = { FREE, offset + size, block.size - size, kUnusedToken}; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.state = IN_USE; 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) block.size = size; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this is the last thing being done because it may invalidate block; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) blocks_.insert(blocks_.begin() + index + 1, newblock); 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return offset; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The blocks are in offset order, so we can do a binary search. 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)FencedAllocator::BlockIndex FencedAllocator::GetBlockByOffset(Offset offset) { 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block templ = { IN_USE, offset, 0, kUnusedToken }; 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Container::iterator it = std::lower_bound(blocks_.begin(), blocks_.end(), 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) templ, OffsetCmp()); 244f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DCHECK(it != blocks_.end() && it->offset == offset); 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return it-blocks_.begin(); 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace gpu 249