tnc_misc.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * This file is part of UBIFS.
  4. *
  5. * Copyright (C) 2006-2008 Nokia Corporation.
  6. *
  7. * Authors: Adrian Hunter
  8. * Artem Bityutskiy (Битюцкий Артём)
  9. */
  10. /*
  11. * This file contains miscelanious TNC-related functions shared betweend
  12. * different files. This file does not form any logically separate TNC
  13. * sub-system. The file was created because there is a lot of TNC code and
  14. * putting it all in one file would make that file too big and unreadable.
  15. */
  16. #ifdef __UBOOT__
  17. #include <log.h>
  18. #include <dm/devres.h>
  19. #include <linux/err.h>
  20. #endif
  21. #include "ubifs.h"
  22. /**
  23. * ubifs_tnc_levelorder_next - next TNC tree element in levelorder traversal.
  24. * @zr: root of the subtree to traverse
  25. * @znode: previous znode
  26. *
  27. * This function implements levelorder TNC traversal. The LNC is ignored.
  28. * Returns the next element or %NULL if @znode is already the last one.
  29. */
  30. struct ubifs_znode *ubifs_tnc_levelorder_next(struct ubifs_znode *zr,
  31. struct ubifs_znode *znode)
  32. {
  33. int level, iip, level_search = 0;
  34. struct ubifs_znode *zn;
  35. ubifs_assert(zr);
  36. if (unlikely(!znode))
  37. return zr;
  38. if (unlikely(znode == zr)) {
  39. if (znode->level == 0)
  40. return NULL;
  41. return ubifs_tnc_find_child(zr, 0);
  42. }
  43. level = znode->level;
  44. iip = znode->iip;
  45. while (1) {
  46. ubifs_assert(znode->level <= zr->level);
  47. /*
  48. * First walk up until there is a znode with next branch to
  49. * look at.
  50. */
  51. while (znode->parent != zr && iip >= znode->parent->child_cnt) {
  52. znode = znode->parent;
  53. iip = znode->iip;
  54. }
  55. if (unlikely(znode->parent == zr &&
  56. iip >= znode->parent->child_cnt)) {
  57. /* This level is done, switch to the lower one */
  58. level -= 1;
  59. if (level_search || level < 0)
  60. /*
  61. * We were already looking for znode at lower
  62. * level ('level_search'). As we are here
  63. * again, it just does not exist. Or all levels
  64. * were finished ('level < 0').
  65. */
  66. return NULL;
  67. level_search = 1;
  68. iip = -1;
  69. znode = ubifs_tnc_find_child(zr, 0);
  70. ubifs_assert(znode);
  71. }
  72. /* Switch to the next index */
  73. zn = ubifs_tnc_find_child(znode->parent, iip + 1);
  74. if (!zn) {
  75. /* No more children to look at, we have walk up */
  76. iip = znode->parent->child_cnt;
  77. continue;
  78. }
  79. /* Walk back down to the level we came from ('level') */
  80. while (zn->level != level) {
  81. znode = zn;
  82. zn = ubifs_tnc_find_child(zn, 0);
  83. if (!zn) {
  84. /*
  85. * This path is not too deep so it does not
  86. * reach 'level'. Try next path.
  87. */
  88. iip = znode->iip;
  89. break;
  90. }
  91. }
  92. if (zn) {
  93. ubifs_assert(zn->level >= 0);
  94. return zn;
  95. }
  96. }
  97. }
  98. /**
  99. * ubifs_search_zbranch - search znode branch.
  100. * @c: UBIFS file-system description object
  101. * @znode: znode to search in
  102. * @key: key to search for
  103. * @n: znode branch slot number is returned here
  104. *
  105. * This is a helper function which search branch with key @key in @znode using
  106. * binary search. The result of the search may be:
  107. * o exact match, then %1 is returned, and the slot number of the branch is
  108. * stored in @n;
  109. * o no exact match, then %0 is returned and the slot number of the left
  110. * closest branch is returned in @n; the slot if all keys in this znode are
  111. * greater than @key, then %-1 is returned in @n.
  112. */
  113. int ubifs_search_zbranch(const struct ubifs_info *c,
  114. const struct ubifs_znode *znode,
  115. const union ubifs_key *key, int *n)
  116. {
  117. int beg = 0, end = znode->child_cnt, uninitialized_var(mid);
  118. int uninitialized_var(cmp);
  119. const struct ubifs_zbranch *zbr = &znode->zbranch[0];
  120. ubifs_assert(end > beg);
  121. while (end > beg) {
  122. mid = (beg + end) >> 1;
  123. cmp = keys_cmp(c, key, &zbr[mid].key);
  124. if (cmp > 0)
  125. beg = mid + 1;
  126. else if (cmp < 0)
  127. end = mid;
  128. else {
  129. *n = mid;
  130. return 1;
  131. }
  132. }
  133. *n = end - 1;
  134. /* The insert point is after *n */
  135. ubifs_assert(*n >= -1 && *n < znode->child_cnt);
  136. if (*n == -1)
  137. ubifs_assert(keys_cmp(c, key, &zbr[0].key) < 0);
  138. else
  139. ubifs_assert(keys_cmp(c, key, &zbr[*n].key) > 0);
  140. if (*n + 1 < znode->child_cnt)
  141. ubifs_assert(keys_cmp(c, key, &zbr[*n + 1].key) < 0);
  142. return 0;
  143. }
  144. /**
  145. * ubifs_tnc_postorder_first - find first znode to do postorder tree traversal.
  146. * @znode: znode to start at (root of the sub-tree to traverse)
  147. *
  148. * Find the lowest leftmost znode in a subtree of the TNC tree. The LNC is
  149. * ignored.
  150. */
  151. struct ubifs_znode *ubifs_tnc_postorder_first(struct ubifs_znode *znode)
  152. {
  153. if (unlikely(!znode))
  154. return NULL;
  155. while (znode->level > 0) {
  156. struct ubifs_znode *child;
  157. child = ubifs_tnc_find_child(znode, 0);
  158. if (!child)
  159. return znode;
  160. znode = child;
  161. }
  162. return znode;
  163. }
  164. /**
  165. * ubifs_tnc_postorder_next - next TNC tree element in postorder traversal.
  166. * @znode: previous znode
  167. *
  168. * This function implements postorder TNC traversal. The LNC is ignored.
  169. * Returns the next element or %NULL if @znode is already the last one.
  170. */
  171. struct ubifs_znode *ubifs_tnc_postorder_next(struct ubifs_znode *znode)
  172. {
  173. struct ubifs_znode *zn;
  174. ubifs_assert(znode);
  175. if (unlikely(!znode->parent))
  176. return NULL;
  177. /* Switch to the next index in the parent */
  178. zn = ubifs_tnc_find_child(znode->parent, znode->iip + 1);
  179. if (!zn)
  180. /* This is in fact the last child, return parent */
  181. return znode->parent;
  182. /* Go to the first znode in this new subtree */
  183. return ubifs_tnc_postorder_first(zn);
  184. }
  185. /**
  186. * ubifs_destroy_tnc_subtree - destroy all znodes connected to a subtree.
  187. * @znode: znode defining subtree to destroy
  188. *
  189. * This function destroys subtree of the TNC tree. Returns number of clean
  190. * znodes in the subtree.
  191. */
  192. long ubifs_destroy_tnc_subtree(struct ubifs_znode *znode)
  193. {
  194. struct ubifs_znode *zn = ubifs_tnc_postorder_first(znode);
  195. long clean_freed = 0;
  196. int n;
  197. ubifs_assert(zn);
  198. while (1) {
  199. for (n = 0; n < zn->child_cnt; n++) {
  200. if (!zn->zbranch[n].znode)
  201. continue;
  202. if (zn->level > 0 &&
  203. !ubifs_zn_dirty(zn->zbranch[n].znode))
  204. clean_freed += 1;
  205. cond_resched();
  206. kfree(zn->zbranch[n].znode);
  207. }
  208. if (zn == znode) {
  209. if (!ubifs_zn_dirty(zn))
  210. clean_freed += 1;
  211. kfree(zn);
  212. return clean_freed;
  213. }
  214. zn = ubifs_tnc_postorder_next(zn);
  215. }
  216. }
  217. /**
  218. * read_znode - read an indexing node from flash and fill znode.
  219. * @c: UBIFS file-system description object
  220. * @lnum: LEB of the indexing node to read
  221. * @offs: node offset
  222. * @len: node length
  223. * @znode: znode to read to
  224. *
  225. * This function reads an indexing node from the flash media and fills znode
  226. * with the read data. Returns zero in case of success and a negative error
  227. * code in case of failure. The read indexing node is validated and if anything
  228. * is wrong with it, this function prints complaint messages and returns
  229. * %-EINVAL.
  230. */
  231. static int read_znode(struct ubifs_info *c, int lnum, int offs, int len,
  232. struct ubifs_znode *znode)
  233. {
  234. int i, err, type, cmp;
  235. struct ubifs_idx_node *idx;
  236. idx = kmalloc(c->max_idx_node_sz, GFP_NOFS);
  237. if (!idx)
  238. return -ENOMEM;
  239. err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);
  240. if (err < 0) {
  241. kfree(idx);
  242. return err;
  243. }
  244. znode->child_cnt = le16_to_cpu(idx->child_cnt);
  245. znode->level = le16_to_cpu(idx->level);
  246. dbg_tnc("LEB %d:%d, level %d, %d branch",
  247. lnum, offs, znode->level, znode->child_cnt);
  248. if (znode->child_cnt > c->fanout || znode->level > UBIFS_MAX_LEVELS) {
  249. ubifs_err(c, "current fanout %d, branch count %d",
  250. c->fanout, znode->child_cnt);
  251. ubifs_err(c, "max levels %d, znode level %d",
  252. UBIFS_MAX_LEVELS, znode->level);
  253. err = 1;
  254. goto out_dump;
  255. }
  256. for (i = 0; i < znode->child_cnt; i++) {
  257. const struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);
  258. struct ubifs_zbranch *zbr = &znode->zbranch[i];
  259. key_read(c, &br->key, &zbr->key);
  260. zbr->lnum = le32_to_cpu(br->lnum);
  261. zbr->offs = le32_to_cpu(br->offs);
  262. zbr->len = le32_to_cpu(br->len);
  263. zbr->znode = NULL;
  264. /* Validate branch */
  265. if (zbr->lnum < c->main_first ||
  266. zbr->lnum >= c->leb_cnt || zbr->offs < 0 ||
  267. zbr->offs + zbr->len > c->leb_size || zbr->offs & 7) {
  268. ubifs_err(c, "bad branch %d", i);
  269. err = 2;
  270. goto out_dump;
  271. }
  272. switch (key_type(c, &zbr->key)) {
  273. case UBIFS_INO_KEY:
  274. case UBIFS_DATA_KEY:
  275. case UBIFS_DENT_KEY:
  276. case UBIFS_XENT_KEY:
  277. break;
  278. default:
  279. ubifs_err(c, "bad key type at slot %d: %d",
  280. i, key_type(c, &zbr->key));
  281. err = 3;
  282. goto out_dump;
  283. }
  284. if (znode->level)
  285. continue;
  286. type = key_type(c, &zbr->key);
  287. if (c->ranges[type].max_len == 0) {
  288. if (zbr->len != c->ranges[type].len) {
  289. ubifs_err(c, "bad target node (type %d) length (%d)",
  290. type, zbr->len);
  291. ubifs_err(c, "have to be %d", c->ranges[type].len);
  292. err = 4;
  293. goto out_dump;
  294. }
  295. } else if (zbr->len < c->ranges[type].min_len ||
  296. zbr->len > c->ranges[type].max_len) {
  297. ubifs_err(c, "bad target node (type %d) length (%d)",
  298. type, zbr->len);
  299. ubifs_err(c, "have to be in range of %d-%d",
  300. c->ranges[type].min_len,
  301. c->ranges[type].max_len);
  302. err = 5;
  303. goto out_dump;
  304. }
  305. }
  306. /*
  307. * Ensure that the next key is greater or equivalent to the
  308. * previous one.
  309. */
  310. for (i = 0; i < znode->child_cnt - 1; i++) {
  311. const union ubifs_key *key1, *key2;
  312. key1 = &znode->zbranch[i].key;
  313. key2 = &znode->zbranch[i + 1].key;
  314. cmp = keys_cmp(c, key1, key2);
  315. if (cmp > 0) {
  316. ubifs_err(c, "bad key order (keys %d and %d)", i, i + 1);
  317. err = 6;
  318. goto out_dump;
  319. } else if (cmp == 0 && !is_hash_key(c, key1)) {
  320. /* These can only be keys with colliding hash */
  321. ubifs_err(c, "keys %d and %d are not hashed but equivalent",
  322. i, i + 1);
  323. err = 7;
  324. goto out_dump;
  325. }
  326. }
  327. kfree(idx);
  328. return 0;
  329. out_dump:
  330. ubifs_err(c, "bad indexing node at LEB %d:%d, error %d", lnum, offs, err);
  331. ubifs_dump_node(c, idx);
  332. kfree(idx);
  333. return -EINVAL;
  334. }
  335. /**
  336. * ubifs_load_znode - load znode to TNC cache.
  337. * @c: UBIFS file-system description object
  338. * @zbr: znode branch
  339. * @parent: znode's parent
  340. * @iip: index in parent
  341. *
  342. * This function loads znode pointed to by @zbr into the TNC cache and
  343. * returns pointer to it in case of success and a negative error code in case
  344. * of failure.
  345. */
  346. struct ubifs_znode *ubifs_load_znode(struct ubifs_info *c,
  347. struct ubifs_zbranch *zbr,
  348. struct ubifs_znode *parent, int iip)
  349. {
  350. int err;
  351. struct ubifs_znode *znode;
  352. ubifs_assert(!zbr->znode);
  353. /*
  354. * A slab cache is not presently used for znodes because the znode size
  355. * depends on the fanout which is stored in the superblock.
  356. */
  357. znode = kzalloc(c->max_znode_sz, GFP_NOFS);
  358. if (!znode)
  359. return ERR_PTR(-ENOMEM);
  360. err = read_znode(c, zbr->lnum, zbr->offs, zbr->len, znode);
  361. if (err)
  362. goto out;
  363. atomic_long_inc(&c->clean_zn_cnt);
  364. /*
  365. * Increment the global clean znode counter as well. It is OK that
  366. * global and per-FS clean znode counters may be inconsistent for some
  367. * short time (because we might be preempted at this point), the global
  368. * one is only used in shrinker.
  369. */
  370. atomic_long_inc(&ubifs_clean_zn_cnt);
  371. zbr->znode = znode;
  372. znode->parent = parent;
  373. znode->time = get_seconds();
  374. znode->iip = iip;
  375. return znode;
  376. out:
  377. kfree(znode);
  378. return ERR_PTR(err);
  379. }
  380. /**
  381. * ubifs_tnc_read_node - read a leaf node from the flash media.
  382. * @c: UBIFS file-system description object
  383. * @zbr: key and position of the node
  384. * @node: node is returned here
  385. *
  386. * This function reads a node defined by @zbr from the flash media. Returns
  387. * zero in case of success or a negative negative error code in case of
  388. * failure.
  389. */
  390. int ubifs_tnc_read_node(struct ubifs_info *c, struct ubifs_zbranch *zbr,
  391. void *node)
  392. {
  393. union ubifs_key key1, *key = &zbr->key;
  394. int err, type = key_type(c, key);
  395. struct ubifs_wbuf *wbuf;
  396. /*
  397. * 'zbr' has to point to on-flash node. The node may sit in a bud and
  398. * may even be in a write buffer, so we have to take care about this.
  399. */
  400. wbuf = ubifs_get_wbuf(c, zbr->lnum);
  401. if (wbuf)
  402. err = ubifs_read_node_wbuf(wbuf, node, type, zbr->len,
  403. zbr->lnum, zbr->offs);
  404. else
  405. err = ubifs_read_node(c, node, type, zbr->len, zbr->lnum,
  406. zbr->offs);
  407. if (err) {
  408. dbg_tnck(key, "key ");
  409. return err;
  410. }
  411. /* Make sure the key of the read node is correct */
  412. key_read(c, node + UBIFS_KEY_OFFSET, &key1);
  413. if (!keys_eq(c, key, &key1)) {
  414. ubifs_err(c, "bad key in node at LEB %d:%d",
  415. zbr->lnum, zbr->offs);
  416. dbg_tnck(key, "looked for key ");
  417. dbg_tnck(&key1, "but found node's key ");
  418. ubifs_dump_node(c, node);
  419. return -EINVAL;
  420. }
  421. return 0;
  422. }