File this under neat/stupid C tricks:

/* From linux/include/stddef.h */
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

The offsetof(t,m) macro is supposed to return the offset of member m in type (structure) t. This is useful for a variety of things, particular finding the address of the beginning of a structure given the address of any element in it.

Some compilers implement offsetof() natively and the code above will use the compiler’s offsetof() if it exists. But if it doesn’t it performs the pointer arithmetic tricks seen above. It works by taking address 0 and casting it to a pointer (pointer to whatever structure we care about). Then it uses the structure element operator -> to obtain the value of member, then applies the address-of operator to obtain the address of the structure member relative to a structure beginning at address zero, and thus relative to the beginning of the structure. Then it simply casts this value into a generic size_t, indicating an address offset. Note that while this code appears to dereference a null (0) pointer, it only applies the address-of operator to the result so no actual dereferencing is performed at runtime.

The Linux kernel uses this in its linked list implementation. The doubly linked list implementation uses a structure called list_head which contains forward and backward pointers. To use the linked list, you simply need to include the list_head as an element anywhere in whatever structure you want to use as the data associated with the list. You can even include it multiple times, and the data can be a member of multiple lists. You manipulate the list using the list_head structures and when you want a pointer to the data you simply use the list_entry() macro which uses offsetof() to determine where the list_head exists within the data structure then subtracts it to yield the beginning of the structure. Neat and elegant!

For details about the kernel linked list, check out Linux Kernel Linked List Explained, which does a good job describing the various functions which allow easy linked list manipulation.

At work (LNI) we have a tool which implements a remotely controlled RDMA agent using the OpenFabrics interface. The agent is used for compliance, interoperability, and performance testing. For quite some time we’ve had a problem where sometimes the agent hangs and then after sending SIGINT (ctrl-C or kill) the agent shows up as “defunct” with a Zombie state in the output of ps.

Normally a zombie process means that the process has died but remains in the process table because the parent hasn’t called wait() to “reap” the process and retrieve the return code. If you kill the parent, the zombie process becomes parented by init (process 1) and init reaps it. But, the problem we were having was clearly not this. Killing the parent did nothing. And the defunct agent appeared to be holding onto resources. It was not possible to start a new agent since the defunct one continued to hold a socket open, which would never be true with the usual meaning of a defunct process. The only workaround was to reboot the system.

The key to the real answer is that the agent uses multiple threads with the POSIX threads library. Individual threads and processes under Linux are both viewed as tasks to the process management code. Threads are implemented using one task designated as “thread group leader” and a “thread group id” present in each task_struct. By default, the ps utility displays just the thread group leader, hiding the other tasks.

Working at the OpenFabrics Alliance interoperability event last week at UNH-IOL we once again experienced the defunct problem. This time I attacked it in earnest and discovered the “ps aumx” option (”m” being the critical one which displays threads individually). This showed the thread group leader in “Z” state, and then the key: another threads was stuck in the “D” uninterruptible sleep state. In this state the process is running in kernel mode yet cannot be interrupted by any signal, including SIGKILL (signal 9, which normally cannot be ignored). Thus, this thread is unkillable, until whatever condition it is waiting for in kernel mode is cleared. The only solution is to reboot the system.

When the SIGINT (or SIGKILL or whatever) was delivered to the agent, all the tasks (threads) received the signal. Yet one couldn’t exit because it was in “D” and the thread group leader remains around in the deceptive “Z” state, in this case indicating that the process is still around. In fact, this was confirmed by running ps aumx on the agent after a suspected hang but before attempting to kill the agent. This time there were the usual numerous threads, one of which was listed in state “D”.

So how to debug from here? It was possible to use the Magic SysRq Key to obtain a listing of the current tasks on the system. This displayed a stack trace showing the execution context of each task running in kernel mode, including the agent task stuck in uninterruptible sleep. Using this it was possible to determine what the task was doing which caused it to slip into a coma.

I wanted to make sure this got written up because I spent way to much time looking on Google and finding pages that described the usual meaning of “defunct” processes but didn’t touch on this deceptive alternate meaning. So hopefully now it’ll be found! Extra thanks to Professor Robert Russell who helped me troubleshoot all of this.

This week I am attending the InfiniBand Trade Association plugfest at UNH-IOL and next week I’ll be there again for the OpenFabrics Alliance interoperability event. The OFA is an industry alliance representing InfiniBand and iWARP, both high performance networking technologies that allow remote DMA (Direct Memory Access). For my readers who don’t know what RDMA is, I’ll try to explain.

First, a bit of background about DMA. There are many different ways to handle IO. Initially, the CPU was involved in copying data between a device and memory. This means that the CPU can’t be used for anything else during the copy. Since access to IO devices is significantly slower than the CPU (generally orders of magnitude, especially for disks), the CPU is essentially wasted on such a simple task. DMA allows a separate controller to take charge of the transfer between the IO device and main memory. The CPU initiates a transfer, and the DMA controller does the actual work, freeing the CPU for other tasks. When the DMA transfer is completed, it sends an interrupt to the CPU which alerts the operating system that the transfer is done.

In an ideal world the operating system has a number of tasks which can run on the CPU. An ideal load balances tasks which require a lot of IO and tasks which are bound by CPU (for example, many calculations with little IO). By using DMA the system an switch to CPU bound tasks and run them while the slow data transfer happens. Additionally, because the system is not overloaded with interrupts occurring constantly (for example, with a byte-by-byte non-DMA transfer) interactive tasks - such as a keypress being registered - are handled more effectively.

RDMA - Remote DMA - extends this concept to networking. Networking tends to involve a lot of data copying, and a lot of work by the operating system. Many network cards support DMA already, but this only allows a DMA transfer of raw network data from the card into the OS Kernel’s memory. This data must be decoded as it moves through the protocol stack, which typically involves additional copying, and eventually it is deliver to a user space program (which involves yet another copy). All this copying is particularly necessary since the kernel must virtualize the shared network interface to all the programs running on a system. The kernel needs to ensure that a user program cannot read network traffic meant for a different program. As network interfaces keep getting faster this overhead becomes more and more significant.

RDMA gives increased performance at the expense of security. Special network interface cards implement the protocol stack in silicon on the card. A user program can then initiate a remote direct memory-to-memory transfer. The operating system kernel is not involved in the transfer at all. This means the CPU can be busy doing computations while the (comparatively) much slower network link transfers data. This is especially useful for high performance computing. If a parallel task involves a lot of computation with message passing to synchronize, then things can be drastically sped up by using RDMA.

InfiniBand is one technology that implements RDMA. IB uses a high performance dedicated network. It is commonly used for computing clusters, since it uses dedicated InfiniBand switch hardware. iWARP is a second technology for RDMA which also RDMA transfers over standard Internet Protocol links (such as a normal local area ethernet network). It still requires special iWARP “RNIC”s which contain a hardware network stack and enable RDMA operations. But there is no need for special switch hardware, and iWARP can even be used over a wide area.

Obviously this technology is not going to show up in your home any time soon. The target market is the high performance computing market, the storage market, and financial market. Nonetheless, within this limited sector RDMA is a very exciting development.

For many years now the AOL Instant Messenger protocol OSCAR has been reverse engineered, enabling third party access to the AIM network. Open source libraries such as libpurple package this functionality, and are used by the Pidgin and Adium clients amongst others.

Recently, AOL has announced an OpenAIM initiative, billed as opening the network for third party clients. But check out the license agreement:

Additional Feature Requirements. Any Custom Client or Web AIM Developer Application that you distribute must include at least two of the following features or functionalities (”Additional Features”) as an integral part of such distributed Developer Application:

1. AIM Expressions. Inclusion of the capability for your users to choose and display a Buddy Icon to customize his or her user experience and provide a link to the AOL-Hosted AIM Expressions web page as documented in the AOL Additional Features document.
2. AIM Toolbar. Inclusion of the AIM Toolbar as a user-selected option during the registration/download/installation process for the Developer Application, as applicable.
3. AIM Start Page Launch. Inclusion of the launch of the AIM Start Page upon users. logon to your Site or to the Developer Application.
4. Buddy Info. Inclusion of content provided by AOL that includes information about a user’s online status, including the user’s AIM profile, and AOL-supplied advertising.
5. Advertisement. Inclusion of an AOL-provided display advertisement (”Advertisement”) within your Custom Client, Site or activity window. Unless otherwise provided in a written agreement, all revenue from such Advertisement will belong to AOL.

It isn’t open at all. You need to include specific functions. And even worse, if your client is used by more than 100,000 people, as determined by AOL, you must include advertising supplied by AOL. I’m glad that AOL has decided to get onto the “open” bandwagon but this is a PR move - the protocol hasn’t really been opened at all. In fact, it appears that this may even be a ploy to go after open source libraries like libpurple which currently use the reverse engineered OSCAR specification.

Google Talk is based on the open XMPP messaging protocol, also known as Jabber. It provides a true open interface, and interoperates freely with XMPP/Jabber servers operated by independent individuals (like myself). You can view the specification online without the stipulation of a license agreement. XMPP is the truly open instant message framework.

You can send me an instant message at spinfire@isomerica.net, and if you want to join XMPP users, register your own screen name at isomerica.net or Google Talk or any of the open Jabber/XMPP operators. Give it a try in the name of open specifications and interoperability!

In one of my classes this semester we have had a sequence of assignments dealing with a program that finds strings in files (a simpler “grep”). Initially, the program just searched files. For the second assignment additional options were added and we had to descend into directories recursively. Recursive directory descent proves to be nontrivial because when you follow symbolic links you may enter a directory loop. This would cause infinite recursion, which is clearly not good.

The solution is to keep track of your position on a stack. A stack is a natural data structure for any recursive process. For example, when functions are called recursively data and positions are kept track of on the system stack. Each directory on a POSIX system is uniquely identified by its inode number and its device number (obtained from a stat() call). I created a linked list of nodes with inode and device numbers as well as the full file path for error reporting. To detect directory loops, my program pushed onto the directory stack each time a new directory is encountered and a recursive call is made. When the recursive function returned, the directory stack was popped off. Each time push is called the stack is searched all the way to the bottom, looking for a node with the same inode,device pair. If one is found the stack can be printed and the descent aborted.

The third assignment was to modify this program to search directories in a multithreaded manner using pthreads. Each time a directory is encountered, a thread is created to process it (up to certain limits after which the directory is processed in line). Clearly this presents a problem for the directory stack data structure. The stack needs to be maintained as threads are launched so loops can be prevented. However, clearly the threads cannot be manipulating a single stack - nodes would be interleaved and messed up.

One way to deal with this is to copy the stack each time you launch a thread, then pass the copy to the thread. When the thread is finished it free()s the copy. This satisfies the problem. The stacks do not need to be identical, they just need to converge at some point near the bottom. These stack copies will also get progressively larger as you move deeper into a directory tree. Altogether, it involves a lot of allocating, copying, and deallocating, as well as additional memory usage.

Better way: Branching stack. A branching stack is similar to a standard stack, having operations push() and pop(). The branching stack introduces a new operation called branch(). This operation simply creates a new top-of-stack pointer and points it to the same place. This yields a lightweight copy of the stack. Each copy can be pushed onto and this will result in two different stacks which converge at the branch point. The copy shouldn’t pop off below the branch point - this would corrupt the shared portion of the stack. But our application dictates that this won’t happen because there will be an equal number of pushes and pops. This is a beautiful solution and it doesn’t even require modifying the node structure! all memory below each branch point is shared.

There is still an issue with regards to threads. What happens if a lightweight copy is created, passed to a newly created thread, then the original thread finishes processing the directory and goes to pop off the stack? The memory at the point will be freed(), but there might still be other threads above this node on the stack! If the memory is freed they will not be able to check for loops or print them out. The solution is to add a reference count to each node in the stack, initially zero. The reference count at the top of the stack is incremented each time a branch is performed. When a thread is done with the branch of the directory stack (and at the top of the branch section), it performs a join() operation which decrements the reference count at the tops of the branch stack.

Now, when a pop() operation is performed the reference count is checked. If it is nonzero, it blocks with a conditional wait. When a join() operation reduces the reference count to zero, it signals the waiting pop() operation which can continue. Obviously appropriate synchronization is also needed. Still, this is much better than the original solution. The memory usage is much smaller and the working set is more likely to fit in cache. Furthermore, branching is an extremely simple operation, simply copying a pointer and incrementing a counter. Similarly for joining.

This version does introduce blocking in the pop() operation. But for the most part this does not affect performance - the parallel gain is from processing a few directories in parallel not launching hundreds of threads which is what happens if you do not limit a version that copies. And, blocking threads consume no CPU. Even when processing deep directory trees, my program’s memory usage rarely climbs above 1MB.

Below is a visualization of this data structure after a branch.

The week of November 12th I will be heading to Portland, Oregon for the DLNA Plugfest. This marks a new milestone as the first time I’ve ever traveled on a business trip (sadly, I will not be traveling business class :). The plugfest is a week long event where vendors who are members of DLNA will get a chance to test their devices for interoperability, as well as test with out product which is a test suite for the DLNA devices guidelines. I was also invited to the previous plugfest in Tampere, Finland, but alas I was in the UK for my honeymoon during the Finland Plugfest.

Unfortunately, I’ll be missing some class. But it works out well since that week is a short one due to a UNH Holiday and avoids scheduled tests. Plus, there is a decent chance I may be able to attend a plugfest in the spring as well, in either Europe (currently undecided between France and Spain) or Japan. Pretty sweet!

From #haskell, via a discussion on reddit:

<sigfpe> Haskell is so strict about type safety that randomly generated snippets of code that successfully typecheck are likely to do something useful, even if you've no idea what that useful thing is.

With 320GB SATA drives on sale with free shipping, I decided to increase my workstation’s RAID capacity for the last time. I say for the last time because I am now literally out of drive bays. With the new drive, tuna now has one system drive and five 320GB drives in a RAID 1. I have two more SATA ports remaining, but I’m out of 3.5″ drive bays. Plus, I’m probably set for capacity for now!

One nice things about SATA drives with Linux these days is you don’t ever need to shut the system down. In fact, with SATA, Linux software RAID, and the XFS filesystem I was able to add 320GB of capacity to the RAID filesystem without even unmounting it. During the entire time the system was completely usable, including all data on the RAID volume.

First, I took the case side off and carefully removed the drive cage which has an empty slot. There was already another drive in this cage so I had to set it down carefully without pulling out the SATA connection or power. Next, I screwed the rail kit onto the drive. The drive with rails then slides into the cage. One the drive was in the cage I carefully plugged a new SATA cable into the SiI3114 controller on my motherboard. As soon as you connect the other end of the SATA cable to the drive, and connect power to the drive, dmesg is filled with some kernel messages recording the hotplug event:


ata8: exception Emask 0x10 SAct 0x0 SErr 0x50000 action 0x2 frozen
ata8: hard resetting port
ata8: SATA link up 1.5 Gbps (SStatus 113 SControl 310)
ata8.00: ATA-7, max UDMA/133, 625142448 sectors: LBA48 NCQ (depth 0/32)
ata8.00: configured for UDMA/100
ata8: EH complete
scsi 7:0:0:0: Direct-Access ATA ST3320620AS 3.AA PQ: 0 ANSI: 5
SCSI device sdf: 625142448 512-byte hdwr sectors (320073 MB)
sdf: Write Protect is off
sdf: Mode Sense: 00 3a 00 00
SCSI device sdf: drive cache: write back
SCSI device sdf: 625142448 512-byte hdwr sectors (320073 MB)
sdf: Write Protect is off
sdf: Mode Sense: 00 3a 00 00
SCSI device sdf: drive cache: write back
sdf: unknown partition table
sd 7:0:0:0: Attached scsi disk sdf
sd 7:0:0:0: Attached scsi generic sg5 type 0


At this point I very carefully slid the cage back into the chassis and organized the cables. Next, I buttoned up the case and ran cfdisk on the new drive to create partitions:


root@tuna:~# cfdisk /dev/sdf


I created a single partition the size of the entire drive, then set the partition type to Linux raid autodetect (code “fd”). Once you tell cfdisk to write the partition table a kernel log message is generated indicating the new partition layout.


SCSI device sdf: 625142448 512-byte hdwr sectors (320073 MB)
sdf: Write Protect is off
sdf: Mode Sense: 00 3a 00 00
SCSI device sdf: drive cache: write back
sdf: sdf1


With the new sdf1 partition available for use, I added /dev/sdf1 into the RAID 5 as a hot spare.


root@tuna:~# mdadm --add /dev/md/0 /dev/sdf1
mdadm: added /dev/sdf1
root@tuna:~#


At this point md0 has four drives, with a fifth available as a hot spare:


root@tuna:~# mdadm --detail /dev/md/0
/dev/md/0:
Version : 00.90.03
Creation Time : Wed Jan 3 20:23:10 2007
Raid Level : raid5
Array Size : 937705728 (894.27 GiB 960.21 GB)
Used Dev Size : 312568576 (298.09 GiB 320.07 GB)
Raid Devices : 4
Total Devices : 5
Preferred Minor : 0
Persistence : Superblock is persistent

4 8 81 - spare /dev/sdf1
root@tuna:~#


To grow the array by turning the spare into an active component, you need to use mdadm –grow. There is a short delay while it copies a critical section, then reconstruction begins. The entire array must be reconstructed to stripe data and parity information across all five drives.


root@tuna:~# mdadm --grow /dev/md/0 -n 5
mdadm: Need to backup 768K of critical section..
mdadm: ... critical section passed.
root@tuna:~#


This kernel message is printed:


md: bind<sdf1>
RAID5 conf printout:
--- rd:5 wd:5
disk 0, o:1, dev:sdb1
disk 1, o:1, dev:sdc1
disk 2, o:1, dev:sdd1
disk 3, o:1, dev:sde1
disk 4, o:1, dev:sdf1
md: reshape of RAID array md0
md: minimum _guaranteed_ speed: 1000 KB/sec/disk.
md: using maximum available idle IO bandwidth (but not more than 200000 KB/sec) for reshape.
md: using 128k window, over a total of 312568576 blocks.


The file /proc/mdstat gives the status of the reshaping, including a time remaining estimate. In my experience, the time estimate was pretty reasonable. It took around 7 hours to reshape my array from four drives to five. You can use the “watch” command to get continuous status updates.


root@tuna:~# cat /proc/mdstat
Personalities : [raid6] [raid5] [raid4]
md0 : active raid5 sdf1[4] sdb1[0] sde1[3] sdd1[2] sdc1[1]
937705728 blocks super 0.91 level 5, 64k chunk, algorithm 2 [5/5] [UUUUU]
[>....................] reshape = 0.5% (1749580/312568576) finish=440.0min speed=11770K/sec

unused devices: <none>



root@tuna:~# watch -n 30 cat /proc/mdstat



root@tuna:~# mdadm -D /dev/md/0
/dev/md/0:
Version : 00.91.03
Creation Time : Wed Jan 3 20:23:10 2007
Raid Level : raid5
Array Size : 937705728 (894.27 GiB 960.21 GB)
Used Dev Size : 312568576 (298.09 GiB 320.07 GB)
Raid Devices : 5
Total Devices : 5
Preferred Minor : 0
Persistence : Superblock is persistent

Number Major Minor RaidDevice State
0 8 17 0 active sync /dev/sdb1
1 8 33 1 active sync /dev/sdc1
2 8 49 2 active sync /dev/sdd1
3 8 65 3 active sync /dev/sde1
4 8 81 4 active sync /dev/sdf1


About 7 hours later the reshaping finished. At this point, I run xfs_growfs /mntpoint. This command will automatically choose options to grow the existing filesystem to the maximum available size. You do not need to unmount the filesystem. The grow process completes relatively quickly. Note, this is for SGI’s XFS filesystem. For other filesystems such as ext3, consult manpages to find out how to grow the filesystem.


root@tuna:~# xfs_growfs /mnt/albacore
meta-data=/dev/md/0 isize=256 agcount=48, agsize=4883888 blks
= sectsz=4096 attr=0
data = bsize=4096 blocks=234426432, imaxpct=25
= sunit=16 swidth=32 blks, unwritten=1
naming =version 2 bsize=4096
log =internal bsize=4096 blocks=32768, version=2
= sectsz=4096 sunit=1 blks
realtime =none extsz=131072 blocks=0, rtextents=0
data blocks changed from 234426432 to 312568576
root@tuna:~# df -h
Filesystem Size Used Avail Use% Mounted on
/dev/sda3 138G 127G 12G 92% /
udev 1007M 2.7M 1004M 1% /dev
/dev/md/0 1.2T 853G 340G 72% /mnt/albacore
shm 1007M 0 1007M 0% /dev/shm
mackerel:/export 232G 150G 82G 65% /mnt/mackerel
anchovy:/export 149G 3.5G 145G 3% /mnt/anchovy


As you can see the capacity of /mnt/albacore is now up to 1.2TB, without ever turning the computer off, or even unmounting the filesystem!

On Linux systems, ldd is a command which displays information about which shared libraries are used by a particular executable. For example:

dpn@colobus:~$ ldd /bin/sh
        linux-gate.so.1 =>  (0xffffe000)
        libncurses.so.5 => /lib/libncurses.so.5 (0xb7f4c000)
        libdl.so.2 => /lib/libdl.so.2 (0xb7f48000)
        libc.so.6 => /lib/libc.so.6 (0xb7e24000)
        /lib/ld-linux.so.2 (0xb7f9c000)

This morning I read this page which gives an excellent explanation of what the “linux-gate” entry is (read the link for more background). Basically, it maps to a virtual shared library created by the kernel. The virtual shared library is used to select the best interface for performing a system call depending on what your CPU supports. Essentially, more modern x86 systems support a sysenter instruction which is significantly faster than the old method of generating an particular interrupt with the int instruction.

Naturally, I immediately tried what the article described on my workstation and was surprised to find no linux-gate.so.1 entry! That system is 64 bit (note the 64 bit addresses for libraries in the ldd output below).

dpn@tuna:~$ ldd /bin/sh
        libncurses.so.5 => /lib/libncurses.so.5 (0x00002ae3837c8000)
        libdl.so.2 => /lib/libdl.so.2 (0x00002ae383926000)
        libc.so.6 => /lib/libc.so.6 (0x00002ae383a2a000)
        /lib64/ld-linux-x86-64.so.2 (0x00002ae3836ab000)

To find out what is going on, I can run objdump -d on /lib64/libc-2.5.so, which I know will contain several system calls since it provided the most basic interface to kernel functionality. I redirected the output to a file and opened it in vim, searching through for a simple function which I know uses a syscall:

0000000000090ca0 :
   90ca0: b8 3f 00 00 00        mov    $0×3f,%eax
   90ca5: 0f 05                 syscall
   90ca7: 48 3d 01 f0 ff ff     cmp    $0xfffffffffffff001,%rax
   90cad: 73 01                 jae    90cb0 
   90caf: c3                    retq
   90cb0: 48 8b 0d 11 42 1a 00  mov    1720849(%rip),%rcx        # 234ec8 <_io_file_jumps +0x988>
   90cb7: 31 d2                 xor    %edx,%edx
   90cb9: 48 29 c2              sub    %rax,%rdx
   90cbc: 64 89 11              mov    %edx,%fs:(%rcx)
   90cbf: 48 83 c8 ff           or     $0xffffffffffffffff,%rax
   90cc3: eb ea                 jmp    90caf 
   90cc5: 90                    nop

This is the assembly code for the uname system call (I omitted 10 additional nop instructions at the end, presumably added by the compiler for alignment), which returns information about the current running kernel (such as version, etc). I can see from /usr/include/asm-x86_64/unistd.h that the system call number for uname is 63, which corresponds to 0×3f in hex. This is the value moved into the register eax at the start of the uname function. The kernel code looks into this register to determine which system call was executed. The next instruction is the syscall instruction. As you can see, the x86_64 architecture has an instruction called syscall which is directly defined as part of the architecture for all CPUs. Unlike x86, which had several different system call interfaces including the int instruction and the sysenter instruction, the virtual system call interface defined in linux-gate has no purpose on x86_64 systems.

One question remains. The uname system call takes one argument: A pointer to a utsname struct, which the kernel fills with data. But how is that argument passed to the kernel? The glibc function only sets up the system call number in eax. The answer is that in x86_64 arguments are passed in registers, beginning with rdi and rsi. So when the uname stub in glibc is called by a user program, rdi already contains the pointer to the utsname struct. The kernel just takes the pointer value out of rdi, where it remains untouched by the stub.

I have a Visa credit card through Bank of America. A few months ago I noticed a recurring charge on my account which I couldn’t track to anything I was receiving or had agreed to pay for. I followed the normal procedure for challenging a charge and everything seems to have been dealt with. However, it did teach me an important lesson about monitoring charges closely. It is good to discover any fraudulent charges as soon as they occur. Because of this and other reasons, I use the Bank of America Online Account website to regularly check charges, pending charges, etc. I also pay my bills via the online website, choosing not to receive paper statements at all.

Bank of America started a promotion where their credit card customers could open a checking account and receive a $100 bonus from them. I decided to do this, and followed the procedure for opening the account online on Sunday night. Early Monday morning I received an email from Bank of America saying that my account application had been granted. Obviously they send things like the ATM/Debit card and PIN number through conventional mail, and of course I have yet to receive this information - it has been less than 18 hours since I applied for the account.

This morning I tried to access my Bank of America Online Account site to do my normal periodic check of any pending charges. But after entering my login information, I get a new page saying “Other Bank of America Accounts Detected: Enter ATM PIN.” This page required me to enter information about my new account - which I have not yet received - to continue and access information about my existing accounts. The bottom of the page gives my two choices: Continue (which doesn’t work because I can’t enter account information BoA hasn’t given me yet) or Cancel. If I click cancel, I get a page saying “You have decided not to continue which means you will be unable to access your accounts.” Which means I can’t access my existing account either, the one I have had access to for over a year now. The page also gives me a nice set of reasons I can give for why I decided to cancel, including “I don’t have all of the required information” and “I don’t have my ATM PIN.” Except no matter which you choose, it simply cancels the online account login and dumps me back at the Bank of America homepage.

Dear Bank of America: This behavior is broken. Clearly it takes longer for you to actually mail out the new account information than to send out an email saying “your account has been granted.” And clearly it also takes some amount of time for the US Postal Service to actually deliver that mail to me. Fortunately I have already payed my bill for this month, but what if I hadn’t? My experience has been that it can take up to a week or more for new account information to arrive in the mail. Because I choose to receive statements online (which, I might add, saves BoA costs), I don’t have a paper bill stub to send in a check with. So quite conceivably this bug could cause someone to miss a payment, causing the typical enormous late fees and sky high default APR.

I don’t understand how online banking sites get away with this shit. There is absolutely no reason why it should be necessary to completely block access to a customer’s online account access when they sign up for a new account. It doesn’t make sense from a technical standpoint, a security standpoint, or a usability standpoint. All you need to do to implement new account setup in the online account manager is to have a link on the main page of the online account site, after you log in. You can simply say “We show that you recently signed up for a new account. When you receive your account details, click here to add it to online banking.” This works far better from a usability standpoint, and it doesn’t lock a customer out of their own account management tools while waiting for BoA and the USPS. What if the postal service messed up and the new account mailing got lost? I’d be completely screwed, because it would inevitably be a very long time before I had access to my statements and bill pay tools.

I sent a comment in via their online account comment/bug report form. We’ll see what comes of it.

In the process of trying to clean up some directories on my systems, I banged out a quick python script for searching recursively beneath a particular path and printing the largest files located. You can configure how many items are printed. They will always be printed in descending order (largest first) with the file’s path and a human readable size.

You can probably do this with other tools (du comes to mind, although it doesn’t do exactly the same thing, and the output of du -h is harder to sort). But this works reasonably well and is fairly fast. If you add the -v option, additional info is printed about the program’s run.

Interestingly enough when I was working on this I was originally planning to use the Python heapq priority queue. But it wasn’t really flexible enough for my needs and apparently it is often slower than the Python built in list sort. I’m pretty sure that the built in Python sort is now using an adaptive mergesort called timsort. I’ve found that most of the bottleneck is in the stat() calls to determine file size anyway. The time difference on subsequent runs makes this very clear. Operating system caching means that the later runs are considerably quicker.

Sample Run

dpn@colobus:~/Common/scripts$ python bigfiles.py -vn 10 /usr/portage
Processing ... Called stat() on 146116 files in 6.805681 seconds
Sorting ... Sorted in 0.617009 seconds

46.71 MB /usr/portage/distfiles/jdk-1_5_0_06-linux-i586.bin
44.05 MB /usr/portage/distfiles/jdk-1_5_0-doc-r1.zip
42.32 MB /usr/portage/distfiles/X11R6.8.2-src.tar.bz2
40.75 MB /usr/portage/distfiles/linux-2.6.19.tar.bz2
39.36 MB /usr/portage/distfiles/linux-2.6.17.tar.bz2
38.95 MB /usr/portage/distfiles/linux-2.6.16.tar.bz2
37.36 MB /usr/portage/distfiles/gcc-4.1.1.tar.bz2
26.95 MB /usr/portage/distfiles/gcc-3.4.5.tar.bz2
19.05 MB /usr/portage/distfiles/mono-1.2.2.1.tar.gz
17.21 MB /usr/portage/distfiles/mono-1.1.13.2.tar.gz

You can download the script here. I would appreciate it if you sent any modifications back to me so I can incorporate them and post them here. Thanks! Enjoy…

Software development today is generally very complex. Large pieces of software can reach millions of lines of code, developed by many developers with varying skill and technique. Quality Assurance, or QA, is a huge job. In the most ideal situation, every possible path of execution is checked. Only in this circumstance is the code fully tested. But this is very difficult to achieve. The number of possible code paths is typically immense. While appropriate for NASA and nuclear powe r plants, the development cycle of a commercial software tool is often too short to aim that high. As a second best alternative, we can aim for complete code coverage, in other words, every line of code is tested.

Obviously, it is impractical to aim for complete code coverage when you are doing QA by hand. The solution is automated testing. Automated testing allows you to retest your application every time you commit a change to version control. This level of automated testing helps to ensure that bugs are never introduced into already working code. Typically the deepest levels of automated testing are used for libraries, where the consequences of bugs are greatly amplified.

Since I started working at my current job last summer I have been working on a single project, written in C#. The project is a compliance testing suite for a proprietary protocol. Eventually (shortly, in fact), a trade association will use the tool we wrote to test vendor’s products. And, if they pass, they get to put a certain logo on their packaging when they sell their product. Many of the tests our tool runs against devices are automated, but some require user intervention. You might think our test tool would use some nice automated testing, particularly for its networking libraries, but unfortunately it does not. The result is less than pretty. During the development cycle we constantly encountered problems with libraries that were part of our tool. Unfortunately, I was on the wrong side of those libraries.. and frequently found myself having to find and help fix bugs in them. Since we had no automated testing, things would often get broken later due to a new feature or code change and the problem wouldn’t be found for weeks.

What is the better way? All of the libraries need to have automatic test suites. This vastly simplifies the QA process which frees up resources to do some real QA and find the more difficult issues. The end result is simply better software. Soon, I will be moving to a different project at work and apparently I’m going to be taking on the role of writing an automated test suite for parts of the core API. This is the way to do it. Unfortunately we are on a tight release schedule and there is no way we’ll even get to test the entire API, let alone shoot for complete code coverage. Ideally the testing process should begin very early on.

Some software projects are even using a test driven development model. Authoring a test for a particular API function has several effects. First, it forces the developer to think in depth about how API function should behave. Particular attention is paid to error handling. Secondly, with the test written first, the function can be tested right from the beginning. There is no QA “catch up” which never works. Instead, the code is always tested. Of course, the automated tests are still no substitute for manual, in depth QA, but they free up resources and catch the stupid bugs sooner.

The most typical type of automated test today is the unit test. In unit testing the focus is on writing tests that test small sections of code. Each unit test tests a particular part of the program. The unit tests also provide a form of documentation as they indicate what the function of the code is. While unit tests ease integration by making sure all the components work, they do not test the integrated product as a whole.

Unit testing has become more and more popular with the rise of the “Extreme Programming” development style and the corresponding increase in test before development. The Ruby on Rails framework actively encourages the authoring of tests before development. For duck typed languages like Python and Ruby runtime testing is more important because compile time type checks are not performed.

I recently read some advice online about honing your programming skills prior to applying for a job by adding unit tests to open source projects. I think this is great advice. Most open source projects would welcome any effort put towards testing as it is often very useful. Wikipedia lists over 40 unit testing frameworks in just about every language. You can choose a small open source project to get your feet wet. Then, you have something to put on your resume. And, it is a specialized skill in demand, too!

The computer language Python uses indentation to mark blocks of code. Any indentation level is supported, but problems can arise when tabs and spaces are mixed. Well, earlier today I managed to do just that on a script of mine. I edited it using two different sets of vim settings and got a mixed indentation file. Solution? I wrote another script to convert tabs into spaces and vice versa. It seems to work decently well. If you discover any bugs, please drop a comment or send an email! Download fixindent.py

In C, arrays are really just pointers with some “syntactic sugar” around them to make access easier. When you use square brackets to access ar[2], ar is a pointer and the compiler translates ar[2] into *(ar + 2). The pointer arithmetic increments the pointer ar by two times the size of an element of ar. Then, it is dereferenced. This has an interesting consequence in that ar[2] == 2[ar]. Both of these allow you to access the the same location in memory and thus the same array member!

Why is this? Remember that a pointer is just an integer value that references a location in memory. So, when you write 2[ar] it translates to *(2 + ar). The address 2, plus the base address of the array. Which is the same as the base address of the array plus two. A really quick snippet of C can verify that this is true:

int main(int argc, char* argv[]) {
    char test[10] = "ABCDEFG";
    if (test[2] == 2[test]) {
        puts("whoa!n");
    }
    return 0;
}

If you compile and run this, it will print “whoa!” as expected, because C == C. But is that really the reason? I compiled this code with gcc -S test.c to get the results (note some code including the string initialization is omitted):

main:
.LFB2:
    pushq   %rbp
.LCFI0:
    movq    %rsp, %rbp
.LCFI1:
    subq    $32, %rsp
.LCFI2:
    movl    %edi, -20(%rbp)
    movq    %rsi, -32(%rbp)
    movq    .LC0(%rip), %rax
    movq    %rax, -16(%rbp)
    movw    $0, -8(%rbp)
    movl    $.LC1, %edi
    call    puts
    movl    $0, %eax
    leave
    ret

There are no compare or conditional branch instructions in there! That means that without any optimization options turned on GCC has generated code which will always execute the code within the if. This is even without the “constant folding” code which attempts to recognize and optimize constant sections of code. The compiler recognizes that *(ar + 2) = *(2 + r). If the C code is changed slightly so the value is assigned to a temporary variable before the comparison:

char tmp = 2[test];
if (test[2] == tmp) {
    puts("whoa!n");
}

main:
.LFB2:
    pushq   %rbp
.LCFI0:
    movq    %rsp, %rbp
.LCFI1:
    subq    $32, %rsp
.LCFI2:
    movl    %edi, -20(%rbp)
    movq    %rsi, -32(%rbp)
    movq    .LC0(%rip), %rax
    movq    %rax, -16(%rbp)
    movw    $0, -8(%rbp)
    movzbl  -14(%rbp), %eax    /*  Move element 2 to EAX */
    movb    %al, -1(%rbp)        /*  Move low order byte of EAX to temporary stack location */
    movzbl  -14(%rbp), %eax    /*  Move element 2 to EAX */
    cmpb    -1(%rbp), %al        /*  Compare temporary stack location and low order byte of EAX */
    jne .L2                             /*  Jump if not zero (equal) */
    movl    $.LC1, %edi
    call    puts
.L2:
    movl    $0, %eax
    leave
    ret

In this case you can clearly see the array element value being retrieved from the stack and placed into the temporary value (seen here as an offset off the base pointer) and then the identical address array element being retrieved into the EAX register, then compared with the temporary value. Interestingly enough, if I compile the same code with the GCC optimization option -O2 it yields a dramatically less complicated set of assembly instructions:

main:
.LFB24:
    subq    $8, %rsp      /* Allocate memory on the stack? */
.LCFI0:
    movl    $.LC0, %edi   /* Move address of "whoa!n" into %edi */
    call    puts          /* Call puts to output %edi string */
    xorl    %eax, %eax    /* Zero out %eax (return 0) */
    addq    $8, %rsp      /* Unwind the stack pointer */
    ret

Optimization really does improve the code! In this case GCC has once again figured out that the two array references are identical. But it has gone much farther this time and optimized away the temp variable, the comparison, and the array altogether! No memory at all was allocated for the array, and all references to it were gone from the assembly language code. Of course, the compiler is correct. The array has absolutely no purpose in our code given the foregone conclusion of the if block executing. You can even see that GCC has changed to using an xor instruction to zero out %eax (return register) instead of using a mov instruction - which is probably faster (note that anything xor’d with itself is always 0). Optimized code really does make a difference.

I don’t know why the compiler has created the two instructions which manipulate the stack pointer. After some thought, the 8 byte allocation would correspond to a pointer to the string literal at label .LC0. I’m not as familiar with how the assembler treats strings. Obviously 8 bytes does not correspond to the entire string, which was previously confusing me. If you know more, please drop a comment. Thanks to Stu for pointing out the obfuscated array trick.

A common beginner exercise in C is to implement some of the string routines. The strcpy routine takes two arrays of characters (terminated by a “null” character and copies the first to the second. Which of these two implementations is better?

char* strcpy (char* a, char* b) {
    int i;
    for (i = 0; i < strlen(a); i++) {
        b[i] = a[i];
    }
    return b;
}

or

char* strcpy (char* a, char* b) {
    int i;
    int len = strlen(a);
    for (i = 0; i < len; i++) {
         b[i] = a[i];
    }
    return b;
}

If you answered the second one, you’re right. The for loop has three parameters. The first is executed before the start of the loop. The second is executed as a loop conditional before the start of each iteration. The third is executed at the end of each iteration. While the first version above seems to be worse because it uses an extra local variable, strlen() is executed once for every iteration of the loop.

In C, strings are terminated by a special character (null). strlen() works by looking forward through the string until it finds the null character. This means the strlen() needs to perform comparison operations on the order of n, where n is the length of the string. And since the for loop in the code above also executes n times, the number of comparisons in the fast loop will be on the order of n and in the slow loop will be on the order of n squared. This is a significant difference when the string gets large!

Of course, an astute observation is that we don’t need strlen() at all. If you iterate over a and b side by side and check a for null before copying you don’t need another step to determine strlen. This avoids the expensive function call to strlen and the double work involved in traversing the string twice. As compiled by GCC with optimization, the assembly language for this version looks like this:

    movzbl  (%rdi), %eax   /* Move value at address %rdi to %eax */
    testb   %al, %al       /* AND low order byte of %eax with itself */
    je  .L2                /* jump to L2 if result was 0 (null) */
    .p2align 4,,7
.L4:
    movb    %al, (%rsi)    /* Move low order byte of %eax into address %rsi */
    movzbl  1(%rdi), %eax  /* Move value at %rdi + 1 to %eax */
    incq    %rsi           /* Increment %rsi */
    incq    %rdi           /* Increment %rdi */
    testb   %al, %al       /* AND low order byte of %eax with itself */
    jne .L4                /* Jump to L4 if not equal to zero */
.L2:
    movq    %rsi, %rax     /* Move %rsi to %rax (return value) */
    ret                    /* Return to caller */

The loop is now quite compact and involves only six instructions. Furthermore, the instructions are relatively simple (no CALL instructions which are very expensive!). But there is still room for improvement. Conditional branches are expensive. The CPU has prepared to execute instructions in a linear fashion and may already be decoding subsequent instructions when there suddenly needs to be a branch. The hardware in the CPU tries to predict which branches will be taken, but this logic isn’t perfect and the CPU stalls for many cycles when the branch prediction fails and it needs to refill the instruction pipeline. To avoid this, we can unroll the loop by processing several elements in each iteration of the loop. This reduces the total number of branches at the expense of an increase in code size and register usage.

The “real” strcpy from glibc on my workstation is actually hand coded in x86_64 assembly. It uses a number of additional tricks including loop unrolling (performing several copies on each loop iteration) and copying multiple characters at once. Check out the x86_64 glibc version here.

In CS520 today I found out that my assignment (mentioned previously) was actually due not today but on Tuesday. So, there were still questions from other students regarding help with the assignment. One student was storing the graph data as a single array containing the upper right triangle of the matrix, read out from left to right one row after another. He was trying to figure out how to index into this array to get a particular item without using a for loop. It is, of course, possible to do this. However, several people in the class insisted that it could not be done.

For a graph with n vertices, this data structure has n - 1 data points in the first row, n - 2 in the second, and so on. The first step in indexing into the array is to figure out where the row you want starts. You could do this using a for loop which sums up a counter with (n - 1) + (n - 2) + …, but this is very inefficient - the algorithm is O(n) versus a possible O(1) implementation. The hint is of course the summing you need to do.

Gauss is famous for figuring out a shortcut way to sum all the numbers between one and 100 in elementary school. What Gauss figured out is that any time you sum a series of numbers between 1 and n the answer is n(n+1)/2. You can use this fact to figure out the indexing problem. First, separate out the sum of i:

The sum of (n - 1) over i from 1 to n is just n(n-1). We can use the expansion of the sum of i to determine a result:

Not only is it possible without a for loop, it is a very clean result! Of course, our job isn’t finished - we still need to add an offset for the position within the row. This is left as an exercise (it isn’t hard to do. Just think of the relationship between the number of vertices, row number, and the number of items in the row).

After class I was waiting around because I planned to go to the UNH ACM chapter’s free pizza/learn about Linux event. The instructor asked me about some of the other caching things I’d implemented and suggested that the results of searching the graph are also eligible for caching, a possibility I hadn’t considered. It ends up being a significantly more complicated problem, because if you want to keep track of paths discovered between nodes in a reusable fashion. It also led to him asking me if I knew about UROP. While I’d love to do UROP I’m not sure how well that can coincide with trying to work part time.

The UNH ACM chapter event was also fun and although I certainly didn’t learn anything new about Linux there was a good turnout of people who did and I got to meet some new folks.. and re-meet some people who’ve previously been in my classes. It turns out most of them are seniors, so they are looking for not-seniors to get involved as well. Yet another thing to eat my time!

For my CS520 class, we were given an assignment to create a program that searches an unweighted, undirected graph for the possibility of a path between two vertices. The basic purpose of the assignment was to be an intro to C, but it is nonetheless an interesting problem.

In mathematics and computer science, a graph is a set of vertices which are connected via edges. If the edges have weights or costs, the graph is weighted. If the edges are only connected in one direction, the graph is a directed graph. Graphs have some really neat uses is computer science. For example, if you needed to route packets between two nodes on a meshed network, you can use a weighted graph to determine the shortest path between the two nodes. One real world application of this is OSPF, a network routing protocol that uses Dijkstra’s Algorithm to determine the shortest path.

Dijkstra’s algorithm is a way to find the shortest path, but for my assignment we just needed to find any path. The method I chose for this is a depth first search. A depth first search is very easy to think about recursively. Here is an example in pseudocode which works recursively:

dfs(i, j)
  if (i == j)
    return true
  else
    for each unvisited vertex v adjacent to i
      if (dfs(v, j) is true)
        return true
    return false


Note that that code snippet only checks for connectivity and does not return the path used to obtain the destination. The path used can be built “on the way back up” as the stack unwinds. That is, the base case step can return the current position then the iterative case can take on its position at the beginning. Then you will end up with a string or list which contains the nodes visited in order. This example really demonstrates the beauty of recursion. There is no need to keep track of where you are in the graph. It is done implicitly by function calls. The only thing you need to take care of is which nodes are visited which is very simple and cheap to do with, say, a bitmap.

I’m not going to post my code here until the due date is passed and gone. I’m pretty proud of the program itself, however. It is very fast. The slowest part of the program when run on large inputs is the reading of the datafile. For a 40,000 node graph the data file measures 763MB! For this input, the program spends about 1:10 reading in the input and searching the graph. For fun, I created a cache which caches the memory representation of the graph. For the 40,000 node graph, this file is approximately 191MB (pretty close to the memory usage of the program). With the cache file in the OS’s disk cache, the graph is searched in under 2 seconds (even for very long paths). It takes a bit longer if the OS has to fetch the cache file from disk, closer to 10 second. Still, a significant improvement. This also demonstrates just how fast the search algorithm itself is. Even on an incredibly complex graph (a 40,000 node graph contains 799,980,000 unique data points, n(n-1) / 2) the search is very fast. Because the graph data is stored as a matrix of adjacent nodes, setting an edge or getting the status of an edge is a constant time operation. All in all, the program works fairly well.

Of course, those numbers are from running a fairly fast system :)

UNH uses the Blackboard software for online course material. The problem is, Blackboard sucks and UNH’s admins seem to have no clue how to maintain it. It regularly goes down for long periods, hours even, at a time. The software itself is slow and the user interface is horrible. Right now it is completely down and not responding, which means no access to the University webmail portal, the registration management system, or Blackboard itself. And this is exactly during peak times.

The problem is when this stuff happens all the time people begin to accept it instead of saying “why is this software unavailable when I need it the most?”

One of the two Western Digital Raptor drives in colobus failed tonight. I was sitting at my desk when my phone indicated an incoming SMS. It turned out to be from the mdadm monitoring utility telling me that one of the drives had failed and the RAID was running in degraded mode. The main filesystem is on a RAID 1 array, which means two identical drives in a mirrored configuration. Since one has now failed, it is running in a non-redundant configuration until the drive can be replaced.

Fortunately I was able to find a replacement drive at the local Best Buy for an entirely reasonable price and I’ll be heading down to Boston to replace the drive tomorrow. Amazingly, the failed drive was less than a year old. The drive is under warranty (5 year warranty terms) so it’ll be replaced free, but in order to rush in an immediate replacement I need to get a new drive. The failed drive will be RMA’d later and then I’ll have a spare on hand.

We’ll need to reboot to perform the drive replacement. The latest version of the Linux kernel fully supports hotplugging of SATA drives, but unfortunately that was not out 160 days ago when colobus was last rebooted. It’ll received a shiny new kernel tomorrow as well.

UPDATE: The drive replacement was completed in about 20 minutes with the array reconstruction taking an additional hour (while the system was up). I am very pleased with how things worked and how easily the my Tyan Rackmount’s hotswap bays worked. I wasn’t able to actually hotswap the drives this time because the old Linux kernel version didn’t support it, but when the machine was rebooted the kernel was upgraded and any future drive replacements can be done with the machine online.

On the advice of a coworker, I tried out the IE7 Beta today at work. It was a bit of a disapointment. I’ve heard a lot of hype about the new IE, so it was really a letdown to actually try it out. The first disapointment was that the installer requires a reboot, and basically breaks the entire machine if you don’t reboot immediately. I had about 20 windows open and busy, so it wasn’t exactly practical to reboot. I started getting error dialogs about missing DLLs and finally our test tool app failed to start because it couldn’t load embedded browser controls. So, I finally had to restart. At this point the install finally completed and I actually had a working IE7.

On to the interface. It is ugly. Ugly and very clunky. They completely threw out all existing human interface guidelines. By default there is no menu bar - the menus are only accessible via icons in a toolbar. The menu bar can be enabled, allowing access to all options. But the menu bar is placed below the address bar. It really proves just how important interface consistency is. I also had to manually turn off all “ClearType” font anti-aliasing in IE despite the system wide setting. The font anti-aliasing was especially brutal, and the fonts were quite blurry and almost unreadable at times. I don’t know why.

People often complain about Firefox memory usage. As a very simple test, I started firefox and IE7 and loaded my rawdog rss feed in each browser. This is a large HTML file with many images linked. Here is the memory usage after loading the entire rawdog feed:

Close, but Firefox wins. Certainly IE isn’t lower, which is actually what I’d expected. The conclusion? I didn’t take my time uninstalling it (which required yet another reboot, thank you Microsoft).