Sub.jam

Links
Experiments with Kernel 2.6 on a Hyperthreaded Pentium 4
Spinlocks and Semaphore
GCC-Inline-Assembly-HOWTO
Inline assembly for x86 in Linux
POSIX Threads Programming
Three classic examples in concurrency

Atomic operations
A simple "atomic increment and decrement" implementation. Adopted from Experiments with Kernel 2.6 on a Hyperthreaded Pentium 4 and Linux kernel source.

/* atomic.h */
static inline void atomic_inc(volatile int *addr)
{
       __asm__ __volatile__(
               "lock; incl %0\n\t"
               :"=m"(*addr)
               :"m"(*addr)
       );
}
  
static inline void atomic_dec(volatile int *addr)
{
      __asm__ __volatile__(
              "lock; decl %0\n\t"
              :"=m"(*addr)
              :"m"(*addr)
      );
}

Spinlocks
"A spin lock is a lock that can be held by at most one thread of execution. If a thread of execution attempts to acquire a spin lock while it is contended (already held), the thread busy loops - spins - waiting for the lock to become available. If the lock is not contended, the thread can immediately acquire the lock and continue."
--- From "Linux Kernel Development", page 137

The implementation of spinlocks is architecture dependent. Here is an example implementation from Professor Giorgio Ingargiola at Temple University.

#ifndef _SPINLOCK_H_
#define _SPINLOCK_H_

/* This code was extracted from the Linux Kernel */

#ifdef __SMP__
#define LOCK_PREFIX "lock ; "
#else
#define LOCK_PREFIX ""
#endif
struct __dummy { unsigned long a[100]; };
#define ADDR (*(volatile struct __dummy *) addr)


extern __inline__ int test_and_set_bit(int nr, volatile void * addr)
{
         int oldbit;
 
         __asm__ __volatile__( LOCK_PREFIX
                 "btsl %2,%1\n\tsbbl %0,%0"
                 :"=r" (oldbit),"=m" (ADDR)
                 :"Ir" (nr));
         return oldbit;
 }

/* This code was extracted from the Linux Kernel */

/* This implementation of spinlocks does not disable interrupts, so
   there is a danger of deadlocks. It uses busy waiting. It can be 
   used for mutual exclusion between processes. 
   The variable x below must be a pointer to a location in memory
   shared between the communicating processes
 */

#define spin_lock_init(x) {*x = 0;}
#define spin_lock(x) {while (test_and_set_bit(0,x));}
#define spin_unlock(x) {*x = 0;}

#endif

Semaphore
"Semaphores in Linux are sleeping locks. When a task attempts to acquire a semaphore that is already held, the semaphore places onto a wait queue and puts the task to sleep. The processor is then free to execute other code. When the processes holding the semaphore release the lock, one of the tasks on the wait queue is awakened so that it can then acquire the semaphore"
--- From "Linux Kernel Development", page 143


Test Programs
Adopted from book "Beginning Linux Programming".

/* concurrency example with atomic operation*/
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include "atomic.h"

#define NTHREADS 5
#define NLOOPS 100000

void* thread_function( void* arg );
int count = 0;

int main()
{
    pthread_t mythread[NTHREADS];
    printf( "Number of processors: %ld\n", 
             sysconf( _SC_NPROCESSORS_ONLN ) );
    printf( "Creating %d threads (each increments Count %d times)\n",
            NTHREADS, NLOOPS );

    int i;  
    for (i=0; i<NTHREADS; i++) {
        if (pthread_create( &mythread[i], NULL, thread_function, NULL)) {
            printf( "*** Error creating thread ***\n" );
            exit( -1 );
        }
    }

    for (i=0; i<NTHREADS; i++) {
        if (pthread_join( mythread[i], NULL )) {
            printf( "*** Error joining thread ***\n" );
            exit( -2 );
        }
    }

    printf( "count: %d (should be %d)\n", count, NTHREADS*NLOOPS );
    return 0;
}

void* thread_function( void* arg )
{
    int n;
    for (n=0; n<NLOOPS; n++) {
        atomic_inc(&count);
    }
    return NULL;
}

Links
Subject: [Phrack] Building Into The Linux Network Layer

Description
"OTP (Obscure Transport Protocol): The first one is really simple (and fun too), it works in a client-server paradigm, meaning that you need to have two modules loaded, one on the client and one on the server (duh). The client module catches every TCP packet with the SYN flag on and swaps it with a FIN flag. The server module does exactly the opposite, swaps the FIN for a SYN. I find this particularly fun since both sides behave like a regular connection is undergoing, but if you watch it on the wire it will seem totally absurd. This can also do the same for ports and source address. Let's look at an example taken right from the wire."
--- From [Phrack] Building Into The Linux Network Layer

Objective: modify the code for kernel version 2.6.26

Code

Notes
1. Re: Change In sk_buff structure in 2.6.22 kernel

sk_buff *skb;

//Access tcp header
tcp_hdr(skb)

//Access ip header
ip_hdr(skb)

2. [PATCH 13/16] net: Make the device list and device lookups per namespace.

char *name = "eth0";
struct net_device *d;
d = get_dev_by_name(&init_net, name);