linux-kernel - Re: [RFC PATCH] Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap

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] [day] [month] [year] [list]

Message-ID: <20101007062414.GA28631@Krystal>
Date:	Thu, 7 Oct 2010 02:24:14 -0400
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	Balbir Singh <balbir@...ux.vnet.ibm.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>,
	Paul Menage <menage@...gle.com>,
	David Rientjes <rientjes@...gle.com>,
	Nick Piggin <nickpiggin@...oo.com.au>,
	Cedric Le Goater <clg@...t.ibm.com>,
	"Eric W. Biederman" <ebiederm@...ssion.com>
Subject: Re: [RFC PATCH] Prio_heap: heap_remove(), heap_maximum(),
	heap_replace() and heap_cherrypick()

* Balbir Singh (balbir@...ux.vnet.ibm.com) wrote:
> * Mathieu Desnoyers <mathieu.desnoyers@...icios.com> [2010-10-06 14:03:23]:
> 
> > 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>
> > Cc: Paul Menage <menage@...gle.com>
> > Cc: David Rientjes <rientjes@...gle.com>
> > Cc: Nick Piggin <nickpiggin@...oo.com.au>
> > Cc: Balbir Singh <balbir@...ibm.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>
> > ---
> 
> The patchset looks good to me, one comment on cherry picking below
> 
> Acked-by: Balbir Singh <balbir@...ux.vnet.ibm.com>

Thanks!

[...]
> > +/**
> > + * 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);
> 
> One way to reduce cherrypick'ing in O(n) if n is large, is to sort the
> entire heap using heapify() and then doing a binary search. The cost
> of sorting is high, so it depends on how often and in what phases we
> cherry pick.

I need this to implement the ring buffer iterator "reset" primitive, which is
very infrequently called. So for my use-case, I really prefer to keep very fast
add/remove/get max (as implemented currently) without sorting the rest of the
heap. What you propose looks more like a balanced binary tree, which we already
have in the kernel, but clearly adds some overhead by requiring to keep the
whole tree sorted.

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/