The msgbuf structure in SysV message queue

Most of you who are familiar with SysV message queue must be aware of the formatting the message to following weird structure. The weirdest part is none other than the char mtext[1]. What is this unusual stuff? It is nothing but plays the role of expandable structure.

struct msgbuf {
    long mtype;       /* message type, must be > 0 */
    char mtext[1];    /* message data */
};

For example:

If you wish to send a message of 40 bytes, then one needs to create a structure with following size.

sizeof(long)+40;

Of-course, first element should be of type 'long' which represents message type.

Now, why is this weird mtext[1]. It could have been mtext[0]? Simple, SysV IPCs were introduced way long back. There was no C standard of having zero length arrays in structure. That is the sole reason behind mtext[1]. I used to scratch my head for a very long time and it has been eventually settled [hope even louses are out]. If any other reason, please leave comment in the box.

Glibc malloc in linux

How does glibc implement malloc? I guess as many of you know, in traditional nix systems, it is implemented using brk() and sbrk() system calls. Basically these system calls adjust the heap pointer of process (or rather break pointer) to new location as per desired size. However in linux, glibc employs a different methodology in implementing malloc functions. For "x" number of bytes, the glibc allocates via brk()/sbrk() system calls while anything equal or above "x", mmap system call is used. Currently this threshold is 128k. Now what is mmap(). In the case of mmap(), the process address space is not adjusted rather the kernel allocates memory from its page cache and attaches the Virtual Memory Address to the process address space. Hence the heap segment is untouched and stack can grow freely upwards teasing heap :D.

Alright, can we have plausible example? Here it is :-). The first one is with 127k and latter is 128k. Follow the explanations after example code. Both of the code have sleep() function to be in wait state for some time. This enables me to see process maps. To see how malloc() behaves, one needs to run system call trace tool (strace) to understand the flow for different sizes.

1) 127k

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

#define BUF_SIZE (127 * 1024)

int main()
{
    char *temp = NULL;

    temp = (char*)(malloc(BUF_SIZE));
    strcpy(temp, "LINUX-TUX :-)");
    sleep(100);
}

compile with gcc and run the resulting executable with strace
>>strace ./a.out

I have stripped most of the portions especially the memory mappings of shared libraries. The actual snippet looks like

<<snip>>
brk(0)                                  = 0xb1d000
brk(0xb5d000)                           = 0xb5d000
rt_sigprocmask(SIG_BLOCK, [CHLD], [], 8) = 0
rt_sigaction(SIGCHLD, NULL, {SIG_DFL, [], 0}, 8) = 0
rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
<<snip>>

As you can see malloc() implementation uses brk() system calls to increase the data segment width. Initially it passes 0 to find current data segment location and later adds 127k to inform the OS to adjust data segment to new location.

How to verify? Most unix systems list memory mapings in /proc/<pid>/maps. Lets do the same for our case. As I mentioned earlier, the sleep serves the purpose of grabbing memory map or else the proc entry of the process gets flushed out.

In one more terminal, obtain process-id of a.out

>>pgrep a.out
14565

>>cat /proc/14565/maps
00400000-00401000 r-xp 00000000 08:0a 1708078                            /home/nandakumar/a.out
00600000-00601000 r--p 00000000 08:0a 1708078                            /home/nandakumar/a.out
00601000-00602000 rw-p 00001000 08:0a 1708078                            /home/nandakumar/a.out
00b1d000-00b5d000 rw-p 00000000 00:00 0                                  [heap]
7f5fe1ca0000-7f5fe1e5d000 r-xp 00000000 08:0a 658188                     /lib/x86_64-linux-gnu/libc-2.17.so
7f5fe1e5d000-7f5fe205d000 ---p 001bd000 08:0a 658188                     /lib/x86_64-linux-gnu/libc-2.17.so
7f5fe205d000-7f5fe2061000 r--p 001bd000 08:0a 658188                     /lib/x86_64-linux-gnu/libc-2.17.so
7f5fe2061000-7f5fe2063000 rw-p 001c1000 08:0a 658188                     /lib/x86_64-linux-gnu/libc-2.17.so
7f5fe2063000-7f5fe2068000 rw-p 00000000 00:00 0
7f5fe2068000-7f5fe208b000 r-xp 00000000 08:0a 658164                     /lib/x86_64-linux-gnu/ld-2.17.so
7f5fe2268000-7f5fe226b000 rw-p 00000000 00:00 0
7f5fe2288000-7f5fe228a000 rw-p 00000000 00:00 0
7f5fe228a000-7f5fe228b000 r--p 00022000 08:0a 658164                     /lib/x86_64-linux-gnu/ld-2.17.so
7f5fe228b000-7f5fe228d000 rw-p 00023000 08:0a 658164                     /lib/x86_64-linux-gnu/ld-2.17.so
7ffffa977000-7ffffa998000 rw-p 00000000 00:00 0                          [stack]
7ffffa99d000-7ffffa99f000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

Here we go :D. The new break pointer obtained from system call matches with proc entry [and obviously should match ;-)]. The length if you have calculate is [00b1d000-00b5d000]= 256K

Wait a minute! How come so much? That's how malloc does. It allocates more than what is required and manages later requests internally. This avoids frequent system call overheads and also fragmentation to certain extent

If you are curious to know the logic behind the calculation, please dissect sysmalloc() function in glibc/malloc/malloc.c {Home work :-)}

2) 128k (mmap). Here is next example!

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

#define BUF_SIZE (128 * 1024)

int main()
{
    char *temp = NULL;

    temp = (char*)(malloc(BUF_SIZE));
    strcpy(temp, "LINUX-TUX :-)");
    sleep(100);
}
Snipping unnecessary parts:

<<snip>>
mmap(NULL, 135168, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fbd51e67000
rt_sigprocmask(SIG_BLOCK, [CHLD], [], 8) = 0
rt_sigaction(SIGCHLD, NULL, {SIG_DFL, [], 0}, 8) = 0
rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
<<snip>>

Now lets look into maps

>>pgrep a.out
15060

>>cat /proc/15060/maps
00400000-00401000 r-xp 00000000 08:0a 1708078                            /home/nandakumar/a.out
00600000-00601000 r--p 00000000 08:0a 1708078                            /home/nandakumar/a.out
00601000-00602000 rw-p 00001000 08:0a 1708078                            /home/nandakumar/a.out
7fbd518c0000-7fbd51a7d000 r-xp 00000000 08:0a 658188                     /lib/x86_64-linux-gnu/libc-2.17.so
7fbd51a7d000-7fbd51c7d000 ---p 001bd000 08:0a 658188                     /lib/x86_64-linux-gnu/libc-2.17.so
7fbd51c7d000-7fbd51c81000 r--p 001bd000 08:0a 658188                     /lib/x86_64-linux-gnu/libc-2.17.so
7fbd51c81000-7fbd51c83000 rw-p 001c1000 08:0a 658188                     /lib/x86_64-linux-gnu/libc-2.17.so
7fbd51c83000-7fbd51c88000 rw-p 00000000 00:00 0
7fbd51c88000-7fbd51cab000 r-xp 00000000 08:0a 658164                     /lib/x86_64-linux-gnu/ld-2.17.so
7fbd51e67000-7fbd51e8b000 rw-p 00000000 00:00 0
7fbd51ea8000-7fbd51eaa000 rw-p 00000000 00:00 0
7fbd51eaa000-7fbd51eab000 r--p 00022000 08:0a 658164                     /lib/x86_64-linux-gnu/ld-2.17.so
7fbd51eab000-7fbd51ead000 rw-p 00023000 08:0a 658164                     /lib/x86_64-linux-gnu/ld-2.17.so
7fff48a97000-7fff48ab8000 rw-p 00000000 00:00 0                          [stack]
7fff48bfe000-7fff48c00000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

If you glance at the process maps, the address returned by mmap() 0x7fbd51e67000 is attached to process address space with size of 7fbd51e67000-7fbd51e8b000 which is 144k. The kernel for mmap returns memory which is aligned by pagesize. If you look at mmap system call, the number supplied by glibc is 128k+4k. As said earlier, it may be for some house keeping stuffs. Later kernel allocates with multiples of pagesize. The extra memory returned by kernel is zeroed out and useless which means even if you write at that location, it will be still zero (citation required). Also note that there is no heap segment now!

The memory allocation is complex matter and one needs to dwell into glibc code if you wish to know more. The mmap() system call is quite complex implementation in linux kernel :-). If you wish to know why malloc follows this mechanism, please read Linux System Programming by Robert Love which provides excellent insight on this topic.

As mentioned, memory topics are quite confusing and complicated. If you have feedback or corrections, please feel free to leave a comment. It also helps me to improve.

References:

1) Linux system programming by Robert Love

2) glibc malloc code (just peeped into)

3) If you wish, you can check linux kernel mmap code [mm/mmap.c -- SYSCALL_DEFINE6(mmap_pgoff, ...)]. To give some heads-up, the code is quite complicated and requires to have good knowledge of Linux Kernel MM subsystem

Speculative stores

Recently I read this wonderful article on C11 atomic variables and its possible usage in Linux Kernel. This is why admire community coding. People throng into fruitful discussions and eventually best comes out. The final result is lot of learning from all corners. In the article, Mr.Corbet mentioned about speculative stores which means the consequences of nasty compiler optimizations. I wrote about how intelligibly compilers handle certain cases here and here. So lets look at following example which is also mentioned in the article.

int y=2;

int do_some_work()
{
    y = 2;

    if (y)
        ....
    else
        ....
}

In above code, many programmers may expect compiler to rip off the 'else' branch. That's the dangerous part if the code belongs to kernel space. Why? Now 'y' is a data segment entity and can be manipulated by any CPU in SMP system. It can be even set to zero by some CPU. In that case, the optimization of compiler will result in untidy results. I cannot say how do compilers treat such code in kernel space since it requires bit of time to experiment.

How can we do it in user space? Very simple! Run more than one thread and lets see how assembly looks like. Note that this code is not thread safe

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

int y=0;
void* thread_routine(void* arg);

void* thread_routine(void* arg)
{
        y=1;
        if(y)
                printf("Y is Y in thread = %d\n", pthread_self());
        else
                printf("Y is !Y in thread = %d\n", pthread_self());
}

void* thread_routine2(void* arg)
{
        y=0;
        if(y)
                printf("Y is !Y in thread = %d\n", pthread_self());
        else
                printf("Y is Y in thread = %d\n", pthread_self());
}

int main(int argc, char **argv)
{
        pthread_t tid[2];
        int thread_rc = 0;

        thread_rc = pthread_create(&tid[0], NULL, thread_routine, NULL);
        assert(!thread_rc);
        thread_rc = pthread_create(&tid[1], NULL, thread_routine2, NULL);
        assert(!thread_rc);
}

I am stripping of unnecessary sections and retaining only the thread stack assembly. The thread_routine2 function also looks similar

thread_routine:
.LFB2:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $16, %rsp
        movq    %rdi, -8(%rbp)
        movl    $1, y(%rip)
       movl    y(%rip), %eax <-- I know you are tricking me :D
       testl   %eax, %eax
       je      .L2
        call    pthread_self
        movq    %rax, %rsi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        jmp     .L4
.L2:
        call    pthread_self
        movq    %rax, %rsi
        movl    $.LC1, %edi
        movl    $0, %eax
        call    printf
.L4:
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc

If you glance at assembly code, gcc is smart man :D. It knows that it should not optimize in such cases. If you observe the assembly, gcc emits code for both if and else part even though there is straight forward assignment before the branching. Also look at "movl y(%rip), %eax"! Instead of blindly copying value of '1' to EAX register, the actual value of 'y' is copied and tested :-).

Caveat: Multi threading may not emulate a SMP scenario in linux. Nowadays operating systems tend to hook threads to particular CPU rather than multiple CPUs. This is mainly to avoid penalty incurred due to cache line invalidations especially when global variable is involved and can be modified. Nevertheless, a thread can be pre-empted in middle of operation (say while if{} branch can be precisely evaluated) unless lock is held explicitly. Understanding SMP systems is quite intricate however opens up to wide variety of thoughts in programming world. Two cores are not two brains you know ;-). There are lot difficulties while handling such scenarios!

Finally short assignments ;-): 

1) Examine the assembly in case of -O2 switch
2) Remove threads and run bare minimal program while retaining data segment  variable and observe what gcc does!

Handling of absurd code by gcc - The absurd sequel ;-)

I did mention about this in my previous blog here. Now slightly extending the condition to this

int test(unsigned int k)
{
        if (k <= 0)
                printf("BUG IN COMPILER: THIS IS ABSURD BLOCK\n");
}

We can expect few changes by compiler. Now this has two conditions, one for comparing for zero and other for comparing for Sign bit. What does compiler emit?

.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $16, %rsp
        movl    %edi, -4(%rbp)
        cmpl    $0, -4(%rbp)<-- Just compare with zero and kick programmer 
        jne     .L3
        movl    $.LC0, %edi
        call    puts


As expected it emits only condition for comparing with zero :D. gcc is very smart with this case too! Everything remains same except we have "call puts" now to print in case of condition is true.

Handling of absurd code by gcc

We programmers are bound to make silly mistakes and tend to write absurd code :-). If these things are spotted during code reviews or internal testing, then you are spared. If the buggy stuffs land in customer's runway, then we are in trouble :-). Today's blog is to closely examine gcc behavior's to such absurd code. This example is not exhaustive. I will try to come up with few more examples in future to learn myself and share observations. As of now, here is sample code.

#include<stdio.h>

int test(unsigned int k)
{
        if (k < 0)
                printf("BUG IN COMPILER: THIS IS ABSURD BLOCK\n");
}

int main()
{
        unsigned int k = 9;
        test(k);
        return 0;
}

As a programmer you know the absurdity of the code. So how does gcc behave. We can only say by looking into assembly output emitted by gcc. Here is the assembly dump of the program (with default optimization).

<snip>

test:
.LFB0:
        .cfi_startproc
        pushq   %rbp /* Save return pointer */
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp /* New base pointer */
        .cfi_def_cfa_register 6
       movl    %edi, -4(%rbp) /* Copy Argument */
       popq    %rbp /* Restore base pointer */
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   test, .-test
        .globl  main
        .type   main, @function
main:
.LFB1:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $16, %rsp
        movl    $9, -4(%rbp)
        movl    -4(%rbp), %eax
        movl    %eax, %edi
       call    test /* Here is call to function */
        movl    $0, %eax
        leave
        .cfi_def_cfa 7, 8
        ret

<snip>


As you can see, the entire 'if' block is discarded by gcc :-D. Compilers are smart nowadays ;-). They know how to get rid of weeds and make ELF fertile :-). Even though we inject irrelevant code, compilers (atleast gcc) get rid of them in final binary. Let me see what more weird stuff can be experimented with. Hope you enjoyed this small and simple post. Critiques and comments are always welcome!

LD_PRELOAD environment variable - A short insight

I believe most of the programmers (unix C programmers) are aware of the application of LD_PRELOAD env variable. Basically it can be used to override any functionality of libc with the in house implementation. For ex: 'getaddrinfo' may have different implementation for an organization and cannot replaced in libc code itself (due to GPL restrictions). The organization may not be wanting to expose their internal implementation to public domain to preserve intellectual stuffs. Can't they write their own implementation? That is crux of the matter. They may be using third party application and want to modify certain functionalities for their use. Instead of modifying glibc code, they replace with their own implementation. Aha! how is this irony :-). Forget it! The usual method is to implement same implementation with prototype matching libc and create a dynamic shared library. Later set the LD_PRELOAD environment variable to this dynamic shared object. This makes the program loader to preload the created .so before libc gets loaded. The loader marks all the symbols used by executable based on the order of libs loaded. In above case, 'getaddrinfo' will be linked to created library than libc. Even though I knew this information, never attempted to write a program. Finally I was tempted to write and here it is. This guy overrides malloc implementation

The library for malloc -- Buggy!!!

my_lib.c

#include <stdio.h>

char *virus_data_segment = (char*)(0x1234567890)

void* malloc(size_t size)
{
        printf("Get lost! I do not have even a penny to give ;-)\n");
        return virus_data_segment;
}

created shared library: gcc -shared -o libmy_lib.so -fPIC my_lib.c

Now the actual fun starts :D

set LD_PRELOAD

>>LD_PRELOAD=./libmy_lib.so

execute ls command

>> ls
Get lost! I do not have even a penny to give ;-)
Segmentation fault

LOL! The malloc has been overridden and 'ls' cannot run (may be 'ls' is using malloc). Why segmentation fault? Because malloc returned an address region not belonging to process address space. Here is output when we return NULL.

Get lost! I do not have even a penny to give ;-)
Get lost! I do not have even a penny to give ;-)
Get lost! I do not have even a penny to give ;-)
Get lost! I do not have even a penny to give ;-)
Get lost! I do not have even a penny to give ;-)
Get lost! I do not have even a penny to give ;-)
Get lost! I do not have even a penny to give ;-)
Get lost! I do not have even a penny to give ;-)
Get lost! I do not have even a penny to give ;-)
ls: memory exhausted

Strange is it not! Either it is retrying or multiple places trying to allocate.

Yes, LD_PRELOAD is well known :-) but scribbled here in case for anyone can provide more insight. I will try to gather some more information if possible and post them.

The 'cd' command

As everyone knows, the 'cd' command in Linux changes the current working directory to new directory. Really?! To be precise it changes the current working directory of the process in interest to new working directory. It cannot change 'cwd' of other processes. So whats the big deal?

Internally 'cd' command uses chdir system call to change current working directory. As mentioned before, 'chdir' can only change 'cwd' of process which is calling it not any other process. So what? :-). Now think of bash which is executing 'cd' command. How does it change its 'cwd' to new directory? Usually other commands like 'ls', 'dir' etc.. are executed with fork+exec combination i.e. by spawning a new process. Now in case of 'cd' you cannot spawn new process since new process cannot change 'cwd' of bash.

Aha! there is interesting part. Now how do you work it around? What does bash do? Bash does this by embedding the implementation of 'cd' in its own executable i.e. 'cd' is a command in bash itself rather than being stand-alone executables like 'ls' or 'dir'. Bash implements 'cd' in itself and exposes it as command in terminal. The user still interprets it as stand alone command because of this bash trick ;-). That means along with other commands enumerated by bash (using PATH variable), it also inserts 'cd' into the pool. Since 'cd' is now part of bash process, the changing to new working directory is straight forward :-). You can check your bin directory if any executable with name 'cd' could be found like one below ;-)

nandakumar@heramba ~ $ which ls || echo -e "get lost :-)"
/bin/ls
nandakumar@heramba ~ $ which cd || echo -e "get lost :-)"
get lost :-)

Even I was not aware of this fact until I recently read System Programming Book by Robert Love. The beauty of book is how Mr.Robert Love presents such minute things so accurately. At the end of day, there was a happy learner!