From a64977f98e71aaf046dc81719459a8f9b03da90d Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 18 Oct 2018 23:11:31 +0200 Subject: erts: Fix debug_realloc for ptr==NULL --- erts/emulator/beam/erl_alloc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_alloc.c b/erts/emulator/beam/erl_alloc.c index 36c46fd7aa..cd679e32b0 100644 --- a/erts/emulator/beam/erl_alloc.c +++ b/erts/emulator/beam/erl_alloc.c @@ -4041,7 +4041,7 @@ debug_realloc(ErtsAlcType_t type, void *extra, void *ptr, Uint size) erts_hdbg_chk_blks(); #endif - if (old_size > size) + if (ptr && old_size > size) sys_memset((void *) (((char *) ptr) + size), 0xf, sizeof(Uint) + old_size - size); -- cgit v1.2.3 From 0d29c75482a2cd24501419d1eb702ee982c4d669 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 11 Oct 2018 16:36:09 +0200 Subject: erts: Fix compiler warning in erl_bif_binary.c --- erts/emulator/beam/erl_bif_binary.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_bif_binary.c b/erts/emulator/beam/erl_bif_binary.c index 5b3f091ccc..d465f6c6b9 100644 --- a/erts/emulator/beam/erl_bif_binary.c +++ b/erts/emulator/beam/erl_bif_binary.c @@ -1051,14 +1051,13 @@ static int do_binary_match_compile(Eterm argument, Eterm *tag, Binary **binp) Uint bitoffs, bitsize; byte *temp_alloc = NULL; MyAllocator my; - BMData *bmd; Binary *bin; ERTS_GET_BINARY_BYTES(comp_term, bytes, bitoffs, bitsize); if (bitoffs != 0) { bytes = erts_get_aligned_binary_bytes(comp_term, &temp_alloc); } - bmd = create_bmdata(&my, bytes, characters, &bin); + create_bmdata(&my, bytes, characters, &bin); erts_free_aligned_binary_bytes(temp_alloc); CHECK_ALLOCATOR(my); *tag = am_bm; -- cgit v1.2.3 From 79707448997e6b00d33d53935123cd9e3e330b58 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 8 Oct 2018 17:43:25 +0200 Subject: erts: Refactor ets ordered_set match spec key boundness --- erts/emulator/beam/erl_db_tree.c | 147 +++++++++++++++++++-------------------- 1 file changed, 72 insertions(+), 75 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index c6f1a0fc6d..70d233ff63 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -185,16 +185,20 @@ static void do_dump_tree2(DbTableTree*, int to, void *to_arg, int show, ** Datatypes */ +enum ms_key_boundness { + /* Order significant, larger means more "boundness" => less iteration */ + MS_KEY_UNBOUND = 0, + MS_KEY_PARTIALLY_BOUND = 1, + MS_KEY_BOUND = 2, + MS_KEY_IMPOSSIBLE = 3 +}; + /* * This structure is filled in by analyze_pattern() for the select * functions. */ struct mp_info { - int something_can_match; /* The match_spec is not "impossible" */ - int some_limitation; /* There is some limitation on the search - * area, i. e. least and/or most is set.*/ - int got_partial; /* The limitation has a partially bound - * key */ + enum ms_key_boundness key_boundness; Eterm least; /* The lowest matching key (possibly * partially bound expression) */ Eterm most; /* The highest matching key (possibly @@ -323,8 +327,9 @@ static void traverse_update_backwards(DbTableCommon *tb, void *, int), void *context); -static int key_given(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, - TreeDbTerm ***ret, Eterm *partly_bound); +static enum ms_key_boundness key_boundness(DbTableCommon *tb, TreeDbTerm **root, + Eterm pattern, + TreeDbTerm ***ret, Eterm *keyp); static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key); static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done); @@ -1187,22 +1192,21 @@ int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, RET_TO_BIF(NIL,errcode); } - if (!mpi.something_can_match) { + if (mpi.key_boundness == MS_KEY_IMPOSSIBLE) { RET_TO_BIF(NIL,DB_ERROR_NONE); /* can't possibly match anything */ } sc.mp = mpi.mp; - if (!mpi.got_partial && mpi.some_limitation && - CMP_EQ(mpi.least,mpi.most)) { + if (mpi.key_boundness == MS_KEY_BOUND) { doit_select(tb,*(mpi.save_term),&sc,0 /* direction doesn't matter */); RET_TO_BIF(sc.accum,DB_ERROR_NONE); } stack = get_any_stack((DbTable*)tb,stack_container); if (reverse) { - if (mpi.some_limitation) { + if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { if ((this = find_prev_from_pb_key(tb, *root, stack, mpi.least)) != NULL) { lastkey = GETKEY(tb, this->dbterm.tpl); } @@ -1210,7 +1214,7 @@ int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, } traverse_forward(tb, root, stack, lastkey, &doit_select, &sc); } else { - if (mpi.some_limitation) { + if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) { lastkey = GETKEY(tb, this->dbterm.tpl); } @@ -1405,21 +1409,20 @@ int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root RET_TO_BIF(NIL,errcode); } - if (!mpi.something_can_match) { + if (mpi.key_boundness == MS_KEY_IMPOSSIBLE) { RET_TO_BIF(make_small(0),DB_ERROR_NONE); /* can't possibly match anything */ } sc.mp = mpi.mp; - if (!mpi.got_partial && mpi.some_limitation && - CMP_EQ(mpi.least,mpi.most)) { + if (mpi.key_boundness == MS_KEY_BOUND) { doit_select_count(tb,*(mpi.save_term),&sc,0 /* dummy */); RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE); } stack = get_any_stack((DbTable*)tb, stack_container); - if (mpi.some_limitation) { + if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) { lastkey = GETKEY(tb, this->dbterm.tpl); } @@ -1513,15 +1516,14 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root RET_TO_BIF(NIL,errcode); } - if (!mpi.something_can_match) { + if (mpi.key_boundness == MS_KEY_IMPOSSIBLE) { RET_TO_BIF(am_EOT,DB_ERROR_NONE); /* can't possibly match anything */ } sc.mp = mpi.mp; - if (!mpi.got_partial && mpi.some_limitation && - CMP_EQ(mpi.least,mpi.most)) { + if (mpi.key_boundness == MS_KEY_BOUND) { doit_select(tb,*(mpi.save_term),&sc, 0 /* direction doesn't matter */); if (sc.accum != NIL) { hp=HAlloc(p, 3); @@ -1533,7 +1535,7 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root stack = get_any_stack((DbTable*)tb,stack_container); if (reverse) { - if (mpi.some_limitation) { + if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) { lastkey = GETKEY(tb, this->dbterm.tpl); } @@ -1541,7 +1543,7 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root } traverse_backwards(tb, root, stack, lastkey, &doit_select_chunk, &sc); } else { - if (mpi.some_limitation) { + if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { if ((this = find_prev_from_pb_key(tb, *root, stack, mpi.least)) != NULL) { lastkey = GETKEY(tb, this->dbterm.tpl); } @@ -1777,21 +1779,20 @@ int db_select_delete_tree_common(Process *p, DbTable *tbl, RET_TO_BIF(0,errcode); } - if (!mpi.something_can_match) { + if (mpi.key_boundness == MS_KEY_IMPOSSIBLE) { RET_TO_BIF(make_small(0),DB_ERROR_NONE); /* can't possibly match anything */ } sc.mp = mpi.mp; - if (!mpi.got_partial && mpi.some_limitation && - CMP_EQ(mpi.least,mpi.most)) { + if (mpi.key_boundness == MS_KEY_BOUND) { doit_select_delete(&tbl->common,*(mpi.save_term),&sc, 0 /* direction doesn't matter */); RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE); } - if (mpi.some_limitation) { + if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { if ((this = find_next_from_pb_key(&tbl->common, *root, stack, mpi.most)) != NULL) { lastkey = GETKEY(&tbl->common, this->dbterm.tpl); } @@ -1988,23 +1989,22 @@ int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **ro RET_TO_BIF(NIL,errcode); } - if (!mpi.something_can_match) { + if (mpi.key_boundness == MS_KEY_IMPOSSIBLE) { RET_TO_BIF(make_small(0),DB_ERROR_NONE); /* can't possibly match anything */ } sc.mp = mpi.mp; - if (!mpi.got_partial && mpi.some_limitation && - CMP_EQ(mpi.least,mpi.most)) { - doit_select_replace(tb,mpi.save_term,&sc,0 /* dummy */); + if (mpi.key_boundness == MS_KEY_BOUND) { + doit_select_replace(tb,*mpi.save_term,&sc,0 /* dummy */); reset_static_stack(stack_container); /* may refer replaced term */ RET_TO_BIF(erts_make_integer(sc.replaced,p),DB_ERROR_NONE); } stack = get_any_stack((DbTable*)tb,stack_container); - if (mpi.some_limitation) { + if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) { lastkey = GETKEY(tb, this->dbterm.tpl); } @@ -2340,14 +2340,11 @@ static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, int i; int num_heads = 0; Eterm key; - Eterm partly_bound; - int res; - Eterm least = 0; - Eterm most = 0; + Eterm least = THE_NON_VALUE; + Eterm most = THE_NON_VALUE; + enum ms_key_boundness boundness; - mpi->some_limitation = 1; - mpi->got_partial = 0; - mpi->something_can_match = 0; + mpi->key_boundness = MS_KEY_IMPOSSIBLE; mpi->mp = NULL; mpi->save_term = NULL; @@ -2401,30 +2398,29 @@ static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, } ++i; - partly_bound = NIL; - res = key_given(tb, root, tpl, &(mpi->save_term), &partly_bound); - if ( res >= 0 ) { /* Can match something */ - key = 0; - mpi->something_can_match = 1; - if (res > 0) { - key = GETKEY(tb,tuple_val(tpl)); - } else if (partly_bound != NIL) { - mpi->got_partial = 1; - key = partly_bound; - } else { - mpi->some_limitation = 0; - } - if (key != 0) { - if (least == 0 || - partly_bound_can_match_lesser(key,least)) { - least = key; - } - if (most == 0 || - partly_bound_can_match_greater(key,most)) { - most = key; - } - } - } + boundness = key_boundness(tb, root, tpl, &(mpi->save_term), &key); + switch (boundness) + { + case MS_KEY_BOUND: + case MS_KEY_PARTIALLY_BOUND: + if (is_non_value(least) || partly_bound_can_match_lesser(key,least)) { + least = key; + } + if (is_non_value(most) || partly_bound_can_match_greater(key,most)) { + most = key; + } + break; + case MS_KEY_IMPOSSIBLE: + case MS_KEY_UNBOUND: + break; + } + if (mpi->key_boundness > boundness) + mpi->key_boundness = boundness; + } + + if (mpi->key_boundness == MS_KEY_BOUND && !CMP_EQ(least, most)) { + /* Several different bound keys */ + mpi->key_boundness = MS_KEY_PARTIALLY_BOUND; } mpi->least = least; mpi->most = most; @@ -3168,33 +3164,34 @@ static void traverse_update_backwards(DbTableCommon *tb, } } -/* - * Returns 0 if not given 1 if given and -1 on no possible match - * if key is given; *ret is set to point to the object concerned. - */ -static int key_given(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, - TreeDbTerm ***ret, Eterm *partly_bound) +static enum ms_key_boundness key_boundness(DbTableCommon *tb, TreeDbTerm **root, + Eterm pattern, TreeDbTerm ***ret, + Eterm *keyp) { TreeDbTerm **this; Eterm key; ASSERT(ret != NULL); if (pattern == am_Underscore || db_is_variable(pattern) != -1) - return 0; + return MS_KEY_UNBOUND; key = db_getkey(tb->keypos, pattern); if (is_non_value(key)) - return -1; /* can't possibly match anything */ + return MS_KEY_IMPOSSIBLE; /* can't possibly match anything */ if (!db_has_variable(key)) { /* Bound key */ if (( this = find_node2(tb, root, key) ) == NULL) { - return -1; + return MS_KEY_IMPOSSIBLE; } *ret = this; - return 1; - } else if (partly_bound != NULL && key != am_Underscore && - db_is_variable(key) < 0 && !db_has_map(key)) - *partly_bound = key; + *keyp = key; + return MS_KEY_BOUND; + } else if (key != am_Underscore && + db_is_variable(key) < 0 && !db_has_map(key)) { + + *keyp = key; + return MS_KEY_PARTIALLY_BOUND; + } - return 0; + return MS_KEY_UNBOUND; } -- cgit v1.2.3 From cb76aae94c6e9ec3a4e1a8179883591264f5112f Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 9 Oct 2018 15:54:40 +0200 Subject: erts: Refactor ets:select* bound key lookup Move lookup from analyze_pattern to callers. --- erts/emulator/beam/erl_db_tree.c | 68 +++++++++++++++++++++------------------- 1 file changed, 36 insertions(+), 32 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index 70d233ff63..4f280bf641 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -203,10 +203,6 @@ struct mp_info { * partially bound expression) */ Eterm most; /* The highest matching key (possibly * partially bound expression) */ - - TreeDbTerm **save_term; /* If the key is completely bound, this - * will be the Tree node we're searching - * for, otherwise it will be useless */ Binary *mp; /* The compiled match program */ }; @@ -327,13 +323,12 @@ static void traverse_update_backwards(DbTableCommon *tb, void *, int), void *context); -static enum ms_key_boundness key_boundness(DbTableCommon *tb, TreeDbTerm **root, - Eterm pattern, - TreeDbTerm ***ret, Eterm *keyp); +static enum ms_key_boundness key_boundness(DbTableCommon *tb, + Eterm pattern, Eterm *keyp); static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key); static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done); -static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, +static int analyze_pattern(DbTableCommon *tb, Eterm pattern, extra_match_validator_t extra_validator, /* Optional callback */ struct mp_info *mpi); static int doit_select(DbTableCommon *tb, @@ -1188,7 +1183,7 @@ int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, sc.got = 0; sc.chunk_size = 0; - if ((errcode = analyze_pattern(tb, root, pattern, NULL, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(NIL,errcode); } @@ -1200,7 +1195,10 @@ int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, sc.mp = mpi.mp; if (mpi.key_boundness == MS_KEY_BOUND) { - doit_select(tb,*(mpi.save_term),&sc,0 /* direction doesn't matter */); + ASSERT(CMP_EQ(mpi.least, mpi.most)); + this = find_node(tb, *root, mpi.least, NULL); + if (this) + doit_select(tb, this, &sc, 0 /* direction doesn't matter */); RET_TO_BIF(sc.accum,DB_ERROR_NONE); } @@ -1405,7 +1403,7 @@ int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root sc.keypos = tb->keypos; sc.got = 0; - if ((errcode = analyze_pattern(tb, root, pattern, NULL, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(NIL,errcode); } @@ -1417,7 +1415,10 @@ int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root sc.mp = mpi.mp; if (mpi.key_boundness == MS_KEY_BOUND) { - doit_select_count(tb,*(mpi.save_term),&sc,0 /* dummy */); + ASSERT(CMP_EQ(mpi.least, mpi.most)); + this = find_node(tb, *root, mpi.least, NULL); + if (this) + doit_select_count(tb, this, &sc, 0 /* dummy */); RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE); } @@ -1512,7 +1513,7 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root sc.got = 0; sc.chunk_size = chunk_size; - if ((errcode = analyze_pattern(tb, root, pattern, NULL, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(NIL,errcode); } @@ -1524,7 +1525,10 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root sc.mp = mpi.mp; if (mpi.key_boundness == MS_KEY_BOUND) { - doit_select(tb,*(mpi.save_term),&sc, 0 /* direction doesn't matter */); + ASSERT(CMP_EQ(mpi.least, mpi.most)); + this = find_node(tb, *root, mpi.least, NULL); + if (this) + doit_select(tb, this, &sc, 0 /* direction doesn't matter */); if (sc.accum != NIL) { hp=HAlloc(p, 3); RET_TO_BIF(TUPLE2(hp,sc.accum,am_EOT),DB_ERROR_NONE); @@ -1775,7 +1779,7 @@ int db_select_delete_tree_common(Process *p, DbTable *tbl, sc.root = root; sc.stack = stack; - if ((errcode = analyze_pattern(&tbl->common, root, pattern, NULL, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(&tbl->common, pattern, NULL, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(0,errcode); } @@ -1787,7 +1791,10 @@ int db_select_delete_tree_common(Process *p, DbTable *tbl, sc.mp = mpi.mp; if (mpi.key_boundness == MS_KEY_BOUND) { - doit_select_delete(&tbl->common,*(mpi.save_term),&sc, 0 /* direction doesn't + ASSERT(CMP_EQ(mpi.least, mpi.most)); + this = find_node(&tbl->common, *root, mpi.least, NULL); + if (this) + doit_select_delete(&tbl->common, this, &sc, 0 /* direction doesn't matter */); RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE); } @@ -1985,7 +1992,7 @@ int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **ro sc.keypos = tb->keypos; sc.replaced = 0; - if ((errcode = analyze_pattern(tb, root, pattern, db_match_keeps_key, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(tb, pattern, db_match_keeps_key, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(NIL,errcode); } @@ -1997,8 +2004,13 @@ int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **ro sc.mp = mpi.mp; if (mpi.key_boundness == MS_KEY_BOUND) { - doit_select_replace(tb,*mpi.save_term,&sc,0 /* dummy */); - reset_static_stack(stack_container); /* may refer replaced term */ + TreeDbTerm** pp; + ASSERT(CMP_EQ(mpi.least, mpi.most)); + pp = find_node2(tb, root, mpi.least); + if (pp) { + doit_select_replace(tb, pp, &sc, 0 /* dummy */); + reset_static_stack(stack_container); /* may refer replaced term */ + } RET_TO_BIF(erts_make_integer(sc.replaced,p),DB_ERROR_NONE); } @@ -2328,7 +2340,7 @@ static TreeDbTerm *linkout_object_tree(DbTableCommon *tb, TreeDbTerm **root, ** For the select functions, analyzes the pattern and determines which ** part of the tree should be searched. Also compiles the match program */ -static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, +static int analyze_pattern(DbTableCommon *tb, Eterm pattern, extra_match_validator_t extra_validator, /* Optional callback */ struct mp_info *mpi) { @@ -2339,14 +2351,12 @@ static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, Eterm *ptpl; int i; int num_heads = 0; - Eterm key; Eterm least = THE_NON_VALUE; Eterm most = THE_NON_VALUE; enum ms_key_boundness boundness; mpi->key_boundness = MS_KEY_IMPOSSIBLE; mpi->mp = NULL; - mpi->save_term = NULL; for (lst = pattern; is_list(lst); lst = CDR(list_val(lst))) ++num_heads; @@ -2367,6 +2377,7 @@ static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, Eterm match; Eterm guard; Eterm body; + Eterm key; ttpl = CAR(list_val(lst)); if (!is_tuple(ttpl)) { @@ -2398,7 +2409,7 @@ static int analyze_pattern(DbTableCommon *tb, TreeDbTerm **root, Eterm pattern, } ++i; - boundness = key_boundness(tb, root, tpl, &(mpi->save_term), &key); + boundness = key_boundness(tb, tpl, &key); switch (boundness) { case MS_KEY_BOUND: @@ -3164,24 +3175,17 @@ static void traverse_update_backwards(DbTableCommon *tb, } } -static enum ms_key_boundness key_boundness(DbTableCommon *tb, TreeDbTerm **root, - Eterm pattern, TreeDbTerm ***ret, - Eterm *keyp) +static enum ms_key_boundness key_boundness(DbTableCommon *tb, + Eterm pattern, Eterm *keyp) { - TreeDbTerm **this; Eterm key; - ASSERT(ret != NULL); if (pattern == am_Underscore || db_is_variable(pattern) != -1) return MS_KEY_UNBOUND; key = db_getkey(tb->keypos, pattern); if (is_non_value(key)) return MS_KEY_IMPOSSIBLE; /* can't possibly match anything */ if (!db_has_variable(key)) { /* Bound key */ - if (( this = find_node2(tb, root, key) ) == NULL) { - return MS_KEY_IMPOSSIBLE; - } - *ret = this; *keyp = key; return MS_KEY_BOUND; } else if (key != am_Underscore && -- cgit v1.2.3 From c7ea2f9bde2cc3125a12d820cca36582ee1046c5 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 9 Oct 2018 16:27:15 +0200 Subject: erts: Add table type assertions for static stack access DbTableCATree has no static stack. --- erts/emulator/beam/erl_db_tree.c | 30 ++++++++++++++++++------------ 1 file changed, 18 insertions(+), 12 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index 4f280bf641..4c58c40b9c 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -70,8 +70,10 @@ */ ERTS_INLINE static DbTreeStack* get_static_stack(DbTableTree* tb) { - if (tb != NULL && !erts_atomic_xchg_acqb(&tb->is_stack_busy, 1)) { - return &tb->static_stack; + if (tb != NULL) { + ASSERT(IS_TREE_TABLE(tb->common.type)); + if (!erts_atomic_xchg_acqb(&tb->is_stack_busy, 1)) + return &tb->static_stack; } return NULL; } @@ -82,9 +84,10 @@ ERTS_INLINE static DbTreeStack* get_static_stack(DbTableTree* tb) static DbTreeStack* get_any_stack(DbTable* tb, DbTableTree* stack_container) { DbTreeStack* stack; - if (stack_container != NULL && - !erts_atomic_xchg_acqb(&stack_container->is_stack_busy, 1)) { - return &stack_container->static_stack; + if (stack_container != NULL) { + ASSERT(IS_TREE_TABLE(stack_container->common.type)); + if (!erts_atomic_xchg_acqb(&stack_container->is_stack_busy, 1)) + return &stack_container->static_stack; } stack = erts_db_alloc(ERTS_ALC_T_DB_STK, tb, sizeof(DbTreeStack) + sizeof(TreeDbTerm*) * STACK_NEED); @@ -96,14 +99,16 @@ static DbTreeStack* get_any_stack(DbTable* tb, DbTableTree* stack_container) static void release_stack(DbTable* tb, DbTableTree* stack_container, DbTreeStack* stack) { - if (stack_container != NULL && stack == &stack_container->static_stack) { - ASSERT(erts_atomic_read_nob(&stack_container->is_stack_busy) == 1); - erts_atomic_set_relb(&stack_container->is_stack_busy, 0); - } - else { - erts_db_free(ERTS_ALC_T_DB_STK, tb, - (void *) stack, sizeof(DbTreeStack) + sizeof(TreeDbTerm*) * STACK_NEED); + if (stack_container != NULL) { + ASSERT(IS_TREE_TABLE(stack_container->common.type)); + if (stack == &stack_container->static_stack) { + ASSERT(erts_atomic_read_nob(&stack_container->is_stack_busy) == 1); + erts_atomic_set_relb(&stack_container->is_stack_busy, 0); + return; + } } + erts_db_free(ERTS_ALC_T_DB_STK, tb, + (void *) stack, sizeof(DbTreeStack) + sizeof(TreeDbTerm*) * STACK_NEED); } static ERTS_INLINE void reset_stack(DbTreeStack* stack) @@ -117,6 +122,7 @@ static ERTS_INLINE void reset_stack(DbTreeStack* stack) static ERTS_INLINE void reset_static_stack(DbTableTree* tb) { if (tb != NULL) { + ASSERT(IS_TREE_TABLE(tb->common.type)); reset_stack(&tb->static_stack); } } -- cgit v1.2.3 From c45856710651882d16686be82626ae6058590005 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 16 Oct 2018 21:51:34 +0200 Subject: erts: Remove tree merging for ets:select* --- erts/emulator/beam/erl_db_catree.c | 404 ++++++++++++++++++--- erts/emulator/beam/erl_db_catree.h | 19 + erts/emulator/beam/erl_db_tree.c | 658 +++++++++++++++++++++------------- erts/emulator/beam/erl_db_tree_util.h | 46 +-- 4 files changed, 805 insertions(+), 322 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index a8e48bce1b..2c3b262312 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -158,6 +158,7 @@ db_lookup_dbterm_catree(Process *, DbTable *, Eterm key, Eterm obj, DbUpdateHandle*); static void db_finalize_dbterm_catree(int cret, DbUpdateHandle *); + /* ** External interface */ @@ -710,6 +711,40 @@ void unlock_route_node(DbTableCATreeNode *route_node) erts_mtx_unlock(&route_node->u.route.lock); } +static ERTS_INLINE +void init_root_iterator(DbTableCATree* tb, CATreeRootIterator* iter, + int read_only) +{ + iter->tb = tb; + iter->read_only = read_only; + iter->locked_bnode = NULL; + iter->next_route_key = THE_NON_VALUE; +} + +static ERTS_INLINE +void lock_iter_base_node(CATreeRootIterator* iter, + DbTableCATreeBaseNode *base_node) +{ + ASSERT(!iter->locked_bnode); + if (iter->read_only) + rlock_base_node(base_node); + else + wlock_base_node(base_node); + iter->locked_bnode = base_node; +} + +static ERTS_INLINE +void unlock_iter_base_node(CATreeRootIterator* iter) +{ + ASSERT(iter->locked_bnode); + if (iter->read_only) + runlock_base_node(iter->locked_bnode); + else + wunlock_base_node(iter->locked_bnode); + iter->locked_bnode = NULL; +} + + /* * The following macros are used to create the ETS functions that only @@ -717,6 +752,32 @@ void unlock_route_node(DbTableCATreeNode *route_node) * db_erase_catree). */ + +typedef struct +{ + DbTableCATreeNode *parent; + int current_level; +} FindBaseNode; + +static ERTS_INLINE +DbTableCATreeBaseNode* find_base_node(DbTableCATree* tb, Eterm key, + FindBaseNode* fbn) +{ + DbTableCATreeNode* ERTS_RESTRICT node = GET_ROOT_ACQB(tb); + fbn->parent = NULL; + fbn->current_level = 0; + while (!node->is_base_node) { + fbn->current_level++; + fbn->parent = node; + if (cmp_key_route(key, node) < 0) { + node = GET_LEFT_ACQB(node); + } else { + node = GET_RIGHT_ACQB(node); + } + } + return &node->u.base; +} + #define ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(LOCK,UNLOCK) \ int retry; \ DbTableCATreeNode *current_node; \ @@ -1675,7 +1736,10 @@ void db_initialize_catree(void) int db_create_catree(Process *p, DbTable *tbl) { DbTableCATree *tb = &tbl->catree; - DbTableCATreeNode *root = create_base_node(tb, NULL, NIL); + DbTableCATreeNode *root; + + root = create_base_node(tb, NULL, + NIL);/* lc_key of first base node does not matter */ tb->deletion = 0; tb->base_nodes_to_free_list = NULL; erts_atomic_init_relb(&(tb->root), (erts_aint_t)root); @@ -1781,6 +1845,226 @@ static int db_get_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) return erl_db_catree_do_operation_get(tb, key, p, ret); } + + +TreeDbTerm** catree_find_root(Eterm key, CATreeRootIterator* iter) +{ + FindBaseNode fbn; + DbTableCATreeBaseNode* base_node; + + while (1) { + base_node = find_base_node(iter->tb, key, &fbn); + lock_iter_base_node(iter, base_node); + if (base_node->is_valid) + break; + unlock_iter_base_node(iter); + } + return &base_node->root; +} + + +TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, + CATreeRootIterator* iter) +{ +#ifdef DEBUG + DbTableCATreeNode *rejected_base = NULL; +#endif + DbTableCATreeNode *node; + DbTableCATreeNode* next_route_node; + + ASSERT(!iter->locked_bnode); + + while (1) { + node = GET_ROOT_ACQB(iter->tb); + next_route_node = NULL; + while (!node->is_base_node) { + if (cmp_partly_bound(key, GET_ROUTE_NODE_KEY(node)) <= 0) { + node = GET_LEFT_ACQB(node); + } else { + next_route_node = node; + node = GET_RIGHT_ACQB(node); + } + } + ASSERT(node != rejected_base); + lock_iter_base_node(iter, &node->u.base); + if (node->u.base.is_valid) { + if (node->u.base.root || !next_route_node) { + iter->next_route_key = (next_route_node ? + next_route_node->u.route.key.term : + THE_NON_VALUE); + return &node->u.base.root; + } + unlock_iter_base_node(iter); + iter->next_route_key = next_route_node->u.route.key.term; + return catree_find_next_root(iter); + } + /* Retry */ + unlock_iter_base_node(iter); +#ifdef DEBUG + rejected_base = node; +#endif + } +} + +TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next) +{ +#ifdef DEBUG + DbTableCATreeNode *rejected_base = NULL; +#endif + DbTableCATreeNode *node; + DbTableCATreeNode* next_route_node; + Eterm key = iter->next_route_key; + + if (iter->locked_bnode) + unlock_iter_base_node(iter); + + if (is_non_value(key)) + return NULL; + + while (1) { + node = GET_ROOT_ACQB(iter->tb); + next_route_node = NULL; + while (!node->is_base_node) { + if (next) { + if (cmp_key_route(key,node) < 0) { + next_route_node = node; + node = GET_LEFT_ACQB(node); + } else { + node = GET_RIGHT_ACQB(node); + } + } + else { + if (cmp_key_route(key,node) > 0) { + next_route_node = node; + node = GET_RIGHT_ACQB(node); + } else { + node = GET_LEFT_ACQB(node); + } + } + } + ASSERT(node != rejected_base); + lock_iter_base_node(iter, &node->u.base); + if (node->u.base.is_valid) { + if (node->u.base.root) { + iter->next_route_key = (next_route_node ? + next_route_node->u.route.key.term : + THE_NON_VALUE); + iter->locked_bnode = &node->u.base; + return &node->u.base.root; + } + if (!next_route_node) { + unlock_iter_base_node(iter); + return NULL; + } + key = next_route_node->u.route.key.term; + } + /* Retry */ + unlock_iter_base_node(iter); +#ifdef DEBUG + rejected_base = node; +#endif + } +} + +TreeDbTerm** catree_find_next_root(CATreeRootIterator *iter) +{ + return catree_find_nextprev_root(iter, 1); +} + +TreeDbTerm** catree_find_prev_root(CATreeRootIterator *iter) +{ + return catree_find_nextprev_root(iter, 0); +} + + +TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, + CATreeRootIterator* iter) +{ +#ifdef DEBUG + DbTableCATreeNode *rejected_base = NULL; +#endif + DbTableCATreeNode *node; + DbTableCATreeNode* next_route_node; + + ASSERT(!iter->locked_bnode); + + while (1) { + node = GET_ROOT_ACQB(iter->tb); + next_route_node = NULL; + while (!node->is_base_node) { + if (cmp_partly_bound(key, GET_ROUTE_NODE_KEY(node)) >= 0) { + next_route_node = node; + node = GET_RIGHT_ACQB(node); + } else { + node = GET_LEFT_ACQB(node); + } + } + ASSERT(node != rejected_base); + lock_iter_base_node(iter, &node->u.base); + if (node->u.base.is_valid) { + if (node->u.base.root || !next_route_node) { + iter->next_route_key = (next_route_node ? + next_route_node->u.route.key.term : + THE_NON_VALUE); + iter->locked_bnode = &node->u.base; + return &node->u.base.root; + } + unlock_iter_base_node(iter); + iter->next_route_key = next_route_node->u.route.key.term; + return catree_find_prev_root(iter); + } + /* Retry */ + unlock_iter_base_node(iter); +#ifdef DEBUG + rejected_base = node; +#endif + } +} + +static TreeDbTerm** catree_find_firstlast_root(CATreeRootIterator* iter, + int first) +{ +#ifdef DEBUG + DbTableCATreeNode *rejected_base = NULL; +#endif + DbTableCATreeNode *node; + DbTableCATreeNode* next_route_node; + + while (1) { + node = GET_ROOT_ACQB(iter->tb); + next_route_node = NULL; + while (!node->is_base_node) { + next_route_node = node; + node = first ? GET_LEFT_ACQB(node) : GET_RIGHT_ACQB(node); + } + ASSERT(node != rejected_base); + lock_iter_base_node(iter, &node->u.base); + if (node->u.base.is_valid) { + iter->next_route_key = (next_route_node ? + next_route_node->u.route.key.term : + THE_NON_VALUE); + iter->locked_bnode = &node->u.base; + return &node->u.base.root; + } + /* Retry */ + unlock_iter_base_node(iter); +#ifdef DEBUG + rejected_base = node; +#endif + } +} + +TreeDbTerm** catree_find_first_root(CATreeRootIterator* iter) +{ + return catree_find_firstlast_root(iter, 1); +} + +TreeDbTerm** catree_find_last_root(CATreeRootIterator* iter) +{ + return catree_find_firstlast_root(iter, 0); +} + + #define ERL_DB_CATREE_DO_OPERATION_MEMBER_PARAMS Eterm *ret ERL_DB_CATREE_CREATE_DO_READ_OPERATION_FUNCTION(member, ERL_DB_CATREE_DO_OPERATION_MEMBER_PARAMS, @@ -1861,25 +2145,28 @@ static int db_select_continue_catree(Process *p, Eterm *ret) { int result; - DbTableCATreeNode *base; - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_continue_tree_common(p, &tbl->common, &base->u.base.root, - continuation, ret, NULL); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 1); + result = db_select_continue_tree_common(p, &tbl->common, + continuation, ret, NULL, &iter); + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); + return result; } - static int db_select_catree(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, int reverse, Eterm *ret) { int result; - DbTableCATreeNode *base; - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_tree_common(p, &tbl->common, &base->u.base.root, - tid, pattern, reverse, ret, - NULL); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 1); + result = db_select_tree_common(p, tbl, tid, pattern, reverse, ret, + NULL, &iter); + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); return result; } @@ -1889,12 +2176,14 @@ static int db_select_count_continue_catree(Process *p, Eterm *ret) { int result; - DbTableCATreeNode *base; - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_count_continue_tree_common(p, &tbl->common, - &base->u.base.root, - continuation, ret, NULL); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 1); + result = db_select_count_continue_tree_common(p, tbl, + continuation, ret, NULL, + &iter); + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); return result; } @@ -1902,11 +2191,14 @@ static int db_select_count_catree(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, Eterm *ret) { int result; - DbTableCATreeNode *base; - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_count_tree_common(p, &tbl->common, &base->u.base.root, - tid, pattern, ret, NULL); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 1); + result = db_select_count_tree_common(p, tbl, + tid, pattern, ret, NULL, &iter); + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); + return result; } @@ -1915,11 +2207,14 @@ static int db_select_chunk_catree(Process *p, DbTable *tbl, Eterm tid, int reversed, Eterm *ret) { int result; - DbTableCATreeNode *base; - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_chunk_tree_common(p, &tbl->common, &base->u.base.root, - tid, pattern, chunk_size, reversed, ret, NULL); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 1); + result = db_select_chunk_tree_common(p, tbl, + tid, pattern, chunk_size, reversed, ret, + NULL, &iter); + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); return result; } @@ -1931,12 +2226,14 @@ static int db_select_delete_continue_catree(Process *p, DbTreeStack stack; TreeDbTerm * stack_array[STACK_NEED]; int result; - DbTableCATreeNode *base; + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 0); init_tree_stack(&stack, stack_array, 0); - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_delete_continue_tree_common(p, tbl, &base->u.base.root, - continuation, ret, &stack); - wunlock_base_node(&(base->u.base)); + result = db_select_delete_continue_tree_common(p, tbl, continuation, ret, + &stack, &iter); + if (iter.locked_bnode) + wunlock_base_node(iter.locked_bnode); return result; } @@ -1946,12 +2243,15 @@ static int db_select_delete_catree(Process *p, DbTable *tbl, Eterm tid, DbTreeStack stack; TreeDbTerm * stack_array[STACK_NEED]; int result; - DbTableCATreeNode *base; + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 0); init_tree_stack(&stack, stack_array, 0); - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_delete_tree_common(p, tbl, &base->u.base.root, - tid, pattern, ret, &stack); - wunlock_base_node(&(base->u.base)); + result = db_select_delete_tree_common(p, tbl, + tid, pattern, ret, &stack, + &iter); + if (iter.locked_bnode) + wunlock_base_node(iter.locked_bnode); return result; } @@ -1959,12 +2259,13 @@ static int db_select_replace_catree(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, Eterm *ret) { int result; - DbTableCATreeNode *base; - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_replace_tree_common(p, &tbl->common, - &base->u.base.root, - tid, pattern, ret, NULL); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 0); + result = db_select_replace_tree_common(p, tbl, + tid, pattern, ret, NULL, &iter); + if (iter.locked_bnode) + wunlock_base_node(iter.locked_bnode); return result; } @@ -1972,12 +2273,13 @@ static int db_select_replace_continue_catree(Process *p, DbTable *tbl, Eterm continuation, Eterm *ret) { int result; - DbTableCATreeNode *base; - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_select_replace_continue_tree_common(p, &tbl->common, - &base->u.base.root, - continuation, ret, NULL); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 0); + result = db_select_replace_continue_tree_common(p, tbl, continuation, ret, + NULL, &iter); + if (iter.locked_bnode) + wunlock_base_node(iter.locked_bnode); return result; } diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h index f9c0784289..510a9e81d3 100644 --- a/erts/emulator/beam/erl_db_catree.h +++ b/erts/emulator/beam/erl_db_catree.h @@ -92,11 +92,30 @@ typedef struct db_table_catree { int is_routing_nodes_freed; } DbTableCATree; +typedef struct { + DbTableCATree* tb; + Eterm next_route_key; + DbTableCATreeBaseNode* locked_bnode; + int read_only; +} CATreeRootIterator; + + void db_initialize_catree(void); int db_create_catree(Process *p, DbTable *tbl); +TreeDbTerm** catree_find_root(Eterm key, CATreeRootIterator*); + +TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, CATreeRootIterator*); +TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, CATreeRootIterator*); +TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator*, int next); +TreeDbTerm** catree_find_next_root(CATreeRootIterator*); +TreeDbTerm** catree_find_prev_root(CATreeRootIterator*); +TreeDbTerm** catree_find_first_root(CATreeRootIterator*); +TreeDbTerm** catree_find_last_root(CATreeRootIterator*); + + #ifdef ERTS_ENABLE_LOCK_COUNT void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable); #endif diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index 4c58c40b9c..71ec6e28e5 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -212,10 +212,16 @@ struct mp_info { Binary *mp; /* The compiled match program */ }; +struct select_common { + TreeDbTerm **root; +}; + + /* * Used by doit_select(_chunk) */ struct select_context { + struct select_common common; Process *p; Eterm accum; Binary *mp; @@ -231,6 +237,7 @@ struct select_context { * Used by doit_select_count */ struct select_count_context { + struct select_common common; Process *p; Binary *mp; Eterm end_condition; @@ -244,9 +251,9 @@ struct select_count_context { * Used by doit_select_delete */ struct select_delete_context { + struct select_common common; Process *p; DbTableCommon *tb; - TreeDbTerm **root; DbTreeStack *stack; Uint accum; Binary *mp; @@ -261,9 +268,9 @@ struct select_delete_context { * Used by doit_select_replace */ struct select_replace_context { + struct select_common common; Process *p; DbTableCommon *tb; - TreeDbTerm **root; Binary *mp; Eterm end_condition; Eterm *lastobj; @@ -298,64 +305,62 @@ static TreeDbTerm *find_next(DbTableCommon *tb, TreeDbTerm *root, DbTreeStack* stack, Eterm key); static TreeDbTerm *find_prev(DbTableCommon *tb, TreeDbTerm *root, DbTreeStack* stack, Eterm key); -static TreeDbTerm *find_next_from_pb_key(DbTableCommon *tb, TreeDbTerm *root, - DbTreeStack* stack, Eterm key); -static TreeDbTerm *find_prev_from_pb_key(DbTableCommon *tb, TreeDbTerm *root, - DbTreeStack* stack, Eterm key); +static TreeDbTerm *find_next_from_pb_key(DbTable*, TreeDbTerm*** rootpp, + DbTreeStack* stack, Eterm key, + CATreeRootIterator*); +static TreeDbTerm *find_prev_from_pb_key(DbTable*, TreeDbTerm*** rootpp, + DbTreeStack* stack, Eterm key, + CATreeRootIterator*); +typedef int traverse_doit_funcT(DbTableCommon*, TreeDbTerm*, + struct select_common*, int forward); + static void traverse_backwards(DbTableCommon *tb, - TreeDbTerm **root, DbTreeStack*, Eterm lastkey, - int (*doit)(DbTableCommon *, - TreeDbTerm *, - void *, - int), - void *context); + traverse_doit_funcT*, + struct select_common *context, + CATreeRootIterator*); static void traverse_forward(DbTableCommon *tb, - TreeDbTerm **root, DbTreeStack*, Eterm lastkey, - int (*doit)(DbTableCommon *tb, - TreeDbTerm *, - void *, - int), - void *context); + traverse_doit_funcT*, + struct select_common *context, + CATreeRootIterator*); static void traverse_update_backwards(DbTableCommon *tb, - TreeDbTerm **root, DbTreeStack*, Eterm lastkey, int (*doit)(DbTableCommon *tb, TreeDbTerm **, // out - void *, + struct select_common*, int), - void *context); + struct select_common*, + CATreeRootIterator*); static enum ms_key_boundness key_boundness(DbTableCommon *tb, Eterm pattern, Eterm *keyp); -static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key); static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done); static int analyze_pattern(DbTableCommon *tb, Eterm pattern, extra_match_validator_t extra_validator, /* Optional callback */ struct mp_info *mpi); static int doit_select(DbTableCommon *tb, - TreeDbTerm *this, - void *ptr, + TreeDbTerm *this, + struct select_common* ptr, int forward); static int doit_select_count(DbTableCommon *tb, TreeDbTerm *this, - void *ptr, + struct select_common*, int forward); static int doit_select_chunk(DbTableCommon *tb, TreeDbTerm *this, - void *ptr, + struct select_common*, int forward); static int doit_select_delete(DbTableCommon *tb, TreeDbTerm *this, - void *ptr, + struct select_common*, int forward); static int doit_select_replace(DbTableCommon *tb, TreeDbTerm **this_ptr, - void *ptr, + struct select_common*, int forward); static int partly_bound_can_match_lesser(Eterm partly_bound_1, @@ -987,10 +992,10 @@ static BIF_RETTYPE bif_trap3(Export *bif, int db_select_continue_tree_common(Process *p, DbTableCommon *tb, - TreeDbTerm **root, Eterm continuation, Eterm *ret, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator* iter) { DbTreeStack* stack; struct select_context sc; @@ -1004,7 +1009,6 @@ int db_select_continue_tree_common(Process *p, Sint chunk_size; Sint reverse; - #define RET_TO_BIF(Term, State) do { *ret = (Term); return State; } while(0); /* Decode continuation. We know it's a tuple but not the arity or @@ -1038,23 +1042,32 @@ int db_select_continue_tree_common(Process *p, reverse = unsigned_val(tptr[7]); sc.got = signed_val(tptr[8]); - stack = get_any_stack((DbTable*)tb, stack_container); - if (chunk_size) { - if (reverse) { - traverse_backwards(tb, root, stack, lastkey, &doit_select_chunk, &sc); - } else { - traverse_forward(tb, root, stack, lastkey, &doit_select_chunk, &sc); - } - } else { - if (reverse) { - traverse_forward(tb, root, stack, lastkey, &doit_select, &sc); - } else { - traverse_backwards(tb, root, stack, lastkey, &doit_select, &sc); - } + if (iter) { + iter->next_route_key = lastkey; + sc.common.root = catree_find_nextprev_root(iter, !!reverse != !!chunk_size); } - release_stack((DbTable*)tb,stack_container,stack); + else + sc.common.root = &((DbTableTree*)tb)->root; + + if (sc.common.root) { + stack = get_any_stack((DbTable*)tb, stack_container); + if (chunk_size) { + if (reverse) { + traverse_backwards(tb, stack, lastkey, &doit_select_chunk, &sc.common, iter); + } else { + traverse_forward(tb, stack, lastkey, &doit_select_chunk, &sc.common, iter); + } + } else { + if (reverse) { + traverse_forward(tb, stack, lastkey, &doit_select, &sc.common, iter); + } else { + traverse_backwards(tb, stack, lastkey, &doit_select, &sc.common, iter); + } + } + release_stack((DbTable*)tb,stack_container,stack); - BUMP_REDS(p, 1000 - sc.max); + BUMP_REDS(p, 1000 - sc.max); + } if (sc.max > 0 || (chunk_size && sc.got == chunk_size)) { if (chunk_size) { @@ -1148,13 +1161,14 @@ static int db_select_continue_tree(Process *p, Eterm *ret) { DbTableTree *tb = &tbl->tree; - return db_select_continue_tree_common(p, &tb->common, &tb->root, - continuation, ret, tb); + return db_select_continue_tree_common(p, &tb->common, + continuation, ret, tb, NULL); } -int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, +int db_select_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, int reverse, Eterm *ret, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator* iter) { /* Strategy: Traverse backwards to build resulting list from tail to head */ DbTreeStack* stack; @@ -1185,11 +1199,11 @@ int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, sc.p = p; sc.max = 1000; sc.end_condition = NIL; - sc.keypos = tb->keypos; + sc.keypos = tb->common.keypos; sc.got = 0; sc.chunk_size = 0; - if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(&tb->common, pattern, NULL, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(NIL,errcode); } @@ -1202,29 +1216,47 @@ int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, if (mpi.key_boundness == MS_KEY_BOUND) { ASSERT(CMP_EQ(mpi.least, mpi.most)); - this = find_node(tb, *root, mpi.least, NULL); + if (iter) + sc.common.root = catree_find_root(mpi.least, iter); + else + sc.common.root = &tb->tree.root; + this = find_node(&tb->common, *sc.common.root, mpi.least, NULL); if (this) - doit_select(tb, this, &sc, 0 /* direction doesn't matter */); + doit_select(&tb->common, this, &sc.common, 0 /* direction doesn't matter */); RET_TO_BIF(sc.accum,DB_ERROR_NONE); } stack = get_any_stack((DbTable*)tb,stack_container); if (reverse) { if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { - if ((this = find_prev_from_pb_key(tb, *root, stack, mpi.least)) != NULL) { + this = find_prev_from_pb_key(tb, &sc.common.root, stack, mpi.least, iter); + if (this) lastkey = GETKEY(tb, this->dbterm.tpl); - } sc.end_condition = mpi.most; } - traverse_forward(tb, root, stack, lastkey, &doit_select, &sc); + else { + ASSERT(mpi.key_boundness == MS_KEY_UNBOUND); + if (iter) + sc.common.root = catree_find_first_root(iter); + else + sc.common.root = &tb->tree.root; + } + traverse_forward(&tb->common, stack, lastkey, &doit_select, &sc.common, iter); } else { if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { - if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) { - lastkey = GETKEY(tb, this->dbterm.tpl); - } + this = find_next_from_pb_key(tb, &sc.common.root, stack, mpi.most, iter); + if (this) + lastkey = GETKEY(tb, this->dbterm.tpl); sc.end_condition = mpi.least; } - traverse_backwards(tb, root, stack, lastkey, &doit_select, &sc); + else { + ASSERT(mpi.key_boundness == MS_KEY_UNBOUND); + if (iter) + sc.common.root = catree_find_last_root(iter); + else + sc.common.root = &tb->tree.root; + } + traverse_backwards(&tb->common, stack, lastkey, &doit_select, &sc.common, iter); } release_stack((DbTable*)tb,stack_container,stack); #ifdef HARDDEBUG @@ -1265,17 +1297,16 @@ int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, static int db_select_tree(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, int reverse, Eterm *ret) { - DbTableTree *tb = &tbl->tree; - return db_select_tree_common(p, &tb->common, &tb->root, tid, - pattern, reverse, ret, tb); + return db_select_tree_common(p, tbl, tid, + pattern, reverse, ret, &tbl->tree, NULL); } int db_select_count_continue_tree_common(Process *p, - DbTableCommon *tb, - TreeDbTerm **root, + DbTable *tb, Eterm continuation, Eterm *ret, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator* iter) { DbTreeStack* stack; struct select_count_context sc; @@ -1288,7 +1319,6 @@ int db_select_count_continue_tree_common(Process *p, Eterm *tptr; Eterm egot; - #define RET_TO_BIF(Term, State) do { *ret = (Term); return State; } while(0); /* Decode continuation. We know it's a tuple and everything else as @@ -1313,18 +1343,28 @@ int db_select_count_continue_tree_common(Process *p, sc.end_condition = NIL; sc.lastobj = NULL; sc.max = 1000; - sc.keypos = tb->keypos; + sc.keypos = tb->common.keypos; if (is_big(tptr[5])) { sc.got = big_to_uint32(tptr[5]); } else { sc.got = unsigned_val(tptr[5]); } - stack = get_any_stack((DbTable*)tb, stack_container); - traverse_backwards(tb, root, stack, lastkey, &doit_select_count, &sc); - release_stack((DbTable*)tb,stack_container,stack); + if (iter) { + iter->next_route_key = lastkey; + sc.common.root = catree_find_prev_root(iter); + } + else { + sc.common.root = &tb->tree.root; + } - BUMP_REDS(p, 1000 - sc.max); + if (sc.common.root) { + stack = get_any_stack(tb, stack_container); + traverse_backwards(&tb->common, stack, lastkey, &doit_select_count, &sc.common, iter); + release_stack(tb,stack_container,stack); + + BUMP_REDS(p, 1000 - sc.max); + } if (sc.max > 0) { RET_TO_BIF(erts_make_integer(sc.got,p), DB_ERROR_NONE); @@ -1369,14 +1409,15 @@ static int db_select_count_continue_tree(Process *p, Eterm *ret) { DbTableTree *tb = &tbl->tree; - return db_select_count_continue_tree_common(p, &tb->common, &tb->root, - continuation, ret, tb); + return db_select_count_continue_tree_common(p, tbl, + continuation, ret, tb, NULL); } -int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, +int db_select_count_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, Eterm *ret, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator* iter) { DbTreeStack* stack; struct select_count_context sc; @@ -1391,7 +1432,6 @@ int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root Eterm egot; Eterm mpb; - #define RET_TO_BIF(Term,RetVal) do { \ if (mpi.mp != NULL) { \ erts_bin_free(mpi.mp); \ @@ -1406,10 +1446,10 @@ int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root sc.p = p; sc.max = 1000; sc.end_condition = NIL; - sc.keypos = tb->keypos; + sc.keypos = tb->common.keypos; sc.got = 0; - if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(&tb->common, pattern, NULL, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(NIL,errcode); } @@ -1422,21 +1462,32 @@ int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root if (mpi.key_boundness == MS_KEY_BOUND) { ASSERT(CMP_EQ(mpi.least, mpi.most)); - this = find_node(tb, *root, mpi.least, NULL); + if (iter) + sc.common.root = catree_find_root(mpi.least, iter); + else + sc.common.root = &((DbTable*)tb)->tree.root; + this = find_node(&tb->common, *sc.common.root, mpi.least, NULL); if (this) - doit_select_count(tb, this, &sc, 0 /* dummy */); + doit_select_count(&tb->common, this, &sc.common, 0 /* dummy */); RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE); } stack = get_any_stack((DbTable*)tb, stack_container); if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { - if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) { - lastkey = GETKEY(tb, this->dbterm.tpl); - } + this = find_next_from_pb_key(tb, &sc.common.root, stack, mpi.most, iter); + if (this) + lastkey = GETKEY(tb, this->dbterm.tpl); sc.end_condition = mpi.least; } + else { + ASSERT(mpi.key_boundness == MS_KEY_UNBOUND); + if (iter) + sc.common.root = catree_find_last_root(iter); + else + sc.common.root = &tb->tree.root; + } - traverse_backwards(tb, root, stack, lastkey, &doit_select_count, &sc); + traverse_backwards(&tb->common, stack, lastkey, &doit_select_count, &sc.common, iter); release_stack((DbTable*)tb,stack_container,stack); BUMP_REDS(p, 1000 - sc.max); if (sc.max > 0) { @@ -1477,15 +1528,16 @@ static int db_select_count_tree(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, Eterm *ret) { DbTableTree *tb = &tbl->tree; - return db_select_count_tree_common(p, &tb->common, &tb->root, - tid, pattern, ret, tb); + return db_select_count_tree_common(p, tbl, + tid, pattern, ret, tb, NULL); } -int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, +int db_select_chunk_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, Sint chunk_size, int reverse, Eterm *ret, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator* iter) { DbTreeStack* stack; struct select_context sc; @@ -1499,7 +1551,6 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root int errcode; Eterm mpb; - #define RET_TO_BIF(Term,RetVal) do { \ if (mpi.mp != NULL) { \ erts_bin_free(mpi.mp); \ @@ -1515,11 +1566,11 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root sc.p = p; sc.max = 1000; sc.end_condition = NIL; - sc.keypos = tb->keypos; + sc.keypos = tb->common.keypos; sc.got = 0; sc.chunk_size = chunk_size; - if ((errcode = analyze_pattern(tb, pattern, NULL, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(&tb->common, pattern, NULL, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(NIL,errcode); } @@ -1532,9 +1583,13 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root if (mpi.key_boundness == MS_KEY_BOUND) { ASSERT(CMP_EQ(mpi.least, mpi.most)); - this = find_node(tb, *root, mpi.least, NULL); + if (iter) + sc.common.root = catree_find_root(mpi.least, iter); + else + sc.common.root = &tb->tree.root; + this = find_node(&tb->common, *sc.common.root, mpi.least, NULL); if (this) - doit_select(tb, this, &sc, 0 /* direction doesn't matter */); + doit_select(&tb->common, this, &sc.common, 0 /* direction doesn't matter */); if (sc.accum != NIL) { hp=HAlloc(p, 3); RET_TO_BIF(TUPLE2(hp,sc.accum,am_EOT),DB_ERROR_NONE); @@ -1546,20 +1601,34 @@ int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root stack = get_any_stack((DbTable*)tb,stack_container); if (reverse) { if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { - if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) { - lastkey = GETKEY(tb, this->dbterm.tpl); - } + this = find_next_from_pb_key(tb, &sc.common.root, stack, mpi.most, iter); + if (this) + lastkey = GETKEY(tb, this->dbterm.tpl); sc.end_condition = mpi.least; } - traverse_backwards(tb, root, stack, lastkey, &doit_select_chunk, &sc); + else { + ASSERT(mpi.key_boundness == MS_KEY_UNBOUND); + if (iter) + sc.common.root = catree_find_last_root(iter); + else + sc.common.root = &tb->tree.root; + } + traverse_backwards(&tb->common, stack, lastkey, &doit_select_chunk, &sc.common, iter); } else { if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { - if ((this = find_prev_from_pb_key(tb, *root, stack, mpi.least)) != NULL) { - lastkey = GETKEY(tb, this->dbterm.tpl); - } + this = find_prev_from_pb_key(tb, &sc.common.root, stack, mpi.least, iter); + if (this) + lastkey = GETKEY(tb, this->dbterm.tpl); sc.end_condition = mpi.most; } - traverse_forward(tb, root, stack, lastkey, &doit_select_chunk, &sc); + else { + ASSERT(mpi.key_boundness == MS_KEY_UNBOUND); + if (iter) + sc.common.root = catree_find_first_root(iter); + else + sc.common.root = &tb->tree.root; + } + traverse_forward(&tb->common, stack, lastkey, &doit_select_chunk, &sc.common, iter); } release_stack((DbTable*)tb,stack_container,stack); @@ -1636,18 +1705,18 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl, Eterm tid, Eterm *ret) { DbTableTree *tb = &tbl->tree; - return db_select_chunk_tree_common(p, &tb->common, &tb->root, + return db_select_chunk_tree_common(p, tbl, tid, pattern, chunk_size, - reverse, ret, tb); + reverse, ret, tb, NULL); } int db_select_delete_continue_tree_common(Process *p, DbTable *tbl, - TreeDbTerm **root, Eterm continuation, Eterm *ret, - DbTreeStack* stack) + DbTreeStack* stack, + CATreeRootIterator* iter) { struct select_delete_context sc; unsigned sz; @@ -1659,7 +1728,6 @@ int db_select_delete_continue_tree_common(Process *p, Eterm *tptr; Eterm eaccsum; - #define RET_TO_BIF(Term, State) do { \ if (sc.erase_lastterm) { \ free_term(tbl, sc.lastterm); \ @@ -1682,7 +1750,6 @@ int db_select_delete_continue_tree_common(Process *p, mp = erts_db_get_match_prog_binary_unchecked(tptr[4]); sc.p = p; sc.tb = &tbl->common; - sc.root = root; sc.stack = stack; if (is_big(tptr[5])) { sc.accum = big_to_uint32(tptr[5]); @@ -1694,9 +1761,19 @@ int db_select_delete_continue_tree_common(Process *p, sc.max = 1000; sc.keypos = tbl->common.keypos; - traverse_backwards(&tbl->common, root, stack, lastkey, &doit_select_delete, &sc); + if (iter) { + iter->next_route_key = lastkey; + sc.common.root = catree_find_prev_root(iter); + } + else { + sc.common.root = &tbl->tree.root; + } - BUMP_REDS(p, 1000 - sc.max); + if (sc.common.root) { + traverse_backwards(&tbl->common, stack, lastkey, &doit_select_delete, &sc.common, iter); + + BUMP_REDS(p, 1000 - sc.max); + } if (sc.max > 0) { RET_TO_BIF(erts_make_integer(sc.accum, p), DB_ERROR_NONE); @@ -1738,16 +1815,15 @@ static int db_select_delete_continue_tree(Process *p, { DbTableTree *tb = &tbl->tree; ASSERT(!erts_atomic_read_nob(&tb->is_stack_busy)); - return db_select_delete_continue_tree_common(p, tbl, &tb->root, - continuation, ret, - &tb->static_stack); + return db_select_delete_continue_tree_common(p, tbl, continuation, ret, + &tb->static_stack, NULL); } int db_select_delete_tree_common(Process *p, DbTable *tbl, - TreeDbTerm **root, Eterm tid, Eterm pattern, Eterm *ret, - DbTreeStack* stack) + DbTreeStack* stack, + CATreeRootIterator* iter) { struct select_delete_context sc; struct mp_info mpi; @@ -1782,7 +1858,6 @@ int db_select_delete_tree_common(Process *p, DbTable *tbl, sc.end_condition = NIL; sc.keypos = tbl->common.keypos; sc.tb = &tbl->common; - sc.root = root; sc.stack = stack; if ((errcode = analyze_pattern(&tbl->common, pattern, NULL, &mpi)) != DB_ERROR_NONE) { @@ -1798,21 +1873,33 @@ int db_select_delete_tree_common(Process *p, DbTable *tbl, if (mpi.key_boundness == MS_KEY_BOUND) { ASSERT(CMP_EQ(mpi.least, mpi.most)); - this = find_node(&tbl->common, *root, mpi.least, NULL); + if (iter) + sc.common.root = catree_find_root(mpi.least, iter); + else + sc.common.root = &tbl->tree.root; + this = find_node(&tbl->common, *sc.common.root, mpi.least, NULL); if (this) - doit_select_delete(&tbl->common, this, &sc, 0 /* direction doesn't + doit_select_delete(&tbl->common, this, &sc.common, 0 /* direction doesn't matter */); RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE); } if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { - if ((this = find_next_from_pb_key(&tbl->common, *root, stack, mpi.most)) != NULL) { - lastkey = GETKEY(&tbl->common, this->dbterm.tpl); - } + this = find_next_from_pb_key(tbl, &sc.common.root, stack, mpi.most, iter); + if (this) + lastkey = GETKEY(&tbl->common, this->dbterm.tpl); sc.end_condition = mpi.least; } + else { + ASSERT(mpi.key_boundness == MS_KEY_UNBOUND); + if (iter) + sc.common.root = catree_find_last_root(iter); + else + sc.common.root = &tbl->tree.root; + } - traverse_backwards(&tbl->common, root, stack, lastkey, &doit_select_delete, &sc); + traverse_backwards(&tbl->common, stack, lastkey, + &doit_select_delete, &sc.common, iter); BUMP_REDS(p, 1000 - sc.max); if (sc.max > 0) { @@ -1856,16 +1943,16 @@ static int db_select_delete_tree(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, Eterm *ret) { DbTableTree *tb = &tbl->tree; - return db_select_delete_tree_common(p, tbl, &tb->root, tid, pattern, ret, - &tb->static_stack); + return db_select_delete_tree_common(p, tbl, tid, pattern, ret, + &tb->static_stack, NULL); } int db_select_replace_continue_tree_common(Process *p, - DbTableCommon *tb, - TreeDbTerm **root, + DbTable *tbl, Eterm continuation, Eterm *ret, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator* iter) { DbTreeStack* stack; struct select_replace_context sc; @@ -1902,7 +1989,7 @@ int db_select_replace_continue_tree_common(Process *p, sc.end_condition = NIL; sc.lastobj = NULL; sc.max = 1000; - sc.keypos = tb->keypos; + sc.keypos = tbl->common.keypos; if (is_big(tptr[5])) { sc.replaced = big_to_uint32(tptr[5]); } else { @@ -1910,9 +1997,18 @@ int db_select_replace_continue_tree_common(Process *p, } prev_replaced = sc.replaced; - stack = get_any_stack((DbTable*)tb,stack_container); - traverse_update_backwards(tb, root, stack, lastkey, &doit_select_replace, &sc); - release_stack((DbTable*)tb,stack_container,stack); + if (iter) { + iter->next_route_key = lastkey; + sc.common.root = catree_find_prev_root(iter); + } + else { + sc.common.root = &tbl->tree.root; + } + + stack = get_any_stack(tbl, stack_container); + traverse_update_backwards(&tbl->common, stack, lastkey, &doit_select_replace, + &sc.common, iter); + release_stack(tbl, stack_container,stack); // the more objects we've replaced, the more reductions we've consumed BUMP_REDS(p, MIN(2000, (1000 - sc.max) + (sc.replaced - prev_replaced))); @@ -1920,7 +2016,7 @@ int db_select_replace_continue_tree_common(Process *p, if (sc.max > 0) { RET_TO_BIF(erts_make_integer(sc.replaced,p), DB_ERROR_NONE); } - key = GETKEY(tb, sc.lastobj); + key = GETKEY(tbl, sc.lastobj); if (end_condition != NIL && (cmp_partly_bound(end_condition,key) > 0)) { /* done anyway */ @@ -1956,14 +2052,14 @@ static int db_select_replace_continue_tree(Process *p, Eterm continuation, Eterm *ret) { - DbTableTree *tb = &tbl->tree; - return db_select_replace_continue_tree_common(p, &tb->common, &tb->root, - continuation, ret, tb); + return db_select_replace_continue_tree_common(p, tbl, continuation, ret, + &tbl->tree, NULL); } -int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, +int db_select_replace_tree_common(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, Eterm *ret, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator* iter) { DbTreeStack* stack; struct select_replace_context sc; @@ -1991,14 +2087,13 @@ int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **ro sc.lastobj = NULL; sc.p = p; - sc.tb = tb; - sc.root = root; + sc.tb = &tbl->common; sc.max = 1000; sc.end_condition = NIL; - sc.keypos = tb->keypos; + sc.keypos = tbl->common.keypos; sc.replaced = 0; - if ((errcode = analyze_pattern(tb, pattern, db_match_keeps_key, &mpi)) != DB_ERROR_NONE) { + if ((errcode = analyze_pattern(&tbl->common, pattern, db_match_keeps_key, &mpi)) != DB_ERROR_NONE) { RET_TO_BIF(NIL,errcode); } @@ -2012,32 +2107,44 @@ int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **ro if (mpi.key_boundness == MS_KEY_BOUND) { TreeDbTerm** pp; ASSERT(CMP_EQ(mpi.least, mpi.most)); - pp = find_node2(tb, root, mpi.least); + if (iter) + sc.common.root = catree_find_root(mpi.least, iter); + else + sc.common.root = &tbl->tree.root; + pp = find_node2(&tbl->common, sc.common.root, mpi.least); if (pp) { - doit_select_replace(tb, pp, &sc, 0 /* dummy */); + doit_select_replace(&tbl->common, pp, &sc.common, 0 /* dummy */); reset_static_stack(stack_container); /* may refer replaced term */ } RET_TO_BIF(erts_make_integer(sc.replaced,p),DB_ERROR_NONE); } - stack = get_any_stack((DbTable*)tb,stack_container); + stack = get_any_stack(tbl,stack_container); if (mpi.key_boundness == MS_KEY_PARTIALLY_BOUND) { - if ((this = find_next_from_pb_key(tb, *root, stack, mpi.most)) != NULL) { - lastkey = GETKEY(tb, this->dbterm.tpl); - } + this = find_next_from_pb_key(tbl, &sc.common.root, stack, mpi.most, iter); + if (this) + lastkey = GETKEY(tbl, this->dbterm.tpl); sc.end_condition = mpi.least; } + else { + ASSERT(mpi.key_boundness == MS_KEY_UNBOUND); + if (iter) + sc.common.root = catree_find_last_root(iter); + else + sc.common.root = &tbl->tree.root; + } - traverse_update_backwards(tb, root, stack, lastkey, &doit_select_replace, &sc); - release_stack((DbTable*)tb,stack_container,stack); + traverse_update_backwards(&tbl->common, stack, lastkey, &doit_select_replace, + &sc.common, iter); + release_stack(tbl,stack_container,stack); // the more objects we've replaced, the more reductions we've consumed BUMP_REDS(p, MIN(2000, (1000 - sc.max) + sc.replaced)); if (sc.max > 0) { RET_TO_BIF(erts_make_integer(sc.replaced,p),DB_ERROR_NONE); } - key = GETKEY(tb, sc.lastobj); + key = GETKEY(tbl, sc.lastobj); sz = size_object(key); if (IS_USMALL(0, sc.replaced)) { hp = HAlloc(p, sz + ERTS_MAGIC_REF_THING_SIZE + 6); @@ -2070,9 +2177,8 @@ int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **ro static int db_select_replace_tree(Process *p, DbTable *tbl, Eterm tid, Eterm pattern, Eterm *ret) { - DbTableTree *tb = &tbl->tree; - return db_select_replace_tree_common(p, &tb->common, &tb->root, - tid, pattern, ret, tb); + return db_select_replace_tree_common(p, tbl, tid, pattern, ret, + &tbl->tree, NULL); } int db_take_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root, @@ -2809,20 +2915,32 @@ static TreeDbTerm *find_prev(DbTableCommon *tb, TreeDbTerm *root, return this; } -static TreeDbTerm *find_next_from_pb_key(DbTableCommon *tb, TreeDbTerm *root, - DbTreeStack* stack, Eterm key) + +static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, + DbTreeStack* stack, Eterm key, + CATreeRootIterator* iter) { + TreeDbTerm* root; TreeDbTerm *this; TreeDbTerm *tmp; Sint c; + if (iter) { + *rootpp = catree_find_next_from_pb_key_root(key, iter); + root = *rootpp ? **rootpp : NULL; + } + else { + *rootpp = &tbl->tree.root; + root = tbl->tree.root; + } + /* spool the stack, we have to "re-search" */ stack->pos = stack->slot = 0; if (( this = root ) == NULL) return NULL; for (;;) { PUSH_NODE(stack, this); - if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl))) >= 0) { + if (( c = cmp_partly_bound(key,GETKEY(tbl, this->dbterm.tpl))) >= 0) { if (this->right == NULL) { do { tmp = POP_NODE(stack); @@ -2842,20 +2960,31 @@ static TreeDbTerm *find_next_from_pb_key(DbTableCommon *tb, TreeDbTerm *root, } } -static TreeDbTerm *find_prev_from_pb_key(DbTableCommon *tb, TreeDbTerm *root, - DbTreeStack* stack, Eterm key) +static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, + DbTreeStack* stack, Eterm key, + CATreeRootIterator* iter) { + TreeDbTerm* root; TreeDbTerm *this; TreeDbTerm *tmp; Sint c; + if (iter) { + *rootpp = catree_find_prev_from_pb_key_root(key, iter); + root = *rootpp ? **rootpp : NULL; + } + else { + *rootpp = &tbl->tree.root; + root = tbl->tree.root; + } + /* spool the stack, we have to "re-search" */ stack->pos = stack->slot = 0; if (( this = root ) == NULL) return NULL; for (;;) { PUSH_NODE(stack, this); - if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl))) <= 0) { + if (( c = cmp_partly_bound(key,GETKEY(tbl, this->dbterm.tpl))) <= 0) { if (this->left == NULL) { do { tmp = POP_NODE(stack); @@ -2866,7 +2995,7 @@ static TreeDbTerm *find_prev_from_pb_key(DbTableCommon *tb, TreeDbTerm *root, return this; } else this = this->left; - } else /*if (c < 0)*/ { + } else /*if (c > 0)*/ { if (this->right == NULL) /* Done */ return this; else @@ -3059,126 +3188,147 @@ db_finalize_dbterm_tree(int cret, DbUpdateHandle *handle) * Traverse the tree with a callback function, used by db_match_xxx */ static void traverse_backwards(DbTableCommon *tb, - TreeDbTerm **root, DbTreeStack* stack, Eterm lastkey, - int (*doit)(DbTableCommon *, - TreeDbTerm *, - void *, - int), - void *context) + traverse_doit_funcT* doit, + struct select_common *context, + CATreeRootIterator* iter) { TreeDbTerm *this, *next; + TreeDbTerm** root = context->root; - if (lastkey == THE_NON_VALUE) { - stack->pos = stack->slot = 0; - if (( this = *root ) == NULL) { - return; - } - while (this != NULL) { - PUSH_NODE(stack, this); - this = this->right; - } - this = TOP_NODE(stack); - next = find_prev(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); - if (!((*doit)(tb, this, context, 0))) - return; - } else { - next = find_prev(tb, *root, stack, lastkey); - } + do { + if (lastkey == THE_NON_VALUE) { + stack->pos = stack->slot = 0; + if (( this = *root ) == NULL) { + goto next_root; + } + while (this != NULL) { + PUSH_NODE(stack, this); + this = this->right; + } + this = TOP_NODE(stack); + next = find_prev(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); + if (!((*doit)(tb, this, context, 0))) + return; + } else { + next = find_prev(tb, *root, stack, lastkey); + } - while ((this = next) != NULL) { - next = find_prev(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); - if (!((*doit)(tb, this, context, 0))) - return; - } + while ((this = next) != NULL) { + next = find_prev(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); + if (!((*doit)(tb, this, context, 0))) + return; + } + +next_root: + if (!iter) + return; + root = context->root = catree_find_prev_root(iter); + lastkey = THE_NON_VALUE; + } while (root); } /* * Traverse the tree with a callback function, used by db_match_xxx */ static void traverse_forward(DbTableCommon *tb, - TreeDbTerm **root, DbTreeStack* stack, Eterm lastkey, - int (*doit)(DbTableCommon *, - TreeDbTerm *, - void *, - int), - void *context) + traverse_doit_funcT* doit, + struct select_common *context, + CATreeRootIterator* iter) { TreeDbTerm *this, *next; + TreeDbTerm **root = context->root; - if (lastkey == THE_NON_VALUE) { - stack->pos = stack->slot = 0; - if (( this = *root ) == NULL) { - return; - } - while (this != NULL) { - PUSH_NODE(stack, this); - this = this->left; - } - this = TOP_NODE(stack); - next = find_next(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); - if (!((*doit)(tb, this, context, 1))) - return; - } else { - next = find_next(tb, *root, stack, lastkey); - } + do { + if (lastkey == THE_NON_VALUE) { + stack->pos = stack->slot = 0; + if (( this = *root ) == NULL) { + goto next_root; + } + while (this != NULL) { + PUSH_NODE(stack, this); + this = this->left; + } + this = TOP_NODE(stack); + next = find_next(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); + if (!((*doit)(tb, this, context, 1))) + return; + } else { + next = find_next(tb, *root, stack, lastkey); + } - while ((this = next) != NULL) { - next = find_next(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); - if (!((*doit)(tb, this, context, 1))) - return; - } + while ((this = next) != NULL) { + next = find_next(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); + if (!((*doit)(tb, this, context, 1))) + return; + } + +next_root: + if (!iter) + return; + root = context->root = catree_find_next_root(iter); + lastkey = THE_NON_VALUE; + } while(root); } /* * Traverse the tree with an update callback function, used by db_select_replace */ static void traverse_update_backwards(DbTableCommon *tb, - TreeDbTerm **root, DbTreeStack* stack, Eterm lastkey, int (*doit)(DbTableCommon*, TreeDbTerm**, - void*, + struct select_common*, int), - void* context) + struct select_common* context, + CATreeRootIterator* iter) { int res; TreeDbTerm *this, *next, **this_ptr; + TreeDbTerm** root = context->root; - if (lastkey == THE_NON_VALUE) { - stack->pos = stack->slot = 0; - if (( this = *root ) == NULL) { - return; + do { + if (lastkey == THE_NON_VALUE) { + stack->pos = stack->slot = 0; + if (( this = *root ) == NULL) { + goto next_root; + } + while (this != NULL) { + PUSH_NODE(stack, this); + this = this->right; + } + this = TOP_NODE(stack); + this_ptr = find_ptr(tb, root, stack, this); + ASSERT(this_ptr != NULL); + res = (*doit)(tb, this_ptr, context, 0); + REPLACE_TOP_NODE(stack, *this_ptr); + next = find_prev(tb, *root, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl)); + if (!res) + return; + } else { + next = find_prev(tb, *root, stack, lastkey); } - while (this != NULL) { - PUSH_NODE(stack, this); - this = this->right; + + while ((this = next) != NULL) { + this_ptr = find_ptr(tb, root, stack, this); + ASSERT(this_ptr != NULL); + res = (*doit)(tb, this_ptr, context, 0); + REPLACE_TOP_NODE(stack, *this_ptr); + next = find_prev(tb, *root, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl)); + if (!res) + return; } - this = TOP_NODE(stack); - this_ptr = find_ptr(tb, root, stack, this); - ASSERT(this_ptr != NULL); - res = (*doit)(tb, this_ptr, context, 0); - REPLACE_TOP_NODE(stack, *this_ptr); - next = find_prev(tb, *root, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl)); - if (!res) - return; - } else { - next = find_prev(tb, *root, stack, lastkey); - } - while ((this = next) != NULL) { - this_ptr = find_ptr(tb, root, stack, this); - ASSERT(this_ptr != NULL); - res = (*doit)(tb, this_ptr, context, 0); - REPLACE_TOP_NODE(stack, *this_ptr); - next = find_prev(tb, *root, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl)); - if (!res) +next_root: + if (!iter) return; - } + root = context->root = catree_find_prev_root(iter); + lastkey = THE_NON_VALUE; + } while (root); } static enum ms_key_boundness key_boundness(DbTableCommon *tb, @@ -3269,7 +3419,8 @@ static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done) } } -static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key) { +Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key) +{ int done = 0; Sint ret = do_cmp_partly_bound(partly_bound_key, bound_key, &done); #ifdef HARDDEBUG @@ -3485,7 +3636,8 @@ static int do_partly_bound_can_match_greater(Eterm a, Eterm b, * Callback functions for the different match functions */ -static int doit_select(DbTableCommon *tb, TreeDbTerm *this, void *ptr, +static int doit_select(DbTableCommon *tb, TreeDbTerm *this, + struct select_common* ptr, int forward) { struct select_context *sc = (struct select_context *) ptr; @@ -3520,7 +3672,8 @@ static int doit_select(DbTableCommon *tb, TreeDbTerm *this, void *ptr, return 1; } -static int doit_select_count(DbTableCommon *tb, TreeDbTerm *this, void *ptr, +static int doit_select_count(DbTableCommon *tb, TreeDbTerm *this, + struct select_common* ptr, int forward) { struct select_count_context *sc = (struct select_count_context *) ptr; @@ -3544,7 +3697,8 @@ static int doit_select_count(DbTableCommon *tb, TreeDbTerm *this, void *ptr, return 1; } -static int doit_select_chunk(DbTableCommon *tb, TreeDbTerm *this, void *ptr, +static int doit_select_chunk(DbTableCommon *tb, TreeDbTerm *this, + struct select_common* ptr, int forward) { struct select_context *sc = (struct select_context *) ptr; @@ -3582,7 +3736,8 @@ static int doit_select_chunk(DbTableCommon *tb, TreeDbTerm *this, void *ptr, } -static int doit_select_delete(DbTableCommon *tb, TreeDbTerm *this, void *ptr, +static int doit_select_delete(DbTableCommon *tb, TreeDbTerm *this, + struct select_common *ptr, int forward) { struct select_delete_context *sc = (struct select_delete_context *) ptr; @@ -3601,7 +3756,7 @@ static int doit_select_delete(DbTableCommon *tb, TreeDbTerm *this, void *ptr, ret = db_match_dbterm(tb, sc->p, sc->mp, &this->dbterm, NULL, 0); if (ret == am_true) { key = GETKEY(sc->tb, this->dbterm.tpl); - linkout_tree(sc->tb, sc->root, key, sc->stack); + linkout_tree(sc->tb, sc->common.root, key, sc->stack); sc->erase_lastterm = 1; ++sc->accum; } @@ -3611,7 +3766,8 @@ static int doit_select_delete(DbTableCommon *tb, TreeDbTerm *this, void *ptr, return 1; } -static int doit_select_replace(DbTableCommon *tb, TreeDbTerm **this, void *ptr, +static int doit_select_replace(DbTableCommon *tb, TreeDbTerm **this, + struct select_common* ptr, int forward) { struct select_replace_context *sc = (struct select_replace_context *) ptr; diff --git a/erts/emulator/beam/erl_db_tree_util.h b/erts/emulator/beam/erl_db_tree_util.h index fbd9a9124a..c816660c71 100644 --- a/erts/emulator/beam/erl_db_tree_util.h +++ b/erts/emulator/beam/erl_db_tree_util.h @@ -93,48 +93,52 @@ int db_erase_object_tree_common(DbTable *tbl, TreeDbTerm **root, Eterm object, int db_slot_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm slot_term, Eterm *ret, DbTableTree *stack_container); -int db_select_chunk_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, +int db_select_chunk_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, Sint chunk_size, int reverse, Eterm *ret, - DbTableTree *stack_container); -int db_select_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, + DbTableTree *stack_container, + CATreeRootIterator*); +int db_select_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, int reverse, Eterm *ret, - DbTableTree *stack_container); + DbTableTree *stack_container, + CATreeRootIterator*); int db_select_delete_tree_common(Process *p, DbTable *tbl, - TreeDbTerm **root, Eterm tid, Eterm pattern, Eterm *ret, - DbTreeStack* stack); + DbTreeStack* stack, + CATreeRootIterator* iter); int db_select_continue_tree_common(Process *p, DbTableCommon *tb, - TreeDbTerm **root, Eterm continuation, Eterm *ret, - DbTableTree *stack_container); + DbTableTree *stack_container, + CATreeRootIterator* iter); int db_select_delete_continue_tree_common(Process *p, DbTable *tbl, - TreeDbTerm **root, Eterm continuation, Eterm *ret, - DbTreeStack* stack); -int db_select_count_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, + DbTreeStack* stack, + CATreeRootIterator* iter); +int db_select_count_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, Eterm *ret, - DbTableTree *stack_container); + DbTableTree *stack_container, + CATreeRootIterator* iter); int db_select_count_continue_tree_common(Process *p, - DbTableCommon *tb, - TreeDbTerm **root, + DbTable *tb, Eterm continuation, Eterm *ret, - DbTableTree *stack_container); -int db_select_replace_tree_common(Process *p, DbTableCommon *tb, TreeDbTerm **root, + DbTableTree *stack_container, + CATreeRootIterator* iter); +int db_select_replace_tree_common(Process *p, DbTable*, Eterm tid, Eterm pattern, Eterm *ret, - DbTableTree *stack_container); + DbTableTree *stack_container, + CATreeRootIterator* iter); int db_select_replace_continue_tree_common(Process *p, - DbTableCommon *tb, - TreeDbTerm **root, + DbTable*, Eterm continuation, Eterm *ret, - DbTableTree *stack_container); + DbTableTree *stack_container, + CATreeRootIterator* iter); int db_take_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root, Eterm key, Eterm *ret, DbTreeStack *stack /* NULL if no static stack */); @@ -148,4 +152,6 @@ int db_lookup_dbterm_tree_common(Process *p, DbTable *tbl, TreeDbTerm **root, DbTableTree *stack_container); void db_finalize_dbterm_tree_common(int cret, DbUpdateHandle *handle, DbTableTree *stack_container); +Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key); + #endif /* _DB_TREE_UTIL_H */ -- cgit v1.2.3 From fd66782f1832966c5ee27bf756f1255bf0102bc9 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 15 Oct 2018 19:17:27 +0200 Subject: erts: Remove tree merging for ets:first,last,next,prev --- erts/emulator/beam/erl_db_catree.c | 135 ++++++++++++++++++------------------- erts/emulator/beam/erl_db_tree.c | 4 +- 2 files changed, 68 insertions(+), 71 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 2c3b262312..62c616e66d 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -1125,34 +1125,6 @@ clone_stack(CATreeNodeStack *search_stack_ptr, } } - - -static ERTS_INLINE DbTableCATreeNode* -lock_first_base_node(DbTable *tbl, - CATreeNodeStack *search_stack_ptr, - CATreeNodeStack *locked_base_nodes_stack_ptr) -{ - DbTableCATreeNode *current_node; - DbTableCATreeBaseNode *base_node; - DbTableCATree* tb = &tbl->catree; - while (1) { - current_node = GET_ROOT_ACQB(tb); - while ( ! current_node->is_base_node ) { - PUSH_NODE(search_stack_ptr, current_node); - current_node = GET_LEFT_ACQB(current_node); - } - base_node = ¤t_node->u.base; - rlock_base_node(base_node); - if (base_node->is_valid) - break; - /* Retry */ - runlock_base_node(base_node); - search_stack_ptr->pos = 0; - } - push_node_dyn_array(tbl, locked_base_nodes_stack_ptr, current_node); - return current_node; -} - static ERTS_INLINE DbTableCATreeBaseNode* find_and_lock_next_base_node_and_path(DbTable *tbl, CATreeNodeStack **search_stack_ptr_ptr, @@ -1748,68 +1720,93 @@ int db_create_catree(Process *p, DbTable *tbl) static int db_first_catree(Process *p, DbTable *tbl, Eterm *ret) { - DbTableCATreeBaseNode *base_node; + TreeDbTerm *root; + CATreeRootIterator iter; int result; - DECLARE_AND_INIT_BASE_NODE_SEARCH_STACKS; - /* Find first base node */ - base_node = &(lock_first_base_node(tbl, &search_stack, &locked_base_nodes_stack)->u.base); - /* Find next base node until non-empty base node is found */ - while (base_node != NULL && base_node->root == NULL) { - base_node = find_and_lock_next_base_node_and_path(tbl, &search_stack_ptr, &search_stack_copy_ptr, locked_base_nodes_stack_ptr); + + init_root_iterator(&tbl->catree, &iter, 1); + root = *catree_find_first_root(&iter); + if (!root) { + TreeDbTerm **pp = catree_find_next_root(&iter); + root = pp ? *pp : NULL; } - /* Get the return value */ - result = db_first_tree_common(p, tbl, (base_node == NULL ? NULL : base_node->root), ret, NULL); - /* Unlock base nodes */ - unlock_and_release_locked_base_node_stack(tbl, locked_base_nodes_stack_ptr); + + result = db_first_tree_common(p, tbl, root, ret, NULL); + + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); return result; } static int db_next_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) { - DbTreeStack next_search_stack; - TreeDbTerm *next_search_stack_array[STACK_NEED]; - DbTableCATreeBaseNode *base_node; - int result = 0; - DECLARE_AND_INIT_BASE_NODE_SEARCH_STACKS; - init_tree_stack(&next_search_stack, next_search_stack_array, 0); - /* Lock base node with key */ - base_node = lock_base_node_with_key(tbl, key, &search_stack, &locked_base_nodes_stack); - /* Continue until key is not >= greatest key in base_node */ - while (base_node != NULL) { - result = db_next_tree_common(p, tbl, base_node->root, key, - ret, &next_search_stack); - if (result != DB_ERROR_NONE || *ret != am_EOT) { + DbTreeStack stack; + TreeDbTerm * stack_array[STACK_NEED]; + TreeDbTerm **rootp; + CATreeRootIterator iter; + int result; + + init_root_iterator(&tbl->catree, &iter, 1); + iter.next_route_key = key; + rootp = catree_find_next_root(&iter); + + do { + init_tree_stack(&stack, stack_array, 0); + result = db_next_tree_common(p, tbl, (rootp ? *rootp : NULL), key, ret, &stack); + if (result != DB_ERROR_NONE || *ret != am_EOT) break; - } - base_node = - find_and_lock_next_base_node_and_path(tbl, - &search_stack_ptr, - &search_stack_copy_ptr, - locked_base_nodes_stack_ptr); - } - unlock_and_release_locked_base_node_stack(tbl, &locked_base_nodes_stack); + + rootp = catree_find_next_root(&iter); + } while (rootp); + + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); return result; } static int db_last_catree(Process *p, DbTable *tbl, Eterm *ret) { - DbTableCATreeNode *base = merge_to_one_locked_base_node(&tbl->catree); - int result = db_last_tree_common(p, tbl, base->u.base.root, ret, NULL); - wunlock_base_node(&(base->u.base)); + TreeDbTerm *root; + CATreeRootIterator iter; + int result; + + init_root_iterator(&tbl->catree, &iter, 1); + root = *catree_find_last_root(&iter); + if (!root) { + TreeDbTerm **pp = catree_find_prev_root(&iter); + root = pp ? *pp : NULL; + } + + result = db_last_tree_common(p, tbl, root, ret, NULL); + + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); return result; - } static int db_prev_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) { DbTreeStack stack; TreeDbTerm * stack_array[STACK_NEED]; + TreeDbTerm **rootp; + CATreeRootIterator iter; int result; - DbTableCATreeNode *base; - init_tree_stack(&stack, stack_array, 0); - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_prev_tree_common(p, tbl, base->u.base.root, key, ret, &stack); - wunlock_base_node(&(base->u.base)); + + init_root_iterator(&tbl->catree, &iter, 1); + iter.next_route_key = key; + rootp = catree_find_prev_root(&iter); + + do { + init_tree_stack(&stack, stack_array, 0); + result = db_prev_tree_common(p, tbl, (rootp ? *rootp : NULL), key, ret, + &stack); + if (result != DB_ERROR_NONE || *ret != am_EOT) + break; + rootp = catree_find_prev_root(&iter); + } while (rootp); + + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); return result; } diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index 71ec6e28e5..35868c318d 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -547,7 +547,7 @@ int db_next_tree_common(Process *p, DbTable *tbl, { TreeDbTerm *this; - if (is_atom(key) && key == am_EOT) + if (key == am_EOT) return DB_ERROR_BADKEY; this = find_next(&tbl->common, root, stack, key); if (this == NULL) { @@ -605,7 +605,7 @@ int db_prev_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm key, { TreeDbTerm *this; - if (is_atom(key) && key == am_EOT) + if (key == am_EOT) return DB_ERROR_BADKEY; this = find_prev(&tbl->common, root, stack, key); if (this == NULL) { -- cgit v1.2.3 From 76f7e5a04e1dc8150ac0f90d983e0d1488e705a5 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 16 Oct 2018 12:19:32 +0200 Subject: erts: Remove tree merging for ets:slot Brute force solution will always iterate tree from slot 0 and forward. ToDo1: Yield. ToDo2: Maybe optimize by caching AVL tree size in each base node. --- erts/emulator/beam/erl_db_catree.c | 12 +-- erts/emulator/beam/erl_db_tree.c | 133 ++++++++++++++++++++-------------- erts/emulator/beam/erl_db_tree_util.h | 3 +- 3 files changed, 88 insertions(+), 60 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 62c616e66d..46441c060b 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -2128,11 +2128,13 @@ static int db_slot_catree(Process *p, DbTable *tbl, Eterm slot_term, Eterm *ret) { int result; - DbTableCATreeNode *base; - base = merge_to_one_locked_base_node(&tbl->catree); - result = db_slot_tree_common(p, tbl, base->u.base.root, - slot_term, ret, NULL); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + + init_root_iterator(&tbl->catree, &iter, 1); + result = db_slot_tree_common(p, tbl, *catree_find_first_root(&iter), + slot_term, ret, NULL, &iter); + if (iter.locked_bnode) + runlock_base_node(iter.locked_bnode); return result; } diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index 35868c318d..a3147e0f68 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -295,7 +295,8 @@ int tree_balance_left(TreeDbTerm **this); int tree_balance_right(TreeDbTerm **this); static int delsub(TreeDbTerm **this); static TreeDbTerm *slot_search(Process *p, TreeDbTerm *root, Sint slot, - DbTable *tb, DbTableTree *stack_container); + DbTable *tb, DbTableTree *stack_container, + CATreeRootIterator *iter); static TreeDbTerm *find_node(DbTableCommon *tb, TreeDbTerm *root, Eterm key, DbTableTree *stack_container); static TreeDbTerm **find_node2(DbTableCommon *tb, TreeDbTerm **root, Eterm key); @@ -873,7 +874,8 @@ static int db_erase_object_tree(DbTable *tbl, Eterm object, Eterm *ret) int db_slot_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm slot_term, Eterm *ret, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator *iter) { Sint slot; TreeDbTerm *st; @@ -903,7 +905,7 @@ int db_slot_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, * are counted from 1 and up. */ ++slot; - st = slot_search(p, root, slot, tbl, stack_container); + st = slot_search(p, root, slot, tbl, stack_container, iter); if (st == NULL) { *ret = am_false; return DB_ERROR_UNSPEC; @@ -921,7 +923,7 @@ static int db_slot_tree(Process *p, DbTable *tbl, Eterm slot_term, Eterm *ret) { DbTableTree *tb = &tbl->tree; - return db_slot_tree_common(p, tbl, tb->root, slot_term, ret, tb); + return db_slot_tree_common(p, tbl, tb->root, slot_term, ret, tb, NULL); } @@ -2727,10 +2729,12 @@ static int delsub(TreeDbTerm **this) static TreeDbTerm *slot_search(Process *p, TreeDbTerm *root, Sint slot, DbTable *tb, - DbTableTree *stack_container) + DbTableTree *stack_container, + CATreeRootIterator *iter) { TreeDbTerm *this; TreeDbTerm *tmp; + TreeDbTerm **pp; DbTreeStack* stack = get_any_stack(tb,stack_container); ASSERT(stack != NULL); @@ -2743,56 +2747,77 @@ static TreeDbTerm *slot_search(Process *p, TreeDbTerm *root, are not recorded */ stack->pos = 0; } - if (EMPTY_NODE(stack)) { - this = root; - if (this == NULL) - goto done; - while (this->left != NULL){ - PUSH_NODE(stack, this); - this = this->left; - } - PUSH_NODE(stack, this); - stack->slot = 1; - } - this = TOP_NODE(stack); - while (stack->slot != slot && this != NULL) { - if (slot > stack->slot) { - if (this->right != NULL) { - this = this->right; - while (this->left != NULL) { - PUSH_NODE(stack, this); - this = this->left; - } - PUSH_NODE(stack, this); - } else { - for (;;) { - tmp = POP_NODE(stack); - this = TOP_NODE(stack); - if (this == NULL || this->left == tmp) - break; - } - } - ++(stack->slot); - } else { - if (this->left != NULL) { - this = this->left; - while (this->right != NULL) { - PUSH_NODE(stack, this); - this = this->right; - } - PUSH_NODE(stack, this); - } else { - for (;;) { - tmp = POP_NODE(stack); - this = TOP_NODE(stack); - if (this == NULL || this->right == tmp) - break; - } - } - --(stack->slot); - } + while (1) { + if (EMPTY_NODE(stack)) { + this = root; + if (this == NULL) + goto next_root; + while (this->left != NULL){ + PUSH_NODE(stack, this); + this = this->left; + } + PUSH_NODE(stack, this); + stack->slot++; + } + this = TOP_NODE(stack); + while (stack->slot != slot) { + ASSERT(this); + if (slot > stack->slot) { + if (this->right != NULL) { + this = this->right; + while (this->left != NULL) { + PUSH_NODE(stack, this); + this = this->left; + } + PUSH_NODE(stack, this); + } else { + for (;;) { + tmp = POP_NODE(stack); + this = TOP_NODE(stack); + if (!this) + goto next_root; + if (this->left == tmp) + break; + } + } + ++(stack->slot); + } else { + if (this->left != NULL) { + this = this->left; + while (this->right != NULL) { + PUSH_NODE(stack, this); + this = this->right; + } + PUSH_NODE(stack, this); + } else { + for (;;) { + tmp = POP_NODE(stack); + this = TOP_NODE(stack); + if (!this) + goto next_root; + if (this->right == tmp) + break; + } + } + --(stack->slot); + } + } + /* Found slot */ + ASSERT(this); + break; + +next_root: + if (!iter) + break; /* EOT */ + + pp = catree_find_next_root(iter); + if (!pp) + break; /* EOT */ + root = *pp; + stack->pos = 0; } -done: + + release_stack(tb,stack_container,stack); return this; } diff --git a/erts/emulator/beam/erl_db_tree_util.h b/erts/emulator/beam/erl_db_tree_util.h index c816660c71..02df74678d 100644 --- a/erts/emulator/beam/erl_db_tree_util.h +++ b/erts/emulator/beam/erl_db_tree_util.h @@ -92,7 +92,8 @@ int db_erase_object_tree_common(DbTable *tbl, TreeDbTerm **root, Eterm object, Eterm *ret, DbTableTree *stack_container); int db_slot_tree_common(Process *p, DbTable *tbl, TreeDbTerm *root, Eterm slot_term, Eterm *ret, - DbTableTree *stack_container); + DbTableTree *stack_container, + CATreeRootIterator*); int db_select_chunk_tree_common(Process *p, DbTable *tb, Eterm tid, Eterm pattern, Sint chunk_size, int reverse, Eterm *ret, -- cgit v1.2.3 From bfacc491d99156cef23de4e99a2d3cb0965eb075 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 16 Oct 2018 14:27:42 +0200 Subject: erts: Remove tree merging for print and foreach_offheap --- erts/emulator/beam/erl_db_catree.c | 26 ++++++++++++++++++++------ 1 file changed, 20 insertions(+), 6 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 46441c060b..1b4e5d45e7 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -2304,9 +2304,16 @@ static int db_take_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) static void db_print_catree(fmtfn_t to, void *to_arg, int show, DbTable *tbl) { - DbTableCATreeNode *base = merge_to_one_locked_base_node(&tbl->catree); - db_print_tree_common(to, to_arg, show, base->u.base.root, tbl); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + TreeDbTerm** root; + + init_root_iterator(&tbl->catree, &iter, 1); + root = catree_find_first_root(&iter); + do { + db_print_tree_common(to, to_arg, show, *root, tbl); + root = catree_find_next_root(&iter); + } while (root); + ASSERT(!iter.locked_bnode); } /* Release all memory occupied by a single table */ @@ -2382,9 +2389,16 @@ static void db_foreach_offheap_catree(DbTable *tbl, void (*func)(ErlOffHeap *, void *), void *arg) { - DbTableCATreeNode *base = merge_to_one_locked_base_node(&tbl->catree); - db_foreach_offheap_tree_common(base->u.base.root, func, arg); - wunlock_base_node(&(base->u.base)); + CATreeRootIterator iter; + TreeDbTerm** root; + + init_root_iterator(&tbl->catree, &iter, 1); + root = catree_find_first_root(&iter); + do { + db_foreach_offheap_tree_common(*root, func, arg); + root = catree_find_next_root(&iter); + } while (root); + ASSERT(!iter.locked_bnode); } static int db_lookup_dbterm_catree(Process *p, DbTable *tbl, Eterm key, Eterm obj, -- cgit v1.2.3 From 1add406b90e5cff980230d3450a437d5cc88aa60 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 15 Oct 2018 19:55:59 +0200 Subject: erts: Remove dead tree merging code --- erts/emulator/beam/erl_db_catree.c | 343 ------------------------------------ erts/emulator/beam/erl_lock_check.c | 7 +- 2 files changed, 1 insertion(+), 349 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 1b4e5d45e7..d433a5b56e 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -242,30 +242,6 @@ static ERTS_INLINE Sint cmp_key_route(Eterm key, return CMP(key, GET_ROUTE_NODE_KEY(obj)); } -static ERTS_INLINE void push_node_dyn_array(DbTable *tb, - CATreeNodeStack *stack, - DbTableCATreeNode *node) -{ - int i; - if (stack->pos == stack->size) { - DbTableCATreeNode **newArray = - erts_db_alloc(ERTS_ALC_T_DB_STK, tb, - sizeof(DbTableCATreeNode*) * (stack->size*2)); - for (i = 0; i < stack->pos; i++) { - newArray[i] = stack->array[i]; - } - if (stack->size > STACK_NEED) { - /* Dynamically allocated array that needs to be deallocated */ - erts_db_free(ERTS_ALC_T_DB_STK, tb, - stack->array, - sizeof(DbTableCATreeNode *) * stack->size); - } - stack->array = newArray; - stack->size = stack->size*2; - } - PUSH_NODE(stack, node); -} - /* * Used by the split_tree function */ @@ -914,20 +890,6 @@ static DbTableCATreeNode *create_base_node(DbTableCATree *tb, return p; } -static ERTS_INLINE -DbTableCATreeNode *create_wlocked_base_node(DbTableCATree *tb, - TreeDbTerm* root, - Eterm lc_key) -{ - DbTableCATreeNode* p = create_base_node(tb, root, lc_key); - ethr_rwmutex_rwlock(&p->u.base.lock.rwmtx); -#ifdef ERTS_ENABLE_LOCK_CHECK - erts_lc_trylock_flg(-1, &p->u.base.lock.lc, ERTS_LOCK_OPTIONS_RDWR); -#endif - return p; -} - - static ERTS_INLINE Uint sizeof_route_node(Uint key_size) { return (offsetof(DbTableCATreeNode, u.route.key.heap) @@ -1075,126 +1037,6 @@ rightmost_route_node(DbTableCATreeNode *root) return prev_node; } -static ERTS_INLINE DbTableCATreeNode* -leftmost_base_node_and_path(DbTableCATreeNode *root, CATreeNodeStack * stack) -{ - DbTableCATreeNode * node = root; - while (!node->is_base_node) { - PUSH_NODE(stack, node); - node = GET_LEFT_ACQB(node); - } - return node; -} - -static ERTS_INLINE DbTableCATreeNode* -get_next_base_node_and_path(DbTableCATreeNode *base_node, - CATreeNodeStack *stack) -{ - if (EMPTY_NODE(stack)) { /* The parent of b is the root */ - return NULL; - } else { - if (GET_LEFT(TOP_NODE(stack)) == base_node) { - return leftmost_base_node_and_path( - GET_RIGHT_ACQB(TOP_NODE(stack)), - stack); - } else { - Eterm pkey = - TOP_NODE(stack)->u.route.key.term; /* pKey = key of parent */ - POP_NODE(stack); - while (!EMPTY_NODE(stack)) { - if (TOP_NODE(stack)->u.route.is_valid && - cmp_key_route(pkey, TOP_NODE(stack)) <= 0) { - return leftmost_base_node_and_path(GET_RIGHT_ACQB(TOP_NODE(stack)), stack); - } else { - POP_NODE(stack); - } - } - } - return NULL; - } -} - -static ERTS_INLINE void -clone_stack(CATreeNodeStack *search_stack_ptr, - CATreeNodeStack *search_stack_copy_ptr) -{ - int i; - search_stack_copy_ptr->pos = search_stack_ptr->pos; - for (i = 0; i < search_stack_ptr->pos; i++) { - search_stack_copy_ptr->array[i] = search_stack_ptr->array[i]; - } -} - -static ERTS_INLINE DbTableCATreeBaseNode* -find_and_lock_next_base_node_and_path(DbTable *tbl, - CATreeNodeStack **search_stack_ptr_ptr, - CATreeNodeStack **search_stack_copy_ptr_ptr, - CATreeNodeStack *locked_base_nodes_stack_ptr) -{ - DbTableCATreeNode *current_node; - DbTableCATreeBaseNode *base_node; - CATreeNodeStack * tmp_stack_ptr; - - while (1) { - current_node = TOP_NODE(locked_base_nodes_stack_ptr); - clone_stack(*search_stack_ptr_ptr, *search_stack_copy_ptr_ptr); - current_node = - get_next_base_node_and_path(current_node, *search_stack_ptr_ptr); - if (current_node == NULL) { - return NULL; - } - base_node = ¤t_node->u.base; - rlock_base_node(base_node); - if (base_node->is_valid) - break; - - /* Retry */ - runlock_base_node(base_node); - /* Revert to previous state */ - current_node = TOP_NODE(locked_base_nodes_stack_ptr); - tmp_stack_ptr = *search_stack_ptr_ptr; - *search_stack_ptr_ptr = *search_stack_copy_ptr_ptr; - *search_stack_copy_ptr_ptr = tmp_stack_ptr; - } - - push_node_dyn_array(tbl, locked_base_nodes_stack_ptr, current_node); - return base_node; -} - -static ERTS_INLINE -void unlock_and_release_locked_base_node_stack(DbTable *tbl, - CATreeNodeStack *locked_base_nodes_stack_ptr) -{ - DbTableCATreeNode *current_node; - DbTableCATreeBaseNode *base_node; - int i; - for (i = 0; i < locked_base_nodes_stack_ptr->pos; i++) { - current_node = locked_base_nodes_stack_ptr->array[i]; - base_node = ¤t_node->u.base; - if (locked_base_nodes_stack_ptr->pos > 1) { - base_node->lock_statistics = /* This is not atomic which is fine as */ - base_node->lock_statistics + /* correctness does not depend on that. */ - ERL_DB_CATREE_LOCK_MORE_THAN_ONE_CONTRIBUTION; - } - runlock_base_node(base_node); - } - if (locked_base_nodes_stack_ptr->size > STACK_NEED) { - erts_db_free(ERTS_ALC_T_DB_STK, tbl, - locked_base_nodes_stack_ptr->array, - sizeof(DbTableCATreeNode *) * locked_base_nodes_stack_ptr->size); - } -} - -static ERTS_INLINE -void init_stack(CATreeNodeStack *stack, - DbTableCATreeNode **stack_array, - Uint init_size) -{ - stack->array = stack_array; - stack->pos = 0; - stack->size = init_size; -} - static ERTS_INLINE void init_tree_stack(DbTreeStack *stack, TreeDbTerm **stack_array, @@ -1205,191 +1047,6 @@ void init_tree_stack(DbTreeStack *stack, stack->slot = init_slot; } -#define DEC_ROUTE_NODE_STACK_AND_ARRAY(STACK_NAME) \ - CATreeNodeStack STACK_NAME; \ - CATreeNodeStack * STACK_NAME##_ptr = &(STACK_NAME); \ - DbTableCATreeNode *STACK_NAME##_array[STACK_NEED]; - -#define DECLARE_AND_INIT_BASE_NODE_SEARCH_STACKS \ -DEC_ROUTE_NODE_STACK_AND_ARRAY(search_stack) \ -DEC_ROUTE_NODE_STACK_AND_ARRAY(search_stack_copy) \ -DEC_ROUTE_NODE_STACK_AND_ARRAY(locked_base_nodes_stack) \ -init_stack(&search_stack, search_stack_array, 0); \ -init_stack(&search_stack_copy, search_stack_copy_array, 0); \ -init_stack(&locked_base_nodes_stack, locked_base_nodes_stack_array, STACK_NEED);/* Abuse as stack array size*/ - -/* - * Locks and returns the base node that contains the specified key if - * it is present. The function saves the search path to the found base - * node in search_stack_ptr and adds the found base node to - * locked_base_nodes_stack_ptr. - */ -static ERTS_INLINE DbTableCATreeBaseNode * -lock_base_node_with_key(DbTable *tbl, - Eterm key, - CATreeNodeStack * search_stack_ptr, - CATreeNodeStack * locked_base_nodes_stack_ptr) -{ - int retry; - DbTableCATreeNode *current_node; - DbTableCATreeBaseNode *base_node; - DbTableCATree* tb = &tbl->catree; - do { - retry = 0; - current_node = GET_ROOT_ACQB(tb); - while ( ! current_node->is_base_node ) { - PUSH_NODE(search_stack_ptr, current_node); - if( cmp_key_route(key,current_node) < 0 ) { - current_node = GET_LEFT_ACQB(current_node); - } else { - current_node = GET_RIGHT_ACQB(current_node); - } - } - base_node = ¤t_node->u.base; - rlock_base_node(base_node); - if ( ! base_node->is_valid ) { - /* Retry */ - runlock_base_node(base_node); - retry = 1; - } - } while(retry); - push_node_dyn_array(tbl, locked_base_nodes_stack_ptr, current_node); - return base_node; -} - -/* - * Joins a base node with it's right neighbor. Returns the base node - * resulting from the join in locked state or NULL if there is no base - * node to join with. - */ -static DbTableCATreeNode* -erl_db_catree_force_join_right(DbTableCATree *tb, - DbTableCATreeNode *parent, - DbTableCATreeNode *thiz, - DbTableCATreeNode **result_parent_wb) -{ - DbTableCATreeNode *gparent; - DbTableCATreeNode *neighbor; - DbTableCATreeNode *new_neighbor; - DbTableCATreeNode *neighbor_parent; - TreeDbTerm* new_root; - - if (parent == NULL) { - return NULL; - } - ASSERT(thiz == GET_LEFT(parent)); - while (1) { - neighbor = leftmost_base_node(GET_RIGHT_ACQB(parent)); - wlock_base_node_no_stats(&neighbor->u.base); - if (neighbor->u.base.is_valid) - break; - wunlock_base_node(&neighbor->u.base); - } - lock_route_node(parent); - parent->u.route.is_valid = 0; - neighbor->u.base.is_valid = 0; - thiz->u.base.is_valid = 0; - while (1) { - gparent = parent_of(tb, parent); - if (gparent == NULL) - break; - lock_route_node(gparent); - if (gparent->u.route.is_valid) - break; - unlock_route_node(gparent); - } - if (gparent == NULL) { - SET_ROOT_RELB(tb, GET_RIGHT(parent)); - } else if (GET_LEFT(gparent) == parent) { - SET_LEFT_RELB(gparent, GET_RIGHT(parent)); - } else { - SET_RIGHT_RELB(gparent, GET_RIGHT(parent)); - } - unlock_route_node(parent); - if (gparent != NULL) { - unlock_route_node(gparent); - } - - new_root = join_trees(thiz->u.base.root, neighbor->u.base.root); - new_neighbor = create_wlocked_base_node(tb, new_root, - LC_ORDER(thiz->u.base.lc_key.term)); - - if (GET_RIGHT(parent) == neighbor) { - neighbor_parent = gparent; - } else { - neighbor_parent = leftmost_route_node(GET_RIGHT(parent)); - } - if(neighbor_parent == NULL) { - SET_ROOT_RELB(tb, new_neighbor); - } else if (GET_LEFT(neighbor_parent) == neighbor) { - SET_LEFT_RELB(neighbor_parent, new_neighbor); - } else { - SET_RIGHT_RELB(neighbor_parent, new_neighbor); - } - wunlock_base_node(&thiz->u.base); - wunlock_base_node(&neighbor->u.base); - /* Free the parent and base */ - erts_schedule_db_free(&tb->common, - do_free_route_node, - parent, - &parent->u.route.free_item, - sizeof_route_node(parent->u.route.key.size)); - erts_schedule_db_free(&tb->common, - do_free_base_node, - thiz, - &thiz->u.base.free_item, - sizeof_base_node(thiz->u.base.lc_key.size)); - erts_schedule_db_free(&tb->common, - do_free_base_node, - neighbor, - &neighbor->u.base.free_item, - sizeof_base_node(neighbor->u.base.lc_key.size)); - - *result_parent_wb = neighbor_parent; - return new_neighbor; -} - -/* - * Used to merge together all base nodes for operations such as last - * and select_*. Returns the base node resulting from the merge in - * locked state. - */ -static DbTableCATreeNode * -merge_to_one_locked_base_node(DbTableCATree* tb) -{ - DbTableCATreeNode *parent; - DbTableCATreeNode *new_parent; - DbTableCATreeNode *base; - DbTableCATreeNode *new_base; - int is_not_valid; - /* Find first base node */ - do { - parent = NULL; - base = GET_ROOT_ACQB(tb); - while ( ! base->is_base_node ) { - parent = base; - base = GET_LEFT_ACQB(base); - } - wlock_base_node_no_stats(&(base->u.base)); - is_not_valid = ! base->u.base.is_valid; - if (is_not_valid) { - wunlock_base_node(&(base->u.base)); - } - } while(is_not_valid); - do { - new_base = erl_db_catree_force_join_right(tb, - parent, - base, - &new_parent); - if (new_base != NULL) { - base = new_base; - parent = new_parent; - } - } while(new_base != NULL); - return base; -} - - static void join_catree(DbTableCATree *tb, DbTableCATreeNode *parent, DbTableCATreeNode *thiz) diff --git a/erts/emulator/beam/erl_lock_check.c b/erts/emulator/beam/erl_lock_check.c index 987e370341..018c82aabb 100644 --- a/erts/emulator/beam/erl_lock_check.c +++ b/erts/emulator/beam/erl_lock_check.c @@ -1034,11 +1034,6 @@ erts_lc_trylock_force_busy_flg(erts_lc_lock_t *lck, erts_lock_options_t options) #endif } -/* - * locked = 0 trylock failed - * locked > 0 trylock succeeded - * locked < 0 prelocking of newly created lock (no lock order check) - */ void erts_lc_trylock_flg_x(int locked, erts_lc_lock_t *lck, erts_lock_options_t options, char *file, unsigned int line) { @@ -1069,7 +1064,7 @@ void erts_lc_trylock_flg_x(int locked, erts_lc_lock_t *lck, erts_lock_options_t for (tl_lck = thr->locked.last; tl_lck; tl_lck = tl_lck->prev) { int order = compare_locked_by_id_extra(tl_lck, lck); if (order <= 0) { - if (order == 0 && locked >= 0) + if (order == 0) lock_twice("Trylocking", thr, lck, options); if (locked) { ll->next = tl_lck->next; -- cgit v1.2.3 From 375a1f5c29fd2d3b537e117149e78b0ac61e263f Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 16 Oct 2018 20:04:33 +0200 Subject: erts: Implement ets:info(T, stats) for catrees {RouteNodes, BaseNodes, MaxRouteTreeDepth} --- erts/emulator/beam/erl_db.c | 15 +++++++++++++-- erts/emulator/beam/erl_db_catree.c | 36 ++++++++++++++++++++++++++++++++++++ erts/emulator/beam/erl_db_catree.h | 8 ++++++++ 3 files changed, 57 insertions(+), 2 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db.c b/erts/emulator/beam/erl_db.c index 3653c0bf7c..337efa94bd 100644 --- a/erts/emulator/beam/erl_db.c +++ b/erts/emulator/beam/erl_db.c @@ -4247,9 +4247,20 @@ static Eterm table_info(Process* p, DbTable* tb, Eterm What) make_small(stats.max_chain_len), make_small(stats.kept_items)); } - else { + else if (IS_CATREE_TABLE(tb->common.status)) { + DbCATreeStats stats; + Eterm* hp; + + db_calc_stats_catree(&tb->catree, &stats); + hp = HAlloc(p, 4); + ret = TUPLE3(hp, + make_small(stats.route_nodes), + make_small(stats.base_nodes), + make_small(stats.max_depth)); + + } + else ret = am_false; - } } return ret; } diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index d433a5b56e..f467230ced 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -2118,6 +2118,42 @@ void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable) } #endif /* ERTS_ENABLE_LOCK_COUNT */ +void db_calc_stats_catree(DbTableCATree* tb, DbCATreeStats* stats) +{ + DbTableCATreeNode* stack[ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT]; + DbTableCATreeNode* node; + Uint depth = 0; + + stats->route_nodes = 0; + stats->base_nodes = 0; + stats->max_depth = 0; + + node = GET_ROOT(tb); + do { + while (!node->is_base_node) { + stats->route_nodes++; + ASSERT(depth < sizeof(stack)/sizeof(*stack)); + stack[depth++] = node; /* PUSH parent */ + if (stats->max_depth < depth) + stats->max_depth = depth; + node = GET_LEFT(node); + } + stats->base_nodes++; + + while (depth > 0) { + DbTableCATreeNode* parent = stack[depth-1]; + if (node == GET_LEFT(parent)) { + node = GET_RIGHT(parent); + break; + } + else { + ASSERT(node == GET_RIGHT(parent)); + node = parent; + depth--; /* POP parent */ + } + } + } while (depth > 0); +} #ifdef HARDDEBUG diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h index 510a9e81d3..e3d574589c 100644 --- a/erts/emulator/beam/erl_db_catree.h +++ b/erts/emulator/beam/erl_db_catree.h @@ -120,4 +120,12 @@ TreeDbTerm** catree_find_last_root(CATreeRootIterator*); void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable); #endif +typedef struct { + Uint route_nodes; + Uint base_nodes; + Uint max_depth; +} DbCATreeStats; +void db_calc_stats_catree(DbTableCATree*, DbCATreeStats*); + + #endif /* _DB_CATREE_H */ -- cgit v1.2.3 From 129e61564807c0ad43faf9d0c36260c793501920 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 11 Oct 2018 23:34:49 +0200 Subject: erts: Add erts_debug feature 'ets_force_split' to easier generate a routing tree for test without having to spend cpu to provoke actual repeated lock conflicts. --- erts/emulator/beam/erl_bif_info.c | 8 ++++++++ erts/emulator/beam/erl_db.c | 13 +++++++++++++ erts/emulator/beam/erl_db.h | 1 + erts/emulator/beam/erl_db_catree.c | 25 +++++++++++++++++++++++-- erts/emulator/beam/erl_db_catree.h | 2 ++ erts/emulator/beam/erl_db_util.h | 2 ++ 6 files changed, 49 insertions(+), 2 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_bif_info.c b/erts/emulator/beam/erl_bif_info.c index 2a8e7e8858..3b0f0d33fa 100644 --- a/erts/emulator/beam/erl_bif_info.c +++ b/erts/emulator/beam/erl_bif_info.c @@ -4669,6 +4669,14 @@ BIF_RETTYPE erts_debug_set_internal_state_2(BIF_ALIST_2) BIF_RET(am_notsup); #endif } + else if (ERTS_IS_ATOM_STR("ets_force_split", BIF_ARG_1)) { + if (is_tuple(BIF_ARG_2)) { + Eterm* tpl = tuple_val(BIF_ARG_2); + + if (erts_ets_force_split(tpl[1], tpl[2] == am_true)) + BIF_RET(am_ok); + } + } } BIF_ERROR(BIF_P, BADARG); diff --git a/erts/emulator/beam/erl_db.c b/erts/emulator/beam/erl_db.c index 337efa94bd..df6f42edd3 100644 --- a/erts/emulator/beam/erl_db.c +++ b/erts/emulator/beam/erl_db.c @@ -4465,3 +4465,16 @@ void erts_lcnt_update_db_locks(int enable) { #ifdef ETS_DBG_FORCE_TRAP erts_aint_t erts_ets_dbg_force_trap = 0; #endif + +int erts_ets_force_split(Eterm tid, int on) +{ + DbTable* tb = tid2tab(tid); + if (!tb || !IS_CATREE_TABLE(tb->common.type)) + return 0; + + db_lock(tb, LCK_WRITE); + if (!(tb->common.status & DB_DELETE)) + db_catree_force_split(&tb->catree, on); + db_unlock(tb, LCK_WRITE); + return 1; +} diff --git a/erts/emulator/beam/erl_db.h b/erts/emulator/beam/erl_db.h index 7a915ccea2..5955d42aae 100644 --- a/erts/emulator/beam/erl_db.h +++ b/erts/emulator/beam/erl_db.h @@ -130,6 +130,7 @@ extern Export ets_select_continue_exp; extern erts_atomic_t erts_ets_misc_mem_size; Eterm erts_ets_colliding_names(Process*, Eterm name, Uint cnt); +int erts_ets_force_split(Eterm tid, int on); Uint erts_db_get_max_tabs(void); Eterm erts_db_make_tid(Process *c_p, DbTableCommon *tb); diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index f467230ced..975e19a878 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -885,7 +885,8 @@ static DbTableCATreeNode *create_base_node(DbTableCATree *tb, "erl_db_catree_base_node", lc_key, ERTS_LOCK_FLAGS_CATEGORY_DB); - p->u.base.lock_statistics = 0; + p->u.base.lock_statistics = ((tb->common.status & DB_CATREE_FORCE_SPLIT) + ? INT_MAX : 0); p->u.base.is_valid = 1; return p; } @@ -1205,7 +1206,8 @@ static void split_catree(DbTableCATree *tb, DbTableCATreeNode* ERTS_RESTRICT new_route; if (less_than_two_elements(base->u.base.root)) { - base->u.base.lock_statistics = 0; + if (!(tb->common.status & DB_CATREE_FORCE_SPLIT)) + base->u.base.lock_statistics = 0; wunlock_base_node(&base->u.base); return; } else { @@ -2118,6 +2120,25 @@ void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable) } #endif /* ERTS_ENABLE_LOCK_COUNT */ +void db_catree_force_split(DbTableCATree* tb, int on) +{ + CATreeRootIterator iter; + TreeDbTerm** root; + + init_root_iterator(tb, &iter, 1); + root = catree_find_first_root(&iter); + do { + iter.locked_bnode->lock_statistics = (on ? INT_MAX : 0); + root = catree_find_next_root(&iter); + } while (root); + ASSERT(!iter.locked_bnode); + + if (on) + tb->common.status |= DB_CATREE_FORCE_SPLIT; + else + tb->common.status &= ~DB_CATREE_FORCE_SPLIT; +} + void db_calc_stats_catree(DbTableCATree* tb, DbCATreeStats* stats) { DbTableCATreeNode* stack[ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT]; diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h index e3d574589c..feb6f27980 100644 --- a/erts/emulator/beam/erl_db_catree.h +++ b/erts/emulator/beam/erl_db_catree.h @@ -120,6 +120,8 @@ TreeDbTerm** catree_find_last_root(CATreeRootIterator*); void erts_lcnt_enable_db_catree_lock_count(DbTableCATree *tb, int enable); #endif +void db_catree_force_split(DbTableCATree*, int on); + typedef struct { Uint route_nodes; Uint base_nodes; diff --git a/erts/emulator/beam/erl_db_util.h b/erts/emulator/beam/erl_db_util.h index be74bc795c..dcffaf9718 100644 --- a/erts/emulator/beam/erl_db_util.h +++ b/erts/emulator/beam/erl_db_util.h @@ -290,6 +290,8 @@ typedef struct db_table_common { #define DB_NAMED_TABLE (1 << 11) #define DB_BUSY (1 << 12) +#define DB_CATREE_FORCE_SPLIT (1 << 31) /* erts_debug */ + #define IS_HASH_TABLE(Status) (!!((Status) & \ (DB_BAG | DB_SET | DB_DUPLICATE_BAG))) #define IS_TREE_TABLE(Status) (!!((Status) & \ -- cgit v1.2.3 From 8cd07dae15569deea3a0b539057299a238c8ddc1 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 17 Oct 2018 21:31:19 +0200 Subject: erts: Optimize find_next/prev_from_pb_key to not have to backtrack up on the stack. --- erts/emulator/beam/erl_db_tree.c | 38 ++++++++++++++------------------------ 1 file changed, 14 insertions(+), 24 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index a3147e0f68..250d90e189 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -2947,7 +2947,7 @@ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, { TreeDbTerm* root; TreeDbTerm *this; - TreeDbTerm *tmp; + Uint candidate = 0; Sint c; if (iter) { @@ -2967,20 +2967,15 @@ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, PUSH_NODE(stack, this); if (( c = cmp_partly_bound(key,GETKEY(tbl, this->dbterm.tpl))) >= 0) { if (this->right == NULL) { - do { - tmp = POP_NODE(stack); - if (( this = TOP_NODE(stack)) == NULL) { - return NULL; - } - } while (this->right == tmp); - return this; - } else - this = this->right; + stack->pos = candidate; + return TOP_NODE(stack); + } + this = this->right; } else /*if (c < 0)*/ { if (this->left == NULL) /* Done */ return this; - else - this = this->left; + candidate = stack->pos; + this = this->left; } } } @@ -2991,7 +2986,7 @@ static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, { TreeDbTerm* root; TreeDbTerm *this; - TreeDbTerm *tmp; + Uint candidate = 0; Sint c; if (iter) { @@ -3011,20 +3006,15 @@ static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, PUSH_NODE(stack, this); if (( c = cmp_partly_bound(key,GETKEY(tbl, this->dbterm.tpl))) <= 0) { if (this->left == NULL) { - do { - tmp = POP_NODE(stack); - if (( this = TOP_NODE(stack)) == NULL) { - return NULL; - } - } while (this->left == tmp); - return this; - } else - this = this->left; + stack->pos = candidate; + return TOP_NODE(stack); + } + this = this->left; } else /*if (c > 0)*/ { if (this->right == NULL) /* Done */ return this; - else - this = this->right; + candidate = stack->pos; + this = this->right; } } } -- cgit v1.2.3 From 77d3d262c5e7d784204a6d91b79ed2f46b4013ad Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 18 Oct 2018 11:29:06 +0200 Subject: erts: Do contention adaptions during (updating) iterations Once an iteration key has been found, never fall back to first/last key in next/prev tree as trees may split or join under our feet. I.e we must always use previous key when searching for the next key. --- erts/emulator/beam/erl_db_catree.c | 315 ++++++++++++++++++++++--------------- erts/emulator/beam/erl_db_catree.h | 11 +- erts/emulator/beam/erl_db_tree.c | 201 ++++++++++++++--------- 3 files changed, 315 insertions(+), 212 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 975e19a878..072858f3f5 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -158,6 +158,13 @@ db_lookup_dbterm_catree(Process *, DbTable *, Eterm key, Eterm obj, DbUpdateHandle*); static void db_finalize_dbterm_catree(int cret, DbUpdateHandle *); +static void split_catree(DbTableCATree *tb, + DbTableCATreeNode* ERTS_RESTRICT base, + DbTableCATreeNode* ERTS_RESTRICT parent); +static void join_catree(DbTableCATree *tb, + DbTableCATreeNode *thiz, + DbTableCATreeNode *parent); + /* ** External interface @@ -634,9 +641,10 @@ int try_wlock_base_node(DbTableCATreeBaseNode *base_node) * Locks a base node without adjusting the lock statistics */ static ERTS_INLINE -void wlock_base_node_no_stats(DbTableCATreeBaseNode *base_node) +void wlock_base_node_no_stats(DbTableCATreeNode *base_node) { - erts_rwmtx_rwlock(&base_node->lock); + ASSERT(base_node->is_base_node); + erts_rwmtx_rwlock(&base_node->u.base.lock); } /* @@ -644,33 +652,54 @@ void wlock_base_node_no_stats(DbTableCATreeBaseNode *base_node) * the lock was contended or not */ static ERTS_INLINE -void wlock_base_node(DbTableCATreeBaseNode *base_node) +void wlock_base_node(DbTableCATreeNode *base_node) { - if (try_wlock_base_node(base_node)) { + ASSERT(base_node->is_base_node); + if (try_wlock_base_node(&base_node->u.base)) { /* The lock is contended */ wlock_base_node_no_stats(base_node); - base_node->lock_statistics += ERL_DB_CATREE_LOCK_FAILURE_CONTRIBUTION; + base_node->u.base.lock_statistics += ERL_DB_CATREE_LOCK_FAILURE_CONTRIBUTION; } else { - base_node->lock_statistics += ERL_DB_CATREE_LOCK_SUCCESS_CONTRIBUTION; + base_node->u.base.lock_statistics += ERL_DB_CATREE_LOCK_SUCCESS_CONTRIBUTION; } } static ERTS_INLINE -void wunlock_base_node(DbTableCATreeBaseNode *base_node) +void wunlock_base_node(DbTableCATreeNode *base_node) { - erts_rwmtx_rwunlock(&base_node->lock); + erts_rwmtx_rwunlock(&base_node->u.base.lock); +} + +static ERTS_INLINE +void wunlock_adapt_base_node(DbTableCATree* tb, + DbTableCATreeNode* base_node, + DbTableCATreeNode* parent, + int current_level) +{ + if (base_node->u.base.lock_statistics > ERL_DB_CATREE_HIGH_CONTENTION_LIMIT + && current_level < ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT) { + split_catree(tb, base_node, parent); + } + else if (base_node->u.base.lock_statistics < ERL_DB_CATREE_LOW_CONTENTION_LIMIT) { + join_catree(tb, base_node, parent); + } + else { + wunlock_base_node(base_node); + } } static ERTS_INLINE -void rlock_base_node(DbTableCATreeBaseNode *base_node) +void rlock_base_node(DbTableCATreeNode *base_node) { - erts_rwmtx_rlock(&base_node->lock); + ASSERT(base_node->is_base_node); + erts_rwmtx_rlock(&base_node->u.base.lock); } static ERTS_INLINE -void runlock_base_node(DbTableCATreeBaseNode *base_node) +void runlock_base_node(DbTableCATreeNode *base_node) { - erts_rwmtx_runlock(&base_node->lock); + ASSERT(base_node->is_base_node); + erts_rwmtx_runlock(&base_node->u.base.lock); } static ERTS_INLINE @@ -695,17 +724,23 @@ void init_root_iterator(DbTableCATree* tb, CATreeRootIterator* iter, iter->read_only = read_only; iter->locked_bnode = NULL; iter->next_route_key = THE_NON_VALUE; + iter->search_key = NULL; } static ERTS_INLINE void lock_iter_base_node(CATreeRootIterator* iter, - DbTableCATreeBaseNode *base_node) + DbTableCATreeNode *base_node, + DbTableCATreeNode *parent, + int current_level) { ASSERT(!iter->locked_bnode); if (iter->read_only) rlock_base_node(base_node); - else + else { wlock_base_node(base_node); + iter->bnode_parent = parent; + iter->bnode_level = current_level; + } iter->locked_bnode = base_node; } @@ -715,12 +750,23 @@ void unlock_iter_base_node(CATreeRootIterator* iter) ASSERT(iter->locked_bnode); if (iter->read_only) runlock_base_node(iter->locked_bnode); + else if (iter->locked_bnode->u.base.is_valid) { + wunlock_adapt_base_node(iter->tb, iter->locked_bnode, + iter->bnode_parent, iter->bnode_level); + } else wunlock_base_node(iter->locked_bnode); iter->locked_bnode = NULL; } - +static ERTS_INLINE +void destroy_root_iterator(CATreeRootIterator* iter) +{ + if (iter->locked_bnode) + unlock_iter_base_node(iter); + if (iter->search_key) + erts_free(ERTS_ALC_T_DB_TMP, iter->search_key); +} /* * The following macros are used to create the ETS functions that only @@ -736,8 +782,8 @@ typedef struct } FindBaseNode; static ERTS_INLINE -DbTableCATreeBaseNode* find_base_node(DbTableCATree* tb, Eterm key, - FindBaseNode* fbn) +DbTableCATreeNode* find_base_node(DbTableCATree* tb, Eterm key, + FindBaseNode* fbn) { DbTableCATreeNode* ERTS_RESTRICT node = GET_ROOT_ACQB(tb); fbn->parent = NULL; @@ -751,7 +797,7 @@ DbTableCATreeBaseNode* find_base_node(DbTableCATree* tb, Eterm key, node = GET_RIGHT_ACQB(node); } } - return &node->u.base; + return node; } #define ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(LOCK,UNLOCK) \ @@ -776,25 +822,14 @@ DbTableCATreeBaseNode* find_base_node(DbTableCATree* tb, Eterm key, } \ } \ base_node = ¤t_node->u.base; \ - LOCK(base_node); \ + LOCK(current_node); \ if ( ! base_node->is_valid ) { \ /* Retry */ \ - UNLOCK(base_node); \ + UNLOCK(current_node); \ retry = 1; \ } \ } while(retry); - -#define ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_ADAPT_AND_UNLOCK_PART \ - if (base_node->lock_statistics > ERL_DB_CATREE_HIGH_CONTENTION_LIMIT \ - && current_level < ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT) { \ - split_catree(tb, prev_node, current_node); \ - } else if (base_node->lock_statistics < ERL_DB_CATREE_LOW_CONTENTION_LIMIT) { \ - join_catree(tb, prev_node, current_node); \ - } else { \ - wunlock_base_node(base_node); \ - } - #define ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION(FUN_POSTFIX,PARAMETERS,SEQUENTAIL_CALL) \ static int erl_db_catree_do_operation_##FUN_POSTFIX(DbTableCATree *tb, \ Eterm key, \ @@ -802,7 +837,7 @@ DbTableCATreeBaseNode* find_base_node(DbTableCATree* tb, Eterm key, int result; \ ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(wlock_base_node,wunlock_base_node) \ result = SEQUENTAIL_CALL; \ - ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_ADAPT_AND_UNLOCK_PART \ + wunlock_adapt_base_node(tb, current_node, prev_node, current_level);\ return result; \ } @@ -814,7 +849,7 @@ DbTableCATreeBaseNode* find_base_node(DbTableCATree* tb, Eterm key, int result; \ ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(rlock_base_node,runlock_base_node) \ result = SEQUENTAIL_CALL; \ - runlock_base_node(base_node); \ + runlock_base_node(current_node); \ return result; \ } @@ -1049,8 +1084,8 @@ void init_tree_stack(DbTreeStack *stack, } static void join_catree(DbTableCATree *tb, - DbTableCATreeNode *parent, - DbTableCATreeNode *thiz) + DbTableCATreeNode *thiz, + DbTableCATreeNode *parent) { DbTableCATreeNode *gparent; DbTableCATreeNode *neighbor; @@ -1060,7 +1095,7 @@ static void join_catree(DbTableCATree *tb, ASSERT(thiz->is_base_node); if (parent == NULL) { thiz->u.base.lock_statistics = 0; - wunlock_base_node(&thiz->u.base); + wunlock_base_node(thiz); return; } ASSERT(!parent->is_base_node); @@ -1069,12 +1104,12 @@ static void join_catree(DbTableCATree *tb, if (try_wlock_base_node(&neighbor->u.base)) { /* Failed to acquire lock */ thiz->u.base.lock_statistics = 0; - wunlock_base_node(&thiz->u.base); + wunlock_base_node(thiz); return; } else if (!neighbor->u.base.is_valid) { thiz->u.base.lock_statistics = 0; - wunlock_base_node(&thiz->u.base); - wunlock_base_node(&neighbor->u.base); + wunlock_base_node(thiz); + wunlock_base_node(neighbor); return; } else { lock_route_node(parent); @@ -1120,12 +1155,12 @@ static void join_catree(DbTableCATree *tb, if (try_wlock_base_node(&neighbor->u.base)) { /* Failed to acquire lock */ thiz->u.base.lock_statistics = 0; - wunlock_base_node(&thiz->u.base); + wunlock_base_node(thiz); return; } else if (!neighbor->u.base.is_valid) { thiz->u.base.lock_statistics = 0; - wunlock_base_node(&thiz->u.base); - wunlock_base_node(&neighbor->u.base); + wunlock_base_node(thiz); + wunlock_base_node(neighbor); return; } else { lock_route_node(parent); @@ -1177,8 +1212,8 @@ static void join_catree(DbTableCATree *tb, } else { SET_RIGHT_RELB(neighbor_parent, new_neighbor); } - wunlock_base_node(&thiz->u.base); - wunlock_base_node(&neighbor->u.base); + wunlock_base_node(thiz); + wunlock_base_node(neighbor); /* Free the parent and base */ erts_schedule_db_free(&tb->common, do_free_route_node, @@ -1198,8 +1233,9 @@ static void join_catree(DbTableCATree *tb, } static void split_catree(DbTableCATree *tb, - DbTableCATreeNode* ERTS_RESTRICT parent, - DbTableCATreeNode* ERTS_RESTRICT base) { + DbTableCATreeNode* ERTS_RESTRICT base, + DbTableCATreeNode* ERTS_RESTRICT parent) +{ TreeDbTerm *splitOutWriteBack; DbTableCATreeNode* ERTS_RESTRICT new_left; DbTableCATreeNode* ERTS_RESTRICT new_right; @@ -1208,7 +1244,7 @@ static void split_catree(DbTableCATree *tb, if (less_than_two_elements(base->u.base.root)) { if (!(tb->common.status & DB_CATREE_FORCE_SPLIT)) base->u.base.lock_statistics = 0; - wunlock_base_node(&base->u.base); + wunlock_base_node(base); return; } else { TreeDbTerm *left_tree; @@ -1234,7 +1270,7 @@ static void split_catree(DbTableCATree *tb, SET_RIGHT_RELB(parent, new_route); } base->u.base.is_valid = 0; - wunlock_base_node(&base->u.base); + wunlock_base_node(base); erts_schedule_db_free(&tb->common, do_free_base_node, base, @@ -1386,14 +1422,13 @@ static int db_first_catree(Process *p, DbTable *tbl, Eterm *ret) init_root_iterator(&tbl->catree, &iter, 1); root = *catree_find_first_root(&iter); if (!root) { - TreeDbTerm **pp = catree_find_next_root(&iter); + TreeDbTerm **pp = catree_find_next_root(&iter, NULL); root = pp ? *pp : NULL; } result = db_first_tree_common(p, tbl, root, ret, NULL); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1407,7 +1442,7 @@ static int db_next_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) init_root_iterator(&tbl->catree, &iter, 1); iter.next_route_key = key; - rootp = catree_find_next_root(&iter); + rootp = catree_find_next_root(&iter, NULL); do { init_tree_stack(&stack, stack_array, 0); @@ -1415,11 +1450,10 @@ static int db_next_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) if (result != DB_ERROR_NONE || *ret != am_EOT) break; - rootp = catree_find_next_root(&iter); + rootp = catree_find_next_root(&iter, NULL); } while (rootp); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1432,14 +1466,13 @@ static int db_last_catree(Process *p, DbTable *tbl, Eterm *ret) init_root_iterator(&tbl->catree, &iter, 1); root = *catree_find_last_root(&iter); if (!root) { - TreeDbTerm **pp = catree_find_prev_root(&iter); + TreeDbTerm **pp = catree_find_prev_root(&iter, NULL); root = pp ? *pp : NULL; } result = db_last_tree_common(p, tbl, root, ret, NULL); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1453,7 +1486,7 @@ static int db_prev_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) init_root_iterator(&tbl->catree, &iter, 1); iter.next_route_key = key; - rootp = catree_find_prev_root(&iter); + rootp = catree_find_prev_root(&iter, NULL); do { init_tree_stack(&stack, stack_array, 0); @@ -1461,11 +1494,10 @@ static int db_prev_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) &stack); if (result != DB_ERROR_NONE || *ret != am_EOT) break; - rootp = catree_find_prev_root(&iter); + rootp = catree_find_prev_root(&iter, NULL); } while (rootp); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1506,16 +1538,16 @@ static int db_get_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) TreeDbTerm** catree_find_root(Eterm key, CATreeRootIterator* iter) { FindBaseNode fbn; - DbTableCATreeBaseNode* base_node; + DbTableCATreeNode* base_node; while (1) { base_node = find_base_node(iter->tb, key, &fbn); - lock_iter_base_node(iter, base_node); - if (base_node->is_valid) + lock_iter_base_node(iter, base_node, fbn.parent, fbn.current_level); + if (base_node->u.base.is_valid) break; unlock_iter_base_node(iter); } - return &base_node->root; + return &base_node->u.base.root; } @@ -1526,33 +1558,34 @@ TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, DbTableCATreeNode *rejected_base = NULL; #endif DbTableCATreeNode *node; + DbTableCATreeNode *parent; DbTableCATreeNode* next_route_node; + int current_level; ASSERT(!iter->locked_bnode); while (1) { node = GET_ROOT_ACQB(iter->tb); + current_level = 0; + parent = NULL; next_route_node = NULL; while (!node->is_base_node) { + current_level++; + parent = node; if (cmp_partly_bound(key, GET_ROUTE_NODE_KEY(node)) <= 0) { + next_route_node = node; node = GET_LEFT_ACQB(node); } else { - next_route_node = node; node = GET_RIGHT_ACQB(node); } } ASSERT(node != rejected_base); - lock_iter_base_node(iter, &node->u.base); + lock_iter_base_node(iter, node, parent, current_level); if (node->u.base.is_valid) { - if (node->u.base.root || !next_route_node) { - iter->next_route_key = (next_route_node ? - next_route_node->u.route.key.term : - THE_NON_VALUE); - return &node->u.base.root; - } - unlock_iter_base_node(iter); - iter->next_route_key = next_route_node->u.route.key.term; - return catree_find_next_root(iter); + iter->next_route_key = (next_route_node ? + next_route_node->u.route.key.term : + THE_NON_VALUE); + return &node->u.base.root; } /* Retry */ unlock_iter_base_node(iter); @@ -1562,25 +1595,57 @@ TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, } } -TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next) +static Eterm copy_iter_search_key(CATreeRootIterator* iter, Eterm key) +{ + Uint key_size; + + if (is_immed(key)) + return key; + + if (iter->search_key) { + ASSERT(key != iter->search_key->term); + destroy_route_key(iter->search_key); + } + key_size = size_object(key); + if (!iter->search_key || key_size > iter->search_key->size) { + iter->search_key = erts_realloc(ERTS_ALC_T_DB_TMP, + iter->search_key, + (offsetof(DbRouteKey, heap) + + key_size*sizeof(Eterm))); + } + copy_route_key(iter->search_key, key, key_size); + return iter->search_key->term; +} + +TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, + Eterm *keyp) { #ifdef DEBUG DbTableCATreeNode *rejected_base = NULL; #endif DbTableCATreeNode *node; + DbTableCATreeNode *parent; DbTableCATreeNode* next_route_node; Eterm key = iter->next_route_key; + int current_level; - if (iter->locked_bnode) + if (iter->locked_bnode) { + if (keyp) + *keyp = copy_iter_search_key(iter, *keyp); unlock_iter_base_node(iter); + } if (is_non_value(key)) return NULL; while (1) { node = GET_ROOT_ACQB(iter->tb); + current_level = 0; + parent = NULL; next_route_node = NULL; while (!node->is_base_node) { + current_level++; + parent = node; if (next) { if (cmp_key_route(key,node) < 0) { next_route_node = node; @@ -1599,13 +1664,13 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next) } } ASSERT(node != rejected_base); - lock_iter_base_node(iter, &node->u.base); + lock_iter_base_node(iter, node, parent, current_level); if (node->u.base.is_valid) { if (node->u.base.root) { iter->next_route_key = (next_route_node ? next_route_node->u.route.key.term : THE_NON_VALUE); - iter->locked_bnode = &node->u.base; + iter->locked_bnode = node; return &node->u.base.root; } if (!next_route_node) { @@ -1622,14 +1687,14 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next) } } -TreeDbTerm** catree_find_next_root(CATreeRootIterator *iter) +TreeDbTerm** catree_find_next_root(CATreeRootIterator *iter, Eterm* keyp) { - return catree_find_nextprev_root(iter, 1); + return catree_find_nextprev_root(iter, 1, keyp); } -TreeDbTerm** catree_find_prev_root(CATreeRootIterator *iter) +TreeDbTerm** catree_find_prev_root(CATreeRootIterator *iter, Eterm* keyp) { - return catree_find_nextprev_root(iter, 0); + return catree_find_nextprev_root(iter, 0, keyp); } @@ -1640,14 +1705,20 @@ TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, DbTableCATreeNode *rejected_base = NULL; #endif DbTableCATreeNode *node; + DbTableCATreeNode *parent; DbTableCATreeNode* next_route_node; + int current_level; ASSERT(!iter->locked_bnode); while (1) { node = GET_ROOT_ACQB(iter->tb); + current_level = 0; + parent = NULL; next_route_node = NULL; while (!node->is_base_node) { + current_level++; + parent = node; if (cmp_partly_bound(key, GET_ROUTE_NODE_KEY(node)) >= 0) { next_route_node = node; node = GET_RIGHT_ACQB(node); @@ -1656,18 +1727,12 @@ TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, } } ASSERT(node != rejected_base); - lock_iter_base_node(iter, &node->u.base); + lock_iter_base_node(iter, node, parent, current_level); if (node->u.base.is_valid) { - if (node->u.base.root || !next_route_node) { - iter->next_route_key = (next_route_node ? - next_route_node->u.route.key.term : - THE_NON_VALUE); - iter->locked_bnode = &node->u.base; - return &node->u.base.root; - } - unlock_iter_base_node(iter); - iter->next_route_key = next_route_node->u.route.key.term; - return catree_find_prev_root(iter); + iter->next_route_key = (next_route_node ? + next_route_node->u.route.key.term : + THE_NON_VALUE); + return &node->u.base.root; } /* Retry */ unlock_iter_base_node(iter); @@ -1685,21 +1750,23 @@ static TreeDbTerm** catree_find_firstlast_root(CATreeRootIterator* iter, #endif DbTableCATreeNode *node; DbTableCATreeNode* next_route_node; + int current_level; while (1) { node = GET_ROOT_ACQB(iter->tb); + current_level = 0; next_route_node = NULL; while (!node->is_base_node) { + current_level++; next_route_node = node; node = first ? GET_LEFT_ACQB(node) : GET_RIGHT_ACQB(node); } ASSERT(node != rejected_base); - lock_iter_base_node(iter, &node->u.base); + lock_iter_base_node(iter, node, next_route_node, current_level); if (node->u.base.is_valid) { iter->next_route_key = (next_route_node ? next_route_node->u.route.key.term : THE_NON_VALUE); - iter->locked_bnode = &node->u.base; return &node->u.base.root; } /* Retry */ @@ -1792,8 +1859,7 @@ static int db_slot_catree(Process *p, DbTable *tbl, init_root_iterator(&tbl->catree, &iter, 1); result = db_slot_tree_common(p, tbl, *catree_find_first_root(&iter), slot_term, ret, NULL, &iter); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1808,9 +1874,7 @@ static int db_select_continue_catree(Process *p, init_root_iterator(&tbl->catree, &iter, 1); result = db_select_continue_tree_common(p, &tbl->common, continuation, ret, NULL, &iter); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); - + destroy_root_iterator(&iter); return result; } @@ -1823,8 +1887,7 @@ static int db_select_catree(Process *p, DbTable *tbl, Eterm tid, init_root_iterator(&tbl->catree, &iter, 1); result = db_select_tree_common(p, tbl, tid, pattern, reverse, ret, NULL, &iter); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1840,8 +1903,7 @@ static int db_select_count_continue_catree(Process *p, result = db_select_count_continue_tree_common(p, tbl, continuation, ret, NULL, &iter); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1854,9 +1916,7 @@ static int db_select_count_catree(Process *p, DbTable *tbl, Eterm tid, init_root_iterator(&tbl->catree, &iter, 1); result = db_select_count_tree_common(p, tbl, tid, pattern, ret, NULL, &iter); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); - + destroy_root_iterator(&iter); return result; } @@ -1871,8 +1931,7 @@ static int db_select_chunk_catree(Process *p, DbTable *tbl, Eterm tid, result = db_select_chunk_tree_common(p, tbl, tid, pattern, chunk_size, reversed, ret, NULL, &iter); - if (iter.locked_bnode) - runlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1890,8 +1949,7 @@ static int db_select_delete_continue_catree(Process *p, init_tree_stack(&stack, stack_array, 0); result = db_select_delete_continue_tree_common(p, tbl, continuation, ret, &stack, &iter); - if (iter.locked_bnode) - wunlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1908,8 +1966,7 @@ static int db_select_delete_catree(Process *p, DbTable *tbl, Eterm tid, result = db_select_delete_tree_common(p, tbl, tid, pattern, ret, &stack, &iter); - if (iter.locked_bnode) - wunlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1922,8 +1979,7 @@ static int db_select_replace_catree(Process *p, DbTable *tbl, Eterm tid, init_root_iterator(&tbl->catree, &iter, 0); result = db_select_replace_tree_common(p, tbl, tid, pattern, ret, NULL, &iter); - if (iter.locked_bnode) - wunlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1936,8 +1992,7 @@ static int db_select_replace_continue_catree(Process *p, DbTable *tbl, init_root_iterator(&tbl->catree, &iter, 0); result = db_select_replace_continue_tree_common(p, tbl, continuation, ret, NULL, &iter); - if (iter.locked_bnode) - wunlock_base_node(iter.locked_bnode); + destroy_root_iterator(&iter); return result; } @@ -1970,9 +2025,9 @@ static void db_print_catree(fmtfn_t to, void *to_arg, root = catree_find_first_root(&iter); do { db_print_tree_common(to, to_arg, show, *root, tbl); - root = catree_find_next_root(&iter); + root = catree_find_next_root(&iter, NULL); } while (root); - ASSERT(!iter.locked_bnode); + destroy_root_iterator(&iter); } /* Release all memory occupied by a single table */ @@ -2055,9 +2110,9 @@ static void db_foreach_offheap_catree(DbTable *tbl, root = catree_find_first_root(&iter); do { db_foreach_offheap_tree_common(*root, func, arg); - root = catree_find_next_root(&iter); + root = catree_find_next_root(&iter, NULL); } while (root); - ASSERT(!iter.locked_bnode); + destroy_root_iterator(&iter); } static int db_lookup_dbterm_catree(Process *p, DbTable *tbl, Eterm key, Eterm obj, @@ -2068,7 +2123,7 @@ static int db_lookup_dbterm_catree(Process *p, DbTable *tbl, Eterm key, Eterm ob ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(wlock_base_node,wunlock_base_node); res = db_lookup_dbterm_tree_common(p, tbl, &base_node->root, key, obj, handle, NULL); if (res == 0) { - ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_ADAPT_AND_UNLOCK_PART; + wunlock_adapt_base_node(tb, current_node, prev_node, current_level); } else { /* db_finalize_dbterm_catree will unlock */ handle->lck = prev_node; @@ -2083,10 +2138,8 @@ static void db_finalize_dbterm_catree(int cret, DbUpdateHandle *handle) DbTableCATree *tb = &(handle->tb->catree); DbTableCATreeNode *prev_node = handle->lck; DbTableCATreeNode *current_node = handle->lck2; - int current_level = handle->current_level; - DbTableCATreeBaseNode *base_node = ¤t_node->u.base; db_finalize_dbterm_tree_common(cret, handle, NULL); - ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_ADAPT_AND_UNLOCK_PART; + wunlock_adapt_base_node(tb, current_node, prev_node, handle->current_level); return; } @@ -2128,10 +2181,10 @@ void db_catree_force_split(DbTableCATree* tb, int on) init_root_iterator(tb, &iter, 1); root = catree_find_first_root(&iter); do { - iter.locked_bnode->lock_statistics = (on ? INT_MAX : 0); - root = catree_find_next_root(&iter); + iter.locked_bnode->u.base.lock_statistics = (on ? INT_MAX : 0); + root = catree_find_next_root(&iter, NULL); } while (root); - ASSERT(!iter.locked_bnode); + destroy_root_iterator(&iter); if (on) tb->common.status |= DB_CATREE_FORCE_SPLIT; diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h index feb6f27980..6913609bf8 100644 --- a/erts/emulator/beam/erl_db_catree.h +++ b/erts/emulator/beam/erl_db_catree.h @@ -95,8 +95,11 @@ typedef struct db_table_catree { typedef struct { DbTableCATree* tb; Eterm next_route_key; - DbTableCATreeBaseNode* locked_bnode; + DbTableCATreeNode* locked_bnode; + DbTableCATreeNode* bnode_parent; + int bnode_level; int read_only; + DbRouteKey* search_key; } CATreeRootIterator; @@ -109,9 +112,9 @@ TreeDbTerm** catree_find_root(Eterm key, CATreeRootIterator*); TreeDbTerm** catree_find_next_from_pb_key_root(Eterm key, CATreeRootIterator*); TreeDbTerm** catree_find_prev_from_pb_key_root(Eterm key, CATreeRootIterator*); -TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator*, int next); -TreeDbTerm** catree_find_next_root(CATreeRootIterator*); -TreeDbTerm** catree_find_prev_root(CATreeRootIterator*); +TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator*, int next, Eterm* keyp); +TreeDbTerm** catree_find_next_root(CATreeRootIterator*, Eterm* keyp); +TreeDbTerm** catree_find_prev_root(CATreeRootIterator*, Eterm* keyp); TreeDbTerm** catree_find_first_root(CATreeRootIterator*); TreeDbTerm** catree_find_last_root(CATreeRootIterator*); diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index 250d90e189..854b8d6329 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -1046,7 +1046,7 @@ int db_select_continue_tree_common(Process *p, if (iter) { iter->next_route_key = lastkey; - sc.common.root = catree_find_nextprev_root(iter, !!reverse != !!chunk_size); + sc.common.root = catree_find_nextprev_root(iter, !!reverse != !!chunk_size, NULL); } else sc.common.root = &((DbTableTree*)tb)->root; @@ -1354,7 +1354,7 @@ int db_select_count_continue_tree_common(Process *p, if (iter) { iter->next_route_key = lastkey; - sc.common.root = catree_find_prev_root(iter); + sc.common.root = catree_find_prev_root(iter, NULL); } else { sc.common.root = &tb->tree.root; @@ -1765,7 +1765,7 @@ int db_select_delete_continue_tree_common(Process *p, if (iter) { iter->next_route_key = lastkey; - sc.common.root = catree_find_prev_root(iter); + sc.common.root = catree_find_prev_root(iter, NULL); } else { sc.common.root = &tbl->tree.root; @@ -2001,7 +2001,7 @@ int db_select_replace_continue_tree_common(Process *p, if (iter) { iter->next_route_key = lastkey; - sc.common.root = catree_find_prev_root(iter); + sc.common.root = catree_find_prev_root(iter, NULL); } else { sc.common.root = &tbl->tree.root; @@ -2734,8 +2734,22 @@ static TreeDbTerm *slot_search(Process *p, TreeDbTerm *root, { TreeDbTerm *this; TreeDbTerm *tmp; + TreeDbTerm *lastobj; + Eterm lastkey; TreeDbTerm **pp; - DbTreeStack* stack = get_any_stack(tb,stack_container); + DbTreeStack* stack; + + if (iter) { + /* Find first non-empty tree */ + while (!root) { + TreeDbTerm** pp = catree_find_next_root(iter, NULL); + if (!pp) + return NULL; + root = *pp; + } + } + + stack = get_any_stack(tb,stack_container); ASSERT(stack != NULL); if (slot == 1) { /* Don't search from where we are if we are @@ -2762,6 +2776,7 @@ static TreeDbTerm *slot_search(Process *p, TreeDbTerm *root, this = TOP_NODE(stack); while (stack->slot != slot) { ASSERT(this); + lastobj = this; if (slot > stack->slot) { if (this->right != NULL) { this = this->right; @@ -2810,14 +2825,19 @@ next_root: if (!iter) break; /* EOT */ - pp = catree_find_next_root(iter); + ASSERT(slot > stack->slot); + if (lastobj) { + lastkey = GETKEY(tb, lastobj->dbterm.tpl); + lastobj = NULL; + } + pp = catree_find_next_root(iter, &lastkey); if (!pp) break; /* EOT */ root = *pp; stack->pos = 0; + find_next(&tb->common, root, stack, lastkey); } - release_stack(tb,stack_container,stack); return this; } @@ -2952,7 +2972,8 @@ static TreeDbTerm *find_next_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, if (iter) { *rootpp = catree_find_next_from_pb_key_root(key, iter); - root = *rootpp ? **rootpp : NULL; + ASSERT(*rootpp); + root = **rootpp; } else { *rootpp = &tbl->tree.root; @@ -2991,7 +3012,8 @@ static TreeDbTerm *find_prev_from_pb_key(DbTable *tbl, TreeDbTerm*** rootpp, if (iter) { *rootpp = catree_find_prev_from_pb_key_root(key, iter); - root = *rootpp ? **rootpp : NULL; + ASSERT(*rootpp); + root = **rootpp; } else { *rootpp = &tbl->tree.root; @@ -3212,36 +3234,45 @@ static void traverse_backwards(DbTableCommon *tb, TreeDbTerm *this, *next; TreeDbTerm** root = context->root; - do { - if (lastkey == THE_NON_VALUE) { - stack->pos = stack->slot = 0; - if (( this = *root ) == NULL) { - goto next_root; - } - while (this != NULL) { - PUSH_NODE(stack, this); - this = this->right; + if (lastkey == THE_NON_VALUE) { + if (iter) { + while (*root == NULL) { + root = catree_find_prev_root(iter, NULL); + if (!root) + return; } - this = TOP_NODE(stack); - next = find_prev(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); - if (!((*doit)(tb, this, context, 0))) - return; - } else { - next = find_prev(tb, *root, stack, lastkey); + context->root = root; } + stack->pos = stack->slot = 0; + next = *root; + while (next != NULL) { + PUSH_NODE(stack, next); + next = next->right; + } + next = TOP_NODE(stack); + } else { + next = find_prev(tb, *root, stack, lastkey); + } - while ((this = next) != NULL) { - next = find_prev(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); + while (1) { + while (next) { + this = next; + lastkey = GETKEY(tb, this->dbterm.tpl); + next = find_prev(tb, *root, stack, lastkey); if (!((*doit)(tb, this, context, 0))) return; } -next_root: if (!iter) return; - root = context->root = catree_find_prev_root(iter); - lastkey = THE_NON_VALUE; - } while (root); + ASSERT(is_value(lastkey)); + root = catree_find_prev_root(iter, &lastkey); + if (!root) + return; + context->root = root; + stack->pos = stack->slot = 0; + next = find_prev(tb, *root, stack, lastkey); + } } /* @@ -3257,36 +3288,45 @@ static void traverse_forward(DbTableCommon *tb, TreeDbTerm *this, *next; TreeDbTerm **root = context->root; - do { - if (lastkey == THE_NON_VALUE) { - stack->pos = stack->slot = 0; - if (( this = *root ) == NULL) { - goto next_root; + if (lastkey == THE_NON_VALUE) { + if (iter) { + while (*root == NULL) { + root = catree_find_next_root(iter, NULL); + if (!root) + return; } - while (this != NULL) { - PUSH_NODE(stack, this); - this = this->left; - } - this = TOP_NODE(stack); - next = find_next(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); - if (!((*doit)(tb, this, context, 1))) - return; - } else { - next = find_next(tb, *root, stack, lastkey); + context->root = root; } + stack->pos = stack->slot = 0; + next = *root; + while (next != NULL) { + PUSH_NODE(stack, next); + next = next->left; + } + next = TOP_NODE(stack); + } else { + next = find_next(tb, *root, stack, lastkey); + } - while ((this = next) != NULL) { - next = find_next(tb, *root, stack, GETKEY(tb, this->dbterm.tpl)); + while (1) { + while (next) { + this = next; + lastkey = GETKEY(tb, this->dbterm.tpl); + next = find_next(tb, *root, stack, lastkey); if (!((*doit)(tb, this, context, 1))) return; } -next_root: if (!iter) return; - root = context->root = catree_find_next_root(iter); - lastkey = THE_NON_VALUE; - } while(root); + ASSERT(is_value(lastkey)); + root = catree_find_next_root(iter, &lastkey); + if (!root) + return; + context->root = root; + stack->pos = stack->slot = 0; + next = find_next(tb, *root, stack, lastkey); + } } /* @@ -3306,44 +3346,51 @@ static void traverse_update_backwards(DbTableCommon *tb, TreeDbTerm *this, *next, **this_ptr; TreeDbTerm** root = context->root; - do { - if (lastkey == THE_NON_VALUE) { - stack->pos = stack->slot = 0; - if (( this = *root ) == NULL) { - goto next_root; + if (lastkey == THE_NON_VALUE) { + if (iter) { + while (*root == NULL) { + root = catree_find_prev_root(iter, NULL); + if (!root) + return; + context->root = root; } - while (this != NULL) { - PUSH_NODE(stack, this); - this = this->right; - } - this = TOP_NODE(stack); - this_ptr = find_ptr(tb, root, stack, this); - ASSERT(this_ptr != NULL); - res = (*doit)(tb, this_ptr, context, 0); - REPLACE_TOP_NODE(stack, *this_ptr); - next = find_prev(tb, *root, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl)); - if (!res) - return; - } else { - next = find_prev(tb, *root, stack, lastkey); } + stack->pos = stack->slot = 0; + next = *root; + while (next) { + PUSH_NODE(stack, next); + next = next->right; + } + next = TOP_NODE(stack); + } + else + next = find_prev(tb, *root, stack, lastkey); - while ((this = next) != NULL) { + + while (1) { + while (next) { + this = next; this_ptr = find_ptr(tb, root, stack, this); ASSERT(this_ptr != NULL); res = (*doit)(tb, this_ptr, context, 0); - REPLACE_TOP_NODE(stack, *this_ptr); - next = find_prev(tb, *root, stack, GETKEY(tb, (*this_ptr)->dbterm.tpl)); + this = *this_ptr; + REPLACE_TOP_NODE(stack, this); if (!res) return; + lastkey = GETKEY(tb, this->dbterm.tpl); + next = find_prev(tb, *root, stack, lastkey); } -next_root: if (!iter) return; - root = context->root = catree_find_prev_root(iter); - lastkey = THE_NON_VALUE; - } while (root); + ASSERT(is_value(lastkey)); + root = catree_find_prev_root(iter, &lastkey); + if (!root) + return; + context->root = root; + stack->pos = stack->slot = 0; + next = find_prev(tb, *root, stack, lastkey); + } } static enum ms_key_boundness key_boundness(DbTableCommon *tb, -- cgit v1.2.3 From 43499e6ab183a44a979d4fb5c80b5a3603e1bbd9 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 19 Oct 2018 17:35:51 +0200 Subject: erts: Fix lc_key in base nodes to actually pass the copy to lock checker. --- erts/emulator/beam/erl_db_catree.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 072858f3f5..5069e1e531 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -855,7 +855,7 @@ DbTableCATreeNode* find_base_node(DbTableCATree* tb, Eterm key, static ERTS_INLINE -void copy_route_key(DbRouteKey* dst, Eterm key, Uint key_size) +Eterm copy_route_key(DbRouteKey* dst, Eterm key, Uint key_size) { dst->size = key_size; if (key_size != 0) { @@ -870,6 +870,7 @@ void copy_route_key(DbRouteKey* dst, Eterm key, Uint key_size) dst->term = key; dst->oh = NULL; } + return dst->term; } static ERTS_INLINE @@ -914,7 +915,7 @@ static DbTableCATreeNode *create_base_node(DbTableCATree *tb, rwmtx_opt.main_spincount = erts_ets_rwmtx_spin_count; #ifdef ERTS_ENABLE_LOCK_CHECK - copy_route_key(&p->u.base.lc_key, lc_key, lc_key_size); + lc_key = copy_route_key(&p->u.base.lc_key, lc_key, lc_key_size); #endif erts_rwmtx_init_opt(&p->u.base.lock, &rwmtx_opt, "erl_db_catree_base_node", @@ -1613,8 +1614,7 @@ static Eterm copy_iter_search_key(CATreeRootIterator* iter, Eterm key) (offsetof(DbRouteKey, heap) + key_size*sizeof(Eterm))); } - copy_route_key(iter->search_key, key, key_size); - return iter->search_key->term; + return copy_route_key(iter->search_key, key, key_size); } TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, -- cgit v1.2.3 From be9fd1bfaa30ba25b6d3a3a39159c81172964010 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 19 Oct 2018 17:40:21 +0200 Subject: erts: Fix slot bug in find_next/prev --- erts/emulator/beam/erl_db_tree.c | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index 854b8d6329..f5fac9dcb6 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -2872,7 +2872,7 @@ static TreeDbTerm *find_next(DbTableCommon *tb, TreeDbTerm *root, this = this->right; } else if (c < 0) { if (this->left == NULL) /* Done */ - return this; + goto found_next; else this = this->left; } else @@ -2887,8 +2887,6 @@ static TreeDbTerm *find_next(DbTableCommon *tb, TreeDbTerm *root, this = this->left; PUSH_NODE(stack, this); } - if (stack->slot > 0) - ++(stack->slot); } else { do { tmp = POP_NODE(stack); @@ -2897,9 +2895,12 @@ static TreeDbTerm *find_next(DbTableCommon *tb, TreeDbTerm *root, return NULL; } } while (this->right == tmp); - if (stack->slot > 0) - ++(stack->slot); } + +found_next: + if (stack->slot > 0) + ++(stack->slot); + return this; } @@ -2929,7 +2930,7 @@ static TreeDbTerm *find_prev(DbTableCommon *tb, TreeDbTerm *root, this = this->left; } else if (c > 0) { if (this->right == NULL) /* Done */ - return this; + goto found_prev; else this = this->right; } else @@ -2944,8 +2945,6 @@ static TreeDbTerm *find_prev(DbTableCommon *tb, TreeDbTerm *root, this = this->right; PUSH_NODE(stack, this); } - if (stack->slot > 0) - --(stack->slot); } else { do { tmp = POP_NODE(stack); @@ -2954,9 +2953,12 @@ static TreeDbTerm *find_prev(DbTableCommon *tb, TreeDbTerm *root, return NULL; } } while (this->left == tmp); - if (stack->slot > 0) - --(stack->slot); } + +found_prev: + if (stack->slot > 0) + --(stack->slot); + return this; } -- cgit v1.2.3 From 822b60430eeae0ae32aca52019762566fec1acce Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 19 Oct 2018 20:08:22 +0200 Subject: erts: Provoke random catree split/join for DEBUG emulator --- erts/emulator/beam/erl_db_catree.c | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 5069e1e531..c3bebefbdf 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -630,6 +630,31 @@ static TreeDbTerm* join_trees(TreeDbTerm *left_root_param, } } +#ifdef DEBUG +# define FORCE_RANDOM_SPLIT_JOIN +#endif +#ifdef FORCE_RANDOM_SPLIT_JOIN +static int dbg_fastrand(void) +{ + static int g_seed = 648835; + g_seed = (214013*g_seed+2531011); + return (g_seed>>16)&0x7FFF; +} + +static void dbg_maybe_force_splitjoin(DbTableCATreeNode* base_node) +{ + switch (dbg_fastrand() % 8) { + case 1: + base_node->u.base.lock_statistics = 1+ERL_DB_CATREE_HIGH_CONTENTION_LIMIT; + break; + case 2: + base_node->u.base.lock_statistics = -1+ERL_DB_CATREE_LOW_CONTENTION_LIMIT; + break; + } +} +#else +# define dbg_maybe_force_splitjoin(N) +#endif /* FORCE_RANDOM_SPLIT_JOIN */ static ERTS_INLINE int try_wlock_base_node(DbTableCATreeBaseNode *base_node) @@ -676,6 +701,7 @@ void wunlock_adapt_base_node(DbTableCATree* tb, DbTableCATreeNode* parent, int current_level) { + dbg_maybe_force_splitjoin(base_node); if (base_node->u.base.lock_statistics > ERL_DB_CATREE_HIGH_CONTENTION_LIMIT && current_level < ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT) { split_catree(tb, base_node, parent); -- cgit v1.2.3 From de75be217596ec07ea42b03b701430cf2ae5260a Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 22 Oct 2018 16:06:51 +0200 Subject: erts: Fix faulty assert in catree_find_nextprev_root It's possible to first find an empty base node and then retry and find the same base node as invalid. It's a benign race with join which first makes the old invalid 'neighbor' accessible from 'gparent' before replacing it with 'new_neighbor'. --- erts/emulator/beam/erl_db_catree.c | 19 ++++++++++++++----- 1 file changed, 14 insertions(+), 5 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index c3bebefbdf..bc058dcf18 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -96,6 +96,12 @@ #include "erl_db_tree.h" #include "erl_db_tree_util.h" +#ifdef DEBUG +# define IF_DEBUG(X) X +#else +# define IF_DEBUG(X) +#endif + /* ** Forward declarations */ @@ -1647,7 +1653,8 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, Eterm *keyp) { #ifdef DEBUG - DbTableCATreeNode *rejected_base = NULL; + DbTableCATreeNode *rejected_invalid = NULL; + DbTableCATreeNode *rejected_empty = NULL; #endif DbTableCATreeNode *node; DbTableCATreeNode *parent; @@ -1689,9 +1696,10 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, } } } - ASSERT(node != rejected_base); + ASSERT(node != rejected_invalid); lock_iter_base_node(iter, node, parent, current_level); if (node->u.base.is_valid) { + ASSERT(node != rejected_empty); if (node->u.base.root) { iter->next_route_key = (next_route_node ? next_route_node->u.route.key.term : @@ -1704,12 +1712,13 @@ TreeDbTerm** catree_find_nextprev_root(CATreeRootIterator *iter, int next, return NULL; } key = next_route_node->u.route.key.term; + IF_DEBUG(rejected_empty = node); } + else + IF_DEBUG(rejected_invalid = node); + /* Retry */ unlock_iter_base_node(iter); -#ifdef DEBUG - rejected_base = node; -#endif } } -- cgit v1.2.3 From 8f2dfc574968c9d0e8484e5e87940579806815db Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 22 Oct 2018 19:58:26 +0200 Subject: erts: Refactor away function generating macros in erl_db_catree.c Easier to read and debug, and about the same lines of code. --- erts/emulator/beam/erl_db_catree.c | 236 +++++++++++++++---------------------- 1 file changed, 93 insertions(+), 143 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index bc058dcf18..756f188983 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -568,14 +568,14 @@ static TreeDbTerm* join_trees(TreeDbTerm *left_root_param, p = *this; if (dir == DIR_LEFT) { switch (p->balance) { - case 1: + case 1: p->balance = 0; state = 0; break; - case 0: + case 0: p->balance = -1; break; - case -1: /* The icky case */ + case -1: /* The icky case */ p1 = p->left; if (p1->balance == -1) { /* Single LL rotation */ p->left = p1->right; @@ -598,14 +598,14 @@ static TreeDbTerm* join_trees(TreeDbTerm *left_root_param, } } else { /* dir == DIR_RIGHT */ switch (p->balance) { - case -1: + case -1: p->balance = 0; state = 0; break; - case 0: + case 0: p->balance = 1; break; - case 1: + case 1: p1 = p->right; if (p1->balance == 1) { /* Single RR rotation */ p->right = p1->left; @@ -800,12 +800,6 @@ void destroy_root_iterator(CATreeRootIterator* iter) erts_free(ERTS_ALC_T_DB_TMP, iter->search_key); } -/* - * The following macros are used to create the ETS functions that only - * need to access one element (e.g. db_put_catree, db_get_catree and - * db_erase_catree). - */ - typedef struct { @@ -818,11 +812,15 @@ DbTableCATreeNode* find_base_node(DbTableCATree* tb, Eterm key, FindBaseNode* fbn) { DbTableCATreeNode* ERTS_RESTRICT node = GET_ROOT_ACQB(tb); - fbn->parent = NULL; - fbn->current_level = 0; + if (fbn) { + fbn->parent = NULL; + fbn->current_level = 0; + } while (!node->is_base_node) { - fbn->current_level++; - fbn->parent = node; + if (fbn) { + fbn->current_level++; + fbn->parent = node; + } if (cmp_key_route(key, node) < 0) { node = GET_LEFT_ACQB(node); } else { @@ -832,59 +830,36 @@ DbTableCATreeNode* find_base_node(DbTableCATree* tb, Eterm key, return node; } -#define ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(LOCK,UNLOCK) \ - int retry; \ - DbTableCATreeNode *current_node; \ - DbTableCATreeNode *prev_node; \ - DbTableCATreeBaseNode *base_node; \ - int current_level; \ - (void)prev_node; \ - do { \ - retry = 0; \ - current_node = GET_ROOT_ACQB(tb); \ - prev_node = NULL; \ - current_level = 0; \ - while ( ! current_node->is_base_node ) { \ - current_level = current_level + 1; \ - prev_node = current_node; \ - if (cmp_key_route(key,current_node) < 0) { \ - current_node = GET_LEFT_ACQB(current_node); \ - } else { \ - current_node = GET_RIGHT_ACQB(current_node); \ - } \ - } \ - base_node = ¤t_node->u.base; \ - LOCK(current_node); \ - if ( ! base_node->is_valid ) { \ - /* Retry */ \ - UNLOCK(current_node); \ - retry = 1; \ - } \ - } while(retry); - -#define ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION(FUN_POSTFIX,PARAMETERS,SEQUENTAIL_CALL) \ - static int erl_db_catree_do_operation_##FUN_POSTFIX(DbTableCATree *tb, \ - Eterm key, \ - PARAMETERS){ \ - int result; \ - ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(wlock_base_node,wunlock_base_node) \ - result = SEQUENTAIL_CALL; \ - wunlock_adapt_base_node(tb, current_node, prev_node, current_level);\ - return result; \ +static ERTS_INLINE +DbTableCATreeNode* find_rlock_valid_base_node(DbTableCATree* tb, Eterm key) +{ + DbTableCATreeNode* base_node; + + while (1) { + base_node = find_base_node(tb, key, NULL); + rlock_base_node(base_node); + if (base_node->u.base.is_valid) + break; + runlock_base_node(base_node); } + return base_node; +} +static ERTS_INLINE +DbTableCATreeNode* find_wlock_valid_base_node(DbTableCATree* tb, Eterm key, + FindBaseNode* fbn) +{ + DbTableCATreeNode* base_node; -#define ERL_DB_CATREE_CREATE_DO_READ_OPERATION_FUNCTION(FUN_POSTFIX,PARAMETERS,SEQUENTAIL_CALL) \ - static int erl_db_catree_do_operation_##FUN_POSTFIX(DbTableCATree *tb, \ - Eterm key, \ - PARAMETERS){ \ - int result; \ - ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(rlock_base_node,runlock_base_node) \ - result = SEQUENTAIL_CALL; \ - runlock_base_node(current_node); \ - return result; \ + while (1) { + base_node = find_base_node(tb, key, fbn); + wlock_base_node(base_node); + if (base_node->u.base.is_valid) + break; + wunlock_base_node(base_node); } - + return base_node; +} static ERTS_INLINE Eterm copy_route_key(DbRouteKey* dst, Eterm key, Uint key_size) @@ -1534,40 +1509,29 @@ static int db_prev_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) return result; } -#define ERL_DB_CATREE_DO_OPERATION_PUT_PARAMS Eterm obj, int key_clash_fail -ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION(put, - ERL_DB_CATREE_DO_OPERATION_PUT_PARAMS, - db_put_tree_common(&tb->common, - &base_node->root, - obj, - key_clash_fail, - NULL);) - static int db_put_catree(DbTable *tbl, Eterm obj, int key_clash_fail) { DbTableCATree *tb = &tbl->catree; Eterm key = GETKEY(&tb->common, tuple_val(obj)); - return erl_db_catree_do_operation_put(tb, - key, - obj, - key_clash_fail); + FindBaseNode fbn; + DbTableCATreeNode* node = find_wlock_valid_base_node(tb, key, &fbn); + int result = db_put_tree_common(&tb->common, &node->u.base.root, obj, + key_clash_fail, NULL); + wunlock_adapt_base_node(tb, node, fbn.parent, fbn.current_level); + return result; } -#define ERL_DB_CATREE_DO_OPERATION_GET_PARAMS Process *p, Eterm *ret -ERL_DB_CATREE_CREATE_DO_READ_OPERATION_FUNCTION(get, - ERL_DB_CATREE_DO_OPERATION_GET_PARAMS, - db_get_tree_common(p, &tb->common, - base_node->root, - key, ret, NULL);) - static int db_get_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) { DbTableCATree *tb = &tbl->catree; - return erl_db_catree_do_operation_get(tb, key, p, ret); + DbTableCATreeNode* node = find_rlock_valid_base_node(tb, key); + int result = db_get_tree_common(p, &tb->common, + node->u.base.root, + key, ret, NULL); + runlock_base_node(node); + return result; } - - TreeDbTerm** catree_find_root(Eterm key, CATreeRootIterator* iter) { FindBaseNode fbn; @@ -1822,66 +1786,53 @@ TreeDbTerm** catree_find_last_root(CATreeRootIterator* iter) return catree_find_firstlast_root(iter, 0); } - -#define ERL_DB_CATREE_DO_OPERATION_MEMBER_PARAMS Eterm *ret -ERL_DB_CATREE_CREATE_DO_READ_OPERATION_FUNCTION(member, - ERL_DB_CATREE_DO_OPERATION_MEMBER_PARAMS, - db_member_tree_common(&tb->common, - base_node->root, - key, - ret, - NULL);) - static int db_member_catree(DbTable *tbl, Eterm key, Eterm *ret) { DbTableCATree *tb = &tbl->catree; - return erl_db_catree_do_operation_member(tb, key, ret); + DbTableCATreeNode* node = find_rlock_valid_base_node(tb, key); + int result = db_member_tree_common(&tb->common, + node->u.base.root, + key, ret, NULL); + runlock_base_node(node); + return result; } -#define ERL_DB_CATREE_DO_OPERATION_GET_ELEMENT_PARAMS Process *p, int ndex, Eterm *ret -ERL_DB_CATREE_CREATE_DO_READ_OPERATION_FUNCTION(get_element, - ERL_DB_CATREE_DO_OPERATION_GET_ELEMENT_PARAMS, - db_get_element_tree_common(p, &tb->common, - base_node->root, - key, ndex, - ret, NULL)) - static int db_get_element_catree(Process *p, DbTable *tbl, Eterm key, int ndex, Eterm *ret) { DbTableCATree *tb = &tbl->catree; - return erl_db_catree_do_operation_get_element(tb, key, p, ndex, ret); + DbTableCATreeNode* node = find_rlock_valid_base_node(tb, key); + int result = db_get_element_tree_common(p, &tb->common, + node->u.base.root, + key, ndex, ret, NULL); + runlock_base_node(node); + return result; } -#define ERL_DB_CATREE_DO_OPERATION_ERASE_PARAMS DbTable *tbl, Eterm *ret -ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION(erase, - ERL_DB_CATREE_DO_OPERATION_ERASE_PARAMS, - db_erase_tree_common(tbl, - &base_node->root, - key, - ret, - NULL);) - static int db_erase_catree(DbTable *tbl, Eterm key, Eterm *ret) { DbTableCATree *tb = &tbl->catree; - return erl_db_catree_do_operation_erase(tb, key, tbl, ret); + FindBaseNode fbn; + DbTableCATreeNode* node = find_wlock_valid_base_node(tb, key, &fbn); + int result = db_erase_tree_common(tbl, &node->u.base.root, key, + ret, NULL); + wunlock_adapt_base_node(tb, node, fbn.parent, fbn.current_level); + return result; } -#define ERL_DB_CATREE_DO_OPERATION_ERASE_OBJECT_PARAMS DbTable *tbl, Eterm object, Eterm *ret -ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION(erase_object, - ERL_DB_CATREE_DO_OPERATION_ERASE_OBJECT_PARAMS, - db_erase_object_tree_common(tbl, - &base_node->root, - object, - ret, - NULL);) - static int db_erase_object_catree(DbTable *tbl, Eterm object, Eterm *ret) { DbTableCATree *tb = &tbl->catree; Eterm key = GETKEY(&tb->common, tuple_val(object)); - return erl_db_catree_do_operation_erase_object(tb, key, tbl, object, ret); + FindBaseNode fbn; + DbTableCATreeNode* node = find_wlock_valid_base_node(tb, key, &fbn); + int result = db_erase_object_tree_common(tbl, + &node->u.base.root, + object, + ret, + NULL); + wunlock_adapt_base_node(tb, node, fbn.parent, fbn.current_level); + return result; } @@ -2031,17 +1982,15 @@ static int db_select_replace_continue_catree(Process *p, DbTable *tbl, return result; } -#define ERL_DB_CATREE_DO_OPERATION_TAKE_PARAMS Process *p, Eterm *ret, DbTable *tbl -ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION(take, - ERL_DB_CATREE_DO_OPERATION_TAKE_PARAMS, - db_take_tree_common(p, tbl, - &base_node->root, - key, ret, NULL);) - static int db_take_catree(Process *p, DbTable *tbl, Eterm key, Eterm *ret) { DbTableCATree *tb = &tbl->catree; - return erl_db_catree_do_operation_take(tb, key, p, ret, tbl); + FindBaseNode fbn; + DbTableCATreeNode* node = find_wlock_valid_base_node(tb, key, &fbn); + int result = db_take_tree_common(p, tbl, &node->u.base.root, key, + ret, NULL); + wunlock_adapt_base_node(tb, node, fbn.parent, fbn.current_level); + return result; } /* @@ -2154,16 +2103,17 @@ static int db_lookup_dbterm_catree(Process *p, DbTable *tbl, Eterm key, Eterm ob DbUpdateHandle *handle) { DbTableCATree *tb = &tbl->catree; - int res; - ERL_DB_CATREE_CREATE_DO_OPERATION_FUNCTION_FIND_BASE_NODE_PART(wlock_base_node,wunlock_base_node); - res = db_lookup_dbterm_tree_common(p, tbl, &base_node->root, key, obj, handle, NULL); + FindBaseNode fbn; + DbTableCATreeNode* node = find_wlock_valid_base_node(tb, key, &fbn); + int res = db_lookup_dbterm_tree_common(p, tbl, &node->u.base.root, key, + obj, handle, NULL); if (res == 0) { - wunlock_adapt_base_node(tb, current_node, prev_node, current_level); + wunlock_adapt_base_node(tb, node, fbn.parent, fbn.current_level); } else { /* db_finalize_dbterm_catree will unlock */ - handle->lck = prev_node; - handle->lck2 = current_node; - handle->current_level = current_level; + handle->lck = fbn.parent; + handle->lck2 = node; + handle->current_level = fbn.current_level; } return res; } -- cgit v1.2.3 From 3dc37254016825d027f8e3c7fac0a0f32d0d57e0 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 22 Oct 2018 20:21:49 +0200 Subject: erts: Refactor DbUpdateHandle with nicer types --- erts/emulator/beam/erl_db_catree.c | 12 ++++++------ erts/emulator/beam/erl_db_hash.c | 4 ++-- erts/emulator/beam/erl_db_util.h | 13 ++++++++++--- 3 files changed, 18 insertions(+), 11 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 756f188983..5d88c61144 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -2111,9 +2111,9 @@ static int db_lookup_dbterm_catree(Process *p, DbTable *tbl, Eterm key, Eterm ob wunlock_adapt_base_node(tb, node, fbn.parent, fbn.current_level); } else { /* db_finalize_dbterm_catree will unlock */ - handle->lck = fbn.parent; - handle->lck2 = node; - handle->current_level = fbn.current_level; + handle->u.catree.base_node = node; + handle->u.catree.parent = fbn.parent; + handle->u.catree.current_level = fbn.current_level; } return res; } @@ -2121,10 +2121,10 @@ static int db_lookup_dbterm_catree(Process *p, DbTable *tbl, Eterm key, Eterm ob static void db_finalize_dbterm_catree(int cret, DbUpdateHandle *handle) { DbTableCATree *tb = &(handle->tb->catree); - DbTableCATreeNode *prev_node = handle->lck; - DbTableCATreeNode *current_node = handle->lck2; db_finalize_dbterm_tree_common(cret, handle, NULL); - wunlock_adapt_base_node(tb, current_node, prev_node, handle->current_level); + wunlock_adapt_base_node(tb, handle->u.catree.base_node, + handle->u.catree.parent, + handle->u.catree.current_level); return; } diff --git a/erts/emulator/beam/erl_db_hash.c b/erts/emulator/beam/erl_db_hash.c index 61806876a7..f05a3b51c9 100644 --- a/erts/emulator/beam/erl_db_hash.c +++ b/erts/emulator/beam/erl_db_hash.c @@ -3103,7 +3103,7 @@ Ldone: handle->dbterm = &b->dbterm; handle->flags = flags; handle->new_size = b->dbterm.size; - handle->lck = lck; + handle->u.hash.lck = lck; return 1; } @@ -3116,7 +3116,7 @@ db_finalize_dbterm_hash(int cret, DbUpdateHandle* handle) DbTableHash *tb = &tbl->hash; HashDbTerm **bp = (HashDbTerm **) handle->bp; HashDbTerm *b = *bp; - erts_rwmtx_t* lck = (erts_rwmtx_t*) handle->lck; + erts_rwmtx_t* lck = handle->u.hash.lck; HashDbTerm* free_me = NULL; ERTS_LC_ASSERT(IS_HASH_WLOCKED(tb, lck)); /* locked by db_lookup_dbterm_hash */ diff --git a/erts/emulator/beam/erl_db_util.h b/erts/emulator/beam/erl_db_util.h index dcffaf9718..e1af9210ea 100644 --- a/erts/emulator/beam/erl_db_util.h +++ b/erts/emulator/beam/erl_db_util.h @@ -89,9 +89,16 @@ typedef struct { void** bp; /* {Hash|Tree}DbTerm** */ Uint new_size; int flags; - void* lck; - void* lck2; - int current_level; + union { + struct { + erts_rwmtx_t* lck; + } hash; + struct { + struct DbTableCATreeNode* base_node; + struct DbTableCATreeNode* parent; + int current_level; + } catree; + } u; } DbUpdateHandle; -- cgit v1.2.3 From 13214aae3697d27d27d5c628997fd4a92b497f89 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 25 Oct 2018 13:35:12 +0200 Subject: erts: Join empty base nodes in catree The original implementation did not do this due to fear of bad performance. But we think the negative effect of "leaking" empty base nodes is more important to fix. To get the bad performance a special kind of access patterns is needed where base nodes are frequently emptied and then repopulated soon again. ets_SUITE:throughput_benchmark for example did not show any negative effect from this commit at all. --- erts/emulator/beam/erl_db_catree.c | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 5d88c61144..1cd01e7e33 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -703,20 +703,22 @@ void wunlock_base_node(DbTableCATreeNode *base_node) static ERTS_INLINE void wunlock_adapt_base_node(DbTableCATree* tb, - DbTableCATreeNode* base_node, + DbTableCATreeNode* node, DbTableCATreeNode* parent, int current_level) { - dbg_maybe_force_splitjoin(base_node); - if (base_node->u.base.lock_statistics > ERL_DB_CATREE_HIGH_CONTENTION_LIMIT - && current_level < ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT) { - split_catree(tb, base_node, parent); + dbg_maybe_force_splitjoin(node); + if ((!node->u.base.root && parent && !(tb->common.status + & DB_CATREE_FORCE_SPLIT)) + || node->u.base.lock_statistics < ERL_DB_CATREE_LOW_CONTENTION_LIMIT) { + join_catree(tb, node, parent); } - else if (base_node->u.base.lock_statistics < ERL_DB_CATREE_LOW_CONTENTION_LIMIT) { - join_catree(tb, base_node, parent); + else if (node->u.base.lock_statistics > ERL_DB_CATREE_HIGH_CONTENTION_LIMIT + && current_level < ERL_DB_CATREE_MAX_ROUTE_NODE_LAYER_HEIGHT) { + split_catree(tb, node, parent); } else { - wunlock_base_node(base_node); + wunlock_base_node(node); } } -- cgit v1.2.3 From d86aa04dbab03b9e5d6f74ac44e4e52e41ab2f91 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 25 Oct 2018 17:56:26 +0200 Subject: erts: Fix bug in lock checker for term comparison --- erts/emulator/beam/erl_lock_check.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_lock_check.c b/erts/emulator/beam/erl_lock_check.c index 018c82aabb..edcfcb4cd7 100644 --- a/erts/emulator/beam/erl_lock_check.c +++ b/erts/emulator/beam/erl_lock_check.c @@ -1205,7 +1205,7 @@ void erts_lc_lock_flg_x(erts_lc_lock_t *lck, erts_lock_options_t options, thr->locked.last->next = new_ll; thr->locked.last = new_ll; } - else if (thr->locked.last->id == lck->id && thr->locked.last->extra == lck->extra) + else if (order == 0) lock_twice("Locking", thr, lck, options); else lock_order_violation(thr, lck); -- cgit v1.2.3 From 15f8ca326070dde083bd59618d4b77c24dde06a5 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 25 Oct 2018 18:06:30 +0200 Subject: erts: Let lock checker allow trylock of same order for different lock instances. --- erts/emulator/beam/erl_lock_check.c | 25 ++++++++++++++++--------- 1 file changed, 16 insertions(+), 9 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_lock_check.c b/erts/emulator/beam/erl_lock_check.c index edcfcb4cd7..394e19f2fa 100644 --- a/erts/emulator/beam/erl_lock_check.c +++ b/erts/emulator/beam/erl_lock_check.c @@ -194,6 +194,12 @@ struct lc_locked_lock_t_ { unsigned int line; erts_lock_flags_t flags; erts_lock_options_t taken_options; + /* + * Pointer back to the lock instance if it exists or NULL for proc locks. + * If set, we use it to allow trylock of other lock instance + * but with identical lock order as an already locked lock. + */ + erts_lc_lock_t *lck; }; typedef struct { @@ -407,6 +413,10 @@ new_locked_lock(lc_thread_t* thr, ll->line = line; ll->flags = lck->flags; ll->taken_options = options; + if ((lck->flags & ERTS_LOCK_FLAGS_MASK_TYPE) == ERTS_LOCK_FLAGS_TYPE_PROCLOCK) + ll->lck = NULL; + else + ll->lck = lck; return ll; } @@ -1005,17 +1015,14 @@ erts_lc_trylock_force_busy_flg(erts_lc_lock_t *lck, erts_lock_options_t options) */ /* Check that we are not trying to lock this lock twice */ - while (1) { - if (order <= 0) { - if (order == 0) - lock_twice("Trylocking", thr, lck, options); - break; - } + do { + if (order == 0 && (ll->lck == lck || !ll->lck)) + lock_twice("Trylocking", thr, lck, options); ll = ll->prev; if (!ll) break; order = compare_locked_by_id_extra(ll, lck); - } + } while (order >= 0); #ifndef ERTS_LC_ALLWAYS_FORCE_BUSY_TRYLOCK_ON_LOCK_ORDER_VIOLATION /* We only force busy if a lock order violation would occur @@ -1064,8 +1071,8 @@ void erts_lc_trylock_flg_x(int locked, erts_lc_lock_t *lck, erts_lock_options_t for (tl_lck = thr->locked.last; tl_lck; tl_lck = tl_lck->prev) { int order = compare_locked_by_id_extra(tl_lck, lck); if (order <= 0) { - if (order == 0) - lock_twice("Trylocking", thr, lck, options); + if (order == 0 && (tl_lck->lck == lck || !tl_lck->lck)) + lock_twice("Trylocking", thr, lck, options); if (locked) { ll->next = tl_lck->next; ll->prev = tl_lck; -- cgit v1.2.3 From dd2c35fbdc354d1897307a20a459f2b9178abb84 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 25 Oct 2018 18:18:09 +0200 Subject: erts: Remove lock ordering of catree base nodes We no longer lock more than one base node at a time. We do however trylock a second base node at join. --- erts/emulator/beam/erl_db_catree.c | 47 ++++++++++++------------------------- erts/emulator/beam/erl_db_catree.h | 3 --- erts/emulator/beam/erl_lock_check.c | 2 +- 3 files changed, 16 insertions(+), 36 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 1cd01e7e33..b52a4a53fe 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -894,27 +894,21 @@ void destroy_route_key(DbRouteKey* key) #ifdef ERTS_ENABLE_LOCK_CHECK -# define sizeof_base_node(KEY_SZ) \ - (offsetof(DbTableCATreeNode, u.base.lc_key.heap) \ - + (KEY_SZ)*sizeof(Eterm)) # define LC_ORDER(ORDER) ORDER #else -# define sizeof_base_node(KEY_SZ) \ - offsetof(DbTableCATreeNode, u.base.end_of_struct__) # define LC_ORDER(ORDER) NIL #endif +#define sizeof_base_node() \ + offsetof(DbTableCATreeNode, u.base.end_of_struct__) + static DbTableCATreeNode *create_base_node(DbTableCATree *tb, - TreeDbTerm* root, - Eterm lc_key) + TreeDbTerm* root) { DbTableCATreeNode *p; erts_rwmtx_opt_t rwmtx_opt = ERTS_RWMTX_OPT_DEFAULT_INITER; -#ifdef ERTS_ENABLE_LOCK_CHECK - Eterm lc_key_size = size_object(lc_key); -#endif p = erts_db_alloc(ERTS_ALC_T_DB_TABLE, (DbTable *) tb, - sizeof_base_node(lc_key_size)); + sizeof_base_node()); p->is_base_node = 1; p->u.base.root = root; @@ -923,12 +917,9 @@ static DbTableCATreeNode *create_base_node(DbTableCATree *tb, if (erts_ets_rwmtx_spin_count >= 0) rwmtx_opt.main_spincount = erts_ets_rwmtx_spin_count; -#ifdef ERTS_ENABLE_LOCK_CHECK - lc_key = copy_route_key(&p->u.base.lc_key, lc_key, lc_key_size); -#endif erts_rwmtx_init_opt(&p->u.base.lock, &rwmtx_opt, "erl_db_catree_base_node", - lc_key, + NIL, ERTS_LOCK_FLAGS_CATEGORY_DB); p->u.base.lock_statistics = ((tb->common.status & DB_CATREE_FORCE_SPLIT) ? INT_MAX : 0); @@ -982,16 +973,13 @@ static void do_free_base_node(void* vptr) DbTableCATreeNode *p = (DbTableCATreeNode *)vptr; ASSERT(p->is_base_node); erts_rwmtx_destroy(&p->u.base.lock); -#ifdef ERTS_ENABLE_LOCK_CHECK - destroy_route_key(&p->u.base.lc_key); -#endif erts_free(ERTS_ALC_T_DB_TABLE, p); } static void free_catree_base_node(DbTableCATree* tb, DbTableCATreeNode* p) { ASSERT(p->is_base_node); - ERTS_DB_ALC_MEM_UPDATE_(tb, sizeof_base_node(p->u.base.lc_key.size), 0); + ERTS_DB_ALC_MEM_UPDATE_(tb, sizeof_base_node(), 0); do_free_base_node(p); } @@ -1150,8 +1138,7 @@ static void join_catree(DbTableCATree *tb, { TreeDbTerm* new_root = join_trees(thiz->u.base.root, neighbor->u.base.root); - new_neighbor = create_base_node(tb, new_root, - LC_ORDER(thiz->u.base.lc_key.term)); + new_neighbor = create_base_node(tb, new_root); } if (GET_RIGHT(parent) == neighbor) { neighbor_parent = gparent; @@ -1203,8 +1190,7 @@ static void join_catree(DbTableCATree *tb, { TreeDbTerm* new_root = join_trees(neighbor->u.base.root, thiz->u.base.root); - new_neighbor = create_base_node(tb, new_root, - LC_ORDER(thiz->u.base.lc_key.term)); + new_neighbor = create_base_node(tb, new_root); } if (GET_LEFT(parent) == neighbor) { neighbor_parent = gparent; @@ -1234,12 +1220,12 @@ static void join_catree(DbTableCATree *tb, do_free_base_node, thiz, &thiz->u.base.free_item, - sizeof_base_node(thiz->u.base.lc_key.size)); + sizeof_base_node()); erts_schedule_db_free(&tb->common, do_free_base_node, neighbor, &neighbor->u.base.free_item, - sizeof_base_node(neighbor->u.base.lc_key.size)); + sizeof_base_node()); } static void split_catree(DbTableCATree *tb, @@ -1263,10 +1249,8 @@ static void split_catree(DbTableCATree *tb, split_tree(tb, base->u.base.root, &splitOutWriteBack, &left_tree, &right_tree); - new_left = create_base_node(tb, left_tree, - LC_ORDER(GETKEY(tb, left_tree->dbterm.tpl))); - new_right = create_base_node(tb, right_tree, - LC_ORDER(GETKEY(tb, right_tree->dbterm.tpl))); + new_left = create_base_node(tb, left_tree); + new_right = create_base_node(tb, right_tree); new_route = create_route_node(tb, new_left, new_right, @@ -1285,7 +1269,7 @@ static void split_catree(DbTableCATree *tb, do_free_base_node, base, &base->u.base.free_item, - sizeof_base_node(base->u.base.lc_key.size)); + sizeof_base_node()); } } @@ -1415,8 +1399,7 @@ int db_create_catree(Process *p, DbTable *tbl) DbTableCATree *tb = &tbl->catree; DbTableCATreeNode *root; - root = create_base_node(tb, NULL, - NIL);/* lc_key of first base node does not matter */ + root = create_base_node(tb, NULL); tb->deletion = 0; tb->base_nodes_to_free_list = NULL; erts_atomic_init_relb(&(tb->root), (erts_aint_t)root); diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h index 6913609bf8..418837be8e 100644 --- a/erts/emulator/beam/erl_db_catree.h +++ b/erts/emulator/beam/erl_db_catree.h @@ -48,9 +48,6 @@ typedef struct { ErtsThrPrgrLaterOp free_item; /* Used when freeing using thread progress */ struct DbTableCATreeNode * next; /* Used when gradually deleting */ -#ifdef ERTS_ENABLE_LOCK_CHECK - DbRouteKey lc_key; -#endif char end_of_struct__; } DbTableCATreeBaseNode; diff --git a/erts/emulator/beam/erl_lock_check.c b/erts/emulator/beam/erl_lock_check.c index 394e19f2fa..cfa63e7cd9 100644 --- a/erts/emulator/beam/erl_lock_check.c +++ b/erts/emulator/beam/erl_lock_check.c @@ -92,7 +92,7 @@ static erts_lc_lock_order_t erts_lock_order[] = { { "db_tab", "address" }, { "db_tab_fix", "address" }, { "db_hash_slot", "address" }, - { "erl_db_catree_base_node", "term" }, + { "erl_db_catree_base_node", NULL }, { "erl_db_catree_route_node", "index" }, { "resource_monitors", "address" }, { "driver_list", NULL }, -- cgit v1.2.3