move pf from RB macros to RBT code

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

move pf from RB macros to RBT code

David Gwynne-5
the subject says it all.  this is largely mechanical.

ok?

Index: if_pfsync.c
===================================================================
RCS file: /cvs/src/sys/net/if_pfsync.c,v
retrieving revision 1.232
diff -u -p -r1.232 if_pfsync.c
--- if_pfsync.c 21 Sep 2016 07:41:49 -0000 1.232
+++ if_pfsync.c 26 Sep 2016 10:26:29 -0000
@@ -747,8 +748,8 @@ pfsync_in_clr(caddr_t buf, int len, int
     (kif = pfi_kif_find(clr->ifname)) == NULL)
  continue;
 
- for (st = RB_MIN(pf_state_tree_id, &tree_id); st; st = nexts) {
- nexts = RB_NEXT(pf_state_tree_id, &tree_id, st);
+ for (st = RBT_MIN(pf_state_tree_id, &tree_id); st; st = nexts) {
+ nexts = RBT_NEXT(pf_state_tree_id, st);
  if (st->creatorid == creatorid &&
     ((kif && st->kif == kif) || !kif)) {
  SET(st->state_flags, PFSTATE_NOSYNC);
Index: pf.c
===================================================================
RCS file: /cvs/src/sys/net/pf.c,v
retrieving revision 1.985
diff -u -p -r1.985 pf.c
--- pf.c 22 Sep 2016 10:50:19 -0000 1.985
+++ pf.c 26 Sep 2016 10:26:29 -0000
@@ -293,11 +294,12 @@ struct pf_pool_limit pf_pool_limits[PF_L
  mrm->r->states_cur++; \
  } while (0)
 
-static __inline int pf_src_compare(struct pf_src_node *, struct pf_src_node *);
-static __inline int pf_state_compare_key(struct pf_state_key *,
- struct pf_state_key *);
-static __inline int pf_state_compare_id(struct pf_state *,
- struct pf_state *);
+static __inline int pf_src_compare(const struct pf_src_node *,
+ const struct pf_src_node *);
+static __inline int pf_state_compare_key(const struct pf_state_key *,
+ const struct pf_state_key *);
+static __inline int pf_state_compare_id(const struct pf_state *,
+ const struct pf_state *);
 static __inline void pf_cksum_uncover(u_int16_t *, u_int16_t, u_int8_t);
 static __inline void pf_cksum_cover(u_int16_t *, u_int16_t, u_int8_t);
 
@@ -306,16 +308,17 @@ struct pf_src_tree tree_src_tracking;
 struct pf_state_tree_id tree_id;
 struct pf_state_queue state_list;
 
-RB_GENERATE(pf_src_tree, pf_src_node, entry, pf_src_compare);
-RB_GENERATE(pf_state_tree, pf_state_key, entry, pf_state_compare_key);
-RB_GENERATE(pf_state_tree_id, pf_state,
+RBT_GENERATE(pf_src_tree, pf_src_node, entry, pf_src_compare);
+RBT_GENERATE(pf_state_tree, pf_state_key, entry, pf_state_compare_key);
+RBT_GENERATE(pf_state_tree_id, pf_state,
     entry_id, pf_state_compare_id);
 
 SLIST_HEAD(pf_rule_gcl, pf_rule) pf_rule_gcl =
  SLIST_HEAD_INITIALIZER(pf_rule_gcl);
 
 __inline int
-pf_addr_compare(struct pf_addr *a, struct pf_addr *b, sa_family_t af)
+pf_addr_compare(const struct pf_addr *a, const struct pf_addr *b,
+    sa_family_t af)
 {
  switch (af) {
  case AF_INET:
@@ -349,7 +352,7 @@ pf_addr_compare(struct pf_addr *a, struc
 }
 
 static __inline int
-pf_src_compare(struct pf_src_node *a, struct pf_src_node *b)
+pf_src_compare(const struct pf_src_node *a, const struct pf_src_node *b)
 {
  int diff;
 
@@ -480,7 +483,7 @@ pf_src_connlimit(struct pf_state **state
  struct pf_state *st;
 
  pf_status.lcounters[LCNT_OVERLOAD_FLUSH]++;
- RB_FOREACH(st, pf_state_tree_id, &tree_id) {
+ RBT_FOREACH(st, pf_state_tree_id, &tree_id) {
  sk = st->key[PF_SK_WIRE];
  /*
  * Kill states from this source.  (Only those
@@ -528,7 +531,7 @@ pf_insert_src_node(struct pf_src_node **
  PF_ACPY(&k.addr, src, af);
  k.rule.ptr = rule;
  pf_status.scounters[SCNT_SRC_NODE_SEARCH]++;
- *sn = RB_FIND(pf_src_tree, &tree_src_tracking, &k);
+ *sn = RBT_FIND(pf_src_tree, &tree_src_tracking, &k);
  }
  if (*sn == NULL) {
  if (!rule->max_src_nodes ||
@@ -549,7 +552,7 @@ pf_insert_src_node(struct pf_src_node **
  PF_ACPY(&(*sn)->addr, src, af);
  if (raddr)
  PF_ACPY(&(*sn)->raddr, raddr, af);
- if (RB_INSERT(pf_src_tree,
+ if (RBT_INSERT(pf_src_tree,
     &tree_src_tracking, *sn) != NULL) {
  if (pf_status.debug >= LOG_NOTICE) {
  log(LOG_NOTICE,
@@ -584,7 +587,7 @@ pf_remove_src_node(struct pf_src_node *s
  if (sn->rule.ptr->states_cur == 0 &&
     sn->rule.ptr->src_nodes == 0)
  pf_rm_rule(NULL, sn->rule.ptr);
- RB_REMOVE(pf_src_tree, &tree_src_tracking, sn);
+ RBT_REMOVE(pf_src_tree, &tree_src_tracking, sn);
  pf_status.scounters[SCNT_SRC_NODE_REMOVALS]++;
  pf_status.src_nodes--;
  pool_put(&pf_src_tree_pl, sn);
@@ -625,7 +628,7 @@ pf_state_rm_src_node(struct pf_state *s,
 /* state table stuff */
 
 static __inline int
-pf_state_compare_key(struct pf_state_key *a, struct pf_state_key *b)
+pf_state_compare_key(const struct pf_state_key *a, const struct pf_state_key *b)
 {
  int diff;
 
@@ -647,7 +650,7 @@ pf_state_compare_key(struct pf_state_key
 }
 
 static __inline int
-pf_state_compare_id(struct pf_state *a, struct pf_state *b)
+pf_state_compare_id(const struct pf_state *a, const struct pf_state *b)
 {
  if (a->id > b->id)
  return (1);
@@ -669,7 +672,7 @@ pf_state_key_attach(struct pf_state_key
  struct pf_state *olds = NULL;
 
  KASSERT(s->key[idx] == NULL);
- if ((cur = RB_INSERT(pf_state_tree, &pf_statetbl, sk)) != NULL) {
+ if ((cur = RBT_INSERT(pf_state_tree, &pf_statetbl, sk)) != NULL) {
  /* key exists. check for same kif, if none, add to key */
  TAILQ_FOREACH(si, &cur->states, entry)
  if (si->s->kif == s->kif &&
@@ -768,7 +771,7 @@ pf_state_key_detach(struct pf_state *s,
  sk = s->key[idx];
  s->key[idx] = NULL;
  if (TAILQ_EMPTY(&sk->states)) {
- RB_REMOVE(pf_state_tree, &pf_statetbl, sk);
+ RBT_REMOVE(pf_state_tree, &pf_statetbl, sk);
  sk->removed = 1;
  pf_state_key_unlink_reverse(sk);
  pf_inpcb_unlink_state_key(sk->inp);
@@ -944,7 +947,7 @@ pf_state_insert(struct pfi_kif *kif, str
  s->id = htobe64(pf_status.stateid++);
  s->creatorid = pf_status.hostid;
  }
- if (RB_INSERT(pf_state_tree_id, &tree_id, s) != NULL) {
+ if (RBT_INSERT(pf_state_tree_id, &tree_id, s) != NULL) {
  if (pf_status.debug >= LOG_NOTICE) {
  log(LOG_NOTICE, "pf: state insert failed: "
     "id: %016llx creatorid: %08x",
@@ -969,7 +972,7 @@ pf_find_state_byid(struct pf_state_cmp *
 {
  pf_status.fcounters[FCNT_STATE_SEARCH]++;
 
- return (RB_FIND(pf_state_tree_id, &tree_id, (struct pf_state *)key));
+ return (RBT_FIND(pf_state_tree_id, &tree_id, (struct pf_state *)key));
 }
 
 int
@@ -1048,7 +1051,7 @@ pf_find_state(struct pfi_kif *kif, struc
  }
 
  if (sk == NULL) {
- if ((sk = RB_FIND(pf_state_tree, &pf_statetbl,
+ if ((sk = RBT_FIND(pf_state_tree, &pf_statetbl,
     (struct pf_state_key *)key)) == NULL)
  return (NULL);
  if (dir == PF_OUT && pkt_sk &&
@@ -1084,7 +1087,7 @@ pf_find_state_all(struct pf_state_key_cm
 
  pf_status.fcounters[FCNT_STATE_SEARCH]++;
 
- sk = RB_FIND(pf_state_tree, &pf_statetbl, (struct pf_state_key *)key);
+ sk = RBT_FIND(pf_state_tree, &pf_statetbl, (struct pf_state_key *)key);
 
  if (sk != NULL) {
  TAILQ_FOREACH(si, &sk->states, entry)
@@ -1269,14 +1272,13 @@ pf_purge_expired_src_nodes(int waslocked
  struct pf_src_node *cur, *next;
  int locked = waslocked;
 
- for (cur = RB_MIN(pf_src_tree, &tree_src_tracking); cur; cur = next) {
- next = RB_NEXT(pf_src_tree, &tree_src_tracking, cur);
+ for (cur = RBT_MIN(pf_src_tree, &tree_src_tracking); cur; cur = next) {
+ next = RBT_NEXT(pf_src_tree, cur);
 
  if (cur->states == 0 && cur->expire <= time_uptime) {
  if (! locked) {
  rw_enter_write(&pf_consistency_lock);
- next = RB_NEXT(pf_src_tree,
-    &tree_src_tracking, cur);
+ next = RBT_NEXT(pf_src_tree, cur);
  locked = 1;
  }
  pf_remove_src_node(cur);
@@ -1327,7 +1329,7 @@ pf_remove_state(struct pf_state *cur)
     TH_RST|TH_ACK, 0, 0, 0, 1, cur->tag,
     cur->key[PF_SK_WIRE]->rdomain);
  }
- RB_REMOVE(pf_state_tree_id, &tree_id, cur);
+ RBT_REMOVE(pf_state_tree_id, &tree_id, cur);
 #if NPFLOW > 0
  if (cur->state_flags & PFSTATE_PFLOW)
  export_pflow(cur);
@@ -3025,7 +3027,7 @@ pf_step_into_anchor(int *depth, struct p
  f->r = *r;
  if ((*r)->anchor_wildcard) {
  f->parent = &(*r)->anchor->children;
- if ((f->child = RB_MIN(pf_anchor_node, f->parent)) == NULL) {
+ if ((f->child = RBT_MIN(pf_anchor_node, f->parent)) == NULL) {
  *r = NULL;
  return;
  }
@@ -3050,7 +3052,7 @@ pf_step_out_of_anchor(int *depth, struct
  break;
  f = pf_anchor_stack + *depth - 1;
  if (f->parent != NULL && f->child != NULL) {
- f->child = RB_NEXT(pf_anchor_node, f->parent, f->child);
+ f->child = RBT_NEXT(pf_anchor_node, f->child);
  if (f->child != NULL) {
  *rs = &f->child->ruleset;
  *r = TAILQ_FIRST((*rs)->rules.active.ptr);
Index: pf_if.c
===================================================================
RCS file: /cvs/src/sys/net/pf_if.c,v
retrieving revision 1.84
diff -u -p -r1.84 pf_if.c
--- pf_if.c 15 Sep 2016 02:00:18 -0000 1.84
+++ pf_if.c 26 Sep 2016 10:26:29 -0000
@@ -72,12 +72,12 @@ void pfi_table_update(struct pfr_ktabl
 void pfi_kifaddr_update(void *);
 void pfi_instance_add(struct ifnet *, u_int8_t, int);
 void pfi_address_add(struct sockaddr *, sa_family_t, u_int8_t);
-int pfi_if_compare(struct pfi_kif *, struct pfi_kif *);
+int pfi_if_compare(const struct pfi_kif *, const struct pfi_kif *);
 int pfi_skip_if(const char *, struct pfi_kif *);
 int pfi_unmask(void *);
 
-RB_PROTOTYPE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare);
-RB_GENERATE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare);
+RBT_PROTOTYPE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare);
+RBT_GENERATE(pfi_ifhead, pfi_kif, pfik_tree, pfi_if_compare);
 
 #define PFI_BUFFER_MAX 0x10000
 #define PFI_MTYPE M_IFADDR
@@ -105,7 +105,7 @@ pfi_kif_find(const char *kif_name)
 
  bzero(&s, sizeof(s));
  strlcpy(s.pfik_name, kif_name, sizeof(s.pfik_name));
- return (RB_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&s));
+ return (RBT_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&s));
 }
 
 struct pfi_kif *
@@ -130,7 +130,7 @@ pfi_kif_get(const char *kif_name)
  kif->pfik_flags_new |= PFI_IFLAG_ANY;
  }
 
- RB_INSERT(pfi_ifhead, &pfi_ifs, kif);
+ RBT_INSERT(pfi_ifhead, &pfi_ifs, kif);
  return (kif);
 }
 
@@ -195,7 +195,7 @@ pfi_kif_unref(struct pfi_kif *kif, enum
  if (kif->pfik_rules || kif->pfik_states || kif->pfik_routes)
  return;
 
- RB_REMOVE(pfi_ifhead, &pfi_ifs, kif);
+ RBT_REMOVE(pfi_ifhead, &pfi_ifs, kif);
  free(kif, PFI_MTYPE, 0);
 }
 
@@ -628,7 +628,7 @@ pfi_kifaddr_update(void *v)
 }
 
 int
-pfi_if_compare(struct pfi_kif *p, struct pfi_kif *q)
+pfi_if_compare(const struct pfi_kif *p, const struct pfi_kif *q)
 {
  return (strncmp(p->pfik_name, q->pfik_name, IFNAMSIZ));
 }
@@ -644,7 +644,7 @@ pfi_update_status(const char *name, stru
 
  s = splsoftnet();
  if (*name == '\0' && pfs == NULL) {
- RB_FOREACH(p, pfi_ifhead, &pfi_ifs) {
+ RBT_FOREACH(p, pfi_ifhead, &pfi_ifs) {
  bzero(p->pfik_packets, sizeof(p->pfik_packets));
  bzero(p->pfik_bytes, sizeof(p->pfik_bytes));
  p->pfik_tzero = time_second;
@@ -654,7 +654,7 @@ pfi_update_status(const char *name, stru
  }
 
  strlcpy(key.pfik_name, name, sizeof(key.pfik_name));
- p = RB_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&key);
+ p = RBT_FIND(pfi_ifhead, &pfi_ifs, (struct pfi_kif *)&key);
  if (p == NULL) {
  splx(s);
  return;
@@ -704,8 +704,8 @@ pfi_get_ifaces(const char *name, struct
  int s, n = 0;
 
  s = splsoftnet();
- for (p = RB_MIN(pfi_ifhead, &pfi_ifs); p; p = nextp) {
- nextp = RB_NEXT(pfi_ifhead, &pfi_ifs, p);
+ for (p = RBT_MIN(pfi_ifhead, &pfi_ifs); p; p = nextp) {
+ nextp = RBT_NEXT(pfi_ifhead, p);
  if (pfi_skip_if(name, p))
  continue;
  if (*size > n++) {
@@ -717,7 +717,7 @@ pfi_get_ifaces(const char *name, struct
  splx(s);
  return (EFAULT);
  }
- nextp = RB_NEXT(pfi_ifhead, &pfi_ifs, p);
+ nextp = RBT_NEXT(pfi_ifhead, p);
  pfi_kif_unref(p, PFI_KIF_REF_RULE);
  }
  }
@@ -755,7 +755,7 @@ pfi_set_flags(const char *name, int flag
  int s;
 
  s = splsoftnet();
- RB_FOREACH(p, pfi_ifhead, &pfi_ifs) {
+ RBT_FOREACH(p, pfi_ifhead, &pfi_ifs) {
  if (pfi_skip_if(name, p))
  continue;
  p->pfik_flags_new = p->pfik_flags | flags;
@@ -771,7 +771,7 @@ pfi_clear_flags(const char *name, int fl
  int s;
 
  s = splsoftnet();
- RB_FOREACH(p, pfi_ifhead, &pfi_ifs) {
+ RBT_FOREACH(p, pfi_ifhead, &pfi_ifs) {
  if (pfi_skip_if(name, p))
  continue;
  p->pfik_flags_new = p->pfik_flags & ~flags;
@@ -787,7 +787,7 @@ pfi_xcommit(void)
  int s;
 
  s = splsoftnet();
- RB_FOREACH(p, pfi_ifhead, &pfi_ifs)
+ RBT_FOREACH(p, pfi_ifhead, &pfi_ifs)
  p->pfik_flags = p->pfik_flags_new;
  splx(s);
 }
Index: pf_ioctl.c
===================================================================
RCS file: /cvs/src/sys/net/pf_ioctl.c,v
retrieving revision 1.300
diff -u -p -r1.300 pf_ioctl.c
--- pf_ioctl.c 15 Sep 2016 02:00:18 -0000 1.300
+++ pf_ioctl.c 26 Sep 2016 10:26:29 -0000
@@ -169,8 +169,8 @@ pfattach(int num)
  pf_pool_limits[PF_LIMIT_TABLE_ENTRIES].limit =
     PFR_KENTRY_HIWAT_SMALL;
 
- RB_INIT(&tree_src_tracking);
- RB_INIT(&pf_anchors);
+ RBT_INIT(pf_src_tree, &tree_src_tracking);
+ RBT_INIT(pf_anchor_global, &pf_anchors);
  pf_init_ruleset(&pf_main_ruleset);
  TAILQ_INIT(&pf_queues[0]);
  TAILQ_INIT(&pf_queues[1]);
@@ -1418,8 +1418,8 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
  struct pfioc_state_kill *psk = (struct pfioc_state_kill *)addr;
  u_int killed = 0;
 
- for (s = RB_MIN(pf_state_tree_id, &tree_id); s; s = nexts) {
- nexts = RB_NEXT(pf_state_tree_id, &tree_id, s);
+ for (s = RBT_MIN(pf_state_tree_id, &tree_id); s; s = nexts) {
+ nexts = RBT_NEXT(pf_state_tree_id, s);
 
  if (!psk->psk_ifname[0] || !strcmp(psk->psk_ifname,
     s->kif->pfik_name)) {
@@ -1456,9 +1456,8 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
  break;
  }
 
- for (s = RB_MIN(pf_state_tree_id, &tree_id); s;
-    s = nexts) {
- nexts = RB_NEXT(pf_state_tree_id, &tree_id, s);
+ for (s = RBT_MIN(pf_state_tree_id, &tree_id); s; s = nexts) {
+ nexts = RBT_NEXT(pf_state_tree_id, s);
 
  if (s->direction == PF_OUT) {
  sk = s->key[PF_SK_STACK];
@@ -1754,11 +1753,11 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
  pr->nr = 0;
  if (ruleset->anchor == NULL) {
  /* XXX kludge for pf_main_ruleset */
- RB_FOREACH(anchor, pf_anchor_global, &pf_anchors)
+ RBT_FOREACH(anchor, pf_anchor_global, &pf_anchors)
  if (anchor->parent == NULL)
  pr->nr++;
  } else {
- RB_FOREACH(anchor, pf_anchor_node,
+ RBT_FOREACH(anchor, pf_anchor_node,
     &ruleset->anchor->children)
  pr->nr++;
  }
@@ -1779,14 +1778,14 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
  pr->name[0] = 0;
  if (ruleset->anchor == NULL) {
  /* XXX kludge for pf_main_ruleset */
- RB_FOREACH(anchor, pf_anchor_global, &pf_anchors)
+ RBT_FOREACH(anchor, pf_anchor_global, &pf_anchors)
  if (anchor->parent == NULL && nr++ == pr->nr) {
  strlcpy(pr->name, anchor->name,
     sizeof(pr->name));
  break;
  }
  } else {
- RB_FOREACH(anchor, pf_anchor_node,
+ RBT_FOREACH(anchor, pf_anchor_node,
     &ruleset->anchor->children)
  if (nr++ == pr->nr) {
  strlcpy(pr->name, anchor->name,
@@ -2236,7 +2235,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
  int space = psn->psn_len;
 
  if (space == 0) {
- RB_FOREACH(n, pf_src_tree, &tree_src_tracking)
+ RBT_FOREACH(n, pf_src_tree, &tree_src_tracking)
  nr++;
  psn->psn_len = sizeof(struct pf_src_node) * nr;
  break;
@@ -2245,7 +2244,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
  pstore = malloc(sizeof(*pstore), M_TEMP, M_WAITOK);
 
  p = psn->psn_src_nodes;
- RB_FOREACH(n, pf_src_tree, &tree_src_tracking) {
+ RBT_FOREACH(n, pf_src_tree, &tree_src_tracking) {
  int secs = time_uptime, diff;
 
  if ((nr + 1) * sizeof(*p) > (unsigned)psn->psn_len)
@@ -2289,9 +2288,9 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
  struct pf_src_node *n;
  struct pf_state *state;
 
- RB_FOREACH(state, pf_state_tree_id, &tree_id)
+ RBT_FOREACH(state, pf_state_tree_id, &tree_id)
  pf_src_tree_remove_state(state);
- RB_FOREACH(n, pf_src_tree, &tree_src_tracking)
+ RBT_FOREACH(n, pf_src_tree, &tree_src_tracking)
  n->expire = 1;
  pf_purge_expired_src_nodes(1);
  break;
@@ -2304,7 +2303,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
     (struct pfioc_src_node_kill *)addr;
  u_int killed = 0;
 
- RB_FOREACH(sn, pf_src_tree, &tree_src_tracking) {
+ RBT_FOREACH(sn, pf_src_tree, &tree_src_tracking) {
  if (PF_MATCHA(psnk->psnk_src.neg,
  &psnk->psnk_src.addr.v.a.addr,
  &psnk->psnk_src.addr.v.a.mask,
@@ -2315,7 +2314,7 @@ pfioctl(dev_t dev, u_long cmd, caddr_t a
  &sn->raddr, sn->af)) {
  /* Handle state to src_node linkage */
  if (sn->states != 0)
- RB_FOREACH(s, pf_state_tree_id,
+ RBT_FOREACH(s, pf_state_tree_id,
    &tree_id)
  pf_state_rm_src_node(s, sn);
  sn->expire = 1;
Index: pf_lb.c
===================================================================
RCS file: /cvs/src/sys/net/pf_lb.c,v
retrieving revision 1.55
diff -u -p -r1.55 pf_lb.c
--- pf_lb.c 19 Jul 2016 12:51:19 -0000 1.55
+++ pf_lb.c 26 Sep 2016 10:26:29 -0000
@@ -275,7 +275,7 @@ pf_map_addr_sticky(sa_family_t af, struc
  PF_ACPY(&k.addr, saddr, af);
  k.rule.ptr = r;
  pf_status.scounters[SCNT_SRC_NODE_SEARCH]++;
- sns[type] = RB_FIND(pf_src_tree, &tree_src_tracking, &k);
+ sns[type] = RBT_FIND(pf_src_tree, &tree_src_tracking, &k);
  if (sns[type] == NULL)
  return (-1);
 
@@ -307,7 +307,7 @@ pf_map_addr_sticky(sa_family_t af, struc
  }
  if (sns[type]->states != 0) {
  /* XXX expensive */
- RB_FOREACH(s, pf_state_tree_id,
+ RBT_FOREACH(s, pf_state_tree_id,
    &tree_id)
  pf_state_rm_src_node(s,
     sns[type]);
Index: pf_norm.c
===================================================================
RCS file: /cvs/src/sys/net/pf_norm.c,v
retrieving revision 1.192
diff -u -p -r1.192 pf_norm.c
--- pf_norm.c 15 Sep 2016 02:00:18 -0000 1.192
+++ pf_norm.c 26 Sep 2016 10:26:29 -0000
@@ -74,7 +74,7 @@ struct pf_frent {
  u_int16_t fe_mff; /* more fragment flag */
 };
 
-/* keep synced with struct pf_fragment, used in RB_FIND */
+/* keep synced with struct pf_fragment, used in RBT_FIND */
 struct pf_fragment_cmp {
  struct pf_addr fr_src;
  struct pf_addr fr_dst;
@@ -92,7 +92,7 @@ struct pf_fragment {
  u_int8_t fr_proto; /* protocol of this fragment */
  u_int8_t fr_direction; /* pf packet direction */
 
- RB_ENTRY(pf_fragment) fr_entry;
+ RBT_ENTRY(pf_fragment) fr_entry;
  TAILQ_ENTRY(pf_fragment) frag_next;
  TAILQ_HEAD(pf_fragq, pf_frent) fr_queue;
  int32_t fr_timeout;
@@ -107,11 +107,11 @@ struct pf_fragment_tag {
 
 TAILQ_HEAD(pf_fragqueue, pf_fragment) pf_fragqueue;
 
-static __inline int pf_frag_compare(struct pf_fragment *,
-    struct pf_fragment *);
-RB_HEAD(pf_frag_tree, pf_fragment) pf_frag_tree, pf_cache_tree;
-RB_PROTOTYPE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare);
-RB_GENERATE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare);
+static __inline int pf_frag_compare(const struct pf_fragment *,
+    const struct pf_fragment *);
+RBT_HEAD(pf_frag_tree, pf_fragment) pf_frag_tree, pf_cache_tree;
+RBT_PROTOTYPE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare);
+RBT_GENERATE(pf_frag_tree, pf_fragment, fr_entry, pf_frag_compare);
 
 /* Private prototypes */
 void pf_flush_fragments(void);
@@ -151,7 +151,7 @@ pf_normalize_init(void)
 }
 
 static __inline int
-pf_frag_compare(struct pf_fragment *a, struct pf_fragment *b)
+pf_frag_compare(const struct pf_fragment *a, const struct pf_fragment *b)
 {
  int diff;
 
@@ -211,7 +211,7 @@ pf_free_fragment(struct pf_fragment *fra
 {
  struct pf_frent *frent;
 
- RB_REMOVE(pf_frag_tree, &pf_frag_tree, frag);
+ RBT_REMOVE(pf_frag_tree, &pf_frag_tree, frag);
  TAILQ_REMOVE(&pf_fragqueue, frag, frag_next);
 
  /* Free all fragment entries */
@@ -229,7 +229,7 @@ pf_find_fragment(struct pf_fragment_cmp
 {
  struct pf_fragment *frag;
 
- frag = RB_FIND(pf_frag_tree, tree, (struct pf_fragment *)key);
+ frag = RBT_FIND(pf_frag_tree, tree, (struct pf_fragment *)key);
  if (frag != NULL) {
  TAILQ_REMOVE(&pf_fragqueue, frag, frag_next);
  TAILQ_INSERT_HEAD(&pf_fragqueue, frag, frag_next);
@@ -309,7 +309,7 @@ pf_fillup_fragment(struct pf_fragment_cm
  frag->fr_timeout = time_uptime;
  frag->fr_maxlen = frent->fe_len;
 
- RB_INSERT(pf_frag_tree, &pf_frag_tree, frag);
+ RBT_INSERT(pf_frag_tree, &pf_frag_tree, frag);
  TAILQ_INSERT_HEAD(&pf_fragqueue, frag, frag_next);
 
  /* We do not have a previous fragment */
Index: pf_ruleset.c
===================================================================
RCS file: /cvs/src/sys/net/pf_ruleset.c,v
retrieving revision 1.12
diff -u -p -r1.12 pf_ruleset.c
--- pf_ruleset.c 19 Jul 2016 13:34:12 -0000 1.12
+++ pf_ruleset.c 26 Sep 2016 10:26:29 -0000
@@ -79,13 +79,14 @@
 struct pf_anchor_global pf_anchors;
 struct pf_anchor pf_main_anchor;
 
-static __inline int pf_anchor_compare(struct pf_anchor *, struct pf_anchor *);
+static __inline int pf_anchor_compare(const struct pf_anchor *,
+    const struct pf_anchor *);
 
-RB_GENERATE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare);
-RB_GENERATE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare);
+RBT_GENERATE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare);
+RBT_GENERATE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare);
 
 static __inline int
-pf_anchor_compare(struct pf_anchor *a, struct pf_anchor *b)
+pf_anchor_compare(const struct pf_anchor *a, const struct pf_anchor *b)
 {
  int c = strcmp(a->path, b->path);
 
@@ -111,7 +112,7 @@ pf_find_anchor(const char *path)
  if (key == NULL)
  return (NULL);
  strlcpy(key->path, path, sizeof(key->path));
- found = RB_FIND(pf_anchor_global, &pf_anchors, key);
+ found = RBT_FIND(pf_anchor_global, &pf_anchors, key);
  rs_free(key);
  return (found);
 }
@@ -180,7 +181,7 @@ pf_find_or_create_ruleset(const char *pa
  rs_free(p);
  return (NULL);
  }
- RB_INIT(&anchor->children);
+ RBT_INIT(pf_anchor_node, &anchor->children);
  strlcpy(anchor->name, q, sizeof(anchor->name));
  if (parent != NULL) {
  strlcpy(anchor->path, parent->path,
@@ -188,10 +189,10 @@ pf_find_or_create_ruleset(const char *pa
  strlcat(anchor->path, "/", sizeof(anchor->path));
  }
  strlcat(anchor->path, anchor->name, sizeof(anchor->path));
- if ((dup = RB_INSERT(pf_anchor_global, &pf_anchors, anchor)) !=
+ if ((dup = RBT_INSERT(pf_anchor_global, &pf_anchors, anchor)) !=
     NULL) {
  DPFPRINTF(LOG_NOTICE,
-    "pf_find_or_create_ruleset: RB_INSERT1 "
+    "pf_find_or_create_ruleset: RBT_INSERT1 "
     "'%s' '%s' collides with '%s' '%s'",
     anchor->path, anchor->name, dup->path, dup->name);
  rs_free(anchor);
@@ -200,14 +201,14 @@ pf_find_or_create_ruleset(const char *pa
  }
  if (parent != NULL) {
  anchor->parent = parent;
- if ((dup = RB_INSERT(pf_anchor_node, &parent->children,
+ if ((dup = RBT_INSERT(pf_anchor_node, &parent->children,
     anchor)) != NULL) {
  DPFPRINTF(LOG_NOTICE,
     "pf_find_or_create_ruleset: "
-    "RB_INSERT2 '%s' '%s' collides with "
+    "RBT_INSERT2 '%s' '%s' collides with "
     "'%s' '%s'", anchor->path, anchor->name,
     dup->path, dup->name);
- RB_REMOVE(pf_anchor_global, &pf_anchors,
+ RBT_REMOVE(pf_anchor_global, &pf_anchors,
     anchor);
  rs_free(anchor);
  rs_free(p);
@@ -233,7 +234,7 @@ pf_remove_if_empty_ruleset(struct pf_rul
 
  while (ruleset != NULL) {
  if (ruleset == &pf_main_ruleset || ruleset->anchor == NULL ||
-    !RB_EMPTY(&ruleset->anchor->children) ||
+    !RBT_EMPTY(pf_anchor_node, &ruleset->anchor->children) ||
     ruleset->anchor->refcnt > 0 || ruleset->tables > 0 ||
     ruleset->topen)
  return;
@@ -241,9 +242,9 @@ pf_remove_if_empty_ruleset(struct pf_rul
     !TAILQ_EMPTY(ruleset->rules.inactive.ptr) ||
     ruleset->rules.inactive.open)
  return;
- RB_REMOVE(pf_anchor_global, &pf_anchors, ruleset->anchor);
+ RBT_REMOVE(pf_anchor_global, &pf_anchors, ruleset->anchor);
  if ((parent = ruleset->anchor->parent) != NULL)
- RB_REMOVE(pf_anchor_node, &parent->children,
+ RBT_REMOVE(pf_anchor_node, &parent->children,
     ruleset->anchor);
  rs_free(ruleset->anchor);
  if (parent == NULL)
Index: pf_table.c
===================================================================
RCS file: /cvs/src/sys/net/pf_table.c,v
retrieving revision 1.118
diff -u -p -r1.118 pf_table.c
--- pf_table.c 15 Sep 2016 02:00:18 -0000 1.118
+++ pf_table.c 26 Sep 2016 10:26:29 -0000
@@ -177,8 +177,8 @@ struct pfr_ktable *pfr_create_ktable(str
     int);
 void pfr_destroy_ktables(struct pfr_ktableworkq *, int);
 void pfr_destroy_ktable(struct pfr_ktable *, int);
-int pfr_ktable_compare(struct pfr_ktable *,
-    struct pfr_ktable *);
+int pfr_ktable_compare(const struct pfr_ktable *,
+    const struct pfr_ktable *);
 void pfr_ktable_winfo_update(struct pfr_ktable *,
     struct pfr_kentry *);
 struct pfr_ktable *pfr_lookup_table(struct pfr_table *);
@@ -190,8 +190,8 @@ int pfr_skip_table(struct pfr_table *
 struct pfr_kentry *pfr_kentry_byidx(struct pfr_ktable *, int, int);
 int pfr_islinklocal(sa_family_t, struct pf_addr *);
 
-RB_PROTOTYPE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare);
-RB_GENERATE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare);
+RBT_PROTOTYPE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare);
+RBT_GENERATE(pfr_ktablehead, pfr_ktable, pfrkt_tree, pfr_ktable_compare);
 
 struct pfr_ktablehead pfr_ktables;
 struct pfr_table pfr_nulltable;
@@ -1273,7 +1273,7 @@ pfr_clr_tables(struct pfr_table *filter,
  return (ENOENT);
 
  SLIST_INIT(&workq);
- RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+ RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
  if (pfr_skip_table(filter, p, flags))
  continue;
  if (!strcmp(p->pfrkt_anchor, PF_RESERVED_ANCHOR))
@@ -1311,7 +1311,7 @@ pfr_add_tables(struct pfr_table *tbl, in
     flags & PFR_FLAG_USERIOCTL))
  senderr(EINVAL);
  key.pfrkt_flags |= PFR_TFLAG_ACTIVE;
- p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+ p = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
  if (p == NULL) {
  p = pfr_create_ktable(&key.pfrkt_t, tzero, 1,
     !(flags & PFR_FLAG_USERIOCTL));
@@ -1328,7 +1328,7 @@ pfr_add_tables(struct pfr_table *tbl, in
 
  /* find or create root table */
  bzero(key.pfrkt_anchor, sizeof(key.pfrkt_anchor));
- r = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+ r = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
  if (r != NULL) {
  p->pfrkt_root = r;
  goto _skip;
@@ -1387,7 +1387,7 @@ pfr_del_tables(struct pfr_table *tbl, in
  if (pfr_validate_table(&key.pfrkt_t, 0,
     flags & PFR_FLAG_USERIOCTL))
  return (EINVAL);
- p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+ p = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
  if (p != NULL && (p->pfrkt_flags & PFR_TFLAG_ACTIVE)) {
  SLIST_FOREACH(q, &workq, pfrkt_workq)
  if (!pfr_ktable_compare(p, q))
@@ -1425,7 +1425,7 @@ pfr_get_tables(struct pfr_table *filter,
  *size = n;
  return (0);
  }
- RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+ RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
  if (pfr_skip_table(filter, p, flags))
  continue;
  if (n-- <= 0)
@@ -1463,7 +1463,7 @@ pfr_get_tstats(struct pfr_table *filter,
  return (0);
  }
  SLIST_INIT(&workq);
- RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+ RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
  if (pfr_skip_table(filter, p, flags))
  continue;
  if (n-- <= 0)
@@ -1504,7 +1504,7 @@ pfr_clr_tstats(struct pfr_table *tbl, in
  return (EFAULT);
  if (pfr_validate_table(&key.pfrkt_t, 0, 0))
  return (EINVAL);
- p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+ p = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
  if (p != NULL) {
  SLIST_INSERT_HEAD(&workq, p, pfrkt_workq);
  xzero++;
@@ -1539,7 +1539,7 @@ pfr_set_tflags(struct pfr_table *tbl, in
  if (pfr_validate_table(&key.pfrkt_t, 0,
     flags & PFR_FLAG_USERIOCTL))
  return (EINVAL);
- p = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+ p = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
  if (p != NULL && (p->pfrkt_flags & PFR_TFLAG_ACTIVE)) {
  p->pfrkt_nflags = (p->pfrkt_flags | setflag) &
     ~clrflag;
@@ -1582,7 +1582,7 @@ pfr_ina_begin(struct pfr_table *trs, u_i
  if (rs == NULL)
  return (ENOMEM);
  SLIST_INIT(&workq);
- RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+ RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
  if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) ||
     pfr_skip_table(trs, p, 0))
  continue;
@@ -1625,7 +1625,7 @@ pfr_ina_define(struct pfr_table *tbl, st
  return (EBUSY);
  tbl->pfrt_flags |= PFR_TFLAG_INACTIVE;
  SLIST_INIT(&tableq);
- kt = RB_FIND(pfr_ktablehead, &pfr_ktables, (struct pfr_ktable *)tbl);
+ kt = RBT_FIND(pfr_ktablehead, &pfr_ktables, (struct pfr_ktable *)tbl);
  if (kt == NULL) {
  kt = pfr_create_ktable(tbl, 0, 1,
     !(flags & PFR_FLAG_USERIOCTL));
@@ -1639,7 +1639,7 @@ pfr_ina_define(struct pfr_table *tbl, st
  /* find or create root table */
  bzero(&key, sizeof(key));
  strlcpy(key.pfrkt_name, tbl->pfrt_name, sizeof(key.pfrkt_name));
- rt = RB_FIND(pfr_ktablehead, &pfr_ktables, &key);
+ rt = RBT_FIND(pfr_ktablehead, &pfr_ktables, &key);
  if (rt != NULL) {
  kt->pfrkt_root = rt;
  goto _skip;
@@ -1721,7 +1721,7 @@ pfr_ina_rollback(struct pfr_table *trs,
  if (rs == NULL || !rs->topen || ticket != rs->tticket)
  return (0);
  SLIST_INIT(&workq);
- RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+ RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
  if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) ||
     pfr_skip_table(trs, p, 0))
  continue;
@@ -1755,7 +1755,7 @@ pfr_ina_commit(struct pfr_table *trs, u_
  return (EBUSY);
 
  SLIST_INIT(&workq);
- RB_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
+ RBT_FOREACH(p, pfr_ktablehead, &pfr_ktables) {
  if (!(p->pfrkt_flags & PFR_TFLAG_INACTIVE) ||
     pfr_skip_table(trs, p, 0))
  continue;
@@ -1928,7 +1928,7 @@ pfr_insert_ktables(struct pfr_ktablework
 void
 pfr_insert_ktable(struct pfr_ktable *kt)
 {
- RB_INSERT(pfr_ktablehead, &pfr_ktables, kt);
+ RBT_INSERT(pfr_ktablehead, &pfr_ktables, kt);
  pfr_ktable_cnt++;
  if (kt->pfrkt_root != NULL)
  if (!kt->pfrkt_root->pfrkt_refcnt[PFR_REFCNT_ANCHOR]++)
@@ -1959,7 +1959,7 @@ pfr_setflags_ktable(struct pfr_ktable *k
  if (!(newf & PFR_TFLAG_ACTIVE))
  newf &= ~PFR_TFLAG_USRMASK;
  if (!(newf & PFR_TFLAG_SETMASK)) {
- RB_REMOVE(pfr_ktablehead, &pfr_ktables, kt);
+ RBT_REMOVE(pfr_ktablehead, &pfr_ktables, kt);
  if (kt->pfrkt_root != NULL)
  if (!--kt->pfrkt_root->pfrkt_refcnt[PFR_REFCNT_ANCHOR])
  pfr_setflags_ktable(kt->pfrkt_root,
@@ -2082,7 +2082,7 @@ pfr_destroy_ktable(struct pfr_ktable *kt
 }
 
 int
-pfr_ktable_compare(struct pfr_ktable *p, struct pfr_ktable *q)
+pfr_ktable_compare(const struct pfr_ktable *p, const struct pfr_ktable *q)
 {
  int d;
 
@@ -2095,7 +2095,7 @@ struct pfr_ktable *
 pfr_lookup_table(struct pfr_table *tbl)
 {
  /* struct pfr_ktable start like a struct pfr_table */
- return (RB_FIND(pfr_ktablehead, &pfr_ktables,
+ return (RBT_FIND(pfr_ktablehead, &pfr_ktables,
     (struct pfr_ktable *)tbl));
 }
 
Index: pfvar.h
===================================================================
RCS file: /cvs/src/sys/net/pfvar.h,v
retrieving revision 1.438
diff -u -p -r1.438 pfvar.h
--- pfvar.h 3 Sep 2016 17:11:40 -0000 1.438
+++ pfvar.h 26 Sep 2016 10:26:29 -0000
@@ -619,7 +619,7 @@ SLIST_HEAD(pf_rule_slist, pf_rule_item);
 enum pf_sn_types { PF_SN_NONE, PF_SN_NAT, PF_SN_RDR, PF_SN_ROUTE, PF_SN_MAX };
 
 struct pf_src_node {
- RB_ENTRY(pf_src_node) entry;
+ RBT_ENTRY(pf_src_node) entry;
  struct pf_addr addr;
  struct pf_addr raddr;
  union pf_rule_ptr rule;
@@ -682,7 +682,7 @@ struct pf_state_peer {
 
 TAILQ_HEAD(pf_state_queue, pf_state);
 
-/* keep synced with struct pf_state_key, used in RB_FIND */
+/* keep synced with struct pf_state_key, used in RBT_FIND */
 struct pf_state_key_cmp {
  struct pf_addr addr[2];
  u_int16_t port[2];
@@ -705,7 +705,7 @@ struct pf_state_key {
  sa_family_t af;
  u_int8_t proto;
 
- RB_ENTRY(pf_state_key) entry;
+ RBT_ENTRY(pf_state_key) entry;
  struct pf_statelisthead states;
  struct pf_state_key *reverse;
  struct inpcb *inp;
@@ -716,7 +716,7 @@ struct pf_state_key {
  ((key[PF_SK_WIRE]->af != key[PF_SK_STACK]->af) && \
  (key[PF_SK_WIRE]->af != (family)))
 
-/* keep synced with struct pf_state, used in RB_FIND */
+/* keep synced with struct pf_state, used in RBT_FIND */
 struct pf_state_cmp {
  u_int64_t id;
  u_int32_t creatorid;
@@ -732,7 +732,7 @@ struct pf_state {
 
  TAILQ_ENTRY(pf_state) sync_list;
  TAILQ_ENTRY(pf_state) entry_list;
- RB_ENTRY(pf_state) entry_id;
+ RBT_ENTRY(pf_state) entry_id;
  struct pf_state_peer src;
  struct pf_state_peer dst;
  struct pf_rule_slist match_rules;
@@ -916,11 +916,11 @@ struct pf_ruleset {
  int topen;
 };
 
-RB_HEAD(pf_anchor_global, pf_anchor);
-RB_HEAD(pf_anchor_node, pf_anchor);
+RBT_HEAD(pf_anchor_global, pf_anchor);
+RBT_HEAD(pf_anchor_node, pf_anchor);
 struct pf_anchor {
- RB_ENTRY(pf_anchor) entry_global;
- RB_ENTRY(pf_anchor) entry_node;
+ RBT_ENTRY(pf_anchor) entry_global;
+ RBT_ENTRY(pf_anchor) entry_node;
  struct pf_anchor *parent;
  struct pf_anchor_node children;
  char name[PF_ANCHOR_NAME_SIZE];
@@ -929,8 +929,8 @@ struct pf_anchor {
  int refcnt; /* anchor rules */
  int match;
 };
-RB_PROTOTYPE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare)
-RB_PROTOTYPE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare)
+RBT_PROTOTYPE(pf_anchor_global, pf_anchor, entry_global, pf_anchor_compare)
+RBT_PROTOTYPE(pf_anchor_node, pf_anchor, entry_node, pf_anchor_compare)
 
 #define PF_RESERVED_ANCHOR "_pf"
 
@@ -1080,10 +1080,10 @@ struct pfr_kentry_all {
 #define pfrke_rkif u.kr.kif
 
 SLIST_HEAD(pfr_ktableworkq, pfr_ktable);
-RB_HEAD(pfr_ktablehead, pfr_ktable);
+RBT_HEAD(pfr_ktablehead, pfr_ktable);
 struct pfr_ktable {
  struct pfr_tstats pfrkt_ts;
- RB_ENTRY(pfr_ktable) pfrkt_tree;
+ RBT_ENTRY(pfr_ktable) pfrkt_tree;
  SLIST_ENTRY(pfr_ktable) pfrkt_workq;
  struct radix_node_head *pfrkt_ip4;
  struct radix_node_head *pfrkt_ip6;
@@ -1109,19 +1109,19 @@ struct pfr_ktable {
 #define pfrkt_nomatch pfrkt_ts.pfrts_nomatch
 #define pfrkt_tzero pfrkt_ts.pfrts_tzero
 
-RB_HEAD(pf_state_tree, pf_state_key);
-RB_PROTOTYPE(pf_state_tree, pf_state_key, entry, pf_state_compare_key)
+RBT_HEAD(pf_state_tree, pf_state_key);
+RBT_PROTOTYPE(pf_state_tree, pf_state_key, entry, pf_state_compare_key)
 
-RB_HEAD(pf_state_tree_ext_gwy, pf_state_key);
-RB_PROTOTYPE(pf_state_tree_ext_gwy, pf_state_key,
+RBT_HEAD(pf_state_tree_ext_gwy, pf_state_key);
+RBT_PROTOTYPE(pf_state_tree_ext_gwy, pf_state_key,
     entry_ext_gwy, pf_state_compare_ext_gwy)
 
-RB_HEAD(pfi_ifhead, pfi_kif);
+RBT_HEAD(pfi_ifhead, pfi_kif);
 
 /* state tables */
 extern struct pf_state_tree pf_statetbl;
 
-/* keep synced with pfi_kif, used in RB_FIND */
+/* keep synced with pfi_kif, used in RBT_FIND */
 struct pfi_kif_cmp {
  char pfik_name[IFNAMSIZ];
 };
@@ -1131,7 +1131,7 @@ struct ifg_group;
 
 struct pfi_kif {
  char pfik_name[IFNAMSIZ];
- RB_ENTRY(pfi_kif) pfik_tree;
+ RBT_ENTRY(pfi_kif) pfik_tree;
  u_int64_t pfik_packets[2][2][2];
  u_int64_t pfik_bytes[2][2][2];
  time_t pfik_tzero;
@@ -1641,12 +1641,12 @@ struct pfioc_iface {
 #define DIOCGETQSTATS _IOWR('D', 96, struct pfioc_qstats)
 
 #ifdef _KERNEL
-RB_HEAD(pf_src_tree, pf_src_node);
-RB_PROTOTYPE(pf_src_tree, pf_src_node, entry, pf_src_compare);
+RBT_HEAD(pf_src_tree, pf_src_node);
+RBT_PROTOTYPE(pf_src_tree, pf_src_node, entry, pf_src_compare);
 extern struct pf_src_tree tree_src_tracking;
 
-RB_HEAD(pf_state_tree_id, pf_state);
-RB_PROTOTYPE(pf_state_tree_id, pf_state,
+RBT_HEAD(pf_state_tree_id, pf_state);
+RBT_PROTOTYPE(pf_state_tree_id, pf_state,
     entry_id, pf_state_compare_id);
 extern struct pf_state_tree_id tree_id;
 extern struct pf_state_queue state_list;
@@ -1842,8 +1842,8 @@ void pf_tag2tagname(u_int16_t, char *)
 void pf_tag_ref(u_int16_t);
 void pf_tag_unref(u_int16_t);
 void pf_tag_packet(struct mbuf *, int, int);
-int pf_addr_compare(struct pf_addr *, struct pf_addr *,
-    sa_family_t);
+int pf_addr_compare(const struct pf_addr *,
+    const struct pf_addr *, sa_family_t);
 
 extern struct pf_status pf_status;
 extern struct pool pf_frent_pl, pf_frag_pl;