Actual (m)alloc Implementation?

[dsguy]

First of all, I want to thank everyone responsible for creating this wonderful project-based course as well as everyone involved in the forum, it has been tremendously helpful and was by far the most fruitful educational experience I ever had the pleasure of experiencing.

With N2T being wrapped up, I still have some questions about Ch12. Within Ch12, the Memory module has been the most interesting to me and it made a lot things click. It had me wondering, though: How is C's malloc or C++'s new (if I'm not completely mistaken - I know virtually nothing about either of those languages) actually implemented?

In the grand scheme of things, since basically every modern OS is written in either of those two, I would assume that the implementation is actually quite similar to how alloc is implemented in Jack. Then again, a modern computer does not have a fixed RAM as we do here and there's lots of different layers, so the access is likely not as straight-forward.

My research indicates that the basic idea of the free linked list is the same, however how does the actual access take place? Is there something similar to the ingenious "Array ram = 0" hack taking place in malloc? It seems almost too simple (and the language feature way too weak) to believe this could be a valid real life implementation. But then again - as I said - I know nothing about C, C++ or their compilers.

Does anyone know how it actually works (simplified) on Windows/Linux/MacOS?

Thanks!

[WBahn]

How memory management works in a program written in C and how it works at the operating system level (even one written in C) are very different things.

When you write a program in C and run it (on most modern operating systems), that program is given a block of memory by the OS when it is loaded and it can do anything with that block of memory it wants to and the OS doesn't care. If it attempts to access memory outside of that block, the CPU will detect that and throw and exception, at which point the OS will usually kill the program with something like a memory sharing or segmentation fault exception.

If your program uses dynamic memory allocation, the compiler will include a memory manager in your program (or, more likely, it will be dynamically linked from a shared library (a DLL) with a data structure that is incorporated into your program). The details of how that memory manager works is up to the compiler and/or whoever wrote the DLL. When and how the memory manager interacts with the OS is also a detail that is up to whomever write it and depends on the services offered by the OS and whether the implementer chooses to use them.

So there's a wide range of options available and the approach taken depends on a number of factors, such as how much memory is available in the first place (the memory management functions need some amount of memory for their own use, so on memory-constrained platforms a lighter-weight memory manager might be chosen even if it's performance suffers as a result), how much excess processing capacity the CPU is expected to have (the memory management functions need some amount of CPU cycles to do their work, so on CPU-constrained platforms a lighter-weight manager might be chosen even it it's performance suffers). If neither of these are the case, then a more capable memory-management system is an option, but may not be needed. In programs that do a lot of allocation and deallocation, such that running out of memory is a concern, then a heavier memory manager can do a better job of optimally allocating memory and defragmenting released memory, at the cost of more memory and CPU cycles used by the manager).

The data structure used by the memory manager to keep track of what memory is allocated and where free memory can be found is going to reflect these choices.

[pm100]

Simple thing to start with

>>Is there something similar to the ingenious "Array ram = 0" hack taking place in malloc?

C has pointers so it does not need a hack like that. You can simply do

char * ram_base = 0;

You want access to location 42?

char x = ram_base[42];

Now the main question.

All mallocs work in the same way roughly. They have a chunk of memory they get from the base OS, on linux historically obtained via a call to sbrk, while the program is being started.

The mallocs then chop that memory up and hand bits out to callers. Different malloc implementations use more of less sophisticated algorithms. If you want to read about them a good place to start is here https://en.wikipedia.org/wiki/C_dynamic_memory_allocation scroll down to the section called 'implementations'

Note also that you are getting dangerously close to disappearing down another rabbit hole - memory virtualization and protection. The hack cpu does not support that but all modern OSes are built on top of it. An interesting thought experiment is - what are the minimal changes that need to be made to Hack cpu in order to support robust milti-tasking OS?

[dsguy]

Thanks to both of you, that's very helpful. Just for my understanding, are the "memory manager" mentioned by WBahn and "memory virtualization" mentioned by pm100 the same thing?

Considering your explanations, my understanding is that Jack's alloc serves as both the OS memory allocation as well as the program's memory allocation - is this at least the right direction, albeit extremely simplified?
I guess most discrepancies to my initial post stem from the fact that in N2T everything is so very close to the hardware and the system itself is very simplified for educational purposes, which is likely not feasible for a modern computer.

Maybe a better question would be: Given I have completed N2T, learned a ton and loved it, where do I go from here? How do I continue in the "real world" considering there's so many concepts, topics and directions. When I started this course, I came across a forum post elsewhere where people recommended doing N2T and then learning C/C++, since apparently a lot of the concepts learned here are applicable when using those languages, but is that simple - learn a programming language?

I kind of want to dive deeper and potentially see where it takes me, personally and professionally (I do work in software already, but not even close to what I've learned here).