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