2 * Implementation of the extensible bitmap type.
4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
7 * Updated: Hewlett-Packard <paul.moore@hp.com>
9 * Added ebitmap_export() and ebitmap_import()
11 * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
14 #include <linux/kernel.h>
15 #include <linux/slab.h>
16 #include <linux/errno.h>
20 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
22 struct ebitmap_node *n1, *n2;
24 if (e1->highbit != e2->highbit)
30 (n1->startbit == n2->startbit) &&
31 (n1->map == n2->map)) {
42 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
44 struct ebitmap_node *n, *new, *prev;
50 new = kzalloc(sizeof(*new), GFP_ATOMIC);
55 new->startbit = n->startbit;
66 dst->highbit = src->highbit;
71 * ebitmap_export - Export an ebitmap to a unsigned char bitmap string
72 * @src: the ebitmap to export
73 * @dst: the resulting bitmap string
74 * @dst_len: length of dst in bytes
77 * Allocate a buffer at least src->highbit bits long and export the extensible
78 * bitmap into the buffer. The bitmap string will be in little endian format,
79 * i.e. LSB first. The value returned in dst_len may not the true size of the
80 * buffer as the length of the buffer is rounded up to a multiple of MAPTYPE.
81 * The caller must free the buffer when finished. Returns zero on success,
82 * negative values on failure.
85 int ebitmap_export(const struct ebitmap *src,
90 unsigned char *bitmap;
91 struct ebitmap_node *iter_node;
94 unsigned char bitmask;
96 if (src->highbit == 0) {
102 bitmap_len = src->highbit / 8;
103 if (src->highbit % 7)
106 bitmap = kzalloc((bitmap_len & ~(sizeof(MAPTYPE) - 1)) +
112 iter_node = src->node;
114 bitmap_byte = iter_node->startbit / 8;
116 node_val = iter_node->map;
122 if (node_val & (MAPTYPE)0x01)
123 bitmap[bitmap_byte] |= bitmask;
126 } while (node_val > 0);
127 iter_node = iter_node->next;
131 *dst_len = bitmap_len;
136 * ebitmap_import - Import an unsigned char bitmap string into an ebitmap
137 * @src: the bitmap string
138 * @src_len: the bitmap length in bytes
139 * @dst: the empty ebitmap
142 * This function takes a little endian bitmap string in src and imports it into
143 * the ebitmap pointed to by dst. Returns zero on success, negative values on
147 int ebitmap_import(const unsigned char *src,
153 struct ebitmap_node *node_new;
154 struct ebitmap_node *node_last = NULL;
157 unsigned char src_byte;
159 while (src_off < src_len) {
160 if (src_len - src_off >= sizeof(MAPTYPE)) {
161 if (*(MAPTYPE *)&src[src_off] == 0) {
162 src_off += sizeof(MAPTYPE);
165 node_limit = sizeof(MAPTYPE);
167 for (src_byte = 0, i_byte = src_off;
168 i_byte < src_len && src_byte == 0;
170 src_byte |= src[i_byte];
173 node_limit = src_len - src_off;
176 node_new = kzalloc(sizeof(*node_new), GFP_ATOMIC);
177 if (unlikely(node_new == NULL)) {
178 ebitmap_destroy(dst);
181 node_new->startbit = src_off * 8;
182 for (i_byte = 0; i_byte < node_limit; i_byte++) {
183 src_byte = src[src_off++];
184 for (i_bit = i_byte * 8; src_byte != 0; i_bit++) {
186 node_new->map |= MAPBIT << i_bit;
191 if (node_last != NULL)
192 node_last->next = node_new;
194 dst->node = node_new;
195 node_last = node_new;
198 if (likely(node_last != NULL))
199 dst->highbit = node_last->startbit + MAPSIZE;
206 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
208 struct ebitmap_node *n1, *n2;
210 if (e1->highbit < e2->highbit)
215 while (n1 && n2 && (n1->startbit <= n2->startbit)) {
216 if (n1->startbit < n2->startbit) {
220 if ((n1->map & n2->map) != n2->map)
233 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
235 struct ebitmap_node *n;
237 if (e->highbit < bit)
241 while (n && (n->startbit <= bit)) {
242 if ((n->startbit + MAPSIZE) > bit) {
243 if (n->map & (MAPBIT << (bit - n->startbit)))
254 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
256 struct ebitmap_node *n, *prev, *new;
260 while (n && n->startbit <= bit) {
261 if ((n->startbit + MAPSIZE) > bit) {
263 n->map |= (MAPBIT << (bit - n->startbit));
265 n->map &= ~(MAPBIT << (bit - n->startbit));
267 /* drop this node from the bitmap */
271 * this was the highest map
275 e->highbit = prev->startbit + MAPSIZE;
280 prev->next = n->next;
296 new = kzalloc(sizeof(*new), GFP_ATOMIC);
300 new->startbit = bit & ~(MAPSIZE - 1);
301 new->map = (MAPBIT << (bit - new->startbit));
304 /* this node will be the highest map within the bitmap */
305 e->highbit = new->startbit + MAPSIZE;
308 new->next = prev->next;
318 void ebitmap_destroy(struct ebitmap *e)
320 struct ebitmap_node *n, *temp;
337 int ebitmap_read(struct ebitmap *e, void *fp)
340 struct ebitmap_node *n, *l;
342 u32 mapsize, count, i;
347 rc = next_entry(buf, fp, sizeof buf);
351 mapsize = le32_to_cpu(buf[0]);
352 e->highbit = le32_to_cpu(buf[1]);
353 count = le32_to_cpu(buf[2]);
355 if (mapsize != MAPSIZE) {
356 printk(KERN_ERR "security: ebitmap: map size %u does not "
357 "match my size %Zd (high bit was %d)\n", mapsize,
358 MAPSIZE, e->highbit);
365 if (e->highbit & (MAPSIZE - 1)) {
366 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
367 "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
371 for (i = 0; i < count; i++) {
372 rc = next_entry(buf, fp, sizeof(u32));
374 printk(KERN_ERR "security: ebitmap: truncated map\n");
377 n = kzalloc(sizeof(*n), GFP_KERNEL);
379 printk(KERN_ERR "security: ebitmap: out of memory\n");
384 n->startbit = le32_to_cpu(buf[0]);
386 if (n->startbit & (MAPSIZE - 1)) {
387 printk(KERN_ERR "security: ebitmap start bit (%d) is "
388 "not a multiple of the map size (%Zd)\n",
389 n->startbit, MAPSIZE);
392 if (n->startbit > (e->highbit - MAPSIZE)) {
393 printk(KERN_ERR "security: ebitmap start bit (%d) is "
394 "beyond the end of the bitmap (%Zd)\n",
395 n->startbit, (e->highbit - MAPSIZE));
398 rc = next_entry(&map, fp, sizeof(u64));
400 printk(KERN_ERR "security: ebitmap: truncated map\n");
403 n->map = le64_to_cpu(map);
406 printk(KERN_ERR "security: ebitmap: null map in "
407 "ebitmap (startbit %d)\n", n->startbit);
411 if (n->startbit <= l->startbit) {
412 printk(KERN_ERR "security: ebitmap: start "
413 "bit %d comes after start bit %d\n",
414 n->startbit, l->startbit);