2 * Implementation of the extensible bitmap type.
4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
6 #include <linux/kernel.h>
7 #include <linux/slab.h>
8 #include <linux/errno.h>
12 int ebitmap_or(struct ebitmap *dst, struct ebitmap *e1, struct ebitmap *e2)
14 struct ebitmap_node *n1, *n2, *new, *prev;
22 new = kmalloc(sizeof(*new), GFP_ATOMIC);
27 memset(new, 0, sizeof(*new));
28 if (n1 && n2 && n1->startbit == n2->startbit) {
29 new->startbit = n1->startbit;
30 new->map = n1->map | n2->map;
33 } else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
34 new->startbit = n1->startbit;
38 new->startbit = n2->startbit;
51 dst->highbit = (e1->highbit > e2->highbit) ? e1->highbit : e2->highbit;
55 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
57 struct ebitmap_node *n1, *n2;
59 if (e1->highbit != e2->highbit)
65 (n1->startbit == n2->startbit) &&
66 (n1->map == n2->map)) {
77 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
79 struct ebitmap_node *n, *new, *prev;
85 new = kmalloc(sizeof(*new), GFP_ATOMIC);
90 memset(new, 0, sizeof(*new));
91 new->startbit = n->startbit;
102 dst->highbit = src->highbit;
106 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
108 struct ebitmap_node *n1, *n2;
110 if (e1->highbit < e2->highbit)
115 while (n1 && n2 && (n1->startbit <= n2->startbit)) {
116 if (n1->startbit < n2->startbit) {
120 if ((n1->map & n2->map) != n2->map)
133 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
135 struct ebitmap_node *n;
137 if (e->highbit < bit)
141 while (n && (n->startbit <= bit)) {
142 if ((n->startbit + MAPSIZE) > bit) {
143 if (n->map & (MAPBIT << (bit - n->startbit)))
154 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
156 struct ebitmap_node *n, *prev, *new;
160 while (n && n->startbit <= bit) {
161 if ((n->startbit + MAPSIZE) > bit) {
163 n->map |= (MAPBIT << (bit - n->startbit));
165 n->map &= ~(MAPBIT << (bit - n->startbit));
167 /* drop this node from the bitmap */
171 * this was the highest map
175 e->highbit = prev->startbit + MAPSIZE;
180 prev->next = n->next;
196 new = kmalloc(sizeof(*new), GFP_ATOMIC);
199 memset(new, 0, sizeof(*new));
201 new->startbit = bit & ~(MAPSIZE - 1);
202 new->map = (MAPBIT << (bit - new->startbit));
205 /* this node will be the highest map within the bitmap */
206 e->highbit = new->startbit + MAPSIZE;
209 new->next = prev->next;
219 void ebitmap_destroy(struct ebitmap *e)
221 struct ebitmap_node *n, *temp;
238 int ebitmap_read(struct ebitmap *e, void *fp)
241 struct ebitmap_node *n, *l;
242 u32 *buf, mapsize, count, i;
247 buf = next_entry(fp, sizeof(u32)*3);
251 mapsize = le32_to_cpu(buf[0]);
252 e->highbit = le32_to_cpu(buf[1]);
253 count = le32_to_cpu(buf[2]);
255 if (mapsize != MAPSIZE) {
256 printk(KERN_ERR "security: ebitmap: map size %u does not "
257 "match my size %Zd (high bit was %d)\n", mapsize,
258 MAPSIZE, e->highbit);
265 if (e->highbit & (MAPSIZE - 1)) {
266 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
267 "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
271 for (i = 0; i < count; i++) {
272 buf = next_entry(fp, sizeof(u32));
274 printk(KERN_ERR "security: ebitmap: truncated map\n");
277 n = kmalloc(sizeof(*n), GFP_KERNEL);
279 printk(KERN_ERR "security: ebitmap: out of memory\n");
283 memset(n, 0, sizeof(*n));
285 n->startbit = le32_to_cpu(buf[0]);
287 if (n->startbit & (MAPSIZE - 1)) {
288 printk(KERN_ERR "security: ebitmap start bit (%d) is "
289 "not a multiple of the map size (%Zd)\n",
290 n->startbit, MAPSIZE);
293 if (n->startbit > (e->highbit - MAPSIZE)) {
294 printk(KERN_ERR "security: ebitmap start bit (%d) is "
295 "beyond the end of the bitmap (%Zd)\n",
296 n->startbit, (e->highbit - MAPSIZE));
299 buf = next_entry(fp, sizeof(u64));
301 printk(KERN_ERR "security: ebitmap: truncated map\n");
304 memcpy(&map, buf, sizeof(u64));
305 n->map = le64_to_cpu(map);
308 printk(KERN_ERR "security: ebitmap: null map in "
309 "ebitmap (startbit %d)\n", n->startbit);
313 if (n->startbit <= l->startbit) {
314 printk(KERN_ERR "security: ebitmap: start "
315 "bit %d comes after start bit %d\n",
316 n->startbit, l->startbit);