Kool Aid Served Daily

theShepler asked me offline why I wasn't looking at inet_ntoa(3SOCKET) for Reversing a network address from an uint_t. His email was dry, but I think there was a "D'oh!" in there somewhere.

I had considered those routines, but I went with the stuff in mountd because for the standalone, we don't have sockets being attached. In the finished product, I'll be looking at this. Also, since I will need to support IPv6, I'll have more need to not be doing my own parsing. But for right now, I'm going to proceed without IPv6 and without inet_aton(3SOCKET).

Okay, I did two things with the little network parsing code:

• I taught it to work with netmasks in a way just like addresses.
• I had it also just count bits to determine the netmask in decimal.
  • I took this from http://infolab.stanford.edu/~manku/bitcount/bitcount.html - which was the first google.com hit.

And here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>

#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

/*
 * http://infolab.stanford.edu/~manku/bitcount/bitcount.html
 */
int
spe_bitcount (unsigned int n)     
{
        int count = 8 * sizeof(int) ;
        n ^= (unsigned int) -1 ;
        while (n) {
                count-- ;
                n &= (n - 1) ;
        }

        return (count);
}


int
main (int argc, char *argv[])
{
        char    *p = argv[1];
        char    *junk;
        uint_t  addr = 0, mask = 0;
        uint_t  rev;
        int     i;
        int     shift;
        int     t;
        char    sep = ' ';

        unsigned char   b = 0;

        for (i = 0; i < 4; i++) {
                t = strtol(p, &junk, 10);
                if (junk && junk[0] == '/' && i == 3) {
                        b = 1;
                } else if (junk && junk[0] != '.' && junk[0] != '\0') {
                        fprintf(stderr, "%s is wrong in the %d octet,"
                                " %s has non-digits as |%s|\n", argv[1],
                                i+1, p, junk);
                        exit (-1);
                } else if (t > 255 || t < 0) {
                        fprintf(stderr, "%s is wrong in the %d octet,"
                                " %d is out of range\n", argv[1],
                                i+1, t);
                        exit (-1);
                }

                addr |= t << ((3-i) * 8);
                p = strchr(p, '.');
                if (p == NULL)
                        break;
                p++;
        }

        if (b) {
                p = &junk[1];   /* advance over '/' */
                t = strtol(p, &junk, 10);

                if (junk && junk[0] != '\0') {
                        fprintf(stderr, "%s is wrong in the netmask,"
                                " %s has non-digits as |%s|\n", argv[1],
                                p, junk);
                        exit (-1);
                } else if (t < 0 || t > 32) {
                        fprintf(stderr, "%s is wrong in the netmask,"
                                " %d is out of range\n", argv[1], t);
                        exit (-1);
                }

                mask = t ? ~0 << ((sizeof (struct in_addr) * NBBY) - t) : 0;
        } else {
                if ((addr & 0x00ffffff) == 0)
                        mask = 0xff000000;
                else if ((addr & 0x0000ffff) == 0)
                        mask = 0xffff0000;
                else if ((addr & 0x000000ff) == 0)
                        mask = 0xffffff00;
                else
                        mask = 0xffffffff;
        }

        printf("%s yields %u (%u) and that reverse maps to ", argv[1],
                addr, mask);

        for (i = 0; i < 4; i++) {
                shift = ((3-i) * 8);

                rev = (addr & (0xff << shift)) >> shift;

                printf("%c%u", sep, rev);
                sep = '.';
        }

        sep = '(';
        t = 0;
        for (i = 0; i < 4; i++) {
                shift = ((3-i) * 8);

                rev = (mask & (0xff << shift)) >> shift;

                printf("%c%u", sep, rev);
                sep = '.';
        }

        t = spe_bitcount(mask);
        printf(" - %u)\n", t);

        return (0);
}

And some test runs:

% ./a.out 192.168.2.0/23
192.168.2.0/23 yields 3232236032 (4294966784) and that reverse maps to  192.168.2.0(255.255.254.0 - 23)
% ./a.out 192.168.2.0/24
192.168.2.0/24 yields 3232236032 (4294967040) and that reverse maps to  192.168.2.0(255.255.255.0 - 24)
% ./a.out 192.168.2.0/31
192.168.2.0/31 yields 3232236032 (4294967294) and that reverse maps to  192.168.2.0(255.255.255.254 - 31)
% ./a.out 192.168.2.0/32
192.168.2.0/32 yields 3232236032 (4294967295) and that reverse maps to  192.168.2.0(255.255.255.255 - 32)
% ./a.out 192.168.2.0/0
192.168.2.0/0 yields 3232236032 (0) and that reverse maps to  192.168.2.0(0.0.0.0 - 0)
% ./a.out 192.168.2.0/1
192.168.2.0/1 yields 3232236032 (2147483648) and that reverse maps to  192.168.2.0(128.0.0.0 - 1)
% ./a.out 192.168.2.0/8
192.168.2.0/8 yields 3232236032 (4278190080) and that reverse maps to  192.168.2.0(255.0.0.0 - 8)
% ./a.out 192.168.2.0/33
192.168.2.0/33 is wrong in the netmask, 33 is out of range

I just need to stuff this code into my prototype.

Okay, the amount of delta turns out to be small to getting working code. I spent more time thinking about things. I tried putting the '(' code handling into the RHS and struggled with what node do I attach it to? I understood why for the LHS case it went to si, but after I created some new storage, I could not figure out how I knew si already had 2 children allocated.

Consider (path == /db) && (ext == jpg). From just doing the '(' code from the LHS, I knew there was no way that I had a correct si to attach the LHS ((ext == jpg)). Which is when I looked for where I had the correct code, which was in the get_compound state. And once I realized that, I realized I could keep the get_lhs focused on just handling data. The changes I had to make were in the OP code:

        case ('|') :
                /* 
                 * Rewind so that the compound operator can handle this correctly.
                 */
                if (*expression-- != '|') {
                        fprintf(stderr,
...
                }
                
                goto get_compound;
        
        case ('&') :
                /* 
                 * Rewind so that the compound operator can handle this correctly.
                 */
                if (*expression-- != '&') {
..
                }
                
                goto get_compound;

This also means that I only have to worry about '!' and '(' in the get_lhs state. This code may not be what a generator would have produced and it may make me groan when I come back to it, but it works.

Anyway, the current set of tests pass:

1, 16, 64000 (path == /db)
2, 16, 64000  !(path == /db)
3, 16, 64000 path == /db && ext == jpg
4, 16, 64000 path == /db && ext == jpg || ext == jpeg
5, 16, 64000 (path == /db && ext == jpg) || ext == jpeg
6, 16, 64000 path == /db && (ext == jpg || ext == jpeg)
7, 16, 64000 path == /db
8, 16, 64000 (path == /db && ext == jpg) || (path != /db && ext == jpeg)
9, 16, 32000 (path == /db && ext == jpg)
10, 16, 32000  !(path == /db && ext == jpg)
% cat tests/parens.txt
1, 16, 64k, (path == /db)
2, 16, 64k, !(path == /db)
3, 16, 64k, path == /db && ext == jpg
4, 16, 64k, path == /db && ext == jpg || ext == jpeg
5, 16, 64k, (path == /db && ext == jpg) || ext == jpeg
6, 16, 64k, path == /db && (ext == jpg || ext == jpeg)
7, 16, 64k, path == /db
8, 16, 64k, (path == /db && ext == jpg) || (path != /db && ext == jpeg)
9, 16, 32k, (path == /db && ext == jpg)
10, 16, 32k, !(path == /db && ext == jpg)

I need to go back and strip out all of the debug printfs, fix the storage of data in the get_rhs state, finish off the command line processing, etc. All of which needs to be done before I write the evaluation code. And that will be the real test case. I also need to add a new command line option to just verify the input. I've basically done that with the attribute-expression parsing, but I'd like a mode which does not load into the "global" set of policies. Note, I am thinking about the final product here.

Also, the code assumes that all id's are unique. If I were to have multiple ids in my rules-files, they would just load. BTW: I need to start calling it my policies-file. I think what I want to do in the final product is treat the loading of a policies-file to be atomic. To that end, they would load into a local list (which now has to become a parameter) and a warning would be spit out if there were duplicate ids. Only when the policies are all loaded correctly would the local copy be merged with the global one. And at that point, there would be no warnings about duplicates.

The latest code is at: speadm.c and speadm.h.

Turns out test case 4 is also horked, so let us work on it first:

4, 16, 64000 path == /db && ext == jpg && ext == jpeg

versus the expected

4, 16, 64000 path == /db && ext == jpg && ext == jpeg

5 and 6 also have this problem... Pretty easy to find once we noticed it:

        case ('|') :
                if (*expression++ != '|') {
...
                }                

                sop = SPE_OP_AND;
                break;

        case ('&') :
                if (*expression++ != '&') {
...
                }

                sop = SPE_OP_AND;
                break;

...
        /*
         * Both children are interior nodes...!
         */
        si_new->si_op = sop;

Cutting and pasting when in a hurry or tired is going to lead to bugs. Fixed and working.

Back to 5 and 6:

5, 16, 64000 (path == /db) && ext == jpg || ext == jpeg
6, 16, 64000 path == /db && (ext == jpg) || ext == jpeg

I did the expressions out on paper and I think the basic mechanism may be correct here. It might be that the recording of the parentheses is the problem. I.e., they look to be in the correct area, but on the wrong interior node. Hard to explain what I mean, let me see if I can find the bug and illustrate what I suspect.

First I'll add two new test cases:

8, 16, 64k, (path == /db && ext == jpg) || (path != /db && ext == jpeg)
9, 16, 32k, (path == /db && ext == jpg)

And look at the results:

8, 16, 64000 (path == /db) && ext == jpg || (path != /db) && ext == jpeg
9, 16, 32000 (path == /db) && ext == jpg

So my parentheses handling only works for the simple case of !(path == /db). It does not work for compound operators at all. As a matter of fact, a new test case suggests itself:

10, 16, 32k, !(path == /db && ext == jpg)

And we get:

10, 16, 32000  !(path == /db) && ext == jpg

I think what we should be doing is that when we encounter a '(' we recursively parse the subexpression and when that comes back, we throw the parentheses over the root of the subtree. And that reminds me, we are only handling match detecting for when we hit '!'.

We can test this claim pretty quickly as the '!' almost does this exact algorithm. A quick test shows with this:

                if (!(si->si_branches[0].st_node =
                    spe_parse_attribute_expression(si->si_branches[0].st_node, sub_expr,
                    pf, piLine, prc))) {
                        goto cleanup; 
                }
        
                {
                        spe_interior_t  *sip;
                
                        if (si->si_branches[0].st_is_interior == FALSE) {
...
                        }
                
                        sip = (spe_interior_t *)si->si_branches[0].st_node;
                        sip->si_parens = TRUE;
                }

bears fruit:

2, 16, 64000  !(path == /db)
10, 16, 32000  !(path == /db && ext == jpg)

What I'm trying to get at is that I believe the parse trees are correct, but it is just the annotation on them to produce parentheses which is incorrect. I.e., they would evaluate file creations correctly. And this is a very dangerous claim to make - it may simply be that my test cases support it and new test cases would tear it apart. I'm not going to investigate this angle, I have other fish to fry.

And while this latest change appears to work, what I really need to do is push the parentheses handling out of the '!' case and make it a first class citizen.

The big difference here is that we need to consume the parentheses first when getting the sub-expression:

                t = expression;
                iLen = strlen(t) + 1;
                b = FALSE;

                iParens = 1;
                for (i = 0; i < iLen - 1; i++) {

If we don't consume it, then we will never have a base case to halt recursion. The new code, works, kinda. I actually was predicting the failure to myself.

spe_parse_attribute_expression: EOS when parsing operator for Line 10 in 
1, 16, 64000 (path == /db)
2, 16, 64000  !(path == /db)
3, 16, 64000 path == /db && ext == jpg
4, 16, 64000 path == /db && ext == jpg || ext == jpeg
5, 16, 64000 (path == /db && ext == jpg)
6, 16, 64000 path == /db && (ext == jpg || ext == jpeg)
7, 16, 64000 path == /db
8, 16, 64000 (path == /db && ext == jpg)
9, 16, 32000 (path == /db && ext == jpg)
10, 16, 32000  !(path == /db && ext == jpg)

Note the warning I've included. The problem is the the code was structured to handle LHS OP RHS, where the allowed ops were '==' and '!='. This worked when we had the latest parentheses bug. You can see it fail in policies 5 and 8 where the op is '||'.

We need to allow the ops '||' and '&&' to now appear in the OP slot. We also need to allow a '(' to appear in the RHS slot.

I'm trying to decide if the code is about to become too kludgey or not. I think I put too much emphasis in trying to parse it without recursion. You might have noticed my hesitation about some things earlier (like the labels).

I think the best thing is to continue down the path of finishing the prototype. Then I can decide if I need to rewrite it for the final product.

I'm going to cut this entry off here - this is a big enough of an issue. The final code is at: speadm.c and speadm.h.

I quickly wrote a recursive print routine for an attribute-expression and also stuffed all RHS data into the string data type. Here is the resulting code:

char *spe_ops_list[] = {
	"&&",
	"||",
	"!",
	"==",
	"!=",
	NULL
};

...

void
spe_print_leaf (spe_leaf_t *sl)
{
	if (sl->sl_is_attr == TRUE) {
	} else {
		switch (sl->sl_type) {
		case (SPE_DATA_STRING) :
			fprintf(stdout, "%s", sl->sl_data.sz);
			break;
...
		default :
			fprintf(stderr,
			    "spe_print_leaf: Unknown type %d\n", sl->sl_type);
			break;
		}
	}
}

void
spe_print_thunk (spe_thunk_t st)
{
	if (st.st_is_interior == TRUE) {
		spe_print_attribute((spe_interior_t *)st.st_node);
	} else {
		spe_print_leaf((spe_leaf_t *)st.st_node);
	}
}

void
spe_print_attribute (spe_interior_t *si)
{
	int	i;

	if (!si) {
		return;
	}

	if (si->si_children == 1) {
		fprintf(stdout, " %s", spe_ops_list[si->si_op]);
		spe_print_thunk(si->si_branches[0]);
	} else {
		if (si->si_parens) {
			fprintf(stdout, "(");
		}

		spe_print_thunk(si->si_branches[0]);
		fprintf(stdout, " %s ", spe_ops_list[si->si_op]);
		spe_print_thunk(si->si_branches[1]);

		if (si->si_parens) {
			fprintf(stdout, ")");
		}
	}
}

void
spe_print_policy (spe_policy_t *spe)
{
	if (!spe) {
		return;
	}

	fprintf(stdout, "%u, %u, %u ", spe->sp_id, spe->sp_stripe_count,
	    spe->sp_interlace);

	spe_print_attribute(spe->sp_attr_expr);

	fprintf(stdout, "\n");
}

void
spe_print_policy_list (void)
{
	spe_policy_t	*spe;

	for (spe = spe_policy_list; spe; spe = spe->next) {
		spe_print_policy(spe);
	}
}

/*
 * When we parse an attribute-expression...
 */
spe_interior_t *
spe_parse_attribute_expression (spe_interior_t *si, char *expression, FILE *pf,
    int *piLine, int *prc)
{
...
		/*
		 * The sub_expr is basically the tested.
		 */
		printf("RHS is %s\n", sub_expr);

		/*
		 * XXX: Hack to get to debugging!
		 */
		sl = (spe_leaf_t *)si->si_branches[0].st_node;
		sl->sl_is_attr = FALSE;
		sl->sl_type = SPE_DATA_STRING;
		sl->sl_data.sz = sub_expr;

		if (sub_expr) {
#if 0
			free(sub_expr);
#endif
			sub_expr = NULL;
		}
	}

And here is some output:

% cat !$
cat tests/parens.txt
1, 16, 64k, (path == /db)
2, 16, 64k, !(path == /db)
3, 16, 64k, path == /db && ext == jpg
4, 16, 64k, path == /db && ext == jpg || ext == jpeg
5, 16, 64k, (path == /db && ext == jpg) || ext == jpeg
6, 16, 64k, path == /db && (ext == jpg || ext == jpeg)
% ./a.out -r tests/parens.txt 
1, 16, 64000 (/db == (null))
2, 16, 64000  !(/db == (null))
3, 16, 64000 jpg == (null)
4, 16, 64000 jpeg == (null)
5, 16, 64000 jpeg == (null)
6, 16, 64000 jpeg == (null)

I've already spotted a bug in spe_print_leaf(), a quick fix of:

void
spe_print_leaf (spe_leaf_t *sl)
{
        int     i;
        
        if (!sl) {
                return;
        }       
        
        if (sl->sl_is_attr == TRUE) {
                for (i = 0; i < attribute_count; i++) {
                        if (spe_attribute_table[i].at_attr == sl->sl_attr) {
                                fprintf(stdout, "%s", spe_attribute_table[i].at_name);
                        }       
                }       
        } else {

Hmm, sl_attr could come out of the table, the index should suffice. But that is for later. What results do we get?

1, 16, 64000 (/db == (null))
2, 16, 64000  !(/db == (null))
3, 16, 64000 jpg == (null)
4, 16, 64000 jpeg == (null)
5, 16, 64000 jpeg == (null)
6, 16, 64000 jpeg == (null)

I'm actually quite happy with that, I didn't think that should have been the issue. Okay, what do we know? Well, first off, the attribute expression looks backwards. Hmm, the parentheses in 1 and the negation in 2 appear correct.

A little exploration in gdb shows that the first node is storing the path:

(gdb) print si
$1 = (spe_interior_t *) 0x100160
(gdb) print *si
$2 = {
  si_op = SPE_OP_EQUAL, 
  si_parens = 1 '\001', 
  si_children = 2, 
  si_branches = 0x100170
}
(gdb) print si->si_branches[0]
$3 = {
  st_is_interior = 0 '\0', 
  st_node = 0x100180
}
(gdb) print (spe_leaf_t *)si->si_branches[0].st_node
$4 = (spe_leaf_t *) 0x100180
(gdb) print *(spe_leaf_t *)si->si_branches[0].st_node
$5 = {
  sl_is_attr = 0 '\0', 
  sl_attr = SPE_ATTR_PATH, 
  sl_type = SPE_DATA_STRING, 
  sl_data = {
    uid = 1049088, 
    gid = 1049088, 
    i = 1049088, 
    sz = 0x100200 "/db", 
    net = {
      sn_netname = 0x100200 "/db", 
      sn_network = 0, 
      sn_netmask = 0
    }
  }
}

Okay, the bug is in the quick hack to get printing to work, wrong index here:

		/*
		 * XXX: Hack to get to debugging!
		 */
		sl = (spe_leaf_t *)si->si_branches[0].st_node;

Fix it and:

1, 16, 64000 (path == /db)
2, 16, 64000  !(path == /db)
3, 16, 64000 ext == jpg
4, 16, 64000 ext == jpeg
5, 16, 64000 ext == jpeg
6, 16, 64000 ext == jpeg
7, 16, 64000 path == /db

Great, I added a new simple test 7 and it with the first 2 tests are working correctly. As thought though, the more complex parentheses tests are failing. Just not the way I expected. Sheesh! By the way, I'm leaking memory like crazy as well.

Walking through the code, I think the bug is here, where I only allocate 1 branch and not 2:

        /*
         * Both children are interior nodes...!
         */
        si_new->si_op = sop;
        si_new->si_children = 2;
        si_new->si_branches = (spe_thunk_t *)calloc(1, sizeof(spe_thunk_t));

Crap, my fix was this:

        /*
         * Both children are interior nodes...!
         */
        si_new->si_op = sop;
        si_new->si_children = 2;
        si_new->si_branches = (spe_thunk_t *)calloc(si_new->si_children, sizeof(spe_thunk_t));

And in applying it everywhere I did the calloc, I found where I must have cut and paste the bug from:

                /*
                 * We do not yet know what the operator is...
                 */
                si->si_children = 2;
                si->si_branches = (spe_thunk_t *)calloc(1, sizeof(spe_thunk_t));

While nasty, those are not the bug which is killing me. I think it is this code:

	/*
	 * The first child is the previous root of the parse tree.
	 */
	si_new->si_branches[0].st_is_interior = TRUE;
	si_new->si_branches[0].st_node = si;

	/*
	 * This is temporary until we get the second child allocated.
	 * This is done to allow proper cleanup in the case of a
	 * memory allocation when getting the second child.
	 */
	si = si_new;

	si_new->si_branches[1].st_is_interior = TRUE;
	si_new->si_branches[1].st_node = (spe_interior_t *)calloc(1,
	    sizeof(spe_interior_t));
	if (!si_new->si_branches[1].st_node) {
		fprintf(stderr, "spe_parse_attribute_expression:"
		    " Not enough memory\n");
		*prc = ENOMEM;
		goto cleanup;
	}

	/*
	 * Now we get the correct subtree to fill out.
	 */
	si = (spe_interior_t *)si_new->si_branches[1].st_node;

	/*
	 * Finally, we realize that we have more input to process.
	 */
	szError = expression;
	goto get_lhs;

The problem is that what I want to be returning (si_new) and what I want to be working on (si) are not the same. This may be where not using recursion is really going to bite me! Hmm, is it as simple as making a recursive call right here?

Yes, that is a good thing:

	/*
	 * The first child is the previous root of the parse tree.
	 */
	si_new->si_branches[0].st_is_interior = TRUE;
	si_new->si_branches[0].st_node = si;

	/*
	 * We hoist the new node into place.
	 */
	si = si_new;

	si_new->si_branches[1].st_is_interior = TRUE;
	si_new->si_branches[1].st_node = (spe_interior_t *)calloc(1,
	    sizeof(spe_interior_t));
	if (!si_new->si_branches[1].st_node) {
		fprintf(stderr, "spe_parse_attribute_expression:"
		    " Not enough memory\n");
		*prc = ENOMEM;
		goto cleanup;
	}

	/*
	 * Handle the rest by recursion.
	 */
	if (!(si_new->si_branches[1].st_node =
	    spe_parse_attribute_expression(si_new->si_branches[1].st_node, expression,
	    pf, piLine, prc))) {
		goto cleanup;
	}

	/*
	 * XXX: Do we want to check to make sure we've exhausted input? And how?
	 */

cleanup:

Which yields:

1, 16, 64000 (path == /db)
2, 16, 64000  !(path == /db)
3, 16, 64000 path == /db && ext == jpg
4, 16, 64000 path == /db && ext == jpg && ext == jpeg
5, 16, 64000 (path == /db) && ext == jpg && ext == jpeg
6, 16, 64000 path == /db && (ext == jpg) && ext == jpeg
7, 16, 64000 path == /db

Only 5 and 6 are horked. But those are the ones I suspected from the start would be that way.

And I'm okay with that for right now. I'm getting tired and I almost zapped my source while making a backup! Here is the current speadm.c and speadm.h.