[oprof-cvs] CVS: oprofile/libop op_alloc_counter.h,1.3,1.4 op_alloc_counter.c,1.4,1.5

[Philippe E. <ph...@us...>]

Update of /cvsroot/oprofile/oprofile/libop
In directory sc8-pr-cvs1:/tmp/cvs-serv20426/libop

Modified Files:
	op_alloc_counter.h op_alloc_counter.c 
Log Message:
libop/op_alloc_counter.[c|h]: change allocator by a backtracking algorithm walking only through possible solution. No change in public interface


Index: op_alloc_counter.h
===================================================================
RCS file: /cvsroot/oprofile/oprofile/libop/op_alloc_counter.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -p -d -r1.3 -r1.4
--- op_alloc_counter.h	22 Sep 2003 14:10:14 -0000	1.3
+++ op_alloc_counter.h	28 Sep 2003 17:28:30 -0000	1.4
@@ -22,7 +22,18 @@
 extern "C" {
 #endif
 
-/// FIXME: doc
+/**
+ * @param pev  array of selected event we want to bind to counter
+ * @param nr_events  size of pev array
+ * @param cpu_type  cpu type: FIXME passing this parameter is a non sense
+ *  load_events(); automatically determine the cpu type so it look like only
+ *  a way to get a mismatch between detected cpu type and this parameter. btw
+ *  op_events.c API is weird.
+ *
+ * Try to calculate a binding between passed event in pev and counter number.
+ * The binding is returned in a size_t * where returned ptr[i] is the counter
+ * number bound to pev[i]
+ */
 size_t * map_event_to_counter(struct op_event const * pev[], int nr_events,
                               op_cpu cpu_type);
 

Index: op_alloc_counter.c
===================================================================
RCS file: /cvsroot/oprofile/oprofile/libop/op_alloc_counter.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -p -d -r1.4 -r1.5
--- op_alloc_counter.c	8 Aug 2003 01:42:10 -0000	1.4
+++ op_alloc_counter.c	28 Sep 2003 17:28:31 -0000	1.5
@@ -17,100 +17,146 @@
 #include "op_libiberty.h"
 
 
-static void iter_swap(size_t * a, size_t * b)
-{
-	size_t tmp = *a;
-	*a = *b;
-	*b = tmp;
-}
+typedef struct counter_arc_head {
+	/** the head of allowed counter for this event */
+	struct list_head next;
+} counter_arc_head;
 
 
-static void reverse(size_t * first, size_t * last)
-{
-	while (1) {
-		if (first == last || first == --last)
-			return;
-		else
-			iter_swap(first++, last);
-	}
-}
+typedef struct counter_arc {
+	/** counter nr */
+	int counter;
+	/** the next counter allowed for this event */
+	struct list_head next;
+} counter_arc;
 
 
-static int next_permutation(size_t * first, size_t * last)
+/**
+ * @param pev  an array of event
+ * @param nr_events  number of entry in pev
+ *
+ * build an array of counter list allowed for each events
+ *  counter_arc_head[i] is the list of allowed counter for pev[i] events
+ * The returned pointer is an array of nr_events entry
+ */
+static counter_arc_head *
+build_counter_arc(struct op_event const * pev[], int nr_events)
 {
-	size_t * i;
-	if (first == last)
-		return 0;
-	i = first;
-	++i;
-	if (i == last)
-		return 0;
-	i = last;
-	--i;
+	counter_arc_head * ctr_arc;
+	int i;
 
-	for(;;) {
-		size_t * ii = i;
-		--i;
-		if (*i < *ii) {
-			size_t * j = last;
-			while (!(*i < *--j)) {
+	ctr_arc = xmalloc(nr_events * sizeof(*ctr_arc));
+
+	for (i = 0; i < nr_events; ++i) {
+		int j;
+		u32 mask = pev[i]->counter_mask;
+
+		list_init(&ctr_arc[i].next);
+		for (j = 0; mask; ++j) {
+			if (mask & (1 << j)) {
+				counter_arc * arc = 
+					xmalloc(sizeof(counter_arc));
+				arc->counter = j;
+				list_add(&arc->next, &ctr_arc[i].next);
+				mask &= ~(1 << j);
 			}
-			iter_swap(i, j);
-			reverse(ii, last);
-			return 1;
 		}
-		if (i == first) {
-			reverse(first, last);
-			return 0;
+	}
+
+	return ctr_arc;
+}
+
+
+/**
+ * @param ctr_arc  the array to deallocate
+ * @param nr_events  number of entry in array
+ *
+ *  deallocate all previously allocated resource by build_counter_arc()
+ */
+static void delete_counter_arc(counter_arc_head * ctr_arc, int nr_events)
+{
+	int i;
+	for (i = 0; i < nr_events; ++i) {
+		struct list_head * pos, * pos2;
+		list_for_each_safe(pos, pos2, &ctr_arc[i].next) {
+			counter_arc * arc = list_entry(pos, counter_arc, next);
+			list_del(&arc->next);
+			free(arc);
 		}
 	}
+	free(ctr_arc);
 }
 
-static int allocate_counter(size_t const * counter_map,
-                            struct op_event const * pev[], int nr_events)
+
+/**
+ * @param ctr_arc  tree description, ctr_arc[i] is the i-th level of tree.
+ * @param max_depth  number of entry in array ctr_arc == depth of tree
+ * @param depth  current level we are exploring
+ * @param allocated_mask  current counter already allocated mask
+ * @param counter_map  array of counter number mapping, returned results go
+ *   here
+ *
+ * return non zero on succees, in this case counter_map is set to the counter
+ * mapping number.
+ *
+ * Solution is searched through a simple backtracking exploring recursively all
+ * possible solution until one is found, prunning is done in O(1) by tracking
+ * a bitmask of already allocated counter. Walking through node is done in
+ * preorder left to right.
+ *
+ * Possible improvment if neccessary: partition counters in class of counter,
+ * two counter belong to the same class if they allow exactly the same set of
+ * event. Now using a variant of the backtrack algo can works on class of
+ * counter rather on counter (this is not an improvment if each counter goes
+ * in it's own class)
+ */
+static int
+allocate_counter(counter_arc_head const * ctr_arc, int max_depth, int depth,
+		 u32 allocated_mask, size_t * counter_map)
 {
-	int c = 0;
+	struct list_head * pos;
 
-	for (; c < nr_events; ++c) {
-		/* assert(c < nr_counters) */
-		int mask = 1 << counter_map[c];
-		if (!(pev[c]->counter_mask & mask))
-			return EXIT_FAILURE;
+	if (depth == max_depth)
+		return 1;
+
+	list_for_each(pos, &ctr_arc[depth].next) {
+		counter_arc const * arc = list_entry(pos, counter_arc, next);
+
+		if (allocated_mask & (1 << arc->counter))
+			return 0;
+
+		counter_map[depth] = arc->counter;
+
+		if (allocate_counter(ctr_arc, max_depth, depth + 1,
+		                     allocated_mask | (1 << arc->counter),
+		                     counter_map))
+			return 1;
 	}
 
-	return EXIT_SUCCESS;
+	return 0;
 }
 
 
 size_t * map_event_to_counter(struct op_event const * pev[], int nr_events,
                               op_cpu cpu_type)
 {
-	int nr_counters;
+	counter_arc_head * ctr_arc;
 	size_t * counter_map;
-	int success;
-	int i;
+	int nr_counters;
 
 	nr_counters = op_get_nr_counters(cpu_type);
 	if (nr_counters < nr_events)
 		return 0;
 
-	counter_map = xmalloc(nr_counters * sizeof(size_t));
-
-	for (i = 0; i < nr_counters; ++i)
-		counter_map[i] = i;
-
-	success = EXIT_FAILURE;
-	do {
-		success = allocate_counter(counter_map, pev, nr_events);
+	ctr_arc = build_counter_arc(pev, nr_events);
 
-		if (success == EXIT_SUCCESS)
-			break;
-	} while (next_permutation(counter_map, counter_map + nr_counters));
+	counter_map = xmalloc(nr_counters * sizeof(size_t));
 
-	if (success == EXIT_FAILURE) {
+	if (!allocate_counter(ctr_arc, nr_events, 0, 0, counter_map)) {
 		free(counter_map);
 		counter_map = 0;
 	}
 
+	delete_counter_arc(ctr_arc, nr_events);
 	return counter_map;
 }