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.moore@hp.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 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
  26 {
  27         struct ebitmap_node *n1, *n2;
  28
  29         if (e1->highbit != e2->highbit)
  30                 return 0;
  31
  32         n1 = e1->node;
  33         n2 = e2->node;
  34         while (n1 && n2 &&
  35                (n1->startbit == n2->startbit) &&
  36                !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
  37                 n1 = n1->next;
  38                 n2 = n2->next;
  39         }
  40
  41         if (n1 || n2)
  42                 return 0;
  43
  44         return 1;
  45 }
  46
  47 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
  48 {
  49         struct ebitmap_node *n, *new, *prev;
  50
  51         ebitmap_init(dst);
  52         n = src->node;
  53         prev = NULL;
  54         while (n) {
  55                 new = kzalloc(sizeof(*new), GFP_ATOMIC);
  56                 if (!new) {
  57                         ebitmap_destroy(dst);
  58                         return -ENOMEM;
  59                 }
  60                 new->startbit = n->startbit;
  61                 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
  62                 new->next = NULL;
  63                 if (prev)
  64                         prev->next = new;
  65                 else
  66                         dst->node = new;
  67                 prev = new;
  68                 n = n->next;
  69         }
  70
  71         dst->highbit = src->highbit;
  72         return 0;
  73 }
  74
  75 #ifdef CONFIG_NETLABEL
  76 /**
  77  * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap
  78  * @ebmap: the ebitmap to export
  79  * @catmap: the NetLabel category bitmap
  80  *
  81  * Description:
  82  * Export a SELinux extensibile bitmap into a NetLabel category bitmap.
  83  * Returns zero on success, negative values on error.
  84  *
  85  */
  86 int ebitmap_netlbl_export(struct ebitmap *ebmap,
  87                           struct netlbl_lsm_secattr_catmap **catmap)
  88 {
  89         struct ebitmap_node *e_iter = ebmap->node;
  90         struct netlbl_lsm_secattr_catmap *c_iter;
  91         u32 cmap_idx, cmap_sft;
  92         int i;
  93
  94         /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
  95          * however, it is not always compatible with an array of unsigned long
  96          * in ebitmap_node.
  97          * In addition, you should pay attention the following implementation
  98          * assumes unsigned long has a width equal with or less than 64-bit.
  99          */
 100
 101         if (e_iter == NULL) {
 102                 *catmap = NULL;
 103                 return 0;
 104         }
 105
 106         c_iter = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
 107         if (c_iter == NULL)
 108                 return -ENOMEM;
 109         *catmap = c_iter;
 110         c_iter->startbit = e_iter->startbit & ~(NETLBL_CATMAP_SIZE - 1);
 111
 112         while (e_iter != NULL) {
 113                 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
 114                         unsigned int delta, e_startbit, c_endbit;
 115
 116                         e_startbit = e_iter->startbit + i * EBITMAP_UNIT_SIZE;
 117                         c_endbit = c_iter->startbit + NETLBL_CATMAP_SIZE;
 118                         if (e_startbit >= c_endbit) {
 119                                 c_iter->next
 120                                   = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
 121                                 if (c_iter->next == NULL)
 122                                         goto netlbl_export_failure;
 123                                 c_iter = c_iter->next;
 124                                 c_iter->startbit
 125                                   = e_startbit & ~(NETLBL_CATMAP_SIZE - 1);
 126                         }
 127                         delta = e_startbit - c_iter->startbit;
 128                         cmap_idx = delta / NETLBL_CATMAP_MAPSIZE;
 129                         cmap_sft = delta % NETLBL_CATMAP_MAPSIZE;
 130                         c_iter->bitmap[cmap_idx]
 131                                 |= e_iter->maps[cmap_idx] << cmap_sft;
 132                 }
 133                 e_iter = e_iter->next;
 134         }
 135
 136         return 0;
 137
 138 netlbl_export_failure:
 139         netlbl_secattr_catmap_free(*catmap);
 140         return -ENOMEM;
 141 }
 142
 143 /**
 144  * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
 145  * @ebmap: the ebitmap to import
 146  * @catmap: the NetLabel category bitmap
 147  *
 148  * Description:
 149  * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
 150  * Returns zero on success, negative values on error.
 151  *
 152  */
 153 int ebitmap_netlbl_import(struct ebitmap *ebmap,
 154                           struct netlbl_lsm_secattr_catmap *catmap)
 155 {
 156         struct ebitmap_node *e_iter = NULL;
 157         struct ebitmap_node *emap_prev = NULL;
 158         struct netlbl_lsm_secattr_catmap *c_iter = catmap;
 159         u32 c_idx, c_pos, e_idx, e_sft;
 160
 161         /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
 162          * however, it is not always compatible with an array of unsigned long
 163          * in ebitmap_node.
 164          * In addition, you should pay attention the following implementation
 165          * assumes unsigned long has a width equal with or less than 64-bit.
 166          */
 167
 168         do {
 169                 for (c_idx = 0; c_idx < NETLBL_CATMAP_MAPCNT; c_idx++) {
 170                         unsigned int delta;
 171                         u64 map = c_iter->bitmap[c_idx];
 172
 173                         if (!map)
 174                                 continue;
 175
 176                         c_pos = c_iter->startbit
 177                                 + c_idx * NETLBL_CATMAP_MAPSIZE;
 178                         if (!e_iter
 179                             || c_pos >= e_iter->startbit + EBITMAP_SIZE) {
 180                                 e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC);
 181                                 if (!e_iter)
 182                                         goto netlbl_import_failure;
 183                                 e_iter->startbit
 184                                         = c_pos - (c_pos % EBITMAP_SIZE);
 185                                 if (emap_prev == NULL)
 186                                         ebmap->node = e_iter;
 187                                 else
 188                                         emap_prev->next = e_iter;
 189                                 emap_prev = e_iter;
 190                         }
 191                         delta = c_pos - e_iter->startbit;
 192                         e_idx = delta / EBITMAP_UNIT_SIZE;
 193                         e_sft = delta % EBITMAP_UNIT_SIZE;
 194                         while (map) {
 195                                 e_iter->maps[e_idx++] |= map & (-1UL);
 196                                 map = EBITMAP_SHIFT_UNIT_SIZE(map);
 197                         }
 198                 }
 199                 c_iter = c_iter->next;
 200         } while (c_iter != NULL);
 201         if (e_iter != NULL)
 202                 ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
 203         else
 204                 ebitmap_destroy(ebmap);
 205
 206         return 0;
 207
 208 netlbl_import_failure:
 209         ebitmap_destroy(ebmap);
 210         return -ENOMEM;
 211 }
 212 #endif /* CONFIG_NETLABEL */
 213
 214 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
 215 {
 216         struct ebitmap_node *n1, *n2;
 217         int i;
 218
 219         if (e1->highbit < e2->highbit)
 220                 return 0;
 221
 222         n1 = e1->node;
 223         n2 = e2->node;
 224         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
 225                 if (n1->startbit < n2->startbit) {
 226                         n1 = n1->next;
 227                         continue;
 228                 }
 229                 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
 230                         if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
 231                                 return 0;
 232                 }
 233
 234                 n1 = n1->next;
 235                 n2 = n2->next;
 236         }
 237
 238         if (n2)
 239                 return 0;
 240
 241         return 1;
 242 }
 243
 244 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
 245 {
 246         struct ebitmap_node *n;
 247
 248         if (e->highbit < bit)
 249                 return 0;
 250
 251         n = e->node;
 252         while (n && (n->startbit <= bit)) {
 253                 if ((n->startbit + EBITMAP_SIZE) > bit)
 254                         return ebitmap_node_get_bit(n, bit);
 255                 n = n->next;
 256         }
 257
 258         return 0;
 259 }
 260
 261 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 262 {
 263         struct ebitmap_node *n, *prev, *new;
 264
 265         prev = NULL;
 266         n = e->node;
 267         while (n && n->startbit <= bit) {
 268                 if ((n->startbit + EBITMAP_SIZE) > bit) {
 269                         if (value) {
 270                                 ebitmap_node_set_bit(n, bit);
 271                         } else {
 272                                 unsigned int s;
 273
 274                                 ebitmap_node_clr_bit(n, bit);
 275
 276                                 s = find_first_bit(n->maps, EBITMAP_SIZE);
 277                                 if (s < EBITMAP_SIZE)
 278                                         return 0;
 279
 280                                 /* drop this node from the bitmap */
 281                                 if (!n->next) {
 282                                         /*
 283                                          * this was the highest map
 284                                          * within the bitmap
 285                                          */
 286                                         if (prev)
 287                                                 e->highbit = prev->startbit
 288                                                              + EBITMAP_SIZE;
 289                                         else
 290                                                 e->highbit = 0;
 291                                 }
 292                                 if (prev)
 293                                         prev->next = n->next;
 294                                 else
 295                                         e->node = n->next;
 296                                 kfree(n);
 297                         }
 298                         return 0;
 299                 }
 300                 prev = n;
 301                 n = n->next;
 302         }
 303
 304         if (!value)
 305                 return 0;
 306
 307         new = kzalloc(sizeof(*new), GFP_ATOMIC);
 308         if (!new)
 309                 return -ENOMEM;
 310
 311         new->startbit = bit - (bit % EBITMAP_SIZE);
 312         ebitmap_node_set_bit(new, bit);
 313
 314         if (!n)
 315                 /* this node will be the highest map within the bitmap */
 316                 e->highbit = new->startbit + EBITMAP_SIZE;
 317
 318         if (prev) {
 319                 new->next = prev->next;
 320                 prev->next = new;
 321         } else {
 322                 new->next = e->node;
 323                 e->node = new;
 324         }
 325
 326         return 0;
 327 }
 328
 329 void ebitmap_destroy(struct ebitmap *e)
 330 {
 331         struct ebitmap_node *n, *temp;
 332
 333         if (!e)
 334                 return;
 335
 336         n = e->node;
 337         while (n) {
 338                 temp = n;
 339                 n = n->next;
 340                 kfree(temp);
 341         }
 342
 343         e->highbit = 0;
 344         e->node = NULL;
 345         return;
 346 }
 347
 348 int ebitmap_read(struct ebitmap *e, void *fp)
 349 {
 350         struct ebitmap_node *n = NULL;
 351         u32 mapunit, count, startbit, index;
 352         u64 map;
 353         __le32 buf[3];
 354         int rc, i;
 355
 356         ebitmap_init(e);
 357
 358         rc = next_entry(buf, fp, sizeof buf);
 359         if (rc < 0)
 360                 goto out;
 361
 362         mapunit = le32_to_cpu(buf[0]);
 363         e->highbit = le32_to_cpu(buf[1]);
 364         count = le32_to_cpu(buf[2]);
 365
 366         if (mapunit != sizeof(u64) * 8) {
 367                 printk(KERN_ERR "security: ebitmap: map size %u does not "
 368                        "match my size %Zd (high bit was %d)\n",
 369                        mapunit, sizeof(u64) * 8, e->highbit);
 370                 goto bad;
 371         }
 372
 373         /* round up e->highbit */
 374         e->highbit += EBITMAP_SIZE - 1;
 375         e->highbit -= (e->highbit % EBITMAP_SIZE);
 376
 377         if (!e->highbit) {
 378                 e->node = NULL;
 379                 goto ok;
 380         }
 381
 382         for (i = 0; i < count; i++) {
 383                 rc = next_entry(&startbit, fp, sizeof(u32));
 384                 if (rc < 0) {
 385                         printk(KERN_ERR "security: ebitmap: truncated map\n");
 386                         goto bad;
 387                 }
 388                 startbit = le32_to_cpu(startbit);
 389
 390                 if (startbit & (mapunit - 1)) {
 391                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
 392                                "not a multiple of the map unit size (%u)\n",
 393                                startbit, mapunit);
 394                         goto bad;
 395                 }
 396                 if (startbit > e->highbit - mapunit) {
 397                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
 398                                "beyond the end of the bitmap (%u)\n",
 399                                startbit, (e->highbit - mapunit));
 400                         goto bad;
 401                 }
 402
 403                 if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
 404                         struct ebitmap_node *tmp;
 405                         tmp = kzalloc(sizeof(*tmp), GFP_KERNEL);
 406                         if (!tmp) {
 407                                 printk(KERN_ERR
 408                                        "security: ebitmap: out of memory\n");
 409                                 rc = -ENOMEM;
 410                                 goto bad;
 411                         }
 412                         /* round down */
 413                         tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
 414                         if (n) {
 415                                 n->next = tmp;
 416                         } else {
 417                                 e->node = tmp;
 418                         }
 419                         n = tmp;
 420                 } else if (startbit <= n->startbit) {
 421                         printk(KERN_ERR "security: ebitmap: start bit %d"
 422                                " comes after start bit %d\n",
 423                                startbit, n->startbit);
 424                         goto bad;
 425                 }
 426
 427                 rc = next_entry(&map, fp, sizeof(u64));
 428                 if (rc < 0) {
 429                         printk(KERN_ERR "security: ebitmap: truncated map\n");
 430                         goto bad;
 431                 }
 432                 map = le64_to_cpu(map);
 433
 434                 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
 435                 while (map) {
 436                         n->maps[index++] = map & (-1UL);
 437                         map = EBITMAP_SHIFT_UNIT_SIZE(map);
 438                 }
 439         }
 440 ok:
 441         rc = 0;
 442 out:
 443         return rc;
 444 bad:
 445         if (!rc)
 446                 rc = -EINVAL;
 447         ebitmap_destroy(e);
 448         goto out;
 449 }