security/selinux/ss/ebitmap.c

   1 /*
   2  * Implementation of the extensible bitmap type.
   3  *
   4  * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
   5  */
   6 /*
   7  * Updated: Hewlett-Packard <paul@paul-moore.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 #define BITS_PER_U64    (sizeof(u64) * 8)
  26
  27 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
  28 {
  29         struct ebitmap_node *n1, *n2;
  30
  31         if (e1->highbit != e2->highbit)
  32                 return 0;
  33
  34         n1 = e1->node;
  35         n2 = e2->node;
  36         while (n1 && n2 &&
  37                (n1->startbit == n2->startbit) &&
  38                !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
  39                 n1 = n1->next;
  40                 n2 = n2->next;
  41         }
  42
  43         if (n1 || n2)
  44                 return 0;
  45
  46         return 1;
  47 }
  48
  49 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
  50 {
  51         struct ebitmap_node *n, *new, *prev;
  52
  53         ebitmap_init(dst);
  54         n = src->node;
  55         prev = NULL;
  56         while (n) {
  57                 new = kzalloc(sizeof(*new), GFP_ATOMIC);
  58                 if (!new) {
  59                         ebitmap_destroy(dst);
  60                         return -ENOMEM;
  61                 }
  62                 new->startbit = n->startbit;
  63                 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
  64                 new->next = NULL;
  65                 if (prev)
  66                         prev->next = new;
  67                 else
  68                         dst->node = new;
  69                 prev = new;
  70                 n = n->next;
  71         }
  72
  73         dst->highbit = src->highbit;
  74         return 0;
  75 }
  76
  77 #ifdef CONFIG_NETLABEL
  78 /**
  79  * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap
  80  * @ebmap: the ebitmap to export
  81  * @catmap: the NetLabel category bitmap
  82  *
  83  * Description:
  84  * Export a SELinux extensibile bitmap into a NetLabel category bitmap.
  85  * Returns zero on success, negative values on error.
  86  *
  87  */
  88 int ebitmap_netlbl_export(struct ebitmap *ebmap,
  89                           struct netlbl_lsm_secattr_catmap **catmap)
  90 {
  91         struct ebitmap_node *e_iter = ebmap->node;
  92         struct netlbl_lsm_secattr_catmap *c_iter;
  93         u32 cmap_idx, cmap_sft;
  94         int i;
  95
  96         /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
  97          * however, it is not always compatible with an array of unsigned long
  98          * in ebitmap_node.
  99          * In addition, you should pay attention the following implementation
 100          * assumes unsigned long has a width equal with or less than 64-bit.
 101          */
 102
 103         if (e_iter == NULL) {
 104                 *catmap = NULL;
 105                 return 0;
 106         }
 107
 108         c_iter = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
 109         if (c_iter == NULL)
 110                 return -ENOMEM;
 111         *catmap = c_iter;
 112         c_iter->startbit = e_iter->startbit & ~(NETLBL_CATMAP_SIZE - 1);
 113
 114         while (e_iter) {
 115                 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
 116                         unsigned int delta, e_startbit, c_endbit;
 117
 118                         e_startbit = e_iter->startbit + i * EBITMAP_UNIT_SIZE;
 119                         c_endbit = c_iter->startbit + NETLBL_CATMAP_SIZE;
 120                         if (e_startbit >= c_endbit) {
 121                                 c_iter->next
 122                                   = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
 123                                 if (c_iter->next == NULL)
 124                                         goto netlbl_export_failure;
 125                                 c_iter = c_iter->next;
 126                                 c_iter->startbit
 127                                   = e_startbit & ~(NETLBL_CATMAP_SIZE - 1);
 128                         }
 129                         delta = e_startbit - c_iter->startbit;
 130                         cmap_idx = delta / NETLBL_CATMAP_MAPSIZE;
 131                         cmap_sft = delta % NETLBL_CATMAP_MAPSIZE;
 132                         c_iter->bitmap[cmap_idx]
 133                                 |= e_iter->maps[i] << cmap_sft;
 134                 }
 135                 e_iter = e_iter->next;
 136         }
 137
 138         return 0;
 139
 140 netlbl_export_failure:
 141         netlbl_secattr_catmap_free(*catmap);
 142         return -ENOMEM;
 143 }
 144
 145 /**
 146  * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
 147  * @ebmap: the ebitmap to import
 148  * @catmap: the NetLabel category bitmap
 149  *
 150  * Description:
 151  * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
 152  * Returns zero on success, negative values on error.
 153  *
 154  */
 155 int ebitmap_netlbl_import(struct ebitmap *ebmap,
 156                           struct netlbl_lsm_secattr_catmap *catmap)
 157 {
 158         struct ebitmap_node *e_iter = NULL;
 159         struct ebitmap_node *emap_prev = NULL;
 160         struct netlbl_lsm_secattr_catmap *c_iter = catmap;
 161         u32 c_idx, c_pos, e_idx, e_sft;
 162
 163         /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
 164          * however, it is not always compatible with an array of unsigned long
 165          * in ebitmap_node.
 166          * In addition, you should pay attention the following implementation
 167          * assumes unsigned long has a width equal with or less than 64-bit.
 168          */
 169
 170         do {
 171                 for (c_idx = 0; c_idx < NETLBL_CATMAP_MAPCNT; c_idx++) {
 172                         unsigned int delta;
 173                         u64 map = c_iter->bitmap[c_idx];
 174
 175                         if (!map)
 176                                 continue;
 177
 178                         c_pos = c_iter->startbit
 179                                 + c_idx * NETLBL_CATMAP_MAPSIZE;
 180                         if (!e_iter
 181                             || c_pos >= e_iter->startbit + EBITMAP_SIZE) {
 182                                 e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC);
 183                                 if (!e_iter)
 184                                         goto netlbl_import_failure;
 185                                 e_iter->startbit
 186                                         = c_pos - (c_pos % EBITMAP_SIZE);
 187                                 if (emap_prev == NULL)
 188                                         ebmap->node = e_iter;
 189                                 else
 190                                         emap_prev->next = e_iter;
 191                                 emap_prev = e_iter;
 192                         }
 193                         delta = c_pos - e_iter->startbit;
 194                         e_idx = delta / EBITMAP_UNIT_SIZE;
 195                         e_sft = delta % EBITMAP_UNIT_SIZE;
 196                         while (map) {
 197                                 e_iter->maps[e_idx++] |= map & (-1UL);
 198                                 map = EBITMAP_SHIFT_UNIT_SIZE(map);
 199                         }
 200                 }
 201                 c_iter = c_iter->next;
 202         } while (c_iter);
 203         if (e_iter != NULL)
 204                 ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
 205         else
 206                 ebitmap_destroy(ebmap);
 207
 208         return 0;
 209
 210 netlbl_import_failure:
 211         ebitmap_destroy(ebmap);
 212         return -ENOMEM;
 213 }
 214 #endif /* CONFIG_NETLABEL */
 215
 216 /*
 217  * Check to see if all the bits set in e2 are also set in e1. Optionally,
 218  * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed
 219  * last_e2bit.
 220  */
 221 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit)
 222 {
 223         struct ebitmap_node *n1, *n2;
 224         int i;
 225
 226         if (e1->highbit < e2->highbit)
 227                 return 0;
 228
 229         n1 = e1->node;
 230         n2 = e2->node;
 231
 232         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
 233                 if (n1->startbit < n2->startbit) {
 234                         n1 = n1->next;
 235                         continue;
 236                 }
 237                 for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; )
 238                         i--;    /* Skip trailing NULL map entries */
 239                 if (last_e2bit && (i >= 0)) {
 240                         u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE +
 241                                          __fls(n2->maps[i]);
 242                         if (lastsetbit > last_e2bit)
 243                                 return 0;
 244                 }
 245
 246                 while (i >= 0) {
 247                         if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
 248                                 return 0;
 249                         i--;
 250                 }
 251
 252                 n1 = n1->next;
 253                 n2 = n2->next;
 254         }
 255
 256         if (n2)
 257                 return 0;
 258
 259         return 1;
 260 }
 261
 262 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
 263 {
 264         struct ebitmap_node *n;
 265
 266         if (e->highbit < bit)
 267                 return 0;
 268
 269         n = e->node;
 270         while (n && (n->startbit <= bit)) {
 271                 if ((n->startbit + EBITMAP_SIZE) > bit)
 272                         return ebitmap_node_get_bit(n, bit);
 273                 n = n->next;
 274         }
 275
 276         return 0;
 277 }
 278
 279 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 280 {
 281         struct ebitmap_node *n, *prev, *new;
 282
 283         prev = NULL;
 284         n = e->node;
 285         while (n && n->startbit <= bit) {
 286                 if ((n->startbit + EBITMAP_SIZE) > bit) {
 287                         if (value) {
 288                                 ebitmap_node_set_bit(n, bit);
 289                         } else {
 290                                 unsigned int s;
 291
 292                                 ebitmap_node_clr_bit(n, bit);
 293
 294                                 s = find_first_bit(n->maps, EBITMAP_SIZE);
 295                                 if (s < EBITMAP_SIZE)
 296                                         return 0;
 297
 298                                 /* drop this node from the bitmap */
 299                                 if (!n->next) {
 300                                         /*
 301                                          * this was the highest map
 302                                          * within the bitmap
 303                                          */
 304                                         if (prev)
 305                                                 e->highbit = prev->startbit
 306                                                              + EBITMAP_SIZE;
 307                                         else
 308                                                 e->highbit = 0;
 309                                 }
 310                                 if (prev)
 311                                         prev->next = n->next;
 312                                 else
 313                                         e->node = n->next;
 314                                 kfree(n);
 315                         }
 316                         return 0;
 317                 }
 318                 prev = n;
 319                 n = n->next;
 320         }
 321
 322         if (!value)
 323                 return 0;
 324
 325         new = kzalloc(sizeof(*new), GFP_ATOMIC);
 326         if (!new)
 327                 return -ENOMEM;
 328
 329         new->startbit = bit - (bit % EBITMAP_SIZE);
 330         ebitmap_node_set_bit(new, bit);
 331
 332         if (!n)
 333                 /* this node will be the highest map within the bitmap */
 334                 e->highbit = new->startbit + EBITMAP_SIZE;
 335
 336         if (prev) {
 337                 new->next = prev->next;
 338                 prev->next = new;
 339         } else {
 340                 new->next = e->node;
 341                 e->node = new;
 342         }
 343
 344         return 0;
 345 }
 346
 347 void ebitmap_destroy(struct ebitmap *e)
 348 {
 349         struct ebitmap_node *n, *temp;
 350
 351         if (!e)
 352                 return;
 353
 354         n = e->node;
 355         while (n) {
 356                 temp = n;
 357                 n = n->next;
 358                 kfree(temp);
 359         }
 360
 361         e->highbit = 0;
 362         e->node = NULL;
 363         return;
 364 }
 365
 366 int ebitmap_read(struct ebitmap *e, void *fp)
 367 {
 368         struct ebitmap_node *n = NULL;
 369         u32 mapunit, count, startbit, index;
 370         u64 map;
 371         __le32 buf[3];
 372         int rc, i;
 373
 374         ebitmap_init(e);
 375
 376         rc = next_entry(buf, fp, sizeof buf);
 377         if (rc < 0)
 378                 goto out;
 379
 380         mapunit = le32_to_cpu(buf[0]);
 381         e->highbit = le32_to_cpu(buf[1]);
 382         count = le32_to_cpu(buf[2]);
 383
 384         if (mapunit != BITS_PER_U64) {
 385                 printk(KERN_ERR "SELinux: ebitmap: map size %u does not "
 386                        "match my size %Zd (high bit was %d)\n",
 387                        mapunit, BITS_PER_U64, e->highbit);
 388                 goto bad;
 389         }
 390
 391         /* round up e->highbit */
 392         e->highbit += EBITMAP_SIZE - 1;
 393         e->highbit -= (e->highbit % EBITMAP_SIZE);
 394
 395         if (!e->highbit) {
 396                 e->node = NULL;
 397                 goto ok;
 398         }
 399
 400         for (i = 0; i < count; i++) {
 401                 rc = next_entry(&startbit, fp, sizeof(u32));
 402                 if (rc < 0) {
 403                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
 404                         goto bad;
 405                 }
 406                 startbit = le32_to_cpu(startbit);
 407
 408                 if (startbit & (mapunit - 1)) {
 409                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
 410                                "not a multiple of the map unit size (%u)\n",
 411                                startbit, mapunit);
 412                         goto bad;
 413                 }
 414                 if (startbit > e->highbit - mapunit) {
 415                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
 416                                "beyond the end of the bitmap (%u)\n",
 417                                startbit, (e->highbit - mapunit));
 418                         goto bad;
 419                 }
 420
 421                 if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
 422                         struct ebitmap_node *tmp;
 423                         tmp = kzalloc(sizeof(*tmp), GFP_KERNEL);
 424                         if (!tmp) {
 425                                 printk(KERN_ERR
 426                                        "SELinux: ebitmap: out of memory\n");
 427                                 rc = -ENOMEM;
 428                                 goto bad;
 429                         }
 430                         /* round down */
 431                         tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
 432                         if (n)
 433                                 n->next = tmp;
 434                         else
 435                                 e->node = tmp;
 436                         n = tmp;
 437                 } else if (startbit <= n->startbit) {
 438                         printk(KERN_ERR "SELinux: ebitmap: start bit %d"
 439                                " comes after start bit %d\n",
 440                                startbit, n->startbit);
 441                         goto bad;
 442                 }
 443
 444                 rc = next_entry(&map, fp, sizeof(u64));
 445                 if (rc < 0) {
 446                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
 447                         goto bad;
 448                 }
 449                 map = le64_to_cpu(map);
 450
 451                 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
 452                 while (map) {
 453                         n->maps[index++] = map & (-1UL);
 454                         map = EBITMAP_SHIFT_UNIT_SIZE(map);
 455                 }
 456         }
 457 ok:
 458         rc = 0;
 459 out:
 460         return rc;
 461 bad:
 462         if (!rc)
 463                 rc = -EINVAL;
 464         ebitmap_destroy(e);
 465         goto out;
 466 }
 467
 468 int ebitmap_write(struct ebitmap *e, void *fp)
 469 {
 470         struct ebitmap_node *n;
 471         u32 count;
 472         __le32 buf[3];
 473         u64 map;
 474         int bit, last_bit, last_startbit, rc;
 475
 476         buf[0] = cpu_to_le32(BITS_PER_U64);
 477
 478         count = 0;
 479         last_bit = 0;
 480         last_startbit = -1;
 481         ebitmap_for_each_positive_bit(e, n, bit) {
 482                 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
 483                         count++;
 484                         last_startbit = rounddown(bit, BITS_PER_U64);
 485                 }
 486                 last_bit = roundup(bit + 1, BITS_PER_U64);
 487         }
 488         buf[1] = cpu_to_le32(last_bit);
 489         buf[2] = cpu_to_le32(count);
 490
 491         rc = put_entry(buf, sizeof(u32), 3, fp);
 492         if (rc)
 493                 return rc;
 494
 495         map = 0;
 496         last_startbit = INT_MIN;
 497         ebitmap_for_each_positive_bit(e, n, bit) {
 498                 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
 499                         __le64 buf64[1];
 500
 501                         /* this is the very first bit */
 502                         if (!map) {
 503                                 last_startbit = rounddown(bit, BITS_PER_U64);
 504                                 map = (u64)1 << (bit - last_startbit);
 505                                 continue;
 506                         }
 507
 508                         /* write the last node */
 509                         buf[0] = cpu_to_le32(last_startbit);
 510                         rc = put_entry(buf, sizeof(u32), 1, fp);
 511                         if (rc)
 512                                 return rc;
 513
 514                         buf64[0] = cpu_to_le64(map);
 515                         rc = put_entry(buf64, sizeof(u64), 1, fp);
 516                         if (rc)
 517                                 return rc;
 518
 519                         /* set up for the next node */
 520                         map = 0;
 521                         last_startbit = rounddown(bit, BITS_PER_U64);
 522                 }
 523                 map |= (u64)1 << (bit - last_startbit);
 524         }
 525         /* write the last node */
 526         if (map) {
 527                 __le64 buf64[1];
 528
 529                 /* write the last node */
 530                 buf[0] = cpu_to_le32(last_startbit);
 531                 rc = put_entry(buf, sizeof(u32), 1, fp);
 532                 if (rc)
 533                         return rc;
 534
 535                 buf64[0] = cpu_to_le64(map);
 536                 rc = put_entry(buf64, sizeof(u64), 1, fp);
 537                 if (rc)
 538                         return rc;
 539         }
 540         return 0;
 541 }