5:12 a.m.
Hi
I quickly summarized what is happend so far.
Requirements from issue #51 [1] in Github:
- 20000 rules in policy
- 600 SMACK labels
Current situation:
- We have hash based dictionary for SMACK labels already implemented.
- Support for detecting and writing multiple rules [2] is lacking.
- Rule set is not optimized in any possible way. It's just a
a linear list.
This is my plan to move forward:
- Keep label management as it is.
- Multiple rules handling must be implemented. Rafal, you are working
on this right?
- Rules should be always merged.
My decision as is to take one implementation to the end and therefore
integrate code for merging labels in Github issue #87 [3].
If you ever encounter a real-world workload that causes problems
with that approach, we can take it into discussion here in this
mailing list.
[1] https://github.com/smack-team/smack/issues/51
[2] https://lkml.org/lkml/2013/8/9/156
[3] https://github.com/smack-team/smack/pull/87
/Jarkko
12:23 a.m.
I've been seeing strange benchmark results for few days that I couldn't explain.
While trying to compare different implementations of rule merging and processing, there is
one factor that turns out to be very important.
When feeding rules to kernel, they should be sorted by subject and object (maybe sorting
only by subject is enough). This makes a huge difference.
I've been testing one particular implementation on an input file generated by script
from José Bollo. Using 500 labels and 1000000 rules (245272 unique) I get the following
results:
*output sorted by (subject, object)*
3180.077300 task-clock # 0.992 CPUs utilized ( +-
0.71% )
171 context-switches # 0.054 K/sec ( +-
37.58% )
4 CPU-migrations # 0.001 K/sec ( +-
34.71% )
243 page-faults # 0.076 K/sec
5062966584 cycles # 1.592 GHz ( +-
0.84% )
26162516 stalled-cycles-frontend # 0.52% frontend cycles idle ( +-
21.36% )
2639629839 stalled-cycles-backend # 52.14% backend cycles idle ( +-
1.57% )
3984587644 instructions # 0.79 insns per cycle
# 0.66 stalled cycles per insn ( +-
0.05% )
468929791 branches # 147.459 M/sec ( +-
0.03% )
77636935 branch-misses # 16.56% of all branches ( +-
0.78% )
3.205577202 seconds time elapsed ( +-
0.68% )
*no sorting, writing rules in the order of input*
7250.575934 task-clock # 0.993 CPUs utilized ( +-
0.79% )
446 context-switches # 0.061 K/sec ( +-
44.82% )
3 CPU-migrations # 0.000 K/sec ( +-
13.36% )
243 page-faults # 0.034 K/sec
11558497434 cycles # 1.594 GHz ( +-
0.80% )
63861332 stalled-cycles-frontend # 0.55% frontend cycles idle ( +-
12.58% )
9113627677 stalled-cycles-backend # 78.85% backend cycles idle ( +-
0.99% )
3993300730 instructions # 0.35 insns per cycle
# 2.28 stalled cycles per insn ( +-
0.07% )
469925865 branches # 64.812 M/sec ( +-
0.03% )
78249613 branch-misses # 16.65% of all branches ( +-
0.60% )
7.301213820 seconds time elapsed ( +-
0.93% )
All tests have been done on Samsung I8800 device (Redwood) with quad core Exynos 4412 CPU
(32/32 L1 cache, 1MB L2 cache)
As you can see, the second variant is *2.28 times slower*! This difference can be
attributed to internal kernel data structures used for storing Smack rules.
Because of this any decent approach for rule mangling in libsmack should output sorted
rules. This affects libsmack data structure design. They must support sorting as a side
effect or at least enable it.
I will submit my implementation soon. It might be also good to revise previous approaches
and test them with output sorting.
1:41 a.m.
On ven, 2014-01-10 at 14:23 +0100, Rafał Krypa wrote:
I've been seeing strange benchmark results for few days that I
couldn't explain. While trying to compare different implementations of rule merging
and processing, there is one factor that turns out to be very important.
When feeding rules to kernel, they should be sorted by subject and object (maybe sorting
only by subject is enough). This makes a huge difference.
I've been testing one particular implementation on an input file generated by script
from José Bollo. Using 500 labels and 1000000 rules (245272 unique) I get the following
results:
(snip)
As you can see, the second variant is *2.28 times slower*! This
difference can be attributed to internal kernel data structures used for storing Smack
rules.
Because of this any decent approach for rule mangling in libsmack should output sorted
rules. This affects libsmack data structure design. They must support sorting as a side
effect or at least enable it.
I will submit my implementation soon. It might be also good to revise previous approaches
and test them with output sorting.
It should be checked that it doesn't comes from sorting but instead from
grouping. The hash table of LSMsmack is very small:
#define SMACK_HASH_SLOTS 16
when entries are created, they are inserted at head of the list. Then
near (in time) searches to it are fast.
That is grouping subjects that is good. Sorting has the side effect of
grouping.
The tree version does a natural sorting of the rules but the rules have
to be iterated using the function 'twalk'.
Best Regards
José
2:57 a.m.
On ven, 2014-01-10 at 15:41 +0100, José Bollo wrote:
The tree version does a natural sorting of the rules but the rules
have
to be iterated using the function 'twalk'.
well the problem with twalk is that it doesn't have a user pointer.
The solution is to index the accesses struct instead of next rule (same
memory size) and to record the FILE in accesses instead of first/last.
twalk(root, emit);
void emit(const void*node,const VISIT visit,const int depth)
{
if(visit==postorder) {
rule_t * rule = *(rule_t**)node; /* const ... */
fprintf(rule->access->file,"%s %s %s %s",rule->....);
}
}
That would work. But 3 callback calls by rule! And the price of
retrieving file...
Best regards
José
3:50 a.m.
Hi José,
On Fri, Jan 10, 2014 at 04:57:01PM +0100, José Bollo wrote:
On ven, 2014-01-10 at 15:41 +0100, José Bollo wrote:
> The tree version does a natural sorting of the rules but the rules have
> to be iterated using the function 'twalk'.
well the problem with twalk is that it doesn't have a user pointer.
The solution is to index the accesses struct instead of next rule (same
memory size) and to record the FILE in accesses instead of first/last.
twalk(root, emit);
void emit(const void*node,const VISIT visit,const int depth)
{
if(visit==postorder) {
rule_t * rule = *(rule_t**)node; /* const ... */
fprintf(rule->access->file,"%s %s %s %s",rule->....);
}
}
That would work. But 3 callback calls by rule! And the price of
retrieving file...
Maybe I'm missing something but why you would you wnat to use twalk
in the first place? We could just traverse the directly? List traversal
is trivial even without using a library function. Please correct me
if I'm now ignoring something.
Best regards
José
/Jarkko
5:50 a.m.
On 2014-01-10 17:50, Jarkko Sakkinen wrote:
Hi José,
On Fri, Jan 10, 2014 at 04:57:01PM +0100, José Bollo wrote:
> On ven, 2014-01-10 at 15:41 +0100, José Bollo wrote:
>
>> The tree version does a natural sorting of the rules but the rules have
>> to be iterated using the function 'twalk'.
> well the problem with twalk is that it doesn't have a user pointer.
>
> The solution is to index the accesses struct instead of next rule (same
> memory size) and to record the FILE in accesses instead of first/last.
>
> twalk(root, emit);
>
> void emit(const void*node,const VISIT visit,const int depth)
> {
> if(visit==postorder) {
> rule_t * rule = *(rule_t**)node; /* const ... */
> fprintf(rule->access->file,"%s %s %s %s",rule->....);
> }
> }
>
> That would work. But 3 callback calls by rule! And the price of
> retrieving file...
Maybe I'm missing something but why you would you wnat to use twalk
in the first place? We could just traverse the directly? List traversal
is trivial even without using a library function. Please correct me
if I'm now ignoring something.
The problem with direct traversal of glibc tree is that tree data
structures are not exported. The struct node_t, containing left and
right pointers isn't defined nor even declared in any header. It appears
only in implementation file, misc/tsearch.c. For tree API (tsearch() and
friends) tree is typed as void**. The only supported way to traverse it
is the library function twalk().
We could define our copy of struct node_t in libsmack, but it doesn't
sound like a good idea to me.
8:47 p.m.
On Fri, Jan 10, 2014 at 07:50:36PM +0100, Rafał Krypa wrote:
On 2014-01-10 17:50, Jarkko Sakkinen wrote:
>Hi José,
>
>On Fri, Jan 10, 2014 at 04:57:01PM +0100, José Bollo wrote:
>>On ven, 2014-01-10 at 15:41 +0100, José Bollo wrote:
>>
>>>The tree version does a natural sorting of the rules but the rules have
>>>to be iterated using the function 'twalk'.
>>well the problem with twalk is that it doesn't have a user pointer.
>>
>>The solution is to index the accesses struct instead of next rule (same
>>memory size) and to record the FILE in accesses instead of first/last.
>>
>>twalk(root, emit);
>>
>>void emit(const void*node,const VISIT visit,const int depth)
>>{
>> if(visit==postorder) {
>> rule_t * rule = *(rule_t**)node; /* const ... */
>> fprintf(rule->access->file,"%s %s %s %s",rule->....);
>> }
>>}
>>
>>That would work. But 3 callback calls by rule! And the price of
>>retrieving file...
>Maybe I'm missing something but why you would you wnat to use twalk
>in the first place? We could just traverse the directly? List traversal
>is trivial even without using a library function. Please correct me
>if I'm now ignoring something.
The problem with direct traversal of glibc tree is that tree data
structures are not exported. The struct node_t, containing left and
right pointers isn't defined nor even declared in any header. It
appears only in implementation file, misc/tsearch.c. For tree API
(tsearch() and friends) tree is typed as void**. The only supported
way to traverse it is the library function twalk().
We could define our copy of struct node_t in libsmack, but it
doesn't sound like a good idea to me.
That is definitely something you don't want to do because struct
node_t can change from GLIBC version to another and who knows what
internal structure is used in other libc implementations.
The next best option is then to use TLS for the state.
/Jarkko
1:42 a.m.
On Fri, Jan 10, 2014 at 02:23:50PM +0100, Rafał Krypa wrote:
I've been seeing strange benchmark results for few days that I
couldn't
explain. While trying to compare different implementations of rule merging
and processing, there is one factor that turns out to be very important.
When feeding rules to kernel, they should be sorted by subject and object
(maybe sorting only by subject is enough). This makes a huge difference.
I've been testing one particular implementation on an input file generated
by script from José Bollo. Using 500 labels and 1000000 rules (245272
unique) I get the following results:
OK, this changes the game them. If we need to sort rules, then it makes sense
to use RB-tree because there we seek much more scalability than in number of
labels.
Meta-note: could you configure your mail client to send mails in plain text
and quote replies properly? Would make discussion easier to follow. Thanks!
/Jarkko
output sorted by (subject, object)
3180.077300 task-clock # 0.992 CPUs utilized ( +-
0.71% )
171 context-switches # 0.054 K/sec ( +-
37.58% )
4 CPU-migrations # 0.001 K/sec ( +-
34.71% )
243 page-faults # 0.076 K/sec
5062966584 cycles # 1.592 GHz ( +-
0.84% )
26162516 stalled-cycles-frontend # 0.52% frontend cycles idle ( +-
21.36% )
2639629839 stalled-cycles-backend # 52.14% backend cycles idle ( +-
1.57% )
3984587644 instructions # 0.79 insns per cycle
# 0.66 stalled cycles per insn ( +-
0.05% )
468929791 branches # 147.459 M/sec ( +-
0.03% )
77636935 branch-misses # 16.56% of all branches ( +-
0.78% )
3.205577202 seconds time elapsed ( +-
0.68% )
no sorting, writing rules in the order of input
7250.575934 task-clock # 0.993 CPUs utilized ( +-
0.79% )
446 context-switches # 0.061 K/sec ( +-
44.82% )
3 CPU-migrations # 0.000 K/sec ( +-
13.36% )
243 page-faults # 0.034 K/sec
11558497434 cycles # 1.594 GHz ( +-
0.80% )
63861332 stalled-cycles-frontend # 0.55% frontend cycles idle ( +-
12.58% )
9113627677 stalled-cycles-backend # 78.85% backend cycles idle ( +-
0.99% )
3993300730 instructions # 0.35 insns per cycle
# 2.28 stalled cycles per insn ( +-
0.07% )
469925865 branches # 64.812 M/sec ( +-
0.03% )
78249613 branch-misses # 16.65% of all branches ( +-
0.60% )
7.301213820 seconds time elapsed ( +-
0.93% )
All tests have been done on Samsung I8800 device (Redwood) with quad core
Exynos 4412 CPU (32/32 L1 cache, 1MB L2 cache)
As you can see, the second variant is 2.28 times slower! This difference
can be attributed to internal kernel data structures used for storing
Smack rules.
Because of this any decent approach for rule mangling in libsmack should
output sorted rules. This affects libsmack data structure design. They
must support sorting as a side effect or at least enable it.
I will submit my implementation soon. It might be also good to revise
previous approaches and test them with output sorting.
_______________________________________________
SMACK-discuss mailing list
SMACK-discuss(a)lists.01.org
https://lists.01.org/mailman/listinfo/smack-discuss
5:31 a.m.
On 2014-01-10 14:23, Rafał Krypa wrote:
I've been seeing strange benchmark results for few days that I
couldn't explain. While trying to compare different implementations of rule merging
and processing, there is one factor that turns out to be very important.
When feeding rules to kernel, they should be sorted by subject and object (maybe sorting
only by subject is enough). This makes a huge difference.
After several more tests and refining of test methodology I have to take my words back.
We have all made some errors while testing rule loading performance. These are:
- loading several different policy files in batch
- running different implementations after each other, while they write rules to kernel in
different order
- also to some degree: runningthesame program with the same input multiple times
To get proper resultsone must load the policy when nothing has been loaded to kernel yet.
It's best to have a testing script being run as system init.
Failing to do that causes data to build up in internal kernel data structures. This
affects results for subsequent benchmarks, if the system is not rebooted in between.
When I applied the above method, order in which rules are written to kernel stopped being
that important. It still gives few percent of performance to have the rules sorted or
grouped by subject. Rule grouping also happens to enable nice implementation of rule
merging, so I did it anyway.
After a thorough testing and comparison with few alternative implementation, I believe to
have a final version of rule merging code. It has been uploaded to Github
(https://github.com/smack-team/smack/pull/39), so please review and comment on it. I'm
not sure if I shall send it to the list as well.
I will share my benchmark results in a separate e-mail.
Best regards,
Rafal Krypa
7:02 p.m.
On Mon, Jan 27, 2014 at 07:31:24PM +0100, Rafał Krypa wrote:
To get proper resultsone must load the policy when nothing has been
loaded to kernel yet. It's best to have a testing script being run
as system init. Failing to do that causes data to build up in
internal kernel data structures. This affects results for subsequent
benchmarks, if the system is not rebooted in between.
+1
When I applied the above method, order in which rules are written to
kernel stopped being that important. It still gives few percent of
performance to have the rules sorted or grouped by subject. Rule
grouping also happens to enable nice implementation of rule merging,
so I did it anyway.
+1
After a thorough testing and comparison with few alternative
implementation, I believe to have a final version of rule merging
code. It has been uploaded to Github
(https://github.com/smack-team/smack/pull/39), so please review and
comment on it. I'm not sure if I shall send it to the list as well.
I will share my benchmark results in a separate e-mail.
ACK. Your reasoning is solid. We'll stick to this solution now and
only move to another direction if there's ever a workload that would
need reconsideration.
/Jarkko
3155
days inactive
3175
days old
9 comments
4 participants
participants (4)
-
Jarkko Sakkinen -
José Bollo -
Rafał Krypa -
Rafał Krypa