Monday, November 7, 2011

Self-modifying code for debug tracing in quasi-C

Printing a program's state as it runs is the simple but effective debugging tool of programmers everywhere. For efficiency, we usually disable the most verbose output in production. But sometimes you need to diagnose a problem in a deployed system. It would be convenient to declare "tracepoints" and enable them at runtime, like so:

tracepoint foo_entry;

int foo(int n) {
TRACE(foo_entry, "called foo(%d)\n", n);
// ...
}

// Called from UI, monitoring interface, etc.
void debug_foo() {
enable(&foo_entry);
}

Here's a simple implementation of this API:

typedef int tracepoint;

#define TRACE(_point, _args...) \ do { \ if (_point) printf(_args); \ } while (0)

static inline void enable(tracepoint *point) {
*point = 1;
}

Each tracepoint is simply a global variable. The construct do { ... } while (0) is a standard trick to make macro-expanded code play nicely with its surroundings. We also use GCC's syntax for macros with a variable number of arguments.

This approach does introduce a bit of overhead. One concern is that reading a global variable will cause a cache miss and will also evict a line of useful data from the cache. There's also some impact from adding a branch instruction. We'll develop a significantly more complicated implementation which avoids both of these problems.

Our new solution will be specific to x86-64 processors running Linux, though the idea can be ported to other platforms. This approach is inspired by various self-modifying-code schemes in the Linux kernel, such as ftrace, kprobes, immediate values, etc. It's mostly intended as an example of how these tricks work. The code in this article is not production-ready.

The design

Our new TRACE macro will produce code like the following pseudo-assembly:

foo:
...
; code before tracepoint
...
tracepoint:
nop
after_tracepoint:
...
; rest of function
...
ret

do_tracepoint:
push args to printf
call printf
jmp after_tracepoint

In the common case, the tracepoint is disabled, and the overhead is only a single nop instruction. To enable the tracepoint, we replace the nop instruction in memory with jmp do_tracepoint.

The TRACE macro

Our nop instruction needs to be big enough that we can overwrite it with an unconditional jump. On x86-64, the standard jmp instruction has a 1-byte opcode and a 4-byte signed relative displacement, so we need a 5-byte nop. Five one-byte 0x90 instructions would work, but a single five-byte instruction will consume fewer CPU resources. Finding the best way to do nothing is actually rather difficult, but the Linux kernel has already compiled a list of favorite nops. We'll use this one:

#define NOP5 ".byte 0x0f, 0x1f, 0x44, 0x00, 0x00;"

Let's check this instruction using udcli:

$ echo 0f 1f 44 00 00 | udcli -x -64 -att
0000000000000000 0f1f440000       nop 0x0(%rax,%rax)

GCC's extended inline assembly lets us insert arbitrarily bizarre assembly code into a normal C program. We'll use the asm goto flavor, new in GCC 4.5, so that we can pass C labels into our assembly code. (The tracing use case inspired the asm goto feature, and my macro is adapted from an example in the GCC manual.)

Here's how it looks:

typedef int tracepoint;

#define TRACE(_point, _args...) \ do { \ asm goto ( \ "0: " NOP5 \ ".pushsection trace_table, \"a\";" \ ".quad " #_point ", 0b, %l0;" \ ".popsection" \ : : : : __lbl_##_point); \ if (0) { \ __lbl_##_point: printf(_args); \ } \ } while (0)

We use the stringify and concat macro operators, and rely on the gluing together of adjacent string literals. A call like this:

TRACE(foo_entry, "called foo(%d)\n", n);

will produce the following code:

  do {
asm goto (
"0: .byte 0x0f, 0x1f, 0x44, 0x00, 0x00;"
".pushsection trace_table, \"a\";"
".quad foo_entry, 0b, %l0;"
".popsection"
: : : : __lbl_foo_entry);
if (0) {
__lbl_foo_entry: printf("called foo(%d)\n", n);
}
} while (0);

Besides emitting the nop instruction, we write three 64-bit values ("quads"). They are, in order:

  • The address of the tracepoint variable declared by the user. We never actually read or write this variable. We're just using its address as a unique key.
  • The address of the nop instruction, by way of a local assembler label.
  • The address of the C label for our printf call, as passed to asm goto.

This is the information we need in order to patch in a jmp at runtime. The .pushsection directive makes the assembler write into the trace_table section without disrupting the normal flow of code and data. The "a" section flag marks these bytes as "allocatable", i.e. something we actually want available at runtime.

We count on GCC's optimizer to notice that the condition 0 is unlikely to be true, and therefore move the if body to the end of the function. It's still considered reachable due to the label passed to asm goto, so it will not fall victim to dead code elimination.

The linker script

We have to collect all of these trace_table records, possibly from multiple source files, and put them somewhere for use by our C code. We'll do this with the following linker script:

SECTIONS {
  trace_table : {
    trace_table_start = .;
    *(trace_table)
    trace_table_end = .;
  }
}

This concatenates all trace_table sections into a single section in the resulting binary. It also provides symbols trace_table_start and trace_table_end at the endpoints of this section.

Memory protection

Linux systems will prevent an application from overwriting its own code, for good security reasons, but we can explicitly override these permissions. Memory permissions are managed per page of memory. There's a correct way to determine the size of a page, but our code is terribly x86-specific anyway, so we'll hardcode the page size of 4096 bytes.

#define PAGE_SIZE 4096
#define PAGE_OF(_addr) ( ((uint64_t) (_addr)) & ~(PAGE_SIZE-1) )

Then we can unprotect an arbitrary region of memory by calling mprotect for the appropriate page(s):

static void unprotect(void *addr, size_t len) {
uint64_t pg1 = PAGE_OF(addr),
pg2 = PAGE_OF(addr + len - 1);
if (mprotect((void *) pg1, pg2 - pg1 + PAGE_SIZE,
PROT_READ | PROT_EXEC | PROT_WRITE)) {
perror("mprotect");
abort();
}
}

We're calling mprotect on a page which was not obtained from mmap. POSIX does not define this behavior, but Linux specifically allows mprotect on any page except the vsyscall page.

Enabling a tracepoint

Now we need to implement the enable function:

void enable(tracepoint *point);

We will scan through the trace_table records looking for a matching tracepoint pointer. The C struct corresponding to a trace_table record is:

struct trace_desc {
tracepoint *point;
void *jump_from;
void *jump_to;
} __attribute__((packed));

The packed attribute tells GCC not to insert any padding within or after these structs. This ensures that their layout will match the records we produced from assembly. Now we can implement a linear search through this table.

void enable(tracepoint *point) {
extern struct trace_desc trace_table_start[], trace_table_end[];
struct trace_desc *desc;
for (desc = trace_table_start; desc < trace_table_end; desc++) {
if (desc->point != point)
continue;

int64_t offset = (desc->jump_to - desc->jump_from) - 5;
if ((offset > INT32_MAX) || (offset < INT32_MIN)) {
fprintf(stderr, "offset too big: %lx\n", offset);
abort();
}

int32_t offset32 = offset;
unsigned char *dest = desc->jump_from;
unprotect(dest, 5);
dest[0] = 0xe9;
memcpy(dest+1, &offset32, 4);
}
}

We enable a tracepoint by overwriting its nop with an unconditional jump. The opcode is 0xe9. The operand is a 32-bit displacement, interpreted relative to the instruction after the jump. desc->jump_from points to the beginning of what will be the jump instruction, so we subtract 5 from the displacement. Then we unprotect memory and write the new bytes into place.

That's everything. You can grab all of this code from GitHub, including a simple test program.

Pitfalls

Where to start?

This code is extremely non-portable, relying on details of x86-64, Linux, and specific recent versions of the GNU C compiler and assembler. The idea can be ported to other platforms, with some care. For example, ARM processors require an instruction cache flush after writing to code. Linux on ARM implements the cacheflush system call for this purpose.

Our code is not thread-safe, either. If one thread reaches a nop while it is being overwritten by another thread, the result will surely be a crash or other horrible bug. The Ksplice paper [PDF] discusses how to prevent this, in the context of live-patching the Linux kernel.

Is it worth opening this can of worms in order to improve performance a little? In general, no. Obviously we'd have to measure the performance difference to be sure. But for most projects, concerns of maintainability and avoiding bugs will preclude tricky hacks like this one.

The Linux kernel is under extreme demands for both performance and flexibility. It's part of every application on a huge number of systems, so any small performance improvement has a large aggregate effect. And those systems are incredibly diverse, making it likely that someone will see a large difference. Finally, kernel development will always involve tricky low-level code as a matter of course. The infrastructure is already there to support it — both software infrastructure and knowledgeable developers.

86 comments:

  1. How does this compare to DTrace/SystemTap static probes (USDTs)?

    ReplyDelete
  2. Nathan, quite different.

    Both dtrace and systemtap (currently) evaluate tracing commands in kernel space, so that part is not compiled into the application, and instead a breakpoint instruction ends up being patched into the process virtual image. Systemtap and dtrace sdt.h implementations are different too, so dormant and active tracepoint overheads differ. Clever tricks abound in each.

    LTTng's UST is closer to the technique outlined in this post.

    ReplyDelete
  3. Somewhat related for x86: http://blogs.msdn.com/b/oldnewthing/archive/2011/09/21/10214405.aspx

    Raymond seems to imply that there aren't any threading issues with that solution, but that may be due to the 2-byte nop fitting into an interlocked swap.

    ReplyDelete
  4. Sharkey: That solution avoids the threading issue because it overwrites a two-byte NOP with a two-byte JMP instruction, which can be done as a single two-byte store: any parallel thread will see either the NOP or the JMP. With the solution above, however, five bytes must be overwritten, which cannot be done as an atomic store.

    However, since the above technique is x86-64 specific, it could just use a NOP8 instead of a NOP5, which can be overwritten in a single store. This would make it safe.

    ReplyDelete
  5. caf: My x86-64 is rusty, but are the 2-byte relative jump instructions no longer valid? I was under the impression that x86-64 is an almost-superset of x86, but I'm too lazy to crack open Windbg to find out...

    What's more, if a synchronous write of 8 bytes is thread-safe, the above code could work with a little more effort. When dropping in the jump over the nop via an 8-byte interlocked store, you would have to rewrite the 3 bytes of the following instruction as well.

    ReplyDelete
  6. Sharkey: The 0xEB JMP rel8 instruction is still valid in 64-Bit mode, but using that requires jumping to the trampoline containing the full 5-byte jump. This is required on x86 (at least older models that don't have any way of doing an atomic store larger than 4 bytes), but is suboptimal on x86-64.

    You're right that you could do a read-modify-write with the NOP5 implementation.

    ReplyDelete
  7. Nicely explained, and the many links off to details on side issues are welcome. enable()'s for-loop could do with a break at the end to stop searching once a match has been found.

    ReplyDelete
  8. For a primitive tracing facility, you can also probably use -finstrument-functions. Then have a shared object that can track the function call chain by providing __cyg_profile_func_enter() and __cyg_profile_func_exit().

    ReplyDelete
  9. I read your post. It is very informative and helpful to me. I admire the message  valuable information you provided in your article. Thank you for posting, again!

    ReplyDelete
  10. Thank you for the information of this code!

    ReplyDelete
  11. Bandicut Torrent
    Cracked Here is a useful place where you can easily find Activators, Patch, Full version software Free Download, License key, serial key, keygen, Activation Key and Torrents. Get all of these by easily just on a single click.

    ReplyDelete
  12. WPS Office Premium Crack 2021
    WPS Office Premium Cracked Here is a useful place where you can easily find Activators, Patch, Full version software Free Download, License key, serial key, keygen, Activation Key and Torrents. Get all of these by easily just on a single click.

    ReplyDelete
  13. Suggest good information in this message, click here.
    glathhouses.com
    banknegar

    ReplyDelete
  14. https://crackedversion.com/wondershare-dr-fone-crack-full-download/
    Wondershare Dr.Fone Crack is one of the amazing software used to the data. Dr. fone is launched and developed by wonder-share. You can recover any type of your lost data that is lost by any kind of source. Also, Dr help to the recovery of the data from your mobile and Io’s phone. Furthermore, This phone also gives you a lot of features for data recovery. This becomes the top list application for the data recovery software in the market.

    ReplyDelete
  15. Your source for fun, free mobile and PC download games. Thousands of free ... Download or play free online! ... Here is the Exact Arcade Version of Dig Dug!
    wildermyth torrent

    ReplyDelete
  16. Good job. Its very excellent blog. I like it.This site have different software articles which appears to be a useful and valuable for you individual, proficient software installation. This is where you can get helps for any software installation, usage and cracked.
    Crackios.com

    ReplyDelete
  17. Moreover to the beyond, tick the zooming key which is joined to explain any point fully. One extra item of this software is to give the opportunity of real streaming. That you will stream along by leading media places. That includes sites like YouTube, Dailymotion, etc.
    https://crackgift.com/vmix-pro-crack/

    ReplyDelete
  18. Nero Burning ROM Crack Download is the most powerful optical disk creation and recording software in the world for creating high-quality CD, DVD, and Blu-ray discs.neroburningrom

    ReplyDelete
  19. All versions of Cubase Elements Crack Free Download have the same clear sound quality and ease of use that makes Cubase Free one of the most popular recording and production solutions in the world. cubaseelementsregistrationkey

    ReplyDelete
  20. Klevgrand Pipa Crack Download is a synth song with a unique and different sound. Inspired by the expression and flexibility of the human voice, it is not intended to cover all aspects of the real voice.klevgrandpipa

    ReplyDelete
  21. Corel VideoStudio Ultimate License Key Crack has a professional video editing environment and a lot of powerful tools. corelvideostudioserialkey

    ReplyDelete
  22. Kaspersky Antivirus Crack provides the necessary protection to help protect your computer against the latest viruses, solvents, and more.kasperskyantivirus

    ReplyDelete
  23. PassMark Performance Test crack
    PassMark Performance Crack gives you the best result and compared to the other computers. serial key use to test a benchmark a system. If you have any problem with your hardware or any type of hidden system

    ReplyDelete
  24. Omnisphere crack
    With the help of this app, you can write songs with suitable lyrics. And then you can compose them after the composing of the songs.

    ReplyDelete
  25. iCare Data Recovery Pro crack
    this app can recover your lost data. This will help you to backup your mistakenly deleted data. Moreover, this software also can regain those files that were removed from the recycle bin

    ReplyDelete
  26. Deezer APK Premium crack
    this app helps the users enjoy various sorts of high quality and they even don’t have to subscribe to it. Moreover, this app comes with almost fifty-six millions of the titles and a great amount of the Spotify and Tide

    ReplyDelete
  27. Xfer Serum crack
    this tool provides for the clean and bright, bold, and detailed sound effects from there. In addition, this tool is a wide wavetable that is present for it.

    ReplyDelete
  28. I really enjoy reading your post about this Posting. This sort of clever work and coverage! Keep up the wonderful works guys, thanks for sharing
    mailbird-pro-crack

    ReplyDelete

  29. JRiver Media Center Crack
    JRiver Media Center License Key is an application for a multimedia system player. With the use of Player, prepare various types of media on one computer.

    ReplyDelete
  30. I guess I am the only one who came here to share my very own experience. Guess what!? I am using my laptop for almost the past 2 years, but I had no idea of solving some basic issues. I do not know how to Getsoftwares.org and IDM Crack software or any other basic crack version. I always really on others to solve my basic issues. But thankfully, I recently visited a website named Azharpc.org

    Wondershare Filmora Crack
    WPS Office Premium Crack
    WPS Office Crack
    TweakBit Driver Updater Crack
    Wondershare Filmora Crack

    ReplyDelete
  31. I am a regular visitor, and this post posted on this web page is truly pleasant.
    LooserCrack

    ReplyDelete
  32. DeskSoft SmartCapture Crack is the professional and easy-to-use screen capture tool for Windows. But the clean, intuitive user interface and powerful features make it the ideal utility for anyone who wants to capture content on the Windows desktop. You can capture rectangular areas of the screen, entire objects, windows or screens, and capture images from imaging devices (for example, scanners, digital cameras, etc.). DeskSoft SmartCapture Serial Number Users sometimes use the PrintScreen keyboard to create an image from a specific application or document. You can download from this link https://crackclick.com/desksoft-smartcapture-crack/

    ReplyDelete

  33. Altium Designer Crack
    Altium Designer Crack Download offers you the latest technology and new guides to focus on your process and design. Despite his busy schedule, he still manages to impress those around him with his creativity.

    ReplyDelete
  34. Reimage PC Repair 2021 Crack
    Please note that we will not sell your information to anyone. You can contact our technical support team 24/7 by email for assistance in completing repairs.

    ReplyDelete
  35. Thanks for Nice and Informative Post. This article is really contains lot more information about This Topic eset-nod32-antivirus-license-key

    ReplyDelete
  36. ArcGIS Pro Crack
    This application is also user-friendly since it includes ArcMap, ArcCatalog, and ArcGIS pro.

    ReplyDelete
  37. Goood Working...Thanks for shairng keep it up!
    cubase-pro-crack

    ReplyDelete
  38. but you can have this game also here in just with single click only.download assassins creed 1 for pc free full version highly compressed enjoy And if you want to play the
    Are you searching for a good and high quality you are on the right place now because i will guide you through a very high quality website which is perfect for

    ReplyDelete
  39. Great Job Amazing content and blog Thanks For this nice content
    apoweredit-crack-download

    ReplyDelete
  40. https://keyhax.com/wp-admin/post.php?post=951&action=edit

    ReplyDelete
  41. https://getintocrack.com/wp-admin/post.php?post=2314&action=edit

    ReplyDelete
  42. https://hirapc.com/wp-admin/post.php?post=810&action=edit

    https://hirapc.com/

    ReplyDelete
  43. I guess I am the only one who came here to share my very own experience. Guess what!? I am using my laptop for almost the past 2 years, but I had no idea of solving some basic issues. I do not know how to Download Cracked Pro Softwares But thankfully, I recently visited a website named wahabtech.net
    JRiver Media Center Crack

    ReplyDelete
  44. Thanks for sharing your knowledge to install & crack the Time Tables, but you need to update
    it now. because there is a 2022 version available now.


    Thanks for sharing

    ReplyDelete
  45. Hello it’s me, I am also visiting this site on a regular basis, this web page is truly nice and the people are actually sharing fastidious thoughts.


    Thanks for sharing

    ReplyDelete
  46. สาระน่ารู้เกี่ยวกับเกม เกมออนไลน์ เกมออฟไลน์ เกมยอดนิยม ข่าวสารวงการไอที และกีฬาประเภทต่าง ๆ ที่ดีต่อสุขภาพ คลิก hisuperautocar รวบรวมเกมน่าเล่น อัพเดทใหม่ล่าสุด 2022 ที่เหล่าเกมเมอร์ไม่ควรพลาดด้วยประการทั้งปวง !!

    ReplyDelete
  47. Download Software for PC & Mac
    You make it look very easy with your presentation, but I think this is important to Be something that I think I would never understand
    It seems very complex and extremely broad to me. I look forward to your next post,
    CCleaner Pro Crack
    Nero Platinum Crack
    WYSIWYG Web Builder Crack
    JRiver Media Center Crack
    PDF24 Creator Crack
    Doodly Crack
    4k Video Downloader Crack

    ReplyDelete
  48. You’ve written nice post, I am gonna bookmark this page, thanks for info. I actually appreciate your own position and I will be sure to come back here. Feel free to visit my website; 야설

    ReplyDelete
  49. I am glad to search out so many useful information here in the post, thank you for sharing. Feel free to visit my website;
    한국야동


    ReplyDelete
  50. I am really happy with articles quality and presentation. Thanks a lot for keeping great stuff. I am very much thankful for this site. Feel free to visit my website; 국산야동

    ReplyDelete
  51. Your views are in accordance with my own for the most part. This is great content for your readers. Feel free to visit my website;

    일본야동

    ReplyDelete
  52. I like your all post. You have done really good work. Thank you for the information you provide, it helped me a lot. crackbay.org I hope to have many more entries or so from you.
    Very interesting blog.
    PRTG Network Monitor Crack

    ReplyDelete
  53. Really nice blog, thanks for sharing this helpful information.

    ReplyDelete
  54. Gutt Websäit : Zonahobisaya
    Gutt Websäit : Sinopsis Film
    Gutt Websäit : Logo
    Gutt Websäit : Zonahobisaya
    Gutt Websäit : Zonahobisaya
    Gutt Websäit : Zonahobisaya
    Gutt Websäit : Zonahobisaya
    Gutt Websäit : Zonahobisaya

    ReplyDelete

  55. Very informative article. Thanks!
    https://cracksync.com/photolemur-crack/

    ReplyDelete
  56. Really Good Work Done By You...However, stopping by with great quality writing, it's hard to see any good blog today.
    PROcrackerr
    WebcamMax CRACK
    Crack Softwares Free Download

    ReplyDelete
  57. The article is very well written. it's a good substance Hope you will post more. ทางเข้า 123plus

    ReplyDelete
  58. I like your all post. You have done really good work. Thank you for the information you provide, it helped me a lot. I hope to have many more entries or so from you.
    Very interesting blog.
    howcrack.org
    DeskSoft SmartCapture Crack

    ReplyDelete
  59. I am overjoyed to have discovered this article. The writer has an extremely creative mind; life is all about creating yourself, not finding yourself. Kindly visit my page.https://crackcut.com/wondershare-filmora-10-crack/

    ReplyDelete
  60. Really a nice article. Thank you so much for your efforts. Definitely, it will be helpful for others. 온라인카지노

    ReplyDelete
  61. Very nice work keep it up thanks for sharing the knowledge to us.
    카지노

    ReplyDelete
  62. Thanks for giving great kind of information. So useful and practical for me. Thanks for your excellent blog, nice work keep it up thanks for sharing the knowledge. 온라인바둑이

    ReplyDelete
  63. It was so bravely and depth information. I feel so good read to your blog.
    Software Universal

    ReplyDelete
  64. I guess I am the only one who came here to share my very own experience. Guess what!? I am using my laptop for almost the past 2 years, but I had no idea of solving some basic issues. I do not know how to Crack Softwares Free Download But thankfully, I recently visited a website named softwarelee.org
    OfficeSuite crack
    WebcamMax crack
    Norton Antivirus crack
    Wondershare Filmora crack
    SAM Broadcaster Pro crack

    ReplyDelete
  65. A blog comment is an art form. Positive remarks foster relationships. You're working very hard. Keep going. Thank you, I am a professional blogger. Visit this most recent article about Disable PS4 controller sound on PC. I appreciate your care.

    ReplyDelete
  66. This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. revo uninstaller pro crack

    ReplyDelete
  67. You certainly understand how to bring a problem to light and make it important.

    ReplyDelete
  68. A lot more peoople must read his and understand this side of thhe story.

    ReplyDelete
  69. I was surprised that you're not more popular since you definitely possess the gift.

    ReplyDelete
  70. Hope I'll get such posts in future too.

    ReplyDelete
  71. I am happy to find this post very useful for me, as it contains lot of information.

    ReplyDelete
  72. I appreciate you sharing this article; it was informative. I discovered this fantastic article Online Farnsworth Lantern Test. Not all cases of colorblindness result in ineffective service.

    ReplyDelete
  73. Diese wertvolle Lektüre bot neue Perspektiven. Sehen Sie sich dieses Profil an Click Test. Fordern Sie sich mit dem Klickgeschwindigkeitstest heraus.

    ReplyDelete
  74. Appreciate you sharing, great article post. Much thanks again. Fantastic.

    ReplyDelete
  75. Good way of explaining, and fastidious piece of writing to take facts

    ReplyDelete
  76. Major thanks for the post. Really looking forward to read more. Really Great.

    ReplyDelete
  77. I need to thank you for this great read!! I certainly loved every bit of it.

    ReplyDelete