search

kohler / click

The Click modular router: fast modular packet processing and analysis
Other
748 stars 321 forks source link

Possible optimization issue in rule compiler #312

Closed jonask84 closed 7 years ago

jonask84 commented 7 years ago

Hi!

So I stumbled on this issue purely at chance, but it seems like in certain particular scenarios some rules might be optimized away.

The attached testie exposes the issue.

In the test, two rulesets are created that are almost identical in their definition; the only difference is the second set contains a clause to allow traffic to the destination 1.1.1.2. Outside of that they should be identical.

Yet when the rulesets are compiled, we see that the 6th rule in the ruleset disappears from the second program. This can be seen both by inspecting the printout of the program (no path leads to output six (or [5]), and by passing a packet through that would normally match with rule six.

The cause of this is uncertain, though it would seem like we've stumbled upon a very rare corner case that causes the compiler to drop part of the program tree.

This has not been tested on the main click repo (so my apologies for that) - it has only been tested on the fork my company has made from it. Though I do not think any changes have been made to the rule compiler, so I fear this issue might be present in all branches.

compiler_issue.testie.txt

kohler commented 7 years ago

Hi, I can't replicate this. Here's your testie revised to work with vanilla Click. No issue appears.

compiler_issue.testie.txt

kohler commented 7 years ago

Is it possible that some of the issues I fixed in your PR were affecting this?

jonask84 commented 7 years ago

You're right, it seems to compile fine on my vanilla Click. Both before and after the rule loading change.

My apologies then, I'll have to go back and see where the PR compiler code deviates from the mainline.

I'll close this for now, and in case I find anything noteworthy I'll report back.

Thanks for looking at this!

tbarbette commented 7 years ago

Working on a regression test suite, figured adding a little test could be fun : 0060-ipfilter_compile

kohler commented 7 years ago

!!

Does 5b5a534 ever win (on small rule sets)?

On Fri, Dec 9, 2016 at 10:43 AM, Tom Barbette notifications@github.com wrote:

Working on a regression test suite, figured adding a little test could be fun : [image: 0060-ipfilter_compile] https://cloud.githubusercontent.com/assets/248961/21054574/8bbf73bc-be2e-11e6-9075-52c798618205.png

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/kohler/click/issues/312#issuecomment-266044933, or mute the thread https://github.com/notifications/unsubscribe-auth/AAZEF_HkGkf_qforu2Zw-gwS0Qyr0NYZks5rGXc3gaJpZM4LF7RA .

tbarbette commented 7 years ago

0060-ipfilter_compile 1

Nope. But I would not trust the difference for small values that much as the Y axis is the full Click execution time.

jonask84 commented 7 years ago

Thanks for looking at this Tom!

The data looks really cool! I have to add that there are situations in which the new optimization scheme will perform worse. It theoretically possible to create two rules/programs that are opposed in such a way that they cannot be compressed at all. That is if N is number of nodes, then N1 + N2 == optimized(N1 + N2).

If the entire ruleset is composed of rules like this, then the execution will be slower, as the new scheme will attempt to optimize the 'incompressible' rules several times over.