xref: /linux/fs/ubifs/orphan.c (revision 6eb2fb3170549737207974c2c6ad34bcc2f3025e)
1 /*
2  * This file is part of UBIFS.
3  *
4  * Copyright (C) 2006-2008 Nokia Corporation.
5  *
6  * This program is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU General Public License version 2 as published by
8  * the Free Software Foundation.
9  *
10  * This program is distributed in the hope that it will be useful, but WITHOUT
11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
13  * more details.
14  *
15  * You should have received a copy of the GNU General Public License along with
16  * this program; if not, write to the Free Software Foundation, Inc., 51
17  * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18  *
19  * Author: Adrian Hunter
20  */
21 
22 #include "ubifs.h"
23 
24 /*
25  * An orphan is an inode number whose inode node has been committed to the index
26  * with a link count of zero. That happens when an open file is deleted
27  * (unlinked) and then a commit is run. In the normal course of events the inode
28  * would be deleted when the file is closed. However in the case of an unclean
29  * unmount, orphans need to be accounted for. After an unclean unmount, the
30  * orphans' inodes must be deleted which means either scanning the entire index
31  * looking for them, or keeping a list on flash somewhere. This unit implements
32  * the latter approach.
33  *
34  * The orphan area is a fixed number of LEBs situated between the LPT area and
35  * the main area. The number of orphan area LEBs is specified when the file
36  * system is created. The minimum number is 1. The size of the orphan area
37  * should be so that it can hold the maximum number of orphans that are expected
38  * to ever exist at one time.
39  *
40  * The number of orphans that can fit in a LEB is:
41  *
42  *         (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)
43  *
44  * For example: a 15872 byte LEB can fit 1980 orphans so 1 LEB may be enough.
45  *
46  * Orphans are accumulated in a rb-tree. When an inode's link count drops to
47  * zero, the inode number is added to the rb-tree. It is removed from the tree
48  * when the inode is deleted.  Any new orphans that are in the orphan tree when
49  * the commit is run, are written to the orphan area in 1 or more orphan nodes.
50  * If the orphan area is full, it is consolidated to make space.  There is
51  * always enough space because validation prevents the user from creating more
52  * than the maximum number of orphans allowed.
53  */
54 
55 static int dbg_check_orphans(struct ubifs_info *c);
56 
57 /**
58  * ubifs_add_orphan - add an orphan.
59  * @c: UBIFS file-system description object
60  * @inum: orphan inode number
61  *
62  * Add an orphan. This function is called when an inodes link count drops to
63  * zero.
64  */
65 int ubifs_add_orphan(struct ubifs_info *c, ino_t inum)
66 {
67 	struct ubifs_orphan *orphan, *o;
68 	struct rb_node **p, *parent = NULL;
69 
70 	orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_NOFS);
71 	if (!orphan)
72 		return -ENOMEM;
73 	orphan->inum = inum;
74 	orphan->new = 1;
75 
76 	spin_lock(&c->orphan_lock);
77 	if (c->tot_orphans >= c->max_orphans) {
78 		spin_unlock(&c->orphan_lock);
79 		kfree(orphan);
80 		return -ENFILE;
81 	}
82 	p = &c->orph_tree.rb_node;
83 	while (*p) {
84 		parent = *p;
85 		o = rb_entry(parent, struct ubifs_orphan, rb);
86 		if (inum < o->inum)
87 			p = &(*p)->rb_left;
88 		else if (inum > o->inum)
89 			p = &(*p)->rb_right;
90 		else {
91 			ubifs_err("orphaned twice");
92 			spin_unlock(&c->orphan_lock);
93 			kfree(orphan);
94 			return 0;
95 		}
96 	}
97 	c->tot_orphans += 1;
98 	c->new_orphans += 1;
99 	rb_link_node(&orphan->rb, parent, p);
100 	rb_insert_color(&orphan->rb, &c->orph_tree);
101 	list_add_tail(&orphan->list, &c->orph_list);
102 	list_add_tail(&orphan->new_list, &c->orph_new);
103 	spin_unlock(&c->orphan_lock);
104 	dbg_gen("ino %lu", (unsigned long)inum);
105 	return 0;
106 }
107 
108 /**
109  * ubifs_delete_orphan - delete an orphan.
110  * @c: UBIFS file-system description object
111  * @inum: orphan inode number
112  *
113  * Delete an orphan. This function is called when an inode is deleted.
114  */
115 void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
116 {
117 	struct ubifs_orphan *o;
118 	struct rb_node *p;
119 
120 	spin_lock(&c->orphan_lock);
121 	p = c->orph_tree.rb_node;
122 	while (p) {
123 		o = rb_entry(p, struct ubifs_orphan, rb);
124 		if (inum < o->inum)
125 			p = p->rb_left;
126 		else if (inum > o->inum)
127 			p = p->rb_right;
128 		else {
129 			if (o->del) {
130 				spin_unlock(&c->orphan_lock);
131 				dbg_gen("deleted twice ino %lu",
132 					(unsigned long)inum);
133 				return;
134 			}
135 			if (o->cmt) {
136 				o->del = 1;
137 				o->dnext = c->orph_dnext;
138 				c->orph_dnext = o;
139 				spin_unlock(&c->orphan_lock);
140 				dbg_gen("delete later ino %lu",
141 					(unsigned long)inum);
142 				return;
143 			}
144 			rb_erase(p, &c->orph_tree);
145 			list_del(&o->list);
146 			c->tot_orphans -= 1;
147 			if (o->new) {
148 				list_del(&o->new_list);
149 				c->new_orphans -= 1;
150 			}
151 			spin_unlock(&c->orphan_lock);
152 			kfree(o);
153 			dbg_gen("inum %lu", (unsigned long)inum);
154 			return;
155 		}
156 	}
157 	spin_unlock(&c->orphan_lock);
158 	ubifs_err("missing orphan ino %lu", (unsigned long)inum);
159 	dump_stack();
160 }
161 
162 /**
163  * ubifs_orphan_start_commit - start commit of orphans.
164  * @c: UBIFS file-system description object
165  *
166  * Start commit of orphans.
167  */
168 int ubifs_orphan_start_commit(struct ubifs_info *c)
169 {
170 	struct ubifs_orphan *orphan, **last;
171 
172 	spin_lock(&c->orphan_lock);
173 	last = &c->orph_cnext;
174 	list_for_each_entry(orphan, &c->orph_new, new_list) {
175 		ubifs_assert(orphan->new);
176 		ubifs_assert(!orphan->cmt);
177 		orphan->new = 0;
178 		orphan->cmt = 1;
179 		*last = orphan;
180 		last = &orphan->cnext;
181 	}
182 	*last = NULL;
183 	c->cmt_orphans = c->new_orphans;
184 	c->new_orphans = 0;
185 	dbg_cmt("%d orphans to commit", c->cmt_orphans);
186 	INIT_LIST_HEAD(&c->orph_new);
187 	if (c->tot_orphans == 0)
188 		c->no_orphs = 1;
189 	else
190 		c->no_orphs = 0;
191 	spin_unlock(&c->orphan_lock);
192 	return 0;
193 }
194 
195 /**
196  * avail_orphs - calculate available space.
197  * @c: UBIFS file-system description object
198  *
199  * This function returns the number of orphans that can be written in the
200  * available space.
201  */
202 static int avail_orphs(struct ubifs_info *c)
203 {
204 	int avail_lebs, avail, gap;
205 
206 	avail_lebs = c->orph_lebs - (c->ohead_lnum - c->orph_first) - 1;
207 	avail = avail_lebs *
208 	       ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64));
209 	gap = c->leb_size - c->ohead_offs;
210 	if (gap >= UBIFS_ORPH_NODE_SZ + sizeof(__le64))
211 		avail += (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64);
212 	return avail;
213 }
214 
215 /**
216  * tot_avail_orphs - calculate total space.
217  * @c: UBIFS file-system description object
218  *
219  * This function returns the number of orphans that can be written in half
220  * the total space. That leaves half the space for adding new orphans.
221  */
222 static int tot_avail_orphs(struct ubifs_info *c)
223 {
224 	int avail_lebs, avail;
225 
226 	avail_lebs = c->orph_lebs;
227 	avail = avail_lebs *
228 	       ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64));
229 	return avail / 2;
230 }
231 
232 /**
233  * do_write_orph_node - write a node to the orphan head.
234  * @c: UBIFS file-system description object
235  * @len: length of node
236  * @atomic: write atomically
237  *
238  * This function writes a node to the orphan head from the orphan buffer. If
239  * %atomic is not zero, then the write is done atomically. On success, %0 is
240  * returned, otherwise a negative error code is returned.
241  */
242 static int do_write_orph_node(struct ubifs_info *c, int len, int atomic)
243 {
244 	int err = 0;
245 
246 	if (atomic) {
247 		ubifs_assert(c->ohead_offs == 0);
248 		ubifs_prepare_node(c, c->orph_buf, len, 1);
249 		len = ALIGN(len, c->min_io_size);
250 		err = ubifs_leb_change(c, c->ohead_lnum, c->orph_buf, len);
251 	} else {
252 		if (c->ohead_offs == 0) {
253 			/* Ensure LEB has been unmapped */
254 			err = ubifs_leb_unmap(c, c->ohead_lnum);
255 			if (err)
256 				return err;
257 		}
258 		err = ubifs_write_node(c, c->orph_buf, len, c->ohead_lnum,
259 				       c->ohead_offs);
260 	}
261 	return err;
262 }
263 
264 /**
265  * write_orph_node - write an orphan node.
266  * @c: UBIFS file-system description object
267  * @atomic: write atomically
268  *
269  * This function builds an orphan node from the cnext list and writes it to the
270  * orphan head. On success, %0 is returned, otherwise a negative error code
271  * is returned.
272  */
273 static int write_orph_node(struct ubifs_info *c, int atomic)
274 {
275 	struct ubifs_orphan *orphan, *cnext;
276 	struct ubifs_orph_node *orph;
277 	int gap, err, len, cnt, i;
278 
279 	ubifs_assert(c->cmt_orphans > 0);
280 	gap = c->leb_size - c->ohead_offs;
281 	if (gap < UBIFS_ORPH_NODE_SZ + sizeof(__le64)) {
282 		c->ohead_lnum += 1;
283 		c->ohead_offs = 0;
284 		gap = c->leb_size;
285 		if (c->ohead_lnum > c->orph_last) {
286 			/*
287 			 * We limit the number of orphans so that this should
288 			 * never happen.
289 			 */
290 			ubifs_err("out of space in orphan area");
291 			return -EINVAL;
292 		}
293 	}
294 	cnt = (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64);
295 	if (cnt > c->cmt_orphans)
296 		cnt = c->cmt_orphans;
297 	len = UBIFS_ORPH_NODE_SZ + cnt * sizeof(__le64);
298 	ubifs_assert(c->orph_buf);
299 	orph = c->orph_buf;
300 	orph->ch.node_type = UBIFS_ORPH_NODE;
301 	spin_lock(&c->orphan_lock);
302 	cnext = c->orph_cnext;
303 	for (i = 0; i < cnt; i++) {
304 		orphan = cnext;
305 		ubifs_assert(orphan->cmt);
306 		orph->inos[i] = cpu_to_le64(orphan->inum);
307 		orphan->cmt = 0;
308 		cnext = orphan->cnext;
309 		orphan->cnext = NULL;
310 	}
311 	c->orph_cnext = cnext;
312 	c->cmt_orphans -= cnt;
313 	spin_unlock(&c->orphan_lock);
314 	if (c->cmt_orphans)
315 		orph->cmt_no = cpu_to_le64(c->cmt_no);
316 	else
317 		/* Mark the last node of the commit */
318 		orph->cmt_no = cpu_to_le64((c->cmt_no) | (1ULL << 63));
319 	ubifs_assert(c->ohead_offs + len <= c->leb_size);
320 	ubifs_assert(c->ohead_lnum >= c->orph_first);
321 	ubifs_assert(c->ohead_lnum <= c->orph_last);
322 	err = do_write_orph_node(c, len, atomic);
323 	c->ohead_offs += ALIGN(len, c->min_io_size);
324 	c->ohead_offs = ALIGN(c->ohead_offs, 8);
325 	return err;
326 }
327 
328 /**
329  * write_orph_nodes - write orphan nodes until there are no more to commit.
330  * @c: UBIFS file-system description object
331  * @atomic: write atomically
332  *
333  * This function writes orphan nodes for all the orphans to commit. On success,
334  * %0 is returned, otherwise a negative error code is returned.
335  */
336 static int write_orph_nodes(struct ubifs_info *c, int atomic)
337 {
338 	int err;
339 
340 	while (c->cmt_orphans > 0) {
341 		err = write_orph_node(c, atomic);
342 		if (err)
343 			return err;
344 	}
345 	if (atomic) {
346 		int lnum;
347 
348 		/* Unmap any unused LEBs after consolidation */
349 		lnum = c->ohead_lnum + 1;
350 		for (lnum = c->ohead_lnum + 1; lnum <= c->orph_last; lnum++) {
351 			err = ubifs_leb_unmap(c, lnum);
352 			if (err)
353 				return err;
354 		}
355 	}
356 	return 0;
357 }
358 
359 /**
360  * consolidate - consolidate the orphan area.
361  * @c: UBIFS file-system description object
362  *
363  * This function enables consolidation by putting all the orphans into the list
364  * to commit. The list is in the order that the orphans were added, and the
365  * LEBs are written atomically in order, so at no time can orphans be lost by
366  * an unclean unmount.
367  *
368  * This function returns %0 on success and a negative error code on failure.
369  */
370 static int consolidate(struct ubifs_info *c)
371 {
372 	int tot_avail = tot_avail_orphs(c), err = 0;
373 
374 	spin_lock(&c->orphan_lock);
375 	dbg_cmt("there is space for %d orphans and there are %d",
376 		tot_avail, c->tot_orphans);
377 	if (c->tot_orphans - c->new_orphans <= tot_avail) {
378 		struct ubifs_orphan *orphan, **last;
379 		int cnt = 0;
380 
381 		/* Change the cnext list to include all non-new orphans */
382 		last = &c->orph_cnext;
383 		list_for_each_entry(orphan, &c->orph_list, list) {
384 			if (orphan->new)
385 				continue;
386 			orphan->cmt = 1;
387 			*last = orphan;
388 			last = &orphan->cnext;
389 			cnt += 1;
390 		}
391 		*last = NULL;
392 		ubifs_assert(cnt == c->tot_orphans - c->new_orphans);
393 		c->cmt_orphans = cnt;
394 		c->ohead_lnum = c->orph_first;
395 		c->ohead_offs = 0;
396 	} else {
397 		/*
398 		 * We limit the number of orphans so that this should
399 		 * never happen.
400 		 */
401 		ubifs_err("out of space in orphan area");
402 		err = -EINVAL;
403 	}
404 	spin_unlock(&c->orphan_lock);
405 	return err;
406 }
407 
408 /**
409  * commit_orphans - commit orphans.
410  * @c: UBIFS file-system description object
411  *
412  * This function commits orphans to flash. On success, %0 is returned,
413  * otherwise a negative error code is returned.
414  */
415 static int commit_orphans(struct ubifs_info *c)
416 {
417 	int avail, atomic = 0, err;
418 
419 	ubifs_assert(c->cmt_orphans > 0);
420 	avail = avail_orphs(c);
421 	if (avail < c->cmt_orphans) {
422 		/* Not enough space to write new orphans, so consolidate */
423 		err = consolidate(c);
424 		if (err)
425 			return err;
426 		atomic = 1;
427 	}
428 	err = write_orph_nodes(c, atomic);
429 	return err;
430 }
431 
432 /**
433  * erase_deleted - erase the orphans marked for deletion.
434  * @c: UBIFS file-system description object
435  *
436  * During commit, the orphans being committed cannot be deleted, so they are
437  * marked for deletion and deleted by this function. Also, the recovery
438  * adds killed orphans to the deletion list, and therefore they are deleted
439  * here too.
440  */
441 static void erase_deleted(struct ubifs_info *c)
442 {
443 	struct ubifs_orphan *orphan, *dnext;
444 
445 	spin_lock(&c->orphan_lock);
446 	dnext = c->orph_dnext;
447 	while (dnext) {
448 		orphan = dnext;
449 		dnext = orphan->dnext;
450 		ubifs_assert(!orphan->new);
451 		ubifs_assert(orphan->del);
452 		rb_erase(&orphan->rb, &c->orph_tree);
453 		list_del(&orphan->list);
454 		c->tot_orphans -= 1;
455 		dbg_gen("deleting orphan ino %lu", (unsigned long)orphan->inum);
456 		kfree(orphan);
457 	}
458 	c->orph_dnext = NULL;
459 	spin_unlock(&c->orphan_lock);
460 }
461 
462 /**
463  * ubifs_orphan_end_commit - end commit of orphans.
464  * @c: UBIFS file-system description object
465  *
466  * End commit of orphans.
467  */
468 int ubifs_orphan_end_commit(struct ubifs_info *c)
469 {
470 	int err;
471 
472 	if (c->cmt_orphans != 0) {
473 		err = commit_orphans(c);
474 		if (err)
475 			return err;
476 	}
477 	erase_deleted(c);
478 	err = dbg_check_orphans(c);
479 	return err;
480 }
481 
482 /**
483  * ubifs_clear_orphans - erase all LEBs used for orphans.
484  * @c: UBIFS file-system description object
485  *
486  * If recovery is not required, then the orphans from the previous session
487  * are not needed. This function locates the LEBs used to record
488  * orphans, and un-maps them.
489  */
490 int ubifs_clear_orphans(struct ubifs_info *c)
491 {
492 	int lnum, err;
493 
494 	for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
495 		err = ubifs_leb_unmap(c, lnum);
496 		if (err)
497 			return err;
498 	}
499 	c->ohead_lnum = c->orph_first;
500 	c->ohead_offs = 0;
501 	return 0;
502 }
503 
504 /**
505  * insert_dead_orphan - insert an orphan.
506  * @c: UBIFS file-system description object
507  * @inum: orphan inode number
508  *
509  * This function is a helper to the 'do_kill_orphans()' function. The orphan
510  * must be kept until the next commit, so it is added to the rb-tree and the
511  * deletion list.
512  */
513 static int insert_dead_orphan(struct ubifs_info *c, ino_t inum)
514 {
515 	struct ubifs_orphan *orphan, *o;
516 	struct rb_node **p, *parent = NULL;
517 
518 	orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_KERNEL);
519 	if (!orphan)
520 		return -ENOMEM;
521 	orphan->inum = inum;
522 
523 	p = &c->orph_tree.rb_node;
524 	while (*p) {
525 		parent = *p;
526 		o = rb_entry(parent, struct ubifs_orphan, rb);
527 		if (inum < o->inum)
528 			p = &(*p)->rb_left;
529 		else if (inum > o->inum)
530 			p = &(*p)->rb_right;
531 		else {
532 			/* Already added - no problem */
533 			kfree(orphan);
534 			return 0;
535 		}
536 	}
537 	c->tot_orphans += 1;
538 	rb_link_node(&orphan->rb, parent, p);
539 	rb_insert_color(&orphan->rb, &c->orph_tree);
540 	list_add_tail(&orphan->list, &c->orph_list);
541 	orphan->del = 1;
542 	orphan->dnext = c->orph_dnext;
543 	c->orph_dnext = orphan;
544 	dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum,
545 		c->new_orphans, c->tot_orphans);
546 	return 0;
547 }
548 
549 /**
550  * do_kill_orphans - remove orphan inodes from the index.
551  * @c: UBIFS file-system description object
552  * @sleb: scanned LEB
553  * @last_cmt_no: cmt_no of last orphan node read is passed and returned here
554  * @outofdate: whether the LEB is out of date is returned here
555  * @last_flagged: whether the end orphan node is encountered
556  *
557  * This function is a helper to the 'kill_orphans()' function. It goes through
558  * every orphan node in a LEB and for every inode number recorded, removes
559  * all keys for that inode from the TNC.
560  */
561 static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
562 			   unsigned long long *last_cmt_no, int *outofdate,
563 			   int *last_flagged)
564 {
565 	struct ubifs_scan_node *snod;
566 	struct ubifs_orph_node *orph;
567 	unsigned long long cmt_no;
568 	ino_t inum;
569 	int i, n, err, first = 1;
570 
571 	list_for_each_entry(snod, &sleb->nodes, list) {
572 		if (snod->type != UBIFS_ORPH_NODE) {
573 			ubifs_err("invalid node type %d in orphan area at %d:%d",
574 				  snod->type, sleb->lnum, snod->offs);
575 			ubifs_dump_node(c, snod->node);
576 			return -EINVAL;
577 		}
578 
579 		orph = snod->node;
580 
581 		/* Check commit number */
582 		cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX;
583 		/*
584 		 * The commit number on the master node may be less, because
585 		 * of a failed commit. If there are several failed commits in a
586 		 * row, the commit number written on orphan nodes will continue
587 		 * to increase (because the commit number is adjusted here) even
588 		 * though the commit number on the master node stays the same
589 		 * because the master node has not been re-written.
590 		 */
591 		if (cmt_no > c->cmt_no)
592 			c->cmt_no = cmt_no;
593 		if (cmt_no < *last_cmt_no && *last_flagged) {
594 			/*
595 			 * The last orphan node had a higher commit number and
596 			 * was flagged as the last written for that commit
597 			 * number. That makes this orphan node, out of date.
598 			 */
599 			if (!first) {
600 				ubifs_err("out of order commit number %llu in orphan node at %d:%d",
601 					  cmt_no, sleb->lnum, snod->offs);
602 				ubifs_dump_node(c, snod->node);
603 				return -EINVAL;
604 			}
605 			dbg_rcvry("out of date LEB %d", sleb->lnum);
606 			*outofdate = 1;
607 			return 0;
608 		}
609 
610 		if (first)
611 			first = 0;
612 
613 		n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3;
614 		for (i = 0; i < n; i++) {
615 			inum = le64_to_cpu(orph->inos[i]);
616 			dbg_rcvry("deleting orphaned inode %lu",
617 				  (unsigned long)inum);
618 			err = ubifs_tnc_remove_ino(c, inum);
619 			if (err)
620 				return err;
621 			err = insert_dead_orphan(c, inum);
622 			if (err)
623 				return err;
624 		}
625 
626 		*last_cmt_no = cmt_no;
627 		if (le64_to_cpu(orph->cmt_no) & (1ULL << 63)) {
628 			dbg_rcvry("last orph node for commit %llu at %d:%d",
629 				  cmt_no, sleb->lnum, snod->offs);
630 			*last_flagged = 1;
631 		} else
632 			*last_flagged = 0;
633 	}
634 
635 	return 0;
636 }
637 
638 /**
639  * kill_orphans - remove all orphan inodes from the index.
640  * @c: UBIFS file-system description object
641  *
642  * If recovery is required, then orphan inodes recorded during the previous
643  * session (which ended with an unclean unmount) must be deleted from the index.
644  * This is done by updating the TNC, but since the index is not updated until
645  * the next commit, the LEBs where the orphan information is recorded are not
646  * erased until the next commit.
647  */
648 static int kill_orphans(struct ubifs_info *c)
649 {
650 	unsigned long long last_cmt_no = 0;
651 	int lnum, err = 0, outofdate = 0, last_flagged = 0;
652 
653 	c->ohead_lnum = c->orph_first;
654 	c->ohead_offs = 0;
655 	/* Check no-orphans flag and skip this if no orphans */
656 	if (c->no_orphs) {
657 		dbg_rcvry("no orphans");
658 		return 0;
659 	}
660 	/*
661 	 * Orph nodes always start at c->orph_first and are written to each
662 	 * successive LEB in turn. Generally unused LEBs will have been unmapped
663 	 * but may contain out of date orphan nodes if the unmap didn't go
664 	 * through. In addition, the last orphan node written for each commit is
665 	 * marked (top bit of orph->cmt_no is set to 1). It is possible that
666 	 * there are orphan nodes from the next commit (i.e. the commit did not
667 	 * complete successfully). In that case, no orphans will have been lost
668 	 * due to the way that orphans are written, and any orphans added will
669 	 * be valid orphans anyway and so can be deleted.
670 	 */
671 	for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
672 		struct ubifs_scan_leb *sleb;
673 
674 		dbg_rcvry("LEB %d", lnum);
675 		sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1);
676 		if (IS_ERR(sleb)) {
677 			if (PTR_ERR(sleb) == -EUCLEAN)
678 				sleb = ubifs_recover_leb(c, lnum, 0,
679 							 c->sbuf, -1);
680 			if (IS_ERR(sleb)) {
681 				err = PTR_ERR(sleb);
682 				break;
683 			}
684 		}
685 		err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate,
686 				      &last_flagged);
687 		if (err || outofdate) {
688 			ubifs_scan_destroy(sleb);
689 			break;
690 		}
691 		if (sleb->endpt) {
692 			c->ohead_lnum = lnum;
693 			c->ohead_offs = sleb->endpt;
694 		}
695 		ubifs_scan_destroy(sleb);
696 	}
697 	return err;
698 }
699 
700 /**
701  * ubifs_mount_orphans - delete orphan inodes and erase LEBs that recorded them.
702  * @c: UBIFS file-system description object
703  * @unclean: indicates recovery from unclean unmount
704  * @read_only: indicates read only mount
705  *
706  * This function is called when mounting to erase orphans from the previous
707  * session. If UBIFS was not unmounted cleanly, then the inodes recorded as
708  * orphans are deleted.
709  */
710 int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only)
711 {
712 	int err = 0;
713 
714 	c->max_orphans = tot_avail_orphs(c);
715 
716 	if (!read_only) {
717 		c->orph_buf = vmalloc(c->leb_size);
718 		if (!c->orph_buf)
719 			return -ENOMEM;
720 	}
721 
722 	if (unclean)
723 		err = kill_orphans(c);
724 	else if (!read_only)
725 		err = ubifs_clear_orphans(c);
726 
727 	return err;
728 }
729 
730 /*
731  * Everything below is related to debugging.
732  */
733 
734 struct check_orphan {
735 	struct rb_node rb;
736 	ino_t inum;
737 };
738 
739 struct check_info {
740 	unsigned long last_ino;
741 	unsigned long tot_inos;
742 	unsigned long missing;
743 	unsigned long long leaf_cnt;
744 	struct ubifs_ino_node *node;
745 	struct rb_root root;
746 };
747 
748 static int dbg_find_orphan(struct ubifs_info *c, ino_t inum)
749 {
750 	struct ubifs_orphan *o;
751 	struct rb_node *p;
752 
753 	spin_lock(&c->orphan_lock);
754 	p = c->orph_tree.rb_node;
755 	while (p) {
756 		o = rb_entry(p, struct ubifs_orphan, rb);
757 		if (inum < o->inum)
758 			p = p->rb_left;
759 		else if (inum > o->inum)
760 			p = p->rb_right;
761 		else {
762 			spin_unlock(&c->orphan_lock);
763 			return 1;
764 		}
765 	}
766 	spin_unlock(&c->orphan_lock);
767 	return 0;
768 }
769 
770 static int dbg_ins_check_orphan(struct rb_root *root, ino_t inum)
771 {
772 	struct check_orphan *orphan, *o;
773 	struct rb_node **p, *parent = NULL;
774 
775 	orphan = kzalloc(sizeof(struct check_orphan), GFP_NOFS);
776 	if (!orphan)
777 		return -ENOMEM;
778 	orphan->inum = inum;
779 
780 	p = &root->rb_node;
781 	while (*p) {
782 		parent = *p;
783 		o = rb_entry(parent, struct check_orphan, rb);
784 		if (inum < o->inum)
785 			p = &(*p)->rb_left;
786 		else if (inum > o->inum)
787 			p = &(*p)->rb_right;
788 		else {
789 			kfree(orphan);
790 			return 0;
791 		}
792 	}
793 	rb_link_node(&orphan->rb, parent, p);
794 	rb_insert_color(&orphan->rb, root);
795 	return 0;
796 }
797 
798 static int dbg_find_check_orphan(struct rb_root *root, ino_t inum)
799 {
800 	struct check_orphan *o;
801 	struct rb_node *p;
802 
803 	p = root->rb_node;
804 	while (p) {
805 		o = rb_entry(p, struct check_orphan, rb);
806 		if (inum < o->inum)
807 			p = p->rb_left;
808 		else if (inum > o->inum)
809 			p = p->rb_right;
810 		else
811 			return 1;
812 	}
813 	return 0;
814 }
815 
816 static void dbg_free_check_tree(struct rb_root *root)
817 {
818 	struct rb_node *this = root->rb_node;
819 	struct check_orphan *o;
820 
821 	while (this) {
822 		if (this->rb_left) {
823 			this = this->rb_left;
824 			continue;
825 		} else if (this->rb_right) {
826 			this = this->rb_right;
827 			continue;
828 		}
829 		o = rb_entry(this, struct check_orphan, rb);
830 		this = rb_parent(this);
831 		if (this) {
832 			if (this->rb_left == &o->rb)
833 				this->rb_left = NULL;
834 			else
835 				this->rb_right = NULL;
836 		}
837 		kfree(o);
838 	}
839 }
840 
841 static int dbg_orphan_check(struct ubifs_info *c, struct ubifs_zbranch *zbr,
842 			    void *priv)
843 {
844 	struct check_info *ci = priv;
845 	ino_t inum;
846 	int err;
847 
848 	inum = key_inum(c, &zbr->key);
849 	if (inum != ci->last_ino) {
850 		/* Lowest node type is the inode node, so it comes first */
851 		if (key_type(c, &zbr->key) != UBIFS_INO_KEY)
852 			ubifs_err("found orphan node ino %lu, type %d",
853 				  (unsigned long)inum, key_type(c, &zbr->key));
854 		ci->last_ino = inum;
855 		ci->tot_inos += 1;
856 		err = ubifs_tnc_read_node(c, zbr, ci->node);
857 		if (err) {
858 			ubifs_err("node read failed, error %d", err);
859 			return err;
860 		}
861 		if (ci->node->nlink == 0)
862 			/* Must be recorded as an orphan */
863 			if (!dbg_find_check_orphan(&ci->root, inum) &&
864 			    !dbg_find_orphan(c, inum)) {
865 				ubifs_err("missing orphan, ino %lu",
866 					  (unsigned long)inum);
867 				ci->missing += 1;
868 			}
869 	}
870 	ci->leaf_cnt += 1;
871 	return 0;
872 }
873 
874 static int dbg_read_orphans(struct check_info *ci, struct ubifs_scan_leb *sleb)
875 {
876 	struct ubifs_scan_node *snod;
877 	struct ubifs_orph_node *orph;
878 	ino_t inum;
879 	int i, n, err;
880 
881 	list_for_each_entry(snod, &sleb->nodes, list) {
882 		cond_resched();
883 		if (snod->type != UBIFS_ORPH_NODE)
884 			continue;
885 		orph = snod->node;
886 		n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3;
887 		for (i = 0; i < n; i++) {
888 			inum = le64_to_cpu(orph->inos[i]);
889 			err = dbg_ins_check_orphan(&ci->root, inum);
890 			if (err)
891 				return err;
892 		}
893 	}
894 	return 0;
895 }
896 
897 static int dbg_scan_orphans(struct ubifs_info *c, struct check_info *ci)
898 {
899 	int lnum, err = 0;
900 	void *buf;
901 
902 	/* Check no-orphans flag and skip this if no orphans */
903 	if (c->no_orphs)
904 		return 0;
905 
906 	buf = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
907 	if (!buf) {
908 		ubifs_err("cannot allocate memory to check orphans");
909 		return 0;
910 	}
911 
912 	for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
913 		struct ubifs_scan_leb *sleb;
914 
915 		sleb = ubifs_scan(c, lnum, 0, buf, 0);
916 		if (IS_ERR(sleb)) {
917 			err = PTR_ERR(sleb);
918 			break;
919 		}
920 
921 		err = dbg_read_orphans(ci, sleb);
922 		ubifs_scan_destroy(sleb);
923 		if (err)
924 			break;
925 	}
926 
927 	vfree(buf);
928 	return err;
929 }
930 
931 static int dbg_check_orphans(struct ubifs_info *c)
932 {
933 	struct check_info ci;
934 	int err;
935 
936 	if (!dbg_is_chk_orph(c))
937 		return 0;
938 
939 	ci.last_ino = 0;
940 	ci.tot_inos = 0;
941 	ci.missing  = 0;
942 	ci.leaf_cnt = 0;
943 	ci.root = RB_ROOT;
944 	ci.node = kmalloc(UBIFS_MAX_INO_NODE_SZ, GFP_NOFS);
945 	if (!ci.node) {
946 		ubifs_err("out of memory");
947 		return -ENOMEM;
948 	}
949 
950 	err = dbg_scan_orphans(c, &ci);
951 	if (err)
952 		goto out;
953 
954 	err = dbg_walk_index(c, &dbg_orphan_check, NULL, &ci);
955 	if (err) {
956 		ubifs_err("cannot scan TNC, error %d", err);
957 		goto out;
958 	}
959 
960 	if (ci.missing) {
961 		ubifs_err("%lu missing orphan(s)", ci.missing);
962 		err = -EINVAL;
963 		goto out;
964 	}
965 
966 	dbg_cmt("last inode number is %lu", ci.last_ino);
967 	dbg_cmt("total number of inodes is %lu", ci.tot_inos);
968 	dbg_cmt("total number of leaf nodes is %llu", ci.leaf_cnt);
969 
970 out:
971 	dbg_free_check_tree(&ci.root);
972 	kfree(ci.node);
973 	return err;
974 }
975