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
71 #define TREE_NODE_FLG (((Uint) 1) << 0)
72 #define RED_FLG (((Uint) 1) << 1)
73 #ifdef HARD_DEBUG
74 # define LEFT_VISITED_FLG (((Uint) 1) << 2)
75 # define RIGHT_VISITED_FLG (((Uint) 1) << 3)
76 #endif
77 #ifdef DEBUG
78 # define IS_BF_FLG (((Uint) 1) << 4)
79 #endif
80
81 #define IS_TREE_NODE(N) (((AOFF_RBTree_t *) (N))->flags & TREE_NODE_FLG)
82 #define IS_LIST_ELEM(N) (!IS_TREE_NODE(((AOFF_RBTree_t *) (N))))
83
84 #define SET_TREE_NODE(N) (((AOFF_RBTree_t *) (N))->flags |= TREE_NODE_FLG)
85 #define SET_LIST_ELEM(N) (((AOFF_RBTree_t *) (N))->flags &= ~TREE_NODE_FLG)
86
87 #define IS_RED(N) (((AOFF_RBTree_t *) (N)) \
88 && ((AOFF_RBTree_t *) (N))->flags & RED_FLG)
89 #define IS_BLACK(N) (!IS_RED(((AOFF_RBTree_t *) (N))))
90
91 #define SET_RED(N) (((AOFF_RBTree_t *) (N))->flags |= RED_FLG)
92 #define SET_BLACK(N) (((AOFF_RBTree_t *) (N))->flags &= ~RED_FLG)
93
94 #if 1
95 #define RBT_ASSERT ASSERT
96 #else
97 #define RBT_ASSERT(x)
98 #endif
99
100 #define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
101
102 #define AOFF_LIST_NEXT(N) (((AOFF_RBTree_t*)(N))->u.next)
103 #define AOFF_LIST_PREV(N) (((AOFF_RBTree_t*)(N))->parent)
104
105 typedef struct AOFF_Carrier_t_ AOFF_Carrier_t;
106
107 struct AOFF_Carrier_t_ {
108 Carrier_t crr;
109 AOFF_RBTree_t rbt_node; /* My node in the carrier tree */
110 AOFF_RBTree_t* root; /* Root of my block tree */
111 enum AOFFSortOrder blk_order;
112 };
113
114 #define RBT_NODE_TO_MBC(PTR) ErtsContainerStruct((PTR), AOFF_Carrier_t, rbt_node)
115
116 /*
117 To support carrier migration we keep two kinds of rb-trees:
118 1. One tree of carriers for each allocator instance.
119 2. One tree of free blocks for each carrier.
120 Both trees use the same node structure AOFF_RBTree_t and implementation.
121 Carrier nodes thus contain a phony Block_t header 'rbt_node.hdr'.
122 The size value of such a phony block is the size of the largest free block in
123 that carrier, i.e same as 'max_sz' of the root node of its block tree.
124 */
125
126 #ifdef HARD_DEBUG
127 # define HARD_CHECK_IS_MEMBER(ROOT,NODE) ASSERT(rbt_is_member(ROOT,NODE))
128 # define HARD_CHECK_TREE(CRR,ORDER,ROOT,SZ) check_tree(CRR, ORDER, ROOT, SZ)
129 static AOFF_RBTree_t * check_tree(Carrier_t*, enum AOFFSortOrder, AOFF_RBTree_t*, Uint);
130 #else
131 # define HARD_CHECK_IS_MEMBER(ROOT,NODE)
132 # define HARD_CHECK_TREE(CRR,ORDER,ROOT,SZ)
133 #endif
134
135
136 /* Calculate 'max_sz' of tree node x by only looking at 'max_sz' of the
137 * direct children of x and the size x itself.
138 */
node_max_size(AOFF_RBTree_t * x)139 static ERTS_INLINE Uint node_max_size(AOFF_RBTree_t *x)
140 {
141 Uint sz = AOFF_BLK_SZ(x);
142 if (x->left && x->left->max_sz > sz) {
143 sz = x->left->max_sz;
144 }
145 if (x->right && x->right->max_sz > sz) {
146 sz = x->right->max_sz;
147 }
148 return sz;
149 }
150
151 /* Set new possibly lower 'max_sz' of node and propagate change toward root
152 */
lower_max_size(AOFF_RBTree_t * node,AOFF_RBTree_t * stop_at)153 static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
154 AOFF_RBTree_t* stop_at)
155 {
156 AOFF_RBTree_t* x = node;
157 Uint old_max = x->max_sz;
158 Uint new_max = node_max_size(x);
159
160 if (new_max < old_max) {
161 x->max_sz = new_max;
162 while ((x=x->parent) != stop_at && x->max_sz == old_max) {
163 x->max_sz = node_max_size(x);
164 }
165 ASSERT(x == stop_at || x->max_sz > old_max);
166 }
167 else ASSERT(new_max == old_max);
168 }
169
170 /*
171 * Set possibly new larger 'max_sz' of node and propagate change toward root
172 */
erts_aoff_larger_max_size(AOFF_RBTree_t * node)173 void erts_aoff_larger_max_size(AOFF_RBTree_t *node)
174 {
175 AOFF_RBTree_t* x = node;
176 const Uint new_sz = node->hdr.bhdr;
177
178 ASSERT(!x->left || x->left->max_sz <= x->max_sz);
179 ASSERT(!x->right || x->right->max_sz <= x->max_sz);
180
181 while (new_sz > x->max_sz) {
182 x->max_sz = new_sz;
183 x = x->parent;
184 if (!x)
185 break;
186 }
187 }
188
189 /* Compare nodes for both carrier and block trees */
cmp_blocks(enum AOFFSortOrder order,AOFF_RBTree_t * lhs,AOFF_RBTree_t * rhs)190 static ERTS_INLINE SWord cmp_blocks(enum AOFFSortOrder order,
191 AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
192 {
193 ASSERT(lhs != rhs);
194 if (order == FF_AGEFF) {
195 Sint64 diff = lhs->u.birth_time - rhs->u.birth_time;
196 #ifdef ARCH_64
197 if (diff)
198 return diff;
199 #else
200 if (diff < 0)
201 return -1;
202 else if (diff > 0)
203 return 1;
204 #endif
205 }
206 else {
207 ASSERT(order == FF_AOFF || FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
208 if (order != FF_AOFF) {
209 SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs);
210 if (diff || order == FF_BF) return diff;
211 }
212 }
213 return (char*)lhs - (char*)rhs;
214 }
215
216 /* Compare candidate block. Only for block tree */
cmp_cand_blk(enum AOFFSortOrder order,Block_t * cand_blk,AOFF_RBTree_t * rhs)217 static ERTS_INLINE SWord cmp_cand_blk(enum AOFFSortOrder order,
218 Block_t* cand_blk, AOFF_RBTree_t* rhs)
219 {
220 ASSERT(order != FF_AGEFF);
221 if (order != FF_AOFF) {
222 if (BLK_TO_MBC(cand_blk) == FBLK_TO_MBC(&rhs->hdr)) {
223 SWord diff = (SWord)MBC_BLK_SZ(cand_blk) - (SWord)MBC_FBLK_SZ(&rhs->hdr);
224 if (diff || order == FF_BF) return diff;
225 }
226 }
227 return (char*)cand_blk - (char*)rhs;
228 }
229
230
231 /* Prototypes of callback functions */
232 static Block_t* aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint);
233 static void aoff_link_free_block(Allctr_t *, Block_t*);
234 static void aoff_unlink_free_block(Allctr_t *allctr, Block_t *del);
235 static void aoff_creating_mbc(Allctr_t*, Carrier_t*);
236 #ifdef DEBUG
237 static void aoff_destroying_mbc(Allctr_t*, Carrier_t*);
238 #endif
239 static void aoff_add_mbc(Allctr_t*, Carrier_t*);
240 static void aoff_remove_mbc(Allctr_t*, Carrier_t*);
241 static UWord aoff_largest_fblk_in_mbc(Allctr_t*, Carrier_t*);
242
243 static Block_t *aoff_first_fblk_in_mbc(Allctr_t *, Carrier_t *);
244 static Block_t *aoff_next_fblk_in_mbc(Allctr_t *, Carrier_t *, Block_t *);
245
246 /* Generic tree functions used by both carrier and block trees. */
247 static void rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del);
248 static void rbt_insert(enum AOFFSortOrder, AOFF_RBTree_t** root, AOFF_RBTree_t* blk);
249 static AOFF_RBTree_t* rbt_search(AOFF_RBTree_t* root, Uint size);
250
251 static Eterm info_options(Allctr_t *, char *, fmtfn_t *, void *, Uint **, Uint *);
252 static void init_atoms(void);
253
254
255 static int atoms_initialized = 0;
256
257 #ifndef ERTS_HAVE_OS_MONOTONIC_TIME_SUPPORT
258 static erts_atomic64_t birth_time_counter;
259 #endif
260
261 void
erts_aoffalc_init(void)262 erts_aoffalc_init(void)
263 {
264 atoms_initialized = 0;
265 #ifndef ERTS_HAVE_OS_MONOTONIC_TIME_SUPPORT
266 erts_atomic64_init_nob(&birth_time_counter, 0);
267 #endif
268 }
269
270 Allctr_t *
erts_aoffalc_start(AOFFAllctr_t * alc,AOFFAllctrInit_t * aoffinit,AllctrInit_t * init)271 erts_aoffalc_start(AOFFAllctr_t *alc,
272 AOFFAllctrInit_t* aoffinit,
273 AllctrInit_t *init)
274 {
275 struct {
276 int dummy;
277 AOFFAllctr_t allctr;
278 } zero = {0};
279 /* The struct with a dummy element first is used in order to avoid (an
280 incorrect) gcc warning. gcc warns if {0} is used as initializer of
281 a struct when the first member is a struct (not if, for example,
282 the third member is a struct). */
283
284 Allctr_t *allctr = (Allctr_t *) alc;
285
286 sys_memcpy((void *) alc, (void *) &zero.allctr, sizeof(AOFFAllctr_t));
287
288 if (aoffinit->blk_order == FF_CHAOS) {
289 const enum AOFFSortOrder orders[3] = {FF_AOFF, FF_AOBF, FF_BF};
290 int index = init->ix % (sizeof(orders) / sizeof(orders[0]));
291
292 ASSERT(init->alloc_no == ERTS_ALC_A_TEST);
293 aoffinit->blk_order = orders[index];
294 }
295
296 if (aoffinit->crr_order == FF_CHAOS) {
297 const enum AOFFSortOrder orders[2] = {FF_AGEFF, FF_AOFF};
298 int index = init->ix % (sizeof(orders) / sizeof(orders[0]));
299
300 ASSERT(init->alloc_no == ERTS_ALC_A_TEST);
301 aoffinit->crr_order = orders[index];
302 }
303
304 alc->blk_order = aoffinit->blk_order;
305 alc->crr_order = aoffinit->crr_order;
306 allctr->mbc_header_size = sizeof(AOFF_Carrier_t);
307 allctr->min_mbc_size = MIN_MBC_SZ;
308 allctr->min_block_size = sizeof(AOFF_RBTree_t);
309
310 allctr->vsn_str = ERTS_ALC_AOFF_ALLOC_VSN_STR;
311
312
313 /* Callback functions */
314
315 allctr->get_free_block = aoff_get_free_block;
316 allctr->link_free_block = aoff_link_free_block;
317 allctr->unlink_free_block = aoff_unlink_free_block;
318 allctr->info_options = info_options;
319
320 allctr->get_next_mbc_size = NULL;
321 allctr->creating_mbc = aoff_creating_mbc;
322 #ifdef DEBUG
323 allctr->destroying_mbc = aoff_destroying_mbc;
324 #else
325 allctr->destroying_mbc = NULL;
326 #endif
327 allctr->add_mbc = aoff_add_mbc;
328 allctr->remove_mbc = aoff_remove_mbc;
329 allctr->largest_fblk_in_mbc = aoff_largest_fblk_in_mbc;
330 allctr->first_fblk_in_mbc = aoff_first_fblk_in_mbc;
331 allctr->next_fblk_in_mbc = aoff_next_fblk_in_mbc;
332 allctr->init_atoms = init_atoms;
333
334 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
335 allctr->check_block = NULL;
336 allctr->check_mbc = NULL;
337 #endif
338
339 allctr->atoms_initialized = 0;
340
341 if (!erts_alcu_start(allctr, init))
342 return NULL;
343
344 return allctr;
345 }
346
347 /*
348 * Red-Black Tree operations needed
349 */
350
351 static ERTS_INLINE void
left_rotate(AOFF_RBTree_t ** root,AOFF_RBTree_t * x)352 left_rotate(AOFF_RBTree_t **root, AOFF_RBTree_t *x)
353 {
354 AOFF_RBTree_t *y = x->right;
355 x->right = y->left;
356 if (y->left)
357 y->left->parent = x;
358 y->parent = x->parent;
359 if (!y->parent) {
360 RBT_ASSERT(*root == x);
361 *root = y;
362 }
363 else if (x == x->parent->left)
364 x->parent->left = y;
365 else {
366 RBT_ASSERT(x == x->parent->right);
367 x->parent->right = y;
368 }
369 y->left = x;
370 x->parent = y;
371
372 y->max_sz = x->max_sz;
373 x->max_sz = node_max_size(x);
374 ASSERT(y->max_sz >= x->max_sz);
375 }
376
377 static ERTS_INLINE void
right_rotate(AOFF_RBTree_t ** root,AOFF_RBTree_t * x)378 right_rotate(AOFF_RBTree_t **root, AOFF_RBTree_t *x)
379 {
380 AOFF_RBTree_t *y = x->left;
381 x->left = y->right;
382 if (y->right)
383 y->right->parent = x;
384 y->parent = x->parent;
385 if (!y->parent) {
386 RBT_ASSERT(*root == x);
387 *root = y;
388 }
389 else if (x == x->parent->right)
390 x->parent->right = y;
391 else {
392 RBT_ASSERT(x == x->parent->left);
393 x->parent->left = y;
394 }
395 y->right = x;
396 x->parent = y;
397 y->max_sz = x->max_sz;
398 x->max_sz = node_max_size(x);
399 ASSERT(y->max_sz >= x->max_sz);
400 }
401
402
403 /*
404 * Replace node x with node y
405 * NOTE: block header of y is not changed
406 */
407 static ERTS_INLINE void
replace(AOFF_RBTree_t ** root,AOFF_RBTree_t * x,AOFF_RBTree_t * y)408 replace(AOFF_RBTree_t **root, AOFF_RBTree_t *x, AOFF_RBTree_t *y)
409 {
410
411 if (!x->parent) {
412 RBT_ASSERT(*root == x);
413 *root = y;
414 }
415 else if (x == x->parent->left)
416 x->parent->left = y;
417 else {
418 RBT_ASSERT(x == x->parent->right);
419 x->parent->right = y;
420 }
421 if (x->left) {
422 RBT_ASSERT(x->left->parent == x);
423 x->left->parent = y;
424 }
425 if (x->right) {
426 RBT_ASSERT(x->right->parent == x);
427 x->right->parent = y;
428 }
429
430 y->flags = x->flags;
431 y->parent = x->parent;
432 y->right = x->right;
433 y->left = x->left;
434 y->max_sz = x->max_sz;
435 }
436
437 static void
tree_insert_fixup(AOFF_RBTree_t ** root,AOFF_RBTree_t * blk)438 tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk)
439 {
440 AOFF_RBTree_t *x = blk, *y;
441
442 /*
443 * Rearrange the tree so that it satisfies the Red-Black Tree properties
444 */
445
446 RBT_ASSERT(x != *root && IS_RED(x->parent));
447 do {
448
449 /*
450 * x and its parent are both red. Move the red pair up the tree
451 * until we get to the root or until we can separate them.
452 */
453
454 RBT_ASSERT(IS_RED(x));
455 RBT_ASSERT(IS_BLACK(x->parent->parent));
456 RBT_ASSERT(x->parent->parent);
457
458 if (x->parent == x->parent->parent->left) {
459 y = x->parent->parent->right;
460 if (IS_RED(y)) {
461 SET_BLACK(y);
462 x = x->parent;
463 SET_BLACK(x);
464 x = x->parent;
465 SET_RED(x);
466 }
467 else {
468
469 if (x == x->parent->right) {
470 x = x->parent;
471 left_rotate(root, x);
472 }
473
474 RBT_ASSERT(x == x->parent->parent->left->left);
475 RBT_ASSERT(IS_RED(x));
476 RBT_ASSERT(IS_RED(x->parent));
477 RBT_ASSERT(IS_BLACK(x->parent->parent));
478 RBT_ASSERT(IS_BLACK(y));
479
480 SET_BLACK(x->parent);
481 SET_RED(x->parent->parent);
482 right_rotate(root, x->parent->parent);
483
484 RBT_ASSERT(x == x->parent->left);
485 RBT_ASSERT(IS_RED(x));
486 RBT_ASSERT(IS_RED(x->parent->right));
487 RBT_ASSERT(IS_BLACK(x->parent));
488 break;
489 }
490 }
491 else {
492 RBT_ASSERT(x->parent == x->parent->parent->right);
493 y = x->parent->parent->left;
494 if (IS_RED(y)) {
495 SET_BLACK(y);
496 x = x->parent;
497 SET_BLACK(x);
498 x = x->parent;
499 SET_RED(x);
500 }
501 else {
502
503 if (x == x->parent->left) {
504 x = x->parent;
505 right_rotate(root, x);
506 }
507
508 RBT_ASSERT(x == x->parent->parent->right->right);
509 RBT_ASSERT(IS_RED(x));
510 RBT_ASSERT(IS_RED(x->parent));
511 RBT_ASSERT(IS_BLACK(x->parent->parent));
512 RBT_ASSERT(IS_BLACK(y));
513
514 SET_BLACK(x->parent);
515 SET_RED(x->parent->parent);
516 left_rotate(root, x->parent->parent);
517
518 RBT_ASSERT(x == x->parent->right);
519 RBT_ASSERT(IS_RED(x));
520 RBT_ASSERT(IS_RED(x->parent->left));
521 RBT_ASSERT(IS_BLACK(x->parent));
522 break;
523 }
524 }
525 } while (x != *root && IS_RED(x->parent));
526
527 SET_BLACK(*root);
528 }
529
530 static void
aoff_unlink_free_block(Allctr_t * allctr,Block_t * blk)531 aoff_unlink_free_block(Allctr_t *allctr, Block_t *blk)
532 {
533 AOFF_RBTree_t* del = (AOFF_RBTree_t*)blk;
534 AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(&del->hdr);
535
536 (void)allctr;
537
538 ASSERT(crr->rbt_node.hdr.bhdr == crr->root->max_sz);
539 HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
540
541 if (crr->blk_order == FF_BF) {
542 ASSERT(del->flags & IS_BF_FLG);
543 if (IS_LIST_ELEM(del)) {
544 /* Remove from list */
545 ASSERT(AOFF_LIST_PREV(del));
546 ASSERT(AOFF_LIST_PREV(del)->flags & IS_BF_FLG);
547 AOFF_LIST_NEXT(AOFF_LIST_PREV(del)) = AOFF_LIST_NEXT(del);
548 if (AOFF_LIST_NEXT(del)) {
549 ASSERT(AOFF_LIST_NEXT(del)->flags & IS_BF_FLG);
550 AOFF_LIST_PREV(AOFF_LIST_NEXT(del)) = AOFF_LIST_PREV(del);
551 }
552 return;
553 }
554 else if (AOFF_LIST_NEXT(del)) {
555 /* Replace tree node by next element in list... */
556
557 ASSERT(AOFF_BLK_SZ(AOFF_LIST_NEXT(del)) == AOFF_BLK_SZ(del));
558 ASSERT(IS_LIST_ELEM(AOFF_LIST_NEXT(del)));
559
560 replace(&crr->root, (AOFF_RBTree_t*)del, AOFF_LIST_NEXT(del));
561
562 HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
563 return;
564 }
565 }
566
567 rbt_delete(&crr->root, (AOFF_RBTree_t*)del);
568
569 HARD_CHECK_TREE(&crr->crr, crr->blk_order, crr->root, 0);
570
571 /* Update the carrier tree with a potentially new (lower) max_sz
572 */
573 if (crr->root) {
574 if (crr->rbt_node.hdr.bhdr == crr->root->max_sz) {
575 return;
576 }
577 ASSERT(crr->rbt_node.hdr.bhdr > crr->root->max_sz);
578 crr->rbt_node.hdr.bhdr = crr->root->max_sz;
579 }
580 else {
581 crr->rbt_node.hdr.bhdr = 0;
582 }
583 lower_max_size(&crr->rbt_node, NULL);
584 }
585
586
587 static void
rbt_delete(AOFF_RBTree_t ** root,AOFF_RBTree_t * del)588 rbt_delete(AOFF_RBTree_t** root, AOFF_RBTree_t* del)
589 {
590 Uint spliced_is_black;
591 AOFF_RBTree_t *x, *y, *z = del;
592 AOFF_RBTree_t null_x; /* null_x is used to get the fixup started when we
593 splice out a node without children. */
594
595 HARD_CHECK_IS_MEMBER(*root, del);
596
597 null_x.parent = NULL;
598
599 /* Remove node from tree... */
600
601 /* Find node to splice out */
602 if (!z->left || !z->right)
603 y = z;
604 else {
605 /* Set y to z:s successor */
606 for(y = z->right; y->left; y = y->left)
607 ;
608 }
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
1079 return (Block_t*)blk;
1080 }
1081
1082 return NULL;
1083 }
1084
aoff_next_fblk_in_mbc(Allctr_t * allctr,Carrier_t * carrier,Block_t * block)1085 static Block_t *aoff_next_fblk_in_mbc(Allctr_t *allctr, Carrier_t *carrier,
1086 Block_t *block)
1087 {
1088 AOFF_RBTree_t *parent, *blk;
1089
1090 (void)allctr;
1091 (void)carrier;
1092
1093 blk = (AOFF_RBTree_t*)block;
1094
1095 if (blk->left) {
1096 /* Descend to the rightmost block of the left subtree. */
1097 for (blk = blk->left; blk->right; blk = blk->right)
1098 ;
1099
1100 return (Block_t*)blk;
1101 }
1102
1103 while (blk->parent) {
1104 parent = blk->parent;
1105
1106 /* If we ascend from the right we know we haven't visited our parent
1107 * yet, because we always descend as far as we can to the right when
1108 * entering a subtree. */
1109 if (parent->right == blk) {
1110 ASSERT(parent->left != blk);
1111 return (Block_t*)parent;
1112 }
1113
1114 /* If we ascend from the left we know we've already visited our
1115 * parent, and will need to keep ascending until we do so from the
1116 * right or reach the end of the tree. */
1117 ASSERT(parent->left == blk);
1118 blk = parent;
1119 }
1120
1121 return NULL;
1122 }
1123
1124 /*
1125 * info_options()
1126 */
1127
1128 static const char* flavor_str[2][3] = {
1129 {"ageffcaoff", "ageffcaobf", "ageffcbf"},
1130 { "aoff", "aoffcaobf", "aoffcbf"}
1131 };
1132 static Eterm flavor_atoms[2][3];
1133
1134 static struct {
1135 Eterm as;
1136 } am;
1137
atom_init(Eterm * atom,const char * name)1138 static void ERTS_INLINE atom_init(Eterm *atom, const char *name)
1139 {
1140 *atom = am_atom_put(name, sys_strlen(name));
1141 }
1142 #define AM_INIT(AM) atom_init(&am.AM, #AM)
1143
1144 static void
init_atoms(void)1145 init_atoms(void)
1146 {
1147 int i, j;
1148
1149 if (atoms_initialized)
1150 return;
1151
1152 AM_INIT(as);
1153
1154 for (i = 0; i < 2; i++)
1155 for (j = 0; j < 3; j++)
1156 atom_init(&flavor_atoms[i][j], flavor_str[i][j]);
1157
1158 atoms_initialized = 1;
1159 }
1160
1161
1162 #define bld_uint erts_bld_uint
1163 #define bld_cons erts_bld_cons
1164 #define bld_tuple erts_bld_tuple
1165
1166 static ERTS_INLINE void
add_2tup(Uint ** hpp,Uint * szp,Eterm * lp,Eterm el1,Eterm el2)1167 add_2tup(Uint **hpp, Uint *szp, Eterm *lp, Eterm el1, Eterm el2)
1168 {
1169 *lp = bld_cons(hpp, szp, bld_tuple(hpp, szp, 2, el1, el2), *lp);
1170 }
1171
1172 static Eterm
info_options(Allctr_t * allctr,char * prefix,fmtfn_t * print_to_p,void * print_to_arg,Uint ** hpp,Uint * szp)1173 info_options(Allctr_t *allctr,
1174 char *prefix,
1175 fmtfn_t *print_to_p,
1176 void *print_to_arg,
1177 Uint **hpp,
1178 Uint *szp)
1179 {
1180 AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
1181 Eterm res = THE_NON_VALUE;
1182
1183 ASSERT(alc->crr_order >= 0 && alc->crr_order <= 1);
1184 ASSERT(alc->blk_order >= 1 && alc->blk_order <= 3);
1185
1186 if (print_to_p) {
1187 erts_print(*print_to_p,
1188 print_to_arg,
1189 "%sas: %s\n",
1190 prefix,
1191 flavor_str[alc->crr_order][alc->blk_order-1]);
1192 }
1193
1194 if (hpp || szp) {
1195
1196 if (!atoms_initialized)
1197 erts_exit(ERTS_ERROR_EXIT, "%s:%d: Internal error: Atoms not initialized",
1198 __FILE__, __LINE__);;
1199
1200 res = NIL;
1201 add_2tup(hpp, szp, &res, am.as,
1202 flavor_atoms[alc->crr_order][alc->blk_order-1]);
1203 }
1204
1205 return res;
1206 }
1207
1208
1209 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
1210 * NOTE: erts_aoffalc_test() is only supposed to be used for testing. *
1211 * *
1212 * Keep alloc_SUITE_data/allocator_test.h updated if changes are made *
1213 * to erts_aoffalc_test() *
1214 \* */
1215
1216 UWord
erts_aoffalc_test(UWord op,UWord a1,UWord a2)1217 erts_aoffalc_test(UWord op, UWord a1, UWord a2)
1218 {
1219 switch (op) {
1220 case 0x500: return (UWord) ((AOFFAllctr_t *) a1)->blk_order == FF_AOBF;
1221 case 0x501: {
1222 AOFF_RBTree_t *node = ((AOFFAllctr_t *) a1)->mbc_root;
1223 Uint size = (Uint) a2;
1224 node = node ? rbt_search(node, size) : NULL;
1225 return (UWord) (node ? RBT_NODE_TO_MBC(node)->root : NULL);
1226 }
1227 case 0x502: return (UWord) ((AOFF_RBTree_t *) a1)->parent;
1228 case 0x503: return (UWord) ((AOFF_RBTree_t *) a1)->left;
1229 case 0x504: return (UWord) ((AOFF_RBTree_t *) a1)->right;
1230 case 0x505: return (UWord) AOFF_LIST_NEXT(a1);
1231 case 0x506: return (UWord) IS_BLACK((AOFF_RBTree_t *) a1);
1232 case 0x507: return (UWord) IS_TREE_NODE((AOFF_RBTree_t *) a1);
1233 case 0x508: return (UWord) 0; /* IS_BF_ALGO */
1234 case 0x509: return (UWord) ((AOFF_RBTree_t *) a1)->max_sz;
1235 case 0x50a: return (UWord) ((AOFFAllctr_t *) a1)->blk_order == FF_BF;
1236 case 0x50b: return (UWord) AOFF_LIST_PREV(a1);
1237 default: ASSERT(0); return ~((UWord) 0);
1238 }
1239 }
1240
1241
1242 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
1243 * Debug functions *
1244 \* */
1245
1246
1247 #ifdef HARD_DEBUG
rbt_is_member(AOFF_RBTree_t * root,AOFF_RBTree_t * node)1248 static int rbt_is_member(AOFF_RBTree_t* root, AOFF_RBTree_t* node)
1249 {
1250 while (node != root) {
1251 if (!node->parent || (node->parent->left != node &&
1252 node->parent->right != node)) {
1253 return 0;
1254 }
1255 node = node->parent;
1256 }
1257 return 1;
1258 }
1259
1260 #define IS_LEFT_VISITED(FB) ((FB)->flags & LEFT_VISITED_FLG)
1261 #define IS_RIGHT_VISITED(FB) ((FB)->flags & RIGHT_VISITED_FLG)
1262
1263 #define SET_LEFT_VISITED(FB) ((FB)->flags |= LEFT_VISITED_FLG)
1264 #define SET_RIGHT_VISITED(FB) ((FB)->flags |= RIGHT_VISITED_FLG)
1265
1266 #define UNSET_LEFT_VISITED(FB) ((FB)->flags &= ~LEFT_VISITED_FLG)
1267 #define UNSET_RIGHT_VISITED(FB) ((FB)->flags &= ~RIGHT_VISITED_FLG)
1268
1269
1270 #if 0
1271 # define PRINT_TREE
1272 #else
1273 # undef PRINT_TREE
1274 #endif
1275
1276 #ifdef PRINT_TREE
1277 static void print_tree(AOFF_RBTree_t*);
1278 #endif
1279
1280 /*
1281 * Checks that the order between parent and children are correct,
1282 * and that the Red-Black Tree properies are satisfied. if size > 0,
1283 * check_tree() returns the node that satisfies "address order first fit"
1284 *
1285 * The Red-Black Tree properies are:
1286 * 1. Every node is either red or black.
1287 * 2. Every leaf (NIL) is black.
1288 * 3. If a node is red, then both its children are black.
1289 * 4. Every simple path from a node to a descendant leaf
1290 * contains the same number of black nodes.
1291 *
1292 * + own.max_size == MAX(own.size, left.max_size, right.max_size)
1293 */
1294
1295 static AOFF_RBTree_t *
check_tree(Carrier_t * within_crr,enum AOFFSortOrder order,AOFF_RBTree_t * root,Uint size)1296 check_tree(Carrier_t* within_crr, enum AOFFSortOrder order, AOFF_RBTree_t* root, Uint size)
1297 {
1298 AOFF_RBTree_t *res = NULL;
1299 Sint blacks;
1300 Sint curr_blacks;
1301 AOFF_RBTree_t *x;
1302 Carrier_t* crr;
1303 Uint depth, max_depth, node_cnt;
1304
1305 #ifdef PRINT_TREE
1306 print_tree(root);
1307 #endif
1308 ASSERT((within_crr && order >= FF_AOFF) ||
1309 (!within_crr && order <= FF_AOFF));
1310
1311 if (!root)
1312 return res;
1313
1314 x = root;
1315 ASSERT(IS_BLACK(x));
1316 ASSERT(!x->parent);
1317 curr_blacks = 1;
1318 blacks = -1;
1319 depth = 1;
1320 max_depth = 0;
1321 node_cnt = 0;
1322
1323 while (x) {
1324 if (!IS_LEFT_VISITED(x)) {
1325 SET_LEFT_VISITED(x);
1326 if (x->left) {
1327 x = x->left;
1328 ++depth;
1329 if (IS_BLACK(x))
1330 curr_blacks++;
1331 continue;
1332 }
1333 else {
1334 if (blacks < 0)
1335 blacks = curr_blacks;
1336 ASSERT(blacks == curr_blacks);
1337 }
1338 }
1339
1340 if (!IS_RIGHT_VISITED(x)) {
1341 SET_RIGHT_VISITED(x);
1342 if (x->right) {
1343 x = x->right;
1344 ++depth;
1345 if (IS_BLACK(x))
1346 curr_blacks++;
1347 continue;
1348 }
1349 else {
1350 if (blacks < 0)
1351 blacks = curr_blacks;
1352 ASSERT(blacks == curr_blacks);
1353 }
1354 }
1355
1356 ++node_cnt;
1357 if (depth > max_depth)
1358 max_depth = depth;
1359
1360 if (within_crr) {
1361 crr = FBLK_TO_MBC(&x->hdr);
1362 ASSERT(crr == within_crr);
1363 ASSERT((char*)x > (char*)crr);
1364 ASSERT(((char*)x + AOFF_BLK_SZ(x)) <= ((char*)crr + CARRIER_SZ(crr)));
1365
1366 }
1367 if (order == FF_BF) {
1368 AOFF_RBTree_t* y = x;
1369 AOFF_RBTree_t* nxt = AOFF_LIST_NEXT(y);
1370 ASSERT(IS_TREE_NODE(x));
1371 while (nxt) {
1372 ASSERT(IS_LIST_ELEM(nxt));
1373 ASSERT(AOFF_BLK_SZ(nxt) == AOFF_BLK_SZ(x));
1374 ASSERT(FBLK_TO_MBC(&nxt->hdr) == within_crr);
1375 ASSERT(AOFF_LIST_PREV(nxt) == y);
1376 y = nxt;
1377 nxt = AOFF_LIST_NEXT(nxt);
1378 }
1379 }
1380
1381 if (IS_RED(x)) {
1382 ASSERT(IS_BLACK(x->right));
1383 ASSERT(IS_BLACK(x->left));
1384 }
1385
1386 ASSERT(x->parent || x == root);
1387
1388 if (x->left) {
1389 ASSERT(x->left->parent == x);
1390 ASSERT(cmp_blocks(order, x->left, x) < 0);
1391 ASSERT(x->left->max_sz <= x->max_sz);
1392 }
1393
1394 if (x->right) {
1395 ASSERT(x->right->parent == x);
1396 ASSERT(cmp_blocks(order, x->right, x) > 0);
1397 ASSERT(x->right->max_sz <= x->max_sz);
1398 }
1399 ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
1400 ASSERT(x->max_sz == AOFF_BLK_SZ(x)
1401 || x->max_sz == (x->left ? x->left->max_sz : 0)
1402 || x->max_sz == (x->right ? x->right->max_sz : 0));
1403
1404 if (size && AOFF_BLK_SZ(x) >= size) {
1405 if (!res || cmp_blocks(order, x, res) < 0) {
1406 res = x;
1407 }
1408 }
1409
1410 UNSET_LEFT_VISITED(x);
1411 UNSET_RIGHT_VISITED(x);
1412 if (IS_BLACK(x))
1413 curr_blacks--;
1414 x = x->parent;
1415 --depth;
1416 }
1417 ASSERT(depth == 0 || (!root && depth==1));
1418 ASSERT(curr_blacks == 0);
1419 ASSERT((1 << (max_depth/2)) <= node_cnt);
1420
1421 UNSET_LEFT_VISITED(root);
1422 UNSET_RIGHT_VISITED(root);
1423
1424 return res;
1425
1426 }
1427
1428
1429 #ifdef PRINT_TREE
1430 #define INDENT_STEP 2
1431
1432 #include <stdio.h>
1433
1434 static void
print_tree_aux(AOFF_RBTree_t * x,int indent)1435 print_tree_aux(AOFF_RBTree_t *x, int indent)
1436 {
1437 int i;
1438
1439 if (x) {
1440 print_tree_aux(x->right, indent + INDENT_STEP);
1441 for (i = 0; i < indent; i++) {
1442 putc(' ', stderr);
1443 }
1444 fprintf(stderr, "%s: sz=%lu addr=0x%lx max_size=%u\r\n",
1445 IS_BLACK(x) ? "BLACK" : "RED",
1446 AOFF_BLK_SZ(x), (Uint)x, (unsigned)x->max_sz);
1447 print_tree_aux(x->left, indent + INDENT_STEP);
1448 }
1449 }
1450
1451
1452 static void
print_tree(AOFF_RBTree_t * root)1453 print_tree(AOFF_RBTree_t* root)
1454 {
1455 fprintf(stderr, " --- AOFF tree begin ---\r\n");
1456 print_tree_aux(root, 0);
1457 fprintf(stderr, " --- AOFF tree end ---\r\n");
1458 }
1459
1460 #endif /* PRINT_TREE */
1461
1462 #endif /* HARD_DEBUG */
1463