1ad452a1656343f3dff9415fa6ff5cba889d44669plougher/* 2ad452a1656343f3dff9415fa6ff5cba889d44669plougher * Squashfs - a compressed read only filesystem for Linux 3ad452a1656343f3dff9415fa6ff5cba889d44669plougher * 4ad452a1656343f3dff9415fa6ff5cba889d44669plougher * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008 5ad452a1656343f3dff9415fa6ff5cba889d44669plougher * Phillip Lougher <phillip@lougher.demon.co.uk> 6ad452a1656343f3dff9415fa6ff5cba889d44669plougher * 7ad452a1656343f3dff9415fa6ff5cba889d44669plougher * This program is free software; you can redistribute it and/or 8ad452a1656343f3dff9415fa6ff5cba889d44669plougher * modify it under the terms of the GNU General Public License 9ad452a1656343f3dff9415fa6ff5cba889d44669plougher * as published by the Free Software Foundation; either version 2, 10ad452a1656343f3dff9415fa6ff5cba889d44669plougher * or (at your option) any later version. 11ad452a1656343f3dff9415fa6ff5cba889d44669plougher * 12ad452a1656343f3dff9415fa6ff5cba889d44669plougher * This program is distributed in the hope that it will be useful, 13ad452a1656343f3dff9415fa6ff5cba889d44669plougher * but WITHOUT ANY WARRANTY; without even the implied warranty of 14ad452a1656343f3dff9415fa6ff5cba889d44669plougher * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15ad452a1656343f3dff9415fa6ff5cba889d44669plougher * GNU General Public License for more details. 16ad452a1656343f3dff9415fa6ff5cba889d44669plougher * 17ad452a1656343f3dff9415fa6ff5cba889d44669plougher * You should have received a copy of the GNU General Public License 18ad452a1656343f3dff9415fa6ff5cba889d44669plougher * along with this program; if not, write to the Free Software 19a3e28ecaf227d2c03ec6724dd718e3c5a12b74efplougher * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 20ad452a1656343f3dff9415fa6ff5cba889d44669plougher * 21ad452a1656343f3dff9415fa6ff5cba889d44669plougher * namei.c 22ad452a1656343f3dff9415fa6ff5cba889d44669plougher */ 23ad452a1656343f3dff9415fa6ff5cba889d44669plougher 2445536264329db40a7fd61b6784f8307e827b8a20plougher/* 2545536264329db40a7fd61b6784f8307e827b8a20plougher * This file implements code to do filename lookup in directories. 2645536264329db40a7fd61b6784f8307e827b8a20plougher * 2745536264329db40a7fd61b6784f8307e827b8a20plougher * Like inodes, directories are packed into compressed metadata blocks, stored 2845536264329db40a7fd61b6784f8307e827b8a20plougher * in a directory table. Directories are accessed using the start address of 2907e0310c61c277c87523afcf136e028524e24686plougher * the metablock containing the directory and the offset into the 3045536264329db40a7fd61b6784f8307e827b8a20plougher * decompressed block (<block, offset>). 3145536264329db40a7fd61b6784f8307e827b8a20plougher * 3245536264329db40a7fd61b6784f8307e827b8a20plougher * Directories are organised in a slightly complex way, and are not simply 3345536264329db40a7fd61b6784f8307e827b8a20plougher * a list of file names. The organisation takes advantage of the 3445536264329db40a7fd61b6784f8307e827b8a20plougher * fact that (in most cases) the inodes of the files will be in the same 3545536264329db40a7fd61b6784f8307e827b8a20plougher * compressed metadata block, and therefore, can share the start block. 3645536264329db40a7fd61b6784f8307e827b8a20plougher * Directories are therefore organised in a two level list, a directory 3745536264329db40a7fd61b6784f8307e827b8a20plougher * header containing the shared start block value, and a sequence of directory 3845536264329db40a7fd61b6784f8307e827b8a20plougher * entries, each of which share the shared start block. A new directory header 3945536264329db40a7fd61b6784f8307e827b8a20plougher * is written once/if the inode start block changes. The directory 4045536264329db40a7fd61b6784f8307e827b8a20plougher * header/directory entry list is repeated as many times as necessary. 4145536264329db40a7fd61b6784f8307e827b8a20plougher * 4245536264329db40a7fd61b6784f8307e827b8a20plougher * Directories are sorted, and can contain a directory index to speed up 4345536264329db40a7fd61b6784f8307e827b8a20plougher * file lookup. Directory indexes store one entry per metablock, each entry 4445536264329db40a7fd61b6784f8307e827b8a20plougher * storing the index/filename mapping to the first directory header 4545536264329db40a7fd61b6784f8307e827b8a20plougher * in each metadata block. Directories are sorted in alphabetical order, 4645536264329db40a7fd61b6784f8307e827b8a20plougher * and at lookup the index is scanned linearly looking for the first filename 4745536264329db40a7fd61b6784f8307e827b8a20plougher * alphabetically larger than the filename being looked up. At this point the 4845536264329db40a7fd61b6784f8307e827b8a20plougher * location of the metadata block the filename is in has been found. 4945536264329db40a7fd61b6784f8307e827b8a20plougher * The general idea of the index is ensure only one metadata block needs to be 5045536264329db40a7fd61b6784f8307e827b8a20plougher * decompressed to do a lookup irrespective of the length of the directory. 5145536264329db40a7fd61b6784f8307e827b8a20plougher * This scheme has the advantage that it doesn't require extra memory overhead 5245536264329db40a7fd61b6784f8307e827b8a20plougher * and doesn't require much extra storage on disk. 5345536264329db40a7fd61b6784f8307e827b8a20plougher */ 5445536264329db40a7fd61b6784f8307e827b8a20plougher 55ad452a1656343f3dff9415fa6ff5cba889d44669plougher#include <linux/fs.h> 56618f0d4fd2bc599903287b625ed940fec1908f15plougher#include <linux/vfs.h> 57618f0d4fd2bc599903287b625ed940fec1908f15plougher#include <linux/slab.h> 58618f0d4fd2bc599903287b625ed940fec1908f15plougher#include <linux/string.h> 59618f0d4fd2bc599903287b625ed940fec1908f15plougher#include <linux/dcache.h> 60618f0d4fd2bc599903287b625ed940fec1908f15plougher#include <linux/zlib.h> 61ad452a1656343f3dff9415fa6ff5cba889d44669plougher 62a70c1cc4b995d559bcbdf2d3dda88c5bd1292c32plougher#include "squashfs_fs.h" 63a70c1cc4b995d559bcbdf2d3dda88c5bd1292c32plougher#include "squashfs_fs_sb.h" 64a70c1cc4b995d559bcbdf2d3dda88c5bd1292c32plougher#include "squashfs_fs_i.h" 65ad452a1656343f3dff9415fa6ff5cba889d44669plougher#include "squashfs.h" 66ad452a1656343f3dff9415fa6ff5cba889d44669plougher 6745536264329db40a7fd61b6784f8307e827b8a20plougher/* 6845536264329db40a7fd61b6784f8307e827b8a20plougher * Lookup name in the directory index, returning the location of the metadata 6948a99fd96c66820dfd23418995c2f01e154d15d4plougher * block containing it, and the directory index this represents. 7042d43d8a5d236bdae90e04b241ef5db631904ebfplougher * 7142d43d8a5d236bdae90e04b241ef5db631904ebfplougher * If we get an error reading the index then return the part of the index 7242d43d8a5d236bdae90e04b241ef5db631904ebfplougher * (if any) we have managed to read - the index isn't essential, just 7342d43d8a5d236bdae90e04b241ef5db631904ebfplougher * quicker. 7445536264329db40a7fd61b6784f8307e827b8a20plougher */ 755809be53e4a797efae8bb2e206f94889f3f81065plougherstatic int get_dir_index_using_name(struct super_block *sb, 76f006b96e65d7092838983913afbd69fd8199d793plougher u64 *next_block, int *next_offset, u64 index_start, 77f006b96e65d7092838983913afbd69fd8199d793plougher int index_offset, int i_count, const char *name, 78f006b96e65d7092838983913afbd69fd8199d793plougher int len) 79ad452a1656343f3dff9415fa6ff5cba889d44669plougher{ 805809be53e4a797efae8bb2e206f94889f3f81065plougher struct squashfs_sb_info *msblk = sb->s_fs_info; 8142d43d8a5d236bdae90e04b241ef5db631904ebfplougher int i, size, length = 0, err; 82ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct squashfs_dir_index *index; 83ad452a1656343f3dff9415fa6ff5cba889d44669plougher char *str; 84ad452a1656343f3dff9415fa6ff5cba889d44669plougher 85ad452a1656343f3dff9415fa6ff5cba889d44669plougher TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count); 86ad452a1656343f3dff9415fa6ff5cba889d44669plougher 876c11db91fcd3d5f18989424d2278b79f7448972fplougher index = kmalloc(sizeof(*index) + SQUASHFS_NAME_LEN * 2 + 2, GFP_KERNEL); 886c11db91fcd3d5f18989424d2278b79f7448972fplougher if (index == NULL) { 89ad452a1656343f3dff9415fa6ff5cba889d44669plougher ERROR("Failed to allocate squashfs_dir_index\n"); 9045536264329db40a7fd61b6784f8307e827b8a20plougher goto out; 91ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 92ad452a1656343f3dff9415fa6ff5cba889d44669plougher 936c11db91fcd3d5f18989424d2278b79f7448972fplougher str = &index->name[SQUASHFS_NAME_LEN + 1]; 942d023a80f4dae8e06cf7e4b74f7870c524db8943plougher strncpy(str, name, len); 952d023a80f4dae8e06cf7e4b74f7870c524db8943plougher str[len] = '\0'; 96ad452a1656343f3dff9415fa6ff5cba889d44669plougher 97ad452a1656343f3dff9415fa6ff5cba889d44669plougher for (i = 0; i < i_count; i++) { 985809be53e4a797efae8bb2e206f94889f3f81065plougher err = squashfs_read_metadata(sb, index, &index_start, 9942d43d8a5d236bdae90e04b241ef5db631904ebfplougher &index_offset, sizeof(*index)); 10042d43d8a5d236bdae90e04b241ef5db631904ebfplougher if (err < 0) 10142d43d8a5d236bdae90e04b241ef5db631904ebfplougher break; 10242d43d8a5d236bdae90e04b241ef5db631904ebfplougher 1032d023a80f4dae8e06cf7e4b74f7870c524db8943plougher 1042d023a80f4dae8e06cf7e4b74f7870c524db8943plougher size = le32_to_cpu(index->size) + 1; 105ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1065809be53e4a797efae8bb2e206f94889f3f81065plougher err = squashfs_read_metadata(sb, index->name, &index_start, 107bfffe327332facc323af287277f68fe905ce7a8aplougher &index_offset, size); 10842d43d8a5d236bdae90e04b241ef5db631904ebfplougher if (err < 0) 10942d43d8a5d236bdae90e04b241ef5db631904ebfplougher break; 110ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1112d023a80f4dae8e06cf7e4b74f7870c524db8943plougher index->name[size] = '\0'; 112ad452a1656343f3dff9415fa6ff5cba889d44669plougher 113ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (strcmp(index->name, str) > 0) 114ad452a1656343f3dff9415fa6ff5cba889d44669plougher break; 115ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1162d023a80f4dae8e06cf7e4b74f7870c524db8943plougher length = le32_to_cpu(index->index); 1172d023a80f4dae8e06cf7e4b74f7870c524db8943plougher *next_block = le32_to_cpu(index->start_block) + 1181aef9e4f12365714fd95ac9a7a059ea4c7d6d846plougher msblk->directory_table; 119ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 120ad452a1656343f3dff9415fa6ff5cba889d44669plougher 121ad452a1656343f3dff9415fa6ff5cba889d44669plougher *next_offset = (length + *next_offset) % SQUASHFS_METADATA_SIZE; 1226c11db91fcd3d5f18989424d2278b79f7448972fplougher kfree(index); 123ad452a1656343f3dff9415fa6ff5cba889d44669plougher 12445536264329db40a7fd61b6784f8307e827b8a20plougherout: 12545536264329db40a7fd61b6784f8307e827b8a20plougher /* 12645536264329db40a7fd61b6784f8307e827b8a20plougher * Return index (f_pos) of the looked up metadata block. Translate 12745536264329db40a7fd61b6784f8307e827b8a20plougher * from internal f_pos to external f_pos which is offset by 3 because 12845536264329db40a7fd61b6784f8307e827b8a20plougher * we invent "." and ".." entries which are not actually stored in the 12948a99fd96c66820dfd23418995c2f01e154d15d4plougher * directory. 13045536264329db40a7fd61b6784f8307e827b8a20plougher */ 131ad452a1656343f3dff9415fa6ff5cba889d44669plougher return length + 3; 132ad452a1656343f3dff9415fa6ff5cba889d44669plougher} 133ad452a1656343f3dff9415fa6ff5cba889d44669plougher 13486afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher 135d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougherstatic struct dentry *squashfs_lookup(struct inode *dir, struct dentry *dentry, 136d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher struct nameidata *nd) 137ad452a1656343f3dff9415fa6ff5cba889d44669plougher{ 138ad452a1656343f3dff9415fa6ff5cba889d44669plougher const unsigned char *name = dentry->d_name.name; 139ad452a1656343f3dff9415fa6ff5cba889d44669plougher int len = dentry->d_name.len; 140ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct inode *inode = NULL; 141d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher struct squashfs_sb_info *msblk = dir->i_sb->s_fs_info; 142ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct squashfs_dir_header dirh; 143ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct squashfs_dir_entry *dire; 144f006b96e65d7092838983913afbd69fd8199d793plougher u64 block = squashfs_i(dir)->start + msblk->directory_table; 1455921b8d869f8d9a5a15a520eee1cfae06b1d9688plougher int offset = squashfs_i(dir)->offset; 14617f4c6f13075c74c7a4f3f3388c822b9f516b892plougher int err, length = 0, dir_count, size; 147ad452a1656343f3dff9415fa6ff5cba889d44669plougher 148d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher TRACE("Entered squashfs_lookup [%llx:%x]\n", block, offset); 149ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1503405d617eb69745519a80952f1fe3e8ff0fa0541plougher dire = kmalloc(sizeof(*dire) + SQUASHFS_NAME_LEN + 1, GFP_KERNEL); 151ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (dire == NULL) { 152ad452a1656343f3dff9415fa6ff5cba889d44669plougher ERROR("Failed to allocate squashfs_dir_entry\n"); 153171e3df917d22af3d8e5caff56c3665f626d96f4plougher return ERR_PTR(-ENOMEM); 154ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 155ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1561931723ba8788fc58882550c16d367375fd245e5plougher if (len > SQUASHFS_NAME_LEN) { 1571931723ba8788fc58882550c16d367375fd245e5plougher err = -ENAMETOOLONG; 1581931723ba8788fc58882550c16d367375fd245e5plougher goto failed; 1591931723ba8788fc58882550c16d367375fd245e5plougher } 160ad452a1656343f3dff9415fa6ff5cba889d44669plougher 161d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher length = get_dir_index_using_name(dir->i_sb, &block, &offset, 1625921b8d869f8d9a5a15a520eee1cfae06b1d9688plougher squashfs_i(dir)->dir_idx_start, 1635921b8d869f8d9a5a15a520eee1cfae06b1d9688plougher squashfs_i(dir)->dir_idx_offset, 1645921b8d869f8d9a5a15a520eee1cfae06b1d9688plougher squashfs_i(dir)->dir_idx_cnt, name, len); 165ad452a1656343f3dff9415fa6ff5cba889d44669plougher 166d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher while (length < i_size_read(dir)) { 16745536264329db40a7fd61b6784f8307e827b8a20plougher /* 16807e0310c61c277c87523afcf136e028524e24686plougher * Read directory header. 16907e0310c61c277c87523afcf136e028524e24686plougher */ 170d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher err = squashfs_read_metadata(dir->i_sb, &dirh, &block, 171d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher &offset, sizeof(dirh)); 17242d43d8a5d236bdae90e04b241ef5db631904ebfplougher if (err < 0) 17317f4c6f13075c74c7a4f3f3388c822b9f516b892plougher goto read_failure; 174ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1752d023a80f4dae8e06cf7e4b74f7870c524db8943plougher length += sizeof(dirh); 176ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1772d023a80f4dae8e06cf7e4b74f7870c524db8943plougher dir_count = le32_to_cpu(dirh.count) + 1; 178ad452a1656343f3dff9415fa6ff5cba889d44669plougher while (dir_count--) { 17945536264329db40a7fd61b6784f8307e827b8a20plougher /* 18007e0310c61c277c87523afcf136e028524e24686plougher * Read directory entry. 18107e0310c61c277c87523afcf136e028524e24686plougher */ 182d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher err = squashfs_read_metadata(dir->i_sb, dire, &block, 183d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher &offset, sizeof(*dire)); 18442d43d8a5d236bdae90e04b241ef5db631904ebfplougher if (err < 0) 18517f4c6f13075c74c7a4f3f3388c822b9f516b892plougher goto read_failure; 1862d023a80f4dae8e06cf7e4b74f7870c524db8943plougher 1872d023a80f4dae8e06cf7e4b74f7870c524db8943plougher size = le16_to_cpu(dire->size) + 1; 188ad452a1656343f3dff9415fa6ff5cba889d44669plougher 189d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher err = squashfs_read_metadata(dir->i_sb, dire->name, 190d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher &block, &offset, size); 19142d43d8a5d236bdae90e04b241ef5db631904ebfplougher if (err < 0) 19217f4c6f13075c74c7a4f3f3388c822b9f516b892plougher goto read_failure; 193ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1942d023a80f4dae8e06cf7e4b74f7870c524db8943plougher length += sizeof(*dire) + size; 195ad452a1656343f3dff9415fa6ff5cba889d44669plougher 196ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (name[0] < dire->name[0]) 197ad452a1656343f3dff9415fa6ff5cba889d44669plougher goto exit_lookup; 198ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1992d023a80f4dae8e06cf7e4b74f7870c524db8943plougher if (len == size && !strncmp(name, dire->name, len)) { 200d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher unsigned int blk, off, ino_num; 201d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher long long ino; 202d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher blk = le32_to_cpu(dirh.start_block); 203d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher off = le16_to_cpu(dire->offset); 204d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher ino_num = le32_to_cpu(dirh.inode_number) + 20586afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher (short) le16_to_cpu(dire->inode_number); 206d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher ino = SQUASHFS_MKINODE(blk, off); 20786afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher 20886afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher TRACE("calling squashfs_iget for directory " 20986afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher "entry %s, inode %x:%x, %d\n", name, 210d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher blk, off, ino_num); 21186afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher 212d8ac9728f1e18adf5d6f06cd2de7ded12c9f98d0plougher inode = squashfs_iget(dir->i_sb, ino, ino_num); 2131931723ba8788fc58882550c16d367375fd245e5plougher if (IS_ERR(inode)) { 2141931723ba8788fc58882550c16d367375fd245e5plougher err = PTR_ERR(inode); 2151931723ba8788fc58882550c16d367375fd245e5plougher goto failed; 2161931723ba8788fc58882550c16d367375fd245e5plougher } 217ad452a1656343f3dff9415fa6ff5cba889d44669plougher 218ad452a1656343f3dff9415fa6ff5cba889d44669plougher goto exit_lookup; 219ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 220ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 221ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 222ad452a1656343f3dff9415fa6ff5cba889d44669plougher 223ad452a1656343f3dff9415fa6ff5cba889d44669plougherexit_lookup: 224ad452a1656343f3dff9415fa6ff5cba889d44669plougher kfree(dire); 225ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (inode) 226ad452a1656343f3dff9415fa6ff5cba889d44669plougher return d_splice_alias(inode, dentry); 227ad452a1656343f3dff9415fa6ff5cba889d44669plougher d_add(dentry, inode); 228ad452a1656343f3dff9415fa6ff5cba889d44669plougher return ERR_PTR(0); 229ad452a1656343f3dff9415fa6ff5cba889d44669plougher 23017f4c6f13075c74c7a4f3f3388c822b9f516b892plougherread_failure: 2310b77ad632ce83f94aa24e028e1ce98ceec518944plougher ERROR("Unable to read directory block [%llx:%x]\n", 2325921b8d869f8d9a5a15a520eee1cfae06b1d9688plougher squashfs_i(dir)->start + msblk->directory_table, 2335921b8d869f8d9a5a15a520eee1cfae06b1d9688plougher squashfs_i(dir)->offset); 2341931723ba8788fc58882550c16d367375fd245e5plougherfailed: 2351931723ba8788fc58882550c16d367375fd245e5plougher kfree(dire); 23617f4c6f13075c74c7a4f3f3388c822b9f516b892plougher return ERR_PTR(err); 237ad452a1656343f3dff9415fa6ff5cba889d44669plougher} 238ad452a1656343f3dff9415fa6ff5cba889d44669plougher 239ad452a1656343f3dff9415fa6ff5cba889d44669plougher 240ad452a1656343f3dff9415fa6ff5cba889d44669plougherconst struct inode_operations squashfs_dir_inode_ops = { 241ad452a1656343f3dff9415fa6ff5cba889d44669plougher .lookup = squashfs_lookup 242ad452a1656343f3dff9415fa6ff5cba889d44669plougher}; 243