1 /*
2 * %CopyrightBegin%
3 *
4 * Copyright Ericsson AB 2003-2020. All Rights Reserved.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * %CopyrightEnd%
19 */
20
21
22 /*
23 * Description: A family of "first fit" allocator strategies
24 * based on a Red-Black (binary search) Tree. The search,
25 * insert, and delete operations are all O(log n) operations
26 * on a Red-Black Tree.
27 * Red-Black Trees are described in "Introduction to Algorithms",
28 * by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Riverest.
29 *
30 * This module is a callback-module for erl_alloc_util.c
31 *
32 * AOFF Algorithm:
33 * The tree nodes are ordered in address order.
34 * Every node also keeps the size of the largest block in its
35 * sub-tree ('max_sz'). By that we can start from root and keep
36 * left (for low addresses) while dismissing entire sub-trees with
37 * too small blocks.
38 * Bestfit within carrier:
39 * The only difference for "bestfit within carrier" is the tree
40 * sorting order. Blocks within the same carrier are sorted
41 * wrt size instead of address. The 'max_sz' field is maintained
42 * in order to dismiss entire carriers with too small blocks.
43 * Age Order:
44 * Carriers are ordered by creation time instead of address.
45 * Oldest carrier with a large enough free block is chosen.
46 * No age order supported for blocks.
47 *
48 * Authors: Rickard Green/Sverker Eriksson
49 */
50
51
52 #ifdef HAVE_CONFIG_H
53 # include "config.h"
54 #endif
55 #include "global.h"
56 #define GET_ERL_AOFF_ALLOC_IMPL
57 #include "erl_ao_firstfit_alloc.h"
58
59 #ifdef DEBUG
60 # define IS_DEBUG 1
61 #if 0
62 #define HARD_DEBUG
63 #endif
64 #else
65 # define IS_DEBUG 0
66 #undef HARD_DEBUG
67 #endif
68
69 #define MIN_MBC_SZ (16*1024)
70 #define MIN_MBC_FIRST_FREE_SZ (4*1024)
71
72 #define TREE_NODE_FLG (((Uint) 1) << 0)
73 #define RED_FLG (((Uint) 1) << 1)
74 #ifdef HARD_DEBUG
75 # define LEFT_VISITED_FLG (((Uint) 1) << 2)
76 # define RIGHT_VISITED_FLG (((Uint) 1) << 3)
77 #endif
78 #ifdef DEBUG
79 # define IS_BF_FLG (((Uint) 1) << 4)
80 #endif
81
82 #define IS_TREE_NODE(N) (((AOFF_RBTree_t *) (N))->flags & TREE_NODE_FLG)
83 #define IS_LIST_ELEM(N) (!IS_TREE_NODE(((AOFF_RBTree_t *) (N))))
84
85 #define SET_TREE_NODE(N) (((AOFF_RBTree_t *) (N))->flags |= TREE_NODE_FLG)
86 #define SET_LIST_ELEM(N) (((AOFF_RBTree_t *) (N))->flags &= ~TREE_NODE_FLG)
87
88 #define IS_RED(N) (((AOFF_RBTree_t *) (N)) \
89 && ((AOFF_RBTree_t *) (N))->flags & RED_FLG)
90 #define IS_BLACK(N) (!IS_RED(((AOFF_RBTree_t *) (N))))
91
92 #define SET_RED(N) (((AOFF_RBTree_t *) (N))->flags |= RED_FLG)
93 #define SET_BLACK(N) (((AOFF_RBTree_t *) (N))->flags &= ~RED_FLG)
94
95 #if 1
96 #define RBT_ASSERT ASSERT
97 #else
98 #define RBT_ASSERT(x)
99 #endif
100
101 #define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
102
103 #define AOFF_LIST_NEXT(N) (((AOFF_RBTree_t*)(N))->u.next)
104 #define AOFF_LIST_PREV(N) (((AOFF_RBTree_t*)(N))->parent)
105
106 typedef struct AOFF_Carrier_t_ AOFF_Carrier_t;
107
108 struct AOFF_Carrier_t_ {
109 Carrier_t crr;
110 AOFF_RBTree_t rbt_node; /* My node in the carrier tree */
111 AOFF_RBTree_t* root; /* Root of my block tree */
112 enum AOFFSortOrder blk_order;
113 };
114
115 #define RBT_NODE_TO_MBC(PTR) ErtsContainerStruct((PTR), AOFF_Carrier_t, rbt_node)
116
117 /*
118 To support carrier migration we keep two kinds of rb-trees:
119 1. One tree of carriers for each allocator instance.
120 2. One tree of free blocks for each carrier.
121 Both trees use the same node structure AOFF_RBTree_t and implementation.
122 Carrier nodes thus contain a phony Block_t header 'rbt_node.hdr'.
123 The size value of such a phony block is the size of the largest free block in
124 that carrier, i.e same as 'max_sz' of the root node of its block tree.
125 */
126
127 #ifdef HARD_DEBUG
128 # define HARD_CHECK_IS_MEMBER(ROOT,NODE) ASSERT(rbt_is_member(ROOT,NODE))
129 # define HARD_CHECK_TREE(CRR,ORDER,ROOT,SZ) check_tree(CRR, ORDER, ROOT, SZ)
130 static AOFF_RBTree_t * check_tree(Carrier_t*, enum AOFFSortOrder, AOFF_RBTree_t*, Uint);
131 #else
132 # define HARD_CHECK_IS_MEMBER(ROOT,NODE)
133 # define HARD_CHECK_TREE(CRR,ORDER,ROOT,SZ)
134 #endif
135
136
137 /* Calculate 'max_sz' of tree node x by only looking at 'max_sz' of the
138 * direct children of x and the size x itself.
139 */
node_max_size(AOFF_RBTree_t * x)140 static ERTS_INLINE Uint node_max_size(AOFF_RBTree_t *x)
141 {
142 Uint sz = AOFF_BLK_SZ(x);
143 if (x->left && x->left->max_sz > sz) {
144 sz = x->left->max_sz;
145 }
146 if (x->right && x->right->max_sz > sz) {
147 sz = x->right->max_sz;
148 }
149 return sz;
150 }
151
152 /* Set new possibly lower 'max_sz' of node and propagate change toward root
153 */
lower_max_size(AOFF_RBTree_t * node,AOFF_RBTree_t * stop_at)154 static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
155 AOFF_RBTree_t* stop_at)
156 {
157 AOFF_RBTree_t* x = node;
158 Uint old_max = x->max_sz;
159 Uint new_max = node_max_size(x);
160
161 if (new_max < old_max) {
162 x->max_sz = new_max;
163 while ((x=x->parent) != stop_at && x->max_sz == old_max) {
164 x->max_sz = node_max_size(x);
165 }
166 ASSERT(x == stop_at || x->max_sz > old_max);
167 }
168 else ASSERT(new_max == old_max);
169 }
170
171 /*
172 * Set possibly new larger 'max_sz' of node and propagate change toward root
173 */
erts_aoff_larger_max_size(AOFF_RBTree_t * node)174 void erts_aoff_larger_max_size(AOFF_RBTree_t *node)
175 {
176 AOFF_RBTree_t* x = node;
177 const Uint new_sz = node->hdr.bhdr;
178
179 ASSERT(!x->left || x->left->max_sz <= x->max_sz);
180 ASSERT(!x->right || x->right->max_sz <= x->max_sz);
181
182 while (new_sz > x->max_sz) {
183 x->max_sz = new_sz;
184 x = x->parent;
185 if (!x)
186 break;
187 }
188 }
189
190 /* Compare nodes for both carrier and block trees */
cmp_blocks(enum AOFFSortOrder order,AOFF_RBTree_t * lhs,AOFF_RBTree_t * rhs)191 static ERTS_INLINE SWord cmp_blocks(enum AOFFSortOrder order,
192 AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
193 {
194 ASSERT(lhs != rhs);
195 if (order == FF_AGEFF) {
196 Sint64 diff = lhs->u.birth_time - rhs->u.birth_time;
197 #ifdef ARCH_64
198 if (diff)
199 return diff;
200 #else
201 if (diff < 0)
202 return -1;
203 else if (diff > 0)
204 return 1;
205 #endif
206 }
207 else {
208 ASSERT(order == FF_AOFF || FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
209 if (order != FF_AOFF) {
210 SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs);
211 if (diff || order == FF_BF) return diff;
212 }
213 }
214 return (char*)lhs - (char*)rhs;
215 }
216
217 /* Compare candidate block. Only for block tree */
cmp_cand_blk(enum AOFFSortOrder order,Block_t * cand_blk,AOFF_RBTree_t * rhs)218 static ERTS_INLINE SWord cmp_cand_blk(enum AOFFSortOrder order,
219 Block_t* cand_blk, AOFF_RBTree_t* rhs)
220 {
221 ASSERT(order != FF_AGEFF);
222 if (order != FF_AOFF) {
223 if (BLK_TO_MBC(cand_blk) == FBLK_TO_MBC(&rhs->hdr)) {
224 SWord diff = (SWord)MBC_BLK_SZ(cand_blk) - (SWord)MBC_FBLK_SZ(&rhs->hdr);
225 if (diff || order == FF_BF) return diff;
226 }
227 }
228 return (char*)cand_blk - (char*)rhs;
229 }
230
231
232 /* Prototypes of callback functions */
233 static Block_t* aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint);
234 static void aoff_link_free_block(Allctr_t *, Block_t*);
235 static void aoff_unlink_free_block(Allctr_t *allctr, Block_t *del);
236 static void aoff_creating_mbc(Allctr_t*, Carrier_t*);
237 #ifdef DEBUG
238 static void aoff_destroying_mbc(Allctr_t*, Carrier_t*);
239 #endif
240 static void aoff_add_mbc(Allctr_t*, Carrier_t*);
241 static void aoff_remove_mbc(Allctr_t*, Carrier_t*);
242 static UWord aoff_largest_fblk_in_mbc(Allctr_t*, Carrier_t*);
243
244 static Block_t *aoff_first_fblk_in_mbc(Allctr_t *, Carrier_t *);
245 static Block_t *aoff_next_fblk_in_mbc(Allctr_t *, Carrier_t *, Block_t *);
246
247 /* Generic tree functions used by both carrier and block trees. */
248 static void rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del);
249 static void rbt_insert(enum AOFFSortOrder, AOFF_RBTree_t** root, AOFF_RBTree_t* blk);
250 static AOFF_RBTree_t* rbt_search(AOFF_RBTree_t* root, Uint size);
251
252 static Eterm info_options(Allctr_t *, char *, fmtfn_t *, void *, Uint **, Uint *);
253 static void init_atoms(void);
254
255
256 static int atoms_initialized = 0;
257
258 #ifndef ERTS_HAVE_OS_MONOTONIC_TIME_SUPPORT
259 static erts_atomic64_t birth_time_counter;
260 #endif
261
262 void
erts_aoffalc_init(void)263 erts_aoffalc_init(void)
264 {
265 atoms_initialized = 0;
266 #ifndef ERTS_HAVE_OS_MONOTONIC_TIME_SUPPORT
267 erts_atomic64_init_nob(&birth_time_counter, 0);
268 #endif
269 }
270
271 Allctr_t *
erts_aoffalc_start(AOFFAllctr_t * alc,AOFFAllctrInit_t * aoffinit,AllctrInit_t * init)272 erts_aoffalc_start(AOFFAllctr_t *alc,
273 AOFFAllctrInit_t* aoffinit,
274 AllctrInit_t *init)
275 {
276 struct {
277 int dummy;
278 AOFFAllctr_t allctr;
279 } zero = {0};
280 /* The struct with a dummy element first is used in order to avoid (an
281 incorrect) gcc warning. gcc warns if {0} is used as initializer of
282 a struct when the first member is a struct (not if, for example,
283 the third member is a struct). */
284
285 Allctr_t *allctr = (Allctr_t *) alc;
286
287 sys_memcpy((void *) alc, (void *) &zero.allctr, sizeof(AOFFAllctr_t));
288
289 if (aoffinit->blk_order == FF_CHAOS) {
290 const enum AOFFSortOrder orders[3] = {FF_AOFF, FF_AOBF, FF_BF};
291 int index = init->ix % (sizeof(orders) / sizeof(orders[0]));
292
293 ASSERT(init->alloc_no == ERTS_ALC_A_TEST);
294 aoffinit->blk_order = orders[index];
295 }
296
297 if (aoffinit->crr_order == FF_CHAOS) {
298 const enum AOFFSortOrder orders[2] = {FF_AGEFF, FF_AOFF};
299 int index = init->ix % (sizeof(orders) / sizeof(orders[0]));
300
301 ASSERT(init->alloc_no == ERTS_ALC_A_TEST);
302 aoffinit->crr_order = orders[index];
303 }
304
305 alc->blk_order = aoffinit->blk_order;
306 alc->crr_order = aoffinit->crr_order;
307 allctr->mbc_header_size = sizeof(AOFF_Carrier_t);
308 allctr->min_mbc_size = MIN_MBC_SZ;
309 allctr->min_mbc_first_free_size = MIN_MBC_FIRST_FREE_SZ;
310 allctr->min_block_size = sizeof(AOFF_RBTree_t);
311
312 allctr->vsn_str = ERTS_ALC_AOFF_ALLOC_VSN_STR;
313
314
315 /* Callback functions */
316
317 allctr->get_free_block = aoff_get_free_block;
318 allctr->link_free_block = aoff_link_free_block;
319 allctr->unlink_free_block = aoff_unlink_free_block;
320 allctr->info_options = info_options;
321
322 allctr->get_next_mbc_size = NULL;
323 allctr->creating_mbc = aoff_creating_mbc;
324 #ifdef DEBUG
325 allctr->destroying_mbc = aoff_destroying_mbc;
326 #else
327 allctr->destroying_mbc = NULL;
328 #endif
329 allctr->add_mbc = aoff_add_mbc;
330 allctr->remove_mbc = aoff_remove_mbc;
331 allctr->largest_fblk_in_mbc = aoff_largest_fblk_in_mbc;
332 allctr->first_fblk_in_mbc = aoff_first_fblk_in_mbc;
333 allctr->next_fblk_in_mbc = aoff_next_fblk_in_mbc;
334 allctr->init_atoms = init_atoms;
335
336 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
337 allctr->check_block = NULL;
338 allctr->check_mbc = NULL;
339 #endif
340
341 allctr->atoms_initialized = 0;
342
343 if (!erts_alcu_start(allctr, init))
344 return NULL;
345
346 return allctr;
347 }
348
349 /*
350 * Red-Black Tree operations needed
351 */
352
353 static ERTS_INLINE void
left_rotate(AOFF_RBTree_t ** root,AOFF_RBTree_t * x)354 left_rotate(AOFF_RBTree_t **root, AOFF_RBTree_t *x)
355 {
356 AOFF_RBTree_t *y = x->right;
357 x->right = y->left;
358 if (y->left)
359 y->left->parent = x;
360 y->parent = x->parent;
361 if (!y->parent) {
362 RBT_ASSERT(*root == x);
363 *root = y;
364 }
365 else if (x == x->parent->left)
366 x->parent->left = y;
367 else {
368 RBT_ASSERT(x == x->parent->right);
369 x->parent->right = y;
370 }
371 y->left = x;
372 x->parent = y;
373
374 y->max_sz = x->max_sz;
375 x->max_sz = node_max_size(x);
376 ASSERT(y->max_sz >= x->max_sz);
377 }
378
379 static ERTS_INLINE void
right_rotate(AOFF_RBTree_t ** root,AOFF_RBTree_t * x)380 right_rotate(AOFF_RBTree_t **root, AOFF_RBTree_t *x)
381 {
382 AOFF_RBTree_t *y = x->left;
383 x->left = y->right;
384 if (y->right)
385 y->right->parent = x;
386 y->parent = x->parent;
387 if (!y->parent) {
388 RBT_ASSERT(*root == x);
389 *root = y;
390 }
391 else if (x == x->parent->right)
392 x->parent->right = y;
393 else {
394 RBT_ASSERT(x == x->parent->left);
395 x->parent->left = y;
396 }
397 y->right = x;
398 x->parent = y;
399 y->max_sz = x->max_sz;
400 x->max_sz = node_max_size(x);
401 ASSERT(y->max_sz >= x->max_sz);
402 }
403
404
405 /*
406 * Replace node x with node y
407 * NOTE: block header of y is not changed
408 */
409 static ERTS_INLINE void
replace(AOFF_RBTree_t ** root,AOFF_RBTree_t * x,AOFF_RBTree_t * y)410 replace(AOFF_RBTree_t **root, AOFF_RBTree_t *x, AOFF_RBTree_t *y)
411 {
412
413 if (!x->parent) {
414 RBT_ASSERT(*root == x);
415 *root = y;
416 }
417 else if (x == x->parent->left)
418 x->parent->left = y;
419 else {
420 RBT_ASSERT(x == x->parent->right);
421 x->parent->right = y;
422 }
423 if (x->left) {
424 RBT_ASSERT(x->left->parent == x);
425 x->left->parent = y;
426 }
427 if (x->right) {
428 RBT_ASSERT(x->right->parent == x);
429 x->right->parent = y;
430 }
431
432 y->flags = x->flags;
433 y->parent = x->parent;
434 y->right = x->right;
435 y->left = x->left;
436 y->max_sz = x->max_sz;
437 }
438
439 static void
tree_insert_fixup(AOFF_RBTree_t ** root,AOFF_RBTree_t * blk)440 tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk)
441 {
442 AOFF_RBTree_t *x = blk, *y;
443
444 /*
445 * Rearrange the tree so that it satisfies the Red-Black Tree properties
446 */
447
448 RBT_ASSERT(x != *root && IS_RED(x->parent));
449 do {
450
451 /*
452 * x and its parent are both red. Move the red pair up the tree
453 * until we get to the root or until we can separate them.
454 */
455
456 RBT_ASSERT(IS_RED(x));
457 RBT_ASSERT(IS_BLACK(x->parent->parent));
458 RBT_ASSERT(x->parent->parent);
459
460 if (x->parent == x->parent->parent->left) {
461 y = x->parent->parent->right;
462 if (IS_RED(y)) {
463 SET_BLACK(y);
464 x = x->parent;
465 SET_BLACK(x);
466 x = x->parent;
467 SET_RED(x);
468 }
469 else {
470
471 if (x == x->parent->right) {
472 x = x->parent;
473 left_rotate(root, x);
474 }
475
476 RBT_ASSERT(x == x->parent->parent->left->left);
477 RBT_ASSERT(IS_RED(x));
478 RBT_ASSERT(IS_RED(x->parent));
479 RBT_ASSERT(IS_BLACK(x->parent->parent));
480 RBT_ASSERT(IS_BLACK(y));
481
482 SET_BLACK(x->parent);
483 SET_RED(x->parent->parent);
484 right_rotate(root, x->parent->parent);
485
486 RBT_ASSERT(x == x->parent->left);
487 RBT_ASSERT(IS_RED(x));
488 RBT_ASSERT(IS_RED(x->parent->right));
489 RBT_ASSERT(IS_BLACK(x->parent));
490 break;
491 }
492 }
493 else {
494 RBT_ASSERT(x->parent == x->parent->parent->right);
495 y = x->parent->parent->left;
496 if (IS_RED(y)) {
497 SET_BLACK(y);
498 x = x->parent;
499 SET_BLACK(x);
500 x = x->parent;
501 SET_RED(x);
502 }
503 else {
504
505 if (x == x->parent->left) {
506 x = x->parent;
507 right_rotate(root, x);
508 }
509
510 RBT_ASSERT(x == x->parent->parent->right->right);
511 RBT_ASSERT(IS_RED(x));
512 RBT_ASSERT(IS_RED(x->parent));
513 RBT_ASSERT(IS_BLACK(x->parent->parent));
514 RBT_ASSERT(IS_BLACK(y));
515
516 SET_BLACK(x->parent);
517 SET_RED(x->parent->parent);
518 left_rotate(root, x->parent->parent);
519
520 RBT_ASSERT(x == x->parent->right);
521 RBT_ASSERT(IS_RED(x));
522 RBT_ASSERT(IS_RED(x->parent->left));
523 RBT_ASSERT(IS_BLACK(x->parent));
524 break;
525 }
526 }
527 } while (x != *root && IS_RED(x->parent));
528
529 SET_BLACK(*root);
530 }
531
532 static void
aoff_unlink_free_block(Allctr_t * allctr,Block_t * blk)533 aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk)
534 {
535 AOFF_RBTree_t* del = (AOFF_RBTree_t*)blk;
536 AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(&del->hdr);
537
538 (void)allctr;
539
540 ASSERT(crr->rbt_node.hdr.bhdr == crr->root->max_sz);
541 HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
542
543 if (crr->blk_order == FF_BF) {
544 ASSERT(del->flags & IS_BF_FLG);
545 if (IS_LIST_ELEM(del)) {
546 /* Remove from list */
547 ASSERT(AOFF_LIST_PREV(del));
548 ASSERT(AOFF_LIST_PREV(del)->flags & IS_BF_FLG);
549 AOFF_LIST_NEXT(AOFF_LIST_PREV(del)) = AOFF_LIST_NEXT(del);
550 if (AOFF_LIST_NEXT(del)) {
551 ASSERT(AOFF_LIST_NEXT(del)->flags & IS_BF_FLG);
552 AOFF_LIST_PREV(AOFF_LIST_NEXT(del)) = AOFF_LIST_PREV(del);
553 }
554 return;
555 }
556 else if (AOFF_LIST_NEXT(del)) {
557 /* Replace tree node by next element in list... */
558
559 ASSERT(AOFF_BLK_SZ(AOFF_LIST_NEXT(del)) == AOFF_BLK_SZ(del));
560 ASSERT(IS_LIST_ELEM(AOFF_LIST_NEXT(del)));
561
562 replace(&crr->root, (AOFF_RBTree_t*)del, AOFF_LIST_NEXT(del));
563
564 HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
565 return;
566 }
567 }
568
569 rbt_delete(&crr->root, (AOFF_RBTree_t*)del);
570
571 HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
572
573 /* Update the carrier tree with a potentially new (lower) max_sz
574 */
575 if (crr->root) {
576 if (crr->rbt_node.hdr.bhdr == crr->root->max_sz) {
577 return;
578 }
579 ASSERT(crr->rbt_node.hdr.bhdr > crr->root->max_sz);
580 crr->rbt_node.hdr.bhdr = crr->root->max_sz;
581 }
582 else {
583 crr->rbt_node.hdr.bhdr = 0;
584 }
585 lower_max_size(&crr->rbt_node, NULL);
586 }
587
588
589 static void
rbt_delete(AOFF_RBTree_t ** root,AOFF_RBTree_t * del)590 rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
591 {
592 Uint spliced_is_black;
593 AOFF_RBTree_t *x, *y, *z = del;
594 AOFF_RBTree_t null_x; /* null_x is used to get the fixup started when we
595 splice out a node without children. */
596
597 HARD_CHECK_IS_MEMBER(*root, del);
598
599 null_x.parent = NULL;
600
601 /* Remove node from tree... */
602
603 /* Find node to splice out */
604 if (!z->left || !z->right)
605 y = z;
606 else
607 /* Set y to z:s successor */
608 for(y = z->right; y->left; y = y->left);
609 /* splice out y */
610 x = y->left ? y->left : y->right;
611 spliced_is_black = IS_BLACK(y);
612 if (x) {
613 x->parent = y->parent;
614 }
615 else if (spliced_is_black) {
616 x = &null_x;
617 x->flags = 0;
618 SET_BLACK(x);
619 x->right = x->left = NULL;
620 x->max_sz = 0;
621 x->parent = y->parent;
622 y->left = x;
623 }
624
625 if (!y->parent) {
626 RBT_ASSERT(*root == y);
627 *root = x;
628 }
629 else {
630 if (y == y->parent->left) {
631 y->parent->left = x;
632 }
633 else {
634 RBT_ASSERT(y == y->parent->right);
635 y->parent->right = x;
636 }
637 if (y->parent != z) {
638 lower_max_size(y->parent, (y==z ? NULL : z));
639 }
640 }
641 if (y != z) {
642 /* We spliced out the successor of z; replace z by the successor */
643 ASSERT(z != &null_x);
644 replace(root, z, y);
645 lower_max_size(y, NULL);
646 }
647
648 if (spliced_is_black) {
649 /* We removed a black node which makes the resulting tree
650 violate the Red-Black Tree properties. Fixup tree... */
651
652 while (IS_BLACK(x) && x->parent) {
653
654 /*
655 * x has an "extra black" which we move up the tree
656 * until we reach the root or until we can get rid of it.
657 *
658 * y is the sibbling of x
659 */
660
661 if (x == x->parent->left) {
662 y = x->parent->right;
663 RBT_ASSERT(y);
664 if (IS_RED(y)) {
665 RBT_ASSERT(y->right);
666 RBT_ASSERT(y->left);
667 SET_BLACK(y);
668 RBT_ASSERT(IS_BLACK(x->parent));
669 SET_RED(x->parent);
670 left_rotate(root, x->parent);
671 y = x->parent->right;
672 }
673 RBT_ASSERT(y);
674 RBT_ASSERT(IS_BLACK(y));
675 if (IS_BLACK(y->left) && IS_BLACK(y->right)) {
676 SET_RED(y);
677 x = x->parent;
678 }
679 else {
680 if (IS_BLACK(y->right)) {
681 SET_BLACK(y->left);
682 SET_RED(y);
683 right_rotate(root, y);
684 y = x->parent->right;
685 }
686 RBT_ASSERT(y);
687 if (IS_RED(x->parent)) {
688
689 SET_BLACK(x->parent);
690 SET_RED(y);
691 }
692 RBT_ASSERT(y->right);
693 SET_BLACK(y->right);
694 left_rotate(root, x->parent);
695 x = *root;
696 break;
697 }
698 }
699 else {
700 RBT_ASSERT(x == x->parent->right);
701 y = x->parent->left;
702 RBT_ASSERT(y);
703 if (IS_RED(y)) {
704 RBT_ASSERT(y->right);
705 RBT_ASSERT(y->left);
706 SET_BLACK(y);
707 RBT_ASSERT(IS_BLACK(x->parent));
708 SET_RED(x->parent);
709 right_rotate(root, x->parent);
710 y = x->parent->left;
711 }
712 RBT_ASSERT(y);
713 RBT_ASSERT(IS_BLACK(y));
714 if (IS_BLACK(y->right) && IS_BLACK(y->left)) {
715 SET_RED(y);
716 x = x->parent;
717 }
718 else {
719 if (IS_BLACK(y->left)) {
720 SET_BLACK(y->right);
721 SET_RED(y);
722 left_rotate(root, y);
723 y = x->parent->left;
724 }
725 RBT_ASSERT(y);
726 if (IS_RED(x->parent)) {
727 SET_BLACK(x->parent);
728 SET_RED(y);
729 }
730 RBT_ASSERT(y->left);
731 SET_BLACK(y->left);
732 right_rotate(root, x->parent);
733 x = *root;
734 break;
735 }
736 }
737 }
738 SET_BLACK(x);
739
740 if (null_x.parent) {
741 if (null_x.parent->left == &null_x)
742 null_x.parent->left = NULL;
743 else {
744 RBT_ASSERT(null_x.parent->right == &null_x);
745 null_x.parent->right = NULL;
746 }
747 RBT_ASSERT(!null_x.left);
748 RBT_ASSERT(!null_x.right);
749 }
750 else if (*root == &null_x) {
751 *root = NULL;
752 RBT_ASSERT(!null_x.left);
753 RBT_ASSERT(!null_x.right);
754 }
755 }
756 }
757
758 static void
aoff_link_free_block(Allctr_t * allctr,Block_t * block)759 aoff_link_free_block(Allctr_t *allctr, Block_t *block)
760 {
761 AOFF_RBTree_t *blk = (AOFF_RBTree_t *) block;
762 AOFF_RBTree_t *crr_node;
763 AOFF_Carrier_t *blk_crr = (AOFF_Carrier_t*) FBLK_TO_MBC(block);
764 Uint blk_sz = AOFF_BLK_SZ(blk);
765
766 (void)allctr;
767
768 ASSERT(allctr == ERTS_ALC_CARRIER_TO_ALLCTR(&blk_crr->crr));
769 ASSERT(blk_crr->rbt_node.hdr.bhdr == (blk_crr->root ? blk_crr->root->max_sz : 0));
770 HARD_CHECK_TREE(&blk_crr->crr, blk_crr->blk_order, blk_crr->root, 0);
771
772 rbt_insert(blk_crr->blk_order, &blk_crr->root, blk);
773
774 /*
775 * Update carrier tree with a potentially new (larger) max_sz
776 */
777 crr_node = &blk_crr->rbt_node;
778 if (blk_sz > crr_node->hdr.bhdr) {
779 ASSERT(blk_sz == blk_crr->root->max_sz);
780 crr_node->hdr.bhdr = blk_sz;
781 while (blk_sz > crr_node->max_sz) {
782 crr_node->max_sz = blk_sz;
783 crr_node = crr_node->parent;
784 if (!crr_node) break;
785 }
786 }
787 HARD_CHECK_TREE(NULL, alc->crr_order, alc->mbc_root, 0);
788 }
789
790 static void
rbt_insert(enum AOFFSortOrder order,AOFF_RBTree_t ** root,AOFF_RBTree_t * blk)791 rbt_insert(enum AOFFSortOrder order, AOFF_RBTree_t** root, AOFF_RBTree_t* blk)
792 {
793 Uint blk_sz = AOFF_BLK_SZ(blk);
794
795 #ifdef DEBUG
796 blk->flags = (order == FF_BF) ? IS_BF_FLG : 0;
797 #else
798 blk->flags = 0;
799 #endif
800 blk->left = NULL;
801 blk->right = NULL;
802 blk->max_sz = blk_sz;
803
804 if (!*root) {
805 blk->parent = NULL;
806 SET_BLACK(blk);
807 *root = blk;
808 }
809 else {
810 AOFF_RBTree_t *x = *root;
811 while (1) {
812 SWord diff;
813 if (x->max_sz < blk_sz) {
814 x->max_sz = blk_sz;
815 }
816 diff = cmp_blocks(order, blk, x);
817 if (diff < 0) {
818 if (!x->left) {
819 blk->parent = x;
820 x->left = blk;
821 break;
822 }
823 x = x->left;
824 }
825 else if (diff > 0) {
826 if (!x->right) {
827 blk->parent = x;
828 x->right = blk;
829 break;
830 }
831 x = x->right;
832 }
833 else {
834 ASSERT(order == FF_BF);
835 ASSERT(blk->flags & IS_BF_FLG);
836 ASSERT(x->flags & IS_BF_FLG);
837 SET_LIST_ELEM(blk);
838 AOFF_LIST_NEXT(blk) = AOFF_LIST_NEXT(x);
839 AOFF_LIST_PREV(blk) = x;
840 if (AOFF_LIST_NEXT(x))
841 AOFF_LIST_PREV(AOFF_LIST_NEXT(x)) = blk;
842 AOFF_LIST_NEXT(x) = blk;
843 return;
844 }
845 }
846
847 /* Insert block into size tree */
848 RBT_ASSERT(blk->parent);
849
850 SET_RED(blk);
851 if (IS_RED(blk->parent))
852 tree_insert_fixup(root, blk);
853 }
854 if (order == FF_BF) {
855 SET_TREE_NODE(blk);
856 AOFF_LIST_NEXT(blk) = NULL;
857 }
858 }
859
860 static AOFF_RBTree_t*
rbt_search(AOFF_RBTree_t * root,Uint size)861 rbt_search(AOFF_RBTree_t* root, Uint size)
862 {
863 AOFF_RBTree_t* x = root;
864
865 ASSERT(x);
866 for (;;) {
867 if (x->left && x->left->max_sz >= size) {
868 x = x->left;
869 }
870 else if (AOFF_BLK_SZ(x) >= size) {
871 return x;
872 }
873 else {
874 x = x->right;
875 if (!x) {
876 return NULL;
877 }
878 }
879 }
880 }
881
aoff_lookup_pooled_mbc(Allctr_t * allctr,Uint size)882 Carrier_t* aoff_lookup_pooled_mbc(Allctr_t* allctr, Uint size)
883 {
884 AOFF_RBTree_t* node;
885
886 if (!allctr->cpool.pooled_tree)
887 return NULL;
888 node = rbt_search(allctr->cpool.pooled_tree, size);
889 return node ? ErtsContainerStruct(node, Carrier_t, cpool.pooled) : NULL;
890 }
891
892 static Block_t *
aoff_get_free_block(Allctr_t * allctr,Uint size,Block_t * cand_blk,Uint cand_size)893 aoff_get_free_block(Allctr_t *allctr, Uint size,
894 Block_t *cand_blk, Uint cand_size)
895 {
896 AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
897 AOFF_RBTree_t *crr_node = alc->mbc_root;
898 AOFF_Carrier_t* crr;
899 AOFF_RBTree_t *blk = NULL;
900 #ifdef HARD_DEBUG
901 AOFF_RBTree_t* dbg_blk;
902 #endif
903
904 ASSERT(!cand_blk || cand_size >= size);
905
906 /* Get first-fit carrier
907 */
908 if (!crr_node || !(blk=rbt_search(crr_node, size))) {
909 return NULL;
910 }
911 crr = RBT_NODE_TO_MBC(blk);
912
913 /* Get block within carrier tree
914 */
915 #ifdef HARD_DEBUG
916 dbg_blk = HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, size);
917 #endif
918
919 blk = rbt_search(crr->root, size);
920 ASSERT(blk);
921
922 #ifdef HARD_DEBUG
923 ASSERT(blk == dbg_blk);
924 #endif
925
926 if (!blk)
927 return NULL;
928
929 if (cand_blk && cmp_cand_blk(crr->blk_order, cand_blk, blk) < 0) {
930 return NULL; /* cand_blk was better */
931 }
932
933 aoff_unlink_free_block(allctr, (Block_t *) blk);
934
935 return (Block_t *) blk;
936 }
937
get_birth_time(void)938 static ERTS_INLINE Sint64 get_birth_time(void)
939 {
940 #ifdef ERTS_HAVE_OS_MONOTONIC_TIME_SUPPORT
941 return (Sint64) erts_os_monotonic_time();
942 #else
943 return (Sint64) erts_atomic64_inc_read_nob(&birth_time_counter);
944 #endif
945 }
946
aoff_creating_mbc(Allctr_t * allctr,Carrier_t * carrier)947 static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier)
948 {
949 AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
950 AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
951 AOFF_RBTree_t **root = &alc->mbc_root;
952 Sint64 bt = get_birth_time();
953
954 HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
955
956 crr->rbt_node.hdr.bhdr = 0;
957
958 /* While birth time is only used for FF_AGEFF, we have to set it for all
959 * types as we can be migrated to an instance that uses it and we don't
960 * want to mess its order up. */
961 crr->rbt_node.u.birth_time = bt;
962 crr->crr.cpool.pooled.u.birth_time = bt;
963
964 rbt_insert(alc->crr_order, root, &crr->rbt_node);
965
966 /* aoff_link_free_block will add free block later */
967 crr->root = NULL;
968
969 HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
970
971 /* When a carrier has been migrated, its block order may differ from that
972 * of the allocator it's been migrated to. */
973 crr->blk_order = alc->blk_order;
974 }
975
976 #define IS_CRR_IN_TREE(CRR,ROOT) \
977 ((CRR)->rbt_node.parent || (ROOT) == &(CRR)->rbt_node)
978
979 #ifdef DEBUG
aoff_destroying_mbc(Allctr_t * allctr,Carrier_t * carrier)980 static void aoff_destroying_mbc(Allctr_t *allctr, Carrier_t *carrier)
981 {
982 AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
983 AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
984
985 ASSERT(!IS_CRR_IN_TREE(crr, alc->mbc_root));
986 }
987 #endif
988
aoff_add_mbc(Allctr_t * allctr,Carrier_t * carrier)989 static void aoff_add_mbc(Allctr_t *allctr, Carrier_t *carrier)
990 {
991 AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
992 AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
993 AOFF_RBTree_t **root = &alc->mbc_root;
994
995 ASSERT(!IS_CRR_IN_TREE(crr, *root));
996 HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
997
998 rbt_insert(alc->crr_order, root, &crr->rbt_node);
999
1000 HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
1001 }
1002
aoff_add_pooled_mbc(Allctr_t * allctr,Carrier_t * crr)1003 void aoff_add_pooled_mbc(Allctr_t *allctr, Carrier_t *crr)
1004 {
1005 AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
1006 AOFF_RBTree_t **root = &allctr->cpool.pooled_tree;
1007
1008 ASSERT(allctr == crr->cpool.orig_allctr);
1009 HARD_CHECK_TREE(NULL, 0, *root, 0);
1010
1011 /* Link carrier in address order tree
1012 */
1013 rbt_insert(alc->crr_order, root, &crr->cpool.pooled);
1014
1015 HARD_CHECK_TREE(NULL, 0, *root, 0);
1016 }
1017
aoff_remove_mbc(Allctr_t * allctr,Carrier_t * carrier)1018 static void aoff_remove_mbc(Allctr_t *allctr, Carrier_t *carrier)
1019 {
1020 AOFF_RBTree_t **root = &((AOFFAllctr_t*)allctr)->mbc_root;
1021 AOFF_Carrier_t *crr = (AOFF_Carrier_t*)carrier;
1022
1023 ASSERT(allctr == ERTS_ALC_CARRIER_TO_ALLCTR(carrier));
1024
1025 if (!IS_CRR_IN_TREE(crr,*root))
1026 return;
1027
1028 HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
1029
1030 rbt_delete(root, &crr->rbt_node);
1031 crr->rbt_node.parent = NULL;
1032 crr->rbt_node.left = NULL;
1033 crr->rbt_node.right = NULL;
1034 crr->rbt_node.max_sz = crr->rbt_node.hdr.bhdr;
1035
1036 HARD_CHECK_TREE(NULL, alc->crr_order, *root, 0);
1037 }
1038
aoff_remove_pooled_mbc(Allctr_t * allctr,Carrier_t * crr)1039 void aoff_remove_pooled_mbc(Allctr_t *allctr, Carrier_t *crr)
1040 {
1041 ASSERT(allctr == crr->cpool.orig_allctr);
1042
1043 HARD_CHECK_TREE(NULL, 0, allctr->cpool.pooled_tree, 0);
1044
1045 rbt_delete(&allctr->cpool.pooled_tree, &crr->cpool.pooled);
1046 #ifdef DEBUG
1047 crr->cpool.pooled.parent = NULL;
1048 crr->cpool.pooled.left = NULL;
1049 crr->cpool.pooled.right = NULL;
1050 crr->cpool.pooled.max_sz = 0;
1051 #endif
1052 HARD_CHECK_TREE(NULL, 0, allctr->cpool.pooled_tree, 0);
1053
1054 }
1055
1056
aoff_largest_fblk_in_mbc(Allctr_t * allctr,Carrier_t * carrier)1057 static UWord aoff_largest_fblk_in_mbc(Allctr_t* allctr, Carrier_t* carrier)
1058 {
1059 AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
1060
1061 ASSERT(allctr == ERTS_ALC_CARRIER_TO_ALLCTR(carrier));
1062 ASSERT(crr->rbt_node.hdr.bhdr == (crr->root ? crr->root->max_sz : 0));
1063 return crr->rbt_node.hdr.bhdr;
1064 }
1065
aoff_first_fblk_in_mbc(Allctr_t * allctr,Carrier_t * carrier)1066 static Block_t *aoff_first_fblk_in_mbc(Allctr_t *allctr, Carrier_t *carrier)
1067 {
1068 AOFF_Carrier_t *crr = (AOFF_Carrier_t*)carrier;
1069
1070 (void)allctr;
1071
1072 if (crr->root) {
1073 AOFF_RBTree_t *blk;
1074
1075 /* Descend to the rightmost block of the tree. */
1076 for (blk = crr->root; blk->right; blk = blk->right);
1077
1078 return (Block_t*)blk;
1079 }
1080
1081 return NULL;
1082 }
1083
aoff_next_fblk_in_mbc(Allctr_t * allctr,Carrier_t * carrier,Block_t * block)1084 static Block_t *aoff_next_fblk_in_mbc(Allctr_t *allctr, Carrier_t *carrier,
1085 Block_t *block)
1086 {
1087 AOFF_RBTree_t *parent, *blk;
1088
1089 (void)allctr;
1090 (void)carrier;
1091
1092 blk = (AOFF_RBTree_t*)block;
1093
1094 if (blk->left) {
1095 /* Descend to the rightmost block of the left subtree. */
1096 for (blk = blk->left; blk->right; blk = blk->right);
1097
1098 return (Block_t*)blk;
1099 }
1100
1101 while (blk->parent) {
1102 parent = blk->parent;
1103
1104 /* If we ascend from the right we know we haven't visited our parent
1105 * yet, because we always descend as far as we can to the right when
1106 * entering a subtree. */
1107 if (parent->right == blk) {
1108 ASSERT(parent->left != blk);
1109 return (Block_t*)parent;
1110 }
1111
1112 /* If we ascend from the left we know we've already visited our
1113 * parent, and will need to keep ascending until we do so from the
1114 * right or reach the end of the tree. */
1115 ASSERT(parent->left == blk);
1116 blk = parent;
1117 }
1118
1119 return NULL;
1120 }
1121
1122 /*
1123 * info_options()
1124 */
1125
1126 static const char* flavor_str[2][3] = {
1127 {"ageffcaoff", "ageffcaobf", "ageffcbf"},
1128 { "aoff", "aoffcaobf", "aoffcbf"}
1129 };
1130 static Eterm flavor_atoms[2][3];
1131
1132 static struct {
1133 Eterm as;
1134 } am;
1135
atom_init(Eterm * atom,const char * name)1136 static void ERTS_INLINE atom_init(Eterm *atom, const char *name)
1137 {
1138 *atom = am_atom_put(name, sys_strlen(name));
1139 }
1140 #define AM_INIT(AM) atom_init(&am.AM, #AM)
1141
1142 static void
init_atoms(void)1143 init_atoms(void)
1144 {
1145 int i, j;
1146
1147 if (atoms_initialized)
1148 return;
1149
1150 AM_INIT(as);
1151
1152 for (i = 0; i < 2; i++)
1153 for (j = 0; j < 3; j++)
1154 atom_init(&flavor_atoms[i][j], flavor_str[i][j]);
1155
1156 atoms_initialized = 1;
1157 }
1158
1159
1160 #define bld_uint erts_bld_uint
1161 #define bld_cons erts_bld_cons
1162 #define bld_tuple erts_bld_tuple
1163
1164 static ERTS_INLINE void
add_2tup(Uint ** hpp,Uint * szp,Eterm * lp,Eterm el1,Eterm el2)1165 add_2tup(Uint **hpp, Uint *szp, Eterm *lp, Eterm el1, Eterm el2)
1166 {
1167 *lp = bld_cons(hpp, szp, bld_tuple(hpp, szp, 2, el1, el2), *lp);
1168 }
1169
1170 static Eterm
info_options(Allctr_t * allctr,char * prefix,fmtfn_t * print_to_p,void * print_to_arg,Uint ** hpp,Uint * szp)1171 info_options(Allctr_t *allctr,
1172 char *prefix,
1173 fmtfn_t *print_to_p,
1174 void *print_to_arg,
1175 Uint **hpp,
1176 Uint *szp)
1177 {
1178 AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
1179 Eterm res = THE_NON_VALUE;
1180
1181 ASSERT(alc->crr_order >= 0 && alc->crr_order <= 1);
1182 ASSERT(alc->blk_order >= 1 && alc->blk_order <= 3);
1183
1184 if (print_to_p) {
1185 erts_print(*print_to_p,
1186 print_to_arg,
1187 "%sas: %s\n",
1188 prefix,
1189 flavor_str[alc->crr_order][alc->blk_order-1]);
1190 }
1191
1192 if (hpp || szp) {
1193
1194 if (!atoms_initialized)
1195 erts_exit(ERTS_ERROR_EXIT, "%s:%d: Internal error: Atoms not initialized",
1196 __FILE__, __LINE__);;
1197
1198 res = NIL;
1199 add_2tup(hpp, szp, &res, am.as,
1200 flavor_atoms[alc->crr_order][alc->blk_order-1]);
1201 }
1202
1203 return res;
1204 }
1205
1206
1207 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
1208 * NOTE: erts_aoffalc_test() is only supposed to be used for testing. *
1209 * *
1210 * Keep alloc_SUITE_data/allocator_test.h updated if changes are made *
1211 * to erts_aoffalc_test() *
1212 \* */
1213
1214 UWord
erts_aoffalc_test(UWord op,UWord a1,UWord a2)1215 erts_aoffalc_test(UWord op, UWord a1, UWord a2)
1216 {
1217 switch (op) {
1218 case 0x500: return (UWord) ((AOFFAllctr_t *) a1)->blk_order == FF_AOBF;
1219 case 0x501: {
1220 AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root;
1221 Uint size = (Uint) a2;
1222 node = node ? rbt_search(node, size) : NULL;
1223 return (UWord) (node ? RBT_NODE_TO_MBC(node)->root : NULL);
1224 }
1225 case 0x502: return (UWord) ((AOFF_RBTree_t *) a1)->parent;
1226 case 0x503: return (UWord) ((AOFF_RBTree_t *) a1)->left;
1227 case 0x504: return (UWord) ((AOFF_RBTree_t *) a1)->right;
1228 case 0x505: return (UWord) AOFF_LIST_NEXT(a1);
1229 case 0x506: return (UWord) IS_BLACK((AOFF_RBTree_t *) a1);
1230 case 0x507: return (UWord) IS_TREE_NODE((AOFF_RBTree_t *) a1);
1231 case 0x508: return (UWord) 0; /* IS_BF_ALGO */
1232 case 0x509: return (UWord) ((AOFF_RBTree_t *) a1)->max_sz;
1233 case 0x50a: return (UWord) ((AOFFAllctr_t *) a1)->blk_order == FF_BF;
1234 case 0x50b: return (UWord) AOFF_LIST_PREV(a1);
1235 default: ASSERT(0); return ~((UWord) 0);
1236 }
1237 }
1238
1239
1240 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
1241 * Debug functions *
1242 \* */
1243
1244
1245 #ifdef HARD_DEBUG
rbt_is_member(AOFF_RBTree_t * root,AOFF_RBTree_t * node)1246 static int rbt_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node)
1247 {
1248 while (node != root) {
1249 if (!node->parent || (node->parent->left != node &&
1250 node->parent->right != node)) {
1251 return 0;
1252 }
1253 node = node->parent;
1254 }
1255 return 1;
1256 }
1257
1258 #define IS_LEFT_VISITED(FB) ((FB)->flags & LEFT_VISITED_FLG)
1259 #define IS_RIGHT_VISITED(FB) ((FB)->flags & RIGHT_VISITED_FLG)
1260
1261 #define SET_LEFT_VISITED(FB) ((FB)->flags |= LEFT_VISITED_FLG)
1262 #define SET_RIGHT_VISITED(FB) ((FB)->flags |= RIGHT_VISITED_FLG)
1263
1264 #define UNSET_LEFT_VISITED(FB) ((FB)->flags &= ~LEFT_VISITED_FLG)
1265 #define UNSET_RIGHT_VISITED(FB) ((FB)->flags &= ~RIGHT_VISITED_FLG)
1266
1267
1268 #if 0
1269 # define PRINT_TREE
1270 #else
1271 # undef PRINT_TREE
1272 #endif
1273
1274 #ifdef PRINT_TREE
1275 static void print_tree(AOFF_RBTree_t*);
1276 #endif
1277
1278 /*
1279 * Checks that the order between parent and children are correct,
1280 * and that the Red-Black Tree properies are satisfied. if size > 0,
1281 * check_tree() returns the node that satisfies "address order first fit"
1282 *
1283 * The Red-Black Tree properies are:
1284 * 1. Every node is either red or black.
1285 * 2. Every leaf (NIL) is black.
1286 * 3. If a node is red, then both its children are black.
1287 * 4. Every simple path from a node to a descendant leaf
1288 * contains the same number of black nodes.
1289 *
1290 * + own.max_size == MAX(own.size, left.max_size, right.max_size)
1291 */
1292
1293 static AOFF_RBTree_t *
check_tree(Carrier_t * within_crr,enum AOFFSortOrder order,AOFF_RBTree_t * root,Uint size)1294 check_tree(Carrier_t* within_crr, enum AOFFSortOrder order, AOFF_RBTree_t* root, Uint size)
1295 {
1296 AOFF_RBTree_t *res = NULL;
1297 Sint blacks;
1298 Sint curr_blacks;
1299 AOFF_RBTree_t *x;
1300 Carrier_t* crr;
1301 Uint depth, max_depth, node_cnt;
1302
1303 #ifdef PRINT_TREE
1304 print_tree(root);
1305 #endif
1306 ASSERT((within_crr && order >= FF_AOFF) ||
1307 (!within_crr && order <= FF_AOFF));
1308
1309 if (!root)
1310 return res;
1311
1312 x = root;
1313 ASSERT(IS_BLACK(x));
1314 ASSERT(!x->parent);
1315 curr_blacks = 1;
1316 blacks = -1;
1317 depth = 1;
1318 max_depth = 0;
1319 node_cnt = 0;
1320
1321 while (x) {
1322 if (!IS_LEFT_VISITED(x)) {
1323 SET_LEFT_VISITED(x);
1324 if (x->left) {
1325 x = x->left;
1326 ++depth;
1327 if (IS_BLACK(x))
1328 curr_blacks++;
1329 continue;
1330 }
1331 else {
1332 if (blacks < 0)
1333 blacks = curr_blacks;
1334 ASSERT(blacks == curr_blacks);
1335 }
1336 }
1337
1338 if (!IS_RIGHT_VISITED(x)) {
1339 SET_RIGHT_VISITED(x);
1340 if (x->right) {
1341 x = x->right;
1342 ++depth;
1343 if (IS_BLACK(x))
1344 curr_blacks++;
1345 continue;
1346 }
1347 else {
1348 if (blacks < 0)
1349 blacks = curr_blacks;
1350 ASSERT(blacks == curr_blacks);
1351 }
1352 }
1353
1354 ++node_cnt;
1355 if (depth > max_depth)
1356 max_depth = depth;
1357
1358 if (within_crr) {
1359 crr = FBLK_TO_MBC(&x->hdr);
1360 ASSERT(crr == within_crr);
1361 ASSERT((char*)x > (char*)crr);
1362 ASSERT(((char*)x + AOFF_BLK_SZ(x)) <= ((char*)crr + CARRIER_SZ(crr)));
1363
1364 }
1365 if (order == FF_BF) {
1366 AOFF_RBTree_t* y = x;
1367 AOFF_RBTree_t* nxt = AOFF_LIST_NEXT(y);
1368 ASSERT(IS_TREE_NODE(x));
1369 while (nxt) {
1370 ASSERT(IS_LIST_ELEM(nxt));
1371 ASSERT(AOFF_BLK_SZ(nxt) == AOFF_BLK_SZ(x));
1372 ASSERT(FBLK_TO_MBC(&nxt->hdr) == within_crr);
1373 ASSERT(AOFF_LIST_PREV(nxt) == y);
1374 y = nxt;
1375 nxt = AOFF_LIST_NEXT(nxt);
1376 }
1377 }
1378
1379 if (IS_RED(x)) {
1380 ASSERT(IS_BLACK(x->right));
1381 ASSERT(IS_BLACK(x->left));
1382 }
1383
1384 ASSERT(x->parent || x == root);
1385
1386 if (x->left) {
1387 ASSERT(x->left->parent == x);
1388 ASSERT(cmp_blocks(order, x->left, x) < 0);
1389 ASSERT(x->left->max_sz <= x->max_sz);
1390 }
1391
1392 if (x->right) {
1393 ASSERT(x->right->parent == x);
1394 ASSERT(cmp_blocks(order, x->right, x) > 0);
1395 ASSERT(x->right->max_sz <= x->max_sz);
1396 }
1397 ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
1398 ASSERT(x->max_sz == AOFF_BLK_SZ(x)
1399 || x->max_sz == (x->left ? x->left->max_sz : 0)
1400 || x->max_sz == (x->right ? x->right->max_sz : 0));
1401
1402 if (size && AOFF_BLK_SZ(x) >= size) {
1403 if (!res || cmp_blocks(order, x, res) < 0) {
1404 res = x;
1405 }
1406 }
1407
1408 UNSET_LEFT_VISITED(x);
1409 UNSET_RIGHT_VISITED(x);
1410 if (IS_BLACK(x))
1411 curr_blacks--;
1412 x = x->parent;
1413 --depth;
1414 }
1415 ASSERT(depth == 0 || (!root && depth==1));
1416 ASSERT(curr_blacks == 0);
1417 ASSERT((1 << (max_depth/2)) <= node_cnt);
1418
1419 UNSET_LEFT_VISITED(root);
1420 UNSET_RIGHT_VISITED(root);
1421
1422 return res;
1423
1424 }
1425
1426
1427 #ifdef PRINT_TREE
1428 #define INDENT_STEP 2
1429
1430 #include <stdio.h>
1431
1432 static void
print_tree_aux(AOFF_RBTree_t * x,int indent)1433 print_tree_aux(AOFF_RBTree_t *x, int indent)
1434 {
1435 int i;
1436
1437 if (x) {
1438 print_tree_aux(x->right, indent + INDENT_STEP);
1439 for (i = 0; i < indent; i++) {
1440 putc(' ', stderr);
1441 }
1442 fprintf(stderr, "%s: sz=%lu addr=0x%lx max_size=%u\r\n",
1443 IS_BLACK(x) ? "BLACK" : "RED",
1444 AOFF_BLK_SZ(x), (Uint)x, (unsigned)x->max_sz);
1445 print_tree_aux(x->left, indent + INDENT_STEP);
1446 }
1447 }
1448
1449
1450 static void
print_tree(AOFF_RBTree_t * root)1451 print_tree(AOFF_RBTree_t* root)
1452 {
1453 fprintf(stderr, " --- AOFF tree begin ---\r\n");
1454 print_tree_aux(root, 0);
1455 fprintf(stderr, " --- AOFF tree end ---\r\n");
1456 }
1457
1458 #endif /* PRINT_TREE */
1459
1460 #endif /* HARD_DEBUG */
1461