net/netfilter/nft_set_bitmap.c

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

File Facts

System
Linux kernel
Corpus path
net/netfilter/nft_set_bitmap.c
Extension
.c
Size
9161 bytes
Lines
322
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_bitmap_elem {
	struct nft_elem_priv	priv;
	struct list_head	head;
	struct nft_set_ext	ext;
};

/* This bitmap uses two bits to represent one element. These two bits determine
 * the element state in the current and the future generation.
 *
 * An element can be in three states. The generation cursor is represented using
 * the ^ character, note that this cursor shifts on every successful transaction.
 * If no transaction is going on, we observe all elements are in the following
 * state:
 *
 * 11 = this element is active in the current generation. In case of no updates,
 * ^    it stays active in the next generation.
 * 00 = this element is inactive in the current generation. In case of no
 * ^    updates, it stays inactive in the next generation.
 *
 * On transaction handling, we observe these two temporary states:
 *
 * 01 = this element is inactive in the current generation and it becomes active
 * ^    in the next one. This happens when the element is inserted but commit
 *      path has not yet been executed yet, so activation is still pending. On
 *      transaction abortion, the element is removed.
 * 10 = this element is active in the current generation and it becomes inactive
 * ^    in the next one. This happens when the element is deactivated but commit
 *      path has not yet been executed yet, so removal is still pending. On
 *      transaction abortion, the next generation bit is reset to go back to
 *      restore its previous state.
 */
struct nft_bitmap {
	struct	list_head	list;
	u16			bitmap_size;
	u8			bitmap[];
};

static inline void nft_bitmap_location(const struct nft_set *set,
				       const void *key,
				       u32 *idx, u32 *off)
{
	u32 k;

	if (set->klen == 2)
		k = *(u16 *)key;
	else
		k = *(u8 *)key;
	k <<= 1;

	*idx = k / BITS_PER_BYTE;
	*off = k % BITS_PER_BYTE;
}

/* Fetch the two bits that represent the element and check if it is active based
 * on the generation mask.
 */
static inline bool
nft_bitmap_active(const u8 *bitmap, u32 idx, u32 off, u8 genmask)
{
	return (bitmap[idx] & (0x3 << off)) & (genmask << off);
}

INDIRECT_CALLABLE_SCOPE
const struct nft_set_ext *
nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
		  const u32 *key)
{
	const struct nft_bitmap *priv = nft_set_priv(set);
	static const struct nft_set_ext found;
	u8 genmask = nft_genmask_cur(net);
	u32 idx, off;

	nft_bitmap_location(set, key, &idx, &off);

	if (nft_bitmap_active(priv->bitmap, idx, off, genmask))
		return &found;

	return NULL;
}

static struct nft_bitmap_elem *
nft_bitmap_elem_find(const struct net *net,
		     const struct nft_set *set, struct nft_bitmap_elem *this,
		     u8 genmask)
{
	const struct nft_bitmap *priv = nft_set_priv(set);
	struct nft_bitmap_elem *be;

	list_for_each_entry_rcu(be, &priv->list, head,
				lockdep_is_held(&nft_pernet(net)->commit_mutex)) {

Annotation

Implementation Notes