233 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/*3 * Squashfs - a compressed read only filesystem for Linux4 *5 * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 20086 * Phillip Lougher <phillip@squashfs.org.uk>7 *8 * namei.c9 */10 11/*12 * This file implements code to do filename lookup in directories.13 *14 * Like inodes, directories are packed into compressed metadata blocks, stored15 * in a directory table. Directories are accessed using the start address of16 * the metablock containing the directory and the offset into the17 * decompressed block (<block, offset>).18 *19 * Directories are organised in a slightly complex way, and are not simply20 * a list of file names. The organisation takes advantage of the21 * fact that (in most cases) the inodes of the files will be in the same22 * compressed metadata block, and therefore, can share the start block.23 * Directories are therefore organised in a two level list, a directory24 * header containing the shared start block value, and a sequence of directory25 * entries, each of which share the shared start block. A new directory header26 * is written once/if the inode start block changes. The directory27 * header/directory entry list is repeated as many times as necessary.28 *29 * Directories are sorted, and can contain a directory index to speed up30 * file lookup. Directory indexes store one entry per metablock, each entry31 * storing the index/filename mapping to the first directory header32 * in each metadata block. Directories are sorted in alphabetical order,33 * and at lookup the index is scanned linearly looking for the first filename34 * alphabetically larger than the filename being looked up. At this point the35 * 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 be37 * 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 overhead39 * 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 metadata57 * 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 index60 * (if any) we have managed to read - the index isn't essential, just61 * 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{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 109out:110 /*111 * Return index (f_pos) of the looked up metadata block. Translate112 * from internal f_pos to external f_pos which is offset by 3 because113 * we invent "." and ".." entries which are not actually stored in the114 * directory.115 */116 return length + 3;117}118 119 120static 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 212exit_lookup:213 kfree(dire);214 return d_splice_alias(inode, dentry);215 216data_error:217 err = -EIO;218 219read_failure:220 ERROR("Unable to read directory block [%llx:%x]\n",221 squashfs_i(dir)->start + msblk->directory_table,222 squashfs_i(dir)->offset);223failed:224 kfree(dire);225 return ERR_PTR(err);226}227 228 229const struct inode_operations squashfs_dir_inode_ops = {230 .lookup = squashfs_lookup,231 .listxattr = squashfs_listxattr232};233