linux-kernel - Re: [RFC 3/5] Replacement policy on heap overfull

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 27 Jun 2008 08:37:34 -0700
From:	"Paul Menage" <menage@...gle.com>
To:	"Balbir Singh" <balbir@...ux.vnet.ibm.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

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?

> +       if (policy == HEAP_REP_TOP)

switch() here?

> +               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.

Paul
--
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/