linux/security/selinux/ss/ebitmap.c
<<
>>
Prefs
   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
  27int 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
  49int 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 */
  88int 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
 125netlbl_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 */
 140int 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
 187netlbl_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 */
 198int 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
 239int 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
 256int 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
 324void 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
 343int 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        }
 437ok:
 438        rc = 0;
 439out:
 440        return rc;
 441bad:
 442        if (!rc)
 443                rc = -EINVAL;
 444        ebitmap_destroy(e);
 445        goto out;
 446}
 447
 448int 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}
 522