tnc_misc.c 12 KB

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