[linux.git] / kernel / bpf / bpf_lru_list.h

/* SPDX-License-Identifier: GPL-2.0-only */
/* Copyright (c) 2016 Facebook
 */
#ifndef __BPF_LRU_LIST_H_
#define __BPF_LRU_LIST_H_

#include <linux/cache.h>
#include <linux/list.h>
#include <linux/spinlock_types.h>

#define NR_BPF_LRU_LIST_T	(3)
#define NR_BPF_LRU_LIST_COUNT	(2)
#define NR_BPF_LRU_LOCAL_LIST_T (2)
#define BPF_LOCAL_LIST_T_OFFSET NR_BPF_LRU_LIST_T

enum bpf_lru_list_type {
	BPF_LRU_LIST_T_ACTIVE,
	BPF_LRU_LIST_T_INACTIVE,
	BPF_LRU_LIST_T_FREE,
	BPF_LRU_LOCAL_LIST_T_FREE,
	BPF_LRU_LOCAL_LIST_T_PENDING,
};

struct bpf_lru_node {
	struct list_head list;
	u16 cpu;
	u8 type;
	u8 ref;
};

struct bpf_lru_list {
	struct list_head lists[NR_BPF_LRU_LIST_T];
	unsigned int counts[NR_BPF_LRU_LIST_COUNT];
	/* The next inactive list rotation starts from here */
	struct list_head *next_inactive_rotation;

	raw_spinlock_t lock ____cacheline_aligned_in_smp;
};

struct bpf_lru_locallist {
	struct list_head lists[NR_BPF_LRU_LOCAL_LIST_T];
	u16 next_steal;
	raw_spinlock_t lock;
};

struct bpf_common_lru {
	struct bpf_lru_list lru_list;
	struct bpf_lru_locallist __percpu *local_list;
};

typedef bool (*del_from_htab_func)(void *arg, struct bpf_lru_node *node);

struct bpf_lru {
	union {
		struct bpf_common_lru common_lru;
		struct bpf_lru_list __percpu *percpu_lru;
	};
	del_from_htab_func del_from_htab;
	void *del_arg;
	unsigned int hash_offset;
	unsigned int nr_scans;
	bool percpu;
};

static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node)
{
	/* ref is an approximation on access frequency.  It does not
	 * have to be very accurate.  Hence, no protection is used.
	 */
	if (!node->ref)
		node->ref = 1;
}

int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
		 del_from_htab_func del_from_htab, void *delete_arg);
void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
		      u32 elem_size, u32 nr_elems);
void bpf_lru_destroy(struct bpf_lru *lru);
struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash);
void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node);
void bpf_lru_promote(struct bpf_lru *lru, struct bpf_lru_node *node);

#endif
Commit	Line	Data
25763b3c	1	/* SPDX-License-Identifier: GPL-2.0-only */
3a08c2fd	2	/* Copyright (c) 2016 Facebook
3a08c2fd MKL	3	*/
	4	#ifndef __BPF_LRU_LIST_H_
	5	#define __BPF_LRU_LIST_H_
	6
534aa1dc	7	#include <linux/cache.h>
3a08c2fd MKL	8	#include <linux/list.h>
	9	#include <linux/spinlock_types.h>
	10
	11	#define NR_BPF_LRU_LIST_T (3)
	12	#define NR_BPF_LRU_LIST_COUNT (2)
	13	#define NR_BPF_LRU_LOCAL_LIST_T (2)
	14	#define BPF_LOCAL_LIST_T_OFFSET NR_BPF_LRU_LIST_T
	15
	16	enum bpf_lru_list_type {
	17	BPF_LRU_LIST_T_ACTIVE,
	18	BPF_LRU_LIST_T_INACTIVE,
	19	BPF_LRU_LIST_T_FREE,
	20	BPF_LRU_LOCAL_LIST_T_FREE,
	21	BPF_LRU_LOCAL_LIST_T_PENDING,
	22	};
	23
	24	struct bpf_lru_node {
	25	struct list_head list;
	26	u16 cpu;
	27	u8 type;
	28	u8 ref;
	29	};
	30
	31	struct bpf_lru_list {
	32	struct list_head lists[NR_BPF_LRU_LIST_T];
	33	unsigned int counts[NR_BPF_LRU_LIST_COUNT];
0ac16296	34	/* The next inactive list rotation starts from here */
3a08c2fd MKL	35	struct list_head *next_inactive_rotation;
	36
	37	raw_spinlock_t lock ____cacheline_aligned_in_smp;
	38	};
	39
	40	struct bpf_lru_locallist {
	41	struct list_head lists[NR_BPF_LRU_LOCAL_LIST_T];
	42	u16 next_steal;
	43	raw_spinlock_t lock;
	44	};
	45
	46	struct bpf_common_lru {
	47	struct bpf_lru_list lru_list;
	48	struct bpf_lru_locallist __percpu *local_list;
	49	};
	50
	51	typedef bool (del_from_htab_func)(void arg, struct bpf_lru_node *node);
	52
	53	struct bpf_lru {
961578b6 MKL	54	union {
	55	struct bpf_common_lru common_lru;
	56	struct bpf_lru_list __percpu *percpu_lru;
	57	};
3a08c2fd MKL	58	del_from_htab_func del_from_htab;
	59	void *del_arg;
	60	unsigned int hash_offset;
	61	unsigned int nr_scans;
961578b6	62	bool percpu;
3a08c2fd MKL	63	};
	64
	65	static inline void bpf_lru_node_set_ref(struct bpf_lru_node *node)
	66	{
	67	/* ref is an approximation on access frequency. It does not
	68	* have to be very accurate. Hence, no protection is used.
	69	*/
bb9b9f88 MKL	70	if (!node->ref)
bb9b9f88 MKL	71	node->ref = 1;
3a08c2fd MKL	72	}
3a08c2fd MKL	73
961578b6	74	int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
3a08c2fd MKL	75	del_from_htab_func del_from_htab, void *delete_arg);
	76	void bpf_lru_populate(struct bpf_lru lru, void buf, u32 node_offset,
	77	u32 elem_size, u32 nr_elems);
	78	void bpf_lru_destroy(struct bpf_lru *lru);
	79	struct bpf_lru_node bpf_lru_pop_free(struct bpf_lru lru, u32 hash);
	80	void bpf_lru_push_free(struct bpf_lru lru, struct bpf_lru_node node);
	81	void bpf_lru_promote(struct bpf_lru lru, struct bpf_lru_node node);
	82
	83	#endif