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 */
41const int *
42dist_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 */
80const int *
81dist_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 */
160void
161dist_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 */
192void
193dist_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