[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty
- From: Sean Conner <sean@...>
- Date: Wed, 18 Oct 2017 01:17:53 -0400
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 ... ))