1 /*
2 * %CopyrightBegin%
3 *
4 * Copyright Ericsson AB 2003-2018. 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 combined "address order best fit"/"best fit" allocator
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. In the "address order best fit" case
27 * n equals number of free blocks, and in the "best fit" case
28 * n equals number of distinct sizes of free blocks. Red-Black
29 * Trees are described in "Introduction to Algorithms", by
30 * Thomas H. Cormen, Charles E. Leiserson, and
31 * Ronald L. Riverest.
32 *
33 * This module is a callback-module for erl_alloc_util.c
34 *
35 * Author: Rickard Green
36 */
37
38
39 #ifdef HAVE_CONFIG_H
40 # include "config.h"
41 #endif
42 #include "global.h"
43 #define GET_ERL_BF_ALLOC_IMPL
44 #include "erl_bestfit_alloc.h"
45
46 #ifdef DEBUG
47 #if 0
48 #define HARD_DEBUG
49 #endif
50 #else
51 #undef HARD_DEBUG
52 #endif
53
54 #define MIN_MBC_SZ (16*1024)
55 #define MIN_MBC_FIRST_FREE_SZ (4*1024)
56
57 #define TREE_NODE_FLG (((Uint) 1) << 0)
58 #define RED_FLG (((Uint) 1) << 1)
59 #ifdef HARD_DEBUG
60 # define LEFT_VISITED_FLG (((Uint) 1) << 2)
61 # define RIGHT_VISITED_FLG (((Uint) 1) << 3)
62 #endif
63
64 #define IS_TREE_NODE(N) (((RBTree_t *) (N))->flags & TREE_NODE_FLG)
65 #define IS_LIST_ELEM(N) (!IS_TREE_NODE(((RBTree_t *) (N))))
66
67 #define SET_TREE_NODE(N) (((RBTree_t *) (N))->flags |= TREE_NODE_FLG)
68 #define SET_LIST_ELEM(N) (((RBTree_t *) (N))->flags &= ~TREE_NODE_FLG)
69
70 #define IS_RED(N) (((RBTree_t *) (N)) \
71 && ((RBTree_t *) (N))->flags & RED_FLG)
72 #define IS_BLACK(N) (!IS_RED(((RBTree_t *) (N))))
73
74 #define SET_RED(N) (((RBTree_t *) (N))->flags |= RED_FLG)
75 #define SET_BLACK(N) (((RBTree_t *) (N))->flags &= ~RED_FLG)
76
77 #define BF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
78
79 #if 1
80 #define RBT_ASSERT ASSERT
81 #else
82 #define RBT_ASSERT(x)
83 #endif
84
85
86 #ifdef HARD_DEBUG
87 static RBTree_t * check_tree(RBTree_t, int, Uint);
88 #endif
89
90 static void tree_delete(Allctr_t *allctr, Block_t *del);
91
92 /* Prototypes of callback functions */
93
94 /* "address order best fit" specific callback functions */
95 static Block_t * aobf_get_free_block (Allctr_t *, Uint,
96 Block_t *, Uint);
97 static void aobf_link_free_block (Allctr_t *, Block_t *);
98 #define aobf_unlink_free_block tree_delete
99
100 /* "best fit" specific callback functions */
101 static Block_t * bf_get_free_block (Allctr_t *, Uint,
102 Block_t *, Uint);
103 static void bf_link_free_block (Allctr_t *, Block_t *);
104 static ERTS_INLINE void bf_unlink_free_block (Allctr_t *, Block_t *);
105
106
107 static Eterm info_options (Allctr_t *, char *, fmtfn_t *,
108 void *, Uint **, Uint *);
109 static void init_atoms (void);
110
111 /* Types... */
112 struct RBTree_t_ {
113 Block_t hdr;
114 Uint flags;
115 RBTree_t *parent;
116 RBTree_t *left;
117 RBTree_t *right;
118 };
119
120 typedef struct {
121 RBTree_t t;
122 RBTree_t *next;
123 } RBTreeList_t;
124
125 #define BF_LIST_NEXT(N) (((RBTreeList_t *) (N))->next)
126 #define BF_LIST_PREV(N) (((RBTreeList_t *) (N))->t.parent)
127
128
129 #ifdef DEBUG
130
131 /* Destroy all tree fields */
132 #define DESTROY_TREE_NODE(N) \
133 sys_memset((void *) (((Block_t *) (N)) + 1), \
134 0xff, \
135 (sizeof(RBTree_t) - sizeof(Block_t)))
136
137 /* Destroy all tree and list fields */
138 #define DESTROY_LIST_ELEM(N) \
139 sys_memset((void *) (((Block_t *) (N)) + 1), \
140 0xff, \
141 (sizeof(RBTreeList_t) - sizeof(Block_t)))
142
143 #else
144
145 #define DESTROY_TREE_NODE(N)
146 #define DESTROY_LIST_ELEM(N)
147
148 #endif
149
150
151 static int atoms_initialized = 0;
152
153 void
erts_bfalc_init(void)154 erts_bfalc_init(void)
155 {
156 atoms_initialized = 0;
157 }
158
159 Allctr_t *
erts_bfalc_start(BFAllctr_t * bfallctr,BFAllctrInit_t * bfinit,AllctrInit_t * init)160 erts_bfalc_start(BFAllctr_t *bfallctr,
161 BFAllctrInit_t *bfinit,
162 AllctrInit_t *init)
163 {
164 struct {
165 int dummy;
166 BFAllctr_t allctr;
167 } zero = {0};
168 /* The struct with a dummy element first is used in order to avoid (an
169 incorrect) gcc warning. gcc warns if {0} is used as initializer of
170 a struct when the first member is a struct (not if, for example,
171 the third member is a struct). */
172
173 Allctr_t *allctr = (Allctr_t *) bfallctr;
174
175 sys_memcpy((void *) bfallctr, (void *) &zero.allctr, sizeof(BFAllctr_t));
176
177 bfallctr->address_order = bfinit->ao;
178
179
180 allctr->mbc_header_size = sizeof(Carrier_t);
181 allctr->min_mbc_size = MIN_MBC_SZ;
182 allctr->min_mbc_first_free_size = MIN_MBC_FIRST_FREE_SZ;
183 allctr->min_block_size = (bfinit->ao
184 ? sizeof(RBTree_t)
185 : sizeof(RBTreeList_t));
186
187 allctr->vsn_str = (bfinit->ao
188 ? ERTS_ALC_AOBF_ALLOC_VSN_STR
189 : ERTS_ALC_BF_ALLOC_VSN_STR);
190
191
192 /* Callback functions */
193
194 if (bfinit->ao) {
195 allctr->get_free_block = aobf_get_free_block;
196 allctr->link_free_block = aobf_link_free_block;
197 allctr->unlink_free_block = aobf_unlink_free_block;
198 }
199 else {
200 allctr->get_free_block = bf_get_free_block;
201 allctr->link_free_block = bf_link_free_block;
202 allctr->unlink_free_block = bf_unlink_free_block;
203 }
204 allctr->info_options = info_options;
205
206 allctr->get_next_mbc_size = NULL;
207 allctr->creating_mbc = NULL;
208 allctr->destroying_mbc = NULL;
209 allctr->add_mbc = NULL;
210 allctr->remove_mbc = NULL;
211 allctr->largest_fblk_in_mbc = NULL;
212 allctr->init_atoms = init_atoms;
213
214 #ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
215 allctr->check_block = NULL;
216 allctr->check_mbc = NULL;
217 #endif
218
219 allctr->atoms_initialized = 0;
220
221 if (!erts_alcu_start(allctr, init))
222 return NULL;
223
224 return allctr;
225 }
226
227 /*
228 * Red-Black Tree operations needed
229 */
230
231 static ERTS_INLINE void
left_rotate(RBTree_t ** root,RBTree_t * x)232 left_rotate(RBTree_t **root, RBTree_t *x)
233 {
234 RBTree_t *y = x->right;
235 x->right = y->left;
236 if (y->left)
237 y->left->parent = x;
238 y->parent = x->parent;
239 if (!y->parent) {
240 RBT_ASSERT(*root == x);
241 *root = y;
242 }
243 else if (x == x->parent->left)
244 x->parent->left = y;
245 else {
246 RBT_ASSERT(x == x->parent->right);
247 x->parent->right = y;
248 }
249 y->left = x;
250 x->parent = y;
251 }
252
253 static ERTS_INLINE void
right_rotate(RBTree_t ** root,RBTree_t * x)254 right_rotate(RBTree_t **root, RBTree_t *x)
255 {
256 RBTree_t *y = x->left;
257 x->left = y->right;
258 if (y->right)
259 y->right->parent = x;
260 y->parent = x->parent;
261 if (!y->parent) {
262 RBT_ASSERT(*root == x);
263 *root = y;
264 }
265 else if (x == x->parent->right)
266 x->parent->right = y;
267 else {
268 RBT_ASSERT(x == x->parent->left);
269 x->parent->left = y;
270 }
271 y->right = x;
272 x->parent = y;
273 }
274
275
276 /*
277 * Replace node x with node y
278 * NOTE: block header of y is not changed
279 */
280 static ERTS_INLINE void
replace(RBTree_t ** root,RBTree_t * x,RBTree_t * y)281 replace(RBTree_t **root, RBTree_t *x, RBTree_t *y)
282 {
283
284 if (!x->parent) {
285 RBT_ASSERT(*root == x);
286 *root = y;
287 }
288 else if (x == x->parent->left)
289 x->parent->left = y;
290 else {
291 RBT_ASSERT(x == x->parent->right);
292 x->parent->right = y;
293 }
294 if (x->left) {
295 RBT_ASSERT(x->left->parent == x);
296 x->left->parent = y;
297 }
298 if (x->right) {
299 RBT_ASSERT(x->right->parent == x);
300 x->right->parent = y;
301 }
302
303 y->flags = x->flags;
304 y->parent = x->parent;
305 y->right = x->right;
306 y->left = x->left;
307
308 DESTROY_TREE_NODE(x);
309
310 }
311
312 static void
tree_insert_fixup(RBTree_t ** root,RBTree_t * blk)313 tree_insert_fixup(RBTree_t **root, RBTree_t *blk)
314 {
315 RBTree_t *x = blk, *y;
316
317 /*
318 * Rearrange the tree so that it satisfies the Red-Black Tree properties
319 */
320
321 RBT_ASSERT(x != *root && IS_RED(x->parent));
322 do {
323
324 /*
325 * x and its parent are both red. Move the red pair up the tree
326 * until we get to the root or until we can separate them.
327 */
328
329 RBT_ASSERT(IS_RED(x));
330 RBT_ASSERT(IS_BLACK(x->parent->parent));
331 RBT_ASSERT(x->parent->parent);
332
333 if (x->parent == x->parent->parent->left) {
334 y = x->parent->parent->right;
335 if (IS_RED(y)) {
336 SET_BLACK(y);
337 x = x->parent;
338 SET_BLACK(x);
339 x = x->parent;
340 SET_RED(x);
341 }
342 else {
343
344 if (x == x->parent->right) {
345 x = x->parent;
346 left_rotate(root, x);
347 }
348
349 RBT_ASSERT(x == x->parent->parent->left->left);
350 RBT_ASSERT(IS_RED(x));
351 RBT_ASSERT(IS_RED(x->parent));
352 RBT_ASSERT(IS_BLACK(x->parent->parent));
353 RBT_ASSERT(IS_BLACK(y));
354
355 SET_BLACK(x->parent);
356 SET_RED(x->parent->parent);
357 right_rotate(root, x->parent->parent);
358
359 RBT_ASSERT(x == x->parent->left);
360 RBT_ASSERT(IS_RED(x));
361 RBT_ASSERT(IS_RED(x->parent->right));
362 RBT_ASSERT(IS_BLACK(x->parent));
363 break;
364 }
365 }
366 else {
367 RBT_ASSERT(x->parent == x->parent->parent->right);
368 y = x->parent->parent->left;
369 if (IS_RED(y)) {
370 SET_BLACK(y);
371 x = x->parent;
372 SET_BLACK(x);
373 x = x->parent;
374 SET_RED(x);
375 }
376 else {
377
378 if (x == x->parent->left) {
379 x = x->parent;
380 right_rotate(root, x);
381 }
382
383 RBT_ASSERT(x == x->parent->parent->right->right);
384 RBT_ASSERT(IS_RED(x));
385 RBT_ASSERT(IS_RED(x->parent));
386 RBT_ASSERT(IS_BLACK(x->parent->parent));
387 RBT_ASSERT(IS_BLACK(y));
388
389 SET_BLACK(x->parent);
390 SET_RED(x->parent->parent);
391 left_rotate(root, x->parent->parent);
392
393 RBT_ASSERT(x == x->parent->right);
394 RBT_ASSERT(IS_RED(x));
395 RBT_ASSERT(IS_RED(x->parent->left));
396 RBT_ASSERT(IS_BLACK(x->parent));
397 break;
398 }
399 }
400 } while (x != *root && IS_RED(x->parent));
401
402 SET_BLACK(*root);
403
404 }
405
406 /*
407 * The argument types of "Allctr_t *" and "Block_t *" have been
408 * chosen since we then can use tree_delete() as unlink_free_block
409 * callback function in the address order case.
410 */
411 static void
tree_delete(Allctr_t * allctr,Block_t * del)412 tree_delete(Allctr_t *allctr, Block_t *del)
413 {
414 BFAllctr_t *bfallctr = (BFAllctr_t *) allctr;
415 Uint spliced_is_black;
416 RBTree_t **root = &bfallctr->mbc_root;
417 RBTree_t *x, *y, *z = (RBTree_t *) del;
418 RBTree_t null_x; /* null_x is used to get the fixup started when we
419 splice out a node without children. */
420
421 null_x.parent = NULL;
422
423
424 #ifdef HARD_DEBUG
425 check_tree(*root, bfallctr->address_order, 0);
426 #endif
427
428 /* Remove node from tree... */
429
430 /* Find node to splice out */
431 if (!z->left || !z->right)
432 y = z;
433 else
434 /* Set y to z:s successor */
435 for(y = z->right; y->left; y = y->left);
436 /* splice out y */
437 x = y->left ? y->left : y->right;
438 spliced_is_black = IS_BLACK(y);
439 if (x) {
440 x->parent = y->parent;
441 }
442 else if (!x && spliced_is_black) {
443 x = &null_x;
444 x->flags = 0;
445 SET_BLACK(x);
446 x->right = x->left = NULL;
447 x->parent = y->parent;
448 y->left = x;
449 }
450
451 if (!y->parent) {
452 RBT_ASSERT(*root == y);
453 *root = x;
454 }
455 else if (y == y->parent->left)
456 y->parent->left = x;
457 else {
458 RBT_ASSERT(y == y->parent->right);
459 y->parent->right = x;
460 }
461 if (y != z) {
462 /* We spliced out the successor of z; replace z by the successor */
463 replace(root, z, y);
464 }
465
466 if (spliced_is_black) {
467 /* We removed a black node which makes the resulting tree
468 violate the Red-Black Tree properties. Fixup tree... */
469
470 while (IS_BLACK(x) && x->parent) {
471
472 /*
473 * x has an "extra black" which we move up the tree
474 * until we reach the root or until we can get rid of it.
475 *
476 * y is the sibbling of x
477 */
478
479 if (x == x->parent->left) {
480 y = x->parent->right;
481 RBT_ASSERT(y);
482 if (IS_RED(y)) {
483 RBT_ASSERT(y->right);
484 RBT_ASSERT(y->left);
485 SET_BLACK(y);
486 RBT_ASSERT(IS_BLACK(x->parent));
487 SET_RED(x->parent);
488 left_rotate(root, x->parent);
489 y = x->parent->right;
490 }
491 RBT_ASSERT(y);
492 RBT_ASSERT(IS_BLACK(y));
493 if (IS_BLACK(y->left) && IS_BLACK(y->right)) {
494 SET_RED(y);
495 x = x->parent;
496 }
497 else {
498 if (IS_BLACK(y->right)) {
499 SET_BLACK(y->left);
500 SET_RED(y);
501 right_rotate(root, y);
502 y = x->parent->right;
503 }
504 RBT_ASSERT(y);
505 if (IS_RED(x->parent)) {
506
507 SET_BLACK(x->parent);
508 SET_RED(y);
509 }
510 RBT_ASSERT(y->right);
511 SET_BLACK(y->right);
512 left_rotate(root, x->parent);
513 x = *root;
514 break;
515 }
516 }
517 else {
518 RBT_ASSERT(x == x->parent->right);
519 y = x->parent->left;
520 RBT_ASSERT(y);
521 if (IS_RED(y)) {
522 RBT_ASSERT(y->right);
523 RBT_ASSERT(y->left);
524 SET_BLACK(y);
525 RBT_ASSERT(IS_BLACK(x->parent));
526 SET_RED(x->parent);
527 right_rotate(root, x->parent);
528 y = x->parent->left;
529 }
530 RBT_ASSERT(y);
531 RBT_ASSERT(IS_BLACK(y));
532 if (IS_BLACK(y->right) && IS_BLACK(y->left)) {
533 SET_RED(y);
534 x = x->parent;
535 }
536 else {
537 if (IS_BLACK(y->left)) {
538 SET_BLACK(y->right);
539 SET_RED(y);
540 left_rotate(root, y);
541 y = x->parent->left;
542 }
543 RBT_ASSERT(y);
544 if (IS_RED(x->parent)) {
545 SET_BLACK(x->parent);
546 SET_RED(y);
547 }
548 RBT_ASSERT(y->left);
549 SET_BLACK(y->left);
550 right_rotate(root, x->parent);
551 x = *root;
552 break;
553 }
554 }
555 }
556 SET_BLACK(x);
557
558 if (null_x.parent) {
559 if (null_x.parent->left == &null_x)
560 null_x.parent->left = NULL;
561 else {
562 RBT_ASSERT(null_x.parent->right == &null_x);
563 null_x.parent->right = NULL;
564 }
565 RBT_ASSERT(!null_x.left);
566 RBT_ASSERT(!null_x.right);
567 }
568 else if (*root == &null_x) {
569 *root = NULL;
570 RBT_ASSERT(!null_x.left);
571 RBT_ASSERT(!null_x.right);
572 }
573 }
574
575
576 DESTROY_TREE_NODE(del);
577
578 #ifdef HARD_DEBUG
579 check_tree(root, bfallctr->address_order, 0);
580 #endif
581
582 }
583
584 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
585 * "Address order best fit" specific callbacks. *
586 \* */
587
588 static void
aobf_link_free_block(Allctr_t * allctr,Block_t * block)589 aobf_link_free_block(Allctr_t *allctr, Block_t *block)
590 {
591 BFAllctr_t *bfallctr = (BFAllctr_t *) allctr;
592 RBTree_t **root = &bfallctr->mbc_root;
593 RBTree_t *blk = (RBTree_t *) block;
594 Uint blk_sz = BF_BLK_SZ(blk);
595
596
597 blk->flags = 0;
598 blk->left = NULL;
599 blk->right = NULL;
600
601 if (!*root) {
602 blk->parent = NULL;
603 SET_BLACK(blk);
604 *root = blk;
605 }
606 else {
607 RBTree_t *x = *root;
608 while (1) {
609 Uint size;
610
611 size = BF_BLK_SZ(x);
612
613 if (blk_sz < size || (blk_sz == size && blk < x)) {
614 if (!x->left) {
615 blk->parent = x;
616 x->left = blk;
617 break;
618 }
619 x = x->left;
620 }
621 else {
622 if (!x->right) {
623 blk->parent = x;
624 x->right = blk;
625 break;
626 }
627 x = x->right;
628 }
629
630 }
631
632 /* Insert block into size tree */
633 RBT_ASSERT(blk->parent);
634
635 SET_RED(blk);
636 if (IS_RED(blk->parent))
637 tree_insert_fixup(root, blk);
638 }
639
640 #ifdef HARD_DEBUG
641 check_tree(root, 1, 0);
642 #endif
643 }
644
645 #if 0 /* tree_delete() is directly used instead */
646 static void
647 aobf_unlink_free_block(Allctr_t *allctr, Block_t *block)
648 {
649 tree_delete(allctr, block);
650 }
651 #endif
652
653 static Block_t *
aobf_get_free_block(Allctr_t * allctr,Uint size,Block_t * cand_blk,Uint cand_size)654 aobf_get_free_block(Allctr_t *allctr, Uint size,
655 Block_t *cand_blk, Uint cand_size)
656 {
657 BFAllctr_t *bfallctr = (BFAllctr_t *) allctr;
658 RBTree_t **root = &bfallctr->mbc_root;
659 RBTree_t *x = *root;
660 RBTree_t *blk = NULL;
661 Uint blk_sz;
662
663 ASSERT(!cand_blk || cand_size >= size);
664
665 while (x) {
666 blk_sz = BF_BLK_SZ(x);
667 if (blk_sz < size) {
668 x = x->right;
669 }
670 else {
671 blk = x;
672 x = x->left;
673 }
674 }
675
676 if (!blk)
677 return NULL;
678
679 #ifdef HARD_DEBUG
680 ASSERT(blk == check_tree(root, 1, size));
681 #endif
682
683 if (cand_blk) {
684 blk_sz = BF_BLK_SZ(blk);
685 if (cand_size < blk_sz)
686 return NULL; /* cand_blk was better */
687 if (cand_size == blk_sz && ((void *) cand_blk) < ((void *) blk))
688 return NULL; /* cand_blk was better */
689 }
690
691 aobf_unlink_free_block(allctr, (Block_t *) blk);
692
693 return (Block_t *) blk;
694 }
695
696
697 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
698 * "Best fit" specific callbacks. *
699 \* */
700
701 static void
bf_link_free_block(Allctr_t * allctr,Block_t * block)702 bf_link_free_block(Allctr_t *allctr, Block_t *block)
703 {
704 BFAllctr_t *bfallctr = (BFAllctr_t *) allctr;
705 RBTree_t **root = &bfallctr->mbc_root;
706 RBTree_t *blk = (RBTree_t *) block;
707 Uint blk_sz = BF_BLK_SZ(blk);
708
709 SET_TREE_NODE(blk);
710
711
712 blk->flags = 0;
713 blk->left = NULL;
714 blk->right = NULL;
715
716 if (!*root) {
717 blk->parent = NULL;
718 SET_BLACK(blk);
719 *root = blk;
720 }
721 else {
722 RBTree_t *x = *root;
723 while (1) {
724 Uint size;
725
726 size = BF_BLK_SZ(x);
727
728 if (blk_sz == size) {
729
730 SET_LIST_ELEM(blk);
731 BF_LIST_NEXT(blk) = BF_LIST_NEXT(x);
732 BF_LIST_PREV(blk) = x;
733 if (BF_LIST_NEXT(x))
734 BF_LIST_PREV(BF_LIST_NEXT(x)) = blk;
735 BF_LIST_NEXT(x) = blk;
736
737 return; /* Finnished */
738 }
739 else if (blk_sz < size) {
740 if (!x->left) {
741 blk->parent = x;
742 x->left = blk;
743 break;
744 }
745 x = x->left;
746 }
747 else {
748 if (!x->right) {
749 blk->parent = x;
750 x->right = blk;
751 break;
752 }
753 x = x->right;
754 }
755 }
756
757 RBT_ASSERT(blk->parent);
758
759 SET_RED(blk);
760 if (IS_RED(blk->parent))
761 tree_insert_fixup(root, blk);
762
763 }
764
765 SET_TREE_NODE(blk);
766 BF_LIST_NEXT(blk) = NULL;
767
768 #ifdef HARD_DEBUG
769 check_tree(root, 0, 0);
770 #endif
771 }
772
773 static ERTS_INLINE void
bf_unlink_free_block(Allctr_t * allctr,Block_t * block)774 bf_unlink_free_block(Allctr_t *allctr, Block_t *block)
775 {
776 BFAllctr_t *bfallctr = (BFAllctr_t *) allctr;
777 RBTree_t **root = &bfallctr->mbc_root;
778 RBTree_t *x = (RBTree_t *) block;
779
780 if (IS_LIST_ELEM(x)) {
781 /* Remove from list */
782 ASSERT(BF_LIST_PREV(x));
783 BF_LIST_NEXT(BF_LIST_PREV(x)) = BF_LIST_NEXT(x);
784 if (BF_LIST_NEXT(x))
785 BF_LIST_PREV(BF_LIST_NEXT(x)) = BF_LIST_PREV(x);
786 }
787 else if (BF_LIST_NEXT(x)) {
788 /* Replace tree node by next element in list... */
789
790 ASSERT(BF_BLK_SZ(BF_LIST_NEXT(x)) == BF_BLK_SZ(x));
791 ASSERT(IS_TREE_NODE(x));
792 ASSERT(IS_LIST_ELEM(BF_LIST_NEXT(x)));
793
794 #ifdef HARD_DEBUG
795 check_tree(root, 0, 0);
796 #endif
797 replace(root, x, BF_LIST_NEXT(x));
798
799 #ifdef HARD_DEBUG
800 check_tree(bfallctr, 0);
801 #endif
802 }
803 else {
804 /* Remove from tree */
805 tree_delete(allctr, block);
806 }
807
808 DESTROY_LIST_ELEM(x);
809 }
810
811
812 static Block_t *
bf_get_free_block(Allctr_t * allctr,Uint size,Block_t * cand_blk,Uint cand_size)813 bf_get_free_block(Allctr_t *allctr, Uint size,
814 Block_t *cand_blk, Uint cand_size)
815 {
816 BFAllctr_t *bfallctr = (BFAllctr_t *) allctr;
817 RBTree_t **root = &bfallctr->mbc_root;
818 RBTree_t *x = *root;
819 RBTree_t *blk = NULL;
820 Uint blk_sz;
821
822 ASSERT(!cand_blk || cand_size >= size);
823
824 while (x) {
825 blk_sz = BF_BLK_SZ(x);
826 if (blk_sz < size) {
827 x = x->right;
828 }
829 else {
830 blk = x;
831 if (blk_sz == size)
832 break;
833 x = x->left;
834 }
835 }
836
837 if (!blk)
838 return NULL;
839
840 ASSERT(IS_TREE_NODE(blk));
841
842
843 #ifdef HARD_DEBUG
844 {
845 RBTree_t *ct_blk = check_tree(root, 0, size);
846 ASSERT(BF_BLK_SZ(ct_blk) == BF_BLK_SZ(blk));
847 }
848 #endif
849
850 if (cand_blk && cand_size <= BF_BLK_SZ(blk))
851 return NULL; /* cand_blk was better */
852
853 /* Use next block if it exist in order to avoid replacing
854 the tree node */
855 blk = BF_LIST_NEXT(blk) ? BF_LIST_NEXT(blk) : blk;
856
857 bf_unlink_free_block(allctr, (Block_t *) blk);
858 return (Block_t *) blk;
859 }
860
861
862 /*
863 * info_options()
864 */
865
866 static struct {
867 Eterm as;
868 Eterm aobf;
869 Eterm bf;
870 #ifdef DEBUG
871 Eterm end_of_atoms;
872 #endif
873 } am;
874
atom_init(Eterm * atom,char * name)875 static void ERTS_INLINE atom_init(Eterm *atom, char *name)
876 {
877 *atom = am_atom_put(name, sys_strlen(name));
878 }
879 #define AM_INIT(AM) atom_init(&am.AM, #AM)
880
881 static void
init_atoms(void)882 init_atoms(void)
883 {
884 #ifdef DEBUG
885 Eterm *atom;
886 #endif
887
888 if (atoms_initialized)
889 return;
890
891 #ifdef DEBUG
892 for (atom = (Eterm *) &am; atom <= &am.end_of_atoms; atom++) {
893 *atom = THE_NON_VALUE;
894 }
895 #endif
896 AM_INIT(as);
897 AM_INIT(aobf);
898 AM_INIT(bf);
899
900 #ifdef DEBUG
901 for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) {
902 ASSERT(*atom != THE_NON_VALUE);
903 }
904 #endif
905
906 atoms_initialized = 1;
907 }
908
909
910 #define bld_uint erts_bld_uint
911 #define bld_cons erts_bld_cons
912 #define bld_tuple erts_bld_tuple
913
914 static ERTS_INLINE void
add_2tup(Uint ** hpp,Uint * szp,Eterm * lp,Eterm el1,Eterm el2)915 add_2tup(Uint **hpp, Uint *szp, Eterm *lp, Eterm el1, Eterm el2)
916 {
917 *lp = bld_cons(hpp, szp, bld_tuple(hpp, szp, 2, el1, el2), *lp);
918 }
919
920 static Eterm
info_options(Allctr_t * allctr,char * prefix,fmtfn_t * print_to_p,void * print_to_arg,Uint ** hpp,Uint * szp)921 info_options(Allctr_t *allctr,
922 char *prefix,
923 fmtfn_t *print_to_p,
924 void *print_to_arg,
925 Uint **hpp,
926 Uint *szp)
927 {
928 BFAllctr_t *bfallctr = (BFAllctr_t *) allctr;
929 Eterm res = THE_NON_VALUE;
930
931 if (print_to_p) {
932 erts_print(*print_to_p,
933 print_to_arg,
934 "%sas: %s\n",
935 prefix,
936 bfallctr->address_order ? "aobf" : "bf");
937 }
938
939 if (hpp || szp) {
940
941 if (!atoms_initialized)
942 erts_exit(ERTS_ERROR_EXIT, "%s:%d: Internal error: Atoms not initialized",
943 __FILE__, __LINE__);;
944
945 res = NIL;
946 add_2tup(hpp, szp, &res,
947 am.as,
948 bfallctr->address_order ? am.aobf : am.bf);
949 }
950
951 return res;
952 }
953
954
955 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
956 * NOTE: erts_bfalc_test() is only supposed to be used for testing. *
957 * *
958 * Keep alloc_SUITE_data/allocator_test.h updated if changes are made *
959 * to erts_bfalc_test() *
960 \* */
961
962 UWord
erts_bfalc_test(UWord op,UWord a1,UWord a2)963 erts_bfalc_test(UWord op, UWord a1, UWord a2)
964 {
965 switch (op) {
966 case 0x200: return (UWord) ((BFAllctr_t *) a1)->address_order; /* IS_AOBF */
967 case 0x201: return (UWord) ((BFAllctr_t *) a1)->mbc_root;
968 case 0x202: return (UWord) ((RBTree_t *) a1)->parent;
969 case 0x203: return (UWord) ((RBTree_t *) a1)->left;
970 case 0x204: return (UWord) ((RBTree_t *) a1)->right;
971 case 0x205: return (UWord) BF_LIST_NEXT(a1);
972 case 0x206: return (UWord) IS_BLACK((RBTree_t *) a1);
973 case 0x207: return (UWord) IS_TREE_NODE((RBTree_t *) a1);
974 case 0x208: return (UWord) 1; /* IS_BF_ALGO */
975 case 0x20a: return (UWord) !((BFAllctr_t *) a1)->address_order; /* IS_BF */
976 case 0x20b: return (UWord) BF_LIST_PREV(a1);
977 default: ASSERT(0); return ~((UWord) 0);
978 }
979 }
980
981
982 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
983 * Debug functions *
984 \* */
985
986
987 #ifdef HARD_DEBUG
988
989 #define IS_LEFT_VISITED(FB) ((FB)->flags & LEFT_VISITED_FLG)
990 #define IS_RIGHT_VISITED(FB) ((FB)->flags & RIGHT_VISITED_FLG)
991
992 #define SET_LEFT_VISITED(FB) ((FB)->flags |= LEFT_VISITED_FLG)
993 #define SET_RIGHT_VISITED(FB) ((FB)->flags |= RIGHT_VISITED_FLG)
994
995 #define UNSET_LEFT_VISITED(FB) ((FB)->flags &= ~LEFT_VISITED_FLG)
996 #define UNSET_RIGHT_VISITED(FB) ((FB)->flags &= ~RIGHT_VISITED_FLG)
997
998
999 #if 0
1000 # define PRINT_TREE
1001 #else
1002 # undef PRINT_TREE
1003 #endif
1004
1005 #ifdef PRINT_TREE
1006 static void print_tree(RBTree_t *, int);
1007 #endif
1008
1009 /*
1010 * Checks that the order between parent and children are correct,
1011 * and that the Red-Black Tree properies are satisfied. if size > 0,
1012 * check_tree() returns a node that satisfies "best fit" resp.
1013 * "address order best fit".
1014 *
1015 * The Red-Black Tree properies are:
1016 * 1. Every node is either red or black.
1017 * 2. Every leaf (NIL) is black.
1018 * 3. If a node is red, then both its children are black.
1019 * 4. Every simple path from a node to a descendant leaf
1020 * contains the same number of black nodes.
1021 */
1022
1023 static RBTree_t *
check_tree(RBTree_t * root,int ao,Uint size)1024 check_tree(RBTree_t *root, int ao, Uint size)
1025 {
1026 RBTree_t *res = NULL;
1027 Sint blacks;
1028 Sint curr_blacks;
1029 RBTree_t *x;
1030
1031 #ifdef PRINT_TREE
1032 print_tree(root, ao);
1033 #endif
1034
1035 if (!root)
1036 return res;
1037
1038 x = root;
1039 ASSERT(IS_BLACK(x));
1040 ASSERT(!x->parent);
1041 curr_blacks = 1;
1042 blacks = -1;
1043
1044 while (x) {
1045 if (!IS_LEFT_VISITED(x)) {
1046 SET_LEFT_VISITED(x);
1047 if (x->left) {
1048 x = x->left;
1049 if (IS_BLACK(x))
1050 curr_blacks++;
1051 continue;
1052 }
1053 else {
1054 if (blacks < 0)
1055 blacks = curr_blacks;
1056 ASSERT(blacks == curr_blacks);
1057 }
1058 }
1059
1060 if (!IS_RIGHT_VISITED(x)) {
1061 SET_RIGHT_VISITED(x);
1062 if (x->right) {
1063 x = x->right;
1064 if (IS_BLACK(x))
1065 curr_blacks++;
1066 continue;
1067 }
1068 else {
1069 if (blacks < 0)
1070 blacks = curr_blacks;
1071 ASSERT(blacks == curr_blacks);
1072 }
1073 }
1074
1075
1076 if (IS_RED(x)) {
1077 ASSERT(IS_BLACK(x->right));
1078 ASSERT(IS_BLACK(x->left));
1079 }
1080
1081 ASSERT(x->parent || x == root);
1082
1083 if (x->left) {
1084 ASSERT(x->left->parent == x);
1085 if (ao) {
1086 ASSERT(BF_BLK_SZ(x->left) < BF_BLK_SZ(x)
1087 || (BF_BLK_SZ(x->left) == BF_BLK_SZ(x) && x->left < x));
1088 }
1089 else {
1090 ASSERT(IS_TREE_NODE(x->left));
1091 ASSERT(BF_BLK_SZ(x->left) < BF_BLK_SZ(x));
1092 }
1093 }
1094
1095 if (x->right) {
1096 ASSERT(x->right->parent == x);
1097 if (ao) {
1098 ASSERT(BF_BLK_SZ(x->right) > BF_BLK_SZ(x)
1099 || (BF_BLK_SZ(x->right) == BF_BLK_SZ(x) && x->right > x));
1100 }
1101 else {
1102 ASSERT(IS_TREE_NODE(x->right));
1103 ASSERT(BF_BLK_SZ(x->right) > BF_BLK_SZ(x));
1104 }
1105 }
1106
1107 if (size && BF_BLK_SZ(x) >= size) {
1108 if (ao) {
1109 if (!res
1110 || BF_BLK_SZ(x) < BF_BLK_SZ(res)
1111 || (BF_BLK_SZ(x) == BF_BLK_SZ(res) && x < res))
1112 res = x;
1113 }
1114 else {
1115 if (!res || BF_BLK_SZ(x) < BF_BLK_SZ(res))
1116 res = x;
1117 }
1118 }
1119
1120 UNSET_LEFT_VISITED(x);
1121 UNSET_RIGHT_VISITED(x);
1122 if (IS_BLACK(x))
1123 curr_blacks--;
1124 x = x->parent;
1125
1126 }
1127
1128 ASSERT(curr_blacks == 0);
1129
1130 UNSET_LEFT_VISITED(root);
1131 UNSET_RIGHT_VISITED(root);
1132
1133 return res;
1134
1135 }
1136
1137
1138 #ifdef PRINT_TREE
1139 #define INDENT_STEP 2
1140
1141 #include <stdio.h>
1142
1143 static void
print_tree_aux(RBTree_t * x,int indent)1144 print_tree_aux(RBTree_t *x, int indent)
1145 {
1146 int i;
1147
1148 if (!x) {
1149 for (i = 0; i < indent; i++) {
1150 putc(' ', stderr);
1151 }
1152 fprintf(stderr, "BLACK: nil\r\n");
1153 }
1154 else {
1155 print_tree_aux(x->right, indent + INDENT_STEP);
1156 for (i = 0; i < indent; i++) {
1157 putc(' ', stderr);
1158 }
1159 fprintf(stderr, "%s: sz=%lu addr=0x%lx\r\n",
1160 IS_BLACK(x) ? "BLACK" : "RED",
1161 BF_BLK_SZ(x),
1162 (Uint) x);
1163 print_tree_aux(x->left, indent + INDENT_STEP);
1164 }
1165 }
1166
1167
1168 static void
print_tree(RBTree_t * root,int ao)1169 print_tree(RBTree_t *root, int ao)
1170 {
1171 char *type = ao ? "Size-Adress" : "Size";
1172 fprintf(stderr, " --- %s tree begin ---\r\n", type);
1173 print_tree_aux(root, 0);
1174 fprintf(stderr, " --- %s tree end ---\r\n", type);
1175 }
1176
1177 #endif
1178
1179 #endif
1180