aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/sys
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2013-09-09 15:49:21 +0200
committerSverker Eriksson <[email protected]>2013-09-30 17:45:46 +0200
commitac32bccf21354d7e6896d8b83b6e9a45bb1bccd7 (patch)
treeb0fdae26c8867d6e10286f1a31efc5c2efc7db91 /erts/emulator/sys
parent2d64c6e31966d9e63d1aa1835d41ded22f799175 (diff)
downloadotp-ac32bccf21354d7e6896d8b83b6e9a45bb1bccd7.tar.gz
otp-ac32bccf21354d7e6896d8b83b6e9a45bb1bccd7.tar.bz2
otp-ac32bccf21354d7e6896d8b83b6e9a45bb1bccd7.zip
erts: Sort tree in super aligned sizes (SA_SZ_ADDR_ORDER)
Diffstat (limited to 'erts/emulator/sys')
-rw-r--r--erts/emulator/sys/common/erl_mmap.c52
1 files changed, 32 insertions, 20 deletions
diff --git a/erts/emulator/sys/common/erl_mmap.c b/erts/emulator/sys/common/erl_mmap.c
index 1d18c1fcc9..eae1a1a410 100644
--- a/erts/emulator/sys/common/erl_mmap.c
+++ b/erts/emulator/sys/common/erl_mmap.c
@@ -106,9 +106,12 @@ static ERTS_INLINE UWord parent_and_color(RBTNode* parent, int color)
enum SortOrder {
ADDR_ORDER, /* only address order */
- SZ_ADDR_ORDER, /* first size then address order as tiebreaker */
+ SA_SZ_ADDR_ORDER, /* first super-aligned size then address order */
SZ_REVERSE_ADDR_ORDER /* first size then reverse address order */
};
+#ifdef HARD_DEBUG
+static const char* sort_order_names[] = {"Address","SuperAlignedSize-Address","Size-RevAddress"};
+#endif
typedef struct {
RBTNode* root;
@@ -286,9 +289,17 @@ static ERTS_INLINE SWord cmp_nodes(enum SortOrder order,
ErtsFreeSegDesc* rdesc = node_to_desc(order, rhs);
RBT_ASSERT(lhs != rhs);
if (order != ADDR_ORDER) {
- SWord lsz = ldesc->end - ldesc->start;
- SWord rsz = rdesc->end - rdesc->start;
- SWord diff = lsz - rsz;
+ SWord lsz, rsz, diff;
+ if (order == SA_SZ_ADDR_ORDER) {
+ lsz = ERTS_SUPERALIGNED_FLOOR(ldesc->end) - ERTS_SUPERALIGNED_CEILING(ldesc->start);
+ rsz = ERTS_SUPERALIGNED_FLOOR(rdesc->end) - ERTS_SUPERALIGNED_CEILING(rdesc->start);
+ }
+ else {
+ RBT_ASSERT(order == SZ_REVERSE_ADDR_ORDER);
+ lsz = ldesc->end - ldesc->start;
+ rsz = rdesc->end - rdesc->start;
+ }
+ diff = lsz - rsz;
if (diff) return diff;
}
if (order != SZ_REVERSE_ADDR_ORDER) {
@@ -305,12 +316,14 @@ static ERTS_INLINE SWord cmp_with_node(enum SortOrder order,
{
ErtsFreeSegDesc* rdesc;
if (order != ADDR_ORDER) {
+ SWord rhs_sz, diff;
rdesc = snode_to_desc(rhs);
- {
- SWord rhs_sz = rdesc->end - rdesc->start;
- SWord diff = sz - rhs_sz;
- if (diff) return diff;
- }
+ if (order == SA_SZ_ADDR_ORDER)
+ rhs_sz = ERTS_SUPERALIGNED_FLOOR(rdesc->end) - ERTS_SUPERALIGNED_CEILING(rdesc->start);
+ else
+ rhs_sz = rdesc->end - rdesc->start;
+ diff = sz - rhs_sz;
+ if (diff) return diff;
}
else
rdesc = anode_to_desc(rhs);
@@ -860,7 +873,7 @@ static RBTNode* rbt_next_node(RBTNode* node)
/* The API to keep track of a bunch of separated (free) segments
(non-overlapping and non-adjacent).
*/
-static void init_free_seg_map(ErtsFreeSegMap*, int reverse_ao);
+static void init_free_seg_map(ErtsFreeSegMap*, enum SortOrder);
static void adjacent_free_seg(ErtsFreeSegMap*, char* start, char* end,
ErtsFreeSegDesc** under, ErtsFreeSegDesc** over);
static void insert_free_seg(ErtsFreeSegMap*, ErtsFreeSegDesc*, char* start, char* end);
@@ -869,12 +882,12 @@ static void delete_free_seg(ErtsFreeSegMap*, ErtsFreeSegDesc*);
static ErtsFreeSegDesc* lookup_free_seg(ErtsFreeSegMap*, SWord sz);
-static void init_free_seg_map(ErtsFreeSegMap* map, int reverse_ao)
+static void init_free_seg_map(ErtsFreeSegMap* map, enum SortOrder order)
{
map->atree.root = NULL;
map->atree.order = ADDR_ORDER;
map->stree.root = NULL;
- map->stree.order = reverse_ao ? SZ_REVERSE_ADDR_ORDER : SZ_ADDR_ORDER;
+ map->stree.order = order;
map->nseg = 0;
}
@@ -1931,8 +1944,8 @@ erts_mmap_init(ErtsMMapInit *init)
#endif
add_free_desc_area(mmap_state.sua.top, end);
- init_free_seg_map(&mmap_state.sa.map, 0);
- init_free_seg_map(&mmap_state.sua.map, 1);
+ init_free_seg_map(&mmap_state.sa.map, SA_SZ_ADDR_ORDER);
+ init_free_seg_map(&mmap_state.sua.map, SZ_REVERSE_ADDR_ORDER);
mmap_state.supercarrier = 1;
erts_have_erts_mmap |= ERTS_HAVE_ERTS_SUPERCARRIER_MMAP;
@@ -2125,10 +2138,9 @@ print_tree_aux(enum SortOrder order, RBTNode *x, int indent)
static void
print_tree(enum SortOrder order, RBTNode* root)
{
- static const char* type[] = {"Address","Size-Address","Size-RevAddress"};
- fprintf(stderr, " --- %s ordered tree begin ---\r\n", type[order]);
+ fprintf(stderr, " --- %s ordered tree begin ---\r\n", sort_order_names[order]);
print_tree_aux(order, root, 0);
- fprintf(stderr, " --- %s ordered tree end ---\r\n", type[order]);
+ fprintf(stderr, " --- %s ordered tree end ---\r\n", sort_order_names[order]);
}
#endif /* PRINT_TREE */
@@ -2140,10 +2152,10 @@ void test_it(void)
{
ErtsFreeSegMap map;
ErtsFreeSegDesc *desc, *under, *over, *d1, *d2;
- int i;
+ const int i = 1; /* reverse addr order */
- for (i=0; i<2; i++) {
- init_free_seg_map(&map, i);
+ {
+ init_free_seg_map(&map, SZ_REVERSE_ADDR_ORDER);
insert_free_seg(&map, alloc_desc(), (char*)0x11000, (char*)0x12000);
HARD_CHECK_TREE(&map.atree, 0); HARD_CHECK_TREE(&map.stree, 0);