linux/security/selinux/ss/ebitmap.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Implementation of the extensible bitmap type.
   4 *
   5 * Author : Stephen Smalley, <sds@tycho.nsa.gov>
   6 */
   7/*
   8 * Updated: Hewlett-Packard <paul@paul-moore.com>
   9 *
  10 *      Added support to import/export the NetLabel category bitmap
  11 *
  12 * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
  13 */
  14/*
  15 * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com>
  16 *      Applied standard bit operations to improve bitmap scanning.
  17 */
  18
  19#include <linux/kernel.h>
  20#include <linux/slab.h>
  21#include <linux/errno.h>
  22#include <linux/jhash.h>
  23#include <net/netlabel.h>
  24#include "ebitmap.h"
  25#include "policydb.h"
  26
  27#define BITS_PER_U64    (sizeof(u64) * 8)
  28
  29static struct kmem_cache *ebitmap_node_cachep __ro_after_init;
  30
  31int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
  32{
  33        struct ebitmap_node *n1, *n2;
  34
  35        if (e1->highbit != e2->highbit)
  36                return 0;
  37
  38        n1 = e1->node;
  39        n2 = e2->node;
  40        while (n1 && n2 &&
  41               (n1->startbit == n2->startbit) &&
  42               !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
  43                n1 = n1->next;
  44                n2 = n2->next;
  45        }
  46
  47        if (n1 || n2)
  48                return 0;
  49
  50        return 1;
  51}
  52
  53int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
  54{
  55        struct ebitmap_node *n, *new, *prev;
  56
  57        ebitmap_init(dst);
  58        n = src->node;
  59        prev = NULL;
  60        while (n) {
  61                new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
  62                if (!new) {
  63                        ebitmap_destroy(dst);
  64                        return -ENOMEM;
  65                }
  66                new->startbit = n->startbit;
  67                memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
  68                new->next = NULL;
  69                if (prev)
  70                        prev->next = new;
  71                else
  72                        dst->node = new;
  73                prev = new;
  74                n = n->next;
  75        }
  76
  77        dst->highbit = src->highbit;
  78        return 0;
  79}
  80
  81int ebitmap_and(struct ebitmap *dst, struct ebitmap *e1, struct ebitmap *e2)
  82{
  83        struct ebitmap_node *n;
  84        int bit, rc;
  85
  86        ebitmap_init(dst);
  87
  88        ebitmap_for_each_positive_bit(e1, n, bit) {
  89                if (ebitmap_get_bit(e2, bit)) {
  90                        rc = ebitmap_set_bit(dst, bit, 1);
  91                        if (rc < 0)
  92                                return rc;
  93                }
  94        }
  95        return 0;
  96}
  97
  98
  99#ifdef CONFIG_NETLABEL
 100/**
 101 * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap
 102 * @ebmap: the ebitmap to export
 103 * @catmap: the NetLabel category bitmap
 104 *
 105 * Description:
 106 * Export a SELinux extensibile bitmap into a NetLabel category bitmap.
 107 * Returns zero on success, negative values on error.
 108 *
 109 */
 110int ebitmap_netlbl_export(struct ebitmap *ebmap,
 111                          struct netlbl_lsm_catmap **catmap)
 112{
 113        struct ebitmap_node *e_iter = ebmap->node;
 114        unsigned long e_map;
 115        u32 offset;
 116        unsigned int iter;
 117        int rc;
 118
 119        if (e_iter == NULL) {
 120                *catmap = NULL;
 121                return 0;
 122        }
 123
 124        if (*catmap != NULL)
 125                netlbl_catmap_free(*catmap);
 126        *catmap = NULL;
 127
 128        while (e_iter) {
 129                offset = e_iter->startbit;
 130                for (iter = 0; iter < EBITMAP_UNIT_NUMS; iter++) {
 131                        e_map = e_iter->maps[iter];
 132                        if (e_map != 0) {
 133                                rc = netlbl_catmap_setlong(catmap,
 134                                                           offset,
 135                                                           e_map,
 136                                                           GFP_ATOMIC);
 137                                if (rc != 0)
 138                                        goto netlbl_export_failure;
 139                        }
 140                        offset += EBITMAP_UNIT_SIZE;
 141                }
 142                e_iter = e_iter->next;
 143        }
 144
 145        return 0;
 146
 147netlbl_export_failure:
 148        netlbl_catmap_free(*catmap);
 149        return -ENOMEM;
 150}
 151
 152/**
 153 * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
 154 * @ebmap: the ebitmap to import
 155 * @catmap: the NetLabel category bitmap
 156 *
 157 * Description:
 158 * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
 159 * Returns zero on success, negative values on error.
 160 *
 161 */
 162int ebitmap_netlbl_import(struct ebitmap *ebmap,
 163                          struct netlbl_lsm_catmap *catmap)
 164{
 165        int rc;
 166        struct ebitmap_node *e_iter = NULL;
 167        struct ebitmap_node *e_prev = NULL;
 168        u32 offset = 0, idx;
 169        unsigned long bitmap;
 170
 171        for (;;) {
 172                rc = netlbl_catmap_getlong(catmap, &offset, &bitmap);
 173                if (rc < 0)
 174                        goto netlbl_import_failure;
 175                if (offset == (u32)-1)
 176                        return 0;
 177
 178                /* don't waste ebitmap space if the netlabel bitmap is empty */
 179                if (bitmap == 0) {
 180                        offset += EBITMAP_UNIT_SIZE;
 181                        continue;
 182                }
 183
 184                if (e_iter == NULL ||
 185                    offset >= e_iter->startbit + EBITMAP_SIZE) {
 186                        e_prev = e_iter;
 187                        e_iter = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
 188                        if (e_iter == NULL)
 189                                goto netlbl_import_failure;
 190                        e_iter->startbit = offset - (offset % EBITMAP_SIZE);
 191                        if (e_prev == NULL)
 192                                ebmap->node = e_iter;
 193                        else
 194                                e_prev->next = e_iter;
 195                        ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
 196                }
 197
 198                /* offset will always be aligned to an unsigned long */
 199                idx = EBITMAP_NODE_INDEX(e_iter, offset);
 200                e_iter->maps[idx] = bitmap;
 201
 202                /* next */
 203                offset += EBITMAP_UNIT_SIZE;
 204        }
 205
 206        /* NOTE: we should never reach this return */
 207        return 0;
 208
 209netlbl_import_failure:
 210        ebitmap_destroy(ebmap);
 211        return -ENOMEM;
 212}
 213#endif /* CONFIG_NETLABEL */
 214
 215/*
 216 * Check to see if all the bits set in e2 are also set in e1. Optionally,
 217 * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed
 218 * last_e2bit.
 219 */
 220int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit)
 221{
 222        struct ebitmap_node *n1, *n2;
 223        int i;
 224
 225        if (e1->highbit < e2->highbit)
 226                return 0;
 227
 228        n1 = e1->node;
 229        n2 = e2->node;
 230
 231        while (n1 && n2 && (n1->startbit <= n2->startbit)) {
 232                if (n1->startbit < n2->startbit) {
 233                        n1 = n1->next;
 234                        continue;
 235                }
 236                for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; )
 237                        i--;    /* Skip trailing NULL map entries */
 238                if (last_e2bit && (i >= 0)) {
 239                        u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE +
 240                                         __fls(n2->maps[i]);
 241                        if (lastsetbit > last_e2bit)
 242                                return 0;
 243                }
 244
 245                while (i >= 0) {
 246                        if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
 247                                return 0;
 248                        i--;
 249                }
 250
 251                n1 = n1->next;
 252                n2 = n2->next;
 253        }
 254
 255        if (n2)
 256                return 0;
 257
 258        return 1;
 259}
 260
 261int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
 262{
 263        struct ebitmap_node *n;
 264
 265        if (e->highbit < bit)
 266                return 0;
 267
 268        n = e->node;
 269        while (n && (n->startbit <= bit)) {
 270                if ((n->startbit + EBITMAP_SIZE) > bit)
 271                        return ebitmap_node_get_bit(n, bit);
 272                n = n->next;
 273        }
 274
 275        return 0;
 276}
 277
 278int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 279{
 280        struct ebitmap_node *n, *prev, *new;
 281
 282        prev = NULL;
 283        n = e->node;
 284        while (n && n->startbit <= bit) {
 285                if ((n->startbit + EBITMAP_SIZE) > bit) {
 286                        if (value) {
 287                                ebitmap_node_set_bit(n, bit);
 288                        } else {
 289                                unsigned int s;
 290
 291                                ebitmap_node_clr_bit(n, bit);
 292
 293                                s = find_first_bit(n->maps, EBITMAP_SIZE);
 294                                if (s < EBITMAP_SIZE)
 295                                        return 0;
 296
 297                                /* drop this node from the bitmap */
 298                                if (!n->next) {
 299                                        /*
 300                                         * this was the highest map
 301                                         * within the bitmap
 302                                         */
 303                                        if (prev)
 304                                                e->highbit = prev->startbit
 305                                                             + EBITMAP_SIZE;
 306                                        else
 307                                                e->highbit = 0;
 308                                }
 309                                if (prev)
 310                                        prev->next = n->next;
 311                                else
 312                                        e->node = n->next;
 313                                kmem_cache_free(ebitmap_node_cachep, n);
 314                        }
 315                        return 0;
 316                }
 317                prev = n;
 318                n = n->next;
 319        }
 320
 321        if (!value)
 322                return 0;
 323
 324        new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
 325        if (!new)
 326                return -ENOMEM;
 327
 328        new->startbit = bit - (bit % EBITMAP_SIZE);
 329        ebitmap_node_set_bit(new, bit);
 330
 331        if (!n)
 332                /* this node will be the highest map within the bitmap */
 333                e->highbit = new->startbit + EBITMAP_SIZE;
 334
 335        if (prev) {
 336                new->next = prev->next;
 337                prev->next = new;
 338        } else {
 339                new->next = e->node;
 340                e->node = new;
 341        }
 342
 343        return 0;
 344}
 345
 346void ebitmap_destroy(struct ebitmap *e)
 347{
 348        struct ebitmap_node *n, *temp;
 349
 350        if (!e)
 351                return;
 352
 353        n = e->node;
 354        while (n) {
 355                temp = n;
 356                n = n->next;
 357                kmem_cache_free(ebitmap_node_cachep, temp);
 358        }
 359
 360        e->highbit = 0;
 361        e->node = NULL;
 362}
 363
 364int ebitmap_read(struct ebitmap *e, void *fp)
 365{
 366        struct ebitmap_node *n = NULL;
 367        u32 mapunit, count, startbit, index;
 368        __le32 ebitmap_start;
 369        u64 map;
 370        __le64 mapbits;
 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                pr_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        if (e->highbit && !count)
 401                goto bad;
 402
 403        for (i = 0; i < count; i++) {
 404                rc = next_entry(&ebitmap_start, fp, sizeof(u32));
 405                if (rc < 0) {
 406                        pr_err("SELinux: ebitmap: truncated map\n");
 407                        goto bad;
 408                }
 409                startbit = le32_to_cpu(ebitmap_start);
 410
 411                if (startbit & (mapunit - 1)) {
 412                        pr_err("SELinux: ebitmap start bit (%d) is "
 413                               "not a multiple of the map unit size (%u)\n",
 414                               startbit, mapunit);
 415                        goto bad;
 416                }
 417                if (startbit > e->highbit - mapunit) {
 418                        pr_err("SELinux: ebitmap start bit (%d) is "
 419                               "beyond the end of the bitmap (%u)\n",
 420                               startbit, (e->highbit - mapunit));
 421                        goto bad;
 422                }
 423
 424                if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
 425                        struct ebitmap_node *tmp;
 426                        tmp = kmem_cache_zalloc(ebitmap_node_cachep, GFP_KERNEL);
 427                        if (!tmp) {
 428                                pr_err("SELinux: ebitmap: out of memory\n");
 429                                rc = -ENOMEM;
 430                                goto bad;
 431                        }
 432                        /* round down */
 433                        tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
 434                        if (n)
 435                                n->next = tmp;
 436                        else
 437                                e->node = tmp;
 438                        n = tmp;
 439                } else if (startbit <= n->startbit) {
 440                        pr_err("SELinux: ebitmap: start bit %d"
 441                               " comes after start bit %d\n",
 442                               startbit, n->startbit);
 443                        goto bad;
 444                }
 445
 446                rc = next_entry(&mapbits, fp, sizeof(u64));
 447                if (rc < 0) {
 448                        pr_err("SELinux: ebitmap: truncated map\n");
 449                        goto bad;
 450                }
 451                map = le64_to_cpu(mapbits);
 452
 453                index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
 454                while (map) {
 455                        n->maps[index++] = map & (-1UL);
 456                        map = EBITMAP_SHIFT_UNIT_SIZE(map);
 457                }
 458        }
 459ok:
 460        rc = 0;
 461out:
 462        return rc;
 463bad:
 464        if (!rc)
 465                rc = -EINVAL;
 466        ebitmap_destroy(e);
 467        goto out;
 468}
 469
 470int ebitmap_write(struct ebitmap *e, void *fp)
 471{
 472        struct ebitmap_node *n;
 473        u32 count;
 474        __le32 buf[3];
 475        u64 map;
 476        int bit, last_bit, last_startbit, rc;
 477
 478        buf[0] = cpu_to_le32(BITS_PER_U64);
 479
 480        count = 0;
 481        last_bit = 0;
 482        last_startbit = -1;
 483        ebitmap_for_each_positive_bit(e, n, bit) {
 484                if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
 485                        count++;
 486                        last_startbit = rounddown(bit, BITS_PER_U64);
 487                }
 488                last_bit = roundup(bit + 1, BITS_PER_U64);
 489        }
 490        buf[1] = cpu_to_le32(last_bit);
 491        buf[2] = cpu_to_le32(count);
 492
 493        rc = put_entry(buf, sizeof(u32), 3, fp);
 494        if (rc)
 495                return rc;
 496
 497        map = 0;
 498        last_startbit = INT_MIN;
 499        ebitmap_for_each_positive_bit(e, n, bit) {
 500                if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
 501                        __le64 buf64[1];
 502
 503                        /* this is the very first bit */
 504                        if (!map) {
 505                                last_startbit = rounddown(bit, BITS_PER_U64);
 506                                map = (u64)1 << (bit - last_startbit);
 507                                continue;
 508                        }
 509
 510                        /* write the last node */
 511                        buf[0] = cpu_to_le32(last_startbit);
 512                        rc = put_entry(buf, sizeof(u32), 1, fp);
 513                        if (rc)
 514                                return rc;
 515
 516                        buf64[0] = cpu_to_le64(map);
 517                        rc = put_entry(buf64, sizeof(u64), 1, fp);
 518                        if (rc)
 519                                return rc;
 520
 521                        /* set up for the next node */
 522                        map = 0;
 523                        last_startbit = rounddown(bit, BITS_PER_U64);
 524                }
 525                map |= (u64)1 << (bit - last_startbit);
 526        }
 527        /* write the last node */
 528        if (map) {
 529                __le64 buf64[1];
 530
 531                /* write the last node */
 532                buf[0] = cpu_to_le32(last_startbit);
 533                rc = put_entry(buf, sizeof(u32), 1, fp);
 534                if (rc)
 535                        return rc;
 536
 537                buf64[0] = cpu_to_le64(map);
 538                rc = put_entry(buf64, sizeof(u64), 1, fp);
 539                if (rc)
 540                        return rc;
 541        }
 542        return 0;
 543}
 544
 545u32 ebitmap_hash(const struct ebitmap *e, u32 hash)
 546{
 547        struct ebitmap_node *node;
 548
 549        /* need to change hash even if ebitmap is empty */
 550        hash = jhash_1word(e->highbit, hash);
 551        for (node = e->node; node; node = node->next) {
 552                hash = jhash_1word(node->startbit, hash);
 553                hash = jhash(node->maps, sizeof(node->maps), hash);
 554        }
 555        return hash;
 556}
 557
 558void __init ebitmap_cache_init(void)
 559{
 560        ebitmap_node_cachep = kmem_cache_create("ebitmap_node",
 561                                                        sizeof(struct ebitmap_node),
 562                                                        0, SLAB_PANIC, NULL);
 563}
 564