Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Implementation of the extensible bitmap type. |
| 3 | * |
| 4 | * Author : Stephen Smalley, <sds@epoch.ncsc.mil> |
| 5 | */ |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 6 | /* |
Paul Moore | 82c21bf | 2011-08-01 11:10:33 +0000 | [diff] [blame] | 7 | * Updated: Hewlett-Packard <paul@paul-moore.com> |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 8 | * |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 9 | * Added support to import/export the NetLabel category bitmap |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 10 | * |
| 11 | * (c) Copyright Hewlett-Packard Development Company, L.P., 2006 |
| 12 | */ |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 13 | /* |
| 14 | * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com> |
| 15 | * Applied standard bit operations to improve bitmap scanning. |
| 16 | */ |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 17 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 18 | #include <linux/kernel.h> |
| 19 | #include <linux/slab.h> |
| 20 | #include <linux/errno.h> |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 21 | #include <net/netlabel.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 22 | #include "ebitmap.h" |
| 23 | #include "policydb.h" |
| 24 | |
Eric Paris | cee74f4 | 2010-10-13 17:50:25 -0400 | [diff] [blame] | 25 | #define BITS_PER_U64 (sizeof(u64) * 8) |
| 26 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 27 | int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2) |
| 28 | { |
| 29 | struct ebitmap_node *n1, *n2; |
| 30 | |
| 31 | if (e1->highbit != e2->highbit) |
| 32 | return 0; |
| 33 | |
| 34 | n1 = e1->node; |
| 35 | n2 = e2->node; |
| 36 | while (n1 && n2 && |
| 37 | (n1->startbit == n2->startbit) && |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 38 | !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 39 | n1 = n1->next; |
| 40 | n2 = n2->next; |
| 41 | } |
| 42 | |
| 43 | if (n1 || n2) |
| 44 | return 0; |
| 45 | |
| 46 | return 1; |
| 47 | } |
| 48 | |
| 49 | int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src) |
| 50 | { |
| 51 | struct ebitmap_node *n, *new, *prev; |
| 52 | |
| 53 | ebitmap_init(dst); |
| 54 | n = src->node; |
| 55 | prev = NULL; |
| 56 | while (n) { |
James Morris | 89d155e | 2005-10-30 14:59:21 -0800 | [diff] [blame] | 57 | new = kzalloc(sizeof(*new), GFP_ATOMIC); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 58 | if (!new) { |
| 59 | ebitmap_destroy(dst); |
| 60 | return -ENOMEM; |
| 61 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 62 | new->startbit = n->startbit; |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 63 | memcpy(new->maps, n->maps, EBITMAP_SIZE / 8); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 64 | new->next = NULL; |
| 65 | if (prev) |
| 66 | prev->next = new; |
| 67 | else |
| 68 | dst->node = new; |
| 69 | prev = new; |
| 70 | n = n->next; |
| 71 | } |
| 72 | |
| 73 | dst->highbit = src->highbit; |
| 74 | return 0; |
| 75 | } |
| 76 | |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 77 | #ifdef CONFIG_NETLABEL |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 78 | /** |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 79 | * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap |
| 80 | * @ebmap: the ebitmap to export |
| 81 | * @catmap: the NetLabel category bitmap |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 82 | * |
| 83 | * Description: |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 84 | * Export a SELinux extensibile bitmap into a NetLabel category bitmap. |
| 85 | * Returns zero on success, negative values on error. |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 86 | * |
| 87 | */ |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 88 | int ebitmap_netlbl_export(struct ebitmap *ebmap, |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 89 | struct netlbl_lsm_catmap **catmap) |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 90 | { |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 91 | struct ebitmap_node *e_iter = ebmap->node; |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 92 | unsigned long e_map; |
| 93 | u32 offset; |
| 94 | unsigned int iter; |
| 95 | int rc; |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 96 | |
| 97 | if (e_iter == NULL) { |
| 98 | *catmap = NULL; |
Paul Moore | bf0edf3 | 2006-10-11 19:10:48 -0400 | [diff] [blame] | 99 | return 0; |
| 100 | } |
| 101 | |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 102 | if (*catmap != NULL) |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 103 | netlbl_catmap_free(*catmap); |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 104 | *catmap = NULL; |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 105 | |
Vesa-Matti Kari | dbc74c6 | 2008-08-07 03:18:20 +0300 | [diff] [blame] | 106 | while (e_iter) { |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 107 | offset = e_iter->startbit; |
| 108 | for (iter = 0; iter < EBITMAP_UNIT_NUMS; iter++) { |
| 109 | e_map = e_iter->maps[iter]; |
| 110 | if (e_map != 0) { |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 111 | rc = netlbl_catmap_setlong(catmap, |
| 112 | offset, |
| 113 | e_map, |
| 114 | GFP_ATOMIC); |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 115 | if (rc != 0) |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 116 | goto netlbl_export_failure; |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 117 | } |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 118 | offset += EBITMAP_UNIT_SIZE; |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 119 | } |
KaiGai Kohei | 6d2b685 | 2007-11-07 01:17:16 +0900 | [diff] [blame] | 120 | e_iter = e_iter->next; |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 121 | } |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 122 | |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 123 | return 0; |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 124 | |
| 125 | netlbl_export_failure: |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 126 | netlbl_catmap_free(*catmap); |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 127 | return -ENOMEM; |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 128 | } |
| 129 | |
| 130 | /** |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 131 | * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 132 | * @ebmap: the ebitmap to import |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 133 | * @catmap: the NetLabel category bitmap |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 134 | * |
| 135 | * Description: |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 136 | * Import a NetLabel category bitmap into a SELinux extensibile bitmap. |
| 137 | * Returns zero on success, negative values on error. |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 138 | * |
| 139 | */ |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 140 | int ebitmap_netlbl_import(struct ebitmap *ebmap, |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 141 | struct netlbl_lsm_catmap *catmap) |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 142 | { |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 143 | int rc; |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 144 | struct ebitmap_node *e_iter = NULL; |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 145 | struct ebitmap_node *e_prev = NULL; |
| 146 | u32 offset = 0, idx; |
| 147 | unsigned long bitmap; |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 148 | |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 149 | for (;;) { |
Paul Moore | 4fbe63d | 2014-08-01 11:17:37 -0400 | [diff] [blame] | 150 | rc = netlbl_catmap_getlong(catmap, &offset, &bitmap); |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 151 | if (rc < 0) |
| 152 | goto netlbl_import_failure; |
| 153 | if (offset == (u32)-1) |
| 154 | return 0; |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 155 | |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 156 | if (e_iter == NULL || |
| 157 | offset >= e_iter->startbit + EBITMAP_SIZE) { |
| 158 | e_prev = e_iter; |
| 159 | e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC); |
| 160 | if (e_iter == NULL) |
| 161 | goto netlbl_import_failure; |
| 162 | e_iter->startbit = offset & ~(EBITMAP_SIZE - 1); |
| 163 | if (e_prev == NULL) |
| 164 | ebmap->node = e_iter; |
| 165 | else |
| 166 | e_prev->next = e_iter; |
| 167 | ebmap->highbit = e_iter->startbit + EBITMAP_SIZE; |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 168 | } |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 169 | |
Paul Moore | 4b8feff | 2014-08-01 11:17:17 -0400 | [diff] [blame] | 170 | /* offset will always be aligned to an unsigned long */ |
| 171 | idx = EBITMAP_NODE_INDEX(e_iter, offset); |
| 172 | e_iter->maps[idx] = bitmap; |
| 173 | |
| 174 | /* next */ |
| 175 | offset += EBITMAP_UNIT_SIZE; |
| 176 | } |
| 177 | |
| 178 | /* NOTE: we should never reach this return */ |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 179 | return 0; |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 180 | |
| 181 | netlbl_import_failure: |
| 182 | ebitmap_destroy(ebmap); |
| 183 | return -ENOMEM; |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 184 | } |
Paul Moore | 0275276 | 2006-11-29 13:18:18 -0500 | [diff] [blame] | 185 | #endif /* CONFIG_NETLABEL */ |
Venkat Yekkirala | 7420ed2 | 2006-08-04 23:17:57 -0700 | [diff] [blame] | 186 | |
Waiman Long | fee7114 | 2013-07-23 17:38:41 -0400 | [diff] [blame] | 187 | /* |
| 188 | * Check to see if all the bits set in e2 are also set in e1. Optionally, |
| 189 | * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed |
| 190 | * last_e2bit. |
| 191 | */ |
| 192 | int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 193 | { |
| 194 | struct ebitmap_node *n1, *n2; |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 195 | int i; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 196 | |
| 197 | if (e1->highbit < e2->highbit) |
| 198 | return 0; |
| 199 | |
| 200 | n1 = e1->node; |
| 201 | n2 = e2->node; |
Waiman Long | fee7114 | 2013-07-23 17:38:41 -0400 | [diff] [blame] | 202 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 203 | while (n1 && n2 && (n1->startbit <= n2->startbit)) { |
| 204 | if (n1->startbit < n2->startbit) { |
| 205 | n1 = n1->next; |
| 206 | continue; |
| 207 | } |
Waiman Long | fee7114 | 2013-07-23 17:38:41 -0400 | [diff] [blame] | 208 | for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; ) |
| 209 | i--; /* Skip trailing NULL map entries */ |
| 210 | if (last_e2bit && (i >= 0)) { |
| 211 | u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE + |
| 212 | __fls(n2->maps[i]); |
| 213 | if (lastsetbit > last_e2bit) |
| 214 | return 0; |
| 215 | } |
| 216 | |
| 217 | while (i >= 0) { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 218 | if ((n1->maps[i] & n2->maps[i]) != n2->maps[i]) |
| 219 | return 0; |
Waiman Long | fee7114 | 2013-07-23 17:38:41 -0400 | [diff] [blame] | 220 | i--; |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 221 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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)) { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 242 | if ((n->startbit + EBITMAP_SIZE) > bit) |
| 243 | return ebitmap_node_get_bit(n, bit); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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) { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 257 | if ((n->startbit + EBITMAP_SIZE) > bit) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 258 | if (value) { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 259 | ebitmap_node_set_bit(n, bit); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 260 | } else { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 261 | unsigned int s; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 262 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 263 | ebitmap_node_clr_bit(n, bit); |
| 264 | |
| 265 | s = find_first_bit(n->maps, EBITMAP_SIZE); |
| 266 | if (s < EBITMAP_SIZE) |
| 267 | return 0; |
| 268 | |
| 269 | /* drop this node from the bitmap */ |
| 270 | if (!n->next) { |
| 271 | /* |
| 272 | * this was the highest map |
| 273 | * within the bitmap |
| 274 | */ |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 275 | if (prev) |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 276 | e->highbit = prev->startbit |
| 277 | + EBITMAP_SIZE; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 278 | else |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 279 | e->highbit = 0; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 280 | } |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 281 | if (prev) |
| 282 | prev->next = n->next; |
| 283 | else |
| 284 | e->node = n->next; |
| 285 | kfree(n); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 286 | } |
| 287 | return 0; |
| 288 | } |
| 289 | prev = n; |
| 290 | n = n->next; |
| 291 | } |
| 292 | |
| 293 | if (!value) |
| 294 | return 0; |
| 295 | |
James Morris | 89d155e | 2005-10-30 14:59:21 -0800 | [diff] [blame] | 296 | new = kzalloc(sizeof(*new), GFP_ATOMIC); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 297 | if (!new) |
| 298 | return -ENOMEM; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 299 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 300 | new->startbit = bit - (bit % EBITMAP_SIZE); |
| 301 | ebitmap_node_set_bit(new, bit); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 302 | |
| 303 | if (!n) |
| 304 | /* this node will be the highest map within the bitmap */ |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 305 | e->highbit = new->startbit + EBITMAP_SIZE; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 339 | struct ebitmap_node *n = NULL; |
| 340 | u32 mapunit, count, startbit, index; |
| 341 | u64 map; |
Alexey Dobriyan | b5bf6c5 | 2005-09-03 15:55:17 -0700 | [diff] [blame] | 342 | __le32 buf[3]; |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 343 | int rc, i; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 344 | |
| 345 | ebitmap_init(e); |
| 346 | |
| 347 | rc = next_entry(buf, fp, sizeof buf); |
| 348 | if (rc < 0) |
| 349 | goto out; |
| 350 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 351 | mapunit = le32_to_cpu(buf[0]); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 352 | e->highbit = le32_to_cpu(buf[1]); |
| 353 | count = le32_to_cpu(buf[2]); |
| 354 | |
Eric Paris | cee74f4 | 2010-10-13 17:50:25 -0400 | [diff] [blame] | 355 | if (mapunit != BITS_PER_U64) { |
James Morris | 454d972 | 2008-02-26 20:42:02 +1100 | [diff] [blame] | 356 | printk(KERN_ERR "SELinux: ebitmap: map size %u does not " |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 357 | "match my size %Zd (high bit was %d)\n", |
Eric Paris | cee74f4 | 2010-10-13 17:50:25 -0400 | [diff] [blame] | 358 | mapunit, BITS_PER_U64, e->highbit); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 359 | goto bad; |
| 360 | } |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 361 | |
| 362 | /* round up e->highbit */ |
| 363 | e->highbit += EBITMAP_SIZE - 1; |
| 364 | e->highbit -= (e->highbit % EBITMAP_SIZE); |
| 365 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 366 | if (!e->highbit) { |
| 367 | e->node = NULL; |
| 368 | goto ok; |
| 369 | } |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 370 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 371 | for (i = 0; i < count; i++) { |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 372 | rc = next_entry(&startbit, fp, sizeof(u32)); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 373 | if (rc < 0) { |
James Morris | 454d972 | 2008-02-26 20:42:02 +1100 | [diff] [blame] | 374 | printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 375 | goto bad; |
| 376 | } |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 377 | startbit = le32_to_cpu(startbit); |
| 378 | |
| 379 | if (startbit & (mapunit - 1)) { |
James Morris | 454d972 | 2008-02-26 20:42:02 +1100 | [diff] [blame] | 380 | printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " |
KaiGai Kohei | 087feb9 | 2007-10-03 23:42:56 +0900 | [diff] [blame] | 381 | "not a multiple of the map unit size (%u)\n", |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 382 | startbit, mapunit); |
| 383 | goto bad; |
| 384 | } |
| 385 | if (startbit > e->highbit - mapunit) { |
James Morris | 454d972 | 2008-02-26 20:42:02 +1100 | [diff] [blame] | 386 | printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " |
KaiGai Kohei | 087feb9 | 2007-10-03 23:42:56 +0900 | [diff] [blame] | 387 | "beyond the end of the bitmap (%u)\n", |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 388 | startbit, (e->highbit - mapunit)); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 389 | goto bad; |
| 390 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 391 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 392 | if (!n || startbit >= n->startbit + EBITMAP_SIZE) { |
| 393 | struct ebitmap_node *tmp; |
| 394 | tmp = kzalloc(sizeof(*tmp), GFP_KERNEL); |
| 395 | if (!tmp) { |
| 396 | printk(KERN_ERR |
James Morris | 454d972 | 2008-02-26 20:42:02 +1100 | [diff] [blame] | 397 | "SELinux: ebitmap: out of memory\n"); |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 398 | rc = -ENOMEM; |
| 399 | goto bad; |
| 400 | } |
| 401 | /* round down */ |
| 402 | tmp->startbit = startbit - (startbit % EBITMAP_SIZE); |
Eric Paris | 7696ee8 | 2008-04-18 17:38:30 -0400 | [diff] [blame] | 403 | if (n) |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 404 | n->next = tmp; |
Eric Paris | 7696ee8 | 2008-04-18 17:38:30 -0400 | [diff] [blame] | 405 | else |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 406 | e->node = tmp; |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 407 | n = tmp; |
| 408 | } else if (startbit <= n->startbit) { |
James Morris | 454d972 | 2008-02-26 20:42:02 +1100 | [diff] [blame] | 409 | printk(KERN_ERR "SELinux: ebitmap: start bit %d" |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 410 | " comes after start bit %d\n", |
| 411 | startbit, n->startbit); |
| 412 | goto bad; |
| 413 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 414 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 415 | rc = next_entry(&map, fp, sizeof(u64)); |
| 416 | if (rc < 0) { |
James Morris | 454d972 | 2008-02-26 20:42:02 +1100 | [diff] [blame] | 417 | printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 418 | goto bad; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 419 | } |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 420 | map = le64_to_cpu(map); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 421 | |
KaiGai Kohei | 9fe79ad | 2007-09-29 02:20:55 +0900 | [diff] [blame] | 422 | index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; |
| 423 | while (map) { |
KaiGai Kohei | 087feb9 | 2007-10-03 23:42:56 +0900 | [diff] [blame] | 424 | n->maps[index++] = map & (-1UL); |
| 425 | map = EBITMAP_SHIFT_UNIT_SIZE(map); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 426 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 427 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 428 | ok: |
| 429 | rc = 0; |
| 430 | out: |
| 431 | return rc; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 432 | bad: |
| 433 | if (!rc) |
| 434 | rc = -EINVAL; |
| 435 | ebitmap_destroy(e); |
| 436 | goto out; |
| 437 | } |
Eric Paris | cee74f4 | 2010-10-13 17:50:25 -0400 | [diff] [blame] | 438 | |
| 439 | int ebitmap_write(struct ebitmap *e, void *fp) |
| 440 | { |
| 441 | struct ebitmap_node *n; |
| 442 | u32 count; |
| 443 | __le32 buf[3]; |
| 444 | u64 map; |
| 445 | int bit, last_bit, last_startbit, rc; |
| 446 | |
| 447 | buf[0] = cpu_to_le32(BITS_PER_U64); |
| 448 | |
| 449 | count = 0; |
| 450 | last_bit = 0; |
| 451 | last_startbit = -1; |
| 452 | ebitmap_for_each_positive_bit(e, n, bit) { |
| 453 | if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { |
| 454 | count++; |
| 455 | last_startbit = rounddown(bit, BITS_PER_U64); |
| 456 | } |
| 457 | last_bit = roundup(bit + 1, BITS_PER_U64); |
| 458 | } |
| 459 | buf[1] = cpu_to_le32(last_bit); |
| 460 | buf[2] = cpu_to_le32(count); |
| 461 | |
| 462 | rc = put_entry(buf, sizeof(u32), 3, fp); |
| 463 | if (rc) |
| 464 | return rc; |
| 465 | |
| 466 | map = 0; |
| 467 | last_startbit = INT_MIN; |
| 468 | ebitmap_for_each_positive_bit(e, n, bit) { |
| 469 | if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { |
| 470 | __le64 buf64[1]; |
| 471 | |
| 472 | /* this is the very first bit */ |
| 473 | if (!map) { |
| 474 | last_startbit = rounddown(bit, BITS_PER_U64); |
| 475 | map = (u64)1 << (bit - last_startbit); |
| 476 | continue; |
| 477 | } |
| 478 | |
| 479 | /* write the last node */ |
| 480 | buf[0] = cpu_to_le32(last_startbit); |
| 481 | rc = put_entry(buf, sizeof(u32), 1, fp); |
| 482 | if (rc) |
| 483 | return rc; |
| 484 | |
| 485 | buf64[0] = cpu_to_le64(map); |
| 486 | rc = put_entry(buf64, sizeof(u64), 1, fp); |
| 487 | if (rc) |
| 488 | return rc; |
| 489 | |
| 490 | /* set up for the next node */ |
| 491 | map = 0; |
| 492 | last_startbit = rounddown(bit, BITS_PER_U64); |
| 493 | } |
| 494 | map |= (u64)1 << (bit - last_startbit); |
| 495 | } |
| 496 | /* write the last node */ |
| 497 | if (map) { |
| 498 | __le64 buf64[1]; |
| 499 | |
| 500 | /* write the last node */ |
| 501 | buf[0] = cpu_to_le32(last_startbit); |
| 502 | rc = put_entry(buf, sizeof(u32), 1, fp); |
| 503 | if (rc) |
| 504 | return rc; |
| 505 | |
| 506 | buf64[0] = cpu_to_le64(map); |
| 507 | rc = put_entry(buf64, sizeof(u64), 1, fp); |
| 508 | if (rc) |
| 509 | return rc; |
| 510 | } |
| 511 | return 0; |
| 512 | } |