Reading Robert Austin's book Measuring and Managing Performance in Organizations (Dorset House, 1996), was such an eye-opening experience for me that it has merited mention in this blog several times before this, most prominently in In Defense of Misbehavior. Once you understand measurement dysfunction, in which the performance measurement of individuals almost inevitably drives dysfunction into an organization, you will never again see the world in quite the same way.
The gist of it is this: an old axiom of business is "You cannot manage what you do not measure." But in his Ph.D. thesis, Austin, formerly an executive with Ford Motor Company and now on the faculty of the Harvard Business School, applies agency theory, a form of game theory, to show that in all but the most trivial of situations, it is impossible to measure all metrics applicable to an individual's performance. There will always be aspects of performance that cannot be measured. When rewarded (or punished) based on the metrics you do measure, the person being measured will be highly incentivized to game the system by slacking off on the those unmeasurable metrics. A classic example are call center agents hanging up on customers in the middle of calls to meet their quotas.
Austin's work has been cited by Tom DeMarco ("Mad About Measurement") in Why Does Software Cost So Much? (Dorset House, 1995), and by Joel Spolsky ("Measurement") in Joel on Software (Apress, 2004). It compelled me to get a copy of his dissertation (Robert Daniel Austin, Theories of measurement and dysfunction in organizations, Carnegie Mellon University, University Microfilm, #9522945, 1995), and even put a talk together on the topic which I've given several times. Given the recent horrifying cover story in BusinessWeek, "Managing by the Numbers: How IBM improves quality by tracking employees' every move" (September 8, 2008) , this topic is bound to become popular blog fodder once again.
But that's not what I'm here to talk about. I'm here to talk about why free markets don't work.
A few years ago, a large telecommunications equipment manufacturer decided to save money by eliminating all desktop PC support and having their product developers support their own predominantly-Windows desktop computers. This was done, of course, as a money savings move.
Did they save money? On paper sure, because they eliminated a bunch of IT staff from the bottom line. In reality, who the hell knows? All they really did was move their desktop IT support from where its cost could be measured to where it could not be measured. Most of the product line of this manufacturer was Linux-based, so the developers, who were earning hefty salaries for their Linux and telecommunications expertise, were not Windows experts. Most of their Windows support experience came from buying a home PC from BestBuy.
I suspect those developers were the most expensive IT support staff on the planet. But its all good because those costs weren't measured. Nor was the loss in productivity, the reduction in efficiency and quality in the work environment, and the moral hit to both the developers and the IT staff that came with the assumption that those two skill sets were interchangeable. I mean, really, it's just all computers, right? How hard can it be?
Sure, you could see this as a form of measurement dysfunction: some VP got a bonus by gaming the system. This is how people most often think of measurement dysfunction, as a more general term for incentive distortion. But this can also be seen in another way, not inadvertent dysfunction caused by the measurement of performance of individuals, but in a deliberate application so as to move costs to where they could not be measured. It's measurement dysfunction as management strategy.
Pollution is another form of measurement dysfunction. Companies realize cost savings by not dealing with the environmental costs of manufacturing. That's because, without government regulation, environmental costs are not borne by the polluter. The costs are pushed off onto the downstream neighbors of the manufacturer, or into the surrounding community, even onto future generations. As long as you just think locally and take a short term view, there is a strong incentive to move environmental costs to where they cannot be measured. Offshoring is just another form of this: moving environmental, or even societal, costs to where they are not measured.
In his book, Best Business Crime Writing of the Year (Random House, 2002), James Surowiecki collects magazine and newspaper articles on the spate of corporate crime that lead to the demise of Enron, WorldCom, Tyco, and other best-in-class companies. The actions of the executives described in these articles illustrate another form measurement dysfunction. Federal, state and local laws are a form of measurement. There is a strong (given the huge dollar amounts involved, I'm tempted to say irresistible) incentive to game the system by testing the limits and loopholes of those laws in an effort to derive revenue from areas for which the results of actions are not measured. I suspect that many of these executives didn't even realize they had committed a crime until the men with badges, guns, and handcuffs showed up with warrants, subpoenas, and writs. The Sarbanes-Oxley Act is an attempt to fix this dysfunction by measuring a metric that had not been measured before.
Measurement dysfunction is much more broadly applicable than just as incentive distortion. That's why it's known by other names in other contexts: unintended consequences, perverse incentives, and moral hazard are some I know about. With all due respect to my libertarian friends (and I have a lot of them), I argue that measurement dysfunction is why free markets don't work.
There will always be an economic incentive for participants in a truly free market to dump costs into or derive revenue from any gray area in which there is no measurement. And in an information economy, there are a lot of gray areas. That's because the measurement of all dimensions of market costs is impossible. Adam Smith described an "invisible hand" that guides markets to the most efficient allocation of resources. But for many metrics of market cost, there is no hand at all, invisible or otherwise. I'm not arguing for controlled markets. But I am arguing for regulated markets: that a significant (and perhaps unfortunate) amount of government regulation is necessary to act as a visible hand, forcing market participants to bear the full costs of their transactions.
In the realm of performance measurement of individuals, Austin argues against extrinsic motivation, for example bonuses tied to specific goals, because of the measurement dysfunction this produces. Instead, intrinsic motivation, for example corporate culture, causes individuals to do the right thing independent of incentives. If intrinsic motivators worked at the corporate level, free markets could work as well. But it's been argued that corporations are psychopathic because, devoid of any other legal restraint, their sole purpose is to maximize shareholder value.
I'm not saying that corporations are evil. I'm the founder and CEO (and janitor) of a corporation myself. But I am saying that it would be foolish not to acknowledge the measurement dysfunction that occurs in a truly free market.
Thursday, September 04, 2008
Tuesday, September 02, 2008
Choosing Software for Diminuto
Diminuto is my attempt to put together a platform on which to teach real-time software design, systems programming, embedded software development and assembly language programming, all using real commercial hardware and open source software. In Diminuto Right Out of the Box, I described how to get the Atmel AT91RM9200-EK evaluation kit (EK) running with the software it ships with, which includes a Linux version 2.4 kernel and a tool chain based on the GNU Compiler Collection version 2.95.3. In this this article, I'll describe the software I used to build a reduced-memory footprint system using the Linux version 2.6 kernel and a tool chain based on GCC 4.2.4.
My career as a technologist has been pretty much all over the map. I've always thought of that as a good thing, although I've been accused by my betters of being everything from "a renaissance man" to "unfocused". My career seems to shuttle back and forth between developing for high-end server-side systems and doing real-time and embedded development. Consequently, the systems for which I've developed have ranged from processors with eight kilobytes of memory to distributed networks of servers to supercomputers.
Even among embedded systems, the range has been kind of startling. In the 1970s I wrote standalone assembler code for PDP-11s with 8KB of core memory. Core memory was kind of neat because it maintained its state across power cycles. We used to patch our code by toggling in new machine instructions from the switch register on the front panel. More recently, and more typically, I've found myself writing mostly in C, C++ and occasionally even Java, for PowerPC, i960, or ARM microprocessors running some commercial real-time operating system (RTOS) like VxWorks, pSOS, C-Executive, or RTX which run completely memory resident. Meanwhile, the server-side portion of my career evolved from using just about every UNIX variant known to man to being 100% Linux based. Probably no surprise there.
With the availability of cheaper random access memory (RAM), and relatively inexpensive microprocessors that have a memory management unit (MMU), perhaps it was inevitable that these two career paths merge with the advent of embedded Linux. But even among embedded Linux systems there is a broad range of configurations, ranging from systems that still run completely memory resident and which are reminiscent of those VxWorks systems, to those that have persistent storage in the form of solid-state "disks" such that they seem more like a Linux server.
Whether you are accustomed to developing for Linux on a PC, or you are an embedded developer used to VxWorks, embedded Linux will seem like a weird combination of the familiar and the bizarre, not quite fitting in with either world. The kernel seems familiar to the PC developer, but there may be no persistent storage and hence no paging of virtual memory, and you may do everything logged in as root while the system runs in single-user mode. The lack of persistent storage seems natural to the embedded developer, but the system has an MMU which maps between physical and virtual memory addresses, the processor executes code in privileged and non-privileged mode, it insists on having a root file system even though it may be completely memory resident in something called a RAM disk, and there is an unusual wealth of sophisticated applications and tools that can run on the system. The need to compile and link on a host system (like a conventional Linux PC with an Intel processor and a cross-compilation tool chain) but run on a completely different target system (like the AT91RM9200-EK board with an ARM processor and no tool chain at all) freaks out the PC developer but is strictly in the comfort zone of the embedded developer.
Many embedded systems have pretty severe resource constraints when compared to your typical PC. The EK board has 32 megabytes of RAM and a processor delivering a claimed 200 million instructions per second (MIPS). The Dell 530 quad-core server in the basement (a.k.a. the vast Digital Aggregates corporate data center) on which I run the Diminuto tool chain has three gigabytes of RAM and its speed is several billion instructions per second (GIPS). My Nokia N810 internet tablet, more typical of hand-held consumer devices, has 128 megabytes of RAM, just four times that of the EK, with maybe a 400 MIPS processor. All of these are Linux systems, but clearly they are not quite the same Linux system.
Living within your means, RAM-wise, isn't just an issue for the kernel and any programs that are running at any one time. Although Linux requires a root file system, I've mentioned that many embedded devices have no persistent storage device. The kernel, any running programs, and the root file system in some kind of RAM disk, all share the available RAM. The kernel and the RAM disk are loaded into RAM at boot time, either from some read-only memory (ROM) or across a network using something like the Trivial File Transfer Protocol (TFTP). Reducing the memory footprint of the RAM disk turns out to be important too.
Or maybe not. Ridiculously large surface mounted flash memory devices with integrated controllers that emulate IDE disk drives are becoming more available, driven in part by Windows CE hand-held devices. The multi-gigabyte single chip disk drives that I have used come from the factory pre-formatted for the Windows FAT file system. Linux itself includes drivers for devices like Secure Digital (SD) flash cards and USB flash drives which emulate SCSI disk drives.
Persistent storage devices are becoming more common in all but the most cost sensitive or tiniest embedded systems. However, such solid state persistent storage devices tend to be very slow when compared to disk drives. Even when they are available, there is a tendency to keep as much as possible of the working set of "disk" blocks from these devices cached in memory.
It's easy to argue that the trend will be towards more and more RAM in embedded devices, just as there has been for servers, desktops, and laptops. But the trend may be in just the opposite direction for many embedded applications. Microcontrollers (which is what microprocessors are called when you don't know that they're there) are being used in physically smaller, and more price sensitive, devices. There is a strong competitive pressure to shave the manufacturing cost of a device that will be sold in the millions. Sometimes this means less RAM and eliminating a flash drive. Pennies count in such applications.
I've built both types of embedded Linux systems: those that had a lot of RAM and a large flash-based disk drive, and those that booted from ROM and ran completely in RAM. The former wasn't substantially different from the user's point of view from a PC-based system: multi-user, ran the SSH daemon, even ran an Apache web server and a Java SE JVM, and your files were still there in your home directory when the system was rebooted. The latter: single user mode, could only be accessed from a serial port, and every press of the reset button was a new day RAM disk-wise. It's easy to get spoiled with the former. I learned more from the latter. Diminuto marches right down the middle: the basic system runs completely resident in RAM, but supports the use of persistent file systems on SD cards and USB drives.
Here are some approaches to reducing the resource footprint of a Linux system.
Reduce the Size of the Kernel
You download the latest Linux kernel from www.kernel.org: all eight million lines of C code in twenty thousand source files. In the case of Diminuto, which uses an ARM-based processor, you run the command
make menuconfig ARCH=arm
and are delighted to discover that you can select the options AT91 and AT91RM9200-EK to get support for the devices in your system-on-a-chip. Then you build the kernel and discover to your horror that the resulting bootable image is enormous. True, the Linux kernel has direct support for the AT91RM9200-EK board. But if you just select that option, you will find that by default the configuration process has selected tons of other options and drivers you could care less about, including a lot of stuff you don't even recognize, and also left out a bunch of stuff you know you're going to need.
To generate exactly the kernel you need without blowing your memory budget, you must laboriously go through all the dozens of nested configuration menus, figure out whether you really need each item, and then either enable or disable it. This includes the seemingly hundreds of device drivers, including the ones that can be built as loadable modules (more on that later). This may take several iterations, some research, and some hard decisions ("Hmmmm, do I really need IPV6?"), but it's worth it. In the end you'll get what you need with a memory footprint you can live with. If you forget something, you can always generate another kernel and try it.
During this process you will be tempted to build every device driver as a loadable module. You will do this because this is exactly what you do for your PC-based Linux system. Loadable kernel modules and device drivers are not linked directly into the kernel image, but instead are loaded dynamically on demand from the file system. Building loadable modules for your embedded system doesn't actually hurt anything, as long as you realize it's mostly a waste of time. Devices other than what are on your board aren't likely to magically appear; the EK doesn't have a back plane into which you can easily plug in other boards. And you have pretty much a 100% chance of using the devices that are implemented on your board. Furthermore, unused loadable modules in a RAM disk file system take up RAM whether you are using them or not. My advice is to build all the kernel options and device drivers you know you are going to use directly into the kernel, and explicitly omit everything else.
There is an important exception to this rule: if you are writing your own device drivers for your board, you may want to use loadable modules for reasons of intellectual property and licensing. Conventional wisdom is that loadable modules are not contaminated by the GNU Public License (GPL), whereas modules linked directly into the kernel are. I'm not a lawyer, and I'm not aware of any legal precedent having been set for this, but when I've written device drivers for my clients for closed, proprietary, custom hardware, I've built them as loadable modules.
In Diminuto, I built version 2.6.25.10 of the Linux kernel using the approach I just described, including all supported devices, directly into the kernel, and omitting everything else.
There are also alternatives to the conventional Linux kernel. uCLinux is a version of Linux that does not require an MMU. I've never used it. But it does admit the possibility of running Linux on microcontrollers that are in the traditional sphere of RTOSes like VxWorks. uCLinux has been ported to many of the embedded microprocessors on which I've worked over the years. I think it's worth examining if that's the world in which you are working.
Reduce the Size of Binary Executables
A statically linked binary executable is a program which incorporates all of its code in a single monolithic image. If several programs are statically linked against the same library, they each contain unique copies of the same functions and subroutines that they reference in that library. Everyone gets their own copy of printf. There are sometimes reasons to do this (it may facilitate debugging), but it makes every binary executable a lot larger than it otherwise needs to be.
A shared library in Linux is like a Dynamic Link Library (DLL) in Windows (or so I'm told). It is a way for binary executables to share common code. One copy of the shared library is loaded into memory. When a binary executable which was originally dynamically linked against that shared library is run, the program loader fills in the references to the shared functions and subroutines inside the executable so that they point into the shared library. The MMU is used to create the illusion that everyone is using their own copy of the library, even though everyone is sharing the same code.
This is a good thing, generally, whether you have an embedded system with 32MB of RAM or a PC with 3GB of RAM. But it does take some care to manage the installation and maintenance of the shared library. Woe be to the person who runs a binary executable that was dynamically linked on the host system against a different version of the shared library from that which is resident on the target system.
It also requires some care in the construction of the shared library itself. A shared library that incorporates a bunch of functions and subroutines that aren't used by any binary executable is still wasting RAM. Shared libraries are only a win if the code in them is actually shared. This is why I chose to build Diminuto using uClibc, a version of the Standard C library with a reduced memory footprint. uClibc gets its reduction through a variety of means: by omitting some features not needed in most embedded applications, by reducing the capacity of some retained features, and by some code re-factoring. I used version 0.9.29 of uClibc for Diminuto.
I have also built embedded Linux systems using the full blown GNU standard C library, so your mileage may vary. If you are running completely memory resident, I recommend you at least look at uClibc to see if it meets your needs. If you have the extravagant pleasure of a "disk" on your target, you may consider using the GNU library. On my To Do list for Diminuto is to build a root file system using the full GNU library that boots from an EXT3 file system on the Secure Digital (SD) flash card supported by the EK. I built support for EXT3 and the SD driver into the kernel, so that same kernel should work for either system. I'd like to eventually run the ARM-version of Sun's Standard Edition (SE) of their Java Virtual Machine (JVM) using this platform. (I've done this in the past on embedded PowerPC platforms with zero issues.) I routinely use EXT3 file systems on USB drives for persistent storage with the current RAM-resident Diminuto system.
One thing I did not scrimp on was the C++ standard library and the POSIX Thread library. I knew I was going to port my embedded, real-time C++ toolkit, Desperado, to Diminuto, and I wanted unfettered access to the complete Standard Template Library (STL) and to pthreads. Recently, however, a reduced footprint version of the C++ standard library, uClibc++, has been developed that is worth a look. I haven't used it.
I've had no library-compatibility issues with porting either Desperado or my C-based Diminuto library to the AT91RM9200-EK and running their unit tests. I have had some weirdness with the GNU arm-linux-g++ compiler itself which I discuss on the Diminuto web page.
Reduce the Size of the Root File System
Much of the Linux root file system is taken up with scripts and utilities to manage its multi-user environment and to provide a rich set of tools for those multi-users. The entire huge System V init script infrastructure exists mainly to take a multi-user system up and down in an orderly manner. The typical embedded system, however, runs a very limited set of applications, may have no traditional user interface at all except for during initial development, all processes may run as root, and it is brought up and down strictly with the power switch. This requires a much simpler infrastructure that eliminates a lot of the stuff usually found in the root file system.
This is also one of the reasons I recommend using an EXT3 journaled file system if you have persistent storage. EXT3 is bit-compatible with EXT2, a staple of Linux systems for a long time, with the addition of a journal file. In fact, an EXT3 file system can be mounted as an EXT2 file system, in which case the system ignores the journal file. EXT3 is a robust approach for an embedded system where someone may hit the reset button at any time. I built Diminuto with support for EXT2, EXT3, and VFAT (a.k.a. Windows FAT-32, especially useful for USB drives that are traded between Windows and Linux systems).
PC developers will be horrified to know that most work is done on embedded Linux systems while the developer is logged in as root, but this will seem natural to the embedded developer. This is because nearly all of the work that needs to be done on the target system has to be done as root, while all the development work that needs to be done on the host system is done logged in as a normal unprivileged user. Also, a scrogged target system can typically be recovered by just hitting the reset button, with the resulting loss of everything you may have had on the RAM disk. Linux offers the ability to segregate processes and files on the target system by user ID, which does provide a great deal more protection. I recommend thinking about this if non-developers have access to the innards of your embedded Linux system, even if they don't have login access. For example, you will surely want to run any web server under a non-root account.
BusyBox is a very clever way of reducing both the RAM and disk footprints of a Linux system without much impact on functionality. BusyBox is a single monolithic program that implements the functionality of dozens of commonly used Linux commands. It achieves this significant resource reduction, even when using shared libraries, by yet more sharing of common code, excluding seldom used options, and by being less scalable than the equivalent full featured GNU utilities. BusyBox is a multi-call binary: if it is invoked through a soft link called ls, it behaves like the ls command.
I built Diminuto using version 1.11.1 of BusyBox. A quick tour through all of the bin directories on my PATH reveals that my root file system on Diminuto has all of five binary executables:
/sbin/ldconfig
/usr/bin/ldd
/usr/bin/gdbserver
/usr/local/bin/getubenv, and
/bin/busybox.
The dozens of other commands are just soft links to /bin/busybox. (And the first three of those binaries are just to expedite debugging.)
The use of BusyBox is a huge win, even if you can't use all of its capabilities. I am currently using the Bourne-like shell provided by BusyBox. If your embedded system depends heavily on complex shell scripts, and if resources permit, consider loading your shell of choice (e.g. the Bourne Shell) on your embedded system. Scripting is a huge win productivity-wise over implementing the same functionality in C code, and the additional resources required by a full blown shell interpreter can be well worth it.
In future articles I'll discuss how I built the root file system for Diminuto, describe the adventure that was getting the 2.6 Linux kernel running on the AT91RM9200-EK board, and give you a tour of the running system.
My career as a technologist has been pretty much all over the map. I've always thought of that as a good thing, although I've been accused by my betters of being everything from "a renaissance man" to "unfocused". My career seems to shuttle back and forth between developing for high-end server-side systems and doing real-time and embedded development. Consequently, the systems for which I've developed have ranged from processors with eight kilobytes of memory to distributed networks of servers to supercomputers.
Even among embedded systems, the range has been kind of startling. In the 1970s I wrote standalone assembler code for PDP-11s with 8KB of core memory. Core memory was kind of neat because it maintained its state across power cycles. We used to patch our code by toggling in new machine instructions from the switch register on the front panel. More recently, and more typically, I've found myself writing mostly in C, C++ and occasionally even Java, for PowerPC, i960, or ARM microprocessors running some commercial real-time operating system (RTOS) like VxWorks, pSOS, C-Executive, or RTX which run completely memory resident. Meanwhile, the server-side portion of my career evolved from using just about every UNIX variant known to man to being 100% Linux based. Probably no surprise there.
With the availability of cheaper random access memory (RAM), and relatively inexpensive microprocessors that have a memory management unit (MMU), perhaps it was inevitable that these two career paths merge with the advent of embedded Linux. But even among embedded Linux systems there is a broad range of configurations, ranging from systems that still run completely memory resident and which are reminiscent of those VxWorks systems, to those that have persistent storage in the form of solid-state "disks" such that they seem more like a Linux server.
Whether you are accustomed to developing for Linux on a PC, or you are an embedded developer used to VxWorks, embedded Linux will seem like a weird combination of the familiar and the bizarre, not quite fitting in with either world. The kernel seems familiar to the PC developer, but there may be no persistent storage and hence no paging of virtual memory, and you may do everything logged in as root while the system runs in single-user mode. The lack of persistent storage seems natural to the embedded developer, but the system has an MMU which maps between physical and virtual memory addresses, the processor executes code in privileged and non-privileged mode, it insists on having a root file system even though it may be completely memory resident in something called a RAM disk, and there is an unusual wealth of sophisticated applications and tools that can run on the system. The need to compile and link on a host system (like a conventional Linux PC with an Intel processor and a cross-compilation tool chain) but run on a completely different target system (like the AT91RM9200-EK board with an ARM processor and no tool chain at all) freaks out the PC developer but is strictly in the comfort zone of the embedded developer.
Many embedded systems have pretty severe resource constraints when compared to your typical PC. The EK board has 32 megabytes of RAM and a processor delivering a claimed 200 million instructions per second (MIPS). The Dell 530 quad-core server in the basement (a.k.a. the vast Digital Aggregates corporate data center) on which I run the Diminuto tool chain has three gigabytes of RAM and its speed is several billion instructions per second (GIPS). My Nokia N810 internet tablet, more typical of hand-held consumer devices, has 128 megabytes of RAM, just four times that of the EK, with maybe a 400 MIPS processor. All of these are Linux systems, but clearly they are not quite the same Linux system.
Living within your means, RAM-wise, isn't just an issue for the kernel and any programs that are running at any one time. Although Linux requires a root file system, I've mentioned that many embedded devices have no persistent storage device. The kernel, any running programs, and the root file system in some kind of RAM disk, all share the available RAM. The kernel and the RAM disk are loaded into RAM at boot time, either from some read-only memory (ROM) or across a network using something like the Trivial File Transfer Protocol (TFTP). Reducing the memory footprint of the RAM disk turns out to be important too.
Or maybe not. Ridiculously large surface mounted flash memory devices with integrated controllers that emulate IDE disk drives are becoming more available, driven in part by Windows CE hand-held devices. The multi-gigabyte single chip disk drives that I have used come from the factory pre-formatted for the Windows FAT file system. Linux itself includes drivers for devices like Secure Digital (SD) flash cards and USB flash drives which emulate SCSI disk drives.
Persistent storage devices are becoming more common in all but the most cost sensitive or tiniest embedded systems. However, such solid state persistent storage devices tend to be very slow when compared to disk drives. Even when they are available, there is a tendency to keep as much as possible of the working set of "disk" blocks from these devices cached in memory.
It's easy to argue that the trend will be towards more and more RAM in embedded devices, just as there has been for servers, desktops, and laptops. But the trend may be in just the opposite direction for many embedded applications. Microcontrollers (which is what microprocessors are called when you don't know that they're there) are being used in physically smaller, and more price sensitive, devices. There is a strong competitive pressure to shave the manufacturing cost of a device that will be sold in the millions. Sometimes this means less RAM and eliminating a flash drive. Pennies count in such applications.
I've built both types of embedded Linux systems: those that had a lot of RAM and a large flash-based disk drive, and those that booted from ROM and ran completely in RAM. The former wasn't substantially different from the user's point of view from a PC-based system: multi-user, ran the SSH daemon, even ran an Apache web server and a Java SE JVM, and your files were still there in your home directory when the system was rebooted. The latter: single user mode, could only be accessed from a serial port, and every press of the reset button was a new day RAM disk-wise. It's easy to get spoiled with the former. I learned more from the latter. Diminuto marches right down the middle: the basic system runs completely resident in RAM, but supports the use of persistent file systems on SD cards and USB drives.
Here are some approaches to reducing the resource footprint of a Linux system.
Reduce the Size of the Kernel
You download the latest Linux kernel from www.kernel.org: all eight million lines of C code in twenty thousand source files. In the case of Diminuto, which uses an ARM-based processor, you run the command
make menuconfig ARCH=arm
and are delighted to discover that you can select the options AT91 and AT91RM9200-EK to get support for the devices in your system-on-a-chip. Then you build the kernel and discover to your horror that the resulting bootable image is enormous. True, the Linux kernel has direct support for the AT91RM9200-EK board. But if you just select that option, you will find that by default the configuration process has selected tons of other options and drivers you could care less about, including a lot of stuff you don't even recognize, and also left out a bunch of stuff you know you're going to need.
To generate exactly the kernel you need without blowing your memory budget, you must laboriously go through all the dozens of nested configuration menus, figure out whether you really need each item, and then either enable or disable it. This includes the seemingly hundreds of device drivers, including the ones that can be built as loadable modules (more on that later). This may take several iterations, some research, and some hard decisions ("Hmmmm, do I really need IPV6?"), but it's worth it. In the end you'll get what you need with a memory footprint you can live with. If you forget something, you can always generate another kernel and try it.
During this process you will be tempted to build every device driver as a loadable module. You will do this because this is exactly what you do for your PC-based Linux system. Loadable kernel modules and device drivers are not linked directly into the kernel image, but instead are loaded dynamically on demand from the file system. Building loadable modules for your embedded system doesn't actually hurt anything, as long as you realize it's mostly a waste of time. Devices other than what are on your board aren't likely to magically appear; the EK doesn't have a back plane into which you can easily plug in other boards. And you have pretty much a 100% chance of using the devices that are implemented on your board. Furthermore, unused loadable modules in a RAM disk file system take up RAM whether you are using them or not. My advice is to build all the kernel options and device drivers you know you are going to use directly into the kernel, and explicitly omit everything else.
There is an important exception to this rule: if you are writing your own device drivers for your board, you may want to use loadable modules for reasons of intellectual property and licensing. Conventional wisdom is that loadable modules are not contaminated by the GNU Public License (GPL), whereas modules linked directly into the kernel are. I'm not a lawyer, and I'm not aware of any legal precedent having been set for this, but when I've written device drivers for my clients for closed, proprietary, custom hardware, I've built them as loadable modules.
In Diminuto, I built version 2.6.25.10 of the Linux kernel using the approach I just described, including all supported devices, directly into the kernel, and omitting everything else.
There are also alternatives to the conventional Linux kernel. uCLinux is a version of Linux that does not require an MMU. I've never used it. But it does admit the possibility of running Linux on microcontrollers that are in the traditional sphere of RTOSes like VxWorks. uCLinux has been ported to many of the embedded microprocessors on which I've worked over the years. I think it's worth examining if that's the world in which you are working.
Reduce the Size of Binary Executables
A statically linked binary executable is a program which incorporates all of its code in a single monolithic image. If several programs are statically linked against the same library, they each contain unique copies of the same functions and subroutines that they reference in that library. Everyone gets their own copy of printf. There are sometimes reasons to do this (it may facilitate debugging), but it makes every binary executable a lot larger than it otherwise needs to be.
A shared library in Linux is like a Dynamic Link Library (DLL) in Windows (or so I'm told). It is a way for binary executables to share common code. One copy of the shared library is loaded into memory. When a binary executable which was originally dynamically linked against that shared library is run, the program loader fills in the references to the shared functions and subroutines inside the executable so that they point into the shared library. The MMU is used to create the illusion that everyone is using their own copy of the library, even though everyone is sharing the same code.
This is a good thing, generally, whether you have an embedded system with 32MB of RAM or a PC with 3GB of RAM. But it does take some care to manage the installation and maintenance of the shared library. Woe be to the person who runs a binary executable that was dynamically linked on the host system against a different version of the shared library from that which is resident on the target system.
It also requires some care in the construction of the shared library itself. A shared library that incorporates a bunch of functions and subroutines that aren't used by any binary executable is still wasting RAM. Shared libraries are only a win if the code in them is actually shared. This is why I chose to build Diminuto using uClibc, a version of the Standard C library with a reduced memory footprint. uClibc gets its reduction through a variety of means: by omitting some features not needed in most embedded applications, by reducing the capacity of some retained features, and by some code re-factoring. I used version 0.9.29 of uClibc for Diminuto.
I have also built embedded Linux systems using the full blown GNU standard C library, so your mileage may vary. If you are running completely memory resident, I recommend you at least look at uClibc to see if it meets your needs. If you have the extravagant pleasure of a "disk" on your target, you may consider using the GNU library. On my To Do list for Diminuto is to build a root file system using the full GNU library that boots from an EXT3 file system on the Secure Digital (SD) flash card supported by the EK. I built support for EXT3 and the SD driver into the kernel, so that same kernel should work for either system. I'd like to eventually run the ARM-version of Sun's Standard Edition (SE) of their Java Virtual Machine (JVM) using this platform. (I've done this in the past on embedded PowerPC platforms with zero issues.) I routinely use EXT3 file systems on USB drives for persistent storage with the current RAM-resident Diminuto system.
One thing I did not scrimp on was the C++ standard library and the POSIX Thread library. I knew I was going to port my embedded, real-time C++ toolkit, Desperado, to Diminuto, and I wanted unfettered access to the complete Standard Template Library (STL) and to pthreads. Recently, however, a reduced footprint version of the C++ standard library, uClibc++, has been developed that is worth a look. I haven't used it.
I've had no library-compatibility issues with porting either Desperado or my C-based Diminuto library to the AT91RM9200-EK and running their unit tests. I have had some weirdness with the GNU arm-linux-g++ compiler itself which I discuss on the Diminuto web page.
Reduce the Size of the Root File System
Much of the Linux root file system is taken up with scripts and utilities to manage its multi-user environment and to provide a rich set of tools for those multi-users. The entire huge System V init script infrastructure exists mainly to take a multi-user system up and down in an orderly manner. The typical embedded system, however, runs a very limited set of applications, may have no traditional user interface at all except for during initial development, all processes may run as root, and it is brought up and down strictly with the power switch. This requires a much simpler infrastructure that eliminates a lot of the stuff usually found in the root file system.
This is also one of the reasons I recommend using an EXT3 journaled file system if you have persistent storage. EXT3 is bit-compatible with EXT2, a staple of Linux systems for a long time, with the addition of a journal file. In fact, an EXT3 file system can be mounted as an EXT2 file system, in which case the system ignores the journal file. EXT3 is a robust approach for an embedded system where someone may hit the reset button at any time. I built Diminuto with support for EXT2, EXT3, and VFAT (a.k.a. Windows FAT-32, especially useful for USB drives that are traded between Windows and Linux systems).
PC developers will be horrified to know that most work is done on embedded Linux systems while the developer is logged in as root, but this will seem natural to the embedded developer. This is because nearly all of the work that needs to be done on the target system has to be done as root, while all the development work that needs to be done on the host system is done logged in as a normal unprivileged user. Also, a scrogged target system can typically be recovered by just hitting the reset button, with the resulting loss of everything you may have had on the RAM disk. Linux offers the ability to segregate processes and files on the target system by user ID, which does provide a great deal more protection. I recommend thinking about this if non-developers have access to the innards of your embedded Linux system, even if they don't have login access. For example, you will surely want to run any web server under a non-root account.
BusyBox is a very clever way of reducing both the RAM and disk footprints of a Linux system without much impact on functionality. BusyBox is a single monolithic program that implements the functionality of dozens of commonly used Linux commands. It achieves this significant resource reduction, even when using shared libraries, by yet more sharing of common code, excluding seldom used options, and by being less scalable than the equivalent full featured GNU utilities. BusyBox is a multi-call binary: if it is invoked through a soft link called ls, it behaves like the ls command.
I built Diminuto using version 1.11.1 of BusyBox. A quick tour through all of the bin directories on my PATH reveals that my root file system on Diminuto has all of five binary executables:
/sbin/ldconfig
/usr/bin/ldd
/usr/bin/gdbserver
/usr/local/bin/getubenv, and
/bin/busybox.
The dozens of other commands are just soft links to /bin/busybox. (And the first three of those binaries are just to expedite debugging.)
The use of BusyBox is a huge win, even if you can't use all of its capabilities. I am currently using the Bourne-like shell provided by BusyBox. If your embedded system depends heavily on complex shell scripts, and if resources permit, consider loading your shell of choice (e.g. the Bourne Shell) on your embedded system. Scripting is a huge win productivity-wise over implementing the same functionality in C code, and the additional resources required by a full blown shell interpreter can be well worth it.
In future articles I'll discuss how I built the root file system for Diminuto, describe the adventure that was getting the 2.6 Linux kernel running on the AT91RM9200-EK board, and give you a tour of the running system.
Thursday, August 28, 2008
Diminuto Right Out of the Box
Diminuto is my attempt to put together a platform on which to teach real-time software design, systems programming, embedded software development and assembly language programming, all using real commercial hardware and open source software. In Choosing Hardware for Diminuto, I described how I chose the Atmel AT91RM9200-EK evaluation kit has my first cut at a hardware platform. In this article, I'll describe the EK in detail and show you how to get it up and running in about an hour, just with the software it comes with.
(Blogger sometimes truncates the right-hand portion of the photographs. You can always click on a photograph to bring a full-size version up in your browser.)
The EK is a single board computer (SBC) that is about 6.5" x 7.5" in size. It has an AT91RM9200 microprocessor, part of the Atmel AT91 family. The AT91RM9200 is a system-on-a-chip (SoC) that integrates an ARM920T RISC processor core with several special purpose cores that implement controllers for a variety of peripheral devices. The ARM920T is part of the ARM ARM9 family. It incorporates a real-time clock, a system timer, and a memory management unit (MMU). The EK has 8MB of flash, pre-programmed with the U-Boot boot loader, and 32MB of RAM. Peripheral devices include an Secure Digital (SD) card slot, two USB host ports, one USB gadget port, two DB-9 serial ports, one 10/100 Base-T Ethernet RJ-45 port, a video controller (which is the largest chip on the board) with a VGA port, a JTAG debugging connector, and some other goodies.
Here is a photograph of the EK hooked up to my development setup at the Palatial Overclock Estate (a.k.a. the Heavily-Armed Overclock Compound). You can see the beige serial console cable to the left, the blue CAT5 Ethernet cable front center, and the power supply to the right. Other accoutrements include a little fan (not really necessary, the EK runs pretty cool), a static mat and wrist strap (absolutely required), and a magnifying glass (because I'm old).
The EK is available retail in single quantities from any number of distributors for about $1250. (Yes, I know; I bought an absolutely immense Dell 530 quad-core server for less than this; economies of scale are at work here.) I purchased mine from Avnet. Here's what it looks like when the box arrives at your door.
The box contains (left to right, top to bottom): a European electrical cord, a U.S. electrical cord, a 12V power supply, the EK board in a static bag, a DB9S-to-DB9S null modem serial cable, a Type A-to-Type B USB cable, three DataFlash cards with sample systems on them, a CAT5 Ethernet crossover cable, and two CD-ROMs, one with software for the EK, and a Windows CE demo.
You can use the CAT5 Ethernet crossover cable to connect the EK directly to the Ethernet port on another computer. Instead, I connected the EK to a nearby Ethernet switch using a standard CAT5 Ethernet cable. I used the DB9S-to-DB9S serial cable to attach the console port on the EK to an old Windows ThinkPad laptop, and I used PuTTY to talk to the board. For sure, you will need access to the serial console, since much of not all of the work you will be doing on the EK will be in single-user mode. In a teaching laboratory with several stations, you might consider connecting all of the EKs to a reverse telnet server, which is common practice in the field for serial console ports on all kinds of devices.
The EK has a configuration strap, J15, that needs to be set to cause it to boot U-Boot from flash. This is described in the documentation that comes with the EK. (And this is why I needed the magnifying glass.) If you hold the board while you are grounded using a static strap so that the printing is right-side-up, J15 is in the bottom left quadrant on the board. It should be set to the right so that it connects the center of three pins to the right-hand pin labeled EXT. The photograph below is kind of fuzzy, but it shows you the correct orientation of the board.
The software CD-ROM contains a Windows Trivial File Transfer Protocol (TFTP) server utility, U-Bootable Linux 2.4 kernel images for both the EK and the older (and more expensive) AT91RM9200-DK boards, a corresponding initrd RAM disk root file system image, and a tarball of the tool chain. The tool chain includes the C cross-compiler environment which runs under Linux on a i386 platform, and generates code for the ARM9. I used an existing Linux server (a Dell 530) as both my development platform for the tool chain and as a TFTP server.
The U-Boot boot loader is widely used in embedded products. It is preloaded into flash on the EK. It is set up to boot the EK over TFTP. All you have to do is drop the linux-ek kernel image and the initrd ramdisk root file system image from the CD-ROM in appropriate directory on your TFTP server, administer U-Boot with the parameters for your network, and run some predefined U-Boot commands.
Here is the initial U-Boot dialog that you will see on the console when you hit the reset button on the EK. U-Boot is waiting for you to enter a command.
You will need to use a series of U-Boot setenv commands to configure U-Boot by setting parameters in the form of keyword value pairs. Then use the U-Boot saveenv command to save your settings in non-volatile flash so that they persist across resets. Finally, you can use the U-Boot printenv command to see all of your saved settings. This is described in the Getting Started guide on the software CD-ROM. Use the printenv command first to see what parameters might already be set. (There is a typo on the first page of the guide: when setting the bootargs parameter, there is a space instead of a comma between 115200 and mem.)
You will likely want to replace the IP addresses in the guide for the parameters ipaddr, the static IP address of the EK, and serverip, the IP address of your TFTP server. Here are the commands I used.
setenv ipaddr 192.168.1.223
setenv serverip 192.168.1.102
The guide also shows you how to define long U-Boot command sequences, save them as variables, and then run them. I followed the manual and defined the commands kernel to download the kernel image, and ramdisk to download the ramdisk image. This is useful to save time in the long run, although don't hesitate to try using the raw U-Boot commands. (The guide doesn't show using single quotes to enclose strings with embedded spaces as the value portion of the U-Boot setenv command, but I've used that practice on U-Boot on other projects in the past.)
Below you can see how the U-Boot printenv command displays all the settings for my EK.
To boot the board, you need to tell U-Boot to use TFTP to load the kernel image into memory, then load the ramdisk image into memory, then finally to boot the board. U-Boot boots the board by literally calling the kernel image as a subroutine and passing to it the address of the ramdisk image as a parameter.
First, I download the kernel image linux-ek from the TFTP server to memory location 0x21000000 using the command kernel that I defined.
Next, I download the ramdisk image ramdisk from the TFTP server to memory location 0x21100000 using the command ramdisk that I defined.
Finally, I tell U-Boot to boot the kernel image at location 0x21000000 using the bootm command. You can see below that Linux 2.4 boots and I log into the system.
Using the EK right out of the box, I was able to compile "Hello, World!" on my Linux PC using the arm-linux-gcc command in the provided tool chain, download the resulting ARM executable to the board using TFTP from the shell prompt on the EK, and run it on the EK. There is a lot of learning experience in just getting this far.
Of course, I wasn't satisfied. This was the older Linux 2.4. I wanted to run the current Linux 2.6 kernel. I wanted to use Windows and Linux file systems on SD cards and USB drives. I wanted to experiment with tools to reduce the memory footprint of the system. I wanted a richer set of commands on the EK than what was provided out of the box. I wanted to port my Desperado embedded C++ library and run the unit tests. I wanted Linux to configure the Ethernet port automatically during boot.
In upcoming articles, I'll describe how to get Linux 2.6 running on the EK to do all that other fun stuff.
(Blogger sometimes truncates the right-hand portion of the photographs. You can always click on a photograph to bring a full-size version up in your browser.)
The EK is a single board computer (SBC) that is about 6.5" x 7.5" in size. It has an AT91RM9200 microprocessor, part of the Atmel AT91 family. The AT91RM9200 is a system-on-a-chip (SoC) that integrates an ARM920T RISC processor core with several special purpose cores that implement controllers for a variety of peripheral devices. The ARM920T is part of the ARM ARM9 family. It incorporates a real-time clock, a system timer, and a memory management unit (MMU). The EK has 8MB of flash, pre-programmed with the U-Boot boot loader, and 32MB of RAM. Peripheral devices include an Secure Digital (SD) card slot, two USB host ports, one USB gadget port, two DB-9 serial ports, one 10/100 Base-T Ethernet RJ-45 port, a video controller (which is the largest chip on the board) with a VGA port, a JTAG debugging connector, and some other goodies.
Here is a photograph of the EK hooked up to my development setup at the Palatial Overclock Estate (a.k.a. the Heavily-Armed Overclock Compound). You can see the beige serial console cable to the left, the blue CAT5 Ethernet cable front center, and the power supply to the right. Other accoutrements include a little fan (not really necessary, the EK runs pretty cool), a static mat and wrist strap (absolutely required), and a magnifying glass (because I'm old).
The EK is available retail in single quantities from any number of distributors for about $1250. (Yes, I know; I bought an absolutely immense Dell 530 quad-core server for less than this; economies of scale are at work here.) I purchased mine from Avnet. Here's what it looks like when the box arrives at your door.
The box contains (left to right, top to bottom): a European electrical cord, a U.S. electrical cord, a 12V power supply, the EK board in a static bag, a DB9S-to-DB9S null modem serial cable, a Type A-to-Type B USB cable, three DataFlash cards with sample systems on them, a CAT5 Ethernet crossover cable, and two CD-ROMs, one with software for the EK, and a Windows CE demo.
You can use the CAT5 Ethernet crossover cable to connect the EK directly to the Ethernet port on another computer. Instead, I connected the EK to a nearby Ethernet switch using a standard CAT5 Ethernet cable. I used the DB9S-to-DB9S serial cable to attach the console port on the EK to an old Windows ThinkPad laptop, and I used PuTTY to talk to the board. For sure, you will need access to the serial console, since much of not all of the work you will be doing on the EK will be in single-user mode. In a teaching laboratory with several stations, you might consider connecting all of the EKs to a reverse telnet server, which is common practice in the field for serial console ports on all kinds of devices.
The EK has a configuration strap, J15, that needs to be set to cause it to boot U-Boot from flash. This is described in the documentation that comes with the EK. (And this is why I needed the magnifying glass.) If you hold the board while you are grounded using a static strap so that the printing is right-side-up, J15 is in the bottom left quadrant on the board. It should be set to the right so that it connects the center of three pins to the right-hand pin labeled EXT. The photograph below is kind of fuzzy, but it shows you the correct orientation of the board.
The software CD-ROM contains a Windows Trivial File Transfer Protocol (TFTP) server utility, U-Bootable Linux 2.4 kernel images for both the EK and the older (and more expensive) AT91RM9200-DK boards, a corresponding initrd RAM disk root file system image, and a tarball of the tool chain. The tool chain includes the C cross-compiler environment which runs under Linux on a i386 platform, and generates code for the ARM9. I used an existing Linux server (a Dell 530) as both my development platform for the tool chain and as a TFTP server.
The U-Boot boot loader is widely used in embedded products. It is preloaded into flash on the EK. It is set up to boot the EK over TFTP. All you have to do is drop the linux-ek kernel image and the initrd ramdisk root file system image from the CD-ROM in appropriate directory on your TFTP server, administer U-Boot with the parameters for your network, and run some predefined U-Boot commands.
Here is the initial U-Boot dialog that you will see on the console when you hit the reset button on the EK. U-Boot is waiting for you to enter a command.
You will need to use a series of U-Boot setenv commands to configure U-Boot by setting parameters in the form of keyword value pairs. Then use the U-Boot saveenv command to save your settings in non-volatile flash so that they persist across resets. Finally, you can use the U-Boot printenv command to see all of your saved settings. This is described in the Getting Started guide on the software CD-ROM. Use the printenv command first to see what parameters might already be set. (There is a typo on the first page of the guide: when setting the bootargs parameter, there is a space instead of a comma between 115200 and mem.)
You will likely want to replace the IP addresses in the guide for the parameters ipaddr, the static IP address of the EK, and serverip, the IP address of your TFTP server. Here are the commands I used.
setenv ipaddr 192.168.1.223
setenv serverip 192.168.1.102
The guide also shows you how to define long U-Boot command sequences, save them as variables, and then run them. I followed the manual and defined the commands kernel to download the kernel image, and ramdisk to download the ramdisk image. This is useful to save time in the long run, although don't hesitate to try using the raw U-Boot commands. (The guide doesn't show using single quotes to enclose strings with embedded spaces as the value portion of the U-Boot setenv command, but I've used that practice on U-Boot on other projects in the past.)
Below you can see how the U-Boot printenv command displays all the settings for my EK.
To boot the board, you need to tell U-Boot to use TFTP to load the kernel image into memory, then load the ramdisk image into memory, then finally to boot the board. U-Boot boots the board by literally calling the kernel image as a subroutine and passing to it the address of the ramdisk image as a parameter.
First, I download the kernel image linux-ek from the TFTP server to memory location 0x21000000 using the command kernel that I defined.
Next, I download the ramdisk image ramdisk from the TFTP server to memory location 0x21100000 using the command ramdisk that I defined.
Finally, I tell U-Boot to boot the kernel image at location 0x21000000 using the bootm command. You can see below that Linux 2.4 boots and I log into the system.
Using the EK right out of the box, I was able to compile "Hello, World!" on my Linux PC using the arm-linux-gcc command in the provided tool chain, download the resulting ARM executable to the board using TFTP from the shell prompt on the EK, and run it on the EK. There is a lot of learning experience in just getting this far.
Of course, I wasn't satisfied. This was the older Linux 2.4. I wanted to run the current Linux 2.6 kernel. I wanted to use Windows and Linux file systems on SD cards and USB drives. I wanted to experiment with tools to reduce the memory footprint of the system. I wanted a richer set of commands on the EK than what was provided out of the box. I wanted to port my Desperado embedded C++ library and run the unit tests. I wanted Linux to configure the Ethernet port automatically during boot.
In upcoming articles, I'll describe how to get Linux 2.6 running on the EK to do all that other fun stuff.
Subscribe to:
Posts (Atom)
