1/* Modified by Broadcom Corp. Portions Copyright (c) Broadcom Corp, 2012. */ 2/* 3 * Squashfs - a compressed read only filesystem for Linux 4 * 5 * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008 6 * Phillip Lougher <phillip@lougher.demon.co.uk> 7 * 8 * This program is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU General Public License 10 * as published by the Free Software Foundation; either version 2, 11 * or (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with this program; if not, write to the Free Software 20 * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 21 * 22 * namei.c 23 */ 24 25/* 26 * This file implements code to do filename lookup in directories. 27 * 28 * Like inodes, directories are packed into compressed metadata blocks, stored 29 * in a directory table. Directories are accessed using the start address of 30 * the metablock containing the directory and the offset into the 31 * decompressed block (<block, offset>). 32 * 33 * Directories are organised in a slightly complex way, and are not simply 34 * a list of file names. The organisation takes advantage of the 35 * fact that (in most cases) the inodes of the files will be in the same 36 * compressed metadata block, and therefore, can share the start block. 37 * Directories are therefore organised in a two level list, a directory 38 * header containing the shared start block value, and a sequence of directory 39 * entries, each of which share the shared start block. A new directory header 40 * is written once/if the inode start block changes. The directory 41 * header/directory entry list is repeated as many times as necessary. 42 * 43 * Directories are sorted, and can contain a directory index to speed up 44 * file lookup. Directory indexes store one entry per metablock, each entry 45 * storing the index/filename mapping to the first directory header 46 * in each metadata block. Directories are sorted in alphabetical order, 47 * and at lookup the index is scanned linearly looking for the first filename 48 * alphabetically larger than the filename being looked up. At this point the 49 * location of the metadata block the filename is in has been found. 50 * The general idea of the index is ensure only one metadata block needs to be 51 * decompressed to do a lookup irrespective of the length of the directory. 52 * This scheme has the advantage that it doesn't require extra memory overhead 53 * and doesn't require much extra storage on disk. 54 */ 55 56#include <linux/fs.h> 57#include <linux/vfs.h> 58#include <linux/slab.h> 59#include <linux/string.h> 60#include <linux/dcache.h> 61#include <linux/xattr.h> 62 63#include "squashfs_fs.h" 64#include "squashfs_fs_sb.h" 65#include "squashfs_fs_i.h" 66#include "squashfs.h" 67#include "xattr.h" 68 69/* 70 * Lookup name in the directory index, returning the location of the metadata 71 * block containing it, and the directory index this represents. 72 * 73 * If we get an error reading the index then return the part of the index 74 * (if any) we have managed to read - the index isn't essential, just 75 * quicker. 76 */ 77static int get_dir_index_using_name(struct super_block *sb, 78 u64 *next_block, int *next_offset, u64 index_start, 79 int index_offset, int i_count, const char *name, 80 int len) 81{ 82 struct squashfs_sb_info *msblk = sb->s_fs_info; 83 int i, size, length = 0, err; 84 struct squashfs_dir_index *index; 85 char *str; 86 87 TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count); 88 89 index = kmalloc(sizeof(*index) + SQUASHFS_NAME_LEN * 2 + 2, GFP_KERNEL); 90 if (index == NULL) { 91 ERROR("Failed to allocate squashfs_dir_index\n"); 92 goto out; 93 } 94 95 str = &index->name[SQUASHFS_NAME_LEN + 1]; 96 strncpy(str, name, len); 97 str[len] = '\0'; 98 99 for (i = 0; i < i_count; i++) { 100 err = squashfs_read_metadata(sb, index, &index_start, 101 &index_offset, sizeof(*index)); 102 if (err < 0) 103 break; 104 105 106 size = le32_to_cpu(index->size) + 1; 107 108 err = squashfs_read_metadata(sb, index->name, &index_start, 109 &index_offset, size); 110 if (err < 0) 111 break; 112 113 index->name[size] = '\0'; 114 115 if (strcmp(index->name, str) > 0) 116 break; 117 118 length = le32_to_cpu(index->index); 119 *next_block = le32_to_cpu(index->start_block) + 120 msblk->directory_table; 121 } 122 123 *next_offset = (length + *next_offset) % SQUASHFS_METADATA_SIZE; 124 kfree(index); 125 126out: 127 /* 128 * Return index (f_pos) of the looked up metadata block. Translate 129 * from internal f_pos to external f_pos which is offset by 3 because 130 * we invent "." and ".." entries which are not actually stored in the 131 * directory. 132 */ 133 return length + 3; 134} 135 136 137static struct dentry *squashfs_lookup(struct inode *dir, struct dentry *dentry, 138 struct nameidata *nd) 139{ 140 const unsigned char *name = dentry->d_name.name; 141 int len = dentry->d_name.len; 142 struct inode *inode = NULL; 143 struct squashfs_sb_info *msblk = dir->i_sb->s_fs_info; 144 struct squashfs_dir_header dirh; 145 struct squashfs_dir_entry *dire; 146 u64 block = squashfs_i(dir)->start + msblk->directory_table; 147 int offset = squashfs_i(dir)->offset; 148 int err, length = 0, dir_count, size; 149 150 TRACE("Entered squashfs_lookup [%llx:%x]\n", block, offset); 151 152 dire = kmalloc(sizeof(*dire) + SQUASHFS_NAME_LEN + 1, GFP_KERNEL); 153 if (dire == NULL) { 154 ERROR("Failed to allocate squashfs_dir_entry\n"); 155 return ERR_PTR(-ENOMEM); 156 } 157 158 if (len > SQUASHFS_NAME_LEN) { 159 err = -ENAMETOOLONG; 160 goto failed; 161 } 162 163 length = get_dir_index_using_name(dir->i_sb, &block, &offset, 164 squashfs_i(dir)->dir_idx_start, 165 squashfs_i(dir)->dir_idx_offset, 166 squashfs_i(dir)->dir_idx_cnt, name, len); 167 168 while (length < i_size_read(dir)) { 169 /* 170 * Read directory header. 171 */ 172 err = squashfs_read_metadata(dir->i_sb, &dirh, &block, 173 &offset, sizeof(dirh)); 174 if (err < 0) 175 goto read_failure; 176 177 length += sizeof(dirh); 178 179 dir_count = le32_to_cpu(dirh.count) + 1; 180 181 /* dir_count should never be larger than 256 */ 182 if (dir_count > 256) 183 goto data_error; 184 185 while (dir_count--) { 186 /* 187 * Read directory entry. 188 */ 189 err = squashfs_read_metadata(dir->i_sb, dire, &block, 190 &offset, sizeof(*dire)); 191 if (err < 0) 192 goto read_failure; 193 194 size = le16_to_cpu(dire->size) + 1; 195 196 /* size should never be larger than SQUASHFS_NAME_LEN */ 197 if (size > SQUASHFS_NAME_LEN) 198 goto data_error; 199 200 err = squashfs_read_metadata(dir->i_sb, dire->name, 201 &block, &offset, size); 202 if (err < 0) 203 goto read_failure; 204 205 length += sizeof(*dire) + size; 206 207 if (name[0] < dire->name[0]) 208 goto exit_lookup; 209 210 if (len == size && !strncmp(name, dire->name, len)) { 211 unsigned int blk, off, ino_num; 212 long long ino; 213 blk = le32_to_cpu(dirh.start_block); 214 off = le16_to_cpu(dire->offset); 215 ino_num = le32_to_cpu(dirh.inode_number) + 216 (short) le16_to_cpu(dire->inode_number); 217 ino = SQUASHFS_MKINODE(blk, off); 218 219 TRACE("calling squashfs_iget for directory " 220 "entry %s, inode %x:%x, %d\n", name, 221 blk, off, ino_num); 222 223 inode = squashfs_iget(dir->i_sb, ino, ino_num); 224 if (IS_ERR(inode)) { 225 err = PTR_ERR(inode); 226 goto failed; 227 } 228 229 goto exit_lookup; 230 } 231 } 232 } 233 234exit_lookup: 235 kfree(dire); 236 if (inode) 237 return d_splice_alias(inode, dentry); 238 d_add(dentry, inode); 239 return ERR_PTR(0); 240 241data_error: 242 err = -EIO; 243 244read_failure: 245 ERROR("Unable to read directory block [%llx:%x]\n", 246 squashfs_i(dir)->start + msblk->directory_table, 247 squashfs_i(dir)->offset); 248failed: 249 kfree(dire); 250 return ERR_PTR(err); 251} 252 253 254const struct inode_operations squashfs_dir_inode_ops = { 255 .lookup = squashfs_lookup, 256 .getxattr = generic_getxattr, 257 .listxattr = squashfs_listxattr 258}; 259