src/third_party/trace-viewer/trace_viewer/tracing/importer/v8/codemap.js

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 'use strict';
   6
   7 tvcm.require('tracing.importer.v8.splaytree');
   8
   9 /**
  10  * @fileoverview Map addresses to dynamically created functions.
  11  */
  12
  13 tvcm.exportTo('tracing.importer.v8', function() {
  14   /**
  15    * Constructs a mapper that maps addresses into code entries.
  16    *
  17    * @constructor
  18    */
  19   function CodeMap() {
  20     /**
  21      * Dynamic code entries. Used for JIT compiled code.
  22      */
  23     this.dynamics_ = new tracing.importer.v8.SplayTree();
  24
  25     /**
  26      * Name generator for entries having duplicate names.
  27      */
  28     this.dynamicsNameGen_ = new tracing.importer.v8.CodeMap.NameGenerator();
  29
  30     /**
  31      * Static code entries. Used for statically compiled code.
  32      */
  33     this.statics_ = new tracing.importer.v8.SplayTree();
  34
  35     /**
  36      * Libraries entries. Used for the whole static code libraries.
  37      */
  38     this.libraries_ = new tracing.importer.v8.SplayTree();
  39
  40     /**
  41      * Map of memory pages occupied with static code.
  42      */
  43     this.pages_ = [];
  44   };
  45
  46
  47   /**
  48    * The number of alignment bits in a page address.
  49    */
  50   CodeMap.PAGE_ALIGNMENT = 12;
  51
  52
  53   /**
  54    * Page size in bytes.
  55    */
  56   CodeMap.PAGE_SIZE =
  57       1 << CodeMap.PAGE_ALIGNMENT;
  58
  59
  60   /**
  61    * Adds a dynamic (i.e. moveable and discardable) code entry.
  62    *
  63    * @param {number} start The starting address.
  64    * @param {CodeMap.CodeEntry} codeEntry Code entry object.
  65    */
  66   CodeMap.prototype.addCode = function(start, codeEntry) {
  67     this.deleteAllCoveredNodes_(this.dynamics_, start, start + codeEntry.size);
  68     this.dynamics_.insert(start, codeEntry);
  69   };
  70
  71
  72   /**
  73    * Moves a dynamic code entry. Throws an exception if there is no dynamic
  74    * code entry with the specified starting address.
  75    *
  76    * @param {number} from The starting address of the entry being moved.
  77    * @param {number} to The destination address.
  78    */
  79   CodeMap.prototype.moveCode = function(from, to) {
  80     var removedNode = this.dynamics_.remove(from);
  81     this.deleteAllCoveredNodes_(this.dynamics_, to,
  82                                 to + removedNode.value.size);
  83     this.dynamics_.insert(to, removedNode.value);
  84   };
  85
  86
  87   /**
  88    * Discards a dynamic code entry. Throws an exception if there is no dynamic
  89    * code entry with the specified starting address.
  90    *
  91    * @param {number} start The starting address of the entry being deleted.
  92    */
  93   CodeMap.prototype.deleteCode = function(start) {
  94     var removedNode = this.dynamics_.remove(start);
  95   };
  96
  97
  98   /**
  99    * Adds a library entry.
 100    *
 101    * @param {number} start The starting address.
 102    * @param {CodeMap.CodeEntry} codeEntry Code entry object.
 103    */
 104   CodeMap.prototype.addLibrary = function(
 105       start, codeEntry) {
 106     this.markPages_(start, start + codeEntry.size);
 107     this.libraries_.insert(start, codeEntry);
 108   };
 109
 110
 111   /**
 112    * Adds a static code entry.
 113    *
 114    * @param {number} start The starting address.
 115    * @param {CodeMap.CodeEntry} codeEntry Code entry object.
 116    */
 117   CodeMap.prototype.addStaticCode = function(
 118       start, codeEntry) {
 119     this.statics_.insert(start, codeEntry);
 120   };
 121
 122
 123   /**
 124    * @private
 125    */
 126   CodeMap.prototype.markPages_ = function(start, end) {
 127     for (var addr = start; addr <= end;
 128          addr += CodeMap.PAGE_SIZE) {
 129       this.pages_[addr >>> CodeMap.PAGE_ALIGNMENT] = 1;
 130     }
 131   };
 132
 133
 134   /**
 135    * @private
 136    */
 137   CodeMap.prototype.deleteAllCoveredNodes_ = function(tree, start, end) {
 138     var to_delete = [];
 139     var addr = end - 1;
 140     while (addr >= start) {
 141       var node = tree.findGreatestLessThan(addr);
 142       if (!node) break;
 143       var start2 = node.key, end2 = start2 + node.value.size;
 144       if (start2 < end && start < end2) to_delete.push(start2);
 145       addr = start2 - 1;
 146     }
 147     for (var i = 0, l = to_delete.length; i < l; ++i) tree.remove(to_delete[i]);
 148   };
 149
 150
 151   /**
 152    * @private
 153    */
 154   CodeMap.prototype.isAddressBelongsTo_ = function(addr, node) {
 155     return addr >= node.key && addr < (node.key + node.value.size);
 156   };
 157
 158
 159   /**
 160    * @private
 161    */
 162   CodeMap.prototype.findInTree_ = function(tree, addr) {
 163     var node = tree.findGreatestLessThan(addr);
 164     return node && this.isAddressBelongsTo_(addr, node) ? node.value : null;
 165   };
 166
 167
 168   /**
 169    * Finds a code entry that contains the specified address. Both static and
 170    * dynamic code entries are considered.
 171    *
 172    * @param {number} addr Address.
 173    */
 174   CodeMap.prototype.findEntry = function(addr) {
 175     var pageAddr = addr >>> CodeMap.PAGE_ALIGNMENT;
 176     if (pageAddr in this.pages_) {
 177       // Static code entries can contain "holes" of unnamed code.
 178       // In this case, the whole library is assigned to this address.
 179       return this.findInTree_(this.statics_, addr) ||
 180           this.findInTree_(this.libraries_, addr);
 181     }
 182     var min = this.dynamics_.findMin();
 183     var max = this.dynamics_.findMax();
 184     if (max != null && addr < (max.key + max.value.size) && addr >= min.key) {
 185       var dynaEntry = this.findInTree_(this.dynamics_, addr);
 186       if (dynaEntry == null) return null;
 187       // Dedupe entry name.
 188       if (!dynaEntry.nameUpdated_) {
 189         dynaEntry.name = this.dynamicsNameGen_.getName(dynaEntry.name);
 190         dynaEntry.nameUpdated_ = true;
 191       }
 192       return dynaEntry;
 193     }
 194     return null;
 195   };
 196
 197
 198   /**
 199    * Returns a dynamic code entry using its starting address.
 200    *
 201    * @param {number} addr Address.
 202    */
 203   CodeMap.prototype.findDynamicEntryByStartAddress =
 204       function(addr) {
 205     var node = this.dynamics_.find(addr);
 206     return node ? node.value : null;
 207   };
 208
 209
 210   /**
 211    * Returns an array of all dynamic code entries.
 212    */
 213   CodeMap.prototype.getAllDynamicEntries = function() {
 214     return this.dynamics_.exportValues();
 215   };
 216
 217
 218   /**
 219    * Returns an array of pairs of all dynamic code entries and their addresses.
 220    */
 221   CodeMap.prototype.getAllDynamicEntriesWithAddresses = function() {
 222     return this.dynamics_.exportKeysAndValues();
 223   };
 224
 225
 226   /**
 227    * Returns an array of all static code entries.
 228    */
 229   CodeMap.prototype.getAllStaticEntries = function() {
 230     return this.statics_.exportValues();
 231   };
 232
 233
 234   /**
 235    * Returns an array of all libraries entries.
 236    */
 237   CodeMap.prototype.getAllLibrariesEntries = function() {
 238     return this.libraries_.exportValues();
 239   };
 240
 241
 242   /**
 243    * Creates a code entry object.
 244    *
 245    * @param {number} size Code entry size in bytes.
 246    * @param {string=} opt_name Code entry name.
 247    * @constructor
 248    */
 249   CodeMap.CodeEntry = function(size, opt_name) {
 250     this.id = tvcm.GUID.allocate();
 251     this.size = size;
 252     this.name = opt_name || '';
 253     this.nameUpdated_ = false;
 254   };
 255
 256
 257   CodeMap.CodeEntry.prototype.getName = function() {
 258     return this.name;
 259   };
 260
 261
 262   CodeMap.CodeEntry.prototype.toString = function() {
 263     return this.name + ': ' + this.size.toString(16);
 264   };
 265
 266
 267   CodeMap.NameGenerator = function() {
 268     this.knownNames_ = {};
 269   };
 270
 271
 272   CodeMap.NameGenerator.prototype.getName = function(name) {
 273     if (!(name in this.knownNames_)) {
 274       this.knownNames_[name] = 0;
 275       return name;
 276     }
 277     var count = ++this.knownNames_[name];
 278     return name + ' {' + count + '}';
 279   };
 280   return {
 281     CodeMap: CodeMap
 282   };
 283 });