Airs – Ian Lance Taylor

I gave two talks on Go at the GCC Summit last week. The first was about the gccgo frontend: the IR and the gcc interface; for that one I wrote a paper, which is mostly just a miscellany. The second was a Go tutorial, focusing on the more unusual aspects of the language. The one paper and the two slide presentations can be found on the gcc wiki.

My personal favorite presentation at the Summit was by John Regehr of the University of Utah. He spoke about using random input files to test compilers. This is a standard security technique; the interesting aspect to his work was the effort to generate programs which were well-defined, thus permitting his group to test the optimizers. They were able to generate an astonishing number of compiler crashes and miscompilations in every compiler they tested.

It took me a long time to understand that the const qualifier in C is overloaded. There was no const when I first learned C. It was introduced in the C90 standard. It was copied from C++, although the meaning of const is subtly different in the two languages.

The first meaning of const in C is to use it to qualify a variable definition. If you do that, it means that the variable can not be changed; it is immutable. It can have an initializer but will never have another value. A global or static const variable may be placed in read-only memory.

The second meaning is to use it to qualify a pointer. In this usage it means that the program may not change the value being pointed to by using the pointer. However, it does not mean that that value is immutable, as it may be changed by a different pointer, or by a function call, or by casting away the const qualifier.

The first meaning of const has a real effect on the program. A variable declared const may be compiled differently from a variable which is not declared const. The second meaning of const, on the other hand, is, in effect, compiler-enforced documentation. The compiler will issue an error if an attempt is made to change a value using a const qualified pointer, but declaring such a pointer will not change the generated code.

Although const qualified pointers are just documentation, in practice they are used far more often than const variables. When the C90 standard came out and C compilers started supporting const, programmers spoke of const-poisoning: the feeling that once you use the const qualifier anywhere, it spread throughout your program as it had to be tracked through all assignments and function calls to avoid compiler warnings. Adding const-poisoning to a program does not make it any more correct or reliable. It’s just documentation, albeit documentation that the compiler enforces.

One can imagine a range of different types of documentation which it might be nice to have the compiler enforce. Perhaps it would be useful to know the alignment of a generic pointer, or to know that this char* pointer points to a null terminated string while that one points to a block of arbitrary bytes. A program can use a typedef to indicate the intended meaning of some value, but a pointer to one typedef can be assigned to a pointer to a different typedef with no warning if the underlying types happen to be the same. Why do we get compiler warnings for const pointers but not for typedef pointers? It’s because const was added to the type system, whereas typedef, despite its name, is merely an aliasing mechanism, and is not part of the type system at all.

It did not have to be this way. It would have been possible to make const a storage specifier, like static, rather than a type qualifier. It would have simply meant that the variable was immutable. The address of a const int would have type int * rather than const int *.

The C90 standard introduced one other type qualifier: volatile (in fact, the standard introduced the whole idea of type qualifiers). Unlike const, the standard did not define the meaning of a volatile qualified pointer. The address of a volatile variable has a volatile qualified pointer type, but the standard never said what the compiler should do with such a type. It only says that any access to a volatile variable must be through an lvalue with the volatile qualifier.

The C99 standard adds a third type qualifier, restrict, which is another can of worms.

In retrospect I think that adding the const qualifier to the type system was a mistake. It lets the compiler enforce a specific type of documentation but doesn’t let the program define the types of documentation that it cares about. The documentation is not reliable as programs can cast away the qualifier, and indeed the standard requires basic functions like strchr to do exactly that.

If you want the compiler to be able to check type attributes, then give the language a way to define the attributes that matter to a particular program. If you want to compiler to be able to put a variable in a specific type of storage, such as a read-only data section, then use a storage specifier. There is no need to mix the two ideas.

I recently added support for STT_GNU_IFUNC to gold.

As you can tell by the name, STT_GNU_IFUNC is a GNU specific ELF symbol type. It is defined in the range reserved for operating system specific types. A symbol with type STT_GNU_IFUNC is a function, but the symbol does not provide the address of the function as usual. Instead, the symbol provides the address of a function which returns a pointer to the actual function. The idea is that this lets a program use a version of a function which is customized for a particular system. A typical example would be memcpy; the program would choose a version of memcpy optimized for the current CPU. This is in fact what happens in the mainline version of glibc.

STT_GNU_IFUNC is implemented with a little bit of support in the compiler and assembler, basically just enough to set the symbol type. The rest of the implementation is in the linker and the dynamic linker. Here I’ll discuss the support required in the linker.

An STT_GNU_IFUNC symbol always uses a PLT entry, and all references to the symbol go through the PLT. This is true even for a local symbol, although local symbols normally do not require PLT entries. The PLT entry will refer to a GOT entry as usual. The GOT entry will be given an IRELATIVE reloc (a new reloc type) rather than the usual JUMP_SLOT reloc. For a normal PLT entry the GOT entry is initialized to point to the PLT entry, in a way that causes the PLT entry to initialize itself the first time it is called. For an STT_GNU_IFUNC PLT entry, the GOT entry instead points to the symbol’s value, which is the function to call to get the real function address.

Normally, when we need a GOT entry for a function because position independent code takes its address, and we know the value of the function because we are, say, linking the executable, we can set the GOT entry to the value of the symbol. But for an STT_GNU_IFUNC symbol, that would mean that calling the function pointer would return the function to call, rather than calling the actual function. So instead we set the GOT entry to point to the offset in the PLT.

When a global or static variable in a position independent executable is initialized to the address of a local function, we would normally use a RELATIVE reloc. For an STT_GNU_IFUNC symbol, we instead use an IRELATIVE reloc. That will match the address seen in a shared library.

A statically linked executable normally does not have any dynamic relocs. In order to make the IRELATIVE relocs work in a static executable, they are grouped together with symbols to mark the begin and end of the group. The glibc startup code then uses those symbols to resolve all IRELATIVE relocs when the program starts. The symbols are __rel_iplt_start and __rel_iplt_end. For a target which uses SHT_RELA relocs, the symbol names use rela instead of rel.

That is pretty much it for the linker support.

Ideally this would permit STT_GNU_IFUNC symbols to be initialized lazily: the first time the function is called, the PLT entry would jump to the function which returns the real function address to use, and that would be stored into the corresponding GOT entry for future calls through the PLT. However, there is no code there to actually update the PLT entry. Normal PLT initialization calls into the dynamic linker; this process would not. It might be possible to make this work, but the current glibc dynamic linker does not try. Instead, all the IRELATIVE relocs are processed when the program starts up, even if they are in the set of relocs which are normally resolved lazily.

That is all a bit of pain, but overall it’s not too hard to implement. Is it really worth it? Calling an STT_GNU_IFUNC function will jump to the PLT entry, which will load a value from the GOT and jump to it. On x86 this is a single jump indirect instruction. For the CPU this requires loading the jump indirection instruction, loading the actual address, and executing the jump.

An alternative to all this linker stuff would be a variable holding a function pointer. The function could then be written in assembler to do the indirect jump. The variable would be initialized at program startup time. The efficiency would be the same. The address of the function would be the address of the indirect jump, so function pointers would compare consistently. Of course it wouldn’t be quite so automatic, but on the other hand it wouldn’t require special support in the compiler, assembler, linker, and dynamic linker. I’m not sure why that approach was not taken. There may be a good reason.

It’s a frequent observation that computing has oscillated between centralized and distributed. We’ve gone from centralized computing facilities (which were effectively single-user, but only the administrators could use them) to time-sharing to personal computers to server farms. Data has moved from the card deck you kept in your office to the tape deck at the computer center to the hard disk on your personal computer to the hard disk on a centralized server to a cloud site like Flickr. E-mail has moved from a mailbox on a timesharing system to your personal computer to a cloud site like GMail. People increasingly access data from their phones, but the data is stored in the cloud.

Right now we are clearly in a distributed trend. Data is increasingly stored in the cloud and accessed from a variety of devices. People shift from phones to laptops to desktops and expect to see the same list of contacts, the same e-mail, the same calendar. The cloud sites are an extreme version of centralization: millions of users store their data in the same place. What will the computing world look like when and if it oscillates back to a more distributed system?

One possibility is that people will increasingly acquire their own data storage which will be accessible over the net. They’ll keep small cheap redundant servers to hold their data. They’ll have one server at home and one at the office, and they will automatically sync up. Access will be very fast most of the time, and will be possible at over times. The servers will be updated automatically and so forth, and they will (somehow) be easy to administer. The advantage will be fast access to data most of the time and actual control over your data. If you want to delete something, it’s gone, and not available for resurrection.

That particular vision is easy for me to think of because it’s similar to our ideas when I co-founded a company, Zembu, back in 1998. I don’t know how compelling it is. I suspect that going back to a distributed environment will require some cost advantage, and I’m not sure I see that here. Much of cloud computing these days tends to be free, in the sense that advertising pays the bills. Few people will spend money to avoid ads. Few is more than zero, but it’s not enough to build a business on.

During any predominant paradigm it’s difficult to see what the next paradigm will be. History suggests that we will oscillate back, that the cloud will condense at some point. But history is not always right. It seems inherently unlikely to me that data will increasingly be centralized. But I don’t know what the alternative will look like.

I’ve always found it easy to deal with machines, as I expect is true of most computer programmers. The interface to a machine is not always logical, but it is normally consistent in the sense that it always behaves the same way given the same inputs, and it is normally unambiguous in the sense that it either works or it doesn’t, and it is clear which state is which. At lest for me, dealing with machines is simpler than dealing with people when things go wrong—machines may be frustrating but at least they’re frustrating for relatively simple and ultimately comprehensible reasons.

Unfortunately, I’ve started to notice that as programs get smarter and as interface designers get more clever, machines are becoming more like people. Interfaces for web sites and phones are increasingly adjusting based on your past interactions. In many ways this is good, as over time the interaction gets smoother and easier. However, it means that there is a lack of consistency: an input today does not produce the same effect as the same input did yesterday. It also means that there is an increase in ambiguity: it’s difficult to tell the difference between working correctly and being slightly broken.

In effect, the computing world is becoming increasingly tuned for people who prefer dealing with people rather than people who prefer dealing with machines. On average this is of course a good thing, as most of the population seems to find it frustrating to deal with machines. But it’s somewhat ironic considering that the programmers doing most of the work tend to be people who prefer dealing with machines.

I don’t want to give up the advantages I get when things go well, so I guess I’m stuck in an increasingly inconsistent and ambiguous world.