blob: e13c19c8224c4156b0929a026ca80c645f807150 [file] [view]
# Storage Units (`storage_units`)
`storage_units` (`//src/storage/lib/units`) provides zero-cost typed
abstractions for power-of-two block sizes and system memory page sizes.
## Overview
Filesystem and storage code frequently checks alignments, rounds byte offsets
or ranges up/down to block boundaries, and converts between byte counts and
block counts. Using plain integer types (`u64` / `usize`) for block sizes has
two main drawbacks:
1. **Performance**: Standard integer division (`/`) and modulo (`%`) on 64-bit
integers require expensive multi-cycle CPU division instructions, even when
the divisor is known at runtime to be a power of two.
2. **Safety & Ergonomics**: Manual alignment math (e.g.
`(offset + block_size - 1) / block_size` or `offset & !(block_size - 1)`) is
repetitive and prone to integer overflow bugs near `u64::MAX`.
`storage_units` guarantees that block sizes are powers of two and packs the
alignment bitmask (`size - 1`) and bit shift (`trailing_ones`) into a single
`u64` (`(mask << 32) | shift`), replacing division and modulo with single-cycle
bit shifts and masks while providing overflow-safe alignment helpers.
## Core Types
* **[`BlockSize<T = UniversalBlockSizeTag>`](src/lib.rs)**: A power-of-two block
size (up to 2 GiB, `1 << 31`) backed by a packed mask-shift representation and
parameterized by an [`AnyBlockSizeTag`](src/lib.rs).
* Predefined constants on `BlockSize<UniversalBlockSizeTag>`: `SIZE_1B`,
`SIZE_2B`, `SIZE_4B`, `SIZE_8B`, `SIZE_16B`, `SIZE_32B`, `SIZE_64B`,
`SIZE_128B`, `SIZE_256B`, `SIZE_512B`, `SIZE_1KIB`, `SIZE_2KIB`, `SIZE_4KIB`,
`SIZE_8KIB`, `SIZE_16KIB`, `SIZE_32KIB`, `SIZE_64KIB`, `SIZE_128KIB`,
`SIZE_256KIB`, `SIZE_512KIB`, `SIZE_1MIB`.
* **[`BlockSizeTag`](src/lib.rs) and [`AnyBlockSizeTag`](src/lib.rs)**:
Domain-specific tags implement [`BlockSizeTag`](src/lib.rs), which
automatically implements the sealed [`AnyBlockSizeTag`](src/lib.rs) supertrait
and provides `From<BlockSize<T>> for BlockSize<UniversalBlockSizeTag>`.
* **[`page_size()`](src/page.rs)** *(Fuchsia targets)*: Returns the Fuchsia
system memory page size as a [`PageSize`](src/page.rs)
(`BlockSize<PageSizeTag>`). It caches the packed mask-shift representation of
`zx::system_get_page_size()` in a relaxed atomic on first use to avoid
repeated syscalls/vDSO lookups.
### Why is `BlockSize<T>` Generic Over a Tag?
A filesystem typically deals with multiple distinct domains of block alignment
simultaneously:
* **Device Block Size** (e.g. physical 512B or 4KiB sectors)
* **Filesystem Block Size** (e.g. logical 4KiB blocks in Fxfs)
* **Journal Block Size** (e.g. fixed 4KiB journal chunks)
* **System Page Size** (`page_size()`)
If all block sizes shared a single concrete type, the type system could not
distinguish *which* domain a byte offset or range was aligned to. By
parameterizing [`BlockSize<T>`](src/lib.rs) over a [`BlockSizeTag`](src/lib.rs)
`T`, subsystems can define distinct types such as `FxfsBlockSize`,
`DeviceBlockSize`, `JournalBlockSize`, or `LayerBlockSize`. Tags are typically
zero-sized types, or small `Copy` values (such as a device or volume ID) when
disambiguating multiple runtime instances of a domain.
In this hierarchy, **[`BlockSize`](src/lib.rs)**
(`BlockSize<UniversalBlockSizeTag>`) acts as a **universal block size**: it
represents a runtime power-of-two block size when you need to align values or
perform block arithmetic, but do not need (or cannot statically know) a
domain-specific type tag. Any `BlockSize<T>` where `T: BlockSizeTag` can be
converted into `BlockSize<UniversalBlockSizeTag>` via `From` / `Into`.
## Operations & Helpers
### Alignment Helpers
* `bs.is_aligned(val)`: Returns `true` if a `u64` (or `Range<u64>`) is aligned
to `bs`.
* `bs.align_down(bytes) -> u64`: Rounds `bytes` down to the nearest block
boundary (`bytes & !bs.mask()`).
* `bs.align_up(bytes) -> Option<u64>`: Rounds `bytes` up to the nearest block
boundary, returning `None` on `u64` overflow.
* `bs.align_up_to_blocks(bytes) -> u64`: Rounds `bytes` up to the nearest block
boundary and returns the total block count without overflowing `u64`.
* `bs.align_range_outwards(range) -> Option<Range<u64>>`: Aligns `range.start`
down and `range.end` up to block boundaries.
* `bs.checked_mul(blocks) -> Option<u64>`: Multiplies `blocks` by `bs`,
returning `None` on `u64` overflow.
* `bs.saturating_mul(blocks) -> u64`: Multiplies `blocks` by `bs`, saturating at
`u64::MAX` on overflow.
### Arithmetic & Comparisons
`BlockSize<T>` implements standard arithmetic (`+`, `-`, `*`, `/`, `%` and
their assignment counterparts) with `u64`, as well as comparison and hashing
traits (`PartialEq`, `Eq`, `PartialOrd`, `Ord`, `Hash`) between two
`BlockSize<T>` values of the same tag type `T` (ordered by byte size first, then
`tag`) and directly against `u64`:
* **Division (`bytes / bs`)**: Compiles to `bytes >> bs.shift()`.
* **Remainder (`bytes % bs`)**: Compiles to `bytes & bs.mask()`.
* **Multiplication (`blocks * bs`)**: Compiles to `blocks << bs.shift()` (with
debug assertions checking for overflow).
## Example
```rust
use storage_units::BlockSize;
let bs = BlockSize::SIZE_4KIB;
assert!(bs.is_aligned(8192u64));
assert!(bs.is_aligned(0..4096));
assert_eq!(bs.align_down(5000), 4096);
assert_eq!(bs.align_up(5000), Some(8192));
assert_eq!(bs.align_up_to_blocks(5000), 2);
assert_eq!(bs.align_range_outwards(100..5000), Some(0..8192));
// Arithmetic with u64 uses shifts and masks
let blocks = 12288u64 / bs; // 3
let rem = 5000u64 % bs; // 904
let bytes = blocks * bs; // 12288
```
## Future Work
Planned additions to `storage_units` include newtypes parameterized by `T:
AnyBlockSizeTag` that encode both block alignment and alignment domain
invariants directly in the type system:
* **`BlockAligned<T>`**: Represents a byte offset or byte count guaranteed to
be a multiple of the block size `T`.
* **`BlockAlignedRange<T>`**: Represents a `Range` whose start and end offsets
are both guaranteed to be aligned to `T`.
* **`BlockCount<T>`**: Represents an explicit count of blocks of size `T`
rather than raw bytes.
Because these types are generic over `T: AnyBlockSizeTag`, a byte count aligned
to the device block size (`BlockAligned<DeviceBlockSizeTag>`) will be a distinct
type from a byte count aligned to the filesystem block size
(`BlockAligned<FxfsBlockSizeTag>`). Accepting these types in function signatures
in place of raw `u64` values eliminates redundant runtime `is_aligned` checks
and prevents accidentally passing values aligned to the wrong block size at
compile time.