codemap.mjs 8.57 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
// Copyright 2009 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

import { SplayTree } from "./splaytree.mjs";

/**
 * Constructs a mapper that maps addresses into code entries.
 *
 * @constructor
 */
35
export class CodeMap {
36 37 38
  /**
   * Dynamic code entries. Used for JIT compiled code.
   */
39
  dynamics_ = new SplayTree();
40 41 42 43

  /**
   * Name generator for entries having duplicate names.
   */
44
  dynamicsNameGen_ = new NameGenerator();
45 46 47 48

  /**
   * Static code entries. Used for statically compiled code.
   */
49
  statics_ = new SplayTree();
50 51 52 53

  /**
   * Libraries entries. Used for the whole static code libraries.
   */
54
  libraries_ = new SplayTree();
55 56 57 58

  /**
   * Map of memory pages occupied with static code.
   */
59
  pages_ = [];
60 61


62 63 64 65
  /**
   * The number of alignment bits in a page address.
   */
  static PAGE_ALIGNMENT = 12;
66 67


68 69 70 71
  /**
   * Page size in bytes.
   */
  static PAGE_SIZE =  1 << CodeMap.PAGE_ALIGNMENT;
72 73


74 75 76 77 78 79 80 81 82 83
  /**
   * Adds a dynamic (i.e. moveable and discardable) code entry.
   *
   * @param {number} start The starting address.
   * @param {CodeMap.CodeEntry} codeEntry Code entry object.
   */
  addCode(start, codeEntry) {
    this.deleteAllCoveredNodes_(this.dynamics_, start, start + codeEntry.size);
    this.dynamics_.insert(start, codeEntry);
  }
84

85 86 87 88 89 90 91 92
  /**
   * Moves a dynamic code entry. Throws an exception if there is no dynamic
   * code entry with the specified starting address.
   *
   * @param {number} from The starting address of the entry being moved.
   * @param {number} to The destination address.
   */
  moveCode(from, to) {
93
    const removedNode = this.dynamics_.remove(from);
94 95 96
    this.deleteAllCoveredNodes_(this.dynamics_, to, to + removedNode.value.size);
    this.dynamics_.insert(to, removedNode.value);
  }
97

98 99 100 101 102 103 104
  /**
   * Discards a dynamic code entry. Throws an exception if there is no dynamic
   * code entry with the specified starting address.
   *
   * @param {number} start The starting address of the entry being deleted.
   */
  deleteCode(start) {
105
    const removedNode = this.dynamics_.remove(start);
106
  }
107

108 109 110 111 112 113 114 115 116 117
  /**
   * Adds a library entry.
   *
   * @param {number} start The starting address.
   * @param {CodeMap.CodeEntry} codeEntry Code entry object.
   */
  addLibrary(start, codeEntry) {
    this.markPages_(start, start + codeEntry.size);
    this.libraries_.insert(start, codeEntry);
  }
118

119 120 121 122 123 124 125 126 127
  /**
   * Adds a static code entry.
   *
   * @param {number} start The starting address.
   * @param {CodeMap.CodeEntry} codeEntry Code entry object.
   */
  addStaticCode(start, codeEntry) {
    this.statics_.insert(start, codeEntry);
  }
128

129 130 131 132
  /**
   * @private
   */
  markPages_(start, end) {
133
    for (let addr = start; addr <= end;
134 135 136 137
        addr += CodeMap.PAGE_SIZE) {
      this.pages_[(addr / CodeMap.PAGE_SIZE)|0] = 1;
    }
  }
138

139 140 141 142
  /**
   * @private
   */
  deleteAllCoveredNodes_(tree, start, end) {
143 144
    const to_delete = [];
    let addr = end - 1;
145
    while (addr >= start) {
146
      const node = tree.findGreatestLessThan(addr);
147
      if (!node) break;
148
      const start2 = node.key, end2 = start2 + node.value.size;
149 150 151
      if (start2 < end && start < end2) to_delete.push(start2);
      addr = start2 - 1;
    }
152
    for (let i = 0, l = to_delete.length; i < l; ++i) tree.remove(to_delete[i]);
153 154
  }

155 156 157 158 159 160
  /**
   * @private
   */
  isAddressBelongsTo_(addr, node) {
    return addr >= node.key && addr < (node.key + node.value.size);
  }
161

162 163 164 165
  /**
   * @private
   */
  findInTree_(tree, addr) {
166
    const node = tree.findGreatestLessThan(addr);
167
    return node && this.isAddressBelongsTo_(addr, node) ? node : null;
168 169
  }

170 171 172 173 174 175 176 177
  /**
   * Finds a code entry that contains the specified address. Both static and
   * dynamic code entries are considered. Returns the code entry and the offset
   * within the entry.
   *
   * @param {number} addr Address.
   */
  findAddress(addr) {
178
    const pageAddr = (addr / CodeMap.PAGE_SIZE)|0;
179 180 181
    if (pageAddr in this.pages_) {
      // Static code entries can contain "holes" of unnamed code.
      // In this case, the whole library is assigned to this address.
182
      let result = this.findInTree_(this.statics_, addr);
183 184 185 186
      if (!result) {
        result = this.findInTree_(this.libraries_, addr);
        if (!result) return null;
      }
187
      return {entry: result.value, offset: addr - result.key};
188
    }
189 190
    const min = this.dynamics_.findMin();
    const max = this.dynamics_.findMax();
191
    if (max != null && addr < (max.key + max.value.size) && addr >= min.key) {
192
      const dynaEntry = this.findInTree_(this.dynamics_, addr);
193 194
      if (dynaEntry == null) return null;
      // Dedupe entry name.
195
      const entry = dynaEntry.value;
196 197 198 199
      if (!entry.nameUpdated_) {
        entry.name = this.dynamicsNameGen_.getName(entry.name);
        entry.nameUpdated_ = true;
      }
200
      return {entry, offset: addr - dynaEntry.key};
201
    }
202
    return null;
203 204
  }

205 206 207 208 209 210 211
  /**
   * Finds a code entry that contains the specified address. Both static and
   * dynamic code entries are considered.
   *
   * @param {number} addr Address.
   */
  findEntry(addr) {
212
    const result = this.findAddress(addr);
213 214
    return result ? result.entry : null;
  }
215

216 217 218 219 220 221
  /**
   * Returns a dynamic code entry using its starting address.
   *
   * @param {number} addr Address.
   */
  findDynamicEntryByStartAddress(addr) {
222
    const node = this.dynamics_.find(addr);
223 224
    return node ? node.value : null;
  }
225

226 227 228 229 230 231
  /**
   * Returns an array of all dynamic code entries.
   */
  getAllDynamicEntries() {
    return this.dynamics_.exportValues();
  }
232

233 234 235 236 237 238
  /**
   * Returns an array of pairs of all dynamic code entries and their addresses.
   */
  getAllDynamicEntriesWithAddresses() {
    return this.dynamics_.exportKeysAndValues();
  }
239

240 241 242 243 244 245
  /**
   * Returns an array of all static code entries.
   */
  getAllStaticEntries() {
    return this.statics_.exportValues();
  }
246

247 248 249 250 251 252
  /**
   * Returns an array of pairs of all static code entries and their addresses.
   */
  getAllStaticEntriesWithAddresses() {
    return this.statics_.exportKeysAndValues();
  }
253

254
  /**
255
   * Returns an array of all library entries.
256
   */
257
  getAllLibraryEntries() {
258 259
    return this.libraries_.exportValues();
  }
260 261 262 263 264 265 266

  /**
   * Returns an array of pairs of all library entries and their addresses.
   */
  getAllLibraryEntriesWithAddresses() {
    return this.libraries_.exportKeysAndValues();
  }
267
}
268 269 270 271 272 273 274 275


/**
 * Creates a code entry object.
 *
 * @param {number} size Code entry size in bytes.
 * @param {string} opt_name Code entry name.
 * @param {string} opt_type Code entry type, e.g. SHARED_LIB, CPP.
276
 * @param {object} source Optional source position information
277 278
 * @constructor
 */
279 280 281 282 283 284
export class CodeEntry {
  constructor(size, opt_name, opt_type) {
    this.size = size;
    this.name = opt_name || '';
    this.type = opt_type || '';
    this.nameUpdated_ = false;
285
    this.source = undefined;
286
  }
287

288 289 290
  getName() {
    return this.name;
  }
291

292 293
  toString() {
    return this.name + ': ' + this.size.toString(16);
294
  }
295 296 297 298

  getSourceCode() {
    return '';
  }
299 300 301 302 303 304 305 306 307
}

class NameGenerator {
  knownNames_ = { __proto__:null }
  getName(name) {
    if (!(name in this.knownNames_)) {
      this.knownNames_[name] = 0;
      return name;
    }
308
    const count = ++this.knownNames_[name];
309 310 311
    return name + ' {' + count + '}';
  };
}