1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkChunkAlloc.h" 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com// Don't malloc any chunks smaller than this 11ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com#define MIN_CHUNKALLOC_BLOCK_SIZE 1024 12ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com 13ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com// Return the new min blocksize given the current value 14ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.comstatic size_t increase_next_size(size_t size) { 15ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com return size + (size >> 1); 16ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com} 17ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com 18ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com/////////////////////////////////////////////////////////////////////////////// 19ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstruct SkChunkAlloc::Block { 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Block* fNext; 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t fFreeSize; 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fFreePtr; 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // data[] follows 25fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 26aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com char* startOfData() { 27aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com return reinterpret_cast<char*>(this + 1); 28aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com } 29aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com 30ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com static void FreeChain(Block* block) { 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (block) { 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Block* next = block->fNext; 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(block); 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com block = next; 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 37fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 38f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com bool contains(const void* addr) const { 39f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com const char* ptr = reinterpret_cast<const char*>(addr); 40f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com return ptr >= (const char*)(this + 1) && ptr < fFreePtr; 41f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com } 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 44ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com/////////////////////////////////////////////////////////////////////////////// 45ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com 46ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.comSkChunkAlloc::SkChunkAlloc(size_t minSize) { 47ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com if (minSize < MIN_CHUNKALLOC_BLOCK_SIZE) { 48ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com minSize = MIN_CHUNKALLOC_BLOCK_SIZE; 49ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com } 50ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com 51ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fBlock = NULL; 52ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fMinSize = minSize; 53ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fChunkSize = fMinSize; 54ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fTotalCapacity = 0; 556757a3c71fd6c16af6bbd76f268307f0177b17aereed@google.com fTotalUsed = 0; 56ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fBlockCount = 0; 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkChunkAlloc::~SkChunkAlloc() { 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(); 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChunkAlloc::reset() { 64ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com Block::FreeChain(fBlock); 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fBlock = NULL; 66ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fChunkSize = fMinSize; // reset to our initial minSize 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fTotalCapacity = 0; 686757a3c71fd6c16af6bbd76f268307f0177b17aereed@google.com fTotalUsed = 0; 69ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fBlockCount = 0; 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) { 736b9de8cb93f2aa970f2d407381c3768ae505f710scarybeasts@gmail.com size_t size = bytes; 74ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com if (size < fChunkSize) { 75ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com size = fChunkSize; 76ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com } 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 78ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com Block* block = (Block*)sk_malloc_flags(sizeof(Block) + size, 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0); 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (block) { 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // block->fNext = fBlock; 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com block->fFreeSize = size; 84aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com block->fFreePtr = block->startOfData(); 85fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fTotalCapacity += size; 87ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fBlockCount += 1; 88fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 89ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com fChunkSize = increase_next_size(fChunkSize); 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return block; 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) { 956757a3c71fd6c16af6bbd76f268307f0177b17aereed@google.com fTotalUsed += bytes; 964d494f031cd52c79fec69adeaab2c02134b7959bskia.committer@gmail.com 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bytes = SkAlign4(bytes); 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Block* block = fBlock; 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (block == NULL || bytes > block->fFreeSize) { 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com block = this->newBlock(bytes, ftype); 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (NULL == block) { 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return NULL; 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com block->fNext = fBlock; 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fBlock = block; 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(block && bytes <= block->fFreeSize); 111ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com char* ptr = block->fFreePtr; 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com block->fFreeSize -= bytes; 114ebd24962dfdb7a62cf97c0e3938851d56cabd10freed@google.com block->fFreePtr = ptr + bytes; 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return ptr; 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 118aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.comsize_t SkChunkAlloc::unalloc(void* ptr) { 119aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com size_t bytes = 0; 120aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com Block* block = fBlock; 121aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com if (block) { 122aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com char* cPtr = reinterpret_cast<char*>(ptr); 123aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com char* start = block->startOfData(); 124aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com if (start <= cPtr && cPtr < block->fFreePtr) { 125aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com bytes = block->fFreePtr - cPtr; 126aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com block->fFreeSize += bytes; 127aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com block->fFreePtr = cPtr; 128aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com } 129aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com } 130aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com return bytes; 131aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com} 132aefd2bc75738963b9b6579897be32bfbc8fb00afreed@android.com 133f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.combool SkChunkAlloc::contains(const void* addr) const { 134f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com const Block* block = fBlock; 135f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com while (block) { 136f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com if (block->contains(addr)) { 137f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com return true; 138f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com } 139f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com block = block->fNext; 140f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com } 141f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com return false; 142f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com} 143