Can kmalloc() return invalid memory?

Question

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;
    }

Don't cast the returned `void *` from `kmalloc`. [A quick google search on the lkml shows that they don't](https://lkml.org/lkml/2013/3/12/14), so neither should you, if you want to see your code merged into the kernel — Elias Van Ootegem, Dec 27 '13 at 12:58
Had another quick look. Casting returns of `kmalloc` and `kmalloc_array` is also mentioned in [the linux kernel coding style document (chapter 14)](https://www.kernel.org/doc/Documentation/CodingStyle): their advice = don't cast — Elias Van Ootegem, Dec 27 '13 at 13:04
If I can't use casting then how does kernel developers suggest me to allocate memory for user defined structures like I am using? — taufique, Dec 27 '13 at 14:51
@Md.TaufiqueHussain: Just drop the cast: `new_data = kmalloc(sizeof *new_data, GFP_ATOMIC);`. Note that using `sizeof *new_data` guarantees that you allocate the correct size. — Keith Thompson, Dec 27 '13 at 16:01
Just remember that because you crash somewhere doesn't mean that's where the bug is. You may have trashed memory elsewhere, calculated some wrong value somewhere, and it manifests in a crash at a different place, such as this function. — nos, Dec 27 '13 at 16:07

Elias Van Ootegem · Accepted Answer · 2015-02-18T08:43:07.673

3

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)

edited Feb 18 '15 at 08:43

answered Dec 27 '13 at 13:20

Elias Van Ootegem

74,482
9
111
149

`table` is declared as follows: struct queue_data table[HASH_PRIME]; HASH_PRIME is declared as a macro. `hash_prime` is calculated as follows: hash_index = hash_it(...); hash_it() calculates hash_index as modulus of HASH_PRIME. So as far as I know there is no way for hash_index to go out of bound. – taufique Dec 27 '13 at 14:46
`HASH_PRIME` is a macro, so it'll probebly be regarded as a signed int, whereas you're passing it as an `unsigned int`, which could, theoretically lead to unexpected results (eg: `unsigned int foo = -10;` assigns `-10 + UINT_MAX + 1` to `foo`) – Elias Van Ootegem Dec 27 '13 at 14:55
Are you suggesting me to use HASH_PRIME as unsigned int? – taufique Dec 27 '13 at 14:57
@Md.TaufiqueHussain: no, I'd suggest checking for unexpected `hash_index` values, and deal with them, then test again, and see if it works – Elias Van Ootegem Dec 27 '13 at 15:00
Ven Ootegem, to add further detail, it's a netfilter module and it don't crash instantly. After running a few days it crashes. So to test after changing according to you it will take a few days I guess. I will inform you the result here after testing. If needed again I hope I will find you again. BTW take a look at my hash_it() function. See if there can be any problem here: http://paste.ubuntu.com/6645890/ – taufique Dec 27 '13 at 15:21
@Md.TaufiqueHussain: first thing: `jhash_2words` expects the arguments, and returns `u32`, so perhaps be consistent in your types, and use the `u32` consistently across your module – Elias Van Ootegem Dec 27 '13 at 15:27
@Md.TaufiqueHussain: Oh, and if you don't mind my being a rep-whore, I'd greatly appreciate an up-vote if you found my input helpful in any way. (on a related note: +1 for the interesting question) – Elias Van Ootegem Dec 27 '13 at 15:35
1

It still is running but I found my mistake. HASH_PRIME is 1999. And in my hash function I multiplied 3 numbers ranging from 0 to 1998, answer of the multiplication is in the range of 0 to 7976023992, while range of __u32 is 4294967295. Thanks for your answer. You pointed out right. – taufique Dec 28 '13 at 12:44

Can kmalloc() return invalid memory?

1 Answers1