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