Re: [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty

[Sean Conner <sean@...>]

It was thus said that the Great Patrick Donnelly once stated:
> Hi Robert Paprocki,
> 
> (Sorry I didn't get your email. So lua-l gets to be the transition medium :)
> 
> Here is a messy proof-of-concept for handling IP addresses matching a
> set of CIDRs at large scale. As we talked about, it works by
> constructing a tree of CIDRs as an array and matching IP addresses
> against it. (Note: the array is static size and holds the entire 32bit
> ip address space as a 2GB array. However, this malloc'd memory is
> mostly unused and due to memory overcommit in Linux, the actual memory
> of your RSS is much less.)

  There is a much more space efficient way of storing this information and
the retrieval time isn't bad (the average number of comparisons is the
average length of the netmask---worse case is 32, the length of an entire IP
address, regardless of the number of entries).

  On the down side, it's easy to implement, but not quite so easy to
describe.  I'll try, with four bit addresses.

  Assume the following addresses/masks:

	0000/0000	(our default match for "no match")
	1000/1000	addresses 8-15
	0100/1100	addresses 4-7
	0010/1111	address 2

So address 0, 1 and 3 (if my data is correct) should be a "no match".  A
constructed tree will look like:

                  [*]		0000/0000
                  / \
                 0   1
                /     \
              [ ]     [*]	1000/1000
              / \     
             0   1  
            /     \ 
          [ ]     [*]		0100/1100
            \
             1
              \
              [ ]
              /
             0
            /
          [*]			0010/1111

Each node has a match flag (true or false), and links for 0 or 1 bits.  When
constructing, you use the mask to determine which bits of the address are
used for matching.  To find an address, start at the root node:

	while true do
	  if node.match then
	    found = node
	  end
	  
	  next = address:nextbit()

	  if not next then
	    return found
	  end
	  
	  if not node[next] then
	    return found
	  end
	  
	  node = node[next]
	end

Using an address of 1001, we start at the root.  There is a match, so we set
'found' to the root node.  There is another bit (1) so we follow that.  That
node is a match, so we set 'found' to that node.  There is another bit (0),
but there are no more nodes to check, so we return the last node we matched.

Let's try address 0011.  Again, there's a match at the root, so 'found' is
the root.  There's more bits (0), so we follow that.  No match, but there
are still more bits (0), so we follow that again.  Again, no match, but
there are still more bits (1 this time).  We can still follow.  More bits
(1), but this time, there is no link for said bit, so we return 'found',
which is the root node (no match).

  You can extend this out to 32 bits easily.  I'll leave constructing the
table as an exercise for the reader.

  -spc (Can you tell I implemented this?  Only in C, not Lua (it was a
	long time agao ... ))