Dynamic Memory Allocation

Question 1

Void Pointers

Answer 1

• You can’t have a value of type void:
  void v;
• But you can make a pointer to void:
  void *vPtr;
• And that void pointer can hold any pointer value you want
  float f = 3.14;
  vPtr = &f;
  long l = 123456789;
  vPtr = &l;
• But, you can’t directly dereference a void
  pointer.
  printf( “%ld\n”, *vPtr );
• Think of a void pointer as a generic way of
  holding an address
  – they could be used to point to anything
  – but, to use what they point to, you need to know its type.

Question 2

Using Void Pointers

Answer 2

• You need to convert a void * to a more specific type before you dereference.
  long *lPtr = vPtr; -> you don’t even need a cast
  printf( “%ld\n”, *lPtr );
  lPtr = (long *)vPtr; -> but, it’s probably a good idea
  printf( “%ld\n”, *lPtr );
• Void pointers are used:
  – As parameter/return types for functions that can work with memory (no matter what it stores)
  – As temporary holders for pointers of various types.

Question 3

Another Type of Memory

Answer 3

We already have two types of
memory
– Stack space : for values with a lifetime
tied to a single function execution
– Static space : for values with a lifetime
from the start to the end of the
program’s execution
* But, there’s another type of memory,
the heap
– The program says when it needs heap
memory (and how much)
– The program says when it’s done with a
particular value in heap memory
– Called: dynamic memory allocation

Question 4

Asking for Heap Memory

Answer 4

• First, you must include stdlib.h
  #include <stdlib.h></stdlib.h>
• The C Standard Library has functions to let us
  request heap memory
  void *malloc( size_t size );
  How many bytes
  do you want? -> size_t size
  Here’s a pointer
  to your memory -> Here’s a pointer to your memory

Question 5

Using malloc()

Answer 5

• To use malloc():
  – Pass in the number of bytes you need, probably using sizeof()
  – Store the result in a pointer for the type you need.
• Allocate a 1000-element array of ints:
  int *list = (int *) malloc( 1000 * sizeof(int) );
  The cast is a good idea, but a C compiler doesn’t care.
• Allocate space for a copy of a string:
  char *str2 = (char *) malloc( strlen( str ) + 1 );

Question 6

Freeing Memory

Answer 6

• You get to keep each block of dynamically
  allocated memory as long as you need.
• You must tell the C standard library when you
  are done with a block:
  void free( void *ptr );
  Pointer to previously allocated
  memory. -> void *ptr
• Typical usage:
  Allocate storage for the thing you need.
  int *list = (int *)malloc(1000 * sizeof(int));
  Use this thing, probably across
  many …
  free(list);
  … list[ 5 ] = b; …
  … different …
  … z = list[ i ]; …
  … functions.
  … list[x] = list[y];
  Free the storage, probably in some other part of your program.
  free(list);
  A Trivial Example:
  double *list = (double *)malloc(20 * sizeof(double));
  for ( int i = 0; i < 20; i++ )
  list[ i ] = i * 1.5;
  for ( int i = 0; i < 20; i++ )
  printf( “%d : %.2f\n”, i, list[ i ] );
  free( list )

Question 7

A program that reads and returns integers

Answer 7

int *readList -> here’s how we return a list of integers
int *len -> an integer passed by reference, it’s how we return the length
int *readList( int *len )
{
scanf( “%d”, len );
int *list = (int *)malloc( *len * sizeof( int ) );
for ( int i = 0; i < *len; i++ )
scanf( “%d”, list + i );
return list;
}
Client code:
* This is typical client code for readList().
int len;
int *list = readList( &len );
for ( int i = 0; i < len; i++ )
printf( “%d\n”, list[ i ] );
free( list )

Question 8

Type and Ambiguity

Answer 8

• The C type system doesn’t distinguish
  between
  – A pointer to just one value
  – A pointer to the start of a whole array.
  int *readList -> points to start of an array
  itn * len -> points to jsut one value passed by reference
  int *readList( int *len )
  {
  …

Question 9

Return Alternatives

Answer 9

• Instead returning list, with length as a
  parameter …
  int *readList( int *len )
  {
  scanf( “%d”, len );
  …
• We can return the length, with list as a
  parameter
  int readList( int **list )
  {
  int len;
  scanf( “%d”, len );
  …
  int **list -> now you have to pass the list pointer

Question 10

Using Dynamically Allocated Memory(return and syntax)

Answer 10

void *malloc( size_t size );
void free( void *ptr );
* Memory returned by malloc() is uninitialized, it may contain garbage from a previous allocation
* Returns NULL on failure (e.g., if memory is full)
* Type size_t for representing the size of storage regions
– It’s what sizeof() evaluates to
– And what printf() prints with format string “%zd”
– Just another name for an integer type (unsigned long on the common platform)

Question 11

Dynamic Allocation Hazards

Answer 11

• All previous warnings apply
  – Buffer overflow, we can accidentally read/write off the end of a dynamically allocated array.
  – Dereferencing a NULL or uninitialized pointer
• But, now there are some new ways to make
  mistakes.

Question 12

Leaking Memory

Answer 12

• What if you forget to free memory when you’re done with it?
  – That’s called a memory leak.
  – If you keep doing this, you’ll eventually run out of memory …
  – … and probably suffer a lot of performance
  degradation before you do

Question 13

Dangling Pointers

Answer 13

• Freeing memory doesn’t make your pointer
  variable go away (or set it to NULL)
• So, there’s a possibility of using a pointer to
  memory you’ve already freed.
  – This is called an dangling pointer
  – If you’re lucky, using a dangling pointer will crash your program right away.
  – If you’re unlucky, … well maybe much later.
  Security Sidebar
• CWE-416: Use After Free (UAF)
  – “Referencing memory after it has been freed can cause a program to crash, use unexpected values, or execute code”
• The freed memory may be re-allocated and
  contain values controlled by the attacker (e.g.,
  a network input)
  – Particularly bad for function pointers (more on function pointers later)

Question 14

Other Mistakes in Using Dynamically Allocated Memory

Answer 14

• Other, less common mistakes:
  – Freeing non-heap memory.
  int *p = (int []) { 5, 10, 15, 20 }; -> allocated on the stack
  …
  free( p );
  – Double-free, freeing the same memory twice.
  char *p = (char *)malloc( 1024 );
  …
  free( p );
  …
  free( p );
• CWE-415: Double Free
• Calling free() twice on the same argument can
  corrupt the memory management data
  structures
  – May cause program to crash
  – Could also cause two later calls to malloc() to
  return the same pointer (one may have data
  controlled by attacker)

Question 15

Thinking about Dynamic Allocation(C v Java)

Answer 15

• In Java, we have dynamic memory allocation;
  that’s what new does.
  – In fact, we usually have to dynamically allocate anything larger than a primitive type (int, double, char, etc.)
  – But, Java performs Garbage Collection; it
  automatically finds memory we can no longer use and reclaims it as free space.
• Standard C doesn’t perform garbage collection
• We need to tell the system when were done with each block

Question 16

Thinking about Dynamic Allocation(why use malloc/free?)

Answer 16

• Why use malloc/free?
  – When you need to store something that must live longer than a single function call.
  – When you need something with size that’s not known in advance or may need to grow.
  – When you need to store something that’s too large to put on the stack.
• But, only use it where you need it.
  – Stack and static storage can be much less expensive to allocate/free.
  – And, they may have less overhead to use.
  – And, they are easier to work with.

Question 17

Saving Strings

Answer 17

• Consider this (bad) parsing code, to read a list
  of strings.
  int readWords( char *words[],
  int capacity )
  {
  int count = 0;
  char str[ 100 ];
  while ( count < capacity &&
  scanf(“%99s”, str) == 1 ) {
  words[ count ] = str; -> problem
  count++;
  }
  return count;
  }
  Visual on google doc
• This code is better. It copies each string to its
  own memory.
  int readWords( char *words[],
  int capacity )
  {
  int count = 0;
  char str[ 100 ];
  while ( count < capacity &&
  scanf(“%99s”, str) == 1 ) {
  words[ count ] =
  (char *) malloc( strlen(str) + 1 );
  strcpy( words[ count ], str );
  count++;
  }
  return count;
  }

Question 18

Resizing Arrays

Answer 18

• Our earlier example, readList(), was easy
  – We were told how many items to expect, so we could make our array exactly the right size.
• Imagine we had to read a list of values, without knowing a priori how many there were
  – We could use a dynamically allocated array …
  – … but we’d need to be able to enlarge it if we ran out of room.
  – This is what a resizable array does
• We need to keep up with three things
  – A pointer to our array (list)
  – The number of elements used (len)
  – The capacity of the array (capacity)
• Start out with an array that’s large enough …
  for now.
• As we append items:
  – len tells us where to put the next one.
  – increment len on each append
• Everything’s easy until we reach the
  capacity.
• That’s OK. We’ll just allocate a new, larger
  array.
• Then copy everything over to the new array.
• Then, we can free the old array.
• And start using the new array instead.
• Now, you have more room to insert new
  items.
• There are a few example programs that show
  this technique

Question 19

Resizing Array(slow way)

Answer 19

int capacity = 5;
int len = 0;
int *list = (int *)malloc( capacity * sizeof( int ) );
int val;
while ( scanf( “%d”, &val ) == 1 ) {
if ( len >= capacity ) {
capacity += 1;
int *newList = (int *)malloc(capacity * sizeof(int));
for ( int i = 0; i < len; i++ )
newList[ i ] = list[ i ];
free( list );
list = newList;
}

list[ len++ ] = val;
}

Question 20

Copying Memory

Answer 20

• The C Standard Library has functions to copy
  blocks of memory.
  void *memcpy( void *dest, void const *src, size_t n );
• Here, src and dest blocks can’t overlap.
• But they can with memcpy’s slightly more
  expensive friend:
  void *memmove( void *dest, void const *src, size_t n );

Question 21

Resizing Array(better way)

Answer 21

int capacity = 5;
int len = 0;
int *list = (int *)malloc( capacity * sizeof( int ) );
int val;
while ( scanf( “%d”, &val ) == 1 ) {
if ( len >= capacity ) {
capacity *= 2;
int *newList = (int *)malloc(capacity * sizeof(int));
memcpy( newList, list, len * sizeof( int ) );
free( list );
list = newList;
}

list[ len++ ] = val;
}
More storage
overhead, but much
less time overhead.

Question 22

Meet realloc()

Answer 22

• There’s a C standard library function to help.
  void *realloc(void *ptr, size_t size);
• realloc() will enlarge your block and give you
  back the same pointer … if it can.
  void *realloc -> pointer to larger block
  void *ptr -> Pointer to previously
  allocated memory.
  size_t size -> Size you need now.
  int capacity = 5;
  int len = 0;
  int *list = (int *)malloc( capacity * sizeof( int ) );
  int val;
  while ( scanf( “%d”, &val ) == 1 ) {
  if ( len >= capacity ) {
  capacity *= 2; -> capacity
  list = (int *)realloc( list, capacity * sizeof( int ) );->Enlarge array and start
  using it. Beware, this isn’t going to
  work so well if we actually
  run out of memory
  }
  list[ len++ ] = val;
  }

Question 23

Meet calloc()

Answer 23

• There’s one more dynamic allocation function
  void *calloc(size_t count, size_t size);
  void *calloc -> Pointer to your
  memory.
  size_t count-> Number of items you
  need.
  size_t size -> Size of each item.
• Good for allocating arrays, but you don’t really need it for that.
• Returned memory is filled with zeros
  – So, calloc() may be a little more expensive.

Question 24

Performance Comparison

Answer 24

• We have three storage regions we can use
  – each with different behavior
  – .. and performance characteristics
• Let’s try out some different techniques and
  see what they cost

Question 25

Uninitialized Stack Storage

Answer 25

void f() { int a[ 1000 ]; -> Make a big array on the stack, but don’t initialize it. a[ 999 ] = 1; -> Just use it a little counter += a[ 999 ]; -> Using this to modify a global variable (so the compiler doesn’t optimize-out all this code) } int main( void ) { for ( long i = 0; i < 100000000; i++ ) -> Do this 100,000,000 times. f(); return 0; } Make a big array on the stack, but don’t initialize it. Runtime: 0.42 seconds

Question 26

Initialized Stack Storage

Answer 26

void f() { int a[ 1000 ] = {}; -> Same thing, but initializing the array. a[ 999 ] = 1; counter += a[ 999 ]; } int main( void ) { for ( long i = 0; i < 100000000; i++ ) f(); return 0; } Runtime: 9.22 seconds Uninitialized stack space is cheap, but initializing it has a cost

Question 27

Uninitialized Heap Storage

Answer 27

void f() { int *a = malloc( 1000 * sizeof( int ) ); -> This time, on the heap, uninitialized. a[ 999 ] = 1; counter += a[ 999 ]; free( a ); } int main( void ) { for ( long i = 0; i < 100000000; i++ ) f(); return 0; } Runtime: 6.31 seconds Allocating stack space is much cheaper than heap.

Question 28

Initialized Heap Storage

Answer 28

void f() { int *a = calloc( 1000, sizeof( int ) ); -> On the heap, initialized this time. a[ 999 ] = 1; counter += a[ 999 ]; free( a ); } int main( void ) { for ( long i = 0; i < 100000000; i++ ) f(); return 0; } Runtime: 16.17 seconds Initializing any memory has a cost.

Question 29

Static Storage

Answer 29

int a[ 1000 ]; -> Created once at the start of execution void f() { a[ 999 ] = 1; ->Probably, this is what makes it faster. counter += a[ 999 ]; } int main( void ) { for ( long i = 0; i < 100000000; i++ ) f(); return 0; } Runtime: 0.28 seconds You may be able to compute static addresses at compile time (depending on the OS and hardware)

Question 30

In Java

Answer 30

public class Test { static long counter = 0; static void f() { int[] a = new int [ 1000 ]; a[ 999 ] = 1; counter += a[ 999 ]; } public static void main( String[] args ) { for ( long i = 0; i < 100000000; i++ ) f(); } } In Java, all arrays are on the heap… and they’re initialized to zero … and they’re eventually garbage collected.