College ragging

Read Index

1. Linux IP stack Book

a. Socket programming ( Good tutorial link : http://www.tenouk.com/cnlinuxsockettutorials.html)

2. OS concepts

3. RTOS

4. Networking

a. IGMP, Multicast rounting

b. Normal routing

c. DHCP

d. TCP , SACK , Fast retansmit and Fast recovery

e. Throughput, bandwidth

5. Algorothm

a. Hashing

b. Pactrica tree , used for IPv4 address and string manupilation

c. Complexity of Algo

d. Sorting

6. BW arch

7. Multi core

Netlink (for user/kernel communication)

Why do the above features use netlink instead of system calls, ioctls or proc filesystems for communication between user and kernel worlds? It is a nontrivial task to add system calls, ioctls or proc files for new features; we risk polluting the kernel and damaging the stability of the system. Netlink socket is simple, though: only a constant, the protocol type, needs to be added to netlink.h. Then, the kernel module and application can talk using socket-style APIs immediately.

Netlink is asynchronous because, as with any other socket API, it provides a socket queue to smooth the burst of messages. The system call for sending a netlink message queues the message to the receiver's netlink queue and then invokes the receiver's reception handler. The receiver, within the reception handler's context, can decide whether to process the message immediately or leave the message in the queue and process it later in a different context. Unlike netlink, system calls require synchronous processing. Therefore, if we use a system call to pass a message from user space to the kernel, the kernel scheduling granularity may be affected if the time to process that message is long.

The code implementing a system call in the kernel is linked statically to the kernel in compilation time; thus, it is not appropriate to include system call code in a loadable module, which is the case for most device drivers. With netlink socket, no compilation time dependency exists between the netlink core of Linux kernel and the netlink application living in loadable kernel modules.

Netlink socket supports multicast, which is another benefit over system calls, ioctls and proc. One process can multicast a message to a netlink group address, and any number of other processes can listen to that group address. This provides a near-perfect mechanism for event distribution from kernel to user space.

System call and ioctl are simplex IPCs in the sense that a session for these IPCs can be initiated only by user-space applications. But, what if a kernel module has an urgent message for a user-space application? There is no way of doing that directly using these IPCs. Normally, applications periodically need to poll the kernel to get the state changes, although intensive polling is expensive. Netlink solves this problem gracefully by allowing the kernel to initiate sessions too. We call it the duplex characteristic of the netlink socket.

Finally, netlink socket provides a BSD socket-style API that is well understood by the software development community. Therefore, training costs are less as compared to using the rather cryptic system call APIs and ioctls.

Relating to the BSD Routing Socket

In BSD TCP/IP stack implementation, there is a special socket called the routing socket. It has an address family of AF_ROUTE, a protocol family of PF_ROUTE and a socket type of SOCK_RAW. The routing socket in BSD is used by processes to add or delete routes in the kernel routing table.

In Linux, the equivalent function of the routing socket is provided by the netlink socket protocol type NETLINK_ROUTE. Netlink socket provides a functionality superset of BSD's routing socket.

Pthread producer consumer example in C

This code creates two threads then passes data from one to the other in sequence. To compile, save the code as main.c (or whatever you want) and then use the command:

 gcc -lpthread main.c -o main 

or you can create a make file containing the lines:

main: main.c      gcc -lpthread main.c -o main

You can then just use the command “make” to compile the code, this is useful if you want to change the program thus needing to compile it multiple times.

/*pthread example. Copyright (c) 2006-2007 Richard Palethorpe  Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:  The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE  Website: richiejp.wordpress.com email: richiejp@gmail.com*/  #include  #include  #include   void* producer(void*); void* consumer(void*);  /*This data structure contains information that needs to be shared between threads. It is passed to the producer and consumer threads' starter functions. The alternative to this is to use global variables.*/ struct Context{         pthread_cond_t* cond;         pthread_mutex_t* mutex;         /*This is used to hold a character while it is passed from one thread to         another. Only the thread which owns the mutex lock should access it.*/         char holder;         int error; };  int main(){         volatile struct Context context;         context.cond = (pthread_cond_t*)malloc(sizeof(pthread_cond_t));         context.mutex = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t));         context.error = 0;          pthread_cond_init(context.cond, NULL);         pthread_mutex_init(context.mutex, NULL);          pthread_t prod;         pthread_t cons;          puts("createing first thread");         if(pthread_create(&prod, NULL, producer, (void*)&context) != 0){                 puts("Could not create producer thread");                  pthread_mutex_destroy(context.mutex);                 pthread_cond_destroy(context.cond);                  return(EXIT_FAILURE);         }          puts("createing second thread");         if(pthread_create(&cons, NULL, consumer, (void*)&context) != 0){                 puts("Could not create consumer thread");                  pthread_mutex_lock(context.mutex);                 context.error = 1;                 pthread_mutex_unlock(context.mutex);                 pthread_cond_signal(context.cond);                  pthread_join(prod, NULL);                  pthread_mutex_destroy(context.mutex);                 pthread_cond_destroy(context.cond);;                  return(EXIT_FAILURE);         }          pthread_join(prod, NULL);         pthread_join(cons, NULL);          pthread_mutex_destroy(context.mutex);         pthread_cond_destroy(context.cond);          free(context.cond);         free(context.mutex);          return(EXIT_SUCCESS); }  void* producer(void* _context){         puts("in producer");         struct Context* context = (struct Context*)_context;          char data[] = "Some data to send to the consumer\n";          pthread_mutex_lock(context->mutex);         int i;         for(i = 0; i  sizeof data; i++){                 if(!context->error){                         context->holder = data[i];                          pthread_cond_signal(context->cond);                         pthread_cond_wait(context->cond, context->mutex);                 }else{                         pthread_mutex_unlock(context->mutex);                          return NULL;                 }         }          pthread_cond_signal(context->cond);         pthread_mutex_unlock(context->mutex);          return NULL; }  void* consumer(void* _context){         puts("in consumer");         struct Context* context = (struct Context*)_context;          printf("Recieving data: ");           pthread_mutex_lock(context->mutex);         while(context->holder != ''){                 if(!context->error){                         putc((unsigned int)context->holder, stdout);                          pthread_cond_signal(context->cond);                         pthread_cond_wait(context->cond, context->mutex);                 }else{                         pthread_cond_signal(context->cond);                         pthread_mutex_unlock(context->mutex);                          return NULL;                 }         }          pthread_cond_signal(context->cond);         pthread_mutex_unlock(context->mutex);          return NULL; }

Priority Inversion

Priority Inversion

Priority inversion occurs when a low-priority thread holds a mutex, blocking a high-priority thread. Due to its low priority, the mutex owner may hold the mutex for an unbounded duration. As a result, it becomes impossible to guarantee thread deadlines.

The following example illustrates a typical priority inversion. In this example, the case of a uniprocessor system is considered. Priority inversions also occur on multiprocessor systems in a similar way.

In our example, a mutex M is used to protect some common data. Thread A has a priority level of 100 and is scheduled very often. Thread B has a priority level of 20 and is a background thread. Other threads in the process have priority levels near 60. A code fragment from thread A is as follows:

pthread_mutex_lock(&M);             /* 1 */ ... pthread_mutex_unlock(&M);

A code fragment from thread B is as follows:

pthread_mutex_lock(&M);          /* 2 */ ... fprintf(...);                    /* 3 */ ... pthread_mutex_unlock(&M);

Consider the following execution chronology. Thread B is scheduled and executes line 2. While executing line 3, thread B is preempted by thread A. Thread A executes line 1 and is blocked, because the mutex M is held by thread B. Thus, other threads in the process are scheduled. Because thread Bhas a very low priority, it may not be rescheduled for a long period, blocking thread A, although threadA has a very high priority.

Mutex Protocols

To avoid priority inversions, the following mutex protocols are provided by the threads library:

Priority inheritance protocol

Sometimes called basic priority inheritance protocol. In the priority inheritance protocol, the mutex holder inherits the priority of the highest-priority blocked thread. When a thread tries to lock a mutex using this protocol and is blocked, the mutex owner temporarily receives the blocked thread's priority, if that priority is higher than the owner's. It recovers its original priority when it unlocks the mutex.

Priority protection protocol

Sometimes called priority ceiling protocol emulation. In the priority protection protocol, each mutex has a priority ceiling. It is a priority level within the valid range of priorities. When a thread owns a mutex, it temporarily receives the mutex priority ceiling, if the ceiling is higher than its own priority. It recovers its original priority when it unlocks the mutex. The priority ceiling should have the value of the highest priority of all threads that may lock the mutex. Otherwise, priority inversions or even deadlocks may occur, and the protocol would be inefficient.

Choosing a Mutex Protocol

The choice of a mutex protocol is made by setting attributes when creating a mutex. The mutex protocol is controlled through the protocol attribute. This attribute can be set in the mutex attributes object by using the pthread_mutexattr_getprotocol and pthread_mutexattr_setprotocolsubroutines. The protocol attribute can have one of the following values:

PTHREAD_PRIO_NONE	Denotes no protocol. This is the default value.
PTHREAD_PRIO_INHERIT	Denotes the priority inheritance protocol.
PTHREAD_PRIO_PROTECT	Denotes the priority protection protocol.

The priority protection protocol uses one additional attribute: the prioceiling attribute. This attribute contains the priority ceiling of the mutex. The prioceiling attribute can be controlled in the mutex attributes object, by using the pthread_mutexattr_getprioceiling andpthread_mutexattr_setprioceiling subroutines.

The prioceiling attribute of a mutex can also be dynamically controlled by using thepthread_mutex_getprioceiling and pthread_mutex_setprioceiling subroutines. When dynamically changing the priority ceiling of a mutex, the mutex is locked by the library; it should not be held by the thread calling the pthread_mutex_setprioceiling subroutine to avoid a deadlock. Dynamically setting the priority ceiling of a mutex can be useful when increasing the priority of a thread.

The implementation of mutex protocols is optional. Each protocol is a POSIX option. For more information about the priority inheritance and the priority protection POSIX options, see Threads Library Options.

Inheritance or Protection

Both protocols are similar and result in promoting the priority of the thread holding the mutex. If both protocols are available, programmers must choose a protocol. The choice depends on whether the priorities of the threads that will lock the mutex are available to the programmer who is creating the mutex. Typically, mutexes defined by a library and used by application threads will use the inheritance protocol, whereas mutexes created within the application program will use the protection protocol.

In performance-critical programs, performance considerations may also influence the choice. In most implementations, especially in AIX, changing the priority of a thread results in making a system call. Therefore, the two mutex protocols differ in the amount of system calls they generate, as follows:

• Using the inheritance protocol, a system call is made each time a thread is blocked when trying to lock the mutex.
• Using the protection protocol, one system call is always made each time the mutex is locked by a thread.

In most performance-critical programs, the inheritance protocol should be chosen, because mutexes are low contention objects. Mutexes are not held for long periods of time; thus, it is not likely that threads are blocked when trying to lock them.

Thread

1. When several threads compete for a mutex, the losers block at that call - an unblocking call is available with "trylock" instead of the "lock" call.

2. In subroutines that execute to completion normally, you can often dispense with calling pthread_exit() - unless, of course, you want to pass a return code back. However, in main(), there is a definite problem if main() completes before the threads it spawned. If you don't call pthread_exit()explicitly, when main() completes, the process (and all threads) will be terminated. By calling pthread_exit() in main(), the process and all of its threads will be kept alive even though all of the code in main() has been executed

3. pthread_exit is used to explicitly exit a thread. Typically, the pthread_exit() routine is called after a thread has completed its work and is no longer required to exist.

4. If main() finishes before the threads it has created, and exits with pthread_exit(), the other threads will continue to execute. Otherwise, they will be automatically terminated when main() finishes.

5. The attr object is used to establish properties for the mutex object, and must be of type pthread_mutexattr_t if used (may be specified as NULL to accept defaults). The Pthreads standard defines three optional mutex attributes:

• Protocol: Specifies the protocol used to prevent priority inversions for a mutex.
• Prioceiling: Specifies the priority ceiling of a mutex.
• Process-shared: Specifies the process sharing of a mutex.

Idea

1. webpage for TV programs

Interview at sonus

Q1. Difference between OS and RTOS?

Q2. producer consumer ?

Q3. How to send signal in Linux?

Q4. How to calculate Throughput ?

Q5. DHCP send broadcast for some responses? why ?

Kernel Space - User Space Interfaces

http://people.ee.ethz.ch/~arkeller/linux/kernel_user_space_howto.html

This how-to aims to provide an overview over all existing communication mechanisms between Linux user and kernel space. The goal is to present a starting point for a developer who needs to transfer data between Linux kernel modules and user space programs. Each mechanism is described in its own section, with each section further divided into Description, Implementation, and Resources & Further Reading. In the description section we describe the basic mechanism and intended use of the mechanism. The implementation provides an example source code along with a short description. The Resources & Further reading section provides a list of useful articles and book chapters.