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