Samuel Jacob's Web Log

2013-08-29T10:30:00.000-07:00

Self Balancing Tree as Heap

2013-05-11T11:59:00.000-07:00

In this post I will try to explain how to combine a Heap and AVL tree and get benefit of both them from a single structure.

A self balancing binary search tree such as AVL tree can do faster lookup for a item in the tree in O(log n). Heap s mainly used implement priority queues which needs to find min/max elements quickly. Heap achieve this in O(1) time complexity.

Min element of a BST is always at the left most

Lets revisit a basic property of binary search tree - In a binary search tree min element is at the left most leaf position. Similarly in a BST max element is at the right most leaf position. So finding min/max element in a BST is O(h) where h is the depth of the tree. If the BST is a balanced tree then O(h) is O(log n) in worst case(otherwise the worst case O(n), since we considering only balanced trees here lets ignore the unbalanced cases). The picture in the right illustrates this basic property of the BST.

Cached pointer to Min element at the root

The first and simplest optimization comes to mind is store a pointer to min/max elements. This caching will result in O(1) time complexity for finding min/max elements. However this would increase the cost of node insert/delete because the min/max pointer has to be updated during insert and deletion. The cost of finding and deleting a min node is O(log(n)) which is same as if we havent had the cache pointers. The picture in the right shows advantage of having cached pointer to find a min element. Obviously this method cant be used for priority queues where find min/delete operation is used together.

In the above method the problem was the complexity finding next smallest element in the tree from min element is O(log n). So if we have pointer to next smallest element from all nodes then find and delete opearation would be of complexity O(1).

Lets look at the BST from slightly different angle. Usual declaration of BST in C as follows:

When we(me and +Dilip Simha) were implementing ADT for AceOS we decided to experiment BST in a different way. We saw tree as recursive lists rather than a recursive pointers. In the following picture you could see 6 lists(not counting sub-lists):

(300, 200, 100, 50)
(300, 400, 500, 600)
(200, 250, 275)
(100, 150)
(400, 350)
(500, 450)

Now consider this list is a doubly linked circular list. This is illustrated in the following figure. You may argue that this will make the BST to become acyclic directed graph. But for the sake of simplicity lets continue to call this as balanced BST. The picture I left out few arrows to keep it cleaner.

AVL tree in Ace OS is implemented in this way. You can see the data structure declarations below. Initially we did it for reusing the code. But after implementing this we figured out some interesting properties. This balanced tree/graph can find any node in O(log(n)) and also offers findmin operation in O(1) complexity. This also reduces the complexity of delete operation(since we can find right node's left most child in O(1) operation). But delete operation might result in balancing the tree.

GCOV internals overview

2012-03-31T16:21:00.001-07:00

Sometime back I worked on a small project to extract code coverage information created by gcc from a kernel. During that time I didn't find any good internal documentation about gcov. So here I discuss about internals of GCOV. Before jumping to the internals of GCOV here is an example from the man page.

$ gcov -b tmp.c
87.50% of 8 source lines executed in file tmp.c
80.00% of 5 branches executed in file tmp.c
80.00% of 5 branches taken  at  least  once  in  file tmp.c
50.00% of 2 calls executed in file tmp.c
Creating tmp.c.gcov.
Here is a sample of a resulting tmp.c.gcov file:

      main()
      {
    1        int i, total;
    1        total = 0;
   11        for (i = 0; i < 10; i++)
branch 0 taken = 91%
branch 1 taken = 100%
branch 2 taken = 100%
   10        total += i;
   1         if (total != 45)
branch 0 taken = 100%
  ######          printf ("Failure0);
call 0 never executed
branch 1 never executed
             else
    1             printf ("Success0);
call 0 returns = 100%
    1    }

Note - gcov has a cool graphical frontend in Linux - lcov.
As shown above gcov can show what all code path executed and how many time executed.
Want to try? Here is the quick example.

$ gcc -fprofile-arcs -ftest-coverage your_program.c
$ ./a.out
$ gcov your_program.c

During compilation with -ftest-coverage option gcc generates a ".gcno" file. It contains information about each branches in your code. While finishing execution, ./a.out creates .gcda file(s) which actually contains which all branches taken. Using these there files .c(source), .gcno(block info) and .gcda(block execution count) gcov command prints the code coverage information in a human readable format.
You might wonder how your ./a.out would create .gcda while exiting. It is because of "-fprofile-arcs" automatically includes libgcov . Libgcov registers itself to be invoked during program exit by using atexit(). (Yes - it wont generate .gcda files if you exit abnormally). And during program exit it just dumps all the branch information to one or more gcda file.
The coverage information is "just" dumped into files by libgcov. So who collects the the coverage information at run time? Actually the program itself collects the coverage information. In-fact only it can collect because only it knew which all code path it takes. The code coverage information is collected at runtime on the fly. It is accomplished by having a counter for each branch. For example consider the following program.

  int if_counter = 0, else_counter = 0;

  void dump_counters()
  {
      int fd;
      fd = open(strcat(filename, ".gcda"), "w");
      write(fd, if_counter, sizeof(if_counter));
      write(fd, else_counter, sizeof(else_counter));
  }

  int main()
  {
     int a = 1;

     atexit(dump_counters);

     a = a++ + (a * --a) + a--;
     if(a) {
        if_counter++;
        printf("not zero\n");
     } else {
        else_counter++;
        printf("zero\n");
     }
  }

In the above example if you replace the colored code with gcov equivalent then green colored code is implemented inside libgcov and red colored code is implanted inside your code by gcc. It is easy to understand how the increment operation can be implanted inside your code by gcc. It just inserts "inc x-counter" machine instruction before and after every branch. It should be noted that "inc" machine specific instruction might have side effect on some programs which uses asm inside C. For example in x86 the "inc" instruction affects carry flag. Some assembly code might depends on this and if gcc inserts "inc counter" instruction then it will result in error. I had hard time figuring this out when compiled with -fprofile-arcs a kernel was booting but not able to receive any network packets(it was discarding all packets because the network stack found the checksum was wrong).

  1 int main()
  2 {
  3     int a = 1;
  4
  5     if (a) {
  6         a++;
  7     } else {
  8         a--;
  9     }
 10
 11     return a;
 12 }
 13

Here is the disassembly (gcc -g3 test.c;objdump -S -d ./a.out)

int main()
{
  4004b4:       55                      push   %rbp
  4004b5:       48 89 e5                mov    %rsp,%rbp
    int a = 1;
  4004b8:       c7 45 fc 01 00 00 00    movl   $0x1,-0x4(%rbp)

    if (a) {
  4004bf:       83 7d fc 00             cmpl   $0x0,-0x4(%rbp)
  4004c3:       74 06                   je     4004cb <main+0x17>
        a++;
  4004c5:       83 45 fc 01             addl   $0x1,-0x4(%rbp)
  4004c9:       eb 04                   jmp    4004cf <main+0x1b>
    } else {
        a--;
  4004cb:       83 6d fc 01             subl   $0x1,-0x4(%rbp)
    }

    return a;
  4004cf:       8b 45 fc                mov    -0x4(%rbp),%eax
}

After compiling with profile-arcs, the disassembly looks like

int main()
{
  400c34:       55                      push   %rbp
  400c35:       48 89 e5                mov    %rsp,%rbp
  400c38:       48 83 ec 10             sub    $0x10,%rsp
    int a = 1;
  400c3c:       c7 45 fc 01 00 00 00    movl   $0x1,-0x4(%rbp)

    if (a) {
  400c43:       83 7d fc 00             cmpl   $0x0,-0x4(%rbp)
  400c47:       74 18                   je     400c61 <main+0x2d>
        a++;
  400c49:       83 45 fc 01             addl   $0x1,-0x4(%rbp)
  400c4d:       48 8b 05 3c 25 20 00    mov    0x20253c(%rip),%rax        # 603190 <dtor_idx.6460+0x8>
  400c54:       48 83 c0 01             add    $0x1,%rax
  400c58:       48 89 05 31 25 20 00    mov    %rax,0x202531(%rip)        # 603190 <dtor_idx.6460+0x8>
  400c5f:       eb 16                   jmp    400c77 <main+0x43>
    } else {
        a--;
  400c61:       83 6d fc 01             subl   $0x1,-0x4(%rbp)
  400c65:       48 8b 05 2c 25 20 00    mov    0x20252c(%rip),%rax        # 603198 <dtor_idx.6460+0x10>
  400c6c:       48 83 c0 01             add    $0x1,%rax
  400c70:       48 89 05 21 25 20 00    mov    %rax,0x202521(%rip)        # 603198 <dtor_idx.6460+0x10>
    }

    return a;
  400c77:       8b 45 fc                mov    -0x4(%rbp),%eax
}
  400c7a:       c9                      leaveq
  400c7b:       c3                      retq

From the above disassembly it might seem putting inc instruction while compiling is easy. But how/where storage for the counters(dtor_idx.6460 and dtor_idx.6460 in above example) are created. GCC uses statically allocated memory. Dynamically allocating space is one way but it would complicate the code(memory allocation operations during init) and might slow down execution of program(defer pointer). To avoid that gcc allocates storage as a loadable section.
The compiler keep tracks of all the counters in a single file. The data structure outlined in the below picture.

There is a single gcov_info structure for a C file. And multiple gcov_fn_info and gcov_ctr_info. During program exit() these structures are dumped into the .gcda file. For a project(with multiple C files) each C file will have a gcov_info structure. These gcov_info structures should be linked together so that during exit() the program can generate .gcda file for all the C files. This is done by using constructors and destructors.

Generic C constructor: gcc generates constructors for all program. C constructors are accomplished by using ".ctors" section of ELF file. This section contains array of function pointers. This array is iterated and each function is invoked by _init()->__do_global_ctors_aux() during program start. _init() is placed ".init" section so it will be called during program initialization. A function can be declared as constructor by using function attribute.

"-ftest-coverage" creates a constructor per file. This constructor calls __gcov_init() and passes the gcov_info as argument.

samuel@ubuntu:~$objdump  -t ./a.out  | grep -i _GLOBAL__
0000000000400c7c l     F .text  0000000000000010              _GLOBAL__sub_I_65535_0_main

And disassembly of _GLOBAL__sub_I_65535_0_main

 954 0000000000400c7c <_GLOBAL__sub_I_65535_0_main>:
 955   400c7c:       55                      push   %rbp
 956   400c7d:       48 89 e5                mov    %rsp,%rbp
 957   400c80:       bf 00 31 60 00          mov    $0x603100,%edi
 958   400c85:       e8 a6 12 00 00          callq  401f30 <__gcov_init>
 959   400c8a:       5d                      pop    %rbp
 960   400c8b:       c3                      retq
 961   400c8c:       90                      nop
 962   400c8d:       90                      nop
 963   400c8e:       90                      nop
 964   400c8f:       90                      nop

gcov_init() implemented in libgcov stores all the gcov_info() passed in a linked list. This linked list is used to walk through all the gcov_info during program termination.

Graph your data

2012-02-27T19:27:00.000-08:00

System statistics are hard interpolate since usually they are collected in large quantities and sometimes represents large numbers. Recently I was doing a prototype and wanted to measure how much damage it would to the main project (in terms of performance); so used performance counter feature in the processor to measure some events(cache miss, memory read etc) with and without my code change. But after looking at the numbers I realized it is difficult to analyze such a data. Because each number is 8 digit and I had 16 columns(16 cpu) and 100 rows of data(100 seconds of run). So I decided to use some graph so that it would be easy to understand the data.
Googled for a GNU graph tool and found gnu plot - this blog is to show how good it is and how easy it is to use. Consider using it if you have lot of numbers. For this post I took some sample data from my ubuntu machine while running stress command.(stress --cpu 8 --io 4 --vm 2 --vm-bytes 128M --hdd 2 --timeout 200s)

#sudo vmstat -n 1 200 > stat.txt
#cat stat.txt
procs -----------memory---------- ---swap-- -----io---- -system-- ----cpu----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa
 0  0 251124 1827388   4720  32704    6   34    19    38   42   74  1  0 98  1
 0  0 251124 1827388   4720  32708    0    0     0     0  104   71  0  0 100  0
13  3 251108 1349912   4728 322540    4    0     4    20  683 1789 42 12 47  0
11  3 251008 1382620   4728 322520  180    0   180     0 1604 1233 89 12  0  0
11  3 251008 1432052   4728 322520    0    0     0     0 1361 1237 90 10  0  0
11  3 251008 1298352   4728 322668    0    0     0     0 1392 1275 90 10  0  0
 2  3 251008 1512576   4728 323524    0    0     0     0 20077 14827 59 16 13 12
 0  0 251008 1826388   4728  32756    0    0     0     0 45069 25566  0  4 25 71
 0  0 251008 1826444   4728  32708    0    0     0     0   59   46  0  0 100  0
...

The following example shows how to create line graph for us,sy columns in the above against time(seconds).

This graph might not be impressive because it deals with only numbers ranging from 0-100 and the numbers are very steady. Consider a range 0-99999999 and the numbers are fluctuating too much then it will be to graph. The above graph was created by running "gnuplot" with following commands

set title 'CPU usage'
#set terminal svg butt enhanced dynamic
set terminal jpeg
set output 'output.jpg'
set xlabel 'seconds'
#set logscale y
set ylabel 'cpu'
set key below
plot \
    "stat.txt" using :13 title 'Application' with lines lc rgb 'blue', \
    "stat.txt" using :14 title 'Kernel' with lines lc rgb 'green'

You can also intermix two or more datafiles. The following example shows how to graph two different samples collected during different time period.

set title 'CPU usage'
#set terminal svg butt enhanced dynamic
set terminal jpeg
set output 'output.jpg'
set xlabel 'seconds'
#set logscale y
set ylabel 'cpu'
set key below
plot \
    "stat.txt" using :13 title 'Application' with lines lc rgb 'light-green', \
    "stat.txt" using :14 title 'Kernel' with lines lc rgb 'light-red', \
    "stat1.txt" using :13 title 'Application1' with lines lc rgb 'dark-green', \
    "stat1.txt" using :14 title 'Kernel1' with lines lc rgb 'dark-red'

The stat1.txt file is generated by running vmstat while the system was stressed by stress --cpu 4 --io 2 --vm 4 --vm-bytes 1M --hdd 2 --hdd-bytes 4096 --timeout 200s

The nice thing about gnuplot is it will skip the row(line) in the data file if it cant recognize the columns. And also it supports svg and pdf outputs. See what all gnuplot can do at the official demo page.

OpenOCD and NGX USB ARM JTAG

2011-05-22T06:04:00.002-07:00

This post describes the steps needed to make NGX’s USB ARM JTAG to work with OpenOCD in windows 7. This JTAG is compatible with colink JTAG and works with IAR Workbench and Keil uVision. To use with these IDEs there is a well defined methods/plug-ins available in the product page and in internet. However to use this JTAG with OpenOCD there is scarce resource in the internet.

OpenOCD can be used to low level debugging, source level debugging (through GDB) and can be used for flashing. OpenOCD exposes a command line interface which can be accessed through telnet. It also provides remote GDB server which also can be reached through TCP connection.

Steps needed for Windows:

1) Plug-In the JTAG to a available USB connector

2) Download libusb-win32 from http://sourceforge.net/projects/libusb-win32/files/

3) Extract libusb-win32 to a folder and run “inf-wizard.exe”

4) Select “USB Serial Converter A” and install driver

5) Download and install openocd from http://www.freddiechopin.info/index.php/en/download/category/4-openocd

6) Attach the JTAG probe to your target ARM board and poweron the target board

7) Create a openocd configurations file (see at the end)

8) Run openocd.exe –f

9) Run putty or telnet and connect to port localhost:4444

After this the target board will respond to JTAG commands which can be issued through the telnet session.

For GDB debugging, you need a cross compiled GDB which can be downloaded from http://www.codesourcery.com/sgpp/lite/arm/portal/subscription?@template=lite.

After launching arm-none-eabi-gdb.exe run "target remote localhost:3333" to start remote debugging. You can execute low level JTAG commands from GDB by using "monitor " command.

Flashing can be done using the following commands:

reset
halt
sleep 200
wait_halt
flash probe 0
flash info 0
flash write_image erase unlock
sleep 200
reset run

Open OCD configuration file:

# openocd configurations
telnet_port 4444

# gdb configuration
gdb_port 3333

# cpu configuration
source [find target/lpc1768.cfg]

# interface configuration
interface ft2232
ft2232_vid_pid 0x0403 0x6010
ft2232_device_desc "NGX JTAG"
ft2232_layout "oocdlink"
ft2232_latency 2

Wirless Router, Network Storage and Media Server: Software Pieces

2011-03-12T07:43:00.004-08:00

This is the followup post of Router/Network Storage Server. Here I document about the different software used to make my RCN. Here is the different pieces needed.

Operating System
Router
Storage
Media Server

Operating System
There are two open source choices BSD (FreeBSD) or Linux(ubuntu). After few days of analysis I decided to go with Linux - because in my work I use FreeBSD. In either case I didnt want to use FreeNAS or OpenFiler or anyother ready made distro. Since I am familiar with Ubuntu - I decided to use it - the Ubuntu server version.

File System
Wanted to use ZFS on my main storage disk but it is not available on Linux yet, so decided to go with XFS. EXT3/4 on the boot disk because it is natively supported and no extra package needed. The boot media is 8GB flash disk.

Installation
Since there is no optical disk, installation should be through network or USB. Since most of the Linux distributions supports that I decided to use USB.

Download ubuntu 10.10 server
Download universal USB installer
Create bootable install media using the installer
Boot the system with boot media - My dual port monitor and wireless keyboards came handy in this situation because I could switch between Windows and Linux installation.

Partitions
Although no data is going to be stored in the boot media, it would be good to have separate partitions to store the config files and home directory. Otherwise re-installation would wipe out all the data.

I chose to create 5 partitions

/ - EXT4 - 2GB
/usr - EXT4 - 2GB
/var - EXT4 - 2GB
/home - EXT4 - 1GB
swap - - 1GB

Administration

Since this device will run without any Monitor and Keyboard only way to communicate with the system is through network interface. Having SSH access is good but still having a web interface for common administration access is better. Few Linux applications are available for that my choice is Webmin.

How to install webmin on Ubuntu

sudo vi /etc/apt/sources.list
wget http://www.webmin.com/jcameron-key.asc
sudo apt-key add jcameron-key.asc
sudo apt-get update
sudo apt-get install webmin

After this the machine can be controlled from local network - https://hostname:10000/

Shutdown

Shutting down the system should be easy. Since the storage is connected to the system it cant be power off directly. The file system data should be syncd first. Using command line or web interface is not realistic. So programming the ATX power switch is the only way - acpid does that.

sudo apt-get install acpid

Storage

The goal was to create file based storage which is accessible from my home network. The NAS server should be big enough for atleast next 2 years. It should be fast enough to view videos from it without flickering. It should have hardware fault tolerance. It should have a back up facility.

Space: 1TB is big enough for me.

Speed: Each disk has 64MB cache on board which is sufficient to buffer the read/write operations. RAID 1 can fasten read operations by queuing it on different disks(write it cant.Yet to check how Linux implements this.)

Backup: cron job to write create compressed tars on external disks? Need to explore other better software availability.

Fault Tollernce: RAID (Redundant arrays of inexpensive disks)

Although few of my desktop boards had RAID option in the BIOS menu, I never used it and never explored it.I thought RAID chipsets in a motherboard is equivalent to RAID controllers/adapters. It was one of the decideding factor I favoured for Gigabyte(GA-D425TUD) motherboard with JMicron RAID chipset over Intel(D525MO) motherboard.

After configuring RAID in the BIOS and starting Linux I realized it is not true raid. Because Linux recognized as fakeraid. In simple terms fakeraid is a firmware based RAID. That is all the work is still to be done in software yielding no performance benefit. Advantage of fakeraid is multiple OS which runs on same box can utiltize the same RAID. Since my setup wont have multiboot option, I dont want the fakeraid so decided to go with pure software RAID 0.

Create software raid using multiple devices(md) interface.
mdadm --create --verbose /dev/md0 --level=1 --raid-devices=2 /dev/sda /dev/sdb
The above command will take some time (around 6 hours) because it needs to sync the contents of both disks. While it is doing that the status can be checked by using the following command
cat /proc/mdstat
Then create a XFS file system on the md device
mkfs.xfs /dev/md0
Store the configuration
mdadm --detail --scan > /etc/mdadm/mdadm.conf
Create mount point and add the mount information in the /etc/fstab
mkdir /mnt/raid
echo "/dev/md0 /mnt/raid xfs defaults 1 2" >> /etc/fstab

After this /mnt/raid can be made accessible to remote machines through either NFS or through Windows File Sharing. For Windows File Sharing samba service needed to installed

sudo apt-get install samba

Use webmin to configure samba “Servers”->”Samba File sharing”. Add the storage mount point here.

Router

The routing functionality is very simple - handle all 3 interfaces with some limitations.

First interface eth0 is a Gigabit ethernet interface which is directly connected to the a desktop computer.
Second interface eth1 is a Fast ethernet interface which is directly connected to internet(connected to a ADSL modem).
Third interface is 802.11n wireless network.

Network and IP

All interfaces are in different networks. All interface should get static interface while booting up. This router should provide dynamic IP to the other machines.

Modify /etc/network/interface

# This file describes the network interfaces available on your system
# and how to activate them. For more information, see interfaces(5).

# The loopback network interface
auto lo
iface lo inet loopback

# The primary network interface
auto eth0
iface eth0 inet static
address 192.168.1.2
netmask 255.255.255.0
gateway 192.168.100.2
post-up iptables-restore < /etc/iptables.up.rules
up /etc/init.d/dhcp3-server start

#wireless network
auto wlan0
iface wlan0 inet static
address 192.168.2.1
netmask 255.255.255.0
gateway 192.168.100.2
up /etc/init.d/dhcp3-server start

#wan interface
auto eth1
iface eth1 inet static
address 192.168.100.2
netmask 255.255.255.0
gateway 192.168.100.1

Modify /etc/dhcp3/dhcpd.conf

subnet 192.168.1.0 netmask 255.255.255.0 {
range 192.168.1.100 192.168.1.200;
option domain-name-servers 208.67.222.222, 208.67.220.220;
option routers 192.168.1.2;
option broadcast-address 192.168.1.255;
default-lease-time 600;
max-lease-time 7200;
}
subnet 192.168.2.0 netmask 255.255.255.0 {
range 192.168.2.100 192.168.2.200;
option domain-name-servers 208.67.222.222, 208.67.220.220;
option routers 192.168.2.1;
option broadcast-address 192.168.2.255;
default-lease-time 600;
max-lease-time 7200;
}

Finally enable forwarding in Linux kernel by setting the system tunable "/proc/sys/net/ipv4/ip_forward" to 1

echo 1 > /proc/sys/net/ipv4/ip_forward

To set it during boot set it in /etc/sysctl.conf

Still few work is pending to make the desktop to connect to network - NAT and Firewall.

NAT - Network Address Translation
NAT is required on eth1 to translate addresses on any outgoing packets and incoming packets.

INTIF="eth0"
EXTIF="eth1"

#set default polices and flush
iptables -P INPUT ACCEPT
iptables -F INPUT
iptables -P OUTPUT ACCEPT
iptables -F OUTPUT
iptables -P FORWARD DROP
iptables -F FORWARD
#setup NAT
iptables -t nat -F
iptables -t nat -A POSTROUTING -o $EXTIF -j MASQUERADE

iptables -A FORWARD -i $EXTIF -o $INTIF -m state --state ESTABLISHED,RELATED -j ACCEPT
iptables -A FORWARD -i $INTIF -o $EXTIF -j ACCEPT

INTIF1="wlan0"
iptables -A FORWARD -i $EXTIF -o $INTIF1 -m state --state ESTABLISHED,RELATED -j ACCEPT
iptables -A FORWARD -i $INTIF1 -o $EXTIF -j ACCEPT

iptables -A FORWARD -i $INTIF -o $INTIF1 -j ACCEPT
iptables -A FORWARD -i $INTIF1 -o $INTIF -j ACCEPT

#unblock certain services
#webmin
iptables -A INPUT -p tcp -m tcp --dport 10000 -j ACCEPT

Wireless
Now it is time to setup the wireless interface. Assuming the wireless are drivers are present in the kernel. The other tool requied is hostapd. hostapd implements IEEE 802.11 access point management.

interface=wlan0
driver=nl80211

ctrl_interface=/var/run/hostapd
ctrl_interface_group=0

ssid=rcnap
hw_mode=g
channel=11

ieee80211n=1
#ht_capab=[HT40-][SHORT-GI-40]

wpa_pairwise=TKIP CCMP
wpa=1

Media Servers
Yet to be filled

Download Manager
Yet to be filled

How to create your own wireless router, network storage server and media server

2011-02-14T07:20:00.000-08:00

I have replaced my Buffalo WRT-G54 wireless router with my own custom built router. This blog explains how I did that. I call this device as RCN (Router cum NAS).

To create your own RCN, you need:

Hardware
Software
Motivation

Motivation for me was

Storage - I was afraid of storing all my family photos/videos in a single drive. I wanted to have RAID 1 setup.
Power Saving - I hate running my i5 24x7 to download stuffs.
Media server – I want to get rid of copying photos/videos/movies on my Play Station 3 before watching it – it spoils the mood.
Exploration - Fun building new thing.

The above list is in reverted priority order.

Hardware
I began my hardware hunt 45 days back – it was difficult because of my requirements and availability in Indian Market.

Here is the initial requirement list (strikethrough indicates I gave up that requirement because the items are too costly or not available in India):

Total board TDP should be less than 40watts
~~Passively cooled~~
Mini-ITX form factor
Onboard RAID is preferred
DDR3 support is preferred
~~Dual core~~
Hardware should be available in India
~~Should be less than Rs.10K~~

Here is the final products I purchased:

Gigabyte GA-D425TUD
iBall Baby 306 Cabinet
DDR-3 2GB RAM
2 x 1TB Western Digital WD10EARS SATA
USB to Ethernet
USB Flash Drive
PCI Wifi Adapter DLink 552 Xtreme N

Here is some pictures of my RCN (Ignore the fancy cabling)

Mini-ITX board - I didnt expect this board to be so small - Compare it with the building set block

I got two noisy fans with this cabinet - I yet to shutdown and close the holes

After Attaching the Wireless PCI card

Interesting fact about WD10EARS is it use 4KB sectors instead of the conventional 512byte sectors. Since this is a breakthrough software support is not much there. Looks like these drives perform poor if not partitioned properly - Since my requirement demands creating single partition, I purchased this drive and it performs well.

Will post the software things needed in the next post...

USB image creation using dd command

2011-02-09T02:22:00.002-08:00

Wrote this post while waiting for a "dd" command to finish USB image creation. So this post is mainly for dd tips.

1) How to create a USB drive clone?

sudo dd of=/dev/xxx if=clone.img

The output image will be in clone.img. If you want to restore to the original disk or another usb drive use sudo dd if=/dev/xxx of=clone.img

2) How to find where my usb drive is attached?

dmesg | less

This will tell which device name is attached to the usb drive.

3) How long will it take for a 4GB drive?

Depends on your usb drive transfer rate.

But also depends on the buffer size used by dd, I use

sudo dd of=/dev/xxx if=clone.img bs=10M

sudo dd if=/dev/xxx of=clone.img bs=10M

iostat will give you the transfer rate of your devices

4) Dont know whether dd is dead or not?

If you send USR1 signal to dd it will print the status.
sudo kill -USR1 `pidof dd`

If you want auto update every 10 sec, try

watch -n 10 sudo kill -USR1 `pidof dd`

PS3 File Conversion(mkv to vob)

2010-12-21T07:20:00.005-08:00

PlayStation 3 supports lot of file formats. However PS3 doesnt play most famous HD files container mkv. Another limitation of PS3 is it doesn't support any file system except FAT32. And FAT32 has limitation of 4GB file size. And most of the HD files will easily cross 4GB limit.

I used to watch HD movies on my PS3 since it is connected to TV and HT; and other movies(which doesnt require special video/audio effects) on my desktop computer.

So to watch movie in mkv format on PS3, it should be converted to PS3 compatible format(VOB) and the output file(s) size should be less than 4GB. For this I have been using mkv2vob, this tool transcodes DTS to AC3(if necessary) otherwise just copies video/audio streams to output file which in vob format. It also does good job by splitting the files so that a single file is always <>

Recently this tool was not able to convert a mkv file, so I have to try different tools. The first tool I tried was media coder; after few trial and errors I was able to convert mkv to vob. However it doesnt have provision for splitting the file. So I went through few forums to find GOTSent. It did the job but took lot of time(~15-20min) than mkv2vob.

After all this, I started watching that movie and realized that particular doesn't have any special effects(audio/video) but needs subtitles; instead of transcoding it again - I just watched it in my computer. Either I should lay cable between my router and PS3 so that PS3 Media Server or I should develop a wireless router which can communicate at 1G speed. I feel the later more interesting :)

mount: Invalid Argument

2010-12-10T10:03:00.002-08:00

This post regarding a simple problem which took almost 10 hours to realize my mistake.

I am working on PowerPC FreeBSD system where no harddisk is attached instead USB flash drive is used as storage. I needed to edit file system layout and content extensively. So I took the USB flash drive from the that machine and came back to my desk. Time 3PM.

1) Inserted into my Linux desktop and did "dmesg" - the kernel was able to detect the usb drive and print the partitions inside it. But when I tried mount it failed. After some googling I found that UFS file system can be mounted in Linux only in RO mode. So I tried mount -r but still it failed.

2) So I tried Windows next, by googling UFS driver/utility for windows. The free one I could find which has write access it ffsdrv. I avoid posting its link because it is not helpful and I wont recommend that utility to anyone. Since it has file system driver it can easily crash the windows. It showed me BSOD three times to me.

3) Then I decided to try mounting the USB on a FreeBSD machine. I couldnt find one, so I decided to use VirtualBox. Since I already had virtual box installed and FreeBSD vm in it, it was easier to "start". I started the FreeBSD vm but it couldnt detect the host USB device. So searched and found that when I installed I should have omitted the VirtualBox usb driver which is causing the issue, so downloaded the latest version of VirtualBox. After installing VirtualBox also it couldnt detect the USB drive. Few googling revealed there is a bug in VirtualBox implementation of USB EHCI controller 2, so I unselected it and VirtualBox is able to detect my drive. But when I tried to mount the drive, FreeBSD failed with "Invalid Argument".

4) At this time I lost hope with VirtualBox, so I installed Vmware and started FreeBSD on it. There were no glitches, the drive got detected immediately and FreeBSD was able to detect it too. However when it came to mount, again same problem. Ahhh

5) Ok - this is time to blame emulators - I thought both VirtualBox's and VMware's USB simulation is bad :), so I decided to try with real hardware. Since it was late around 8PM, I went to home - I booted my machine with a FreeBSD Live CD and tried to mount - same problem.

6) Now I started suspecting the drive/data. I ran fsck - it complaint it couldnt find super block and alternative super block. newfs -N said the alternative should be at 32. So I tried fsck_ffs -b 32 and no luck.

7) Time 11.xxPM, bulb:> "you are using i386(Little Endian) machine to read file system which was created by powerpc(Big Endian).

Eva

2010-07-31T02:55:00.002-07:00

I have created a small utility which can evaluate "C" expressions and print it in Hex/Binary formats. The name of the project is Eva.

The core part - Parser is created using ANTLR. Actually the parser part contains 3 modules - Lexer, Parser and Tree walker. The GUI part is developed using WxWidgets.

Since it is a small project, I decided to post it in google code hosting rather than sourceforge. Here is the link to the project - http://code.google.com/p/eva-c/

Kernel(FreeBSD) Concurrency

2010-02-10T03:17:00.002-08:00

Today, I had to revisit how FreeBSD system call path was synchronized. And here it is:

Kernel data structures are tradionally protected by the following synchronization methods.

Interrupt disabling
Spinlock
System priority level
Mutex

Disabling interrupts is the easiest method because only one code path can be executed with in a interrupt disbale/enable boundary. However exceptions are there which dont honour interrupts disabled attribute.

Eg:

Exceptions
Faults
NMI

Disabling interrupts wont work on SMP because interrupts can be disabled/enabled only on current CPU. Disabling interrupts is problematic if the code path takes longer time to complete. Because the kernel would have lost interrupts from devices.

Spinlocks is a datastructure residing on memory and acceissible from all the processors on the system. Before entering a critical code path spinlock is taken and all other access to that code path is prohibted and the other cpus will be in a loop trying to get the lock and enter. There are certain rules while creating a spinlock to avoid dead locks and gain performance from SMP.

Locking order heierarchy should be maintained to avoid dead locks.
Fine grained locks instead of single big lock to gain performance on SMP.

Spinlock alone would cause a dead lock in a preemptive kernel. Avoiding this in easy way is disabling interrupt because scheduler wont run. However it again would introduce a problem of losing interrupts.

system priority level or SPL is the prefered method to use with spinlock to avoid lock issues and also get interrupts from devices. SPL rules:

And all spinlocks are at greater SPL than scheduler.
All spinlocks should have a associated SPL and at that or greater SPL level only the spinlock should be taken.

Note:

In simpler term spl is equivalent to masking interrupts.
SPL is per processor, so the spinlock should have locking order hierarchy, otherwise deadlock for sure.

Mutexes used because even with fine grained spinlock there is performance penalty when other CPUs are waiting(looping) for a spinlock. Mutex solves this problem by scheduling out the looping threads in the other CPUs and selecting other threads to run.

Note:

Mutex cant be used in certain situations eg: a interrupt handler which runs without context cant take mutex because it might be put into sleep.
Combining mutex and spinlock requires only one condition - after a spinlock is taken no mutex acquire should be attempted.

FreeBSD 6.x uses mutex and spinlock - MUTEX_DEF and MUTEX_SPIN.

MUTEX_DEF - Is a mutex which result in going to sleep.

MUTEX_SPIN - Is a spinlock which never puts the caller into sleep but spins and also disables interrupts.

When FreeBSD was optimized for SMP, spinlocks were removed and mutex was introduced.

It also introduced context full interrupt handlers; now interrupt handlers can sleep, so can use mutex. Since most of the system calls was not ported to SMP, they were protected using a big mutex called Giant.

Giant - Gaint is a MUTEX_DEF which protects the code path of most system calls.

Size of all structures in your program

2009-11-19T02:58:00.003-08:00

There are some cases when you want to find size of all structures in your program/project. For a given program it is easy because we can manually calculate or put a printf sizeof() to calculate a few structures. But for a project with few hundred files it is difficult. There is noway AFAIK in gcc to dump all the structure sizes while it compiles.

Here is a way todo it using dwarf debugging info if you are using gnu compiler tools. Compile your project output file with -g option, this will generate debugging information in your program. Then run objdump to dump the debug info. This debugging information contains all the information about your program, filter the output for "DW_TAG_structure_type" and you will get only structure information.

Here is how I did it:

objdump -W kernel.debug.reloc > debug.info

grep -e "DW_TAG_structure_type" debug.info --after-context=5 --mmap > structs.txt

SLOC

2009-10-29T09:21:00.005-07:00

Recently I was browsing some open source project's(as usual I forgot the name) web site and the author has put SLOC report for his project. It was pretty cool. I wanted to try it on some of my projects and tried sloccount(http://www.dwheeler.com/sloccount/) in my office but since my office PC doesnt have my personal project sources I was not able to get SLOC report for my projects.

Today I suddenly, I remembered about SLOC and tried it on my Ace project. And here is the output

Sam@samxp /cygdrive/e/Projects
$ sloccount ace_test/src
Creating filelist for app
Creating filelist for drivers
Creating filelist for include
Creating filelist for kernel
Creating filelist for lib
Have a non-directory at the top, so creating directory top_dir
Adding /cygdrive/e/Projects/ace_test/src/wscript to top_dir
Categorizing files.
Finding a working MD5 command....
Found a working MD5 command.
Computing results.

SLOC Directory SLOC-by-Language (Sorted)
13716 include ansic=13699,sh=17
9045 kernel ansic=8810,asm=221,python=14
3712 lib ansic=3691,sh=11,python=10
1062 drivers ansic=1051,python=11
41 top_dir python=41
10 app ansic=6,python=4

Totals grouped by language (dominant language first):
ansic: 27257 (98.81%)
asm: 221 (0.80%)
python: 80 (0.29%)
sh: 28 (0.10%)

Total Physical Source Lines of Code (SLOC) = 27,586
Development Effort Estimate, Person-Years (Person-Months) = 6.51 (78.15)
(Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months) = 1.09 (13.10)
(Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule) = 5.97
Total Estimated Cost to Develop = $ 879,761
(average salary = $56,286/year, overhead = 2.40).
SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
redistribute it under certain conditions as specified by the GNU GPL license;
see the documentation for details.
Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."

Pretty cool isnt it? :)

Funny numbers

2009-10-27T02:01:00.002-07:00

Freebsd kernel source files count vs Makefile count. Just from the numbers it looks like for every 4 source files there is an Makefile. I ran these commands when I thought of converting FreeBSD build system(make) to use waf(http://code.google.com/p/waf/) or scons(http://www.scons.org/).

root@freebsd-sam:/sys#find . -name "*.c" | wc -l

3171

root@freebsd-sam:/sys#find . -name "*.h" | wc -l

3004

root@freebsd-sam:/sys#find . -name "*.s" | wc -l

root@freebsd-sam:/sys#find . -name "Makefile*" | wc -l

746

And yes, after seeing this number I let me thought to stay inside for sometime.

Call Trace without modifying the source

2009-10-03T13:04:00.005-07:00

While investigating about gcc flag "-fprofile-arcs", I came to know about a new(to me) gcc flag and this blog entry is about it. For any large C project it is hard to learn/find call graph through code walk. From C prospective unless otherwise you put a printf in each function entry/exit it is hard to find the call trace.

GCC and ICC has a wonderful option "-finstrument-functions" to solve this. This option instructs the compiler to emit instructions to call a external function on each function's entry/exit. Defining these two functions like the following and adding the above option -finstrument-function to your makefile will do the magic.

void noinstrument __cyg_profile_func_enter(void *this_fn, void *call_site)
{
printf("%p called from %p\n", this_fn, call_site);
}

void noinstrument __cyg_profile_func_exit(void *this_fn, void *call_site)
{
printf("%p returns\n", this_fn);
}

Of course, you can do anything in these functions, for simplicity sake I just defined them as printfs.

Tracing ld

2009-09-03T22:30:00.002-07:00

I was trying to do something with customized FreeBSD kernel which required constructors(.ctors) and destructor(.dtors) sections to be included in the final binary. So I used the normal gnu practice of including the following code into my linker script(/sys/conf/ldscript.i386).

.data.gcov :
{
__CTOR_LIST__ = .;
LONG((__CTOR_END__ - __CTOR_LIST__) /
(__CTOR_LIST2__ - __CTOR_LIST__) - 2 )
__CTOR_LIST2__ = .;
KEEP(*(.ctors))
LONG(0)
__CTOR_END__ = .;
__DTOR_LIST__ = .;
LONG(( __DTOR_END__ - __DTOR_LIST__ )/
(__CTOR_LIST2__ - __CTOR_LIST__) - 2)
KEEP(*(.dtors))
LONG(0)
__DTOR_END__ = .;
}

But when I tried to see the contents of of the linked kernel there were no constructors. Because

__CTOR_LIST__ and __CTOR_END__ are placed next to each other, from the linker script you can see the .ctors comes in between them.

$objdump -t kernel | grep __CTOR
c049cb8c g .data.gcov 00000000 __CTOR_LIST__
c049cb94 g .data.gcov 00000000 __CTOR_END__
c049cb90 g .data.gcov 00000000 __CTOR_LIST2__

$objdump -s -j .data.gcov kernel | head

kernel: file format elf32-i386-freebsd

Contents of section .data.gcov:
c049cb8c 00000000 00000000 00000000 00000000 ................
c049cb9c 5f090000 e7124ac0 e7124ac0 1b4a4ac0 _.....J...J..JJ.
c049cbac 1b4a4ac0 085c4ac0 085c4ac0 06234bc0 .JJ..\J..\J..#K.
c049cbbc 06234bc0 1f374bc0 1f374bc0 d43b4bc0 .#K..7K..7K..;K.
c049cbcc d43b4bc0 b1414bc0 b1414bc0 b2494bc0 .;K..AK..AK..IK.
c049cbdc b2494bc0 d77b4bc0 d77b4bc0 0e894bc0 .IK..{K..{K...K.

I tried to find what ld is doing by enabling --verbose option in SYSTEM_LD (/sys/conf/kern.pre.mk) but it did not help. Then I tried -Map option to ask ld to generate map file and it helped me.

In my environment the kernel is generated in step. First all system objects are partially linked(-r/-Ur option) to generate relocatable kernel. Then this relocatable kernel is linked with some other static modules to create the kernel. From the map files I could see the constructors are present in the relocatable kernel and dropped while creating the proper kernel. I guess it is a bug with ld. So I merged the two step process into one and it worked.

$objdump -t kernel | grep __CTOR
c049cf50 g .data.gcov 00000000 __CTOR_LIST__
c049f4e4 g .data.gcov 00000000 __CTOR_END__
c049cf54 g .data.gcov 00000000 __CTOR_LIST2__

$objdump -s -j .data.gcov kernel | head

kernel: file format elf32-i386-freebsd

Contents of section .data.gcov:
c049cf50 63090000 a7164ac0 a7164ac0 db4d4ac0 c.....J...J..MJ.
c049cf60 db4d4ac0 c85f4ac0 c85f4ac0 c6264bc0 .MJ.._J.._J..&K.
c049cf70 c6264bc0 df3a4bc0 df3a4bc0 943f4bc0 .&K..:K..:K..?K.
c049cf80 943f4bc0 71454bc0 71454bc0 724d4bc0 .?K.qEK.qEK.rMK.
c049cf90 724d4bc0 977f4bc0 977f4bc0 ce8c4bc0 rMK...K...K...K.
c049cfa0 ce8c4bc0 bbf74bc0 bbf74bc0 bb0a4cc0 ..K...K...K...L.

Debugging gcc behavior

2009-08-28T02:23:00.004-07:00

While compiling a FreeBSD kernel I encountered the following error message from GNU assembler

Error: suffix or operands invalid for `mov'

I was not sure whether the error is because of my changes are not. But still I have to debug the problem and solve it, so I decided to find what is wrong with the mov instruction. But since gcc created a temporary file and invoked as to assemble it, I couldn’t find the temp file anymore.

Googled and find the following gcc options to find what gcc does.

gcc –v is verbose mode, which prints all the action/scripts gcc is doing.
gcc -### similar to –v but wont execute any commands.
gcc –save-temps saves all the temporary files generated by the gcc. Useful if you want to see the assembly output passed to gnu assembler.
gcc –E Just preprocess the c file
gcc –S generate assembly file.

With gcc –v –save-temps, I got the temporary assembler file used by assembler. Since reading machine generated assembly file is difficult, I tried to find the C source code corresponding to the error. From nearest .file assembler directive I found the C file name and from the .loc directive I found the line number. And the following was the inline assembly in the C file.

__asm __volatile("movl %%ss,%0" : "=rm" (sel));

Was surprised what is wrong with this and why my assembler giving error. Googled again and found this link - http://kerneltrap.org/node/5785. It seems newer gnu assembler(>=2.16) wont support long read/write operations(mov) on segment registers(ds,ss...). So changed the above source to movw %%ss, %o and it compiled perfectly. :)

Unreferenced symbols - EXPORT_SYMBOL

2009-04-09T04:22:00.005-07:00

I wrote ACPI driver for Ace and try to load it into kernel. It was failing with the error message symbol not found.

The log file content says AcpiGetName was not found.

$ cat log.txt
Driver for id acpi : acpi.sys
../src/kernel/pm/elf.c:343:FindElfSymbolByName(): Symbol not found AcpiGetName(c01a2148:1869) string table c01aa619

After exploring the Acpi-CA source code and Ace kernel code, I couldn’t figure out why the symbol is missing. Then I tried to dump the symbol table for Acpi library and kernel.sys.

$ nm build/default/src/kernel/libacpi.a | grep GetName
U AcpiExGetNameString
000001e3 T AcpiExGetNameString
000001b7 T AcpiPsGetName
000000f4 T AcpiGetName
$ nm build/default/src/kernel/kernel.sys | grep GetName
c0135163 T AcpiExGetNameString
c0137bfb T AcpiPsGetName

It is obvious during kernel link process some how the linker is losing AcpiGetName. Within few seconds I realized that the linker is doing optimization on the output to remove unreferenced sections. So I googled for how to avoid this and found --no-gc-sections is the ld option to do it. However even after giving this option to linker to was removing the unreferenced symbols; I kept on trying to find a solution for making the linker to include unreferenced symbols in the output… I didn’t find the solution.

Then I started thinking how linux kernel is avoiding this problem and I it flashed seeing EXPORT_SYMBOL kind of macro in some source. So I googled for it and got the answer – use the symbol in storage, so that it will be referenced, so that linker will include it in the output.

struct kernel_symbol
{
unsigned long symbol;
char * name;
};
#ifndef MODULE_SYMBOL_PREFIX
#define MODULE_SYMBOL_PREFIX ""
#endif
#define __EXPORT_SYMBOL(sym, sec) \
static const char __kstrtab_##sym[] \
__attribute__((section("__ksymtab_strings"))) \
= MODULE_SYMBOL_PREFIX#sym; \
static const struct kernel_symbol __ksymtab_##sym \
__attribute__((section("__ksymtab" sec), unused)) \
= { (unsigned long)&sym, __kstrtab_##sym }
#define EXPORT_SYMBOL(sym) \
__EXPORT_SYMBOL(sym, "")

Better build system

2009-03-17T03:54:00.003-07:00

I was using “make”(http://en.wikipedia.org/wiki/GNU_build_system) to build and clean my projects. The makefiles grew bigger enough to not maintainable state. Recently I came to know about waf(http://code.google.com/p/waf/) from a forum, so decided to give a try. I went through the waf documentation and it took 2 hours to understand how it works and it took 2 days to convert all my makefiles to waf wscripts and wscript_build files.

The basic problem with make was I have write rules to how to build object files from source and

then to clean I have to write how to delete the object files. With waf the problem is simplified, you have to tell what all source files and it will take care of how to compile and link. It will also take care of how to clean the project and the dependency between files are also taken care, so no need for gcc –M and dependency files etc. The feature I liked in waf is it has colored output with progress bar :)

The other problem solved in Ace project compilation was build configuration. Waf will configure the project for the first time, so it solved the different cross compiler required for Ace OS.

Waf(http://code.google.com/p/waf/) is really good alternative/replacement for make tools.

Putty Tips

2008-12-15T22:47:00.005-08:00

Putty title

I wanted to change putty title to reflect current working directory of the remote machine to distinguish multiple putty windows easily.

PUTTY_TITLE=`hostname`:`tty | cut -f 4 -d "/"`

export PS1='$PWD>^[]2;$PWD:$PUTTY_TITLE^G'

To insert in vi editor the "^[" character in insert mode press control-V and then the Escape key. ^G is created by pressing control-G.

Reference: http://www.unix.com/sun-solaris/23038-change-terminal-title-2.html

Passwordless connection to HPUX machines

Since I was forgetting my passwords for HPUX machines, I decided to try SSH public/private key authentication to get rid of passwords. After some struggle I managed to login in to HPUX machines using Putty without entering a password.

Before I forget all those steps which are not part of my daily job, I wanted to log them and so here it is.

Login to HPUX machine using your login and password
Create a .ssh directory under your home directory mkdir .ssh
Create public/private key pair ssh-keygen –t rsa
Add the public key to authorized_keys2 file cat id_rsa.pub>> authorized_keys2
Now ftp the private key file(id_rsa) to your Windows machine.
Covert the private key file format to putty private key file format. (Use puttygen.exe and then load and save the private key file).
Now in putty, select the host and select SSH as protocol and in SSH options on the left hand tab select Auth and select the private key file.

If you get “server refused our key” error then I would suggest running sshd with debug option. (/usr/sbin/sshd -d -d -d &)

You can also check the permission of your files and folders.

chmod 600 authorized_keys2
chmod 700 .ssh
Also check your home directory permission.

It should work. If it is not, you can try running the ssh client in debug mode from the same server. (ssh -l username servername -v -v -v)

Passwordless connection to Tru64 machines

It is almost same as HPUX configuration but the directory name should be ".ssh2" instead of ".ssh". And it should contain a text file named "authorization"; the contents of that file should be list of public key files separated by newline.

Example:

/home/samuel/.ssh2>ls
authorization id_rsa_2048_a id_rsa_2048_a.pub random_seed
/home/samuel/.ssh2>cat authorization
Key id_rsa_2048_a.pub

Someother tools I came to know when I was searching Putty enchancements

I wanted some small utility to avoid digging through Start menu Programsto find Putty or any other program to launch it. I want a small command line kind of utility and found Launchy it can launch any program by typing few letters of that program.
Sometime I start source control/compilation of kernel from my office and want to continue things from my home. But since terminal emulators such as Putty are bound to local machine, I used to open new terminal session or use remote desktop connection to my office machine to continue my work. One of my colleagues told me about GNU screen and how it can solve the problem. Here is some good introduction to screen.

Putty sessions

I was searching for method to launch Putty session quickly and saw the following article Multiple putty addons http://www.thegeekstuff.com/2008/08/turbocharge-putty-with-12-powerful-add-ons-software-for-geeks-3/

Previously I was using "Putty Session Manager" to categorize and lanuch putty sessions.

Enabling colors in vim in putty terminal

http://vim.wikia.com/wiki/Using_vim_color_schemes_with_Putty

Porting to “Intel C Compiler”

2008-11-22T04:36:00.002-08:00

In this post, I will explain how to easy it is to compile/port C programs and makefiles designed for GCC(GNU compiler collection) can be used with ICC(intel c compiler)

The necessity for using ICC happened to me because gcc was generating much bigger object files. Ace is using ACPI-CA(http://acpica.org/) as it is ACPI driver. After compilation the ACPI library is around 7M in debug version and around 500K in non-debug version. But from http://acpica.org/download/changes.txt it seems Microsoft C compiler produce smaller code.

Non-Debug Version: 81.2K Code, 17.0K Data, 98.2K Total

Debug Version: 155.8K Code, 49.1K Data, 204.9K Total

So I decided to try “Intel Compiler” as replacement for GCC. Things were easy, since icc has options which is similar to gcc.

You can get the details of portability options from icc documentation -http://www.intel.com/software/products/compilers/docs/clin/main_cls/index.htm.

I just changed my make.conf file to check the compiler in use and use appropriate options. I removed -fno-leading-underscore and –Wall. I removed –Wall because it was giving lot of warnings, we have to fix our code sometime soon. I removed -fno-leading-underscore because there is no equivalent option in icc, however icc does not adds underscores to symbols anyway.

I added –O1 option because the kernel was panicked during boot with invalid opcode exception, I believe it was because of some MMX register usage by icc. So I settled with –O1 now.

ifeq ($(CC),gcc)

DEBUG_FLAGS= -gdwarf-2 -g3

CFLAGS+= -Wall -Wno-multichar $(DEFINES) -nostartfiles -ffreestanding -funsigned-char -fno-leading-underscore -c -fno-stack-protector $(DEBUG_FLAGS) $(CUSTOM_FLAG)

else

DEBUG_FLAGS= -gdwarf-2 -g

CFLAGS+= -O1 -Wno-multichar $(DEFINES) -nostartfiles -ffreestanding -funsigned-char -c -fno-stack-protector $(DEBUG_FLAGS) $(CUSTOM_FLAG)

endif

I also made some static variables in kernel/i386/gdb_stub.c to non-static because icc appends .0 to static variables but it forgets the same name when referenced in a inline assembly code in the same file. After removing the static attribute it is working fine.

gcc compiler took the following time to compile Ace source code.

real 0m51.125s

user 0m36.975s

sys 0m11.185s

icc compiler took the following time to compile Ace source code.

real 1m44.366s

user 0m59.107s

sys 0m20.946s

Gcc produced double the size of kernel.sys produced by icc. (I used GNU linker(ld) and ar).

gcc output size:

[samuel@linux Ace3]$ ls -lh /home/samuel/Projects/Ace3/obj/

-rw-rw-r-- 1 samuel samuel 372K 2008-11-22 18:17 acpi.a

-rw-rw-r-- 1 samuel samuel 545K 2008-11-22 18:17 arch.a

-rwxrwxr-x 1 samuel samuel 1.3M 2008-11-22 18:17 kernel.sys

-rw-rw-r-- 1 samuel samuel 62K 2008-11-22 18:17 libds.a

-rw-rw-r-- 1 samuel samuel 40K 2008-11-22 18:17 libheap.a

-rw-rw-r-- 1 samuel samuel 39K 2008-11-22 18:17 libstring.a

-rw-rw-r-- 1 samuel samuel 9.5K 2008-11-22 18:17 libsync.a

-rw-rw-r-- 1 samuel samuel 91K 2008-11-22 18:17 pic.a

-rw-rw-r-- 1 samuel samuel 23K 2008-11-22 18:17 pit.a

-rw-rw-r-- 1 samuel samuel 21K 2008-11-22 18:17 rtc.a

icc output:

[samuel@linux Ace3]$ ls -lh /home/samuel/Projects/Ace3/obj/

-rw-rw-r-- 1 samuel samuel 352K 2008-11-22 16:25 acpi.a

-rw-rw-r-- 1 samuel samuel 230K 2008-11-22 16:24 arch.a

-rwxrwxr-x 1 samuel samuel 528K 2008-11-22 16:25 kernel.sys

-rw-rw-r-- 1 samuel samuel 38K 2008-11-22 16:23 libds.a

-rw-rw-r-- 1 samuel samuel 22K 2008-11-22 16:23 libheap.a

-rw-rw-r-- 1 samuel samuel 21K 2008-11-22 16:23 libstring.a

-rw-rw-r-- 1 samuel samuel 11K 2008-11-22 16:23 libsync.a

-rw-rw-r-- 1 samuel samuel 19K 2008-11-22 16:24 pic.a

-rw-rw-r-- 1 samuel samuel 8.4K 2008-11-22 16:24 pit.a

-rw-rw-r-- 1 samuel samuel 13K 2008-11-22 16:24 rtc.a

So it is easy to use icc instead of gcc. However since I am using Windows and icc is free only for Linux for non commerical purposes. I stick to gcc to compile Ace in Windows.

GNU make slow build process

2008-11-06T07:58:00.005-08:00

While building one my project it was taking too much time; the project was taking around 40-60 seconds to build and around 20 seconds to clean. I was frustrated with this because the debugging cycle time for my project was going high.

So I decided to stop debugging my project and start debugging the build process. In my makefile I had .SILENT option and I removed it to see what is going. The following was the output

make[1]: Entering directory `/cygdrive/g/Projects/Ace3/src/lib'
make[2]: Entering directory `/cygdrive/g/Projects/Ace3/src/lib/string'
make[2]: Nothing to be done for `all'.
..
make[1]: Leaving directory `/cygdrive/g/Projects/Ace3/src/lib'
make[1]: Entering directory `/cygdrive/g/Projects/Ace3/src/kernel'
..
make[2]: Leaving directory `/cygdrive/g/Projects/Ace3/src/kernel/pic'
New kernel is at /cygdrive/g/Projects/Ace3/obj/kernel.sys
/cygdrive/g/Projects/Ace3/img/create_bootcd.sh

Everything was fast, however there was huge delay before getting the output “make[1]: Leaving directory `/cygdrive/g/Projects/Ace3/src/lib'”

Then I tried invoking make with –d (debug) option and it gave the following output

This program built for i686-pc-cygwin
Reading makefiles...
Reading makefile `makefile'...
Reading makefile `/cygdrive/g/Projects/Ace3/make.conf' (search path) (no ~ expansion)...
Reading makefile `boot_module.d' (search path) (don't care) (no ~ expansion)...
Reading makefile `interrupt.d' (search path) (don't care) (no ~ expansion)...
Reading makefile `ktrace.d' (search path) (don't care) (no ~ expansion)...
Reading makefile `main.d' (search path) (don't care) (no ~ expansion)...

And it took lot of time before continuing the from the above step, so I knew something wrong with the main.c dependency file, so I opened it and it had too many entries. I casually checked the size of the file and it was 50MB. That explained why make was slow. I carefully examined the dependency entries and found they were repeating. I opened make.conf and checked the rule for making dependency file and found the culprit

%.d: %.c
@$(CC) -c -M $< -I$(INCLUDE) $(CFLAGS) >> $@

The output redirection symbol >> caused the problem. It appended the dependency rules every time I compiled and increased the size of .d file. I replaced >> with > and now incremental build process completes in 3 seconds.

Editing PDF files

2008-10-15T04:37:00.000-07:00

Today, I have to fill a form which is in the form of PDF and send it to some other city. Although it is a PDF file, it doesn’t have any input fields, so I have to take print out of the form and fill and then send it through postal mail. Instead I decided to try some pdf converters and after some searches got the link for http://www.pdfonline.com/pdf2word/index.asp. It is fast and produces rtf files.

I also got the following comparison pdf to word conversion utilities http://www.freewaregenius.com/2008/03/28/how-to-convert-pdf-to-word-doc-for-free-a-comparative-test/

CodeLite - IDE for C

2008-09-21T23:33:00.012-07:00

For my C projects I was using Notepad++ as my editor/IDE for some time. Although notepad++ is good, it is lacking the integration with a code browser, source control and debugger.
I came to know about CodeLite when I was searching for ctags for windows. It has integrated Subversion, ctags, gdb under one roof.

Since it is multiplatform GUI, I was little reluctant to install and try(I have tried lot of multiplatform GUI applications and never satisfied with the look and feel of them). But wxWidgets makes the CodeLite to look like native windows application.

CodeLite has lot of features and it looks very similar to VC++ IDE.

Code browsing is very easy with CodeLite. It is has a very light explorer and also workspace view through which you can browse your project “easily”. You can switch between header and c file “easily” using the “Swap Header/implementation file” in the context menu. Context menus “Goto declaration” and “Goto Implementation” are handy to browse through code quickly.

If you are using cygwin and custom makefile - you can use a script as custom build command - see http://samueldotj.blogspot.com/2007/10/notepad-as-ide.html for more details.

I use the following command to build(because I use gcc cross compiler)

c:\cygwin\bin\bash -l -c 'cd $ACE_ROOT/src;PATH=/usr/cross/i586-elf/bin/:$PATH:;make 2> err; sed -e "s@$\/cygdrive\/$$[a-zA-Z]$@\2:@g" err; rm err’. And the following command to clean

c:\cygwin\bin\bash -l -c 'cd $ACE_ROOT/src;PATH=/usr/cross/i586-elf/bin/:$PATH:;make clean’

Codelite supports debugging through gdb; embedded and remote targets also supported. Since I am using a emulator to test my kernel, I have to use remote debugging in GDB to test my OS. Codelite integrates well with GDB remote debugging. I use the following GDB commands as startup gdb commands.

set print pretty on

directory src/kernel

symbol obj/kernel.sys

source img/gdb/general.gdb

source img/gdb/stack.gdb

source img/gdb/vm.gdb

If SVN is configured, using codelite you can see difference between two versions of a same file. By default codelite uses the default diff viewer. It can be changed from Plugins menu -> Subversion->Options and setting the value appropriately. I use WinMerge to see differnece of source files and have the following settings:

External Diff viewer: C:\Program Files\WinMerge\WinMergeU.exe

Arguments : /dl %bname /dr %mname %base %mine

Another good thing about CodeLite is still under development and your bug report/feature requests are solved within short time frame.

You can download CodeLite from www.codelite.org. It has installer for Windows and Linux also.