From e27516edd537045e1151dc8a95c821ba18aadf4f Mon Sep 17 00:00:00 2001 From: Patrik Nyblom Date: Wed, 21 Apr 2010 16:37:16 +0200 Subject: Count reductions for process even when not trapping Set loop factors to 10. Teach erts_debug:set_internal_state to limit loop factor for binary. Add random tests for matches and match with multiple searchstrings. --- erts/emulator/beam/binary.c | 80 +++++++++++++----- erts/emulator/beam/erl_bif_info.c | 11 +++ erts/emulator/beam/global.h | 4 +- lib/stdlib/test/binary_module_SUITE.erl | 138 ++++++++++++++++++++++++++++++-- 4 files changed, 204 insertions(+), 29 deletions(-) diff --git a/erts/emulator/beam/binary.c b/erts/emulator/beam/binary.c index f51815d615..6b6571a1b2 100644 --- a/erts/emulator/beam/binary.c +++ b/erts/emulator/beam/binary.c @@ -695,6 +695,9 @@ static Export binary_match_trap_export; static BIF_RETTYPE binary_match_trap(BIF_ALIST_3); static Export binary_matches_trap_export; static BIF_RETTYPE binary_matches_trap(BIF_ALIST_3); +static Uint max_loop_limit; + + void erts_init_bif_binary(void) { sys_memset((void *) &binary_match_trap_export, 0, sizeof(Export)); @@ -713,9 +716,31 @@ void erts_init_bif_binary(void) binary_matches_trap_export.code[3] = (BeamInstr) em_apply_bif; binary_matches_trap_export.code[4] = (BeamInstr) &binary_matches_trap; + max_loop_limit = 0; return; } +Sint erts_binary_set_loop_limit(Sint limit) +{ + Sint save = (Sint) max_loop_limit; + if (limit <= 0) { + max_loop_limit = 0; + } else { + max_loop_limit = (Uint) limit; + } + return save; +} + +static Uint get_reds(Process *p, int loop_factor) +{ + Uint reds = ERTS_BIF_REDS_LEFT(p) * loop_factor; + Uint tmp = max_loop_limit; + if (tmp != 0 && tmp < reds) { + return tmp; + } + return reds; +} + #define MYALIGN(Size) (SIZEOF_VOID_P * (((Size) / SIZEOF_VOID_P) + \ !!(((Size) % SIZEOF_VOID_P)))) @@ -979,6 +1004,7 @@ static void ac_compute_failure_functions(ACTrie *act, ACNode **qbuff) root->h = root; } + /* * The actual searching for needles in the haystack... * Find first match using Aho-Coracick Trie @@ -1009,10 +1035,10 @@ static void ac_init_find_first_match(ACFindFirstState *state, ACTrie *act, Sint #define AC_NOT_FOUND -1 #define AC_RESTART -2 -#define AC_LOOP_FACTOR 1 +#define AC_LOOP_FACTOR 10 static int ac_find_first_match(ACFindFirstState *state, byte *haystack, - Uint *mpos, Uint *mlen, Uint reductions) + Uint *mpos, Uint *mlen, Uint *reductions) { ACNode *q = state->q; Uint i = state->pos; @@ -1020,7 +1046,7 @@ static int ac_find_first_match(ACFindFirstState *state, byte *haystack, Uint len = state->len; Uint candidate_start = state->candidate_start; Uint rstart; - register Uint reds = (Uint) reductions; + register Uint reds = *reductions; while (i < len) { if (--reds == 0) { @@ -1057,6 +1083,7 @@ static int ac_find_first_match(ACFindFirstState *state, byte *haystack, } } } + *reductions = reds; if (!candidate) { return AC_NOT_FOUND; } @@ -1127,7 +1154,8 @@ static void ac_clean_find_all(ACFindAllState *state) * Differs to the find_first function in that it stores all matches and the values * arte returned only in the state. */ -static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack, Uint reductions) +static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack, + Uint *reductions) { ACNode *q = state->q; Uint i = state->pos; @@ -1137,7 +1165,7 @@ static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack, Ui Uint m = state->m, save_m; Uint allocated = state->allocated; FindallData *out = state->out; - register Uint reds = (Uint) reductions; + register Uint reds = *reductions; while (i < len) { @@ -1212,6 +1240,7 @@ static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack, Ui } } } + *reductions = reds; state->m = m; state->out = out; return (m == 0) ? AC_NOT_FOUND : AC_OK; @@ -1308,7 +1337,7 @@ typedef struct { #define BM_OK 0 /* used only for find_all */ #define BM_NOT_FOUND -1 #define BM_RESTART -2 -#define BM_LOOP_FACTOR 1 +#define BM_LOOP_FACTOR 10 /* Should we have a higher value? */ static void bm_init_find_first_match(BMFindFirstState *state, Sint startpos, Uint len) { @@ -1317,7 +1346,7 @@ static void bm_init_find_first_match(BMFindFirstState *state, Sint startpos, Uin } -static Sint bm_find_first_match(BMFindFirstState *state, BMData *bmd, byte *haystack, Uint reductions) +static Sint bm_find_first_match(BMFindFirstState *state, BMData *bmd, byte *haystack, Uint *reductions) { Sint blen = bmd->len; Sint len = state->len; @@ -1326,7 +1355,7 @@ static Sint bm_find_first_match(BMFindFirstState *state, BMData *bmd, byte *hays byte *needle = bmd->x; Sint i; Sint j = state->pos; - register Uint reds = reductions; + register Uint reds = *reductions; while (j <= len - blen) { if (--reds == 0) { @@ -1336,10 +1365,12 @@ static Sint bm_find_first_match(BMFindFirstState *state, BMData *bmd, byte *hays for (i = blen - 1; i >= 0 && needle[i] == haystack[i + j]; --i) ; if (i < 0) { /* found */ + *reductions = reds; return j; } j += MAX(gs[i],bs[haystack[i+j]] - blen + 1 + i); } + *reductions = reds; return BM_NOT_FOUND; } @@ -1391,7 +1422,7 @@ static void bm_clean_find_all(BMFindAllState *state) * arte returned only in the state. */ static Sint bm_find_all_non_overlapping(BMFindAllState *state, - BMData *bmd, byte *haystack, Uint reductions) + BMData *bmd, byte *haystack, Uint *reductions) { Sint blen = bmd->len; Sint len = state->len; @@ -1403,7 +1434,7 @@ static Sint bm_find_all_non_overlapping(BMFindAllState *state, Uint m = state->m; Uint allocated = state->allocated; FindallData *out = state->out; - register Uint reds = reductions; + register Uint reds = *reductions; while (j <= len - blen) { if (--reds == 0) { @@ -1436,6 +1467,7 @@ static Sint bm_find_all_non_overlapping(BMFindAllState *state, } state->m = m; state->out = out; + *reductions = reds; return (m == 0) ? BM_NOT_FOUND : BM_OK; } @@ -1588,7 +1620,8 @@ static int do_binary_match(Process *p, Eterm subject, Uint hsstart, Uint hslen, Eterm ret; Eterm *hp; BMFindFirstState state; - Uint reds = ERTS_BIF_REDS_LEFT(p) * BM_LOOP_FACTOR; + Uint reds = get_reds(p, BM_LOOP_FACTOR); + Uint save_reds = reds; bm = (BMData *) ERTS_MAGIC_BIN_DATA(bin); #ifdef HARDDEBUG @@ -1603,7 +1636,7 @@ static int do_binary_match(Process *p, Eterm subject, Uint hsstart, Uint hslen, #ifdef HARDDEBUG erts_printf("(bm) state->pos = %ld, state->len = %lu\n",state.pos, state.len); #endif - pos = bm_find_first_match(&state, bm, bytes, reds); + pos = bm_find_first_match(&state, bm, bytes, &reds); if (pos == BM_NOT_FOUND) { ret = am_nomatch; } else if (pos == BM_RESTART) { @@ -1626,6 +1659,7 @@ static int do_binary_match(Process *p, Eterm subject, Uint hsstart, Uint hslen, ret = TUPLE2(hp, ret, erlen); } erts_free_aligned_binary_bytes(temp_alloc); + BUMP_REDS(p, (save_reds - reds) / BM_LOOP_FACTOR); *res_term = ret; return DO_BIN_MATCH_OK; } else if (type == am_ac) { @@ -1635,7 +1669,8 @@ static int do_binary_match(Process *p, Eterm subject, Uint hsstart, Uint hslen, ACFindFirstState state; Eterm ret; Eterm *hp; - Uint reds = ERTS_BIF_REDS_LEFT(p) * AC_LOOP_FACTOR; + Uint reds = get_reds(p, AC_LOOP_FACTOR); + Uint save_reds = reds; act = (ACTrie *) ERTS_MAGIC_BIN_DATA(bin); #ifdef HARDDEBUG @@ -1647,7 +1682,7 @@ static int do_binary_match(Process *p, Eterm subject, Uint hsstart, Uint hslen, Eterm *ptr = big_val(state_term); memcpy(&state,ptr+2,sizeof(state)); } - acr = ac_find_first_match(&state, bytes, &pos, &rlen, reds); + acr = ac_find_first_match(&state, bytes, &pos, &rlen, &reds); if (acr == AC_NOT_FOUND) { ret = am_nomatch; } else if (acr == AC_RESTART) { @@ -1670,6 +1705,7 @@ static int do_binary_match(Process *p, Eterm subject, Uint hsstart, Uint hslen, ret = TUPLE2(hp, epos, erlen); } erts_free_aligned_binary_bytes(temp_alloc); + BUMP_REDS(p, (save_reds - reds) / AC_LOOP_FACTOR); *res_term = ret; return DO_BIN_MATCH_OK; } @@ -1702,7 +1738,8 @@ static int do_binary_matches(Process *p, Eterm subject, Uint hsstart, Uint hslen Eterm ret,tpl; Eterm *hp; BMFindAllState state; - Uint reds = ERTS_BIF_REDS_LEFT(p) * BM_LOOP_FACTOR; + Uint reds = get_reds(p, BM_LOOP_FACTOR); + Uint save_reds = reds; bm = (BMData *) ERTS_MAGIC_BIN_DATA(bin); #ifdef HARDDEBUG @@ -1715,9 +1752,9 @@ static int do_binary_matches(Process *p, Eterm subject, Uint hsstart, Uint hslen bm_restore_find_all(&state,(char *) (ptr+2)); } - pos = bm_find_all_non_overlapping(&state, bm, bytes, reds); + pos = bm_find_all_non_overlapping(&state, bm, bytes, &reds); if (pos == BM_NOT_FOUND) { - ret = am_nomatch; + ret = NIL; } else if (pos == BM_RESTART) { int x = (SIZEOF_BM_SERIALIZED_FIND_ALL_STATE(state) / sizeof(Eterm)) + !!(SIZEOF_BM_SERIALIZED_FIND_ALL_STATE(state) % sizeof(Eterm)); @@ -1750,6 +1787,7 @@ static int do_binary_matches(Process *p, Eterm subject, Uint hsstart, Uint hslen } erts_free_aligned_binary_bytes(temp_alloc); bm_clean_find_all(&state); + BUMP_REDS(p, (save_reds - reds) / BM_LOOP_FACTOR); *res_term = ret; return DO_BIN_MATCH_OK; } else if (type == am_ac) { @@ -1758,7 +1796,8 @@ static int do_binary_matches(Process *p, Eterm subject, Uint hsstart, Uint hslen ACFindAllState state; Eterm ret,tpl; Eterm *hp; - Uint reds = ERTS_BIF_REDS_LEFT(p) * AC_LOOP_FACTOR; + Uint reds = get_reds(p, AC_LOOP_FACTOR); + Uint save_reds = reds; act = (ACTrie *) ERTS_MAGIC_BIN_DATA(bin); #ifdef HARDDEBUG @@ -1770,9 +1809,9 @@ static int do_binary_matches(Process *p, Eterm subject, Uint hsstart, Uint hslen Eterm *ptr = big_val(state_term); ac_restore_find_all(&state,(char *) (ptr+2)); } - acr = ac_find_all_non_overlapping(&state, bytes, reds); + acr = ac_find_all_non_overlapping(&state, bytes, &reds); if (acr == AC_NOT_FOUND) { - ret = am_nomatch; + ret = NIL; } else if (acr == AC_RESTART) { int x = (SIZEOF_AC_SERIALIZED_FIND_ALL_STATE(state) / sizeof(Eterm)) + !!(SIZEOF_AC_SERIALIZED_FIND_ALL_STATE(state) % sizeof(Eterm)); @@ -1805,6 +1844,7 @@ static int do_binary_matches(Process *p, Eterm subject, Uint hsstart, Uint hslen } erts_free_aligned_binary_bytes(temp_alloc); ac_clean_find_all(&state); + BUMP_REDS(p, (save_reds - reds) / AC_LOOP_FACTOR); *res_term = ret; return DO_BIN_MATCH_OK; } diff --git a/erts/emulator/beam/erl_bif_info.c b/erts/emulator/beam/erl_bif_info.c index 18cb09d8cd..de60ca49fa 100644 --- a/erts/emulator/beam/erl_bif_info.c +++ b/erts/emulator/beam/erl_bif_info.c @@ -3567,6 +3567,17 @@ BIF_RETTYPE erts_debug_set_internal_state_2(BIF_ALIST_2) } } } + else if (ERTS_IS_ATOM_STR("binary_loop_limit", BIF_ARG_1)) { + /* Used by binary_module_SUITE (stdlib) */ + Uint max_loops; + if (is_atom(BIF_ARG_2) && ERTS_IS_ATOM_STR("default", BIF_ARG_2)) { + max_loops = erts_binary_set_loop_limit(-1); + BIF_RET(make_small(max_loops)); + } else if (term_to_Uint(BIF_ARG_2, &max_loops) != 0) { + max_loops = erts_binary_set_loop_limit(max_loops); + BIF_RET(make_small(max_loops)); + } + } else if (ERTS_IS_ATOM_STR("re_loop_limit", BIF_ARG_1)) { /* Used by re_SUITE (stdlib) */ Uint max_loops; diff --git a/erts/emulator/beam/global.h b/erts/emulator/beam/global.h index f25b082049..4745aaf9f5 100644 --- a/erts/emulator/beam/global.h +++ b/erts/emulator/beam/global.h @@ -1575,8 +1575,10 @@ extern int erts_cpu_timestamp; void erts_init_bif_chksum(void); /* erl_bif_re.c */ void erts_init_bif_re(void); -void erts_init_bif_binary(void); Sint erts_re_set_loop_limit(Sint limit); +/* erl_bif_binary.c */ +void erts_init_bif_binary(void); +Sint erts_binary_set_loop_limit(Sint limit); /* erl_unicode.c */ void erts_init_unicode(void); Sint erts_unicode_set_loop_limit(Sint limit); diff --git a/lib/stdlib/test/binary_module_SUITE.erl b/lib/stdlib/test/binary_module_SUITE.erl index b6d3dde1d4..ffed43af10 100644 --- a/lib/stdlib/test/binary_module_SUITE.erl +++ b/lib/stdlib/test/binary_module_SUITE.erl @@ -98,14 +98,104 @@ do_interesting(Module) -> random_ref_comp(doc) -> ["Test pseudorandomly generated cases against reference imlementation"]; random_ref_comp(Config) when is_list(Config) -> - put(success_counter,0), - random:seed({1271,769940,559934}), - do_random_match_comp(5000,{1,40},{30,1000}), + ?line put(success_counter,0), + ?line random:seed({1271,769940,559934}), + ?line do_random_match_comp(5000,{1,40},{30,1000}), io:format("Number of successes: ~p~n",[get(success_counter)]), - do_random_match_comp2(5000,{1,40},{30,1000}), + ?line do_random_match_comp2(5000,{1,40},{30,1000}), io:format("Number of successes: ~p~n",[get(success_counter)]), + ?line do_random_match_comp3(5000,{1,40},{30,1000}), + io:format("Number of successes: ~p~n",[get(success_counter)]), + ?line do_random_matches_comp(5000,{1,40},{30,1000}), + io:format("Number of successes: ~p~n",[get(success_counter)]), + ?line do_random_matches_comp2(5000,{1,40},{30,1000}), + io:format("Number of successes: ~p~n",[get(success_counter)]), + ?line do_random_matches_comp3(5,{1,40},{30,1000}), + ?line erts_debug:set_internal_state(available_internal_state,true), + ?line io:format("oldlimit: ~p~n",[ erts_debug:set_internal_state(binary_loop_limit,100)]), + ?line do_random_matches_comp3(5,{1,40},{30,1000}), + ?line io:format("limit was: ~p~n",[ erts_debug:set_internal_state(binary_loop_limit,default)]), + ?line erts_debug:set_internal_state(available_internal_state,false), ok. +do_random_matches_comp(0,_,_) -> + ok; +do_random_matches_comp(N,NeedleRange,HaystackRange) -> + NumNeedles = element(2,HaystackRange) div element(2,NeedleRange), + Needles = [random_string(NeedleRange) || + _ <- lists:duplicate(NumNeedles,a)], + Haystack = random_string(HaystackRange), + true = do_matches_comp(Needles,Haystack), + do_random_matches_comp(N-1,NeedleRange,HaystackRange). + +do_random_matches_comp2(0,_,_) -> + ok; +do_random_matches_comp2(N,NeedleRange,HaystackRange) -> + NumNeedles = element(2,HaystackRange) div element(2,NeedleRange), + Haystack = random_string(HaystackRange), + Needles = [random_substring(NeedleRange,Haystack) || + _ <- lists:duplicate(NumNeedles,a)], + true = do_matches_comp(Needles,Haystack), + do_random_matches_comp2(N-1,NeedleRange,HaystackRange). + +do_random_matches_comp3(0,_,_) -> + ok; +do_random_matches_comp3(N,NeedleRange,HaystackRange) -> + NumNeedles = element(2,HaystackRange) div element(2,NeedleRange), + Haystack = random_string(HaystackRange), + Needles = [random_substring(NeedleRange,Haystack) || + _ <- lists:duplicate(NumNeedles,a)], + RefRes = binref:matches(Haystack,Needles), + true = do_matches_comp_loop(10000,Needles,Haystack, RefRes), + do_random_matches_comp3(N-1,NeedleRange,HaystackRange). + +do_matches_comp_loop(0,_,_,_) -> + true; +do_matches_comp_loop(N, Needles, Haystack0,RR) -> + DummySize=N*8, + Haystack1 = <<0:DummySize,Haystack0/binary>>, + RR1=[{X+N,Y} || {X,Y} <- RR], + true = do_matches_comp2(Needles,Haystack1,RR1), + Haystack2 = <>, + RR2 = RR ++ [{X2+N+byte_size(Haystack0),Y2} || {X2,Y2} <- RR], + true = do_matches_comp2(Needles,Haystack2,RR2), + do_matches_comp_loop(N-1, Needles, Haystack0,RR). + + +do_matches_comp2(N,H,A) -> + C = (catch binary:matches(H,N)), + case (A =:= C) of + true -> + true; + _ -> + io:format("Failed to match ~p (needle) against ~s (haystack)~n", + [N,H]), + io:format("A:~p,~n,C:~p.~n", + [A,C]), + exit(mismatch) + end. +do_matches_comp(N,H) -> + A = (catch binref:matches(H,N)), + B = (catch binref:matches(H,binref:compile_pattern(N))), + C = (catch binary:matches(H,N)), + D = (catch binary:matches(H,binary:compile_pattern(N))), + if + A =/= nomatch -> + put(success_counter,get(success_counter)+1); + true -> + ok + end, + case {(A =:= B), (B =:= C),(C =:= D)} of + {true,true,true} -> + true; + _ -> + io:format("Failed to match ~p (needle) against ~s (haystack)~n", + [N,H]), + io:format("A:~p,~nB:~p,~n,C:~p,~n,D:~p.~n", + [A,B,C,D]), + exit(mismatch) + end. + do_random_match_comp(0,_,_) -> ok; do_random_match_comp(N,NeedleRange,HaystackRange) -> @@ -122,11 +212,43 @@ do_random_match_comp2(N,NeedleRange,HaystackRange) -> true = do_match_comp(Needle,Haystack), do_random_match_comp2(N-1,NeedleRange,HaystackRange). +do_random_match_comp3(0,_,_) -> + ok; +do_random_match_comp3(N,NeedleRange,HaystackRange) -> + NumNeedles = element(2,HaystackRange) div element(2,NeedleRange), + Haystack = random_string(HaystackRange), + Needles = [random_substring(NeedleRange,Haystack) || + _ <- lists:duplicate(NumNeedles,a)], + true = do_match_comp3(Needles,Haystack), + do_random_match_comp3(N-1,NeedleRange,HaystackRange). + do_match_comp(N,H) -> - A = binref:match(H,N), - B = binref:match(H,binref:compile_pattern([N])), - C = binary:match(H,N), - D = binary:match(H,binary:compile_pattern([N])), + A = (catch binref:match(H,N)), + B = (catch binref:match(H,binref:compile_pattern([N]))), + C = (catch binary:match(H,N)), + D = (catch binary:match(H,binary:compile_pattern([N]))), + if + A =/= nomatch -> + put(success_counter,get(success_counter)+1); + true -> + ok + end, + case {(A =:= B), (B =:= C),(C =:= D)} of + {true,true,true} -> + true; + _ -> + io:format("Failed to match ~s (needle) against ~s (haystack)~n", + [N,H]), + io:format("A:~p,~nB:~p,~n,C:~p,~n,D:~p.~n", + [A,B,C,D]), + exit(mismatch) + end. + +do_match_comp3(N,H) -> + A = (catch binref:match(H,N)), + B = (catch binref:match(H,binref:compile_pattern(N))), + C = (catch binary:match(H,N)), + D = (catch binary:match(H,binary:compile_pattern(N))), if A =/= nomatch -> put(success_counter,get(success_counter)+1); -- cgit v1.2.3