git.oblomov.eu Git - linux-2.6/blob - 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         size_t node_limit;
 149         struct ebitmap_node *node_new;
 150         struct ebitmap_node *node_last = NULL;
 151         u32 i_byte;
 152         u32 i_bit;
 153         unsigned char src_byte;
 154
 155         while (src_off < src_len) {
 156                 if (src_len - src_off >= sizeof(MAPTYPE)) {
 157                         if (*(MAPTYPE *)&src[src_off] == 0) {
 158                                 src_off += sizeof(MAPTYPE);
 159                                 continue;
 160                         }
 161                         node_limit = sizeof(MAPTYPE);
 162                 } else {
 163                         for (src_byte = 0, i_byte = src_off;
 164                              i_byte < src_len && src_byte == 0;
 165                              i_byte++)
 166                                 src_byte |= src[i_byte];
 167                         if (src_byte == 0)
 168                                 break;
 169                         node_limit = src_len - src_off;
 170                 }
 171
 172                 node_new = kzalloc(sizeof(*node_new), GFP_ATOMIC);
 173                 if (unlikely(node_new == NULL)) {
 174                         ebitmap_destroy(dst);
 175                         return -ENOMEM;
 176                 }
 177                 node_new->startbit = src_off * 8;
 178                 for (i_byte = 0; i_byte < node_limit; i_byte++) {
 179                         src_byte = src[src_off++];
 180                         for (i_bit = i_byte * 8; src_byte != 0; i_bit++) {
 181                                 if (src_byte & 0x80)
 182                                         node_new->map |= MAPBIT << i_bit;
 183                                 src_byte <<= 1;
 184                         }
 185                 }
 186
 187                 if (node_last != NULL)
 188                         node_last->next = node_new;
 189                 else
 190                         dst->node = node_new;
 191                 node_last = node_new;
 192         }
 193
 194         if (likely(node_last != NULL))
 195                 dst->highbit = node_last->startbit + MAPSIZE;
 196         else
 197                 ebitmap_init(dst);
 198
 199         return 0;
 200 }
 201
 202 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
 203 {
 204         struct ebitmap_node *n1, *n2;
 205
 206         if (e1->highbit < e2->highbit)
 207                 return 0;
 208
 209         n1 = e1->node;
 210         n2 = e2->node;
 211         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
 212                 if (n1->startbit < n2->startbit) {
 213                         n1 = n1->next;
 214                         continue;
 215                 }
 216                 if ((n1->map & n2->map) != n2->map)
 217                         return 0;
 218
 219                 n1 = n1->next;
 220                 n2 = n2->next;
 221         }
 222
 223         if (n2)
 224                 return 0;
 225
 226         return 1;
 227 }
 228
 229 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
 230 {
 231         struct ebitmap_node *n;
 232
 233         if (e->highbit < bit)
 234                 return 0;
 235
 236         n = e->node;
 237         while (n && (n->startbit <= bit)) {
 238                 if ((n->startbit + MAPSIZE) > bit) {
 239                         if (n->map & (MAPBIT << (bit - n->startbit)))
 240                                 return 1;
 241                         else
 242                                 return 0;
 243                 }
 244                 n = n->next;
 245         }
 246
 247         return 0;
 248 }
 249
 250 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 251 {
 252         struct ebitmap_node *n, *prev, *new;
 253
 254         prev = NULL;
 255         n = e->node;
 256         while (n && n->startbit <= bit) {
 257                 if ((n->startbit + MAPSIZE) > bit) {
 258                         if (value) {
 259                                 n->map |= (MAPBIT << (bit - n->startbit));
 260                         } else {
 261                                 n->map &= ~(MAPBIT << (bit - n->startbit));
 262                                 if (!n->map) {
 263                                         /* drop this node from the bitmap */
 264
 265                                         if (!n->next) {
 266                                                 /*
 267                                                  * this was the highest map
 268                                                  * within the bitmap
 269                                                  */
 270                                                 if (prev)
 271                                                         e->highbit = prev->startbit + MAPSIZE;
 272                                                 else
 273                                                         e->highbit = 0;
 274                                         }
 275                                         if (prev)
 276                                                 prev->next = n->next;
 277                                         else
 278                                                 e->node = n->next;
 279
 280                                         kfree(n);
 281                                 }
 282                         }
 283                         return 0;
 284                 }
 285                 prev = n;
 286                 n = n->next;
 287         }
 288
 289         if (!value)
 290                 return 0;
 291
 292         new = kzalloc(sizeof(*new), GFP_ATOMIC);
 293         if (!new)
 294                 return -ENOMEM;
 295
 296         new->startbit = bit & ~(MAPSIZE - 1);
 297         new->map = (MAPBIT << (bit - new->startbit));
 298
 299         if (!n)
 300                 /* this node will be the highest map within the bitmap */
 301                 e->highbit = new->startbit + MAPSIZE;
 302
 303         if (prev) {
 304                 new->next = prev->next;
 305                 prev->next = new;
 306         } else {
 307                 new->next = e->node;
 308                 e->node = new;
 309         }
 310
 311         return 0;
 312 }
 313
 314 void ebitmap_destroy(struct ebitmap *e)
 315 {
 316         struct ebitmap_node *n, *temp;
 317
 318         if (!e)
 319                 return;
 320
 321         n = e->node;
 322         while (n) {
 323                 temp = n;
 324                 n = n->next;
 325                 kfree(temp);
 326         }
 327
 328         e->highbit = 0;
 329         e->node = NULL;
 330         return;
 331 }
 332
 333 int ebitmap_read(struct ebitmap *e, void *fp)
 334 {
 335         int rc;
 336         struct ebitmap_node *n, *l;
 337         __le32 buf[3];
 338         u32 mapsize, count, i;
 339         __le64 map;
 340
 341         ebitmap_init(e);
 342
 343         rc = next_entry(buf, fp, sizeof buf);
 344         if (rc < 0)
 345                 goto out;
 346
 347         mapsize = le32_to_cpu(buf[0]);
 348         e->highbit = le32_to_cpu(buf[1]);
 349         count = le32_to_cpu(buf[2]);
 350
 351         if (mapsize != MAPSIZE) {
 352                 printk(KERN_ERR "security: ebitmap: map size %u does not "
 353                        "match my size %Zd (high bit was %d)\n", mapsize,
 354                        MAPSIZE, e->highbit);
 355                 goto bad;
 356         }
 357         if (!e->highbit) {
 358                 e->node = NULL;
 359                 goto ok;
 360         }
 361         if (e->highbit & (MAPSIZE - 1)) {
 362                 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
 363                        "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
 364                 goto bad;
 365         }
 366         l = NULL;
 367         for (i = 0; i < count; i++) {
 368                 rc = next_entry(buf, fp, sizeof(u32));
 369                 if (rc < 0) {
 370                         printk(KERN_ERR "security: ebitmap: truncated map\n");
 371                         goto bad;
 372                 }
 373                 n = kzalloc(sizeof(*n), GFP_KERNEL);
 374                 if (!n) {
 375                         printk(KERN_ERR "security: ebitmap: out of memory\n");
 376                         rc = -ENOMEM;
 377                         goto bad;
 378                 }
 379
 380                 n->startbit = le32_to_cpu(buf[0]);
 381
 382                 if (n->startbit & (MAPSIZE - 1)) {
 383                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
 384                                "not a multiple of the map size (%Zd)\n",
 385                                n->startbit, MAPSIZE);
 386                         goto bad_free;
 387                 }
 388                 if (n->startbit > (e->highbit - MAPSIZE)) {
 389                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
 390                                "beyond the end of the bitmap (%Zd)\n",
 391                                n->startbit, (e->highbit - MAPSIZE));
 392                         goto bad_free;
 393                 }
 394                 rc = next_entry(&map, fp, sizeof(u64));
 395                 if (rc < 0) {
 396                         printk(KERN_ERR "security: ebitmap: truncated map\n");
 397                         goto bad_free;
 398                 }
 399                 n->map = le64_to_cpu(map);
 400
 401                 if (!n->map) {
 402                         printk(KERN_ERR "security: ebitmap: null map in "
 403                                "ebitmap (startbit %d)\n", n->startbit);
 404                         goto bad_free;
 405                 }
 406                 if (l) {
 407                         if (n->startbit <= l->startbit) {
 408                                 printk(KERN_ERR "security: ebitmap: start "
 409                                        "bit %d comes after start bit %d\n",
 410                                        n->startbit, l->startbit);
 411                                 goto bad_free;
 412                         }
 413                         l->next = n;
 414                 } else
 415                         e->node = n;
 416
 417                 l = n;
 418         }
 419
 420 ok:
 421         rc = 0;
 422 out:
 423         return rc;
 424 bad_free:
 425         kfree(n);
 426 bad:
 427         if (!rc)
 428                 rc = -EINVAL;
 429         ebitmap_destroy(e);
 430         goto out;
 431 }