| 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 17:03:58 -0400
From: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To: Paul Menage <menage@...gle.com>,
Steven Rostedt <rostedt@...dmis.org>,
LKML <linux-kernel@...r.kernel.org>,
Lai Jiangshan <laijs@...fujitsu.com>,
Balbir Singh <balbir@...ibm.com>
Cc: 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>,
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>,
Cedric Le Goater <clg@...ibm.com>,
"Eric W. Biederman" <ebiederm@...ssion.com>
Subject: [PATCH] Prio_heap: heap_remove(), heap_maximum(), heap_replace()
and heap_cherrypick() (v2)
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.
Changelog since v1:
- Apply cleanups recommended by Lai Jiangshan.
- Apply cleanups recommended by Paul Menage.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Acked-by: Balbir Singh <balbir@...ibm.com>
Acked-by: Paul Menage <menage@...gle.com>
Reviewed-by: Lai Jiangshan <laijs@...fujitsu.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 | 47 ++++++++++++++++++++-
lib/prio_heap.c | 99 ++++++++++++++++++++++++++++++++++++----------
2 files changed, 123 insertions(+), 23 deletions(-)
Index: linux.trees.git/include/linux/prio_heap.h
===================================================================
--- linux.trees.git.orig/include/linux/prio_heap.h
+++ linux.trees.git/include/linux/prio_heap.h
@@ -2,8 +2,7 @@
#define _LINUX_PRIO_HEAP_H
/*
- * Simple insertion-only static-sized priority heap containing
- * pointers, based on CLR, chapter 7
+ * Static-sized priority heap containing pointers. Based on CLR, chapter 7.
*/
#include <linux/gfp.h>
@@ -23,6 +22,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 +64,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
+++ linux.trees.git/lib/prio_heap.c
@@ -1,6 +1,5 @@
/*
- * Simple insertion-only static-sized priority heap containing
- * pointers, based on CLR, chapter 7
+ * Static-sized priority heap containing pointers. Based on CLR, chapter 7.
*/
#include <linux/slab.h>
@@ -23,10 +22,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, int pos)
+{
+ void **ptrs = heap->ptrs;
+ void *p = ptrs[pos];
+
+ while (1) {
+ int left = 2 * pos + 1;
+ int right = 2 * pos + 2;
+ int largest = pos;
+ if (left < heap->size && heap->gt(ptrs[left], p))
+ largest = left;
+ if (right < heap->size && heap->gt(ptrs[right], ptrs[largest]))
+ largest = right;
+ if (largest == pos)
+ break;
+ /* Push p down the heap one level and bump one up */
+ ptrs[pos] = ptrs[largest];
+ ptrs[largest] = p;
+ pos = largest;
+ }
+}
+
+void *heap_replace_max(struct ptr_heap *heap, void *p)
{
void *res;
void **ptrs = heap->ptrs;
+
+ if (!heap->size) {
+ ptrs[0] = p;
+ heap->size = 1;
+ return NULL;
+ }
+
+ /* Replace the current max and heapify */
+ res = ptrs[0];
+ ptrs[0] = p;
+ heapify(heap, 0);
+ return res;
+}
+
+void *heap_insert(struct ptr_heap *heap, void *p)
+{
+ void **ptrs = heap->ptrs;
int pos;
if (heap->size < heap->max) {
@@ -47,24 +85,43 @@ void *heap_insert(struct ptr_heap *heap,
return p;
/* Replace the current max and heapify */
- res = ptrs[0];
- ptrs[0] = p;
- pos = 0;
+ return heap_replace_max(heap, p);
+}
- while (1) {
- int left = 2 * pos + 1;
- int right = 2 * pos + 2;
- int largest = pos;
- if (left < heap->size && heap->gt(ptrs[left], p))
- largest = left;
- if (right < heap->size && heap->gt(ptrs[right], ptrs[largest]))
- largest = right;
- if (largest == pos)
- break;
- /* Push p down the heap one level and bump one up */
- ptrs[pos] = ptrs[largest];
- ptrs[largest] = p;
- pos = largest;
+void *heap_remove(struct ptr_heap *heap)
+{
+ void **ptrs = heap->ptrs;
+
+ switch (heap->size) {
+ case 0:
+ return NULL;
+ case 1:
+ heap->size = 0;
+ return ptrs[0];
}
- return res;
+
+ /* Shrink, replace the current max by previous last entry and heapify */
+ return heap_replace_max(heap, ptrs[--heap->size]);
+}
+
+void *heap_cherrypick(struct ptr_heap *heap, void *p)
+{
+ void **ptrs = heap->ptrs;
+ size_t pos, size = heap->size;
+
+ for (pos = 0; pos < size; pos++)
+ if (ptrs[pos] == p)
+ goto found;
+ return NULL;
+found:
+ if (heap->size == 1) {
+ heap->size = 0;
+ return ptrs[0];
+ }
+ /*
+ * Replace p with previous last entry and heapify.
+ */
+ ptrs[pos] = ptrs[--heap->size];
+ heapify(heap, pos);
+ return p;
}
--
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