Memory

Introduction

S6 drew the map the compiler prints: runtime, code, initialisers, and a gap up to Fixed Data. Everything a program does while it runs happens in that gap, and there are two things in it that grow towards each other - the stack, where every function's locals live, and the heap, where malloc hands out memory on request. This section is about the gap: how big it is, how to use it, and how each end of it runs out, which on a 64K machine is a thing you will see.

The Map, Running

Take the numbers from the listing below, in decimal:

sbrk(0) is a library call that returns the first free address after the program: everything below it is code, everything above it up to the stack is free. The globals - yours and the library's - are the Fixed Data of the map, laid out downward from EC00. The stack starts under them and grows downward: each function call pushes its return address and its locals, each return pops them, and &local in main is at 58401, about 2K below the top, because the runtime's own workspace comes first. The heap grows upward from sbrk(0). Between them, on this program, about 52,000 bytes; the free space in a bigger program is whatever its code and globals leave.

Globals are allotted when the program loads and cost nothing at run time. They start at zero. Locals live on the stack and cost nothing until the function is called, and start with rubbish. That is the whole difference, and it is why S15 said what it did about filling arrays.

Asking For Memory

p = malloc(100);

gives 100 bytes and returns their address, as a char *; assign it to whatever pointer type you need (S16 says a cast may be wanted). The listing asks for 100 twice and gets 6054 and then 6158 - 104 apart, so each block costs four bytes over its size for the heap's own records. free(p) gives a block back. Asking again after the free gave 6102: not the same address, and where the freed space went is the library's business. sbrk(0) moves up as the heap grows - 6258 after the two blocks.

Why malloc at all, when an array would do? Because an array's size is fixed when you write the program, and malloc takes a number computed at run time - a table as long as the file it was read from, a board as big as the level says. And because a global array of 50,000 bytes takes 50,000 bytes whether the program uses them or not; a malloc of the same takes them only when asked.

Running Out: The Heap

Ask for more than there is and malloc returns 0, and this library's malloc also prints heap full on the screen for you. It is the same rule as fopen: test the result before you use it. A program that writes through the 0 that malloc returned is writing at address 0, which is the runtime.

How much is there? In one run, malloc(20000) succeeded twice and malloc(10000) a third time - fifty thousand bytes, up to 55963 - then 5000 was refused and 2000 was granted at 55967. So the ceiling was a little under 58000, just below the stack, and the heap will take everything up to it. Which means a program that mallocs freely can eat the stack's room, and the stack does not check with the heap before it grows.

Running Out: The Stack

Every call costs stack: a return address, the arguments, the locals. A function that calls itself (S13) goes down one frame per level, and the levels are the only thing that can use the stack up fast. The program below counts:

down(n) int n;
{
    int local;
    local = n;
    if (n % 256 == 0)
        printf("%d ", n);
    down(local + 1);
}

It printed 256 512 ... 6400 6656 and then

stack overflow

and the prompt came back. That message is the runtime's, and the manual says it is the only thing the runtime checks for. About 6,650 levels of a function with one argument and one local; a function with a 100-byte array among its locals managed a little over 500.

Do not count on the prompt, though. The same message from a function with a 500-byte array in it was followed not by the prompt but by the program starting again from its first line - and overflowing again, and again, until the Einstein was restarted. The check is real; what happens after it is not something to build on. Recursion that stops at a depth you can count - the levels of a tree, the length of a string - is fine. Recursion that goes as deep as the input is large is a stack overflow waiting for the right input.

Running Out: Globals

The third way is quieter. Declare char big[50000]; as a global and the map's Fixed Data line reads 2893 EC00: the array has pulled the globals' start down to 10,387, and the stack and the heap must now share the five thousand bytes between there and the end of the code. A global array of 55,000 bytes compiled just as quietly, with Fixed Data starting a few hundred bytes above the code, and the program misbehaved when it ran. There is no message at either stage. Read the map when a program has a big array, and keep a few thousand bytes between the end of Initialisers and the start of Fixed Data.

The Code

#include STDIO.H

main()
{
    int local;
    char *p, *q;
    printf("the program ends at %u\n", sbrk(0));
    printf("a local lives at %u\n", &local);
    p = malloc(100);
    q = malloc(100);
    printf("malloc gave %u then %u\n", p, q);
    printf("sbrk now says %u\n", sbrk(0));
    free(p);
    p = malloc(50);
    printf("after free, malloc gave %u\n", p);
    p = malloc(60000);
    printf("60000 bytes: %d\n", p);
}

#include ?STDIO.LIB?

Starting from

Typed as MEM.C; compiled and run.

What you should see

the program ends at 6050
a local lives at 58401
malloc gave 6054 then 6158
sbrk now says 6258
after free, malloc gave 6102
heap full
60000 bytes: 0

The exact addresses shift by a few bytes if the program is edited; the shape does not.

Change One Thing

• Change the two malloc(100) to malloc(30000). Which one fails, and what does sbrk(0) say after?
• Add char pad[500]; to the locals of S13's fact, and call fact(2000). What happens, and how is it reported?
• Declare char big[50000]; as a global in MEM.C and compile it. Compare the map with the one above before you run it - and then do not run it.

Exercises

21.1 malloc room for ten ints, fill them with 1 to 10 through a pointer, print their sum, and free them.

21.2 Count how many malloc(1000) calls succeed before one returns 0, and print the count.

21.3 Write a function that calls itself with a counter and a char pad[100] local, prints the counter every 50 calls, and never stops. How deep does it get, and how does it end?

Worked solutions are in Appendix II.

When It Goes Wrong

Summary

Code from 4608 up; globals at the top, under the DOS; the heap grows up from sbrk(0); the stack grows down from under the globals; about 50K between on a small program. malloc(n) returns an address or 0 - and prints heap full; free gives it back. Stack overflow is reported and ends the program; the heap running out is reported and returns 0; globals filling memory is not reported at all.

Next

S22, Keys Without ENTER - the first section of the machine: what the keyboard sends, kbd() measured, and how a game loop reads the player without stopping.