OSDev.org

The Place to Start for Operating System Developers
It is currently Fri Mar 29, 2024 3:49 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Kernel dynamic structs
PostPosted: Sun Sep 24, 2017 4:51 am 
Offline
Member
Member

Joined: Sun Mar 01, 2015 7:58 am
Posts: 51
Hello,

I have a misconception. I was thinking of implementing the buddy algorithm for physical memory allocator, but in theory the internal structures for buddy algorithm have dynamic size. E. g. for 1MiB you can have:
- 512KiB 512KiB
- 32KiB 32KiB 64KiB 128KiB 256KiB 256KiB 128KiB 128KiB
In the first case the list will have two nodes, while in the second case the list will have 8 nodes. This is just an example, let's say for 2 nodes we need of 4KiB of memory (4KiB is the minimum for physical page size). When I need a new physical page (also virtual page), how can I map the new virtual page in all processes? This is not the only example, the same situation is for open files. When a process open a file, all processes need to know that a new file have been opened.
Briefly, how do I update the virtual memory of the kernel in all processes when it is changed in a process?

I have 2 solutions, but it seems to me primitive.
1. I have a separate process for kernel and when someone wants to allocate memory or to open a file, he send a message (IPC) to the kernel process and he wait for a response.
2. For the physical memory allocator I calculate the maximum memory I need and reserve it. For open files, I reserve memory for x files and can be maximum x open files at the same time. But, for me, that is not a solution, because if x is 1000, I have reserved memory for 1000 open files but at this point only 5 files are open. So it will be a waste of memory.

I want a better solution. I'm sure there's something better.


Top
 Profile  
 
 Post subject: Re: Kernel dynamic structs
PostPosted: Sun Sep 24, 2017 6:12 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 999
Yes, the buddy structures have a variable size. However, you can allocate them once at boot time and then you never need to allocate more buddy structs (disregarding memory hotplug).

The common solution to your second problem is that the kernel shares its highest level page struct entries with all processes. For example, if you're in 32-bit non-PAE mode, the kernel shares its PDEs (lets say PDEs with index 768-1023 for a 1 GiB kernel space) with all processes. If you're in 64-bit mode, the kernel shares its PML4 entries (usualy entries 256-511 for the whole negative address space).

You should also consider mapping all (or at least most of) the physical memory into the kernel space, so that you can change paging structures without explicitly mapping them first.

_________________
managarm: Microkernel-based OS capable of running a Wayland desktop (Discord: https://discord.gg/7WB6Ur3). My OS-dev projects: [mlibc: Portable C library for managarm, qword, Linux, Sigma, ...] [LAI: AML interpreter] [xbstrap: Build system for OS distributions].


Top
 Profile  
 
 Post subject: Re: Kernel dynamic structs
PostPosted: Sun Sep 24, 2017 7:13 am 
Offline
Member
Member

Joined: Sun Mar 01, 2015 7:58 am
Posts: 51
I understand the solution. I do not know how I did not think about it. Thank you very much.


Top
 Profile  
 
 Post subject: Re: Kernel dynamic structs
PostPosted: Sun Sep 24, 2017 7:46 am 
Offline
Member
Member

Joined: Sun Mar 01, 2015 7:58 am
Posts: 51
But I have a curiosity. You may have a process with PAE paging and another process with IA32 paging?
Another question about TLB: I map 768-1023 PDE in each PD, but when I map or unmap a page in PT should I invalidate the TLB? As far as I know the invalidation of the TLB for unmapping a page it's a security method, but when I map a new page in PT should I invalidate the TLB for that page in each logical core or if I map a page in core1 and is immediately accessed from core2 everything will be ok or I get page fault? I read somewhere that is recommended to invalidate TLD when map a new page.


Top
 Profile  
 
 Post subject: Re: Kernel dynamic structs
PostPosted: Sun Sep 24, 2017 8:23 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 999
PAE is invisible to user space, it only affects the physical addresses that can be mapped. So you'll usually either use PAE in all processes or not at all.

Yes, after you unmap a page you have to invalidate it on all CPUs. OSes generally use IPIs to inform other processes that pages have been unmapped. Invalidation is not a security measure but it is required for correctness: Imagine the following situation:
  • Threads S and T both share the same address space but run on different CPUs.
  • Page P is mapped at address A.
  • Thread S unmaps P and invalidates only locally. Page P is freed.
  • The page P is reallocated and mapped into a second process.
  • T accesses address A. Because its TLB still contains P, thread T can now manipulate a different process' address space!

The correct solution is to unmap the page immediately but only free it after all CPUs have invalidated it.

_________________
managarm: Microkernel-based OS capable of running a Wayland desktop (Discord: https://discord.gg/7WB6Ur3). My OS-dev projects: [mlibc: Portable C library for managarm, qword, Linux, Sigma, ...] [LAI: AML interpreter] [xbstrap: Build system for OS distributions].


Top
 Profile  
 
 Post subject: Re: Kernel dynamic structs
PostPosted: Sun Sep 24, 2017 9:01 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 27, 2004 11:00 pm
Posts: 874
Location: WA
as for mapping a new page:

for most Intel (and AMD, iirc) CPUs, you don't need to invalidate the TLB when mapping a previously not-present page, because Intel CPUs do not cache not-present pages in the TLBs in the first place -- however there are some other brands of CPUs (cyrix?) that do cache not-present pages in the TLBs (for those CPUs, failing to invalidate when mapping a page can result in #PF)

_________________
## ---- ----- ------ Intel Manuals
OSdev wiki


Top
 Profile  
 
 Post subject: Re: Kernel dynamic structs
PostPosted: Sun Oct 01, 2017 8:46 am 
Offline
Member
Member

Joined: Sat Jan 21, 2017 7:35 am
Posts: 35
The buddy allocator uses a fixed-set of structs for fixed-set of memory. You will need to allocate this data dynamically before setting up your physical memory allocator (PMA). If you use multiboot, you should scan the memory map to allocate the structs in physical memory in a continuous range. Now, you should map the physical memory range to page-tables of kernel memory. For now, all this will be enough for non-hot-plug implementation.

Make sure - You try to allocate the PMA data after the 16th MB to save DMA memory.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: 8infy, Majestic-12 [Bot], songziming and 119 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