codemap.mjs 8.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308
  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. import { SplayTree } from "./splaytree.mjs";
  28. /**
  29. * The number of alignment bits in a page address.
  30. */
  31. const kPageAlignment = 12;
  32. /**
  33. * Page size in bytes.
  34. */
  35. const kPageSize = 1 << kPageAlignment;
  36. /**
  37. * Constructs a mapper that maps addresses into code entries.
  38. *
  39. * @constructor
  40. */
  41. export class CodeMap {
  42. /**
  43. * Dynamic code entries. Used for JIT compiled code.
  44. */
  45. dynamics_ = new SplayTree();
  46. /**
  47. * Name generator for entries having duplicate names.
  48. */
  49. dynamicsNameGen_ = new NameGenerator();
  50. /**
  51. * Static code entries. Used for statically compiled code.
  52. */
  53. statics_ = new SplayTree();
  54. /**
  55. * Libraries entries. Used for the whole static code libraries.
  56. */
  57. libraries_ = new SplayTree();
  58. /**
  59. * Map of memory pages occupied with static code.
  60. */
  61. pages_ = new Set();
  62. /**
  63. * Adds a dynamic (i.e. moveable and discardable) code entry.
  64. *
  65. * @param {number} start The starting address.
  66. * @param {CodeMap.CodeEntry} codeEntry Code entry object.
  67. */
  68. addCode(start, codeEntry) {
  69. this.deleteAllCoveredNodes_(this.dynamics_, start, start + codeEntry.size);
  70. this.dynamics_.insert(start, codeEntry);
  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. moveCode(from, to) {
  80. const removedNode = this.dynamics_.remove(from);
  81. this.deleteAllCoveredNodes_(this.dynamics_, to, to + removedNode.value.size);
  82. this.dynamics_.insert(to, removedNode.value);
  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. deleteCode(start) {
  91. const removedNode = this.dynamics_.remove(start);
  92. }
  93. /**
  94. * Adds a library entry.
  95. *
  96. * @param {number} start The starting address.
  97. * @param {CodeMap.CodeEntry} codeEntry Code entry object.
  98. */
  99. addLibrary(start, codeEntry) {
  100. this.markPages_(start, start + codeEntry.size);
  101. this.libraries_.insert(start, codeEntry);
  102. }
  103. /**
  104. * Adds a static code entry.
  105. *
  106. * @param {number} start The starting address.
  107. * @param {CodeMap.CodeEntry} codeEntry Code entry object.
  108. */
  109. addStaticCode(start, codeEntry) {
  110. this.statics_.insert(start, codeEntry);
  111. }
  112. /**
  113. * @private
  114. */
  115. markPages_(start, end) {
  116. for (let addr = start; addr <= end; addr += kPageSize) {
  117. this.pages_.add((addr / kPageSize) | 0);
  118. }
  119. }
  120. /**
  121. * @private
  122. */
  123. deleteAllCoveredNodes_(tree, start, end) {
  124. const to_delete = [];
  125. let addr = end - 1;
  126. while (addr >= start) {
  127. const node = tree.findGreatestLessThan(addr);
  128. if (node === null) break;
  129. const start2 = node.key, end2 = start2 + node.value.size;
  130. if (start2 < end && start < end2) to_delete.push(start2);
  131. addr = start2 - 1;
  132. }
  133. for (let i = 0, l = to_delete.length; i < l; ++i) tree.remove(to_delete[i]);
  134. }
  135. /**
  136. * @private
  137. */
  138. isAddressBelongsTo_(addr, node) {
  139. return addr >= node.key && addr < (node.key + node.value.size);
  140. }
  141. /**
  142. * @private
  143. */
  144. findInTree_(tree, addr) {
  145. const node = tree.findGreatestLessThan(addr);
  146. return node !== null && this.isAddressBelongsTo_(addr, node) ? node : null;
  147. }
  148. /**
  149. * Finds a code entry that contains the specified address. Both static and
  150. * dynamic code entries are considered. Returns the code entry and the offset
  151. * within the entry.
  152. *
  153. * @param {number} addr Address.
  154. */
  155. findAddress(addr) {
  156. const pageAddr = (addr / kPageSize) | 0;
  157. if (this.pages_.has(pageAddr)) {
  158. // Static code entries can contain "holes" of unnamed code.
  159. // In this case, the whole library is assigned to this address.
  160. let result = this.findInTree_(this.statics_, addr);
  161. if (result === null) {
  162. result = this.findInTree_(this.libraries_, addr);
  163. if (result === null) return null;
  164. }
  165. return {entry: result.value, offset: addr - result.key};
  166. }
  167. const max = this.dynamics_.findMax();
  168. if (max === null) return null;
  169. const min = this.dynamics_.findMin();
  170. if (addr >= min.key && addr < (max.key + max.value.size)) {
  171. const dynaEntry = this.findInTree_(this.dynamics_, addr);
  172. if (dynaEntry === null) return null;
  173. // Dedupe entry name.
  174. const entry = dynaEntry.value;
  175. if (!entry.nameUpdated_) {
  176. entry.name = this.dynamicsNameGen_.getName(entry.name);
  177. entry.nameUpdated_ = true;
  178. }
  179. return {entry, offset: addr - dynaEntry.key};
  180. }
  181. return null;
  182. }
  183. /**
  184. * Finds a code entry that contains the specified address. Both static and
  185. * dynamic code entries are considered.
  186. *
  187. * @param {number} addr Address.
  188. */
  189. findEntry(addr) {
  190. const result = this.findAddress(addr);
  191. return result !== null ? result.entry : null;
  192. }
  193. /**
  194. * Returns a dynamic code entry using its starting address.
  195. *
  196. * @param {number} addr Address.
  197. */
  198. findDynamicEntryByStartAddress(addr) {
  199. const node = this.dynamics_.find(addr);
  200. return node !== null ? node.value : null;
  201. }
  202. /**
  203. * Returns an array of all dynamic code entries.
  204. */
  205. getAllDynamicEntries() {
  206. return this.dynamics_.exportValues();
  207. }
  208. /**
  209. * Returns an array of pairs of all dynamic code entries and their addresses.
  210. */
  211. getAllDynamicEntriesWithAddresses() {
  212. return this.dynamics_.exportKeysAndValues();
  213. }
  214. /**
  215. * Returns an array of all static code entries.
  216. */
  217. getAllStaticEntries() {
  218. return this.statics_.exportValues();
  219. }
  220. /**
  221. * Returns an array of pairs of all static code entries and their addresses.
  222. */
  223. getAllStaticEntriesWithAddresses() {
  224. return this.statics_.exportKeysAndValues();
  225. }
  226. /**
  227. * Returns an array of all library entries.
  228. */
  229. getAllLibraryEntries() {
  230. return this.libraries_.exportValues();
  231. }
  232. /**
  233. * Returns an array of pairs of all library entries and their addresses.
  234. */
  235. getAllLibraryEntriesWithAddresses() {
  236. return this.libraries_.exportKeysAndValues();
  237. }
  238. }
  239. /**
  240. * Creates a code entry object.
  241. *
  242. * @param {number} size Code entry size in bytes.
  243. * @param {string} opt_name Code entry name.
  244. * @param {string} opt_type Code entry type, e.g. SHARED_LIB, CPP.
  245. * @param {object} source Optional source position information
  246. * @constructor
  247. */
  248. export class CodeEntry {
  249. constructor(size, opt_name, opt_type) {
  250. this.size = size;
  251. this.name = opt_name || '';
  252. this.type = opt_type || '';
  253. this.nameUpdated_ = false;
  254. this.source = undefined;
  255. }
  256. getName() {
  257. return this.name;
  258. }
  259. toString() {
  260. return this.name + ': ' + this.size.toString(16);
  261. }
  262. getSourceCode() {
  263. return '';
  264. }
  265. }
  266. class NameGenerator {
  267. knownNames_ = { __proto__:null }
  268. getName(name) {
  269. if (!(name in this.knownNames_)) {
  270. this.knownNames_[name] = 0;
  271. return name;
  272. }
  273. const count = ++this.knownNames_[name];
  274. return name + ' {' + count + '}';
  275. };
  276. }