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.

56 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. Nice article, thanks for the information. It's very complete information. I will bookmark for next reference
    jaring futsal | jaring golf | jaring pengaman proyek |
    jaring pengaman bangunan | jaring pengaman gedung
    http://www.jual-jaring.blogspot.com/
    http://www.agen-jaring.blogspot.com/
    http://www.pancasamudera-safetynet.blogspot.com/
    http://www.toko-jaring.blogspot.com/
    http://www.pusat-jaring.blogspot.com/
    http://jualjaringpengaman.blogspot.com/
    https://pancasamudera.wordpress.com/
    https://pasangjaringfutsal.wordpress.com/
    https://jualtambangmurah.wordpress.com/
    https://tokojaring.wordpress.com/
    https://jualjaringfutsal.wordpress.com/
    https://jaringfutsal.wordpress.com/


    ReplyDelete
  10. 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
  11. Thank you for the information of this code!

    ReplyDelete
  12. ห้ามพลาดหนังดัง ชนโรง>> movie online
    REVIEWS ตามใจอยาก>> Travel With Us

    ReplyDelete
  13. 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
  14. 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
  15. Really a vry nice blog i really appreciate all your efforts ,thank you so mch for sharing this valuable information with all of us .
    Local Packers And Movers Bangalore

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

    ReplyDelete
  17. https://cracksoon.com/fl-studio-crack-full-special-torrent-download-here-2020/
    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
  18. https://crackpluskey.com/vce-exam-simulator-crack-license-key/
    VCE Exam Simulator Serial Key allows us to adjust the simulation classes, the other allows the user to reply to questions and make parameters. For newcomers, the report is official, it may arrive at the origin of the analysis, and listing the sign of a right with a crack will entail a change of the orders of evaluation of the study. You can reply to topics to complex types of plans by naming their class and taking the place.

    ReplyDelete
  19. 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
  20. https://usecracked.com/final-cut-pro-x-full-crack-download/
    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.

    ReplyDelete
  21. 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
  22. Get Packers and Movers Jaipur List of Top Reliable, 100% Affordable, Verified and Secured Service Provider. Get Free ###Packers and Movers Jaipur Price Quotation instantly and Save Cost and Time. Packers and Movers Jaipur ✔✔✔Reviews and Compare Charges for household Shifting, Home/Office Relocation, ***Car Transportation, Pet Relocation, Bike SHifting @ Packers And Movers Jaipur

    ReplyDelete
  23. Android Apks - is a place where you can fiAndroid Apks - is a place where you can find paid best android apk apps games to download free full version for mobile, tablets.
    androidapkhere.com

    ReplyDelete
  24. 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
  25. 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
  26. 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
  27. MAGIX SOUND FORGE Audio Studio Key Free is a professional audio editor that provides all the tools you need to record, control, load and edit audio files with VST and ASIO support. magixsoundforgeaudiostudiotorrent

    ReplyDelete
  28. 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
  29. 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
  30. Corel VideoStudio Ultimate License Key Crack has a professional video editing environment and a lot of powerful tools. corelvideostudioserialkey

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

    ReplyDelete
  32. If you are looking for GTA 5 iOS, then you have landed on the right page. Here you will get all information about GTA 5 iOS Apk including a tutorial on how to download and install GTA 5 on iOS. https://gta5apk.biz/ios/

    ReplyDelete
  33. This is very interesting, You’re a very skilled blogger. I’ve joined your feed and look forward to seeking more of your magnificent post. Also, I have shared your website on my social networks!
    Camtasia Studio Crack
    Ezdrummer Crack
    Minitool Partition Wizard Pro Crack
    Iobit Driver Booster Pro Crack

    ReplyDelete
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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

  40. 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
  41. 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
  42. I am a regular visitor, and this post posted on this web page is truly pleasant.
    LooserCrack

    ReplyDelete
  43. 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

  44. 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
  45. 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
  46. Thanks for Nice and Informative Post. This article is really contains lot more information about This Topic eset-nod32-antivirus-license-key

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

    ReplyDelete
  48. I am very impressed with your post because this post is very beneficial for me and provide a new knowledge to me
    Reason Crack
    LicenseCrawler Crack

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

    ReplyDelete
  50. 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
  51. Great Job Amazing content and blog Thanks For this nice content
    apoweredit-crack-download

    ReplyDelete