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 ebitmap_export() and ebitmap_import()
  10  *
  11  * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
  12  */
  13
  14 #include <linux/kernel.h>
  15 #include <linux/slab.h>
  16 #include <linux/errno.h>
  17 #include "ebitmap.h"
  18 #include "policydb.h"
  19
  20 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
  21 {
  22         struct ebitmap_node *n1, *n2;
  23
  24         if (e1->highbit != e2->highbit)
  25                 return 0;
  26
  27         n1 = e1->node;
  28         n2 = e2->node;
  29         while (n1 && n2 &&
  30                (n1->startbit == n2->startbit) &&
  31                (n1->map == n2->map)) {
  32                 n1 = n1->next;
  33                 n2 = n2->next;
  34         }
  35
  36         if (n1 || n2)
  37                 return 0;
  38
  39         return 1;
  40 }
  41
  42 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
  43 {
  44         struct ebitmap_node *n, *new, *prev;
  45
  46         ebitmap_init(dst);
  47         n = src->node;
  48         prev = NULL;
  49         while (n) {
  50                 new = kzalloc(sizeof(*new), GFP_ATOMIC);
  51                 if (!new) {
  52                         ebitmap_destroy(dst);
  53                         return -ENOMEM;
  54                 }
  55                 new->startbit = n->startbit;
  56                 new->map = n->map;
  57                 new->next = NULL;
  58                 if (prev)
  59                         prev->next = new;
  60                 else
  61                         dst->node = new;
  62                 prev = new;
  63                 n = n->next;
  64         }
  65
  66         dst->highbit = src->highbit;
  67         return 0;
  68 }
  69
  70 /**
  71  * ebitmap_export - Export an ebitmap to a unsigned char bitmap string
  72  * @src: the ebitmap to export
  73  * @dst: the resulting bitmap string
  74  * @dst_len: length of dst in bytes
  75  *
  76  * Description:
  77  * Allocate a buffer at least src->highbit bits long and export the extensible
  78  * bitmap into the buffer.  The bitmap string will be in little endian format,
  79  * i.e. LSB first.  The value returned in dst_len may not the true size of the
  80  * buffer as the length of the buffer is rounded up to a multiple of MAPTYPE.
  81  * The caller must free the buffer when finished. Returns zero on success,
  82  * negative values on failure.
  83  *
  84  */
  85 int ebitmap_export(const struct ebitmap *src,
  86                    unsigned char **dst,
  87                    size_t *dst_len)
  88 {
  89         size_t bitmap_len;
  90         unsigned char *bitmap;
  91         struct ebitmap_node *iter_node;
  92         MAPTYPE node_val;
  93         size_t bitmap_byte;
  94         unsigned char bitmask;
  95
  96         bitmap_len = src->highbit / 8;
  97         if (src->highbit % 7)
  98                 bitmap_len += 1;
  99         if (bitmap_len == 0)
 100                 return -EINVAL;
 101
 102         bitmap = kzalloc((bitmap_len & ~(sizeof(MAPTYPE) - 1)) +
 103                          sizeof(MAPTYPE),
 104                          GFP_ATOMIC);
 105         if (bitmap == NULL)
 106                 return -ENOMEM;
 107
 108         iter_node = src->node;
 109         do {
 110                 bitmap_byte = iter_node->startbit / 8;
 111                 bitmask = 0x80;
 112                 node_val = iter_node->map;
 113                 do {
 114                         if (bitmask == 0) {
 115                                 bitmap_byte++;
 116                                 bitmask = 0x80;
 117                         }
 118                         if (node_val & (MAPTYPE)0x01)
 119                                 bitmap[bitmap_byte] |= bitmask;
 120                         node_val >>= 1;
 121                         bitmask >>= 1;
 122                 } while (node_val > 0);
 123                 iter_node = iter_node->next;
 124         } while (iter_node);
 125
 126         *dst = bitmap;
 127         *dst_len = bitmap_len;
 128         return 0;
 129 }
 130
 131 /**
 132  * ebitmap_import - Import an unsigned char bitmap string into an ebitmap
 133  * @src: the bitmap string
 134  * @src_len: the bitmap length in bytes
 135  * @dst: the empty ebitmap
 136  *
 137  * Description:
 138  * This function takes a little endian bitmap string in src and imports it into
 139  * the ebitmap pointed to by dst.  Returns zero on success, negative values on
 140  * failure.
 141  *
 142  */
 143 int ebitmap_import(const unsigned char *src,
 144                    size_t src_len,
 145                    struct ebitmap *dst)
 146 {
 147         size_t src_off = 0;
 148         struct ebitmap_node *node_new;
 149         struct ebitmap_node *node_last = NULL;
 150         size_t iter;
 151         size_t iter_bit;
 152         size_t iter_limit;
 153         unsigned char src_byte;
 154
 155         do {
 156                 iter_limit = src_len - src_off;
 157                 if (iter_limit >= sizeof(MAPTYPE)) {
 158                         if (*(MAPTYPE *)&src[src_off] == 0) {
 159                                 src_off += sizeof(MAPTYPE);
 160                                 continue;
 161                         }
 162                         iter_limit = sizeof(MAPTYPE);
 163                 } else {
 164                         iter = src_off;
 165                         src_byte = 0;
 166                         do {
 167                                 src_byte |= src[iter++];
 168                         } while (iter < src_len && src_byte == 0);
 169                         if (src_byte == 0)
 170                                 break;
 171                 }
 172
 173                 node_new = kzalloc(sizeof(*node_new), GFP_ATOMIC);
 174                 if (unlikely(node_new == NULL)) {
 175                         ebitmap_destroy(dst);
 176                         return -ENOMEM;
 177                 }
 178                 node_new->startbit = src_off * 8;
 179                 iter = 0;
 180                 do {
 181                         src_byte = src[src_off++];
 182                         iter_bit = iter++ * 8;
 183                         while (src_byte != 0) {
 184                                 if (src_byte & 0x80)
 185                                         node_new->map |= MAPBIT << iter_bit;
 186                                 iter_bit++;
 187                                 src_byte <<= 1;
 188                         }
 189                 } while (iter < iter_limit);
 190
 191                 if (node_last != NULL)
 192                         node_last->next = node_new;
 193                 else
 194                         dst->node = node_new;
 195                 node_last = node_new;
 196         } while (src_off < src_len);
 197
 198         if (likely(node_last != NULL))
 199                 dst->highbit = node_last->startbit + MAPSIZE;
 200         else
 201                 ebitmap_init(dst);
 202
 203         return 0;
 204 }
 205
 206 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
 207 {
 208         struct ebitmap_node *n1, *n2;
 209
 210         if (e1->highbit < e2->highbit)
 211                 return 0;
 212
 213         n1 = e1->node;
 214         n2 = e2->node;
 215         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
 216                 if (n1->startbit < n2->startbit) {
 217                         n1 = n1->next;
 218                         continue;
 219                 }
 220                 if ((n1->map & n2->map) != n2->map)
 221                         return 0;
 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 + MAPSIZE) > bit) {
 243                         if (n->map & (MAPBIT << (bit - n->startbit)))
 244                                 return 1;
 245                         else
 246                                 return 0;
 247                 }
 248                 n = n->next;
 249         }
 250
 251         return 0;
 252 }
 253
 254 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 255 {
 256         struct ebitmap_node *n, *prev, *new;
 257
 258         prev = NULL;
 259         n = e->node;
 260         while (n && n->startbit <= bit) {
 261                 if ((n->startbit + MAPSIZE) > bit) {
 262                         if (value) {
 263                                 n->map |= (MAPBIT << (bit - n->startbit));
 264                         } else {
 265                                 n->map &= ~(MAPBIT << (bit - n->startbit));
 266                                 if (!n->map) {
 267                                         /* drop this node from the bitmap */
 268
 269                                         if (!n->next) {
 270                                                 /*
 271                                                  * this was the highest map
 272                                                  * within the bitmap
 273                                                  */
 274                                                 if (prev)
 275                                                         e->highbit = prev->startbit + MAPSIZE;
 276                                                 else
 277                                                         e->highbit = 0;
 278                                         }
 279                                         if (prev)
 280                                                 prev->next = n->next;
 281                                         else
 282                                                 e->node = n->next;
 283
 284                                         kfree(n);
 285                                 }
 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 & ~(MAPSIZE - 1);
 301         new->map = (MAPBIT << (bit - new->startbit));
 302
 303         if (!n)
 304                 /* this node will be the highest map within the bitmap */
 305                 e->highbit = new->startbit + MAPSIZE;
 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         int rc;
 340         struct ebitmap_node *n, *l;
 341         __le32 buf[3];
 342         u32 mapsize, count, i;
 343         __le64 map;
 344
 345         ebitmap_init(e);
 346
 347         rc = next_entry(buf, fp, sizeof buf);
 348         if (rc < 0)
 349                 goto out;
 350
 351         mapsize = le32_to_cpu(buf[0]);
 352         e->highbit = le32_to_cpu(buf[1]);
 353         count = le32_to_cpu(buf[2]);
 354
 355         if (mapsize != MAPSIZE) {
 356                 printk(KERN_ERR "security: ebitmap: map size %u does not "
 357                        "match my size %Zd (high bit was %d)\n", mapsize,
 358                        MAPSIZE, e->highbit);
 359                 goto bad;
 360         }
 361         if (!e->highbit) {
 362                 e->node = NULL;
 363                 goto ok;
 364         }
 365         if (e->highbit & (MAPSIZE - 1)) {
 366                 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
 367                        "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
 368                 goto bad;
 369         }
 370         l = NULL;
 371         for (i = 0; i < count; i++) {
 372                 rc = next_entry(buf, fp, sizeof(u32));
 373                 if (rc < 0) {
 374                         printk(KERN_ERR "security: ebitmap: truncated map\n");
 375                         goto bad;
 376                 }
 377                 n = kzalloc(sizeof(*n), GFP_KERNEL);
 378                 if (!n) {
 379                         printk(KERN_ERR "security: ebitmap: out of memory\n");
 380                         rc = -ENOMEM;
 381                         goto bad;
 382                 }
 383
 384                 n->startbit = le32_to_cpu(buf[0]);
 385
 386                 if (n->startbit & (MAPSIZE - 1)) {
 387                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
 388                                "not a multiple of the map size (%Zd)\n",
 389                                n->startbit, MAPSIZE);
 390                         goto bad_free;
 391                 }
 392                 if (n->startbit > (e->highbit - MAPSIZE)) {
 393                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
 394                                "beyond the end of the bitmap (%Zd)\n",
 395                                n->startbit, (e->highbit - MAPSIZE));
 396                         goto bad_free;
 397                 }
 398                 rc = next_entry(&map, fp, sizeof(u64));
 399                 if (rc < 0) {
 400                         printk(KERN_ERR "security: ebitmap: truncated map\n");
 401                         goto bad_free;
 402                 }
 403                 n->map = le64_to_cpu(map);
 404
 405                 if (!n->map) {
 406                         printk(KERN_ERR "security: ebitmap: null map in "
 407                                "ebitmap (startbit %d)\n", n->startbit);
 408                         goto bad_free;
 409                 }
 410                 if (l) {
 411                         if (n->startbit <= l->startbit) {
 412                                 printk(KERN_ERR "security: ebitmap: start "
 413                                        "bit %d comes after start bit %d\n",
 414                                        n->startbit, l->startbit);
 415                                 goto bad_free;
 416                         }
 417                         l->next = n;
 418                 } else
 419                         e->node = n;
 420
 421                 l = n;
 422         }
 423
 424 ok:
 425         rc = 0;
 426 out:
 427         return rc;
 428 bad_free:
 429         kfree(n);
 430 bad:
 431         if (!rc)
 432                 rc = -EINVAL;
 433         ebitmap_destroy(e);
 434         goto out;
 435 }