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
56struct ufdt_node_pool_entry_header {
57  struct ufdt_node_pool_entry_header *next;
58};
59
60struct 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
66void ufdt_node_pool_construct(struct ufdt_node_pool *pool) {
67  pool->first_block = NULL;
68  pool->last_block_ptr = &pool->first_block;
69}
70
71void 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
90static 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
117static void _ufdt_node_pool_destory_block(
118    struct ufdt_node_pool_block_header *block) {
119  dto_free(block);
120}
121
122static 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
133static 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
143static 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
154static 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
162static 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
176void *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
200static 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
218void 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