1 # Copyright 2014 The Chromium Authors. All rights reserved.
2 # Use of this source code is governed by a BSD-style license that can be
3 # found in the LICENSE file.
18 # addr2line builds a possibly infinite memory cache that can exhaust
19 # the computer's memory if allowed to grow for too long. This constant
20 # controls how many lookups we do before restarting the process. 4000
21 # gives near peak performance without extreme memory usage.
22 ADDR2LINE_RECYCLE_LIMIT = 4000
25 class ELFSymbolizer(object):
26 """An uber-fast (multiprocessing, pipelined and asynchronous) ELF symbolizer.
28 This class is a frontend for addr2line (part of GNU binutils), designed to
29 symbolize batches of large numbers of symbols for a given ELF file. It
30 supports sharding symbolization against many addr2line instances and
31 pipelining of multiple requests per each instance (in order to hide addr2line
32 internals and OS pipe latencies).
34 The interface exhibited by this class is a very simple asynchronous interface,
35 which is based on the following three methods:
36 - SymbolizeAsync(): used to request (enqueue) resolution of a given address.
37 - The |callback| method: used to communicated back the symbol information.
38 - Join(): called to conclude the batch to gather the last outstanding results.
39 In essence, before the Join method returns, this class will have issued as
40 many callbacks as the number of SymbolizeAsync() calls. In this regard, note
41 that due to multiprocess sharding, callbacks can be delivered out of order.
43 Some background about addr2line:
44 - it is invoked passing the elf path in the cmdline, piping the addresses in
45 its stdin and getting results on its stdout.
46 - it has pretty large response times for the first requests, but it
47 works very well in streaming mode once it has been warmed up.
48 - it doesn't scale by itself (on more cores). However, spawning multiple
49 instances at the same time on the same file is pretty efficient as they
50 keep hitting the pagecache and become mostly CPU bound.
51 - it might hang or crash, mostly for OOM. This class deals with both of these
54 Despite the "scary" imports and the multi* words above, (almost) no multi-
55 threading/processing is involved from the python viewpoint. Concurrency
56 here is achieved by spawning several addr2line subprocesses and handling their
57 output pipes asynchronously. Therefore, all the code here (with the exception
58 of the Queue instance in Addr2Line) should be free from mind-blowing
59 thread-safety concerns.
61 The multiprocess sharding works as follows:
62 The symbolizer tries to use the lowest number of addr2line instances as
63 possible (with respect of |max_concurrent_jobs|) and enqueue all the requests
64 in a single addr2line instance. For few symbols (i.e. dozens) sharding isn't
65 worth the startup cost.
66 The multiprocess logic kicks in as soon as the queues for the existing
67 instances grow. Specifically, once all the existing instances reach the
68 |max_queue_size| bound, a new addr2line instance is kicked in.
69 In the case of a very eager producer (i.e. all |max_concurrent_jobs| instances
70 have a backlog of |max_queue_size|), back-pressure is applied on the caller by
71 blocking the SymbolizeAsync method.
73 This module has been deliberately designed to be dependency free (w.r.t. of
74 other modules in this project), to allow easy reuse in external projects.
77 def __init__(self, elf_file_path, addr2line_path, callback, inlines=False,
78 max_concurrent_jobs=None, addr2line_timeout=30, max_queue_size=50,
79 source_root_path=None, strip_base_path=None):
81 elf_file_path: path of the elf file to be symbolized.
82 addr2line_path: path of the toolchain's addr2line binary.
83 callback: a callback which will be invoked for each resolved symbol with
84 the two args (sym_info, callback_arg). The former is an instance of
85 |ELFSymbolInfo| and contains the symbol information. The latter is an
86 embedder-provided argument which is passed to SymbolizeAsync().
87 inlines: when True, the ELFSymbolInfo will contain also the details about
88 the outer inlining functions. When False, only the innermost function
90 max_concurrent_jobs: Max number of addr2line instances spawned.
91 Parallelize responsibly, addr2line is a memory and I/O monster.
92 max_queue_size: Max number of outstanding requests per addr2line instance.
93 addr2line_timeout: Max time (in seconds) to wait for a addr2line response.
94 After the timeout, the instance will be considered hung and respawned.
95 source_root_path: In some toolchains only the name of the source file is
96 is output, without any path information; disambiguation searches
97 through the source directory specified by |source_root_path| argument
98 for files whose name matches, adding the full path information to the
99 output. For example, if the toolchain outputs "unicode.cc" and there
100 is a file called "unicode.cc" located under |source_root_path|/foo,
101 the tool will replace "unicode.cc" with
102 "|source_root_path|/foo/unicode.cc". If there are multiple files with
103 the same name, disambiguation will fail because the tool cannot
104 determine which of the files was the source of the symbol.
105 strip_base_path: Rebases the symbols source paths onto |source_root_path|
106 (i.e replace |strip_base_path| with |source_root_path).
108 assert(os.path.isfile(addr2line_path)), 'Cannot find ' + addr2line_path
109 self.elf_file_path = elf_file_path
110 self.addr2line_path = addr2line_path
111 self.callback = callback
112 self.inlines = inlines
113 self.max_concurrent_jobs = (max_concurrent_jobs or
114 min(multiprocessing.cpu_count(), 4))
115 self.max_queue_size = max_queue_size
116 self.addr2line_timeout = addr2line_timeout
117 self.requests_counter = 0 # For generating monotonic request IDs.
118 self._a2l_instances = [] # Up to |max_concurrent_jobs| _Addr2Line inst.
120 # If necessary, create disambiguation lookup table
121 self.disambiguate = source_root_path is not None
122 self.disambiguation_table = {}
123 self.strip_base_path = strip_base_path
124 if(self.disambiguate):
125 self.source_root_path = os.path.abspath(source_root_path)
126 self._CreateDisambiguationTable()
128 # Create one addr2line instance. More instances will be created on demand
129 # (up to |max_concurrent_jobs|) depending on the rate of the requests.
130 self._CreateNewA2LInstance()
132 def SymbolizeAsync(self, addr, callback_arg=None):
133 """Requests symbolization of a given address.
135 This method is not guaranteed to return immediately. It generally does, but
136 in some scenarios (e.g. all addr2line instances have full queues) it can
137 block to create back-pressure.
140 addr: address to symbolize.
141 callback_arg: optional argument which will be passed to the |callback|."""
142 assert(isinstance(addr, int))
144 # Process all the symbols that have been resolved in the meanwhile.
145 # Essentially, this drains all the addr2line(s) out queues.
146 for a2l_to_purge in self._a2l_instances:
147 a2l_to_purge.ProcessAllResolvedSymbolsInQueue()
148 a2l_to_purge.RecycleIfNecessary()
150 # Find the best instance according to this logic:
151 # 1. Find an existing instance with the shortest queue.
152 # 2. If all of instances' queues are full, but there is room in the pool,
153 # (i.e. < |max_concurrent_jobs|) create a new instance.
154 # 3. If there were already |max_concurrent_jobs| instances and all of them
155 # had full queues, make back-pressure.
158 def _SortByQueueSizeAndReqID(a2l):
159 return (a2l.queue_size, a2l.first_request_id)
160 a2l = min(self._a2l_instances, key=_SortByQueueSizeAndReqID)
163 if (a2l.queue_size >= self.max_queue_size and
164 len(self._a2l_instances) < self.max_concurrent_jobs):
165 a2l = self._CreateNewA2LInstance()
168 if a2l.queue_size >= self.max_queue_size:
169 a2l.WaitForNextSymbolInQueue()
171 a2l.EnqueueRequest(addr, callback_arg)
174 """Waits for all the outstanding requests to complete and terminates."""
175 for a2l in self._a2l_instances:
179 def _CreateNewA2LInstance(self):
180 assert(len(self._a2l_instances) < self.max_concurrent_jobs)
181 a2l = ELFSymbolizer.Addr2Line(self)
182 self._a2l_instances.append(a2l)
185 def _CreateDisambiguationTable(self):
186 """ Non-unique file names will result in None entries"""
187 self.disambiguation_table = {}
189 for root, _, filenames in os.walk(self.source_root_path):
191 self.disambiguation_table[f] = os.path.join(root, f) if (f not in
192 self.disambiguation_table) else None
195 class Addr2Line(object):
196 """A python wrapper around an addr2line instance.
198 The communication with the addr2line process looks as follows:
199 [STDIN] [STDOUT] (from addr2line's viewpoint)
202 < Symbol::Name(foo, bar) for f001111
203 < /path/to/source/file.c:line_number
205 < Symbol::Name2() for f002222
206 < /path/to/source/file.c:line_number
207 < Symbol::Name3() for f003333
208 < /path/to/source/file.c:line_number
211 SYM_ADDR_RE = re.compile(r'([^:]+):(\?|\d+).*')
213 def __init__(self, symbolizer):
214 self._symbolizer = symbolizer
215 self._lib_file_name = posixpath.basename(symbolizer.elf_file_path)
217 # The request queue (i.e. addresses pushed to addr2line's stdin and not
218 # yet retrieved on stdout)
219 self._request_queue = collections.deque()
221 # This is essentially len(self._request_queue). It has been optimized to a
222 # separate field because turned out to be a perf hot-spot.
225 # Keep track of the number of symbols a process has processed to
226 # avoid a single process growing too big and using all the memory.
227 self._processed_symbols_count = 0
229 # Objects required to handle the addr2line subprocess.
230 self._proc = None # Subprocess.Popen(...) instance.
231 self._thread = None # Threading.thread instance.
232 self._out_queue = None # Queue.Queue instance (for buffering a2l stdout).
233 self._RestartAddr2LineProcess()
235 def EnqueueRequest(self, addr, callback_arg):
236 """Pushes an address to addr2line's stdin (and keeps track of it)."""
237 self._symbolizer.requests_counter += 1 # For global "age" of requests.
238 req_idx = self._symbolizer.requests_counter
239 self._request_queue.append((addr, callback_arg, req_idx))
241 self._WriteToA2lStdin(addr)
243 def WaitForIdle(self):
244 """Waits until all the pending requests have been symbolized."""
245 while self.queue_size > 0:
246 self.WaitForNextSymbolInQueue()
248 def WaitForNextSymbolInQueue(self):
249 """Waits for the next pending request to be symbolized."""
250 if not self.queue_size:
253 # This outer loop guards against a2l hanging (detecting stdout timeout).
255 start_time = datetime.datetime.now()
256 timeout = datetime.timedelta(seconds=self._symbolizer.addr2line_timeout)
258 # The inner loop guards against a2l crashing (checking if it exited).
259 while (datetime.datetime.now() - start_time < timeout):
260 # poll() returns !None if the process exited. a2l should never exit.
261 if self._proc.poll():
262 logging.warning('addr2line crashed, respawning (lib: %s).' %
264 self._RestartAddr2LineProcess()
265 # TODO(primiano): the best thing to do in this case would be
266 # shrinking the pool size as, very likely, addr2line is crashed
267 # due to low memory (and the respawned one will die again soon).
270 lines = self._out_queue.get(block=True, timeout=0.25)
272 # On timeout (1/4 s.) repeat the inner loop and check if either the
273 # addr2line process did crash or we waited its output for too long.
276 # In nominal conditions, we get straight to this point.
277 self._ProcessSymbolOutput(lines)
280 # If this point is reached, we waited more than |addr2line_timeout|.
281 logging.warning('Hung addr2line process, respawning (lib: %s).' %
283 self._RestartAddr2LineProcess()
285 def ProcessAllResolvedSymbolsInQueue(self):
286 """Consumes all the addr2line output lines produced (without blocking)."""
287 if not self.queue_size:
291 lines = self._out_queue.get_nowait()
294 self._ProcessSymbolOutput(lines)
296 def RecycleIfNecessary(self):
297 """Restarts the process if it has been used for too long.
299 A long running addr2line process will consume excessive amounts
300 of memory without any gain in performance."""
301 if self._processed_symbols_count >= ADDR2LINE_RECYCLE_LIMIT:
302 self._RestartAddr2LineProcess()
306 """Kills the underlying addr2line process.
308 The poller |_thread| will terminate as well due to the broken pipe."""
311 self._proc.communicate() # Essentially wait() without risking deadlock.
312 except Exception: # An exception while terminating? How interesting.
316 def _WriteToA2lStdin(self, addr):
317 self._proc.stdin.write('%s\n' % hex(addr))
318 if self._symbolizer.inlines:
319 # In the case of inlines we output an extra blank line, which causes
320 # addr2line to emit a (??,??:0) tuple that we use as a boundary marker.
321 self._proc.stdin.write('\n')
322 self._proc.stdin.flush()
324 def _ProcessSymbolOutput(self, lines):
325 """Parses an addr2line symbol output and triggers the client callback."""
326 (_, callback_arg, _) = self._request_queue.popleft()
329 innermost_sym_info = None
331 for (line1, line2) in lines:
332 prev_sym_info = sym_info
333 name = line1 if not line1.startswith('?') else None
336 m = ELFSymbolizer.Addr2Line.SYM_ADDR_RE.match(line2)
338 if not m.group(1).startswith('?'):
339 source_path = m.group(1)
340 if not m.group(2).startswith('?'):
341 source_line = int(m.group(2))
343 logging.warning('Got invalid symbol path from addr2line: %s' % line2)
345 # In case disambiguation is on, and needed
346 was_ambiguous = False
347 disambiguated = False
348 if self._symbolizer.disambiguate:
349 if source_path and not posixpath.isabs(source_path):
350 path = self._symbolizer.disambiguation_table.get(source_path)
352 disambiguated = path is not None
353 source_path = path if disambiguated else source_path
355 # Use absolute paths (so that paths are consistent, as disambiguation
356 # uses absolute paths)
357 if source_path and not was_ambiguous:
358 source_path = os.path.abspath(source_path)
360 if source_path and self._symbolizer.strip_base_path:
361 # Strip the base path
362 source_path = re.sub('^' + self._symbolizer.strip_base_path,
363 self._symbolizer.source_root_path or '', source_path)
365 sym_info = ELFSymbolInfo(name, source_path, source_line, was_ambiguous,
368 prev_sym_info.inlined_by = sym_info
369 if not innermost_sym_info:
370 innermost_sym_info = sym_info
372 self._processed_symbols_count += 1
373 self._symbolizer.callback(innermost_sym_info, callback_arg)
375 def _RestartAddr2LineProcess(self):
379 # The only reason of existence of this Queue (and the corresponding
380 # Thread below) is the lack of a subprocess.stdout.poll_avail_lines().
381 # Essentially this is a pipe able to extract a couple of lines atomically.
382 self._out_queue = Queue.Queue()
384 # Start the underlying addr2line process in line buffered mode.
386 cmd = [self._symbolizer.addr2line_path, '--functions', '--demangle',
387 '--exe=' + self._symbolizer.elf_file_path]
388 if self._symbolizer.inlines:
390 self._proc = subprocess.Popen(cmd, bufsize=1, stdout=subprocess.PIPE,
391 stdin=subprocess.PIPE, stderr=sys.stderr, close_fds=True)
393 # Start the poller thread, which simply moves atomically the lines read
394 # from the addr2line's stdout to the |_out_queue|.
395 self._thread = threading.Thread(
396 target=ELFSymbolizer.Addr2Line.StdoutReaderThread,
397 args=(self._proc.stdout, self._out_queue, self._symbolizer.inlines))
398 self._thread.daemon = True # Don't prevent early process exit.
401 self._processed_symbols_count = 0
403 # Replay the pending requests on the new process (only for the case
404 # of a hung addr2line timing out during the game).
405 for (addr, _, _) in self._request_queue:
406 self._WriteToA2lStdin(addr)
409 def StdoutReaderThread(process_pipe, queue, inlines):
410 """The poller thread fn, which moves the addr2line stdout to the |queue|.
412 This is the only piece of code not running on the main thread. It merely
413 writes to a Queue, which is thread-safe. In the case of inlines, it
414 detects the ??,??:0 marker and sends the lines atomically, such that the
415 main thread always receives all the lines corresponding to one symbol in
418 lines_for_one_symbol = []
420 line1 = process_pipe.readline().rstrip('\r\n')
421 line2 = process_pipe.readline().rstrip('\r\n')
422 if not line1 or not line2:
424 inline_has_more_lines = inlines and (len(lines_for_one_symbol) == 0 or
425 (line1 != '??' and line2 != '??:0'))
426 if not inlines or inline_has_more_lines:
427 lines_for_one_symbol += [(line1, line2)]
428 if inline_has_more_lines:
430 queue.put(lines_for_one_symbol)
431 lines_for_one_symbol = []
434 # Every addr2line processes will die at some point, please die silently.
435 except (IOError, OSError):
439 def first_request_id(self):
440 """Returns the request_id of the oldest pending request in the queue."""
441 return self._request_queue[0][2] if self._request_queue else 0
444 class ELFSymbolInfo(object):
445 """The result of the symbolization passed as first arg. of each callback."""
447 def __init__(self, name, source_path, source_line, was_ambiguous=False,
448 disambiguated=False):
449 """All the fields here can be None (if addr2line replies with '??')."""
451 self.source_path = source_path
452 self.source_line = source_line
453 # In the case of |inlines|=True, the |inlined_by| points to the outer
454 # function inlining the current one (and so on, to form a chain).
455 self.inlined_by = None
456 self.disambiguated = disambiguated
457 self.was_ambiguous = was_ambiguous
460 return '%s [%s:%d]' % (
461 self.name or '??', self.source_path or '??', self.source_line or 0)