1 /*
2 * Implementation of the extensible bitmap type.
3 *
4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
5 */
6 /*
7 * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com>
8 * Applied standard bit operations to improve bitmap scanning.
9 */
10
11 /* Ported to Xen 3.0, George Coker, <gscoker@alpha.ncsc.mil> */
12
13 #include <xen/bitmap.h>
14 #include <xen/byteorder.h>
15 #include <xen/errno.h>
16 #include <xen/lib.h>
17 #include <xen/spinlock.h>
18 #include <xen/xmalloc.h>
19
20 #include "ebitmap.h"
21 #include "policydb.h"
22
ebitmap_cmp(struct ebitmap * e1,struct ebitmap * e2)23 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
24 {
25 struct ebitmap_node *n1, *n2;
26
27 if ( e1->highbit != e2->highbit )
28 return 0;
29
30 n1 = e1->node;
31 n2 = e2->node;
32 while ( n1 && n2 && (n1->startbit == n2->startbit) &&
33 !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8))
34 {
35 n1 = n1->next;
36 n2 = n2->next;
37 }
38
39 if ( n1 || n2 )
40 return 0;
41
42 return 1;
43 }
44
ebitmap_cpy(struct ebitmap * dst,struct ebitmap * src)45 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
46 {
47 struct ebitmap_node *n, *new, *prev;
48
49 ebitmap_init(dst);
50 n = src->node;
51 prev = NULL;
52 while ( n )
53 {
54 new = xzalloc(struct ebitmap_node);
55 if ( !new )
56 {
57 ebitmap_destroy(dst);
58 return -ENOMEM;
59 }
60 new->startbit = n->startbit;
61 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
62 new->next = NULL;
63 if ( prev )
64 prev->next = new;
65 else
66 dst->node = new;
67 prev = new;
68 n = n->next;
69 }
70
71 dst->highbit = src->highbit;
72 return 0;
73 }
74
ebitmap_contains(struct ebitmap * e1,struct ebitmap * e2)75 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
76 {
77 struct ebitmap_node *n1, *n2;
78 int i;
79
80 if ( e1->highbit < e2->highbit )
81 return 0;
82
83 n1 = e1->node;
84 n2 = e2->node;
85 while ( n1 && n2 && (n1->startbit <= n2->startbit) )
86 {
87 if ( n1->startbit < n2->startbit )
88 {
89 n1 = n1->next;
90 continue;
91 }
92 for ( i = 0; i < EBITMAP_UNIT_NUMS; i++ )
93 {
94 if ( (n1->maps[i] & n2->maps[i]) != n2->maps[i] )
95 return 0;
96 }
97
98 n1 = n1->next;
99 n2 = n2->next;
100 }
101
102 if ( n2 )
103 return 0;
104
105 return 1;
106 }
107
ebitmap_get_bit(struct ebitmap * e,unsigned long bit)108 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
109 {
110 struct ebitmap_node *n;
111
112 if ( e->highbit < bit )
113 return 0;
114
115 n = e->node;
116 while ( n && (n->startbit <= bit) )
117 {
118 if ( (n->startbit + EBITMAP_SIZE) > bit )
119 return ebitmap_node_get_bit(n, bit);
120 n = n->next;
121 }
122
123 return 0;
124 }
125
ebitmap_set_bit(struct ebitmap * e,unsigned long bit,int value)126 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
127 {
128 struct ebitmap_node *n, *prev, *new;
129
130 prev = NULL;
131 n = e->node;
132 while ( n && n->startbit <= bit )
133 {
134 if ( (n->startbit + EBITMAP_SIZE) > bit )
135 {
136 if ( value )
137 {
138 ebitmap_node_set_bit(n, bit);
139 }
140 else
141 {
142 unsigned int s;
143
144 ebitmap_node_clr_bit(n, bit);
145
146 s = find_first_bit(n->maps, EBITMAP_SIZE);
147 if ( s < EBITMAP_SIZE )
148 return 0;
149
150 /* drop this node from the bitmap */
151
152 if ( !n->next )
153 {
154 /*
155 * this was the highest map
156 * within the bitmap
157 */
158 if ( prev )
159 e->highbit = prev->startbit + EBITMAP_SIZE;
160 else
161 e->highbit = 0;
162 }
163 if ( prev )
164 prev->next = n->next;
165 else
166 e->node = n->next;
167
168 xfree(n);
169 }
170 return 0;
171 }
172 prev = n;
173 n = n->next;
174 }
175
176 if ( !value )
177 return 0;
178
179 new = xzalloc(struct ebitmap_node);
180 if ( !new )
181 return -ENOMEM;
182
183 new->startbit = bit - (bit % EBITMAP_SIZE);
184 ebitmap_node_set_bit(new, bit);
185
186 if ( !n )
187 /* this node will be the highest map within the bitmap */
188 e->highbit = new->startbit + EBITMAP_SIZE;
189
190 if ( prev )
191 {
192 new->next = prev->next;
193 prev->next = new;
194 }
195 else
196 {
197 new->next = e->node;
198 e->node = new;
199 }
200
201 return 0;
202 }
203
ebitmap_destroy(struct ebitmap * e)204 void ebitmap_destroy(struct ebitmap *e)
205 {
206 struct ebitmap_node *n, *temp;
207
208 if ( !e )
209 return;
210
211 n = e->node;
212 while ( n )
213 {
214 temp = n;
215 n = n->next;
216 xfree(temp);
217 }
218
219 e->highbit = 0;
220 e->node = NULL;
221 return;
222 }
223
ebitmap_read(struct ebitmap * e,void * fp)224 int ebitmap_read(struct ebitmap *e, void *fp)
225 {
226 struct ebitmap_node *n = NULL;
227 u32 mapunit, count, startbit, index;
228 u64 map;
229 __le32 buf[3];
230 int rc, i;
231
232 ebitmap_init(e);
233
234 rc = next_entry(buf, fp, sizeof buf);
235 if ( rc < 0 )
236 goto out;
237
238 mapunit = le32_to_cpu(buf[0]);
239 e->highbit = le32_to_cpu(buf[1]);
240 count = le32_to_cpu(buf[2]);
241
242 if ( mapunit != sizeof(u64) * 8 )
243 {
244 printk(KERN_ERR "Flask: ebitmap: map size %u does not "
245 "match my size %zd (high bit was %d)\n", mapunit,
246 sizeof(u64) * 8, e->highbit);
247 goto bad;
248 }
249
250 /* round up e->highbit */
251 e->highbit += EBITMAP_SIZE - 1;
252 e->highbit -= (e->highbit % EBITMAP_SIZE);
253
254 if ( !e->highbit )
255 {
256 e->node = NULL;
257 goto ok;
258 }
259
260 for ( i = 0; i < count; i++ )
261 {
262 rc = next_entry(&startbit, fp, sizeof(u32));
263 if ( rc < 0 )
264 {
265 printk(KERN_ERR "Flask: ebitmap: truncated map\n");
266 goto bad;
267 }
268 startbit = le32_to_cpu(startbit);
269 if ( startbit & (mapunit - 1) )
270 {
271 printk(KERN_ERR "Flask: ebitmap start bit (%d) is "
272 "not a multiple of the map unit size (%u)\n",
273 startbit, mapunit);
274 goto bad;
275 }
276 if ( startbit > e->highbit - mapunit )
277 {
278 printk(KERN_ERR "Flask: ebitmap start bit (%d) is "
279 "beyond the end of the bitmap (%u)\n",
280 startbit, (e->highbit - mapunit));
281 goto bad;
282 }
283
284 if ( !n || startbit >= n->startbit + EBITMAP_SIZE )
285 {
286 struct ebitmap_node *tmp = xzalloc(struct ebitmap_node);
287
288 if ( !tmp )
289 {
290 printk(KERN_ERR
291 "Flask: ebitmap: out of memory\n");
292 rc = -ENOMEM;
293 goto bad;
294 }
295 /* round down */
296 tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
297 if ( n )
298 n->next = tmp;
299 else
300 e->node = tmp;
301 n = tmp;
302 }
303 else if ( startbit <= n->startbit )
304 {
305 printk(KERN_ERR "Flask: ebitmap: start bit %d"
306 " comes after start bit %d\n",
307 startbit, n->startbit);
308 goto bad;
309 }
310
311 rc = next_entry(&map, fp, sizeof(u64));
312 if ( rc < 0 )
313 {
314 printk(KERN_ERR "Flask: ebitmap: truncated map\n");
315 goto bad;
316 }
317 map = le64_to_cpu(map);
318
319 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
320 while ( map )
321 {
322 n->maps[index++] = map & (-1UL);
323 map = EBITMAP_SHIFT_UNIT_SIZE(map);
324 }
325 }
326 ok:
327 rc = 0;
328 out:
329 return rc;
330 bad:
331 if ( !rc )
332 rc = -EINVAL;
333 ebitmap_destroy(e);
334 goto out;
335 }
336