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 <getopt.h>
11 : #include <sys/stat.h>
12 :
13 : #include "linux_err.h"
14 : #include "bitops.h"
15 : #include "kmem.h"
16 : #include "ubifs.h"
17 : #include "defs.h"
18 : #include "debug.h"
19 : #include "key.h"
20 : #include "misc.h"
21 : #include "fsck.ubifs.h"
22 :
23 : /**
24 : * scanned_info - nodes and files information from scanning.
25 : * @valid_inos: the tree of scanned inode nodes with 'nlink > 0'
26 : * @del_inos: the tree of scanned inode nodes with 'nlink = 0'
27 : * @valid_dents: the tree of scanned dentry nodes with 'inum > 0'
28 : * @del_dents: the tree of scanned dentry nodes with 'inum = 0'
29 : */
30 : struct scanned_info {
31 : struct rb_root valid_inos;
32 : struct rb_root del_inos;
33 : struct rb_root valid_dents;
34 : struct rb_root del_dents;
35 : };
36 :
37 : /**
38 : * struct idx_entry - index entry.
39 : * @list: link in the list index entries for building index tree
40 : * @key: key
41 : * @name: directory entry name used for sorting colliding keys by name
42 : * @lnum: LEB number
43 : * @offs: offset
44 : * @len: length
45 : *
46 : * The index is recorded as a linked list which is sorted and used to create
47 : * the bottom level of the on-flash index tree. The remaining levels of the
48 : * index tree are each built from the level below.
49 : */
50 : struct idx_entry {
51 : struct list_head list;
52 : union ubifs_key key;
53 : char *name;
54 : int name_len;
55 : int lnum;
56 : int offs;
57 : int len;
58 : };
59 :
60 425 : static int init_rebuild_info(struct ubifs_info *c)
61 : {
62 : int err;
63 :
64 425 : c->sbuf = vmalloc(c->leb_size);
65 425 : if (!c->sbuf) {
66 0 : log_err(c, errno, "can not allocate sbuf");
67 0 : return -ENOMEM;
68 : }
69 850 : FSCK(c)->rebuild = kzalloc(sizeof(struct ubifs_rebuild_info),
70 : GFP_KERNEL);
71 425 : if (!FSCK(c)->rebuild) {
72 0 : err = -ENOMEM;
73 0 : log_err(c, errno, "can not allocate rebuild info");
74 0 : goto free_sbuf;
75 : }
76 425 : FSCK(c)->scanned_files = RB_ROOT;
77 850 : FSCK(c)->used_lebs = kcalloc(BITS_TO_LONGS(c->main_lebs),
78 : sizeof(unsigned long), GFP_KERNEL);
79 425 : if (!FSCK(c)->used_lebs) {
80 0 : err = -ENOMEM;
81 0 : log_err(c, errno, "can not allocate bitmap of used lebs");
82 0 : goto free_rebuild;
83 : }
84 850 : FSCK(c)->lpts = kzalloc(sizeof(struct ubifs_lprops) * c->main_lebs,
85 : GFP_KERNEL);
86 425 : if (!FSCK(c)->lpts) {
87 0 : err = -ENOMEM;
88 0 : log_err(c, errno, "can not allocate lpts");
89 0 : goto free_used_lebs;
90 : }
91 425 : FSCK(c)->rebuild->write_buf = vmalloc(c->leb_size);
92 425 : if (!FSCK(c)->rebuild->write_buf) {
93 0 : err = -ENOMEM;
94 : goto free_lpts;
95 : }
96 425 : FSCK(c)->rebuild->head_lnum = -1;
97 :
98 425 : return 0;
99 :
100 0 : free_lpts:
101 0 : kfree(FSCK(c)->lpts);
102 0 : free_used_lebs:
103 0 : kfree(FSCK(c)->used_lebs);
104 0 : free_rebuild:
105 0 : kfree(FSCK(c)->rebuild);
106 0 : free_sbuf:
107 0 : vfree(c->sbuf);
108 0 : return err;
109 : }
110 :
111 425 : static void destroy_rebuild_info(struct ubifs_info *c)
112 : {
113 425 : vfree(FSCK(c)->rebuild->write_buf);
114 850 : kfree(FSCK(c)->lpts);
115 850 : kfree(FSCK(c)->used_lebs);
116 850 : kfree(FSCK(c)->rebuild);
117 425 : vfree(c->sbuf);
118 425 : }
119 :
120 : /**
121 : * insert_or_update_ino_node - insert or update inode node.
122 : * @c: UBIFS file-system description object
123 : * @new_ino: new inode node
124 : * @tree: a tree to record valid/deleted inode node info
125 : *
126 : * This function inserts @new_ino into the @tree, or updates inode node
127 : * if it already exists in the tree. Returns zero in case of success, a
128 : * negative error code in case of failure.
129 : */
130 36934474 : static int insert_or_update_ino_node(struct ubifs_info *c,
131 : struct scanned_ino_node *new_ino,
132 : struct rb_root *tree)
133 : {
134 : int cmp;
135 36934474 : struct scanned_ino_node *ino_node, *old_ino_node = NULL;
136 36934474 : struct rb_node **p, *parent = NULL;
137 :
138 36934474 : p = &tree->rb_node;
139 625690457 : while (*p) {
140 609537641 : parent = *p;
141 609537641 : ino_node = rb_entry(parent, struct scanned_ino_node, rb);
142 609537641 : cmp = keys_cmp(c, &new_ino->key, &ino_node->key);
143 : if (cmp < 0) {
144 243264215 : p = &(*p)->rb_left;
145 366273426 : } else if (cmp > 0) {
146 345491768 : p = &(*p)->rb_right;
147 : } else {
148 : old_ino_node = ino_node;
149 : break;
150 : }
151 : }
152 36934474 : if (old_ino_node) {
153 20781658 : if (old_ino_node->header.sqnum < new_ino->header.sqnum) {
154 9423507 : size_t len = offsetof(struct scanned_ino_node, rb);
155 :
156 9423507 : memcpy(old_ino_node, new_ino, len);
157 : }
158 : return 0;
159 : }
160 :
161 16152816 : ino_node = kmalloc(sizeof(struct scanned_ino_node), GFP_KERNEL);
162 16152816 : if (!ino_node)
163 : return -ENOMEM;
164 :
165 16152816 : *ino_node = *new_ino;
166 32305632 : rb_link_node(&ino_node->rb, parent, p);
167 16152816 : rb_insert_color(&ino_node->rb, tree);
168 :
169 : return 0;
170 : }
171 :
172 : static int namecmp(const char *a, int la, const char *b, int lb)
173 : {
174 3898462 : int cmp, len = min(la, lb);
175 :
176 3898462 : cmp = memcmp(a, b, len);
177 3898462 : if (cmp)
178 : return cmp;
179 :
180 3898462 : return la - lb;
181 : }
182 :
183 : /**
184 : * insert_or_update_dent_node - insert or update dentry node.
185 : * @c: UBIFS file-system description object
186 : * @new_dent: new dentry node
187 : * @tree: a tree to record valid/deleted dentry node info
188 : *
189 : * This function inserts @new_dent into the @tree, or updates dent node
190 : * if it already exists in the tree. Returns zero in case of success, a
191 : * negative error code in case of failure.
192 : */
193 21288069 : static int insert_or_update_dent_node(struct ubifs_info *c,
194 : struct scanned_dent_node *new_dent,
195 : struct rb_root *tree)
196 : {
197 : int cmp;
198 21288069 : struct scanned_dent_node *dent_node, *old_dent_node = NULL;
199 21288069 : struct rb_node **p, *parent = NULL;
200 :
201 21288069 : p = &tree->rb_node;
202 362322783 : while (*p) {
203 343196362 : parent = *p;
204 343196362 : dent_node = rb_entry(parent, struct scanned_dent_node, rb);
205 367387200 : cmp = keys_cmp(c, &new_dent->key, &dent_node->key);
206 : if (cmp < 0) {
207 152618247 : p = &(*p)->rb_left;
208 190578115 : } else if (cmp > 0) {
209 188416467 : p = &(*p)->rb_right;
210 : } else {
211 6484944 : cmp = namecmp(new_dent->name, new_dent->nlen,
212 4323296 : dent_node->name, dent_node->nlen);
213 2161648 : if (cmp < 0) {
214 0 : p = &(*p)->rb_left;
215 2161648 : } else if (cmp > 0) {
216 0 : p = &(*p)->rb_right;
217 : } else {
218 : old_dent_node = dent_node;
219 : break;
220 : }
221 : }
222 : }
223 21288069 : if (old_dent_node) {
224 2161648 : if (old_dent_node->header.sqnum < new_dent->header.sqnum) {
225 1289045 : size_t len = offsetof(struct scanned_dent_node, rb);
226 :
227 1289045 : memcpy(old_dent_node, new_dent, len);
228 : }
229 : return 0;
230 : }
231 :
232 19126421 : dent_node = kmalloc(sizeof(struct scanned_dent_node), GFP_KERNEL);
233 19126421 : if (!dent_node)
234 : return -ENOMEM;
235 :
236 19126421 : *dent_node = *new_dent;
237 38252842 : rb_link_node(&dent_node->rb, parent, p);
238 19126421 : rb_insert_color(&dent_node->rb, tree);
239 :
240 : return 0;
241 : }
242 :
243 : /**
244 : * process_scanned_node - process scanned node.
245 : * @c: UBIFS file-system description object
246 : * @lnum: logical eraseblock number
247 : * @snod: scanned node
248 : * @si: records nodes and files information during scanning
249 : *
250 : * This function parses, checks and records scanned node information.
251 : * Returns zero in case of success, 1% if the scanned LEB doesn't hold file
252 : * data and should be ignored(eg. index LEB), a negative error code in case
253 : * of failure.
254 : */
255 243980725 : static int process_scanned_node(struct ubifs_info *c, int lnum,
256 : struct ubifs_scan_node *snod,
257 : struct scanned_info *si)
258 : {
259 : ino_t inum;
260 243980725 : int offs = snod->offs;
261 243980725 : void *node = snod->node;
262 243980725 : union ubifs_key *key = &snod->key;
263 : struct rb_root *tree;
264 : struct scanned_node *sn;
265 : struct scanned_ino_node ino_node;
266 : struct scanned_dent_node dent_node;
267 : struct scanned_data_node data_node;
268 : struct scanned_trun_node trun_node;
269 :
270 243980725 : switch (snod->type) {
271 37683772 : case UBIFS_INO_NODE:
272 : {
273 37683772 : if (!parse_ino_node(c, lnum, offs, node, key, &ino_node))
274 : return 0;
275 :
276 36934474 : tree = &si->del_inos;
277 36934474 : if (ino_node.nlink)
278 35656309 : tree = &si->valid_inos;
279 36934474 : return insert_or_update_ino_node(c, &ino_node, tree);
280 : }
281 21288069 : case UBIFS_DENT_NODE:
282 : case UBIFS_XENT_NODE:
283 : {
284 21288069 : if (!parse_dent_node(c, lnum, offs, node, key, &dent_node))
285 : return 0;
286 :
287 21288069 : tree = &si->del_dents;
288 21288069 : if (dent_node.inum)
289 19484009 : tree = &si->valid_dents;
290 21288069 : return insert_or_update_dent_node(c, &dent_node, tree);
291 : }
292 184458321 : case UBIFS_DATA_NODE:
293 : {
294 184458321 : if (!parse_data_node(c, lnum, offs, node, key, &data_node))
295 : return 0;
296 :
297 368916642 : inum = key_inum(c, key);
298 184458321 : sn = (struct scanned_node *)&data_node;
299 184458321 : break;
300 : }
301 327663 : case UBIFS_TRUN_NODE:
302 : {
303 327663 : if (!parse_trun_node(c, lnum, offs, node, key, &trun_node))
304 : return 0;
305 :
306 327663 : inum = le32_to_cpu(((struct ubifs_trun_node *)node)->inum);
307 327663 : sn = (struct scanned_node *)&trun_node;
308 327663 : break;
309 : }
310 222900 : default:
311 222900 : dbg_fsck("skip node type %d, at %d:%d, in %s",
312 : snod->type, lnum, offs, c->dev_name);
313 : return 1;
314 : }
315 :
316 184785984 : tree = &FSCK(c)->scanned_files;
317 369571968 : return insert_or_update_file(c, tree, sn, key_type(c, key), inum);
318 : }
319 :
320 : /**
321 : * destroy_scanned_info - destroy scanned nodes.
322 : * @c: UBIFS file-system description object
323 : * @si: records nodes and files information during scanning
324 : *
325 : * Destroy scanned files and all data/dentry nodes attached to file, destroy
326 : * valid/deleted inode/dentry info.
327 : */
328 425 : static void destroy_scanned_info(struct ubifs_info *c, struct scanned_info *si)
329 : {
330 : struct scanned_ino_node *ino_node;
331 : struct scanned_dent_node *dent_node;
332 : struct rb_node *this;
333 :
334 425 : destroy_file_tree(c, &FSCK(c)->scanned_files);
335 :
336 425 : this = rb_first(&si->valid_inos);
337 1264 : while (this) {
338 414 : ino_node = rb_entry(this, struct scanned_ino_node, rb);
339 414 : this = rb_next(this);
340 :
341 414 : rb_erase(&ino_node->rb, &si->valid_inos);
342 : kfree(ino_node);
343 : }
344 :
345 425 : this = rb_first(&si->del_inos);
346 957 : while (this) {
347 107 : ino_node = rb_entry(this, struct scanned_ino_node, rb);
348 107 : this = rb_next(this);
349 :
350 107 : rb_erase(&ino_node->rb, &si->del_inos);
351 : kfree(ino_node);
352 : }
353 :
354 425 : this = rb_first(&si->valid_dents);
355 1381 : while (this) {
356 531 : dent_node = rb_entry(this, struct scanned_dent_node, rb);
357 531 : this = rb_next(this);
358 :
359 531 : rb_erase(&dent_node->rb, &si->valid_dents);
360 : kfree(dent_node);
361 : }
362 :
363 425 : this = rb_first(&si->del_dents);
364 969 : while (this) {
365 119 : dent_node = rb_entry(this, struct scanned_dent_node, rb);
366 119 : this = rb_next(this);
367 :
368 119 : rb_erase(&dent_node->rb, &si->del_dents);
369 : kfree(dent_node);
370 : }
371 425 : }
372 :
373 : /**
374 : * scan_nodes - scan node information from flash.
375 : * @c: UBIFS file-system description object
376 : * @si: records nodes and files information during scanning
377 : *
378 : * This function scans nodes from flash, all ino/dent nodes are split
379 : * into valid tree and deleted tree, all trun/data nodes are collected
380 : * into file, the file is inserted into @FSCK(c)->scanned_files.
381 : */
382 425 : static int scan_nodes(struct ubifs_info *c, struct scanned_info *si)
383 : {
384 425 : int lnum, err = 0;
385 : struct ubifs_scan_leb *sleb;
386 : struct ubifs_scan_node *snod;
387 :
388 714832 : for (lnum = c->main_first; lnum < c->leb_cnt; ++lnum) {
389 714408 : dbg_fsck("scan nodes at LEB %d, in %s", lnum, c->dev_name);
390 :
391 714408 : sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1);
392 714408 : if (IS_ERR(sleb)) {
393 2099 : if (PTR_ERR(sleb) != -EUCLEAN)
394 1 : return PTR_ERR(sleb);
395 :
396 2098 : sleb = ubifs_recover_leb(c, lnum, 0, c->sbuf, -1);
397 2098 : if (IS_ERR(sleb)) {
398 2098 : if (PTR_ERR(sleb) != -EUCLEAN)
399 0 : return PTR_ERR(sleb);
400 :
401 : /* This LEB holds corrupted data, abandon it. */
402 2098 : continue;
403 : }
404 : }
405 :
406 244470134 : list_for_each_entry(snod, &sleb->nodes, list) {
407 243980725 : if (snod->sqnum > c->max_sqnum)
408 6443344 : c->max_sqnum = snod->sqnum;
409 :
410 243980725 : err = process_scanned_node(c, lnum, snod, si);
411 243980725 : if (err < 0) {
412 0 : log_err(c, 0, "process node failed at LEB %d, err %d",
413 : lnum, err);
414 0 : ubifs_scan_destroy(sleb);
415 0 : goto out;
416 243980725 : } else if (err == 1) {
417 : err = 0;
418 : break;
419 : }
420 : }
421 :
422 712309 : ubifs_scan_destroy(sleb);
423 : }
424 :
425 424 : out:
426 : return err;
427 : }
428 :
429 : static struct scanned_ino_node *
430 1119870 : lookup_valid_ino_node(struct ubifs_info *c, struct scanned_info *si,
431 : struct scanned_ino_node *target)
432 : {
433 : int cmp;
434 : struct scanned_ino_node *ino_node;
435 : struct rb_node *p;
436 :
437 1119870 : p = si->valid_inos.rb_node;
438 17024788 : while (p) {
439 17018327 : ino_node = rb_entry(p, struct scanned_ino_node, rb);
440 17018327 : cmp = keys_cmp(c, &target->key, &ino_node->key);
441 : if (cmp < 0) {
442 7725000 : p = p->rb_left;
443 9293327 : } else if (cmp > 0) {
444 8179918 : p = p->rb_right;
445 : } else {
446 1113409 : if (target->header.sqnum > ino_node->header.sqnum)
447 : return ino_node;
448 : else
449 : return NULL;
450 : }
451 : }
452 :
453 : return NULL;
454 : }
455 :
456 : static struct scanned_dent_node *
457 1801595 : lookup_valid_dent_node(struct ubifs_info *c, struct scanned_info *si,
458 : struct scanned_dent_node *target)
459 : {
460 : int cmp;
461 : struct scanned_dent_node *dent_node;
462 : struct rb_node *p;
463 :
464 1801595 : p = si->valid_dents.rb_node;
465 25699569 : while (p) {
466 25634788 : dent_node = rb_entry(p, struct scanned_dent_node, rb);
467 27632767 : cmp = keys_cmp(c, &target->key, &dent_node->key);
468 : if (cmp < 0) {
469 12776255 : p = p->rb_left;
470 12858533 : } else if (cmp > 0) {
471 11121719 : p = p->rb_right;
472 : } else {
473 5210442 : cmp = namecmp(target->name, target->nlen,
474 3473628 : dent_node->name, dent_node->nlen);
475 1736814 : if (cmp < 0) {
476 0 : p = p->rb_left;
477 1736814 : } else if (cmp > 0) {
478 0 : p = p->rb_right;
479 : } else {
480 3473628 : if (target->header.sqnum >
481 1736814 : dent_node->header.sqnum)
482 : return dent_node;
483 : else
484 : return NULL;
485 : }
486 : }
487 : }
488 :
489 : return NULL;
490 : }
491 :
492 138742761 : static void update_lpt(struct ubifs_info *c, struct scanned_node *sn,
493 : bool deleted)
494 : {
495 138742761 : int index = sn->lnum - c->main_first;
496 138742761 : int pos = sn->offs + ALIGN(sn->len, 8);
497 :
498 277485522 : set_bit(index, FSCK(c)->used_lebs);
499 138742761 : FSCK(c)->lpts[index].end = max_t(int, FSCK(c)->lpts[index].end, pos);
500 :
501 138742761 : if (deleted)
502 : return;
503 :
504 136700406 : FSCK(c)->lpts[index].used += ALIGN(sn->len, 8);
505 : }
506 :
507 : /**
508 : * remove_del_nodes - remove deleted nodes from valid node tree.
509 : * @c: UBIFS file-system description object
510 : * @si: records nodes and files information during scanning
511 : *
512 : * This function compares sqnum between deleted node and corresponding valid
513 : * node, removes valid node from tree if the sqnum of deleted node is bigger.
514 : * Deleted ino/dent nodes will be removed from @si->del_inos/@si->del_dents
515 : * after this function finished.
516 : */
517 424 : static void remove_del_nodes(struct ubifs_info *c, struct scanned_info *si)
518 : {
519 : struct scanned_ino_node *del_ino_node, *valid_ino_node;
520 : struct scanned_dent_node *del_dent_node, *valid_dent_node;
521 : struct rb_node *this;
522 :
523 424 : this = rb_first(&si->del_inos);
524 1120718 : while (this) {
525 1119870 : del_ino_node = rb_entry(this, struct scanned_ino_node, rb);
526 1119870 : this = rb_next(this);
527 :
528 1119870 : valid_ino_node = lookup_valid_ino_node(c, si, del_ino_node);
529 1119870 : if (valid_ino_node) {
530 147562 : update_lpt(c, &del_ino_node->header, true);
531 147562 : rb_erase(&valid_ino_node->rb, &si->valid_inos);
532 : kfree(valid_ino_node);
533 : }
534 :
535 1119870 : rb_erase(&del_ino_node->rb, &si->del_inos);
536 : kfree(del_ino_node);
537 : }
538 :
539 424 : this = rb_first(&si->del_dents);
540 1802443 : while (this) {
541 1801595 : del_dent_node = rb_entry(this, struct scanned_dent_node, rb);
542 1801595 : this = rb_next(this);
543 :
544 1801595 : valid_dent_node = lookup_valid_dent_node(c, si, del_dent_node);
545 1801595 : if (valid_dent_node) {
546 1731648 : update_lpt(c, &del_dent_node->header, true);
547 1731648 : rb_erase(&valid_dent_node->rb, &si->valid_dents);
548 : kfree(valid_dent_node);
549 : }
550 :
551 1801595 : rb_erase(&del_dent_node->rb, &si->del_dents);
552 : kfree(del_dent_node);
553 : }
554 424 : }
555 :
556 : /**
557 : * add_valid_nodes_into_file - add valid nodes into file.
558 : * @c: UBIFS file-system description object
559 : * @si: records nodes and files information during scanning
560 : *
561 : * This function adds valid nodes into corresponding file, all valid ino/dent
562 : * nodes will be removed from @si->valid_inos/@si->valid_dents if the function
563 : * is executed successfully.
564 : */
565 424 : static int add_valid_nodes_into_file(struct ubifs_info *c,
566 : struct scanned_info *si)
567 : {
568 : int err, type;
569 : ino_t inum;
570 : struct scanned_node *sn;
571 : struct scanned_ino_node *ino_node;
572 : struct scanned_dent_node *dent_node;
573 : struct rb_node *this;
574 424 : struct rb_root *tree = &FSCK(c)->scanned_files;
575 :
576 424 : this = rb_first(&si->valid_inos);
577 14885711 : while (this) {
578 14884863 : ino_node = rb_entry(this, struct scanned_ino_node, rb);
579 14884863 : this = rb_next(this);
580 :
581 14884863 : sn = (struct scanned_node *)ino_node;
582 29769726 : type = key_type(c, &ino_node->key);
583 29769726 : inum = key_inum(c, &ino_node->key);
584 14884863 : err = insert_or_update_file(c, tree, sn, type, inum);
585 14884863 : if (err)
586 : return err;
587 :
588 14884863 : rb_erase(&ino_node->rb, &si->valid_inos);
589 : kfree(ino_node);
590 : }
591 :
592 424 : this = rb_first(&si->valid_dents);
593 15593376 : while (this) {
594 15592528 : dent_node = rb_entry(this, struct scanned_dent_node, rb);
595 15592528 : this = rb_next(this);
596 :
597 15592528 : sn = (struct scanned_node *)dent_node;
598 15592528 : inum = dent_node->inum;
599 31185056 : type = key_type(c, &dent_node->key);
600 15592528 : err = insert_or_update_file(c, tree, sn, type, inum);
601 15592528 : if (err)
602 : return err;
603 :
604 15592528 : rb_erase(&dent_node->rb, &si->valid_dents);
605 : kfree(dent_node);
606 : }
607 :
608 : return 0;
609 : }
610 :
611 : /**
612 : * filter_invalid_files - filter out invalid files.
613 : * @c: UBIFS file-system description object
614 : *
615 : * This function filters out invalid files(eg. inconsistent types between
616 : * inode and dentry node, or missing inode/dentry node, or encrypted inode
617 : * has no encryption related xattrs, etc.).
618 : */
619 424 : static void filter_invalid_files(struct ubifs_info *c)
620 : {
621 : struct rb_node *node;
622 : struct scanned_file *file;
623 424 : struct rb_root *tree = &FSCK(c)->scanned_files;
624 424 : LIST_HEAD(tmp_list);
625 :
626 : /* Add all xattr files into a list. */
627 15086055 : for (node = rb_first(tree); node; node = rb_next(node)) {
628 15085631 : file = rb_entry(node, struct scanned_file, rb);
629 :
630 15085631 : if (file->ino.is_xattr)
631 4657973 : list_add(&file->list, &tmp_list);
632 : }
633 :
634 : /*
635 : * Round 1: Traverse xattr files, check whether the xattr file is
636 : * valid, move valid xattr file into corresponding host file's subtree.
637 : */
638 4658397 : while (!list_empty(&tmp_list)) {
639 4657973 : file = list_entry(tmp_list.next, struct scanned_file, list);
640 :
641 9315946 : list_del(&file->list);
642 4657973 : rb_erase(&file->rb, tree);
643 4657973 : if (!file_is_valid(c, file, tree, NULL)) {
644 112115 : destroy_file_content(c, file);
645 : kfree(file);
646 : }
647 : }
648 :
649 : /* Round 2: Traverse non-xattr files. */
650 10428082 : for (node = rb_first(tree); node; node = rb_next(node)) {
651 10427658 : file = rb_entry(node, struct scanned_file, rb);
652 :
653 10427658 : if (!file_is_valid(c, file, tree, NULL))
654 451261 : list_add(&file->list, &tmp_list);
655 : }
656 :
657 : /* Remove invalid files. */
658 451685 : while (!list_empty(&tmp_list)) {
659 451261 : file = list_entry(tmp_list.next, struct scanned_file, list);
660 :
661 902522 : list_del(&file->list);
662 451261 : destroy_file_content(c, file);
663 451261 : rb_erase(&file->rb, tree);
664 : kfree(file);
665 : }
666 424 : }
667 :
668 : /**
669 : * extract_dentry_tree - extract reachable directory entries.
670 : * @c: UBIFS file-system description object
671 : *
672 : * This function iterates all directory entries and remove those
673 : * unreachable ones. 'Unreachable' means that a directory entry can
674 : * not be searched from '/'.
675 : */
676 424 : static void extract_dentry_tree(struct ubifs_info *c)
677 : {
678 : struct rb_node *node;
679 : struct scanned_file *file;
680 424 : struct rb_root *tree = &FSCK(c)->scanned_files;
681 424 : LIST_HEAD(unreachable);
682 :
683 9976821 : for (node = rb_first(tree); node; node = rb_next(node)) {
684 9976397 : file = rb_entry(node, struct scanned_file, rb);
685 :
686 : /*
687 : * Since all xattr files are already attached to corresponding
688 : * host file, there are only non-xattr files in the file tree.
689 : */
690 9976397 : ubifs_assert(c, !file->ino.is_xattr);
691 9976397 : if (!file_is_reachable(c, file, tree))
692 1920988 : list_add(&file->list, &unreachable);
693 : }
694 :
695 : /* Remove unreachable files. */
696 1921412 : while (!list_empty(&unreachable)) {
697 1920988 : file = list_entry(unreachable.next, struct scanned_file, list);
698 :
699 1920988 : dbg_fsck("remove unreachable file %lu, in %s",
700 : file->inum, c->dev_name);
701 3841976 : list_del(&file->list);
702 1920988 : destroy_file_content(c, file);
703 1920988 : rb_erase(&file->rb, tree);
704 : kfree(file);
705 : }
706 424 : }
707 :
708 1 : static void init_root_ino(struct ubifs_info *c, struct ubifs_ino_node *ino)
709 : {
710 : __le64 tmp_le64;
711 :
712 : /* Create default root inode */
713 2 : ino_key_init_flash(c, &ino->key, UBIFS_ROOT_INO);
714 1 : ino->ch.node_type = UBIFS_INO_NODE;
715 1 : ino->creat_sqnum = cpu_to_le64(++c->max_sqnum);
716 1 : ino->nlink = cpu_to_le32(2);
717 1 : tmp_le64 = cpu_to_le64(time(NULL));
718 1 : ino->atime_sec = tmp_le64;
719 1 : ino->ctime_sec = tmp_le64;
720 1 : ino->mtime_sec = tmp_le64;
721 1 : ino->atime_nsec = 0;
722 1 : ino->ctime_nsec = 0;
723 1 : ino->mtime_nsec = 0;
724 1 : ino->mode = cpu_to_le32(S_IFDIR | S_IRUGO | S_IWUSR | S_IXUGO);
725 1 : ino->size = cpu_to_le64(UBIFS_INO_NODE_SZ);
726 : /* Set compression enabled by default */
727 1 : ino->flags = cpu_to_le32(UBIFS_COMPR_FL);
728 1 : }
729 :
730 : /**
731 : * flush_write_buf - flush write buffer.
732 : * @c: UBIFS file-system description object
733 : *
734 : * This function flush write buffer to LEB @FSCK(c)->rebuild->head_lnum, then
735 : * set @FSCK(c)->rebuild->head_lnum to '-1'.
736 : */
737 19469 : static int flush_write_buf(struct ubifs_info *c)
738 : {
739 : int len, pad, err;
740 :
741 19469 : if (!FSCK(c)->rebuild->head_offs)
742 : return 0;
743 :
744 19469 : len = ALIGN(FSCK(c)->rebuild->head_offs, c->min_io_size);
745 19469 : pad = len - FSCK(c)->rebuild->head_offs;
746 19469 : if (pad)
747 10902 : ubifs_pad(c, FSCK(c)->rebuild->write_buf +
748 5451 : FSCK(c)->rebuild->head_offs, pad);
749 :
750 19469 : err = ubifs_leb_write(c, FSCK(c)->rebuild->head_lnum,
751 19469 : FSCK(c)->rebuild->write_buf, 0, len);
752 19469 : if (err)
753 : return err;
754 :
755 19469 : if (FSCK(c)->rebuild->need_update_lpt) {
756 19468 : int index = FSCK(c)->rebuild->head_lnum - c->main_first;
757 :
758 19468 : FSCK(c)->lpts[index].free = c->leb_size - len;
759 19468 : FSCK(c)->lpts[index].dirty = pad;
760 19468 : FSCK(c)->lpts[index].flags = LPROPS_INDEX;
761 : }
762 :
763 19469 : FSCK(c)->rebuild->head_lnum = -1;
764 :
765 19469 : return 0;
766 : }
767 :
768 : /**
769 : * reserve_space - reserve enough space to write data.
770 : * @c: UBIFS file-system description object
771 : * @len: the length of written data
772 : * @lnum: the write LEB number is returned here
773 : * @offs: the write pos in LEB is returned here
774 : *
775 : * This function finds target position <@lnum, @offs> to write data with
776 : * length of @len.
777 : */
778 13782458 : static int reserve_space(struct ubifs_info *c, int len, int *lnum, int *offs)
779 : {
780 : int err, new_lnum;
781 :
782 13782458 : if (FSCK(c)->rebuild->head_lnum == -1) {
783 160 : get_new:
784 19470 : new_lnum = get_free_leb(c);
785 19470 : if (new_lnum < 0)
786 : return new_lnum;
787 :
788 19470 : err = ubifs_leb_unmap(c, new_lnum);
789 19470 : if (err)
790 : return err;
791 :
792 19469 : FSCK(c)->rebuild->head_lnum = new_lnum;
793 19469 : FSCK(c)->rebuild->head_offs = 0;
794 : }
795 :
796 13801767 : if (len > c->leb_size - FSCK(c)->rebuild->head_offs) {
797 19310 : err = flush_write_buf(c);
798 19310 : if (err)
799 : return err;
800 :
801 : goto get_new;
802 : }
803 :
804 13782457 : *lnum = FSCK(c)->rebuild->head_lnum;
805 13782457 : *offs = FSCK(c)->rebuild->head_offs;
806 13782457 : FSCK(c)->rebuild->head_offs += ALIGN(len, 8);
807 :
808 13782457 : return 0;
809 : }
810 :
811 13782457 : static void copy_node_data(struct ubifs_info *c, void *node, int offs, int len)
812 : {
813 13782457 : memcpy(FSCK(c)->rebuild->write_buf + offs, node, len);
814 13782457 : memset(FSCK(c)->rebuild->write_buf + offs + len, 0xff, ALIGN(len, 8) - len);
815 13782457 : }
816 :
817 : /**
818 : * create_root - create root dir.
819 : * @c: UBIFS file-system description object
820 : *
821 : * This function creates root dir.
822 : */
823 1 : static int create_root(struct ubifs_info *c)
824 : {
825 : int err, lnum, offs;
826 : struct ubifs_ino_node *ino;
827 : struct scanned_file *file;
828 :
829 2 : ino = kzalloc(ALIGN(UBIFS_INO_NODE_SZ, c->min_io_size), GFP_KERNEL);
830 1 : if (!ino)
831 : return -ENOMEM;
832 :
833 1 : c->max_sqnum = 0;
834 1 : c->highest_inum = UBIFS_FIRST_INO;
835 1 : init_root_ino(c, ino);
836 1 : err = ubifs_prepare_node_hmac(c, ino, UBIFS_INO_NODE_SZ, -1, 1);
837 1 : if (err)
838 : goto out;
839 :
840 1 : err = reserve_space(c, UBIFS_INO_NODE_SZ, &lnum, &offs);
841 1 : if (err)
842 : goto out;
843 :
844 1 : copy_node_data(c, ino, offs, UBIFS_INO_NODE_SZ);
845 :
846 1 : err = flush_write_buf(c);
847 1 : if (err)
848 : goto out;
849 :
850 1 : file = kzalloc(sizeof(struct scanned_file), GFP_KERNEL);
851 1 : if (!file) {
852 : err = -ENOMEM;
853 : goto out;
854 : }
855 :
856 1 : file->inum = UBIFS_ROOT_INO;
857 1 : file->dent_nodes = RB_ROOT;
858 1 : file->data_nodes = RB_ROOT;
859 2 : INIT_LIST_HEAD(&file->list);
860 :
861 1 : file->ino.header.exist = true;
862 1 : file->ino.header.lnum = lnum;
863 1 : file->ino.header.offs = offs;
864 1 : file->ino.header.len = UBIFS_INO_NODE_SZ;
865 1 : file->ino.header.sqnum = le64_to_cpu(ino->ch.sqnum);
866 2 : ino_key_init(c, &file->ino.key, UBIFS_ROOT_INO);
867 1 : file->ino.is_xattr = le32_to_cpu(ino->flags) & UBIFS_XATTR_FL;
868 1 : file->ino.mode = le32_to_cpu(ino->mode);
869 1 : file->calc_nlink = file->ino.nlink = le32_to_cpu(ino->nlink);
870 1 : file->calc_xcnt = file->ino.xcnt = le32_to_cpu(ino->xattr_cnt);
871 1 : file->calc_xsz = file->ino.xsz = le32_to_cpu(ino->xattr_size);
872 1 : file->calc_xnms = file->ino.xnms = le32_to_cpu(ino->xattr_names);
873 1 : file->calc_size = file->ino.size = le64_to_cpu(ino->size);
874 :
875 2 : rb_link_node(&file->rb, NULL, &FSCK(c)->scanned_files.rb_node);
876 1 : rb_insert_color(&file->rb, &FSCK(c)->scanned_files);
877 :
878 1 : out:
879 1 : kfree(ino);
880 1 : return err;
881 : }
882 :
883 3794 : static const char *get_file_name(struct ubifs_info *c, struct scanned_file *file)
884 : {
885 : static char name[UBIFS_MAX_NLEN + 1];
886 : struct rb_node *node;
887 : struct scanned_dent_node *dent_node;
888 :
889 3794 : node = rb_first(&file->dent_nodes);
890 3794 : if (!node) {
891 16 : ubifs_assert(c, file->inum == UBIFS_ROOT_INO);
892 : return "/";
893 : }
894 :
895 3778 : if (c->encrypted && !file->ino.is_xattr)
896 : /* Encrypted file name. */
897 : return "<encrypted>";
898 :
899 : /* Get name from any one dentry. */
900 3778 : dent_node = rb_entry(node, struct scanned_dent_node, rb);
901 3778 : memcpy(name, dent_node->name, dent_node->nlen);
902 : /* @dent->name could be non '\0' terminated. */
903 3778 : name[dent_node->nlen] = '\0';
904 3778 : return name;
905 : }
906 :
907 136700406 : static int parse_node_info(struct ubifs_info *c, struct scanned_node *sn,
908 : union ubifs_key *key, char *name, int name_len,
909 : struct list_head *idx_list, int *idx_cnt)
910 : {
911 : struct idx_entry *e;
912 :
913 136863551 : update_lpt(c, sn, idx_cnt == NULL);
914 :
915 136700406 : if (idx_cnt == NULL)
916 : /* Skip truncation node. */
917 : return 0;
918 :
919 136700406 : e = kmalloc(sizeof(struct idx_entry), GFP_KERNEL);
920 136700406 : if (!e)
921 : return -ENOMEM;
922 :
923 273400812 : key_copy(c, key, &e->key);
924 136700406 : e->name = name;
925 136700406 : e->name_len = name_len;
926 136700406 : e->lnum = sn->lnum;
927 136700406 : e->offs = sn->offs;
928 136700406 : e->len = sn->len;
929 273400812 : list_add_tail(&e->list, idx_list);
930 136700406 : *idx_cnt = *idx_cnt + 1;
931 :
932 136700406 : return 0;
933 : }
934 :
935 13782457 : static int add_idx_node(struct ubifs_info *c, struct ubifs_idx_node *idx,
936 : union ubifs_key *key, int child_cnt,
937 : struct idx_entry *e)
938 : {
939 : int err, lnum, offs, len;
940 :
941 13782457 : len = ubifs_idx_node_sz(c, child_cnt);
942 13782457 : ubifs_prepare_node(c, idx, len, 0);
943 :
944 13782457 : err = reserve_space(c, len, &lnum, &offs);
945 13782457 : if (err)
946 : return err;
947 :
948 13782456 : copy_node_data(c, idx, offs, len);
949 :
950 13782456 : c->calc_idx_sz += ALIGN(len, 8);
951 :
952 : /* The last index node written will be the root */
953 13782456 : c->zroot.lnum = lnum;
954 13782456 : c->zroot.offs = offs;
955 13782456 : c->zroot.len = len;
956 :
957 27564912 : key_copy(c, key, &e->key);
958 13782456 : e->lnum = lnum;
959 13782456 : e->offs = offs;
960 13782456 : e->len = len;
961 :
962 13782456 : return err;
963 : }
964 :
965 1719058355 : static int cmp_idx(void *priv, const struct list_head *a,
966 : const struct list_head *b)
967 : {
968 : int cmp;
969 1719058355 : struct ubifs_info *c = priv;
970 : struct idx_entry *ia, *ib;
971 :
972 1719058355 : if (a == b)
973 : return 0;
974 :
975 1719058355 : ia = list_entry(a, struct idx_entry, list);
976 1719058355 : ib = list_entry(b, struct idx_entry, list);
977 :
978 1719058355 : cmp = keys_cmp(c, &ia->key, &ib->key);
979 : if (cmp)
980 : return cmp;
981 :
982 0 : return namecmp(ia->name, ia->name_len, ib->name, ib->name_len);
983 : }
984 :
985 : /**
986 : * build_tnc - construct TNC and write it into flash.
987 : * @c: UBIFS file-system description object
988 : * @lower_idxs: leaf entries of TNC
989 : * @lower_cnt: the count of @lower_idxs
990 : *
991 : * This function builds TNC according to @lower_idxs and writes all index
992 : * nodes into flash.
993 : */
994 159 : static int build_tnc(struct ubifs_info *c, struct list_head *lower_idxs,
995 : int lower_cnt)
996 : {
997 159 : int i, j, err, upper_cnt, child_cnt, idx_sz, level = 0;
998 159 : struct idx_entry *pe, *tmp_e, *e = NULL;
999 : struct ubifs_idx_node *idx;
1000 : struct ubifs_branch *br;
1001 : union ubifs_key key;
1002 159 : LIST_HEAD(upper_idxs);
1003 :
1004 318 : idx_sz = ubifs_idx_node_sz(c, c->fanout);
1005 159 : idx = kmalloc(idx_sz, GFP_KERNEL);
1006 159 : if (!idx)
1007 : return -ENOMEM;
1008 :
1009 159 : list_sort(c, lower_idxs, cmp_idx);
1010 159 : FSCK(c)->rebuild->need_update_lpt = true;
1011 :
1012 159 : ubifs_assert(c, lower_cnt != 0);
1013 :
1014 : do {
1015 859 : upper_cnt = lower_cnt / c->fanout;
1016 859 : if (lower_cnt % c->fanout)
1017 776 : upper_cnt += 1;
1018 859 : e = list_first_entry(lower_idxs, struct idx_entry, list);
1019 :
1020 13783315 : for (i = 0; i < upper_cnt; i++) {
1021 13782457 : if (i == upper_cnt - 1) {
1022 858 : child_cnt = lower_cnt % c->fanout;
1023 858 : if (child_cnt == 0)
1024 83 : child_cnt = c->fanout;
1025 : } else
1026 13781599 : child_cnt = c->fanout;
1027 :
1028 27564914 : key_copy(c, &e->key, &key);
1029 13782457 : memset(idx, 0, idx_sz);
1030 13782457 : idx->ch.node_type = UBIFS_IDX_NODE;
1031 13782457 : idx->child_cnt = cpu_to_le16(child_cnt);
1032 13782457 : idx->level = cpu_to_le16(level);
1033 124038828 : for (j = 0; j < child_cnt; j++) {
1034 110256371 : ubifs_assert(c,
1035 : !list_entry_is_head(e, lower_idxs, list));
1036 110256371 : br = ubifs_idx_branch(c, idx, j);
1037 220512742 : key_write_idx(c, &e->key, &br->key);
1038 110256371 : br->lnum = cpu_to_le32(e->lnum);
1039 110256371 : br->offs = cpu_to_le32(e->offs);
1040 110256371 : br->len = cpu_to_le32(e->len);
1041 110256371 : e = list_next_entry(e, list);
1042 : }
1043 :
1044 13782457 : pe = kmalloc(sizeof(struct idx_entry), GFP_KERNEL);
1045 13782457 : if (!pe) {
1046 : err = -ENOMEM;
1047 : goto out;
1048 : }
1049 :
1050 13782457 : err = add_idx_node(c, idx, &key, child_cnt, pe);
1051 13782457 : if (err) {
1052 : kfree(pe);
1053 : goto out;
1054 : }
1055 :
1056 27564912 : list_add_tail(&pe->list, &upper_idxs);
1057 : }
1058 :
1059 858 : level++;
1060 110257221 : list_for_each_entry_safe(e, tmp_e, lower_idxs, list) {
1061 220512726 : list_del(&e->list);
1062 110256363 : kfree(e);
1063 : }
1064 858 : list_splice_init(&upper_idxs, lower_idxs);
1065 858 : lower_cnt = upper_cnt;
1066 858 : } while (lower_cnt > 1);
1067 :
1068 : /* Set the index head */
1069 158 : c->ihead_lnum = FSCK(c)->rebuild->head_lnum;
1070 158 : c->ihead_offs = ALIGN(FSCK(c)->rebuild->head_offs, c->min_io_size);
1071 :
1072 : /* Flush the last index LEB */
1073 158 : err = flush_write_buf(c);
1074 158 : FSCK(c)->rebuild->need_update_lpt = false;
1075 :
1076 159 : out:
1077 184708 : list_for_each_entry_safe(e, tmp_e, lower_idxs, list) {
1078 369098 : list_del(&e->list);
1079 184549 : kfree(e);
1080 : }
1081 159 : list_for_each_entry_safe(e, tmp_e, &upper_idxs, list) {
1082 0 : list_del(&e->list);
1083 0 : kfree(e);
1084 : }
1085 159 : kfree(idx);
1086 159 : return err;
1087 : }
1088 :
1089 10263462 : static int record_file_used_lebs(struct ubifs_info *c,
1090 : struct scanned_file *file,
1091 : struct list_head *idx_list, int *idx_cnt)
1092 : {
1093 : int err;
1094 : struct rb_node *node;
1095 : struct scanned_file *xattr_file;
1096 : struct scanned_dent_node *dent_node;
1097 : struct scanned_data_node *data_node;
1098 :
1099 10263462 : dbg_fsck("recovered file(inum:%lu name:%s type:%s), in %s",
1100 : file->inum, get_file_name(c, file),
1101 : file->ino.is_xattr ? "xattr" :
1102 : ubifs_get_type_name(ubifs_get_dent_type(file->ino.mode)),
1103 : c->dev_name);
1104 10263462 : c->highest_inum = max_t(ino_t, c->highest_inum, file->inum);
1105 :
1106 10263462 : err = parse_node_info(c, &file->ino.header, &file->ino.key,
1107 : NULL, 0, idx_list, idx_cnt);
1108 10263462 : if (err)
1109 : return err;
1110 :
1111 10263462 : if (file->trun.header.exist) {
1112 326290 : err = parse_node_info(c, &file->trun.header, NULL, NULL,
1113 : 0, idx_list, NULL);
1114 : if (err)
1115 : return err;
1116 : }
1117 :
1118 125833707 : for (node = rb_first(&file->data_nodes); node; node = rb_next(node)) {
1119 115570245 : data_node = rb_entry(node, struct scanned_data_node, rb);
1120 :
1121 115570245 : err = parse_node_info(c, &data_node->header, &data_node->key,
1122 : NULL, 0, idx_list, idx_cnt);
1123 115570245 : if (err)
1124 : return err;
1125 : }
1126 :
1127 21130161 : for (node = rb_first(&file->dent_nodes); node; node = rb_next(node)) {
1128 10866699 : dent_node = rb_entry(node, struct scanned_dent_node, rb);
1129 :
1130 21733398 : err = parse_node_info(c, &dent_node->header, &dent_node->key,
1131 21733398 : dent_node->name, dent_node->nlen,
1132 : idx_list, idx_cnt);
1133 10866699 : if (err)
1134 : return err;
1135 : }
1136 :
1137 13161758 : for (node = rb_first(&file->xattr_files); node; node = rb_next(node)) {
1138 2898296 : xattr_file = rb_entry(node, struct scanned_file, rb);
1139 :
1140 2898296 : err = record_file_used_lebs(c, xattr_file, idx_list, idx_cnt);
1141 2898296 : if (err)
1142 : return err;
1143 : }
1144 :
1145 : return err;
1146 : }
1147 :
1148 : /**
1149 : * traverse_files_and_nodes - traverse all nodes from valid files.
1150 : * @c: UBIFS file-system description object
1151 : *
1152 : * This function traverses all nodes from valid files and does following
1153 : * things:
1154 : * 1. If there are no scanned files, create default empty filesystem.
1155 : * 2. Record all used LEBs which may hold useful nodes, then left unused
1156 : * LEBs could be taken for storing new index tree.
1157 : * 3. Re-write data to prevent failed gc scanning in the subsequent mounting
1158 : * process caused by corrupted data.
1159 : * 4. Build TNC.
1160 : */
1161 366 : static int traverse_files_and_nodes(struct ubifs_info *c)
1162 : {
1163 366 : int i, err = 0, idx_cnt = 0;
1164 : struct rb_node *node;
1165 : struct scanned_file *file;
1166 366 : struct rb_root *tree = &FSCK(c)->scanned_files;
1167 : struct idx_entry *ie, *tmp_ie;
1168 366 : LIST_HEAD(idx_list);
1169 :
1170 366 : if (rb_first(tree) == NULL) {
1171 : /* No scanned files. Create root dir. */
1172 1 : log_out(c, "No files found, create empty filesystem");
1173 1 : err = create_root(c);
1174 1 : if (err)
1175 : return err;
1176 : }
1177 :
1178 366 : log_out(c, "Record used LEBs");
1179 7365532 : for (node = rb_first(tree); node; node = rb_next(node)) {
1180 7365166 : file = rb_entry(node, struct scanned_file, rb);
1181 :
1182 7365166 : err = record_file_used_lebs(c, file, &idx_list, &idx_cnt);
1183 7365166 : if (err)
1184 : goto out_idx_list;
1185 : }
1186 :
1187 : /* Re-write data. */
1188 366 : log_out(c, "Re-write data");
1189 365085 : for (i = 0; i < c->main_lebs; ++i) {
1190 : int lnum, len, end;
1191 :
1192 729852 : if (!test_bit(i, FSCK(c)->used_lebs))
1193 204183 : continue;
1194 :
1195 160743 : lnum = i + c->main_first;
1196 160743 : dbg_fsck("re-write LEB %d, in %s", lnum, c->dev_name);
1197 :
1198 160743 : end = FSCK(c)->lpts[i].end;
1199 160743 : len = ALIGN(end, c->min_io_size);
1200 :
1201 160743 : err = ubifs_leb_read(c, lnum, c->sbuf, 0, len, 0);
1202 160743 : if (err && err != -EBADMSG)
1203 : goto out_idx_list;
1204 :
1205 160743 : if (len > end)
1206 73328 : ubifs_pad(c, c->sbuf + end, len - end);
1207 :
1208 160743 : err = ubifs_leb_change(c, lnum, c->sbuf, len);
1209 160743 : if (err)
1210 : goto out_idx_list;
1211 : }
1212 :
1213 : /* Build TNC. */
1214 159 : log_out(c, "Build TNC");
1215 159 : err = build_tnc(c, &idx_list, idx_cnt);
1216 :
1217 573 : out_idx_list:
1218 40042316 : list_for_each_entry_safe(ie, tmp_ie, &idx_list, list) {
1219 80083900 : list_del(&ie->list);
1220 40041950 : kfree(ie);
1221 : }
1222 : return err;
1223 : }
1224 :
1225 294904 : static int calculate_lp(struct ubifs_info *c, int index, int *free, int *dirty,
1226 : __unused int *is_idx)
1227 : {
1228 746938 : if (!test_bit(index, FSCK(c)->used_lebs) ||
1229 157130 : c->gc_lnum == index + c->main_first) {
1230 137932 : *free = c->leb_size;
1231 137932 : *dirty = 0;
1232 156972 : } else if (FSCK(c)->lpts[index].flags & LPROPS_INDEX) {
1233 19468 : *free = FSCK(c)->lpts[index].free;
1234 19468 : *dirty = FSCK(c)->lpts[index].dirty;
1235 : } else {
1236 137504 : int len = ALIGN(FSCK(c)->lpts[index].end, c->min_io_size);
1237 :
1238 137504 : *free = c->leb_size - len;
1239 137504 : *dirty = len - FSCK(c)->lpts[index].used;
1240 :
1241 137504 : if (*dirty == c->leb_size) {
1242 22 : *free = c->leb_size;
1243 22 : *dirty = 0;
1244 : }
1245 : }
1246 :
1247 294904 : return 0;
1248 : }
1249 :
1250 : /**
1251 : * clean_log - clean up log area.
1252 : * @c: UBIFS file-system description object
1253 : *
1254 : * This function cleans up log area, since there is no need to do recovery
1255 : * in next mounting.
1256 : */
1257 158 : static int clean_log(struct ubifs_info *c)
1258 : {
1259 : int lnum, err;
1260 : struct ubifs_cs_node *cs;
1261 :
1262 854 : for (lnum = UBIFS_LOG_LNUM; lnum <= c->log_last; lnum++) {
1263 696 : err = ubifs_leb_unmap(c, lnum);
1264 696 : if (err)
1265 : return err;
1266 : }
1267 :
1268 316 : cs = kzalloc(ALIGN(UBIFS_CS_NODE_SZ, c->min_io_size), GFP_KERNEL);
1269 158 : if (!cs)
1270 : return -ENOMEM;
1271 :
1272 158 : cs->ch.node_type = UBIFS_CS_NODE;
1273 158 : cs->cmt_no = cpu_to_le64(0);
1274 :
1275 158 : err = ubifs_write_node(c, cs, UBIFS_CS_NODE_SZ, UBIFS_LOG_LNUM, 0);
1276 158 : kfree(cs);
1277 158 : if (err)
1278 : return err;
1279 :
1280 158 : return 0;
1281 : }
1282 :
1283 : /**
1284 : * write_master - write master nodes.
1285 : * @c: UBIFS file-system description object
1286 : *
1287 : * This function updates meta information into master node and writes master
1288 : * node into master area.
1289 : */
1290 158 : static int write_master(struct ubifs_info *c)
1291 : {
1292 : int err, lnum;
1293 : struct ubifs_mst_node *mst;
1294 :
1295 316 : mst = kzalloc(c->mst_node_alsz, GFP_KERNEL);
1296 158 : if (!mst)
1297 : return -ENOMEM;
1298 :
1299 158 : mst->ch.node_type = UBIFS_MST_NODE;
1300 158 : mst->log_lnum = cpu_to_le32(UBIFS_LOG_LNUM);
1301 158 : mst->highest_inum = cpu_to_le64(c->highest_inum);
1302 158 : mst->cmt_no = 0;
1303 158 : mst->root_lnum = cpu_to_le32(c->zroot.lnum);
1304 158 : mst->root_offs = cpu_to_le32(c->zroot.offs);
1305 158 : mst->root_len = cpu_to_le32(c->zroot.len);
1306 158 : mst->gc_lnum = cpu_to_le32(c->gc_lnum);
1307 158 : mst->ihead_lnum = cpu_to_le32(c->ihead_lnum);
1308 158 : mst->ihead_offs = cpu_to_le32(c->ihead_offs);
1309 158 : mst->index_size = cpu_to_le64(c->calc_idx_sz);
1310 158 : mst->lpt_lnum = cpu_to_le32(c->lpt_lnum);
1311 158 : mst->lpt_offs = cpu_to_le32(c->lpt_offs);
1312 158 : mst->nhead_lnum = cpu_to_le32(c->nhead_lnum);
1313 158 : mst->nhead_offs = cpu_to_le32(c->nhead_offs);
1314 158 : mst->ltab_lnum = cpu_to_le32(c->ltab_lnum);
1315 158 : mst->ltab_offs = cpu_to_le32(c->ltab_offs);
1316 158 : mst->lsave_lnum = cpu_to_le32(c->lsave_lnum);
1317 158 : mst->lsave_offs = cpu_to_le32(c->lsave_offs);
1318 158 : mst->lscan_lnum = cpu_to_le32(c->main_first);
1319 158 : mst->empty_lebs = cpu_to_le32(c->lst.empty_lebs);
1320 158 : mst->idx_lebs = cpu_to_le32(c->lst.idx_lebs);
1321 158 : mst->leb_cnt = cpu_to_le32(c->leb_cnt);
1322 158 : mst->total_free = cpu_to_le64(c->lst.total_free);
1323 158 : mst->total_dirty = cpu_to_le64(c->lst.total_dirty);
1324 158 : mst->total_used = cpu_to_le64(c->lst.total_used);
1325 158 : mst->total_dead = cpu_to_le64(c->lst.total_dead);
1326 158 : mst->total_dark = cpu_to_le64(c->lst.total_dark);
1327 158 : mst->flags |= cpu_to_le32(UBIFS_MST_NO_ORPHS);
1328 :
1329 158 : lnum = UBIFS_MST_LNUM;
1330 158 : err = ubifs_leb_unmap(c, lnum);
1331 158 : if (err)
1332 : goto out;
1333 158 : err = ubifs_write_node_hmac(c, mst, UBIFS_MST_NODE_SZ, lnum, 0,
1334 : offsetof(struct ubifs_mst_node, hmac));
1335 158 : if (err)
1336 : goto out;
1337 158 : lnum++;
1338 158 : err = ubifs_leb_unmap(c, lnum);
1339 158 : if (err)
1340 : goto out;
1341 158 : err = ubifs_write_node_hmac(c, mst, UBIFS_MST_NODE_SZ, lnum, 0,
1342 : offsetof(struct ubifs_mst_node, hmac));
1343 : if (err)
1344 : goto out;
1345 :
1346 158 : out:
1347 158 : kfree(mst);
1348 :
1349 158 : return err;
1350 : }
1351 :
1352 : /**
1353 : * ubifs_rebuild_filesystem - Rebuild filesystem.
1354 : * @c: UBIFS file-system description object
1355 : *
1356 : * Scanning nodes from UBI volume and rebuild filesystem. Any inconsistent
1357 : * problems or corrupted data will be fixed.
1358 : */
1359 425 : int ubifs_rebuild_filesystem(struct ubifs_info *c)
1360 : {
1361 425 : int err = 0;
1362 : struct scanned_info si;
1363 :
1364 425 : si.valid_inos = si.del_inos = si.valid_dents = si.del_dents = RB_ROOT;
1365 425 : log_out(c, "Start rebuilding filesystem (Notice: dropping data/recovering deleted data can't be awared)");
1366 425 : FSCK(c)->mode = REBUILD_MODE;
1367 :
1368 425 : err = init_rebuild_info(c);
1369 425 : if (err) {
1370 0 : exit_code |= FSCK_ERROR;
1371 0 : return err;
1372 : }
1373 :
1374 : /* Step 1: Scan valid/deleted nodes from volume. */
1375 425 : log_out(c, "Scan nodes");
1376 425 : err = scan_nodes(c, &si);
1377 425 : if (err) {
1378 1 : exit_code |= FSCK_ERROR;
1379 1 : goto out;
1380 : }
1381 :
1382 : /* Step 2: Remove deleted nodes from valid node tree. */
1383 424 : log_out(c, "Remove deleted nodes");
1384 424 : remove_del_nodes(c, &si);
1385 :
1386 : /* Step 3: Add valid nodes into file. */
1387 424 : log_out(c, "Add valid nodes into file");
1388 424 : err = add_valid_nodes_into_file(c, &si);
1389 424 : if (err) {
1390 0 : exit_code |= FSCK_ERROR;
1391 0 : goto out;
1392 : }
1393 :
1394 : /* Step 4: Drop invalid files. */
1395 424 : log_out(c, "Filter invalid files");
1396 424 : filter_invalid_files(c);
1397 :
1398 : /* Step 5: Extract reachable directory entries. */
1399 424 : log_out(c, "Extract reachable files");
1400 424 : extract_dentry_tree(c);
1401 :
1402 : /* Step 6: Check & correct files' information. */
1403 424 : log_out(c, "Check & correct file information");
1404 424 : err = check_and_correct_files(c);
1405 424 : if (err) {
1406 58 : exit_code |= FSCK_ERROR;
1407 58 : goto out;
1408 : }
1409 :
1410 : /*
1411 : * Step 7: Record used LEBs.
1412 : * Step 8: Re-write data to clean corrupted data.
1413 : * Step 9: Build TNC.
1414 : */
1415 366 : err = traverse_files_and_nodes(c);
1416 366 : if (err) {
1417 208 : exit_code |= FSCK_ERROR;
1418 208 : goto out;
1419 : }
1420 :
1421 : /* Step 10. Build LPT. */
1422 158 : log_out(c, "Build LPT");
1423 158 : err = build_lpt(c, calculate_lp, true);
1424 158 : if (err) {
1425 0 : exit_code |= FSCK_ERROR;
1426 0 : goto out;
1427 : }
1428 :
1429 : /* Step 11. Clean up log & orphan. */
1430 158 : log_out(c, "Clean up log & orphan");
1431 158 : err = clean_log(c);
1432 158 : if (err) {
1433 0 : exit_code |= FSCK_ERROR;
1434 0 : goto out;
1435 : }
1436 158 : err = ubifs_clear_orphans(c);
1437 158 : if (err) {
1438 0 : exit_code |= FSCK_ERROR;
1439 0 : goto out;
1440 : }
1441 :
1442 : /* Step 12. Write master node. */
1443 158 : log_out(c, "Write master");
1444 158 : err = write_master(c);
1445 158 : if (err)
1446 0 : exit_code |= FSCK_ERROR;
1447 :
1448 583 : out:
1449 425 : destroy_scanned_info(c, &si);
1450 425 : destroy_rebuild_info(c);
1451 :
1452 425 : return err;
1453 : }
|