Invalid write when initializing an array of linked lists

Question

So I have this function that allocates and initialize to NULL what will be an array of linked lists. I actually want this function to return an array of NULL pointers so that I can fill it with linked lists later.

static t_tokens **init_tokens_groups(size_t size)
{
    t_tokens **toks_groups;
    if (!(toks_groups = malloc(sizeof(toks_groups) * size + 1)))
        exit(EXIT_FAILURE);
    while (size + 1)
    {
        printf("size: %zu\n", size);
            toks_groups[size] = NULL;
            size--;
    }
    return (toks_groups);
}

It works fine, but when I'm running my program (which is a minimalist shell) into Valgrind,

valgrind --track-origins=yes ./mysh

I'm running into this:

==4914== Invalid write of size 8
==4914==    at 0x10AD6B: init_tokens_groups (tokens_split.c:39)
==4914==    by 0x10AE06: split_tokens (tokens_split.c:68)
==4914==    by 0x1093D9: prompt_loop (sh21.c:38)
==4914==    by 0x10944A: main (sh21.c:57)
==4914==  Address 0x4a508f8 is 8 bytes inside a block of size 9 alloc'd
==4914==    at 0x483A7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4914==    by 0x10AD42: init_tokens_groups (tokens_split.c:35)
==4914==    by 0x10AE06: split_tokens (tokens_split.c:68)
==4914==    by 0x1093D9: prompt_loop (sh21.c:38)
==4914==    by 0x10944A: main (sh21.c:57)
==4914== 
==4914== Invalid write of size 8
==4914==    at 0x10AD6B: init_tokens_groups (tokens_split.c:39)
==4914==    by 0x10AE06: split_tokens (tokens_split.c:68)
==4914==    by 0x109369: dispatch (sh21.c:19)
==4914==    by 0x1093F6: prompt_loop (sh21.c:42)
==4914==    by 0x10944A: main (sh21.c:57)
==4914==  Address 0x4a509f8 is 8 bytes inside a block of size 9 alloc'd
==4914==    at 0x483A7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4914==    by 0x10AD42: init_tokens_groups (tokens_split.c:35)
==4914==    by 0x10AE06: split_tokens (tokens_split.c:68)
==4914==    by 0x109369: dispatch (sh21.c:19)
==4914==    by 0x1093F6: prompt_loop (sh21.c:42)
==4914==    by 0x10944A: main (sh21.c:57)

I really don't understand where it's coming from, since I'm just initializing those pointers to NULL at this stage, and I have no problems or bugs (well, not that I've detected) while filling, manipulating and reading those linked lists arrays in the program. I'm assuming I'm doing something weird with the memory, but I don't see where.

Answer 1

This:

toks_groups = malloc(sizeof(toks_groups) * size + 1))

is wrong, and causes a problem later the first time you do toks_groups[size] = NULL; (which is outside the allocated region). Valgrind tells you that the invalid write is of 8 bytes because the size of a pointer on your system is 8 bytes.

If you want to allocate size + 1 elements you should put the expression in parentheses. The fact that you are doing sizeof(toks_groups) is also very strange and doesn't make much sense. What you probably wanted to do is the following:

toks_groups = malloc(sizeof(*toks_groups) * (size + 1)))

If you only want to allocate size elements (not size + 1) then remove the + 1 from malloc() and change the while (...) condition. You also don't really need the while at all, if you want to initialize everything to NULL you can just use calloc() instead of malloc().

Also, as a rule of thumb:

1. Use meaningful names. Calling something size when it's clearly not a size, but just a number of elements, is confusing.
2. Use the proper code constructs. Using a while loop to iterate on a range of values is really counter intuitive and can easily lead to errors.

A better version of the above code would be the following:

static t_tokens **init_tokens_groups(size_t n)
{
    t_tokens **toks_groups;

    if (!(toks_groups = calloc(sizeof(*toks_groups) * (n + 1))))
        exit(EXIT_FAILURE);

    return toks_groups;
}

I am still unsure whether you actually need the additional element or not, but you should know that.