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 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
 217 {
 218         struct ebitmap_node *n1, *n2;
 219         int i;
 220
 221         if (e1->highbit < e2->highbit)
 222                 return 0;
 223
 224         n1 = e1->node;
 225         n2 = e2->node;
 226         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
 227                 if (n1->startbit < n2->startbit) {
 228                         n1 = n1->next;
 229                         continue;
 230                 }
 231                 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
 232                         if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
 233                                 return 0;
 234                 }
 235
 236                 n1 = n1->next;
 237                 n2 = n2->next;
 238         }
 239
 240         if (n2)
 241                 return 0;
 242
 243         return 1;
 244 }
 245
 246 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
 247 {
 248         struct ebitmap_node *n;
 249
 250         if (e->highbit < bit)
 251                 return 0;
 252
 253         n = e->node;
 254         while (n && (n->startbit <= bit)) {
 255                 if ((n->startbit + EBITMAP_SIZE) > bit)
 256                         return ebitmap_node_get_bit(n, bit);
 257                 n = n->next;
 258         }
 259
 260         return 0;
 261 }
 262
 263 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 264 {
 265         struct ebitmap_node *n, *prev, *new;
 266
 267         prev = NULL;
 268         n = e->node;
 269         while (n && n->startbit <= bit) {
 270                 if ((n->startbit + EBITMAP_SIZE) > bit) {
 271                         if (value) {
 272                                 ebitmap_node_set_bit(n, bit);
 273                         } else {
 274                                 unsigned int s;
 275
 276                                 ebitmap_node_clr_bit(n, bit);
 277
 278                                 s = find_first_bit(n->maps, EBITMAP_SIZE);
 279                                 if (s < EBITMAP_SIZE)
 280                                         return 0;
 281
 282                                 /* drop this node from the bitmap */
 283                                 if (!n->next) {
 284                                         /*
 285                                          * this was the highest map
 286                                          * within the bitmap
 287                                          */
 288                                         if (prev)
 289                                                 e->highbit = prev->startbit
 290                                                              + EBITMAP_SIZE;
 291                                         else
 292                                                 e->highbit = 0;
 293                                 }
 294                                 if (prev)
 295                                         prev->next = n->next;
 296                                 else
 297                                         e->node = n->next;
 298                                 kfree(n);
 299                         }
 300                         return 0;
 301                 }
 302                 prev = n;
 303                 n = n->next;
 304         }
 305
 306         if (!value)
 307                 return 0;
 308
 309         new = kzalloc(sizeof(*new), GFP_ATOMIC);
 310         if (!new)
 311                 return -ENOMEM;
 312
 313         new->startbit = bit - (bit % EBITMAP_SIZE);
 314         ebitmap_node_set_bit(new, bit);
 315
 316         if (!n)
 317                 /* this node will be the highest map within the bitmap */
 318                 e->highbit = new->startbit + EBITMAP_SIZE;
 319
 320         if (prev) {
 321                 new->next = prev->next;
 322                 prev->next = new;
 323         } else {
 324                 new->next = e->node;
 325                 e->node = new;
 326         }
 327
 328         return 0;
 329 }
 330
 331 void ebitmap_destroy(struct ebitmap *e)
 332 {
 333         struct ebitmap_node *n, *temp;
 334
 335         if (!e)
 336                 return;
 337
 338         n = e->node;
 339         while (n) {
 340                 temp = n;
 341                 n = n->next;
 342                 kfree(temp);
 343         }
 344
 345         e->highbit = 0;
 346         e->node = NULL;
 347         return;
 348 }
 349
 350 int ebitmap_read(struct ebitmap *e, void *fp)
 351 {
 352         struct ebitmap_node *n = NULL;
 353         u32 mapunit, count, startbit, index;
 354         u64 map;
 355         __le32 buf[3];
 356         int rc, i;
 357
 358         ebitmap_init(e);
 359
 360         rc = next_entry(buf, fp, sizeof buf);
 361         if (rc < 0)
 362                 goto out;
 363
 364         mapunit = le32_to_cpu(buf[0]);
 365         e->highbit = le32_to_cpu(buf[1]);
 366         count = le32_to_cpu(buf[2]);
 367
 368         if (mapunit != BITS_PER_U64) {
 369                 printk(KERN_ERR "SELinux: ebitmap: map size %u does not "
 370                        "match my size %Zd (high bit was %d)\n",
 371                        mapunit, BITS_PER_U64, e->highbit);
 372                 goto bad;
 373         }
 374
 375         /* round up e->highbit */
 376         e->highbit += EBITMAP_SIZE - 1;
 377         e->highbit -= (e->highbit % EBITMAP_SIZE);
 378
 379         if (!e->highbit) {
 380                 e->node = NULL;
 381                 goto ok;
 382         }
 383
 384         for (i = 0; i < count; i++) {
 385                 rc = next_entry(&startbit, fp, sizeof(u32));
 386                 if (rc < 0) {
 387                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
 388                         goto bad;
 389                 }
 390                 startbit = le32_to_cpu(startbit);
 391
 392                 if (startbit & (mapunit - 1)) {
 393                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
 394                                "not a multiple of the map unit size (%u)\n",
 395                                startbit, mapunit);
 396                         goto bad;
 397                 }
 398                 if (startbit > e->highbit - mapunit) {
 399                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
 400                                "beyond the end of the bitmap (%u)\n",
 401                                startbit, (e->highbit - mapunit));
 402                         goto bad;
 403                 }
 404
 405                 if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
 406                         struct ebitmap_node *tmp;
 407                         tmp = kzalloc(sizeof(*tmp), GFP_KERNEL);
 408                         if (!tmp) {
 409                                 printk(KERN_ERR
 410                                        "SELinux: ebitmap: out of memory\n");
 411                                 rc = -ENOMEM;
 412                                 goto bad;
 413                         }
 414                         /* round down */
 415                         tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
 416                         if (n)
 417                                 n->next = tmp;
 418                         else
 419                                 e->node = tmp;
 420                         n = tmp;
 421                 } else if (startbit <= n->startbit) {
 422                         printk(KERN_ERR "SELinux: ebitmap: start bit %d"
 423                                " comes after start bit %d\n",
 424                                startbit, n->startbit);
 425                         goto bad;
 426                 }
 427
 428                 rc = next_entry(&map, fp, sizeof(u64));
 429                 if (rc < 0) {
 430                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
 431                         goto bad;
 432                 }
 433                 map = le64_to_cpu(map);
 434
 435                 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
 436                 while (map) {
 437                         n->maps[index++] = map & (-1UL);
 438                         map = EBITMAP_SHIFT_UNIT_SIZE(map);
 439                 }
 440         }
 441 ok:
 442         rc = 0;
 443 out:
 444         return rc;
 445 bad:
 446         if (!rc)
 447                 rc = -EINVAL;
 448         ebitmap_destroy(e);
 449         goto out;
 450 }
 451
 452 int ebitmap_write(struct ebitmap *e, void *fp)
 453 {
 454         struct ebitmap_node *n;
 455         u32 count;
 456         __le32 buf[3];
 457         u64 map;
 458         int bit, last_bit, last_startbit, rc;
 459
 460         buf[0] = cpu_to_le32(BITS_PER_U64);
 461
 462         count = 0;
 463         last_bit = 0;
 464         last_startbit = -1;
 465         ebitmap_for_each_positive_bit(e, n, bit) {
 466                 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
 467                         count++;
 468                         last_startbit = rounddown(bit, BITS_PER_U64);
 469                 }
 470                 last_bit = roundup(bit + 1, BITS_PER_U64);
 471         }
 472         buf[1] = cpu_to_le32(last_bit);
 473         buf[2] = cpu_to_le32(count);
 474
 475         rc = put_entry(buf, sizeof(u32), 3, fp);
 476         if (rc)
 477                 return rc;
 478
 479         map = 0;
 480         last_startbit = INT_MIN;
 481         ebitmap_for_each_positive_bit(e, n, bit) {
 482                 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
 483                         __le64 buf64[1];
 484
 485                         /* this is the very first bit */
 486                         if (!map) {
 487                                 last_startbit = rounddown(bit, BITS_PER_U64);
 488                                 map = (u64)1 << (bit - last_startbit);
 489                                 continue;
 490                         }
 491
 492                         /* write the last node */
 493                         buf[0] = cpu_to_le32(last_startbit);
 494                         rc = put_entry(buf, sizeof(u32), 1, fp);
 495                         if (rc)
 496                                 return rc;
 497
 498                         buf64[0] = cpu_to_le64(map);
 499                         rc = put_entry(buf64, sizeof(u64), 1, fp);
 500                         if (rc)
 501                                 return rc;
 502
 503                         /* set up for the next node */
 504                         map = 0;
 505                         last_startbit = rounddown(bit, BITS_PER_U64);
 506                 }
 507                 map |= (u64)1 << (bit - last_startbit);
 508         }
 509         /* write the last node */
 510         if (map) {
 511                 __le64 buf64[1];
 512
 513                 /* write the last node */
 514                 buf[0] = cpu_to_le32(last_startbit);
 515                 rc = put_entry(buf, sizeof(u32), 1, fp);
 516                 if (rc)
 517                         return rc;
 518
 519                 buf64[0] = cpu_to_le64(map);
 520                 rc = put_entry(buf64, sizeof(u64), 1, fp);
 521                 if (rc)
 522                         return rc;
 523         }
 524         return 0;
 525 }