Velko made a good point that virtual space management and virtual memory management mean different things, but I may abuse the terminology here and there.
First, let's discuss what constitutes an allocation. Does it mean to provide actual access to to the physical frame or just to manage its allocation state? In user mode, the heap always returns a mapped address. But in kernel mode, the two concerns are usually kept separate. Physical frame allocation by default means to mark it as busy and nothing more. Let's say that you use a bitmap for tracking the state of physical memory. To serve an allocation means to find a cleared bit, to set it, and to return the index. Since the bitmap is a global entity of fixed size, it can be allocated at boot time and kept mapped in all processes, from process creation to process termination. No dynamic mapping is necessary.
If, like linux, you map the entire memory in one contiguous virtual address range, then the bit position returned by the physical allocator can be used to derive the page address in virtual memory. For kernel space servings, this concludes the entire allocation process. You wont need to map anything anywhere.
If you need to serve user space memory, or don't use the linux approach, you also need to find an address space range that is currently free. This involves other structures, such as prefix trees or self-balancing trees. Once you have such an address range, you need to map the physical frame you have allocated into a page somewhere in that range. If you use recursive (aka self-mapping) page tables, a technique to which Velko referred in his answer, you already have direct access to every page table for the process. This access is not dynamically controlled. It becomes automatically available at process creation and automatically reflects changes to the tables (assuming that you invalidate the TLB when making changes to the page directory), and doesn't cost additional table space in physical memory. But it doesn't guarantee that you will not end up in a location for which no page table is currently present. You may still have to allocate one more frame for creating the missing page table. The good news is that the physical allocator will not cause reentry into the mapping code, because it does not concern itself with providing access to the frames. Once the frame for the page table is allocated, the index returned from the physical allocator can be used to fill in the address in the page directory entry, thus making the table visible. You get to a point where a table entry has to be filled in with the address originally retrieved to serve the initial allocation, which will conclude the process.
If you don't use recursive page tables, to bottom out the recursion, you need to keep a few page tables mapped at all times, and dedicate them to bouncing other page tables into visibility. This may save some address space, but is not very performant, hence the relative popularity of the self-mapping approach.
Physical allocators don't have to use bitmaps, and neither does Linux nor Windows. They use free lists, which maintain one list link for each physical frame. The links are actually embedded in a slightly bigger record that also holds other frame related information, and the records are organized in array that is similarly allocated at boot and kept mapped at all times in every process. When a frame is served, the link is detached from the respective free list and can temporarily be used by the requestor. The owner gets to use the link however it chooses until they free the page. OSes usually keep there file caching state/pointer, sub-page allocation state/pointer, or page replacement queue links.
P.S. You can try to google self-mapping page tables or recursive page tables. This is not really an algorithm, but just a way to link the page tables back to themselves in a way that makes them visible in the space they describe. (Edit: To "themselves" is misspoken here, but its better that you read up a really thorough explanation.)
|