cddl/contrib/opensolaris/lib/libdtrace/common/dt_aggregate.c

   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
  27 /*
  28  * Copyright (c) 2013, Joyent, Inc. All rights reserved.
  29  * Copyright (c) 2012 by Delphix. All rights reserved.
  30  */
  31
  32 #include <stdlib.h>
  33 #include <strings.h>
  34 #include <errno.h>
  35 #include <unistd.h>
  36 #include <dt_impl.h>
  37 #include <assert.h>
  38 #if defined(sun)
  39 #include <alloca.h>
  40 #else
  41 #include <sys/sysctl.h>
  42 #include <libproc_compat.h>
  43 #endif
  44 #include <limits.h>
  45
  46 #define DTRACE_AHASHSIZE        32779           /* big 'ol prime */
  47
  48 /*
  49  * Because qsort(3C) does not allow an argument to be passed to a comparison
  50  * function, the variables that affect comparison must regrettably be global;
  51  * they are protected by a global static lock, dt_qsort_lock.
  52  */
  53 static pthread_mutex_t dt_qsort_lock = PTHREAD_MUTEX_INITIALIZER;
  54
  55 static int dt_revsort;
  56 static int dt_keysort;
  57 static int dt_keypos;
  58
  59 #define DT_LESSTHAN     (dt_revsort == 0 ? -1 : 1)
  60 #define DT_GREATERTHAN  (dt_revsort == 0 ? 1 : -1)
  61
  62 static void
  63 dt_aggregate_count(int64_t *existing, int64_t *new, size_t size)
  64 {
  65         uint_t i;
  66
  67         for (i = 0; i < size / sizeof (int64_t); i++)
  68                 existing[i] = existing[i] + new[i];
  69 }
  70
  71 static int
  72 dt_aggregate_countcmp(int64_t *lhs, int64_t *rhs)
  73 {
  74         int64_t lvar = *lhs;
  75         int64_t rvar = *rhs;
  76
  77         if (lvar < rvar)
  78                 return (DT_LESSTHAN);
  79
  80         if (lvar > rvar)
  81                 return (DT_GREATERTHAN);
  82
  83         return (0);
  84 }
  85
  86 /*ARGSUSED*/
  87 static void
  88 dt_aggregate_min(int64_t *existing, int64_t *new, size_t size)
  89 {
  90         if (*new < *existing)
  91                 *existing = *new;
  92 }
  93
  94 /*ARGSUSED*/
  95 static void
  96 dt_aggregate_max(int64_t *existing, int64_t *new, size_t size)
  97 {
  98         if (*new > *existing)
  99                 *existing = *new;
 100 }
 101
 102 static int
 103 dt_aggregate_averagecmp(int64_t *lhs, int64_t *rhs)
 104 {
 105         int64_t lavg = lhs[0] ? (lhs[1] / lhs[0]) : 0;
 106         int64_t ravg = rhs[0] ? (rhs[1] / rhs[0]) : 0;
 107
 108         if (lavg < ravg)
 109                 return (DT_LESSTHAN);
 110
 111         if (lavg > ravg)
 112                 return (DT_GREATERTHAN);
 113
 114         return (0);
 115 }
 116
 117 static int
 118 dt_aggregate_stddevcmp(int64_t *lhs, int64_t *rhs)
 119 {
 120         uint64_t lsd = dt_stddev((uint64_t *)lhs, 1);
 121         uint64_t rsd = dt_stddev((uint64_t *)rhs, 1);
 122
 123         if (lsd < rsd)
 124                 return (DT_LESSTHAN);
 125
 126         if (lsd > rsd)
 127                 return (DT_GREATERTHAN);
 128
 129         return (0);
 130 }
 131
 132 /*ARGSUSED*/
 133 static void
 134 dt_aggregate_lquantize(int64_t *existing, int64_t *new, size_t size)
 135 {
 136         int64_t arg = *existing++;
 137         uint16_t levels = DTRACE_LQUANTIZE_LEVELS(arg);
 138         int i;
 139
 140         for (i = 0; i <= levels + 1; i++)
 141                 existing[i] = existing[i] + new[i + 1];
 142 }
 143
 144 static long double
 145 dt_aggregate_lquantizedsum(int64_t *lquanta)
 146 {
 147         int64_t arg = *lquanta++;
 148         int32_t base = DTRACE_LQUANTIZE_BASE(arg);
 149         uint16_t step = DTRACE_LQUANTIZE_STEP(arg);
 150         uint16_t levels = DTRACE_LQUANTIZE_LEVELS(arg), i;
 151         long double total = (long double)lquanta[0] * (long double)(base - 1);
 152
 153         for (i = 0; i < levels; base += step, i++)
 154                 total += (long double)lquanta[i + 1] * (long double)base;
 155
 156         return (total + (long double)lquanta[levels + 1] *
 157             (long double)(base + 1));
 158 }
 159
 160 static int64_t
 161 dt_aggregate_lquantizedzero(int64_t *lquanta)
 162 {
 163         int64_t arg = *lquanta++;
 164         int32_t base = DTRACE_LQUANTIZE_BASE(arg);
 165         uint16_t step = DTRACE_LQUANTIZE_STEP(arg);
 166         uint16_t levels = DTRACE_LQUANTIZE_LEVELS(arg), i;
 167
 168         if (base - 1 == 0)
 169                 return (lquanta[0]);
 170
 171         for (i = 0; i < levels; base += step, i++) {
 172                 if (base != 0)
 173                         continue;
 174
 175                 return (lquanta[i + 1]);
 176         }
 177
 178         if (base + 1 == 0)
 179                 return (lquanta[levels + 1]);
 180
 181         return (0);
 182 }
 183
 184 static int
 185 dt_aggregate_lquantizedcmp(int64_t *lhs, int64_t *rhs)
 186 {
 187         long double lsum = dt_aggregate_lquantizedsum(lhs);
 188         long double rsum = dt_aggregate_lquantizedsum(rhs);
 189         int64_t lzero, rzero;
 190
 191         if (lsum < rsum)
 192                 return (DT_LESSTHAN);
 193
 194         if (lsum > rsum)
 195                 return (DT_GREATERTHAN);
 196
 197         /*
 198          * If they're both equal, then we will compare based on the weights at
 199          * zero.  If the weights at zero are equal (or if zero is not within
 200          * the range of the linear quantization), then this will be judged a
 201          * tie and will be resolved based on the key comparison.
 202          */
 203         lzero = dt_aggregate_lquantizedzero(lhs);
 204         rzero = dt_aggregate_lquantizedzero(rhs);
 205
 206         if (lzero < rzero)
 207                 return (DT_LESSTHAN);
 208
 209         if (lzero > rzero)
 210                 return (DT_GREATERTHAN);
 211
 212         return (0);
 213 }
 214
 215 static void
 216 dt_aggregate_llquantize(int64_t *existing, int64_t *new, size_t size)
 217 {
 218         int i;
 219
 220         for (i = 1; i < size / sizeof (int64_t); i++)
 221                 existing[i] = existing[i] + new[i];
 222 }
 223
 224 static long double
 225 dt_aggregate_llquantizedsum(int64_t *llquanta)
 226 {
 227         int64_t arg = *llquanta++;
 228         uint16_t factor = DTRACE_LLQUANTIZE_FACTOR(arg);
 229         uint16_t low = DTRACE_LLQUANTIZE_LOW(arg);
 230         uint16_t high = DTRACE_LLQUANTIZE_HIGH(arg);
 231         uint16_t nsteps = DTRACE_LLQUANTIZE_NSTEP(arg);
 232         int bin = 0, order;
 233         int64_t value = 1, next, step;
 234         long double total;
 235
 236         assert(nsteps >= factor);
 237         assert(nsteps % factor == 0);
 238
 239         for (order = 0; order < low; order++)
 240                 value *= factor;
 241
 242         total = (long double)llquanta[bin++] * (long double)(value - 1);
 243
 244         next = value * factor;
 245         step = next > nsteps ? next / nsteps : 1;
 246
 247         while (order <= high) {
 248                 assert(value < next);
 249                 total += (long double)llquanta[bin++] * (long double)(value);
 250
 251                 if ((value += step) != next)
 252                         continue;
 253
 254                 next = value * factor;
 255                 step = next > nsteps ? next / nsteps : 1;
 256                 order++;
 257         }
 258
 259         return (total + (long double)llquanta[bin] * (long double)value);
 260 }
 261
 262 static int
 263 dt_aggregate_llquantizedcmp(int64_t *lhs, int64_t *rhs)
 264 {
 265         long double lsum = dt_aggregate_llquantizedsum(lhs);
 266         long double rsum = dt_aggregate_llquantizedsum(rhs);
 267         int64_t lzero, rzero;
 268
 269         if (lsum < rsum)
 270                 return (DT_LESSTHAN);
 271
 272         if (lsum > rsum)
 273                 return (DT_GREATERTHAN);
 274
 275         /*
 276          * If they're both equal, then we will compare based on the weights at
 277          * zero.  If the weights at zero are equal, then this will be judged a
 278          * tie and will be resolved based on the key comparison.
 279          */
 280         lzero = lhs[1];
 281         rzero = rhs[1];
 282
 283         if (lzero < rzero)
 284                 return (DT_LESSTHAN);
 285
 286         if (lzero > rzero)
 287                 return (DT_GREATERTHAN);
 288
 289         return (0);
 290 }
 291
 292 static int
 293 dt_aggregate_quantizedcmp(int64_t *lhs, int64_t *rhs)
 294 {
 295         int nbuckets = DTRACE_QUANTIZE_NBUCKETS;
 296         long double ltotal = 0, rtotal = 0;
 297         int64_t lzero, rzero;
 298         uint_t i;
 299
 300         for (i = 0; i < nbuckets; i++) {
 301                 int64_t bucketval = DTRACE_QUANTIZE_BUCKETVAL(i);
 302
 303                 if (bucketval == 0) {
 304                         lzero = lhs[i];
 305                         rzero = rhs[i];
 306                 }
 307
 308                 ltotal += (long double)bucketval * (long double)lhs[i];
 309                 rtotal += (long double)bucketval * (long double)rhs[i];
 310         }
 311
 312         if (ltotal < rtotal)
 313                 return (DT_LESSTHAN);
 314
 315         if (ltotal > rtotal)
 316                 return (DT_GREATERTHAN);
 317
 318         /*
 319          * If they're both equal, then we will compare based on the weights at
 320          * zero.  If the weights at zero are equal, then this will be judged a
 321          * tie and will be resolved based on the key comparison.
 322          */
 323         if (lzero < rzero)
 324                 return (DT_LESSTHAN);
 325
 326         if (lzero > rzero)
 327                 return (DT_GREATERTHAN);
 328
 329         return (0);
 330 }
 331
 332 static void
 333 dt_aggregate_usym(dtrace_hdl_t *dtp, uint64_t *data)
 334 {
 335         uint64_t pid = data[0];
 336         uint64_t *pc = &data[1];
 337         struct ps_prochandle *P;
 338         GElf_Sym sym;
 339
 340         if (dtp->dt_vector != NULL)
 341                 return;
 342
 343         if ((P = dt_proc_grab(dtp, pid, PGRAB_RDONLY | PGRAB_FORCE, 0)) == NULL)
 344                 return;
 345
 346         dt_proc_lock(dtp, P);
 347
 348         if (Plookup_by_addr(P, *pc, NULL, 0, &sym) == 0)
 349                 *pc = sym.st_value;
 350
 351         dt_proc_unlock(dtp, P);
 352         dt_proc_release(dtp, P);
 353 }
 354
 355 static void
 356 dt_aggregate_umod(dtrace_hdl_t *dtp, uint64_t *data)
 357 {
 358         uint64_t pid = data[0];
 359         uint64_t *pc = &data[1];
 360         struct ps_prochandle *P;
 361         const prmap_t *map;
 362
 363         if (dtp->dt_vector != NULL)
 364                 return;
 365
 366         if ((P = dt_proc_grab(dtp, pid, PGRAB_RDONLY | PGRAB_FORCE, 0)) == NULL)
 367                 return;
 368
 369         dt_proc_lock(dtp, P);
 370
 371         if ((map = Paddr_to_map(P, *pc)) != NULL)
 372                 *pc = map->pr_vaddr;
 373
 374         dt_proc_unlock(dtp, P);
 375         dt_proc_release(dtp, P);
 376 }
 377
 378 static void
 379 dt_aggregate_sym(dtrace_hdl_t *dtp, uint64_t *data)
 380 {
 381         GElf_Sym sym;
 382         uint64_t *pc = data;
 383
 384         if (dtrace_lookup_by_addr(dtp, *pc, &sym, NULL) == 0)
 385                 *pc = sym.st_value;
 386 }
 387
 388 static void
 389 dt_aggregate_mod(dtrace_hdl_t *dtp, uint64_t *data)
 390 {
 391         uint64_t *pc = data;
 392         dt_module_t *dmp;
 393
 394         if (dtp->dt_vector != NULL) {
 395                 /*
 396                  * We don't have a way of just getting the module for a
 397                  * vectored open, and it doesn't seem to be worth defining
 398                  * one.  This means that use of mod() won't get true
 399                  * aggregation in the postmortem case (some modules may
 400                  * appear more than once in aggregation output).  It seems
 401                  * unlikely that anyone will ever notice or care...
 402                  */
 403                 return;
 404         }
 405
 406         for (dmp = dt_list_next(&dtp->dt_modlist); dmp != NULL;
 407             dmp = dt_list_next(dmp)) {
 408                 if (*pc - dmp->dm_text_va < dmp->dm_text_size) {
 409                         *pc = dmp->dm_text_va;
 410                         return;
 411                 }
 412         }
 413 }
 414
 415 static dtrace_aggvarid_t
 416 dt_aggregate_aggvarid(dt_ahashent_t *ent)
 417 {
 418         dtrace_aggdesc_t *agg = ent->dtahe_data.dtada_desc;
 419         caddr_t data = ent->dtahe_data.dtada_data;
 420         dtrace_recdesc_t *rec = agg->dtagd_rec;
 421
 422         /*
 423          * First, we'll check the variable ID in the aggdesc.  If it's valid,
 424          * we'll return it.  If not, we'll use the compiler-generated ID
 425          * present as the first record.
 426          */
 427         if (agg->dtagd_varid != DTRACE_AGGVARIDNONE)
 428                 return (agg->dtagd_varid);
 429
 430         agg->dtagd_varid = *((dtrace_aggvarid_t *)(uintptr_t)(data +
 431             rec->dtrd_offset));
 432
 433         return (agg->dtagd_varid);
 434 }
 435
 436
 437 static int
 438 dt_aggregate_snap_cpu(dtrace_hdl_t *dtp, processorid_t cpu)
 439 {
 440         dtrace_epid_t id;
 441         uint64_t hashval;
 442         size_t offs, roffs, size, ndx;
 443         int i, j, rval;
 444         caddr_t addr, data;
 445         dtrace_recdesc_t *rec;
 446         dt_aggregate_t *agp = &dtp->dt_aggregate;
 447         dtrace_aggdesc_t *agg;
 448         dt_ahash_t *hash = &agp->dtat_hash;
 449         dt_ahashent_t *h;
 450         dtrace_bufdesc_t b = agp->dtat_buf, *buf = &b;
 451         dtrace_aggdata_t *aggdata;
 452         int flags = agp->dtat_flags;
 453
 454         buf->dtbd_cpu = cpu;
 455
 456 #if defined(sun)
 457         if (dt_ioctl(dtp, DTRACEIOC_AGGSNAP, buf) == -1) {
 458 #else
 459         if (dt_ioctl(dtp, DTRACEIOC_AGGSNAP, &buf) == -1) {
 460 #endif
 461                 if (errno == ENOENT) {
 462                         /*
 463                          * If that failed with ENOENT, it may be because the
 464                          * CPU was unconfigured.  This is okay; we'll just
 465                          * do nothing but return success.
 466                          */
 467                         return (0);
 468                 }
 469
 470                 return (dt_set_errno(dtp, errno));
 471         }
 472
 473         if (buf->dtbd_drops != 0) {
 474                 if (dt_handle_cpudrop(dtp, cpu,
 475                     DTRACEDROP_AGGREGATION, buf->dtbd_drops) == -1)
 476                         return (-1);
 477         }
 478
 479         if (buf->dtbd_size == 0)
 480                 return (0);
 481
 482         if (hash->dtah_hash == NULL) {
 483                 size_t size;
 484
 485                 hash->dtah_size = DTRACE_AHASHSIZE;
 486                 size = hash->dtah_size * sizeof (dt_ahashent_t *);
 487
 488                 if ((hash->dtah_hash = malloc(size)) == NULL)
 489                         return (dt_set_errno(dtp, EDT_NOMEM));
 490
 491                 bzero(hash->dtah_hash, size);
 492         }
 493
 494         for (offs = 0; offs < buf->dtbd_size; ) {
 495                 /*
 496                  * We're guaranteed to have an ID.
 497                  */
 498                 id = *((dtrace_epid_t *)((uintptr_t)buf->dtbd_data +
 499                     (uintptr_t)offs));
 500
 501                 if (id == DTRACE_AGGIDNONE) {
 502                         /*
 503                          * This is filler to assure proper alignment of the
 504                          * next record; we simply ignore it.
 505                          */
 506                         offs += sizeof (id);
 507                         continue;
 508                 }
 509
 510                 if ((rval = dt_aggid_lookup(dtp, id, &agg)) != 0)
 511                         return (rval);
 512
 513                 addr = buf->dtbd_data + offs;
 514                 size = agg->dtagd_size;
 515                 hashval = 0;
 516
 517                 for (j = 0; j < agg->dtagd_nrecs - 1; j++) {
 518                         rec = &agg->dtagd_rec[j];
 519                         roffs = rec->dtrd_offset;
 520
 521                         switch (rec->dtrd_action) {
 522                         case DTRACEACT_USYM:
 523                                 dt_aggregate_usym(dtp,
 524                                     /* LINTED - alignment */
 525                                     (uint64_t *)&addr[roffs]);
 526                                 break;
 527
 528                         case DTRACEACT_UMOD:
 529                                 dt_aggregate_umod(dtp,
 530                                     /* LINTED - alignment */
 531                                     (uint64_t *)&addr[roffs]);
 532                                 break;
 533
 534                         case DTRACEACT_SYM:
 535                                 /* LINTED - alignment */
 536                                 dt_aggregate_sym(dtp, (uint64_t *)&addr[roffs]);
 537                                 break;
 538
 539                         case DTRACEACT_MOD:
 540                                 /* LINTED - alignment */
 541                                 dt_aggregate_mod(dtp, (uint64_t *)&addr[roffs]);
 542                                 break;
 543
 544                         default:
 545                                 break;
 546                         }
 547
 548                         for (i = 0; i < rec->dtrd_size; i++)
 549                                 hashval += addr[roffs + i];
 550                 }
 551
 552                 ndx = hashval % hash->dtah_size;
 553
 554                 for (h = hash->dtah_hash[ndx]; h != NULL; h = h->dtahe_next) {
 555                         if (h->dtahe_hashval != hashval)
 556                                 continue;
 557
 558                         if (h->dtahe_size != size)
 559                                 continue;
 560
 561                         aggdata = &h->dtahe_data;
 562                         data = aggdata->dtada_data;
 563
 564                         for (j = 0; j < agg->dtagd_nrecs - 1; j++) {
 565                                 rec = &agg->dtagd_rec[j];
 566                                 roffs = rec->dtrd_offset;
 567
 568                                 for (i = 0; i < rec->dtrd_size; i++)
 569                                         if (addr[roffs + i] != data[roffs + i])
 570                                                 goto hashnext;
 571                         }
 572
 573                         /*
 574                          * We found it.  Now we need to apply the aggregating
 575                          * action on the data here.
 576                          */
 577                         rec = &agg->dtagd_rec[agg->dtagd_nrecs - 1];
 578                         roffs = rec->dtrd_offset;
 579                         /* LINTED - alignment */
 580                         h->dtahe_aggregate((int64_t *)&data[roffs],
 581                             /* LINTED - alignment */
 582                             (int64_t *)&addr[roffs], rec->dtrd_size);
 583
 584                         /*
 585                          * If we're keeping per CPU data, apply the aggregating
 586                          * action there as well.
 587                          */
 588                         if (aggdata->dtada_percpu != NULL) {
 589                                 data = aggdata->dtada_percpu[cpu];
 590
 591                                 /* LINTED - alignment */
 592                                 h->dtahe_aggregate((int64_t *)data,
 593                                     /* LINTED - alignment */
 594                                     (int64_t *)&addr[roffs], rec->dtrd_size);
 595                         }
 596
 597                         goto bufnext;
 598 hashnext:
 599                         continue;
 600                 }
 601
 602                 /*
 603                  * If we're here, we couldn't find an entry for this record.
 604                  */
 605                 if ((h = malloc(sizeof (dt_ahashent_t))) == NULL)
 606                         return (dt_set_errno(dtp, EDT_NOMEM));
 607                 bzero(h, sizeof (dt_ahashent_t));
 608                 aggdata = &h->dtahe_data;
 609
 610                 if ((aggdata->dtada_data = malloc(size)) == NULL) {
 611                         free(h);
 612                         return (dt_set_errno(dtp, EDT_NOMEM));
 613                 }
 614
 615                 bcopy(addr, aggdata->dtada_data, size);
 616                 aggdata->dtada_size = size;
 617                 aggdata->dtada_desc = agg;
 618                 aggdata->dtada_handle = dtp;
 619                 (void) dt_epid_lookup(dtp, agg->dtagd_epid,
 620                     &aggdata->dtada_edesc, &aggdata->dtada_pdesc);
 621                 aggdata->dtada_normal = 1;
 622
 623                 h->dtahe_hashval = hashval;
 624                 h->dtahe_size = size;
 625                 (void) dt_aggregate_aggvarid(h);
 626
 627                 rec = &agg->dtagd_rec[agg->dtagd_nrecs - 1];
 628
 629                 if (flags & DTRACE_A_PERCPU) {
 630                         int max_cpus = agp->dtat_maxcpu;
 631                         caddr_t *percpu = malloc(max_cpus * sizeof (caddr_t));
 632
 633                         if (percpu == NULL) {
 634                                 free(aggdata->dtada_data);
 635                                 free(h);
 636                                 return (dt_set_errno(dtp, EDT_NOMEM));
 637                         }
 638
 639                         for (j = 0; j < max_cpus; j++) {
 640                                 percpu[j] = malloc(rec->dtrd_size);
 641
 642                                 if (percpu[j] == NULL) {
 643                                         while (--j >= 0)
 644                                                 free(percpu[j]);
 645
 646                                         free(aggdata->dtada_data);
 647                                         free(h);
 648                                         return (dt_set_errno(dtp, EDT_NOMEM));
 649                                 }
 650
 651                                 if (j == cpu) {
 652                                         bcopy(&addr[rec->dtrd_offset],
 653                                             percpu[j], rec->dtrd_size);
 654                                 } else {
 655                                         bzero(percpu[j], rec->dtrd_size);
 656                                 }
 657                         }
 658
 659                         aggdata->dtada_percpu = percpu;
 660                 }
 661
 662                 switch (rec->dtrd_action) {
 663                 case DTRACEAGG_MIN:
 664                         h->dtahe_aggregate = dt_aggregate_min;
 665                         break;
 666
 667                 case DTRACEAGG_MAX:
 668                         h->dtahe_aggregate = dt_aggregate_max;
 669                         break;
 670
 671                 case DTRACEAGG_LQUANTIZE:
 672                         h->dtahe_aggregate = dt_aggregate_lquantize;
 673                         break;
 674
 675                 case DTRACEAGG_LLQUANTIZE:
 676                         h->dtahe_aggregate = dt_aggregate_llquantize;
 677                         break;
 678
 679                 case DTRACEAGG_COUNT:
 680                 case DTRACEAGG_SUM:
 681                 case DTRACEAGG_AVG:
 682                 case DTRACEAGG_STDDEV:
 683                 case DTRACEAGG_QUANTIZE:
 684                         h->dtahe_aggregate = dt_aggregate_count;
 685                         break;
 686
 687                 default:
 688                         return (dt_set_errno(dtp, EDT_BADAGG));
 689                 }
 690
 691                 if (hash->dtah_hash[ndx] != NULL)
 692                         hash->dtah_hash[ndx]->dtahe_prev = h;
 693
 694                 h->dtahe_next = hash->dtah_hash[ndx];
 695                 hash->dtah_hash[ndx] = h;
 696
 697                 if (hash->dtah_all != NULL)
 698                         hash->dtah_all->dtahe_prevall = h;
 699
 700                 h->dtahe_nextall = hash->dtah_all;
 701                 hash->dtah_all = h;
 702 bufnext:
 703                 offs += agg->dtagd_size;
 704         }
 705
 706         return (0);
 707 }
 708
 709 int
 710 dtrace_aggregate_snap(dtrace_hdl_t *dtp)
 711 {
 712         int i, rval;
 713         dt_aggregate_t *agp = &dtp->dt_aggregate;
 714         hrtime_t now = gethrtime();
 715         dtrace_optval_t interval = dtp->dt_options[DTRACEOPT_AGGRATE];
 716
 717         if (dtp->dt_lastagg != 0) {
 718                 if (now - dtp->dt_lastagg < interval)
 719                         return (0);
 720
 721                 dtp->dt_lastagg += interval;
 722         } else {
 723                 dtp->dt_lastagg = now;
 724         }
 725
 726         if (!dtp->dt_active)
 727                 return (dt_set_errno(dtp, EINVAL));
 728
 729         if (agp->dtat_buf.dtbd_size == 0)
 730                 return (0);
 731
 732         for (i = 0; i < agp->dtat_ncpus; i++) {
 733                 if ((rval = dt_aggregate_snap_cpu(dtp, agp->dtat_cpus[i])))
 734                         return (rval);
 735         }
 736
 737         return (0);
 738 }
 739
 740 static int
 741 dt_aggregate_hashcmp(const void *lhs, const void *rhs)
 742 {
 743         dt_ahashent_t *lh = *((dt_ahashent_t **)lhs);
 744         dt_ahashent_t *rh = *((dt_ahashent_t **)rhs);
 745         dtrace_aggdesc_t *lagg = lh->dtahe_data.dtada_desc;
 746         dtrace_aggdesc_t *ragg = rh->dtahe_data.dtada_desc;
 747
 748         if (lagg->dtagd_nrecs < ragg->dtagd_nrecs)
 749                 return (DT_LESSTHAN);
 750
 751         if (lagg->dtagd_nrecs > ragg->dtagd_nrecs)
 752                 return (DT_GREATERTHAN);
 753
 754         return (0);
 755 }
 756
 757 static int
 758 dt_aggregate_varcmp(const void *lhs, const void *rhs)
 759 {
 760         dt_ahashent_t *lh = *((dt_ahashent_t **)lhs);
 761         dt_ahashent_t *rh = *((dt_ahashent_t **)rhs);
 762         dtrace_aggvarid_t lid, rid;
 763
 764         lid = dt_aggregate_aggvarid(lh);
 765         rid = dt_aggregate_aggvarid(rh);
 766
 767         if (lid < rid)
 768                 return (DT_LESSTHAN);
 769
 770         if (lid > rid)
 771                 return (DT_GREATERTHAN);
 772
 773         return (0);
 774 }
 775
 776 static int
 777 dt_aggregate_keycmp(const void *lhs, const void *rhs)
 778 {
 779         dt_ahashent_t *lh = *((dt_ahashent_t **)lhs);
 780         dt_ahashent_t *rh = *((dt_ahashent_t **)rhs);
 781         dtrace_aggdesc_t *lagg = lh->dtahe_data.dtada_desc;
 782         dtrace_aggdesc_t *ragg = rh->dtahe_data.dtada_desc;
 783         dtrace_recdesc_t *lrec, *rrec;
 784         char *ldata, *rdata;
 785         int rval, i, j, keypos, nrecs;
 786
 787         if ((rval = dt_aggregate_hashcmp(lhs, rhs)) != 0)
 788                 return (rval);
 789
 790         nrecs = lagg->dtagd_nrecs - 1;
 791         assert(nrecs == ragg->dtagd_nrecs - 1);
 792
 793         keypos = dt_keypos + 1 >= nrecs ? 0 : dt_keypos;
 794
 795         for (i = 1; i < nrecs; i++) {
 796                 uint64_t lval, rval;
 797                 int ndx = i + keypos;
 798
 799                 if (ndx >= nrecs)
 800                         ndx = ndx - nrecs + 1;
 801
 802                 lrec = &lagg->dtagd_rec[ndx];
 803                 rrec = &ragg->dtagd_rec[ndx];
 804
 805                 ldata = lh->dtahe_data.dtada_data + lrec->dtrd_offset;
 806                 rdata = rh->dtahe_data.dtada_data + rrec->dtrd_offset;
 807
 808                 if (lrec->dtrd_size < rrec->dtrd_size)
 809                         return (DT_LESSTHAN);
 810
 811                 if (lrec->dtrd_size > rrec->dtrd_size)
 812                         return (DT_GREATERTHAN);
 813
 814                 switch (lrec->dtrd_size) {
 815                 case sizeof (uint64_t):
 816                         /* LINTED - alignment */
 817                         lval = *((uint64_t *)ldata);
 818                         /* LINTED - alignment */
 819                         rval = *((uint64_t *)rdata);
 820                         break;
 821
 822                 case sizeof (uint32_t):
 823                         /* LINTED - alignment */
 824                         lval = *((uint32_t *)ldata);
 825                         /* LINTED - alignment */
 826                         rval = *((uint32_t *)rdata);
 827                         break;
 828
 829                 case sizeof (uint16_t):
 830                         /* LINTED - alignment */
 831                         lval = *((uint16_t *)ldata);
 832                         /* LINTED - alignment */
 833                         rval = *((uint16_t *)rdata);
 834                         break;
 835
 836                 case sizeof (uint8_t):
 837                         lval = *((uint8_t *)ldata);
 838                         rval = *((uint8_t *)rdata);
 839                         break;
 840
 841                 default:
 842                         switch (lrec->dtrd_action) {
 843                         case DTRACEACT_UMOD:
 844                         case DTRACEACT_UADDR:
 845                         case DTRACEACT_USYM:
 846                                 for (j = 0; j < 2; j++) {
 847                                         /* LINTED - alignment */
 848                                         lval = ((uint64_t *)ldata)[j];
 849                                         /* LINTED - alignment */
 850                                         rval = ((uint64_t *)rdata)[j];
 851
 852                                         if (lval < rval)
 853                                                 return (DT_LESSTHAN);
 854
 855                                         if (lval > rval)
 856                                                 return (DT_GREATERTHAN);
 857                                 }
 858
 859                                 break;
 860
 861                         default:
 862                                 for (j = 0; j < lrec->dtrd_size; j++) {
 863                                         lval = ((uint8_t *)ldata)[j];
 864                                         rval = ((uint8_t *)rdata)[j];
 865
 866                                         if (lval < rval)
 867                                                 return (DT_LESSTHAN);
 868
 869                                         if (lval > rval)
 870                                                 return (DT_GREATERTHAN);
 871                                 }
 872                         }
 873
 874                         continue;
 875                 }
 876
 877                 if (lval < rval)
 878                         return (DT_LESSTHAN);
 879
 880                 if (lval > rval)
 881                         return (DT_GREATERTHAN);
 882         }
 883
 884         return (0);
 885 }
 886
 887 static int
 888 dt_aggregate_valcmp(const void *lhs, const void *rhs)
 889 {
 890         dt_ahashent_t *lh = *((dt_ahashent_t **)lhs);
 891         dt_ahashent_t *rh = *((dt_ahashent_t **)rhs);
 892         dtrace_aggdesc_t *lagg = lh->dtahe_data.dtada_desc;
 893         dtrace_aggdesc_t *ragg = rh->dtahe_data.dtada_desc;
 894         caddr_t ldata = lh->dtahe_data.dtada_data;
 895         caddr_t rdata = rh->dtahe_data.dtada_data;
 896         dtrace_recdesc_t *lrec, *rrec;
 897         int64_t *laddr, *raddr;
 898         int rval;
 899
 900         assert(lagg->dtagd_nrecs == ragg->dtagd_nrecs);
 901
 902         lrec = &lagg->dtagd_rec[lagg->dtagd_nrecs - 1];
 903         rrec = &ragg->dtagd_rec[ragg->dtagd_nrecs - 1];
 904
 905         assert(lrec->dtrd_action == rrec->dtrd_action);
 906
 907         laddr = (int64_t *)(uintptr_t)(ldata + lrec->dtrd_offset);
 908         raddr = (int64_t *)(uintptr_t)(rdata + rrec->dtrd_offset);
 909
 910         switch (lrec->dtrd_action) {
 911         case DTRACEAGG_AVG:
 912                 rval = dt_aggregate_averagecmp(laddr, raddr);
 913                 break;
 914
 915         case DTRACEAGG_STDDEV:
 916                 rval = dt_aggregate_stddevcmp(laddr, raddr);
 917                 break;
 918
 919         case DTRACEAGG_QUANTIZE:
 920                 rval = dt_aggregate_quantizedcmp(laddr, raddr);
 921                 break;
 922
 923         case DTRACEAGG_LQUANTIZE:
 924                 rval = dt_aggregate_lquantizedcmp(laddr, raddr);
 925                 break;
 926
 927         case DTRACEAGG_LLQUANTIZE:
 928                 rval = dt_aggregate_llquantizedcmp(laddr, raddr);
 929                 break;
 930
 931         case DTRACEAGG_COUNT:
 932         case DTRACEAGG_SUM:
 933         case DTRACEAGG_MIN:
 934         case DTRACEAGG_MAX:
 935                 rval = dt_aggregate_countcmp(laddr, raddr);
 936                 break;
 937
 938         default:
 939                 assert(0);
 940         }
 941
 942         return (rval);
 943 }
 944
 945 static int
 946 dt_aggregate_valkeycmp(const void *lhs, const void *rhs)
 947 {
 948         int rval;
 949
 950         if ((rval = dt_aggregate_valcmp(lhs, rhs)) != 0)
 951                 return (rval);
 952
 953         /*
 954          * If we're here, the values for the two aggregation elements are
 955          * equal.  We already know that the key layout is the same for the two
 956          * elements; we must now compare the keys themselves as a tie-breaker.
 957          */
 958         return (dt_aggregate_keycmp(lhs, rhs));
 959 }
 960
 961 static int
 962 dt_aggregate_keyvarcmp(const void *lhs, const void *rhs)
 963 {
 964         int rval;
 965
 966         if ((rval = dt_aggregate_keycmp(lhs, rhs)) != 0)
 967                 return (rval);
 968
 969         return (dt_aggregate_varcmp(lhs, rhs));
 970 }
 971
 972 static int
 973 dt_aggregate_varkeycmp(const void *lhs, const void *rhs)
 974 {
 975         int rval;
 976
 977         if ((rval = dt_aggregate_varcmp(lhs, rhs)) != 0)
 978                 return (rval);
 979
 980         return (dt_aggregate_keycmp(lhs, rhs));
 981 }
 982
 983 static int
 984 dt_aggregate_valvarcmp(const void *lhs, const void *rhs)
 985 {
 986         int rval;
 987
 988         if ((rval = dt_aggregate_valkeycmp(lhs, rhs)) != 0)
 989                 return (rval);
 990
 991         return (dt_aggregate_varcmp(lhs, rhs));
 992 }
 993
 994 static int
 995 dt_aggregate_varvalcmp(const void *lhs, const void *rhs)
 996 {
 997         int rval;
 998
 999         if ((rval = dt_aggregate_varcmp(lhs, rhs)) != 0)
1000                 return (rval);
1001
1002         return (dt_aggregate_valkeycmp(lhs, rhs));
1003 }
1004
1005 static int
1006 dt_aggregate_keyvarrevcmp(const void *lhs, const void *rhs)
1007 {
1008         return (dt_aggregate_keyvarcmp(rhs, lhs));
1009 }
1010
1011 static int
1012 dt_aggregate_varkeyrevcmp(const void *lhs, const void *rhs)
1013 {
1014         return (dt_aggregate_varkeycmp(rhs, lhs));
1015 }
1016
1017 static int
1018 dt_aggregate_valvarrevcmp(const void *lhs, const void *rhs)
1019 {
1020         return (dt_aggregate_valvarcmp(rhs, lhs));
1021 }
1022
1023 static int
1024 dt_aggregate_varvalrevcmp(const void *lhs, const void *rhs)
1025 {
1026         return (dt_aggregate_varvalcmp(rhs, lhs));
1027 }
1028
1029 static int
1030 dt_aggregate_bundlecmp(const void *lhs, const void *rhs)
1031 {
1032         dt_ahashent_t **lh = *((dt_ahashent_t ***)lhs);
1033         dt_ahashent_t **rh = *((dt_ahashent_t ***)rhs);
1034         int i, rval;
1035
1036         if (dt_keysort) {
1037                 /*
1038                  * If we're sorting on keys, we need to scan until we find the
1039                  * last entry -- that's the representative key.  (The order of
1040                  * the bundle is values followed by key to accommodate the
1041                  * default behavior of sorting by value.)  If the keys are
1042                  * equal, we'll fall into the value comparison loop, below.
1043                  */
1044                 for (i = 0; lh[i + 1] != NULL; i++)
1045                         continue;
1046
1047                 assert(i != 0);
1048                 assert(rh[i + 1] == NULL);
1049
1050                 if ((rval = dt_aggregate_keycmp(&lh[i], &rh[i])) != 0)
1051                         return (rval);
1052         }
1053
1054         for (i = 0; ; i++) {
1055                 if (lh[i + 1] == NULL) {
1056                         /*
1057                          * All of the values are equal; if we're sorting on
1058                          * keys, then we're only here because the keys were
1059                          * found to be equal and these records are therefore
1060                          * equal.  If we're not sorting on keys, we'll use the
1061                          * key comparison from the representative key as the
1062                          * tie-breaker.
1063                          */
1064                         if (dt_keysort)
1065                                 return (0);
1066
1067                         assert(i != 0);
1068                         assert(rh[i + 1] == NULL);
1069                         return (dt_aggregate_keycmp(&lh[i], &rh[i]));
1070                 } else {
1071                         if ((rval = dt_aggregate_valcmp(&lh[i], &rh[i])) != 0)
1072                                 return (rval);
1073                 }
1074         }
1075 }
1076
1077 int
1078 dt_aggregate_go(dtrace_hdl_t *dtp)
1079 {
1080         dt_aggregate_t *agp = &dtp->dt_aggregate;
1081         dtrace_optval_t size, cpu;
1082         dtrace_bufdesc_t *buf = &agp->dtat_buf;
1083         int rval, i;
1084
1085         assert(agp->dtat_maxcpu == 0);
1086         assert(agp->dtat_ncpu == 0);
1087         assert(agp->dtat_cpus == NULL);
1088
1089         agp->dtat_maxcpu = dt_sysconf(dtp, _SC_CPUID_MAX) + 1;
1090         agp->dtat_ncpu = dt_sysconf(dtp, _SC_NPROCESSORS_MAX);
1091         agp->dtat_cpus = malloc(agp->dtat_ncpu * sizeof (processorid_t));
1092
1093         if (agp->dtat_cpus == NULL)
1094                 return (dt_set_errno(dtp, EDT_NOMEM));
1095
1096         /*
1097          * Use the aggregation buffer size as reloaded from the kernel.
1098          */
1099         size = dtp->dt_options[DTRACEOPT_AGGSIZE];
1100
1101         rval = dtrace_getopt(dtp, "aggsize", &size);
1102         assert(rval == 0);
1103
1104         if (size == 0 || size == DTRACEOPT_UNSET)
1105                 return (0);
1106
1107         buf = &agp->dtat_buf;
1108         buf->dtbd_size = size;
1109
1110         if ((buf->dtbd_data = malloc(buf->dtbd_size)) == NULL)
1111                 return (dt_set_errno(dtp, EDT_NOMEM));
1112
1113         /*
1114          * Now query for the CPUs enabled.
1115          */
1116         rval = dtrace_getopt(dtp, "cpu", &cpu);
1117         assert(rval == 0 && cpu != DTRACEOPT_UNSET);
1118
1119         if (cpu != DTRACE_CPUALL) {
1120                 assert(cpu < agp->dtat_ncpu);
1121                 agp->dtat_cpus[agp->dtat_ncpus++] = (processorid_t)cpu;
1122
1123                 return (0);
1124         }
1125
1126         agp->dtat_ncpus = 0;
1127         for (i = 0; i < agp->dtat_maxcpu; i++) {
1128                 if (dt_status(dtp, i) == -1)
1129                         continue;
1130
1131                 agp->dtat_cpus[agp->dtat_ncpus++] = i;
1132         }
1133
1134         return (0);
1135 }
1136
1137 static int
1138 dt_aggwalk_rval(dtrace_hdl_t *dtp, dt_ahashent_t *h, int rval)
1139 {
1140         dt_aggregate_t *agp = &dtp->dt_aggregate;
1141         dtrace_aggdata_t *data;
1142         dtrace_aggdesc_t *aggdesc;
1143         dtrace_recdesc_t *rec;
1144         int i;
1145
1146         switch (rval) {
1147         case DTRACE_AGGWALK_NEXT:
1148                 break;
1149
1150         case DTRACE_AGGWALK_CLEAR: {
1151                 uint32_t size, offs = 0;
1152
1153                 aggdesc = h->dtahe_data.dtada_desc;
1154                 rec = &aggdesc->dtagd_rec[aggdesc->dtagd_nrecs - 1];
1155                 size = rec->dtrd_size;
1156                 data = &h->dtahe_data;
1157
1158                 if (rec->dtrd_action == DTRACEAGG_LQUANTIZE) {
1159                         offs = sizeof (uint64_t);
1160                         size -= sizeof (uint64_t);
1161                 }
1162
1163                 bzero(&data->dtada_data[rec->dtrd_offset] + offs, size);
1164
1165                 if (data->dtada_percpu == NULL)
1166                         break;
1167
1168                 for (i = 0; i < dtp->dt_aggregate.dtat_maxcpu; i++)
1169                         bzero(data->dtada_percpu[i] + offs, size);
1170                 break;
1171         }
1172
1173         case DTRACE_AGGWALK_ERROR:
1174                 /*
1175                  * We assume that errno is already set in this case.
1176                  */
1177                 return (dt_set_errno(dtp, errno));
1178
1179         case DTRACE_AGGWALK_ABORT:
1180                 return (dt_set_errno(dtp, EDT_DIRABORT));
1181
1182         case DTRACE_AGGWALK_DENORMALIZE:
1183                 h->dtahe_data.dtada_normal = 1;
1184                 return (0);
1185
1186         case DTRACE_AGGWALK_NORMALIZE:
1187                 if (h->dtahe_data.dtada_normal == 0) {
1188                         h->dtahe_data.dtada_normal = 1;
1189                         return (dt_set_errno(dtp, EDT_BADRVAL));
1190                 }
1191
1192                 return (0);
1193
1194         case DTRACE_AGGWALK_REMOVE: {
1195                 dtrace_aggdata_t *aggdata = &h->dtahe_data;
1196                 int max_cpus = agp->dtat_maxcpu;
1197
1198                 /*
1199                  * First, remove this hash entry from its hash chain.
1200                  */
1201                 if (h->dtahe_prev != NULL) {
1202                         h->dtahe_prev->dtahe_next = h->dtahe_next;
1203                 } else {
1204                         dt_ahash_t *hash = &agp->dtat_hash;
1205                         size_t ndx = h->dtahe_hashval % hash->dtah_size;
1206
1207                         assert(hash->dtah_hash[ndx] == h);
1208                         hash->dtah_hash[ndx] = h->dtahe_next;
1209                 }
1210
1211                 if (h->dtahe_next != NULL)
1212                         h->dtahe_next->dtahe_prev = h->dtahe_prev;
1213
1214                 /*
1215                  * Now remove it from the list of all hash entries.
1216                  */
1217                 if (h->dtahe_prevall != NULL) {
1218                         h->dtahe_prevall->dtahe_nextall = h->dtahe_nextall;
1219                 } else {
1220                         dt_ahash_t *hash = &agp->dtat_hash;
1221
1222                         assert(hash->dtah_all == h);
1223                         hash->dtah_all = h->dtahe_nextall;
1224                 }
1225
1226                 if (h->dtahe_nextall != NULL)
1227                         h->dtahe_nextall->dtahe_prevall = h->dtahe_prevall;
1228
1229                 /*
1230                  * We're unlinked.  We can safely destroy the data.
1231                  */
1232                 if (aggdata->dtada_percpu != NULL) {
1233                         for (i = 0; i < max_cpus; i++)
1234                                 free(aggdata->dtada_percpu[i]);
1235                         free(aggdata->dtada_percpu);
1236                 }
1237
1238                 free(aggdata->dtada_data);
1239                 free(h);
1240
1241                 return (0);
1242         }
1243
1244         default:
1245                 return (dt_set_errno(dtp, EDT_BADRVAL));
1246         }
1247
1248         return (0);
1249 }
1250
1251 void
1252 dt_aggregate_qsort(dtrace_hdl_t *dtp, void *base, size_t nel, size_t width,
1253     int (*compar)(const void *, const void *))
1254 {
1255         int rev = dt_revsort, key = dt_keysort, keypos = dt_keypos;
1256         dtrace_optval_t keyposopt = dtp->dt_options[DTRACEOPT_AGGSORTKEYPOS];
1257
1258         dt_revsort = (dtp->dt_options[DTRACEOPT_AGGSORTREV] != DTRACEOPT_UNSET);
1259         dt_keysort = (dtp->dt_options[DTRACEOPT_AGGSORTKEY] != DTRACEOPT_UNSET);
1260
1261         if (keyposopt != DTRACEOPT_UNSET && keyposopt <= INT_MAX) {
1262                 dt_keypos = (int)keyposopt;
1263         } else {
1264                 dt_keypos = 0;
1265         }
1266
1267         if (compar == NULL) {
1268                 if (!dt_keysort) {
1269                         compar = dt_aggregate_varvalcmp;
1270                 } else {
1271                         compar = dt_aggregate_varkeycmp;
1272                 }
1273         }
1274
1275         qsort(base, nel, width, compar);
1276
1277         dt_revsort = rev;
1278         dt_keysort = key;
1279         dt_keypos = keypos;
1280 }
1281
1282 int
1283 dtrace_aggregate_walk(dtrace_hdl_t *dtp, dtrace_aggregate_f *func, void *arg)
1284 {
1285         dt_ahashent_t *h, *next;
1286         dt_ahash_t *hash = &dtp->dt_aggregate.dtat_hash;
1287
1288         for (h = hash->dtah_all; h != NULL; h = next) {
1289                 /*
1290                  * dt_aggwalk_rval() can potentially remove the current hash
1291                  * entry; we need to load the next hash entry before calling
1292                  * into it.
1293                  */
1294                 next = h->dtahe_nextall;
1295
1296                 if (dt_aggwalk_rval(dtp, h, func(&h->dtahe_data, arg)) == -1)
1297                         return (-1);
1298         }
1299
1300         return (0);
1301 }
1302
1303 static int
1304 dt_aggregate_total(dtrace_hdl_t *dtp, boolean_t clear)
1305 {
1306         dt_ahashent_t *h;
1307         dtrace_aggdata_t **total;
1308         dtrace_aggid_t max = DTRACE_AGGVARIDNONE, id;
1309         dt_aggregate_t *agp = &dtp->dt_aggregate;
1310         dt_ahash_t *hash = &agp->dtat_hash;
1311         uint32_t tflags;
1312
1313         tflags = DTRACE_A_TOTAL | DTRACE_A_HASNEGATIVES | DTRACE_A_HASPOSITIVES;
1314
1315         /*
1316          * If we need to deliver per-aggregation totals, we're going to take
1317          * three passes over the aggregate:  one to clear everything out and
1318          * determine our maximum aggregation ID, one to actually total
1319          * everything up, and a final pass to assign the totals to the
1320          * individual elements.
1321          */
1322         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1323                 dtrace_aggdata_t *aggdata = &h->dtahe_data;
1324
1325                 if ((id = dt_aggregate_aggvarid(h)) > max)
1326                         max = id;
1327
1328                 aggdata->dtada_total = 0;
1329                 aggdata->dtada_flags &= ~tflags;
1330         }
1331
1332         if (clear || max == DTRACE_AGGVARIDNONE)
1333                 return (0);
1334
1335         total = dt_zalloc(dtp, (max + 1) * sizeof (dtrace_aggdata_t *));
1336
1337         if (total == NULL)
1338                 return (-1);
1339
1340         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1341                 dtrace_aggdata_t *aggdata = &h->dtahe_data;
1342                 dtrace_aggdesc_t *agg = aggdata->dtada_desc;
1343                 dtrace_recdesc_t *rec;
1344                 caddr_t data;
1345                 int64_t val, *addr;
1346
1347                 rec = &agg->dtagd_rec[agg->dtagd_nrecs - 1];
1348                 data = aggdata->dtada_data;
1349                 addr = (int64_t *)(uintptr_t)(data + rec->dtrd_offset);
1350
1351                 switch (rec->dtrd_action) {
1352                 case DTRACEAGG_STDDEV:
1353                         val = dt_stddev((uint64_t *)addr, 1);
1354                         break;
1355
1356                 case DTRACEAGG_SUM:
1357                 case DTRACEAGG_COUNT:
1358                         val = *addr;
1359                         break;
1360
1361                 case DTRACEAGG_AVG:
1362                         val = addr[0] ? (addr[1] / addr[0]) : 0;
1363                         break;
1364
1365                 default:
1366                         continue;
1367                 }
1368
1369                 if (total[agg->dtagd_varid] == NULL) {
1370                         total[agg->dtagd_varid] = aggdata;
1371                         aggdata->dtada_flags |= DTRACE_A_TOTAL;
1372                 } else {
1373                         aggdata = total[agg->dtagd_varid];
1374                 }
1375
1376                 if (val > 0)
1377                         aggdata->dtada_flags |= DTRACE_A_HASPOSITIVES;
1378
1379                 if (val < 0) {
1380                         aggdata->dtada_flags |= DTRACE_A_HASNEGATIVES;
1381                         val = -val;
1382                 }
1383
1384                 if (dtp->dt_options[DTRACEOPT_AGGZOOM] != DTRACEOPT_UNSET) {
1385                         val = (int64_t)((long double)val *
1386                             (1 / DTRACE_AGGZOOM_MAX));
1387
1388                         if (val > aggdata->dtada_total)
1389                                 aggdata->dtada_total = val;
1390                 } else {
1391                         aggdata->dtada_total += val;
1392                 }
1393         }
1394
1395         /*
1396          * And now one final pass to set everyone's total.
1397          */
1398         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1399                 dtrace_aggdata_t *aggdata = &h->dtahe_data, *t;
1400                 dtrace_aggdesc_t *agg = aggdata->dtada_desc;
1401
1402                 if ((t = total[agg->dtagd_varid]) == NULL || aggdata == t)
1403                         continue;
1404
1405                 aggdata->dtada_total = t->dtada_total;
1406                 aggdata->dtada_flags |= (t->dtada_flags & tflags);
1407         }
1408
1409         dt_free(dtp, total);
1410
1411         return (0);
1412 }
1413
1414 static int
1415 dt_aggregate_minmaxbin(dtrace_hdl_t *dtp, boolean_t clear)
1416 {
1417         dt_ahashent_t *h;
1418         dtrace_aggdata_t **minmax;
1419         dtrace_aggid_t max = DTRACE_AGGVARIDNONE, id;
1420         dt_aggregate_t *agp = &dtp->dt_aggregate;
1421         dt_ahash_t *hash = &agp->dtat_hash;
1422
1423         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1424                 dtrace_aggdata_t *aggdata = &h->dtahe_data;
1425
1426                 if ((id = dt_aggregate_aggvarid(h)) > max)
1427                         max = id;
1428
1429                 aggdata->dtada_minbin = 0;
1430                 aggdata->dtada_maxbin = 0;
1431                 aggdata->dtada_flags &= ~DTRACE_A_MINMAXBIN;
1432         }
1433
1434         if (clear || max == DTRACE_AGGVARIDNONE)
1435                 return (0);
1436
1437         minmax = dt_zalloc(dtp, (max + 1) * sizeof (dtrace_aggdata_t *));
1438
1439         if (minmax == NULL)
1440                 return (-1);
1441
1442         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1443                 dtrace_aggdata_t *aggdata = &h->dtahe_data;
1444                 dtrace_aggdesc_t *agg = aggdata->dtada_desc;
1445                 dtrace_recdesc_t *rec;
1446                 caddr_t data;
1447                 int64_t *addr;
1448                 int minbin = -1, maxbin = -1, i;
1449                 int start = 0, size;
1450
1451                 rec = &agg->dtagd_rec[agg->dtagd_nrecs - 1];
1452                 size = rec->dtrd_size / sizeof (int64_t);
1453                 data = aggdata->dtada_data;
1454                 addr = (int64_t *)(uintptr_t)(data + rec->dtrd_offset);
1455
1456                 switch (rec->dtrd_action) {
1457                 case DTRACEAGG_LQUANTIZE:
1458                         /*
1459                          * For lquantize(), we always display the entire range
1460                          * of the aggregation when aggpack is set.
1461                          */
1462                         start = 1;
1463                         minbin = start;
1464                         maxbin = size - 1 - start;
1465                         break;
1466
1467                 case DTRACEAGG_QUANTIZE:
1468                         for (i = start; i < size; i++) {
1469                                 if (!addr[i])
1470                                         continue;
1471
1472                                 if (minbin == -1)
1473                                         minbin = i - start;
1474
1475                                 maxbin = i - start;
1476                         }
1477
1478                         if (minbin == -1) {
1479                                 /*
1480                                  * If we have no data (e.g., due to a clear()
1481                                  * or negative increments), we'll use the
1482                                  * zero bucket as both our min and max.
1483                                  */
1484                                 minbin = maxbin = DTRACE_QUANTIZE_ZEROBUCKET;
1485                         }
1486
1487                         break;
1488
1489                 default:
1490                         continue;
1491                 }
1492
1493                 if (minmax[agg->dtagd_varid] == NULL) {
1494                         minmax[agg->dtagd_varid] = aggdata;
1495                         aggdata->dtada_flags |= DTRACE_A_MINMAXBIN;
1496                         aggdata->dtada_minbin = minbin;
1497                         aggdata->dtada_maxbin = maxbin;
1498                         continue;
1499                 }
1500
1501                 if (minbin < minmax[agg->dtagd_varid]->dtada_minbin)
1502                         minmax[agg->dtagd_varid]->dtada_minbin = minbin;
1503
1504                 if (maxbin > minmax[agg->dtagd_varid]->dtada_maxbin)
1505                         minmax[agg->dtagd_varid]->dtada_maxbin = maxbin;
1506         }
1507
1508         /*
1509          * And now one final pass to set everyone's minbin and maxbin.
1510          */
1511         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1512                 dtrace_aggdata_t *aggdata = &h->dtahe_data, *mm;
1513                 dtrace_aggdesc_t *agg = aggdata->dtada_desc;
1514
1515                 if ((mm = minmax[agg->dtagd_varid]) == NULL || aggdata == mm)
1516                         continue;
1517
1518                 aggdata->dtada_minbin = mm->dtada_minbin;
1519                 aggdata->dtada_maxbin = mm->dtada_maxbin;
1520                 aggdata->dtada_flags |= DTRACE_A_MINMAXBIN;
1521         }
1522
1523         dt_free(dtp, minmax);
1524
1525         return (0);
1526 }
1527
1528 static int
1529 dt_aggregate_walk_sorted(dtrace_hdl_t *dtp,
1530     dtrace_aggregate_f *func, void *arg,
1531     int (*sfunc)(const void *, const void *))
1532 {
1533         dt_aggregate_t *agp = &dtp->dt_aggregate;
1534         dt_ahashent_t *h, **sorted;
1535         dt_ahash_t *hash = &agp->dtat_hash;
1536         size_t i, nentries = 0;
1537         int rval = -1;
1538
1539         agp->dtat_flags &= ~(DTRACE_A_TOTAL | DTRACE_A_MINMAXBIN);
1540
1541         if (dtp->dt_options[DTRACEOPT_AGGHIST] != DTRACEOPT_UNSET) {
1542                 agp->dtat_flags |= DTRACE_A_TOTAL;
1543
1544                 if (dt_aggregate_total(dtp, B_FALSE) != 0)
1545                         return (-1);
1546         }
1547
1548         if (dtp->dt_options[DTRACEOPT_AGGPACK] != DTRACEOPT_UNSET) {
1549                 agp->dtat_flags |= DTRACE_A_MINMAXBIN;
1550
1551                 if (dt_aggregate_minmaxbin(dtp, B_FALSE) != 0)
1552                         return (-1);
1553         }
1554
1555         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall)
1556                 nentries++;
1557
1558         sorted = dt_alloc(dtp, nentries * sizeof (dt_ahashent_t *));
1559
1560         if (sorted == NULL)
1561                 goto out;
1562
1563         for (h = hash->dtah_all, i = 0; h != NULL; h = h->dtahe_nextall)
1564                 sorted[i++] = h;
1565
1566         (void) pthread_mutex_lock(&dt_qsort_lock);
1567
1568         if (sfunc == NULL) {
1569                 dt_aggregate_qsort(dtp, sorted, nentries,
1570                     sizeof (dt_ahashent_t *), NULL);
1571         } else {
1572                 /*
1573                  * If we've been explicitly passed a sorting function,
1574                  * we'll use that -- ignoring the values of the "aggsortrev",
1575                  * "aggsortkey" and "aggsortkeypos" options.
1576                  */
1577                 qsort(sorted, nentries, sizeof (dt_ahashent_t *), sfunc);
1578         }
1579
1580         (void) pthread_mutex_unlock(&dt_qsort_lock);
1581
1582         for (i = 0; i < nentries; i++) {
1583                 h = sorted[i];
1584
1585                 if (dt_aggwalk_rval(dtp, h, func(&h->dtahe_data, arg)) == -1)
1586                         goto out;
1587         }
1588
1589         rval = 0;
1590 out:
1591         if (agp->dtat_flags & DTRACE_A_TOTAL)
1592                 (void) dt_aggregate_total(dtp, B_TRUE);
1593
1594         if (agp->dtat_flags & DTRACE_A_MINMAXBIN)
1595                 (void) dt_aggregate_minmaxbin(dtp, B_TRUE);
1596
1597         dt_free(dtp, sorted);
1598         return (rval);
1599 }
1600
1601 int
1602 dtrace_aggregate_walk_sorted(dtrace_hdl_t *dtp,
1603     dtrace_aggregate_f *func, void *arg)
1604 {
1605         return (dt_aggregate_walk_sorted(dtp, func, arg, NULL));
1606 }
1607
1608 int
1609 dtrace_aggregate_walk_keysorted(dtrace_hdl_t *dtp,
1610     dtrace_aggregate_f *func, void *arg)
1611 {
1612         return (dt_aggregate_walk_sorted(dtp, func,
1613             arg, dt_aggregate_varkeycmp));
1614 }
1615
1616 int
1617 dtrace_aggregate_walk_valsorted(dtrace_hdl_t *dtp,
1618     dtrace_aggregate_f *func, void *arg)
1619 {
1620         return (dt_aggregate_walk_sorted(dtp, func,
1621             arg, dt_aggregate_varvalcmp));
1622 }
1623
1624 int
1625 dtrace_aggregate_walk_keyvarsorted(dtrace_hdl_t *dtp,
1626     dtrace_aggregate_f *func, void *arg)
1627 {
1628         return (dt_aggregate_walk_sorted(dtp, func,
1629             arg, dt_aggregate_keyvarcmp));
1630 }
1631
1632 int
1633 dtrace_aggregate_walk_valvarsorted(dtrace_hdl_t *dtp,
1634     dtrace_aggregate_f *func, void *arg)
1635 {
1636         return (dt_aggregate_walk_sorted(dtp, func,
1637             arg, dt_aggregate_valvarcmp));
1638 }
1639
1640 int
1641 dtrace_aggregate_walk_keyrevsorted(dtrace_hdl_t *dtp,
1642     dtrace_aggregate_f *func, void *arg)
1643 {
1644         return (dt_aggregate_walk_sorted(dtp, func,
1645             arg, dt_aggregate_varkeyrevcmp));
1646 }
1647
1648 int
1649 dtrace_aggregate_walk_valrevsorted(dtrace_hdl_t *dtp,
1650     dtrace_aggregate_f *func, void *arg)
1651 {
1652         return (dt_aggregate_walk_sorted(dtp, func,
1653             arg, dt_aggregate_varvalrevcmp));
1654 }
1655
1656 int
1657 dtrace_aggregate_walk_keyvarrevsorted(dtrace_hdl_t *dtp,
1658     dtrace_aggregate_f *func, void *arg)
1659 {
1660         return (dt_aggregate_walk_sorted(dtp, func,
1661             arg, dt_aggregate_keyvarrevcmp));
1662 }
1663
1664 int
1665 dtrace_aggregate_walk_valvarrevsorted(dtrace_hdl_t *dtp,
1666     dtrace_aggregate_f *func, void *arg)
1667 {
1668         return (dt_aggregate_walk_sorted(dtp, func,
1669             arg, dt_aggregate_valvarrevcmp));
1670 }
1671
1672 int
1673 dtrace_aggregate_walk_joined(dtrace_hdl_t *dtp, dtrace_aggvarid_t *aggvars,
1674     int naggvars, dtrace_aggregate_walk_joined_f *func, void *arg)
1675 {
1676         dt_aggregate_t *agp = &dtp->dt_aggregate;
1677         dt_ahashent_t *h, **sorted = NULL, ***bundle, **nbundle;
1678         const dtrace_aggdata_t **data;
1679         dt_ahashent_t *zaggdata = NULL;
1680         dt_ahash_t *hash = &agp->dtat_hash;
1681         size_t nentries = 0, nbundles = 0, start, zsize = 0, bundlesize;
1682         dtrace_aggvarid_t max = 0, aggvar;
1683         int rval = -1, *map, *remap = NULL;
1684         int i, j;
1685         dtrace_optval_t sortpos = dtp->dt_options[DTRACEOPT_AGGSORTPOS];
1686
1687         /*
1688          * If the sorting position is greater than the number of aggregation
1689          * variable IDs, we silently set it to 0.
1690          */
1691         if (sortpos == DTRACEOPT_UNSET || sortpos >= naggvars)
1692                 sortpos = 0;
1693
1694         /*
1695          * First we need to translate the specified aggregation variable IDs
1696          * into a linear map that will allow us to translate an aggregation
1697          * variable ID into its position in the specified aggvars.
1698          */
1699         for (i = 0; i < naggvars; i++) {
1700                 if (aggvars[i] == DTRACE_AGGVARIDNONE || aggvars[i] < 0)
1701                         return (dt_set_errno(dtp, EDT_BADAGGVAR));
1702
1703                 if (aggvars[i] > max)
1704                         max = aggvars[i];
1705         }
1706
1707         if ((map = dt_zalloc(dtp, (max + 1) * sizeof (int))) == NULL)
1708                 return (-1);
1709
1710         zaggdata = dt_zalloc(dtp, naggvars * sizeof (dt_ahashent_t));
1711
1712         if (zaggdata == NULL)
1713                 goto out;
1714
1715         for (i = 0; i < naggvars; i++) {
1716                 int ndx = i + sortpos;
1717
1718                 if (ndx >= naggvars)
1719                         ndx -= naggvars;
1720
1721                 aggvar = aggvars[ndx];
1722                 assert(aggvar <= max);
1723
1724                 if (map[aggvar]) {
1725                         /*
1726                          * We have an aggregation variable that is present
1727                          * more than once in the array of aggregation
1728                          * variables.  While it's unclear why one might want
1729                          * to do this, it's legal.  To support this construct,
1730                          * we will allocate a remap that will indicate the
1731                          * position from which this aggregation variable
1732                          * should be pulled.  (That is, where the remap will
1733                          * map from one position to another.)
1734                          */
1735                         if (remap == NULL) {
1736                                 remap = dt_zalloc(dtp, naggvars * sizeof (int));
1737
1738                                 if (remap == NULL)
1739                                         goto out;
1740                         }
1741
1742                         /*
1743                          * Given that the variable is already present, assert
1744                          * that following through the mapping and adjusting
1745                          * for the sort position yields the same aggregation
1746                          * variable ID.
1747                          */
1748                         assert(aggvars[(map[aggvar] - 1 + sortpos) %
1749                             naggvars] == aggvars[ndx]);
1750
1751                         remap[i] = map[aggvar];
1752                         continue;
1753                 }
1754
1755                 map[aggvar] = i + 1;
1756         }
1757
1758         /*
1759          * We need to take two passes over the data to size our allocation, so
1760          * we'll use the first pass to also fill in the zero-filled data to be
1761          * used to properly format a zero-valued aggregation.
1762          */
1763         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1764                 dtrace_aggvarid_t id;
1765                 int ndx;
1766
1767                 if ((id = dt_aggregate_aggvarid(h)) > max || !(ndx = map[id]))
1768                         continue;
1769
1770                 if (zaggdata[ndx - 1].dtahe_size == 0) {
1771                         zaggdata[ndx - 1].dtahe_size = h->dtahe_size;
1772                         zaggdata[ndx - 1].dtahe_data = h->dtahe_data;
1773                 }
1774
1775                 nentries++;
1776         }
1777
1778         if (nentries == 0) {
1779                 /*
1780                  * We couldn't find any entries; there is nothing else to do.
1781                  */
1782                 rval = 0;
1783                 goto out;
1784         }
1785
1786         /*
1787          * Before we sort the data, we're going to look for any holes in our
1788          * zero-filled data.  This will occur if an aggregation variable that
1789          * we are being asked to print has not yet been assigned the result of
1790          * any aggregating action for _any_ tuple.  The issue becomes that we
1791          * would like a zero value to be printed for all columns for this
1792          * aggregation, but without any record description, we don't know the
1793          * aggregating action that corresponds to the aggregation variable.  To
1794          * try to find a match, we're simply going to lookup aggregation IDs
1795          * (which are guaranteed to be contiguous and to start from 1), looking
1796          * for the specified aggregation variable ID.  If we find a match,
1797          * we'll use that.  If we iterate over all aggregation IDs and don't
1798          * find a match, then we must be an anonymous enabling.  (Anonymous
1799          * enablings can't currently derive either aggregation variable IDs or
1800          * aggregation variable names given only an aggregation ID.)  In this
1801          * obscure case (anonymous enabling, multiple aggregation printa() with
1802          * some aggregations not represented for any tuple), our defined
1803          * behavior is that the zero will be printed in the format of the first
1804          * aggregation variable that contains any non-zero value.
1805          */
1806         for (i = 0; i < naggvars; i++) {
1807                 if (zaggdata[i].dtahe_size == 0) {
1808                         dtrace_aggvarid_t aggvar;
1809
1810                         aggvar = aggvars[(i - sortpos + naggvars) % naggvars];
1811                         assert(zaggdata[i].dtahe_data.dtada_data == NULL);
1812
1813                         for (j = DTRACE_AGGIDNONE + 1; ; j++) {
1814                                 dtrace_aggdesc_t *agg;
1815                                 dtrace_aggdata_t *aggdata;
1816
1817                                 if (dt_aggid_lookup(dtp, j, &agg) != 0)
1818                                         break;
1819
1820                                 if (agg->dtagd_varid != aggvar)
1821                                         continue;
1822
1823                                 /*
1824                                  * We have our description -- now we need to
1825                                  * cons up the zaggdata entry for it.
1826                                  */
1827                                 aggdata = &zaggdata[i].dtahe_data;
1828                                 aggdata->dtada_size = agg->dtagd_size;
1829                                 aggdata->dtada_desc = agg;
1830                                 aggdata->dtada_handle = dtp;
1831                                 (void) dt_epid_lookup(dtp, agg->dtagd_epid,
1832                                     &aggdata->dtada_edesc,
1833                                     &aggdata->dtada_pdesc);
1834                                 aggdata->dtada_normal = 1;
1835                                 zaggdata[i].dtahe_hashval = 0;
1836                                 zaggdata[i].dtahe_size = agg->dtagd_size;
1837                                 break;
1838                         }
1839
1840                         if (zaggdata[i].dtahe_size == 0) {
1841                                 caddr_t data;
1842
1843                                 /*
1844                                  * We couldn't find this aggregation, meaning
1845                                  * that we have never seen it before for any
1846                                  * tuple _and_ this is an anonymous enabling.
1847                                  * That is, we're in the obscure case outlined
1848                                  * above.  In this case, our defined behavior
1849                                  * is to format the data in the format of the
1850                                  * first non-zero aggregation -- of which, of
1851                                  * course, we know there to be at least one
1852                                  * (or nentries would have been zero).
1853                                  */
1854                                 for (j = 0; j < naggvars; j++) {
1855                                         if (zaggdata[j].dtahe_size != 0)
1856                                                 break;
1857                                 }
1858
1859                                 assert(j < naggvars);
1860                                 zaggdata[i] = zaggdata[j];
1861
1862                                 data = zaggdata[i].dtahe_data.dtada_data;
1863                                 assert(data != NULL);
1864                         }
1865                 }
1866         }
1867
1868         /*
1869          * Now we need to allocate our zero-filled data for use for
1870          * aggregations that don't have a value corresponding to a given key.
1871          */
1872         for (i = 0; i < naggvars; i++) {
1873                 dtrace_aggdata_t *aggdata = &zaggdata[i].dtahe_data;
1874                 dtrace_aggdesc_t *aggdesc = aggdata->dtada_desc;
1875                 dtrace_recdesc_t *rec;
1876                 uint64_t larg;
1877                 caddr_t zdata;
1878
1879                 zsize = zaggdata[i].dtahe_size;
1880                 assert(zsize != 0);
1881
1882                 if ((zdata = dt_zalloc(dtp, zsize)) == NULL) {
1883                         /*
1884                          * If we failed to allocated some zero-filled data, we
1885                          * need to zero out the remaining dtada_data pointers
1886                          * to prevent the wrong data from being freed below.
1887                          */
1888                         for (j = i; j < naggvars; j++)
1889                                 zaggdata[j].dtahe_data.dtada_data = NULL;
1890                         goto out;
1891                 }
1892
1893                 aggvar = aggvars[(i - sortpos + naggvars) % naggvars];
1894
1895                 /*
1896                  * First, the easy bit.  To maintain compatibility with
1897                  * consumers that pull the compiler-generated ID out of the
1898                  * data, we put that ID at the top of the zero-filled data.
1899                  */
1900                 rec = &aggdesc->dtagd_rec[0];
1901                 /* LINTED - alignment */
1902                 *((dtrace_aggvarid_t *)(zdata + rec->dtrd_offset)) = aggvar;
1903
1904                 rec = &aggdesc->dtagd_rec[aggdesc->dtagd_nrecs - 1];
1905
1906                 /*
1907                  * Now for the more complicated part.  If (and only if) this
1908                  * is an lquantize() aggregating action, zero-filled data is
1909                  * not equivalent to an empty record:  we must also get the
1910                  * parameters for the lquantize().
1911                  */
1912                 if (rec->dtrd_action == DTRACEAGG_LQUANTIZE) {
1913                         if (aggdata->dtada_data != NULL) {
1914                                 /*
1915                                  * The easier case here is if we actually have
1916                                  * some prototype data -- in which case we
1917                                  * manually dig it out of the aggregation
1918                                  * record.
1919                                  */
1920                                 /* LINTED - alignment */
1921                                 larg = *((uint64_t *)(aggdata->dtada_data +
1922                                     rec->dtrd_offset));
1923                         } else {
1924                                 /*
1925                                  * We don't have any prototype data.  As a
1926                                  * result, we know that we _do_ have the
1927                                  * compiler-generated information.  (If this
1928                                  * were an anonymous enabling, all of our
1929                                  * zero-filled data would have prototype data
1930                                  * -- either directly or indirectly.) So as
1931                                  * gross as it is, we'll grovel around in the
1932                                  * compiler-generated information to find the
1933                                  * lquantize() parameters.
1934                                  */
1935                                 dtrace_stmtdesc_t *sdp;
1936                                 dt_ident_t *aid;
1937                                 dt_idsig_t *isp;
1938
1939                                 sdp = (dtrace_stmtdesc_t *)(uintptr_t)
1940                                     aggdesc->dtagd_rec[0].dtrd_uarg;
1941                                 aid = sdp->dtsd_aggdata;
1942                                 isp = (dt_idsig_t *)aid->di_data;
1943                                 assert(isp->dis_auxinfo != 0);
1944                                 larg = isp->dis_auxinfo;
1945                         }
1946
1947                         /* LINTED - alignment */
1948                         *((uint64_t *)(zdata + rec->dtrd_offset)) = larg;
1949                 }
1950
1951                 aggdata->dtada_data = zdata;
1952         }
1953
1954         /*
1955          * Now that we've dealt with setting up our zero-filled data, we can
1956          * allocate our sorted array, and take another pass over the data to
1957          * fill it.
1958          */
1959         sorted = dt_alloc(dtp, nentries * sizeof (dt_ahashent_t *));
1960
1961         if (sorted == NULL)
1962                 goto out;
1963
1964         for (h = hash->dtah_all, i = 0; h != NULL; h = h->dtahe_nextall) {
1965                 dtrace_aggvarid_t id;
1966
1967                 if ((id = dt_aggregate_aggvarid(h)) > max || !map[id])
1968                         continue;
1969
1970                 sorted[i++] = h;
1971         }
1972
1973         assert(i == nentries);
1974
1975         /*
1976          * We've loaded our array; now we need to sort by value to allow us
1977          * to create bundles of like value.  We're going to acquire the
1978          * dt_qsort_lock here, and hold it across all of our subsequent
1979          * comparison and sorting.
1980          */
1981         (void) pthread_mutex_lock(&dt_qsort_lock);
1982
1983         qsort(sorted, nentries, sizeof (dt_ahashent_t *),
1984             dt_aggregate_keyvarcmp);
1985
1986         /*
1987          * Now we need to go through and create bundles.  Because the number
1988          * of bundles is bounded by the size of the sorted array, we're going
1989          * to reuse the underlying storage.  And note that "bundle" is an
1990          * array of pointers to arrays of pointers to dt_ahashent_t -- making
1991          * its type (regrettably) "dt_ahashent_t ***".  (Regrettable because
1992          * '*' -- like '_' and 'X' -- should never appear in triplicate in
1993          * an ideal world.)
1994          */
1995         bundle = (dt_ahashent_t ***)sorted;
1996
1997         for (i = 1, start = 0; i <= nentries; i++) {
1998                 if (i < nentries &&
1999                     dt_aggregate_keycmp(&sorted[i], &sorted[i - 1]) == 0)
2000                         continue;
2001
2002                 /*
2003                  * We have a bundle boundary.  Everything from start to
2004                  * (i - 1) belongs in one bundle.
2005                  */
2006                 assert(i - start <= naggvars);
2007                 bundlesize = (naggvars + 2) * sizeof (dt_ahashent_t *);
2008
2009                 if ((nbundle = dt_zalloc(dtp, bundlesize)) == NULL) {
2010                         (void) pthread_mutex_unlock(&dt_qsort_lock);
2011                         goto out;
2012                 }
2013
2014                 for (j = start; j < i; j++) {
2015                         dtrace_aggvarid_t id = dt_aggregate_aggvarid(sorted[j]);
2016
2017                         assert(id <= max);
2018                         assert(map[id] != 0);
2019                         assert(map[id] - 1 < naggvars);
2020                         assert(nbundle[map[id] - 1] == NULL);
2021                         nbundle[map[id] - 1] = sorted[j];
2022
2023                         if (nbundle[naggvars] == NULL)
2024                                 nbundle[naggvars] = sorted[j];
2025                 }
2026
2027                 for (j = 0; j < naggvars; j++) {
2028                         if (nbundle[j] != NULL)
2029                                 continue;
2030
2031                         /*
2032                          * Before we assume that this aggregation variable
2033                          * isn't present (and fall back to using the
2034                          * zero-filled data allocated earlier), check the
2035                          * remap.  If we have a remapping, we'll drop it in
2036                          * here.  Note that we might be remapping an
2037                          * aggregation variable that isn't present for this
2038                          * key; in this case, the aggregation data that we
2039                          * copy will point to the zeroed data.
2040                          */
2041                         if (remap != NULL && remap[j]) {
2042                                 assert(remap[j] - 1 < j);
2043                                 assert(nbundle[remap[j] - 1] != NULL);
2044                                 nbundle[j] = nbundle[remap[j] - 1];
2045                         } else {
2046                                 nbundle[j] = &zaggdata[j];
2047                         }
2048                 }
2049
2050                 bundle[nbundles++] = nbundle;
2051                 start = i;
2052         }
2053
2054         /*
2055          * Now we need to re-sort based on the first value.
2056          */
2057         dt_aggregate_qsort(dtp, bundle, nbundles, sizeof (dt_ahashent_t **),
2058             dt_aggregate_bundlecmp);
2059
2060         (void) pthread_mutex_unlock(&dt_qsort_lock);
2061
2062         /*
2063          * We're done!  Now we just need to go back over the sorted bundles,
2064          * calling the function.
2065          */
2066         data = alloca((naggvars + 1) * sizeof (dtrace_aggdata_t *));
2067
2068         for (i = 0; i < nbundles; i++) {
2069                 for (j = 0; j < naggvars; j++)
2070                         data[j + 1] = NULL;
2071
2072                 for (j = 0; j < naggvars; j++) {
2073                         int ndx = j - sortpos;
2074
2075                         if (ndx < 0)
2076                                 ndx += naggvars;
2077
2078                         assert(bundle[i][ndx] != NULL);
2079                         data[j + 1] = &bundle[i][ndx]->dtahe_data;
2080                 }
2081
2082                 for (j = 0; j < naggvars; j++)
2083                         assert(data[j + 1] != NULL);
2084
2085                 /*
2086                  * The representative key is the last element in the bundle.
2087                  * Assert that we have one, and then set it to be the first
2088                  * element of data.
2089                  */
2090                 assert(bundle[i][j] != NULL);
2091                 data[0] = &bundle[i][j]->dtahe_data;
2092
2093                 if ((rval = func(data, naggvars + 1, arg)) == -1)
2094                         goto out;
2095         }
2096
2097         rval = 0;
2098 out:
2099         for (i = 0; i < nbundles; i++)
2100                 dt_free(dtp, bundle[i]);
2101
2102         if (zaggdata != NULL) {
2103                 for (i = 0; i < naggvars; i++)
2104                         dt_free(dtp, zaggdata[i].dtahe_data.dtada_data);
2105         }
2106
2107         dt_free(dtp, zaggdata);
2108         dt_free(dtp, sorted);
2109         dt_free(dtp, remap);
2110         dt_free(dtp, map);
2111
2112         return (rval);
2113 }
2114
2115 int
2116 dtrace_aggregate_print(dtrace_hdl_t *dtp, FILE *fp,
2117     dtrace_aggregate_walk_f *func)
2118 {
2119         dt_print_aggdata_t pd;
2120
2121         bzero(&pd, sizeof (pd));
2122
2123         pd.dtpa_dtp = dtp;
2124         pd.dtpa_fp = fp;
2125         pd.dtpa_allunprint = 1;
2126
2127         if (func == NULL)
2128                 func = dtrace_aggregate_walk_sorted;
2129
2130         if ((*func)(dtp, dt_print_agg, &pd) == -1)
2131                 return (dt_set_errno(dtp, dtp->dt_errno));
2132
2133         return (0);
2134 }
2135
2136 void
2137 dtrace_aggregate_clear(dtrace_hdl_t *dtp)
2138 {
2139         dt_aggregate_t *agp = &dtp->dt_aggregate;
2140         dt_ahash_t *hash = &agp->dtat_hash;
2141         dt_ahashent_t *h;
2142         dtrace_aggdata_t *data;
2143         dtrace_aggdesc_t *aggdesc;
2144         dtrace_recdesc_t *rec;
2145         int i, max_cpus = agp->dtat_maxcpu;
2146
2147         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
2148                 aggdesc = h->dtahe_data.dtada_desc;
2149                 rec = &aggdesc->dtagd_rec[aggdesc->dtagd_nrecs - 1];
2150                 data = &h->dtahe_data;
2151
2152                 bzero(&data->dtada_data[rec->dtrd_offset], rec->dtrd_size);
2153
2154                 if (data->dtada_percpu == NULL)
2155                         continue;
2156
2157                 for (i = 0; i < max_cpus; i++)
2158                         bzero(data->dtada_percpu[i], rec->dtrd_size);
2159         }
2160 }
2161
2162 void
2163 dt_aggregate_destroy(dtrace_hdl_t *dtp)
2164 {
2165         dt_aggregate_t *agp = &dtp->dt_aggregate;
2166         dt_ahash_t *hash = &agp->dtat_hash;
2167         dt_ahashent_t *h, *next;
2168         dtrace_aggdata_t *aggdata;
2169         int i, max_cpus = agp->dtat_maxcpu;
2170
2171         if (hash->dtah_hash == NULL) {
2172                 assert(hash->dtah_all == NULL);
2173         } else {
2174                 free(hash->dtah_hash);
2175
2176                 for (h = hash->dtah_all; h != NULL; h = next) {
2177                         next = h->dtahe_nextall;
2178
2179                         aggdata = &h->dtahe_data;
2180
2181                         if (aggdata->dtada_percpu != NULL) {
2182                                 for (i = 0; i < max_cpus; i++)
2183                                         free(aggdata->dtada_percpu[i]);
2184                                 free(aggdata->dtada_percpu);
2185                         }
2186
2187                         free(aggdata->dtada_data);
2188                         free(h);
2189                 }
2190
2191                 hash->dtah_hash = NULL;
2192                 hash->dtah_all = NULL;
2193                 hash->dtah_size = 0;
2194         }
2195
2196         free(agp->dtat_buf.dtbd_data);
2197         free(agp->dtat_cpus);
2198 }