Thursday, August 8, 2019

free()ing an invalid pointer

One of my friend asked this question. What happens if you free() an invalid pointer location? i.e. the pointer which was not returned by malloc(). I thought for a while. Few years back when I skimmed through glibc malloc code, I remember it was some kind of lookup based on pointer. After a while, I replied saying it would be a memory leak.

But wait a minute, the free() call returns nothing. While the programmer is happy about his bad code, internally there is something baking bad without his notice. When customer reports a long run memory leak issue, then the furnace erupts and developer is under intense pressure. So there should be something else free() doing. So let's try a sample program

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

int main()
{
    char ptr = (char)(malloc(100));

    ptr++;

    free(ptr);
}

And the output is...

nanda@nanda-MS-7640:/media/nanda/PERSONAL/c_code/const$ ./a.out 
free(): invalid pointer
Aborted (core dumped)

Yes the ABORT is called by glibc and the actions are performed as per the SIGABRT behaviour of the calling process. This was a fantastic learning. Now let's look at the glibc code.

if you try to free invalid pointer, this is result

if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
      || __builtin_expect (misaligned_chunk (p), 0))
    malloc_printerr ("free(): invalid pointer");

this guy calls abort

malloc_printerr (const char *str)
{
  __libc_message (do_abort, "%s\n", str);
  __builtin_unreachable ();
}

So what's the point here?

Look at the start of free() function : https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#3092

In line 3109 it tries to get the metadata associated with the allocated memory

p = mem2chunk (mem);

In line 3131

ar_ptr = arena_for_chunk (p);
  _int_free (ar_ptr, p, 0);

The _int_free has this comment

/* Little security check which won't hurt performance: the
     allocator never wrapps around at the end of the address space.
     Therefore we can exclude some size values which might appear
     here by accident or by "design" from some intruder.  */

  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
      || __builtin_expect (misaligned_chunk (p), 0))
    malloc_printerr ("free(): invalid pointer");

Probably in our case, it was misaligned chunk. There is no way ptr in actual code would have wrapped around.


Ending Note:

This is specific to glibc implementation. The man pages do not mandate specific behaviour in such a case. It just says the pointer to free() should be the one returned by malloc.

More deep dive on malloc/free code in subsequent posts.

Sunday, May 19, 2019

How does is_same works?

Sometimes I turn  inquisitive towards the type traits of modern c++. A more dig into glibc unfolds the mystery behind the implementation. So how does is_same work then?

See the below code. I have shamelessly copied libstdc++ code :-) for learning myself.

Find it here: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/type_traits

#include <iostream>

template<typename _Tp, _Tp __v>
struct integral_constant
{
    static constexpr _Tp                  value = __v;
    typedef _Tp                           value_type;
    typedef integral_constant<_Tp, __v>   type;
    constexpr operator value_type() const noexcept { return value; }
};

/// The type used as a compile-time boolean with true value.
typedef integral_constant<bool, true>     true_type;

/// The type used as a compile-time boolean with false value.
typedef integral_constant<bool, false>    false_type;

/// is_same
template<typename, typename>
    struct is_same
    : public false_type {
        is_same() { std::cout << "False Type" << std::endl;}
    };

template<typename _Tp>
    struct is_same<_Tp, _Tp>
    : public true_type
{
        is_same() { std::cout << "True Type" << std::endl;}
};

int main()
{
        is_same<int,int> test1;
        is_same<int,unsigned char> test2;
        std::cout << is_same<int,int>::value << std::endl;
        std::cout << is_same<int,unsigned char>::value << std::endl;
}


The fact is that, is_same works on template specialization! Hurray! It has O(1) complexity. So how is that being achieved?

consider is_same<int,int>

As you know that modern c++ allows template specialization for particular cases. The same thing works here as well!

is_same<> with same datatype resolves to specialized template

template<typename _Tp>
    struct is_same<_Tp, _Tp>
    : public true_type
{
        is_same() { std::cout << "True Type" << std::endl;}
};

which is inherited from true_type which itself is a struct integral_constant having value true and type bool. Note the static constexpr value which is evaluated in compile time i.e. no runtime overhead is seen. Also the weird template structure contains first argument as typename and second as value. These are somethings which even I did not knew are possible to write in this fashion.

Needless to say, is_same<> evaluating on different types is quite trivial template substitution and tracing on similar basis results in value = false.

I was scratching my head why static is required for the first member of integral_constant. I feel its due to the fact that is_same is structure and its value is constant throughout. static makes that each copy of is_same is referencing to same copy in memory for 'value' member. The other members do not consume memory anyway!

Most importantly, the output of program:

True Type
False Type
1
0