Re: my kmalloc implementation

[Dave Hylands]

Hi Bond,

On Sat, Oct 2, 2010 at 11:25 AM, Bond  wrote:
> No not glibc I  want a link to heap implementation in glibc

Look for malloc... in the glibc source code and go from there

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.DaveHylands.com/

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[Bond]

No not glibc I  want a link to heap implementation in glibc

On Sat, Oct 2, 2010 at 10:05 PM, Dave Hylands  wrote:
> Hi Bond,
>
> On Sat, Oct 2, 2010 at 2:34 AM, Bond  wrote:
>>
>>
>> On Sat, Oct 2, 2010 at 1:13 PM, Dave Hylands  wrote:
>>>
>>> Hi Bond,
>>>
>>> Sending to the list this time...
>>> glibc has a fairly sophisticated heap...
>>> Look at glibc alternatives. Each one will have a heap.
>>>
>> Hey Dave thanks for this information.
>>  I do want to have a look.
>> Can you give me some link?
>
> I just googled using the words glibs alternatives. The first page that
> came back is this one:
> 
>
> which has several alternatives listed.
>
> --
> Dave Hylands
> Shuswap, BC, Canada
> http://www.DaveHylands.com/
>



-- 
http://vger.kernel.org/vger-lists.html

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[Dave Hylands]

Hi Bond,

On Sat, Oct 2, 2010 at 2:34 AM, Bond  wrote:
>
>
> On Sat, Oct 2, 2010 at 1:13 PM, Dave Hylands  wrote:
>>
>> Hi Bond,
>>
>> Sending to the list this time...
>> glibc has a fairly sophisticated heap...
>> Look at glibc alternatives. Each one will have a heap.
>>
> Hey Dave thanks for this information.
>  I do want to have a look.
> Can you give me some link?

I just googled using the words glibs alternatives. The first page that
came back is this one:


which has several alternatives listed.

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.DaveHylands.com/

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[Bond]

On Sat, Oct 2, 2010 at 1:13 PM, Dave Hylands  wrote:

> Hi Bond,
>
> Sending to the list this time...
> glibc has a fairly sophisticated heap...
>
> Look at glibc alternatives. Each one will have a heap.
>
> Hey Dave thanks for this information.
 I do want to have a look.
Can you give me some link?

Re: my kmalloc implementation

[Dave Hylands]

Hi Bond,

Sending to the list this time...

On Fri, Oct 1, 2010 at 10:18 PM, Bond  wrote:
>
>
> On Fri, Oct 1, 2010 at 8:13 PM, Dave Hylands  wrote:
>>
>> Hi Bond,
>>
>> There are many different algorithms, and you wanted to know how
>> indexes would work for tracking 1 byte allocations.
>
> For my learning if you can provide some more that would be nice.
> Not only I want to track 1 byte but also if more than one byte is free some
> where
> that also I want to track.

glibc has a fairly sophisticated heap...

Look at glibc alternatives. Each one will have a heap.

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.DaveHylands.com/

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[Bond]

On Fri, Oct 1, 2010 at 8:13 PM, Dave Hylands  wrote:

> Hi Bond,
>
> There are many different algorithms, and you wanted to know how
> indexes would work for tracking 1 byte allocations.
>

For my learning if you can provide some more that would be nice.
Not only I want to track 1 byte but also if more than one byte is free some
where
that also I want to track.

>
> You can spend a lifetime writing and analyzing different heap algorithms.
>
> Ok

Re: my kmalloc implementation

[Dave Hylands]

Hi Bond,

On Fri, Oct 1, 2010 at 3:36 AM, Bond  wrote:
> Wouldn't a sparse matrix implementation of this be a better thing.

There are many different algorithms, and you wanted to know how
indexes would work for tracking 1 byte allocations.

I guess it depends on how you define better...
The algorithm I presented is very fast, and it's O(1). It's limited to
255 bytes, but there are ways of extending it and still making it O(1)
(with the free portion perhaps being O(log2(n) in the general case).

You can spend a lifetime writing and analyzing different heap algorithms.

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.DaveHylands.com/

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[Bond]

Wouldn't a sparse matrix implementation of this be a better thing.


> I don't have a link. But you'd initialize doing something like this:
>
> uint8_t data[256];
>
> free_list = 0;
> for ( i = 1; i < 256; i++ )
> {
>// Add Each byte to the free list.
>data[i] = free_list;
>free_list = i;
> }
>
> Finding a free entry would be something like:
>
> if ( free_list != 0 )
> {
>uint8_t *avail = &data[free_list];
>free_list = *avail;
>*avail = 0;
>return avail;
> }
>
> and freeing would be something like this:
>
> index = freePtr - data;
> data[index] = free_list;
> free_list = index;
>
> --
>

Re: my kmalloc implementation

[Dave Hylands]

Hi Bond,

On Tue, Sep 28, 2010 at 1:43 AM, Bond  wrote:
>
>
> On Tue, Sep 28, 2010 at 11:59 AM, Dave Hylands  wrote:
> Hi Bond,
>>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.
>>You could use a bitmap (one bit per byte). Or you could maintain a
>>indexed free list, where an 8-bit index is used.
> I googled above thing
> http://www.google.co.in/search?sourceid=chrome&client=ubuntu&channel=cs&ie=UTF-8&q=index+free+list
> but indexed free list I could not find any where.
> Can you give some link to what you are referring to.
>>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.

I don't have a link. But you'd initialize doing something like this:

uint8_t data[256];

free_list = 0;
for ( i = 1; i < 256; i++ )
{
// Add Each byte to the free list.
data[i] = free_list;
free_list = i;
}

Finding a free entry would be something like:

if ( free_list != 0 )
{
uint8_t *avail = &data[free_list];
free_list = *avail;
*avail = 0;
return avail;
}

and freeing would be something like this:

index = freePtr - data;
data[index] = free_list;
free_list = index;

-- 
Dave Hylands
Shuswap, BC, Canada
http://www.DaveHylands.com/

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[Bond]

On Tue, Sep 28, 2010 at 11:59 AM, Dave Hylands  wrote:
Hi Bond,

>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.

>You could use a bitmap (one bit per byte). Or you could maintain a
>indexed free list, where an 8-bit index is used.
I googled above thing
http://www.google.co.in/search?sourceid=chrome&client=ubuntu&channel=cs&ie=UTF-8&q=index+free+list
but indexed free list I could not find any where.
Can you give some link to what you are referring to.

>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.





On Tue, Sep 28, 2010 at 12:15 PM, John Mahoney  wrote:
>I would start by reading how it is already done...is that cheating.
>http://lxr.free-electrons.com/source/mm/page_alloc.c
I am not that competent that I could understand that code which is given on
that link.
Before posting here I had looked that link.I want to understand what data
structure or
mechanism is used to do that.So once I get that thing with a simple program
I surely will
finish that link which you also pointed out.


On Tue, Sep 28, 2010 at 12:15 PM, Manish Katiyar  wrote:
>Bond,
>You might want to look at the example of malloc at the end of KnR.
Can you tell me which page or chapter you are referring to?
I was not able to find or missed what you suggested.

Re: my kmalloc implementation

[Manish Katiyar]

Bond,

You might want to look at the example of malloc at the end of KnR.

On Mon, Sep 27, 2010 at 11:05 PM, Bond  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.
> 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.



-- 
Thanks -
Manish
==
[$\*.^ -- I miss being one of them
==

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[John Mahoney]

On Tue, Sep 28, 2010 at 2:05 AM, Bond  wrote:
> I have to write my own kmalloc.
> I am not given any sort of Kernel API to assign or delete memory.

I would start by reading how it is already done...is that cheating.

http://lxr.free-electrons.com/source/mm/page_alloc.c

--
John

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[Manish Katiyar]

Bond,

You might want to look at the example of malloc at the end of KnR.

On Mon, Sep 27, 2010 at 11:05 PM, Bond  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.
> 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.



-- 
Thanks -
Manish
==
[$\*.^ -- I miss being one of them
==

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

Re: my kmalloc implementation

[Dave Hylands]

Hi Bond,

On Tue, Sep 28, 2010 at 12:05 AM, Bond  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 ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ

my kmalloc implementation

[Bond]

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.
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.