Skip to contentSkip to conversation

netfilter: ipset: remove need to allocate memory on delete operations

PATCH In review Florian Westphal 3 participants 4 messages Aug 4 – Aug 10

Subsystems (2)
lore
Share & tools
lore

Florian Westphal

author maintainer
#0 lore raw

PATCH 1/1 netfilter: ipset: remove need to allocate memory on delete operations

Allocating mem via GFP_ATOMIC on delete is problematic, delete operations should always succedd.

Do in-place substitution: When /cidr reaches 0 count (no more elements in the range), move ranges stores later in the array forward and keep the count 0 ones at the end.

INIT_CIDR() can then check count == 0 without a need to search next element in the array.

To avoid problems on weakly ordered architectures, pack the structure so it is only 32bit wide, then use READ/WRITE_ONCE to store both cidr and count atomically.

_add path is unchanged: like the del path it acquires set->lock, i.e. we are only writer.

Fixes 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping")

---
Won't apply, this is supposed to go on top of the pending nf PR. In case that PR needs a v2, this could be squashed.

 net/netfilter/ipset/ip_set_hash_gen.h | 71 ++++++++++++++++-----------
 1 file changed, 43 insertions(+), 28 deletions(-)
net/netfilter/ipset/ip_set_hash_gen.h +43 -28
index 784e6d4a00ea..b2089ff6f1dc 100644
@@ -101,9 +101,10 @@ struct htable {
 
 /* Book-keeping of the prefixes added to the set */
 struct net_prefix {
-	u8 cidr;			/* the cidr value */
-	u32 count;			/* number of elements of this cidr */
+	u32 cidr:8;
+	u32 count:24;
 };
+#define CIDR_MAX_COUNT ((1 << 24) - 1)
 
 struct net_prefixes {
 	struct rcu_head rcu;
@@ -144,8 +145,11 @@ htable_size(u8 hbits)
 #endif
 
 #define INIT_CIDR(n, host_mask) ({				\
-	const struct net_prefixes *__n = rcu_dereference(n);		\
-	DCIDR_PUT((__n)->len ? (__n)->nets[0].cidr : host_mask);\
+	const struct net_prefixes *__n = rcu_dereference(n);	\
+	struct net_prefix __p =					\
+		__n->len ? READ_ONCE(__n->nets[0])		\
+			 : (struct net_prefix){};		\
+	DCIDR_PUT(__p.count ? __p.cidr : host_mask);		\
 })
 
 #endif /* IP_SET_HASH_WITH_NETS */
@@ -436,7 +440,10 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 		} else if (nets->nets[i].cidr < cidr) {
 			found = i;
 		} else if (nets->nets[i].cidr == cidr) {
-			nets->nets[i].count++;
+			if (nets->nets[i].count < CIDR_MAX_COUNT)
+				nets->nets[i].count++;
+			else
+				ret = -EOVERFLOW;
 			goto unlock;
 		}
 	}
@@ -472,39 +479,43 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 static void
 mtype_del_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 {
-	struct net_prefixes *nets, *tmp;
-	u8 i, j, len = 0;
+	struct net_prefixes *nets;
+	struct net_prefix np;
 	int found;
+	u8 i, j;
+
+	BUILD_BUG_ON(sizeof(struct net_prefix) != sizeof(u32));
 
 	spin_lock_bh(&set->lock);
 	nets = __ipset_dereference(h->rnets[n]);
 	for (i = 0, found = -1; i < nets->len; i++) {
-		if (nets->nets[i].count)
-			len++;
-		if (nets->nets[i].cidr == cidr)
+		np = READ_ONCE(nets->nets[i]);
+		if (np.count && np.cidr == cidr) {
+			np.count--;
 			found = i;
+			break;
+		}
 	}
 	if (unlikely(found == -1))
 		goto unlock;
 
-	nets->nets[found].count--;
-	if (nets->nets[found].count)
-		goto unlock;
-	len--;
-	tmp = kzalloc_flex(*tmp, nets, len, GFP_ATOMIC);
-	if (!tmp)
-		/* Leave a hole */
+	if (np.count) {
+		WRITE_ONCE(nets->nets[found], np);
 		goto unlock;
+	}
 
-	tmp->len = len;
 	for (i = 0, j = 0; i < nets->len; i++) {
-		if (!nets->nets[i].count || i == found)
+		if (i == found)
 			continue;
-		tmp->nets[j].cidr = nets->nets[i].cidr;
-		tmp->nets[j++].count = nets->nets[i].count;
+
+		np = READ_ONCE(nets->nets[i]);
+		if (i != j)
+			WRITE_ONCE(nets->nets[j], np);
+		j++;
 	}
-	rcu_assign_pointer(h->rnets[n], tmp);
-	kfree_rcu(nets, rcu);
+
+	while (j < nets->len)
+		WRITE_ONCE(nets->nets[j++], (struct net_prefix){});
 unlock:
 	spin_unlock_bh(&set->lock);
 }
@@ -1381,17 +1392,21 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
 	nets1 = rcu_dereference_bh(h->rnets[1]);
 #endif
 	for (j = 0; j < nets0->len && !multi; j++) {
-		if (!nets0->nets[j].count)
+		struct net_prefix p0 = READ_ONCE(nets0->nets[j]);
+
+		if (!p0.count)
 			continue;
 #if IPSET_NET_COUNT == 2
 		mtype_data_reset_elem(d, &orig);
-		mtype_data_netmask(d, nets0->nets[j].cidr, false);
+		mtype_data_netmask(d, p0.cidr, false);
 		for (k = 0; k < nets1->len && !multi; k++) {
-			if (!nets1->nets[k].count)
+			struct net_prefix p1 = READ_ONCE(nets1->nets[k]);
+
+			if (!p1.count)
 				continue;
-			mtype_data_netmask(d, nets1->nets[k].cidr, true);
+			mtype_data_netmask(d, p1.cidr, true);
 #else
-		mtype_data_netmask(d, nets0->nets[j].cidr);
+		mtype_data_netmask(d, p0.cidr);
 #endif
 		key = HKEY(d, h->initval, t->htable_bits);
 		n = rcu_dereference_bh(hbucket(t, key));
Signature · 1 line
2.54.0
#1 lore raw

Hi Florian,

Quoted 31 lines · Florian Westphal

Allocating mem via GFP_ATOMIC on delete is problematic, delete operations should always succedd.

Do in-place substitution: When /cidr reaches 0 count (no more elements in the range), move ranges stores later in the array forward and keep the count 0 ones at the end.

INIT_CIDR() can then check count == 0 without a need to search next element in the array.

To avoid problems on weakly ordered architectures, pack the structure so it is only 32bit wide, then use READ/WRITE_ONCE to store both cidr and count atomically.

_add path is unchanged: like the del path it acquires set->lock, i.e. we are only writer.

Fixes 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping")

---
Won't apply, this is supposed to go on top of the pending nf PR. In case that PR needs a v2, this could be squashed.

 net/netfilter/ipset/ip_set_hash_gen.h | 71 ++++++++++++++++-----------
 1 file changed, 43 insertions(+), 28 deletions(-)
net/netfilter/ipset/ip_set_hash_gen.h +0 -0
index 784e6d4a00ea..b2089ff6f1dc 100644

net/netfilter/ipset/ip_set_hash_gen.h struct htable { · line 107

Quoted 9 lines
net/netfilter/ipset/ip_set_hash_gen.h +3 -2
@@ -101,9 +101,10 @@ struct htable {
 
 /* Book-keeping of the prefixes added to the set */
 struct net_prefix {
-	u8 cidr;			/* the cidr value */
-	u32 count;			/* number of elements of this cidr */
+	u32 cidr:8;
+	u32 count:24;
 };
+#define CIDR_MAX_COUNT ((1 << 24) - 1)

Could it be changed to

struct net_prefix {
     u64 cidr:8;
     u64 count:24;
};

#define CIDR_MAX_COUNT ((1 << 56) - 1)

(and the other required changes below)?

2**24 is a lot but still a reachable limit.

Quoted 108 lines
net/netfilter/ipset/ip_set_hash_gen.h +37 -24
 struct net_prefixes {
 	struct rcu_head rcu;
@@ -144,8 +145,11 @@ htable_size(u8 hbits)
 #endif
 
 #define INIT_CIDR(n, host_mask) ({				\
-	const struct net_prefixes *__n = rcu_dereference(n);		\
-	DCIDR_PUT((__n)->len ? (__n)->nets[0].cidr : host_mask);\
+	const struct net_prefixes *__n = rcu_dereference(n);	\
+	struct net_prefix __p =					\
+		__n->len ? READ_ONCE(__n->nets[0])		\
+			 : (struct net_prefix){};		\
+	DCIDR_PUT(__p.count ? __p.cidr : host_mask);		\
 })
 
 #endif /* IP_SET_HASH_WITH_NETS */
@@ -436,7 +440,10 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 		} else if (nets->nets[i].cidr < cidr) {
 			found = i;
 		} else if (nets->nets[i].cidr == cidr) {
-			nets->nets[i].count++;
+			if (nets->nets[i].count < CIDR_MAX_COUNT)
+				nets->nets[i].count++;
+			else
+				ret = -EOVERFLOW;
 			goto unlock;
 		}
 	}
@@ -472,39 +479,43 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 static void
 mtype_del_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 {
-	struct net_prefixes *nets, *tmp;
-	u8 i, j, len = 0;
+	struct net_prefixes *nets;
+	struct net_prefix np;
 	int found;
+	u8 i, j;
+
+	BUILD_BUG_ON(sizeof(struct net_prefix) != sizeof(u32));
 
 	spin_lock_bh(&set->lock);
 	nets = __ipset_dereference(h->rnets[n]);
 	for (i = 0, found = -1; i < nets->len; i++) {
-		if (nets->nets[i].count)
-			len++;
-		if (nets->nets[i].cidr == cidr)
+		np = READ_ONCE(nets->nets[i]);
+		if (np.count && np.cidr == cidr) {
+			np.count--;
 			found = i;
+			break;
+		}
 	}
 	if (unlikely(found == -1))
 		goto unlock;
 
-	nets->nets[found].count--;
-	if (nets->nets[found].count)
-		goto unlock;
-	len--;
-	tmp = kzalloc_flex(*tmp, nets, len, GFP_ATOMIC);
-	if (!tmp)
-		/* Leave a hole */
+	if (np.count) {
+		WRITE_ONCE(nets->nets[found], np);
 		goto unlock;
+	}
 
-	tmp->len = len;
 	for (i = 0, j = 0; i < nets->len; i++) {
-		if (!nets->nets[i].count || i == found)
+		if (i == found)
 			continue;
-		tmp->nets[j].cidr = nets->nets[i].cidr;
-		tmp->nets[j++].count = nets->nets[i].count;
+
+		np = READ_ONCE(nets->nets[i]);
+		if (i != j)
+			WRITE_ONCE(nets->nets[j], np);
+		j++;
 	}
-	rcu_assign_pointer(h->rnets[n], tmp);
-	kfree_rcu(nets, rcu);
+
+	while (j < nets->len)
+		WRITE_ONCE(nets->nets[j++], (struct net_prefix){});
 unlock:
 	spin_unlock_bh(&set->lock);
 }
@@ -1381,17 +1392,21 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
 	nets1 = rcu_dereference_bh(h->rnets[1]);
 #endif
 	for (j = 0; j < nets0->len && !multi; j++) {
-		if (!nets0->nets[j].count)
+		struct net_prefix p0 = READ_ONCE(nets0->nets[j]);
+
+		if (!p0.count)
 			continue;
 #if IPSET_NET_COUNT == 2
 		mtype_data_reset_elem(d, &orig);
-		mtype_data_netmask(d, nets0->nets[j].cidr, false);
+		mtype_data_netmask(d, p0.cidr, false);
 		for (k = 0; k < nets1->len && !multi; k++) {
-			if (!nets1->nets[k].count)
+			struct net_prefix p1 = READ_ONCE(nets1->nets[k]);
+

net/netfilter/ipset/ip_set_hash_gen.h mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d, · line 1412

Quoted 10 lines
net/netfilter/ipset/ip_set_hash_gen.h +3 -2
+			if (!p1.count)
 				continue;
-			mtype_data_netmask(d, nets1->nets[k].cidr, true);
+			mtype_data_netmask(d, p1.cidr, true);
 #else
-		mtype_data_netmask(d, nets0->nets[j].cidr);
+		mtype_data_netmask(d, p0.cidr);
 #endif
 		key = HKEY(d, h->initval, t->htable_bits);
 		n = rcu_dereference_bh(hbucket(t, key));

Best regards,
Jozsef

Signature · 3 lines
E-mail : [email protected], [email protected], [email protected]
Address: Wigner Research Centre for Physics
         H-1525 Budapest 114, POB. 49, Hungary
author maintainer
#2 lore raw
Quoted 11 lines · Jozsef Kadlecsik

net/netfilter/ipset/ip_set_hash_gen.h struct htable { · line 107

Quoted 8 lines

/* Book-keeping of the prefixes added to the set */ struct net_prefix {

net/netfilter/ipset/ip_set_hash_gen.h +3 -2
-	u8 cidr;			/* the cidr value */
-	u32 count;			/* number of elements of this cidr */
+	u32 cidr:8;
+	u32 count:24;
 };
+#define CIDR_MAX_COUNT ((1 << 24) - 1)

Could it be changed to

Quoted 7 lines
struct net_prefix {
     u64 cidr:8;
     u64 count:24;
};

#define CIDR_MAX_COUNT ((1 << 56) - 1)

(and the other required changes below)?

Only for 64bit builds, because WRITE_ONCE() is not atomic on 32bit. If we do it for 32 bit builds, all read side paths would need to switch to write seqcount use (including the normal case, i.e. nets[i]->count++ / count. ATM only the "it became 0 and has to be moved) uses the sequence write lock, so read side never retries for typical updates.

Quoted 1 line

2**24 is a lot but still a reachable limit.

Hmm. 16m entries... I guess its possible for very small prefix lengths? We could use BITS_PER_LONG == 64 but it gets more ugly then.

Quoted 3 lines

net/netfilter/ipset/ip_set_hash_gen.h mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n) · line 504

Quoted 3 lines
net/netfilter/ipset/ip_set_hash_gen.h +2 -0
+	if (np.count) {
+		WRITE_ONCE(nets->nets[found], np);
 		goto unlock;

This should be the typical case, which doesn't change the write seq side, hence no retry on reader side.

This would have to be changed if we no longer rely on READ/WRITE_ONCE.

#3 lore raw

Hi Florian,

Quoted 4 lines · Florian Westphal
Quoted 1 line

2**24 is a lot but still a reachable limit.

Hmm. 16m entries... I guess its possible for very small prefix lengths? We could use BITS_PER_LONG == 64 but it gets more ugly then.

I was thinking on IPv6 where it's more possible. But hash:ip has no such limitation with same-size prefixes so there are other solutions to store large number of same-size prefixes.

Best regards,
Jozsef