Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-only
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 : /*
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 :
18 : #include "linux_err.h"
19 : #include "bitops.h"
20 : #include "kmem.h"
21 : #include "ubifs.h"
22 : #include "defs.h"
23 : #include "debug.h"
24 : #include "key.h"
25 : #include "misc.h"
26 :
27 : /**
28 : * ubifs_search_zbranch - search znode branch.
29 : * @c: UBIFS file-system description object
30 : * @znode: znode to search in
31 : * @key: key to search for
32 : * @n: znode branch slot number is returned here
33 : *
34 : * This is a helper function which search branch with key @key in @znode using
35 : * binary search. The result of the search may be:
36 : * o exact match, then %1 is returned, and the slot number of the branch is
37 : * stored in @n;
38 : * o no exact match, then %0 is returned and the slot number of the left
39 : * closest branch is returned in @n; the slot if all keys in this znode are
40 : * greater than @key, then %-1 is returned in @n.
41 : */
42 55851721955 : int ubifs_search_zbranch(const struct ubifs_info *c,
43 : const struct ubifs_znode *znode,
44 : const union ubifs_key *key, int *n)
45 : {
46 55851721955 : int beg = 0, end = znode->child_cnt, mid;
47 : int cmp;
48 55851721955 : const struct ubifs_zbranch *zbr = &znode->zbranch[0];
49 :
50 55851721955 : if (!end) {
51 : /* Different with linux kernel, TNC could become empty. */
52 0 : *n = -1;
53 0 : return 0;
54 : }
55 :
56 55851721955 : ubifs_assert(c, end > beg);
57 :
58 >19107*10^7 : while (end > beg) {
59 >14225*10^7 : mid = (beg + end) >> 1;
60 >14225*10^7 : cmp = keys_cmp(c, key, &zbr[mid].key);
61 : if (cmp > 0)
62 72829694804 : beg = mid + 1;
63 69424269388 : else if (cmp < 0)
64 : end = mid;
65 : else {
66 7029829231 : *n = mid;
67 7029829231 : return 1;
68 : }
69 : }
70 :
71 48821892724 : *n = end - 1;
72 :
73 : /* The insert point is after *n */
74 48821892724 : ubifs_assert(c, *n >= -1 && *n < znode->child_cnt);
75 48821892724 : if (*n == -1)
76 393874766 : ubifs_assert(c, keys_cmp(c, key, &zbr[0].key) < 0);
77 : else
78 48428017958 : ubifs_assert(c, keys_cmp(c, key, &zbr[*n].key) > 0);
79 48821892724 : if (*n + 1 < znode->child_cnt)
80 37467544433 : ubifs_assert(c, keys_cmp(c, key, &zbr[*n + 1].key) < 0);
81 :
82 : return 0;
83 : }
84 :
85 : /**
86 : * ubifs_tnc_postorder_first - find first znode to do postorder tree traversal.
87 : * @znode: znode to start at (root of the sub-tree to traverse)
88 : *
89 : * Find the lowest leftmost znode in a subtree of the TNC tree. The LNC is
90 : * ignored.
91 : */
92 0 : struct ubifs_znode *ubifs_tnc_postorder_first(struct ubifs_znode *znode)
93 : {
94 1933 : if (unlikely(!znode))
95 : return NULL;
96 :
97 567162990 : while (znode->level > 0) {
98 : struct ubifs_znode *child;
99 :
100 111784912 : child = ubifs_tnc_find_child(znode, 0);
101 111784912 : if (!child)
102 : return znode;
103 : znode = child;
104 : }
105 :
106 : return znode;
107 : }
108 :
109 : /**
110 : * ubifs_tnc_postorder_next - next TNC tree element in postorder traversal.
111 : * @c: UBIFS file-system description object
112 : * @znode: previous znode
113 : *
114 : * This function implements postorder TNC traversal. The LNC is ignored.
115 : * Returns the next element or %NULL if @znode is already the last one.
116 : */
117 567161057 : struct ubifs_znode *ubifs_tnc_postorder_next(const struct ubifs_info *c,
118 : struct ubifs_znode *znode)
119 : {
120 : struct ubifs_znode *zn;
121 :
122 567161057 : ubifs_assert(c, znode);
123 567161057 : if (unlikely(!znode->parent))
124 : return NULL;
125 :
126 : /* Switch to the next index in the parent */
127 1134322114 : zn = ubifs_tnc_find_child(znode->parent, znode->iip + 1);
128 567161057 : if (!zn)
129 : /* This is in fact the last child, return parent */
130 : return znode->parent;
131 :
132 : /* Go to the first znode in this new subtree */
133 : return ubifs_tnc_postorder_first(zn);
134 : }
135 :
136 : /**
137 : * ubifs_destroy_tnc_subtree - destroy all znodes connected to a subtree.
138 : * @c: UBIFS file-system description object
139 : * @znode: znode defining subtree to destroy
140 : *
141 : * This function destroys subtree of the TNC tree. Returns number of clean
142 : * znodes in the subtree.
143 : */
144 1933 : long ubifs_destroy_tnc_subtree(const struct ubifs_info *c,
145 : struct ubifs_znode *znode)
146 : {
147 : struct ubifs_znode *zn = ubifs_tnc_postorder_first(znode);
148 : long clean_freed = 0;
149 : int n;
150 :
151 0 : ubifs_assert(c, zn);
152 : while (1) {
153 4190923056 : for (n = 0; n < zn->child_cnt; n++) {
154 3056599009 : if (!zn->zbranch[n].znode)
155 2489102557 : continue;
156 :
157 1134657509 : if (zn->level > 0 &&
158 1134322114 : !ubifs_zn_dirty(zn->zbranch[n].znode))
159 567026874 : clean_freed += 1;
160 :
161 : cond_resched();
162 567496452 : kfree(zn->zbranch[n].znode);
163 : }
164 :
165 567162990 : if (zn == znode) {
166 1933 : if (!ubifs_zn_dirty(zn))
167 1888 : clean_freed += 1;
168 1933 : kfree(zn);
169 1933 : return clean_freed;
170 : }
171 :
172 567161057 : zn = ubifs_tnc_postorder_next(c, zn);
173 : }
174 : }
175 :
176 : /**
177 : * ubifs_destroy_tnc_tree - destroy all znodes connected to the TNC tree.
178 : * @c: UBIFS file-system description object
179 : *
180 : * This function destroys the whole TNC tree and updates clean global znode
181 : * count.
182 : */
183 1951 : void ubifs_destroy_tnc_tree(struct ubifs_info *c)
184 : {
185 : long n, freed;
186 :
187 1951 : if (!c->zroot.znode)
188 : return;
189 :
190 1933 : n = atomic_long_read(&c->clean_zn_cnt);
191 1933 : freed = ubifs_destroy_tnc_subtree(c, c->zroot.znode);
192 1933 : ubifs_assert(c, freed == n);
193 3866 : atomic_long_sub(n, &ubifs_clean_zn_cnt);
194 :
195 1933 : c->zroot.znode = NULL;
196 : }
197 :
198 : /**
199 : * read_znode - read an indexing node from flash and fill znode.
200 : * @c: UBIFS file-system description object
201 : * @zzbr: the zbranch describing the node to read
202 : * @znode: znode to read to
203 : *
204 : * This function reads an indexing node from the flash media and fills znode
205 : * with the read data. Returns zero in case of success and a negative error
206 : * code in case of failure. The read indexing node is validated and if anything
207 : * is wrong with it, this function prints complaint messages and returns
208 : * %-EINVAL.
209 : */
210 567496017 : static int read_znode(struct ubifs_info *c, struct ubifs_zbranch *zzbr,
211 : struct ubifs_znode *znode)
212 : {
213 567496017 : int lnum = zzbr->lnum;
214 567496017 : int offs = zzbr->offs;
215 567496017 : int len = zzbr->len;
216 : int i, err, type, cmp;
217 : struct ubifs_idx_node *idx;
218 :
219 567496017 : idx = kmalloc(c->max_idx_node_sz, GFP_NOFS);
220 567496017 : if (!idx)
221 : return -ENOMEM;
222 :
223 567496017 : err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);
224 567496017 : if (err < 0) {
225 298 : if (test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED))
226 : set_failure_reason_callback(c, FR_TNC_CORRUPTED);
227 298 : kfree(idx);
228 : return err;
229 : }
230 :
231 567495719 : err = ubifs_node_check_hash(c, idx, zzbr->hash);
232 : if (err) {
233 : ubifs_bad_hash(c, idx, zzbr->hash, lnum, offs);
234 : kfree(idx);
235 : return err;
236 : }
237 :
238 567495719 : znode->child_cnt = le16_to_cpu(idx->child_cnt);
239 567495719 : znode->level = le16_to_cpu(idx->level);
240 :
241 567495719 : dbg_tnc("LEB %d:%d, level %d, %d branch",
242 : lnum, offs, znode->level, znode->child_cnt);
243 :
244 567495719 : if (znode->child_cnt > c->fanout || znode->level > UBIFS_MAX_LEVELS) {
245 0 : ubifs_err(c, "current fanout %d, branch count %d",
246 : c->fanout, znode->child_cnt);
247 0 : ubifs_err(c, "max levels %d, znode level %d",
248 : UBIFS_MAX_LEVELS, znode->level);
249 : err = 1;
250 : goto out_dump;
251 : }
252 :
253 3059129393 : for (i = 0; i < znode->child_cnt; i++) {
254 3059129449 : struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);
255 3059129449 : struct ubifs_zbranch *zbr = &znode->zbranch[i];
256 :
257 6118258898 : key_read(c, &br->key, &zbr->key);
258 3059129449 : zbr->lnum = le32_to_cpu(br->lnum);
259 3059129449 : zbr->offs = le32_to_cpu(br->offs);
260 3059129449 : zbr->len = le32_to_cpu(br->len);
261 9177388347 : ubifs_copy_hash(c, ubifs_branch_hash(c, br), zbr->hash);
262 3059129449 : zbr->znode = NULL;
263 :
264 : /* Validate branch */
265 :
266 6118258898 : if (zbr->lnum < c->main_first ||
267 9177388347 : zbr->lnum >= c->leb_cnt || zbr->offs < 0 ||
268 6118258898 : zbr->offs + zbr->len > c->leb_size || zbr->offs & 7) {
269 18 : ubifs_err(c, "bad branch %d", i);
270 : err = 2;
271 : goto out_dump;
272 : }
273 :
274 6118258862 : switch (key_type(c, &zbr->key)) {
275 : case UBIFS_INO_KEY:
276 : case UBIFS_DATA_KEY:
277 : case UBIFS_DENT_KEY:
278 : case UBIFS_XENT_KEY:
279 : break;
280 0 : default:
281 0 : ubifs_err(c, "bad key type at slot %d: %d",
282 : i, key_type(c, &zbr->key));
283 : err = 3;
284 : goto out_dump;
285 : }
286 :
287 3059129431 : if (znode->level)
288 : type = UBIFS_IDX_NODE;
289 : else
290 2491617872 : type = key_type(c, &zbr->key);
291 :
292 3059129431 : if (c->ranges[type].max_len == 0) {
293 0 : if (zbr->len != c->ranges[type].len) {
294 0 : ubifs_err(c, "bad target node (type %d) length (%d)",
295 : type, zbr->len);
296 0 : ubifs_err(c, "have to be %d", c->ranges[type].len);
297 : err = 4;
298 : goto out_dump;
299 : }
300 3059129431 : } else if (zbr->len < c->ranges[type].min_len ||
301 : zbr->len > c->ranges[type].max_len) {
302 38 : ubifs_err(c, "bad target node (type %d) length (%d)",
303 : type, zbr->len);
304 38 : ubifs_err(c, "have to be in range of %d-%d",
305 : c->ranges[type].min_len,
306 : c->ranges[type].max_len);
307 : err = 5;
308 : goto out_dump;
309 : }
310 : }
311 :
312 : /*
313 : * Ensure that the next key is greater or equivalent to the
314 : * previous one.
315 : */
316 3059129239 : for (i = 0; i < znode->child_cnt - 1; i++) {
317 : const union ubifs_key *key1, *key2;
318 :
319 2491633602 : key1 = &znode->zbranch[i].key;
320 2491633602 : key2 = &znode->zbranch[i + 1].key;
321 :
322 2491633602 : cmp = keys_cmp(c, key1, key2);
323 : if (cmp > 0) {
324 26 : ubifs_err(c, "bad key order (keys %d and %d)", i, i + 1);
325 : err = 6;
326 : goto out_dump;
327 2491633576 : } else if (cmp == 0 && !is_hash_key(c, key1)) {
328 : /* These can only be keys with colliding hash */
329 0 : ubifs_err(c, "keys %d and %d are not hashed but equivalent",
330 : i, i + 1);
331 : err = 7;
332 : goto out_dump;
333 : }
334 : }
335 :
336 567495637 : kfree(idx);
337 : return 0;
338 :
339 82 : out_dump:
340 82 : set_failure_reason_callback(c, FR_TNC_CORRUPTED);
341 82 : ubifs_err(c, "bad indexing node at LEB %d:%d, error %d", lnum, offs, err);
342 82 : ubifs_dump_node(c, idx, c->max_idx_node_sz);
343 82 : kfree(idx);
344 : return -EINVAL;
345 : }
346 :
347 : /**
348 : * ubifs_load_znode - load znode to TNC cache.
349 : * @c: UBIFS file-system description object
350 : * @zbr: znode branch
351 : * @parent: znode's parent
352 : * @iip: index in parent
353 : *
354 : * This function loads znode pointed to by @zbr into the TNC cache and
355 : * returns pointer to it in case of success and a negative error code in case
356 : * of failure.
357 : */
358 567496017 : struct ubifs_znode *ubifs_load_znode(struct ubifs_info *c,
359 : struct ubifs_zbranch *zbr,
360 : struct ubifs_znode *parent, int iip)
361 : {
362 : int err;
363 : struct ubifs_znode *znode;
364 :
365 567496017 : ubifs_assert(c, !zbr->znode);
366 : /*
367 : * A slab cache is not presently used for znodes because the znode size
368 : * depends on the fanout which is stored in the superblock.
369 : */
370 1134992034 : znode = kzalloc(c->max_znode_sz, GFP_NOFS);
371 567496017 : if (!znode)
372 : return ERR_PTR(-ENOMEM);
373 :
374 567496017 : err = read_znode(c, zbr, znode);
375 567496017 : if (err)
376 : goto out;
377 :
378 1134991274 : atomic_long_inc(&c->clean_zn_cnt);
379 :
380 : /*
381 : * Increment the global clean znode counter as well. It is OK that
382 : * global and per-FS clean znode counters may be inconsistent for some
383 : * short time (because we might be preempted at this point), the global
384 : * one is only used in shrinker.
385 : */
386 567495637 : atomic_long_inc(&ubifs_clean_zn_cnt);
387 :
388 567495637 : zbr->znode = znode;
389 567495637 : znode->parent = parent;
390 567495637 : znode->time = ktime_get_seconds();
391 567495637 : znode->iip = iip;
392 :
393 567495637 : return znode;
394 :
395 380 : out:
396 380 : kfree(znode);
397 760 : return ERR_PTR(err);
398 : }
399 :
400 : /**
401 : * ubifs_tnc_read_node - read a leaf node from the flash media.
402 : * @c: UBIFS file-system description object
403 : * @zbr: key and position of the node
404 : * @node: node is returned here
405 : *
406 : * This function reads a node defined by @zbr from the flash media. Returns
407 : * zero in case of success or a negative error code in case of failure.
408 : */
409 2491640519 : int ubifs_tnc_read_node(struct ubifs_info *c, struct ubifs_zbranch *zbr,
410 : void *node)
411 : {
412 2491640519 : union ubifs_key key1, *key = &zbr->key;
413 4983281038 : int err, type = key_type(c, key);
414 : struct ubifs_wbuf *wbuf;
415 :
416 : /*
417 : * 'zbr' has to point to on-flash node. The node may sit in a bud and
418 : * may even be in a write buffer, so we have to take care about this.
419 : */
420 2491640519 : wbuf = ubifs_get_wbuf(c, zbr->lnum);
421 2491640519 : if (wbuf)
422 4310261 : err = ubifs_read_node_wbuf(wbuf, node, type, zbr->len,
423 : zbr->lnum, zbr->offs);
424 : else
425 2487330258 : err = ubifs_read_node(c, node, type, zbr->len, zbr->lnum,
426 : zbr->offs);
427 :
428 2491640517 : if (err) {
429 184992 : dbg_tnck(key, "key ");
430 184992 : return err;
431 : }
432 :
433 : /* Make sure the key of the read node is correct */
434 4982911050 : key_read(c, node + UBIFS_KEY_OFFSET, &key1);
435 2491455525 : if (!keys_eq(c, key, &key1)) {
436 18 : set_failure_reason_callback(c, FR_DATA_CORRUPTED);
437 18 : ubifs_err(c, "bad key in node at LEB %d:%d",
438 : zbr->lnum, zbr->offs);
439 18 : dbg_tnck(key, "looked for key ");
440 18 : dbg_tnck(&key1, "but found node's key ");
441 18 : ubifs_dump_node(c, node, zbr->len);
442 18 : return -EINVAL;
443 : }
444 :
445 : err = ubifs_node_check_hash(c, node, zbr->hash);
446 : if (err) {
447 : ubifs_bad_hash(c, node, zbr->hash, zbr->lnum, zbr->offs);
448 : return err;
449 : }
450 :
451 : return 0;
452 : }
|