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 }; 295