1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 #pragma ident	"%Z%%M%	%I%	%E% SMI"
27 
28 #include <mdb/mdb_modapi.h>
29 #ifndef	_KMDB
30 #include <math.h>
31 #endif
32 
33 #include "dist.h"
34 
35 /*
36  * Divides the given range (inclusive at both endpoints) evenly into the given
37  * number of buckets, adding one bucket at the end that is one past the end of
38  * the range. The returned buckets will be automatically freed when the dcmd
39  * completes or is forcibly aborted.
40  */
41 const int *
42 dist_linear(int buckets, int beg, int end)
43 {
44 	int *out = mdb_alloc((buckets + 1) * sizeof (*out), UM_SLEEP | UM_GC);
45 	int pos;
46 	int dist = end - beg + 1;
47 
48 	for (pos = 0; pos < buckets; pos++)
49 		out[pos] = beg + (pos * dist)/buckets;
50 	out[buckets] = end + 1;
51 
52 	return (out);
53 }
54 
55 /*
56  * We want the bins to be a constant ratio:
57  *
58  *	b_0	  = beg;
59  *	b_idx	  = b_{idx-1} * r;
60  *	b_buckets = end + 1;
61  *
62  * That is:
63  *
64  *	       buckets
65  *	beg * r        = end
66  *
67  * Which reduces to:
68  *
69  *		  buckets ___________________
70  *	      r = -------/ ((end + 1) / beg)
71  *
72  *		  log ((end + 1) / beg)
73  *	  log r = ---------------------
74  *		         buckets
75  *
76  *		   (log ((end + 1) / beg)) / buckets
77  *	      r = e
78  */
79 /* ARGSUSED */
80 const int *
81 dist_geometric(int buckets, int beg, int end, int minbucketsize)
82 {
83 #ifdef	_KMDB
84 	return (dist_linear(buckets, beg, end));
85 #else
86 	int *out = mdb_alloc((buckets + 1) * sizeof (*out), UM_SLEEP | UM_GC);
87 
88 	double r;
89 	double b;
90 	int idx = 0;
91 	int last;
92 	int begzero;
93 
94 	if (minbucketsize == 0)
95 		minbucketsize = 1;
96 
97 	if (buckets == 1) {
98 		out[0] = beg;
99 		out[1] = end + 1;
100 		return (out);
101 	}
102 
103 	begzero = (beg == 0);
104 	if (begzero)
105 		beg = 1;
106 
107 	r = exp(log((double)(end + 1) / beg) / buckets);
108 
109 	/*
110 	 * We've now computed r, using the previously derived formula.  We
111 	 * now need to generate the array of bucket bounds.  There are
112 	 * two major variables:
113 	 *
114 	 *	b	holds b_idx, the current index, as a double.
115 	 *	last	holds the integer which goes into out[idx]
116 	 *
117 	 * Our job is to transform the smooth function b_idx, defined
118 	 * above, into integer-sized buckets, with a specified minimum
119 	 * bucket size.  Since b_idx is an exponentially growing function,
120 	 * any inadequate buckets must be at the beginning.  To deal
121 	 * with this, we make buckets of minimum size until b catches up
122 	 * with last.
123 	 *
124 	 * A final wrinkle is that beg *can* be zero.  We compute r and b
125 	 * as if beg was 1, then start last as 0.  This can lead to a bit
126 	 * of oddness around the 0 bucket, but it's mostly reasonable.
127 	 */
128 
129 	b = last = beg;
130 	if (begzero)
131 		last = 0;
132 
133 	for (idx = 0; idx < buckets; idx++) {
134 		int next;
135 
136 		out[idx] = last;
137 
138 		b *= r;
139 		next = (int)b;
140 
141 		if (next > last + minbucketsize - 1)
142 			last = next;
143 		else
144 			last += minbucketsize;
145 	}
146 	out[buckets] = end + 1;
147 
148 	return (out);
149 #endif
150 }
151 
152 #define	NCHARS	50
153 /*
154  * Print the distribution header with the given bucket label. The header is
155  * printed on a single line, and the label is assumed to fit within the given
156  * width (number of characters). The default label width when unspecified (0)
157  * is eleven characters. Optionally, a label other than "count" may be specified
158  * for the bucket counts.
159  */
160 void
161 dist_print_header(const char *label, int width, const char *count)
162 {
163 	int n;
164 	const char *dist = " Distribution ";
165 	char dashes[NCHARS + 1];
166 
167 	if (width == 0)
168 		width = 11;
169 
170 	if (count == NULL)
171 		count = "count";
172 
173 	n = (NCHARS - strlen(dist)) / 2;
174 	(void) memset(dashes, '-', n);
175 	dashes[n] = '\0';
176 
177 	mdb_printf("%*s  %s%s%s %s\n", width, label, dashes, dist, dashes,
178 	    count);
179 }
180 
181 /*
182  * Print one distribution bucket whose range is from distarray[i] inclusive to
183  * distarray[i + 1] exclusive by totalling counts in that index range.  The
184  * given total is assumed to be the sum of all elements in the counts array.
185  * Each bucket is labeled by its range in the form "first-last" (omit "-last" if
186  * the range is a single value) where first and last are integers, and last is
187  * one less than the first value of the next bucket range. The bucket label is
188  * assumed to fit within the given width (number of characters), which should
189  * match the width value passed to dist_print_header(). The default width when
190  * unspecified (0) is eleven characters.
191  */
192 void
193 dist_print_bucket(const int *distarray, int i, const uint_t *counts,
194     uint64_t total, int width)
195 {
196 	int b;				/* bucket range index */
197 	int bb = distarray[i];		/* bucket begin */
198 	int be = distarray[i + 1] - 1;	/* bucket end */
199 	uint64_t count = 0;		/* bucket value */
200 
201 	int nats;
202 	char ats[NCHARS + 1], spaces[NCHARS + 1];
203 	char range[40];
204 
205 	if (width == 0)
206 		width = 11;
207 
208 	if (total == 0)
209 		total = 1;		/* avoid divide-by-zero */
210 
211 	for (b = bb; b <= be; b++)
212 		count += counts[b];
213 
214 	nats = (NCHARS * count) / total;
215 	(void) memset(ats, '@', nats);
216 	ats[nats] = 0;
217 	(void) memset(spaces, ' ', NCHARS - nats);
218 	spaces[NCHARS - nats] = 0;
219 
220 	if (bb == be)
221 		(void) mdb_snprintf(range, sizeof (range), "%d", bb);
222 	else
223 		(void) mdb_snprintf(range, sizeof (range), "%d-%d", bb, be);
224 	mdb_printf("%*s |%s%s %lld\n", width, range, ats, spaces, count);
225 }
226 #undef NCHARS
227