namei.c 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238
  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. * This file implements code to do filename lookup in directories.
  12. *
  13. * Like inodes, directories are packed into compressed metadata blocks, stored
  14. * in a directory table. Directories are accessed using the start address of
  15. * the metablock containing the directory and the offset into the
  16. * decompressed block (<block, offset>).
  17. *
  18. * Directories are organised in a slightly complex way, and are not simply
  19. * a list of file names. The organisation takes advantage of the
  20. * fact that (in most cases) the inodes of the files will be in the same
  21. * compressed metadata block, and therefore, can share the start block.
  22. * Directories are therefore organised in a two level list, a directory
  23. * header containing the shared start block value, and a sequence of directory
  24. * entries, each of which share the shared start block. A new directory header
  25. * is written once/if the inode start block changes. The directory
  26. * header/directory entry list is repeated as many times as necessary.
  27. *
  28. * Directories are sorted, and can contain a directory index to speed up
  29. * file lookup. Directory indexes store one entry per metablock, each entry
  30. * storing the index/filename mapping to the first directory header
  31. * in each metadata block. Directories are sorted in alphabetical order,
  32. * and at lookup the index is scanned linearly looking for the first filename
  33. * alphabetically larger than the filename being looked up. At this point the
  34. * location of the metadata block the filename is in has been found.
  35. * The general idea of the index is ensure only one metadata block needs to be
  36. * decompressed to do a lookup irrespective of the length of the directory.
  37. * This scheme has the advantage that it doesn't require extra memory overhead
  38. * and doesn't require much extra storage on disk.
  39. */
  40. #include <linux/fs.h>
  41. #include <linux/vfs.h>
  42. #include <linux/slab.h>
  43. #include <linux/string.h>
  44. #include <linux/dcache.h>
  45. #include <linux/xattr.h>
  46. #include "squashfs_fs.h"
  47. #include "squashfs_fs_sb.h"
  48. #include "squashfs_fs_i.h"
  49. #include "squashfs.h"
  50. #include "xattr.h"
  51. /*
  52. * Lookup name in the directory index, returning the location of the metadata
  53. * block containing it, and the directory index this represents.
  54. *
  55. * If we get an error reading the index then return the part of the index
  56. * (if any) we have managed to read - the index isn't essential, just
  57. * quicker.
  58. */
  59. static int get_dir_index_using_name(struct super_block *sb,
  60. u64 *next_block, int *next_offset, u64 index_start,
  61. int index_offset, int i_count, const char *name,
  62. int len)
  63. {
  64. struct squashfs_sb_info *msblk = sb->s_fs_info;
  65. int i, length = 0, err;
  66. unsigned int size;
  67. struct squashfs_dir_index *index;
  68. char *str;
  69. TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count);
  70. index = kmalloc(sizeof(*index) + SQUASHFS_NAME_LEN * 2 + 2, GFP_KERNEL);
  71. if (index == NULL) {
  72. ERROR("Failed to allocate squashfs_dir_index\n");
  73. goto out;
  74. }
  75. str = &index->name[SQUASHFS_NAME_LEN + 1];
  76. strncpy(str, name, len);
  77. str[len] = '\0';
  78. for (i = 0; i < i_count; i++) {
  79. err = squashfs_read_metadata(sb, index, &index_start,
  80. &index_offset, sizeof(*index));
  81. if (err < 0)
  82. break;
  83. size = le32_to_cpu(index->size) + 1;
  84. if (size > SQUASHFS_NAME_LEN)
  85. break;
  86. err = squashfs_read_metadata(sb, index->name, &index_start,
  87. &index_offset, size);
  88. if (err < 0)
  89. break;
  90. index->name[size] = '\0';
  91. if (strcmp(index->name, str) > 0)
  92. break;
  93. length = le32_to_cpu(index->index);
  94. *next_block = le32_to_cpu(index->start_block) +
  95. msblk->directory_table;
  96. }
  97. *next_offset = (length + *next_offset) % SQUASHFS_METADATA_SIZE;
  98. kfree(index);
  99. out:
  100. /*
  101. * Return index (f_pos) of the looked up metadata block. Translate
  102. * from internal f_pos to external f_pos which is offset by 3 because
  103. * we invent "." and ".." entries which are not actually stored in the
  104. * directory.
  105. */
  106. return length + 3;
  107. }
  108. static struct dentry *squashfs_lookup(struct inode *dir, struct dentry *dentry,
  109. unsigned int flags)
  110. {
  111. const unsigned char *name = dentry->d_name.name;
  112. int len = dentry->d_name.len;
  113. struct inode *inode = NULL;
  114. struct squashfs_sb_info *msblk = dir->i_sb->s_fs_info;
  115. struct squashfs_dir_header dirh;
  116. struct squashfs_dir_entry *dire;
  117. u64 block = squashfs_i(dir)->start + msblk->directory_table;
  118. int offset = squashfs_i(dir)->offset;
  119. int err, length;
  120. unsigned int dir_count, size;
  121. TRACE("Entered squashfs_lookup [%llx:%x]\n", block, offset);
  122. dire = kmalloc(sizeof(*dire) + SQUASHFS_NAME_LEN + 1, GFP_KERNEL);
  123. if (dire == NULL) {
  124. ERROR("Failed to allocate squashfs_dir_entry\n");
  125. return ERR_PTR(-ENOMEM);
  126. }
  127. if (len > SQUASHFS_NAME_LEN) {
  128. err = -ENAMETOOLONG;
  129. goto failed;
  130. }
  131. length = get_dir_index_using_name(dir->i_sb, &block, &offset,
  132. squashfs_i(dir)->dir_idx_start,
  133. squashfs_i(dir)->dir_idx_offset,
  134. squashfs_i(dir)->dir_idx_cnt, name, len);
  135. while (length < i_size_read(dir)) {
  136. /*
  137. * Read directory header.
  138. */
  139. err = squashfs_read_metadata(dir->i_sb, &dirh, &block,
  140. &offset, sizeof(dirh));
  141. if (err < 0)
  142. goto read_failure;
  143. length += sizeof(dirh);
  144. dir_count = le32_to_cpu(dirh.count) + 1;
  145. if (dir_count > SQUASHFS_DIR_COUNT)
  146. goto data_error;
  147. while (dir_count--) {
  148. /*
  149. * Read directory entry.
  150. */
  151. err = squashfs_read_metadata(dir->i_sb, dire, &block,
  152. &offset, sizeof(*dire));
  153. if (err < 0)
  154. goto read_failure;
  155. size = le16_to_cpu(dire->size) + 1;
  156. /* size should never be larger than SQUASHFS_NAME_LEN */
  157. if (size > SQUASHFS_NAME_LEN)
  158. goto data_error;
  159. err = squashfs_read_metadata(dir->i_sb, dire->name,
  160. &block, &offset, size);
  161. if (err < 0)
  162. goto read_failure;
  163. length += sizeof(*dire) + size;
  164. if (name[0] < dire->name[0])
  165. goto exit_lookup;
  166. if (len == size && !strncmp(name, dire->name, len)) {
  167. unsigned int blk, off, ino_num;
  168. long long ino;
  169. blk = le32_to_cpu(dirh.start_block);
  170. off = le16_to_cpu(dire->offset);
  171. ino_num = le32_to_cpu(dirh.inode_number) +
  172. (short) le16_to_cpu(dire->inode_number);
  173. ino = SQUASHFS_MKINODE(blk, off);
  174. TRACE("calling squashfs_iget for directory "
  175. "entry %s, inode %x:%x, %d\n", name,
  176. blk, off, ino_num);
  177. inode = squashfs_iget(dir->i_sb, ino, ino_num);
  178. goto exit_lookup;
  179. }
  180. }
  181. }
  182. exit_lookup:
  183. kfree(dire);
  184. return d_splice_alias(inode, dentry);
  185. data_error:
  186. err = -EIO;
  187. read_failure:
  188. ERROR("Unable to read directory block [%llx:%x]\n",
  189. squashfs_i(dir)->start + msblk->directory_table,
  190. squashfs_i(dir)->offset);
  191. failed:
  192. kfree(dire);
  193. return ERR_PTR(err);
  194. }
  195. const struct inode_operations squashfs_dir_inode_ops = {
  196. .lookup = squashfs_lookup,
  197. .listxattr = squashfs_listxattr
  198. };