I've setup basic paging in my kernel, but theres a few things I dont understand (despite many hours of reading).
If an application requests 1 byte of memory through an allocator such as malloc(), would the allocator have to give the application the entire page, which is 4kb? Wouldnt this be a waste of memory?
Before I started using paging, I would setup a GDT entry for each new task (seperate entries for code and data). I would also setup GDT entries for the task's TSS. Would this change now that Im using paging, and how?
Memory
I have solved it like this...
You should have a page alloc that can allocate one free page and map it into the process address space.
then, you should have a malloc which uses this function. But this function should try to keep a list of allocated space. So that the malloc function divided the page into 4096 1 bytes if that what you program allocs...
cheers
Thomas
then, you should have a malloc which uses this function. But this function should try to keep a list of allocated space. So that the malloc function divided the page into 4096 1 bytes if that what you program allocs...
cheers
Thomas
Normally the memory allocator works from a pool of free pages - I.e. some contiguous block of free, usable memory. When a request for, say, 1 byte comes in, The allocator finds some free space of size
using some algorithm (usually best-fit with compacting to try and avoid memory holes). Here, header = some information that the allocator uses to keep track of that allocated piece of memory (when calling free(), the allocator looks at this header to work out sizes etc), request is the request size (e.g. 1 byte) and footer is some (optional) information the allocator puts afterwards (maybe error checking, or data for compacting). The allocator then returns the address of the hole it found + sizeof(header). That was a crappy explanation so here is some pseudocode...
Hopefully that answered your question -- allocators don't return a page per request, they allocate from a memory pool.
JamesM
Code: Select all
sizeof(header) + sizeof(request) + sizeof(footer)
Code: Select all
typedef struct
{
u32int size;
} header_t;
typedef struct
{
u32int magicNumber; // for error-checking, maybe
} footer_t;
void *malloc(u32int size)
{
// find a memory hole using some algorithm
u32int holeLocation = find_memory_hole( sizeof(header_t) + size + sizeof(footer_t));
// fill out the header/footer fields
header_t *pHeader = (header_t *) holeLocation;
footer_t *pFooter = (footer_t *) holeLocation+sizeof(header_t)+size;
pHeader->size = size;
pFooter->magic = MY_SUPER_MAGIC_NUMBER;
// return the address after the header, for the user to use as he wills.
return (void *)holeLocation+sizeof(header_t);
}
void free(void *p)
{
// here we use the header we allocated before to find out the size
// of the memory we are about to deallocate
header_t *pHeader = (header_t *) ((u32int)p - sizeof(header_t));
// we might also get the footer and error-check it for overflows.
footer_t *pFooter = (footer_t *) ((u32int)p + pHeader->size);
// et voila, we can deallocate.
deallocate_region((u32int) &pHeader /* region start location */, size);
}
JamesM
I was thinking that if I used 1 byte of a page I would mark the entire page as 'used' (stupid thought, now that I look at it).JamesM wrote: allocators don't return a page per request
Is this pool an area of memory set for use specifically by the allocator, or does the allocator search the entire area of user memory itself?JamesM wrote: they allocate from a memory pool.
Also, is it possible to declare segments (using the GDT, the GDT is what we use to declare segments, right?) after paging is enabled, and what is the max amount of segments allowed (I remember reading 8192 somewhere, but im not sure)?
Well thats not entirely true. There are two levels of allocations, page level and byte level(malloc). When malloc needs more memory to supply one of its requests it usually calls sbrk. sbrk maps more pages into the applications address space and returns a pointer to the start of those pages. Then malloc divides those pages up into used and free regions. The free regions can be used on subsequent calls to malloc to fulfill requests for more memory. sbrk usually works on a page granularity so yes an entire page is mapped in and marked as used if an application asks for 1 byte, unless there is enough space left in the free region.
So would I be right in saying that, if my allocator gives a block of memory to a task, so that it shares a page with another task, and the application tries to access that piece of memory the cpu would cause an interrupt? (im trying to figure out if a task's pages which were allocated at byte level are specific to a particular task or not)
The CPUs memory protection is mainly page based. There is no real easy way to provide byte level protection between processes or tasks. The only way to provide that level of protection would be to use segments in the LDT. I have yet to see an OS yet that provides more than page level protection. Most OSs will just allocate the full page to the application and use page level protection. Page level protection is accomplished by using a separate page directory for each task. Only that tasks particular pages are mapped in its page directory so there is no way that a task can access any other tasks pages (unless the tasks are sharing memory).pacman wrote:So would I be right in saying that, if my allocator gives a block of memory to a task, so that it shares a page with another task, and the application tries to access that piece of memory the cpu would cause an interrupt? (im trying to figure out if a task's pages which were allocated at byte level are specific to a particular task or not)
Oh well I thought I was correcting you but it turns out we were talking about two different things. I'm sorry if I seemed a little harsh. That should teach me to post at 12:30 in the morningJamesM wrote:@frank:
Sorry, I misread the OP's question - thought he was talking about a kernel memory allocator. All the same I'd point him to g.oswego.edu/dl/html/malloc.htm - thats the description page for Doug Lea's malloc, used in linux I believe. That should explain a lot.
JamesM