1 /** 2 * BSD 2-Clause License 3 * 4 * Copyright (c) 2021, Khaled Emara 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright notice, this 11 * list of conditions and the following disclaimer. 12 * 13 * 2. Redistributions in binary form must reproduce the above copyright notice, 14 * this list of conditions and the following disclaimer in the documentation 15 * and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 20 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 24 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 use std::{ 29 cmp::Ordering, 30 io::{prelude::*, SeekFrom}, 31 mem, 32 }; 33 34 use byteorder::{BigEndian, LittleEndian, ReadBytesExt}; 35 use num_traits::{PrimInt, Unsigned}; 36 use uuid::Uuid; 37 38 use super::{ 39 bmbt_rec::BmbtRec, 40 definitions::{XfsFileoff, XfsFsblock}, 41 sb::Sb, 42 }; 43 44 pub const POINTERS_AREA_OFFSET: u16 = 0x808; 45 46 #[derive(Debug)] 47 pub struct BtreeBlock<T: PrimInt + Unsigned> { 48 pub bb_magic: u32, 49 pub bb_level: u16, 50 pub bb_numrecs: u16, 51 pub bb_leftsib: T, 52 pub bb_rightsib: T, 53 pub bb_blkno: u64, 54 pub bb_lsn: u64, 55 pub bb_uuid: Uuid, 56 pub bb_owner: u64, 57 pub bb_crc: u32, 58 pub bb_pad: u32, 59 } 60 61 impl<T: PrimInt + Unsigned> BtreeBlock<T> { from<R: BufRead + Seek>(buf_reader: &mut R, super_block: &Sb) -> BtreeBlock<T>62 pub fn from<R: BufRead + Seek>(buf_reader: &mut R, super_block: &Sb) -> BtreeBlock<T> { 63 let bb_magic = buf_reader.read_u32::<BigEndian>().unwrap(); 64 let bb_level = buf_reader.read_u16::<BigEndian>().unwrap(); 65 let bb_numrecs = buf_reader.read_u16::<BigEndian>().unwrap(); 66 67 let type_size = mem::size_of::<T>(); 68 let bb_leftsib = T::from(buf_reader.read_uint::<BigEndian>(type_size).unwrap()).unwrap(); 69 let bb_rightsib = T::from(buf_reader.read_uint::<BigEndian>(type_size).unwrap()).unwrap(); 70 71 let bb_blkno = buf_reader.read_u64::<BigEndian>().unwrap(); 72 let bb_lsn = buf_reader.read_u64::<BigEndian>().unwrap(); 73 let bb_uuid = Uuid::from_u128(buf_reader.read_u128::<BigEndian>().unwrap()); 74 let bb_owner = buf_reader.read_u64::<BigEndian>().unwrap(); 75 let bb_crc = buf_reader.read_u32::<LittleEndian>().unwrap(); 76 let bb_pad = buf_reader.read_u32::<BigEndian>().unwrap(); 77 78 if bb_uuid != super_block.sb_uuid { 79 panic!("UUID mismatch!"); 80 } 81 82 BtreeBlock { 83 bb_magic, 84 bb_level, 85 bb_numrecs, 86 bb_leftsib, 87 bb_rightsib, 88 bb_blkno, 89 bb_lsn, 90 bb_uuid, 91 bb_owner, 92 bb_crc, 93 bb_pad, 94 } 95 } 96 } 97 98 #[derive(Debug, Clone)] 99 pub struct BmdrBlock { 100 pub bb_level: u16, 101 pub bb_numrecs: u16, 102 } 103 104 impl BmdrBlock { from<R: BufRead>(buf_reader: &mut R) -> BmdrBlock105 pub fn from<R: BufRead>(buf_reader: &mut R) -> BmdrBlock { 106 let bb_level = buf_reader.read_u16::<BigEndian>().unwrap(); 107 let bb_numrecs = buf_reader.read_u16::<BigEndian>().unwrap(); 108 109 BmdrBlock { 110 bb_level, 111 bb_numrecs, 112 } 113 } 114 } 115 116 #[derive(Debug, Clone)] 117 pub struct BmbtKey { 118 pub br_startoff: XfsFileoff, 119 } 120 121 impl BmbtKey { from<R: BufRead>(buf_reader: &mut R) -> BmbtKey122 pub fn from<R: BufRead>(buf_reader: &mut R) -> BmbtKey { 123 let br_startoff = buf_reader.read_u64::<BigEndian>().unwrap(); 124 125 BmbtKey { br_startoff } 126 } 127 } 128 129 pub type XfsBmbtPtr = XfsFsblock; 130 pub type XfsBmdrPtr = XfsFsblock; 131 pub type XfsBmbtBlock = BtreeBlock<u64>; 132 133 #[derive(Debug, Clone)] 134 pub struct Btree { 135 pub bmdr: BmdrBlock, 136 pub keys: Vec<BmbtKey>, 137 pub ptrs: Vec<XfsBmbtPtr>, 138 } 139 140 impl Btree { map_block<R: BufRead + Seek>( &self, buf_reader: &mut R, super_block: &Sb, logical_block: XfsFileoff, ) -> XfsFsblock141 pub fn map_block<R: BufRead + Seek>( 142 &self, 143 buf_reader: &mut R, 144 super_block: &Sb, 145 logical_block: XfsFileoff, 146 ) -> XfsFsblock { 147 let mut low: i64 = 0; 148 let mut high: i64 = (self.bmdr.bb_numrecs - 1) as i64; 149 150 let mut predecessor = 0; 151 152 while low <= high { 153 let mid = low + ((high - low) / 2); 154 155 let key = self.keys[mid as usize].br_startoff; 156 157 match key.cmp(&logical_block) { 158 Ordering::Greater => { 159 high = mid - 1; 160 } 161 Ordering::Less => { 162 low = mid + 1; 163 predecessor = mid; 164 } 165 Ordering::Equal => { 166 predecessor = mid; 167 break; 168 } 169 } 170 } 171 172 buf_reader 173 .seek(SeekFrom::Start( 174 self.ptrs[predecessor as usize] * u64::from(super_block.sb_blocksize), 175 )) 176 .unwrap(); 177 178 let mut bmbt_block = XfsBmbtBlock::from(buf_reader.by_ref(), super_block); 179 let mut keys_offset = buf_reader.stream_position().unwrap(); 180 181 loop { 182 if bmbt_block.bb_level == 0 { 183 break; 184 } else { 185 let mut low: i64 = 0; 186 let mut high: i64 = (bmbt_block.bb_numrecs - 1) as i64; 187 188 let mut predecessor = 0; 189 190 while low <= high { 191 let mid = low + ((high - low) / 2); 192 193 buf_reader.seek(SeekFrom::Start(keys_offset)).unwrap(); 194 buf_reader 195 .seek(SeekFrom::Current(mid * (mem::size_of::<BmbtKey>() as i64))) 196 .unwrap(); 197 198 let key = BmbtKey::from(buf_reader.by_ref()).br_startoff; 199 200 match key.cmp(&logical_block) { 201 Ordering::Greater => { 202 high = mid - 1; 203 } 204 Ordering::Less => { 205 low = mid + 1; 206 predecessor = mid; 207 } 208 Ordering::Equal => { 209 predecessor = mid; 210 break; 211 } 212 } 213 } 214 215 buf_reader 216 .seek(SeekFrom::Start( 217 keys_offset - (mem::size_of::<XfsBmbtBlock>() as u64) 218 + u64::from(POINTERS_AREA_OFFSET), 219 )) 220 .unwrap(); 221 buf_reader.seek(SeekFrom::Current(predecessor * 8)).unwrap(); 222 223 let ptr = buf_reader.read_u64::<BigEndian>().unwrap(); 224 225 buf_reader 226 .seek(SeekFrom::Start(ptr * u64::from(super_block.sb_blocksize))) 227 .unwrap(); 228 229 bmbt_block = XfsBmbtBlock::from(buf_reader.by_ref(), super_block); 230 keys_offset = buf_reader.stream_position().unwrap(); 231 } 232 } 233 234 let recs_offset = buf_reader.stream_position().unwrap(); 235 236 let mut low: i64 = 0; 237 let mut high: i64 = (bmbt_block.bb_numrecs - 1) as i64; 238 239 let mut predecessor = 0; 240 241 while low <= high { 242 let mid = low + ((high - low) / 2); 243 244 buf_reader.seek(SeekFrom::Start(recs_offset)).unwrap(); 245 buf_reader 246 .seek(SeekFrom::Current(mid * (mem::size_of::<BmbtRec>() as i64))) 247 .unwrap(); 248 249 let key = BmbtRec::from(buf_reader.by_ref()).br_startoff; 250 251 match key.cmp(&logical_block) { 252 Ordering::Greater => { 253 high = mid - 1; 254 } 255 Ordering::Less => { 256 low = mid + 1; 257 predecessor = mid; 258 } 259 Ordering::Equal => { 260 predecessor = mid; 261 break; 262 } 263 } 264 } 265 266 buf_reader.seek(SeekFrom::Start(recs_offset)).unwrap(); 267 buf_reader 268 .seek(SeekFrom::Current( 269 predecessor * (mem::size_of::<BmbtRec>() as i64), 270 )) 271 .unwrap(); 272 273 let rec = BmbtRec::from(buf_reader.by_ref()); 274 275 rec.br_startblock + (logical_block - rec.br_startoff) 276 } 277 } 278