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 *
dist_linear(int buckets,int beg,int end)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 *
dist_geometric(int buckets,int beg,int end,int minbucketsize)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
dist_print_header(const char * label,int width,const char * count)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
dist_print_bucket(const int * distarray,int i,const uint_t * counts,uint64_t total,int width)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