Fix the include paths in the document: s/google/glog/.
[platform/upstream/glog.git] / src / symbolize.cc
1 // Copyright 2006 Google Inc. All Rights Reserved.
2 // Author: Satoru Takabayashi
3 // Stack-footprint reduction work done by Raksit Ashok
4 //
5 // Implementation note:
6 //
7 // We don't use heaps but only use stacks.  We want to reduce the
8 // stack consumption so that the symbolizer can run on small stacks.
9 //
10 // Here are some numbers collected with GCC 4.1.0 on x86:
11 // - sizeof(Elf32_Sym)  = 16
12 // - sizeof(Elf32_Shdr) = 40
13 // - sizeof(Elf64_Sym)  = 24
14 // - sizeof(Elf64_Shdr) = 64
15 //
16 // This implementation is intended to be async-signal-safe but uses
17 // some functions which are not guaranteed to be so, such as memchr()
18 // and memmove().  We assume they are async-signal-safe.
19 //
20
21 #if defined(__ELF__)  // defined by gcc on Linux
22
23 #include <dlfcn.h>
24 #include <elf.h>
25 #include <errno.h>
26 #include <fcntl.h>
27 #include <limits.h>
28 #include <link.h>  // For ElfW() macro.
29 #include <stdint.h>
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <stddef.h>
33 #include <string.h>
34 #include <sys/stat.h>
35 #include <sys/types.h>
36 #include <unistd.h>
37
38 #include "symbolize.h"
39 #include "demangle.h"
40 #include "config.h"
41 #include "utilities.h"
42 #include "glog/raw_logging.h"
43
44 // Re-runs fn until it doesn't cause EINTR.
45 #define NO_INTR(fn)   do {} while ((fn) < 0 && errno == EINTR)
46
47 _START_GOOGLE_NAMESPACE_
48
49 // We don't use assert() since it's not guaranteed to be
50 // async-signal-safe.  Instead we define a minimal assertion
51 // macro. So far, we don't need pretty printing for __FILE__, etc.
52
53 // A wrapper for abort() to make it callable in ? :.
54 static int AssertFail() {
55   abort();
56   return 0;  // Should not reach.
57 }
58
59 #define SAFE_ASSERT(expr) ((expr) ? 0 : AssertFail())
60
61 // Read up to "count" bytes from file descriptor "fd" into the buffer
62 // starting at "buf" while handling short reads and EINTR.  On
63 // success, return the number of bytes read.  Otherwise, return -1.
64 static ssize_t ReadPersistent(const int fd, void *buf, const size_t count) {
65   SAFE_ASSERT(fd >= 0);
66   SAFE_ASSERT(count >= 0 && count <= SSIZE_MAX);
67   char *buf0 = reinterpret_cast<char *>(buf);
68   ssize_t num_bytes = 0;
69   while (num_bytes < count) {
70     ssize_t len;
71     NO_INTR(len = read(fd, buf0 + num_bytes, count - num_bytes));
72     if (len < 0) {  // There was an error other than EINTR.
73       return -1;
74     }
75     if (len == 0) {  // Reached EOF.
76       break;
77     }
78     num_bytes += len;
79   }
80   SAFE_ASSERT(num_bytes <= count);
81   return num_bytes;
82 }
83
84 // Read up to "count" bytes from "offset" in the file pointed by file
85 // descriptor "fd" into the buffer starting at "buf".  On success,
86 // return the number of bytes read.  Otherwise, return -1.
87 static ssize_t ReadFromOffset(const int fd, void *buf,
88                               const size_t count, const off_t offset) {
89   off_t off = lseek(fd, offset, SEEK_SET);
90   if (off == (off_t)-1) {
91     return -1;
92   }
93   return ReadPersistent(fd, buf, count);
94 }
95
96 // Try reading exactly "count" bytes from "offset" bytes in a file
97 // pointed by "fd" into the buffer starting at "buf" while handling
98 // short reads and EINTR.  On success, return true. Otherwise, return
99 // false.
100 static bool ReadFromOffsetExact(const int fd, void *buf,
101                                 const size_t count, const off_t offset) {
102   ssize_t len = ReadFromOffset(fd, buf, count, offset);
103   return len == count;
104 }
105
106 // Returns elf_header.e_type if the file pointed by fd is an ELF binary.
107 static int FileGetElfType(const int fd) {
108   ElfW(Ehdr) elf_header;
109   if (!ReadFromOffsetExact(fd, &elf_header, sizeof(elf_header), 0)) {
110     return -1;
111   }
112   if (memcmp(elf_header.e_ident, ELFMAG, SELFMAG) != 0) {
113     return -1;
114   }
115   return elf_header.e_type;
116 }
117
118 // Read the section headers in the given ELF binary, and if a section
119 // of the specified type is found, set the output to this section header
120 // and return true.  Otherwise, return false.
121 // To keep stack consumption low, we would like this function to not get
122 // inlined.
123 static ATTRIBUTE_NOINLINE bool
124 GetSectionHeaderByType(const int fd, ElfW(Half) sh_num, const off_t sh_offset,
125                        ElfW(Word) type, ElfW(Shdr) *out) {
126   // Read at most 16 section headers at a time to save read calls.
127   ElfW(Shdr) buf[16];
128   for (int i = 0; i < sh_num;) {
129     const ssize_t num_bytes_left = (sh_num - i) * sizeof(buf[0]);
130     const ssize_t num_bytes_to_read =
131         (sizeof(buf) > num_bytes_left) ? num_bytes_left : sizeof(buf);
132     const ssize_t len = ReadFromOffset(fd, buf, num_bytes_to_read,
133                                        sh_offset + i * sizeof(buf[0]));
134     SAFE_ASSERT(len % sizeof(buf[0]) == 0);
135     const ssize_t num_headers_in_buf = len / sizeof(buf[0]);
136     SAFE_ASSERT(num_headers_in_buf <= sizeof(buf) / sizeof(buf[0]));
137     for (int j = 0; j < num_headers_in_buf; ++j) {
138       if (buf[j].sh_type == type) {
139         *out = buf[j];
140         return true;
141       }
142     }
143     i += num_headers_in_buf;
144   }
145   return false;
146 }
147
148 // There is no particular reason to limit section name to 63 characters,
149 // but there has (as yet) been no need for anything longer either.
150 const int kMaxSectionNameLen = 64;
151
152 // name_len should include terminating '\0'.
153 bool GetSectionHeaderByName(int fd, const char *name, size_t name_len,
154                             ElfW(Shdr) *out) {
155   ElfW(Ehdr) elf_header;
156   if (!ReadFromOffsetExact(fd, &elf_header, sizeof(elf_header), 0)) {
157     return false;
158   }
159
160   ElfW(Shdr) shstrtab;
161   off_t shstrtab_offset = (elf_header.e_shoff +
162                            elf_header.e_shentsize * elf_header.e_shstrndx);
163   if (!ReadFromOffsetExact(fd, &shstrtab, sizeof(shstrtab), shstrtab_offset)) {
164     return false;
165   }
166
167   for (int i = 0; i < elf_header.e_shnum; ++i) {
168     off_t section_header_offset = (elf_header.e_shoff +
169                                    elf_header.e_shentsize * i);
170     if (!ReadFromOffsetExact(fd, out, sizeof(*out), section_header_offset)) {
171       return false;
172     }
173     char header_name[kMaxSectionNameLen];
174     if (sizeof(header_name) < name_len) {
175       RAW_LOG(WARNING, "Section name '%s' is too long (%"PRIuS"); "
176               "section will not be found (even if present).", name, name_len);
177       // No point in even trying.
178       return false;
179     }
180     off_t name_offset = shstrtab.sh_offset + out->sh_name;
181     ssize_t n_read = ReadFromOffset(fd, &header_name, name_len, name_offset);
182     if (n_read == -1) {
183       return false;
184     } else if (n_read != name_len) {
185       // Short read -- name could be at end of file.
186       continue;
187     }
188     if (memcmp(header_name, name, name_len) == 0) {
189       return true;
190     }
191   }
192   return false;
193 }
194
195 // Read a symbol table and look for the symbol containing the
196 // pc. Iterate over symbols in a symbol table and look for the symbol
197 // containing "pc".  On success, return true and write the symbol name
198 // to out.  Otherwise, return false.
199 // To keep stack consumption low, we would like this function to not get
200 // inlined.
201 static ATTRIBUTE_NOINLINE bool
202 FindSymbol(uint64_t pc, const int fd, char *out, int out_size,
203            uint64_t symbol_offset, const ElfW(Shdr) *strtab,
204            const ElfW(Shdr) *symtab) {
205   if (symtab == NULL) {
206     return false;
207   }
208   const int num_symbols = symtab->sh_size / symtab->sh_entsize;
209   for (int i = 0; i < num_symbols;) {
210     off_t offset = symtab->sh_offset + i * symtab->sh_entsize;
211
212     // If we are reading Elf64_Sym's, we want to limit this array to
213     // 32 elements (to keep stack consumption low), otherwise we can
214     // have a 64 element Elf32_Sym array.
215 #if __WORDSIZE == 64
216 #define NUM_SYMBOLS 32
217 #else
218 #define NUM_SYMBOLS 64
219 #endif
220
221     // Read at most NUM_SYMBOLS symbols at once to save read() calls.
222     ElfW(Sym) buf[NUM_SYMBOLS];
223     const ssize_t len = ReadFromOffset(fd, &buf, sizeof(buf), offset);
224     SAFE_ASSERT(len % sizeof(buf[0]) == 0);
225     const ssize_t num_symbols_in_buf = len / sizeof(buf[0]);
226     SAFE_ASSERT(num_symbols_in_buf <= sizeof(buf)/sizeof(buf[0]));
227     for (int j = 0; j < num_symbols_in_buf; ++j) {
228       const ElfW(Sym)& symbol = buf[j];
229       uint64_t start_address = symbol.st_value;
230       start_address += symbol_offset;
231       uint64_t end_address = start_address + symbol.st_size;
232       if (symbol.st_value != 0 &&  // Skip null value symbols.
233           symbol.st_shndx != 0 &&  // Skip undefined symbols.
234           start_address <= pc && pc < end_address) {
235         ssize_t len1 = ReadFromOffset(fd, out, out_size,
236                                       strtab->sh_offset + symbol.st_name);
237         if (len1 <= 0 || memchr(out, '\0', out_size) == NULL) {
238           return false;
239         }
240         return true;  // Obtained the symbol name.
241       }
242     }
243     i += num_symbols_in_buf;
244   }
245   return false;
246 }
247
248 // Get the symbol name of "pc" from the file pointed by "fd".  Process
249 // both regular and dynamic symbol tables if necessary.  On success,
250 // write the symbol name to "out" and return true.  Otherwise, return
251 // false.
252 static bool GetSymbolFromObjectFile(const int fd, uint64_t pc,
253                                     char *out, int out_size,
254                                     uint64_t map_start_address) {
255   // Read the ELF header.
256   ElfW(Ehdr) elf_header;
257   if (!ReadFromOffsetExact(fd, &elf_header, sizeof(elf_header), 0)) {
258     return false;
259   }
260
261   uint64_t symbol_offset = 0;
262   if (elf_header.e_type == ET_DYN) {  // DSO needs offset adjustment.
263     symbol_offset = map_start_address;
264   }
265
266   ElfW(Shdr) symtab, strtab;
267
268   // Consult a regular symbol table first.
269   if (!GetSectionHeaderByType(fd, elf_header.e_shnum, elf_header.e_shoff,
270                               SHT_SYMTAB, &symtab)) {
271     return false;
272   }
273   if (!ReadFromOffsetExact(fd, &strtab, sizeof(strtab), elf_header.e_shoff +
274                            symtab.sh_link * sizeof(symtab))) {
275     return false;
276   }
277   if (FindSymbol(pc, fd, out, out_size, symbol_offset,
278                  &strtab, &symtab)) {
279     return true;  // Found the symbol in a regular symbol table.
280   }
281
282   // If the symbol is not found, then consult a dynamic symbol table.
283   if (!GetSectionHeaderByType(fd, elf_header.e_shnum, elf_header.e_shoff,
284                               SHT_DYNSYM, &symtab)) {
285     return false;
286   }
287   if (!ReadFromOffsetExact(fd, &strtab, sizeof(strtab), elf_header.e_shoff +
288                            symtab.sh_link * sizeof(symtab))) {
289     return false;
290   }
291   if (FindSymbol(pc, fd, out, out_size, symbol_offset,
292                  &strtab, &symtab)) {
293     return true;  // Found the symbol in a dynamic symbol table.
294   }
295
296   return false;
297 }
298
299 namespace {
300 // Thin wrapper around a file descriptor so that the file descriptor
301 // gets closed for sure.
302 struct FileDescriptor {
303   const int fd_;
304   explicit FileDescriptor(int fd) : fd_(fd) {}
305   ~FileDescriptor() {
306     if (fd_ >= 0) {
307       NO_INTR(close(fd_));
308     }
309   }
310   int get() { return fd_; }
311
312  private:
313   explicit FileDescriptor(const FileDescriptor&);
314   void operator=(const FileDescriptor&);
315 };
316
317 // Helper class for reading lines from file.
318 //
319 // Note: we don't use ProcMapsIterator since the object is big (it has
320 // a 5k array member) and uses async-unsafe functions such as sscanf()
321 // and snprintf().
322 class LineReader {
323  public:
324   explicit LineReader(int fd, char *buf, int buf_len) : fd_(fd),
325     buf_(buf), buf_len_(buf_len), bol_(buf), eol_(buf), eod_(buf) {
326   }
327
328   // Read '\n'-terminated line from file.  On success, modify "bol"
329   // and "eol", then return true.  Otherwise, return false.
330   //
331   // Note: if the last line doesn't end with '\n', the line will be
332   // dropped.  It's an intentional behavior to make the code simple.
333   bool ReadLine(const char **bol, const char **eol) {
334     if (BufferIsEmpty()) {  // First time.
335       const ssize_t num_bytes = ReadPersistent(fd_, buf_, buf_len_);
336       if (num_bytes <= 0) {  // EOF or error.
337         return false;
338       }
339       eod_ = buf_ + num_bytes;
340       bol_ = buf_;
341     } else {
342       bol_ = eol_ + 1;  // Advance to the next line in the buffer.
343       SAFE_ASSERT(bol_ <= eod_);  // "bol_" can point to "eod_".
344       if (!HasCompleteLine()) {
345         const int incomplete_line_length = eod_ - bol_;
346         // Move the trailing incomplete line to the beginning.
347         memmove(buf_, bol_, incomplete_line_length);
348         // Read text from file and append it.
349         char * const append_pos = buf_ + incomplete_line_length;
350         const int capacity_left = buf_len_ - incomplete_line_length;
351         const ssize_t num_bytes = ReadPersistent(fd_, append_pos,
352                                                  capacity_left);
353         if (num_bytes <= 0) {  // EOF or error.
354           return false;
355         }
356         eod_ = append_pos + num_bytes;
357         bol_ = buf_;
358       }
359     }
360     eol_ = FindLineFeed();
361     if (eol_ == NULL) {  // '\n' not found.  Malformed line.
362       return false;
363     }
364     *eol_ = '\0';  // Replace '\n' with '\0'.
365
366     *bol = bol_;
367     *eol = eol_;
368     return true;
369   }
370
371   // Beginning of line.
372   const char *bol() {
373     return bol_;
374   }
375
376   // End of line.
377   const char *eol() {
378     return eol_;
379   }
380
381  private:
382   explicit LineReader(const LineReader&);
383   void operator=(const LineReader&);
384
385   char *FindLineFeed() {
386     return reinterpret_cast<char *>
387       (memchr(reinterpret_cast<const void *>(bol_), '\n', eod_ - bol_));
388   }
389
390   bool BufferIsEmpty() {
391     return buf_ == eod_;
392   }
393
394   bool HasCompleteLine() {
395     return !BufferIsEmpty() && FindLineFeed() != NULL;
396   }
397
398   const int fd_;
399   char * const buf_;
400   const int buf_len_;
401   const char *bol_;
402   char *eol_;
403   const char *eod_;  // End of data in "buf_".
404 };
405 }  // namespace
406
407 // Place the hex number read from "start" into "*hex".  The pointer to
408 // the first non-hex character or "end" is returned.
409 static char *GetHex(const char *start, const char *end, uint64_t *hex) {
410   *hex = 0;
411   const char *p;
412   for (p = start; p < end; ++p) {
413     int ch = *p;
414     if ((ch >= '0' && ch <= '9') ||
415         (ch >= 'A' && ch <= 'F') || (ch >= 'a' && ch <= 'f')) {
416       *hex = (*hex << 4) | (ch < 'A' ? ch - '0' : (ch & 0xF) + 9);
417     } else {  // Encountered the first non-hex character.
418       break;
419     }
420   }
421   SAFE_ASSERT(p <= end);
422   return const_cast<char *>(p);
423 }
424
425 // Search for the object file (from /proc/self/maps) that contains
426 // the specified pc. If found, open this file and return the file handle,
427 // and also set start_address to the start address of where this object
428 // file is mapped to in memory. Otherwise, return -1.
429 static ATTRIBUTE_NOINLINE int
430 OpenObjectFileContainingPcAndGetStartAddress(uint64_t pc,
431                                              uint64_t &start_address) {
432   int object_fd;
433
434   // Open /proc/self/maps.
435   int maps_fd;
436   NO_INTR(maps_fd = open("/proc/self/maps", O_RDONLY));
437   FileDescriptor wrapped_maps_fd(maps_fd);
438   if (wrapped_maps_fd.get() < 0) {
439     return -1;
440   }
441
442   // Iterate over maps and look for the map containing the pc.  Then
443   // look into the symbol tables inside.
444   char buf[1024];  // Big enough for line of sane /proc/self/maps
445   LineReader reader(wrapped_maps_fd.get(), buf, sizeof(buf));
446   while (true) {
447     const char *cursor;
448     const char *eol;
449     if (!reader.ReadLine(&cursor, &eol)) {  // EOF or malformed line.
450       return -1;
451     }
452
453     // Start parsing line in /proc/self/maps.  Here is an example:
454     //
455     // 08048000-0804c000 r-xp 00000000 08:01 2142121    /bin/cat
456     //
457     // We want start address (08048000), end address (0804c000), flags
458     // (r-xp) and file name (/bin/cat).
459
460     // Read start address.
461     cursor = GetHex(cursor, eol, &start_address);
462     if (cursor == eol || *cursor != '-') {
463       return -1;  // Malformed line.
464     }
465     ++cursor;  // Skip '-'.
466
467     // Read end address.
468     uint64_t end_address;
469     cursor = GetHex(cursor, eol, &end_address);
470     if (cursor == eol || *cursor != ' ') {
471       return -1;  // Malformed line.
472     }
473     ++cursor;  // Skip ' '.
474
475     // Check start and end addresses.
476     if (!(start_address <= pc && pc < end_address)) {
477       continue;  // We skip this map.  PC isn't in this map.
478     }
479
480     // Read flags.  Skip flags until we encounter a space or eol.
481     const char * const flags_start = cursor;
482     while (cursor < eol && *cursor != ' ') {
483       ++cursor;
484     }
485     // We expect at least four letters for flags (ex. "r-xp").
486     if (cursor == eol || cursor < flags_start + 4) {
487       return -1;  // Malformed line.
488     }
489
490     // Check flags.  We are only interested in "r-x" maps.
491     if (memcmp(flags_start, "r-x", 3) != 0) {  // Not a "r-x" map.
492       continue;  // We skip this map.
493     }
494     ++cursor;  // Skip ' '.
495
496     // Skip to file name.  "cursor" now points to file offset.  We need to
497     // skip at least three spaces for file offset, dev, and inode.
498     int num_spaces = 0;
499     while (cursor < eol) {
500       if (*cursor == ' ') {
501         ++num_spaces;
502       } else if (num_spaces >= 3) {
503         // The first non-space character after  skipping three spaces
504         // is the beginning of the file name.
505         break;
506       }
507       ++cursor;
508     }
509     if (cursor == eol) {
510       return -1;  // Malformed line.
511     }
512
513     // Finally, "cursor" now points to file name of our interest.
514     NO_INTR(object_fd = open(cursor, O_RDONLY));
515     if (object_fd < 0) {
516       return -1;
517     }
518     return object_fd;
519   }
520 }
521
522
523 SymbolizeCallback g_symbolize_callback = NULL;
524 void InstallSymbolizeCallback(SymbolizeCallback callback) {
525   g_symbolize_callback = callback;
526 }
527
528 // This function wraps the Demangle function to provide an interface
529 // where the input symbol is demangled in-place.
530 // To keep stack consumption low, we would like this function to not
531 // get inlined.
532 static ATTRIBUTE_NOINLINE void DemangleInplace(char *out, int out_size) {
533   char demangled[256];  // Big enough for sane demangled symbols.
534   if (Demangle(out, demangled, sizeof(demangled))) {
535     // Demangling succeeded. Copy to out if the space allows.
536     int len = strlen(demangled);
537     if (len + 1 <= out_size) {  // +1 for '\0'.
538       SAFE_ASSERT(len < sizeof(demangled));
539       memmove(out, demangled, len + 1);
540     }
541   }
542 }
543
544 // The implementation of our symbolization routine.  If it
545 // successfully finds the symbol containing "pc" and obtains the
546 // symbol name, returns true and write the symbol name to "out".
547 // Otherwise, returns false. If Callback function is installed via
548 // InstallSymbolizeCallback(), the function is also called in this function,
549 // and "out" is used as its output.
550 // To keep stack consumption low, we would like this function to not
551 // get inlined.
552 static ATTRIBUTE_NOINLINE bool SymbolizeAndDemangle(void *pc, char *out,
553                                                     int out_size) {
554   uint64_t pc0 = reinterpret_cast<uintptr_t>(pc);
555   uint64_t start_address = 0;
556
557   int object_fd = OpenObjectFileContainingPcAndGetStartAddress(pc0,
558                                                                start_address);
559   if (object_fd == -1) {
560     return false;
561   }
562   FileDescriptor wrapped_object_fd(object_fd);
563   int elf_type = FileGetElfType(wrapped_object_fd.get());
564   if (elf_type == -1) {
565     return false;
566   }
567   if (g_symbolize_callback) {
568     // Run the call back if it's installed.
569     // Note: relocation (and much of the rest of this code) will be
570     // wrong for prelinked shared libraries and PIE executables.
571     uint64 relocation = (elf_type == ET_DYN) ? start_address : 0;
572     int num_bytes_written = g_symbolize_callback(wrapped_object_fd.get(),
573                                                  pc, out, out_size,
574                                                  relocation);
575     if (num_bytes_written > 0) {
576       out += num_bytes_written;
577       out_size -= num_bytes_written;
578     }
579   }
580   if (!GetSymbolFromObjectFile(wrapped_object_fd.get(), pc0,
581                                out, out_size, start_address)) {
582     return false;
583   }
584   // Symbolization succeeded.  Now we try to demangle the symbol.
585   DemangleInplace(out, out_size);
586   return true;
587 }
588
589 bool Symbolize(void *pc, char *out, int out_size) {
590   SAFE_ASSERT(out_size >= 0);
591   return SymbolizeAndDemangle(pc, out, out_size);
592 }
593
594 _END_GOOGLE_NAMESPACE_
595
596 #else  /* __ELF__ */
597
598 #include <assert.h>
599
600 #include "config.h"
601
602 _START_GOOGLE_NAMESPACE_
603
604 // TODO: osx-port-incomplete.  An alternative is Brakepad, but I don't
605 // think we want that mixed up in google3.
606 bool Symbolize(void *pc, char *out, int out_size) {
607   assert(0);
608   return false;
609 }
610
611 _END_GOOGLE_NAMESPACE_
612
613 #endif