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.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 */
188CodeMap.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 */
217CodeMap.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 */
227CodeMap.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 */
235CodeMap.prototype.getAllDynamicEntriesWithAddresses = function() {
236  return this.dynamics_.exportKeysAndValues();
237};
238
239
240/**
241 * Returns an array of all static code entries.
242 */
243CodeMap.prototype.getAllStaticEntries = function() {
244  return this.statics_.exportValues();
245};
246
247
248/**
249 * Returns an array of all libraries entries.
250 */
251CodeMap.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 * @constructor
262 */
263CodeMap.CodeEntry = function(size, opt_name) {
264  this.size = size;
265  this.name = opt_name || '';
266  this.nameUpdated_ = false;
267};
268
269
270CodeMap.CodeEntry.prototype.getName = function() {
271  return this.name;
272};
273
274
275CodeMap.CodeEntry.prototype.toString = function() {
276  return this.name + ': ' + this.size.toString(16);
277};
278
279
280CodeMap.NameGenerator = function() {
281  this.knownNames_ = {};
282};
283
284
285CodeMap.NameGenerator.prototype.getName = function(name) {
286  if (!(name in this.knownNames_)) {
287    this.knownNames_[name] = 0;
288    return name;
289  }
290  var count = ++this.knownNames_[name];
291  return name + ' {' + count + '}';
292};
293