Project

General

Profile

« Previous | Next » 

Revision c16b176d

Added by Dominic Cleal over 7 years ago

fixes #17387 - SubnetService#find_subnet has constant time lookup

find_subnet is now approximately constant with the number of subnets
configured, using hash lookups of possible network prefixes for the
given IP address until the most specific prefix is found. Benchmark
results:

find_subnet (1 subnets, 200 hosts)
                              1.665k (± 9.5%) i/s -     16.437k in   9.991955s
    find_subnet (5 subnets, 1000 hosts)
                            331.898  (± 7.5%) i/s -      3.298k in   9.999109s
    find_subnet (50 subnets, 10000 hosts)
                             31.363  (± 6.4%) i/s -    313.000  in  10.005986s
    find_subnet (500 subnets, 100000 hosts)
                              3.078  (± 0.0%) i/s -     31.000  in  10.072384s
    find_subnet (5000 subnets, 1000000 hosts)
                              0.301  (± 0.0%) i/s -      4.000  in  13.298996s

add_subnet only checks for an identical network prefix instead of
overlapping prefixes with #find_subnet, speeding it up considerably.
Benchmark results:

add_subnet (1)     41.389k (±17.4%) i/s -    378.638k in   9.792687s
        add_subnet (5)     10.278k (±11.2%) i/s -     99.588k in   9.931308s
       add_subnet (50)      1.062k (± 9.3%) i/s -     10.470k in   9.991114s
      add_subnet (500)    105.161  (± 9.5%) i/s -      1.042k in  10.007969s
     add_subnet (1000)     53.826  (± 7.4%) i/s -    536.000  in  10.012055s
    add_subnet (15000)      3.424  (± 0.0%) i/s -     35.000  in  10.241879s

View differences:

modules/dhcp_common/subnet_service.rb
class SubnetService
include Proxy::Log
SEARCH_MASKS = (0..31).map { |bit| ~(1 << bit) }
attr_reader :m, :subnets, :leases_by_ip, :leases_by_mac, :reservations_by_ip, :reservations_by_mac, :reservations_by_name
def initialize(subnets, leases_by_ip, leases_by_mac, reservations_by_ip, reservations_by_mac, reservations_by_name)
def initialize(leases_by_ip, leases_by_mac, reservations_by_ip, reservations_by_mac, reservations_by_name, subnets = {})
@subnets = subnets
@leases_by_ip = leases_by_ip
@leases_by_mac = leases_by_mac
......
end
def self.initialized_instance
new(::Proxy::MemoryStore.new, ::Proxy::MemoryStore.new, ::Proxy::MemoryStore.new,
new(::Proxy::MemoryStore.new, ::Proxy::MemoryStore.new,
::Proxy::MemoryStore.new, ::Proxy::MemoryStore.new, ::Proxy::MemoryStore.new)
end
def add_subnet(subnet)
m.synchronize do
raise Proxy::DHCP::Error, "Unable to add subnet #{subnet}" if find_subnet(subnet.network)
key = subnet.ipaddr.to_i
raise Proxy::DHCP::Error, "Unable to add subnet #{subnet}" if subnets.key?(key)
logger.debug("Added a subnet: #{subnet.network}")
subnets[subnet.network] = subnet
subnets[key] = subnet
subnet
end
end
......
end
def delete_subnet(subnet_address)
m.synchronize { subnets.delete(subnet_address) }
m.synchronize { subnets.delete(Proxy::DHCP.ipv4_to_i(subnet_address)) }
logger.debug("Deleted a subnet: #{subnet_address}")
end
def find_subnet(address)
m.synchronize do
to_ret = subnets[address]
return to_ret if to_ret # we were given a subnet address
ipv4_as_i = Proxy::DHCP.ipv4_to_i(address)
return subnets[ipv4_as_i] if subnets.key?(ipv4_as_i)
do_find_subnet(subnets, ipv4_as_i, address)
end
end
# TODO: this can be done much faster
subnets.values.each do |subnet|
return subnet if subnet.include?(address)
def do_find_subnet(all_subnets, address_as_i, address)
search_as_i = address_as_i
SEARCH_MASKS.each do |mask|
# zero consecutive least-significant bits until a matching prefix is found
search_as_i &= mask
if all_subnets.key?(search_as_i)
matching = all_subnets[search_as_i]
return matching if matching.netmask_to_i & address_as_i == search_as_i
end
end
nil
end
private :do_find_subnet
def all_subnets
m.synchronize { subnets.values }

Also available in: Unified diff