Data representation 4: Dynamic allocation, invariants

Overview

Today, we’ll use the problem set to explore alignment, dynamic allocation, invariants, tests, and internal metadata.

Problem set comment

After memory reuse, your m61_malloc might use a helper function like this:

static void* m61_find_free_space(size_t sz) {
    // do we have a freed allocation that will work?
    for (allocation& a : freed allocation set) {
        if (a is at least sz bytes big) {
            void* ptr = first byte in a;
            remove a from freed allocation set;
            return ptr;
        }
    }
    // otherwise fail
    return nullptr;
}

Specifications

• A specification for a function is a high-level, but ideally precise, description of its desired behavior
• Ideally a specification says what a function does, not how it does it
  • Allows optimizations
• If a function implementation disagrees with its specification, that’s a bug
• We often write specifications before function definitions in a comment

/// m61_malloc(sz, file, line)
///    Returns a pointer to `sz` bytes of freshly-allocated dynamic memory.
///    The memory is not initialized. If `sz == 0`, then m61_malloc may
///    return either `nullptr` or a pointer to a unique allocation.
///    The allocation request was made at source code location `file`:`line`.

• What is missing from this specification, if anything?
• Write a specification for m61_find_free_space!

m61_find_free_space specification

• m61_malloc performs an allocation, but does other work too
  • Maintains statistics
  • Checks for integer overflow
  • Rounds allocation size up to ensure alignment
• m61_find_free_space just allocates space
  • Solves a smaller, more targeted problem
  • May simplify m61_malloc

/// m61_find_free_space(sz)
///    Allocates a block of `sz` bytes and returns a pointer to that block.
///    Returns `nullptr` on failure. The newly-allocated block does not
///    overlap with any other concurrently-allocated block.

Handout code

void* m61_malloc(size_t sz, const char* file, int line) {
    (void) file, (void) line;   // avoid uninitialized variable warnings
    // Your code here.
    if (default_buffer.pos + sz > default_buffer.size) {
        // Not enough space left in default buffer for allocation
        return nullptr;
    }

    // Otherwise there is enough space; claim the next `sz` bytes
    void* ptr = &default_buffer.buffer[default_buffer.pos];
    default_buffer.pos += sz;
    return ptr;
}

• Can we refactor a version of m61_find_free_space out of this code?

Rewritten m61_malloc

void* m61_find_free_space(size_t sz) {
    if (default_buffer.pos + sz <= default_buffer.sz) {
        void* ptr = &default_buffer.buffer[default_buffer.pos];
        default_buffer.pos += sz;
        return ptr;
    }
    return nullptr;
}

void* m61_malloc(size_t sz, const char* file, int line) {
    void* ptr = m61_find_free_space(sz);
    return ptr;
}

• How to add statistics collection?

Adding statistics

void* m61_find_free_space(size_t sz) {
    if (default_buffer.pos + sz <= default_buffer.sz) {
        void* ptr = &default_buffer.buffer[default_buffer.pos];
        default_buffer.pos += sz;
        return ptr;
    }
    return nullptr;
}

void* m61_malloc(size_t sz, const char* file, int line) {
    void* ptr = m61_find_free_space(sz);
    if (ptr) {
        global_statistics.ntotal += 1;
        global_statistics.total_size += sz;
        global_statistics.nactive += 1;
        global_statistics.active_size += sz;
    } else {
        global_statistics.nfail += 1;
        global_statistics.fail_size += sz;
    }
    return ptr;
}

• How to add alignment?

Alignment sidebar

Sizes of primitive types on x86-64

Standard sizes of primitive types

Alignment

• Hardware and compilers can impose restrictions on the addresses at which certain types of object can appear
  • The address of any int is a multiple of 4 (on x86-64)
  • The address of any pointer is a multiple of 8
• This is called alignment
• The C++ alignof operator returns the alignment of a type or object
  • All objects of the same type have the same alignment
  • alignof(std::max_align_t) is the maximum alignment for any type (16 on x86-64)

Alignments of primitive types

• Except for alignof(char), these values can change
  • On some x86-64 operating systems and compilers, alignof(long) = 4!
  • On x86-32 Linux, alignof(double) = 4
  • On Apple Silicon, alignof(std::max_align_t) = 8

Inductive alignment

• The alignment rule (from the problem set): “malloc(sz) returns memory whose alignment works for any object.”
• This means that every non-null pointer returned by m61_malloc must have a numeric address value evenly divisible by alignof(std::max_align_t)
• May require leaving little gaps between allocations
  • Consider m61_malloc(1)
  • These gaps are called fragmentation
• The initial value of default_buffer.buffer is always correctly aligned
  • assert(reinterpret_cast<uintptr_t>(default_buffer.buffer) % alignof(std::max_align_t) == 0)
• Is there an easy way to ensure later allocations are also aligned?

Adding alignment

void* m61_find_free_space(size_t sz) {
    if (default_buffer.pos + sz <= default_buffer.sz) {
        void* ptr = &default_buffer.buffer[default_buffer.pos];
        default_buffer.pos += sz;
        return ptr;
    }
    return nullptr;
}

void* m61_malloc(size_t sz, const char* file, int line) {
    size_t alignment_space = /* YOUR CODE HERE */;
    size_t aligned_sz = sz + alignment_space;
    void* ptr = m61_find_free_space(aligned_sz);
    if (ptr) {
        global_statistics.ntotal += 1;
        global_statistics.total_size += sz;
        global_statistics.nactive += 1;
        global_statistics.active_size += sz;
    } else {
        global_statistics.nfail += 1;
        global_statistics.fail_size += sz;
    }
    return ptr;
}

Checking your arithmetic

• Computing alignment_space is a little tricky!
• What are some facts that should always hold for alignment_space?
• Why not add code to assert those facts?

Reusing memory

• Extend our m61_find_free_space to handle memory reuse (pseudocode)

void* m61_find_free_space(size_t sz) {
    if (default_buffer.pos + sz <= default_buffer.sz) {
        // can perform allocation using default buffer
        void* ptr = &default_buffer.buffer[default_buffer.pos];
        default_buffer.pos += sz;
        return ptr;
    }

    // otherwise, try previously-freed allocations
    for (allocation& a : freed allocation set) {
        if (a is at least sz bytes big) {
            void* ptr = first byte in a;
            remove a from freed allocation set;
            return ptr;
        }
    }

    return nullptr;
}

Questions about allocation reuse

• How to represent freed allocation set?
• How to populate freed allocation set?
• How do these data structures relate?
  • What invariants can we write to relate them?