{"id":256,"date":"2013-09-03T13:38:28","date_gmt":"2013-09-03T12:38:28","guid":{"rendered":"http:\/\/blog.mozilla.org\/jseward\/?p=256"},"modified":"2013-09-03T13:38:28","modified_gmt":"2013-09-03T12:38:28","slug":"how-compactly-can-cfiexidx-stack-unwinding-info-be-represented","status":"publish","type":"post","link":"https:\/\/blog.mozilla.org\/jseward\/2013\/09\/03\/how-compactly-can-cfiexidx-stack-unwinding-info-be-represented\/","title":{"rendered":"How compactly can CFI\/EXIDX stack unwinding info be represented?"},"content":{"rendered":"

In last week’s episode<\/a> of The Wonderful World of CFI Unwinding we looked at how fast it could be done.\u00a0 This week we’re going to look at how compactly the unwind information can be stored.<\/p>\n

But I know you want a summary up front, so here it is: I reckon it’s possible to store enough CFI to unwind all of libxul.so on x86_64-linux in just 5.4MB.\u00a0 At least, if my numbers are not wrong.<\/p>\n

Background<\/h2>\n

Representing CFI and EXIDX unwind information compactly in memory is critical for memory constrained devices running FirefoxOS and Fennec.<\/p>\n

The title of this posting is misleading, though.\u00a0 The question is not “how compactly can it be stored?”, but rather “how compactly can it be stored and still give us the really fast access we need?”.<\/p>\n

I did some digging.\u00a0 Valgrind will, if asked nicely, print out the CFI unwinding rules as it stores them.\u00a0 The previous posting<\/a> described how it only stores unwind information for a limited register set — on x86_64-linux, which I’m experimenting with here — %rip, %rsp and %rbp.\u00a0 It manages to summarise the unwind rule for each address range into just one line of text:<\/p>\n

 \u00a0[0x53eea71 .. 0x53eea84]: let cfa=oldBP+16 in RA=*(cfa+-8) SP=cfa+0 BP=*(cfa+-16)<\/pre>\n
This says: for %rip values in the range 0x53eea71 to 0x53eea84, first compute<\/p>\n
\u00a0 cfa = %rbp + 16<\/pre>\n
then<\/p>\n
\u00a0 previous %rip = *(cfa-8)\r\n\u00a0 previous %rsp = cfa\r\n\u00a0 previous %rbp = *(cfa-16)<\/pre>\n
For libxul.so for a recent m-c, built with “-g -O”, there are 890,065 of these records — that is, the compiler gives unwind descriptions for 890,065 different code address ranges in libxul.so.<\/p>\n
That sounds like a lot of data.\u00a0 But those descriptions are immensely repetitive.\u00a0 Just how repetitive we can see by generating the descriptions, cutting off the address range part and throwing the rest through sort -u:<\/p>\n
  valgrind --smc-check=all-non-file --tool=none --trace-cfi=yes \" \\\r\n     --trace-symtab-patt=*libxul.so*\" \\\r\n     .\/ff-opt-linux\/dist\/bin\/firefox-bin &> logfile\r\n\r\n  cat logfile | grep \"let cfa=\" | cut -c 27- | sort -u | wc<\/pre>\n
The are just 75 different ones in nearly 900k address ranges!<\/p>\n
In hindsight, that shouldn’t be a big surprise.\u00a0 A description of how to recover the return address, stack pointer and frame pointer must be pretty boring.\u00a0 Either they’re parked in memory at a small handful of 8-aligned offsets from the stack pointer, or they are the value of one of the previous registers plus or minus a similarly constrained offset.<\/p>\n
In other words, the set of descriptions is small because GCC generates only a small set of stack frame layouts, if we restrict ourselves to considering just the parts of the frame needed for unwinding.<\/p>\n
I was surprised by these figures, so I also tested the CFI on the main Valgrind executable.\u00a0 That has 35,430 address ranges containing 160 unique descriptions.\u00a0 Not quite as striking as the libxul.so case, but not far off.<\/p>\n
Storing the address ranges compactly<\/h2>\n
The obvious storage optimisation is to park the 75 descriptions in a dictionary, the size of which is insignificant, and represent the 890,065 address ranges and dictionary-entry number as compactly as possible.\u00a0 Then, sort these entries by address range and put them in a flat array, for fast binary search.<\/p>\n
How compactly can we represent an (address, length, dictionary-entry-number) triple?\u00a0 Naively, the address is a 64 bit word, and length and entry number could be 32 bits, giving 16 bytes in total.<\/p>\n
That’s way overkill.\u00a0 Since we’ll have one table per mapped object, the base address can be replaced by the offset from the base of the object.\u00a0 libxul.so has about 36MB of text, so unfortunately that’s 4 bytes.\u00a0 The address range lengths are tiny, though, mostly less than 256, so we could store than in a byte, and duplicate the descriptor for the occasional longer run.\u00a0 And the dictionary entry number in the two cases I tested would fit in 8 bits.<\/p>\n
So that’s 6 bytes per description.\u00a0 For 890,065 descriptions, 5,340,390 bytes in total.<\/p>\n
It would be interesting to see if the same level of duplication occurs for CFI and EXIDX on ARM.\u00a0 But given that it merely reflects the non-diversity of frame layouts, I find it hard to believe we’d see anything much different.<\/p>\n
EXIDX contains less information than CFI, yet — as experiments on Fennec\/ARM have shown — it gives good unwinding results.\u00a0 So this analysis surely applies equally to our EXIDX-based targets, Fennec\/ARM and FirefoxOS\/ARM.<\/p>\n","protected":false},"excerpt":{"rendered":"
In last week’s episode of The Wonderful World of CFI Unwinding we looked at how fast it could be done.\u00a0 This week we’re going to look at how compactly the unwind information can be stored. But I know you want … Continue reading<\/a><\/p>\n","protected":false},"author":240,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts\/256"}],"collection":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/users\/240"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/comments?post=256"}],"version-history":[{"count":0,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts\/256\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/media?parent=256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/categories?post=256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/tags?post=256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}