Question Regarding Dynamic memory allocation

Question

Hello guys,

I have questions regarding stacks and dynamic memory allocation.

1) Does kernel determine the size of the stack dynamically during run time or sets the size before the load time ? If stack size is allocated dynamically how can stack overflow take place (Because if size of stack reaches beyond the limit the page handler will allocate space to grow the stack). Also If dynamically allocated how can stack grow from higher address to lower address(because always the virtual address increments for dynamically allocated storage right?)

2) Also if memory is allocated dynamically using malloc the size of the data region grows right ?

Thanks & Regards,

Mousey.

Answer 1

1) Dynamic memory allocation is from the heap, not the stack. The stack is a per-thread block of memory that also handles local variables and return addresses during function calls. The heap is just one or more blocks of memory allocated from the OS, which the C RTL subdivides as needed to satisfy malloc calls.

As for the stack, it's typically of a fixed size because, in a program free of infinite recursion, you should only need a finite amount. If you keep recursing, you'll overflow, which is a good thing in that it's a clean failure. As for growing down in memory, that's an implementation detail of CPU's.

2) Not necessarily. So long as the current allocation of memory from the OS is sufficient, malloc just uses it. Once this is gone, it may cause an additional allocation.

I know you want more detail here, but I'm not sure what's useful. I could talk about how the heap is typically implemented as linked lists of free blocks with arena headers that define their size, or how some systems use fixed-size blocks for small allocations to limit fragmentation, or even how memory bubbles are coalesced when no single sufficiently large block is found. However, all of these are implementation details that may well turn out not to apply in your case, at least not exactly.

Answer 2

Stack sizes

Typically, each thread has a fixed stack when the thread is created. Run ulimit -a to see the default stack size for your system. On my system, it is 8 MiB. When you create new threads, you can give them smaller or larger stacks (see pthread_attr_setstacksize).

When the stack grows beyond 8 MiB, the program will write to an invalid memory location and crash. The kernel makes sure that the memory locations next to the stack are all invalid, to ensure that programs crash when their stacks overflow.

You may think that a fixed size is a waste, but that 8 MiB is virtual memory and not physical memory. The difference is important, see below.

Malloc

On Unix systems, memory allocation has two layers to it. The user-space layer is malloc (and calloc, realloc, free). This is just part of the C library, and can be replaced with your own code -- Firefox does this, and many programming languages use their own allocation scheme other than malloc. Various malloc implementations are cross-platform.

The lower layer is mmap (and sbrk). The mmap function is a system call which alters your program's address space. One of the things it can do is add new anonymous, private pages into your program's memory.

The purpose of malloc is to get large chunks of virtual memory from the kernel using mmap (or sbrk) and divide them up efficiently for your program. The mmap system call only works in multiples of 4 KiB (on most systems).

Memory: virtual versus real

Remember that the stack and all of the memory returned by mmap is just virtual memory, not physical RAM. The kernel doesn't allocate physical RAM to your process until you actually use it.

When you get anonymous memory from the kernel, either on the heap or the stack, it's filled with zeroes. Instead of giving you hundreds of pages of physical RAM pre-filled with zeroes, however, the kernel makes all of that virtual memory share one single page of physical RAM. The virtual memory is marked read only. As soon as you write to it, the CPU throws an exception, transfers control to the kernel, and the kernel allocates a fresh, writable, zeroed page for your program.

This explains why:

• calloc is faster than malloc + memset (because calloc knows that the mmap'd pages are pre-zeroed, and memset forces the allocation of physical RAM)
• You can allocate much more memory than combined RAM + swap (because it's not used until you write to it)

Answer 3

1) It kind of depends on the OS, but a typical scheme is for the OS to give you one page of virtual memory (pages are commonly 4 KB) for the stack and then marks the virtual memory page immediately after it as a "guard page." This is a special flag that causes a low-level exception to trigger when an application tries to write into it.

The OS handles the exception when you try to write into the guard page (which happens as you grow the stack past the initial allocation size), allocates that page for you (i.e. maps it to a physical memory page), and reruns your program from the instruction where the faulting write occurred. It will work this time since the page has been backed by real memory.

Past a certain point (commonly 1 MB), the OS will stop doing this and trigger a stack overflow exception. This is just because these are usually indicative of program error, and code that really needs huge stacks can allocate memory for whatever their stack data is on the heap.

2) The data segment doesn't really "grow." Modern programs have a fixed virtual memory address space. malloc() uses some scheme to carve up this space and back portions of it with real physical memory.

I think both of your questions hint at wanting a better understanding of how the OS provides physical memory to your programs. The key concept in modern systems is virtual memory. Wikipedia's page on virtual memory is a good place to start.

If you want to develop detailed knowledge, an OS textbook would be a good place to start. Preferably one that's better than whatever I had when I took that OS course in college :)