BPF JIT compiler

[Matthew Luckie]

The existing intel BPF JIT compiler has one flaw.  sys/net/bpf_filter.c 
initialises the A and X registers to zero when called.  The just in time 
compiler does not.  This means the JIT compiler will behave differently 
to the interpreter on any filter that does not set the A or X registers 
before using them.

One approach is to put two additional ops in the procedure header of all 
compiled filters to zero these registers.  This is the easiest thing to 
do, though it does mean a slower JIT compiler.  Another approach is to 
reject any filter that might use A or X before setting it.  This 
approach is really no different to having code check the filter and 
conditionally include zero operations if necessary.

Below is a recursive function to check if A or X need to be set in the 
procedure header.  This function would go in bpf_jitter.c and set two 
additional struct members in bpf_jit_filter to allow the machdep code to 
do the right thing.

To my way of thinking, the bpf_insn_seta, bpf_insn_usea, bpf_insn_setx, 
bpf_insn_seta functions could perhaps be macros.  Of greater concern to 
me is any policy that may exist on recursion in the kernel.

Comments, please.  jkim@ is busy with other things, so if you're 
interested, please speak up.

static int bpf_insn_seta(const struct bpf_insn *ins)
{
   if(BPF_CLASS(ins->code) == BPF_LD || ins->code == (BPF_MISC|BPF_TXA))
     {
       return 1;
     }
   return 0;
}

static int bpf_insn_usea(const struct bpf_insn *ins)
{
   if(BPF_CLASS(ins->code) == BPF_ALU ||
      (BPF_CLASS(ins->code) == BPF_JMP && BPF_OP(ins->code) != BPF_JA) ||
      ins->code == (BPF_RET|BPF_A) ||
      ins->code == (BPF_ST) ||
      ins->code == (BPF_MISC|BPF_TAX))
     {
       return 1;
     }
   return 0;
}

static int bpf_insn_setx(const struct bpf_insn *ins)
{
   if(BPF_CLASS(ins->code) == BPF_LDX || ins->code == (BPF_MISC|BPF_TAX))
     {
       return 1;
     }
   return 0;
}

static int bpf_insn_usex(const struct bpf_insn *ins)
{
   if((BPF_CLASS(ins->code) == BPF_ALU && BPF_SRC(ins->code) == BPF_X) ||
      (BPF_CLASS(ins->code) == BPF_LD && BPF_MODE(ins->code) == BPF_IND) ||
      (BPF_CLASS(ins->code) == BPF_JMP && BPF_SRC(ins->code) == BPF_X) ||
      ins->code == (BPF_STX) ||
      ins->code == (BPF_MISC|BPF_TXA))
     {
       return 1;
     }
   return 0;
}

/*
  * bpf_ax
  *
  * determine if we need to initialise the accumulator and index
  * registers.
  */
static void bpf_ax(const struct bpf_insn *fp, int i, int nins, int *a, 
int *x)
{
   const struct bpf_insn *ins;
   int a1, a2, x1, x2;

   while(i<nins)
     {
       ins = &fp[i];

       if(*a == 0)
	{
	  if(bpf_insn_usea(ins) != 0)
	    *a = 1;
	  else if(bpf_insn_seta(ins) != 0)
	    *a = 2;
	}

       if(*x == 0)
	{
	  if(bpf_insn_usex(ins) != 0)
	    *x = 1;
	  else if(bpf_insn_setx(ins) != 0)
	    *x = 2;
	}

       if(*a != 0 && *x != 0)
	break;

       if(BPF_CLASS(ins->code) == BPF_JMP)
	{
	  if(BPF_OP(ins->code) == BPF_JA)
	    {
	      bpf_ax(fp, i+1+ins->k, nins, a, x);
	    }
	  else
	    {
	      a1 = a2 = *a;
	      x1 = x2 = *x;
	      bpf_ax(fp, i+1+ins->jt, nins, &a1, &x1);
	      bpf_ax(fp, i+1+ins->jf, nins, &a2, &x2);

	      if(a1 == 1 || a2 == 1)
		*a = 1;
	      else
		*a = 0;
	
	      if(x1 == 1 || x2 == 1)
		*x = 1;
	      else
		*x = 0;
	    }
	  break;
	}

       i++;
     }

   if(*a != 1)
     *a = 0;

   if(*x != 1)
     *x = 0;

   return;
}