Lines Matching +full:- +full:c
4 * Copyright (C) 2006-2008 Nokia Corporation.
6 * SPDX-License-Identifier: GPL-2.0+
32 * (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)
36 * Orphans are accumulated in a rb-tree. When an inode's link count drops to
37 * zero, the inode number is added to the rb-tree. It is removed from the tree
45 static int dbg_check_orphans(struct ubifs_info *c);
48 * ubifs_add_orphan - add an orphan.
49 * @c: UBIFS file-system description object
55 int ubifs_add_orphan(struct ubifs_info *c, ino_t inum) in ubifs_add_orphan() argument
62 return -ENOMEM; in ubifs_add_orphan()
63 orphan->inum = inum; in ubifs_add_orphan()
64 orphan->new = 1; in ubifs_add_orphan()
66 spin_lock(&c->orphan_lock); in ubifs_add_orphan()
67 if (c->tot_orphans >= c->max_orphans) { in ubifs_add_orphan()
68 spin_unlock(&c->orphan_lock); in ubifs_add_orphan()
70 return -ENFILE; in ubifs_add_orphan()
72 p = &c->orph_tree.rb_node; in ubifs_add_orphan()
76 if (inum < o->inum) in ubifs_add_orphan()
77 p = &(*p)->rb_left; in ubifs_add_orphan()
78 else if (inum > o->inum) in ubifs_add_orphan()
79 p = &(*p)->rb_right; in ubifs_add_orphan()
81 ubifs_err(c, "orphaned twice"); in ubifs_add_orphan()
82 spin_unlock(&c->orphan_lock); in ubifs_add_orphan()
87 c->tot_orphans += 1; in ubifs_add_orphan()
88 c->new_orphans += 1; in ubifs_add_orphan()
89 rb_link_node(&orphan->rb, parent, p); in ubifs_add_orphan()
90 rb_insert_color(&orphan->rb, &c->orph_tree); in ubifs_add_orphan()
91 list_add_tail(&orphan->list, &c->orph_list); in ubifs_add_orphan()
92 list_add_tail(&orphan->new_list, &c->orph_new); in ubifs_add_orphan()
93 spin_unlock(&c->orphan_lock); in ubifs_add_orphan()
99 * ubifs_delete_orphan - delete an orphan.
100 * @c: UBIFS file-system description object
105 void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum) in ubifs_delete_orphan() argument
110 spin_lock(&c->orphan_lock); in ubifs_delete_orphan()
111 p = c->orph_tree.rb_node; in ubifs_delete_orphan()
114 if (inum < o->inum) in ubifs_delete_orphan()
115 p = p->rb_left; in ubifs_delete_orphan()
116 else if (inum > o->inum) in ubifs_delete_orphan()
117 p = p->rb_right; in ubifs_delete_orphan()
119 if (o->del) { in ubifs_delete_orphan()
120 spin_unlock(&c->orphan_lock); in ubifs_delete_orphan()
125 if (o->cmt) { in ubifs_delete_orphan()
126 o->del = 1; in ubifs_delete_orphan()
127 o->dnext = c->orph_dnext; in ubifs_delete_orphan()
128 c->orph_dnext = o; in ubifs_delete_orphan()
129 spin_unlock(&c->orphan_lock); in ubifs_delete_orphan()
134 rb_erase(p, &c->orph_tree); in ubifs_delete_orphan()
135 list_del(&o->list); in ubifs_delete_orphan()
136 c->tot_orphans -= 1; in ubifs_delete_orphan()
137 if (o->new) { in ubifs_delete_orphan()
138 list_del(&o->new_list); in ubifs_delete_orphan()
139 c->new_orphans -= 1; in ubifs_delete_orphan()
141 spin_unlock(&c->orphan_lock); in ubifs_delete_orphan()
147 spin_unlock(&c->orphan_lock); in ubifs_delete_orphan()
148 ubifs_err(c, "missing orphan ino %lu", (unsigned long)inum); in ubifs_delete_orphan()
153 * ubifs_orphan_start_commit - start commit of orphans.
154 * @c: UBIFS file-system description object
158 int ubifs_orphan_start_commit(struct ubifs_info *c) in ubifs_orphan_start_commit() argument
162 spin_lock(&c->orphan_lock); in ubifs_orphan_start_commit()
163 last = &c->orph_cnext; in ubifs_orphan_start_commit()
164 list_for_each_entry(orphan, &c->orph_new, new_list) { in ubifs_orphan_start_commit()
165 ubifs_assert(orphan->new); in ubifs_orphan_start_commit()
166 ubifs_assert(!orphan->cmt); in ubifs_orphan_start_commit()
167 orphan->new = 0; in ubifs_orphan_start_commit()
168 orphan->cmt = 1; in ubifs_orphan_start_commit()
170 last = &orphan->cnext; in ubifs_orphan_start_commit()
173 c->cmt_orphans = c->new_orphans; in ubifs_orphan_start_commit()
174 c->new_orphans = 0; in ubifs_orphan_start_commit()
175 dbg_cmt("%d orphans to commit", c->cmt_orphans); in ubifs_orphan_start_commit()
176 INIT_LIST_HEAD(&c->orph_new); in ubifs_orphan_start_commit()
177 if (c->tot_orphans == 0) in ubifs_orphan_start_commit()
178 c->no_orphs = 1; in ubifs_orphan_start_commit()
180 c->no_orphs = 0; in ubifs_orphan_start_commit()
181 spin_unlock(&c->orphan_lock); in ubifs_orphan_start_commit()
186 * avail_orphs - calculate available space.
187 * @c: UBIFS file-system description object
192 static int avail_orphs(struct ubifs_info *c) in avail_orphs() argument
196 avail_lebs = c->orph_lebs - (c->ohead_lnum - c->orph_first) - 1; in avail_orphs()
198 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); in avail_orphs()
199 gap = c->leb_size - c->ohead_offs; in avail_orphs()
201 avail += (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64); in avail_orphs()
206 * tot_avail_orphs - calculate total space.
207 * @c: UBIFS file-system description object
212 static int tot_avail_orphs(struct ubifs_info *c) in tot_avail_orphs() argument
216 avail_lebs = c->orph_lebs; in tot_avail_orphs()
218 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); in tot_avail_orphs()
223 * do_write_orph_node - write a node to the orphan head.
224 * @c: UBIFS file-system description object
232 static int do_write_orph_node(struct ubifs_info *c, int len, int atomic) in do_write_orph_node() argument
237 ubifs_assert(c->ohead_offs == 0); in do_write_orph_node()
238 ubifs_prepare_node(c, c->orph_buf, len, 1); in do_write_orph_node()
239 len = ALIGN(len, c->min_io_size); in do_write_orph_node()
240 err = ubifs_leb_change(c, c->ohead_lnum, c->orph_buf, len); in do_write_orph_node()
242 if (c->ohead_offs == 0) { in do_write_orph_node()
244 err = ubifs_leb_unmap(c, c->ohead_lnum); in do_write_orph_node()
248 err = ubifs_write_node(c, c->orph_buf, len, c->ohead_lnum, in do_write_orph_node()
249 c->ohead_offs); in do_write_orph_node()
255 * write_orph_node - write an orphan node.
256 * @c: UBIFS file-system description object
263 static int write_orph_node(struct ubifs_info *c, int atomic) in write_orph_node() argument
269 ubifs_assert(c->cmt_orphans > 0); in write_orph_node()
270 gap = c->leb_size - c->ohead_offs; in write_orph_node()
272 c->ohead_lnum += 1; in write_orph_node()
273 c->ohead_offs = 0; in write_orph_node()
274 gap = c->leb_size; in write_orph_node()
275 if (c->ohead_lnum > c->orph_last) { in write_orph_node()
280 ubifs_err(c, "out of space in orphan area"); in write_orph_node()
281 return -EINVAL; in write_orph_node()
284 cnt = (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64); in write_orph_node()
285 if (cnt > c->cmt_orphans) in write_orph_node()
286 cnt = c->cmt_orphans; in write_orph_node()
288 ubifs_assert(c->orph_buf); in write_orph_node()
289 orph = c->orph_buf; in write_orph_node()
290 orph->ch.node_type = UBIFS_ORPH_NODE; in write_orph_node()
291 spin_lock(&c->orphan_lock); in write_orph_node()
292 cnext = c->orph_cnext; in write_orph_node()
295 ubifs_assert(orphan->cmt); in write_orph_node()
296 orph->inos[i] = cpu_to_le64(orphan->inum); in write_orph_node()
297 orphan->cmt = 0; in write_orph_node()
298 cnext = orphan->cnext; in write_orph_node()
299 orphan->cnext = NULL; in write_orph_node()
301 c->orph_cnext = cnext; in write_orph_node()
302 c->cmt_orphans -= cnt; in write_orph_node()
303 spin_unlock(&c->orphan_lock); in write_orph_node()
304 if (c->cmt_orphans) in write_orph_node()
305 orph->cmt_no = cpu_to_le64(c->cmt_no); in write_orph_node()
308 orph->cmt_no = cpu_to_le64((c->cmt_no) | (1ULL << 63)); in write_orph_node()
309 ubifs_assert(c->ohead_offs + len <= c->leb_size); in write_orph_node()
310 ubifs_assert(c->ohead_lnum >= c->orph_first); in write_orph_node()
311 ubifs_assert(c->ohead_lnum <= c->orph_last); in write_orph_node()
312 err = do_write_orph_node(c, len, atomic); in write_orph_node()
313 c->ohead_offs += ALIGN(len, c->min_io_size); in write_orph_node()
314 c->ohead_offs = ALIGN(c->ohead_offs, 8); in write_orph_node()
319 * write_orph_nodes - write orphan nodes until there are no more to commit.
320 * @c: UBIFS file-system description object
326 static int write_orph_nodes(struct ubifs_info *c, int atomic) in write_orph_nodes() argument
330 while (c->cmt_orphans > 0) { in write_orph_nodes()
331 err = write_orph_node(c, atomic); in write_orph_nodes()
339 for (lnum = c->ohead_lnum + 1; lnum <= c->orph_last; lnum++) { in write_orph_nodes()
340 err = ubifs_leb_unmap(c, lnum); in write_orph_nodes()
349 * consolidate - consolidate the orphan area.
350 * @c: UBIFS file-system description object
359 static int consolidate(struct ubifs_info *c) in consolidate() argument
361 int tot_avail = tot_avail_orphs(c), err = 0; in consolidate()
363 spin_lock(&c->orphan_lock); in consolidate()
365 tot_avail, c->tot_orphans); in consolidate()
366 if (c->tot_orphans - c->new_orphans <= tot_avail) { in consolidate()
370 /* Change the cnext list to include all non-new orphans */ in consolidate()
371 last = &c->orph_cnext; in consolidate()
372 list_for_each_entry(orphan, &c->orph_list, list) { in consolidate()
373 if (orphan->new) in consolidate()
375 orphan->cmt = 1; in consolidate()
377 last = &orphan->cnext; in consolidate()
381 ubifs_assert(cnt == c->tot_orphans - c->new_orphans); in consolidate()
382 c->cmt_orphans = cnt; in consolidate()
383 c->ohead_lnum = c->orph_first; in consolidate()
384 c->ohead_offs = 0; in consolidate()
390 ubifs_err(c, "out of space in orphan area"); in consolidate()
391 err = -EINVAL; in consolidate()
393 spin_unlock(&c->orphan_lock); in consolidate()
398 * commit_orphans - commit orphans.
399 * @c: UBIFS file-system description object
404 static int commit_orphans(struct ubifs_info *c) in commit_orphans() argument
408 ubifs_assert(c->cmt_orphans > 0); in commit_orphans()
409 avail = avail_orphs(c); in commit_orphans()
410 if (avail < c->cmt_orphans) { in commit_orphans()
412 err = consolidate(c); in commit_orphans()
417 err = write_orph_nodes(c, atomic); in commit_orphans()
422 * erase_deleted - erase the orphans marked for deletion.
423 * @c: UBIFS file-system description object
430 static void erase_deleted(struct ubifs_info *c) in erase_deleted() argument
434 spin_lock(&c->orphan_lock); in erase_deleted()
435 dnext = c->orph_dnext; in erase_deleted()
438 dnext = orphan->dnext; in erase_deleted()
439 ubifs_assert(!orphan->new); in erase_deleted()
440 ubifs_assert(orphan->del); in erase_deleted()
441 rb_erase(&orphan->rb, &c->orph_tree); in erase_deleted()
442 list_del(&orphan->list); in erase_deleted()
443 c->tot_orphans -= 1; in erase_deleted()
444 dbg_gen("deleting orphan ino %lu", (unsigned long)orphan->inum); in erase_deleted()
447 c->orph_dnext = NULL; in erase_deleted()
448 spin_unlock(&c->orphan_lock); in erase_deleted()
452 * ubifs_orphan_end_commit - end commit of orphans.
453 * @c: UBIFS file-system description object
457 int ubifs_orphan_end_commit(struct ubifs_info *c) in ubifs_orphan_end_commit() argument
461 if (c->cmt_orphans != 0) { in ubifs_orphan_end_commit()
462 err = commit_orphans(c); in ubifs_orphan_end_commit()
466 erase_deleted(c); in ubifs_orphan_end_commit()
467 err = dbg_check_orphans(c); in ubifs_orphan_end_commit()
472 * ubifs_clear_orphans - erase all LEBs used for orphans.
473 * @c: UBIFS file-system description object
477 * orphans, and un-maps them.
479 int ubifs_clear_orphans(struct ubifs_info *c) in ubifs_clear_orphans() argument
483 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { in ubifs_clear_orphans()
484 err = ubifs_leb_unmap(c, lnum); in ubifs_clear_orphans()
488 c->ohead_lnum = c->orph_first; in ubifs_clear_orphans()
489 c->ohead_offs = 0; in ubifs_clear_orphans()
494 * insert_dead_orphan - insert an orphan.
495 * @c: UBIFS file-system description object
499 * must be kept until the next commit, so it is added to the rb-tree and the
502 static int insert_dead_orphan(struct ubifs_info *c, ino_t inum) in insert_dead_orphan() argument
509 return -ENOMEM; in insert_dead_orphan()
510 orphan->inum = inum; in insert_dead_orphan()
512 p = &c->orph_tree.rb_node; in insert_dead_orphan()
516 if (inum < o->inum) in insert_dead_orphan()
517 p = &(*p)->rb_left; in insert_dead_orphan()
518 else if (inum > o->inum) in insert_dead_orphan()
519 p = &(*p)->rb_right; in insert_dead_orphan()
521 /* Already added - no problem */ in insert_dead_orphan()
526 c->tot_orphans += 1; in insert_dead_orphan()
527 rb_link_node(&orphan->rb, parent, p); in insert_dead_orphan()
528 rb_insert_color(&orphan->rb, &c->orph_tree); in insert_dead_orphan()
529 list_add_tail(&orphan->list, &c->orph_list); in insert_dead_orphan()
530 orphan->del = 1; in insert_dead_orphan()
531 orphan->dnext = c->orph_dnext; in insert_dead_orphan()
532 c->orph_dnext = orphan; in insert_dead_orphan()
534 c->new_orphans, c->tot_orphans); in insert_dead_orphan()
539 * do_kill_orphans - remove orphan inodes from the index.
540 * @c: UBIFS file-system description object
550 static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb, in do_kill_orphans() argument
560 list_for_each_entry(snod, &sleb->nodes, list) { in do_kill_orphans()
561 if (snod->type != UBIFS_ORPH_NODE) { in do_kill_orphans()
562 ubifs_err(c, "invalid node type %d in orphan area at %d:%d", in do_kill_orphans()
563 snod->type, sleb->lnum, snod->offs); in do_kill_orphans()
564 ubifs_dump_node(c, snod->node); in do_kill_orphans()
565 return -EINVAL; in do_kill_orphans()
568 orph = snod->node; in do_kill_orphans()
571 cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX; in do_kill_orphans()
578 * because the master node has not been re-written. in do_kill_orphans()
580 if (cmt_no > c->cmt_no) in do_kill_orphans()
581 c->cmt_no = cmt_no; in do_kill_orphans()
589 ubifs_err(c, "out of order commit number %llu in orphan node at %d:%d", in do_kill_orphans()
590 cmt_no, sleb->lnum, snod->offs); in do_kill_orphans()
591 ubifs_dump_node(c, snod->node); in do_kill_orphans()
592 return -EINVAL; in do_kill_orphans()
594 dbg_rcvry("out of date LEB %d", sleb->lnum); in do_kill_orphans()
602 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; in do_kill_orphans()
604 inum = le64_to_cpu(orph->inos[i]); in do_kill_orphans()
607 err = ubifs_tnc_remove_ino(c, inum); in do_kill_orphans()
610 err = insert_dead_orphan(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()
628 * kill_orphans - remove all orphan inodes from the index.
629 * @c: UBIFS file-system description object
637 static int kill_orphans(struct ubifs_info *c) in kill_orphans() argument
642 c->ohead_lnum = c->orph_first; in kill_orphans()
643 c->ohead_offs = 0; in kill_orphans()
644 /* Check no-orphans flag and skip this if no orphans */ in kill_orphans()
645 if (c->no_orphs) { in kill_orphans()
650 * Orph nodes always start at c->orph_first and are written to each in kill_orphans()
654 * marked (top bit of orph->cmt_no is set to 1). It is possible that in kill_orphans()
660 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { in kill_orphans()
664 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1); in kill_orphans()
666 if (PTR_ERR(sleb) == -EUCLEAN) in kill_orphans()
667 sleb = ubifs_recover_leb(c, lnum, 0, in kill_orphans()
668 c->sbuf, -1); in kill_orphans()
674 err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate, in kill_orphans()
680 if (sleb->endpt) { in kill_orphans()
681 c->ohead_lnum = lnum; in kill_orphans()
682 c->ohead_offs = sleb->endpt; in kill_orphans()
690 * ubifs_mount_orphans - delete orphan inodes and erase LEBs that recorded them.
691 * @c: UBIFS file-system description object
699 int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only) in ubifs_mount_orphans() argument
703 c->max_orphans = tot_avail_orphs(c); in ubifs_mount_orphans()
706 c->orph_buf = vmalloc(c->leb_size); in ubifs_mount_orphans()
707 if (!c->orph_buf) in ubifs_mount_orphans()
708 return -ENOMEM; in ubifs_mount_orphans()
712 err = kill_orphans(c); in ubifs_mount_orphans()
714 err = ubifs_clear_orphans(c); in ubifs_mount_orphans()
737 static int dbg_find_orphan(struct ubifs_info *c, ino_t inum) in dbg_find_orphan() argument
742 spin_lock(&c->orphan_lock); in dbg_find_orphan()
743 p = c->orph_tree.rb_node; in dbg_find_orphan()
746 if (inum < o->inum) in dbg_find_orphan()
747 p = p->rb_left; in dbg_find_orphan()
748 else if (inum > o->inum) in dbg_find_orphan()
749 p = p->rb_right; in dbg_find_orphan()
751 spin_unlock(&c->orphan_lock); in dbg_find_orphan()
755 spin_unlock(&c->orphan_lock); in dbg_find_orphan()
766 return -ENOMEM; in dbg_ins_check_orphan()
767 orphan->inum = inum; in dbg_ins_check_orphan()
769 p = &root->rb_node; in dbg_ins_check_orphan()
773 if (inum < o->inum) in dbg_ins_check_orphan()
774 p = &(*p)->rb_left; in dbg_ins_check_orphan()
775 else if (inum > o->inum) in dbg_ins_check_orphan()
776 p = &(*p)->rb_right; in dbg_ins_check_orphan()
782 rb_link_node(&orphan->rb, parent, p); in dbg_ins_check_orphan()
783 rb_insert_color(&orphan->rb, root); in dbg_ins_check_orphan()
792 p = root->rb_node; in dbg_find_check_orphan()
795 if (inum < o->inum) in dbg_find_check_orphan()
796 p = p->rb_left; in dbg_find_check_orphan()
797 else if (inum > o->inum) in dbg_find_check_orphan()
798 p = p->rb_right; in dbg_find_check_orphan()
813 static int dbg_orphan_check(struct ubifs_info *c, struct ubifs_zbranch *zbr, in dbg_orphan_check() argument
820 inum = key_inum(c, &zbr->key); in dbg_orphan_check()
821 if (inum != ci->last_ino) { in dbg_orphan_check()
823 if (key_type(c, &zbr->key) != UBIFS_INO_KEY) in dbg_orphan_check()
824 ubifs_err(c, "found orphan node ino %lu, type %d", in dbg_orphan_check()
825 (unsigned long)inum, key_type(c, &zbr->key)); in dbg_orphan_check()
826 ci->last_ino = inum; in dbg_orphan_check()
827 ci->tot_inos += 1; in dbg_orphan_check()
828 err = ubifs_tnc_read_node(c, zbr, ci->node); in dbg_orphan_check()
830 ubifs_err(c, "node read failed, error %d", err); in dbg_orphan_check()
833 if (ci->node->nlink == 0) in dbg_orphan_check()
835 if (!dbg_find_check_orphan(&ci->root, inum) && in dbg_orphan_check()
836 !dbg_find_orphan(c, inum)) { in dbg_orphan_check()
837 ubifs_err(c, "missing orphan, ino %lu", in dbg_orphan_check()
839 ci->missing += 1; in dbg_orphan_check()
842 ci->leaf_cnt += 1; in dbg_orphan_check()
853 list_for_each_entry(snod, &sleb->nodes, list) { in dbg_read_orphans()
855 if (snod->type != UBIFS_ORPH_NODE) in dbg_read_orphans()
857 orph = snod->node; in dbg_read_orphans()
858 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; in dbg_read_orphans()
860 inum = le64_to_cpu(orph->inos[i]); in dbg_read_orphans()
861 err = dbg_ins_check_orphan(&ci->root, inum); in dbg_read_orphans()
869 static int dbg_scan_orphans(struct ubifs_info *c, struct check_info *ci) in dbg_scan_orphans() argument
874 /* Check no-orphans flag and skip this if no orphans */ in dbg_scan_orphans()
875 if (c->no_orphs) in dbg_scan_orphans()
878 buf = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL); in dbg_scan_orphans()
880 ubifs_err(c, "cannot allocate memory to check orphans"); in dbg_scan_orphans()
884 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { in dbg_scan_orphans()
887 sleb = ubifs_scan(c, lnum, 0, buf, 0); in dbg_scan_orphans()
903 static int dbg_check_orphans(struct ubifs_info *c) in dbg_check_orphans() argument
908 if (!dbg_is_chk_orph(c)) in dbg_check_orphans()
918 ubifs_err(c, "out of memory"); in dbg_check_orphans()
919 return -ENOMEM; in dbg_check_orphans()
922 err = dbg_scan_orphans(c, &ci); in dbg_check_orphans()
926 err = dbg_walk_index(c, &dbg_orphan_check, NULL, &ci); in dbg_check_orphans()
928 ubifs_err(c, "cannot scan TNC, error %d", err); in dbg_check_orphans()
933 ubifs_err(c, "%lu missing orphan(s)", ci.missing); in dbg_check_orphans()
934 err = -EINVAL; in dbg_check_orphans()