security/selinux/ss/ebitmap.c

   1 /*
   2  * Implementation of the extensible bitmap type.
   3  *
   4  * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
   5  */
   6 #include <linux/kernel.h>
   7 #include <linux/slab.h>
   8 #include <linux/errno.h>
   9 #include "ebitmap.h"
  10 #include "policydb.h"
  11
  12 int ebitmap_or(struct ebitmap *dst, struct ebitmap *e1, struct ebitmap *e2)
  13 {
  14         struct ebitmap_node *n1, *n2, *new, *prev;
  15
  16         ebitmap_init(dst);
  17
  18         n1 = e1->node;
  19         n2 = e2->node;
  20         prev = 0;
  21         while (n1 || n2) {
  22                 new = kmalloc(sizeof(*new), GFP_ATOMIC);
  23                 if (!new) {
  24                         ebitmap_destroy(dst);
  25                         return -ENOMEM;
  26                 }
  27                 memset(new, 0, sizeof(*new));
  28                 if (n1 && n2 && n1->startbit == n2->startbit) {
  29                         new->startbit = n1->startbit;
  30                         new->map = n1->map | n2->map;
  31                         n1 = n1->next;
  32                         n2 = n2->next;
  33                 } else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
  34                         new->startbit = n1->startbit;
  35                         new->map = n1->map;
  36                         n1 = n1->next;
  37                 } else {
  38                         new->startbit = n2->startbit;
  39                         new->map = n2->map;
  40                         n2 = n2->next;
  41                 }
  42
  43                 new->next = 0;
  44                 if (prev)
  45                         prev->next = new;
  46                 else
  47                         dst->node = new;
  48                 prev = new;
  49         }
  50
  51         dst->highbit = (e1->highbit > e2->highbit) ? e1->highbit : e2->highbit;
  52         return 0;
  53 }
  54
  55 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
  56 {
  57         struct ebitmap_node *n1, *n2;
  58
  59         if (e1->highbit != e2->highbit)
  60                 return 0;
  61
  62         n1 = e1->node;
  63         n2 = e2->node;
  64         while (n1 && n2 &&
  65                (n1->startbit == n2->startbit) &&
  66                (n1->map == n2->map)) {
  67                 n1 = n1->next;
  68                 n2 = n2->next;
  69         }
  70
  71         if (n1 || n2)
  72                 return 0;
  73
  74         return 1;
  75 }
  76
  77 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
  78 {
  79         struct ebitmap_node *n, *new, *prev;
  80
  81         ebitmap_init(dst);
  82         n = src->node;
  83         prev = 0;
  84         while (n) {
  85                 new = kmalloc(sizeof(*new), GFP_ATOMIC);
  86                 if (!new) {
  87                         ebitmap_destroy(dst);
  88                         return -ENOMEM;
  89                 }
  90                 memset(new, 0, sizeof(*new));
  91                 new->startbit = n->startbit;
  92                 new->map = n->map;
  93                 new->next = 0;
  94                 if (prev)
  95                         prev->next = new;
  96                 else
  97                         dst->node = new;
  98                 prev = new;
  99                 n = n->next;
 100         }
 101
 102         dst->highbit = src->highbit;
 103         return 0;
 104 }
 105
 106 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
 107 {
 108         struct ebitmap_node *n1, *n2;
 109
 110         if (e1->highbit < e2->highbit)
 111                 return 0;
 112
 113         n1 = e1->node;
 114         n2 = e2->node;
 115         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
 116                 if (n1->startbit < n2->startbit) {
 117                         n1 = n1->next;
 118                         continue;
 119                 }
 120                 if ((n1->map & n2->map) != n2->map)
 121                         return 0;
 122
 123                 n1 = n1->next;
 124                 n2 = n2->next;
 125         }
 126
 127         if (n2)
 128                 return 0;
 129
 130         return 1;
 131 }
 132
 133 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
 134 {
 135         struct ebitmap_node *n;
 136
 137         if (e->highbit < bit)
 138                 return 0;
 139
 140         n = e->node;
 141         while (n && (n->startbit <= bit)) {
 142                 if ((n->startbit + MAPSIZE) > bit) {
 143                         if (n->map & (MAPBIT << (bit - n->startbit)))
 144                                 return 1;
 145                         else
 146                                 return 0;
 147                 }
 148                 n = n->next;
 149         }
 150
 151         return 0;
 152 }
 153
 154 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
 155 {
 156         struct ebitmap_node *n, *prev, *new;
 157
 158         prev = 0;
 159         n = e->node;
 160         while (n && n->startbit <= bit) {
 161                 if ((n->startbit + MAPSIZE) > bit) {
 162                         if (value) {
 163                                 n->map |= (MAPBIT << (bit - n->startbit));
 164                         } else {
 165                                 n->map &= ~(MAPBIT << (bit - n->startbit));
 166                                 if (!n->map) {
 167                                         /* drop this node from the bitmap */
 168
 169                                         if (!n->next) {
 170                                                 /*
 171                                                  * this was the highest map
 172                                                  * within the bitmap
 173                                                  */
 174                                                 if (prev)
 175                                                         e->highbit = prev->startbit + MAPSIZE;
 176                                                 else
 177                                                         e->highbit = 0;
 178                                         }
 179                                         if (prev)
 180                                                 prev->next = n->next;
 181                                         else
 182                                                 e->node = n->next;
 183
 184                                         kfree(n);
 185                                 }
 186                         }
 187                         return 0;
 188                 }
 189                 prev = n;
 190                 n = n->next;
 191         }
 192
 193         if (!value)
 194                 return 0;
 195
 196         new = kmalloc(sizeof(*new), GFP_ATOMIC);
 197         if (!new)
 198                 return -ENOMEM;
 199         memset(new, 0, sizeof(*new));
 200
 201         new->startbit = bit & ~(MAPSIZE - 1);
 202         new->map = (MAPBIT << (bit - new->startbit));
 203
 204         if (!n)
 205                 /* this node will be the highest map within the bitmap */
 206                 e->highbit = new->startbit + MAPSIZE;
 207
 208         if (prev) {
 209                 new->next = prev->next;
 210                 prev->next = new;
 211         } else {
 212                 new->next = e->node;
 213                 e->node = new;
 214         }
 215
 216         return 0;
 217 }
 218
 219 void ebitmap_destroy(struct ebitmap *e)
 220 {
 221         struct ebitmap_node *n, *temp;
 222
 223         if (!e)
 224                 return;
 225
 226         n = e->node;
 227         while (n) {
 228                 temp = n;
 229                 n = n->next;
 230                 kfree(temp);
 231         }
 232
 233         e->highbit = 0;
 234         e->node = 0;
 235         return;
 236 }
 237
 238 int ebitmap_read(struct ebitmap *e, void *fp)
 239 {
 240         int rc = -EINVAL;
 241         struct ebitmap_node *n, *l;
 242         u32 *buf, mapsize, count, i;
 243         u64 map;
 244
 245         ebitmap_init(e);
 246
 247         buf = next_entry(fp, sizeof(u32)*3);
 248         if (!buf)
 249                 goto out;
 250
 251         mapsize = le32_to_cpu(buf[0]);
 252         e->highbit = le32_to_cpu(buf[1]);
 253         count = le32_to_cpu(buf[2]);
 254
 255         if (mapsize != MAPSIZE) {
 256                 printk(KERN_ERR "security: ebitmap: map size %u does not "
 257                        "match my size %Zd (high bit was %d)\n", mapsize,
 258                        MAPSIZE, e->highbit);
 259                 goto out;
 260         }
 261         if (!e->highbit) {
 262                 e->node = NULL;
 263                 goto ok;
 264         }
 265         if (e->highbit & (MAPSIZE - 1)) {
 266                 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
 267                        "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
 268                 goto bad;
 269         }
 270         l = NULL;
 271         for (i = 0; i < count; i++) {
 272                 buf = next_entry(fp, sizeof(u32));
 273                 if (!buf) {
 274                         printk(KERN_ERR "security: ebitmap: truncated map\n");
 275                         goto bad;
 276                 }
 277                 n = kmalloc(sizeof(*n), GFP_KERNEL);
 278                 if (!n) {
 279                         printk(KERN_ERR "security: ebitmap: out of memory\n");
 280                         rc = -ENOMEM;
 281                         goto bad;
 282                 }
 283                 memset(n, 0, sizeof(*n));
 284
 285                 n->startbit = le32_to_cpu(buf[0]);
 286
 287                 if (n->startbit & (MAPSIZE - 1)) {
 288                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
 289                                "not a multiple of the map size (%Zd)\n",
 290                                n->startbit, MAPSIZE);
 291                         goto bad_free;
 292                 }
 293                 if (n->startbit > (e->highbit - MAPSIZE)) {
 294                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
 295                                "beyond the end of the bitmap (%Zd)\n",
 296                                n->startbit, (e->highbit - MAPSIZE));
 297                         goto bad_free;
 298                 }
 299                 buf = next_entry(fp, sizeof(u64));
 300                 if (!buf) {
 301                         printk(KERN_ERR "security: ebitmap: truncated map\n");
 302                         goto bad_free;
 303                 }
 304                 memcpy(&map, buf, sizeof(u64));
 305                 n->map = le64_to_cpu(map);
 306
 307                 if (!n->map) {
 308                         printk(KERN_ERR "security: ebitmap: null map in "
 309                                "ebitmap (startbit %d)\n", n->startbit);
 310                         goto bad_free;
 311                 }
 312                 if (l) {
 313                         if (n->startbit <= l->startbit) {
 314                                 printk(KERN_ERR "security: ebitmap: start "
 315                                        "bit %d comes after start bit %d\n",
 316                                        n->startbit, l->startbit);
 317                                 goto bad_free;
 318                         }
 319                         l->next = n;
 320                 } else
 321                         e->node = n;
 322
 323                 l = n;
 324         }
 325
 326 ok:
 327         rc = 0;
 328 out:
 329         return rc;
 330 bad_free:
 331         kfree(n);
 332 bad:
 333         ebitmap_destroy(e);
 334         goto out;
 335 }