Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 : /*
3 : * Copyright (C) 2024, Huawei Technologies Co, Ltd.
4 : *
5 : * Authors: Zhihao Cheng <chengzhihao1@huawei.com>
6 : */
7 :
8 : #include <stdio.h>
9 : #include <stdlib.h>
10 : #include <sys/stat.h>
11 :
12 : #include "linux_err.h"
13 : #include "bitops.h"
14 : #include "kmem.h"
15 : #include "ubifs.h"
16 : #include "defs.h"
17 : #include "debug.h"
18 : #include "key.h"
19 : #include "fsck.ubifs.h"
20 :
21 : struct invalid_node {
22 : union ubifs_key key;
23 : int lnum;
24 : int offs;
25 : struct list_head list;
26 : };
27 :
28 : struct iteration_info {
29 : struct list_head invalid_nodes;
30 : unsigned long *corrupted_lebs;
31 : };
32 :
33 197630 : static int add_invalid_node(struct ubifs_info *c, union ubifs_key *key,
34 : int lnum, int offs, struct iteration_info *iter)
35 : {
36 : struct invalid_node *in;
37 :
38 197630 : in = kmalloc(sizeof(struct invalid_node), GFP_KERNEL);
39 197630 : if (!in) {
40 0 : log_err(c, errno, "can not allocate invalid node");
41 0 : return -ENOMEM;
42 : }
43 :
44 395260 : key_copy(c, key, &in->key);
45 197630 : in->lnum = lnum;
46 197630 : in->offs = offs;
47 395260 : list_add(&in->list, &iter->invalid_nodes);
48 :
49 197630 : return 0;
50 : }
51 :
52 2491373597 : static int construct_file(struct ubifs_info *c, union ubifs_key *key,
53 : int lnum, int offs, void *node,
54 : struct iteration_info *iter)
55 : {
56 2491373597 : ino_t inum = 0;
57 2491373597 : struct rb_root *tree = &FSCK(c)->scanned_files;
58 2491373597 : struct scanned_node *sn = NULL;
59 2491373597 : struct ubifs_ch *ch = (struct ubifs_ch *)node;
60 :
61 2491373597 : switch (ch->node_type) {
62 207732613 : case UBIFS_INO_NODE:
63 : {
64 : struct scanned_ino_node ino_node;
65 :
66 207732613 : if (!parse_ino_node(c, lnum, offs, node, key, &ino_node)) {
67 95 : if (fix_problem(c, INVALID_INO_NODE, NULL))
68 74 : return add_invalid_node(c, key, lnum, offs, iter);
69 : }
70 415465036 : inum = key_inum(c, key);
71 207732518 : sn = (struct scanned_node *)&ino_node;
72 207732518 : break;
73 : }
74 218126908 : case UBIFS_DENT_NODE:
75 : case UBIFS_XENT_NODE:
76 : {
77 : struct scanned_dent_node dent_node;
78 :
79 218126908 : if (!parse_dent_node(c, lnum, offs, node, key, &dent_node)) {
80 36 : if (fix_problem(c, INVALID_DENT_NODE, NULL))
81 18 : return add_invalid_node(c, key, lnum, offs, iter);
82 : }
83 218126872 : inum = dent_node.inum;
84 218126872 : sn = (struct scanned_node *)&dent_node;
85 218126872 : break;
86 : }
87 2065514076 : case UBIFS_DATA_NODE:
88 : {
89 : struct scanned_data_node data_node;
90 :
91 2065514076 : if (!parse_data_node(c, lnum, offs, node, key, &data_node)) {
92 6 : if (fix_problem(c, INVALID_DATA_NODE, NULL))
93 3 : return add_invalid_node(c, key, lnum, offs, iter);
94 : }
95 4131028140 : inum = key_inum(c, key);
96 2065514070 : sn = (struct scanned_node *)&data_node;
97 2065514070 : break;
98 : }
99 : default:
100 0 : ubifs_assert(c, 0);
101 : }
102 :
103 2497737540 : dbg_fsck("construct file(%lu) for %s node, TNC location %d:%d, in %s",
104 : inum, ubifs_get_key_name(key_type(c, key)), sn->lnum, sn->offs,
105 : c->dev_name);
106 4982746920 : return insert_or_update_file(c, tree, sn, key_type(c, key), inum);
107 : }
108 :
109 3059008529 : static int scan_check_leb(struct ubifs_info *c, int lnum, bool is_idx)
110 : {
111 3059008529 : int err = 0;
112 : struct ubifs_scan_leb *sleb;
113 : struct ubifs_scan_node *snod;
114 :
115 3059008529 : if (FSCK(c)->mode == CHECK_MODE)
116 : /* Skip check mode. */
117 : return 0;
118 :
119 3057289365 : ubifs_assert(c, lnum >= c->main_first);
120 6114578730 : if (test_bit(lnum - c->main_first, FSCK(c)->used_lebs))
121 : return 0;
122 :
123 4332996 : sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0);
124 4332996 : if (IS_ERR(sleb)) {
125 567 : err = PTR_ERR(sleb);
126 567 : if (test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED))
127 567 : err = 1;
128 : return err;
129 : }
130 :
131 6471007679 : list_for_each_entry(snod, &sleb->nodes, list) {
132 6466675278 : if (is_idx) {
133 2454526693 : if (snod->type != UBIFS_IDX_NODE) {
134 : err = 1;
135 : goto out;
136 : }
137 : } else {
138 4012148585 : if (snod->type == UBIFS_IDX_NODE) {
139 : err = 1;
140 : goto out;
141 : }
142 : }
143 : }
144 :
145 4332401 : set_bit(lnum - c->main_first, FSCK(c)->used_lebs);
146 :
147 4332429 : out:
148 4332429 : ubifs_scan_destroy(sleb);
149 4332429 : return err;
150 : }
151 :
152 2491571234 : static int check_leaf(struct ubifs_info *c, struct ubifs_zbranch *zbr,
153 : void *priv)
154 : {
155 : void *node;
156 2491571234 : struct iteration_info *iter = (struct iteration_info *)priv;
157 2491571234 : union ubifs_key *key = &zbr->key;
158 2491571234 : int lnum = zbr->lnum, offs = zbr->offs, len = zbr->len, err = 0;
159 :
160 2491571234 : if (len < UBIFS_CH_SZ) {
161 0 : ubifs_err(c, "bad leaf length %d (LEB %d:%d)",
162 : len, lnum, offs);
163 : set_failure_reason_callback(c, FR_TNC_CORRUPTED);
164 : return -EINVAL;
165 : }
166 7266968991 : if (key_type(c, key) != UBIFS_INO_KEY &&
167 2501963909 : key_type(c, key) != UBIFS_DATA_KEY &&
168 290822751 : key_type(c, key) != UBIFS_DENT_KEY &&
169 72685365 : key_type(c, key) != UBIFS_XENT_KEY) {
170 0 : ubifs_err(c, "bad key type %d (LEB %d:%d)",
171 : key_type(c, key), lnum, offs);
172 : set_failure_reason_callback(c, FR_TNC_CORRUPTED);
173 : return -EINVAL;
174 : }
175 :
176 4983142468 : if (test_bit(lnum - c->main_first, iter->corrupted_lebs)) {
177 12152 : if (fix_problem(c, SCAN_CORRUPTED, zbr))
178 : /* All nodes in corrupted LEB should be removed. */
179 12152 : return add_invalid_node(c, key, lnum, offs, iter);
180 : return 0;
181 : }
182 :
183 2491559082 : err = scan_check_leb(c, lnum, false);
184 2491559082 : if (err < 0) {
185 : return err;
186 2491559082 : } else if (err) {
187 946 : set_bit(lnum - c->main_first, iter->corrupted_lebs);
188 473 : if (fix_problem(c, SCAN_CORRUPTED, zbr))
189 458 : return add_invalid_node(c, key, lnum, offs, iter);
190 : return 0;
191 : }
192 :
193 2491558609 : node = kmalloc(len, GFP_NOFS);
194 2491558609 : if (!node)
195 : return -ENOMEM;
196 :
197 2491558609 : err = ubifs_tnc_read_node(c, zbr, node);
198 2491558607 : if (err) {
199 185010 : if (test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED)) {
200 185010 : if (fix_problem(c, TNC_DATA_CORRUPTED, NULL))
201 184925 : err = add_invalid_node(c, key, lnum, offs, iter);
202 : }
203 : goto out;
204 : }
205 :
206 2491373597 : err = construct_file(c, key, lnum, offs, node, iter);
207 :
208 2491558480 : out:
209 2491558480 : kfree(node);
210 2491558480 : return err;
211 : }
212 :
213 567519542 : static int check_znode(struct ubifs_info *c, struct ubifs_znode *znode,
214 : __unused void *priv)
215 : {
216 : int err;
217 : const struct ubifs_zbranch *zbr;
218 :
219 567519542 : if (znode->parent)
220 567517964 : zbr = &znode->parent->zbranch[znode->iip];
221 : else
222 1578 : zbr = &c->zroot;
223 :
224 567519542 : if (zbr->lnum == 0) {
225 : /* The znode has been split up. */
226 70095 : ubifs_assert(c, zbr->offs == 0 && zbr->len == 0);
227 : return 0;
228 : }
229 :
230 567449447 : err = scan_check_leb(c, zbr->lnum, true);
231 567449447 : if (err < 0) {
232 : return err;
233 567449447 : } else if (err) {
234 : set_failure_reason_callback(c, FR_TNC_CORRUPTED);
235 : return -EINVAL;
236 : }
237 :
238 : return 0;
239 : }
240 :
241 2052 : static int remove_invalid_nodes(struct ubifs_info *c,
242 : struct list_head *invalid_nodes, int error)
243 : {
244 2052 : int ret = 0;;
245 : struct invalid_node *in;
246 :
247 201734 : while (!list_empty(invalid_nodes)) {
248 197630 : in = list_entry(invalid_nodes->next, struct invalid_node, list);
249 :
250 197630 : if (!error) {
251 176429 : error = ubifs_tnc_remove_node(c, &in->key, in->lnum, in->offs);
252 176429 : if (error) {
253 : /* TNC traversing is finished, any TNC path is accessible */
254 0 : ubifs_assert(c, !get_failure_reason_callback(c));
255 : ret = error;
256 : }
257 : }
258 :
259 395260 : list_del(&in->list);
260 : kfree(in);
261 : }
262 :
263 2052 : return ret;
264 : }
265 :
266 : /**
267 : * traverse_tnc_and_construct_files - traverse TNC and construct all files.
268 : * @c: UBIFS file-system description object
269 : *
270 : * This function does two things by traversing TNC:
271 : * 1. Check all index nodes and non-index nodes, then construct file according
272 : * to scanned non-index nodes and insert file into file tree.
273 : * 2. Make sure that LEB(contains any nodes from TNC) can be scanned by
274 : * ubifs_scan, and the LEB only contains index nodes or non-index nodes.
275 : * Returns zero in case of success, a negative error code in case of failure.
276 : */
277 2196 : int traverse_tnc_and_construct_files(struct ubifs_info *c)
278 : {
279 : int err, ret;
280 : struct iteration_info iter;
281 :
282 2196 : FSCK(c)->scanned_files = RB_ROOT;
283 4392 : FSCK(c)->used_lebs = kcalloc(BITS_TO_LONGS(c->main_lebs),
284 : sizeof(unsigned long), GFP_KERNEL);
285 2196 : if (!FSCK(c)->used_lebs) {
286 0 : err = -ENOMEM;
287 0 : log_err(c, errno, "can not allocate bitmap of used lebs");
288 0 : return err;
289 : }
290 2196 : INIT_LIST_HEAD(&iter.invalid_nodes);
291 4392 : iter.corrupted_lebs = kcalloc(BITS_TO_LONGS(c->main_lebs),
292 : sizeof(unsigned long), GFP_KERNEL);
293 2196 : if (!iter.corrupted_lebs) {
294 0 : err = -ENOMEM;
295 0 : log_err(c, errno, "can not allocate bitmap of corrupted lebs");
296 : goto out;
297 : }
298 :
299 2196 : err = dbg_walk_index(c, check_leaf, check_znode, &iter);
300 :
301 2052 : ret = remove_invalid_nodes(c, &iter.invalid_nodes, err);
302 2052 : if (!err)
303 1578 : err = ret;
304 :
305 2052 : kfree(iter.corrupted_lebs);
306 2052 : out:
307 2052 : if (err) {
308 948 : kfree(FSCK(c)->used_lebs);
309 474 : destroy_file_tree(c, &FSCK(c)->scanned_files);
310 : }
311 : return err;
312 : }
313 :
314 : /**
315 : * update_files_size - Update files' size.
316 : * @c: UBIFS file-system description object
317 : *
318 : * This function updates files' size according to @c->size_tree for check mode.
319 : */
320 1578 : void update_files_size(struct ubifs_info *c)
321 : {
322 : struct rb_node *this;
323 :
324 1578 : if (FSCK(c)->mode != CHECK_MODE) {
325 : /* Other modes(rw) have updated inode size in place. */
326 1546 : dbg_fsck("skip updating files' size%s, in %s",
327 : mode_name(c), c->dev_name);
328 : return;
329 : }
330 :
331 32 : log_out(c, "Update files' size");
332 :
333 32 : this = rb_first(&c->size_tree);
334 64 : while (this) {
335 : struct size_entry *e;
336 :
337 0 : e = rb_entry(this, struct size_entry, rb);
338 0 : this = rb_next(this);
339 :
340 0 : if (e->exists && e->i_size < e->d_size) {
341 : struct scanned_file *file;
342 :
343 0 : file = lookup_file(&FSCK(c)->scanned_files, e->inum);
344 0 : if (file && file->ino.header.exist &&
345 0 : file->ino.size < e->d_size) {
346 0 : dbg_fsck("update file(%lu) size %llu->%llu, in %s",
347 : e->inum, file->ino.size,
348 : (unsigned long long)e->d_size,
349 : c->dev_name);
350 0 : file->ino.size = e->d_size;
351 : }
352 : }
353 :
354 0 : rb_erase(&e->rb, &c->size_tree);
355 : kfree(e);
356 : }
357 : }
358 :
359 : /**
360 : * handle_invalid_files - Handle invalid files.
361 : * @c: UBIFS file-system description object
362 : *
363 : * This function checks and handles invalid files, there are three situations:
364 : * 1. Move unattached(file has no dentries, or file's parent file has invalid
365 : * type) regular file into disconnected list, let subsequent steps to handle
366 : * them with lost+found.
367 : * 2. Make file type be consistent between inode, detries and data nodes by
368 : * deleting dentries or data blocks.
369 : * 3. Delete file for other invalid cases(eg. file has no inode).
370 : *
371 : * Returns zero in case of success, a negative error code in case of failure.
372 : */
373 1578 : int handle_invalid_files(struct ubifs_info *c)
374 : {
375 : int err;
376 : struct rb_node *node;
377 : struct scanned_file *file;
378 1578 : struct rb_root *tree = &FSCK(c)->scanned_files;
379 1578 : LIST_HEAD(tmp_list);
380 :
381 : /* Add all xattr files into a list. */
382 207688493 : for (node = rb_first(tree); node; node = rb_next(node)) {
383 207686915 : file = rb_entry(node, struct scanned_file, rb);
384 :
385 207686915 : if (file->ino.is_xattr)
386 72659107 : list_add(&file->list, &tmp_list);
387 : }
388 :
389 : /*
390 : * Round 1: Traverse xattr files, check whether the xattr file is
391 : * valid, move valid xattr file into corresponding host file's subtree.
392 : */
393 72660643 : while (!list_empty(&tmp_list)) {
394 72659074 : file = list_entry(tmp_list.next, struct scanned_file, list);
395 :
396 145318148 : list_del(&file->list);
397 72659074 : rb_erase(&file->rb, tree);
398 72659074 : err = file_is_valid(c, file, tree, NULL);
399 72659065 : if (err < 0) {
400 0 : destroy_file_content(c, file);
401 0 : kfree(file);
402 0 : return err;
403 72659065 : } else if (!err) {
404 4693 : err = delete_file(c, file);
405 4693 : kfree(file);
406 4693 : if (err)
407 : return err;
408 : }
409 : }
410 :
411 : /* Round 2: Traverse non-xattr files. */
412 135028190 : for (node = rb_first(tree); node; node = rb_next(node)) {
413 135026635 : int is_diconnected = 0;
414 :
415 135026635 : file = rb_entry(node, struct scanned_file, rb);
416 135026635 : err = file_is_valid(c, file, tree, &is_diconnected);
417 135026621 : if (err < 0) {
418 0 : return err;
419 135026621 : } else if (!err) {
420 6115 : if (is_diconnected)
421 1708 : list_add(&file->list, &FSCK(c)->disconnected_files);
422 : else
423 4407 : list_add(&file->list, &tmp_list);
424 : }
425 : }
426 :
427 : /* Delete & remove invalid files. */
428 5962 : while (!list_empty(&tmp_list)) {
429 4407 : file = list_entry(tmp_list.next, struct scanned_file, list);
430 :
431 8814 : list_del(&file->list);
432 4407 : err = delete_file(c, file);
433 4407 : if (err)
434 : return err;
435 4407 : rb_erase(&file->rb, tree);
436 : kfree(file);
437 : }
438 :
439 : /* Remove disconnected file from the file tree. */
440 3263 : list_for_each_entry(file, &FSCK(c)->disconnected_files, list) {
441 1708 : rb_erase(&file->rb, tree);
442 : }
443 :
444 : return 0;
445 : }
446 :
447 : /**
448 : * handle_dentry_tree - Handle unreachable dentries and files.
449 : * @c: UBIFS file-system description object
450 : *
451 : * This function iterates all directory entries and remove those unreachable
452 : * ones. If file has no directory entries, it becomes unreachable:
453 : * 1. If the unreachable file has non-regular type, delete it;
454 : * 2. If the unreachable file has regular type, move it into the
455 : * @FSCK(c)->disconnected_files.
456 : * 'Unreachable' means that a directory entry can not be searched from '/'.
457 : *
458 : * Returns zero in case of success, a negative error code in case of failure.
459 : */
460 1555 : int handle_dentry_tree(struct ubifs_info *c)
461 : {
462 : struct rb_node *node;
463 : struct scanned_file *file;
464 1555 : struct rb_root *tree = &FSCK(c)->scanned_files;
465 1555 : LIST_HEAD(unreachable);
466 :
467 135021955 : for (node = rb_first(tree); node; node = rb_next(node)) {
468 135020400 : file = rb_entry(node, struct scanned_file, rb);
469 :
470 : /*
471 : * Since all xattr files are already attached to corresponding
472 : * host file, there are only non-xattr files in the file tree.
473 : */
474 135020400 : ubifs_assert(c, !file->ino.is_xattr);
475 135020400 : if (!file_is_reachable(c, file, tree))
476 54858 : list_add(&file->list, &unreachable);
477 : }
478 :
479 56413 : while (!list_empty(&unreachable)) {
480 54858 : file = list_entry(unreachable.next, struct scanned_file, list);
481 :
482 109716 : list_del(&file->list);
483 54858 : if (S_ISREG(file->ino.mode)) {
484 : /*
485 : * Move regular type unreachable file into the
486 : * @FSCK(c)->disconnected_files.
487 : */
488 35744 : list_add(&file->list, &FSCK(c)->disconnected_files);
489 17872 : rb_erase(&file->rb, tree);
490 : } else {
491 : /* Delete non-regular type unreachable file. */
492 36986 : int err = delete_file(c, file);
493 36986 : if (err)
494 : return err;
495 36986 : rb_erase(&file->rb, tree);
496 : kfree(file);
497 : }
498 : }
499 :
500 : return 0;
501 : }
502 :
503 : /**
504 : * tnc_is_empty - Check whether the TNC is empty.
505 : * @c: UBIFS file-system description object
506 : *
507 : * Returns %true if the TNC is empty, otherwise %false is returned.
508 : */
509 1553 : bool tnc_is_empty(struct ubifs_info *c)
510 : {
511 : /*
512 : * Check whether the TNC is empty, turn to rebuild_fs if it is empty.
513 : * Can we recreate a new root dir to avoid empty TNC? The answer is no,
514 : * lpt fixing should be done before creating new entry, but lpt fixing
515 : * needs a committing before new dirty data generated to ensure that
516 : * bud data won't be overwritten(bud LEB could become freeable after
517 : * replaying journal, corrected lpt may treat it as a free one to hold
518 : * new data, see details in space checking & correcting step). Then we
519 : * have to create the new root dir after fixing lpt and a committing,
520 : * znode without childs(empty TNC) maybe written on disk at the moment
521 : * of committing, which corrupts the UBIFS image. So we choose to
522 : * rebuild the filesystem if the TNC is empty, this case is equivalent
523 : * to corrupted TNC.
524 : */
525 1553 : return c->zroot.znode->child_cnt == 0;
526 : }
527 :
528 : /**
529 : * check_and_create_root - Check and create root dir.
530 : * @c: UBIFS file-system description object
531 : *
532 : * This function checks whether the root dir is existed, create a new root
533 : * dir if it doesn't exist. Returns zero in case of success, a negative error
534 : * code in case of failure.
535 : */
536 1497 : int check_and_create_root(struct ubifs_info *c)
537 : {
538 : int err;
539 1497 : struct ubifs_inode *ui = ubifs_lookup_by_inum(c, UBIFS_ROOT_INO);
540 :
541 1497 : if (!IS_ERR(ui)) {
542 : /* The root dir is found. */
543 1492 : dbg_fsck("root dir is found, in %s", c->dev_name);
544 1492 : kfree(ui);
545 1492 : return 0;
546 : }
547 :
548 5 : err = PTR_ERR(ui);
549 5 : if (err != -ENOENT)
550 : return err;
551 :
552 5 : fix_problem(c, ROOT_DIR_NOT_FOUND, NULL);
553 5 : dbg_fsck("root dir is lost, create a new one, in %s", c->dev_name);
554 5 : return ubifs_create_root(c);
555 : }
|