malloc, recasting and free

Question

I have some structures to store different kinds of lists: typedef int db_int; typedef char db_string[DB_STRING_LEN];

struct List_db_int {
    struct List_db_int *next;
    struct List_db_int *prev;
    db_int v;
};
struct List_db_string {
    struct List_db_string *next;
    struct List_db_string *prev;
    db_string v;
};
struct List_db_void {
    struct List_db_void *next;
    struct List_db_void *prev;
};

I also have an union which can store any of this list pointers:

union Uni_list {
    struct List_db_int *db_type_int;
    struct List_db_string *db_type_string;
    struct List_db_void *db_type_void;
};

I want to create a function which will delete some elements from lists but I want it to be list type agnostic so I come with following solution:

    /*data is an array of pointers to begin of lists*/
    union Uni_list *data;
    struct List_db_void *last; 
    for (i = 0; i < ELEMENTS_; i++) {
        last = data[i].db_type_void->next;
        for (j = 0; j < HOW_MANY_ELEMENTS_REMOVE; j++) {
            free_list(last, t->cols[i]/*type of column*/);
            last = last->next;
        }
        data[i].db_type_void->next = last;
    }

Here is the free_list function: void

free_list(struct List_db_void *elm, enum db_type type) {
    switch(type) {
        case db_type_int:
            free((struct List_db_int*) elm);
            break;
        case db_type_string:
            free((struct List_db_string*) elm);
            break;
        default:
            /*Should not reach*/
            return ;
            break;
    }
}

But it does not work correctly and when I try to read modified lists, I end up with:

*** Error in `./ppbase': free(): invalid pointer: 0x00007f84aa47f678 ***                                                       
======= Backtrace: =========                                                                                                   
/usr/lib/libc.so.6(+0x72ecf)[0x7f84aa14cecf]                                                                                   
/usr/lib/libc.so.6(+0x7869e)[0x7f84aa15269e]                                                                                   
/usr/lib/libc.so.6(+0x79377)[0x7f84aa153377]                                                                                   
./ppbase[0x402001]                                                                                                             
./ppbase[0x40217e]                                                                                                             
./ppbase[0x40273d]                                                                                                             
/usr/lib/libc.so.6(__libc_start_main+0xf5)[0x7f84aa0fbbc5]                                                                     
./ppbase[0x4009d9]                                                                                                             
======= Memory map: ========                                                                                                   
00400000-00404000 r-xp 00000000 08:04 10883382                           /home/hafron/dev/ppbase/ppbase                        
00603000-00604000 rw-p 00003000 08:04 10883382                           /home/hafron/dev/ppbase/ppbase                        
01797000-017b8000 rw-p 00000000 00:00 0                                  [heap]                                                
7f84a9ec4000-7f84a9ed9000 r-xp 00000000 08:03 49858                      /usr/lib/libgcc_s.so.1                                
7f84a9ed9000-7f84aa0d9000 ---p 00015000 08:03 49858                      /usr/lib/libgcc_s.so.1                                
7f84aa0d9000-7f84aa0da000 rw-p 00015000 08:03 49858                      /usr/lib/libgcc_s.so.1                                
7f84aa0da000-7f84aa27c000 r-xp 00000000 08:03 9136                       /usr/lib/libc-2.18.so                                 
7f84aa27c000-7f84aa47b000 ---p 001a2000 08:03 9136                       /usr/lib/libc-2.18.so                                 
7f84aa47b000-7f84aa47f000 r--p 001a1000 08:03 9136                       /usr/lib/libc-2.18.so                                 
7f84aa47f000-7f84aa481000 rw-p 001a5000 08:03 9136                       /usr/lib/libc-2.18.so                                 
7f84aa481000-7f84aa485000 rw-p 00000000 00:00 0                                                                                
7f84aa485000-7f84aa4a5000 r-xp 00000000 08:03 7209                       /usr/lib/ld-2.18.so                                   
7f84aa672000-7f84aa675000 rw-p 00000000 00:00 0                                                                                
7f84aa6a1000-7f84aa6a4000 rw-p 00000000 00:00 0                                                                                
7f84aa6a4000-7f84aa6a5000 r--p 0001f000 08:03 7209                       /usr/lib/ld-2.18.so                                   
7f84aa6a5000-7f84aa6a6000 rw-p 00020000 08:03 7209                       /usr/lib/ld-2.18.so                                   
7f84aa6a6000-7f84aa6a7000 rw-p 00000000 00:00 0                                                                                
7fff249c8000-7fff249e9000 rw-p 00000000 00:00 0                          [stack]                                               
7fff249fe000-7fff24a00000 r-xp 00000000 00:00 0                          [vdso]                                                
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]                                            
zsh: abort (core dumped)  ./ppbase < tests/filter       

How should I use free function in this code correctly? Can I safly cast any of the List into: db_type_void->next (line 5 in second example)?

Answer 1

This function:

free_list(struct List_db_void *elm, enum db_type type) {
    switch(type) {
        case db_type_int:
            free((struct List_db_int*) elm);
            break;
        case db_type_string:
            free((struct List_db_string*) elm);
            break;
        default:
            /*Should not reach*/
            return ;
            break;
    }
}

is exactly the same as (considering that we never go through the default branch, as your comment suggests)

free_list(struct List_db_void *elm, enum db_type type) {
    free(elm);
}

Pointer casts are for the type system and have no dynamic semantics. They disappear after compiling, so to speak.

This being said I'm taking a look to see what causes the segfault.

EDIT: Probably this!

for (j = 0; j < HOW_MANY_ELEMENTS_REMOVE; j++) {
    free_list(last, t->cols[i]/*type of column*/);
    last = last->next;
}

You're using last after freeing it. Do something like

for (j = 0; j < HOW_MANY_ELEMENTS_REMOVE; j++) {
    struct List_db_void *temp = last->next; 

    free_list(last, t->cols[i]/*type of column*/);
    last = temp;
}

Answer 2

        free_list(last, t->cols[i]/*type of column*/);
        last = last->next;

seems to be incorrect. free_list frees last which is accessed in the next line.

EDIT:

Regarding

Can I safly cast any of the List into: db_type_void->next

It is not clean. C standard guarantees only that first member of a struct is at offset 0. So, casting ->next to the typed struct List_db_string * is ok. But there is no guarantee that struct List_db_string * and struct List_db_void * have the same internal representation so that

        struct List_db_void *next;
        next = last->next;  /* was last = last->next in question */

can cause problems (theoretically; it will probably do the right thing on every relevant platform).

A more clean way would be casting last->next to the correct type and accessing its next attribute.

NOTE: all this is valid for accessing next; behaviour for other members (prev, v) is undefined without the mentioned cast.

EDIT:

Implementing operations on a generic type like

struct list_head {
    struct list_head *next;
    struct list_head *prev;
}

allows e.g.

struct List_db_int {
    struct list_head head;
    int v;
}

struct List_db_string {
    string v;
    struct list_head head;
}

(note the different order of attributs). You can calculate the object from head by using a container_of pattern.

Answer 3

One problem is the following pair of lines

free_list(last, t->cols[i]/*type of column*/);
last = last->next;

This code is freeing the memory for last and then immediately using that freed memory on the next line. The caching of the next pointer should be done before you free last.

I'm unsure if this is causing your segfault but it's definitely something that should change. My suspicion is that the error is most likely in the allocation function. Could you post that?