1
2
3
4
5
6
7
8
9
10#include <log.h>
11#include <dm/devres.h>
12#include <linux/err.h>
13#include "ubifs.h"
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46static int dbg_check_orphans(struct ubifs_info *c);
47
48
49
50
51
52
53
54
55
56int ubifs_add_orphan(struct ubifs_info *c, ino_t inum)
57{
58 struct ubifs_orphan *orphan, *o;
59 struct rb_node **p, *parent = NULL;
60
61 orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_NOFS);
62 if (!orphan)
63 return -ENOMEM;
64 orphan->inum = inum;
65 orphan->new = 1;
66
67 spin_lock(&c->orphan_lock);
68 if (c->tot_orphans >= c->max_orphans) {
69 spin_unlock(&c->orphan_lock);
70 kfree(orphan);
71 return -ENFILE;
72 }
73 p = &c->orph_tree.rb_node;
74 while (*p) {
75 parent = *p;
76 o = rb_entry(parent, struct ubifs_orphan, rb);
77 if (inum < o->inum)
78 p = &(*p)->rb_left;
79 else if (inum > o->inum)
80 p = &(*p)->rb_right;
81 else {
82 ubifs_err(c, "orphaned twice");
83 spin_unlock(&c->orphan_lock);
84 kfree(orphan);
85 return 0;
86 }
87 }
88 c->tot_orphans += 1;
89 c->new_orphans += 1;
90 rb_link_node(&orphan->rb, parent, p);
91 rb_insert_color(&orphan->rb, &c->orph_tree);
92 list_add_tail(&orphan->list, &c->orph_list);
93 list_add_tail(&orphan->new_list, &c->orph_new);
94 spin_unlock(&c->orphan_lock);
95 dbg_gen("ino %lu", (unsigned long)inum);
96 return 0;
97}
98
99
100
101
102
103
104
105
106void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
107{
108 struct ubifs_orphan *o;
109 struct rb_node *p;
110
111 spin_lock(&c->orphan_lock);
112 p = c->orph_tree.rb_node;
113 while (p) {
114 o = rb_entry(p, struct ubifs_orphan, rb);
115 if (inum < o->inum)
116 p = p->rb_left;
117 else if (inum > o->inum)
118 p = p->rb_right;
119 else {
120 if (o->del) {
121 spin_unlock(&c->orphan_lock);
122 dbg_gen("deleted twice ino %lu",
123 (unsigned long)inum);
124 return;
125 }
126 if (o->cmt) {
127 o->del = 1;
128 o->dnext = c->orph_dnext;
129 c->orph_dnext = o;
130 spin_unlock(&c->orphan_lock);
131 dbg_gen("delete later ino %lu",
132 (unsigned long)inum);
133 return;
134 }
135 rb_erase(p, &c->orph_tree);
136 list_del(&o->list);
137 c->tot_orphans -= 1;
138 if (o->new) {
139 list_del(&o->new_list);
140 c->new_orphans -= 1;
141 }
142 spin_unlock(&c->orphan_lock);
143 kfree(o);
144 dbg_gen("inum %lu", (unsigned long)inum);
145 return;
146 }
147 }
148 spin_unlock(&c->orphan_lock);
149 ubifs_err(c, "missing orphan ino %lu", (unsigned long)inum);
150 dump_stack();
151}
152
153
154
155
156
157
158
159int ubifs_orphan_start_commit(struct ubifs_info *c)
160{
161 struct ubifs_orphan *orphan, **last;
162
163 spin_lock(&c->orphan_lock);
164 last = &c->orph_cnext;
165 list_for_each_entry(orphan, &c->orph_new, new_list) {
166 ubifs_assert(orphan->new);
167 ubifs_assert(!orphan->cmt);
168 orphan->new = 0;
169 orphan->cmt = 1;
170 *last = orphan;
171 last = &orphan->cnext;
172 }
173 *last = NULL;
174 c->cmt_orphans = c->new_orphans;
175 c->new_orphans = 0;
176 dbg_cmt("%d orphans to commit", c->cmt_orphans);
177 INIT_LIST_HEAD(&c->orph_new);
178 if (c->tot_orphans == 0)
179 c->no_orphs = 1;
180 else
181 c->no_orphs = 0;
182 spin_unlock(&c->orphan_lock);
183 return 0;
184}
185
186
187
188
189
190
191
192
193static int avail_orphs(struct ubifs_info *c)
194{
195 int avail_lebs, avail, gap;
196
197 avail_lebs = c->orph_lebs - (c->ohead_lnum - c->orph_first) - 1;
198 avail = avail_lebs *
199 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64));
200 gap = c->leb_size - c->ohead_offs;
201 if (gap >= UBIFS_ORPH_NODE_SZ + sizeof(__le64))
202 avail += (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64);
203 return avail;
204}
205
206
207
208
209
210
211
212
213static int tot_avail_orphs(struct ubifs_info *c)
214{
215 int avail_lebs, avail;
216
217 avail_lebs = c->orph_lebs;
218 avail = avail_lebs *
219 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64));
220 return avail / 2;
221}
222
223
224
225
226
227
228
229
230
231
232
233static int do_write_orph_node(struct ubifs_info *c, int len, int atomic)
234{
235 int err = 0;
236
237 if (atomic) {
238 ubifs_assert(c->ohead_offs == 0);
239 ubifs_prepare_node(c, c->orph_buf, len, 1);
240 len = ALIGN(len, c->min_io_size);
241 err = ubifs_leb_change(c, c->ohead_lnum, c->orph_buf, len);
242 } else {
243 if (c->ohead_offs == 0) {
244
245 err = ubifs_leb_unmap(c, c->ohead_lnum);
246 if (err)
247 return err;
248 }
249 err = ubifs_write_node(c, c->orph_buf, len, c->ohead_lnum,
250 c->ohead_offs);
251 }
252 return err;
253}
254
255
256
257
258
259
260
261
262
263
264static int write_orph_node(struct ubifs_info *c, int atomic)
265{
266 struct ubifs_orphan *orphan, *cnext;
267 struct ubifs_orph_node *orph;
268 int gap, err, len, cnt, i;
269
270 ubifs_assert(c->cmt_orphans > 0);
271 gap = c->leb_size - c->ohead_offs;
272 if (gap < UBIFS_ORPH_NODE_SZ + sizeof(__le64)) {
273 c->ohead_lnum += 1;
274 c->ohead_offs = 0;
275 gap = c->leb_size;
276 if (c->ohead_lnum > c->orph_last) {
277
278
279
280
281 ubifs_err(c, "out of space in orphan area");
282 return -EINVAL;
283 }
284 }
285 cnt = (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64);
286 if (cnt > c->cmt_orphans)
287 cnt = c->cmt_orphans;
288 len = UBIFS_ORPH_NODE_SZ + cnt * sizeof(__le64);
289 ubifs_assert(c->orph_buf);
290 orph = c->orph_buf;
291 orph->ch.node_type = UBIFS_ORPH_NODE;
292 spin_lock(&c->orphan_lock);
293 cnext = c->orph_cnext;
294 for (i = 0; i < cnt; i++) {
295 orphan = cnext;
296 ubifs_assert(orphan->cmt);
297 orph->inos[i] = cpu_to_le64(orphan->inum);
298 orphan->cmt = 0;
299 cnext = orphan->cnext;
300 orphan->cnext = NULL;
301 }
302 c->orph_cnext = cnext;
303 c->cmt_orphans -= cnt;
304 spin_unlock(&c->orphan_lock);
305 if (c->cmt_orphans)
306 orph->cmt_no = cpu_to_le64(c->cmt_no);
307 else
308
309 orph->cmt_no = cpu_to_le64((c->cmt_no) | (1ULL << 63));
310 ubifs_assert(c->ohead_offs + len <= c->leb_size);
311 ubifs_assert(c->ohead_lnum >= c->orph_first);
312 ubifs_assert(c->ohead_lnum <= c->orph_last);
313 err = do_write_orph_node(c, len, atomic);
314 c->ohead_offs += ALIGN(len, c->min_io_size);
315 c->ohead_offs = ALIGN(c->ohead_offs, 8);
316 return err;
317}
318
319
320
321
322
323
324
325
326
327static int write_orph_nodes(struct ubifs_info *c, int atomic)
328{
329 int err;
330
331 while (c->cmt_orphans > 0) {
332 err = write_orph_node(c, atomic);
333 if (err)
334 return err;
335 }
336 if (atomic) {
337 int lnum;
338
339
340 for (lnum = c->ohead_lnum + 1; lnum <= c->orph_last; lnum++) {
341 err = ubifs_leb_unmap(c, lnum);
342 if (err)
343 return err;
344 }
345 }
346 return 0;
347}
348
349
350
351
352
353
354
355
356
357
358
359
360static int consolidate(struct ubifs_info *c)
361{
362 int tot_avail = tot_avail_orphs(c), err = 0;
363
364 spin_lock(&c->orphan_lock);
365 dbg_cmt("there is space for %d orphans and there are %d",
366 tot_avail, c->tot_orphans);
367 if (c->tot_orphans - c->new_orphans <= tot_avail) {
368 struct ubifs_orphan *orphan, **last;
369 int cnt = 0;
370
371
372 last = &c->orph_cnext;
373 list_for_each_entry(orphan, &c->orph_list, list) {
374 if (orphan->new)
375 continue;
376 orphan->cmt = 1;
377 *last = orphan;
378 last = &orphan->cnext;
379 cnt += 1;
380 }
381 *last = NULL;
382 ubifs_assert(cnt == c->tot_orphans - c->new_orphans);
383 c->cmt_orphans = cnt;
384 c->ohead_lnum = c->orph_first;
385 c->ohead_offs = 0;
386 } else {
387
388
389
390
391 ubifs_err(c, "out of space in orphan area");
392 err = -EINVAL;
393 }
394 spin_unlock(&c->orphan_lock);
395 return err;
396}
397
398
399
400
401
402
403
404
405static int commit_orphans(struct ubifs_info *c)
406{
407 int avail, atomic = 0, err;
408
409 ubifs_assert(c->cmt_orphans > 0);
410 avail = avail_orphs(c);
411 if (avail < c->cmt_orphans) {
412
413 err = consolidate(c);
414 if (err)
415 return err;
416 atomic = 1;
417 }
418 err = write_orph_nodes(c, atomic);
419 return err;
420}
421
422
423
424
425
426
427
428
429
430
431static void erase_deleted(struct ubifs_info *c)
432{
433 struct ubifs_orphan *orphan, *dnext;
434
435 spin_lock(&c->orphan_lock);
436 dnext = c->orph_dnext;
437 while (dnext) {
438 orphan = dnext;
439 dnext = orphan->dnext;
440 ubifs_assert(!orphan->new);
441 ubifs_assert(orphan->del);
442 rb_erase(&orphan->rb, &c->orph_tree);
443 list_del(&orphan->list);
444 c->tot_orphans -= 1;
445 dbg_gen("deleting orphan ino %lu", (unsigned long)orphan->inum);
446 kfree(orphan);
447 }
448 c->orph_dnext = NULL;
449 spin_unlock(&c->orphan_lock);
450}
451
452
453
454
455
456
457
458int ubifs_orphan_end_commit(struct ubifs_info *c)
459{
460 int err;
461
462 if (c->cmt_orphans != 0) {
463 err = commit_orphans(c);
464 if (err)
465 return err;
466 }
467 erase_deleted(c);
468 err = dbg_check_orphans(c);
469 return err;
470}
471
472
473
474
475
476
477
478
479
480int ubifs_clear_orphans(struct ubifs_info *c)
481{
482 int lnum, err;
483
484 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
485 err = ubifs_leb_unmap(c, lnum);
486 if (err)
487 return err;
488 }
489 c->ohead_lnum = c->orph_first;
490 c->ohead_offs = 0;
491 return 0;
492}
493
494
495
496
497
498
499
500
501
502
503static int insert_dead_orphan(struct ubifs_info *c, ino_t inum)
504{
505 struct ubifs_orphan *orphan, *o;
506 struct rb_node **p, *parent = NULL;
507
508 orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_KERNEL);
509 if (!orphan)
510 return -ENOMEM;
511 orphan->inum = inum;
512
513 p = &c->orph_tree.rb_node;
514 while (*p) {
515 parent = *p;
516 o = rb_entry(parent, struct ubifs_orphan, rb);
517 if (inum < o->inum)
518 p = &(*p)->rb_left;
519 else if (inum > o->inum)
520 p = &(*p)->rb_right;
521 else {
522
523 kfree(orphan);
524 return 0;
525 }
526 }
527 c->tot_orphans += 1;
528 rb_link_node(&orphan->rb, parent, p);
529 rb_insert_color(&orphan->rb, &c->orph_tree);
530 list_add_tail(&orphan->list, &c->orph_list);
531 orphan->del = 1;
532 orphan->dnext = c->orph_dnext;
533 c->orph_dnext = orphan;
534 dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum,
535 c->new_orphans, c->tot_orphans);
536 return 0;
537}
538
539
540
541
542
543
544
545
546
547
548
549
550
551static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
552 unsigned long long *last_cmt_no, int *outofdate,
553 int *last_flagged)
554{
555 struct ubifs_scan_node *snod;
556 struct ubifs_orph_node *orph;
557 unsigned long long cmt_no;
558 ino_t inum;
559 int i, n, err, first = 1;
560
561 list_for_each_entry(snod, &sleb->nodes, list) {
562 if (snod->type != UBIFS_ORPH_NODE) {
563 ubifs_err(c, "invalid node type %d in orphan area at %d:%d",
564 snod->type, sleb->lnum, snod->offs);
565 ubifs_dump_node(c, snod->node);
566 return -EINVAL;
567 }
568
569 orph = snod->node;
570
571
572 cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX;
573
574
575
576
577
578
579
580
581 if (cmt_no > c->cmt_no)
582 c->cmt_no = cmt_no;
583 if (cmt_no < *last_cmt_no && *last_flagged) {
584
585
586
587
588
589 if (!first) {
590 ubifs_err(c, "out of order commit number %llu in orphan node at %d:%d",
591 cmt_no, sleb->lnum, snod->offs);
592 ubifs_dump_node(c, snod->node);
593 return -EINVAL;
594 }
595 dbg_rcvry("out of date LEB %d", sleb->lnum);
596 *outofdate = 1;
597 return 0;
598 }
599
600 if (first)
601 first = 0;
602
603 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3;
604 for (i = 0; i < n; i++) {
605 inum = le64_to_cpu(orph->inos[i]);
606 dbg_rcvry("deleting orphaned inode %lu",
607 (unsigned long)inum);
608 err = ubifs_tnc_remove_ino(c, inum);
609 if (err)
610 return err;
611 err = insert_dead_orphan(c, inum);
612 if (err)
613 return err;
614 }
615
616 *last_cmt_no = cmt_no;
617 if (le64_to_cpu(orph->cmt_no) & (1ULL << 63)) {
618 dbg_rcvry("last orph node for commit %llu at %d:%d",
619 cmt_no, sleb->lnum, snod->offs);
620 *last_flagged = 1;
621 } else
622 *last_flagged = 0;
623 }
624
625 return 0;
626}
627
628
629
630
631
632
633
634
635
636
637
638static int kill_orphans(struct ubifs_info *c)
639{
640 unsigned long long last_cmt_no = 0;
641 int lnum, err = 0, outofdate = 0, last_flagged = 0;
642
643 c->ohead_lnum = c->orph_first;
644 c->ohead_offs = 0;
645
646 if (c->no_orphs) {
647 dbg_rcvry("no orphans");
648 return 0;
649 }
650
651
652
653
654
655
656
657
658
659
660
661 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
662 struct ubifs_scan_leb *sleb;
663
664 dbg_rcvry("LEB %d", lnum);
665 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1);
666 if (IS_ERR(sleb)) {
667 if (PTR_ERR(sleb) == -EUCLEAN)
668 sleb = ubifs_recover_leb(c, lnum, 0,
669 c->sbuf, -1);
670 if (IS_ERR(sleb)) {
671 err = PTR_ERR(sleb);
672 break;
673 }
674 }
675 err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate,
676 &last_flagged);
677 if (err || outofdate) {
678 ubifs_scan_destroy(sleb);
679 break;
680 }
681 if (sleb->endpt) {
682 c->ohead_lnum = lnum;
683 c->ohead_offs = sleb->endpt;
684 }
685 ubifs_scan_destroy(sleb);
686 }
687 return err;
688}
689
690
691
692
693
694
695
696
697
698
699
700int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only)
701{
702 int err = 0;
703
704 c->max_orphans = tot_avail_orphs(c);
705
706 if (!read_only) {
707 c->orph_buf = vmalloc(c->leb_size);
708 if (!c->orph_buf)
709 return -ENOMEM;
710 }
711
712 if (unclean)
713 err = kill_orphans(c);
714 else if (!read_only)
715 err = ubifs_clear_orphans(c);
716
717 return err;
718}
719
720
721
722
723
724struct check_orphan {
725 struct rb_node rb;
726 ino_t inum;
727};
728
729struct check_info {
730 unsigned long last_ino;
731 unsigned long tot_inos;
732 unsigned long missing;
733 unsigned long long leaf_cnt;
734 struct ubifs_ino_node *node;
735 struct rb_root root;
736};
737
738static int dbg_find_orphan(struct ubifs_info *c, ino_t inum)
739{
740 struct ubifs_orphan *o;
741 struct rb_node *p;
742
743 spin_lock(&c->orphan_lock);
744 p = c->orph_tree.rb_node;
745 while (p) {
746 o = rb_entry(p, struct ubifs_orphan, rb);
747 if (inum < o->inum)
748 p = p->rb_left;
749 else if (inum > o->inum)
750 p = p->rb_right;
751 else {
752 spin_unlock(&c->orphan_lock);
753 return 1;
754 }
755 }
756 spin_unlock(&c->orphan_lock);
757 return 0;
758}
759
760static int dbg_ins_check_orphan(struct rb_root *root, ino_t inum)
761{
762 struct check_orphan *orphan, *o;
763 struct rb_node **p, *parent = NULL;
764
765 orphan = kzalloc(sizeof(struct check_orphan), GFP_NOFS);
766 if (!orphan)
767 return -ENOMEM;
768 orphan->inum = inum;
769
770 p = &root->rb_node;
771 while (*p) {
772 parent = *p;
773 o = rb_entry(parent, struct check_orphan, rb);
774 if (inum < o->inum)
775 p = &(*p)->rb_left;
776 else if (inum > o->inum)
777 p = &(*p)->rb_right;
778 else {
779 kfree(orphan);
780 return 0;
781 }
782 }
783 rb_link_node(&orphan->rb, parent, p);
784 rb_insert_color(&orphan->rb, root);
785 return 0;
786}
787
788static int dbg_find_check_orphan(struct rb_root *root, ino_t inum)
789{
790 struct check_orphan *o;
791 struct rb_node *p;
792
793 p = root->rb_node;
794 while (p) {
795 o = rb_entry(p, struct check_orphan, rb);
796 if (inum < o->inum)
797 p = p->rb_left;
798 else if (inum > o->inum)
799 p = p->rb_right;
800 else
801 return 1;
802 }
803 return 0;
804}
805
806static void dbg_free_check_tree(struct rb_root *root)
807{
808 struct check_orphan *o, *n;
809
810 rbtree_postorder_for_each_entry_safe(o, n, root, rb)
811 kfree(o);
812}
813
814static int dbg_orphan_check(struct ubifs_info *c, struct ubifs_zbranch *zbr,
815 void *priv)
816{
817 struct check_info *ci = priv;
818 ino_t inum;
819 int err;
820
821 inum = key_inum(c, &zbr->key);
822 if (inum != ci->last_ino) {
823
824 if (key_type(c, &zbr->key) != UBIFS_INO_KEY)
825 ubifs_err(c, "found orphan node ino %lu, type %d",
826 (unsigned long)inum, key_type(c, &zbr->key));
827 ci->last_ino = inum;
828 ci->tot_inos += 1;
829 err = ubifs_tnc_read_node(c, zbr, ci->node);
830 if (err) {
831 ubifs_err(c, "node read failed, error %d", err);
832 return err;
833 }
834 if (ci->node->nlink == 0)
835
836 if (!dbg_find_check_orphan(&ci->root, inum) &&
837 !dbg_find_orphan(c, inum)) {
838 ubifs_err(c, "missing orphan, ino %lu",
839 (unsigned long)inum);
840 ci->missing += 1;
841 }
842 }
843 ci->leaf_cnt += 1;
844 return 0;
845}
846
847static int dbg_read_orphans(struct check_info *ci, struct ubifs_scan_leb *sleb)
848{
849 struct ubifs_scan_node *snod;
850 struct ubifs_orph_node *orph;
851 ino_t inum;
852 int i, n, err;
853
854 list_for_each_entry(snod, &sleb->nodes, list) {
855 cond_resched();
856 if (snod->type != UBIFS_ORPH_NODE)
857 continue;
858 orph = snod->node;
859 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3;
860 for (i = 0; i < n; i++) {
861 inum = le64_to_cpu(orph->inos[i]);
862 err = dbg_ins_check_orphan(&ci->root, inum);
863 if (err)
864 return err;
865 }
866 }
867 return 0;
868}
869
870static int dbg_scan_orphans(struct ubifs_info *c, struct check_info *ci)
871{
872 int lnum, err = 0;
873 void *buf;
874
875
876 if (c->no_orphs)
877 return 0;
878
879 buf = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
880 if (!buf) {
881 ubifs_err(c, "cannot allocate memory to check orphans");
882 return 0;
883 }
884
885 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
886 struct ubifs_scan_leb *sleb;
887
888 sleb = ubifs_scan(c, lnum, 0, buf, 0);
889 if (IS_ERR(sleb)) {
890 err = PTR_ERR(sleb);
891 break;
892 }
893
894 err = dbg_read_orphans(ci, sleb);
895 ubifs_scan_destroy(sleb);
896 if (err)
897 break;
898 }
899
900 vfree(buf);
901 return err;
902}
903
904static int dbg_check_orphans(struct ubifs_info *c)
905{
906 struct check_info ci;
907 int err;
908
909 if (!dbg_is_chk_orph(c))
910 return 0;
911
912 ci.last_ino = 0;
913 ci.tot_inos = 0;
914 ci.missing = 0;
915 ci.leaf_cnt = 0;
916 ci.root = RB_ROOT;
917 ci.node = kmalloc(UBIFS_MAX_INO_NODE_SZ, GFP_NOFS);
918 if (!ci.node) {
919 ubifs_err(c, "out of memory");
920 return -ENOMEM;
921 }
922
923 err = dbg_scan_orphans(c, &ci);
924 if (err)
925 goto out;
926
927 err = dbg_walk_index(c, &dbg_orphan_check, NULL, &ci);
928 if (err) {
929 ubifs_err(c, "cannot scan TNC, error %d", err);
930 goto out;
931 }
932
933 if (ci.missing) {
934 ubifs_err(c, "%lu missing orphan(s)", ci.missing);
935 err = -EINVAL;
936 goto out;
937 }
938
939 dbg_cmt("last inode number is %lu", ci.last_ino);
940 dbg_cmt("total number of inodes is %lu", ci.tot_inos);
941 dbg_cmt("total number of leaf nodes is %llu", ci.leaf_cnt);
942
943out:
944 dbg_free_check_tree(&ci.root);
945 kfree(ci.node);
946 return err;
947}
948