1 /* Modified by Broadcom Corp. Portions Copyright (c) Broadcom Corp, 2012. */
3 * Squashfs - a compressed read only filesystem for Linux
5 * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008
6 * Phillip Lougher <phillip@lougher.demon.co.uk>
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version 2,
11 * or (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
26 * This file implements code to do filename lookup in directories.
28 * Like inodes, directories are packed into compressed metadata blocks, stored
29 * in a directory table. Directories are accessed using the start address of
30 * the metablock containing the directory and the offset into the
31 * decompressed block (<block, offset>).
33 * Directories are organised in a slightly complex way, and are not simply
34 * a list of file names. The organisation takes advantage of the
35 * fact that (in most cases) the inodes of the files will be in the same
36 * compressed metadata block, and therefore, can share the start block.
37 * Directories are therefore organised in a two level list, a directory
38 * header containing the shared start block value, and a sequence of directory
39 * entries, each of which share the shared start block. A new directory header
40 * is written once/if the inode start block changes. The directory
41 * header/directory entry list is repeated as many times as necessary.
43 * Directories are sorted, and can contain a directory index to speed up
44 * file lookup. Directory indexes store one entry per metablock, each entry
45 * storing the index/filename mapping to the first directory header
46 * in each metadata block. Directories are sorted in alphabetical order,
47 * and at lookup the index is scanned linearly looking for the first filename
48 * alphabetically larger than the filename being looked up. At this point the
49 * location of the metadata block the filename is in has been found.
50 * The general idea of the index is ensure only one metadata block needs to be
51 * decompressed to do a lookup irrespective of the length of the directory.
52 * This scheme has the advantage that it doesn't require extra memory overhead
53 * and doesn't require much extra storage on disk.
57 #include <linux/vfs.h>
58 #include <linux/slab.h>
59 #include <linux/string.h>
60 #include <linux/dcache.h>
61 #include <linux/xattr.h>
63 #include "squashfs_fs.h"
64 #include "squashfs_fs_sb.h"
65 #include "squashfs_fs_i.h"
70 * Lookup name in the directory index, returning the location of the metadata
71 * block containing it, and the directory index this represents.
73 * If we get an error reading the index then return the part of the index
74 * (if any) we have managed to read - the index isn't essential, just
77 static int get_dir_index_using_name(struct super_block
*sb
,
78 u64
*next_block
, int *next_offset
, u64 index_start
,
79 int index_offset
, int i_count
, const char *name
,
82 struct squashfs_sb_info
*msblk
= sb
->s_fs_info
;
83 int i
, size
, length
= 0, err
;
84 struct squashfs_dir_index
*index
;
87 TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count
);
89 index
= kmalloc(sizeof(*index
) + SQUASHFS_NAME_LEN
* 2 + 2, GFP_KERNEL
);
91 ERROR("Failed to allocate squashfs_dir_index\n");
95 str
= &index
->name
[SQUASHFS_NAME_LEN
+ 1];
96 strncpy(str
, name
, len
);
99 for (i
= 0; i
< i_count
; i
++) {
100 err
= squashfs_read_metadata(sb
, index
, &index_start
,
101 &index_offset
, sizeof(*index
));
106 size
= le32_to_cpu(index
->size
) + 1;
108 err
= squashfs_read_metadata(sb
, index
->name
, &index_start
,
109 &index_offset
, size
);
113 index
->name
[size
] = '\0';
115 if (strcmp(index
->name
, str
) > 0)
118 length
= le32_to_cpu(index
->index
);
119 *next_block
= le32_to_cpu(index
->start_block
) +
120 msblk
->directory_table
;
123 *next_offset
= (length
+ *next_offset
) % SQUASHFS_METADATA_SIZE
;
128 * Return index (f_pos) of the looked up metadata block. Translate
129 * from internal f_pos to external f_pos which is offset by 3 because
130 * we invent "." and ".." entries which are not actually stored in the
137 static struct dentry
*squashfs_lookup(struct inode
*dir
, struct dentry
*dentry
,
138 struct nameidata
*nd
)
140 const unsigned char *name
= dentry
->d_name
.name
;
141 int len
= dentry
->d_name
.len
;
142 struct inode
*inode
= NULL
;
143 struct squashfs_sb_info
*msblk
= dir
->i_sb
->s_fs_info
;
144 struct squashfs_dir_header dirh
;
145 struct squashfs_dir_entry
*dire
;
146 u64 block
= squashfs_i(dir
)->start
+ msblk
->directory_table
;
147 int offset
= squashfs_i(dir
)->offset
;
148 int err
, length
= 0, dir_count
, size
;
150 TRACE("Entered squashfs_lookup [%llx:%x]\n", block
, offset
);
152 dire
= kmalloc(sizeof(*dire
) + SQUASHFS_NAME_LEN
+ 1, GFP_KERNEL
);
154 ERROR("Failed to allocate squashfs_dir_entry\n");
155 return ERR_PTR(-ENOMEM
);
158 if (len
> SQUASHFS_NAME_LEN
) {
163 length
= get_dir_index_using_name(dir
->i_sb
, &block
, &offset
,
164 squashfs_i(dir
)->dir_idx_start
,
165 squashfs_i(dir
)->dir_idx_offset
,
166 squashfs_i(dir
)->dir_idx_cnt
, name
, len
);
168 while (length
< i_size_read(dir
)) {
170 * Read directory header.
172 err
= squashfs_read_metadata(dir
->i_sb
, &dirh
, &block
,
173 &offset
, sizeof(dirh
));
177 length
+= sizeof(dirh
);
179 dir_count
= le32_to_cpu(dirh
.count
) + 1;
181 /* dir_count should never be larger than 256 */
185 while (dir_count
--) {
187 * Read directory entry.
189 err
= squashfs_read_metadata(dir
->i_sb
, dire
, &block
,
190 &offset
, sizeof(*dire
));
194 size
= le16_to_cpu(dire
->size
) + 1;
196 /* size should never be larger than SQUASHFS_NAME_LEN */
197 if (size
> SQUASHFS_NAME_LEN
)
200 err
= squashfs_read_metadata(dir
->i_sb
, dire
->name
,
201 &block
, &offset
, size
);
205 length
+= sizeof(*dire
) + size
;
207 if (name
[0] < dire
->name
[0])
210 if (len
== size
&& !strncmp(name
, dire
->name
, len
)) {
211 unsigned int blk
, off
, ino_num
;
213 blk
= le32_to_cpu(dirh
.start_block
);
214 off
= le16_to_cpu(dire
->offset
);
215 ino_num
= le32_to_cpu(dirh
.inode_number
) +
216 (short) le16_to_cpu(dire
->inode_number
);
217 ino
= SQUASHFS_MKINODE(blk
, off
);
219 TRACE("calling squashfs_iget for directory "
220 "entry %s, inode %x:%x, %d\n", name
,
223 inode
= squashfs_iget(dir
->i_sb
, ino
, ino_num
);
225 err
= PTR_ERR(inode
);
237 return d_splice_alias(inode
, dentry
);
238 d_add(dentry
, inode
);
245 ERROR("Unable to read directory block [%llx:%x]\n",
246 squashfs_i(dir
)->start
+ msblk
->directory_table
,
247 squashfs_i(dir
)->offset
);
254 const struct inode_operations squashfs_dir_inode_ops
= {
255 .lookup
= squashfs_lookup
,
256 .getxattr
= generic_getxattr
,
257 .listxattr
= squashfs_listxattr