1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "ufdt_node_pool.h" 18 19 #include "libufdt_sysdeps.h" 20 #include "ufdt_types.h" 21 22 /* Define DEBUG_DISABLE_POOL to use dto_malloc and dto_free directly */ 23 /* #define DEBUG_DISABLE_POOL */ 24 25 #define MAX(a, b) ((a) > (b) ? (a) : (b)) 26 27 #define UFDT_NODE_POOL_ENTRIES_PER_BLOCK 1024 28 /* UFDT_NODE_POOL_ENTRY_SIZE must be equal to or larger than 29 sizeof(struct ufdt_node_fdt_node) and sizeof(struct ufdt_node_fdt_prop) */ 30 #define UFDT_NODE_POOL_ENTRY_SIZE \ 31 MAX(sizeof(struct ufdt_node_fdt_node), sizeof(struct ufdt_node_fdt_prop)) 32 /* A block is a header appended UFDT_NODE_POOL_ENTRIES_PER_BLOCK entries */ 33 #define UFDT_NODE_POOL_BLOCK_SIZE \ 34 (sizeof(struct ufdt_node_pool_block_header) + \ 35 UFDT_NODE_POOL_ENTRY_SIZE * UFDT_NODE_POOL_ENTRIES_PER_BLOCK) 36 37 /* 38 * The data structure: 39 * 40 * pool block block 41 * +--------------+ +--------------------+ +-----------------+ 42 * | *first_block |---->| block_header: | | ... | ... 43 * | ... | | *next_block |---->| |----> 44 * +--------------+ | *first_free_entry |--\ | ... | 45 * | ... | | 46 * +--------------------+ | 47 * | entry_header: |<-/ 48 * | *next |--\ 49 * +--------------------+ | 50 * | ... |<-/ 51 * | |--\ 52 * +--------------------+ | 53 * | ... | v 54 */ 55 56 struct ufdt_node_pool_entry_header { 57 struct ufdt_node_pool_entry_header *next; 58 }; 59 60 struct ufdt_node_pool_block_header { 61 struct ufdt_node_pool_block_header *next_block; 62 struct ufdt_node_pool_entry_header *first_free_entry; 63 int alloc_entry_cnt; 64 }; 65 66 void ufdt_node_pool_construct(struct ufdt_node_pool *pool) { 67 pool->first_block = NULL; 68 pool->last_block_ptr = &pool->first_block; 69 } 70 71 void ufdt_node_pool_destruct(struct ufdt_node_pool *pool) { 72 int is_leak = 0; 73 struct ufdt_node_pool_block_header *block = pool->first_block; 74 while (block != NULL) { 75 if (block->alloc_entry_cnt != 0) is_leak = 1; 76 77 struct ufdt_node_pool_block_header *next_block = block->next_block; 78 dto_free(block); 79 block = next_block; 80 } 81 82 if (is_leak) { 83 dto_error("Some nodes aren't freed before ufdt_node_pool_destruct().\n"); 84 } 85 86 pool->first_block = NULL; 87 pool->last_block_ptr = NULL; 88 } 89 90 static struct ufdt_node_pool_block_header *_ufdt_node_pool_create_block() { 91 char *block_buf = (char *)dto_malloc(UFDT_NODE_POOL_BLOCK_SIZE); 92 char *block_buf_start = block_buf + sizeof(struct ufdt_node_pool_block_header); 93 char *block_buf_end = block_buf + UFDT_NODE_POOL_BLOCK_SIZE; 94 95 struct ufdt_node_pool_block_header *block = 96 (struct ufdt_node_pool_block_header *)block_buf; 97 98 // Setup all entries to be a one way link list 99 struct ufdt_node_pool_entry_header **next_ptr = &block->first_free_entry; 100 for (char *entry_buf = block_buf_start; entry_buf < block_buf_end; 101 entry_buf += UFDT_NODE_POOL_ENTRY_SIZE) { 102 struct ufdt_node_pool_entry_header *entry = 103 (struct ufdt_node_pool_entry_header *)entry_buf; 104 105 *next_ptr = entry; 106 107 next_ptr = &entry->next; 108 } 109 *next_ptr = NULL; 110 111 block->next_block = NULL; 112 block->alloc_entry_cnt = 0; 113 114 return block; 115 } 116 117 static void _ufdt_node_pool_destory_block( 118 struct ufdt_node_pool_block_header *block) { 119 dto_free(block); 120 } 121 122 static void *_ufdt_node_pool_block_alloc( 123 struct ufdt_node_pool_block_header *block) { 124 // take the first free enrtry 125 struct ufdt_node_pool_entry_header *entry = block->first_free_entry; 126 127 block->first_free_entry = entry->next; 128 block->alloc_entry_cnt++; 129 130 return entry; 131 } 132 133 static void _ufdt_node_pool_block_free(struct ufdt_node_pool_block_header *block, 134 void *node) { 135 // put the node to the first free enrtry 136 struct ufdt_node_pool_entry_header *entry = node; 137 entry->next = block->first_free_entry; 138 139 block->first_free_entry = entry; 140 block->alloc_entry_cnt--; 141 } 142 143 static void _ufdt_node_pool_preppend_block( 144 struct ufdt_node_pool *pool, struct ufdt_node_pool_block_header *block) { 145 struct ufdt_node_pool_block_header *origin_first_block = pool->first_block; 146 block->next_block = origin_first_block; 147 148 pool->first_block = block; 149 if (origin_first_block == NULL) { 150 pool->last_block_ptr = &block->next_block; 151 } 152 } 153 154 static void _ufdt_node_pool_append_block( 155 struct ufdt_node_pool *pool, struct ufdt_node_pool_block_header *block) { 156 block->next_block = NULL; 157 158 *pool->last_block_ptr = block; 159 pool->last_block_ptr = &block->next_block; 160 } 161 162 static void _ufdt_node_pool_remove_block( 163 struct ufdt_node_pool *pool, 164 struct ufdt_node_pool_block_header **block_ptr) { 165 struct ufdt_node_pool_block_header *block = *block_ptr; 166 struct ufdt_node_pool_block_header *next_block = block->next_block; 167 168 *block_ptr = next_block; 169 if (next_block == NULL) { 170 pool->last_block_ptr = block_ptr; 171 } 172 173 block->next_block = NULL; 174 } 175 176 void *ufdt_node_pool_alloc(struct ufdt_node_pool *pool) { 177 #ifdef DEBUG_DISABLE_POOL 178 return dto_malloc(UFDT_NODE_POOL_ENTRY_SIZE); 179 #endif 180 181 // return dto_malloc(UFDT_NODE_POOL_ENTRY_SIZE); 182 // If there is no free block, create a new one 183 struct ufdt_node_pool_block_header *block = pool->first_block; 184 if (block == NULL || block->first_free_entry == NULL) { 185 block = _ufdt_node_pool_create_block(); 186 _ufdt_node_pool_preppend_block(pool, block); 187 } 188 189 void *node = _ufdt_node_pool_block_alloc(block); 190 191 // Move the block to the last if there is no free entry 192 if (block->first_free_entry == NULL && *pool->last_block_ptr != block) { 193 _ufdt_node_pool_remove_block(pool, &pool->first_block); 194 _ufdt_node_pool_append_block(pool, block); 195 } 196 197 return node; 198 } 199 200 static struct ufdt_node_pool_block_header **_ufdt_node_pool_search_block( 201 struct ufdt_node_pool *pool, void *node) { 202 struct ufdt_node_pool_block_header **block_ptr = &pool->first_block; 203 while (*block_ptr != NULL) { 204 struct ufdt_node_pool_block_header *block = *block_ptr; 205 const char *block_buf_start = 206 (char *)block + sizeof(struct ufdt_node_pool_block_header); 207 const char *block_buf_end = (char *)block + UFDT_NODE_POOL_BLOCK_SIZE; 208 209 if ((char *)node >= block_buf_start && (char *)node < block_buf_end) { 210 break; 211 } 212 213 block_ptr = &block->next_block; 214 } 215 return block_ptr; 216 } 217 218 void ufdt_node_pool_free(struct ufdt_node_pool *pool, void *node) { 219 #ifdef DEBUG_DISABLE_POOL 220 return dto_free(node); 221 #endif 222 223 struct ufdt_node_pool_block_header **block_ptr = 224 _ufdt_node_pool_search_block(pool, node); 225 if (*block_ptr == NULL) { 226 dto_error("Given node is not in the pool.\n"); 227 return; 228 } 229 230 struct ufdt_node_pool_block_header *block = *block_ptr; 231 _ufdt_node_pool_block_free(block, node); 232 _ufdt_node_pool_remove_block(pool, block_ptr); 233 234 /* Delay free block: free the block only if the block is all freed and 235 there has at least one another free block */ 236 if (block->alloc_entry_cnt == 0 && pool->first_block != NULL && 237 pool->first_block->first_free_entry != NULL) { 238 _ufdt_node_pool_destory_block(block); 239 return; 240 } 241 242 _ufdt_node_pool_preppend_block(pool, block); 243 } 244