1<!DOCTYPE html> 2<!-- 3Copyright (c) 2015 The Chromium Authors. All rights reserved. 4Use of this source code is governed by a BSD-style license that can be 5found in the LICENSE file. 6--> 7 8<link rel="import" href="/tracing/base/iteration_helpers.html"> 9<link rel="import" href="/tracing/model/container_memory_dump.html"> 10<link rel="import" href="/tracing/model/event_registry.html"> 11<link rel="import" href="/tracing/model/memory_allocator_dump.html"> 12<link rel="import" href="/tracing/value/numeric.html"> 13<link rel="import" href="/tracing/value/unit.html"> 14 15<script> 16'use strict'; 17 18/** 19 * @fileoverview Provides the GlobalMemoryDump class. 20 */ 21tr.exportTo('tr.model', function() { 22 /** 23 * The GlobalMemoryDump represents a simultaneous memory dump of all 24 * processes. 25 * @constructor 26 */ 27 function GlobalMemoryDump(model, start) { 28 tr.model.ContainerMemoryDump.call(this, start); 29 this.model = model; 30 this.processMemoryDumps = {}; 31 } 32 33 // Size numeric names. 34 var SIZE_NUMERIC_NAME = tr.model.MemoryAllocatorDump.SIZE_NUMERIC_NAME; 35 var EFFECTIVE_SIZE_NUMERIC_NAME = 36 tr.model.MemoryAllocatorDump.EFFECTIVE_SIZE_NUMERIC_NAME; 37 38 // Size numeric info types. 39 var MemoryAllocatorDumpInfoType = tr.model.MemoryAllocatorDumpInfoType; 40 var PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN = 41 MemoryAllocatorDumpInfoType.PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN; 42 var PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER = 43 MemoryAllocatorDumpInfoType.PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER; 44 45 // TODO(petrcermak): Move this to tracing/base/iteration_helpers.html. 46 function inPlaceFilter(array, predicate, opt_this) { 47 opt_this = opt_this || this; 48 var nextPosition = 0; 49 for (var i = 0; i < array.length; i++) { 50 if (!predicate.call(opt_this, array[i], i)) 51 continue; 52 if (nextPosition < i) 53 array[nextPosition] = array[i]; // Move elements only if necessary. 54 nextPosition++; 55 } 56 57 if (nextPosition < array.length) 58 array.length = nextPosition; // Truncate the array only if necessary. 59 } 60 61 function getSize(dump) { 62 var numeric = dump.numerics[SIZE_NUMERIC_NAME]; 63 if (numeric === undefined) 64 return 0; 65 return numeric.value; 66 } 67 68 function hasSize(dump) { 69 return dump.numerics[SIZE_NUMERIC_NAME] !== undefined; 70 } 71 72 function optional(value, defaultValue) { 73 if (value === undefined) 74 return defaultValue; 75 return value; 76 } 77 78 GlobalMemoryDump.prototype = { 79 __proto__: tr.model.ContainerMemoryDump.prototype, 80 81 get userFriendlyName() { 82 return 'Global memory dump at ' + 83 tr.v.Unit.byName.timeStampInMs.format(this.start); 84 }, 85 86 get containerName() { 87 return 'global space'; 88 }, 89 90 finalizeGraph: function() { 91 // 1. Transitively remove weak memory allocator dumps and all their 92 // owners and descendants from the model. This must be performed before 93 // any other steps. 94 this.removeWeakDumps(); 95 96 // 2. Add ownership links from tracing MADs to descendants of malloc or 97 // winheap MADs so that tracing would be automatically discounted from 98 // them later (step 3). 99 this.setUpTracingOverheadOwnership(); 100 101 // 3. Aggregate all other numerics of all MADs (*excluding* sizes and 102 // effective sizes) and propagate numerics from global MADs to their 103 // owners (*including* sizes and effective sizes). This step must be 104 // carried out before the sizes of all MADs are calculated (step 3). 105 // Otherwise, the propagated sizes of all MADs would not be aggregated. 106 this.aggregateNumerics(); 107 108 // 4. Calculate the sizes of all memory allocator dumps (MADs). This step 109 // requires that the memory allocator dump graph has been finalized (step 110 // 1) and numerics were propagated from global MADs (step 2). Subsequent 111 // modifications of the graph will most likely break the calculation 112 // invariants. 113 this.calculateSizes(); 114 115 // 5. Calculate the effective sizes of all MADs. This step requires that 116 // the sizes of all MADs have already been calculated (step 3). 117 this.calculateEffectiveSizes(); 118 119 // 6. Discount tracing from VM regions stats. This steps requires that 120 // resident sizes (step 2) and sizes (step 3) of the tracing MADs have 121 // already been calculated. 122 this.discountTracingOverheadFromVmRegions(); 123 124 // 7. The above steps (especially steps 1 and 3) can create new memory 125 // allocator dumps, so we force rebuilding the memory allocator dump 126 // indices of all container memory dumps. 127 this.forceRebuildingMemoryAllocatorDumpByFullNameIndices(); 128 }, 129 130 removeWeakDumps: function() { 131 // Mark all transitive owners and children of weak memory allocator dumps 132 // as weak. 133 this.traverseAllocatorDumpsInDepthFirstPreOrder(function(dump) { 134 if (dump.weak) 135 return; 136 if ((dump.owns !== undefined && dump.owns.target.weak) || 137 (dump.parent !== undefined && dump.parent.weak)) { 138 dump.weak = true; 139 } 140 }); 141 142 function removeWeakDumpsFromListRecursively(dumps) { 143 inPlaceFilter(dumps, function(dump) { 144 if (dump.weak) { 145 // The dump is weak, so remove it. This will implicitly remove all 146 // its descendants, which are also weak due to the initial marking 147 // step. 148 return false; 149 } 150 151 // This dump is non-weak, so keep it. Recursively remove its weak 152 // descendants and ownership links from weak dumps instead. 153 removeWeakDumpsFromListRecursively(dump.children); 154 inPlaceFilter(dump.ownedBy, function(ownershipLink) { 155 return !ownershipLink.source.weak; 156 }); 157 158 return true; 159 }); 160 } 161 162 this.iterateContainerDumps(function(containerDump) { 163 var memoryAllocatorDumps = containerDump.memoryAllocatorDumps; 164 if (memoryAllocatorDumps !== undefined) 165 removeWeakDumpsFromListRecursively(memoryAllocatorDumps); 166 }); 167 }, 168 169 /** 170 * Calculate the size of all memory allocator dumps in the dump graph. 171 * 172 * The size refers to the allocated size of a (sub)component. It is a 173 * natural extension of the optional size numeric provided by 174 * MemoryAllocatorDump(s): 175 * 176 * - If a MAD provides a size numeric, then its size is assumed to be 177 * equal to it. 178 * - If a MAD does not provide a size numeric, then its size is assumed 179 * to be the maximum of (1) the size of the largest owner of the MAD 180 * and (2) the aggregated size of the MAD's children. 181 * 182 * Metric motivation: "How big is a (sub)system?" 183 * 184 * Please refer to the Memory Dump Graph Metric Calculation design document 185 * for more details (https://goo.gl/fKg0dt). 186 */ 187 calculateSizes: function() { 188 this.traverseAllocatorDumpsInDepthFirstPostOrder( 189 this.calculateMemoryAllocatorDumpSize_.bind(this)); 190 }, 191 192 /** 193 * Calculate the size of the given MemoryAllocatorDump. This method assumes 194 * that the size of both the children and owners of the dump has already 195 * been calculated. 196 */ 197 calculateMemoryAllocatorDumpSize_: function(dump) { 198 // This flag becomes true if the size numeric of the current dump should 199 // be defined, i.e. if (1) the current dump's size numeric is defined, 200 // (2) the size of at least one of its children is defined or (3) the 201 // size of at least one of its owners is defined. 202 var shouldDefineSize = false; 203 204 // This helper function returns the value of the size numeric of the 205 // given dependent memory allocator dump. If the numeric is defined, the 206 // shouldDefineSize flag above is also set to true (because condition 207 // (2) or (3) is satisfied). Otherwise, zero is returned (and the flag is 208 // left unchanged). 209 function getDependencySize(dependencyDump) { 210 var numeric = dependencyDump.numerics[SIZE_NUMERIC_NAME]; 211 if (numeric === undefined) 212 return 0; 213 shouldDefineSize = true; 214 return numeric.value; 215 } 216 217 // 1. Get the size provided by the dump. If present, define a function 218 // for checking dependent size consistency (a dump must always be bigger 219 // than all its children aggregated together and/or its largest owner). 220 var sizeNumeric = dump.numerics[SIZE_NUMERIC_NAME]; 221 var size = 0; 222 var checkDependencySizeIsConsistent = function() { /* no-op */ }; 223 if (sizeNumeric !== undefined) { 224 size = sizeNumeric.value; 225 shouldDefineSize = true; 226 if (sizeNumeric.unit !== tr.v.Unit.byName.sizeInBytes_smallerIsBetter) { 227 this.model.importWarning({ 228 type: 'memory_dump_parse_error', 229 message: 'Invalid unit of \'size\' numeric of memory allocator ' + 230 'dump ' + dump.quantifiedName + ': ' + 231 sizeNumeric.unit.unitName + '.' 232 }); 233 } 234 checkDependencySizeIsConsistent = function( 235 dependencySize, dependencyInfoType, dependencyName) { 236 if (size >= dependencySize) 237 return; 238 this.model.importWarning({ 239 type: 'memory_dump_parse_error', 240 message: 'Size provided by memory allocator dump \'' + 241 dump.fullName + '\'' + 242 tr.v.Unit.byName.sizeInBytes.format(size) + 243 ') is less than ' + dependencyName + ' (' + 244 tr.v.Unit.byName.sizeInBytes.format(dependencySize) + ').' 245 }); 246 dump.infos.push({ 247 type: dependencyInfoType, 248 providedSize: size, 249 dependencySize: dependencySize 250 }); 251 }.bind(this); 252 } 253 254 // 2. Aggregate size of children. The recursive function traverses all 255 // descendants and ensures that double-counting due to ownership within a 256 // subsystem is avoided. 257 var aggregatedChildrenSize = 0; 258 // Owned child dump name -> (Owner child dump name -> overlapping size). 259 var allOverlaps = {}; 260 dump.children.forEach(function(childDump) { 261 function aggregateDescendantDump(descendantDump) { 262 // Don't count this descendant dump if it owns another descendant of 263 // the current dump (would cause double-counting). 264 var ownedDumpLink = descendantDump.owns; 265 if (ownedDumpLink !== undefined && 266 ownedDumpLink.target.isDescendantOf(dump)) { 267 // If the target owned dump is a descendant of a *different* child 268 // of the the current dump (i.e. not childDump), then we remember 269 // the ownership so that we could explain why the size of the 270 // current dump is not equal to the sum of its children. 271 var ownedChildDump = ownedDumpLink.target; 272 while (ownedChildDump.parent !== dump) 273 ownedChildDump = ownedChildDump.parent; 274 if (childDump !== ownedChildDump) { 275 var ownedBySiblingSize = getDependencySize(descendantDump); 276 if (ownedBySiblingSize > 0) { 277 var previousTotalOwnedBySiblingSize = 278 ownedChildDump.ownedBySiblingSizes.get(childDump) || 0; 279 var updatedTotalOwnedBySiblingSize = 280 previousTotalOwnedBySiblingSize + ownedBySiblingSize; 281 ownedChildDump.ownedBySiblingSizes.set( 282 childDump, updatedTotalOwnedBySiblingSize); 283 } 284 } 285 return; 286 } 287 288 // If this descendant dump is a leaf node, add its size to the 289 // aggregated size. 290 if (descendantDump.children.length === 0) { 291 aggregatedChildrenSize += getDependencySize(descendantDump); 292 return; 293 } 294 295 // If this descendant dump is an intermediate node, recurse down into 296 // its children. Note that the dump's size is NOT added because it is 297 // an aggregate of its children (would cause double-counting). 298 descendantDump.children.forEach(aggregateDescendantDump); 299 } 300 aggregateDescendantDump(childDump); 301 }); 302 checkDependencySizeIsConsistent( 303 aggregatedChildrenSize, 304 PROVIDED_SIZE_LESS_THAN_AGGREGATED_CHILDREN, 305 'the aggregated size of its children'); 306 307 // 3. Calculate the largest owner size. 308 var largestOwnerSize = 0; 309 dump.ownedBy.forEach(function(ownershipLink) { 310 var owner = ownershipLink.source; 311 var ownerSize = getDependencySize(owner); 312 largestOwnerSize = Math.max(largestOwnerSize, ownerSize); 313 }); 314 checkDependencySizeIsConsistent( 315 largestOwnerSize, 316 PROVIDED_SIZE_LESS_THAN_LARGEST_OWNER, 317 'the size of its largest owner'); 318 319 // If neither the dump nor any of its dependencies (children and owners) 320 // provide a size, do NOT add a zero size numeric. 321 if (!shouldDefineSize) { 322 // The rest of the pipeline relies on size being either a valid 323 // ScalarNumeric, or undefined. 324 delete dump.numerics[SIZE_NUMERIC_NAME]; 325 return; 326 } 327 328 // A dump must always be bigger than all its children aggregated 329 // together and/or its largest owner. 330 size = Math.max(size, aggregatedChildrenSize, largestOwnerSize); 331 332 dump.numerics[SIZE_NUMERIC_NAME] = new tr.v.ScalarNumeric( 333 tr.v.Unit.byName.sizeInBytes_smallerIsBetter, size); 334 335 // Add a virtual child to make up for extra size of the dump with 336 // respect to its children (if applicable). 337 if (aggregatedChildrenSize < size && 338 dump.children !== undefined && dump.children.length > 0) { 339 var virtualChild = new tr.model.MemoryAllocatorDump( 340 dump.containerMemoryDump, dump.fullName + '/<unspecified>'); 341 virtualChild.parent = dump; 342 dump.children.unshift(virtualChild); 343 virtualChild.numerics[SIZE_NUMERIC_NAME] = new tr.v.ScalarNumeric( 344 tr.v.Unit.byName.sizeInBytes_smallerIsBetter, 345 size - aggregatedChildrenSize); 346 } 347 }, 348 349 /** 350 * Calculate the effective size of all memory allocator dumps in the dump 351 * graph. 352 * 353 * The effective size refers to the amount of memory a particular component 354 * is using/consuming. In other words, every (reported) byte of used memory 355 * is uniquely attributed to exactly one component. Consequently, unlike 356 * size, effective size is cumulative, i.e. the sum of the effective sizes 357 * of (top-level) components is equal to the total amount of (reported) 358 * used memory. 359 * 360 * Metric motivation: "How much memory does a (sub)system use?" or "For how 361 * much memory should a (sub)system be 'charged'?" 362 * 363 * Please refer to the Memory Dump Graph Metric Calculation design document 364 * for more details (https://goo.gl/fKg0dt). 365 * 366 * This method assumes that the size of all contained memory allocator 367 * dumps has already been calculated [see calculateSizes()]. 368 */ 369 calculateEffectiveSizes: function() { 370 // 1. Calculate not-owned and not-owning sub-sizes of all MADs 371 // (depth-first post-order traversal). 372 this.traverseAllocatorDumpsInDepthFirstPostOrder( 373 this.calculateDumpSubSizes_.bind(this)); 374 375 // 2. Calculate owned and owning coefficients of owned and owner MADs 376 // respectively (arbitrary traversal). 377 this.traverseAllocatorDumpsInDepthFirstPostOrder( 378 this.calculateDumpOwnershipCoefficient_.bind(this)); 379 380 // 3. Calculate cumulative owned and owning coefficients of all MADs 381 // (depth-first pre-order traversal). 382 this.traverseAllocatorDumpsInDepthFirstPreOrder( 383 this.calculateDumpCumulativeOwnershipCoefficient_.bind(this)); 384 385 // 4. Calculate the effective sizes of all MADs (depth-first post-order 386 // traversal). 387 this.traverseAllocatorDumpsInDepthFirstPostOrder( 388 this.calculateDumpEffectiveSize_.bind(this)); 389 }, 390 391 /** 392 * Calculate not-owned and not-owning sub-sizes of a memory allocator dump 393 * from its children's (sub-)sizes. 394 * 395 * Not-owned sub-size refers to the aggregated memory of all children which 396 * is not owned by other MADs. Conversely, not-owning sub-size is the 397 * aggregated memory of all children which do not own another MAD. The 398 * diagram below illustrates these two concepts: 399 * 400 * ROOT 1 ROOT 2 401 * size: 4 size: 5 402 * not-owned sub-size: 4 not-owned sub-size: 1 (!) 403 * not-owning sub-size: 0 (!) not-owning sub-size: 5 404 * 405 * ^ ^ 406 * | | 407 * 408 * PARENT 1 ===== owns =====> PARENT 2 409 * size: 4 size: 5 410 * not-owned sub-size: 4 not-owned sub-size: 5 411 * not-owning sub-size: 4 not-owning sub-size: 5 412 * 413 * ^ ^ 414 * | | 415 * 416 * CHILD 1 CHILD 2 417 * size [given]: 4 size [given]: 5 418 * not-owned sub-size: 4 not-owned sub-size: 5 419 * not-owning sub-size: 4 not-owning sub-size: 5 420 * 421 * This method assumes that (1) the size of the dump, its children, and its 422 * owners [see calculateSizes()] and (2) the not-owned and not-owning 423 * sub-sizes of both the children and owners of the dump have already been 424 * calculated [depth-first post-order traversal]. 425 */ 426 calculateDumpSubSizes_: function(dump) { 427 // Completely skip dumps with undefined size. 428 if (!hasSize(dump)) 429 return; 430 431 // If the dump is a leaf node, then both sub-sizes are equal to the size. 432 if (dump.children === undefined || dump.children.length === 0) { 433 var size = getSize(dump); 434 dump.notOwningSubSize_ = size; 435 dump.notOwnedSubSize_ = size; 436 return; 437 } 438 439 // Calculate this dump's not-owning sub-size by summing up the not-owning 440 // sub-sizes of children MADs which do not own another MAD. 441 var notOwningSubSize = 0; 442 dump.children.forEach(function(childDump) { 443 if (childDump.owns !== undefined) 444 return; 445 notOwningSubSize += optional(childDump.notOwningSubSize_, 0); 446 }); 447 dump.notOwningSubSize_ = notOwningSubSize; 448 449 // Calculate this dump's not-owned sub-size. 450 var notOwnedSubSize = 0; 451 dump.children.forEach(function(childDump) { 452 // If the child dump is not owned, then add its not-owned sub-size. 453 if (childDump.ownedBy.length === 0) { 454 notOwnedSubSize += optional(childDump.notOwnedSubSize_, 0); 455 return; 456 } 457 // If the child dump is owned, then add the difference between its size 458 // and the largest owner. 459 var largestChildOwnerSize = 0; 460 childDump.ownedBy.forEach(function(ownershipLink) { 461 largestChildOwnerSize = Math.max( 462 largestChildOwnerSize, getSize(ownershipLink.source)); 463 }); 464 notOwnedSubSize += getSize(childDump) - largestChildOwnerSize; 465 }); 466 dump.notOwnedSubSize_ = notOwnedSubSize; 467 }, 468 469 /** 470 * Calculate owned and owning coefficients of a memory allocator dump and 471 * its owners. 472 * 473 * The owning coefficient refers to the proportion of a dump's not-owning 474 * sub-size which is attributed to the dump (only relevant to owning MADs). 475 * Conversely, the owned coefficient is the proportion of a dump's 476 * not-owned sub-size, which is attributed to it (only relevant to owned 477 * MADs). 478 * 479 * The not-owned size of the owned dump is split among its owners in the 480 * order of the ownership importance as demonstrated by the following 481 * example: 482 * 483 * memory allocator dumps 484 * OWNED OWNER1 OWNER2 OWNER3 OWNER4 485 * not-owned sub-size [given] 10 - - - - 486 * not-owning sub-size [given] - 6 7 5 8 487 * importance [given] - 2 2 1 0 488 * attributed not-owned sub-size 2 - - - - 489 * attributed not-owning sub-size - 3 4 0 1 490 * owned coefficient 2/10 - - - - 491 * owning coefficient - 3/6 4/7 0/5 1/8 492 * 493 * Explanation: Firstly, 6 bytes are split equally among OWNER1 and OWNER2 494 * (highest importance). OWNER2 owns one more byte, so its attributed 495 * not-owning sub-size is 6/2 + 1 = 4 bytes. OWNER3 is attributed no size 496 * because it is smaller than the owners with higher priority. However, 497 * OWNER4 is larger, so it's attributed the difference 8 - 7 = 1 byte. 498 * Finally, 2 bytes remain unattributed and are hence kept in the OWNED 499 * dump as attributed not-owned sub-size. The coefficients are then 500 * directly calculated as fractions of the sub-sizes and corresponding 501 * attributed sub-sizes. 502 * 503 * Note that we always assume that all ownerships of a dump overlap (e.g. 504 * OWNER3 is subsumed by both OWNER1 and OWNER2). Hence, the table could 505 * be alternatively represented as follows: 506 * 507 * owned memory range 508 * 0 1 2 3 4 5 6 7 8 9 10 509 * Priority 2 | OWNER1 + OWNER2 (split) | OWNER2 | 510 * Priority 1 | (already attributed) | 511 * Priority 0 | - - - (already attributed) - - - | OWNER4 | 512 * Remainder | - - - - - (already attributed) - - - - - - | OWNED | 513 * 514 * This method assumes that (1) the size of the dump [see calculateSizes()] 515 * and (2) the not-owned size of the dump and not-owning sub-sizes of its 516 * owners [see the first step of calculateEffectiveSizes()] have already 517 * been calculated. Note that the method doesn't make any assumptions about 518 * the order in which dumps are visited. 519 */ 520 calculateDumpOwnershipCoefficient_: function(dump) { 521 // Completely skip dumps with undefined size. 522 if (!hasSize(dump)) 523 return; 524 525 // We only need to consider owned dumps. 526 if (dump.ownedBy.length === 0) 527 return; 528 529 // Sort the owners in decreasing order of ownership importance and 530 // increasing order of not-owning sub-size (in case of equal importance). 531 var owners = dump.ownedBy.map(function(ownershipLink) { 532 return { 533 dump: ownershipLink.source, 534 importance: optional(ownershipLink.importance, 0), 535 notOwningSubSize: optional(ownershipLink.source.notOwningSubSize_, 0) 536 }; 537 }); 538 owners.sort(function(a, b) { 539 if (a.importance === b.importance) 540 return a.notOwningSubSize - b.notOwningSubSize; 541 return b.importance - a.importance; 542 }); 543 544 // Loop over the list of owners and distribute the owned dump's not-owned 545 // sub-size among them according to their ownership importance and 546 // not-owning sub-size. 547 var currentImportanceStartPos = 0; 548 var alreadyAttributedSubSize = 0; 549 while (currentImportanceStartPos < owners.length) { 550 var currentImportance = owners[currentImportanceStartPos].importance; 551 552 // Find the position of the first owner with lower priority. 553 var nextImportanceStartPos = currentImportanceStartPos + 1; 554 while (nextImportanceStartPos < owners.length && 555 owners[nextImportanceStartPos].importance === 556 currentImportance) { 557 nextImportanceStartPos++; 558 } 559 560 // Visit the owners with the same importance in increasing order of 561 // not-owned sub-size, split the owned memory among them appropriately, 562 // and calculate their owning coefficients. 563 var attributedNotOwningSubSize = 0; 564 for (var pos = currentImportanceStartPos; pos < nextImportanceStartPos; 565 pos++) { 566 var owner = owners[pos]; 567 var notOwningSubSize = owner.notOwningSubSize; 568 if (notOwningSubSize > alreadyAttributedSubSize) { 569 attributedNotOwningSubSize += 570 (notOwningSubSize - alreadyAttributedSubSize) / 571 (nextImportanceStartPos - pos); 572 alreadyAttributedSubSize = notOwningSubSize; 573 } 574 575 var owningCoefficient = 0; 576 if (notOwningSubSize !== 0) 577 owningCoefficient = attributedNotOwningSubSize / notOwningSubSize; 578 owner.dump.owningCoefficient_ = owningCoefficient; 579 } 580 581 currentImportanceStartPos = nextImportanceStartPos; 582 } 583 584 // Attribute the remainder of the owned dump's not-owned sub-size to 585 // the dump itself and calculate its owned coefficient. 586 var notOwnedSubSize = optional(dump.notOwnedSubSize_, 0); 587 var remainderSubSize = notOwnedSubSize - alreadyAttributedSubSize; 588 var ownedCoefficient = 0; 589 if (notOwnedSubSize !== 0) 590 ownedCoefficient = remainderSubSize / notOwnedSubSize; 591 dump.ownedCoefficient_ = ownedCoefficient; 592 }, 593 594 /** 595 * Calculate cumulative owned and owning coefficients of a memory allocator 596 * dump from its (non-cumulative) owned and owning coefficients and the 597 * cumulative coefficients of its parent and/or owned dump. 598 * 599 * The cumulative coefficients represent the total effect of all 600 * (non-strict) ancestor ownerships on a memory allocator dump. The 601 * cumulative owned coefficient of a MAD can be calculated simply as: 602 * 603 * cumulativeOwnedC(M) = ownedC(M) * cumulativeOwnedC(parent(M)) 604 * 605 * This reflects the assumption that if a parent of a child MAD is 606 * (partially) owned, then the parent's owner also indirectly owns (a part 607 * of) the child MAD. 608 * 609 * The cumulative owning coefficient of a MAD depends on whether the MAD 610 * owns another dump: 611 * 612 * [if M doesn't own another MAD] 613 * / cumulativeOwningC(parent(M)) 614 * cumulativeOwningC(M) = 615 * \ [if M owns another MAD] 616 * owningC(M) * cumulativeOwningC(owned(M)) 617 * 618 * The reasoning behind the first case is similar to the one for cumulative 619 * owned coefficient above. The only difference is that we don't need to 620 * include the dump's (non-cumulative) owning coefficient because it is 621 * implicitly 1. 622 * 623 * The formula for the second case is derived as follows: Since the MAD 624 * owns another dump, its memory is not included in its parent's not-owning 625 * sub-size and hence shouldn't be affected by the parent's corresponding 626 * cumulative coefficient. Instead, the MAD indirectly owns everything 627 * owned by its owned dump (and so it should be affected by the 628 * corresponding coefficient). 629 * 630 * Note that undefined coefficients (and coefficients of non-existent 631 * dumps) are implicitly assumed to be 1. 632 * 633 * This method assumes that (1) the size of the dump [see calculateSizes()], 634 * (2) the (non-cumulative) owned and owning coefficients of the dump [see 635 * the second step of calculateEffectiveSizes()], and (3) the cumulative 636 * coefficients of the dump's parent and owned MADs (if present) 637 * [depth-first pre-order traversal] have already been calculated. 638 */ 639 calculateDumpCumulativeOwnershipCoefficient_: function(dump) { 640 // Completely skip dumps with undefined size. 641 if (!hasSize(dump)) 642 return; 643 644 var cumulativeOwnedCoefficient = optional(dump.ownedCoefficient_, 1); 645 var parent = dump.parent; 646 if (dump.parent !== undefined) 647 cumulativeOwnedCoefficient *= dump.parent.cumulativeOwnedCoefficient_; 648 dump.cumulativeOwnedCoefficient_ = cumulativeOwnedCoefficient; 649 650 var cumulativeOwningCoefficient; 651 if (dump.owns !== undefined) { 652 cumulativeOwningCoefficient = dump.owningCoefficient_ * 653 dump.owns.target.cumulativeOwningCoefficient_; 654 } else if (dump.parent !== undefined) { 655 cumulativeOwningCoefficient = dump.parent.cumulativeOwningCoefficient_; 656 } else { 657 cumulativeOwningCoefficient = 1; 658 } 659 dump.cumulativeOwningCoefficient_ = cumulativeOwningCoefficient; 660 }, 661 662 /** 663 * Calculate the effective size of a memory allocator dump. 664 * 665 * In order to simplify the (already complex) calculation, we use the fact 666 * that effective size is cumulative (unlike regular size), i.e. the 667 * effective size of a non-leaf node is equal to the sum of effective sizes 668 * of its children. The effective size of a leaf MAD is calculated as: 669 * 670 * effectiveSize(M) = size(M) * cumulativeOwningC(M) * cumulativeOwnedC(M) 671 * 672 * This method assumes that (1) the size of the dump and its children [see 673 * calculateSizes()] and (2) the cumulative owning and owned coefficients 674 * of the dump (if it's a leaf node) [see the third step of 675 * calculateEffectiveSizes()] or the effective sizes of its children (if 676 * it's a non-leaf node) [depth-first post-order traversal] have already 677 * been calculated. 678 */ 679 calculateDumpEffectiveSize_: function(dump) { 680 // Completely skip dumps with undefined size. As a result, each dump will 681 // have defined effective size if and only if it has defined size. 682 if (!hasSize(dump)) { 683 // The rest of the pipeline relies on effective size being either a 684 // valid ScalarNumeric, or undefined. 685 delete dump.numerics[EFFECTIVE_SIZE_NUMERIC_NAME]; 686 return; 687 } 688 689 var effectiveSize; 690 if (dump.children === undefined || dump.children.length === 0) { 691 // Leaf dump. 692 effectiveSize = getSize(dump) * dump.cumulativeOwningCoefficient_ * 693 dump.cumulativeOwnedCoefficient_; 694 } else { 695 // Non-leaf dump. 696 effectiveSize = 0; 697 dump.children.forEach(function(childDump) { 698 if (!hasSize(childDump)) 699 return; 700 effectiveSize += 701 childDump.numerics[EFFECTIVE_SIZE_NUMERIC_NAME].value; 702 }); 703 } 704 dump.numerics[EFFECTIVE_SIZE_NUMERIC_NAME] = new tr.v.ScalarNumeric( 705 tr.v.Unit.byName.sizeInBytes_smallerIsBetter, effectiveSize); 706 }, 707 708 aggregateNumerics: function() { 709 // 1. Aggregate numerics in this global memory dump. 710 this.iterateRootAllocatorDumps(function(dump) { 711 dump.aggregateNumericsRecursively(this.model); 712 }); 713 714 // 2. Propagate numerics and diagnostics from global memory allocator 715 // dumps to their owners. 716 this.iterateRootAllocatorDumps( 717 this.propagateNumericsAndDiagnosticsRecursively); 718 719 // 3. Aggregate numerics in the associated process memory dumps. 720 tr.b.iterItems(this.processMemoryDumps, function(pid, processMemoryDump) { 721 processMemoryDump.iterateRootAllocatorDumps(function(dump) { 722 dump.aggregateNumericsRecursively(this.model); 723 }, this); 724 }, this); 725 }, 726 727 propagateNumericsAndDiagnosticsRecursively: function(globalAllocatorDump) { 728 ['numerics', 'diagnostics'].forEach(function(field) { 729 tr.b.iterItems(globalAllocatorDump[field], function(name, value) { 730 globalAllocatorDump.ownedBy.forEach(function(ownershipLink) { 731 var processAllocatorDump = ownershipLink.source; 732 if (processAllocatorDump[field][name] !== undefined) { 733 // Numerics and diagnostics provided by process memory allocator 734 // dumps themselves have precedence over numerics and diagnostics 735 // propagated from global memory allocator dumps. 736 return; 737 } 738 processAllocatorDump[field][name] = value; 739 }); 740 }); 741 }); 742 743 // Recursively propagate numerics from all child memory allocator dumps. 744 globalAllocatorDump.children.forEach( 745 this.propagateNumericsAndDiagnosticsRecursively, this); 746 }, 747 748 setUpTracingOverheadOwnership: function() { 749 tr.b.iterItems(this.processMemoryDumps, function(pid, dump) { 750 dump.setUpTracingOverheadOwnership(this.model); 751 }, this); 752 }, 753 754 discountTracingOverheadFromVmRegions: function() { 755 // TODO(petrcermak): Consider factoring out all the finalization code and 756 // constants to a single file. 757 tr.b.iterItems(this.processMemoryDumps, function(pid, dump) { 758 dump.discountTracingOverheadFromVmRegions(this.model); 759 }, this); 760 }, 761 762 forceRebuildingMemoryAllocatorDumpByFullNameIndices: function() { 763 this.iterateContainerDumps(function(containerDump) { 764 containerDump.forceRebuildingMemoryAllocatorDumpByFullNameIndex(); 765 }); 766 }, 767 768 iterateContainerDumps: function(fn) { 769 fn.call(this, this); 770 tr.b.iterItems(this.processMemoryDumps, function(pid, processDump) { 771 fn.call(this, processDump); 772 }, this); 773 }, 774 775 iterateAllRootAllocatorDumps: function(fn) { 776 this.iterateContainerDumps(function(containerDump) { 777 containerDump.iterateRootAllocatorDumps(fn, this); 778 }); 779 }, 780 781 /** 782 * Traverse the memory dump graph in a depth first post-order, i.e. 783 * children and owners of a memory allocator dump are visited before the 784 * dump itself. This method will throw an exception if the graph contains 785 * a cycle. 786 */ 787 traverseAllocatorDumpsInDepthFirstPostOrder: function(fn) { 788 var visitedDumps = new WeakSet(); 789 var openDumps = new WeakSet(); 790 791 function visit(dump) { 792 if (visitedDumps.has(dump)) 793 return; 794 795 if (openDumps.has(dump)) 796 throw new Error(dump.userFriendlyName + ' contains a cycle'); 797 openDumps.add(dump); 798 799 // Visit owners before the dumps they own. 800 dump.ownedBy.forEach(function(ownershipLink) { 801 visit.call(this, ownershipLink.source); 802 }, this); 803 804 // Visit children before parents. 805 dump.children.forEach(visit, this); 806 807 // Actually visit the current memory allocator dump. 808 fn.call(this, dump); 809 visitedDumps.add(dump); 810 811 openDumps.delete(dump); 812 } 813 814 this.iterateAllRootAllocatorDumps(visit); 815 }, 816 817 /** 818 * Traverse the memory dump graph in a depth first pre-order, i.e. 819 * children and owners of a memory allocator dump are visited after the 820 * dump itself. This method will not visit some dumps if the graph contains 821 * a cycle. 822 */ 823 traverseAllocatorDumpsInDepthFirstPreOrder: function(fn) { 824 var visitedDumps = new WeakSet(); 825 826 function visit(dump) { 827 if (visitedDumps.has(dump)) 828 return; 829 830 // If this dumps owns another dump which hasn't been visited yet, then 831 // wait for this dump to be visited later. 832 if (dump.owns !== undefined && !visitedDumps.has(dump.owns.target)) 833 return; 834 835 // If this dump's parent hasn't been visited yet, then wait for this 836 // dump to be visited later. 837 if (dump.parent !== undefined && !visitedDumps.has(dump.parent)) 838 return; 839 840 // Actually visit the current memory allocator dump. 841 fn.call(this, dump); 842 visitedDumps.add(dump); 843 844 // Visit owners after the dumps they own. 845 dump.ownedBy.forEach(function(ownershipLink) { 846 visit.call(this, ownershipLink.source); 847 }, this); 848 849 // Visit children after parents. 850 dump.children.forEach(visit, this); 851 } 852 853 this.iterateAllRootAllocatorDumps(visit); 854 } 855 }; 856 857 tr.model.EventRegistry.register( 858 GlobalMemoryDump, 859 { 860 name: 'globalMemoryDump', 861 pluralName: 'globalMemoryDumps', 862 singleViewElementName: 'tr-ui-a-container-memory-dump-sub-view', 863 multiViewElementName: 'tr-ui-a-container-memory-dump-sub-view' 864 }); 865 866 return { 867 GlobalMemoryDump: GlobalMemoryDump 868 }; 869}); 870</script> 871