add forgotten lttng patch

2 files changed, 345 insertions, 0 deletions

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 00000000000000..2c7aa683d2094a
--- /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 <mathieu.desnoyers@efficios.com>
+Date: Mon, 28 Nov 2011 07:42:08 -0500
+Subject: lttng lib: lttng priority heap
+
+Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
+
+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 <mathieu.desnoyers@efficios.com>
++ *
++ * 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 <linux/slab.h>
++#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 <mathieu.desnoyers@efficios.com>
++ *
++ * 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 <linux/gfp.h>
++
++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 25b7174b9d15d3..31759f02adfb8e 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