OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 2:36 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: new/delete...
PostPosted: Mon Dec 04, 2006 6:21 pm 
Offline
Member
Member
User avatar

Joined: Fri Sep 29, 2006 8:59 am
Posts: 397
Hi guys...
I've been working on the memory management stuff
about tow months ago and i got my physical memory
management working fine also the virtual mm working
fine, i mean paging...but until now i can't write
the "new/delete" they realy giving me headache,
so do you know any good links,open src or may be
good advice can help me out.
Thanx.


Top
 Profile  
 
 Post subject: Re: new/delete...
PostPosted: Tue Dec 05, 2006 5:04 am 
Offline
Member
Member
User avatar

Joined: Mon Dec 04, 2006 6:06 am
Posts: 158
Location: Berlin, Germany
abuashraf wrote:
but until now i can't write
the "new/delete" they realy giving me headache ...

Try to look at Doug Lea's Home Page. He has written and updated a malloc implementation since 1987. Look for "malloc" under the Software section. The code is available, but also read his design of the memory allocator article.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Dec 05, 2006 7:23 am 
Offline
Member
Member
User avatar

Joined: Thu Nov 16, 2006 12:01 pm
Posts: 7612
Location: Germany
Erm... I assume abusharaf got malloc() working allright, but wants to implement operator new() and operator delete(), the ones required by C++...

_________________
Every good solution is obvious once you've found it.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Dec 05, 2006 9:01 am 
Offline
Member
Member
User avatar

Joined: Fri Sep 29, 2006 8:59 am
Posts: 397
No Solar until now i didn't get "malloc()" and my real problem is about
it, and i don't know how malloc works...so i can't implement it.
nice explain would be helpful.
Thanx.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Dec 05, 2006 3:18 pm 
Offline
Member
Member
User avatar

Joined: Mon Dec 04, 2006 6:06 am
Posts: 158
Location: Berlin, Germany
Solar wrote:
Erm... I assume abusharaf got malloc() working allright, but wants to implement operator new() and operator delete(), the ones required by C++...

The new and delete operators shouldn't be that difficult, when you have a working malloc(). See the attached files. Remove the exception stuff if it gives you problems (it however should disable automaticly when supplying the parameter -fno-exceptions to GCC).

abuashraf wrote:
No Solar until now i didn't get "malloc()" and my real problem is about
it, and i don't know how malloc works...so i can't implement it.

Look at the links I gave you.

A very simple solution (but not very efficient in terms of speed) is to maintain a linked list with free chunks of memory and a linked list with used chunks of memory. When malloc() gets called with a size it has to search the linked list with free chunks for a chunk that is exactly the size or greater. Now remove the chunk from the list, split it up if it is greater than the size allocated, add the allocated chunk to the not-free linked list and eventually add the remaining free chunk to the free linked list. When free() gets called it gets a bit more complicated because of fragmentation. You remove the chunk from the not-free linked list and add it to the free linked-list, which should actually be sorted in terms of the memory position. Now see if the just inserted chunk is bound to the previous and/or next chunk and merge them if it does.

The algorithm is O(N) for N the number of allocated/free chunks, which is very bad for a memory allocator. But it works and it almost simple to implement.

When first initialized the linked list with free chunks has to be created. For that you have to know the available memory of your system. If booting using the multiboot standard (ie. GRUB) you can access this information. Just add the free memory blocks GRUBs tell you about to the linked list and that's it.

A lot of improvement can be made to the memory manager. Some of these improvements are discussed in the article I mentioned: http://gee.cs.oswego.edu/dl/html/malloc.html

Hope you get it to work.


Attachments:
File comment: C++ implementation of New. It is just calling malloc(), free() and abort() if failing (or throwing an exception).
new.cpp [1.12 KiB]
Downloaded 43 times
File comment: Header file for New. Only used when special calls are used. (Rename to no extension for proper C++ inclusion)
new.h [1.03 KiB]
Downloaded 70 times
Top
 Profile  
 
 Post subject:
PostPosted: Wed Dec 06, 2006 1:11 am 
Offline
Member
Member
User avatar

Joined: Thu Nov 16, 2006 12:01 pm
Posts: 7612
Location: Germany
I second Walling. Get malloc() to work first, new() / delete() build on top of them. Doug Lea's dlmalloc() is about the best instructional source you can find.

_________________
Every good solution is obvious once you've found it.


Top
 Profile  
 
 Post subject:
PostPosted: Wed Dec 06, 2006 4:08 pm 
Offline
Member
Member
User avatar

Joined: Fri Sep 29, 2006 8:59 am
Posts: 397
Thank you Walling thank you Solar
i'm fine now. :)


Top
 Profile  
 
 Post subject:
PostPosted: Fri Dec 08, 2006 4:03 pm 
Offline
Member
Member

Joined: Sat Nov 18, 2006 9:11 am
Posts: 571
Let me know if you get anything implemented, i'm working on a memory manager in C currently. Trying to make it as efficient as possible for worst case things, like allocating single bytes of memory, etc. I am trying to not waste space as much as possible, and still make it fast for allocating. Once complete I am going to take the above examples, and compile them into a test application to compare all the overheads I can think of, like allocation/deallocation/reallocation speed (on all different size data types), memory wasteage (amount allocated vs. amount total used). If you get anything implemented, I'd love to see how you've done it and add it into my comparison once I get it ready. Since this is for purely virtual memory allocation, I will compile and run the manager on a buffer in memory under win xp for initial testing, with plans to integrate the managers into my OS for real-world testing. I am just trying to figure out a good way to track actual memory used vs. memory requested as generically as possible, any ideas are welcome. Anyways, once completed, or at least useable, i will post everything open source for people to play with and test any ideas out. Probably take me a few weeks to get everything where I want it, will try to comment and seperate as much as possible for ease of use/learning.


Top
 Profile  
 
 Post subject:
PostPosted: Fri Dec 08, 2006 8:32 pm 
Offline
Member
Member

Joined: Sat Nov 18, 2006 9:11 am
Posts: 571
Almost forgot, do most people recommend doing things the "standard" way, by using sbrk and brk, or by doing it in some other manner, like just having a flat memory space to play with (for example, my kernel stays in the upper 1gb of virtual memory, while my application uses the lower 3gb) and just let the allocator hand out this space as it sees fit, with the kernel simply allocating memory as each page is read/written too, or some other scheme to ask the kernel for a page at a time, and tell the kernel which virtual address to assign it to, I dunno, tons of possibilities, just wondering what everyone else is doing, or if there are any (non obvious/overlooked) pro's/con's to each method. I am leaning towards not using brk and sbrk, because I just don't like the idea on how they work, and when I migrate my OS to other platforms that don't have MMU's and virtual memory, it will really be crappy. Only problem then would be benchmarking other allocators that do rely on brk and sbrk, again any suggestions welcome ;).


Top
 Profile  
 
 Post subject:
PostPosted: Sat Dec 09, 2006 6:46 am 
Offline
Member
Member
User avatar

Joined: Mon Dec 04, 2006 6:06 am
Posts: 158
Location: Berlin, Germany
Ready4Dis, that is very interesting. Looking forward for that benchmark and other news.

I'm only creating some test OS for the moment to get some experience, but I have a lot of ideas about my memory manager in a future OS. It is going to be a global memory manager seeing the memory as one flat space. Since the OS will be a virtual machine I can optimize the memory manager in some ways. There is still some worst case problems I have to figure out as well. And of course write the implementation. :)


Top
 Profile  
 
 Post subject:
PostPosted: Sat Dec 09, 2006 3:52 pm 
Offline
Member
Member
User avatar

Joined: Fri Sep 29, 2006 8:59 am
Posts: 397
Here is the code but i think you won't like it
beacuse it was made in the "standerd way" as you said
using "kbrk function" and most of the sources i saw
they were kind of similar of this code.
The code in its earliear stage and i would like to make
it better so may i see your code then i can improve mine.
Thanx.


Attachments:
File comment: kmalloc.h
kmalloc.h [634 Bytes]
Downloaded 40 times
File comment: kmalloc.c
kmalloc.c [3.2 KiB]
Downloaded 34 times
Top
 Profile  
 
 Post subject:
PostPosted: Sat Dec 09, 2006 7:00 pm 
Offline
Member
Member

Joined: Sat Nov 18, 2006 9:11 am
Posts: 571
I had a manager done before, but I lost the sources, I am working on a new version and the benchmark somewhat together since it will be dependant on each other. I think I have most of my specifics worked, only a few things my allocator will rely on.

A.) The process' memory space is linear (starting and ending values are given to manager), and is also passed the page size.
B.) The kernel has a function to mark a page in the process' memory space as useable.

Theseare the only things relied on by my manager, it will allocate space for itself when it's initialize function is called, as well as create a list (a single entry actually) of all available memory. When you allocate a large chunk it will ask for more memory, and split the list into used/unused. If you allocate a single byte of memory, it will allocate a page, store info in the list of free memory about this page, and what the granularity of it is (byte, word, dword, qword, 16-bytes, whatever 'small' size it may be). This way, if our app asks for another byte, it will set the appropriate bit, and return a pointer to the next free byte. Testing will determine what seems necessary, like do I really need a byte allocator, or would a size of 2 or 4 be sufficient, especially for things like alignment, testing will tell, but that's a bit far off right now. Anyways, I'm still working out a few more specifics, but I will be sure to share code once complete, so stay tuned :).


Top
 Profile  
 
 Post subject:
PostPosted: Mon Dec 11, 2006 5:15 am 
Offline
Member
Member

Joined: Sat Nov 18, 2006 9:11 am
Posts: 571
With the kbrk method, what are the chances of a process ever un-allocating it's memory? Not very likely right? One of the things i'm going to try to do with my method is to give back ram to the system once it's no longer used. With kbrk you can't really give it back, I mean, I guess you can set the page back to virtual again, and free the physical memory associated with it, which requires a good amount of kernel specifics to do, but would work pretty good. I figured asking a kernel for a length of memory available to the virtual process, for a function to mark a virtual page as available, and then mark one as unavailable (free) wasn't really asking a whole lot, and will make giving back memory that is no longer used much simpler, something about that kbrk just doesn't fit well with me, got some sort of programmers block against it, lol.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 64 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group