Memory Models and Dynamic Memory

Recall that an object is a piece of data in memory, located at some address in memory. An object also has a storage duration that determines its lifetime. In this course, we consider three storage durations:

• static: the lifetime is essentially the whole program

• automatic (also called local): the lifetime is tied to a particular scope, such as a block of code

• dynamic: the object is explicitly created and destroyed by the programmer

The first two durations are controlled by the compiler, and an object with static or automatic scope is associated with a variable. Objects with dynamic storage are managed by the programmer, and they are not directly associated with variables.

The following variables refer to objects with static storage duration:

• global variables [1]

• static member variables

• static local variables

[1]

Also those defined at namespace scope.

The lifetime of these objects is essentially the whole program, so they can be used at any point in time in the program. [2]

[2]

Initialization in C++ is rather complicated, and the details are beyond the scope of this course. A relatively safe assumption is that variables with static storage duration can be initialized in any order before main() is run, but that they have all been initialized by the time main() is called.

Static Local Variables

We have already seen global and static member variables. A static local variable is a local variable declared with the static keyword. Rather than living in the activation record for a function call, it is located in the same region of memory as other variables with static storage duration, and there is one copy of each static local variable in the entire program. The following is an example:

int count_calls() {
  static int count = 0;
  return ++count;
}

int main() {
  cout << count_calls() << endl;    // prints 1
  cout << count_calls() << endl;    // prints 2
  cout << count_calls() << endl;    // prints 3
  cout << count_calls() << endl;    // prints 4
}

The count static local variable is initialized to 0, so its value is 0 the first time count_calls() is called. The call increments count and returns the new value of 1. The next time count_calls() is called, count has value 1. It gets incremented again, and the call returns 2. And so on. Thus, all calls to count_calls() use the same count object, unlike a non-static local variable, where each call would get its own object.

Automatic Storage Duration

Function parameters and local variables have automatic storage duration, also called local storage duration. The lifetime of the associated object corresponds to the variable’s scope, the region of code where it is valid to refer to the variable. The scope of a variable begins at its point of declaration and ends at the end of the scope region in which it is defined. A scope region can be the body of a function, a whole loop or conditional, the body of a loop or conditional, or just a plain block denoted by curly braces. For example, consider the following code:

void func(int x) {
  for (int i = 2; i < 10; ++i) {
    string s = " cats";
    cout << i << s << endl;
  } // end scope of i, s

  int y = 10;

  {
    int z = -3;
    cout << x << " " << y << " " << z << endl;
  } // end scope of z

} // end scope of x, y

The variables fall into the following categories;

• The scope of a parameter is the entire function body. Thus, the lifetime of the object associated with x begins when the function is called and ends when the function returns.

• The scope of a variable declared in a loop header is the entire loop. Thus, the lifetime of the object i begins when the loop starts and ends when the loop exits.

• The scope of a variable declared within a block is from its point of declaration to the end of the block. The lifetime of s begins when its initialization runs and ends at the end of a loop iteration – a new object associated with s is created in each iteration. The lifetime of y also begins when its initialization runs, and it ends when the function returns. Lastly, the lifetime of z starts when its declaration is run and ends when the code exits the block containing z‘s declaration.

Scope generally prevents us from using a local variable beyond the lifetime of its associated object. However, indirection through a pointer or reference can circumvent this protection. The following is an example:

int *func1() {
  int x = 3;
  return &x;
}

void func2() {
  int y = 5;
}

int main() {
  int *z = func1();
  func2();
  assert(*z == 3);  // ASSERTION FAILURE
}

Figure 50 Returning the address of a local variable results in a pointer that refers to a dead object. Dereferencing the pointer produces undefined behavior.

When the program calls func1(), it places the activation record on the stack, with x inside of the activation record. The call returns the address of x, which gets stored in z. However, when the call returns, its activation record is destroyed, so z is actually pointing at a dead object. The memory for that activation record can then be reused for something else – in the case of Figure 50, the activation record for func2(), placing y at the same address used for x. Dereferencing z results in undefined behavior; in this case, since the memory was reused for y, dereferencing z results in the value 5, not 3.

There are cases, however, where we want an object’s lifetime to last beyond the execution of the function that creates it. Previously, we saw the factory pattern, where a factory function creates an object and returns its address. We used the new operator to decouple the lifetime of the object from the duration of the function call:

Bird * Bird_factory(const string &color, const string &name) {
  if (color == "blue") {
    return new BlueBird(name);
  } else if (color == "black") {
    return new Raven(name);
  }
  ...
}

Address Space

The new operator creates an object not in some activation record, but in an independent region of memory called the heap. The stack and heap are two of the segments that make up a program’s address space, which is the total memory associated with a running program. Figure 51 depicts a typical layout for an address space.

Figure 51 The address space of a program.

The text segment contains the actual machine instructions representing the program’s code, and it is often placed at the bottom of a program’s address space. (Nothing is located at address 0, since that is the representation used for a null pointer.) Space for objects in static storage generally is located above the text segment, followed by the heap. The latter can grow or shrink as objects in dynamic memory are created and destroyed; in most implementations the heap grows upward as needed, into the empty space between the heap and stack. The stack starts at the top of the address space, and it grows downward when a new activation record is created.

The new and delete Operators

The syntax of a new expression consists of the new keyword, followed by a type, followed by an optional initialization using parentheses or curly braces. The following are examples:

// default initialization
new int;
// value initialization
new int();
new int{};
// explicit initialization
new int(3);
new int{3};

If no initialization is provided, the newly created object is default initialized. For an atomic type, nothing is done, so the object’s value is whatever is already there in memory. For a class type, the default constructor is called.

Empty parentheses or curly braces result in value initialization. For an atomic type, the object is initialized to a zero value. For a class type, the default constructor is called.

Explicit initialization can be done by supplying values in parentheses or curly braces. For atomic types, the value is used to initialize the object. For C-style ADTs, curly braces must be used, and the values within are used to initialize the member variables. For C++ ADTs, both parentheses and curly braces invoke a constructor with the values within as arguments.

A new expression does the following:

• Allocates space for an object of the given type on the heap.

• Initializes the object according to the given initialization expression.

• Evaluates to the address of the newly created object.

The address is how we keep track of the new object; it is not associated with a variable name, so we have to store the address somewhere to be able to use the object.

int main() {
  int *ptr = new int(3);
  cout << *ptr << endl;   // prints 3
  ...
}

Figure 52 A new expression creates an object on the heap and evaluates to its address.

The newly created object’s lifetime is not tied to a particular scope. Rather, it begins when the new expression is evaluated and ends when the delete operator is applied to the object’s address.

delete ptr;

Here, the operand to delete evaluates to the address value contained in ptr. The delete operator follows this address and destroys the object at that address.

Figure 53 Applying delete to an address in dynamic memory kills the object that lives at that address.

The expression delete ptr; does not kill the ptr object – it is a local variable, and its lifetime ends when it goes out of scope. Rather, delete follows the pointer to the object it is pointing to and kills the latter. We can continue to use the pointer object itself:

int main() {
  int *ptr = new int(3);
  cout << *ptr << endl;   // prints 3
  delete ptr;             // kills *ptr, not ptr itself
  ptr = new int(-1);
  cout << *ptr << endl;   // prints -1
  delete ptr;             // kills *ptr, not ptr itself
}                         // ptr dies here, since it is going out of scope

Dynamic Arrays

We saw previously that local and member-variable arrays must have a size that is known at compile time, so the compiler can reason about the sizes of activation records and class-type objects. This restriction does not apply to dynamic arrays – since they are located on the heap rather than in an activation record or directly within a class-type object, the compiler does not need to know their size.

The syntax for creating a dynamic array is the new keyword, an element type, square brackets containing an integer expression, and an optional initializer list. The expression within the square brackets need not be a compile-time constant:

int main() {
  cout << "How many elements? ";
  int count;
  cin >> count;
  int *arr = new int[count];
  for (int i = 0; i < count; ++i) {
    arr[i] = i;
  }
  ...
}

A new array expression does the following:

• Allocates space for an array of the given number of elements on the heap.

• Initializes the array elements according to the given initialization expression. If no initialization is provided, the elements are default initialized.

• Evaluates to the address of the first element of the newly created array.

Previously, we saw that a local or member-variable array decays to a pointer to its first element when the array’s value is required. A dynamic array immediately decays as part of the new array expression, so the expression evaluates to the address of the first element.

Figure 54 illustrates memory at the end of the code snippet above.

Figure 54 A new array expression creates an array on the heap and evaluates to the address of its first element.

As with any pointer into an array, we can use the subscript operator to index into the array:

arr[i] = i;

This is equivalent to:

*(arr + i) = i;

The lifetime of a dynamic array begins when it is created by a new array expression. It ends when the array-deletion operator delete[] is applied to the address of the array’s first element:

delete[] arr;

Though the type of arr is int *, we cannot use the regular delete operator on it; instead, we must inform the program with delete[] that we intend to delete a dynamic array, not just a single object on its own.

Using the wrong deletion operator results in undefined behavior. It is also undefined behavior to apply delete[] to anything other than the address of the first element of a dynamic array.

We cannot delete an individual element of an array. The lifetime of an array’s elements are tied to the lifetime of the array as a whole; they are born when the array as a whole is born and die when the array dies.

Lifetime of Class-Type Objects

When a class-type object is created, a constructor is run to initialize it. [3] When a class-type object dies, its destructor is run to clean up its data. For a local object, this is when the associated variable goes out of scope. For a dynamic object, it is when delete is applied to its address.

[3]

The exception is aggregates (C-style ADTs) that are initialized directly with an initializer list.

If a class-type object is an element of an array, it dies when the array dies, so its destructor runs when the array is dying.

The lifetime of member variables of a class-type object is tied to the lifetime of the object as a whole. When the object dies, its members die as well; if they are of class-type themselves, their destructors run. Specifically, the members of a class-type object are automatically destroyed after the destructor of the object is run, in reverse order of their declarations. The following is an example:

class M {
public:
  M(const string &s) : mstr(s) {
    cout << "M ctor: " << mstr << endl;
  }

  ~M() {
    cout << "M dtor: " << mstr << endl;
  }

private:
  string mstr;
};

class C {
public:
  C(const string &s) : cstr(s), m1(s + ".m1"), m2(s + ".m2") {
    cout << "C ctor: " << cstr << endl;
  }

  ~C() {
    cout << "C dtor: " << cstr << endl;
  }

private:
  string cstr;
  M m1;
  M m2;
};

int main() {
  C c1("c1");
  C *cptr = new C("(*cptr)");
  C c2("c2");
  delete cptr;
}

This prints the following when run:

M ctor: c1.m1
M ctor: c1.m2
C ctor: c1
M ctor: (*cptr).m1
M ctor: (*cptr).m2
C ctor: (*cptr)
M ctor: c2.m1
M ctor: c2.m2
C ctor: c2
C dtor: (*cptr)
M dtor: (*cptr).m2
M dtor: (*cptr).m1
C dtor: c2
M dtor: c2.m2
M dtor: c2.m1
C dtor: c1
M dtor: c1.m2
M dtor: c1.m1

When main() is run, the declaration of c1 creates a C object and calls its constructor. The latter first initializes the members m1 and m2 in order before running the body of C‘s constructor. Thus, we get the output:

M ctor: c1.m1
M ctor: c1.m2
C ctor: c1

The code then constructs a C object in dynamic memory, resulting in:

M ctor: (*cptr).m1
M ctor: (*cptr).m2
C ctor: (*cptr)

It then creates another local C object:

M ctor: c2.m1
M ctor: c2.m2
C ctor: c2

The program proceeds to apply delete to the address of the dynamic C object, which causes its destructor to run. The body of ~C() runs first, and then the members are destroyed in reverse order:

C dtor: (*cptr)
M dtor: (*cptr).m2
M dtor: (*cptr).m1

The string cstr is also destroyed, since it is a class-type object, and it is destroyed after m1. However, the string destructor doesn’t print anything out, so we do not see it in the output.

The order in which the bodies of the destructors are run is the reverse of the constructors – we get the same “socks-and-shoes” ordering that we saw with base-class and derived-class constructors and destructors.

When execution reaches the end of main(), both c1 and c2 go out of scope, so their associated objects are destroyed in reverse order of construction. Thus, c2 dies first, followed by c1:

C dtor: c2
M dtor: c2.m2
M dtor: c2.m1
C dtor: c1
M dtor: c1.m2
M dtor: c1.m1

Dynamic-Memory Errors

The compiler manages objects with static and automatic storage duration, and the management of subobjects is directly tied to the objects that contain them. Dynamic objects, on the other hand, must be explicitly managed by the programmer. Improper management can result in many kinds of errors that are unique to dynamic memory.

The most common error with dynamic memory is a memory leak, where a program is no longer in need of a dynamic object but has failed to delete it. The usual cause of a memory leak is orphaned memory, when we lose track of a dynamic object, inevitably resulting in a leak. The following is an example:

void func1() {
  double *ptr = new double(3.0);
}

int main() {
  func1();
  ...
}

When func1() is called, it allocates a dynamic object and stores its address in the local variable ptr. When func1() returns, its activation record is destroyed and ptr dies. Thus, the program no longer knows the address of the dynamic object that func1() created – the object has been orphaned, and there is no way to get to it to delete it. Thus, the corresponding memory is leaked.

The solution is to apply delete to the address before we lose track of it:

void func1() {
  double *ptr = new double(3.0);
  delete ptr;
}

int main() {
  func1();
  ...
}

Memory leaks result in a program using more memory than it needs. This is problematic on systems that run more than one program at once, which is the case for most machines – it reduces the amount of physical memory available to the other programs, potentially slowing them down. It is our responsibility as programmers to write well-behaved programs that avoid memory leaks.

Another memory error is a double free, also called a double delete, where a program deletes the same object more than once:

void func2() {
  int x = 0;
  int *ptr1 = new int(1);
  int *ptr2 = new int(2);
  ptr2 = ptr1;

  delete ptr1;
  delete ptr2;
}

Here, the second dynamic int is orphaned by the assignment ptr2 = ptr1. The program then applies delete to the same address twice; this is a double free, which results in undefined behavior.

Another category of errors is a bad delete, which is when a delete operator is applied to the wrong kind of address. This includes applying delete to the address of a non-dynamic object and applying delete[] to anything other than the address of the first element in a dynamic array. The result of a bad delete is undefined behavior.

Deleting a dynamic object is not enough to avoid a memory error. If we keep around its address, we have a dangling pointer – a pointer that points to a dead object. If we then dereference the pointer, we get undefined behavior. The following is an example:

void func3() {
  int *ptr = new int(42);
  cout << *ptr << endl;
  delete ptr;

  int *ptr2 = new int(3);
  cout << *ptr << endl;    // oops
  delete ptr2;
}

In this code, we have accidentally dereferenced ptr after applying delete to it. The object it is pointing at is dead, and the memory may have been reused for something else.

We can avoid dangling pointers by restricting the scope of a pointer to the region of code where it is expected to be used [4]. One way to do so is by moving that code into its own block, as in the following:

void func3() {
  {
    int *ptr = new int(42);
    cout << *ptr << endl;
    delete ptr;
  }

  int *ptr2 = new int(3);
  cout << *ptr << endl;    // oops
  delete ptr2;
}

Now ptr is no longer in scope when we mistakenly access it, and the compiler will detect this and give us a meaningful error.

[4]

An alternative strategy is to set a pointer to null after applying delete to it. Dereferencing a null pointer still results in undefined behavior, but implementations almost universally detect this, resulting in a segmentation fault or a bad access. However, there are two downsides to this strategy. First, it complicates the code, making it harder to read and maintain. Second, deleting a null pointer is valid in C++ – it has no effect. This means that if we set a pointer to null and then subsequently delete it a second time, we will not encounter an error. However, this may hide a logic bug – perhaps we expected the pointer to still be alive even though it was deleted earlier, in which case we would prefer a visible error from a double delete rather the code passing our test cases. For these reasons, it is better to rely on scoping to detect dangling pointers at compile time rather than relying on runtime checks.

Uses for Dynamic Memory

Dynamic memory adds another use for indirection through a pointer or reference. Since a dynamic object is not directly associated with a variable, we are forced to interact with the object indirectly.

We have already seen two uses for dynamic memory:

• The factory pattern, where a factory function creates objects of specific derived types based on runtime information.

• Dynamic arrays, where the size can be determined at runtime.

The factory pattern is an example of decoupling the lifetime of an object from a particular scope. Next time, we will make use of dynamic arrays to build a container ADT without a fixed maximum capacity; we will do so by decoupling the storage for the container’s elements from that of the container itself. However, we will see that this results in nontrivial memory-management issues, and we will learn how to address them.