aboutsummaryrefslogtreecommitdiffstats
path: root/lib/prio_heap.c
diff options
context:
space:
mode:
authorPaul Menage <menage@google.com>2007-10-19 02:40:22 -0400
committerLinus Torvalds <torvalds@woody.linux-foundation.org>2007-10-19 14:53:41 -0400
commit8707d8b8c0cbdf4441507f8dded194167da896c7 (patch)
tree1e9ac6b15027bd55263378e551c1595a937d66d6 /lib/prio_heap.c
parent020958b6272882c1a8bfbe5f3e0927f3845c2698 (diff)
Fix cpusets update_cpumask
Cause writes to cpuset "cpus" file to update cpus_allowed for member tasks: - collect batches of tasks under tasklist_lock and then call set_cpus_allowed() on them outside the lock (since this can sleep). - add a simple generic priority heap type to allow efficient collection of batches of tasks to be processed without duplicating or missing any tasks in subsequent batches. - make "cpus" file update a no-op if the mask hasn't changed - fix race between update_cpumask() and sched_setaffinity() by making sched_setaffinity() post-check that it's not running on any cpus outside cpuset_cpus_allowed(). [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Paul Menage <menage@google.com> Cc: Paul Jackson <pj@sgi.com> Cc: David Rientjes <rientjes@google.com> Cc: Nick Piggin <nickpiggin@yahoo.com.au> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Balbir Singh <balbir@in.ibm.com> Cc: Cedric Le Goater <clg@fr.ibm.com> Cc: "Eric W. Biederman" <ebiederm@xmission.com> Cc: Serge Hallyn <serue@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/prio_heap.c')
-rw-r--r--lib/prio_heap.c70
1 files changed, 70 insertions, 0 deletions
diff --git a/lib/prio_heap.c b/lib/prio_heap.c
new file mode 100644
index 000000000000..471944a54e23
--- /dev/null
+++ b/lib/prio_heap.c
@@ -0,0 +1,70 @@
1/*
2 * Simple insertion-only static-sized priority heap containing
3 * pointers, based on CLR, chapter 7
4 */
5
6#include <linux/slab.h>
7#include <linux/prio_heap.h>
8
9int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask,
10 int (*gt)(void *, void *))
11{
12 heap->ptrs = kmalloc(size, gfp_mask);
13 if (!heap->ptrs)
14 return -ENOMEM;
15 heap->size = 0;
16 heap->max = size / sizeof(void *);
17 heap->gt = gt;
18 return 0;
19}
20
21void heap_free(struct ptr_heap *heap)
22{
23 kfree(heap->ptrs);
24}
25
26void *heap_insert(struct ptr_heap *heap, void *p)
27{
28 void *res;
29 void **ptrs = heap->ptrs;
30 int pos;
31
32 if (heap->size < heap->max) {
33 /* Heap insertion */
34 int pos = heap->size++;
35 while (pos > 0 && heap->gt(p, ptrs[(pos-1)/2])) {
36 ptrs[pos] = ptrs[(pos-1)/2];
37 pos = (pos-1)/2;
38 }
39 ptrs[pos] = p;
40 return NULL;
41 }
42
43 /* The heap is full, so something will have to be dropped */
44
45 /* If the new pointer is greater than the current max, drop it */
46 if (heap->gt(p, ptrs[0]))
47 return p;
48
49 /* Replace the current max and heapify */
50 res = ptrs[0];
51 ptrs[0] = p;
52 pos = 0;
53
54 while (1) {
55 int left = 2 * pos + 1;
56 int right = 2 * pos + 2;
57 int largest = pos;
58 if (left < heap->size && heap->gt(ptrs[left], p))
59 largest = left;
60 if (right < heap->size && heap->gt(ptrs[right], ptrs[largest]))
61 largest = right;
62 if (largest == pos)
63 break;
64 /* Push p down the heap one level and bump one up */
65 ptrs[pos] = ptrs[largest];
66 ptrs[largest] = p;
67 pos = largest;
68 }
69 return res;
70}