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
7base.require('tracing.importer.v8.splaytree');
8
9/**
10 * @fileoverview Map addresses to dynamically created functions.
11 */
12
13base.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.size = size;
251    this.name = opt_name || '';
252    this.nameUpdated_ = false;
253  };
254
255
256  CodeMap.CodeEntry.prototype.getName = function() {
257    return this.name;
258  };
259
260
261  CodeMap.CodeEntry.prototype.toString = function() {
262    return this.name + ': ' + this.size.toString(16);
263  };
264
265
266  CodeMap.NameGenerator = function() {
267    this.knownNames_ = {};
268  };
269
270
271  CodeMap.NameGenerator.prototype.getName = function(name) {
272    if (!(name in this.knownNames_)) {
273      this.knownNames_[name] = 0;
274      return name;
275    }
276    var count = ++this.knownNames_[name];
277    return name + ' {' + count + '}';
278  };
279  return {
280    CodeMap: CodeMap
281  };
282});
283