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