Sunday, August 5, 2012

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.

Wednesday, August 1, 2012

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)

Tuesday, July 31, 2012

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

Thursday, July 26, 2012

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.

Wednesday, November 23, 2011

Building Webkit with Qt 4.8 on Linux

To build recent webkit codebase for qt, qt 4.8 is required.Currently to pre-built binaries for qt 4.8 is available, so you have to build it manually.

The steps to build webkit with qt4.8 on linux (mine is ubuntu Natty version) are as follows:-
Step 1. Get the qt 4.8 source:-
Get the qt 4.8 source from here in tar.gz format.

Step 2. Uncompress it:-
Uncompress it by using the below commands:-
  1. gunzip qt-everywhere-opensource-src-%VERSION%.tar.gz
  2. tar xvf qt-everywhere-opensource-src-%VERSION%.tar
Step 3. Building the qt 4.8 library:-
Move to the qt source home folder and use following commands:-
  1. cd qt-everywhere-opensource-src-%VERSION%
  2. ./configure // Deafault confing can be used
  3. make // create the library
  4. make install // install the library
Step 4: Set the Environment Variables:-
  • export PATH=/usr/local/Trolltech/Qt-4.8.0/bin:$PATH
With this step qt library is set-up is complete.

Step 5. Now build the webkit library

Get the webkit source from www.webkit.org.
From the home folder (which contains the "Source", "Tools" folder etc) use the below command:-
  • export QTDIR="/usr/local/Trolltech/Qt-4.8.0" // Set the Qt Dir
  • ./Tools/Scripts/build-webkit --qt [--debug]
Step 5. Launch qtwebkit
Now to launch the webkit library use the below command:-
  • ./Tools/Scripts/run-launcher --qt [--debug]


Monday, August 15, 2011

Android SDK update issue: "Folder failed to be renamed or moved on SDK install"

Recently while i was updating my Android SDK, I faced some issues and I was not able to update the sdk.The AVD managr was displaying the below error message.

-= Warning ! =-
A folder failed to be renamed or moved. On Windows this typically means that a program is using that folder (for example Windows Explorer.) Please close all running programs that may be locking the directory.

So I did the next natural step for such cases i.e googling for the error and foud that this issue is faced by many people recently and the same issue is logged in code.google.com also.URL for the same is:-
http://code.google.com/p/android/issues/detail?id=4410#makechanges

In the above page different people has recomended different solutions for the above issue.I am listing down all the solutions below (and yes, the one which worked for me.)

1.Might be an issue with anti-virus.Disable it and try again.
(didn't work for me)
2.If no antivirus software running and still get the error message, try
to delete the temp folder itself and run the update again. Worked for some people.
(didn't work for me)
3. Check if "adb.exe" is running as an independent process (normally when an android device is plugged-in).Unplugged the device and try. (not my case as no device was plugged-in)
4. Make a copy of the tools folder itself (keeping it at the same directory tree level, thus "tools" and "tools-copy" were both in the "android-sdk-windows" folder).
- Run Android.bat from that copy folder.
- Closed the SDK and , delete the folder (kill the adb.exe process first as you can't delete the folder without doing that).
- Restar the SDK from the normal (now-updated) tools folder.
(didn't try this option because of it's complexity...should have been the last one to try)
5. In the "temp" present inside "Android-Sdk-Windows" folder you can find the "tools_r12-windows.zip" or other files which you will update.
-Unzip it and copy all the files in the file the "tools" folder.
(This one works for me)

There are some other solutions mentioned also I didn't look at them as my problem was solved by that time and couldn't wait more to explore android 3.2 version.

Tuesday, April 19, 2011

Building chrome for Ubuntu linux...Some common errors

The steps for building Chrome for different platform is well documented by google.But while building Chrome I encountered some errors which are less documented.These are mostly due to missing linux package.Below are some of the issues due to missing package and the respective package required.

1. error: ‘XTestQueryExtension’ was not declared in this scope
Package Required:-
1. libxt-dev
2. libxtst-dev

2.libcommon.so: cannot open shared object file: No such file or directory
This is not exactly a compilation error.But this error comes while executing the chrome, if chrome is built using shared library option.To solve the error you need to add the path of the concerned library to system path i.e.

export LD_LIBRARY_PATH=/CHROME-PATH/src/out/Debug:/CHROME-PATH/src/out/Debug/lib.target:$LD_LIBRARY_PATH

where "CHROME-PATH" is the path of chrome source.