diff --git a/SOURCES/v1.0.0-0037-fix-ipset-reduce-cost-of-entry-overlap-detection.patch b/SOURCES/v1.0.0-0037-fix-ipset-reduce-cost-of-entry-overlap-detection.patch
new file mode 100644
index 0000000..54a26d0
--- /dev/null
+++ b/SOURCES/v1.0.0-0037-fix-ipset-reduce-cost-of-entry-overlap-detection.patch
@@ -0,0 +1,140 @@
+From 3eb0f3239b9b35a1c388a91fc2e546b1e87cb020 Mon Sep 17 00:00:00 2001
+From: Eric Garver <eric@garver.life>
+Date: Tue, 30 Nov 2021 14:54:20 -0500
+Subject: [PATCH 37/39] fix(ipset): reduce cost of entry overlap detection
+
+This increases peak memory usage to reduce the duration it takes to
+apply the set entries. Building the list of IPv4Network objects up front
+means we don't have to build them multiple times inside the for loop.
+
+Fixes: #881
+(cherry picked from commit 7f5b736378c0133f46470c42e0c1fb3b95087de5)
+---
+ src/firewall/client.py | 10 ++++------
+ src/firewall/core/fw_ipset.py | 9 +++------
+ src/firewall/core/ipset.py | 27 ++++++++++++++++++++++-----
+ src/firewall/server/config_ipset.py | 10 ++++------
+ 4 files changed, 33 insertions(+), 23 deletions(-)
+
+diff --git a/src/firewall/client.py b/src/firewall/client.py
+index 3715ffd29316..fdc88ac7946b 100644
+--- a/src/firewall/client.py
++++ b/src/firewall/client.py
+@@ -34,7 +34,8 @@ from firewall.core.base import DEFAULT_ZONE_TARGET, DEFAULT_POLICY_TARGET, DEFAU
+ from firewall.dbus_utils import dbus_to_python
+ from firewall.functions import b2u
+ from firewall.core.rich import Rich_Rule
+-from firewall.core.ipset import normalize_ipset_entry, check_entry_overlaps_existing
++from firewall.core.ipset import normalize_ipset_entry, check_entry_overlaps_existing, \
++ check_for_overlapping_entries
+ from firewall import errors
+ from firewall.errors import FirewallError
+
+@@ -1617,11 +1618,8 @@ class FirewallClientIPSetSettings(object):
+ if "timeout" in self.settings[4] and \
+ self.settings[4]["timeout"] != "0":
+ raise FirewallError(errors.IPSET_WITH_TIMEOUT)
+- _entries = set()
+- for _entry in dbus_to_python(entries, list):
+- check_entry_overlaps_existing(_entry, _entries)
+- _entries.add(normalize_ipset_entry(_entry))
+- self.settings[5] = list(_entries)
++ check_for_overlapping_entries(entries)
++ self.settings[5] = entries
+ @handle_exceptions
+ def addEntry(self, entry):
+ if "timeout" in self.settings[4] and \
+diff --git a/src/firewall/core/fw_ipset.py b/src/firewall/core/fw_ipset.py
+index a285fd4a4aab..d7878c01921e 100644
+--- a/src/firewall/core/fw_ipset.py
++++ b/src/firewall/core/fw_ipset.py
+@@ -25,7 +25,8 @@ __all__ = [ "FirewallIPSet" ]
+
+ from firewall.core.logger import log
+ from firewall.core.ipset import remove_default_create_options as rm_def_cr_opts, \
+- normalize_ipset_entry, check_entry_overlaps_existing
++ normalize_ipset_entry, check_entry_overlaps_existing, \
++ check_for_overlapping_entries
+ from firewall.core.io.ipset import IPSet
+ from firewall import errors
+ from firewall.errors import FirewallError
+@@ -244,11 +245,7 @@ class FirewallIPSet(object):
+ def set_entries(self, name, entries):
+ obj = self.get_ipset(name, applied=True)
+
+- _entries = set()
+- for _entry in entries:
+- check_entry_overlaps_existing(_entry, _entries)
+- _entries.add(normalize_ipset_entry(_entry))
+- entries = list(_entries)
++ check_for_overlapping_entries(entries)
+
+ for entry in entries:
+ IPSet.check_entry(entry, obj.options, obj.type)
+diff --git a/src/firewall/core/ipset.py b/src/firewall/core/ipset.py
+index d6defa395241..66ea4335536d 100644
+--- a/src/firewall/core/ipset.py
++++ b/src/firewall/core/ipset.py
+@@ -309,9 +309,26 @@ def check_entry_overlaps_existing(entry, entries):
+ if len(entry.split(",")) > 1:
+ return
+
++ try:
++ entry_network = ipaddress.ip_network(entry, strict=False)
++ except ValueError:
++ # could not parse the new IP address, maybe a MAC
++ return
++
+ for itr in entries:
+- try:
+- if ipaddress.ip_network(itr, strict=False).overlaps(ipaddress.ip_network(entry, strict=False)):
+- raise FirewallError(errors.INVALID_ENTRY, "Entry '{}' overlaps with existing entry '{}'".format(itr, entry))
+- except ValueError:
+- pass
++ if entry_network.overlaps(ipaddress.ip_network(itr, strict=False)):
++ raise FirewallError(errors.INVALID_ENTRY, "Entry '{}' overlaps with existing entry '{}'".format(entry, itr))
++
++def check_for_overlapping_entries(entries):
++ """ Check if any entry overlaps any entry in the list of entries """
++ try:
++ entries = [ipaddress.ip_network(x, strict=False) for x in entries]
++ except ValueError:
++ # at least one entry can not be parsed
++ return
++
++ while entries:
++ entry = entries.pop()
++ for itr in entries:
++ if entry.overlaps(itr):
++ raise FirewallError(errors.INVALID_ENTRY, "Entry '{}' overlaps entry '{}'".format(entry, itr))
+diff --git a/src/firewall/server/config_ipset.py b/src/firewall/server/config_ipset.py
+index f33c2a02926f..499ffcb9227a 100644
+--- a/src/firewall/server/config_ipset.py
++++ b/src/firewall/server/config_ipset.py
+@@ -34,7 +34,8 @@ from firewall.dbus_utils import dbus_to_python, \
+ dbus_introspection_add_properties
+ from firewall.core.io.ipset import IPSet
+ from firewall.core.ipset import IPSET_TYPES, normalize_ipset_entry, \
+- check_entry_overlaps_existing
++ check_entry_overlaps_existing, \
++ check_for_overlapping_entries
+ from firewall.core.logger import log
+ from firewall.server.decorators import handle_exceptions, \
+ dbus_handle_exceptions, dbus_service_method
+@@ -407,11 +408,8 @@ class FirewallDConfigIPSet(slip.dbus.service.Object):
+ in_signature='as')
+ @dbus_handle_exceptions
+ def setEntries(self, entries, sender=None):
+- _entries = set()
+- for _entry in dbus_to_python(entries, list):
+- check_entry_overlaps_existing(_entry, _entries)
+- _entries.add(normalize_ipset_entry(_entry))
+- entries = list(_entries)
++ entries = dbus_to_python(entries, list)
++ check_for_overlapping_entries(entries)
+ log.debug1("%s.setEntries('[%s]')", self._log_prefix,
+ ",".join(entries))
+ self.parent.accessCheck(sender)
+--
+2.31.1
+
diff --git a/SOURCES/v1.0.0-0038-test-ipset-huge-set-of-entries-benchmark.patch b/SOURCES/v1.0.0-0038-test-ipset-huge-set-of-entries-benchmark.patch
new file mode 100644
index 0000000..362202b
--- /dev/null
+++ b/SOURCES/v1.0.0-0038-test-ipset-huge-set-of-entries-benchmark.patch
@@ -0,0 +1,56 @@
+From 976260a0d74009cea18f3c60e4b03e7f41de8fa9 Mon Sep 17 00:00:00 2001
+From: Eric Garver <eric@garver.life>
+Date: Tue, 30 Nov 2021 14:50:17 -0500
+Subject: [PATCH 38/39] test(ipset): huge set of entries benchmark
+
+Coverage: #881
+(cherry picked from commit 114936c71ab1b12a5598d06805b7e9e13f7ee190)
+---
+ src/tests/regression/gh881.at | 25 +++++++++++++++++++++++++
+ src/tests/regression/regression.at | 1 +
+ 2 files changed, 26 insertions(+)
+ create mode 100644 src/tests/regression/gh881.at
+
+diff --git a/src/tests/regression/gh881.at b/src/tests/regression/gh881.at
+new file mode 100644
+index 000000000000..c7326805b555
+--- /dev/null
++++ b/src/tests/regression/gh881.at
+@@ -0,0 +1,25 @@
++FWD_START_TEST([ipset entry overlap detect perf])
++AT_KEYWORDS(ipset gh881)
++
++dnl build a large ipset
++dnl
++AT_DATA([./deny_cidr], [])
++NS_CHECK([sh -c '
++for I in $(seq 10); do
++ for J in $(seq 250); do
++ echo "10.${I}.${J}.0/24" >> ./deny_cidr
++ done
++done
++'])
++
++dnl verify non-overlapping does not error
++dnl
++FWD_CHECK([--permanent --new-ipset=deny_set --type=hash:net --option=family=inet --option=hashsize=16384 --option=maxelem=20000], 0, [ignore])
++NS_CHECK([time timeout 300 firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 0, [ignore], [ignore])
++
++dnl verify overlap detection actually detects an overlap
++dnl
++NS_CHECK([echo "10.1.0.0/16" >> ./deny_cidr])
++NS_CHECK([time timeout 300 firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 136, [ignore], [ignore])
++
++FWD_END_TEST()
+diff --git a/src/tests/regression/regression.at b/src/tests/regression/regression.at
+index aadd948a459f..6ef6579434b1 100644
+--- a/src/tests/regression/regression.at
++++ b/src/tests/regression/regression.at
+@@ -42,3 +42,4 @@ m4_include([regression/ipset_netmask_allowed.at])
+ m4_include([regression/rhbz1940928.at])
+ m4_include([regression/rhbz1936896.at])
+ m4_include([regression/rhbz1914935.at])
++m4_include([regression/gh881.at])
+--
+2.31.1
+
diff --git a/SOURCES/v1.0.0-0039-fix-ipset-further-reduce-cost-of-entry-overlap-detec.patch b/SOURCES/v1.0.0-0039-fix-ipset-further-reduce-cost-of-entry-overlap-detec.patch
new file mode 100644
index 0000000..c9db4f7
--- /dev/null
+++ b/SOURCES/v1.0.0-0039-fix-ipset-further-reduce-cost-of-entry-overlap-detec.patch
@@ -0,0 +1,150 @@
+From e61807c71c8532cfd23f9946d903beec7f496abc Mon Sep 17 00:00:00 2001
+From: Eric Garver <eric@garver.life>
+Date: Tue, 25 Jan 2022 09:29:32 -0500
+Subject: [PATCH 39/39] fix(ipset): further reduce cost of entry overlap
+ detection
+
+This makes the complexity linear by sorting the networks ahead of time.
+
+Fixes: #881
+Fixes: rhbz2043289
+(cherry picked from commit 36c170db265265e838a089858be4b20dbbd582eb)
+---
+ src/firewall/core/ipset.py | 59 ++++++++++++++++++++++++++++++++---
+ src/tests/regression/gh881.at | 42 ++++++++++++++++++++++---
+ 2 files changed, 92 insertions(+), 9 deletions(-)
+
+diff --git a/src/firewall/core/ipset.py b/src/firewall/core/ipset.py
+index 66ea4335536d..b160d8345669 100644
+--- a/src/firewall/core/ipset.py
++++ b/src/firewall/core/ipset.py
+@@ -327,8 +327,57 @@ def check_for_overlapping_entries(entries):
+ # at least one entry can not be parsed
+ return
+
+- while entries:
+- entry = entries.pop()
+- for itr in entries:
+- if entry.overlaps(itr):
+- raise FirewallError(errors.INVALID_ENTRY, "Entry '{}' overlaps entry '{}'".format(entry, itr))
++ # We can take advantage of some facts of IPv4Network/IPv6Network and
++ # how Python sorts the networks to quickly detect overlaps.
++ #
++ # Facts:
++ #
++ # 1. IPv{4,6}Network are normalized to remove host bits, e.g.
++ # 10.1.1.0/16 will become 10.1.0.0/16.
++ #
++ # 2. IPv{4,6}Network objects are sorted by:
++ # a. IP address (network bits)
++ # then
++ # b. netmask (significant bits count)
++ #
++ # Because of the above we have these properties:
++ #
++ # 1. big networks (netA) are sorted before smaller networks (netB)
++ # that overlap the big network (netA)
++ # - e.g. 10.1.128.0/17 (netA) sorts before 10.1.129.0/24 (netB)
++ # 2. same value addresses (network bits) are grouped together even
++ # if the number of network bits vary. e.g. /16 vs /24
++ # - recall that address are normalized to remove host bits
++ # - e.g. 10.1.128.0/17 (netA) sorts before 10.1.128.0/24 (netC)
++ # 3. non-overlapping networks (netD, netE) are always sorted before or
++ # after networks that overlap (netB, netC) the current one (netA)
++ # - e.g. 10.1.128.0/17 (netA) sorts before 10.2.128.0/16 (netD)
++ # - e.g. 10.1.128.0/17 (netA) sorts after 9.1.128.0/17 (netE)
++ # - e.g. 9.1.128.0/17 (netE) sorts before 10.1.129.0/24 (netB)
++ #
++ # With this we know the sorted list looks like:
++ #
++ # list: [ netE, netA, netB, netC, netD ]
++ #
++ # netE = non-overlapping network
++ # netA = big network
++ # netB = smaller network that overlaps netA (subnet)
++ # netC = smaller network that overlaps netA (subnet)
++ # netD = non-overlapping network
++ #
++ # If networks netB and netC exist in the list, they overlap and are
++ # adjacent to netA.
++ #
++ # Checking for overlaps on a sorted list is thus:
++ #
++ # 1. compare adjacent elements in the list for overlaps
++ #
++ # Recall that we only need to detect a single overlap. We do not need to
++ # detect them all.
++ #
++ entries.sort()
++ prev_network = entries.pop(0)
++ for current_network in entries:
++ if prev_network.overlaps(current_network):
++ raise FirewallError(errors.INVALID_ENTRY, "Entry '{}' overlaps entry '{}'".format(prev_network, current_network))
++ prev_network = current_network
+diff --git a/src/tests/regression/gh881.at b/src/tests/regression/gh881.at
+index c7326805b555..a5cf7e4eb912 100644
+--- a/src/tests/regression/gh881.at
++++ b/src/tests/regression/gh881.at
+@@ -5,21 +5,55 @@ dnl build a large ipset
+ dnl
+ AT_DATA([./deny_cidr], [])
+ NS_CHECK([sh -c '
+-for I in $(seq 10); do
++for I in $(seq 250); do
+ for J in $(seq 250); do
+ echo "10.${I}.${J}.0/24" >> ./deny_cidr
+ done
+ done
+ '])
++NS_CHECK([echo "10.254.0.0/16" >> ./deny_cidr])
+
+ dnl verify non-overlapping does not error
+ dnl
+ FWD_CHECK([--permanent --new-ipset=deny_set --type=hash:net --option=family=inet --option=hashsize=16384 --option=maxelem=20000], 0, [ignore])
+-NS_CHECK([time timeout 300 firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 0, [ignore], [ignore])
++NS_CHECK([time firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 0, [ignore], [ignore])
++
++dnl still no overlap
++dnl
++AT_DATA([./deny_cidr], [
++9.0.0.0/8
++11.1.0.0/16
++])
++NS_CHECK([time firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 0, [ignore], [ignore])
+
+ dnl verify overlap detection actually detects an overlap
+ dnl
+-NS_CHECK([echo "10.1.0.0/16" >> ./deny_cidr])
+-NS_CHECK([time timeout 300 firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 136, [ignore], [ignore])
++AT_DATA([./deny_cidr], [
++10.1.0.0/16
++10.2.0.0/16
++10.250.0.0/16
++])
++NS_CHECK([time firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 136, [ignore], [ignore])
++
++AT_DATA([./deny_cidr], [
++10.253.0.0/16
++10.253.128.0/17
++])
++NS_CHECK([time firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 136, [ignore], [ignore])
++
++AT_DATA([./deny_cidr], [
++10.1.1.1/32
++])
++NS_CHECK([time firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 136, [ignore], [ignore])
++
++AT_DATA([./deny_cidr], [
++10.0.0.0/8
++10.0.0.0/25
++])
++NS_CHECK([time firewall-cmd --permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 136, [ignore], [ignore])
++
++dnl empty file, no additions, but previous ones will remain
++AT_DATA([./deny_cidr], [])
++FWD_CHECK([--permanent --ipset=deny_set --add-entries-from-file=./deny_cidr], 0, [ignore], [ignore])
+
+ FWD_END_TEST()
+--
+2.31.1
+
diff --git a/SPECS/firewalld.spec b/SPECS/firewalld.spec
index 675dd16..af9eb18 100644
--- a/SPECS/firewalld.spec
+++ b/SPECS/firewalld.spec
@@ -1,7 +1,7 @@
Summary: A firewall daemon with D-Bus interface providing a dynamic firewall
Name: firewalld
Version: 0.9.3
-Release: 7%{?dist}
+Release: 7%{?dist}.1
URL: http://www.firewalld.org
License: GPLv2+
Source0: https://github.com/firewalld/firewalld/releases/download/v%{version}/firewalld-%{version}.tar.gz
@@ -41,6 +41,9 @@ Patch33: 0033-fix-policy-warn-instead-of-error-for-overlapping-por.patch
Patch34: 0034-test-zone-verify-overlapping-ports-don-t-halt-zone-l.patch
Patch35: v1.0.0-0035-fix-ipset-normalize-entries-in-CIDR-notation.patch
Patch36: v1.0.0-0036-fix-ipset-disallow-overlapping-entries.patch
+Patch37: v1.0.0-0037-fix-ipset-reduce-cost-of-entry-overlap-detection.patch
+Patch38: v1.0.0-0038-test-ipset-huge-set-of-entries-benchmark.patch
+Patch39: v1.0.0-0039-fix-ipset-further-reduce-cost-of-entry-overlap-detec.patch
BuildArch: noarch
BuildRequires: autoconf
@@ -242,6 +245,9 @@ desktop-file-install --delete-original \
%{_mandir}/man1/firewall-config*.1*
%changelog
+* Thu Feb 03 2022 Eric Garver <egarver@redhat.com> - 0.9.3-7.el8_5.1
+- fix(ipset): reduce cost of entry overlap detection
+
* Tue Jul 13 2021 Eric Garver <egarver@redhat.com> - 0.9.3-7
- fix(ipset): disallow overlapping entries