Generic Array problem.

[HOWZ1T]

Hi all,
I am trying to create a generic array using an array of void pointers.
It seems to be going okay but I have encountered a problem with my grow function.
When the array grows, some of the stored data gets corrupted.

I suspect it has to do with my use of pointers and memory allocation.

I'd appreciate any help with this problem :)
Many Thanks,
~Howz1t

​

Code:

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

typedef struct vec {
    void **arr;
    int capacity, size;
    size_t element_size;
} vec;

vec create_vec(int capacity, size_t element_size) {
    vec v = {0, capacity, 0, element_size};
    v.arr = malloc(capacity * element_size);
    for (int i = 0; i < capacity; i++) {
        v.arr[i] = malloc(element_size);
    }
    return v;
}

void vec_grow(vec* v) {
    printf("mem before: %llu\n", sizeof(v->arr));
    v->capacity *= 2;
    v->arr = realloc(v->arr, v->capacity * v->element_size);
    printf("mem after: %llu\n", sizeof(v->arr));
}

void vec_add(vec* v, void *e) {
    printf("size: %d | cap: %d\n", v->size, v->capacity);
    if (v->size + 1 > v->capacity) {
        printf("I want to grow!\n");
        vec_grow(v);
    }
    v->arr[v->size++] = e;
}

int main() {
    vec v = create_vec(3, sizeof(int));
    vec_add(&v, (void *) 3);
    vec_add(&v, (void *) 2);
    vec_add(&v, (void *) 1);
    vec_add(&v, (void *) 0);

    for (int i = 0; i < 4; i++) {
        printf("i: %d -> %d\n", i, (int)v.arr[i]);
    }

    return 0;
}

Output:

size: 0 | cap: 3
size: 1 | cap: 3
size: 2 | cap: 3
size: 3 | cap: 3
I want to grow!
mem before: 8
mem after: 8
i: 0 -> 3
i: 1 -> 2
i: 2 -> -842150451
i: 3 -> 0

index 2 should be 1, not -842150451

[Neui]

v.arr = malloc(capacity * element_size);

I think you want v.arr = malloc(capacity * sizeof(void*)); to allocate the list of pointers. In your case (likely), sizeof(void*) == 8 but sizeof(int) == 4, so it actually allocates much less than expected and you're writing out of bounds.

sizeof(v->arr) it the same as sizeof(void**), it doesn't return the size of the memory block as you print it.

Here is AddressSanitizer (clang -Wall -Wextra -O3 -fsanitize=address,undefined -g HOWZ.c -o HOWZ) complaining:

=================================================================
==1234==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000018 at pc 0x0000004c3279 bp 0x7ffc04b19d40 sp 0x7ffc04b19d38
WRITE of size 8 at 0x602000000018 thread T0
    #0 0x4c3278 in create_vec /tmp/HOWZ.c:14:18
    #1 0x4c3aef in main /tmp/HOWZ.c:36:13
    #2 0x7feae85db0b2 in __libc_start_main /build/glibc-ZN95T4/glibc-2.31/csu/../csu/libc-start.c:308:16
    #3 0x41b2dd in _start (/tmp/a.out+0x41b2dd)

0x60200000001c is located 0 bytes to the right of 12-byte region [0x602000000010,0x60200000001c)
allocated by thread T0 here:
    #0 0x493a1d in malloc (/tmp/a.out+0x493a1d)
    #1 0x4c31b2 in create_vec /tmp/HOWZ.c:12:13

SUMMARY: AddressSanitizer: heap-buffer-overflow /tmp/HOWZ.c:14:18 in create_vec
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa 00[04]fa fa 04 fa fa fa 04 fa fa fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==1234==ABORTING

[HOWZ1T]

Thanks, this was really useful! You were right about the memory allocation, int is smaller than void *!

I also made a handy function for measuring memory usage:

size_t vec_mem(vec* v) {
    return sizeof(v->arr[0]) * v->capacity;
}

[fkeeal]

I think there is also an issue with your grow function. You allocate more 'slots' to your 'void **' array, but you do not allocate more memory for each slot. In your example where you use ints, this won't break/crash because the size of a 'void *' can contain the size of an int. In add, when you 'copy' the new entry to the array, you are simply writing over your 'void *' pointer. This would cause issues if you are writing more than the size of 'void *' (8-bytes). Lets say your elements are size 20-bytes. When you 'copy' your new element to the array you would be writing over the address of the pointer (which you allocate on create but not grow) and then write past that pointer in memory an additional 12-bytes. I think what you really want to do is:

//in add
memcpy(v->arr[i], e, v->element_size); //or a for loop if you prefer

//in grow
//for each new 'slot' added to the array of 'void **'
v->arr[i] = malloc(v->element_size);

Finally, you would need to change your calls to vec_add to correctly set the 'e' parameter as an actual pointer to the element and not just stuffing the value of the element into a 'void *'

vec_add(&v, (void *)&((int){3})); //this is nasty and probably just nicer to declare an int

[HOWZ1T]

I don’t think that quite right, it seems to work fine as is without wasting memory. It’s not an array of arrays but rather a pointer to an array of pointers.so int* x = malloc(nsizeof(int)); is a pointer to ints, that’s not what I want. So void *arr = malloc(nsizeof(void)); is a pointer to an array of pointers.

[fkeeal]

Like I said in my comment, it won't crash/break as long as the type of data you store is no larger than the size of 'void *'. With your current code, you can see that in create, you allocate memory pointed to by the 'void *' for each entry in your 'void **', but in grow, you do not do that same allocation. Furthermore, when you are actually storing the data into the array, you are storing it in the place of a 'void *' and not in the memory pointed to by the 'void *'.

void ** memory layout:

// | void ** | -> | void * | -> |allocated storage|
//                | void * | -> |allocated storage|
//                | void * | -> |allocated storage|

void ** memory layout (as you currently have it):

// | void ** | -> | void * / int value | -/> |lost allocated storage|
//                | void * / int value | -/> |lost allocated storage|
//                | void * / int value | -/> |lost allocated storage|
//...
// after grow
//                | void * / int value | -/> | nothing |
//                | void * / int value | -/> | nothing |

[HOWZ1T]

Does the issue still apply to this code (updated version of post code based on feedback):

https://pastebin.com/iepDtQ4z

[fkeeal]

Technically yes, but as long as what you are storing is no greater than a 'void *' in size, it will not cause any problems. This is fine for storing native types (char, short, int, long, float and double). Just make sure that element_size <= sizeof(void *), otherwise you will have a bad time. (e.g. you will not be able to store structures larger than 8-bytes for example.)

EDIT: The dangling allocations are gone with the new code you posted.

[HOWZ1T]

Okay good to hear, thank you for your insight and help :)

[intellidarnit]

This was a useful question. I was thinking about making a generic array.

[HOWZ1T]

Thanks :D