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 implements TNC (Tree Node Cache) which caches indexing nodes of
13 : * the UBIFS B-tree.
14 : *
15 : * At the moment the locking rules of the TNC tree are quite simple and
16 : * straightforward. We just have a mutex and lock it when we traverse the
17 : * tree. If a znode is not in memory, we read it from flash while still having
18 : * the mutex locked.
19 : */
20 :
21 : #include "linux_err.h"
22 : #include "bitops.h"
23 : #include "kmem.h"
24 : #include "crc32.h"
25 : #include "ubifs.h"
26 : #include "defs.h"
27 : #include "debug.h"
28 : #include "key.h"
29 : #include "misc.h"
30 :
31 : static int try_read_node(const struct ubifs_info *c, void *buf, int type,
32 : struct ubifs_zbranch *zbr);
33 : static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,
34 : struct ubifs_zbranch *zbr, void *node);
35 :
36 : /*
37 : * Returned codes of 'matches_name()' and 'fallible_matches_name()' functions.
38 : * @NAME_LESS: name corresponding to the first argument is less than second
39 : * @NAME_MATCHES: names match
40 : * @NAME_GREATER: name corresponding to the second argument is greater than
41 : * first
42 : * @NOT_ON_MEDIA: node referred by zbranch does not exist on the media
43 : *
44 : * These constants were introduce to improve readability.
45 : */
46 : enum {
47 : NAME_LESS = 0,
48 : NAME_MATCHES = 1,
49 : NAME_GREATER = 2,
50 : NOT_ON_MEDIA = 3,
51 : };
52 :
53 1738207 : static void do_insert_old_idx(struct ubifs_info *c,
54 : struct ubifs_old_idx *old_idx)
55 : {
56 : struct ubifs_old_idx *o;
57 1738207 : struct rb_node **p, *parent = NULL;
58 :
59 1738207 : p = &c->old_idx.rb_node;
60 37207606 : while (*p) {
61 33731192 : parent = *p;
62 33731192 : o = rb_entry(parent, struct ubifs_old_idx, rb);
63 33731192 : if (old_idx->lnum < o->lnum)
64 10360668 : p = &(*p)->rb_left;
65 23370524 : else if (old_idx->lnum > o->lnum)
66 7995386 : p = &(*p)->rb_right;
67 15375138 : else if (old_idx->offs < o->offs)
68 866900 : p = &(*p)->rb_left;
69 14508238 : else if (old_idx->offs > o->offs)
70 14508238 : p = &(*p)->rb_right;
71 : else {
72 0 : ubifs_err(c, "old idx added twice!");
73 : kfree(old_idx);
74 : return;
75 : }
76 : }
77 3476414 : rb_link_node(&old_idx->rb, parent, p);
78 1738207 : rb_insert_color(&old_idx->rb, &c->old_idx);
79 : }
80 :
81 : /**
82 : * insert_old_idx - record an index node obsoleted since the last commit start.
83 : * @c: UBIFS file-system description object
84 : * @lnum: LEB number of obsoleted index node
85 : * @offs: offset of obsoleted index node
86 : *
87 : * Returns %0 on success, and a negative error code on failure.
88 : *
89 : * For recovery, there must always be a complete intact version of the index on
90 : * flash at all times. That is called the "old index". It is the index as at the
91 : * time of the last successful commit. Many of the index nodes in the old index
92 : * may be dirty, but they must not be erased until the next successful commit
93 : * (at which point that index becomes the old index).
94 : *
95 : * That means that the garbage collection and the in-the-gaps method of
96 : * committing must be able to determine if an index node is in the old index.
97 : * Most of the old index nodes can be found by looking up the TNC using the
98 : * 'lookup_znode()' function. However, some of the old index nodes may have
99 : * been deleted from the current index or may have been changed so much that
100 : * they cannot be easily found. In those cases, an entry is added to an RB-tree.
101 : * That is what this function does. The RB-tree is ordered by LEB number and
102 : * offset because they uniquely identify the old index node.
103 : */
104 1738207 : static int insert_old_idx(struct ubifs_info *c, int lnum, int offs)
105 : {
106 : struct ubifs_old_idx *old_idx;
107 :
108 1738207 : old_idx = kmalloc(sizeof(struct ubifs_old_idx), GFP_NOFS);
109 1738207 : if (unlikely(!old_idx))
110 : return -ENOMEM;
111 1738207 : old_idx->lnum = lnum;
112 1738207 : old_idx->offs = offs;
113 1738207 : do_insert_old_idx(c, old_idx);
114 :
115 1738207 : return 0;
116 : }
117 :
118 : /**
119 : * insert_old_idx_znode - record a znode obsoleted since last commit start.
120 : * @c: UBIFS file-system description object
121 : * @znode: znode of obsoleted index node
122 : *
123 : * Returns %0 on success, and a negative error code on failure.
124 : */
125 1770017 : int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode)
126 : {
127 1770017 : if (znode->parent) {
128 : struct ubifs_zbranch *zbr;
129 :
130 1769993 : zbr = &znode->parent->zbranch[znode->iip];
131 1769993 : if (zbr->len)
132 1737971 : return insert_old_idx(c, zbr->lnum, zbr->offs);
133 : } else
134 24 : if (c->zroot.len)
135 24 : return insert_old_idx(c, c->zroot.lnum,
136 : c->zroot.offs);
137 : return 0;
138 : }
139 :
140 : /**
141 : * ins_clr_old_idx_znode - record a znode obsoleted since last commit start.
142 : * @c: UBIFS file-system description object
143 : * @znode: znode of obsoleted index node
144 : *
145 : * Returns %0 on success, and a negative error code on failure.
146 : */
147 12820 : static int ins_clr_old_idx_znode(struct ubifs_info *c,
148 : struct ubifs_znode *znode)
149 : {
150 : int err;
151 :
152 12820 : if (znode->parent) {
153 : struct ubifs_zbranch *zbr;
154 :
155 12820 : zbr = &znode->parent->zbranch[znode->iip];
156 12820 : if (zbr->len) {
157 206 : err = insert_old_idx(c, zbr->lnum, zbr->offs);
158 206 : if (err)
159 : return err;
160 206 : zbr->lnum = 0;
161 206 : zbr->offs = 0;
162 206 : zbr->len = 0;
163 : }
164 : } else
165 0 : if (c->zroot.len) {
166 0 : err = insert_old_idx(c, c->zroot.lnum, c->zroot.offs);
167 0 : if (err)
168 : return err;
169 0 : c->zroot.lnum = 0;
170 0 : c->zroot.offs = 0;
171 0 : c->zroot.len = 0;
172 : }
173 : return 0;
174 : }
175 :
176 : /**
177 : * destroy_old_idx - destroy the old_idx RB-tree.
178 : * @c: UBIFS file-system description object
179 : *
180 : * During start commit, the old_idx RB-tree is used to avoid overwriting index
181 : * nodes that were in the index last commit but have since been deleted. This
182 : * is necessary for recovery i.e. the old index must be kept intact until the
183 : * new index is successfully written. The old-idx RB-tree is used for the
184 : * in-the-gaps method of writing index nodes and is destroyed every commit.
185 : */
186 5378 : void destroy_old_idx(struct ubifs_info *c)
187 : {
188 : struct ubifs_old_idx *old_idx, *n;
189 :
190 1727619 : rbtree_postorder_for_each_entry_safe(old_idx, n, &c->old_idx, rb)
191 1722241 : kfree(old_idx);
192 :
193 5378 : c->old_idx = RB_ROOT;
194 5378 : }
195 :
196 : /**
197 : * copy_znode - copy a dirty znode.
198 : * @c: UBIFS file-system description object
199 : * @znode: znode to copy
200 : *
201 : * A dirty znode being committed may not be changed, so it is copied.
202 : */
203 0 : static struct ubifs_znode *copy_znode(struct ubifs_info *c,
204 : struct ubifs_znode *znode)
205 : {
206 : struct ubifs_znode *zn;
207 :
208 0 : zn = kmemdup(znode, c->max_znode_sz, GFP_NOFS);
209 0 : if (unlikely(!zn))
210 : return ERR_PTR(-ENOMEM);
211 :
212 0 : zn->cnext = NULL;
213 0 : __set_bit(DIRTY_ZNODE, &zn->flags);
214 0 : __clear_bit(COW_ZNODE, &zn->flags);
215 :
216 0 : return zn;
217 : }
218 :
219 : /**
220 : * add_idx_dirt - add dirt due to a dirty znode.
221 : * @c: UBIFS file-system description object
222 : * @lnum: LEB number of index node
223 : * @dirt: size of index node
224 : *
225 : * This function updates lprops dirty space and the new size of the index.
226 : */
227 : static int add_idx_dirt(struct ubifs_info *c, int lnum, int dirt)
228 : {
229 2264334 : c->calc_idx_sz -= ALIGN(dirt, 8);
230 2264334 : return ubifs_add_dirt(c, lnum, dirt);
231 : }
232 :
233 : /**
234 : * replace_znode - replace old znode with new znode.
235 : * @c: UBIFS file-system description object
236 : * @new_zn: new znode
237 : * @old_zn: old znode
238 : * @zbr: the branch of parent znode
239 : *
240 : * Replace old znode with new znode in TNC.
241 : */
242 0 : static void replace_znode(struct ubifs_info *c, struct ubifs_znode *new_zn,
243 : struct ubifs_znode *old_zn, struct ubifs_zbranch *zbr)
244 : {
245 0 : ubifs_assert(c, !ubifs_zn_obsolete(old_zn));
246 0 : __set_bit(OBSOLETE_ZNODE, &old_zn->flags);
247 :
248 0 : if (old_zn->level != 0) {
249 : int i;
250 0 : const int n = new_zn->child_cnt;
251 :
252 : /* The children now have new parent */
253 0 : for (i = 0; i < n; i++) {
254 0 : struct ubifs_zbranch *child = &new_zn->zbranch[i];
255 :
256 0 : if (child->znode)
257 0 : child->znode->parent = new_zn;
258 : }
259 : }
260 :
261 0 : zbr->znode = new_zn;
262 0 : zbr->lnum = 0;
263 0 : zbr->offs = 0;
264 0 : zbr->len = 0;
265 :
266 0 : atomic_long_inc(&c->dirty_zn_cnt);
267 0 : }
268 :
269 : /**
270 : * dirty_cow_znode - ensure a znode is not being committed.
271 : * @c: UBIFS file-system description object
272 : * @zbr: branch of znode to check
273 : *
274 : * Returns dirtied znode on success or negative error code on failure.
275 : */
276 37540205 : static struct ubifs_znode *dirty_cow_znode(struct ubifs_info *c,
277 : struct ubifs_zbranch *zbr)
278 : {
279 37540205 : struct ubifs_znode *znode = zbr->znode;
280 : struct ubifs_znode *zn;
281 : int err;
282 :
283 37540205 : if (!ubifs_zn_cow(znode)) {
284 : /* znode is not being committed */
285 39804539 : if (!test_and_set_bit(DIRTY_ZNODE, &znode->flags)) {
286 4528668 : atomic_long_inc(&c->dirty_zn_cnt);
287 4528668 : atomic_long_dec(&c->clean_zn_cnt);
288 2264334 : atomic_long_dec(&ubifs_clean_zn_cnt);
289 4528668 : err = add_idx_dirt(c, zbr->lnum, zbr->len);
290 2264334 : if (unlikely(err))
291 0 : return ERR_PTR(err);
292 : }
293 : return znode;
294 : }
295 :
296 0 : zn = copy_znode(c, znode);
297 0 : if (IS_ERR(zn))
298 : return zn;
299 :
300 0 : if (zbr->len) {
301 : struct ubifs_old_idx *old_idx;
302 :
303 0 : old_idx = kmalloc(sizeof(struct ubifs_old_idx), GFP_NOFS);
304 0 : if (unlikely(!old_idx)) {
305 : err = -ENOMEM;
306 : goto out;
307 : }
308 0 : old_idx->lnum = zbr->lnum;
309 0 : old_idx->offs = zbr->offs;
310 :
311 0 : err = add_idx_dirt(c, zbr->lnum, zbr->len);
312 0 : if (err) {
313 : kfree(old_idx);
314 : goto out;
315 : }
316 :
317 0 : do_insert_old_idx(c, old_idx);
318 : }
319 :
320 0 : replace_znode(c, zn, znode, zbr);
321 :
322 0 : return zn;
323 :
324 0 : out:
325 0 : kfree(zn);
326 0 : return ERR_PTR(err);
327 : }
328 :
329 : /**
330 : * lnc_add - add a leaf node to the leaf node cache.
331 : * @c: UBIFS file-system description object
332 : * @zbr: zbranch of leaf node
333 : * @node: leaf node
334 : *
335 : * Leaf nodes are non-index nodes directory entry nodes or data nodes. The
336 : * purpose of the leaf node cache is to save re-reading the same leaf node over
337 : * and over again. Most things are cached by VFS, however the file system must
338 : * cache directory entries for readdir and for resolving hash collisions. The
339 : * present implementation of the leaf node cache is extremely simple, and
340 : * allows for error returns that are not used but that may be needed if a more
341 : * complex implementation is created.
342 : *
343 : * Note, this function does not add the @node object to LNC directly, but
344 : * allocates a copy of the object and adds the copy to LNC. The reason for this
345 : * is that @node has been allocated outside of the TNC subsystem and will be
346 : * used with @c->tnc_mutex unlock upon return from the TNC subsystem. But LNC
347 : * may be changed at any time, e.g. freed by the shrinker.
348 : */
349 457 : static int lnc_add(struct ubifs_info *c, struct ubifs_zbranch *zbr,
350 : const void *node)
351 : {
352 : int err;
353 : void *lnc_node;
354 457 : const struct ubifs_dent_node *dent = node;
355 :
356 457 : ubifs_assert(c, !zbr->leaf);
357 457 : ubifs_assert(c, zbr->len != 0);
358 914 : ubifs_assert(c, is_hash_key(c, &zbr->key));
359 :
360 457 : err = ubifs_validate_entry(c, dent);
361 457 : if (err) {
362 0 : dump_stack();
363 0 : ubifs_dump_node(c, dent, zbr->len);
364 0 : return err;
365 : }
366 :
367 457 : lnc_node = kmemdup(node, zbr->len, GFP_NOFS);
368 457 : if (!lnc_node)
369 : /* We don't have to have the cache, so no error */
370 : return 0;
371 :
372 457 : zbr->leaf = lnc_node;
373 457 : return 0;
374 : }
375 :
376 : /**
377 : * lnc_add_directly - add a leaf node to the leaf-node-cache.
378 : * @c: UBIFS file-system description object
379 : * @zbr: zbranch of leaf node
380 : * @node: leaf node
381 : *
382 : * This function is similar to 'lnc_add()', but it does not create a copy of
383 : * @node but inserts @node to TNC directly.
384 : */
385 355867 : static int lnc_add_directly(struct ubifs_info *c, struct ubifs_zbranch *zbr,
386 : void *node)
387 : {
388 : int err;
389 :
390 355867 : ubifs_assert(c, !zbr->leaf);
391 355867 : ubifs_assert(c, zbr->len != 0);
392 :
393 355867 : err = ubifs_validate_entry(c, node);
394 355867 : if (err) {
395 0 : dump_stack();
396 0 : ubifs_dump_node(c, node, zbr->len);
397 : return err;
398 : }
399 :
400 355867 : zbr->leaf = node;
401 : return 0;
402 : }
403 :
404 : /**
405 : * lnc_free - remove a leaf node from the leaf node cache.
406 : * @zbr: zbranch of leaf node
407 : */
408 : static void lnc_free(struct ubifs_zbranch *zbr)
409 : {
410 3559691 : if (!zbr->leaf)
411 : return;
412 37242 : kfree(zbr->leaf);
413 18621 : zbr->leaf = NULL;
414 : }
415 :
416 : /**
417 : * tnc_read_hashed_node - read a "hashed" leaf node.
418 : * @c: UBIFS file-system description object
419 : * @zbr: key and position of the node
420 : * @node: node is returned here
421 : *
422 : * This function reads a "hashed" node defined by @zbr from the leaf node cache
423 : * (in it is there) or from the hash media, in which case the node is also
424 : * added to LNC. Returns zero in case of success or a negative error
425 : * code in case of failure.
426 : */
427 881 : static int tnc_read_hashed_node(struct ubifs_info *c, struct ubifs_zbranch *zbr,
428 : void *node)
429 : {
430 : int err;
431 :
432 1762 : ubifs_assert(c, is_hash_key(c, &zbr->key));
433 :
434 881 : if (zbr->leaf) {
435 : /* Read from the leaf node cache */
436 323 : ubifs_assert(c, zbr->len != 0);
437 323 : memcpy(node, zbr->leaf, zbr->len);
438 323 : return 0;
439 : }
440 :
441 558 : if (c->replaying) {
442 519 : err = fallible_read_node(c, &zbr->key, zbr, node);
443 : /*
444 : * When the node was not found, return -ENOENT, 0 otherwise.
445 : * Negative return codes stay as-is.
446 : */
447 519 : if (err == 0)
448 : err = -ENOENT;
449 418 : else if (err == 1)
450 : err = 0;
451 : } else {
452 39 : err = ubifs_tnc_read_node(c, zbr, node);
453 : }
454 39 : if (err)
455 : return err;
456 :
457 : /* Add the node to the leaf node cache */
458 457 : err = lnc_add(c, zbr, node);
459 457 : return err;
460 : }
461 :
462 : /**
463 : * try_read_node - read a node if it is a node.
464 : * @c: UBIFS file-system description object
465 : * @buf: buffer to read to
466 : * @type: node type
467 : * @zbr: the zbranch describing the node to read
468 : *
469 : * This function tries to read a node of known type and length, checks it and
470 : * stores it in @buf. This function returns %1 if a node is present and %0 if
471 : * a node is not present. A negative error code is returned for I/O errors.
472 : * This function performs that same function as ubifs_read_node except that
473 : * it does not require that there is actually a node present and instead
474 : * the return code indicates if a node was read.
475 : *
476 : * Note, this function does not check CRC of data nodes if @c->no_chk_data_crc
477 : * is true (it is controlled by corresponding mount option). However, if
478 : * @c->mounting or @c->remounting_rw is true (we are mounting or re-mounting to
479 : * R/W mode), @c->no_chk_data_crc is ignored and CRC is checked. This is
480 : * because during mounting or re-mounting from R/O mode to R/W mode we may read
481 : * journal nodes (when replying the journal or doing the recovery) and the
482 : * journal nodes may potentially be corrupted, so checking is required.
483 : */
484 994190 : static int try_read_node(const struct ubifs_info *c, void *buf, int type,
485 : struct ubifs_zbranch *zbr)
486 : {
487 994190 : int len = zbr->len;
488 994190 : int lnum = zbr->lnum;
489 994190 : int offs = zbr->offs;
490 : int err, node_len;
491 994190 : struct ubifs_ch *ch = buf;
492 : uint32_t crc, node_crc;
493 :
494 994190 : dbg_io("LEB %d:%d, %s, length %d", lnum, offs, dbg_ntype(type), len);
495 :
496 994190 : err = ubifs_leb_read(c, lnum, buf, offs, len, 1);
497 994190 : if (err && err != -EBADMSG) {
498 0 : ubifs_err(c, "cannot read node type %d from LEB %d:%d, error %d",
499 : type, lnum, offs, err);
500 : return err;
501 : }
502 :
503 994190 : if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)
504 : return 0;
505 :
506 402346 : if (ch->node_type != type)
507 : return 0;
508 :
509 359708 : node_len = le32_to_cpu(ch->len);
510 359708 : if (node_len != len)
511 : return 0;
512 :
513 359380 : if (type != UBIFS_DATA_NODE || !c->no_chk_data_crc || c->mounting ||
514 : c->remounting_rw) {
515 718760 : crc = crc32(UBIFS_CRC32_INIT, buf + 8, node_len - 8);
516 359380 : node_crc = le32_to_cpu(ch->crc);
517 359380 : if (crc != node_crc)
518 : return 0;
519 : }
520 :
521 359380 : err = ubifs_node_check_hash(c, buf, zbr->hash);
522 : if (err) {
523 : ubifs_bad_hash(c, buf, zbr->hash, lnum, offs);
524 : return 0;
525 : }
526 :
527 : return 1;
528 : }
529 :
530 : /**
531 : * fallible_read_node - try to read a leaf node.
532 : * @c: UBIFS file-system description object
533 : * @key: key of node to read
534 : * @zbr: position of node
535 : * @node: node returned
536 : *
537 : * This function tries to read a node and returns %1 if the node is read, %0
538 : * if the node is not present, and a negative error code in the case of error.
539 : */
540 994190 : static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,
541 : struct ubifs_zbranch *zbr, void *node)
542 : {
543 : int ret;
544 :
545 994190 : dbg_tnck(key, "LEB %d:%d, key ", zbr->lnum, zbr->offs);
546 :
547 1988380 : ret = try_read_node(c, node, key_type(c, key), zbr);
548 994190 : if (ret == 1) {
549 : union ubifs_key node_key;
550 359380 : struct ubifs_dent_node *dent = node;
551 :
552 : /* All nodes have key in the same place */
553 718760 : key_read(c, &dent->key, &node_key);
554 715665 : if (keys_cmp(c, key, &node_key) != 0)
555 3095 : ret = 0;
556 : }
557 991095 : if (ret == 0 && c->replaying)
558 637905 : dbg_mntk(key, "dangling branch LEB %d:%d len %d, key ",
559 : zbr->lnum, zbr->offs, zbr->len);
560 994190 : return ret;
561 : }
562 :
563 : /**
564 : * matches_name - determine if a direntry or xattr entry matches a given name.
565 : * @c: UBIFS file-system description object
566 : * @zbr: zbranch of dent
567 : * @nm: name to match
568 : *
569 : * This function checks if xentry/direntry referred by zbranch @zbr matches name
570 : * @nm. Returns %NAME_MATCHES if it does, %NAME_LESS if the name referred by
571 : * @zbr is less than @nm, and %NAME_GREATER if it is greater than @nm. In case
572 : * of failure, a negative error code is returned.
573 : */
574 0 : static int matches_name(struct ubifs_info *c, struct ubifs_zbranch *zbr,
575 : const struct fscrypt_name *nm)
576 : {
577 : struct ubifs_dent_node *dent;
578 : int nlen, err;
579 :
580 : /* If possible, match against the dent in the leaf node cache */
581 0 : if (!zbr->leaf) {
582 0 : dent = kmalloc(zbr->len, GFP_NOFS);
583 0 : if (!dent)
584 : return -ENOMEM;
585 :
586 0 : err = ubifs_tnc_read_node(c, zbr, dent);
587 0 : if (err)
588 : goto out_free;
589 :
590 : /* Add the node to the leaf node cache */
591 0 : err = lnc_add_directly(c, zbr, dent);
592 0 : if (err)
593 : goto out_free;
594 : } else
595 : dent = zbr->leaf;
596 :
597 0 : nlen = le16_to_cpu(dent->nlen);
598 0 : err = memcmp(dent->name, fname_name(nm), min_t(int, nlen, fname_len(nm)));
599 0 : if (err == 0) {
600 0 : if (nlen == fname_len(nm))
601 : return NAME_MATCHES;
602 0 : else if (nlen < fname_len(nm))
603 : return NAME_LESS;
604 : else
605 0 : return NAME_GREATER;
606 0 : } else if (err < 0)
607 : return NAME_LESS;
608 : else
609 0 : return NAME_GREATER;
610 :
611 0 : out_free:
612 0 : kfree(dent);
613 0 : return err;
614 : }
615 :
616 : /**
617 : * get_znode - get a TNC znode that may not be loaded yet.
618 : * @c: UBIFS file-system description object
619 : * @znode: parent znode
620 : * @n: znode branch slot number
621 : *
622 : * This function returns the znode or a negative error code.
623 : */
624 : static struct ubifs_znode *get_znode(struct ubifs_info *c,
625 : struct ubifs_znode *znode, int n)
626 : {
627 : struct ubifs_zbranch *zbr;
628 :
629 16294335069 : zbr = &znode->zbranch[n];
630 16294335069 : if (zbr->znode)
631 : znode = zbr->znode;
632 : else
633 165528 : znode = ubifs_load_znode(c, zbr, znode, n);
634 : return znode;
635 : }
636 :
637 : /**
638 : * tnc_next - find next TNC entry.
639 : * @c: UBIFS file-system description object
640 : * @zn: znode is passed and returned here
641 : * @n: znode branch slot number is passed and returned here
642 : *
643 : * This function returns %0 if the next TNC entry is found, %-ENOENT if there is
644 : * no next entry, or a negative error code otherwise.
645 : */
646 34970984 : static int tnc_next(struct ubifs_info *c, struct ubifs_znode **zn, int *n)
647 : {
648 34970984 : struct ubifs_znode *znode = *zn;
649 34970984 : int nn = *n;
650 :
651 34970984 : nn += 1;
652 34970984 : if (nn < znode->child_cnt) {
653 27956129 : *n = nn;
654 27956129 : return 0;
655 : }
656 : while (1) {
657 : struct ubifs_znode *zp;
658 :
659 8005354 : zp = znode->parent;
660 8005354 : if (!zp)
661 : return -ENOENT;
662 7999767 : nn = znode->iip + 1;
663 7999767 : znode = zp;
664 7999767 : if (nn < znode->child_cnt) {
665 7009268 : znode = get_znode(c, znode, nn);
666 7009268 : if (IS_ERR(znode))
667 0 : return PTR_ERR(znode);
668 7956457 : while (znode->level != 0) {
669 947189 : znode = get_znode(c, znode, 0);
670 947189 : if (IS_ERR(znode))
671 0 : return PTR_ERR(znode);
672 : }
673 7009268 : nn = 0;
674 : break;
675 : }
676 : }
677 7009268 : *zn = znode;
678 7009268 : *n = nn;
679 7009268 : return 0;
680 : }
681 :
682 : /**
683 : * tnc_prev - find previous TNC entry.
684 : * @c: UBIFS file-system description object
685 : * @zn: znode is returned here
686 : * @n: znode branch slot number is passed and returned here
687 : *
688 : * This function returns %0 if the previous TNC entry is found, %-ENOENT if
689 : * there is no next entry, or a negative error code otherwise.
690 : */
691 52043489 : static int tnc_prev(struct ubifs_info *c, struct ubifs_znode **zn, int *n)
692 : {
693 52043489 : struct ubifs_znode *znode = *zn;
694 52043489 : int nn = *n;
695 :
696 52043489 : if (nn > 0) {
697 27893374 : *n = nn - 1;
698 27893374 : return 0;
699 : }
700 : while (1) {
701 : struct ubifs_znode *zp;
702 :
703 28351110 : zp = znode->parent;
704 28351110 : if (!zp)
705 : return -ENOENT;
706 28349292 : nn = znode->iip - 1;
707 28349292 : znode = zp;
708 28349292 : if (nn >= 0) {
709 24148297 : znode = get_znode(c, znode, nn);
710 24148297 : if (IS_ERR(znode))
711 0 : return PTR_ERR(znode);
712 28340250 : while (znode->level != 0) {
713 4191953 : nn = znode->child_cnt - 1;
714 4191953 : znode = get_znode(c, znode, nn);
715 4191953 : if (IS_ERR(znode))
716 0 : return PTR_ERR(znode);
717 : }
718 24148297 : nn = znode->child_cnt - 1;
719 : break;
720 : }
721 : }
722 24148297 : *zn = znode;
723 24148297 : *n = nn;
724 24148297 : return 0;
725 : }
726 :
727 : /**
728 : * resolve_collision - resolve a collision.
729 : * @c: UBIFS file-system description object
730 : * @key: key of a directory or extended attribute entry
731 : * @zn: znode is returned here
732 : * @n: zbranch number is passed and returned here
733 : * @nm: name of the entry
734 : *
735 : * This function is called for "hashed" keys to make sure that the found key
736 : * really corresponds to the looked up node (directory or extended attribute
737 : * entry). It returns %1 and sets @zn and @n if the collision is resolved.
738 : * %0 is returned if @nm is not found and @zn and @n are set to the previous
739 : * entry, i.e. to the entry after which @nm could follow if it were in TNC.
740 : * This means that @n may be set to %-1 if the leftmost key in @zn is the
741 : * previous one. A negative error code is returned on failures.
742 : */
743 0 : static int resolve_collision(struct ubifs_info *c, const union ubifs_key *key,
744 : struct ubifs_znode **zn, int *n,
745 : const struct fscrypt_name *nm)
746 : {
747 : int err;
748 :
749 0 : err = matches_name(c, &(*zn)->zbranch[*n], nm);
750 0 : if (unlikely(err < 0))
751 : return err;
752 0 : if (err == NAME_MATCHES)
753 : return 1;
754 :
755 0 : if (err == NAME_GREATER) {
756 : /* Look left */
757 : while (1) {
758 0 : err = tnc_prev(c, zn, n);
759 0 : if (err == -ENOENT) {
760 0 : ubifs_assert(c, *n == 0);
761 0 : *n = -1;
762 0 : return 0;
763 : }
764 0 : if (err < 0)
765 : return err;
766 0 : if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {
767 : /*
768 : * We have found the branch after which we would
769 : * like to insert, but inserting in this znode
770 : * may still be wrong. Consider the following 3
771 : * znodes, in the case where we are resolving a
772 : * collision with Key2.
773 : *
774 : * znode zp
775 : * ----------------------
776 : * level 1 | Key0 | Key1 |
777 : * -----------------------
778 : * | |
779 : * znode za | | znode zb
780 : * ------------ ------------
781 : * level 0 | Key0 | | Key2 |
782 : * ------------ ------------
783 : *
784 : * The lookup finds Key2 in znode zb. Lets say
785 : * there is no match and the name is greater so
786 : * we look left. When we find Key0, we end up
787 : * here. If we return now, we will insert into
788 : * znode za at slot n = 1. But that is invalid
789 : * according to the parent's keys. Key2 must
790 : * be inserted into znode zb.
791 : *
792 : * Note, this problem is not relevant for the
793 : * case when we go right, because
794 : * 'tnc_insert()' would correct the parent key.
795 : */
796 0 : if (*n == (*zn)->child_cnt - 1) {
797 0 : err = tnc_next(c, zn, n);
798 0 : if (err) {
799 : /* Should be impossible */
800 0 : ubifs_assert(c, 0);
801 0 : if (err == -ENOENT)
802 0 : err = -EINVAL;
803 : return err;
804 : }
805 0 : ubifs_assert(c, *n == 0);
806 0 : *n = -1;
807 : }
808 : return 0;
809 : }
810 0 : err = matches_name(c, &(*zn)->zbranch[*n], nm);
811 0 : if (err < 0)
812 : return err;
813 0 : if (err == NAME_LESS)
814 : return 0;
815 0 : if (err == NAME_MATCHES)
816 : return 1;
817 0 : ubifs_assert(c, err == NAME_GREATER);
818 : }
819 : } else {
820 0 : int nn = *n;
821 0 : struct ubifs_znode *znode = *zn;
822 :
823 : /* Look right */
824 : while (1) {
825 0 : err = tnc_next(c, &znode, &nn);
826 0 : if (err == -ENOENT)
827 : return 0;
828 0 : if (err < 0)
829 : return err;
830 0 : if (keys_cmp(c, &znode->zbranch[nn].key, key))
831 : return 0;
832 0 : err = matches_name(c, &znode->zbranch[nn], nm);
833 0 : if (err < 0)
834 : return err;
835 0 : if (err == NAME_GREATER)
836 : return 0;
837 0 : *zn = znode;
838 0 : *n = nn;
839 0 : if (err == NAME_MATCHES)
840 : return 1;
841 0 : ubifs_assert(c, err == NAME_LESS);
842 : }
843 : }
844 : }
845 :
846 : /**
847 : * fallible_matches_name - determine if a dent matches a given name.
848 : * @c: UBIFS file-system description object
849 : * @zbr: zbranch of dent
850 : * @nm: name to match
851 : *
852 : * This is a "fallible" version of 'matches_name()' function which does not
853 : * panic if the direntry/xentry referred by @zbr does not exist on the media.
854 : *
855 : * This function checks if xentry/direntry referred by zbranch @zbr matches name
856 : * @nm. Returns %NAME_MATCHES it does, %NAME_LESS if the name referred by @zbr
857 : * is less than @nm, %NAME_GREATER if it is greater than @nm, and @NOT_ON_MEDIA
858 : * if xentry/direntry referred by @zbr does not exist on the media. A negative
859 : * error code is returned in case of failure.
860 : */
861 995487 : static int fallible_matches_name(struct ubifs_info *c,
862 : struct ubifs_zbranch *zbr,
863 : const struct fscrypt_name *nm)
864 : {
865 : struct ubifs_dent_node *dent;
866 : int nlen, err;
867 :
868 : /* If possible, match against the dent in the leaf node cache */
869 995487 : if (!zbr->leaf) {
870 993671 : dent = kmalloc(zbr->len, GFP_NOFS);
871 993671 : if (!dent)
872 : return -ENOMEM;
873 :
874 993671 : err = fallible_read_node(c, &zbr->key, zbr, dent);
875 993671 : if (err < 0)
876 : goto out_free;
877 993671 : if (err == 0) {
878 : /* The node was not present */
879 : err = NOT_ON_MEDIA;
880 : goto out_free;
881 : }
882 355867 : ubifs_assert(c, err == 1);
883 :
884 355867 : err = lnc_add_directly(c, zbr, dent);
885 355867 : if (err)
886 : goto out_free;
887 : } else
888 : dent = zbr->leaf;
889 :
890 357683 : nlen = le16_to_cpu(dent->nlen);
891 357683 : err = memcmp(dent->name, fname_name(nm), min_t(int, nlen, fname_len(nm)));
892 357683 : if (err == 0) {
893 19303 : if (nlen == fname_len(nm))
894 : return NAME_MATCHES;
895 682 : else if (nlen < fname_len(nm))
896 : return NAME_LESS;
897 : else
898 682 : return NAME_GREATER;
899 338380 : } else if (err < 0)
900 : return NAME_LESS;
901 : else
902 338351 : return NAME_GREATER;
903 :
904 0 : out_free:
905 637804 : kfree(dent);
906 637804 : return err;
907 : }
908 :
909 : /**
910 : * fallible_resolve_collision - resolve a collision even if nodes are missing.
911 : * @c: UBIFS file-system description object
912 : * @key: key
913 : * @zn: znode is returned here
914 : * @n: branch number is passed and returned here
915 : * @nm: name of directory entry
916 : * @adding: indicates caller is adding a key to the TNC
917 : *
918 : * This is a "fallible" version of the 'resolve_collision()' function which
919 : * does not panic if one of the nodes referred to by TNC does not exist on the
920 : * media. This may happen when replaying the journal if a deleted node was
921 : * Garbage-collected and the commit was not done. A branch that refers to a node
922 : * that is not present is called a dangling branch. The following are the return
923 : * codes for this function:
924 : * o if @nm was found, %1 is returned and @zn and @n are set to the found
925 : * branch;
926 : * o if we are @adding and @nm was not found, %0 is returned;
927 : * o if we are not @adding and @nm was not found, but a dangling branch was
928 : * found, then %1 is returned and @zn and @n are set to the dangling branch;
929 : * o a negative error code is returned in case of failure.
930 : */
931 676677 : static int fallible_resolve_collision(struct ubifs_info *c,
932 : const union ubifs_key *key,
933 : struct ubifs_znode **zn, int *n,
934 : const struct fscrypt_name *nm,
935 : int adding)
936 : {
937 676677 : struct ubifs_znode *o_znode = NULL, *znode = *zn;
938 676677 : int err, cmp, o_n = 0, unsure = 0, nn = *n;
939 :
940 676677 : cmp = fallible_matches_name(c, &znode->zbranch[nn], nm);
941 676677 : if (unlikely(cmp < 0))
942 : return cmp;
943 676677 : if (cmp == NAME_MATCHES)
944 : return 1;
945 658056 : if (cmp == NOT_ON_MEDIA) {
946 430410 : o_znode = znode;
947 430410 : o_n = nn;
948 : /*
949 : * We are unlucky and hit a dangling branch straight away.
950 : * Now we do not really know where to go to find the needed
951 : * branch - to the left or to the right. Well, let's try left.
952 : */
953 430410 : unsure = 1;
954 227646 : } else if (!adding)
955 227646 : unsure = 1; /* Remove a dangling branch wherever it is */
956 :
957 658056 : if (cmp == NAME_GREATER || unsure) {
958 : /* Look left */
959 : while (1) {
960 865450 : err = tnc_prev(c, zn, n);
961 865450 : if (err == -ENOENT) {
962 0 : ubifs_assert(c, *n == 0);
963 0 : *n = -1;
964 0 : break;
965 : }
966 865450 : if (err < 0)
967 : return err;
968 1072844 : if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {
969 : /* See comments in 'resolve_collision()' */
970 658056 : if (*n == (*zn)->child_cnt - 1) {
971 157876 : err = tnc_next(c, zn, n);
972 157876 : if (err) {
973 : /* Should be impossible */
974 0 : ubifs_assert(c, 0);
975 0 : if (err == -ENOENT)
976 0 : err = -EINVAL;
977 : return err;
978 : }
979 157876 : ubifs_assert(c, *n == 0);
980 157876 : *n = -1;
981 : }
982 : break;
983 : }
984 207394 : err = fallible_matches_name(c, &(*zn)->zbranch[*n], nm);
985 207394 : if (err < 0)
986 : return err;
987 207394 : if (err == NAME_MATCHES)
988 : return 1;
989 207394 : if (err == NOT_ON_MEDIA) {
990 207394 : o_znode = *zn;
991 207394 : o_n = *n;
992 207394 : continue;
993 : }
994 0 : if (!adding)
995 0 : continue;
996 0 : if (err == NAME_LESS)
997 : break;
998 : else
999 : unsure = 0;
1000 : }
1001 : }
1002 :
1003 658056 : if (cmp == NAME_LESS || unsure) {
1004 : /* Look right */
1005 658056 : *zn = znode;
1006 658056 : *n = nn;
1007 : while (1) {
1008 658056 : err = tnc_next(c, &znode, &nn);
1009 658056 : if (err == -ENOENT)
1010 : break;
1011 654292 : if (err < 0)
1012 : return err;
1013 765708 : if (keys_cmp(c, &znode->zbranch[nn].key, key))
1014 : break;
1015 111416 : err = fallible_matches_name(c, &znode->zbranch[nn], nm);
1016 111416 : if (err < 0)
1017 : return err;
1018 111416 : if (err == NAME_GREATER)
1019 : break;
1020 0 : *zn = znode;
1021 0 : *n = nn;
1022 0 : if (err == NAME_MATCHES)
1023 : return 1;
1024 0 : if (err == NOT_ON_MEDIA) {
1025 0 : o_znode = znode;
1026 0 : o_n = nn;
1027 : }
1028 : }
1029 : }
1030 :
1031 : /* Never match a dangling branch when adding */
1032 658056 : if (adding || !o_znode)
1033 : return 0;
1034 :
1035 318994 : dbg_mntk(key, "dangling match LEB %d:%d len %d key ",
1036 : o_znode->zbranch[o_n].lnum, o_znode->zbranch[o_n].offs,
1037 : o_znode->zbranch[o_n].len);
1038 318994 : *zn = o_znode;
1039 318994 : *n = o_n;
1040 318994 : return 1;
1041 : }
1042 :
1043 : /**
1044 : * matches_position - determine if a zbranch matches a given position.
1045 : * @zbr: zbranch of dent
1046 : * @lnum: LEB number of dent to match
1047 : * @offs: offset of dent to match
1048 : *
1049 : * This function returns %1 if @lnum:@offs matches, and %0 otherwise.
1050 : */
1051 : static int matches_position(struct ubifs_zbranch *zbr, int lnum, int offs)
1052 : {
1053 0 : if (zbr->lnum == lnum && zbr->offs == offs)
1054 : return 1;
1055 : else
1056 : return 0;
1057 : }
1058 :
1059 : /**
1060 : * resolve_collision_directly - resolve a collision directly.
1061 : * @c: UBIFS file-system description object
1062 : * @key: key of directory entry
1063 : * @zn: znode is passed and returned here
1064 : * @n: zbranch number is passed and returned here
1065 : * @lnum: LEB number of dent node to match
1066 : * @offs: offset of dent node to match
1067 : *
1068 : * This function is used for "hashed" keys to make sure the found directory or
1069 : * extended attribute entry node is what was looked for. It is used when the
1070 : * flash address of the right node is known (@lnum:@offs) which makes it much
1071 : * easier to resolve collisions (no need to read entries and match full
1072 : * names). This function returns %1 and sets @zn and @n if the collision is
1073 : * resolved, %0 if @lnum:@offs is not found and @zn and @n are set to the
1074 : * previous directory entry. Otherwise a negative error code is returned.
1075 : */
1076 0 : static int resolve_collision_directly(struct ubifs_info *c,
1077 : const union ubifs_key *key,
1078 : struct ubifs_znode **zn, int *n,
1079 : int lnum, int offs)
1080 : {
1081 : struct ubifs_znode *znode;
1082 : int nn, err;
1083 :
1084 0 : znode = *zn;
1085 0 : nn = *n;
1086 0 : if (matches_position(&znode->zbranch[nn], lnum, offs))
1087 : return 1;
1088 :
1089 : /* Look left */
1090 : while (1) {
1091 0 : err = tnc_prev(c, &znode, &nn);
1092 0 : if (err == -ENOENT)
1093 : break;
1094 0 : if (err < 0)
1095 : return err;
1096 0 : if (keys_cmp(c, &znode->zbranch[nn].key, key))
1097 : break;
1098 0 : if (matches_position(&znode->zbranch[nn], lnum, offs)) {
1099 0 : *zn = znode;
1100 0 : *n = nn;
1101 0 : return 1;
1102 : }
1103 : }
1104 :
1105 : /* Look right */
1106 0 : znode = *zn;
1107 0 : nn = *n;
1108 : while (1) {
1109 0 : err = tnc_next(c, &znode, &nn);
1110 0 : if (err == -ENOENT)
1111 : return 0;
1112 0 : if (err < 0)
1113 : return err;
1114 0 : if (keys_cmp(c, &znode->zbranch[nn].key, key))
1115 : return 0;
1116 0 : *zn = znode;
1117 0 : *n = nn;
1118 0 : if (matches_position(&znode->zbranch[nn], lnum, offs))
1119 : return 1;
1120 : }
1121 : }
1122 :
1123 : /**
1124 : * dirty_cow_bottom_up - dirty a znode and its ancestors.
1125 : * @c: UBIFS file-system description object
1126 : * @znode: znode to dirty
1127 : *
1128 : * If we do not have a unique key that resides in a znode, then we cannot
1129 : * dirty that znode from the top down (i.e. by using lookup_level0_dirty)
1130 : * This function records the path back to the last dirty ancestor, and then
1131 : * dirties the znodes on that path.
1132 : */
1133 31437 : static struct ubifs_znode *dirty_cow_bottom_up(struct ubifs_info *c,
1134 : struct ubifs_znode *znode)
1135 : {
1136 : struct ubifs_znode *zp;
1137 31437 : int *path = c->bottom_up_buf, p = 0;
1138 :
1139 31437 : ubifs_assert(c, c->zroot.znode);
1140 31437 : ubifs_assert(c, znode);
1141 31437 : if (c->zroot.znode->level > BOTTOM_UP_HEIGHT) {
1142 0 : kfree(c->bottom_up_buf);
1143 0 : c->bottom_up_buf = kmalloc_array(c->zroot.znode->level,
1144 : sizeof(int),
1145 : GFP_NOFS);
1146 0 : if (!c->bottom_up_buf)
1147 : return ERR_PTR(-ENOMEM);
1148 : path = c->bottom_up_buf;
1149 : }
1150 31437 : if (c->zroot.znode->level) {
1151 : /* Go up until parent is dirty */
1152 : while (1) {
1153 : int n;
1154 :
1155 70845 : zp = znode->parent;
1156 70845 : if (!zp)
1157 : break;
1158 70777 : n = znode->iip;
1159 70777 : ubifs_assert(c, p < c->zroot.znode->level);
1160 70777 : path[p++] = n;
1161 141554 : if (!zp->cnext && ubifs_zn_dirty(znode))
1162 : break;
1163 : znode = zp;
1164 : }
1165 : }
1166 :
1167 : /* Come back down, dirtying as we go */
1168 39408 : while (1) {
1169 : struct ubifs_zbranch *zbr;
1170 :
1171 70845 : zp = znode->parent;
1172 70845 : if (zp) {
1173 70777 : ubifs_assert(c, path[p - 1] >= 0);
1174 70777 : ubifs_assert(c, path[p - 1] < zp->child_cnt);
1175 70777 : zbr = &zp->zbranch[path[--p]];
1176 70777 : znode = dirty_cow_znode(c, zbr);
1177 : } else {
1178 68 : ubifs_assert(c, znode == c->zroot.znode);
1179 68 : znode = dirty_cow_znode(c, &c->zroot);
1180 : }
1181 70845 : if (IS_ERR(znode) || !p)
1182 : break;
1183 39408 : ubifs_assert(c, path[p - 1] >= 0);
1184 39408 : ubifs_assert(c, path[p - 1] < znode->child_cnt);
1185 39408 : znode = znode->zbranch[path[p - 1]].znode;
1186 : }
1187 :
1188 : return znode;
1189 : }
1190 :
1191 : /**
1192 : * ubifs_lookup_level0 - search for zero-level znode.
1193 : * @c: UBIFS file-system description object
1194 : * @key: key to lookup
1195 : * @zn: znode is returned here
1196 : * @n: znode branch slot number is returned here
1197 : *
1198 : * This function looks up the TNC tree and search for zero-level znode which
1199 : * refers key @key. The found zero-level znode is returned in @zn. There are 3
1200 : * cases:
1201 : * o exact match, i.e. the found zero-level znode contains key @key, then %1
1202 : * is returned and slot number of the matched branch is stored in @n;
1203 : * o not exact match, which means that zero-level znode does not contain
1204 : * @key, then %0 is returned and slot number of the closest branch or %-1
1205 : * is stored in @n; In this case calling tnc_next() is mandatory.
1206 : * o @key is so small that it is even less than the lowest key of the
1207 : * leftmost zero-level node, then %0 is returned and %0 is stored in @n.
1208 : *
1209 : * Note, when the TNC tree is traversed, some znodes may be absent, then this
1210 : * function reads corresponding indexing nodes and inserts them to TNC. In
1211 : * case of failure, a negative error code is returned.
1212 : */
1213 3922941336 : int ubifs_lookup_level0(struct ubifs_info *c, const union ubifs_key *key,
1214 : struct ubifs_znode **zn, int *n)
1215 : {
1216 : int err, exact;
1217 : struct ubifs_znode *znode;
1218 3922941336 : time64_t time = ktime_get_seconds();
1219 :
1220 3922941336 : dbg_tnck(key, "search key ");
1221 7845882672 : ubifs_assert(c, key_type(c, key) < UBIFS_INVALID_KEY);
1222 :
1223 3922941336 : znode = c->zroot.znode;
1224 3922941336 : if (unlikely(!znode)) {
1225 1 : znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
1226 2 : if (IS_ERR(znode))
1227 0 : return PTR_ERR(znode);
1228 : }
1229 :
1230 3922941336 : znode->time = time;
1231 :
1232 : while (1) {
1233 : struct ubifs_zbranch *zbr;
1234 :
1235 37930607858 : exact = ubifs_search_zbranch(c, znode, key, n);
1236 :
1237 37930607858 : if (znode->level == 0)
1238 : break;
1239 :
1240 34007666522 : if (*n < 0)
1241 212673895 : *n = 0;
1242 34007666522 : zbr = &znode->zbranch[*n];
1243 :
1244 34007666522 : if (zbr->znode) {
1245 34007546935 : znode->time = time;
1246 34007546935 : znode = zbr->znode;
1247 34007546935 : continue;
1248 : }
1249 :
1250 : /* znode is not in TNC cache, load it from the media */
1251 119587 : znode = ubifs_load_znode(c, zbr, znode, *n);
1252 239174 : if (IS_ERR(znode))
1253 0 : return PTR_ERR(znode);
1254 : }
1255 :
1256 3922941336 : *zn = znode;
1257 4666526886 : if (exact || !is_hash_key(c, key) || *n != -1) {
1258 3905872132 : dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n);
1259 : return exact;
1260 : }
1261 :
1262 : /*
1263 : * Here is a tricky place. We have not found the key and this is a
1264 : * "hashed" key, which may collide. The rest of the code deals with
1265 : * situations like this:
1266 : *
1267 : * | 3 | 5 |
1268 : * / \
1269 : * | 3 | 5 | | 6 | 7 | (x)
1270 : *
1271 : * Or more a complex example:
1272 : *
1273 : * | 1 | 5 |
1274 : * / \
1275 : * | 1 | 3 | | 5 | 8 |
1276 : * \ /
1277 : * | 5 | 5 | | 6 | 7 | (x)
1278 : *
1279 : * In the examples, if we are looking for key "5", we may reach nodes
1280 : * marked with "(x)". In this case what we have do is to look at the
1281 : * left and see if there is "5" key there. If there is, we have to
1282 : * return it.
1283 : *
1284 : * Note, this whole situation is possible because we allow to have
1285 : * elements which are equivalent to the next key in the parent in the
1286 : * children of current znode. For example, this happens if we split a
1287 : * znode like this: | 3 | 5 | 5 | 6 | 7 |, which results in something
1288 : * like this:
1289 : * | 3 | 5 |
1290 : * / \
1291 : * | 3 | 5 | | 5 | 6 | 7 |
1292 : * ^
1293 : * And this becomes what is at the first "picture" after key "5" marked
1294 : * with "^" is removed. What could be done is we could prohibit
1295 : * splitting in the middle of the colliding sequence. Also, when
1296 : * removing the leftmost key, we would have to correct the key of the
1297 : * parent node, which would introduce additional complications. Namely,
1298 : * if we changed the leftmost key of the parent znode, the garbage
1299 : * collector would be unable to find it (GC is doing this when GC'ing
1300 : * indexing LEBs). Although we already have an additional RB-tree where
1301 : * we save such changed znodes (see 'ins_clr_old_idx_znode()') until
1302 : * after the commit. But anyway, this does not look easy to implement
1303 : * so we did not try this.
1304 : */
1305 17069204 : err = tnc_prev(c, &znode, n);
1306 17069204 : if (err == -ENOENT) {
1307 1818 : dbg_tnc("found 0, lvl %d, n -1", znode->level);
1308 1818 : *n = -1;
1309 1818 : return 0;
1310 : }
1311 17067386 : if (unlikely(err < 0))
1312 : return err;
1313 17067386 : if (keys_cmp(c, key, &znode->zbranch[*n].key)) {
1314 17067386 : dbg_tnc("found 0, lvl %d, n -1", znode->level);
1315 17067386 : *n = -1;
1316 17067386 : return 0;
1317 : }
1318 :
1319 0 : dbg_tnc("found 1, lvl %d, n %d", znode->level, *n);
1320 0 : *zn = znode;
1321 0 : return 1;
1322 : }
1323 :
1324 : /**
1325 : * lookup_level0_dirty - search for zero-level znode dirtying.
1326 : * @c: UBIFS file-system description object
1327 : * @key: key to lookup
1328 : * @zn: znode is returned here
1329 : * @n: znode branch slot number is returned here
1330 : *
1331 : * This function looks up the TNC tree and search for zero-level znode which
1332 : * refers key @key. The found zero-level znode is returned in @zn. There are 3
1333 : * cases:
1334 : * o exact match, i.e. the found zero-level znode contains key @key, then %1
1335 : * is returned and slot number of the matched branch is stored in @n;
1336 : * o not exact match, which means that zero-level znode does not contain @key
1337 : * then %0 is returned and slot number of the closed branch is stored in
1338 : * @n;
1339 : * o @key is so small that it is even less than the lowest key of the
1340 : * leftmost zero-level node, then %0 is returned and %-1 is stored in @n.
1341 : *
1342 : * Additionally all znodes in the path from the root to the located zero-level
1343 : * znode are marked as dirty.
1344 : *
1345 : * Note, when the TNC tree is traversed, some znodes may be absent, then this
1346 : * function reads corresponding indexing nodes and inserts them to TNC. In
1347 : * case of failure, a negative error code is returned.
1348 : */
1349 3887467 : static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key,
1350 : struct ubifs_znode **zn, int *n)
1351 : {
1352 : int err, exact;
1353 : struct ubifs_znode *znode;
1354 3887467 : time64_t time = ktime_get_seconds();
1355 :
1356 3887467 : dbg_tnck(key, "search and dirty key ");
1357 :
1358 3887467 : znode = c->zroot.znode;
1359 3887467 : if (unlikely(!znode)) {
1360 535 : znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
1361 1070 : if (IS_ERR(znode))
1362 0 : return PTR_ERR(znode);
1363 : }
1364 :
1365 3887467 : znode = dirty_cow_znode(c, &c->zroot);
1366 7774934 : if (IS_ERR(znode))
1367 0 : return PTR_ERR(znode);
1368 :
1369 3887467 : znode->time = time;
1370 :
1371 : while (1) {
1372 : struct ubifs_zbranch *zbr;
1373 :
1374 37469354 : exact = ubifs_search_zbranch(c, znode, key, n);
1375 :
1376 37469354 : if (znode->level == 0)
1377 : break;
1378 :
1379 33581915 : if (*n < 0)
1380 287 : *n = 0;
1381 33581915 : zbr = &znode->zbranch[*n];
1382 :
1383 33581915 : if (zbr->znode) {
1384 31659043 : znode->time = time;
1385 31659043 : znode = dirty_cow_znode(c, zbr);
1386 63318086 : if (IS_ERR(znode))
1387 0 : return PTR_ERR(znode);
1388 31659043 : continue;
1389 : }
1390 :
1391 : /* znode is not in TNC cache, load it from the media */
1392 1922872 : znode = ubifs_load_znode(c, zbr, znode, *n);
1393 3845744 : if (IS_ERR(znode))
1394 56 : return PTR_ERR(znode);
1395 1922844 : znode = dirty_cow_znode(c, zbr);
1396 3845688 : if (IS_ERR(znode))
1397 0 : return PTR_ERR(znode);
1398 : }
1399 :
1400 3887439 : *zn = znode;
1401 4119961 : if (exact || !is_hash_key(c, key) || *n != -1) {
1402 3886927 : dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n);
1403 : return exact;
1404 : }
1405 :
1406 : /*
1407 : * See huge comment at 'lookup_level0_dirty()' what is the rest of the
1408 : * code.
1409 : */
1410 512 : err = tnc_prev(c, &znode, n);
1411 512 : if (err == -ENOENT) {
1412 0 : *n = -1;
1413 0 : dbg_tnc("found 0, lvl %d, n -1", znode->level);
1414 : return 0;
1415 : }
1416 512 : if (unlikely(err < 0))
1417 : return err;
1418 512 : if (keys_cmp(c, key, &znode->zbranch[*n].key)) {
1419 512 : *n = -1;
1420 512 : dbg_tnc("found 0, lvl %d, n -1", znode->level);
1421 : return 0;
1422 : }
1423 :
1424 0 : if (znode->cnext || !ubifs_zn_dirty(znode)) {
1425 0 : znode = dirty_cow_bottom_up(c, znode);
1426 0 : if (IS_ERR(znode))
1427 0 : return PTR_ERR(znode);
1428 : }
1429 :
1430 0 : dbg_tnc("found 1, lvl %d, n %d", znode->level, *n);
1431 0 : *zn = znode;
1432 0 : return 1;
1433 : }
1434 :
1435 : /**
1436 : * ubifs_tnc_locate - look up a file-system node and return it and its location.
1437 : * @c: UBIFS file-system description object
1438 : * @key: node key to lookup
1439 : * @node: the node is returned here
1440 : * @lnum: LEB number is returned here
1441 : * @offs: offset is returned here
1442 : *
1443 : * This function looks up and reads node with key @key. The caller has to make
1444 : * sure the @node buffer is large enough to fit the node. Returns zero in case
1445 : * of success, %-ENOENT if the node was not found, and a negative error code in
1446 : * case of failure. The node location can be returned in @lnum and @offs.
1447 : */
1448 82687 : int ubifs_tnc_locate(struct ubifs_info *c, const union ubifs_key *key,
1449 : void *node, int *lnum, int *offs)
1450 : {
1451 : int found, n, err;
1452 : struct ubifs_znode *znode;
1453 : struct ubifs_zbranch *zt;
1454 :
1455 82687 : mutex_lock(&c->tnc_mutex);
1456 82687 : found = ubifs_lookup_level0(c, key, &znode, &n);
1457 82687 : if (!found) {
1458 : err = -ENOENT;
1459 : goto out;
1460 81910 : } else if (found < 0) {
1461 : err = found;
1462 : goto out;
1463 : }
1464 81910 : zt = &znode->zbranch[n];
1465 81910 : if (lnum) {
1466 53 : *lnum = zt->lnum;
1467 53 : *offs = zt->offs;
1468 : }
1469 163820 : if (is_hash_key(c, key)) {
1470 : /*
1471 : * In this case the leaf node cache gets used, so we pass the
1472 : * address of the zbranch and keep the mutex locked
1473 : */
1474 39 : err = tnc_read_hashed_node(c, zt, node);
1475 39 : goto out;
1476 : }
1477 81871 : err = ubifs_tnc_read_node(c, zt, node);
1478 :
1479 82687 : out:
1480 82687 : mutex_unlock(&c->tnc_mutex);
1481 82687 : return err;
1482 : }
1483 :
1484 : /**
1485 : * do_lookup_nm- look up a "hashed" node.
1486 : * @c: UBIFS file-system description object
1487 : * @key: node key to lookup
1488 : * @node: the node is returned here
1489 : * @nm: node name
1490 : *
1491 : * This function looks up and reads a node which contains name hash in the key.
1492 : * Since the hash may have collisions, there may be many nodes with the same
1493 : * key, so we have to sequentially look to all of them until the needed one is
1494 : * found. This function returns zero in case of success, %-ENOENT if the node
1495 : * was not found, and a negative error code in case of failure.
1496 : */
1497 0 : static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
1498 : void *node, const struct fscrypt_name *nm)
1499 : {
1500 : int found, n, err;
1501 : struct ubifs_znode *znode;
1502 :
1503 0 : dbg_tnck(key, "key ");
1504 0 : mutex_lock(&c->tnc_mutex);
1505 0 : found = ubifs_lookup_level0(c, key, &znode, &n);
1506 0 : if (!found) {
1507 : err = -ENOENT;
1508 : goto out_unlock;
1509 0 : } else if (found < 0) {
1510 : err = found;
1511 : goto out_unlock;
1512 : }
1513 :
1514 0 : ubifs_assert(c, n >= 0);
1515 :
1516 0 : err = resolve_collision(c, key, &znode, &n, nm);
1517 0 : dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);
1518 0 : if (unlikely(err < 0))
1519 : goto out_unlock;
1520 0 : if (err == 0) {
1521 : err = -ENOENT;
1522 : goto out_unlock;
1523 : }
1524 :
1525 0 : err = tnc_read_hashed_node(c, &znode->zbranch[n], node);
1526 :
1527 0 : out_unlock:
1528 0 : mutex_unlock(&c->tnc_mutex);
1529 0 : return err;
1530 : }
1531 :
1532 : /**
1533 : * ubifs_tnc_lookup_nm - look up a "hashed" node.
1534 : * @c: UBIFS file-system description object
1535 : * @key: node key to lookup
1536 : * @node: the node is returned here
1537 : * @nm: node name
1538 : *
1539 : * This function looks up and reads a node which contains name hash in the key.
1540 : * Since the hash may have collisions, there may be many nodes with the same
1541 : * key, so we have to sequentially look to all of them until the needed one is
1542 : * found. This function returns zero in case of success, %-ENOENT if the node
1543 : * was not found, and a negative error code in case of failure.
1544 : */
1545 271 : int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
1546 : void *node, const struct fscrypt_name *nm)
1547 : {
1548 : int err, len;
1549 271 : const struct ubifs_dent_node *dent = node;
1550 :
1551 : /*
1552 : * We assume that in most of the cases there are no name collisions and
1553 : * 'ubifs_tnc_lookup()' returns us the right direntry.
1554 : */
1555 271 : err = ubifs_tnc_lookup(c, key, node);
1556 271 : if (err)
1557 : return err;
1558 :
1559 39 : len = le16_to_cpu(dent->nlen);
1560 39 : if (fname_len(nm) == len && !memcmp(dent->name, fname_name(nm), len))
1561 : return 0;
1562 :
1563 : /*
1564 : * Unluckily, there are hash collisions and we have to iterate over
1565 : * them look at each direntry with colliding name hash sequentially.
1566 : */
1567 :
1568 0 : return do_lookup_nm(c, key, node, nm);
1569 : }
1570 :
1571 : /**
1572 : * correct_parent_keys - correct parent znodes' keys.
1573 : * @c: UBIFS file-system description object
1574 : * @znode: znode to correct parent znodes for
1575 : *
1576 : * This is a helper function for 'tnc_insert()'. When the key of the leftmost
1577 : * zbranch changes, keys of parent znodes have to be corrected. This helper
1578 : * function is called in such situations and corrects the keys if needed.
1579 : */
1580 589 : static void correct_parent_keys(const struct ubifs_info *c,
1581 : struct ubifs_znode *znode)
1582 : {
1583 : union ubifs_key *key, *key1;
1584 :
1585 589 : ubifs_assert(c, znode->parent);
1586 589 : ubifs_assert(c, znode->iip == 0);
1587 :
1588 589 : key = &znode->zbranch[0].key;
1589 589 : key1 = &znode->parent->zbranch[0].key;
1590 :
1591 1304 : while (keys_cmp(c, key, key1) < 0) {
1592 566 : key_copy(c, key, key1);
1593 283 : znode = znode->parent;
1594 283 : znode->alt = 1;
1595 283 : if (!znode->parent || znode->iip)
1596 : break;
1597 126 : key1 = &znode->parent->zbranch[0].key;
1598 : }
1599 589 : }
1600 :
1601 : /**
1602 : * insert_zbranch - insert a zbranch into a znode.
1603 : * @c: UBIFS file-system description object
1604 : * @znode: znode into which to insert
1605 : * @zbr: zbranch to insert
1606 : * @n: slot number to insert to
1607 : *
1608 : * This is a helper function for 'tnc_insert()'. UBIFS does not allow "gaps" in
1609 : * znode's array of zbranches and keeps zbranches consolidated, so when a new
1610 : * zbranch has to be inserted to the @znode->zbranches[]' array at the @n-th
1611 : * slot, zbranches starting from @n have to be moved right.
1612 : */
1613 624633 : static void insert_zbranch(struct ubifs_info *c, struct ubifs_znode *znode,
1614 : const struct ubifs_zbranch *zbr, int n)
1615 : {
1616 : int i;
1617 :
1618 624633 : ubifs_assert(c, ubifs_zn_dirty(znode));
1619 :
1620 624633 : if (znode->level) {
1621 267405 : for (i = znode->child_cnt; i > n; i--) {
1622 119379 : znode->zbranch[i] = znode->zbranch[i - 1];
1623 119379 : if (znode->zbranch[i].znode)
1624 18945 : znode->zbranch[i].znode->iip = i;
1625 : }
1626 74013 : if (zbr->znode)
1627 74013 : zbr->znode->iip = n;
1628 : } else
1629 1339160 : for (i = znode->child_cnt; i > n; i--)
1630 788540 : znode->zbranch[i] = znode->zbranch[i - 1];
1631 :
1632 624633 : znode->zbranch[n] = *zbr;
1633 624633 : znode->child_cnt += 1;
1634 :
1635 : /*
1636 : * After inserting at slot zero, the lower bound of the key range of
1637 : * this znode may have changed. If this znode is subsequently split
1638 : * then the upper bound of the key range may change, and furthermore
1639 : * it could change to be lower than the original lower bound. If that
1640 : * happens, then it will no longer be possible to find this znode in the
1641 : * TNC using the key from the index node on flash. That is bad because
1642 : * if it is not found, we will assume it is obsolete and may overwrite
1643 : * it. Then if there is an unclean unmount, we will start using the
1644 : * old index which will be broken.
1645 : *
1646 : * So we first mark znodes that have insertions at slot zero, and then
1647 : * if they are split we add their lnum/offs to the old_idx tree.
1648 : */
1649 624633 : if (n == 0)
1650 24314 : znode->alt = 1;
1651 624633 : }
1652 :
1653 : /**
1654 : * tnc_insert - insert a node into TNC.
1655 : * @c: UBIFS file-system description object
1656 : * @znode: znode to insert into
1657 : * @zbr: branch to insert
1658 : * @n: slot number to insert new zbranch to
1659 : *
1660 : * This function inserts a new node described by @zbr into znode @znode. If
1661 : * znode does not have a free slot for new zbranch, it is split. Parent znodes
1662 : * are splat as well if needed. Returns zero in case of success or a negative
1663 : * error code in case of failure.
1664 : */
1665 550620 : static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode,
1666 : struct ubifs_zbranch *zbr, int n)
1667 : {
1668 : struct ubifs_znode *zn, *zi, *zp;
1669 550620 : int i, keep, move, appending = 0;
1670 550620 : union ubifs_key *key = &zbr->key, *key1;
1671 :
1672 550620 : ubifs_assert(c, n >= 0 && n <= c->fanout);
1673 :
1674 : /* Implement naive insert for now */
1675 550620 : again:
1676 624633 : zp = znode->parent;
1677 624633 : if (znode->child_cnt < c->fanout) {
1678 550620 : ubifs_assert(c, n != c->fanout);
1679 550620 : dbg_tnck(key, "inserted at %d level %d, key ", n, znode->level);
1680 :
1681 550620 : insert_zbranch(c, znode, zbr, n);
1682 :
1683 : /* Ensure parent's key is correct */
1684 550620 : if (n == 0 && zp && znode->iip == 0)
1685 552 : correct_parent_keys(c, znode);
1686 :
1687 : return 0;
1688 : }
1689 :
1690 : /*
1691 : * Unfortunately, @znode does not have more empty slots and we have to
1692 : * split it.
1693 : */
1694 74013 : dbg_tnck(key, "splitting level %d, key ", znode->level);
1695 :
1696 74013 : if (znode->alt)
1697 : /*
1698 : * We can no longer be sure of finding this znode by key, so we
1699 : * record it in the old_idx tree.
1700 : */
1701 12820 : ins_clr_old_idx_znode(c, znode);
1702 :
1703 148026 : zn = kzalloc(c->max_znode_sz, GFP_NOFS);
1704 74013 : if (!zn)
1705 : return -ENOMEM;
1706 74013 : zn->parent = zp;
1707 74013 : zn->level = znode->level;
1708 :
1709 : /* Decide where to split */
1710 136092 : if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) {
1711 : /* Try not to split consecutive data keys */
1712 32129 : if (n == c->fanout) {
1713 16276 : key1 = &znode->zbranch[n - 1].key;
1714 65096 : if (key_inum(c, key1) == key_inum(c, key) &&
1715 16268 : key_type(c, key1) == UBIFS_DATA_KEY)
1716 : appending = 1;
1717 : } else
1718 : goto check_split;
1719 41884 : } else if (appending && n != c->fanout) {
1720 : /* Try not to split consecutive data keys */
1721 : appending = 0;
1722 33591 : check_split:
1723 17738 : if (n >= (c->fanout + 1) / 2) {
1724 16543 : key1 = &znode->zbranch[0].key;
1725 63600 : if (key_inum(c, key1) == key_inum(c, key) &&
1726 13971 : key_type(c, key1) == UBIFS_DATA_KEY) {
1727 12829 : key1 = &znode->zbranch[n].key;
1728 50496 : if (key_inum(c, key1) != key_inum(c, key) ||
1729 12009 : key_type(c, key1) != UBIFS_DATA_KEY) {
1730 2293 : keep = n;
1731 2293 : move = c->fanout - keep;
1732 2293 : zi = znode;
1733 2293 : goto do_split;
1734 : }
1735 : }
1736 : }
1737 : }
1738 :
1739 55495 : if (appending) {
1740 17147 : keep = c->fanout;
1741 17147 : move = 0;
1742 : } else {
1743 54573 : keep = (c->fanout + 1) / 2;
1744 54573 : move = c->fanout - keep;
1745 : }
1746 :
1747 : /*
1748 : * Although we don't at present, we could look at the neighbors and see
1749 : * if we can move some zbranches there.
1750 : */
1751 :
1752 71720 : if (n < keep) {
1753 : /* Insert into existing znode */
1754 13608 : zi = znode;
1755 13608 : move += 1;
1756 13608 : keep -= 1;
1757 : } else {
1758 : /* Insert into new znode */
1759 58112 : zi = zn;
1760 58112 : n -= keep;
1761 : /* Re-parent */
1762 58112 : if (zn->level != 0)
1763 8692 : zbr->znode->parent = zn;
1764 : }
1765 :
1766 123433 : do_split:
1767 :
1768 148026 : __set_bit(DIRTY_ZNODE, &zn->flags);
1769 148026 : atomic_long_inc(&c->dirty_zn_cnt);
1770 :
1771 74013 : zn->child_cnt = move;
1772 74013 : znode->child_cnt = keep;
1773 :
1774 74013 : dbg_tnc("moving %d, keeping %d", move, keep);
1775 :
1776 : /* Move zbranch */
1777 236574 : for (i = 0; i < move; i++) {
1778 236574 : zn->zbranch[i] = znode->zbranch[keep + i];
1779 : /* Re-parent */
1780 236574 : if (zn->level != 0)
1781 46030 : if (zn->zbranch[i].znode) {
1782 17312 : zn->zbranch[i].znode->parent = zn;
1783 17312 : zn->zbranch[i].znode->iip = i;
1784 : }
1785 : }
1786 :
1787 : /* Insert new key and branch */
1788 74013 : dbg_tnck(key, "inserting at %d level %d, key ", n, zn->level);
1789 :
1790 74013 : insert_zbranch(c, zi, zbr, n);
1791 :
1792 : /* Insert new znode (produced by spitting) into the parent */
1793 74013 : if (zp) {
1794 74013 : if (n == 0 && zi == znode && znode->iip == 0)
1795 37 : correct_parent_keys(c, znode);
1796 :
1797 : /* Locate insertion point */
1798 74013 : n = znode->iip + 1;
1799 :
1800 : /* Tail recursion */
1801 74013 : zbr->key = zn->zbranch[0].key;
1802 74013 : zbr->znode = zn;
1803 74013 : zbr->lnum = 0;
1804 74013 : zbr->offs = 0;
1805 74013 : zbr->len = 0;
1806 74013 : znode = zp;
1807 :
1808 74013 : goto again;
1809 : }
1810 :
1811 : /* We have to split root znode */
1812 0 : dbg_tnc("creating new zroot at level %d", znode->level + 1);
1813 :
1814 0 : zi = kzalloc(c->max_znode_sz, GFP_NOFS);
1815 0 : if (!zi)
1816 : return -ENOMEM;
1817 :
1818 0 : zi->child_cnt = 2;
1819 0 : zi->level = znode->level + 1;
1820 :
1821 0 : __set_bit(DIRTY_ZNODE, &zi->flags);
1822 0 : atomic_long_inc(&c->dirty_zn_cnt);
1823 :
1824 0 : zi->zbranch[0].key = znode->zbranch[0].key;
1825 0 : zi->zbranch[0].znode = znode;
1826 0 : zi->zbranch[0].lnum = c->zroot.lnum;
1827 0 : zi->zbranch[0].offs = c->zroot.offs;
1828 0 : zi->zbranch[0].len = c->zroot.len;
1829 0 : zi->zbranch[1].key = zn->zbranch[0].key;
1830 0 : zi->zbranch[1].znode = zn;
1831 :
1832 0 : c->zroot.lnum = 0;
1833 0 : c->zroot.offs = 0;
1834 0 : c->zroot.len = 0;
1835 0 : c->zroot.znode = zi;
1836 :
1837 0 : zn->parent = zi;
1838 0 : zn->iip = 1;
1839 0 : znode->parent = zi;
1840 0 : znode->iip = 0;
1841 :
1842 0 : return 0;
1843 : }
1844 :
1845 : /**
1846 : * ubifs_tnc_add - add a node to TNC.
1847 : * @c: UBIFS file-system description object
1848 : * @key: key to add
1849 : * @lnum: LEB number of node
1850 : * @offs: node offset
1851 : * @len: node length
1852 : * @hash: The hash over the node
1853 : *
1854 : * This function adds a node with key @key to TNC. The node may be new or it may
1855 : * obsolete some existing one. Returns %0 on success or negative error code on
1856 : * failure.
1857 : */
1858 2784222 : int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum,
1859 : int offs, int len, const u8 *hash)
1860 : {
1861 2784222 : int found, n, err = 0;
1862 : struct ubifs_znode *znode;
1863 :
1864 2784222 : mutex_lock(&c->tnc_mutex);
1865 2784222 : dbg_tnck(key, "%d:%d, len %d, key ", lnum, offs, len);
1866 2784222 : found = lookup_level0_dirty(c, key, &znode, &n);
1867 2784222 : if (!found) {
1868 : struct ubifs_zbranch zbr;
1869 :
1870 211355 : zbr.znode = NULL;
1871 211355 : zbr.lnum = lnum;
1872 211355 : zbr.offs = offs;
1873 211355 : zbr.len = len;
1874 211355 : ubifs_copy_hash(c, hash, zbr.hash);
1875 422710 : key_copy(c, key, &zbr.key);
1876 211355 : err = tnc_insert(c, znode, &zbr, n + 1);
1877 2572867 : } else if (found == 1) {
1878 2572859 : struct ubifs_zbranch *zbr = &znode->zbranch[n];
1879 :
1880 2572859 : lnc_free(zbr);
1881 5145718 : err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
1882 2572859 : zbr->lnum = lnum;
1883 2572859 : zbr->offs = offs;
1884 2572859 : zbr->len = len;
1885 2572859 : ubifs_copy_hash(c, hash, zbr->hash);
1886 : } else
1887 : err = found;
1888 2784222 : if (!err)
1889 2784214 : err = dbg_check_tnc(c, 0);
1890 2784222 : mutex_unlock(&c->tnc_mutex);
1891 :
1892 2784222 : return err;
1893 : }
1894 :
1895 : /**
1896 : * ubifs_tnc_replace - replace a node in the TNC only if the old node is found.
1897 : * @c: UBIFS file-system description object
1898 : * @key: key to add
1899 : * @old_lnum: LEB number of old node
1900 : * @old_offs: old node offset
1901 : * @lnum: LEB number of node
1902 : * @offs: node offset
1903 : * @len: node length
1904 : *
1905 : * This function replaces a node with key @key in the TNC only if the old node
1906 : * is found. This function is called by garbage collection when node are moved.
1907 : * Returns %0 on success or negative error code on failure.
1908 : */
1909 5468 : int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key,
1910 : int old_lnum, int old_offs, int lnum, int offs, int len)
1911 : {
1912 5468 : int found, n, err = 0;
1913 : struct ubifs_znode *znode;
1914 :
1915 5468 : mutex_lock(&c->tnc_mutex);
1916 5468 : dbg_tnck(key, "old LEB %d:%d, new LEB %d:%d, len %d, key ", old_lnum,
1917 : old_offs, lnum, offs, len);
1918 5468 : found = lookup_level0_dirty(c, key, &znode, &n);
1919 5468 : if (found < 0) {
1920 : err = found;
1921 : goto out_unlock;
1922 : }
1923 :
1924 5468 : if (found == 1) {
1925 5468 : struct ubifs_zbranch *zbr = &znode->zbranch[n];
1926 :
1927 5468 : found = 0;
1928 5468 : if (zbr->lnum == old_lnum && zbr->offs == old_offs) {
1929 5468 : lnc_free(zbr);
1930 10936 : err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
1931 5468 : if (err)
1932 : goto out_unlock;
1933 5468 : zbr->lnum = lnum;
1934 5468 : zbr->offs = offs;
1935 5468 : zbr->len = len;
1936 5468 : found = 1;
1937 0 : } else if (is_hash_key(c, key)) {
1938 0 : found = resolve_collision_directly(c, key, &znode, &n,
1939 : old_lnum, old_offs);
1940 0 : dbg_tnc("rc returned %d, znode %p, n %d, LEB %d:%d",
1941 : found, znode, n, old_lnum, old_offs);
1942 0 : if (found < 0) {
1943 : err = found;
1944 : goto out_unlock;
1945 : }
1946 :
1947 0 : if (found) {
1948 : /* Ensure the znode is dirtied */
1949 0 : if (znode->cnext || !ubifs_zn_dirty(znode)) {
1950 0 : znode = dirty_cow_bottom_up(c, znode);
1951 0 : if (IS_ERR(znode)) {
1952 0 : err = PTR_ERR(znode);
1953 0 : goto out_unlock;
1954 : }
1955 : }
1956 0 : zbr = &znode->zbranch[n];
1957 0 : lnc_free(zbr);
1958 0 : err = ubifs_add_dirt(c, zbr->lnum,
1959 : zbr->len);
1960 0 : if (err)
1961 : goto out_unlock;
1962 0 : zbr->lnum = lnum;
1963 0 : zbr->offs = offs;
1964 0 : zbr->len = len;
1965 : }
1966 : }
1967 : }
1968 :
1969 0 : if (!found)
1970 0 : err = ubifs_add_dirt(c, lnum, len);
1971 :
1972 5468 : if (!err)
1973 5468 : err = dbg_check_tnc(c, 0);
1974 :
1975 5468 : out_unlock:
1976 5468 : mutex_unlock(&c->tnc_mutex);
1977 5468 : return err;
1978 : }
1979 :
1980 : /**
1981 : * ubifs_tnc_add_nm - add a "hashed" node to TNC.
1982 : * @c: UBIFS file-system description object
1983 : * @key: key to add
1984 : * @lnum: LEB number of node
1985 : * @offs: node offset
1986 : * @len: node length
1987 : * @hash: The hash over the node
1988 : * @nm: node name
1989 : *
1990 : * This is the same as 'ubifs_tnc_add()' but it should be used with keys which
1991 : * may have collisions, like directory entry keys.
1992 : */
1993 350288 : int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key,
1994 : int lnum, int offs, int len, const u8 *hash,
1995 : const struct fscrypt_name *nm)
1996 : {
1997 350288 : int found, n, err = 0;
1998 : struct ubifs_znode *znode;
1999 :
2000 350288 : mutex_lock(&c->tnc_mutex);
2001 350288 : dbg_tnck(key, "LEB %d:%d, key ", lnum, offs);
2002 350288 : found = lookup_level0_dirty(c, key, &znode, &n);
2003 350288 : if (found < 0) {
2004 : err = found;
2005 : goto out_unlock;
2006 : }
2007 :
2008 350288 : if (found == 1) {
2009 329833 : if (c->replaying)
2010 329833 : found = fallible_resolve_collision(c, key, &znode, &n,
2011 : nm, 1);
2012 : else
2013 0 : found = resolve_collision(c, key, &znode, &n, nm);
2014 329833 : dbg_tnc("rc returned %d, znode %p, n %d", found, znode, n);
2015 329833 : if (found < 0) {
2016 : err = found;
2017 : goto out_unlock;
2018 : }
2019 :
2020 : /* Ensure the znode is dirtied */
2021 659666 : if (znode->cnext || !ubifs_zn_dirty(znode)) {
2022 0 : znode = dirty_cow_bottom_up(c, znode);
2023 0 : if (IS_ERR(znode)) {
2024 0 : err = PTR_ERR(znode);
2025 0 : goto out_unlock;
2026 : }
2027 : }
2028 :
2029 329833 : if (found == 1) {
2030 11023 : struct ubifs_zbranch *zbr = &znode->zbranch[n];
2031 :
2032 11023 : lnc_free(zbr);
2033 22046 : err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2034 11023 : zbr->lnum = lnum;
2035 11023 : zbr->offs = offs;
2036 11023 : zbr->len = len;
2037 11023 : ubifs_copy_hash(c, hash, zbr->hash);
2038 : goto out_unlock;
2039 : }
2040 : }
2041 :
2042 339265 : if (!found) {
2043 : struct ubifs_zbranch zbr;
2044 :
2045 339265 : zbr.znode = NULL;
2046 339265 : zbr.lnum = lnum;
2047 339265 : zbr.offs = offs;
2048 339265 : zbr.len = len;
2049 339265 : ubifs_copy_hash(c, hash, zbr.hash);
2050 678530 : key_copy(c, key, &zbr.key);
2051 339265 : err = tnc_insert(c, znode, &zbr, n + 1);
2052 339265 : if (err)
2053 : goto out_unlock;
2054 339265 : if (c->replaying) {
2055 : /*
2056 : * We did not find it in the index so there may be a
2057 : * dangling branch still in the index. So we remove it
2058 : * by passing 'ubifs_tnc_remove_nm()' the same key but
2059 : * an unmatchable name.
2060 : */
2061 339033 : struct fscrypt_name noname = { .disk_name = { .name = "", .len = 1 } };
2062 :
2063 339033 : err = dbg_check_tnc(c, 0);
2064 339033 : mutex_unlock(&c->tnc_mutex);
2065 : if (err)
2066 : return err;
2067 339033 : return ubifs_tnc_remove_nm(c, key, &noname);
2068 : }
2069 : }
2070 :
2071 11255 : out_unlock:
2072 11255 : if (!err)
2073 : err = dbg_check_tnc(c, 0);
2074 11255 : mutex_unlock(&c->tnc_mutex);
2075 11255 : return err;
2076 : }
2077 :
2078 : /**
2079 : * tnc_delete - delete a znode form TNC.
2080 : * @c: UBIFS file-system description object
2081 : * @znode: znode to delete from
2082 : * @n: zbranch slot number to delete
2083 : *
2084 : * This function deletes a leaf node from @n-th slot of @znode. Returns zero in
2085 : * case of success and a negative error code in case of failure.
2086 : */
2087 765529 : static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)
2088 : {
2089 : struct ubifs_zbranch *zbr;
2090 : struct ubifs_znode *zp;
2091 : int i, err;
2092 :
2093 : /* Delete without merge for now */
2094 765529 : ubifs_assert(c, znode->level == 0);
2095 765529 : ubifs_assert(c, n >= 0 && n < c->fanout);
2096 765529 : dbg_tnck(&znode->zbranch[n].key, "deleting key ");
2097 :
2098 765529 : zbr = &znode->zbranch[n];
2099 765529 : lnc_free(zbr);
2100 :
2101 1531058 : err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2102 765529 : if (err) {
2103 0 : ubifs_dump_znode(c, znode);
2104 0 : return err;
2105 : }
2106 :
2107 : /* We do not "gap" zbranch slots */
2108 1412297 : for (i = n; i < znode->child_cnt - 1; i++)
2109 1412297 : znode->zbranch[i] = znode->zbranch[i + 1];
2110 765529 : znode->child_cnt -= 1;
2111 :
2112 765529 : if (znode->child_cnt > 0)
2113 : return 0;
2114 :
2115 : /* Different with linux kernel, TNC could become empty. */
2116 90080 : if (!znode->parent)
2117 : return 0;
2118 :
2119 : /*
2120 : * This was the last zbranch, we have to delete this znode from the
2121 : * parent.
2122 : */
2123 :
2124 : do {
2125 110689 : ubifs_assert(c, !ubifs_zn_obsolete(znode));
2126 110689 : ubifs_assert(c, ubifs_zn_dirty(znode));
2127 :
2128 110689 : zp = znode->parent;
2129 110689 : n = znode->iip;
2130 :
2131 221378 : atomic_long_dec(&c->dirty_zn_cnt);
2132 :
2133 110689 : err = insert_old_idx_znode(c, znode);
2134 110689 : if (err)
2135 : return err;
2136 :
2137 110689 : if (znode->cnext) {
2138 0 : __set_bit(OBSOLETE_ZNODE, &znode->flags);
2139 0 : atomic_long_inc(&c->clean_zn_cnt);
2140 : atomic_long_inc(&ubifs_clean_zn_cnt);
2141 : } else
2142 : kfree(znode);
2143 110689 : znode = zp;
2144 110689 : } while (znode->child_cnt == 1); /* while removing last child */
2145 :
2146 : /* Remove from znode, entry n - 1 */
2147 90074 : znode->child_cnt -= 1;
2148 90074 : ubifs_assert(c, znode->level != 0);
2149 294767 : for (i = n; i < znode->child_cnt; i++) {
2150 204693 : znode->zbranch[i] = znode->zbranch[i + 1];
2151 204693 : if (znode->zbranch[i].znode)
2152 104670 : znode->zbranch[i].znode->iip = i;
2153 : }
2154 :
2155 : /*
2156 : * If this is the root and it has only 1 child then
2157 : * collapse the tree.
2158 : */
2159 90074 : if (!znode->parent) {
2160 52 : while (znode->child_cnt == 1 && znode->level != 0) {
2161 6 : zp = znode;
2162 6 : zbr = &znode->zbranch[0];
2163 6 : znode = get_znode(c, znode, 0);
2164 6 : if (IS_ERR(znode))
2165 0 : return PTR_ERR(znode);
2166 6 : znode = dirty_cow_znode(c, zbr);
2167 6 : if (IS_ERR(znode))
2168 0 : return PTR_ERR(znode);
2169 6 : znode->parent = NULL;
2170 6 : znode->iip = 0;
2171 6 : if (c->zroot.len) {
2172 6 : err = insert_old_idx(c, c->zroot.lnum,
2173 : c->zroot.offs);
2174 6 : if (err)
2175 : return err;
2176 : }
2177 6 : c->zroot.lnum = zbr->lnum;
2178 6 : c->zroot.offs = zbr->offs;
2179 6 : c->zroot.len = zbr->len;
2180 6 : c->zroot.znode = znode;
2181 6 : ubifs_assert(c, !ubifs_zn_obsolete(zp));
2182 6 : ubifs_assert(c, ubifs_zn_dirty(zp));
2183 12 : atomic_long_dec(&c->dirty_zn_cnt);
2184 :
2185 6 : if (zp->cnext) {
2186 0 : __set_bit(OBSOLETE_ZNODE, &zp->flags);
2187 0 : atomic_long_inc(&c->clean_zn_cnt);
2188 : atomic_long_inc(&ubifs_clean_zn_cnt);
2189 : } else
2190 : kfree(zp);
2191 : }
2192 : }
2193 :
2194 : return 0;
2195 : }
2196 :
2197 : /**
2198 : * ubifs_tnc_remove - remove an index entry of a node.
2199 : * @c: UBIFS file-system description object
2200 : * @key: key of node
2201 : *
2202 : * Returns %0 on success or negative error code on failure.
2203 : */
2204 0 : int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key)
2205 : {
2206 0 : int found, n, err = 0;
2207 : struct ubifs_znode *znode;
2208 :
2209 0 : mutex_lock(&c->tnc_mutex);
2210 0 : dbg_tnck(key, "key ");
2211 0 : found = lookup_level0_dirty(c, key, &znode, &n);
2212 0 : if (found < 0) {
2213 : err = found;
2214 : goto out_unlock;
2215 : }
2216 0 : if (found == 1)
2217 0 : err = tnc_delete(c, znode, n);
2218 0 : if (!err)
2219 : err = dbg_check_tnc(c, 0);
2220 :
2221 0 : out_unlock:
2222 0 : mutex_unlock(&c->tnc_mutex);
2223 0 : return err;
2224 : }
2225 :
2226 : /**
2227 : * ubifs_tnc_remove_nm - remove an index entry for a "hashed" node.
2228 : * @c: UBIFS file-system description object
2229 : * @key: key of node
2230 : * @nm: directory entry name
2231 : *
2232 : * Returns %0 on success or negative error code on failure.
2233 : */
2234 346835 : int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key,
2235 : const struct fscrypt_name *nm)
2236 : {
2237 : int n, err;
2238 : struct ubifs_znode *znode;
2239 :
2240 346835 : mutex_lock(&c->tnc_mutex);
2241 346835 : dbg_tnck(key, "key ");
2242 346835 : err = lookup_level0_dirty(c, key, &znode, &n);
2243 346835 : if (err < 0)
2244 : goto out_unlock;
2245 :
2246 346815 : if (err) {
2247 346103 : if (c->replaying)
2248 346103 : err = fallible_resolve_collision(c, key, &znode, &n,
2249 : nm, 0);
2250 : else
2251 0 : err = resolve_collision(c, key, &znode, &n, nm);
2252 346103 : dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);
2253 346103 : if (err < 0)
2254 : goto out_unlock;
2255 346103 : if (err) {
2256 : /* Ensure the znode is dirtied */
2257 651702 : if (znode->cnext || !ubifs_zn_dirty(znode)) {
2258 0 : znode = dirty_cow_bottom_up(c, znode);
2259 0 : if (IS_ERR(znode)) {
2260 0 : err = PTR_ERR(znode);
2261 0 : goto out_unlock;
2262 : }
2263 : }
2264 325851 : err = tnc_delete(c, znode, n);
2265 : }
2266 : }
2267 :
2268 367819 : out_unlock:
2269 346835 : if (!err)
2270 346815 : err = dbg_check_tnc(c, 0);
2271 346835 : mutex_unlock(&c->tnc_mutex);
2272 346835 : return err;
2273 : }
2274 :
2275 : /**
2276 : * key_in_range - determine if a key falls within a range of keys.
2277 : * @c: UBIFS file-system description object
2278 : * @key: key to check
2279 : * @from_key: lowest key in range
2280 : * @to_key: highest key in range
2281 : *
2282 : * This function returns %1 if the key is in range and %0 otherwise.
2283 : */
2284 : static int key_in_range(struct ubifs_info *c, union ubifs_key *key,
2285 : union ubifs_key *from_key, union ubifs_key *to_key)
2286 : {
2287 249555 : if (keys_cmp(c, key, from_key) < 0)
2288 : return 0;
2289 249555 : if (keys_cmp(c, key, to_key) > 0)
2290 : return 0;
2291 : return 1;
2292 : }
2293 :
2294 : /**
2295 : * ubifs_tnc_remove_range - remove index entries in range.
2296 : * @c: UBIFS file-system description object
2297 : * @from_key: lowest key to remove
2298 : * @to_key: highest key to remove
2299 : *
2300 : * This function removes index entries starting at @from_key and ending at
2301 : * @to_key. This function returns zero in case of success and a negative error
2302 : * code in case of failure.
2303 : */
2304 9107 : int ubifs_tnc_remove_range(struct ubifs_info *c, union ubifs_key *from_key,
2305 : union ubifs_key *to_key)
2306 : {
2307 9107 : int i, n, k, err = 0;
2308 : struct ubifs_znode *znode;
2309 : union ubifs_key *key;
2310 :
2311 9107 : mutex_lock(&c->tnc_mutex);
2312 : while (1) {
2313 : /* Find first level 0 znode that contains keys to remove */
2314 48131 : err = ubifs_lookup_level0(c, from_key, &znode, &n);
2315 48131 : if (err < 0)
2316 : goto out_unlock;
2317 :
2318 48131 : if (err)
2319 : key = from_key;
2320 : else {
2321 41241 : err = tnc_next(c, &znode, &n);
2322 41241 : if (err == -ENOENT) {
2323 : err = 0;
2324 : goto out_unlock;
2325 : }
2326 40190 : if (err < 0)
2327 : goto out_unlock;
2328 40190 : key = &znode->zbranch[n].key;
2329 40190 : if (!key_in_range(c, key, from_key, to_key)) {
2330 : err = 0;
2331 : goto out_unlock;
2332 : }
2333 : }
2334 :
2335 : /* Ensure the znode is dirtied */
2336 78048 : if (znode->cnext || !ubifs_zn_dirty(znode)) {
2337 31437 : znode = dirty_cow_bottom_up(c, znode);
2338 62874 : if (IS_ERR(znode)) {
2339 0 : err = PTR_ERR(znode);
2340 0 : goto out_unlock;
2341 : }
2342 : }
2343 :
2344 : /* Remove all keys in range except the first */
2345 243836 : for (i = n + 1, k = 0; i < znode->child_cnt; i++, k++) {
2346 209365 : key = &znode->zbranch[i].key;
2347 209365 : if (!key_in_range(c, key, from_key, to_key))
2348 : break;
2349 204812 : lnc_free(&znode->zbranch[i]);
2350 409624 : err = ubifs_add_dirt(c, znode->zbranch[i].lnum,
2351 204812 : znode->zbranch[i].len);
2352 204812 : if (err) {
2353 0 : ubifs_dump_znode(c, znode);
2354 0 : goto out_unlock;
2355 : }
2356 204812 : dbg_tnck(key, "removing key ");
2357 : }
2358 39024 : if (k) {
2359 37666 : for (i = n + 1 + k; i < znode->child_cnt; i++)
2360 3587 : znode->zbranch[i - k] = znode->zbranch[i];
2361 34079 : znode->child_cnt -= k;
2362 : }
2363 :
2364 : /* Now delete the first */
2365 39024 : err = tnc_delete(c, znode, n);
2366 39024 : if (err)
2367 : goto out_unlock;
2368 : }
2369 :
2370 0 : out_unlock:
2371 9107 : if (!err)
2372 9107 : err = dbg_check_tnc(c, 0);
2373 9107 : mutex_unlock(&c->tnc_mutex);
2374 9107 : return err;
2375 : }
2376 :
2377 : /**
2378 : * ubifs_tnc_remove_ino - remove an inode from TNC.
2379 : * @c: UBIFS file-system description object
2380 : * @inum: inode number to remove
2381 : *
2382 : * This function remove inode @inum and all the extended attributes associated
2383 : * with the anode from TNC and returns zero in case of success or a negative
2384 : * error code in case of failure.
2385 : */
2386 4747 : int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum)
2387 : {
2388 : union ubifs_key key1, key2;
2389 4747 : struct ubifs_dent_node *xent, *pxent = NULL;
2390 4747 : struct fscrypt_name nm = {0};
2391 :
2392 4747 : dbg_tnc("ino %lu", (unsigned long)inum);
2393 :
2394 : /*
2395 : * Walk all extended attribute entries and remove them together with
2396 : * corresponding extended attribute inodes.
2397 : */
2398 4747 : lowest_xent_key(c, &key1, inum);
2399 : while (1) {
2400 : ino_t xattr_inum;
2401 : int err;
2402 :
2403 5488 : xent = ubifs_tnc_next_ent(c, &key1, &nm);
2404 5488 : if (IS_ERR(xent)) {
2405 : unsigned int reason;
2406 :
2407 4747 : err = PTR_ERR(xent);
2408 4747 : if (err == -ENOENT)
2409 : break;
2410 :
2411 0 : reason = get_failure_reason_callback(c);
2412 0 : if (reason & FR_DATA_CORRUPTED) {
2413 0 : test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED);
2414 0 : if (handle_failure_callback(c, FR_H_TNC_DATA_CORRUPTED, NULL)) {
2415 : /* Set %FR_LPT_INCORRECT for lpt status. */
2416 : set_lpt_invalid_callback(c, FR_LPT_INCORRECT);
2417 : /* Leave xattrs to be deleted by subsequent steps */
2418 : break;
2419 : }
2420 : }
2421 0 : kfree(pxent);
2422 0 : return err;
2423 : }
2424 :
2425 741 : xattr_inum = le64_to_cpu(xent->inum);
2426 741 : dbg_tnc("xent '%s', ino %lu", xent->name,
2427 : (unsigned long)xattr_inum);
2428 :
2429 741 : fname_name(&nm) = (const char *)xent->name;
2430 741 : fname_len(&nm) = le16_to_cpu(xent->nlen);
2431 741 : err = ubifs_tnc_remove_nm(c, &key1, &nm);
2432 741 : if (err) {
2433 0 : kfree(pxent);
2434 0 : kfree(xent);
2435 0 : return err;
2436 : }
2437 :
2438 1482 : lowest_ino_key(c, &key1, xattr_inum);
2439 1482 : highest_ino_key(c, &key2, xattr_inum);
2440 741 : err = ubifs_tnc_remove_range(c, &key1, &key2);
2441 741 : if (err) {
2442 0 : kfree(pxent);
2443 0 : kfree(xent);
2444 0 : return err;
2445 : }
2446 :
2447 741 : kfree(pxent);
2448 741 : pxent = xent;
2449 741 : key_read(c, &xent->key, &key1);
2450 : }
2451 :
2452 4747 : kfree(pxent);
2453 9494 : lowest_ino_key(c, &key1, inum);
2454 9494 : highest_ino_key(c, &key2, inum);
2455 :
2456 4747 : return ubifs_tnc_remove_range(c, &key1, &key2);
2457 : }
2458 :
2459 : /**
2460 : * ubifs_tnc_remove_node - remove an index entry of a node by given position.
2461 : * @c: UBIFS file-system description object
2462 : * @key: key of node
2463 : * @lnum: LEB number of node
2464 : * @offs: node offset
2465 : *
2466 : * Returns %0 on success or negative error code on failure.
2467 : */
2468 400654 : int ubifs_tnc_remove_node(struct ubifs_info *c, const union ubifs_key *key,
2469 : int lnum, int offs)
2470 : {
2471 400654 : int found, n, err = 0;
2472 : struct ubifs_znode *znode;
2473 :
2474 400654 : mutex_lock(&c->tnc_mutex);
2475 400654 : dbg_tnck(key, "pos %d:%d, key ", lnum, offs);
2476 400654 : found = lookup_level0_dirty(c, key, &znode, &n);
2477 400654 : if (found < 0) {
2478 : err = found;
2479 : goto out_unlock;
2480 : }
2481 400654 : if (found == 1) {
2482 400654 : struct ubifs_zbranch *zbr = &znode->zbranch[n];
2483 :
2484 400654 : if (zbr->lnum == lnum && zbr->offs == offs) {
2485 400654 : err = tnc_delete(c, znode, n);
2486 0 : } else if (is_hash_key(c, key)) {
2487 0 : found = resolve_collision_directly(c, key, &znode, &n,
2488 : lnum, offs);
2489 0 : if (found < 0) {
2490 : err = found;
2491 : goto out_unlock;
2492 : }
2493 :
2494 0 : if (found) {
2495 : /* Ensure the znode is dirtied */
2496 0 : if (znode->cnext || !ubifs_zn_dirty(znode)) {
2497 0 : znode = dirty_cow_bottom_up(c, znode);
2498 0 : if (IS_ERR(znode)) {
2499 0 : err = PTR_ERR(znode);
2500 0 : goto out_unlock;
2501 : }
2502 : }
2503 0 : err = tnc_delete(c, znode, n);
2504 : } else {
2505 : goto not_found;
2506 : }
2507 : } else {
2508 : goto not_found;
2509 : }
2510 : } else {
2511 0 : not_found:
2512 : /* Impossible, the node has been found before being deleted. */
2513 0 : ubifs_assert(c, 0);
2514 : }
2515 400654 : if (!err)
2516 : err = dbg_check_tnc(c, 0);
2517 :
2518 0 : out_unlock:
2519 400654 : mutex_unlock(&c->tnc_mutex);
2520 400654 : return err;
2521 : }
2522 :
2523 : /**
2524 : * ubifs_tnc_next_ent - walk directory or extended attribute entries.
2525 : * @c: UBIFS file-system description object
2526 : * @key: key of last entry
2527 : * @nm: name of last entry found or %NULL
2528 : *
2529 : * This function finds and reads the next directory or extended attribute entry
2530 : * after the given key (@key) if there is one. @nm is used to resolve
2531 : * collisions.
2532 : *
2533 : * If the name of the current entry is not known and only the key is known,
2534 : * @nm->name has to be %NULL. In this case the semantics of this function is a
2535 : * little bit different and it returns the entry corresponding to this key, not
2536 : * the next one. If the key was not found, the closest "right" entry is
2537 : * returned.
2538 : *
2539 : * If the fist entry has to be found, @key has to contain the lowest possible
2540 : * key value for this inode and @name has to be %NULL.
2541 : *
2542 : * This function returns the found directory or extended attribute entry node
2543 : * in case of success, %-ENOENT is returned if no entry was found, and a
2544 : * negative error code is returned in case of failure.
2545 : */
2546 5488 : struct ubifs_dent_node *ubifs_tnc_next_ent(struct ubifs_info *c,
2547 : union ubifs_key *key,
2548 : const struct fscrypt_name *nm)
2549 : {
2550 10976 : int n, err, type = key_type(c, key);
2551 : struct ubifs_znode *znode;
2552 : struct ubifs_dent_node *dent;
2553 : struct ubifs_zbranch *zbr;
2554 : union ubifs_key *dkey;
2555 :
2556 5488 : dbg_tnck(key, "key ");
2557 10976 : ubifs_assert(c, is_hash_key(c, key));
2558 :
2559 5488 : mutex_lock(&c->tnc_mutex);
2560 5488 : err = ubifs_lookup_level0(c, key, &znode, &n);
2561 5488 : if (unlikely(err < 0))
2562 : goto out_unlock;
2563 :
2564 5488 : if (fname_len(nm) > 0) {
2565 741 : if (err) {
2566 : /* Handle collisions */
2567 741 : if (c->replaying)
2568 741 : err = fallible_resolve_collision(c, key, &znode, &n,
2569 : nm, 0);
2570 : else
2571 0 : err = resolve_collision(c, key, &znode, &n, nm);
2572 741 : dbg_tnc("rc returned %d, znode %p, n %d",
2573 : err, znode, n);
2574 741 : if (unlikely(err < 0))
2575 : goto out_unlock;
2576 : }
2577 :
2578 : /* Now find next entry */
2579 741 : err = tnc_next(c, &znode, &n);
2580 741 : if (unlikely(err))
2581 : goto out_unlock;
2582 : } else {
2583 : /*
2584 : * The full name of the entry was not given, in which case the
2585 : * behavior of this function is a little different and it
2586 : * returns current entry, not the next one.
2587 : */
2588 4747 : if (!err) {
2589 : /*
2590 : * However, the given key does not exist in the TNC
2591 : * tree and @znode/@n variables contain the closest
2592 : * "preceding" element. Switch to the next one.
2593 : */
2594 4747 : err = tnc_next(c, &znode, &n);
2595 4747 : if (err)
2596 : goto out_unlock;
2597 : }
2598 : }
2599 :
2600 4716 : zbr = &znode->zbranch[n];
2601 4716 : dent = kmalloc(zbr->len, GFP_NOFS);
2602 4716 : if (unlikely(!dent)) {
2603 : err = -ENOMEM;
2604 : goto out_unlock;
2605 : }
2606 :
2607 : /*
2608 : * The above 'tnc_next()' call could lead us to the next inode, check
2609 : * this.
2610 : */
2611 4716 : dkey = &zbr->key;
2612 14990 : if (key_inum(c, dkey) != key_inum(c, key) ||
2613 842 : key_type(c, dkey) != type) {
2614 : err = -ENOENT;
2615 : goto out_free;
2616 : }
2617 :
2618 842 : err = tnc_read_hashed_node(c, zbr, dent);
2619 842 : if (unlikely(err))
2620 : goto out_free;
2621 :
2622 741 : mutex_unlock(&c->tnc_mutex);
2623 741 : return dent;
2624 :
2625 101 : out_free:
2626 : kfree(dent);
2627 5519 : out_unlock:
2628 4747 : mutex_unlock(&c->tnc_mutex);
2629 9494 : return ERR_PTR(err);
2630 : }
2631 :
2632 : /**
2633 : * tnc_destroy_cnext - destroy left-over obsolete znodes from a failed commit.
2634 : * @c: UBIFS file-system description object
2635 : *
2636 : * Destroy left-over obsolete znodes from a failed commit.
2637 : */
2638 1951 : static void tnc_destroy_cnext(struct ubifs_info *c)
2639 : {
2640 : struct ubifs_znode *cnext;
2641 :
2642 1951 : if (!c->cnext)
2643 : return;
2644 27 : ubifs_assert(c, c->cmt_state == COMMIT_BROKEN);
2645 27 : cnext = c->cnext;
2646 : do {
2647 141183 : struct ubifs_znode *znode = cnext;
2648 :
2649 141183 : cnext = cnext->cnext;
2650 141183 : if (ubifs_zn_obsolete(znode))
2651 : kfree(znode);
2652 141183 : else if (!ubifs_zn_cow(znode)) {
2653 : /*
2654 : * Don't forget to update clean znode count after
2655 : * committing failed, because ubifs will check this
2656 : * count while closing tnc. Non-obsolete znode could
2657 : * be re-dirtied during committing process, so dirty
2658 : * flag is untrustable. The flag 'COW_ZNODE' is set
2659 : * for each dirty znode before committing, and it is
2660 : * cleared as long as the znode become clean, so we
2661 : * can statistic clean znode count according to this
2662 : * flag.
2663 : */
2664 46754 : atomic_long_inc(&c->clean_zn_cnt);
2665 : atomic_long_inc(&ubifs_clean_zn_cnt);
2666 : }
2667 141183 : } while (cnext && cnext != c->cnext);
2668 : }
2669 :
2670 : /**
2671 : * ubifs_tnc_close - close TNC subsystem and free all related resources.
2672 : * @c: UBIFS file-system description object
2673 : */
2674 1951 : void ubifs_tnc_close(struct ubifs_info *c)
2675 : {
2676 1951 : tnc_destroy_cnext(c);
2677 1951 : ubifs_destroy_tnc_tree(c);
2678 3902 : kfree(c->gap_lebs);
2679 3902 : kfree(c->ilebs);
2680 1951 : destroy_old_idx(c);
2681 1951 : }
2682 :
2683 : /**
2684 : * left_znode - get the znode to the left.
2685 : * @c: UBIFS file-system description object
2686 : * @znode: znode
2687 : *
2688 : * This function returns a pointer to the znode to the left of @znode or NULL if
2689 : * there is not one. A negative error code is returned on failure.
2690 : */
2691 102148990 : static struct ubifs_znode *left_znode(struct ubifs_info *c,
2692 : struct ubifs_znode *znode)
2693 : {
2694 102148990 : int level = znode->level;
2695 :
2696 : while (1) {
2697 130475114 : int n = znode->iip - 1;
2698 :
2699 : /* Go up until we can go left */
2700 130475114 : znode = znode->parent;
2701 130475114 : if (!znode)
2702 : return NULL;
2703 130466649 : if (n >= 0) {
2704 : /* Now go down the rightmost branch to 'level' */
2705 102140525 : znode = get_znode(c, znode, n);
2706 102140525 : if (IS_ERR(znode))
2707 : return znode;
2708 130445143 : while (znode->level != level) {
2709 28304618 : n = znode->child_cnt - 1;
2710 28304618 : znode = get_znode(c, znode, n);
2711 28304618 : if (IS_ERR(znode))
2712 : return znode;
2713 : }
2714 : break;
2715 : }
2716 : }
2717 : return znode;
2718 : }
2719 :
2720 : /**
2721 : * right_znode - get the znode to the right.
2722 : * @c: UBIFS file-system description object
2723 : * @znode: znode
2724 : *
2725 : * This function returns a pointer to the znode to the right of @znode or NULL
2726 : * if there is not one. A negative error code is returned on failure.
2727 : */
2728 70001511 : static struct ubifs_znode *right_znode(struct ubifs_info *c,
2729 : struct ubifs_znode *znode)
2730 : {
2731 70001511 : int level = znode->level;
2732 :
2733 : while (1) {
2734 92967202 : int n = znode->iip + 1;
2735 :
2736 : /* Go up until we can go right */
2737 92967202 : znode = znode->parent;
2738 92967202 : if (!znode)
2739 : return NULL;
2740 92906351 : if (n < znode->child_cnt) {
2741 : /* Now go down the leftmost branch to 'level' */
2742 69940660 : znode = get_znode(c, znode, n);
2743 69940660 : if (IS_ERR(znode))
2744 : return znode;
2745 92862633 : while (znode->level != level) {
2746 22921973 : znode = get_znode(c, znode, 0);
2747 22921973 : if (IS_ERR(znode))
2748 : return znode;
2749 : }
2750 : break;
2751 : }
2752 : }
2753 : return znode;
2754 : }
2755 :
2756 : /**
2757 : * lookup_znode - find a particular indexing node from TNC.
2758 : * @c: UBIFS file-system description object
2759 : * @key: index node key to lookup
2760 : * @level: index node level
2761 : * @lnum: index node LEB number
2762 : * @offs: index node offset
2763 : *
2764 : * This function searches an indexing node by its first key @key and its
2765 : * address @lnum:@offs. It looks up the indexing tree by pulling all indexing
2766 : * nodes it traverses to TNC. This function is called for indexing nodes which
2767 : * were found on the media by scanning, for example when garbage-collecting or
2768 : * when doing in-the-gaps commit. This means that the indexing node which is
2769 : * looked for does not have to have exactly the same leftmost key @key, because
2770 : * the leftmost key may have been changed, in which case TNC will contain a
2771 : * dirty znode which still refers the same @lnum:@offs. This function is clever
2772 : * enough to recognize such indexing nodes.
2773 : *
2774 : * Note, if a znode was deleted or changed too much, then this function will
2775 : * not find it. For situations like this UBIFS has the old index RB-tree
2776 : * (indexed by @lnum:@offs).
2777 : *
2778 : * This function returns a pointer to the znode found or %NULL if it is not
2779 : * found. A negative error code is returned on failure.
2780 : */
2781 2400723461 : static struct ubifs_znode *lookup_znode(struct ubifs_info *c,
2782 : union ubifs_key *key, int level,
2783 : int lnum, int offs)
2784 : {
2785 : struct ubifs_znode *znode, *zn;
2786 : int n, nn;
2787 :
2788 4801446922 : ubifs_assert(c, key_type(c, key) < UBIFS_INVALID_KEY);
2789 :
2790 : /*
2791 : * The arguments have probably been read off flash, so don't assume
2792 : * they are valid.
2793 : */
2794 2400723461 : if (level < 0)
2795 : return ERR_PTR(-EINVAL);
2796 :
2797 : /* Get the root znode */
2798 2400723461 : znode = c->zroot.znode;
2799 2400723461 : if (!znode) {
2800 0 : znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
2801 0 : if (IS_ERR(znode))
2802 : return znode;
2803 : }
2804 : /* Check if it is the one we are looking for */
2805 2400723461 : if (c->zroot.lnum == lnum && c->zroot.offs == offs)
2806 : return znode;
2807 : /* Descend to the parent level i.e. (level + 1) */
2808 2400721929 : if (level >= znode->level)
2809 : return NULL;
2810 : while (1) {
2811 17866782189 : ubifs_search_zbranch(c, znode, key, &n);
2812 17866782189 : if (n < 0) {
2813 : /*
2814 : * We reached a znode where the leftmost key is greater
2815 : * than the key we are searching for. This is the same
2816 : * situation as the one described in a huge comment at
2817 : * the end of the 'ubifs_lookup_level0()' function. And
2818 : * for exactly the same reasons we have to try to look
2819 : * left before giving up.
2820 : */
2821 16866989 : znode = left_znode(c, znode);
2822 16866989 : if (!znode)
2823 : return NULL;
2824 16862554 : if (IS_ERR(znode))
2825 : return znode;
2826 16862554 : ubifs_search_zbranch(c, znode, key, &n);
2827 16862554 : ubifs_assert(c, n >= 0);
2828 : }
2829 17866777754 : if (znode->level == level + 1)
2830 : break;
2831 30935628298 : znode = get_znode(c, znode, n);
2832 15467814149 : if (IS_ERR(znode))
2833 : return znode;
2834 : }
2835 : /* Check if the child is the one we are looking for */
2836 2398963605 : if (znode->zbranch[n].lnum == lnum && znode->zbranch[n].offs == offs)
2837 566916431 : return get_znode(c, znode, n);
2838 : /* If the key is unique, there is nowhere else to look */
2839 3664094348 : if (!is_hash_key(c, key))
2840 : return NULL;
2841 : /*
2842 : * The key is not unique and so may be also in the znodes to either
2843 : * side.
2844 : */
2845 : zn = znode;
2846 : nn = n;
2847 : /* Look left */
2848 : while (1) {
2849 : /* Move one branch to the left */
2850 361220610 : if (n)
2851 275938609 : n -= 1;
2852 : else {
2853 85282001 : znode = left_znode(c, znode);
2854 85282001 : if (!znode)
2855 : break;
2856 85277971 : if (IS_ERR(znode))
2857 : return znode;
2858 85277971 : n = znode->child_cnt - 1;
2859 : }
2860 : /* Check it */
2861 365959787 : if (znode->zbranch[n].lnum == lnum &&
2862 4743207 : znode->zbranch[n].offs == offs)
2863 0 : return get_znode(c, znode, n);
2864 : /* Stop if the key is less than the one we are looking for */
2865 361216580 : if (keys_cmp(c, &znode->zbranch[n].key, key) < 0)
2866 : break;
2867 : }
2868 : /* Back to the middle */
2869 361220610 : znode = zn;
2870 361220610 : n = nn;
2871 : /* Look right */
2872 : while (1) {
2873 : /* Move one branch to the right */
2874 361220610 : if (++n >= znode->child_cnt) {
2875 70001511 : znode = right_znode(c, znode);
2876 70001511 : if (!znode)
2877 : break;
2878 69940660 : if (IS_ERR(znode))
2879 : return znode;
2880 69940660 : n = 0;
2881 : }
2882 : /* Check it */
2883 367590752 : if (znode->zbranch[n].lnum == lnum &&
2884 6430993 : znode->zbranch[n].offs == offs)
2885 0 : return get_znode(c, znode, n);
2886 : /* Stop if the key is greater than the one we are looking for */
2887 361159759 : if (keys_cmp(c, &znode->zbranch[n].key, key) > 0)
2888 : break;
2889 : }
2890 : return NULL;
2891 : }
2892 :
2893 : /**
2894 : * is_idx_node_in_tnc - determine if an index node is in the TNC.
2895 : * @c: UBIFS file-system description object
2896 : * @key: key of index node
2897 : * @level: index node level
2898 : * @lnum: LEB number of index node
2899 : * @offs: offset of index node
2900 : *
2901 : * This function returns %0 if the index node is not referred to in the TNC, %1
2902 : * if the index node is referred to in the TNC and the corresponding znode is
2903 : * dirty, %2 if an index node is referred to in the TNC and the corresponding
2904 : * znode is clean, and a negative error code in case of failure.
2905 : *
2906 : * Note, the @key argument has to be the key of the first child. Also note,
2907 : * this function relies on the fact that 0:0 is never a valid LEB number and
2908 : * offset for a main-area node.
2909 : */
2910 2400723461 : int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level,
2911 : int lnum, int offs)
2912 : {
2913 : struct ubifs_znode *znode;
2914 :
2915 2400723461 : znode = lookup_znode(c, key, level, lnum, offs);
2916 2400723461 : if (!znode)
2917 : return 0;
2918 566917963 : if (IS_ERR(znode))
2919 0 : return PTR_ERR(znode);
2920 :
2921 566917963 : return ubifs_zn_dirty(znode) ? 1 : 2;
2922 : }
2923 :
2924 : /**
2925 : * is_leaf_node_in_tnc - determine if a non-indexing not is in the TNC.
2926 : * @c: UBIFS file-system description object
2927 : * @key: node key
2928 : * @lnum: node LEB number
2929 : * @offs: node offset
2930 : *
2931 : * This function returns %1 if the node is referred to in the TNC, %0 if it is
2932 : * not, and a negative error code in case of failure.
2933 : *
2934 : * Note, this function relies on the fact that 0:0 is never a valid LEB number
2935 : * and offset for a main-area node.
2936 : */
2937 3922805030 : static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key,
2938 : int lnum, int offs)
2939 : {
2940 : struct ubifs_zbranch *zbr;
2941 : struct ubifs_znode *znode, *zn;
2942 : int n, found, err, nn;
2943 7845610060 : const int unique = !is_hash_key(c, key);
2944 :
2945 3922805030 : found = ubifs_lookup_level0(c, key, &znode, &n);
2946 3922805030 : if (found < 0)
2947 : return found; /* Error code */
2948 3922805030 : if (!found)
2949 : return 0;
2950 3179266245 : zbr = &znode->zbranch[n];
2951 3179266245 : if (lnum == zbr->lnum && offs == zbr->offs)
2952 : return 1; /* Found it */
2953 692037866 : if (unique)
2954 : return 0;
2955 : /*
2956 : * Because the key is not unique, we have to look left
2957 : * and right as well
2958 : */
2959 : zn = znode;
2960 : nn = n;
2961 : /* Look left */
2962 : while (1) {
2963 34108323 : err = tnc_prev(c, &znode, &n);
2964 34108323 : if (err == -ENOENT)
2965 : break;
2966 34108323 : if (err)
2967 : return err;
2968 34108323 : if (keys_cmp(c, key, &znode->zbranch[n].key))
2969 : break;
2970 0 : zbr = &znode->zbranch[n];
2971 0 : if (lnum == zbr->lnum && offs == zbr->offs)
2972 : return 1; /* Found it */
2973 : }
2974 : /* Look right */
2975 34108323 : znode = zn;
2976 34108323 : n = nn;
2977 : while (1) {
2978 34108323 : err = tnc_next(c, &znode, &n);
2979 34108323 : if (err) {
2980 0 : if (err == -ENOENT)
2981 : return 0;
2982 0 : return err;
2983 : }
2984 34108323 : if (keys_cmp(c, key, &znode->zbranch[n].key))
2985 : break;
2986 0 : zbr = &znode->zbranch[n];
2987 0 : if (lnum == zbr->lnum && offs == zbr->offs)
2988 : return 1; /* Found it */
2989 : }
2990 : return 0;
2991 : }
2992 :
2993 : /**
2994 : * ubifs_tnc_has_node - determine whether a node is in the TNC.
2995 : * @c: UBIFS file-system description object
2996 : * @key: node key
2997 : * @level: index node level (if it is an index node)
2998 : * @lnum: node LEB number
2999 : * @offs: node offset
3000 : * @is_idx: non-zero if the node is an index node
3001 : *
3002 : * This function returns %1 if the node is in the TNC, %0 if it is not, and a
3003 : * negative error code in case of failure. For index nodes, @key has to be the
3004 : * key of the first child. An index node is considered to be in the TNC only if
3005 : * the corresponding znode is clean or has not been loaded.
3006 : */
3007 6321522230 : int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level,
3008 : int lnum, int offs, int is_idx)
3009 : {
3010 : int err;
3011 :
3012 6321522230 : mutex_lock(&c->tnc_mutex);
3013 6321522230 : if (is_idx) {
3014 2398717200 : err = is_idx_node_in_tnc(c, key, level, lnum, offs);
3015 2398717200 : if (err < 0)
3016 : goto out_unlock;
3017 2398717200 : if (err == 1)
3018 : /* The index node was found but it was dirty */
3019 : err = 0;
3020 2396602525 : else if (err == 2)
3021 : /* The index node was found and it was clean */
3022 : err = 1;
3023 : else
3024 1832144905 : BUG_ON(err != 0);
3025 : } else
3026 3922805030 : err = is_leaf_node_in_tnc(c, key, lnum, offs);
3027 :
3028 6321522230 : out_unlock:
3029 6321522230 : mutex_unlock(&c->tnc_mutex);
3030 6321522230 : return err;
3031 : }
3032 :
3033 : /**
3034 : * ubifs_dirty_idx_node - dirty an index node.
3035 : * @c: UBIFS file-system description object
3036 : * @key: index node key
3037 : * @level: index node level
3038 : * @lnum: index node LEB number
3039 : * @offs: index node offset
3040 : *
3041 : * This function loads and dirties an index node so that it can be garbage
3042 : * collected. The @key argument has to be the key of the first child. This
3043 : * function relies on the fact that 0:0 is never a valid LEB number and offset
3044 : * for a main-area node. Returns %0 on success and a negative error code on
3045 : * failure.
3046 : */
3047 0 : int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level,
3048 : int lnum, int offs)
3049 : {
3050 : struct ubifs_znode *znode;
3051 0 : int err = 0;
3052 :
3053 0 : mutex_lock(&c->tnc_mutex);
3054 0 : znode = lookup_znode(c, key, level, lnum, offs);
3055 0 : if (!znode)
3056 : goto out_unlock;
3057 0 : if (IS_ERR(znode)) {
3058 0 : err = PTR_ERR(znode);
3059 0 : goto out_unlock;
3060 : }
3061 0 : znode = dirty_cow_bottom_up(c, znode);
3062 0 : if (IS_ERR(znode)) {
3063 0 : err = PTR_ERR(znode);
3064 0 : goto out_unlock;
3065 : }
3066 :
3067 0 : out_unlock:
3068 0 : mutex_unlock(&c->tnc_mutex);
3069 0 : return err;
3070 : }
|