diff options
Diffstat (limited to 'src/fnettrace/radix.c')
-rw-r--r-- | src/fnettrace/radix.c | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/src/fnettrace/radix.c b/src/fnettrace/radix.c new file mode 100644 index 000000000..a1f44dd31 --- /dev/null +++ b/src/fnettrace/radix.c | |||
@@ -0,0 +1,218 @@ | |||
1 | /* | ||
2 | * Copyright (C) 2014-2022 Firejail Authors | ||
3 | * | ||
4 | * This file is part of firejail project | ||
5 | * | ||
6 | * This program is free software; you can redistribute it and/or modify | ||
7 | * it under the terms of the GNU General Public License as published by | ||
8 | * the Free Software Foundation; either version 2 of the License, or | ||
9 | * (at your option) any later version. | ||
10 | * | ||
11 | * This program is distributed in the hope that it will be useful, | ||
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
14 | * GNU General Public License for more details. | ||
15 | * | ||
16 | * You should have received a copy of the GNU General Public License along | ||
17 | * with this program; if not, write to the Free Software Foundation, Inc., | ||
18 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. | ||
19 | */ | ||
20 | #include <stdio.h> | ||
21 | #include <stdlib.h> | ||
22 | #include <string.h> | ||
23 | #include <stdint.h> | ||
24 | #include <assert.h> | ||
25 | #include "radix.h" | ||
26 | #include "fnettrace.h" | ||
27 | |||
28 | RNode *head = 0; | ||
29 | |||
30 | static inline RNode *addOne(RNode *ptr, uint32_t ip, uint32_t mask, char *name) { | ||
31 | assert(ptr); | ||
32 | if (ptr->one) | ||
33 | return ptr->one; | ||
34 | RNode *node = malloc(sizeof(RNode)); | ||
35 | if (!node) | ||
36 | errExit("malloc"); | ||
37 | memset(node, 0, sizeof(RNode)); | ||
38 | node->ip = ip; | ||
39 | node->mask = mask; | ||
40 | if (name) { | ||
41 | node->name = strdup(name); | ||
42 | if (!node->name) | ||
43 | errExit("strdup"); | ||
44 | } | ||
45 | |||
46 | ptr->one = node; | ||
47 | return node; | ||
48 | } | ||
49 | |||
50 | static inline RNode *addZero(RNode *ptr, uint32_t ip, uint32_t mask, char *name) { | ||
51 | assert(ptr); | ||
52 | if (ptr->zero) | ||
53 | return ptr->zero; | ||
54 | RNode *node = malloc(sizeof(RNode)); | ||
55 | if (!node) | ||
56 | errExit("malloc"); | ||
57 | memset(node, 0, sizeof(RNode)); | ||
58 | node->ip = ip; | ||
59 | node->mask = mask; | ||
60 | if (name) { | ||
61 | node->name = strdup(name); | ||
62 | if (!node->name) | ||
63 | errExit("strdup"); | ||
64 | } | ||
65 | |||
66 | ptr->zero = node; | ||
67 | return node; | ||
68 | } | ||
69 | |||
70 | |||
71 | // add to radix tree | ||
72 | void radix_add(uint32_t ip, uint32_t mask, char *name) { | ||
73 | assert(name); | ||
74 | char *tmp = strdup(name); | ||
75 | if (!tmp) | ||
76 | errExit("strdup"); | ||
77 | name = tmp; | ||
78 | |||
79 | uint32_t m = 0x80000000; | ||
80 | uint32_t lastm = 0; | ||
81 | if (head == 0) { | ||
82 | head = malloc(sizeof(RNode)); | ||
83 | memset(head, 0, sizeof(RNode)); | ||
84 | } | ||
85 | RNode *ptr = head; | ||
86 | |||
87 | int i; | ||
88 | for (i = 0; i < 32; i++, m >>= 1) { | ||
89 | if (!(m & mask)) | ||
90 | break; | ||
91 | |||
92 | lastm |= m; | ||
93 | int valid = (lastm == mask)? 1: 0; | ||
94 | if (m & ip) | ||
95 | ptr = addOne(ptr, ip & lastm, mask & lastm, (valid)? name: NULL); | ||
96 | else | ||
97 | ptr = addZero(ptr, ip & lastm, mask & lastm, (valid)? name: NULL); | ||
98 | } | ||
99 | assert(ptr); | ||
100 | if (!ptr->name) { | ||
101 | ptr->name = strdup(name); | ||
102 | if (!ptr->name) | ||
103 | errExit("strdup"); | ||
104 | } | ||
105 | } | ||
106 | |||
107 | // find first match | ||
108 | char *radix_find_first(uint32_t ip) { | ||
109 | if (!head) | ||
110 | return NULL; | ||
111 | |||
112 | uint32_t m = 0x80000000; | ||
113 | RNode *ptr = head; | ||
114 | |||
115 | int i; | ||
116 | for (i = 0; i < 32; i++, m >>= 1) { | ||
117 | if (m & ip) | ||
118 | ptr = ptr->one; | ||
119 | else | ||
120 | ptr = ptr->zero; | ||
121 | if (!ptr) | ||
122 | return NULL; | ||
123 | if (ptr->name) | ||
124 | return ptr->name; | ||
125 | } | ||
126 | return NULL; | ||
127 | } | ||
128 | |||
129 | // find last match | ||
130 | char *radix_find_last(uint32_t ip) { | ||
131 | if (!head) | ||
132 | return NULL; | ||
133 | |||
134 | uint32_t m = 0x80000000; | ||
135 | RNode *ptr = head; | ||
136 | RNode *rv = NULL; | ||
137 | |||
138 | int i; | ||
139 | for (i = 0; i < 32; i++, m >>= 1) { | ||
140 | if (m & ip) | ||
141 | ptr = ptr->one; | ||
142 | else | ||
143 | ptr = ptr->zero; | ||
144 | if (!ptr) | ||
145 | break; | ||
146 | if (ptr->name) | ||
147 | rv = ptr; | ||
148 | } | ||
149 | |||
150 | return (rv)? rv->name: NULL; | ||
151 | } | ||
152 | |||
153 | static void radix_print_node(RNode *ptr, int level) { | ||
154 | assert(ptr); | ||
155 | |||
156 | int i; | ||
157 | for (i = 0; i < level; i++) | ||
158 | printf(" "); | ||
159 | printf("%08x %08x", ptr->ip, ptr->mask); | ||
160 | if (ptr->name) | ||
161 | printf(" (%s)\n", ptr->name); | ||
162 | else | ||
163 | printf(" (NULL)\n"); | ||
164 | |||
165 | if (ptr->zero) | ||
166 | radix_print_node(ptr->zero, level + 1); | ||
167 | if (ptr->one) | ||
168 | radix_print_node(ptr->one, level + 1); | ||
169 | } | ||
170 | |||
171 | void radix_print(void) { | ||
172 | if (!head) { | ||
173 | printf("radix tree is empty\n"); | ||
174 | return; | ||
175 | } | ||
176 | |||
177 | printf("radix IPv4 tree\n"); | ||
178 | radix_print_node(head, 0); | ||
179 | } | ||
180 | |||
181 | |||
182 | static inline int mask2cidr(uint32_t mask) { | ||
183 | uint32_t m = 0x80000000; | ||
184 | int i; | ||
185 | int cnt = 0; | ||
186 | for (i = 0; i < 32; i++, m = m >> 1) { | ||
187 | if (mask & m) | ||
188 | cnt++; | ||
189 | } | ||
190 | |||
191 | return cnt; | ||
192 | } | ||
193 | |||
194 | static void radix_build_list_node(RNode *ptr) { | ||
195 | assert(ptr); | ||
196 | |||
197 | |||
198 | if (ptr->name) { | ||
199 | printf("%d.%d.%d.%d/%d %s\n", PRINT_IP(ptr->ip), mask2cidr(ptr->mask), ptr->name); | ||
200 | return; | ||
201 | } | ||
202 | else { | ||
203 | if (ptr->zero) | ||
204 | radix_build_list_node(ptr->zero); | ||
205 | if (ptr->one) | ||
206 | radix_build_list_node(ptr->one); | ||
207 | } | ||
208 | } | ||
209 | |||
210 | void radix_build_list(void) { | ||
211 | if (!head) { | ||
212 | printf("radix tree is empty\n"); | ||
213 | return; | ||
214 | } | ||
215 | |||
216 | radix_build_list_node(head); | ||
217 | } | ||
218 | |||