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 */ 63static 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 int len) 67{ 68 struct squashfs_sb_info *msblk = sb->s_fs_info; 69 int i, length = 0, err; 70 unsigned int size; 71 struct squashfs_dir_index *index; 72 char *str; 73 74 TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count); 75 76 index = kmalloc(sizeof(*index) + SQUASHFS_NAME_LEN * 2 + 2, GFP_KERNEL); 77 if (index == NULL) { 78 ERROR("Failed to allocate squashfs_dir_index\n"); 79 goto out; 80 } 81 82 str = &index->name[SQUASHFS_NAME_LEN + 1]; 83 strncpy(str, name, len); 84 str[len] = '\0'; 85 86 for (i = 0; i < i_count; i++) { 87 err = squashfs_read_metadata(sb, index, &index_start, 88 &index_offset, sizeof(*index)); 89 if (err < 0) 90 break; 91 92 93 size = le32_to_cpu(index->size) + 1; 94 if (size > SQUASHFS_NAME_LEN) 95 break; 96 97 err = squashfs_read_metadata(sb, index->name, &index_start, 98 &index_offset, size); 99 if (err < 0) 100 break; 101 102 index->name[size] = '\0'; 103 104 if (strcmp(index->name, str) > 0) 105 break; 106 107 length = le32_to_cpu(index->index); 108 *next_block = le32_to_cpu(index->start_block) + 109 msblk->directory_table; 110 } 111 112 *next_offset = (length + *next_offset) % SQUASHFS_METADATA_SIZE; 113 kfree(index); 114 115out: 116 /* 117 * Return index (f_pos) of the looked up metadata block. Translate 118 * from internal f_pos to external f_pos which is offset by 3 because 119 * we invent "." and ".." entries which are not actually stored in the 120 * directory. 121 */ 122 return length + 3; 123} 124 125 126static struct dentry *squashfs_lookup(struct inode *dir, struct dentry *dentry, 127 unsigned int flags) 128{ 129 const unsigned char *name = dentry->d_name.name; 130 int len = dentry->d_name.len; 131 struct inode *inode = NULL; 132 struct squashfs_sb_info *msblk = dir->i_sb->s_fs_info; 133 struct squashfs_dir_header dirh; 134 struct squashfs_dir_entry *dire; 135 u64 block = squashfs_i(dir)->start + msblk->directory_table; 136 int offset = squashfs_i(dir)->offset; 137 int err, length; 138 unsigned int dir_count, size; 139 140 TRACE("Entered squashfs_lookup [%llx:%x]\n", block, offset); 141 142 dire = kmalloc(sizeof(*dire) + SQUASHFS_NAME_LEN + 1, GFP_KERNEL); 143 if (dire == NULL) { 144 ERROR("Failed to allocate squashfs_dir_entry\n"); 145 return ERR_PTR(-ENOMEM); 146 } 147 148 if (len > SQUASHFS_NAME_LEN) { 149 err = -ENAMETOOLONG; 150 goto failed; 151 } 152 153 length = get_dir_index_using_name(dir->i_sb, &block, &offset, 154 squashfs_i(dir)->dir_idx_start, 155 squashfs_i(dir)->dir_idx_offset, 156 squashfs_i(dir)->dir_idx_cnt, name, len); 157 158 while (length < i_size_read(dir)) { 159 /* 160 * Read directory header. 161 */ 162 err = squashfs_read_metadata(dir->i_sb, &dirh, &block, 163 &offset, sizeof(dirh)); 164 if (err < 0) 165 goto read_failure; 166 167 length += sizeof(dirh); 168 169 dir_count = le32_to_cpu(dirh.count) + 1; 170 171 if (dir_count > SQUASHFS_DIR_COUNT) 172 goto data_error; 173 174 while (dir_count--) { 175 /* 176 * Read directory entry. 177 */ 178 err = squashfs_read_metadata(dir->i_sb, dire, &block, 179 &offset, sizeof(*dire)); 180 if (err < 0) 181 goto read_failure; 182 183 size = le16_to_cpu(dire->size) + 1; 184 185 /* size should never be larger than SQUASHFS_NAME_LEN */ 186 if (size > SQUASHFS_NAME_LEN) 187 goto data_error; 188 189 err = squashfs_read_metadata(dir->i_sb, dire->name, 190 &block, &offset, size); 191 if (err < 0) 192 goto read_failure; 193 194 length += sizeof(*dire) + size; 195 196 if (name[0] < dire->name[0]) 197 goto exit_lookup; 198 199 if (len == size && !strncmp(name, dire->name, len)) { 200 unsigned int blk, off, ino_num; 201 long long ino; 202 blk = le32_to_cpu(dirh.start_block); 203 off = le16_to_cpu(dire->offset); 204 ino_num = le32_to_cpu(dirh.inode_number) + 205 (short) le16_to_cpu(dire->inode_number); 206 ino = SQUASHFS_MKINODE(blk, off); 207 208 TRACE("calling squashfs_iget for directory " 209 "entry %s, inode %x:%x, %d\n", name, 210 blk, off, ino_num); 211 212 inode = squashfs_iget(dir->i_sb, ino, ino_num); 213 goto exit_lookup; 214 } 215 } 216 } 217 218exit_lookup: 219 kfree(dire); 220 return d_splice_alias(inode, dentry); 221 222data_error: 223 err = -EIO; 224 225read_failure: 226 ERROR("Unable to read directory block [%llx:%x]\n", 227 squashfs_i(dir)->start + msblk->directory_table, 228 squashfs_i(dir)->offset); 229failed: 230 kfree(dire); 231 return ERR_PTR(err); 232} 233 234 235const struct inode_operations squashfs_dir_inode_ops = { 236 .lookup = squashfs_lookup, 237 .listxattr = squashfs_listxattr 238}; 239