[Cake] Heaps of cake

[Cake] Heaps of cake

[Jonathan Morton]

I’ve just pushed my latest set of updates, the main feature of which is the replacement of the linear search in cake_drop() with a heap structure.  For efficiency, the heap is constructed the first time a packet drop is required (on overflow) and maintained incrementally thereafter until 64K packets have been delivered without an overflow occurring.

Please do hammer on these codepaths for all you’re worth.  It compiles and survives a smoke-test, that’s all I know so far.

I also took the opportunity to remove a variable which was widely read but never written, except for initialisation.  The number of queues per tin is thus now a compile-time constant.  This should be an efficiency improvement, as well as removing magic numbers from a few places.

 - Jonathan Morton

Re: [Cake] Heaps of cake

[Jonathan Morton]

> On 21 May, 2016, at 01:07, Jonathan Morton <chromatix99@gmail.com> wrote:
> 
> Please do hammer on these codepaths for all you’re worth.  It compiles and survives a smoke-test, that’s all I know so far.

Having noted a series of kernel panics in cake_drop(), I eventually traced the fault to dequeue_head(), which AFAIK hadn’t been touched since the first version (as it was lifted from fq_codel).  If it’s called on en empty subqueue, it tried to read NULL->next.

The question remains why cake_drop() would select an empty subqueue as the longest one - evidently there’s a missing heap update somewhere.  But at least now it won’t crash if that happens.

 - Jonathan Morton

Re: [Cake] Heaps of cake

[Kevin Darbyshire-Bryant]

On 29/05/16 03:32, Jonathan Morton wrote:
>
>> On 21 May, 2016, at 01:07, Jonathan Morton <chromatix99@gmail.com> wrote:
>>
>> Please do hammer on these codepaths for all you’re worth.  It compiles and survives a smoke-test, that’s all I know so far.
>
> Having noted a series of kernel panics in cake_drop(), I eventually traced the fault to dequeue_head(), which AFAIK hadn’t been touched since the first version (as it was lifted from fq_codel).  If it’s called on en empty subqueue, it tried to read NULL->next.
>
> The question remains why cake_drop() would select an empty subqueue as the longest one - evidently there’s a missing heap update somewhere.  But at least now it won’t crash if that happens.
>
>   - Jonathan Morton

Pointed my build at the latest code, so far no unexpected out-to-lunch 
moments :-)

Thanks for continuing to work on making things stable again.

Kevin