| 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
| ||
|
Date: Sat, 9 Oct 2010 16:37:24 -0400
From: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To: Paul Menage <menage@...gle.com>
Cc: Steven Rostedt <rostedt@...dmis.org>,
LKML <linux-kernel@...r.kernel.org>,
Linus Torvalds <torvalds@...ux-foundation.org>,
Andrew Morton <akpm@...ux-foundation.org>,
Peter Zijlstra <peterz@...radead.org>,
Ingo Molnar <mingo@...e.hu>,
Frederic Weisbecker <fweisbec@...il.com>,
Thomas Gleixner <tglx@...utronix.de>,
Christoph Hellwig <hch@....de>, Li Zefan <lizf@...fujitsu.com>,
Lai Jiangshan <laijs@...fujitsu.com>,
Johannes Berg <johannes.berg@...el.com>,
Masami Hiramatsu <masami.hiramatsu.pt@...achi.com>,
Arnaldo Carvalho de Melo <acme@...radead.org>,
Tom Zanussi <tzanussi@...il.com>,
KOSAKI Motohiro <kosaki.motohiro@...fujitsu.com>,
Andi Kleen <andi@...stfloor.org>,
"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
David Rientjes <rientjes@...gle.com>,
Nick Piggin <nickpiggin@...oo.com.au>,
Balbir Singh <balbir@...ibm.com>,
Cedric Le Goater <clg@...ibm.com>,
"Eric W. Biederman" <ebiederm@...ssion.com>
Subject: Re: [PATCH] Prio_heap: heap_remove(), heap_maximum(),
heap_replace() and heap_cherrypick()
* Paul Menage (menage@...gle.com) wrote:
> On Thu, Oct 7, 2010 at 12:03 PM, Mathieu Desnoyers
> <mathieu.desnoyers@...icios.com> wrote:
> > These added interfaces lets prio_heap users lookup the top of heap item without
> > performing any insertion, perform removal of the topmost heap entry, and also
> > replacement of topmost heap entry. This is useful if one need to use the result
> > of the lookup to determine if the current maximum should simply be removed or if
> > it should be replaced.
> >
> > This is used by the Generic Ring Buffer to perform timestamp-based fusion-merge
> > of per-cpu buffer records into a single stream.
> >
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
>
> Looks fine, other than a couple of suggestions to make the code
> slightly clearer.
>
> Acked-by: Paul Menage <menage@...gle.com>
>
> > Acked-by: Balbir Singh <balbir@...ibm.com>
> > Cc: Paul Menage <menage@...gle.com>
> > Cc: David Rientjes <rientjes@...gle.com>
> > Cc: Cedric Le Goater <clg@...ibm.com>
> > Cc: "Eric W. Biederman" <ebiederm@...ssion.com>
> > Cc: Andrew Morton <akpm@...ux-foundation.org>
> > Cc: Linus Torvalds <torvalds@...ux-foundation.org>
> > ---
> > include/linux/prio_heap.h | 44 ++++++++++++++++++++++
> > lib/prio_heap.c | 91 ++++++++++++++++++++++++++++++++++++----------
> > 2 files changed, 116 insertions(+), 19 deletions(-)
> >
> > Index: linux.trees.git/include/linux/prio_heap.h
> > ===================================================================
> > --- linux.trees.git.orig/include/linux/prio_heap.h 2010-07-06 14:25:29.000000000 -0400
> > +++ linux.trees.git/include/linux/prio_heap.h 2010-07-07 10:04:33.000000000 -0400
> > @@ -23,6 +23,18 @@ struct ptr_heap {
> > };
> >
> > /**
> > + * heap_maximum - return the largest element in the heap
> > + * @heap: the heap to be operated on
> > + *
> > + * Returns the largest element in the heap, without performing any modification
> > + * to the heap structure. Returns NULL if the heap is empty.
> > + */
> > +static inline void *heap_maximum(const struct ptr_heap *heap)
> > +{
> > + return heap->size ? heap->ptrs[0] : NULL;
> > +}
> > +
> > +/**
> > * heap_init - initialize an empty heap with a given memory size
> > * @heap: the heap structure to be initialized
> > * @size: amount of memory to use in bytes
> > @@ -53,6 +65,38 @@ void heap_free(struct ptr_heap *heap);
> > */
> > extern void *heap_insert(struct ptr_heap *heap, void *p);
> >
> > +/**
> > + * heap_remove - remove the largest element from the heap
> > + * @heap: the heap to be operated on
> > + *
> > + * Returns the largest element in the heap. It removes this element from the
> > + * heap. Returns NULL if the heap is empty.
> > + */
> > +extern void *heap_remove(struct ptr_heap *heap);
> >
> > +/**
> > + * heap_cherrypick - remove a given element from the heap
> > + * @heap: the heap to be operated on
> > + * @p: the element
> > + *
> > + * Remove the given element from the heap. Return the element if present, else
> > + * return NULL. This algorithm has a complexity of O(n), which is higher than
> > + * O(log(n)) provided by the rest of this API.
> > + */
> > +extern void *heap_cherrypick(struct ptr_heap *heap, void *p);
> > +
> > +/**
> > + * heap_replace_max - replace the the largest element from the heap
> > + * @heap: the heap to be operated on
> > + * @p: the pointer to be inserted as topmost element replacement
> > + *
> > + * Returns the largest element in the heap. It removes this element from the
> > + * heap. The heap is rebalanced only once after the insertion. Returns NULL if
> > + * the heap is empty.
> > + *
> > + * This is the equivalent of calling heap_remove() and then heap_insert(), but
> > + * it only rebalances the heap once.
> > + */
> > +extern void *heap_replace_max(struct ptr_heap *heap, void *p);
> >
> > #endif /* _LINUX_PRIO_HEAP_H */
> > Index: linux.trees.git/lib/prio_heap.c
> > ===================================================================
> > --- linux.trees.git.orig/lib/prio_heap.c 2010-07-06 14:25:29.000000000 -0400
> > +++ linux.trees.git/lib/prio_heap.c 2010-07-07 10:18:32.000000000 -0400
> > @@ -23,12 +23,49 @@ void heap_free(struct ptr_heap *heap)
> > kfree(heap->ptrs);
> > }
> >
> > -void *heap_insert(struct ptr_heap *heap, void *p)
> > +static void heapify(struct ptr_heap *heap, void **ptrs, void *p, int pos)
>
> I'd be inclined to not pass "ptrs" or "p" as an argument, and instead
> get ptrs from heap->ptrs and p from ptrs[pos]. It makes it clearer
> what heapify() is doing.
OK.
>
> > +void *heap_replace_max(struct ptr_heap *heap, void *p)
> > {
> > void *res;
> > void **ptrs = heap->ptrs;
> > int pos;
>
> No need for "pos" - just pass a constant 0 to heapify()
OK
> >
> > + if (!heap->size) {
> > + ptrs[heap->size++] = p;
>
> Maybe make this clearer?
>
> ptrs[0] = p;
> heap->size = 1;
OK.
>
> > +void *heap_remove(struct ptr_heap *heap)
> > +{
> > + void **ptrs = heap->ptrs;
> > +
> > + switch (heap->size) {
> > + case 0:
> > + return NULL;
> > + case 1:
> > + return ptrs[--heap->size];
>
> Maybe clearer:
>
> heap->size = 0;
> return ptrs[0];
Yep, I changed the same thing in heap_cherrypick too.
Thanks!
Mathieu
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
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