Skip to content

Instantly share code, notes, and snippets.

@shuhei
Created September 4, 2018 21:23
Show Gist options
  • Save shuhei/1b0ca2735298ae331ec6b402d3bb7e70 to your computer and use it in GitHub Desktop.
Save shuhei/1b0ca2735298ae331ec6b402d3bb7e70 to your computer and use it in GitHub Desktop.
symbol.js
const fs = require('fs');
const path = require('path');
class Node {
constructor(start, end, depth) {
this.start = start;
this.end = end;
this.middle = Math.floor((start + end) / 2);
this.items = [];
this.left = null;
this.right = null;
if (depth > 0) {
this.left = new Node(start, this.middle, depth - 1);
this.right = new Node(this.middle, end, depth - 1);
}
}
insert(entry) {
// Remove colliding ones on the way.
// TODO: Do it in more low-cost way.
this.items = this.items.filter(item => !intersect(item, entry));
const { start, size } = entry;
if (start + size <= this.middle) {
if (this.left) {
this.left.insert(entry);
} else {
this.items.push(entry);
}
} else if (start <= this.middle) {
this.items.push(entry);
} else {
if (this.right) {
this.right.insert(entry);
} else {
this.items.push(entry);
}
}
}
find(address) {
if (this.start <= address && address < this.end) {
const own = this.items.find(entry => inRange(address, entry));
if (own) {
return own;
}
if (address < this.middle) {
return this.left && this.left.find(address);
} else {
return this.right && this.right.find(address);
}
}
return null;
}
size() {
const left = this.left ? this.left.size() : 0;
const right = this.right ? this.right.size() : 0;
return this.items.length + left + right;
}
}
const availableCommands = [
'tidy',
'find',
'update',
];
const command = process.argv[2];
if (!availableCommands.includes(command)) {
console.error(`Available commands: ${availableCommands.join(', ')}`);
process.exit(1);
}
const filename = process.argv[3];
if (!filename) {
console.error('Symbol file name should be given');
process.exit(1);
}
// Get entries
const content = fs.readFileSync(filename, { encoding: 'utf8' });
const entries = content.split(/\r?\n/).filter(Boolean).map(line => {
const components = line.split(' ');
return {
start: parseInt(components[0], 16),
size: parseInt(components[1], 16),
name: components.slice(2).join(' '),
};
});
console.log(`Total: ${entries.length} entries`);
const tree = buildTree(entries);
console.log(`Fresh: ${tree.size()} entries`);
switch (command) {
case 'find': {
const address = parseInt(process.argv[4], 16);
if (Number.isNaN(address)) {
console.error('Address should be a hex number');
process.exit(1);
}
const matches = entries.filter(entry => inRange(address, entry));
printEntries('All Matches', matches);
const freshMatches = freshEntries.filter(entry => inRange(address, entry));
printEntries('Fresh Matches', freshMatches);
}
case 'tidy': {
const outFilename = process.argv[4];
if (!outFilename) {
console.error('Output filename should be given');
process.exit(1);
}
const output = freshEntries.map(stringifyEntry).join('\n');
fs.writeFileSync(path.resolve(outFilename), output);
}
case 'update': {
const stackFilename = process.argv[4];
const outFilename = process.argv[5];
if (!stackFilename) {
console.error('Stack trace filename should be given');
process.exit(1);
}
if (!outFilename) {
console.error('Output filename should be given');
process.exit(1);
}
const stacks = fs.readFileSync(stackFilename, { encoding: 'utf8' });
const output = stacks.split(/\r?\n/).map((line) => {
const pattern = /^(\s+)([0-9a-f]+) (.+) (\(\/tmp\/perf-[0-9]+\.map\))$/;
const match = pattern.exec(line);
if (!match) {
return line;
}
const [_, space, addressStr, symbol, filename] = match;
const address = parseInt(addressStr, 16);
const newSymbol = findSymbol(tree, address) || symbol;
return `${space}${addressStr} ${newSymbol} ${filename}`;
}).join('\n');
fs.writeFileSync(path.resolve(outFilename), output);
}
}
function inRange(address, { start, size }) {
return start <= address && address < start + size;
}
function intersect(a, b) {
// Make sure that `a` is earlier than `b`.
if (a.start > b.start) {
return intersect(b, a);
}
return a.start + a.size > b.start;
}
function printEntries(label, entries) {
console.log(`${label}: ${entries.length} entries`);
entries.forEach(entry => {
console.log(` ${stringifyEntry(entry)}`);
});
}
function stringifyEntry(entry) {
return `${entry.start.toString(16)} ${entry.size.toString(16)} ${entry.name}`;
}
function findSymbol(tree, address) {
const found = tree.find(address);
return found && found.name;
}
function buildTree(entries) {
let min = Infinity;
let max = -Infinity;
entries.forEach(({ start, size }) => {
if (start < min) {
min = start;
}
if (max < start + size) {
max = start + size;
}
});
console.log({ min, max });
const root = new Node(min, max, 20);
entries.forEach((entry) => {
root.insert(entry);
});
return root;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment