Kea  2.1.7-git
isc::dhcp::FreeLeaseQueue Class Reference

Queue holding free leases for various address and prefix ranges. More...

#include <free_lease_queue.h>

Public Member Functions

 FreeLeaseQueue ()
 Constructor. More...
 
void addRange (const AddressRange &range)
 Adds new address range to the queue. More...
 
void addRange (const asiolink::IOAddress &start, const asiolink::IOAddress &end)
 Adds new address range to the queue. More...
 
void addRange (const PrefixRange &range)
 Adds new delegated prefix range to the queue. More...
 
void addRange (const asiolink::IOAddress &prefix, const uint8_t prefix_length, const uint8_t delegated_length)
 Adds new delegated prefix range to the queue. More...
 
bool append (const asiolink::IOAddress &address)
 Appends an address to the end of the queue for a range. More...
 
bool append (const asiolink::IOAddress &prefix, const uint8_t delegated_length)
 Appends a delegated prefix to the end of the queue for a range. More...
 
void append (const AddressRange &range, const asiolink::IOAddress &address)
 Appends an address to the end of the queue for a range. More...
 
void append (const PrefixRange &range, const asiolink::IOAddress &prefix)
 Appends a prefix to the end of the queue for a range. More...
 
void append (const uint64_t range_index, const asiolink::IOAddress &ip)
 Appends an address or prefix to the end of the queue for a range. More...
 
template<typename RangeType >
uint64_t getRangeIndex (const RangeType &range) const
 Returns range index. More...
 
template<typename RangeType >
asiolink::IOAddress next (const RangeType &range)
 Returns next free address or delegated prefix in the range. More...
 
template<typename RangeType >
asiolink::IOAddress pop (const RangeType &range)
 Pops and returns next free address or delegated prefix in the range. More...
 
template<typename RangeType >
bool removeRange (const RangeType &range)
 Removes the range from the queue. More...
 
bool use (const AddressRange &range, const asiolink::IOAddress &address)
 Removes the specified address from the free addresses. More...
 
bool use (const PrefixRange &range, const asiolink::IOAddress &prefix)
 Removes the specified delegated prefix from the free prefixes. More...
 

Detailed Description

Queue holding free leases for various address and prefix ranges.

Free leases can be stored in this queue to provide the DHCP allocation engine with the fast lookup mechanism for available leases. This avoids costly lookup for available leases in the lease database backend when the client's packet is being processed. Instead, when the server is being configured, it iterates over the addresses and/or prefixes in respective pools, verifies if leases exist for these addresses and/or prefixes and for each of them for which it doesn't find the lease it creates an appropriate entry in the queue.

This effectively moves the free lease lookup to the configuration phase. When the server is going to allocate a new lease, it will make an appropriate query to this queue to get the next available lease for the given pool. If the server decides to use this lease, it is removed from this queue. Conversely, when the lease expires (and is reclaimed) or is released it is returned to this queue so it can be offered to a requesting client at some later time.

The queue with free leases is optimized for two use cases. Firstly, it is optimized to get the next available address or prefix efficiently. In order to the get the next available lease the allocation engine can call the FreeLeaseQueue::next function. The range from which the lease is to be returned must be specified in the call. The range corresponds to the address or prefix pool boundaries. The next function puts the returned lease at the end of the queue. If the lease is rejected by the allocation engine for any reason, e.g. conflict with existing host reservations, the allocation engine simply calls next function again. It may need to perform multiple calls to the next function until it gets the satifactionary lease. However, it should be typically one call per allocation when no reservations are present or there is a low number of in pool reservations. If the allocation engine decides to allocate the returned lease, it must call FreeLeaseQueue::use to remove this lease from the queue.

If the FreeLeaseQueue::pop method is used instead of next to get the next available lease the returned lease is removed from the queue. In that case, the allocation engine must not call FreeLeaseQueue::use function when this lease is allocated. However, if the allocation engine rejects this lease the FreeLeaseQueue::append must be called to return the lease to the queue.

The second use case for which this queue is optimized is the lease reclamation. This is the process by which expired leases are again made available for allocation. The leases belonging to different pools expire at various times. When the expired leases are reclaimed the server doesn't know to which pools they belong. Since this queue associates free leases with certain ranges it is important that this container can efficiently identify the range. Once the range is identified, the reclaimed lease is appended to the end of the queue for that range.

Todo:
Methods of this class should be called in thread safe context. Otherwise they should be made thread safe.

Definition at line 82 of file free_lease_queue.h.

Constructor & Destructor Documentation

◆ FreeLeaseQueue()

isc::dhcp::FreeLeaseQueue::FreeLeaseQueue ( )

Constructor.

Definition at line 22 of file free_lease_queue.cc.

Member Function Documentation

◆ addRange() [1/4]

void isc::dhcp::FreeLeaseQueue::addRange ( const AddressRange range)

Adds new address range to the queue.

The new range must not overlap with existing ranges.

Parameters
rangethe new range to be added.
Exceptions
BadValueif the new range overlaps with any of the existing ranges.

Definition at line 27 of file free_lease_queue.cc.

References isc::dhcp::AddressRange::end_, and isc::dhcp::AddressRange::start_.

Referenced by addRange().

◆ addRange() [2/4]

void isc::dhcp::FreeLeaseQueue::addRange ( const asiolink::IOAddress start,
const asiolink::IOAddress end 
)

Adds new address range to the queue.

This variant of the method accepts the address range as a pair of start/end arguments.

Parameters
startbeginning of the new address range.
endend of the new address range.
Exceptions
BadValueif the new range overlaps with any of the existing ranges.

Definition at line 37 of file free_lease_queue.cc.

References addRange().

+ Here is the call graph for this function:

◆ addRange() [3/4]

void isc::dhcp::FreeLeaseQueue::addRange ( const PrefixRange range)

Adds new delegated prefix range to the queue.

The new range must not overlap with existing ranges.

Parameters
rangethe new range to be added.
Exceptions
BadValueof the new range overlaps with any of the existing ranges.

Definition at line 42 of file free_lease_queue.cc.

References isc::dhcp::PrefixRange::delegated_length_, isc::dhcp::PrefixRange::end_, isc::asiolink::offsetAddress(), and isc::dhcp::PrefixRange::start_.

+ Here is the call graph for this function:

◆ addRange() [4/4]

void isc::dhcp::FreeLeaseQueue::addRange ( const asiolink::IOAddress prefix,
const uint8_t  prefix_length,
const uint8_t  delegated_length 
)

Adds new delegated prefix range to the queue.

This variant of the method accepts the prefix range specified with three parameters: prefix, prefix length and delegated prefix length.

Parameters
prefixrange prefix.
prefix_lengthrange prefix length.
delegated_lengthdelegated prefix length.
Exceptions
BadValueif the new range overlaps with any of the existing ranges.

Definition at line 52 of file free_lease_queue.cc.

References addRange().

+ Here is the call graph for this function:

◆ append() [1/5]

bool isc::dhcp::FreeLeaseQueue::append ( const asiolink::IOAddress address)

Appends an address to the end of the queue for a range.

This method is typically called when a lease expires and is reclaimed. The range is not specified by the caller. The method identifies appropriate address range for that address.

Parameters
addressaddress to be appended to the range queue.
Returns
true if the range was found and the address was appended, false otherwise.

Definition at line 58 of file free_lease_queue.cc.

Referenced by append(), and removeRange().

◆ append() [2/5]

bool isc::dhcp::FreeLeaseQueue::append ( const asiolink::IOAddress prefix,
const uint8_t  delegated_length 
)

Appends a delegated prefix to the end of the queue for a range.

This method is typically called when a lease expires and is reclaimed. The range is not specified by the caller. The method identifies appropriate prefix range for that prefix.

Parameters
prefixdelegated prefix to be appended to the range queue.
delegated_lengthdelegated prefix length.
Returns
true if the range was found and the prefix was appended, false otherwise.

Definition at line 86 of file free_lease_queue.cc.

References append().

+ Here is the call graph for this function:

◆ append() [3/5]

void isc::dhcp::FreeLeaseQueue::append ( const AddressRange range,
const asiolink::IOAddress address 
)

Appends an address to the end of the queue for a range.

This method is typically called upon server startup or reconfiguration. For each address belonging to the pool for which there is no lease this method appends free address at the end of the queue for the specified range.

Parameters
rangespecifies the address range to which the given address belongs.
addressaddress to be appended to the range queue.
Exceptions
BadValueif the address does not belong to the specified range or if the given range does not exist.

Definition at line 115 of file free_lease_queue.cc.

◆ append() [4/5]

void isc::dhcp::FreeLeaseQueue::append ( const PrefixRange range,
const asiolink::IOAddress prefix 
)

Appends a prefix to the end of the queue for a range.

This method is typically called upon server startup or reconfiguration. For each delegated prefix belonging to the pool for which there is no lease this method appends free delegated prefix at the end of the queue for the specified range.

Parameters
rangespecifies the prefix range to which the given prefix belongs.
prefixdelegated prefix to be appended to the range queue.
Exceptions
BadValueif the prefix does not belong to the specified range or if the given range does not exist.

Definition at line 133 of file free_lease_queue.cc.

◆ append() [5/5]

void isc::dhcp::FreeLeaseQueue::append ( const uint64_t  range_index,
const asiolink::IOAddress ip 
)

Appends an address or prefix to the end of the queue for a range.

This variant of the append method is called upon server startup or reconfiguration. It is considered faster than the overload of this method taking the Range structure as an argument. The range is identified by the range_index which designates the range index in the queue returned by the getRangeIndex method. Use this method variant to add many addresses to the same range.

Parameters
range_indexaddress range index returned by getRangeIndex.
ipaddress or prefix to be appended to the range queue.
Exceptions
BadValueif the address or prefix does not belong to the specified range or if the given range does not exist.

Definition at line 123 of file free_lease_queue.cc.

References isc_throw.

◆ getRangeIndex()

template<typename RangeType >
uint64_t isc::dhcp::FreeLeaseQueue::getRangeIndex ( const RangeType &  range) const
inline

Returns range index.

The range index designates the position of the range within the queue. Searching for a range using the index is faster than searching by the range itself because it uses random access index.

Parameters
rangerange which index is to be returned.
Template Parameters
RangeTypetype of the range, i.e. AddressRange or PrefixRange.
Returns
range index.
Exceptions
BadValueif the range does not exist.

Definition at line 268 of file free_lease_queue.h.

References isc::asiolink::IOAddress::IPV4_ZERO_ADDRESS(), isc::asiolink::IOAddress::IPV6_ZERO_ADDRESS(), isc_throw, and next().

+ Here is the call graph for this function:

◆ next()

template<typename RangeType >
asiolink::IOAddress isc::dhcp::FreeLeaseQueue::next ( const RangeType &  range)
inline

Returns next free address or delegated prefix in the range.

This address or delegated prefix is moved to the end of the queue for the range.

Parameters
rangerange for which next address is to be returned.
Template Parameters
RangeTypetype of the range, i.e. AddressRange or PrefixRange.
Returns
Next free address or delegated prefix in that range.
Exceptions
BadValueif the range does not exist.

Definition at line 238 of file free_lease_queue.h.

Referenced by getRangeIndex().

◆ pop()

template<typename RangeType >
asiolink::IOAddress isc::dhcp::FreeLeaseQueue::pop ( const RangeType &  range)
inline

Pops and returns next free address or delegated prefix in the range.

The address or delegated prefix is removed from the queue. If the caller, i.e. allocation engine decides to not use this address or prefix it should be appended to the queue using the append method.

Parameters
rangerange for which next address or prefix is to be returned.
Template Parameters
RangeTypetype of the range, i.e. AddressRange or PrefixRange.
Returns
Next free address or delegated prefix in that range.
Exceptions
BadValueif the range does not exist.

Definition at line 253 of file free_lease_queue.h.

◆ removeRange()

template<typename RangeType >
bool isc::dhcp::FreeLeaseQueue::removeRange ( const RangeType &  range)
inline

Removes the range from the queue.

It removes all free leases associated with the removed address range.

Parameters
rangerange to be removed.
Template Parameters
RangeTypetype of the range, i.e. Range or PrefixRange.
Returns
true if the range existed and was removed.

Definition at line 134 of file free_lease_queue.h.

References append(), and use().

+ Here is the call graph for this function:

◆ use() [1/2]

bool isc::dhcp::FreeLeaseQueue::use ( const AddressRange range,
const asiolink::IOAddress address 
)

Removes the specified address from the free addresses.

This method should be called upon successful lease allocation for that address.

Parameters
rangerange from which the free address should be removed.
addressaddress to remove.
Returns
true if the address was found and successfully removed, false otherwise.
Exceptions
BadValueif the range does not exist.

Definition at line 140 of file free_lease_queue.cc.

Referenced by removeRange().

◆ use() [2/2]

bool isc::dhcp::FreeLeaseQueue::use ( const PrefixRange range,
const asiolink::IOAddress prefix 
)

Removes the specified delegated prefix from the free prefixes.

This method should be called upon successful lease allocation for that delegated prefix.

Parameters
rangerange from which the free prefix should be removed.
prefixprefix to remove.
Returns
true if the prefix was found and successfully removed, false otherwise.
Exceptions
BadValueif the range does not exist.

Definition at line 152 of file free_lease_queue.cc.

References isc::dhcp::PrefixRange::delegated_length_, isc::dhcp::AddressRange::end_, isc_throw, isc::dhcp::AddressRange::start_, and isc::dhcp::PrefixRange::start_.


The documentation for this class was generated from the following files: