]>
git.proxmox.com Git - mirror_ubuntu-focal-kernel.git/blob - security/selinux/ss/avtab.c
2 * Implementation of the access vector table type.
4 * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
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
;
28 static inline int avtab_hash(struct avtab_key
*keyp
, u16 mask
)
30 return ((keyp
->target_class
+ (keyp
->target_type
<< 2) +
31 (keyp
->source_type
<< 9)) & mask
);
34 static struct avtab_node
*
35 avtab_insert_node(struct avtab
*h
, int hvalue
,
36 struct avtab_node
* prev
, struct avtab_node
* cur
,
37 struct avtab_key
*key
, struct avtab_datum
*datum
)
39 struct avtab_node
* newnode
;
40 newnode
= kmem_cache_zalloc(avtab_node_cachep
, GFP_KERNEL
);
44 newnode
->datum
= *datum
;
46 newnode
->next
= prev
->next
;
49 newnode
->next
= h
->htable
[hvalue
];
50 h
->htable
[hvalue
] = newnode
;
57 static int avtab_insert(struct avtab
*h
, struct avtab_key
*key
, struct avtab_datum
*datum
)
60 struct avtab_node
*prev
, *cur
, *newnode
;
61 u16 specified
= key
->specified
& ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
66 hvalue
= avtab_hash(key
, h
->mask
);
67 for (prev
= NULL
, cur
= h
->htable
[hvalue
];
69 prev
= cur
, cur
= cur
->next
) {
70 if (key
->source_type
== cur
->key
.source_type
&&
71 key
->target_type
== cur
->key
.target_type
&&
72 key
->target_class
== cur
->key
.target_class
&&
73 (specified
& cur
->key
.specified
))
75 if (key
->source_type
< cur
->key
.source_type
)
77 if (key
->source_type
== cur
->key
.source_type
&&
78 key
->target_type
< cur
->key
.target_type
)
80 if (key
->source_type
== cur
->key
.source_type
&&
81 key
->target_type
== cur
->key
.target_type
&&
82 key
->target_class
< cur
->key
.target_class
)
86 newnode
= avtab_insert_node(h
, hvalue
, prev
, cur
, key
, datum
);
93 /* Unlike avtab_insert(), this function allow multiple insertions of the same
94 * key/specified mask into the table, as needed by the conditional avtab.
95 * It also returns a pointer to the node inserted.
98 avtab_insert_nonunique(struct avtab
* h
, struct avtab_key
* key
, struct avtab_datum
* datum
)
101 struct avtab_node
*prev
, *cur
, *newnode
;
102 u16 specified
= key
->specified
& ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
104 if (!h
|| !h
->htable
)
106 hvalue
= avtab_hash(key
, h
->mask
);
107 for (prev
= NULL
, cur
= h
->htable
[hvalue
];
109 prev
= cur
, cur
= cur
->next
) {
110 if (key
->source_type
== cur
->key
.source_type
&&
111 key
->target_type
== cur
->key
.target_type
&&
112 key
->target_class
== cur
->key
.target_class
&&
113 (specified
& cur
->key
.specified
))
115 if (key
->source_type
< cur
->key
.source_type
)
117 if (key
->source_type
== cur
->key
.source_type
&&
118 key
->target_type
< cur
->key
.target_type
)
120 if (key
->source_type
== cur
->key
.source_type
&&
121 key
->target_type
== cur
->key
.target_type
&&
122 key
->target_class
< cur
->key
.target_class
)
125 newnode
= avtab_insert_node(h
, hvalue
, prev
, cur
, key
, datum
);
130 struct avtab_datum
*avtab_search(struct avtab
*h
, struct avtab_key
*key
)
133 struct avtab_node
*cur
;
134 u16 specified
= key
->specified
& ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
136 if (!h
|| !h
->htable
)
139 hvalue
= avtab_hash(key
, h
->mask
);
140 for (cur
= h
->htable
[hvalue
]; cur
; cur
= cur
->next
) {
141 if (key
->source_type
== cur
->key
.source_type
&&
142 key
->target_type
== cur
->key
.target_type
&&
143 key
->target_class
== cur
->key
.target_class
&&
144 (specified
& cur
->key
.specified
))
147 if (key
->source_type
< cur
->key
.source_type
)
149 if (key
->source_type
== cur
->key
.source_type
&&
150 key
->target_type
< cur
->key
.target_type
)
152 if (key
->source_type
== cur
->key
.source_type
&&
153 key
->target_type
== cur
->key
.target_type
&&
154 key
->target_class
< cur
->key
.target_class
)
161 /* This search function returns a node pointer, and can be used in
162 * conjunction with avtab_search_next_node()
165 avtab_search_node(struct avtab
*h
, struct avtab_key
*key
)
168 struct avtab_node
*cur
;
169 u16 specified
= key
->specified
& ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
171 if (!h
|| !h
->htable
)
174 hvalue
= avtab_hash(key
, h
->mask
);
175 for (cur
= h
->htable
[hvalue
]; cur
; cur
= cur
->next
) {
176 if (key
->source_type
== cur
->key
.source_type
&&
177 key
->target_type
== cur
->key
.target_type
&&
178 key
->target_class
== cur
->key
.target_class
&&
179 (specified
& cur
->key
.specified
))
182 if (key
->source_type
< cur
->key
.source_type
)
184 if (key
->source_type
== cur
->key
.source_type
&&
185 key
->target_type
< cur
->key
.target_type
)
187 if (key
->source_type
== cur
->key
.source_type
&&
188 key
->target_type
== cur
->key
.target_type
&&
189 key
->target_class
< cur
->key
.target_class
)
196 avtab_search_node_next(struct avtab_node
*node
, int specified
)
198 struct avtab_node
*cur
;
203 specified
&= ~(AVTAB_ENABLED
|AVTAB_ENABLED_OLD
);
204 for (cur
= node
->next
; cur
; cur
= cur
->next
) {
205 if (node
->key
.source_type
== cur
->key
.source_type
&&
206 node
->key
.target_type
== cur
->key
.target_type
&&
207 node
->key
.target_class
== cur
->key
.target_class
&&
208 (specified
& cur
->key
.specified
))
211 if (node
->key
.source_type
< cur
->key
.source_type
)
213 if (node
->key
.source_type
== cur
->key
.source_type
&&
214 node
->key
.target_type
< cur
->key
.target_type
)
216 if (node
->key
.source_type
== cur
->key
.source_type
&&
217 node
->key
.target_type
== cur
->key
.target_type
&&
218 node
->key
.target_class
< cur
->key
.target_class
)
224 void avtab_destroy(struct avtab
*h
)
227 struct avtab_node
*cur
, *temp
;
229 if (!h
|| !h
->htable
)
232 for (i
= 0; i
< h
->nslot
; i
++) {
234 while (cur
!= NULL
) {
237 kmem_cache_free(avtab_node_cachep
, temp
);
247 int avtab_init(struct avtab
*h
)
254 int avtab_alloc(struct avtab
*h
, u32 nrules
)
262 goto avtab_alloc_out
;
271 if (nslot
> MAX_AVTAB_SIZE
)
272 nslot
= MAX_AVTAB_SIZE
;
275 h
->htable
= kcalloc(nslot
, sizeof(*(h
->htable
)), GFP_KERNEL
);
283 printk(KERN_DEBUG
"SELinux:%d avtab hash slots allocated."
284 "Num of rules:%d\n", h
->nslot
, nrules
);
288 void avtab_hash_eval(struct avtab
*h
, char *tag
)
290 int i
, chain_len
, slots_used
, max_chain_len
;
291 unsigned long long chain2_len_sum
;
292 struct avtab_node
*cur
;
297 for (i
= 0; i
< h
->nslot
; i
++) {
307 if (chain_len
> max_chain_len
)
308 max_chain_len
= chain_len
;
309 chain2_len_sum
+= chain_len
* chain_len
;
313 printk(KERN_DEBUG
"%s: %d entries and %d/%d buckets used, longest "
314 "chain length %d sum of chain length^2 %Lu\n",
315 tag
, h
->nel
, slots_used
, h
->nslot
, max_chain_len
,
319 static uint16_t spec_order
[] = {
328 int avtab_read_item(void *fp
, u32 vers
, struct avtab
*a
,
329 int (*insertf
)(struct avtab
*a
, struct avtab_key
*k
,
330 struct avtab_datum
*d
, void *p
),
336 u32 items
, items2
, val
;
337 struct avtab_key key
;
338 struct avtab_datum datum
;
341 memset(&key
, 0, sizeof(struct avtab_key
));
342 memset(&datum
, 0, sizeof(struct avtab_datum
));
344 if (vers
< POLICYDB_VERSION_AVTAB
) {
345 rc
= next_entry(buf32
, fp
, sizeof(u32
));
347 printk(KERN_ERR
"security: avtab: truncated entry\n");
350 items2
= le32_to_cpu(buf32
[0]);
351 if (items2
> ARRAY_SIZE(buf32
)) {
352 printk(KERN_ERR
"security: avtab: entry overflow\n");
356 rc
= next_entry(buf32
, fp
, sizeof(u32
)*items2
);
358 printk(KERN_ERR
"security: avtab: truncated entry\n");
363 val
= le32_to_cpu(buf32
[items
++]);
364 key
.source_type
= (u16
)val
;
365 if (key
.source_type
!= val
) {
366 printk("security: avtab: truncated source type\n");
369 val
= le32_to_cpu(buf32
[items
++]);
370 key
.target_type
= (u16
)val
;
371 if (key
.target_type
!= val
) {
372 printk("security: avtab: truncated target type\n");
375 val
= le32_to_cpu(buf32
[items
++]);
376 key
.target_class
= (u16
)val
;
377 if (key
.target_class
!= val
) {
378 printk("security: avtab: truncated target class\n");
382 val
= le32_to_cpu(buf32
[items
++]);
383 enabled
= (val
& AVTAB_ENABLED_OLD
) ? AVTAB_ENABLED
: 0;
385 if (!(val
& (AVTAB_AV
| AVTAB_TYPE
))) {
386 printk("security: avtab: null entry\n");
389 if ((val
& AVTAB_AV
) &&
390 (val
& AVTAB_TYPE
)) {
391 printk("security: avtab: entry has both access vectors and types\n");
395 for (i
= 0; i
< ARRAY_SIZE(spec_order
); i
++) {
396 if (val
& spec_order
[i
]) {
397 key
.specified
= spec_order
[i
] | enabled
;
398 datum
.data
= le32_to_cpu(buf32
[items
++]);
399 rc
= insertf(a
, &key
, &datum
, p
);
404 if (items
!= items2
) {
405 printk("security: avtab: entry only had %d items, expected %d\n", items2
, items
);
411 rc
= next_entry(buf16
, fp
, sizeof(u16
)*4);
413 printk("security: avtab: truncated entry\n");
418 key
.source_type
= le16_to_cpu(buf16
[items
++]);
419 key
.target_type
= le16_to_cpu(buf16
[items
++]);
420 key
.target_class
= le16_to_cpu(buf16
[items
++]);
421 key
.specified
= le16_to_cpu(buf16
[items
++]);
423 rc
= next_entry(buf32
, fp
, sizeof(u32
));
425 printk("security: avtab: truncated entry\n");
428 datum
.data
= le32_to_cpu(*buf32
);
429 return insertf(a
, &key
, &datum
, p
);
432 static int avtab_insertf(struct avtab
*a
, struct avtab_key
*k
,
433 struct avtab_datum
*d
, void *p
)
435 return avtab_insert(a
, k
, d
);
438 int avtab_read(struct avtab
*a
, void *fp
, u32 vers
)
445 rc
= next_entry(buf
, fp
, sizeof(u32
));
447 printk(KERN_ERR
"security: avtab: truncated table\n");
450 nel
= le32_to_cpu(buf
[0]);
452 printk(KERN_ERR
"security: avtab: table is empty\n");
457 rc
= avtab_alloc(a
, nel
);
461 for (i
= 0; i
< nel
; i
++) {
462 rc
= avtab_read_item(fp
,vers
, a
, avtab_insertf
, NULL
);
465 printk(KERN_ERR
"security: avtab: out of memory\n");
466 else if (rc
== -EEXIST
)
467 printk(KERN_ERR
"security: avtab: duplicate entry\n");
483 void avtab_cache_init(void)
485 avtab_node_cachep
= kmem_cache_create("avtab_node",
486 sizeof(struct avtab_node
),
487 0, SLAB_PANIC
, NULL
);
490 void avtab_cache_destroy(void)
492 kmem_cache_destroy (avtab_node_cachep
);