Eliminate exhausted pools from allocation attempts

Our iterative address allocator in the allocation engine iterates over all addresses within a pool and tries if they are available one by one. That is very expensive when we get to the case of the nearly exhausted or completely exhausted pool. There are many different ideas how to improve the performance of free lease lookup, but many of them involve significant changes to the code.

I would like to propose a simple solution on our way towards more and more sophisticated allocation strategies.

The core idea is to add a new API call to the lease manager:

uint64_t getValidLeasesCount(IOAddress lower_bound, IOAdress upper_bound) const;

which would return the number of allocated leases (excluding expired) ones in that address range. This could be initially only implemented for Memfile and later for other backends. The backends for which it is not supported could always return 0.

The IterativeAllocator within the allocation engine could make use of this call for each pool it considers for allocation. It should call this function to see how many addresses are allocated in that pool and compare that with the pool size. If they are equal, the allocator gives up on this pool for this particular allocation. If it goes over all pools and all of them are exhausted it returns zero IP address to indicate to the calling code that it was unable to find an address. That would cause the allocation engine to drop the discover. There would be a lot less of useless trying.

The downside of this solution is that it adds extra query. This maybe specifically a concern in case when SQL database is in use for leases and the pools utilization is low. In those cases I'd recommend to add the following enhancement....

Extend the Pool with a new member:

uint64_t predicted_exhaustion_;

which would hold the value of

pool_size - getValidLeasesCount(a, b);

and would be decreased every time the new allocation takes place. The call to getValidLeasesCount() would only be made when this value hits 0. In some cases there may be other things impacting pool utilization, e.g. expired leases processing. In those cases would set this value straight to 0 to force an update.

For the starters I'd implement always checking the pool utilization without such adaptive mechanism, especially if doing it for memfile only.