1 /* $OpenBSD: rde_sets.c,v 1.10 2020/12/30 07:29:56 claudio Exp $ */
2
3 /*
4 * Copyright (c) 2018 Claudio Jeker <claudio@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18 #include <sys/types.h>
19 #include <sys/queue.h>
20
21 #include <assert.h>
22 #include <errno.h>
23 #include <limits.h>
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <string.h>
27
28 #include "rde.h"
29
30 struct set_table {
31 void *set;
32 size_t nmemb;
33 size_t size;
34 size_t max;
35 };
36
37 struct as_set *
as_sets_new(struct as_set_head * as_sets,const char * name,size_t nmemb,size_t size)38 as_sets_new(struct as_set_head *as_sets, const char *name, size_t nmemb,
39 size_t size)
40 {
41 struct as_set *aset;
42 size_t len;
43
44 aset = calloc(1, sizeof(*aset));
45 if (aset == NULL)
46 return NULL;
47
48 len = strlcpy(aset->name, name, sizeof(aset->name));
49 assert(len < sizeof(aset->name));
50
51 aset->set = set_new(nmemb, size);
52 if (aset->set == NULL) {
53 free(aset);
54 return NULL;
55 }
56
57 SIMPLEQ_INSERT_TAIL(as_sets, aset, entry);
58 return aset;
59 }
60
61 struct as_set *
as_sets_lookup(struct as_set_head * as_sets,const char * name)62 as_sets_lookup(struct as_set_head *as_sets, const char *name)
63 {
64 struct as_set *aset;
65
66 SIMPLEQ_FOREACH(aset, as_sets, entry) {
67 if (strcmp(aset->name, name) == 0)
68 return aset;
69 }
70 return NULL;
71 }
72
73
74 void
as_sets_free(struct as_set_head * as_sets)75 as_sets_free(struct as_set_head *as_sets)
76 {
77 struct as_set *aset;
78
79 if (as_sets == NULL)
80 return;
81 while (!SIMPLEQ_EMPTY(as_sets)) {
82 aset = SIMPLEQ_FIRST(as_sets);
83 SIMPLEQ_REMOVE_HEAD(as_sets, entry);
84 set_free(aset->set);
85 free(aset);
86 }
87 }
88
89 void
as_sets_mark_dirty(struct as_set_head * old,struct as_set_head * new)90 as_sets_mark_dirty(struct as_set_head *old, struct as_set_head *new)
91 {
92 struct as_set *n, *o;
93
94 SIMPLEQ_FOREACH(n, new, entry) {
95 if (old == NULL || (o = as_sets_lookup(old, n->name)) == NULL ||
96 !set_equal(n->set, o->set)) {
97 n->dirty = 1;
98 n->lastchange = getmonotime();
99 } else
100 n->lastchange = o->lastchange;
101 }
102 }
103
104 int
as_set_match(const struct as_set * aset,u_int32_t asnum)105 as_set_match(const struct as_set *aset, u_int32_t asnum)
106 {
107 return set_match(aset->set, asnum) != NULL;
108 }
109
110 struct set_table *
set_new(size_t nmemb,size_t size)111 set_new(size_t nmemb, size_t size)
112 {
113 struct set_table *set;
114
115 set = calloc(1, sizeof(*set));
116 if (set == NULL)
117 return NULL;
118
119 if (nmemb == 0)
120 nmemb = 4;
121
122 set->size = size;
123 set->max = nmemb;
124 set->set = calloc(nmemb, set->size);
125 if (set->set == NULL) {
126 free(set);
127 return NULL;
128 }
129
130 rdemem.aset_cnt++;
131 rdemem.aset_size += sizeof(*set);
132 rdemem.aset_size += set->size * set->max;
133 return set;
134 }
135
136 void
set_free(struct set_table * set)137 set_free(struct set_table *set)
138 {
139 if (set == NULL)
140 return;
141 rdemem.aset_cnt--;
142 rdemem.aset_size -= sizeof(*set);
143 rdemem.aset_size -= set->size * set->max;
144 rdemem.aset_nmemb -= set->nmemb;
145 free(set->set);
146 free(set);
147 }
148
149 int
set_add(struct set_table * set,void * elms,size_t nelms)150 set_add(struct set_table *set, void *elms, size_t nelms)
151 {
152 if (set->max < nelms || set->max - nelms < set->nmemb) {
153 u_int32_t *s;
154 size_t new_size;
155
156 if (set->nmemb >= SIZE_MAX - 4096 - nelms) {
157 errno = ENOMEM;
158 return -1;
159 }
160 for (new_size = set->max; new_size < set->nmemb + nelms; )
161 new_size += (new_size < 4096 ? new_size : 4096);
162
163 s = reallocarray(set->set, new_size, set->size);
164 if (s == NULL)
165 return -1;
166 rdemem.aset_size += set->size * (new_size - set->max);
167 set->set = s;
168 set->max = new_size;
169 }
170
171 memcpy((u_int8_t *)set->set + set->nmemb * set->size, elms,
172 nelms * set->size);
173 set->nmemb += nelms;
174 rdemem.aset_nmemb += nelms;
175
176 return 0;
177 }
178
179 void *
set_get(struct set_table * set,size_t * nelms)180 set_get(struct set_table *set, size_t *nelms)
181 {
182 *nelms = set->nmemb;
183 return set->set;
184 }
185
186 static int
set_cmp(const void * ap,const void * bp)187 set_cmp(const void *ap, const void *bp)
188 {
189 const u_int32_t *a = ap;
190 const u_int32_t *b = bp;
191
192 if (*a > *b)
193 return 1;
194 else if (*a < *b)
195 return -1;
196 return 0;
197 }
198
199 void
set_prep(struct set_table * set)200 set_prep(struct set_table *set)
201 {
202 if (set == NULL)
203 return;
204 qsort(set->set, set->nmemb, set->size, set_cmp);
205 }
206
207 void *
set_match(const struct set_table * a,u_int32_t asnum)208 set_match(const struct set_table *a, u_int32_t asnum)
209 {
210 if (a == NULL)
211 return NULL;
212 return bsearch(&asnum, a->set, a->nmemb, a->size, set_cmp);
213 }
214
215 int
set_equal(const struct set_table * a,const struct set_table * b)216 set_equal(const struct set_table *a, const struct set_table *b)
217 {
218 /* allow NULL pointers to be passed */
219 if (a == NULL && b == NULL)
220 return 1;
221 if (a == NULL || b == NULL)
222 return 0;
223
224 if (a->nmemb != b->nmemb)
225 return 0;
226 if (memcmp(a->set, b->set, a->nmemb * a->size) != 0)
227 return 0;
228 return 1;
229 }
230
231 size_t
set_nmemb(const struct set_table * set)232 set_nmemb(const struct set_table *set)
233 {
234 return set->nmemb;
235 }
236