Out-of-Order Execution (OOE)

http://en.wikipedia.org/wiki/Out-of-order_execution

Data alignment

http://www.ibm.com/developerworks/library/pa-dalign/

Linux Kernel Important Sites

1. http://www.linuxdriver.co.il/ldd3/chp-10-sect-4
2. 

Multithreading - Part 2: Synchronization

Consider the program which we mentioned in "Multithreading - Part 1: Basics"


Program:

#include <stdio.h>
#include <pthread.h>


int gvar;

void* t1_fun(void *msg)
{
    int i;
    for(i = 0; i < 10; i++)
    {   
        gvar++;
        /*printf("[%d:%s] : gvar = %d.\n", pthread_self(), (char*) msg, gvar);*/
        printf("[%d:%s] : gvar = %d.\n", (long int)syscall(224), (char*) msg, gvar);
    }   
}

int main()

{

    pthread_t t1, t2; 

    char *msg1 = "thread1";

    char *msg2 = "thread2";

    int rc1 = pthread_create(&t1, NULL, t1_fun, (void *) msg1);

    if( rc1 ) { printf("Error for thread 1.\n"); perror("pthread_create"); }

    int rc2 = pthread_create(&t2, NULL, t1_fun, (void *) msg2);

    if( rc2 ) { printf("Error for thread 1.\n"); perror("pthread_create"); }

    /* If the 2nd arg is NOT NULL, the return value of t1 and t2 will be stored there.
     * This pthread_join will suspend the main thread until the t1/t2 completes, terminates or by calling
     * pthread_exit. 
     */
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);    

    printf("Threads execution over.\n");

    return 0;

}

NOTE that if there is no load in the system, this program might print the value of "gvar" as 20 as expected (each thread increments gvar 10 times; hence 20).
But, if you increase the load in the system or if you increase the count in the for loop (replace the count 10 with 50), you can see the threads will fight each other to increment the global variable "gvar". At the  end of the program, if you see, the "gvar" will not be "100" as expected; but rather less (see below).

[5164:thread1] : gvar = 95.

[5164:thread1] : gvar = 96.

...
...

[5165:thread2] : gvar = 95.

[5165:thread2] : gvar = 97.

This kind of situation is called "race condition" where two or more threads will race with each other to change the state of a variable without bothering about the other one.

To avoid this, we have to use mutex.

Mutex (ONLY BETWEEN THREADS IN A SINGLE PROCESS; NOT ACROSS PROCESSES LIKE SEMAPHORE):
Mutexes are used to prevent data inconsistencies due to operations by multiple threads upon the same memory area performed at the same time or to prevent race conditions where an order of operation upon the memory is expected. A contention or race condition often occurs when two or more threads need to perform operations on the same memory area, but the results of computations depends on the order in which these operations are performed. Mutexes are used for serializing shared resources such as memory. Anytime a global resource is accessed by more than one thread the resource should have a Mutex associated with it. Once can apply a mutex to protect a segment of memomry ("critical region") from other threads. Mutexes can be applied only to threads in a single process and do not work between processes as do semaphores.

Modified Program with Mutex:


#include <stdio.h>
#include <pthread.h>


/* Note scope of variable and mutex are the same */
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

int gvar;
void* t1_fun(void *msg)
{
    int i;
    for(i = 0; i < 100; i++)
    {   
        pthread_mutex_lock( &mutex );
        gvar++;
        /*printf("[%d:%s] : gvar = %d.\n", pthread_self(), (char*) msg, gvar);*/
        printf("[%d:%s] : gvar = %d.\n", (long int)syscall(224), (char*) msg, gvar);
        pthread_mutex_unlock( &mutex );
    }   
}

...

...

Program Output:

$> gcc sample.c -lpthread

$> ls

a.out sample.c

$> ./a.out

[5164:thread1] : gvar = 99.

[5164:thread1] : gvar = 100.

...
...

[5165:thread2] : gvar = 199.

[5165:thread2] : gvar = 200.
Now, no matter how much ever you try executing this program, "gvar" at the end of the program will be always 200 (if you specify 100 as loop count in for loop).
NOTE THAT THE SCOPE OF THE VARIABLE AND THE MUTEX VARIABLE IS SAME. MEANS, GLOBAL VARIABLE PROTECTION SHOULD USE GLOBAL MUTEX VARIABLE!!

Multithreading - Part 1: Basics

Threads: Light-weight Processes (LWP); mostly useful if created in user-space.

Program:

#include <stdio.h>
#include <pthread.h>

int gvar;
void* t1_fun(void *msg)
{
    int i;
    for(i = 0; i < 10; i++)
    {   
        gvar++;
        /*printf("[%d:%s] : gvar = %d.\n", pthread_self(), (char*) msg, gvar);*/
        printf("[%d:%s] : gvar = %d.\n", (long int)syscall(224), (char*) msg, gvar);
    }   
}

int main()

{

    pthread_t t1, t2; 

    char *msg1 = "thread1";

    char *msg2 = "thread2";

    int rc1 = pthread_create(&t1, NULL, t1_fun, (void *) msg1);

    if( rc1 ) { printf("Error for thread 1.\n"); perror("pthread_create"); }

    int rc2 = pthread_create(&t2, NULL, t1_fun, (void *) msg2);

    if( rc2 ) { printf("Error for thread 1.\n"); perror("pthread_create"); }

    

    printf("Threads execution over.\n");

    return 0;

}

Points to Note:

1. The function prototype of the thread should be

 void * fun( void * args);

2. Single arguments (like above) can be directly passed after casting to "void *"; where as

multiple arguments can be passed in the form of structures.

3. To print the LWP (thread) ID, I am using the method

(long int) syscall (224) ==> This is the system call for "gettid" system call.

And note, pthread_self() returns "pthread_t"; and not the "thread id".

4. And for both the threads, I can give the same function (t1_fun).

5. Format of pthread_create: pthread_create(&t1, <thread_attr>, <function>, <function_args>)

Program Output:

$> gcc sample.c -lpthread

$> ls

a.out sample.c

$> ./a.out

Threads execution over.

[5164:thread1] : gvar = 1.

[5164:thread1] : gvar = 2.

Why such output?:
The reason is, we have "just triggered the threads and did not bother about them after that".
To make sure, we get all the printfs of both the threads, the main thread should "wait" for those two threads to "join" it.
Hence, if you provide "pthread_join" call for both the threads, you main thread will not exit UNTIL both the threads completes its execution.

...
...

    int rc2 = pthread_create(&t2, NULL, t1_fun, (void *) msg2);

    if( rc2 ) { printf("Error for thread 1.\n"); perror("pthread_create"); }

    
    /* If the 2nd arg is NOT NULL, the return value of t1 and t2 will be stored there.
     * This pthread_join will suspend the main thread until the t1/t2 completes, terminates or by calling
     * pthread_exit. 
     */
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Threads execution over.\n");

    return 0;

}

Program Output:

$> gcc sample.c -lpthread

$> ls

a.out sample.c

$> ./a.out

[5164:thread1] : gvar = 1.

[5164:thread1] : gvar = 2.

[5164:thread1] : gvar = 3.

[5164:thread1] : gvar = 4.

[5164:thread1] : gvar = 5.

[5164:thread1] : gvar = 6.

...
...

[5165:thread2] : gvar = 19.

[5165:thread2] : gvar = 20.

Intel VS PPC Architecture

PPC Uses Load/Store architecture.
Means, it uses only the load/store instructions to access memory. For the operations, the operands are stored in the registers itself.
Eg. the operands of AND operation are stored in the registers itself.

Intel x86 uses "Register memory architecture" where in one of the operands of AND operation may be in memory and the other one in register.

RISC Vs CISC

Intel : "Hardware to bear more responsibility; software life should be easy"
Apple: "Software to bear major role; hardware life should be easy"

This derived to two widely deployed CPU Architectures

1. Intel formed CISC (Complex Instruction Set Computing)
2. Apple formed RISC (Reduced Instruction Set Computing)
[NOTE that the word "reduced" does not mean the "minimal number of instructions". It means easy and light-weight instructions that takes "minimal" or "reduced" time to execute]

Pros and cons of these two follows:

CPU Performance of a program is calculated as :-

                             seconds        Instructions            cycles           seconds     
  CPU Speed = ------------  =  ----------------  X  ---------------- X -----------
                            program           program         Instruction          cycle

                                              = A X B X C

CISC: Attempts to minimize the number of instructions per program; sacrificing number of cycles per instruction (CISC tries to reduce A at the cost of increased B)

RISC: Attempts to minimize the number of cycles per instruction; sacrificing number of instructions per program (RISC tries to reduce B at the cost of increased A)


Reference: http://www.engineersgarage.com/articles/risc-and-cisc-architecture

Important Kernel Structures and its sizes

NOTE: The following are found in 32-bit Ubuntu system (Kernel version:  3.2.0-29-generic-pae)

1. Process kernel stack = 8KB in 32 bit; 16KB in 64 bit
Basically, 2 pages as process kernel stack

2. task_struct - structure for each process
sizeof(task_struct) = 3236 bytes = 3.1 KB

3. thread_struct - structure of thread info in each task_struct
sizeof(thread_struct) = 128 bytes

/proc File system usages

NOTE: The following are found in 32-bit Ubuntu system (Kernel version:  3.2.0-29-generic-pae)

1. [PID_MAX]:  default - 32768 (short int)
"/proc/sys/kernel/pid_max"

2. [Loadable Modules]
"/proc/modules" Used by "lsmod"

3. [printk levels]: default 7
echo "/proc/sys/kernel/printk"

TCP Keep Alive : Overview

TCP keepalive overview

In order to understand what TCP keepalive (which we will just call keepalive) does, you need do nothing more than read the name: keep TCP alive. This means that you will be able to check your connected socket (also known as TCP sockets), and determine whether the connection is still up and running or if it has broken.

2.1. What is TCP keepalive?

The keepalive concept is very simple: when you set up a TCP connection, you associate a set of timers. Some of these timers deal with the keepalive procedure. When the keepalive timer reaches zero, you send your peer a keepalive probe packet with no data in it and the ACK flag turned on. You can do this because of the TCP/IP specifications, as a sort of duplicate ACK, and the remote endpoint will have no arguments, as TCP is a stream-oriented protocol. On the other hand, you will receive a reply from the remote host (which doesn't need to support keepalive at all, just TCP/IP), with no data and the ACK set.
If you receive a reply to your keepalive probe, you can assert that the connection is still up and running without worrying about the user-level implementation. In fact, TCP permits you to handle a stream, not packets, and so a zero-length data packet is not dangerous for the user program.
This procedure is useful because if the other peers lose their connection (for example by rebooting) you will notice that the connection is broken, even if you don't have traffic on it. If the keepalive probes are not replied to by your peer, you can assert that the connection cannot be considered valid and then take the correct action.

2.2. Why use TCP keepalive?

You can live quite happily without keepalive, so if you're reading this, you may be trying to understand if keepalive is a possible solution for your problems. Either that or you've really got nothing more interesting to do instead, and that's okay too. :)
Keepalive is non-invasive, and in most cases, if you're in doubt, you can turn it on without the risk of doing something wrong. But do remember that it generates extra network traffic, which can have an impact on routers and firewalls.
In short, use your brain and be careful.
In the next section we will distinguish between the two target tasks for keepalive:

• Checking for dead peers
• Preventing disconnection due to network inactivity

2.3. Checking for dead peers

Keepalive can be used to advise you when your peer dies before it is able to notify you. This could happen for several reasons, like kernel panic or a brutal termination of the process handling that peer. Another scenario that illustrates when you need keepalive to detect peer death is when the peer is still alive but the network channel between it and you has gone down. In this scenario, if the network doesn't become operational again, you have the equivalent of peer death. This is one of those situations where normal TCP operations aren't useful to check the connection status.
Think of a simple TCP connection between Peer A and Peer B: there is the initial three-way handshake, with one SYN segment from A to B, the SYN/ACK back from B to A, and the final ACK from A to B. At this time, we're in a stable status: connection is established, and now we would normally wait for someone to send data over the channel. And here comes the problem: unplug the power supply from B and instantaneously it will go down, without sending anything over the network to notify A that the connection is going to be broken. A, from its side, is ready to receive data, and has no idea that B has crashed. Now restore the power supply to B and wait for the system to restart. A and B are now back again, but while A knows about a connection still active with B, B has no idea. The situation resolves itself when A tries to send data to B over the dead connection, and B replies with an RST packet, causing A to finally to close the connection.
Keepalive can tell you when another peer becomes unreachable without the risk of false-positives. In fact, if the problem is in the network between two peers, the keepalive action is to wait some time and then retry, sending the keepalive packet before marking the connection as broken.

_____ _____ | | | | | A | | B | |_____| |_____| ^ ^ |--->--->--->-------------- SYN -------------->--->--->---| |---<---<---<------------ SYN/ACK ------------<---<---<---| |--->--->--->-------------- ACK -------------->--->--->---| | | | system crash ---> X | | system restart ---> ^ | | |--->--->--->-------------- PSH -------------->--->--->---| |---<---<---<-------------- RST --------------<---<---<---| | |

2.4. Preventing disconnection due to network inactivity

The other useful goal of keepalive is to prevent inactivity from disconnecting the channel. It's a very common issue, when you are behind a NAT proxy or a firewall, to be disconnected without a reason. This behavior is caused by the connection tracking procedures implemented in proxies and firewalls, which keep track of all connections that pass through them. Because of the physical limits of these machines, they can only keep a finite number of connections in their memory. The most common and logical policy is to keep newest connections and to discard old and inactive connections first.
Returning to Peers A and B, reconnect them. Once the channel is open, wait until an event occurs and then communicate this to the other peer. What if the event verifies after a long period of time? Our connection has its scope, but it's unknown to the proxy. So when we finally send data, the proxy isn't able to correctly handle it, and the connection breaks up.
Because the normal implementation puts the connection at the top of the list when one of its packets arrives and selects the last connection in the queue when it needs to eliminate an entry, periodically sending packets over the network is a good way to always be in a polar position with a minor risk of deletion.

_____ _____ _____ | | | | | | | A | | NAT | | B | |_____| |_____| |_____| ^ ^ ^ |--->--->--->---|----------- SYN ------------->--->--->---| |---<---<---<---|--------- SYN/ACK -----------<---<---<---| |--->--->--->---|----------- ACK ------------->--->--->---| | | | | | <--- connection deleted from table | | | | |--->- PSH ->---| <--- invalid connection | | | |

Courtesy: http://tldp.org/HOWTO/TCP-Keepalive-HOWTO/overview.html

Semaphores and Mutex

http://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-2-the-mutex/
http://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-2-the-mutex/
http://blog.feabhas.com/2009/10/mutex-vs-semaphores-%E2%80%93-part-3-final-part-mutual-exclusion-problems/

32/64 bit shared library with 32/64 applications

mylib.c
========
#include <stdio.h>

int print_hello()
{
printf("Hello.\n");
return 0;
}

int print_world()
{
printf("World.\n");
return 0;
}

char *get_str()
{
return "Hello World";
}

$> xlc -c mylib.c -o mylib.o [-q64]
$> xlc -qmkshrobj -qexpfile=mylib.exp mylib.o [-q64]
$> cat mylib.exp [You can create this export file manually as well. By default all functions will be exported]
print_hello
print_world
get_str
$> xlc -qmkshrobj mylib.o [-q64]==> This will generate shr.o (mylib.o + mylib.exp)
$> [export OBJECT_MODE=64] ==> Though u compiled the code in 64 bit, ar (nm and strip etc) command does still work in 32 bit mode.
Hence, set the object mode to 64 bit, before calling the "ar" command.
$> ar -rv libfoo.a shr.o
This will generate the shared library (static linking) in AIX.

pgm.c
======
#include <stdio.h>

/* Note these are important to inform linker */
extern int print_hello();
extern int print_world();
extern char* get_str();

int main()
{
print_hello();
print_world();
printf("String from library: %s.\n", get_str());
}

$> xlc -o pgm pgm.c -L/home/harish/temp/ -lfoo [-q32|-q64]
$> ./pgm
Hello.
World.
String from library: Hello World.

NOTE: If you have compiled the application (pgm.c) with -q32 (as 32 bit),
then you would get error :
$> xlc -o pgm pgm.c -L/home/harish/temp/ -lfoo -q32
ld: 0711-317 ERROR: Undefined symbol: .print_hello
ld: 0711-317 ERROR: Undefined symbol: .print_world
ld: 0711-317 ERROR: Undefined symbol: .get_str
ld: 0711-345 Use the -bloadmap or -bnoquiet option to obtain more information.

[Use "-bnoquiet" option to find that ELF (XCOFF) format maintained by library
is different from what 32 bit application expects.]

$> xlc -o test test.c -L/perffs/ptx/harishse/sandbox/temp -lfoo -q32 -bnoquiet
(ld): halt 4
(ld): setfflag 4
(ld): savename test
(ld): filelist 6 1
(ld): i /lib/crt0.o
(ld): i test.o
(ld): lib /perffs/ptx/harishse/sandbox/temp/libfoo.a
(ld): lib /usr/vac/lib/libxlopt.a
(ld): lib /usr/vac/lib/libxl.a
(ld): lib /usr/lib/libc.a
LIBRARY: Shared object libc.a[shr.o]: 2874 symbols imported.
LIBRARY: Shared object libc.a[meth.o]: 2 symbols imported.
LIBRARY: Shared object libc.a[posix_aio.o]: 20 symbols imported.
LIBRARY: Shared object libc.a[aio.o]: 18 symbols imported.
LIBRARY: Shared object libc.a[pse.o]: 5 symbols imported.
LIBRARY: Shared object libc.a[dl.o]: 4 symbols imported.
LIBRARY: Shared object libc.a[pty.o]: 1 symbols imported.
FILELIST: Number of previously inserted files processed: 6
(ld): resolve
RESOLVE: 36 of 6085 symbols were kept.
(ld): addgl /usr/lib/glink.o
ADDGL: Glink code added for 6 symbols.
(ld): er full
ld: 0711-318 ERROR: Undefined symbols were found.
        The following symbols are in error:
 Symbol                    Inpndx  TY CL Source-File(Object-File) OR Import-File{Shared-object}
                              RLD: Address  Section  Rld-type Referencing Symbol
 ----------------------------------------------------------------------------------------------
 .print_hello              [26]    ER PR test.c(test.o)
                                   00000028 .text    R_RBR    [12]    .main
 .print_world              [28]    ER PR test.c(test.o)
                                   00000030 .text    R_RBR    [12]    .main
 .get_str                  [30]    ER PR test.c(test.o)
                                   00000038 .text    R_RBR    [12]    .main
ER: The return code is 8.

Kernel Debugging

[Ref: http://publib.boulder.ibm.com/infocenter/aix/v6r1/index.jsp?topic=%2Fcom.ibm.aix.kdb%2Fdoc%2Fkdb%2Fkdb.htm]

 

kdb command

This command is implemented as an ordinary user-space program and is typically used for

post-mortem analysis of a previously-crashed system by using a system dump file. The kdb command includes subcommands specific to the manipulation of system dumps.

 

KDB kernel debugger

- The KDB kernel debugger is integrated into the kernel and allows full control of the system while a debugging session is in progress. The KDB kernel debugger allows for traditional debugging tasks such as setting breakpoints and single-stepping through code.

- KDB needs to be enabled when the system boots.

- To check if the KDB is enabled or not, issue

$> bosdebug -L

Memory debugger           off
Memory sizes              0
Network memory sizes      0
Kernel debugger           off
Real Time Kernel          off
Backtracking fault log    on
Kernext Memory Tracking   off

- To create a kernel image with KDB enabled, issue

$> bosdebug -D 

This will turn on the kernel debugger. You need to bosboot and reboot in order to take this effect.

$> bosboot -a && reboot

[After of about 20-30 mins, you will have a KDB enabled image}

bosboot: Boot image is 49180 512 byte blocks.

- KDB enabled kernel image is ready. All you gotto do now is, reboot.

If you have HMC kinda machine (where you remotely try to reboot the machine), while booting, you can see Kernel Debugging is enabled.

$> reboot

 -------------------------------------------------------------------------------
                                Welcome to AIX.
                   boot image timestamp: 11:02:54 12/26/2011
                 The current time and date: 11:18:52 12/26/2011
        processor count: 1;  memory size: 2048MB;  kernel size: 28147575
         boot device: /vdevice/v-scsi@30000003/disk@8100000000000000:2
                       kernel debugger setting: enabled
-------------------------------------------------------------------------------

 

One color/partial color photo

http://graphicssoft.about.com/od/gimp/ss/partialcolor_8.htm