1 /*-
2 * Copyright 2016 Vsevolod Stakhov
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #include "config.h"
17 #include "radix.h"
18 #include "btrie.h"
19 #include "mempool.h"
20
21 struct radix_tree_compressed {
22 struct mempool pool;
23 size_t size;
24 struct btrie *tree;
25 };
26
27 uintptr_t
radix_find_compressed(radix_compressed_t * tree,const guint8 * key,gsize keylen)28 radix_find_compressed (radix_compressed_t * tree, const guint8 *key, gsize keylen)
29 {
30 gconstpointer ret;
31
32 if (tree == NULL) {
33 return RADIX_NO_VALUE;
34 }
35
36 ret = btrie_lookup (tree->tree, key, keylen * NBBY);
37
38 if (ret == NULL) {
39 return RADIX_NO_VALUE;
40 }
41
42 return (uintptr_t)ret;
43 }
44
45
46 uintptr_t
radix_insert_compressed(radix_compressed_t * tree,guint8 * key,gsize keylen,gsize masklen,uintptr_t value)47 radix_insert_compressed (radix_compressed_t * tree,
48 guint8 *key, gsize keylen,
49 gsize masklen,
50 uintptr_t value)
51 {
52 guint keybits = keylen * NBBY;
53 uintptr_t old;
54 gchar ip_str[INET6_ADDRSTRLEN + 1];
55 int ret;
56
57 if (tree == NULL) {
58 return NULL;
59 }
60
61 g_assert (keybits >= masklen);
62
63 old = radix_find_compressed (tree, key, keylen);
64
65 ret = btrie_add_prefix (tree->tree, key, keybits - masklen,
66 (gconstpointer)value);
67
68 if (ret != BTRIE_OKAY) {
69 memset (ip_str, 0, sizeof (ip_str));
70
71 if (keybits == 32) {
72 msg_err ("cannot insert %p, key: %s/%d, duplicate value",
73 (gpointer)value,
74 inet_ntop (AF_INET, key, ip_str, sizeof (ip_str) - 1),
75 (int)(keybits - masklen));
76 }
77 else if (keybits == 128) {
78 msg_err ("cannot insert %p, key: [%s]/%d, duplicate value",
79 (gpointer)value,
80 inet_ntop (AF_INET6, key, ip_str, sizeof (ip_str) - 1),
81 (int)(keybits - masklen));
82 }
83 else {
84 msg_err ("cannot insert %p with mask %d, key: unknown, duplicate value",
85 (gpointer)value, (int)(keybits - masklen));
86 }
87 }
88 else {
89 tree->size ++;
90 }
91
92 return old;
93 }
94
95
96 radix_compressed_t *
radix_create_compressed(void)97 radix_create_compressed (void)
98 {
99 radix_compressed_t *tree;
100
101 tree = calloc (1, sizeof (*tree));
102 if (tree == NULL) {
103 return NULL;
104 }
105
106 mp_init (&tree->pool);
107 tree->size = 0;
108 tree->tree = btrie_init (&tree->pool);
109
110 return tree;
111 }
112
113 void
radix_destroy_compressed(radix_compressed_t * tree)114 radix_destroy_compressed (radix_compressed_t *tree)
115 {
116 if (tree) {
117 mp_free (&tree->pool);
118 free (tree);
119 }
120 }
121
122 gint
rspamd_radix_add_iplist(const gchar * list,const gchar * separators,radix_compressed_t * tree,gconstpointer value,gboolean resolve)123 rspamd_radix_add_iplist (const gchar *list, const gchar *separators,
124 radix_compressed_t *tree, gconstpointer value, gboolean resolve)
125 {
126 gchar *token, *ipnet, *err_str, **strv, **cur, *brace;
127 struct in_addr ina;
128 struct in6_addr ina6;
129 guint k = G_MAXINT;
130 gint af;
131 gint res = 0, r;
132 struct addrinfo hints, *ai_res, *cur_ai;
133
134 /* Split string if there are multiple items inside a single string */
135 strv = g_strsplit_set (list, separators, 0);
136 cur = strv;
137 while (*cur) {
138 af = AF_UNSPEC;
139 if (**cur == '\0') {
140 cur++;
141 continue;
142 }
143 /* Extract ipnet */
144 ipnet = *cur;
145 token = strsep (&ipnet, "/");
146
147 if (ipnet != NULL) {
148 errno = 0;
149 /* Get mask */
150 k = strtoul (ipnet, &err_str, 10);
151 if (errno != 0) {
152 msg_warn (
153 "invalid netmask, error detected on symbol: %s, erorr: %s",
154 err_str,
155 strerror (errno));
156 k = G_MAXINT;
157 }
158 }
159
160 /* Check IP */
161 if (token[0] == '[') {
162 /* Braced IPv6 */
163 brace = strrchr (token, ']');
164
165 if (brace != NULL) {
166 token ++;
167 *brace = '\0';
168
169 if (inet_pton (AF_INET6, token, &ina6) == 1) {
170 af = AF_INET6;
171 }
172 else {
173 msg_warn ("invalid IP address: %s", token);
174
175 cur ++;
176 continue;
177 }
178 }
179 else {
180 msg_warn ("invalid IP address: %s", token);
181
182 cur ++;
183 continue;
184 }
185 }
186 else {
187 if (inet_pton (AF_INET, token, &ina) == 1) {
188 af = AF_INET;
189 }
190 else if (inet_pton (AF_INET6, token, &ina6) == 1) {
191 af = AF_INET6;
192 }
193 else {
194
195 if (resolve) {
196 memset (&hints, 0, sizeof (hints));
197 hints.ai_socktype = SOCK_STREAM; /* Type of the socket */
198 hints.ai_flags = AI_NUMERICSERV;
199 hints.ai_family = AF_UNSPEC;
200
201 if ((r = getaddrinfo (token, NULL, &hints, &ai_res)) == 0) {
202 for (cur_ai = ai_res; cur_ai != NULL;
203 cur_ai = cur_ai->ai_next) {
204
205 if (cur_ai->ai_family == AF_INET) {
206 struct sockaddr_in *sin;
207
208 sin = (struct sockaddr_in *)cur_ai->ai_addr;
209 if (k > 32) {
210 k = 32;
211 }
212
213 radix_insert_compressed (tree,
214 (guint8 *)&sin->sin_addr,
215 sizeof (sin->sin_addr),
216 32 - k, (uintptr_t)value);
217 res ++;
218 }
219 else if (cur_ai->ai_family == AF_INET6) {
220 struct sockaddr_in6 *sin6;
221
222 sin6 = (struct sockaddr_in6 *)cur_ai->ai_addr;
223 if (k > 128) {
224 k = 128;
225 }
226
227 radix_insert_compressed (tree,
228 (guint8 *)&sin6->sin6_addr,
229 sizeof (sin6->sin6_addr),
230 128 - k, (uintptr_t)value);
231 res ++;
232 }
233 }
234
235 freeaddrinfo (ai_res);
236 }
237 else {
238 msg_warn ("getaddrinfo failed for %s: %s", token,
239 gai_strerror (r));
240 }
241
242 cur ++;
243 continue;
244 }
245 else {
246 msg_warn ("invalid IP address: %s", token);
247
248 cur ++;
249 continue;
250 }
251 }
252 }
253
254 if (af == AF_INET) {
255 if (k > 32) {
256 k = 32;
257 }
258 radix_insert_compressed (tree, (guint8 *)&ina, sizeof (ina),
259 32 - k, (uintptr_t)value);
260 res ++;
261 }
262 else if (af == AF_INET6){
263 if (k > 128) {
264 k = 128;
265 }
266 radix_insert_compressed (tree, (guint8 *)&ina6, sizeof (ina6),
267 128 - k, (uintptr_t)value);
268 res ++;
269 }
270 cur++;
271 }
272
273 g_strfreev (strv);
274
275 return res;
276 }
277
278 gboolean
radix_add_generic_iplist(const gchar * ip_list,radix_compressed_t ** tree,gboolean resolve)279 radix_add_generic_iplist (const gchar *ip_list, radix_compressed_t **tree,
280 gboolean resolve)
281 {
282 if (*tree == NULL) {
283 *tree = radix_create_compressed ();
284 }
285
286 return (rspamd_radix_add_iplist (ip_list, ",; ", *tree,
287 GINT_TO_POINTER (1), resolve) > 0);
288 }
289
290
291 gsize
radix_get_size(radix_compressed_t * tree)292 radix_get_size (radix_compressed_t *tree)
293 {
294 if (tree != NULL) {
295 return tree->size;
296 }
297
298 return 0;
299 }
300
301
302
303 const gchar *
radix_get_info(radix_compressed_t * tree)304 radix_get_info (radix_compressed_t *tree)
305 {
306 if (tree == NULL) {
307 return NULL;
308 }
309
310 return btrie_stats (tree->tree);
311 }
312
313 uintptr_t
radix_find_rmilter_addr(radix_compressed_t * tree,const struct rmilter_inet_address * addr)314 radix_find_rmilter_addr (radix_compressed_t * tree,
315 const struct rmilter_inet_address *addr)
316 {
317 const uint8_t *key;
318 size_t keylen;
319
320 switch (addr->family) {
321 case AF_INET:
322 key = (const uint8_t *)&addr->addr.sa4.sin_addr;
323 keylen = sizeof (addr->addr.sa4.sin_addr);
324 break;
325 case AF_INET6:
326 key = (const uint8_t *)&addr->addr.sa6.sin6_addr;
327 keylen = sizeof (addr->addr.sa6.sin6_addr);
328 break;
329 default:
330 return RADIX_NO_VALUE;
331 }
332
333 return radix_find_compressed (tree, key, keylen);
334 }
335