1 /* $OpenBSD: rde_sets.c,v 1.12 2022/07/28 13:11:51 deraadt 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 * 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 * 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 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 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 105 as_set_match(const struct as_set *aset, uint32_t asnum) 106 { 107 return set_match(aset->set, asnum) != NULL; 108 } 109 110 struct set_table * 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 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 150 set_add(struct set_table *set, void *elms, size_t nelms) 151 { 152 if (set->max < nelms || set->max - nelms < set->nmemb) { 153 uint32_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((uint8_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 * 180 set_get(struct set_table *set, size_t *nelms) 181 { 182 *nelms = set->nmemb; 183 return set->set; 184 } 185 186 static int 187 set_cmp(const void *ap, const void *bp) 188 { 189 const uint32_t *a = ap; 190 const uint32_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 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 * 208 set_match(const struct set_table *a, uint32_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 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 232 set_nmemb(const struct set_table *set) 233 { 234 return set->nmemb; 235 } 236