Thread safety

Before I start with thread safety, evolving design, if something can be improved don't be lazy.
Now I remembered that GCC supports 128 bit integers and that Fibonacci numbers can be calculated up to forty digits. There is problem with printing those 128 bit integers but somebody already offered utility function to convert them to string, that was Perkins . I only added zero case to his solution.

#include <stdio.h> #include <stdlib.h> void uint128_to_str_iter(__uint128_t n, char *out,int firstiter){ static int offset=0; if (firstiter){ offset=0; } if (n == 0) { return; } uint128_to_str_iter(n/10,out,0); out[offset++]=n%10+0x30; } char* uint128_to_str(__uint128_t n){ if(!n) { char * c = (char*)calloc(sizeof(char),2); c[0] = '0'; return c; } char *out=calloc(sizeof(char),40); uint128_to_str_iter(n, out, 1); return out; } __uint128_t * allocate(uint i){ __uint128_t* res = (__uint128_t*)malloc(2 * sizeof(__uint128_t)); res[0] = 1; res[1] = i; return res; } __uint128_t * recurse(uint i){ if(i<2) return allocate(i); __uint128_t * t = recurse(i/2); __uint128_t t0 = t[0]*t[0]+t[1]*t[1]; t[1] = t[1]*((t[0]<<1)-t[1]); t[0] = t0; if(i%2){ t0 = t[0]+t[1]; t[1] = t[0]; t[0] = t0; } return t; } __uint128_t square(uint n){ __uint128_t * result = recurse(n); __uint128_t r = result[1]; free(result); return r; } uint main(){ uint i; for(i=0; i<187; i++){ char * str = uint128_to_str(square(i)); printf("F(%d) = %s\n", i, str); free(str); } return 0; }

Now we can go up to 186th Fibonacci number without overflow.

Threads

There is few buzz words which people are using in job ads, related to threads, but usually they fail to define them. For example multithreading, concurrency, thread safety, reentrant function and similar.
What is reentrant function or thread safe function? That would be such function that does not use statically allocated or global variables and result depends only on input arguments. For example:

int increase(int i){ static counter = 0; counter += i; return counter; }

is not reentrant or threadsafe. If more than one thread calls that function in the same time, that is concurrency, it will produce unpredictable result. Even if it is called sequentially result will be influenced by previous calls, possibly from different thread. We are on Linux and we are using POSIX threads. So, here is example where two threads are calling nonreentrant function:

#include <stdio.h> #include <stdlib.h> #include <pthread.h> int increase(int i){ static int counter = 0; counter += i; return counter; } void * runnable1(void *arg){ int i; for(i = 1; i < 5; i++){ printf("thread 1 call %d = %d, expecting %d\n", i, increase(2), 2*i); } return((void *)1); } void * runnable2(void *arg) { int i; for(i = 1; i < 5; i++){ printf("thread 2 call %d = %d, expecting %d\n", i, increase(3), 3*i); } pthread_exit((void *)2); } int main(void) { int error; pthread_t tid1, tid2; void * exitCode; error = pthread_create(&tid1, NULL, runnable1, NULL); if (error != 0){ perror("create thread 1 failed"); exit(1); } error = pthread_create(&tid2, NULL, runnable2, NULL); if (error != 0){ perror("create thread 2 failed"); exit(1); } error = pthread_join(tid1, &exitCode); if (error != 0){ perror("join thread 1 failed"); exit(1); } printf("thread 1 exit code %ld\n", (long)exitCode); error = pthread_join(tid2, &exitCode); if (error != 0){ perror("join thread 2 failed"); exit(1); } printf("thread 2 exit code %ld\n", (long)exitCode); return 0; }

To compile it I used:

gcc -o notreentrant -g -gdwarf-2 notreentrant.c -pthread

That -gdwarf-2 story is distraction, I am using gcc version 4.9.2 built from source on old Mint based on Ubuntu 12.04 and new gcc outputs by default debug info which gdb doesn’t understand. If you just built new gcc and gdb doesn't work as expected, that is cure. Linker switch -pthread is required.
Example output from execution looks like this:

thread 1 call 1 = 2, expecting 2
thread 1 call 2 = 7, expecting 4
thread 1 call 3 = 9, expecting 6
thread 1 call 4 = 11, expecting 8
thread 2 call 1 = 5, expecting 3
thread 2 call 2 = 14, expecting 6
thread 2 call 3 = 17, expecting 9
thread 2 call 4 = 20, expecting 12
thread 1 exit code 1
thread 2 exit code 2

How do we remedy that? We make increase reentrant or thread safe:

int increase(int i){ static __thread int counter = 0; counter += i; return counter; }

We requested thread local storage, available since kernel 2.6 and supported by gcc 3.3 and higher. When thread terminates and goes out of scope, local thread storage does to. We could make function reentrant via using thread specific data, but that is much more code, maybe next time.