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