Lines Matching +full:- +full:c
1 // SPDX-License-Identifier: GPL-2.0-only
5 * Copyright (C) 2006-2008 Nokia Corporation.
30 * (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)
34 * Orphans are accumulated in a rb-tree. When an inode's link count drops to
35 * zero, the inode number is added to the rb-tree. It is removed from the tree
43 static int dbg_check_orphans(struct ubifs_info *c);
46 * ubifs_add_orphan - add an orphan.
47 * @c: UBIFS file-system description object
53 int ubifs_add_orphan(struct ubifs_info *c, ino_t inum) in ubifs_add_orphan() argument
60 return -ENOMEM; in ubifs_add_orphan()
61 orphan->inum = inum; in ubifs_add_orphan()
62 orphan->new = 1; in ubifs_add_orphan()
64 spin_lock(&c->orphan_lock); in ubifs_add_orphan()
65 if (c->tot_orphans >= c->max_orphans) { in ubifs_add_orphan()
66 spin_unlock(&c->orphan_lock); in ubifs_add_orphan()
68 return -ENFILE; in ubifs_add_orphan()
70 p = &c->orph_tree.rb_node; in ubifs_add_orphan()
74 if (inum < o->inum) in ubifs_add_orphan()
75 p = &(*p)->rb_left; in ubifs_add_orphan()
76 else if (inum > o->inum) in ubifs_add_orphan()
77 p = &(*p)->rb_right; in ubifs_add_orphan()
79 ubifs_err(c, "ino %lu orphaned twice", (unsigned long)inum); in ubifs_add_orphan()
80 spin_unlock(&c->orphan_lock); in ubifs_add_orphan()
82 return -EINVAL; in ubifs_add_orphan()
85 c->tot_orphans += 1; in ubifs_add_orphan()
86 c->new_orphans += 1; in ubifs_add_orphan()
87 rb_link_node(&orphan->rb, parent, p); in ubifs_add_orphan()
88 rb_insert_color(&orphan->rb, &c->orph_tree); in ubifs_add_orphan()
89 list_add_tail(&orphan->list, &c->orph_list); in ubifs_add_orphan()
90 list_add_tail(&orphan->new_list, &c->orph_new); in ubifs_add_orphan()
92 spin_unlock(&c->orphan_lock); in ubifs_add_orphan()
97 static struct ubifs_orphan *lookup_orphan(struct ubifs_info *c, ino_t inum) in lookup_orphan() argument
102 p = c->orph_tree.rb_node; in lookup_orphan()
105 if (inum < o->inum) in lookup_orphan()
106 p = p->rb_left; in lookup_orphan()
107 else if (inum > o->inum) in lookup_orphan()
108 p = p->rb_right; in lookup_orphan()
116 static void __orphan_drop(struct ubifs_info *c, struct ubifs_orphan *o) in __orphan_drop() argument
118 rb_erase(&o->rb, &c->orph_tree); in __orphan_drop()
119 list_del(&o->list); in __orphan_drop()
120 c->tot_orphans -= 1; in __orphan_drop()
122 if (o->new) { in __orphan_drop()
123 list_del(&o->new_list); in __orphan_drop()
124 c->new_orphans -= 1; in __orphan_drop()
130 static void orphan_delete(struct ubifs_info *c, struct ubifs_orphan *orph) in orphan_delete() argument
132 if (orph->del) { in orphan_delete()
133 dbg_gen("deleted twice ino %lu", (unsigned long)orph->inum); in orphan_delete()
137 if (orph->cmt) { in orphan_delete()
138 orph->del = 1; in orphan_delete()
139 rb_erase(&orph->rb, &c->orph_tree); in orphan_delete()
140 orph->dnext = c->orph_dnext; in orphan_delete()
141 c->orph_dnext = orph; in orphan_delete()
142 dbg_gen("delete later ino %lu", (unsigned long)orph->inum); in orphan_delete()
146 __orphan_drop(c, orph); in orphan_delete()
150 * ubifs_delete_orphan - delete an orphan.
151 * @c: UBIFS file-system description object
156 void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum) in ubifs_delete_orphan() argument
160 spin_lock(&c->orphan_lock); in ubifs_delete_orphan()
162 orph = lookup_orphan(c, inum); in ubifs_delete_orphan()
164 spin_unlock(&c->orphan_lock); in ubifs_delete_orphan()
165 ubifs_err(c, "missing orphan ino %lu", (unsigned long)inum); in ubifs_delete_orphan()
171 orphan_delete(c, orph); in ubifs_delete_orphan()
173 spin_unlock(&c->orphan_lock); in ubifs_delete_orphan()
177 * ubifs_orphan_start_commit - start commit of orphans.
178 * @c: UBIFS file-system description object
182 int ubifs_orphan_start_commit(struct ubifs_info *c) in ubifs_orphan_start_commit() argument
186 spin_lock(&c->orphan_lock); in ubifs_orphan_start_commit()
187 last = &c->orph_cnext; in ubifs_orphan_start_commit()
188 list_for_each_entry(orphan, &c->orph_new, new_list) { in ubifs_orphan_start_commit()
189 ubifs_assert(c, orphan->new); in ubifs_orphan_start_commit()
190 ubifs_assert(c, !orphan->cmt); in ubifs_orphan_start_commit()
191 orphan->new = 0; in ubifs_orphan_start_commit()
192 orphan->cmt = 1; in ubifs_orphan_start_commit()
194 last = &orphan->cnext; in ubifs_orphan_start_commit()
197 c->cmt_orphans = c->new_orphans; in ubifs_orphan_start_commit()
198 c->new_orphans = 0; in ubifs_orphan_start_commit()
199 dbg_cmt("%d orphans to commit", c->cmt_orphans); in ubifs_orphan_start_commit()
200 INIT_LIST_HEAD(&c->orph_new); in ubifs_orphan_start_commit()
201 if (c->tot_orphans == 0) in ubifs_orphan_start_commit()
202 c->no_orphs = 1; in ubifs_orphan_start_commit()
204 c->no_orphs = 0; in ubifs_orphan_start_commit()
205 spin_unlock(&c->orphan_lock); in ubifs_orphan_start_commit()
210 * avail_orphs - calculate available space.
211 * @c: UBIFS file-system description object
216 static int avail_orphs(struct ubifs_info *c) in avail_orphs() argument
220 avail_lebs = c->orph_lebs - (c->ohead_lnum - c->orph_first) - 1; in avail_orphs()
222 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); in avail_orphs()
223 gap = c->leb_size - c->ohead_offs; in avail_orphs()
225 avail += (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64); in avail_orphs()
230 * tot_avail_orphs - calculate total space.
231 * @c: UBIFS file-system description object
236 static int tot_avail_orphs(struct ubifs_info *c) in tot_avail_orphs() argument
240 avail_lebs = c->orph_lebs; in tot_avail_orphs()
242 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); in tot_avail_orphs()
247 * do_write_orph_node - write a node to the orphan head.
248 * @c: UBIFS file-system description object
256 static int do_write_orph_node(struct ubifs_info *c, int len, int atomic) in do_write_orph_node() argument
261 ubifs_assert(c, c->ohead_offs == 0); in do_write_orph_node()
262 ubifs_prepare_node(c, c->orph_buf, len, 1); in do_write_orph_node()
263 len = ALIGN(len, c->min_io_size); in do_write_orph_node()
264 err = ubifs_leb_change(c, c->ohead_lnum, c->orph_buf, len); in do_write_orph_node()
266 if (c->ohead_offs == 0) { in do_write_orph_node()
268 err = ubifs_leb_unmap(c, c->ohead_lnum); in do_write_orph_node()
272 err = ubifs_write_node(c, c->orph_buf, len, c->ohead_lnum, in do_write_orph_node()
273 c->ohead_offs); in do_write_orph_node()
279 * write_orph_node - write an orphan node.
280 * @c: UBIFS file-system description object
287 static int write_orph_node(struct ubifs_info *c, int atomic) in write_orph_node() argument
293 ubifs_assert(c, c->cmt_orphans > 0); in write_orph_node()
294 gap = c->leb_size - c->ohead_offs; in write_orph_node()
296 c->ohead_lnum += 1; in write_orph_node()
297 c->ohead_offs = 0; in write_orph_node()
298 gap = c->leb_size; in write_orph_node()
299 if (c->ohead_lnum > c->orph_last) { in write_orph_node()
304 ubifs_err(c, "out of space in orphan area"); in write_orph_node()
305 return -EINVAL; in write_orph_node()
308 cnt = (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64); in write_orph_node()
309 if (cnt > c->cmt_orphans) in write_orph_node()
310 cnt = c->cmt_orphans; in write_orph_node()
312 ubifs_assert(c, c->orph_buf); in write_orph_node()
313 orph = c->orph_buf; in write_orph_node()
314 orph->ch.node_type = UBIFS_ORPH_NODE; in write_orph_node()
315 spin_lock(&c->orphan_lock); in write_orph_node()
316 cnext = c->orph_cnext; in write_orph_node()
319 ubifs_assert(c, orphan->cmt); in write_orph_node()
320 orph->inos[i] = cpu_to_le64(orphan->inum); in write_orph_node()
321 orphan->cmt = 0; in write_orph_node()
322 cnext = orphan->cnext; in write_orph_node()
323 orphan->cnext = NULL; in write_orph_node()
325 c->orph_cnext = cnext; in write_orph_node()
326 c->cmt_orphans -= cnt; in write_orph_node()
327 spin_unlock(&c->orphan_lock); in write_orph_node()
328 if (c->cmt_orphans) in write_orph_node()
329 orph->cmt_no = cpu_to_le64(c->cmt_no); in write_orph_node()
332 orph->cmt_no = cpu_to_le64((c->cmt_no) | (1ULL << 63)); in write_orph_node()
333 ubifs_assert(c, c->ohead_offs + len <= c->leb_size); in write_orph_node()
334 ubifs_assert(c, c->ohead_lnum >= c->orph_first); in write_orph_node()
335 ubifs_assert(c, c->ohead_lnum <= c->orph_last); in write_orph_node()
336 err = do_write_orph_node(c, len, atomic); in write_orph_node()
337 c->ohead_offs += ALIGN(len, c->min_io_size); in write_orph_node()
338 c->ohead_offs = ALIGN(c->ohead_offs, 8); in write_orph_node()
343 * write_orph_nodes - write orphan nodes until there are no more to commit.
344 * @c: UBIFS file-system description object
350 static int write_orph_nodes(struct ubifs_info *c, int atomic) in write_orph_nodes() argument
354 while (c->cmt_orphans > 0) { in write_orph_nodes()
355 err = write_orph_node(c, atomic); in write_orph_nodes()
363 for (lnum = c->ohead_lnum + 1; lnum <= c->orph_last; lnum++) { in write_orph_nodes()
364 err = ubifs_leb_unmap(c, lnum); in write_orph_nodes()
373 * consolidate - consolidate the orphan area.
374 * @c: UBIFS file-system description object
383 static int consolidate(struct ubifs_info *c) in consolidate() argument
385 int tot_avail = tot_avail_orphs(c), err = 0; in consolidate()
387 spin_lock(&c->orphan_lock); in consolidate()
389 tot_avail, c->tot_orphans); in consolidate()
390 if (c->tot_orphans - c->new_orphans <= tot_avail) { in consolidate()
394 /* Change the cnext list to include all non-new orphans */ in consolidate()
395 last = &c->orph_cnext; in consolidate()
396 list_for_each_entry(orphan, &c->orph_list, list) { in consolidate()
397 if (orphan->new) in consolidate()
399 orphan->cmt = 1; in consolidate()
401 last = &orphan->cnext; in consolidate()
405 ubifs_assert(c, cnt == c->tot_orphans - c->new_orphans); in consolidate()
406 c->cmt_orphans = cnt; in consolidate()
407 c->ohead_lnum = c->orph_first; in consolidate()
408 c->ohead_offs = 0; in consolidate()
414 ubifs_err(c, "out of space in orphan area"); in consolidate()
415 err = -EINVAL; in consolidate()
417 spin_unlock(&c->orphan_lock); in consolidate()
422 * commit_orphans - commit orphans.
423 * @c: UBIFS file-system description object
428 static int commit_orphans(struct ubifs_info *c) in commit_orphans() argument
432 ubifs_assert(c, c->cmt_orphans > 0); in commit_orphans()
433 avail = avail_orphs(c); in commit_orphans()
434 if (avail < c->cmt_orphans) { in commit_orphans()
436 err = consolidate(c); in commit_orphans()
441 err = write_orph_nodes(c, atomic); in commit_orphans()
446 * erase_deleted - erase the orphans marked for deletion.
447 * @c: UBIFS file-system description object
454 static void erase_deleted(struct ubifs_info *c) in erase_deleted() argument
458 spin_lock(&c->orphan_lock); in erase_deleted()
459 dnext = c->orph_dnext; in erase_deleted()
462 dnext = orphan->dnext; in erase_deleted()
463 ubifs_assert(c, !orphan->new); in erase_deleted()
464 ubifs_assert(c, orphan->del); in erase_deleted()
465 list_del(&orphan->list); in erase_deleted()
466 c->tot_orphans -= 1; in erase_deleted()
467 dbg_gen("deleting orphan ino %lu", (unsigned long)orphan->inum); in erase_deleted()
470 c->orph_dnext = NULL; in erase_deleted()
471 spin_unlock(&c->orphan_lock); in erase_deleted()
475 * ubifs_orphan_end_commit - end commit of orphans.
476 * @c: UBIFS file-system description object
480 int ubifs_orphan_end_commit(struct ubifs_info *c) in ubifs_orphan_end_commit() argument
484 if (c->cmt_orphans != 0) { in ubifs_orphan_end_commit()
485 err = commit_orphans(c); in ubifs_orphan_end_commit()
489 erase_deleted(c); in ubifs_orphan_end_commit()
490 err = dbg_check_orphans(c); in ubifs_orphan_end_commit()
495 * ubifs_clear_orphans - erase all LEBs used for orphans.
496 * @c: UBIFS file-system description object
500 * orphans, and un-maps them.
502 int ubifs_clear_orphans(struct ubifs_info *c) in ubifs_clear_orphans() argument
506 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { in ubifs_clear_orphans()
507 err = ubifs_leb_unmap(c, lnum); in ubifs_clear_orphans()
511 c->ohead_lnum = c->orph_first; in ubifs_clear_orphans()
512 c->ohead_offs = 0; in ubifs_clear_orphans()
517 * do_kill_orphans - remove orphan inodes from the index.
518 * @c: UBIFS file-system description object
528 static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb, in do_kill_orphans() argument
541 return -ENOMEM; in do_kill_orphans()
543 list_for_each_entry(snod, &sleb->nodes, list) { in do_kill_orphans()
544 if (snod->type != UBIFS_ORPH_NODE) { in do_kill_orphans()
545 ubifs_err(c, "invalid node type %d in orphan area at %d:%d", in do_kill_orphans()
546 snod->type, sleb->lnum, snod->offs); in do_kill_orphans()
547 ubifs_dump_node(c, snod->node, in do_kill_orphans()
548 c->leb_size - snod->offs); in do_kill_orphans()
549 err = -EINVAL; in do_kill_orphans()
553 orph = snod->node; in do_kill_orphans()
556 cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX; in do_kill_orphans()
563 * because the master node has not been re-written. in do_kill_orphans()
565 if (cmt_no > c->cmt_no) in do_kill_orphans()
566 c->cmt_no = cmt_no; in do_kill_orphans()
574 ubifs_err(c, "out of order commit number %llu in orphan node at %d:%d", in do_kill_orphans()
575 cmt_no, sleb->lnum, snod->offs); in do_kill_orphans()
576 ubifs_dump_node(c, snod->node, in do_kill_orphans()
577 c->leb_size - snod->offs); in do_kill_orphans()
578 err = -EINVAL; in do_kill_orphans()
581 dbg_rcvry("out of date LEB %d", sleb->lnum); in do_kill_orphans()
590 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; in do_kill_orphans()
594 inum = le64_to_cpu(orph->inos[i]); in do_kill_orphans()
596 ino_key_init(c, &key, inum); in do_kill_orphans()
597 err = ubifs_tnc_lookup(c, &key, ino); in do_kill_orphans()
598 if (err && err != -ENOENT) in do_kill_orphans()
605 if (err == 0 && ino->nlink == 0) { in do_kill_orphans()
609 err = ubifs_tnc_remove_ino(c, inum); in do_kill_orphans()
616 if (le64_to_cpu(orph->cmt_no) & (1ULL << 63)) { in do_kill_orphans()
618 cmt_no, sleb->lnum, snod->offs); in do_kill_orphans()
630 ubifs_ro_mode(c, err); in do_kill_orphans()
636 * kill_orphans - remove all orphan inodes from the index.
637 * @c: UBIFS file-system description object
645 static int kill_orphans(struct ubifs_info *c) in kill_orphans() argument
650 c->ohead_lnum = c->orph_first; in kill_orphans()
651 c->ohead_offs = 0; in kill_orphans()
652 /* Check no-orphans flag and skip this if no orphans */ in kill_orphans()
653 if (c->no_orphs) { in kill_orphans()
658 * Orph nodes always start at c->orph_first and are written to each in kill_orphans()
662 * marked (top bit of orph->cmt_no is set to 1). It is possible that in kill_orphans()
668 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { in kill_orphans()
672 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1); in kill_orphans()
674 if (PTR_ERR(sleb) == -EUCLEAN) in kill_orphans()
675 sleb = ubifs_recover_leb(c, lnum, 0, in kill_orphans()
676 c->sbuf, -1); in kill_orphans()
682 err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate, in kill_orphans()
688 if (sleb->endpt) { in kill_orphans()
689 c->ohead_lnum = lnum; in kill_orphans()
690 c->ohead_offs = sleb->endpt; in kill_orphans()
698 * ubifs_mount_orphans - delete orphan inodes and erase LEBs that recorded them.
699 * @c: UBIFS file-system description object
707 int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only) in ubifs_mount_orphans() argument
711 c->max_orphans = tot_avail_orphs(c); in ubifs_mount_orphans()
714 c->orph_buf = vmalloc(c->leb_size); in ubifs_mount_orphans()
715 if (!c->orph_buf) in ubifs_mount_orphans()
716 return -ENOMEM; in ubifs_mount_orphans()
720 err = kill_orphans(c); in ubifs_mount_orphans()
722 err = ubifs_clear_orphans(c); in ubifs_mount_orphans()
745 static bool dbg_find_orphan(struct ubifs_info *c, ino_t inum) in dbg_find_orphan() argument
749 spin_lock(&c->orphan_lock); in dbg_find_orphan()
750 found = !!lookup_orphan(c, inum); in dbg_find_orphan()
751 spin_unlock(&c->orphan_lock); in dbg_find_orphan()
763 return -ENOMEM; in dbg_ins_check_orphan()
764 orphan->inum = inum; in dbg_ins_check_orphan()
766 p = &root->rb_node; in dbg_ins_check_orphan()
770 if (inum < o->inum) in dbg_ins_check_orphan()
771 p = &(*p)->rb_left; in dbg_ins_check_orphan()
772 else if (inum > o->inum) in dbg_ins_check_orphan()
773 p = &(*p)->rb_right; in dbg_ins_check_orphan()
779 rb_link_node(&orphan->rb, parent, p); in dbg_ins_check_orphan()
780 rb_insert_color(&orphan->rb, root); in dbg_ins_check_orphan()
789 p = root->rb_node; in dbg_find_check_orphan()
792 if (inum < o->inum) in dbg_find_check_orphan()
793 p = p->rb_left; in dbg_find_check_orphan()
794 else if (inum > o->inum) in dbg_find_check_orphan()
795 p = p->rb_right; in dbg_find_check_orphan()
810 static int dbg_orphan_check(struct ubifs_info *c, struct ubifs_zbranch *zbr, in dbg_orphan_check() argument
817 inum = key_inum(c, &zbr->key); in dbg_orphan_check()
818 if (inum != ci->last_ino) { in dbg_orphan_check()
823 if (key_type(c, &zbr->key) != UBIFS_INO_KEY && in dbg_orphan_check()
824 key_type(c, &zbr->key) != UBIFS_XENT_KEY) in dbg_orphan_check()
825 ubifs_err(c, "found orphan node ino %lu, type %d", in dbg_orphan_check()
826 (unsigned long)inum, key_type(c, &zbr->key)); in dbg_orphan_check()
827 ci->last_ino = inum; in dbg_orphan_check()
828 ci->tot_inos += 1; in dbg_orphan_check()
829 err = ubifs_tnc_read_node(c, zbr, ci->node); in dbg_orphan_check()
831 ubifs_err(c, "node read failed, error %d", err); in dbg_orphan_check()
834 if (ci->node->nlink == 0) in dbg_orphan_check()
836 if (!dbg_find_check_orphan(&ci->root, inum) && in dbg_orphan_check()
837 !dbg_find_orphan(c, inum)) { in dbg_orphan_check()
838 ubifs_err(c, "missing orphan, ino %lu", in dbg_orphan_check()
840 ci->missing += 1; in dbg_orphan_check()
843 ci->leaf_cnt += 1; in dbg_orphan_check()
854 list_for_each_entry(snod, &sleb->nodes, list) { in dbg_read_orphans()
856 if (snod->type != UBIFS_ORPH_NODE) in dbg_read_orphans()
858 orph = snod->node; in dbg_read_orphans()
859 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; in dbg_read_orphans()
861 inum = le64_to_cpu(orph->inos[i]); in dbg_read_orphans()
862 err = dbg_ins_check_orphan(&ci->root, inum); in dbg_read_orphans()
870 static int dbg_scan_orphans(struct ubifs_info *c, struct check_info *ci) in dbg_scan_orphans() argument
875 /* Check no-orphans flag and skip this if no orphans */ in dbg_scan_orphans()
876 if (c->no_orphs) in dbg_scan_orphans()
879 buf = __vmalloc(c->leb_size, GFP_NOFS); in dbg_scan_orphans()
881 ubifs_err(c, "cannot allocate memory to check orphans"); in dbg_scan_orphans()
885 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { in dbg_scan_orphans()
888 sleb = ubifs_scan(c, lnum, 0, buf, 0); in dbg_scan_orphans()
904 static int dbg_check_orphans(struct ubifs_info *c) in dbg_check_orphans() argument
909 if (!dbg_is_chk_orph(c)) in dbg_check_orphans()
919 ubifs_err(c, "out of memory"); in dbg_check_orphans()
920 return -ENOMEM; in dbg_check_orphans()
923 err = dbg_scan_orphans(c, &ci); in dbg_check_orphans()
927 err = dbg_walk_index(c, &dbg_orphan_check, NULL, &ci); in dbg_check_orphans()
929 ubifs_err(c, "cannot scan TNC, error %d", err); in dbg_check_orphans()
934 ubifs_err(c, "%lu missing orphan(s)", ci.missing); in dbg_check_orphans()
935 err = -EINVAL; in dbg_check_orphans()