15  * nodes) or not. For non-index LEBs, garbage collection finds a LEB which
16  * contains a lot of dirty space (obsolete nodes), and copies the non-obsolete
17  * nodes to the journal, at which point the garbage-collected LEB is free to be
18  * reused. For index LEBs, garbage collection marks the non-obsolete index nodes
20  * to be reused. Garbage collection will cause the number of dirty index nodes
34  * the UBIFS nodes GC deals with. Large nodes make GC waste more space. Indeed,
35  * if GC move data from LEB A to LEB B and nodes in LEB A are large, GC would
36  * have to waste large pieces of free space at the end of LEB B, because nodes
37  * from LEB A would not fit. And the worst situation is when all nodes are of
108  * data_nodes_cmp - compare 2 data nodes.
113  * This function compares data nodes @a and @b. Returns %1 if @a has greater
150  * nondata_nodes_cmp - compare 2 non-data nodes.
155  * This function compares nodes @a and @b. It makes sure that inode nodes go
156  * first and sorted by length in descending order. Directory entry nodes go
157  * after inode nodes and are sorted in ascending hash valuer order.
212  * sort_nodes - sort nodes for GC.
214  * @sleb: describes nodes to sort and contains the result on exit
215  * @nondata: contains non-data nodes on exit
219  * kills obsolete nodes and separates data and non-data nodes to the
220  * @sleb->nodes and @nondata lists correspondingly.
222  * Data nodes are then sorted in block number order - this is important for
223  * bulk-read; data nodes with lower inode number go before data nodes with
224  * higher inode number, and data nodes with lower block number go before data
225  * nodes with higher block number;
227  * Non-data nodes are sorted as follows.
228  *   o First go inode nodes - they are sorted in descending length order.
229  *   o Then go directory entry nodes - they are sorted in hash order, which
230  *     should supposedly optimize 'readdir()'. Direntry nodes with lower parent
231  *     inode number go before direntry nodes with higher parent inode number,
232  *     and direntry nodes with lower name hash values go before direntry nodes
246 	/* Separate data nodes and non-data nodes */  in sort_nodes()
247 	list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in sort_nodes()
288 	/* Sort data and non-data nodes */  in sort_nodes()
289 	list_sort(c, &sleb->nodes, &data_nodes_cmp);  in sort_nodes()
292 	err = dbg_check_data_nodes_order(c, &sleb->nodes);  in sort_nodes()
304  * @sleb: describes the LEB to move nodes from
331  * move_nodes - move nodes.
333  * @sleb: describes the LEB to move nodes from
335  * This function moves valid nodes from data LEB described by @sleb to the GC
360 	/* Write nodes to their new location. Use the first-fit strategy */  in move_nodes()
365 		/* Move data nodes */  in move_nodes()
366 		list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {  in move_nodes()
370 				 * Do not skip data nodes in order to optimize  in move_nodes()
380 		/* Move non-data nodes */  in move_nodes()
391 				 * nodes and direntry nodes are roughly of the  in move_nodes()
405 		if (list_empty(&sleb->nodes) && list_empty(&nondata))  in move_nodes()
420 	list_splice_tail(&nondata, &sleb->nodes);  in move_nodes()
428  * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
511 	ubifs_assert(!list_empty(&sleb->nodes));  in ubifs_garbage_collect_leb()
512 	snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);  in ubifs_garbage_collect_leb()
519 		list_for_each_entry(snod, &sleb->nodes, list) {  in ubifs_garbage_collect_leb()
595 	/* We may have moved at least some nodes so allow for races with TNC */  in ubifs_garbage_collect_leb()
615  * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
768 		 * and the LEB which was GC'ed contained only large nodes which  in ubifs_garbage_collect()
825  * correspond index nodes that are required for recovery.  In that case, the