Avoid passing negative available count to allocator

The available nodes are calculated in nodepool.py by

 n_provider = count_nodes_and_subnodes(provider.name)
 available = provider_max - n_provider

There is no guarantee this will not fall negative (one example: you
could reduce the max while servers were running).

When this happens, things can get hairy.  The general outline for
handing out nodes is as follows:

1) make the grant
2) calculate remaining availalbe nodes on this provider
3) re-distribute remaining sub-requests proportionally based on
   available nodes

Let us work through an example

 Provider-a has -5 nodes available
 Provider-b has 20 nodes available
 Request-x is for 5 label1
 Request-y is for 5 label2

Both requests can be satisified by either provider.

Request-x is be added to Provider-a.  It will create an sub-request
for 5 nodes from Provider-a.

We then add Request-x to Provider-b as well.  At this point, the
request should split into two sub-requests; one to each provider.

The calculation proceeds as follows.  It calculates the total number
of available nodes across all providers for this request, which in
this case is worked out as 20+(-5)=15

It then distributes the the nodes.

For Request-x, it works out a ratio of (-5/15)=-0.33. A sub-request of
(5*-0.33)=-1.66 nodes on Provider-a is created.

For Provider-b, the ratio is (20/15=1.66), and the sub-request for
Provider-b is adjusted to (5*1.66) = 6.666 nodes.

Request-y does the same thing for label2

We now have 4 sub-requests

 1) -1.66 label1 on Provider-a
 2) -1.66 label2 on Provider-b
 3) 6.66  label1 on Provider-a
 4) 6.66  label1 on Provider-b

It comes time to grant for Provider-a.

We find the total requests for Provider-a of -1.66+-1.66=-3.33.

The Request-x sub-request for -1.666 is assigned a ratio of
-1.666/-3.33 = 0.5; i.e. half the available nodes.

We grant the *smaller* of either the request (-1.66) or of
int(available*ratio) (e.g. int(-5*0.5=-2.5)=-3).  When using positive
numbers this is supposed to be either all the nodes you asked for if
possible, or your fair-share of the nodes if not.

Now things really get fun.  The allocator knows that it can't allocate
-3 nodes.  But it still takes -3 away from the available nodes in
Provider-a, e.g. (-5 - (-3) = -2).  And it thinks it allocated -3
nodes, so it takes -3 away from Request-x which makes it increase to
(5-(-3)) = 8.

Redistribution happens, but the result is it now looks like there is a
request for 8-nodes of label1 from Provider-b!  That has 20 nodes, so
it will actually allocate these.  We asked for 5 and got 8!

Note that this only comes into play *under capacity*.  Imagine x and y
were requests for 40 nodes.  Nothing is actually allocated on
Provider-a, but by the mechanism described the calculations inflate
the requests upwards to around 60 for Provider-b.  However, you never
notice, because there are only 20 Provider-b nodes and 40 nodes is
just as over-commited as 60.  The allocation completes just as usual
for the overcommitted case.

This is why this problem affects the round-robin allocator so badly.
It promotes small requests to the head of the queue where they get
over-allocated.

(did anyone get this far :)

If the provider is over-subscribed, there is nothing sensible to do
but ignore it by setting the available nodes to 0.  Maybe you reduced
the max-servers, and as the existing nodes delete we will come back
into sync.

To be doubly sure, we also clamp the available nodes to 0 in the
allocator

A test-case is added that follows the example given above

Change-Id: I40f432b00e619e38135d34ae15c98f12df52424b
Revert "Revert "Track last allocations to ensure forward-progress""

This reverts commit fb27c84bbf00154d4a246099feec32d47517c668.

Change I40f432b00e619e38135d34ae15c98f12df52424b avoids a
mis-calculation of current nodes that can cause too many nodes to be
created.  This adversley affects this change because it is making more
smaller allocations (see full description in other change).  These get
inflated and we start over-allocating nodes.

Change-Id: Ibdb357864bdc6f972530cbb22d12dcd97222b626
Change history allocation from list to dict

This change was suggested in review of the original.  It's a little
clearer to keep the values in a dict so you can tell a priori what is
being used.

Change-Id: I26716953d74342453bb934bba6d90860f32976cb
Some extra safety around negative numbers

An extra check that available is > 0, not just != 0.

Also, when rebalancing subrequests after a grant, if the grant
was not made, set the value of the subrequest to 0, and use that
when adjusting the amount available for the provider and amounts
of other subrequests.  In the case that a subrequest was for a
negative value, it could cause the total request amount as well
as the provider's available amount to increase.  Now the negative
case is handled as a grant of 0.

Change-Id: I83c56b35e02defaba8a7338dcdf17363d687266f
Starting changes for external devices.
Merge branch 'master' of https://github.com/dani4571/nodepool
Merge branch 'master' of https://git.openstack.org/openstack-infra/nodepool