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
107  * data_nodes_cmp - compare 2 data nodes.
112  * This function compares data nodes @a and @b. Returns %1 if @a has greater
149  * nondata_nodes_cmp - compare 2 non-data nodes.
154  * This function compares nodes @a and @b. It makes sure that inode nodes go
155  * first and sorted by length in descending order. Directory entry nodes go
156  * after inode nodes and are sorted in ascending hash valuer order.
211  * sort_nodes - sort nodes for GC.
213  * @sleb: describes nodes to sort and contains the result on exit
214  * @nondata: contains non-data nodes on exit
218  * kills obsolete nodes and separates data and non-data nodes to the
219  * @sleb->nodes and @nondata lists correspondingly.
221  * Data nodes are then sorted in block number order - this is important for
222  * bulk-read; data nodes with lower inode number go before data nodes with
223  * higher inode number, and data nodes with lower block number go before data
224  * nodes with higher block number;
226  * Non-data nodes are sorted as follows.
227  *   o First go inode nodes - they are sorted in descending length order.
228  *   o Then go directory entry nodes - they are sorted in hash order, which
229  *     should supposedly optimize 'readdir()'. Direntry nodes with lower parent
230  *     inode number go before direntry nodes with higher parent inode number,
231  *     and direntry nodes with lower name hash values go before direntry nodes
245 	/* Separate data nodes and non-data nodes */  in sort_nodes()
246 	list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in sort_nodes()
287 	/* Sort data and non-data nodes */  in sort_nodes()
288 	list_sort(c, &sleb->nodes, &data_nodes_cmp);  in sort_nodes()
291 	err = dbg_check_data_nodes_order(c, &sleb->nodes);  in sort_nodes()
303  * @sleb: describes the LEB to move nodes from
330  * move_nodes - move nodes.
332  * @sleb: describes the LEB to move nodes from
334  * This function moves valid nodes from data LEB described by @sleb to the GC
359 	/* Write nodes to their new location. Use the first-fit strategy */  in move_nodes()
364 		/* Move data nodes */  in move_nodes()
365 		list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in move_nodes()
369 				 * Do not skip data nodes in order to optimize  in move_nodes()
379 		/* Move non-data nodes */  in move_nodes()
390 				 * nodes and direntry nodes are roughly of the  in move_nodes()
404 		if (list_empty(&sleb->nodes) && list_empty(&nondata))  in move_nodes()
419 	list_splice_tail(&nondata, &sleb->nodes);  in move_nodes()
427  * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
510 	ubifs_assert(!list_empty(&sleb->nodes));  in ubifs_garbage_collect_leb()
511 	snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);  in ubifs_garbage_collect_leb()
518 		list_for_each_entry(snod, &sleb->nodes, list) {  in ubifs_garbage_collect_leb()
594 	/* We may have moved at least some nodes so allow for races with TNC */  in ubifs_garbage_collect_leb()
614  * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
767 		 * and the LEB which was GC'ed contained only large nodes which  in ubifs_garbage_collect()
824  * correspond index nodes that are required for recovery.  In that case, the