# btrfs-transaction

Atomic, COW-based modification of btrfs filesystem images.

> This is a pre-1.0, experimental crate. It is a clean-room
> reimplementation of btrfs's read-write tree machinery and may
> have edge cases that testing doesn't cover. Do not use it on
> filesystems you care about without taking a backup first.

This crate sits on top of `btrfs-disk` and provides the write-side
machinery that the parsing crate deliberately doesn't: copy-on-write
of tree blocks, leaf insert/delete/split/balance, a delayed reference
queue, free space tree maintenance, and a `Transaction` type that
groups all of those into an atomic commit. It works on raw image
files or block devices and does not call any ioctls — it only needs
read/write/seek access to the filesystem bytes.

Part of the [btrfsutils](https://github.com/rustutils/btrfsutils) project.

## What's implemented

### Tree-block storage and COW

- **`Filesystem`**: open an image, resolve tree roots, read tree
  blocks via the chunk tree, write blocks back to disk on all
  mirrors with correct CRC32C checksums.
- **`ExtentBuffer`**: in-memory tree block with leaf/node helpers
  for items, key/data offsets, and slot manipulation. Tracks dirty
  state and pending writes.
- **`cow_block`**: copy-on-write a tree block, allocating a new
  bytenr, clearing the WRITTEN/RELOC flags, and queuing add/drop
  delayed refs against the old and new addresses.

### B-tree operations

- **`search_slot`**: search for a key in any tree, with optional
  COW of the path. Supports `ReadOnly`, `Insert(size)`, and
  `Delete` intents; the latter two pre-COW and pre-balance the
  path so the caller can mutate the leaf in place.
- **`next_leaf`**: cursor advance across leaf boundaries.
- **`items::insert_item` / `del_items` / `update_item` / `shrink_item`**:
  in-place leaf payload manipulation that maintains the descending
  data offset invariant.
- **Split / balance**: leaf and node split when an insert won't fit;
  push-left/push-right/merge to keep nodes within fill thresholds
  on delete.
- **`BtrfsPath`**: per-level slot+buffer trace from the root to a
  target leaf, owned and released explicitly so the caller controls
  borrow scope.

### Allocation

- **Block group scan**: load every `BLOCK_GROUP_ITEM` from the
  block group tree (id 11) when present, otherwise from the
  extent tree (id 2).
- **Per-kind bump allocator**: `Transaction::alloc_block(kind)`
  with separate cursors for `BlockGroupKind::Metadata` and
  `BlockGroupKind::System`. Cursors are seeded by scanning the
  extent tree for free gaps inside block groups of the requested
  kind. Pinned blocks (freed earlier in the same transaction) are
  skipped to preserve crash consistency.
- **`alloc_tree_block(tree_id, level)`**: routes the chunk tree
  (id 3) to a SYSTEM block group and every other tree to a
  metadata block group, registers a delayed `add_ref`, and for
  SYSTEM allocations updates the superblock's `sys_chunk_array`
  bootstrap snippet so the next mount can resolve the new chunk
  root.

### Delayed reference queue

- **`DelayedRefQueue`**: batches reference count changes keyed by
  `DelayedRefKey::Metadata { bytenr, owner_root, level }` or
  `DelayedRefKey::Data { bytenr, owner_root, owner_ino, owner_offset }`.
  Add/drop pairs to the same key cancel.
- **Metadata flush**: creates `METADATA_ITEM` (skinny) or
  `EXTENT_ITEM` records with `TREE_BLOCK_REF` inline backrefs on
  positive deltas, deletes them on negative deltas, and threads
  byte deltas into per-block-group `bytes_used` accounting.
- **Data flush** (drop side): locates the matching
  `EXTENT_DATA_REF` either inline inside the parent `EXTENT_ITEM`
  or as a standalone item (with hash-collision walk forward),
  decrements both the inline `count` field and the parent
  `EXTENT_ITEM.refs`, and on hitting zero deletes the entire
  `EXTENT_ITEM` and trims overlapping csum tree entries.
- **Csum tree maintenance**: when a data extent is fully freed,
  walks the csum tree once to collect every overlapping
  `EXTENT_CSUM` item, then in a second pass deletes whole-coverage
  items and re-inserts trimmed head/tail fragments under new keys.

### Free space tree

- **Incremental update**: `update_free_space_tree` consumes the
  per-block-group range deltas accumulated during the delayed-ref
  flush and applies them to the on-disk FST, deleting and
  re-inserting `FREE_SPACE_EXTENT` items and updating the
  `FREE_SPACE_INFO.extent_count`. Bitmap-layout block groups are
  refused with a clear error.
- **`FREE_SPACE_TREE_VALID` stays set**: the convergence loop in
  `Transaction::commit` runs `flush_delayed_refs →
  update_root_items → snapshot_roots → update_free_space_tree`
  in that order so the FST root change is captured by the next
  pass and the on-disk FST stays consistent with the extent tree.

### Transaction lifecycle

- **`Transaction::start`**: bumps the in-memory generation,
  snapshots the current root pointers, and seeds the metadata
  allocator cursor.
- **`Transaction::commit`**: force-COWs the root tree (so every
  commit advances `header.generation`), runs the convergence loop
  to drain delayed refs, root item updates, and FST updates until
  stable, flushes every dirty block to disk via the chunk tree
  (writing all DUP/RAID1 mirrors), updates superblock fields and
  the rotating backup roots, and writes the superblock to all
  mirrors.
- **`Transaction::abort`**: restores the in-memory root pointer
  snapshot so the next transaction reads consistent on-disk state.

## What's not yet implemented

- **Data extent ref additions**: `flush_delayed_refs` only handles
  the drop side for data refs (`todo!` on positive deltas). No
  current caller produces data ref additions.
- **New SYSTEM chunk allocation**: if no existing SYSTEM block
  group has free space, `ensure_in_sys_chunk_array` cannot carve
  out a new one. Bails cleanly.
- **Multi-device replication for chunk tree COW**: tested only
  on single-device filesystems.
- **Bitmap-layout free space tree**: refused with a clear error.

## Testing

Unit tests cover the leaf manipulation primitives, balance logic,
delayed ref merging, search/next_leaf, and the chunk array
bootstrap helpers (in `btrfs-disk`).

Integration tests build real filesystem images via `mkfs.btrfs`,
exercise the full COW pipeline through `Transaction::commit`, and
verify the result both by reopening the image with `Filesystem`
and by running `btrfs check --readonly` on it. The fixture image
under `cli/tests/commands/fixture.img.gz` is also used for
read-path and data-ref drop tests.

A regression suite hits historical bugs (cow pinning, sibling
generation, leaf data compaction, cascading splits, ...). A
proptest-based playground tree harness exercises insert/delete
sequences against an in-memory model and verifies that
`Transaction::commit` produces a structurally valid filesystem
on every step.

## License

Licensed under either of [Apache License, Version 2.0](LICENSE-APACHE) or
[MIT license](LICENSE-MIT) at your option.
