Memory Management and Safety

Relevant source files

• src/lib.rs

This document details the memory management strategies and safety mechanisms employed by the FlattenObjects container. It covers the use of uninitialized memory, unsafe operations, and the critical safety invariants that ensure memory safety despite storing objects in a fixed-capacity array.

For information about the ID management system that works alongside these memory safety mechanisms, see ID Management System. For details about the public API that maintains these safety guarantees, see Object Management Operations.

Memory Layout and Data Structures

The FlattenObjects container uses a carefully designed memory layout that balances performance with safety in no_std environments.

Core Memory Components

flowchart TD
subgraph subGraph2["Safety Invariants"]
    invariant1["If bitmap[i] == true, then objects[i] is initialized"]
    invariant2["If bitmap[i] == false, then objects[i] is uninitialized"]
    invariant3["count == number of true bits in bitmap"]
end
subgraph subGraph1["Memory States"]
    uninit["MaybeUninit::uninit()"]
    init["MaybeUninit with valid T"]
    bitmap_false["Bitmap bit = false"]
    bitmap_true["Bitmap bit = true"]
end
subgraph subGraph0["FlattenObjects"]
    objects["objects: [MaybeUninit; CAP]"]
    id_bitmap["id_bitmap: Bitmap"]
    count["count: usize"]
end

bitmap_false --> invariant2
bitmap_true --> invariant1
count --> invariant3
id_bitmap --> bitmap_false
id_bitmap --> bitmap_true
objects --> init
objects --> uninit

Sources: src/lib.rs(L44 - L51) 

The container maintains three core fields that work together to provide safe object storage:

MaybeUninit Usage Pattern

The container uses MaybeUninit<T> to defer object initialization until actually needed, avoiding the overhead of default initialization for the entire array.

Sources: src/lib.rs(L79)  src/lib.rs(L227)  src/lib.rs(L255)  src/lib.rs(L286 - L287)  src/lib.rs(L322) 

Safety Mechanisms and Unsafe Operations

The FlattenObjects implementation contains several unsafe operations that are carefully controlled by safety invariants.

Unsafe Operation Sites

flowchart TD
subgraph subGraph0["Constructor Safety"]
    remove_fn["remove()"]
    assume_init_read["assume_init_read()"]
    replace_fn["add_or_replace_at()"]
    get_fn["get()"]
    assume_init_ref["assume_init_ref()"]
    get_mut_fn["get_mut()"]
    assume_init_mut["assume_init_mut()"]
    new_fn["new()"]
    bitmap_init["MaybeUninit::zeroed().assume_init()"]
    array_init["[MaybeUninit::uninit(); CAP]"]
    subgraph subGraph1["Access Operations"]
        subgraph subGraph2["Removal Operations"]
            remove_fn["remove()"]
            assume_init_read["assume_init_read()"]
            replace_fn["add_or_replace_at()"]
            get_fn["get()"]
            assume_init_ref["assume_init_ref()"]
            get_mut_fn["get_mut()"]
            assume_init_mut["assume_init_mut()"]
            new_fn["new()"]
            bitmap_init["MaybeUninit::zeroed().assume_init()"]
        end
    end
end

get_fn --> assume_init_ref
get_mut_fn --> assume_init_mut
new_fn --> array_init
new_fn --> bitmap_init
remove_fn --> assume_init_read
replace_fn --> assume_init_read

Sources: src/lib.rs(L77 - L84)  src/lib.rs(L165 - L173)  src/lib.rs(L194 - L202)  src/lib.rs(L315 - L326)  src/lib.rs(L277 - L297) 

Critical Safety Contracts

Each unsafe operation in the codebase follows specific safety contracts:

Safety Invariant Enforcement

The container maintains critical safety invariants through careful coordination between the bitmap and object array states.

Invariant Maintenance Operations

sequenceDiagram
    participant Client as Client
    participant FlattenObjects as FlattenObjects
    participant Bitmap as Bitmap
    participant ObjectArray as ObjectArray

    Note over FlattenObjects: Add Operation
    Client ->> FlattenObjects: add(value)
    FlattenObjects ->> Bitmap: first_false_index()
    Bitmap -->> FlattenObjects: Some(id)
    FlattenObjects ->> FlattenObjects: count += 1
    FlattenObjects ->> Bitmap: set(id, true)
    FlattenObjects ->> ObjectArray: objects[id].write(value)
    FlattenObjects -->> Client: Ok(id)
    Note over FlattenObjects: Access Operation
    Client ->> FlattenObjects: get(id)
    FlattenObjects ->> Bitmap: get(id)
    Bitmap -->> FlattenObjects: true
    FlattenObjects ->> ObjectArray: assume_init_ref()
    ObjectArray -->> FlattenObjects: &T
    FlattenObjects -->> Client: Some(&T)
    Note over FlattenObjects: Remove Operation
    Client ->> FlattenObjects: remove(id)
    FlattenObjects ->> Bitmap: get(id)
    Bitmap -->> FlattenObjects: true
    FlattenObjects ->> Bitmap: set(id, false)
    FlattenObjects ->> FlattenObjects: count -= 1
    FlattenObjects ->> ObjectArray: assume_init_read()
    ObjectArray -->> FlattenObjects: T
    FlattenObjects -->> Client: Some(T)

Sources: src/lib.rs(L222 - L232)  src/lib.rs(L165 - L173)  src/lib.rs(L315 - L326) 

Bitmap Synchronization Strategy

The id_bitmap field serves as the authoritative source of truth for object initialization state. All access to MaybeUninit storage goes through bitmap checks:

flowchart TD
subgraph subGraph1["Safe Failure Pattern"]
    check_false["is_assigned(id) == false"]
    none_return["Return None"]
end
subgraph subGraph0["Safe Access Pattern"]
    check["is_assigned(id)"]
    bitmap_get["id_bitmap.get(id)"]
    range_check["id < CAP"]
    unsafe_access["assume_init_*()"]
    safe_return["Return Some(T)"]
end

bitmap_get --> unsafe_access
check --> bitmap_get
check --> check_false
check --> range_check
check_false --> none_return
range_check --> unsafe_access
unsafe_access --> safe_return

Sources: src/lib.rs(L144 - L146)  src/lib.rs(L166)  src/lib.rs(L195) 

Memory Efficiency Considerations

The design prioritizes memory efficiency through several strategies suitable for resource-constrained environments.

Zero-Initialization Avoidance

flowchart TD
subgraph Benefits["Benefits"]
    no_default["No Default trait requirement"]
    fast_creation["O(1) container creation"]
    mem_efficient["Memory efficient for sparse usage"]
end
subgraph subGraph1["FlattenObjects Approach"]
    lazy_init["Objects initialized only when added"]
    compact_storage["Minimal stack footprint"]
    subgraph subGraph0["Traditional Array[T; CAP]"]
        trad_init["Default::default() called CAP times"]
        trad_memory["Full T initialization overhead"]
        trad_stack["Large stack usage"]
        maybe_init["MaybeUninit::uninit() - zero cost"]
    end
end

compact_storage --> mem_efficient
lazy_init --> fast_creation
maybe_init --> no_default

Sources: src/lib.rs(L79)  src/lib.rs(L227) 

Const Construction Support

The container supports const construction for compile-time initialization in embedded contexts:

flowchart TD
subgraph subGraph1["Runtime Benefits"]
    no_runtime_init["No runtime initialization cost"]
    static_storage["Can be stored in static memory"]
    embedded_friendly["Suitable for embedded systems"]
end
subgraph subGraph0["Const Construction"]
    const_new["const fn new()"]
    const_array["const MaybeUninit array"]
    const_bitmap["zeroed bitmap"]
    const_count["count = 0"]
end

const_array --> static_storage
const_bitmap --> embedded_friendly
const_new --> no_runtime_init

Sources: src/lib.rs(L77 - L84) 

The memory management strategy ensures that FlattenObjects maintains safety guarantees while providing efficient object storage suitable for kernel-level and embedded programming contexts where traditional heap allocation is not available.