Hi Bond, On Tue, Sep 28, 2010 at 12:05 AM, Bond <jamesbond.2k.g@xxxxxxxxx> wrote: > I have to write my own kmalloc. > I am not given any sort of Kernel API to assign or delete memory. > Suppose I have 4GB of memory on Ram. > Some of which is filled and some of which is not filled. > My question is what data structure do I need to maintain in order to be able > to assign memory > to any userspace program when the program requests some bytes of memory > which can be 1 or > more. So user mode programs don't allocate memory using kmalloc. I believe that they wind up calling __get_free_pages. There are many data structures that can be used. The kernel provides 3 different implementations of kmalloc, called, slab, slub and slob. It all depends on you design criteria. The simplest is to maintain a linked list of free spaces. It's simple, but suffers performance issues and fragmentation issues. > My logic for this implementation was to maintain a hashtable. > For example > 1------> points to all the memory addresses which are 1 byte and free > 2------> points to all the memory addresses which are 2 byte and free > 3------> points to all the memory addresses which are 3 byte and free > 4------> points to all the memory addresses which are 4 byte and free > . > . > . > . > . > . > . > n------> points to all the memory addresses which are n byte and free > How can I improve the above schema because to know the location where 1byte > memory is free > I will maintain a pointer which can be u64 or u32 which itself is costlier > than the free memory itself. > So what should I be doing to be able to do above. You could use a bitmap (one bit per byte). Or you could maintain a indexed free list, where an 8-bit index is used. The 8-bit index would be stored using the free memory itself. You'd need to have a separate list for every 256 bytes, but that would have very low overhead. -- Dave Hylands Shuswap, BC, Canada http://www.DaveHylands.com/ -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
