Solution: Android 4.0 (ICS) Compillation Error On Ubuntu

While compilling Android ICS 4.0 on my Ubuntu system I faced the below compillation error.

1. "_FORTIFY_SOURCE" redefined

Solution:
build/core/combo/HOST_linux-x86.mk:
    -HOST_GLOBAL_CFLAGS += -D_FORTIFY_SOURCE=0
    +HOST_GLOBAL_CFLAGS += -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=0

2. error: reference 'counts' cannot be declared 'mutable' [-fpermissive]

Solution:
external/oprofile/libpp/format_output.h
    -mutable counts_t & counts;
    +counts_t & counts;

3. error: 'ptrdiff_t' does not name a type

Solution:
external/gtest/include/gtest/internal/gtest-param-util.h
    #include <vector>
    +#include <cstddef>
    #include <gtest/internal/gtest-port.h>

4. undefined reference to 'pthread_mutex_trylock'

Solution:
external/llvm/llvm-host-build.mk
    LOCAL_LDLIBS := -lpthread -ldl

5. error: variable 'ParamName' set but not used

Solution:s
frameworks/compile/slang/Android.mk
    -local_cflags_for_slang := -Wno-sign-promo -Wall -Wno-unused-parameter -Werror
    +local_cflags_for_slang := -Wno-sign-promo -Wall -Wno-unused-parameter

Please note that on master branch these errors are resolved.

Creating A Detached PThread using Thread Attribute

In some cases you neither need the child thread to return information to the
main thread nor want the main thread to wait for it. This behavior can be achieved by making the child thread a detached thread. A detached thread can be created by using the thread attribute or by using Posix thread method "pthread_detach". here we will discuss about the former case i.e using the thread attribute.

1. Init thread attribute:
A thread attribute can be init by following function:

int pthread_attr_init(pthread_attr_t *attr);

2. Functions for Detached state:
Below functions are used to set and get the detached state of a thread.

int pthread_attr_setdetachstate(pthread_attr_t *attr, int detachstate);
int pthread_attr_getdetachstate(const pthread_attr_t *attr, int *detachstate);

Parameter:
1. attr: Thread attribute to init.
2. detachstate: Flag to set the required thread state. It can take the vales of "PTHREAD_CREATE_JOINABLE" or "PTHREAD_CREATE_DETACHED". The default value to detachstate is "PTHREAD_CREATE_JOINABLE". When it is "PTHREAD_CREATE_DETACHED" it creates a detached thread.

3. Example:
Below is the program to create a detached thread using thread attribute. We'll call it detachedThread.c.
detachedThread.c

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <signal.h>

bool thread_finished = 0;

void* start_function(void* value)
{
    printf("%s is now entering the thread function.\n", (char*)value);
    sleep(4);
    thread_finished =1;
    printf("%s is now leaving the thread function.\n", (char*)value);
    pthread_exit(value);  
}

main()
{
    int res,err;
    pthread_attr_t attr;
    pthread_t thread1;

    res = pthread_attr_init(&attr);
    if (res != 0) {
        perror("Attribute init failed");
        exit(EXIT_FAILURE);
    }
    res = pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
    if (res != 0) {
        perror("Setting detached state failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_create(&thread1, &attr, start_function, (void*)"Thread1");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }

    while(!thread_finished) {
        printf("Waiting for thread1 to finish.\n");
        sleep(1);
    }

    printf("Child thread finished.\n");    
    pthread_attr_destroy(&attr);
}

When you compile and run the program, you'll see the output as:

Waiting for thread1 to finish.
Thread1 is now entering the thread function.
Waiting for thread1 to finish.
Waiting for thread1 to finish.
Waiting for thread1 to finish.
Thread1 is now leaving the thread function.
Child thread finished.

Getting the Posix Thread Id in Linux

In linux system gettid function used to get the thread ID. The TID is diffrent than PID.In a single-threaded process, the TID is equal to the PID. But in a multithreaded program, all threads belonging to same process have the same PID but each one has a unique TID. The TID generally reprsent the kernel thread id and is different from the thread ID returned by pthread_self(i.e. thread handle which is returned from pthread_create function).

Note that Glibc does not provide the function gettid(). So we will use the system call to get the TID. Let's create a simple program to see the use of gettid, getpid and pthread_self. We'll call this threadBasic.c.

threadBasic.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/syscall.h>
#include <pthread.h>

pid_t gettid()
{
    pid_t tid = syscall (SYS_gettid);
}

void* start_function(void* value)
{
    pid_t tid = gettid();
    printf("Thread start function is running for: %u\n", (unsigned int)pthread_self());
    printf("The TID of thread is: %ld\n", (long int)tid);
    printf("PID of parent process is: %d\n", getpid());
    sleep(5);
    pthread_exit(value);
}

main()
{
    int res;
    pthread_t thread1, thread2;
    void* threadReturnValue;

    printf("PID of main process: %d\n", getpid());

    res = pthread_create(&thread1, NULL, start_function, "thread-one");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }
    printf("Thread1 created with id: %u\n", (unsigned int)thread1);

    res = pthread_create(&thread2, NULL, start_function, "thread-two");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }
    printf("Thread2 created with id: %u\n", (unsigned int)thread2);
 
    res = pthread_join(thread1, &threadReturnValue);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }
    printf("%s joined.\n", (char*)threadReturnValue);

    res = pthread_join(thread2, &threadReturnValue);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }
    printf("%s joined.\n", (char*)threadReturnValue);
}

Now when you compile and run the program, you will see:

gcc -o threadBasic threadBasic.c -lpthread
./threadBasic 
PID of main process: 4610
Thread1 created with id: 3078278000
Thread start function is running for: 3078278000
The TID of thread is: 4611
PID of parent process is: 4610
Thread start function is running for: 3069885296
The TID of thread is: 4612
Thread2 created with id: 3069885296
PID of parent process is: 4610
thread-one joined.
thread-two joined.

Explanation:

Posix Thread synchronization with Semaphore

In my previous post , we have seen how to synchronize threads with Mutex. In this post we will see how to synchronize threads using semaphore. Also we will undersatand semaphore in terms of POSIX and we'll not discuss about Linux system V semaphore (will discuss in another post).

In simple terms a semaphore can be thought of a variable with two operation: wait and signal. the wait operation decrement the counter where as the signal operation increment the counter.

1. Semaphore functions

int sem_init(sem_t *sem, int pshared, unsigned int value);

It initializes a semaphore pointed to by sem. The pshared param is used to specify the type of semaphore. If it's value is 0, then the semaphore is local to the current process. Otherwise, the semaphore may be shared between processes. The value param is used to give an initial value to semaphore.

int sem_wait(sem_t * sem);

The sem_wait function atomically decreases the value of the semaphore by one. So if you call sem_wait on a semaphore with a value of 2, then the value of semaphore will be decreased to 1. If you call sem_wait on a semaphore with a value of 0, then the thread will be blocked until some other thread has incremented the value to a positive number. If multiple threads are blocked waiting on a semaphore before some other thread increment the semaphore, then only one of them will get to decrement the semaphore and continue. The thread which will get the samaphore is decided by the system and the decesion making technique may vary from system to system i.e. it may be FIFO or may be based on some priority.

int sem_post(sem_t * sem);

The sem_post function atomically increases the value of the semaphore by one. It's the reverse of sem_wait.

It's worth noting that, I have used to term "atomically" with sem_wait and sem_post operation. Atomically means that if two threads simultaneously try to increase or decrease the value of a single semaphore by 1, they do not interfere with each other.

int sem_destroy(sem_t * sem);

It destroys the semaphore pointed to by sem.

2. Code Example:

There are a number of types of semaphore. But here we will use a binary semaphore. A binary semaphore takes only values of 0 or 1 and can be used like a mutex. In fact I have replaced the mutex functions from the example in the previous post , with the semaphore functions in the below example. We'll call it semaphore.c.

semaphore.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

sem_t  smp;
int counter = 0;

void* start_function(void* value)
{
    printf("%s is now entering the thread function.\n", (char*)value);
    sem_wait(&smp);
    counter++;
    sleep(2);
    sem_post(&smp);
    printf("%s is now leaving the thread function.\n", (char*)value);
    printf("Value of counter is: %d\n", counter);
    pthread_exit(value);
}

main()
{
    int res;
    pthread_t thread1, thread2;

    sem_init(&smp, 0, 1);

    res = pthread_create(&thread1, NULL, start_function, "Thread1");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_create(&thread2, NULL, start_function, "Thread2");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }
 
    res = pthread_join(thread1, NULL);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_join(thread2, NULL);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }

    sem_destroy(&smp);
}

Now when you compile and run the program, you will see:

gcc -o semaphore semaphore.c -lpthread
./semaphore 
Thread1 is now entering the thread function.
Thread2 is now entering the thread function.
Thread1 is now leaving the thread function.
Value of counter is: 1
Thread2 is now leaving the thread function.
Value of counter is: 2

What will happen if we don't use semaphore? Try that out.

Posix Thread synchronization with Mutex

Mutex is a synchronization technique to protect shared resources. It can be thought of a lock, which is used to protect a resource. Similarly when one thread lock a region or piece of code (normally called critical section), then no other thread can access or execute the locked code.

Here we will use POSIX mutex API to see the use of mutex lock. Below are some important POSIX functions, that we will use in our example.

1. Init Mutex

int pthread_mutex_init(pthread_mutex_t *mutex, const pthrea. d_mutexattr_t *attr);

This function initializes a mutex pointed to by mutex. The pthread_mutexattr_t param is for specifying attribute for the mutex.

2. Lock,Unlock and Destroy

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
int pthread_mutex_destroy(pthread_mutex_t *mutex);

The above functions are self-explanatory.

3. Points to remember while using mutex.

1. No thread should attempt to lock or unlock a mutex that has not been initialized.
2. The thread that locks a mutex must be the thread that unlocks it.
3. No thread should have the mutex locked when you destroy the mutex.
4. Never call pthread_mutex_lock on a mutex that it has already locked.

4. Code Example
We wiil create small and simple program to understand Mutex. We'll call it mutex.c
mutex.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>

pthread_mutex_t  ml;
int counter = 0;

void* start_function(void* value)
{
    printf("%s is now entering the thread function.\n", (char*)value);
    pthread_mutex_lock(&ml);
    counter++;
    sleep(2);
    pthread_mutex_unlock(&ml);
    printf("%s is now leaving the thread function.\n", (char*)value);
    printf("Value of counter is: %d\n", counter);
    pthread_exit(value);
}

main()
{
    int res;
    pthread_t thread1, thread2;

    res = pthread_mutex_init(&ml, NULL);
    if (res != 0) {
        perror("Mutex Init failed.");
        exit(EXIT_FAILURE);
    }

    res = pthread_create(&thread1, NULL, start_function, "Thread1");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_create(&thread2, NULL, start_function, "Thread2");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }
 
    res = pthread_join(thread1, NULL);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_join(thread2, NULL);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }

    pthread_mutex_destroy(&ml);
}

Now when you compile and run the program, you will see:

gcc -o mutex mutex.c -lpthread
./mutex
Thread1 is now entering the thread function.
Thread2 is now entering the thread function.
Thread1 is now leaving the thread function.
Value of counter is: 1
Thread2 is now leaving the thread function.
Value of counter is: 2

The above progarm has a critical section of code, which increases the counter. And this piece of code can be executed by multiple threads simulataneously in a multi-threaded programming. So a mutex lock is used to protect it.

What will happen if we don't use mutex? Then the output will be:

./mutex 
Thread1 is now entering the thread function.
Thread2 is now entering the thread function.
Thread2 is now leaving the thread function.
Value of counter is: 2
Thread1 is now leaving the thread function.
Value of counter is: 2

This is not the output, which you have expected. So in a multi-threaded program if you don't protect critcal section, then the result is not guaranteed.

Binary Search Tree

A Binary Search Tree(BST) is a node-based binary tree data structure which has the following properties:
1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

One major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Example


Terms Used In BST
1. Node: An item that is stored in the tree.
2. Root: The top item in the tree (50 in above case)
3. Child: Node(s) under the current node.
4. Parent: The node that is present directly above the current node. (90 is the parent of 100 in above case).
5. Leaf : A node which has no children(20 is a leaf in the above case)

Searching in a BST
1. Start at the root node.
2. If the item that you are searching for is less than the root node, move to the left child of the root node, else if the item that you are searching for is more than the root node, move to the right child of the root node and if it is equal to the root node, then you have found the item that you are looking for :)
3. Now check to see if the item that you are searching for is equal to, less than or more than the new node that you are on. Again perform step 2.
4. Repeat this process until you find the item that you are looking for or until the node doesn't have a child on the correct branch, in which case the tree doesn't contain the item which you are looking for.

Code Example

bool BinarySearchTree::search(int val)
{
    Node *next = this->root();
    while (next != NULL) {
        if (val == next->value()) {
            return true;
        } else if (val < next->value()) {
            next = next->left();
        } else {
            next = next->right();
    }
}
    //Element not found
    return false;
}

Complexity
Average Case:
If we have a tree with n nodes, then with each step we halves the value n. So the number of steps the algorithm takes equals the number of times we can halve n. By definition, this is exactly log n. So the algorithm is of O(log n)

Best case : O(1)
Worst case: O(n)

Other Operations:
The other operations that are performed on a BST are:
1. Adding an item to a binary search tree (coming soon)
2. Deleting an item from a binary search tree (coming soon)

Binary Tree and It's Traversal

A tree is called a binary tree where each node has zero, one, or two children ie. at most 2 children.

There are three different methods for traversing binary trees: preorder, postorder and in-order.

Preorder
preorder: Current node, left subtree, right subtree

preorder(node)
    visit(node)
    if node.left != null then preorder(node.left)
    if node.right != null then preorder(node.right)

Postorder
postorder: Left subtree, right subtree, current node

postorder(node)
    if node.left != null then postorder(node.left)
    if node.right != null then postorder(node.right)
    visit(node)

Inorder
in-order: Left subtree, current node, right subtree

inorder(node)
    if node.left != null then inorder(node.left)
    visit(node)
    if node.right != null then inorder(node.right)

Example

If we have a tree as shown above, then the output for different traversal method will be as:
1. preorder : 50, 30, 20, 40, 90, 100
2. postorder : 20, 40, 30, 100, 90, 50
3. inorder : 20, 30, 40, 50, 90, 100

Creating a shared library in linux

Lets discuss how to create a shared library in linux and use it in another program.

Step 1. Write the header and source file that will be used to create the shared library. We'll call them myclass.h and myclass.cc.

myclass.h

#ifndef __MYCLASS_H__
#define __MYCLASS_H__

class myClass
{
public:
    myClass() {}

    // use virtual otherwise linker will try to perform static linkage.
    virtual void myFunction();
};

#endif // __MYCLASS_H__

myclass.cc

#include <iostream>
#include "myclass.h"

using namespace std;

void myClass::myFunction()
{
   cout<<"Hello from shared library.\n";
}

Step 2. Creating Object File with Position Independent Code

The code that constitutes the shared library needs to be position independent. Because since several programs can use a single instance of your shared library the location of that library in memory will vary from program to program. PIC works no matter where in memory it is placed.

g++ -c -fpic myclass.cc -o myclass.o

Compiler options:
-c : Here our objective is to create the object file and not to run the linker. The "-c" oprtion is used to achive this.

-fpic : It generate position-independent code(PIC) suitable for use in a shared library. PIC accesses all constant addresses through a global offset table(GOT). The dynamic loader(part of the operating system) resolves the GOT entries when the program starts. If the GOT size for the linked executable exceeds a machine-specific maximum size, you get an error message from the linker indicating that -fpic does not work. For such case, recompile with "-fPIC" option. The "-fPIC" option avoids any limit on the size of the global offset table.

-o [filename]: Place output in file file named filename.

Step 3. Creating Shared library from the generated Object File

Now we will create a shared library using the object file created in previous step. We’ll call it libmyclass.so.

g++ -shared -o libmyclass.so myclass.o

Compiler options:
-shared: Produce a shared object which can then be linked with other objects to form an executable.

-o [libname] : create the shared object with libname. If not specified the will create shared library with default name i.e. "a.out".

In this step the shared library is created and ready for use. In the next step we will see how to use it.

Step 4. Using the Shared Library
Create a programme and link it with the above shared library. we'll call it test.cc.

test.cc

#include <iostream>
#include "myclass.h"

using namespace std;

int main()
{
    cout<<"This is a test program for shared library.\n";
    myClass m;
    m.myFunction();
}

Now link the program with the shared library:

g++ -o test test.cc -lmyclass -L/PATH-TO-LIBRARY

Compiler options:
-l [library]: Search the library named library when linking. It should be noted that the -lmyclass option is not looking for myclass.o, but liblmyclass.so.

-L[dir] : Add directory dir to the list of directories to be searched for library mentioned with option -l. Note that g++ first searches for libraries in /usr/local/lib, then in /usr/lib. Following that, it searches for libraries in the directories specified by the -L parameter.

What will happen if you don't provide the -L option? say you link the program as:

g++ -o test test.cc -lmyclass

It will throw the below error:

/usr/bin/ld: cannot find -lmyclass
collect2: ld returned 1 exit status

What will happen if you don't provide the -l option also? See it yourself.

Step 4. Run the program that uses the library

./test
./test: error while loading shared libraries: libmyclass.so: cannot open shared object file: No such file or directory

The problem is that the loader can’t find the shared library. since libmyclass.so is not present in a standard location used for library lookup, we need to set the environment variable LD_LIBRARY_PATH with the path that contans libmyclass.so .

export LD_LIBRARY_PATH=/PATH-TO-LIBRARY/:$LD_LIBRARY_PATH

Now run the program again. You will see the output as:

./test
This is a test program for shared library.
Hello from shared library.