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
19  * to be reused. Garbage collection will cause the number of dirty index nodes
33  * the UBIFS nodes GC deals with. Large nodes make GC waste more space. Indeed,
34  * if GC move data from LEB A to LEB B and nodes in LEB A are large, GC would
35  * have to waste large pieces of free space at the end of LEB B, because nodes
36  * from LEB A would not fit. And the worst situation is when all nodes are of
97  * data_nodes_cmp - compare 2 data nodes.
102  * This function compares data nodes @a and @b. Returns %1 if @a has greater
140  * nondata_nodes_cmp - compare 2 non-data nodes.
145  * This function compares nodes @a and @b. It makes sure that inode nodes go
146  * first and sorted by length in descending order. Directory entry nodes go
147  * after inode nodes and are sorted in ascending hash valuer order.
202  * sort_nodes - sort nodes for GC.
204  * @sleb: describes nodes to sort and contains the result on exit
205  * @nondata: contains non-data nodes on exit
209  * kills obsolete nodes and separates data and non-data nodes to the
210  * @sleb->nodes and @nondata lists correspondingly.
212  * Data nodes are then sorted in block number order - this is important for
213  * bulk-read; data nodes with lower inode number go before data nodes with
214  * higher inode number, and data nodes with lower block number go before data
215  * nodes with higher block number;
217  * Non-data nodes are sorted as follows.
218  *   o First go inode nodes - they are sorted in descending length order.
219  *   o Then go directory entry nodes - they are sorted in hash order, which
220  *     should supposedly optimize 'readdir()'. Direntry nodes with lower parent
221  *     inode number go before direntry nodes with higher parent inode number,
222  *     and direntry nodes with lower name hash values go before direntry nodes
236 	/* Separate data nodes and non-data nodes */  in sort_nodes()
237 	list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in sort_nodes()
279 	/* Sort data and non-data nodes */  in sort_nodes()
280 	list_sort(c, &sleb->nodes, &data_nodes_cmp);  in sort_nodes()
283 	err = dbg_check_data_nodes_order(c, &sleb->nodes);  in sort_nodes()
295  * @sleb: describes the LEB to move nodes from
322  * move_nodes - move nodes.
324  * @sleb: describes the LEB to move nodes from
326  * This function moves valid nodes from data LEB described by @sleb to the GC
351 	/* Write nodes to their new location. Use the first-fit strategy */  in move_nodes()
356 		/* Move data nodes */  in move_nodes()
357 		list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in move_nodes()
362 				 * Do not skip data nodes in order to optimize  in move_nodes()
378 		/* Move non-data nodes */  in move_nodes()
390 				 * nodes and direntry nodes are roughly of the  in move_nodes()
436 		if (list_empty(&sleb->nodes) && list_empty(&nondata))  in move_nodes()
451 	list_splice_tail(&nondata, &sleb->nodes);  in move_nodes()
459  * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
542 	ubifs_assert(c, !list_empty(&sleb->nodes));  in ubifs_garbage_collect_leb()
543 	snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);  in ubifs_garbage_collect_leb()
550 		list_for_each_entry(snod, &sleb->nodes, list) {  in ubifs_garbage_collect_leb()
626 	/* We may have moved at least some nodes so allow for races with TNC */  in ubifs_garbage_collect_leb()
646  * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
813 		 * and the LEB which was GC'ed contained only large nodes which  in ubifs_garbage_collect()
871  * correspond index nodes that are required for recovery.  In that case, the