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