I have a struct in C which mimics a hashtable, except it is an array of linked lists.
The length of the array is predetermined by the hash_length and is set to 2^hash_length.
My function here is supposed to free all of the memory allocated by its respective ht_create function. By looping through the array of linked lists, and freeing all of its nodes, and then freeing the array, followed by the hashtable itself.
Through running this code however, I am encountering a heap-use after free. I believe that the problem lies in the way I wrote the function itself but I cant seem to pinpoint the error. I am unsure whether this is enough information to determine a problem, let me know if there is further clarification needed.
void ht_destroy(struct hashtable *ht) {
for(int i = 0; i < my_exp(2,ht->hash_length); ++i) {
struct llist *lst = &ht->list[i];
struct llnode *curnode = lst->front;
struct llnode *nextnode = NULL;
while (curnode) {
nextnode = curnode->next;
free(curnode->str);
free(curnode);
curnode = nextnode;
}
free(&ht->list[i]);
}
free(ht->list);
free(ht);
}
This should be a minimal reproducible example, one that simply creates a hashtable using ht_create, and then frees memory using ht_destroy
// my_exp(a,b): raises a to the bth power.
// Requires: b >= 0
int my_exp(int a, int b) {
if (b == 0) {
return 1;
}
int tot = a;
for (int i = 1; i < b; ++i) {
tot *= a;
}
return tot;
}
struct llnode {
char *str;
struct llnode *next;
};
struct llist {
struct llnode *front;
};
struct hashtable {
int hash_length;
struct llist *list;
};
struct hashtable *ht_create(int hash_length) {
struct hashtable *ht = malloc(sizeof(struct hashtable));
ht->list = malloc(my_exp(2,hash_length) * sizeof(struct llist));
ht->hash_length = hash_length;
for(int i = 0; i < my_exp(2,hash_length); ++i ){
(ht->list)[i].front = NULL;
}
return ht;
}
void ht_destroy(struct hashtable *ht) {
for(int i = 0; i < my_exp(2,ht->hash_length); ++i) {
struct llist *lst = &ht->list[i];
struct llnode *curnode = lst->front;
struct llnode *nextnode = NULL;
while (curnode) {
nextnode = curnode->next;
free(curnode->str);
free(curnode);
curnode = nextnode;
}
free(&ht->list[i]);
}
free(ht->list);
free(ht);
}
int main(void) {
struct hashtable *ht = ht_create(2);
ht_destroy(ht);
}
>Solution :
This line is causing undefined behavior:
free(&ht->list[i]);
ht->list[i] is an array element. The array ht->list was allocated dynamically, but the addresses of its individual elements were not, so you can’t free them. The dynamically-allocated elements are in the linked list reached from ht->list[i].head, and you freed them in the while loop.
The "use after free" is because &ht->list[0] is equivalent to ht->list, so the first iteration of the for loop is freeing the entire array, then subsequent iterations try to use elements of that freed array. And you then try to free it again with free(ht->list).
Get rid of the above line.