[LITMUS^RT] Binary heaps for Litmus

[Glenn Elliott]

On Mar 30, 2012, at 10:48 AM, Björn Brandenburg wrote:

> On Mar 22, 2012, at 12:29 AM, Glenn Elliott wrote:
> 
>> I realized that binheap_delete() was more complicated than necessary.  Cleaned that up and then added binheap_decrease().  Sorry for the explosion of patches.
>> 
> 
> The attached patches are difficult to comment on. I'll copy and paste some segments.
> 
>> 
>> 365	        /* NULL data pointers are used internally */
>> 366	        if(!data) {
>> 367	                WARN();
>> 368	                return;
>> 369	        }
> 
> 
> Should that be a BUG_ON(!data)? It's clearly a misuse of the API, so why only a WARN()? It's not like the user could be expected to do anything about this. A BUG_ON() at least makes sure that it's noticed.

I agree.  I had been more gentle in my testing.

>> 422	static inline void __binheap_delete_root(struct binheap_handle *handle,
>> 423	                                                                                 struct binheap_node *container)
>> 
>> 500	static inline void __binheap_delete(
>> 501	                                                                struct binheap_node *node_to_delete,
>> 502	                                                                struct binheap_node *user_of_node,
>> 503	                                                                struct binheap_handle *handle)
>> 504	
>> 
> 
> I don't know what your TAB setting is, but the above code looks very strangely indented to me (same in chit).

That can be easily fixed.

> I'm also not quite sure what replacing the  binomial heap in GSN-EDF with a binary heap is buying us.  The new code still relies on dynamic memory allocation and does not look much simpler to me than the existing binomial heap implementation. Is there some pressing need? I'm not really opposed to it, but I'd like to understand the motivation.

The binheap implementation doesn't necessarily rely on dynamic memory.  For example, heap nodes could be allocated on call stacks (similar to linked list nodes when used with Linux wait queues).

Normally I agree that more code results in more bugs and maintenance problems.  If binheaps could only be used for the CPU priority ordering, I would rather stick to binomial heaps.  However, the binheaps have other applications and are being used extensively in work being done here at UNC.  Applying the binheaps to CPU priority ordering seemed like an easy way for binheaps to get into Litmus quickly.

> Anyway, before this is merged, I think it should be rebased to hide the fixup commits. (Commit bdce67bc2babc2e5b3b2440964e9cf819ac814dc contains unrelated changes, for example).

I agree.

> Thanks,
> Björn