Bit Maipulations

Most hated area in programming. Anyways here you go few important examples.

1) given 32 bit integer, swap ith and jth positions
swap(int n,int i,int j)
{
    if( (n & 1<<i)>>i ^ (n & (i<<j))>>j) ) // if bits i and j are different
    {
        n^= 1<<i;
        n^= 1<<j;
    }
    return n;
}

2) check 9th bit ser or not
return (number & (position - 1 ) ;

3) To find the number of zeros in an integer
int zerocount(int n)
{
    int ctr  = 0 ;
    while (n>0) {
        ctr = ctr + !(n & 1 ) ;
        n = n << 1 ;
    }
    return ctr ;
}

4) ip string to integer
uint ip2int(char *str)
{
    uint x = 0 ;
    char *tok = strtok(str, ".") ;
    for (i=3; tok != NULL; i--) {
        ans |= atoi(tok) << (8*i)) ;
        tok = strtok(tok, ".") ;
    }
    return tok ;
}

5) MSB of a number
int IsMSB(int x)
{
    if (x & 0x8000)
        printf("msb = 1") ;
    else
        printf("msb = 0") ;
}

6) count bits
int count(uint x)
{
    int i ;
    while (x) {
        x = x & (x-1) ;
        i++ ;
    }
    return i ;
}

7) result = a?b:c
 result = !!a * b + !a * c;

8) #define mysize(x) ((char*) &x+1) - ((char*) &x)  ;

9) multiply by power of 2
n << 2 ;

10) set a bit
unsigned char a = a  | (1<<n) ;

11) clear a bit
unsigned char b = b & ~(1<<n) ;

12) toggle a bit
unsigned char c = c ^ (1<<n) ;

13) test a bit
unsigned d = c & (1<<n) ;

14) right most bit
uchar right = val & 0xff ;
uchar left = (val>8) & 8 ;

Good hash function for strings

This is called Horner's rule
int hash(string str) {
    int h = 0;
    for (int i=0; i<str.length - 1 ; i++) {
        h = (str[i] + 128*h) % tableSize ;
    }
    return h ;
}
hash(s) = s1+s2*128+s3*128+s4*128+.....+sn*128

OSPF notes

Few things about OSPF protocol
packet type = 1 -- hello
packet type = 2 -- data base description packets
packet type = 3 -- link state request
packet type = 4 -- link state update
packet type = 5 -- link state ack

hello packets are used to keep alive the session between 2 peers.
DBD packets used for initial synchronization. These packets contain the initial links there were connected.
This also contains the some link states that are marked as a need to get complete link details.

packet type 3 -- In DBD process, few links are marked will be sent in these packets. This requests new/latest data
for LSA is required.

packet type 4 -- This is response for packet type 3. This will contains the updates of lsa those are requested from peer.

packet type 5 -- link state ack. The final/full stage where both peers have their database are synchronised. From here onwards
actual dijsktra's algorithm will be executed.

lsa types
type 1 -- router lsa .. flooded within area. Contains the information about connected links, intefaces, cost etc. Link id is router id
type 2 -- network lsa .. are generated by designated router. link id is interface ip address of the designated router.
           describes the routes connected to the network.
type 3 -- summary lsa .. Generated by ABRs. The networks are flooded into another area. link id is network number advertised.
type 4 -- summary lsa .. Generated by ABSs. Contains routes to ASBR. link id is asbr id and these are not allowed into stub areas.
type 5 -- external lsa .. Generated by ASBRs, contain the routes to networks that are not external to current as. AS to AS communication.
type 6 -- multicast lsa .. used for multicast applications.
type 7 -- nssa external lsa ..


non broadcast over ospf framerelay
dr/bdr election takes place.
neighbour discovery will not be automated.
Add neighbour statment in ospf.
set ospf priority 0 for all routers who pvc is connection from only 1 router.

ospf point to multipoint over frame relay
no dr/bdr election process.
neighbours will be detected automatically.
command to add is
ip ospf network point-to-multipoint

Redistribution
redistributes routes from eigrp routers to r1.
E1 routes are from other protocols where cost will be calculated with default metric + recevied metric.
E2 routes will only contain the default met ric
command for redistribution from eigrp into  ospf as follows
# redistribute eigrp 1 metric-type 1 subnets  --- this is generates E1 type routes
# redistribute eigrp 2 metric-type 2 subnets  --- This will generate E2 type routes.
subnets keyword specifies redistribution whether classful or classless.
If present classful and classless redistribution takes place
if absent only classful redistibution takes place.

redistribution with route-maps
define acl
define route-maps for acl either to permit/deny
define route-map parameter in redistribution command

Example
ip acces-list 10
    10 permit <ip> <subnet mask>
    20 deny <ip> <subnet mask>

route-map domain1-ospf permit 10
    match ip address 10
    set metric 200
    set metric-type type 2

Difference between shared memory and message queue

Both shared memory and message queues can be used to exchange information between processes.The difference is in how they are used.

Shared memory is exactly what you'd think: it's an area of storage that can be read and written by more than one process.
 It provides no inherent synchronization; in other words, it's up to the programmer to
 ensure that one process doesn't clobber another's data.
  But it's efficient in terms of throughput: reading and writing are relatively fast operations.

A message queue is a one-way pipe: one process writes to the queue,
and another reads the data in the order it was written until an end-of-data condition occurs.
When the queue is created, the message size (bytes per message, usually fairly small)
and queue length (maximum number of pending messages) are set.
Access is slower than shared memory because each read/write operation is typically a single message.
But the queue guarantees that each operation will either processes an entire message successfully or fail
 without altering the queue. So the writer can never fail after writing only a partial message, and
 the reader will either retrieve a complete message or nothing at all.

How GDB works

At a very high level gdb works as below. Check for the actual implementation for more details.
ptrace system call will be used for tracing the program. It has 4 arguments
1) operation
2) target pid
3) address in the target process memory
4) data pointer

The last arguments depends on operation.
For example, to attach debugger
ptrace(PTRACE_ATTACH, pid, 0, 0) ;
ptrace(PTRACE_DETAACH, pid, 0, 0) ;

single step execution
ptrace(PTRACE_ATTACH, pid, 0, 0) ;
int status ;
waitpid(pid, &status, WSTOPPED) ;
while (...) {
    ptrace(PTRACE_SINGLESTEP, pid, 0, 0) ;
    // give the user a chance to do something
}
ptrace(PTRACE_DETACH, pid, 0, 0) ;
I dont know who will write new debuggers, where we have freely the best GDB available. :-).

Structure containing zero length member

It is called unwarranted chumminess with the C implementation
This shows how to use the structure containing zero element

struct test
{
    int len ;
    char str[1] ;
} ;

struct test* fun(char *name)
{
    struct test *ptr = malloc(sizeof(struct test)) ;
    if (ptr)
    {
        ptr->len = strlen(name) ;
        ptr->str = malloc(ptr->len+1) ;
        strcpy(ptr->str, name) ;
    }
    return ptr ;
}

Difference between macros and inline functions

Difference between macros and inline functions
1) macros are text replacement. The macro will be expanded in preprocessing time, but inline functions are replaced during compile time. They are just normal functions.
2) macros have following problems
    a) There is no typechecking for macro arguments
    b) Macros results ambiguity if properly not created.
        # define product(a) a*a
        will cause wrong result when called
        result = product(++a) if a = 10
        This will expand to
        product(++10) (++10*++10) = 120 but actually expected is
        a = 10
        result = product(++10) i.e 11
        result = 121
    c) One more problem if multiple statements
    #define multi(a,b) a+=10; b+=20
    if the above macro called within if statement
    if (flag){
        multi(a,b)
    }
    will become
    if (flag){
        a+=10;
    }
    b += 20 ;
3) All above problems will not occur when inline functions are used
4) Since macros are expanded in preprocessing time, there wont be any symbols available for debugger
5) With inline functions you can easily debug functions.

Caution: One of the important thing to know about MACRO.. :-(
#define INIT_LIST_HEAD(ptr) do {
    (ptr)->next = (ptr) ; \
    (ptr)->prev = (ptr) ; \
    } while (0)
If there is no do while then the following is invalid
if (foo)
    INTI_LIST_HEAD(ptr)
to
if (foo)
    (ptr)->next = (ptr) ;
    (ptr)->prev = (ptr) ;
   
but if do while is present then
if (foo)
    do {
        (ptr)->next = (ptr) ;
        (ptr)->prev = (ptr) ;
    while (0)
The above is valid

Simple wrapper examples for networking code

Following are few wrappers used for networking code.. Mainly for sockets

int nRead(int fd, char* ptr, int nBytes)
{
    int nleft = nbytes ;
    int nread ;
   
    while (nleft>0)
    {
        nread = read(fd, ptr, nleft) ;
        if (nread == 0)
            break ;
           
        if (nread<0)
            return nread ;
           
        nleft = nleft - nread ;
       
        ptr = ptr+nread ;
    }
   
    return nbytes - nleft ;
}
   

int nWrite(int fd, const char* ptr, int nBytes)
{
    int nleft = nBytes ;
    int nwrite ;
   
    while (nleft >= 0)
    {
        nwrite = write(fd, ptr, nleft) ;
        if (nwrite <=0)
        nleft = nleft - nwrite ;
        ptr = ptr + nwrite ;
    }
    return nBytes - nleft ;
}
           
int setNonBlocking(int fd)
{
    int flags ;
    if (flags = fcntl(fd, F_GETFL) < 0)
    {
        perror("GETFL") ;
        return -1 ;
    }
   
    if (fcntl(fd, F_SETFL | flags) < 0)
    {
        perror("SETFL") ;
        return -1 ;
    }

    return 0 ;
}

Few questions to help for interviews

Below are few questions shared by my friends since 4 years. These are not ordered correctly. Many questions are repetitive. I have not cleared yet.
Skill set: C,C++,linux, gdb, telcom, networking(l2/l3/l7), sip etc.

1) Design patterns used in project.
2) Troubleshooting skills. How do you troubleshoot.
3) If there is an issue reported at site and manager is out of office, then how do you handle the situation.
4) Explain observer design pattern and polymorphism.
5) what is conitnues integration testing.
6) which automation testing tools used for unit testing.

1) what are the difference between semaphore and mutex.
2) Can we use these to ipc
3) what are the default functions given by c++
4) override default constructor
5) difference between message queue and pipe
6) how hash table works
7) can mutex will be shared to other processes.

how copy constructors are created, use pointers .. read the stuff
how singleton classes implemented, use pointers and static methods
difference between sctp and tcp
header about tcp, 3 way handshake. use seq numbers, ack etc

1) difference between point code and global title.
2) which link used for ss7(dialogic)
3) what is segmentation violation.
4) what is stack unwinding.
5) what is vtable.
6) vtable with example.
7) Difference between deep copy and shallow copy.

1) how to set/reset a particular bit on the number.
2) what is the size of structure -
   struct a
   {
      uint32_t a;
      uint_8 b;
   };
   the size is 8 bytes.
3) how to add ip address using the command.
4) how to check the ip address in windows.
5) what is L2 switch. what is vlan. study basics.
6) what is fragmentation. Explain flags and procedure.
7) worked on tcp or not.

1) how traceroute is implemented.
2) IF the packet is looping between 2 routers, when this packet will be discarded.
3) what is the field to identify L3 in ethernet frame.
4) what is deadlock and how to avoid.
5) simple example for raising segmentation violation.
6) if there are 1000 rooms and I want to find the person correctly, which data structure you will use.
7) what is volatile variable.
8) what are different segements to store the data in program.
9) what will be stored in function calls.
http://www.tenouk.com/Bufferoverflowc/Bufferoverflow2a.html
10) what will be stored in context switch.
11) which data structures used.
12) If there are 3 threads writing message Q and 1 thread reading, which synchronization will be used.


what are the 4 basic concepts of oops, explain with example.
what is polymorphism used in your project
what is deadlock and how to prevent.
How semaphores worked
what are message queues
what are the problems with shared memory segments
what are different types of IPCs
what are different kind of design patterns used. Singleton, command, factory.
Explain the design patterns used. Logger, configuration reading etc. Factory class examples.
how data will be shared between 2 threads.
what are different kind of mechanism for synchronization
what are the difference between mutex and semaphore.
How to detect memory leaks and what are the tools used. (mdb, dbx, valgrind, gdb)
what is memory pool. where this pool will be used. Normally we can use tdynHash functions(Hash table data structure) to store the messages. States will be stored.
How to manage the dynamically allocated memory.
what are message queues...

what are threads.
When threads will be used.
why threads are required, not the difference between thread and process.
What is parellel processing.
If I have 2 cores, and 2 threads, then threads will help here. Basically how wanted to know how threads will be used.
what is buffer size of tcp.
If I have 2 GB bytes of data, then who will manage the chunks of data either in application(socket) or IP layer will do this.
what is MTU size. Read more about this
How to store the elements from the container which is having duplicate elements. What is time complexity.
Singleton class implementation with thread safe.
What is atomicity and how it is different from synchronization.

how to detect memory corruption. He has given hint as watch point. Not sure how it will be used.
what are the difference between fib and rib
what are the difference between is-is, rip, ospf.
explain semaphore, mutex and binary semaphore
what are static functions


programs
Reverse a linked list
count the number of bits in the number
delete linked list
swap nibbles in a byte
swap even/odd positions

what are static functions
what are volatile variables.
have u used linux internals
difference between semaphore and mutex.
different kinds of IPC's used
priority for threads
bit operations
order even and odd numbers
count the number of 1's
 detailed level packet flow from router1 to router2.

tcp/ip connection/termination details in detail
mmap usage
sockets example call flow
linked list to detect loop and startting point
stack overflow example : call main within main()
detect starting point of loop, below description
Step1: Proceed in the usual way u'll use to find the loop. ie. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.
Step2: Freeze one pointer where it was and increment the other pointer in one step counting the steps u make and when they both meet again, the count will give u the length of the loop.(This is same as counting the number of elements in a circular link list.)
Step3: Reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it'll be the start of the loop. (This is same as finding the nth element from the end of the link list.)

what happens if there are 2 routes for ospf?
how fragmentation works.. explain the fields



1) is it possible to reassmeble the packet at host? from IP fragmentation
2) how to control congestion in tcp networks
3) what is 3 way hand shake?
4) does ospf can travel within subnet
5) create hash function which accepts string as an argument
6) delete last node of linked list
7) what is static variable and where it is stored? same for static functions
8) what happens to thread if try to lock the locked mutex.
9) what is segmenation violation and how to detect.
10) ipcs: message queue? how it is different from other ipc mechanism.
11) a function pointer pointing to static function? can we access this variable.
12) what is piggy backing?



1) what are different types of lsa
2) how bfd helps
3) which data structure used to construct lsa
4) can balanced tree become unbalanced
5) LMP(longest match prefix) which ds use
6) what happens if main program exits (it created 5 threads)
7) scaling: Have you faced any problems in scalability. How to improve.
8) Lots of questions of scalling.
9) Does router lsa floods the routes?
10) Does bfd is L2/L3 protocol.
11) what are the issues fixed in code.
12) What are the operations done on data structures? tree.. and how these are used in ospf software.

Static functions

Why people love to ask about static functions is no idea. But the fact is that static functions are just an extra-ordinary functions compared to normal functions.

Gotchas while using Static functions.
1) Static functions are limited to file where they are declared.
2) You can define the same name of the function in another file.
3) Global functions have global scope, meaning function defined in one file can be accessed by other module.

Example for static function
File1.c
static void fun1()
{
    printf("I am a static function") ;
    return ;
}

The keyword static  makes the function as static and the call will be used only within File1.c file.

Another example
File2.c
static void Func2()
{
      printf("Another static demo\n") ;
      return ;
}

File3.c
void Func2()
{
     printf("This is normal function") ;
     return ;
}

main.c
int main()
{
    Func2() ;
    Func2() ;
}

The fuction Func2() is defined twice. If static function was used you will get an error. Both File2.o and File3.o can used to create an executale main.o(main.c).

function pointers

Like pointer to data(int, char, struct etc) we can have pointer to functions as well.
The convention to use function pointer is same as calling the name of the function.

Example:
// function to be called via function pointer. Note the return type and arguments
void testFunction(int data)
{
     // Do something on data
     printf("%d is the number passed via function pointer\n", data) ;
     return ;
}

// Main function

int main()
{
   // funPtr is function pointer, returning void and accepting an int
  //  void (*funPtr)(int)  ;
  // Now point funptr to point the right function
  void (*funPtr)(int)  = &testFunction;   // &testFunction is address of fun stored, try printing *testFunction or *funPtr

 *funPtr(10) ;           // called testFunction
 return 0 ;
}

Above program will call testFunction() via function pointer.

Points to remember
1) function pointers are not allocated by any memory like data poiners.
2) function pointers will be used for call back functions.
3) You can call function pointer without using *.
4) Function pointers will be mainly used for runtime which function to use.
5) quick sort and binary search standard library functions uses function pointers.
6) Like normal variables passed to function as arguments, the same way function pointers will also used for the same. Check quick sort and other sorting methods to sort the numbers in ascending and descending order.
7) virtual functions are nothing but implementation of function pointers.
8) Most OS code has function pointers, lots of functionality for file system, memory management, scheduling etc has function pointers involved.
9) Events are triggered via function pointers.

Arrays

Arrays are nothing but elements of same type stored in contigues manner.
A list of programmers working in a company, list of softwares installed in computer. For example there 10 programmers and 200 softwares installed in the computer.

10 programmers, 200 softwares but they are not same type, how come arrays will be used. Yes, 10 programmers are just numbers we are not interested on each person whether he is male or female, young or old, black or white etc.
Confused leave that example.

IF there are 100 apples, then we can store these apples in array. Thats it.
We have one dimensional, 2 dimensional and upto n-dimensional array.
All n-dimensional arrays are again each 1-dimensional array.

Properties of arrays
1) Arrays should be same data type and cannot be mixed with other data types.
examples
int apple[100], float money[100], char names[500] etc.
Each one is unique.

2) Arrays will always start with index 0 and ends with <n> -1.
In the above example, loop your variable from 0 to 99, 0 to 499 etc to access each item from the array.

3) Arrays can be statically created or dynamically created. Above example shows static allocation.
Dynamically create the array as follows
int *p = (int*) malloc(100*(sizeof(int)) ;
and access using p[0], p[1] etc. and remember to free after the usage.

Memory layout of C program

A typical C program contains the following segments
1) text segment
2) data segment - initialized
3) data segment - unintialized
4) stack
5) Heap

Text segment is the actual c program. The whole C program will be stored in this segment. Actual code is the executable instructions CPU use for execution.
This segment is normally sharable, I mean this section can be shared to editors like vi, vim, ed, shells, and the compilers. Normally this segment will be below the stack or heap.

Data segment: Data segment can be read only or read write. All the global and static variables stored in this segment.
This segment can be divided into initialized data segment where the variables with some values will be stored and uninitialized data segment where variables without initialization will be stored.
Examples:
int a = 100;
char s = 'T' ;
The variables a and s are stored in intialized data segment

char m ;
int i ;
m and i will be stored in uninitialized data segments. This segment is also called BSS(Block started by Symbol)

what about static variables. The memory for static is also stored in data segments.
Example:
static int a = 100;
static float m = 10.34 ;
Note:If static variables will not initiliazed, then they will be set to zero.
So there is no concept of initialized and unitialized data segments for static variables.

Now one more missing section in data segment is READ ONLY.
The global/static variables with read only will be stored in "READ ONLY segment"

Typically data segment can be read only and read-write. All const data variables will be used in READ only data segment and rest in read-write data segments.

Example:
char test[] = "Lets Make Simple" ;
The string literal "Lets Make Simple" is stored in read-only segment while variable test is stored in read-write segment.


STACK segment: As expected used to store the local variables of the function. It contains program stack in LIFO(Last in First Out) fashion. The top of the stack is always the first to be removed from the stack. The register called stack pointer maintain the top of the stack and this will be adjusted as and when function is called and returned. The stack grown opposite to heap area.
Recursion programs use the best use of stack. The stack pointer keeps a seperate copy of each address of called and calling function and hence allocates fresh copy of address for each function call.
int main()
{
   main() ;
}

main() called recursively, as expected we got stack overflow error. Since there is no exit from stack(no exit in the functions).
Typically stack grown from higher address to lower address. Memory for these variables will be de-allocated when the function exits.

HEAP segment: Memory in this segment will be altered when you call malloc, new, free, delete, realloc. They are used to allocate memory dynamically. Heap and stack grows opposite to each other.  Memory in this segment are not freed automatically like stack. You need to call free(), delete() to free the memory from this region.

To know the memory allocated for your program use size command. It shows the size of each segment.

IPC part -1

IPC's are the mechanism used to communicate between 2 or more processes.
Before going further lets understand why processes need to communicate.
1) Because large amount of cpu time will be used if everything is controlled by a single process.
2) User need to wait, till one task need to complete.
3) IF the kernel is not preemptive, high priority task will wait till completion of current task.

So we need to communication. There are many links available on net why process need communication.

But what are the different ways to communicate process each other. How to identify process A need to talk to process B. Of course your mind will think we can use PID to communicate. Right and wrong.
Some questions about communication.
1) what does it mean process to communicate actually?
2) what happens the process which is waiting for data to arrive to process.
3) Lets not use any communication. We are happy with our own single process to do the task all.

To answer above, processes communicate via some simple mechanism. What they communicate. Ideally sharing the resources nothing but communication. Resources can be anything like file descriptors, data(global, static), signals, list of open files etc. All these will be shared to other processes to make the program efficient, smart and fast.

To share these we need to take care about synchronization. A big problem for processes to communicate.
Lets take standard scenario of client/server applications. These are 2 processes, client created by client.c and server created by server.c.

The use of these 2 programs is to write the data on the standard output. Server program will create a nasty funny string "Why it is working" and write on a buffer..Consider buffer is now standard ipc mechanism. Now client will come up and read the contents of buffer and prints on the screen. The data is then removed from buffer. Thats all. End of story.

Some simple problems
1) What happens if buffer is not free/not available.
2) What happens if client reads data from buffer
3) what happens if buffer is full.
4) what happens when client is reading, but server is writing.
5) etc..
So buffer and points 2 and 3 are important. point is just about the different mechanism for communication and rest are for synchronization.

It is boring, we are not yet started ipc's.  :-(
1) pipes
2) message queues
3) shared memory
4) sockets
5) signals

Above are used for IPC. Why there are so many. Again it depends on the way to communicate like
1) Within proceses like program called fork/vfork
2) Whether process is interested to only read or write
3) whether to communicate 2 systems over a network.
4) etc

The best, easy and fastest IPC is shared memory. Because processes are directly accessed memory very faster without copying into user space.

Troubleshooting in Linux/Solaris core file

Troubleshooting crash occured at site
Now customer reported that the binary crashed at site and helling that he lost about x% of revenues for the crash.
Ooops.. and that too crashed on weekends.
Dont worry, cannot do anything at the time of crash, just sit back and relax.
Ask the following from site.
1) Core file
2) Last log
3) pstack
4) pflag
5) Binary version or label running

3 and 4 will be available if OS is solaris.

Now build the same binary in your local lab and run the gdb to pin point where the crash occured.

$cd /home/test/binary
$gdb binary_name core

This will show the location of the stack crashed.
For more details enter backtrace command, this will display the complete stack.
Enter the command "list" to display the 10 lines in and around the crash.
Check which parameters are passing to sys call and why it is coming as NULL.
Review the code and check which all the cases the param gets NULL value.
And reply to the customer that the issue is because of XXX is getting NULL for YYY data and get some time to analyse more time.
The above gdb commands will work only if you are lucky. But most of the time site reported issues will ???????? :-(.

For stack containing only ?????, you cannot do anything. But the frequency of the crash is repeating, then you can give the debug built to site and run the binary. Let binary crash and writes all logs into the file. The logs will help to troubleshoot. If it is one off case and customer is very aggressive about the crash, take the help of your senior manages and let them handle.

Misc

Linux Memory Model
This post will explain about basics of memory model used in linux.
Ideally all processes allocates memory from Kernel via the real daemon like component MMU. But as a process, how do we know that how much memory is allocated.

By default memory allocated to process is just a virtual memory. Virtual memory is chunks of data into pages mapped to phyisical memory.
Virtual memory ABCD will be mapped may be pApBpCpD. The process of mapping of virtual memory pages into physical pages is done by the old traditional memory manager(MMU). It is upto MMU to map which virtual page to load at runtime to CPU. But we should aware that we need some memory to run the program. IT is upto kernel to take care of all internal activities.