namei.c revision 45536264329db40a7fd61b6784f8307e827b8a20
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 19ad452a1656343f3dff9415fa6ff5cba889d44669plougher * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 2945536264329db40a7fd61b6784f8307e827b8a20plougher * 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> 61618f0d4fd2bc599903287b625ed940fec1908f15plougher#include <linux/squashfs_fs.h> 62ad452a1656343f3dff9415fa6ff5cba889d44669plougher#include <linux/squashfs_fs_sb.h> 63ad452a1656343f3dff9415fa6ff5cba889d44669plougher#include <linux/squashfs_fs_i.h> 64ad452a1656343f3dff9415fa6ff5cba889d44669plougher 65ad452a1656343f3dff9415fa6ff5cba889d44669plougher#include "squashfs.h" 66ad452a1656343f3dff9415fa6ff5cba889d44669plougher 6745536264329db40a7fd61b6784f8307e827b8a20plougher/* 6845536264329db40a7fd61b6784f8307e827b8a20plougher * Lookup name in the directory index, returning the location of the metadata 6945536264329db40a7fd61b6784f8307e827b8a20plougher * block containing the filename, and the directory index this represents. 7045536264329db40a7fd61b6784f8307e827b8a20plougher */ 71ad452a1656343f3dff9415fa6ff5cba889d44669plougherstatic int get_dir_index_using_name(struct super_block *s, 7286afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher long long *next_block, unsigned int *next_offset, 7386afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher long long index_start, unsigned int index_offset, 7486afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher int i_count, const char *name, int len) 75ad452a1656343f3dff9415fa6ff5cba889d44669plougher{ 76ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct squashfs_sb_info *msblk = s->s_fs_info; 772d023a80f4dae8e06cf7e4b74f7870c524db8943plougher int i, size, length = 0; 78ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct squashfs_dir_index *index; 79ad452a1656343f3dff9415fa6ff5cba889d44669plougher char *str; 80ad452a1656343f3dff9415fa6ff5cba889d44669plougher 81ad452a1656343f3dff9415fa6ff5cba889d44669plougher TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count); 82ad452a1656343f3dff9415fa6ff5cba889d44669plougher 833405d617eb69745519a80952f1fe3e8ff0fa0541plougher str = kmalloc(sizeof(*index) + (SQUASHFS_NAME_LEN + 1) * 2, GFP_KERNEL); 84ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (str == NULL) { 85ad452a1656343f3dff9415fa6ff5cba889d44669plougher ERROR("Failed to allocate squashfs_dir_index\n"); 8645536264329db40a7fd61b6784f8307e827b8a20plougher goto out; 87ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 88ad452a1656343f3dff9415fa6ff5cba889d44669plougher 89ad452a1656343f3dff9415fa6ff5cba889d44669plougher index = (struct squashfs_dir_index *) (str + SQUASHFS_NAME_LEN + 1); 902d023a80f4dae8e06cf7e4b74f7870c524db8943plougher strncpy(str, name, len); 912d023a80f4dae8e06cf7e4b74f7870c524db8943plougher str[len] = '\0'; 92ad452a1656343f3dff9415fa6ff5cba889d44669plougher 93ad452a1656343f3dff9415fa6ff5cba889d44669plougher for (i = 0; i < i_count; i++) { 948d3339a3f9bc64056966314685c424b1c2a55d0bplougher squashfs_read_metadata(s, index, index_start, index_offset, 953405d617eb69745519a80952f1fe3e8ff0fa0541plougher sizeof(*index), &index_start, 963405d617eb69745519a80952f1fe3e8ff0fa0541plougher &index_offset); 972d023a80f4dae8e06cf7e4b74f7870c524db8943plougher 982d023a80f4dae8e06cf7e4b74f7870c524db8943plougher size = le32_to_cpu(index->size) + 1; 99ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1008d3339a3f9bc64056966314685c424b1c2a55d0bplougher squashfs_read_metadata(s, index->name, index_start, 10186afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher index_offset, size, &index_start, 10286afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher &index_offset); 103ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1042d023a80f4dae8e06cf7e4b74f7870c524db8943plougher index->name[size] = '\0'; 105ad452a1656343f3dff9415fa6ff5cba889d44669plougher 106ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (strcmp(index->name, str) > 0) 107ad452a1656343f3dff9415fa6ff5cba889d44669plougher break; 108ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1092d023a80f4dae8e06cf7e4b74f7870c524db8943plougher length = le32_to_cpu(index->index); 1102d023a80f4dae8e06cf7e4b74f7870c524db8943plougher *next_block = le32_to_cpu(index->start_block) + 11186afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher msblk->directory_table_start; 112ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 113ad452a1656343f3dff9415fa6ff5cba889d44669plougher 114ad452a1656343f3dff9415fa6ff5cba889d44669plougher *next_offset = (length + *next_offset) % SQUASHFS_METADATA_SIZE; 115ad452a1656343f3dff9415fa6ff5cba889d44669plougher kfree(str); 116ad452a1656343f3dff9415fa6ff5cba889d44669plougher 11745536264329db40a7fd61b6784f8307e827b8a20plougherout: 11845536264329db40a7fd61b6784f8307e827b8a20plougher /* 11945536264329db40a7fd61b6784f8307e827b8a20plougher * Return index (f_pos) of the looked up metadata block. Translate 12045536264329db40a7fd61b6784f8307e827b8a20plougher * from internal f_pos to external f_pos which is offset by 3 because 12145536264329db40a7fd61b6784f8307e827b8a20plougher * we invent "." and ".." entries which are not actually stored in the 12245536264329db40a7fd61b6784f8307e827b8a20plougher * directory on disk. 12345536264329db40a7fd61b6784f8307e827b8a20plougher */ 124ad452a1656343f3dff9415fa6ff5cba889d44669plougher return length + 3; 125ad452a1656343f3dff9415fa6ff5cba889d44669plougher} 126ad452a1656343f3dff9415fa6ff5cba889d44669plougher 12786afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher 128ad452a1656343f3dff9415fa6ff5cba889d44669plougherstatic struct dentry *squashfs_lookup(struct inode *i, struct dentry *dentry, 129ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct nameidata *nd) 130ad452a1656343f3dff9415fa6ff5cba889d44669plougher{ 131ad452a1656343f3dff9415fa6ff5cba889d44669plougher const unsigned char *name = dentry->d_name.name; 132ad452a1656343f3dff9415fa6ff5cba889d44669plougher int len = dentry->d_name.len; 133ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct inode *inode = NULL; 134ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct squashfs_sb_info *msblk = i->i_sb->s_fs_info; 135ad452a1656343f3dff9415fa6ff5cba889d44669plougher long long next_block = SQUASHFS_I(i)->start_block + 13612c75c4de956f45dc7348d3ba31bf1568c79542aplougher msblk->directory_table_start; 1372d023a80f4dae8e06cf7e4b74f7870c524db8943plougher int next_offset = SQUASHFS_I(i)->offset, length = 0, dir_count, size; 138ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct squashfs_dir_header dirh; 139ad452a1656343f3dff9415fa6ff5cba889d44669plougher struct squashfs_dir_entry *dire; 14086afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher unsigned int start_block, offset, ino_number; 14186afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher long long ino; 142ad452a1656343f3dff9415fa6ff5cba889d44669plougher 143ad452a1656343f3dff9415fa6ff5cba889d44669plougher TRACE("Entered squashfs_lookup [%llx:%x]\n", next_block, next_offset); 144ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1453405d617eb69745519a80952f1fe3e8ff0fa0541plougher dire = kmalloc(sizeof(*dire) + SQUASHFS_NAME_LEN + 1, GFP_KERNEL); 146ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (dire == NULL) { 147ad452a1656343f3dff9415fa6ff5cba889d44669plougher ERROR("Failed to allocate squashfs_dir_entry\n"); 148ad452a1656343f3dff9415fa6ff5cba889d44669plougher goto exit_lookup; 149ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 150ad452a1656343f3dff9415fa6ff5cba889d44669plougher 151ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (len > SQUASHFS_NAME_LEN) 152ad452a1656343f3dff9415fa6ff5cba889d44669plougher goto exit_lookup; 153ad452a1656343f3dff9415fa6ff5cba889d44669plougher 154ad452a1656343f3dff9415fa6ff5cba889d44669plougher length = get_dir_index_using_name(i->i_sb, &next_block, &next_offset, 155ead3026ed1e0258177b4a3cb2e3c800a78084e79plougher SQUASHFS_I(i)->dir_index_start, 156ead3026ed1e0258177b4a3cb2e3c800a78084e79plougher SQUASHFS_I(i)->dir_index_offset, 157ead3026ed1e0258177b4a3cb2e3c800a78084e79plougher SQUASHFS_I(i)->dir_index_count, name, len); 158ad452a1656343f3dff9415fa6ff5cba889d44669plougher 159ad452a1656343f3dff9415fa6ff5cba889d44669plougher while (length < i_size_read(i)) { 16045536264329db40a7fd61b6784f8307e827b8a20plougher /* 16145536264329db40a7fd61b6784f8307e827b8a20plougher * Read directory header. 16245536264329db40a7fd61b6784f8307e827b8a20plougher */ 1638d3339a3f9bc64056966314685c424b1c2a55d0bplougher if (!squashfs_read_metadata(i->i_sb, &dirh, next_block, 16486afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher next_offset, sizeof(dirh), &next_block, 16586afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher &next_offset)) 1662d023a80f4dae8e06cf7e4b74f7870c524db8943plougher goto failed_read; 167ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1682d023a80f4dae8e06cf7e4b74f7870c524db8943plougher length += sizeof(dirh); 169ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1702d023a80f4dae8e06cf7e4b74f7870c524db8943plougher dir_count = le32_to_cpu(dirh.count) + 1; 171ad452a1656343f3dff9415fa6ff5cba889d44669plougher while (dir_count--) { 17245536264329db40a7fd61b6784f8307e827b8a20plougher /* 17345536264329db40a7fd61b6784f8307e827b8a20plougher * Read directory entry. 17445536264329db40a7fd61b6784f8307e827b8a20plougher */ 1758d3339a3f9bc64056966314685c424b1c2a55d0bplougher if (!squashfs_read_metadata(i->i_sb, dire, 17686afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher next_block, next_offset, sizeof(*dire), 17786afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher &next_block, &next_offset)) 1782d023a80f4dae8e06cf7e4b74f7870c524db8943plougher goto failed_read; 1792d023a80f4dae8e06cf7e4b74f7870c524db8943plougher 1802d023a80f4dae8e06cf7e4b74f7870c524db8943plougher size = le16_to_cpu(dire->size) + 1; 181ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1828d3339a3f9bc64056966314685c424b1c2a55d0bplougher if (!squashfs_read_metadata(i->i_sb, dire->name, 18386afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher next_block, next_offset, size, 18486afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher &next_block, &next_offset)) 185ad452a1656343f3dff9415fa6ff5cba889d44669plougher goto failed_read; 186ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1872d023a80f4dae8e06cf7e4b74f7870c524db8943plougher length += sizeof(*dire) + size; 188ad452a1656343f3dff9415fa6ff5cba889d44669plougher 189ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (name[0] < dire->name[0]) 190ad452a1656343f3dff9415fa6ff5cba889d44669plougher goto exit_lookup; 191ad452a1656343f3dff9415fa6ff5cba889d44669plougher 1922d023a80f4dae8e06cf7e4b74f7870c524db8943plougher if (len == size && !strncmp(name, dire->name, len)) { 19386afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher start_block = le32_to_cpu(dirh.start_block); 194f55ef27468d7d3d1eaeac9f7128ce917f6f856e8plougher offset = le16_to_cpu(dire->offset); 19586afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher ino_number = le32_to_cpu(dirh.inode_number) + 19686afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher (short) le16_to_cpu(dire->inode_number); 19786afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher ino = SQUASHFS_MKINODE(start_block, offset); 19886afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher 19986afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher TRACE("calling squashfs_iget for directory " 20086afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher "entry %s, inode %x:%x, %d\n", name, 20186afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher start_block, offset, ino_number); 20286afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher 20386afe43736e3acf5bb1ebc0ca132c9eaa187b383plougher inode = squashfs_iget(i->i_sb, ino, ino_number); 204ad452a1656343f3dff9415fa6ff5cba889d44669plougher 205ad452a1656343f3dff9415fa6ff5cba889d44669plougher goto exit_lookup; 206ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 207ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 208ad452a1656343f3dff9415fa6ff5cba889d44669plougher } 209ad452a1656343f3dff9415fa6ff5cba889d44669plougher 210ad452a1656343f3dff9415fa6ff5cba889d44669plougherexit_lookup: 211ad452a1656343f3dff9415fa6ff5cba889d44669plougher kfree(dire); 212ad452a1656343f3dff9415fa6ff5cba889d44669plougher if (inode) 213ad452a1656343f3dff9415fa6ff5cba889d44669plougher return d_splice_alias(inode, dentry); 214ad452a1656343f3dff9415fa6ff5cba889d44669plougher d_add(dentry, inode); 215ad452a1656343f3dff9415fa6ff5cba889d44669plougher return ERR_PTR(0); 216ad452a1656343f3dff9415fa6ff5cba889d44669plougher 217ad452a1656343f3dff9415fa6ff5cba889d44669plougherfailed_read: 218ad452a1656343f3dff9415fa6ff5cba889d44669plougher ERROR("Unable to read directory block [%llx:%x]\n", next_block, 219ad452a1656343f3dff9415fa6ff5cba889d44669plougher next_offset); 220ad452a1656343f3dff9415fa6ff5cba889d44669plougher goto exit_lookup; 221ad452a1656343f3dff9415fa6ff5cba889d44669plougher} 222ad452a1656343f3dff9415fa6ff5cba889d44669plougher 223ad452a1656343f3dff9415fa6ff5cba889d44669plougher 224ad452a1656343f3dff9415fa6ff5cba889d44669plougherconst struct inode_operations squashfs_dir_inode_ops = { 225ad452a1656343f3dff9415fa6ff5cba889d44669plougher .lookup = squashfs_lookup 226ad452a1656343f3dff9415fa6ff5cba889d44669plougher}; 227