src/v8/tools/codemap.js

   1 // Copyright 2009 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28
  29 /**
  30  * Constructs a mapper that maps addresses into code entries.
  31  *
  32  * @constructor
  33  */
  34 function CodeMap() {
  35   /**
  36    * Dynamic code entries. Used for JIT compiled code.
  37    */
  38   this.dynamics_ = new SplayTree();
  39
  40   /**
  41    * Name generator for entries having duplicate names.
  42    */
  43   this.dynamicsNameGen_ = new CodeMap.NameGenerator();
  44
  45   /**
  46    * Static code entries. Used for statically compiled code.
  47    */
  48   this.statics_ = new SplayTree();
  49
  50   /**
  51    * Libraries entries. Used for the whole static code libraries.
  52    */
  53   this.libraries_ = new SplayTree();
  54
  55   /**
  56    * Map of memory pages occupied with static code.
  57    */
  58   this.pages_ = [];
  59 };
  60
  61
  62 /**
  63  * The number of alignment bits in a page address.
  64  */
  65 CodeMap.PAGE_ALIGNMENT = 12;
  66
  67
  68 /**
  69  * Page size in bytes.
  70  */
  71 CodeMap.PAGE_SIZE =
  72     1 << CodeMap.PAGE_ALIGNMENT;
  73
  74
  75 /**
  76  * Adds a dynamic (i.e. moveable and discardable) code entry.
  77  *
  78  * @param {number} start The starting address.
  79  * @param {CodeMap.CodeEntry} codeEntry Code entry object.
  80  */
  81 CodeMap.prototype.addCode = function(start, codeEntry) {
  82   this.deleteAllCoveredNodes_(this.dynamics_, start, start + codeEntry.size);
  83   this.dynamics_.insert(start, codeEntry);
  84 };
  85
  86
  87 /**
  88  * Moves a dynamic code entry. Throws an exception if there is no dynamic
  89  * code entry with the specified starting address.
  90  *
  91  * @param {number} from The starting address of the entry being moved.
  92  * @param {number} to The destination address.
  93  */
  94 CodeMap.prototype.moveCode = function(from, to) {
  95   var removedNode = this.dynamics_.remove(from);
  96   this.deleteAllCoveredNodes_(this.dynamics_, to, to + removedNode.value.size);
  97   this.dynamics_.insert(to, removedNode.value);
  98 };
  99
 100
 101 /**
 102  * Discards a dynamic code entry. Throws an exception if there is no dynamic
 103  * code entry with the specified starting address.
 104  *
 105  * @param {number} start The starting address of the entry being deleted.
 106  */
 107 CodeMap.prototype.deleteCode = function(start) {
 108   var removedNode = this.dynamics_.remove(start);
 109 };
 110
 111
 112 /**
 113  * Adds a library entry.
 114  *
 115  * @param {number} start The starting address.
 116  * @param {CodeMap.CodeEntry} codeEntry Code entry object.
 117  */
 118 CodeMap.prototype.addLibrary = function(
 119     start, codeEntry) {
 120   this.markPages_(start, start + codeEntry.size);
 121   this.libraries_.insert(start, codeEntry);
 122 };
 123
 124
 125 /**
 126  * Adds a static code entry.
 127  *
 128  * @param {number} start The starting address.
 129  * @param {CodeMap.CodeEntry} codeEntry Code entry object.
 130  */
 131 CodeMap.prototype.addStaticCode = function(
 132     start, codeEntry) {
 133   this.statics_.insert(start, codeEntry);
 134 };
 135
 136
 137 /**
 138  * @private
 139  */
 140 CodeMap.prototype.markPages_ = function(start, end) {
 141   for (var addr = start; addr <= end;
 142        addr += CodeMap.PAGE_SIZE) {
 143     this.pages_[addr >>> CodeMap.PAGE_ALIGNMENT] = 1;
 144   }
 145 };
 146
 147
 148 /**
 149  * @private
 150  */
 151 CodeMap.prototype.deleteAllCoveredNodes_ = function(tree, start, end) {
 152   var to_delete = [];
 153   var addr = end - 1;
 154   while (addr >= start) {
 155     var node = tree.findGreatestLessThan(addr);
 156     if (!node) break;
 157     var start2 = node.key, end2 = start2 + node.value.size;
 158     if (start2 < end && start < end2) to_delete.push(start2);
 159     addr = start2 - 1;
 160   }
 161   for (var i = 0, l = to_delete.length; i < l; ++i) tree.remove(to_delete[i]);
 162 };
 163
 164
 165 /**
 166  * @private
 167  */
 168 CodeMap.prototype.isAddressBelongsTo_ = function(addr, node) {
 169   return addr >= node.key && addr < (node.key + node.value.size);
 170 };
 171
 172
 173 /**
 174  * @private
 175  */
 176 CodeMap.prototype.findInTree_ = function(tree, addr) {
 177   var node = tree.findGreatestLessThan(addr);
 178   return node && this.isAddressBelongsTo_(addr, node) ? node.value : null;
 179 };
 180
 181
 182 /**
 183  * Finds a code entry that contains the specified address. Both static and
 184  * dynamic code entries are considered.
 185  *
 186  * @param {number} addr Address.
 187  */
 188 CodeMap.prototype.findEntry = function(addr) {
 189   var pageAddr = addr >>> CodeMap.PAGE_ALIGNMENT;
 190   if (pageAddr in this.pages_) {
 191     // Static code entries can contain "holes" of unnamed code.
 192     // In this case, the whole library is assigned to this address.
 193     return this.findInTree_(this.statics_, addr) ||
 194         this.findInTree_(this.libraries_, addr);
 195   }
 196   var min = this.dynamics_.findMin();
 197   var max = this.dynamics_.findMax();
 198   if (max != null && addr < (max.key + max.value.size) && addr >= min.key) {
 199     var dynaEntry = this.findInTree_(this.dynamics_, addr);
 200     if (dynaEntry == null) return null;
 201     // Dedupe entry name.
 202     if (!dynaEntry.nameUpdated_) {
 203       dynaEntry.name = this.dynamicsNameGen_.getName(dynaEntry.name);
 204       dynaEntry.nameUpdated_ = true;
 205     }
 206     return dynaEntry;
 207   }
 208   return null;
 209 };
 210
 211
 212 /**
 213  * Returns a dynamic code entry using its starting address.
 214  *
 215  * @param {number} addr Address.
 216  */
 217 CodeMap.prototype.findDynamicEntryByStartAddress =
 218     function(addr) {
 219   var node = this.dynamics_.find(addr);
 220   return node ? node.value : null;
 221 };
 222
 223
 224 /**
 225  * Returns an array of all dynamic code entries.
 226  */
 227 CodeMap.prototype.getAllDynamicEntries = function() {
 228   return this.dynamics_.exportValues();
 229 };
 230
 231
 232 /**
 233  * Returns an array of pairs of all dynamic code entries and their addresses.
 234  */
 235 CodeMap.prototype.getAllDynamicEntriesWithAddresses = function() {
 236   return this.dynamics_.exportKeysAndValues();
 237 };
 238
 239
 240 /**
 241  * Returns an array of all static code entries.
 242  */
 243 CodeMap.prototype.getAllStaticEntries = function() {
 244   return this.statics_.exportValues();
 245 };
 246
 247
 248 /**
 249  * Returns an array of all libraries entries.
 250  */
 251 CodeMap.prototype.getAllLibrariesEntries = function() {
 252   return this.libraries_.exportValues();
 253 };
 254
 255
 256 /**
 257  * Creates a code entry object.
 258  *
 259  * @param {number} size Code entry size in bytes.
 260  * @param {string} opt_name Code entry name.
 261  * @param {string} opt_type Code entry type, e.g. SHARED_LIB, CPP.
 262  * @constructor
 263  */
 264 CodeMap.CodeEntry = function(size, opt_name, opt_type) {
 265   this.size = size;
 266   this.name = opt_name || '';
 267   this.type = opt_type || '';
 268   this.nameUpdated_ = false;
 269 };
 270
 271
 272 CodeMap.CodeEntry.prototype.getName = function() {
 273   return this.name;
 274 };
 275
 276
 277 CodeMap.CodeEntry.prototype.toString = function() {
 278   return this.name + ': ' + this.size.toString(16);
 279 };
 280
 281
 282 CodeMap.NameGenerator = function() {
 283   this.knownNames_ = {};
 284 };
 285
 286
 287 CodeMap.NameGenerator.prototype.getName = function(name) {
 288   if (!(name in this.knownNames_)) {
 289     this.knownNames_[name] = 0;
 290     return name;
 291   }
 292   var count = ++this.knownNames_[name];
 293   return name + ' {' + count + '}';
 294 };