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 | 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(size: 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(p: str, q: name, size: 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(objp: index); |
114 | |
115 | out: |
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 | |
126 | static 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(inode: dir)->start + msblk->directory_table; |
136 | int offset = squashfs_i(inode: 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(size: 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(error: -ENOMEM); |
146 | } |
147 | |
148 | if (len > SQUASHFS_NAME_LEN) { |
149 | err = -ENAMETOOLONG; |
150 | goto failed; |
151 | } |
152 | |
153 | length = get_dir_index_using_name(sb: dir->i_sb, next_block: &block, next_offset: &offset, |
154 | index_start: squashfs_i(inode: dir)->dir_idx_start, |
155 | index_offset: squashfs_i(inode: dir)->dir_idx_offset, |
156 | i_count: squashfs_i(inode: dir)->dir_idx_cnt, name, len); |
157 | |
158 | while (length < i_size_read(inode: 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 | |
218 | exit_lookup: |
219 | kfree(objp: dire); |
220 | return d_splice_alias(inode, dentry); |
221 | |
222 | data_error: |
223 | err = -EIO; |
224 | |
225 | read_failure: |
226 | ERROR("Unable to read directory block [%llx:%x]\n" , |
227 | squashfs_i(dir)->start + msblk->directory_table, |
228 | squashfs_i(dir)->offset); |
229 | failed: |
230 | kfree(objp: dire); |
231 | return ERR_PTR(error: err); |
232 | } |
233 | |
234 | |
235 | const struct inode_operations squashfs_dir_inode_ops = { |
236 | .lookup = squashfs_lookup, |
237 | .listxattr = squashfs_listxattr |
238 | }; |
239 | |