tools/reorder/garope.cpp@97036ab72558
tools/reorder/garope.cpp
Tue, 06 Jan 2015 21:39:09 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Tue, 06 Jan 2015 21:39:09 +0100
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
- permissions
- -rw-r--r--
Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.
1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 /*
7 A program that attempts to find an optimal function ordering for an
8 executable using a genetic algorithm whose fitness function is
9 computed using runtime profile information.
11 The fitness function was inspired by Nat Friedman's <nat@nat.org>
12 work on `grope':
14 _GNU Rope - A Subroutine Position Optimizer_
15 <http://www.hungry.com/~shaver/grope/grope.ps>
17 Brendan Eich <brendan@mozilla.org> told me tales about Scott Furman
18 doing something like this, which sort of made me want to try it.
20 As far as I can tell, it would take a lot of computers a lot of time
21 to actually find something useful on a non-trivial program using
22 this.
24 */
26 #include <assert.h>
27 #include <fstream>
28 #include <hash_map>
29 #include <vector>
30 #include <limits.h>
31 #include <unistd.h>
32 #include <stdio.h>
33 #include <fcntl.h>
35 #include "elf_symbol_table.h"
37 #define _GNU_SOURCE
38 #include <getopt.h>
40 #define PAGE_SIZE 4096
41 #define SYMBOL_ALIGN 4
43 //----------------------------------------------------------------------
45 class call_pair
46 {
47 public:
48 const Elf32_Sym *m_lo;
49 const Elf32_Sym *m_hi;
51 call_pair(const Elf32_Sym *site1, const Elf32_Sym *site2)
52 {
53 if (site1 < site2) {
54 m_lo = site1;
55 m_hi = site2;
56 }
57 else {
58 m_hi = site1;
59 m_lo = site2;
60 }
61 }
63 friend bool
64 operator==(const call_pair &lhs, const call_pair &rhs)
65 {
66 return (lhs.m_lo == rhs.m_lo) && (lhs.m_hi == rhs.m_hi);
67 }
68 };
70 // Straight outta plhash.c!
71 #define GOLDEN_RATIO 0x9E3779B9U
73 template<>
74 struct hash<call_pair>
75 {
76 size_t operator()(const call_pair &pair) const
77 {
78 size_t h = (reinterpret_cast<size_t>(pair.m_hi) >> 4);
79 h += (reinterpret_cast<size_t>(pair.m_lo) >> 4);
80 h *= GOLDEN_RATIO;
81 return h;
82 }
83 };
85 //----------------------------------------------------------------------
87 struct hash<const Elf32_Sym *>
88 {
89 size_t operator()(const Elf32_Sym *sym) const
90 {
91 return (reinterpret_cast<size_t>(sym) >> 4) * GOLDEN_RATIO;
92 }
93 };
95 //----------------------------------------------------------------------
97 typedef hash_map<call_pair, unsigned int> call_graph_t;
98 call_graph_t call_graph;
100 typedef hash_map<const Elf32_Sym *, unsigned int> histogram_t;
101 histogram_t histogram;
102 long long total_calls = 0;
104 elf_symbol_table symtab;
106 bool opt_debug = false;
107 int opt_generations = 10;
108 int opt_mutate = 0;
109 const char *opt_out = "order.out";
110 int opt_population_size = 100;
111 int opt_tick = 0;
112 bool opt_verbose = false;
113 int opt_window = 0;
115 static struct option long_options[] = {
116 { "debug", no_argument, 0, 'd' },
117 { "exe", required_argument, 0, 'e' },
118 { "generations", required_argument, 0, 'g' },
119 { "help", no_argument, 0, '?' },
120 { "mutate", required_argument, 0, 'm' },
121 { "out", required_argument, 0, 'o' },
122 { "population", required_argument, 0, 'p' },
123 { "seed", required_argument, 0, 's' },
124 { "tick", optional_argument, 0, 't' },
125 { "verbose", no_argument, 0, 'v' },
126 { "window", required_argument, 0, 'w' },
127 { 0, 0, 0, 0 }
128 };
130 //----------------------------------------------------------------------
132 static long long
133 llrand()
134 {
135 long long result;
136 result = (long long) rand();
137 result *= (long long) (unsigned int) (RAND_MAX + 1);
138 result += (long long) rand();
139 return result;
140 }
142 //----------------------------------------------------------------------
144 class symbol_order {
145 public:
146 typedef vector<const Elf32_Sym *> vector_t;
147 typedef long long score_t;
149 static const score_t max_score;
151 /**
152 * A vector of symbols that is this ordering.
153 */
154 vector_t m_ordering;
156 /**
157 * The symbol ordering's score.
158 */
159 score_t m_score;
161 symbol_order() : m_score(0) {}
163 /**
164 * ``Shuffle'' a symbol ordering, randomizing it.
165 */
166 void shuffle();
168 /**
169 * Initialize this symbol ordering by performing a crossover from
170 * two ``parent'' symbol orderings.
171 */
172 void crossover_from(const symbol_order *father, const symbol_order *mother);
174 /**
175 * Randomly mutate this symbol ordering.
176 */
177 void mutate();
179 /**
180 * Score a symbol ordering based on paginated locality.
181 */
182 score_t compute_score_page();
184 /**
185 * Score a symbol ordering based on a sliding window.
186 */
187 score_t compute_score_window(int window_size);
189 static score_t compute_score(symbol_order &order);
191 /**
192 * Use the symbol table to dump the ordered symbolic constants.
193 */
194 void dump_symbols() const;
196 friend ostream &
197 operator<<(ostream &out, const symbol_order &order);
198 };
200 const symbol_order::score_t
201 symbol_order::max_score = ~((symbol_order::score_t)1 << ((sizeof(symbol_order::score_t) * 8) - 1));
203 symbol_order::score_t
204 symbol_order::compute_score_page()
205 {
206 m_score = 0;
208 unsigned int off = 0; // XXX in reality, probably not page-aligned to start
210 vector_t::const_iterator end = m_ordering.end(),
211 last = end,
212 sym = m_ordering.begin();
214 while (sym != end) {
215 vector_t page;
217 // If we had a symbol that spilled over from the last page,
218 // then include it here.
219 if (last != end)
220 page.push_back(*last);
222 // Pack symbols into the page
223 do {
224 page.push_back(*sym);
226 int size = (*sym)->st_size;
227 size += SYMBOL_ALIGN - 1;
228 size &= ~(SYMBOL_ALIGN - 1);
230 off += size;
231 } while (++sym != end && off < PAGE_SIZE);
233 // Remember if there was spill-over.
234 off %= PAGE_SIZE;
235 last = (off != 0) ? sym : end;
237 // Now score the page as the count of all calls to symbols on
238 // the page, less calls between the symbols on the page.
239 vector_t::const_iterator page_end = page.end();
240 for (vector_t::const_iterator i = page.begin(); i != page_end; ++i) {
241 histogram_t::const_iterator func = histogram.find(*i);
242 if (func == histogram.end())
243 continue;
245 m_score += func->second;
247 vector_t::const_iterator j = i;
248 for (++j; j != page_end; ++j) {
249 call_graph_t::const_iterator call =
250 call_graph.find(call_pair(*i, *j));
252 if (call != call_graph.end())
253 m_score -= call->second;
254 }
255 }
256 }
258 assert(m_score >= 0);
260 // Integer reciprocal so we minimize instead of maximize.
261 if (m_score == 0)
262 m_score = 1;
264 m_score = (total_calls / m_score) + 1;
266 return m_score;
267 }
269 symbol_order::score_t
270 symbol_order::compute_score_window(int window_size)
271 {
272 m_score = 0;
274 vector_t::const_iterator *window = new vector_t::const_iterator[window_size];
275 int window_fill = 0;
277 vector_t::const_iterator end = m_ordering.end(),
278 sym = m_ordering.begin();
280 for (; sym != end; ++sym) {
281 histogram_t::const_iterator func = histogram.find(*sym);
282 if (func != histogram.end()) {
283 long long scale = ((long long) 1) << window_size;
285 m_score += func->second * scale * 2;
287 vector_t::const_iterator *limit = window + window_fill;
288 vector_t::const_iterator *iter;
289 for (iter = window ; iter < limit; ++iter) {
290 call_graph_t::const_iterator call =
291 call_graph.find(call_pair(*sym, **iter));
293 if (call != call_graph.end())
294 m_score -= (call->second * scale);
296 scale >>= 1;
297 }
298 }
300 // Slide the window.
301 vector_t::const_iterator *begin = window;
302 vector_t::const_iterator *iter;
303 for (iter = window + (window_size - 1); iter > begin; --iter)
304 *iter = *(iter - 1);
306 if (window_fill < window_size)
307 ++window_fill;
309 *window = sym;
310 }
312 delete[] window;
314 assert(m_score >= 0);
316 // Integer reciprocal so we minimize instead of maximize.
317 if (m_score == 0)
318 m_score = 1;
320 m_score = (total_calls / m_score) + 1;
322 return m_score;
323 }
325 symbol_order::score_t
326 symbol_order::compute_score(symbol_order &order)
327 {
328 if (opt_window)
329 return order.compute_score_window(opt_window);
331 return order.compute_score_page();
332 }
334 void
335 symbol_order::shuffle()
336 {
337 vector_t::iterator sym = m_ordering.begin();
338 vector_t::iterator end = m_ordering.end();
339 for (; sym != end; ++sym) {
340 int i = rand() % m_ordering.size();
341 const Elf32_Sym *temp = *sym;
342 *sym = m_ordering[i];
343 m_ordering[i] = temp;
344 }
345 }
347 void
348 symbol_order::crossover_from(const symbol_order *father, const symbol_order *mother)
349 {
350 histogram_t used;
352 m_ordering = vector_t(father->m_ordering.size(), 0);
354 vector_t::const_iterator parent_sym = father->m_ordering.begin();
355 vector_t::iterator sym = m_ordering.begin();
356 vector_t::iterator end = m_ordering.end();
358 for (; sym != end; ++sym, ++parent_sym) {
359 if (rand() % 2) {
360 *sym = *parent_sym;
361 used[*parent_sym] = 1;
362 }
363 }
365 parent_sym = mother->m_ordering.begin();
366 sym = m_ordering.begin();
368 for (; sym != end; ++sym) {
369 if (! *sym) {
370 while (used[*parent_sym])
371 ++parent_sym;
373 *sym = *parent_sym++;
374 }
375 }
376 }
378 void
379 symbol_order::mutate()
380 {
381 int i, j;
382 i = rand() % m_ordering.size();
383 j = rand() % m_ordering.size();
385 const Elf32_Sym *temp = m_ordering[i];
386 m_ordering[i] = m_ordering[j];
387 m_ordering[j] = temp;
388 }
390 void
391 symbol_order::dump_symbols() const
392 {
393 ofstream out(opt_out);
395 vector_t::const_iterator sym = m_ordering.begin();
396 vector_t::const_iterator end = m_ordering.end();
397 for (; sym != end; ++sym)
398 out << symtab.get_symbol_name(*sym) << endl;
400 out.close();
401 }
403 ostream &
404 operator<<(ostream &out, const symbol_order &order)
405 {
406 out << "symbol_order(" << order.m_score << ") ";
408 symbol_order::vector_t::const_iterator sym = order.m_ordering.begin();
409 symbol_order::vector_t::const_iterator end = order.m_ordering.end();
410 for (; sym != end; ++sym)
411 out.form("%08x ", *sym);
413 out << endl;
415 return out;
416 }
418 //----------------------------------------------------------------------
420 static void
421 usage(const char *name)
422 {
423 cerr << "usage: " << name << " [options] [<file> ...]" << endl;
424 cerr << " Options:" << endl;
425 cerr << " --debug, -d" << endl;
426 cerr << " Print lots of verbose debugging cruft." << endl;
427 cerr << " --exe=<image>, -e <image> (required)" << endl;
428 cerr << " Specify the executable image from which to read symbol information." << endl;
429 cerr << " --generations=<num>, -g <num>" << endl;
430 cerr << " Specify the number of generations to run the GA (default is 10)." << endl;
431 cerr << " --help, -?" << endl;
432 cerr << " Print this message and exit." << endl;
433 cerr << " --mutate=<num>, -m <num>" << endl;
434 cerr << " Mutate every <num>th individual, or zero for no mutation (default)." << endl;
435 cerr << " --out=<file>, -o <file>" << endl;
436 cerr << " Specify the output file to which to dump the symbol ordering of the" << endl;
437 cerr << " best individual (default is `order.out')." << endl;
438 cerr << " --population=<num>, -p <num>" << endl;
439 cerr << " Set the population size to <num> individuals (default is 100)." << endl;
440 cerr << " --seed=<num>, -s <num>" << endl;
441 cerr << " Specify a seed to srand()." << endl;
442 cerr << " --tick[=<num>], -t [<num>]" << endl;
443 cerr << " When reading address data, print a dot to stderr every <num>th" << endl;
444 cerr << " address processed from the call trace. If specified with no argument," << endl;
445 cerr << " a dot will be printed for every million addresses processed." << endl;
446 cerr << " --verbose, -v" << endl;
447 cerr << " Issue progress messages to stderr." << endl;
448 cerr << " --window=<num>, -w <num>" << endl;
449 cerr << " Use a sliding window instead of pagination to score orderings." << endl;
450 cerr << endl;
451 cerr << "This program uses a genetic algorithm to produce an `optimal' ordering for" << endl;
452 cerr << "an executable based on call patterns." << endl;
453 cerr << endl;
454 cerr << "Addresses from a call trace are read as binary data from the files" << endl;
455 cerr << "specified, or from stdin if no files are specified. These addresses" << endl;
456 cerr << "are used with the symbolic information from the executable to create" << endl;
457 cerr << "a call graph. This call graph is used to `score' arbitrary symbol" << endl;
458 cerr << "orderings, and provides the fitness function for the GA." << endl;
459 cerr << endl;
460 }
462 /**
463 * Using the symbol table, map a stream of address references into a
464 * callgraph and a histogram.
465 */
466 static void
467 map_addrs(int fd)
468 {
469 const Elf32_Sym *last = 0;
470 unsigned int buf[128];
471 ssize_t cb;
473 unsigned int count = 0;
474 while ((cb = read(fd, buf, sizeof buf)) > 0) {
475 if (cb % sizeof buf[0])
476 fprintf(stderr, "unaligned read\n");
478 unsigned int *addr = buf;
479 unsigned int *limit = buf + (cb / 4);
481 for (; addr < limit; ++addr) {
482 const Elf32_Sym *sym = symtab.lookup(*addr);
484 if (last && sym && last != sym) {
485 ++total_calls;
486 ++histogram[sym];
487 ++call_graph[call_pair(last, sym)];
489 if (opt_tick && (++count % opt_tick == 0)) {
490 cerr << ".";
491 flush(cerr);
492 }
493 }
495 last = sym;
496 }
497 }
499 if (opt_tick)
500 cerr << endl;
502 cerr << "Total calls: " << total_calls << endl;
503 total_calls *= 1024;
505 if (opt_window)
506 total_calls <<= (opt_window + 1);
507 }
509 static symbol_order *
510 pick_parent(symbol_order *ordering, int max, int index)
511 {
512 while (1) {
513 index -= ordering->m_score;
514 if (index < 0)
515 break;
517 ++ordering;
518 }
520 return ordering;
521 }
523 /**
524 * The main program
525 */
526 int
527 main(int argc, char *argv[])
528 {
529 const char *opt_exe = 0;
531 int c;
532 while (1) {
533 int option_index = 0;
534 c = getopt_long(argc, argv, "?de:g:m:o:p:s:t:vw:", long_options, &option_index);
536 if (c < 0)
537 break;
539 switch (c) {
540 case '?':
541 usage(argv[0]);
542 return 0;
544 case 'd':
545 opt_debug = true;
546 break;
548 case 'e':
549 opt_exe = optarg;
550 break;
552 case 'g':
553 opt_generations = atoi(optarg);
554 break;
556 case 'm':
557 opt_mutate = atoi(optarg);
558 break;
560 case 'o':
561 opt_out = optarg;
562 break;
564 case 'p':
565 opt_population_size = atoi(optarg);
566 break;
568 case 's':
569 srand(atoi(optarg));
570 break;
572 case 't':
573 opt_tick = optarg ? atoi(optarg) : 1000000;
574 break;
576 case 'v':
577 opt_verbose = true;
578 break;
580 case 'w':
581 opt_window = atoi(optarg);
582 if (opt_window < 0 || opt_window > 8) {
583 cerr << "invalid window size: " << opt_window << endl;
584 return 1;
585 }
587 break;
589 default:
590 usage(argv[0]);
591 return 1;
592 }
593 }
595 // Make sure an image was specified
596 if (! opt_exe) {
597 usage(argv[0]);
598 return 1;
599 }
601 // Read the sym table.
602 symtab.init(opt_exe);
604 // Process addresses to construct the call graph.
605 if (optind >= argc) {
606 map_addrs(STDIN_FILENO);
607 }
608 else {
609 do {
610 int fd = open(argv[optind], O_RDONLY);
611 if (fd < 0) {
612 perror(argv[optind]);
613 return 1;
614 }
616 map_addrs(fd);
617 close(fd);
618 } while (++optind < argc);
619 }
621 if (opt_debug) {
622 cerr << "Call graph:" << endl;
624 call_graph_t::const_iterator limit = call_graph.end();
625 call_graph_t::const_iterator i;
626 for (i = call_graph.begin(); i != limit; ++i) {
627 const call_pair& pair = i->first;
628 cerr.form("%08x %08x %10d\n",
629 pair.m_lo->st_value,
630 pair.m_hi->st_value,
631 i->second);
632 }
633 }
635 // Collect the symbols into a vector
636 symbol_order::vector_t ordering;
637 elf_symbol_table::const_iterator end = symtab.end();
638 for (elf_symbol_table::const_iterator sym = symtab.begin(); sym != end; ++sym) {
639 if (symtab.is_function(sym))
640 ordering.push_back(sym);
641 }
643 if (opt_verbose) {
644 symbol_order initial;
645 initial.m_ordering = ordering;
646 cerr << "created initial ordering, score=" << symbol_order::compute_score(initial) << endl;
648 if (opt_debug)
649 cerr << initial;
650 }
652 // Create a population.
653 if (opt_verbose)
654 cerr << "creating population" << endl;
656 symbol_order *population = new symbol_order[opt_population_size];
658 symbol_order::score_t total = 0, min = symbol_order::max_score, max = 0;
660 // Score it.
661 symbol_order *order = population;
662 symbol_order *limit = population + opt_population_size;
663 for (; order < limit; ++order) {
664 order->m_ordering = ordering;
665 order->shuffle();
667 symbol_order::score_t score = symbol_order::compute_score(*order);
669 if (opt_debug)
670 cerr << *order;
672 if (min > score)
673 min = score;
674 if (max < score)
675 max = score;
677 total += score;
678 }
680 if (opt_verbose) {
681 cerr << "Initial population";
682 cerr << ": min=" << min;
683 cerr << ", max=" << max;
684 cerr << " mean=" << (total / opt_population_size);
685 cerr << endl;
686 }
689 // Run the GA.
690 if (opt_verbose)
691 cerr << "begininng ga" << endl;
693 symbol_order::score_t best = 0;
695 for (int generation = 1; generation <= opt_generations; ++generation) {
696 // Create a new population.
697 symbol_order *offspring = new symbol_order[opt_population_size];
699 symbol_order *kid = offspring;
700 symbol_order *offspring_limit = offspring + opt_population_size;
701 for (; kid < offspring_limit; ++kid) {
702 // Pick parents.
703 symbol_order *father, *mother;
704 father = pick_parent(population, max, llrand() % total);
705 mother = pick_parent(population, max, llrand() % total);
707 // Create a kid.
708 kid->crossover_from(father, mother);
710 // Mutate, possibly.
711 if (opt_mutate) {
712 if (rand() % opt_mutate == 0)
713 kid->mutate();
714 }
715 }
717 delete[] population;
718 population = offspring;
720 // Score the new population.
721 total = 0;
722 min = symbol_order::max_score;
723 max = 0;
725 symbol_order *fittest = 0;
727 limit = offspring_limit;
728 for (order = population; order < limit; ++order) {
729 symbol_order::score_t score = symbol_order::compute_score(*order);
731 if (opt_debug)
732 cerr << *order;
734 if (min > score)
735 min = score;
737 if (max < score)
738 max = score;
740 if (best < score) {
741 best = score;
742 fittest = order;
743 }
745 total += score;
746 }
748 if (opt_verbose) {
749 cerr << "Generation " << generation;
750 cerr << ": min=" << min;
751 cerr << ", max=" << max;
752 if (fittest)
753 cerr << "*";
754 cerr << " mean=" << (total / opt_population_size);
755 cerr << endl;
756 }
758 // If we've found a new ``best'' individual, dump it.
759 if (fittest)
760 fittest->dump_symbols();
761 }
763 delete[] population;
764 return 0;
765 }
