Module alloc 

Block + inode bitmap allocator — planning layer.

Phase 4 write path scaffolding. This module produces typed [AllocationPlan] values describing what bits to flip in which bitmap block + the updated free-counter deltas. It does NOT write to disk; E11 (journaled writes) will apply the plans atomically under a JBD2 transaction.

Rationale: separating allocation (pure function over bitmap bytes) from commit (journaled block write) makes tests trivial and keeps the read-only mount path untouched. Block device traits stay read-only in Phase 1; the write trait lives at the commit boundary.

Block bitmap layout

One bit per block in the group. Bit i = block group_start + i. A 4 KiB block bitmap covers 32768 blocks (one block group on a 4 KiB-block fs). Bits are packed LSB-first within each byte: bit 0 of byte 0 represents the first block in the group.

Inode bitmap layout

Same LSB-first packing. Bit i = inode (group_idx * inodes_per_group) + i + 1 (inode numbers are 1-based).

Orlov allocator (directories)

Linux ext4 chooses a group for new directories using the Orlov heuristic: prefer groups whose (free_blocks, free_inodes, used_dirs) triple is “below average” — distributing directories evenly across groups so sibling files end up near their parent dir. We implement a simplified variant: iterate groups starting from hint, prefer one whose used_dirs is below the fleet average and has the most free_inodes.

Structs

BgdCounterUpdate

A change to one block-group descriptor’s free-counter and/or used_dirs_count. Applied together with the matching BitmapWrite.

BitmapWrite

A change to one bitmap block: flip bits bit_start .. bit_start + count from 0 (free) to 1 (used). The new bitmap bytes are NOT materialised here — only the semantic description is.

BlockAllocationPlan

Complete plan for one block-allocation request.

InodeAllocationPlan

Complete plan for one inode-allocation request.

SuperblockCounterUpdate

A change to the superblock free-counter totals.

Functions

apply_bitmap_write

Apply a BitmapWrite to a bitmap buffer in place.

bit_is_set

Test bit idx in a bitmap (LSB-first within each byte).

find_first_free

Find the first free (0-valued) bit at or after start, searching up to max_bits total. Returns None if none found.

find_free_run

Find the first run of count consecutive free bits at or after start, within the first max_bits bits of the bitmap. Returns the starting bit index of the run, or None if no such run exists.

plan_block_allocation

Plan allocation of count contiguous blocks.

plan_inode_allocation

Plan allocation of a single inode. For directories, uses a simplified Orlov heuristic to spread dirs across groups; for regular files, prefers the hint_group (typically the parent directory’s group).