# Memory Allocation Using 'malloc'

CS 301 Lecture, Dr. Lawlor

## Dynamic allocation in C++

There are many ways to allocate space for an array in C or C++:
• int *arr=(int *)malloc(n*sizeof(int)); /* C/C++ "malloc" routine-- allocates given number of bytes. */
• int *arr=new int[n]; /* C++ "new" operator.   Doesn't exist in plain old C or assembly. */
• int arr[n];  /* C/C++ local variable--actually allocates space on the stack. Except on gcc/g++, "n" must be a constant! */
There are also many ways to do this in assembly.

## Stack Allocation

We've seen you can also allocate space on the stack, by just moving the stack pointer down to make room:
`sub esp,4*10; Make space on the stackmov eax, esp; Point eax to the start of that space... ; Use eax as array hereadd esp,4*10; Restore stack`
C/C++ of course can't directly access the stack pointer, but there's often a compiler-builtin function called "alloca" (which looks suspiciously like malloc!) that allocates a user-defined amount of space on the stack.  Unlike malloc, memory allocated with alloca is automatically freed when the function returns.  "alloca" may not exist on all machines, since some machines have rather funky stacks.

## Malloc and Free

Other than the stack, the most common memory allocation method is to call malloc and free.  "malloc" is a C function that takes one parameter, the number of bytes to allocate, and returns a pointer to the allocated memory.  You can then use the pointer like an array, or struct, or whatever you like.  "free" takes one parameter, the pointer to the allocated memory to free (which has to come from malloc--you'll get a bizarre crash if you free a stack pointer!).  Here's how you call "malloc" and "free" in assembly:
`push 4*10; Number of bytes to allocateextern malloccall mallocadd esp,4; Undo "push"; Malloc's return value, a pointer, comes back in eax.... ; use eax as array here; Eventually, you'll need to call "free" to release that memory:push eaxextern freecall freeadd esp,4; Undo "push"`

## Fixed Allocation

Finally, you can allocate space in the initialized (".data") or uninitialized (".bss") section of your executable file:
`mov eax,thingy; Point eax to thingy's data...section .bss; <- Uninitialized (but writeable!) data areathingy:	resb 4*10; Reserve this many bytes of space here`

Any of these allocation schemes will work, and the pointer you end up with is just plain old memory.  But there are tradeoffs in deciding which memory allocation scheme to use.  Malloc is slow and a pain to use, but offers the most possible memory (gigabytes).  The stack is very fast, but must be given back at the end of your subroutine, and is limited to a few megabytes on many machines.  Initialized or uninitialized data is a fixed size, and always allocated; this is a waste of space unless you're storing small objects of a few kilobytes.

 Allocation Method Allocation Speed Storage Available Assembly Example Disadvantages malloc/free Slow (100ns) Gigabytes push 100 call malloc Must remember to call free stack or alloca Fast (1ns) Megabytes sub esp,100 mov eax,esp Must remember to move stack pointer back; storage is limited to stack size; alloca() not always available in C/C++ "section" Not needed (fixed allocation!) Megabytes mov eax,my_pointer my_pointer:     resb 100 Wastes space even when not in use; usually not "threadsafe"

One all-too-common problem in C++ is accessing beyond the end of the memory you're allowed to touch.  For example, this buggy program actually seems to run fine:
`int n=read_input();int *arr=(int *)malloc(n); /* OOPS!  n bytes, not n ints! */std::cout<<"Arr runs from "<<arr<<" to "<<arr+n<<"\n";for (int i=0;i<n;i++) arr[i]=i;iarray_print(arr,n);std::cout<<"OK, done with arr--freeing it.\n";free(arr);`

(Try this in NetRun now!)

The problem is this trashes 3*n bytes of heap memory, but if you're "lucky" nobody's using those bytes, and your program survives.  It will crash eventually, though, usually after some other code is added/changed.  This code only crashes (when the guilty array is freed) once you add some innocent pointer manipulation elsewhere in the program:
`int *innocent=(int *)malloc(sizeof(int));*innocent=3;std::cout<<"Innocent pointer at "<<innocent<<"\n";int n=read_input();int *arr=(int *)malloc(n); /* OOPS!  n bytes, not n ints! */std::cout<<"Arr runs from "<<arr<<" to "<<arr+n<<"\n";for (int i=0;i<n;i++) arr[i]=i;iarray_print(arr,n);std::cout<<"OK, done with arr--freeing it.\n";free(arr);if (*innocent!=3) std::cout<<"Innocent bystander shot like moose!(page A3)\n";std::cout<<"Freeing innocent bystander\n";free(innocent);`

(Try this in NetRun now!)

You can get an immediate crash on accessing off the end of your memory by linking with "electric fence", a cool little library by Bruce Perens.  Just link with "-lefence".  On Linux, valgrind is similar but doesn't even require re-linking.
`int n=read_input();int *arr=(int *)malloc(n); /* OOPS!  n bytes, not n ints! */std::cout<<"Arr runs from "<<arr<<" to "<<arr+n<<"\n";for (int i=0;i<n;i++) arr[i]=i;iarray_print(arr,n);std::cout<<"OK, done with arr--freeing it.\n";free(arr);`

(Try this in NetRun now!)

If you're getting weird crashes in a big C/C++ program, it's quite possible that somebody's overwriting memory!  This is one place where the explicit array size checks built into Java or C# really shine--you can't corrupt the heap in those languages, because every array access verifies that the index is in-bounds.  Of course, those extra checks can take some time, so those languages can be a bit slower than C++.

## Explict Array Size Checking in C++

You can actually check your array indices in C++, if you're willing to build your own array class:
`class myArray {	int *arr;	int length;public:	myArray(int n) {		arr=(int *)malloc(n*sizeof(int));		length=n;	}	int & operator[] (int index) {		if (index<0 || index>=length) 		{ /* out of bounds! */		  std::cout<<"I'm very sorry, but you've gone out of bounds.\n";		  std::cout<<"  Your index "<<index<<" is more than the array length "<<length<<".\n";		  exit(1);		}		return arr[index];	}};int n=read_input();myArray a(n);a[1]=123;a[n+1]=1234;return a[1];`

(Try this in NetRun now!)