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:

bundler.d/development.rb
gem 'single_test'
gem 'pry'
gem 'rubocop', '0.38.0' if RUBY_VERSION > "1.9.2"
gem 'benchmark-ips'
gem 'ruby-prof'
end
modules/dhcp_common/dhcp_common.rb
class Collision < RuntimeError; end
class InvalidRecord < RuntimeError; end
class AlreadyExists < RuntimeError; end
def self.ipv4_to_i(ipv4_address)
ipv4_address.split('.', 4).inject(0) { |i, octet| (i << 8) | octet.to_i }
end
end
modules/dhcp_common/subnet.rb
module Proxy::DHCP
class Subnet
attr_reader :network, :netmask, :server
attr_reader :ipaddr, :network, :netmask, :server
attr_accessor :options
include Proxy::DHCP
......
def initialize network, netmask, options = {}
@network = validate_ip network
@netmask = validate_ip netmask
@ipaddr = IPAddr.new(to_s)
@options = {}
@options[:routers] = options[:routers].each{|ip| validate_ip ip } if options[:routers]
......
end
end
IPAddr.new(to_s).include?(ipaddr)
@ipaddr.include?(ipaddr)
end
def to_s
......
end
def cidr
IPAddr.new(netmask).to_i.to_s(2).count("1")
netmask_to_i.to_s(2).count("1")
end
def range
......
"#{r.first}-#{r.last}"
end
def netmask_to_i
@netmask_to_i ||= Proxy::DHCP.ipv4_to_i(netmask)
end
def get_index_and_lock filename
# Store for use in the unlock method
@filename = "#{Dir::tmpdir}/#{filename}"
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 }
modules/dhcp_isc/configuration_loader.rb
def load_dependency_injection_wirings(container, settings)
container.dependency :memory_store, ::Proxy::MemoryStore
container.singleton_dependency :subnet_service, (lambda do
::Proxy::DHCP::SubnetService.new(container.get_dependency(:memory_store), container.get_dependency(:memory_store),
::Proxy::DHCP::SubnetService.new(container.get_dependency(:memory_store),
container.get_dependency(:memory_store), container.get_dependency(:memory_store),
container.get_dependency(:memory_store), container.get_dependency(:memory_store))
end)
modules/dhcp_libvirt/configuration_loader.rb
def load_dependency_injection_wirings(container, settings)
container.dependency :memory_store, ::Proxy::MemoryStore
container.dependency :subnet_service, (lambda do
::Proxy::DHCP::SubnetService.new(container.get_dependency(:memory_store), container.get_dependency(:memory_store),
::Proxy::DHCP::SubnetService.new(container.get_dependency(:memory_store),
container.get_dependency(:memory_store), container.get_dependency(:memory_store),
container.get_dependency(:memory_store), container.get_dependency(:memory_store))
end)
test/benchmark_helper.rb
require 'test_helper'
require 'benchmark/ips'
def proxy_benchmark
GC.start
yield
stats = GC.stat
puts "Memory stats"
puts "Total objects allocated: #{stats[:total_allocated_objects]}"
puts "Total heap pages allocated: #{stats[:total_allocated_pages]}"
end
test/dhcp/subnet_service_add_subnet_benchmark.rb
require 'benchmark_helper'
require 'dhcp_common/dhcp_common'
require 'dhcp_common/subnet'
require 'dhcp_common/subnet_service'
proxy_benchmark do
Benchmark.ips do |x|
x.config(:time => 10, :warmup => 0)
[1, 5, 50, 500, 1000, 15_000].each do |subnet_count|
s1 = s2 = 0
subnets = (1..subnet_count).map do |i|
s2 += 1
if s2 % 256 == 0
s1 += 1
s2 = 0
end
subnet = "#{s1}.#{s2}.0.0"
netmask = '255.255.255.0'
Proxy::DHCP::Subnet.new(subnet, netmask, {})
end
x.report("add_subnet (#{subnet_count})") do
service = Proxy::DHCP::SubnetService.initialized_instance
subnets.each { |s| service.add_subnet(s) }
end
end
end
end
test/dhcp/subnet_service_find_subnet_benchmark.rb
require 'benchmark_helper'
require 'dhcp_common/dhcp_common'
require 'dhcp_common/subnet'
require 'dhcp_common/subnet_service'
host_count = 200
proxy_benchmark do
Benchmark.ips do |x|
x.config(:time => 10, :warmup => 0)
[1, 5, 50, 500, 5000].each do |subnet_count|
hosts = []
s1 = s2 = 0
subnets = (1..subnet_count).map do |_|
s2 += 1
if s2 % 256 == 0
s1 += 1
s2 = 0
end
prefix = "#{s1}.#{s2}.0"
netmask = '255.255.255.0'
host_count.times { |c| hosts << "#{prefix}.#{c}" }
Proxy::DHCP::Subnet.new(prefix + '.0', netmask, {})
end
service = Proxy::DHCP::SubnetService.initialized_instance
subnets.each { |s| service.add_subnet(s) }
x.report("find_subnet (#{subnet_count} subnets, #{host_count * subnet_count} hosts)") do
hosts.each { |s| service.find_subnet(s) }
end
end
end
end
test/dhcp/subnet_service_test.rb
class SubnetServiceTest < Test::Unit::TestCase
def setup
@subnets = Proxy::MemoryStore.new
@subnets = {}
@leases_ip_store = Proxy::MemoryStore.new
@leases_mac_store = Proxy::MemoryStore.new
@reservations_ip_store = Proxy::MemoryStore.new
@reservations_ip_store = Proxy::MemoryStore.new
@reservations_mac_store = Proxy::MemoryStore.new
@reservations_name_store = Proxy::MemoryStore.new
@service = Proxy::DHCP::SubnetService.new(@subnets, @leases_ip_store, @leases_mac_store, @reservations_ip_store, @reservations_mac_store, @reservations_name_store)
@service = Proxy::DHCP::SubnetService.new(@leases_ip_store, @leases_mac_store, @reservations_ip_store, @reservations_mac_store, @reservations_name_store, @subnets)
end
def test_add_subnet
......
assert_equal subnets.first, @service.find_subnet("192.168.0.0")
end
def test_find_subnet_with_cidr_mask
subnets = [Proxy::DHCP::Subnet.new("192.168.0.0", "255.255.255.192"),
Proxy::DHCP::Subnet.new("192.168.0.64", "255.255.255.192"),
Proxy::DHCP::Subnet.new("192.168.0.128", "255.255.255.192"),
Proxy::DHCP::Subnet.new("192.168.0.192", "255.255.255.192")]
@service.add_subnets(*subnets)
assert_equal subnets[2], @service.find_subnet("192.168.0.131")
end
def test_find_subnet_with_cidr_mask_if_subnet_is_undefined
subnets = [Proxy::DHCP::Subnet.new("192.168.0.0", "255.255.255.192"),
Proxy::DHCP::Subnet.new("192.168.0.64", "255.255.255.192"),
Proxy::DHCP::Subnet.new("192.168.0.192", "255.255.255.192")]
@service.add_subnets(*subnets)
assert_nil @service.find_subnet("192.168.0.131")
end
def test_find_subnet_with_mixed_cidr_returns_255_255_255_254_subnet
subnets = [Proxy::DHCP::Subnet.new("192.0.0.0", "255.128.0.0"),
Proxy::DHCP::Subnet.new("192.169.0.0", "255.255.0.0"),
Proxy::DHCP::Subnet.new("192.168.0.0", "255.255.255.192"),
Proxy::DHCP::Subnet.new("192.168.0.64", "255.255.255.224"),
Proxy::DHCP::Subnet.new("192.168.0.96", "255.255.255.224"),
Proxy::DHCP::Subnet.new("192.168.0.128", "255.255.255.192"),
Proxy::DHCP::Subnet.new("192.168.0.192", "255.255.255.192")]
@service.add_subnets(*subnets)
assert_not_nil @service.find_subnet("192.168.0.100")
assert_equal subnets[4], @service.find_subnet("192.168.0.100")
end
def test_find_subnet_with_mixed_cidr_returns_252_0_0_0_subnet
subnets = [Proxy::DHCP::Subnet.new("188.0.0.0", "252.0.0.0"),
Proxy::DHCP::Subnet.new("196.168.0.0", "255.255.255.192"),
Proxy::DHCP::Subnet.new("196.168.0.64", "255.255.255.224"),
Proxy::DHCP::Subnet.new("196.168.0.96", "255.255.255.224"),
Proxy::DHCP::Subnet.new("192.0.0.0", "252.0.0.0"),
Proxy::DHCP::Subnet.new("196.168.0.128", "255.255.255.192"),
Proxy::DHCP::Subnet.new("196.168.0.192", "255.255.255.192")]
@service.add_subnets(*subnets)
assert_not_nil @service.find_subnet("192.168.0.100")
assert_equal subnets[4], @service.find_subnet("192.168.0.100")
end
def test_find_subnet_by_host_ip
subnets = [Proxy::DHCP::Subnet.new("192.168.0.0", "255.255.255.0"),
Proxy::DHCP::Subnet.new("192.168.1.0", "255.255.255.0")]
test/dhcp_isc/state_changes_observer_test.rb
def setup
@config_file = Object.new
@leases_file = Object.new
@service = Proxy::DHCP::SubnetService.new(Proxy::MemoryStore.new, Proxy::MemoryStore.new,
@service = Proxy::DHCP::SubnetService.new(Proxy::MemoryStore.new,
Proxy::MemoryStore.new, Proxy::MemoryStore.new,
Proxy::MemoryStore.new, Proxy::MemoryStore.new)
@observer = ::Proxy::DHCP::ISC::IscStateChangesObserver.new(@config_file, @leases_file, @service)
test/dhcp_libvirt/dhcp_libvirt_provider_test.rb
@libvirt_network.stubs(:dump_xml).returns(fixture)
@libvirt_network.stubs(:dhcp_leases).returns(@json_leases)
@subnet = Proxy::DHCP::Subnet.new("192.168.122.0", "255.255.255.0")
@subnet_store = Proxy::MemoryStore.new
@service = Proxy::DHCP::SubnetService.new(@subnet_store, Proxy::MemoryStore.new, Proxy::MemoryStore.new,
Proxy::MemoryStore.new, Proxy::MemoryStore.new, Proxy::MemoryStore.new)
@subnet_store = {}
@service = Proxy::DHCP::SubnetService.new(Proxy::MemoryStore.new, Proxy::MemoryStore.new,
Proxy::MemoryStore.new, Proxy::MemoryStore.new, Proxy::MemoryStore.new, @subnet_store)
@subject = ::Proxy::DHCP::Libvirt::Provider.new('default', @libvirt_network, @service)
end

Also available in: Unified diff