| 1 | // This program is free software; you can redistribute it and/or modify |
| 2 | // it under the terms of the GNU General Public License as published by |
| 3 | // the Free Software Foundation: version 2 of the License, dated June 1991. |
| 4 | // |
| 5 | // This program is distributed in the hope that it will be useful, |
| 6 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 7 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 8 | // GNU General Public License for more details. |
| 9 | // |
| 10 | // You should have received a copy of the GNU General Public License along |
| 11 | // with this program; if not, see <https://www.gnu.org/licenses/>. |
| 12 | |
| 13 | use crate::hash::{HashAlgorithm, ObjectID, GIT_MAX_RAWSZ}; |
| 14 | use std::collections::BTreeMap; |
| 15 | use std::convert::TryInto; |
| 16 | use std::io::{self, Write}; |
| 17 | |
| 18 | /// The type of object stored in the map. |
| 19 | /// |
| 20 | /// If this value is `Reserved`, then it is never written to disk and is used primarily to store |
| 21 | /// certain hard-coded objects, like the empty tree, empty blob, or null object ID. |
| 22 | /// |
| 23 | /// If this value is `LooseObject`, then this represents a loose object. `Shallow` represents a |
| 24 | /// shallow commit, its parent, or its tree. `Submodule` represents a submodule commit. |
| 25 | #[repr(C)] |
| 26 | #[derive(Debug, Clone, Copy, Ord, PartialOrd, Eq, PartialEq)] |
| 27 | pub enum MapType { |
| 28 | Reserved = 0, |
| 29 | LooseObject = 1, |
| 30 | Shallow = 2, |
| 31 | Submodule = 3, |
| 32 | } |
| 33 | |
| 34 | impl MapType { |
| 35 | pub fn from_u32(n: u32) -> Option<MapType> { |
| 36 | match n { |
| 37 | 0 => Some(Self::Reserved), |
| 38 | 1 => Some(Self::LooseObject), |
| 39 | 2 => Some(Self::Shallow), |
| 40 | 3 => Some(Self::Submodule), |
| 41 | _ => None, |
| 42 | } |
| 43 | } |
| 44 | } |
| 45 | |
| 46 | /// The value of an object stored in a `ObjectMemoryMap`. |
| 47 | /// |
| 48 | /// This keeps the object ID to which the key is mapped and its kind together. |
| 49 | struct MappedObject { |
| 50 | oid: ObjectID, |
| 51 | kind: MapType, |
| 52 | } |
| 53 | |
| 54 | /// Memory storage for a loose object. |
| 55 | struct ObjectMemoryMap { |
| 56 | to_compat: BTreeMap<ObjectID, MappedObject>, |
| 57 | to_storage: BTreeMap<ObjectID, MappedObject>, |
| 58 | compat: HashAlgorithm, |
| 59 | storage: HashAlgorithm, |
| 60 | } |
| 61 | |
| 62 | impl ObjectMemoryMap { |
| 63 | /// Create a new `ObjectMemoryMap`. |
| 64 | /// |
| 65 | /// The storage and compatibility `HashAlgorithm` instances are used to store the object IDs in |
| 66 | /// the correct map. |
| 67 | fn new(storage: HashAlgorithm, compat: HashAlgorithm) -> Self { |
| 68 | Self { |
| 69 | to_compat: BTreeMap::new(), |
| 70 | to_storage: BTreeMap::new(), |
| 71 | compat, |
| 72 | storage, |
| 73 | } |
| 74 | } |
| 75 | |
| 76 | fn len(&self) -> usize { |
| 77 | self.to_compat.len() |
| 78 | } |
| 79 | |
| 80 | /// Write this map to an interface implementing `std::io::Write`. |
| 81 | fn write<W: Write>(&self, wrtr: W) -> io::Result<()> { |
| 82 | const VERSION_NUMBER: u32 = 1; |
| 83 | const NUM_OBJECT_FORMATS: u32 = 2; |
| 84 | const PADDING: [u8; 4] = [0u8; 4]; |
| 85 | |
| 86 | let mut wrtr = wrtr; |
| 87 | let header_size: u32 = (4 * 5) + (4 + 4 + 8) * NUM_OBJECT_FORMATS + 8; |
| 88 | |
| 89 | wrtr.write_all(b"LMAP")?; |
| 90 | wrtr.write_all(&VERSION_NUMBER.to_be_bytes())?; |
| 91 | wrtr.write_all(&header_size.to_be_bytes())?; |
| 92 | wrtr.write_all(&(self.to_compat.len() as u32).to_be_bytes())?; |
| 93 | wrtr.write_all(&NUM_OBJECT_FORMATS.to_be_bytes())?; |
| 94 | |
| 95 | let storage_short_len = self.find_short_name_len(&self.to_compat, self.storage); |
| 96 | let compat_short_len = self.find_short_name_len(&self.to_storage, self.compat); |
| 97 | |
| 98 | let storage_npadding = Self::required_nul_padding(self.to_compat.len(), storage_short_len); |
| 99 | let compat_npadding = Self::required_nul_padding(self.to_compat.len(), compat_short_len); |
| 100 | |
| 101 | let mut offset: u64 = header_size as u64; |
| 102 | |
| 103 | for (algo, len, npadding) in &[ |
| 104 | (self.storage, storage_short_len, storage_npadding), |
| 105 | (self.compat, compat_short_len, compat_npadding), |
| 106 | ] { |
| 107 | wrtr.write_all(&algo.format_id().to_be_bytes())?; |
| 108 | wrtr.write_all(&(*len as u32).to_be_bytes())?; |
| 109 | |
| 110 | offset += *npadding; |
| 111 | wrtr.write_all(&offset.to_be_bytes())?; |
| 112 | |
| 113 | offset += self.to_compat.len() as u64 * (*len as u64 + algo.raw_len() as u64 + 4); |
| 114 | } |
| 115 | |
| 116 | wrtr.write_all(&offset.to_be_bytes())?; |
| 117 | |
| 118 | let order_map: BTreeMap<&ObjectID, usize> = self |
| 119 | .to_compat |
| 120 | .keys() |
| 121 | .enumerate() |
| 122 | .map(|(i, oid)| (oid, i)) |
| 123 | .collect(); |
| 124 | |
| 125 | wrtr.write_all(&PADDING[0..storage_npadding as usize])?; |
| 126 | for oid in self.to_compat.keys() { |
| 127 | wrtr.write_all(&oid.as_slice().unwrap()[0..storage_short_len])?; |
| 128 | } |
| 129 | for oid in self.to_compat.keys() { |
| 130 | wrtr.write_all(oid.as_slice().unwrap())?; |
| 131 | } |
| 132 | for meta in self.to_compat.values() { |
| 133 | wrtr.write_all(&(meta.kind as u32).to_be_bytes())?; |
| 134 | } |
| 135 | |
| 136 | wrtr.write_all(&PADDING[0..compat_npadding as usize])?; |
| 137 | for oid in self.to_storage.keys() { |
| 138 | wrtr.write_all(&oid.as_slice().unwrap()[0..compat_short_len])?; |
| 139 | } |
| 140 | for meta in self.to_compat.values() { |
| 141 | wrtr.write_all(meta.oid.as_slice().unwrap())?; |
| 142 | } |
| 143 | for meta in self.to_storage.values() { |
| 144 | wrtr.write_all(&(order_map[&meta.oid] as u32).to_be_bytes())?; |
| 145 | } |
| 146 | |
| 147 | Ok(()) |
| 148 | } |
| 149 | |
| 150 | fn required_nul_padding(nitems: usize, short_len: usize) -> u64 { |
| 151 | let shortened_table_len = nitems as u64 * short_len as u64; |
| 152 | let misalignment = shortened_table_len & 3; |
| 153 | // If the value is 0, return 0; otherwise, return the difference from 4. |
| 154 | (4 - misalignment) & 3 |
| 155 | } |
| 156 | |
| 157 | fn last_matching_offset(a: &ObjectID, b: &ObjectID, algop: HashAlgorithm) -> usize { |
| 158 | for i in 0..=algop.raw_len() { |
| 159 | if a.hash[i] != b.hash[i] { |
| 160 | return i; |
| 161 | } |
| 162 | } |
| 163 | algop.raw_len() |
| 164 | } |
| 165 | |
| 166 | fn find_short_name_len( |
| 167 | &self, |
| 168 | map: &BTreeMap<ObjectID, MappedObject>, |
| 169 | algop: HashAlgorithm, |
| 170 | ) -> usize { |
| 171 | if map.len() <= 1 { |
| 172 | return 1; |
| 173 | } |
| 174 | let mut len = 1; |
| 175 | let mut iter = map.keys(); |
| 176 | let mut cur = match iter.next() { |
| 177 | Some(cur) => cur, |
| 178 | None => return len, |
| 179 | }; |
| 180 | for item in iter { |
| 181 | let offset = Self::last_matching_offset(cur, item, algop); |
| 182 | if offset >= len { |
| 183 | len = offset + 1; |
| 184 | } |
| 185 | cur = item; |
| 186 | } |
| 187 | if len > algop.raw_len() { |
| 188 | algop.raw_len() |
| 189 | } else { |
| 190 | len |
| 191 | } |
| 192 | } |
| 193 | } |
| 194 | |
| 195 | struct ObjectFormatData { |
| 196 | data_off: usize, |
| 197 | shortened_len: usize, |
| 198 | full_off: usize, |
| 199 | mapping_off: Option<usize>, |
| 200 | } |
| 201 | |
| 202 | pub struct MmapedObjectMapIter<'a> { |
| 203 | offset: usize, |
| 204 | algos: Vec<HashAlgorithm>, |
| 205 | source: &'a MmapedObjectMap<'a>, |
| 206 | } |
| 207 | |
| 208 | impl<'a> Iterator for MmapedObjectMapIter<'a> { |
| 209 | type Item = Vec<ObjectID>; |
| 210 | |
| 211 | fn next(&mut self) -> Option<Self::Item> { |
| 212 | if self.offset >= self.source.nitems { |
| 213 | return None; |
| 214 | } |
| 215 | let offset = self.offset; |
| 216 | self.offset += 1; |
| 217 | let v: Vec<ObjectID> = self |
| 218 | .algos |
| 219 | .iter() |
| 220 | .cloned() |
| 221 | .filter_map(|algo| self.source.oid_from_offset(offset, algo)) |
| 222 | .collect(); |
| 223 | if v.len() != self.algos.len() { |
| 224 | return None; |
| 225 | } |
| 226 | Some(v) |
| 227 | } |
| 228 | } |
| 229 | |
| 230 | #[allow(dead_code)] |
| 231 | pub struct MmapedObjectMap<'a> { |
| 232 | memory: &'a [u8], |
| 233 | nitems: usize, |
| 234 | meta_off: usize, |
| 235 | obj_formats: BTreeMap<HashAlgorithm, ObjectFormatData>, |
| 236 | main_algo: HashAlgorithm, |
| 237 | } |
| 238 | |
| 239 | #[derive(Debug)] |
| 240 | #[allow(dead_code)] |
| 241 | enum MmapedParseError { |
| 242 | HeaderTooSmall, |
| 243 | InvalidSignature, |
| 244 | InvalidVersion, |
| 245 | UnknownAlgorithm, |
| 246 | OffsetTooLarge, |
| 247 | TooFewObjectFormats, |
| 248 | UnalignedData, |
| 249 | InvalidTrailerOffset, |
| 250 | } |
| 251 | |
| 252 | #[allow(dead_code)] |
| 253 | impl<'a> MmapedObjectMap<'a> { |
| 254 | fn new( |
| 255 | slice: &'a [u8], |
| 256 | hash_algo: HashAlgorithm, |
| 257 | ) -> Result<MmapedObjectMap<'a>, MmapedParseError> { |
| 258 | let object_format_header_size = 4 + 4 + 8; |
| 259 | let trailer_offset_size = 8; |
| 260 | let header_size: usize = |
| 261 | 4 + 4 + 4 + 4 + 4 + object_format_header_size * 2 + trailer_offset_size; |
| 262 | if slice.len() < header_size { |
| 263 | return Err(MmapedParseError::HeaderTooSmall); |
| 264 | } |
| 265 | if slice[0..4] != *b"LMAP" { |
| 266 | return Err(MmapedParseError::InvalidSignature); |
| 267 | } |
| 268 | if Self::u32_at_offset(slice, 4) != 1 { |
| 269 | return Err(MmapedParseError::InvalidVersion); |
| 270 | } |
| 271 | let _ = Self::u32_at_offset(slice, 8) as usize; |
| 272 | let nitems = Self::u32_at_offset(slice, 12) as usize; |
| 273 | let nobj_formats = Self::u32_at_offset(slice, 16) as usize; |
| 274 | if nobj_formats < 2 { |
| 275 | return Err(MmapedParseError::TooFewObjectFormats); |
| 276 | } |
| 277 | let mut offset = 20; |
| 278 | let mut meta_off = None; |
| 279 | let mut data = BTreeMap::new(); |
| 280 | for i in 0..nobj_formats { |
| 281 | if offset + object_format_header_size + trailer_offset_size > slice.len() { |
| 282 | return Err(MmapedParseError::HeaderTooSmall); |
| 283 | } |
| 284 | let format_id = Self::u32_at_offset(slice, offset); |
| 285 | let shortened_len = Self::u32_at_offset(slice, offset + 4) as usize; |
| 286 | let data_off = Self::u64_at_offset(slice, offset + 8); |
| 287 | |
| 288 | let algo = HashAlgorithm::from_format_id(format_id) |
| 289 | .ok_or(MmapedParseError::UnknownAlgorithm)?; |
| 290 | let data_off: usize = data_off |
| 291 | .try_into() |
| 292 | .map_err(|_| MmapedParseError::OffsetTooLarge)?; |
| 293 | |
| 294 | // Every object format must have these entries. |
| 295 | let shortened_table_len = shortened_len |
| 296 | .checked_mul(nitems) |
| 297 | .ok_or(MmapedParseError::OffsetTooLarge)?; |
| 298 | let full_off = data_off |
| 299 | .checked_add(shortened_table_len) |
| 300 | .ok_or(MmapedParseError::OffsetTooLarge)?; |
| 301 | Self::verify_aligned(full_off)?; |
| 302 | Self::verify_valid(slice, full_off as u64)?; |
| 303 | |
| 304 | let full_length = algo |
| 305 | .raw_len() |
| 306 | .checked_mul(nitems) |
| 307 | .ok_or(MmapedParseError::OffsetTooLarge)?; |
| 308 | let off = full_length |
| 309 | .checked_add(full_off) |
| 310 | .ok_or(MmapedParseError::OffsetTooLarge)?; |
| 311 | Self::verify_aligned(off)?; |
| 312 | Self::verify_valid(slice, off as u64)?; |
| 313 | |
| 314 | // This is for the metadata for the first object format and for the order mapping for |
| 315 | // other object formats. |
| 316 | let meta_size = nitems |
| 317 | .checked_mul(4) |
| 318 | .ok_or(MmapedParseError::OffsetTooLarge)?; |
| 319 | let meta_end = off |
| 320 | .checked_add(meta_size) |
| 321 | .ok_or(MmapedParseError::OffsetTooLarge)?; |
| 322 | Self::verify_valid(slice, meta_end as u64)?; |
| 323 | |
| 324 | let mut mapping_off = None; |
| 325 | if i == 0 { |
| 326 | meta_off = Some(off); |
| 327 | } else { |
| 328 | mapping_off = Some(off); |
| 329 | } |
| 330 | |
| 331 | data.insert( |
| 332 | algo, |
| 333 | ObjectFormatData { |
| 334 | data_off, |
| 335 | shortened_len, |
| 336 | full_off, |
| 337 | mapping_off, |
| 338 | }, |
| 339 | ); |
| 340 | offset += object_format_header_size; |
| 341 | } |
| 342 | let trailer = Self::u64_at_offset(slice, offset); |
| 343 | Self::verify_aligned(trailer as usize)?; |
| 344 | Self::verify_valid(slice, trailer)?; |
| 345 | let end = trailer |
| 346 | .checked_add(hash_algo.raw_len() as u64) |
| 347 | .ok_or(MmapedParseError::OffsetTooLarge)?; |
| 348 | if end != slice.len() as u64 { |
| 349 | return Err(MmapedParseError::InvalidTrailerOffset); |
| 350 | } |
| 351 | match meta_off { |
| 352 | Some(meta_off) => Ok(MmapedObjectMap { |
| 353 | memory: slice, |
| 354 | nitems, |
| 355 | meta_off, |
| 356 | obj_formats: data, |
| 357 | main_algo: hash_algo, |
| 358 | }), |
| 359 | None => Err(MmapedParseError::TooFewObjectFormats), |
| 360 | } |
| 361 | } |
| 362 | |
| 363 | fn iter(&self) -> MmapedObjectMapIter<'_> { |
| 364 | let mut algos = Vec::with_capacity(self.obj_formats.len()); |
| 365 | algos.push(self.main_algo); |
| 366 | for algo in self.obj_formats.keys().cloned() { |
| 367 | if algo != self.main_algo { |
| 368 | algos.push(algo); |
| 369 | } |
| 370 | } |
| 371 | MmapedObjectMapIter { |
| 372 | offset: 0, |
| 373 | algos, |
| 374 | source: self, |
| 375 | } |
| 376 | } |
| 377 | |
| 378 | /// Treats `sl` as if it were a set of slices of `wanted.len()` bytes, and searches for |
| 379 | /// `wanted` within it. |
| 380 | /// |
| 381 | /// If found, returns the offset of the subslice in `sl`. |
| 382 | /// |
| 383 | /// ``` |
| 384 | /// let sl = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; |
| 385 | /// |
| 386 | /// assert_eq!(MmapedObjectMap::binary_search_slice(sl, &[2, 3]), Some(1)); |
| 387 | /// assert_eq!(MmapedObjectMap::binary_search_slice(sl, &[6, 7]), Some(4)); |
| 388 | /// assert_eq!(MmapedObjectMap::binary_search_slice(sl, &[1, 2]), None); |
| 389 | /// assert_eq!(MmapedObjectMap::binary_search_slice(sl, &[10, 20]), None); |
| 390 | /// ``` |
| 391 | fn binary_search_slice(sl: &[u8], wanted: &[u8]) -> Option<usize> { |
| 392 | let len = wanted.len(); |
| 393 | let res = sl.binary_search_by(|item| { |
| 394 | // We would like element_offset, but that is currently nightly only. Instead, do a |
| 395 | // pointer subtraction to find the index. |
| 396 | let index = unsafe { (item as *const u8).offset_from(sl.as_ptr()) } as usize; |
| 397 | // Now we have the index of this object. Round it down to the nearest full-sized |
| 398 | // chunk to find the actual offset where this starts. |
| 399 | let index = index - (index % len); |
| 400 | // Compute the comparison of that value instead, which will provide the expected |
| 401 | // result. |
| 402 | sl[index..index + wanted.len()].cmp(wanted) |
| 403 | }); |
| 404 | res.ok().map(|offset| offset / len) |
| 405 | } |
| 406 | |
| 407 | /// Look up `oid` in the map in order to convert it to `algo`. |
| 408 | /// |
| 409 | /// If this object is in the map, return the offset in the table for the main algorithm. |
| 410 | fn look_up_object(&self, oid: &ObjectID) -> Option<usize> { |
| 411 | let oid_algo = HashAlgorithm::from_u32(oid.algo)?; |
| 412 | let params = self.obj_formats.get(&oid_algo)?; |
| 413 | let short_table = |
| 414 | &self.memory[params.data_off..params.data_off + (params.shortened_len * self.nitems)]; |
| 415 | let index = Self::binary_search_slice( |
| 416 | short_table, |
| 417 | &oid.as_slice().unwrap()[0..params.shortened_len], |
| 418 | )?; |
| 419 | match params.mapping_off { |
| 420 | Some(from_off) => { |
| 421 | // oid is in a compatibility algorithm. Find the mapping index. |
| 422 | let mapped = Self::u32_at_offset(self.memory, from_off + index * 4) as usize; |
| 423 | if mapped >= self.nitems { |
| 424 | return None; |
| 425 | } |
| 426 | let oid_offset = params.full_off + mapped * oid_algo.raw_len(); |
| 427 | if self.memory[oid_offset..oid_offset + oid_algo.raw_len()] |
| 428 | != *oid.as_slice().unwrap() |
| 429 | { |
| 430 | return None; |
| 431 | } |
| 432 | Some(mapped) |
| 433 | } |
| 434 | None => { |
| 435 | // oid is in the main algorithm. Find the object ID in the main map to confirm |
| 436 | // it's correct. |
| 437 | let oid_offset = params.full_off + index * oid_algo.raw_len(); |
| 438 | if self.memory[oid_offset..oid_offset + oid_algo.raw_len()] |
| 439 | != *oid.as_slice().unwrap() |
| 440 | { |
| 441 | return None; |
| 442 | } |
| 443 | Some(index) |
| 444 | } |
| 445 | } |
| 446 | } |
| 447 | |
| 448 | #[allow(dead_code)] |
| 449 | fn map_object(&self, oid: &ObjectID, algo: HashAlgorithm) -> Option<MappedObject> { |
| 450 | let main = self.look_up_object(oid)?; |
| 451 | let meta = MapType::from_u32(Self::u32_at_offset(self.memory, self.meta_off + (main * 4)))?; |
| 452 | Some(MappedObject { |
| 453 | oid: self.oid_from_offset(main, algo)?, |
| 454 | kind: meta, |
| 455 | }) |
| 456 | } |
| 457 | |
| 458 | fn map_oid(&self, oid: &ObjectID, algo: HashAlgorithm) -> Option<ObjectID> { |
| 459 | if algo as u32 == oid.algo { |
| 460 | return Some(oid.clone()); |
| 461 | } |
| 462 | |
| 463 | let main = self.look_up_object(oid)?; |
| 464 | self.oid_from_offset(main, algo) |
| 465 | } |
| 466 | |
| 467 | fn oid_from_offset(&self, offset: usize, algo: HashAlgorithm) -> Option<ObjectID> { |
| 468 | let aparams = self.obj_formats.get(&algo)?; |
| 469 | |
| 470 | let mut hash = [0u8; GIT_MAX_RAWSZ]; |
| 471 | let len = algo.raw_len(); |
| 472 | let oid_off = aparams.full_off + (offset * len); |
| 473 | hash[0..len].copy_from_slice(&self.memory[oid_off..oid_off + len]); |
| 474 | Some(ObjectID { |
| 475 | hash, |
| 476 | algo: algo as u32, |
| 477 | }) |
| 478 | } |
| 479 | |
| 480 | fn u32_at_offset(slice: &[u8], offset: usize) -> u32 { |
| 481 | u32::from_be_bytes(slice[offset..offset + 4].try_into().unwrap()) |
| 482 | } |
| 483 | |
| 484 | fn u64_at_offset(slice: &[u8], offset: usize) -> u64 { |
| 485 | u64::from_be_bytes(slice[offset..offset + 8].try_into().unwrap()) |
| 486 | } |
| 487 | |
| 488 | fn verify_aligned(offset: usize) -> Result<(), MmapedParseError> { |
| 489 | if (offset & 3) != 0 { |
| 490 | return Err(MmapedParseError::UnalignedData); |
| 491 | } |
| 492 | Ok(()) |
| 493 | } |
| 494 | |
| 495 | fn verify_valid(slice: &[u8], offset: u64) -> Result<(), MmapedParseError> { |
| 496 | if offset >= slice.len() as u64 { |
| 497 | return Err(MmapedParseError::OffsetTooLarge); |
| 498 | } |
| 499 | Ok(()) |
| 500 | } |
| 501 | } |
| 502 | |
| 503 | /// A map for loose and other non-packed object IDs that maps between a storage and compatibility |
| 504 | /// mapping. |
| 505 | /// |
| 506 | /// In addition to the in-memory option, there is an optional batched storage, which can be used to |
| 507 | /// write objects to disk in an efficient way. |
| 508 | pub struct ObjectMap { |
| 509 | mem: ObjectMemoryMap, |
| 510 | batch: Option<ObjectMemoryMap>, |
| 511 | } |
| 512 | |
| 513 | impl ObjectMap { |
| 514 | /// Create a new `ObjectMap` with the given hash algorithms. |
| 515 | /// |
| 516 | /// This initializes the memory map to automatically map the empty tree, empty blob, and null |
| 517 | /// object ID. |
| 518 | pub fn new(storage: HashAlgorithm, compat: HashAlgorithm) -> Self { |
| 519 | let mut map = ObjectMemoryMap::new(storage, compat); |
| 520 | for (main, compat) in &[ |
| 521 | (storage.empty_tree(), compat.empty_tree()), |
| 522 | (storage.empty_blob(), compat.empty_blob()), |
| 523 | (storage.null_oid(), compat.null_oid()), |
| 524 | ] { |
| 525 | map.to_storage.insert( |
| 526 | (*compat).clone(), |
| 527 | MappedObject { |
| 528 | oid: (*main).clone(), |
| 529 | kind: MapType::Reserved, |
| 530 | }, |
| 531 | ); |
| 532 | map.to_compat.insert( |
| 533 | (*main).clone(), |
| 534 | MappedObject { |
| 535 | oid: (*compat).clone(), |
| 536 | kind: MapType::Reserved, |
| 537 | }, |
| 538 | ); |
| 539 | } |
| 540 | Self { |
| 541 | mem: map, |
| 542 | batch: None, |
| 543 | } |
| 544 | } |
| 545 | |
| 546 | pub fn hash_algo(&self) -> HashAlgorithm { |
| 547 | self.mem.storage |
| 548 | } |
| 549 | |
| 550 | /// Start a batch for efficient writing. |
| 551 | /// |
| 552 | /// If there is already a batch started, this does nothing and the existing batch is retained. |
| 553 | pub fn start_batch(&mut self) { |
| 554 | if self.batch.is_none() { |
| 555 | self.batch = Some(ObjectMemoryMap::new(self.mem.storage, self.mem.compat)); |
| 556 | } |
| 557 | } |
| 558 | |
| 559 | pub fn batch_len(&self) -> Option<usize> { |
| 560 | self.batch.as_ref().map(|b| b.len()) |
| 561 | } |
| 562 | |
| 563 | /// If a batch exists, write it to the writer. |
| 564 | pub fn finish_batch<W: Write>(&mut self, w: W) -> io::Result<()> { |
| 565 | if let Some(txn) = self.batch.take() { |
| 566 | txn.write(w)?; |
| 567 | } |
| 568 | Ok(()) |
| 569 | } |
| 570 | |
| 571 | /// If a batch exists, write it to the writer. |
| 572 | pub fn abort_batch(&mut self) { |
| 573 | self.batch = None; |
| 574 | } |
| 575 | |
| 576 | /// Return whether there is a batch already started. |
| 577 | /// |
| 578 | /// If you just want a batch to exist and don't care whether one has already been started, you |
| 579 | /// may simply call `start_batch` unconditionally. |
| 580 | pub fn has_batch(&self) -> bool { |
| 581 | self.batch.is_some() |
| 582 | } |
| 583 | |
| 584 | /// Insert an object into the map. |
| 585 | /// |
| 586 | /// If `write` is true and there is a batch started, write the object into the batch as well as |
| 587 | /// into the memory map. |
| 588 | pub fn insert(&mut self, oid1: &ObjectID, oid2: &ObjectID, kind: MapType, write: bool) { |
| 589 | let (compat_oid, storage_oid) = |
| 590 | if HashAlgorithm::from_u32(oid1.algo) == Some(self.mem.compat) { |
| 591 | (oid1, oid2) |
| 592 | } else { |
| 593 | (oid2, oid1) |
| 594 | }; |
| 595 | Self::insert_into(&mut self.mem, storage_oid, compat_oid, kind); |
| 596 | if write { |
| 597 | if let Some(ref mut batch) = self.batch { |
| 598 | Self::insert_into(batch, storage_oid, compat_oid, kind); |
| 599 | } |
| 600 | } |
| 601 | } |
| 602 | |
| 603 | fn insert_into( |
| 604 | map: &mut ObjectMemoryMap, |
| 605 | storage: &ObjectID, |
| 606 | compat: &ObjectID, |
| 607 | kind: MapType, |
| 608 | ) { |
| 609 | map.to_compat.insert( |
| 610 | storage.clone(), |
| 611 | MappedObject { |
| 612 | oid: compat.clone(), |
| 613 | kind, |
| 614 | }, |
| 615 | ); |
| 616 | map.to_storage.insert( |
| 617 | compat.clone(), |
| 618 | MappedObject { |
| 619 | oid: storage.clone(), |
| 620 | kind, |
| 621 | }, |
| 622 | ); |
| 623 | } |
| 624 | |
| 625 | #[allow(dead_code)] |
| 626 | fn map_object(&self, oid: &ObjectID, algo: HashAlgorithm) -> Option<&MappedObject> { |
| 627 | let map = if algo == self.mem.storage { |
| 628 | &self.mem.to_storage |
| 629 | } else { |
| 630 | &self.mem.to_compat |
| 631 | }; |
| 632 | map.get(oid) |
| 633 | } |
| 634 | |
| 635 | #[allow(dead_code)] |
| 636 | fn map_oid<'a, 'b: 'a>( |
| 637 | &'b self, |
| 638 | oid: &'a ObjectID, |
| 639 | algo: HashAlgorithm, |
| 640 | ) -> Option<&'a ObjectID> { |
| 641 | if algo as u32 == oid.algo { |
| 642 | return Some(oid); |
| 643 | } |
| 644 | let entry = self.map_object(oid, algo); |
| 645 | entry.map(|obj| &obj.oid) |
| 646 | } |
| 647 | } |
| 648 | |
| 649 | #[cfg(test)] |
| 650 | mod tests { |
| 651 | use super::{MapType, MmapedObjectMap, ObjectMap, ObjectMemoryMap}; |
| 652 | use crate::hash::{CryptoDigest, CryptoHasher, HashAlgorithm, ObjectID}; |
| 653 | use std::convert::TryInto; |
| 654 | use std::io::{self, Cursor, Write}; |
| 655 | |
| 656 | struct TrailingWriter { |
| 657 | curs: Cursor<Vec<u8>>, |
| 658 | hasher: CryptoHasher, |
| 659 | } |
| 660 | |
| 661 | impl TrailingWriter { |
| 662 | fn new() -> Self { |
| 663 | Self { |
| 664 | curs: Cursor::new(Vec::new()), |
| 665 | hasher: CryptoHasher::new(HashAlgorithm::SHA256), |
| 666 | } |
| 667 | } |
| 668 | |
| 669 | fn finalize(mut self) -> Vec<u8> { |
| 670 | let _ = self.hasher.flush(); |
| 671 | let mut v = self.curs.into_inner(); |
| 672 | v.extend(self.hasher.into_vec()); |
| 673 | v |
| 674 | } |
| 675 | } |
| 676 | |
| 677 | impl Write for TrailingWriter { |
| 678 | fn write(&mut self, data: &[u8]) -> io::Result<usize> { |
| 679 | self.hasher.write_all(data)?; |
| 680 | self.curs.write_all(data)?; |
| 681 | Ok(data.len()) |
| 682 | } |
| 683 | |
| 684 | fn flush(&mut self) -> io::Result<()> { |
| 685 | self.hasher.flush()?; |
| 686 | self.curs.flush()?; |
| 687 | Ok(()) |
| 688 | } |
| 689 | } |
| 690 | |
| 691 | fn sha1_oid(b: &[u8]) -> ObjectID { |
| 692 | assert_eq!(b.len(), 20); |
| 693 | let mut data = [0u8; 32]; |
| 694 | data[0..20].copy_from_slice(b); |
| 695 | ObjectID { |
| 696 | hash: data, |
| 697 | algo: HashAlgorithm::SHA1 as u32, |
| 698 | } |
| 699 | } |
| 700 | |
| 701 | fn sha256_oid(b: &[u8]) -> ObjectID { |
| 702 | assert_eq!(b.len(), 32); |
| 703 | ObjectID { |
| 704 | hash: b.try_into().unwrap(), |
| 705 | algo: HashAlgorithm::SHA256 as u32, |
| 706 | } |
| 707 | } |
| 708 | |
| 709 | #[allow(clippy::type_complexity)] |
| 710 | fn test_entries() -> &'static [(&'static str, &'static [u8], &'static [u8], MapType, bool)] { |
| 711 | // These are all example blobs containing the content in the first argument. |
| 712 | &[ |
| 713 | ("abc", b"\xf2\xba\x8f\x84\xab\x5c\x1b\xce\x84\xa7\xb4\x41\xcb\x19\x59\xcf\xc7\x09\x3b\x7f", b"\xc1\xcf\x6e\x46\x50\x77\x93\x0e\x88\xdc\x51\x36\x64\x1d\x40\x2f\x72\xa2\x29\xdd\xd9\x96\xf6\x27\xd6\x0e\x96\x39\xea\xba\x35\xa6", MapType::LooseObject, false), |
| 714 | ("def", b"\x0c\x00\x38\x32\xe7\xbf\xa9\xca\x8b\x5c\x20\x35\xc9\xbd\x68\x4a\x5f\x26\x23\xbc", b"\x8a\x90\x17\x26\x48\x4d\xb0\xf2\x27\x9f\x30\x8d\x58\x96\xd9\x6b\xf6\x3a\xd6\xde\x95\x7c\xa3\x8a\xdc\x33\x61\x68\x03\x6e\xf6\x63", MapType::Shallow, true), |
| 715 | ("ghi", b"\x45\xa8\x2e\x29\x5c\x52\x47\x31\x14\xc5\x7c\x18\xf4\xf5\x23\x68\xdf\x2a\x3c\xfd", b"\x6e\x47\x4c\x74\xf5\xd7\x78\x14\xc7\xf7\xf0\x7c\x37\x80\x07\x90\x53\x42\xaf\x42\x81\xe6\x86\x8d\x33\x46\x45\x4b\xb8\x63\xab\xc3", MapType::Submodule, false), |
| 716 | ("jkl", b"\x45\x32\x8c\x36\xff\x2e\x9b\x9b\x4e\x59\x2c\x84\x7d\x3f\x9a\x7f\xd9\xb3\xe7\x16", b"\xc3\xee\xf7\x54\xa2\x1e\xc6\x9d\x43\x75\xbe\x6f\x18\x47\x89\xa8\x11\x6f\xd9\x66\xfc\x67\xdc\x31\xd2\x11\x15\x42\xc8\xd5\xa0\xaf", MapType::LooseObject, true), |
| 717 | ] |
| 718 | } |
| 719 | |
| 720 | fn test_map(write_all: bool) -> Box<ObjectMap> { |
| 721 | let mut map = Box::new(ObjectMap::new(HashAlgorithm::SHA256, HashAlgorithm::SHA1)); |
| 722 | |
| 723 | map.start_batch(); |
| 724 | |
| 725 | for (_blob_content, sha1, sha256, kind, swap) in test_entries() { |
| 726 | let s256 = sha256_oid(sha256); |
| 727 | let s1 = sha1_oid(sha1); |
| 728 | let write = write_all || (*kind as u32 & 2) == 0; |
| 729 | if *swap { |
| 730 | // Insert the item into the batch arbitrarily based on the type. This tests that |
| 731 | // we can specify either order and we'll do the right thing. |
| 732 | map.insert(&s256, &s1, *kind, write); |
| 733 | } else { |
| 734 | map.insert(&s1, &s256, *kind, write); |
| 735 | } |
| 736 | } |
| 737 | |
| 738 | map |
| 739 | } |
| 740 | |
| 741 | #[test] |
| 742 | fn can_read_and_write_format() { |
| 743 | for full in &[true, false] { |
| 744 | let mut map = test_map(*full); |
| 745 | let mut wrtr = TrailingWriter::new(); |
| 746 | map.finish_batch(&mut wrtr).unwrap(); |
| 747 | |
| 748 | assert!(!map.has_batch()); |
| 749 | |
| 750 | let data = wrtr.finalize(); |
| 751 | MmapedObjectMap::new(&data, HashAlgorithm::SHA256).unwrap(); |
| 752 | } |
| 753 | } |
| 754 | |
| 755 | #[test] |
| 756 | fn looks_up_from_mmaped() { |
| 757 | let mut map = test_map(true); |
| 758 | let mut wrtr = TrailingWriter::new(); |
| 759 | map.finish_batch(&mut wrtr).unwrap(); |
| 760 | |
| 761 | assert!(!map.has_batch()); |
| 762 | |
| 763 | let data = wrtr.finalize(); |
| 764 | let entries = test_entries(); |
| 765 | let map = MmapedObjectMap::new(&data, HashAlgorithm::SHA256).unwrap(); |
| 766 | |
| 767 | for (_, sha1, sha256, kind, _) in entries { |
| 768 | let s256 = sha256_oid(sha256); |
| 769 | let s1 = sha1_oid(sha1); |
| 770 | |
| 771 | let res = map.map_object(&s256, HashAlgorithm::SHA1).unwrap(); |
| 772 | assert_eq!(res.oid, s1); |
| 773 | assert_eq!(res.kind, *kind); |
| 774 | let res = map.map_oid(&s256, HashAlgorithm::SHA1).unwrap(); |
| 775 | assert_eq!(res, s1); |
| 776 | |
| 777 | let res = map.map_object(&s256, HashAlgorithm::SHA256).unwrap(); |
| 778 | assert_eq!(res.oid, s256); |
| 779 | assert_eq!(res.kind, *kind); |
| 780 | let res = map.map_oid(&s256, HashAlgorithm::SHA256).unwrap(); |
| 781 | assert_eq!(res, s256); |
| 782 | |
| 783 | let res = map.map_object(&s1, HashAlgorithm::SHA256).unwrap(); |
| 784 | assert_eq!(res.oid, s256); |
| 785 | assert_eq!(res.kind, *kind); |
| 786 | let res = map.map_oid(&s1, HashAlgorithm::SHA256).unwrap(); |
| 787 | assert_eq!(res, s256); |
| 788 | |
| 789 | let res = map.map_object(&s1, HashAlgorithm::SHA1).unwrap(); |
| 790 | assert_eq!(res.oid, s1); |
| 791 | assert_eq!(res.kind, *kind); |
| 792 | let res = map.map_oid(&s1, HashAlgorithm::SHA1).unwrap(); |
| 793 | assert_eq!(res, s1); |
| 794 | } |
| 795 | |
| 796 | for octet in &[0x00u8, 0x6d, 0x6e, 0x8a, 0xff] { |
| 797 | let missing_oid = ObjectID { |
| 798 | hash: [*octet; 32], |
| 799 | algo: HashAlgorithm::SHA256 as u32, |
| 800 | }; |
| 801 | |
| 802 | assert!(map.map_object(&missing_oid, HashAlgorithm::SHA1).is_none()); |
| 803 | assert!(map.map_oid(&missing_oid, HashAlgorithm::SHA1).is_none()); |
| 804 | |
| 805 | assert_eq!( |
| 806 | map.map_oid(&missing_oid, HashAlgorithm::SHA256).unwrap(), |
| 807 | missing_oid |
| 808 | ); |
| 809 | } |
| 810 | } |
| 811 | |
| 812 | #[test] |
| 813 | fn binary_searches_slices_correctly() { |
| 814 | let sl = &[ |
| 815 | 0, 1, 2, 15, 14, 13, 18, 10, 2, 20, 20, 20, 21, 21, 0, 21, 21, 1, 21, 21, 21, 21, 21, |
| 816 | 22, 22, 23, 24, |
| 817 | ]; |
| 818 | |
| 819 | let expected: &[(&[u8], Option<usize>)] = &[ |
| 820 | (&[0, 1, 2], Some(0)), |
| 821 | (&[15, 14, 13], Some(1)), |
| 822 | (&[18, 10, 2], Some(2)), |
| 823 | (&[20, 20, 20], Some(3)), |
| 824 | (&[21, 21, 0], Some(4)), |
| 825 | (&[21, 21, 1], Some(5)), |
| 826 | (&[21, 21, 21], Some(6)), |
| 827 | (&[21, 21, 22], Some(7)), |
| 828 | (&[22, 23, 24], Some(8)), |
| 829 | (&[2, 15, 14], None), |
| 830 | (&[0, 21, 21], None), |
| 831 | (&[21, 21, 23], None), |
| 832 | (&[22, 22, 23], None), |
| 833 | (&[0xff, 0xff, 0xff], None), |
| 834 | (&[0, 0, 0], None), |
| 835 | ]; |
| 836 | |
| 837 | for (wanted, value) in expected { |
| 838 | assert_eq!(MmapedObjectMap::binary_search_slice(sl, wanted), *value); |
| 839 | } |
| 840 | } |
| 841 | |
| 842 | #[test] |
| 843 | fn looks_up_oid_correctly() { |
| 844 | let map = test_map(false); |
| 845 | let entries = test_entries(); |
| 846 | |
| 847 | let s256 = sha256_oid(entries[0].2); |
| 848 | let s1 = sha1_oid(entries[0].1); |
| 849 | |
| 850 | let missing_oid = ObjectID { |
| 851 | hash: [0xffu8; 32], |
| 852 | algo: HashAlgorithm::SHA256 as u32, |
| 853 | }; |
| 854 | |
| 855 | let res = map.map_object(&s256, HashAlgorithm::SHA1).unwrap(); |
| 856 | assert_eq!(res.oid, s1); |
| 857 | assert_eq!(res.kind, MapType::LooseObject); |
| 858 | let res = map.map_oid(&s256, HashAlgorithm::SHA1).unwrap(); |
| 859 | assert_eq!(*res, s1); |
| 860 | |
| 861 | let res = map.map_object(&s1, HashAlgorithm::SHA256).unwrap(); |
| 862 | assert_eq!(res.oid, s256); |
| 863 | assert_eq!(res.kind, MapType::LooseObject); |
| 864 | let res = map.map_oid(&s1, HashAlgorithm::SHA256).unwrap(); |
| 865 | assert_eq!(*res, s256); |
| 866 | |
| 867 | assert!(map.map_object(&missing_oid, HashAlgorithm::SHA1).is_none()); |
| 868 | assert!(map.map_oid(&missing_oid, HashAlgorithm::SHA1).is_none()); |
| 869 | |
| 870 | assert_eq!( |
| 871 | *map.map_oid(&missing_oid, HashAlgorithm::SHA256).unwrap(), |
| 872 | missing_oid |
| 873 | ); |
| 874 | } |
| 875 | |
| 876 | #[test] |
| 877 | fn looks_up_known_oids_correctly() { |
| 878 | let map = test_map(false); |
| 879 | |
| 880 | let funcs: &[&dyn Fn(HashAlgorithm) -> &'static ObjectID] = &[ |
| 881 | &|h: HashAlgorithm| h.empty_tree(), |
| 882 | &|h: HashAlgorithm| h.empty_blob(), |
| 883 | &|h: HashAlgorithm| h.null_oid(), |
| 884 | ]; |
| 885 | |
| 886 | for f in funcs { |
| 887 | let s256 = f(HashAlgorithm::SHA256); |
| 888 | let s1 = f(HashAlgorithm::SHA1); |
| 889 | |
| 890 | let res = map.map_object(s256, HashAlgorithm::SHA1).unwrap(); |
| 891 | assert_eq!(res.oid, *s1); |
| 892 | assert_eq!(res.kind, MapType::Reserved); |
| 893 | let res = map.map_oid(s256, HashAlgorithm::SHA1).unwrap(); |
| 894 | assert_eq!(*res, *s1); |
| 895 | |
| 896 | let res = map.map_object(s1, HashAlgorithm::SHA256).unwrap(); |
| 897 | assert_eq!(res.oid, *s256); |
| 898 | assert_eq!(res.kind, MapType::Reserved); |
| 899 | let res = map.map_oid(s1, HashAlgorithm::SHA256).unwrap(); |
| 900 | assert_eq!(*res, *s256); |
| 901 | } |
| 902 | } |
| 903 | |
| 904 | #[test] |
| 905 | fn nul_padding() { |
| 906 | assert_eq!(ObjectMemoryMap::required_nul_padding(1, 1), 3); |
| 907 | assert_eq!(ObjectMemoryMap::required_nul_padding(2, 1), 2); |
| 908 | assert_eq!(ObjectMemoryMap::required_nul_padding(3, 1), 1); |
| 909 | assert_eq!(ObjectMemoryMap::required_nul_padding(2, 2), 0); |
| 910 | |
| 911 | assert_eq!(ObjectMemoryMap::required_nul_padding(39, 3), 3); |
| 912 | } |
| 913 | } |