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