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 support to import/export the NetLabel category bitmap 10 * 11 * (c) Copyright Hewlett-Packard Development Company, L.P., 2006 12 */ 13 /* 14 * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com> 15 * Applied standard bit operations to improve bitmap scanning. 16 */ 17 18 #include <linux/kernel.h> 19 #include <linux/slab.h> 20 #include <linux/errno.h> 21 #include <net/netlabel.h> 22 #include "ebitmap.h" 23 #include "policydb.h" 24 25 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2) 26 { 27 struct ebitmap_node *n1, *n2; 28 29 if (e1->highbit != e2->highbit) 30 return 0; 31 32 n1 = e1->node; 33 n2 = e2->node; 34 while (n1 && n2 && 35 (n1->startbit == n2->startbit) && 36 !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) { 37 n1 = n1->next; 38 n2 = n2->next; 39 } 40 41 if (n1 || n2) 42 return 0; 43 44 return 1; 45 } 46 47 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src) 48 { 49 struct ebitmap_node *n, *new, *prev; 50 51 ebitmap_init(dst); 52 n = src->node; 53 prev = NULL; 54 while (n) { 55 new = kzalloc(sizeof(*new), GFP_ATOMIC); 56 if (!new) { 57 ebitmap_destroy(dst); 58 return -ENOMEM; 59 } 60 new->startbit = n->startbit; 61 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8); 62 new->next = NULL; 63 if (prev) 64 prev->next = new; 65 else 66 dst->node = new; 67 prev = new; 68 n = n->next; 69 } 70 71 dst->highbit = src->highbit; 72 return 0; 73 } 74 75 #ifdef CONFIG_NETLABEL 76 /** 77 * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap 78 * @ebmap: the ebitmap to export 79 * @catmap: the NetLabel category bitmap 80 * 81 * Description: 82 * Export a SELinux extensibile bitmap into a NetLabel category bitmap. 83 * Returns zero on success, negative values on error. 84 * 85 */ 86 int ebitmap_netlbl_export(struct ebitmap *ebmap, 87 struct netlbl_lsm_secattr_catmap **catmap) 88 { 89 struct ebitmap_node *e_iter = ebmap->node; 90 struct netlbl_lsm_secattr_catmap *c_iter; 91 u32 cmap_idx, cmap_sft; 92 int i; 93 94 /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64, 95 * however, it is not always compatible with an array of unsigned long 96 * in ebitmap_node. 97 * In addition, you should pay attention the following implementation 98 * assumes unsigned long has a width equal with or less than 64-bit. 99 */ 100 101 if (e_iter == NULL) { 102 *catmap = NULL; 103 return 0; 104 } 105 106 c_iter = netlbl_secattr_catmap_alloc(GFP_ATOMIC); 107 if (c_iter == NULL) 108 return -ENOMEM; 109 *catmap = c_iter; 110 c_iter->startbit = e_iter->startbit & ~(NETLBL_CATMAP_SIZE - 1); 111 112 while (e_iter) { 113 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) { 114 unsigned int delta, e_startbit, c_endbit; 115 116 e_startbit = e_iter->startbit + i * EBITMAP_UNIT_SIZE; 117 c_endbit = c_iter->startbit + NETLBL_CATMAP_SIZE; 118 if (e_startbit >= c_endbit) { 119 c_iter->next 120 = netlbl_secattr_catmap_alloc(GFP_ATOMIC); 121 if (c_iter->next == NULL) 122 goto netlbl_export_failure; 123 c_iter = c_iter->next; 124 c_iter->startbit 125 = e_startbit & ~(NETLBL_CATMAP_SIZE - 1); 126 } 127 delta = e_startbit - c_iter->startbit; 128 cmap_idx = delta / NETLBL_CATMAP_MAPSIZE; 129 cmap_sft = delta % NETLBL_CATMAP_MAPSIZE; 130 c_iter->bitmap[cmap_idx] 131 |= e_iter->maps[cmap_idx] << cmap_sft; 132 } 133 e_iter = e_iter->next; 134 } 135 136 return 0; 137 138 netlbl_export_failure: 139 netlbl_secattr_catmap_free(*catmap); 140 return -ENOMEM; 141 } 142 143 /** 144 * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap 145 * @ebmap: the ebitmap to import 146 * @catmap: the NetLabel category bitmap 147 * 148 * Description: 149 * Import a NetLabel category bitmap into a SELinux extensibile bitmap. 150 * Returns zero on success, negative values on error. 151 * 152 */ 153 int ebitmap_netlbl_import(struct ebitmap *ebmap, 154 struct netlbl_lsm_secattr_catmap *catmap) 155 { 156 struct ebitmap_node *e_iter = NULL; 157 struct ebitmap_node *emap_prev = NULL; 158 struct netlbl_lsm_secattr_catmap *c_iter = catmap; 159 u32 c_idx, c_pos, e_idx, e_sft; 160 161 /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64, 162 * however, it is not always compatible with an array of unsigned long 163 * in ebitmap_node. 164 * In addition, you should pay attention the following implementation 165 * assumes unsigned long has a width equal with or less than 64-bit. 166 */ 167 168 do { 169 for (c_idx = 0; c_idx < NETLBL_CATMAP_MAPCNT; c_idx++) { 170 unsigned int delta; 171 u64 map = c_iter->bitmap[c_idx]; 172 173 if (!map) 174 continue; 175 176 c_pos = c_iter->startbit 177 + c_idx * NETLBL_CATMAP_MAPSIZE; 178 if (!e_iter 179 || c_pos >= e_iter->startbit + EBITMAP_SIZE) { 180 e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC); 181 if (!e_iter) 182 goto netlbl_import_failure; 183 e_iter->startbit 184 = c_pos - (c_pos % EBITMAP_SIZE); 185 if (emap_prev == NULL) 186 ebmap->node = e_iter; 187 else 188 emap_prev->next = e_iter; 189 emap_prev = e_iter; 190 } 191 delta = c_pos - e_iter->startbit; 192 e_idx = delta / EBITMAP_UNIT_SIZE; 193 e_sft = delta % EBITMAP_UNIT_SIZE; 194 while (map) { 195 e_iter->maps[e_idx++] |= map & (-1UL); 196 map = EBITMAP_SHIFT_UNIT_SIZE(map); 197 } 198 } 199 c_iter = c_iter->next; 200 } while (c_iter); 201 if (e_iter != NULL) 202 ebmap->highbit = e_iter->startbit + EBITMAP_SIZE; 203 else 204 ebitmap_destroy(ebmap); 205 206 return 0; 207 208 netlbl_import_failure: 209 ebitmap_destroy(ebmap); 210 return -ENOMEM; 211 } 212 #endif /* CONFIG_NETLABEL */ 213 214 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2) 215 { 216 struct ebitmap_node *n1, *n2; 217 int i; 218 219 if (e1->highbit < e2->highbit) 220 return 0; 221 222 n1 = e1->node; 223 n2 = e2->node; 224 while (n1 && n2 && (n1->startbit <= n2->startbit)) { 225 if (n1->startbit < n2->startbit) { 226 n1 = n1->next; 227 continue; 228 } 229 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) { 230 if ((n1->maps[i] & n2->maps[i]) != n2->maps[i]) 231 return 0; 232 } 233 234 n1 = n1->next; 235 n2 = n2->next; 236 } 237 238 if (n2) 239 return 0; 240 241 return 1; 242 } 243 244 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit) 245 { 246 struct ebitmap_node *n; 247 248 if (e->highbit < bit) 249 return 0; 250 251 n = e->node; 252 while (n && (n->startbit <= bit)) { 253 if ((n->startbit + EBITMAP_SIZE) > bit) 254 return ebitmap_node_get_bit(n, bit); 255 n = n->next; 256 } 257 258 return 0; 259 } 260 261 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) 262 { 263 struct ebitmap_node *n, *prev, *new; 264 265 prev = NULL; 266 n = e->node; 267 while (n && n->startbit <= bit) { 268 if ((n->startbit + EBITMAP_SIZE) > bit) { 269 if (value) { 270 ebitmap_node_set_bit(n, bit); 271 } else { 272 unsigned int s; 273 274 ebitmap_node_clr_bit(n, bit); 275 276 s = find_first_bit(n->maps, EBITMAP_SIZE); 277 if (s < EBITMAP_SIZE) 278 return 0; 279 280 /* drop this node from the bitmap */ 281 if (!n->next) { 282 /* 283 * this was the highest map 284 * within the bitmap 285 */ 286 if (prev) 287 e->highbit = prev->startbit 288 + EBITMAP_SIZE; 289 else 290 e->highbit = 0; 291 } 292 if (prev) 293 prev->next = n->next; 294 else 295 e->node = n->next; 296 kfree(n); 297 } 298 return 0; 299 } 300 prev = n; 301 n = n->next; 302 } 303 304 if (!value) 305 return 0; 306 307 new = kzalloc(sizeof(*new), GFP_ATOMIC); 308 if (!new) 309 return -ENOMEM; 310 311 new->startbit = bit - (bit % EBITMAP_SIZE); 312 ebitmap_node_set_bit(new, bit); 313 314 if (!n) 315 /* this node will be the highest map within the bitmap */ 316 e->highbit = new->startbit + EBITMAP_SIZE; 317 318 if (prev) { 319 new->next = prev->next; 320 prev->next = new; 321 } else { 322 new->next = e->node; 323 e->node = new; 324 } 325 326 return 0; 327 } 328 329 void ebitmap_destroy(struct ebitmap *e) 330 { 331 struct ebitmap_node *n, *temp; 332 333 if (!e) 334 return; 335 336 n = e->node; 337 while (n) { 338 temp = n; 339 n = n->next; 340 kfree(temp); 341 } 342 343 e->highbit = 0; 344 e->node = NULL; 345 return; 346 } 347 348 int ebitmap_read(struct ebitmap *e, void *fp) 349 { 350 struct ebitmap_node *n = NULL; 351 u32 mapunit, count, startbit, index; 352 u64 map; 353 __le32 buf[3]; 354 int rc, i; 355 356 ebitmap_init(e); 357 358 rc = next_entry(buf, fp, sizeof buf); 359 if (rc < 0) 360 goto out; 361 362 mapunit = le32_to_cpu(buf[0]); 363 e->highbit = le32_to_cpu(buf[1]); 364 count = le32_to_cpu(buf[2]); 365 366 if (mapunit != sizeof(u64) * 8) { 367 printk(KERN_ERR "SELinux: ebitmap: map size %u does not " 368 "match my size %Zd (high bit was %d)\n", 369 mapunit, sizeof(u64) * 8, e->highbit); 370 goto bad; 371 } 372 373 /* round up e->highbit */ 374 e->highbit += EBITMAP_SIZE - 1; 375 e->highbit -= (e->highbit % EBITMAP_SIZE); 376 377 if (!e->highbit) { 378 e->node = NULL; 379 goto ok; 380 } 381 382 for (i = 0; i < count; i++) { 383 rc = next_entry(&startbit, fp, sizeof(u32)); 384 if (rc < 0) { 385 printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); 386 goto bad; 387 } 388 startbit = le32_to_cpu(startbit); 389 390 if (startbit & (mapunit - 1)) { 391 printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " 392 "not a multiple of the map unit size (%u)\n", 393 startbit, mapunit); 394 goto bad; 395 } 396 if (startbit > e->highbit - mapunit) { 397 printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " 398 "beyond the end of the bitmap (%u)\n", 399 startbit, (e->highbit - mapunit)); 400 goto bad; 401 } 402 403 if (!n || startbit >= n->startbit + EBITMAP_SIZE) { 404 struct ebitmap_node *tmp; 405 tmp = kzalloc(sizeof(*tmp), GFP_KERNEL); 406 if (!tmp) { 407 printk(KERN_ERR 408 "SELinux: ebitmap: out of memory\n"); 409 rc = -ENOMEM; 410 goto bad; 411 } 412 /* round down */ 413 tmp->startbit = startbit - (startbit % EBITMAP_SIZE); 414 if (n) 415 n->next = tmp; 416 else 417 e->node = tmp; 418 n = tmp; 419 } else if (startbit <= n->startbit) { 420 printk(KERN_ERR "SELinux: ebitmap: start bit %d" 421 " comes after start bit %d\n", 422 startbit, n->startbit); 423 goto bad; 424 } 425 426 rc = next_entry(&map, fp, sizeof(u64)); 427 if (rc < 0) { 428 printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); 429 goto bad; 430 } 431 map = le64_to_cpu(map); 432 433 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; 434 while (map) { 435 n->maps[index++] = map & (-1UL); 436 map = EBITMAP_SHIFT_UNIT_SIZE(map); 437 } 438 } 439 ok: 440 rc = 0; 441 out: 442 return rc; 443 bad: 444 if (!rc) 445 rc = -EINVAL; 446 ebitmap_destroy(e); 447 goto out; 448 } 449