I am writing a linux kernel module in which I implemented a linked list. I know there is a list API in linux kernel but when I implemented it I didn't know so implemented it handling raw pointer with kmalloc(). After running several hours, kernel is crashing and in crash log it is showing "General Protection Fault". Log also shows that it is occuring from my function for searching linked list. Apparently search function is like below which has no logical error.
/*
* Searches in a certain index of hash table for a data
* returns NULL if not found else returns pointer of that element in the table
*/
struct queue_data * search_table(unsigned int hash_index, struct queue_data *new_data)
{
/* Taking a new queue pointer. Which will be pointing to the queue represented
* by new_data at last. */
struct queue_data *ret;
/* First initializing it with first queue on the list */
ret = table[hash_index].next;
/* Iterating through the list to find the desired queue */
while(ret != NULL) {
/* Checking if current queue matches our criteria */
if(ret->saddr == new_data->saddr &&
ret->daddr == new_data->daddr &&
ret->dest == new_data->dest &&
ret->ssrc == new_data->ssrc) {
/* It matched. So I can return it */
return ret;
}
/* It didn't match so I need to go to next queue */
ret = ret->next;
}
/* No queue matched out criteria. Because if it matched it would have not
* come this far. It would have returned before.
* So I need to return a NULL. Now value of 'ret' is NULL.
* I can return 'ret'
*/
return ret;
}
It's also apparent that insert function is also flawless in logical point of view. As General Protection Fault usually occurs in when invalid memory access occurs and I never used a memory allocated by other than kmalloc(). Now my question is if I use a memory allocated by kmalloc then there is any possibility of using invalid memory which should I check before use?
Fraction of crash Log is here:
[ffff8804130cb690] general_protection at ffffffff81661c85
[exception RIP: search_table+52]
RIP: ffffffffa00bc854 RSP: ffff8804130cb748 RFLAGS: 00010286
RAX: d6d4575455d55555 RBX: ffff88040f46db00 RCX: 0000000000000018
RDX: 02b53202ab706c17 RSI: ffff8803fccaaa00 RDI: 00000000000c2568
RBP: ffff8804130cb748 R8: ffffffff8180cb80 R9: 000000000000016d
R10: a3d70a3d70a3d70b R11: ffff8803fccaab58 R12: ffffc9001262cc38
R13: 000000000000079f R14: ffff8803fccaaa00 R15: ffffffffa00cbee8
ORIG_RAX: ffffffffffffffff CS: 0010 SS: 0018
When inserting, I checked allocated memory by kmalloc with this :
/* Allocating and initializing a new queue.
* If a queue corresponding to it already exists then it's data will
* copied and this queue will be dropped.
* Else this queue will be inserted to the hash table that manages the queues.
*/
new_data = (struct queue_data *)kmalloc(sizeof(struct queue_data), GFP_ATOMIC);
if (!new_data) {
//printk(KERN_ALERT "pkt_queue EXCEPTION: new_data\n");
return NULL;
}
Looking at the code you posted, the only possible source for the General Protection Fault I can see is this line:
ret = table[hash_index].next;
You're not checking the size of table, so perhaps you're accessing out-of-bounds memory? No way to be sure, without knowing how, where and what table is declared as, and how you initialize it.
After looking at your comment, saying hash_index, an unsigned int, is the result of a modulus of the HASH_PRIME macro, it could be that at some point, you're encountering possible signed-unsigned arithmetic issues, so that, despite the modulus on HASH_PRIME, you are in fact going out of bounds. Perhaps add:
if (hash_index >= HASH_PRIME) hash_index = HASH_PRIME-1;//or error
Just for completeness' sake: as I pointed out in the comments, the functions you're using all use the kernel's u32 type. As it turns out, that was the reason for your code still accessing wrong memory. (Typed this update on phone... Hate it)