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