alice.pds.demo.boltless.dev
This repository has no description
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use std::io::{self, BufWriter, Write};
2use std::os::unix::fs::FileExt;
3use std::sync::Mutex;
4
5use gix::ObjectId;
6
7use crate::error::PackError;
8use crate::ids::{Crc32, PackOffset};
9
10const V2_SIGNATURE: &[u8] = &[0xff, 0x74, 0x4f, 0x63];
11const V2_VERSION: u32 = 2;
12const HIGH_BIT: u32 = 0x8000_0000;
13const LARGE_OFFSET_THRESHOLD: u64 = 0x7fff_ffff;
14const BUCKETS: usize = 256;
15const BUCKET_BUF: usize = 64 * 1024;
16const CRC_LEN: usize = 4;
17const OFFSET_LEN: usize = 8;
18
19struct Record {
20 id: ObjectId,
21 crc32: Crc32,
22 offset: PackOffset,
23}
24
25pub(crate) struct Spool {
26 buckets: Vec<Mutex<BufWriter<std::fs::File>>>,
27 record_len: usize,
28 hash_len: usize,
29}
30
31impl Spool {
32 pub(crate) fn new(kind: gix::hash::Kind) -> io::Result<Self> {
33 let hash_len = kind.len_in_bytes();
34 let buckets = (0..BUCKETS)
35 .map(|_| {
36 tempfile::tempfile()
37 .map(|file| Mutex::new(BufWriter::with_capacity(BUCKET_BUF, file)))
38 })
39 .collect::<io::Result<Vec<_>>>()?;
40 Ok(Self {
41 buckets,
42 record_len: hash_len + CRC_LEN + OFFSET_LEN,
43 hash_len,
44 })
45 }
46
47 pub(crate) fn push(&self, id: ObjectId, crc32: Crc32, offset: PackOffset) -> io::Result<()> {
48 let mut guard = self.buckets[id.first_byte() as usize]
49 .lock()
50 .expect("spool bucket poisoned");
51 guard.write_all(id.as_slice())?;
52 guard.write_all(&crc32.get().to_be_bytes())?;
53 guard.write_all(&offset.get().to_be_bytes())
54 }
55
56 fn cumulative_fanout(&self) -> Result<[u32; 256], PackError> {
57 let mut fanout = [0u32; 256];
58 self.buckets.iter().enumerate().try_for_each(
59 |(bucket, cell)| -> Result<(), PackError> {
60 let mut guard = cell.lock().expect("spool bucket poisoned");
61 guard.flush()?;
62 let len = guard.get_ref().metadata()?.len() as usize;
63 fanout[bucket] = (len / self.record_len) as u32;
64 Ok(())
65 },
66 )?;
67 fanout.iter_mut().fold(0u32, |acc, count| {
68 *count += acc;
69 *count
70 });
71 Ok(fanout)
72 }
73
74 fn visit_sorted(
75 &self,
76 mut visit: impl FnMut(&Record) -> Result<(), PackError>,
77 ) -> Result<(), PackError> {
78 self.buckets.iter().try_for_each(|cell| {
79 let mut records = self.read_bucket(cell)?;
80 records.sort_unstable_by_key(|record| record.id);
81 records.iter().try_for_each(&mut visit)
82 })
83 }
84
85 fn read_bucket(
86 &self,
87 cell: &Mutex<BufWriter<std::fs::File>>,
88 ) -> Result<Vec<Record>, PackError> {
89 let mut guard = cell.lock().expect("spool bucket poisoned");
90 guard.flush()?;
91 let file = guard.get_ref();
92 let len = file.metadata()?.len() as usize;
93 let mut bytes = vec![0u8; len];
94 file.read_exact_at(&mut bytes, 0)?;
95 drop(guard);
96 bytes
97 .chunks_exact(self.record_len)
98 .map(|chunk| {
99 let (id, rest) = chunk.split_at(self.hash_len);
100 Ok(Record {
101 id: ObjectId::try_from(id)
102 .map_err(|error| PackError::Pack(format!("spool record oid: {error}")))?,
103 crc32: Crc32::new(u32::from_be_bytes(
104 rest[..CRC_LEN].try_into().expect("crc slice"),
105 )),
106 offset: PackOffset::new(u64::from_be_bytes(
107 rest[CRC_LEN..].try_into().expect("offset slice"),
108 )),
109 })
110 })
111 .collect()
112 }
113}
114
115fn feed(out: &mut dyn Write, hasher: &mut gix_hash::Hasher, buf: &[u8]) -> io::Result<()> {
116 hasher.update(buf);
117 out.write_all(buf)
118}
119
120pub(crate) fn write_v2_index(
121 out: &mut dyn Write,
122 records: &Spool,
123 pack_hash: &ObjectId,
124 kind: gix::hash::Kind,
125) -> Result<ObjectId, PackError> {
126 let mut hasher = gix_hash::hasher(kind);
127 feed(out, &mut hasher, V2_SIGNATURE)?;
128 feed(out, &mut hasher, &V2_VERSION.to_be_bytes())?;
129
130 records
131 .cumulative_fanout()?
132 .iter()
133 .try_for_each(|count| feed(out, &mut hasher, &count.to_be_bytes()))?;
134 records.visit_sorted(|record| Ok(feed(out, &mut hasher, record.id.as_slice())?))?;
135 records
136 .visit_sorted(|record| Ok(feed(out, &mut hasher, &record.crc32.get().to_be_bytes())?))?;
137
138 let mut large_offsets = Vec::<u64>::new();
139 records.visit_sorted(|record| {
140 let encoded = if record.offset.get() > LARGE_OFFSET_THRESHOLD {
141 let position = large_offsets.len() as u32;
142 large_offsets.push(record.offset.get());
143 position | HIGH_BIT
144 } else {
145 record.offset.get() as u32
146 };
147 Ok(feed(out, &mut hasher, &encoded.to_be_bytes())?)
148 })?;
149 large_offsets
150 .iter()
151 .try_for_each(|offset| feed(out, &mut hasher, &offset.to_be_bytes()))?;
152
153 feed(out, &mut hasher, pack_hash.as_slice())?;
154
155 let index_hash = hasher
156 .try_finalize()
157 .map_err(|error| PackError::Pack(format!("finalize index hash: {error}")))?;
158 out.write_all(index_hash.as_slice())?;
159 out.flush()?;
160 Ok(index_hash)
161}
162
163#[cfg(test)]
164mod tests {
165 use super::*;
166
167 fn oid(seed: u8) -> ObjectId {
168 let mut raw = [0u8; 20];
169 raw[0] = seed;
170 raw[19] = seed;
171 ObjectId::try_from(raw.as_slice()).unwrap()
172 }
173
174 #[test]
175 fn large_offsets_round_trip_through_the_index_reader() {
176 let records = [
177 (oid(0x02), 0x1111_1111u32, 12u64),
178 (oid(0x40), 0x2222_2222, LARGE_OFFSET_THRESHOLD),
179 (oid(0x80), 0x3333_3333, 0x1_2345_6789),
180 (oid(0xc0), 0x4444_4444, LARGE_OFFSET_THRESHOLD + 1),
181 ];
182 let spool = Spool::new(gix::hash::Kind::Sha1).unwrap();
183 records.iter().for_each(|(id, crc32, offset)| {
184 spool
185 .push(*id, Crc32::new(*crc32), PackOffset::new(*offset))
186 .unwrap()
187 });
188 let pack_hash = oid(0xaa);
189
190 let mut buf = Vec::new();
191 let index_hash =
192 write_v2_index(&mut buf, &spool, &pack_hash, gix::hash::Kind::Sha1).unwrap();
193
194 let dir = tempfile::tempdir().unwrap();
195 let path = dir.path().join("pack-under-test.idx");
196 std::fs::write(&path, &buf).unwrap();
197 let index = gix_pack::index::File::at(&path, gix::hash::Kind::Sha1).unwrap();
198
199 assert_eq!(index.num_objects(), records.len() as u32);
200 assert_eq!(index.index_checksum(), index_hash);
201 assert_eq!(index.pack_checksum(), pack_hash);
202 records.iter().for_each(|(id, crc32, offset)| {
203 let at = index
204 .lookup(*id)
205 .expect("written oid resolves in the index");
206 assert_eq!(index.oid_at_index(at), id.as_ref());
207 assert_eq!(index.pack_offset_at_index(at), *offset);
208 assert_eq!(index.crc32_at_index(at), Some(*crc32));
209 });
210 }
211}