ebitmap.c revision 255e72915d4cbddceb435e13d81601755714e9f3 
1
2/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
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_cmp(const ebitmap_t * e1, const ebitmap_t * e2)
75{
76	ebitmap_node_t *n1, *n2;
77
78	if (e1->highbit != e2->highbit)
79		return 0;
80
81	n1 = e1->node;
82	n2 = e2->node;
83	while (n1 && n2 &&
84	       (n1->startbit == n2->startbit) && (n1->map == n2->map)) {
85		n1 = n1->next;
86		n2 = n2->next;
87	}
88
89	if (n1 || n2)
90		return 0;
91
92	return 1;
93}
94
95int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
96{
97	ebitmap_node_t *n, *new, *prev;
98
99	ebitmap_init(dst);
100	n = src->node;
101	prev = 0;
102	while (n) {
103		new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
104		if (!new) {
105			ebitmap_destroy(dst);
106			return -ENOMEM;
107		}
108		memset(new, 0, sizeof(ebitmap_node_t));
109		new->startbit = n->startbit;
110		new->map = n->map;
111		new->next = 0;
112		if (prev)
113			prev->next = new;
114		else
115			dst->node = new;
116		prev = new;
117		n = n->next;
118	}
119
120	dst->highbit = src->highbit;
121	return 0;
122}
123
124int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2)
125{
126	ebitmap_node_t *n1, *n2;
127
128	if (e1->highbit < e2->highbit)
129		return 0;
130
131	n1 = e1->node;
132	n2 = e2->node;
133	while (n1 && n2 && (n1->startbit <= n2->startbit)) {
134		if (n1->startbit < n2->startbit) {
135			n1 = n1->next;
136			continue;
137		}
138		if ((n1->map & n2->map) != n2->map)
139			return 0;
140
141		n1 = n1->next;
142		n2 = n2->next;
143	}
144
145	if (n2)
146		return 0;
147
148	return 1;
149}
150
151int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit)
152{
153	ebitmap_node_t *n;
154
155	if (e->highbit < bit)
156		return 0;
157
158	n = e->node;
159	while (n && (n->startbit <= bit)) {
160		if ((n->startbit + MAPSIZE) > bit) {
161			if (n->map & (MAPBIT << (bit - n->startbit)))
162				return 1;
163			else
164				return 0;
165		}
166		n = n->next;
167	}
168
169	return 0;
170}
171
172int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
173{
174	ebitmap_node_t *n, *prev, *new;
175	uint32_t startbit = bit & ~(MAPSIZE - 1);
176	uint32_t highbit = startbit + MAPSIZE;
177
178	if (highbit == 0) {
179		ERR(NULL, "bitmap overflow, bit 0x%x", bit);
180		return -EINVAL;
181	}
182
183	prev = 0;
184	n = e->node;
185	while (n && n->startbit <= bit) {
186		if ((n->startbit + MAPSIZE) > bit) {
187			if (value) {
188				n->map |= (MAPBIT << (bit - n->startbit));
189			} else {
190				n->map &= ~(MAPBIT << (bit - n->startbit));
191				if (!n->map) {
192					/* drop this node from the bitmap */
193
194					if (!n->next) {
195						/*
196						 * this was the highest map
197						 * within the bitmap
198						 */
199						if (prev)
200							e->highbit =
201							    prev->startbit +
202							    MAPSIZE;
203						else
204							e->highbit = 0;
205					}
206					if (prev)
207						prev->next = n->next;
208					else
209						e->node = n->next;
210
211					free(n);
212				}
213			}
214			return 0;
215		}
216		prev = n;
217		n = n->next;
218	}
219
220	if (!value)
221		return 0;
222
223	new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
224	if (!new)
225		return -ENOMEM;
226	memset(new, 0, sizeof(ebitmap_node_t));
227
228	new->startbit = startbit;
229	new->map = (MAPBIT << (bit - new->startbit));
230
231	if (!n) {
232		/* this node will be the highest map within the bitmap */
233		e->highbit = highbit;
234	}
235
236	if (prev) {
237		new->next = prev->next;
238		prev->next = new;
239	} else {
240		new->next = e->node;
241		e->node = new;
242	}
243
244	return 0;
245}
246
247void ebitmap_destroy(ebitmap_t * e)
248{
249	ebitmap_node_t *n, *temp;
250
251	if (!e)
252		return;
253
254	n = e->node;
255	while (n) {
256		temp = n;
257		n = n->next;
258		free(temp);
259	}
260
261	e->highbit = 0;
262	e->node = 0;
263	return;
264}
265
266int ebitmap_read(ebitmap_t * e, void *fp)
267{
268	int rc;
269	ebitmap_node_t *n, *l;
270	uint32_t buf[3], mapsize, count, i;
271	uint64_t map;
272
273	ebitmap_init(e);
274
275	rc = next_entry(buf, fp, sizeof(uint32_t) * 3);
276	if (rc < 0)
277		goto bad;
278
279	mapsize = le32_to_cpu(buf[0]);
280	e->highbit = le32_to_cpu(buf[1]);
281	count = le32_to_cpu(buf[2]);
282
283	if (mapsize != MAPSIZE) {
284		printf
285		    ("security: ebitmap: map size %d does not match my size %zu (high bit was %d)\n",
286		     mapsize, MAPSIZE, e->highbit);
287		goto bad;
288	}
289	if (!e->highbit) {
290		e->node = NULL;
291		goto ok;
292	}
293	if (e->highbit & (MAPSIZE - 1)) {
294		printf
295		    ("security: ebitmap: high bit (%d) is not a multiple of the map size (%zu)\n",
296		     e->highbit, MAPSIZE);
297		goto bad;
298	}
299	l = NULL;
300	for (i = 0; i < count; i++) {
301		rc = next_entry(buf, fp, sizeof(uint32_t));
302		if (rc < 0) {
303			printf("security: ebitmap: truncated map\n");
304			goto bad;
305		}
306		n = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
307		if (!n) {
308			printf("security: ebitmap: out of memory\n");
309			rc = -ENOMEM;
310			goto bad;
311		}
312		memset(n, 0, sizeof(ebitmap_node_t));
313
314		n->startbit = le32_to_cpu(buf[0]);
315
316		if (n->startbit & (MAPSIZE - 1)) {
317			printf
318			    ("security: ebitmap start bit (%d) is not a multiple of the map size (%zu)\n",
319			     n->startbit, MAPSIZE);
320			goto bad_free;
321		}
322		if (n->startbit > (e->highbit - MAPSIZE)) {
323			printf
324			    ("security: ebitmap start bit (%d) is beyond the end of the bitmap (%zu)\n",
325			     n->startbit, (e->highbit - MAPSIZE));
326			goto bad_free;
327		}
328		rc = next_entry(&map, fp, sizeof(uint64_t));
329		if (rc < 0) {
330			printf("security: ebitmap: truncated map\n");
331			goto bad_free;
332		}
333		n->map = le64_to_cpu(map);
334
335		if (!n->map) {
336			printf
337			    ("security: ebitmap: null map in ebitmap (startbit %d)\n",
338			     n->startbit);
339			goto bad_free;
340		}
341		if (l) {
342			if (n->startbit <= l->startbit) {
343				printf
344				    ("security: ebitmap: start bit %d comes after start bit %d\n",
345				     n->startbit, l->startbit);
346				goto bad_free;
347			}
348			l->next = n;
349		} else
350			e->node = n;
351
352		l = n;
353	}
354
355      ok:
356	rc = 0;
357      out:
358	return rc;
359      bad_free:
360	free(n);
361      bad:
362	if (!rc)
363		rc = -EINVAL;
364	ebitmap_destroy(e);
365	goto out;
366}
367
368/* FLASK */
369