ematch API, u32 ematch, nbyte ematch, basic classifier

Jamal et al,

I attached 4 patches of a first ematch implementation. Comments and suggestions very much appreciated. Compiles but untested.

Patch 1: ematch API

API visible to classifier:

tcf_em_tree_validate(tp, tlv, tree)
tlv: ematches TLV
tree: temporary struct tcf_ematch_tree

Validates the data in the TLV and builds the ematch tree upon the temporary variable.

tcf_em_tree_change(tp, dst, src)
dst: destination ematch tree (from classifier private data)
src: source ematch tree (temporary tree from _validate)

Replaces the ematch tree in the classifier with the temporary tree.

tcf_em_tree_destroy(tp, tree)
Destroys an ematch tree

tcf_em_tree_dump(skb, tree, tlv_type)
tlv_type: T of ematches TLV (classifier specific)

Dumps the ematch tree to the skb with given tlv_type.

tcf_em_tree_match(skb, tree, res)
res: struct tcf_result *

Macro returning 1 if no ematches are configured, otherwise the tree is evaulated and 1 is returned if the tree matches.

The complete API is also visible if ematch is not configured but will result in empty macros/structures. Those need to be improved though.

API visible to ematches:

tcf_em_register(ops)
tcf_em_unregister(ops)

ematches must at least provide the following callbacks:

change, match

Optional callbacks are: destroy, dump

kind must be set to a unique ID, i thought about declaring 1..2^16 to ematches within the mainline tree and have the rest declared as to be used for private use to avoid collisions.

Patch 2: u32 ematch

Is an ematch based on the existing u32 match but allows to specify the layer and is able to read u32 values if alignment does not allow direct access. Additionally it supports the operands, eq, lt, gt. It is a few ticks slower than the existing match but worth it. However, it does not support the neat nexthdr via hashing as u32 does which is the main problem before u32 can make proper use of it.

Patch 3: nbyte ematch

Compares n bytes at specified offset. To be used for IPv6 address matches to avoid 4 ANDed u32 matches.

Patch 4: Basic Classifier

This is the most basic classifier possible doing nothing more than executing extensions and ematches. It follows the architecture of u32 and fw by storing a filter list in tp->root. This eventually makes fw obsolete once meta ematch is available. I didn't copy the u32/fw code but rather made use of the list.h.

pskbs are completely unhandled so far as I'm still not sure how to do it properly.

struct tcf_ematch_hdr

{
       __u16           handle;
       __u16           matchID;
       __u16           kind;
       __u8            flags;
       __u8            pad; /* currently unused */
};

you need both matchID and handle?

Both tcf_ematch_ops and tcf_ematch_hdr have kind;

Is data length stored somewhere?

Noticed indev still hanging there ;-> shouldnt that die by this patch?

Quoted 6 lines

tcf_em_tree_change(tp, dst, src)
dst: destination ematch tree (from classifier private data)
src: source ematch tree (temporary tree from _validate)

Replaces the ematch tree in the classifier with the temporary tree.

Seems to assume some owner of the ematch other than mother classifier. Recall the idea of ownership by classifier we discussed earlier which should be default if the ematch doesnt implement a ->change()

BTW, Is the assumption i can have a u32:
match
ematch
match
match
ematch

now gone? I couldnt tell.

Quoted 7 lines

tcf_em_tree_destroy(tp, tree)
Destroys an ematch tree

tcf_em_tree_dump(skb, tree, tlv_type)
tlv_type: T of ematches TLV (classifier specific)

Dumps the ematch tree to the skb with given tlv_type.

Same comments as in ->change().
if ematch doesnt implement a destroy or dump then mother classifier is responsible.

With std actions also this was an issue - at the moment dont have anything in any headers just to make it free for all - This way you could write a simple module that has zero dependency on an already compiled kernel. There would be standard practise where say 11 would mean something - but i suggest not to enforce it; the register() should probably spit some helpful message of who already has the number. you are trying to grab.

Quoted 1 line

Patch 2: u32 ematch

It does emulate a u32 node but not the classifier - which is a _lot_ more sophisticated (with multilevel trees of hashes etc). Maybe you should change its name to something like 32bit match.

Quoted 4 lines

Patch 3: nbyte ematch

Compares n bytes at specified offset. To be used for IPv6 address matches to avoid 4 ANDed u32 matches.

This looks useful.
My recommendation would be to have the metamatch as the first thing so we can kill indev and friends.

Quoted 1 line

Patch 4: Basic Classifier

Very inefficient, but serves the purpose of an example. [Even if you go as basic a hash as fw classifier you will do better]

* jamal <[email protected]> 2005-01-03 23:13

Right, I changed this already. change/dump/destroy are fully optional. Here's the latest API to the classifier:

change() (Optional)
Called if provided, otherwise ematch api allocates the data, stores it in m->data and sets m->datalen. Special Case: If TCF_EM_SIMPLE is set the ematch data consists of a simple u32 which means no allocation is required and the value is stored in m->data directly.

Note: I might add a special field to ematch_ops which can be set to the expected length of the ematch data so we have at least some basic sanity check. Thoughts?

match() (Must)
...

destroy() (Optional)
Called if provided, otheriwse m->data is freed in ematch api unless TCF_EM_SIMPLE is set.

dump() (Optional)
Called if provided, otherwise m->data is dumped onto the skb with m->datalen as L. Special handling again for TCF_EM_SIMPLE.

I think this makes it as simple as it can get while keeping the door open for complex ematches such as meta ematch.

Quoted 4 lines

Quoted 1 line

Patch 4: Basic Classifier

Very inefficient, but serves the purpose of an example. [Even if you go as basic a hash as fw classifier you will do better]

Fully agreed, nevertheless I think something like this is required to fill the gaps of u32 and fw.

Quoted 1 line

change() (Optional)

My thinking is:
It doesnt have to be simple 32 bit data.
If i pass you a struct and tell you what length it is, then you as the classifier dont know need to know anything about it. You just store mystruct as data and datalen from the TLV. you then pass the datastruct to match() - Of course the match() will have to know what that struct means.

Quoted 3 lines

destroy() (Optional)
Called if provided, otheriwse m->data is freed in ematch api unless TCF_EM_SIMPLE is set.

Again using the above logic, destroy becomes just kfree(mystruct)

Quoted 3 lines

dump() (Optional)
Called if provided, otherwise m->data is dumped onto the skb with m->datalen as L. Special handling again for TCF_EM_SIMPLE.

and dump becomes a matter of looking at datalen and encapsulating mystruct in a TLV without thinking about what the content is.

Quoted 1 line

Patch 4: Basic Classifier

Very inefficient, but serves the purpose of an example. [Even if you go as basic a hash as fw classifier you will do better]

* jamal <[email protected]> 2005-01-03 23:13

Quoted 2 lines

Very inefficient, but serves the purpose of an example. [Even if you go as basic a hash as fw classifier you will do better]

Might be worth to mention the motivation for this. fw and u32 will definitely perform much better on complex setups but many do not use u32 hashing not to mention even understand it or have large nfmark -> classid fw maps.

Many use u32 to match simple stuff as port numbers, dscp values or ip subnet addresses and create a new filter for every port/dscp value and for every address. Some even use temporary classes to emulate logic relations and this gets really slow. I have to get numbers first but a single basic filter with ORed matches is probably faster than a separate u32 filter for every case.

Sure, once u32
has ematch support it gets better and the hashing shouldn't have too much influence even if it's unused.. We can see what to do once u32 can handle ematches.

Quoted 6 lines

Many use u32 to match simple stuff as port numbers, dscp values or ip subnet addresses and create a new filter for every port/dscp value and for every address. Some even use temporary classes to emulate logic relations and this gets really slow. I have to get numbers first but a single basic filter with ORed matches is probably faster than a separate u32 filter for every case.

I am pretty sure someone who knows u32 well can outperform you (in the scenarios where u32 works using AND etc).
Start hitting 50K rules then lets talk ;->

If your intent is to write an ematch holder, then it would be worth to at least go as far as making it some basic hash - as basic as fw does; where collision leads toa linked list. If it is just to show an example, then it is fine.

* jamal <[email protected]> 2005-01-04 08:22

Quoted 5 lines · Thomas Graf

I am pretty sure someone who knows u32 well can outperform you (in the scenarios where u32 works using AND etc).
Start hitting 50K rules then lets talk ;->

Sure but I'd call a filter with 50K ANDed rules an unlikely scenario ;->

In most cases logic will beat brute force. I used to have a u32 setup with 4K matches and hashing, it was not only error prone but could be replaced with 12 egp filters gaining 90kpps. Why's that? Simply because it was easier to optimize the logic behind it. egp itself is terribly slow compared to u32.

Quoted 4 lines

If your intent is to write an ematch holder, then it would be worth to at least go as far as making it some basic hash - as basic as fw does; where collision leads toa linked list. If it is just to show an example, then it is fine.

Using what key? We have no knowledge about what the ematches want to see or not.

I think this is a debate that can be easily settled ;-> Agreed logic will beat brute force smartness and u32 is not exactly for the faint hearted. And its usability is extremely poor - but lets maintain its power as is.

Quoted 2 lines

Using what key? We have no knowledge about what the ematches want to see or not.

Ok, good question ;->
Maybe you should have own some 32 bit key?

* TCF_EM_SIMPLE flag which marks an ematch config as simple, meaning that the data consists of a u32 value.

Quoted 3 lines

* TCF_EM_SIMPLE flag which marks an ematch config as simple, meaning that the data consists of a u32 value.

This is 1 of 2 parts i think thats still an issue; otherwise looks very good.
Why do i need to signal something as simple? AND why does it have to be 32 bit type - what edge does that give you?

I should be able to specify a struct with two 32 bits and encap it in a TLV and the classifier can treat it the same way - it knows the type and length - thats sufficient to create, destroy and dump.

The other issue is still on the ematch/match interleaving i.e i should be able to say something along the lines:

//simple slammer-worm or code-red ACL detector rule //using u32 classifier and ematches
(match ip protocol udp port 1434 AND
ematch packetlen minsize 404 maxsize 404) OR (match ip protocol tcp http AND
ematch urlscanner "*.ida")
action ipt -j ULOG "Virus detected and dropped" action drop

Not a very good example - but you can see how powerfull this is when you can quickly use a string scanner such as the one you have as an ematch while maintaining u32 as is.

* jamal <[email protected]> 2005-01-04 22:12

Quoted 2 lines

Why do i need to signal something as simple? AND why does it have to be 32 bit type - what edge does that give you?

You don't have to, providing a 32bit data chunk without TCF_EM_SIMPLE set will simply result in allocating & copy. It's an optimization, nothing more.

Quoted 3 lines

Not a very good example - but you can see how powerfull this is when you can quickly use a string scanner such as the one you have as an ematch while maintaining u32 as is.

Basically you could do that already with the basic classifier but I understand your concern and it would be neat to benefit from u32's hashing. There are 2 options:
1) We make u32 hold multiple ematch trees, a u32 key can be of 3
kinds: u32/ematch/container. It's kind of a hack and not very fast due to a lot of stack movement.

2) We make the existing u32 match be an ematch which I already did expect for the nexthdr bits. That is the select will simply be replaced by an ematch tree. I'll take a look into how we could have the classifier take influence on the ematches config data. One possibiliy is to have a struct transfered via map which contains useful data such as offset to next header (u32/rsvp). I have to think about this a little more though.

Personally I'm all for 2) because it's just cleaner and easier to maintain.

It's probably the best to not to use the u32 ematch I wrote (which I renamed to cmp) but to write a new one behaving exactly the same as the existing u32 match.

Attached cmp ematch (formerly u32), it was on diet for a while and is quite smallish now.

include/linux/pkt_cls.h +14 -0

@@ -366,4 +367,28 @@
 #define TCF_EM_INVERT	(1<<3)
 #define TCF_EM_SIMPLE	(1<<4)
 
+struct tcf_em_cmp
+{
+	__u32		val;
+	__u32		mask;
+	__u16		off;
+	__u8		align;
+	__u8		layer:4;
+	__u8		opnd:4;
+};
+
+enum
+{
+	TCF_EM_ALIGN_U8  = 1,
+	TCF_EM_ALIGN_U16 = 2,

include/linux/pkt_cls.h +0 -0

 #endif

diff -Nru linux-2.6.10-bk6.orig/include/net/pkt_cls.h linux-2.6.10-bk6/include/net/pkt_cls.h

include/net/pkt_cls.h +20 -0

@@ -270,6 +270,36 @@
 
 #endif /* CONFIG_NET_EMATCH */
 
+static inline u32 tcf_read_bucket(u8 *ptr, u8 align)
+{
+	switch (align) {
+		case TCF_EM_ALIGN_U8:
+			return *ptr;
+		case TCF_EM_ALIGN_U16:
+			return (*ptr << 8) | *(ptr+1);
+		case TCF_EM_ALIGN_U32:
+			return (*ptr << 24) | (*(ptr+1) << 16) |
+				(*(ptr+2) << 8) | *(ptr+3);
+	}
+	return 0;
+}
+
+static inline u8 * tcf_get_base_ptr(struct sk_buff *skb, u8 layer)
+{
+	switch (layer) {
+		case 0:
+			return skb->data;
+		case 1:

Quoted 5 lines

* jamal <[email protected]> 2005-01-04 22:12

Quoted 2 lines

Why do i need to signal something as simple? AND why does it have to be 32 bit type - what edge does that give you?

Quoted 3 lines

You don't have to, providing a 32bit data chunk without TCF_EM_SIMPLE set will simply result in allocating & copy. It's an optimization, nothing more.

Sorry i missed that. Isnt it still unecessary though? You should be able to pass L=4 and not need the speacial treatment, no?

Quoted 3 lines

1) We make u32 hold multiple ematch trees, a u32 key can be of 3
kinds: u32/ematch/container. It's kind of a hack and not very fast due to a lot of stack movement.

Indeed this is what i was thinking of.
The only added overhead I can think of is when processing a series of u32 keys _within the same selector_ (not across selectors), you check if its u32 native and execute localy (as is done now) or transfer the check to the ematch defined in that key and continue to next key based on the ematchs return code + the logical operation.

Quoted 7 lines

2) We make the existing u32 match be an ematch which I already did expect for the nexthdr bits. That is the select will simply be replaced by an ematch tree. I'll take a look into how we could have the classifier take influence on the ematches config data. One possibiliy is to have a struct transfered via map which contains useful data such as offset to next header (u32/rsvp). I have to think about this a little more though.

This could be done in addition to #1. I see #1 as more important for u32 but not so for things like fwmark, tcindex which should fizzle away with meta ematch. I think the danger is in trying to replicate u32 as an ematch; if somehow you can loop back and use the real u32 code, then fine. I feel it being non-trivial to do so.
Like i said earlier, theres a lot of power in u32 other than in basic matching.

I think #2 is better for other classifiers which were already doomed anyways. #1 is important for u32 and perhaps other classifiers like rsvp and route. And yes, #1 is more work ;->

hang on:-> No dont rewrite u32 please. Your cmp is good for the basic matches that u32 does, but is _nowhere_ close to being able to do what u32 can when used properly.

I Should be able to compile a new ematch as a module in an already running kernel. So, other than generic stuff for ematches, things like TCF_EM_CMP should not be in that enumeration.

Which means the above should go in its own file; probably create a include/linux/tc_ematch directory with a file of sort tcf_em_cmp.h which holds all the above.

And all this also goes in that header file as well.

Most importantly I don't want to touch any of the hashing code in u32. I really like and it should stay as it is. The existing u32 match can be easly made an ematch so this would safe us the extra work in u32 to implement logic relations again and to fiddle with complicated selector TLVs. The only problem with this is the nexthdr bits because it relies on the hashing code. So we have to make this data available to the ematch which is actually not a bad idea anyway. So I'm thinking about introducing a new structure tcf_em_pkt_info or alike which carries some additional information found out by the classifiers which can be used by ematches. This can be information about the next header, already extracted dscp values, etc.

Here's what I mean, it moves the u32 match as-is to an ematch so it benefits from logic relations, inversion and can be used from other classifiers as well. All we have to do is set info->ptr and info->nexthdr to ptr respetively off2 before we evaluate the ematch tree. The pkt_info struct is then passed to tcf_em_tree_match and made available to every ematch.

Thoughts?

* jamal <[email protected]> 2005-01-05 08:33

Quoted 2 lines

Sorry i missed that. Isnt it still unecessary though? You should be able to pass L=4 and not need the speacial treatment, no?

Agreed, but the ematch might expect an allocated block. Assuming the data is variable and sometimes is L=4, sometimes L=16 the ematch requires special handling because m->data might hold the value directly or a pointer depending on datalen.

Quoted 4 lines

Quoted 3 lines

1) We make u32 hold multiple ematch trees, a u32 key can be of 3
kinds: u32/ematch/container. It's kind of a hack and not very fast due to a lot of stack movement.

Quoted 6 lines

Indeed this is what i was thinking of.
The only added overhead I can think of is when processing a series of u32 keys _within the same selector_ (not across selectors), you check if its u32 native and execute localy (as is done now) or transfer the check to the ematch defined in that key and continue to next key based on the ematchs return code + the logical operation.

Exactly, does the performance gap come with any advantage? No.

That's
why I don't like it.

Quoted 8 lines

Quoted 7 lines

2) We make the existing u32 match be an ematch which I already did expect for the nexthdr bits. That is the select will simply be replaced by an ematch tree. I'll take a look into how we could have the classifier take influence on the ematches config data. One possibiliy is to have a struct transfered via map which contains useful data such as offset to next header (u32/rsvp). I have to think about this a little more though.

Quoted 7 lines

This could be done in addition to #1. I see #1 as more important for u32 but not so for things like fwmark, tcindex which should fizzle away with meta ematch. I think the danger is in trying to replicate u32 as an ematch; if somehow you can loop back and use the real u32 code, then fine. I feel it being non-trivial to do so.
Like i said earlier, theres a lot of power in u32 other than in basic matching.

Most importantly I don't want to touch any of the hashing code in u32.

I really like and it should stay as it is. The existing u32 match can be easly made an ematch so this would safe us the extra work in u32 to implement logic relations again and to fiddle with complicated selector TLVs. The only problem with this is the nexthdr bits because it relies on the hashing code. So we have to make this data available to the ematch which is actually not a bad idea anyway. So I'm thinking about introducing a new structure tcf_em_pkt_info or alike which carries some additional information found out by the classifiers which can be used by ematches. This can be information about the next header, already extracted dscp values, etc.

This would give us the chance to add a very small em_u32.c (~40 lines) doing exactly the same as the current u32 match and have the u32 selector replaced with an ematch tree at no additional cost. Backward compatibility is as easy as creating a flat ANDed ematch tree.

Note: The u32 ematch I'm talking about is not the cmp ematch, cmp is more advanced but also slightly slower.

Thoughts?

Quoted 3 lines

I think #2 is better for other classifiers which were already doomed anyways. #1 is important for u32 and perhaps other classifiers like rsvp and route. And yes, #1 is more work ;->

Why is it better? What's the advantage?

Quoted 3 lines

hang on:-> No dont rewrite u32 please. Your cmp is good for the basic matches that u32 does, but is _nowhere_ close to being able to do what u32 can when used properly.

Right, that's why I now call it cmp and the existing u32 match becomes the u32 ematch.

Quoted 3 lines

I Should be able to compile a new ematch as a module in an already running kernel. So, other than generic stuff for ematches, things like TCF_EM_CMP should not be in that enumeration.

It's not a requirement to put it there but we need to manage the assigned types for ematches in mainline anyway.

Quoted 1 line

And all this also goes in that header file as well.

I put it here because it might be very useful for other ematches or further classifiers, you name it. tcf_get_base_ptr is used by nbyte ematch for example.

So the issue is whether its by ref or copy? Maybe thats what the flag is for then. My view is that _everything_ for ematches should be by copy for simplicty.

Oh, yes;-> the one check in the datapath comes with a _huge_ advantage even all that you had was old style matches because now you have embeded logical operations which are more than just the old AND. But more importantly you can use ematches as well to influence the existing u32 tree path.

What i am reading is you see more work involved. Is this correct?

There is one issue which i think is the big source of our lack of sync:
You conclude people are gonna want to use the logical tree building scheme you are putting in to put together matches and ematches. U32 _already_ has a tree building scheme which is very very flexible.

Again, u32 classifier is not just matches; the more interesting thing is the layout of the rules that it can be taught to do.
I think the ematch which emulates the std u32 match is of course valuable to have but it _doesnt_ deserve the same name.

Thinking more about it; not sure why you would even bother managing them. Everything runs at the same kernel privilege level. I am not sure you want to have certain things that can only be built when recompiling the kernel

* jamal <[email protected]> 2005-01-06 08:47

If we do everything as ref we'll be allocating 4 byte chunks or we introduce a storage u32 which pollutes the structure. I don't like that given that the transfer of a single u32 is probably the most common for all those smallish ematches for a specific thing. For simplicity, you don't even notice if you're not aware of that it can be of help so I don't think we're losing any simplicity here.

Missunderstanding here, I meant is there any advantage in having multiple ematch trees (interleaved) over just making the existing u32 key an ematch and have the selector (with the hashing bits extracted) with one ematch tree.

1) extract hashing bits out of selector and move it into a new TLV.
2) Replace the foreach key match loop with an ematch_tree match

3) Fill out a pkt_info struct with ptr and off2 so we don't lose hashing capabilities

4) Add backward compat code. Old selector must be transformed into a flat ematch tree and the hashing bits must be extracted and stored in the new struct.

The most difficult part is to do the Kconfig dependencies in a smart way ;->

Quoted 4 lines

Again, u32 classifier is not just matches; the more interesting thing is the layout of the rules that it can be taught to do.
I think the ematch which emulates the std u32 match is of course valuable to have but it _doesnt_ deserve the same name.

Stupid terms, em_u32.c is a replacement for the u32 key and it has exactly the same behaviour. I'll be happy to rename it but as you know I really suck at naming things ;->

Quoted 4 lines

Thinking more about it; not sure why you would even bother managing them. Everything runs at the same kernel privilege level. I am not sure you want to have certain things that can only be built when recompiling the kernel

Well, we have exactly the same issues as with TLV types. I don't see why one would need to recompile things. The enumeration is for ematches included in the kernel tree.

Quoted 2 lines

3) Fill out a pkt_info struct with ptr and off2 so we don't lose hashing capabilities

And this is why i dont like it.

I think the u32 changes are one-shot if you want to avoid lotsa #ifdefs. Someone sends you a old sel, then convert it to a new one for storage. Dumping is a little trickier, need some way to recognize old style request.

The trick would be to always use sel2 and present no kconfig options for back compat. We need to figure out how to recognize an old style dump and we are set.

Above you are trying to insert off2 into the info (what i said i didnt like) - how are you going to achieve the same with a standalone en_u32 from say you basic classifier?

* jamal <[email protected]> 2005-01-07 08:45

Quoted 4 lines

Quoted 2 lines

3) Fill out a pkt_info struct with ptr and off2 so we don't lose hashing capabilities

And this is why i dont like it.

What's the reason for not liking it? I know it's not a perfect solution in terms of layers but having the classifier sharing already gathered information to an ematch is not a bad thing.

The easiest way is to introduce a new TLV type and regard configuration requests carrying the old type in compatibility mode.

Quoted 3 lines

The trick would be to always use sel2 and present no kconfig options for back compat. We need to figure out how to recognize an old style dump and we are set.

Given we always use the new method by converting old style parameters and we use em_u32 as u32 key we would need to put a dependcy on ematch && em_u32 for cls_u32.

Quoted 3 lines

Above you are trying to insert off2 into the info (what i said i didnt like) - how are you going to achieve the same with a standalone en_u32 from say you basic classifier?

I won't and it's not necessary, one can use u32 if he requires the nexthdr capabilities or otherwise use em_cmp support the skb layers. (Which i know is not perfect since the pointers to those layers are not provided all the time).

I think its _a hack_ Thomas ;-> Mostly because it has dependency on u32. off2 doesnt exist on any other classifier and the basic ematch should be usable by any classifier.

Why not just have a check to see if it is native match then not to call up any ematch executing code. Have the native match maybe be of kind 0. Have the return code for ematch lookup return something that indicates that you need to match using local u32 instead of ematch.

* jamal <[email protected]> 2005-01-10 08:26

Quoted 3 lines

I think its _a hack_ Thomas ;-> Mostly because it has dependency on u32. off2 doesnt exist on any other classifier and the basic ematch should be usable by any classifier.

It does not, u32 does have a dependency on em_u32 but not vice versa. em_u32 is perfectly useful even without nexthdr functionality since this is the way it is used today in 90% of the cases and it should be a little bit faster than em_cmp but also a bit less powerful. On top of that, rsvp could provide this information as well so one could extend rsvp with em_u32 ematches. I think we should not think of it as being dependant on off2 but rather as it is able to use information from a underlying layer.

Quoted 5 lines

* jamal <[email protected]> 2005-01-10 08:26

Quoted 3 lines

I think its _a hack_ Thomas ;-> Mostly because it has dependency on u32. off2 doesnt exist on any other classifier and the basic ematch should be usable by any classifier.

Quoted 8 lines

It does not, u32 does have a dependency on em_u32 but not vice versa. em_u32 is perfectly useful even without nexthdr functionality since this is the way it is used today in 90% of the cases and it should be a little bit faster than em_cmp but also a bit less powerful. On top of that, rsvp could provide this information as well so one could extend rsvp with em_u32 ematches. I think we should not think of it as being dependant on off2 but rather as it is able to use information from a underlying layer.

Ok, you make a convincing arguement ;-> No more concerns from my side. Churn that code!

Ok, you make a convincing arguement ;-> No more concerns from my side. Churn that code!

Found some cycles today and wrote the meta ematch. It tried to find a good compromise between speed and power.

So far I added the following matching possibilies:
- random
- load average (0,1,2)
- dev (numeric and string)
- indev (numeric and string)
- realdev (numeric and string)
- skb priority
- ... protocol
- ... security
- ... pkttype (to easly match on multicast/broadcast)
- ... pktlen
- ... datalen
- ... maclen
- netfilter mark
- ... cache
- ... conntrack info
- ... debug variable
- tc index
- ... verdict
- ... classid
- routing classid
- .... iif

Yet to come are more routing and socket attributes such as queue sizes, backlog sizes, neighbour attribute of the route found, ...

It is also possible to compare two kernel meta values, e.g realdev equals dev.

Numeric matches may be modified via shift and mask operators to for example only consider a part of nfmark.

Binary matches may have a shift modifier to only consider a certain amount of the data, e.g. "eth1" with shift 1 would end up with "eth". I added this because I wanted something like eth% but didn't want to implement expensive string operations.

If its not obvious, random and loadavg are intended for load balancing purposes, i.e.

Looks great. I have a few doubts about about the set of chosen values though. Things like nf_debug and nf_cache were never meant to be userspace-visible. What about backwards compatibility if we want to remove it, or some other more meaningful value where just returning 0 wouldn't be the same ?

- var_dev sets dst->value to dev->name, meta_var_destroy will try to free dev->name.

- meta_int_change only uses 32 bit, but dst->value is unsigned long (64 bit on 64-bit arches). nfmark for example is unsigned long, so you should also use *(unsigned long *).

- for the same reason meta_int_compare should return long not int

* Patrick McHardy <[email protected]> 2005-01-13 19:54

Quoted 7 lines

Looks great. I have a few doubts about about the set of chosen values though. Things like nf_debug and nf_cache were never meant to be userspace-visible. What about backwards compatibility if we want to remove it, or some other more meaningful value where just returning 0 wouldn't be the same ?

It is indeed problematic and they should be marked as "for debugging purposes (unreliable)" but at least nf_debug and nfctinfo are very useful for debugging.

Quoted 4 lines

- var_dev sets dst->value to dev->name, meta_var_destroy will try to free dev->name.

The dst meta_value is the l_value/r_lvalue from em_meta_match and never gets destroyed. I reused meta_data to store address & length. It might be a good idea to make a new struct for this to make it more readable though.

Quoted 5 lines

- meta_int_change only uses 32 bit, but dst->value is unsigned long (64 bit on 64-bit arches). nfmark for example is unsigned long, so you should also use *(unsigned long *).

Doesn't work when size of long differs between kernel and userspace. I'm aware of this but it seems everyone is using int anyway for nfmark, so yes this indeed limits the use of nfmark match to only 32 bits on 64bit machines. The proper way is to introduce a new type TCF_EM_TYPE_INT64 and access nfmark over it but I didn't want to create a new type just because of this special case. We can always add it later as addition to the 32bit version.

True. nfctinfo is even useful for more, the direction of a connection might be interesting. connmark, conntrack counters, src-ip before SNAT etc. might also be interesting, but they are horrible to implement cleanly because any dependency on ip_conntrack_lock will automatically load ip_conntrack. Perhaps we should add something like nf_ct_get_afinfo() to return a set of conntrack operations to nf_conntrack.

For things beside the nf* fields: I think we should make it very clear that everything that isn't already visible to userspace in some way, and thus won't disappear (like priority, nfmark, load average ...), can get changed/removed any time.

Quoted 5 lines

The dst meta_value is the l_value/r_lvalue from em_meta_match and never gets destroyed. I reused meta_data to store address & length. It might be a good idea to make a new struct for this to make it more readable though.

Looks good to me already. I only looked at the diff, so I didn't really follow the codepath.

Shouldn't be too hard to get right. In the kernel you can decide based on RTA_PAYLOAD. Userspace needs some other way to notice it is running as a 32-bit binary on a 64-bit kernel, but that's something you can't solve in the kernel anyway.

Here's a revised patch. I fixed the numeric comparison issues and added meta_obj instead of using meta_data to give a better impression on the difference of a comparable object and meta data definitions.

Quoted 4 lines

Here's a revised patch. I fixed the numeric comparison issues and added meta_obj instead of using meta_data to give a better impression on the difference of a comparable object and meta data definitions.

I scanned the code very quickly; lets start with the big picture then i will send some more comments:
Did i understand this correctly that a metamatch MUST have a lvalue + rvalue pair?

What if all i wanted to say was
..
ematch indev eth0

The lvalue will be TCF_META_ID_INDEV and your rvalue will be TCF_META_TYPE_VAR with "eth0" as payload(TCF_EM_META_RVALUE). TCF_EM_META_LVALUE will be unused in this case.

Quoted 4 lines

The lvalue will be TCF_META_ID_INDEV and your rvalue will be TCF_META_TYPE_VAR with "eth0" as payload(TCF_EM_META_RVALUE). TCF_EM_META_LVALUE will be unused in this case.

ok - i get it. So the rvalue is basically just the data that needs to be compared against. rvalue confused me a little. If you had called it meta_data i would have got it right away. But now that you explain it, makes sense.

I am not sure iam following yet:

So in the case of indev, you would need to
- get indev ifindex from skb
- get indev name from skb
- compare the two??

Actually it may be a little overkill to have those two as separate entities with their own headers etc, no? Why not just store it in the same fashion you transported it from/to user space?

The rvalue may also point to a metadata in the kernel. This gets useful when comparing dev against real dev or if nfmark, tcindex, you name it carries a ifindex for example. It would even be possible to compare two strings from userspace but that wouldn't make sense. The only difference between lvalue and rvalue is that the lvalue carries the operand.

Quoted 8 lines

I am not sure iam following yet:

So in the case of indev, you would need to
- get indev ifindex from skb
- get indev name from skb
- compare the two??

Quoted 7 lines

Quoted 7 lines

I am not sure iam following yet:

So in the case of indev, you would need to
- get indev ifindex from skb
- get indev name from skb
- compare the two??

Can you explain the above in context of indev = "eth0"? I am still not sure i get it:

diff -Nru linux-2.6.10-bk14.orig/include/linux/tc_ematch/tc_em_meta.h linux-2.6.10-bk14/include/linux/tc_ematch/tc_em_meta.h

include/linux/tc_ematch/tc_em_meta.h +6 -0

+enum
+{
+	TCF_META_TYPE_VAR,
+	TCF_META_TYPE_INT,
+	__TCF_META_TYPE_MAX
+};

diff -Nru linux-2.6.10-bk14.orig/net/sched/em_meta.c linux-2.6.10-bk14/net/sched/em_meta.c

net/sched/em_meta.c +2 -0

+
+struct meta_obj

net/sched/em_meta.c +4 -0

+/**************************************************************************
+ * System status & misc
+ **************************************************************************/
+

net/sched/em_meta.c +12 -0

+}
+
+static int meta_int_loadavg_0(struct sk_buff *skb, struct tcf_pkt_info *info,
+			      struct meta_value *v, struct meta_obj *dst)
+{
+	dst->value = fixed_loadavg(avenrun[0]);
+	return 0;
+}
+
+static int meta_int_loadavg_1(struct sk_buff *skb, struct tcf_pkt_info *info,
+			      struct meta_value *v, struct meta_obj *dst)
+{

net/sched/em_meta.c +10 -0

+/**************************************************************************
+ * Device names & indices
+ **************************************************************************/
+
+static inline int int_dev(struct net_device *dev, struct meta_obj *dst)
+{
+	if (unlikely(dev == NULL))
+		return -1;
+
+	dst->value = dev->ifindex;

net/sched/em_meta.c +4 -0

+static inline struct meta_ops * meta_ops(struct meta_value *v)
+{
+	return &__meta_ops[meta_type(v)][meta_id(v)];
+}

Quoted 2 lines

diff -Nru linux-2.6.10-bk14.orig/include/linux/tc_ematch/tc_em_meta.h linux-2.6.10-bk14/include/linux/tc_ematch/tc_em_meta.h

[..]

include/linux/tc_ematch/tc_em_meta.h line 26

Quoted 11 lines

include/linux/tc_ematch/tc_em_meta.h +11 -0

+struct tcf_meta_val
+{
+	__u16			kind;
+	__u8			shift;
+	__u8			op;
+};
+
+#define TCF_META_TYPE_MASK	(0xf << 12)
+#define TCF_META_TYPE(kind)	(((kind) & TCF_META_TYPE_MASK) >> 12)
+#define TCF_META_ID_MASK	0x7ff
+#define TCF_META_ID(kind)	((kind) & TCF_META_ID_MASK)

Does it smell like there may be endianess issues? Probably not.

include/linux/tc_ematch/tc_em_meta.h line 43

Quoted 1 line

include/linux/tc_ematch/tc_em_meta.h +1 -0

+	TCF_META_ID_DEV,

Since filters are attached to devices - is TCF_META_ID_DEV of any value?

net/sched/em_meta.c line 35

Quoted 5 lines

net/sched/em_meta.c +5 -0

+struct meta_value
+{
+	struct tcf_meta_val	hdr;
+	unsigned long		val;
+	unsigned int		len;

Those last two look like meta_obj you defined above

net/sched/em_meta.c line 60

Quoted 1 line

net/sched/em_meta.c +1 -0

+	return (v + (FIXED_1/200)) >> FSHIFT;

200 has some magic connotation to it - a define somewhere perhaps?

Theres a lot of parameters not used at all in these calls .get calls. So far i have seen dst->value and some of the skb fields used. I apologize, I normally dont pick on these things - so if you have future plans for why you are passing those, keep them and ignore the comment.

net/sched/em_meta.c line 103

Quoted 7 lines

net/sched/em_meta.c +7 -0

+static inline int var_dev(struct net_device *dev, struct meta_obj *dst)
+{
+	if (unlikely(dev == NULL))
+		return -1;
+
+	dst->value = (unsigned long) dev->name;
+	dst->len = strlen(dev->name);

So if device dissapears ... what happens to the pointer?

net/sched/em_meta.c line 372

Quoted 8 lines

net/sched/em_meta.c +8 -0

+static void meta_var_apply_extras(struct meta_value *v,
+				  struct meta_obj *dst)
+{
+	int shift = v->hdr.shift;
+
+	if (shift && shift < dst->len)
+		dst->len -= shift;
+}

whats the purpose to the extras?

Quoted 4 lines

net/sched/em_meta.c +4 -0

+static int em_meta_match(struct sk_buff *skb, struct tcf_ematch *m,
+			 struct tcf_pkt_info *info)
+{
+	int r;

net/sched/em_meta.c line 469

Quoted 6 lines

net/sched/em_meta.c +6 -0

+	struct meta_match *meta = (struct meta_match *) m->data;
+	struct meta_obj l_value, r_value;
+
+	if (meta_get(skb, info, &meta->lvalue, &l_value) < 0 ||
+	    meta_get(skb, info, &meta->rvalue, &r_value) < 0)
+		return 0;

This is one part that confused me in my earlier email

Ok, I have to admit I am not a friend of too-friendly, which is one of the faults IMO with netfilter; however, this would have joenetfilterfireman sweat a little too profusely.
I think you could add a new metafield in 31 seconds. I could probably do it in 95 seconds. Would be ideal to get average janeorjoenetfilterfireman to do it in 30 minutes - I dont think you are there.

* jamal <[email protected]> 2005-01-16 11:11

Quoted 17 lines · Thomas Graf

Quoted 2 lines

diff -Nru linux-2.6.10-bk14.orig/include/linux/tc_ematch/tc_em_meta.h linux-2.6.10-bk14/include/linux/tc_ematch/tc_em_meta.h

[..]

include/linux/tc_ematch/tc_em_meta.h line 26

Quoted 11 lines

include/linux/tc_ematch/tc_em_meta.h +11 -0

+struct tcf_meta_val
+{
+	__u16			kind;
+	__u8			shift;
+	__u8			op;
+};
+
+#define TCF_META_TYPE_MASK	(0xf << 12)
+#define TCF_META_TYPE(kind)	(((kind) & TCF_META_TYPE_MASK) >> 12)
+#define TCF_META_ID_MASK	0x7ff
+#define TCF_META_ID(kind)	((kind) & TCF_META_ID_MASK)

Does it smell like there may be endianess issues? Probably not.

Not really as long as iproute2 uses the same byte ordering. It has the same issues as all other rtnetlink users.

Quoted 3 lines

include/linux/tc_ematch/tc_em_meta.h line 43

Quoted 1 line

include/linux/tc_ematch/tc_em_meta.h +1 -0

+	TCF_META_ID_DEV,

Since filters are attached to devices - is TCF_META_ID_DEV of any value?

Yes, to compare against realdev and indev.

Quoted 7 lines

net/sched/em_meta.c line 35

Quoted 5 lines

net/sched/em_meta.c +5 -0

+struct meta_value
+{
+	struct tcf_meta_val	hdr;
+	unsigned long		val;
+	unsigned int		len;

Those last two look like meta_obj you defined above

Yes, they once were but the code is more readable this way because one cannot mistake meta_obj (temporary data) with the data/len in meta_value (persistent).

Quoted 3 lines

net/sched/em_meta.c line 60

Quoted 1 line

net/sched/em_meta.c +1 -0

+	return (v + (FIXED_1/200)) >> FSHIFT;

200 has some magic connotation to it - a define somewhere perhaps?

I coped this from the code for procfs ;->

Quoted 4 lines

Theres a lot of parameters not used at all in these calls .get calls. So far i have seen dst->value and some of the skb fields used. I apologize, I normally dont pick on these things - so if you have future plans for why you are passing those, keep them and ignore the comment.

I do have plans but for more complicated meta matches and they will take some time and will get pushed in a second iteration.

Quoted 9 lines

net/sched/em_meta.c line 103

Quoted 7 lines

net/sched/em_meta.c +7 -0

+static inline int var_dev(struct net_device *dev, struct meta_obj *dst)
+{
+	if (unlikely(dev == NULL))
+		return -1;
+
+	dst->value = (unsigned long) dev->name;
+	dst->len = strlen(dev->name);

So if device dissapears ... what happens to the pointer?

Not possible, the pointer is only legal to use while classifying, dst is on the stack of meta_match and the device cannot disappear while classyfing.

Quoted 10 lines

net/sched/em_meta.c line 372

Quoted 8 lines

net/sched/em_meta.c +8 -0

+static void meta_var_apply_extras(struct meta_value *v,
+				  struct meta_obj *dst)
+{
+	int shift = v->hdr.shift;
+
+	if (shift && shift < dst->len)
+		dst->len -= shift;
+}

whats the purpose to the extras?

"eth0" shift 1 gets "eth" so we can emulate eth%. It will also get useful for ipv6 routing bits to implement the prefix.

Quoted 4 lines

Quoted 4 lines

net/sched/em_meta.c +4 -0

+static int em_meta_match(struct sk_buff *skb, struct tcf_ematch *m,
+			 struct tcf_pkt_info *info)
+{
+	int r;

Quoted 8 lines

net/sched/em_meta.c line 469

Quoted 6 lines

net/sched/em_meta.c +6 -0

+	struct meta_match *meta = (struct meta_match *) m->data;
+	struct meta_obj l_value, r_value;
+
+	if (meta_get(skb, info, &meta->lvalue, &l_value) < 0 ||
+	    meta_get(skb, info, &meta->rvalue, &r_value) < 0)
+		return 0;

This is one part that confused me in my earlier email

It transforms the meta data info in (l|r)value into 2 temporary meta objects for comparing. mgiht help if i find a better name.

Quoted 7 lines

Ok, I have to admit I am not a friend of too-friendly, which is one of the faults IMO with netfilter; however, this would have joenetfilterfireman sweat a little too profusely.
I think you could add a new metafield in 31 seconds. I could probably do it in 95 seconds. Would be ideal to get average janeorjoenetfilterfireman to do it in 30 minutes - I dont think you are there.

ideas? a step-by-step guide in Documentation/? ;->

Quoted 2 lines

Not really as long as iproute2 uses the same byte ordering. It has the same issues as all other rtnetlink users.

wont harm to do a quick test if you have hardware. pedit for example still has some occasional issues some issues with big endian which i havent had time to chase.

Quoted 5 lines

Quoted 3 lines

net/sched/em_meta.c line 60

Quoted 1 line

net/sched/em_meta.c +1 -0

+	return (v + (FIXED_1/200)) >> FSHIFT;

200 has some magic connotation to it - a define somewhere perhaps?

I coped this from the code for procfs ;->

know why they have that number? It must have some significance - or maybe someone just stuck their hand in the air and measured 200? ;->

Quoted 5 lines

net/sched/em_meta.c +5 -0

+static int meta_int_loadavg_2(struct sk_buff *skb, struct tcf_pkt_info *info,
+			      struct meta_value *v, struct meta_obj *dst)
+{
+	dst->value = fixed_loadavg(avenrun[2]);
+	return 0;

Quoted 2 lines

+}

Theres a lot of parameters not used at all in these calls .get calls. So far i have seen dst->value and some of the skb fields used. I apologize, I normally dont pick on these things - so if you have future plans for why you are passing those, keep them and ignore the comment. BTW, it would probably be useful to return some mnemonic instead of 0.

net/sched/em_meta.c line 103

Quoted 9 lines

net/sched/em_meta.c +7 -0

+static inline int var_dev(struct net_device *dev, struct meta_obj *dst)
+{
+	if (unlikely(dev == NULL))
+		return -1;
+
+	dst->value = (unsigned long) dev->name;
+	dst->len = strlen(dev->name);

So if device dissapears ... what happens to the pointer?

Quoted 9 lines

net/sched/em_meta.c +9 -0

+static int meta_int_compare(struct meta_obj *a, struct meta_obj *b)
+{
+	/* Let gcc optimize it, the unlikely is not really based on
+	 * some numbers but jump free code for missmatches seems
+	 * more logical.
+	 */
+	if (unlikely(a == b))
+		return 0;
+	else if (a < b)

net/sched/em_meta.c line 386

Quoted 6 lines

net/sched/em_meta.c +4 -0

+		return -1;
+	else
+		return 1;
+}

Would be very useful to return mnemonics for readability.

jamal wrote:

Quoted 1 line

BTW, it would probably be useful to return some mnemonic instead of 0.

Returning 0 for success and negative error codes is perfectly fine as long as you don't need any magic numbers (1, 2, ..).

Quoted 9 lines

Quoted 9 lines

net/sched/em_meta.c +9 -0

+static int meta_int_compare(struct meta_obj *a, struct meta_obj *b)
+{
+	/* Let gcc optimize it, the unlikely is not really based on
+	 * some numbers but jump free code for missmatches seems
+	 * more logical.
+	 */
+	if (unlikely(a == b))
+		return 0;
+	else if (a < b)

Quoted 10 lines

net/sched/em_meta.c line 386

Quoted 6 lines

net/sched/em_meta.c +4 -0

+		return -1;
+	else
+		return 1;
+}

Would be very useful to return mnemonics for readability.

Same as for above, everyone knows what to expect from a *_compare function. Returning stuff like CMP_LT, CMP_BT, .. is just ugly.

I attached 4 patches of a first ematch implementation. Comments and suggestions very much appreciated. Compiles but untested.

* Thomas Graf:

Quoted 2 lines

I attached 4 patches of a first ematch implementation. Comments and suggestions very much appreciated. Compiles but untested.

This might infringe US patent 5,793,954 and the patents that reference it. 8-(