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 */ 34function 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 */ 65CodeMap.PAGE_ALIGNMENT = 12; 66 67 68/** 69 * Page size in bytes. 70 */ 71CodeMap.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 */ 81CodeMap.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 */ 94CodeMap.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 */ 107CodeMap.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 */ 118CodeMap.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 */ 131CodeMap.prototype.addStaticCode = function( 132 start, codeEntry) { 133 this.statics_.insert(start, codeEntry); 134}; 135 136 137/** 138 * @private 139 */ 140CodeMap.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 */ 151CodeMap.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 */ 168CodeMap.prototype.isAddressBelongsTo_ = function(addr, node) { 169 return addr >= node.key && addr < (node.key + node.value.size); 170}; 171 172 173/** 174 * @private 175 */ 176CodeMap.prototype.findInTree_ = function(tree, addr) { 177 var node = tree.findGreatestLessThan(addr); 178 return node && this.isAddressBelongsTo_(addr, node) ? node : null; 179}; 180 181/** 182 * Embedded builtins are located in the shared library but should be attributed 183 * according to the dynamically generated code-create events. 184 * 185 * @private 186 */ 187CodeMap.prototype.isIsolateIndependentBuiltin_ = function(entry) { 188 return entry.type == "CPP" && /v8_\w*embedded_blob_/.test(entry.name); 189}; 190 191/** 192 * Finds a code entry that contains the specified address. Both static and 193 * dynamic code entries are considered. Returns the code entry and the offset 194 * within the entry. 195 * 196 * @param {number} addr Address. 197 */ 198CodeMap.prototype.findAddress = function(addr) { 199 var pageAddr = addr >>> CodeMap.PAGE_ALIGNMENT; 200 if (pageAddr in this.pages_) { 201 // Static code entries can contain "holes" of unnamed code. 202 // In this case, the whole library is assigned to this address. 203 var result = this.findInTree_(this.statics_, addr); 204 if (!result) { 205 result = this.findInTree_(this.libraries_, addr); 206 if (!result) return null; 207 } 208 if (!this.isIsolateIndependentBuiltin_(result.value)) { 209 // Embedded builtins are handled in the following dynamic section. 210 return { entry : result.value, offset : addr - result.key }; 211 } 212 } 213 var min = this.dynamics_.findMin(); 214 var max = this.dynamics_.findMax(); 215 if (max != null && addr < (max.key + max.value.size) && addr >= min.key) { 216 var dynaEntry = this.findInTree_(this.dynamics_, addr); 217 if (dynaEntry == null) return null; 218 // Dedupe entry name. 219 var entry = dynaEntry.value; 220 if (!entry.nameUpdated_) { 221 entry.name = this.dynamicsNameGen_.getName(entry.name); 222 entry.nameUpdated_ = true; 223 } 224 return { entry : entry, offset : addr - dynaEntry.key }; 225 } 226 return null; 227}; 228 229 230/** 231 * Finds a code entry that contains the specified address. Both static and 232 * dynamic code entries are considered. 233 * 234 * @param {number} addr Address. 235 */ 236CodeMap.prototype.findEntry = function(addr) { 237 var result = this.findAddress(addr); 238 return result ? result.entry : null; 239}; 240 241 242/** 243 * Returns a dynamic code entry using its starting address. 244 * 245 * @param {number} addr Address. 246 */ 247CodeMap.prototype.findDynamicEntryByStartAddress = 248 function(addr) { 249 var node = this.dynamics_.find(addr); 250 return node ? node.value : null; 251}; 252 253 254/** 255 * Returns an array of all dynamic code entries. 256 */ 257CodeMap.prototype.getAllDynamicEntries = function() { 258 return this.dynamics_.exportValues(); 259}; 260 261 262/** 263 * Returns an array of pairs of all dynamic code entries and their addresses. 264 */ 265CodeMap.prototype.getAllDynamicEntriesWithAddresses = function() { 266 return this.dynamics_.exportKeysAndValues(); 267}; 268 269 270/** 271 * Returns an array of all static code entries. 272 */ 273CodeMap.prototype.getAllStaticEntries = function() { 274 return this.statics_.exportValues(); 275}; 276 277 278/** 279 * Returns an array of pairs of all static code entries and their addresses. 280 */ 281CodeMap.prototype.getAllStaticEntriesWithAddresses = function() { 282 return this.statics_.exportKeysAndValues(); 283}; 284 285 286/** 287 * Returns an array of all libraries entries. 288 */ 289CodeMap.prototype.getAllLibrariesEntries = function() { 290 return this.libraries_.exportValues(); 291}; 292 293 294/** 295 * Creates a code entry object. 296 * 297 * @param {number} size Code entry size in bytes. 298 * @param {string} opt_name Code entry name. 299 * @param {string} opt_type Code entry type, e.g. SHARED_LIB, CPP. 300 * @constructor 301 */ 302CodeMap.CodeEntry = function(size, opt_name, opt_type) { 303 this.size = size; 304 this.name = opt_name || ''; 305 this.type = opt_type || ''; 306 this.nameUpdated_ = false; 307}; 308 309 310CodeMap.CodeEntry.prototype.getName = function() { 311 return this.name; 312}; 313 314 315CodeMap.CodeEntry.prototype.toString = function() { 316 return this.name + ': ' + this.size.toString(16); 317}; 318 319 320CodeMap.NameGenerator = function() { 321 this.knownNames_ = {}; 322}; 323 324 325CodeMap.NameGenerator.prototype.getName = function(name) { 326 if (!(name in this.knownNames_)) { 327 this.knownNames_[name] = 0; 328 return name; 329 } 330 var count = ++this.knownNames_[name]; 331 return name + ' {' + count + '}'; 332}; 333