Archive for August, 2007

Linkers part 1

I’ve been working on and off on a new linker. To my surprise, I’ve discovered in talking about this that some people, even some computer programmers, are unfamiliar with the details of the linking process. I’ve decided to write some notes about linkers, with the goal of producing an essay similar to my existing one about the GNU configure and build system.

As I only have the time to write one thing a day, I’m going to do this on my blog over time, and gather the final essay together later. I believe that I may be up to five readers, and I hope y’all will accept this digression into stuff that matters. I will return to random philosophizing and minding other people’s business soon enough.

A Personal Introduction

Who am I to write about linkers?

I wrote my first linker back in 1988, for the AMOS operating system which ran on Alpha Micro systems. (If you don’t understand the following description, don’t worry; all will be explained below). I used a single global database to register all symbols. Object files were checked into the database after they had been compiled. The link process mainly required identifying the object file holding the main function. Other objects files were pulled in by reference. I reverse engineered the object file format, which was undocumented but quite simple. The goal of all this was speed, and indeed this linker was much faster than the system one, mainly because of the speed of the database.

I wrote my second linker in 1993 and 1994. This linker was designed and prototyped by Steve Chamberlain while we both worked at Cygnus Support (later Cygnus Solutions, later part of Red Hat). This was a complete reimplementation of the BFD based linker which Steve had written a couple of years before. The primary target was a.out and COFF. Again the goal was speed, especially compared to the original BFD based linker. On SunOS 4 this linker was almost as fast as running the cat program on the input .o files.

The linker I am now working, called gold, on will be my third. It is exclusively an ELF linker. Once again, the goal is speed, in this case being faster than my second linker. That linker has been significantly slowed down over the years by adding support for ELF and for shared libraries. This support was patched in rather than being designed in. Future plans for the new linker include support for incremental linking–which is another way of increasing speed.

There is an obvious pattern here: everybody wants linkers to be faster. This is because the job which a linker does is uninteresting. The linker is a speed bump for a developer, a process which takes a relatively long time but adds no real value. So why do we have linkers at all? That brings us to our next topic.

A Technical Introduction

What does a linker do?

It’s simple: a linker converts object files into executables and shared libraries. Let’s look at what that means. For cases where a linker is used, the software development process consists of writing program code in some language: e.g., C or C++ or Fortran (but typically not Java, as Java normally works differently, using a loader rather than a linker). A compiler translates this program code, which is human readable text, into into another form of human readable text known as assembly code. Assembly code is a readable form of the machine language which the computer can execute directly. An assembler is used to turn this assembly code into an object file. For completeness, I’ll note that some compilers include an assembler internally, and produce an object file directly. Either way, this is where things get interesting.

In the old days, when dinosaurs roamed the data centers, many programs were complete in themselves. In those days there was generally no compiler–people wrote directly in assembly code–and the assembler actually generated an executable file which the machine could execute directly. As languages liked Fortran and Cobol started to appear, people began to think in terms of libraries of subroutines, which meant that there had to be some way to run the assembler at two different times, and combine the output into a single executable file. This required the assembler to generate a different type of output, which became known as an object file (I have no idea where this name came from). And a new program was required to combine different object files together into a single executable. This new program became known as the linker (the source of this name should be obvious).

Linkers still do the same job today. In the decades that followed, one new feature has been added: shared libraries.

More tomorrow.

Comments (22)

The Morality of Government

Governments are formed when a group of people gathers together, either freely or by force, and lives together in a community with a shared set of laws. The government is the entity which creates and enforces the laws. What is the moral grounding of the government?

In the old days in Europe we had kings who ruled by divine right. In principle they could declare whatever law they liked. In practice they were hemmed in in various ways. These days the U.S. and Europe mostly have elections. The elected government can pass any law within certain limits, but the laws are subject to repeal by later governments installed by later elections. The court system is also able to rule that certain laws are inappropriate, based on arguments from a higher set of laws–in the U.S., the constitution.

In the last resort, governments enforce their laws by force. Therefore, we have to ask: what is the moral basis for their actions? In a democratic system in which the government is freely elected, the presumption is that the government acts morally because it derives its powers from the consent of the people who elect it. In a monarchy in which the ruler rules by divine right, the presumption is that the government acts morally because God appointed the ruler, and God is by definition the source of all morality.

These points of view are easy enough to understand within the system. But consider what they look like from outside. In particular, what if you live in another country, and you are being invaded by the one under discussion.

If you are being invaded by a monarchy, then perhaps the monarch believes in a false God. In that case, you need to fight back against the monarch, try to convince the people that he or she believes in a false God and encourage them to rebel, try to assassinate the monarch. There is no reason for any special animus against the people: they may be heretics, and you defend yourself against them, but they are not really the enemy.

Or suppose you are being invaded by a democracy (Thomas Friedman once argued that one democracy would never invade another, but that rule clearly fell by the wayside during the Balkan struggles in the 90s). Now you are being attacked by representatives of all the people in the invading country. Since the people provide the moral grounding for the government, they are all responsible. They are all the enemy.

This point of view naturally leads to the war of entire societies, and the targeting of what were once known as innocent civilians–a practice which began in earnest in World War II. This seems like an unfortunate consequence. But there is no way for us to have the right to change our government without taking on the moral responsibility for the actions of the government. It’s not enough to say “I voted for the other guy.” We are still part of the society, and we live by its rules.

In a democracy, we are truly our brother’s keeper, because we are in part responsible for his actions. That is a heavy load to carry.

Comments (4)

Terrorism: Goals vs. Methods

I rcently read what I thought was an insightful comment on terrorism, although I have unfortunately now forgotten where. The comment was that terrorists want to be judged on their statements, but they are in fact judged on their actions.

For example, Osama bin Laden has stated that his goals are to force U.S. forces to leave Islamic lands, in which he includes Israel. His actions have been to attack the U.S., killing innocents. People in the U.S. do not conclude, based on his statements, that he is a rational actor using asymetrical warfare techniques to make us for his lack of force. Instead, they conclude, based on his actions, that he is an insane mass murderer who wants to kill as many Americans as possible. The result is that people ignore bin Laden’s actual goals. This quite likely came as a surprise to him, to the extent that he has recognized it at all.

Now, I personally think that bin Laden is an evil mass murderer, but I don’t think that he is insane. I think his goals are what he says they are: to reestablish the Islamic caliphate, free from foreign control. This may seem quixotic, but after all he did succeed in Afghanistan–at least he succeeded until 9/11 provoked an invastion. Assuming that he is not insane, he has no reason to hide his goals. I think it is quite probably that, in the extremely unlikely case that he were successful, he would cease his attacks on the U.S. He would no longer have any reason to attack.

The original comment regarded terrorists. But I think it’s important to extend this in considering how other people regard us. We have caused the deaths of far more Iraqis than the number of Americans who died in 9/11. U.S. forces have regularly killed innocent Iraqis at checkpoints and by dropping bombs. Unlike bin Laden, these are accidents which occurred despite our good intentions. But the people in Iraq judge us by our actions, not our statements. What they see is that we are killing people. No wonder most of them regard the U.S. as an occupation force, and that they want us to leave.

A similar trap occurs in Israel. The Israeli forces try hard to avoid hurting innocent bystanders. But they do get hurt. In the second Intifadah many more Palestinians died than Israelis.

To be clear, I do think that motives matter. There is a huge difference between the Palestinian terrorists who target innocent people and the Israeli forces who try to avoid harming innocent people. There is a huge difference between evil people like bin Laden or Saddam Hussein and the U.S. forces fighting in Iraq and Afghanistan. But when judging only by actions, not by statements or intentions, the difference appears much smaller.

It is a cliche to observe that it is not enough to mean well; you must also appear to mean well. For the U.S. to succeed in preventing terrorism, we must remember and apply that lesson. And we must also remember that terrorists may have crazy goals and crazy methods, but they aren’t irrational. If they were irrational, they would be much less dangerous.

Comments (2)


What should we do about Iraq? (Obviously a contentious topic.) It seems clear at this late date that the reasons that the Bush administration gave for the invasion were consistently either lies or hopes which have failed. But that is the past. What should we do now?

What are the advantages of keeping the army in Iraq?

  • There is the chance that if we can keep the peace in Iraq, it will become a relatively normal country. That would be good. Unfortunately, I think that at this point we can rule out the premise: we are not able to keep the peace. Our military is simply not large enough to provide a police force for a country the size of Iraq. The Iraqi police and military are showing no signs of being able to do the job themselves. We need to set aside wishful thinking and acknowledge that this is not going to happen. For that matter, we should also acknowledge that Iraq was created by fiat in the 1920s, and has never in fact been a normal country. It has no ties of culture, religion or ethnicity sufficient to hold it together.
  • We owe it to the people of Iraq to keep the peace: in other words, we broke the country, so now we own it. I think this argument is strong, but, again, it founders on the fact that we can not do it. We owe the people of Iraq no apologies for removing Saddam Hussein, but we owe them big-time for messing up the reconstruction. Unfortunately, this is a debt which we can not pay. It is folly to keep trying the impossible.
  • Iraq has considerable oil reserves, and oil has strategic importance for the U.S. This is absolutely true, although unfortunately the oil is currently unrecoverable due to regular sabotage. However, we do not need to have military forces in Iraq in order to extract the oil. We need to first have the country normalize, and we need to then offer the best terms for the oil. This will not be easy, as China is willing to make a considerable investment in order to get oil, as they are showing in Chad and other places. However, I think that we can compete fairly in the marketplace.
  • Having military bases in Iraq would be useful to counteract potential enemies like Al Qaeda, Iran, and Syria. This is likely true, although it is necessary to weigh the benefit of having the bases against the provocation they provide. The most plausible solution will be to keep military bases in the Kurdish region of Iraq, where they will be both more welcome and less provocative.
  • Leaving Iraq would be admitting defeat, and that would be a victory for our enemies. This argument was used during the Vietnam War, and it proved completely false. Admittedly, leaving Iraq will mean that few people will welcome our involvement in their country in the future, but that’s OK: the Iraqis didn’t want us there either (at least, they didn’t want us to stay–at the start of the occupation, many Iraqis said “thanks for removing Saddam Hussein; now please leave”). Taking our military forces out of Iraq will not make us weaker; it will make us stronger.

I can’t think of any other advantages. The disadvantages–the loss of life, the enormous expense, the distraction from other parts of the world–are clear. We need to leave Iraq.

How should we do it? Given the situation, the answer has to be as fast as possible, consistent with keeping Americans and Iraqis safe and doing as best as we can for Iraq in the process. I am scarcely a military strategist, but my recommendations would be along the lines of preparing bases in Kurdistan, slowly consolidating our forces in the rest of Iraq, and then announcing our withdrawal at a future date. On that date, the withdrawal must be done in sufficient force to protect the soldiers. We should provide asylum to members of the Iraqi government who request it, along with their families.

When announcing the date of the withdrawal, we should encourage the other Arab countries to help stabilize Iraq. They are unlikely to actually do anything, but we have to try.

Then we have to see what happens. The immediate result will most likely be an escalation of the process of civil war and ethnic cleansing. This is already happening despite our best efforts, and is likely to intensify. General regional instability will also increase, and we must be ready to intervene militarily to prevent chaos from spilling across country borders. Kurdistan will presumably declare its independence from Iraq, and we should support that, while keeping close watch on the borders between Kurdistan and Turkey.

This is, of course, an admission of defeat. I think an honest appraisal is that we have already lost. The question now is how to lose as gracefully as possible.

Sadly, none of this will happen during the current administration. Things won’t look any better when we have a new president, 17 long months from now. I just hope they don’t look significantly worse.

Comments (2)

Cutting Without Measuring

We’re having our front steps replaced. They are made of concrete with embedded tiles (the old steps were badly cracked, and had to be removed anyhow when we had our foundation rebuilt). We were able to salvage about half the tiles from the old steps as they were destroyed, and managed to find matching new ones for about $15 a tile. My wife and daughter spent about two hours laying out the tiles on a sheet, marked with tape to the measured size of the steps, and with the location of each tile measured out. The tiles are each marked to indicate which one goes where (they are various different colors). This map will be used by the builders to place the tiles precisely into the concrete before it dries.

The amount of time spent planning for this task of placing tiles far exceeds the amount of time which the task will actually take. This approach is captured in the old carpentry dictum “measure twice, cut once.” While participating in this tile project, I couldn’t help noticing that this is not how programmers work. It is appropriate to take a long time to measure the tile location because once the concrete dries–a couple of hours at most–there is no going back. The tiles will be set into their position, and the only way to change them will be to destroy the steps again.

Programming is quite different. It takes place in a fluid medium. Any decision can be changed at any time. Of course, some decisions are harder to change than others, because they affect more code. But decisions at the level of “change this tile to another color” or “move this tile a few inches” are generally pretty easy to make in code. This fluidity means that programmers almost never measure twice and cut once. In fact, programmers often don’t measure at all. They just code.

There have been various efforts over the years to encourage programmers to spend more time in the design phase before they start the coding phase. I really don’t know any experienced programmer who takes them seriously. Most projects do start with a relatively informal written plan. This plan is helpful but soon becomes inaccurate. It is generally not updated in detail.

This is not inherently a bad thing. It is appropriate for the nature of the medium. Despite the claims made by the proponents of better design, the truth is that the biggest problems in programming do not arise from lack of design. They come where different systems are stitched together, such that the systems were never designed together in the first place. The biggest problems in programming come from managing complexity, dealing with unexpected and unplanned interactions between different parts of the program and between different layers of the overall system.

This complexity is most likely irreducible. Perhaps what we need in our programs is more ability to handle unforseen events. Perhaps we need to write our code so that it does approximately the right thing in all cases, as well as doing the precisely correct thing in well understood cases. Of course the “right thing” to do is an inherently context dependent operation. So this would have to be expressed in the interfaces between components, rather than in the components themselves.

So perhaps what we need is an interface more sophisticated than the function call, one that can describe what the caller expects. So you wouldn’t just say “draw a window this size at this position,” you would also specify what type of data was going into the window and how the window was likely to be used. That information would be used when it turns out to be impossible or inappropriate to fulfill the original request, perhaps because the screen is too small or because the user has requested extra large windows.

Of course, if done in a simplistic manner, this amounts to adding parameters to the function call, which just pushes the problem back one level. Is there any way that we can capture this kind of fuzzy information in a useful way? Can our programs automatically learn what to do in unexpected situations? Can we provide mechanisms that we can use to teach them?


« Previous Page« Previous entries « Previous Page · Next Page » Next entries »Next Page »