1 // SPDX-License-Identifier: GPL-2.0-only
5  * Copyright (C) 2006-2008 Nokia Corporation.
14  * nodes) or not. For non-index LEBs, garbage collection finds a LEB which
15  * contains a lot of dirty space (obsolete nodes), and copies the non-obsolete
16  * nodes to the journal, at which point the garbage-collected LEB is free to be
17  * reused. For index LEBs, garbage collection marks the non-obsolete index nodes
18  * dirty in the TNC, and after the next commit, the garbage-collected LEB is
24  * LEBs which have less than @c->dead_wm bytes of free + dirty space are full
25  * and not worth garbage-collecting. The dead watermark is one min. I/O unit
58  * switch_gc_head - switch the garbage collection journal head.
59  * @c: UBIFS file-system description object
62  * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required,
63  * and other negative error code in case of failures.
67 	int err, gc_lnum = c->gc_lnum;  in switch_gc_head()
68 	struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;  in switch_gc_head()
70 	ubifs_assert(c, gc_lnum != -1);  in switch_gc_head()
72 	       wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum,  in switch_gc_head()
73 	       c->leb_size - wbuf->offs - wbuf->used);  in switch_gc_head()
80 	 * The GC write-buffer was synchronized, we may safely unmap  in switch_gc_head()
81 	 * 'c->gc_lnum'.  in switch_gc_head()
91 	c->gc_lnum = -1;  in switch_gc_head()
97  * data_nodes_cmp - compare 2 data nodes.
98  * @priv: UBIFS file-system description object
103  * inode or block number, and %-1 otherwise.
118 	ubifs_assert(c, key_type(c, &sa->key) == UBIFS_DATA_KEY);  in data_nodes_cmp()
119 	ubifs_assert(c, key_type(c, &sb->key) == UBIFS_DATA_KEY);  in data_nodes_cmp()
120 	ubifs_assert(c, sa->type == UBIFS_DATA_NODE);  in data_nodes_cmp()
121 	ubifs_assert(c, sb->type == UBIFS_DATA_NODE);  in data_nodes_cmp()
123 	inuma = key_inum(c, &sa->key);  in data_nodes_cmp()
124 	inumb = key_inum(c, &sb->key);  in data_nodes_cmp()
127 		unsigned int blka = key_block(c, &sa->key);  in data_nodes_cmp()
128 		unsigned int blkb = key_block(c, &sb->key);  in data_nodes_cmp()
131 			return -1;  in data_nodes_cmp()
133 		return -1;  in data_nodes_cmp()
139  * nondata_nodes_cmp - compare 2 non-data nodes.
140  * @priv: UBIFS file-system description object
162 	ubifs_assert(c, key_type(c, &sa->key) != UBIFS_DATA_KEY &&  in nondata_nodes_cmp()
163 		     key_type(c, &sb->key) != UBIFS_DATA_KEY);  in nondata_nodes_cmp()
164 	ubifs_assert(c, sa->type != UBIFS_DATA_NODE &&  in nondata_nodes_cmp()
165 		     sb->type != UBIFS_DATA_NODE);  in nondata_nodes_cmp()
168 	if (sa->type == UBIFS_INO_NODE) {  in nondata_nodes_cmp()
169 		if (sb->type == UBIFS_INO_NODE)  in nondata_nodes_cmp()
170 			return sb->len - sa->len;  in nondata_nodes_cmp()
171 		return -1;  in nondata_nodes_cmp()
173 	if (sb->type == UBIFS_INO_NODE)  in nondata_nodes_cmp()
176 	ubifs_assert(c, key_type(c, &sa->key) == UBIFS_DENT_KEY ||  in nondata_nodes_cmp()
177 		     key_type(c, &sa->key) == UBIFS_XENT_KEY);  in nondata_nodes_cmp()
178 	ubifs_assert(c, key_type(c, &sb->key) == UBIFS_DENT_KEY ||  in nondata_nodes_cmp()
179 		     key_type(c, &sb->key) == UBIFS_XENT_KEY);  in nondata_nodes_cmp()
180 	ubifs_assert(c, sa->type == UBIFS_DENT_NODE ||  in nondata_nodes_cmp()
181 		     sa->type == UBIFS_XENT_NODE);  in nondata_nodes_cmp()
182 	ubifs_assert(c, sb->type == UBIFS_DENT_NODE ||  in nondata_nodes_cmp()
183 		     sb->type == UBIFS_XENT_NODE);  in nondata_nodes_cmp()
185 	inuma = key_inum(c, &sa->key);  in nondata_nodes_cmp()
186 	inumb = key_inum(c, &sb->key);  in nondata_nodes_cmp()
189 		uint32_t hasha = key_hash(c, &sa->key);  in nondata_nodes_cmp()
190 		uint32_t hashb = key_hash(c, &sb->key);  in nondata_nodes_cmp()
193 			return -1;  in nondata_nodes_cmp()
195 		return -1;  in nondata_nodes_cmp()
201  * sort_nodes - sort nodes for GC.
202  * @c: UBIFS file-system description object
204  * @nondata: contains non-data nodes on exit
208  * kills obsolete nodes and separates data and non-data nodes to the
209  * @sleb->nodes and @nondata lists correspondingly.
211  * Data nodes are then sorted in block number order - this is important for
212  * bulk-read; data nodes with lower inode number go before data nodes with
216  * Non-data nodes are sorted as follows.
217  *   o First go inode nodes - they are sorted in descending length order.
218  *   o Then go directory entry nodes - they are sorted in hash order, which
224  * This function returns zero in case of success and a negative error code in
235 	/* Separate data nodes and non-data nodes */  in sort_nodes()
236 	list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in sort_nodes()
237 		ubifs_assert(c, snod->type == UBIFS_INO_NODE  ||  in sort_nodes()
238 			     snod->type == UBIFS_DATA_NODE ||  in sort_nodes()
239 			     snod->type == UBIFS_DENT_NODE ||  in sort_nodes()
240 			     snod->type == UBIFS_XENT_NODE ||  in sort_nodes()
241 			     snod->type == UBIFS_TRUN_NODE ||  in sort_nodes()
242 			     snod->type == UBIFS_AUTH_NODE);  in sort_nodes()
244 		if (snod->type != UBIFS_INO_NODE  &&  in sort_nodes()
245 		    snod->type != UBIFS_DATA_NODE &&  in sort_nodes()
246 		    snod->type != UBIFS_DENT_NODE &&  in sort_nodes()
247 		    snod->type != UBIFS_XENT_NODE) {  in sort_nodes()
249 			list_del(&snod->list);  in sort_nodes()
254 		ubifs_assert(c, key_type(c, &snod->key) == UBIFS_DATA_KEY ||  in sort_nodes()
255 			     key_type(c, &snod->key) == UBIFS_INO_KEY  ||  in sort_nodes()
256 			     key_type(c, &snod->key) == UBIFS_DENT_KEY ||  in sort_nodes()
257 			     key_type(c, &snod->key) == UBIFS_XENT_KEY);  in sort_nodes()
259 		err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,  in sort_nodes()
260 					 snod->offs, 0);  in sort_nodes()
266 			list_del(&snod->list);  in sort_nodes()
271 		if (snod->len < *min)  in sort_nodes()
272 			*min = snod->len;  in sort_nodes()
274 		if (key_type(c, &snod->key) != UBIFS_DATA_KEY)  in sort_nodes()
275 			list_move_tail(&snod->list, nondata);  in sort_nodes()
278 	/* Sort data and non-data nodes */  in sort_nodes()
279 	list_sort(c, &sleb->nodes, &data_nodes_cmp);  in sort_nodes()
282 	err = dbg_check_data_nodes_order(c, &sleb->nodes);  in sort_nodes()
292  * move_node - move a node.
293  * @c: UBIFS file-system description object
296  * @wbuf: write-buffer to move node to
299  * destroys @snod. Returns zero in case of success and a negative error code in
305 	int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used;  in move_node()
308 	err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len);  in move_node()
312 	err = ubifs_tnc_replace(c, &snod->key, sleb->lnum,  in move_node()
313 				snod->offs, new_lnum, new_offs,  in move_node()
314 				snod->len);  in move_node()
315 	list_del(&snod->list);  in move_node()
321  * move_nodes - move nodes.
322  * @c: UBIFS file-system description object
326  * journal head. This function returns zero in case of success, %-EAGAIN if
327  * commit is required, and other negative error codes in case of other
334 	struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;  in move_nodes()
336 	if (wbuf->lnum == -1) {  in move_nodes()
350 	/* Write nodes to their new location. Use the first-fit strategy */  in move_nodes()
356 		list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in move_nodes()
357 			avail = c->leb_size - wbuf->offs - wbuf->used -  in move_nodes()
359 			if  (snod->len > avail)  in move_nodes()
362 				 * bulk-read.  in move_nodes()
366 			err = ubifs_shash_update(c, c->jheads[GCHD].log_hash,  in move_nodes()
367 						 snod->node, snod->len);  in move_nodes()
377 		/* Move non-data nodes */  in move_nodes()
379 			avail = c->leb_size - wbuf->offs - wbuf->used -  in move_nodes()
384 			if  (snod->len > avail) {  in move_nodes()
388 				 * head. IOW, we assume that data-less inode  in move_nodes()
392 				if (key_type(c, &snod->key) == UBIFS_DENT_KEY ||  in move_nodes()
393 				    snod->len == UBIFS_INO_NODE_SZ)  in move_nodes()
398 			err = ubifs_shash_update(c, c->jheads[GCHD].log_hash,  in move_nodes()
399 						 snod->node, snod->len);  in move_nodes()
414 				err = -ENOMEM;  in move_nodes()
419 						c->jheads[GCHD].log_hash);  in move_nodes()
432 			ubifs_add_dirt(c, wbuf->lnum, ubifs_auth_node_sz(c));  in move_nodes()
435 		if (list_empty(&sleb->nodes) && list_empty(&nondata))  in move_nodes()
450 	list_splice_tail(&nondata, &sleb->nodes);  in move_nodes()
455  * gc_sync_wbufs - sync write-buffers for GC.
456  * @c: UBIFS file-system description object
459  * be in a write-buffer instead. That is, a node could be written to a
460  * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is
461  * erased before the write-buffer is sync'd and then there is an unclean
463  * write-buffers.
465  * This function returns %0 on success or a negative error code on failure.
471 	for (i = 0; i < c->jhead_cnt; i++) {  in gc_sync_wbufs()
474 		err = ubifs_wbuf_sync(&c->jheads[i].wbuf);  in gc_sync_wbufs()
482  * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock.
483  * @c: UBIFS file-system description object
486  * This function garbage-collects an LEB and returns one of the @LEB_FREED,
487  * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is
488  * required, and other negative error codes in case of failures.
494 	struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;  in ubifs_garbage_collect_leb()
495 	int err = 0, lnum = lp->lnum;  in ubifs_garbage_collect_leb()
497 	ubifs_assert(c, c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 ||  in ubifs_garbage_collect_leb()
498 		     c->need_recovery);  in ubifs_garbage_collect_leb()
499 	ubifs_assert(c, c->gc_lnum != lnum);  in ubifs_garbage_collect_leb()
500 	ubifs_assert(c, wbuf->lnum != lnum);  in ubifs_garbage_collect_leb()
502 	if (lp->free + lp->dirty == c->leb_size) {  in ubifs_garbage_collect_leb()
503 		/* Special case - a free LEB  */  in ubifs_garbage_collect_leb()
504 		dbg_gc("LEB %d is free, return it", lp->lnum);  in ubifs_garbage_collect_leb()
505 		ubifs_assert(c, !(lp->flags & LPROPS_INDEX));  in ubifs_garbage_collect_leb()
507 		if (lp->free != c->leb_size) {  in ubifs_garbage_collect_leb()
511 			 * which obsoletes something in 'lp->lnum'.  in ubifs_garbage_collect_leb()
516 			err = ubifs_change_one_lp(c, lp->lnum, c->leb_size,  in ubifs_garbage_collect_leb()
521 		err = ubifs_leb_unmap(c, lp->lnum);  in ubifs_garbage_collect_leb()
525 		if (c->gc_lnum == -1) {  in ubifs_garbage_collect_leb()
526 			c->gc_lnum = lnum;  in ubifs_garbage_collect_leb()
535 	 * (c->leb_size - lp->free).  in ubifs_garbage_collect_leb()
537 	sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0);  in ubifs_garbage_collect_leb()
541 	ubifs_assert(c, !list_empty(&sleb->nodes));  in ubifs_garbage_collect_leb()
542 	snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);  in ubifs_garbage_collect_leb()
544 	if (snod->type == UBIFS_IDX_NODE) {  in ubifs_garbage_collect_leb()
548 		       lnum, lp->free, lp->dirty);  in ubifs_garbage_collect_leb()
549 		list_for_each_entry(snod, &sleb->nodes, list) {  in ubifs_garbage_collect_leb()
550 			struct ubifs_idx_node *idx = snod->node;  in ubifs_garbage_collect_leb()
551 			int level = le16_to_cpu(idx->level);  in ubifs_garbage_collect_leb()
553 			ubifs_assert(c, snod->type == UBIFS_IDX_NODE);  in ubifs_garbage_collect_leb()
554 			key_read(c, ubifs_idx_key(c, idx), &snod->key);  in ubifs_garbage_collect_leb()
555 			err = ubifs_dirty_idx_node(c, &snod->key, level, lnum,  in ubifs_garbage_collect_leb()
556 						   snod->offs);  in ubifs_garbage_collect_leb()
563 			err = -ENOMEM;  in ubifs_garbage_collect_leb()
567 		idx_gc->lnum = lnum;  in ubifs_garbage_collect_leb()
568 		idx_gc->unmap = 0;  in ubifs_garbage_collect_leb()
569 		list_add(&idx_gc->list, &c->idx_gc);  in ubifs_garbage_collect_leb()
577 		err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0,  in ubifs_garbage_collect_leb()
584 		       lnum, lp->free, lp->dirty);  in ubifs_garbage_collect_leb()
594 		err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0);  in ubifs_garbage_collect_leb()
599 		c->gced_lnum = lnum;  in ubifs_garbage_collect_leb()
601 		c->gc_seq += 1;  in ubifs_garbage_collect_leb()
604 		if (c->gc_lnum == -1) {  in ubifs_garbage_collect_leb()
605 			c->gc_lnum = lnum;  in ubifs_garbage_collect_leb()
626 	c->gced_lnum = lnum;  in ubifs_garbage_collect_leb()
628 	c->gc_seq += 1;  in ubifs_garbage_collect_leb()
634  * ubifs_garbage_collect - UBIFS garbage collector.
635  * @c: UBIFS file-system description object
638  * This function does out-of-place garbage collection. The return codes are:
640  *   o %-EAGAIN if the caller has to run commit;
641  *   o %-ENOSPC if GC failed to make any progress;
642  *   o other negative error codes in case of other errors.
647  * caller might be holding the commit lock, so %-EAGAIN is returned instead;
648  * And this error code means that the caller has to run commit, and re-run GC
651  * There are many reasons why this function may return %-EAGAIN:
653  *   @c->gc_lnum;
659  * Note, if the file-system is close to be full, this function may return
660  * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of
667  * %-EAGAIN may happen, but in some extreme/misconfiguration cases.
671 	int i, err, ret, min_space = c->dead_wm;  in ubifs_garbage_collect()
673 	struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;  in ubifs_garbage_collect()
676 	ubifs_assert(c, !c->ro_media && !c->ro_mount);  in ubifs_garbage_collect()
679 		return -EAGAIN;  in ubifs_garbage_collect()
681 	mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);  in ubifs_garbage_collect()
683 	if (c->ro_error) {  in ubifs_garbage_collect()
684 		ret = -EROFS;  in ubifs_garbage_collect()
688 	/* We expect the write-buffer to be empty on entry */  in ubifs_garbage_collect()
689 	ubifs_assert(c, !wbuf->used);  in ubifs_garbage_collect()
698 			ret = -EAGAIN;  in ubifs_garbage_collect()
702 		if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) {  in ubifs_garbage_collect()
707 			dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN");  in ubifs_garbage_collect()
709 			ret = -EAGAIN;  in ubifs_garbage_collect()
718 			dbg_gc("hard limit, -ENOSPC");  in ubifs_garbage_collect()
719 			ret = -ENOSPC;  in ubifs_garbage_collect()
732 			if (ret == -ENOSPC)  in ubifs_garbage_collect()
741 		space_before = c->leb_size - wbuf->offs - wbuf->used;  in ubifs_garbage_collect()
742 		if (wbuf->lnum == -1)  in ubifs_garbage_collect()
747 			if (ret == -EAGAIN) {  in ubifs_garbage_collect()
752 				 * caller instead of the original '-EAGAIN'.  in ubifs_garbage_collect()
781 		space_after = c->leb_size - wbuf->offs - wbuf->used;  in ubifs_garbage_collect()
783 		       space_after - space_before);  in ubifs_garbage_collect()
788 			if (min_space < c->dead_wm)  in ubifs_garbage_collect()
789 				min_space = c->dead_wm;  in ubifs_garbage_collect()
817 		if (min_space > c->dark_wm)  in ubifs_garbage_collect()
818 			min_space = c->dark_wm;  in ubifs_garbage_collect()
822 	if (ret == -ENOSPC && !list_empty(&c->idx_gc)) {  in ubifs_garbage_collect()
823 		dbg_gc("no space, some index LEBs GC'ed, -EAGAIN");  in ubifs_garbage_collect()
825 		ret = -EAGAIN;  in ubifs_garbage_collect()
830 		err = ubifs_leb_unmap(c, c->gc_lnum);  in ubifs_garbage_collect()
836 	mutex_unlock(&wbuf->io_mutex);  in ubifs_garbage_collect()
841 	ubifs_assert(c, ret != -ENOSPC && ret != -EAGAIN);  in ubifs_garbage_collect()
844 	mutex_unlock(&wbuf->io_mutex);  in ubifs_garbage_collect()
850  * ubifs_gc_start_commit - garbage collection at start of commit.
851  * @c: UBIFS file-system description object
858  * This function returns %0 upon success and a negative error code upon failure.
869 	 * Unmap (non-index) freeable LEBs. Note that recovery requires that all  in ubifs_gc_start_commit()
876 		ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));  in ubifs_gc_start_commit()
877 		ubifs_assert(c, !(lp->flags & LPROPS_INDEX));  in ubifs_gc_start_commit()
878 		err = ubifs_leb_unmap(c, lp->lnum);  in ubifs_gc_start_commit()
881 		lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0);  in ubifs_gc_start_commit()
886 		ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));  in ubifs_gc_start_commit()
887 		ubifs_assert(c, !(lp->flags & LPROPS_INDEX));  in ubifs_gc_start_commit()
891 	list_for_each_entry(idx_gc, &c->idx_gc, list)  in ubifs_gc_start_commit()
892 		idx_gc->unmap = 1;  in ubifs_gc_start_commit()
905 			err = -ENOMEM;  in ubifs_gc_start_commit()
908 		ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));  in ubifs_gc_start_commit()
909 		ubifs_assert(c, lp->flags & LPROPS_INDEX);  in ubifs_gc_start_commit()
911 		flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX;  in ubifs_gc_start_commit()
912 		lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1);  in ubifs_gc_start_commit()
918 		ubifs_assert(c, lp->flags & LPROPS_TAKEN);  in ubifs_gc_start_commit()
919 		ubifs_assert(c, !(lp->flags & LPROPS_INDEX));  in ubifs_gc_start_commit()
920 		idx_gc->lnum = lp->lnum;  in ubifs_gc_start_commit()
921 		idx_gc->unmap = 1;  in ubifs_gc_start_commit()
922 		list_add(&idx_gc->list, &c->idx_gc);  in ubifs_gc_start_commit()
930  * ubifs_gc_end_commit - garbage collection at end of commit.
931  * @c: UBIFS file-system description object
933  * This function completes out-of-place garbage collection of index LEBs.
941 	wbuf = &c->jheads[GCHD].wbuf;  in ubifs_gc_end_commit()
942 	mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);  in ubifs_gc_end_commit()
943 	list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list)  in ubifs_gc_end_commit()
944 		if (idx_gc->unmap) {  in ubifs_gc_end_commit()
945 			dbg_gc("LEB %d", idx_gc->lnum);  in ubifs_gc_end_commit()
946 			err = ubifs_leb_unmap(c, idx_gc->lnum);  in ubifs_gc_end_commit()
949 			err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC,  in ubifs_gc_end_commit()
950 					  LPROPS_NC, 0, LPROPS_TAKEN, -1);  in ubifs_gc_end_commit()
953 			list_del(&idx_gc->list);  in ubifs_gc_end_commit()
957 	mutex_unlock(&wbuf->io_mutex);  in ubifs_gc_end_commit()
962  * ubifs_destroy_idx_gc - destroy idx_gc list.
963  * @c: UBIFS file-system description object
965  * This function destroys the @c->idx_gc list. It is called when unmounting
966  * so locks are not needed. Returns zero in case of success and a negative
971 	while (!list_empty(&c->idx_gc)) {  in ubifs_destroy_idx_gc()
974 		idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb,  in ubifs_destroy_idx_gc()
976 		c->idx_gc_cnt -= 1;  in ubifs_destroy_idx_gc()
977 		list_del(&idx_gc->list);  in ubifs_destroy_idx_gc()
983  * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list.
984  * @c: UBIFS file-system description object
993 	if (list_empty(&c->idx_gc))  in ubifs_get_idx_gc_leb()
994 		return -ENOSPC;  in ubifs_get_idx_gc_leb()
995 	idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list);  in ubifs_get_idx_gc_leb()
996 	lnum = idx_gc->lnum;  in ubifs_get_idx_gc_leb()
997 	/* c->idx_gc_cnt is updated by the caller when lprops are updated */  in ubifs_get_idx_gc_leb()
998 	list_del(&idx_gc->list);  in ubifs_get_idx_gc_leb()