Memory allocation, view at the lowest level

What you describe is increasing the stack pointer to "allocate" an array. The runtime has already allocated stack memory for your program when the thread was started. When you increase the stack pointer you are using some memory from that fixed allocation (usually ~1MB). The allocation would be automatically "deallocated" when the function returns. This is effectively the same as declaring a statically-sized C array, or using the alloca() function:

int array[4];
int* array = (int*)alloca(4*sizeof(int));

While stack allocation is fast, it can only allocate so much memory before a stack overflow occurs (i.e. by accessing invalid memory pages beyond the end of the stack).

Real memory allocation requires calling OS functions, such as VirtualAlloc(), to get a portion of virtual memory space to use for program memory. The C/C++ allocator is doing that under the hood. The C/C++ allocator is then dividing up those virtual memory pages into individual user allocations (when you call malloc()), and manages how they are freed (when you call free()). The allocator is using lots of complicated tricks to avoid problems like fragmentation.

When you declare a global variable, space for it is made inside the executable file's data section, and references to the variable name get replaced by the address in global memory. At application startup, the OS reads the executable file and allocates memory for its various sections (code, data, etc.).

When you declare a local variable, the function prelude takes care of it as you enter the function. It usually consists of something like this:

push rbp      ; push the stackframe base pointer
mov rbp, rsp  ; set the current stack pointer as the new base pointer.
sub rsp, N    ; subtract the stack pointer (grows downwards) to make space for local vars

And then a reverse sequence is done at the end of the function before you return:

mov rsp, rbp  ; reset stack to the start of this stack frame.
pop rbp       ; regain the old stack frame's base pointer
ret

X86 has two special instructions that can also be used instead: enter N, 0 and leave. Modern optimising compilers prefer not to use enter, since it is slower than doing the sequence yourself (as it performs a more complex operation supporting nested stackframes), but leave is usually emitted.

Local variables are addressed via [rbp - offset], where offset is the start address of the variable on the stack.

Global variables are addressed via their known address in virtual memory, or via some segment register or something, for position-independent code, as far as I know.

Runtime-allocated memory is allocated via a syscall to the operating system. As syscalls are expensive due to the privilege escalation and all the virtual memory mapping changes etc. (usually on the order of a thousand cycles or something), and since the kernel allocator only works on a page (4KiB) granularity, most runtimes implement malloc() and other functions via a custom wrapper around it that runs in userspace. But internally, it still relies on the kernel to allocate memory. You could theoretically write your own malloc/free around the kernel allocator you wanted.

It's pretty fun to try to program some stuff in assembly. I once wrote a NASM dialect using macros that was pretty much assembly + structured statements like if/else, and automatically handled function calls & signatures, local variable allocation, etc.. You should at least have a rudimentary understanding of what the machine has to do in order to execute your high level code, so that you can get a rough idea of how good or bad a piece of code is.

Others are covering the difference on the stack and the heap, there is more to it besides, especially if you move out of the "Big" operating systems like Windows or *nix family operating systems, and get closer to the actual underlying hardware.

Activating university C++ class lecture mode

What you ask is actually a relatively deep question, and it gets harder to answer simply when you start asking about the underlying hardware.

First, is the difference between stack space and heap space.

STACK SPACE.

Every program gets a chunk of memory, called the stack. For 64-bit Windows program it defaults to either 1 or 4MB, for 32-bit Windows programs generally the default was 1MB. For Linux programs generally 8MB. Every time you call a function, information is put on the stack and stack pointer register (which we'll call RSP) is increased. When you create a local variable you could bump the stack pointer to account for the space, and when you return from the function that bit of the stack was no longer in use. If a function used 192 bytes of local variables, C++ would reserve 192 bytes by increasing the stack pointer by 192 bytes, and would automatically translate the locations like RSP+4, RSP+8, RSP+12, and so on. The saying is the stack grows DOWN, because in most systems when you enter you subtract that total amount so RSP points to the base of your current stack, then you can use + offsets into where your variable lives. That is all by convention, a new operating system could come up with a different convention, but that's been the normal way of doing things for nearly 50 years and few systems have significantly changed it.

Side note on the register. In some code the stack pointer is also be copied to the RBP, the base pointer, so you can use it as a local constant. That's by convention only. If you're using an optimizing compiler there are optimization settings where only one of those will be used, usually RSP, the other usually RBP will be used for other general purpose operations so there is one more register available to the optimizer. If your configuration happens to copy RSP to RBP, know that optimizers can remove it as part of removing frame pointers.

Stack space is a very limited resource. It doesn't matter how much physical memory is installed or how much virtual memory is available, usually all you get is what the system allocates for your thread. If it gives you 4 MB, and you want to create a 2MB array you've just consumed half your total stack. If you want to create a 6 MB array, tough cookies, that's too big and your program will crash if you attempt it.

HEAP SPACE.

Heap space is limited by the operating system. You make a function call into the system, either through a language system call like malloc(), calloc(), realloc(), aligned_alloc() or through an operating system call like GlobalAlloc() , LocalAlloc(), HeapAlloc(), VirtualAlloc(), or similar. Whatever variation you use, the system does whatever work it needs to behind the scenes to allocate your block of memory.

Generally when allocating your block of memory, first it will try to reuse blocks of memory that were already assigned to your program. If it can't reuse a block, it will go out to the operating system's global pool of memory and find a block for the program, blank it out to all zeros for security purposes so you can't see what used to be there, assign that block of memory to your process, then return with a pointer to that piece of memory. Most operating systems will work in "pages" of memory, these days typically 2MB or 4MB chunks, and assign the full "page" to the program. If the operating system has to allocate and assign memory, it can potentially be an extremely slow task that (invisible to you) blocks your program. It can require system-level mutex locks across multiple processes, can require multiple round trips to and from disk, and those all take time.

When you allocate memory using these libraries, a chunk of memory is assigned to you. It can potentially cause fragments of memory to not be in use, either because the system needs to get memory alignment correct, or because there are gaps in the size like you asked for 192 bytes and there was a 196 byte available block so the system left those 4 extra bytes ignored, or for many more reasons besides. These can accumulate over time as programs allocate and release blocks of memory. In resource-constrained environments, and in computer systems before the 64-bit era, memory fragmentation was a serious concern. If a game console only had 4 MB total memory available you couldn't really afford to have little fragments of memory unused, and programmers needed to think carefully about code that could potentially cause memory fragmentation. Virtual memory resolved some of that problem, and the 64-bit address space where you could theoretically allocate 16 terabytes in total system virtual memory, memory fragmentation of your heap space is a very rare situation because so many pages of virtual memory are available.

Decades ago in AAA games (and even in smaller games) there used to be strict rules about when heap allocations could take place because they have a potentially high impact, stalling the computer for multiple graphics frames in the worst case if old spinny hard drives needed to be spun up from sleep, or worse for game consoles if CD's potentially needed to be spun up. Definitely not something you wanted to trigger during gameplay, just about to jump out of the way of a boss's devastating attack when suddenly the game stalls as an effect was processed.

It can be a painful but informative dive if you ever want to get into the details of how those libraries work. They're not typically installed by default, but you can install the UCRT (Universal C Runtime) library source to see what is involved. There are all kinds of checks around verifying the heap integrity, tools for detecting memory leaks, functionality to ensure safety between threads, and so much more. It can take an awful lot of digging to make sense of it, but a seemingly simple call to allocate memory can trigger an incredible amount of processing. I can't find a public link, but if it is installed, look up C:\Program Files (x86)\Windows Kits\10\Source\10.0.26100.0\ucrt\heap\malloc.cpp as the starting point, then dig, dig, dig.

PROCESS MEMORY SPACE (virtual space) AND PHYSICAL HARDWARE SPACE

If you're working on a "big" operating system like Windows or Linux, those addresses are actually virtual addresses, not real hardware addresses. When your program reads and writes to memory, there is a behind-the-scenes mapping that the CPU does, mapping blocks of your program's memory to the physical memory. The CPU and operating system work together and it is usually invisible, unless it isn't. Most of the time, they can keep the "working set" of programs in the actual hardware memory chips, so when you access a memory address the CPU looks it up in a data table, finds the process's virtual memory address that maps to the physical memory address, and loads it up. If you happen to load a memory address that isn't in the working set, the processor generates a hardware exception for the operating system. The process thread is paused (invisibly to you), the operating system figures out what block of physical memory it wants to allocate to your program's memory. If it has an empty slot, it will use it, otherwise it will save off memory that some process is using, mark the memory as not in use, load from virtual memory storage on disk into that block, mark the memory as belonging to your process, and finally resume running your process. Swapping memory like that is slow because disks are relatively slow. It can take many million CPU cycles or even trillions of cycles to do the work, especially if the disk used for swap space happened to be on hardware sleep to save power. For the brave or foolhardy, the Linux kernel handler for user-space faults is here.

If you're working on a small system like a microprocessor, there very often is minimal overhead at the operating system and no virtual memory; all memory addresses are actual hardware memory addresses, with special cases for the zero memory address because zero as a null pointer constant. If you really want to get into the weeds of the languages, both C and C++ rely on multiple null pointer constants, and it's only through compiler guarantees that they compare equal to a value like (void*)0. It is also very rare that it refers to the actual memory address 0x00000000 , it's just a magic number the system reserves to say "this is actually nowhere." If you're using near and far addresses, not done in modern c++ code but it still exists at the assembly level, these pointers automatically convert and compare to "huge" 32-bit or 64-bit pointers doing behind-your-back magic. Unless you're a language lawyer looking at hardware implementations of languages, they're something you don't have to think about, but it is something that exists.

More along those lines about what technically could happen versus what actually happens in regard to multiple null pointer constants, it gets painful fast. There was a rather in-depth conversation back in the old Usenet days that I remember Richard Heathfield and I got a bit too deeply around a seemingly simple question. He was able to boil it down to a single statement that he reposted to the official language newsgroups: In C, is printf("%p", 0); well-defined? Justify. that ultimately pulled in multiple people who served on the language standard groups, with the final conclusion that (void*)0 is defined but in the strictest technical reading 0 alone was undefined but in practice it would do everything you intuitively expected it to do. The reason got into deep technical discussion about the nature of null pointer constants.

In any event, for the systems you are working on, the memory addresses you see in your program's process space do not map to physical hardware directly. At the lowest level your process can reach in user-space as C++, C, or even assembly code, there are still two levels of redirection that take place in kernel-space that map process memory into virtual memory, and virtual memory to hardware memory. Those are managed by the operating system.

end lecture mode

Sidenote - x86_64 notably does not use a frame-pointer anymore, unless absolutely required. Frame-pointer was mainly a leftover of early days, where a lot of manual ASM was used; and also before a unified unwinding routine was established.

In compiler-generated x64, the compiler is very well able to know where RSP was before modifications, so it can just calculate any access that would be done as [RBP+X] as [RSP+X-Y], where Y is the final allocated stack-size of the function.
Also, the unwinding-procedure is fixed, so the epilogue will simply undo all modifications to the stack (so "sub rsp" instead of "mov rsp,rbp"). This means the runtime does not need RBP for unwinding either, as it has information about what operations were done on the RSP (and can thus undo those operations internally to get to the previous frame) - this is part of the unwind-information section in the binary, which is necessary both for unwinds as well as exception-handling (even if c++-exceptions are disabled).

This leaves x64 with one more register to use as it sees fit. There are still cases where RBP must be used, but this is mainly for functions that have a dynamic frame-size, mostly due to uses of dynamic-sized stack arrays (alloca).

Calin wrote:

It would be complicated to unravel what is taking place in c++, that's why I'm trying to understand the Assembly perspective.

Show more

If you're interested in the broader sense of memory management, which is usually the motivation to look at lower level implementation details already explained by others, maybe it's worth to add some context about this as well.
Imo it's quite a difficult topic and understanding it at the low level does not help much to deal with it.

The usual problem is: We want to allocate/deallocate memory dynamically, e.g. as units or buildings come and go during the game. We also want it to be fast, and we want to minimze levels of indirection to access our data. We may even want to have multiple elements in order so we can iterate them efficiently, minimizing random access.

That's a lot of goals, so we have to do some compromises, and there is no 'one fits all needs' solution ideal for any use case.

The primary technical problem is: Asking OS to allocate new memory for each element individually is slow, and it would also scatter elements randomly across RAM, so processing them after allocation is done can be slow too.

The solution is: Allocate a large buffer of RAM only once, and suballocate from that using a custom algorithm and data structure which is fast.
A simple one would be a 'stack allocator', which works like the stack frame discussed above, but requires to allocate and deallocate temporal memory in the same order, so we can not free up some chunk we had allocated earlier than the last and current allocation.
To lift this limitation, we can use the 'freelist' algorithm e.g. to make a 'pool allocator'.
(I have implemented freelist pretty often over the years, both on CPU and GPU, each time forgetting how it works, so i always need to begin from scratch again. It would be smarter to make this a general and modular tool in the code base early.)

There are many variants of such custom allocators. It depends if all elements we may allocate are guaranteed to have the same size or not for example. Or you want to only allocate, but then free all of them after the frame is done, etc.

This is also where high level languages such as C really shine over assembly.
You can implement anything in assembly, but managing the complexity quickly becomes impossible in practice.

JoeJ said:
There are many variants of such custom allocators. It depends if all elements we may allocate are guaranteed to have the same size or not for example. Or you want to only allocate, but then free all of them after the frame is done, etc.

My custom allocator differentiates between “objects” and “regions”, where objects get pooled by size-class and are not resizable. That way, I can avoid fragmentation. Regions are resizable allocations and do not go into the object pool. Objects of the same size class are in an array, basically, leading to good locality if order of access is similar to order of allocation. On top of that, I have a stack/linear allocator, which allows for partial or full resets of the allocator progress. And objects and regions have separate free() functions, and you have to also provide the alignment and size with the deallocation request, so that the deallocator can more efficiently find the memory to free up.

JoeJ said:
This is also where high level languages such as C really shine over assembly. You can implement anything in assembly, but managing the complexity quickly becomes impossible in practice.

I think it's best if you roughly know what assembly you want to achieve, but then use the high-level language to write it, and hope that the optimiser gets it as close as possible to what you wanted to actually do. Which is how SIMD intrinsics work, too. That way, you don't have to worry about register spilling and keeping track of variables, etc.. However, sometimes, it is crucial that no register spilling is allowed to happen or it would make one approach slower than another. For that, it can still help to have inline assembly. For example SIMD registers have much higher latencies to/from memory than general purpose registers, at least on x86. So a spill can easily break your neck there. Though I guess you can probably more or less trust a compiler to not spill SIMD registers when the working set of vector variables is ≤16 and no function calls are within their lifetime.

RmbRT wrote:

where objects get pooled by size-class and are not resizable. That way, I can avoid fragmentation.

Depends on goals. For example, i want to allocate 20 rigid bodes, and i want to have them close in memory because they form a ragdoll and i will iterate them in order often. But there is no guarantee they will end up in order, and chances decrease the longer the game runs. So i still have fragmentation, and i might want to defrag the memory pool from time to time, changing all the pointers and causing runtime spikes.
That's why i consider memory management difficult and basically impossible to be optimal. It's frustrating and i'm never happy.

RmbRT wrote:

For that, it can still help to have inline assembly.

Yeah, but i have some paranoia here. Say you have a little inline asm function using registers a,b,c.
If the caller already uses those registers for something else, it needs to shuffle stuff around, which it would not need to if i used an inline C function instead which does not fix the HW registers.
I guess compilers are not smart enough to avoid this in some ore any form. But maybe i use the example as an excuse to no longer bother with asm. ; )

RmbRT wrote:

I think it's best if you roughly know what assembly you want to achieve, but then use the high-level language to write it, and hope that the optimiser gets it as close as possible to what you wanted to actually do.

Compilers are hyper-optimized at that stage, and way better in generating ASM than any human. They have knowledge of all those edge-cases and performance-quirks, more so than you do. They will not only get "close to what you want to do", but be better in 99.9% of the time - the chance that your handwritten ASM beats a compiler, is slim to none. You'll most likely make things worse.
The only way your hand-written ASM could be better is, if you have some global knowledge that the compiler can't possibly have (ie. that a global variable doesn't change through an opaque function call - but even that can be solved in high-level with local variables). Or if you are trying to optimize for a very specific processor architecture, but most compilers even have settings to tune for some architecture.
There'll always be bugs/misoptimizations, but that'll be the same (and worse) for what you do yourself. And compiler will get smarter, while your own knowledge of what is faster get's invalidated with every new processor generation (I'll guarantee you that 90% of what you think is faster, doesn't apply anymore).
Knowing ASM can somewhat help understand what choices to take, but what is or is not faster in ASM is not intuitive at all. Mostly, it'll be enough to know about the general calling-convention of your target-platform, to understand how to best setup function-calls (as there can be huge difference, if the platform ends up passing some primitive type in a register, or via reference).

JoeJ said:
That's why i consider memory management difficult and basically impossible to be optimal. It's frustrating and i'm never happy.

Yeah, it's one of the hardest problems in programming, especially when you want performance. Though with 20 pieces, I'd allocate them as one object as well, or as a region. One “object” allocation does not have to correspond to a single struct in the type system. I did add the option to register a defragmentation handler with every resizable allocation, though. To properly use that feature is not easy, though.

JoeJ said:
I guess compilers are not smart enough to avoid this in some ore any form. But maybe i use the example as an excuse to no longer bother with asm. ; )

I also don't use inline asm unless I need to invoke some specific instruction that I otherwise can't. Such as rdtscp or something. Or if I had to write my own _start() or something (which I might have to end up doing soon).

Juliean said:
Compilers are hyper-optimized at that stage, and way better in generating ASM than any human. They have knowledge of all those edge-cases and performance-quirks, more so than you do. They will not only get "close to what you want to do", but be better in 99.9% of the time - the chance that your handwritten ASM beats a compiler, is slim to none. You'll most likely make things worse.

You're coming at it from the wrong angle. It's not about being able to write better ASM than the compiler, it's about targeting good ASM as your goal. If you have no understanding of how CPU execution works, then you don't know what good or bad machine code is. Then you also don't know what machine code your C/C++ code could produce, and what the upper limit in performance is, assuming a perfect compiler. And you also have to think about how much register pressure your code produces, etc., which can also make your code much slower than a tight loop that only lives in registers. Whether you could then write ASM code that is the optimal implementation of your algorithm, or whether you let the compiler do it for you, doesn't really matter these days. But there's a huge difference between having some sort of machine operation sequence in mind, and not thinking about it.

RmbRT wrote:

Though with 20 pieces, I'd allocate them as one object as well, or as a region.

Going from example to practice, i've tried that by putting them in an array, requiring to manage rigid bodies differently than intended from the physics engine. It was hacky but it worked and i liked it.
But then the physics dev made changes, so now each body requires a unique allocation and a kind of smart pointer.
Lesson learned: I can not hack code written by others which is still wip. : /
Though, they guy has optimized the memory management of the biggest AAA game of the recent decade, and it runs like a charm. So probably he knows what he's doing and i don't need to outsmart.

JoeJ said:
But then the physics dev made changes, so now each body requires a unique allocation and a kind of smart pointer.

Lesson learned: don't use OOP. I'm glad I don't have to work with other programmers. Actually, the lesson could also be that one person should be the owner of an entire section of the program and he should be responsible for all architectural decisions made there, and also for its performance.

If it was already a concern to have everything cache-friendly, then the programmer should have put in some effort to design the physics code around cache locality. Though as long as every object is contained within a single cacheline, and you can do a manual prefetch, then it doesn't matter much even if you scatter it around.

RmbRT wrote:

Lesson learned: don't use OOP. I'm glad I don't have to work with other programmers. Actually, the lesson could also be that one person should be the owner of an entire section of the program and he should be responsible for all architectural decisions made there, and also for its performance.

It's like you're intentionally learning the wrong lessons.

That isn't what object-oriented is nor does, and conflating the two doesn't help.

That isn't what developing together is about, and that type of control is terrible, almost abusive rather than collaborative.

The takeaway I've seen in dealing with this for decades is that it almost always don't matter. The tools and systems involved are faster and better at it for the general case. Measure, and only then can you find the actual places where it does matter. It is almost never where you think it is. I've been in likely thousands of group meetings where we've done group deep dives into optimization passes, reviews of performance graphs, PIX measurements, and assorted other profiling system data. Most of them there is absolutely zero point in trying to guess what we'll find, that educated guess is going to be wrong nearly all the time. It's going to be some edge case nobody thought about, some resource contention over a data structure nobody thought was important, some algorithm choice that was unrealized at the time, some code path that happened to trigger a recursive call nobody knew was there, or any of an untold number of things.

Measure, find out what today's actual measured issue is, then address that issue and measure again.

So many operations on the CPU have an amortized cost of zero. Between the optimizing compilers, the out-of-order core, the assorted prediction systems, caches, pattern history tables, branch history tables, and techniques like the 2-ahead branch prediction, the cost isn't the processing. The double-redirect pattern has been used since the 1970s, the pattern is the core of what became called virtual functions in the 1980s, and history tables introduced to the x86 core in the early 1990s usually make that redirection free except for the first access. Almost always the cost is simply the effort of keeping the CPU fed with instructions and data, streaming a steady supply. And that's almost always best done through simple data access patterns of arrays of things. Nothing about being object oriented precludes it, and done well, keeping things in objects allows building regular collections that are highly predictable, easily iterated, easily pre-fetched, and have patterns the processor and compiler can find far easier than humans ever could.

Measure, see the actual bottlenecks, and address those. The rest tend to not be issues in practice. Experts have been iterating on these tools for over a half century; the tools are complex, they take a lot of effort to dig deeply to understand how the pieces work, but they're really quite good at their job.

RmbRT wrote:

Lesson learned: don't use OOP.

That's another topic, but it applies to my physics engine struggles too, even more so.
If it would be written in C instead C++, i would not need to hack it, e.g. to access private members or to call functionality implemented only in constructors.

RmbRT wrote:

I'm glad I don't have to work with other programmers.

You will be glad once it becomes too much work for you alone ; )

RmbRT wrote:

If it was already a concern to have everything cache-friendly, then the programmer should have put in some effort to design the physics code around cache locality.

Show more

Show more

The guy is good at optimization and i do not worry.
I think that almost all programmers care about optimization, as it's part of the primary motivation to see how fast computers can do stuff.

Disagreement on programming paradigm is the bigger problem imo, but usually you can clearly divide responsibility and just care about interfaces everybody agrees upon. Which is easy if both guys work on the same project, but harder when using open source libraries. But well, it's no huge problem. It just causes some rant and focus on the flaws of various paradigms, but that goes both ways.

@khawk

There is an annoying bug since today. Some quotes, but not all, cause repetitive automatic insertion of 'Show more' right below it. It can add infinite lines of that, one more each few seconds, and i can not delete them quickly enough before posting.
When posting it asks about potential spam, probably because the 'show more' is supposed to be a javascript link inside but not outside the quote:

(sorry for not using feedback button but i already had the image only in clipboard)

frob wrote:

malloc(), calloc(), realloc(), aligned_alloc()

Alocating memory on the stack is simple the variable gets replaced with an actual memory address when the program starts (the OS does the replace operation) but what about malloc()? How does that work? If you call malloc() in your program that's just a library function. The malloc function definition becomes an extension of your program, basically it's part of your program but the problem is that's it's a general purpose library that doesn't have specific information about what memory will be available when the program will be launched. I wonder do you get some code segments from malloc() function definition being replaced with actual memory addresses that are available when the program starts?

JoeJ wrote:

Imo it's quite a difficult topic and understanding it at the low level does not help much to deal with it.

I need to understand the cell before I can understand the whale. It looks like you guys can understand the whale directly ) I can't function like that...

When an x86 OS mimics multithreading applications take turns at using CPU time. There is always just one process using the CPU time. My question is how do they (the processes) exchange information. Do they leave "messages" for each other at a commonly agreed memory address? Similarily to how threads talk to each other in an app that is using threads while running on a multicore processor? Is that how Windows tells an app the available memory address in a memory allocation request?

Thanks for your constructive feedback guys, I've learned a lot.

Calin wrote:

I need to understand the cell before I can understand the whale. It looks like you guys can understand the whale directly ) I can't function like that...

Well, say you have a wardrobe with 100 drawers.
Daughter wants 20 drawers.
Then son wants 10.
Daughter wants 10 more.
Son gives them back, not needing them anymore.
Daughter wants 50 more.
etc.

To distribute all the drawers to the kids requires you to track what's reserved and how many unused drawers you still have.
You need an algorithm and a data structure to manage this.
But knowing in in detail how drawers are made so you can open and close them, or how to make a wardrobe from wood, does not help much for your actual management problem.
That's what i meant.

Calin wrote:

Is that how Windows tells an app the available memory address in a memory allocation request?

Idk how Windows does it in detail, but it's the same problem. Multiple processes are like multiple kids. Windows needs to implement the management in software to serve their requests.
(There are also relevant hardware features like virtual memory addresses, but you always need memory management in software)

Calin wrote:

Alocating memory on the stack is simple the variable gets replaced with an actual memory address when the program starts (the OS does the replace operation) but what about malloc()?

Again, questions that are probably deeper than you intended. It can go down into compiler theory and operating system theory.

The malloc() functions ultimately get the block of memory from the operating system, exactly the same way the operating system allocates memory to create the process' stack in the first place.

It isn't that allocating memory on the stack is easier, it is that it has already been done for you. Your program already owns the stack memory and it has been fully allocated. The program happens to use it for variables, as a scratch space, and as a framework for function calls, but the work of allocating the space was done when the process was created. Every processing thread gets their own allocation.

Stack allocation feels easy because you aren't actually doing any allocation. The program is just marking memory that it already owns as being in use through a convention the program follows. It isn't allocating anything, it is merely saying "of the pool of memory the process already owns in the stack, reserve x bytes of the stack by advancing the stack pointer that many bytes".

The malloc function can actually allocate new memory to the program's process. In the language standard the details of how it gets the memory are left up to the implementation, they return a pointer to a region of storage that is allocated to the program. In practice, when they allocate a block from the operating system they allocate a large block, then they shave off pieces of that large block in subsequent calls. If you free memory, those aren't returned to the operating system immediately but are instead reused by subsequent allocation calls.

The easy "I'm new to programming" view, yes, malloc() gives your program a fresh block of memory with random garbage in it.

The more nuanced "I'm an advanced programmer" view, malloc() is potentially reusing memory your program previously released, potentially calling out to the operating system, potentially doing a tremendous amount of work on your behalf, and then ultimately returns you a fresh block of memory with unknown contents in it.

Calin wrote:

The malloc function definition becomes an extension of your program, basically it's part of your program but the problem is that's it's a general purpose library that doesn't have specific information about what memory will be available when the program will be launched.

The function is part of the language specification.

In that regard, yes, it becomes and extension of your program, just like so many others: malloc(), free(), sin(), cos(), tan(), abs(), exit(), abort(), gets(), puts(), isupper(), islower(), isspace(), isdigit(), and on and on, all of these functions in the standard library get incorporated into your program through the standard libraries. They are linked to your program just like any other libraries. You can link to graphics libraries, math processing libraries, windowing libraries, sound libraries, and so on.

None of them have any implicit knowledge of how you intend to use them, they are libraries available to the program for your program to use.

As far as it being general purpose, that's not a bad thing. General purpose libraries do an incredible number of amazing things. Math functions are general purpose, for example. File access is general purpose. Being general purpose gives a huge amount of accessibility.

You can augment the libraries with other allocation functions, others have already mentioned a few like pool allocators, small object allocators, singleton pools, segregated storage, and more, but down under the covers ultimately these rely on those same general purpose functions to get the memory in the first place. At some point, somewhere along the line something has to get a chunk of memory allocated to the program from the operating system. It can be done behind your back at program startup through the stack, it can be done intentionally at program startup, as plenty of old-school console games would immediately allocate ALL available hardware memory and then send it to their own custom allocator, or it can be something else entirely. But in the end, those functions exist and are there to be used.

Calin wrote:

I wonder do you get some code segments from malloc() function definition being replaced with actual memory addresses that are available when the program starts?

Again, a potentially deep question.

How malloc works is implementation defined. In practice, the functionality includes requesting memory from the operating system.

The stack is allocated by the operating system before your program starts. How it does it is implementation defined. In practice, this also includes requesting memory from the operating system.

When you dig deep into kernel code, you can find that at least on both Windows and on Linux, both of them allocate the memory in the same way, pulling from the operating system's global heap allocator. In that regard, yes, they are the same.

The size and availability of the stack is implementation defined, specified by the system and compiler, and set by options. In Microsoft's compilers, that's with the /stack command line option, in gcc it's the --stack option. It is stored as part of the program's information. In Windows, part of the PE header, the block at the start of an .exe file that says "this is a program and what it needs", one field of the header is the size of the stack.

Because of a bunch of details, malloc() and similar system library functions are written in a way that programs can replace them if they need to. It usually isn't done, but sometimes is. For example, there are many libraries out there to hunt down memory bugs that will replace the standard library memory allocation functions and replace it with their custom memory allocation functions.

Calin wrote:

When an x86 OS mimics multithreading applications take turns at using CPU time. There is always just one process using the CPU time. My question is how do they (the processes) exchange information. Do they leave "messages" for each other at a commonly agreed memory address? Similarily to how threads talk to each other in an app that is using threads while running on a multicore processor?

There are university courses that spend months on how processes exchange information.

There are many methods. The Wikipedia page on inter-process communication covers 11 major patterns, all of them except for the Darmouth-specific communications file are available on both Windows and Linux. The Dartmouth thing is something like "And then there's that guy over there. Nobody does that, but yeah, he's out there."

In my experience, message passing, message queues, sockets, and files are the ones I've used most often, signals less often apart from SIGKILL and SIGHUP, but I know in some industries and systems others like pipes and memory mapped files are more common.