namei.c 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * Copyright (C) 2017-2018 HUAWEI, Inc.
  4. * https://www.huawei.com/
  5. * Created by Gao Xiang <gaoxiang25@huawei.com>
  6. */
  7. #include "xattr.h"
  8. #include <trace/events/erofs.h>
  9. struct erofs_qstr {
  10. const unsigned char *name;
  11. const unsigned char *end;
  12. };
  13. /* based on the end of qn is accurate and it must have the trailing '\0' */
  14. static inline int erofs_dirnamecmp(const struct erofs_qstr *qn,
  15. const struct erofs_qstr *qd,
  16. unsigned int *matched)
  17. {
  18. unsigned int i = *matched;
  19. /*
  20. * on-disk error, let's only BUG_ON in the debugging mode.
  21. * otherwise, it will return 1 to just skip the invalid name
  22. * and go on (in consideration of the lookup performance).
  23. */
  24. DBG_BUGON(qd->name > qd->end);
  25. /* qd could not have trailing '\0' */
  26. /* However it is absolutely safe if < qd->end */
  27. while (qd->name + i < qd->end && qd->name[i] != '\0') {
  28. if (qn->name[i] != qd->name[i]) {
  29. *matched = i;
  30. return qn->name[i] > qd->name[i] ? 1 : -1;
  31. }
  32. ++i;
  33. }
  34. *matched = i;
  35. /* See comments in __d_alloc on the terminating NUL character */
  36. return qn->name[i] == '\0' ? 0 : 1;
  37. }
  38. #define nameoff_from_disk(off, sz) (le16_to_cpu(off) & ((sz) - 1))
  39. static struct erofs_dirent *find_target_dirent(struct erofs_qstr *name,
  40. u8 *data,
  41. unsigned int dirblksize,
  42. const int ndirents)
  43. {
  44. int head, back;
  45. unsigned int startprfx, endprfx;
  46. struct erofs_dirent *const de = (struct erofs_dirent *)data;
  47. /* since the 1st dirent has been evaluated previously */
  48. head = 1;
  49. back = ndirents - 1;
  50. startprfx = endprfx = 0;
  51. while (head <= back) {
  52. const int mid = head + (back - head) / 2;
  53. const int nameoff = nameoff_from_disk(de[mid].nameoff,
  54. dirblksize);
  55. unsigned int matched = min(startprfx, endprfx);
  56. struct erofs_qstr dname = {
  57. .name = data + nameoff,
  58. .end = mid >= ndirents - 1 ?
  59. data + dirblksize :
  60. data + nameoff_from_disk(de[mid + 1].nameoff,
  61. dirblksize)
  62. };
  63. /* string comparison without already matched prefix */
  64. int ret = erofs_dirnamecmp(name, &dname, &matched);
  65. if (!ret) {
  66. return de + mid;
  67. } else if (ret > 0) {
  68. head = mid + 1;
  69. startprfx = matched;
  70. } else {
  71. back = mid - 1;
  72. endprfx = matched;
  73. }
  74. }
  75. return ERR_PTR(-ENOENT);
  76. }
  77. static struct page *find_target_block_classic(struct inode *dir,
  78. struct erofs_qstr *name,
  79. int *_ndirents)
  80. {
  81. unsigned int startprfx, endprfx;
  82. int head, back;
  83. struct address_space *const mapping = dir->i_mapping;
  84. struct page *candidate = ERR_PTR(-ENOENT);
  85. startprfx = endprfx = 0;
  86. head = 0;
  87. back = erofs_inode_datablocks(dir) - 1;
  88. while (head <= back) {
  89. const int mid = head + (back - head) / 2;
  90. struct page *page = read_mapping_page(mapping, mid, NULL);
  91. if (!IS_ERR(page)) {
  92. struct erofs_dirent *de = kmap_atomic(page);
  93. const int nameoff = nameoff_from_disk(de->nameoff,
  94. EROFS_BLKSIZ);
  95. const int ndirents = nameoff / sizeof(*de);
  96. int diff;
  97. unsigned int matched;
  98. struct erofs_qstr dname;
  99. if (!ndirents) {
  100. kunmap_atomic(de);
  101. put_page(page);
  102. erofs_err(dir->i_sb,
  103. "corrupted dir block %d @ nid %llu",
  104. mid, EROFS_I(dir)->nid);
  105. DBG_BUGON(1);
  106. page = ERR_PTR(-EFSCORRUPTED);
  107. goto out;
  108. }
  109. matched = min(startprfx, endprfx);
  110. dname.name = (u8 *)de + nameoff;
  111. if (ndirents == 1)
  112. dname.end = (u8 *)de + EROFS_BLKSIZ;
  113. else
  114. dname.end = (u8 *)de +
  115. nameoff_from_disk(de[1].nameoff,
  116. EROFS_BLKSIZ);
  117. /* string comparison without already matched prefix */
  118. diff = erofs_dirnamecmp(name, &dname, &matched);
  119. kunmap_atomic(de);
  120. if (!diff) {
  121. *_ndirents = 0;
  122. goto out;
  123. } else if (diff > 0) {
  124. head = mid + 1;
  125. startprfx = matched;
  126. if (!IS_ERR(candidate))
  127. put_page(candidate);
  128. candidate = page;
  129. *_ndirents = ndirents;
  130. } else {
  131. put_page(page);
  132. back = mid - 1;
  133. endprfx = matched;
  134. }
  135. continue;
  136. }
  137. out: /* free if the candidate is valid */
  138. if (!IS_ERR(candidate))
  139. put_page(candidate);
  140. return page;
  141. }
  142. return candidate;
  143. }
  144. int erofs_namei(struct inode *dir,
  145. struct qstr *name,
  146. erofs_nid_t *nid, unsigned int *d_type)
  147. {
  148. int ndirents;
  149. struct page *page;
  150. void *data;
  151. struct erofs_dirent *de;
  152. struct erofs_qstr qn;
  153. if (!dir->i_size)
  154. return -ENOENT;
  155. qn.name = name->name;
  156. qn.end = name->name + name->len;
  157. ndirents = 0;
  158. page = find_target_block_classic(dir, &qn, &ndirents);
  159. if (IS_ERR(page))
  160. return PTR_ERR(page);
  161. data = kmap_atomic(page);
  162. /* the target page has been mapped */
  163. if (ndirents)
  164. de = find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents);
  165. else
  166. de = (struct erofs_dirent *)data;
  167. if (!IS_ERR(de)) {
  168. *nid = le64_to_cpu(de->nid);
  169. *d_type = de->file_type;
  170. }
  171. kunmap_atomic(data);
  172. put_page(page);
  173. return PTR_ERR_OR_ZERO(de);
  174. }
  175. /* NOTE: i_mutex is already held by vfs */
  176. static struct dentry *erofs_lookup(struct inode *dir,
  177. struct dentry *dentry,
  178. unsigned int flags)
  179. {
  180. int err;
  181. erofs_nid_t nid;
  182. unsigned int d_type;
  183. struct inode *inode;
  184. DBG_BUGON(!d_really_is_negative(dentry));
  185. /* dentry must be unhashed in lookup, no need to worry about */
  186. DBG_BUGON(!d_unhashed(dentry));
  187. trace_erofs_lookup(dir, dentry, flags);
  188. /* file name exceeds fs limit */
  189. if (dentry->d_name.len > EROFS_NAME_LEN)
  190. return ERR_PTR(-ENAMETOOLONG);
  191. /* false uninitialized warnings on gcc 4.8.x */
  192. err = erofs_namei(dir, &dentry->d_name, &nid, &d_type);
  193. if (err == -ENOENT) {
  194. /* negative dentry */
  195. inode = NULL;
  196. } else if (err) {
  197. inode = ERR_PTR(err);
  198. } else {
  199. erofs_dbg("%s, %s (nid %llu) found, d_type %u", __func__,
  200. dentry->d_name.name, nid, d_type);
  201. inode = erofs_iget(dir->i_sb, nid, d_type == FT_DIR);
  202. }
  203. return d_splice_alias(inode, dentry);
  204. }
  205. const struct inode_operations erofs_dir_iops = {
  206. .lookup = erofs_lookup,
  207. .getattr = erofs_getattr,
  208. .listxattr = erofs_listxattr,
  209. .get_acl = erofs_get_acl,
  210. };