1 /* $NetBSD: cidr_match.c,v 1.4 2022/10/08 16:12:50 christos Exp $ */ 2 3 /*++ 4 /* NAME 5 /* cidr_match 3 6 /* SUMMARY 7 /* CIDR-style pattern matching 8 /* SYNOPSIS 9 /* #include <cidr_match.h> 10 /* 11 /* VSTRING *cidr_match_parse(info, pattern, match, why) 12 /* CIDR_MATCH *info; 13 /* char *pattern; 14 /* VSTRING *why; 15 /* 16 /* int cidr_match_execute(info, address) 17 /* CIDR_MATCH *info; 18 /* const char *address; 19 /* AUXILIARY FUNCTIONS 20 /* VSTRING *cidr_match_parse_if(info, pattern, match, why) 21 /* CIDR_MATCH *info; 22 /* char *pattern; 23 /* VSTRING *why; 24 /* 25 /* void cidr_match_endif(info) 26 /* CIDR_MATCH *info; 27 /* DESCRIPTION 28 /* This module parses address or address/length patterns and 29 /* provides simple address matching. The implementation is 30 /* such that parsing and execution can be done without dynamic 31 /* memory allocation. The purpose is to minimize overhead when 32 /* called by functions that parse and execute on the fly, such 33 /* as match_hostaddr(). 34 /* 35 /* cidr_match_parse() parses an address or address/mask 36 /* expression and stores the result into the info argument. 37 /* A non-zero (or zero) match argument requests a positive (or 38 /* negative) match. The symbolic constants CIDR_MATCH_TRUE and 39 /* CIDR_MATCH_FALSE may help to improve code readability. 40 /* The result is non-zero in case of problems: either the 41 /* value of the why argument, or a newly allocated VSTRING 42 /* (the caller should give the latter to vstring_free()). 43 /* The pattern argument is destroyed. 44 /* 45 /* cidr_match_parse_if() parses the address that follows an IF 46 /* token, and stores the result into the info argument. 47 /* The arguments are the same as for cidr_match_parse(). 48 /* 49 /* cidr_match_endif() handles the occurrence of an ENDIF token, 50 /* and updates the info argument. 51 /* 52 /* cidr_match_execute() matches the specified address against 53 /* a list of parsed expressions, and returns the matching 54 /* expression's data structure. 55 /* SEE ALSO 56 /* dict_cidr(3) CIDR-style lookup table 57 /* AUTHOR(S) 58 /* Wietse Venema 59 /* IBM T.J. Watson Research 60 /* P.O. Box 704 61 /* Yorktown Heights, NY 10598, USA 62 /* 63 /* Wietse Venema 64 /* Google, Inc. 65 /* 111 8th Avenue 66 /* New York, NY 10011, USA 67 /*--*/ 68 69 /* System library. */ 70 71 #include <sys_defs.h> 72 #include <stdlib.h> 73 #include <unistd.h> 74 #include <string.h> 75 #include <ctype.h> 76 #include <sys/socket.h> 77 #include <netinet/in.h> 78 #include <arpa/inet.h> 79 80 /* Utility library. */ 81 82 #include <msg.h> 83 #include <vstring.h> 84 #include <stringops.h> 85 #include <split_at.h> 86 #include <myaddrinfo.h> 87 #include <mask_addr.h> 88 #include <cidr_match.h> 89 90 /* Application-specific. */ 91 92 /* 93 * This is how we figure out the address family, address bit count and 94 * address byte count for a CIDR_MATCH entry. 95 */ 96 #ifdef HAS_IPV6 97 #define CIDR_MATCH_ADDR_FAMILY(a) (strchr((a), ':') ? AF_INET6 : AF_INET) 98 #define CIDR_MATCH_ADDR_BIT_COUNT(f) \ 99 ((f) == AF_INET6 ? MAI_V6ADDR_BITS : \ 100 (f) == AF_INET ? MAI_V4ADDR_BITS : \ 101 (msg_panic("%s: bad address family %d", myname, (f)), 0)) 102 #define CIDR_MATCH_ADDR_BYTE_COUNT(f) \ 103 ((f) == AF_INET6 ? MAI_V6ADDR_BYTES : \ 104 (f) == AF_INET ? MAI_V4ADDR_BYTES : \ 105 (msg_panic("%s: bad address family %d", myname, (f)), 0)) 106 #else 107 #define CIDR_MATCH_ADDR_FAMILY(a) (AF_INET) 108 #define CIDR_MATCH_ADDR_BIT_COUNT(f) \ 109 ((f) == AF_INET ? MAI_V4ADDR_BITS : \ 110 (msg_panic("%s: bad address family %d", myname, (f)), 0)) 111 #define CIDR_MATCH_ADDR_BYTE_COUNT(f) \ 112 ((f) == AF_INET ? MAI_V4ADDR_BYTES : \ 113 (msg_panic("%s: bad address family %d", myname, (f)), 0)) 114 #endif 115 116 /* cidr_match_entry - match one entry */ 117 118 static inline int cidr_match_entry(CIDR_MATCH *entry, 119 unsigned char *addr_bytes) 120 { 121 unsigned char *mp; 122 unsigned char *np; 123 unsigned char *ap; 124 125 /* Unoptimized case: netmask with some or all bits zero. */ 126 if (entry->mask_shift < entry->addr_bit_count) { 127 for (np = entry->net_bytes, mp = entry->mask_bytes, 128 ap = addr_bytes; /* void */ ; np++, mp++, ap++) { 129 if (ap >= addr_bytes + entry->addr_byte_count) 130 return (entry->match); 131 if ((*ap & *mp) != *np) 132 break; 133 } 134 } 135 /* Optimized case: all 1 netmask (i.e. no netmask specified). */ 136 else { 137 for (np = entry->net_bytes, 138 ap = addr_bytes; /* void */ ; np++, ap++) { 139 if (ap >= addr_bytes + entry->addr_byte_count) 140 return (entry->match); 141 if (*ap != *np) 142 break; 143 } 144 } 145 return (!entry->match); 146 } 147 148 /* cidr_match_execute - match address against compiled CIDR pattern list */ 149 150 CIDR_MATCH *cidr_match_execute(CIDR_MATCH *list, const char *addr) 151 { 152 unsigned char addr_bytes[CIDR_MATCH_ABYTES]; 153 unsigned addr_family; 154 CIDR_MATCH *entry; 155 156 addr_family = CIDR_MATCH_ADDR_FAMILY(addr); 157 if (inet_pton(addr_family, addr, addr_bytes) != 1) 158 return (0); 159 160 for (entry = list; entry; entry = entry->next) { 161 162 switch (entry->op) { 163 164 case CIDR_MATCH_OP_MATCH: 165 if (entry->addr_family == addr_family) 166 if (cidr_match_entry(entry, addr_bytes)) 167 return (entry); 168 break; 169 170 case CIDR_MATCH_OP_IF: 171 if (entry->addr_family == addr_family) 172 if (cidr_match_entry(entry, addr_bytes)) 173 continue; 174 /* An IF without matching ENDIF has no end-of block entry. */ 175 if ((entry = entry->block_end) == 0) 176 return (0); 177 /* FALLTHROUGH */ 178 179 case CIDR_MATCH_OP_ENDIF: 180 continue; 181 } 182 } 183 return (0); 184 } 185 186 /* cidr_match_parse - parse CIDR pattern */ 187 188 VSTRING *cidr_match_parse(CIDR_MATCH *ip, char *pattern, int match, 189 VSTRING *why) 190 { 191 const char *myname = "cidr_match_parse"; 192 char *mask_search; 193 char *mask; 194 MAI_HOSTADDR_STR hostaddr; 195 unsigned char *np; 196 unsigned char *mp; 197 198 /* 199 * Strip [] from [addr/len] or [addr]/len, destroying the pattern. CIDR 200 * maps don't need [] to eliminate syntax ambiguity, but matchlists need 201 * it. While stripping [], figure out where we should start looking for 202 * /mask information. 203 */ 204 if (*pattern == '[') { 205 pattern++; 206 if ((mask_search = split_at(pattern, ']')) == 0) { 207 vstring_sprintf(why ? why : (why = vstring_alloc(20)), 208 "missing ']' character after \"[%s\"", pattern); 209 return (why); 210 } else if (*mask_search != '/') { 211 if (*mask_search != 0) { 212 vstring_sprintf(why ? why : (why = vstring_alloc(20)), 213 "garbage after \"[%s]\"", pattern); 214 return (why); 215 } 216 mask_search = pattern; 217 } 218 } else 219 mask_search = pattern; 220 221 /* 222 * Parse the pattern into network and mask, destroying the pattern. 223 */ 224 if ((mask = split_at(mask_search, '/')) != 0) { 225 const char *parse_error; 226 227 ip->addr_family = CIDR_MATCH_ADDR_FAMILY(pattern); 228 ip->addr_bit_count = CIDR_MATCH_ADDR_BIT_COUNT(ip->addr_family); 229 ip->addr_byte_count = CIDR_MATCH_ADDR_BYTE_COUNT(ip->addr_family); 230 if (!alldig(mask)) { 231 parse_error = "bad mask value"; 232 } else if ((ip->mask_shift = atoi(mask)) > ip->addr_bit_count) { 233 parse_error = "bad mask length"; 234 } else if (inet_pton(ip->addr_family, pattern, ip->net_bytes) != 1) { 235 parse_error = "bad network value"; 236 } else { 237 parse_error = 0; 238 } 239 if (parse_error != 0) { 240 vstring_sprintf(why ? why : (why = vstring_alloc(20)), 241 "%s in \"%s/%s\"", parse_error, pattern, mask); 242 return (why); 243 } 244 if (ip->mask_shift > 0) { 245 /* Allow for bytes > 8. */ 246 memset(ip->mask_bytes, ~0U, ip->addr_byte_count); 247 mask_addr(ip->mask_bytes, ip->addr_byte_count, ip->mask_shift); 248 } else 249 memset(ip->mask_bytes, 0, ip->addr_byte_count); 250 251 /* 252 * Sanity check: all host address bits must be zero. 253 */ 254 for (np = ip->net_bytes, mp = ip->mask_bytes; 255 np < ip->net_bytes + ip->addr_byte_count; np++, mp++) { 256 if (*np & ~(*mp)) { 257 mask_addr(ip->net_bytes, ip->addr_byte_count, ip->mask_shift); 258 if (inet_ntop(ip->addr_family, ip->net_bytes, hostaddr.buf, 259 sizeof(hostaddr.buf)) == 0) 260 msg_fatal("inet_ntop: %m"); 261 vstring_sprintf(why ? why : (why = vstring_alloc(20)), 262 "non-null host address bits in \"%s/%s\", " 263 "perhaps you should use \"%s/%d\" instead", 264 pattern, mask, hostaddr.buf, ip->mask_shift); 265 return (why); 266 } 267 } 268 } 269 270 /* 271 * No /mask specified. Treat a bare network address as /allbits. 272 */ 273 else { 274 ip->addr_family = CIDR_MATCH_ADDR_FAMILY(pattern); 275 ip->addr_bit_count = CIDR_MATCH_ADDR_BIT_COUNT(ip->addr_family); 276 ip->addr_byte_count = CIDR_MATCH_ADDR_BYTE_COUNT(ip->addr_family); 277 if (inet_pton(ip->addr_family, pattern, ip->net_bytes) != 1) { 278 vstring_sprintf(why ? why : (why = vstring_alloc(20)), 279 "bad address pattern: \"%s\"", pattern); 280 return (why); 281 } 282 ip->mask_shift = ip->addr_bit_count; 283 /* Allow for bytes > 8. */ 284 memset(ip->mask_bytes, ~0U, ip->addr_byte_count); 285 } 286 287 /* 288 * Wrap up the result. 289 */ 290 ip->op = CIDR_MATCH_OP_MATCH; 291 ip->match = match; 292 ip->next = 0; 293 ip->block_end = 0; 294 295 return (0); 296 } 297 298 /* cidr_match_parse_if - parse CIDR pattern after IF */ 299 300 VSTRING *cidr_match_parse_if(CIDR_MATCH *ip, char *pattern, int match, 301 VSTRING *why) 302 { 303 VSTRING *ret; 304 305 if ((ret = cidr_match_parse(ip, pattern, match, why)) == 0) 306 ip->op = CIDR_MATCH_OP_IF; 307 return (ret); 308 } 309 310 /* cidr_match_endif - handle ENDIF pattern */ 311 312 void cidr_match_endif(CIDR_MATCH *ip) 313 { 314 memset(ip, 0, sizeof(*ip)); 315 ip->op = CIDR_MATCH_OP_ENDIF; 316 ip->next = 0; /* maybe not all bits 0 */ 317 ip->block_end = 0; 318 } 319