Problems with Pointer - and Some Solutions

Three Possible Kinds of Errors

• We will look at three kinds of errors that can happen with pointers:
1. Null reference
2. Garbage creation (ie memory leak)
3. Dangling reference

Null Pointers

Error 1: Null Pointers

• What happens here?

    type Box is ...
    type BoxPtr is access Box;

    b1: Box := (2, 3);
    p1: BoxPtr;
begin
    p1.all := b1;

    put(p1.all.w);
    

Null Exclusion

• Reduce the problem with a null exclusion - catch the error earlier

    type Box is ...
    type BoxPtr is access Box;

    p0: BoxPtr;           -- compiles and p0 is null
    p1: not null BoxPtr;  -- does not compile
    p2: not null BoxPtr := new Box;  -- initialization required
begin
    p2 := p1;    -- Would be okay, if p1 compiled
    p2 := p0;    -- Run time error
    

Null Exclusion in Type Declarations

• Null exclusion can be used in type declarations

    type Box is ...
    type NN_BoxPtr is not null access Box;

    -- Must be initialized
    nnbp: NN_BoxPtr := new Box;
    ...
    dispose(nnbp);   -- but this is an error
                   -- dispose deallocates and sets bp to null
    

• Problem: Can nnbp be deallocated
• Solution:

    type Box is ...
    type BoxPtr is access Box;

    subtype NN_BoxPtr is not null access Box;

    bp: BoxPtr;       -- Can be deallocated
    nnbp: NN_BoxPtr;  -- Can not be deallocated
     ...
    bp := nnbp;
    dispose(bp);
    

Null Exclusion in Parameter Declarations

• Null exclusion can be used in parameter declarations

    type Box is ...
    type BoxPtr is access Box;

    procedure foo(nnbp: Not Null BoxPtr) is
    

Something Similar in Java?

• What is something similar in Java?

Garbage Creation and Memory Leak

Garbage: Definition, and the Freelist

• Garbage: Memory that is allocated to a program but is not accessible by the program
• An anonymous variable that has no pointers to it

Error 2: Creating Garbage

• In Java, how can we create garbage:

    Foo f;

    f = new Foo();
    f = new Foo();
    

• In Ada the same code creates garbage, too:

    declare
        f: FooPtr:
    begin
        f := new Foo;
        f := new Foo;
    

Garbage Collection and Memory Leaks

• In Java, what happens to garbage?


• In Ada, in most systems garbage creates a memory leak:
• Memory leak: increasing amounts of unreachable memory
• Some Ada systems have garbage collection
• Available on systems whose compilers generate byte code
• But garbage collected Ada systems is rare
• GC can be problematic on real time systems
• Garbage collection can take time (First Garbage collector: John McCarthy and LISP and poor timing)

Garbage, Explicit Deallocation, and the Freelist

• The runtime system maintains a list of memory that is available to be allocated to your program
• Called the "Freelist"
• Initially, the entire heap is on the freelist


• When a block of memory is allocated from the heap, it is removed from the freelist


• To avoid creating garbage we return a block of memory to the freelist before destroying all pointers to it.
• Returning a block of memory to the freelist is called "deallocating" the block of memory


• In Ada the programmer avoid garbage with explicit deallocation of heap variables

Two Algorithms for Collecting Garbage

1. Mark and Sweep:
1. Follow all pointers and mark all reachable cells
2. Look at all cells and free cells that are not marked


2. Copy Collection:
1. Only use half of heap space at a time
• Assume currently allocating cells from half one
2. To collect garbage: Follow all pointers and copy reachable cells from half one to half two
3. Now allocate cells from half two

Avoid Garbage with Explicit Deallocation of Memory

• To deallocate an anonymous variable of a specific type,
• we must create a deallocation procedure specific for


• Create the deallocation procedure by instantiating a generic procedure Unchecked_Deallocation for the specified type
• Example: procedure dispose is new Unchecked_Deallocation(Box, BoxPtr)


• Then use the deallocation routine as required
• Example: dispose(p);


• Example: boxdispose.adb (prettified)


• Other points:
• You can choose any name - free is another common name
• Two params needed to instantiate dispose, one needed to call it
• Separate Deallocation routine required for each pointer type
• Deallocation sets pointer to null
• Deallocation of null is okay

Stack-Based Allocation

• Problem of garbage is minimized with stack-based allocation


• In Java, arrays are allocated on the heap, meaning that GC is required


• In Ada, arrays that are local variables are allocated on the stack
• Thus, deallocation is automatic on exit from procedure (or block).

Controlled Types

• Controlled types: control what happens on assignment
• Can automatically reclaim on assignment


• Example: Unbounded_String
• Example - Read entire file into one string

        u: Unbounded_String := Null_Unbounded_String;
        ... 
        while not end_of_file loop
           u := u & get_line & ASCII.NL; 
      

• Each old value of u is automatically reclaimed on assignment

Storage Pools

• Problem of garbage is minimized with storage pools


• A storage pool is a dynamically allocated area of memory from which other objects can be be allocated
• Like a heap that is dedicated to a particular procedure


• Example:

    procedure main is 
        procedure something is 

            type Node is ...
            type Node_Pointer is access Whatever;

            -- Create a storage pool type
            type Some_Storage_Pool_Type is new Storage_Pools.Root_Storage_Pool;

            -- Create the storage pool itself
            Pool_Object : Some_Storage_Pool_Type;

            -- Specify the storage pool to use for automatic allocation
            for Node_Pointer'Storage_Pool use Pool_Object;

            -- An allocation that goes in the pool
            N : Node_Pointer := new Node;

    

• Pool_Object is automatically deallocated on exit from the procedure

Dangling References (and Aliases)

Error 3: Dangling References

• Dangling References are the result of having explicit deallocation and aliases


• Before looking at Dangling References, we need to understand Aliases

Aliases

• Alias: alternate name for a variable


• Pointers are a common way to create an alias


• Example

    type Box ...
    type BoxPtr is access Box;

    p, q: BoxPtr;
begin
    p := new Box'(1, 2);

    q := p;
    

• What is another way that aliases are created?
• Think procedures


• Aliases are unavoidable, but they also cause problems
• Make debugging difficult:

        p := new Box(1, 2);

        q := p;

        q.w := 99;

        put_line(p);  -- What gets printed?
        

Dangling References

• Dangling Reference: pointer to memory that is invalid

    p, q: BoxPtr;
begin
    p := new Box'(1, 2);
    q := p;

    dispose(q);

    put_line(p);     -- output unpredictable
    

• Invalid memory could be
• memory that is no longer allocated
• reallocated memory of correct or incorrect type

Dangling References and Reallocated Memory

• Sometimes new (re)allocates the most recently deallocated memory


• Example danglingref.adb (prettified)

    p, q: BoxPtr;
begin
    p := new Box'(1, 2);
    put_line(p);     -- output: 1 2

    q := p;          -- Create an alias

    dispose(q);

    put_line(p);     -- output unpredictable (example: 0 2)

    q := new Box'(3, 4);

    -- p may be an alias to the new object
    put_line(p);     -- may output 3 4

    p.all.w := 99;   -- What does this modify?

    put_line(q);     -- may output 3 99
    

Dangling References and Reallocation of Different Types

• Reallocation can cause havoc with types
• Example:

    p, q: BoxPtr;
    r: PersonPtr;
begin
    p := new Box'(1, 2);
    q := p;

    dispose(q);

    put_line(p);     -- outputs 1 2

    r := new Person;

    -- What does this do to Person r?
    p.all.w := 99;

    

Avoiding Dangling References

• Two possibilities when deallocating q with alias p:
1. Pointer p is still needed
• In this case, deallocation of q is an error


2. Pointer p is not needed
• Can set it to null before deallocation
• Requires keeping track of aliases, which is difficult
• Java will not deallocate this object

Avoiding Dangling References with Aliases

• Dangling References can't occur if it's impossible to create aliases


• Limited private types can't have aliases

Summary of Errors

• Watch out for several pointer errors:


1. Dereference a null pointer
• Note that pointer variables have default value null


2. Creating garbage
• Garbage is a memory location that is allocated but is unaccessible (ie has no pointers to it)
• How to avoid (when no garbage collection): explicit deallocation


3. Dangling reference
• A dangling reference is a pointer to invalid memory
• Avoid by setting alias pointers to null prior to deallocating other aliases