1/*
2 * Copyright (c) 2013 Luca Clementi <luca.clementi@gmail.com>
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 * 3. The name of the author may not be used to endorse or promote products
13 *    derived from this software without specific prior written permission.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "defs.h"
28#include <limits.h>
29#include <libunwind-ptrace.h>
30
31#ifdef _LARGEFILE64_SOURCE
32# ifdef HAVE_FOPEN64
33#  define fopen_for_input fopen64
34# else
35#  define fopen_for_input fopen
36# endif
37#else
38# define fopen_for_input fopen
39#endif
40
41#define DPRINTF(F, A, ...) if (debug_flag) fprintf(stderr, " [unwind(" A ")] " F "\n", __VA_ARGS__)
42
43/*
44 * Кeep a sorted array of cache entries,
45 * so that we can binary search through it.
46 */
47struct mmap_cache_t {
48	/**
49	 * example entry:
50	 * 7fabbb09b000-7fabbb09f000 r-xp 00179000 fc:00 1180246 /lib/libc-2.11.1.so
51	 *
52	 * start_addr  is 0x7fabbb09b000
53	 * end_addr    is 0x7fabbb09f000
54	 * mmap_offset is 0x179000
55	 * binary_filename is "/lib/libc-2.11.1.so"
56	 */
57	unsigned long start_addr;
58	unsigned long end_addr;
59	unsigned long mmap_offset;
60	char *binary_filename;
61};
62
63/*
64 * Type used in stacktrace walker
65 */
66typedef void (*call_action_fn)(void *data,
67			       const char *binary_filename,
68			       const char *symbol_name,
69			       unw_word_t function_offset,
70			       unsigned long true_offset);
71typedef void (*error_action_fn)(void *data,
72				const char *error,
73				unsigned long true_offset);
74
75/*
76 * Type used in stacktrace capturing
77 */
78struct call_t {
79       struct call_t* next;
80       char *output_line;
81};
82
83struct queue_t {
84       struct call_t *tail;
85       struct call_t *head;
86};
87
88static void queue_print(struct queue_t *queue);
89static void delete_mmap_cache(struct tcb *tcp, const char *caller);
90
91static unw_addr_space_t libunwind_as;
92static unsigned int mmap_cache_generation;
93
94void
95unwind_init(void)
96{
97	libunwind_as = unw_create_addr_space(&_UPT_accessors, 0);
98	if (!libunwind_as)
99		error_msg_and_die("failed to create address space for stack tracing");
100	unw_set_caching_policy(libunwind_as, UNW_CACHE_GLOBAL);
101}
102
103void
104unwind_tcb_init(struct tcb *tcp)
105{
106	tcp->libunwind_ui = _UPT_create(tcp->pid);
107	if (!tcp->libunwind_ui)
108		die_out_of_memory();
109
110	tcp->queue = malloc(sizeof(*tcp->queue));
111	if (!tcp->queue)
112		die_out_of_memory();
113	tcp->queue->head = NULL;
114	tcp->queue->tail = NULL;
115}
116
117void
118unwind_tcb_fin(struct tcb *tcp)
119{
120	queue_print(tcp->queue);
121	free(tcp->queue);
122	tcp->queue = NULL;
123
124	delete_mmap_cache(tcp, __FUNCTION__);
125
126	_UPT_destroy(tcp->libunwind_ui);
127	tcp->libunwind_ui = NULL;
128}
129
130/*
131 * caching of /proc/ID/maps for each process to speed up stack tracing
132 *
133 * The cache must be refreshed after syscalls that affect memory mappings,
134 * e.g. mmap, mprotect, munmap, execve.
135 */
136static void
137build_mmap_cache(struct tcb* tcp)
138{
139	FILE *fp;
140	struct mmap_cache_t *cache_head;
141	/* start with a small dynamically-allocated array and then expand it */
142	size_t cur_array_size = 10;
143	char filename[sizeof("/proc/4294967296/maps")];
144	char buffer[PATH_MAX + 80];
145
146	unw_flush_cache(libunwind_as, 0, 0);
147
148	sprintf(filename, "/proc/%u/maps", tcp->pid);
149	fp = fopen_for_input(filename, "r");
150	if (!fp) {
151		perror_msg("fopen: %s", filename);
152		return;
153	}
154
155	cache_head = calloc(cur_array_size, sizeof(*cache_head));
156	if (!cache_head)
157		die_out_of_memory();
158
159	while (fgets(buffer, sizeof(buffer), fp) != NULL) {
160		struct mmap_cache_t *entry;
161		unsigned long start_addr, end_addr, mmap_offset;
162		char exec_bit;
163		char binary_path[PATH_MAX];
164
165		if (sscanf(buffer, "%lx-%lx %*c%*c%c%*c %lx %*x:%*x %*d %[^\n]",
166			   &start_addr, &end_addr, &exec_bit,
167			   &mmap_offset, binary_path) != 5)
168			continue;
169
170		/* ignore mappings that have no PROT_EXEC bit set */
171		if (exec_bit != 'x')
172			continue;
173
174		if (end_addr < start_addr) {
175			error_msg("%s: unrecognized file format", filename);
176			break;
177		}
178
179		/*
180		 * sanity check to make sure that we're storing
181		 * non-overlapping regions in ascending order
182		 */
183		if (tcp->mmap_cache_size > 0) {
184			entry = &cache_head[tcp->mmap_cache_size - 1];
185			if (entry->start_addr == start_addr &&
186			    entry->end_addr == end_addr) {
187				/* duplicate entry, e.g. [vsyscall] */
188				continue;
189			}
190			if (start_addr <= entry->start_addr ||
191			    start_addr < entry->end_addr) {
192				error_msg("%s: overlapping memory region",
193					  filename);
194				continue;
195			}
196		}
197
198		if (tcp->mmap_cache_size >= cur_array_size) {
199			cur_array_size *= 2;
200			cache_head = realloc(cache_head,
201					     cur_array_size * sizeof(*cache_head));
202			if (!cache_head)
203				die_out_of_memory();
204		}
205
206		entry = &cache_head[tcp->mmap_cache_size];
207		entry->start_addr = start_addr;
208		entry->end_addr = end_addr;
209		entry->mmap_offset = mmap_offset;
210		entry->binary_filename = strdup(binary_path);
211		if (!entry->binary_filename)
212			die_out_of_memory();
213		tcp->mmap_cache_size++;
214	}
215	fclose(fp);
216	tcp->mmap_cache = cache_head;
217	tcp->mmap_cache_generation = mmap_cache_generation;
218
219	DPRINTF("tgen=%u, ggen=%u, tcp=%p, cache=%p",
220		"cache-build",
221		tcp->mmap_cache_generation,
222		mmap_cache_generation,
223		tcp, tcp->mmap_cache);
224}
225
226/* deleting the cache */
227static void
228delete_mmap_cache(struct tcb *tcp, const char *caller)
229{
230	unsigned int i;
231
232	DPRINTF("tgen=%u, ggen=%u, tcp=%p, cache=%p, caller=%s",
233		"cache-delete",
234		tcp->mmap_cache_generation,
235		mmap_cache_generation,
236		tcp, tcp->mmap_cache, caller);
237
238	for (i = 0; i < tcp->mmap_cache_size; i++) {
239		free(tcp->mmap_cache[i].binary_filename);
240		tcp->mmap_cache[i].binary_filename = NULL;
241	}
242	free(tcp->mmap_cache);
243	tcp->mmap_cache = NULL;
244	tcp->mmap_cache_size = 0;
245}
246
247static bool
248rebuild_cache_if_invalid(struct tcb *tcp, const char *caller)
249{
250	if ((tcp->mmap_cache_generation != mmap_cache_generation)
251	    && tcp->mmap_cache)
252		delete_mmap_cache(tcp, caller);
253
254	if (!tcp->mmap_cache)
255		build_mmap_cache(tcp);
256
257	if (!tcp->mmap_cache || !tcp->mmap_cache_size)
258		return false;
259	else
260		return true;
261}
262
263void
264unwind_cache_invalidate(struct tcb* tcp)
265{
266#if SUPPORTED_PERSONALITIES > 1
267	if (tcp->currpers != DEFAULT_PERSONALITY) {
268		/* disable strack trace */
269		return;
270	}
271#endif
272	mmap_cache_generation++;
273	DPRINTF("tgen=%u, ggen=%u, tcp=%p, cache=%p", "increment",
274		tcp->mmap_cache_generation,
275		mmap_cache_generation,
276		tcp,
277		tcp->mmap_cache);
278}
279
280static void
281get_symbol_name(unw_cursor_t *cursor, char **name,
282		size_t *size, unw_word_t *offset)
283{
284	for (;;) {
285		int rc = unw_get_proc_name(cursor, *name, *size, offset);
286		if (rc == 0)
287			break;
288		if (rc != -UNW_ENOMEM) {
289			**name = '\0';
290			*offset = 0;
291			break;
292		}
293		*size *= 2;
294		*name = realloc(*name, *size);
295		if (!*name)
296			die_out_of_memory();
297	}
298}
299
300static int
301print_stack_frame(struct tcb *tcp,
302		  call_action_fn call_action,
303		  error_action_fn error_action,
304		  void *data,
305		  unw_cursor_t *cursor,
306		  char **symbol_name,
307		  size_t *symbol_name_size)
308{
309	unw_word_t ip;
310	int lower = 0;
311	int upper = (int) tcp->mmap_cache_size - 1;
312
313	if (unw_get_reg(cursor, UNW_REG_IP, &ip) < 0) {
314		perror_msg("Can't walk the stack of process %d", tcp->pid);
315		return -1;
316	}
317
318	while (lower <= upper) {
319		struct mmap_cache_t *cur_mmap_cache;
320		int mid = (upper + lower) / 2;
321
322		cur_mmap_cache = &tcp->mmap_cache[mid];
323
324		if (ip >= cur_mmap_cache->start_addr &&
325		    ip < cur_mmap_cache->end_addr) {
326			unsigned long true_offset;
327			unw_word_t function_offset;
328
329			get_symbol_name(cursor, symbol_name, symbol_name_size,
330					&function_offset);
331			true_offset = ip - cur_mmap_cache->start_addr +
332				cur_mmap_cache->mmap_offset;
333			call_action(data,
334				    cur_mmap_cache->binary_filename,
335				    *symbol_name,
336				    function_offset,
337				    true_offset);
338			return 0;
339		}
340		else if (ip < cur_mmap_cache->start_addr)
341			upper = mid - 1;
342		else
343			lower = mid + 1;
344	}
345
346	/*
347	 * there is a bug in libunwind >= 1.0
348	 * after a set_tid_address syscall
349	 * unw_get_reg returns IP == 0
350	 */
351	if(ip)
352		error_action(data, "unexpected_backtracing_error", ip);
353	return -1;
354}
355
356/*
357 * walking the stack
358 */
359static void
360stacktrace_walk(struct tcb *tcp,
361		call_action_fn call_action,
362		error_action_fn error_action,
363		void *data)
364{
365	char *symbol_name;
366	size_t symbol_name_size = 40;
367	unw_cursor_t cursor;
368	int stack_depth;
369
370	if (!tcp->mmap_cache)
371		error_msg_and_die("bug: mmap_cache is NULL");
372	if (tcp->mmap_cache_size == 0)
373		error_msg_and_die("bug: mmap_cache is empty");
374
375	symbol_name = malloc(symbol_name_size);
376	if (!symbol_name)
377		die_out_of_memory();
378
379	if (unw_init_remote(&cursor, libunwind_as, tcp->libunwind_ui) < 0)
380		perror_msg_and_die("Can't initiate libunwind");
381
382	for (stack_depth = 0; stack_depth < 256; ++stack_depth) {
383		if (print_stack_frame(tcp, call_action, error_action, data,
384				&cursor, &symbol_name, &symbol_name_size) < 0)
385			break;
386		if (unw_step(&cursor) <= 0)
387			break;
388	}
389	if (stack_depth >= 256)
390		error_action(data, "too many stack frames", 0);
391
392	free(symbol_name);
393}
394
395/*
396 * printing an entry in stack to stream or buffer
397 */
398/*
399 * we want to keep the format used by backtrace_symbols from the glibc
400 *
401 * ./a.out() [0x40063d]
402 * ./a.out() [0x4006bb]
403 * ./a.out() [0x4006c6]
404 * /lib64/libc.so.6(__libc_start_main+0xed) [0x7fa2f8a5976d]
405 * ./a.out() [0x400569]
406 */
407#define STACK_ENTRY_SYMBOL_FMT			\
408	" > %s(%s+0x%lx) [0x%lx]\n",		\
409	binary_filename,			\
410	symbol_name,				\
411	(unsigned long) function_offset,	\
412	true_offset
413#define STACK_ENTRY_NOSYMBOL_FMT		\
414	" > %s() [0x%lx]\n",			\
415	binary_filename, true_offset
416#define STACK_ENTRY_BUG_FMT			\
417	" > BUG IN %s\n"
418#define STACK_ENTRY_ERROR_WITH_OFFSET_FMT	\
419	" > %s [0x%lx]\n", error, true_offset
420#define STACK_ENTRY_ERROR_FMT			\
421	" > %s\n", error
422
423static void
424print_call_cb(void *dummy,
425	      const char *binary_filename,
426	      const char *symbol_name,
427	      unw_word_t function_offset,
428	      unsigned long true_offset)
429{
430	if (symbol_name)
431		tprintf(STACK_ENTRY_SYMBOL_FMT);
432	else if (binary_filename)
433		tprintf(STACK_ENTRY_NOSYMBOL_FMT);
434	else
435		tprintf(STACK_ENTRY_BUG_FMT, __FUNCTION__);
436
437	line_ended();
438}
439
440static void
441print_error_cb(void *dummy,
442	       const char *error,
443	       unsigned long true_offset)
444{
445	if (true_offset)
446		tprintf(STACK_ENTRY_ERROR_WITH_OFFSET_FMT);
447	else
448		tprintf(STACK_ENTRY_ERROR_FMT);
449
450	line_ended();
451}
452
453static char *
454sprint_call_or_error(const char *binary_filename,
455		     const char *symbol_name,
456		     unw_word_t function_offset,
457		     unsigned long true_offset,
458		     const char *error)
459{
460       char *output_line = NULL;
461       int n;
462
463       if (symbol_name)
464               n = asprintf(&output_line, STACK_ENTRY_SYMBOL_FMT);
465       else if (binary_filename)
466               n = asprintf(&output_line, STACK_ENTRY_NOSYMBOL_FMT);
467       else if (error)
468               n = true_offset
469                       ? asprintf(&output_line, STACK_ENTRY_ERROR_WITH_OFFSET_FMT)
470                       : asprintf(&output_line, STACK_ENTRY_ERROR_FMT);
471       else
472               n = asprintf(&output_line, STACK_ENTRY_BUG_FMT, __FUNCTION__);
473
474       if (n < 0)
475               error_msg_and_die("error in asprintf");
476
477       return output_line;
478}
479
480/*
481 * queue manipulators
482 */
483static void
484queue_put(struct queue_t *queue,
485	  const char *binary_filename,
486	  const char *symbol_name,
487	  unw_word_t function_offset,
488	  unsigned long true_offset,
489	  const char *error)
490{
491	struct call_t *call;
492
493	call = malloc(sizeof(*call));
494	if (!call)
495		die_out_of_memory();
496
497	call->output_line = sprint_call_or_error(binary_filename,
498						 symbol_name,
499						 function_offset,
500						 true_offset,
501						 error);
502	call->next = NULL;
503
504	if (!queue->head) {
505		queue->head = call;
506		queue->tail = call;
507	} else {
508		queue->tail->next = call;
509		queue->tail = call;
510	}
511}
512
513static void
514queue_put_call(void *queue,
515	       const char *binary_filename,
516	       const char *symbol_name,
517	       unw_word_t function_offset,
518	       unsigned long true_offset)
519{
520	queue_put(queue,
521		  binary_filename,
522		  symbol_name,
523		  function_offset,
524		  true_offset,
525		  NULL);
526}
527
528static void
529queue_put_error(void *queue,
530		const char *error,
531		unsigned long ip)
532{
533	queue_put(queue, NULL, NULL, 0, ip, error);
534}
535
536static void
537queue_print(struct queue_t *queue)
538{
539	struct call_t *call, *tmp;
540
541	queue->tail = NULL;
542	call = queue->head;
543	queue->head = NULL;
544	while (call) {
545		tmp = call;
546		call = call->next;
547
548		tprints(tmp->output_line);
549		line_ended();
550
551		free(tmp->output_line);
552		tmp->output_line = NULL;
553		tmp->next = NULL;
554		free(tmp);
555	}
556}
557
558/*
559 * printing stack
560 */
561void
562unwind_print_stacktrace(struct tcb* tcp)
563{
564#if SUPPORTED_PERSONALITIES > 1
565	if (tcp->currpers != DEFAULT_PERSONALITY) {
566		/* disable strack trace */
567		return;
568	}
569#endif
570       if (tcp->queue->head) {
571	       DPRINTF("tcp=%p, queue=%p", "queueprint", tcp, tcp->queue->head);
572	       queue_print(tcp->queue);
573       }
574       else if (rebuild_cache_if_invalid(tcp, __FUNCTION__)) {
575               DPRINTF("tcp=%p, queue=%p", "stackprint", tcp, tcp->queue->head);
576               stacktrace_walk(tcp, print_call_cb, print_error_cb, NULL);
577       }
578}
579
580/*
581 * capturing stack
582 */
583void
584unwind_capture_stacktrace(struct tcb *tcp)
585{
586#if SUPPORTED_PERSONALITIES > 1
587	if (tcp->currpers != DEFAULT_PERSONALITY) {
588		/* disable strack trace */
589		return;
590	}
591#endif
592	if (tcp->queue->head)
593		error_msg_and_die("bug: unprinted entries in queue");
594
595	if (rebuild_cache_if_invalid(tcp, __FUNCTION__)) {
596		stacktrace_walk(tcp, queue_put_call, queue_put_error,
597				tcp->queue);
598		DPRINTF("tcp=%p, queue=%p", "captured", tcp, tcp->queue->head);
599	}
600}
601