functions.m4, classify.m4: Handle negative address ranges.

That is, a network can explicitly exclude an address range.  Ranges are
checked in order, so you carve out a hole in the middle of a range by
putting a negative range first for the hole first, and the big network
afterwards.

This involves a fairly major rearrangement of the address classification
machinery.  Again.

diff --git a/classify.m4 b/classify.m4
index 12ad314..819cce6 100644 (file)
--- a/classify.m4
+++ b/classify.m4
@@ -171,51 +171,132 @@ run ip6tables -t mangle -A out-classify -g out-classify-mcast \
 ## Build the input classification chains.  There's one chain `in-IFACE' for
 ## each local interface.  This chain does a further dispatch on the source
 ## address to the appropriate `mark-from-CLASS' chain for the source network
-## class.
+## class.  We also build a table mapping interface names to numbers (since
+## the names are so unhelpful).
 seen=:
+ifq=0
+ifmap=""
 for iface in $host_ifaces_<::>FWHOST; do
   ifname=${iface%=*}
   case $seen in *:$ifname:*) continue ;; esac
   seen=$seen$ifname:
+  addword ifmap $ifname=$ifq
+  ifq=$(( $ifq + 1 ))
   clearchain mangle:in-$ifname
   run ip46tables -t mangle -A in-classify -i $ifname -g in-$ifname
 done
 
-## Now populate the `in-IFACE' and `out-classify' chains.  We iterate over
-## the available networks and add addresses to the appropriate chains.  Also,
-## build up a map of which interfaces receive from which address ranged so
-## that we can finish the chains off properly later.  This contains entries
-## of the form IFACE=:ADDR:ADDR:...:
-ifnets=""
+## We do a first pass over nets first, and then the interfaces which those
+## networks reach.  During this pass, we populate the `out-classify' chains,
+## and we also build some lists so that we can do later passes over
+## interfaces first and then reaching networks.  This is complicated by
+## interface names being unhelpful.
+##
+## Here are the variables we maintain.
+##
+## ifmap               A list of entries IFACE=N mapping interface names to
+##                     numbers.
+##
+## ifnets_N            A space-separated list of networks reaching interface
+##                     number N.  This is used for building the matching
+##                     chains.
+##
+## ifaddrs_N           A bang-separated list of address ranges reaching
+##                     interface number N.  This is used for filtering out
+##                     known networks if the default network reaches the
+##                     interface.
 for net in $allnets; do
 
-  ## Determine the addresses and class for this network, and populate the
-  ## `out-classify' chains.
-  eval addr=\$net_inet_$net addr6=\$net_inet6_$net class=\$net_class_$net
-  case $class in virtual) continue ;; esac
-  trace "$net : $class"
-  for a in $addr; do
-    run iptables -t mangle -A out-classify -g mark-to-$class -d $a
+  ## Work through the interfaces that this network reaches.
+  for iface in $(net_interfaces FWHOST $net); do
+    case $iface in -) break ;; esac
+
+    ## Find a sequence number for this interface.
+    q=nil
+    for i in $ifmap; do
+      case "$i" in "$iface"=*) q=${i##*=}; break ;; esac
+    done
+    case $q in
+      nil)
+       echo >&2 "$0 INTERNAL ERROR: missing interface \`$iface'!"
+       exit 1
+       ;;
+    esac
+
+    ## Remember the reachability information.
+    addword ifnets_$q $net
   done
-  for a in $addr6; do
-    run ip6tables -t mangle -A out-classify -g mark-to-$class -d $a
+done
+
+## Build the `ifaddr_N' map and an `all-addresses' list.
+alladdrs=!
+trace "ifmap = $ifmap"
+for entry in $ifmap; do
+  iface=${entry%=*} q=${entry##*=}
+  eval nets=\$ifnets_$q
+  trace "iface $iface [$q] = $nets"
+  aa=!
+  for n in $nets; do
+    eval "addrs=\"\$net_inet_$n \$net_inet6_$n\""
+    trace "$iface $n addrs = $addrs"
+    for a in $addrs; do
+      case $aa in *!$a!*) ;; *) aa=$aa$a! ;; esac
+      case $alladdrs in *!$a!*) ;; *) alladdrs=$alladdrs$a! ;; esac
+    done
   done
+  eval ifaddrs_$q=\$aa
+  trace "iface $q = $iface; nets = $nets; addrs = $aa"
+trace "alladdrs = $alladdrs"
+done
 
-  ## Now work through the interfaces.
-  for iface in $(net_interfaces FWHOST $net); do
-    nets=""
-    case $iface in
+## Populate the `out-classify' chain, matching networks.
+prepare_to () { mode=goto fail=mark-to-$net_class_default; }
+matchnets -d mark-from : prepare_to out-classify "" 0 $allnets
 
-      -)
-       ## A special `no interface' marker: we should not receive packets
-       ## from this network at all.
-       continue
-       ;;
+## A `finish' hook for rejecting known address ranges arriving on a
+## default-reachable interface.
+finish_from_default () {
+  q=$1 chain=$2
+  eval addrs=\$ifaddrs_$q
+
+  for n in $allnets; do
+    eval addr=\$net_inet_$n addr6=\$net_inet6_$n
+    for a in $addr; do
+      case $a in !*) continue ;; esac
+      case $addrs in *"!$a!"*) continue ;; esac
+      run iptables -t mangle -A $chain -s $a -g bad-source-address
+    done
+    for a in $addr6; do
+      case $a in !*) continue ;; esac
+      case $addrs in *"!$a!"*) continue ;; esac
+      run ip6tables -t mangle -A $chain -s $a -g bad-source-address
+    done
+  done
+  run ip46tables -t mangle -A $chain -g in-default
+}
+
+## A `prepare' hook for input classification.  If the interface is
+## default-reachable, then we need to reject known address ranges before
+## dispatching to the default chain; otherwise just reject the packet.
+prepare_from () {
+  q=$1 flags=$2
+  case $flags in
+    *:default:*) mode=call finish="finish_from_default $q" ;;
+    *) mode=goto fail=bad-source-address ;;
+  esac
+}
 
-      *-+)
-       ## A special marker indicating a collection of point-to-point
-       ## interfaces.  We should match an address to a particular interface.
-       ## Later, we'll cap this chain off by rejecting all other traffic.
+## Populate the `in-IFACE' chains.
+for entry in $ifmap; do
+  iface=${entry%=*} q=${entry##*=}
+  eval nets=\$ifnets_$q
+
+  case $iface in
+    *-+)
+      ## A special marker indicating a collection of point-to-point
+      ## interfaces.  We should match an address to a particular interface.
+      chains=""
+      for net in $nets; do
        eval hosts=\$net_hosts_$net
        for host in $hosts; do
          eval ha=\$host_inet_$host ha6=\$host_inet6_$host
@@ -223,90 +304,36 @@ for net in $allnets; do
          for a in $ha; do
            run iptables -t mangle -A in-$iface \
                    -i ${iface%+}$host -s $a -g mark-from-$class
-           nets=$nets$a:
          done
          for a in $ha6; do
            run ip6tables -t mangle -A in-$iface \
                    -i ${iface%+}$host -s $a -g mark-from-$class
-           nets=$nets$a:
          done
        done
-       ;;
-
-      *)
-       ## A normal interface.  Classify incoming traffic according to the
-       ## source address.
-       trace "$net : $class -> $iface"
-       for a in $addr; do
-         run iptables -t mangle -A in-$iface -g mark-from-$class -s $a
-         nets=$nets$a:
-       done
-       for a in $addr6; do
-         run ip6tables -t mangle -A in-$iface -g mark-from-$class -s $a
-         nets=$nets$a:
-       done
-       case $net in default) nets=${nets}default: ;; esac
-       ;;
-    esac
-
-    ## Record that this interface receives traffic from this network.
-    unset nifnets
-    foundp=nil
-    for ifnet in $ifnets; do
-      case $ifnet in
-       $iface=*:$net:*) addword nifnets $ifnet; foundp=t ;;
-       $iface=*) addword nifnets $ifnet$nets; foundp=t ;;
-       *) addword nifnets $ifnet ;;
-      esac
-    done
-    case $foundp in nil) addword nifnets $iface=:$nets ;; esac
-    ifnets=$nifnets
-
-  done
-done
-
-## Wrap up all of the `in-IFACE' chains.  A chain which matches the `default'
-## net should have unmatched but known networks blocked off, and then chain
-## onto `in-default'.  Other chains should just chain onto
-## `bad-source-address'.
-trace "ifnets = $ifnets"
-for ifnet in $ifnets; do
-  iface=${ifnet%%=*} nets=${ifnet#*=}
-  case $nets in
-    *:default:*)
-      for n in $allnets; do
-       eval addr=\$net_inet_$n addr6=\$net_inet6_$n
-       for a in $addr; do
-         case $nets in *:$a:*) continue ;; esac
-         nets=$nets$a
-         run iptables -t mangle -A in-$iface -s $a -g bad-source-address
-       done
-       for a in $addr6; do
-         case $nets in *:$a:*) continue ;; esac
-         nets=$nets$a
-         run ip6tables -t mangle -A in-$iface -s $a -g bad-source-address
-       done
       done
-      run ip46tables -t mangle -A in-$iface -g in-default
+      run ip46tables -t mangle -A in-$iface -g bad-source-address
       ;;
     *)
-      run ip46tables -t mangle -A in-$iface -g bad-source-address
+      matchnets -s mark-from : "prepare_from $q" in-$iface "" 0 $nets
       ;;
   esac
 done
 
-## Fill in the black holes in the network.
+## Fill in the black holes in the network.  Some of these might actually be
+## known networks, so don't fill those in again.
 for addr in \
        10.0.0.0/8 172.16.0.0/12 192.168.0.0/16 \
        127.0.0.0/8 \
        192.0.2.0/24 198.51.100.0/24 203.0.113.0/24
 do
+  case $alladdrs in *!$addr!*) continue ;; esac
   run iptables -t mangle -A in-default -s $addr -g bad-source-address
 done
 for addr in \
        fc00::/7 \
        2001:db8::/32
 do
+  case $alladdrs in *!$addr!*) continue ;; esac
   run ip6tables -t mangle -A in-default -s $addr -g bad-source-address
 done
 run ip46tables -t mangle -A in-default -g mark-from-$net_class_default
@@ -317,7 +344,6 @@ m4_divert(92)m4_dnl
 for iface in $defaultifaces; do
   run ip46tables -t mangle -A in-$iface -g in-default
 done
-run ip46tables -t mangle -A out-classify -g mark-to-$net_class_default
 run ip46tables -t mangle -A PREROUTING -j in-classify
 run ip46tables -t mangle -A PREROUTING -j out-classify
 

diff --git a/functions.m4 b/functions.m4
index 0ebba30..16c07c8 100644 (file)
--- a/functions.m4
+++ b/functions.m4
@@ -534,6 +534,115 @@ iface () {
   done
 }
 
+## Build rules which match a particular collection of networks.
+## Specifically, use the address-comparison operator OPT (typically `-s' or
+## `-d') to match the addresses of NOT, writing the rules to the chain
+## BASESUFFIX.  If we find a match, dispatch to WIN-CLASS, where CLASS is
+## the class of the matching network.  In order to deal with networks
+## containing negative address ranges, more chains may need to be
+## constructed; they will be named BASE#Q for sequence numbers Q starting
+## with NEXT.  All of this happens on the `mangle' table, and there isn't
+## (currently) a way to tweak this.
+##
+## The FLAGS gather additional interesting information about the job,
+## separated by colons.  The only flag currently is :default: which means
+## that the default network was listed.
+##
+## Finally, there is a hook PREPARE which is called just in advance of
+## processing the final network, passing it the argument FLAGS.  (The PREPARE
+## string will be subjected to shell word-splitting, so it can provide some
+## arguments of its own if it wants.)  It should set `mode' to indicate how
+## the chain should be finished.
+##
+## goto                If no networks matched, then issue a final `goto' to the
+##             chain named by the variable `fail'.
+##
+## call                Run `$finish CHAIN' to write final rules to the named CHAIN
+##             (which may be suffixed from the original BASE argument if
+##             this was necessary).  This function will arrange to call
+##             these rules if no networks match.
+##
+## ret         If no network matches then return (maybe by falling off the
+##             end of the chain).
+matchnets () {
+  local opt win flags prepare base suffix next net lose splitp
+  opt=$1 win=$2 flags=$3 prepare=$4 base=$5 suffix=$6 next=$7 net=$8
+  shift 8
+
+  ## If this is the default network, then set the flag.
+  case "$net" in default) flags=${flags}default: ;; esac
+
+  ## Do an initial pass over the addresses to see whether there are any
+  ## negative ranges.  If so, we'll need to split.  See also the standard
+  ## joke about soup.
+  splitp=nil
+  eval "addrs=\"\$net_inet_$net \$net_inet6_$net\""
+  for a in $addrs; do case $a in !*) splitp=t; break ;; esac; done
+
+  trace "MATCHNETS [splitp $splitp] $opt $win $flags [$prepare] $base $suffix $next : $net $*"
+
+  ## Work out how to handle matches against negative address ranges.  If this
+  ## is the last network, invoke the PREPARE hook to find out.  Otherwise, if
+  ## we have to split the chain, recursively build the target here.
+  case $splitp,$# in
+    t,0 | nil,0)
+      $prepare $flags
+      case $splitp,$mode in
+       *,goto)
+         lose="-g $fail"
+         ;;
+       *,ret)
+         lose="-j RETURN"
+         ;;
+       t,call)
+         clearchain mangle:$base#$next
+         lose="-g $base#$next"
+         ;;
+       nil,call)
+         ;;
+      esac
+      ;;
+    t,*)
+      clearchain mangle:$base#$next
+      matchnets $opt $win $flags "$prepare" \
+       $base \#$next $(( $next + 1 )) "$@"
+      lose="-g $base#$next" mode=goto
+      ;;
+    *)
+      mode=continue
+      ;;
+  esac
+
+  ## Populate the chain with rules to match the necessary networks.
+  eval addr=\$net_inet_$net addr6=\$net_inet6_$net class=\$net_class_$net
+  for a in $addr; do
+    case $a in
+      !*) run iptables -t mangle -A $base$suffix $lose $opt ${a#!} ;;
+      *) run iptables -t mangle -A $base$suffix -g $win-$class $opt $a ;;
+    esac
+  done
+  for a in $addr6; do
+    case $a in
+      !*) run ip6tables -t mangle -A $base$suffix $lose $opt ${a#!} ;;
+      *) run ip6tables -t mangle -A $base$suffix -g $win-$class $opt $a ;;
+    esac
+  done
+
+  ## Wrap up the chain appropriately.  If we didn't split and there are more
+  ## networks to handle then append the necessary rules now.  (If we did
+  ## split, then we already wrote the rules for them above.)  If there are no
+  ## more networks then consult the `mode' setting to find out what to do.
+  case $splitp,$#,$mode in
+    *,0,ret) ;;
+    *,*,goto) run ip46tables -t mangle -A $base$suffix $lose ;;
+    t,0,call) $finish $base#$next ;;
+    nil,0,call) $finish $base$suffix ;;
+    nil,*,*)
+      matchnets $opt $win $flags "$prepare" $base "$suffix" $next "$@"
+      ;;
+  esac
+}
+
 ## net_interfaces HOST NET
 ##
 ## Determine the interfaces on which packets may plausibly arrive from the