How does KERNEL memory allocation work? //Source Dive// 004
Vložit
- čas přidán 12. 10. 2023
- In this installment of //Source Dive//, we're deep in the xv6 operating system, trying to understand how physical memory of the system is tracked, distributed, and returned to the kernel. It's a fascinatingly simple algorithm, which can be paradoxically kind of hard to understand!
=[ 🔗 Links 🔗 ]=
🐋 RISC-V Docker Image: github.com/francisrstokes/rv-...
🎥 Series Playlist:
🗣 Discord: / discord
⭐️ Patreon: / lowleveljavascript
💻 Github Repo: github.com/mit-pdos/xv6-riscv
This is my favourite series on CZcams right now, absolutely insane how well you explain the code you're going through. Great work!
Seconded, this is SO lucid
26:35 memset is in fact byte-based, just like other mem* functions, the argument is an int for legacy reasons
You're totally right
So in bytes, a free page will look like
0x00 0xf0 0xab 0x52 0x20 0xf1 0xa1 0x14 | 0x01 0x01 0x01 0x01 0x01 ... 0x01
with the first 8 bytes being a pointer (lowest order byte first I guess) to whatever page has been freed previously (Of the ones that are still free of course)
It's so cool that you can basically index into a linked list in O(1) because the data IS the list node!
Edit: of course it must point to the beginning of a page, oups
Yep, that's it!
Using the actual memory as your free page linked list, a struct which its only field is a pointer to the same struct... Only in C, don't you just love it!
Also in C++
@@luisfernando5998we don’t talk about cpp here
Love this series , low level content is very rare , appreciate it ❤️
That diagram feature is exactly the thing I need for my own projects! I didn't even know it was there!
That's the draw.io extension. Absolutely life changing
I know I could read all this code myself, but it's just so relaxing watching this video, I don't even have to do anything!
Every morning I now spend an hour trying to watch a video from this series and learn something new. Great content, please continue this amazing work!
As youre going through the freelist im sitting there thinking "ok so I guess while you allocate 4096 bytes the user only actually gets 4095 (or whatever), otherwise the user could f' up the free mem tracking..." Yea ok, i guess its a small tradeoff, probably a really efficient way of doing things still... Then you said the magic phrase
"We dont need to track the memory once its been allocated..."
At that point it _all_ fell into place and I just ended up with a massive smile on my face.
Really well done, thank for sharing :)
I have watched the previous episodes with pleasure! I like now how you've added diagrams to your teaching repertoire🤩
The explanation of the linked list is so well detailed, it's a really clever trick
as someone who had only one semester/class with lowlevel C programming... i REALLY like it! Even my brain can understand it a little!
Great work Francis! These source dives are very helpful.
Ayy thanks Greg 🙏
This is just awesome. Thank you! Can't wait for the next episode already!
really good explanation, whole series is super awesome, thank you for doing this ❤
Difficult but very interesting concepts. This series is really very riveting. Can't wait for the next episode. Thank you for all of your hard work. Please keep going.
Please continue ! Loving this content. Thank you
I NEED MORE! Was waiting for this one, seems good
Just wanted to thank you for these excellent videos. Really amazing stuff. Cannot wait until you will tell us all about how context switching is exactly working. 😊
malloc also uses this type of unstructured memory access like this kalloc function (so even for userspace we don't use more structure). We just have a chunk of memory and write an address to the next free chunk in the first few bytes. Also, these chunks can be of variable sizes, so you would even need to insert more implicit structure and markers into the memory locations. (Plus we have several lists, mechanisms to prevent and resolve fragmentation etc.). So if you find this kind of structuring interesting, definitely have a look at the common malloc implementation and other allocators in general.
Amazing video!! This series is really good, i'll keep watching the following videos
Wow! I think that visualization was awesome!
I am amazed at how simple this idea and implementation is. Takes some really clever people to come up with such an elegant solution. Memory allocation and freeing always seemed like black magic to me.
PS:
Since you seem interested: mainly I'm a PhD student in theoretical physics (quantum optics and quantum information theory) but has had programming as a hobby since I was 14 or so, started with C++. Since then I have always been curious how a computer works (physically and software wise).
Really loving this series, I turned notifications to follow along.
This channel is such a gem. Amazing content.
I love this series and you're very good at explaining things in a concise manner. It would be interesting to see how you use the debugger to get a better understanding of what's happening.
Mind-blowing yet very understandable video, keep it going! I'm actually trying to read code first and understand it and then listen for a great explanation. Also, it was super fun to try to write on paper implementation of the kalloc function and see 1-1 correspondence with code base (despite error checking and locking though).
Really well explained!
I am grinning ear to ear to see how smart these OS developers are. Thanks for making this video.
Very interesting topic! I currently study that in university, but at a software point of view. Seeing this from the kernel pov is fascinating, and it doesn't differ that much. :D Looking forward to the next vid!
Very informative video and nicely explained.
I really enjoyed watching this video. Thanks for this amazing stuff.
Hello and thank you! It's all come together for me, rather quickly. Middle of last year I couldn't count in binary and end of this year I'm looking at the ELF_magic in riscV kernel! Thanks for these vids
That's awesome to hear! Keep climbing 💪
love this series!
Great video! I have never thought that memories worked like this.
It's crazy right
Very interesting, didn't quite catch all of it but I'll get there eventually :)
indebted to you for the knowledge you're sharing
Really love this!
Such excellent videos!
I havent programmed in a while but this video made me curious so I cloned the project and am playing with xv6 now. Note that instead of the huge Docker image you provided, on my Mac I was able to 'brew' the x-toolchain as described on the MIT project page.
Was able to untangle the pointer acrobatics of kinit() by printing out the first 8 bytes at the beginning of every page. The first page seems to have all zero bytes at the beginning (forming the NULL pointer) while the first 8 bytes of subsequent pages point back to the starting location in memory of the previous page. Very cool to see how it works.
I really like this series, I love the fact that you go into so much detail and are not glossing over the code, I like the code. I do have to say that the name: "paging" always suggested so much more then what is actually is, blocks of 4k memory. I still love it though. I always like things that work on a "stack" like a function call or command pattern and this kinda feels similar. It always feels a bit magical.
One of the things I wish I'd realised sooner was that so many concepts I thought were complex and out of reach are actually completely accessible (sometimes with a little work!).
Giving yourself permission is half the battle.
38:30 I wonder if it would be better to have free pages stored in a structure, as you expected. Yes it's very elegant and clever to use the memory itself as a linked list structure, but in modern CPU architectures linked lists are generally to be avoided because they don't play well with cache. I suppose the only way to settle that question would be to build and test it, but honestly I'm not interested enough to go to that much work. :-)
You're spot on, it's not at all performant with today's hardware. Linux uses something called a buddy allocator internally: www.kernel.org/doc/gorman/html/understand/understand009.html
@Low Byte Production, thanks again for this great Video. I hope you bring us all the way up to the user land. I added a "free" command including syscall already.I am in IT since 1998, most of the time as Linux System Admin and Network Engineer. I was in high level user land (CLI), I can do some programming languages like perl, ruby and golang. Since 2016 I do every October some deep-dives how Systems work. I looked into assembly, transistor, logic elements, ben eaters 8 bit computer, arduino, c and c++. I also look into cryptography. Your video series bridges the gap between the low level and my high level knowledge. Actually I would missed my deep dive this October but then youtube send me to your series. So double Thank you :-) If need some input regarding sys calls etc. I will reply with the links I used and the update (cause they weren't uptodate). Best regards Markus
xv6 kernel is booting
kinit: Start Addr: 0x0000000080021db0, End Addr:0x0000000088000000
kinit: freepages 32735
hart 1 starting
hart 2 starting
init: starting sh
$ free
free memory 32565 Pages
free memory 133386240 Bytes
free memory 130260 KB
free memory 127 MB
Wow that's a great idea! A whole month of study focused in one area. Might have to try that myself
I'd love this!
Awesome 🙌🙏
It's insane how good you explain this. Are you a teacher? If not, be one because it's just awesome
I'm not, but I appreciate the comment!
Nice video. The heap metadata for modern OS's is more complicted to accomodate for improving availabilty, fragmentation, etc. This singlely-linked list is generally used for 'fast bins'; bins of small chunks of memory that are too small to worry about optimization on. The main question I have, is why did they call the structure for this memory metadata 'run'? What a terrible name for the memory allocation metadata.
So the free list is more of a free stack here :D
Thank you
Thank you so much for your wonderful explanation! Is the single-linked list implementation the default one for most of OS? What happens if a user program forgets to deallocate memory? Does it mean it is going to be lost until the system reboots? Or the occupied pages are kept track of in a custom implementation of malloc, like libc malloc? Because I remember there is also supposed to be a mechanism for separating contiguous blocks of memory depending on the size to get optimal performance...
When a user process ends, the kernel automatically frees any pages that belonged to the user, so no chance of leaking memory that way. Interestingly this also how all modern operating systems work, which is why people sometimes say you do not need to free all your allocations if the program is about to exit anyway (it's probably still good practice though!)
@@LowByteProductions yes, but how does kernel know what was allocated? You mean, in a full OS keeping track of allocated space is unavoidable? The idea of keeping track of only freed pages seems so elegant though(
One problem with this approach is if some DMA master requires physically contiguous memory spanning multiple pages as you will have to traverse the list potentially multiple times in search of them. It also requires entire physical memory permanently mapped into kernel address space, which is not a problem on 64bit cpu, but can be a big problem on 32 bit systems.
two thumbs up!
Linux does use a large global table to track all of the dynamic memory pages in the system. This table itself hogs a large amount of memory, but one of the advantages to that allocator is that it can allocate blocks of contiguous pages, which it looks like this allocator does not support. The page state table is overloaded for many key Linux kernel functions, so it is quite a bit more complex than this example, which is nice in its simplicity.
Really enjoying this! In kalloc.c, free range... Why are the parameters void* when the implementation casts to char* anyway? Why not just have char* as the parameters to start with? The only reason I can think of is API stability allowing for the implementation to change, but I've only ever seen memory bytes represented at chars
It's also the free page that has the highest chance of being in the CPU cache no? Really ingenious.
That PGROUNDUP and PGROUNDDOWN macros are Amazing (yes, amazing by capitalized 'A') 😀 I've never seen so much such smart code in one place.
You should check out one of "creel"s videos about interesting bit operations. They never fail to blow my mind
I did something super similar not long ago, to align numbers to a certain power of two byte boundary. It's way better and simpler than previous versions I made of it.
One question I got is that in the memory layout you drew, the kernel space is located at the bottom of the memory address, does it mean that kernel starts at lower memory address and virtual memory allocation grows upward in memory address? Or should it be that kernel space starts from the higher memory address and grows downward?
RAM ranges from 0x80000000 onwards. The kernel code and data is loaded there. Everything left over is memory that can be dynamically allocated. That memory can be thought of as being "above" the kernel so to speak. Stack memory, which we'd think of as growing up or down, is actually located within that initial kernel memory space
great series. A tad slow for me, gonna be about six months till we get a shell prompt :-)
Could take a while, although I expect I'll be able to speed up in some areas once the core OS concepts are on the table.
Amazing work, thank you. Really looking forward to your subscriber numbers exploding. Finding low-level stuff is so difficult.
How much of this can be mapped to how the Linux kernel works?
Thank you Kerim!
I can't really speak expertly on linux, but I would say quite a bit actually. Linux is definitely an order of magnitude more complex in nearly every dimension, but all the essential parts will be the same. It still has a kernel allocator. It still has processes and a scheduler. It still has to manage virtual memory etc
I wonder if this design of freeing memory pages based on the pointer of the next memory block is also the most optimal way, in multi CPU systems, using L3/L2 caching and Intel's QuickPath Interconnect (QPI) or AMD HyperTransport.
LOL opening screen could be a poster for "clean code".
just a note here becouse maybe i missed it or you didnt say it, but the page freeing and allocation does not need to be sequential, thats why the pointers to the next struct exist. Free your memory or you will have a memory leak ;)
IF the 'next' pointer is stored in the block itself, then the block to the process is only 4092 bytes big and how are continuous >4k memory blocks handled?
What happens if the kmem pointer is null? Wouldn't that cause a panic as null < end so there's no 'out of memory' check, or am I misunderstanding? Also, wouldn't the struct mean that there wee 2 points loaded into he first 128 bytes off each page, 1 to the next page and 1 to the spinlock or does the compiler take care of 'pointing' to the lock?
Im not entirely sure what would happen if kmem is null in this case, but using a null pointer is considered undefined behavior, so it would be pretty unpredicable or thow an exception. Kmem isn't really considered a pointer, but just a globally declared variable of the struct type. FUN FACT: globally declared variables are often automatically initialized to NULL, except for structs and unions in which it's members are initialized to NULL, though I personally wouldn't recommend it as it is also considered undefined behavior. The panic check uses the pointer sent to kfree by freerange and not kmem which is just used to hold the address to the start of the page list and the lock . kfree only writes the freelist pointer that is in kmem to the page so that is only 8 bytes.
I hope this helps
@@captaincluck8129 Throw an exception? You don't have those in C do you? I fee like I'd like to try this now to see what happens when you run out of memory or how this is handled as it seems to me a panic is all you can expect which is not a very stable way to design an OS, but I'm sure they thought of that and somewhere there's some code to detect such a condition which maybe we'll see over time.
@@SirKenchalot From what I've read, exceptions are actually a feature of the cpu. The panics in xv6 are actually used for problems that are highly likely to corrupt a resource that the kernel is controlling. You could actually consider them to be like the BSOD in windows
❤
There are very few spots in the video where increasing your font size by 50-75% would cause any issues whatsoever... and it would help incredibly on small screens and old eyes.
I'm kind of surprised that they just round the page addresses up/down like that, because imo passing in a start/end address for the pages that isn't 4k aligned is a bug. At least, in my page allocator I treat it as such. I also have a function that runs once on startup to sanity check that the page size and page shift actually match but that's probably overkill.
It definitely makes sense! In xv6s defence, freerange is a "private" function only called in this one context, so the only value you'd ever expect it to round up would be `end`. Not entirely sure why they did it this way, instead of just inlining the stuff in freerange into kinit. I think it's because the original version of xv6 was written for x86, where the process is a bit more involved (and the freerange function is used multiple times).
Is `end` also aligned in memory to the 4k page? Rounding up to the next 4k boundary would make it so that if the pointer passed to that function is using any of the 12 lower bits, then we know what has been passed is an invalid page address (void *pa). (I retract my comment, it's explained that `end` it's not aligned at 31:00, but the pages are aligned).
I'm still not sure why they didn't just align end in the linkerscript. Maybe that was deemed a little too magical?
@@LowByteProductions It also means that there is up to 4095 bytes of memory that's not used. You could perhaps stash some data that that you know nothing is ever going to touch. It's cursed, but it's possible.
Can you talk about how you learn what parts of a code base does? Like I can read many languages well but I have no idea how to find what code does in a methodical way. Could you help with that?
I will try to incorporate more into the future videos.
But for now, two tips:
1. Learn to use the debugger! Everything from stepping through code, to Conditional breakpoints, to log points, inspecting memory, etc
2. When investigating a new system, write down assumptions you have, observations you made etc. Then try to test these assumptions by experimenting, stepping, adding lines etc. If the outcome doesn't line up with your assumptions, that's great! Your assumptions were wrong. Try to make new assumptions, test them, and throw out the stuff that didn't turn out to be true. This is essentially the scientific method.
@@LowByteProductions Hey this is enough for me, I don’t use the debugger enough but to see how much you’re accomplishing… I trust it! Great job in the videos 👍🏾
I can imagine that this method leads to memory fragmentation, but is that an issue? Does it affect the process performance at all?
BTW: Not sure since this is not an x86/x64 based OS, but in that world pages are 4K because that's what "granularity" i386 protected mode supported (other than byte-by-byte mode) - not sure if other sizes are possible now on modern x64 or ARM hardware.
On the new apple silicon processors, page size is actually 16KiB! I remember it cause some headache for the asahi linux developers when they found a lot of hardcoded 4KiB assumptions throughout the codebase.
Storing the freelist in the free memory itself is just genius, its already free, so why not use it then to hold the pointer.
Right!
There is this constant memset going on in kalloc and kfree, always setting 4k of memory (and actually the complete memory on setup). How is this efficient? How is memset implemented?
Yes that is indeed happening. You'd be surprised at how efficient memset.
memset and memcpy are probably the two functions that run more than anything else in any computer.
@@LowByteProductions Okay, I figure that there is no for loop running in memset :D So does it compile into a machine instruction, or how exactly can it be soooo efficient?
It's not necessarily important how many instructions it compiles into, it's how many cycles the functionality takes. There is no faster way of doing it, so in terms of efficiency it is, by definition, perfect.
Stark contrast to user code, which is possibly what you're understanding, where value semantics (requiring copies) is worse than reference semantics (requiring indirection but no copy), for large objects. Efficiency is then a discussion because "it depends" whereas here it doesn't.
Question about the KERNBASE=0x80000000L. Imagine I want to build a physical device running with this OS, should I wire the physical memory so that there is a mem chip responding on address bus at 0x80000000L? Otherwise, thanks for the high-level content, that's fascinating to dive into this!
You're welcome!
You could wire it that way, certainly! You could also redefine the KERNBASE and place RAM where it was most convenient. All of this mapping is geared towards the design of the qemu virtual machine, so mixing things up to your setup is probably easier than trying to mimic the qemu vm.
@@LowByteProductions I get it! Thanks a million! ❤
12:00 Yes, this is a PERFECT example of why this style of naming is BAD. We're not living in the 70s and 80s any more, there's no need to conserve ram by keeping names short. Yes, pre C89 limited you to 6 characters. C99 allows you up to 32 characters in length. Use them. The only excuse is when you absolutely MUST use short identifiers only, which is vanishingly rare.
Long descriptive names with underscores to separate words make things so much more readable. And you don't even need to type the entire names out any more thanks to tab completion being present in nearly every editing environment.
Luckily the NT kernel fixes this issue by introducing wonderful function names such as "PsSetCreateThreadNotifyRoutine" and "MmAllocateContiguousMemorySpecifyCacheNode" (real functions you can find on MSDN)
What surprises me is that they free mem pages to the list under lock. What I would expect to see there instead is atomic compare exchange.
risc-v doesn't have a cmpxchg instruction
interesting algorithm, but what happens when multiple pages are allocated to store a large (>4096byte) block of data? how are the first 8bytes for each page (which contain the next pointer) write protected so they don't get overwritten with data?
Only free pages have a pointer in their first 8 bytes. As soon as a page is allocated, it's removed from the free list, and the consumer of the page can use the full 4KiB for whatever they want.
Although the kernel does make use of kalloc, it doesn't need it for anything that is in excess of a single page, so that issue does not arise in kernel space. In userspace, the user would call malloc, which through a few levels of abstraction, ends up both allocating as many pages as are required for the amount of memory requested, as well as making sure that memory appears contiguous to the process by virtually mapping it all sequentially. This will probably make quite a bit more sense after the next video, which will cover the essence of virtual memory.
@@LowByteProductions thank you for the explanation.
Generally kalloc(size_t sz) takes the size of memory to allocate, but in this os code why kallaoc(void)
suppose if i want to allocate memory for a structure of 25 bytes, I get whole 4096 bytes, Is this inefficient
Correct me if I am wrong
kalloc is a page allocator, so yes it always returns 4096 bytes. You can build a finer grained allocator on top of this mechanism.
Ok Thanks. I am comparing this page allocator (kmalloc) API with linux kernel kmalloc API.
Thanks for pointing out😊.
fuck yeah youtube algorithm rocks
So basically the OS "frees" every page after the kernel space to create the list of available memory? Starting from the first page, it just iterates upwards up the heap until it reaches the end of memory. Its like building a deck of cards by placing them on top of each other on a table. You start with the first page right after the kernel space, then you put another page on top. If you take that page off you get back to the page you just covered... the OS builds a deck of memory with pages the size of 4KiB when it starts lmao. Whenever we use memory we just move that pointer down the top of the stack, and when we give it back we move that pointer back up the stack... though in real world operating systems its probably much more complicated 🤔
You got it! Great summary 👌
thanks to christian bale of kernel programming
Christian Bale in "Batman", or Christian Bale in "The Machinist"?
You constantly need to 'actually' do things. Just stop saying 'actually' 2 or 3 times in one sentence.
I might actually do that
What I do not get is why you need the run structure in the first place. Couldn't you just copy the value of freelist to a variable then assign the dereferenced variable to freelist instead?
I mean, that is essentially what is being done with the struct. We need it anyway to keep track of the freelist itself, so it makes sense to use it as a lesson to write into each page.
I think this way it helps self document the code and make it clear it is a linked list.
@@wizhippo Thanks, that answer makes sense
It is better to have panic("kfree %p", pa);