Archive for the ‘Uncategorized’ Category

Linked Lists- C

Posted: October 9, 2011 in Uncategorized


Linked list is one of the fundamental data structures, and can be used to implement other data structures. In a linked list there are different numbers of nodes. Each node is consists of two fields. The first field holds the value or data and the second field holds the reference to the next node or null if the linked list is empty.



Figure: Linked list


Collapse | Copy Code
Linkedlist Node {
    data // The value or data stored in the node
    next // A reference to the next node, null for last node


The singly-linked list is the easiest of the linked list, which has one link per node.


To create linked list in C/C++ we must have a clear understanding about pointer. Now I will explain in brief what is pointer and how it works.

A pointer is a variable that contains the address of a variable. The question is why we need pointer? Or why it is so powerful? The answer is they have been part of the C/C++ language and so we have to use it. Using pointer we can pass argument to the functions. Generally we pass them by value as a copy. So we cannot change them. But if we pass argument using pointer, we can modify them. To understand about pointers, we must know how computer store variable and its value. Now, I will show it here in a very simple way.


Let us imagine that a computer memory is a long array and every array location has a distinct memory location.


Collapse | Copy Code
 int a = 50 // initialize variable a



Figure: Variable value store inside an array


It is like a house which has an address and this house has only one room. So the full address is-

Name of the house: a

Name of the person/value who live here is: 50

House Number: 4010


If we want to change the person/value of this house, the conventional way is, type this code line

Collapse | Copy Code
 a = 100    // new initialization


But using pointer we can directly go to the memory location of ‘a’ and change the person/value of this house without disturbing ‘a’. This is the main point about pointer.


Now the question is how we can use pointer. Type this code line:


Collapse | Copy Code
 int *b;    // declare pointer b


We transfer the memory location of a to b.


Collapse | Copy Code
 b = &a;    // the unary operator & gives the address of an object


Figure: Integer pointer b store the address of the integer variable a


Now, we can change the value of a without accessing a.


Collapse | Copy Code
 *b = 100;  // change the value of 'a' using pointer ‘b’
  cout<<a;  // show the output of 'a'


When you order the computer to access to access *b, it reads the content inside b, which is actually the address of a then it will follow the address and comes to the house of a and read a`s content which is 50.


Now the question is, if it is possible to read and change the content of b without accessing b? The answer is affirmative. We can create a pointer of pointer.


Collapse | Copy Code
 int **c;   //declare a pointer to a pointer
 c = &b;    //transfer the address of ‘b’ to ‘c’


So, we can change the value of a without disturbing variable a and pointer b.


Collapse | Copy Code
 **c = 200;  // change the value of ‘a’ using pointer to a pointer ‘c’
  cout<<a;  // show the output of a


Now the total code is:

Collapse | Copy Code
using namespace std;

int main()
      int a = 50;       // initialize integer variable a
      cout<<"The value of 'a': "<<a<<endl; // show the output of a

      int * b;          // declare an integer pointer b
      b = &a;           // transfer the address of 'a' to pointer 'b'
      *b = 100;         // change the value of 'a' using pointer 'b'
      cout<<"The value of 'a' using *b: "<<a<<endl;// show the output of a

      int **c;          // declare an integer pointer to pointer 'c'
      c = &b;           // transfer the address of 'b' to pointer to pointer 'c'
      **c = 200;        // change the value of 'a' using pointer to pointer 'c'
      cout<<"The value of 'a' using **c: "<<a<<endl;// show the output of a

      return 0;





This program will give you the inside view of the pointer.

Collapse | Copy Code
using namespace std;

int main()
      int a = 50;       // initialize integer variable a
      cout<<"Value of 'a' = "<<a<<endl;          // show the output of a
      cout<<"Memory address of 'a': "<<&a<<endl; // show the address of a

      int * b;             // declare an integer pointer b
      b = &a;              // transfer the address of 'a' to pointer 'b'
      cout<<"Value of Pointer 'b': "<<*b<<endl;  // show the output of *b
      cout<<"Content of Pointer 'b': "<<b<<endl; // show the content of *b
      cout<<"Memory address of Pointer 'b': "<<&b<<endl; // show the address of *b

      int **c;                // declare an integer pointer to a pointer
      c = &b;                 // transfer the address of 'b' to 'c'
      cout<<"Value of Pointer 'c': "<<**c<<endl; // show the output of **c
      cout<<"Content of Pointer 'c': "<<c<<endl;  // show the content of **c
      cout<<"Memory address of Pointer 'c': "<<&c<<endl; // show the address of **c
      return 0;




We can observe that the memory address of a and the content of pointer b is same. The content of pointer c and the memory address of b is same.


Linked list operation

Now we have a clear view about pointer. So we are ready for creating linked list.


Linked list structure

Collapse | Copy Code
typedef struct node                                                
      int data;               // will store information
      node *next;             // the reference to the next node


First we create a structure “node”. It has two members and first is int data which will store the information and second is node *next which will hold the address of the next node. Linked list structure is complete so now we will create linked list. We can insert data in the linked list from ‘front’ and at the same time from ‘back’. Now we will examine how we can insert data from front in the linked list.

1) Insert from front

At first initialize node type.

Collapse | Copy Code
node *head = NULL;             //empty linked list


Then we take the data input from the user and store in the node info variable. Create a temporary node node *temp and allocate space for it.

Collapse | Copy Code
node *temp;             //create a temporary node 
temp = (node*)malloc(sizeof(node)); //allocate space for node


Then place info to temp->data. So the first field of the node *temp is filled. Now temp->next must become a part of the remaining linked list (although now linked list is empty but imagine that we have a 2 node linked list and head is pointed at the front) So temp->next must copy the address of the *head (Because we want insert at first) and we also want that *head will always point at front. So *head must copy the address of the node *temp.


Figure: Insert at first


Collapse | Copy Code
temp->data = info;             // store data(first field)
temp->next=head;  // store the address of the pointer head(second field)
head = temp;                  // transfer the address of 'temp' to 'head'


2) Traverse

Now we want to see the information stored inside the linked list. We create node *temp1. Transfer the address of *head to *temp1. So *temp1 is also pointed at the front of the linked list. Linked list has 3 nodes.


We can get the data from first node using temp1->data. To get data from second node, we shift *temp1 to the second node. Now we can get the data from second node.


Collapse | Copy Code
while( temp1!=NULL )
 cout<< temp1->data<<" ";// show the data in the linked list
 temp1 = temp1->next;   // tranfer the address of 'temp->next' to 'temp'


Figure: Traverse


This process will run until the linked list’s next is NULL.

3) Insert from back

Insert data from back is very similar to the insert from front in the linked list. Here the extra job is to find the last node of the linked list.


Collapse | Copy Code
node *temp1;                         // create a temporary node
temp1=(node*)malloc(sizeof(node));   // allocate space for node
temp1 = head;                  // transfer the address of 'head' to 'temp1'
while(temp1->next!=NULL) // go to the last node
      temp1 = temp1->next;//tranfer the address of 'temp1->next' to 'temp1'



Now, Create a temporary node node *temp and allocate space for it. Then place info to temp->data, so the first field of the node node *temp is filled. node *temp will be the last node of the linked list. For this reason, temp->next will be NULL. To create a connection between linked list and the new node, the last node of the existing linked list node *temp1`s second field temp1->next is pointed to node *temp.



Figure: Insert at last



Collapse | Copy Code
node *temp;                           // create a temporary node
temp = (node*)malloc(sizeof(node));  // allocate space for node
temp->data = info;                   // store data(first field)
temp->next = NULL;                   // second field will be null(last node)
temp1->next = temp;                  // 'temp' node will be the last node

4) Insert after specified number of nodes

Insert data in the linked list after specified number of node is a little bit complicated. But the idea is simple. Suppose, we want to add a node after 2nd position. So, the new node must be in 3rd position. The first step is to go the specified number of node. Let, node *temp1 is pointed to the 2nd node now.


Collapse | Copy Code
cin>>node_number;                   // take the node number from user 

node *temp1;                        // create a temporary node
temp1 = (node*)malloc(sizeof(node)); // allocate space for node
temp1 = head;

for( int i = 1 ; i < node_number ; i++ )
      temp1 = temp1->next;           // go to the next node

      if( temp1 == NULL )
            cout<<node_number<<" node is not exist"<< endl;


Now, Create a temporary node node *temp and allocate space for it. Then place info to temp->next , so the first field of the node node *temp is filled.

Collapse | Copy Code
node *temp;                          // create a temporary node
temp = (node*)malloc(sizeof(node));  // allocate space for node
temp->data = info;                   // store data(first field)



To establish the connection between new node and the existing linked list, new node’s next must pointed to the 2nd node’s (temp1) next . The 2nd node’s (temp1) next must pointed to the new node(temp).

Collapse | Copy Code
temp->next = temp1->next;            //transfer the address of temp1->next to temp->next
temp1->next = temp;     //transfer the address of temp to temp1->next


Figure: Insert after specified number of nodes



5) Delete from front

Delete a node from linked list is relatively easy. First, we create node *temp. Transfer the address of *head to *temp. So *temp is pointed at the front of the linked list. We want to delete the first node. So transfer the address of temp->next to head so that it now pointed to the second node. Now free the space allocated for first node.


Collapse | Copy Code
node *temp;                                      // create a temporary node
temp = (node*)malloc(sizeof(node));  // allocate space for node
temp = head;                   // transfer the address of 'head' to 'temp'
head = temp->next;      // transfer the address of 'temp->next' to 'head'


Figure: Delete at first node



6) Delete from back

The last node`s next of the linked list always pointed to NULL. So when we will delete the last node, the previous node of last nodeis now pointed at NULL. So, we will track last node and previous node of the last node in the linked list. Create temporary node * temp1 and *old_temp.

Collapse | Copy Code
// create a temporary node
node *temp1;
temp1 = (node*)malloc(sizeof(node)); // allocate space for node
temp1 = head;                        //transfer the address of head to temp1
node *old_temp;                     // create a temporary node
old_temp = (node*)malloc(sizeof(node));    // allocate space for node

while(temp1->next!=NULL)             // go to the last node
      old_temp = temp1; // transfer the address of 'temp1' to 'old_temp'
      temp1 = temp1->next;       // transfer the address of 'temp1->next' to 'temp1'


Now node *temp1 is now pointed at the last node and *old_temp is pointed at the previous node of the last node. Now rest of the work is very simple. Previous node of the last node old_temp will be NULL so it become the last node of the linked list. Free the space allocated for last lode.

Collapse | Copy Code
old_temp->next = NULL;         // previous node of the last node is null


Figure: Delete at first last


7) Delete specified number of node

To delete a specified node in the linked list, we also require to find the specified node and previous node of the specified node. Create temporary node * temp1, *old_temp and allocate space for it. Take the input from user to know the number of the node.

Collapse | Copy Code
node *temp1;                         // create a temporary node
temp1 = (node*)malloc(sizeof(node)); // allocate space for node
temp1 = head;                  // transfer the address of 'head' to 'temp1'

node *old_temp;                     // create a temporary node
old_temp = (node*)malloc(sizeof(node));    // allocate space for node
old_temp = temp1;       // transfer the address of 'temp1' to 'old_temp'


Collapse | Copy Code
cin>>node_number;                    // take location


Collapse | Copy Code
for( int i = 1 ; i < node_number ; i++ )
      old_temp = temp1;                    // store previous node
      temp1 = temp1->next;                 // store current node



Now node *temp1 is now pointed at the specified node and *old_temp is pointed at the previous node of the specified node. The previous node of the specified node must connect to the rest of the linked list so we transfer the address of temp1->next to old_temp->next. Now free the space allocated for the specified node.

Collapse | Copy Code
old_temp->next = temp1->next;  // transfer the address of 'temp1->next' to 'old_temp->next'



8) Sort nodes

Linked list sorting is very simple. It is just like ordinary array sorting. First we create two temporary node node *temp1, *temp2 and allocate space for it. Transfer the address of first node to temp1 and address of second node to temp2. Now check if temp1->data is greater than temp2->data. If yes then exchange the data. Similarly, we perform this checking for all the nodes.


Collapse | Copy Code
node *temp1;                         // create a temporary node
temp1 = (node*)malloc(sizeof(node)); // allocate space for node

node *temp2;                         // create a temporary node
temp2 = (node*)malloc(sizeof(node)); // allocate space for node

int temp = 0;                        // store temporary data value

for( temp1 = head ; temp1!=NULL ; temp1 = temp1->next )
      for( temp2 = temp1->next ; temp2!=NULL ; temp2 = temp2->next )
            if( temp1->data > temp2->data )
                  temp = temp1->data;
                  temp1->data = temp2->data;
                  temp2->data = temp;



From the above discussions, I hope that everybody understands what linked list is and how we can create it. Now we can easily modify linked list according to our program requirement and try to use it for some real tasks. Those who still have some confusion about linked list, for them I will now tell you a story.

Once upon a time, an old man lived in a small village. The old man was very wise and knew many solutions about different problems. He had also special powers so he could talk to genie and spirits, and sometimes they granted his wish by using their special powers. Oneday a witch with a broom came to talk with him and ask difficult and complex issues about global warming. He was very surprised but patiently explained her about green house model and gave her advice about using biofuel in her broom. The witch was very rude and greedy but she always liked to preach her nobility. So at the time of her departure, she wanted to grant only two wishes. The old man asked her why she only granted two wishes. He also reminded her that whenever genie comes he granted two wishes.” What I am look like” the witch asked angrily,” A blank check?” The old man brewed a plan. He told her that his first wish was to get a super computer.” It is granted”, the witch announced loudly.” Then my second wish is to have another two wishes”, the old man said very slowly. The witch was shell shocked. “It is also granted”, the witch said and left the place very quickly with her broom.

You may ask yourself why the witch was surprised. First, the witch granted two witches. One was fulfilled and for the second wish, the old man wanted another two wish. “What’s the big idea?” you can ask me,” The witch can also fulfill this wish”. Certainly, the witch can grant his wish. But what will happen if the old man wants to extend his second wish to another two wish set. So, the process will never end unless, the old man want to stop. The idea is same for linked list. First you have a node where you can imagine that data is the first wish and node*next is the second wish by which you can create second node just like first. This process will continue until you put NULL in the *next.


Figure: It looks like the old man had lots of wish.


  1. Wikipedia, the free encyclopedia.
  2. Pointer in C, from P. Kanetkar.



This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Nasif M.



         "Understanding Hash Tables"
  C/O :: arp of DynamicHell Development Team
------------------------------------------------ |

This tutorial is aimed at users with a basic understanding of C, pointers, and
more importantly linked lists.  This technique, like linked lists, is portable
and can be used on any operating system with a standard C library and compiler.

There are many data structures available to the programmer.  The most common
being the linked-list.  However, linked-list traversal can become quite slow
with large lists.  A hash tables provides a means of storing and accessing data
much more efficiently.

Essentially, a hash table is an array of linked-lists, with each list indexed
by the hash of a common variable stored in a node.

For large amounts of data, in which hashing is possible, hash tables become
faster to traverse than a standard linked-list.  Rather than traversing one
large list, the program tests the data to be added, generates a hash index and
inserts it into the array of linked-lists at that index.  Meaning that the 
linked-list to be traversed is much shorter; saving time.

The following diagram shows a visual representation of a hash table:

Node    : ===
Pointer : ---


As you can see once the index is found, the number of nodes to traverse is much
smaller than a traditional long linked-list.

Implementing a Hash Table (C)

The traditional structure for a node in a hash table is identical to that of a
linked list:

struct node {
       char *data;
       struct node *next;

Now our table must be defined, remembering to define a size which is 
accessible by all parts of our program (this will become clearer later.)

#define TABLE_SIZE 100

struct node *hashtable[TABLE_SIZE];

We must now define a method of creating a new node.  It is identical to the 
function typically used in a linked-list:

struct node *hashtable_alloc(void)
	struct node *tmp = calloc(1, sizeof(struct hash));
	if(tmp == NULL) {
	       fprintf(stderr, "Error: calloc()\n");

	tmp->next = NULL;	

	return tmp;       

The next step is important--easy to forget--and involves initialising the array
of linked lists.  There are various ways to do this, though for simplicity we
will allocate one root node for each list.

void hashtable_init(void)
	int x;

	for(x = 0; x <TABLE_SIZE; x++) {
	      hashtable[x] = hashtable_alloc();


Before adding to our table, we need a means of finding an index into our array;
a hashing function.  Our hashing function will take our value, a string, and
convert it into an index into our hash table (array of linked lists).

unsigned int hash_gen(char *string)
	unsigned int num = 0;

	while(*string++ != '')
			num += *string;

	return num % TABLE_SIZE;

Now able to find the correct index into the hash table, we are ready to add 
data to it.  A typical function for adding data to a hash table follows.  
Notice the double traversal. The first checks the whole list, up to the NULL 
pointer and acts appropriately--in this case returning.  The second traversal
ends when node->next equals NULL, so we know that the current node exists, and
thus, using its pointer will result in a successful link.

void hashtable_add(char *data)
	unsigned int x = hash_gen(data);
	struct node *tmp;
	char *strdup(const char *s);

	/* Our first loop checks to see the data doesn't already exist */

	for(tmp = hashtable[x]; tmp != NULL; tmp = tmp->next) {

		if(tmp->data != 0) { /* for our root node */

			if(!strcmp(data, tmp->data))
					 return; /* Exists already */


	for(tmp = hashtable[x]; tmp->next != NULL; tmp = tmp->next);

	if(tmp->next == NULL) { 
		     tmp->next = hashtable_alloc();
		     tmp = tmp->next;
		     tmp->data = strdup(data);
		     tmp->next = NULL;
	} else

With our functions for creating nodes, generating a hash and adding data to 
the hash table, we are now ready to write a function to read the data from the
list.  This entails looping through the table and traversing each list as you
would a linked-list.

void hashtable_list(void)
	int x = 0;
	struct node *tmp;

	for(x = 0; x < TABLE_SIZE; x++) {

		for(tmp = hashtable[x]; tmp != NULL; tmp = tmp->next) {
			if(tmp->name != 0) {
		                printf("Index is %d, Data is %s\n", x, 


We are almost complete.  The only thing that remains to be done is to clean up
once we have finished with our hash table.  We use two temporary pointers in 
order to reconnect to the list once one node has been freed.

void hashtable_free(void)
	struct node *tmp;
	struct node *fwd;
	int x;

	for(x = 0; x < TABLE_SIZE; x++) {

	      tmp = hashtable[x];
	      while(tmp != NULL) {
	              fwd = tmp->next;
		      tmp = fwd;


Again as with linked lists we never modify the pointer to a root node as this
would break our lists.

Final Code

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

#define TABLE_SIZE 100

struct node {
       char *data;
       struct node *next;

struct node *hashtable[TABLE_SIZE]; /* Our hash table */

struct node *hashtable_alloc(void);
void hashtable_init(void);
unsigned int hash_gen(char *string);
void hashtable_add(char *data);
void hashtable_list(void);
void hashtable_free(void);

int main(void)





void hashtable_list(void)
	int x = 0;
	struct node *tmp;

	for(x = 0; x < TABLE_SIZE; x++) {

		for(tmp = hashtable[x]; tmp != NULL; tmp = tmp->next) {
			if(tmp->data != 0) {
		                printf("Index is %d, Data is %s\n", x, 


void hashtable_add(char *data)
	unsigned int x = hash_gen(data);
	struct node *tmp;
	char *strdup(const char *s);

	/* Our first loop checks to see the data doesn't already exist */

	for(tmp = hashtable[x]; tmp != NULL; tmp = tmp->next) {

		if(tmp->data != 0) { /* for our root node */

			if(!strcmp(data, tmp->data))

	for(tmp = hashtable[x]; tmp->next != NULL; tmp = tmp->next);

	if(tmp->next == NULL) { 
		     tmp->next = hashtable_alloc();
		     tmp = tmp->next;
		     tmp->data = strdup(data);
		     tmp->next = NULL;
	} else

unsigned int hash_gen(char *string)
	unsigned int num = 0;

	while(*string++ != '')
			num += *string;

	return num % TABLE_SIZE;

void hashtable_init(void)
	int x;

	for(x = 0; x <TABLE_SIZE; x++) {
	      hashtable[x] = hashtable_alloc();


struct node *hashtable_alloc(void)
	struct node *tmp = calloc(1, sizeof(struct node));
	if(tmp == NULL) {
	       fprintf(stderr, "Error: calloc()\n");

	tmp->next = NULL;	

	return tmp;       

void hashtable_free(void)
	struct node *tmp;
	struct node *fwd;
	int x;

	for(x = 0; x < TABLE_SIZE; x++) {

	      tmp = hashtable[x];
	      while(tmp != NULL) {
	              fwd = tmp->next;
		      tmp = fwd;



There are various improvements which could be made to this design.  Firstly, 
the hash table could be larger to avoid unnecessary collisions.  Secondly,
instead of wasting memory by allocating one root node for each array of linked
lists, we could allocate on demand, instead initialising by setting each 
linked-list to NULL.  Another suggestion is to use a bitmap for defining used
and unused lists.  The program could quickly check the bits and decide whether
to allocate or to traverse.  


Hash tables are faster than large linked lists.  They--like linked lists--are 
used throughout the software industry.  

The root node of any list is never directly modified, only pointers to it, so
not to damage the list's structure.

There are various ways to improve hash table efficiency.

Copright (c) 2006.  Alastair Poole.

Verbatim copying and distribution of this entire article are permitted
worldwide, without royalty, in any medium, provided this notice, and the
copyright notice, are preserved.


Walking Around the World

Date: 02/08/97 at 18:02:14
From: Anonymous
Subject: Calculating new position and heading after a walk around the 

I've been trying to solve the following problem, but as I don't know 
any spherical geometry (or whatever it is that's needed). I haven't 
had much luck so far.

Given someone's starting point on the earth (in degrees longitude and
latitude), and the direction he is initially facing, if he travels in 
a straight line a certain distance, where will he end up (in degrees/
radians) and in what direction will he now be facing?

I really want to get this down to a set of formulae which I can put 
the 4 given values into (longitude, latitude, direction, distance) and 
get out the 3 values I'm looking for (new longitude, new latitude, new

Date: 02/13/97 at 12:59:12
From: Doctor Mitteldorf
Subject: Re: Calculating new position and heading after a walk around 
the world

Dear Kluj,

I've been working periodically on your question about headings, 
latitude and longitude.  I have an answer for you, and I'll describe 
briefly where it comes from.  Let me know if you want more details, or 
if the derivation either too advanced or too elementary.

First, definitions:

Start at a point with given longitude, we'll call this long1, and 
given latitude, we'll call this lat1.   

Travel in a compass heading, we'll call this hdng1, and go a certain 
distance, we'll call this dist.  The compass heading is measured from 
due north, which is equal to 0.

Define alpha = dist/[earth radius] to be the angular distance covered 
on the earth's surface.

You're looking for coordinates of the point that you reach, which 
we'll call lat2 and long2.

You also want to know your new compass heading, which we'll call 

The answer:

First calculate the new latitude:

1) sin(lat2) = cos(hdng1)*cos(lat1)*sin(alpha) + sin(lat1)*cos(alpha)

Then calculate the new longitude, using your result for lat2:

                            cos(alpha) - sin(lat1)*sin(lat2) 
2)    cos(long2-long1) =   ----------------------------------

Again, using lat2 you can calculate the new compass heading:

                      sin(lat1) - sin(lat2)*cos(alpha) 
3)    cos(hdng2) =   ----------------------------------

hdng2 is the compass setting from point 2 to point 1; it's just 180 
degrees from the compass heading that one has when traveling from
point 1 to point 2 and continuing on from there.

The derivation:

I'm a physicist, and I find it natural to think in terms of vectors.  
Going back and forth between expressing the vectors in spherical 
coordinates (r, theta, phi) and in cartesian coordinates (x,y,z) gives 
you a wealth of identities, which are sufficient to solve the kind of 
problem you've posed.

The first useful result from this is that the scalar product (dot 
product) between two vectors can be expressed in two different ways:  
In cartesian coordinates, it's x1*x2 + y1*y2 + z1*z2.  In polar 
coordinates, it's r1*r2*cos(alpha), where alpha is the angle between 
the two vectors.  Now, on the surface of the earth, the angle alpha is 
just the distance between the points divided by the earth's radius.  
This gives you a very useful expression for the distance between any 
two points on the earth's surface.  The quantities x1/r1, y1/r1 and 
z1/r1 are simply related to latitude and longitude of point 1. By 

            z1/r1 = sin(lat1) 
            x1/r1 = cos(lat1)*sin(long1)
            y1/r1 = cos(lat1)*cos(long1)

Identifying the cartesian and polar expressions for the dot product 

cos(alpha)= sin(lat1)*sin(lat2) + cos(lat1)*cos(lat2)*cos(long1-long2)

This is half of your problem right here: it's an expression for the 
distance between any two points on the globe in terms of their 

The other expression you need involves compass headings.  Given that 
you're at point 2 with coordinates as above, and you want to get to 
point 1, what direction should you travel?  The answer is given in 
equation (3) at the top of my answer.  The derivation for this also 
comes from vector manipulations in polar coordinates, but it's a 
little more involved than the one above.

Let r2u be a unit vector from the center of the earth's surface to 
point 2. This unit vector is just a vector that's one unit long, but 
pointing in the same direction as the vector r2.  Let zu be the unit 
vector in the z direction.  Then you can construct a vector that 
points "due north" along the earth's surface from point 2 as: 

       north pointing vector = zu - (zu.r2u)r2u

The period in this expression connotes the scalar product of two 
vectors. Similarly, a vector pointing along the earth's surface from 
point 2 toward point 1 (on a great circle) can be written as:

       heading vector = r1u - (r1u.r2u)r2u

The cosine of the heading angle is just the angle between these two 
vectors. You can get this by taking the scalar product of the two 
vectors and then dividing by the length of each vector separately.  
This is exactly what I did to derive equation (3).

I'm hoping at least the formulas are useful to you, and if you want to 
go through the details of the derivation, please write back.


How Do Satellites Track Mobile Phones? [Technology Explained]

by Guy McDowell on Aug. 8th, 2009

Treo_650_TomTom_NavigatorHave you ever wondered how satellites can track mobile phones? It seems like they’re so far away, yet they can be accurate within about 15 meters. Just how is that done?

The key to tracking any signal, whether it be cellular or radiowave signals, is something called trilateration. In order for trilateration to be used effectively, your phone needs to be picking up on at least 3 satellites – 4, or more, is better.

Your GPS-enabled phone receives a constantly streaming signal, from the satellites, containing information such as the time the signal was sent and the orbital information of the satellite.  Based on that, your phone’s GPS receiver calculates your location in latitude and longitude. It can also calculate your current speed, based on the time between readings and distance covered.

So how exactly does this trilateration thing work?

How Do Satellites Track Mobile Phones?

Imagine a cone extending down from each of the three satellites covering your location. These cones make ellipses, close to circles, when the hit they Earth. Now, you have three intersecting circles. The centers of those circles are then used in a trilateration equation to determine roughly where you are. The point where all three circles intersect is your position. Let’s see how that might look in a simplified view.


The actual equation is more complex than the scope of this article will allow. However, I think this will give you a good high-level understanding of how it all works.

Since the GPS system employs from 24 to 32  global positioning satellites, your position can be determined almost anywhere on Earth. Take a look at the animation below and you’ll see how multiple satellites can transmit to your phone simultaneously. When there are 4 or more satellites transmitting their signal to your phone, the calculation is far more accurate.  Originally, the GPS receivers could only use data from 4 or 5 satellites at once. Now they can use as many as 20.


What can stop it from being tracked is anything that is going to block the line of sight. For instance, if you are in a building, away from a window, the satellites cannot communicate with your cellphone. So it isn’t a foolproof system.

Not all phones have the hardware to be tracked by satellite, but many do. BlackBerry and Treo are popular brands of cellphones that have satellite-trackable models. If your phone has GPS but doesn’t use satellites to trilaterate, then it is relying on the trilateration of cell towers, or even WiFi, to determine your location. Same principle, slightly different technologies.

Once your phone has calculated your position, how does it let anyone else know what that position is? I wasn’t able to find a definitive answer, but I’m led to believe it does it via your cell signal when a call is made,  or SMS. I bet one of our readers has an answer to this question.

50th_space_wingInterestingly, the entire Global Positioning System of satellites is run by the United States Air Force’s 50th Space Wing, located in Colorado. The system has been around for quite some time and was made accessible to the public during President Reagan’s administration.

Of course, there are those people that fear that having their location tracked by their phone will lead to some sort of uber-surveillance. Personally, I don’t see it. How many cellphones are there in the world? What kind of massive server farm would you need to keep track of all that?

Very generally speaking, if law enforcement wants, or needs, to track your phone, then a warrant must be obtained and provided to the service carrier. There are situations of emergency where this process is sped up and may not include the full warrant procedure. Surely you’ve seen at least one story of how a stranded or kidnapped person was found alive, thanks to cellphone GPS services. Due to all those safeguards, the system is reasonably free from abuse and a technology that truly does add to our lives.


Tutorial: JFrame and JPanel

Posted: February 13, 2011 in Java, Uncategorized

JFrame represents a framed window and a
JPanel represents some area in which controls (e.g., buttons, checkboxes, and textfields) and visuals (e.g., figures, pictures, and even text) can appear. Windows can contain/display multiple panels, although in the simplest GUIs, we will associate just one panel with a window.

Swing is a collection of related classes for writing stand-alone Java applications: applets are written using other Java packages.
By extending JFrame, the View subclass inherits hundreds of methods from not only JFrame, but its superclasses: the JFrame class is in a hierarchy whose superclasses include (going upward) Frame, Window, Container, Component, and finally Object).
At the top of this heirarchy is the Component class, which is abstract; objects from its concrete subclasses are displayable on the screen, and have the following important methods (along with many many more): isVisible/setVisible (with a boolean parameter), getSize/setSize (with either a Dimension or two int parameters), getLocation/setLocation (with either a Point or two int parameters), and repaint (parameterless).
The Container class is itself considered a Component, but one that in addition collects together other Components, using a LayoutManager to organize them visually; it takes the role of a composite pattern: when we perform an operation on a Container, it performs that operation on all its Components.
The Window class represents a raw window (e.g., no border) with its own internal coordinate system: (0,0) is the windows upper-left hand corner.
The Frame class represents a window with Border and title area (we can specify various kinds of borders and set its associated icon/title).
Finally, the JFrame class represents a Java compatible window: it has an associated content pane, which shows its visual contents.
origin=upper left corner…… bottom right hand corner= (1280,1024) pixels
JFrame methods

*getLocation which returns a Point object

*getSize which returns a Dimension object

*setLocation and setSize methods, which use objects from these classes as parameters

JFrame headers



*window control(min,max,close)
To read an icon from a file and put it into the header first requires calling the getImage method in the Toolkit class, passing its result to the setIconImage

method.Toolkit tk        = Toolkit.getDefaultToolkit();

Image   titleIcon = tk.getImage(gifFileName);

Finally, the method setVisible (with a boolean parameter) determines whether a JFrame appears on (or disappears from) the screen.


An adapter is a kind of pattern. Typically, it is a concrete class with a variety of stub methods (typically void methods that immediately return) that can be overriden.
WindowAdapte class








In the WindowAdapter class, these methods just return immediately, without doing anything (but these methods exist, and are called when the user clicks a window control button).
The JFrame class inherits (from the Window class) the addWindowListener method from the Window superclass. It “listens” for certain components being clicked and call the appropriate method for each component.
addWindowListener(new WindowAdapter());
Of course, because every method in this class does nothing, we have added no new interesting behavior to the JFrame with this method call. But now, let’s define some interesting behavior when the window is closed. We can define the following class.
public class Terminator extends WindowAdapter {

public void windowClosing(WindowEvent e)    {      System.out.println(“Window closing selected: terminating program”);      System.exit(0);



Java supplies a default constructor for the Terminator class. This class inherits all the stub methods from the WindowAdapter superclass, but it overrides the windowClosing method (the code inside says that when the user clicks the terminate button on this window, print a message, and the entire program itself that created the window should terminate).
Given this class, we can write

addWindowListener(new Terminator());

to give the JFrame the new behavior that we want.
OR we can use the Terminator(sub class) of WindowAdapter(super class) without even mentioning it.
addWindowListener(new WindowAdapter() {

public void windowClosing(WindowEvent e)    {      System.out.println(“Window closing selected: terminating program”);      System.exit(0);


=================The JPanel Class=============
Once we write a JFrame for our GUI, we often add one or more objects to it, each from a subclass extending JPanel. Typically, each sublcass will define some instance variables and a constructor (to initialize them), and overrides the inherited paintComponent method with one that is special to the subclass. The paintComponent method determines what figures, images, and/or text (controls like buttons and textfields are painted automatically) appear on the part of the screen that is owned by the JPanel.
To override the inherited paintComponent method, we must write a void method with one parameter: a reference to an object of type Graphics (called the Graphics context: see the next section for a short discussion of this class), which contains all the methods for drawing figures, images, and text.
The Java runtime system automatically calls this paintComponent method whenever the size of its JFrame is changed, whenever other windows are moved to uncover part of the JFrame, and whenever the JFrame is deiconified after being iconified (subclasses of the WindowAdapter can add special behavior for such events as well).
In all cases, the paintComponent method is called to redisplay the contents of the JPanel, now that the amount of it that is visible has been “changed”.
If we want to call the paintComponent method we must do so by calling a void repaint method.
The screen does not store any information. So whatever we see on the window is whatever is present. If the window is for example maximized then the paintComponent method is called again to display full image.
========JPanel, paintComponent, and the Graphics Context========
Whenever the paintComponent method of a JPanel is called (whether by the Java system or the program itself), it is supplied with a reference to an object from the Graphics class (called its graphics context). The graphics context stores state, including where on the screen the upper-left hand corner of the JPanel is, what is the current color for drawing/text, etc. It does not store anything drawn in the JPanel. The paintComponent method general uses methods from the Graphics class to draw lines, rectangles, ovals, images, and text. In the process, it can change some of these states.
===================Drawing Figures==============

First of all, whenever we specify coordinates, the graphics context will translate them so that (0,0) is the upper-left hand corner of the JPanel. Parts of drawings may go beyond the screen. This is not an error: such parts just won’t be seen.
void drawArc(int x, int y, int width, int height, int startAngle, int arcAngle)

void drawLine(int x1, int y1, int x2, int y2)

void drawOval(int x, int y, int width, int height)
void drawPolygon(int[] xPoints, int[] yPoints, int nPoints)

void drawPolygon(Polygon p)

void drawPolyline(int[] xPoints, int[] yPoints, int nPoints)

void drawRect(int x, int y, int width, int height)

void drawRoundRect(int x, int y, int width, int height,  int arcWidth, int arcHeight)
*Line are straight lines

*ovals are drawn with the specified major and minor axes (circles have these axes the same)

*a polygon is specified either by two parallel arrays of matching x and y coordinates, or a Polygon object (see Javadoc) which stores such arrays internally (and can determine whether a point is in a polygon)

*a polyline is like a polygon, but its last point is not connected to its first

*rectangles come in two flavors: square corners and rounded corners (squares just have their width and height the same.

=====================Drawing Images===============
Here are prototypes for the simplest image methods in the Graphics class.

boolean drawImage(Image img, int x, int y, ImageObserver observer)

boolean drawImage(Image img, int x, int y,  int width, int height, ImageObserver observer)

The x and y values specify the upper-left hand of the image. The first method renders the image in it actual size; the second shrinks or expands it to the dimensions width and height.
=====================Drawing Text===============

Objects in the Font class are constructed, specified by a font name (e.g., SanSerif), style (e.g., plain, bold, italic), and size (e.g., 12 point: specified in points, which is 1/72 of an inch). Objects in the FontMetrics class describe a font, with lots of interesting information: the height and width of characters in the font, ascent and descent, etc.
Here are prototypes for the simplest text methods in the Graphics class.
void drawString(String str, int x, int y)

Font getFont()

FontMetrics getFontMetrics()

FontMetrics getFontMetrics(Font f)

void setFont(Font font)
Note: the x and y values specify the baseline of the the text, not its upper-left hand (the baseline is the bottom of the character, not including the descender). The first method renders the text (using the current font and color) starting at the specified coordinate. Before this statement we might write the following code to specify the font to use and get its metrics.  Font        f1  = new Font(“SansSerif”, Font.BOLD, 14);  FontMetrics f1m = g.getFontMetrics(f1);  g.setFont(f1);  g.setColor(;With any FontMetrics object we can call the stringWidth method with any String: it returns the width of that String using that Font

Standard buttons are constructed from the JButton class (in the javax.swing package). As with other controls, they inherit hundreds of methods. The typical constructor specifies a String to use as a label for the button (or we can call setLabel with any String later). We can also call inherited methods such as setFont, setBackground, and setForeground, although most standard buttons use default values for these. We can also call the setEnabled method (with a boolean parameter) to tell Java whether a button is pressable (if not, its label will appear as a faded color).
Here is an example of declaring a JButton and performing many of these operations.
JButton b = new JButton(“Cold”);

b.setFont(new Font(“Monospaced”,Font.BOLD,12));



Finally, we can use the add method to add any kind of Component to a JPanel.

This is a stripped version of a tutorial on JFrames and JPanels. To read the complete tutorial visit

Interrupt Requests (irqs)

Posted: February 10, 2011 in Uncategorized

Interrupt Requesting (IRQ) is a computer system performance enhancing technology that plays a key role in how the CPU performs input/output processing and interfaces with every peripheral in the computer, from the keyboard and mouse to the hard disk and modem. It is through IRQ prioritization that the CPU juggles multiple concurrent tasks thereby giving the impression that it is doing many things at once.

A computer’s main processor (CPU) is a highly-tuned machine that is designed to (basically) do one thing at a time. For example; execute the current instruction or operation. However; because of the way in which we humans work and use computers, we require the CPU to do many things at once (or at least to seem to be doing many things simultaneously).

Multitasking – Projecting the impression that it (the CPU) is performing many tasks simultaneously is known as “multitasking”. Modern CPUs contain multiple processing pipelines and the newer CPUs of today actually have multiple processing cores each with its own full complement of multiple processingpipelines.

This latter development (multiple complete processing cores) has indeed given the CPU the capability to perform multiple tasks simultaneously and not merely just seem to be doing so. The way in which processing tasks are managed and distributed among the multiple processing pipelines of the multiple cores is however; still achieved in pretty much the same way that it has always been done.

Multitasking Operating System – When using multitasking operating systems (like Windows, Mac OS X, and Linux etc.) users tend to have multiple programs, utilities and applications running concurrently/simultaneously. For example you may be: editing a word document, downloading from the Internet and listening to music.

In order to be able to do this the CPU will share its processing time among the tasks requiring its attention including user initiated tasks, the operating system, programs, utilities, memory management and quite a few “background” services and routines. It only appears that the processor is doing many things at once because of the incredible speeds that modern CPUs are able to switch between tasks.

Communicating with the CPU – The majority of the subsystems in a PC need to send information to and receive information from the CPU and system memory (RAM). Most also expect to be able to get the CPU’s attention when they do so.

In order to improve a computer’s overall efficiency the CPU also needs to balance the data transfers between itself and the various other subsystems of the machine. In addition; some of a computer’s subsystems such as input/output (I/O) devices and human interface devices, all tend to require “special” attention.

Different Requirements – Another influential factor here is that different devices require different amounts of CPU time at various different irregular intervals.

The mouse; for example, needs far less attention than a hard disk involved in the transference of a large multi-gigabyte file. Thus; in the interest of a more efficient use of a computer’s finite resources, it is most beneficial if the amount of CPU time assigned to each device reflects the type of device and the nature of the operation and processing tasks involved.

In the above example of the resource needs of the mouse versus those of the hard drive; more resources can be allocated (even dedicated) to the hard drive for the duration of its current operation(s) while the mouse gets a smaller amount of CPU time.

When the hard drive is finished its current task(s) it may not be required to perform any transactions for various irregular periods of time. The system will then reassign those resources that were being used by the hard drive to other devices and processes as and when required.

Managing Processes – The computer (via the CPU) must also ensure that all active (running) processes and tasks are managed in the most efficient organized manner possible. There are basically 2 ways in which this can be done: CPU polling and device initiated interrupting.

Polling – Polling is the process whereby the CPU systematically locates and asks each device in turn if it requires any help or CPU processing time. This strategy (polling) is a very inefficient process because it is a waste of finite resources.

With polling the CPU is required to continually perform the same tasks (asking each device if it needs the CPU’s attention) over and over again. More often than not the device will not require the CPU’s attention. Statistically; the most likely answer or result of a hardware polling query is that which it received last time (offer declined).

With polling the CPU will continue to ask each device in sequence the same question ad infinitum. To overcome polling’s inefficiency a different strategy; known as “Interrupting”; also referred to as Interrupt Request (IRQ), was developed.

Interrupting – The other way that the CPU (processor) can employ to handle CPU required processes and data transfers is to have the devices requiring the CPU’s attention to issue a request for attention as and when they require it. This is the basic concept of interrupt requests.

Thus when a device has data to transfer, it generates an interrupt that says “Mr. CPU I need your attention now, please”. The processor then stops what it is doing and deals with the device that requested its attention. Modern CPUs can handle many such requests at a time. In the event of multiple simultaneous interrupt requests the CPU uses a priority system that gives a priority status to interrupt requests based upon the priority associated with the device issuing the request. This is known as Interrupt Request Management.

Supply and Demand – One way of looking at interrupt requests is from a supply and demand perspective. While; having the CPU interrupted all the time may at first glance appear to be an inefficient way to run a computer, when examined closer reality proves otherwise. A large part of the reason is that the modern CPU is literally light years ahead; in terms of speed, when compared to the vast majority of devices conducting transactions with it. To put it into perspective let us consider the following scenario:

Let us suppose that a typist is typing at a rate of 120 words per minute and that on average there are five letters per word. This equates to the typist producing 600 characters of keyboard input per minute. This means that an old 200 MHz Pentium class CPU will process 20,000,000 instructions between each keystroke.

This is why having the processor spend a lot of time asking the keyboard if it needs any help would be wasteful, especially since the typist may at any time you might stop for a minute or two to review the copy, or do something else like make a cup of coffee. In fact; even while handling a full-bandwidth transfer from a 28,800 Kb/sec modem, which of course moves data much faster than the typist’s fingers, the processor has over 60,000 instruction cycles between the bytes it needs to process.

Hardware Interrupts – Hardware interrupts such as those mentioned above (typing/keyboard input and modem transfers) are distinguishable from software interrupts by the fact that they generally originate from a device outside the CPU. Table 1 below shows the default IRQs in order of descending priority.

Software Interrupts – There is another type of interrupt that occurs in modern PCs; known as software interrupts. These are generated by the operating system, programs and various other software applications and are used by various software programs in response to different events that occur as the operating system and applications run.

In essence a software interrupt represents the CPU interrupting itself (as the interrupt originates from within the CPU) and is part of the reason of how the CPU is able to do many things at once.

Basic Input/Output System (BIOS) – A computer’s BIOS provides various software routines (subprograms) that can be called by higher-level software such as DOS, Windows, or their applications, to perform different tasks. This includes actions like reading and writing from the hard disk, processing information received from devices, etc.

BIOS Access – Another performance enhancing functionality that software interrupts make possible is facilitating system software (DOS or the operating system), applications and other software to directly access one another via BIOS routines without having to know where the target application resides in memory.

Interrupt Vector Table – Normally, to call a software routine you need to know its address (location) in memory. However; with interrupt requests a table called an interrupt vector table is created and this is used to bypass the need to explicitly know the correct address in memory. Now every time the system is booted, the BIOS puts addresses representing where its routines are located for each interrupt that it is configured to respond to.

So whenever DOS, the operating system or other applications want to use a BIOS routine, it generates a software interrupt. The system processes the interrupt, looks up the value in the interrupt vector table and then automatically jumps directly to the appropriate BIOS routine. Modern operating systems and applications as well as DOS can also directly use this interrupt vector table.

BIOS Bypass – More recently newer operating systems bypass the BIOS totally as this does help improve system performance.

BIOS Assigned Logical Names – The BIOS assigns logical names to devices based on their IRQ number and memory address. For example:

IRQ 3 and I/O address 2F8-2FFh becomes Com2.

Legacy Devices Default Settings – For older systems; such as those based around the ISA bus, it is often the case that the default IRQ assignments must be preserved. This necessity is most common with older software and games that require the ISA SoundBlaster sound card to be accessible using the following configurations:

IRQ 5, I/O Address 220h and DMA 1

Failure to comply will result in; at best no in game sound and at worst no game at all.

Interrupt Summary – In short; interrupt requests are a mechanism that allows the various devices and software that make up a computer to jump the processing queue in order to have tasks of a predetermined “higher” priority to be executed “out of turn”. BIOS services are accessed using software interrupts, which are similar to the hardware interrupts except that they are generated inside the CPU by programs instead of being generated outside the CPU by hardware devices.

Read more:


The real cost of sms bandwidth: Rs.83886.08 per Gigabyte

When developers started marketing cellphone services, did they ever think that the real money spinner would be the humble sms service?

Let’s have a closer look on how much do we pay for 1GB of sms. Telenor offers 700 sms’ for Rs.8 for a week. It means price of a single sms is 0.011  (8/700)  paisa, looks quite cheap? Lets examine more.

A standard SMS message contains up to 140 bytes (1120 bits) of data – this takes care of the 160 characters allowed in your text message. This might not make sense at first, until you realize that SMS uses 7 – not 8 – bit characters – leaving you with 128 possible character values instead of the normal 256. So 1120bits/7bits = 160 characters.

So our total message length is about a tenth of a kilobyte (.13671875 Kbytes). That gives us 7 messages on a kilobyte. There is 1024 kilobytes on a Megabyte that gives us 7168 messages on a megabyte. Again there is 1024 megabytes in a Gigabyte that gives us 7340032 messages on a gigabyte. Our sms’s will then cost us Rs.83886.08 per Gigabyte.

Big questions asked:

Why are we being ripped of by the cell phone providers? the argument in favour of the data providers usually alludes to the costs of maintaining the network, but here are the facts:

The marginal cost of a SMS is 0. SMS messages are sent on the control channel. Initially SMS were implemented in the GSM standard as a control system, just like the ICMP protocol of the IP stack. Then NOKIA though to implement a actual instant message function using SMS. The Contol channel is the channel that your mobile listens to in order to receive calls. So for receiving a SMS a control signal is sent. Since bandwidht is somehow limited on these channels it could happen that in a situation of massive usage of texting the control channel gets saturated and normal voice protocol initiation is disrupted. To prevent this carriers nowadays apply a kind of QoS delaying SMSs until there is no risk of congestion. So we can state that the marginal cost is 0 and the cost/opportunity is also 0.

There is a case for opportunity cost, where a provider charges a premium for the opportunity of making our lives easier, and that is true for a sms. I’m surely not advocating that there should not be any premium for the cellphone providers given the nature of the sms, I’m just asking for a fair price. That is all.

The article has been re- written considering the sms price in Pakistan.


Android Architecture part 1

Posted: February 9, 2011 in Android, Uncategorized

Howto: Ubuntu Linux convert DHCP network configuration to static IP configuration

by Vivek Gite on September 13, 2006 · 72 comments

My friend wanted to know how to change or convert DHCP network configuration to static configuration. After initial installation, he wanted to change network settings. Further, his system is w/o GUI system aka X Windows. Here is quick way to accomplish the same:

Your main network configuration file is /etc/network/interfaces

Desired new sample settings:
=> Host IP address
=> Netmask:
=> Network ID:
=> Broadcast IP:
=> Gateway/Router IP:
=> DNS Server:

Open network configuration file
$ sudo vi /etc/network/interfacesOR$ sudo nano /etc/network/interfaces

Find and remove dhcp entry:
iface eth0 inet dhcp

Append new network settings:

iface eth0 inet static

Save and close the file. Restart the network:
$ sudo /etc/init.d/networking restart

Task: Define new DNS servers

Open /etc/resolv.conf file
$ sudo vi /etc/resolv.conf

You need to remove old DNS server assigned by DHCP server:

Save and close the file.

Task: Test DNS server

$ host

Network command line cheat sheet

You can also use commands to change settings. Please note that these settings are temporary and not the permanent. Use above method to make network changes permanent or GUI tool as described below.

Task: Display network interface information

$ ifconfig

Task: Take down network interface eth0 / take a network interface down

$ sudo ifconfig eth0 downOR $ sudo ifdown eth0

Task: Bring a network interface eth0 up

$ sudo ifconfig eth0 upOR$ sudo ifup eth0

Task: Change IP address and netmask from command line

Activate network interface eth0 with a new IP ( / netmask:
$ sudo ifconfig eth0 netmask up

Task: Display the routing table

$ /sbin/route OR$ /sbin/route -n

Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
localnet        *        U     0      0        0 ra0    *        U     0      0        0 eth0    *        U     0      0        0 eth1
default         UG    0      0        0 ra0

Task: Add a new gateway

$ sudo route add default gw

Task: Display current active Internet connections (servers and established connection)

$ netstat -nat

Task: Display open ports

$ sudo netstat -tulpOR$ sudo netstat -tulpn

Task: Display network interfaces stats (RX/TX etc)

$ netstat -i

Task: Display output for active/established connections only

$ netstat -e
$ netstat -te
$ netstat -tue


  • -t : TCP connections
  • -u : UDP connections
  • -e : Established

Task: Test network connectivity

Send ICMP ECHO_REQUEST to network hosts, routers, servers etc with ping command. This verifies connectivity exists between local host and remote network system:
$ ping router
$ ping
$ ping

See simple Linux system monitoring with ping command and scripts for more information.

Task: Use GUI (Graphical Configuration) network Tool

If you are new, use GUI configuration tool, type the following command at terminal:
$ network-admin &

Above command is Ubuntu’s GUI for configuring network connections tool.

Final tip – Learn how find out more information about commands

A man page is your best friend when you wanted to learn more about particular command or syntax. For example, read detailed information about ifconfig and netstat command:
$ man ifconfig
$ man netstat

Just get a short help with all command options by appending –help option to each command:
$ netstat --help

Find out what command is used for particular task by searching the short descriptions and manual page names for the keyword:
$ man -k 'delete directory'
$ apropos -s 1 remove

Display short descriptions of a command:
$ whatis rm
$ whatis netstat

Linux offers an excellent collection of utilities, which can be use to finding the files and executables, remember you cannot memorize all the commands and files 😉

Anatomy of a Program in Memory

Posted: January 17, 2011 in Uncategorized

Gustavo Duarte
Software, computers, and business.

Anatomy of a Program in Memory

Memory management is the heart of operating systems; it is crucial for both programming and system administration. In the next few posts I’ll cover memory with an eye towards practical aspects, but without shying away from internals. While the concepts are generic, examples are mostly from Linux and Windows on 32-bit x86. This first post describes how programs are laid out in memory.

Each process in a multi-tasking OS runs in its own memory sandbox. This sandbox is the virtual address space, which in 32-bit mode is always a 4GB block of memory addresses. These virtual addresses are mapped to physical memory by page tables, which are maintained by the operating system kernel and consulted by the processor. Each process has its own set of page tables, but there is a catch. Once virtual addresses are enabled, they apply to all software running in the machine, including the kernel itself. Thus a portion of the virtual address space must be reserved to the kernel:

Kernel/User Memory Split

This does not mean the kernel uses that much physical memory, only that it has that portion of address space available to map whatever physical memory it wishes. Kernel space is flagged in the page tables as exclusive to privileged code (ring 2 or lower), hence a page fault is triggered if user-mode programs try to touch it. In Linux, kernel space is constantly present and maps the same physical memory in all processes. Kernel code and data are always addressable, ready to handle interrupts or system calls at any time. By contrast, the mapping for the user-mode portion of the address space changes whenever a process switch happens:

Process Switch Effects on Virtual Memory

Blue regions represent virtual addresses that are mapped to physical memory, whereas white regions are unmapped. In the example above, Firefox has used far more of its virtual address space due to its legendary memory hunger. The distinct bands in the address space correspond to memory segments like the heap, stack, and so on. Keep in mind these segments are simply a range of memory addresses and have nothing to do with Intel-style segments. Anyway, here is the standard segment layout in a Linux process:

Flexible Process Address Space Layout In Linux

When computing was happy and safe and cuddly, the starting virtual addresses for the segments shown above were exactly the same for nearly every process in a machine. This made it easy to exploit security vulnerabilities remotely. An exploit often needs to reference absolute memory locations: an address on the stack, the address for a library function, etc. Remote attackers must choose this location blindly, counting on the fact that address spaces are all the same. When they are, people get pwned. Thus address space randomization has become popular. Linux randomizes thestackmemory mapping segment, and heap by adding offsets to their starting addresses. Unfortunately the 32-bit address space is pretty tight, leaving little room for randomization andhampering its effectiveness.

The topmost segment in the process address space is the stack, which stores local variables and function parameters in most programming languages. Calling a method or function pushes a newstack frame onto the stack. The stack frame is destroyed when the function returns. This simple design, possible because the data obeys strict LIFO order, means that no complex data structure is needed to track stack contents – a simple pointer to the top of the stack will do. Pushing and popping are thus very fast and deterministic. Also, the constant reuse of stack regions tends to keep active stack memory in the cpu caches, speeding up access. Each thread in a process gets its own stack.

It is possible to exhaust the area mapping the stack by pushing more data than it can fit. This triggers a page fault that is handled in Linux by expand_stack(), which in turn callsacct_stack_growth() to check whether it’s appropriate to grow the stack. If the stack size is belowRLIMIT_STACK (usually 8MB), then normally the stack grows and the program continues merrily, unaware of what just happened. This is the normal mechanism whereby stack size adjusts to demand. However, if the maximum stack size has been reached, we have a stack overflow and the program receives a Segmentation Fault. While the mapped stack area expands to meet demand, it does not shrink back when the stack gets smaller. Like the federal budget, it only expands.

Dynamic stack growth is the only situation in which access to an unmapped memory region, shown in white above, might be valid. Any other access to unmapped memory triggers a page fault that results in a Segmentation Fault. Some mapped areas are read-only, hence write attempts to these areas also lead to segfaults.

Below the stack, we have the memory mapping segment. Here the kernel maps contents of files directly to memory. Any application can ask for such a mapping via the Linux mmap() system call (implementation) or CreateFileMapping()MapViewOfFile() in Windows. Memory mapping is a convenient and high-performance way to do file I/O, so it is used for loading dynamic libraries. It is also possible to create an anonymous memory mapping that does not correspond to any files, being used instead for program data. In Linux, if you request a large block of memory via malloc(), the C library will create such an anonymous mapping instead of using heap memory. ‘Large’ means larger than MMAP_THRESHOLD bytes, 128 kB by default and adjustable via mallopt().

Speaking of the heap, it comes next in our plunge into address space. The heap provides runtime memory allocation, like the stack, meant for data that must outlive the function doing the allocation, unlike the stack. Most languages provide heap management to programs. Satisfying memory requests is thus a joint affair between the language runtime and the kernel. In C, the interface to heap allocation is malloc() and friends, whereas in a garbage-collected language like C# the interface is thenew keyword.

If there is enough space in the heap to satisfy a memory request, it can be handled by the language runtime without kernel involvement. Otherwise the heap is enlarged via the brk() system call (implementation) to make room for the requested block. Heap management is complex, requiring sophisticated algorithms that strive for speed and efficient memory usage in the face of our programs’ chaotic allocation patterns. The time needed to service a heap request can vary substantially. Real-time systems have special-purpose allocators to deal with this problem. Heaps also becomefragmented, shown below:

Fragmented Heap

Finally, we get to the lowest segments of memory: BSS, data, and program text. Both BSS and data store contents for static (global) variables in C. The difference is that BSS stores the contents ofuninitialized static variables, whose values are not set by the programmer in source code. The BSS memory area is anonymous: it does not map any file. If you say static int cntActiveUsers, the contents of cntActiveUsers live in the BSS.

The data segment, on the other hand, holds the contents for static variables initialized in source code. This memory area is not anonymous. It maps the part of the program’s binary image that contains the initial static values given in source code. So if you say static int cntWorkerBees = 10, the contents of cntWorkerBees live in the data segment and start out as 10. Even though the data segment maps a file, it is a private memory mapping, which means that updates to memory are not reflected in the underlying file. This must be the case, otherwise assignments to global variables would change your on-disk binary image. Inconceivable!

The data example in the diagram is trickier because it uses a pointer. In that case, the contents of pointer gonzo – a 4-byte memory address – live in the data segment. The actual string it points to does not, however. The string lives in the text segment, which is read-only and stores all of your code in addition to tidbits like string literals. The text segment also maps your binary file in memory, but writes to this area earn your program a Segmentation Fault. This helps prevent pointer bugs, though not as effectively as avoiding C in the first place. Here’s a diagram showing these segments and our example variables:

ELF Binary Image Mapped Into Memory

You can examine the memory areas in a Linux process by reading the file/proc/pid_of_process/maps. Keep in mind that a segment may contain many areas. For example, each memory mapped file normally has its own area in the mmap segment, and dynamic libraries have extra areas similar to BSS and data. The next post will clarify what ‘area’ really means. Also, sometimes people say “data segment” meaning all of data + bss + heap.

You can examine binary images using the nm and objdump commands to display symbols, their addresses, segments, and so on. Finally, the virtual address layout described above is the “flexible” layout in Linux, which has been the default for a few years. It assumes that we have a value forRLIMIT_STACK. When that’s not the case, Linux reverts back to the “classic” layout shown below:

Classic Process Address Space Layout In Linux