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.

C++ and pthreads on Linux

If one wants to use NDK and that is JNI on Android, sooner or later he will run into threading on Linux, yes Android is Linux. Pthreads is short for POSIX threads where POSIX is Portable Operating System Interface. Since they are portable they will work on Unix, Linux, FreeBSD, Mac and so on. Pthread is defined in pthread.h and represents set of C functions, structs and defs, to discover where it is you can execute from terminal:

$ locate pthread.h

If you have NDK installed you will see that pthread.h is part of it and that arch-arm version is significantly smaller than /usr/include/pthread.h one. To cut long story short we can do Hello World and see how it looks like:

extern "C" { #include <pthread.h> } #include <iostream> using namespace std; void* callback(void* arg){ cout << *(reinterpret_cast<string*>(arg)) << endl; return 0; } int main( void ){ pthread_t thread; string hello("Hello World!"); int res = pthread_create( &thread,NULL, callback,reinterpret_cast<void*>(&hello)); if (res != 0){ cout << "pthread_create failed" << endl; return 1; } res = pthread_join(thread,NULL); if (res != 0){ cout << "pthread_join failed" << endl; return 1; } cout << "that's all folks" << endl; return 0; }

It is quite simple, we declare thread function, thread itself and then we create thread and pass function pointer and argument in pthread_create. Later we join and exit. To compile it we do:

g++ -pthread simple.cpp -o simple

That -pthread switch is linking instruction. Now cout is not thread safe and we may want to use mutex to make printing to standard output safe.

extern "C" { #include <pthread.h> } #include<iostream> #define NTHREADS 8 using namespace std; pthread_mutex_t mutex; void* function(void* arg){ int index=*(static_cast<int*>(arg)); pthread_mutex_lock(&mutex); cout<<"Hello from thread "<<index<<endl; pthread_mutex_unlock(&mutex); return 0; } int main(){ pthread_mutex_init(&mutex,NULL); pthread_t threads[NTHREADS]; int thread_no[NTHREADS]; for(int i=0;i<NTHREADS;++i){ thread_no[i] = i; pthread_create(&threads[i],NULL,function,static_cast<void*>(&thread_no[i])); } for(int i=0;i<NTHREADS;++i) pthread_join(threads[i],NULL); pthread_mutex_destroy(&mutex); return 0; }

Now one can go and wrap pthread or mutex in class and make it easier to use. Only we need to be careful with that function pointer in pthread_create, that is C function and passing class method won’t work without some additional coding and static casting.
Finally we will take a look at pthread_key_create, which is recommended by Android documentation. Its signature is:

int pthread_key_create(pthread_key_t *key, void (*destructor)(void *));

That "destructor" should free resources taken by key when thread exits. Key itself is global variable but on thread level, sort of locally global. So here is example:

extern "C" { #include <pthread.h> #include <stdlib.h> #include <string.h> } #include <iostream> #include <string> #include <sstream> using namespace std; #define NTHREADS 4 pthread_key_t that_key; struct payload{ char* data; int size; } *load; void free_key(void* arg){ payload* s = (payload*)arg; free(s->data); free(s); } void* thread_func(void* param) { cout<<"in thread "<<pthread_self()<<endl; pthread_setspecific(that_key, param); payload* s = static_cast<payload*>(pthread_getspecific(that_key)); cout<<"thread_func, data is "<<s->data<<" and size is "<<s->size<<endl; return NULL; } int main(){ pthread_key_create(&that_key, free_key); pthread_t thread[NTHREADS]; int i; for(i=0;i<NTHREADS;i++){ load = (payload*)malloc(sizeof(payload)); string s("this is test string "); ostringstream o; o<<s<<i; load->size = o.str().size(); load->data = static_cast<char*>(malloc(sizeof(char)*(o.str().size()+1))); memcpy(load->data, static_cast<const void*>(o.str().c_str()), o.str().size()); pthread_create(&thread[i], NULL, thread_func, static_cast<void*>(load)); } for (i=0; i <NTHREADS; ++i) { pthread_join(thread[i], NULL); } pthread_key_delete(that_key); return 0; }

When you build it and execute it you will see that cout is not thread safe. If you want to wrap pthread in class, very good reading is Implementation and Usage of a Thread Pool based on POSIX Threads by Ronald Kriemann, sorry do not have link for it. Beside mutex, there are are condition variables and semaphores to help with concurrency issues. If you are going to fork process you may want to use System V semaphores instead of pthread semaphores. Finally for any serious implementation of pthread_key_create you need to look at pthread_once_t.

Tutorial part 3

In this part we are going to take a look at AsyncTask which is light-weight framework intended to save programmers from concurrency traps and handling of Java threads.

AsyncTask

Most important thing is AsyncTask is intended to be used on UI thread, so do not try to use it elsewhere. Signature is android.os.AsyncTask and you can use them or ignore them and replace unused ones with Void. If you are planning to pass array of strings as parameters and not use progress or result than it becomes android.os.AsyncTask.
There are four commonly used and overridden methods:

protected void onPreExecute ()
protected abstract Result doInBackground (Params... params)
protected void onProgressUpdate (Progress... values)
protected void onPostExecute (Result result)

obviously only doInBacground is compulsory to override and that is only one which is not executing on UI thread. Typical implementation looks like this:

private class FetchItemsTask extends AsyncTask {
    @Override
    protected void onPreExecute() {
        super.onPreExecute();
        progressDialog.setMessage("Downloading. Please wait...");
        progressDialog.show();
    }
    @Override
    protected Void doInBackground(Void... params) {
        do some heavy I/O work here
        return null;
    }
    @Override
    protected void onPostExecute(Void result) {
        pass to UI result of work here
        progressDialog.dismiss();
    }
}

Usually it is declared as inner class inside Activity and we have instance of ProgressDialog accessible.
It is not full size threading framework, it should be used as suggested to do lengthy I/O operations. That lengthy is few seconds not few minutes. So good candidate for downloading image from Internet or pulling data from DB. Very good idea here is to go to your Android SDK Manager and to download source code and see how implementation of AsyncTask looks like. Equally good idea is to place logging at every method and log ID of current thread, so that we can be sure where is what executed.
If we take a look at my example in git://github.com/FBulovic/grumpyoldprogrammer.git we will see that my BroadcastReceiver contains  AsyncTask. Knowing that  AsyncTask can bi instantiated only from UI thread we can conclude that  BroadcastReceiver is also executed on UI thread. That was nice intro to CursorAdapter and ContentProvider where execution happens outside of UI thread but they need to communicate with UI thread and that may course some problems here and there. Especially you want to access SQLite DB directly without using ContentProvider.
Next part of this tutorial will follow, soon.