| 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: Fri, 27 Jun 2008 20:48:38 +0530
From: Balbir Singh <balbir@...ux.vnet.ibm.com>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: YAMAMOTO Takashi <yamamoto@...inux.co.jp>,
Paul Menage <menage@...gle.com>, linux-kernel@...r.kernel.org,
linux-mm@...ck.org, Balbir Singh <balbir@...ux.vnet.ibm.com>,
KAMEZAWA Hiroyuki <kamezawa.hiroyu@...fujitsu.com>
Subject: [RFC 3/5] Replacement policy on heap overfull
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,
+};
+
/**
* heap_init - initialize an empty heap with a given memory size
* @heap: the heap structure to be initialized
@@ -42,6 +47,8 @@ void heap_free(struct ptr_heap *heap);
* heap_insert - insert a value into the heap and return any overflowed value
* @heap: the heap to be operated on
* @p: the pointer to be inserted
+ * @policy: Heap replacement policy, when heap is full. Replace the top
+ * of the heap or the leaf at the end of the array
*
* Attempts to insert the given value into the priority heap. If the
* heap is full prior to the insertion, then the resulting heap will
@@ -51,7 +58,7 @@ void heap_free(struct ptr_heap *heap);
* (i.e. no change to the heap) if the new element is greater than all
* elements currently in the heap.
*/
-extern void *heap_insert(struct ptr_heap *heap, void *p);
+extern void *heap_insert(struct ptr_heap *heap, void *p, int policy);
/**
* heap_delete_max - delete the maximum element from the top of the heap
diff -puN lib/prio_heap.c~prio_heap_replace_leaf lib/prio_heap.c
--- linux-2.6.26-rc5/lib/prio_heap.c~prio_heap_replace_leaf 2008-06-27 20:43:09.000000000 +0530
+++ linux-2.6.26-rc5-balbir/lib/prio_heap.c 2008-06-27 20:43:09.000000000 +0530
@@ -46,7 +46,17 @@ static void heap_adjust(struct ptr_heap
}
}
-void *heap_insert(struct ptr_heap *heap, void *p)
+static void heap_insert_at(struct ptr_heap *heap, void *p, int pos)
+{
+ void **ptrs = heap->ptrs;
+ while (pos > 0 && heap->gt(p, ptrs[(pos-1)/2])) {
+ ptrs[pos] = ptrs[(pos-1)/2];
+ pos = (pos-1)/2;
+ }
+ ptrs[pos] = p;
+}
+
+void *heap_insert(struct ptr_heap *heap, void *p, int policy)
{
void *res;
void **ptrs = heap->ptrs;
@@ -54,19 +64,24 @@ void *heap_insert(struct ptr_heap *heap,
if (heap->size < heap->max) {
/* Heap insertion */
int pos = heap->size++;
- while (pos > 0 && heap->gt(p, ptrs[(pos-1)/2])) {
- ptrs[pos] = ptrs[(pos-1)/2];
- pos = (pos-1)/2;
- }
- ptrs[pos] = p;
+ heap_insert_at(heap, p, pos);
return NULL;
}
/* The heap is full, so something will have to be dropped */
/* If the new pointer is greater than the current max, drop it */
- if (heap->gt(p, ptrs[0]))
- return p;
+ if (policy == HEAP_REP_TOP)
+ 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];
diff -puN kernel/cgroup.c~prio_heap_replace_leaf kernel/cgroup.c
--- linux-2.6.26-rc5/kernel/cgroup.c~prio_heap_replace_leaf 2008-06-27 20:43:09.000000000 +0530
+++ linux-2.6.26-rc5-balbir/kernel/cgroup.c 2008-06-27 20:43:09.000000000 +0530
@@ -1976,7 +1976,7 @@ int cgroup_scan_tasks(struct cgroup_scan
*/
if (!started_after_time(p, &latest_time, latest_task))
continue;
- dropped = heap_insert(heap, p);
+ dropped = heap_insert(heap, p, HEAP_REP_TOP);
if (dropped == NULL) {
/*
* The new task was inserted; the heap wasn't
_
--
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