OS Kernel Hacks

A Comparison of Solaris, Linux, and FreeBSD Kernels at OpenSolaris.org

2005-10-17T03:03:00.000-04:00

The article at OpenSolaris.com not only discusses three major kernels: solaris, linux, and freebsd, but also shows a list of pointers to resources of these systems.

Worth a read!

Windows 2003 TCP/IP Implementation Details

2005-07-14T10:38:00.000-04:00

While browsing the MSDNAA website, I came across this 116-page word document of Windows 2003 TCP/IP implementation details. I think this is by far the most detailed explanation of Windows TCP/IP - you might find a chapter of windows networking in the "Microsoft Windows Internal" book by Mark Russinovich and David Solomon, but it is very high-level and does not provide this much of details.

User-Level Spin Locks - Threads, Processes & IPC

2005-06-29T18:13:00.000-04:00

Spin locks are used by SMP OS kernels for kernel thread (control path) synchonization. It is a busy-waiting style meaning that the thread trying to acquire the spin lock will constantly poll for the availability of the lock. Therefore thread holding a spin lock should not do a lot of things.

Here is an interesting post
The Code Project - User-Level Spin Locks - Threads, Processes & IPC about user level spin lock.

ACM Queue - The Reincarnation of Virtual Machines -

2005-06-23T07:21:00.000-04:00

Mendel Rosenblum, Co-Founder of VMware was interviewed by ACM Queue talking about ACM Queue - The Reincarnation of Virtual Machines - Like the best of the 1970s and 1980s, VMs have returned to the scene -- and they're a lot cooler than polyester pants.

The story gives a clear overview of the VM landscape. Considering the fact that the VM market is poised for a big battle between VMWare, Microsoft Virtual PC, and Xen, and VM's technical closeness with network emulators, this is indeed an exciting field I need to follow.

Windows NT Native API

2005-05-25T23:18:00.000-04:00

One of the authors of the well-known book "Windows Internals" talks about Windows NT native APIs and other related topics such as Win32 DLLs, kernel/user mode, etc.

The Native API is equivalent to the system call interface on traditional monolithic operating systems such as most UNIXes. On most UNIXes, however, the system call interface is well documented and is generally available for use by standard applications.

There is a nice picture showing the architecture of Windows NT DLLs and system services.

trickle: userland bandwidth shaper

2005-04-29T13:06:00.000-04:00

The networking session of this year's USENIX has a paper talking about a userland bandwidth shaper created by Google engineer Marius Aamodt Eriksen (need login to download the paper, but the source code is available here).

Form Trickle's man page:

trickle is a userspace bandwidth manager.  Currently, trickle supports
the shaping of any SOCK_STREAM (see socket(2)) connection established
via the socket(2) interface.  Furthermore, trickle will not work
with statically linked executables, nor with setuid(2) executables. 
trickle is highly configurable; download and upload rates can be
set separately, or in an aggregate fashion.

The trickle daemon, an LD_PRELOAD module, works by imposing a rate cap on the bandwidth (upload, download, or both) of a process or group of processes using socket connections.

LD_PRELOAD is a way to intercept dynamic function called. You set the environment variable to your own shared library, in which you define your own functions.

User Model Linux for Wireless Network Emulation

2005-04-26T11:40:00.000-04:00

USENIX'05 has an emulation track of 3 papers, one of which, "Running virtualized native drivers in User Mode Linux", proposes a method of using User Mode Linux along with virtual wireless network interfaces for wireless network emulation. It uses the Hostap driver in the guest OS to communicate the virtual wireless interface via TCP. While the system can be used to test ad hoc routing or other protocols, it may be only useful when the wireless network (wireless LAN, for example) is small. Good thing is, there is no need to modify the protocol implementation because it is executed in a guest OS.

Linux Netfilter Revisit

2005-04-18T17:38:00.000-04:00

The netfilter architecture in Linux kernel 2.4 and above makes packet filtering in kernel IP stack much easier: what you need to do is implementing your "hooks" and placing it into specific places in the kernel stack. Below is picture in Paul "Rusty" Russell's 2000 Linux Journal article "Writing Modules for Netfilter".

Note that connection tracking is done in PRE_ROUTE and LOCAL_OUT, while NAT is done in PRE_ROUTE (destination NAT, such as port forwarding, for incoming connections), LOCAL_OUT (destination NAT), and POST_ROUTE (source NAT including masquerading for outgoing connections).

A very nice figure of 2.4 kernel IP handling is here

Network Emulation: Multiple Network Stacks in One Kernel

2005-04-15T15:14:00.000-04:00

While looking into the increasingly popular virtual machine technology, I realized my previous work on network emulation could be categorized into this broad area.

To be exact, "pure" machine virtualization refers to allowing for multiple complete OSes to run top of a middle layer (always called Virtual Machine Manager VMM). Systems falling into this class are VMWare, Microsoft Virtual PC, and User Mode Linux, among others.

But in the domain of network emulation/simulation, we don't really need to virtualize everything a general purpose OS will use. Instead, we may just focus on the network protocol stack in the kernel, and protocol instances.

IMUNES is such a multi-net-stack emulator. Based on a FreeBSD kernel, IMUNES adds a vnet kernel structure to maintain global and static symbols used by the network stack code for each virtual node of the underlying cloned stack. So within each virtual node, a process (for example, a routing daemon) will only see emulated interfaces, routing tables, etc, previously configured for the virtual node. The way to bind a process to a virtual node is done by modifying process control block of the kernel.

The creation of a virtual topology using multiple virtual nodes within a kernel is enabled by the netgraph framework in the FreeBSD kernel. Another way to build virtual links is to use virtual network interfaces. In both cases, packets are handed over between virtual nodes only by reference (the socket buffer sk_buf).

In IMUNES, queueing and traffic shaping are provided by a shaper called ng_pipe, a special netgraph node. Emulated network conditions include delay, bandwidth, and bit-error-rate.

As you may have already figured out, this approach performs much better than pure virtual machine based network emulation and user-space based virtual node in terms of supporting long route path with high throughput. The downside is apparently the heavy modification made to the FreeBSD kernel.

To dig further, read the IMUNES USENIX paper.

A very good summary of software tools for networking is here (IEEE COMSOC).

My outdated network emulation page @MSU has a list of emulators. I really need to update it.....

Running Linux 2.6.11 On Dell Inspiron 5100

2005-04-04T00:23:00.000-04:00

This weekend I decided to make my Dell Inspiron 5100 dual-boot for both Windows XP and Linux. I already have Windows there working fine. Based on the fact that I have Fedora Core II CDs burned last year when I worked for Nextel, I chose to use Fedora but with latest kernel. At least 16 hours have been taken for this job. Be patient.

Section 0: Create a partition using ntfsresize in Knoppix, the well-known single-CD Linux system. This allows resizing an NTFS partition (the laptop only has one disk). The guide to this step is here. Now I have a 10G partition for Linux.

Section 1: Big trouble with the CD drive on my Inspirion 5100. It seems when it continues to read for sometime (let's say 1 hour), the CD drive will ALWAYS report read error as it is getting very hot. Thus there is no way to have a pretty complete installation of Fedora; I have to wait until it cools down. I ended up using my old Redhat 9 3-CD set, and chose "minimal" package selection - No KDE or GNOME, no kernel source, etc. Eventually I got a Redhat 9 with kernel 2.4.20 on my laptop. Now I wanted to make the network work.

Section 2: Old kernels (2.4.x) do not have support for the built-in Broadcom 4401 Ethernet interface in Dell Insprion. But Broadcom provides a Linux driver here. Download and compile, follow the readme, and it worked.

Section 3: Grab the 2.6.11 kernel from kernel.org. A good article about this step is here. The 2.6 kernel changed several modules names, as well as in-kernel module loader interfaces. So I must download the module-init-tools and replaced those "modprobe", "insmod" stuff with the new ones. The 2.6 kernel has bcm4400 support, and the module is named "b44". A kernel configuration is for the bcm 4400 support. After compilation, as the article suggested, I modified modprobe and rc.sysinit for usb mouse, etc. Then modified grub. Rebooted.

Section 4: Make the build-in TrueMobile (broadcom 1300) work. After some google search, I figured out (ndiswrapper + Dell TrueMobile driver) is the solution. Downloaded both of them and followed the installation guide. At some point, the "make" did not proceed because my system does not have the docbook2html tool. Then I configued the wlan0 to be automatically up and hook to my access point, with proper IP setting. Then in rc.local, added a default gateway through my desktop proxy server and bring down the built-in ethernet interface (eth0), which will automatically remove the routes associated with it in the routing table.

Section 5: Get apt, kde, firefox, etc. Installing rpms onto a Linux system always ends up with dependency hell. Apt makes this process extremely easire. I also tried Yum, but gave up later.

Section 6: Since I use ssh a lot from the laptop, I don't want to always use my gateway machine as the intermediate hop. I want to directly ssh to a remote box. The solution is to use connect.c (created by Shun-ichi Goto) with openssh.

Lessions learned:
a. Never underestimate the time you're gonna take to do a Linux installation on a laptop. You need a lot of time searching online and playing directly with packages, sometime you have to hack it your self.

b. RPM dependency is a hell. Because my CD drive does not always work, getting needed rpms for a special package is a pain in the neck. Get your network ready and use apt as sooner as possible.

c. Dell Inspiron is hot! (after the CD drive spins for some time).

Zero-Copy in Linux Kernel

2005-04-03T17:26:00.000-04:00

Found a (supposedly) outdated doc on Zero Copy in Linux Kernel written by Dragan Stancevic. The article clearly explains how send() and "sendfile()" differ from kernel's perspective.

Using sendfile(socket, file, len), Data from a disk is first DMA-copied into kernel buffer, then the kernel socket buffer only collects descriptors (not the data!) of those skbs. Eventually the NIC performs DMA-gather over the socket buffer(skb descriptors) and the kernel buffer(data) into NIC's transmission ring buffer. Thus this operation (zero-copy in kernel) requires the NIC support scatter-gather DMA.

Windows Virtual Memory

2005-03-25T15:34:00.000-05:00

In light of a big project with Microsoft, I started to collect Windows OS resources. Wong's article is definitely a must-read for anyone interested with Windows virtual memory management.

Think you are pretty clear with Microsoft's VM?

Question: what is the difference between a swap file and a page file?

The differences lie in how the process is being swapped and how the free space is being used by other processes.

Read-Copy Update Mutex in Linux Kernel

2005-03-24T20:54:00.000-05:00

I ran into a nice article talking about Read-Copy Update at LSE sourceforge site (Linux Scalability Effort). RCP differs from traidational spin-lock mutex (spin-waiting) in that:

Read-Copy Update is one ... mutual exclusion method where readers (threads trying to access, but not modify the data) can access the shared data without acquiring any conventional lock. The writers (threads that update the data) however, have to use a special callback scheme to update the data. They update all the global references to the updated data with a new copy and use the callback scheme to free the old copy after all the CPUs have lost local references to it by going through a quiescent state (like a context switch).

The overhead of spin waiting could be high when multiple threads are accessing the same route cache or routing table, for example. As you can see, the "write" is more expensive because it has to make sure processors have lost reference to the old data. The implementation can be downloaded here.

As a sidenote, semaphores in Linux are sleeping locks as opposed to spnning locks. So semaphores should be used when lock-held time is long considering the overhead of putting thread in sleep and waking it up later.

At this point(03/24/2005), the latest kernel may have already incorporated this scheme or even better scheme to replace spin locks. I will check it out when I get a chance.