Branch optimization in gcc

With -O2 option, gcc by default does some of branch optimizations. This one I recently discovered trying to understand __builtin_expect() gcc buitlin.

Consider following example:

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

int main()
{
        char *c = malloc(10);
        if (c ==NULL) {
                printf("MALLOC FAILED\n");
                return 1;
        }
        free(c);
        printf("MALLOC SUCCEEDED\n");
}

If I compile as 'gcc -S test.c' and 'gcc -O2 -S test.c' and compare the assembly here is the output. Now what does that mean? In the optimized version, the malloc() is considered to be error free for most of cases (likely condition) by gcc and the part of code is moved near the text segment. The failure part is put in the sequel. How come gcc is doing such kind of optimization? Does this do based upon memory footprint of system? If so, how about cross compiler situation? I have no answer. Is this optimization based on exit point (since our code is small, gcc may be predicting things after malloc() are really less and hence nothing to worry on optimization since all code may be within cacheline size). My assumption was such kind of optimization is only left to user based on __builtin_expect() directive even if -O2 switch is used.

Look at assembly output difference

1) Optimized one

.section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "MALLOC FAILED"
.LC1:
        .string "MALLOC SUCCEEDED"
        .section        .text.startup,"ax",@progbits
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB34:
        .cfi_startproc
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        movl    $10, %edi
        call    malloc
        testq   %rax, %rax
        je      .L4
        movq    %rax, %rdi
        call    free
        movl    $.LC1, %edi
        addq    $8, %rsp
        .cfi_remember_state
        .cfi_def_cfa_offset 8
        jmp     puts
.L4:
        .cfi_restore_state
        movl    $.LC0, %edi
        call    puts
        movl    $1, %eax
        popq    %rdx
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE34:
        .size   main, .-main
        .ident  "GCC: (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2"
        .section        .note.GNU-stack,"",@progbits

2) Non-Optimized

.section        .rodata
.LC0:
        .string "MALLOC FAILED"
.LC1:
        .string "MALLOC SUCCEEDED"
        .text
        .globl  main
        .type   main, @function
main:
.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    $10, %edi
        call    malloc
        movq    %rax, -8(%rbp)
        cmpq    $0, -8(%rbp)
        jne     .L2
        movl    $.LC0, %edi
        call    puts
        movl    $1, %eax
        jmp     .L1
.L2:
        movq    -8(%rbp), %rax
        movq    %rax, %rdi
        call    free
        movl    $.LC1, %edi
        call    puts
.L1:
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   main, .-main
        .ident  "GCC: (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2"
        .section        .note.GNU-stack,"",@progbits


If you look at optimized assembly code

testq    %rax, %rax
je    .L4

which is callng the failure one. However right after 'je .L4', we see success code

movq    %rax, %rdi
call    free
movl    $.LC1, %edi
addq $8, %rsp       .cfi_remember_state                                                                                                                                            
.cfi_def_cfa_offset8                                                                                                                                          
jmp    puts

That means gcc has optimized the branch prediction. So we do not have to use __builtin_expect() for such cases ;-). Not sure if this is applicable for all sort branching or only branches with less code.

The non-optimized part takes normal course.

subq    $16, %rsp
movl    $10, %edi
call    malloc
movq    %rax, -8(%rbp)
cmpq    $0, -8(%rbp)
jne    .L2   // call usual malloc
movl    $.LC0, %edi //failure
call    puts
movl    $1, %eax
jmp    .L1


Let me know if you have alternate thoughts. The code is compiled under Linux mint x86_64 architecture. Not sure if same behavior could be seen across all archs.

Format specifiers for definitive types

In one of my previous post, I mentioned about an ugly #ifdef workaround for printing definitive types like uint64_t. However this is not at all required :-). There is already format specifiers for these types in inttypes.h! It contains ARCH independent format specifiers for many definitive types like uint64_t, uint32_t, uint16_t etc.. and their signed counterparts too!

A quick glance around the header file is below! It is located in "/usr/include/inttypes.h"

/* Unsigned decimal notation.  */
# define SCNu8          "hhu"
# define SCNu16         "hu"
# define SCNu32         "u"
# define SCNu64         __PRI64_PREFIX "u"

and __PRI64_PREFIX is defined as

# if __WORDSIZE == 64
#  define __PRI64_PREFIX        "l"
#  define __PRIPTR_PREFIX       "l"
# else
#  define __PRI64_PREFIX        "ll"
#  define __PRIPTR_PREFIX
# endif


There are several such macros for many types and variants (hex, octal etc..). Glance through the header if you are interested further!

A quick short program.

#include <stdio.h>
#include <inttypes.h>

int main()
{
        uint64_t test = 0x12345678;
        printf("%"SCNu64" : %"SCNx64"\n", test, test);
}

Output: 305419896 : 12345678

and no warnings too ;-)

What happens if a pthread holding mutex lock exits without unlocking?

This was question asked by someone. It was kind of new to me :-). It was very good question indeed. So what is the answer? Let me write a simple C code.

#include <stdio.h>

#include <pthread.h>

pthread_mutex_t nasty_mutex = PTHREAD_MUTEX_INITIALIZER;

void*

pthread_mutex_function (void *arg)

{

    pthread_mutex_lock(&nasty_mutex);

    printf("Got my lock ;)\n");

    pthread_mutex_unlock(&nasty_mutex);

}

void*

pthread_mutex_nasty_function (void *arg)

{

    pthread_mutex_lock(&nasty_mutex);

}

int main (void)

{

    pthread_t tid[3];

    int i=0;

    pthread_create(&tid[0], NULL, pthread_mutex_nasty_function, NULL);

    pthread_create(&tid[1], NULL, pthread_mutex_function, NULL);

    pthread_create(&tid[2], NULL, pthread_mutex_function, NULL);

    for (; i<3; i++) {

        pthread_join(tid[i], NULL);

    }

}

So what is the output? LOL :D deadlock. This is really nasty coding. I thought LWP state would be cleared even if thread exits however, that is not case. The cleanup happens after process exits not LWP. Conclusion is that we have to make sure nothing crashes when holding lock, that does not mean it should crash after releasing mutex lock ;). For me it was one more learning.

Code tested in Linux mint 14 /64 bit. Validations in code are left to user!

Edit 1: I did mention that thread should not crash while holding a lock. But if the lock is private to process, then entire process address space goes for toss after crash. This will not lead to any deadlocks ;-). However, if thread exits gracefully without releasing lock, then consequences are obvious. I am not sure what happens if the mutex lock is shared across processes and the process holding lock crashes. I will give a try sometimes later when I get time.

My version of tail program based on inotify

Honestly speaking there is no intention behind the program I did! It is just for learning and time pass.
So how does linux tail program works?

Earlier it was based on sleep and stat. The program used to stat and check the modified time of file.
If file was modified, the difference used to get printed to stdout. Otherwise, it would go for sleep and check back again.

Recently it seems like the tail program in linux has been changed to use inotify system calls (using strace command). Honestly I realized after writing one of mine. I thought I would publish inotify version of mine. But world is gone way ahead and I am late :-). But still it was very good learning for me. I feel the other unix variant use the earlier version of tail since inotify is specific to linux.

So here is the program. It is quite basic and expect more features in future release :-). Test, raise bugs and provide feedback!
https://github.com/nkumar85/tail

Programming Gotcha - 2

#include<stdio.h>

int test();

int main()
{
    test(1,2);
}

int test()
{
    printf("Got ya!!\n");
}

So what is the output of the above program?

If you think that, it would result in compilation error then try the program yourself! Yeah.. It does not result in any error. Instead the output is

Got ya!!

So why is it like that? As per C standards, any function declaration with blank arguments can take any number of arguments. It is the common silly mistakes most programmers do including me :-).

How do we get out of such problem? Modify the prototype with explicit void declaration

int test(void);

Now the compiler throws up error!

Thanks for one of the nice tutorial I had in office which exposed this type of mistake. Honestly even I did not knew about it.


Note: The code was compiled using gcc on a 64 bit linux machine

Programming Gotcha - 1

This is something C programmers do and it is simple mistake. However the mistake can cost you days in debugging. Eventually the mistake turns out to be trivial, however the impact will be huge.

Consider an example cited by my friend:


int main()
{
        uint64_t var = 0;
        var |= (1 << 45);
        printf("%lu\n", var);
}

The above one looks pretty simple right. But there is mistake :-). Where?

Output: 0

Oooooooo... The output is not expected. So what is the problem. See line #4. The constant '1' is treated as 32 bit number by compiler :-). There you go! The shift by left 45 times leads to var being assigned '0' (or invalid number if operation is rotation). You got the point. This can lead to waste of time while debugging. Fortunately gcc warns about this.

warning: left shift count >= width of type [enabled by default]

If you have lot of files, you may even ignore these warnings. It is better to convert these warnings to errors as stated in previous blogs. So how do we correct it? Just typecast!! Since I am using 64 bit machine I have done some ugly ifdef. This can be done in proper way (kindly comment on writing good ifdef or checking for CPU arch). So here is complete program.

#include <stdint.h>
#include <stdio.h>

#define ARCH 64

#ifdef ARCH
        #if ARCH == 64
                #define FORMAT "%lu\n"
        #else
                #define FORMAT "%llu\n"
        #endif
#else
        #define ARCH 32
        #define FORMAT "%lu\n"
#endif

int main()
{
        uint64_t var = 0;
        var |= ((uint64_t)1 << 45);
        printf(FORMAT, var);
}

The output: 35184372088832

You got it right now and no gcc warnings too! As always kindly comment if you have suggestions and improvements.

Blocking echo on terminal

There may be situation where in you may have to stop echo of characters on console while user types in. For ex: when prompted for password. This can be done very easily by using set of glibc library calls namely tcgetattr and tcsetattr. These library calls internally use ioctl on hardware to achieve the required functionality on terminal. You can achieve with following flow.

1)      Get old terminal configuration using tcgetattr
2)      Mask off echo
3)      Set new configuration to the terminal immediately using tcsetattr and TCSANOW.
4)      Do the work.
5)      Restore the old terminal settings.

Simple is it. So here is the code tested on linux box. Hope you will find it useful. Again I have tried to maintain at-most modularity so that these things can be used as APIs. Code should be portable easily across OSes using glibc.

#include <stdio.h>
#include <unistd.h>
#include <termios.h>
#include <stdint.h>

#define TRUE  1
#define FALSE 0

int term_get_current (struct termios* term)
{
    if (term && !tcgetattr(STDIN_FILENO, term)) {
        return TRUE;
    }

    return FALSE;
}

int term_echo_set (struct termios* term, uint8_t echo_flag)
{
    if (term) {
        term->c_lflag = echo_flag? (term->c_lflag | ECHO):(term->c_lflag & ~ECHO);
        if (!tcsetattr(STDIN_FILENO, TCSANOW, term)) {
            return TRUE;
        }
    }

    return FALSE;
}

int term_restore (struct termios* term)
{
    if (term) {
        if(!tcsetattr(STDIN_FILENO, TCSANOW, term)) {
            return TRUE;
        }
    }

    return FALSE;
}

int main()
{
    struct termios term_old, term_new;
    char buf[50] = {0};

    if (!term_get_current(&term_old)) {
        printf("Unable to get terminal current instance\n");
        goto end;
    }

    term_new = term_old;

    printf("Password Please: ");

    if (!term_echo_set(&term_new, FALSE)) {
        printf("Unable to turn terminal echo off\n");
        goto end;
    }

    scanf("%s", buf);

    /*
     * If turning back echo ON does not succeed, do not exit!
     * Instead proceed to restore old terminal settings
     * In case of failure, do not try to echo the password
     */
    if (!term_echo_set(&term_new, TRUE)) {
        printf("Unable to turn terminal echo on\n");       
    } else {
        printf("\n\nYour password is: %s\n", buf);
    }

    if (!term_restore(&term_old)) {
        printf("Unable to restore old terminal settings\n");
    }

end: return 0;   
}

Compile using gcc. I have not shown output here since it needs to be tried on your own machines.

Off-Topic:

The man pages of tcsetattr has lot of other interesting options to play with terminal. Just have look at man pages.

Please leave comments or suggestions if you have.