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_catmap **catmap)
  90 {
  91         struct ebitmap_node *e_iter = ebmap->node;
  92         unsigned long e_map;
  93         u32 offset;
  94         unsigned int iter;
  95         int rc;
  96
  97         if (e_iter == NULL) {
  98                 *catmap = NULL;
  99                 return 0;
 100         }
 101
 102         if (*catmap != NULL)
 103                 netlbl_catmap_free(*catmap);
 104         *catmap = NULL;
 105
 106         while (e_iter) {
 107                 offset = e_iter->startbit;
 108                 for (iter = 0; iter < EBITMAP_UNIT_NUMS; iter++) {
 109                         e_map = e_iter->maps[iter];
 110                         if (e_map != 0) {
 111                                 rc = netlbl_catmap_setlong(catmap,
 112                                                            offset,
 113                                                            e_map,
 114                                                            GFP_ATOMIC);
 115                                 if (rc != 0)
 116                                         goto netlbl_export_failure;
 117                         }
 118                         offset += EBITMAP_UNIT_SIZE;
 119                 }
 120                 e_iter = e_iter->next;
 121         }
 122
 123         return 0;
 124
 125 netlbl_export_failure:
 126         netlbl_catmap_free(*catmap);
 127         return -ENOMEM;
 128 }
 129
 130 /**
 131  * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
 132  * @ebmap: the ebitmap to import
 133  * @catmap: the NetLabel category bitmap
 134  *
 135  * Description:
 136  * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
 137  * Returns zero on success, negative values on error.
 138  *
 139  */
 140 int ebitmap_netlbl_import(struct ebitmap *ebmap,
 141                           struct netlbl_lsm_catmap *catmap)
 142 {
 143         int rc;
 144         struct ebitmap_node *e_iter = NULL;
 145         struct ebitmap_node *e_prev = NULL;
 146         u32 offset = 0, idx;
 147         unsigned long bitmap;
 148
 149         for (;;) {
 150                 rc = netlbl_catmap_getlong(catmap, &offset, &bitmap);
 151                 if (rc < 0)
 152                         goto netlbl_import_failure;
 153                 if (offset == (u32)-1)
 154                         return 0;
 155
 156                 /* don't waste ebitmap space if the netlabel bitmap is empty */
 157                 if (bitmap == 0) {
 158                         offset += EBITMAP_UNIT_SIZE;
 159                         continue;
 160                 }
 161
 162                 if (e_iter == NULL ||
 163                     offset >= e_iter->startbit + EBITMAP_SIZE) {
 164                         e_prev = e_iter;
 165                         e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC);
 166                         if (e_iter == NULL)
 167                                 goto netlbl_import_failure;
 168                         e_iter->startbit = offset - (offset % EBITMAP_SIZE);
 169                         if (e_prev == NULL)
 170                                 ebmap->node = e_iter;
 171                         else
 172                                 e_prev->next = e_iter;
 173                         ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
 174                 }
 175
 176                 /* offset will always be aligned to an unsigned long */
 177                 idx = EBITMAP_NODE_INDEX(e_iter, offset);
 178                 e_iter->maps[idx] = bitmap;
 179
 180                 /* next */
 181                 offset += EBITMAP_UNIT_SIZE;
 182         }
 183
 184         /* NOTE: we should never reach this return */
 185         return 0;
 186
 187 netlbl_import_failure:
 188         ebitmap_destroy(ebmap);
 189         return -ENOMEM;
 190 }
 191 #endif /* CONFIG_NETLABEL */
 192
 193 /*
 194  * Check to see if all the bits set in e2 are also set in e1. Optionally,
 195  * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed
 196  * last_e2bit.
 197  */
 198 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit)
 199 {
 200         struct ebitmap_node *n1, *n2;
 201         int i;
 202
 203         if (e1->highbit < e2->highbit)
 204                 return 0;
 205
 206         n1 = e1->node;
 207         n2 = e2->node;
 208
 209         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
 210                 if (n1->startbit < n2->startbit) {
 211                         n1 = n1->next;
 212                         continue;
 213                 }
 214                 for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; )
 215                         i--;    /* Skip trailing NULL map entries */
 216                 if (last_e2bit && (i >= 0)) {
 217                         u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE +
 218                                          __fls(n2->maps[i]);
 219                         if (lastsetbit > last_e2bit)
 220                                 return 0;
 221                 }
 222
 223                 while (i >= 0) {
 224                         if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
 225                                 return 0;
 226                         i--;
 227                 }
 228
 229                 n1 = n1->next;
 230                 n2 = n2->next;
 231         }
 232
 233         if (n2)
 234                 return 0;
 235
 236         return 1;
 237 }
 238
 239 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
 240 {
 241         struct ebitmap_node *n;
 242
 243         if (e->highbit < bit)
 244                 return 0;
 245
 246         n = e->node;
 247         while (n && (n->startbit <= bit)) {
 248                 if ((n->startbit + EBITMAP_SIZE) > bit)
 249                         return ebitmap_node_get_bit(n, bit);
 250                 n = n->next;
 251         }
 252
 253         return 0;
 254 }
 255
 256 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 257 {
 258         struct ebitmap_node *n, *prev, *new;
 259
 260         prev = NULL;
 261         n = e->node;
 262         while (n && n->startbit <= bit) {
 263                 if ((n->startbit + EBITMAP_SIZE) > bit) {
 264                         if (value) {
 265                                 ebitmap_node_set_bit(n, bit);
 266                         } else {
 267                                 unsigned int s;
 268
 269                                 ebitmap_node_clr_bit(n, bit);
 270
 271                                 s = find_first_bit(n->maps, EBITMAP_SIZE);
 272                                 if (s < EBITMAP_SIZE)
 273                                         return 0;
 274
 275                                 /* drop this node from the bitmap */
 276                                 if (!n->next) {
 277                                         /*
 278                                          * this was the highest map
 279                                          * within the bitmap
 280                                          */
 281                                         if (prev)
 282                                                 e->highbit = prev->startbit
 283                                                              + EBITMAP_SIZE;
 284                                         else
 285                                                 e->highbit = 0;
 286                                 }
 287                                 if (prev)
 288                                         prev->next = n->next;
 289                                 else
 290                                         e->node = n->next;
 291                                 kfree(n);
 292                         }
 293                         return 0;
 294                 }
 295                 prev = n;
 296                 n = n->next;
 297         }
 298
 299         if (!value)
 300                 return 0;
 301
 302         new = kzalloc(sizeof(*new), GFP_ATOMIC);
 303         if (!new)
 304                 return -ENOMEM;
 305
 306         new->startbit = bit - (bit % EBITMAP_SIZE);
 307         ebitmap_node_set_bit(new, bit);
 308
 309         if (!n)
 310                 /* this node will be the highest map within the bitmap */
 311                 e->highbit = new->startbit + EBITMAP_SIZE;
 312
 313         if (prev) {
 314                 new->next = prev->next;
 315                 prev->next = new;
 316         } else {
 317                 new->next = e->node;
 318                 e->node = new;
 319         }
 320
 321         return 0;
 322 }
 323
 324 void ebitmap_destroy(struct ebitmap *e)
 325 {
 326         struct ebitmap_node *n, *temp;
 327
 328         if (!e)
 329                 return;
 330
 331         n = e->node;
 332         while (n) {
 333                 temp = n;
 334                 n = n->next;
 335                 kfree(temp);
 336         }
 337
 338         e->highbit = 0;
 339         e->node = NULL;
 340         return;
 341 }
 342
 343 int ebitmap_read(struct ebitmap *e, void *fp)
 344 {
 345         struct ebitmap_node *n = NULL;
 346         u32 mapunit, count, startbit, index;
 347         u64 map;
 348         __le32 buf[3];
 349         int rc, i;
 350
 351         ebitmap_init(e);
 352
 353         rc = next_entry(buf, fp, sizeof buf);
 354         if (rc < 0)
 355                 goto out;
 356
 357         mapunit = le32_to_cpu(buf[0]);
 358         e->highbit = le32_to_cpu(buf[1]);
 359         count = le32_to_cpu(buf[2]);
 360
 361         if (mapunit != BITS_PER_U64) {
 362                 printk(KERN_ERR "SELinux: ebitmap: map size %u does not "
 363                        "match my size %Zd (high bit was %d)\n",
 364                        mapunit, BITS_PER_U64, e->highbit);
 365                 goto bad;
 366         }
 367
 368         /* round up e->highbit */
 369         e->highbit += EBITMAP_SIZE - 1;
 370         e->highbit -= (e->highbit % EBITMAP_SIZE);
 371
 372         if (!e->highbit) {
 373                 e->node = NULL;
 374                 goto ok;
 375         }
 376
 377         if (e->highbit && !count)
 378                 goto bad;
 379
 380         for (i = 0; i < count; i++) {
 381                 rc = next_entry(&startbit, fp, sizeof(u32));
 382                 if (rc < 0) {
 383                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
 384                         goto bad;
 385                 }
 386                 startbit = le32_to_cpu(startbit);
 387
 388                 if (startbit & (mapunit - 1)) {
 389                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
 390                                "not a multiple of the map unit size (%u)\n",
 391                                startbit, mapunit);
 392                         goto bad;
 393                 }
 394                 if (startbit > e->highbit - mapunit) {
 395                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
 396                                "beyond the end of the bitmap (%u)\n",
 397                                startbit, (e->highbit - mapunit));
 398                         goto bad;
 399                 }
 400
 401                 if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
 402                         struct ebitmap_node *tmp;
 403                         tmp = kzalloc(sizeof(*tmp), GFP_KERNEL);
 404                         if (!tmp) {
 405                                 printk(KERN_ERR
 406                                        "SELinux: ebitmap: out of memory\n");
 407                                 rc = -ENOMEM;
 408                                 goto bad;
 409                         }
 410                         /* round down */
 411                         tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
 412                         if (n)
 413                                 n->next = tmp;
 414                         else
 415                                 e->node = tmp;
 416                         n = tmp;
 417                 } else if (startbit <= n->startbit) {
 418                         printk(KERN_ERR "SELinux: ebitmap: start bit %d"
 419                                " comes after start bit %d\n",
 420                                startbit, n->startbit);
 421                         goto bad;
 422                 }
 423
 424                 rc = next_entry(&map, fp, sizeof(u64));
 425                 if (rc < 0) {
 426                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
 427                         goto bad;
 428                 }
 429                 map = le64_to_cpu(map);
 430
 431                 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
 432                 while (map) {
 433                         n->maps[index++] = map & (-1UL);
 434                         map = EBITMAP_SHIFT_UNIT_SIZE(map);
 435                 }
 436         }
 437 ok:
 438         rc = 0;
 439 out:
 440         return rc;
 441 bad:
 442         if (!rc)
 443                 rc = -EINVAL;
 444         ebitmap_destroy(e);
 445         goto out;
 446 }
 447
 448 int ebitmap_write(struct ebitmap *e, void *fp)
 449 {
 450         struct ebitmap_node *n;
 451         u32 count;
 452         __le32 buf[3];
 453         u64 map;
 454         int bit, last_bit, last_startbit, rc;
 455
 456         buf[0] = cpu_to_le32(BITS_PER_U64);
 457
 458         count = 0;
 459         last_bit = 0;
 460         last_startbit = -1;
 461         ebitmap_for_each_positive_bit(e, n, bit) {
 462                 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
 463                         count++;
 464                         last_startbit = rounddown(bit, BITS_PER_U64);
 465                 }
 466                 last_bit = roundup(bit + 1, BITS_PER_U64);
 467         }
 468         buf[1] = cpu_to_le32(last_bit);
 469         buf[2] = cpu_to_le32(count);
 470
 471         rc = put_entry(buf, sizeof(u32), 3, fp);
 472         if (rc)
 473                 return rc;
 474
 475         map = 0;
 476         last_startbit = INT_MIN;
 477         ebitmap_for_each_positive_bit(e, n, bit) {
 478                 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
 479                         __le64 buf64[1];
 480
 481                         /* this is the very first bit */
 482                         if (!map) {
 483                                 last_startbit = rounddown(bit, BITS_PER_U64);
 484                                 map = (u64)1 << (bit - last_startbit);
 485                                 continue;
 486                         }
 487
 488                         /* write the last node */
 489                         buf[0] = cpu_to_le32(last_startbit);
 490                         rc = put_entry(buf, sizeof(u32), 1, fp);
 491                         if (rc)
 492                                 return rc;
 493
 494                         buf64[0] = cpu_to_le64(map);
 495                         rc = put_entry(buf64, sizeof(u64), 1, fp);
 496                         if (rc)
 497                                 return rc;
 498
 499                         /* set up for the next node */
 500                         map = 0;
 501                         last_startbit = rounddown(bit, BITS_PER_U64);
 502                 }
 503                 map |= (u64)1 << (bit - last_startbit);
 504         }
 505         /* write the last node */
 506         if (map) {
 507                 __le64 buf64[1];
 508
 509                 /* write the last node */
 510                 buf[0] = cpu_to_le32(last_startbit);
 511                 rc = put_entry(buf, sizeof(u32), 1, fp);
 512                 if (rc)
 513                         return rc;
 514
 515                 buf64[0] = cpu_to_le64(map);
 516                 rc = put_entry(buf64, sizeof(u64), 1, fp);
 517                 if (rc)
 518                         return rc;
 519         }
 520         return 0;
 521 }