180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkChunkAlloc.h" 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Don't malloc any chunks smaller than this 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define MIN_CHUNKALLOC_BLOCK_SIZE 1024 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Return the new min blocksize given the current value 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic size_t increase_next_size(size_t size) { 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return size + (size >> 1); 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustruct SkChunkAlloc::Block { 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* fNext; 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t fFreeSize; 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* fFreePtr; 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // data[] follows 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* startOfData() { 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return reinterpret_cast<char*>(this + 1); 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static void FreeChain(Block* block) { 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (block) { 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* next = block->fNext; 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru sk_free(block); 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block = next; 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool contains(const void* addr) const { 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const char* ptr = reinterpret_cast<const char*>(addr); 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return ptr >= (const char*)(this + 1) && ptr < fFreePtr; 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkChunkAlloc::SkChunkAlloc(size_t minSize) { 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (minSize < MIN_CHUNKALLOC_BLOCK_SIZE) { 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru minSize = MIN_CHUNKALLOC_BLOCK_SIZE; 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBlock = NULL; 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fMinSize = minSize; 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fChunkSize = fMinSize; 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTotalCapacity = 0; 5558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fTotalUsed = 0; 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBlockCount = 0; 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkChunkAlloc::~SkChunkAlloc() { 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->reset(); 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkChunkAlloc::reset() { 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block::FreeChain(fBlock); 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBlock = NULL; 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fChunkSize = fMinSize; // reset to our initial minSize 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTotalCapacity = 0; 6858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fTotalUsed = 0; 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBlockCount = 0; 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) { 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t size = bytes; 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (size < fChunkSize) { 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size = fChunkSize; 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* block = (Block*)sk_malloc_flags(sizeof(Block) + size, 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0); 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (block) { 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // block->fNext = fBlock; 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fFreeSize = size; 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fFreePtr = block->startOfData(); 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTotalCapacity += size; 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBlockCount += 1; 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fChunkSize = increase_next_size(fChunkSize); 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return block; 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) { 9558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fTotalUsed += bytes; 9658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bytes = SkAlign4(bytes); 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* block = fBlock; 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (block == NULL || bytes > block->fFreeSize) { 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block = this->newBlock(bytes, ftype); 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == block) { 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return NULL; 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fNext = fBlock; 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fBlock = block; 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(block && bytes <= block->fFreeSize); 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* ptr = block->fFreePtr; 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fFreeSize -= bytes; 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fFreePtr = ptr + bytes; 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return ptr; 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querusize_t SkChunkAlloc::unalloc(void* ptr) { 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t bytes = 0; 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* block = fBlock; 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (block) { 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* cPtr = reinterpret_cast<char*>(ptr); 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* start = block->startOfData(); 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (start <= cPtr && cPtr < block->fFreePtr) { 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bytes = block->fFreePtr - cPtr; 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fFreeSize += bytes; 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fFreePtr = cPtr; 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return bytes; 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkChunkAlloc::contains(const void* addr) const { 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Block* block = fBlock; 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (block) { 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (block->contains(addr)) { 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block = block->fNext; 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 143