From 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 16 Apr 2005 15:20:36 -0700 Subject: Linux-2.6.12-rc2 Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip! --- security/selinux/ss/ebitmap.c | 293 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 293 insertions(+) create mode 100644 security/selinux/ss/ebitmap.c (limited to 'security/selinux/ss/ebitmap.c') diff --git a/security/selinux/ss/ebitmap.c b/security/selinux/ss/ebitmap.c new file mode 100644 index 000000000000..d8ce9cc0b9f1 --- /dev/null +++ b/security/selinux/ss/ebitmap.c @@ -0,0 +1,293 @@ +/* + * Implementation of the extensible bitmap type. + * + * Author : Stephen Smalley, + */ +#include +#include +#include +#include "ebitmap.h" +#include "policydb.h" + +int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2) +{ + struct ebitmap_node *n1, *n2; + + if (e1->highbit != e2->highbit) + return 0; + + n1 = e1->node; + n2 = e2->node; + while (n1 && n2 && + (n1->startbit == n2->startbit) && + (n1->map == n2->map)) { + n1 = n1->next; + n2 = n2->next; + } + + if (n1 || n2) + return 0; + + return 1; +} + +int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src) +{ + struct ebitmap_node *n, *new, *prev; + + ebitmap_init(dst); + n = src->node; + prev = NULL; + while (n) { + new = kmalloc(sizeof(*new), GFP_ATOMIC); + if (!new) { + ebitmap_destroy(dst); + return -ENOMEM; + } + memset(new, 0, sizeof(*new)); + new->startbit = n->startbit; + new->map = n->map; + new->next = NULL; + if (prev) + prev->next = new; + else + dst->node = new; + prev = new; + n = n->next; + } + + dst->highbit = src->highbit; + return 0; +} + +int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2) +{ + struct ebitmap_node *n1, *n2; + + if (e1->highbit < e2->highbit) + return 0; + + n1 = e1->node; + n2 = e2->node; + while (n1 && n2 && (n1->startbit <= n2->startbit)) { + if (n1->startbit < n2->startbit) { + n1 = n1->next; + continue; + } + if ((n1->map & n2->map) != n2->map) + return 0; + + n1 = n1->next; + n2 = n2->next; + } + + if (n2) + return 0; + + return 1; +} + +int ebitmap_get_bit(struct ebitmap *e, unsigned long bit) +{ + struct ebitmap_node *n; + + if (e->highbit < bit) + return 0; + + n = e->node; + while (n && (n->startbit <= bit)) { + if ((n->startbit + MAPSIZE) > bit) { + if (n->map & (MAPBIT << (bit - n->startbit))) + return 1; + else + return 0; + } + n = n->next; + } + + return 0; +} + +int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) +{ + struct ebitmap_node *n, *prev, *new; + + prev = NULL; + n = e->node; + while (n && n->startbit <= bit) { + if ((n->startbit + MAPSIZE) > bit) { + if (value) { + n->map |= (MAPBIT << (bit - n->startbit)); + } else { + n->map &= ~(MAPBIT << (bit - n->startbit)); + if (!n->map) { + /* drop this node from the bitmap */ + + if (!n->next) { + /* + * this was the highest map + * within the bitmap + */ + if (prev) + e->highbit = prev->startbit + MAPSIZE; + else + e->highbit = 0; + } + if (prev) + prev->next = n->next; + else + e->node = n->next; + + kfree(n); + } + } + return 0; + } + prev = n; + n = n->next; + } + + if (!value) + return 0; + + new = kmalloc(sizeof(*new), GFP_ATOMIC); + if (!new) + return -ENOMEM; + memset(new, 0, sizeof(*new)); + + new->startbit = bit & ~(MAPSIZE - 1); + new->map = (MAPBIT << (bit - new->startbit)); + + if (!n) + /* this node will be the highest map within the bitmap */ + e->highbit = new->startbit + MAPSIZE; + + if (prev) { + new->next = prev->next; + prev->next = new; + } else { + new->next = e->node; + e->node = new; + } + + return 0; +} + +void ebitmap_destroy(struct ebitmap *e) +{ + struct ebitmap_node *n, *temp; + + if (!e) + return; + + n = e->node; + while (n) { + temp = n; + n = n->next; + kfree(temp); + } + + e->highbit = 0; + e->node = NULL; + return; +} + +int ebitmap_read(struct ebitmap *e, void *fp) +{ + int rc; + struct ebitmap_node *n, *l; + u32 buf[3], mapsize, count, i; + u64 map; + + ebitmap_init(e); + + rc = next_entry(buf, fp, sizeof buf); + if (rc < 0) + goto out; + + mapsize = le32_to_cpu(buf[0]); + e->highbit = le32_to_cpu(buf[1]); + count = le32_to_cpu(buf[2]); + + if (mapsize != MAPSIZE) { + printk(KERN_ERR "security: ebitmap: map size %u does not " + "match my size %Zd (high bit was %d)\n", mapsize, + MAPSIZE, e->highbit); + goto bad; + } + if (!e->highbit) { + e->node = NULL; + goto ok; + } + if (e->highbit & (MAPSIZE - 1)) { + printk(KERN_ERR "security: ebitmap: high bit (%d) is not a " + "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE); + goto bad; + } + l = NULL; + for (i = 0; i < count; i++) { + rc = next_entry(buf, fp, sizeof(u32)); + if (rc < 0) { + printk(KERN_ERR "security: ebitmap: truncated map\n"); + goto bad; + } + n = kmalloc(sizeof(*n), GFP_KERNEL); + if (!n) { + printk(KERN_ERR "security: ebitmap: out of memory\n"); + rc = -ENOMEM; + goto bad; + } + memset(n, 0, sizeof(*n)); + + n->startbit = le32_to_cpu(buf[0]); + + if (n->startbit & (MAPSIZE - 1)) { + printk(KERN_ERR "security: ebitmap start bit (%d) is " + "not a multiple of the map size (%Zd)\n", + n->startbit, MAPSIZE); + goto bad_free; + } + if (n->startbit > (e->highbit - MAPSIZE)) { + printk(KERN_ERR "security: ebitmap start bit (%d) is " + "beyond the end of the bitmap (%Zd)\n", + n->startbit, (e->highbit - MAPSIZE)); + goto bad_free; + } + rc = next_entry(&map, fp, sizeof(u64)); + if (rc < 0) { + printk(KERN_ERR "security: ebitmap: truncated map\n"); + goto bad_free; + } + n->map = le64_to_cpu(map); + + if (!n->map) { + printk(KERN_ERR "security: ebitmap: null map in " + "ebitmap (startbit %d)\n", n->startbit); + goto bad_free; + } + if (l) { + if (n->startbit <= l->startbit) { + printk(KERN_ERR "security: ebitmap: start " + "bit %d comes after start bit %d\n", + n->startbit, l->startbit); + goto bad_free; + } + l->next = n; + } else + e->node = n; + + l = n; + } + +ok: + rc = 0; +out: + return rc; +bad_free: + kfree(n); +bad: + if (!rc) + rc = -EINVAL; + ebitmap_destroy(e); + goto out; +} -- cgit v1.2.3-59-g8ed1b