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.
@rickwightman23662 жыл бұрын
"Oops, I have some warnings. I should fix them." A sure sign that someone is worth listening to.
@AlejandroAnzolaAvila2 жыл бұрын
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.
@Excelsiur12 ай бұрын
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.
@tobiasbergkvist45202 жыл бұрын
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.
@pxolqopt35972 жыл бұрын
Probably out of the scope of this video.
@chri-k2 жыл бұрын
@@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
@Rsparing16 күн бұрын
@@AbhayKumar-xf8nz you could use the write syscall
@brianb92802 жыл бұрын
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
@Live_and_Let_Live62702 жыл бұрын
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.
@claytonleonardcook2 жыл бұрын
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_mousse2 жыл бұрын
Indeed, and this comment needs more upvotes.
@arnoentz83202 жыл бұрын
Hi, great video ! Analyzing the behaviour of malloc and free would be very interesting for me.
@ChrisBNisbet2 жыл бұрын
"There's a pattern here - I'm doing things randomly". You're funny.
@zeinfeimrelduulthaarn70282 жыл бұрын
Great video, would love a dive into malloc code
@maxaafbackname55622 жыл бұрын
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?
@tanchienhao11 ай бұрын
The visualization was really cool!
@Uerdue2 жыл бұрын
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?
@suncrafterspielt94792 жыл бұрын
I would say it also has to do something with fragmentation and faster „free memory“ finding.
@foomoo10882 жыл бұрын
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.
@idofrenkel70002 жыл бұрын
Great video, thank you! Hope to see more visualization videos its very helpful for understanding 😀
@anon_y_mousse2 жыл бұрын
Definitely makes this one to recommend.
@konnosgar10 ай бұрын
Very nice. I could leave this random allocation program for hours and just look at it!`
@Cwmwd242 жыл бұрын
Why not use 'fprintf(..., "%p", ptr,...)' to output the pointer address to your log file?
@maxaafbackname55622 жыл бұрын
Maybe the integer value is easier to parse in the Ruby code?
@Cwmwd242 жыл бұрын
@@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?
@jesselangham2 жыл бұрын
I'd love to dig into the various flavors of kernel allocators in future videos.
@sanderbos42432 жыл бұрын
Really cool, thanks for the visualization!
@thomaswetmore7905 Жыл бұрын
I would love to see a short video on how you have your vscode editor set up.
@leokiller123able2 жыл бұрын
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
@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.
@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! 😄
@mantisfootball9184 ай бұрын
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.
@Redmat5272 жыл бұрын
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
@JacobSorber2 жыл бұрын
Good idea. Thanks.
@sagivalia50412 жыл бұрын
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?
@zxuiji2 жыл бұрын
12:07, don't need a boolean for that, the pointer doubles as a boolean, just clear it after releasing it.
@Eknoma2 жыл бұрын
Did you not watch at 10:45?
@zxuiji2 жыл бұрын
@@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.
@Eknoma2 жыл бұрын
@@zxuiji Yes, exactly what Jacob said at 10:45
@zxuiji2 жыл бұрын
@@Eknoma Ah, I missed that statement
@homelikebrick422 жыл бұрын
@@zxuiji you can allocate block 0 using mmap in userland
@user-de4mr7uk8d2 жыл бұрын
Could you please make a video about different sorting algorithms
@user-it8yh8tu7dАй бұрын
The binary exploitation topics landed me here. It appears unlike the stack visualizations for heap calls are rare.
@Shredcheddar6 ай бұрын
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?
2 жыл бұрын
Awesome! The visualizations look very nice!
@n0kodoko143 Жыл бұрын
What's an awesome idea, and great implementation!
@adamvalt66092 жыл бұрын
This was amazing!
@JacobSorber2 жыл бұрын
Thanks. Glad you enjoyed it.
@Uerdue2 жыл бұрын
Ruby video would be great!
@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.
@DenisovichDev2 жыл бұрын
That was really good Jacob!
@dogukan4632 жыл бұрын
Awesome video! Really enjoyed it.
@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?
@suncrafterspielt94792 жыл бұрын
I would be very interested in the ruby script
@DanielFSmith2 жыл бұрын
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.)
@zxuiji2 жыл бұрын
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;
@sanderbos42432 жыл бұрын
So what does _cb stand for?
@25NN252 жыл бұрын
cool beans
@JacobSorber2 жыл бұрын
call back
@zxuiji2 жыл бұрын
@@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_mousse2 жыл бұрын
@@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.
@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.
@timothyhitge91892 жыл бұрын
Are you still going to do a video on async networking and event driven systems?
@adamodimattia2 жыл бұрын
Super video as always! But... Ruby? :)
@TehPwnerer Жыл бұрын
20:20 Just a hunch but I think the allocator did that to defragment the heap
@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?
@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...
@UnderSiege722 жыл бұрын
and what about if fopen calls malloc()?
@anon_y_mousse2 жыл бұрын
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().
@milasudril2 жыл бұрын
some glibc implementations call malloc in printf
@GangrelBrandao2 жыл бұрын
Yes... I'm stuck at that situation and I can't even use backtrace() because it uses malloc too.
@skevin84402 жыл бұрын
@@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); }
@GegoXaren2 жыл бұрын
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.
@rasimbot2 жыл бұрын
Why did you put space between function name and round bracket in free definition?
@anon_y_mousse2 жыл бұрын
We each have our individual styles. That's the beauty of C, it allows this.
@rasimbot2 жыл бұрын
@@anon_y_mousse | Then why no space in the case of malloc?
@anon_y_mousse2 жыл бұрын
@@rasimbot Like I said, style preference. Some people like to differentiate between a function pointer declaration and a function call.
@44r0n-92 жыл бұрын
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.
@lukakvavilashvili2 жыл бұрын
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!
@YoTengoUnLCD2 жыл бұрын
He already has videos on that.
@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!
@sync98272 жыл бұрын
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?
@sync98272 жыл бұрын
@250CC interesting!
@ansismaleckis1296 Жыл бұрын
cool stuff, I just don't get why do ~8min intro doing gymnastics of wrapping malloc/free.
@AlessioSangalli Жыл бұрын
It's most interesting
@rockom772 жыл бұрын
These videos are great....at 0.75 Playback speed.
@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.
@subnumeric2 жыл бұрын
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...
@viacheslav13922 жыл бұрын
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...
@guilhermgonzaga2 жыл бұрын
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
@MellexLabs2 жыл бұрын
Very cool 😎
@zxuiji2 жыл бұрын
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 ) { ... }
@burningglory23732 жыл бұрын
To bad I work with pics that only have about 8k of ram.
@rustycherkas82292 жыл бұрын
@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-92 жыл бұрын
That's not necessarily true because you can unmap heap pages using munmap, and malloc COULD be doing that.
@rustycherkas82292 жыл бұрын
@@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-92 жыл бұрын
@@rustycherkas8229 I completely agree. Just pointing out that it's technically possible to free the page so that it isn't lost :D
@telisijohn20542 жыл бұрын
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.
@nordgaren23582 жыл бұрын
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?
@psionl02 жыл бұрын
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).
@diamondtroller12532 жыл бұрын
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.
@Vulto1662 жыл бұрын
This is why i pay for internet!
@NunoFidalgo2 жыл бұрын
😲🤤
@dcorderoch2 жыл бұрын
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
@skevin84402 жыл бұрын
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); }