244 lines
7.8 KiB
C
244 lines
7.8 KiB
C
/*
|
|
* Copyright (C) 2017 The Android Open Source Project
|
|
*
|
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
|
* you may not use this file except in compliance with the License.
|
|
* You may obtain a copy of the License at
|
|
*
|
|
* http://www.apache.org/licenses/LICENSE-2.0
|
|
*
|
|
* Unless required by applicable law or agreed to in writing, software
|
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
* See the License for the specific language governing permissions and
|
|
* limitations under the License.
|
|
*/
|
|
|
|
#include "ufdt_node_pool.h"
|
|
|
|
#include "libufdt_sysdeps.h"
|
|
#include "ufdt_types.h"
|
|
|
|
/* Define DEBUG_DISABLE_POOL to use dto_malloc and dto_free directly */
|
|
/* #define DEBUG_DISABLE_POOL */
|
|
|
|
#define MAX(a, b) ((a) > (b) ? (a) : (b))
|
|
|
|
#define UFDT_NODE_POOL_ENTRIES_PER_BLOCK 1024
|
|
/* UFDT_NODE_POOL_ENTRY_SIZE must be equal to or larger than
|
|
sizeof(struct ufdt_node_fdt_node) and sizeof(struct ufdt_node_fdt_prop) */
|
|
#define UFDT_NODE_POOL_ENTRY_SIZE \
|
|
MAX(sizeof(struct ufdt_node_fdt_node), sizeof(struct ufdt_node_fdt_prop))
|
|
/* A block is a header appended UFDT_NODE_POOL_ENTRIES_PER_BLOCK entries */
|
|
#define UFDT_NODE_POOL_BLOCK_SIZE \
|
|
(sizeof(struct ufdt_node_pool_block_header) + \
|
|
UFDT_NODE_POOL_ENTRY_SIZE * UFDT_NODE_POOL_ENTRIES_PER_BLOCK)
|
|
|
|
/*
|
|
* The data structure:
|
|
*
|
|
* pool block block
|
|
* +--------------+ +--------------------+ +-----------------+
|
|
* | *first_block |---->| block_header: | | ... | ...
|
|
* | ... | | *next_block |---->| |---->
|
|
* +--------------+ | *first_free_entry |--\ | ... |
|
|
* | ... | |
|
|
* +--------------------+ |
|
|
* | entry_header: |<-/
|
|
* | *next |--\
|
|
* +--------------------+ |
|
|
* | ... |<-/
|
|
* | |--\
|
|
* +--------------------+ |
|
|
* | ... | v
|
|
*/
|
|
|
|
struct ufdt_node_pool_entry_header {
|
|
struct ufdt_node_pool_entry_header *next;
|
|
};
|
|
|
|
struct ufdt_node_pool_block_header {
|
|
struct ufdt_node_pool_block_header *next_block;
|
|
struct ufdt_node_pool_entry_header *first_free_entry;
|
|
int alloc_entry_cnt;
|
|
};
|
|
|
|
void ufdt_node_pool_construct(struct ufdt_node_pool *pool) {
|
|
pool->first_block = NULL;
|
|
pool->last_block_ptr = &pool->first_block;
|
|
}
|
|
|
|
void ufdt_node_pool_destruct(struct ufdt_node_pool *pool) {
|
|
int is_leak = 0;
|
|
struct ufdt_node_pool_block_header *block = pool->first_block;
|
|
while (block != NULL) {
|
|
if (block->alloc_entry_cnt != 0) is_leak = 1;
|
|
|
|
struct ufdt_node_pool_block_header *next_block = block->next_block;
|
|
dto_free(block);
|
|
block = next_block;
|
|
}
|
|
|
|
if (is_leak) {
|
|
dto_error("Some nodes aren't freed before ufdt_node_pool_destruct().\n");
|
|
}
|
|
|
|
pool->first_block = NULL;
|
|
pool->last_block_ptr = NULL;
|
|
}
|
|
|
|
static struct ufdt_node_pool_block_header *_ufdt_node_pool_create_block() {
|
|
char *block_buf = (char *)dto_malloc(UFDT_NODE_POOL_BLOCK_SIZE);
|
|
char *block_buf_start = block_buf + sizeof(struct ufdt_node_pool_block_header);
|
|
char *block_buf_end = block_buf + UFDT_NODE_POOL_BLOCK_SIZE;
|
|
|
|
struct ufdt_node_pool_block_header *block =
|
|
(struct ufdt_node_pool_block_header *)block_buf;
|
|
|
|
// Setup all entries to be a one way link list
|
|
struct ufdt_node_pool_entry_header **next_ptr = &block->first_free_entry;
|
|
for (char *entry_buf = block_buf_start; entry_buf < block_buf_end;
|
|
entry_buf += UFDT_NODE_POOL_ENTRY_SIZE) {
|
|
struct ufdt_node_pool_entry_header *entry =
|
|
(struct ufdt_node_pool_entry_header *)entry_buf;
|
|
|
|
*next_ptr = entry;
|
|
|
|
next_ptr = &entry->next;
|
|
}
|
|
*next_ptr = NULL;
|
|
|
|
block->next_block = NULL;
|
|
block->alloc_entry_cnt = 0;
|
|
|
|
return block;
|
|
}
|
|
|
|
static void _ufdt_node_pool_destory_block(
|
|
struct ufdt_node_pool_block_header *block) {
|
|
dto_free(block);
|
|
}
|
|
|
|
static void *_ufdt_node_pool_block_alloc(
|
|
struct ufdt_node_pool_block_header *block) {
|
|
// take the first free enrtry
|
|
struct ufdt_node_pool_entry_header *entry = block->first_free_entry;
|
|
|
|
block->first_free_entry = entry->next;
|
|
block->alloc_entry_cnt++;
|
|
|
|
return entry;
|
|
}
|
|
|
|
static void _ufdt_node_pool_block_free(struct ufdt_node_pool_block_header *block,
|
|
void *node) {
|
|
// put the node to the first free enrtry
|
|
struct ufdt_node_pool_entry_header *entry = node;
|
|
entry->next = block->first_free_entry;
|
|
|
|
block->first_free_entry = entry;
|
|
block->alloc_entry_cnt--;
|
|
}
|
|
|
|
static void _ufdt_node_pool_preppend_block(
|
|
struct ufdt_node_pool *pool, struct ufdt_node_pool_block_header *block) {
|
|
struct ufdt_node_pool_block_header *origin_first_block = pool->first_block;
|
|
block->next_block = origin_first_block;
|
|
|
|
pool->first_block = block;
|
|
if (origin_first_block == NULL) {
|
|
pool->last_block_ptr = &block->next_block;
|
|
}
|
|
}
|
|
|
|
static void _ufdt_node_pool_append_block(
|
|
struct ufdt_node_pool *pool, struct ufdt_node_pool_block_header *block) {
|
|
block->next_block = NULL;
|
|
|
|
*pool->last_block_ptr = block;
|
|
pool->last_block_ptr = &block->next_block;
|
|
}
|
|
|
|
static void _ufdt_node_pool_remove_block(
|
|
struct ufdt_node_pool *pool,
|
|
struct ufdt_node_pool_block_header **block_ptr) {
|
|
struct ufdt_node_pool_block_header *block = *block_ptr;
|
|
struct ufdt_node_pool_block_header *next_block = block->next_block;
|
|
|
|
*block_ptr = next_block;
|
|
if (next_block == NULL) {
|
|
pool->last_block_ptr = block_ptr;
|
|
}
|
|
|
|
block->next_block = NULL;
|
|
}
|
|
|
|
void *ufdt_node_pool_alloc(struct ufdt_node_pool *pool) {
|
|
#ifdef DEBUG_DISABLE_POOL
|
|
return dto_malloc(UFDT_NODE_POOL_ENTRY_SIZE);
|
|
#endif
|
|
|
|
// return dto_malloc(UFDT_NODE_POOL_ENTRY_SIZE);
|
|
// If there is no free block, create a new one
|
|
struct ufdt_node_pool_block_header *block = pool->first_block;
|
|
if (block == NULL || block->first_free_entry == NULL) {
|
|
block = _ufdt_node_pool_create_block();
|
|
_ufdt_node_pool_preppend_block(pool, block);
|
|
}
|
|
|
|
void *node = _ufdt_node_pool_block_alloc(block);
|
|
|
|
// Move the block to the last if there is no free entry
|
|
if (block->first_free_entry == NULL && *pool->last_block_ptr != block) {
|
|
_ufdt_node_pool_remove_block(pool, &pool->first_block);
|
|
_ufdt_node_pool_append_block(pool, block);
|
|
}
|
|
|
|
return node;
|
|
}
|
|
|
|
static struct ufdt_node_pool_block_header **_ufdt_node_pool_search_block(
|
|
struct ufdt_node_pool *pool, void *node) {
|
|
struct ufdt_node_pool_block_header **block_ptr = &pool->first_block;
|
|
while (*block_ptr != NULL) {
|
|
struct ufdt_node_pool_block_header *block = *block_ptr;
|
|
const char *block_buf_start =
|
|
(char *)block + sizeof(struct ufdt_node_pool_block_header);
|
|
const char *block_buf_end = (char *)block + UFDT_NODE_POOL_BLOCK_SIZE;
|
|
|
|
if ((char *)node >= block_buf_start && (char *)node < block_buf_end) {
|
|
break;
|
|
}
|
|
|
|
block_ptr = &block->next_block;
|
|
}
|
|
return block_ptr;
|
|
}
|
|
|
|
void ufdt_node_pool_free(struct ufdt_node_pool *pool, void *node) {
|
|
#ifdef DEBUG_DISABLE_POOL
|
|
return dto_free(node);
|
|
#endif
|
|
|
|
struct ufdt_node_pool_block_header **block_ptr =
|
|
_ufdt_node_pool_search_block(pool, node);
|
|
if (*block_ptr == NULL) {
|
|
dto_error("Given node is not in the pool.\n");
|
|
return;
|
|
}
|
|
|
|
struct ufdt_node_pool_block_header *block = *block_ptr;
|
|
_ufdt_node_pool_block_free(block, node);
|
|
_ufdt_node_pool_remove_block(pool, block_ptr);
|
|
|
|
/* Delay free block: free the block only if the block is all freed and
|
|
there has at least one another free block */
|
|
if (block->alloc_entry_cnt == 0 && pool->first_block != NULL &&
|
|
pool->first_block->first_free_entry != NULL) {
|
|
_ufdt_node_pool_destory_block(block);
|
|
return;
|
|
}
|
|
|
|
_ufdt_node_pool_preppend_block(pool, block);
|
|
}
|