sys/netpfil/ipfw/ip_fw_dynamic.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2002 Luigi Rizzo, Universita` di Pisa
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  */
  27
  28 #include <sys/cdefs.h>
  29 __FBSDID("$FreeBSD$");
  30
  31 #define        DEB(x)
  32 #define        DDB(x) x
  33
  34 /*
  35  * Dynamic rule support for ipfw
  36  */
  37
  38 #include "opt_ipfw.h"
  39 #include "opt_inet.h"
  40 #ifndef INET
  41 #error IPFIREWALL requires INET.
  42 #endif /* INET */
  43 #include "opt_inet6.h"
  44
  45 #include <sys/param.h>
  46 #include <sys/systm.h>
  47 #include <sys/malloc.h>
  48 #include <sys/mbuf.h>
  49 #include <sys/kernel.h>
  50 #include <sys/ktr.h>
  51 #include <sys/lock.h>
  52 #include <sys/rmlock.h>
  53 #include <sys/socket.h>
  54 #include <sys/sysctl.h>
  55 #include <sys/syslog.h>
  56 #include <net/ethernet.h> /* for ETHERTYPE_IP */
  57 #include <net/if.h>
  58 #include <net/if_var.h>
  59 #include <net/pfil.h>
  60 #include <net/vnet.h>
  61
  62 #include <netinet/in.h>
  63 #include <netinet/ip.h>
  64 #include <netinet/ip_var.h>     /* ip_defttl */
  65 #include <netinet/ip_fw.h>
  66 #include <netinet/tcp_var.h>
  67 #include <netinet/udp.h>
  68
  69 #include <netinet/ip6.h>        /* IN6_ARE_ADDR_EQUAL */
  70 #ifdef INET6
  71 #include <netinet6/in6_var.h>
  72 #include <netinet6/ip6_var.h>
  73 #endif
  74
  75 #include <netpfil/ipfw/ip_fw_private.h>
  76
  77 #include <machine/in_cksum.h>   /* XXX for in_cksum */
  78
  79 #ifdef MAC
  80 #include <security/mac/mac_framework.h>
  81 #endif
  82
  83 /*
  84  * Description of dynamic rules.
  85  *
  86  * Dynamic rules are stored in lists accessed through a hash table
  87  * (ipfw_dyn_v) whose size is curr_dyn_buckets. This value can
  88  * be modified through the sysctl variable dyn_buckets which is
  89  * updated when the table becomes empty.
  90  *
  91  * XXX currently there is only one list, ipfw_dyn.
  92  *
  93  * When a packet is received, its address fields are first masked
  94  * with the mask defined for the rule, then hashed, then matched
  95  * against the entries in the corresponding list.
  96  * Dynamic rules can be used for different purposes:
  97  *  + stateful rules;
  98  *  + enforcing limits on the number of sessions;
  99  *  + in-kernel NAT (not implemented yet)
 100  *
 101  * The lifetime of dynamic rules is regulated by dyn_*_lifetime,
 102  * measured in seconds and depending on the flags.
 103  *
 104  * The total number of dynamic rules is equal to UMA zone items count.
 105  * The max number of dynamic rules is dyn_max. When we reach
 106  * the maximum number of rules we do not create anymore. This is
 107  * done to avoid consuming too much memory, but also too much
 108  * time when searching on each packet (ideally, we should try instead
 109  * to put a limit on the length of the list on each bucket...).
 110  *
 111  * Each dynamic rule holds a pointer to the parent ipfw rule so
 112  * we know what action to perform. Dynamic rules are removed when
 113  * the parent rule is deleted. This can be changed by dyn_keep_states
 114  * sysctl.
 115  *
 116  * There are some limitations with dynamic rules -- we do not
 117  * obey the 'randomized match', and we do not do multiple
 118  * passes through the firewall. XXX check the latter!!!
 119  */
 120
 121 struct ipfw_dyn_bucket {
 122         struct mtx      mtx;            /* Bucket protecting lock */
 123         ipfw_dyn_rule   *head;          /* Pointer to first rule */
 124 };
 125
 126 /*
 127  * Static variables followed by global ones
 128  */
 129 static VNET_DEFINE(struct ipfw_dyn_bucket *, ipfw_dyn_v);
 130 static VNET_DEFINE(u_int32_t, dyn_buckets_max);
 131 static VNET_DEFINE(u_int32_t, curr_dyn_buckets);
 132 static VNET_DEFINE(struct callout, ipfw_timeout);
 133 #define V_ipfw_dyn_v                    VNET(ipfw_dyn_v)
 134 #define V_dyn_buckets_max               VNET(dyn_buckets_max)
 135 #define V_curr_dyn_buckets              VNET(curr_dyn_buckets)
 136 #define V_ipfw_timeout                  VNET(ipfw_timeout)
 137
 138 static VNET_DEFINE(uma_zone_t, ipfw_dyn_rule_zone);
 139 #define V_ipfw_dyn_rule_zone            VNET(ipfw_dyn_rule_zone)
 140
 141 #define IPFW_BUCK_LOCK_INIT(b)  \
 142         mtx_init(&(b)->mtx, "IPFW dynamic bucket", NULL, MTX_DEF)
 143 #define IPFW_BUCK_LOCK_DESTROY(b)       \
 144         mtx_destroy(&(b)->mtx)
 145 #define IPFW_BUCK_LOCK(i)       mtx_lock(&V_ipfw_dyn_v[(i)].mtx)
 146 #define IPFW_BUCK_UNLOCK(i)     mtx_unlock(&V_ipfw_dyn_v[(i)].mtx)
 147 #define IPFW_BUCK_ASSERT(i)     mtx_assert(&V_ipfw_dyn_v[(i)].mtx, MA_OWNED)
 148
 149
 150 static VNET_DEFINE(int, dyn_keep_states);
 151 #define V_dyn_keep_states               VNET(dyn_keep_states)
 152
 153 /*
 154  * Timeouts for various events in handing dynamic rules.
 155  */
 156 static VNET_DEFINE(u_int32_t, dyn_ack_lifetime);
 157 static VNET_DEFINE(u_int32_t, dyn_syn_lifetime);
 158 static VNET_DEFINE(u_int32_t, dyn_fin_lifetime);
 159 static VNET_DEFINE(u_int32_t, dyn_rst_lifetime);
 160 static VNET_DEFINE(u_int32_t, dyn_udp_lifetime);
 161 static VNET_DEFINE(u_int32_t, dyn_short_lifetime);
 162
 163 #define V_dyn_ack_lifetime              VNET(dyn_ack_lifetime)
 164 #define V_dyn_syn_lifetime              VNET(dyn_syn_lifetime)
 165 #define V_dyn_fin_lifetime              VNET(dyn_fin_lifetime)
 166 #define V_dyn_rst_lifetime              VNET(dyn_rst_lifetime)
 167 #define V_dyn_udp_lifetime              VNET(dyn_udp_lifetime)
 168 #define V_dyn_short_lifetime            VNET(dyn_short_lifetime)
 169
 170 /*
 171  * Keepalives are sent if dyn_keepalive is set. They are sent every
 172  * dyn_keepalive_period seconds, in the last dyn_keepalive_interval
 173  * seconds of lifetime of a rule.
 174  * dyn_rst_lifetime and dyn_fin_lifetime should be strictly lower
 175  * than dyn_keepalive_period.
 176  */
 177
 178 static VNET_DEFINE(u_int32_t, dyn_keepalive_interval);
 179 static VNET_DEFINE(u_int32_t, dyn_keepalive_period);
 180 static VNET_DEFINE(u_int32_t, dyn_keepalive);
 181 static VNET_DEFINE(time_t, dyn_keepalive_last);
 182
 183 #define V_dyn_keepalive_interval        VNET(dyn_keepalive_interval)
 184 #define V_dyn_keepalive_period          VNET(dyn_keepalive_period)
 185 #define V_dyn_keepalive                 VNET(dyn_keepalive)
 186 #define V_dyn_keepalive_last            VNET(dyn_keepalive_last)
 187
 188 static VNET_DEFINE(u_int32_t, dyn_max);         /* max # of dynamic rules */
 189
 190 #define DYN_COUNT                       uma_zone_get_cur(V_ipfw_dyn_rule_zone)
 191 #define V_dyn_max                       VNET(dyn_max)
 192
 193 /* for userspace, we emulate the uma_zone_counter with ipfw_dyn_count */
 194 static int ipfw_dyn_count;      /* number of objects */
 195
 196 #ifdef USERSPACE /* emulation of UMA object counters for userspace */
 197 #define uma_zone_get_cur(x)     ipfw_dyn_count
 198 #endif /* USERSPACE */
 199
 200 static int last_log;    /* Log ratelimiting */
 201
 202 static void ipfw_dyn_tick(void *vnetx);
 203 static void check_dyn_rules(struct ip_fw_chain *, ipfw_range_tlv *, int, int);
 204 #ifdef SYSCTL_NODE
 205
 206 static int sysctl_ipfw_dyn_count(SYSCTL_HANDLER_ARGS);
 207 static int sysctl_ipfw_dyn_max(SYSCTL_HANDLER_ARGS);
 208
 209 SYSBEGIN(f2)
 210
 211 SYSCTL_DECL(_net_inet_ip_fw);
 212 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_buckets,
 213     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_buckets_max), 0,
 214     "Max number of dyn. buckets");
 215 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, curr_dyn_buckets,
 216     CTLFLAG_VNET | CTLFLAG_RD, &VNET_NAME(curr_dyn_buckets), 0,
 217     "Current Number of dyn. buckets");
 218 SYSCTL_PROC(_net_inet_ip_fw, OID_AUTO, dyn_count,
 219     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RD, 0, 0, sysctl_ipfw_dyn_count, "IU",
 220     "Number of dyn. rules");
 221 SYSCTL_PROC(_net_inet_ip_fw, OID_AUTO, dyn_max,
 222     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW, 0, 0, sysctl_ipfw_dyn_max, "IU",
 223     "Max number of dyn. rules");
 224 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_ack_lifetime,
 225     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_ack_lifetime), 0,
 226     "Lifetime of dyn. rules for acks");
 227 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_syn_lifetime,
 228     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_syn_lifetime), 0,
 229     "Lifetime of dyn. rules for syn");
 230 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_fin_lifetime,
 231     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_fin_lifetime), 0,
 232     "Lifetime of dyn. rules for fin");
 233 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_rst_lifetime,
 234     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_rst_lifetime), 0,
 235     "Lifetime of dyn. rules for rst");
 236 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_udp_lifetime,
 237     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_udp_lifetime), 0,
 238     "Lifetime of dyn. rules for UDP");
 239 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_short_lifetime,
 240     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_short_lifetime), 0,
 241     "Lifetime of dyn. rules for other situations");
 242 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_keepalive,
 243     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_keepalive), 0,
 244     "Enable keepalives for dyn. rules");
 245 SYSCTL_UINT(_net_inet_ip_fw, OID_AUTO, dyn_keep_states,
 246     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(dyn_keep_states), 0,
 247     "Do not flush dynamic states on rule deletion");
 248
 249 SYSEND
 250
 251 #endif /* SYSCTL_NODE */
 252
 253
 254 #ifdef INET6
 255 static __inline int
 256 hash_packet6(const struct ipfw_flow_id *id)
 257 {
 258         u_int32_t i;
 259         i = (id->dst_ip6.__u6_addr.__u6_addr32[2]) ^
 260             (id->dst_ip6.__u6_addr.__u6_addr32[3]) ^
 261             (id->src_ip6.__u6_addr.__u6_addr32[2]) ^
 262             (id->src_ip6.__u6_addr.__u6_addr32[3]);
 263         return ntohl(i);
 264 }
 265 #endif
 266
 267 /*
 268  * IMPORTANT: the hash function for dynamic rules must be commutative
 269  * in source and destination (ip,port), because rules are bidirectional
 270  * and we want to find both in the same bucket.
 271  */
 272 static __inline int
 273 hash_packet(const struct ipfw_flow_id *id, int buckets)
 274 {
 275         u_int32_t i;
 276
 277 #ifdef INET6
 278         if (IS_IP6_FLOW_ID(id))
 279                 i = hash_packet6(id);
 280         else
 281 #endif /* INET6 */
 282         i = (id->dst_ip) ^ (id->src_ip);
 283         i ^= (id->dst_port) ^ (id->src_port);
 284         return (i & (buckets - 1));
 285 }
 286
 287 #if 0
 288 #define DYN_DEBUG(fmt, ...)     do {                    \
 289         printf("%s: " fmt "\n", __func__, __VA_ARGS__); \
 290 } while (0)
 291 #else
 292 #define DYN_DEBUG(fmt, ...)
 293 #endif
 294
 295 static char *default_state_name = "default";
 296 struct dyn_state_obj {
 297         struct named_object     no;
 298         char                    name[64];
 299 };
 300
 301 #define DYN_STATE_OBJ(ch, cmd)  \
 302     ((struct dyn_state_obj *)SRV_OBJECT(ch, (cmd)->arg1))
 303 /*
 304  * Classifier callback.
 305  * Return 0 if opcode contains object that should be referenced
 306  * or rewritten.
 307  */
 308 static int
 309 dyn_classify(ipfw_insn *cmd, uint16_t *puidx, uint8_t *ptype)
 310 {
 311
 312         DYN_DEBUG("opcode %d, arg1 %d", cmd->opcode, cmd->arg1);
 313         /* Don't rewrite "check-state any" */
 314         if (cmd->arg1 == 0 &&
 315             cmd->opcode == O_CHECK_STATE)
 316                 return (1);
 317
 318         *puidx = cmd->arg1;
 319         *ptype = 0;
 320         return (0);
 321 }
 322
 323 static void
 324 dyn_update(ipfw_insn *cmd, uint16_t idx)
 325 {
 326
 327         cmd->arg1 = idx;
 328         DYN_DEBUG("opcode %d, arg1 %d", cmd->opcode, cmd->arg1);
 329 }
 330
 331 static int
 332 dyn_findbyname(struct ip_fw_chain *ch, struct tid_info *ti,
 333     struct named_object **pno)
 334 {
 335         ipfw_obj_ntlv *ntlv;
 336         const char *name;
 337
 338         DYN_DEBUG("uidx %d", ti->uidx);
 339         if (ti->uidx != 0) {
 340                 if (ti->tlvs == NULL)
 341                         return (EINVAL);
 342                 /* Search ntlv in the buffer provided by user */
 343                 ntlv = ipfw_find_name_tlv_type(ti->tlvs, ti->tlen, ti->uidx,
 344                     IPFW_TLV_STATE_NAME);
 345                 if (ntlv == NULL)
 346                         return (EINVAL);
 347                 name = ntlv->name;
 348         } else
 349                 name = default_state_name;
 350         /*
 351          * Search named object with corresponding name.
 352          * Since states objects are global - ignore the set value
 353          * and use zero instead.
 354          */
 355         *pno = ipfw_objhash_lookup_name_type(CHAIN_TO_SRV(ch), 0,
 356             IPFW_TLV_STATE_NAME, name);
 357         /*
 358          * We always return success here.
 359          * The caller will check *pno and mark object as unresolved,
 360          * then it will automatically create "default" object.
 361          */
 362         return (0);
 363 }
 364
 365 static struct named_object *
 366 dyn_findbykidx(struct ip_fw_chain *ch, uint16_t idx)
 367 {
 368
 369         DYN_DEBUG("kidx %d", idx);
 370         return (ipfw_objhash_lookup_kidx(CHAIN_TO_SRV(ch), idx));
 371 }
 372
 373 static int
 374 dyn_create(struct ip_fw_chain *ch, struct tid_info *ti,
 375     uint16_t *pkidx)
 376 {
 377         struct namedobj_instance *ni;
 378         struct dyn_state_obj *obj;
 379         struct named_object *no;
 380         ipfw_obj_ntlv *ntlv;
 381         char *name;
 382
 383         DYN_DEBUG("uidx %d", ti->uidx);
 384         if (ti->uidx != 0) {
 385                 if (ti->tlvs == NULL)
 386                         return (EINVAL);
 387                 ntlv = ipfw_find_name_tlv_type(ti->tlvs, ti->tlen, ti->uidx,
 388                     IPFW_TLV_STATE_NAME);
 389                 if (ntlv == NULL)
 390                         return (EINVAL);
 391                 name = ntlv->name;
 392         } else
 393                 name = default_state_name;
 394
 395         ni = CHAIN_TO_SRV(ch);
 396         obj = malloc(sizeof(*obj), M_IPFW, M_WAITOK | M_ZERO);
 397         obj->no.name = obj->name;
 398         obj->no.etlv = IPFW_TLV_STATE_NAME;
 399         strlcpy(obj->name, name, sizeof(obj->name));
 400
 401         IPFW_UH_WLOCK(ch);
 402         no = ipfw_objhash_lookup_name_type(ni, 0,
 403             IPFW_TLV_STATE_NAME, name);
 404         if (no != NULL) {
 405                 /*
 406                  * Object is already created.
 407                  * Just return its kidx and bump refcount.
 408                  */
 409                 *pkidx = no->kidx;
 410                 no->refcnt++;
 411                 IPFW_UH_WUNLOCK(ch);
 412                 free(obj, M_IPFW);
 413                 DYN_DEBUG("\tfound kidx %d", *pkidx);
 414                 return (0);
 415         }
 416         if (ipfw_objhash_alloc_idx(ni, &obj->no.kidx) != 0) {
 417                 DYN_DEBUG("\talloc_idx failed for %s", name);
 418                 IPFW_UH_WUNLOCK(ch);
 419                 free(obj, M_IPFW);
 420                 return (ENOSPC);
 421         }
 422         ipfw_objhash_add(ni, &obj->no);
 423         SRV_OBJECT(ch, obj->no.kidx) = obj;
 424         obj->no.refcnt++;
 425         *pkidx = obj->no.kidx;
 426         IPFW_UH_WUNLOCK(ch);
 427         DYN_DEBUG("\tcreated kidx %d", *pkidx);
 428         return (0);
 429 }
 430
 431 static void
 432 dyn_destroy(struct ip_fw_chain *ch, struct named_object *no)
 433 {
 434         struct dyn_state_obj *obj;
 435
 436         IPFW_UH_WLOCK_ASSERT(ch);
 437
 438         KASSERT(no->refcnt == 1,
 439             ("Destroying object '%s' (type %u, idx %u) with refcnt %u",
 440             no->name, no->etlv, no->kidx, no->refcnt));
 441
 442         DYN_DEBUG("kidx %d", no->kidx);
 443         obj = SRV_OBJECT(ch, no->kidx);
 444         SRV_OBJECT(ch, no->kidx) = NULL;
 445         ipfw_objhash_del(CHAIN_TO_SRV(ch), no);
 446         ipfw_objhash_free_idx(CHAIN_TO_SRV(ch), no->kidx);
 447
 448         free(obj, M_IPFW);
 449 }
 450
 451 static struct opcode_obj_rewrite dyn_opcodes[] = {
 452         {
 453                 O_KEEP_STATE, IPFW_TLV_STATE_NAME,
 454                 dyn_classify, dyn_update,
 455                 dyn_findbyname, dyn_findbykidx,
 456                 dyn_create, dyn_destroy
 457         },
 458         {
 459                 O_CHECK_STATE, IPFW_TLV_STATE_NAME,
 460                 dyn_classify, dyn_update,
 461                 dyn_findbyname, dyn_findbykidx,
 462                 dyn_create, dyn_destroy
 463         },
 464         {
 465                 O_PROBE_STATE, IPFW_TLV_STATE_NAME,
 466                 dyn_classify, dyn_update,
 467                 dyn_findbyname, dyn_findbykidx,
 468                 dyn_create, dyn_destroy
 469         },
 470         {
 471                 O_LIMIT, IPFW_TLV_STATE_NAME,
 472                 dyn_classify, dyn_update,
 473                 dyn_findbyname, dyn_findbykidx,
 474                 dyn_create, dyn_destroy
 475         },
 476 };
 477 /**
 478  * Print customizable flow id description via log(9) facility.
 479  */
 480 static void
 481 print_dyn_rule_flags(const struct ipfw_flow_id *id, int dyn_type,
 482     int log_flags, char *prefix, char *postfix)
 483 {
 484         struct in_addr da;
 485 #ifdef INET6
 486         char src[INET6_ADDRSTRLEN], dst[INET6_ADDRSTRLEN];
 487 #else
 488         char src[INET_ADDRSTRLEN], dst[INET_ADDRSTRLEN];
 489 #endif
 490
 491 #ifdef INET6
 492         if (IS_IP6_FLOW_ID(id)) {
 493                 ip6_sprintf(src, &id->src_ip6);
 494                 ip6_sprintf(dst, &id->dst_ip6);
 495         } else
 496 #endif
 497         {
 498                 da.s_addr = htonl(id->src_ip);
 499                 inet_ntop(AF_INET, &da, src, sizeof(src));
 500                 da.s_addr = htonl(id->dst_ip);
 501                 inet_ntop(AF_INET, &da, dst, sizeof(dst));
 502         }
 503         log(log_flags, "ipfw: %s type %d %s %d -> %s %d, %d %s\n",
 504             prefix, dyn_type, src, id->src_port, dst,
 505             id->dst_port, DYN_COUNT, postfix);
 506 }
 507
 508 #define print_dyn_rule(id, dtype, prefix, postfix)      \
 509         print_dyn_rule_flags(id, dtype, LOG_DEBUG, prefix, postfix)
 510
 511 #define TIME_LEQ(a,b)       ((int)((a)-(b)) <= 0)
 512 #define TIME_LE(a,b)       ((int)((a)-(b)) < 0)
 513
 514 static void
 515 dyn_update_proto_state(ipfw_dyn_rule *q, const struct ipfw_flow_id *id,
 516     const void *ulp, int dir)
 517 {
 518         const struct tcphdr *tcp;
 519         uint32_t ack;
 520         u_char flags;
 521
 522         if (id->proto == IPPROTO_TCP) {
 523                 tcp = (const struct tcphdr *)ulp;
 524                 flags = id->_flags & (TH_FIN | TH_SYN | TH_RST);
 525 #define BOTH_SYN        (TH_SYN | (TH_SYN << 8))
 526 #define BOTH_FIN        (TH_FIN | (TH_FIN << 8))
 527 #define TCP_FLAGS       (TH_FLAGS | (TH_FLAGS << 8))
 528 #define ACK_FWD         0x10000                 /* fwd ack seen */
 529 #define ACK_REV         0x20000                 /* rev ack seen */
 530
 531                 q->state |= (dir == MATCH_FORWARD) ? flags : (flags << 8);
 532                 switch (q->state & TCP_FLAGS) {
 533                 case TH_SYN:                    /* opening */
 534                         q->expire = time_uptime + V_dyn_syn_lifetime;
 535                         break;
 536
 537                 case BOTH_SYN:                  /* move to established */
 538                 case BOTH_SYN | TH_FIN:         /* one side tries to close */
 539                 case BOTH_SYN | (TH_FIN << 8):
 540 #define _SEQ_GE(a,b) ((int)(a) - (int)(b) >= 0)
 541                         if (tcp == NULL)
 542                                 break;
 543
 544                         ack = ntohl(tcp->th_ack);
 545                         if (dir == MATCH_FORWARD) {
 546                                 if (q->ack_fwd == 0 ||
 547                                     _SEQ_GE(ack, q->ack_fwd)) {
 548                                         q->ack_fwd = ack;
 549                                         q->state |= ACK_FWD;
 550                                 }
 551                         } else {
 552                                 if (q->ack_rev == 0 ||
 553                                     _SEQ_GE(ack, q->ack_rev)) {
 554                                         q->ack_rev = ack;
 555                                         q->state |= ACK_REV;
 556                                 }
 557                         }
 558                         if ((q->state & (ACK_FWD | ACK_REV)) ==
 559                             (ACK_FWD | ACK_REV)) {
 560                                 q->expire = time_uptime + V_dyn_ack_lifetime;
 561                                 q->state &= ~(ACK_FWD | ACK_REV);
 562                         }
 563                         break;
 564
 565                 case BOTH_SYN | BOTH_FIN:       /* both sides closed */
 566                         if (V_dyn_fin_lifetime >= V_dyn_keepalive_period)
 567                                 V_dyn_fin_lifetime =
 568                                     V_dyn_keepalive_period - 1;
 569                         q->expire = time_uptime + V_dyn_fin_lifetime;
 570                         break;
 571
 572                 default:
 573 #if 0
 574                         /*
 575                          * reset or some invalid combination, but can also
 576                          * occur if we use keep-state the wrong way.
 577                          */
 578                         if ( (q->state & ((TH_RST << 8)|TH_RST)) == 0)
 579                                 printf("invalid state: 0x%x\n", q->state);
 580 #endif
 581                         if (V_dyn_rst_lifetime >= V_dyn_keepalive_period)
 582                                 V_dyn_rst_lifetime =
 583                                     V_dyn_keepalive_period - 1;
 584                         q->expire = time_uptime + V_dyn_rst_lifetime;
 585                         break;
 586                 }
 587         } else if (id->proto == IPPROTO_UDP) {
 588                 q->expire = time_uptime + V_dyn_udp_lifetime;
 589         } else {
 590                 /* other protocols */
 591                 q->expire = time_uptime + V_dyn_short_lifetime;
 592         }
 593 }
 594
 595 /*
 596  * Lookup a dynamic rule, locked version.
 597  */
 598 static ipfw_dyn_rule *
 599 lookup_dyn_rule_locked(const struct ipfw_flow_id *pkt, const void *ulp,
 600     int i, int *match_direction, uint16_t kidx)
 601 {
 602         /*
 603          * Stateful ipfw extensions.
 604          * Lookup into dynamic session queue.
 605          */
 606         ipfw_dyn_rule *prev, *q = NULL;
 607         int dir;
 608
 609         IPFW_BUCK_ASSERT(i);
 610
 611         dir = MATCH_NONE;
 612         for (prev = NULL, q = V_ipfw_dyn_v[i].head; q; prev = q, q = q->next) {
 613                 if (q->dyn_type == O_LIMIT_PARENT)
 614                         continue;
 615
 616                 if (pkt->addr_type != q->id.addr_type)
 617                         continue;
 618
 619                 if (pkt->proto != q->id.proto)
 620                         continue;
 621
 622                 if (kidx != 0 && kidx != q->kidx)
 623                         continue;
 624
 625                 if (IS_IP6_FLOW_ID(pkt)) {
 626                         if (IN6_ARE_ADDR_EQUAL(&pkt->src_ip6, &q->id.src_ip6) &&
 627                             IN6_ARE_ADDR_EQUAL(&pkt->dst_ip6, &q->id.dst_ip6) &&
 628                             pkt->src_port == q->id.src_port &&
 629                             pkt->dst_port == q->id.dst_port) {
 630                                 dir = MATCH_FORWARD;
 631                                 break;
 632                         }
 633                         if (IN6_ARE_ADDR_EQUAL(&pkt->src_ip6, &q->id.dst_ip6) &&
 634                             IN6_ARE_ADDR_EQUAL(&pkt->dst_ip6, &q->id.src_ip6) &&
 635                             pkt->src_port == q->id.dst_port &&
 636                             pkt->dst_port == q->id.src_port) {
 637                                 dir = MATCH_REVERSE;
 638                                 break;
 639                         }
 640                 } else {
 641                         if (pkt->src_ip == q->id.src_ip &&
 642                             pkt->dst_ip == q->id.dst_ip &&
 643                             pkt->src_port == q->id.src_port &&
 644                             pkt->dst_port == q->id.dst_port) {
 645                                 dir = MATCH_FORWARD;
 646                                 break;
 647                         }
 648                         if (pkt->src_ip == q->id.dst_ip &&
 649                             pkt->dst_ip == q->id.src_ip &&
 650                             pkt->src_port == q->id.dst_port &&
 651                             pkt->dst_port == q->id.src_port) {
 652                                 dir = MATCH_REVERSE;
 653                                 break;
 654                         }
 655                 }
 656         }
 657         if (q == NULL)
 658                 goto done;      /* q = NULL, not found */
 659
 660         if (prev != NULL) {     /* found and not in front */
 661                 prev->next = q->next;
 662                 q->next = V_ipfw_dyn_v[i].head;
 663                 V_ipfw_dyn_v[i].head = q;
 664         }
 665
 666         /* update state according to flags */
 667         dyn_update_proto_state(q, pkt, ulp, dir);
 668 done:
 669         if (match_direction != NULL)
 670                 *match_direction = dir;
 671         return (q);
 672 }
 673
 674 struct ip_fw *
 675 ipfw_dyn_lookup_state(const struct ipfw_flow_id *pkt, const void *ulp,
 676     int pktlen, int *match_direction, uint16_t kidx)
 677 {
 678         struct ip_fw *rule;
 679         ipfw_dyn_rule *q;
 680         int i;
 681
 682         i = hash_packet(pkt, V_curr_dyn_buckets);
 683
 684         IPFW_BUCK_LOCK(i);
 685         q = lookup_dyn_rule_locked(pkt, ulp, i, match_direction, kidx);
 686         if (q == NULL)
 687                 rule = NULL;
 688         else {
 689                 rule = q->rule;
 690                 IPFW_INC_DYN_COUNTER(q, pktlen);
 691         }
 692         IPFW_BUCK_UNLOCK(i);
 693         return (rule);
 694 }
 695
 696 static int
 697 resize_dynamic_table(struct ip_fw_chain *chain, int nbuckets)
 698 {
 699         int i, k, nbuckets_old;
 700         ipfw_dyn_rule *q;
 701         struct ipfw_dyn_bucket *dyn_v, *dyn_v_old;
 702
 703         /* Check if given number is power of 2 and less than 64k */
 704         if ((nbuckets > 65536) || (!powerof2(nbuckets)))
 705                 return 1;
 706
 707         CTR3(KTR_NET, "%s: resize dynamic hash: %d -> %d", __func__,
 708             V_curr_dyn_buckets, nbuckets);
 709
 710         /* Allocate and initialize new hash */
 711         dyn_v = malloc(nbuckets * sizeof(*dyn_v), M_IPFW,
 712             M_WAITOK | M_ZERO);
 713
 714         for (i = 0 ; i < nbuckets; i++)
 715                 IPFW_BUCK_LOCK_INIT(&dyn_v[i]);
 716
 717         /*
 718          * Call upper half lock, as get_map() do to ease
 719          * read-only access to dynamic rules hash from sysctl
 720          */
 721         IPFW_UH_WLOCK(chain);
 722
 723         /*
 724          * Acquire chain write lock to permit hash access
 725          * for main traffic path without additional locks
 726          */
 727         IPFW_WLOCK(chain);
 728
 729         /* Save old values */
 730         nbuckets_old = V_curr_dyn_buckets;
 731         dyn_v_old = V_ipfw_dyn_v;
 732
 733         /* Skip relinking if array is not set up */
 734         if (V_ipfw_dyn_v == NULL)
 735                 V_curr_dyn_buckets = 0;
 736
 737         /* Re-link all dynamic states */
 738         for (i = 0 ; i < V_curr_dyn_buckets ; i++) {
 739                 while (V_ipfw_dyn_v[i].head != NULL) {
 740                         /* Remove from current chain */
 741                         q = V_ipfw_dyn_v[i].head;
 742                         V_ipfw_dyn_v[i].head = q->next;
 743
 744                         /* Get new hash value */
 745                         k = hash_packet(&q->id, nbuckets);
 746                         q->bucket = k;
 747                         /* Add to the new head */
 748                         q->next = dyn_v[k].head;
 749                         dyn_v[k].head = q;
 750              }
 751         }
 752
 753         /* Update current pointers/buckets values */
 754         V_curr_dyn_buckets = nbuckets;
 755         V_ipfw_dyn_v = dyn_v;
 756
 757         IPFW_WUNLOCK(chain);
 758
 759         IPFW_UH_WUNLOCK(chain);
 760
 761         /* Start periodic callout on initial creation */
 762         if (dyn_v_old == NULL) {
 763                 callout_reset_on(&V_ipfw_timeout, hz, ipfw_dyn_tick, curvnet, 0);
 764                 return (0);
 765         }
 766
 767         /* Destroy all mutexes */
 768         for (i = 0 ; i < nbuckets_old ; i++)
 769                 IPFW_BUCK_LOCK_DESTROY(&dyn_v_old[i]);
 770
 771         /* Free old hash */
 772         free(dyn_v_old, M_IPFW);
 773
 774         return 0;
 775 }
 776
 777 /**
 778  * Install state of type 'type' for a dynamic session.
 779  * The hash table contains two type of rules:
 780  * - regular rules (O_KEEP_STATE)
 781  * - rules for sessions with limited number of sess per user
 782  *   (O_LIMIT). When they are created, the parent is
 783  *   increased by 1, and decreased on delete. In this case,
 784  *   the third parameter is the parent rule and not the chain.
 785  * - "parent" rules for the above (O_LIMIT_PARENT).
 786  */
 787 static ipfw_dyn_rule *
 788 add_dyn_rule(const struct ipfw_flow_id *id, int i, uint8_t dyn_type,
 789     struct ip_fw *rule, uint16_t kidx)
 790 {
 791         ipfw_dyn_rule *r;
 792
 793         IPFW_BUCK_ASSERT(i);
 794
 795         r = uma_zalloc(V_ipfw_dyn_rule_zone, M_NOWAIT | M_ZERO);
 796         if (r == NULL) {
 797                 if (last_log != time_uptime) {
 798                         last_log = time_uptime;
 799                         log(LOG_DEBUG,
 800                             "ipfw: Cannot allocate dynamic state, "
 801                             "consider increasing net.inet.ip.fw.dyn_max\n");
 802                 }
 803                 return NULL;
 804         }
 805         ipfw_dyn_count++;
 806
 807         /*
 808          * refcount on parent is already incremented, so
 809          * it is safe to use parent unlocked.
 810          */
 811         if (dyn_type == O_LIMIT) {
 812                 ipfw_dyn_rule *parent = (ipfw_dyn_rule *)rule;
 813                 if ( parent->dyn_type != O_LIMIT_PARENT)
 814                         panic("invalid parent");
 815                 r->parent = parent;
 816                 rule = parent->rule;
 817         }
 818
 819         r->id = *id;
 820         r->expire = time_uptime + V_dyn_syn_lifetime;
 821         r->rule = rule;
 822         r->dyn_type = dyn_type;
 823         IPFW_ZERO_DYN_COUNTER(r);
 824         r->count = 0;
 825         r->kidx = kidx;
 826         r->bucket = i;
 827         r->next = V_ipfw_dyn_v[i].head;
 828         V_ipfw_dyn_v[i].head = r;
 829         DEB(print_dyn_rule(id, dyn_type, "add dyn entry", "total");)
 830         return r;
 831 }
 832
 833 /**
 834  * lookup dynamic parent rule using pkt and rule as search keys.
 835  * If the lookup fails, then install one.
 836  */
 837 static ipfw_dyn_rule *
 838 lookup_dyn_parent(const struct ipfw_flow_id *pkt, int *pindex,
 839     struct ip_fw *rule, uint16_t kidx)
 840 {
 841         ipfw_dyn_rule *q;
 842         int i, is_v6;
 843
 844         is_v6 = IS_IP6_FLOW_ID(pkt);
 845         i = hash_packet( pkt, V_curr_dyn_buckets );
 846         *pindex = i;
 847         IPFW_BUCK_LOCK(i);
 848         for (q = V_ipfw_dyn_v[i].head ; q != NULL ; q=q->next)
 849                 if (q->dyn_type == O_LIMIT_PARENT &&
 850                     kidx == q->kidx &&
 851                     rule == q->rule &&
 852                     pkt->proto == q->id.proto &&
 853                     pkt->src_port == q->id.src_port &&
 854                     pkt->dst_port == q->id.dst_port &&
 855                     (
 856                         (is_v6 &&
 857                          IN6_ARE_ADDR_EQUAL(&(pkt->src_ip6),
 858                                 &(q->id.src_ip6)) &&
 859                          IN6_ARE_ADDR_EQUAL(&(pkt->dst_ip6),
 860                                 &(q->id.dst_ip6))) ||
 861                         (!is_v6 &&
 862                          pkt->src_ip == q->id.src_ip &&
 863                          pkt->dst_ip == q->id.dst_ip)
 864                     )
 865                 ) {
 866                         q->expire = time_uptime + V_dyn_short_lifetime;
 867                         DEB(print_dyn_rule(pkt, q->dyn_type,
 868                             "lookup_dyn_parent found", "");)
 869                         return q;
 870                 }
 871
 872         /* Add virtual limiting rule */
 873         return add_dyn_rule(pkt, i, O_LIMIT_PARENT, rule, kidx);
 874 }
 875
 876 /**
 877  * Install dynamic state for rule type cmd->o.opcode
 878  *
 879  * Returns 1 (failure) if state is not installed because of errors or because
 880  * session limitations are enforced.
 881  */
 882 int
 883 ipfw_dyn_install_state(struct ip_fw_chain *chain, struct ip_fw *rule,
 884     ipfw_insn_limit *cmd, struct ip_fw_args *args, uint32_t tablearg)
 885 {
 886         ipfw_dyn_rule *q;
 887         int i;
 888
 889         DEB(print_dyn_rule(&args->f_id, cmd->o.opcode, "install_state",
 890             (cmd->o.arg1 == 0 ? "": DYN_STATE_OBJ(chain, &cmd->o)->name));)
 891
 892         i = hash_packet(&args->f_id, V_curr_dyn_buckets);
 893
 894         IPFW_BUCK_LOCK(i);
 895
 896         q = lookup_dyn_rule_locked(&args->f_id, NULL, i, NULL, cmd->o.arg1);
 897         if (q != NULL) {        /* should never occur */
 898                 DEB(
 899                 if (last_log != time_uptime) {
 900                         last_log = time_uptime;
 901                         printf("ipfw: %s: entry already present, done\n",
 902                             __func__);
 903                 })
 904                 IPFW_BUCK_UNLOCK(i);
 905                 return (0);
 906         }
 907
 908         /*
 909          * State limiting is done via uma(9) zone limiting.
 910          * Save pointer to newly-installed rule and reject
 911          * packet if add_dyn_rule() returned NULL.
 912          * Note q is currently set to NULL.
 913          */
 914
 915         switch (cmd->o.opcode) {
 916         case O_KEEP_STATE:      /* bidir rule */
 917                 q = add_dyn_rule(&args->f_id, i, O_KEEP_STATE, rule,
 918                     cmd->o.arg1);
 919                 break;
 920
 921         case O_LIMIT: {         /* limit number of sessions */
 922                 struct ipfw_flow_id id;
 923                 ipfw_dyn_rule *parent;
 924                 uint32_t conn_limit;
 925                 uint16_t limit_mask = cmd->limit_mask;
 926                 int pindex;
 927
 928                 conn_limit = IP_FW_ARG_TABLEARG(chain, cmd->conn_limit, limit);
 929
 930                 DEB(
 931                 if (cmd->conn_limit == IP_FW_TARG)
 932                         printf("ipfw: %s: O_LIMIT rule, conn_limit: %u "
 933                             "(tablearg)\n", __func__, conn_limit);
 934                 else
 935                         printf("ipfw: %s: O_LIMIT rule, conn_limit: %u\n",
 936                             __func__, conn_limit);
 937                 )
 938
 939                 id.dst_ip = id.src_ip = id.dst_port = id.src_port = 0;
 940                 id.proto = args->f_id.proto;
 941                 id.addr_type = args->f_id.addr_type;
 942                 id.fib = M_GETFIB(args->m);
 943
 944                 if (IS_IP6_FLOW_ID (&(args->f_id))) {
 945                         bzero(&id.src_ip6, sizeof(id.src_ip6));
 946                         bzero(&id.dst_ip6, sizeof(id.dst_ip6));
 947
 948                         if (limit_mask & DYN_SRC_ADDR)
 949                                 id.src_ip6 = args->f_id.src_ip6;
 950                         if (limit_mask & DYN_DST_ADDR)
 951                                 id.dst_ip6 = args->f_id.dst_ip6;
 952                 } else {
 953                         if (limit_mask & DYN_SRC_ADDR)
 954                                 id.src_ip = args->f_id.src_ip;
 955                         if (limit_mask & DYN_DST_ADDR)
 956                                 id.dst_ip = args->f_id.dst_ip;
 957                 }
 958                 if (limit_mask & DYN_SRC_PORT)
 959                         id.src_port = args->f_id.src_port;
 960                 if (limit_mask & DYN_DST_PORT)
 961                         id.dst_port = args->f_id.dst_port;
 962
 963                 /*
 964                  * We have to release lock for previous bucket to
 965                  * avoid possible deadlock
 966                  */
 967                 IPFW_BUCK_UNLOCK(i);
 968
 969                 parent = lookup_dyn_parent(&id, &pindex, rule, cmd->o.arg1);
 970                 if (parent == NULL) {
 971                         printf("ipfw: %s: add parent failed\n", __func__);
 972                         IPFW_BUCK_UNLOCK(pindex);
 973                         return (1);
 974                 }
 975
 976                 if (parent->count >= conn_limit) {
 977                         if (V_fw_verbose && last_log != time_uptime) {
 978                                 char sbuf[24];
 979                                 last_log = time_uptime;
 980                                 snprintf(sbuf, sizeof(sbuf),
 981                                     "%d drop session",
 982                                     parent->rule->rulenum);
 983                                 print_dyn_rule_flags(&args->f_id,
 984                                     cmd->o.opcode,
 985                                     LOG_SECURITY | LOG_DEBUG,
 986                                     sbuf, "too many entries");
 987                         }
 988                         IPFW_BUCK_UNLOCK(pindex);
 989                         return (1);
 990                 }
 991                 /* Increment counter on parent */
 992                 parent->count++;
 993                 IPFW_BUCK_UNLOCK(pindex);
 994
 995                 IPFW_BUCK_LOCK(i);
 996                 q = add_dyn_rule(&args->f_id, i, O_LIMIT,
 997                     (struct ip_fw *)parent, cmd->o.arg1);
 998                 if (q == NULL) {
 999                         /* Decrement index and notify caller */
1000                         IPFW_BUCK_UNLOCK(i);
1001                         IPFW_BUCK_LOCK(pindex);
1002                         parent->count--;
1003                         IPFW_BUCK_UNLOCK(pindex);
1004                         return (1);
1005                 }
1006                 break;
1007         }
1008         default:
1009                 printf("ipfw: %s: unknown dynamic rule type %u\n",
1010                     __func__, cmd->o.opcode);
1011         }
1012
1013         if (q == NULL) {
1014                 IPFW_BUCK_UNLOCK(i);
1015                 return (1);     /* Notify caller about failure */
1016         }
1017
1018         dyn_update_proto_state(q, &args->f_id, NULL, MATCH_FORWARD);
1019         IPFW_BUCK_UNLOCK(i);
1020         return (0);
1021 }
1022
1023 /*
1024  * Queue keepalive packets for given dynamic rule
1025  */
1026 static struct mbuf **
1027 ipfw_dyn_send_ka(struct mbuf **mtailp, ipfw_dyn_rule *q)
1028 {
1029         struct mbuf *m_rev, *m_fwd;
1030
1031         m_rev = (q->state & ACK_REV) ? NULL :
1032             ipfw_send_pkt(NULL, &(q->id), q->ack_rev - 1, q->ack_fwd, TH_SYN);
1033         m_fwd = (q->state & ACK_FWD) ? NULL :
1034             ipfw_send_pkt(NULL, &(q->id), q->ack_fwd - 1, q->ack_rev, 0);
1035
1036         if (m_rev != NULL) {
1037                 *mtailp = m_rev;
1038                 mtailp = &(*mtailp)->m_nextpkt;
1039         }
1040         if (m_fwd != NULL) {
1041                 *mtailp = m_fwd;
1042                 mtailp = &(*mtailp)->m_nextpkt;
1043         }
1044
1045         return (mtailp);
1046 }
1047
1048 /*
1049  * This procedure is used to perform various maintenance
1050  * on dynamic hash list. Currently it is called every second.
1051  */
1052 static void
1053 ipfw_dyn_tick(void * vnetx)
1054 {
1055         struct ip_fw_chain *chain;
1056         int check_ka = 0;
1057 #ifdef VIMAGE
1058         struct vnet *vp = vnetx;
1059 #endif
1060
1061         CURVNET_SET(vp);
1062
1063         chain = &V_layer3_chain;
1064
1065         /* Run keepalive checks every keepalive_period iff ka is enabled */
1066         if ((V_dyn_keepalive_last + V_dyn_keepalive_period <= time_uptime) &&
1067             (V_dyn_keepalive != 0)) {
1068                 V_dyn_keepalive_last = time_uptime;
1069                 check_ka = 1;
1070         }
1071
1072         check_dyn_rules(chain, NULL, check_ka, 1);
1073
1074         callout_reset_on(&V_ipfw_timeout, hz, ipfw_dyn_tick, vnetx, 0);
1075
1076         CURVNET_RESTORE();
1077 }
1078
1079
1080 /*
1081  * Walk through all dynamic states doing generic maintenance:
1082  * 1) free expired states
1083  * 2) free all states based on deleted rule / set
1084  * 3) send keepalives for states if needed
1085  *
1086  * @chain - pointer to current ipfw rules chain
1087  * @rule - delete all states originated by given rule if != NULL
1088  * @set - delete all states originated by any rule in set @set if != RESVD_SET
1089  * @check_ka - perform checking/sending keepalives
1090  * @timer - indicate call from timer routine.
1091  *
1092  * Timer routine must call this function unlocked to permit
1093  * sending keepalives/resizing table.
1094  *
1095  * Others has to call function with IPFW_UH_WLOCK held.
1096  * Additionally, function assume that dynamic rule/set is
1097  * ALREADY deleted so no new states can be generated by
1098  * 'deleted' rules.
1099  *
1100  * Write lock is needed to ensure that unused parent rules
1101  * are not freed by other instance (see stage 2, 3)
1102  */
1103 static void
1104 check_dyn_rules(struct ip_fw_chain *chain, ipfw_range_tlv *rt,
1105     int check_ka, int timer)
1106 {
1107         struct mbuf *m0, *m, *mnext, **mtailp;
1108         struct ip *h;
1109         int i, dyn_count, new_buckets = 0, max_buckets;
1110         int expired = 0, expired_limits = 0, parents = 0, total = 0;
1111         ipfw_dyn_rule *q, *q_prev, *q_next;
1112         ipfw_dyn_rule *exp_head, **exptailp;
1113         ipfw_dyn_rule *exp_lhead, **expltailp;
1114
1115         KASSERT(V_ipfw_dyn_v != NULL, ("%s: dynamic table not allocated",
1116             __func__));
1117
1118         /* Avoid possible LOR */
1119         KASSERT(!check_ka || timer, ("%s: keepalive check with lock held",
1120             __func__));
1121
1122         /*
1123          * Do not perform any checks if we currently have no dynamic states
1124          */
1125         if (DYN_COUNT == 0)
1126                 return;
1127
1128         /* Expired states */
1129         exp_head = NULL;
1130         exptailp = &exp_head;
1131
1132         /* Expired limit states */
1133         exp_lhead = NULL;
1134         expltailp = &exp_lhead;
1135
1136         /*
1137          * We make a chain of packets to go out here -- not deferring
1138          * until after we drop the IPFW dynamic rule lock would result
1139          * in a lock order reversal with the normal packet input -> ipfw
1140          * call stack.
1141          */
1142         m0 = NULL;
1143         mtailp = &m0;
1144
1145         /* Protect from hash resizing */
1146         if (timer != 0)
1147                 IPFW_UH_WLOCK(chain);
1148         else
1149                 IPFW_UH_WLOCK_ASSERT(chain);
1150
1151 #define NEXT_RULE()     { q_prev = q; q = q->next ; continue; }
1152
1153         /* Stage 1: perform requested deletion */
1154         for (i = 0 ; i < V_curr_dyn_buckets ; i++) {
1155                 IPFW_BUCK_LOCK(i);
1156                 for (q = V_ipfw_dyn_v[i].head, q_prev = q; q ; ) {
1157                         /* account every rule */
1158                         total++;
1159
1160                         /* Skip parent rules at all */
1161                         if (q->dyn_type == O_LIMIT_PARENT) {
1162                                 parents++;
1163                                 NEXT_RULE();
1164                         }
1165
1166                         /*
1167                          * Remove rules which are:
1168                          * 1) expired
1169                          * 2) matches deletion range
1170                          */
1171                         if ((TIME_LEQ(q->expire, time_uptime)) ||
1172                             (rt != NULL && ipfw_match_range(q->rule, rt))) {
1173                                 if (TIME_LE(time_uptime, q->expire) &&
1174                                     q->dyn_type == O_KEEP_STATE &&
1175                                     V_dyn_keep_states != 0) {
1176                                         /*
1177                                          * Do not delete state if
1178                                          * it is not expired and
1179                                          * dyn_keep_states is ON.
1180                                          * However we need to re-link it
1181                                          * to any other stable rule
1182                                          */
1183                                         q->rule = chain->default_rule;
1184                                         NEXT_RULE();
1185                                 }
1186
1187                                 /* Unlink q from current list */
1188                                 q_next = q->next;
1189                                 if (q == V_ipfw_dyn_v[i].head)
1190                                         V_ipfw_dyn_v[i].head = q_next;
1191                                 else
1192                                         q_prev->next = q_next;
1193
1194                                 q->next = NULL;
1195
1196                                 /* queue q to expire list */
1197                                 if (q->dyn_type != O_LIMIT) {
1198                                         *exptailp = q;
1199                                         exptailp = &(*exptailp)->next;
1200                                         DEB(print_dyn_rule(&q->id, q->dyn_type,
1201                                             "unlink entry", "left");
1202                                         )
1203                                 } else {
1204                                         /* Separate list for limit rules */
1205                                         *expltailp = q;
1206                                         expltailp = &(*expltailp)->next;
1207                                         expired_limits++;
1208                                         DEB(print_dyn_rule(&q->id, q->dyn_type,
1209                                             "unlink limit entry", "left");
1210                                         )
1211                                 }
1212
1213                                 q = q_next;
1214                                 expired++;
1215                                 continue;
1216                         }
1217
1218                         /*
1219                          * Check if we need to send keepalive:
1220                          * we need to ensure if is time to do KA,
1221                          * this is established TCP session, and
1222                          * expire time is within keepalive interval
1223                          */
1224                         if ((check_ka != 0) && (q->id.proto == IPPROTO_TCP) &&
1225                             ((q->state & BOTH_SYN) == BOTH_SYN) &&
1226                             (TIME_LEQ(q->expire, time_uptime +
1227                               V_dyn_keepalive_interval)))
1228                                 mtailp = ipfw_dyn_send_ka(mtailp, q);
1229
1230                         NEXT_RULE();
1231                 }
1232                 IPFW_BUCK_UNLOCK(i);
1233         }
1234
1235         /* Stage 2: decrement counters from O_LIMIT parents */
1236         if (expired_limits != 0) {
1237                 /*
1238                  * XXX: Note that deleting set with more than one
1239                  * heavily-used LIMIT rules can result in overwhelming
1240                  * locking due to lack of per-hash value sorting
1241                  *
1242                  * We should probably think about:
1243                  * 1) pre-allocating hash of size, say,
1244                  * MAX(16, V_curr_dyn_buckets / 1024)
1245                  * 2) checking if expired_limits is large enough
1246                  * 3) If yes, init hash (or its part), re-link
1247                  * current list and start decrementing procedure in
1248                  * each bucket separately
1249                  */
1250
1251                 /*
1252                  * Small optimization: do not unlock bucket until
1253                  * we see the next item resides in different bucket
1254                  */
1255                 if (exp_lhead != NULL) {
1256                         i = exp_lhead->parent->bucket;
1257                         IPFW_BUCK_LOCK(i);
1258                 }
1259                 for (q = exp_lhead; q != NULL; q = q->next) {
1260                         if (i != q->parent->bucket) {
1261                                 IPFW_BUCK_UNLOCK(i);
1262                                 i = q->parent->bucket;
1263                                 IPFW_BUCK_LOCK(i);
1264                         }
1265
1266                         /* Decrease parent refcount */
1267                         q->parent->count--;
1268                 }
1269                 if (exp_lhead != NULL)
1270                         IPFW_BUCK_UNLOCK(i);
1271         }
1272
1273         /*
1274          * We protectet ourselves from unused parent deletion
1275          * (from the timer function) by holding UH write lock.
1276          */
1277
1278         /* Stage 3: remove unused parent rules */
1279         if ((parents != 0) && (expired != 0)) {
1280                 for (i = 0 ; i < V_curr_dyn_buckets ; i++) {
1281                         IPFW_BUCK_LOCK(i);
1282                         for (q = V_ipfw_dyn_v[i].head, q_prev = q ; q ; ) {
1283                                 if (q->dyn_type != O_LIMIT_PARENT)
1284                                         NEXT_RULE();
1285
1286                                 if (q->count != 0)
1287                                         NEXT_RULE();
1288
1289                                 /* Parent rule without consumers */
1290
1291                                 /* Unlink q from current list */
1292                                 q_next = q->next;
1293                                 if (q == V_ipfw_dyn_v[i].head)
1294                                         V_ipfw_dyn_v[i].head = q_next;
1295                                 else
1296                                         q_prev->next = q_next;
1297
1298                                 q->next = NULL;
1299
1300                                 /* Add to expired list */
1301                                 *exptailp = q;
1302                                 exptailp = &(*exptailp)->next;
1303
1304                                 DEB(print_dyn_rule(&q->id, q->dyn_type,
1305                                     "unlink parent entry", "left");
1306                                 )
1307
1308                                 expired++;
1309
1310                                 q = q_next;
1311                         }
1312                         IPFW_BUCK_UNLOCK(i);
1313                 }
1314         }
1315
1316 #undef NEXT_RULE
1317
1318         if (timer != 0) {
1319                 /*
1320                  * Check if we need to resize hash:
1321                  * if current number of states exceeds number of buckes in hash,
1322                  * grow hash size to the minimum power of 2 which is bigger than
1323                  * current states count. Limit hash size by 64k.
1324                  */
1325                 max_buckets = (V_dyn_buckets_max > 65536) ?
1326                     65536 : V_dyn_buckets_max;
1327
1328                 dyn_count = DYN_COUNT;
1329
1330                 if ((dyn_count > V_curr_dyn_buckets * 2) &&
1331                     (dyn_count < max_buckets)) {
1332                         new_buckets = V_curr_dyn_buckets;
1333                         while (new_buckets < dyn_count) {
1334                                 new_buckets *= 2;
1335
1336                                 if (new_buckets >= max_buckets)
1337                                         break;
1338                         }
1339                 }
1340
1341                 IPFW_UH_WUNLOCK(chain);
1342         }
1343
1344         /* Finally delete old states ad limits if any */
1345         for (q = exp_head; q != NULL; q = q_next) {
1346                 q_next = q->next;
1347                 uma_zfree(V_ipfw_dyn_rule_zone, q);
1348                 ipfw_dyn_count--;
1349         }
1350
1351         for (q = exp_lhead; q != NULL; q = q_next) {
1352                 q_next = q->next;
1353                 uma_zfree(V_ipfw_dyn_rule_zone, q);
1354                 ipfw_dyn_count--;
1355         }
1356
1357         /*
1358          * The rest code MUST be called from timer routine only
1359          * without holding any locks
1360          */
1361         if (timer == 0)
1362                 return;
1363
1364         /* Send keepalive packets if any */
1365         for (m = m0; m != NULL; m = mnext) {
1366                 mnext = m->m_nextpkt;
1367                 m->m_nextpkt = NULL;
1368                 h = mtod(m, struct ip *);
1369                 if (h->ip_v == 4)
1370                         ip_output(m, NULL, NULL, 0, NULL, NULL);
1371 #ifdef INET6
1372                 else
1373                         ip6_output(m, NULL, NULL, 0, NULL, NULL, NULL);
1374 #endif
1375         }
1376
1377         /* Run table resize without holding any locks */
1378         if (new_buckets != 0)
1379                 resize_dynamic_table(chain, new_buckets);
1380 }
1381
1382 /*
1383  * Deletes all dynamic rules originated by given rule or all rules in
1384  * given set. Specify RESVD_SET to indicate set should not be used.
1385  * @chain - pointer to current ipfw rules chain
1386  * @rr - delete all states originated by rules in matched range.
1387  *
1388  * Function has to be called with IPFW_UH_WLOCK held.
1389  * Additionally, function assume that dynamic rule/set is
1390  * ALREADY deleted so no new states can be generated by
1391  * 'deleted' rules.
1392  */
1393 void
1394 ipfw_expire_dyn_rules(struct ip_fw_chain *chain, ipfw_range_tlv *rt)
1395 {
1396
1397         check_dyn_rules(chain, rt, 0, 0);
1398 }
1399
1400 /*
1401  * Check if rule contains at least one dynamic opcode.
1402  *
1403  * Returns 1 if such opcode is found, 0 otherwise.
1404  */
1405 int
1406 ipfw_is_dyn_rule(struct ip_fw *rule)
1407 {
1408         int cmdlen, l;
1409         ipfw_insn *cmd;
1410
1411         l = rule->cmd_len;
1412         cmd = rule->cmd;
1413         cmdlen = 0;
1414         for ( ; l > 0 ; l -= cmdlen, cmd += cmdlen) {
1415                 cmdlen = F_LEN(cmd);
1416
1417                 switch (cmd->opcode) {
1418                 case O_LIMIT:
1419                 case O_KEEP_STATE:
1420                 case O_PROBE_STATE:
1421                 case O_CHECK_STATE:
1422                         return (1);
1423                 }
1424         }
1425
1426         return (0);
1427 }
1428
1429 void
1430 ipfw_dyn_init(struct ip_fw_chain *chain)
1431 {
1432
1433         V_ipfw_dyn_v = NULL;
1434         V_dyn_buckets_max = 256; /* must be power of 2 */
1435         V_curr_dyn_buckets = 256; /* must be power of 2 */
1436
1437         V_dyn_ack_lifetime = 300;
1438         V_dyn_syn_lifetime = 20;
1439         V_dyn_fin_lifetime = 1;
1440         V_dyn_rst_lifetime = 1;
1441         V_dyn_udp_lifetime = 10;
1442         V_dyn_short_lifetime = 5;
1443
1444         V_dyn_keepalive_interval = 20;
1445         V_dyn_keepalive_period = 5;
1446         V_dyn_keepalive = 1;    /* do send keepalives */
1447         V_dyn_keepalive_last = time_uptime;
1448
1449         V_dyn_max = 16384; /* max # of dynamic rules */
1450
1451         V_ipfw_dyn_rule_zone = uma_zcreate("IPFW dynamic rule",
1452             sizeof(ipfw_dyn_rule), NULL, NULL, NULL, NULL,
1453             UMA_ALIGN_PTR, 0);
1454
1455         /* Enforce limit on dynamic rules */
1456         uma_zone_set_max(V_ipfw_dyn_rule_zone, V_dyn_max);
1457
1458         callout_init(&V_ipfw_timeout, 1);
1459
1460         /*
1461          * This can potentially be done on first dynamic rule
1462          * being added to chain.
1463          */
1464         resize_dynamic_table(chain, V_curr_dyn_buckets);
1465         IPFW_ADD_OBJ_REWRITER(IS_DEFAULT_VNET(curvnet), dyn_opcodes);
1466 }
1467
1468 void
1469 ipfw_dyn_uninit(int pass)
1470 {
1471         int i;
1472
1473         if (pass == 0) {
1474                 callout_drain(&V_ipfw_timeout);
1475                 return;
1476         }
1477         IPFW_DEL_OBJ_REWRITER(IS_DEFAULT_VNET(curvnet), dyn_opcodes);
1478
1479         if (V_ipfw_dyn_v != NULL) {
1480                 /*
1481                  * Skip deleting all dynamic states -
1482                  * uma_zdestroy() does this more efficiently;
1483                  */
1484
1485                 /* Destroy all mutexes */
1486                 for (i = 0 ; i < V_curr_dyn_buckets ; i++)
1487                         IPFW_BUCK_LOCK_DESTROY(&V_ipfw_dyn_v[i]);
1488                 free(V_ipfw_dyn_v, M_IPFW);
1489                 V_ipfw_dyn_v = NULL;
1490         }
1491
1492         uma_zdestroy(V_ipfw_dyn_rule_zone);
1493 }
1494
1495 #ifdef SYSCTL_NODE
1496 /*
1497  * Get/set maximum number of dynamic states in given VNET instance.
1498  */
1499 static int
1500 sysctl_ipfw_dyn_max(SYSCTL_HANDLER_ARGS)
1501 {
1502         int error;
1503         unsigned int nstates;
1504
1505         nstates = V_dyn_max;
1506
1507         error = sysctl_handle_int(oidp, &nstates, 0, req);
1508         /* Read operation or some error */
1509         if ((error != 0) || (req->newptr == NULL))
1510                 return (error);
1511
1512         V_dyn_max = nstates;
1513         uma_zone_set_max(V_ipfw_dyn_rule_zone, V_dyn_max);
1514
1515         return (0);
1516 }
1517
1518 /*
1519  * Get current number of dynamic states in given VNET instance.
1520  */
1521 static int
1522 sysctl_ipfw_dyn_count(SYSCTL_HANDLER_ARGS)
1523 {
1524         int error;
1525         unsigned int nstates;
1526
1527         nstates = DYN_COUNT;
1528
1529         error = sysctl_handle_int(oidp, &nstates, 0, req);
1530
1531         return (error);
1532 }
1533 #endif
1534
1535 /*
1536  * Returns size of dynamic states in legacy format
1537  */
1538 int
1539 ipfw_dyn_len(void)
1540 {
1541
1542         return (V_ipfw_dyn_v == NULL) ? 0 :
1543                 (DYN_COUNT * sizeof(ipfw_dyn_rule));
1544 }
1545
1546 /*
1547  * Returns number of dynamic states.
1548  * Used by dump format v1 (current).
1549  */
1550 int
1551 ipfw_dyn_get_count(void)
1552 {
1553
1554         return (V_ipfw_dyn_v == NULL) ? 0 : DYN_COUNT;
1555 }
1556
1557 static void
1558 export_dyn_rule(ipfw_dyn_rule *src, ipfw_dyn_rule *dst)
1559 {
1560         uint16_t rulenum;
1561
1562         rulenum = (uint16_t)src->rule->rulenum;
1563         memcpy(dst, src, sizeof(*src));
1564         memcpy(&dst->rule, &rulenum, sizeof(rulenum));
1565         /*
1566          * store set number into high word of
1567          * dst->rule pointer.
1568          */
1569         memcpy((char *)&dst->rule + sizeof(rulenum), &src->rule->set,
1570             sizeof(src->rule->set));
1571         /*
1572          * store a non-null value in "next".
1573          * The userland code will interpret a
1574          * NULL here as a marker
1575          * for the last dynamic rule.
1576          */
1577         memcpy(&dst->next, &dst, sizeof(dst));
1578         dst->expire = TIME_LEQ(dst->expire, time_uptime) ?  0:
1579             dst->expire - time_uptime;
1580 }
1581
1582 /*
1583  * Fills int buffer given by @sd with dynamic states.
1584  * Used by dump format v1 (current).
1585  *
1586  * Returns 0 on success.
1587  */
1588 int
1589 ipfw_dump_states(struct ip_fw_chain *chain, struct sockopt_data *sd)
1590 {
1591         ipfw_dyn_rule *p;
1592         ipfw_obj_dyntlv *dst, *last;
1593         ipfw_obj_ctlv *ctlv;
1594         int i;
1595         size_t sz;
1596
1597         if (V_ipfw_dyn_v == NULL)
1598                 return (0);
1599
1600         IPFW_UH_RLOCK_ASSERT(chain);
1601
1602         ctlv = (ipfw_obj_ctlv *)ipfw_get_sopt_space(sd, sizeof(*ctlv));
1603         if (ctlv == NULL)
1604                 return (ENOMEM);
1605         sz = sizeof(ipfw_obj_dyntlv);
1606         ctlv->head.type = IPFW_TLV_DYNSTATE_LIST;
1607         ctlv->objsize = sz;
1608         last = NULL;
1609
1610         for (i = 0 ; i < V_curr_dyn_buckets; i++) {
1611                 IPFW_BUCK_LOCK(i);
1612                 for (p = V_ipfw_dyn_v[i].head ; p != NULL; p = p->next) {
1613                         dst = (ipfw_obj_dyntlv *)ipfw_get_sopt_space(sd, sz);
1614                         if (dst == NULL) {
1615                                 IPFW_BUCK_UNLOCK(i);
1616                                 return (ENOMEM);
1617                         }
1618
1619                         export_dyn_rule(p, &dst->state);
1620                         dst->head.length = sz;
1621                         dst->head.type = IPFW_TLV_DYN_ENT;
1622                         last = dst;
1623                 }
1624                 IPFW_BUCK_UNLOCK(i);
1625         }
1626
1627         if (last != NULL) /* mark last dynamic rule */
1628                 last->head.flags = IPFW_DF_LAST;
1629
1630         return (0);
1631 }
1632
1633 /*
1634  * Fill given buffer with dynamic states (legacy format).
1635  * IPFW_UH_RLOCK has to be held while calling.
1636  */
1637 void
1638 ipfw_get_dynamic(struct ip_fw_chain *chain, char **pbp, const char *ep)
1639 {
1640         ipfw_dyn_rule *p, *last = NULL;
1641         char *bp;
1642         int i;
1643
1644         if (V_ipfw_dyn_v == NULL)
1645                 return;
1646         bp = *pbp;
1647
1648         IPFW_UH_RLOCK_ASSERT(chain);
1649
1650         for (i = 0 ; i < V_curr_dyn_buckets; i++) {
1651                 IPFW_BUCK_LOCK(i);
1652                 for (p = V_ipfw_dyn_v[i].head ; p != NULL; p = p->next) {
1653                         if (bp + sizeof *p <= ep) {
1654                                 ipfw_dyn_rule *dst =
1655                                         (ipfw_dyn_rule *)bp;
1656
1657                                 export_dyn_rule(p, dst);
1658                                 last = dst;
1659                                 bp += sizeof(ipfw_dyn_rule);
1660                         }
1661                 }
1662                 IPFW_BUCK_UNLOCK(i);
1663         }
1664
1665         if (last != NULL) /* mark last dynamic rule */
1666                 bzero(&last->next, sizeof(last));
1667         *pbp = bp;
1668 }
1669 /* end of file */