Packed storage: zstd packs with sorted indexes, oxy gc, auto-pack at 4096 loose objects; README d02e545dc265

 "jobserver",

 "libc",

name = "jobserver"

version = "0.1.35"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "1c00acbd29eabad4a2392fa0e921c874934dbbf4194312ad20f04a0ed67a3cb3"

dependencies = [

 "getrandom 0.4.3",

 "libc",

]

[[package]]

 "zstd",

name = "pkg-config"

version = "0.3.34"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "f6b464fbc74e149a392436b17d523f769e057cb6877f6a5c4618bc6f11800548"

[[package]]

[[package]]

name = "zstd"

version = "0.13.3"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "e91ee311a569c327171651566e07972200e76fcfe2242a4fa446149a3881c08a"

dependencies = [

 "zstd-safe",

]

[[package]]

name = "zstd-safe"

version = "7.3.0"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "64d80649ab6db9d9f6f9c80a40becd948eda4714a0a5ac8c4d157a32231c7882"

dependencies = [

 "zstd-sys",

]

[[package]]

name = "zstd-sys"

version = "2.1.0+zstd.1.5.7"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "0ef0a8027ec3ee71300ab3bcbcd0393f434aa72b91ca6d635a39941deae8eea0"

dependencies = [

 "cc",

 "pkg-config",

]

Oxygen (`oxy`) is a distributed, commutative version control system written in Rust for large repositories. See [docs/spec.md](docs/spec.md) for the specification.

It is self-hosting: this directory is an Oxygen repository, and the project's own history is kept with `oxy`, not with Git.

## What is different

- **History is a set of changes, not a chain of snapshots.** A change records what it did to identified lines and tree nodes and which earlier changes it depends on. Changes that do not depend on each other commute, so there are no merge commits and rebasing independent work rewrites nothing.

- **Conflicts are data.** A conflicted state can be committed, pushed and pulled. Resolving one is an ordinary edit followed by a commit.

- **Every change has a stable ID and a content hash.** The ID survives rewrites; the hash makes history tamper-evident.

- **Everything is signed.** Composite Ed25519 + ML-DSA-65 signatures on changes and on every bookmark update, verified against a trust policy that lives in the repository.

- **Every operation is undoable** through an operation log.

- **Large files are chunked** with content-defined chunking into a BLAKE3-addressed store.

## Status

Early, but usable for its own development. Implemented: the object model, the change graph with conflict detection and resolution, the working copy (`status`, `commit`, `checkout`, `diff`, `undo`), identities and signatures, remotes over local paths and HTTP(S) with `clone`, `fetch`, `pull`, `push`, the reference server `oxy serve`, the trust policy, and packed storage.

Not yet: checkpoints for very long histories, history editing (`rebase`, `split`, `edit`), multiple workspaces, garbage collection with retention, and the Thin client profile for constrained machines.

## Building

```

cargo build --release

cargo test --workspace

```

The binary is `target/release/oxy`.

## Quick start

```

oxy identity create --name "Your Name" --email [email protected]

oxy config --user core.sign change      # sign every commit

oxy init                                 # in a project directory

oxy status

oxy commit -m "First change"

oxy log

```

Collaborating:

```

oxy serve --root /srv/oxy --bind 0.0.0.0:8890 --tls-cert cert.pem --tls-key key.pem --token SECRET

oxy clone https://host:8890/project

oxy config remote.origin.token SECRET

oxy push

oxy pull

```

Trust policy, so a server accepts only changes from keys you have granted:

```

oxy policy init                          # your key becomes the root

oxy identity export                      # a contributor sends you this file

oxy policy grant alice.identity

oxy push                                 # publishes the policy

```

## Layout

| Path | Contents |

|---|---|

| `crates/oxy-core` | Library: encoding, hashing, objects, the change graph, storage, identities, policy, protocol, repository operations |

| `crates/oxy-server` | Reference HTTP(S) server for the wire protocol |

| `src/cli` | The `oxy` command-line interface |

| `docs/spec.md` | The specification |

## Licence

MIT or Apache-2.0, at your option.

zstd = "0.13"

/// Loose objects tolerated before a commit packs them (spec §13.4).

pub const AUTOPACK_THRESHOLD: usize = 4096;

    /// Pack every loose object (spec §13.4). Pruning unreachable objects

    /// waits for operation-log retention, since every operation keeps its

    /// states reachable for now.

    pub fn gc(&self) -> Result<crate::store::PackReport> {

        Ok(self.store.pack_loose()?)

    }

    /// Pack automatically once many loose objects have accumulated.

    pub(crate) fn maybe_autopack(&self) -> Result<()> {

        if self.store.loose_count()? > AUTOPACK_THRESHOLD {

            self.store.pack_loose()?;

        }

        Ok(())

    }

        self.maybe_autopack()?;

#[test]

fn gc_packs_objects_and_history_still_works() {

    hermetic();

    let dir = tempfile::tempdir().unwrap();

    let root = dir.path();

    let mut repo = Repo::init(root).unwrap().with_home(root.join("home"));

    repo.create_identity("Ada", "a@b", IdentityScope::User).unwrap();

    repo.set_user_config("core.sign", "change").unwrap();

    write(root, "a.txt", b"one\n");

    let h1 = repo.commit("one", &[]).unwrap();

    write(root, "a.txt", b"two\n");

    write(root, "big.bin", &vec![0u8; 100_000]);

    let h2 = repo.commit("two", &[]).unwrap();

    let before = repo.store().list().unwrap();

    assert!(repo.store().loose_count().unwrap() > 0);

    let r = repo.gc().unwrap();

    assert_eq!(r.objects, before.len());

    assert_eq!(repo.store().loose_count().unwrap(), 0);

    assert_eq!(repo.store().list().unwrap(), before);

    // Reopen: reads come from the pack; signatures, states, ops all resolve.

    let repo = Repo::open(root).unwrap().with_home(root.join("home"));

    assert_eq!(repo.bookmark_heads().unwrap(), vec![h2]);

    assert!(matches!(repo.verify_change(&h2).unwrap(), SignatureStatus::Valid { .. }));

    assert_eq!(repo.log().unwrap().len(), 3);

    repo.checkout(&[h1], false, "checkout").unwrap();

    assert_eq!(fs::read(root.join("a.txt")).unwrap(), b"one\n");

    repo.checkout(&[h2], false, "checkout").unwrap();

    assert_eq!(fs::read(root.join("big.bin")).unwrap().len(), 100_000);

    assert!(!repo.snapshot("status").unwrap().changed);

    // New work after packing goes loose and commits fine.

    write(root, "a.txt", b"three\n");

    repo.commit("three", &[]).unwrap();

    assert!(repo.store().loose_count().unwrap() > 0);

    assert_eq!(repo.gc().unwrap().objects, repo.store().list().unwrap().len() - before.len());

    assert_eq!(repo.store().pack_count(), 2);

}

//! Object store (spec §13.1, §13.3, §13.4): loose objects, one file per

//! object under `objects/loose/<hh>/<rest>`, and packs, `pack-<id>.pack`

//! with a sorted `pack-<id>.idx`, holding zstd-compressed objects. Reads

//! check loose objects first, then every pack; every read re-hashes.

//!

//! Pack file: `OXYPACK1` then entries of

//! `type u8 | flags u8 (bit 0: zstd) | stored_len u32 | raw_len u32 | ref 32 | body`.

//! Index file: `OXYIDX01` then `count u32` then sorted entries of

//! `ref 32 | offset u64 | stored_len u32 | raw_len u32 | type u8 | flags u8`.

use std::cell::RefCell;

use std::io::{self, Read, Seek, SeekFrom, Write};

const PACK_MAGIC: &[u8; 8] = b"OXYPACK1";

const IDX_MAGIC: &[u8; 8] = b"OXYIDX01";

const IDX_ENTRY: usize = 32 + 8 + 4 + 4 + 1 + 1;

const FLAG_ZSTD: u8 = 1;

const ZSTD_LEVEL: i32 = 3;

#[derive(Clone, Copy, Debug)]

struct PackEntry {

    offset: u64,

    stored_len: u32,

    raw_len: u32,

    ty: ObjectType,

    flags: u8,

}

/// One pack's index, fully in memory and sorted by ObjectRef.

#[derive(Debug)]

struct PackIndex {

    path: PathBuf,

    refs: Vec<ObjectRef>,

    entries: Vec<PackEntry>,

}

impl PackIndex {

    fn load(idx_path: &Path, pack_path: &Path) -> Result<PackIndex> {

        let data = fs::read(idx_path)?;

        let bad = |m: &str| StoreError::Corrupt(ObjectRef::ZERO, format!("{}: {m}", idx_path.display()));

        if data.len() < 12 || &data[..8] != IDX_MAGIC {

            return Err(bad("bad index header"));

        }

        let count = u32::from_le_bytes(data[8..12].try_into().unwrap()) as usize;

        if data.len() != 12 + count * IDX_ENTRY {

            return Err(bad("index length mismatch"));

        }

        let mut refs = Vec::with_capacity(count);

        let mut entries = Vec::with_capacity(count);

        for i in 0..count {

            let e = &data[12 + i * IDX_ENTRY..12 + (i + 1) * IDX_ENTRY];

            let r = ObjectRef::from_slice(&e[..32]).unwrap();

            if let Some(prev) = refs.last() {

                if r <= *prev {

                    return Err(bad("index not sorted"));

                }

            }

            refs.push(r);

            entries.push(PackEntry {

                offset: u64::from_le_bytes(e[32..40].try_into().unwrap()),

                stored_len: u32::from_le_bytes(e[40..44].try_into().unwrap()),

                raw_len: u32::from_le_bytes(e[44..48].try_into().unwrap()),

                ty: ObjectType::ALL.get(e[48] as usize).copied().ok_or_else(|| bad("unknown object type"))?,

                flags: e[49],

            });

        }

        Ok(PackIndex { path: pack_path.to_path_buf(), refs, entries })

    }

    fn find(&self, r: &ObjectRef) -> Option<PackEntry> {

        self.refs.binary_search(r).ok().map(|i| self.entries[i])

    }

    fn read(&self, r: &ObjectRef, e: PackEntry) -> Result<(ObjectType, Vec<u8>)> {

        let mut f = fs::File::open(&self.path)?;

        f.seek(SeekFrom::Start(e.offset))?;

        let mut stored = vec![0u8; e.stored_len as usize];

        f.read_exact(&mut stored)?;

        let body = if e.flags & FLAG_ZSTD != 0 {

            zstd::bulk::decompress(&stored, e.raw_len as usize).map_err(|err| StoreError::Corrupt(*r, format!("zstd: {err}")))?

        } else {

            stored

        };

        if body.len() != e.raw_len as usize || hash_object(e.ty, &body) != *r {

            return Err(StoreError::Corrupt(*r, "packed object does not match its reference".into()));

        }

        Ok((e.ty, body))

    }

}

fn type_index(ty: ObjectType) -> u8 {

    ObjectType::ALL.iter().position(|t| *t == ty).unwrap() as u8

}

/// What `pack_loose` did.

#[derive(Debug, Clone, Default, PartialEq, Eq)]

pub struct PackReport {

    pub objects: usize,

    pub raw_bytes: u64,

    pub packed_bytes: u64,

}

#[derive(Debug)]

    packs: RefCell<Vec<PackIndex>>,

        let store = Store { dir, packs: RefCell::new(Vec::new()) };

        store.reload_packs().map_err(|e| io::Error::other(e.to_string()))?;

        Ok(store)

    }

    fn reload_packs(&self) -> Result<()> {

        let mut packs = Vec::new();

        let mut names: Vec<PathBuf> = fs::read_dir(&self.dir)?

            .filter_map(|e| e.ok().map(|e| e.path()))

            .filter(|p| p.extension().is_some_and(|x| x == "idx") && p.file_name().is_some_and(|n| n.to_string_lossy().starts_with("pack-")))

            .collect();

        names.sort();

        for idx in names {

            let pack = idx.with_extension("pack");

            if pack.is_file() {

                packs.push(PackIndex::load(&idx, &pack)?);

            }

        }

        *self.packs.borrow_mut() = packs;

        Ok(())

    }

    pub fn pack_count(&self) -> usize {

        self.packs.borrow().len()

    }

    fn find_packed(&self, r: &ObjectRef) -> Option<(usize, PackEntry)> {

        self.packs.borrow().iter().enumerate().find_map(|(i, p)| p.find(r).map(|e| (i, e)))

    }

    /// Loose objects on disk, with their paths.

    fn loose_objects(&self) -> io::Result<Vec<(ObjectRef, PathBuf)>> {

        let mut out = Vec::new();

        let loose = self.dir.join("loose");

        for d in fs::read_dir(&loose)? {

            let d = d?;

            if !d.file_type()?.is_dir() {

                continue;

            }

            let prefix = d.file_name().to_string_lossy().to_string();

            for f in fs::read_dir(d.path())? {

                let f = f?;

                let name = f.file_name().to_string_lossy().to_string();

                if let Some(r) = ObjectRef::from_hex(&format!("{prefix}{name}")) {

                    out.push((r, f.path()));

                }

            }

        }

        out.sort();

        Ok(out)

    }

    pub fn loose_count(&self) -> io::Result<usize> {

        Ok(self.loose_objects()?.len())

    }

    /// Move every loose object into a new pack (spec §13.4). Loose files are

    /// deleted only after the pack and its index are durable.

    pub fn pack_loose(&self) -> Result<PackReport> {

        let loose = self.loose_objects()?;

        if loose.is_empty() {

            return Ok(PackReport::default());

        }

        let mut nonce = [0u8; 8];

        rand::rngs::OsRng.fill_bytes(&mut nonce);

        let id = hex::encode(nonce);

        let pack_path = self.dir.join(format!("pack-{id}.pack"));

        let idx_path = self.dir.join(format!("pack-{id}.idx"));

        let tmp_pack = self.dir.join(format!("tmp-{id}.pack"));

        let tmp_idx = self.dir.join(format!("tmp-{id}.idx"));

        let mut report = PackReport::default();

        let mut index: Vec<(ObjectRef, PackEntry)> = Vec::with_capacity(loose.len());

        {

            let mut f = io::BufWriter::new(fs::File::create(&tmp_pack)?);

            f.write_all(PACK_MAGIC)?;

            let mut offset = PACK_MAGIC.len() as u64;

            for (r, _) in &loose {

                let (ty, body) = self.get(r)?;

                let compressed = zstd::bulk::compress(&body, ZSTD_LEVEL).map_err(|e| StoreError::Corrupt(*r, format!("zstd: {e}")))?;

                let (flags, stored) = if compressed.len() < body.len() { (FLAG_ZSTD, compressed) } else { (0, body.clone()) };

                let header_len = 1 + 1 + 4 + 4 + 32;

                f.write_all(&[type_index(ty), flags])?;

                f.write_all(&(stored.len() as u32).to_le_bytes())?;

                f.write_all(&(body.len() as u32).to_le_bytes())?;

                f.write_all(&r.0)?;

                f.write_all(&stored)?;

                index.push((*r, PackEntry { offset: offset + header_len, stored_len: stored.len() as u32, raw_len: body.len() as u32, ty, flags }));

                offset += header_len + stored.len() as u64;

                report.objects += 1;

                report.raw_bytes += body.len() as u64;

                report.packed_bytes += stored.len() as u64;

            }

            f.flush()?;

            f.get_ref().sync_all()?;

        }

        {

            let mut f = io::BufWriter::new(fs::File::create(&tmp_idx)?);

            f.write_all(IDX_MAGIC)?;

            f.write_all(&(index.len() as u32).to_le_bytes())?;

            for (r, e) in &index {

                f.write_all(&r.0)?;

                f.write_all(&e.offset.to_le_bytes())?;

                f.write_all(&e.stored_len.to_le_bytes())?;

                f.write_all(&e.raw_len.to_le_bytes())?;

                f.write_all(&[type_index(e.ty), e.flags])?;

            }

            f.flush()?;

            f.get_ref().sync_all()?;

        }

        fs::rename(&tmp_pack, &pack_path)?;

        fs::rename(&tmp_idx, &idx_path)?;

        self.reload_packs()?;

        for (_, path) in &loose {

            fs::remove_file(path)?;

            if let Some(dir) = path.parent() {

                let _ = fs::remove_dir(dir);

            }

        }

        Ok(report)

        self.path_for(r).is_file() || self.find_packed(r).is_some()

        if path.is_file() || self.find_packed(&r).is_some() {

    /// Read and verify an object, loose or packed.

            Err(e) if e.kind() == io::ErrorKind::NotFound => {

                return match self.find_packed(r) {

                    Some((i, e)) => self.packs.borrow()[i].read(r, e),

                    None => Err(StoreError::NotFound(*r)),

                };

            }

    /// Every object reference in the store, loose and packed (slow; for gc and tests).

        let mut out: Vec<ObjectRef> = self.loose_objects()?.into_iter().map(|(r, _)| r).collect();

        for p in self.packs.borrow().iter() {

            out.extend(p.refs.iter().copied());

        out.dedup();

    fn packing_keeps_every_object_readable() {

        let dir = tempfile::tempdir().unwrap();

        let s = Store::open(dir.path()).unwrap();

        let mut refs = Vec::new();

        for i in 0..300u32 {

            let body = format!("object {i} ").repeat(1 + (i % 7) as usize);

            refs.push((s.put(ObjectType::Chunk, body.as_bytes()).unwrap(), body));

        }

        let c = crate::objects::tests::sample_change();

        let cr = s.put_change(&c).unwrap();

        assert_eq!(s.loose_count().unwrap(), 301);

        let report = s.pack_loose().unwrap();

        assert_eq!(report.objects, 301);

        assert!(report.packed_bytes < report.raw_bytes, "{report:?}");

        assert_eq!(s.loose_count().unwrap(), 0);

        assert_eq!(s.pack_count(), 1);

        for (r, body) in &refs {

            assert!(s.has(r));

            assert_eq!(s.get(r).unwrap(), (ObjectType::Chunk, body.as_bytes().to_vec()));

        }

        assert_eq!(s.get_change(&cr).unwrap(), c);

        assert_eq!(s.list().unwrap().len(), 301);

        // Re-putting a packed object is a no-op; new objects go loose and a

        // second pack coexists with the first.

        assert_eq!(s.put(ObjectType::Chunk, refs[0].1.as_bytes()).unwrap(), refs[0].0);

        assert_eq!(s.loose_count().unwrap(), 0);

        let extra = s.put(ObjectType::Chunk, b"after packing").unwrap();

        s.pack_loose().unwrap();

        assert_eq!(s.pack_count(), 2);

        assert_eq!(s.get(&extra).unwrap().1, b"after packing");

        // A reopened store sees the packs.

        let s2 = Store::open(dir.path()).unwrap();

        assert_eq!(s2.pack_count(), 2);

        assert_eq!(s2.get(&refs[5].0).unwrap().1, refs[5].1.as_bytes());

        assert!(matches!(s2.get(&ObjectRef([9; 32])), Err(StoreError::NotFound(_))));

        // Corrupting an object's body inside the pack is detected on read.

        let target = refs[5].0;

        let (pack_path, offset) = {

            let packs = s2.packs.borrow();

            let (i, e) = s2.find_packed(&target).unwrap();

            (packs[i].path.clone(), e.offset as usize)

        };

        let mut data = fs::read(&pack_path).unwrap();

        data[offset] ^= 0xff;

        fs::write(&pack_path, data).unwrap();

        let s3 = Store::open(dir.path()).unwrap();

        assert!(matches!(s3.get(&target), Err(StoreError::Corrupt(..))));

        assert_eq!(s3.get(&refs[6].0).unwrap().1, refs[6].1.as_bytes(), "other objects are unaffected");

    }

    #[test]

| **Status** | Draft 0.6a |

The pack and index formats are fixed so that tools can read them without the implementation:

```

pack:  "OXYPACK1" || entry*

entry: type u8 || flags u8 || stored_len u32le || raw_len u32le || ref bytes(32) || body[stored_len]

index: "OXYIDX01" || count u32le || ( ref bytes(32) || offset u64le || stored_len u32le || raw_len u32le || type u8 || flags u8 )*

```

`type` indexes the object types in the order of §5.3 (chunk 0, blob 1, change 2, checkpoint 3, op 4, attest 5, identity 6, policy 7, state 8). Flag bit 0 means the body is zstd-compressed and `raw_len` is its decompressed size; otherwise the body is stored raw and the two lengths are equal. `offset` is the position of the body, not of the entry. Index entries are sorted by `ref`. A reader MUST re-hash every object it reads from a pack and reject a mismatch.

*Changelog.* Draft 0.6a (2026-09-26): §13.4 fixes the pack and index file formats.

Draft 0.6 (2026-09-26): trust policy propagation over the wire, the `policy` signing domain, per-remote downgrade protection, the bootstrap rule for unverified remotes, and the rule that policies govern only changes added after them.

    /// Pack loose objects into a compressed pack

    Gc,

        Cmd::Gc => workspace::gc(),

pub fn gc() -> Result<i32> {

    let repo = open()?;

    let r = repo.gc()?;

    if r.objects == 0 {

        println!("Nothing to pack; {} pack(s) present.", repo.store().pack_count());

    } else {

        println!(

            "Packed {} into one pack: {} bytes -> {} bytes ({:.0}%); {} pack(s) present.",

            plural(r.objects, "object"),

            r.raw_bytes,

            r.packed_bytes,

            100.0 * r.packed_bytes as f64 / r.raw_bytes.max(1) as f64,

            repo.store().pack_count()

        );

    }

    Ok(0)

}