Archive for March, 2008

Apocalypse Now

We’re a bit busy with a slow motion move, so my postings may be less frequent than usual.

It’s fairly common for people to say that the future world will be a terrible place for one reason or another. I wonder to what extent that has already happened. The world today is radically and completely different from the world of 150 years ago. Nobody back then would have predicted suburban sprawl or the extent to which we’ve paved the earth. We live a lot longer, but our food has become homogenized and much of it would have been unrecognizable back then. Are we already living in the future apocalypse?

Perhaps a better way to get at this is the notion popular with some SF writers of the singularity. As I’ve written before I don’t find the idea to be very likely. But perhaps one way to describe the singularity is the point in time beyond which life becomes unpredictable and perhaps incomprehensible. By that definition, I think the singularity happened early in the 20th century. Don’t expect some remarkable singularity to happen in the future–it already happened in the past.

Comments (5)

Future Transportation

Barring some remarkable change in the world, we are going run out of oil in my lifetime. I don’t mean that we will literally run out of oil; I mean that it will become too expensive to use for ordinary tasks such as selling it in the form of gasoline for cars. There seem to be a number of alternative for cars, ranging from batteries to biofuel to liquified natural gas. So cars in the future will most likely continue to exist in much the same form they have now, perhaps somewhat smaller and lighter and with less range but not radically different.

What I wonder is whether there is a good alternative for jet fuel. We in the western world have become accustomed to relatively casual flying. We can get to any part of the world we care to go to, by simply hopping on a plane. When jet fuel is no longer easily available, will we lose that ability? Will flying become restricted to the very rich or very important?

In many ways that might be a good thing, making the world larger again after it has spent so many years becoming smaller. In many other ways, of course, it would be a bad thing. Every time I fly with my daughter I wonder how often she will be able to fly when she is an adult.

Comments (12)

GCC Exception Frames

When an exception is thrown in C++ and caught by one of the calling functions, the supporting libraries need to unwind the stack. With gcc this is done using a variant of DWARF debugging information. The unwind information is loaded at runtime, but is not read unless an exception is thrown. That means that the unwind library needs to have some way of finding the appropriate unwind information at runtime.

On some systems, this is done by registering the exception frame information when the program starts. The registration is done with a variant of the handling of C++ constructors. This becomes interesting when one shared library can throw an exception which is caught by another shared library. It is possible for such a case to arise when the executable itself never throws exceptions and therefore has no frames to register. Obviously the unwinder needs to be able to find the unwind information for both shared libraries, which means that both shared libraries need to use the same registration functions. With gcc this is normally ensured by putting the unwind code in a shared library, libgcc_s.so. Each shared library, and sometimes the executable, will use libgcc_s.so. That ensures a single copy of the registration and unwind functions, so the library will be able to reliably unwind across shared libraries. With gcc the use of libgcc_s.so can be controlled with the -shared-libgcc and -static-libgcc options. Normally the right thing will happen by default.

That approach has a cost: there is an extra shared library, and there is a small cost of registering the unwind information at program startup or library load time (and unregistering it if a shared library is unloaded via dlclose). There is now a better way, which requires linker support.

Both gold and the GNU linker support the command line option --eh-frame-hdr. With this option, when the linker sees the .eh_frame sections used to hold the unwind information, it automatically builds a header. This header is a sorted array mapping program counter addresses to unwind information. The header is recorded as a program segment of type PT_GNU_EH_FRAME. (This is a little bit ugly since the .eh_frame sections are recognized only by name; ideally they should have a special section type.)

At runtime, the unwind library can use the dl_iterate_phdr function to find the program segments of the executable and all currently loaded shared libraries. It can use that to find the PT_GNU_EH_FRAME segments, and use the sorted array in those segments to quickly find the unwind information.

This approach means that no registration functions are required. It also means that it is not necessary to have a single shared library, since dl_iterate_phdr is available no matter which shared library throws the exception.

This all only works if you have a linker which supports generating PT_GNU_EH_FRAME sections, if all the shared libraries and the executable are linked by such a linker, and if you have a working dl_iterate_phdr function in your C library or dynamic linker. I think that pretty much restricts this approach to GNU/Linux and possibly other free operating systems. For those scenarios, I hope that gcc will soon be able to stop using libgcc_s.so by default.

Comments (2)

Concurrent linking

There is still work to do on gold. But once that is done, what is the next big step? In the long term we need an incremental linker, but I’m also interested in an idea which I call concurrent linking. A concurrent linker runs at the same time as the compiler. As each object file is compiled, the linker is notified, and the linker adds the object file to the executable that it is building. When the last compilation is completed, the linker writes out the fully linked executable.

The idea is to keep the linker from being a serializing step in a compilation. It is normally easy to run many compilations in parallel, as each compilation is independent. Traditionally, however, the linker can not start until all the compilations are complete, and it must read all the input files at that time.

A concurrent linker can instead run at the same time as the compilations. There is no long wait after the compilations are complete. Also, the newly generated object file should be in the disk cache, and so the linker will have to do less actual disk I/O. I expect that this would only be a noticeable improvement for large programs, but then those are the cases where the linker really is a bottleneck.

The key to making this work will be careful control of the symbol table, and efficient tracking of relocations. In general relocations for an object file may only be resolved when they refer to symbols defined in objects which appear on the link command line. In other cases we must remember the relocation. If the symbol is already known to be defined in an object which appears later on the link line, it would probably be appropriate to resolve the relocation to that symbol, but to record it in case the symbol definition is changed later.

In general an executable linked in this way may have additional text and data segments, and they won’t be as tightly packed. Thus the resulting executable will most likely have slightly worse paging behaviour and will run slightly slower. So this technique is only appropriate during the development cycle, not during a release build.

Comments (15)

Gold Released

I have finally released gold, the new ELF linker I’ve been working on, to the free software world. It is now part of the GNU binutils. I sent an announcement to the binutils mailing list.

Comments (6)

« Previous entries Next Page » Next Page »