Sunday, June 8, 2014

C String interview Question

1. What will be output when you will execute following c code?
#include
void main(){
char arr[7]="Network";
printf("%s",arr);
}
Explanation:
Size of a character array should one greater than total number of characters in any string which it stores. In c every string has one terminating null character. This represents end of the string.So in the string “Network” , there are 8 characters and they are ‘N’,’e’,’t’,’w’,’o’,’r’,’k’ and ‘\0’. Size of array arr is seven. So array arr will store only first sevent characters and it will note store null character.
As we know %s in prinf statement prints stream of characters until it doesn’t get first null character. Since array arr has not stored any null character so it will print garbage value.



2.What will be output when you will execute following c code?
#include
void main(){
    char arr[11]="The African Queen";
    printf("%s",arr);
}
Explanation:
Size of any character array cannot be less than the number of characters in any string which it has assigned. Size of an array can be equal (excluding null character) or greater than but never less than.

3.What will be output when you will execute following c code?
#include
void main(){
    int const SIZE=5;
    int expr;
    double value[SIZE]={2.0,4.0,6.0,8.0,10.0};
    expr=1|2|3|4;
    printf("%f",value[expr]);
}
Explanation:
Size of any array in c cannot be constantan variable.

4.What will be output when you will execute following c code?
#include
enum power{
    Dalai,
    Vladimir=3,
    Barack,
    Hillary
};
void main(){
    float leader[Dalai+Hillary]={1.f,2.f,3.f,4.f,5.f};
    enum power p=Barack;
    printf("%0.f",leader[p>>1+1]);
}
Explanation:
Size of an array can be enum constantan.
Value of enum constant Barack will equal to Vladimir + 1 = 3 +1 = 4
So, value of enum variable p  = 4
leader[p >> 1 +1]
= leader[4 >> 1+1]
=leader[4 >> 2]   //+ operator enjoy higher precedence than >> operator.
=leader[1]  //4>>2 = (4 / (2^2) = 4/4 = 1
=2

5.What will be output when you will execute following c code?
#include
#define var 3
void main(){
    char *cricket[var+~0]={"clarke","kallis"};
    char *ptr=cricket[1+~0];
    printf("%c",*++ptr);
}
Explanation:
In the expression of size of an array can have micro constant.
var +~0 = 3 + ~0 = 3 + (-1)  = 2
Let’s assume string “clarke” and “kallis” has stored at memory address 100 and 500 respectively as shown in the following figure:
For string “clarke”:
For string “kallis”:
In this program cricket is array of character’s pointer of size 2. So array cricket will keep the memory address of first character of both strings i.e. content of array cricket is:
cricket[2] = {100,500}
ptr is character pointer which is pointing to the fist element of array cricket. So, ptr = 100
Now consider on *++ptr
Since ptr = 100 so after ++ptr , ptr = 101
*(++ptr) = *(101) = content of memory address 101. From above figure it is clear that character is l.

6.What will be output when you will execute following c code?
#include
void main(){
    char data[2][3][2]={0,1,2,3,4,5,6,7,8,9,10,11};
    printf("%o",data[0][2][1]);
}
Explanation:
%o in printf statement is used to print number in the octal format.

7.What will be output when you will execute following c code?
#include
void main(){
    short num[3][2]={3,6,9,12,15,18};
    printf("%d  %d",*(num+1)[1],**(num+2));
}
Explanation:
*(num+1)[1]=*(*((num+1)+1))=*(*(num+2))=*(num[2])=num[2][0]=15And**(num+2)=*(num[2]+0)=num[2][0]=15

8.What will be output when you will execute following c code?
#include
void main(){
    char *ptr="cquestionbank";
    printf("%d",-3[ptr]);
}
Explanation:
-3[ptr]=-*(3+ptr)=-*(ptr+3)
=-ptr[3]
=-103  //ASCII value of character ‘e’ is 103

9.What will be output when you will execute following c code?
#include
void main(){
    long  myarr[2][4]={0l,1l,2l,3l,4l,5l,6l,7l};
    printf("%ld\t",myarr[1][2]);
    printf("%ld%ld\t",*(myarr[1]+3),3[myarr[1]]);
    printf("%ld%ld%ld\t" ,*(*(myarr+1)+2),*(1[myarr]+2),3[1[myarr]]); 
}
Explanation:
Think yourself.

10.What will be output when you will execute following c code?
#include
void main(){
    int array[2][3]={5,10,15,20,25,30};
    int (*ptr)[2][3]=&array;
    printf("%d\t",***ptr);
    printf("%d\t",***(ptr+1));
    printf("%d\t",**(*ptr+1));
    printf("%d\t",*(*(*ptr+1)+2));
}
Explanation:
ptr is pointer to two dimension array.
***ptr
=***&array  //ptr = &array
=**array //* and & always cancel to each other
=*arr[0]  // *array = *(array +0) = array[0]
=array[0][0]
= 5
Rests think yourself.

11.What will be output when you will execute following c code?
#include
void main(){
    static int a=2,b=4,c=8;
    static int *arr1[2]={&a,&b};
    static int *arr2[2]={&b,&c};
    int* (*arr[2])[2]={&arr1,&arr2};
    printf("%d %d\t",*(*arr[0])[1],  *(*(**(arr+1)+1)));
}
Explanation:
Consider on the following expression:
*(*arr[0])[1]
=*(*&arr1)[1]  //arr[0] = &arr1
=*arr1[1]   //* and & always cancel to each other
=*&b
=b
=4
Consider on following expression:
*(*(**(arr+1)+1))
= *(*(*arr[1]+1))  //*(arr+1) = arr[1]
= *(*(*&arr2+1))  //arr[1] = &arr2
=*(*(arr2+1))  //*&arr2 = arr2
=*(arr2[1])  //*(arr2+1) = arr2[1]
=  *&c    //arr2[1] = &c
=  c
= 8

12.What will be output when you will execute following c code?
#include
#include
double myfun(double);
void main(){
    double(*array[3])(double);
    array[0]=exp;
    array[1]=sqrt;
    array[2]=myfun;
    printf("%.1f\t",(*array)((*array[2])((**(array+1))(4)))); 
}
double myfun(double d){
       d-=1;
       return d;
}
Explanation:
array is array of pointer to such function which parameter is double type data and return type is double.
Consider on following expression:
(*array)((*array[2])((**(array+1))(4)))
= (*array)((*array[2])((*array[1])(4)))
//*(array+1) = array[1]
= (*array)((*array[2])(sqrt(4))))
//array[1] = address of sqrt function
= (*array)((*array[2])(2.000000)))
= (*array)(myfun(2.000000)))
// array[2] = address of myfunc function
=(*array)(1.000000)
=array[0](1.000000)
=exp(1.000000)

13.What will be output when you will execute following c code?
#include
typedef struct{
    char *name;
    double salary;
}job;
void main(){
    static job a={"TCS",15000.0};
    static job b={"IBM",25000.0};
    static job c={"Google",35000.0};
    int x=5;
    job * arr[3]={&a,&b,&c};
    printf("%s  %f\t",(3,x>>5-4)[*arr]);
}
double myfun(double d){
       d-=1;
       return d;
}
Explanation:
(3,5>>5-4)[*arr]
=(3,5>>5-4)[*arr] //x=5
= (3,5>>1)[*arr] //- operator enjoy higher precedence than >>
= (3,2)[*arr]  //5>>1 = 5/(2^1) = 5 /2 = 2
= 2[*arr]  //In c comma is also operator.
= *(2 + *arr)
= *(*arr + 2)
=*arr[2]
=*(&c) //arr[2] = &c
=c   // *  and & always cancel to each other.
So,
printf("%s  %f\t",c);
=> printf("%s  %f\t", "Google",35000.0);

14.What will be output when you will execute following c code?
#include
union group{
    char xarr[2][2];
    char yarr[4];
};
void main(){
    union group x={'A','B','C','D'};
    printf("%c",x.xarr[x.yarr[2]-67][x.yarr[3]-67]);
}
Explanation:
In union all member variables share common memory space.
So union member variable, array xarray will look like:
{
{‘A’,’B’},
{‘C’,’D’}
}
And union member variable, array yarray will look like:
{
{‘A’,’B’,’C’,’D’}
}
x.xarr[x.yarr[2]-67][x.yarr[3]-67]
= x.xarr[‘C’-67][‘D’-67]
= x.xarr[67-67][68-67]
//ASCII value of ‘C’ is 67 and ‘D’ is 68.
x.xarr[0][1]
=’B’

15.What will be output when you will execute following c code?
#include
void main(){
    int a=5,b=10,c=15;
    int *arr[3]={&a,&b,&c};
    printf("%d",*arr[*arr[1]-8]);
}
Explanation:
Member of an array cannot be address of auto variable because array gets memory at load time while auto variable gets memory at run time.

16.What will be output when you will execute following c code?
#include
void main(){
    int arr[][3]={{1,2},{3,4,5},{5}};
    printf("%d %d %d",sizeof(arr),arr[0][2],arr[1][2]);
}
Explanation:
If we will not write size of first member of any array at the time of declaration then size of the first dimension is max elements in the initialization of array of that dimension.
So, size of first dimension in above question is 3.
So size of array = (size of int) * (total number of elements) = 2 *(3*3) = 18
Default initial value of rest elements are zero.  So above array will look like:
{
{1,2,0}
{3,4,5},
{5,0,0}
}         

17.What will be output when you will execute following c code?
#include
void main(){
    int xxx[10]={5};
    printf("%d %d",xxx[1],xxx[9]);
}
Explanation:
If we initialize any array at the time of declaration the compiler will treat such array as static variable and its default value of uninitialized member is zero.

18.What will be output when you will execute following c code?
#include
#define WWW -1
enum {cat,rat};
void main(){
    int Dhoni[]={2,'b',0x3,01001,'\x1d','\111',rat,WWW};
    int i;
    for(i=0;i<8 i="" span="">
         printf(" %d",Dhoni[i]);
}
Explanation:
Dhoni[0]=2
Dhoni[1]=’b’ =98  //ASCII value of character ‘b’ is 98.
Dhoni[2]=  0x3  =  3  //0x represents hexadecimal number. Decimal value of hexadecimal 3 is also 3.
Dhoni[3]=01001 = 513 //Number begins with 0 represents octal number.
Dhoni[4]  = ‘\x1d’ = 29 //’\x1d’ is hexadecimal character constant.
Dhoni[5] = ‘\111’ = 73 //’\111’ is octal character constant.
Dhoni[6] =rat = 1  //rat is enum constant
Dhoni[7] = WWW = -1  //WWW is macro constant.


19.What will be output when you will execute following c code?
#include
void main(){
    long double a;
    signed char b;
    int arr[sizeof(!a+b)];
    printf("%d",sizeof(arr));
}
Explanation:
Size of data type in TURBO C 3.0 compiler is:
S.N.
Data type
Size(In byte)
1
char
1
2
int
2
3
double
8
Consider on the expression: !a + b
! Operator always return zero if a is non-zero number other wisie 1. In general we can say ! operator always returns an int type number. So
!a +b
=! (Any double type number) + Any character type number
= Any integer type number + any character type number
= Any integer type number
Note: In any expression lower type data is always automatically type casted into the higher data type. In this case char data type is automatically type casted into the int type data.
So sizeof (!a +b) = sizeof(Any int type number)  = 2
So size of array arr is 2 and its data type is int. So
sizeof(arr) = size of array * sizeof its data type = 2* 2= 4


20.What will be output when you will execute following c code?
#include
void main(){
    char array[]="Ashfaq \0 Kayani";
    char *str="Ashfaq \0 Kayani";
    printf("%s %c\n",array,array[2]);
    printf("%s %c\n",str,str[2]);
    printf("%d %d\n",sizeof(array),sizeof(str));
}
Explanation:
A character array keeps the each element of an assigned array but a character pointer always keeps the memory address of first element. 
As we know %s in prints the characters of stream until it doesn’t any null character (‘\0’).  So first and second printf function will print same thing in the above program.  But size of array is total numbers of its elements i.e. 16 byte (including ending null character). While size of any type of pointer is 2 byte (near pointer).

Difference Between Semaphore and Mutex


Mutex:

Is a key to a toilet. One person can have the key – occupy the toilet – at the time. When finished, the person gives (frees) the key to the next person in the queue.

Officially: “Mutexes are typically used to serialise access to a section of re-entrant code that cannot be executed concurrently by more than one thread. A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section.”
Ref: Symbian Developer Library

(A mutex is really a semaphore with value 1.)

Semaphore:

Is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count – the count of keys – is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.

Officially: “A semaphore restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore).”
Ref: Symbian Developer Library

From http://www.geeksforgeeks.org/archives/9102

Using Mutex:

A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by producer, the consumer needs to wait, and vice versa.

At any point of time, only one thread can work with the entire buffer. The concept can be generalized using semaphore.

Using Semaphore:

A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.

Misconception:

There is an ambiguity between binary semaphore and mutex. We might have come across that a mutex is binary semaphore. But they are not! The purpose of mutex and semaphore are different. May be, due to similarity in their implementation a mutex would be referred as binary semaphore.

Strictly speaking, a mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).

Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup.

General Questions:

1. Can a thread acquire more than one lock (Mutex)?

Yes, it is possible that a thread will be in need of more than one resource, hence the locks. If any lock is not available the thread will wait (block) on the lock.

2. Can a mutex be locked more than once?

A mutex is a lock. Only one state (locked/unlocked) is associated with it. However, a recursive mutex can be locked more than once (POSIX complaint systems), in which a count is associated with it, yet retains only one state (locked/unlocked). The programmer must unlock the mutex as many number times as it was locked.

3. What will happen if a non-recursive mutex is locked more than once.

Deadlock. If a thread which had already locked a mutex, tries to lock the mutex again, it will enter into the waiting list of that mutex, which results in deadlock. It is because no other thread can unlock the mutex. An operating system implementer can exercise care in identifying the owner of mutex and return if it is already locked by same thread to prevent deadlocks.

4. Are binary semaphore and mutex same?

No. We will suggest to treat them separately, as it was explained signalling vs locking mechanisms. But a binary semaphore may experience the same critical issues (e.g. priority inversion) associated with mutex. We will cover these later article.

A programmer can prefer mutex rather than creating a semaphore with count 1.

5. What is a mutex and critical section?

Some operating systems use the same word critical section in the API. Usually a mutex is costly operation due to protection protocols associated with it. At last, the objective of mutex is atomic access. There are other ways to achieve atomic access like disabling interrupts which can be much faster but ruins responsiveness. The alternate API makes use of disabling interrupts.

6. What are events?

The semantics of mutex, semaphore, event, critical section, etc… are same. All are synchronization primitives. Based on their cost in using them they are different. We should consult the OS documentation for exact details.

7. Can we acquire mutex/semaphore in an Interrupt Service Routine?

An ISR will run asynchronously in the context of current running thread. It is not recommended to query (blocking call) the availability of synchronization primitives in an ISR. The ISR are meant be short, the call to mutex/semaphore may block the current running thread. However, an ISR can signal a semaphore or unlock a mutex.

8. What we mean by “thread blocking on mutex/semaphore” when they are not available?

Every synchronization primitive will have waiting list associated with it. When the resource is not available, the requesting thread will be moved from the running list of processor to the waiting list of the synchronization primitive. When the resource is available, the higher priority thread on the waiting list will get resource (more precisely, it depends on the scheduling policies).

9. Is it necessary that a thread must block always when resource is not available?

Not necessarily. If the design is sure ‘what has to be done when resource is not available‘, the thread can take up that work (a different code branch). To support application requirements the OS provides non-blocking API.

For example POSIX pthread_mutex_trylock() API. When the mutex is not available the function will return immediately where as the API pthread_mutex_lock() will block the thread till resource is available.

References:

http://www.netrino.com/node/202

http://doc.trolltech.com/4.7/qsemaphore.html

Also compare mutex/semaphores with Peterson’s algorithm and Dekker’s algorithm. A good reference is the Art of Concurrency book. Also explore reader locks and writer locks in Qt documentation.

Saturday, June 7, 2014

Linux Device Driver Interview Question

  

                                    Linux Device Model (LDM)

Explain about the Linux Device Model (LDM)?

Explain about about ksets, kobjects and ktypes. How are they related?

Questions about sysfs.



                                       Linux Boot Sequence

Explain about the Linux boot sequence in case of ARM architecture?

How are the command line arguments passed to Linux kernel by the u-boot (bootloader)?

Explain about ATAGS?

Explain about command line arguments that are passed to linux kernel and how/where they are 
parsed in kernel code?

Explain about device tree.

                                      Interrupts in Linux

Explain about the interrupt mechanims in linux?

What are the APIs that are used to register an interrupt handler?
How do you register an interrupt handler on a shared IRQ line?

Explain about the flags that are passed to request_irq().

Explain about the internals of Interrupt handling in case of Linux running on ARM.

What are the precautions to be taken while writing an interrupt handler?

Explain interrupt sequence in detail starting from ARM to registered interrupt handler.

What is bottom half and top half.

What is request_threaded_irq()

If same interrupts occurs in two cpu how are they handled?

How to synchronize data between 'two interrupts' and 'interrupts and process'.

How are nested interrupts handled?

How is task context saved during interrupt.

                                    Bottom-half Mechanisms in Linux

What are the different bottom-half mechanisms in Linux?
Softirq, Tasklet and Workqueues

What are the differences between Softirq/Tasklet and Workqueue? Given an example what you 
prefer to use?

What are the differences between softirqs and tasklets?
  • Softirq is guaranteed to run on the CPU it was scheduled on, where as tasklets don’t have that guarantee. 
  • The same tasklet can't run on two separate CPUs at the same time, where as a softirq can. 
When are these bottom halfs executed?

Explain about the internal implementation of softirqs?
http://linuxblore.blogspot.com/2013/02/bottom-halves-in-linux-part-1-softirqs.html

Explain about the internal implementation of tasklets?
http://linuxblore.blogspot.com/2013/02/bottom-halves-in-linux-part-2-tasklets.html

Explain about the internal implementation of workqueues?
http://linuxblore.blogspot.in/2013/01/workqueues-in-linux.html

Explain about the concurrent work queues.


                                       Linux Memory Management 

What are the differences between vmalloc and kmalloc? Which is preferred to use in device drivers?

What are the differences between slab allocator and slub allocator?

What is boot memory allocator?

How do you reserve block of memory?
What is virtual memory and what are the advanatages of using virtual memory?

What's paging and swapping?

Is it better to enable swapping in embedded systems? and why?

What is the page size in Linux kernel in case of 32-bit ARM architecture?

What is page frame?

What are the different memory zones and why does different zones exist?

What is high memory and when is it needed?

Why is high memory zone not needed in case of 64-bit machine?

How to allocate a page frame from high memory?

In ARM, an abort exception if generated, if the page table doesn't contain a virtual to physical map for a particular page. How exactly does the MMU know that a virtual to physical map is present in the pagetable or not?

A Level-1 page table entry can be one of four possible types. The 1st type is given below: 
  • A fault entry that generates an abort exception. This can be either a prefetch or data abort, depending on the type of access. This effectively indicates virtual addresses that are unmapped.

In this case the bit [0] and [1] are set to 0. This is how the MMU identifies that it's a fault entry. 


Same is the case with Level-2 page table entry.

Does the Translation Table Base Address (TTBR) register, Level 1 page table and Level 2 page table contain Physical addresses or Virtual addresses?

TTBR: Contain physical address of the pgd base
Level 1 page table (pgd): Physical address pointing to the pte base
Level 2 page table (pte): Physical address pointing to the physical page frame

Since page tables are in kernel space and kernel virtual memory is mapped directly to RAM. Using just an easy macro like __virt_to_phys(), we can get the physical address for the pgd base or pte base or pte entry.


                                           Kernel Synchronization

Why do we need synchronization mechanisms in Linux kernel?
What are the different synchonization mechanisms present in Linux kernel?
What are the differences between spinlock and mutex?
What is lockdep?
Which synchronization mechanism is safe to use in interrupt context and why?
Explain about the implementation of spinlock in case of ARM architecture.
Explain about the implementation of mutex in case of ARM architecture.
Solution

Explain about the notifier chains.
Solution
Explain about RCU locks and when are they used?

Explain about RW spinlocks locks and when are they used?

Which are the synchronization technoques you use 'between processes', 'between processe and interrupt' and 'between interrupts'; why and how ?

What are the differences between semaphores and spinlocks?

                            Process Management and Process Scheduling


What are the different schedulers class present in the linux kernel?

How to create a new process?

What is the difference between fork( ) and vfork( )?

Which is the first task what is spawned in linux kernel?

What are the processes with PID 0 and PID 1?
PID 0 - idle task
PID 1 - init 

How to extract task_struct of a particular process if the stack pointer is given?

How does scheduler picks particular task?

When does scheduler picks a task?

How is timeout managed?

How does load balancing happens?

Explain about any scheduler class?

Explain about wait queues and how they implemented? Where and how are they used?

What is process kernel stack and process user stack? What is the size of each and how are they allocated?

Why do we need seperate kernel stack for each process?

What all happens during context switch?

What is thread_info? Why is it stored at the end of kernel stack?

What is the use of preempt_count variable?

What is the difference between interruptible and uninterruptible task states?

How processes and threads are created? (from user level till kernel level)

How is virtual run time (vruntime) calculated?
Solution

                                      Timers and Time Management


What are jiffies and HZ?
What is the initial value of jiffies when the system has started?

Explain about HR timers and normal timers?

On what hardware timers, does the HR timers are based on?

How to declare that a specific hardware timers is used for kernel periodic timer interrupt used by the scheduler?

How software timers are implemented?

                                       Power Management in Linux



Explain about cpuidle framework.

Explain about cpufreq framework.

Explain about clock framework.

Explain about regulator framework.

Explain about suspened and resume framwork.

Explain about early suspend and late resume.

Explain about wakelocks.

                                          Linux Kernel Modules


How to make a module as loadable module?

How to make a module as in-built module?

Explain about Kconfig build system?

Explain about the init call mechanism.
Solution

What is the difference between early init and late init?
Early init:
  • Early init functions are called when only the boot processor is online.
  • Run before initializing SMP.
  • Only for built-in code, not modules.
Late init:
  •  Late init functions are called _after_ all the CPUs are online.

                                         Linux Kernel Debugging

What is Oops and kernel panic?
Does all Oops result in kernel panic?
What are the tools that you have used for debugging the Linux kernel?
What are the log levels in printk?
Can printk's be used in interrupt context?
How to print a stack trace from a particular function?
What's the use of early_printk( )?
Explan about the various gdb commands.

                                                  Miscellaneous

How are the atomic functions implemented in case of ARM architecture?
Solution

How is container_of( ) macro implemented? 

Explain about system call flow in case of ARM Linux.

What 's the use of __init and __exit macros?
How to ensure that init function of a partiuclar driver was called before our driver's init function is called (assume that both these drivers are built into the kenrel image)?

What's a segementation fault and what are the scenarios in which segmentation fault is triggered?

If the scenarios which triggers the segmentation fault has occured, how the kernel identifies it and what are the actions that the kernel takes?