Hello,
On Wed, Aug 10, 2022 at 02:38:16PM +0000, Stefan Butz wrote:
> Hi everyone,
>
> this mail includes a patch to store pf rules in a red-black tree.
> Currently they are stored in a linked list.
> My system configured with 16000 rules takes about 10 minutes
> to print them out using `pfctl -sr`.
> This patch decreases the time to 4 seconds.
> I was not able to measure a time increase for rule insertion.
> Inserting a lot of labels is still very slow.
> This has to be attacked separatly.
took me while to figure out why it can take sooo loooong
to retrieve 16k rules from kernel. this is the answer
1480 case DIOCGETRULE: {
1496 if (pr->ticket != ruleset->rules.active.ticket) {
1497 error = EBUSY;
1498 PF_UNLOCK();
1499 NET_UNLOCK();
1500 goto fail;
1501 }
1502 rule = TAILQ_FIRST(ruleset->rules.active.ptr);
1503 while ((rule != NULL) && (rule->nr != pr->nr))
1504 rule = TAILQ_NEXT(rule, entries);
1505 if (rule == NULL) {
so yes, in order to retrieve the next rule in list we must
always start with the first (HEAD) rule and iterate to rule n+1.
so I understand a motivation why to solve it using rb-tree.
I also (as todd) have some doubts about code in DIOCHANGERULE.
the current code is able to insert to desired location.
I don't understand how your new code does that:
1675
1676 if (pcr->action == PF_CHANGE_ADD_HEAD)
1677 oldrule = RB_MIN(pf_ruletree,
1678 ruleset->rules.active.ptr);
1679 else if (pcr->action == PF_CHANGE_ADD_TAIL)
1680 oldrule = RB_MAX(pf_ruletree,
1681 ruleset->rules.active.ptr);
1682 else {
1683 oldrule = RB_MIN(pf_ruletree,
1684 ruleset->rules.active.ptr);
1685 while ((oldrule != NULL) && (oldrule->nr !=
pcr->nr))
1686 oldrule = RB_NEXT(pf_ruletree,
1687 ruleset->rules.active.ptr, oldrule);
1688 if (oldrule == NULL) {
1689 if (newrule != NULL)
1690 pf_rm_rule(NULL, newrule);
1691 error = EINVAL;
1692 PF_UNLOCK();
1693 NET_UNLOCK();
1694 goto fail;
1695 }
1696 }
1697
1698 if (pcr->action == PF_CHANGE_REMOVE) {
1699 pf_rm_rule(ruleset->rules.active.ptr, oldrule);
1700 ruleset->rules.active.rcount--;
1701 } else {
1702 RB_INSERT(pf_ruletree,
1703 ruleset->rules.active.ptr, newrule);
1704 ruleset->rules.active.rcount++;
1705 newrule->ruleset = ruleset;
1706 }
1707
how does RB_INSERT() at line 1702 insert rule to
desired location. Consider the current rules look like:
[ 1, 2, 3, 4 ]
i'm going to insert rule x, which should follow existing rule nr 3
[ 1, 2, 3, x, 4]
current code just re-indexes/renumbers the rules after insertion
[ 1, 2, 3, 4, 5 ], where x gets assigned 4.
I don't see how does that happen with RB_INSERT().
I think what we really need to fix is the iteration to n-th retrieved
rule we currently have in DIOCGETRULE. I'm working on slightly large
change which updates pf(4) transactions. I'll try to cherry pick
some changes from my in-progress tree and factor out a smaller diff
which will solve that DIOCGETRULE itch for you. please stay tuned.
thanks and
regards
sashan
