【技术分享】《Chrome V8 源码》38. replace 技术细节、性能影响因素

浏览器安全 3年前 (2021) admin
664 0 0
【技术分享】《Chrome V8 源码》38. replace 技术细节、性能影响因素

 

介绍

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

 

String.prototype.replace 源码

测试用例代码如下:

var str="Visit Microsoft!Visit Microsoft!";var res=str.replace("Microsoft","Runoob");console.log(res);

replace() 采用 TF_BUILTIN 实现,replace() 在 V8 中的函数名是 StringPrototypeReplace,编号是 594,源码如下:

1.  TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) {2.  Label out(this);3.  TNode<Object> receiver = CAST(Parameter(Descriptor::kReceiver));4.  Node* const search = Parameter(Descriptor::kSearch);5.  Node* const replace = Parameter(Descriptor::kReplace);6.  TNode<Context> context = CAST(Parameter(Descriptor::kContext));7.  TNode<Smi> const smi_zero = SmiConstant(0);8.  RequireObjectCoercible(context, receiver, "String.prototype.replace");9.  MaybeCallFunctionAtSymbol(/*省略.....*/);10.   TNode<String> const subject_string = ToString_Inline(context, receiver);11.   TNode<String> const search_string = ToString_Inline(context, search);12.   TNode<IntPtrT> const subject_length = LoadStringLengthAsWord(subject_string);13.   TNode<IntPtrT> const search_length = LoadStringLengthAsWord(search_string);14.   {15.     Label next(this);16.     GotoIfNot(WordEqual(search_length, IntPtrConstant(1)), &next);17.     GotoIfNot(IntPtrGreaterThan(subject_length, IntPtrConstant(0xFF)), &next);18.     GotoIf(TaggedIsSmi(replace), &next);19.     GotoIfNot(IsString(replace), &next);20.     TNode<Uint16T> const subject_instance_type =21.         LoadInstanceType(subject_string);22.     GotoIfNot(IsConsStringInstanceType(subject_instance_type), &next);23.     GotoIf(TaggedIsPositiveSmi(IndexOfDollarChar(context, replace)), &next);24.     Return(CallRuntime(Runtime::kStringReplaceOneCharWithString, context,25.                        subject_string, search_string, replace));26.     BIND(&next); }27.   TNode<Smi> const match_start_index =28.       CAST(CallBuiltin(Builtins::kStringIndexOf, context, subject_string,29.                        search_string, smi_zero));30.   {31.     Label next(this), return_subject(this);32.     GotoIfNot(SmiIsNegative(match_start_index), &next);33.     GotoIf(TaggedIsSmi(replace), &return_subject);34.     GotoIf(IsCallableMap(LoadMap(replace)), &return_subject);35.     ToString_Inline(context, replace);36.     Goto(&return_subject);37.     BIND(&return_subject);38.     Return(subject_string);39.     BIND(&next); }40.   TNode<Smi> const match_end_index = SmiAdd(match_start_index, SmiFromIntPtr(search_length));41.   VARIABLE(var_result, MachineRepresentation::kTagged, EmptyStringConstant());42.   {43.     Label next(this);44.     GotoIf(SmiEqual(match_start_index, smi_zero), &next);45.     TNode<Object> const prefix =46.         CallBuiltin(Builtins::kStringSubstring, context, subject_string,47.                     IntPtrConstant(0), SmiUntag(match_start_index));48.     var_result.Bind(prefix);49.     Goto(&next);50.     BIND(&next); }51.   Label if_iscallablereplace(this), if_notcallablereplace(this);52.   GotoIf(TaggedIsSmi(replace), &if_notcallablereplace);53.   Branch(IsCallableMap(LoadMap(replace)), &if_iscallablereplace,54.          &if_notcallablereplace);55.   BIND(&if_iscallablereplace);56.   {57.     Callable call_callable = CodeFactory::Call(isolate());58.     Node* const replacement =59.         CallJS(call_callable, context, replace, UndefinedConstant(),60.                search_string, match_start_index, subject_string);61.     TNode<String> const replacement_string =62.         ToString_Inline(context, replacement);63.     var_result.Bind(CallBuiltin(Builtins::kStringAdd_CheckNone, context,64.                                 var_result.value(), replacement_string));65.     Goto(&out); }66.   BIND(&if_notcallablereplace);67.   {68.     TNode<String> const replace_string = ToString_Inline(context, replace);69.     Node* const replacement =70.         GetSubstitution(context, subject_string, match_start_index,71.                         match_end_index, replace_string);72.     var_result.Bind(CallBuiltin(Builtins::kStringAdd_CheckNone, context,73.                                 var_result.value(), replacement));74.     Goto(&out);}75.   BIND(&out);76.   {77.     TNode<Object> const suffix =78.         CallBuiltin(Builtins::kStringSubstring, context, subject_string,79.                     SmiUntag(match_end_index), subject_length);80.     TNode<Object> const result = CallBuiltin(81.         Builtins::kStringAdd_CheckNone, context, var_result.value(), suffix);82.      Return(result);83.    }}

上述代码第 3 行代码 receiver 代表测试用例字符串 “Visit Microsoft!Visit Microsoft!”;
第 4 行代码 search 代表测试用例字符串 “Microsoft”;
第 5 行代码 replace 代表测试用例字符串 “Runoob”;
第 9 行代码当 search 为正则表达式时,使用 MaybeCallFunctionAtSymbol() 实现 replace 功能。
下面将 replace 源码划分为五个子功能单独说明:
(1) 功能 1:receiver 长度大于 0xFF、search 长度大于 1 以及 replace 为 ConsString,这三个条件同时成立时
第 10-13 行代码转换 search 和 replace 的数据类型,并计算他们的长度;
第 16 行代码判断 search 的长度是否等于 1,不等于则跳转到第 26 行;
第 17 行代码判断 receiver 的长度是否大于 0xFF,小于等于则跳转到第 26 行;
第 18-19 行判断 replace 是否为小整数或者 replace 不是字符串,结果为真则跳转到第 26 行;
第 20-22 行判断 replace 是否为 ConsString 类型,结果为假则跳转到第 26 行;提示 ConsString不是一个独立的字符串,它是使用指针把两个字符串拼接在一起的字符串对。在 V8 中,两个字符串相加的结果常是 ConsString 类型的字符串对。
第 23 行判断 PositiveSmi 类型;
第 24 行采用 Runtime::kStringReplaceOneCharWithString() 完成 replace。
(2) 功能 2:计算 receiver 中的前缀字符串
第 27-32 行计算 search的第一个字符在 receiver 中的位置 match_start_index,如果 match_start_index 不是负数则跳转到 39 行;
第 33-35 行判断 replace 是否为 SMI 或 函数,是则跳转到 37 行;
第 40 行计算 match_end_index;
第 44 行如果 match_start_index = 0(也就是 search[0]=receiver[0]),则跳转到 49 行;
第 45 行取出 receiver 中 match_start_index 位置之前的字符,保存为 prefix;也就是获取测试用例中的 “Visit ” 字符串;
第 50-54 行判断 replace 是否为 SMI 或 函数,根据判断结果跳转到相应的行号。
(3) 功能 3:replace 是函数类型
第 58-63 行计算 replace 的结果,将该结果拼接在 prefix 后面组成新的字符串 var_result;
(4) 功能 4:replace 是字符串类型
第 58-72 行将 replace 拼接在 prefix 后面组成新的字符串 var_result;
(5) 计算 receiver 中的后缀字符串
第 77-82 行取出 receiver 中 match_end_index 之后的字符串 suffix,将 suffix 拼接在 var_result 后面组成并返回新的字符串,replace 完毕。

下面简单说明 replace 中使用的 runtime 方法:

1.  RUNTIME_FUNCTION(Runtime_StringReplaceOneCharWithString) {2.    HandleScope scope(isolate);3.    DCHECK_EQ(3, args.length());4.    CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);5.    CONVERT_ARG_HANDLE_CHECKED(String, search, 1);6.    CONVERT_ARG_HANDLE_CHECKED(String, replace, 2);7.    const int kRecursionLimit = 0x1000;8.    bool found = false;9.    Handle<String> result;10.    if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,11.                                       kRecursionLimit).ToHandle(&result)) {12.      return *result;13.    }14.    if (isolate->has_pending_exception())15.      return ReadOnlyRoots(isolate).exception();16.    subject = String::Flatten(isolate, subject);17.    if (StringReplaceOneCharWithString(isolate, subject, search, replace, &found,18.                                       kRecursionLimit).ToHandle(&result)) {19.      return *result;20.    }21.    if (isolate->has_pending_exception())22.      return ReadOnlyRoots(isolate).exception();23.    return isolate->StackOverflow();24.  }

上述代码中第 10 执行 StringReplaceOneCharWithString 方法,该方法实现了 replace 功能;
第 14 行代码检测到异常情况时,先执行 String::Flatten,将ConsString字符处理成为单一字符串之后再次执行 StringReplaceOneCharWithString 方法。
图1给出 StringPrototypeReplace 的函数调用堆栈。

【技术分享】《Chrome V8 源码》38. replace 技术细节、性能影响因素

 

String.prototype.replace 测试

测试用例的字节码如下:

1.  //省略........2.  000001A2EE982AC6 @   16 : 12 01             LdaConstant [1]3.  000001A2EE982AC8 @   18 : 15 02 04          StaGlobal [2], [4]4.  000001A2EE982ACB @   21 : 13 02 00          LdaGlobal [2], [0]5.  000001A2EE982ACE @   24 : 26 f9             Star r26.  000001A2EE982AD0 @   26 : 29 f9 03          LdaNamedPropertyNoFeedback r2, [3]7.  000001A2EE982AD3 @   29 : 26 fa             Star r18.  000001A2EE982AD5 @   31 : 12 04             LdaConstant [4]9.  000001A2EE982AD7 @   33 : 26 f8             Star r310.  000001A2EE982AD9 @   35 : 12 05             LdaConstant [5]11.  000001A2EE982ADB @   37 : 26 f7             Star r412.  000001A2EE982ADD @   39 : 5f fa f9 03       CallNoFeedback r1, r2-r413.  000001A2EE982AE1 @   43 : 15 06 06          StaGlobal [6], [6]14.  000001A2EE982AE4 @   46 : 13 07 08          LdaGlobal [7], [8]15.  000001A2EE982AE7 @   49 : 26 f9             Star r216.  000001A2EE982AE9 @   51 : 29 f9 08          LdaNamedPropertyNoFeedback r2, [8]17.  000001A2EE982AEC @   54 : 26 fa             Star r118.  000001A2EE982AEE @   56 : 13 06 02          LdaGlobal [6], [2]19.  000001A2EE982AF1 @   59 : 26 f8             Star r320.  000001A2EE982AF3 @   61 : 5f fa f9 02       CallNoFeedback r1, r2-r321.  000001A2EE982AF7 @   65 : 26 fb             Star r022.  000001A2EE982AF9 @   67 : ab                Return23.  Constant pool (size = 9)24.  000001A2EE982A29: [FixedArray] in OldSpace25.   - map: 0x022d5e100169 <Map>26.   - length: 927.  0: 0x01a2ee9829c9 <FixedArray[8]>28.  1: 0x01a2ee9828c1 <String[#32]: Visit Microsoft!Visit Microsoft!>29.  2: 0x01a2ee9828a9 <String[#3]: str>30.  3: 0x02749a2ab821 <String[#7]: replace>31.  4: 0x01a2ee982909 <String[#9]: Microsoft>32.  5: 0x01a2ee982929 <String[#6]: Runoob>33.  6: 0x01a2ee9828f1 <String[#3]: res>34.  7: 0x02749a2b3699 <String[#7]: console>35.  8: 0x02749a2b2cd9 <String[#3]: log>

上述代码中,第 2-5 行读取字符串 “Visit Microsoft!Visit Microsoft!” 并保存到 r2 寄存器中;
第 6-7 行获取 replace 函数地址并保存到 r1 寄存器中;
第 8-11 行读取 “Microsoft” 和 “Runoob” 并分别保存到 r3 和 r4 寄存器中;
第 12 行调用 repalce 方法;
图 2 给出了 CallNoFeedback 的调用堆栈。

【技术分享】《Chrome V8 源码》38. replace 技术细节、性能影响因素

技术总结
(1) receiver 长度大于 0xFF、search 长度大于 1 以及 replace为ConsString,三个条件同时成立时采用低效率的 runtime 方式处理;
(2) replace 的原理是计算前、后缀,并与 newvalue 拼接组成最终结果。

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

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

【技术分享】《Chrome V8 源码》38. replace 技术细节、性能影响因素

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

原文始发于微信公众号(安全客):【技术分享】《Chrome V8 源码》38. replace 技术细节、性能影响因素

版权声明:admin 发表于 2021年12月27日 上午10:00。
转载请注明:【技术分享】《Chrome V8 源码》38. replace 技术细节、性能影响因素 | CTF导航

相关文章

暂无评论

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