Code: Select all
VMMDIR vmm_CreateDirectory()
{
VMMDIR *dir = pmm_Alloc(1);
for(uint32_t x = 0; x < 1024; ++x)
{
dir[x] = 0;
}
return dir;
}
A important part is still missing and this known by the name of
Identity Mapping, which means that when allocating special pages such as a
Page Directory or
Page Table they have a virtual address that is identical to their physical address in RAM.
The problem with not doing a
Identity Mapping for these special pages is such that, take for instance:
VMMDIR g_k_dir = vmm_CreateDirectory();
vmm_Map(g_k_dir, KERNEL_OFFSET, KERNEL_OFFSET, KERNEL_SIZE/4096);
vmm_Map(g_k_dir, KERNEL_STACK_OFFSET, KERNEL_STACK_OFFSET, KERNEL_STACK_SIZE/4096);
vmm_On(g_k_dir);
Alright after doing this the kernel is running happily using virtual memory, no problem right? If so then let us try to map our
VGA memory after activiating virtual memory.
vmm_Map(g_k_dir, 0xb8000, 0xb8000, 1);
It crashes... Why? We never mapped the directory or tables into our address space. It would seem obvious to just make a call such as:
vmm_Map(g_k_dir, (uintptr_t)g_k_dir, (uintptr_t)g_k_dir, 1);
This is great, now it crashes again because it allocated a table using physical memory but did not map it to the virtual memory we are running in. We need a automated way to identity map these special pages used for
Page Directories and
Page Tables.
The problem with identity mapping is that the exact same physical page address may not be free in every virtual space (multiple directories). The only way to do this dynamically is to force swap pages, or statically is reserve chunks/regions of memory for this special purpose (which I find very cumbersome). I am a flexibility freak I guess!
The idea is to store physical memory in a tree structure exactly like the
Page Directories and
Page Tables. We can make some utility functions to unify this abstract data structure between the PMM and VMM.
Utility Functions For The Abstract Tree
typedef uint32_t* MTREE;
MTREE mtree_Create(uintptr_t page);
uintptr_t mtree_Set(MTREE allocTree, MTREE tree, uintptr_t page, uint32_t value, uint32_t special);
uintptr_t __mtree_Set(uintptr_t *__freePage, MTREE tree, uintptr_t page, uint32_t value, uint32_t special);
uintptr_t mtree_Find(MTREE tree, uint32_t mask, uint32_t value, uint32_t rng_offset, uint32_t rng_stop, uintptr_t count);
uint32_t mtree_Get(MTREE tree, uintptr_t page);
Code: Select all
MTREE mtree_Create(uintptr_t page)
{
MTREE tree = (MTREE)page;
for(uint32_t x = 0; x < 1024; ++x)
{
tree[x] = 0;
}
return tree;
}
This will create a new empty tree structure using one page.
Code: Select all
uint32_t mtree_Get(MTREE tree, uintptr_t page)
{
if(tree[page>>22] == 0)
{
return 0;
}
return ((uint32_t*)tree[page>>22])[page<<10>>22];
}
This will access a entry in the tree using page as the address in the tree.
Code: Select all
uintptr_t __mtree_Set(uintptr_t *__freePage, MTREE tree, uintptr_t page, uint32_t value, uint32_t special)
{
if(tree[page>>22] == 0)
{
ASSERT(__freePage == 0);
tree[page>>22] = __freePage | special;
__freePage = 0;
}
((uint32_t*)tree[page>>22])[page<<10>>22] = value;
if(__freePage == 0)
{
return tree[page>>22];
}
return 0;
}
This will set a entry when standard memory management exists, by using a pointer to a value containing the address of one free page. This function will never need more than one free page per call, in some cases it may not even use the free page provided.
Code: Select all
uintptr_t mtree_Find(MTREE tree, uint32_t mask, uint32_t value, uint32_t rng_offset, uint32_t rng_stop, uintptr_t count)
{
uintptr_t found = 0, foundStart = 0;
for(uint32_t x = rng_offset; x < rng_stop; x += (1<<22))
{
if((tree[x] & mask) == value)
{
if(found == 0)
{
foundStart = x;
}
found += 1024;
if(found > count)
{
return (uintptr_t)foundStart;
}
}else{
for(; (x<<10>>22) != 0; x += 0x1000)
{
if((((uint32_t*)tree[x>>22])[x<<10>>22] & mask) == value)
{
if(found == 0)
{
foundStart = x;
}
++found;
if(found > count)
{
return (uintptr_t)foundStart;
}
}else{
found = 0;
foundStart = 0;
}
}
}
}
return UINTPTR_MAX;
}
This will search the tree for a certain value that when masked equals it.
Code: Select all
uintptr_t mtree_Set(MTREE allocTree, MTREE tree, uintptr_t page, uint32_t value, uint32_t special)
{
uintptr_t freePage = 0;
if(tree[page>>22] == 0)
{
freePage = mtree_Find(allocTree, UINT32_MAX, MM_STATE_FREE, 0, UINT32_MAX, 1);
ASSERT(freePage == 0);
tree[page>>22] = freePage | special;
freePage = 0;
}
((uint32_t*)tree[page>>22])[page<<10>>22] = value;
if(__freePage != 0)
{
return (uintptr_t)tree[page>>22];
}
return 0;
}
This performs the exact same function as the special
__mtree_Set, except it uses a tree to find free pages to create tables when needed.
The New pmm_Free Using The Tree
Code: Select all
MTREE g_k_pmm_tree = 0;
void pmm_Free(uintptr_t page, uintptr_t count)
{
static uintptr_t slack = 0;
uintptr_t __freePage = 0;
if(g_k_pmm_tree == 0)
{
if(slack == 0)
{
/// if we have a slack page from the last call then use it here.
g_k_pmm_tree = mtree_Create(page);
_freePage = page + 0x1000;
page += 0x2000;
count -= 2;
}else{
g_k_pmm_tree = mtree_Create(slack);
slack = 0;
_freePage = page + 0x1000;
page += 0x1000;
count -= 1;
}
__mtree_Set(&__freePage, g_k_pmm_tree, (uintptr_t)g_k_pmm_tree, MM_OWNER_PMM | MM_STATE_USED);
}
if(count == 1)
{
slack = page;
return;
}
if(slack == 0)
{
_freePage = page;
page += 0x1000;
--count;
}else{
_freePage = slack;
slack = 0;
}
for(uint32_t x = 0; x < count; ++x)
{
if(__freePage == 0)
{
if((x+1) >= count)
{
slack = page + (0x1000 * x);
return;
}
__freePage = page + (0x1000 * x);
++x;
}
__mtree_Set(&__freePage, g_k_pmm_tree, page + (0x1000 * x), MM_OWNER_NONE | MM_STATE_FREE);
}
return;
}
This is our
pmm_free function written to use the abstract data structure
mtree, which provides us with a dynamic way to account for memory using a tree and unifying the abstract data structure between our
pmm_* and
vmm_* which saves overhead, work writting redundant code, and the possibility of introducing bugs through two seperate implementations of the same abstract data structure.
The Ability To Make Identity Pages Dynamically
typedef MTREE VMMDIR;
typedef uint32_t VMMREGION;
#define REGION_4MBOFFSET(x) (x>>16)
#define REGION_4MBSTOP(x) (x&0xFFFF)
VMMDIR vmm_Create();
uintptr_t vmm_AllocIdentity(VMMDIR dir, VMMREGION region);
uintptr_t vmm_Alloc(VMMDIR dir, VMMREGION region, uintptr_t count);
uintptr_t vmm_Alloc(VMMDIR dir, VMMREGION region, uintptr_t page, uintptr_t count);
void vmm_Map(VMMDIR dir, uint8_t region, uintptr_t phy, uintptr_t virt, uintptr_t count, uint32_t flags);
void vmm_Free(uintptr_t page, uintptr_t count);
Code: Select all
extern MTREE g_k_pmm_tree;
uintptr_t vmmAllocIdentity(VMMDIR dir, VMMREGION region)
{
uintptr_t soffs = REGION_4MBOFFSET(region);
uintptr_t phy = UINTPTR_MAX;
while(phy == UINTPTR_MAX)
{
phy = mtree_Find(g_k_pmm_tree, UINT32_MAX, MM_STATE_FREE, soffs, REGION_4MBSTOP(region), 1);
soffs += 0x1000;
if(phy == UINTPTR_MAX)
{
// we need to force swap a page.
soffs = REGION_4MBOFFSET(region);
while(phy == UINTPTR_MAX)
{
/// find a page that has not been marked as: NOFORCESWAP or IDENTITY.
phy = mtree_Find(g_k_pmm_tree, MM_NOFORCESWAP | MM_IDENTITY, 0, soffs, REGION_4MBSTOP(region), 1);
if(phy == UINTPTR_MAX)
{
/// There is no avalible memory in the system to force swap, return zero - calling operation should fail with our of memory error.
return UINTPTR_MAX;
}
// ** You might store a process ID that has this page allocated. **
// ** Shared memory might always set MM_NOFORCESWAP and leave this field zero. **
uint32_t processID = (mtree_Get(g_k_pmm_tree, phy)>>16);
// ** Use the processID to access that process' page directory and remap this page somewhere else. **
uintptr_t somewhereElse = pmm_Alloc();
.... blah ... blah ... blah ...
...............................
phy = UINTPTR_MAX;
soffs += 0x1000;
}
}
// check if page is viable for usage as a identity page.
phy = UINTPTR_MAX;
}
}
void vmm_Map(VMMDIR dir, uintptr_t phy, uintptr_t virt, uintptr_t count, uint32_t flags)
{
}
Ok.. I just got really tired of doing this.. and realizing no one is going to read or understand all of this. ^_^
