2007-09-12 Martin Hunt <hunt@redhat.com>

	* map-stat.c (_stp_map_new_hstat_log): Set buckets to
	HIST_LOG_BUCKETS.
	(_stp_pmap_new_hstat_log): Ditto.
	(_stp_map_new_hstat_linear): Call _stp_stat_calc_buckets().
	(_stp_pmap_new_hstat_linear): Ditto.

	* stat.h (STP_MAX_BUCKETS): Define..
	(HIST_LOG_BUCKETS): Define.

	* stat.c (_stp_stat_init): Call _stp_stat_calc_buckets().

	* stat-common.c (_stp_stat_calc_buckets): New function. Common
	bucket calculation and error reporting code.
	(_stp_bucket_to_val): New function.
	(_stp_val_to_bucket): Renamed and now handles negative numbers.
	(_stp_stat_print_histogram): Handle negative values in log histograms.
	(__stp_stat_add): Cleanup..

	* map-gen.c (_stp_map_new): Remove buckets param for HIST_LOG.
	* pmap-gen.c (_stp_pmap_new): Ditto.

8 files changed, 193 insertions, 144 deletions

diff --git a/runtime/ChangeLog b/runtime/ChangeLog
index ac7cce35..eb5a15c7 100644
--- a/runtime/ChangeLog
+++ b/runtime/ChangeLog
@@ -1,3 +1,26 @@
+2007-09-12  Martin Hunt  <hunt@redhat.com>
+
+	* map-stat.c (_stp_map_new_hstat_log): Set buckets to 
+	HIST_LOG_BUCKETS.
+	(_stp_pmap_new_hstat_log): Ditto.
+	(_stp_map_new_hstat_linear): Call _stp_stat_calc_buckets().
+	(_stp_pmap_new_hstat_linear): Ditto.
+
+	* stat.h (STP_MAX_BUCKETS): Define..
+	(HIST_LOG_BUCKETS): Define.
+
+	* stat.c (_stp_stat_init): Call _stp_stat_calc_buckets().
+
+	* stat-common.c (_stp_stat_calc_buckets): New function. Common
+	bucket calculation and error reporting code.
+	(_stp_bucket_to_val): New function.
+	(_stp_val_to_bucket): Renamed and now handles negative numbers.
+	(_stp_stat_print_histogram): Handle negative values in log histograms.
+	(__stp_stat_add): Cleanup..
+
+	* map-gen.c (_stp_map_new): Remove buckets param for HIST_LOG.
+	* pmap-gen.c (_stp_pmap_new): Ditto.
+	
 2007-09-10  Martin Hunt  <hunt@redhat.com>
 
 	* procfs.c: New file. Common runtime procfs functions.
diff --git a/runtime/map-gen.c b/runtime/map-gen.c
index e662e71e..a17f7e34 100644
--- a/runtime/map-gen.c
+++ b/runtime/map-gen.c
@@ -346,25 +346,20 @@ MAP KEYSYM(_stp_map_new) (unsigned max_entries)
 }
 #else
 /* _stp_map_new_key1_key2...val (num, HIST_LINEAR, start, end, interval) */
-/* _stp_map_new_key1_key2...val (num, HIST_LOG, buckets) */ 
+/* _stp_map_new_key1_key2...val (num, HIST_LOG) */ 
 
 MAP KEYSYM(_stp_map_new) (unsigned max_entries, int htype, ...)
 {
-	int buckets=0, start=0, stop=0, interval=0;
+	int start=0, stop=0, interval=0;
 	MAP m;
-	va_list ap;
 
-	if (htype != HIST_NONE) {
+	if (htype == HIST_LINEAR) {
+		va_list ap;
 		va_start (ap, htype);		
-		if (htype == HIST_LOG) {
-			buckets = va_arg(ap, int);
-			// dbug ("buckets=%d\n", buckets);
-		} else {
-			start = va_arg(ap, int);
-			stop = va_arg(ap, int);
-			interval = va_arg(ap, int);
-			// dbug ("start=%d stop=%d interval=%d\n", start, stop, interval);
-		}
+		start = va_arg(ap, int);
+		stop = va_arg(ap, int);
+		interval = va_arg(ap, int);
+		// dbug ("start=%d stop=%d interval=%d\n", start, stop, interval);
 		va_end (ap);
 	}
 
@@ -373,8 +368,7 @@ MAP KEYSYM(_stp_map_new) (unsigned max_entries, int htype, ...)
 		m = _stp_map_new (max_entries, STAT, sizeof(struct KEYSYM(map_node)), 0);
 		break;
 	case HIST_LOG:
-		m = _stp_map_new_hstat_log (max_entries, sizeof(struct KEYSYM(map_node)), 
-					    buckets);
+		m = _stp_map_new_hstat_log (max_entries, sizeof(struct KEYSYM(map_node)));
 		break;
 	case HIST_LINEAR:
 		m = _stp_map_new_hstat_linear (max_entries, sizeof(struct KEYSYM(map_node)),
diff --git a/runtime/map-stat.c b/runtime/map-stat.c
index 6634a2b7..dc3fd6ac 100644
--- a/runtime/map-stat.c
+++ b/runtime/map-stat.c
@@ -14,25 +14,19 @@
 
 #include "stat-common.c"
 
-
 static void _stp_map_print_histogram (MAP map, stat *sd)
 {
 	_stp_stat_print_histogram (&map->hist, sd);
 }
 
-static MAP _stp_map_new_hstat_log (unsigned max_entries, int key_size, int buckets)
+static MAP _stp_map_new_hstat_log (unsigned max_entries, int key_size)
 {
 	/* add size for buckets */
-	int size = buckets * sizeof(int64_t) + sizeof(stat);
+	int size = HIST_LOG_BUCKETS * sizeof(int64_t) + sizeof(stat);
 	MAP m = _stp_map_new (max_entries, STAT, key_size, size);
 	if (m) {
 		m->hist.type = HIST_LOG;
-		m->hist.buckets = buckets;
-		if (buckets < 1 || buckets > 64) {
-			_stp_warn("histogram: Bad number of buckets.  Must be between 1 and 64\n");
-			m->hist.type = HIST_NONE;
-			return m;
-		}
+		m->hist.buckets = HIST_LOG_BUCKETS;
 	}
 	return m;
 }
@@ -41,12 +35,13 @@ static MAP _stp_map_new_hstat_linear (unsigned max_entries, int ksize, int start
 {
 	MAP m;
 	int size;
-	int buckets = (stop - start) / interval;
-	if ((stop - start) % interval) buckets++;
-
+	int buckets = _stp_stat_calc_buckets(stop, start, interval);
+	if (!buckets)
+		return NULL;
+	
         /* add size for buckets */
 	size = buckets * sizeof(int64_t) + sizeof(stat);
-
+	
 	m = _stp_map_new (max_entries, STAT, ksize, size);
 	if (m) {
 		m->hist.type = HIST_LINEAR;
@@ -54,12 +49,6 @@ static MAP _stp_map_new_hstat_linear (unsigned max_entries, int ksize, int start
 		m->hist.stop = stop;
 		m->hist.interval = interval;
 		m->hist.buckets = buckets;
-		if (m->hist.buckets <= 0) {
-			_stp_warn("histogram: bad stop, start and/or interval\n");
-			m->hist.type = HIST_NONE;
-			return m;
-		}
-		
 	}
 	return m;
 }
@@ -68,8 +57,9 @@ static PMAP _stp_pmap_new_hstat_linear (unsigned max_entries, int ksize, int sta
 {
 	PMAP pmap;
 	int size;
-	int buckets = (stop - start) / interval;
-	if ((stop - start) % interval) buckets++;
+	int buckets = _stp_stat_calc_buckets(stop, start, interval);
+	if (!buckets)
+		return NULL;
 
         /* add size for buckets */
 	size = buckets * sizeof(int64_t) + sizeof(stat);
@@ -97,10 +87,10 @@ static PMAP _stp_pmap_new_hstat_linear (unsigned max_entries, int ksize, int sta
 	return pmap;
 }
 
-static PMAP _stp_pmap_new_hstat_log (unsigned max_entries, int key_size, int buckets)
+static PMAP _stp_pmap_new_hstat_log (unsigned max_entries, int key_size)
 {
 	/* add size for buckets */
-	int size = buckets * sizeof(int64_t) + sizeof(stat);
+	int size = HIST_LOG_BUCKETS * sizeof(int64_t) + sizeof(stat);
 	PMAP pmap = _stp_pmap_new (max_entries, STAT, key_size, size);
 	if (pmap) {
 		int i;
@@ -108,12 +98,12 @@ static PMAP _stp_pmap_new_hstat_log (unsigned max_entries, int key_size, int buc
 		for_each_cpu(i) {
 			m = (MAP)per_cpu_ptr (pmap->map, i);
 			m->hist.type = HIST_LOG;
-			m->hist.buckets = buckets;
+			m->hist.buckets = HIST_LOG_BUCKETS;
 		}
 		/* now set agg map  params */
 		m = &pmap->agg;
 		m->hist.type = HIST_LOG;
-		m->hist.buckets = buckets;
+		m->hist.buckets = HIST_LOG_BUCKETS;
 	}
 	return pmap;
 }
diff --git a/runtime/map.h b/runtime/map.h
index f89dc521..6cd6e119 100644
--- a/runtime/map.h
+++ b/runtime/map.h
@@ -187,7 +187,7 @@ unsigned int str_hash(const char *key1);
 static MAP _stp_map_new(unsigned max_entries, int type, int key_size, int data_size);
 static PMAP _stp_pmap_new(unsigned max_entries, int type, int key_size, int data_size);
 static int msb64(int64_t x);
-static MAP _stp_map_new_hstat_log(unsigned max_entries, int key_size, int buckets);
+static MAP _stp_map_new_hstat_log(unsigned max_entries, int key_size);
 static MAP _stp_map_new_hstat_linear(unsigned max_entries, int ksize, int start, int stop, int interval);
 static void _stp_map_print_histogram(MAP map, stat *s);
 struct map_node * _stp_map_start(MAP map);
@@ -202,7 +202,7 @@ static int _new_map_set_str (MAP map, struct map_node *n, char *val, int add);
 static void _new_map_clear_node (struct map_node *);
 static void _new_map_del_node (MAP map, struct map_node *n);
 static PMAP _stp_pmap_new_hstat_linear (unsigned max_entries, int ksize, int start, int stop, int interval);
-static PMAP _stp_pmap_new_hstat_log (unsigned max_entries, int key_size, int buckets);
+static PMAP _stp_pmap_new_hstat_log (unsigned max_entries, int key_size);
 static void _stp_add_agg(struct map_node *aptr, struct map_node *ptr);
 static struct map_node *_stp_new_agg(MAP agg, struct hlist_head *ahead, struct map_node *ptr);
 static void __stp_map_del(MAP map);
diff --git a/runtime/pmap-gen.c b/runtime/pmap-gen.c
index f84b9db7..ca8d45c5 100644
--- a/runtime/pmap-gen.c
+++ b/runtime/pmap-gen.c
@@ -424,25 +424,20 @@ PMAP KEYSYM(_stp_pmap_new) (unsigned max_entries)
 }
 #else
 /* _stp_pmap_new_key1_key2...val (num, HIST_LINEAR, start, end, interval) */
-/* _stp_pmap_new_key1_key2...val (num, HIST_LOG, buckets) */ 
+/* _stp_pmap_new_key1_key2...val (num, HIST_LOG) */ 
 
 PMAP KEYSYM(_stp_pmap_new) (unsigned max_entries, int htype, ...)
 {
-	int buckets=0, start=0, stop=0, interval=0;
+	int start=0, stop=0, interval=0;
 	PMAP pmap;
-	va_list ap;
 
-	if (htype != HIST_NONE) {
+	if (htype == HIST_LINEAR) {
+		va_list ap;
 		va_start (ap, htype);		
-		if (htype == HIST_LOG) {
-			buckets = va_arg(ap, int);
-			// dbug ("buckets=%d\n", buckets);
-		} else {
-			start = va_arg(ap, int);
-			stop = va_arg(ap, int);
-			interval = va_arg(ap, int);
-			// dbug ("start=%d stop=%d interval=%d\n", start, stop, interval);
-		}
+		start = va_arg(ap, int);
+		stop = va_arg(ap, int);
+		interval = va_arg(ap, int);
+		// dbug ("start=%d stop=%d interval=%d\n", start, stop, interval);
 		va_end (ap);
 	}
 
@@ -451,8 +446,7 @@ PMAP KEYSYM(_stp_pmap_new) (unsigned max_entries, int htype, ...)
 		pmap = _stp_pmap_new (max_entries, STAT, sizeof(struct KEYSYM(pmap_node)), 0);
 		break;
 	case HIST_LOG:
-		pmap = _stp_pmap_new_hstat_log (max_entries, sizeof(struct KEYSYM(pmap_node)), 
-					    buckets);
+		pmap = _stp_pmap_new_hstat_log (max_entries, sizeof(struct KEYSYM(pmap_node)));
 		break;
 	case HIST_LINEAR:
 		pmap = _stp_pmap_new_hstat_linear (max_entries, sizeof(struct KEYSYM(pmap_node)),
diff --git a/runtime/stat-common.c b/runtime/stat-common.c
index 9ca045c9..80ced30d 100644
--- a/runtime/stat-common.c
+++ b/runtime/stat-common.c
@@ -12,6 +12,28 @@
 #define _STAT_COMMON_C_
 #include "stat.h"
 
+static int _stp_stat_calc_buckets(int stop, int start, int interval)
+{
+	int buckets;
+
+	if (interval == 0) {
+		_stp_warn("histogram: interval cannot be zero.\n");
+		return 0;
+	}
+	buckets = (stop - start) / interval;
+	if ((stop - start) % interval)
+		buckets++;
+
+	if (buckets > STP_MAX_BUCKETS || buckets <= 0) {
+		_stp_warn("histogram: Number of buckets must be between 1 and %d\n"
+			  "Number_of_buckets = (stop - start) / interval.\n"
+			  "Please adjust your start, stop, and interval values.\n",
+			  STP_MAX_BUCKETS);
+		return 0;
+	}
+	return buckets;
+}
+
 static int needed_space(int64_t v)
 {
 	int space = 0;
@@ -39,57 +61,72 @@ static void reprint (int num, char *s)
 	}
 }
 
-/* implements a log base 2 function, or Most Significant Bit */
-/* with bits from 1 (lsb) to 64 (msb) */
-/* msb64(0) = 0 */
-/* msb64(1) = 1 */
-/* msb64(8) = 4 */
-/* msb64(512) = 10 */
+/* Given a bucket number for a log histogram, return the value. */
+static int64_t _stp_bucket_to_val(int num)
+{
+	if (num == HIST_LOG_BUCKET0)
+		return 0;
+	if (num < HIST_LOG_BUCKET0) {
+		int64_t val = 0x8000000000000000LL;
+		return  val >> num;
+	} else
+		return 1LL << (num - HIST_LOG_BUCKET0 - 1);
+}
 
-static int msb64(int64_t val)
+/* Implements a log base 2 function. Returns a bucket 
+ * number from 0 to HIST_LOG_BUCKETS.
+ */
+static int _stp_val_to_bucket(int64_t val)
 {
-  int res = 64;
-
-  if (val == 0)
-    return 0;
-
-  /* shortcut. most values will be 16-bit */
-  if (val & 0xffffffffffff0000ull) {
-    if (!(val & 0xffffffff00000000ull)) {
-      val <<= 32;
-      res -= 32;
-    }
-
-    if (!(val & 0xffff000000000000ull)) {
-      val <<= 16;
-      res -= 16;
-    }
-  } else {
-      val <<= 48;
-      res -= 48;
-  }
-
-  if (!(val & 0xff00000000000000ull)) {
-    val <<= 8;
-    res -= 8;
-  }
-
-  if (!(val & 0xf000000000000000ull)) {
-    val <<= 4;
-    res -= 4;
-  }
-
-  if (!(val & 0xc000000000000000ull)) {
-    val <<= 2;
-    res -= 2;
-  }
-
-  if (!(val & 0x8000000000000000ull)) {
-    val <<= 1;
-    res -= 1;
-  }
-
-  return res;
+	int neg = 0, res = HIST_LOG_BUCKETS;
+	
+	if (val == 0)
+		return HIST_LOG_BUCKET0;
+
+	if (val < 0) {
+		val = -val;
+		neg = 1;
+	}
+	
+	/* shortcut. most values will be 16-bit */
+	if (unlikely(val & 0xffffffffffff0000ull)) {
+		if (!(val & 0xffffffff00000000ull)) {
+			val <<= 32;
+			res -= 32;
+		}
+		
+		if (!(val & 0xffff000000000000ull)) {
+			val <<= 16;
+			res -= 16;
+		}
+	} else {
+		val <<= 48;
+		res -= 48;
+	}
+	
+	if (!(val & 0xff00000000000000ull)) {
+		val <<= 8;
+		res -= 8;
+	}
+	
+	if (!(val & 0xf000000000000000ull)) {
+		val <<= 4;
+		res -= 4;
+	}
+	
+	if (!(val & 0xc000000000000000ull)) {
+		val <<= 2;
+		res -= 2;
+	}
+
+	if (!(val & 0x8000000000000000ull)) {
+		val <<= 1;
+		res -= 1;
+	}
+	if (neg)
+		res = HIST_LOG_BUCKETS - res;
+
+	return res;
 }
 
 #ifndef HIST_WIDTH
@@ -119,8 +156,14 @@ static void _stp_stat_print_histogram (Hist st, stat *sd)
 	/* Touch up the bucket margin to show up to two zero-slots on
 	   either side of the data range, seems aesthetically pleasant. */
 	for (i = 0; i < 2; i++) {
-		if (low_bucket > 0)
-			low_bucket--;
+		if (st->type == HIST_LOG) {
+			/* For log histograms, don't go negative */
+			/* unless there are negative values. */
+			if (low_bucket != HIST_LOG_BUCKET0 && low_bucket > 0)
+				low_bucket--;
+		} else
+			if (low_bucket > 0)
+				low_bucket--;
 		
 		if (high_bucket < (st->buckets-1))
 			high_bucket++;
@@ -138,8 +181,12 @@ static void _stp_stat_print_histogram (Hist st, stat *sd)
 	cnt_space = needed_space (max);
 	if (st->type == HIST_LINEAR)
 		val_space = needed_space (st->start +  st->interval * high_bucket);
-	else
-		val_space = needed_space (((int64_t)1) << high_bucket);
+	else {
+		int tmp = needed_space(_stp_bucket_to_val(high_bucket));
+		val_space = needed_space(_stp_bucket_to_val(low_bucket));
+		if (tmp > val_space)
+			val_space = tmp;
+	}
 	//dbug ("max=%lld scale=%d val_space=%d\n", max, scale, val_space);
 
 	/* print header */
@@ -153,30 +200,22 @@ static void _stp_stat_print_histogram (Hist st, stat *sd)
 	_stp_print("value |");
 	reprint (HIST_WIDTH, "-");
 	_stp_print(" count\n");
-	if (st->type == HIST_LINEAR)
-		val = st->start;
-	else
-		val = 0;
-	for (i = 0; i < st->buckets; i++) {
-		if (i >= low_bucket && i <= high_bucket) {
-			reprint (val_space - needed_space(val), " ");
-			_stp_printf("%lld", val);
-			_stp_print(" |");
-			
-			/* v = s->histogram[i] / scale; */
-			v = sd->histogram[i];
-			do_div (v, scale);
-		
-			reprint (v, "@");
-			reprint (HIST_WIDTH - v + 1 + cnt_space - needed_space(sd->histogram[i]), " ");
-			_stp_printf ("%lld\n", sd->histogram[i]);
-		}
-		if (st->type == HIST_LINEAR) 
-			val += st->interval;
-		else if (val == 0)
-			val = 1;
+	for (i = low_bucket;  i <= high_bucket; i++) {
+		if (st->type == HIST_LINEAR)
+			val = st->start + i * st->interval;
 		else
-			val *= 2;
+			val = _stp_bucket_to_val(i);
+		reprint (val_space - needed_space(val), " ");
+		_stp_printf("%lld", val);
+		_stp_print(" |");
+		
+		/* v = s->histogram[i] / scale; */
+		v = sd->histogram[i];
+		do_div (v, scale);
+		
+		reprint (v, "@");
+		reprint (HIST_WIDTH - v + 1 + cnt_space - needed_space(sd->histogram[i]), " ");
+		_stp_printf ("%lld\n", sd->histogram[i]);
 	}
 	_stp_print_char('\n');
 	_stp_print_flush();
@@ -231,18 +270,24 @@ static void __stp_stat_add (Hist st, stat *sd, int64_t val)
 	}
 	switch (st->type) {
 	case HIST_LOG:
-		n = msb64 (val);
+		n = _stp_val_to_bucket (val);
 		if (n >= st->buckets)
 			n = st->buckets - 1;
 		sd->histogram[n]++;
 		break;
 	case HIST_LINEAR:
 		val -= st->start;
+
+		/* underflow */
 		if (val < 0)
 			val = 0;
+
 		do_div (val, st->interval);
+
+		/* overflow */
 		if (val >= st->buckets)
 			val = st->buckets - 1;
+
 		sd->histogram[val]++;
 	default:
 		break;
diff --git a/runtime/stat.c b/runtime/stat.c
index f4e205aa..3df1d063 100644
--- a/runtime/stat.c
+++ b/runtime/stat.c
@@ -85,21 +85,15 @@ Stat _stp_stat_init (int type, ...)
 		va_start (ap, type);
 		
 		if (type == HIST_LOG) {
-			buckets = va_arg(ap, int);
+			buckets = HIST_LOG_BUCKETS;
 		} else {
 			start = va_arg(ap, int);
 			stop = va_arg(ap, int);
 			interval = va_arg(ap, int);
-			if (interval == 0) {
-				_stp_warn("histogram: interval cannot be zero.\n");
-				return NULL;
-			}
-			buckets = (stop - start) / interval;
-			if ((stop - start) % interval) buckets++;
-			if (buckets > 128) {
-				_stp_warn("histogram: Interval is too small. Maximum buckets is 128.\n");
+
+			buckets = _stp_stat_calc_buckets(stop, start, interval);
+			if (!buckets)
 				return NULL;
-			}
 		}
 		va_end (ap);
 	}
diff --git a/runtime/stat.h b/runtime/stat.h
index 95872758..4357abb4 100644
--- a/runtime/stat.h
+++ b/runtime/stat.h
@@ -15,6 +15,15 @@
 #define NEED_STAT_LOCKS 0
 #endif
 
+/* maximum buckets for a linear histogram */
+#ifndef STP_MAX_BUCKETS
+#define STP_MAX_BUCKETS 128
+#endif
+
+/* buckets for log histogram. */
+#define HIST_LOG_BUCKETS 128
+#define HIST_LOG_BUCKET0 64
+
 /** histogram type */
 enum histtype { HIST_NONE, HIST_LOG, HIST_LINEAR };