42 static bool bpf_lru_node_is_ref(const struct bpf_lru_node *node)  in bpf_lru_node_is_ref()  argument
44 	return READ_ONCE(node->ref);  in bpf_lru_node_is_ref()
47 static void bpf_lru_node_clear_ref(struct bpf_lru_node *node)  in bpf_lru_node_clear_ref()  argument
49 	WRITE_ONCE(node->ref, 0);  in bpf_lru_node_clear_ref()
67 					struct bpf_lru_node *node,  in __bpf_lru_node_move_to_free()  argument
71 	if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))  in __bpf_lru_node_move_to_free()
77 	if (&node->list == l->next_inactive_rotation)  in __bpf_lru_node_move_to_free()
80 	bpf_lru_list_count_dec(l, node->type);  in __bpf_lru_node_move_to_free()
82 	node->type = tgt_free_type;  in __bpf_lru_node_move_to_free()
83 	list_move(&node->list, free_list);  in __bpf_lru_node_move_to_free()
88 				   struct bpf_lru_node *node,  in __bpf_lru_node_move_in()  argument
91 	if (WARN_ON_ONCE(!IS_LOCAL_LIST_TYPE(node->type)) ||  in __bpf_lru_node_move_in()
96 	node->type = tgt_type;  in __bpf_lru_node_move_in()
97 	bpf_lru_node_clear_ref(node);  in __bpf_lru_node_move_in()
98 	list_move(&node->list, &l->lists[tgt_type]);  in __bpf_lru_node_move_in()
106 				struct bpf_lru_node *node,  in __bpf_lru_node_move()  argument
109 	if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)) ||  in __bpf_lru_node_move()
113 	if (node->type != tgt_type) {  in __bpf_lru_node_move()
114 		bpf_lru_list_count_dec(l, node->type);  in __bpf_lru_node_move()
116 		node->type = tgt_type;  in __bpf_lru_node_move()
118 	bpf_lru_node_clear_ref(node);  in __bpf_lru_node_move()
123 	if (&node->list == l->next_inactive_rotation)  in __bpf_lru_node_move()
126 	list_move(&node->list, &l->lists[tgt_type]);  in __bpf_lru_node_move()
148 	struct bpf_lru_node *node, *tmp_node, *first_node;  in __bpf_lru_list_rotate_active()  local
152 	list_for_each_entry_safe_reverse(node, tmp_node, active, list) {  in __bpf_lru_list_rotate_active()
153 		if (bpf_lru_node_is_ref(node))  in __bpf_lru_list_rotate_active()
154 			__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);  in __bpf_lru_list_rotate_active()
156 			__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);  in __bpf_lru_list_rotate_active()
158 		if (++i == lru->nr_scans || node == first_node)  in __bpf_lru_list_rotate_active()
176 	struct bpf_lru_node *node;  in __bpf_lru_list_rotate_inactive()  local
193 		node = list_entry(cur, struct bpf_lru_node, list);  in __bpf_lru_list_rotate_inactive()
195 		if (bpf_lru_node_is_ref(node))  in __bpf_lru_list_rotate_inactive()
196 			__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);  in __bpf_lru_list_rotate_inactive()
218 	struct bpf_lru_node *node, *tmp_node;  in __bpf_lru_list_shrink_inactive()  local
222 	list_for_each_entry_safe_reverse(node, tmp_node, inactive, list) {  in __bpf_lru_list_shrink_inactive()
223 		if (bpf_lru_node_is_ref(node)) {  in __bpf_lru_list_shrink_inactive()
224 			__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);  in __bpf_lru_list_shrink_inactive()
225 		} else if (lru->del_from_htab(lru->del_arg, node)) {  in __bpf_lru_list_shrink_inactive()
226 			__bpf_lru_node_move_to_free(l, node, free_list,  in __bpf_lru_list_shrink_inactive()
267 	struct bpf_lru_node *node, *tmp_node;  in __bpf_lru_list_shrink()  local
282 	list_for_each_entry_safe_reverse(node, tmp_node, force_shrink_list,  in __bpf_lru_list_shrink()
284 		if (lru->del_from_htab(lru->del_arg, node)) {  in __bpf_lru_list_shrink()
285 			__bpf_lru_node_move_to_free(l, node, free_list,  in __bpf_lru_list_shrink()
298 	struct bpf_lru_node *node, *tmp_node;  in __local_list_flush()  local
300 	list_for_each_entry_safe_reverse(node, tmp_node,  in __local_list_flush()
302 		if (bpf_lru_node_is_ref(node))  in __local_list_flush()
303 			__bpf_lru_node_move_in(l, node, BPF_LRU_LIST_T_ACTIVE);  in __local_list_flush()
305 			__bpf_lru_node_move_in(l, node,  in __local_list_flush()
311 				   struct bpf_lru_node *node)  in bpf_lru_list_push_free()  argument
315 	if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))  in bpf_lru_list_push_free()
319 	__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);  in bpf_lru_list_push_free()
327 	struct bpf_lru_node *node, *tmp_node;  in bpf_lru_list_pop_free_to_local()  local
336 	list_for_each_entry_safe(node, tmp_node, &l->lists[BPF_LRU_LIST_T_FREE],  in bpf_lru_list_pop_free_to_local()
338 		__bpf_lru_node_move_to_free(l, node, local_free_list(loc_l),  in bpf_lru_list_pop_free_to_local()
355 				     struct bpf_lru_node *node,  in __local_list_add_pending()  argument
358 	*(u32 *)((void *)node + lru->hash_offset) = hash;  in __local_list_add_pending()
359 	node->cpu = cpu;  in __local_list_add_pending()
360 	node->type = BPF_LRU_LOCAL_LIST_T_PENDING;  in __local_list_add_pending()
361 	bpf_lru_node_clear_ref(node);  in __local_list_add_pending()
362 	list_add(&node->list, local_pending_list(loc_l));  in __local_list_add_pending()
368 	struct bpf_lru_node *node;  in __local_list_pop_free()  local
370 	node = list_first_entry_or_null(local_free_list(loc_l),  in __local_list_pop_free()
373 	if (node)  in __local_list_pop_free()
374 		list_del(&node->list);  in __local_list_pop_free()
376 	return node;  in __local_list_pop_free()
382 	struct bpf_lru_node *node;  in __local_list_pop_pending()  local
387 	list_for_each_entry_reverse(node, local_pending_list(loc_l),  in __local_list_pop_pending()
389 		if ((!bpf_lru_node_is_ref(node) || force) &&  in __local_list_pop_pending()
390 		    lru->del_from_htab(lru->del_arg, node)) {  in __local_list_pop_pending()
391 			list_del(&node->list);  in __local_list_pop_pending()
392 			return node;  in __local_list_pop_pending()
408 	struct bpf_lru_node *node = NULL;  in bpf_percpu_lru_pop_free()  local
425 		node = list_first_entry(free_list, struct bpf_lru_node, list);  in bpf_percpu_lru_pop_free()
426 		*(u32 *)((void *)node + lru->hash_offset) = hash;  in bpf_percpu_lru_pop_free()
427 		bpf_lru_node_clear_ref(node);  in bpf_percpu_lru_pop_free()
428 		__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);  in bpf_percpu_lru_pop_free()
433 	return node;  in bpf_percpu_lru_pop_free()
441 	struct bpf_lru_node *node;  in bpf_common_lru_pop_free()  local
450 	node = __local_list_pop_free(loc_l);  in bpf_common_lru_pop_free()
451 	if (!node) {  in bpf_common_lru_pop_free()
453 		node = __local_list_pop_free(loc_l);  in bpf_common_lru_pop_free()
456 	if (node)  in bpf_common_lru_pop_free()
457 		__local_list_add_pending(lru, loc_l, cpu, node, hash);  in bpf_common_lru_pop_free()
461 	if (node)  in bpf_common_lru_pop_free()
462 		return node;  in bpf_common_lru_pop_free()
479 		node = __local_list_pop_free(steal_loc_l);  in bpf_common_lru_pop_free()
480 		if (!node)  in bpf_common_lru_pop_free()
481 			node = __local_list_pop_pending(lru, steal_loc_l);  in bpf_common_lru_pop_free()
486 	} while (!node && steal != first_steal);  in bpf_common_lru_pop_free()
490 	if (node) {  in bpf_common_lru_pop_free()
492 		__local_list_add_pending(lru, loc_l, cpu, node, hash);  in bpf_common_lru_pop_free()
496 	return node;  in bpf_common_lru_pop_free()
508 				     struct bpf_lru_node *node)  in bpf_common_lru_push_free()  argument
510 	u8 node_type = READ_ONCE(node->type);  in bpf_common_lru_push_free()
520 		loc_l = per_cpu_ptr(lru->common_lru.local_list, node->cpu);  in bpf_common_lru_push_free()
524 		if (unlikely(node->type != BPF_LRU_LOCAL_LIST_T_PENDING)) {  in bpf_common_lru_push_free()
529 		node->type = BPF_LRU_LOCAL_LIST_T_FREE;  in bpf_common_lru_push_free()
530 		bpf_lru_node_clear_ref(node);  in bpf_common_lru_push_free()
531 		list_move(&node->list, local_free_list(loc_l));  in bpf_common_lru_push_free()
538 	bpf_lru_list_push_free(&lru->common_lru.lru_list, node);  in bpf_common_lru_push_free()
542 				     struct bpf_lru_node *node)  in bpf_percpu_lru_push_free()  argument
547 	l = per_cpu_ptr(lru->percpu_lru, node->cpu);  in bpf_percpu_lru_push_free()
551 	__bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);  in bpf_percpu_lru_push_free()
556 void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node)  in bpf_lru_push_free()  argument
559 		bpf_percpu_lru_push_free(lru, node);  in bpf_lru_push_free()
561 		bpf_common_lru_push_free(lru, node);  in bpf_lru_push_free()
572 		struct bpf_lru_node *node;  in bpf_common_lru_populate()  local
574 		node = (struct bpf_lru_node *)(buf + node_offset);  in bpf_common_lru_populate()
575 		node->type = BPF_LRU_LIST_T_FREE;  in bpf_common_lru_populate()
576 		bpf_lru_node_clear_ref(node);  in bpf_common_lru_populate()
577 		list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);  in bpf_common_lru_populate()
595 		struct bpf_lru_node *node;  in bpf_percpu_lru_populate()  local
599 		node = (struct bpf_lru_node *)(buf + node_offset);  in bpf_percpu_lru_populate()
600 		node->cpu = cpu;  in bpf_percpu_lru_populate()
601 		node->type = BPF_LRU_LIST_T_FREE;  in bpf_percpu_lru_populate()
602 		bpf_lru_node_clear_ref(node);  in bpf_percpu_lru_populate()
603 		list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);  in bpf_percpu_lru_populate()