xref: /illumos-gate/usr/src/lib/libdtrace_jni/java/src/org/opensolaris/os/dtrace/Distribution.java (revision e77b06d21580f630e0a7c437495ab283d3672828)
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 /*
23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  *
26  * ident	"%Z%%M%	%I%	%E% SMI"
27  */
28 package org.opensolaris.os.dtrace;
29 
30 import java.util.*;
31 import java.io.*;
32 import java.beans.*;
33 
34 /**
35  * A frequency distribution aggregated by the DTrace {@code quantize()}
36  * or {@code lquantize()} action.  Each aggregated value falls into a
37  * range known as a bucket and counts toward the frequency of that
38  * bucket.  Bucket ranges are consecutive, with the maximum of one
39  * bucket's range always one less than the minimum of the next bucket's
40  * range.  By convention each bucket is identified by the minimum of its
41  * range.
42  *
43  * @author Tom Erickson
44  */
45 public abstract class Distribution implements AggregationValue,
46        Iterable <Distribution.Bucket>, Serializable
47 {
48     static final long serialVersionUID = 1186243118882654932L;
49 
50     /** @serial */
51     private List <Bucket> buckets;
52     private transient double total;
53     private transient boolean initialized;
54 
55     /**
56      * Package level access, called by subclasses LinearDistribution and
57      * LogDistribution, but not available outside the API.
58      *
59      * @param base  the lower bound of this distribution, or zero if not
60      * applicable
61      * @param constant  the constant term of the distribution function
62      * used to calculate the lower bound of any bucket given the lower
63      * bound of the previous bucket, for example the step in a linear
64      * distribution or the log base in a logarithmic distribution.
65      * @param frequencies  for each bucket, the number of aggregated
66      * values falling into that bucket's range; each element must be a
67      * positive integer
68      * @throws NullPointerException if frequencies is null
69      * @throws IllegalArgumentException if any element of frequencies
70      * does not have the expected range as defined by checkBucketRange()
71      */
Distribution(long base, long constant, long[] frequencies)72     Distribution(long base, long constant, long[] frequencies)
73     {
74 	total = 0;
75 	long frequency;
76 	for (int i = 0, len = frequencies.length; i < len; ++i) {
77 	    frequency = frequencies[i];
78 	    total += frequency;
79 	}
80 
81 	buckets = createBuckets(base, constant, frequencies);
82 	initialized = true;
83     }
84 
85     /**
86      * Supports XML persistence of subclasses.  Sub-class implementation
87      * must call initialize() after setting any state specific to that
88      * subclass for determining bucket ranges.
89      *
90      * @throws NullPointerException if frequencies is null
91      * @throws IllegalArgumentException if any element of frequencies
92      * does not have the expected range as defined by checkBucketRange()
93      */
Distribution(List <Bucket> frequencies)94     Distribution(List <Bucket> frequencies)
95     {
96 	// defensively copy frequencies list
97 	int len = frequencies.size();
98 	// don't need gratuitous capacity % added by constructor that
99 	// takes a Collection argument; list will not be modified
100 	buckets = new ArrayList <Bucket> (len);
101 	buckets.addAll(frequencies);
102     }
103 
104     final void
initialize()105     initialize()
106     {
107         // Called by constructor and readObject() (deserialization).
108 	// 1. Check class invariants, throw exception if deserialized
109 	//    state inconsistent with a Distribution that can result
110 	//    from the public constructor.
111 	// 2. Compute total (transient property derived from buckets)
112 	total = 0;
113 	long frequency;
114 	Bucket bucket;
115 	int len = buckets.size();
116 	for (int i = 0; i < len; ++i) {
117 	    bucket = buckets.get(i);
118 	    frequency = bucket.getFrequency();
119 	    // relies on package-private getBucketRange()
120 	    // implementation
121 	    checkBucketRange(i, len, bucket);
122 	    total += frequency;
123 	}
124 	initialized = true;
125     }
126 
127     // Must be called by public instance methods (since the AbstractList
128     // methods all depend on get() and size(), it is sufficient to call
129     // checkInit() only in those inherited methods).
130     private void
checkInit()131     checkInit()
132     {
133 	if (!initialized) {
134 	    throw new IllegalStateException("Uninitialized");
135 	}
136     }
137 
138     /**
139      * Gets a two element array: the first elelemt is the range minimum
140      * (inclusive), the second element is the range maximum (inclusive).
141      * Implemented by subclasses LinearDistribution and LogDistribution
142      * to define bucket ranges for this distribution and not available
143      * outside the API.  Used by the private general purpose constructor
144      * called from native code.  Implementation must not use
145      * subclass-specific state, since subclass state has not yet been
146      * allocated.
147      *
148      * @see #Distribution(long base, long constant, long[] frequencies)
149      */
150     abstract long[]
getBucketRange(int i, int len, long base, long constant)151     getBucketRange(int i, int len, long base, long constant);
152 
153     /**
154      * Used by public constructors and deserialization only after
155      * state specific to the subclass is available to the method.
156      */
157     abstract long[]
getBucketRange(int i, int len)158     getBucketRange(int i, int len);
159 
160     private List <Distribution.Bucket>
createBuckets(long base, long constant, long[] frequencies)161     createBuckets(long base, long constant, long[] frequencies)
162     {
163 	int len = frequencies.length;
164 	Bucket bucket;
165 	List <Bucket> buckets = new ArrayList <Bucket> (len);
166 	long min; // current bucket
167 	long max; // next bucket minus one
168 	long[] range; // two element array: { min, max }
169 
170 	for (int i = 0; i < len; ++i) {
171 	    range = getBucketRange(i, len, base, constant);
172 	    min = range[0];
173 	    max = range[1];
174 	    bucket = new Distribution.Bucket(min, max, frequencies[i]);
175 	    buckets.add(bucket);
176 	}
177 
178 	return buckets;
179     }
180 
181     /**
182      * Validates that bucket has the expected range for the given bucket
183      * index.  Uses {@code base} and {@code constant} constructor args
184      * to check invariants specific to each subclass, since state
185      * derived from these args in a subclass is not yet available in the
186      * superclass constructor.
187      *
188      * @throws IllegalArgumentException if bucket does not have the
189      * expected range for the given bucket index {@code i}
190      */
191     private void
checkBucketRange(int i, int bucketCount, Distribution.Bucket bucket, long base, long constant)192     checkBucketRange(int i, int bucketCount, Distribution.Bucket bucket,
193 	    long base, long constant)
194     {
195 	long[] range = getBucketRange(i, bucketCount, base, constant);
196 	checkBucketRange(i, bucket, range);
197     }
198 
199     private void
checkBucketRange(int i, int bucketCount, Distribution.Bucket bucket)200     checkBucketRange(int i, int bucketCount, Distribution.Bucket bucket)
201     {
202 	long[] range = getBucketRange(i, bucketCount);
203 	checkBucketRange(i, bucket, range);
204     }
205 
206     private void
checkBucketRange(int i, Distribution.Bucket bucket, long[] range)207     checkBucketRange(int i, Distribution.Bucket bucket, long[] range)
208     {
209 	long min = range[0];
210 	long max = range[1];
211 
212 	if (bucket.getMin() != min) {
213 	    throw new IllegalArgumentException("bucket min " +
214 		    bucket.getMin() + " at index " + i + ", expected " + min);
215 	}
216 	if (bucket.getMax() != max) {
217 	    throw new IllegalArgumentException("bucket max " +
218 		    bucket.getMax() + " at index " + i + ", expected " + max);
219 	}
220     }
221 
222     /**
223      * Gets a modifiable list of this distribution's buckets ordered by
224      * bucket range.  Modifying the returned list has no effect on this
225      * distribution.  Supports XML persistence.
226      *
227      * @return a modifiable list of this distribution's buckets ordered
228      * by bucket range
229      */
230     public List <Bucket>
getBuckets()231     getBuckets()
232     {
233 	checkInit();
234 	return new ArrayList <Bucket> (buckets);
235     }
236 
237     /**
238      * Gets a read-only {@code List} view of this distribution.
239      *
240      * @return a read-only {@code List} view of this distribution
241      */
242     public List <Bucket>
asList()243     asList()
244     {
245 	checkInit();
246 	return Collections. <Bucket> unmodifiableList(buckets);
247     }
248 
249     /**
250      * Gets the number of buckets in this distribution.
251      *
252      * @return non-negative bucket count
253      */
254     public int
size()255     size()
256     {
257 	checkInit();
258 	return buckets.size();
259     }
260 
261     /**
262      * Gets the bucket at the given distribution index (starting at
263      * zero).
264      *
265      * @return non-null distribution bucket at the given zero-based
266      * index
267      */
268     public Bucket
get(int index)269     get(int index)
270     {
271 	checkInit();
272 	return buckets.get(index);
273     }
274 
275     /**
276      * Gets an iterator over the buckets of this distribution.
277      *
278      * @return an iterator over the buckets of this distribution
279      */
280     public Iterator<Bucket>
iterator()281     iterator()
282     {
283 	checkInit();
284 	return buckets.iterator();
285     }
286 
287     /**
288      * Compares the specified object with this {@code Distribution}
289      * instance for equality.  Defines equality as having the same
290      * buckets with the same values.
291      *
292      * @return {@code true} if and only if the specified object is of
293      * type {@code Distribution} and both instances have the same size
294      * and equal buckets at corresponding distribution indexes
295      */
296     public boolean
equals(Object o)297     equals(Object o)
298     {
299 	checkInit();
300 	if (o instanceof Distribution) {
301 	    Distribution d = (Distribution)o;
302 	    return buckets.equals(d.buckets);
303 	}
304 	return false;
305     }
306 
307     /**
308      * Overridden to ensure that equals instances have equal hash codes.
309      */
310     public int
hashCode()311     hashCode()
312     {
313 	checkInit();
314 	return buckets.hashCode();
315     }
316 
317     /**
318      * Gets the total frequency across all buckets.
319      *
320      * @return sum of the frequency of all buckets in this distribution
321      */
322     public double
getTotal()323     getTotal()
324     {
325 	checkInit();
326 	return total;
327     }
328 
329     /**
330      * Gets the numeric value of this distribution used to compare
331      * distributions by overall magnitude, defined as the sum total of
332      * each bucket's frequency times the minimum of its range.
333      */
getValue()334     public abstract Number getValue();
335 
336     /**
337      * Called by native code
338      */
339     private void
normalizeBuckets(long normal)340     normalizeBuckets(long normal)
341     {
342 	for (Bucket b : buckets) {
343 	    b.frequency /= normal;
344 	}
345     }
346 
347     /**
348      * A range inclusive at both endpoints and a count of aggregated
349      * values that fall in that range.  Buckets in a {@link
350      * Distribution} are consecutive, such that the max of one bucket is
351      * always one less than the min of the next bucket (or {@link
352      * Long#MAX_VALUE} if it is the last bucket in the {@code
353      * Distribution}).
354      * <p>
355      * Immutable.  Supports persistence using {@link java.beans.XMLEncoder}.
356      */
357     public static final class Bucket implements Serializable {
358 	static final long serialVersionUID = 4863264115375406295L;
359 
360 	/** @serial */
361 	private final long min;
362 	/** @serial */
363 	private final long max;
364 	/** @serial */
365 	private long frequency; // non-final so native code can normalize
366 
367 	static {
368 	    try {
369 		BeanInfo info = Introspector.getBeanInfo(Bucket.class);
370 		PersistenceDelegate persistenceDelegate =
371 			new DefaultPersistenceDelegate(
372 			new String[] {"min", "max", "frequency"})
373 		{
374 		    /*
375 		     * Need to prevent DefaultPersistenceDelegate from using
376 		     * overridden equals() method, resulting in a
377 		     * StackOverFlowError.  Revert to PersistenceDelegate
378 		     * implementation.  See
379 		     * http://forum.java.sun.com/thread.jspa?threadID=
380 		     * 477019&tstart=135
381 		     */
382 		    protected boolean
383 		    mutatesTo(Object oldInstance, Object newInstance)
384 		    {
385 			return (newInstance != null && oldInstance != null &&
386 				(oldInstance.getClass() ==
387 				newInstance.getClass()));
388 		    }
389 		};
390 		BeanDescriptor d = info.getBeanDescriptor();
391 		d.setValue("persistenceDelegate", persistenceDelegate);
392 	    } catch (IntrospectionException e) {
393 		System.out.println(e);
394 	    }
395 	}
396 
397 	/**
398 	 * Creates a distribution bucket with the given range and
399 	 * frequency.
400 	 *
401 	 * @param rangeMinimumInclusive sets the lower bound (inclusive)
402 	 * returned by {@link #getMin()}
403 	 * @param rangeMaximumInclusive sets the upper bound (inclusive)
404 	 * returned by {@link #getMax()}
405 	 * @param valuesInRange sets the value frequency in this
406 	 * bucket's range returned by {@link #getFrequency()}
407 	 * @throws IllegalArgumentException if {@code
408 	 * rangeMaximumInclusive} is less than {@code
409 	 * rangeMinimumInclusive}
410 	 */
411 	public
Bucket(long rangeMinimumInclusive, long rangeMaximumInclusive, long valuesInRange)412 	Bucket(long rangeMinimumInclusive, long rangeMaximumInclusive,
413 		long valuesInRange)
414 	{
415 	    if (rangeMaximumInclusive < rangeMinimumInclusive) {
416 		throw new IllegalArgumentException("upper bound " +
417 			rangeMaximumInclusive + " is less than lower bound " +
418 			rangeMinimumInclusive);
419 	    }
420 
421 	    min = rangeMinimumInclusive;
422 	    max = rangeMaximumInclusive;
423 	    frequency = valuesInRange;
424 	}
425 
426 	/**
427 	 * Gets the lower bound of this bucket's range (inclusive).
428 	 */
429 	public long
getMin()430 	getMin()
431 	{
432 	    return min;
433 	}
434 
435 	/**
436 	 * Gets the upper bound of this bucket's range (inclusive).
437 	 */
438 	public long
getMax()439 	getMax()
440 	{
441 	    return max;
442 	}
443 
444 	/**
445 	 * Gets the number of values in a {@link Distribution} that fall
446 	 * into the range defined by this bucket.
447 	 */
448 	public long
getFrequency()449 	getFrequency()
450 	{
451 	    return frequency;
452 	}
453 
454 	/**
455 	 * Compares the specified object with this distribution bucket
456 	 * for equality.  Defines equality of two distribution buckets
457 	 * as having the same range and the same frequency.
458 	 *
459 	 * @return false if the specified object is not a {@code
460 	 * Distribution.Bucket}
461 	 */
462 	@Override
463 	public boolean
equals(Object o)464 	equals(Object o)
465 	{
466 	    if (o instanceof Bucket) {
467 		Bucket b = (Bucket)o;
468 		return ((min == b.min) &&
469 			(max == b.max) &&
470 			(frequency == b.frequency));
471 	    }
472 	    return false;
473 	}
474 
475 	/**
476 	 * Overridden to ensure that equal buckets have equal hashcodes.
477 	 */
478 	@Override
479 	public int
hashCode()480 	hashCode()
481 	{
482 	    int hash = 17;
483 	    hash = (37 * hash) + ((int)(min ^ (min >>> 32)));
484 	    hash = (37 * hash) + ((int)(max ^ (max >>> 32)));
485 	    hash = (37 * hash) + ((int)(frequency ^ (frequency >>> 32)));
486 	    return hash;
487 	}
488 
489 	private void
readObject(ObjectInputStream s)490 	readObject(ObjectInputStream s)
491 		throws IOException, ClassNotFoundException
492 	{
493 	    s.defaultReadObject();
494 	    // check class invariants (as constructor does)
495 	    if (max < min) {
496 		throw new InvalidObjectException("upper bound " +
497 			max + " is less than lower bound " + min);
498 	    }
499 	}
500 
501 	/**
502 	 * Gets a string representation of this distribution bucket
503 	 * useful for logging and not intended for display.  The exact
504 	 * details of the representation are unspecified and subject to
505 	 * change, but the following format may be regarded as typical:
506 	 * <pre><code>
507 	 * class-name[property1 = value1, property2 = value2]
508 	 * </code></pre>
509 	 */
510 	public String
toString()511 	toString()
512 	{
513 	    StringBuilder buf = new StringBuilder();
514 	    buf.append(Bucket.class.getName());
515 	    buf.append("[min = ");
516 	    buf.append(min);
517 	    buf.append(", max = ");
518 	    buf.append(max);
519 	    buf.append(", frequency = ");
520 	    buf.append(frequency);
521 	    buf.append(']');
522 	    return buf.toString();
523 	}
524     }
525 
526     /**
527      * Gets a list of buckets of interest by excluding empty buckets at
528      * both ends of the distribution.  Leaves one empty bucket on each
529      * end if possible to convey the distribution context more
530      * effectively in a display.
531      *
532      * @return an unmodifiable sublist that includes the range starting
533      * from the first bucket with a non-zero frequency and ending with
534      * the last bucket with a non-zero frequency, plus one empty bucket
535      * before and after that range if possible
536      */
537     public List <Bucket>
getDisplayRange()538     getDisplayRange()
539     {
540 	checkInit();
541 	int min = -1;
542 	int max = -1;
543 	int len = size();
544 	Bucket b;
545 	// Get first non-empty bucket
546 	for (int i = 0; i < len; ++i) {
547 	    b = buckets.get(i);
548 	    if (b.getFrequency() > 0L) {
549 		min = i;
550 		break;
551 	    }
552 	}
553 	if (min < 0) {
554 	    return Collections. <Bucket> emptyList();
555 	}
556 	// Get last non-empty bucket
557 	for (int i = (len - 1); i >= 0; --i) {
558 	    b = buckets.get(i);
559 	    if (b.getFrequency() > 0L) {
560 		max = i;
561 		break;
562 	    }
563 	}
564 	// If possible, pad non-empty range with one empty bucket at
565 	// each end.
566 	if (min > 0) {
567 	    --min;
568 	}
569 	if (max < (len - 1)) {
570 	    ++max;
571 	}
572 
573 	// subList inclusive at low index, exclusive at high index
574 	return Collections. <Bucket>
575 		unmodifiableList(buckets).subList(min, max + 1);
576     }
577 
578     private void
readObject(ObjectInputStream s)579     readObject(ObjectInputStream s)
580             throws IOException, ClassNotFoundException
581     {
582 	s.defaultReadObject();
583 
584 	// Defensively copy buckets _before_ validating.  Subclass
585 	// validates by calling initialize() after reading any state
586 	// specific to that subclass needed for validation.
587 	int len = buckets.size();
588 	ArrayList <Bucket> copy = new ArrayList <Bucket> (len);
589 	copy.addAll(buckets);
590 	buckets = copy;
591     }
592 
593     /**
594      * Gets a string representation of this {@code Distribution} useful
595      * for logging and not intended for display.  The exact details of
596      * the representation are unspecified and subject to change, but the
597      * following format may be regarded as typical:
598      * <pre><code>
599      * class-name[property1 = value1, property2 = value2]
600      * </code></pre>
601      */
602     public String
toString()603     toString()
604     {
605 	checkInit();
606 	StringBuilder buf = new StringBuilder();
607 	buf.append(Distribution.class.getName());
608 	buf.append("[buckets = ");
609 	List <Bucket> list = getDisplayRange();
610 	if (list.isEmpty()) {
611 	    buf.append("<empty>");
612 	} else {
613 	    buf.append(Arrays.toString(getDisplayRange().toArray()));
614 	}
615 	buf.append(", total = ");
616 	buf.append(getTotal());
617 	buf.append(']');
618 	return buf.toString();
619     }
620 }
621