net/netfilter/nft_set_rbtree.c

Source file repositories/reference/linux-study-clean/net/netfilter/nft_set_rbtree.c

File Facts

System
Linux kernel
Corpus path
net/netfilter/nft_set_rbtree.c
Extension
.c
Size
30781 bytes
Lines
1200
Domain
Networking Core
Bucket
Sockets, Protocols, Packet Path, And Network Policy
Inferred role
Networking Core: implementation source
Status
source implementation candidate

Why This File Exists

Networking stack implementation surface: socket APIs, protocol dispatch, packet flow, routing, filtering, and network namespaces.

Dependency Surface

Detected Declarations

Annotated Snippet

struct nft_array_interval {
	struct nft_set_ext	*from;
	struct nft_set_ext	*to;
};

struct nft_array {
	u32			max_intervals;
	u32			num_intervals;
	struct nft_array_interval *intervals;
	struct rcu_head		rcu_head;
};

struct nft_rbtree {
	struct rb_root		root;
	rwlock_t		lock;
	struct nft_array __rcu	*array;
	struct nft_array	*array_next;
	unsigned long		start_rbe_cookie;
	unsigned long		last_gc;
	struct list_head	expired;
	u64			last_tstamp;
};

struct nft_rbtree_elem {
	struct nft_elem_priv	priv;
	union {
		struct rb_node	node;
		struct list_head list;
	};
	struct nft_set_ext	ext;
};

static bool nft_rbtree_interval_end(const struct nft_rbtree_elem *rbe)
{
	return nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) &&
	       (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END);
}

static bool nft_rbtree_interval_start(const struct nft_rbtree_elem *rbe)
{
	return !nft_rbtree_interval_end(rbe);
}

static bool nft_rbtree_interval_null(const struct nft_set *set,
				     const struct nft_rbtree_elem *rbe)
{
	return (!memchr_inv(nft_set_ext_key(&rbe->ext), 0, set->klen) &&
		nft_rbtree_interval_end(rbe));
}

static int nft_rbtree_cmp(const struct nft_set *set,
			  const struct nft_rbtree_elem *e1,
			  const struct nft_rbtree_elem *e2)
{
	return memcmp(nft_set_ext_key(&e1->ext), nft_set_ext_key(&e2->ext),
		      set->klen);
}

struct nft_array_lookup_ctx {
	const u32	*key;
	u32		klen;
};

static int nft_array_lookup_cmp(const void *pkey, const void *entry)
{
	const struct nft_array_interval *interval = entry;
	const struct nft_array_lookup_ctx *ctx = pkey;
	int a, b;

	if (!interval->from)
		return 1;

	a = memcmp(ctx->key, nft_set_ext_key(interval->from), ctx->klen);
	if (!interval->to)
		b = -1;
	else
		b = memcmp(ctx->key, nft_set_ext_key(interval->to), ctx->klen);

	if (a >= 0 && b < 0)
		return 0;

	if (a < 0)
		return -1;

	return 1;
}

INDIRECT_CALLABLE_SCOPE
const struct nft_set_ext *
nft_rbtree_lookup(const struct net *net, const struct nft_set *set,

Annotation

Implementation Notes