Bugs I found are at end of page ..

I want to understand u32 filter so there are my results from source code hacking. Probably each qdist which has at least one u32 attached has also exactly one instance of tc_u_common structure. Note that logically is u32 filter attached to a class not to qdist. But it's not true at implementation level. The tc_u_common structure has attached list of top level hnodes (h stands for hash). Each hnode is only hash table of knodes (k stands for key). Number of buckets in such table is called "divisor" here (in reality, divisor's value in hnode is stored as decremented by one). In the simplest case, divisor can be 1. Then hnode contains exactly one knode (top level hnodes always has just one knode).
Knode represents node with selector, result, optional policy and optional nested hnode. Result and policy structures are described in general filter section.
Selector (tc_u32_sel) is another animal. It contains several fields and also nkeys count of tc_u32_key structures. Let's see its declaration: 
struct tc_u32_key
{
        __u32           mask;
        __u32           val;
        int             off;
        int             offmask;
};
The structure represents a rule applied at each packet. The rule is very generic. It matches any packet if it has value val at offset off. Only these bits where mask is 1 are compared. Offmask value is used to mask protocol offsets - the exact meaning is not known to me yet. 
struct tc_u32_sel
{
        unsigned char           flags;
        unsigned char           offshift;
        unsigned char           nkeys;

        __u16                   offmask;
        __u16                   off;
        short                   offoff;

        short                   hoff;
        __u32                   hmask;

        struct tc_u32_key       keys[0];
};
This structure contains nkeys count of tc_u32_key. Various flags can be:

TC_U32_TERMINAL when reached during classify, result is copied from here

TC_U32_OFFSET this is used on only one line in source code, it seems as bug. Probably it should tell classifier to apply tc_u32_sel.off when going into subtable.

TC_U32_VAROFFSET similar to previous one, only the offset is fetched from packet at position tc_u32_sel.offoff masked by tc_u32_sel.offmask and shifted right by tc_u32_sel.offshift shifts. It's useful when you need to "locate" subprotocol in protocol (TCP in IP) and apply subtable to the subprotocol.

TC_U32_EAT don't know exactly. It seems it influences way how offsets above are applied to subtables. When this flag is set, base pointer of packet is changed by offset and change is visible only to this and subsequent levels. Without the flag, offset is stored into off2 variable and applied using tc_u32_key.offmask (WHY!??). But when you set offset later again to another value, old value is replaced (with EAT flag, offset is permanent for current level).
Also it seems thst there is BUG in sources. In my opinion the off2 variable should be put onto stack along with ptr and node. If not, WHY !??

Another questions/bugs:

File cls_u32.c at line 172: 
if (ht->divisor)
    sel = ht->divisor&u32_hash_fold(*(u32*)(ptr+n->sel.hoff), &n->sel);
From code above I realized that divisor HAS to be value in format 2^n-1 because sel is computed by ANDing it with hash_fold value ... Am I right ??

Line 262: 

static u32 gen_new_htid(struct tc_u_common *tp_c)
{
    int i = 0x800;
    do {
        if (++tp_c->hgenerator == 0x7FF)
            tp_c->hgenerator = 1;
    } while (i>0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20));

    return i > 0 ? (tp_c->hgenerator|0x800)<<20 : 0;
}
Variable i is used here but NEVER CHANGED ! It seems as bug ..

Line 176: 

     if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT)))
            goto next_ht;

        if (n->sel.flags&(TC_U32_EAT|TC_U32_VAROFFSET)) {
            off2 = n->sel.off + 3;
            if (n->sel.flags&TC_U32_VAROFFSET)
                off2 += ntohs(n->sel.offmask & *(u16*)(ptr+n->sel.offoff)) >>n->sel.offshift;
            off2 &= ~3;
        }
        if (n->sel.flags&TC_U32_EAT) {
            ptr += off2;
            off2 = 0;
        }
When only TC_U32_OFFSET is set, value of off2 is never changed. Probably there should be (TC_U32_OFFSET|TC_U32_VAROFFSET) instead of (TC_U32_EAT|TC_U32_VAROFFSET), right ?

In classify routine, off2 should be also pushed on stack, shouldn't ?

Martin DEVERA, devik@cdi.cz