196 static void remove_backref_node(struct backref_cache *cache,
207 static void backref_cache_init(struct backref_cache *cache)  in backref_cache_init()  argument
210 	cache->rb_root = RB_ROOT;  in backref_cache_init()
212 		INIT_LIST_HEAD(&cache->pending[i]);  in backref_cache_init()
213 	INIT_LIST_HEAD(&cache->changed);  in backref_cache_init()
214 	INIT_LIST_HEAD(&cache->detached);  in backref_cache_init()
215 	INIT_LIST_HEAD(&cache->leaves);  in backref_cache_init()
218 static void backref_cache_cleanup(struct backref_cache *cache)  in backref_cache_cleanup()  argument
223 	while (!list_empty(&cache->detached)) {  in backref_cache_cleanup()
224 		node = list_entry(cache->detached.next,  in backref_cache_cleanup()
226 		remove_backref_node(cache, node);  in backref_cache_cleanup()
229 	while (!list_empty(&cache->leaves)) {  in backref_cache_cleanup()
230 		node = list_entry(cache->leaves.next,  in backref_cache_cleanup()
232 		remove_backref_node(cache, node);  in backref_cache_cleanup()
235 	cache->last_trans = 0;  in backref_cache_cleanup()
238 		BUG_ON(!list_empty(&cache->pending[i]));  in backref_cache_cleanup()
239 	BUG_ON(!list_empty(&cache->changed));  in backref_cache_cleanup()
240 	BUG_ON(!list_empty(&cache->detached));  in backref_cache_cleanup()
241 	BUG_ON(!RB_EMPTY_ROOT(&cache->rb_root));  in backref_cache_cleanup()
242 	BUG_ON(cache->nr_nodes);  in backref_cache_cleanup()
243 	BUG_ON(cache->nr_edges);  in backref_cache_cleanup()
246 static struct backref_node *alloc_backref_node(struct backref_cache *cache)  in alloc_backref_node()  argument
256 		cache->nr_nodes++;  in alloc_backref_node()
261 static void free_backref_node(struct backref_cache *cache,  in free_backref_node()  argument
265 		cache->nr_nodes--;  in free_backref_node()
270 static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)  in alloc_backref_edge()  argument
276 		cache->nr_edges++;  in alloc_backref_edge()
280 static void free_backref_edge(struct backref_cache *cache,  in free_backref_edge()  argument
284 		cache->nr_edges--;  in free_backref_edge()
424 static void remove_backref_node(struct backref_cache *cache,  in remove_backref_node()  argument
440 		free_backref_edge(cache, edge);  in remove_backref_node()
444 			drop_backref_node(cache, node);  in remove_backref_node()
454 			list_add_tail(&upper->lower, &cache->leaves);  in remove_backref_node()
459 	drop_backref_node(cache, node);  in remove_backref_node()
462 static void update_backref_node(struct backref_cache *cache,  in update_backref_node()  argument
466 	rb_erase(&node->rb_node, &cache->rb_root);  in update_backref_node()
468 	rb_node = tree_insert(&cache->rb_root, node->bytenr, &node->rb_node);  in update_backref_node()
477 				struct backref_cache *cache)  in update_backref_cache()  argument
482 	if (cache->last_trans == 0) {  in update_backref_cache()
483 		cache->last_trans = trans->transid;  in update_backref_cache()
487 	if (cache->last_trans == trans->transid)  in update_backref_cache()
495 	while (!list_empty(&cache->detached)) {  in update_backref_cache()
496 		node = list_entry(cache->detached.next,  in update_backref_cache()
498 		remove_backref_node(cache, node);  in update_backref_cache()
501 	while (!list_empty(&cache->changed)) {  in update_backref_cache()
502 		node = list_entry(cache->changed.next,  in update_backref_cache()
506 		update_backref_node(cache, node, node->new_bytenr);  in update_backref_cache()
514 		list_for_each_entry(node, &cache->pending[level], list) {  in update_backref_cache()
518 			update_backref_node(cache, node, node->new_bytenr);  in update_backref_cache()
522 	cache->last_trans = 0;  in update_backref_cache()
683 	struct backref_cache *cache = &rc->backref_cache;  local
714 	node = alloc_backref_node(cache);
849 			edge = alloc_backref_edge(cache);
854 			rb_node = tree_search(&cache->rb_root, key.offset);
856 				upper = alloc_backref_node(cache);
858 					free_backref_edge(cache, edge);
940 			edge = alloc_backref_edge(cache);
947 			rb_node = tree_search(&cache->rb_root, eb->start);
949 				upper = alloc_backref_node(cache);
951 					free_backref_edge(cache, edge);
1036 		rb_node = tree_insert(&cache->rb_root, node->bytenr,
1040 		list_add_tail(&node->lower, &cache->leaves);
1053 			free_backref_edge(cache, edge);
1085 			rb_node = tree_insert(&cache->rb_root, upper->bytenr,
1119 			free_backref_edge(cache, edge);
1126 			list_add(&upper->list, &cache->detached);
1129 			rb_erase(&upper->rb_node, &cache->rb_root);
1130 			free_backref_node(cache, upper);
1149 			free_backref_edge(cache, edge);
1173 			free_backref_node(cache, lower);
1192 	struct backref_cache *cache = &rc->backref_cache;  local
1199 	if (cache->last_trans > 0)
1200 		update_backref_cache(trans, cache);
1202 	rb_node = tree_search(&cache->rb_root, src->commit_root->start);
1212 		rb_node = tree_search(&cache->rb_root,
1224 	new_node = alloc_backref_node(cache);
1236 			new_edge = alloc_backref_edge(cache);
1246 		list_add_tail(&new_node->lower, &cache->leaves);
1249 	rb_node = tree_insert(&cache->rb_root, new_node->bytenr,
1266 		free_backref_edge(cache, new_edge);
1268 	free_backref_node(cache, new_node);
2788 	struct backref_cache *cache = &rc->backref_cache;  local
2794 		while (!list_empty(&cache->pending[level])) {
2795 			node = list_entry(cache->pending[level].next,
2806 		list_splice_init(&list, &cache->pending[level]);