OSDev.org

The Place to Start for Operating System Developers
It is currently Sun Jun 25, 2017 1:00 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: Questions about Memory Allocation
PostPosted: Wed Jul 23, 2003 1:29 pm 
Here is Pype.Clicker's simple malloc (which I am going to improve to incorporate first fit):

Code:
void* free; //<- initialize this with a block of free size obtained by any
void* end_of_free_mem;  // detection technique

void* bottom_up_alloc(int size) {
    void *ret=NULL;
    if (free+size<end_of_free_mem) {
        ret=free;
        free+=size;
    }
    return ret;
}


I have the number of RAM in bytes detected by direct probing. Block of free size? That would be 256 MB on my PC (number of RAM)? How do I translate that into an address? And I have no clue where my kernel is or how big it is... I don't want to allocate over top of it. Should I just start at the first 1 MB for good measure?
How do I know which address is the one where the first MB is?

Basicly I need to know how to translate between bytes and addresses.


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Wed Jul 23, 2003 2:15 pm 
When you compile your kernel you could define a couple of bytes, or a couple of words even, like a boot signature scheme determines a valid bootsector, and stick it at the very end of your compiled kernel image. Start at address 0x00000000 and scan up, looking for that signature, counting from the start of your kernel. Increment counter at each byte, store somewhere how big your kernel is. Skip over BIOS/ROM areas at 640K, up to 1MB, which is address 0xFFFFF, click over at 0x100000 (XXX?) and that's the first byte over 1MB (I think) with which you can begin to allocate memory from. (Assuming your kernel is occupying all memory below 640K).

Are you using paging in your kernel? If so, you have all memory mapped into pages and you need a different algorithm to Pype.Clicker's, and it will need to allocate PAGE_SIZE chunks, usually 4KB in Intel arch systems. You can set the page size you want that is allowed by the Intel architecture. A process may like to ask for X bytes, and you can determine the number of free pages of memory the process will be allocated.

If no paging, e.g. segments, um, you can use a simple algorithm like Pype.Clicker's, that should work fine. You keep a list of free blocks of memory, allocate from there, stick the list of allocated blocks in an allocated memory list, and when the process exits, add the allocated blocks of that exited process back to the list of free blocks.

Let's say you aren't using paging, and simply setup a linked list with each node representing a block of say 4KB. Those in the list are allocated, and the list can be sorted, so the last block in the list plus one is your first block of free memory, do some sanity checks with the last 4KB block based on how much memory is in the system, add it to the list of allocated blocks, and return the pointer to the requesting process, and ... done. Well, that's a rather crude way of doing it. If you aren't using paging then those pointers are physical addresses. (XXX?)

Experienced kernel devers, can you correct any mistakes above?

These are some thoughts off the top of my head to hopefully get you thinking about possible ways to do this... have fun :D


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Wed Jul 23, 2003 2:42 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
both your kernel start and stop can be defined by extra symbols (like kernel_start and kernel_end) in your linker script. I don't use it personally (because the loader tells me), but many people do.
Just have your memory-manager reference those symbols and the linker will fill the values nicely. The "signature" approach may lead to strange results as you cannot exclude that the signature will appear within the binary code, for instance (until you check your binary file and make sure the signature is never in it ...)

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Wed Jul 23, 2003 2:43 pm 
James Buchanan wrote:
When you compile your kernel you could define a couple of bytes, or a couple of words even, like a boot signature scheme determines a valid bootsector, and stick it at the very end of your compiled kernel image. Start at address 0x00000000 and scan up, looking for that signature, counting from the start of your kernel.


There's a much better way than this. When linking your kernel together, use a linker script. The linker script allows you to define veriables that are exported into your kernel, so if you want to know where the end of your kernel is, you can export a symbol after the last section. For example, a simple loader script might be:

Code:
SECTIONS
{
    __start = .;
    .text 0x100000
    {
/* kernel code */
   *(.text)
    }
    .data
    {
/* kernel data */
   *(.data)
    }
    .bss
    {
/* kernel BSS */
   *(.bss)
   *(COMMON)
    }
    __end = .;
}


In this example, the symbols __start and __end (which you can declare as an extern in your code) will contain the addresses of the beginning and end of your kernel, respectively. This way you won't waste time looking for a signature.

You can safely assume that anything past the end of your kernel is available when your kernel starts. So if I understand correctly what you were looking for, the chunk of memory from __end to the end of your memory is your initial free block.


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Wed Jul 23, 2003 2:45 pm 
Pype beat me to it by about 1 minute :P That's cause I was looking up an example... ;)


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Wed Jul 23, 2003 7:03 pm 
So how do I know where memory ends based on knowing that the user has 256 MB of RAM?


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Wed Jul 23, 2003 11:37 pm 
Actually, it's not safe to assume that the memory is continuous.
There might be holes, especially when there is a lot of memory in the system.

In any case, the easiest way is to ask BIOS to tell you where the free RAM is, which is easiest to do by booting with GRUB, since it can get it for you. It handles problems like finding out which BIOS call to use and such.

If you don't want to use GRUB, you might still want to get the stuff before going to pmode though. GRUB source might be a good place to see how it's done. One other place to look would be Linux source.
Old versions probed the memory, but modern kernels just get the BIOS map.

I actually decided to go straight to "virtual memory", since it seemed easier for me, since on top of that I have a malloc-library that depends on a single system call morecore(). The morecore basicly works the way of your bottom_up_alloc, only in continuous kernel heap that it can try to extend by calling vm_enlarge_kheap() which maps more pages there, getting those pages from a page allocator that basicly works just like morecore, only it deals with the
BIOS map, and returns 4k pages (and keeps a free-list)


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Thu Jul 24, 2003 10:33 am 
Well then what should I do? :( I really wish I understood some of this paging info, but I guess age 14 is too young for writing an OS.


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Thu Jul 24, 2003 11:32 am 
I don't think you're ever too young to start...just expect to get very frustrated and completely lost sometimes.

When I was a lot younger I always wanted to write my own operating system. I wrote qbasic shells on top of dos and a lot of other stuff, but I never felt I understood enough about hardware and theory to write an actual operating system.

Instead I decided to focus on learning as much as i could about good programming technique and about how other operating systems work, pouring over code until i understood what it was doing and, i think more importantly, why it was doing it.

So don't give up. If you really want it you'll learn eventually. Just don't get frustrated if it doesn't come easily...


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Thu Jul 24, 2003 2:50 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
mystran wrote:
Actually, it's not safe to assume that the memory is continuous.
There might be holes, especially when there is a lot of memory in the system.


hum, except for the 'ROM & VRAM' hole between 0xA0000 and 0x100000, are there any other 'holes' ? from what i've learned from PCI bus, the PCI devices get mapped in memory where you tell the to map to ... and ususally, this is from 0xffff0000 ... so ?

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Thu Jul 24, 2003 11:52 pm 
Ok, I might be a little paranoid here, I admit, but one such hole is at 15-16MB in some cases for OS/2 support (usually a BIOS option)..

This can be skipped of course, but then there might be some cases where BIOS maps a PCI/VLB card (old VGA cards mostly) to below the top of memory if you have a lot of RAM (some older cards are hardcoded to some address).

Cirrus Logic cards are one example, some low places they might want to be are 32MB, 64MB (VLB), then some ET4000 PCI cards want to map at little below 1GB I think, etc.

I also remember some older systems where touching some areas in memory could cause the system to reboot. Friend used to have one. Indeed, IIRC BIOS did report usable RAM correctly, but probing it would never work.

Ok, now, I'm sorry if I caused confusion, but just wanted to mention
that this might actually happen, especially when legacy hardware is involved.


Top
  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Fri Jul 25, 2003 1:01 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
hmm ... i would be rather interrested if you could drop a link to that BIOS memory mapping function, especially if it is not vendor-dependent ...

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Questions about Memory Allocation
PostPosted: Fri Jul 25, 2003 2:34 am 
So, I'm starting to feel like I've confused something myself.. I mean, AFAIK, the main method both GRUB and Linux use these days is INT 0x15, AX=0xe820 which is documented on this very site at http://www.mega-tokyo.com/os/os-faq-memory.html#determine_memory_bios
falling back to the older BIOS calls and/or probing when it's not available..

Now to be exact, the memory map GRUB returns actually is actually constructed of several pieces of information, including things like EISA memory map (int 0x15, ax=0xe801). This assuming I have understood correctly,
given the nature of GRUB source, that is.

Anyhow, my main point was merely to say that there are strange configurations, and GRUB has already been tested to work with most of them (if not all), which makes kernel
development a little easier, at least in the beginning.

If you want to do it yourself, I'd suggest looking at Linux source, arch/i386/kernel/setup.c and navigating from there. It's far easier to read than GRUB source..


Top
  
 
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: Google [Bot], Yahoo [Bot] and 11 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