| 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 | ;;;-------------------------------------------------------------------------- |
| 25 | ;;; Packaging. |
| 26 | |
| 27 | (defpackage #:net |
| 28 | (:use #:common-lisp #:mdw.base #:mdw.str #:collect #:net-sys) |
| 29 | (:export #:ipaddr #:string-ipaddr #:ipaddr-byte #:ipaddr-string #:ipaddrp |
| 30 | #:integer-netmask #:ipmask #:ipmask-cidl-slash #:make-ipnet |
| 31 | #:string-ipnet #:ipnet #:ipnet-net #:ipnet-mask #:with-ipnet |
| 32 | #:ipnet-pretty #:ipnet-string #:ipnet-broadcast #:ipnet-hosts |
| 33 | #:ipnet-host #:ipaddr-networkp #:ipnet-subnetp |
| 34 | #:ipnet-changeable-bytes |
| 35 | #:host-find #:host-create #:defhost #:parse-ipaddr |
| 36 | #:resolve-hostname #:canonify-hostname |
| 37 | #:net #:net-find #:net-get-as-ipnet #:net-create #:defnet |
| 38 | #:net-next-host #:net-host)) |
| 39 | |
| 40 | (in-package #:net) |
| 41 | |
| 42 | ;;;-------------------------------------------------------------------------- |
| 43 | ;;; Basic types. |
| 44 | |
| 45 | (defun mask (n) |
| 46 | "Return 2^N - 1: i.e., a mask of N set bits." |
| 47 | (1- (ash 1 n))) |
| 48 | |
| 49 | (deftype u32 () |
| 50 | "The type of unsigned 32-bit values." |
| 51 | '(unsigned-byte 32)) |
| 52 | |
| 53 | (deftype ipaddr () |
| 54 | "The type of IP (version 4) addresses." |
| 55 | 'u32) |
| 56 | |
| 57 | ;;;-------------------------------------------------------------------------- |
| 58 | ;;; Various random utilities. |
| 59 | |
| 60 | (defun count-low-zero-bits (n) |
| 61 | "Return the number of low-order zero bits in the integer N." |
| 62 | (if (zerop n) nil |
| 63 | (loop for i from 0 |
| 64 | until (logbitp i n) |
| 65 | finally (return i)))) |
| 66 | |
| 67 | ;;;-------------------------------------------------------------------------- |
| 68 | ;;; Simple messing with IP addresses. |
| 69 | |
| 70 | (defun string-ipaddr (str &key (start 0) (end nil)) |
| 71 | "Parse STR as an IP address in dotted-quad form and return the integer |
| 72 | equivalent. STR may be anything at all: it's converted as if by |
| 73 | `stringify'. The START and END arguments may be used to parse out a |
| 74 | substring." |
| 75 | (setf str (stringify str)) |
| 76 | (setf-default end (length str)) |
| 77 | (let ((addr 0) (noct 0)) |
| 78 | (loop |
| 79 | (let* ((pos (position #\. str :start start :end end)) |
| 80 | (i (parse-integer str :start start :end (or pos end)))) |
| 81 | (unless (<= 0 i 256) |
| 82 | (error "IP address octet out of range")) |
| 83 | (setf addr (+ (* addr 256) i)) |
| 84 | (incf noct) |
| 85 | (unless pos |
| 86 | (return)) |
| 87 | (setf start (1+ pos)))) |
| 88 | (unless (= noct 4) |
| 89 | (error "Wrong number of octets in IP address")) |
| 90 | addr)) |
| 91 | |
| 92 | (defun ipaddr-byte (ip n) |
| 93 | "Return byte N (from most significant downwards) of an IP address." |
| 94 | (assert (<= 0 n 3)) |
| 95 | (logand #xff (ash ip (* -8 (- 3 n))))) |
| 96 | |
| 97 | (defun ipaddr-string (ip) |
| 98 | "Transform the address IP into a string in dotted-quad form." |
| 99 | (check-type ip ipaddr) |
| 100 | (join-strings #\. (collecting () |
| 101 | (dotimes (i 4) |
| 102 | (collect (ipaddr-byte ip i)))))) |
| 103 | |
| 104 | (defun ipaddrp (ip) |
| 105 | "Answer true if IP is a valid IP address in integer form." |
| 106 | (typep ip 'ipaddr)) |
| 107 | |
| 108 | (defun ipaddr (ip) |
| 109 | "Convert IP to an IP address. If it's an integer, return it unchanged; |
| 110 | otherwise convert by `string-ipaddr'." |
| 111 | (typecase ip |
| 112 | (ipaddr ip) |
| 113 | (t (string-ipaddr ip)))) |
| 114 | |
| 115 | ;;;-------------------------------------------------------------------------- |
| 116 | ;;; Netmasks. |
| 117 | |
| 118 | (defun integer-netmask (i) |
| 119 | "Given an integer I, return a netmask with its I top bits set." |
| 120 | (- (ash 1 32) (ash 1 (- 32 i)))) |
| 121 | |
| 122 | (defun ipmask (ip) |
| 123 | "Transform IP into a netmask. If it's a small integer then it's converted |
| 124 | by `integer-netmask'; if nil, then all-bits-set; otherwise convert using |
| 125 | `ipaddr'." |
| 126 | (typecase ip |
| 127 | (null (mask 32)) |
| 128 | ((integer 0 32) (integer-netmask ip)) |
| 129 | (t (ipaddr ip)))) |
| 130 | |
| 131 | (defun ipmask-cidl-slash (mask) |
| 132 | "Given a netmask MASK, return an integer N such that (integer-netmask N) = |
| 133 | MASK, or nil if this is impossible." |
| 134 | (dotimes (i 33) |
| 135 | (when (= mask (integer-netmask i)) |
| 136 | (return i)))) |
| 137 | |
| 138 | ;;;-------------------------------------------------------------------------- |
| 139 | ;;; Networks: pairing an address and netmask. |
| 140 | |
| 141 | (defun make-ipnet (net mask) |
| 142 | "Construct an IP-network object given the NET and MASK; these are |
| 143 | transformed as though by `ipaddr' and `ipmask'." |
| 144 | (let ((net (ipaddr net)) |
| 145 | (mask (ipmask mask))) |
| 146 | (cons (logand net mask) mask))) |
| 147 | |
| 148 | (defun string-ipnet (str &key (start 0) (end nil)) |
| 149 | "Parse an IP-network from the string STR." |
| 150 | (setf str (stringify str)) |
| 151 | (setf-default end (length str)) |
| 152 | (let ((sl (position #\/ str :start start :end end))) |
| 153 | (if sl |
| 154 | (make-ipnet (parse-ipaddr (subseq str start sl)) |
| 155 | (if (find #\. str :start (1+ sl) :end end) |
| 156 | (string-ipaddr str :start (1+ sl) :end end) |
| 157 | (integer-netmask (parse-integer str |
| 158 | :start (1+ sl) |
| 159 | :end end)))) |
| 160 | (make-ipnet (parse-ipaddr (subseq str start end)) |
| 161 | (integer-netmask 32))))) |
| 162 | |
| 163 | (defun ipnet (net) |
| 164 | "Construct an IP-network object from the given argument. A number of forms |
| 165 | are acceptable: |
| 166 | |
| 167 | * ADDR -- a single address (equivalent to ADDR 32) |
| 168 | * (NET . MASK|nil) -- a single-object representation. |
| 169 | * IPNET -- return an equivalent (`equal', not necessarily `eql') |
| 170 | version." |
| 171 | (cond ((or (stringp net) (symbolp net)) (string-ipnet net)) |
| 172 | (t (apply #'make-ipnet (pairify net 32))))) |
| 173 | |
| 174 | (defun ipnet-net (ipn) |
| 175 | "Return the base network address of IPN." |
| 176 | (car ipn)) |
| 177 | |
| 178 | (defun ipnet-mask (ipn) |
| 179 | "Return the netmask of IPN." |
| 180 | (cdr ipn)) |
| 181 | |
| 182 | (defmacro with-ipnet ((net mask) ipn &body body) |
| 183 | "Evaluate BODY with NET and MASK bound to the base address and netmask of |
| 184 | IPN. Either NET or MASK (or, less usefully, both) may be nil if not |
| 185 | wanted." |
| 186 | (with-gensyms tmp |
| 187 | `(let ((,tmp ,ipn)) |
| 188 | (let (,@(and net `((,net (ipnet-net ,tmp)))) |
| 189 | ,@(and mask `((,mask (ipnet-mask ,tmp))))) |
| 190 | ,@body)))) |
| 191 | |
| 192 | (defun ipnet-pretty (ipn) |
| 193 | "Convert IPN to a pretty cons-cell form." |
| 194 | (with-ipnet (net mask) ipn |
| 195 | (cons (ipaddr-string net) |
| 196 | (or (ipmask-cidl-slash mask) (ipaddr-string mask))))) |
| 197 | |
| 198 | (defun ipnet-string (ipn) |
| 199 | "Convert IPN to a string." |
| 200 | (with-ipnet (net mask) ipn |
| 201 | (format nil "~A/~A" |
| 202 | (ipaddr-string net) |
| 203 | (or (ipmask-cidl-slash mask) (ipaddr-string mask))))) |
| 204 | |
| 205 | (defun ipnet-broadcast (ipn) |
| 206 | "Return the broadcast address for the network IPN." |
| 207 | (with-ipnet (net mask) ipn |
| 208 | (logior net (logxor (mask 32) mask)))) |
| 209 | |
| 210 | (defun ipnet-hosts (ipn) |
| 211 | "Return the number of available addresses in network IPN." |
| 212 | (ash 1 (- 32 (logcount (ipnet-mask ipn))))) |
| 213 | |
| 214 | (defun ipnet-host (ipn host) |
| 215 | "Return the address of the given HOST in network IPN. This works even with |
| 216 | a non-contiguous netmask." |
| 217 | (check-type host u32) |
| 218 | (with-ipnet (net mask) ipn |
| 219 | (let ((i 0) (m 1) (a net) (h host)) |
| 220 | (loop |
| 221 | (when (>= i 32) |
| 222 | (error "Host index ~D out of range for network ~A" |
| 223 | host (ipnet-pretty ipn))) |
| 224 | (cond ((zerop h) |
| 225 | (return a)) |
| 226 | ((logbitp i mask) |
| 227 | (setf h (ash h 1))) |
| 228 | (t |
| 229 | (setf a (logior a (logand m h))) |
| 230 | (setf h (logandc2 h m)))) |
| 231 | (setf m (ash m 1)) |
| 232 | (incf i))))) |
| 233 | |
| 234 | (defun ipaddr-networkp (ip ipn) |
| 235 | "Returns true if address IP is within network IPN." |
| 236 | (with-ipnet (net mask) ipn |
| 237 | (= net (logand ip mask)))) |
| 238 | |
| 239 | (defun ipnet-subnetp (ipn subn) |
| 240 | "Returns true if SUBN is a (non-strict) subnet of IPN." |
| 241 | (with-ipnet (net mask) ipn |
| 242 | (with-ipnet (subnet submask) subn |
| 243 | (and (= net (logand subnet mask)) |
| 244 | (= submask (logior mask submask)))))) |
| 245 | |
| 246 | (defun ipnet-changeable-bytes (mask) |
| 247 | "Answers how many low-order bytes of MASK are (entirely or partially) |
| 248 | changeable. This is used when constructing reverse zones." |
| 249 | (dotimes (i 4 4) |
| 250 | (when (/= (ipaddr-byte mask i) 255) |
| 251 | (return (- 4 i))))) |
| 252 | |
| 253 | ;;;-------------------------------------------------------------------------- |
| 254 | ;;; Host names and specifiers. |
| 255 | |
| 256 | (defun parse-ipaddr (addr) |
| 257 | "Convert the string ADDR into an IP address: tries all sorts of things: |
| 258 | |
| 259 | (NET [INDEX]) index a network: NET is a network name defined by |
| 260 | defnet; INDEX is an index or one of the special |
| 261 | symbols understood by net-host, and defaults to :next |
| 262 | |
| 263 | INTEGER an integer IP address |
| 264 | |
| 265 | IPADDR an IP address in dotted-quad form |
| 266 | |
| 267 | HOST a host name defined by defhost |
| 268 | |
| 269 | DNSNAME a name string to look up in the DNS" |
| 270 | (cond ((listp addr) |
| 271 | (destructuring-bind |
| 272 | (net host) |
| 273 | (pairify addr :next) |
| 274 | (net-host (or (net-find net) |
| 275 | (error "Network ~A not found" net)) |
| 276 | host))) |
| 277 | ((ipaddrp addr) addr) |
| 278 | (t |
| 279 | (setf addr (string-downcase (stringify addr))) |
| 280 | (or (host-find addr) |
| 281 | (and (plusp (length addr)) |
| 282 | (digit-char-p (char addr 0)) |
| 283 | (string-ipaddr addr)) |
| 284 | (resolve-hostname (stringify addr)) |
| 285 | (error "Host name ~A unresolvable" addr))))) |
| 286 | |
| 287 | (defvar *hosts* (make-hash-table :test #'equal) |
| 288 | "The table of known hostnames.") |
| 289 | |
| 290 | (defun host-find (name) |
| 291 | "Find a host by NAME." |
| 292 | (gethash (string-downcase (stringify name)) *hosts*)) |
| 293 | |
| 294 | (defun (setf host-find) (addr name) |
| 295 | "Make NAME map to ADDR (must be an ipaddr in integer form)." |
| 296 | (setf (gethash (string-downcase (stringify name)) *hosts*) addr)) |
| 297 | |
| 298 | (defun host-create (name addr) |
| 299 | "Make host NAME map to ADDR (anything acceptable to parse-ipaddr)." |
| 300 | (setf (host-find name) (parse-ipaddr addr))) |
| 301 | |
| 302 | (defmacro defhost (name addr) |
| 303 | "Main host definition macro. Neither NAME nor ADDR is evaluated." |
| 304 | `(progn |
| 305 | (host-create ',name ',addr) |
| 306 | ',name)) |
| 307 | |
| 308 | ;;;-------------------------------------------------------------------------- |
| 309 | ;;; Network names and specifiers. |
| 310 | |
| 311 | (defstruct (net (:predicate netp)) |
| 312 | "A network structure. Slots: |
| 313 | |
| 314 | NAME The network's name, as a string |
| 315 | IPNET The network base address and mask |
| 316 | HOSTS Number of hosts in the network |
| 317 | NEXT Index of the next unassigned host" |
| 318 | name |
| 319 | ipnet |
| 320 | hosts |
| 321 | next) |
| 322 | |
| 323 | (defvar *networks* (make-hash-table :test #'equal) |
| 324 | "The table of known networks.") |
| 325 | |
| 326 | (defun net-find (name) |
| 327 | "Find a network by NAME." |
| 328 | (gethash (string-downcase (stringify name)) *networks*)) |
| 329 | |
| 330 | (defun (setf net-find) (net name) |
| 331 | "Make NAME map to NET." |
| 332 | (setf (gethash (string-downcase (stringify name)) *networks*) net)) |
| 333 | |
| 334 | (defun net-get-as-ipnet (form) |
| 335 | "Transform FORM into an ipnet. FORM may be a network name, or something |
| 336 | acceptable to the ipnet function." |
| 337 | (let ((net (net-find form))) |
| 338 | (if net (net-ipnet net) |
| 339 | (ipnet form)))) |
| 340 | |
| 341 | (defun process-net-form (root addr subnets) |
| 342 | "Unpack a net-form. The return value is a list of entries, each of which |
| 343 | is a list of the form (NAME ADDR MASK). The first entry is merely repeats |
| 344 | the given ROOT and ADDR arguments (unpacking ADDR into separate network |
| 345 | address and mask). The SUBNETS are then processed: they are a list of |
| 346 | items of the form (NAME NUM-HOSTS . SUBNETS), where NAME names the subnet, |
| 347 | NUM-HOSTS is the number of hosts in it, and SUBNETS are its sub-subnets in |
| 348 | the same form. An error is signalled if a net's subnets use up more hosts |
| 349 | than the net has to start with." |
| 350 | (labels ((frob (subnets limit finger) |
| 351 | (when subnets |
| 352 | (destructuring-bind (name size &rest subs) (car subnets) |
| 353 | (when (> (count-low-zero-bits size) |
| 354 | (count-low-zero-bits finger)) |
| 355 | (error "Bad subnet size for ~A." name)) |
| 356 | (when (> (+ finger size) limit) |
| 357 | (error "Subnet ~A out of range." name)) |
| 358 | (append (and name |
| 359 | (list (list name finger (- (ash 1 32) size)))) |
| 360 | (frob subs (+ finger size) finger) |
| 361 | (frob (cdr subnets) limit (+ finger size))))))) |
| 362 | (let ((ipn (ipnet addr))) |
| 363 | (with-ipnet (net mask) ipn |
| 364 | (unless (ipmask-cidl-slash mask) |
| 365 | (error "Bad mask for subnet form.")) |
| 366 | (cons (list root net mask) |
| 367 | (frob subnets (+ net (ipnet-hosts ipn) 1) net)))))) |
| 368 | |
| 369 | (defun net-create (name net) |
| 370 | "Construct a new network called NAME and add it to the map. The ARGS |
| 371 | describe the new network, in a form acceptable to the ipnet function." |
| 372 | (let ((ipn (ipnet net))) |
| 373 | (setf (net-find name) |
| 374 | (make-net :name (string-downcase (stringify name)) |
| 375 | :ipnet ipn |
| 376 | :hosts (ipnet-hosts ipn) |
| 377 | :next 1)))) |
| 378 | |
| 379 | (defmacro defnet (name net &rest subnets) |
| 380 | "Main network definition macro. None of the arguments is evaluated." |
| 381 | `(progn |
| 382 | ,@(loop for (name addr mask) in (process-net-form name net subnets) |
| 383 | collect `(net-create ',name '(,addr . ,mask))) |
| 384 | ',name)) |
| 385 | |
| 386 | (defun net-next-host (net) |
| 387 | "Given a NET, return the IP address (as integer) of the next available |
| 388 | address in the network." |
| 389 | (unless (< (net-next net) (net-hosts net)) |
| 390 | (error "No more hosts left in network ~A" (net-name net))) |
| 391 | (let ((next (net-next net))) |
| 392 | (incf (net-next net)) |
| 393 | (net-host net next))) |
| 394 | |
| 395 | (defun net-host (net host) |
| 396 | "Return the given HOST on the NEXT. HOST may be an index (in range, of |
| 397 | course), or one of the keywords: |
| 398 | |
| 399 | :NEXT next host, as by net-next-host |
| 400 | :NET network base address |
| 401 | :BROADCAST network broadcast address" |
| 402 | (case host |
| 403 | (:next (net-next-host net)) |
| 404 | (:net (ipnet-net (net-ipnet net))) |
| 405 | (:broadcast (ipnet-broadcast (net-ipnet net))) |
| 406 | (t (ipnet-host (net-ipnet net) host)))) |
| 407 | |
| 408 | ;;;----- That's all, folks -------------------------------------------------- |