http://sourceforge.net/projects/x86-32-paging/files/
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.
Code: Select all
;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)
;OPCODE__CPU_x86_32_remap_physical_page_address (can be left unused)
;OPCODE__CPU_x86_32_map_physical_page_address_for_malloc_system__page_disabled
;OPCODE__CPU_x86_32_map_physical_pagedir_entry__page_disabled
;OPCODE__CPU_x86_32_addr2pagedirent
;OPCODE__CPU_x86_32_addr2pagetblent
;OPCODE__CPU_Disable_Default_Paging
;OPCODE__CPU_Enable_Default_Paging
;OPCODE__CPU_load_CR3_paging
;OPCODE__CPU_generate_4KB_empty_page_directory
;OPCODE__CPU_Read_Default_Paging
;OPCODE__CPU_Restore_Default_Paging
;OPCODE__CPU_x86_32__raw_paging__mark_page_AVL_value
;OPCODE__CPU_x86_32__raw_paging__mark_pages_AVL_value (can be unused)
;OPCODE__CPU_x86_32__raw_paging__get_distinct_AVL_value
;OPCODE__CPU__x86_32__find_biggest_free_virtual_block
;OPCODE__CPU__x86_32__find_04MB_free_virtual_block_page_disabled
;OPCODE__CPU_x86_32__raw_paging__read_page_AVL_value
;OPCODE__CPU_x86_32__free_empty_page_table_page_disabled
;OPCODE__CPU_x86_32_raw_paging_free_physical_16KB__AVL_block_page_disabled
;OPCODE__CPU_x86_32__pagetable_is_empty_page_disabled
;OPCODE__klibc32__malloc_PG_0
;OPCODE__klibc32__free_PG_0
;OPCODE__CPU_x86_32___virtual_4KB_page_is_not_free__page_disabled
;OPCODE__CPU_x86_32__get_AVL_block_size_page_disabled
;OPCODE__CPU_x86_32__check_free_virtual_16KB_blocks_after_AVL_allocation__page_disabled
;OPCODE__string__search_DWORD_aligned_DWORD_value
;OPCODE__CPU_x86_32_raw_paging_allocate_physical_4KB_page_disabled
;OPCODE__data_bitmap__free_physical_memory_16KB_cluster (can be unused)
;OPCODE__data_bitmap__get_16KB_physical_memory_cluster_state (can be unused)
;List of raw memory functions:
;;
;OPCODE__detect_32bit_memory_by_pages (must be called before any memory allocation)
;kalloc_Append_Kernel_Pages
;List of raw binary data functions:
;;
;OPCODE__binary_data__find_first_free_WIDEWORD
;List of bitmap functions:
;;
;OPCODE__data_bitmap__get_free_bits_offsets
;OPCODE__data_bitmap_offset_to_4K_address
;OPCODE__data_bitmap__get_free_physical_memory_address
;OPCODE__data_bitmap__free_physical_memory_address
;OPCODE__data_bitmap__get_free_nibble_offsets
;OPCODE__data_bitmap__get_free_physical_memory_16KB_cluster
;OPCODE__data_bitmap__get_physical_4KB_memory_address_state
;List of Binary String Processing Functions:
;;
;OPCODE__string__search_DWORD_aligned_DWORD_value
;List of VGA card functions:
;;
;VGAVideo_CRTC_setTextCurPos
;List of string functions:
;;
;num2str
;List of mode 03h text functions:
;;
;console_scroll_update
;console_doCRLFeffect
;console_kprint_visible
;console_kprint_uint32_16
;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
;List of library functions:
;;
malloc
calloc
realloc (expand only right after the end of the previous allocation)
free
Elements that Don't Need to Turn Off Paging
- Converting a virtual address into a byte offset into a page directory entry.
- Converting a virtual address into a byte offset into a page table entry.
- Converting the passed array index into the byte offset of the specified CR3 array index (to get the actual specified page table base address|possible flags) since it is mapped inside the kernel unlike page directories and page tables.
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 OPCODE__CPU_x86_32_raw_paging_allocate_physical_4KB_page, which is the function that maps a physical page to a virtual page address.
Example of identity-mapping Megabyte number 100:
Code: Select all
;Inputs:
; 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)
;
;
;Outputs:
; 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 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.
FINAL CONCLUSION
Learning paging is just about practicing malloc, thinking that paging is just an optimized hardware array to divide time and space, and we must manage it from the point of view of simply allocating and deallocating, also some mechanism of resizing, be it by leaving enough space between blocks or by defragmenting transparently in some way.
malloc/realloc/free are the starting end result. We can spend as much time as we want practicing those functions and their implementation. There is an infinite number of paging tricks we can add to our program depending on the primitives we want for a given software.
In the end we can rewrite a kernel version that only calls malloc, etc., instead of lower-level functions, for a better-separated code.
