| 1 | ;;; -*-lisp-*- |
| 2 | ;;; |
| 3 | ;;; Network (numbering) tools |
| 4 | ;;; |
| 5 | ;;; (c) 2006 Straylight/Edgeware |
| 6 | ;;; |
| 7 | |
| 8 | ;;;----- Licensing notice --------------------------------------------------- |
| 9 | ;;; |
| 10 | ;;; This program is free software; you can redistribute it and/or modify |
| 11 | ;;; it under the terms of the GNU General Public License as published by |
| 12 | ;;; the Free Software Foundation; either version 2 of the License, or |
| 13 | ;;; (at your option) any later version. |
| 14 | ;;; |
| 15 | ;;; This program is distributed in the hope that it will be useful, |
| 16 | ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 17 | ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 18 | ;;; GNU General Public License for more details. |
| 19 | ;;; |
| 20 | ;;; You should have received a copy of the GNU General Public License |
| 21 | ;;; along with this program; if not, write to the Free Software Foundation, |
| 22 | ;;; Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
| 23 | |
| 24 | (in-package #:net) |
| 25 | |
| 26 | ;;;-------------------------------------------------------------------------- |
| 27 | ;;; Various random utilities. |
| 28 | |
| 29 | (declaim (inline mask)) |
| 30 | (defun mask (n) |
| 31 | "Return 2^N - 1: i.e., a mask of N set bits." |
| 32 | (1- (ash 1 n))) |
| 33 | |
| 34 | (defun find-first-bit-transition |
| 35 | (mask &optional (low 0) (high (integer-length mask))) |
| 36 | "Find the first (lowest bit-position) transition in MASK within the bounds. |
| 37 | |
| 38 | The LOW bound is inclusive; the high bound is exclusive. A transition is |
| 39 | a change from zero to one, or vice-versa. The return value is the |
| 40 | upper (exclusive) bound on the initial run, and the lower (inclusive) |
| 41 | bound on the new run. |
| 42 | |
| 43 | If there is no transition within the bounds, then return HIGH." |
| 44 | |
| 45 | ;; Arrange that the initial run is ones. |
| 46 | (unless (logbitp low mask) (setf mask (lognot mask))) |
| 47 | |
| 48 | ;; Now, note that MASK + 2^LOW is identical to MASK in all bit positions |
| 49 | ;; except for (a) the run of one bits starting at LOW, and (b) the zero bit |
| 50 | ;; just above it. So MASK xor (MASK + 2^LOW) is zero except for these |
| 51 | ;; bits; so all we need now is to find the position of its most significant |
| 52 | ;; set bit. |
| 53 | (let ((pos (1- (integer-length (logxor mask (+ mask (ash 1 low))))))) |
| 54 | (if (<= low pos high) pos high))) |
| 55 | |
| 56 | (defun count-low-zero-bits (n) |
| 57 | "Return the number of low-order zero bits in the integer N." |
| 58 | (cond ((zerop n) nil) |
| 59 | ((oddp n) 0) |
| 60 | (t (find-first-bit-transition n)))) |
| 61 | |
| 62 | (declaim (inline round-down)) |
| 63 | (defun round-down (n step) |
| 64 | "Return the largest multiple of STEP not greater than N." |
| 65 | (* step (floor n step))) |
| 66 | |
| 67 | (declaim (inline round-up)) |
| 68 | (defun round-up (n step) |
| 69 | "Return the smallest multiple of STEP not less than N." |
| 70 | (* step (ceiling n step))) |
| 71 | |
| 72 | (defgeneric extract-class-name (object) |
| 73 | (:documentation "Turn OBJECT into a class name.") |
| 74 | (:method ((instance standard-object)) |
| 75 | (extract-class-name (class-of instance))) |
| 76 | (:method ((class standard-class)) |
| 77 | (class-name class)) |
| 78 | (:method ((name symbol)) |
| 79 | name)) |
| 80 | |
| 81 | (defclass savable-object () |
| 82 | ()) |
| 83 | (defmethod make-load-form ((object savable-object) &optional environment) |
| 84 | (make-load-form-saving-slots object :environment environment)) |
| 85 | |
| 86 | ;;;-------------------------------------------------------------------------- |
| 87 | ;;; Parsing primitives for addresses. |
| 88 | |
| 89 | (defun parse-partial-address |
| 90 | (str |
| 91 | &key (start 0) (end nil) (delim #\.) |
| 92 | (width 8) (radix 10) (min 1) (max 32) (shiftp t) |
| 93 | (what "address")) |
| 94 | "Parse a partial address from STR, which should be a sequence of integers |
| 95 | in the given RADIX, separated by the DELIM character, with each integer |
| 96 | N_i in the interval 0 <= N_i < 2^WIDTH. If the sequence is N_1, N_2, ..., |
| 97 | N_k, then the basic partial address BPA is the sum |
| 98 | |
| 99 | SUM_{1<=i<=k} 2^{WIDTH (k-i)} N_i |
| 100 | |
| 101 | If SHIFTP is true (the default) then let OFFSET be the smallest multiple |
| 102 | of WIDTH not less than MAX - k WIDTH; otherwise, let OFFSET be zero. The |
| 103 | partial address PA is BPA 2^SHIFT. |
| 104 | |
| 105 | The return values are: PA, OFFSET, k WIDTH + OFFSET; i.e., the partial |
| 106 | address, and (inclusive) lower and (exclusive) upper bounds on the bits |
| 107 | specified by STR." |
| 108 | |
| 109 | (setf-default end (length str)) |
| 110 | (let ((addr 0) (nbits 0) (limit (ash 1 width))) |
| 111 | (when (< start end) |
| 112 | (loop |
| 113 | (when (>= nbits max) |
| 114 | (error "Too many elements in ~A" what)) |
| 115 | (let* ((pos (position delim str :start start :end end)) |
| 116 | (w (parse-integer str :radix radix |
| 117 | :start start :end (or pos end)))) |
| 118 | (unless (and (<= 0 w) (< w limit)) |
| 119 | (error "Element out of range in ~A" what)) |
| 120 | (setf addr (logior (ash addr width) w)) |
| 121 | (incf nbits width) |
| 122 | (unless pos (return)) |
| 123 | (setf start (1+ pos))))) |
| 124 | (when (< nbits min) |
| 125 | (error "Not enough elements in ~A" what)) |
| 126 | (if shiftp |
| 127 | (let* ((top (round-up max width)) |
| 128 | (shift (- top nbits))) |
| 129 | (values (ash addr shift) shift top)) |
| 130 | (values addr 0 nbits)))) |
| 131 | |
| 132 | ;;;-------------------------------------------------------------------------- |
| 133 | ;;; Simple messing about with IP addresses. |
| 134 | |
| 135 | (export 'ipaddr) |
| 136 | (export 'ipaddr-addr) |
| 137 | (defclass ipaddr (savable-object) |
| 138 | () |
| 139 | (:documentation |
| 140 | "Base class for IP addresses.")) |
| 141 | |
| 142 | (export 'ipaddr-family) |
| 143 | (defgeneric ipaddr-family (addr)) |
| 144 | |
| 145 | (export 'family-addrclass) |
| 146 | (defgeneric family-addrclass (family) |
| 147 | (:method ((af symbol)) nil)) |
| 148 | |
| 149 | (export 'ipaddr-width) |
| 150 | (defgeneric ipaddr-width (class) |
| 151 | (:method ((object t)) (ipaddr-width (extract-class-name object)))) |
| 152 | |
| 153 | (export 'ipaddr-comparable-p) |
| 154 | (defgeneric ipaddr-comparable-p (addr-a addr-b) |
| 155 | (:method ((addr-a ipaddr) (addr-b ipaddr)) |
| 156 | (eq (class-of addr-a) (class-of addr-b)))) |
| 157 | |
| 158 | (defun guess-address-class (str &key (start 0) (end nil)) |
| 159 | (declare (ignore str start end)) |
| 160 | 'ip4addr) |
| 161 | |
| 162 | (defgeneric parse-partial-ipaddr (class str &key start end min max) |
| 163 | (:method ((object t) str &rest keywords) |
| 164 | (apply #'parse-partial-ipaddr (extract-class-name object) str keywords))) |
| 165 | |
| 166 | (export 'string-ipaddr) |
| 167 | (defun string-ipaddr (str &key (start 0) (end nil)) |
| 168 | "Parse STR into an address; guess what kind is intended by the user. |
| 169 | |
| 170 | STR may be anything at all: it's converted as if by `stringify'. |
| 171 | The START and END arguments may be used to parse out a substring." |
| 172 | (setf str (stringify str)) |
| 173 | (let* ((class (guess-address-class str :start start :end end)) |
| 174 | (width (ipaddr-width class))) |
| 175 | (make-instance class :addr |
| 176 | (parse-partial-ipaddr class str |
| 177 | :start start :end end |
| 178 | :min width :max width)))) |
| 179 | |
| 180 | (export 'integer-ipaddr) |
| 181 | (defgeneric integer-ipaddr (int like) |
| 182 | (:documentation "Convert INT into an address of type indicated by LIKE. |
| 183 | |
| 184 | Specifically, if LIKE is an address object, then use its type; if it's |
| 185 | a class, then use it directly; if it's a symbol, then use the class it |
| 186 | names.") |
| 187 | (:method (int (like t)) (integer-ipaddr int (class-of like))) |
| 188 | (:method (int (like symbol)) |
| 189 | (make-instance (or (family-addrclass like) like) :addr int)) |
| 190 | (:method (int (like standard-class)) (make-instance like :addr int))) |
| 191 | |
| 192 | (export 'ipaddr-string) |
| 193 | (defgeneric ipaddr-string (ip) |
| 194 | (:documentation |
| 195 | "Transform the address IP into a string in dotted-quad form.")) |
| 196 | |
| 197 | (defmethod print-object ((addr ipaddr) stream) |
| 198 | (print-unreadable-object (addr stream :type t) |
| 199 | (write-string (ipaddr-string addr) stream))) |
| 200 | |
| 201 | (export 'ipaddrp) |
| 202 | (defun ipaddrp (ip) |
| 203 | "Answer true if IP is a valid IP address in integer form." |
| 204 | (typep ip 'ipaddr)) |
| 205 | |
| 206 | (defun ipaddr (ip &optional like) |
| 207 | "Convert IP to an IP address, of type similar to LIKE. |
| 208 | |
| 209 | If it's an IP address, just return it unchanged; If it's an integer, |
| 210 | capture it; otherwise convert by `string-ipaddr'." |
| 211 | (typecase ip |
| 212 | (ipaddr ip) |
| 213 | (integer (integer-ipaddr ip like)) |
| 214 | (t (string-ipaddr ip)))) |
| 215 | |
| 216 | (export 'ipaddr-rrtype) |
| 217 | (defgeneric ipaddr-rrtype (addr) |
| 218 | (:documentation "Return the proper resource record type for ADDR.")) |
| 219 | |
| 220 | ;;;-------------------------------------------------------------------------- |
| 221 | ;;; Netmasks. |
| 222 | |
| 223 | (export 'integer-netmask) |
| 224 | (defun integer-netmask (n i) |
| 225 | "Given an integer I, return an N-bit netmask with its I top bits set." |
| 226 | (- (ash 1 n) (ash 1 (- n i)))) |
| 227 | |
| 228 | (export 'ipmask-cidl-slash) |
| 229 | (defun ipmask-cidl-slash (width mask) |
| 230 | "Given a netmask MASK, try to compute a prefix length. |
| 231 | |
| 232 | Return an integer N such that (integer-netmask WIDTH N) = MASK, or nil if |
| 233 | this is impossible." |
| 234 | (let* ((low (logxor mask (mask width))) |
| 235 | (bits (integer-length low))) |
| 236 | (and (= low (mask bits)) (- width bits)))) |
| 237 | |
| 238 | (export 'ipmask) |
| 239 | (defgeneric ipmask (addr mask) |
| 240 | (:documentation "Convert MASK into a suitable netmask for ADDR.") |
| 241 | (:method ((addr ipaddr) (mask null)) |
| 242 | (mask (ipaddr-width addr))) |
| 243 | (:method ((addr ipaddr) (mask integer)) |
| 244 | (let ((w (ipaddr-width addr))) |
| 245 | (if (<= 0 mask w) |
| 246 | (integer-netmask w mask) |
| 247 | (error "Mask out of range."))))) |
| 248 | |
| 249 | (export 'mask-ipaddr) |
| 250 | (defun mask-ipaddr (addr mask) |
| 251 | "Apply the MASK to the ADDR, returning the base address." |
| 252 | (integer-ipaddr (logand mask (ipaddr-addr addr)) addr)) |
| 253 | |
| 254 | ;;;-------------------------------------------------------------------------- |
| 255 | ;;; Networks: pairing an address and netmask. |
| 256 | |
| 257 | (export 'ipnet) |
| 258 | (export 'ipnet-net) |
| 259 | (export 'ipnet-mask) |
| 260 | (defclass ipnet (savable-object) |
| 261 | () |
| 262 | (:documentation "Base class for IP networks.")) |
| 263 | |
| 264 | (export 'ipnet-family) |
| 265 | (defgeneric ipnet-family (ipn) |
| 266 | (:method ((ipn ipnet)) (ipaddr-family (ipnet-net ipn)))) |
| 267 | |
| 268 | (export 'ipnet-addr) |
| 269 | (defun ipnet-addr (ipn) |
| 270 | "Return the base network address of IPN as a raw integer." |
| 271 | (ipaddr-addr (ipnet-net ipn))) |
| 272 | |
| 273 | (export 'ipaddr-ipnet) |
| 274 | (defgeneric ipaddr-ipnet (addr mask) |
| 275 | (:documentation "Construct an `ipnet' object given a base ADDR and MASK.")) |
| 276 | |
| 277 | (export 'make-ipnet) |
| 278 | (defun make-ipnet (net mask) |
| 279 | "Construct an IP-network object given the NET and MASK; these are |
| 280 | transformed as though by `ipaddr' and `ipmask'." |
| 281 | (let* ((net (ipaddr net)) |
| 282 | (mask (ipmask net mask))) |
| 283 | (ipaddr-ipnet (mask-ipaddr net mask) mask))) |
| 284 | |
| 285 | (export 'with-ipnet) |
| 286 | (defmacro with-ipnet ((net addr mask) ipn &body body) |
| 287 | "Evaluate the BODY with components of IPN in scope. |
| 288 | |
| 289 | The NET is bound to the underlying network base address, as an `ipaddr'; |
| 290 | ADDR is bound to the integer value of this address; and MASK is bound to |
| 291 | the netmask, again as an integer. Any (or all) of these may be nil if not |
| 292 | wanted." |
| 293 | (with-gensyms tmp |
| 294 | `(let ((,tmp ,ipn)) |
| 295 | (let (,@(and net `((,net (ipnet-net ,tmp)))) |
| 296 | ,@(and addr `((,addr (ipnet-addr ,tmp)))) |
| 297 | ,@(and mask `((,mask (ipnet-mask ,tmp))))) |
| 298 | ,@body)))) |
| 299 | |
| 300 | (export 'ipnet-width) |
| 301 | (defun ipnet-width (ipn) |
| 302 | "Return the underlying bit width of the addressing system." |
| 303 | (ipaddr-width (ipnet-net ipn))) |
| 304 | |
| 305 | (export 'ipnet-string) |
| 306 | (defun ipnet-string (ipn) |
| 307 | "Convert IPN to a string." |
| 308 | (with-ipnet (net nil mask) ipn |
| 309 | (format nil "~A/~A" |
| 310 | (ipaddr-string net) |
| 311 | (or (ipmask-cidl-slash (ipnet-width ipn) mask) |
| 312 | (ipaddr-string (make-instance (class-of net) :addr mask)))))) |
| 313 | |
| 314 | (defmethod print-object ((ipn ipnet) stream) |
| 315 | (print-unreadable-object (ipn stream :type t) |
| 316 | (write-string (ipnet-string ipn) stream))) |
| 317 | |
| 318 | (defun parse-subnet (class width max str &key (start 0) (end nil)) |
| 319 | "Parse a subnet description from a (substring of) STR." |
| 320 | (setf-default end (length str)) |
| 321 | (let ((sl (position #\/ str :start start :end end))) |
| 322 | (multiple-value-bind (addr lo hi) |
| 323 | (parse-partial-ipaddr class str :max max |
| 324 | :start start :end (or sl end)) |
| 325 | (let* ((present (integer-netmask hi (- hi lo))) |
| 326 | (mask (cond ((not sl) |
| 327 | present) |
| 328 | ((every #'digit-char-p (subseq str (1+ sl) end)) |
| 329 | (let ((length (parse-integer str |
| 330 | :start (1+ sl) |
| 331 | :end end))) |
| 332 | (unless (>= length (- width max)) |
| 333 | (error "Mask doesn't reach subnet boundary")) |
| 334 | (integer-netmask max (- length (- width max))))) |
| 335 | (t |
| 336 | (parse-partial-ipaddr class str :max max |
| 337 | :start (1+ sl) :end end))))) |
| 338 | (unless (zerop (logandc2 mask present)) |
| 339 | (error "Mask selects bits not present in base address")) |
| 340 | (values addr mask))))) |
| 341 | |
| 342 | (export 'ipnet-subnet) |
| 343 | (defun ipnet-subnet (base-ipn sub-net sub-mask) |
| 344 | "Construct a subnet of IPN, using the NET and MASK. |
| 345 | |
| 346 | The NET must either be zero or agree with IPN at all positions indicated |
| 347 | by their respective masks." |
| 348 | (with-ipnet (base-net base-addr base-mask) base-ipn |
| 349 | (let* ((sub-net (ipaddr sub-net (ipnet-net base-ipn))) |
| 350 | (sub-addr (ipaddr-addr sub-net)) |
| 351 | (sub-mask (ipmask sub-net sub-mask)) |
| 352 | (common (logand base-mask sub-mask)) |
| 353 | (base-overlap (logand base-addr common)) |
| 354 | (sub-overlap (logand sub-addr common)) |
| 355 | (full-mask (logior base-mask sub-mask))) |
| 356 | (unless (or (zerop sub-overlap) |
| 357 | (= sub-overlap base-overlap)) |
| 358 | (error "Subnet doesn't match base network")) |
| 359 | (ipaddr-ipnet (integer-ipaddr (logand full-mask |
| 360 | (logior base-addr sub-addr)) |
| 361 | base-net) |
| 362 | full-mask)))) |
| 363 | |
| 364 | (export 'string-ipnet) |
| 365 | (defun string-ipnet (str &key (start 0) (end nil)) |
| 366 | "Parse an IP-network from the string STR." |
| 367 | (setf str (stringify str)) |
| 368 | (setf-default end (length str)) |
| 369 | (let ((addr-class (guess-address-class str :start start :end end))) |
| 370 | (multiple-value-bind (addr mask) |
| 371 | (let ((width (ipaddr-width addr-class))) |
| 372 | (parse-subnet addr-class width width str |
| 373 | :start start :end end)) |
| 374 | (make-ipnet (make-instance addr-class :addr addr) |
| 375 | (make-instance addr-class :addr mask))))) |
| 376 | |
| 377 | (export 'string-subipnet) |
| 378 | (defun string-subipnet (ipn str &key (start 0) (end nil)) |
| 379 | (setf str (stringify str)) |
| 380 | (let* ((addr-class (extract-class-name (ipnet-net ipn))) |
| 381 | (width (ipaddr-width addr-class)) |
| 382 | (max (- width |
| 383 | (or (ipmask-cidl-slash width (ipnet-mask ipn)) |
| 384 | (error "Base network has complex netmask"))))) |
| 385 | (multiple-value-bind (addr mask) |
| 386 | (parse-subnet addr-class width max str :start start :end end) |
| 387 | (ipnet-subnet ipn |
| 388 | (make-instance addr-class :addr addr) |
| 389 | (make-instance addr-class :addr mask))))) |
| 390 | |
| 391 | (defun ipnet (net) |
| 392 | "Construct an IP-network object from the given argument. |
| 393 | |
| 394 | A number of forms are acceptable: |
| 395 | |
| 396 | * ADDR -- a single address, equivalent to (ADDR . N). |
| 397 | * (NET . MASK|nil) -- a single-object representation. |
| 398 | * IPNET -- return an equivalent (`equal', not necessarily `eql') |
| 399 | version." |
| 400 | (typecase net |
| 401 | (ipnet net) |
| 402 | ((or string symbol) (string-ipnet net)) |
| 403 | (t (apply #'make-ipnet (pairify net nil))))) |
| 404 | |
| 405 | (export 'ipnet-broadcast) |
| 406 | (defgeneric ipnet-broadcast (ipn) |
| 407 | (:documentation "Return the broadcast address for the network IPN. |
| 408 | |
| 409 | Returns nil if there isn't one.")) |
| 410 | |
| 411 | (export 'ipnet-hosts) |
| 412 | (defun ipnet-hosts (ipn) |
| 413 | "Return the number of available addresses in network IPN." |
| 414 | (ash 1 (- (ipnet-width ipn) (logcount (ipnet-mask ipn))))) |
| 415 | |
| 416 | (defstruct host-map |
| 417 | "An internal object used by `ipnet-index-host' and `ipnet-host-index'. |
| 418 | |
| 419 | Our objective is to be able to convert between flat host indices and a |
| 420 | possibly crazy non-flat host space. We record the underlying IPNET for |
| 421 | convenience, and a list of byte-specifications for the runs of zero bits |
| 422 | in the netmask, in ascending order." |
| 423 | ipnet |
| 424 | bytes) |
| 425 | |
| 426 | (export 'ipnet-host-map) |
| 427 | (defun ipnet-host-map (ipn) |
| 428 | "Work out how to enumerate the variable portion of IPN. |
| 429 | |
| 430 | Returns an object which can be passed to `ipnet-index-host' and |
| 431 | `ipnet-host-index'." |
| 432 | (let* ((mask (ipnet-mask ipn)) (bytes nil) (i 0) |
| 433 | (len (integer-length mask)) (width (ipnet-width ipn))) |
| 434 | (when (logbitp i mask) (setf i (find-first-bit-transition mask i))) |
| 435 | (loop |
| 436 | (unless (< i len) (return)) |
| 437 | (let ((next (find-first-bit-transition mask i width))) |
| 438 | (push (byte (- next i) i) bytes) |
| 439 | (setf i (find-first-bit-transition mask next width)))) |
| 440 | (when (< len width) (push (byte (- width len) len) bytes)) |
| 441 | (make-host-map :ipnet ipn :bytes (nreverse bytes)))) |
| 442 | |
| 443 | (export 'ipnet-index-host) |
| 444 | (defun ipnet-index-host (map host) |
| 445 | "Convert a HOST index to its address." |
| 446 | (let* ((ipn (host-map-ipnet map)) |
| 447 | (addr (logand (ipnet-addr ipn) (ipnet-mask ipn)))) |
| 448 | (dolist (byte (host-map-bytes map)) |
| 449 | (setf (ldb byte addr) host |
| 450 | host (ash host (- (byte-size byte))))) |
| 451 | (unless (zerop host) |
| 452 | (error "Host index out of range.")) |
| 453 | (integer-ipaddr addr (ipnet-net ipn)))) |
| 454 | |
| 455 | (export 'ipnet-host-index) |
| 456 | (defun ipnet-host-index (map addr) |
| 457 | "Convert an ADDR into a host index." |
| 458 | (let ((addr (ipaddr-addr addr)) |
| 459 | (host 0) (offset 0)) |
| 460 | (dolist (byte (host-map-bytes map)) |
| 461 | (setf host (logior host |
| 462 | (ash (ldb byte addr) offset)) |
| 463 | offset (+ offset (byte-size byte)))) |
| 464 | host)) |
| 465 | |
| 466 | (export 'ipnet-index-bounds) |
| 467 | (defun ipnet-index-bounds (map start end) |
| 468 | "Return host-index bounds corresponding to the given bit-position bounds." |
| 469 | (flet ((hack (frob-map good-byte tweak-addr) |
| 470 | (dolist (byte (funcall frob-map (host-map-bytes map))) |
| 471 | (let* ((low (byte-position byte)) |
| 472 | (high (+ low (byte-size byte))) |
| 473 | (good (funcall good-byte low high))) |
| 474 | (when good |
| 475 | (return-from hack |
| 476 | (ipnet-host-index map |
| 477 | (ipaddr (funcall tweak-addr |
| 478 | (ash 1 good)) |
| 479 | (ipnet-net |
| 480 | (host-map-ipnet map)))))))) |
| 481 | (error "No variable bits in range."))) |
| 482 | (values (hack #'identity |
| 483 | (lambda (low high) |
| 484 | (and (< start high) (max start low))) |
| 485 | #'identity) |
| 486 | (hack #'reverse |
| 487 | (lambda (low high) |
| 488 | (and (>= end low) (min end high))) |
| 489 | #'1-)))) |
| 490 | |
| 491 | (export 'ipnet-host) |
| 492 | (defun ipnet-host (ipn host) |
| 493 | "Return the address of the given HOST in network IPN. |
| 494 | |
| 495 | This works even with a non-contiguous netmask." |
| 496 | (ipnet-index-host (ipnet-host-map ipn) host)) |
| 497 | |
| 498 | (export 'ipaddr-networkp) |
| 499 | (defun ipaddr-networkp (ip ipn) |
| 500 | "Returns true if numeric address IP is within network IPN." |
| 501 | (with-ipnet (nil addr mask) ipn |
| 502 | (= addr (logand ip mask)))) |
| 503 | |
| 504 | (export 'ipnet-subnetp) |
| 505 | (defun ipnet-subnetp (ipn subn) |
| 506 | "Returns true if SUBN is a (non-strict) subnet of IPN." |
| 507 | (with-ipnet (net addr mask) ipn |
| 508 | (with-ipnet (subnet subaddr submask) subn |
| 509 | (and (ipaddr-comparable-p net subnet) |
| 510 | (= addr (logand subaddr mask)) |
| 511 | (= submask (logior mask submask)))))) |
| 512 | |
| 513 | (export 'ipnet-overlapp) |
| 514 | (defun ipnet-overlapp (ipn-a ipn-b) |
| 515 | "Returns true if IPN-A and IPN-B have any addresses in common." |
| 516 | (with-ipnet (net-a addr-a mask-a) ipn-a |
| 517 | (with-ipnet (net-b addr-b mask-b) ipn-b |
| 518 | |
| 519 | ;; In the case of an overlap, we explicitly construct a common |
| 520 | ;; address. If this fails, we know that the networks don't overlap |
| 521 | ;; after all. |
| 522 | (flet ((narrow (addr-a mask-a addr-b mask-b) |
| 523 | ;; Narrow network A towards B, by setting bits in A's base |
| 524 | ;; address towards which A is indifferent, but B is not; |
| 525 | ;; return the resulting base address. This address is still |
| 526 | ;; within network A, since we only set bits to which A is |
| 527 | ;; indifferent. |
| 528 | (logior addr-a (logand addr-b (logandc2 mask-a mask-b))))) |
| 529 | |
| 530 | (and (ipaddr-comparable-p net-a net-b) |
| 531 | (= (narrow addr-a mask-a addr-b mask-b) |
| 532 | (narrow addr-b mask-b addr-a mask-a))))))) |
| 533 | |
| 534 | (export 'ipnet-changeable-bits) |
| 535 | (defun ipnet-changeable-bits (width mask) |
| 536 | "Work out the number of changeable bits in a network, given its MASK. |
| 537 | |
| 538 | This is a conservative estimate in the case of noncontiguous masks. The |
| 539 | WIDTH is the total width of an address." |
| 540 | |
| 541 | ;; We bisect the address. If the low-order bits are changeable then we |
| 542 | ;; recurse on them; otherwise we look at the high-order bits. A mask M of |
| 543 | ;; width W is changeable if it's not all-ones, i.e., if M /= 2^W. If the |
| 544 | ;; top half is changeable then we don't need to look at the bottom half. |
| 545 | (labels ((recurse (width mask offset) |
| 546 | (if (= width 1) |
| 547 | (if (zerop mask) (1+ offset) offset) |
| 548 | (let* ((lowwidth (floor width 2)) |
| 549 | (highwidth (- width lowwidth)) |
| 550 | (highmask (ash mask (- lowwidth)))) |
| 551 | (if (logbitp highwidth (1+ highmask)) |
| 552 | (recurse lowwidth |
| 553 | (logand mask (mask lowwidth)) |
| 554 | offset) |
| 555 | (recurse highwidth highmask (+ offset lowwidth))))))) |
| 556 | (recurse width mask 0))) |
| 557 | |
| 558 | ;;;-------------------------------------------------------------------------- |
| 559 | ;;; Reverse lookups. |
| 560 | |
| 561 | (export 'reverse-domain-component-width) |
| 562 | (defgeneric reverse-domain-component-width (ipaddr) |
| 563 | (:documentation "Return the component width for splitting IPADDR.")) |
| 564 | |
| 565 | (export 'reverse-domain-component-radix) |
| 566 | (defgeneric reverse-domain-radix (ipaddr) |
| 567 | (:documentation "Return the radix for representing IPADDR components.")) |
| 568 | |
| 569 | (export 'reverse-domain-component-suffix) |
| 570 | (defgeneric reverse-domain-suffix (ipaddr) |
| 571 | (:documentation "Return the reverse-lookup domain suffix for IPADDR.")) |
| 572 | |
| 573 | (export 'reverse-domain-fragment) |
| 574 | (defgeneric reverse-domain-fragment (ipaddr start end &key partialp) |
| 575 | (:documentation |
| 576 | "Return a portion of an IPADDR's reverse-resolution domain name. |
| 577 | |
| 578 | Specifically, return the portion of the name which covers the bits of an |
| 579 | IPADDR between bits START (inclusive) and END (exclusive). Address |
| 580 | components which are only partially within the given bounds are included |
| 581 | unless PARTIALP is nil.") |
| 582 | (:method ((ipaddr ipaddr) start end &key (partialp t)) |
| 583 | |
| 584 | (let ((addr (ipaddr-addr ipaddr)) |
| 585 | (comp-width (reverse-domain-component-width ipaddr)) |
| 586 | (radix (reverse-domain-radix ipaddr))) |
| 587 | |
| 588 | (with-output-to-string (out) |
| 589 | (do ((i (funcall (if partialp #'round-down #'round-up) |
| 590 | start comp-width) |
| 591 | (+ i comp-width)) |
| 592 | (limit (funcall (if partialp #'round-up #'round-down) |
| 593 | end comp-width)) |
| 594 | (sep nil t)) |
| 595 | ((>= i limit)) |
| 596 | (format out "~:[~;.~]~(~vR~)" |
| 597 | sep radix (ldb (byte comp-width i) addr))))))) |
| 598 | |
| 599 | (export 'reverse-domain) |
| 600 | (defgeneric reverse-domain (ipaddr-or-ipn &optional prefix-len) |
| 601 | (:documentation "Return a reverse-resolution domain name for IPADDR-OR-IPN. |
| 602 | |
| 603 | If PREFIX-LEN is nil then it defaults to the length of the network's fixed |
| 604 | prefix.") |
| 605 | (:method ((ipn ipnet) &optional prefix-len) |
| 606 | (let* ((addr (ipnet-net ipn)) |
| 607 | (mask (ipnet-mask ipn)) |
| 608 | (width (ipaddr-width addr))) |
| 609 | (concatenate 'string |
| 610 | (reverse-domain-fragment |
| 611 | addr |
| 612 | (if prefix-len |
| 613 | (- width prefix-len) |
| 614 | (ipnet-changeable-bits width mask)) |
| 615 | width |
| 616 | :partialp nil) |
| 617 | "." |
| 618 | (reverse-domain-suffix addr)))) |
| 619 | (:method ((addr ipaddr) &optional prefix-len) |
| 620 | (let* ((width (ipaddr-width addr))) |
| 621 | (reverse-domain (make-ipnet addr (mask width)) |
| 622 | (or prefix-len width))))) |
| 623 | |
| 624 | ;;;-------------------------------------------------------------------------- |
| 625 | ;;; Network names and specifiers. |
| 626 | |
| 627 | (export 'net) |
| 628 | (export 'net-name) |
| 629 | (export 'net-ipnets) |
| 630 | (defclass net () |
| 631 | ((name :type string :initarg :name :reader net-name) |
| 632 | (ipnets :type list :initarg :ipnets :initform nil :accessor net-ipnets) |
| 633 | (next :type unsigned-byte :initform 1 :accessor net-next))) |
| 634 | |
| 635 | (defmethod print-object ((net net) stream) |
| 636 | (print-unreadable-object (net stream :type t) |
| 637 | (format stream "~A~@[ = ~{~A~^, ~}~]" |
| 638 | (net-name net) |
| 639 | (mapcar #'ipnet-string (net-ipnets net))))) |
| 640 | |
| 641 | (defvar *networks* (make-hash-table :test #'equal) |
| 642 | "The table of known networks.") |
| 643 | |
| 644 | (export 'net-find) |
| 645 | (defun net-find (name) |
| 646 | "Find a network by NAME." |
| 647 | (gethash (string-downcase (stringify name)) *networks*)) |
| 648 | (defun (setf net-find) (net name) |
| 649 | "Make NAME map to NET." |
| 650 | (setf (gethash (string-downcase (stringify name)) *networks*) net)) |
| 651 | |
| 652 | (export 'net-must-find) |
| 653 | (defun net-must-find (name) |
| 654 | (or (net-find name) |
| 655 | (error "Unknown network ~A." name))) |
| 656 | |
| 657 | (defun net-ipnet (net family) |
| 658 | (find family (net-ipnets net) :key #'ipnet-family)) |
| 659 | (defun (setf net-ipnet) (ipnet net family) |
| 660 | (assert (eq (ipnet-family ipnet) family)) |
| 661 | (let ((ipns (net-ipnets net))) |
| 662 | (if (find family ipns :key #'ipnet-family) |
| 663 | (nsubstitute ipnet family ipns :key #'ipnet-family) |
| 664 | (setf (net-ipnets net) (cons ipnet ipns))))) |
| 665 | |
| 666 | (defun process-net-form (name addr subnets) |
| 667 | "Unpack a net-form. |
| 668 | |
| 669 | A net-form looks like (NAME ADDR [SUBNET ...]) where: |
| 670 | |
| 671 | * NAME is the name for the network. |
| 672 | |
| 673 | * ADDR is the subnet address (acceptable to `string-subipnet'); at |
| 674 | top-level, this is a plain network address (acceptable to |
| 675 | `string-ipnet'). Alternatively (for compatibility) the ADDR for a |
| 676 | non-top-level network can be an integer number of addresses to |
| 677 | allocate to this subnet; the subnet's base address is implicitly just |
| 678 | past the previous subnet's limit address (or, for the first subnet, |
| 679 | it's the parent network's base address). This won't work at all well |
| 680 | if your subnets have crazy netmasks. |
| 681 | |
| 682 | * The SUBNETs are further net-forms, of the same form, whose addresses |
| 683 | are interpreted relative to the parent network's address. |
| 684 | |
| 685 | The return value is a list of items of the form (NAME . IPNET)." |
| 686 | |
| 687 | (labels ((process-subnets (subnets parent) |
| 688 | (let ((finger (ipnet-addr parent)) |
| 689 | (list nil)) |
| 690 | (dolist (subnet subnets list) |
| 691 | (destructuring-bind (name addr &rest subs) subnet |
| 692 | (let ((net (etypecase addr |
| 693 | (integer |
| 694 | (when (or (> (count-low-zero-bits addr) |
| 695 | (count-low-zero-bits finger)) |
| 696 | (not (zerop (logand addr |
| 697 | (1- addr))))) |
| 698 | (error "Bad subnet size for ~A." name)) |
| 699 | (make-ipnet |
| 700 | (ipaddr finger (ipnet-net parent)) |
| 701 | (ipaddr (- (ash 1 (ipnet-width parent)) |
| 702 | addr) |
| 703 | (ipnet-net parent)))) |
| 704 | ((or string symbol) |
| 705 | (string-subipnet parent addr))))) |
| 706 | |
| 707 | (unless (ipnet-subnetp parent net) |
| 708 | (error "Network `~A' (~A) falls outside parent ~A." |
| 709 | name (ipnet-string net) (ipnet-string parent))) |
| 710 | |
| 711 | (dolist (entry list nil) |
| 712 | (let ((ipn (cdr entry))) |
| 713 | (when (ipnet-overlapp ipn net) |
| 714 | (error "Network `~A' (~A) overlaps `~A' (~A)." |
| 715 | name (ipnet-string net) |
| 716 | (car entry) (ipnet-string ipn))))) |
| 717 | |
| 718 | (setf finger |
| 719 | (1+ (logior |
| 720 | (ipnet-addr net) |
| 721 | (logxor (ipnet-mask net) |
| 722 | (1- (ash 1 (ipnet-width net))))))) |
| 723 | |
| 724 | (when name |
| 725 | (push (cons name net) list)) |
| 726 | |
| 727 | (when subs |
| 728 | (setf list (nconc (process-subnets subs net) |
| 729 | list))))))))) |
| 730 | |
| 731 | (let* ((top (string-ipnet addr)) |
| 732 | (list (nreverse (process-subnets subnets top)))) |
| 733 | (when name (push (cons name top) list)) |
| 734 | list))) |
| 735 | |
| 736 | (export 'net-create) |
| 737 | (defun net-create (name net) |
| 738 | "Construct a new network called NAME and add it to the map. |
| 739 | |
| 740 | The NET describes the new network, in a form acceptable to the `ipnet' |
| 741 | function. A named network may have multiple addresses with different |
| 742 | families: each `net-create' call adds a new family, or modifies the net's |
| 743 | address in an existing family." |
| 744 | (let ((ipn (ipnet net)) |
| 745 | (net (net-find name))) |
| 746 | (if net |
| 747 | (progn (setf (net-ipnet net (ipnet-family ipn)) ipn) net) |
| 748 | (setf (net-find name) |
| 749 | (make-instance 'net |
| 750 | :name (string-downcase (stringify name)) |
| 751 | :ipnets (list ipn)))))) |
| 752 | |
| 753 | (export 'defnet) |
| 754 | (defmacro defnet (name net &rest subnets) |
| 755 | "Main network definition macro. |
| 756 | |
| 757 | None of the arguments is evaluated." |
| 758 | `(progn |
| 759 | ,@(mapcar (lambda (item) |
| 760 | (let ((name (car item)) (ipn (cdr item))) |
| 761 | `(net-create ',name ',ipn))) |
| 762 | (process-net-form name net subnets)) |
| 763 | ',name)) |
| 764 | |
| 765 | (export 'net-parse-to-ipnets) |
| 766 | (defun net-parse-to-ipnets (form &optional (family t)) |
| 767 | (flet ((hack (form family) |
| 768 | (let* ((form (if (and (consp form) |
| 769 | (endp (cdr form))) |
| 770 | (car form) |
| 771 | form)) |
| 772 | (net (net-find form)) |
| 773 | (ipns (if net (net-ipnets net) |
| 774 | (list (ipnet form))))) |
| 775 | (if (eq family t) ipns |
| 776 | (remove family ipns |
| 777 | :key #'ipnet-family |
| 778 | :test-not #'eq))))) |
| 779 | (let* ((ipns (if (and (listp form) |
| 780 | (every (lambda (clause) |
| 781 | (and (listp clause) |
| 782 | (symbolp (car clause)) |
| 783 | (or (eq (car clause) t) |
| 784 | (family-addrclass |
| 785 | (car clause))))) |
| 786 | form)) |
| 787 | (mappend (lambda (clause) |
| 788 | (hack (cdr clause) (car clause))) |
| 789 | form) |
| 790 | (hack form family))) |
| 791 | (merged (reduce (lambda (ipns ipn) |
| 792 | (if (find (ipnet-family ipn) ipns |
| 793 | :key #'ipnet-family) |
| 794 | ipns |
| 795 | (cons ipn ipns))) |
| 796 | ipns |
| 797 | :initial-value nil))) |
| 798 | (or merged (error "No matching addresses."))))) |
| 799 | |
| 800 | (export 'net-host) |
| 801 | (defun net-host (net-form host &optional (family t)) |
| 802 | "Return the given HOST on the NET, as an anonymous `host' object. |
| 803 | |
| 804 | HOST may be an index (in range, of course), or one of the keywords: |
| 805 | |
| 806 | :next next host, as by net-next-host |
| 807 | :net network base address |
| 808 | :broadcast network broadcast address |
| 809 | |
| 810 | If FAMILY is not `t', then only return an address with that family; |
| 811 | otherwise return all available addresses." |
| 812 | (flet ((hosts (ipns host) |
| 813 | (mapcar (lambda (ipn) (ipnet-host ipn host)) |
| 814 | (remove host ipns :key #'ipnet-hosts :test-not #'<)))) |
| 815 | (let* ((net (and (typep net-form '(or string symbol)) |
| 816 | (net-find net-form))) |
| 817 | (ipns (net-parse-to-ipnets net-form family)) |
| 818 | (addrs (case host |
| 819 | (:next |
| 820 | (if net |
| 821 | (prog1 (hosts ipns (net-next net)) |
| 822 | (incf (net-next net))) |
| 823 | (error "Can't use `:next' without a named net."))) |
| 824 | (:net (mapcar #'ipnet-net ipns)) |
| 825 | (:broadcast (remove nil (mapcar #'ipnet-broadcast ipns))) |
| 826 | (t (hosts ipns host))))) |
| 827 | (unless addrs |
| 828 | (error "No networks have that address.")) |
| 829 | (make-instance 'host :addrs addrs)))) |
| 830 | |
| 831 | ;;;-------------------------------------------------------------------------- |
| 832 | ;;; Host names and specifiers. |
| 833 | |
| 834 | (export 'host) |
| 835 | (export 'host-name) |
| 836 | (export 'host-addrs) |
| 837 | (defclass host () |
| 838 | ((name :type (or string null) :initform nil |
| 839 | :initarg :name :reader host-name) |
| 840 | (addrs :type list :initarg :addrs :initform nil :accessor host-addrs))) |
| 841 | |
| 842 | (defmethod print-object ((host host) stream) |
| 843 | (print-unreadable-object (host stream :type t) |
| 844 | (format stream "~:[<anonymous>~;~@*~A~]~@[ = ~{~A~^, ~}~]" |
| 845 | (host-name host) |
| 846 | (mapcar #'ipaddr-string (host-addrs host))))) |
| 847 | |
| 848 | (defvar *hosts* (make-hash-table :test #'equal) |
| 849 | "The table of known hostnames.") |
| 850 | |
| 851 | (export 'host-find) |
| 852 | (defun host-find (name) |
| 853 | "Find a host by NAME." |
| 854 | (gethash (string-downcase (stringify name)) *hosts*)) |
| 855 | (defun (setf host-find) (addr name) |
| 856 | "Make NAME map to ADDR (must be an ipaddr in integer form)." |
| 857 | (setf (gethash (string-downcase (stringify name)) *hosts*) addr)) |
| 858 | |
| 859 | (defun merge-addresses (addrs-a addrs-b) |
| 860 | (append (remove-if (lambda (addr) |
| 861 | (member (ipaddr-family addr) addrs-b |
| 862 | :key #'ipaddr-family)) |
| 863 | addrs-a) |
| 864 | addrs-b)) |
| 865 | |
| 866 | (export 'host-parse) |
| 867 | (defun host-parse (addr &optional (family t)) |
| 868 | "Convert the ADDR into a (possibly anonymous) `host' object. |
| 869 | |
| 870 | The ADDR can be one of a number of different things. |
| 871 | |
| 872 | HOST a host name defined using `defhost' |
| 873 | |
| 874 | (NET INDEX) a particular host in a network |
| 875 | |
| 876 | IPADDR an address form acceptable to `ipnet' |
| 877 | |
| 878 | ((FAMILY . ADDR) ...) the above, restricted to a particular address |
| 879 | FAMILY (i.e., one of the keywords `:ipv4', |
| 880 | etc.)" |
| 881 | |
| 882 | (labels ((filter-addresses (addrs family) |
| 883 | (make-instance 'host |
| 884 | :addrs (if (eq family t) addrs |
| 885 | (remove family addrs |
| 886 | :key #'ipaddr-family |
| 887 | :test-not #'eq)))) |
| 888 | (host-addresses (host family) |
| 889 | (if (eq family t) host |
| 890 | (filter-addresses (host-addrs host) family))) |
| 891 | (hack (addr family) |
| 892 | (let* ((form (listify addr)) |
| 893 | (indic (car form)) |
| 894 | (host (and (null (cdr form)) |
| 895 | (host-find indic)))) |
| 896 | (cond (host |
| 897 | (host-addresses host family)) |
| 898 | ((and (consp (cdr form)) |
| 899 | (endp (cddr form))) |
| 900 | (net-host (car form) (cadr form) family)) |
| 901 | (t |
| 902 | (filter-addresses (list (ipaddr indic)) family)))))) |
| 903 | (let ((host (cond |
| 904 | ((not (eq family t)) |
| 905 | (hack addr family)) |
| 906 | ((and (listp addr) |
| 907 | (every (lambda (clause) |
| 908 | (and (listp clause) |
| 909 | (symbolp (car clause)) |
| 910 | (or (eq (car clause) t) |
| 911 | (family-addrclass (car clause))))) |
| 912 | addr)) |
| 913 | (make-instance 'host |
| 914 | :addrs (reduce #'merge-addresses |
| 915 | (mapcar |
| 916 | (lambda (clause) |
| 917 | (host-addrs |
| 918 | (hack (cdr clause) |
| 919 | (car clause)))) |
| 920 | (reverse addr)) |
| 921 | :initial-value nil))) |
| 922 | (t |
| 923 | (hack addr t))))) |
| 924 | (unless (host-addrs host) |
| 925 | (error "No matching addresses.")) |
| 926 | host))) |
| 927 | |
| 928 | (export 'host-create) |
| 929 | (defun host-create (name addr) |
| 930 | "Make host NAME map to ADDR (anything acceptable to `host-parse')." |
| 931 | (let ((existing (host-find name)) |
| 932 | (new (host-parse addr))) |
| 933 | (if (not existing) |
| 934 | (setf (host-find name) |
| 935 | (make-instance 'host |
| 936 | :name (string-downcase (stringify name)) |
| 937 | :addrs (host-addrs new))) |
| 938 | (progn |
| 939 | (setf (host-addrs existing) |
| 940 | (merge-addresses (host-addrs existing) (host-addrs new))) |
| 941 | existing)))) |
| 942 | |
| 943 | (export 'defhost) |
| 944 | (defmacro defhost (name addr) |
| 945 | "Main host definition macro. Neither NAME nor ADDR is evaluated." |
| 946 | `(progn |
| 947 | (host-create ',name ',addr) |
| 948 | ',name)) |
| 949 | |
| 950 | ;;;----- That's all, folks -------------------------------------------------- |