1 /* 2 * Copyright (C) 2021 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 use anyhow::{anyhow, bail, Result}; 17 use std::collections::HashMap; 18 use std::ffi::{CStr, CString}; 19 use std::io; 20 use std::os::unix::ffi::OsStrExt; 21 22 /// `InodeTable` is a table of `InodeData` indexed by `Inode`. 23 #[derive(Debug)] 24 pub struct InodeTable { 25 table: Vec<InodeData>, 26 } 27 28 /// `Inode` is the handle (or index in the table) to `InodeData` which represents an inode. 29 pub type Inode = u64; 30 31 const INVALID: Inode = 0; 32 const ROOT: Inode = 1; 33 34 #[cfg(multi_tenant)] 35 const READ_MODE: u32 = libc::S_IRUSR | libc::S_IRGRP; 36 #[cfg(multi_tenant)] 37 const EXECUTE_MODE: u32 = libc::S_IXUSR | libc::S_IXGRP; 38 39 #[cfg(not(multi_tenant))] 40 const READ_MODE: u32 = libc::S_IRUSR; 41 #[cfg(not(multi_tenant))] 42 const EXECUTE_MODE: u32 = libc::S_IXUSR; 43 44 const DEFAULT_DIR_MODE: u32 = READ_MODE | EXECUTE_MODE; 45 // b/264668376 some files in APK don't have unix permissions specified. Default to 400 46 // otherwise those files won't be readable even by the owner. 47 const DEFAULT_FILE_MODE: u32 = READ_MODE; 48 const EXECUTABLE_FILE_MODE: u32 = DEFAULT_FILE_MODE | EXECUTE_MODE; 49 50 /// `InodeData` represents an inode which has metadata about a file or a directory 51 #[derive(Debug)] 52 pub struct InodeData { 53 /// Size of the file that this inode represents. In case when the file is a directory, this 54 // is zero. 55 pub size: u64, 56 /// unix mode of this inode. It may not have `S_IFDIR` and `S_IFREG` in case the original zip 57 /// doesn't have the information in the external_attributes fields. To test if this inode 58 /// is for a regular file or a directory, use `is_dir`. 59 pub mode: u32, 60 data: InodeDataData, 61 } 62 63 type ZipIndex = usize; 64 65 /// `InodeDataData` is the actual data (or a means to access the data) of the file or the directory 66 /// that an inode is representing. In case of a directory, this data is the hash table of the 67 /// directory entries. In case of a file, this data is the index of the file in `ZipArchive` which 68 /// can be used to retrieve `ZipFile` that provides access to the content of the file. 69 #[derive(Debug)] 70 enum InodeDataData { 71 Directory(HashMap<CString, DirectoryEntry>), 72 File(ZipIndex), 73 } 74 75 #[derive(Debug, Clone)] 76 pub struct DirectoryEntry { 77 pub inode: Inode, 78 pub kind: InodeKind, 79 } 80 81 #[derive(Debug, Clone, PartialEq, Eq, Copy)] 82 pub enum InodeKind { 83 Directory, 84 File, 85 } 86 87 impl InodeData { is_dir(&self) -> bool88 pub fn is_dir(&self) -> bool { 89 matches!(&self.data, InodeDataData::Directory(_)) 90 } 91 get_directory(&self) -> Option<&HashMap<CString, DirectoryEntry>>92 pub fn get_directory(&self) -> Option<&HashMap<CString, DirectoryEntry>> { 93 match &self.data { 94 InodeDataData::Directory(hash) => Some(hash), 95 _ => None, 96 } 97 } 98 get_zip_index(&self) -> Option<ZipIndex>99 pub fn get_zip_index(&self) -> Option<ZipIndex> { 100 match &self.data { 101 InodeDataData::File(zip_index) => Some(*zip_index), 102 _ => None, 103 } 104 } 105 106 // Below methods are used to construct the inode table when initializing the filesystem. Once 107 // the initialization is done, these are not used because this is a read-only filesystem. 108 new_dir(mode: u32) -> InodeData109 fn new_dir(mode: u32) -> InodeData { 110 InodeData { mode, size: 0, data: InodeDataData::Directory(HashMap::new()) } 111 } 112 new_file(zip_index: ZipIndex, mode: u32, zip_file: &zip::read::ZipFile) -> InodeData113 fn new_file(zip_index: ZipIndex, mode: u32, zip_file: &zip::read::ZipFile) -> InodeData { 114 InodeData { mode, size: zip_file.size(), data: InodeDataData::File(zip_index) } 115 } 116 add_to_directory(&mut self, name: CString, entry: DirectoryEntry)117 fn add_to_directory(&mut self, name: CString, entry: DirectoryEntry) { 118 match &mut self.data { 119 InodeDataData::Directory(hashtable) => { 120 let existing = hashtable.insert(name, entry); 121 assert!(existing.is_none()); 122 } 123 _ => { 124 panic!("can't add a directory entry to a file inode"); 125 } 126 } 127 } 128 } 129 130 impl InodeTable { 131 /// Gets `InodeData` at a specific index. get(&self, inode: Inode) -> Option<&InodeData>132 pub fn get(&self, inode: Inode) -> Option<&InodeData> { 133 match inode { 134 INVALID => None, 135 _ => self.table.get(inode as usize), 136 } 137 } 138 get_mut(&mut self, inode: Inode) -> Option<&mut InodeData>139 fn get_mut(&mut self, inode: Inode) -> Option<&mut InodeData> { 140 match inode { 141 INVALID => None, 142 _ => self.table.get_mut(inode as usize), 143 } 144 } 145 put(&mut self, data: InodeData) -> Inode146 fn put(&mut self, data: InodeData) -> Inode { 147 let inode = self.table.len() as Inode; 148 self.table.push(data); 149 inode 150 } 151 152 /// Finds the inode number of a file named `name` in the `parent` inode. The `parent` inode 153 /// must exist and be a directory. find(&self, parent: Inode, name: &CStr) -> Option<Inode>154 fn find(&self, parent: Inode, name: &CStr) -> Option<Inode> { 155 let data = self.get(parent).unwrap(); 156 match data.get_directory().unwrap().get(name) { 157 Some(DirectoryEntry { inode, .. }) => Some(*inode), 158 _ => None, 159 } 160 } 161 162 // Adds the inode `data` to the inode table and also links it to the `parent` inode as a file 163 // named `name`. The `parent` inode must exist and be a directory. add(&mut self, parent: Inode, name: CString, data: InodeData) -> Inode164 fn add(&mut self, parent: Inode, name: CString, data: InodeData) -> Inode { 165 assert!(self.find(parent, &name).is_none()); 166 167 let kind = if data.is_dir() { InodeKind::Directory } else { InodeKind::File }; 168 // Add the inode to the table 169 let inode = self.put(data); 170 171 // ... and then register it to the directory of the parent inode 172 self.get_mut(parent).unwrap().add_to_directory(name, DirectoryEntry { inode, kind }); 173 inode 174 } 175 176 /// Constructs `InodeTable` from a zip archive `archive`. from_zip<R: io::Read + io::Seek>( archive: &mut zip::ZipArchive<R>, ) -> Result<InodeTable>177 pub fn from_zip<R: io::Read + io::Seek>( 178 archive: &mut zip::ZipArchive<R>, 179 ) -> Result<InodeTable> { 180 let mut table = InodeTable { table: Vec::new() }; 181 182 // Add the inodes for the invalid and the root directory 183 assert_eq!(INVALID, table.put(InodeData::new_dir(0))); 184 assert_eq!(ROOT, table.put(InodeData::new_dir(DEFAULT_DIR_MODE))); 185 186 // For each zip file in the archive, create an inode and add it to the table. If the file's 187 // parent directories don't have corresponding inodes in the table, handle them too. 188 for i in 0..archive.len() { 189 let file = archive.by_index(i)?; 190 let path = file 191 .enclosed_name() 192 .ok_or_else(|| anyhow!("{} is an invalid name", file.name()))?; 193 // TODO(jiyong): normalize this (e.g. a/b/c/../d -> a/b/d). We can't use 194 // fs::canonicalize as this is a non-existing path yet. 195 196 let mut parent = ROOT; 197 let mut iter = path.iter().peekable(); 198 199 let mut file_mode = DEFAULT_FILE_MODE; 200 if path.starts_with("bin/") { 201 // Allow files under bin to have execute permission, this enables payloads to bundle 202 // additional binaries that they might want to execute. 203 // An example of such binary is measure_io one used in the authfs performance tests. 204 // More context available at b/265261525 and b/270955654. 205 file_mode = EXECUTABLE_FILE_MODE; 206 } 207 208 while let Some(name) = iter.next() { 209 // TODO(jiyong): remove this check by canonicalizing `path` 210 if name == ".." { 211 bail!(".. is not allowed"); 212 } 213 214 let is_leaf = iter.peek().is_none(); 215 let is_file = file.is_file() && is_leaf; 216 217 // The happy path; the inode for `name` is already in the `parent` inode. Move on 218 // to the next path element. 219 let name = CString::new(name.as_bytes()).unwrap(); 220 if let Some(found) = table.find(parent, &name) { 221 parent = found; 222 // Update the mode if this is a directory leaf. 223 if !is_file && is_leaf { 224 let inode = table.get_mut(parent).unwrap(); 225 inode.mode = file.unix_mode().unwrap_or(DEFAULT_DIR_MODE); 226 } 227 continue; 228 } 229 230 // No inode found. Create a new inode and add it to the inode table. 231 // At the moment of writing this comment the apk file doesn't specify any 232 // permissions (apart from the ones on lib/), but it might change in the future. 233 // TODO(b/270955654): should we control the file permissions ourselves? 234 let inode = if is_file { 235 InodeData::new_file(i, file.unix_mode().unwrap_or(file_mode), &file) 236 } else if is_leaf { 237 InodeData::new_dir(file.unix_mode().unwrap_or(DEFAULT_DIR_MODE)) 238 } else { 239 InodeData::new_dir(DEFAULT_DIR_MODE) 240 }; 241 let new = table.add(parent, name, inode); 242 parent = new; 243 } 244 } 245 Ok(table) 246 } 247 } 248 249 #[cfg(test)] 250 mod tests { 251 use crate::inode::*; 252 use std::io::{Cursor, Write}; 253 use zip::write::FileOptions; 254 255 // Creates an in-memory zip buffer, adds some files to it, and converts it to InodeTable setup(add: fn(&mut zip::ZipWriter<&mut std::io::Cursor<Vec<u8>>>)) -> InodeTable256 fn setup(add: fn(&mut zip::ZipWriter<&mut std::io::Cursor<Vec<u8>>>)) -> InodeTable { 257 let mut buf: Cursor<Vec<u8>> = Cursor::new(Vec::new()); 258 let mut writer = zip::ZipWriter::new(&mut buf); 259 add(&mut writer); 260 assert!(writer.finish().is_ok()); 261 drop(writer); 262 263 let zip = zip::ZipArchive::new(buf); 264 assert!(zip.is_ok()); 265 let it = InodeTable::from_zip(&mut zip.unwrap()); 266 assert!(it.is_ok()); 267 it.unwrap() 268 } 269 check_dir(it: &InodeTable, parent: Inode, name: &str) -> Inode270 fn check_dir(it: &InodeTable, parent: Inode, name: &str) -> Inode { 271 let name = CString::new(name.as_bytes()).unwrap(); 272 let inode = it.find(parent, &name); 273 assert!(inode.is_some()); 274 let inode = inode.unwrap(); 275 let inode_data = it.get(inode); 276 assert!(inode_data.is_some()); 277 let inode_data = inode_data.unwrap(); 278 assert_eq!(0, inode_data.size); 279 assert!(inode_data.is_dir()); 280 inode 281 } 282 check_file<'a>(it: &'a InodeTable, parent: Inode, name: &str) -> &'a InodeData283 fn check_file<'a>(it: &'a InodeTable, parent: Inode, name: &str) -> &'a InodeData { 284 let name = CString::new(name.as_bytes()).unwrap(); 285 let inode = it.find(parent, &name); 286 assert!(inode.is_some()); 287 let inode = inode.unwrap(); 288 let inode_data = it.get(inode); 289 assert!(inode_data.is_some()); 290 let inode_data = inode_data.unwrap(); 291 assert!(!inode_data.is_dir()); 292 inode_data 293 } 294 295 #[test] empty_zip_has_two_inodes()296 fn empty_zip_has_two_inodes() { 297 let it = setup(|_| {}); 298 assert_eq!(2, it.table.len()); 299 assert!(it.get(INVALID).is_none()); 300 assert!(it.get(ROOT).is_some()); 301 } 302 303 #[test] one_file()304 fn one_file() { 305 let it = setup(|zip| { 306 zip.start_file("foo", FileOptions::default()).unwrap(); 307 zip.write_all(b"0123456789").unwrap(); 308 }); 309 let inode_data = check_file(&it, ROOT, "foo"); 310 assert_eq!(b"0123456789".len() as u64, inode_data.size); 311 } 312 313 #[test] one_dir()314 fn one_dir() { 315 let it = setup(|zip| { 316 zip.add_directory("foo", FileOptions::default()).unwrap(); 317 }); 318 let inode = check_dir(&it, ROOT, "foo"); 319 // The directory doesn't have any entries 320 assert_eq!(0, it.get(inode).unwrap().get_directory().unwrap().len()); 321 } 322 323 #[test] one_file_in_subdirs()324 fn one_file_in_subdirs() { 325 let it = setup(|zip| { 326 zip.start_file("a/b/c/d", FileOptions::default()).unwrap(); 327 zip.write_all(b"0123456789").unwrap(); 328 }); 329 330 assert_eq!(6, it.table.len()); 331 let a = check_dir(&it, ROOT, "a"); 332 let b = check_dir(&it, a, "b"); 333 let c = check_dir(&it, b, "c"); 334 let d = check_file(&it, c, "d"); 335 assert_eq!(10, d.size); 336 } 337 338 #[test] complex_hierarchy()339 fn complex_hierarchy() { 340 // root/ 341 // a/ 342 // b1/ 343 // b2/ 344 // c1 (file) 345 // c2/ 346 // d1 (file) 347 // d2 (file) 348 // d3 (file) 349 // x/ 350 // y1 (file) 351 // y2 (file) 352 // y3/ 353 // 354 // foo (file) 355 // bar (file) 356 let it = setup(|zip| { 357 let opt = FileOptions::default(); 358 zip.add_directory("a/b1", opt).unwrap(); 359 360 zip.start_file("a/b2/c1", opt).unwrap(); 361 362 zip.start_file("a/b2/c2/d1", opt).unwrap(); 363 zip.start_file("a/b2/c2/d2", opt).unwrap(); 364 zip.start_file("a/b2/c2/d3", opt).unwrap(); 365 366 zip.start_file("x/y1", opt).unwrap(); 367 zip.start_file("x/y2", opt).unwrap(); 368 zip.add_directory("x/y3", opt).unwrap(); 369 370 zip.start_file("foo", opt).unwrap(); 371 zip.start_file("bar", opt).unwrap(); 372 }); 373 374 assert_eq!(16, it.table.len()); // 8 files, 6 dirs, and 2 (for root and the invalid inode) 375 let a = check_dir(&it, ROOT, "a"); 376 let _b1 = check_dir(&it, a, "b1"); 377 let b2 = check_dir(&it, a, "b2"); 378 let _c1 = check_file(&it, b2, "c1"); 379 380 let c2 = check_dir(&it, b2, "c2"); 381 let _d1 = check_file(&it, c2, "d1"); 382 let _d2 = check_file(&it, c2, "d3"); 383 let _d3 = check_file(&it, c2, "d3"); 384 385 let x = check_dir(&it, ROOT, "x"); 386 let _y1 = check_file(&it, x, "y1"); 387 let _y2 = check_file(&it, x, "y2"); 388 let _y3 = check_dir(&it, x, "y3"); 389 390 let _foo = check_file(&it, ROOT, "foo"); 391 let _bar = check_file(&it, ROOT, "bar"); 392 } 393 394 #[test] file_size()395 fn file_size() { 396 let it = setup(|zip| { 397 let opt = FileOptions::default(); 398 zip.start_file("empty", opt).unwrap(); 399 400 zip.start_file("10bytes", opt).unwrap(); 401 zip.write_all(&[0; 10]).unwrap(); 402 403 zip.start_file("1234bytes", opt).unwrap(); 404 zip.write_all(&[0; 1234]).unwrap(); 405 406 zip.start_file("2^20bytes", opt).unwrap(); 407 zip.write_all(&[0; 2 << 20]).unwrap(); 408 }); 409 410 let f = check_file(&it, ROOT, "empty"); 411 assert_eq!(0, f.size); 412 413 let f = check_file(&it, ROOT, "10bytes"); 414 assert_eq!(10, f.size); 415 416 let f = check_file(&it, ROOT, "1234bytes"); 417 assert_eq!(1234, f.size); 418 419 let f = check_file(&it, ROOT, "2^20bytes"); 420 assert_eq!(2 << 20, f.size); 421 } 422 423 #[test] rejects_invalid_paths()424 fn rejects_invalid_paths() { 425 let invalid_paths = [ 426 "a/../../b", // escapes the root 427 "a/..", // escapes the root 428 "a/../../b/c", // escape the root 429 "a/b/../c", // doesn't escape the root, but not normalized 430 ]; 431 for path in invalid_paths.iter() { 432 let mut buf: Cursor<Vec<u8>> = Cursor::new(Vec::new()); 433 let mut writer = zip::ZipWriter::new(&mut buf); 434 writer.start_file(*path, FileOptions::default()).unwrap(); 435 assert!(writer.finish().is_ok()); 436 drop(writer); 437 438 let zip = zip::ZipArchive::new(buf); 439 assert!(zip.is_ok()); 440 let it = InodeTable::from_zip(&mut zip.unwrap()); 441 assert!(it.is_err()); 442 } 443 } 444 } 445