15. The Threads group of Modules

This is the (non-POSIX) threads package, that uses the basic clone interface of the Linux-kernel.

Now, what is the difference between threads and processes? A process runs totaly isolated from the other processes in the Unix system, it concurrently request resources and is controled by the operating system such that it does no harm to the other processes. Interfaceing between processes is cost intensive performance wise.

A thread, on the other hand, is scheduled within the context of _one_ process, shares most (if not all) of its resources, and has to cooperate with the other threads in order to do no harm to whole thread group. Interfaceing between threads is very cheap performance wise, hence, using threads is what You should do when having _one_ application that needs to do work in parallel.

15.1 arch/linux/threads/lt-threads.c Information

This thread package does _NOT_ POSIX compatible threading. As its name says: it is a tiny fast alternative using Linux cloning. The aim was to avoid as much unnecessary sys_calls as possible. Locking is _NOT_ done via IPC semaphores, instead we use a user level atomic technique, when the resource is free, there will be no sys_call atall.

Each thread has its own 'Thread Control Block' (TCB) at the bottom of its stack. Hence to identify itself it doesn't need to go over getpid().

However, there are restrictions given by the technique used:

   - The total maximum number of threads is 27.
   - The size of the stack must be at power of 2 and is equal
     for all threads. It is not a problem to make the stack area huge,
     because only those pages actually used will be allocated (paged in)
     by the system. Though you will be estonished what /proc/<pid>/status
     is telling you about stack consumption, ... just ignore it;-)
   - You have to lock/unlock resource_libc when using non-reentrant parts
     of libc (malloc _is_ no-reentrant).
   - You must not use atexit, exit, _exit atall. instead use the techniques
     and functions supplied by lt-threads.

Maintainers:

Hans Lermen <lermen@fgan.de>

15.2 Functions in arch/linux/threads/lt-threads.c

These are the functions defined in arch/linux/threads/lt-threads.c.

Making room on the stack

static char *force_stack_expand(unsigned long address)

   1.   You are forced to put the stacks into the heap (below 1st giga)
        hence it is less protected against overwriting then normally.
   2.   The 1 giga stack address space isn't used any more, and
        you may have problems with address space, on huge programs
        that use huge arrays (data bases, matrices).

Setting User Space Stack limits

int make_stack_unlimited(int drop_privs)

Queuing tools

These two functions have to be used when maintaining queues of various sorts. You may cast to your private queue entry structure as long as the top of this structure fits `struct queue_entry':

        struct queue_entry {
                struct queue_entry *next;
                struct queue_entry *last;
        };

void append_to_queue(struct queue_entry *existing, struct queue_entry *new)

void remove_from_queue(struct queue_entry *entry)

Avoiding Libc reentrancy Problems

Because all threads share the same VM, libc needs to be reentrant. This isn't the case for a lot of functions ( malloc() is one on them). Though newer libc can be made reentrant (needs the -D_REENTRANT on compilation of _each_ object file), this feature has a performance lost due to the overhead that applies to evry libc call. As we exactly know _when_ we come into trouble with libc, the faster (and IMHO) better solution is to to take care of this at application level.

For this to accomplish we have to put a (un)lock_resource(resource_libc) bracket around those involved libc functions. The most frequently used ones are offered by the threads package, including such locking. Some of those are:

void *locked_malloc(size_t size)

void locked_free(void *p)

getting page aligned memory from the heap

If you need a page aligned piece of memory, you usualy would use valloc(). However, you can't free that memory later. For this purpose you may use the below functions, which are put on top of malloc()/free().

void *page_malloc(size_t size)

void page_free(void *ptr)

Name List Tools

The below functions are used for handling small name lists (you may call it directories). All major resources in lt-threads are accessable also by their names, as they are defined on creation time. Especially when it comes to link between different processes (thread cores) and different maschines, we look up the resources (such as mailboxes, threads, services) via name lists.

The global structures used for building namelists (as defined in lt-threads.h) are:

struct name_list_entry {
        char *name;
        union {
                void *p;
                struct tcb *tcb;
                struct lock_struct *lock;
                struct mbox *mbox;
                int idata;
        } u;
};

struct name_list {
        int size;
        int count;
        struct name_list_entry list[0];
};

struct name_list *create_namelist(int numentries)

int lookup_name_list(struct name_list *list, char *name)

void * get_name_list_value(struct name_list *list, char *name)

int set_name_list_value(struct name_list *list, char *name, void *value)

int insert_name_list_entry(struct name_list *list, char *name, void *value)

int delete_name_list_entry(struct name_list *list, char *name)

Exiting a thread

Once the threading system is setup, you never should use exit() or _exit(). Instead use exit_thread(0) to exit the running thread, exit_thread(tcb) to kill an other thread and exit_all() to terminate all threads.

void exit_thread(struct tcb *tcb)

void exit_all(int exit_code)

Suspending / resuming a thread

When a thread has nothing valuable to do (e.g. it is waiting for some event to happen), it should go asleep. The following function supends the current running thread:

void suspend_thread()

void resume_thread(struct tcb *tcb)

 Note: we use our own usleep to avoid
  A) problems with signal stuff
  B) problems with libc

void thread_usleep(int useconds)

Locking Resources

The below locking scheme implements userspace semaphores, that in the most frequent cases do _not_ enter the kernel. ( doesn't use IPC or kernel semphores ) It depends on the atomic_reserv/free() algorithme defined above and won't work with other locking strategies, that cannot `reserve and queue' with _one_ atomic operation.

The win of this algorithme is _much_ more speed, the disadvantage is that you can't have more then 27 threads. (though, on 64-bit machines it could be 58 threads)

All locking function rely on the following structure

struct lock_struct {
        int used;
        int id;
        int owner_count;
        struct tcb *owner;
        int successor_id;
};

struct lock_struct *create_resource(char *name)

void lock_resource(struct lock_struct *lock)

void unlock_resource(struct lock_struct *lock)

void transfer_resource(struct lock_struct *lock, int successor_id)

Sending and receiving messages

A threading system without message transfer would be worthless. We have it ;-)

All messages can be send to `mailboxes', that were created before. The size of the message queue within a mailbox can be defined at creation time. When a sending thread hits a queue overflow in the mailbox, the sending thread is put asleep and queued for later to be awaken. When a receiving thread hits an empty mailbox, it also gets asleep. A sending thread on an empty mailbox awakens a sleeping receiver, A receiving thread on a full mailbox awakens a sleeping sender.

mbox_handle create_local_mailbox(char *name, int numentries)

mbox_handle get_mailbox(char *name)

mbox_handle get_mailbox_wait(char *name)

void sendmessage(mbox_handle mbx, struct msg *msg)

struct msg *receivemessage(mbox_handle mbx)

int mailbox_is_empty(mbox_handle mbx)

Creating (starting) a thread

Any thread can create child threads. You must pass the address of the function, that contains the thread's code and (optionaly) pass the thread a private parameter pointer.

struct tcb *create_thread(thread_function_type *thread_code, void *params)

`init_zero_thread()' makes the starting parent process behave as a normal thread and threfore this function call must come before any other thread related call. It initializes the thrreads system.

struct tcb *init_zero_thread(int stacksize)

pid_t threads_getpid(struct tcb *tcb)

Some debugging aids

To make your life a bit easier (and because GDB has problems debugging a thread group), here some usefull functions

int locked_printf( const char *fmt, ...)

void print_tcb(struct tcb *tcb)

void print_resource(struct lock_struct *lock)

void print_mbox(mbox_handle mbx)

15.3 include/lt-threads.h Information

15.4 Functions in include/lt-threads.h

These are the functions defined in include/lt-threads.h.

The thread itself

typedef void thread_function_type(void *params);

A thread's exit function

typedef void thread_exit_function_type(void);

Accessing a thread's TCB

All thread private data is on the stack, there may be private data allocated on the heap, but the pointers to those areas should be itself on the stack. As long as access happens within scope of the thread function itself (or within local functions within function) this needs no extra handling. However, calling an other function that needs to access thread private data may be a problem. This problem can be solved by putting all this data into a private structure and starting the thread by passing it a pointer to this structure. Now, within scope of the thread one has access to this pointer via.

 OWN_TCB->params;

Looping through all TCBs

It may be necessary to scan data of all running threads or doing something special like notifying e.t.c. To acomplish this you should use the macro FOR_ALL_TCB such as

 struct tcb *tcb;
 int id;
 FOR_ALL_TCB(id,tcb) {
    locked_printf("thread %d tcb is at address %p\n", id, tcb);
 }

Atomic inline Functions

This set of functions is mainly used within the threads package itself, however, you may find them usefull for your stuff too.

Below function atomically reserves 'resource' and queues ID. When the reservation was successfull (i.e. if 'resource' was -1 before) the function returns -1, otherwise '0'. Id must be a number in the range 0..27. In any case bit 'idnum' is set in resource. Due to the technique used for being atomic, only 27 of 32 bits in the integer can be used.

static __inline__ int atomic_reserv(int *resource, int id)

static __inline__ int atomic_free(int *resource, int id)

static __inline__ int get_lowest_waiting_id_from_resource(int resource)

static __inline__ int lt_atomic_inc(int *flag, int increment)

static __inline__ int lt_atomic_dec(int *flag, int decrement)

static __inline__ int atomic_bitset(void *addr, int bitnum)

static __inline__ int atomic_bitclear(void *addr, int bitnum)

Misc inline Functions

This set of functions is mainly used within the threads package itself, however, you may find them usefull for your stuff too.

search_lowest_bit returns the index of lowest bit set or -1, if not found `fieldsize' must be multiple of 32

static __inline__ int search_lowest_bit(void *addr, int fieldsize)

static __inline__ int roundup_to_power_of_2(int val)

15.5 Data Definitions in include/lt-threads.h

These are the structures and/or data defined in include/lt-threads.h.

TCB (Thread Control Block)

The TCB is the main data structure, that is unic to each thread. It alway is at bottom of the thread's stack and can be accessed using the OWN_TCB macro. This also is valid while in signal handlers.

Elements are:

• struct queue_entry link;
• pid_t pid;
• int tcb_id;
• int threadflags;
• struct tcb *parent;
• thread_function_type *thread_code;
• void *params;
• unsigned long stack_size;
• int suspend_count;
• char owning_locks[MAX_RESOURCES>>3];
• jmp_buf exit_jmpbuf;
• thread_exit_function_type *exit_func;
• int exit_code;
• uid_t uid, euid;
• gid_t gid, egid;