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 <sepol/policydb/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_remove(sidtab_t * s,sepol_security_id_t sid)87 int sepol_sidtab_remove(sidtab_t * s, sepol_security_id_t sid)
88 {
89 int hvalue;
90 sidtab_node_t *cur, *last;
91
92 if (!s || !s->htable)
93 return -ENOENT;
94
95 hvalue = SIDTAB_HASH(sid);
96 last = NULL;
97 cur = s->htable[hvalue];
98 while (cur != NULL && sid > cur->sid) {
99 last = cur;
100 cur = cur->next;
101 }
102
103 if (cur == NULL || sid != cur->sid)
104 return -ENOENT;
105
106 if (last == NULL)
107 s->htable[hvalue] = cur->next;
108 else
109 last->next = cur->next;
110
111 context_destroy(&cur->context);
112
113 free(cur);
114 s->nel--;
115 return 0;
116 }
117
sepol_sidtab_search(sidtab_t * s,sepol_security_id_t sid)118 context_struct_t *sepol_sidtab_search(sidtab_t * s, sepol_security_id_t sid)
119 {
120 int hvalue;
121 sidtab_node_t *cur;
122
123 if (!s || !s->htable)
124 return NULL;
125
126 hvalue = SIDTAB_HASH(sid);
127 cur = s->htable[hvalue];
128 while (cur != NULL && sid > cur->sid)
129 cur = cur->next;
130
131 if (cur == NULL || sid != cur->sid) {
132 /* Remap invalid SIDs to the unlabeled SID. */
133 sid = SECINITSID_UNLABELED;
134 hvalue = SIDTAB_HASH(sid);
135 cur = s->htable[hvalue];
136 while (cur != NULL && sid > cur->sid)
137 cur = cur->next;
138 if (!cur || sid != cur->sid)
139 return NULL;
140 }
141
142 return &cur->context;
143 }
144
sepol_sidtab_map(sidtab_t * s,int (* apply)(sepol_security_id_t sid,context_struct_t * context,void * args),void * args)145 int sepol_sidtab_map(sidtab_t * s,
146 int (*apply) (sepol_security_id_t sid,
147 context_struct_t * context,
148 void *args), void *args)
149 {
150 int i, ret;
151 sidtab_node_t *cur;
152
153 if (!s || !s->htable)
154 return 0;
155
156 for (i = 0; i < SIDTAB_SIZE; i++) {
157 cur = s->htable[i];
158 while (cur != NULL) {
159 ret = apply(cur->sid, &cur->context, args);
160 if (ret)
161 return ret;
162 cur = cur->next;
163 }
164 }
165 return 0;
166 }
167
sepol_sidtab_map_remove_on_error(sidtab_t * s,int (* apply)(sepol_security_id_t sid,context_struct_t * context,void * args),void * args)168 void sepol_sidtab_map_remove_on_error(sidtab_t * s,
169 int (*apply) (sepol_security_id_t sid,
170 context_struct_t * context,
171 void *args), void *args)
172 {
173 int i, ret;
174 sidtab_node_t *last, *cur, *temp;
175
176 if (!s || !s->htable)
177 return;
178
179 for (i = 0; i < SIDTAB_SIZE; i++) {
180 last = NULL;
181 cur = s->htable[i];
182 while (cur != NULL) {
183 ret = apply(cur->sid, &cur->context, args);
184 if (ret) {
185 if (last) {
186 last->next = cur->next;
187 } else {
188 s->htable[i] = cur->next;
189 }
190
191 temp = cur;
192 cur = cur->next;
193 context_destroy(&temp->context);
194 free(temp);
195 s->nel--;
196 } else {
197 last = cur;
198 cur = cur->next;
199 }
200 }
201 }
202
203 return;
204 }
205
sepol_sidtab_search_context(sidtab_t * s,context_struct_t * context)206 static inline sepol_security_id_t sepol_sidtab_search_context(sidtab_t * s,
207 context_struct_t *
208 context)
209 {
210 int i;
211 sidtab_node_t *cur;
212
213 for (i = 0; i < SIDTAB_SIZE; i++) {
214 cur = s->htable[i];
215 while (cur != NULL) {
216 if (context_cmp(&cur->context, context))
217 return cur->sid;
218 cur = cur->next;
219 }
220 }
221 return 0;
222 }
223
sepol_sidtab_context_to_sid(sidtab_t * s,context_struct_t * context,sepol_security_id_t * out_sid)224 int sepol_sidtab_context_to_sid(sidtab_t * s,
225 context_struct_t * context,
226 sepol_security_id_t * out_sid)
227 {
228 sepol_security_id_t sid;
229 int ret = 0;
230
231 *out_sid = SEPOL_SECSID_NULL;
232
233 sid = sepol_sidtab_search_context(s, context);
234 if (!sid) {
235 SIDTAB_LOCK(s);
236 /* Rescan now that we hold the lock. */
237 sid = sepol_sidtab_search_context(s, context);
238 if (sid)
239 goto unlock_out;
240 /* No SID exists for the context. Allocate a new one. */
241 if (s->next_sid == UINT_MAX || s->shutdown) {
242 ret = -ENOMEM;
243 goto unlock_out;
244 }
245 sid = s->next_sid++;
246 ret = sepol_sidtab_insert(s, sid, context);
247 if (ret)
248 s->next_sid--;
249 unlock_out:
250 SIDTAB_UNLOCK(s);
251 }
252
253 if (ret)
254 return ret;
255
256 *out_sid = sid;
257 return 0;
258 }
259
sepol_sidtab_hash_eval(sidtab_t * h,char * tag)260 void sepol_sidtab_hash_eval(sidtab_t * h, char *tag)
261 {
262 int i, chain_len, slots_used, max_chain_len;
263 sidtab_node_t *cur;
264
265 slots_used = 0;
266 max_chain_len = 0;
267 for (i = 0; i < SIDTAB_SIZE; i++) {
268 cur = h->htable[i];
269 if (cur) {
270 slots_used++;
271 chain_len = 0;
272 while (cur) {
273 chain_len++;
274 cur = cur->next;
275 }
276
277 if (chain_len > max_chain_len)
278 max_chain_len = chain_len;
279 }
280 }
281
282 printf
283 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n",
284 tag, h->nel, slots_used, SIDTAB_SIZE, max_chain_len);
285 }
286
sepol_sidtab_destroy(sidtab_t * s)287 void sepol_sidtab_destroy(sidtab_t * s)
288 {
289 int i;
290 sidtab_ptr_t cur, temp;
291
292 if (!s || !s->htable)
293 return;
294
295 for (i = 0; i < SIDTAB_SIZE; i++) {
296 cur = s->htable[i];
297 while (cur != NULL) {
298 temp = cur;
299 cur = cur->next;
300 context_destroy(&temp->context);
301 free(temp);
302 }
303 s->htable[i] = NULL;
304 }
305 free(s->htable);
306 s->htable = NULL;
307 s->nel = 0;
308 s->next_sid = 1;
309 }
310
sepol_sidtab_set(sidtab_t * dst,sidtab_t * src)311 void sepol_sidtab_set(sidtab_t * dst, sidtab_t * src)
312 {
313 SIDTAB_LOCK(src);
314 dst->htable = src->htable;
315 dst->nel = src->nel;
316 dst->next_sid = src->next_sid;
317 dst->shutdown = 0;
318 SIDTAB_UNLOCK(src);
319 }
320
sepol_sidtab_shutdown(sidtab_t * s)321 void sepol_sidtab_shutdown(sidtab_t * s)
322 {
323 SIDTAB_LOCK(s);
324 s->shutdown = 1;
325 SIDTAB_UNLOCK(s);
326 }
327
328 /* FLASK */
329