LWN: Comments on "Striking gold in binutils"

A ToC of the 20 part linker essay

nix — Thu, 26 Sep 2013 17:03:21 +0000

Neat! I'll be using it, certainly.

A ToC of the 20 part linker essay

cataliniacob — Mon, 23 Sep 2013 19:00:42 +0000

It's 5 years later but maybe some people still find this.

Here's a Calibre recipe that creates an e-book from the whole series:
https://github.com/cataliniacob/calibre-recipes/blob/mast...

To use it run ebook-convert ian-taylor-linker.recipe linkers.epub

Thanks to JesseW and ncm for the tips to read it.

whatever

happyaron — Fri, 26 Nov 2010 10:25:52 +0000

Well, great!

A ToC of the 20 part linker essay

nix — Mon, 07 Apr 2008 14:37:11 +0000

I do like the idea of performing it. A public reading of a table of 
contents!

I bet it'll be popular ;)

A ToC of the 20 part linker essay

JesseW — Mon, 07 Apr 2008 06:28:16 +0000

Since I couldn't find any well-linked ToC of Ian's 20-part essay on linkers either on his blog, or here, I decided to post one. (And yes, I know the post URLs are consecutive numbers; nevertheless...)

I compiled the titles mainly from Ian's section titles, as Ian just referred to the parts by number.

And now, the author of gold, Ian Lance Taylor's 20 part Linker posts...

I release this message (the ToC and comments) into the public domain, no right reserved. Use it, copy it, perform it, create derivative works with no restrictions and without any further permission from me.

C++ new and delete

pr1268 — Mon, 07 Apr 2008 00:49:04 +0000

how do you dynamically allocate/deallocate memory?

A big push for "modern" C++ programming is to use the standard library's container classes, e.g., vector, list, deque, etc. instead of arrays created with new and delete.

The primary rationale for using dynamically-allocated memory in the first place is to defer until execution time reserving only as much space as is needed (since memory is a scarce resource). The C++ containers have a rich set of methods which allow array-like operation while managing the dynamic allocation (and subsequent releasing) of resources at the library level (instead of making the programmer do it him/herself with new and delete).

I can't speak for why virtual methods are seldom described in literature, but my intuitive perception is that they're this philosophical concept in computer science (object-oriented programming in particular) whose existence programmers are expected to know but avoid using unless no other practical solution exists--kind of like recursion.

Who uses COFF?

anton — Sat, 05 Apr 2008 14:22:08 +0000

Last I looked, Windows and Tru64 Unix (possibly also other proprietary Unices).

Striking gold in binutils

nix — Thu, 03 Apr 2008 20:31:45 +0000

IF you would do such a thing, you would understand that on a 64-bit platform we are actually booting a 32bit binary

Actually, the only things that differ between the elf_x86-64 and elf_i386 emulations are details of the GOT and PLT (which don't exist for the kernel normally), details of relocation processing (which isn't carried out for the kernel), and the start address (which the kernel overrides anyway in its custom linker script). So since they do the same thing as far as the kernel's concerned, let's pick the one that everyone's got because it's present even in older x86 binutils and always present in newer ones, and that's elf_i386.

(At least that's my understanding.)

where vmlinux.bin is created by running a custom tool called objcopy :

Not only is objcopy not a 'custom' tool, but part of the GNU binutils, but it predates Linux (although before about 1993 it was called 'copy'). (The renaming was done by, oh look, Ian Lance Taylor. He's been involved in this area for a long, long time. ;} )

(The objcopy run is anyway hardly crucial: like most of the stuff before the final link, it's just a size optimization.)

Striking gold in binutils

stock — Thu, 03 Apr 2008 19:03:36 +0000

" Digging the commands out of the makefile by hand is madness."  
  
You bet, but IF you would do such a thing, you would understand that on a  
64-bit platform we are actually booting a 32bit binary :  
  
ld -m elf_i386  -Ttext 0x100000 |\  
        -e startup_32 -m elf_i386 |\  
        arch/x86_64/boot/compressed/head.o |\  
        arch/x86_64/boot/compressed/misc.o |\  
        arch/x86_64/boot/compressed/piggy.o |\  
        -o arch/x86_64/boot/compressed/vmlinux  
  
Apparently we are actually booting a 32bit binary on our x86_64 platform.  
But that doesn't matter as long as we call our real kernel piggy.o :  
  
ld -m elf_i386  -r --format binary --oformat elf32-i386 |\  
        -T arch/x86_64/boot/compressed/vmlinux.scr |\  
        arch/x86_64/boot/compressed/vmlinux.bin.gz |\  
        -o arch/x86_64/boot/compressed/piggy.o  
  
where vmlinux.bin.gz is created by the following command :  
  
gzip -f -9 < arch/x86_64/boot/compressed/vmlinux.bin > |\  
        arch/x86_64/boot/compressed/vmlinux.bin.gz  
  
where vmlinux.bin is created by running a custom tool called objcopy :  
  
objcopy -O binary -R .note -R .comment -S  vmlinux |\  
         arch/x86_64/boot/compressed/vmlinux.bin  
  
where finally vmlinux is that ELF 64-bit LSB executable :  
  
ld -m elf_x86_64 -e stext -T arch/x86_64/kernel/vmlinux.lds.s |\  
     arch/x86_64/kernel/head.o arch/x86_64/kernel/head64.o |\  
     arch/x86_64/kernel/init_task.o   init/built-in.o |\  
     --start-group  usr/built-in.o  arch/x86_64/kernel/built-in.o |\  
     arch/x86_64/mm/built-in.o  arch/x86_64/ia32/built-in.o |\  
     kernel/built-in.o  mm/built-in.o  fs/built-in.o  ipc/built-in.o |\  
     security/built-in.o  crypto/built-in.o  lib/lib.a |\  
     arch/x86_64/lib/lib.a  lib/built-in.o  arch/x86_64/lib/built-in.o |\  
     drivers/built-in.o  sound/built-in.o  arch/x86_64/pci/built-in.o |\  
     net/built-in.o --end-group .tmp_kallsyms2.o -o vmlinux  
  
   -rwxr-xr-x  1 root root 7478601 Nov 21 14:48 vmlinux  
  
   vmlinux: ELF 64-bit LSB executable, AMD x86-64, version 1 (SYSV),  
            statically linked, not stripped  
  
Cheers,  
  
Robert  
--   
Robert M. Stockmann - RHCE  
Network Engineer - UNIX/Linux Specialist  
crashrecovery.org  stock@stokkie.net

Making up falsehoods

jchrist — Thu, 03 Apr 2008 18:05:54 +0000

I'm genuinely curious.  If "modern C++" programs don't use new/delete or virtual, how do you
dynamically allocate/deallocate memory?  What do you use instead of virtual functions?

Being dismissive of another's work

lysse — Thu, 03 Apr 2008 03:42:17 +0000

Doing without is a subclass of doing it yourself.

You missed the point, again.

nix — Wed, 02 Apr 2008 19:51:56 +0000

Ah, the last refuge of the erroneous.

Sorry, the onus is on *you*: you're the one making the exaggerated claims.

You missed the point, again.

sylware — Wed, 02 Apr 2008 17:56:51 +0000

You are missing the point full throttle, reread my posts.

The metric is SPEED not just easier development

dvdeug — Wed, 02 Apr 2008 11:12:49 +0000

Java the programming language doesn't use a virtual machine any more than C does. It happens
to usually be implemented using a virtual machine, but there are native compilers, like gcj.
Furthermore, the coding matters a lot more than the language, and the language can frequently
simplify the coding.

Striking gold in binutils

nix — Wed, 02 Apr 2008 08:34:13 +0000

I am not worthy. ;}

Striking gold in binutils

ncm — Wed, 02 Apr 2008 06:51:16 +0000

Oh, and consider yourself vaporized.

Use of assert

pr1268 — Mon, 31 Mar 2008 21:05:16 +0000

Well, I had to level the playing field somewhat since Java forces me to put all that code in a try/catch block...

But yeah, I generally do what you recommend in C/C++.

I see I have to be more explicit

ncm — Mon, 31 Mar 2008 02:51:16 +0000

Ignorance is a poor basis for criticism.  If you don't understand the purpose for any given
feature, you will be ill-equipped to evaluate the benefits available from using it.

By all means avoid C++ if you like.  Most programmers are not intelligent enough to use the
language effectively, and should stick to solving easy problems with trivial languages, and
leave the hard work to professionals.

A bit premature

nix — Mon, 31 Mar 2008 00:12:48 +0000

Er, most GNU software has had better manpages than that for many years 
(derived automatically from the texinfo, just as the info is).

A bit premature

AJWM — Sun, 30 Mar 2008 21:40:36 +0000

>> This is a far cry from a replacement for GNU ld which links dozens of
>> processors' code in at least a half dozen different file formats.

>1) Isn't the unix way "do one thing and do it well"?

Yes, but remember, GNU's Not Unix.  While it's often an improvement, it does have some
idiosyncrasies that drive me crazy (like the insistance on having man pages that basically say
'see the info document', for example).

Use of assert

pjm — Sun, 30 Mar 2008 04:53:51 +0000

Incidentally, please don't use or encourage use of assert for checking for I/O errors or
other can-happen runtime conditions.  Such checks will disappear when compiled with -DNDEBUG
(or conversely make it impractical to compile with -DNDEBUG, thus discouraging use of
assertions), and fail to give a meaningful error message.  That should be if (!in_file) {
perror("foo.txt"); exit(EXIT_FAILURE); }.

Striking gold in binutils

nix — Sat, 29 Mar 2008 13:44:17 +0000

Your comment belongs on slashdot, not here. Let's see how many falsehoods 
I can eliminate before ncm gets here and vapourises you.

Firstly, your 'old diehard UNIX men' are clueless. GCC relied on a lot of 
ad-hoc algorithms at one point: that did not make it a 'total shit of 
banana republic code' by any standard. G++ was one of the first C++ 
compilers written, I think the first that did not emit C code: so it 
certainly wasn't of 'utter inferior quality' then. GCC as a whole went 
through a bad patch in the early-to-mid-90s, when maintenance largely 
stalled: but once egcs started (has it been ten years already?) G++ was 
one of the first parts to improve.

It's definitely not 'utterly inferior' now, in fact it's one of the better 
compilers out there, with an internal architecture that's gone from being 
crufty as anything and full of hidden dependencies to being, well, much 
less crufty over the last few years (cleaning up code that old is an 
achievement).

Its only remaining hole is optimization: especially on machines with small 
register files, vendor compilers could often out-optimize it. This, too, 
is steadily being fixed.

Introducing a new linker, no matter how hotshot (and gold *is* a damn good 
piece of work) doesn't make the *compiler* better or worse in any way. I 
can't fathom the misunderstandings that could lead you to believe that 
switching linkers depending on the source language in use has any merit at 
all. The most integration that is likely to happen seems to be to have the 
linker running in parallel with the compiler, accepting object code and 
incrementally linking it as the compiler disgorges it. Anything more than 
that seems pointless.

Makefiles are the wrong place to solve linker script problems. The problem 
is that GNU ld was fundamentally driven by linker scripts, and gold is not 
(as well as that the Linux kernel constructs some seriously contorted ELF 
files: OS kernels don't have to stick to the rules: they are generally 
loaded by special-purpose code, not by ELF loaders).

The obvious way to see what commands are executed when running make is to 
use 'make -n', but if some of the commands are themselves makes you'll 
need to do something else. It's probably simplest just to add a couple of 
printf()s to make itself, or strace the whole thing with "-ff -e 
trace=process". Digging the commands out of the makefile by hand is 
madness.

finite state machines

man_ls — Sat, 29 Mar 2008 12:39:25 +0000

Oops, you are right: FSMs are indeed easier to implement in those languages. My big mouth again.

They are still pretty hard to follow and understand. Which is of course the concern of the author of gold. But maybe even this can be alleviated with functional programming; on the 7th Antual ICFP Programming Contest functional languages were shown to be an order of magnitude better at writing input for FSMs than imperative languages. I'm not so sure any longer.

So thanks for the clarification, and please disregard my earlier uninformed comment about a red herring.

Striking gold in binutils

stock — Sat, 29 Mar 2008 10:52:59 +0000

hehe what a gas, I have been told by the real old diehard UNIX men that  
gcc was a total shit of banana republic code, as its C++ part was of  
utter inferior quality. With the arrival of Ian's gold linker gcc as a  
C/C++ package has finally moved up in the ranks. 
 
And it was about time also, as the impact of open source and the 
obliged use of gcc made many people puke. Now instead of naming it   
gold, integrate it properly inside the gcc "compilersuite" and make it  
use by default when compiling c++ code. But that's where the problem  
is, as many source trees are hybrid code of .c and .cpp files. 
 
As to linker problem when compiling Linux vmlinux kernels, i like to 
suggest that Torvalds et.al. could solve this inside their "Makefile"  
of the Linux kernel source tree. Some time ago i wanted to checkout how  
a vmlinuz binary actually was created by doing every command by hand.  
It took me more as two days to distillate the commands by hand from the  
various Kbuild and related patch works and custom utils. 
 
Robert 
--  
Robert M. Stockmann - RHCE 
Network Engineer - UNIX/Linux Specialist 
crashrecovery.org  stock@stokkie.net

Algorithm Complexity

pkolloch — Sat, 29 Mar 2008 08:16:02 +0000

That's funny. For me a factor of five actually suggests that the implementation quality has
substantially increased but not the algorithm. 

If you had a different algorithmic complexity, you should be able to find larger examples with
a larger factor.

Maybe that's the case but the "factor five" statement would not tell you that.

Making up falsehoods

ncm — Sat, 29 Mar 2008 07:56:16 +0000

It's no crime not to like any particular language.  (Lord knows I loathe my share of them.)
When you have to invent one falsehood after another to justify your dislike, though, it makes
you look silly, or dishonest.  I know of plenty to dislike in C++; they tend to be
inconveniences in features entirely lacking in other languages.

But, for the record...  Lexical scoping, we have.  Tail recursion?  Pass; over twenty-five
years using C and C++, every time I have been tempted to leave a tail recursion in my code,
changing it to explicit looping has turned out to make the code clearer and more maintainable.
(Certainly there are languages that do or would benefit from it, but C and C++ seem not to
need it.)  Nested "methods"? Coming, more or less, in C++09.  Also coming are mutexes and
atomics, but more important is that they can be built into whatever higher-level apparatus you
prefer.

The great lesson of C was that anything you can build into a library, you are better off
without in the core language.  (For C, particularly, that was I/O.  People miss how
revolutionary that was thought, then.)  C++09 adds enormous power for library writers, to
enable easier-to-use libraries, which will in turn make the language markedly more competitive
against scripting languages.

finite state machines

salimma — Sat, 29 Mar 2008 07:30:33 +0000

FSMs are trivial in languages with tail-call optimization (Lisp et. al., ML, Haskell .. even
Lua!). It is true, though, that most of these languages are not geared towards low-level bit
manipulation.

C--, perhaps. It's a C-like language used by the Haskell team as their intermediate language,
a sort of souped-up assembler.

I see I have to be more explicit

felixfix — Sat, 29 Mar 2008 07:21:26 +0000

You all seem to be concentrating on the limbs of the trees I mentioned, ignoring the entire
forest.

I know perfectly well why C++ has all those warts, speed. But languages progress by more than
merely adding hundreds of new steam gauges (to use a quaint hardware engineers' term) to an
engine to allow ever finer control of it. Anyone who is familiar with radial engines, those
wonderful noisy big round engines on WW II planes, will understand my comparison of C as the
R2800 and C++ as the Wright 3350 (hope I got that "right") which was the complex culmination
of radial engine technology. What was needed was not such a finicky beast but a new way of
thinking, the jet engine, especially augmented with a glass cockpit which only shows you those
instrument readings you need to know, such as only engine temps which are out of spec.

C++ is horrible because it added complexity without benefit. It has all the hallmarks of
kluge piled on top of kluge, patched and held together by duct tape. 3 times as many malloc
call pairs and the additional trap of mixing them up? I doubt C++ gained triple the benefit,
and to say that the compiler, even while knowing the types, could not choose the right calls
based on type, beggars the imagination. I would be embarrassed to rely on such a sorry excuse
for an excuse. If virtual should only be used when absolutely necessary, then it was designed
wrongly.

That is what I was complaining about, not the rationale for each additional complication. All
these complicated additional features screamed loud and clear that the basic design was flawed
beyond redemption; it's too bad no one was brave enough to say the emperor's clothes were
darned to nothingness. That is why C++ disgusts me and I avoid it like the plague.

finite state machines

man_ls — Sat, 29 Mar 2008 01:33:31 +0000

Not that I know of. Finite state machines are actually hard to code and read in any language, so your argument (C++ somehow made gold more difficult) sounds like a red herring to me.

Oddly enough, it seems this is an area where graphical programming should help: state diagrams (or flowcharts) can really help you understand a state machine. But apart from some of the new BPM tooling, which covers a similar but different problem space, that idea hasn't flown either.

A bit premature

nix — Fri, 28 Mar 2008 22:43:24 +0000

GNU ld *does* only one thing: it links. It doesn't actually know much 
about object file formats (as you doubtless know, that job is left to 
libbfd).

ld's real problem is *age*: its design predates ELF, and it shows. Its 
design meshes quite well with COFF, but who uses that naymore?

(And I use the ihex ld target on a fairly regular basis. Maybe there are 
other ways to do the same thing, but it works for me...)

Being dismissive of another's work

nix — Fri, 28 Mar 2008 22:30:28 +0000

Doing without a linker? Neat trick! ;}

You missed the point

nix — Fri, 28 Mar 2008 22:25:54 +0000

Yes. It's not separate from the *Objective C* parser.

(The similarity is that, like the C++ parser, the C parser has now made 
the transition from bison to a hand-rolled parser.)

The famous "./configure; make" - my custom version

nix — Fri, 28 Mar 2008 22:22:40 +0000

chown your build tree to the unprivileged user, build as normal, `make 
install' as root or (if you're paranoid) use `fakeroot' or some similar 
package to install and then deal with the resulting miniature root tree 
using GNU stow or something similar.

(Rarely (very rarely) one encounters packages that write stuff to the 
build tree during the `make install' process, so you might need to be root 
to *remove* it if you chose to do the final installation as root.)

Striking gold in binutils

nix — Fri, 28 Mar 2008 21:27:49 +0000

I need to rebuild it to add back a non DT_GNU_HASH :)

Since WHEN?

nix — Fri, 28 Mar 2008 21:26:38 +0000

I think I need to profile this, then, because exception frames should be 
very nearly free to set up and (non-throw) tear down, certainly not as 
expensive as 15%. This wasn't on an sjlj target, was it? 'cos they're *so* 
last millennium.

You missed the point too

landley — Fri, 28 Mar 2008 17:20:39 +0000

Actually, I'm working on making tinycc (a project derived from tcc) compile the rest of the
stack, including the kernel.  I have rather a lot of work left to do, of course. :)

http://landley.net/code/tinycc

I find gold interesting, but not useful in my case because tinycc's linker is built-in.  (I'm
reorganizing the code to work as a "swiss army knife" executable ala busybox, but that's not
in -pre2.  Maybe -pre3.)

As for the kernel, the linux-tiny project is working on getting that more modular so we need
to select less of it...

Rob

Striking gold in binutils

landley — Fri, 28 Mar 2008 16:26:19 +0000

A friend of mine who still bothers with C++ explained to me once how C++ compilers used to use
a linker optimization where the name mangling would put the innermost identifiers first, and
the outermost identifiers last.  That way if you had these two symbols:

class1.class2.class3.class4.member1
class1.class2.class3.class4.member2

By comparing "member1" vs "member2" first, your string match would figure out inequality
faster.  If you go the other way, your string matches have to go through lots of common
namespace for every symbol before coming to the unique parts, and with BigLongMixedCaseNames
this can get fairly ridiculous.

Now, which way did the Intel Itanium C++ spec specify that name mangling had to occur?  The
long way that links slowly, of course.  And everybody else picked up the Itanium C++ spec
because nobody else bothered to write up a standard for this part of the language.

A bit premature

landley — Fri, 28 Mar 2008 16:20:04 +0000

> This is a far cry from a replacement for GNU ld which links dozens of
> processors' code in at least a half dozen different file formats.

1) Isn't the unix way "do one thing and do it well"?

2) Shouldn't Linux Weekly News be most interested in the tools and formats used by _Linux_?
(Is it still interesting to have an ld mode to produce a.out code?  I tried to produce a static
a.out binary with gcc 4.1.2 and couldn't figure out how in the first hour of trying, and
google didn't pull anything up either.  How interesting is the ability to produce other binary
formats last used by discontinued Hewlett Packard minicomputers from 1986?)

3) The way "binflat" files is created is to make an ELF file, then have a second tool produce
a second file from the ELF file.  Same for the kernel producing zImage files from the ELF
format vmlinux.

Much of what GNU ld is doing may not actually actually a good idea...

Ruby

alkandratsenka — Fri, 28 Mar 2008 16:08:47 +0000

Reading whole file in memory just to parse int from it's first line is very funny :)

You'll need a longer version like this

(File.open('foo.txt') {|f| f.readline}).to_i rescue deadParrot

The famous "./configure; make" - my custom version

DonDiego — Fri, 28 Mar 2008 13:47:26 +0000

The code needs not be intentionally malicious.  Just imagine that a Makefile contains a line
like

  rm -rf $(VARIABLE)/path/to/somewhere

Now if $(VARIABLE) happens to be empty (perhaps only in your nonstandard configuration and not
on the developer's machine), pray that there is nothing important below /path/to/somewhere ...

That's just a simple example, it's easy to come up with more.  It's not so much about
protection against malice, but protection against accidents.  Accidents do happen, it's a fact
of life.  If you want to drive without a seatbelt, all I can wish you is good luck...