OT: Gas Psychology

xkcd points out that the cost of saving money on gas in the time it takes to drive out of your way will rarely be worthwhile. The alt text goes further to state that if you drive an average car more than a mile out of the way for each penny per gallon saved you are spending more on gas than you are saving. I was intrigued so I did a little number crunching.

Suppose I can get gas for $4.00 per gallon without going out of my way, and that I usually get 10 gallons of gas. Results will fluctuate depending on the base price and the amount of gas purchased. Here is a chart showing the farthest I can drive before I start to lose money.

Max distance to travel before losing money. Each line represents a different average miles per gallon from 10 m.p.g. to 50 m.p.g.

Taking a vertical slice out of the middle we can see how far to drive when the gas prices are 10 cents apart:

Max distance to save 10 cents per gallon

I also noticed that (at 10 gallons of gas and with $4.00 base) the alt text is correct for vehicles that get up to 40 mpg. At 40 mpg the break-even point is almost exactly 1 mile of travel for each penny per gallon saved. For my car, which gets about 20 to 25 mpg, the break-even point is about 1/2 mile for every penny saved.

multilib

Back when Eugen and I were porting SPARC-V9 to RTEMS, we had to consider the compiler tools for cross-compiling RTEMS to the target architecture. One of the issues was that RTEMS uses the multilib feature of GCC for building architectural variants, so we should consider the multilib options for SPARC-V9 and submit patches to add support for the desired multilibs to the rtems-sparc64-gcc.

What are multilibs?
The GCC manual doesn't say anything other than to identify the flags that use multilib. Google isn't terribly helpful here either. The automake manual has this to say:

18.3 Support for Multilibs

Automake has support for an obscure feature called multilibs. A multilib is a library that is built for multiple different ABIs at a single time; each time the library is built with a different target flag combination. This is only useful when the library is intended to be cross-compiled, and it is almost exclusively used for compiler support libraries.

The multilib support is still experimental. Only use it if you are familiar with multilibs and can debug problems you might encounter.

Hardly helpful.

So we ignored multilibs and moved on. That was fine, although to this day the sparc64-rtems-gcc does not support multilibs. If a tighter integration of the sparc64-rtems-gcc and BSPs becomes important then this issue might be worth re-visiting. But I still had little knowledge about multilibs.

multilibs are...
It turns out that multilib is common, although most end users won't notice them. multilib is the process by which a library is built multiple times, each with a different set of compiler flags. That means a library can be linked to applications built with similar flags, which may be necessary in case the compiler flags change the ABI (application binary interface). An example is compiling legacy 32-bit applications on 64-bit machines: current Linux distros ship GCC with a 32-bit multilib, so the GCC libraries are available for compiling 32-bit applications. On a 64-bit computer without a 32-bit multilib gcc cannot compile 32-bit programs.

RTEMS adds multilib flags to its rtems-flavored gcc compilers to allow RTEMS to link to GCC libraries that best support the target hardware. For users of existing board support packages (BSPs), the multilib is invisible: the BSP specifies compiler flags (in make/custom/somebsp.cfg), and rtems-gcc links the right library. However, BSP developers should ensure that critical flags specified by the BSP match an available rtems-gcc mulitlib or else a new multilib should be contributed. The gcc flags will pull in a multilib if there is a match in gcc-print-multi-lib

On the RTEMS multilib page there is also an explanation of how RTEMS can build its own multilib library, the librtemscpu.a. Building a multilib RTEMS is mostly useful to save a little time and space when compiling many variants of the same processor family, for example multiple BSPs from the same CPU. Perhaps I'll follow up sometime to discuss RTEMS' librtemscpu.a

Red Black Trees: Bottom-Up or Top-Down?

Conventional red-black trees are bottom-up: nodes are inserted/deleted at the bottom and coloring properties are corrected up. Last year I found a tutorial describing a top-down approach claiming it is superior in terms of simplicity, ease of understanding, code size, and theoretical efficiency. Unfortunately these claims are unsubstantiated. Being curious I investigated further. I implemented an iterative bottom-up red-black tree (with parent pointers) and compared it with the top-down approach.

Since complexity increases with code size, I used sloccount to measure the code size. For the top-down approach, the Total Physical Source Lines of Code (SLOC) = 131. For bottom-up, SLOC = 189. So far the evidence does favor a top-down approach for being less complex.

But what about efficiency? (Speed is King!) The tutorial claims that a top-down approach makes a single pass of the tree and so is theoretically more efficient.

I wrote a simple testing program that generates and inserts (pseudo)random numbers as keys in a red-black tree and then removes them. The program takes wall time measurements with gettimeofday before and after both blocks of insertion and removal. Using wall time is crude but serves for this demonstration. By dividing the total time of insertion (removal) by the number of keys I compute the average cost per insertion (removal). I ran the testing program 10 times and averaged the per operation costs for top-down and bottom-up for an increasing tree size from between 100 and one million nodes. The following two images show the results (smaller is better):

The top-down approach has a worse average time for both inserting and removing nodes. I did not bother with statistical rigor, but the gaps were larger than a few standard deviations of the measured data.

Although my experiments were far from complete I opted to use the more established, more familiar, and (apparently) more efficient bottom-up approach in an implementation of red-black trees that is now part of the RTEMS kernel.

If I had to guess why the top-down approach performs worse I would say it is pessimistic in how many tree rotations it does. The bottom-up approach seems to make about as many tree rotations as there are nodes. (I believe the number of rotations is bounded to 2 for insert and 3 for remove, but on average it appears to be 1/2 rotation per insert/remove.) The top-down approach makes about 2-4 times as many (albeit simpler) rotations, and I have no idea if the bounds apply.

Principles, principals, and protection domains

Recently, I've had some time to think about computer security as I wrap up a book chapter that I'm co-authoring on the topic. I recall my initial exposure to three fundamental security concepts: the principle of least privilege, principals, and protection domains.  These three concepts appear in practical computer security, have been around for a long time (longer than me), and are intricately related. This post explores the relationship among the three as they relate to one aspect of my research.

The classic paper by Saltzer and Schroeder [1] was my first introduction to these concepts; I highly recommend this paper for anyone even slightly interested in computer security. Butler Lampson's pages on Protection [2] and Principles [3] also have good information.

Let's start with definitions [1].

Principle of Least Privilege (POLP): Every program and every user of the system should operate using the least set of privileges necessary to complete the job.

Principal: The entity in a computer system to which authorizations are granted; thus the unit of accountability in a computer system.

Protection domain: The set of objects that currently may be directly accessed by a principal.


The logical conclusion of the POLP is that every principal should be as small (fine-grained) as is feasible, and every protection domain should be minimal for each principal. But in general as things get smaller and more numerous, managing them gets harder.

Lampson has argued against the POLP. His argument is that if "the price of reliability is the pursuit of utmost simplicity," as Hoare famously said, and if reliability is required for security, then enforcing the finest granularity of privileges is wrong because it introduces complexity thus reducing reliability.

So an open challenge in computer security is supporting fine-grained privileges without introducing complexity (or overhead).

Privileges are inherent to both principals and protection domains. In *nix, the "user" (account) is the principal. All processes having the same user can access the same persistent objects, but not temporary objects outside of process context. So files are accessible with user rights, but not per-process open file descriptors. So who is the principal—the user or the process?

I think it is really about multiple "contexts" within a single computer system. In one context, the principal is the user, and the protection domain is the set of persistent objects that are managed by the OS (files, programs). In another context, the principal is the process, and the protection domain is the set of objects "in use" by the process (file descriptors, process address space). These two contexts are muddled by interfaces like /proc, which allow users to access process context, and also because a process has the user's privileges when accessing persistent objects.

By thinking in terms of multiple contexts that align with principals, I can more easily think about how user/process principals fit with other principals, such as the coarser-grained machine principal seen in network protocols or finer-grained principals like threads, objects, or even procedure invocations. Each principal has an associated protection domain and can co-exist with overlapping principals.

Pushing the POLP toward its limits is one aspect of joint work I have done: hardware containers [4,5] support procedure invocations as a fine-grained principal, and we have argued that software can reasonably manage permissions to establish tightly-bounded protection domains.


[1] J. H. Saltzer and M. D. Schroeder, “The protection of information in computer systems,” Proceedings of the IEEE, vol. 63, no. 9, pp. 1278-1308, 1975. Available at: http://www.cs.virginia.edu/~evans/cs551/saltzer/

[2] B. Lampson. Protection. Proc. 5th Princeton Conf. on Information Sciences and Systems, Princeton, 1971. Reprinted in ACM Operating Systems Rev. 8, 1 (Jan. 1974), pp 18-24. Available at: http://research.microsoft.com/en-us/um/people/blampson/08-Protection/WebPage.html

[3] In Software System Reliability and Security, Proceedings of the 2006 Marktoberdorf Summer school. Available at: http://research.microsoft.com/en-us/um/people/blampson/74-PracticalPrinciplesSecurity/74-PracticalPrinciplesSecurityAbstract.htm

[4] E. Leontie, G. Bloom, B. Narahari, R. Simha, and J. Zambreno, “Hardware Containers for Software Components: A Trusted Platform for COTS-Based Systems,” in Computational Science and Engineering, IEEE International Conference on, Los Alamitos, CA, USA, 2009, vol. 2, pp. 830-836. Available at: http://home.gwu.edu/~gedare/publications.html#

[5] E. Leontie, G. Bloom, B. Narahari, R. Simha, and J. Zambreno, “Hardware-enforced fine-grained isolation of untrusted code,” in Proceedings of the first ACM workshop on Secure execution of untrusted code, Chicago, Illinois, USA, 2009, pp. 11-18. Available at: http://home.gwu.edu/~gedare/publications.html#

Writing and Reading

I've been writing a lot lately, and thinking about writing, and reading about writing, and now writing about writing; I'll spare you from any writing about thinking.

As I (re)learn more about proper English, I find that poor usage now grates on me. My ability to read efficiently suffers because I am now aware of improper writing—I keep reaching for a pencil to make edits!

I only hope I can learn to choose to read with a critical eye or not. Ignorance is bliss.

Properly attired yogurt is delicious

In the grocery store today I impulsively bought some plain yogurt and a box of granola (oats & honey) with the idea—surely not original—to combine them with some blueberries and a bit of strawberry jam. The result is a delicious summertime snack that I am enjoying as I write.

The recipe is simple:

1. (Optional) Mix a dollop of jam with plain yogurt.
2. Combine equal parts yogurt, berries, and granola.
3. Eat.

I can has Knuth?

As I was working on my thesis, Misty decided my computer was a nice place to nestle. Then she decided TAOCP was interesting; after all, I was reading from it.