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.
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.
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
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.
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.
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.
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
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
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
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.
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?
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?
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 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?
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
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.
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
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.
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?
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?
@@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.
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! 😄
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.
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.)
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?
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().
Looks like the malloc abandoning areas is because speed optimizations. I think the reason could be fragmentation. Somebody measured it and found this better.
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 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
@@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.
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)? 🤔
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.
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...
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?
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.
It seems RU-vid has been toying with the video encoding settings again. Your IDE looks super blocky. Shame, because it's a really good video otherwise...
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.
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!
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 ) { ... }
@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 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.
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.
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?
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.
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 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).
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