1<!DOCTYPE html>
2<!--
3Copyright (c) 2012 The Chromium Authors. All rights reserved.
4Use of this source code is governed by a BSD-style license that can be
5found in the LICENSE file.
6-->
7
8<link rel="import" href="/tracing/extras/importer/v8/splaytree.html">
9
10<script>
11'use strict';
12
13/**
14 * @fileoverview Map addresses to dynamically created functions.
15 */
16tr.exportTo('tr.e.importer.v8', function() {
17  /**
18   * Constructs a mapper that maps addresses into code entries.
19   *
20   * @constructor
21   */
22  function CodeMap() {
23    /**
24     * Dynamic code entries. Used for JIT compiled code.
25     */
26    this.dynamics_ = new tr.e.importer.v8.SplayTree();
27
28    /**
29     * Name generator for entries having duplicate names.
30     */
31    this.dynamicsNameGen_ = new tr.e.importer.v8.CodeMap.NameGenerator();
32
33    /**
34     * Static code entries. Used for statically compiled code.
35     */
36    this.statics_ = new tr.e.importer.v8.SplayTree();
37
38    /**
39     * Libraries entries. Used for the whole static code libraries.
40     */
41    this.libraries_ = new tr.e.importer.v8.SplayTree();
42
43    /**
44     * Map of memory pages occupied with static code.
45     */
46    this.pages_ = [];
47  };
48
49  /**
50   * The number of alignment bits in a page address.
51   */
52  CodeMap.PAGE_ALIGNMENT = 12;
53
54  /**
55   * Page size in bytes.
56   */
57  CodeMap.PAGE_SIZE = 1 << CodeMap.PAGE_ALIGNMENT;
58
59  /**
60   * Adds a dynamic (i.e. moveable and discardable) code entry.
61   *
62   * @param {number} start The starting address.
63   * @param {CodeMap.CodeEntry} codeEntry Code entry object.
64   */
65  CodeMap.prototype.addCode = function(start, codeEntry) {
66    this.deleteAllCoveredNodes_(this.dynamics_, start, start + codeEntry.size);
67    this.dynamics_.insert(start, codeEntry);
68  };
69
70  /**
71   * Moves a dynamic code entry. Throws an exception if there is no dynamic
72   * code entry with the specified starting address.
73   *
74   * @param {number} from The starting address of the entry being moved.
75   * @param {number} to The destination address.
76   */
77  CodeMap.prototype.moveCode = function(from, to) {
78    var removedNode = this.dynamics_.remove(from);
79    this.deleteAllCoveredNodes_(this.dynamics_, to,
80                                to + removedNode.value.size);
81    this.dynamics_.insert(to, removedNode.value);
82  };
83
84  /**
85   * Discards a dynamic code entry. Throws an exception if there is no dynamic
86   * code entry with the specified starting address.
87   *
88   * @param {number} start The starting address of the entry being deleted.
89   */
90  CodeMap.prototype.deleteCode = function(start) {
91    var removedNode = this.dynamics_.remove(start);
92  };
93
94  /**
95   * Adds a library entry.
96   *
97   * @param {number} start The starting address.
98   * @param {CodeMap.CodeEntry} codeEntry Code entry object.
99   */
100  CodeMap.prototype.addLibrary = function(
101      start, codeEntry) {
102    this.markPages_(start, start + codeEntry.size);
103    this.libraries_.insert(start, codeEntry);
104  };
105
106  /**
107   * Adds a static code entry.
108   *
109   * @param {number} start The starting address.
110   * @param {CodeMap.CodeEntry} codeEntry Code entry object.
111   */
112  CodeMap.prototype.addStaticCode = function(
113      start, codeEntry) {
114    this.statics_.insert(start, codeEntry);
115  };
116
117  /**
118   * @private
119   */
120  CodeMap.prototype.markPages_ = function(start, end) {
121    for (var addr = start; addr <= end;
122         addr += CodeMap.PAGE_SIZE) {
123      this.pages_[addr >>> CodeMap.PAGE_ALIGNMENT] = 1;
124    }
125  };
126
127  /**
128   * @private
129   */
130  CodeMap.prototype.deleteAllCoveredNodes_ = function(tree, start, end) {
131    var to_delete = [];
132    var addr = end - 1;
133    while (addr >= start) {
134      var node = tree.findGreatestLessThan(addr);
135      if (!node) break;
136      var start2 = node.key, end2 = start2 + node.value.size;
137      if (start2 < end && start < end2) to_delete.push(start2);
138      addr = start2 - 1;
139    }
140    for (var i = 0, l = to_delete.length; i < l; ++i) tree.remove(to_delete[i]);
141  };
142
143  /**
144   * @private
145   */
146  CodeMap.prototype.isAddressBelongsTo_ = function(addr, node) {
147    return addr >= node.key && addr < (node.key + node.value.size);
148  };
149
150  /**
151   * @private
152   */
153  CodeMap.prototype.findInTree_ = function(tree, addr) {
154    var node = tree.findGreatestLessThan(addr);
155    return node && this.isAddressBelongsTo_(addr, node) ? node.value : null;
156  };
157
158  /**
159   * Finds a code entry that contains the specified address. Both static and
160   * dynamic code entries are considered.
161   *
162   * @param {number} addr Address.
163   */
164  CodeMap.prototype.findEntry = function(addr) {
165    var pageAddr = addr >>> CodeMap.PAGE_ALIGNMENT;
166    if (pageAddr in this.pages_) {
167      // Static code entries can contain "holes" of unnamed code.
168      // In this case, the whole library is assigned to this address.
169      return this.findInTree_(this.statics_, addr) ||
170          this.findInTree_(this.libraries_, addr);
171    }
172    var min = this.dynamics_.findMin();
173    var max = this.dynamics_.findMax();
174    if (max != null && addr < (max.key + max.value.size) && addr >= min.key) {
175      var dynaEntry = this.findInTree_(this.dynamics_, addr);
176      if (dynaEntry == null) return null;
177      // Dedupe entry name.
178      if (!dynaEntry.nameUpdated_) {
179        dynaEntry.name = this.dynamicsNameGen_.getName(dynaEntry.name);
180        dynaEntry.nameUpdated_ = true;
181      }
182      return dynaEntry;
183    }
184    return null;
185  };
186
187  /**
188   * Returns a dynamic code entry using its starting address.
189   *
190   * @param {number} addr Address.
191   */
192  CodeMap.prototype.findDynamicEntryByStartAddress =
193      function(addr) {
194    var node = this.dynamics_.find(addr);
195    return node ? node.value : null;
196  };
197
198  /**
199   * Returns an array of all dynamic code entries.
200   */
201  CodeMap.prototype.getAllDynamicEntries = function() {
202    return this.dynamics_.exportValues();
203  };
204
205  /**
206   * Returns an array of pairs of all dynamic code entries and their addresses.
207   */
208  CodeMap.prototype.getAllDynamicEntriesWithAddresses = function() {
209    return this.dynamics_.exportKeysAndValues();
210  };
211
212  /**
213   * Returns an array of all static code entries.
214   */
215  CodeMap.prototype.getAllStaticEntries = function() {
216    return this.statics_.exportValues();
217  };
218
219  /**
220   * Returns an array of all libraries entries.
221   */
222  CodeMap.prototype.getAllLibrariesEntries = function() {
223    return this.libraries_.exportValues();
224  };
225
226  /**
227   * Creates a code entry object.
228   *
229   * @param {number} size Code entry size in bytes.
230   * @param {string=} opt_name Code entry name.
231   * @constructor
232   */
233  CodeMap.CodeEntry = function(size, opt_name) {
234    this.id = tr.b.GUID.allocate();
235    this.size = size;
236    this.name = opt_name || '';
237    this.nameUpdated_ = false;
238  };
239
240  CodeMap.CodeEntry.prototype.getName = function() {
241    return this.name;
242  };
243
244  CodeMap.CodeEntry.prototype.toString = function() {
245    return this.name + ': ' + this.size.toString(16);
246  };
247
248  CodeMap.NameGenerator = function() {
249    this.knownNames_ = {};
250  };
251
252  CodeMap.NameGenerator.prototype.getName = function(name) {
253    if (!(name in this.knownNames_)) {
254      this.knownNames_[name] = 0;
255      return name;
256    }
257    var count = ++this.knownNames_[name];
258    return name + ' {' + count + '}';
259  };
260  return {
261    CodeMap: CodeMap
262  };
263});
264</script>
265
266