1
2 /* Author : Stephen Smalley, <sds@tycho.nsa.gov> */
3
4 /* FLASK */
5
6 /*
7 * Implementation of the SID table type.
8 */
9
10 #include <stdlib.h>
11 #include <errno.h>
12 #include <limits.h>
13 #include <stdio.h>
14
15 #include <sepol/policydb/sidtab.h>
16
17 #include "flask.h"
18
19 #define SIDTAB_HASH(sid) \
20 (sid & SIDTAB_HASH_MASK)
21
22 #define INIT_SIDTAB_LOCK(s)
23 #define SIDTAB_LOCK(s)
24 #define SIDTAB_UNLOCK(s)
25
sepol_sidtab_init(sidtab_t * s)26 int sepol_sidtab_init(sidtab_t * s)
27 {
28 int i;
29
30 s->htable = malloc(sizeof(sidtab_ptr_t) * SIDTAB_SIZE);
31 if (!s->htable)
32 return -ENOMEM;
33 for (i = 0; i < SIDTAB_SIZE; i++)
34 s->htable[i] = (sidtab_ptr_t) NULL;
35 s->nel = 0;
36 s->next_sid = 1;
37 s->shutdown = 0;
38 INIT_SIDTAB_LOCK(s);
39 return 0;
40 }
41
sepol_sidtab_insert(sidtab_t * s,sepol_security_id_t sid,context_struct_t * context)42 int sepol_sidtab_insert(sidtab_t * s, sepol_security_id_t sid,
43 context_struct_t * context)
44 {
45 int hvalue;
46 sidtab_node_t *prev, *cur, *newnode;
47
48 if (!s || !s->htable)
49 return -ENOMEM;
50
51 hvalue = SIDTAB_HASH(sid);
52 prev = NULL;
53 cur = s->htable[hvalue];
54 while (cur != NULL && sid > cur->sid) {
55 prev = cur;
56 cur = cur->next;
57 }
58
59 if (cur && sid == cur->sid) {
60 errno = EEXIST;
61 return -EEXIST;
62 }
63
64 newnode = (sidtab_node_t *) malloc(sizeof(sidtab_node_t));
65 if (newnode == NULL)
66 return -ENOMEM;
67 newnode->sid = sid;
68 if (context_cpy(&newnode->context, context)) {
69 free(newnode);
70 return -ENOMEM;
71 }
72
73 if (prev) {
74 newnode->next = prev->next;
75 prev->next = newnode;
76 } else {
77 newnode->next = s->htable[hvalue];
78 s->htable[hvalue] = newnode;
79 }
80
81 s->nel++;
82 if (sid >= s->next_sid)
83 s->next_sid = sid + 1;
84 return 0;
85 }
86
sepol_sidtab_search(sidtab_t * s,sepol_security_id_t sid)87 context_struct_t *sepol_sidtab_search(sidtab_t * s, sepol_security_id_t sid)
88 {
89 int hvalue;
90 sidtab_node_t *cur;
91
92 if (!s || !s->htable)
93 return NULL;
94
95 hvalue = SIDTAB_HASH(sid);
96 cur = s->htable[hvalue];
97 while (cur != NULL && sid > cur->sid)
98 cur = cur->next;
99
100 if (cur == NULL || sid != cur->sid) {
101 /* Remap invalid SIDs to the unlabeled SID. */
102 sid = SECINITSID_UNLABELED;
103 hvalue = SIDTAB_HASH(sid);
104 cur = s->htable[hvalue];
105 while (cur != NULL && sid > cur->sid)
106 cur = cur->next;
107 if (!cur || sid != cur->sid)
108 return NULL;
109 }
110
111 return &cur->context;
112 }
113
sepol_sidtab_map(sidtab_t * s,int (* apply)(sepol_security_id_t sid,context_struct_t * context,void * args),void * args)114 int sepol_sidtab_map(sidtab_t * s,
115 int (*apply) (sepol_security_id_t sid,
116 context_struct_t * context,
117 void *args), void *args)
118 {
119 int i, ret;
120 sidtab_node_t *cur;
121
122 if (!s || !s->htable)
123 return 0;
124
125 for (i = 0; i < SIDTAB_SIZE; i++) {
126 cur = s->htable[i];
127 while (cur != NULL) {
128 ret = apply(cur->sid, &cur->context, args);
129 if (ret)
130 return ret;
131 cur = cur->next;
132 }
133 }
134 return 0;
135 }
136
sepol_sidtab_map_remove_on_error(sidtab_t * s,int (* apply)(sepol_security_id_t sid,context_struct_t * context,void * args),void * args)137 void sepol_sidtab_map_remove_on_error(sidtab_t * s,
138 int (*apply) (sepol_security_id_t sid,
139 context_struct_t * context,
140 void *args), void *args)
141 {
142 int i, ret;
143 sidtab_node_t *last, *cur, *temp;
144
145 if (!s || !s->htable)
146 return;
147
148 for (i = 0; i < SIDTAB_SIZE; i++) {
149 last = NULL;
150 cur = s->htable[i];
151 while (cur != NULL) {
152 ret = apply(cur->sid, &cur->context, args);
153 if (ret) {
154 if (last) {
155 last->next = cur->next;
156 } else {
157 s->htable[i] = cur->next;
158 }
159
160 temp = cur;
161 cur = cur->next;
162 context_destroy(&temp->context);
163 free(temp);
164 s->nel--;
165 } else {
166 last = cur;
167 cur = cur->next;
168 }
169 }
170 }
171
172 return;
173 }
174
sepol_sidtab_search_context(sidtab_t * s,context_struct_t * context)175 static inline sepol_security_id_t sepol_sidtab_search_context(sidtab_t * s,
176 context_struct_t *
177 context)
178 {
179 int i;
180 sidtab_node_t *cur;
181
182 for (i = 0; i < SIDTAB_SIZE; i++) {
183 cur = s->htable[i];
184 while (cur != NULL) {
185 if (context_cmp(&cur->context, context))
186 return cur->sid;
187 cur = cur->next;
188 }
189 }
190 return 0;
191 }
192
sepol_sidtab_context_to_sid(sidtab_t * s,context_struct_t * context,sepol_security_id_t * out_sid)193 int sepol_sidtab_context_to_sid(sidtab_t * s,
194 context_struct_t * context,
195 sepol_security_id_t * out_sid)
196 {
197 sepol_security_id_t sid;
198 int ret = 0;
199
200 *out_sid = SEPOL_SECSID_NULL;
201
202 sid = sepol_sidtab_search_context(s, context);
203 if (!sid) {
204 SIDTAB_LOCK(s);
205 /* Rescan now that we hold the lock. */
206 sid = sepol_sidtab_search_context(s, context);
207 if (sid)
208 goto unlock_out;
209 /* No SID exists for the context. Allocate a new one. */
210 if (s->next_sid == UINT_MAX || s->shutdown) {
211 ret = -ENOMEM;
212 goto unlock_out;
213 }
214 sid = s->next_sid++;
215 ret = sepol_sidtab_insert(s, sid, context);
216 if (ret)
217 s->next_sid--;
218 unlock_out:
219 SIDTAB_UNLOCK(s);
220 }
221
222 if (ret)
223 return ret;
224
225 *out_sid = sid;
226 return 0;
227 }
228
sepol_sidtab_hash_eval(sidtab_t * h,char * tag)229 void sepol_sidtab_hash_eval(sidtab_t * h, char *tag)
230 {
231 int i, chain_len, slots_used, max_chain_len;
232 sidtab_node_t *cur;
233
234 slots_used = 0;
235 max_chain_len = 0;
236 for (i = 0; i < SIDTAB_SIZE; i++) {
237 cur = h->htable[i];
238 if (cur) {
239 slots_used++;
240 chain_len = 0;
241 while (cur) {
242 chain_len++;
243 cur = cur->next;
244 }
245
246 if (chain_len > max_chain_len)
247 max_chain_len = chain_len;
248 }
249 }
250
251 printf
252 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
253 tag, h->nel, slots_used, SIDTAB_SIZE, max_chain_len);
254 }
255
sepol_sidtab_destroy(sidtab_t * s)256 void sepol_sidtab_destroy(sidtab_t * s)
257 {
258 int i;
259 sidtab_ptr_t cur, temp;
260
261 if (!s || !s->htable)
262 return;
263
264 for (i = 0; i < SIDTAB_SIZE; i++) {
265 cur = s->htable[i];
266 while (cur != NULL) {
267 temp = cur;
268 cur = cur->next;
269 context_destroy(&temp->context);
270 free(temp);
271 }
272 s->htable[i] = NULL;
273 }
274 free(s->htable);
275 s->htable = NULL;
276 s->nel = 0;
277 s->next_sid = 1;
278 }
279
sepol_sidtab_set(sidtab_t * dst,sidtab_t * src)280 void sepol_sidtab_set(sidtab_t * dst, sidtab_t * src)
281 {
282 SIDTAB_LOCK(src);
283 dst->htable = src->htable;
284 dst->nel = src->nel;
285 dst->next_sid = src->next_sid;
286 dst->shutdown = 0;
287 SIDTAB_UNLOCK(src);
288 }
289
sepol_sidtab_shutdown(sidtab_t * s)290 void sepol_sidtab_shutdown(sidtab_t * s)
291 {
292 SIDTAB_LOCK(s);
293 s->shutdown = 1;
294 SIDTAB_UNLOCK(s);
295 }
296
297 /* FLASK */
298