1 /* 2 * Implementation of the extensible bitmap type. 3 * 4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil> 5 */ 6 #include <linux/kernel.h> 7 #include <linux/slab.h> 8 #include <linux/errno.h> 9 #include "ebitmap.h" 10 #include "policydb.h" 11 12 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2) 13 { 14 struct ebitmap_node *n1, *n2; 15 16 if (e1->highbit != e2->highbit) 17 return 0; 18 19 n1 = e1->node; 20 n2 = e2->node; 21 while (n1 && n2 && 22 (n1->startbit == n2->startbit) && 23 (n1->map == n2->map)) { 24 n1 = n1->next; 25 n2 = n2->next; 26 } 27 28 if (n1 || n2) 29 return 0; 30 31 return 1; 32 } 33 34 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src) 35 { 36 struct ebitmap_node *n, *new, *prev; 37 38 ebitmap_init(dst); 39 n = src->node; 40 prev = NULL; 41 while (n) { 42 new = kmalloc(sizeof(*new), GFP_ATOMIC); 43 if (!new) { 44 ebitmap_destroy(dst); 45 return -ENOMEM; 46 } 47 memset(new, 0, sizeof(*new)); 48 new->startbit = n->startbit; 49 new->map = n->map; 50 new->next = NULL; 51 if (prev) 52 prev->next = new; 53 else 54 dst->node = new; 55 prev = new; 56 n = n->next; 57 } 58 59 dst->highbit = src->highbit; 60 return 0; 61 } 62 63 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2) 64 { 65 struct ebitmap_node *n1, *n2; 66 67 if (e1->highbit < e2->highbit) 68 return 0; 69 70 n1 = e1->node; 71 n2 = e2->node; 72 while (n1 && n2 && (n1->startbit <= n2->startbit)) { 73 if (n1->startbit < n2->startbit) { 74 n1 = n1->next; 75 continue; 76 } 77 if ((n1->map & n2->map) != n2->map) 78 return 0; 79 80 n1 = n1->next; 81 n2 = n2->next; 82 } 83 84 if (n2) 85 return 0; 86 87 return 1; 88 } 89 90 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit) 91 { 92 struct ebitmap_node *n; 93 94 if (e->highbit < bit) 95 return 0; 96 97 n = e->node; 98 while (n && (n->startbit <= bit)) { 99 if ((n->startbit + MAPSIZE) > bit) { 100 if (n->map & (MAPBIT << (bit - n->startbit))) 101 return 1; 102 else 103 return 0; 104 } 105 n = n->next; 106 } 107 108 return 0; 109 } 110 111 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) 112 { 113 struct ebitmap_node *n, *prev, *new; 114 115 prev = NULL; 116 n = e->node; 117 while (n && n->startbit <= bit) { 118 if ((n->startbit + MAPSIZE) > bit) { 119 if (value) { 120 n->map |= (MAPBIT << (bit - n->startbit)); 121 } else { 122 n->map &= ~(MAPBIT << (bit - n->startbit)); 123 if (!n->map) { 124 /* drop this node from the bitmap */ 125 126 if (!n->next) { 127 /* 128 * this was the highest map 129 * within the bitmap 130 */ 131 if (prev) 132 e->highbit = prev->startbit + MAPSIZE; 133 else 134 e->highbit = 0; 135 } 136 if (prev) 137 prev->next = n->next; 138 else 139 e->node = n->next; 140 141 kfree(n); 142 } 143 } 144 return 0; 145 } 146 prev = n; 147 n = n->next; 148 } 149 150 if (!value) 151 return 0; 152 153 new = kmalloc(sizeof(*new), GFP_ATOMIC); 154 if (!new) 155 return -ENOMEM; 156 memset(new, 0, sizeof(*new)); 157 158 new->startbit = bit & ~(MAPSIZE - 1); 159 new->map = (MAPBIT << (bit - new->startbit)); 160 161 if (!n) 162 /* this node will be the highest map within the bitmap */ 163 e->highbit = new->startbit + MAPSIZE; 164 165 if (prev) { 166 new->next = prev->next; 167 prev->next = new; 168 } else { 169 new->next = e->node; 170 e->node = new; 171 } 172 173 return 0; 174 } 175 176 void ebitmap_destroy(struct ebitmap *e) 177 { 178 struct ebitmap_node *n, *temp; 179 180 if (!e) 181 return; 182 183 n = e->node; 184 while (n) { 185 temp = n; 186 n = n->next; 187 kfree(temp); 188 } 189 190 e->highbit = 0; 191 e->node = NULL; 192 return; 193 } 194 195 int ebitmap_read(struct ebitmap *e, void *fp) 196 { 197 int rc; 198 struct ebitmap_node *n, *l; 199 __le32 buf[3]; 200 u32 mapsize, count, i; 201 __le64 map; 202 203 ebitmap_init(e); 204 205 rc = next_entry(buf, fp, sizeof buf); 206 if (rc < 0) 207 goto out; 208 209 mapsize = le32_to_cpu(buf[0]); 210 e->highbit = le32_to_cpu(buf[1]); 211 count = le32_to_cpu(buf[2]); 212 213 if (mapsize != MAPSIZE) { 214 printk(KERN_ERR "security: ebitmap: map size %u does not " 215 "match my size %Zd (high bit was %d)\n", mapsize, 216 MAPSIZE, e->highbit); 217 goto bad; 218 } 219 if (!e->highbit) { 220 e->node = NULL; 221 goto ok; 222 } 223 if (e->highbit & (MAPSIZE - 1)) { 224 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a " 225 "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE); 226 goto bad; 227 } 228 l = NULL; 229 for (i = 0; i < count; i++) { 230 rc = next_entry(buf, fp, sizeof(u32)); 231 if (rc < 0) { 232 printk(KERN_ERR "security: ebitmap: truncated map\n"); 233 goto bad; 234 } 235 n = kmalloc(sizeof(*n), GFP_KERNEL); 236 if (!n) { 237 printk(KERN_ERR "security: ebitmap: out of memory\n"); 238 rc = -ENOMEM; 239 goto bad; 240 } 241 memset(n, 0, sizeof(*n)); 242 243 n->startbit = le32_to_cpu(buf[0]); 244 245 if (n->startbit & (MAPSIZE - 1)) { 246 printk(KERN_ERR "security: ebitmap start bit (%d) is " 247 "not a multiple of the map size (%Zd)\n", 248 n->startbit, MAPSIZE); 249 goto bad_free; 250 } 251 if (n->startbit > (e->highbit - MAPSIZE)) { 252 printk(KERN_ERR "security: ebitmap start bit (%d) is " 253 "beyond the end of the bitmap (%Zd)\n", 254 n->startbit, (e->highbit - MAPSIZE)); 255 goto bad_free; 256 } 257 rc = next_entry(&map, fp, sizeof(u64)); 258 if (rc < 0) { 259 printk(KERN_ERR "security: ebitmap: truncated map\n"); 260 goto bad_free; 261 } 262 n->map = le64_to_cpu(map); 263 264 if (!n->map) { 265 printk(KERN_ERR "security: ebitmap: null map in " 266 "ebitmap (startbit %d)\n", n->startbit); 267 goto bad_free; 268 } 269 if (l) { 270 if (n->startbit <= l->startbit) { 271 printk(KERN_ERR "security: ebitmap: start " 272 "bit %d comes after start bit %d\n", 273 n->startbit, l->startbit); 274 goto bad_free; 275 } 276 l->next = n; 277 } else 278 e->node = n; 279 280 l = n; 281 } 282 283 ok: 284 rc = 0; 285 out: 286 return rc; 287 bad_free: 288 kfree(n); 289 bad: 290 if (!rc) 291 rc = -EINVAL; 292 ebitmap_destroy(e); 293 goto out; 294 } 295