text: /* This Source Code Form is subject to the terms of the Mozilla Public
   * License, v. 2.0. If a copy of the MPL was not distributed with this
   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
  
  /*
  
    A program that attempts to find an optimal function ordering for an
    executable using a genetic algorithm whose fitness function is
    computed using runtime profile information.
  
    The fitness function was inspired by Nat Friedman's <nat@nat.org>
    work on `grope':
  
      _GNU Rope - A Subroutine Position Optimizer_
      <http://www.hungry.com/~shaver/grope/grope.ps>
  
    Brendan Eich <brendan@mozilla.org> told me tales about Scott Furman
    doing something like this, which sort of made me want to try it.
  
    As far as I can tell, it would take a lot of computers a lot of time
    to actually find something useful on a non-trivial program using
    this.
  
   */
  
  #include <assert.h>
  #include <fstream>
  #include <hash_map>
  #include <vector>
  #include <limits.h>
  #include <unistd.h>
  #include <stdio.h>
  #include <fcntl.h>
  
  #include "elf_symbol_table.h"
  
  #define _GNU_SOURCE
  #include <getopt.h>
  
  #define PAGE_SIZE 4096
  #define SYMBOL_ALIGN 4
  
  //----------------------------------------------------------------------
  
  class call_pair
  {
  public:
      const Elf32_Sym *m_lo;
      const Elf32_Sym *m_hi;
  
      call_pair(const Elf32_Sym *site1, const Elf32_Sym *site2)
      {
          if (site1 < site2) {
              m_lo = site1;
              m_hi = site2;
          }
          else {
              m_hi = site1;
              m_lo = site2;
          }
      }
  
      friend bool
      operator==(const call_pair &lhs, const call_pair &rhs)
      {
          return (lhs.m_lo == rhs.m_lo) && (lhs.m_hi == rhs.m_hi);
      }
  };
  
  // Straight outta plhash.c!
  #define GOLDEN_RATIO 0x9E3779B9U
  
  template<>
  struct hash<call_pair>
  {
      size_t operator()(const call_pair &pair) const
      {
          size_t h = (reinterpret_cast<size_t>(pair.m_hi) >> 4);
          h += (reinterpret_cast<size_t>(pair.m_lo) >> 4);
          h *= GOLDEN_RATIO;
          return h;
      }
  };
  
  //----------------------------------------------------------------------
  
  struct hash<const Elf32_Sym *>
  {
      size_t operator()(const Elf32_Sym *sym) const
      {
          return (reinterpret_cast<size_t>(sym) >> 4) * GOLDEN_RATIO;
      }
  };
  
  //----------------------------------------------------------------------
  
  typedef hash_map<call_pair, unsigned int> call_graph_t;
  call_graph_t call_graph;
  
  typedef hash_map<const Elf32_Sym *, unsigned int> histogram_t;
  histogram_t histogram;
  long long total_calls = 0;
  
  elf_symbol_table symtab;
  
  bool opt_debug = false;
  int opt_generations = 10;
  int opt_mutate = 0;
  const char *opt_out = "order.out";
  int opt_population_size = 100;
  int opt_tick = 0;
  bool opt_verbose = false;
  int opt_window = 0;
  
  static struct option long_options[] = {
      { "debug",       no_argument,       0, 'd' },
      { "exe",         required_argument, 0, 'e' },
      { "generations", required_argument, 0, 'g' },
      { "help",        no_argument,       0, '?' },
      { "mutate",      required_argument, 0, 'm' },
      { "out",         required_argument, 0, 'o' },
      { "population",  required_argument, 0, 'p' },
      { "seed",        required_argument, 0, 's' },
      { "tick",        optional_argument, 0, 't' },
      { "verbose",     no_argument,       0, 'v' },
      { "window",      required_argument, 0, 'w' },
      { 0,             0,                 0, 0   }
  };
  
  //----------------------------------------------------------------------
  
  static long long
  llrand()
  {
      long long result;
      result = (long long) rand();
      result *= (long long) (unsigned int) (RAND_MAX + 1);
      result += (long long) rand();
      return result;
  }
  
  //----------------------------------------------------------------------
  
  class symbol_order {
  public:
      typedef vector<const Elf32_Sym *> vector_t;
      typedef long long score_t;
  
      static const score_t max_score;
  
      /**
       * A vector of symbols that is this ordering.
       */
      vector_t m_ordering;
  
      /**
       * The symbol ordering's score.
       */
      score_t  m_score;
  
      symbol_order() : m_score(0) {}
  
      /**
       * ``Shuffle'' a symbol ordering, randomizing it.
       */
      void shuffle();
  
      /**
       * Initialize this symbol ordering by performing a crossover from
       * two ``parent'' symbol orderings.
       */
      void crossover_from(const symbol_order *father, const symbol_order *mother);
  
      /**
       * Randomly mutate this symbol ordering.
       */
      void mutate();
  
      /**
       * Score a symbol ordering based on paginated locality.
       */
      score_t compute_score_page();
  
      /**
       * Score a symbol ordering based on a sliding window.
       */
      score_t compute_score_window(int window_size);
  
      static score_t compute_score(symbol_order &order);
  
      /**
       * Use the symbol table to dump the ordered symbolic constants.
       */
      void dump_symbols() const;
  
      friend ostream &
      operator<<(ostream &out, const symbol_order &order);
  };
  
  const symbol_order::score_t
  symbol_order::max_score = ~((symbol_order::score_t)1 << ((sizeof(symbol_order::score_t) * 8) - 1));
  
  symbol_order::score_t
  symbol_order::compute_score_page()
  {
      m_score = 0;
  
      unsigned int off = 0; // XXX in reality, probably not page-aligned to start
  
      vector_t::const_iterator end = m_ordering.end(),
          last = end,
          sym = m_ordering.begin();
  
      while (sym != end) {
          vector_t page;
  
          // If we had a symbol that spilled over from the last page,
          // then include it here.
          if (last != end)
              page.push_back(*last);
  
          // Pack symbols into the page
          do {
              page.push_back(*sym);
  
              int size = (*sym)->st_size;
              size += SYMBOL_ALIGN - 1;
              size &= ~(SYMBOL_ALIGN - 1);
  
              off += size;
          } while (++sym != end && off < PAGE_SIZE);
  
          // Remember if there was spill-over.
          off %= PAGE_SIZE;
          last = (off != 0) ? sym : end;
  
          // Now score the page as the count of all calls to symbols on
          // the page, less calls between the symbols on the page.
          vector_t::const_iterator page_end = page.end();
          for (vector_t::const_iterator i = page.begin(); i != page_end; ++i) {
              histogram_t::const_iterator func = histogram.find(*i);
              if (func == histogram.end())
                  continue;
  
              m_score += func->second;
  
              vector_t::const_iterator j = i;
              for (++j; j != page_end; ++j) {
                  call_graph_t::const_iterator call =
                      call_graph.find(call_pair(*i, *j));
  
                  if (call != call_graph.end())
                      m_score -= call->second;
              }
          }
      }
  
      assert(m_score >= 0);
  
      // Integer reciprocal so we minimize instead of maximize.
      if (m_score == 0)
          m_score = 1;
  
      m_score = (total_calls / m_score) + 1;
  
      return m_score;
  }
  
  symbol_order::score_t
  symbol_order::compute_score_window(int window_size)
  {
      m_score = 0;
  
      vector_t::const_iterator *window = new vector_t::const_iterator[window_size];
      int window_fill = 0;
  
      vector_t::const_iterator end = m_ordering.end(),
          sym = m_ordering.begin();
  
      for (; sym != end; ++sym) {
          histogram_t::const_iterator func = histogram.find(*sym);
          if (func != histogram.end()) {
              long long scale = ((long long) 1) << window_size;
  
              m_score += func->second * scale * 2;
  
              vector_t::const_iterator *limit = window + window_fill;
              vector_t::const_iterator *iter;
              for (iter = window ; iter < limit; ++iter) {
                  call_graph_t::const_iterator call =
                      call_graph.find(call_pair(*sym, **iter));
  
                  if (call != call_graph.end())
                      m_score -= (call->second * scale);
              
                  scale >>= 1;
              }
          }
  
          // Slide the window.
          vector_t::const_iterator *begin = window;
          vector_t::const_iterator *iter;
          for (iter = window + (window_size - 1); iter > begin; --iter)
              *iter = *(iter - 1);
  
          if (window_fill < window_size)
              ++window_fill;
  
          *window = sym;
      }
  
      delete[] window;
  
      assert(m_score >= 0);
  
      // Integer reciprocal so we minimize instead of maximize.
      if (m_score == 0)
          m_score = 1;
  
      m_score = (total_calls / m_score) + 1;
  
      return m_score;
  }
  
  symbol_order::score_t
  symbol_order::compute_score(symbol_order &order)
  {
      if (opt_window)
          return order.compute_score_window(opt_window);
  
      return order.compute_score_page();
  }
  
  void
  symbol_order::shuffle()
  {
      vector_t::iterator sym = m_ordering.begin();
      vector_t::iterator end = m_ordering.end();
      for (; sym != end; ++sym) {
          int i = rand() % m_ordering.size();
          const Elf32_Sym *temp = *sym;
          *sym = m_ordering[i];
          m_ordering[i] = temp;
      }
  }
  
  void
  symbol_order::crossover_from(const symbol_order *father, const symbol_order *mother)
  {
      histogram_t used;
  
      m_ordering = vector_t(father->m_ordering.size(), 0);
  
      vector_t::const_iterator parent_sym = father->m_ordering.begin();
      vector_t::iterator sym = m_ordering.begin();
      vector_t::iterator end = m_ordering.end();
  
      for (; sym != end; ++sym, ++parent_sym) {
          if (rand() % 2) {
              *sym = *parent_sym;
              used[*parent_sym] = 1;
          }
      }
  
      parent_sym = mother->m_ordering.begin();
      sym = m_ordering.begin();
  
      for (; sym != end; ++sym) {
          if (! *sym) {
              while (used[*parent_sym])
                  ++parent_sym;
  
              *sym = *parent_sym++;
          }
      }
  }
  
  void
  symbol_order::mutate()
  {
      int i, j;
      i = rand() % m_ordering.size();
      j = rand() % m_ordering.size();
  
      const Elf32_Sym *temp = m_ordering[i];
      m_ordering[i] = m_ordering[j];
      m_ordering[j] = temp;
  }
  
  void
  symbol_order::dump_symbols() const
  {
      ofstream out(opt_out);
  
      vector_t::const_iterator sym = m_ordering.begin();
      vector_t::const_iterator end = m_ordering.end();
      for (; sym != end; ++sym)
          out << symtab.get_symbol_name(*sym) << endl;
  
      out.close();
  }
  
  ostream &
  operator<<(ostream &out, const symbol_order &order)
  {
      out << "symbol_order(" << order.m_score << ") ";
  
      symbol_order::vector_t::const_iterator sym = order.m_ordering.begin();
      symbol_order::vector_t::const_iterator end = order.m_ordering.end();
      for (; sym != end; ++sym)
          out.form("%08x ", *sym);
  
      out << endl;
  
      return out;
  }
  
  //----------------------------------------------------------------------
  
  static void
  usage(const char *name)
  {
      cerr << "usage: " << name << " [options] [<file> ...]" << endl;
      cerr << "  Options:" << endl;
      cerr << "  --debug, -d" << endl;
      cerr << "      Print lots of verbose debugging cruft." << endl;
      cerr << "  --exe=<image>, -e <image> (required)" << endl;
      cerr << "      Specify the executable image from which to read symbol information." << endl;
      cerr << "  --generations=<num>, -g <num>" << endl;
      cerr << "      Specify the number of generations to run the GA (default is 10)." << endl;
      cerr << "  --help, -?" << endl;
      cerr << "      Print this message and exit." << endl;
      cerr << "  --mutate=<num>, -m <num>" << endl;
      cerr << "      Mutate every <num>th individual, or zero for no mutation (default)." << endl;
      cerr << "  --out=<file>, -o <file>" << endl;
      cerr << "      Specify the output file to which to dump the symbol ordering of the" << endl;
      cerr << "      best individual (default is `order.out')." << endl;
      cerr << "  --population=<num>, -p <num>" << endl;
      cerr << "      Set the population size to <num> individuals (default is 100)." << endl;
      cerr << "  --seed=<num>, -s <num>" << endl;
      cerr << "      Specify a seed to srand()." << endl;
      cerr << "  --tick[=<num>], -t [<num>]" << endl;
      cerr << "      When reading address data, print a dot to stderr every <num>th" << endl;
      cerr << "      address processed from the call trace. If specified with no argument," << endl;
      cerr << "      a dot will be printed for every million addresses processed." << endl;
      cerr << "  --verbose, -v" << endl;
      cerr << "      Issue progress messages to stderr." << endl;
      cerr << "  --window=<num>, -w <num>" << endl;
      cerr << "      Use a sliding window instead of pagination to score orderings." << endl;
      cerr << endl;
      cerr << "This program uses a genetic algorithm to produce an `optimal' ordering for" << endl;
      cerr << "an executable based on call patterns." << endl;
      cerr << endl;
      cerr << "Addresses from a call trace are read as binary data from the files" << endl;
      cerr << "specified, or from stdin if no files are specified. These addresses" << endl;
      cerr << "are used with the symbolic information from the executable to create" << endl;
      cerr << "a call graph. This call graph is used to `score' arbitrary symbol" << endl;
      cerr << "orderings, and provides the fitness function for the GA." << endl;
      cerr << endl;
  }
  
  /**
   * Using the symbol table, map a stream of address references into a
   * callgraph and a histogram.
   */
  static void
  map_addrs(int fd)
  {
      const Elf32_Sym *last = 0;
      unsigned int buf[128];
      ssize_t cb;
  
      unsigned int count = 0;
      while ((cb = read(fd, buf, sizeof buf)) > 0) {
          if (cb % sizeof buf[0])
              fprintf(stderr, "unaligned read\n");
  
          unsigned int *addr = buf;
          unsigned int *limit = buf + (cb / 4);
  
          for (; addr < limit; ++addr) {
              const Elf32_Sym *sym = symtab.lookup(*addr);
  
              if (last && sym && last != sym) {
                  ++total_calls;
                  ++histogram[sym];
                  ++call_graph[call_pair(last, sym)];
  
                  if (opt_tick && (++count % opt_tick == 0)) {
                      cerr << ".";
                      flush(cerr);
                  }
              }
  
              last = sym;
          }
      }
  
      if (opt_tick)
          cerr << endl;
  
      cerr << "Total calls: " << total_calls << endl;
      total_calls *= 1024;
  
      if (opt_window)
          total_calls <<= (opt_window + 1);
  }
  
  static symbol_order *
  pick_parent(symbol_order *ordering, int max, int index)
  {
      while (1) {
          index -= ordering->m_score;
          if (index < 0)
              break;
  
          ++ordering;
      }
  
      return ordering;
  }
  
  /**
   * The main program
   */
  int
  main(int argc, char *argv[])
  {
      const char *opt_exe = 0;
  
      int c;
      while (1) {
          int option_index = 0;
          c = getopt_long(argc, argv, "?de:g:m:o:p:s:t:vw:", long_options, &option_index);
  
          if (c < 0)
              break;
  
          switch (c) {
          case '?':
              usage(argv[0]);
              return 0;
  
          case 'd':
              opt_debug = true;
              break;
  
          case 'e':
              opt_exe = optarg;
              break;
  
          case 'g':
              opt_generations = atoi(optarg);
              break;
  
          case 'm':
              opt_mutate = atoi(optarg);
              break;
  
          case 'o':
              opt_out = optarg;
              break;
  
          case 'p':
              opt_population_size = atoi(optarg);
              break;
  
          case 's':
              srand(atoi(optarg));
              break;
  
          case 't':
              opt_tick = optarg ? atoi(optarg) : 1000000;
              break;
  
          case 'v':
              opt_verbose = true;
              break;
  
          case 'w':
              opt_window = atoi(optarg);
              if (opt_window < 0 || opt_window > 8) {
                  cerr << "invalid window size: " << opt_window << endl;
                  return 1;
              }
  
              break;
  
          default:
              usage(argv[0]);
              return 1;
          }
      }
  
      // Make sure an image was specified
      if (! opt_exe) {
          usage(argv[0]);
          return 1;
      }
  
      // Read the sym table.
      symtab.init(opt_exe);
  
      // Process addresses to construct the call graph.
      if (optind >= argc) {
          map_addrs(STDIN_FILENO);
      }
      else {
          do {
              int fd = open(argv[optind], O_RDONLY);
              if (fd < 0) {
                  perror(argv[optind]);
                  return 1;
              }
  
              map_addrs(fd);
              close(fd);
          } while (++optind < argc);
      }
  
      if (opt_debug) {
          cerr << "Call graph:" << endl;
  
          call_graph_t::const_iterator limit = call_graph.end();
          call_graph_t::const_iterator i;
          for (i = call_graph.begin(); i != limit; ++i) {
              const call_pair& pair = i->first;
              cerr.form("%08x %08x %10d\n",
                        pair.m_lo->st_value,
                        pair.m_hi->st_value,
                        i->second);
          }
      }
  
      // Collect the symbols into a vector
      symbol_order::vector_t ordering;
      elf_symbol_table::const_iterator end = symtab.end();
      for (elf_symbol_table::const_iterator sym = symtab.begin(); sym != end; ++sym) {
          if (symtab.is_function(sym))
              ordering.push_back(sym);
      }
  
      if (opt_verbose) {
          symbol_order initial;
          initial.m_ordering = ordering;
          cerr << "created initial ordering, score=" << symbol_order::compute_score(initial) << endl;
  
          if (opt_debug)
              cerr << initial;
      }
  
      // Create a population.
      if (opt_verbose)
          cerr << "creating population" << endl;
  
      symbol_order *population = new symbol_order[opt_population_size];
  
      symbol_order::score_t total = 0, min = symbol_order::max_score, max = 0;
  
      // Score it.
      symbol_order *order = population;
      symbol_order *limit = population + opt_population_size;
      for (; order < limit; ++order) {
          order->m_ordering = ordering;
          order->shuffle();
  
          symbol_order::score_t score = symbol_order::compute_score(*order);
  
          if (opt_debug)
              cerr << *order;
  
          if (min > score)
              min = score;
          if (max < score)
              max = score;
  
          total += score;
      }
  
      if (opt_verbose) {
          cerr << "Initial population";
          cerr << ": min=" << min;
          cerr << ", max=" << max;
          cerr << " mean=" << (total / opt_population_size);
          cerr << endl;
      }
  
  
      // Run the GA.
      if (opt_verbose)
          cerr << "begininng ga" << endl;
  
      symbol_order::score_t best = 0;
  
      for (int generation = 1; generation <= opt_generations; ++generation) {
          // Create a new population.
          symbol_order *offspring = new symbol_order[opt_population_size];
  
          symbol_order *kid = offspring;
          symbol_order *offspring_limit = offspring + opt_population_size;
          for (; kid < offspring_limit; ++kid) {
              // Pick parents.
              symbol_order *father, *mother;
              father = pick_parent(population, max, llrand() % total);
              mother = pick_parent(population, max, llrand() % total);
  
              // Create a kid.
              kid->crossover_from(father, mother);
  
              // Mutate, possibly.
              if (opt_mutate) {
                  if (rand() % opt_mutate == 0)
                      kid->mutate();
              }
          }
  
          delete[] population;
          population = offspring;
  
          // Score the new population.
          total = 0;
          min = symbol_order::max_score;
          max = 0;
  
          symbol_order *fittest = 0;
  
          limit = offspring_limit;
          for (order = population; order < limit; ++order) {
              symbol_order::score_t score = symbol_order::compute_score(*order);
  
              if (opt_debug)
                  cerr << *order;
  
              if (min > score)
                  min = score;
  
              if (max < score)
                  max = score;
  
              if (best < score) {
                  best = score;
                  fittest = order;
              }
  
              total += score;
          }
  
          if (opt_verbose) {
              cerr << "Generation " << generation;
              cerr << ": min=" << min;
              cerr << ", max=" << max;
              if (fittest)
                  cerr << "*";
              cerr << " mean=" << (total / opt_population_size);
              cerr << endl;
          }
  
          // If we've found a new ``best'' individual, dump it.
          if (fittest)
              fittest->dump_symbols();
      }
  
      delete[] population;
      return 0;
  }
  