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
101  * data_nodes_cmp - compare 2 data nodes.
106  * This function compares data nodes @a and @b. Returns %1 if @a has greater
143  * nondata_nodes_cmp - compare 2 non-data nodes.
148  * This function compares nodes @a and @b. It makes sure that inode nodes go
149  * first and sorted by length in descending order. Directory entry nodes go
150  * after inode nodes and are sorted in ascending hash valuer order.
205  * sort_nodes - sort nodes for GC.
207  * @sleb: describes nodes to sort and contains the result on exit
208  * @nondata: contains non-data nodes on exit
212  * kills obsolete nodes and separates data and non-data nodes to the
213  * @sleb->nodes and @nondata lists correspondingly.
215  * Data nodes are then sorted in block number order - this is important for
216  * bulk-read; data nodes with lower inode number go before data nodes with
217  * higher inode number, and data nodes with lower block number go before data
218  * nodes with higher block number;
220  * Non-data nodes are sorted as follows.
221  *   o First go inode nodes - they are sorted in descending length order.
222  *   o Then go directory entry nodes - they are sorted in hash order, which
223  *     should supposedly optimize 'readdir()'. Direntry nodes with lower parent
224  *     inode number go before direntry nodes with higher parent inode number,
225  *     and direntry nodes with lower name hash values go before direntry nodes
239 	/* Separate data nodes and non-data nodes */  in sort_nodes()
240 	list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in sort_nodes()
282 	/* Sort data and non-data nodes */  in sort_nodes()
283 	list_sort(c, &sleb->nodes, &data_nodes_cmp);  in sort_nodes()
286 	err = dbg_check_data_nodes_order(c, &sleb->nodes);  in sort_nodes()
298  * @sleb: describes the LEB to move nodes from
325  * move_nodes - move nodes.
327  * @sleb: describes the LEB to move nodes from
329  * This function moves valid nodes from data LEB described by @sleb to the GC
354 	/* Write nodes to their new location. Use the first-fit strategy */  in move_nodes()
359 		/* Move data nodes */  in move_nodes()
360 		list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in move_nodes()
365 				 * Do not skip data nodes in order to optimize  in move_nodes()
381 		/* Move non-data nodes */  in move_nodes()
393 				 * nodes and direntry nodes are roughly of the  in move_nodes()
439 		if (list_empty(&sleb->nodes) && list_empty(&nondata))  in move_nodes()
454 	list_splice_tail(&nondata, &sleb->nodes);  in move_nodes()
462  * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
545 	ubifs_assert(c, !list_empty(&sleb->nodes));  in ubifs_garbage_collect_leb()
546 	snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);  in ubifs_garbage_collect_leb()
553 		list_for_each_entry(snod, &sleb->nodes, list) {  in ubifs_garbage_collect_leb()
629 	/* We may have moved at least some nodes so allow for races with TNC */  in ubifs_garbage_collect_leb()
649  * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
802 		 * and the LEB which was GC'ed contained only large nodes which  in ubifs_garbage_collect()
859  * correspond index nodes that are required for recovery.  In that case, the