34 static bool bpf_lru_node_is_ref(const struct bpf_lru_node *node)  in bpf_lru_node_is_ref()  argument
36 	return READ_ONCE(node->ref);  in bpf_lru_node_is_ref()
39 static void bpf_lru_node_clear_ref(struct bpf_lru_node *node)  in bpf_lru_node_clear_ref()  argument
41 	WRITE_ONCE(node->ref, 0);  in bpf_lru_node_clear_ref()
59 					struct bpf_lru_node *node,  in __bpf_lru_node_move_to_free()  argument
63 	if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))  in __bpf_lru_node_move_to_free()
66 	/* If the removing node is the next_inactive_rotation candidate,  in __bpf_lru_node_move_to_free()
69 	if (&node->list == l->next_inactive_rotation)  in __bpf_lru_node_move_to_free()
72 	bpf_lru_list_count_dec(l, node->type);  in __bpf_lru_node_move_to_free()
74 	node->type = tgt_free_type;  in __bpf_lru_node_move_to_free()
75 	list_move(&node->list, free_list);  in __bpf_lru_node_move_to_free()
80 				   struct bpf_lru_node *node,  in __bpf_lru_node_move_in()  argument
83 	if (WARN_ON_ONCE(!IS_LOCAL_LIST_TYPE(node->type)) ||  in __bpf_lru_node_move_in()
88 	node->type = tgt_type;  in __bpf_lru_node_move_in()
89 	bpf_lru_node_clear_ref(node);  in __bpf_lru_node_move_in()
90 	list_move(&node->list, &l->lists[tgt_type]);  in __bpf_lru_node_move_in()
98 				struct bpf_lru_node *node,  in __bpf_lru_node_move()  argument
101 	if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)) ||  in __bpf_lru_node_move()
105 	if (node->type != tgt_type) {  in __bpf_lru_node_move()
106 		bpf_lru_list_count_dec(l, node->type);  in __bpf_lru_node_move()
108 		node->type = tgt_type;  in __bpf_lru_node_move()
110 	bpf_lru_node_clear_ref(node);  in __bpf_lru_node_move()
112 	/* If the moving node is the next_inactive_rotation candidate,  in __bpf_lru_node_move()
115 	if (&node->list == l->next_inactive_rotation)  in __bpf_lru_node_move()
118 	list_move(&node->list, &l->lists[tgt_type]);  in __bpf_lru_node_move()
129  * 2. If the node has the ref bit set, it will be rotated
131  *    Give this node one more chance to survive in the active list.
140 	struct bpf_lru_node *node, *tmp_node, *first_node;  in __bpf_lru_list_rotate_active()  local
144 	list_for_each_entry_safe_reverse(node, tmp_node, active, list) {  in __bpf_lru_list_rotate_active()
145 		if (bpf_lru_node_is_ref(node))  in __bpf_lru_list_rotate_active()
146 			__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);  in __bpf_lru_list_rotate_active()
148 			__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);  in __bpf_lru_list_rotate_active()
150 		if (++i == lru->nr_scans || node == first_node)  in __bpf_lru_list_rotate_active()
156  * 1. If the node has ref bit set, it will be moved to the head
158  * 2. If the node does not have ref bit set, it will leave it
168 	struct bpf_lru_node *node;  in __bpf_lru_list_rotate_inactive()  local
185 		node = list_entry(cur, struct bpf_lru_node, list);  in __bpf_lru_list_rotate_inactive()
187 		if (bpf_lru_node_is_ref(node))  in __bpf_lru_list_rotate_inactive()
188 			__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);  in __bpf_lru_list_rotate_inactive()
210 	struct bpf_lru_node *node, *tmp_node;  in __bpf_lru_list_shrink_inactive()  local
214 	list_for_each_entry_safe_reverse(node, tmp_node, inactive, list) {  in __bpf_lru_list_shrink_inactive()
215 		if (bpf_lru_node_is_ref(node)) {  in __bpf_lru_list_shrink_inactive()
216 			__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);  in __bpf_lru_list_shrink_inactive()
217 		} else if (lru->del_from_htab(lru->del_arg, node)) {  in __bpf_lru_list_shrink_inactive()
218 			__bpf_lru_node_move_to_free(l, node, free_list,  in __bpf_lru_list_shrink_inactive()
246  * If it cannot get a free node after calling
248  * one node from either inactive or active list without
259 	struct bpf_lru_node *node, *tmp_node;  in __bpf_lru_list_shrink()  local
274 	list_for_each_entry_safe_reverse(node, tmp_node, force_shrink_list,  in __bpf_lru_list_shrink()
276 		if (lru->del_from_htab(lru->del_arg, node)) {  in __bpf_lru_list_shrink()
277 			__bpf_lru_node_move_to_free(l, node, free_list,  in __bpf_lru_list_shrink()
290 	struct bpf_lru_node *node, *tmp_node;  in __local_list_flush()  local
292 	list_for_each_entry_safe_reverse(node, tmp_node,  in __local_list_flush()
294 		if (bpf_lru_node_is_ref(node))  in __local_list_flush()
295 			__bpf_lru_node_move_in(l, node, BPF_LRU_LIST_T_ACTIVE);  in __local_list_flush()
297 			__bpf_lru_node_move_in(l, node,  in __local_list_flush()
303 				   struct bpf_lru_node *node)  in bpf_lru_list_push_free()  argument
307 	if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))  in bpf_lru_list_push_free()
311 	__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);  in bpf_lru_list_push_free()
319 	struct bpf_lru_node *node, *tmp_node;  in bpf_lru_list_pop_free_to_local()  local
328 	list_for_each_entry_safe(node, tmp_node, &l->lists[BPF_LRU_LIST_T_FREE],  in bpf_lru_list_pop_free_to_local()
330 		__bpf_lru_node_move_to_free(l, node, local_free_list(loc_l),  in bpf_lru_list_pop_free_to_local()
347 				     struct bpf_lru_node *node,  in __local_list_add_pending()  argument
350 	*(u32 *)((void *)node + lru->hash_offset) = hash;  in __local_list_add_pending()
351 	node->cpu = cpu;  in __local_list_add_pending()
352 	node->type = BPF_LRU_LOCAL_LIST_T_PENDING;  in __local_list_add_pending()
353 	bpf_lru_node_clear_ref(node);  in __local_list_add_pending()
354 	list_add(&node->list, local_pending_list(loc_l));  in __local_list_add_pending()
360 	struct bpf_lru_node *node;  in __local_list_pop_free()  local
362 	node = list_first_entry_or_null(local_free_list(loc_l),  in __local_list_pop_free()
365 	if (node)  in __local_list_pop_free()
366 		list_del(&node->list);  in __local_list_pop_free()
368 	return node;  in __local_list_pop_free()
374 	struct bpf_lru_node *node;  in __local_list_pop_pending()  local
379 	list_for_each_entry_reverse(node, local_pending_list(loc_l),  in __local_list_pop_pending()
381 		if ((!bpf_lru_node_is_ref(node) || force) &&  in __local_list_pop_pending()
382 		    lru->del_from_htab(lru->del_arg, node)) {  in __local_list_pop_pending()
383 			list_del(&node->list);  in __local_list_pop_pending()
384 			return node;  in __local_list_pop_pending()
400 	struct bpf_lru_node *node = NULL;  in bpf_percpu_lru_pop_free()  local
417 		node = list_first_entry(free_list, struct bpf_lru_node, list);  in bpf_percpu_lru_pop_free()
418 		*(u32 *)((void *)node + lru->hash_offset) = hash;  in bpf_percpu_lru_pop_free()
419 		bpf_lru_node_clear_ref(node);  in bpf_percpu_lru_pop_free()
420 		__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);  in bpf_percpu_lru_pop_free()
425 	return node;  in bpf_percpu_lru_pop_free()
433 	struct bpf_lru_node *node;  in bpf_common_lru_pop_free()  local
442 	node = __local_list_pop_free(loc_l);  in bpf_common_lru_pop_free()
443 	if (!node) {  in bpf_common_lru_pop_free()
445 		node = __local_list_pop_free(loc_l);  in bpf_common_lru_pop_free()
448 	if (node)  in bpf_common_lru_pop_free()
449 		__local_list_add_pending(lru, loc_l, cpu, node, hash);  in bpf_common_lru_pop_free()
453 	if (node)  in bpf_common_lru_pop_free()
454 		return node;  in bpf_common_lru_pop_free()
471 		node = __local_list_pop_free(steal_loc_l);  in bpf_common_lru_pop_free()
472 		if (!node)  in bpf_common_lru_pop_free()
473 			node = __local_list_pop_pending(lru, steal_loc_l);  in bpf_common_lru_pop_free()
478 	} while (!node && steal != first_steal);  in bpf_common_lru_pop_free()
482 	if (node) {  in bpf_common_lru_pop_free()
484 		__local_list_add_pending(lru, loc_l, cpu, node, hash);  in bpf_common_lru_pop_free()
488 	return node;  in bpf_common_lru_pop_free()
500 				     struct bpf_lru_node *node)  in bpf_common_lru_push_free()  argument
502 	u8 node_type = READ_ONCE(node->type);  in bpf_common_lru_push_free()
512 		loc_l = per_cpu_ptr(lru->common_lru.local_list, node->cpu);  in bpf_common_lru_push_free()
516 		if (unlikely(node->type != BPF_LRU_LOCAL_LIST_T_PENDING)) {  in bpf_common_lru_push_free()
521 		node->type = BPF_LRU_LOCAL_LIST_T_FREE;  in bpf_common_lru_push_free()
522 		bpf_lru_node_clear_ref(node);  in bpf_common_lru_push_free()
523 		list_move(&node->list, local_free_list(loc_l));  in bpf_common_lru_push_free()
530 	bpf_lru_list_push_free(&lru->common_lru.lru_list, node);  in bpf_common_lru_push_free()
534 				     struct bpf_lru_node *node)  in bpf_percpu_lru_push_free()  argument
539 	l = per_cpu_ptr(lru->percpu_lru, node->cpu);  in bpf_percpu_lru_push_free()
543 	__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);  in bpf_percpu_lru_push_free()
548 void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node)  in bpf_lru_push_free()  argument
551 		bpf_percpu_lru_push_free(lru, node);  in bpf_lru_push_free()
553 		bpf_common_lru_push_free(lru, node);  in bpf_lru_push_free()
564 		struct bpf_lru_node *node;  in bpf_common_lru_populate()  local
566 		node = (struct bpf_lru_node *)(buf + node_offset);  in bpf_common_lru_populate()
567 		node->type = BPF_LRU_LIST_T_FREE;  in bpf_common_lru_populate()
568 		bpf_lru_node_clear_ref(node);  in bpf_common_lru_populate()
569 		list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);  in bpf_common_lru_populate()
590 		struct bpf_lru_node *node;  in bpf_percpu_lru_populate()  local
594 		node = (struct bpf_lru_node *)(buf + node_offset);  in bpf_percpu_lru_populate()
595 		node->cpu = cpu;  in bpf_percpu_lru_populate()
596 		node->type = BPF_LRU_LIST_T_FREE;  in bpf_percpu_lru_populate()
597 		bpf_lru_node_clear_ref(node);  in bpf_percpu_lru_populate()
598 		list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);  in bpf_percpu_lru_populate()