Pulling Back the Curtain on the Heap

Рет қаралды 36,576

Күн бұрын

Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
Pulling Back the Curtain on the Heap // The heap is pretty mysterious for most programmers - at least for beginners. In this video, we're going to see what the heap actually looks like, by replacing our allocator to record our activities and then draw what happens.
Related Videos:
Malloc, calloc, realloc, and free: • Allocating memory with...
Allocator videos:
• One reason to Modify y...
• Memory Allocator Error...
***
Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.
About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.
More about me and what I do:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]

Пікірлер: 120

@Jonathan-di1pb 2 жыл бұрын

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 2 жыл бұрын

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

@AlejandroAnzolaAvila 2 жыл бұрын

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.

@tobiasbergkvist4520 2 жыл бұрын

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 2 жыл бұрын

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

@brianb9280 2 жыл бұрын

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

@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

@ChrisBNisbet 2 жыл бұрын

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

@vidhyanandini6270 2 жыл бұрын

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.

@sanderbos4243 2 жыл бұрын

Really cool, thanks for the visualization!

@tanchienhao 10 ай бұрын

The visualization was really cool!

Жыл бұрын

Awesome! The visualizations look very nice!

@n0kodoko143 Жыл бұрын

What's an awesome idea, and great implementation!

@dogukan463 2 жыл бұрын

Awesome video! Really enjoyed it.

@DenisovichDev 2 жыл бұрын

That was really good Jacob!

@claytonleonardcook 2 жыл бұрын

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 2 жыл бұрын

Indeed, and this comment needs more upvotes.

@arnoentz8320 2 жыл бұрын

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

@idofrenkel7000 2 жыл бұрын

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

@anon_y_mousse 2 жыл бұрын

Definitely makes this one to recommend.

@zeinfeimrelduulthaarn7028 2 жыл бұрын

Great video, would love a dive into malloc code

@maxaafbackname5562 2 жыл бұрын

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?

@Uerdue 2 жыл бұрын

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 2 жыл бұрын

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.

@Cwmwd24 2 жыл бұрын

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

@maxaafbackname5562 2 жыл бұрын

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

@Cwmwd24 2 жыл бұрын

@@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?

@konnosgar 9 ай бұрын

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

@jesselangham 2 жыл бұрын

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

@adamvalt6609 2 жыл бұрын

This was amazing!

@JacobSorber 2 жыл бұрын

Thanks. Glad you enjoyed it.

@Shredcheddar 5 ай бұрын

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?

@thomaswetmore7905 10 ай бұрын

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

@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?

@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?

@Redmat527 2 жыл бұрын

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 2 жыл бұрын

Good idea. Thanks.

@timothyhitge9189 2 жыл бұрын

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

@leokiller123able 2 жыл бұрын

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

@suncrafterspielt9479 2 жыл бұрын

I would be very interested in the ruby script

@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! 😄

@mantisfootball918 2 ай бұрын

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.

@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.

@Uerdue 2 жыл бұрын

Ruby video would be great!

@MellexLabs 2 жыл бұрын

Very cool 😎

@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?

@user-it8yh8tu7d 15 күн бұрын

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

@user-de4mr7uk8d 2 жыл бұрын

Could you please make a video about different sorting algorithms

@sync9827 2 жыл бұрын

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 2 жыл бұрын

@250CC interesting!

@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.

@viacheslav1392 2 жыл бұрын

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 2 жыл бұрын

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

@DanielFSmith 2 жыл бұрын

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.)

@adamodimattia Жыл бұрын

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

@zxuiji 2 жыл бұрын

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

@Eknoma 2 жыл бұрын

Did you not watch at 10:45?

@zxuiji 2 жыл бұрын

@@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 2 жыл бұрын

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

@zxuiji 2 жыл бұрын

@@Eknoma Ah, I missed that statement

@homelikebrick42 2 жыл бұрын

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

@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...

@UnderSiege72 2 жыл бұрын

and what about if fopen calls malloc()?

@anon_y_mousse 2 жыл бұрын

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().

@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!

@rasimbot 2 жыл бұрын

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

@anon_y_mousse 2 жыл бұрын

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

@rasimbot 2 жыл бұрын

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

@anon_y_mousse 2 жыл бұрын

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

@zxuiji 2 жыл бұрын

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 2 жыл бұрын

So what does _cb stand for?

@25NN25 2 жыл бұрын

cool beans

@JacobSorber 2 жыл бұрын

call back

@zxuiji 2 жыл бұрын

@@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 2 жыл бұрын

@@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.

@GegoXaren 2 жыл бұрын

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.

@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.

@milasudril 2 жыл бұрын

some glibc implementations call malloc in printf

@GangrelBrandao 2 жыл бұрын

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); }

@TehPwnerer Жыл бұрын

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

@ansismaleckis1296 Жыл бұрын

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

@AlessioSangalli Жыл бұрын

It's most interesting

@rockom77 2 жыл бұрын

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

@zxuiji 2 жыл бұрын

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 ) { ... }

@rustycherkas8229 2 жыл бұрын

@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 2 жыл бұрын

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

@rustycherkas8229 2 жыл бұрын

@@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 2 жыл бұрын

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

@44r0n-9 2 жыл бұрын

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 2 жыл бұрын

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 2 жыл бұрын

He already has videos on that.

@subnumeric 2 жыл бұрын

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

@nordgaren2358 2 жыл бұрын

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?

@telisijohn2054 2 жыл бұрын

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.

@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.

@burningglory2373 2 жыл бұрын

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

@psionl0 2 жыл бұрын

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).

@NunoFidalgo 2 жыл бұрын

😲🤤

@diamondtroller1253 2 жыл бұрын

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

@__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 2 жыл бұрын

This is why i pay for internet!

@dcorderoch 2 жыл бұрын

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); }