symbol.js

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;
}