【技术分享】《Chrome V8 源码》37. match 源码分析、正则快慢的区别

浏览器安全 2年前 (2021) admin
681 0 0
【技术分享】《Chrome V8 源码》37. match 源码分析、正则快慢的区别

 

01
介绍

字符串是 JavaScript 中的重要数据类型,其重要性不仅体现在字符串是应用最多最广泛的数据类型,更体现在V8中使用了大量的技术手段来修饰和优化字符串的操作。接下来的几篇文章将集中讲解字符串的相关操作。本文先讲解 String.prototype.match 的源码以及相关数据结构,再通过测试用例演示 String.prototype.match 的调用、加载和执行过程。
注意 (1)Sea of Nodes 是本文的先导知识,请参考 Cliff 1993年发表的论文 From Quads to Graphs。(2)本文所用环境为:V8 7.9、win10 x64、VS2019。

 

02

String.prototype.match 源码


测试用例代码如下:

var str="1 plus 2 equal 3";str.match(/d+/g);

match() 采用 TF_BUILTIN 实现,concet() 在 V8 中的函数名是 StringPrototypeMatch,编号是 591,源码如下:

1.  TF_BUILTIN(StringPrototypeMatch, StringMatchSearchAssembler) {2.  TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));3.  TNode<Object> maybe_regexp = CAST(Parameter(Descriptor::kRegexp));4.  TNode<Context> context = CAST(Parameter(Descriptor::kContext));5.  Generate(kMatch, "String.prototype.match", receiver, maybe_regexp, context);}6.  //分隔...............7.  void Generate(Variant variant, const char* method_name,TNode<Object> receiver, TNode<Object> maybe_regexp, TNode<Context> context) {8.    Label call_regexp_match_search(this);9.     Builtins::Name builtin;10.      Handle<Symbol> symbol;11.      DescriptorIndexNameValue property_to_check;12.      if (variant == kMatch) {13.        builtin = Builtins::kRegExpMatchFast;14.        symbol = isolate()->factory()->match_symbol();15.        property_to_check = DescriptorIndexNameValue{16.            JSRegExp::kSymbolMatchFunctionDescriptorIndex,17.            RootIndex::kmatch_symbol, Context::REGEXP_MATCH_FUNCTION_INDEX};18.      } else {//省略....................19.      }20.      RequireObjectCoercible(context, receiver, method_name);//省略................21.      { RegExpBuiltinsAssembler regexp_asm(state());22.        TNode<String> receiver_string = ToString_Inline(context, receiver);23.        TNode<NativeContext> native_context = LoadNativeContext(context);24.        TNode<HeapObject> regexp_function = CAST(25.            LoadContextElement(native_context, Context::REGEXP_FUNCTION_INDEX));26.        TNode<Map> initial_map = CAST(LoadObjectField(27.            regexp_function, JSFunction::kPrototypeOrInitialMapOffset));28.        TNode<Object> regexp = regexp_asm.RegExpCreate(29.            context, initial_map, maybe_regexp, EmptyStringConstant());30.        Label fast_path(this), slow_path(this);31.        regexp_asm.BranchIfFastRegExp(context, CAST(regexp), initial_map,32.            PrototypeCheckAssembler::kCheckPrototypePropertyConstness,33.            property_to_check, &fast_path, &slow_path);34.        BIND(&fast_path);35.        Return(CallBuiltin(builtin, context, regexp, receiver_string));36.        BIND(&slow_path);37.        {38.          TNode<Object> maybe_func = GetProperty(context, regexp, symbol);39.          Callable call_callable = CodeFactory::Call(isolate());40.          Return(CallJS(call_callable, context, maybe_func, regexp,41.                        receiver_string));42.        } } }

上述代码中,第 1-5 行是 match() 的入口函数;Generate()(第 7 行代码)用于实现 match 功能,参数 variant 的值只能是 Match 或 Search,这说明了 Search 也由 Generate() 实现。参数 receiver 是字符串(测试用例中的 str),maybe_regexp 是正则字符串(测试用例中的 /d+/g);
第 13-17 行代码准备 Builtins::kRegExpMatchFast、symbol 和 property_to_check 三个参数,其中 kRegExpMatchFast 和 symbol 在快速正则时会被用到;
第 22 行代码把 receiver 转换成字符串并存储到 receiver_string 中;
第 23-28 行代码使用字符串(/d+/g)创建正则表达式 regexp;
第 31 行代码判断是否满足快速正则匹配的使用条件,如果满足则执行第 35 行代码,否则执行第 36-40 行代码;
第 35 行代码执行快速正则匹配;提示:使用 Builtin 实现的正则叫做快速正则匹配;
第 36-40 行代码执行慢速正则匹配。
下面说明 Generate() 中的重要函数:
(1) Builtins::kRegExpMatchFast 用于实现快速正则匹配,源码如下:

1.  TF_BUILTIN(RegExpMatchFast, CodeStubAssembler) {2.    compiler::CodeAssemblerState* state_ = state();  compiler::CodeAssembler ca_(state());3.    TNode<Context> parameter0 = UncheckedCast<Context>(Parameter(Descriptor::kContext));4.    USE(parameter0);5.    compiler::TNode<JSRegExp> parameter1 = UncheckedCast<JSRegExp>(Parameter(Descriptor::kReceiver));6.    USE(parameter1);7.    compiler::TNode<String> parameter2 = UncheckedCast<String>(Parameter(Descriptor::kString));8.    USE(parameter2);9.    compiler::CodeAssemblerParameterizedLabel<Context, JSRegExp, String> block0(&ca_, compiler::CodeAssemblerLabel::kNonDeferred);10.      ca_.Goto(&block0, parameter0, parameter1, parameter2);11.    if (block0.is_used()) {12.      compiler::TNode<Context> tmp0;13.      compiler::TNode<JSRegExp> tmp1;14.      compiler::TNode<String> tmp2;15.      ca_.Bind(&block0, &tmp0, &tmp1, &tmp2);16.      ca_.SetSourcePosition("../../../src/builtins/regexp-match.tq", 27);17.      compiler::TNode<Object> tmp3;18.      USE(tmp3);19.      tmp3 = FastRegExpPrototypeMatchBody_322(state_, compiler::TNode<Context>{tmp0}, compiler::TNode<JSRegExp>{tmp1}, compiler::TNode<String>{tmp2});20.      CodeStubAssembler(state_).Return(tmp3);21.    }22.  }

上述代码中,第 3-8 行定义上下文(parameter0)、正则(parameter1)以及字符串 (parameter2)三个参数;
第 10-14 行代码 Goto 用于跳转到 block0。其中 tmp1 表示 parameter1,tmp2 表示 parameter2;
第 19 行代码 FastRegExpPrototypeMatchBody_322() 是入口函数,在该函数中调用 RegExpBuiltinsAssembler::RegExpPrototypeMatchBody 完成正则匹配,后续文章单独讲解。
(2) BranchIfFastRegExp 判断是否符合满足快速正则条件,源码如下:

1.  void RegExpBuiltinsAssembler::BranchIfFastRegExp(/*省略...*/) {2.    CSA_ASSERT(this, TaggedEqual(LoadMap(object), map));3.    GotoIfForceSlowPath(if_ismodified);4.    TNode<NativeContext> native_context = LoadNativeContext(context);5.    GotoIf(IsRegExpSpeciesProtectorCellInvalid(native_context), if_ismodified);6.    TNode<JSFunction> regexp_fun =7.        CAST(LoadContextElement(native_context, Context::REGEXP_FUNCTION_INDEX));8.    TNode<Map> initial_map = CAST(9.        LoadObjectField(regexp_fun, JSFunction::kPrototypeOrInitialMapOffset));10.    TNode<BoolT> has_initialmap = TaggedEqual(map, initial_map);11.    GotoIfNot(has_initialmap, if_ismodified);12.    TNode<Object> last_index = FastLoadLastIndexBeforeSmiCheck(CAST(object));13.    GotoIfNot(TaggedIsPositiveSmi(last_index), if_ismodified);14.    // Verify the prototype.15.    TNode<Map> initial_proto_initial_map = CAST(16.        LoadContextElement(native_context, Context::REGEXP_PROTOTYPE_MAP_INDEX));17.    DescriptorIndexNameValue properties_to_check[2];18.    int property_count = 0;19.    properties_to_check[property_count++] = DescriptorIndexNameValue{20.        JSRegExp::kExecFunctionDescriptorIndex, RootIndex::kexec_string,21.        Context::REGEXP_EXEC_FUNCTION_INDEX};22.    if (additional_property_to_check) {23.      properties_to_check[property_count++] = *additional_property_to_check;24.    }25.    PrototypeCheckAssembler prototype_check_assembler(26.        state(), prototype_check_flags, native_context, initial_proto_initial_map,27.        Vector<DescriptorIndexNameValue>(properties_to_check, property_count));28.    TNode<HeapObject> prototype = LoadMapPrototype(map);29.    prototype_check_assembler.CheckAndBranch(prototype, if_isunmodified,30.                                             if_ismodified);31.  }

上述代码中 if_ismodified 代表慢速正则;第 3 行代码 GotoIfForceSlowPath 根据 V8_ENABLE_FORCE_SLOW_PATH 判断是否使用慢速正则;
第 2 行代码检测正则表达式对象map的tag标记;
第 10-11 行代码判断正则表式对象的 tag 与 native_context中的 regexp_fun的 tag 是否相等;
第 15-29 行代码检测 prototype 属性,并根据检测结果决定是否使用快速正则。
(3) MaybeCallFunctionAtSymbol 方法源码如下:

1.  void StringBuiltinsAssembler::MaybeCallFunctionAtSymbol(2.      Node* const context, Node* const object, Node* const maybe_string,3.      Handle<Symbol> symbol,4.      DescriptorIndexNameValue additional_property_to_check,5.      const NodeFunction0& regexp_call, const NodeFunction1& generic_call) {6.    Label out(this);7.    // Smis definitely don't have an attached symbol.8.    GotoIf(TaggedIsSmi(object), &out);9.    {10.      Label stub_call(this), slow_lookup(this);11.      GotoIf(TaggedIsSmi(maybe_string), &slow_lookup);12.      GotoIfNot(IsString(maybe_string), &slow_lookup);13.      RegExpBuiltinsAssembler regexp_asm(state());14.      regexp_asm.BranchIfFastRegExp(15.          CAST(context), CAST(object), LoadMap(object),16.          PrototypeCheckAssembler::kCheckPrototypePropertyConstness,17.          additional_property_to_check, &stub_call, &slow_lookup);18.      BIND(&stub_call);19.  .20.      regexp_call();21.      BIND(&slow_lookup);22.    }23.    GotoIf(IsNullOrUndefined(object), &out);24.    TNode<Object> const maybe_func = GetProperty(context, object, symbol);25.    GotoIf(IsUndefined(maybe_func), &out);26.    GotoIf(IsNull(maybe_func), &out);27.    // Attempt to call the function.28.    generic_call(maybe_func);29.    BIND(&out);30.  }

上述代码中第 11-12 行判断正则表达式是否为 SMI 或 String,判断结果为真则执行慢速正则;
第 14 行代码 BranchIfFastRegExp 判断原型链属性是否满足快速正则条件;
第 23、25、26 行代码分别判断字符串是否为空、正则表达式是否未定义或为空。
图 1 给出了 Generate 的函数调用堆栈。

【技术分享】《Chrome V8 源码》37. match 源码分析、正则快慢的区别

 

03

String.prototype.match 测试


测试用例的字节码如下:

1.  //省略.............2.  0000038004E42A8E @   16 : 12 01             LdaConstant [1]3.  0000038004E42A90 @   18 : 15 02 04          StaGlobal [2], [4]4.  0000038004E42A93 @   21 : 13 02 00          LdaGlobal [2], [0]5.  0000038004E42A96 @   24 : 26 f9             Star r26.  0000038004E42A98 @   26 : 29 f9 03          LdaNamedPropertyNoFeedback r2, [3]7.  0000038004E42A9B @   29 : 26 fa             Star r18.  0000038004E42A9D @   31 : 79 04 06 01       CreateRegExpLiteral [4], [6], #19.  0000038004E42AA1 @   35 : 26 f8             Star r310.  0000038004E42AA3 @   37 : 5f fa f9 02       CallNoFeedback r1, r2-r311.  0000038004E42AA7 @   41 : 15 05 07          StaGlobal [5], [7]12.  0000038004E42AAA @   44 : 13 06 09          LdaGlobal [6], [9]13.  0000038004E42AAD @   47 : 26 f9             Star r214.  0000038004E42AAF @   49 : 29 f9 07          LdaNamedPropertyNoFeedback r2, [7]15.  0000038004E42AB2 @   52 : 26 fa             Star r116.  0000038004E42AB4 @   54 : 13 05 02          LdaGlobal [5], [2]17.  0000038004E42AB7 @   57 : 26 f8             Star r318.  0000038004E42AB9 @   59 : 5f fa f9 02       CallNoFeedback r1, r2-r319.  0000038004E42ABD @   63 : 26 fb             Star r020.  0000038004E42ABF @   65 : ab                Return21.  Constant pool (size = 8)22.  0000038004E429F9: [FixedArray] in OldSpace23.   - map: 0x01afd2dc0169 <Map>24.   - length: 825.  0: 0x038004e42999 <FixedArray[8]>26.  1: 0x038004e428c1 <String[#16]: 1 plus 2 equal 3>27.  2: 0x038004e428a9 <String[#3]: str>28.  3: 0x022bdecab4b9 <String[#5]: match>29.  4: 0x038004e428f9 <String[#3]: d+>30.  5: 0x038004e428e1 <String[#3]: res>31.  6: 0x022bdecb3699 <String[#7]: console>32.  7: 0x022bdecb2cd9 <String[#3]: log>33.  Handler Table (size = 0)

上述代码中,第 2-5 行代码加载 “1 plus 2 equal 3” 到 r2 寄存器;
第 6 行代码获取字符串方法 match,并存储到 r1 寄存器;
第 8 行代码为字符串 d+ 创建正表达式对象,并存储到 r3 寄存器;
第 10 行代码 CallNoFeedback 调用 match方法(r1 寄存器),并传递 r2、r3 两个参数给 match 方法。
图 2 给出了字节码 CallNoFeedback 的入口,从此处开始跟踪可以看到正则表达的匹配过程。

【技术分享】《Chrome V8 源码》37. match 源码分析、正则快慢的区别

技术总结
(1) 快速正则是采用 Builtins::kRegExpMatchFast 实现的快速匹配;
(2) 使用快速正则的判断条件包括:字符串类型是否正确、正则表达式的类型、V8_ENABLE_FORCE_SLOW_PATH 等。

好了,今天到这里,下次见。

个人能力有限,有不足与纰漏,欢迎批评指正
微信:qq9123013 备注:v8交流 邮箱:
[email protected]

【技术分享】《Chrome V8 源码》37. match 源码分析、正则快慢的区别

- 结尾 -
精彩推荐
【技术分享】从零开始开发CS beacon(三)
完美收官 | 安全客官网升级岁末惊喜活动
【技术分享】 Latte-SSTI-Payloads总结
【技术分享】《Chrome V8 源码》37. match 源码分析、正则快慢的区别
戳“阅读原文”查看更多内容

原文始发于微信公众号(安全客):【技术分享】《Chrome V8 源码》37. match 源码分析、正则快慢的区别

版权声明:admin 发表于 2021年12月23日 上午10:00。
转载请注明:【技术分享】《Chrome V8 源码》37. match 源码分析、正则快慢的区别 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...