2 * Implementation of the access vector table type.
4 * Author : Stephen Smalley, <sds@tycho.nsa.gov>
7 /* Updated: Frank Mayer <mayerf@tresys.com> and Karl MacMillan <kmacmillan@tresys.com>
9 * Added conditional policy language extensions
11 * Copyright (C) 2003 Tresys Technology, LLC
12 * This program is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License as published by
14 * the Free Software Foundation, version 2.
16 * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
17 * Tuned number of hash slots for avtab to reduce memory usage
20 #include <linux/kernel.h>
21 #include <linux/slab.h>
22 #include <linux/errno.h>
26 static struct kmem_cache
*avtab_node_cachep
;
27 static struct kmem_cache
*avtab_xperms_cachep
;
29 /* Based on MurmurHash3, written by Austin Appleby and placed in the
32 static inline int avtab_hash(struct avtab_key
*keyp
, u32 mask
)
34 static const u32 c1
= 0xcc9e2d51;
35 static const u32 c2
= 0x1b873593;
36 static const u32 r1
= 15;
37 static const u32 r2
= 13;
38 static const u32 m
= 5;
39 static const u32 n
= 0xe6546b64;
43 #define mix(input) { \
46 v = (v << r1) | (v >> (32 - r1)); \
49 hash = (hash << r2) | (hash >> (32 - r2)); \
50 hash = hash * m + n; \
53 mix(keyp
->target_class
);
54 mix(keyp
->target_type
);
55 mix(keyp
->source_type
);
68 static struct avtab_node
*
69 avtab_insert_node(struct avtab
*h
, int hvalue
,
70 struct avtab_node
*prev
, struct avtab_node
*cur
,
71 struct avtab_key
*key
, struct avtab_datum
*datum
)
73 struct avtab_node
*newnode
;
74 struct avtab_extended_perms
*xperms
;
75 newnode
= kmem_cache_zalloc(avtab_node_cachep
, GFP_KERNEL
);
80 if (key
->specified
& AVTAB_XPERMS
) {
81 xperms
= kmem_cache_zalloc(avtab_xperms_cachep
, GFP_KERNEL
);
83 kmem_cache_free(avtab_node_cachep
, newnode
);
86 *xperms
= *(datum
->u
.xperms
);
87 newnode
->datum
.u
.xperms
= xperms
;
89 newnode
->datum
.u
.data
= datum
->u
.data
;
93 newnode
->next
= prev
->next
;
96 struct avtab_node
**n
= &h
->htable
[hvalue
];
106 static int avtab_insert(struct avtab
*h
, struct avtab_key
*key
, struct avtab_datum
*datum
)
109 struct avtab_node
*prev
, *cur
, *newnode
;
110 u16 specified
= key
->specified
& ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
115 hvalue
= avtab_hash(key
, h
->mask
);
116 for (prev
= NULL
, cur
= h
->htable
[hvalue
];
118 prev
= cur
, cur
= cur
->next
) {
119 if (key
->source_type
== cur
->key
.source_type
&&
120 key
->target_type
== cur
->key
.target_type
&&
121 key
->target_class
== cur
->key
.target_class
&&
122 (specified
& cur
->key
.specified
)) {
123 /* extended perms may not be unique */
124 if (specified
& AVTAB_XPERMS
)
128 if (key
->source_type
< cur
->key
.source_type
)
130 if (key
->source_type
== cur
->key
.source_type
&&
131 key
->target_type
< cur
->key
.target_type
)
133 if (key
->source_type
== cur
->key
.source_type
&&
134 key
->target_type
== cur
->key
.target_type
&&
135 key
->target_class
< cur
->key
.target_class
)
139 newnode
= avtab_insert_node(h
, hvalue
, prev
, cur
, key
, datum
);
146 /* Unlike avtab_insert(), this function allow multiple insertions of the same
147 * key/specified mask into the table, as needed by the conditional avtab.
148 * It also returns a pointer to the node inserted.
151 avtab_insert_nonunique(struct avtab
*h
, struct avtab_key
*key
, struct avtab_datum
*datum
)
154 struct avtab_node
*prev
, *cur
;
155 u16 specified
= key
->specified
& ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
159 hvalue
= avtab_hash(key
, h
->mask
);
160 for (prev
= NULL
, cur
= h
->htable
[hvalue
];
162 prev
= cur
, cur
= cur
->next
) {
163 if (key
->source_type
== cur
->key
.source_type
&&
164 key
->target_type
== cur
->key
.target_type
&&
165 key
->target_class
== cur
->key
.target_class
&&
166 (specified
& cur
->key
.specified
))
168 if (key
->source_type
< cur
->key
.source_type
)
170 if (key
->source_type
== cur
->key
.source_type
&&
171 key
->target_type
< cur
->key
.target_type
)
173 if (key
->source_type
== cur
->key
.source_type
&&
174 key
->target_type
== cur
->key
.target_type
&&
175 key
->target_class
< cur
->key
.target_class
)
178 return avtab_insert_node(h
, hvalue
, prev
, cur
, key
, datum
);
181 struct avtab_datum
*avtab_search(struct avtab
*h
, struct avtab_key
*key
)
184 struct avtab_node
*cur
;
185 u16 specified
= key
->specified
& ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
190 hvalue
= avtab_hash(key
, h
->mask
);
191 for (cur
= h
->htable
[hvalue
]; cur
;
193 if (key
->source_type
== cur
->key
.source_type
&&
194 key
->target_type
== cur
->key
.target_type
&&
195 key
->target_class
== cur
->key
.target_class
&&
196 (specified
& cur
->key
.specified
))
199 if (key
->source_type
< cur
->key
.source_type
)
201 if (key
->source_type
== cur
->key
.source_type
&&
202 key
->target_type
< cur
->key
.target_type
)
204 if (key
->source_type
== cur
->key
.source_type
&&
205 key
->target_type
== cur
->key
.target_type
&&
206 key
->target_class
< cur
->key
.target_class
)
213 /* This search function returns a node pointer, and can be used in
214 * conjunction with avtab_search_next_node()
217 avtab_search_node(struct avtab
*h
, struct avtab_key
*key
)
220 struct avtab_node
*cur
;
221 u16 specified
= key
->specified
& ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
226 hvalue
= avtab_hash(key
, h
->mask
);
227 for (cur
= h
->htable
[hvalue
]; cur
;
229 if (key
->source_type
== cur
->key
.source_type
&&
230 key
->target_type
== cur
->key
.target_type
&&
231 key
->target_class
== cur
->key
.target_class
&&
232 (specified
& cur
->key
.specified
))
235 if (key
->source_type
< cur
->key
.source_type
)
237 if (key
->source_type
== cur
->key
.source_type
&&
238 key
->target_type
< cur
->key
.target_type
)
240 if (key
->source_type
== cur
->key
.source_type
&&
241 key
->target_type
== cur
->key
.target_type
&&
242 key
->target_class
< cur
->key
.target_class
)
249 avtab_search_node_next(struct avtab_node
*node
, int specified
)
251 struct avtab_node
*cur
;
256 specified
&= ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
257 for (cur
= node
->next
; cur
; cur
= cur
->next
) {
258 if (node
->key
.source_type
== cur
->key
.source_type
&&
259 node
->key
.target_type
== cur
->key
.target_type
&&
260 node
->key
.target_class
== cur
->key
.target_class
&&
261 (specified
& cur
->key
.specified
))
264 if (node
->key
.source_type
< cur
->key
.source_type
)
266 if (node
->key
.source_type
== cur
->key
.source_type
&&
267 node
->key
.target_type
< cur
->key
.target_type
)
269 if (node
->key
.source_type
== cur
->key
.source_type
&&
270 node
->key
.target_type
== cur
->key
.target_type
&&
271 node
->key
.target_class
< cur
->key
.target_class
)
277 void avtab_destroy(struct avtab
*h
)
280 struct avtab_node
*cur
, *temp
;
285 for (i
= 0; i
< h
->nslot
; i
++) {
290 if (temp
->key
.specified
& AVTAB_XPERMS
)
291 kmem_cache_free(avtab_xperms_cachep
,
292 temp
->datum
.u
.xperms
);
293 kmem_cache_free(avtab_node_cachep
, temp
);
302 int avtab_init(struct avtab
*h
)
310 int avtab_alloc(struct avtab
*h
, u32 nrules
)
318 goto avtab_alloc_out
;
327 if (nslot
> MAX_AVTAB_HASH_BUCKETS
)
328 nslot
= MAX_AVTAB_HASH_BUCKETS
;
331 h
->htable
= kvcalloc(nslot
, sizeof(void *), GFP_KERNEL
);
339 pr_debug("SELinux: %d avtab hash slots, %d rules.\n",
344 void avtab_hash_eval(struct avtab
*h
, char *tag
)
346 int i
, chain_len
, slots_used
, max_chain_len
;
347 unsigned long long chain2_len_sum
;
348 struct avtab_node
*cur
;
353 for (i
= 0; i
< h
->nslot
; i
++) {
363 if (chain_len
> max_chain_len
)
364 max_chain_len
= chain_len
;
365 chain2_len_sum
+= chain_len
* chain_len
;
369 pr_debug("SELinux: %s: %d entries and %d/%d buckets used, "
370 "longest chain length %d sum of chain length^2 %llu\n",
371 tag
, h
->nel
, slots_used
, h
->nslot
, max_chain_len
,
375 static uint16_t spec_order
[] = {
382 AVTAB_XPERMS_ALLOWED
,
383 AVTAB_XPERMS_AUDITALLOW
,
384 AVTAB_XPERMS_DONTAUDIT
387 int avtab_read_item(struct avtab
*a
, void *fp
, struct policydb
*pol
,
388 int (*insertf
)(struct avtab
*a
, struct avtab_key
*k
,
389 struct avtab_datum
*d
, void *p
),
394 u32 items
, items2
, val
, vers
= pol
->policyvers
;
395 struct avtab_key key
;
396 struct avtab_datum datum
;
397 struct avtab_extended_perms xperms
;
398 __le32 buf32
[ARRAY_SIZE(xperms
.perms
.p
)];
402 memset(&key
, 0, sizeof(struct avtab_key
));
403 memset(&datum
, 0, sizeof(struct avtab_datum
));
405 if (vers
< POLICYDB_VERSION_AVTAB
) {
406 rc
= next_entry(buf32
, fp
, sizeof(u32
));
408 pr_err("SELinux: avtab: truncated entry\n");
411 items2
= le32_to_cpu(buf32
[0]);
412 if (items2
> ARRAY_SIZE(buf32
)) {
413 pr_err("SELinux: avtab: entry overflow\n");
417 rc
= next_entry(buf32
, fp
, sizeof(u32
)*items2
);
419 pr_err("SELinux: avtab: truncated entry\n");
424 val
= le32_to_cpu(buf32
[items
++]);
425 key
.source_type
= (u16
)val
;
426 if (key
.source_type
!= val
) {
427 pr_err("SELinux: avtab: truncated source type\n");
430 val
= le32_to_cpu(buf32
[items
++]);
431 key
.target_type
= (u16
)val
;
432 if (key
.target_type
!= val
) {
433 pr_err("SELinux: avtab: truncated target type\n");
436 val
= le32_to_cpu(buf32
[items
++]);
437 key
.target_class
= (u16
)val
;
438 if (key
.target_class
!= val
) {
439 pr_err("SELinux: avtab: truncated target class\n");
443 val
= le32_to_cpu(buf32
[items
++]);
444 enabled
= (val
& AVTAB_ENABLED_OLD
) ? AVTAB_ENABLED
: 0;
446 if (!(val
& (AVTAB_AV
| AVTAB_TYPE
))) {
447 pr_err("SELinux: avtab: null entry\n");
450 if ((val
& AVTAB_AV
) &&
451 (val
& AVTAB_TYPE
)) {
452 pr_err("SELinux: avtab: entry has both access vectors and types\n");
455 if (val
& AVTAB_XPERMS
) {
456 pr_err("SELinux: avtab: entry has extended permissions\n");
460 for (i
= 0; i
< ARRAY_SIZE(spec_order
); i
++) {
461 if (val
& spec_order
[i
]) {
462 key
.specified
= spec_order
[i
] | enabled
;
463 datum
.u
.data
= le32_to_cpu(buf32
[items
++]);
464 rc
= insertf(a
, &key
, &datum
, p
);
470 if (items
!= items2
) {
471 pr_err("SELinux: avtab: entry only had %d items, expected %d\n",
478 rc
= next_entry(buf16
, fp
, sizeof(u16
)*4);
480 pr_err("SELinux: avtab: truncated entry\n");
485 key
.source_type
= le16_to_cpu(buf16
[items
++]);
486 key
.target_type
= le16_to_cpu(buf16
[items
++]);
487 key
.target_class
= le16_to_cpu(buf16
[items
++]);
488 key
.specified
= le16_to_cpu(buf16
[items
++]);
490 if (!policydb_type_isvalid(pol
, key
.source_type
) ||
491 !policydb_type_isvalid(pol
, key
.target_type
) ||
492 !policydb_class_isvalid(pol
, key
.target_class
)) {
493 pr_err("SELinux: avtab: invalid type or class\n");
498 for (i
= 0; i
< ARRAY_SIZE(spec_order
); i
++) {
499 if (key
.specified
& spec_order
[i
])
502 if (!set
|| set
> 1) {
503 pr_err("SELinux: avtab: more than one specifier\n");
507 if ((vers
< POLICYDB_VERSION_XPERMS_IOCTL
) &&
508 (key
.specified
& AVTAB_XPERMS
)) {
509 pr_err("SELinux: avtab: policy version %u does not "
510 "support extended permissions rules and one "
511 "was specified\n", vers
);
513 } else if (key
.specified
& AVTAB_XPERMS
) {
514 memset(&xperms
, 0, sizeof(struct avtab_extended_perms
));
515 rc
= next_entry(&xperms
.specified
, fp
, sizeof(u8
));
517 pr_err("SELinux: avtab: truncated entry\n");
520 rc
= next_entry(&xperms
.driver
, fp
, sizeof(u8
));
522 pr_err("SELinux: avtab: truncated entry\n");
525 rc
= next_entry(buf32
, fp
, sizeof(u32
)*ARRAY_SIZE(xperms
.perms
.p
));
527 pr_err("SELinux: avtab: truncated entry\n");
530 for (i
= 0; i
< ARRAY_SIZE(xperms
.perms
.p
); i
++)
531 xperms
.perms
.p
[i
] = le32_to_cpu(buf32
[i
]);
532 datum
.u
.xperms
= &xperms
;
534 rc
= next_entry(buf32
, fp
, sizeof(u32
));
536 pr_err("SELinux: avtab: truncated entry\n");
539 datum
.u
.data
= le32_to_cpu(*buf32
);
541 if ((key
.specified
& AVTAB_TYPE
) &&
542 !policydb_type_isvalid(pol
, datum
.u
.data
)) {
543 pr_err("SELinux: avtab: invalid type\n");
546 return insertf(a
, &key
, &datum
, p
);
549 static int avtab_insertf(struct avtab
*a
, struct avtab_key
*k
,
550 struct avtab_datum
*d
, void *p
)
552 return avtab_insert(a
, k
, d
);
555 int avtab_read(struct avtab
*a
, void *fp
, struct policydb
*pol
)
562 rc
= next_entry(buf
, fp
, sizeof(u32
));
564 pr_err("SELinux: avtab: truncated table\n");
567 nel
= le32_to_cpu(buf
[0]);
569 pr_err("SELinux: avtab: table is empty\n");
574 rc
= avtab_alloc(a
, nel
);
578 for (i
= 0; i
< nel
; i
++) {
579 rc
= avtab_read_item(a
, fp
, pol
, avtab_insertf
, NULL
);
582 pr_err("SELinux: avtab: out of memory\n");
583 else if (rc
== -EEXIST
)
584 pr_err("SELinux: avtab: duplicate entry\n");
599 int avtab_write_item(struct policydb
*p
, struct avtab_node
*cur
, void *fp
)
602 __le32 buf32
[ARRAY_SIZE(cur
->datum
.u
.xperms
->perms
.p
)];
606 buf16
[0] = cpu_to_le16(cur
->key
.source_type
);
607 buf16
[1] = cpu_to_le16(cur
->key
.target_type
);
608 buf16
[2] = cpu_to_le16(cur
->key
.target_class
);
609 buf16
[3] = cpu_to_le16(cur
->key
.specified
);
610 rc
= put_entry(buf16
, sizeof(u16
), 4, fp
);
614 if (cur
->key
.specified
& AVTAB_XPERMS
) {
615 rc
= put_entry(&cur
->datum
.u
.xperms
->specified
, sizeof(u8
), 1, fp
);
618 rc
= put_entry(&cur
->datum
.u
.xperms
->driver
, sizeof(u8
), 1, fp
);
621 for (i
= 0; i
< ARRAY_SIZE(cur
->datum
.u
.xperms
->perms
.p
); i
++)
622 buf32
[i
] = cpu_to_le32(cur
->datum
.u
.xperms
->perms
.p
[i
]);
623 rc
= put_entry(buf32
, sizeof(u32
),
624 ARRAY_SIZE(cur
->datum
.u
.xperms
->perms
.p
), fp
);
626 buf32
[0] = cpu_to_le32(cur
->datum
.u
.data
);
627 rc
= put_entry(buf32
, sizeof(u32
), 1, fp
);
634 int avtab_write(struct policydb
*p
, struct avtab
*a
, void *fp
)
638 struct avtab_node
*cur
;
641 buf
[0] = cpu_to_le32(a
->nel
);
642 rc
= put_entry(buf
, sizeof(u32
), 1, fp
);
646 for (i
= 0; i
< a
->nslot
; i
++) {
647 for (cur
= a
->htable
[i
]; cur
;
649 rc
= avtab_write_item(p
, cur
, fp
);
658 void __init
avtab_cache_init(void)
660 avtab_node_cachep
= kmem_cache_create("avtab_node",
661 sizeof(struct avtab_node
),
662 0, SLAB_PANIC
, NULL
);
663 avtab_xperms_cachep
= kmem_cache_create("avtab_extended_perms",
664 sizeof(struct avtab_extended_perms
),
665 0, SLAB_PANIC
, NULL
);