Multivax

TCP socket blocking behavior

2012-01-24T20:29:00.000-08:00

Here are some experiments results of blocking behavior of TCP applications. Blocking is a special state in which a process is waiting for I/O and removed from the scheduler queue. When the data is available, the process is woken up. In the case of distributed applications, the network latency is likely to cause blocking. To understand the behavior of such applications, a small experiment is made with netcat on Linux. System events are recorded with LTTng and network events are recorded with tcpdump. To simulate the network latency, the Linux traffic shaper is used. Here is the script used as the test case.

#!/bin/sh
tc qdisc add dev lo root netem delay 100ms
netcat -l localhost 8765 > /dev/null &;
echo "lttng" | netcat localhost 8765
tc qdisc del dev lo root

Here, the traffic shapping command sets the latency of packets to 100ms on the loop-back interface. The first netcat process is configured to listen on port 8765. The server exits immediately when a message is received. Next, the netcat client is spawn and a small string is transfered. The last command removes the traffic shapping configuration. The Linux kernel used is 2.6.38 on x86_64.

Tracing this script reveal three main blockings, as reported by the blocking analysis module of flightbox.

# server process
Blocking report for task /bin/netcat [7495]
Start            Duration (ms)        Syscall Wakeup
8073461215283          300,873     sys_accept SOFTIRQ

# client process
Blocking report for task /bin/netcat [7497]
Start            Duration (ms)        Syscall Wakeup
8073461820815          200,155     sys_select SOFTIRQ
8073662056512          200,135       sys_poll SOFTIRQ

The next figure shows blockings occurring in the system, including messages sent at each steps.

The server process create a new AF_INET socket, binds it and start to listen on the selected port. The accept is then performed for an incoming connection. From the trace, we observe that sys_accept blocks for about 300ms. This delay is very close to three times the network latency and is also almost equal to the process duration. Once the accept returns, the read on the socket doesn't block and the process exits.

In the case of the client, it creates the socket, then perform a sys_connect to the server. The connect returns immediately the value EINPROGRESS without blocking. The next step performed is a sys_connect, in which the client blocks for about two times the network latency. When the select returns, the actual message is sent to the server without blocking and the socket is closed. Finally, the client waits on sys_poll for about twice the network delay.

From this observation, the sys_accept performed by the server blocks until the final handshake ACK is received. Hence, unfinished handshake is completely hidden from the application and handled at the OS level. When the read is done, the data is already buffered, such that the read doesn't block in this case. In the case of the client, the connect system call returns in an optimistic fashion. The wait for the socket to be ready is differed to a select system call. This may allow many connect to be performed simultaneously. As for the poll, this may be related to the tear-down procedure of the socket, waiting for the final FIN from the server.

In the case of the traffic shaper used, the delay between consecutive packets is preserved. For example, the client sends three packets when the sys_select returns in a short burst. Hence, this experiment may not highlight all possible blockings. An alternative to traffic shaper is the iptables NFQUEUE. It allow to forward each packet in userspace for arbitrary processing. More on this in the next blog.

Tracing MPI application

2011-11-16T08:28:00.000-08:00

While preparing labs for the Parallel Systems course at Polytechnique, I had the chance to refresh my MPI knowledge. One of the activity consist to compare communication patterns in a MPI application. For this purpose, the MPI library can be linked with special library to record all communication. Jumpshot is the graphical viewer for the trace. I wanted to compared traces obtained from MPE and compare it to a kernel trace.

First, some technical details on how to instrument MPI program, because it's not so obvious after all and documentation is sparse. I tried MPICH and OpenMPI as MPI implementation. I would recommend MPICH because it seems to provides better error message, which are very valuable to understand failures. In addition, on Fedora, MPE library is built-in in the MPICH package, which is not the case for OpenMPI. On Ubuntu, MPE library must be downloaded and installed by hand [1] because there is no binary package for it. As for the autoconf for the project, I reused m4 macro cs_mpi.m4 from Code Saturne [2] with the following options to configure. By linking to llmpe, the library will ouput suitable file for Jumpshot.

CC=mpicc LDFLAGS="-L/usr/local/lib" LIBS="-llmpe -lmpe" ./configure

The experiment consists in a small MPI application that exchange grid boundaries in 1D cartesian decomposition using blocking send and receive. 4 process are launched on the same host. The first figure shows a zoomed view of execution and messages exchanged between process according to time. The second figure shows a statistic view for an interval, in which the time spent in each state is summed. In one look, one can see what is the relative taken for the communication, which is very handy to understand performance.

The same application has been traced with the LTTng kernel tracer. While the program is computing and exchanging data with neighbors, no system calls are performed to transfer the data. In fact, between process on the same hosts, MPICH uses shared memory for communication, obviously to achieve better performance. This example shows that it may not be possible to recover relationship between processes that communicates through shared memory. One thing to note is that numerous polls on file descriptors are performed, probably for synchronization. Maybe the relationship can be recovered from there.


Jumshot Timeline view (green: recv, blue: send)

Jumshot Histogram view (green: recv, blue: send)

LTTv control flow view (green: userspace)

Would it be possible to trace shared memory accesses directly? A recent kernel feature allows to trace memory map I/O (MMIOTRACE). It works by resetting the flag that indicates a page is in memory, such that a page fault is triggered each time a page is accessed. The page fault handler is instrumented to record those events. This technique may be a hint on how to recover shared memory process relationship. More on this later.

In conclusion, MPI instrumentation with MPE helps to understand runtime performance behaviour of MPI application. The same results can't be obtained with the current kernel tracing infrastructure found in LTTng.

[1] ftp://ftp.mcs.anl.gov/pub/mpi/mpe/mpe2.tar.gz
[2] http://research.edf.com/research-and-the-scientific-community/software/code-saturne/introduction-code-saturne-80058.html

Common Trace Format Bitfields

2011-07-26T08:59:00.000-07:00

The Common Trace Format (CTF) will be the default format of the next release of LTTng 2.0. This new trace format is able to write data at the bit level to optimize space usage of each field. Such sub-byte packed bits is called a bitfield.

Endianness of the bitfield follows the native endianness of the architecture where the trace is obtained. Big endian (BE) and little endian (LE) are supported. But how does the bits are written into the trace? According to the documentation in include/babeltrace/bitfield.h:

The inside of a bitfield is from high bits to low bits.

On big endian, bytes are places from most significant to less significant.
Also, consecutive bitfields are placed from higher to lower bits.

On little endian, bytes are placed from the less significant to the most
significant. Also, consecutive bitfields are placed from lower bits to higher
bits.

To make sure I understood correctly, I created an example based on the current implementation in babeltrace. The structure has three fields. Each field is followed by it's length in bits.

struct x {
    unsigned int a : 4;
    unsigned int b : 32;
    unsigned int c : 4;
}

The total size of the structure is 40 bits or 5 bytes. For the example, following values are assigned to the fields to be able to spot them easily:

x.a = 0x0000000E;
x.b = 0xA1B2C3D4;
x.c = 0x0000000F;

Then, writing those values in a byte array in big and little endian gives the results in the table below. The binary and hexadecimal reprensentation of consecutive bytes are displayed.

Big endian
0b11101010 0xEA
0b00011011 0x1B
0b00101100 0x2C
0b00111101 0x3D
0b01001111 0x4F
0b00000000 0x00
[...]

Little endian
0b01001110 0x4E
0b00111101 0x3D
0b00101100 0x2C
0b00011011 0x1B
0b11111010 0xFA
0b00000000 0x00
[...]

Big endian is simple, because the bitfield is written sequentially. The first byte 0xEA starts with the four bits if the a field, followed by the first four bits of the b field. Notice that in consequence all subsequent bytes of the b field are shifted. The last byte starts with the last four bits of the b field. The c field fills the rest of the last byte. All bytes that follow are untouched.

As to little endian, the first byte ends with the a field. Then, the b field is written, but the most significant bit is found on the second half of the last byte. Notice that tbe bytes and written backwards, also shifted by four bits. The third field c is placed in the upper half of the last byte.

Happy hacking!

Summary of Linux Symposium 2011

2011-06-16T18:39:00.001-07:00

Linux Symposium took place in Ottawa once again in 2011. I went there for a talk about recovering system metrics from kernel trace. There were interesting talks, here is a summary.

Hitoshi Mitake explained scalability issues for virtualization on multi-core architecture with real-time constraints. He mentioned that when one of the virtual CPU is interrupted, another virtual CPU may tries to enter section protected by a spin lock, which decrease performance under load. Alternative scheduling of virtual CPU is proposed to avoid such situation.

Sergey Blagodurov talked about scheduling in NUMA multicore architecture. I learned the numactl system calls that can be used at the userspace level to move process and memory between domains. He was developing scheduler algorithms to optimize performance on this architecture. Since the Linux scheduler can migrate a process, but not the related memory pages, then performance is decreased because the inter-domain communication is increased and is much slower. One of his goal was to increase memory locality for pages that were used frequently.

One talk has been given about Tilera architecture by Jon C Masters, that includes on a single chip up to 100 cores! This piece of hardware is undoubtedly very special, and I would love to get one on my desk! I wonder how does the Linux kernel can scale up to that number of cores.

Trinity, which is a system call fuzzer has been presented by Dave Jones. It's basically a tool that perform system calls with randomized arguments, but still looking at edge cases. They found and fixed around 20 weired bugs this way. Code coverage report could be useful in future.

What about redundant data on a disk? There were a talk about block device deduplication by Kuniyasu Suzaki. The principle is that two identical blocks should not be saved twice. Since it operates at the block level, mileage vary between file systems. The presenter showed principally how much space can be recovered according to block size and file system type. I'm still curious what is the performance impact and CPU overhead of performing deduplication online.

The last talk I wanted to mention is the one given by Alexandre Lissy, about verifications of the Linux kernel. Static checks like Coccinelle are available right now by running make coccicheck in your linux base source tree. While model checking on the entire kernel would be great to get more guarantees about it's well behavior, the feasibility of it with SAT model checker is another story, because of the size and complexity of the Linux source tree, which is quite an undertaking challenge. Maybe an approach like SLAM from Microsoft, that validates interface usage, could be use for Linux drivers too?

This Linux Symposium was the opportunity to meet a lot of people involved in the kernel community and share ideas. Here are few links related to the conference.

Performance analysis with kernel trace

2011-05-21T14:58:00.000-07:00

In this blog, I want to show some progress I made toward providing performance analysis tools for developpers and system administrators. The idea is to answer questions like:

What is the cause of lattency in the system?
How much resource a task require?
What is the relationship between process?
What is the critical path of a task?
Which subsystem is the bottleneck of the system?

To answer such questions, a kernel trace is an excellent source of system performance data. It has low overhead and provide precise timings information about events occuring on the system. But, get an overview of a system behavior by looking at each individual events is a challenge. We need an analysis toolbox. In the rest of this blog, Four tools are presented with which you can experiement yourself. A summary example is presented to show the integration of various analysis made with flightbox, the prototype implementation.

Resource usage recovery

The basic metric needed to perform various other analysis is resource usage. CPU usage recovery has already been presented from previous post. The same kind of analysis can be done with memory, disk and network usage.

In the case of CPU usage, kernel scheduling events indicates the process that drives the CPU. The CPU usage of a process is thus the sum of scheduled time. To display on a chart, CPU usage intervals are decomposed in fixed time range. An average usage is then easy to compute, and the precision can be increased by reducing the duration of time interval. The technique is presented on the following figure.

This technique is known as geometric integration. This computation behaves somewhat like a low-pass filter, by smoothing the raw CPU usage, making it easier to understand. The size of the resulting data is proportional to the trace duration times the desired precision times the number of process, no matter the trace size. In consequence, the CPU usage of a large trace can be summarized with a small array of doubles.

Blocking analysis

A process is blocked when a resource is not available and it can't progress. For example, we a process perform a read on a socket while the data is not yet received, the process block and the sceduler remove the waiting task from the running queue. Blocking can only occur in kernel mode. The main cause of blocking is in system calls. It can also occur during a page fault for which the page is swapped for example. The following picture shows typical example of blocking. Colors are matching legend in LTTV, green is for running in user mode, blue is for running in system call and red is for blocked on IO. Finally, orange represent the interval while the data is ready, but the process is not yet scheduled.

Some blocking are not necesserely bad. Waiting for user input or a server that waits for a request to come is not important. We are mostly interested on blocking on the critical path of an application, meaning blocking that induce processing delay from the user's point of view.

While a task is blocked, a subtask can perform some work. This subtask can also block, thus blocking among tasks is hierarchical.

Inter-process relationship

Under Linux, process can cooperate with various Inter-Process Communication mechanism, namely:

Socket
Pipe
Fifo
Mutex
Signal
Shared memory
File lock

Those mechanism make possible to share resource, send message and data between process. Sockets are well instrumented in the Linux kernel. Hence, it's possible to recover the link between process that use socket to communicate. It works at the host level, but provided traces from many hosts, it would be possible to recover links between distributed components. For example, we could recover process relationship for an httpd client, shown at the following figure.

Resource usage accounting

The idea behing resource usage accounting is to associate resource usage of a server to the client that does the request. This analysis is able to compute the cost of some request accros distributed process as if it was performed by only one thread. To perform this analysis, ressource usage, inter-process relationship and blocking analysis are required.

For example, say that an http client perform a request on a web server. The resulting web page is returned to the client. While waiting for the web page, the http client blocks. By associating the CPU usage of the httpd thread that process the request of the client while it's blocked, the resource usage is effectively accounted to the right process. This is shown by the following figure.

Example

In the following example, we will use a special RPC client and server, srvhog and clihog from workload-kit. The binary srvhog has two commands, sleep and hog. Each operation takes 100ms. Sleep command is implemented with a timer and doesn't consume CPU, while hog command perform computation that last for the duration. A calibration procedure is performed when srvhog starts to ensure that the hog computation duration is close to 100ms. Communication between client and server is done by a simple TCP socket.

The following picture shows the CPU usage of the traced system, a host that has two cores, for the hog scenario. The overall CPU usage is shown in blue, while the CPU usage of srvhog is red. The calibration phase of srvhog last for about one second followed by a burst of about 100ms.

The second analysis shows blocking of clihog. It waits on system call read for 101ms, that correspond to the computation time of the server before reply is sent. Other blocking are very small and negligeable.

By analyzing socket operations of srvhog and clihog, the following graph can be computed. It shows that the client perform a connection to the server.

Finally, by computing resource accounting, the following report is obtained, showing that the CPU usage of srvhog while processing the request should be really accounted to clihog. CPU usage is almost 90ms, which is close to the expected 100ms and waiting time. The exact CPU usage is closer to 100ms and the error can be explained by the lost of precision while computing average CPU usage. To increase precision, smaller CPU usage intervals can be used.

Report for task pid=2668 cmd=/usr/local/bin/clihog

File descriptor blocking summary
FD                                       N    Sum (ms)
------------------------------------------------------
132.207.224.50:9876                      2     101,225

CPU accounting
PID                              Self (ms)    Sub (ms)  Total (ms)
------------------------------------------------------------------
2668 clihog                          2,675      89,797      92,471
 \_ 2666 srvhog                     89,797       0,000      89,797

Conclusion

Kernel analysis goes well beyong kernel developpers. Kernel trace can be very useful to system administrators and application developpers provided simple analysis tools that abstract trace events and produce meaningfull results to users.

Try it for yourself, see flightbox and workload-kit on github.

More to come, stay tuned!

Tracing Workshop '11

2011-05-10T13:03:00.001-07:00

I assisted to the Tracing Workshop held at the École Polytechnique de Montréal on 9-10 may 2011, here are some highlights of the event. Partners presented their challenges followed by current research conducted in the fields from many Canadian universities.

Partners

Partners mentioned the interest in security, debugging hardware, real-time systems, embedded systems and large scale distributed infrastructure.

On the security aspects, the goal would be to increase the accuracy of detecting intrusion. It's reported that simple attacks are often working, like sending an email with a link that loads some browser extension or other web site, up to get the user credentials.

The need to model normal behavior and alert when the system is going outside of it without false positive has been mentioned a lot.

In the field of large scale infrastructure, there are needs for understanding the system wide behavior of a distributed system at runtime. This is at the heart of finding problems fast on hard to reproduce problems, including kernel, and apps crash and performance slowdowns.

Monitoring a system modify the system behavior and the measure itself, even in the computer domain. In the embedded and real-time, first there is the challenge to put an upper bound to tracing impact, to make sure to respect timing constraints, even in the case tracing is enabled.

Research

Sebastian Fischmeister from the University of Waterloo presented research about using a sampling approach to tracing for real-time systems. He presented an approach to add hardware instruction for tracing, that would run it only if the timing requirements would be met.

Ashvim Goel from the University of Toronto talked about increasing security by recording all system calls to allow off-line analysis. Data is indexed to allow fast queries.

Greg Frank from Carleton University presented performance model based on traces. Execution paths at the system level can be modeled by a graph. Graph can be annotated with resource consumption.

Del Mayers from the University of Victoria presented a reverse engineering tool using tracing. By running the program with the desired functionality, then repeating the scenario without using that particular activity, it's possible to do a difference set operation on called methods and isolate with low noise level the classes and methods that implements this particular functionality.

Managing Apache config with Augeas

2011-02-23T07:37:00.000-08:00

Release 0.8.0 of Augeas includes a special lens for managing Apache web server configuration files. First, we will see how the lens maps sections and directives to the tree. Then, we will review some recepies to modify the configuration and show results.

Quick start

Apache configuration has two main components. The first component is section, which is similar to XML elements. Sections can be nested and contain directives. Directives are composed of a name and positional arguments.

As you may know, Apache is very modular. A module can define its own directives and Apache will run the module's callback to parse arguments. This is reflected in the way the configuration is handled in Augeas. The lens is mostly generic and allows arbitrary sections and directives, with arbitrary arguments. Apache allow case insensitive sections are directive. The actual version enforce that open and close tags to be the same case. I recommend to standardize the casing of the configuration for simplicity. Now, let's look at a small example, with one section and one directive.

<VirtualHost *:80>
  ServerAdmin foo@example.org
</VirtualHost>

This configuration produces the following tree.

{ "VirtualHost"
    { "arg" = "*:80" }
    { "directive" = "ServerAdmin"
      { "arg" = "foo@example.org" }
    }
  }

Let's say we want to modify the email address of the server admin, we can do a simple set:

augtool> set "/VirtualHost/*[self::directive='ServerAdmin']/arg" "bar@example.com"

To select the ServerAdmin directive, we need to search for it as a child of VirtualHost. We then set the first argument of the corresponding directive to a new value. Here is the resulting diff from the original file. If there are more than one VirtualHost entries in the file, then a simple set will fail, a set multiple (setm) is required to change them all at once.

$ diff -u httpd.conf httpd.conf.augnew 
--- httpd.conf 2011-02-22 22:03:34.000000000 -0500
+++ httpd.conf.augnew 2011-02-22 22:04:34.844099001 -0500
@@ -1,3 +1,3 @@
 <VirtualHost *:80>
-  ServerAdmin foo@example.org
+  ServerAdmin bar@example.org
 </VirtualHost>

Tree structure

There are 4 special things to know about the tree structure of apache configuration.

Section names are labels of the tree, they appear on the path.
Directives are held in value of a "directive" node.
Arguments of either sections or directives are held in values of "arg" node.
Arguments nodes must be before any other children.

To demonstrate this, let's create a configuration from scratch, and see it build at each step in augtool. First, launch augtool. I suggest to use the -n option to save to a new file.

$ sudo augtool -n

The variable $conf holds the path to the target empty file, for example under Ubuntu it would be:

augtool> defvar conf /files/etc/apache2/sites-available/foo

Step 1: create VirtualHost section

The clear command empty the value of a node and it create it if the node doesn't exists yet.
Command:

augtool> clear $conf/VirtualHost

Result:

<VirtualHost>
</VirtualHost>

Step 2: Set the argument of VirtualHost section.

Command:

augtool> set $conf/VirtualHost/arg "172.16.0.1:80"

Result:

<VirtualHost 172.16.0.1:80>
</VirtualHost>

Step 3: Create the ServerAdmin directive under VirtualHost.

Command:

augtool> set $conf/VirtualHost/directive "ServerAdmin"

Result:

<VirtualHost 172.16.0.1:80>
ServerAdmin
</VirtualHost>

Step 4: Set the ServerAdmin first argument to configure the email.

Command:

augtool> set $conf/VirtualHost/*[self::directive='ServerAdmin']/arg "baz@example.org"

Result:

<VirtualHost 172.16.0.1:80>
ServerAdmin baz@example.org
</VirtualHost>

The order matters

What if we perform step 3 before step 2? Here is the result:

augtool> set $conf/VirtualHost/directive "ServerAdmin"
augtool> set $conf/VirtualHost/arg "172.16.0.1:80"
augtool> print $conf
/files/etc/apache2/sites-available/foo
/files/etc/apache2/sites-available/foo/VirtualHost
/files/etc/apache2/sites-available/foo/VirtualHost/directive = "ServerAdmin"
/files/etc/apache2/sites-available/foo/VirtualHost/arg = "172.16.0.1:80"
augtool> save
Saving failed
augtool> print /augeas/files/etc/apache2/sites-available/foo/error/message = 

Failed to match ({ /arg/ = /[...]/ }({ /arg/ = /[...]/ })*)?(<<rec>>
| { /directive/ = /[...]/ } | { /#comment/ = /[...]/ } | { })*  

with tree

{ \"directive\" = \"ServerAdmin\" } { \"arg\" = \"172.16.0.1:80\" }"

I reformated the error message to highlight why it failed. The lens require "arg" nodes to appear before "directive", "#comment" and empty nodes. In this case, the node "directive" is before the "arg" node, and it doesn't match the tree structure. So, how to make sure that we insert nodes before any other? Here is the twist. First, we will remove the arg node and create it at the right place.

augtool> rm $conf/VirtualHost/arg
rm : $conf/VirtualHost/arg 1
augtool> ins arg before  $conf/VirtualHost/*[1]
augtool> set $conf/VirtualHost/arg "baz@example.org"
augtool> save
Saved 1 file(s)

And the corresponding result is the one expected. The predicate [1] will always select the first node in a node set and is equivalent to [position()=1]. There is one gotcha, that is if there are no children under VirtualHost, no node will match and the insert will fail. In this case, a simple set is required.

Also, take care to set a value to "arg" nodes! Otherwise, Augeas use the section name lens to render it. Here is the result of having an "arg" node with a null value.

<VirtualHost>
<arg>
</arg>
</VirtualHost>

Use cases

Modify document root

The first use case I show is to modify document root in the default configuration of Apache under Ubuntu. The default document root is "/var/www", but say we want to change it to "/srv/www". We have to modify the DocumentRoot directive and one Directory section. I'm using the match command to verify that the right node is selected before applying changes. (sorry for long lines...)

augtool> match $conf2/VirtualHost/*[self::directive="DocumentRoot"]
/files/etc/apache2/sites-available/default/VirtualHost/directive[2] = DocumentRoot
augtool> set $conf2/VirtualHost/*[self::directive="DocumentRoot"]/arg /srv/www
augtool> match $conf2/VirtualHost/Directory/arg[. = "/var/www/"]
/files/etc/apache2/sites-available/default/VirtualHost/Directory[2]/arg = /var/www/
augtool> set $conf2/VirtualHost/Directory/arg[. = "/var/www/"] "/srv/www/"
augtoo> save
Saved 1 file(s)

Here is the resulting diff.

--- /etc/apache2/sites-available/default 2011-02-22 23:30:48.000000000 -0500
+++ /etc/apache2/sites-available/default.augnew 2011-02-22 23:48:10.000000000 -0500
@@ -1,12 +1,12 @@
 
  ServerAdmin webmaster@localhost
 
- DocumentRoot /var/www
+ DocumentRoot /srv/www
  <Directory>
   Options FollowSymLinks
   AllowOverride None
  </Directory>
- <Directory /var/www/>
+ <Directory /srv/www/>
   Options Indexes FollowSymLinks MultiViews
   AllowOverride None
   Order allow,deny

Changing permissions

On Ubuntu, Apache is configured to serve documentation on http://localhost/doc/. We will share this documentation with everybody by changing Order and Allow from directive and delete Deny directive of the doc directory. We are using the regexp function to select the node with or without leading slash and with or without quotes. We remove all arguments of "Allow from" to make sure that arguments are sane.

augtool> match $conf2/VirtualHost/Directory[arg =~ regexp(".*/usr/share/doc.*")]/
/files/etc/apache2/sites-available/default/VirtualHost/Directory[4] = (none)
augtool> defvar dir $conf2/VirtualHost/Directory[arg =~ regexp(".*/usr/share/doc.*")]/
augtool> rm $dir/*[self::directive="Allow"]/arg
augtool> set $dir/*[self::directive="Allow"]/arg[1] from
augtool> set $dir/*[self::directive="Allow"]/arg[2] all
augtool> set $dir/*[self::directive="Order"]/arg[1] "allow,deny"
augtool> rm $dir/*[self::directive="Deny"]
rm : $dir/*[self::directive="Deny"] 3
augtool> save
Saved 1 file(s)

In this example, the predicate "*[self::directive='Allow']" can be rewritten "directive[ . = 'Allow']", both are equivalent.

Here is the resulting diff.

--- /etc/apache2/sites-available/default 2011-02-22 23:30:48.000000000 -0500
+++ /etc/apache2/sites-available/default.augnew 2011-02-23 00:10:14.000000000 -0500
@@ -33,9 +33,8 @@
     <Directory "/usr/share/doc">
         Options Indexes MultiViews FollowSymLinks
         AllowOverride None
-        Order deny,allow
-        Deny from all
-        Allow from 127.0.0.0/255.0.0.0 ::1/128
+        Order allow,deny
+        Allow from all
     </directory>

Conclusion

Augeas is a very powerful and precise tool to modify Apache configuration file. We can do about any changes with a very simple tree structure. As always, don't forget to reload Apache configuration for changes to take effect.

Thanks to David Lutterkort, who designed the amazing recursive lens that Apache lens uses and feedback for the square lens, and Raphaël Pinson for the feedback and stress test of the lens on more than 2000 Apache configurations and the help for this blog post.

Happy hacking!

Visiting Event Tracing for Windows

2011-01-27T11:19:00.000-08:00

In previous posts, we discussed Linux kernel tracing with LTTng. On the Microsoft side, Event Tracing for Windows allows to gather a kernel trace and user space trace. It's advertised as low-impact, lock-less, per-cpu buffers tracer, with live mode and circular buffers option. Quite interesting.
Here is a quick introduction to how to gather a simple trace on Windows 7 Professional and the different analysis we can get.

Installation

Obviously, you will need a Windows 7 Professional host. I installed it in a Linux KVM virtual machine, with 20GB of storage and with two CPUs emulated, with all default options.
First, .NET framework 4 has to be installed, required to install tracing tools bundled with Windows SDK.
In summary, you need to install:

dotNetFx40_Full_x86_x64
winsdk_web

It will install required tools for tracing: xperf, xperfview, tracelog and tracerpt.

Get a trace

To start tracing, open a console in administration mode, as shown in the following screen shot.

We create a trace directory for our experiments, and start and stop a simple trace with tracelog, as shown in the following screen shot. While tracing, you can start programs to create some activity on the system. I started IE and did some random browsing.

The trace file output is set with "-f" option. If a lot of events occurs, some events can be lost. If such a thing occur, increase the buffers size with "-b" option. Other options are there for some extra trace events, refer to help for more information. To give an idea of the disk requirement, I got a trace of about 20MB for a minute of tracing under light load. The trace file can hence become very big.

If the user doesn't have enough privileges for tracing, the following error message will be raised. Make sure the console is launched as administrator.


C:\trace>tracelog -f kernel.etl -start
Setting log file to: C:\trace\kernel.etl
Could not start logger: NT Kernel Logger
Operation Status:       5L
Access is denied.

Analyze the trace

Launch xperfview to start the Windows Performance Analyzer. Then, load the trace kernel.etl obtained previously. Here is what it looks like.

Disk access graph and CPU usage according to time and process in xperfview.

Process life graph and page faults by process according to time in xperfview.

Offset of disk access to detect system-wide bad seek behavior.

Summary of events count obtained from tracerpt

What I like about xperf is the ability to isolate resource usage per process. Also, zooming in a trace is intuitive by selecting with the mouse an interval that seems interesting. Trace events are completely abstracted as chart and statistics. There views are appropriate for understanding overall system performance. Also, when executable symbols are loaded, the call trace performance is available, which may be very handy for the software optimization.
The tracerpt utility outputs reports from a trace file, one is the count of all events and the report in HTML gives the statistics for the whole trace by subsystem. Here is an example of report.html generated with tracerpt.

Tracing a linux cluster

2011-01-07T13:10:00.000-08:00

Gather traces from multiple machines and then showing them all at once is a real challenge, because each computer has it's own independent clock. It means that two events occurring at the same time on two computers have a low probability to have the same time stamp in the trace.

Linux Trace Toolkit have a synchronization feature to adjust trace time stamps to a reference trace. It works by matching sent and received network packets found in traces. Two parameters are computed: an offset, but also a drift, that is the rate of clock change.

To experiment it, I did a virtual Ubuntu cluster of 10 nodes installed with LTTng. Virtual machines are sending each other TCP packets with the small utility pingpong while tracing is enabled. All traces are then sync to the host for analysis. Here are the results:

$ lttv -m sync_chain_batch --sync --sync-stats -t trace1 -t trace2 [...]
[...]
Resulting synchronization factors:
 trace 0 drift= 1 offset= 6.80407e+09 (2.551684) start time= 2433.182802117
 trace 1 drift= 1 offset= 4.12691e+09 (1.547687) start time= 2433.254700670
 trace 2 drift= 0.999999 offset= 0 (0.000000) start time= 2433.229372444
 trace 3 drift= 1 offset= 1.53079e+09 (0.574083) start time= 2433.366687088
 trace 4 drift= 1 offset= 2.31812e+10 (8.693471) start time= 2433.217954184
 trace 5 drift= 1 offset= 1.48957e+10 (5.586227) start time= 2433.280525047
 trace 6 drift= 1 offset= 1.76688e+10 (6.626211) start time= 2433.291125350
 trace 7 drift= 1 offset= 2.0463e+10 (7.674116) start time= 2433.325424020
 trace 8 drift= 0.999999 offset= 1.2206e+10 (4.577534) start time= 2433.204361289
 trace 9 drift= 1 offset= 9.55947e+09 (3.585022) start time= 2433.293578996
[...]

The trace 2 has been selected as the reference trace. We see inside parenthesis the offset between the current trace and the reference trace. We see a delay between each trace that match the delay between virtual machines startup. When loading these traces into lttv with --sync option, all traces events align perfectly, which is not the case without the sync option.

If you want to know more about trace synchronization, I recommend the paper Accurate Offline Synchronization of Distributed Traces Using Kernel-Level Events from Benjamin Poirier.

One simple note if you want to do this analysis, you need extended network trace events. To enable them, arm ltt with

$ sudo ltt-armall -n

I found it really interesting, because it allows to see cluster-wide system state.

CPU history from kernel trace

2010-12-09T08:51:00.000-08:00

Everybody is familiar with CPU history usage, for example with GNOME monitor. We see the average usage in time.

The GNOME monitor poll /proc/stats at regular interval to compute average usage. This file is updated by the kernel. The values comes from sampling that the kernel does for accounting various process.

How could we compute the CPU usage history from the actual kernel trace? We only have to look at sched_schedule events. The event inform us that in a certain point in time, the kernel switched the task on a given CPU. If the new task has PID zero, we know that's the idle thread from the kernel. By splitting running and idle time in fixed intervals, we can compute CPU average usage.

I show one small examples done on my computer that is dual core. First, we see the execution of three cpuburn process started with one second of delay. We can see the result in the control flow viewer in LTTV, and the resulting CPU usage view.

We see a peek at the beginning of the trace. This is likely to be related to the metadata flushing when a trace is started. The two steps after are related to each cpuburn process, and we see that when the third process is started, the CPU usage stays at 100%.

For testing, I added scripts to generate those traces automatically on your computer. It's written in Java, and you will need some extra packages to run it, see the README file. Get the code on github:

https://github.com/giraldeau/flightbox

Happy hacking!

Introduction to Linux Tracing Toolkit

2010-11-12T18:50:00.000-08:00

The Linux Tracing Toolkit next generation (LTTng) is absolutely amazing. In this introduction, we will look at how to interpret the kernel trace of a small program by comparing it to strace. If you want to install components and get a trace on your own machine, you can get packages for the patched kernel and other tools for Ubuntu Maverick in LTTng's PPA on Launchpad. You will also need build-essential to compile the small C executable, strace and hexdump.

Here is the small program. It opens a file and write a integer into it. Then, it adds number in a for loop.

#include <stdio.h>
#define INT_MAX 2147483647
int main(volatile int argc, char **argv) {
    int i = 3;
    FILE *fd = fopen("test.out", "w");
    fwrite(&i, sizeof(int), 1, fd);
    fclose(fd);
    volatile long a;
    int x;
    for (x = 0; x<INT_MAX; x++) {
        a++;
    }
    return 0;
}

Compile it, test it and run it under strace:

$ gcc -o usecase usecase.c
$ ./usecase
$ strace -o usecase.strace ./usecase

Ok. Now, let's run the program under tracing, but before, we have to enable all trace points in the kernel.

$ sudo ltt-armall

To get a tight window around the command, I'm using the small script trace-cmd.sh (see at the end of the post). The script simply starts tracing, run the program and stop the trace. Invoke it like this (don't forget to set the script executable):

./trace-cmd.sh ./usecase

Now, we are ready to launch lttv-gui, which is the utility to look at the trace. To load a trace, select File->Add trace, then select the "trace-cmd" directory created in the same directory as the trace-cmd.sh script. Then, scroll down to the "./usecase" process in the control flow viewer, which is in the middle of the window. Each trace events are displayed under the graph. I will present three phase of the process. First, the creation and file access, then computation phase and the process exit. Trace is rotated to make it more readable. Events name and comments are embedded in the graph. strace events are in red, while related code is in blue.

In addition to system calls, we can look at the paging of an application and see process starvation. This information is not shown by strace. Another cool side effect is that, contrary to strace, the running program can't detect it's under tracing, then we can trace viruses that otherwise quit before they can be analyzed. Tracing reports much more information about kernel internals, which helps a lot to understand what's going on. Events timestamps of the kernel trace are in nanoseconds, so the precision is really high, and since trace points are static (simple function calls compiled right into the kernel), performance impact is ridiculously low, below 3% for core trace points! I'm running LTTng in background on my system without noticeable impact, in flight recorder mode.

I will be working on advanced trace analysis for the next three years or so for my PhD. Since LTTng got all the feature I need for tracing, I will use this tools. My first goal is to create a CPU usage view. Say that something was eating your CPU a minute ago, then with kernel tracing you would be able to go in the "flight recorder" history and see what was running at that time, and understand what was going on.

You can help me in two ways. First, by submitting your ideas about cool trace analysis we could perform and/or you need. Second, you can write to Linus Torvalds and ask him to merge LTTng in mainline. LTTng is the right stuff we need for tracing and it's a bit a shame that this not merged yet while other operating systems have this since a decade.

Next post will be about TMF, an eclipse plugin for trace analysis! Stay tuned!

Script trace-cmd.sh:

#!/bin/sh

if [ -z "$@" ]; then
    echo "missing command argument"
    exit 1
fi

cmd="$@"

name="cmd"
dir="$(pwd)/trace-$name"
sudo rm -rf $dir
sudo lttctl -o channel.all.bufnum=8 -C -w $dir $name
echo "executing $cmd..."
$cmd
echo "return code: $?" 
sudo lttctl -D $name

Scary pumpkin

2010-10-22T13:08:00.000-07:00

I left my computer for few minutes to carve the scariest pumpking for any programmer, the Big O factorial time pumpkin!

Terrifying, isn't?! Hand carved into a local organic grown pumpkin, low power lightening with LEDs, eatable after use, I'm ready for an happy hacking halloween!

Augedit: regedit for Linux

2010-10-08T06:48:00.000-07:00

Few months ago, a prototype of GUI for Augeas was posted on the augeas-devel mailing list. I found it awesome, so I wanted to take it further. I think this is the kind of tool that can easy the configuration management on Linux, like regedit does on Windows. It's still require knowledge of what you're doing, but at least, you don't need to worry about the syntax of a particular config file! Here is a screenshot of the latest version.

On the left pane, there is a GtkTreeView, that shows the tree path and the corresponding value, if any. Then, on the right pane, there is the actual file, where the label and the value are highlighted. At this early stage, the views are read only, but the goal is to make any side editable and make the changes propagate to the other side.

Some of ideas that this kind of tool should have: basic edit operations (add, modify, move, delete, ...) searching, filtering, bookmarks, auto-completion.

If you want to try it, you will need the "myhead" branch of augeas, up to date python-augeas branch "aug_info" that adds the API function for highlighting, and the code of Augedit itself.

http://github.com/giraldeau/augeas
http://github.com/giraldeau/python-augeas
http://github.com/giraldeau/augedit

Leave your ideas about this tool in comments! ;)

Windows Phone 7 adventure

2010-09-02T22:21:00.000-07:00

I went to Ottawa Mobile Conference, and I won as a presence prize 2 day training on Windows Phone 7 (WP7) plateform, at the Microsoft office in Ottawa. The training is provided by Colin Melia from DevTeach, which is knows the plateform very well. This was for me the occasion to get an idea of what it will look like. With the iOS, Android and RIM devices, is there a place for WP7? What it stands for? Millions of theses devices are supposed to hit the market before Thanks Giving in the US, made by Samsung, LG and Dell and others, so it has to be good.

WP7 is the Microsoft implementation of the whole mobile concept from Apple. Mobile Market is equivalent of AppStore, Zune have the same role as iTunes to sync the device and basic apps are about the same, except they are based on Microsoft technology, for example Internet Explorer replace Safari, Bing map and search replaces Google. A light version of Office and SharePoint may be free on the phone for the release. XboxLive will be the basis for all games on the device. Interesting fact, IE doesn't ship with Flash plugin. Seems that Microsoft agree with Apple on this point.

Concerning the interface, it uses the design pattern Hub and Spoke, that force the user to focus on one task at a time. A tile view of apps acts as the Hub. There are three mandatory physical button on the phone itself: back, start and search. Back goes to the previous view, start goes to the tile view and the search go to Bing. There can't multi-process running simultaneously, the same as the iPhone before multitasking. Say that you start an app, then go to the tile view and start another app, the first app instance is lost.

You can use two different libraries for an app, Silverlight for straight forward forms or XNA for games that requires more heavy video display. We saw mainly how to use Silverlight to design the UI. The application code can be written in C#, using the .NET framework classes. What is realy interesting is the clear separation between the logic and display of the application. It has been thought in such a way that the designer can work on the view independently of the programmer, that fills the view. Some preview data can be supplied to the view at design time, so the designer doesn't need the whole application to work. The UI is completely defined in XAML file in a declarative manner. A factory then read the file at runtime and create corresponding objects. .NET library provides a high level of abstraction for XML handling, HTTP and SQL queries, so in very few lines of code, a lot of things occur.

For those of you who may want to give it a try, here are some notes about installation on a MacBook Pro 1,1. The requirement and installation instructions are accurate. You need the VMX extension for virtualization to get good performances. It has to be enabled into EFI boot loader. See the Parallels knowledge base to get instructions. Microsoft supplies a small utility to check if the extension is available. But, maybe more critical is this MacBook Pro have an ATI X1600 card, and the latest (and the last) driver from AMD doesn't support WDDM 1.1, which is required for decent display performance with the phone emulator. Any computer with proper drivers for Windows 7 should do, it just means I will need a new computer to run the emulator appropriately.

In conclusion, Microsoft is jumping in the arena seriously with WP7. SDK is quite lean yet, and this is a great piece of integrated technology AFAIK. Their first step is obviously to copy recipies of competitors with their own technology. It's right, because innovation comes a lot from inspiration from others. iPhone is still the blue ocean device, and except for the Office app, there is nothing that a WP7 seems to do better, so the price point must be somewhat attractive to change the market forces. The fate of WP7 is now in the hand of customers.

No network, no problem!

2010-08-31T11:28:00.000-07:00

I got a brand new smart phone, and the first thing I noticed is that it worth nothing without network. Wifi hotspot availability is uncertain, everybody has yet beg someone to get some access. 3G data is still expansive. Roaming above all, at 20$ bucks per megabyte, could ruine somebody looking at few youtube videos. And even 3G network is not always available, for example in subways, and will make your device as useful as a stone.

We already know the solution: data cache. At least, a device with some type of cache will be useful at some level. I want to bring with me my own files on any of my devices. This way, we do not rely on the cloud for every lookup, and we can sync with low cost network connexion when it becomes available. Mail is an obvious example of asynchronous system that is working well. With IMAP and a good mail client, you can get a cache of all your emails, read them when offline, even compose an email and send them later when network is back.

Another drastic example of a device that rely only on a cache is the WikiReader, that I bought recently. It has a cache of all 3 millions Wikipedia articles on a 8 Gb SSD card. It can be updated with a computer or by subscribing to an update service by old fashion mail. Never forget that a truck loaded with SSD cards has a lot of bandwith!

Though, keeping in sync multiple disconnected data sets is harder. Yet, many interesting projects, like the distributed replicated database system CouchDB, used in Ubuntu One for online services, borrow my contacts where ever I need them. At the file system level, I'm using Dropbox that replicates my files on all my devices. Beyong replication, it acts as a continuous backup, so I don't worry anymore with hard drive crashed. Also, HTML5 cache is a great addition, and can be used to lower your precious G3 bandwith, server load and lower latency. Those are example of disconnected aware cloud services, that I think are going to take off.

This said, sync all data does make sens only if the device belong to the user for a fair amount of time. In the case of shared workstation, for example a school lab, roaming profiles are known to be a disaster, because the data has to be synchronized from scratch multiple time, and it makes the cache useless. We may think of better synchonization, based on the content the user uses frequently, and fetch other things on demand. But the "keep it simple and stupid" way would be to make user reuse the same computer, or at least the same set of computers, and not flush the cache. Keeping users files on a shared computer is always tricky for privacy reasons, but providing encryption based on the user's credentials could be a solution. Another solution would be to let the student own and borrow their computer. With all those Linux mobile tablets that are going to hit the market soon, I think that it will create a great opportunity for providing affordable computers to each and every students. And with 16Gb of flash storage on basic models, there is enough room to cache almost everything! This way, the cache hit will be much higher, and users will be happier.

In summary, let's take a GPS as an example. Would you prefer a GPS that downloads all it's bitmap maps just-in-time, that rely heavily on network, or a GPS that is using it's embedded geo data. The later will not work without network, the later is not ofter updated, or even not at all. What I would consider the best design is to get a device with both. The mapping data should be embedded and rendered on the device itself, and this sort of cache should be updated each time you get network. Or even if you don't have all the data, you should be able to select areas to cache.

In conclusion, the cloud is so fantastic that we sometimes forget that without a link to it, we're screwed. I consider that devices that are not designed to work without network is bad design, and those devices will end into the Computer History Museum soon.

Firefox memory management nightmare

2010-08-08T12:28:00.000-07:00

Can you believe that you can crash any linux machine with a web page displaying stamp size images, while an iPod can display it without an glitch? Try this dead page with you browser, that displays large images resized and watch your memory usage.

WARNING: this page requires ~300Mb RAM to display!

https://pages.usherbrooke.ca/fgiraldeau/crashff/

Ok, what's going on? I did a small utility to monitor the memory usage of Firefox, and the memory usage was quite normal. Where did all this memory allocation occur? After few top, it appears that the Xorg process blew up. Here is a graph that show both process on crashff loading.

Memory consumption for crashff page loading according to time

The test shows the page loading, opening other tabs and coming back to the original page. The full scale image is transfered to the Xserver for rescaling the image. On localhost, it's fast, but when Firefox is started remotely, then all this data has to be transfered on the network! After a while, the image is flushed from Xserver, and display the tab requires doing all this work again. And because the Xserver allocates the memory, if you run out of memory, the Out Of Memory (OOM) killer of the kernel will be triggered, but it's likely to kill the Xorg process and leads to the user's session lost. This is really critical.

There is one optimization that may help this, and wanted to know the impact. When setting MOZ_DISABLE_IMAGE_OPTIMIZE to 1, it was supposed to change the behavior. Let see the same experiment with this environment value set.

Memory consumption for crashff page loading, with optimization, according to time

Ok, so we see that the Xorg process stays at some low level of memory usage, this time firefox blows up. At least, if the user hits the memory limit, then only the Firefox process gets killed, and the user's session will not crash.

I did also the test with Opera 10.60.6386 and Konqueror 4.4.2, and the result is mostly the same as with Firefox with optimization. Konqueror uses a less memory, and doesn't deallocate the tab, so when displaying it again, it's really fast. Here are the graphs.

So MOZ_DISABLE_IMAGE_OPTIMIZE does the trick, and IMHO, this option should be the default.

Note: this blog is related to this firefox bug: https://bugzilla.mozilla.org/show_bug.cgi?id=395260

Mouse safety

2010-07-03T08:01:00.000-07:00

For those of you that are working long hours in front of a computer, you may encounter pain in your wrist at some point. This may be caused by repetitive movement, that creates inflammation of tendon.

The inflammation can be treated with ice, rest and acetaminophen (paracetamol). But the cause, for me, was the abuse of the scroll wheel. Since I'm avoiding to scroll, my hand and wrist pain diminish progressively.

Hope that this trick helps you. Happy hacking!

APLWACA what?

2010-06-09T11:36:00.000-07:00

I went to the conference Analysis and Programming Languages for Web Applications and Cloud Applications (APLWACA) held in Toronto, and I wanted to share one cool stuff I learned: Javascript security.

The kenote was about the security of untrusted Javascript that browsers may run. This is actually happenning because trusted website can embedded code from other, like analysis code to gather statistics and display ads. Here are two examples of those threath.

This code will replace every links in a document to somewhere you don't trust.

els = document.getElementsByTafName("a"); 
for (var el in els) {
    el[url] = "http://dangerous-site.com/";
}

Another bigger threath is that, if you have an active session with a trusted server, then the actual embedded Javascript code can interact with your session like this:

var x = window.XMLHttpRequest();
x.open("/account");
x.send("some nasty command");

To prevent this, all code from untrusted Javascript should be wrapped to prevent calls to XMLHttpRequest. Here is an actual snippet of code that verify simple lookup o[s].

lookup function(o, s){
    if (s == "XMLHttpRequest"){
        return "Not allowed";
    } else {
        return o[s];
    }
}

Some implementation of this kind of wrapper exists, like Facebook Javascript, Google Caja and Yahoo ADsafe. But, how can we actually prove that these wrappers are safe, and they really don't allow to execute the XMLHttpRequest? For example, our simple lookup, s may be an object, will not be equal to the searched string and will be evaluated. But then, s.toString() function will be evaluated, and can return "XMLHttpRequest"!

The solution proposed is to statically typecheck Javascript. String that may evaluates to "XMLHttpRequest" are carried, and then all code is checked to look at unsafe calls that may be made.

Static typecheck has been performed on ADsafe itself. It showed one possible exploit as far. The result is that it could be possible to prove it's secure.

In the mean time, disabling Javascript may not be a bad idea after all...!

Square lens for Augeas

2010-06-01T10:04:00.000-07:00

Augeas has the ability to handle XML like tag. Here is an example of how to do it with key and del lens in a simplified version for a paragraph tag of an HTML document.

let para = [ Util.del_str("<") . key "p" . Util.del_str(">") .
 store /[a-zA-Z0-9 \r\n\t]*/ .
Util.del_str("") ]

That's working fine, but there is a gotcha: we have to list all HTML tags as strings, not as a regexp. Let's create a new version of this lens to process arbitrary tag.

let tag = [ Util.del_str("<") . key /[a-z]+/ . Util.del_str(">") .
 store /[a-zA-Z0-9 \r\n\t]*/ .
 Util.del_str("</") . del /[a-z]+/ "abc" . Util.del_str(">") ]

Let see what happens with the tree cases get, put and create.

The get will accept arbitrary tags and set the node label accordingly

text ---> {"p" = "text"}

The put direction, without updating the label, will yield correct result

{"p" = "text"} ---> text

In the create operation, in the case of a new label, this will yield the default value for the close tag, and this will produce a syntax error

text ---> {"p" = "text"} ---> {"b" = "text"} ---> text</abc>

Also, this lens accepts a malformed tags, like "<a>text", and we should throw an error in this case.

We need that the closed tag be linked to the key. The square lens is just about that. Let's rewrite the example with the square lens. The lens takes two arguments. First, a regexp that describe the tag, and behaves as a key. The other is a lens that represent what's inside the tag.

let content = Util.del(">") . store /[a-zA-Z0-9 \r\n\t]*/ . Util.del_str("<")
let tag = [ Util.del_str("<") . square /[a-z]+/ content . Util.del_str(">") ]

The first difference is that, now, the open and close tag are related. In the get direction, we can test that the second tag is the same as the first, and then detect syntax errors in the input document. The other difference is about the create operation in the put direction, because now we can copy the key of the node at the end of the content, and then yield correct behavior.

"text" ---> {"p" = "text"} ---> {"b" = "text"} ---> "text"

The first lens to benefit from it will be httpd.conf lens. Stay tuned, the patch is cooking!

Character feedback for XSugar

2010-05-14T09:31:00.000-07:00

In the previous post, we showed that embedding white chars inside the XML is not a viable solution for strict bidirectionality. Automaticaly pre-process the modified XML to fix it and make sure it conforms to the stylesheet seems not possible based on the stylesheet itself, because the XML tree and AST tree are both orthogonal and not related to each other.

How does it works in Augeas? Augeas is based on lenses primitives and combinators. The one we are most interested here is the del lens. In the put direction, the del lens remove the matched content, and stores in a skeleton. In the put direction, the lens restores the original content from the skeleton or provides a default value in case of a new node. The skeleton values are retreived either by sequence or by key. To understand the difference, let's see what happens in case of a subtree move. If skeleton is aligned by sequence, then deleted content by the del lens will be restored in the order in which it appears in the original document. It means that white chars are sticking in place while the content move. In the case of insert, every record following the insert will be modified and get the previous skeleton value, and the last record will get the default value. This behavior doesn't correspond to minimal edit. A better approach is to use the key alignment. Then, skeleton is matched by key, and the correct original chars are selected even in the case of move, insert or delete of records.

The idea behind this principle of operation is to create a feedback of the original document to insert previous values when possible, while preserving modifications.

It's possible to do something similar in XSugar, by working on the AST level. In the rest of this blog, I present the principle of operation, a prototype with basic algorithm, obtained results and conclusion about this solution.

The goal is to to get back original white chars inside the updated document, without embedding them in the XML document. By using the strict version of the stylesheet, where every items are labeled, the resulting AST preserves every parsed chars, and we call strict nodes those that contains chars that would have been lost otherwise. Then, we could use this strict AST to match nodes from the updated XML and the original document, and then copy only strict elements from the original to the updated document.

The matching algorithm used to test this hypothesis works as follow. For each node of the first tree, search in the second tree a node where each child labels and text matches, except for strict nodes. The algorithm works by traversing the AST in level order, and has a complexity of O(n^2).

Here is the expected behavior of this simple algorithm.

Round trip without updating content should restore all original values.
Inserted node should get default values.
Updated nodes should get default values, because they will not match any previous values. They are handled the same way as an insert.
Moved nodes should get their original values.
Deleted nodes should not render any previous associated value.

To test and highlight the behavior, I modified slightly the students.xsg example. Here is the format of records that the stylesheet parses :

( [0-9]+ [z]+ [0-9]+ [a]+ )* 

Hence, two numbers are separated by space, and multiple records are separated by new line, but "z" represents spaces and "a" represents new line. The default number of z's and a's is one, to show the behavior, we use two and more chars to detect when a default value is inserted.

A parse tree and a match between original document and updated document in which a record has been deleted is shown in the following figure.

Here are the results of tests.

Test 1 : round trip without modifications

input:     1zz1aa11zzz11aaa111zzzz111aaaa

default: 1z1a11z11a111z111a

merged:   1zz1aa11zzz11aaa111zzzz111aaaa

All characters are recovered, and the resulting document is exactly the same as the input.

Test 2: insert

input:     1zz1aa11zzz11aaa111zzzz111aaaa

default:  1z1a11z11a99z88a111z111a

merged:  1zz1aa11zzz11aaa99z88aaaa111zzzz111a

The new record "99 88" gets a default "z", while the last record gets a default "a".

Test 2 : move

input:    1zz1aa11zzz11aaa111zzzz111aaaa

default: 1z1a111z111a11z11a

merged:   1zz1aa111zzzz111aaa11zzz11aaaa

The moved record gets the right number of "z", but "a" chars keeps their order.

Test 4 : delete

input:     1zz1aa11zzz11aaa111zzzz111aaaa

default: 1z1a111z111a

merged:   1zz1aa111zzzz111aaa

The central record is deleted, and the last record gets 3 a's in place of 4.

From this results, we can see that strict elements z's are retrieved by keys, and a's by sequence. This is caused by the fact that branch nodes that have only one strict leaf nodes are match by their level in the tree. We can't determine if this node should be matched to the parents, or are themselves a parents for other nodes, and in consequence, sequence match is the only remaining possible match. As I understand, other tree matching algorithms can't address this issue.

The algorithm can be improved to match nodes by leaf node string similarity, using Levenshtein distance. It may be possible to restore chars from updated nodes. But then, the match will depend on the number of changes made to the document, and a node may match another one more similar, may confuse the user by an apparent non-deterministic behavior and may produce non-minimal edit.

In conclusion, we showed that it's possible to use the original document to merge back otherwise lost chars. But, alignment of original content is mixed between sequence and key. The user can't control which one will apply. It may lead to non-minimal edit of the resulting file. In that respect, lenses primitives and combinators used in Augeas provides a more predictive behavior, by letting explicitly choose between key or sequence alignment by the lens developer.

Limitations of XSugar

2010-04-09T12:14:00.000-07:00

In previous posts, I explained how XSugar could be used to transform configuration files to XML and back. Preserving white characters (space, tab, carriage return, etc.) is possible by creating special elements to hold them. In a simple round-trip, when the XML document is not modified, it works well. But, there are issues when the XML document is modified. For example, be this simple XML with strict nodes, from the students example of XSugar.


<students xmlns="http://studentsRus.org/">
  <student sid="19701234">
    <name>John Doe</name>
    <email>john_doe@notmail.org</email>
  </student>
  <space1> </space1>
  <space2> </space2>
  <newline>
</newline>
  <student sid="19785678">
    <name>Jane Dow</name>
    <email>dow@bmail.org</email>
  </student>
  <space1> </space1>
  <space2> </space2>
  <newline>
</newline>
</students>

There are spaces and newline elements that follow the student record. They are used to restitute the exact formating of the original string. We can then modify an existing value, and spaces will be preserved, and this correspond to a minimal edit.

But, say another record is inserted after the first student, but before space1 element, then the first record will see it's spacing reset to default values, and the new inserted element will get the spaces from the first record! This doesn't correspond to minimal edit, and is similar to alignment problem found by Foster et. al. in Boomerang.

If a student element is removed, but spaces elements are left, then it will cause a syntax error according to XSugar stylesheet. If an element is moved, it must inserted to right place in the XML, otherwise syntax error may occur.

It may be possible to fix the XML before transformation to non-XML, by adding, moving or deleting space elements. The idea to use the original document and the modified one to produce the updated output is already what does a lens, and is exactly what Augeas does. And now, with the introduction of the recursive lens, Augeas is about to support context-free languages, and opens the door to handle the Web server Apache configuration, and many other.

That's all for now, stay tuned!

Static validation of strict bidirectionality

2010-03-11T20:00:00.000-08:00

These days, I had some fun to validate XSugar stylesheet for their strict bidirectional property. XSugar can convert non-XML documents to XML documents, and vice-versa. In theory, you get back exactly the same file if it does a round-trip to and from XML. But, there are few tricky things that prevent it to be exactly the same. XSugar verify statically the reversibility of a stylesheet, by verifying that both grammars are bijections. It means that there is no ambiguity, and so there will be always one way to do the conversion. But, not all stylesheet that are valid in this respect will yield correct behavior when performing actual transformation. The problem is linked to the fact that some white spaces may be lost in the transformation. To understand the problem, I will use a concrete example.

Say you have the following file, and want to convert it to XML. There are a bloc of numbers lines followed by words lines. Elements are separated by space, and there may be spaces before and after each lines.

  123  456  789  
  987  654  321  
  abc  def  ghi  
  ihg  fed  cba

We will convert this file to the following XML.

<?xml version="1.0" encoding="UTF-8"?>
<a xmlns:b="http://udes.ca/noesis">
  123 456 789
987 654 321

  <z>
    <y>abc</y>
    <y>def</y>
    <y>ghi</y>
  </z>
  <z>
    <y>ihg</y>
    <y>fed</y>
    <y>cba</y>
  </z>
</a>

The stylesheet looks like this...

xmlns:b = "http://udes.ca/noesis"

NUM = [0-9]+ (MAX)   /* numbers */
ALPHA = [a-zA-Z]+ (MAX) /* letters */
NL   = \n|\r|\r\n   /* mandatory new line */
SP = [ \t]+ (MAX)   /* mandatory white space */
OSP = [ \t]* (MAX)   /* optional white space */

/* top-level rule : define the whole document */
a : [xs x] [ys y] = <a> [xs x] [ys y] </>

/* sequence of lines of numbers separated by space, with optional leading and endin white space  */
xs : [OSP] [ns n1] [OSP] [NL] [xs n2] =  [ns n1] [NL] [xs n2]
: =

/* numbers sequence */
ns : [NUM num] [SP] [ns n] = [NUM num] [SP] [ns n]
: [NUM num] = [NUM num]

/* sequence of lines of words separated by space, with optional leading and ending white space */
ys :[OSP] [y y1] [OSP] [NL] [ys y2] = <z> [y y1] </> [ys y2] 
: = 

/* sequence of <y> elements that hold actual words */
y : [ALPHA alpha] [SP] [y y1] = <y> [ALPHA alpha] </> [y y1]
: [ALPHA alpha] = <y> [ALPHA alpha] </>

... and it validates well.

$ xsugar -b strict-test3.xsg
Transformation is guaranteed to be reversible!

But, when we actually try to convert the XML back to the non-XML format, we get a parse error on char 74. When activating the debug mode of XSugar, we can see the result of XML normalization, which is a preparation step done before parsing.

Normalized input:
<a>123 456 789
987 654 321<z><y>abc</><y>def</><y>ghi</></><z><y>ihg</><y>fed</><y>cba</></></>

We see that spaces and carriage return before and after the number text node are lost. This is because the interleaved text with other element is trimmed. Spaces inside the text are preserved by the trim. This doesn't occur when an element contains only text. The parse error occur because the last mandatory new line is dropped. Let's fix the xs rule.

/* sequence of lines of numbers separated by space, with optional leading and endin white space  */
xs : [OSP] [ns n1] [OSP] [NL] [xs n2] =  [ns n1] [NL] [xs n2]
: [OSP] [ns n1] [OSP] [NL] = [ns n1]

This makes the last return carriage optional, and parsing succeed. Let's look at the diff between the result and the original file.

$ diff -u strict-test.txt strict-test3.txt.back
--- strict-test.txt 2010-03-05 15:33:52.043893254 -0500
+++ strict-test3.txt.back 2010-03-12 00:23:12.482905316 -0500
@@ -1,4 +1,4 @@
-  123  456  789  
-  987  654  321  
-  abc  def  ghi  
-  ihg  fed  cba  
+123 456 789
+987 654 321
+abc def ghi
+ihg fed cba

The content is there, but the actual diff shows that every lines are modified. This is because some terminals are not labeled. When this is the case, their values are lost, and example string is generated back when there is not corresponding item. It explains why spaces are all reset to their default values, the empty string for the optional white space, one space for the mandatory white space, and the default carriage return.

Hence, we have to look at two things to make sure stylesheets are strictly bidirectional.

First, the easy part, all items in the stylesheet must be labeled. This way, we can be sure the XML document will contain all chars from the input, and no information will be lost. We only have to traverse the stylesheet and make sure that every RegexpTerminal are labeled.

Second, interleaved text nodes must not begin or end with white characters [ \t\r\n], otherwise those chars will be lost. This is harder to do. First, we must detect if an element contains text nodes, elements, or both, from the stylesheet. Determining this for StringTerminal, RegexpTerminal and Element objects is straight forward. First two generate text, while the other yield elements. But, this is non-trivial for Nonterminal objects, because of the recursive nature of these items. The problem is a chicken and egg problem, because to determine the actual possible values for a nonterminal, we have to compute this nonterminal and substitute it's actual value in a recursive rule, which produces a loop. One solution to this problem is to compute the regular approximation of the XML stylesheet rules. It yields an automaton for each nonterminal that accepts a superset of the XML content than the stylesheet allow. Here is an example for the rule y.

We can know which kind of content this nonterminal have by looking at the transitions of the automaton. In the last example, we know for sure that the nonterminal will yield only elements. The last step is to verify that the interleaved text content beginning and end may overlap with white chars. Here again, regular approximation of nonterminal is used, but this time on the grammar itself. The overlap operator, used for horizontal ambiguity detection, is used. If such overlap exists, such as "WHITE <-> TEXT <-> WHITE", information lost may occur.

With this new information, developers can adjust the stylesheet to label items and enclose text inside elements and prevent information lost.

In summary, strict bidirectionality is required to prevent lost information in a transformation round-trip. Information lost can be caused by unlabeled items in the stylesheet, or because of trimming of interleaved text nodes. A method to detect areas that may not be strict, based on regular approximation of the stylesheet and the grammar, using the overlap operator, is proposed. Results from different stylesheets will be given soon. Stay tuned!

Why iPad is Evil

2010-02-06T15:31:00.000-08:00

Apple just launched the iPad last week, and I was a bit shaken by it. It's a piece of art of human interaction design, and it changes the relation we could have with a computer, more ubiquitous than ever. The device itself is amazing at the technical level, and set the bar for competitors.

But, let's think about the concept in a whole. Apple provides stores for music, books and applications. In fact, this device is a personal buying device, where you can buy only content provided by Apple and it's partner. It's a kind of perfect world, where the consumer is captive like anything ever before, a garden of pure ideology, in each one may bloom, secure, away from the pests, and ... wait a minute! Doesn't it makes you think about 1984?

http://www.youtube.com/watch?v=OYecfV3ubP8

What a closed world we would be in if Apple had dominated the market, closed hardware, closed software, and forced to buy content from Apple!

So, I say no to that iPad, and I will wait for an truly open platform.

Strict reversibility in XSugar

2009-12-23T13:26:00.000-08:00

XSugar is a tool to do bidirectional transformations between two file format. This is particulary useful to provide common API to configuration files under Linux. For example, here is the result of a stylesheet on /etc/hosts file :

<hosts xmlns="http://usherbrooke.ca/">
<record>
<ipaddr>127.0.0.1</ipaddr>
<canonical>localhost</canonical>
</record>
</hosts>

This file can be converted back to it's flat format. But, as you may notice, indentation doesn't appears in the XML file, and will be lost. Spacing is reset to a default value. The round-trip between hosts file and XML format keeps the semantic, but looses formating. Even without modification, if the file is written back, diff will show changes. Once spaces are reset, round-trip will yield identity function i.e. strings will be exactly the same.

One solution to overcome this problem is to add to the XML all elements that would be lost otherwise. This can be done by labeling terminal elements, and add corresponding nodes to XML part of the stylesheet. For examples, this rule loose optional "a" header :

A = [a]*
X = [x]+
n : [A] [X x] "z" = <x> [X x] </x>

Providing input "aaaaxxz" will give the following XML :
<x>xx</x>
Converting it back to non-XML will yield the string "xxz". Since the empty string matches "[a]*", this is the default string that is returned.

Now, let's label the terminal "A" :

A = [a]*
X = [x]+
n : [A a] [X x] "z" = <x> [X x] <a> [A a] <a></x>

Now, we get the string
<x>
xx
<a>aaaa</a>
</x>
and converting it back to non-XML format yield "aaaaxxz", the exact same string as the original input.

Preserving semantic of the file is simple bidirectional property. In addition, if the stylesheet preserve the concrete representation of an input, I call this strict bidirectionality.

Strict bidirectionality can be achieved by labeling unlabeled terminal, and add corresponding element to the XML part. I did a small prototype of this algorithm, that augment the resulting stylesheet. Hence, any stylesheet can be made strict bidirectional.

It rises the question : can we staticaly verify that a stylesheet is strictly bidirectional. Hopefully yes, it's really simple. We have to do the basic check that the stylesheet is bidirectional, and then verify that all regular expression terminal are labeled. This way, we are sure that all the variable concrete string will be represented in the XML.

Automatic strict bidirectionality for stylesheet and static validation of this property will be useful to provide the behavior a system administrator would expect from a tool that modify configuration files under Linux. Let's go on!

Bcfg2 V.S. Puppet

2009-12-18T07:45:00.000-08:00

Bcfg2 and Puppets are two tools for system configuration management, where we want to install configuration files, packages and adjust permissions. It seems simple said like this, but it's near from trivial when the target machines are various operating system and versions.

Bcfg2 and Puppet, while they share the same goal, are completely different in terms of their concepts, how does the desired state is modeled. The fundamental concept here is more important than the actual implementation.

Puppet is like a programming language for system administration. It's another meta-language, with it's own syntax, to indicate what files, packages, users and such, should be present on a system. It's concepts are very close to Cfengine. Well, I used Cfengine a lot, even developing a small utility to automating the management of files under Subversion (svnengine). But, while using this tool, I really came to one simple conclusion : what a mess for so little! I ended up doing everything in scripts, which are copied by cfengine and run in a cron. Big deal.

Bcfg2 is not the same, because unlike Puppet, you don't program configuration elements, they are declared in XML document. The client, specific to a target, encapsulate actions on that target, their sequencing, error handling, etc. This model enables advanced behavior, because the model can be manipulated programmatically, which is not the case for Puppet. If you want to output a Puppet manifest, you have to output strings, which is a Middle Age practice!

Bcfg2 implementation itself has some glitches that must be fixed, but the concept behind it represents a building block for semantic system configuration management, which represent the future. Bcfg2 belongs to scientific field, while I think that Puppet has the exposure it has now because of marketing wave.

But, as the history reminds us, it's not always the best product or software that wins...

Pragmatic testing

2009-10-17T14:24:00.000-07:00

It's certainly a matter of fact that good practice in software development include automated testing. Developing without unit tests is stone age practice. I read few books about testing, and many of them are about writing bureaucracy plans, not code. Reading documentation about unit testing framework doesn't provide much information about how to design tests. Here are few learnings from my experience.

Automated tests should be easy to write and run. If they are hard to run, if they require a special manual setup, then they will be run infrequently. If you need a database or a daemon, it should be setup and launched automatically on localhost by test running scripts. Default config that just work should be provided to avoid configuration mess. Document needed packages from known archives to run tests, that may be different than running or compiling the software.
Take care to apparmor when trying to launch a daemon with unusual locations : it may fail to start because of security restrictions. Disabling it may be necessary in some conditions.
If the program operates on file, then create them in a temporary directory, flushed at each run. A program that copy files is testable : execute the operation and verify that files are where they should be.
Running tests should be fast. if testing requires few minutes each time, and you are interested only to the result of one of them, it's not efficient. A simple solution is to provide a way to test only a subset of all tests.
Running tests should usually not require root access, excepted for special purpose. If you bind ports, use a port over 1024 to avoid restrictions. Don't use global settings, use relative path to settings and files. If you get data from system library, you can simulate obtained data by providing objects with the same interface.
Software always operates on data. You will need test data that simulate possible inputs. If your application reads input files, then those files should be held beside test code.
One tests should not depend on previous test to succeed, they should be independent. In other words, the result should not depend on the order in which tests are executed. To make sure that tests are not linked together, always start from a known state. It means reloading initial data for each test, recreating objects and such. This is conveniently done with setup and tear down method usually available from unit testing framework.
Test Driven Development is about creating test and code for some functionality together. This is the basic thing to do to make sure at least it works. Testing can go further for critical code, by trying to break the code, use it in ways that it may not have been thought by programmers. This kind of tests needs a different point of view, and should be done by someone else.
Don't depend on external services. Tests environment should be self-contained, and running tests should be possible without network access. This may not be possible for all situations, for example if the application is interacting with google API, we can do the assumption that the service will be available, and anyway, we can't reproduce the service on localhost. But providing local servers when possible limit dependencies to run tests, and avoid network delays.

I hope that these few advices will help you build better testing!

Django, soooo cool

2009-10-04T20:51:00.000-07:00

A log time ago, I did a small form in PHP to feed data in a database. I did create the HTML form and the database schema, wrote small functions to validate the form, all inside one php page. SQL statements, fields names and everything else was hardcoded, and it was a nightmare to test and maintain. I was feeling like a prehistoric men, who was trying to survive with rudiment tools. Well, it was the old days.

Now, I had a revelation while using Django! Don't loose your time with other crappy framework and use Django! Django contains all pieces needed for all the gory details of web development, like session management, forms, database and templating. It's so powerfull : you write your model once, Django generate sql statements for the database, generate HTML form to add or modify data, with data validation in bonus, in few lines or code. Documentation is wonderful.

There are some days like that when I really feel that technology is getting better, and Django is a wise and beautiful piece of work.

Look at www.djangoproject.com

Java and system administration

2009-09-30T07:05:00.000-07:00

Java is a wonderful platform for software development, it's mature, stable and feature-full. I had a bias against Java for many reasons in the past, as my coworkers, that lead to dismiss it a few time. Now, since I'm working with Java for Noesis, I had time to revisit this technology. Here are the bias deconstructions.

Java JVM is slow : We don't know for sure at first if the running time of a target application will be slower or faster with C++ or Java, and I don't want to dig into benchmarking. There are so many factors that may lead to a winner and the contrary. We know for sure that there is some overhead while running Java program, but for many applications, the raw output is not a primary concern. In scientific computing field, some code was not optimized and was taking a huge time to run, and optimization was leading to great performance improvement, better than a technology switch. Also, since there are large libraries available for Java, reuse reduces the development time, and it may represent a large portion of total running time. Startup time is annoying, but it occurs only the first time, and can be reduced by read ahead caching.
Java is memory hungry : java applications uses a lot of memory because they do a lot of things.
Java was proprietary : I was excluding Java because it was not open source, and then, any open source Java software had a non-free dependency. Free JVM and libraries was available, but you were on your own by doing this. Since Java JDK is now open, we are free to use it.
Java is complicated : there is some learning curve, but that's not so bad. Eclipse is helping a lot to reduce burden because of typechecking. Compiling with "ant" is so much easy compared to autotools madness! And since CDBS has support for ant, it's easy to package a Java program.
Java is huge : Installing JRE headless on a minimal ubuntu requires about 93MB of disk space. I agree that if you run only one application, it's huge. But if we were mainly running java software, this stack would be used for all applications, and also here, the reuse lowers disk requirement. But for Noesis, it's a good question to ask : do system administrator will be willing to install about one hundred MB of stuff for it? 100MB disk space costs about 1 cent today, but with backups and management time, say 5 cents. Well, I guess it would be the best investment we can do with a nickel. Still, I will have to work hard to convince system administrators to install a JRE on their Linux virtual server that takes less than few hundred MB, because it's a large proportion of the server install size.
What about embedded devices? It could be of practical interest to get Noesis running on a small device. There is the JME, but since it's stripped, I don't really know for sure if it won't break something.

It's a chance that XSugar was in Java, because it's definitely an important technology in the whole picture, and a new arrow to my quiver.

Brics projects packages

2009-09-28T08:26:00.000-07:00

New packages from brics projects are now available for Ubuntu. This is a snapshot of dependencies required for bidirectional configuration file parsing. Main packages are :

automaton : library for finite automata
grammar : library and utility for grammar validation and handling
xsugar : main program for bidirectional transformations

You can find them on launchpad :

http://launchpad.net/~francis-giraldeau/+archive/noesis

Take care, names are subject to change. Have fun!

Configuration as XML

2009-09-10T07:06:00.000-07:00

Augeas provides an XPath like interface and API to access and modify configuration files. But, there are few limitations :

Augeas is limited to regular grammar, it can't parse nested structured documents. Il did search to see if it could be possible to use regular approximations for context free grammar, but in this case it's not possible. A regular expression parser uses only a finite automata, and for general context free grammar, we need a stack to keep track of the nested level of the document.
Augeas doesn't provide a complete xml file from a configuration file, and hence, can't use all the XML libraries processing available.

We need a parser that will be able to parse a general context-free grammar. It should be easy to write grammars, and LR or LALR parsers are too hard to user, since grammar must be written to avoid ambiguities and some type of recursion. The Earley parser algorithm is able to do that.

The project XSugar is exactly what I was looking for. First, it implements a tokenless Earley parser, that has relative acceptable performances on config files. XSugar is able to do bidirectional transformation between a concrete file and an XML document and vice versa. There are few issues that must be resolved.

Bidirectional relation doesn't preserve formating of the config file. The reversability propriety is hence approximate, because a round trip will yield the same result, except for spaces and indentation. You have to keep formating manually, and this can be tedious. There is no way to verify that the stylesheet is able to capture all character of the input. Strict unidirectionality is required for config files.
Ignorable Elements, like nodes to keep spaces and indentation, has to be present in the XML file, otherwise the unparsing fail. The problem is that clients that will modify the XML will have to add formating nodes. One of the main benefit of using XML was to abstract formating, and this requirement on XML breaks this abstraction. Ignorable Elements must be optional, and when not provided, a default value should be used.
The order of elements matters in the XML. If nodes are not provided in the right order, the unparsing fail. The client has to know in which order to provide Elements, and it would be better if the client has not to worry about it.

Those are the main issues I see to make a new day for configuration management come true.

To test those concepts, I created a new project, called Noesis. It means "insight", and I thought it would be meaningful for the current project. News soon.

Augeas : state of art configuration management

2009-02-22T12:03:00.000-08:00

If you are like me, you probably find that configuration management under Linux is a real mess. Each software has it's own configuration file syntax and semantic. Since every project has it's own needs and is developed by different teams, a global and standard repository for configuration is unlikely to ever work in the open source model. We saw some initiatives that worked, like LSB and Freedesktop, but such a shift for configuration file would require a huge coordination and agreement, and is unlikely to happen, and since configuration values are usually highly coupled in software, it makes it hard to change it.

There are few ways we can address the situation. You can choose to not manage at all your config files, you can do backups, use revision management software like subversion. You can also parametrize your configuration files with variables and generate them. You can also do some grep'ing and sed'ing on your config files to change values. Everything there tends to be cumbersome and error prone. But, there is better. If it was possible to have a parser for every config file out there and get in memory representation, change whatever you want and save it back, then you have the st-graal of file configuration management. This way, you can manage configuration at a high semantic level, not manipulate file lines but configuration elements.

Guess what, Augeas aims is exactly that! The concept is simple. For each file type, you write a lens that describe the format of the file. Then, the lens can be used to parse an instance of that config file and you get a tree in memory. You can access the tree and modify it. When you're done, the lens is used again to write back the file, including any modification you made to the tree. A lens is bidirectional, you don't have to specify how to read and write a file, only one description describe both directions.

Last year, at the Linux Symposium, I listen to the talk of David Lutterkort about the progress of the project. There is one limitation of Augeas today related to the type of files for which you can write a lens. For example, we can't write lens to process config files that have recursive structures. For example, Apache configuration has this kind of nested structure. Actualy, this is not possible, because the lens semantic doesn't allow to define recursive grammar.

So, I choosed to do that for my master. When this will be done, it will be possible to manage more file types with Augeas. I will post my findings here, thoughts and ideas on the project. Stay tuned!

NFS and NBD fight

2008-04-04T12:12:00.000-07:00

The fight has started last year, when NBD replaced NFS as the default protocol for root device for thin-clients in Ubuntu. But, there was a lack of scientific data about benefits of NBD.

Few weeks ago, a team from Birzeit university started to work on the topic. They have compared boot time using NFS and NBD. Results show that a thin-client booting with NBD is 44% faster than with NFS. More testing is underway.

One big issue with NBD is that it's not as robust as NFS. For example, the client doesn't reconnect if the nbd-server is terminated. The thin-client is left in a unknown state, and must be rebooted. While this is not a big issue in small scale setup, it's not an option when you have central boot server and thousands thin-clients. The team plan to work on the availability issue as well.

Stay tuned, the final battle is starting.

Interaction design patterns

2008-03-23T21:46:00.000-07:00

I do have 26 years old, and I'm still doing homeworks for school. But this time, I admit that the topic is useful.

I read a book about patterns. You probably know object oriented design patterns. There are patterns everywhere, to save us to reinvent the wheel.

Patterns I read is about interaction design. It's about usability of electronic devices. The goals are mainly :

Design the interface as to make it familiar for users
Reduce memory load on users to let them concentrate on their main task
Reduce the time it takes to complete a task, navigate, find something
Make the device fun, easy and efficient to use

The book is written by Jenifer Tidwell. It's a really good book, it contains what we need to know to start designing any UI. I did some empiricaly previously, and I would have saved so much time by reading this book first.

Now, I'm able to evaluate an interface. A bad interface make the user dig into deeply nested dialogs, let the user waiting without a clue that something is going on, etc. There are mistakes all over the place.

There are also good design out there. And to complete my homework, I will search for UI design patterns in KDE 4. That will be pretty cool to see how much it's usable. Stay tuned.

Hello World

2008-03-22T21:42:00.000-07:00

Hey, this is my first blog on blogger.

Alone in universe. That's how I feel these days. I wonder if someone else could understand me. It's like if I was on another planet. So, in next few weeks, I will try to explain that feeling. Anyway, I'm almost sure that nobody will care about this blog, so that will be the proof that the name is perfectly appropriate.

And, BTW, that will be the occasion to share my toughts, my findings and my soul. Stay tuned.