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
cidr_match_entry(CIDR_MATCH * entry,unsigned char * addr_bytes)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
cidr_match_execute(CIDR_MATCH * list,const char * addr)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
cidr_match_parse(CIDR_MATCH * ip,char * pattern,int match,VSTRING * why)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
cidr_match_parse_if(CIDR_MATCH * ip,char * pattern,int match,VSTRING * why)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
cidr_match_endif(CIDR_MATCH * ip)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