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
139  * nondata_nodes_cmp - compare 2 non-data nodes.
144  * This function compares nodes @a and @b. It makes sure that inode nodes go
145  * first and sorted by length in descending order. Directory entry nodes go
146  * after inode nodes and are sorted in ascending hash valuer order.
201  * sort_nodes - sort nodes for GC.
203  * @sleb: describes nodes to sort and contains the result on exit
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
213  * higher inode number, and data nodes with lower block number go before data
214  * nodes with higher block number;
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
219  *     should supposedly optimize 'readdir()'. Direntry nodes with lower parent
220  *     inode number go before direntry nodes with higher parent inode number,
221  *     and direntry nodes with lower name hash values go before direntry nodes
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()
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()
294  * @sleb: describes the LEB to move nodes from
321  * move_nodes - move nodes.
323  * @sleb: describes the LEB to move nodes from
325  * This function moves valid nodes from data LEB described by @sleb to the GC
350 	/* Write nodes to their new location. Use the first-fit strategy */  in move_nodes()
355 		/* Move data nodes */  in move_nodes()
356 		list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in move_nodes()
361 				 * Do not skip data nodes in order to optimize  in move_nodes()
377 		/* Move non-data nodes */  in move_nodes()
389 				 * nodes and direntry nodes are roughly of the  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()
458  * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
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()
549 		list_for_each_entry(snod, &sleb->nodes, list) {  in ubifs_garbage_collect_leb()
625 	/* We may have moved at least some nodes so allow for races with TNC */  in ubifs_garbage_collect_leb()
645  * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
798 		 * and the LEB which was GC'ed contained only large nodes which  in ubifs_garbage_collect()
855  * correspond index nodes that are required for recovery.  In that case, the