i wrote my own memory allocator in C to prove a point
Vložit
- čas přidán 19. 12. 2023
- Malloc sucks. Memory leaks, use after free? What ELSE is there to say? Instead of suffering through using malloc, I decided to write my own heap.
Heaps are, interesting. I learned alot here. Lets find out more together.
🏫 COURSES 🏫 Learn to code in C at lowlevel.academy
📰 NEWSLETTER 📰 Sign up for our newsletter at mailchi.mp/lowlevel/the-low-down
🛒 GREAT BOOKS FOR THE LOWEST LEVEL🛒
Blue Fox: Arm Assembly Internals and Reverse Engineering: amzn.to/4394t87
Practical Reverse Engineering: x86, x64, ARM, Windows Kernel, Reversing Tools, and Obfuscation : amzn.to/3C1z4sk
Practical Malware Analysis: The Hands-On Guide to Dissecting Malicious Software : amzn.to/3C1daFy
The Ghidra Book: The Definitive Guide: amzn.to/3WC2Vkg
🔥🔥🔥 SOCIALS 🔥🔥🔥
Low Level Merch!: lowlevel.store/
Follow me on Twitter: / lowleveltweets
Follow me on Twitch: / lowlevellearning
Join me on Discord!: / discord - Věda a technologie
wanna get good at programming? check out lowlevel.academy and use code THREADS20 for 20% off lifetime access. or dont. im not a cop
Hm, arent you a cryber-secrerty specealist? kinda like a cop...
virgin standard librarian vs based and gigachad wheel reinventor
bro 💀
my wheel is rounder
@@LowLevelLearning lll what do i do i accidentaly started rewriting c++ stl and physically cannot stop
every time i go onto my computer my hand starts searching for implementation :(((
Cabbage 🥬
@@LowLevelLearning and most definitely squeakier.
"This thing sucks!I can make it better.", "It still sucks but it's mine". Man... I feel right at home
That's me too, it sucks, but I know why it sucks.
Writting a memory allocator is standard part of learning C. People will not appreciate how complicated it is unless they have tried making one themselves
I keep making horrible web servers in every language I learn. They are absolute trash and I'm not even getting better 😭.
Been there. Many, what would be the theoretical idea for freeing memory with the minimum loss of performance?
Well, the problem is that malloc is slow not since it's implementation is bad but since it's designed to work as a general purpose allocator. One probably will not beat the years and years of programming art that flew into implementing such a general purpose allocator, by creating an identical clone. Performance lies in specialized allocators that can be way faster in some corner cases by using domain knowledge about the user code, which a general allocator like malloc doesn't have. Much like when Dx12/vulkan was released and devs tried to reimplement Dx11 style drivers which had like 10+ years of optimization wizardry in them already. No way to beat this. Rethinking the approach to a more domain centric solution was what gained performance benefits in the end.
im waiting for "intel sucks so i forged my own processor using raw silicon"
The story of AMD basically
Also there is guy, who did it in his garage 🤷♂️
@@MrMassaraksh calling that a garage is a pretty stretch my uni doesn't have the tools that guy had
I think a better concept is: "the x86 ISA is a real dog's breakfast, so I invented a whole 'nuther architecture."
@@christopheroliver148 RISC-V origin story
I just love the idea of working in a professional workflow, trying to grab some memory and just getting, "nah", for my trouble.
Needs the audio, too 😂
@@alvaronaranjo2589 One of the hacker moments of all time...
I once got the error message "Way too long, dude" from a first-party macOS application.
your ability to make C programming vids entertaining and funny is pretty amazing tbh.
When you realize C is both of those things.
in my university creating your own allocator is a mandatory project on third semester! its nice to see someone actually doing it for fun :D
Some of my coursemates were writing garbage collectors as a mandatory thing. Even hopelessly dumb at programming managed to pass that somehow. Comparing that to today's tech screenings... kids asking childish questions pretending to be rocket scientists. Able to use a standard library hash map, what an achievement.
@@InconspicuousChap An unfortunate number of colleges and universities teach programming and call it computer science.
you from feri?
holy shit where are you going university of wizards??
@@masterbaits4108 Georgia Tech.
"Is it faster? No. Is it more efficient? No." It's always fun--and honestly the best way--to learn by writing things that just don't make any sense. Like using C to make something slower and less efficient. But you are 100% and objectively correct when you say all that matters is that you learned something. Most of the best discoveries humanity has made come from people just trying stuff. Getting stuck into only doing what is "correct" is a box that's identical to just not doing anything at all. Do things The Wrong Way™ more often, and you'll be shocked at how much you grow as thinker and problem solver. You completely violated the entire reason we still choose C to write things--speed and efficiency--but made fantastic content and learned cool stuff doing it. And I learned cool stuff from you. As a professional teacher, I fucking love this kind of stuff. I wish I could convince my students to go offscript and try this kind of stuff so that they actually learn things instead of just memorizing and creating dogma. What a fantastic idea, honestly.
you should become a teacher!
Think of calling malloc like going to the store to get food, and having your own allocator like going to the fridge.
You don't want to use malloc every single time you want to "eat food", that would take so much time to travel back and forth. Instead you want to "meal plan", occasionally go to the store and stock up your "fridge" with memory you think you'll need, and then when you get "hungry" you pull some out to "eat", already conveniently accessible to consume.
Where the analogy breaks down is giving the food back to the store when you're done with it. Maybe a video rental store is a better analogy, but no one knows what those are anymore.
Thanks for the advice, but i already had dinner.
@@reed6514 instructions unclear, I've eaten an entire store worth of VHS tapes.
"Maybe a video rental store is a better analogy, but no one knows what those are anymore."
How about car rental?
a library?
you mean mmap right? both glibc and musl implementations of malloc have their own 'fridges' in your analogy
This channel really keeps me interested in learning c, thanks :)
I love how your videos are so short but packed with content ❤
always enjoy these videos, I used to program exclusively in C back in 1990's and now I get to have a retro back to the future blast each week! cheers mate and happy christmas!
I recently had to do this for my bachelors degree and I am so f*ing proud of what i did. I found writing some function like malloc on my own really hard, but finding out things about the opperating system and communicating with it even more fun and interesting. Great video, took me back to my own struggles.
I had to do this in University. It was a good time. Credit was awarded according to performance metrics, so if you wanted full points, you had to make a sophisticated allocator.
if you were learning C, and threw in a Garbage Collector you probably would have been flunked.
@@MistahHeffo I mean, yeah. We had to implement the malloc interface, just like in the video.
The sophisticated part was making an efficient allocator underneath that interface by using effective data structures and optimizations for the task--an explicit free list with coalescing was sufficient to get full points, but you could potentially get extra credit with more effort.
@harrisonfackrell I meant that if you implemented a Garbage Collected Heap Allocator in C that was absolutely flawless, you would have been flunked on ideological grounds alone
Man that looks interesting! Do you have the code uploaded somewhere on the web? Like Github or any other code sharing platform. I'd love to take a look at your code.
In this case it’s more efficient to not set the free pointer so close to the end of the allocated space. Something to do with polynomials
Yep. You basically created a memory pool. Went through all of this and and whole lot more with the dynamic memory pool component of my (non bare metal) OS. Great video 😁👍
Wow I literally made a malloc yesterday in x86 assembly and today I see you upload your own malloc. The universe is connected 🧠
Yesterday, as in you did it in a day??
Yes
Couple of hours actually. But I used sys_brk instead of mmap. Which allows me to actually extend my heap past the allocated initial value if my kernel of course allows me 😢
Can we see your code for reference
< yes here @@babudelhi9885
I love this video, brought me back to High School where the Systems teacher had us write an allocator and a scheduler. It also came useful since I actually had to write a custom allocator several years later for a job.
For what job?
Exactly what I was hoping for. Thanks for the video. 🙏
Haha, I actually got the idea in my head to try to make memory allocation in C easier too, but just doing so by obfuscating malloc() behind another function. I think you had a lot better of an approach 😂
i'm a cs student in germany, and we are currently, in one module, programming a little multitasking OS for an atmega 644. With own memory and heap drivers, aswell as malloc with different mem alloc strats, free, realloc and such things. It is really nice and one learns so much about low level programming with C!
Yeah, did that during a Bachelor module.
But without any (standard) library.
It was shitty, but worked.
he also did it without any standard library
@@human-ft3wk He uses the "mmap" function from the standard library.
@@reD_Bo0n gotta get memory somehow
@@UncleJemima Write your own wrapper for kernel interrupts (in assembler)
@@reD_Bo0n I mean, mmap is a system call, if you're going to avoid these you're basically rewriting the OS, which might be out of scope.
Would love longer video like this tbh ! 👍
This is a "fun" assignment we all do in CS as part of learning about the OS. I do wonder about the linked list though, not sure that's the best way to go about it. From what i recall in my courses we just used chunk indices and saved the next free index in the memory header
I do really appreciate the approach: you’re not reinventing the wheel to beat what tens of years of development lead us all to. You are just learning by doing, and I support that very much!
For the sake of educational purposes, though, I would suggest a follow-up with garbage collection, added quite easily by replacing the inuse variable with an int index!
You can then use that whole thing as a basement for a discussion about race conditions and so on.
Keep it running 🤟🏼
Gosh darn. That little “teehee” at the end is what got me to subscribe.
I remember looking through libmowgli's implementation of a custom allocator (mainly for checking how useful it would be for static memory allocation), and finding it to be quite impressive and relatively straightforward. I don't recall if it addresses the issues you bring up at the end of the video, but I wouldn't be surprised if it did.
I love how I just did this a couple of weeks ago as a hw for my intro to computer systems class (CMU). We did malloc using a 8 bit header and we implemented coalescing as well. Honestly I just wanted to add this cause it was great and I really do recommend everyone try to do it as a project if you want to learn about heaps, malloc or just practice some C programming. Less than 2000 lines should do it all.
Out of curiosity, why use mmap() to allocate memory? The kernel has an actual syscall for handling heap allocation to the process, brk(), and libc usually has the sbrk() wrapper to make things a little easier. This a good learning exercise though to learn about the black magic that is heap management and all the subtle nuances that go along with it.
This is all nitpicking, the real issue, which is unfixable if you want "your own" malloc to be perfect, is portability; outside Linux these are not a thing! Outside POSIX mmap() is also not a thing (don't say "Cygwin", that's pure hackery!).
@@erikkonstas brk() and sbrk() are available on nearly all Unix and Unix-like OSes, so its quite easy to make a malloc() implementation that is portable within the Unix realm. While Windows doesn't support brk(), it does have a similar system call, and its not all that hard to structure your code to be able to be portable between the two. Is Cygwin even relevant anymore considering WSL?
That's essentially what they asked us to do as homework for our OS dev course :D We had to implement it in Minix.
this was quite interesting to listen to, always wondered if anyone from the "new schools of thought" actually did any of the old-school stuff....I've probably made at least a dozen of memory allocation routines.
some advice, double-linked lists work better along with storing the table information directly into the heap, as this would redirect the cache for use at that location for when the requestor decides to actually use it. The "structure" I used had 4 variables (next, prev, flag, size), and you can recast a pointer to that structure/class to get the data at the heap location. The flag contains an ID mark (to ensure that you are freeing a valid pointer) along with other use case checks for various things (depending on if you have "shielded" or contained protection, or if the data contains multiple location paths for cluster storage....etc. etc., very advanced stuff). Aside from that, you only need maybe 5 other pointers in a static position, the heap pointer itself (to free when the program unloads), the first/last of used memory (init to null) and the first/last of free memory (init to heap pointer). When allocating, the return should be a pointer adjusted after the structure/class, and when freeing, subtract that size to get the true location. "size" of the data used includes the struct/class as well, makes it easier to coalesce calculate later (if true pointer plus size equals next free pointer, then it can be combined).
why double-link? it literally is much faster to assign and unassign, and defrag comes along with it. Plus, you could have "solid allocate" functions where the requested space may lie dormant for awhile, can be allocated from the back. It's also not the difficult to add in the ability for multiple heap connected spaces, as link pointers can jump memory bounds.
Could you do a similar video but showing us what’s in the heap? It would be cool if you could print out a table with everything in the heap
An easy way to combat fragmentation is to use a buddy allocator (or slab allocator) strategy. It has pros and cons, but dealing with fragmentation sucks.
funny that this would come out when I've been painstakingly writing my own dynamic memory allocator in assembly the last couple days for my homebrew system
Yaaay!! That’s actually pretty cool! I did this as part of my final degree thesis in compuer engineering and it was pretty fun 😊😊 Nice vid as always!!
We had a project in our school where we had to do the same thing but with realloc and calloc to which was quite fun
Funnily enough, I programmed my own malloc and free a week ago; I went with an array of bytes (unsigned char) with a predefined size, and implemented a doubly-linked list with the data being in-line with the heap object info by using an empty struct at the end of the heap object info definition as the data marker. I didn't need an 'in use' boolean because I used the heap object's size as an indicator, 0 meaning there was no heap object there.
Heap allocation is a general approach to dynamic memory allocation...
The bicycle is already invented and it would be a lot better to master different allocation techniques (sized pools, arenas, ring buffers, stack dynamic allocators etc.) and use them where needed.
Or just use libraries like tbb malloc :)
i had to do this for a cs assignment in college, it’s honestly crazy how much shit gets abstracted behind the standard C libraries
Great that you did this for fun but I had to do this as a project in a top 20 school
My personal anecdote about "reinventing the wheel" (but learning important stuff along the way) was building a simple 3D model editor (for modding a game) with zero access to an actual 3D library API. I learned about coordinate transformations, surface normal calculation and cull-facing, trianglefans vs. trianglestrips, and _so much more._
Great video! I really appreciate your ability to make these videos highly educational, while also being fun and easily digestible.
I appreciate that!
this vid was incredible and also gave me instant anxiety from assignments i had to do like this in college in c
huh, I remember this guy from LinkedIn posts
I love this video, so useful since I’m doing an OS class! I understand some of your words magic man!
Glad to hear it!
0:06 The essence of C programmers
Can you make a more indepth video about dynamic memory allocation? Explaining how glibc's malloc work, other alternatives, how does it differ from other systems languages, like rust and zig... Can you have different heaps? Etc
Two or three years ago I wrote a non-contiguous memory allocator in rust. It was a fun little project, though it was actually for my work. I ended up learning a ton about memory security and how memory works on the lowest level. If you added canary pointers and zeroed out your heap memory before dropping it, you would be most of the way to the security of something like libsodium. They also have memory guards and they use the kernel memory permission calls to lock memory, but something I learned from an audit of my system is that locking memory actually makes it more potentially exploitable. With memory locking, you basically attach a metadata flag to the memory chunk which the system looks at before it attempts to read or write to that chunk. If a malicious actor forced a system coredump of the memory, they would still be able to see and what was inside of the memory chunk and most importantly, it would have that metadata flag that shows that it was locked. In other words, the malicious actor could use the metadata flag to find where the most secure data was in the core dump logs. There are ways around this of course, you can prevent chunks and memory from being dumped, though we did something completely different for the non-contiguous memory allocator. Effectively what we did is we used a bunch of xors and hashes to split the secure data into parts and put it all over a large area in the memory space. And then when you went to retrieve the secure data, the allocator would take all of the discrete chunks and xor them together to get back the secure data and a hash of the secure data.
loving this, worst part is it wasnt longer
Subscribed keep it up my dude I'm going to school for a computer science degree and I gotta learn C so this was cool
Here is my version (much better):
my_alloc() {
malloc();
};
my_free() {
free();
};
Yeah, you'll just end up with memory leaks and crashes, but funny 😅
#define my_malloc malloc
#define my_free free
It wouldn't be possible to get a link or something to the code written for this video, would it? I'd like to take a gander at it so I may learn some more C and coding practices. Thanks either way, very cool video and idea!
Just wondering, what happened to the advent of code videos?
I remember creating a slab allocator for a stub OS was one of the projects one could choose for (part) of the exam of Operative Systems. While It seemed cool i was more caught up on signals, but I sort of remember the way it was done, so this rings a bell
I did that using assembly for a university project. I still have the scars.
This reminds me of the pain of trying to code a Texture Atlas from scratch in Open GL.
This looks pretty neat. I'm considering making a small allocator in rust because rust doesn't let you pick the size of a new array (not a Vec) at runtime. Hopefully it won't be too complicated
Have you tried boxed slices?
Could you go over some malloc alternatives like talloc, jemalloc, and tcmalloc?
Could be worth revisiting this project and seeing what other APIs you could provide that makes allocation easier to deal with.
Could be simple things like seeing how the implementation is affecting by requiring free to pass a size as well, or more complex things like looking at arena allocators and how you can use pass-by-value semantics to make the program automatically free memory when you return from a function without the need for a GC or any use of the free function.
please make a longer more in depth video on this
I got a very "primitive" model of my heap allocator working. However, I'm not sure how to properly "classify" or describe it, since it works exclusively with a particular type of "meta-object" that actually handles the "span" of the allocation... Yes yes, that means that it's more of a frame-work than a run-of-the-mill allocator. But! It doesn't leave any holes in the heap... in fact it barely moves anything on the heap much at all whilst also being able to resize existing spans of memory "in-place"... it's probably the most illegal c code you've ever seen tbh, but you have inspired me "to boldly go where behavior has yet to be defined" 😎
First! 😍 Oh yeah... 3:00 - lol - every time I write malloc(), in my head I sing Monzy's So Much Drama in the PhD where he goes "I ain't never callin' malloc without callin' free."
Next on the list. warning about potential memory leaks and maybe even a visualization of the current heap allocations. it's age, it's size etc.
"We could truncate the chunk."
Chunkate, surely.
I did something similar but it had a bit more to it than that and was hell to get to work, but when it worked it worked well. As I recall it was the debugging that was the trouble. it would screw up, but only once in a blue moon.
Oh man.. this reminded me of our OS course in uni. We made a visualization of this in Java, complete with compaction, coalescing, and automatically freeing the allocated memory once the process is done. It's just a visualization tho, it didn't actually allocate heap (except for when we create new objects, but that's just a technicality).
I had this exact exercise!
Had to do the same for a university assignment, but we were only allowed to use sbrk and brk but no mmap.
Game engine darkplaces (Nexuiz and others) uses own memory allocator which is a wrapper for a malloc and free. Its allocate bit more and wrote additional info - from where, why and which group - which is useful for debugging - not only for mem leaks.
HAPPY EARLY NEW YEAR BROGRAMMERS!!!
I had been starting to wonder if memory allocators did defragmenting. That stuff was only ever mentioned to me when talking about garbage collectors, and I was really starting to wonder if this was a consideration
Not in the same way. You talk about defragmentation in GC that uses compaction, generally by copying all allocations that still exist to a new space without the gaps, then updating all the references to the old locations.
Without a runtime you can't do the latter step, so the best you can do is try to allocate things in such a way that deallocating isn't likely to mess things up.
One simple and effective approach is to keep all allocations that are pretty close in size together, say, all the 8 byte allocations, 16, 24, 32, etc... Then no matter what order things are deallocated you still have the same size available.
Bro i need that "Concentration Cap" you are wearing.
I recently did almost exactly the same thing for manually allocating gpu memory.
That's so oddly convenient. I was literally thinking about learning how malloc works under the hood
If you want to keep to abstract standards, you'll have to accept it as a black box... otherwise, you have to dive into the kernel source code; it's NOT as simple as what you see in the video, it's been refined over the years to be as efficient as possible, and it keeps being improved; for example, you are usually given more memory than what you first ask, because there's a high change you'll keep "reallocing +1" (which is itself a bad strategy, there are more efficient ways to manage "capacity", which should be separate from "length" in a data structure).
I randomly had the idea to make a custom heap allocator few days back. Have been working on that idea for like a day. And boom youtube recommends me this video.
it was destiny
that is google spying on you,.
I remember doing this when I was working through the C programming language book. Fun times
Thats your best video yet
Have a good Christmas and New Year! 🎉 =]
I like your words, magic man
If only I had programming memes 15 years ago... I needed this my whole life.
You could use segregated free lists. I did this same project in my Computer Systems class!
Virginia Tech I assume? (just bc no other college I've seen calls it computer systems xd)
What about the case where you free a block to the heap and the block before it is still used, but the block after it is free?
Yeah I noticed that too... 😂
See ya next year!
I've tried this & even tho it's worrisome to some extent, it's an incredibly great learning experience
We had to do exactly that at uni!
I would not write my own malloc / free functions, but I have built my own "memory management method" upon them.
Where I can find the full code and also the full video for this? @LowLevelLearning
In order to make a performing algorithm you typically base it off a static allocated pool of memory with a different base structure to allocate, deallocate and remerge regions from that very pool... Any system calls to dynamically allocate "behind the scenes" is basically just programming a facade which in turn might be even slower than calling the functions directly.
I did many implementations for Microcontrollers and Windows in C and C++ ...
If someone wonders "Why for Windows?!", because if you have a ton of alloc and deallocs, especially of smaller buffers, in a short amount of time, you might get randomly greeted by obscure exceptions which basically are caused by an awful memory fragmentation. Newer Windows versions are a bit more robust, but they still have that issue.
We had to write our own malloc as part of our first "real" computer science class at Georgia Tech. It was the only assignment I submitted that I knew didn't work. I still somehow passed. Despite not working in Ubuntu, it somehow worked in Windows. All of our assignments were supposed to be graded against an Ubuntu image distributed by VMware, but my TA must have been a little lazy or overwhelmed that day and graded on his own laptop.
What would be a good free resource to learn c as a beginner
And do stuff like you do?
Instead of creating custom alloc/free functions, there is an alternative method for integrating a malloc variant into application code is to implement malloc and free. You can compile the allocator library into a shared object, and set the LD_PRELOAD environment variable to point to that file. Then, your custom malloc/free code will be used in-place of the default implementations whenever you're running an application.
I believe standard library uses brk()/sbrk() system calls to increase heap size (but I believe there is only one break pointer per process, so you would have to disable the standard library's allocator).
It's still there for compatibility, but discouraged against. Apple deprecated those calls in macOS ("The brk and sbrk functions are historical curiosities left over from earlier days before the advent of virtual memory management."), and glibc on Linux only calls it once to allocate some memory for the allocator itself, leaving the rest to mmap.
How about adding expiration time for each allocated memory (for example in milliseconds). This way expired memory could be easily reassigned.
How the mmap worked btw , you have given a negative file descriptor for the call ? . This seems to be a nice implementation.
I really admire low level programming. Will start learning C. Can’t wait anymore.
0:48 was honestly expecting you to swing for sbrk
this inspired me to do the same but with buddy system
I had to write a custom heap allocator in my OS/System Programming course. The only really involved C project we had written (in a prereq) was a simple CRUD driver, we were given 2 weeks to write it alone (heavy collaboration penalties), *and our grade was entirely based on cycle and memory efficiency relative to the standard C implementation*
I scrapped my entire codebase twice in the process and after several programming fugue states driven by dangerous levels of caffeine consumption I ended up with an 85%
where to view the videos creating them? I wanna learn
I wrote my custom allocator recently. The trick I used was to only allocate chunks of sizes of powers of 2. I also had them clustered that way. Finding the right free chunk is trivial then because it can always be larger than what the user requested. Besides, should the user want to expand the chunk later on it would also be trivial as long as the requested additional memory doesn't make the chunk exceed the next power of 2. I was dealing with array buffers that needed to automatically grow when they get full. Since usually you would double the size every time the buffer gets full it makes a whole lot of sense to only allocate chunk sizes of the powers of 2.
Cool probably not memory inefficient if you are not allocating in powers of 2
@@monsterhunter445 yes it wastes memory but since I develop games I always optimize for performance at the cost of memory.
Creating your own heap allocator. What an absolute Chad! 💪🏻
Stack OverFlow called...theyll be needing their Chad chin back now! 🎉❤😂
shouldnt the coalescing be a while loop instead of an if statement in case of a chain-reaction of coalescing? its possible