Let’s make your own operating system (#week_7_Virtual_Memory_and_Paging)
Greetings, Friends! This is the seventh week of my article series about creating my own operating system as a test. If you’ve read any of my earlier articles in this series, I believe it will help you grasp this section.
In last week , we looked at how to establish a user mode that, unlike kernel mode, allows us to run user programs. you can go through my last week article by this link. In this article, we are going to learn about how we can implement virtual memory and paging to our operating system.
Ok then lets go,
What Is Virtual Memory? How Does It Work?
Virtual memory is an area of a computer system’s secondary memory storage space (such as a hard disk or solid state drive) which acts as if it were a part of the system’s RAM or primary memory.
Ideally, the data needed to run applications is stored in RAM, where they can be accessed quickly by the CPU. But when large applications are being run, or when many applications are running at once, the system’s RAM may become full.
To get around this problem, some data stored in RAM that is not actively being used can be temporarily moved to virtual memory (which is physically located on a hard drive or other storage device). This frees up space in RAM, which can then be used to accommodate data which the system needs to access imminently.
By swapping data between RAM and virtual memory when it is not needed and back from virtual memory to RAM when it is needed, a system can continue to work smoothly with far less physical RAM than it would otherwise require.
Virtual memory enables a system to run larger applications or run more applications at the same time without running out of RAM. Specifically, the system can operate as if its total RAM resources were equal to the amount of physical RAM, plus the amount of virtual RAM.
Why is There a Need for Virtual Memory?
Virtual memory was developed when physical RAM was very expensive, and RAM is still more expensive per Gigabyte than storage media such as hard disks and solid state drives. For that reason it is much less costly to use a combination of physical RAM and virtual memory than to equip a computer system with more RAM.
Since using virtual memory (or increasing virtual memory) has no extra financial cost (because it uses existing storage space) it offers a way for a computer to use more memory than is physically available on the system.
paging
Paging is a different way of accessing physical memory. Instead of memory being divided into segments it is divided into pages and frames. Frame is a block of physical memory of a specific size (e.g. 4Kb) while page is a block of virtual memory of the same size. Pages are same size as frames. In this mode program does not access memory using physical address. Instead it virtual memory addresses are used. Those virtual addresses are translated into physical addresses by CPU. This is a very expensive process compared to accessing memory directly and almost all CPUs have additional circuitry to help with that. That circuitry is called MMU or Memory Management Unit.
Following image illustrates memory translation process. Keep in mind that the image is simplified a lot and does not represent exactly what happens in a CPU. It does however illustrate basic concepts that we will build upon when we will be setting up paging.
For a CPU to translate a virtual address 0x5006 into a physical address the CPU first takes a prefix and looks up that prefix in its “page table” and finds what physical address is associated with that prefix. For now you can think of page table a special place in CPU. In our case physical address associated with page table entry 0x500 is 0x0011. CPU then takes that address (0x011) and adds the last part of the address (0x6). 0x0010 + 0x6 = 0x0016. And that’s how CPU translates virtual address 0x5006 to physical address 0x0016.
This approach can be extended to multi-level page tables:
In the above image first two bytes are used as index into “Page directory”. The following byte is used as an index into “Page table” and the last byte is offset within memory page.
x86 processors normally use 3 or 4 level paging with most recent ones being able to use even 5 level paging system.
The Paging Process
A page table stores the definition of each page. When an active process requests data, the MMU retrieves corresponding pages into frames located in physical memory for faster processing. The process is called paging.
The MMU uses page tables to translate virtual addresses to physical ones. Each table entry indicates where a page is located: in RAM or on disk as virtual memory. Tables may have a single or multi-level page table such as different tables for applications and segments.
However, constant table lookups can slow down the MMU. A memory cache called the Translation Lookaside Buffer (TLB) stores recent translations of virtual to physical addresses for rapid retrieval. Many systems have multiple TLBs, which may reside at different locations, including between the CPU and RAM, or between multiple page table levels.
Different frame sizes are available for data sets with larger or smaller pages and matching-sized frames. 4KB to 2MB are common sizes, and GB-sized frames are available in high-performance servers.
An issue called hidden fragmentation used to be a problem in older Windows deployments (95, 98, and Me). The problem was internal (or hidden) fragmentation. Unlike the serious external fragmentation of segmenting, internal fragmentation occurred if every frame is not the exact size of the page size. However, this is not an issue in modern Windows OS.
Paging on x86_64
The x86_64 architecture uses a 4-level page table and a page size of 4KiB. Each page table, independent of the level, has a fixed size of 512 entries. Each entry has a size of 8 bytes, so each table is 512 * 8B = 4KiB large and thus fits exactly into one page.
The page table index for level is derived directly from the virtual address:
We see that each table index consists of 9 bits, which makes sense because each table has 2⁹ = 512 entries. The lowest 12 bits are the offset in the 4KiB page (2¹² bytes = 4KiB). Bits 48 to 64 are discarded, which means that x86_64 is not really 64-bit since it only supports 48-bit addresses.
Even though bits 48 to 64 are discarded, they can’t be set to arbitrary values. Instead all bits in this range have to be copies of bit 47 in order to keep addresses unique and allow future extensions like the 5-level page table. This is called sign-extension because it’s very similar to the sign extension in two’s complement. When an address is not correctly sign-extended, the CPU throws an exception.
It’s worth noting that the recent “Ice Lake” Intel CPUs optionally support 5-level page tables to extends virtual addresses from 48-bit to 57-bit. Given that optimizing our kernel for a specific CPU does not make sense at this stage.
Identity and Enabling Paging
The least complex sort of paging is the point at which we map each virtual location onto a similar actual location, called personality paging. This should be possible to incorporate time by making a page catalog where every passage focuses on its comparing 4 MB outline. In NASM this should be possible with macros and orders (%rep, times, and dd). It can obviously additionally be done at showtime by utilizing normal get-together code directions.
Paging is empowered by first composing the location of a page registry to cr3 and afterward setting bit 31 (the PG “paging-empower” bit) of cr0 to 1. To utilize 4 MB pages, set the PSE bit (Page Size Extensions, bit 4) of cr4. The accompanying get together code shows a model:
; eax has the address of the page directory
mov cr3, eax mov ebx, cr4 ; read current cr4
or ebx, 0x00000010 ; set PSE
mov cr4, ebx ; update cr4 mov ebx, cr0 ; read current cr0
or ebx, 0x80000000 ; set PG
mov cr0, ebx ; update cr0 ; now paging is enabled
Note that all locations inside the page index, page tables, and in cr3 should be actual addresses to the designs, never virtual. This will be more significant in later areas where we progressively update the paging structures (see the part “Client Mode”).
The guidance that is helpful when refreshing a PDT or PT is invlpg. It discredits the Translation Lookaside Buffer (TLB) section for a virtual location. The TLB is a reserve for deciphered addresses, planning actual addresses relating to virtual addresses. This is possibly required while changing a PDE or PTE that was recently planned to something different. In the event that the PDE or PTE had recently been set apart as not present (bit 0 was set to 0), executing invlpg is pointless. Changing the worth of cr3 will make all sections in the TLB be negated.
; invalidate any TLB references to virtual address 0
invlpg [0]This section will describe how paging affects the OS kernel. We encourage you to run your OS using identity paging before trying to implement a more advanced paging setup since it can be hard to debug a malfunctioning page table that is set up via assembly code.
On the off chance that the bit is put toward the start of the virtual location space — that is, the virtual location space (0x00000000, “size of bit”) guides to the area of the piece in memory — there will be issues while connecting the client mode measure code. Typically, during connecting, the linker accepts that the code will be stacked into the memory position 0x00000000. Consequently, when settling supreme references, 0x00000000 will be the base location for ascertaining the specific position. Be that as it may if the portion is planned onto the virtual location space (0x00000000, “size of part”), the client mode measure can’t be stacked at virtual location 0x00000000 — it should be set elsewhere. In this manner, the suspicion from the linker that the client mode measure is stacked into memory at position 0x00000000 isn’t right. This can be revised by utilizing a linker script that advises the linker to expect an alternate beginning location, yet that is an extremely lumbering answer for the clients of the working framework.
This likewise expects that we need the piece to be important for the client mode cycle’s location space. As we will see later, this is a pleasant element, since during framework calls we don’t need to change any paging constructions to gain admittance to the bit’s code and information. The portion pages will obviously require advantage level 0 for access, to forestall a client cycle from perusing or composing part memory.
Then you’ll want to figure out how to enable paging. Paging is enabled by changing bit 31 of cr0 to 1 and then putting the URL of a page directory to cr3. The “paging enable.s” file is shown in the code below. Then you’ll want to figure out how to enable paging. Paging is enabled by changing bit 31 of cr0 to 1 and then putting the URL of a page directory to cr3. The “paging enable.s” file is shown in the code below.
To implement paging, we must first construct the “paging.h” and “paging.c” files, as shown below.
Virtual Memory Through Paging
There will be difficulties connecting the client mode measure code if the bit is put toward the start of the virtual location space, that is, the virtual location space (0x00000000, “size of bit”) means the situation of the piece in memory. The piece ought to preferably be situated at an exceptionally high virtual memory address, like 0xC0000000 (3 GB). The client mode measure is probably not going to be 3 GB in size, which is the solitary way it might now cause a bit struggle. A higher-half piece is one that utilizes virtual addresses in the scope of 3 GB and up. Most importantly, it is smarter to put the portion at 0xC0100000 than 0xC0000000, since this makes it conceivable to plan.
Paging makes it conceivable to complete two things that are gainful to virtual memory. First off, it empowers fine-grained memory access control. Pages can be set apart as perused just, read-compose, solely for PL0, etc. Second, it gives the presence of a ceaseless memory. Memory can be gotten to as though it were touching by client mode measures and the portion, and the coterminous memory can be reached out without the need to move information around in memory. We can likewise permit the client mode programs admittance to all memory under 3 GB, yet except if they really use it, we don’t need to dole out page edges to the pages.
Thank you for reading…
