1 /* 2 * Implementation of the extensible bitmap type. 3 * 4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil> 5 */ 6 /* 7 * Updated: Hewlett-Packard <paul.moore@hp.com> 8 * 9 * Added ebitmap_export() and ebitmap_import() 10 * 11 * (c) Copyright Hewlett-Packard Development Company, L.P., 2006 12 */ 13 14 #include <linux/kernel.h> 15 #include <linux/slab.h> 16 #include <linux/errno.h> 17 #include "ebitmap.h" 18 #include "policydb.h" 19 20 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2) 21 { 22 struct ebitmap_node *n1, *n2; 23 24 if (e1->highbit != e2->highbit) 25 return 0; 26 27 n1 = e1->node; 28 n2 = e2->node; 29 while (n1 && n2 && 30 (n1->startbit == n2->startbit) && 31 (n1->map == n2->map)) { 32 n1 = n1->next; 33 n2 = n2->next; 34 } 35 36 if (n1 || n2) 37 return 0; 38 39 return 1; 40 } 41 42 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src) 43 { 44 struct ebitmap_node *n, *new, *prev; 45 46 ebitmap_init(dst); 47 n = src->node; 48 prev = NULL; 49 while (n) { 50 new = kzalloc(sizeof(*new), GFP_ATOMIC); 51 if (!new) { 52 ebitmap_destroy(dst); 53 return -ENOMEM; 54 } 55 new->startbit = n->startbit; 56 new->map = n->map; 57 new->next = NULL; 58 if (prev) 59 prev->next = new; 60 else 61 dst->node = new; 62 prev = new; 63 n = n->next; 64 } 65 66 dst->highbit = src->highbit; 67 return 0; 68 } 69 70 /** 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 75 * 76 * Description: 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. 83 * 84 */ 85 int ebitmap_export(const struct ebitmap *src, 86 unsigned char **dst, 87 size_t *dst_len) 88 { 89 size_t bitmap_len; 90 unsigned char *bitmap; 91 struct ebitmap_node *iter_node; 92 MAPTYPE node_val; 93 size_t bitmap_byte; 94 unsigned char bitmask; 95 96 bitmap_len = src->highbit / 8; 97 if (src->highbit % 7) 98 bitmap_len += 1; 99 if (bitmap_len == 0) 100 return -EINVAL; 101 102 bitmap = kzalloc((bitmap_len & ~(sizeof(MAPTYPE) - 1)) + 103 sizeof(MAPTYPE), 104 GFP_ATOMIC); 105 if (bitmap == NULL) 106 return -ENOMEM; 107 108 iter_node = src->node; 109 do { 110 bitmap_byte = iter_node->startbit / 8; 111 bitmask = 0x80; 112 node_val = iter_node->map; 113 do { 114 if (bitmask == 0) { 115 bitmap_byte++; 116 bitmask = 0x80; 117 } 118 if (node_val & (MAPTYPE)0x01) 119 bitmap[bitmap_byte] |= bitmask; 120 node_val >>= 1; 121 bitmask >>= 1; 122 } while (node_val > 0); 123 iter_node = iter_node->next; 124 } while (iter_node); 125 126 *dst = bitmap; 127 *dst_len = bitmap_len; 128 return 0; 129 } 130 131 /** 132 * ebitmap_import - Import an unsigned char bitmap string into an ebitmap 133 * @src: the bitmap string 134 * @src_len: the bitmap length in bytes 135 * @dst: the empty ebitmap 136 * 137 * Description: 138 * This function takes a little endian bitmap string in src and imports it into 139 * the ebitmap pointed to by dst. Returns zero on success, negative values on 140 * failure. 141 * 142 */ 143 int ebitmap_import(const unsigned char *src, 144 size_t src_len, 145 struct ebitmap *dst) 146 { 147 size_t src_off = 0; 148 size_t node_limit; 149 struct ebitmap_node *node_new; 150 struct ebitmap_node *node_last = NULL; 151 u32 i_byte; 152 u32 i_bit; 153 unsigned char src_byte; 154 155 while (src_off < src_len) { 156 if (src_len - src_off >= sizeof(MAPTYPE)) { 157 if (*(MAPTYPE *)&src[src_off] == 0) { 158 src_off += sizeof(MAPTYPE); 159 continue; 160 } 161 node_limit = sizeof(MAPTYPE); 162 } else { 163 for (src_byte = 0, i_byte = src_off; 164 i_byte < src_len && src_byte == 0; 165 i_byte++) 166 src_byte |= src[i_byte]; 167 if (src_byte == 0) 168 break; 169 node_limit = src_len - src_off; 170 } 171 172 node_new = kzalloc(sizeof(*node_new), GFP_ATOMIC); 173 if (unlikely(node_new == NULL)) { 174 ebitmap_destroy(dst); 175 return -ENOMEM; 176 } 177 node_new->startbit = src_off * 8; 178 for (i_byte = 0; i_byte < node_limit; i_byte++) { 179 src_byte = src[src_off++]; 180 for (i_bit = i_byte * 8; src_byte != 0; i_bit++) { 181 if (src_byte & 0x80) 182 node_new->map |= MAPBIT << i_bit; 183 src_byte <<= 1; 184 } 185 } 186 187 if (node_last != NULL) 188 node_last->next = node_new; 189 else 190 dst->node = node_new; 191 node_last = node_new; 192 } 193 194 if (likely(node_last != NULL)) 195 dst->highbit = node_last->startbit + MAPSIZE; 196 else 197 ebitmap_init(dst); 198 199 return 0; 200 } 201 202 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2) 203 { 204 struct ebitmap_node *n1, *n2; 205 206 if (e1->highbit < e2->highbit) 207 return 0; 208 209 n1 = e1->node; 210 n2 = e2->node; 211 while (n1 && n2 && (n1->startbit <= n2->startbit)) { 212 if (n1->startbit < n2->startbit) { 213 n1 = n1->next; 214 continue; 215 } 216 if ((n1->map & n2->map) != n2->map) 217 return 0; 218 219 n1 = n1->next; 220 n2 = n2->next; 221 } 222 223 if (n2) 224 return 0; 225 226 return 1; 227 } 228 229 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit) 230 { 231 struct ebitmap_node *n; 232 233 if (e->highbit < bit) 234 return 0; 235 236 n = e->node; 237 while (n && (n->startbit <= bit)) { 238 if ((n->startbit + MAPSIZE) > bit) { 239 if (n->map & (MAPBIT << (bit - n->startbit))) 240 return 1; 241 else 242 return 0; 243 } 244 n = n->next; 245 } 246 247 return 0; 248 } 249 250 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) 251 { 252 struct ebitmap_node *n, *prev, *new; 253 254 prev = NULL; 255 n = e->node; 256 while (n && n->startbit <= bit) { 257 if ((n->startbit + MAPSIZE) > bit) { 258 if (value) { 259 n->map |= (MAPBIT << (bit - n->startbit)); 260 } else { 261 n->map &= ~(MAPBIT << (bit - n->startbit)); 262 if (!n->map) { 263 /* drop this node from the bitmap */ 264 265 if (!n->next) { 266 /* 267 * this was the highest map 268 * within the bitmap 269 */ 270 if (prev) 271 e->highbit = prev->startbit + MAPSIZE; 272 else 273 e->highbit = 0; 274 } 275 if (prev) 276 prev->next = n->next; 277 else 278 e->node = n->next; 279 280 kfree(n); 281 } 282 } 283 return 0; 284 } 285 prev = n; 286 n = n->next; 287 } 288 289 if (!value) 290 return 0; 291 292 new = kzalloc(sizeof(*new), GFP_ATOMIC); 293 if (!new) 294 return -ENOMEM; 295 296 new->startbit = bit & ~(MAPSIZE - 1); 297 new->map = (MAPBIT << (bit - new->startbit)); 298 299 if (!n) 300 /* this node will be the highest map within the bitmap */ 301 e->highbit = new->startbit + MAPSIZE; 302 303 if (prev) { 304 new->next = prev->next; 305 prev->next = new; 306 } else { 307 new->next = e->node; 308 e->node = new; 309 } 310 311 return 0; 312 } 313 314 void ebitmap_destroy(struct ebitmap *e) 315 { 316 struct ebitmap_node *n, *temp; 317 318 if (!e) 319 return; 320 321 n = e->node; 322 while (n) { 323 temp = n; 324 n = n->next; 325 kfree(temp); 326 } 327 328 e->highbit = 0; 329 e->node = NULL; 330 return; 331 } 332 333 int ebitmap_read(struct ebitmap *e, void *fp) 334 { 335 int rc; 336 struct ebitmap_node *n, *l; 337 __le32 buf[3]; 338 u32 mapsize, count, i; 339 __le64 map; 340 341 ebitmap_init(e); 342 343 rc = next_entry(buf, fp, sizeof buf); 344 if (rc < 0) 345 goto out; 346 347 mapsize = le32_to_cpu(buf[0]); 348 e->highbit = le32_to_cpu(buf[1]); 349 count = le32_to_cpu(buf[2]); 350 351 if (mapsize != MAPSIZE) { 352 printk(KERN_ERR "security: ebitmap: map size %u does not " 353 "match my size %Zd (high bit was %d)\n", mapsize, 354 MAPSIZE, e->highbit); 355 goto bad; 356 } 357 if (!e->highbit) { 358 e->node = NULL; 359 goto ok; 360 } 361 if (e->highbit & (MAPSIZE - 1)) { 362 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a " 363 "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE); 364 goto bad; 365 } 366 l = NULL; 367 for (i = 0; i < count; i++) { 368 rc = next_entry(buf, fp, sizeof(u32)); 369 if (rc < 0) { 370 printk(KERN_ERR "security: ebitmap: truncated map\n"); 371 goto bad; 372 } 373 n = kzalloc(sizeof(*n), GFP_KERNEL); 374 if (!n) { 375 printk(KERN_ERR "security: ebitmap: out of memory\n"); 376 rc = -ENOMEM; 377 goto bad; 378 } 379 380 n->startbit = le32_to_cpu(buf[0]); 381 382 if (n->startbit & (MAPSIZE - 1)) { 383 printk(KERN_ERR "security: ebitmap start bit (%d) is " 384 "not a multiple of the map size (%Zd)\n", 385 n->startbit, MAPSIZE); 386 goto bad_free; 387 } 388 if (n->startbit > (e->highbit - MAPSIZE)) { 389 printk(KERN_ERR "security: ebitmap start bit (%d) is " 390 "beyond the end of the bitmap (%Zd)\n", 391 n->startbit, (e->highbit - MAPSIZE)); 392 goto bad_free; 393 } 394 rc = next_entry(&map, fp, sizeof(u64)); 395 if (rc < 0) { 396 printk(KERN_ERR "security: ebitmap: truncated map\n"); 397 goto bad_free; 398 } 399 n->map = le64_to_cpu(map); 400 401 if (!n->map) { 402 printk(KERN_ERR "security: ebitmap: null map in " 403 "ebitmap (startbit %d)\n", n->startbit); 404 goto bad_free; 405 } 406 if (l) { 407 if (n->startbit <= l->startbit) { 408 printk(KERN_ERR "security: ebitmap: start " 409 "bit %d comes after start bit %d\n", 410 n->startbit, l->startbit); 411 goto bad_free; 412 } 413 l->next = n; 414 } else 415 e->node = n; 416 417 l = n; 418 } 419 420 ok: 421 rc = 0; 422 out: 423 return rc; 424 bad_free: 425 kfree(n); 426 bad: 427 if (!rc) 428 rc = -EINVAL; 429 ebitmap_destroy(e); 430 goto out; 431 } 432