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