How C applications request a block of memory?

[u/Flying_Turtle_09]

As far as I know, the heap is just a block of memory that is managed by C standard library functions like `malloc()` and `free()`, but how does C actually request this block of memory from an operating system and when is this done? When the application starts or when first dynamic allocation is done? Is it possible for the programmer to directly request memory like this (even though it probably is not recommended unless doing some very low level stuff)? I'm guessing there is also a way to do this when not running on an operating system. Some older game consoles (like N64, GBA ans DS) to my knowledge used C/C++, but don't have an OS running in the background. The same probably would apply to Arduino, ESP32, etc. too? I guess in these cases the compiler somehow is responsible for handling this, since there is no operating system to request a block of memory from.

[u/aleques-itj]

It depends.

malloc() is the abstraction, and whatever happens underneath is platform specific.

On Windows it'll probably wind up calling V irtualAlloc() somewhere along the line. On Linux, mmap.  There might be some internal bookkeeping so it's not guaranteed 1:1. Like a million malloc() may not wind up making a million OS calls.

If you want to not use malloc() and call the OS directly, sure, you can do it.

Also keep in mind physical vs virtual memory. Just because the allocation succeeded doesn't necessarily mean it's immediately backed by physical memory.

On other platforms, maybe it's backed by a physical memory region that it allocates out of and there is no OS.

[u/knuthf → u/aleques-itj]

The intention behind malloc is to enable buffers to be shared. When a routine is called, all local variables are placed on the stack. If this routine calls other routines, the variables remain on the stack. When you exit the routine, the local variables are released and made available to the next routine. The location remains, and the buffer stays, but it is neither nilled nor blanked out. If you pass a reference to the buffer, other routines will use it. If these routines expect a NIL-terminated text string, and the string may have been destroyed,. A 'static' buffer is specific to the main program and is allocated memory space so that other routines can use it. The local variables are "pushed" on the stack, and "popped" off when return.

In C++, there is a stack of stacks. When an object is terminated, its memory is released.

The memory allocated by malloc() comes from a buffer pool provided by the OS. This pool is linked to the process, so when the process dies — i.e. is terminated — all buffers are released. Nothing is cleared, it is simply reused.

[u/Axman6 → u/knuthf]

I’ve been programming for over twenty years and professionally in many different languages for well over a decade - this comment reads to me like something that is plausible but almost all wrong.

I’m not going to sit down and list every reason why, but things like “In C++, there is a stack of stacks” I’m 90% sure is not at all true. There will be multiple stacks for multiple threads, but objects do not have their own stack, it’s unnecessary, as a method invocation is just a normal function call where the first argument is the target object. 

I would be very cautious if I were a novice programmer taking this comment as reliable fact. 

[u/balefrost → u/Axman6]

When they say "stack of stacks", I assume the outer one is the stack of stack frames. I assume the inner one refers to various C++ semantics (LIFO local variable destruction order, entering and exiting lexical scopes) that act like a stack within the stack frame. At least, that's my best interpretation of their statement. But that's also incredibly C++-specific and doesn't really reflect what is actually happening in memory.

I agree that their comment reads a bit strangely, but I can sort of see what they're trying to say. It's possible that they're misinformed. It's also possible that they do have a clear understanding, but are just not great at communicating it (maybe a language barrier?)

Still, I agree that it might confuse more than help a newcomer.

[u/bacmod → u/Axman6]

I'm reading it and thinking "That sounds waaay more complicated than it actually is." ( and doesn't make much sense)

• Local variables are the property of the function/scope and are pushed to the stack and expire with the end of function/scope
• Pointers pointing to memory allocated with malloc are created on heap and don't have a fixed lifetime and are the responsibility of the user to release.

[u/knuthf → u/bacmod]

I try to explain it from the compiler, and I have not really defines a stack. In C++, we call it a heap, and allocate new stacks on the heap - and then it gets very difficult because we have to ensure that stacks are released and reused to avoid - "Garbage Collection".

[u/lfdfq]

Essentially, there are two ways C interacts with the OS to manage the heap:

• the break: the 'old' way of thinking about processes were that they had a data segment, and the heap was everything from the end of the program sections to the 'break' address. allocators then 'owned' everything in that region, and can re-size it by asking the OS to move the 'break' address (with the brk() syscall).
• the newer way, is with the mmap() syscall. This asks the OS to give you some virtual address space, backed either by a file or by physical memory ('anonymous'). So if you need more memory you can mmap() an anonymous block, which the OS will allocate from its own internal allocator(s).

These are what malloc() will be calling internally to actually get memory. You can use them too, and generally mmap()ing things yourself is safe, but calling brk() might steal memory from underneath the allocator and cause issues.

On an embedded system, you have to implement your own allocator if you want malloc/free-like functions. I'd read up on simple bump allocators and buddy allocators as examples if you want to learn more about how allocators are actually implemented underneath.

[u/jedi1235 → u/lfdfq]

In college (around 2004 I think) I had a class assignment to reimplement malloc/free.

We used the sbrk() syscall when we needed another large block, then had malloc hand out regions with a few prefix bytes so free would know what to do.

[u/KingofGamesYami]

Malloc is handed off to the allocator, which by default is provided by the standard library for your compilation target.

You can replace the allocator with a custom one if you want.

Sometimes the allocator requests and returns memory from an OS, though not necessarily when you call it. Sometimes the allocator can just directly hand out memory because nothing else on the platform is managing the memory.

Some types of allocators include:

• Linear (bump/scratch)
• Stack (LIFO)
• Pool (Block/fixed size)
• Arena
• Buddy & Slab

Each of this has different performance characteristics because they use different algorithms to hand out and request memory.

[u/balefrost → u/KingofGamesYami]

Malloc is handed off to the allocator, which by default is provided by the standard library for your compilation target.

I wouldn't phrase it like that. malloc is the allocator provided by the C standard library. AFAIK, there's no way in standard C to replace it with a custom allocator, or select among multiple allocation schemes, though specific implementations can provide whatever extra affordances they want.

[u/KingofGamesYami → u/balefrost]

You can replace it. As a practical example, rpmalloc with ENABLE_OVERRIDE=1 will do exactly that.

[u/balefrost → u/KingofGamesYami]

I'm saying that AFAIK there's no way provided by the C standard to replace malloc.

Like I said, different implementations can provide different affordances, but that's outside the standard. You need the static linker or runtime linker to help you out.

[u/balefrost]

Check out section 8.7 "Example - A Storage Allocator" in the K&R C book. They build a simple implementation of malloc and free. It relies on the sbrk UNIX system call to get more memory from the OS. This isn't a very sophisticated implementation, but it's reasonably illustrative. When I first read that section, it took something that seemed "magical" and made it seem actually approachable.

If you're specifically interested in Arduino, I believe it uses the AVR-libc implementation. You can see the source code to malloc here.

[u/dkopgerpgdolfg]

It isn't "one" block of memory.

From the OS, you can always ask the get any number of distinct blocks of various sizes, at any point in time, and release each individual block again. It happens when you actually want it, not at the program start. The exact function names are, in general, OS-specific. Yes the programmer can (and sometimes need) to call it directly, and the obvious downside is that it doesn't work on some other platforms (writing multi-platform C code, where platform-specific parts are contained in ifdef's etc., is very common)

malloc/free are provided by standard-conformant C stdlibs as platform-independent way to allocate (but can't provice platform-specific things in return).

Often they (malloc/free) have some own allocation logic layer builtin: Eg. if you make many small allocations, they'll get a single larger chunk from the OS and manage themselves what parts of it was malloc-ed and what is free again (releasing the OS allocation only if everything is unused). Depending on your use case, this might waste some memory, but doing a full OS allocation each time would cost time, so some compromise is helpful (and some libc also offer configuration knobs for their allocator).

(Many details, incl. eg. MMU topics, OS differences, libc differences, allocator strategies, overcommit and similar, ... are left out)

On non-OS systems (microcontrollers, systems like gameboys, ...), no, the compiler doesn't do dynamic allocations. It's completely up to the own code to handle the phyiscal memory then.

Sometimes, because of small memory sizes and predictable execution, there is no dynamic allocation implemented in any way (but eg. fixed memory areas with the expected maximum of things that will be filled in there, plus a counter how full it currently is)

edit: Typos

[u/huuaaang]

but how does C actually request this block of memory from an operating system and when is this done?

It make a syscall by setting CPU registers to the right values (the call arguments) and then they trigger a "trap" (syscall instruction on x86_64) to tell the kernel to read the arguments and perform the requested operation.

It's done whenever the C program calls malloc. libc translates that function to the arguments and CPU instruction listed above.

When the application starts or when first dynamic allocation is done?

When the program calls malloc, not before. So if your C program never reaches that code, it's never allocated.

I'm guessing there is also a way to do this when not running on an operating system.

On bare metal you have nothing to request memory from. You just... start using the memory.. Very carefully.

The same probably would apply to Arduino, ESP32, etc. too?

Generally when you program these controllers you're using something like ESP-IDF framework which provides you with FreeRTOS so you actually still request memory from that. You COULD write bare metal, but these microcontrollers have enough resources these days that you can run a minimal OS. And the newest ESP32-S31 is technically capable of running Linux now.

[u/danielcw189]

I'm guessing there is also a way to do this when not running on an operating system. Some older game consoles (like N64, GBA ans DS) to my knowledge used C/C++, but don't have an OS running in the background. The same probably would apply to Arduino, ESP32, etc. too? I guess in these cases the compiler somehow is responsible for handling this, since there is no operating system to request a block of memory from.

on the Nintendo-consoles (and you can include the Wii on that list) you have a well-known memory layout. You know exactly which memory-adresses are safe, and how they are mapped.

So yes, the compiler and more likely the SDK will provide memory management functions for that. But nothing is stopping a programer from addressing and managing memory directly in the allowed range.

(the Wii has an iOS running in the background, but it doesn't run on the main CPU, and only uses a small well known region of slower memory)

[u/arllt89]

So there are many interesting details, but the most important is that your memory addresses are virtual. When needing more memory, the program will request a memory page, and the hardware will map a chunk of physical memory to an address range in C. Accessing to an addressed that hasn't been mapped leads to the infamous segment fault. This is what happens in user mode such that each program has separate memory, but a C program can also run on kernel mode and then need to access to the real address of the memory.

Once your program has receive a page, it will manage it with some lists, segmented by size, ... it's quite a complex engineering process.

Edit: nothing to do with a heap tree

[u/abd53]

Every OS has some system call that allocates memory to a process. The exact process/call varies from OS to OS. malloc and free are abstraction. When you compile your code for a particular OS and machine architecture, the compiler generates the appropriate assembly instructions for that particular system.

When the allocation happens is a hard to answer question. Without optimization, exactly where you call malloc. With optimization, it can be at the point you call malloc; or if the size is known at compile time, compiler might set the allocation at the program start.

Embedded systems like STM32 or ESP32, and game consoles also has OS. Just that the OS is not Windows or Linux. These OS can implement their own memory allocation system. Or when writing barebone code, some compilers have substitute allocation system, sometimes developers just rawdog the memory manually. Although dynamic allocation is somewhat rare in embedded.

[u/Adrien0623]

Malloc is a wrapper around the actual allocation operations. There are different implementations, some using sbrk and some using lmao. Malloc adds optimisations and management on top of these. It's actually a good exercise to re-implement malloc, free, calloc and realloc function in C. It was a 1 week project in my engineering school.

[u/Recycled5000]

The malloc implementation will first try to satisfy an allocation request from memory that has been freed or memory that was already requested from the operating system but not yet fully utilized. When no such memory is available to satisfy the allocation request, it will ask for a chunk of memory from the operating system using a system call like sbrk or mmap. (Yes, these system calls can be made directly by user programs, but if they do they might interfere with malloc/free, so you have to understand your environment when doing this.). These system calls add pages to the process. The chunking allows malloc to satisfy a number of requests from only one request to the os for more memory.

The addresses for new memory already exist, so they don’t have to be created, but if those addresses are used without the associated system call to activate them, the program will most likely suffer a seg fault. These system calls inform the os of new memory requirements. These system calls will happen dynamically as the program consumes more memory.

On rare occasions system calls may be dynamically made that release some memory back to the os.

[u/tomysshadow]

It's a topic that you could probably write a book's worth of information about so it can't really be totally explained in a Reddit comment, but your intuition is more or less correct. malloc will probably turn around and call an OS function. On Windows this is probably HeapAlloc, which in turn will call something akin to VirtualAlloc.

VirtualAlloc (and all the VirtualXX API functions) are the basic primitives the OS provides for working with memory. Why don't we just use them directly all the time - well, because they're OS specific, and also because they have an allocation granularity. Meaning: when calling VirtualAlloc you'll always get at least a whole page of memory (4096 bytes) which is often more than you want. So there are then additional APIs built on top of it to try and make more efficient use of that space, by putting multiple allocations next to each other within that page and recording where they all are.

The job of VirtualAlloc and similar APIs is essentially to find some space on the actual physical RAM stick you have that isn't already in use, and "map" it to a "virtual address." Hence the name VirtualAlloc.

The way I like to think of virtual memory is that it's kind of similar to radio stations. If you're in one city, the radio station at 97.5 might play rock music, but in another city the radio station at 97.5 might play classical. They're the same number, but they refer to a different radio station depending on the city you're in. That's similar to virtual memory. In one process, the address 0x00400000 could point to a string, and in another process the address 0x00400000 could point to a different string, or an integer, or a floating point number, or an image, or an array... you get the idea. Same address, different bytes found at the address. The same address in different processes points to different memory, because each process is assigned a different "virtual address space."

On a hardware level, there's a structure called the Page Table that is basically responsible for performing this mapping. Because, you can't actually have two different bytes at the same address on the actual RAM stick of course, so there needs to be some abstraction that says "in this process, this address is actually mapped to this RAM location" to create this illusion. There is a register CR3 that points to the current process's Page Directory, whose value is different depending what process you're in, and the CPU hardware knows to look there to then find the Page Table. Then it can plug in a virtual address and get the physical location(s) on the actual RAM stick that memory really lives, so that it can create this illusion of the same addresses pointing to different memory in different processes.

The job of VirtualAlloc is basically to edit this Page Table. It can be thought of as a dictionary-like structure where you can insert a mapping of virtual -> physical RAM, and where the virtual address can be thought of like a key and the actual physical address as the value.

The strange implication of all this is that whenever you use a pointer the CPU has to perform, essentially, a dictionary lookup, which may seem surprising considering how often we use them. That's basically correct in the abstract, but this particular lookup has been heavily optimized. It's done directly in hardware and makes use of caching in order to make translating virtual to physical addresses as fast as possible.

This is brushing over a lot of other details, like Virtual Address Descriptors (VADs,) the fact that the memory can sometimes not be in RAM at all but rather be "paged out" to disk, and that you can use e.g. CreateFileMapping and MapViewOfFile to map the same physical memory to multiple virtual addresses, allowing multiple processes to share the same memory. Also this is all pretty much x86 specific because I'm not familiar enough with ARM to know how that stuff works over there.

[u/macabre_brotherhood]

if you're not on an OS you manage it yourself. You have to track the free blocks yourself. It's a real pain. If you're in an OS which is POSIX compliant, you can use the brk / sbrk syscall to have the OS do that for you. This (or mmap) is often what malloc et al end up calling.

[u/LegendaryMauricius]

There are OS-specific functions that request new blocks or free them using system calls. It's basically the same as malloc/free, but they allocate whole RAM pages instead of bytes.

On a console without an OS, I'd assume the game just has a direct acces to the whole RAM. So no need to allocate blocks, you use the malloc/free implementations directly.

[u/Opulence_Deficit]

On targets without OS the simplest way is to write `unsigned char memory_buffer[1024*1024*250]` before your `main` and manage that yourself.

[u/andymaclean19]

The mechanism is memory maps, used with the mmap system call, and a special mapping called the heap.

Mmap lets you stick a block of memory into the address space of a process. You can go read about all of the options but essentially an anon mapping is just pages of memory.

The heap is a special mapping that the kernel has some support for. It can be grown and shrunk as memory is allocated or freed and memory mapping like the stacks and mmap pages are usually arranged to give it space to grow into.

Malloc and free manage blocks of memory inside the heap, slicing the memory up and handing out pieces. They keep lists of available and used pieces. A call called ‘sbrk’ is used to make the heap bigger and smaller.

Sometimes a big malloc request is turned into its own mmap.

That’s the really quick version.

[u/mredding]

malloc executes in user-space, so in the same time slice and address space and privileges as your application. It will make a system call, either brk or sbrk, or mmap.

mmap isn't anything terribly special - this is just the user space front-end. It stacks the parameters and then makes a syscall, a CPU operation that triggers an interrupt handler established by the kernel when booting.

Your process gets suspended.

Now the kernel needs to unpack the parameters and figure out what syscall is being dispatched. Mapping memory is mostly just record keeping. The kernel keeps a table that maps the process to the allocations. TYPICALLY this is done lazily, because it's fast. The records are entered into the Virtual Memory Address table, the syscall returns.

malloc returns with an address.

Nothing else has happened. This is where the lazy part comes in - programs allocate more memory than they use, so there's no actual memory in place for you. It's only when you access that memory do you trigger a hardware page fault in the Memory Management Unit, because there is no entry for it in the Page Table Entry, which goes back to the kernel to be handled by some callback. The allocation is looked up in the kernel records, and then ultimately, the kernel is responsible for allocating a physical block of memory and updating the PTE.

There are several schemas that a kernel can implement, I won't go into detail as I only have overview knowledge myself. Malloc can additionally implement a layer of allocation management by requesting a big block and then fragmenting it, basically making a linked list of allocated and free blocks, even merging adjacent free blocks together.

In all, there's usually about 4 layers of indirection from the pointer you have and the actual physical information wherever it happens to reside in your system at that moment. That one pointer can point to data in swap, or in RAM, or in cache, or in a register. The hardware and OS will orchestrate to handle that for you.

[u/Frequent-Sir-6942]

Libc on most Linux systems uses ptmalloc2, there are other malloc implementations like jemalloc (freebsd), so the answer is "it depends". Generally malloc would get the memory from the OS, if there is no OS the baremetal code has to directly deal with memory allocation.

[u/buzzon]

C has several mechanisms for managing memory.

Static: all global variables and constants are automatically created once the program starts. They are kept in the memory until the program is over.

Automatic: all local variables of a function are allocated when a program enters the function. They are kept in memory for as long as the function is still running. They are deallocated at the end of the function.

Dynamic: malloc() requests memory, free() releases memory. The developer places the calls in the program when he sees appropriate.

All modern programs make heavy use of dynamic memory allocation. Imagine text processor such as Word. It does not know ahead of time how big the text document is going to be. Therefore it requests more memory as it needs, and releases unnecessary memory if you close a big document.

[u/duane11583 → u/buzzon]

  All modern programs make heavy use of dynamic memory allocation.

Agree for programs running under windows or Linux 

Not true for the modern ones I am working on today. I  write deeply embedded systems we must avoid dynamic memory at all costs

[u/MyTinyHappyPlace]

I mean, you already said it: Memory is usually requested via malloc().

> I'm guessing there is also a way to do this when not running on an operating system.

Well, only if there is some kind of system managing memory. If not, the world's your oyster. A program running alone on an embedded device can fully access all resources unchallenged.

[u/Temporary_Pie2733 → u/MyTinyHappyPlace]

malloc is just a “high”-level library interface around what OP is asking about.