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
ufdt_node_pool_construct(struct ufdt_node_pool * pool)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
ufdt_node_pool_destruct(struct ufdt_node_pool * pool)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
_ufdt_node_pool_create_block()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
_ufdt_node_pool_destory_block(struct ufdt_node_pool_block_header * block)117 static void _ufdt_node_pool_destory_block(
118 struct ufdt_node_pool_block_header *block) {
119 dto_free(block);
120 }
121
_ufdt_node_pool_block_alloc(struct ufdt_node_pool_block_header * block)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
_ufdt_node_pool_block_free(struct ufdt_node_pool_block_header * block,void * node)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
_ufdt_node_pool_preppend_block(struct ufdt_node_pool * pool,struct ufdt_node_pool_block_header * block)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
_ufdt_node_pool_append_block(struct ufdt_node_pool * pool,struct ufdt_node_pool_block_header * block)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
_ufdt_node_pool_remove_block(struct ufdt_node_pool * pool,struct ufdt_node_pool_block_header ** block_ptr)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
ufdt_node_pool_alloc(struct ufdt_node_pool * pool)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
_ufdt_node_pool_search_block(struct ufdt_node_pool * pool,void * node)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
ufdt_node_pool_free(struct ufdt_node_pool * pool,void * node)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