RSS | technovelty home | page of ian | ian@wienand.org
In a previous post I mentioned split debugging info.
One addendum to this is how symbols are handled. Symbols are separate to debugging info (i.e. the stuff about variable names, types, etc you get when -g is turned on), but necessary for a good debugging experience.
You have a choice, however, of where you leave the symbol files. You can leave them in your shipping binary/library so that users who don't have the full debugging info available will still get a back-trace that at least has function names. The cost is slightly larger files for everyone, even if the symbols are never used. This appears to be what Redhat does with it's system libraries, for example.
The other option is to keep the symbols in the .debug files along-side the debug info. This results in smaller libraries, but really requires you to have the debug info files available to have workable debugging. This appears to be what Debian does.
So, how do you go about this? Well, it depends on what tools you're using.
For binutils strip, there is some asynchronicity between the --strip-debug and --only-keep-debug options. --strip-debug will keep the symbol table in the binary, and --only-keep-debug will also keep the symbol table.
$ gcc -g -o main main.c $ readelf --sections ./main | grep symtab [36] .symtab SYMTAB 00000000 000f48 000490 10 37 53 4 $ cp main main.debug $ strip --only-keep-debug main.debug $ readelf --sections ./main.debug | grep symtab [36] .symtab SYMTAB 00000000 000b1c 000490 10 37 53 4 $ strip --strip-debug ./main $ readelf --sections ./main.debug | grep symtab [36] .symtab SYMTAB 00000000 000b1c 000490 10 37 53 4
Of course, you can then strip (with no arguments) the final binary to get rid of the symbol table; but other than manually pulling out the .symtab section with objcopy I'm not aware of any way to remove it from the debug info file.
Constrast with elfutils; more commonly used on Redhat based system I think.
eu-strip's --strip-debug does the same thing; leaves the symtab section in the binary. However, it also has a -f option, which puts any removed sections during the strip into a separate file. Therefore, you can create any combination you wish; eu-strip -f results in an empty binary with symbols and debug data in the .debug file, while eu-strip -g -f results in debug data only in the .debug file, and symbol data retained in the binary.
The only thing to be careful about is using eu-strip -g -f and then further stripping the binary, and consequently destroying the symbol table, but retaining debug info. This can lead to some strange things in backtraces:
$ gcc -g -o main main.c
$ eu-strip -g -f main.debug main
$ strip ./main
$ gdb ./main
GNU gdb (GDB) 7.1-debian
...
(gdb) break foo
Breakpoint 1 at 0x8048397: file main.c, line 2.
(gdb) r
Starting program: /home/ianw/tmp/symtab/main
Breakpoint 1, foo (i=100) at main.c:2
2return i + 100;
(gdb) back
#0 foo (i=100) at main.c:2
#1 0x080483b1 in main () at main.c:6
#2 0x423f1c76 in __libc_start_main (main=Could not find the frame base for "__libc_start_main".
) at libc-start.c:228
#3 0x08048301 in ?? ()
Note one difference between strip and eu-strip is that binutils strip will leave the .gnu_debuglink section in, while eu-strip will not:
$ gcc -g -o main main.c $ eu-strip -g -f main.debug main $ readelf --sections ./main| grep debuglink [29] .gnu_debuglink PROGBITS 00000000 000bd8 000010 00 0 0 4 $ eu-strip main $ readelf --sections ./main| grep debuglink $ gcc -g -o main main.c $ eu-strip -g -f main.debug main $ strip main $ readelf --sections ./main| grep debuglink [27] .gnu_debuglink PROGBITS 00000000 0005d8 000010 00 0 0 4
posted at: Tue, 24 Aug 2010 11:39 | in /code | permalink | add comment (1 others)
The usual case for cross-compiling is that your target is so woefully slow and under-powered that you would be insane to do anything else.
However, sometimes for one of the best reasons of all, "historical reasons", you might ship a 64-bit product but support building on 32-bit hosts, and thus cross-compile even on a very fast architecture like x86. How much does this cost, even though almost everyone is running the 32-bit cross-compiler on a modern 64-bit machine?
To test, I got a a 32-bit cross and a 64-bit native x86_64 compiler and toolchain; in this case based on gcc-4.1.2 and binutils 2.17. I then did a allyesconfig build of Linux 2.6.33 x86_64 kernel 3 times using the cross compilier toolchain and then native one. The results (in seconds):
| 32-bit | 64-bit |
|---|---|
| 6090 | 5684 |
| 6050 | 5616 |
| 6063 | 5652 |
| average | |
| 6067 | 5650 |
So, all up, ~7% less by building your 64-bit code on a 64-bit machine with a 32-bit cross-compiler.
posted at: Thu, 06 May 2010 16:50 | in /code/c | permalink | add comment (2 others)
Some time ago I wrote a description of the -Bsymbolic linker flag which could do with some further explanation. The original article is a good starting place.
One interesting point that I didn't go into was the potential for code optimisation -Bsymbolic brings about. I'm not sure if I missed that at the time, or the toolchain changed, both are probably equally likely!
Let me recap the example...
ianw@jj:/tmp/bsymbolic$ cat Makefile
all: test test-bsymbolic
clean:
rm -f *.so test testsym
liboverride.so : liboverride.c
$(CC) -Wall -O2 -shared -fPIC -o liboverride.so $<
libtest.so : libtest.c
$(CC) -Wall -O2 -shared -fPIC -o libtest.so $<
libtest-bsymbolic.so : libtest.c
$(CC) -Wall -O2 -shared -fPIC -Wl,-Bsymbolic -o $@ $<
test : test.c libtest.so liboverride.so
$(CC) -Wall -O2 -L. -Wl,-rpath=. -ltest -o $@ $<
test-bsymbolic : test.c libtest-bsymbolic.so liboverride.so
$(CC) -Wall -O2 -L. -Wl,-rpath=. -ltest-bsymbolic -o $@ $<
$ cat liboverride.c
#include <stdio.h>
int foo(void)
{
printf("override foo called\n");
return 0;
}
$ cat libtest.c
#include <stdio.h>
int foo(void) {
printf("libtest foo called\n");
return 1;
}
int test_foo(void) {
return foo();
}
$ cat test.c
#include <stdio.h>
int test_foo(void);
int main(void)
{
printf("%d\n", test_foo());
return 0;
}
In words; libtest.so provides test_foo(), which calls foo() to do the actual work. libtest-bsymbolic.so is simply built with the flag in question, -Bsymbolic. liboverride.so provides the alternative version of foo() designed to override the original via a LD_PRELOAD of the library.
test is built against libtest.so, test-bsymbolic against libtest-bsymbolic.so.
Running the examples, we can see that the LD_PRELOAD does not override the symbol in the library built with -Bsymbolic.
$ ./test libtest foo called 1 $ ./test-bsymbolic libtest foo called 1 $ LD_PRELOAD=liboverride.so ./test override foo called 0 $ LD_PRELOAD=liboverride.so ./test-bsymbolic libtest foo called 1
There are a couple of things going on here. Firstly, you can see that the SYMBOLIC flag is set in the dynamic section, leading to the dynamic linker behaviour I explained in the original article:
ianw@jj:/tmp/bsymbolic$ readelf --dynamic ./libtest-bsymbolic.so Dynamic section at offset 0x550 contains 22 entries: Tag Type Name/Value 0x00000001 (NEEDED) Shared library: [libc.so.6] 0x00000010 (SYMBOLIC) 0x0 ...
However, there is also an effect on generated code. Have a look at the PLTs:
$ objdump --disassemble-all ./libtest.so
Disassembly of section .plt:
[... blah ...]
0000039c <foo@plt>:
39c: ff a3 10 00 00 00 jmp *0x10(%ebx)
3a2: 68 08 00 00 00 push $0x8
3a7: e9 d0 ff ff ff jmp 37c <_init+0x30>
</pre>
</div>
<div class="codebox">
<pre>
$ objdump --disassemble-all ./libtest-bsymbolic.so
Disassembly of section .plt:
00000374 <__gmon_start__@plt-0x10>:
374: ff b3 04 00 00 00 pushl 0x4(%ebx)
37a: ff a3 08 00 00 00 jmp *0x8(%ebx)
380: 00 00 add %al,(%eax)
...
00000384 <__gmon_start__@plt>:
384: ff a3 0c 00 00 00 jmp *0xc(%ebx)
38a: 68 00 00 00 00 push $0x0
38f: e9 e0 ff ff ff jmp 374 <_init+0x30>
00000394 <puts@plt>:
394: ff a3 10 00 00 00 jmp *0x10(%ebx)
39a: 68 08 00 00 00 push $0x8
39f: e9 d0 ff ff ff jmp 374 <_init+0x30>
000003a4 <__cxa_finalize@plt>:
3a4: ff a3 14 00 00 00 jmp *0x14(%ebx)
3aa: 68 10 00 00 00 push $0x10
3af: e9 c0 ff ff ff jmp 374 <_init+0x30>
Notice the difference? There is no PLT entry for foo() when -Bsymbolic is used.
Effectively, the toolchain has noticed that foo() can never be overridden and optimised out the PLT call for it. This is analogous to using "hidden" attributes for symbols, which I have detailed in another article on symbol visiblity attributes (which also goes into PLT's, if the above meant nothing to you).
So -Bsymbolic does have some more side-effects than just setting a flag to tell the dynamic linker about binding rules -- it can actually result in optimised code. However, I'm still struggling to find good use-cases for -Bsymbolic that can't be better done with Version scripts and visibility attributes. I would certainly recommend using these methods if at all possible.
Thanks to Ryan Lortie for comments on the original article.
posted at: Mon, 22 Mar 2010 15:40 | in /code/c | permalink | add comment (0 others)
So, you have some application where you want the user to specify a remote host/port, and you want to support IPv4 and IPv6.
For literal addresses, things are fairly simple. IPv4 addresses are simple, and RFC2732 has things covered by putting the IPv6 address within square brackets.
It gets more interesting as to what you should do with hostnames. The problem is that getaddrinfo can return you multiple addresses, but without extra disambiguation from the user it is very difficult to know which one to choose. RFC4472 discusses this, but there does not appear to be any good solution.
Possibly you can do something like ping/ping6 and have a separate program name or configuration flag to choose IPv6. This comes at a cost of transparency.
The glibc implementation of getaddrinfo() puts considerable effort into deciding if you have an IPv6 interface up and running before it will return an IPv6 address. It will even recognise link-local addresses and sort addresses more likely to work to the front of the returned list as described here. However, there is still a small possibility that the IPv6 interface doesn't actually work, and so the library will sort the IPv6 address as first in the returned list when maybe it shouldn't be.
If you are using TCP, you can connect to each address in turn to find one that works. With UDP, however, the connect essentially does nothing.
So I believe probably the best way to handle hostnames for UDP connections, at least on Linux/glibc, is to trust getaddrinfo to return the sanest values first, try a connect on the socket anyway just for extra security and then essentially hope it works. Below is some example code to do that (literal address splitter bit stolen from Python's httplib).
import socket
DEFAULT_PORT = 123
host = '[fe80::21c:a0ff:fb27:7196]:567'
# the port will be anything after the last :
p = host.rfind(":")
# ipv6 literals should have a closing brace
b = host.rfind("]")
# if the last : is outside the [addr] part (or if we don't have []'s
if (p > b):
try:
port = int(host[p+1:])
except ValueError:
print "Non-numeric port"
raise
host = host[:p]
else:
port = DEFAULT_PORT
# now strip off ipv6 []'s if there are any
if host and host[0] == '[' and host[-1] == ']':
host = host[1:-1]
print "host = <%s>, port = <%d>" % (host, port)
the_socket = None
res = socket.getaddrinfo(host, port, socket.AF_UNSPEC, socket.SOCK_DGRAM)
# go through all the returned values, and choose the ipv6 one if
# we see it.
for r in res:
af,socktype,proto,cname,sa = r
try:
the_socket = socket.socket(af, socktype, proto)
the_socket.connect(sa)
except socket.error, e:
# connect failed! try the next one
continue
break
if the_socket == None:
raise socket.error, "Could not get address!"
# ready to send!
the_socket.send("hi!")
posted at: Tue, 16 Mar 2010 15:54 | in /code/python | permalink | add comment (0 others)
The ABC overhauled DIG Jazz (now I think it's just called "ABC Jazz") and upgraded from the oh-so 2008 XML playlist to a much more web-cool JSON one.
Hence Version 3 (source) of the applet. Now with improved HTML escaping and different colors.
Check out The Dilworths while you're there!
posted at: Sat, 27 Feb 2010 00:44 | in /code/gnome | permalink | add comment (0 others)
I've recently found out a bit more about separating debug info, and thought a consolidated reference might be handy.
Most every distribution now provides separate debug packages which contain only the debug info, saving much space for the 99% of people who never want to start gdb.
This is achieved with objcopy and --only-keep-debug/--add-gnu-debuglink and is well explained in the man page.
This adds a .gnu_debuglink section to the binary with the name of debug file to look for.
$ gcc -g -shared -o libtest.so libtest.c $ objcopy --only-keep-debug libtest.so libtest.debug $ objcopy --add-gnu-debuglink=libtest.debug libtest.so $ objdump -s -j .gnu_debuglink libtest.so libtest.so: file format elf32-i386 Contents of section .gnu_debuglink: 0000 6c696274 6573742e 64656275 67000000 libtest.debug... 0010 52a7fd0a R...
The first part is the name of the file, the second part is a check-sum of debug-info file for later reference.
Did you know that binaries also get stamped with a unique id when they are built? The ld --build-id flag stamps in a hash near the end of the link.
$ readelf --wide --sections ./libtest.so | grep build [ 1] .note.gnu.build-id NOTE 000000d4 0000d4 000024 00 A 0 0 4 $ objdump -s -j .note.gnu.build-id libtest.so libtest.so: file format elf32-i386 Contents of section .note.gnu.build-id: 00d4 04000000 14000000 03000000 474e5500 ............GNU. 00e4 a07ab0e4 7cd54f60 0f5cf66b 5799b05c .z..|.O`.\.kW..\ 00f4 2d43f456 -C.V
Incase you're wondering what the format of that is...
uint32 name_size; /* size of the name */ uint32 hash_size; /* size of the hash */ uint32 identifier; /* NT_GNU_BUILD_ID == 0x3 */ char name[name_size]; /* the name "GNU" */ char hash[hash_size]; /* the hash */
Although the actual file may change (due to prelink or similar) the hash will not be updated and remain constant.
The last piece of the puzzle is how gdb attempts to find the debug-info files when it is run. The main variable influencing this is debug-file-directory.
(gdb) show debug-file-directory The directory where separate debug symbols are searched for is "/usr/lib/debug".
The first thing gdb does, which you can verify via an strace, is search for a file called [debug-file-directory]/.build-id/xx/yyyyyy.debug; where xx is the first two hexadecimal digits of the hash, and yyy the rest of it:
$ objdump -s -j .note.gnu.build-id /bin/ls
/bin/ls: file format elf32-i386
Contents of section .note.gnu.build-id:
8048168 04000000 14000000 03000000 474e5500 ............GNU.
8048178 c6fd8024 2a11673c 7c6a5af6 2c65b1b5 ...$*.g<|jZ.,e..
8048188 d7e13fd4 ..?.
... [running gdb /bin/ls] ...
access("/usr/lib/debug/.build-id/c6/fd80242a11673c7c6a5af62c65b1b5d7e13fd4.debug", F_OK) = -1 ENOENT (No such file or directory)
Next it moves onto the debug-link info filename. First it looks for the filename in same directory as the object being debugged. After that it looks for the file in a sub-directory called .debug/ in the same directory.
Finally, it prepends the debug-file-directory to the path of the object being inspected and looks for the debug info there. This is why the /usr/lib/debug directory looks like the root of a file-system; if you're looking for the debug-info of /usr/lib/libfoo.so it will be looked for in /usr/lib/debug/usr/lib/libfoo.so.
Interestingly, the sysroot and solib-search-path don't appear to have anything to do with these lookups. So if you change the sysroot, you also need to change the debug-file-directory to match.
However, most distributions make all this "just work", so hopefully you'll never have to worry about anyway!
posted at: Fri, 22 Jan 2010 09:11 | in /code | permalink | add comment (3 others)
By now everybody has now heard about Go, Google's expressive, concurrent, garbage collecting language. One big, glaring thing stuck out at me when I was reading the documentation:
Do not communicate by sharing memory; instead, share memory by communicating.
One of the examples given is a semaphore using a channel, which I'll copy here for posterity.
var sem = make(chan int, MaxOutstanding)
func handle(r *Request) {
sem <- 1; // Wait for active queue to drain.
process(r); // May take a long time.
<-sem; // Done; enable next request to run.
}
func Serve(queue chan *Request) {
for {
req := <-queue;
go handle(req); // Don't wait for handle to finish.
}
}
Here is a little illustration of that in operation.
Serve creates goroutines via the go keyword; each of which tries to get a slot in the channel. In the example there are only 3 slots, so it acts like a semaphore of count 3. When done, each thread returns its slot to the channel, which allows anyone blocked to be woken and continued.
This instantly reminded me of the very first thing you need to do if you ever want to pass Advanced Operating Systems -- write a semaphore server to provide synchronisation within your OS.
In L4, threads communicate with each other via inter-process communication (IPC). IPC messages have a fixed format - you specify a target thread, bundle some data into the available slots in the IPC format and fire it off. By default you block waiting for a reply -- this all happens within a single call for efficiency. On the other side, you can write servers who are listening for remote IPC connections, where everything happens in reverse.
Here's another illustration the of the trivial semaphore server concept Shehjar and I implemented.
Look familiar? Instead of a blocking push of a number into a slot into a channel, you make a blocking IPC call to a remote server.
My point here is that both take the approach of sharing memory via communication. When using IPC, you bundle up all your information into the available slots in the IPC message and send it. When using a channel, you bundle your information into an entry in the channel and call your goroutine. Receiving the IPC is the same as draining a channel - both result in you getting the information that was bundled into it by the caller.
| IPC | Go |
|---|---|
| Start thread | Start goroutine |
| New thread blocks listening for IPC message | Goroutine blocks draining empty channel |
| Bundle information into IPC message | Bundle data into type of your channel |
| Send IPC to new thread | Push data into channel |
| Remote thread unbundles IPC | goroutine drains channel and gets data |
Whenever you mention the word "microkernel", people go off the deep-end and one thing they seem to forget about is the inherent advantages of sharing state only via communication. As soon as you do that, you've broken open an amazing new tool for concurrency, which is now implicitly implied. By communicating via messages/channels rather than shared global state, it doesn't matter where you run! One of those threads in the example could be running on another computer in your cloud, marshalling up it's IPC messages/channel entries and sending them over TCP/IP -- nobody would care!
At any rate, do not communicate by sharing memory; instead, share memory by communicating is certainly an idea whose time has come.
posted at: Fri, 20 Nov 2009 11:37 | in /code | permalink | add comment (5 others)
I recently finished The Race for a New Game Machine: Creating the Chips Inside the XBox 360 and the Playstation 3 (David Shippy and Mickie Phipps); an interesting insight into the processor development process from some of the lead architects.
The executive summary is : Sony, Toshiba and IBM (STI) decided to get together to create the core of the Playstation 3 — the Cell processor. Sony, with their graphics and gaming experience, would do the Synergistic Processing Elements; extremely fast but limited sub-units specialising in doing 3D graphics and physics work (i.e. great for games). IBM would do a Power based core that handled the general purpose computing requirements.
The twist comes when Microsoft came along to IBM looking for the Xbox 360 processor, and someone at IBM mentioned the Power core that was being worked on for the Playstation. Unsurprisingly, the features being built for the Playstaion also interested Microsoft, and the next thing you know, IBM is working on the same core for Microsoft and Sony at the same time, without telling either side.
This whole chain of events makes for a very interesting story. The book is written for a general audience, but you'll probably get the most out of it if you already have some knowledge of computer architecture; if you're trying to understand some of the concepts referred to from the two line descriptions you'll get a bit lost (H&P it is not).
The only small criticism is that it sometimes falls into reading a bit like a long LinkedIn recommendation. However, the book is very well paced, and throws in just enough technical tidbits amongst the corporate and personal dramas to make it a very fun read.
One thing that is talked about a bit is the fan-out of four (FO4) metric used in the designers quest to push the chip as fast as possible (and, as mentioned many times in the book, faster than what Intel could do!). I thought it might be useful to expand on this interesting metric a bit.
One problem facing chip architects is that, thanks to Moore's Law, it is hard to find a constant to compare design versus implementation. For example, you may design an amazing logic-block to factor large integers into products of prime numbers, but somebody else with better fabrication facilities might be able to essentially brute-force a better solution by producing faster hardware using a much less innovative design.
Some metric is needed that can compare the two designs discounting who has the better fabrication process. This is where the FO4 comes in.
When you change the input to a logic gate, it is not like it magically flips the output to the correct level instantaneously. There is a latency while everything settles to its correct level — the gate delay. The more gates connected to the output of a gate the more current required, which has additional effects on latency. The FO4 latency is defined as the time required to flip an inverter gate connected to (fanned-out) to four other inverter gates.
Thus you can describe the latency of other logic blocks in multiples of FO4 latencies. As this avoids measuring against wall-time it is an effective description of the relative efficiency of logic designs. For example, you may calculate that your factoriser has a latency of 100 FO4. Just because someone else's 200 FO4 factoriser gets a result a few microseconds faster thanks to their fancy ultra-low-FO4-latency fabrication process, you can still show that your design, at least a priori, is better.
The book refers several times to efforts to reduce the FO4 of the processor as much as possible. The reason this is important in this context is that the maximum latency on the critical path will determine the fastest clock speed you can run the processor at. For reasons explained in the book high clock speed was a primary goal, so every effort had to be made to reduce latencies.
All modern processors operate as a production line, with each stage doing some work and passing it on to the next stage. Clearly the slowest stage determines the maximum speed that the production line can run at (weakest link in the chain and all that). For example, if you clock at 1Ghz, that means each cycle takes 1 nanosecond (1s / 1,000,000,000Hz). If you have a F04 latency of say, 10 picoseconds, that means any given stage can have a latency of no more than 100 FO4 — otherwise that stage would not have enough time to settle and actually produce the correct result.
Thus the smaller you can get the FO4 latencies of your various stages, the higher you can safely up the clock speed. One way around long latencies might be to split-up your logic into smaller stages, making a much longer pipeline (production line). For example, split your 100 FO4 block into two 50 FO4 stages. You can now clock the processor higher, but this doesn't necessarily mean you'll get actual results out the end of the pipeline any faster (as Intel discovered with the Pentium 4 and it's notoriously long pipelines and corresponding high clock rates).
Of course, this doesn't even begin to describe the issues with superscalar design, instruction level parallelism, cache interaction and the myriad of other things the architects have to consider.
Anyway, after reading this book I guarantee you'll have an interesting new insight the next time you fire-up Guitar Hero.
posted at: Wed, 15 Jul 2009 19:15 | in /code/arch | permalink | add comment (2 others)
It seems the ABC updated the DIG Jazz now-playing list format, breaking V1. Some quick flash disassembly and a bit of hacking, and order is restored. As a bonus, it now shows the upcoming songs.
Source or Debian package.
posted at: Mon, 18 May 2009 23:20 | in /code/gnome | permalink | add comment (0 others)
I think the most correct way to describe utilisation of a hash-table is using chi-squared distributions and hypothesis and degrees of freedom and a bunch of other things nobody but an actuary remembers. So I was looking for a quick method that was close-enough but didn't require digging out a statistics text-book.
I'm sure I've re-invented some well-known measurement, but I'm not sure what it is. The idea is to add up the total steps required to look-up all elements in the hash-table, and compare that to the theoretical ideal of a uniformly balanced hash-table. You can then get a ratio that tells you if you're in the ball-park, or if you should try something else. A diagram should suffice.
This seems to give quite useful results with a bare minimum of effort, and most importantly no tricky floating point math. For example, on the standard Unix words with a 2048 entry hash-table, the standard DJB hash came out very well (as expected)
Ideal 2408448 Actual 2473833 ---- Ratio 0.973569
To contrast, a simple "add each character" type hash:
Ideal 2408448 Actual 6367489 ---- Ratio 0.378241
Example code is hash-ratio.py. I expect this measurement is most useful when you have a largely static bunch of data for which you are attempting to choose an appropriate hash-function. I guess if you are really trying to hash more or less random incoming data and hence only have a random sample to work with, you can't avoid doing the "real" statistics.
posted at: Thu, 07 May 2009 16:37 | in /code | permalink | add comment (1 others)
If you code for long enough on x86-64, you'll eventually hit an error such as:
(.text+0x3): relocation truncated to fit: R_X86_64_32S against symbol `array' defined in foo section in ./pcrel8.o
Here's a little example that might help you figure out what you've done wrong.
Consider the following code:
$ cat foo.s .globl foovar .section foo, "aw",@progbits .type foovar, @object .size foovar, 4 foovar: .long 0 .text .globl _start .type function, @function _start: movq $foovar, %rax
In case it's not clear, that would look something like:
int foovar = 0;
void function(void) {
int *bar = &foovar;
}
Let's build that code, and see what it looks like
$ gcc -c foo.s $ objdump --disassemble-all ./foo.o ./foo.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <_start>: 0: 48 c7 c0 00 00 00 00 mov $0x0,%rax Disassembly of section foo: 0000000000000000 <foovar>: 0: 00 00 add %al,(%rax) ...
We can see that the mov instruction has only allocated 4 bytes (00 00 00 00) for the linker to put in the address of foovar. If we check the relocations:
$ readelf --relocs ./foo.o Relocation section '.rela.text' at offset 0x3a0 contains 1 entries: Offset Info Type Sym. Value Sym. Name + Addend 000000000003 00050000000b R_X86_64_32S 0000000000000000 foovar + 0
The R_X86_64_32S relocation is indeed only a 32-bit relocation. Now we can tickle this error. Consider the following linker script, which puts the foo section about 5 gigabytes away from the code.
$ cat test.lds
SECTIONS
{
. = 10000;
.text : { *(.text) }
. = 5368709120;
.data : { *(.foo) }
}
This now means that we can not fit the address of foovar inside the space allocated by the relocation. When we try it:
$ ld -Ttest.lds ./foo.o ./foo.o: In function `_start': (.text+0x3): relocation truncated to fit: R_X86_64_32S against symbol `foovar' defined in foo section in ./foo.o
What this means is that the full 64-bit address of foovar, which now lives somewhere above 5 gigabytes, can't be represented within the 32-bit space allocated for it.
For code optimisation purposes, the default immediate size to the mov instructions is a 32-bit value. This makes sense because, for the most part, programs can happily live within a 32-bit address space, and people don't do things like keep their data so far away from their code it requires more than a 32-bit address to represent it. Defaulting to using 32-bit immediates therefore cuts the code size considerably, because you don't have to make room for a possible 64-bit immediate for every mov.
So, if you want to really move a full 64-bit immediate into a register, you want the movabs instruction. Try it out with the code above - with movabs you should get a R_X86_64_64 relocation and 64-bits worth of room to patch up the address, too.
If you're seeing this and you're not hand-coding, you probably want to check out the -mmodel argument to gcc.
posted at: Thu, 12 Mar 2009 23:20 | in /code/c | permalink | add comment (2 others)
An interesting extract from the latest IA32 SDM (18.20.5)
The TSC, IA32_MPERF, and IA32_FIXED_CTR2 operate at the same, maximum-resolved frequency of the platform, which is equal to the product of scalable bus frequency and maximum resolved bus ratio.
For processors based on Intel Core microarchitecture, the scalable bus frequency is encoded in the bit field MSR_FSB_FREQ[2:0] at (0CDH), see Appendix B, "Model-Specific Registers (MSRs)". The maximum resolved bus ratio can be read from the following bit field:
- If XE operation is disabled, the maximum resolved bus ratio can be read in MSR_PLATFORM_ID[12:8]. It corresponds to the maximum qualified frequency.
- IF XE operation is enabled, the maximum resolved bus ratio is given in MSR_PERF_STAT[44:40], it corresponds to the maximum XE operation frequency configured by BIOS.
In summary, TSC increment = (scalable bus frequency) * (maximum resolved bus ratio). This implies the TSC is incrementing based on some external bus source (any hardware engineers explain what happened for Core here?), and is a departure from simply assuming that the TSC increments once for each CPU cycle.
The interesting bit is that if XE operation is disabled, the bus ratio is assumed to be the maximum qualified frequency. This seems to mean that if you overclock your CPU and your processor is running at higher than the qualified frequency, attempts to measure the CPU speed by counting TSC ticks over a given time may yeild the wrong results (well, will yield the rated result; i.e. the speed of the processor you bought out of the box).
While interesting, this divergence is probably has little practical implications because using the TSC for benchmarking is already fraught with danger. You have to be super careful to make sure the compiler and processor don't reschedule things around you and handle other architectural nuances. If you need this level of information, you're much better using the right tools to get it (my favourite is perfmon2).
posted at: Thu, 26 Feb 2009 15:54 | in /code/arch | permalink | add comment (1 others)
Fools ignore complexity. Pragmatists suffer it. Some can avoid it. Geniuses remove it.
Alan J. Perlis, Eipgrams on Programming, SIGPLAN Notices Vol. 17, No. 9, September 1982, pages 7-13.
posted at: Wed, 04 Feb 2009 23:23 | in /code | permalink | add comment (0 others)
As a photo management application, Facebook sucks. But it is something that people actually look at (as opposed to Flickr, which is great, but getting people to log-in or follow special guest pass links is a PITA).
I like to keep all my raw photos locally, using IPTC for comments (which Flickr reads -- I put them in using some custom scripts and the Python bindings of libiptcdata) and geo-tagged in the EXIF data (using my google maps point locator). I figure this way if Flickr goes bust/gets bought by Microsoft all I need to do is re-upload somewhere else.
I was waiting for Flickr to integrate with Facebook in some good way, but I then came across the very useful pyfacebook bindings, which, although being a little light on documentation, is a great way to easily throw my photos into Facebook (it's pending the NEW queue in Debian, see #511279).
My fbupload.py script might be a useful starting point if you want to do the same thing. It batches up photos into lots of 60 (the maximum photos in an album) and automatically creates the albums and uploads the photos, reading the IPTC data for comments. The only problem is that you'll have to sign up for a developer key and start a new application to get a secret key to talk to the API (if you're still reading this, I'm sure you can figure it out!).
posted at: Fri, 09 Jan 2009 23:31 | in /code/web | permalink | add comment (6 others)
If you've ever tried to link non-position independent code into a shared library on x86-64, you should have seen a fairly cryptic error about invalid relocations and missing symbols. Hopefully this will clear it up a little!
Let's start with a small program to illustrate.
$ cat function.c
int global = 100;
int function(int i) {
return i + global;
}
$ gcc -c function.c
Firstly, inspect the disassembley of this function:
0000000000000000 <function>: 0: 55 push %rbp 1: 48 89 e5 mov %rsp,%rbp 4: 89 7d fc mov %edi,-0x4(%rbp) 7: 8b 05 00 00 00 00 mov 0x0(%rip),%eax # d <function+0xd> d: 03 45 fc add -0x4(%rbp),%eax 10: c9 leaveq 11: c3 retq
Lets just go through that for clarity:
The IP relative move is really the trick here. We know from the code that it has to move the value of the global variable here. The zero value is simply a place holder - the compiler currently does not determine the required address (i.e. how far away from the instruction pointer the memory holding the global variable is). It leaves behind a relocation -- a note that says to the linker "you should determine the correct address of foo (global in our case), and then patch this bit of the code to point to that addresss (i.e. foo)."
The top portion of the image above gives some idea of how it works. We can examine relocations in binaries with the readelf tool.
$ readelf --relocs ./function.o Relocation section '.rela.text' at offset 0x518 contains 1 entries: Offset Info Type Sym. Value Sym. Name + Addend 000000000009 000800000002 R_X86_64_PC32 0000000000000000 global + fffffffffffffffc
There are many different types of relocations for different situations; the exact rules for different relocation types are described in the ABI documentation for the architecture. The R_X86_64_PC32 relocation is defined as "the base of the section the symbol is within, plus the symbol value, plus the addend". The addend makes it look more tricky than it is; remember that when an instruction is executing the instruction pointer points to the next instruction to be executed. Therefore, to correctly find the data relative to the instruction pointer, we need to subtract the extra. This can be seen more clearly when layed out in a linear fashion (as in the bottom of the above diagram).
If you try and build a shared object (dynamic library) with an object file with this type of relocation, you should get something like:
$ gcc -shared function.c /usr/bin/ld: /tmp/ccQ2ttcT.o: relocation R_X86_64_32 against `a local symbol' can not be used when making a shared object; recompile with -fPIC /tmp/ccQ2ttcT.o: could not read symbols: Bad value collect2: ld returned 1 exit status
The specific problem is how this relocation interacts with Position Independent Code (PIC, enabled with -fPIC). PIC just means that the output binary does not expect to be loaded at a particular base address, but is happy being put anywhere in memory (compare the output of readelf --segments on a binary such as /bin/ls to that of any shared library). This is obviously critical for implementing lazy-loading (i.e. only loaded when required) shared-libraries, where you may have many libraries loaded in essentially any order. Trying to pre-allocate where in memory they would all live is completely impractical and just does not work (not to mention every single library that might ever be used would be competing for a spot in the limited address space of a 32-bit process!).
What's the specific problem with this relocation in a shared library? In a shared library situation, we can not depend on the local value of global actually being the one we want. Consider the following example, where we override the value of global with a LD_PRELOAD library.
$ cat function.c
int global = 100;
int function(int i) {
return i + global;
}
$ gcc -fPIC -shared -o libfunction.so function.c
$ cat preload.c
int global = 200;
$ gcc -shared preload.c -o libpreload.so
$ cat program.c
#include <stdio.h>
int function(int i);
int main(void) {
printf("%d\n", function(10));
}
$ gcc -L. -lfunction program.c -o program
$ LD_LIBRARY_PATH=. ./program
110
$ LD_PRELOAD=libpreload.so LD_LIBRARY_PATH=. ./program
210
If the code in libfunction.so has a fixed offset into its own data section, it will not be able to see the overridden value provided by libpreload.so. This is not the case when building a stand-alone executable, where references are satisfied internally.
Of course, any problem in computer science can be solved with a layer of abstraction, and that is what is done when compiling with -fPIC. To examine this case, let's see what happens with PIC turned on.
$ gcc -fPIC -shared -c function.c $ objdump --disassemble ./function.o ./function.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <function>: 0: 55 push %rbp 1: 48 89 e5 mov %rsp,%rbp 4: 89 7d fc mov %edi,-0x4(%rbp) 7: 48 8b 05 00 00 00 00 mov 0x0(%rip),%rax # e <function+0xe> e: 8b 00 mov (%rax),%eax 10: 03 45 fc add -0x4(%rbp),%eax 13: c9 leaveq 14: c3 retq
It's almost the same! We setup the frame pointer with the first two instructions as before. We push the first argument into memory in the pre-allocated "red-zone" as before. Then, however, we do an IP relative load of an address into rax. Next we de-reference this into eax (e.g. eax = *rax in C) before adding the incoming argument to it and returning.
$ readelf --relocs ./function.o Relocation section '.rela.text' at offset 0x550 contains 1 entries: Offset Info Type Sym. Value Sym. Name + Addend 00000000000a 000800000009 R_X86_64_GOTPCREL 0000000000000000 global + fffffffffffffffc
The magic here is again in the relocations. Notice this time we have a P_X86_64_GOTPCREL relocation. This says "replace the data at offset 0xa with the global offset table (GOT) entry of global.
As shown above, the GOT ensures the abstraction required so symbols can be diverted as expected. Each entry is essentially a pointer to the real data (hence the extra dereference in the code above). Since the GOT is at a fixed offset from the program code, it can use an IP relative address to gain access to the table entries.
This extra reference is obviously slower; however for the most part I imagine the overhead would be essentially immeasurable and is required for "generic" operation. If you have figured the cost of indirection through the GOT is the major bottleneck of your program, I imagine you wouldn't be reading this and would already be considering strategies to remove it!
The next question is why this works on plain old x86-32. Inspecting the code reveals why:
$ objdump --disassemble ./function.o 00000000 <function>: 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: a1 00 00 00 00 mov 0x0,%eax 8: 03 45 08 add 0x8(%ebp),%eax b: 5d pop %ebp c: c3 ret $ readelf --relocs ./function.o Relocation section '.rel.text' at offset 0x2ec contains 1 entries: Offset Info Type Sym.Value Sym. Name 00000004 00000701 R_386_32 00000000 global
We start out the same, with the first two instructions setting up the frame pointer. However, next we load a memory value into eax -- as we can see from the relocation information, the address of global. Next we add the incoming argument from the stack (0x8(%ebp)) to the value in this memory location; implicitly dereferencing it. This provides the abstraction we need -- if the relocation makes the patched address at 0x4 the address of the GOT entry, it will be correctly dereferenced. It is the inability of the x86-32 architecture to try and optimise by doing instruction-pointer relative offseting which means it always needs to do slower memory references, which turns out to be just what you want when you're making a shared library!
So, the executive summary: the ability of x86-64 to use instruction-pointer relative offsetting to data addresses is a nice optimisation, but in a shared-library situation assumptions about the relative location of data are invalid and can not be used. In this case, access to global data (i.e. anything that might be changed around on you) must go through a layer of abstraction, namely the global offset table.
posted at: Wed, 26 Nov 2008 13:53 | in /code/c | permalink | add comment (4 others)
This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.