Very interesting; I learned a lot about how memory allocation works today

Блин чувак, это божественный канал - спасибо за творчество, хороший звук и подачу. Давненько стримы по программированию искал, так тут еще и понятный, родной акцент :)

You're the best youtuber I've found providing interesting content that's actually useful and helps people learn new things.

Quick note on fixed sized chunk allocators (or pool allocators), you don't need an additional array to hold the reusable old chunks. You can just hold a pointer to the last freed chunk, and use that "free" memory space to keep a pointer in that chunk to the next one (and so on). They then form a single-linked list containing all re-usable chunks, and you can easily add or remove from the head of the list. Then you just return the head of the list and shorten it by one, or allocate a brand new chunk if the list is empty. All operations should remain O(1), and the only memory cost is 1 pointer for the head of the list.

46:08 "production-ready" allocators store the metadata within the chunks themselves-the size of the chunk, the state of the chunk (in case needed by garbage collection), a pointer to the next chunk, ...etc. I think this kind of list is known as an "intrusive list" or an "embedded list". if you're wondering, you can take a look at GCC's implementation of dynamic allocation of memory. it uses binning where you have bins and each bin has chunks of a certain size (restricted by the bin) and chunks store the metadata using "boundaries", and there are two boundaries, one at the end of the chunk and one at the beginning. it is pretty interesting!

bsearch was work correct. The bug was in the return result. You shouldn't have divided the pointer difference by the chunk size.

Very interesting, thanks for sharing!

I wrote my own malloc implementation some time ago. My approach was to make linked lists with a next and "up" pointer, a member specifying whether the memory is free, and the amount of memory "managed" by the node. Memory is obtained by sbrk, mmap or malloc (redundant lol) depending on compile flags, but the default is sbrk(n), which extends the program's data segment by n bytes. A left/right list represents contiguous memory, while up/down are separate calls to sbrk and are therefore not guaranteed to be contiguous. At first, a small block (4KiB IIRC) is allocated for the first row, so the size of the memory being managed is 4096 - sizeof (struct memnode). When a memory request is made, we go up the list from the bottom, left to right, bottom to top, to find the first contiguous chunk of memory that can satisfy the request when the bookkeeping node is factored in. So if a request for 10 bytes is made, then there must be 10 + sizeof (struct memnode) bytes available. If so, then the list is bisected. The first node has its size reduced, and after the last byte of its owned memory, a node is made out of the "difference", then the first node is returned and marked as not free. Memory is obtained by adding memnode size, the bookkeeping node is obtained from a pointer in the free function by subtracting memnode size. If enough memory cannot be found before running into the null pointer, then the list head's up pointer is checked. If it's not null, then the same process continues there and so on until either enough free memory is found or a null pointer is reached in the up list. If all lists are exhausted, then a new pool is made with exactly enough memory to satisfy the request and pushed to the top of the uplist. For freeing, and this is perhaps not the most efficient algorithm, it goes over the whole list starting from the top of the uplist, merges adjacent free nodes, and if head->next == NULL and head->isfree is true, then sbrk is called again to return it to the OS. Since the top of the list is always the most recently allocated, this is safe as long as this malloc is the only malloc that's been used. IIRC the bottom of the list is a static char array rather than something obtained from the heap as a small optimization, so before free calls the deallocator function, it makes sure the node being freed doesn't have the same address as the head of the bottom of the up list. Memory is re-used bottom-up as it becomes available, although as always, fragmentation is an unavoidable issue. Writing my implementation taught me that syscall overhead isn't the only reason not to be loosey goosey with heap allocation. The other issue is that being all over the place with heap allocations will create fragmentation no matter what implementation of malloc you use, resulting in potentially inefficient memory usage. So that's how my implementation works. A circular linked list would have probably worked, although to be completely safe, there'd have to be calls to sbrk(0) and comparisons between pools and their addresses/sizes to sanity check that they really are contiguous and that something else hasn't called sbrk in the interim. As I was writing this, it occurred to me that a next pointer is not even necessary, since the whole list is contiguous. Just add the size of the memory pool to get the location of the next node. I guess that's why they call it a heap, eh? 2n+0 2n+1. Doing this would eliminate the null pointer so the total size of the heap would also have to be tracked. Something like struct memnode { size_t size; uint8_t flags; }; static char *pool; static size_t poolsize; struct memnode * memnode_next(struct memnode *node) { void *ptr = node; size_t limit = poolsize - (ptr - pool) ptr += sizeof *node + node->size; if (ptr - node > limit) return NULL; return ptr; } It'll be interesting to see how someone else does it.

Nice one! I don't know if this was already mentioned, but the chunk information is usually saved in the beginning of the allocated chunk. In other words, you always allocate the required size + the size of chunk info structure. That's why you always get unique pointer back even if you allocate 0 length chunk. This approach has multiple benefits in term of performance (less redirections) and reduced memory footstep for the heap management.

Awesome!!! The memory manager is an important thing that often requires customization depending on the specifics of the project. You can't trust the compiler everything.

Wrote this as a system design course assignment. Pain in the ass.

All metadata about allocated and free block stuff is kept inside a block in the same heap. You don't need separate memory to track this information. You just alloc block info + size data and put block info data, then return mem + sizeof(block info) pointer back to the app. The free list requires only the head pointer to the first free block, and all free blocks chained in a singly linked list where you store next pointer in a block info.

A few times i was thinking "no don't do it that way, that'll cause a problem later" and then you get to that point and everything you've set up perfectly solves the problem i was thinking about. It's like well told story

These kinds of exercises is why I’m finding that I’m getting better at understanding C and how the computer operates at a fundamental level!!

This is the only video that has a clickbaity title, but then the content is even more extreme than the title

This video inspired me to get back to C and unmanaged languages in general. A different approach to the problem that, in my opinion, results in simpler code would be to have only one chunk list, and add a "state" variable to Chunk. It's type would be an enumeration, ChunkState with 2 possible values : CHK_FREE and CHK_ALLOCATED. That way, you don't have to perpetually move chunks across lists.

i regularly use a memory pool class i made. has dynamic width blocks and chunks, a partition table, automatic defrag, supplies smart pointers, garbage collection, and more. one of the most useful things ive ever made. can use it on every project for fast memory access and no worries about clean up. definitely recommend using one

Hey! Initially, you mentioned that you've previously done videos on fixed size chunk allocators. Could you please share the link to that video? It would be really helpful to me.

there could be bool value in the struct indicating whether u are using that chunk or not

what program do you use for coloring the man pages?

Very good presentation, very informative.

Isn’t the 0 size basically just padding? Cos Malloc ensures that an allocation is 64 bit aligned. So i would assume that allocating something of zero size is just making a size_t allocation?

what are the benefits of using sizeof(list->chunks[0]) instead of sizeof(Chunk) at 1:12:05?

that asmr in the beginning 🥴

I've always wanted to learn C, you're my hero

enjoying watch your videos, keep on that great.

Awesome video!!! Thanks :)

someone that know programming, why I cant start the for iteration of the main function of the minute 31(aprox) with int i = 1; why I need to start with i = 0; because I saw that the only repetead memory is in the first two iteration with i = 0; and i = 1; after that works properly. Thanks in advance. And thanks you mr Tsoding with you this journey of programming will be more enjoyable, I hope soon could follow your ideas in pforth, I speend some time learning forth and I love it, that combination with python im sure is very cool

dude, knowing this stuff after studying it super hard, and seeing him basically derive everything with a few minutes of thought is crazy. Like how he figured out that the free function should merge the consecutive free slots, without even having encountered an error at all

dont have time to finish to video but im curious to see how things accessed outside of heap are unreacxhable

"helloow" *oh, nice, this will be a relaxed asrm tutorial "*procede to write at lightning fast speed*" oh shit...

By the time I get my code to 1:33:50, I’m getting print out of size 0 and then “Index is 0” 4 times. Why?

This is a memory pool. I had to implement this sort of thing over a decade ago, where I had to have a hybrid of uniform chunks pools and variable size chunks. Management was a real b!tch, but it was worth the hassle, especially for the relative speed of allocation and the garbage collection at shutdown. Because the code is rather involved, I would never even think to try to do a KZfaq video on it. You're a brave man😁

if you werent allowed to use static local variables and global variables how would you change this ?

In chunk_list_find, you should replace `(result - list->chunks) / sizeof(list->chunks[0])` just with `result - list->chunks`

A personal custom made foot gun

640K should be enogh for everyone. video started with a meme.

About that "freed" or "freeed" question, we somehow have this in french. The verb "to create" => "créer", in feminine form (we generally add another e) => "créée". It's uncommonly used but it exists and is grammatically correct. Generally people just write "crée" which confuses everything, but we're used to being confused :)

Your malloc should return aligned addresses, and of course the chunk metadata is inline on the heap (which solves your size0 problem)

Ah throwback to "Intro to OS" cs mod. We had to compare using bitmaps and linked lists to track metadata for our alloc and free. Also different strategies for searching, like best first, worst first, best after previous, etc. I think linked lists are great for large heaps with big chunks but becomes overkill for small chunks since the bitmap is heap_size/8(chunk_size)

I love you man. Please never stop being yourself

Showing an implementation using free-list allocation would be easier and more practical.

I know I'm late to this video, but can anyone help me understand line 3 in heap_alloc at 15:24? I don't get what happens when you add a char array to a size_t.

A semester's worth of learning in one video. -:) Thank you How many fingers do you have for typing. lol

xor copying is efficient in processors that don't necessarily have a spare register for swapping... but I doubt if that was the case you would want to be using linked lists anyway....

nice uh... folder. PepeHands

Another good solution instead of the "Heap_Chunk" array would be to litteraly fill the start of allocated chunks with the structure (which would also accept pointer to next chunk, at least), and return to the user the pointer to the rest of the chunk (the end of the structure). Maybe you did this actually, but I'm still at the beginning of the video lol

I want to say thank you. I have known about low level programming because of you. I am going to keep watching your video. I have a question. Is there a video about your development settings?

very cool

Well, real malloc is not done like this of course. It uses Linux system calls like sbrk (if you read its description, it's very much like malloc) and on the first call creates a structure of linked free memory blocks which it uses to search for free memory (a great example of malloc implementation is given in the last section of K&R where each block has a Header structure which contains a pointer to the next free block(its header) and the size of this block in bytes)

well done

Funny that my homework at uni is to implement malloc, calloc, realloc, free , mmap and more and then this vid pooped into my recommended.

26 mins into the video and i am LOST!!!!

Those 9.1Gb 🤣🤣

12:07 my motivation!!!

Bro uses calender in terminal

*12:30 in fact I'd argue you cant. Any working, complex system evolved from a simple, working system

I’m wayyy too high for this right now.

This question was asked in Qualcomm, Not able to do this. I sucked 😥😥

Having no fragmented heap is not sus at all: When you deallocate a chunk right after allocating it, but before you allocate the next, the small freed chunk at the end of the chain will be merged with the rest of the heap before allocating the new element. So you reclaim pretty much all freed chunks just in time for the new allocate. Hence no fragmentation. Edit: Ok, you found it out on your own. ;) It was obvious for me from the start. I should be patient and finish watching the video. Cool video. I have been looking to create something similar for a virtual machine, but I cheated and used malloc for the time being.

Great

0:47 I see what you did there

isn't memory alignment necessary here? 30:00

Perhaps a really stupid question that probably boils down to stylistic choices, but for heap_alloc I'm guessing it would be just as efficient in terms of the machine code produced to do if(condition){do stuff} else{return NULL;} as it would be to do if(condition){return NULL;} // do stuff ?

come to brazil, big fan here

Is this data really going to heap, or some other space?

Meowy uwu I'm ill rn and that surprisingly is some great, most importantly long content to watch while I'm dying xd

Shoulda started off using linked list(s) (integrated into your 'heap'). Fixed size arrays of "metadata" are no more than guesstimates. Not everything is a char... Blocks must be allocated aligned to the machine's 'native' 'word' size (to accommodate buffers containing multibyte datatypes.) The user may only want 1 byte now, but the next 'alloc()' will likely ask for a "void **" or a "float"... 'Sign' each block (with a constant, perhaps its own address), and validate while traversing the list(s) to detect the caller's buffer overruns a.s.a.p. You appear to "add more code and arrays" trying to facilitate a bad premise... Yes, theory and O(log n) is wonderful conceptually, but things will take what they take. Adding another layer of processing toward ameliorating a bad start is NOT the solution.

What does CFLAGS mean

Is that legal?

font?

bruh the folder name is crazy

Better use mimalloc, jemalloc or TCMalloc. They all basically work the same and coudn't been easily beaten without chosing the same basic principles.

1:01:08

isn't this what virtual machine like JVM does?

кайф для мозга

Why does he have a porn folder of 9.1 gig showing on the screen.Is that supposed to be a practical joke?

Maria

tu eh mt pika

1:44:17 okay

Beta programmers: Nooo!! Don’t write your own Malloc It’s not worth it!!!! Chad programmers: I must write my own Malloc so that I may understand how and why Malloc works.

Deusdedit

freed's feed and seed (sorry)

I guess you used binary search but never sorted the list first?

Have you tried making a stop and copy garbage collector yet? it's pretty simple

Pfffffff.......BLOATED ! void* custom_alloc(size_t size) { srand(time(NULL)); // Seed the random number generator every alloc for security purpose return (void*)(rand() % 0xFFFFFFFF); // Return a random pointer } void custom_free(void* ptr) { // For simplicity, do nothing }

1:28:40 wtf lmao

у тебя очень сильный акцент :)

Get a pop filter for the mouth noises please

why not just do #define unused __attribute__((unused)) void func(unused int a) { //...body } instead of (void) var; ??

Starts at 14:20

640,000 bytes = 625KB, not 640KB. Powers of two.... 1024 bytes in a KB.

Nnnnope. I've been coding in C for over 3 decades but have never had a need for an XOR linked list. I always need random access which precludes XOR lists which require the head for every access.