[CLOSED] Physical allocator and the heap.

[ExeTwezz]

Hi,

During the past few days I'm trying to understand one confusing problem.

From what I know, the physical allocator allocates physical pages ("frames"). Each frame is a block of 4 KB.
The virtual allocator allocates pages. The size of a page is 4 KB too.

Since amount of the physical address space often (in emulators) is not exactly 4 GB, it is logical to assume that it has less free pages than the virtual address space.

Also, the virtual allocator requests a physical page when it needs a page for a page directory or for a page table (if it is not the full list, please finish it). Here I'm confused:

User (actually a programmer) can map a virtual page to a used physical one (read the whole post). This may cause crash (e.g. the physical page may contain a page directory or page table, etc.).

As I guess, there should be a thing called heap and it needs to be in the physical address space. The heap itself is (again, as I guess) a big region of physical memory (e.g. 4 MB, or more, 128 MB?). It contains free and used physical pages. There should be a bitmap (or something else, doesn't matter for me now) for the heap. Is my imagine of the purpose of the heap true?

[iocoder]

Hi,

Since amount of the physical address space often (in emulators) is not exactly 4 GB, it is logical to assume that it has less free pages than the virtual address space.

Sure! Although every process has a separate 4GB virtual address space, most of the time only little megabytes (of the virtual address space of a given process) are mapped to actual physical pages. So it is very logical.

EDIT: BTW I assume you mean "RAM" not "physical address space". Physical address space is always 4GB in 32-bit systems. RAM is usually less than 4GB.

User (actually a programmer) can map a virtual page to a used physical one (read the whole post). This may cause crash (e.g. the physical page may contain a page directory or page table, etc.).

Actually it is the operating system that does the allocation & mapping. Not the programmer! the programmer just uses the ready-to-use malloc() library call or mmap() system call. When you use malloc(), a very simple OS will simply allocate free physical pages, then map them to virtual address space.

As I guess, there should be a thing called heap and it needs to be in the physical address space. The heap itself is (again, as I guess) a big region of physical memory (e.g. 4 MB, or more, 128 MB?). It contains free and used physical pages. There should be a bitmap (or something else, doesn't matter for me now) for the heap. Is my imagine of the purpose of the heap true?

The heap that I know is part of the virtual address space of a process and is used as a data area for dynamic allocations (it is managed by malloc() and free() library calls using a bitmap or whatever). Heap size increases everytime you reserve more space using malloc().

[ExeTwezz]

Hi,

EDIT: BTW I assume you mean "RAM" not "physical address space". Physical address space is always 4GB in 32-bit systems. RAM is usually less than 4GB.

That's it.

Actually it is the operating system that does the allocation & mapping. Not the programmer! the programmer just uses the ready-to-use malloc() library call or mmap() system call. When you use malloc(), a very simple OS will simply allocate free physical pages, then map them to virtual address space.

OK, I think you mean that programmer(s) of the OS needs to thoroughly design the kernel (I don't know why I didn't thought about this obvious answer for my question).

The heap that I know is part of the virtual address space of a process and is used as a data area for dynamic allocations (it is managed by malloc() and free() library calls using a bitmap or whatever). Heap size increases everytime you reserve more space using malloc().

Thank you!

Should I have a kernel version of malloc() (kmalloc())? And why shouldn't I just allocate the whole pages?

[iocoder]

Hi,

EDIT: BTW I assume you mean "RAM" not "physical address space". Physical address space is always 4GB in 32-bit systems. RAM is usually less than 4GB.

That's it.

Actually it is the operating system that does the allocation & mapping. Not the programmer! the programmer just uses the ready-to-use malloc() library call or mmap() system call. When you use malloc(), a very simple OS will simply allocate free physical pages, then map them to virtual address space.

OK, I think you mean that programmer(s) of the OS needs to thoroughly design the kernel (I don't know why I didn't thought about this obvious answer for my question).

The heap that I know is part of the virtual address space of a process and is used as a data area for dynamic allocations (it is managed by malloc() and free() library calls using a bitmap or whatever). Heap size increases everytime you reserve more space using malloc().

Thank you!

Should I have a kernel version of malloc() (kmalloc())? And why shouldn't I just allocate the whole pages?

Yes you should have it so that you can allocate memory for kernel structures. As an example, my kernel data space appears at the highest 1GB of the virtual address space (0xC0000000-0xFFFFFFFF), whenever I call kmalloc(), it looks for a free area in that 1GB space, then reserves it. A data structure is used to help kmalloc() decide where to allocate the required space.

And why shouldn't I just allocate the whole pages?

How? you still need something that tells you which virtual page is free, and that's why there is kmalloc()

[max]

What the heap is and how it is used depends on your kernel model.

For example in a higher-half microkernel: The kernel has it's own heap, located somewhere in the kernels area (the higher memory, starting for example at 0xC0000000). The kernels area is mapped to each existing address space. That is necessary because after the startup, the kernel only exists within system calls. Each process has it's own address space and also it's own heap.

When the kernel needs to allocate something, it uses it's global kernel heap - this one can be managed however it wants.

When a process wants to have heap space, it first needs to ask the kernel. This is usually done by an interface like sbrk/mmap. The simpler one, sbrk, can work for example like this:
- the kernel must for each process remember the heap start and the heap break (the end).
- a process is created; the kernel places it's heap at virtual 0xA0000000, ending at 0xA0000000 (heap is 0 bytes long now)
- now a program uses the userspace malloc implementation. malloc now detects that the requested memory doesn't fit in the current heap (it initially gets the heap break from the kernel by calling sbrk with 0) and therefore needs a way to move the heap break: this is where sbrk comes in.
- malloc calls sbrk with a value. the sbrk function now uses a system call to tell the kernel by how much it shall extend the process heap
- the kernel must now extend the heap by that value: for example, if sbrk was called with 0x2000, the heap is now expanded by that value by mapping physical pages into the virtual address space (appending them to the heap), so the process heap is now at virtual 0xA0000000 - 0xA0002000
- once this is done, sbrk returns with the previous value of the heap break: 0xA0000000. this tells malloc that the operation was successful
- now malloc has enough space in there to allocate something
Whenever the malloc implementation detects that there is not enough space on the heap, it uses sbrk to extend the heap. As this heap area is within the processes virtual address space, and each process has its own address space, they are safe from each other.

How? you still need something that tells you which virtual page is free, and that's why there is kmalloc()

No. What is usually known as kmalloc is just a kernel-space implementation that manages an area of memory within the kernel space that the kernel uses as its heap. Which virtual page is free must be stored once for the kernel space, and once for each process virtual address space (because they clearly dont all have the same free virt pages).

[ExeTwezz]

Thank you,

I've created this topic just because I couldn't find any info about what the heap is.

[iocoder]

How? you still need something that tells you which virtual page is free, and that's why there is kmalloc()

No. What is usually known as kmalloc is just a kernel-space implementation that manages an area of memory within the kernel space that the kernel uses as its heap. Which virtual page is free must be stored once for the kernel space, and once for each process virtual address space (because they clearly dont all have the same free virt pages).

Hi max,
I was talking about kernel virtual pages, not user pages. I meant there must be some structure that is used to describe the kernel memory space. And that's why we need kmalloc()

[max]

@ExeTweez obviously its not your decision if a topic is closed.

I was talking about kernel virtual pages, not user pages. I meant there must be some structure that is used to describe the kernel memory space. And that's why we need kmalloc()

Okay I just want to avoid misconceptions

[ExeTwezz]

@ExeTweez obviously its not your decision if a topic is closed.

Why? I've created this topic, so I can close it or delete. It's logical!