From e6c818956cadeb90f62f61ee5263ba4035be40c4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 1 Aug 2019 18:42:09 +0200 Subject: Ensure that the stack slots are initialized when matching maps When matching a map, the compiler could fail to generate code that would initialize all stack slots (Y registers) properly. Here is a general outline of code that *could* cause this problem: foo(Key, Map) -> Res = case Map of #{Key := Val} -> %% Do something with Val here. . . . #{} -> [] end, %% The stack slot for Val might not have been initialized %% here if the key was not present in the map. . . . %% Use Res. . . . The code generator would wrongly assume that the map matching would always initialize the stack slot, and if nothing else happened to force that stack slot to be initialized, it would remain uninitialized, which would likely crash the runtime system at the next garbage collection. `beam_validator` is supposed to find these kind of problems, but a bug in `beam_validator` prevented it from detecting this problem. https://bugs.erlang.org/browse/ERL-1017 --- lib/compiler/src/beam_ssa_codegen.erl | 18 ++++++++++++++---- lib/compiler/src/beam_validator.erl | 20 +++++++++++++++----- lib/compiler/test/beam_ssa_SUITE.erl | 29 +++++++++++++++++++++++++++-- 3 files changed, 56 insertions(+), 11 deletions(-) diff --git a/lib/compiler/src/beam_ssa_codegen.erl b/lib/compiler/src/beam_ssa_codegen.erl index 07f4c8b461..08641e2abc 100644 --- a/lib/compiler/src/beam_ssa_codegen.erl +++ b/lib/compiler/src/beam_ssa_codegen.erl @@ -764,9 +764,8 @@ defined(Linear, #cg{regs=Regs}) -> def([{L,#cg_blk{is=Is0,last=Last}=Blk0}|Bs], DefMap0, Regs) -> Def0 = def_get(L, DefMap0), - {Is,Def} = def_is(Is0, Regs, Def0, []), - Successors = successors(Last), - DefMap = def_successors(Successors, Def, DefMap0), + {Is,Def,MaybeDef} = def_is(Is0, Regs, Def0, []), + DefMap = def_successors(Last, Def, MaybeDef, DefMap0), Blk = Blk0#cg_blk{is=Is}, [{L,Blk}|def(Bs, DefMap, Regs)]; def([], _, _) -> []. @@ -780,6 +779,11 @@ def_get(L, DefMap) -> def_is([#cg_alloc{anno=Anno0}=I0|Is], Regs, Def, Acc) -> I = I0#cg_alloc{anno=Anno0#{def_yregs=>Def}}, def_is(Is, Regs, Def, [I|Acc]); +def_is([#cg_set{op=succeeded,args=[Var]}=I], Regs, Def, Acc) -> + %% Var will only be defined on the success branch of the `br` + %% for this block. + MaybeDef = def_add_yreg(Var, [], Regs), + {reverse(Acc, [I]),Def,MaybeDef}; def_is([#cg_set{op=kill_try_tag,args=[#b_var{}=Tag]}=I|Is], Regs, Def0, Acc) -> Def = ordsets:del_element(Tag, Def0), def_is(Is, Regs, Def, [I|Acc]); @@ -822,7 +826,7 @@ def_is([#cg_set{anno=Anno0,dst=Dst}=I0|Is], Regs, Def0, Acc) -> Def = def_add_yreg(Dst, Def0, Regs), def_is(Is, Regs, Def, [I|Acc]); def_is([], _, Def, Acc) -> - {reverse(Acc),Def}. + {reverse(Acc),Def,[]}. def_add_yreg(Dst, Def, Regs) -> case is_yreg(Dst, Regs) of @@ -830,6 +834,12 @@ def_add_yreg(Dst, Def, Regs) -> false -> Def end. +def_successors(#cg_br{bool=#b_var{},succ=Succ,fail=Fail}, Def, MaybeDef, DefMap0) -> + DefMap = def_successors([Fail], ordsets:subtract(Def, MaybeDef), DefMap0), + def_successors([Succ], Def, DefMap); +def_successors(Last, Def, [], DefMap) -> + def_successors(successors(Last), Def, DefMap). + def_successors([S|Ss], Def0, DefMap) -> case DefMap of #{S:=Def1} -> diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index ebe9631e09..370481d08a 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -1068,8 +1068,11 @@ verify_get_map(Fail, Src, List, Vst0) -> %% {get_map_elements,{f,7},{x,1},{list,[{atom,a},{x,1},{atom,b},{x,2}]}}. %% %% If 'a' exists but not 'b', {x,1} is overwritten when we jump to {f,7}. +%% +%% We must be careful to preserve the uninitialized status for Y registers +%% that have been allocated but not yet defined. clobber_map_vals([Key,Dst|T], Map, Vst0) -> - case is_reg_defined(Dst, Vst0) of + case is_reg_initialized(Dst, Vst0) of true -> Vst = extract_term(term, {bif,map_get}, [Key, Map], Dst, Vst0), clobber_map_vals(T, Map, Vst); @@ -1079,6 +1082,17 @@ clobber_map_vals([Key,Dst|T], Map, Vst0) -> clobber_map_vals([], _Map, Vst) -> Vst. +is_reg_initialized({x,_}=Reg, #vst{current=#st{xs=Xs}}) -> + is_map_key(Reg, Xs); +is_reg_initialized({y,_}=Reg, #vst{current=#st{ys=Ys}}) -> + case Ys of + #{Reg:=Val} -> + Val =/= uninitialized; + #{} -> + false + end; +is_reg_initialized(V, #vst{}) -> error({not_a_register, V}). + extract_map_keys([Key,_Val|T]) -> [Key|extract_map_keys(T)]; extract_map_keys([]) -> []. @@ -1885,10 +1899,6 @@ check_try_catch_tags(Type, {y,N}=Reg, Vst) -> ok end. -is_reg_defined({x,_}=Reg, #vst{current=#st{xs=Xs}}) -> is_map_key(Reg, Xs); -is_reg_defined({y,_}=Reg, #vst{current=#st{ys=Ys}}) -> is_map_key(Reg, Ys); -is_reg_defined(V, #vst{}) -> error({not_a_register, V}). - assert_term(Src, Vst) -> _ = get_term_type(Src, Vst), ok. diff --git a/lib/compiler/test/beam_ssa_SUITE.erl b/lib/compiler/test/beam_ssa_SUITE.erl index dd1b7ddcd3..6f99b0e28e 100644 --- a/lib/compiler/test/beam_ssa_SUITE.erl +++ b/lib/compiler/test/beam_ssa_SUITE.erl @@ -23,7 +23,7 @@ init_per_group/2,end_per_group/2, calls/1,tuple_matching/1,recv/1,maps/1, cover_ssa_dead/1,combine_sw/1,share_opt/1, - beam_ssa_dead_crash/1]). + beam_ssa_dead_crash/1,stack_init/1]). suite() -> [{ct_hooks,[ts_install_cth]}]. @@ -39,7 +39,8 @@ groups() -> cover_ssa_dead, combine_sw, share_opt, - beam_ssa_dead_crash + beam_ssa_dead_crash, + stack_init ]}]. init_per_suite(Config) -> @@ -589,6 +590,30 @@ do_beam_ssa_dead_crash(A, B) -> end end. +stack_init(_Config) -> + 6 = stack_init(a, #{a => [1,2,3]}), + 0 = stack_init(missing, #{}), + ok. + +stack_init(Key, Map) -> + %% beam_ssa_codegen would wrongly assume that y(0) would always be + %% initialized by the `get_map_elements` instruction that follows, and + %% would set up the stack frame using an `allocate` instruction and + %% would not generate an `init` instruction to initialize y(0). + Res = case Map of + #{Key := Elements} -> + %% Elements will be assigned to y(0) if the key Key exists. + lists:foldl(fun(El, Acc) -> + Acc + El + end, 0, Elements); + #{} -> + %% y(0) will be left uninitialized when the key is not + %% present in the map. + 0 + end, + %% y(0) would be uninitialized here if the key was not present in the map + %% (if the second clause was executed). + id(Res). %% The identity function. id(I) -> I. -- cgit v1.2.3