Effective Terminal Windows

This one's for all the terminal junkies out there.

I have a tendency to open about 10-20 terminal windows at a time, and it gets hard to track which terminal is in use for which ongoing project. The defaults for my distro are to put a ridiculously long and useless title on the terminal, and the prompt shows the entire working directory. Titles get really long when the directory structure is nested more than 8 or so levels. I did a little searching and found the right set of configuration commands for bash to make my terminal titles and prompts more useful for me. Now my title shows the current working directory name, and the prompt shows at most 6 levels (the current directory and its 5 ancestors).

Add the following after the definition of PS1 in .bashrc to get my configuration:

# If this is an xterm set the title to the current directory name
case "$TERM" in
xterm*|rxvt*)
    PS1="\[\e]0;${debian_chroot:+($debian_chroot)}\W\a\]$PS1"
    ;;
*)
    ;;
esac

# cut off really deep prompts
PROMPT_DIRTRIM=6

Add a pseudo instruction to gem5

An important aspect of many computer architecture projects is to modify an instruction set, often to extend the instructions with a new instruction that implements a proposed feature. I'm working on moving some of my research to the GEM5 open source simulator, but first I need to get an idea of the level of effort involved. My first move is to figure out how to add new instructions.

GEM5, being designed especially for computer architecture research, has a well-defined set of pseudo instructions that can be extended to serve my purposes. However, there are not really any instructions on how to extend these instructions. The few emails that I could find about pseudo instructions basically just said go look at what is implemented and extend it. So that is what I did. For posterity, I'll relay my findings here. Maybe they will be helpful to others, or to myself in the future.

The pseudo instructions are useful for implementing functional simulator features that can use a multiple-register instruction. The main drawback is that the pseudo instructions are not integrated tightly with the pipeline and are executed non-speculatively, so if the rate of your new instruction is quite high, the cost could be misleading if doing performance evaluations of the new feature. For my work, the pseudo instruction is fine; I have previously done a very similar implementation for functional simulation with Simics/GEMS.

Adding a new pseudo instruction (for X86)

I'm interested primarily in the X86 full-system simulation capabilities of GEM5 at the moment, so my effort is in that area. However, the pseudo instructions have implementations in the other architectures, and most of the following will translate directly to them.

• Overwrite a reserved opcode in src/arch/x86/isa/decoder/two_byte_opcodes.isa near the other pseudo instructions (look for m5panic).
• Add the instruction’s functional simulation implementation in src/sim/pseudo_inst.cc
• Add the function prototype in src/sim/pseudo_inst.hh. The function prototype will define the available registers for parameters and return values based on the compiler’s calling conventions for the architecture.
• Create an m5op for easily emitting the instruction in compiled code.
• Add function number in util/m5/m5ops.h
• Add function prototype in util/m5/m5op.h
• Instantiate a TWO_BYTE_OP in m5op_x86.S

I have written a simple example that implements addition as a pseudo instruction. The patch may bit-rot, but the idea should be easy enough to follow.

To use the new pseudo instruction call the function declared in util/m5/m5op.h. Then (cross-)compile your source code with the m5 utilities like:

  gcc -o foo foo.c -I ${GEM5}/util/m5 ${GEM5}/util/m5/m5op_x86.S

To get your code into the simulation, you can

• add the binary to the disk image 
• sudo mount -o loop,offset=32256 /dist/m5/system/disks/linux-x86.img /mnt/tmp
• cp foo /mnt/tmp/bin
•  or read it directly into the simulation 
• build/X86/gem5.debug configs/example/fs.py -r 1 --script=foo
• m5term localhost 3456
• m5 readfile > foo
• chmod +x foo
• ./foo

Adding to the disk image requires restarting the simulation, whereas if you have a checkpoint loaded you can read the file in directly using m5 readfile.

Executing the pseudo instruction on real hardware

You can also use your new pseudo-instruction in real hardware by providing an illegal instruction handler (SIGILL handler) that emulates the functionality of the instruction. This may be useful for debugging purposes, since native hardware can run the emulation code much faster than the simulator will. I have written a simple example that shows how to handle the illegal instruction signal that gets caused when the pseudo instruction is executed. This sample example will execute in both GEM5 and natively (on a 64-bit X86).

I guess that covers it for now. Happy hacking!

RTEMS on gem5 SPARC

I previously wrote about booting RTEMS on M5 (Now gem5) SPARC_FS. I am following up on this work in preparation for the release of RTEMS 4.11, which will hopefully be coming soon. I compiled RTEMS (with two small patches) and booted two samples on gem5 and on Simics Niagara.

On the simulator side, the instructions I gave previously continue to work for booting both OpenSolaris and RTEMS. I updated some of the links in the prior post to reflect the change in host to Oracle for the OpenSPARC tools. One issue I did not notice at first is that the port for the console to connect m5term to the gem5 simulator is port 3457.

I successfully built and booted hello and ticker with the niagara BSP. There are a few patches that need to be applied to RTEMS, but hopefully I can get those patches committed before releasing 4.11. Ideally, the RTEMS 4.11 will be able to compile and boot with gem5, giving the RTEMS community an open-source simulator for testing.

Interestingly, the ticker appears to count time. I'll have to take a look at how gem5 simulates the (s)tick register. Simics does not simulate the timer with any accuracy.

I think Qemu would be a nice target simulator for some future endeavors, but I do not have the time to investigate the feasibility of running RTEMS on the Qemu Sparc64.

screen

I finally learned how to use screen, a terminal windowing program that can detach so its windows run as a background task. When you detach, screen returns you to your shell. Detaching allows me to start work on a server from my lab workstation in a screen session, detach screen, logout and turn off my workstation, go home, and resume the same screen session from home.

Start screen with

$> screen

Once inside screen, the windows act mostly like a terminal, but now you can issue commands to screen using Ctrl-a and a command key. The useful keys that I have been using are:

• Create a window (Ctrl-a c)
• Next (Ctrl-a n) or Previous (Ctrl-a p) window.
• Detach (Ctrl-a d)

To start screen with a previously detached session, first find the session with:

$> screen -ls 

There are screens on:
    11999.pts-0.localhost    (Attached)
    17129.pts-3.localhost    (Detached)
$> screen -r 17129.pts-3.localhost

The -r flag resumes the detached screen session.

Detaching is useful especially for long-running programs or for conserving the state of many terminal windows.

Profiling C++ applications: class composition

In the latter half of last year, my research went down an OOP path especially in the direction of C++; both the hardware containers project and my thesis touch elements of OOP concepts. With the hardware containers we were interested in how C++ developers use inheritance, composition, and encapsulation. For my thesis work, I was interested in how applications use the STL; I wrote an appendix in my thesis describing this aspect. For this post, my focus is on the hardware containers work, which is in my paper pipeline waiting for submission.

I found 21 free and commercial (oxymoron?) open-source C++ programs for this investigation: dimacs-sq, Dijkstra's algorithm; Opal and GEM5, processor simulators; Geant4, physics particle simulator; FlightGear, flight simulator; Wesnoth, video game; OpenCV, computer vision library; Boost, library for C++; MySQL, database server; LibreOffice, office productivity suite; Doxygen, documentation generation; Haiku, OS based on BeOS; ReactOS, OS based on Windows NT; Chromium, web browser; povray, soplex, dealII, namd, xalancbmk, astar, and omnetpp, C++ benchmarks from SPEC CPU 2006.

Using synthetic microbenchmarks, Eugen and I determined that the important C++ code behavior attributes that affect performance when using hardware containers are the ratio of private access specifiers to total number of class variables, depth of inheritance, number of objects a class includes by value, and number of public accessor methods that expose private variables. Nicely enough, all of these can be determined by examining source code: no need to run the C++ programs!

I used two tools to analyze the 21 programs: Understand by SciTools, and CCCC. The former is commercial and comes with an evaluation license, which was enough for me to get the data I wanted; the latter is open-source, which was good enough for me to modify to get data I wanted. I used Understand! to measure the ratio of private:class variables and the depth of inheritance, but the tool did not provide enough data for the objects included by value or for accessor methods. Ultimately I did not get any data for the latter, but I was able to hack CCCC to measure how many objects a class includes by value.

For the composition of classes I used my modifications to CCCC to count how many classes each class includes by value. On average, classes do not include very many objects of other classes by value (perhaps by reference), although large outliers exist. The chart shows the average number in orange, with one standard deviation as an error bar; the maximum among all the classes is in blue.

I used both CCCC and Understand to calculate the inheritance tree depth of these C++ programs. Using both tools showed some difference in the tool quality, since for a metric as simple as inheritance depth the two tools should get identical numbers. The following chart shows the maximum depth of the inheritance tree reported by each of the two tools with CCCC in blue and Understand in orange.

 

Although the tools occasionally agreed, vastly different numbers were obtained for lots of the programs. The maximum inheritance depth is less than 10 for almost all of these programs, with small (near 1) averages and standard deviations. Thus most classes are decoupled with small inheritance and composition factors, but some strong outliers do exist. For hardware containers, we can treat the outliers as a special case and make safe (enough) assumptions about an object's composition.

Web site update

Last night I decided to provide an html version of my CV, and then I remodeled my website. The old version was ugly and broken; the main problem were my iframes. I simplified the design, tried to make it mobile-friendly, and reduced the content. I kept my basic design elements (boxes), and tried to eliminate cruft. I think the product is leaner and cleaner.

Downloading starred emails from GMail to apply git patches

Now that RTEMS is using git I frequently have to apply patches received by email, but GMail lacks a web interface for downloading selected emails. The conventional wisdom for how to apply a patch from an email is to "show original", save the page, manually remove the first blank line, and then use git-am to apply. Now do that ten times for a series of patches. How tedious!

So I wrote fetch-flagged-email—a small Python application—to accomplish my goal. Now I star patches in gmail and then run fetch-flagged-email.py followed by git-am. The script does the heavy lifting of saving emails to files in sequential order to a directory of my choosing.

productivity++;

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.

When to make thesis slides

I've been working on my thesis proposal for awhile now, and I even took one attempt at writing it which turned out to be a bit premature. My advisor suggested that I consider making my proposal defense slides before I write the proposal. I have now finished my first iteration on the slides and found it to be a most useful exercise. The content of my slides covers what I plan to address in my proposal, although the presentation needs a unifying story to tie everything together. A presentation should have a strong motivation and story because it is important to hook the audience in the first couple of slides and to keep them engaged throughout.

My feeling is that if I start by writing my proposal, I would have a sub-par narrative that would be weak when translated to a presentation. I usually start writing with an outline, then I fill in the technical details, results, and conclusion, then write the background material: introduction, motivation, and related work.  Making the presentation slides first will allow me to follow a single story throughout the proposal.

The act of thinking about how to present my work makes me consider more deeply both the organization and narrative than when I sit down to write. By expending more energy on the why and less the how, I can focus on a narrative that puts my proposed work in context and motivates my contribution. After I finish my slides, I will write my proposal using the slides as a guideline. This approach should yield a concise, readable proposal with a flow that is consistent with the presentation.

I also expect that most of my slides will be reusable for the thesis defense (and potential job talks), since the motivation and high-level ideas will be largely unchanged. Although some details and results will change, these will amount to a small delta in the presentation that will be easy to update.

Traps, Interrupts, and Exceptions in GEMS

Today, someone asked on the gems-users mailing list the question, "How does GEMS simulate traps?" I gave my best answer, and the topic is a good prelude to an upcoming post I'm planning.

GEMS is a computer hardware simulator, and I have discussed it previously. Simics/GEMS is primarily a three-headed monster: Simics, Opal, and Ruby. Simics+Opal implement the processor simulator, and Ruby implements the memory hierarchy for multicore platforms. My work primarily uses Simics+Opal, without Ruby.  Opal is a "timing-first" simulator based on TFsim. It implements most of the processor model, but relies on the functional simulator (Simics) to verify simulation correctness and to provide some of the harder-to-model processor features.

One of the harder-to-model features of modern processors is the exception/interrupt handling mechanism. In the SPARC-v9 architecture, these are both referred to as traps. Opal models trap handling for a subset of the possible traps, including register window traps, TLB misses, and software interrupts. All trap handling is done in the retire stage of the instruction window, which allows speculation past traps. Non-modelled traps in Opal, for example I/O, rely on Simics to provide the functional implementation of taking the trap and updating the architected state. Modelled traps simulate the trap handling algorithms and should result in the same architected state as functionally correct trap handling.

Modelled traps improve simulation accuracy. In-flight instructions are squashed, the program counter (and other register state) is properly updated, and Opal continues to execute the workload. Simulator correctness depends on the ability of Opal to generate the same traps as Simics, and simulator accuracy requires Opal to model the effects of taking the trap.

That's all for now. In the near future, I will be expanding on this topic to discuss how to add new traps to Simics/GEMS.

Architectural simulators

As a researcher in the areas of operating systems, compilers, and computer architecture, I spend a lot of time dealing with simulators.  An inordinate amount of time.  Much of this time is spent figuring out how well a given simulator provides:

1. Useful timing measurements (cycle-accurate)
2. Support for fully functional OSs (full-system)
3. Auxiliary features for specific experiments
4. Support for useful hardware platforms and instruction sets
5. Openness to modifying microarchitectural features
6. Availability of technical support

In my current work, I'm interested in actively developed simulators that support cycle-accurate full-system simulation with a detailed memory hierarchy on out-of-order uniprocessor or multicore RISC architecture models with the SPARC, MIPS, or ARM instruction sets that supports extending the pipeline and instruction set.  The rest of this article discussed my efforts in finding simulators to meet my needs.

Interrupt Handling with MMU Hardware on an MMU-less OS

This post describes some work that I have just recently gotten to a point that it seems to be correct.  It was a long-running project that started around May 2010.

A week in M5

I spent the last week or so playing around with a relatively new simulator called M5.  It is a very nice simulator, especially for architectural research.  My interest in it is to use it for doing both operating system and architecture research.  This type of research is difficult to do with most simulators, because fully functional simulators rarely provide accurate timing to evaluate overheads, while timing simulators rarely provide sufficient functionality to run an operating system.  What is needed is a full system simulator that provides fidelity for both functionality and timing.

In the past our research group has used SimpleScalar for architectural research.  However, that project is obsolete and the simulator is slowly becoming obsolete with respect to real-world systems.  Also, it does not provide full system simulation, although a set of patches by Jack Whitham merges RTEMS and SimpleScalar to provide full system simulation for RTEMS.  I tried to use Jack's patches, but I could not quite get everything working.  When I sent him an e-mail to ask about it, he suggested that I should look at M5 as a more realistic simulator instead.  So I did.

M5 provides two types of simulators: Full System (FS) and Syscall Emulation (SE).

vim Productivity

I use vim.  Not because I think it is inherently superior to emacs or any other full-featured editor/IDE, but because I learned it first.  A fellow vim user and friend of mine tried emacs out for about a semester+ and his experience was that they are roughly equivalent after learning how to use each, so I stick with vim.  The only real difference between the two is the command syntax

Through working on various projects, I have gathered a few tricks, tips, and features to improve my productivity while using vim.  The rest of this post is a semi-tutorial and repository of my vim usage.

Built-ins:

• .vimrc
• Modes
• Cut-Paste
• Find-Replace
• Jumping Around 
• Split
• Auto-Format 
• Shell commands

Plug-ins:

• Latex-suite
• Cscope
• changelog

Scripting with Lua

For about two weeks, I've been planning to put together a way to generate test cases for one of my current projects. The project involves adding new capabilities to the RTEMS scheduler, and to test it I need to create RTEMS applications that spawn various periodic and aperiodic tasks. I already had written two such applications by hand, but I found it tedious to generate the parameters.

At a high level, the parameters are task type (periodic or aperiodic), duration (execution time), period, relative deadline, and release time (a.k.a. phase). To spawn tasks, I had some arrays defined in my RTEMS code of length equal to the number of total tasks. These arrays hold the values of the period, priority (relative deadline), release time, and execution time. Then my code uses the arrays to generate tasks with the given parameters. This isn't too difficult to write up by hand, but my project also requires that I compute some runtime characteristics of the periodic tasks.

Extensible Data Structures in C

A lot of systems programming code is done in C, primarily because of the exposure of explicit memory addresses, but for other reasons too. However, C has pretty poor language support for many of the helpful programming constructs in object oriented languages that improve code re-use and readability, for example generics/templates, polymorphism, and inheritance. So systems programmers have developed a few design patterns to emulate such language constructs using C.

Lately I've been looking at how to design data structures in C that can provide flexible storage for data elements that can be used by different consumers. In particular, I'm looking at how a thread control block can provide storage for different implementations of scheduling systems.

There are three features of C that appear useful for this purpose: void pointers, unions, and typedefs.

union works well when you know exactly what type of data the different consumers will use ahead of time, and you are willing to place multiple specifications within the data structure. The advantages of union are that it is easy-to-read and efficient, providing multiplexed storage space to different data structures. Some disadvantages are that the programmer has to know which field of the union to access, and the size consumed by the union is equal to the largest member.

void pointers are type-less memory addresses, so a programmer can assign the value of the pointer to point to any structure, and later retrieve what was stored. However, as with unions, the programmer must know the type of the structure pointed to by the void pointer in order to use the structure. This usually is not a problem for the scenario I'm investigating.

typedefs provide a way to define new types for structures and primitives. They allow programmers to define opaque types whose representation can change, but whose type can always be checked. They have the advantage over union and void pointers of being able to be type-checked. The way to use typedef to provide extensibility is to combine it with C pre-processor conditional compilation to control which typedef is used. This way, multiple typedefs of the same type can be defined, and only one will be used based on pre-processor defines. However, code that uses the generic typedef may need to provide multiple cases based on the different specific typedefs provided.

I may come back to this topic and provide some examples. I'm playing around with typedefs right now, and like this approach because the ugliness can be hidden and the end result is high-performance code with little bloat in the compiled version.

Introduction to RTEMS

I will probably have quite a few posts related to RTEMS, so I thought an introduction would be appropriate. I've been doing a lot of work recently on a project with Eugen, a fellow Ph.D. student, to port the RTEMS Operating System (related blog) to the UltraSPARC T1 Niagara, a 64-bit SPARC-v9 processor.

RTEMS is a real-time operating system (RTOS), which means that its operations can be precisely and accurately timed and that it supports applications that have strict timing requirements.  Classes of such applications range from control systems to streaming data processors. Examples that we see (or don't see) everyday are embedded in such things as planes, trains, and automobiles, or multimedia video and audio devices.

RTEMS is notable for a few reasons. First, it's free and open source. Second, it supports a large number of target architectures (platforms). Third, it is in space!  Some of the platforms that RTEMS supports are radiation-hardened for outer space, and it is on some of the NASA and ESA equipment floating around up there.

But I don't plan to be a rocket scientist. My interest in RTEMS is for its support of a variety of computer architectures, including the SPARC-v8 architecture.  Eugen and I have identified the Niagara as a promising architecture with which to continue our current research direction, and we wanted to have a low-level OS that is small enough to understand.  Thus we chose RTEMS and started porting the existing support for SPARC-v8 to the newer SPARC-v9. This has been an ongoing effort for awhile, but we have made quite a bit of success, and hope to contribute our work back to the RTEMS community.

If you want more info about RTEMS, check out its website, which is newly updated.

Versioning my work

I've found it helpful to keep around clean and working versions of projects that I edit, especially when I am changing someone else's work.  This is suggested behavior for generating patches for open source projects, but I find it useful for both programming and document editing.

Of course, version control (CVS or subversion) helps, but I don't always want to commit my changes back to the repository. Someday I should also investigate a distributed version control system that lets other users "check out" your branches.  However, most of the projects I work on use cvs and svn. I also like to extract the changes that I've made, in order to keep track of my versions by hand.  This is useful when I reach milestones in projects, and I want to make off-line backups.