企业官网建设流程全解析

丽水哪里做网站,自己做头像的网站非流光,百度购物平台,做网站的技术路线本文介绍了支配树#xff08;Dominator Tree#xff09;算法在鸿蒙系统 ArkTS 内存分析工具中的应用。为应对淘宝 App 鸿蒙版因内存溢出导致的 Crash 问题#xff0c;作者构建了一套从客户端采集内存快照、服务端自动分析的工具链。文中对比了多种支配树构建算法#xff08…本文介绍了支配树Dominator Tree算法在鸿蒙系统 ArkTS 内存分析工具中的应用。为应对淘宝 App 鸿蒙版因内存溢出导致的 Crash 问题作者构建了一套从客户端采集内存快照、服务端自动分析的工具链。文中对比了多种支配树构建算法如朴素算法、Lengauer-Tarjan 算法和迭代算法并说明选用优化后的迭代算法的原因实现简单、便于验证、且适合存在大量循环引用的内存图结构。前言随着淘宝App鸿蒙版UV⽇渐增⻓ArkTS的内存溢出导致的Crash也在逐步上升因此团队实现了⼀套从客户端采集内存镜像⾄服务端⾃动分析聚合⼯具。本⽂介绍该⼯具的核⼼原理内存对象的⽀配树算法▐⽀配树是什么在⼀个有向图中存在⼀个⼊⼝节点如果节点⽀配节点当且仅当从→的所有路径都经过节点记如果不存在使得且则是的直接⽀配节点记做。从⼊⼝通过直接⽀配节点形成的树则称为⽀配树即⽀配树中每个节点的⽗节点都是其直接⽀配节点。。▐⽀配树作⽤在分析内存泄漏或者内存溢出的时候内存镜像中的对象通常会很多(数量可达百万)。⾸要的问题是如何找出占⽤内存较⼤那些对象对象占⽤内存可以分为两类class B { int c;}class A { B b new B();} A a new A();指的是对象本身的内存⼤⼩。上⽅代码中a对象中有⼀个引⽤指针b为4bytes。b对象中有⼀个变量c为4bytes指的是回收该对象之后虚拟机能够回收的内存⼤⼩。a对象的为8释放a之后可以同时释放b所以显然只要将那些占⽤较⾼的对象回收掉就可以解决内存溢出的问题。如果将对象抽象为有向图中的节点对象间的引⽤关系则可以抽象为有向图中的边例如上⾯的代码a对象引⽤b对象可以抽象为下图。因此内存镜像中的对象集合可以抽象为以GC root为⼊⼝节点的有向图通过有向图构建出对应的⽀配树。假设在⽀配树中根据⽀配树的特性回收 a 对象在内存中就成了孤⽴对象可以被GC由此可以得出▐⽀配树算法种类朴素算法原理是对每个节点依次删除图中的其他节点判断是否存在路径从根节点到达节点算法复杂度为复杂度过⾼⼀般不使⽤。Lengauer-Tarjan算法经典的⽀配树算法⼀般情况是优化后的算法复杂度 α 是阿克曼函数可以理解为趋近于线性。迭代算法通常是用于在编译器的控制流当中算法复杂度是优化后算法复杂度。实现鸿蒙ArkTS内存镜像分析⼯具使⽤的是迭代算法主要有以下⼏个原因Lengauer-Tarjan算法原理及其优化⽐较复杂⼯具类对于构建⽀配树的速度要求没有那么⾼可以使⽤华为已实现的profiler插件以及chrome的开源代码作为对⽐防⽌算法出错在内存对象的引⽤关系中存在很多循环引⽤节点与节点之间的环⽐较严重这让Lengauer-Tarjan算法在计算半⽀配节点的时候算法复杂度⼤⼤增加。Lengauer-Tarjan算法原理介绍Lengauer-Tarjan算法的主要原因是⽹上对于该算法的介绍⼤部分证明过程都是论⽂翻译⽐较复杂包括有时AI的解答也存在错误。例 如 上 ⾯ 是 ⼀ 个 AI 关 于 半 ⽀ 配 者 的 定 义 描 述 错 误 正 确 的 描 述 应 当 是 所有节 点 的 DFS 编 号 都⼤ 于 x。▐基础知识下⾯是⼀张有序图通过DFS之后形成的节点和边的关系图节点0-10是dfs遍历的顺序下⾯称为dfs序边的类型可以分为4种树边即DFS过程中建⽴的边在下图中显示为⿊⾊前向边即祖先节点到⼦树⾮⼉⼦的边在下图中显示蓝⾊, 2-61-40-2返祖边即节点到祖先节点的变在下图中显示为橙⾊4-2,3-2,6-2横叉边即从⾮⼦树、⾮祖先横叉过来的边在下图中显示为绿⾊8-5,9-8。▐理解半⽀配节点如何理解半⽀配节点是理解Lengauer-Tarjan算法关键点以下是半⽀配节点的定义对于任意节点如果存在一个节点且的路径中所有节点节点可以不存在)的序号都大于则是的半支配候选其中dfs序最小的被称为的半支配节点。在基础知识中介绍过4种边的类型对于任意节点的半⽀配节点可以理解为是通过这四种边到达最远祖先节点(⽐当前节点dfs序⼩的节点只有可能是祖先节点或者左⼦树节点dfs必须遍历完左⼦树再遍历右⼦树左⼦树节点不可能存在到右⼦树节点的边只可能是祖先节点)。由半⽀配节点的定义可得⽗节点是半⽀配候选例如: 3-5前向边的节点是半⽀配候选例如: 2-6返祖边的节点是半⽀配候选例如1-4-2横叉边的节点是半⽀配者选例如: 1-7-8-5换个说法整个半⽀配候选的集合是的直接⽀配者更进⼀步从半⽀配候选增加⼀条边指向不改变的⽀配关系于是对于任意节点都可以简化为下⾯的连接关系其中隐含的结论: 半⽀配候选都是在的树边上▐计算直接⽀配节点半⽀配节点还不能直接⽀配节点因为还不⽀配的树边例如上⾯的dfs序为5的节点它存在树边(3-5)和横叉边(1-7-8-5)通过定义可以算出它的半⽀配节点。但实际上还存在0-2-3-5这条路径不经过1号节点实际上。计算直接⽀配节点的⽅式计算从半⽀配节点出发经过树边到达节点所有中间节点的的最⼩dfs序。在论⽂中这两个结论是通过反证法来进⾏证明⽐较难理解这⾥尝试通过⾃然语⾔来进⾏证明不保证完全正确如有错误请以论⽂为准。⽐较好推导说明不存在有的祖先节点不通过到达⼜由于半⽀配集合都是处于的树边上所以到达半⽀配集合都得通过故说明⾄少存在⼀个节点不通过可以到达节点其中可以证明不⽀配可以⼤致得到下图的节点关系最主要问题是为何不需要考虑其他的情况例如。可以假设则存在不经过到达但是该条路径必须经过的半⽀配候选集根据前⾯半⽀配节点隐含的结论的半⽀配候选集都在的树边上且由于存在树边到达这与的定义相悖故。Lengauer-Tarjan算法实现代码可以参考 Android perflibcs.android.com/android-studio/platform/tools/base//mirror-goog-studio-main:perflib/src/main/java/com/android/tools/perflib/heap/analysis/LinkEvalDominators.kt迭代算法▐算法原理迭代算法的原理利⽤了⽀配节点存在传递性即⽀配节点当且仅当⽀配其前驱节点简要⽤公式表达:迭代算法过程如下1. 初始化根节点 s , Dom(s) {s}2. 初始化其他节点 n Dom(n) {全集}3. 对于⾮根节点 n Dom(n) n ∪ (∩Dom(p)) 即当前节点 n 并上所有前驱节点 p的⽀配节点的交集4. 重复步骤3直到所有的 Dom(n) 不再变化▐JS内存镜像分析js内存镜像实际上是⼀个json⽂件分为以下⼏个部分{snapshot:{meta:{node_fields:[type,name,id,self_size,edge_count,trace_node_id,detachedness,native_size],node_types:[[hidden,array,string,object,code,closure,regexp,number,native,synthetic,concatenatedstring,slicedstring,symbol,bigint],string,number,number,number,number,number],edge_fields:[type,name_or_index,to_node],edge_types:[[context,element,property,internal,hidden,shortcut,weak],string_or_number,node],trace_function_info_fields:[...],trace_node_fields:[...],sample_fields:[...],location_fields:[...]},node_count:100056,edge_count:384773,trace_function_count:0},nodes:[...],edges:[...],trace_function_infos:[],trace_tree:[],samples:[],locations:[],strings:[...],}meta: 定义了节点和边的结构node_fields: 定义了单个内存节点(node)的属性node_types:内存节点(node)的类型edge_fields:定义了单个边(edge)的属性edge_types: 定义了边的类型node_count: 节点数量edge_count: 边的数量nodes: 节点的集合edges: 边的集合strings:所有的字符串包括边的名称内存节点的名称等等内存节点node在nodes中每⼀⾏代表⼀个节点其中⾏中的每个数字由node_fields来描述例如node_fields:[type,name,id,self_size,edge_count,trace_node_id,detachedness,native_size], nodes:[9,11693,1,0,6386,0,0,0,8,11696,3,48,1,0,0,0,8,11696,5,48,1,0,0,0,...]以第⼀⾏ 9,11693,1,0,6386,0,0,0 为例解析后是这样type: 9, //节点类型的偏移name: 11693, //节点名字大概率是文件名对应strings中的indexid: 1, //无特殊含义节点的标号self_size: 0, //大概率是shallow_size0大概率是数组edge_count: 6386, //跟其他内存节点的引用关系nodes_type存储了节点的14种类型这个例⼦中节点的类型是synthetic不过这种类型似乎是虚拟机内部类型不展示node_types:[[hidden,array,string,object,code,closure,regexp,number,native,synthetic,concatenatedstring,slicedstring,symbol,bigint],string,number,number,number,number,number],strings存储了所有的字符串包括了节点名字在这个例⼦中name转为字符串是SyntheticRoot。引⽤关系edgeedges中存储了内存节点的引⽤关系每⼀⾏代表⼀条边⾏中的每⼀个数字通过edge_fields进⾏表示edge_fields:[type,name_or_index,to_node], edges:[5,11673,527080,5,11673,527072,5,11673,527056,...]type存储的边的类型也是节点之间引⽤关系的类型例如第⼀⾏的例⼦代表这条边的类型是⼀个shotcutedge_types:[[context,element,property,internal,hidden,shortcut,weak],string_or_number,node],context //暂时没有用处element //DOMTree中的元素property //类当中的属性internal //内部属性hidden //隐藏属性shortcut //和property中差不多通过赋值得到的引用weak //弱引用name or__index存储的是strings中的名字index11673对应的是-subroot-字符串to_node代表的是这条边指向的节点索引因为内存引用构成是一个有向图所以还需要知道这条边来自于哪个节点。边属于哪个节点的计算是通过内存节点索引边来进行计算的举个例子如果一个节点的序号是0有10条边那么edges[0,10)就是属于节点0的如果序号1的节点有5条边那么edges[10,15)就是属于节点1的。▐构建边的索引内存节点的属性edge_count代表该节点持有的边的数量由此可以算出每个节点持有边的索引范围[firstEdgeIndexes[nodeOrdinal], firstEdgeIndexes[nodeOrdinal1])private void buildEdgeIndexes() { firstEdgeIndexes[nodeCount] edges.length; int nodeOrdinal 0; for (int edgeIndex 0; nodeOrdinal nodeCount; nodeOrdinal) { firstEdgeIndexes[nodeOrdinal] edgeIndex; //nodes[nodeOrdinal * nodeFieldCount nodeEdgeCountOffset]当前节点持有边的个数 edgeIndex nodes[nodeOrdinal * nodeFieldCount nodeEdgeCountOffset] * edgeFieldsCount; } }▐构建前驱节点构建前驱节点的算法⽐较巧妙1. 遍历所有的边找到边的toNode然后计算toNode的前驱节点(retainer)的数量存储在 firstRetainerIndex 中和firstEdgeIndexes类型每个节点的前驱节点的范围也计算出来了就是[firstRetainerIndex[nodeOrdinal], firstRetainerIndex[nodeOrdinal1])int edgeLength edges.length; for (int edgeToNodeIndex edgeToNodeOffset; edgeToNodeIndex edgeLength; edgeToNodeIndex edgeFieldsCount) { int toNodeIndex edges[edgeToNodeIndex]; if (toNodeIndex % nodeFieldCount ! 0) { TBPLogger.error(Invalid toNodeIndex is {}, new Object[] {toNodeIndex}); } else { int toNodeOrdinal toNodeIndex / nodeFieldCount; if (isValid(toNodeOrdinal, firstRetainerIndex.length)) { firstRetainerIndex[toNodeOrdinal]; } } }2. 遍历所有的节点然后为前驱节点预留好位置retainingNodes是前驱节点的集合int firstUnusedRetainerSlot 0; for (int nodeOrdinal 0; nodeOrdinal nodeCount; nodeOrdinal) { int retainerCount firstRetainerIndex[nodeOrdinal]; firstRetainerIndex[nodeOrdinal] firstUnusedRetainerSlot; if (isValid(firstUnusedRetainerSlot, edgeCount)) { retainingNodes[firstUnusedRetainerSlot] retainerCount; firstUnusedRetainerSlot retainerCount; }}3. 遍历所有的节点再根据节点持有的边找到toNode那么该节点就是toNode的前驱节点for (srcNodeOrdinal 0; srcNodeOrdinal nodeCount; srcNodeOrdinal) { firstEdgeIndex nextNodeFirstEdgeIndex; nextNodeFirstEdgeIndex firstEdgeIndexes[srcNodeOrdinal 1]; srcNodeIndex srcNodeOrdinal * nodeFieldCount; for (int edgeIndex firstEdgeIndex; edgeIndex nextNodeFirstEdgeIndex; edgeIndex edgeFieldsCount) { int index edgeIndex edgeToNodeOffset; if (isValid(index, edges.length)) { int toNodeIndex edges[index]; if (toNodeIndex % nodeFieldCount ! 0) { TBPLogger.error(Invalid toNodeIndex is {}., new Object[]{toNodeIndex}); } else if (isValid(toNodeIndex / nodeFieldCount, firstRetainerIndex.length)) { //retainningNodes的起点 int firstRetainerSlotIndex firstRetainerIndex[toNodeIndex / nodeFieldCount]; //由后向前添加直到retainingNodes[firstRetainerSlotIndex]变为了0 int nextUnusedRetainerSlotIndex firstRetainerSlotIndex (--retainingNodes[firstRetainerSlotIndex]); if (isValid(nextUnusedRetainerSlotIndex, retainingNodes.length) isValid(nextUnusedRetainerSlotIndex, retainingEdges.length)) { retainingNodes[nextUnusedRetainerSlotIndex] srcNodeIndex; retainingEdges[nextUnusedRetainerSlotIndex] edgeIndex; } } } }}▐计算节点distance计算节点就是使⽤bfs进⾏遍历private void calculateDistances() { for (int nodeOrdinal 0; nodeOrdinal nodeCount; nodeOrdinal) { nodeDistances[nodeOrdinal] noDistance; } int[] nodesToVisit new int[nodeCount]; int nodesToVisitLength 0; //遍历根节点 for (int edgeIndex firstEdgeIndexes[rootNodeIndexInternal]; edgeIndex firstEdgeIndexes[rootNodeIndexInternal 1];edgeIndex edgeFieldsCount) { int childNodeIndex edges[edgeIndex edgeToNodeOffset]; int childNodeOrdinal childNodeIndex / nodeFieldCount; if (isUserRoot(childNodeIndex)) { nodeDistances[childNodeOrdinal] 1; bfsNodes[bfsIndex] childNodeOrdinal; nodesToVisit[nodesToVisitLength] childNodeIndex; } } //从根节点进行遍历 bfs(nodesToVisit, nodesToVisitLength, nodeDistances); nodeDistances[rootNodeIndexInternal / nodeFieldCount] nodesToVisitLength 0 ? -1 : 0;; nodesToVisit[0] rootNodeIndexInternal; nodesToVisitLength 1; //遍历其他单独的节点synthetic节点 bfs(nodesToVisit, nodesToVisitLength, nodeDistances);}▐构建⽀配树chrome的开发者⼯具和鸿蒙IDE的profiler插件使⽤的都是优化过的迭代算法参考论⽂《A Simple, Fast Dominance Algorithm》有两个重要的优化点计算节点的Dom顺序不是采⽤先序遍历⽽是采⽤逆后序进⾏遍历加速收敛。从基础知识那⾥可以得知dfs树有四种边其中前向边和树边先序遍历和逆后序遍历都是⼀次遍历就可以计算对于返祖边都是需要多次遍历才能计算但对于横叉边逆后序只需要⼀次遍历⽽先序遍历就要多次。在计算 Dom(p) 的交集的朴素算法是对所有前驱节点的⽀配节点⼀⼀查找匹配这样的效率很低很低甚⾄可以到达 O(n2) 。论⽂中提出了⼀个新的⽅案由于前驱节点的dom树已经构建完成例如下图dom(7) {7,1,0}, dom(6) {6,2,1,0} dom(3) {3,2,1,0}此时求dom(5)通过观察很容易发现dom(5){5,1,0}。根据树的特点求解 idom(n)就转换为求解n的前驱节点在⽀配树上的公共祖先节点。这⾥给出论⽂中的伪代码⽅便理解。具体实现代码可以参考chrome的代码HeapSnapshot.tsgithub.com/ChromeDevTools/devtools-frontend/blob/chromium/6194/front_end/entrypoints/heap_snapshot_worker/HeapSnapshot.ts计算⽀配节点的核⼼就在intersect⽅法中找当前节点的dom和前驱节点之间的最近公共祖先优化后的迭代算法可以降低到m是遍历次数logn是⽀配树的深度更进⼀步如果m是⼀个常量的话⼀般算法复杂度可以做到。▐计算retainSizeretainSize就是如果通过GC释放这个内存节点能释放的内存⼤⼩。计算⽀配树的⽬的就是确定节点的retainSize 当前节点的shallowSize(⾃身⼤⼩) ⽀配节点的retainSize。void calculateRetainedSizes(int[] postOrderIndex2NodeOrdinal) { int postOrderIndex; for (postOrderIndex 0; postOrderIndex nodeCount;postOrderIndex) { retainedSizes[postOrderIndex] nodes[postOrderIndex *nodeFieldCount nodeSelfSizeOffset]; if (nodeNativeSizeOffset ! 0) { retainedNativeSizes[postOrderIndex] (long)nodes[postOrderIndex * nodeFieldCount nodeNativeSizeOffset]; } } //后序遍历让被支配节点先于支配节点计算retainSize for (postOrderIndex 0; postOrderIndex nodeCount - 1;postOrderIndex) { int nodeOrdinal postOrderIndex2NodeOrdinal[postOrderIndex]; int dominatorOrdinal 0; if (isValid(nodeOrdinal, dominatorsTree.length)) { dominatorOrdinal dominatorsTree[nodeOrdinal]; } if (isValid(dominatorOrdinal, retainedSizes.length) isValid(nodeOrdinal, retainedSizes.length)) { retainedSizes[dominatorOrdinal] retainedSizes[nodeOrdinal]; if (nodeNativeSizeOffset ! 0) { retainedNativeSizes[dominatorOrdinal] retainedNativeSizes[nodeOrdinal]; } } } }▐聚合计算虽然最难的部分⽀配树已经计算完成但还需要将引⽤链聚合起来⽅便⼈⼯分析和上报到平台进⾏⾃动化分析。具体流程如下1. 先遍历所有节点拿到所有节点的stringIndex根据stringIndex进⾏聚合可以得到对象类型的retainSize和个数然后进⾏过滤掉⼀些泄漏不多的对象类型得到⼤对象类型。public MapInteger, ConstructorNode getBigHeapNode() { MapInteger, ConstructorNode heapNodes new HashMap(nodeCount); for (int nodeOrdinal 0; nodeOrdinal nodeCount; nodeOrdinal) { int nodeIndex nodeOrdinal * nodeFieldCount; if (isHidden(nodeIndex)) { continue; } if (isSynthetic(nodeIndex)) { continue; } int stringIndex nodes[nodeIndex nodeNameOffset]; if (heapNodes.containsKey(stringIndex)) { ConstructorNode heapNode heapNodes.get(stringIndex); heapNode.addRetainedSize(1, retainedSizes[nodeOrdinal]); } else { String constructorName strings.get(stringIndex); if (HarmonyAnalyzeUtils.containsTaobao(constructorName)) { ConstructorNode heapNode new ConstructorNode(stringIndex, constructorName, 1,retainedSizes[nodeOrdinal]); heapNodes.put(stringIndex, heapNode); } } } ConfigParams configParams CmdArgs.getInstance().getConfigParams(); MapInteger, ConstructorNode bigNodes new HashMap(); for (ConstructorNode heapNode : heapNodes.values()) { if (heapNode.getRetainedSize() configParams.minRetainedSize || heapNode.getCount() configParams.minLeakCount) { bigNodes.put(heapNode.getStringIndex(), heapNode); } } return bigNodes;}2. 重新通过bfs的顺序遍历节点如果是⼤对象类型就进⾏回溯找到到根节点的路径并记录下来最后进⾏根据引⽤路径进⾏聚合成aggregatedRefTree。private void aggregateReferenceTree() { MapInteger, ConstructorNode bigNodes getTBHeapNode(); //对节点进行bfs for (int i 0; i bfsIndex; i) { int nodeOrdinal bfsNodes[i]; int nodeIndex nodeOrdinal * nodeFieldCount; int stringIndex nodes[nodeIndex nodeNameOffset]; if (bigNodes.containsKey(stringIndex)) { MapString, ListConstructorNode referenceTrees new HashMap(); calculateReferenceTree(nodeOrdinal, new StringBuilder(), new ArrayList(), referenceTrees); for (String key : referenceTrees.keySet()) { ListConstructorNode refChain referenceTrees.get(key); if (aggregatedRefTree.containsKey(key)) { ConstructorNode cached aggregatedRefTree.get(key).get(0); //相同节点的链路不用相加 if (cached refChain.get(0)) { continue; } cached.addCount(); cached.addRetainedSize(retainedSizes[nodeOrdinal]); cached.addShallowSize(nodes[nodeIndex nodeSelfSizeOffset]); } else { if (!refChain.isEmpty()) { aggregatedRefTree.put(key, refChain); } } } } }}private void calculateReferenceTree(int nodeOrdinal, StringBuilder pathKey, ListConstructorNode refChain, MapString, ListConstructorNode referenceTree) { int nodeIndex nodeOrdinal * nodeFieldCount; int stringIndex nodes[nodeIndex nodeNameOffset]; pathKey.append(stringIndex).append(-); ConstructorNode node new ConstructorNode(stringIndex, strings.get(stringIndex), nodeDistances[nodeOrdinal]); refChain.add(node); if (nodeDistances[nodeOrdinal] 1) { String key pathKey.toString(); ListConstructorNode newRefChain new ArrayList(refChain); referenceTree.put(key, newRefChain); return; } ListInteger retainers findRetainers(nodeOrdinal); for (Integer retainer : retainers) { StringBuilder newPathKey new StringBuilder(pathKey); ListConstructorNode newRefChain new ArrayList(refChain); calculateReferenceTree(retainer, newPathKey, newRefChain, referenceTree); }}总结⽀配树算法属于是内存泄漏/溢出分析的核⼼算法我们基于此算法实现鸿蒙ArkTS内存镜像分析⼯具希望本⽂对⼤家实现类似功能的⼯具有⼀定帮助。参考⽂档《A Simple, Fast Dominance Algorithm》https://www.cs.tufts.edu/~nr/cs257/archive/keith-cooper/dom14.pdf《A New, Simpler Linear-Time Dominators Algorithm》http://adambuchsbaum.com/papers/dom-toplas.pdf《A Fast Algorithm for Finding Dominators in a Flowgraph》https://faculty.cc.gatech.edu/~harrold/6340/cs6340_fall2009/Readings/lengauer91jul.pdf团队介绍本文作者灵貎来自淘天集团-终端平台基础工程团队团队负责淘宝App基础架构和基础链路业务致力于通过技术创新和系统优化打造一个更稳定、更流畅的手机淘宝。同时我们也在持续探索通过AI搭建高效、智能的研发体系提升团队的研发效能。¤拓展阅读¤3DXR技术 | 终端技术 | 音视频技术服务端技术 | 技术质量 | 数据算法