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