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