Pulling Back the Curtain on the Heap

[@Jonathan-di1pb]

I think the sudden migration is a measure to combat fragmentation. It just basically starts over fresh therefore undoing all the fragmentation it created before, which probably results in a decent speedup and more efficient memory usage.

[@rickwightman2366]

"Oops, I have some warnings. I should fix them." A sure sign that someone is worth listening to.

[@AlejandroAnzolaAvila]

I was reading Understanding the Linux Kernel some time ago, and while reading about memory (1.6.8 chapter), it was detailing that the address given by malloc is not really an address of the actual memory, but rather it is that the address that you get is from the virtual memory always, and also, somewhere else in the book that this memory is not really allocated until you first access it, so the kernel tries to defer that allocation until the last moment, I'm sure I'm missing a lot of details, but it seemed very interesting to see that mechanism, maybe these page changes that your program saw when doing the random allocator could be related to this behaviour.

[@harrytsang1501]

That is a great book, too sad I won't have a use for it in my current line of work. At work I found a memory leak in Javascript react-redux store, mutating const and other web horrors

[@packediceisthebestminecraf9007]

That mechanism probably doesn't have any visible effect here, because he's measuring everything from within the program itself it can only see the virtual addresses.

[@Excelsiur1]

I think this is the excerpt you're referring to from the book Understanding the Linux Kernel, Bovet and Cesati (2005): "...when the process dynamically requires memory by using malloc( ), or the brk( ) system call (which is invoked internally by malloc( )), the kernel just updates the size of the heap memory region of the process. A page frame is assigned to the process only when it generates an exception by trying to refer its virtual memory addresses." (p.11) You're right, it's basically saying that when we malloc() something, is just updating the heap but the page frame isn't actually handled until the kernel throws an exception. This is an effect from demand paging.

[@brianb9280]

this is so cool! I wonder if the allocator moving on is it basically saying that the metadata it has collected on the situation isn't worth the upkeep since there's a bunch of other memory it could use instead, so it just prioritizes speed. I'm no expert, though

[@tobiasbergkvist4520]

You can use a constructor attribute in front of a function for init-code (like loading symbols with dlopen/dlsym): __attribute__((constructor)) void init() { // initialization code } That way, you don't need the init-variable, or the init-check, as this code will run before the main-function/before dlopen returns if it is a shared library instead of an executable.

[@pxolqopt3597]

Probably out of the scope of this video.

[@chri-k]

@@pxolqopt3597 but still very useful to know.

[@AbhayKumar-xf8nz]

I tried to use std::cout in constructor attribute function but is resulting in a segmentation fault. I think the std::cout is getting instansiated after this attribute function call. Can we somehow use std::cout inside it? ``` #include __attribute__((constructor)) void init() { std::cout

[@Rsparing]

@@AbhayKumar-xf8nz you could use the write syscall

[@supernovaw39]

This is amazing! I've been programming in high-level languages and recently got curious with low-level stuff. Your videos are fueling more and more of my curiosity, it was really exciting to watch

[@Live_and_Let_Live6270]

I really love how you explain things with clarity. Can you please make a video about deadlocks on a real time situation? All I find is only the theoritical information.

[@Uerdue]

As for the "abandoning" of pages: Could this maybe have to do with optimizations regarding caching? You're never actually "using" / accessing the allocated blocks, so - unless freeing a block forces its corresponding memory page back into cache, which I'm not sure about - , old pages are gonna be pushed out of cache eventually. Could it be that the memory allocator "knows" about this (or at least anticipates it), and thus prefers to allocate new blocks on newer pages that it supposes to be still cached?

[@suncrafterspielt9479]

I would say it also has to do something with fragmentation and faster „free memory“ finding.

[@foomoo1088]

Very doubtful, the order things are allocated is not necessarily the order the processor with be reading/writing to them. The allocator has no knowledge of how your program will access it later. If you do know this yourself you can “help” make it cache happy by allocating a big contiguous buffer then placement new (C++) objects into it in the order the processor will use them. Similar approaches in C too of course.

[@maxaafbackname5562]

Nice animations! Maybe it detects somehow that there is a lot of fragmentation and tries to solve this by not using the part for awhile so the larger part of it is freed by the application?

[@Cwmwd24]

Why not use 'fprintf(..., "%p", ptr,...)' to output the pointer address to your log file?

[@maxaafbackname5562]

Maybe the integer value is easier to parse in the Ruby code?

[@Cwmwd24]

@@maxaafbackname5562 Fair comment, also %p is not that useful (or well known?) day-to-day unless something's not working in which case you break out the debug tool and not printf... maybe introducing %p here might detract from the main video objective?

[@arnoentz8320]

Hi, great video ! Analyzing the behaviour of malloc and free would be very interesting for me.

[@ChrisBNisbet]

"There's a pattern here - I'm doing things randomly". You're funny.

[@zeinfeimrelduulthaarn7028]

Great video, would love a dive into malloc code

[@tanchienhao]

The visualization was really cool!

[@sanderbos4243]

Really cool, thanks for the visualization!

[@claytonleonardcook]

Awesome video. I love when things are visualized like this, makes it so much more easier to comprehend. Hope to see more visualizations in the future!

[@anon_y_mousse]

Indeed, and this comment needs more upvotes.

[@konnosgar]

Very nice. I could leave this random allocation program for hours and just look at it!`

[@n0kodoko143]

What's an awesome idea, and great implementation!

[@idofrenkel7000]

Great video, thank you! Hope to see more visualization videos its very helpful for understanding 😀

[@anon_y_mousse]

Definitely makes this one to recommend.

[@sagivalia5041]

Is it probable that at an instant when the old page was almost full, the another process was scheduled, cleaning the cache and once the program was re-scheduled, an optimization similiar to memory allocation of vector had taken place?

[@jesselangham]

I'd love to dig into the various flavors of kernel allocators in future videos.

[@MisterFanwank]

Malloc isn't the only way to request memory. You can also use mmap, or similar syscalls, to do the same thing. Notably with mmap you can create allocators with unusual behaviors, like guarantees that you can grow in place up to X size.

[@JacobSorber]

True. I have videos on mmap (and maybe brk, too - don't remember) in case anyone is interested in how that works.

[@harrytsang1501]

I can tell you why you can find larger continuous chunks in the freed space without it being used, at least in Linux. For efficiency, the table for free and used spaces are only divided into sizes with power of 2, and each power of 2 has its own list. When it begins, only larger size chunks are present. If I asked for 10 bytes, it will look at the 16 byte table, if none, it take an entry from the 32 byte table, give one 16 byte block to malloc and keep the remaining 16 byte block in the table. If you free it and an adjacent same-sized block is also freed, it will merge and became a larger block. Now you can see how one seemingly continuous chunk of free memory can see so little use. It can be fragmented within the table which makes it appears to be many small and different sized chunks. And eventually the small chunk table would reach a size limit and it tries to find a new space to allocate altogether. It shouldn't happen frequently as you usually allocate and free a same-sized thing many times over so it just gives you back what you freed.

Awesome! The visualizations look very nice!

[@thomaswetmore7905]

I would love to see a short video on how you have your vscode editor set up.

[@zxuiji]

12:07, don't need a boolean for that, the pointer doubles as a boolean, just clear it after releasing it.

[@Eknoma]

Did you not watch at 10:45?

[@zxuiji]

@@Eknoma I did, doesn't change my answer, a boolean is only false if it is in the "0" state, in this case booleans and pointers both consider the value 0 to be invalid (unless you're in kernel land but that's a separate topic) so simply using the the pointer as a boolean instead of a separate value is sufficient in this example.

[@Eknoma]

@@zxuiji Yes, exactly what Jacob said at 10:45

[@zxuiji]

@@Eknoma Ah, I missed that statement

[@homelikebrick42]

@@zxuiji you can allocate block 0 using mmap in userland

[@Nick-ui9dr]

I think once I read about heap from Matt Patrick in MSDN article ...and he was so detailed up to the assembly code how compiler implement it in executables. I don't remember much now since it was yrs before... but remember his article about how compilers implement exceptional handling and malloc or new functions under the hood I guess. Only guy whose book I have ever brought in my life related to computers.... O yeah 2 more books.. One pentium microprocessor and micro controllers and some DoS assembly programming book. Good old Softice days! 😄

[@Redmat527]

Great video Jacob! I recently learned about the linker option --warp which seems more suited than using dlsym to redefine malloc ;) I think it could make an interesting video if you are willing to look into it

[@JacobSorber]

Good idea. Thanks.

[@jonashart7902]

How are you having multiple main functions running at the same time? Also how do you run terminal commands in code::blocks, or should i give up and use something else?

[@Shredcheddar]

Amazing idea and visualization. I subscribed for your C content but love a good viz program and would definitely like a video on your Ruby script. Are there any tools like this for tracking your C program's memory leaks as you use it?

[@只是約翰紐約市]

Could you please make a video about different sorting algorithms

[@leokiller123able]

To avoid the `if (!init)` check inside `initcheck` you could just do `static bool dummy = init_malloc(); (void)dummy;` inside the function body and call dlsym inside `init_malloc()` to set sysmalloc/sysfree

[@timothyhitge9189]

Are you still going to do a video on async networking and event driven systems?

[@adamvalt6609]

This was amazing!

[@JacobSorber]

Thanks. Glad you enjoyed it.

[@DenisovichDev]

That was really good Jacob!

[@MantisFootball]

Awesome vid. I was thinking of doing a memory alligator program that visualizes memory allocation/deallocation somehow involving an alligator. Maybe it eats the allocated memory to free it or something. Maybe visualize the allocated memory like in this video and reveal an image of an alligator. Or an animated alligator in ASCII art teaching with text bubbles. The visualization here reminded me of the game Arkanoid.

[@suncrafterspielt9479]

I would be very interested in the ruby script

[@karimdhrif6679]

Hey this was awesome as always, would love to see how you build that nice ruby script and how to convert it to C maybe using SDL?

[@Uerdue]

Ruby video would be great!

[@dogukan463]

Awesome video! Really enjoyed it.

[@WilliamRaezer]

The binary exploitation topics landed me here. It appears unlike the stack visualizations for heap calls are rare.

[@DanielFSmith]

In the past you could get some really interesting bugs if you neglected to fprintf a size_t with %zu (the video example used %lu). (There's a warning now, I think.)

[@EshmesVid]

Looks like the malloc abandoning areas is because speed optimizations. I think the reason could be fragmentation. Somebody measured it and found this better.

[@TehPwnerer]

20:20 Just a hunch but I think the allocator did that to defragment the heap

[@wake11223]

Sorry, but I don't get it. How can code in those test alocators(batchalloc...) see the modified malloc(), which is defined in a separate file(allocator.c)? 🤔

[@AlessioSangalli]

Because all modules are linked together!

[@nickhuynh6321]

Wonder if you can just skip initcheck() in free() since no one will do a free() until after malloc()? I suppose it's safer...

[@GegoXaren]

A warning is that you should probobly use PRIxPTR format macros instead of directly using "%ul", as it is more portabel. fprintf (fp, "M: " PRIuPTR ", " PRIuPTR " "); It seems that there is no RPIxSIZE, but it should be the same as PRIxPTR (In most cases). Though some standard library headers might have PRI[x]SIZE macros.

[@MisterFanwank]

Oh no, non-portable code! Anyway.

[@rasimbot]

Why did you put space between function name and round bracket in free definition?

[@anon_y_mousse]

We each have our individual styles. That's the beauty of C, it allows this.

[@rasimbot]

@@anon_y_mousse | Then why no space in the case of malloc?

[@anon_y_mousse]

@@rasimbot Like I said, style preference. Some people like to differentiate between a function pointer declaration and a function call.

[@adamodimattia]

Super video as always! But... Ruby? :)

[@rockom77]

These videos are great....at 0.75 Playback speed.

[@sync9827]

Hmmm... Maybe it's better for the hardware if it doesn't write to the same memory sections/pages all the time because, for example, writing heats up the hardware? Could this be an explenation for the abondoning of pages?

[@sync9827]

@250CC interesting!

[@viacheslav1392]

Hey Jacob, great video:) but are you sure that there are no allocations on 11:28 ?) You are using const int to declare array size for some reason, so it's VLA...

[@guilhermgonzaga]

It's not really VLA because the size is known at compile time. VLAs use a value produced in run time as the size.

[@salut730]

@@guilhermgonzaga No, the size variable is a const int, so he's right, this seems to be a VLA. Const ints are not know at compile time

[@milasudril]

some glibc implementations call malloc in printf

[@GangrelBrandao]

Yes... I'm stuck at that situation and I can't even use backtrace() because it uses malloc too.

[@skevin8440]

@@GangrelBrandao If you're interested I found a work around. I have a similar issue with GCC on UBUNTU and I managed to make it work using a static boolean as a guard when malloc or free are entered. Here's the code for allocator.c #define _GNU_SOURCE #include #include #include #include #include #include typedef void*(*malloc_like_function)(size_t size); typedef void(*free_like_function)(void *ptr); static malloc_like_function sys_malloc = NULL; static free_like_function sys_free = NULL; static bool inside = false; static FILE *fp = NULL; static const char *log_filename = "allocs.log"; void log_to_file(const char *fmt, ...) { if(!inside) { inside = true; va_list args; va_start(args, fmt); vfprintf(fp, fmt, args); va_end(args); inside = false; } } __attribute__((constructor)) static void init_check() { sys_malloc = (malloc_like_function)dlsym(RTLD_NEXT, "malloc"); sys_free = (free_like_function)dlsym(RTLD_NEXT, "free"); inside = true; fp = fopen(log_filename, "w"); inside = false; } __attribute__((destructor)) static void finalize_check() { inside = true; fclose(fp); inside = false; } void *malloc(size_t size) { void *ptr = sys_malloc(size); log_to_file("M: %lu, %lu ", (uintptr_t)ptr, size); return ptr; } void free(void *ptr) { log_to_file("F: %lu ", (uintptr_t)ptr); sys_free(ptr); }

[@zxuiji]

4:03, I normally just give such typdefs "_cb" as a suffix, so in this example it would be: typedef void* (*malloc_cb)( size_t size ); ... malloc_cb mallocCB;

[@sanderbos4243]

So what does _cb stand for?

[@25NN25]

cool beans

[@JacobSorber]

call back

[@zxuiji]

@@sanderbos4243 whoops, was l8 2 notice ur reply, jacobs given the answer already but I may as well explain why I chose that particular abreviation, it's pretty much a standard abreviation to programmers in general which on turn makes it unlikely to be misunderstood by programmers seeing it for the 1st time, basically one of those "self explanatory" type coding practices, it also reduces the need for documentation. Every now and then I feel some need for documentation so I'll slap a doxygen compatible comment in if possible, or at least expand a bit on what is expected of some parameters. My currently being programmed variants of sprintf etc are an example of the occasional docs needed, since they'll be directly part of my library and support binary output/input and intptr_t/uintptr_t via b & v specifiers respectively, along with an extra modifier for strings to declare minimum characters just as get with numbers AND a special specifier %! to indicate a list of functions for specifers is to be loaded instead of the current (which defaults to standarf modifiers) it is one such scenario where leaving it at pawPrintf is simply insufficient to fully grasp the details

[@anon_y_mousse]

@@zxuiji I've personally never been a fan of that style of typenaming. I prefer the old style Pascal method, so I'll name function pointers as FSomething, structured objects as TSomething, "hidden" pointer types as PSomething. To each their own.

[@luisgustavo.5449]

My guess would be that this migration is a wear leveling algorithm, to avoid creating bad blocks in the RAM due to excessive usage. When we use too much a block of RAM, it gets corrupted some time, aka. becoming a bad block. So the allocator needs to do its best not to use too much the same pages, because if we lose a page, we lose the entire block. I hope that I did not say something too incorrect.

[@AlessioSangalli]

DRAM does not work like that. It does not matter if the value is changed or not, it is continuously rewritten (refreshed) anyway.

[@UnderSiege72]

and what about if fopen calls malloc()?

[@anon_y_mousse]

A lot of implementations of a lot of standard library functions unfortunately do. I'd say, use one that doesn't if you can figure that out. Or if you have the time and ability, write your own libc. If you're just starting out it can be a fun learning experience. Especially all of the string.h functions. My personal favorite is strtok(), though I'm rather partial to strstr().

[@ansismaleckis1296]

cool stuff, I just don't get why do ~8min intro doing gymnastics of wrapping malloc/free.

[@AlessioSangalli]

It's most interesting

[@MellexLabs]

Very cool 😎

[@subnumeric]

It seems KZbin has been toying with the video encoding settings again. Your IDE looks super blocky. Shame, because it's a really good video otherwise...

[@ttt69420]

I still don't know the difference between heap and stack.

[@telisijohn2054]

I was hoping to see a diagram depicting how maloc, free, heap and stack pointers work in conjunction with how the coding work flow works. Instead, all I see is a high level of coding logics. This doesn't help a person like me who wants to understand the logic behind maloc, heap and etc work in writing code.

[@zxuiji]

I would hazard a guess that the page abandonment is due to a combination of speed of new allocations & clearing up fragmentation, for the fragmentation I would hazard a guess the reason is length of time available memory remains unused, something like: for ( ... ) { ... page->time_since_search_succeeded = 0; page->last_allocation_time = time(NULL); return addr; } page->time_since_search_succeed = time(NULL) - page->last_allocation_time; if ( page->time_since_search_succeeded >= TIME_TO_ABANDON_PAGE ) { ... }

[@burningglory2373]

To bad I work with pics that only have about 8k of ram.

[@nordgaren2358]

Just a guess, but maybe the allocator decided that it was too much of a pain to keep re-using those blocks and moved to a fresh block, since it was available? I know this sounds obvious, but that's what my guess would be. Maybe there's also some cpu magic involved here, too? Like branch prediction?

[@44r0n-9]

Good video, though I was a little disappointed that it didn't really go into Operating System and Syscall specifics, like what malloc actually does on a lower level.

[@lukakvavilashvili]

Same! I was expecting this video to dive into how malloc doesn't actually allocate 25 bytes but a whole page, syscalls like sbrk or mmap, and the internal mechanism to manage memory (like a buddy system). This was still very cool though!

[@YoTengoUnLCD]

He already has videos on that.

[@__hannibaal__]

Pointer in the First reason why i hate all ( and all) other programming languages (except ASM), Seconds because its made by mathematicians, and not CS.

[@Vulto166]

This is why i pay for internet!

[@rustycherkas8229]

@20:18... With the excellent visualisation, it's unfortunate that the video ended with that question. Is that "abandoned" section of heap ever re-used if the 'random' program runs longer? If not, then this would be a memory leak... Also, a good reason to not use malloc in an embedded app.

[@44r0n-9]

That's not necessarily true because you can unmap heap pages using munmap, and malloc COULD be doing that.

[@rustycherkas8229]

@@44r0n-9 I don't pretend to know malloc's "page size", but I envision a program similar to Jacob's 'random' that happens to leave (use) myriad tiny blocks, some being long-lived... A number of immortal 10 byte blocks may force malloc to hang onto many perhaps 4K pages just to preserve one or two of these tiny un-free'd regions. It would be good to understand what is causing this behaviour. It's all just bytes, but the video shows malloc seems to give up on recycling low addresses.

[@44r0n-9]

@@rustycherkas8229 I completely agree. Just pointing out that it's technically possible to free the page so that it isn't lost :D

[@diamondtroller1253]

What's up with that weird audio mixing? A bit hard to understand you.

[@NunoFidalgo]

😲🤤

[@psionl0]

As interesting as your visual demonstration was, I must say that I found the original descriptions of malloc and free by Kernighan and Ritchie easier to follow.

[@AlessioSangalli]

What do you mean? The C language does not specify a memory model

[@psionl0]

@@AlessioSangalli Look at K&R for yourself. You will see that malloc() and free() work on blocks of memory that have been requested from the OS. You can even request more memory from the OS if you run out (the blocks don't need to be contiguous).

[@dcorderoch]

I'm not sure if it's a problem with the version of the compiler I'm using, but I had to add some includes, add a #define _GNU_SOURCE in allocator.c to get the code compiling, and even with that, I got segmentation faults when allocating memory

[@skevin8440]

Hi, great content as always. I have a problem with my glibc implementation, because it calls malloc and free inside printf and similar functions. I found a workaround using a boolean to print to file only the first time you enter into malloc or free. Hope it can be useful for anyone with similar issue. #define _GNU_SOURCE #include #include #include #include #include #include typedef void*(*malloc_like_function)(size_t size); typedef void(*free_like_function)(void *ptr); static malloc_like_function sys_malloc = NULL; static free_like_function sys_free = NULL; static bool inside = false; static FILE *fp = NULL; static const char *log_filename = "allocs.log"; void log_to_file(const char *fmt, ...) { if(!inside) { inside = true; va_list args; va_start(args, fmt); vfprintf(fp, fmt, args); va_end(args); inside = false; } } __attribute__((constructor)) static void init_check() { sys_malloc = (malloc_like_function)dlsym(RTLD_NEXT, "malloc"); sys_free = (free_like_function)dlsym(RTLD_NEXT, "free"); inside = true; fp = fopen(log_filename, "w"); inside = false; } __attribute__((destructor)) static void finalize_check() { inside = true; fclose(fp); inside = false; } void *malloc(size_t size) { void *ptr = sys_malloc(size); log_to_file("M: %lu, %lu ", (uintptr_t)ptr, size); return ptr; } void free(void *ptr) { log_to_file("F: %lu ", (uintptr_t)ptr); sys_free(ptr); }