tag:blogger.com,1999:blog-47684045852977497112024-02-02T12:21:26.368-05:00A Computer Scientist's QuestSome of my thoughts and experiences in academia and life.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.comBlogger67125tag:blogger.com,1999:blog-4768404585297749711.post-76056799558849388392013-12-10T11:50:00.000-05:002013-12-10T11:51:29.446-05:00Effective Terminal WindowsThis one's for all the terminal junkies out there. <br />
<br />
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).<br />
<br />
Add the following after the definition of PS1 in .bashrc to get my configuration:<br /><br />
<pre>
# 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
</pre>
<br />Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com2tag:blogger.com,1999:blog-4768404585297749711.post-73120324755298002022013-10-03T09:09:00.000-04:002013-10-03T09:09:00.053-04:00Software product country of origin (COO)Late last year, US Customs (<a href="http://en.wikipedia.org/wiki/U.S._Customs_and_Border_Protection">CBP</a>) issued an advisory ruling regarding how to determine the <a href="http://en.wikipedia.org/wiki/Country_of_origin">COO</a> for software products when software is developed partially in a country not listed in the <a href="http://en.wikipedia.org/wiki/Trade_Agreements_Act_of_1979">Trade Agreements Act</a> as a designated country. For example, China is not a designated country. A fair description has been written up <a href="http://www.governmentcontractslawblog.com/2013/02/articles/baa-and-taa/country-of-origin-for-computer-software-us-customs-finally-sheds-some-light-on-the-issue/">here</a>. The ruling provides a template for labeling the COO as a designated country despite using source code developed in a non-designated country.<br />
<br />
The reason software companies would want to certify their product's COO as a designated country is so they could sell their software to the US Government. The main problem is that competitors (or whistleblowers) can sue under the <a href="http://en.wikipedia.org/wiki/False_Claims_Act">False Claims Act</a>. Significant damages can be awarded if the court finds the COO is not correct.<br />
<br />
Now the companies that want to label their software COO as a designated country can get a better chance at either defending such claims or getting a binding ruling from CBP. These companies are scrambling to hire law firms to determine if the advisory ruling can help, to seek a binding ruling from CBP, and to otherwise gather evidence to use to back COO claims. I consulted for <a href="http://www.blankrome.com/">BlankRome LLP</a> to help them with just such a task. In particular, I examined their client's software development processes to help determine whether and how they fit the template, and to see what evidence there is to claim that the software product is "Made in the USA" despite the fact that much of the software, in terms of source code, has been written in China. While the details of my engagement (who, what, how) are covered by an NDA, I can give some high-level intuition on the issue.<br />
<br />
At first blush, it seems counter-intuitive that the bulk of software can be written in one country, while the end product claims to be another. The defensible stance, however, is to claim that the creativity and human knowledge required to make the software comes out of the design, requirements specifications, and testing/validation. The key seems to be that experts in the US should be involved in making decisions both about how the software is written and in selecting the code modules to use.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-47210599890960229422013-05-30T09:25:00.004-04:002013-05-30T09:25:51.017-04:00Congratulations RTEMS GSoC 2013 StudentsCongratulations to the accepted students in GSoC 2013 for the RTEMS Project! We had many fine applicants again this year, and were able to accept 9 students to do projects with us this summer. In alphabetical order by project name, we accepted these students/projects:<br />
<ul>
<li>Shubham Somani</li>
<ul>
<li>Application Configuration GUI for RTEMS.</li>
</ul>
<li>Deng Hengyi</li>
<ul>
<li>Atomic Operations and SMP lock debug tool for RTEMS</li>
</ul>
<li>Dhananjay M Balan </li>
<ul>
<li>Better debugging support for RTEMS in GDB.</li>
</ul>
<li>Hesham Moustafa AL-matary</li>
<ul>
<li>Enhance low-level API of libmm (Memory Protection & Caches)</li>
</ul>
<li>Philipp E</li>
<ul>
<li>Paravirtualization layer in RTEMS</li>
</ul>
<li>Jin Yang </li>
<ul>
<li>Porting CAN driver, LinCAN, to RTEMS</li>
</ul>
<li>Peng Fan </li>
<ul>
<li>RTEMS Runtime Loader</li>
</ul>
<li>Sree Harsha Konduri </li>
<ul>
<li>SMP Aware Scheduler</li>
</ul>
<li>Vipul Nayyar </li>
<ul>
<li>Unified APIs</li>
</ul>
</ul>
These are all important, ambitious projects that will be of great benefit to RTEMS if successful, and will definitely teach the students a lot about project management and open source development.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-55404909631298387852013-05-09T13:04:00.000-04:002022-03-09T16:34:21.776-05:00Who's calling me? Visualizing function callersMy problem today was to determine and visualize the set of functions (callers) that call another set of functions (callees). For this purpose, I knew the callees function names all started with the same word, say "Callee", and that none of the caller's names start with Callee. For C programs, <a href="http://en.wikipedia.org/wiki/Namespace#Emulating_namespaces">namespaces are often formed by a coding convention</a> that specifies the format of function names and groups related functions by a common "first name".<br />
<br />
I found a simple tool, <a href="http://www.gson.org/egypt/">egypt</a>, that relies on gcc and GraphViz to generate a visualization of a program's static call graph. A call graph is a natural way to visualize what I need, but my requirements are slightly different than the usual. Normally a call graph will include all of the directed edges from callers to callees in an entire program or subset of its functions. What I need is just the nodes of immediate callers of the Callee functions, that is, the subgraph <a href="http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs">induced</a> by the caller and callee vertices in the call graph. <br />
<br />
For my needs, the tool lacks the ability to specify a set of vertices and generate the subgraph they induce. The induced subgraph could be found if I could:<br />
<ul>
<li>specify terminal nodes (callees)</li>
<li>filter nodes that do not have an edge to terminal nodes</li>
</ul>
Rather than implement this ability, I realized I could wrap egypt with a bit of shell code to produce the graph(s) I want.<br />
<br />
egypt processes <a href="http://en.wikipedia.org/wiki/Register-transfer_level">RTL</a> dumps produced by gcc. It outputs a call graph for the RTL dump files passed in. The first thing to do then is to compile the project to visualize using gcc with the <span style="font-family: "Courier New",Courier,monospace;">-fdump-rtl-expand</span> flag. This produces the *.expand files required by egypt. My first attempt was using gcc 4.4.7, which dumps all of the .expand files in the root directory of the build. For projects with multiple source files having the same name, the .expand files overwrite each other. I switched to gcc 4.7.1 because it dumps the .expand files in the same directory as the .o files are generated. Then, I revisited some <a href="http://gedare-csphd.blogspot.com/2010/03/versioning-my-work.html">old tricks</a> to gather the .expand files into a separate directory for analysis while keeping the project's directory structure.<br />
<br />
Now, if I just wanted the callgraph of the Callees, I could easily grep for the .expand files containing functions that start with Callee and pass them to egypt. However, to get the subgraph of caller->Callee is trickier. What I did was to use egypt on each of the .expand files individually and filter the output for edges to a Callee. This gives exactly the set of nodes and edges I need. Then I just need to wrap the output similarly to how egypt does to produce a graph file for GraphViz. The resulting script looks something like,<br />
<blockquote class="tr_bq">
<span style="font-family: "Courier New", Courier, monospace;">#!/bin/bash<br />echo "digraph callgraph {"<br />files=`find . -name "*.expand"`<br />for f in $files<br />do<br /> egypt --include-external $f | grep Callee_ \<br /> | grep -v Callee_.*-\> | grep -v Callee_.*\"\;<br />done<br />echo "}"</span></blockquote>
<span style="font-family: inherit;">The --include-external is necessary to force egypt to produce caller nodes for which it does not find a definition. The second line of greps are to exclude any calls originating from Callee, and to discard any uncalled Callee. Redirect the output of the script to a file, say callgraph.dot, and then it can be processed with one of the layout engines in the dot tools, like</span><span style="font-family: "Courier New",Courier,monospace;"><br />$> dot -Teps -o callgraph-neato.eps callgraph.dot</span><br />
<br />
As an example, I processed the RTEMS <a href="http://gedare-csphd.blogspot.com/2010/11/rtems-modular-task-scheduler.html">Supercore Scheduler</a> package. For this package, the Callee is _Scheduler. I processed the output with the circo drawing filter.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjrQwIcyg8M5OcWj5NT2jJth9eOtWZrizH0IFb9eZHYOXXuZTNgsNXirNtzSS5hFGb6otw6OIi3CuHfE6BsJ0fftWgDNk9vTN9sfqsWONiCtgGctUBzsna-lxX3dt5JTmro_7ABV4kIophl/s1600/callgraph-circo.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjrQwIcyg8M5OcWj5NT2jJth9eOtWZrizH0IFb9eZHYOXXuZTNgsNXirNtzSS5hFGb6otw6OIi3CuHfE6BsJ0fftWgDNk9vTN9sfqsWONiCtgGctUBzsna-lxX3dt5JTmro_7ABV4kIophl/s1600/callgraph-circo.png" height="221" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Supercore Scheduler Callers, with Scheduling Functions filled in Grey</td></tr>
</tbody></table>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
Some further improvements could be made. It might also be interesting to visualize the paths (open walks) that end at the Callees. Also, the egypt tool works only on the static call graph, so indirect function calls e.g. through function pointers are not captured. Making use of dynamic profiling tools that generate a call graph, such as gprof or callgrind, could improve the accuracy of the visualization. <br />
<br />Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-38588771403615985302013-05-07T16:55:00.000-04:002013-05-08T14:41:45.709-04:00Software Licenses with RTEMS<br />
The <a href="http://www.rtems.org/license/LICENSE">RTEMS license</a> is a modified version of the GPL version 2 that includes an exception to permit including headers and linking against RTEMS object files statically. Normally, the GPL can only be <a href="http://en.wikipedia.org/wiki/Static_library">linked statically</a> with other GPL code, or rather, linking statically with GPL code would cause your code to become GPL code. The <a href="http://www.gnu.org/licenses/lgpl.html">LGPL</a> is not a suitable alternative, because it either requires use of a shared library that can be re-linked, or release of the linked (application) code. And newer versions (GPL version 3) are completely unsuitable for embedded systems due to the relinking restriction which is technically challenging.<br />
<br />
A problem for RTEMS is there are no copyleft licenses that are compatible with the RTEMS license. Thus, RTEMS Project has to reject any code that uses the GPL or LGPL, even though RTEMS seems to use the GPL itself---this is because of the exception for static linking, and also because an upstream GPL version 2 project could at any time switch to GPL version 3 and become totally unusable. In practice, RTEMS can only accept original code contributed under the RTEMS License and code that has a <a href="http://en.wikipedia.org/wiki/Permissive_license">permissive license</a>.<br />
<br />
I could not find any license that provides the copyleft protection of a software project while still allowing static linking of proprietary software. Maybe there is some subtle legal or technical issue that I do not understand, but it seems like such a license ought to exist somewhere that protects the free software while permitting applications to use it; a sort-of "Embedded GPL".<br />
<br />
Some things that RTEMS could do better include:<br />
<ul>
<li>Collect all of the copyright and license disclaimers for users</li>
<li>Collect all of the advertising restrictions, or move those encumbered files to a secondary repository</li>
<li>Switch from the GPL + linking exception, but to what I do not know</li>
</ul>
<i>Update 5/8/13: Identified that RTEMS uses version 2 of the GPL, and give some background on why RTEMS has not and will never switch to version 3.</i><br />
<br />Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-54939356874006972442013-04-19T15:30:00.000-04:002013-04-19T15:32:19.921-04:00Generating interrupts with a gem5 deviceToday I extended my work of <a href="http://gedare-csphd.blogspot.com/2013/02/adding-simple-io-device-to-gem5.html">adding a device to gem5</a> by causing the device to generate an interrupt. Interrupts seem to be architecture-specific in gem5, so I needed to include some X86-specific functionality. I copied the approach taken in gem5 for the x86 keyboard interrupts, but with IRQ 3 (because it was available) for my device.<br />
<br />
The following files should help recreate this effort:<br />
<ul>
<li><a href="https://docs.google.com/file/d/0BwYqlNFWv9seWlZVdVBycmhnbjQ/edit?usp=sharing">device.diff</a> - apply to gem5 to create simple device.</li>
<li><a href="https://docs.google.com/file/d/0BwYqlNFWv9sebWVzaXk5Y2lCMjQ/edit?usp=sharing">interrupt.diff</a> - apply to gem5 with device.diff to add interrupt.</li>
<li><a href="https://docs.google.com/file/d/0BwYqlNFWv9seTWtjcVZRX0s1Yk0/edit?usp=sharing">mydev.c</a> - device driver Linux kernel module.</li>
</ul>
<br />Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com1tag:blogger.com,1999:blog-4768404585297749711.post-73466630498465606352013-02-28T15:53:00.000-05:002013-04-19T15:32:19.923-04:00Adding a simple io device to gem5Last time, I <a href="http://gedare-csphd.blogspot.com/2013/02/add-pseudo-instruction-to-gem5.html">added custom pseudo-instructions</a> in gem5. Today, I add a device in gem5 and then use the device from within a simulated (linux-x86_64) system.<br />
<br />
Adding a device to gem5 is lightly documented in the <a href="http://www.m5sim.org/Tutorials#ASPLOS-13">ASPLOS tutorial</a> and <a href="http://www.m5sim.org/Devices">gem5 wiki</a>. I would suggest starting with the tutorial, and read about the <a href="http://www.m5sim.org/Memory_System">memory system</a> as well.<br />
<br />
Devices are located in gem5/src/dev/ subtree, with architecture-specific files located in subdirectories. The IsaFake device, which I found before the ASPLOS tutorial, was useful for starting. To create a simple device, I copied isa_fake.[cc|hh] to mydev.[cc|hh], and copied BadDevice.py to MyDevice.py. Then I copied the parameters for IsaFake from Device.py into the parameters of MyDevice.py, and added mydev.cc and MyDevice.py to the SConscript. After renaming (search-replace IsaFake/BadDevice with MyDevice, isa_fake with mydev, etc), I needed to add the device to the system. I'm working with x86, so I attached it in the x86/Pc.py file, with:<br />
<br />
from MyDevice import MyDevice<br />
...<br />
my_device = MyDevice(pio_addr=x86IOAddress(0xe000), pio_size=8)<br />
...<br />
self.fake_floppy.pio = bus.master<br />
self.my_device.pio = bus.master<br />
self.pciconfig.pio = bus.default<br />
...<br />
<br />
After compiling and running gem5 the device is listed in the m5out/config.ini file.<br />
<br />
Accessing the device requires a device driver. To learn about writing drivers, read a <a href="http://lwn.net/Kernel/LDD3/">good</a> <a href="http://www.makelinux.net/ldd3/">book</a>. For this driver, a simple kernel module will do.<br />
<pre>#include <linux kernel.h>
#include <linux module.h>
#include <linux errno.h>
#include <linux ioport.h>
#include <asm io.h>
#define BASE 0xe000
#define SIZE 0x08
int init_module(void)
{
int t1;
if ( ! request_region(BASE, SIZE, "mydev") ) {
printk( KERN_INFO "unable to get io port at 0x%8X\n", BASE );
return -ENODEV;
}
/* a little test */
t1 = inl(BASE);
printk( KERN_INFO "read %d\n", t1 );
outl(0, BASE);
t1 = inl(BASE);
printk( KERN_INFO "read %d\n", t1 );
return 0;
}
void cleanup_module(void)
{
release_region(BASE, SIZE);
}</pre>
<br />
Compile the module against the Linux kernel, boot gem5, get the module into the simulated system (e.g. with m5 readfile), and insert the module. With the default parameters from the IsaFake device, the write is ignored and the device returns -1 whenever it is read.<br />
<br />
I did not get I/O memory working, but for now I/O ports are fine for me.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com16tag:blogger.com,1999:blog-4768404585297749711.post-84277743584145771222013-02-12T14:48:00.001-05:002021-10-06T11:08:57.857-04:00Add a pseudo instruction to gem5<div style="font-family: inherit;">
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.</div>
<div style="font-family: inherit;">
<br /></div>
<div style="font-family: inherit;">
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.</div>
<div style="font-family: inherit;">
<br /></div>
<span style="font-family: inherit;">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.</span><br />
<h3 style="font-family: inherit;">
<span id="internal-source-marker_0.281956285258092" style="background-color: transparent; color: black; font-size: 19px; font-style: normal; font-variant: normal; text-decoration: none; vertical-align: baseline;">Adding a new pseudo instruction (for X86)</span></h3>
<div style="font-family: inherit;">
<span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">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.</span></span></div>
<div style="font-family: inherit;">
<span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></span></div>
<ul id="internal-source-marker_0.281956285258092" style="font-family: inherit; margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Overwrite
a reserved opcode in src/arch/x86/isa/decoder/two_byte_opcodes.isa near
the other pseudo instructions (look for m5panic). </span></span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Add the instruction’s functional simulation implementation in src/sim/pseudo_inst.cc</span></span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Add the function prototype in src/sim/pseudo_inst.hh. </span><span id="internal-source-marker_0.281956285258092" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The
function prototype will define the available registers for
parameters and return values based on the compiler’s calling conventions for
the architecture.</span></span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Create
an m5op for easily emitting the instruction in compiled code.</span></span></li>
<ul>
<li dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Add
function number in util/m5/m5ops.h</span></span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Add function prototype in
util/m5/m5op.h</span></span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Instantiate a TWO_BYTE_OP in m5op_x86.S</span></span></li>
</ul>
</ul>
<div style="font-family: inherit;">
<span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">I have <a href="https://drive.google.com/file/d/0BwYqlNFWv9seWFAwaGtETHBBM0U/view?usp=sharing&resourcekey=0-kLYAYnf5pevbWFgGQTAOig">written a simple example that implements addition</a> as a pseudo instruction. The patch may bit-rot, but the idea should be easy enough to follow.</span></span></div>
<div style="font-family: inherit;">
<br /></div>
<div style="font-family: inherit;">
<span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">To use the new pseudo instruction call the</span> function declared in </span><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">
util/m5/m5op.h. Then (cross-)compile your source code with the m5 utilities like:</span></span></div>
<span id="internal-source-marker_0.281956285258092" style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> <span style="font-family: "Courier New",Courier,monospace;">gcc -o foo foo.c -I ${GEM5}/util/m5 ${GEM5}/util/m5/m5op_x86.S</span></span><br />
<span id="internal-source-marker_0.281956285258092" style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><br /></span>
<span style="font-size: small;"><span style="background-color: transparent; color: black; font-family: Arial; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span></span><br />
<div style="font-family: inherit;">
<span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">To get your code into the simulation, you can</span></span></div>
<ul>
<li dir="ltr" style="background-color: transparent; color: black; font-family: inherit; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"><span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">add the binary to the disk image</span> </span></li>
<ul style="font-family: "Courier New",Courier,monospace;">
<li dir="ltr" style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;">sudo mount -o loop,offset=32256 /dist/m5/system/disks/linux-x86.img /mnt/tmp</li>
<li dir="ltr" style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;">cp foo /mnt/tmp/bin</li>
</ul>
<li dir="ltr" style="background-color: transparent; color: black; font-family: inherit; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="font-size: small;"> or read it directly into the simulation<span style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> </span></span></li>
<ul style="font-family: "Courier New",Courier,monospace;">
<li dir="ltr" style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">build/X86/gem5.debug configs/example/fs.py -r 1 --script=foo</span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">m5term localhost 3456</span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">m5 readfile > foo</span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">chmod +x foo</span></li>
<li dir="ltr" style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; list-style-type: disc; text-decoration: none; vertical-align: baseline;"><span style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">./foo</span></li>
</ul>
</ul>
<div style="font-family: inherit;">
<span style="background-color: transparent; color: black; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><span style="font-family: inherit; font-size: small;">Adding to the disk image requires restarting the simulation, whereas if you have a checkpoint loaded you can read the file in directly using</span> <span style="font-family: "Courier New",Courier,monospace;">m5 readfile</span>.</span></div>
<h3>
<span style="background-color: transparent; color: black; font-family: inherit; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span>Executing the pseudo instruction on real hardware</h3>
<div style="font-family: inherit;">
<span style="font-size: small;"><span id="internal-source-marker_0.281956285258092" style="background-color: transparent; color: black; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">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.</span> I have written a simple example that shows <a href="https://docs.google.com/file/d/0BwYqlNFWv9seR2d3amZwSDIwUE0/edit?usp=sharing">how to handle the illegal instruction signal</a> that gets caused when the pseudo instruction is executed. This sample example will execute in both GEM5 and natively (on a 64-bit X86).</span></div>
<br />
I guess that covers it for now. Happy hacking!<br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><br />Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com19tag:blogger.com,1999:blog-4768404585297749711.post-90630256220611756312013-02-11T15:09:00.001-05:002013-04-19T15:32:19.928-04:00RTEMS on gem5 SPARCI previously wrote about booting<a href="http://gedare-csphd.blogspot.com/2010/05/week-in-m5.html"> RTEMS on M5</a> (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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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 <a href="http://tyom.blogspot.com/">Qemu Sparc64</a>.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-12251779531644221762013-02-07T11:35:00.000-05:002013-02-07T11:35:17.634-05:00screenI finally learned how to use <span style="font-family: "Courier New",Courier,monospace;">screen</span>, a terminal windowing program that can detach so its windows run as a background task. When you detach, <span style="font-family: "Courier New",Courier,monospace;">screen</span> returns you to your shell<span style="font-family: "Courier New",Courier,monospace;"></span>. Detaching allows me to start work on a server from my lab workstation in a <span style="font-family: "Courier New",Courier,monospace;">screen</span> session, detach <span style="font-family: "Courier New",Courier,monospace;">screen</span>, logout and turn off my workstation, go home, and resume the same <span style="font-family: "Courier New",Courier,monospace;">screen</span> session from home.<br />
<br />
Start <span style="font-family: "Courier New",Courier,monospace;">screen</span> with<br />
<div style="font-family: "Courier New",Courier,monospace;">
$> screen</div>
Once inside <span style="font-family: "Courier New",Courier,monospace;">screen<span style="font-family: inherit;">,</span></span> the windows act mostly like a terminal, but now you can issue commands to <span style="font-family: "Courier New",Courier,monospace;">screen</span> using Ctrl-a and a command key. The useful keys that I have been using are:<br />
<ul>
<li>Create a window (Ctrl-a c)</li>
<li>Next (Ctrl-a n) or Previous (Ctrl-a p) window.</li>
<li>Detach (Ctrl-a d)</li>
</ul>
To start <span style="font-family: "Courier New",Courier,monospace;">screen</span> with a previously detached session, first find the session with: <br />
<div style="font-family: "Courier New",Courier,monospace;">
$> screen -ls </div>
<div style="font-family: "Courier New",Courier,monospace;">
There are screens on:<br /> 11999.pts-0.localhost (Attached)<br /> 17129.pts-3.localhost (Detached)<br />$> screen -r 17129.pts-3.localhost</div>
The -r flag resumes the detached screen session.<br />
<br />
Detaching is useful especially for long-running programs or for conserving the state of many terminal windows.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-61471071298945454302013-01-24T12:53:00.002-05:002013-01-24T12:54:32.507-05:00Profiling C++ applications: class compositionIn the latter half of last year, my research went down an <a href="http://en.wikipedia.org/wiki/Object-oriented_programming">OOP</a> path especially in the direction of C++; both the <a href="http://gedare-csphd.blogspot.com/2011/07/principles-principals-and-protection.html">hardware containers</a> project and <a href="http://home.gwu.edu/%7Egedare/publications.html">my thesis</a> 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.<br />
<br />
I found 21 free and commercial (oxymoron?) open-source C++ programs for this investigation: <a href="http://www.dis.uniroma1.it/challenge9/download.shtml">dimacs-sq</a>, Dijkstra's algorithm; <a href="http://research.cs.wisc.edu/gems/">Opal</a> and <a href="http://www.m5sim.org/Main_Page">GEM5</a>, processor simulators; <a href="http://geant4.cern.ch/">Geant4</a>, physics particle simulator; <a href="http://www.flightgear.org/">FlightGear</a>, flight simulator; <a href="http://www.wesnoth.org/">Wesnoth</a>, video game; <a href="http://opencv.willowgarage.com/wiki/">OpenCV</a>, computer vision library; <a href="http://www.boost.org/">Boost</a>, library for C++; <a href="http://www.mysql.com/">MySQL</a>, database server; <a href="http://www.libreoffice.org/">LibreOffice</a>, office productivity suite; <a href="http://www.stack.nl/%7Edimitri/doxygen/">Doxygen</a>, documentation generation; <a href="https://www.haiku-os.org/">Haiku</a>, OS based on BeOS; <a href="http://www.reactos.org/en/index.html">ReactOS</a>, OS based on Windows NT; <a href="http://www.chromium.org/">Chromium</a>, web browser; povray, soplex, dealII, namd, xalancbmk, astar, and omnetpp, C++ benchmarks from SPEC CPU 2006.<br />
<br />
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!<br />
<br />
I used two tools to analyze the 21 programs: <a href="http://www.scitools.com/">Understand by SciTools</a>, and <a href="http://cccc.sourceforge.net/">CCCC</a>. 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.<br />
<br />
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.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8AzocoR8uVruXd4qEnXgtjtiJJ-9U2jCXfmC16zob6ctqE6t04S__ofJ9dFrYfuS81RFIXrIYB7iLH09ELrzI3a-jAaGwss-y0Fa8zlzN5tuPJrph-MKPm4FA3v7RmjmVLVPxYMEVk6rP/s1600/max_avg_cc.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8AzocoR8uVruXd4qEnXgtjtiJJ-9U2jCXfmC16zob6ctqE6t04S__ofJ9dFrYfuS81RFIXrIYB7iLH09ELrzI3a-jAaGwss-y0Fa8zlzN5tuPJrph-MKPm4FA3v7RmjmVLVPxYMEVk6rP/s400/max_avg_cc.jpg" height="222" width="400" /></a></div>
<br />
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.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjt5rnVizdPm8axFMnkQRlHS4CV0iXEEAf06r354XIj1gQBWGY4KJXgX2lwsQDOBFkbaUTPrtJ-S3JQJsnrtANNV6tyxjEXXcWEjyKdNkUo_1YJbxql6asywmRIBCd9EMS6io5wG_QOEM2j/s1600/maxdit.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjt5rnVizdPm8axFMnkQRlHS4CV0iXEEAf06r354XIj1gQBWGY4KJXgX2lwsQDOBFkbaUTPrtJ-S3JQJsnrtANNV6tyxjEXXcWEjyKdNkUo_1YJbxql6asywmRIBCd9EMS6io5wG_QOEM2j/s400/maxdit.jpg" height="222" width="400" /></a></div>
<br />
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.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-65269531427166061472013-01-22T17:31:00.000-05:002013-01-22T17:32:05.699-05:00My new jobAs of last week I have started my new full-time job as a Postdoctoral Research Scientist at GWU. I'm working with my thesis co-adviser, and my job is an expanded version of what I was doing before graduating. In addition to continuing my research, I will also be overseeing/assisting the research of some graduate students and writing grant proposals.<br />
<br />
The appointment is for the next 18 months or so, and I'm excited about carrying forward the momentum I have in my research.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-7619078484660581862013-01-22T14:45:00.001-05:002013-01-22T17:31:49.968-05:00Looking back to 2012, forward to 2013Of the many post ideas back-logged in my head, I wanted to recap the past year and perhaps look forward to the new year before making it out of January. For me, 2012 was a busy year in which I<br />
<ul>
<li>Became a dad.<br />
</li>
<li>Defended my Ph.D. dissertation.</li>
<li>Dropped 20 pounds to 18% body fat, BMI 23.</li>
<li>Bicycled 2300 miles, ran another 160 or so.</li>
<li>Published 2 papers and a book chapter.</li>
<li>Continued RTEMS involvement as an admin and mentor for GSOC and GCI.</li>
<li>Went on a Caribbean cruise.</li>
<li>Bought my first car, a minivan.</li>
<li>Repaired/Improved my house: foundation crack sealed, water line repaired, water line replaced, water heater replaced, roof repairs, HVAC heat pump and blower replaced, ventilation ducts cleaned, and kitchen cabinets refaced.</li>
</ul>
For 2013 some of my goals, resolutions, and expectations are to<br />
<ul>
<li>Turn 30. Done!</li>
<li>Get a job. Done, more on that soon.</li>
<li>Publish more.</li>
<li>Get more research funding.</li>
<li>Read more.</li>
<li>Learn a new (non-programming) language, probably ASL or suomi.</li>
<li>Continue RTEMS involvement.</li>
<li>Resume regular exercise. I cut way back after my daughter was born.</li>
<li>Finish a century ride, solo or supported. Current best: 88 miles.</li>
<li>Finish a half-marathon, solo or organized. Current best: 8 miles.</li>
<li>Take up swimming.</li>
<li>Go on a family vacation. </li>
<li>Build a "front porch."</li>
<li>Construct a new cat tower.</li>
<li>Get rid of stuff.</li>
<li>Be a better person. </li>
</ul>
Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-87196458629714981492012-11-20T15:52:00.000-05:002012-11-20T15:52:08.477-05:00Hood me!I successfully defended my dissertation thesis yesterday, thus overcoming the final hurdle to the Ph.D. other than some paperwork and formatting/publishing the thesis itself. The title of my thesis is "Operating System Support for Shared Hardware Data Structures" and it spans a range of computer science topics from low-level computer hardware—not quite circuits, but close—up to application software and everything in between. I'm pleased with both the scope of the work, the technical contributions, and the outlook for carrying this work forward. I chose to find and pursue a topic that interested me, and my advisors (and wife!) were flexible enough to permit me to do so. It feels great to take the seed of an idea through germination and see it begin to grow.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com3tag:blogger.com,1999:blog-4768404585297749711.post-44617241950047660652012-10-16T11:07:00.001-04:002012-10-16T12:06:04.446-04:00Critical Bugs and Quality AssuranceSebastian Huber recently posted a nasty RTEMS bug and fix. While simple, the bug manifested in their application as an increase in one task's latency from 20us to 170us! The cause of the problem was that RTEMS has two kinds of critical sections—dispatch and interrupt—and new SMP-aware code added a dispatch critical section to the thread dispatch code. The problem happens with overlapping a traditional interrupt disable critical section. The SMP dispatch code looks like:<br />
<blockquote class="tr_bq">
void _Thread_Dispatch(void) {<br />
Thread_Disable_dispatch();<br />
SMP_Dispatch_other cores();<br />
Interrupt_Disable();<br />
...<br />
... do things, including context switch if needed<br />
...<br />
Interrupt_Enable();<br />
// problem here!<br />
Thread_Unnest_dispatch(); // enable<br />
...<br />
}</blockquote>
The problem is that an interrupt can occur between Interrupt_Enable and Thread_Unnest_dispatch. Suppose a low-priority task (L) is executing _Thread_Dispatch, and the interrupt enables a high-priority task (H), but<br />
H will not be dispatched because dispatching is disabled. Instead L enables dispatching and resumes executing, which is a priority inversion!<br />
<br />
The fix reverts the changes made for SMP. For the SMP code, the priority inversion still exists and is unresolved. (RTEMS currently does not make real-time guarantees for the SMP support, so no one cares yet.)<br />
<br />
In the broader picture, the bug seems like it should be easy to detect. The issue with free open-source software (FOSS) is that quality assurance (QA) is almost non-existent: the <a href="http://en.wikipedia.org/wiki/Linus%27_Law">"many eyeballs" </a>philosophy argues against QA. But what else can FOSS do? No one is going to pay for extensive testing, and if they do they have no incentive to share.<br />
<br />
FOSS communities (and corporate developers) need better tools for software QA. This summer RTEMS had a GSOC student who was looking at testing. Testing is probably the first tool in the QA toolbox, and the only one most developers have a clue about; how about static analysis, path coverage, standards conformance, or certification? Some <a href="http://blog.regehr.org/archives/713">interesting</a> <a href="http://www.cs.cornell.edu/talc/papers/mtal-abstract.html">work</a> <a href="http://web.mit.edu/embeddedsystems/Research.html">modeling</a>, <a href="http://www.cl.cam.ac.uk/%7Eacjf3/arm/">proving</a>, and <a href="http://compcert.inria.fr/">certifying</a> <a href="http://www.ertos.nicta.com.au/research/l4.verified/">systems</a> is out there: Where is the undergraduate textbook and course on QA?Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-17069094276290809002012-10-13T14:37:00.001-04:002012-10-16T12:06:32.571-04:00Web site update<div>
Last night I decided to provide an <a href="http://home.gwu.edu/%7Egedare/vita-gedare.html">html</a> version of my CV, and then I remodeled my <a href="http://home.gwu.edu/%7Egedare">website</a>. 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.</div>
Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-61356431058244306182012-10-12T11:55:00.002-04:002012-10-16T12:07:07.613-04:00Version control for text/LaTeX?I often use version control (VC) for text documents—especially LaTeX. Modern VC software is good for code, and even text when working alone, but collaboratively editing text with VC is a nightmare. The biggest challenge for text VC seems to be structure/formatting.
Code is well-structured within and between lines: text less so.
Words/sentences can be re-arranged within
sentences/paragraphs, and lines are meaningless. With VC, line wrapping
propagates small changes and frustrates reviewing and merging.<br />
<br />
Word processors track revisions, but such tools are restrictive and won't work for markup languages. Cloud tools for collaboration such as Docs exist, including <a href="http://en.wikibooks.org/wiki/LaTeX/Collaborative_Writing_of_LaTeX_Documents">some for LaTeX</a>, but requiring connectivity while editing is a non-starter for me. I would even be happy with a custom LaTeX solution; the features I desire for text VC are similar to those for code:<br />
<ul>
<li>Non-proprietary, application-agnostic, platform-independent <a href="http://en.wikipedia.org/wiki/Free_and_open-source_software">FOSS</a> </li>
<li>Revision history: see what has changed.</li>
<li>Revert: undo changes back to forever.</li>
<li>Lock-free: work in parallel, which requires...</li>
<li>Pain-free merge: help resolve conflicting commits.</li>
<li>Distributed and offline editing: no active (server) connections</li>
<li>External contributions: integrate changes made outside of VC </li>
</ul>
Most VC tracks changes either with changesets or snapshots. Changesets
seem worthless because of the structural problems of text. Snapshots seem viable, but I haven't seen turn-key solutions for plain text or LaTeX, and handling external contributions seems especially troublesome.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com4tag:blogger.com,1999:blog-4768404585297749711.post-4044301670831108712012-10-11T17:51:00.002-04:002012-10-11T17:52:06.910-04:00GSOC2012: MMU project and musingsI finally made a pass at merging my student's <a href="https://github.com/heshamelmatary/rtems/branches/project_snapshot">final code</a> for his GSOC2012 project. The project was the culmination of <a href="http://code.google.com/p/rtems-mmu-support/">multiple</a> <a href="http://code.google.com/p/gsoc2011-rtems-mmu-support-project/">summer</a> <a href="http://www.google-melange.com/gsoc/project/google/gsoc2012/hesham/25001">projects</a> and <a href="http://gedare-csphd.blogspot.com/2011/12/rtems-memory-protection-api.html">some</a> <a href="http://gedare-csphd.blogspot.com/2011/12/rtems-memory-protection-middle-layer.html">work</a> I did. I'm excited to try improving it to add sparc64 support and use it in my research.<br />
<br />
While revising the student's submission for reviewing and merging, I thought of a few ways to improve future new developer participation:<br />
<ul>
<li>Better github integration. Staying up-to-date with rtems.git, tracking student progress, and getting code review from more developers would be helpful for quicker turnaround on submissions.</li>
<li>Style: documentation and code conventions. Clear, consistent guidelines and examples of proper/improper coding style would make reviewing and merging a lot easier.</li>
<li>Improved Git Workflow. Teaching students how to make useful branches and commits ahead of time would ease code merging, testing, and revising.</li>
<li>More submissions. We need to get code reviewed if not merged in smaller increments; this need is well-known and repeated. </li>
</ul>
These improvements could be addressed in part when students/developers are new to the scene. For example, instead of just making students prove they can build RTEMS and patch hello world, we could require them to document and fix the style of sample code using a branch, and submit a pull request for RTEMS github that contains their proof as separate commits on the same branch.<br />
<br />
For getting students to submit and be reviewed more often will take more work on behalf of mentors, developers, and students. Something that may help would be requiring code review as part of the weekly status meetings we instituted this GSOC. Perhaps each student's weekly commits can be reviewed by their mentors as part of tracking progress and status.<br />
<br />
Institutional support from RTEMS mentors and developers would help. For example, github integration requires developers and mentors to use github. Style consistency requires a style guide that we accordingly maintain and abide by. Teaching good workflow, and fixing the bad, takes effort: mentors need to (know how to) identify and correct a student who struggles. Increased submission frequency requires urging and commitment from mentors to review code. These improvements take effort, but I think they could substantially improve the participation, progress, and production of students.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-31984469297899498232012-10-05T16:32:00.002-04:002012-10-11T17:59:09.832-04:00My fall hiatus<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDI1YAp5AmlupkuTaJz_7KUDawDdV2C2IXn6nvIksTBC_CTA91RIjdjL7nvAeFjAWZOaphRn_SiP0RvrQeK3Xvf4L6qpdF4V8W4PZl2PyUse5mTPLhlUhWNT6NvWJXWPEIyu1XSGqPSfvg/s1600/380997_10100184478280854_1952833534_n.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="118" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDI1YAp5AmlupkuTaJz_7KUDawDdV2C2IXn6nvIksTBC_CTA91RIjdjL7nvAeFjAWZOaphRn_SiP0RvrQeK3Xvf4L6qpdF4V8W4PZl2PyUse5mTPLhlUhWNT6NvWJXWPEIyu1XSGqPSfvg/s200/380997_10100184478280854_1952833534_n.jpg" width="200" /></a></div>
I've been busy lately, between child-rearing and working on a grant proposal, and I haven't had the time and energy for much else. I'll be writing my thesis soon, too, but that might encourage me to write more here. Meanwhile, check out some <a href="http://lookingforprogrammers.blogspot.com/">fake ads for programming jobs</a>.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-23532519659535780732012-08-07T13:42:00.001-04:002012-08-07T13:42:44.701-04:00Making and freezing food in bulkMy mom and one of my brothers visited my wife and me this past weekend in order to deliver the cradle—we're expecting a baby girl at the end of this month—made by my father-in-law. We decided to take advantage of this visit to prepare some frozen food to ease transitioning into parenthood. For about a day-and-a-half we cooked and froze one or more of the following meals to produce about 20 frozen ready-to-reheat meals:<br />
<ul>
<li>Jambalaya</li>
<li>Mock Lasagna: layered cooked spaghetti with sauce and cream cheese</li>
<li>Penne with sausage and vegetables in spaghetti sauce</li>
<li>Chicken Cacciatore</li>
<li>Chicken Tetrazzini</li>
<li>Tuna Casserole</li>
<li>Chili</li>
<li>Chicken Curry with chickpeas, spinach, and rice </li>
<li>Rice, chicken and vegetables covered by cream of mushroom soup</li>
<li>Enchiladas</li>
<li>Meatloaf (uncooked)</li>
<li>Meatballs (uncooked)</li>
</ul>
We started by prepping almost everything: chopping vegetables; thawing, cutting, and seasoning proteins; buying and organizing canned goods; cooking rice and pasta. Prep work transferred most of the contents of my freezer to my refrigerator, which was full and working hard to keep food cool.<br />
<br />
The general procedure we followed was to prepare two dishes at a time, and we tried to make double batches when possible. We would cook the meat for each dish, let the meat cool a little, line a freezer-safe container with plastic wrap, apply non-stick spray to the wrap, build the dish in the container, cover with plastic wrap, and stick in the freezer.<br />
<br />
After a dish had thoroughly frozen (a day) we removed the dish from its container and wrapped it in aluminum foil outside the plastic wrap, and then wrote the name of the dish and the name of the container we froze it in. When we reheat/cook the dish we know what container to use for best-fit.<br />
<br />
All-in-all the batch cooking was a success, and I expect the pre-made dishes will be appreciated by future me.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-35311237509579843772012-05-25T15:07:00.000-04:002012-05-25T15:07:18.015-04:00Red-Black Trees Redux: Left-Right SymmetryI previously <a href="http://gedare-csphd.blogspot.com/2011/08/red-black-trees-bottom-up-or-top-down.html">compared top-down versus bottom-up red-black trees</a> and concluded that bottom-up is faster and therefore preferred.<br />
<br />
Recently I was working with binary search trees (BSTs) and happened to observe anomalous performance between two implementations of a BST (<a href="http://en.wikipedia.org/wiki/Splay_tree">splay tree</a>). One implementation was taking much longer than the other. After some investigation I attributed the variance to two factors: <a href="http://en.wikipedia.org/wiki/Function_object">comparison functors</a> and use of <a href="http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_bst1.aspx">left-right</a> BST <a href="http://www.stanford.edu/%7Eblp/avl/libavl.html/BST-Node-Structure.html">symmetry</a>. Cursory examination indicated that using a functor instead of direct comparison of keys was increasing execution time around 10-20% for a particular workload. Left-right symmetry was causing about 30-40% increases in execution time!<br />
<br />
Comparison functors are important because an implementation of a BST cannot know ahead of time how to compare generic nodes, and—for languages that lack decent <a href="http://en.wikipedia.org/wiki/Generic_programming">templates</a> such as C—a functor is a fact of life. But left-right symmetry is a choice. Some <a href="http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx">arguments</a> for left-right symmetry are that it reduces the source lines of code (SLOC) and increases correctness. I think the performance problems of using left-right symmetry comes from indexing in an array on top of a pointer dereference, and doing so multiple times. By separating the left and right cases explicitly the programmer specifies the pointer precisely.<br />
<br />
Execution time increases for code that exploits left-right symmetry at least for splay trees. How much does the use of left-right symmetry affect red-black tree performance?<br />
<br />
Using a search benchmark that I coded from a <a href="http://onlinelibrary.wiley.com/doi/10.1002/spe.4380230403/abstract">published description</a>, I evaluated two versions of red-black trees: one that uses left-right symmetry to compress code paths and one that explicitly represents the two sides. (The left-right symmetrical code is the version currently in use in RTEMS.) The benchmark inserts search keys generated randomly until the tree reaches a specific size, and then issues a mix of update and search operations in sets of 100. For this work I used sizes between 16 and 4096 in powers of 2, and about 1000 update/search operations, with the mix varying between pure search and pure updates. Otherwise the benchmark is as described in the paper linked above.<br />
<br />
The following charts show representative results from running these benchmarks in <a href="http://research.cs.wisc.edu/gems/">Simics/GEMS</a>. The "rbtree" results use explicit left and right child pointers and split the cases; "rbtree sym" compresses the symmetrical cases together and uses an array of two child pointers.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0VdkkrL-gu-o4__FYOR6Pix-aY1U1mZrjFx85fpEQmCunDKyHpDb8B4xNveN0G16TdVmXMWVAMQzsN3EUGQPoTlDXjR7On2C71H9NUichXnFzrkuahy54g8oXOqnPownF7EBw7Z5qJqB5/s1600/warmup_cycles_1_line.png" style="margin-left: auto; margin-right: auto;"><img border="0" height="337" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0VdkkrL-gu-o4__FYOR6Pix-aY1U1mZrjFx85fpEQmCunDKyHpDb8B4xNveN0G16TdVmXMWVAMQzsN3EUGQPoTlDXjR7On2C71H9NUichXnFzrkuahy54g8oXOqnPownF7EBw7Z5qJqB5/s400/warmup_cycles_1_line.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Cycles to insert elements into a red-black tree until reaching the max size.</td></tr>
</tbody></table>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTKzVLFiCkmVkMJiZkhGcxqHKMZzy65I2FTwcQm8KU6CGYwBHMKDa8LUr3ypO68nyejuG0vY8u7P2o6s7akMvOxJIu71J4_Kwi5T7lubbNAWQZXh6LFsi2iLEPsb50DO-2VIiR06qdBe_d/s1600/hold_cycles_1_line.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="337" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTKzVLFiCkmVkMJiZkhGcxqHKMZzy65I2FTwcQm8KU6CGYwBHMKDa8LUr3ypO68nyejuG0vY8u7P2o6s7akMvOxJIu71J4_Kwi5T7lubbNAWQZXh6LFsi2iLEPsb50DO-2VIiR06qdBe_d/s400/hold_cycles_1_line.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Cycles when searching in a red-black tree at certain sizes. 1000 searches at each point.</td></tr>
</tbody></table>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJF5QLcEgGwJeyyzg8skCrjgUviO-94fIJK7tswMOHoiLmB0N19TtdexR4Tu1zhJm8njWqEdgr1ndazVDbzUNT-WvUrI6zpOjEzfOvxKwjhy60EWKRVzKpBS48r9ojYAKT5nOUG-EJ6wJl/s1600/hold_cycles_3_line.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="337" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJF5QLcEgGwJeyyzg8skCrjgUviO-94fIJK7tswMOHoiLmB0N19TtdexR4Tu1zhJm8njWqEdgr1ndazVDbzUNT-WvUrI6zpOjEzfOvxKwjhy60EWKRVzKpBS48r9ojYAKT5nOUG-EJ6wJl/s400/hold_cycles_3_line.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Cycles when updating and searching. 500 searches, 500 extractions, and 500 insertions at each point. Note that an extraction uses a search to find the node to remove.</td></tr>
</tbody></table>
<br />
The percent increase in execution time when using left-right symmetry of insertion is less than that of search: not good for a structure whose purpose is efficient searching!<br />
<br />
Ben Pfaff's <a href="http://adtinfo.org/index.html">libavl</a> uses left-right symmetry (and a table-based approach instead of parent-pointers), and comparing the performance of libavl using explicit cases for handling left and right might be interesting. Using his systems benchmarks to evaluate the RTEMS red-black tree implementation would be nice, although of limited value since the benchmarks target general-purpose (*nix) systems. The Linux (lib/rbtree.c) and FreeBSD (sys/sys/tree.h) kernels both have red-black tree implementations with explicit left and right pointers.<br />
<br />
I have not evaluated whether the symmetrical case reduces code size (generated machine instructions in the binary). How much is SLOC reduced, and does that translate to reduced program size? If code size goes down due to symmetry then, for an embedded system, the choice of which implementation to use becomes more complicated. But if code size is the same (or increases!) then quantitative reasoning tells us not to use left-right symmetry.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-16684674295669010992012-05-18T16:53:00.000-04:002012-05-18T16:53:03.116-04:00Bike to work dayToday was <a href="http://www.biketoworkmetrodc.org/">bike to work day</a> and I normally commute on Friday anyhow so I participated albeit without registering. There were noticeably more people out, particularly in small groups, although not many more than on a nice weekend day: fewer pedestrians though. I wore my new kit, which consists of the bib shorts and jersey of the<span style="font-size: small;"> 2008 Finnish champion (from team </span><span style="font-size: small;">Francaise Des Jeux), blue/white helmet, blue gloves, white shoes, and my blue/white bike. </span><br />
<br />
A skinny-tire caught my wheel shortly after I hooked up to the <a href="http://www.wodfriends.org/">W&OD trail</a> and we paced each other most of the way into DC. It was nice although for the first couple miles I didn't keep his wheel because he was a bit more brazen with rolling through stops. We had a pretty nice pace for the latter half of my ride. He was commuting from Ashburn, which is a sight farther than my own ride.<br />
<br />
The ride home was a little rough, but the worst of it came near the end. Shortly after I got back onto the streets from the trail I was passed by a black BMW and the passenger yelled, "Get off the road %$#hole!" I have read that this is rather common, and so is having things thrown at you or being buzzed. The latter two constitute assault with a deadly weapon (vehicle) and can be brought to court.<br />
<br />
Since I was only verbally harassed I decided to give a little back. So I chased the car down to the next stop light, pulled alongside, and yelled, "I have as much a right to the road as you!" The passenger, a young man, pretended not to hear because the window was up; the young girl driving seemed either embarrassed or amused, or maybe both. I went off to another lane to resume my ride. The same car passed me again a little later. Some people suck.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com2tag:blogger.com,1999:blog-4768404585297749711.post-69002729531167432092012-04-19T08:31:00.002-04:002012-10-16T12:08:49.743-04:00Downloading starred emails from GMail to apply git patchesNow that <a href="http://wiki.rtems.org/wiki/index.php/Main_Page">RTEMS</a> 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! <br />
<br />
So I wrote <a href="http://code.google.com/p/fetch-flagged-email/">fetch-flagged-email</a>—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.<br />
<br />
<pre>productivity++;</pre>
Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com1tag:blogger.com,1999:blog-4768404585297749711.post-32200523413458510662012-04-16T21:12:00.000-04:002012-04-16T21:12:32.642-04:00Crufty StuffJoel Sherrill posted <a href="http://rtemsramblings.blogspot.com/2010/10/running-slocount-on-rtems.html">back in 2010</a> about the lines of code in RTEMS. I was curious about something related to this so first I replicated his work using <a href="http://www.dwheeler.com/sloccount/">sloccount</a>. I think he may have neglected the inline files (because I had to add the .inl extension). I also added support for m4, .ac, and .am files. The latter two are part of the autotools build system and are filed under 'makefile'. Here are the current results on the RTEMS tree<br />
<pre>Totals grouped by language (dominant language first):
ansic: 745153 (86.51%)
asm: 38574 (4.48%)
makefile: 34934 (4.06%)
ada: 26261 (3.05%)
sh: 7086 (0.82%)
cpp: 5248 (0.61%)
m4: 2996 (0.35%)
pascal: 814 (0.09%)
perl: 279 (0.03%)
Total SLOC 861,345
</pre>Now for the interesting part: I also ran sloccount after running bootstrap, which generates a bunch of files for the build system. I modified sloccount to also count the Makefile.in files (which are generated with autotools from Makefile.am sources). Here are the results<br />
<pre>ansic: 745153 (35.73%)
sh: 638471 (30.61%)
makefile: 557257 (26.72%)
m4: 73475 (3.52%)
asm: 38574 (1.85%)
ada: 26261 (1.26%)
cpp: 5248 (0.25%)
pascal: 814 (0.04%)
perl: 279 (0.01%)
SLOC* 2,085,532
* includes generated files
</pre><br />
And do you know how many humans look at that generated code? Any idea how much of it is tested?<br />
<br />
It would be interesting to include all the other code that goes into making RTEMS work such as the compiler, RPM packing scripts, and so on. The moral of this data is that the build system is complex. Very complex.<br />
<br />
<span style="font-size: x-small;">This data was generated using David A. Wheeler's 'SLOCCount'.</span>Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0tag:blogger.com,1999:blog-4768404585297749711.post-46877864796540723202011-12-19T16:34:00.000-05:002011-12-19T16:34:29.251-05:00Using partitions as a free listYesterday I discussed my search for some help with <a href="http://gedare-csphd.blogspot.com/2011/12/rtems-free-list.html">implementing a free list in RTEMS</a>. Today I'm glad to say I was able to use partitions to achieve my objective of a growable free list—something akin to a slab allocator. A fundamental limit, the maximum number of partitions, still exists but partitions can have an arbitrary size; these limits might be circumvented safely by making each partition much larger than the previous or by combining old partitions into new ones. Further improvements can be made, but for now I'm satisfied.<br />
<br />
<span style="font-size: large;">Allocation</span><br />
Iterate over available partitions until one returns a free object. If none succeeds, create a new partition (malloc a new set of objects) and get a free object from the new partition.<br />
<br />
I have not handled what to do if partition creation fails. Performance could be improved by tracking the non-full partitions.<br />
<br />
<span style="font-size: large;">Deallocation</span><br />
Return the object to its partition. I made this easy by storing a handle to the owning partition as part of each object. Non-invasive techniques, such as tracking address ranges for each partition, could be used for a generic solution.Gedarehttp://www.blogger.com/profile/05234390964444125364noreply@blogger.com0