Posts filed under 'General'
So yesterday’s post to madwifi-devel generated a few interesting responses, both on and off list. Derek Smithies suggested that the timestamp may not actually be for the previous packet, but for the end of the current packet.
After looking into this today I realised that I had made a mistake while coding up my experiment which essentially meant that I had already been treating the timestamp as if it were the end timestamp without realising. After re-writing it I convinced myself that the timestamp was not for the previous packet at all.
With the timestamp at the end of the packet, we remove the unknown factor of when the timestamp was actually taken, which is great. This removes the question of how far through the packet’s preamble the timestamp was taken, and removes its dependence on SNR, etc.
However, we still need to accurately determine the transmission time of the packet in order to accurately determine the start time and from there the inter-frame spacing. For HR/DSSS frames this is fairly easy. PreambleLength + PLCPLength + (8*octets/datarate). However, determining whether the frame was sent with HR/DSSS/long or HR/DSSS/short is apparently not possible, so we do not know for an arbitrary packet what it’s preamble and PLCP lengths are. Under controlled conditions though in which we fixed all of these values, we were able to measure inter-frame spaces very accurately.
From the first graph we can easily see the 10 microsecond SIFS interval that separates ACK from DATA packets. The second graph zooms out a bit and we can start to see the DIFS + contention window backoff kicking in. Zooming right out in the third graph shows the major times when activity is happening – for example, we can see where higher layer queueing is starting to take effect.
From here I need to see if I can perform accurate TX time calculations for 802.11a and 802.11g PHYs. 802.11a should be fairly straight forward, however 802.11g poses problems as there are several modes it can operate in depending on the mix of stations in the BSS.
July 22nd, 2009
I’ve been using (and occasionally hacking on) MadWiFi for several years now as part of my Ph.D research. It amazes me that after all this time we can still manage to find pretty severe bugs in the code.
Today I posted a message to the madwifi-devel list detailing how Jamie and I realised that the timestamp on incoming packets is actually the timestamp for the previous packet, not the current. This may sound fairly mundane but there are several areas of the driver that this might affect. Ad-hoc mode has never really worked that well – the problem has been with the way ad-hoc cells merge (which is partly based on beacon timing). So, it will be interesting to see if this finding has any impact on that.
This is a bug that will have been around pretty much forever – and the really annoying part about it is that I don’t really think it’s a bug at all – instead I imagine it’s simply a hardware timing limitation which is probably well known for the fortunate few who have access to the Atheros documentation. Unfortunately for those of us working with open source drivers without access to hardware documentation we miss out on information such as this and end up making incorrect assumptions, which leads to driver bugs such as the ad-hoc merging mess.
I’ll be interested to see the list’s responses. I’ll be especially interested to see if the newer ath5k and ath9k drivers also suffer from this problem (especially seeing as ath9k was written and open sourced by Atheros).
Right, now I can get back to my actual research – though I’m 99% confident that another obscure bug will manage to stop me in my tracks at some point in the near future.
July 21st, 2009
Turns out calculating elapsed times in Mac OS X is a pain. Why not just use gettimeofday(2)? If you’re trying to calculate a time period between two events, you should be able to call gettimeofday(2) before and after, subtract the results, and you’d have an elapsed time, right? Well, almost – but gettimeofday(2) is based on the “wall clock”, so if the time changes between calls to gettimeofday(2) – e.g. daylight savings starts, leap seconds get added, etc – then the elapsed time will be wrong. This also leads to fun when the time is adjusted backwards between calls.
Enter the concept of monotonic time. Monotonic time is a time that increases, well, monotonically from an arbitrary reference point. It is not based on the wall clock, so it’s pretty useless for saying “this event happened at this point in time”, but it is very useful for calculating the time difference between two events, as the clock source won’t ever change between reads.
POSIX defines a nice way of getting times from arbitrary clock sources – clock_gettime(2). You can ask clock_gettime(2) for a time from a number of different clocks. For example, CLOCK_REALTIME will give you the wall time. Linux implements a number of clock sources, including the CLOCK_MONOTONIC source which gives you a nice monotonic time to use for measuring time differences reliably.
Unfortunately Mac OS X (at least 10.5) doesn’t implement clock_gettime(2), which means there’s no simple (read standard) way to get a monotonic time on Mac OS X. As always though, there is a solution.
<mach/mach_time.h> exports the function mach_absolute_time(). This function returns a CPU dependent time, which can, after a bit of magic, be used as a monotonic time. There is a good discussion on the Apple message boards (which you’ll have to follow through to get the whole story) and a Technical Note which are interesting references. Unfortunately it’s not mentioned in any man pages though.
As it turns out, the absolute time units returned by mach_absolute_time() are not affected by CPU power saving, sleeping, etc. mach_absolute_time() is the base function from which all higher level timer related functions are implemented, for example, gettimeofday(2). So, how do we use mach_absolute_time() as a monotonic clock? Well, calling mach_absolute_time() before and after the event we want to measure is a start. Then we need to convert the difference to something useful. The return value from mach_absolute_time() can be converted to a more useful time unit by multiplying it by the fraction returned by mach_timebase_info(). This fraction will convert the absolute time into a time in nanoseconds. Armed with this, we can write some code that converts a difference into the familiar struct timespec:
#include <mach/mach_time.h>
#include <time.h>
#include <stdio.h>
void mach_absolute_difference(uint64_t end, uint64_t start, struct timespec *tp) {
uint64_t difference = end - start;
static mach_timebase_info_data_t info = {0,0};
if (info.denom == 0)
mach_timebase_info(&info);
uint64_t elapsednano = difference * (info.numer / info.denom);
tp->tv_sec = elapsednano * 1e-9;
tp->tv_nsec = elapsednano - (tp->tv_sec * 1e9);
}
int main(int argc, char *argv[]) {
uint64_t start,end;
struct timespec tp;
start = mach_absolute_time();
sleep(1);
end = mach_absolute_time();
mach_absolute_difference(end, start, &tp);
printf("%lu seconds, %lu nanoseconds\n", tp.tv_sec, tp.tv_nsec);
return 0;
}
Running this code produces the output:
kenshin:~ scottr$ make time
cc time.c -o time
kenshin:~ scottr$ ./time
1 seconds, 130951 nanoseconds
The fraction returned by mach_timebase_info() does not appear to change as the processor scales, at least on this Intel mac 
I’ve done some rudimentary tests to make sure that time does increase monotonically when the system clock changes, when the machine goes to sleep, etc, and it all seems to work fine. If anyone out there with a Mac wants to test these theories please do and please get back to me with your results.
It’s a pity that Apple didn’t decide to implement clock_gettime(2) themselves. I guess we can hope that in a later version of Mac OS X it will be implemented but until then we apear to be stuck with this workaround.
January 19th, 2009
The goal of this article is to document the process of setting up a basic KVM instance the hard way. That is, without using GUI tools, magic scripts, VNC’d installers, etc.
Pretty much all of the KVM guides I’ve seen assume you’re sitting at the physical box you’re deploying the VMs on and have access to the local display (i.e. they use GUI tools). Or they assume you just want a magic script to do it all for you. Or they assume you want to sit there and click through the debian-installer over a VNC session.
None of those options sound particularly fun or interesting. Below is a step-by-step guide to getting a KVM instance running the hard way. Most of the information can actually be found by pulling apart Hardy’s ubuntu-vm-builder script. I’m using Debian Lenny as Etch doesn’t have some of the necessary tools, for example kpartx for mapping partitions on a loopback device. Also we assume a 64-bit host and guest, though it should be fairly obvious how to use other numbers of bits. I decided to document the process mainly as a reference, but also as an education in the underlying process.
Let’s begin. First, we need a disk image to work with. Create a 5GB raw image using qemu-img:
$ qemu-img create -f raw lenny-base.raw 5G
Now, create a loopback device for it:
# losetup /dev/loop0 lenny-base.raw
Partition the loopback device using fdisk. I use a single primary partition in this article.
# fdisk /dev/loop0
Now we need to create device-mapper entries for each of the partitions on the loopback device:
# kpartx -a /dev/loop0
If you made a single partition on /dev/loop0, there will now be a device-mapper block device at /dev/mapper/loop0p1, which you can go ahead and make a filesystem on and bootstrap to whatever flavour of Debian/Ubuntu you’d like. You’ll also want to remember the UUID of the root filesystem for later. For example,
# mke2fs -j /dev/mapper/loop0p1
# vol_id --uuid /dev/mapper/loop0p1 > target.uuid
# mkdir /mnt/target
# mount /dev/mapper/loop0p1 /mnt/target
# debootstrap lenny /mnt/target http://ftp.nz.debian.org/debian
At this point, the bootstrapped filesystem will need some manual setting up. In particular you’ll need to
- Set up /etc/hostname
- Set up /etc/hosts
- Set up /etc/fstab (you’ll want to use the UUID you saved before)
- Enable serial getty in /etc/inittab (important, we’ll use this for initial login)
Copy the following into the target’s /etc/kernel-img.conf:
do_symlinks = yes
relative_links = yes
do_bootfloppy = no
do_initrd = yes
link_in_boot = no
postinst_hook = update-grub
postrm_hook = update-grub
do_bootloader = no
Now we need to install a kernel and set up the boot-loader.
# chroot /mnt/target
target # apt-get install linux-image-amd64 grub
target # mkdir -p /boot/grub
target # cp /usr/lib/grub/x86_64-pc/* /boot/grub
Exit from the target’s chroot. Now we’re back in the host, we need to install grub into the MBR of the disk image. You’ll need that UUID for the root filesystem from before. This step requires the host’s /dev to be bind-mounted into the target’s filesystem
# mount --bind /dev /mnt/target/dev
# echo "(hd0) lenny-base.raw" >> device.map
# grub --device-map=device.map
grub>root (hd0,0)
grub>setup (hd0)
grub>quit
# echo "(hd0) UUID=UUID of target root fs goes here" >> /mnt/target/boot/grub/device.map
# chroot /mnt/target
target # update-grub
update-grub will have written a basic menu.lst, but because it’s using the host’s /dev it will be pointing to the wrong place. Edit the target’s /boot/grub/menu.lst to use the UUID of the filesystem and not use the loop0 device. So, open up the target’s /boot/grub/menu.lst, search for the line:
# kopt_2_6 root=/dev/mapper/loop0p1 ro
and replace /dev/mapper/loop0p1 with
UUID=the uuid of the root filesystem
so it will look something like (make sure the # is still at the start of the line):
# kopt_2_6 root=UUID=81af6388-cca5-4bf2-99dc-a47c81c00445 ro
Also, replace the line groot=(loop0p1) with groot=(hd0,0). Again, it’s “commented out”. Now we need to update grub again.
# chroot /mnt/target
target # update-grub
target # exit
Almost done… At this point check that you’ve enabled the serial getty in the target’s /etc/inittab file as we’re going to boot the VM and use the serial console to do the initial login. Of course, you could install SSH in the chroot, set up networking and forget about the serial console, but it’s interesting none the less. The other alternative is to use VNC to connect to the console, but that’s the easy way out, though you will get boot messages, so if something goes wrong you’ll get to see why.
Unmount everything:
# umount /mnt/target/dev
# umount /mnt/target
# kpartx -d /dev/loop0
# losetup -d /dev/loop0
Now boot your shiny new VM:
# kvm -nographic -serial pty -drive file=lenny-base.raw,if=virtio,index=0,boot=on -daemonize
If all goes well you’ll see something like:
char device redirected to /dev/pts/10
Use minicom to connect to that pseudo-terminal and login to your new VM. Done! Sure it would have been easier if you’d just used a script or a graphical tool, but we got there in the end.
At this point the VM isn’t overly useful without networking, but there’s plenty of documentation in the qemu man pages about the options to enable a virtual NIC. There’s also options for changing the amount of RAM the guest is allocated, the number of CPUs, virtual disks, etc. Go RTFM.
Another option from here is to create a libvirt XML description of your VM and use virsh to manage it. This makes networking and management a bit easier, but isn’t necessary.
Enjoy!
August 28th, 2008
A few days ago I received my copy of “Ghosts” in the mail. I paid $10USD about a month ago and got the FLACs that day and have been listening to them ever since. Having the physical CDs now is a nice bonus – in fact, I haven’t even bothered to take them out of the shrink-wrap plastic You might remember that “Ghosts” was released under a Creative Commons license and the MP3 versions were available for free (legitimately) via Bittorrent. Paying a bit extra got you the physical CDs (or Blu-ray or vinyl depending on how much you wanted to spend). “Ghosts” was released independent of any major label with no advertising yet the album was a huge success for Nine Inch Nails.
So, I was having a kick around musicbrainz and noticed a NIN release I hadn’t heard of – “The Slip”. I went to nin.com and this is what I found:
Click HERE to get the new full-length nine inch nails record: the slip (thank you for your continued and loyal support over the years – this one’s on me)
A couple of clicks later and I’m downloading FLACs of a brand new NIN album via Bittorrent for free and contemplating whether I want to spend 1.2GB of my monthly data cap on the 24kbit/96kHz WAV files So, if you’re a NIN fan, join the swarm!
It’s a great time to be a Nine Inch Nails fan.
May 9th, 2008
On the weekend Emily and I decided that we needed to do more outdoorsy stuff, so we went and found a nice little walk on Mt. Pirongia, just out of Hamilton. We did the “Mangakara Nature Walk“, which is a loop through some native bush and crosses the Mangakara stream. It took us about an hour which included a stop of about twenty minutes for a picnic by the stream – how quaint. The walk itself was very easy and the track was well-formed the entire way. The scenery was stunning – apparently that part of the forest is pretty much pristine native bush as it has never been cleared.
The plan is to make our way through the various walks and then move on to something a little more challenging. Eventually I’d like to take Emily on the Tongariro Northern Crossing which was part of a three-day hike I did when I was in high-school.
Photos on flickr as I can’t seem to get this flickr plugin working 
October 29th, 2007
Leopard now comes with a built-in SSH agent. The really nice thing about it is that it integrates with your user’s Keychain. So, the first time you try to unlock your SSH key a dialog will appear asking you for its password along with an option to save that password in your Keychain.
On Tiger I was using SSHKeychain to achieve this, but it had a nasty bug where it would randomly start to consume 100% of a CPU. This chewed through my Macbook Pro’s battery, which was a pain. If you’ve been using a third party SSH agent and want to switch to the built-in agent, make sure to check that you’re not manually setting the SSH_AUTH_SOCK environment variable, which is something I had to do to get SSHKeychain working.
If launch-services is managing your SSH agent, it should look something like:
kenshin:~ scottr$ echo $SSH_AUTH_SOCK
/tmp/launch-fTiPvL/Listeners
Otherwise, check your various profile settings, and check to make sure your third party agent isn’t set as a launch item. You’ll have to log out for this to take effect. Once launch-services is managing your SSH_AUTH_SOCK, logging into OS X will unlock your keychain and allow the ssh-agent to unlock your SSH keys without having to enter another password.
October 28th, 2007
I installed Leopard last night and as I was browsing my local network I noticed something kinda funny… apparently this is what a Windows PC looks like:
October 27th, 2007
I’m sure that no-one has noticed that I’ve been fairly silent on the blogging front for a while. I took a three month break from the Ph.D to do some work for Cambridge Silicon Radio. The experience working on a real-world project was great and the project itself was both interesting and challenging.
I am however looking forward to getting back into the Ph.D work. I’ve still got a week or so before the Ph.D kicks back in so at the moment I’m doing some driver work for RuralLink – specifically getting MadWiFi working better on the CPE/AP devices.
I spent a week or so before the CSR work started looking into performance improvements for MadWiFi. After spending quite a bit of time with oprofile I found a couple of areas in the driver which were causing a large number of PCI transactions to take place unnecessarily. Now, on a laptop or desktop platform this didn’t really make much difference. On an already resource-starved platform such as the Soekris 4526 however, this was resulting in some pretty significant overhead. A couple of patches to MadWiFi later (a couple merged upstream already, one that’s a bit more of a hack specific to our needs) and we’re seeing some much nicer throughput numbers. Off the top of my head, we went from being able to bridge about 9-10 Mbit/s of traffic over wireless through the wired ethernet to about ~15 Mbit/s.
The other neat hack we did was to create a transparent wireless bridge by hacking the ad-hoc demo mode to use 4-address 802.11 frames. This could already be done in other modes, but we really like ad-hoc demo due to its utter simplicity – no associations, no beacons, nothing – just passing frames.
Right now we’re working on implementing our own rate control algorithm. We seem to run into far too many problems on our networks with rate control and Perry came up with a neat idea – as is his wont – so we’re running with it. At the same time we’re looking at using it as a chance to collect large amounts of performance data to give us some deeper knowledge as to what’s going on on our networks. Hopefully lots more info on that soon.
At some point in the (very) near future I need to start thinking about the Ph.D again – I’m starting to think that I should be putting more of a measurement focus into it, but I need to nail down a few ideas first. And maybe play a bit of Guitar Hero as well 
August 9th, 2007
I was playing with setting up bind for my local network at home yesterday and forgot a semi-colon at the end of the localdomain zone. Of course, I’d removed localhost and mugen (the name of the machine I was using) from /etc/hosts so that I could test bind. Restart bind, ping mugen, fail. Oh well… sudo vim /etc/bind/named.conf… sudo can’t look up mugen using gethostbyname(). Shit. No sudo for me. No root user either. Eventually fixed by connecting a monitor and keyboard and starting in single user mode.
Moral of the story? Don’t screw up your resolver if you like having sudo.
March 1st, 2007
Previous Posts