From 2a53eb6929f4de58a175f4f180a5a5c9a6201374 Mon Sep 17 00:00:00 2001 From: Greg Kroah-Hartman Date: Mon, 13 Feb 2012 11:03:09 -0800 Subject: [PATCH] add forgotten lttng patch --- .../0000-lttng-lib-lttng-priority-heap.patch | 344 +++++++++++++++++++++ series | 1 + 2 files changed, 345 insertions(+) create mode 100644 patches.lttng/0000-lttng-lib-lttng-priority-heap.patch diff --git a/patches.lttng/0000-lttng-lib-lttng-priority-heap.patch b/patches.lttng/0000-lttng-lib-lttng-priority-heap.patch new file mode 100644 index 0000000..2c7aa68 --- /dev/null +++ b/patches.lttng/0000-lttng-lib-lttng-priority-heap.patch @@ -0,0 +1,344 @@ +From 1b4d28b622fd88745fc020dd3e363e586e4f9943 Mon Sep 17 00:00:00 2001 +From: Mathieu Desnoyers +Date: Mon, 28 Nov 2011 07:42:08 -0500 +Subject: lttng lib: lttng priority heap + +Signed-off-by: Mathieu Desnoyers +Signed-off-by: Greg Kroah-Hartman + +diff --git a/drivers/staging/lttng/lib/prio_heap/lttng_prio_heap.c b/drivers/staging/lttng/lib/prio_heap/lttng_prio_heap.c +new file mode 100644 +index 0000000..2fce143 +--- /dev/null ++++ b/drivers/staging/lttng/lib/prio_heap/lttng_prio_heap.c +@@ -0,0 +1,207 @@ ++/* ++ * lttng_prio_heap.c ++ * ++ * Priority heap containing pointers. Based on CLRS, chapter 6. ++ * ++ * Copyright 2011 - Mathieu Desnoyers ++ * ++ * Permission is hereby granted, free of charge, to any person obtaining a copy ++ * of this software and associated documentation files (the "Software"), to deal ++ * in the Software without restriction, including without limitation the rights ++ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell ++ * copies of the Software, and to permit persons to whom the Software is ++ * furnished to do so, subject to the following conditions: ++ * ++ * The above copyright notice and this permission notice shall be included in ++ * all copies or substantial portions of the Software. ++ */ ++ ++#include ++#include "lttng_prio_heap.h" ++ ++#ifdef DEBUG_HEAP ++void lttng_check_heap(const struct lttng_ptr_heap *heap) ++{ ++ size_t i; ++ ++ if (!heap->len) ++ return; ++ ++ for (i = 1; i < heap->len; i++) ++ WARN_ON_ONCE(!heap->gt(heap->ptrs[i], heap->ptrs[0])); ++} ++#endif ++ ++static ++size_t parent(size_t i) ++{ ++ return (i -1) >> 1; ++} ++ ++static ++size_t left(size_t i) ++{ ++ return (i << 1) + 1; ++} ++ ++static ++size_t right(size_t i) ++{ ++ return (i << 1) + 2; ++} ++ ++/* ++ * Copy of heap->ptrs pointer is invalid after heap_grow. ++ */ ++static ++int heap_grow(struct lttng_ptr_heap *heap, size_t new_len) ++{ ++ void **new_ptrs; ++ ++ if (heap->alloc_len >= new_len) ++ return 0; ++ ++ heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1); ++ new_ptrs = kmalloc(heap->alloc_len * sizeof(void *), heap->gfpmask); ++ if (!new_ptrs) ++ return -ENOMEM; ++ if (heap->ptrs) ++ memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *)); ++ kfree(heap->ptrs); ++ heap->ptrs = new_ptrs; ++ return 0; ++} ++ ++static ++int heap_set_len(struct lttng_ptr_heap *heap, size_t new_len) ++{ ++ int ret; ++ ++ ret = heap_grow(heap, new_len); ++ if (ret) ++ return ret; ++ heap->len = new_len; ++ return 0; ++} ++ ++int lttng_heap_init(struct lttng_ptr_heap *heap, size_t alloc_len, ++ gfp_t gfpmask, int gt(void *a, void *b)) ++{ ++ heap->ptrs = NULL; ++ heap->len = 0; ++ heap->alloc_len = 0; ++ heap->gt = gt; ++ heap->gfpmask = gfpmask; ++ /* ++ * Minimum size allocated is 1 entry to ensure memory allocation ++ * never fails within heap_replace_max. ++ */ ++ return heap_grow(heap, max_t(size_t, 1, alloc_len)); ++} ++ ++void lttng_heap_free(struct lttng_ptr_heap *heap) ++{ ++ kfree(heap->ptrs); ++} ++ ++static void heapify(struct lttng_ptr_heap *heap, size_t i) ++{ ++ void **ptrs = heap->ptrs; ++ size_t l, r, largest; ++ ++ for (;;) { ++ void *tmp; ++ ++ l = left(i); ++ r = right(i); ++ if (l < heap->len && heap->gt(ptrs[l], ptrs[i])) ++ largest = l; ++ else ++ largest = i; ++ if (r < heap->len && heap->gt(ptrs[r], ptrs[largest])) ++ largest = r; ++ if (largest == i) ++ break; ++ tmp = ptrs[i]; ++ ptrs[i] = ptrs[largest]; ++ ptrs[largest] = tmp; ++ i = largest; ++ } ++ lttng_check_heap(heap); ++} ++ ++void *lttng_heap_replace_max(struct lttng_ptr_heap *heap, void *p) ++{ ++ void *res; ++ ++ if (!heap->len) { ++ (void) heap_set_len(heap, 1); ++ heap->ptrs[0] = p; ++ lttng_check_heap(heap); ++ return NULL; ++ } ++ ++ /* Replace the current max and heapify */ ++ res = heap->ptrs[0]; ++ heap->ptrs[0] = p; ++ heapify(heap, 0); ++ return res; ++} ++ ++int lttng_heap_insert(struct lttng_ptr_heap *heap, void *p) ++{ ++ void **ptrs; ++ size_t pos; ++ int ret; ++ ++ ret = heap_set_len(heap, heap->len + 1); ++ if (ret) ++ return ret; ++ ptrs = heap->ptrs; ++ pos = heap->len - 1; ++ while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) { ++ /* Move parent down until we find the right spot */ ++ ptrs[pos] = ptrs[parent(pos)]; ++ pos = parent(pos); ++ } ++ ptrs[pos] = p; ++ lttng_check_heap(heap); ++ return 0; ++} ++ ++void *lttng_heap_remove(struct lttng_ptr_heap *heap) ++{ ++ switch (heap->len) { ++ case 0: ++ return NULL; ++ case 1: ++ (void) heap_set_len(heap, 0); ++ return heap->ptrs[0]; ++ } ++ /* Shrink, replace the current max by previous last entry and heapify */ ++ heap_set_len(heap, heap->len - 1); ++ /* len changed. previous last entry is at heap->len */ ++ return lttng_heap_replace_max(heap, heap->ptrs[heap->len]); ++} ++ ++void *lttng_heap_cherrypick(struct lttng_ptr_heap *heap, void *p) ++{ ++ size_t pos, len = heap->len; ++ ++ for (pos = 0; pos < len; pos++) ++ if (heap->ptrs[pos] == p) ++ goto found; ++ return NULL; ++found: ++ if (heap->len == 1) { ++ (void) heap_set_len(heap, 0); ++ lttng_check_heap(heap); ++ return heap->ptrs[0]; ++ } ++ /* Replace p with previous last entry and heapify. */ ++ heap_set_len(heap, heap->len - 1); ++ /* len changed. previous last entry is at heap->len */ ++ heap->ptrs[pos] = heap->ptrs[heap->len]; ++ heapify(heap, pos); ++ return p; ++} +diff --git a/drivers/staging/lttng/lib/prio_heap/lttng_prio_heap.h b/drivers/staging/lttng/lib/prio_heap/lttng_prio_heap.h +new file mode 100644 +index 0000000..ea8dbb8 +--- /dev/null ++++ b/drivers/staging/lttng/lib/prio_heap/lttng_prio_heap.h +@@ -0,0 +1,117 @@ ++#ifndef _LTTNG_PRIO_HEAP_H ++#define _LTTNG_PRIO_HEAP_H ++ ++/* ++ * lttng_prio_heap.h ++ * ++ * Priority heap containing pointers. Based on CLRS, chapter 6. ++ * ++ * Copyright 2011 - Mathieu Desnoyers ++ * ++ * Permission is hereby granted, free of charge, to any person obtaining a copy ++ * of this software and associated documentation files (the "Software"), to deal ++ * in the Software without restriction, including without limitation the rights ++ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell ++ * copies of the Software, and to permit persons to whom the Software is ++ * furnished to do so, subject to the following conditions: ++ * ++ * The above copyright notice and this permission notice shall be included in ++ * all copies or substantial portions of the Software. ++ */ ++ ++#include ++ ++struct lttng_ptr_heap { ++ size_t len, alloc_len; ++ void **ptrs; ++ int (*gt)(void *a, void *b); ++ gfp_t gfpmask; ++}; ++ ++#ifdef DEBUG_HEAP ++void lttng_check_heap(const struct lttng_ptr_heap *heap); ++#else ++static inline ++void lttng_check_heap(const struct lttng_ptr_heap *heap) ++{ ++} ++#endif ++ ++/** ++ * lttng_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 *lttng_heap_maximum(const struct lttng_ptr_heap *heap) ++{ ++ lttng_check_heap(heap); ++ return heap->len ? heap->ptrs[0] : NULL; ++} ++ ++/** ++ * lttng_heap_init - initialize the heap ++ * @heap: the heap to initialize ++ * @alloc_len: number of elements initially allocated ++ * @gfp: allocation flags ++ * @gt: function to compare the elements ++ * ++ * Returns -ENOMEM if out of memory. ++ */ ++extern int lttng_heap_init(struct lttng_ptr_heap *heap, ++ size_t alloc_len, gfp_t gfpmask, ++ int gt(void *a, void *b)); ++ ++/** ++ * lttng_heap_free - free the heap ++ * @heap: the heap to free ++ */ ++extern void lttng_heap_free(struct lttng_ptr_heap *heap); ++ ++/** ++ * lttng_heap_insert - insert an element into the heap ++ * @heap: the heap to be operated on ++ * @p: the element to add ++ * ++ * Insert an element into the heap. ++ * ++ * Returns -ENOMEM if out of memory. ++ */ ++extern int lttng_heap_insert(struct lttng_ptr_heap *heap, void *p); ++ ++/** ++ * lttng_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 *lttng_heap_remove(struct lttng_ptr_heap *heap); ++ ++/** ++ * lttng_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 *lttng_heap_cherrypick(struct lttng_ptr_heap *heap, void *p); ++ ++/** ++ * lttng_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. It never allocates memory. ++ */ ++extern void *lttng_heap_replace_max(struct lttng_ptr_heap *heap, void *p); ++ ++#endif /* _LTTNG_PRIO_HEAP_H */ diff --git a/series b/series index 25b7174..31759f0 100644 --- a/series +++ b/series @@ -57,6 +57,7 @@ patches.android/staging-android-add-the-code-back-to-the-build.patch # Patches came from short-lived experiment when they were added to the staging # tree for a week or so. # +patches.lttng/0000-lttng-lib-lttng-priority-heap.patch patches.lttng/0001-lttng-lib-ring-buffer.patch patches.lttng/0002-lttng-lib-portable-bitfield-read-write-header.patch patches.lttng/0003-lttng-BUILD_RUNTIME_BUG_ON.patch -- 2.7.4