Home | History | Annotate | Download | only in src
      1 
      2 /* Author : Stephen Smalley, <sds (at) epoch.ncsc.mil> */
      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 
     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 
     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 
     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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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