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