The Place to Start for Operating System Developers
It is currently Tue Oct 15, 2019 11:19 am

All times are UTC - 6 hours

Post new topic Reply to topic  [ 2 posts ] 
Author Message
 Post subject: x86 32-bit paging management
PostPosted: Sat Sep 14, 2019 11:51 am 
User avatar

Joined: Tue Mar 06, 2007 11:17 am
Posts: 1162
I've working in paging management, and it seems that the easiest way to achieve it is to keep a physical pages bitmap unique to the whole system.

Look at the end of the post for an attached ZIP/.asm file that sums up the easiest way I've found to map a given physical page to a given virtual page, from detecting memory manually to mapping the page.
;List of paging functions:
;OPCODE__CPU_x86_32_raw_paging_allocate_physical_4KB_page      (should be capable to initialize our kernel page directory all by itself)

;List of raw memory functions:
;OPCODE__detect_32bit_memory_by_pages    (must be called before any memory allocation)

;List of raw binary data functions:

;List of bitmap functions:

;List of VGA card functions:

;List of string functions:

;List of mode 03h text functions:

;List of debug macros:
;printdbg_str_hexnum String_Name,"String to display: ",0,wideax   (last 2 parameters are string terminator and value to display)
;include_debugstr String_Name,"FunctionName"  (to mark function starts in assembled code)
%define isdbg 1       ;Set flag to 0 to disable producing debugging code

The steps are (you can see them at the end of the ZIP/.asm code):

- Detect available memory to the highest accessible address.
- Create/initialize the physical bitmap with size adapted to the installed RAM to the last page used by the kernel and the first MB.
- Initialize/enable kernel paging.
- Mark the first sequential physical page available for applications in a variable.
- Cache CR0 for being able to change/restore it while the system runs.
- At this point we can easily map new virtual pages.
- The CR3 value is taken into account for being able to modify any page directory, not just the current one.

I need functions to map manually or automatically any address, to unmap them via virtual pages or via the physical bitmap, to search for contiguous blocks of pages returning type, base address and size in pages (free, used, from the same block -for malloc/realloc/free- using the AVAIL field to relate contiguous ones), I need multitasking to test reusing addresses for applications separated from the kernel more than for switching simultaneous programs. Then I can implement malloc-like functions on top of physical and paging management functions for the rest of programs, that don't really need paging or dynamic memory management as much as a C/C++ compatible kernel.

No tutorial says how to manage things beyond the initial mapping for running with paging. Tutorials for other things show functions built step by step to reason how to implement each detail, but paging tutorials have never been specific on the basic set of functions, variables and tracking algorithms that make up the simplest implementation from which to expand as everyone sees fit.

In the above URL I've included a test kernel written in assembly with a function that is capable of mapping a specific virtual address to a specific physical address and set paging attribute bits. It is capable of reserving a new page if there isn't a page table entry for it. That seems to be the easiest thing to implement for managing paging. That's the most important function I've implemented along with the associated bitmap search, other paging and physical memory detection/reserving/freeing functions to make possible for it to work.

Look at the function called [big]OPCODE__CPU_x86_32_raw_paging_allocate_physical_4KB_page[/big], which is the function that maps a physical page to a virtual page address.

Example of identity-mapping Megabyte number 100:
;      WIDESI -- Index in the CR3 array 0 to N.
;      WIDEAX -- Privilege/type flags and target physical address.
;      WIDEDI -- Target virtual address (0 for identity mapping)
;       WIDEAX -- New virtual page address
mov widesi,0
mov wideax,(1048576*100)|(_FLAG_x86_32_pageDirectoryEntry_Bit0_Present_TRUE|_FLAG_x86_32_pageDirectoryEntry_Bit1_ReadWrite|_FLAG_x86_32_pageDirectoryEntry_Bit2_UserLevel)
mov widedi,1048576*100
call OPCODE__CPU_x86_32_raw_paging_allocate_physical_4KB_page

The opposite function (unmap via a given virtual address in a directory) should make things like freeing a page working as a fully empty page table with no exception to avoid low-level memory leaks easily. But in the end virtual spaces seem to be handled by virtual allocation data to structure the rest of operations.


The easiest is to keep all program allocations to clusters of 4 physical pages and 16 virtual pages (for the virtual ones, that can be partially allocated, not all of them valid of out of 4 page clusters). Think that for a new page directory you need at least 3 new pages (an actual data page, the page directory and a page table for a 4MB block), so if we don't keep things grouped in 4-page clusters the system is capable of reaching a point where it won't be able to allocate new page directories for a new process, and if we need it we will lock up without knowing fast enough if there's enough free RAM speeding up with clusters.

Also, malloc allocations in a directory are easier if kept with a distance of up to 16 Megabytes between allocated blocks to avoid fragmentation widely, to allow realloc() and free() without interfering too often with other blocks, unless a program uses many variables bigger than 16 Megabytes.

Also, the easiest is to keep paging structures unmapped, disable paging and interrupts for the shortest possible time to access them (just enough to ensure that we are coherently marking them as now reserved or free) and reenable to keep working. The physical page bitmap is mapped in kernel space, so searching it doesn't need to disable paging and it's one of the most time consuming operations anyway versus just setting up some paging structures (although we need to search for the AVAIL field for finding big blocks). It causes our address space to keep all addresses available as paging structures will now never interfere because they are unmapped instead of taking up space (doing so is dramatically easier than deciding how to map paging structures themselves and then actual code/data pages), although we'll need to disable paging for allocating/deallocating anything, but now this allocator becomes so simple that we don't need to rely on exceptions for allocating requested pages, we just allocate them when we want them.

Information of contiguous block types could be left to a very fast SQLite3 or manual DB2 database when we have access to disk and swap, to avoid disabling paging too much just to inspect which blocks are contiguous that could be implemented as a cache accelerator.

The question is: Is disabling/enabling paging comparable in speed to reloading CR3 when the cache is invalidated?


Another functions that are needed to manage pages are functions to automatically choose physical and virtual addresses, or force one of them (we already have a function to choose a specific physical/virtual pair meaning it forces them both and leaves searching appropriate addresses to external code). Functions to choose automatic addresses are the most important after having manual mapping functions because those are the ones that take care of where to place stuff without us (they are some of the most used most of the time for normal allocations).

Also functions to search free or reserved virtual and physical page blocks to choose for currently manual mapping functions aligned or not to the page cluster size, allocating virtual addresses apart up to 16 Megabytes and virtual clusters of 16 4KB pages to minimize fragmentation per program. The functions need to return the size in pages of a current/next page block so that we can then decide if it's big enough or not, to actually allocate/free. It will be necessary for malloc() and realloc(). We can use a given value of the AVAIL field to indicate whether the next/previous contiguous pages are part of the same block. We could probably use 2 or 3 different AVAIL values so that we can differentiate between 2 or 3 contiguous blocks (as long as those pages are actually valid, if not AVAIL and the other fields should be 0 at all times to make page entries to indicate a free NULL pointer, and paging structures can have an AVAIL value of 0 as they only need to be mapped or unmapped by the base kernel with single-page fragmentation). It seems to be the easiest way to keep track of the sizes of malloc blocks purely in hardware with zero extra space or additional structures/logic that could introduce unstability because of unnecessary complexity.


It's better to support at least very basic multitasking with a separate CR3 directory to provide resistance without system-wide lockups that we can stop with a hotkey or the like (a key to switch processes manually or to terminate the current one and return to the kernel), and also to make possible to reuse addresses.

The easiest is to employ the AVAIL field marked with all 1's to indicate which pages come from the system/kernel, and that cannot be deallocated from the physical page bitmap when freeing the secondary process memory for termination (free its own page tables but without unmarking kernel memory in the physical page bitmap).


As you can see, it seems that the whole physical/paging/malloc system can be done in hardware and a software bitmap if we figure out a way of making use of available paging bit fields and come up with a reasonable grouping of pages and middle-sized virtual address ranges.

Things like the physical page bitmap could be reallocated to a higher address if it gets in the way of other necessary addresses, for example if it goes beyond the first 4MB of the virtual address space (if programs start there and we need to remap the whole base kernel into the program's space). There is a function that can reallocate the virtual address of a physical page to any other existing virtual address, and other that can do the same even if no page table currently exists (this one should always be used as part of the page manager automation).

But now minimum multitasking with separate CR3 needs to be implemented as a container, for any other function than manually mapping a specific physical page to a specific virtual one to make practical sense (for example to start testing how well malloc-style calls work in programs and how much we will improve against exceptions, how well we can allocate and free memory from separate processes).

Does it look OK to base malloc-like functions purely in the paging hardware with minimum or absolutely no other control data to keep track of the allocations for a given virtual address space? It seems like a practical application that needs such minimalization to effectively reuse addresses several times transparently and to base basic memory management functions only in the available CPU hardware for all tracking.

File comment: The code needed to map the page in a directory placed in a way that will assemble but that needs to be placed in a kernel to make use of it.
x86_32bit_paging_lib.zip [18.18 KiB]
Downloaded 7 times

_________________ (My OS compatible with DOS)

IP for hosts file (all domains): api.exe
 Post subject: Re: x86 32-bit paging management
PostPosted: Sun Sep 15, 2019 10:13 am 

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 1656
~ wrote:
- Detect available memory to the highest accessible address.

You assume memory will be in one continuous block. What happens if there are gaps?
You assume memory will be available. What happens if the firmware is already using it for things like ACPI and SMM?
You assume it's safe to probe addresses that aren't memory. What happens if you hit the memory-mapped registers for your motherboard's voltage controllers?

~ wrote:
Is disabling/enabling paging comparable in speed to reloading CR3 when the cache is invalidated?

Reloading CR3 is faster: it doesn't invalidate cached global pages.

For small updates to the page tables, INVLPG is fastest: it only invalidates the parts you want to invalidate.

You can't take advantage of these features (or newer ones like PCID) if you're disabling paging. Modern CPUs are designed for operating systems that never disable paging.

~ wrote:
Does it look OK to base malloc-like functions purely in the paging hardware with minimum or absolutely no other control data to keep track of the allocations for a given virtual address space?

That's fine, but in the future you might discover you need that extra control data.

Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 posts ] 

All times are UTC - 6 hours

Who is online

Users browsing this forum: Bing [Bot], Google [Bot], MSN [Bot] and 8 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