[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <4868572B.5070006@linux.vnet.ibm.com>
Date: Mon, 30 Jun 2008 09:16:51 +0530
From: Balbir Singh <balbir@...ux.vnet.ibm.com>
To: Paul Menage <menage@...gle.com>
CC: Andrew Morton <akpm@...ux-foundation.org>,
YAMAMOTO Takashi <yamamoto@...inux.co.jp>,
linux-kernel@...r.kernel.org, linux-mm@...ck.org,
KAMEZAWA Hiroyuki <kamezawa.hiroyu@...fujitsu.com>
Subject: Re: [RFC 3/5] Replacement policy on heap overfull
Paul Menage wrote:
> On Fri, Jun 27, 2008 at 8:18 AM, Balbir Singh <balbir@...ux.vnet.ibm.com> wrote:
>>
>> This patch adds a policy parameter to heap_insert. While inserting an element
>> if the heap is full, the policy determines which element to replace.
>> The default earlier is now obtained by passing the policy as HEAP_REP_TOP.
>> The new HEAP_REP_LEAF policy, replaces a leaf node (the last element).
>>
>> Signed-off-by: Balbir Singh <balbir@...ux.vnet.ibm.com>
>> ---
>>
>> include/linux/prio_heap.h | 9 ++++++++-
>> kernel/cgroup.c | 2 +-
>> lib/prio_heap.c | 31 +++++++++++++++++++++++--------
>> 3 files changed, 32 insertions(+), 10 deletions(-)
>>
>> diff -puN include/linux/prio_heap.h~prio_heap_replace_leaf include/linux/prio_heap.h
>> --- linux-2.6.26-rc5/include/linux/prio_heap.h~prio_heap_replace_leaf 2008-06-27 20:43:09.000000000 +0530
>> +++ linux-2.6.26-rc5-balbir/include/linux/prio_heap.h 2008-06-27 20:43:09.000000000 +0530
>> @@ -22,6 +22,11 @@ struct ptr_heap {
>> int (*gt)(void *, void *);
>> };
>>
>> +enum heap_replacement_policy {
>> + HEAP_REP_LEAF,
>> + HEAP_REP_TOP,
>> +};
>
> Maybe "drop" rather than "replace"? HEAP_REP_TOP doesn't replace the
> top element if you insert a new higher element, it drops the top.
>
> How about HEAP_DROP_LEAF and HEAP_DROP_MAX? You could also provide a
> HEAP_DROP_MIN with the caveat that it would take linear time.
>
> Add comments here about what these mean?
>
Sure, will do
>> + if (policy == HEAP_REP_TOP)
>
> switch() here?
>
Can switch over
>> + if (heap->gt(p, ptrs[0]))
>> + return p;
>> +
>> + if (policy == HEAP_REP_LEAF) {
>> + /* Heap insertion */
>> + int pos = heap->size - 1;
>> + res = ptrs[pos];
>> + heap_insert_at(heap, p, pos);
>> + return res;
>> + }
>>
>> /* Replace the current max and heapify */
>> res = ptrs[0];
>
> This should probably be in the arm dealing with
> HEAP_REP_TOP/HEAP_DROP_MAX since we only get here in that case.
I can do that, I'll need to rearrange the code and merge the condition above
with the ->gt check into HEAP_DROP_MAX
--
Warm Regards,
Balbir Singh
Linux Technology Center
IBM, ISTL
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists