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