1
2/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */
3
4/* FLASK */
5
6/*
7 * Implementation of the extensible bitmap type.
8 */
9
10#include <stdlib.h>
11
12#include <sepol/policydb/ebitmap.h>
13#include <sepol/policydb/policydb.h>
14
15#include "debug.h"
16#include "private.h"
17
18int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2)
19{
20	ebitmap_node_t *n1, *n2, *new, *prev;
21
22	ebitmap_init(dst);
23
24	n1 = e1->node;
25	n2 = e2->node;
26	prev = 0;
27	while (n1 || n2) {
28		new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
29		if (!new) {
30			ebitmap_destroy(dst);
31			return -ENOMEM;
32		}
33		memset(new, 0, sizeof(ebitmap_node_t));
34		if (n1 && n2 && n1->startbit == n2->startbit) {
35			new->startbit = n1->startbit;
36			new->map = n1->map | n2->map;
37			n1 = n1->next;
38			n2 = n2->next;
39		} else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
40			new->startbit = n1->startbit;
41			new->map = n1->map;
42			n1 = n1->next;
43		} else {
44			new->startbit = n2->startbit;
45			new->map = n2->map;
46			n2 = n2->next;
47		}
48
49		new->next = 0;
50		if (prev)
51			prev->next = new;
52		else
53			dst->node = new;
54		prev = new;
55	}
56
57	dst->highbit = (e1->highbit > e2->highbit) ? e1->highbit : e2->highbit;
58	return 0;
59}
60
61int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
62{
63	ebitmap_t tmp;
64
65	if (ebitmap_or(&tmp, dst, e1))
66		return -1;
67	ebitmap_destroy(dst);
68	dst->node = tmp.node;
69	dst->highbit = tmp.highbit;
70
71	return 0;
72}
73
74int ebitmap_and(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2)
75{
76	unsigned int i, length = min(ebitmap_length(e1), ebitmap_length(e2));
77	ebitmap_init(dst);
78	for (i=0; i < length; i++) {
79		if (ebitmap_get_bit(e1, i) && ebitmap_get_bit(e2, i)) {
80			int rc = ebitmap_set_bit(dst, i, 1);
81			if (rc < 0)
82				return rc;
83		}
84	}
85	return 0;
86}
87
88int ebitmap_xor(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2)
89{
90	unsigned int i, length = max(ebitmap_length(e1), ebitmap_length(e2));
91	ebitmap_init(dst);
92	for (i=0; i < length; i++) {
93		int val = ebitmap_get_bit(e1, i) ^ ebitmap_get_bit(e2, i);
94		int rc = ebitmap_set_bit(dst, i, val);
95		if (rc < 0)
96			return rc;
97	}
98	return 0;
99}
100
101int ebitmap_not(ebitmap_t *dst, ebitmap_t *e1, unsigned int maxbit)
102{
103	unsigned int i;
104	ebitmap_init(dst);
105	for (i=0; i < maxbit; i++) {
106		int val = ebitmap_get_bit(e1, i);
107		int rc = ebitmap_set_bit(dst, i, !val);
108		if (rc < 0)
109			return rc;
110	}
111	return 0;
112}
113
114int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int maxbit)
115{
116	ebitmap_t e3;
117	ebitmap_init(dst);
118	int rc = ebitmap_not(&e3, e2, maxbit);
119	if (rc < 0)
120		return rc;
121	rc = ebitmap_and(dst, e1, &e3);
122	ebitmap_destroy(&e3);
123	if (rc < 0)
124		return rc;
125	return 0;
126}
127
128unsigned int ebitmap_cardinality(ebitmap_t *e1)
129{
130	unsigned int i, count = 0;
131	for (i=ebitmap_startbit(e1); i < ebitmap_length(e1); i++)
132		if (ebitmap_get_bit(e1, i))
133			count++;
134	return count;
135}
136
137int ebitmap_hamming_distance(ebitmap_t * e1, ebitmap_t * e2)
138{
139	if (ebitmap_cmp(e1, e2))
140		return 0;
141	ebitmap_t tmp;
142	int rc = ebitmap_xor(&tmp, e1, e2);
143	if (rc < 0)
144		return -1;
145	int distance = ebitmap_cardinality(&tmp);
146	ebitmap_destroy(&tmp);
147	return distance;
148}
149
150int ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2)
151{
152	ebitmap_node_t *n1, *n2;
153
154	if (e1->highbit != e2->highbit)
155		return 0;
156
157	n1 = e1->node;
158	n2 = e2->node;
159	while (n1 && n2 &&
160	       (n1->startbit == n2->startbit) && (n1->map == n2->map)) {
161		n1 = n1->next;
162		n2 = n2->next;
163	}
164
165	if (n1 || n2)
166		return 0;
167
168	return 1;
169}
170
171int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
172{
173	ebitmap_node_t *n, *new, *prev;
174
175	ebitmap_init(dst);
176	n = src->node;
177	prev = 0;
178	while (n) {
179		new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
180		if (!new) {
181			ebitmap_destroy(dst);
182			return -ENOMEM;
183		}
184		memset(new, 0, sizeof(ebitmap_node_t));
185		new->startbit = n->startbit;
186		new->map = n->map;
187		new->next = 0;
188		if (prev)
189			prev->next = new;
190		else
191			dst->node = new;
192		prev = new;
193		n = n->next;
194	}
195
196	dst->highbit = src->highbit;
197	return 0;
198}
199
200int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2)
201{
202	ebitmap_node_t *n1, *n2;
203
204	if (e1->highbit < e2->highbit)
205		return 0;
206
207	n1 = e1->node;
208	n2 = e2->node;
209	while (n1 && n2 && (n1->startbit <= n2->startbit)) {
210		if (n1->startbit < n2->startbit) {
211			n1 = n1->next;
212			continue;
213		}
214		if ((n1->map & n2->map) != n2->map)
215			return 0;
216
217		n1 = n1->next;
218		n2 = n2->next;
219	}
220
221	if (n2)
222		return 0;
223
224	return 1;
225}
226
227int ebitmap_match_any(const ebitmap_t *e1, const ebitmap_t *e2)
228{
229	ebitmap_node_t *n1 = e1->node;
230	ebitmap_node_t *n2 = e2->node;
231
232	while (n1 && n2) {
233		if (n1->startbit < n2->startbit) {
234			n1 = n1->next;
235		} else if (n2->startbit < n1->startbit) {
236			n2 = n2->next;
237		} else {
238			if (n1->map & n2->map) {
239				return 1;
240			}
241			n1 = n1->next;
242			n2 = n2->next;
243		}
244	}
245
246	return 0;
247}
248
249int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit)
250{
251	ebitmap_node_t *n;
252
253	if (e->highbit < bit)
254		return 0;
255
256	n = e->node;
257	while (n && (n->startbit <= bit)) {
258		if ((n->startbit + MAPSIZE) > bit) {
259			if (n->map & (MAPBIT << (bit - n->startbit)))
260				return 1;
261			else
262				return 0;
263		}
264		n = n->next;
265	}
266
267	return 0;
268}
269
270int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
271{
272	ebitmap_node_t *n, *prev, *new;
273	uint32_t startbit = bit & ~(MAPSIZE - 1);
274	uint32_t highbit = startbit + MAPSIZE;
275
276	if (highbit == 0) {
277		ERR(NULL, "bitmap overflow, bit 0x%x", bit);
278		return -EINVAL;
279	}
280
281	prev = 0;
282	n = e->node;
283	while (n && n->startbit <= bit) {
284		if ((n->startbit + MAPSIZE) > bit) {
285			if (value) {
286				n->map |= (MAPBIT << (bit - n->startbit));
287			} else {
288				n->map &= ~(MAPBIT << (bit - n->startbit));
289				if (!n->map) {
290					/* drop this node from the bitmap */
291
292					if (!n->next) {
293						/*
294						 * this was the highest map
295						 * within the bitmap
296						 */
297						if (prev)
298							e->highbit =
299							    prev->startbit +
300							    MAPSIZE;
301						else
302							e->highbit = 0;
303					}
304					if (prev)
305						prev->next = n->next;
306					else
307						e->node = n->next;
308
309					free(n);
310				}
311			}
312			return 0;
313		}
314		prev = n;
315		n = n->next;
316	}
317
318	if (!value)
319		return 0;
320
321	new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
322	if (!new)
323		return -ENOMEM;
324	memset(new, 0, sizeof(ebitmap_node_t));
325
326	new->startbit = startbit;
327	new->map = (MAPBIT << (bit - new->startbit));
328
329	if (!n) {
330		/* this node will be the highest map within the bitmap */
331		e->highbit = highbit;
332	}
333
334	if (prev) {
335		new->next = prev->next;
336		prev->next = new;
337	} else {
338		new->next = e->node;
339		e->node = new;
340	}
341
342	return 0;
343}
344
345void ebitmap_destroy(ebitmap_t * e)
346{
347	ebitmap_node_t *n, *temp;
348
349	if (!e)
350		return;
351
352	n = e->node;
353	while (n) {
354		temp = n;
355		n = n->next;
356		free(temp);
357	}
358
359	e->highbit = 0;
360	e->node = 0;
361	return;
362}
363
364int ebitmap_read(ebitmap_t * e, void *fp)
365{
366	int rc;
367	ebitmap_node_t *n, *l;
368	uint32_t buf[3], mapsize, count, i;
369	uint64_t map;
370
371	ebitmap_init(e);
372
373	rc = next_entry(buf, fp, sizeof(uint32_t) * 3);
374	if (rc < 0)
375		goto bad;
376
377	mapsize = le32_to_cpu(buf[0]);
378	e->highbit = le32_to_cpu(buf[1]);
379	count = le32_to_cpu(buf[2]);
380
381	if (mapsize != MAPSIZE) {
382		printf
383		    ("security: ebitmap: map size %d does not match my size %zu (high bit was %d)\n",
384		     mapsize, MAPSIZE, e->highbit);
385		goto bad;
386	}
387	if (!e->highbit) {
388		e->node = NULL;
389		goto ok;
390	}
391	if (e->highbit & (MAPSIZE - 1)) {
392		printf
393		    ("security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)\n",
394		     e->highbit, MAPSIZE);
395		goto bad;
396	}
397
398	if (e->highbit && !count)
399		goto bad;
400
401	l = NULL;
402	for (i = 0; i < count; i++) {
403		rc = next_entry(buf, fp, sizeof(uint32_t));
404		if (rc < 0) {
405			printf("security: ebitmap: truncated map\n");
406			goto bad;
407		}
408		n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
409		if (!n) {
410			printf("security: ebitmap: out of memory\n");
411			rc = -ENOMEM;
412			goto bad;
413		}
414		memset(n, 0, sizeof(ebitmap_node_t));
415
416		n->startbit = le32_to_cpu(buf[0]);
417
418		if (n->startbit & (MAPSIZE - 1)) {
419			printf
420			    ("security: ebitmap start bit (%d) is not a multiple of the map size (%zu)\n",
421			     n->startbit, MAPSIZE);
422			goto bad_free;
423		}
424		if (n->startbit > (e->highbit - MAPSIZE)) {
425			printf
426			    ("security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)\n",
427			     n->startbit, (e->highbit - MAPSIZE));
428			goto bad_free;
429		}
430		rc = next_entry(&map, fp, sizeof(uint64_t));
431		if (rc < 0) {
432			printf("security: ebitmap: truncated map\n");
433			goto bad_free;
434		}
435		n->map = le64_to_cpu(map);
436
437		if (!n->map) {
438			printf
439			    ("security: ebitmap: null map in ebitmap (startbit %d)\n",
440			     n->startbit);
441			goto bad_free;
442		}
443		if (l) {
444			if (n->startbit <= l->startbit) {
445				printf
446				    ("security: ebitmap: start bit %d comes after start bit %d\n",
447				     n->startbit, l->startbit);
448				goto bad_free;
449			}
450			l->next = n;
451		} else
452			e->node = n;
453
454		l = n;
455	}
456	if (count && l->startbit + MAPSIZE != e->highbit) {
457		printf
458		    ("security: ebitmap: hight bit %u has not the expected value %zu\n",
459		     e->highbit, l->startbit + MAPSIZE);
460		goto bad;
461	}
462
463      ok:
464	rc = 0;
465      out:
466	return rc;
467      bad_free:
468	free(n);
469      bad:
470	if (!rc)
471		rc = -EINVAL;
472	ebitmap_destroy(e);
473	goto out;
474}
475
476/* FLASK */
477