change that queue ID allocator so it always has the queues sorted by ID.

that allows us to get rid of the "tagid" global which stored the highest
tag ID in use.
when allocating a new ID scan the list for a free slot and only use
highest + 1 on failure instead of using highest + 1 from the beginning
scanning for a dup afterwards. this prevents ID space fragmentation better.

as a result this allows us do get rid of the pf_tag_purge() function
completely and let pf_tag_unref() remove an entry once the reference
counter reaches zero by itself.
after all it makes for easier code and is about 50% faster.

idea came up during a discussion on icb earlier today between cedric and
myself, which itself was particulary inspired by Darren Reed questioning the
need for pf_tag_purge on tech-net@netbsd.

ok dhartmei@ cedric@

3 files changed, 38 insertions, 45 deletions

diff --git a/sys/net/if_bridge.c b/sys/net/if_bridge.c
index 3ef35dd4591..d434c36633d 100644
--- a/sys/net/if_bridge.c
+++ b/sys/net/if_bridge.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_bridge.c,v 1.120 2003/06/30 10:51:09 henning Exp $	*/
+/*	$OpenBSD: if_bridge.c,v 1.121 2003/06/30 19:09:25 henning Exp $	*/
 
 /*
  * Copyright (c) 1999, 2000 Jason L. Wright (jason@thought.net)
@@ -2080,9 +2080,6 @@ bridge_flushrule(struct bridge_iflist *bif)
 #endif
 		free(p, M_DEVBUF);
 	}
-#if NPF > 0
-	pf_tag_purge();
-#endif
 	return (0);
 }
 
diff --git a/sys/net/pf_ioctl.c b/sys/net/pf_ioctl.c
index ef0fbfb5509..bc07c0ae7b0 100644
--- a/sys/net/pf_ioctl.c
+++ b/sys/net/pf_ioctl.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pf_ioctl.c,v 1.74 2003/06/30 17:45:01 dhartmei Exp $ */
+/*	$OpenBSD: pf_ioctl.c,v 1.75 2003/06/30 19:09:25 henning Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -85,7 +85,6 @@ extern struct timeout	 pf_expire_to;
 struct pf_rule		 pf_default_rule;
 
 #define	TAGID_MAX	 50000
-static u_int16_t	 tagid = 0;
 TAILQ_HEAD(pf_tags, pf_tagname)	pf_tags = TAILQ_HEAD_INITIALIZER(pf_tags);
 
 #define DPFPRINTF(n, x) if (pf_status.debug >= (n)) printf x
@@ -423,37 +422,45 @@ pf_rm_rule(struct pf_rulequeue *rulequeue, struct pf_rule *rule)
 u_int16_t
 pf_tagname2tag(char *tagname)
 {
-	struct pf_tagname	*tag, *p;
-	int			 wrapped = 0;
+	struct pf_tagname	*tag, *p = NULL;
+	u_int16_t		 new_tagid = 1;
 
 	TAILQ_FOREACH(tag, &pf_tags, entries)
 		if (strcmp(tagname, tag->name) == 0) {
 			tag->ref++;
 			return (tag->tag);
 		}
+
+	/*
+	 * to avoid fragmentation, we do a linear search from the beginning
+	 * and take the first free slot we find. if there is none or the list
+	 * is empty, append a new entry at the end.
+	 */
+
 	/* new entry */
-	if (++tagid > TAGID_MAX)	/* > 50000 reserved for special use */
-		tagid = wrapped = 1;
-	for (p = TAILQ_FIRST(&pf_tags); p != NULL; p = TAILQ_NEXT(p, entries))
-		if (p->tag == tagid) {
-			if (++tagid > TAGID_MAX) {
-				if (wrapped)
-					return (0);
-				else
-					tagid = wrapped = 1;
-			}
-			p = TAILQ_FIRST(&pf_tags);
-		}
+	if (!TAILQ_EMPTY(&pf_tags))
+		for (p = TAILQ_FIRST(&pf_tags); p != NULL &&
+		    p->tag == new_tagid; p = TAILQ_NEXT(p, entries))
+			new_tagid = p->tag + 1;
 
+	if (new_tagid > TAGID_MAX)
+		return (0);
+
+	/* allocate and fill new struct pf_tagname */
 	tag = (struct pf_tagname *)malloc(sizeof(struct pf_tagname),
 	    M_TEMP, M_NOWAIT);
 	if (tag == NULL)
 		return (0);
 	bzero(tag, sizeof(struct pf_tagname));
 	strlcpy(tag->name, tagname, sizeof(tag->name));
-	tag->tag = tagid;
+	tag->tag = new_tagid;
 	tag->ref++;
-	TAILQ_INSERT_TAIL(&pf_tags, tag, entries);
+
+	if (p != NULL)	/* insert new entry before p */
+		TAILQ_INSERT_BEFORE(p, tag, entries);
+	else	/* either list empty or no free slot in between */
+		TAILQ_INSERT_TAIL(&pf_tags, tag, entries);
+
 	return (tag->tag);
 }
 
@@ -472,28 +479,19 @@ pf_tag2tagname(u_int16_t tagid, char *p)
 void
 pf_tag_unref(u_int16_t tag)
 {
-	struct pf_tagname	*p;
-
-	if (tag > 0)
-		TAILQ_FOREACH(p, &pf_tags, entries)
-			if (tag == p->tag) {
-				p->ref--;
-				return;
-			}
-}
-
-void
-pf_tag_purge(void)
-{
 	struct pf_tagname	*p, *next;
 
-	for (p = TAILQ_LAST(&pf_tags, pf_tags); p != NULL; p = next) {
-		next = TAILQ_PREV(p, pf_tags, entries);
-		if (p->ref == 0) {
-			if (p->tag == tagid)
-				tagid--;
-			TAILQ_REMOVE(&pf_tags, p, entries);
-			free(p, M_TEMP);
+	if (tag == 0)
+		return;
+
+	for (p = TAILQ_FIRST(&pf_tags); p != NULL; p = next) {
+		next = TAILQ_NEXT(p, entries);
+		if (tag == p->tag) {
+			if (--p->ref == 0) {
+				TAILQ_REMOVE(&pf_tags, p, entries);
+				free(p, M_TEMP);
+			}
+			break;
 		}
 	}
 }
@@ -776,7 +774,6 @@ pfioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
 			pf_rm_rule(old_rules, rule);
 		pf_remove_if_empty_ruleset(ruleset);
 		pf_update_anchor_rules();
-		pf_tag_purge();
 		splx(s);
 		break;
 	}
diff --git a/sys/net/pfvar.h b/sys/net/pfvar.h
index 8b16bdb05ab..919f75bdd4a 100644
--- a/sys/net/pfvar.h
+++ b/sys/net/pfvar.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: pfvar.h,v 1.159 2003/06/30 10:50:16 henning Exp $ */
+/*	$OpenBSD: pfvar.h,v 1.160 2003/06/30 19:09:25 henning Exp $ */
 
 /*
  * Copyright (c) 2001 Daniel Hartmeier
@@ -1116,7 +1116,6 @@ int	pfr_ina_define(struct pfr_table *, struct pfr_addr *, int, int *,
 u_int16_t	pf_tagname2tag(char *);
 void		pf_tag2tagname(u_int16_t, char *);
 void		pf_tag_unref(u_int16_t);
-void		pf_tag_purge(void);
 int		pf_tag_packet(struct mbuf *, struct pf_tag *, int);
 
 extern struct pf_status	pf_status;