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) 2011, 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_walk_sorted(dtrace_hdl_t *dtp,
1305     dtrace_aggregate_f *func, void *arg,
1306     int (*sfunc)(const void *, const void *))
1307 {
1308         dt_aggregate_t *agp = &dtp->dt_aggregate;
1309         dt_ahashent_t *h, **sorted;
1310         dt_ahash_t *hash = &agp->dtat_hash;
1311         size_t i, nentries = 0;
1312
1313         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall)
1314                 nentries++;
1315
1316         sorted = dt_alloc(dtp, nentries * sizeof (dt_ahashent_t *));
1317
1318         if (sorted == NULL)
1319                 return (-1);
1320
1321         for (h = hash->dtah_all, i = 0; h != NULL; h = h->dtahe_nextall)
1322                 sorted[i++] = h;
1323
1324         (void) pthread_mutex_lock(&dt_qsort_lock);
1325
1326         if (sfunc == NULL) {
1327                 dt_aggregate_qsort(dtp, sorted, nentries,
1328                     sizeof (dt_ahashent_t *), NULL);
1329         } else {
1330                 /*
1331                  * If we've been explicitly passed a sorting function,
1332                  * we'll use that -- ignoring the values of the "aggsortrev",
1333                  * "aggsortkey" and "aggsortkeypos" options.
1334                  */
1335                 qsort(sorted, nentries, sizeof (dt_ahashent_t *), sfunc);
1336         }
1337
1338         (void) pthread_mutex_unlock(&dt_qsort_lock);
1339
1340         for (i = 0; i < nentries; i++) {
1341                 h = sorted[i];
1342
1343                 if (dt_aggwalk_rval(dtp, h, func(&h->dtahe_data, arg)) == -1) {
1344                         dt_free(dtp, sorted);
1345                         return (-1);
1346                 }
1347         }
1348
1349         dt_free(dtp, sorted);
1350         return (0);
1351 }
1352
1353 int
1354 dtrace_aggregate_walk_sorted(dtrace_hdl_t *dtp,
1355     dtrace_aggregate_f *func, void *arg)
1356 {
1357         return (dt_aggregate_walk_sorted(dtp, func, arg, NULL));
1358 }
1359
1360 int
1361 dtrace_aggregate_walk_keysorted(dtrace_hdl_t *dtp,
1362     dtrace_aggregate_f *func, void *arg)
1363 {
1364         return (dt_aggregate_walk_sorted(dtp, func,
1365             arg, dt_aggregate_varkeycmp));
1366 }
1367
1368 int
1369 dtrace_aggregate_walk_valsorted(dtrace_hdl_t *dtp,
1370     dtrace_aggregate_f *func, void *arg)
1371 {
1372         return (dt_aggregate_walk_sorted(dtp, func,
1373             arg, dt_aggregate_varvalcmp));
1374 }
1375
1376 int
1377 dtrace_aggregate_walk_keyvarsorted(dtrace_hdl_t *dtp,
1378     dtrace_aggregate_f *func, void *arg)
1379 {
1380         return (dt_aggregate_walk_sorted(dtp, func,
1381             arg, dt_aggregate_keyvarcmp));
1382 }
1383
1384 int
1385 dtrace_aggregate_walk_valvarsorted(dtrace_hdl_t *dtp,
1386     dtrace_aggregate_f *func, void *arg)
1387 {
1388         return (dt_aggregate_walk_sorted(dtp, func,
1389             arg, dt_aggregate_valvarcmp));
1390 }
1391
1392 int
1393 dtrace_aggregate_walk_keyrevsorted(dtrace_hdl_t *dtp,
1394     dtrace_aggregate_f *func, void *arg)
1395 {
1396         return (dt_aggregate_walk_sorted(dtp, func,
1397             arg, dt_aggregate_varkeyrevcmp));
1398 }
1399
1400 int
1401 dtrace_aggregate_walk_valrevsorted(dtrace_hdl_t *dtp,
1402     dtrace_aggregate_f *func, void *arg)
1403 {
1404         return (dt_aggregate_walk_sorted(dtp, func,
1405             arg, dt_aggregate_varvalrevcmp));
1406 }
1407
1408 int
1409 dtrace_aggregate_walk_keyvarrevsorted(dtrace_hdl_t *dtp,
1410     dtrace_aggregate_f *func, void *arg)
1411 {
1412         return (dt_aggregate_walk_sorted(dtp, func,
1413             arg, dt_aggregate_keyvarrevcmp));
1414 }
1415
1416 int
1417 dtrace_aggregate_walk_valvarrevsorted(dtrace_hdl_t *dtp,
1418     dtrace_aggregate_f *func, void *arg)
1419 {
1420         return (dt_aggregate_walk_sorted(dtp, func,
1421             arg, dt_aggregate_valvarrevcmp));
1422 }
1423
1424 int
1425 dtrace_aggregate_walk_joined(dtrace_hdl_t *dtp, dtrace_aggvarid_t *aggvars,
1426     int naggvars, dtrace_aggregate_walk_joined_f *func, void *arg)
1427 {
1428         dt_aggregate_t *agp = &dtp->dt_aggregate;
1429         dt_ahashent_t *h, **sorted = NULL, ***bundle, **nbundle;
1430         const dtrace_aggdata_t **data;
1431         dt_ahashent_t *zaggdata = NULL;
1432         dt_ahash_t *hash = &agp->dtat_hash;
1433         size_t nentries = 0, nbundles = 0, start, zsize = 0, bundlesize;
1434         dtrace_aggvarid_t max = 0, aggvar;
1435         int rval = -1, *map, *remap = NULL;
1436         int i, j;
1437         dtrace_optval_t sortpos = dtp->dt_options[DTRACEOPT_AGGSORTPOS];
1438
1439         /*
1440          * If the sorting position is greater than the number of aggregation
1441          * variable IDs, we silently set it to 0.
1442          */
1443         if (sortpos == DTRACEOPT_UNSET || sortpos >= naggvars)
1444                 sortpos = 0;
1445
1446         /*
1447          * First we need to translate the specified aggregation variable IDs
1448          * into a linear map that will allow us to translate an aggregation
1449          * variable ID into its position in the specified aggvars.
1450          */
1451         for (i = 0; i < naggvars; i++) {
1452                 if (aggvars[i] == DTRACE_AGGVARIDNONE || aggvars[i] < 0)
1453                         return (dt_set_errno(dtp, EDT_BADAGGVAR));
1454
1455                 if (aggvars[i] > max)
1456                         max = aggvars[i];
1457         }
1458
1459         if ((map = dt_zalloc(dtp, (max + 1) * sizeof (int))) == NULL)
1460                 return (-1);
1461
1462         zaggdata = dt_zalloc(dtp, naggvars * sizeof (dt_ahashent_t));
1463
1464         if (zaggdata == NULL)
1465                 goto out;
1466
1467         for (i = 0; i < naggvars; i++) {
1468                 int ndx = i + sortpos;
1469
1470                 if (ndx >= naggvars)
1471                         ndx -= naggvars;
1472
1473                 aggvar = aggvars[ndx];
1474                 assert(aggvar <= max);
1475
1476                 if (map[aggvar]) {
1477                         /*
1478                          * We have an aggregation variable that is present
1479                          * more than once in the array of aggregation
1480                          * variables.  While it's unclear why one might want
1481                          * to do this, it's legal.  To support this construct,
1482                          * we will allocate a remap that will indicate the
1483                          * position from which this aggregation variable
1484                          * should be pulled.  (That is, where the remap will
1485                          * map from one position to another.)
1486                          */
1487                         if (remap == NULL) {
1488                                 remap = dt_zalloc(dtp, naggvars * sizeof (int));
1489
1490                                 if (remap == NULL)
1491                                         goto out;
1492                         }
1493
1494                         /*
1495                          * Given that the variable is already present, assert
1496                          * that following through the mapping and adjusting
1497                          * for the sort position yields the same aggregation
1498                          * variable ID.
1499                          */
1500                         assert(aggvars[(map[aggvar] - 1 + sortpos) %
1501                             naggvars] == aggvars[ndx]);
1502
1503                         remap[i] = map[aggvar];
1504                         continue;
1505                 }
1506
1507                 map[aggvar] = i + 1;
1508         }
1509
1510         /*
1511          * We need to take two passes over the data to size our allocation, so
1512          * we'll use the first pass to also fill in the zero-filled data to be
1513          * used to properly format a zero-valued aggregation.
1514          */
1515         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1516                 dtrace_aggvarid_t id;
1517                 int ndx;
1518
1519                 if ((id = dt_aggregate_aggvarid(h)) > max || !(ndx = map[id]))
1520                         continue;
1521
1522                 if (zaggdata[ndx - 1].dtahe_size == 0) {
1523                         zaggdata[ndx - 1].dtahe_size = h->dtahe_size;
1524                         zaggdata[ndx - 1].dtahe_data = h->dtahe_data;
1525                 }
1526
1527                 nentries++;
1528         }
1529
1530         if (nentries == 0) {
1531                 /*
1532                  * We couldn't find any entries; there is nothing else to do.
1533                  */
1534                 rval = 0;
1535                 goto out;
1536         }
1537
1538         /*
1539          * Before we sort the data, we're going to look for any holes in our
1540          * zero-filled data.  This will occur if an aggregation variable that
1541          * we are being asked to print has not yet been assigned the result of
1542          * any aggregating action for _any_ tuple.  The issue becomes that we
1543          * would like a zero value to be printed for all columns for this
1544          * aggregation, but without any record description, we don't know the
1545          * aggregating action that corresponds to the aggregation variable.  To
1546          * try to find a match, we're simply going to lookup aggregation IDs
1547          * (which are guaranteed to be contiguous and to start from 1), looking
1548          * for the specified aggregation variable ID.  If we find a match,
1549          * we'll use that.  If we iterate over all aggregation IDs and don't
1550          * find a match, then we must be an anonymous enabling.  (Anonymous
1551          * enablings can't currently derive either aggregation variable IDs or
1552          * aggregation variable names given only an aggregation ID.)  In this
1553          * obscure case (anonymous enabling, multiple aggregation printa() with
1554          * some aggregations not represented for any tuple), our defined
1555          * behavior is that the zero will be printed in the format of the first
1556          * aggregation variable that contains any non-zero value.
1557          */
1558         for (i = 0; i < naggvars; i++) {
1559                 if (zaggdata[i].dtahe_size == 0) {
1560                         dtrace_aggvarid_t aggvar;
1561
1562                         aggvar = aggvars[(i - sortpos + naggvars) % naggvars];
1563                         assert(zaggdata[i].dtahe_data.dtada_data == NULL);
1564
1565                         for (j = DTRACE_AGGIDNONE + 1; ; j++) {
1566                                 dtrace_aggdesc_t *agg;
1567                                 dtrace_aggdata_t *aggdata;
1568
1569                                 if (dt_aggid_lookup(dtp, j, &agg) != 0)
1570                                         break;
1571
1572                                 if (agg->dtagd_varid != aggvar)
1573                                         continue;
1574
1575                                 /*
1576                                  * We have our description -- now we need to
1577                                  * cons up the zaggdata entry for it.
1578                                  */
1579                                 aggdata = &zaggdata[i].dtahe_data;
1580                                 aggdata->dtada_size = agg->dtagd_size;
1581                                 aggdata->dtada_desc = agg;
1582                                 aggdata->dtada_handle = dtp;
1583                                 (void) dt_epid_lookup(dtp, agg->dtagd_epid,
1584                                     &aggdata->dtada_edesc,
1585                                     &aggdata->dtada_pdesc);
1586                                 aggdata->dtada_normal = 1;
1587                                 zaggdata[i].dtahe_hashval = 0;
1588                                 zaggdata[i].dtahe_size = agg->dtagd_size;
1589                                 break;
1590                         }
1591
1592                         if (zaggdata[i].dtahe_size == 0) {
1593                                 caddr_t data;
1594
1595                                 /*
1596                                  * We couldn't find this aggregation, meaning
1597                                  * that we have never seen it before for any
1598                                  * tuple _and_ this is an anonymous enabling.
1599                                  * That is, we're in the obscure case outlined
1600                                  * above.  In this case, our defined behavior
1601                                  * is to format the data in the format of the
1602                                  * first non-zero aggregation -- of which, of
1603                                  * course, we know there to be at least one
1604                                  * (or nentries would have been zero).
1605                                  */
1606                                 for (j = 0; j < naggvars; j++) {
1607                                         if (zaggdata[j].dtahe_size != 0)
1608                                                 break;
1609                                 }
1610
1611                                 assert(j < naggvars);
1612                                 zaggdata[i] = zaggdata[j];
1613
1614                                 data = zaggdata[i].dtahe_data.dtada_data;
1615                                 assert(data != NULL);
1616                         }
1617                 }
1618         }
1619
1620         /*
1621          * Now we need to allocate our zero-filled data for use for
1622          * aggregations that don't have a value corresponding to a given key.
1623          */
1624         for (i = 0; i < naggvars; i++) {
1625                 dtrace_aggdata_t *aggdata = &zaggdata[i].dtahe_data;
1626                 dtrace_aggdesc_t *aggdesc = aggdata->dtada_desc;
1627                 dtrace_recdesc_t *rec;
1628                 uint64_t larg;
1629                 caddr_t zdata;
1630
1631                 zsize = zaggdata[i].dtahe_size;
1632                 assert(zsize != 0);
1633
1634                 if ((zdata = dt_zalloc(dtp, zsize)) == NULL) {
1635                         /*
1636                          * If we failed to allocated some zero-filled data, we
1637                          * need to zero out the remaining dtada_data pointers
1638                          * to prevent the wrong data from being freed below.
1639                          */
1640                         for (j = i; j < naggvars; j++)
1641                                 zaggdata[j].dtahe_data.dtada_data = NULL;
1642                         goto out;
1643                 }
1644
1645                 aggvar = aggvars[(i - sortpos + naggvars) % naggvars];
1646
1647                 /*
1648                  * First, the easy bit.  To maintain compatibility with
1649                  * consumers that pull the compiler-generated ID out of the
1650                  * data, we put that ID at the top of the zero-filled data.
1651                  */
1652                 rec = &aggdesc->dtagd_rec[0];
1653                 /* LINTED - alignment */
1654                 *((dtrace_aggvarid_t *)(zdata + rec->dtrd_offset)) = aggvar;
1655
1656                 rec = &aggdesc->dtagd_rec[aggdesc->dtagd_nrecs - 1];
1657
1658                 /*
1659                  * Now for the more complicated part.  If (and only if) this
1660                  * is an lquantize() aggregating action, zero-filled data is
1661                  * not equivalent to an empty record:  we must also get the
1662                  * parameters for the lquantize().
1663                  */
1664                 if (rec->dtrd_action == DTRACEAGG_LQUANTIZE) {
1665                         if (aggdata->dtada_data != NULL) {
1666                                 /*
1667                                  * The easier case here is if we actually have
1668                                  * some prototype data -- in which case we
1669                                  * manually dig it out of the aggregation
1670                                  * record.
1671                                  */
1672                                 /* LINTED - alignment */
1673                                 larg = *((uint64_t *)(aggdata->dtada_data +
1674                                     rec->dtrd_offset));
1675                         } else {
1676                                 /*
1677                                  * We don't have any prototype data.  As a
1678                                  * result, we know that we _do_ have the
1679                                  * compiler-generated information.  (If this
1680                                  * were an anonymous enabling, all of our
1681                                  * zero-filled data would have prototype data
1682                                  * -- either directly or indirectly.) So as
1683                                  * gross as it is, we'll grovel around in the
1684                                  * compiler-generated information to find the
1685                                  * lquantize() parameters.
1686                                  */
1687                                 dtrace_stmtdesc_t *sdp;
1688                                 dt_ident_t *aid;
1689                                 dt_idsig_t *isp;
1690
1691                                 sdp = (dtrace_stmtdesc_t *)(uintptr_t)
1692                                     aggdesc->dtagd_rec[0].dtrd_uarg;
1693                                 aid = sdp->dtsd_aggdata;
1694                                 isp = (dt_idsig_t *)aid->di_data;
1695                                 assert(isp->dis_auxinfo != 0);
1696                                 larg = isp->dis_auxinfo;
1697                         }
1698
1699                         /* LINTED - alignment */
1700                         *((uint64_t *)(zdata + rec->dtrd_offset)) = larg;
1701                 }
1702
1703                 aggdata->dtada_data = zdata;
1704         }
1705
1706         /*
1707          * Now that we've dealt with setting up our zero-filled data, we can
1708          * allocate our sorted array, and take another pass over the data to
1709          * fill it.
1710          */
1711         sorted = dt_alloc(dtp, nentries * sizeof (dt_ahashent_t *));
1712
1713         if (sorted == NULL)
1714                 goto out;
1715
1716         for (h = hash->dtah_all, i = 0; h != NULL; h = h->dtahe_nextall) {
1717                 dtrace_aggvarid_t id;
1718
1719                 if ((id = dt_aggregate_aggvarid(h)) > max || !map[id])
1720                         continue;
1721
1722                 sorted[i++] = h;
1723         }
1724
1725         assert(i == nentries);
1726
1727         /*
1728          * We've loaded our array; now we need to sort by value to allow us
1729          * to create bundles of like value.  We're going to acquire the
1730          * dt_qsort_lock here, and hold it across all of our subsequent
1731          * comparison and sorting.
1732          */
1733         (void) pthread_mutex_lock(&dt_qsort_lock);
1734
1735         qsort(sorted, nentries, sizeof (dt_ahashent_t *),
1736             dt_aggregate_keyvarcmp);
1737
1738         /*
1739          * Now we need to go through and create bundles.  Because the number
1740          * of bundles is bounded by the size of the sorted array, we're going
1741          * to reuse the underlying storage.  And note that "bundle" is an
1742          * array of pointers to arrays of pointers to dt_ahashent_t -- making
1743          * its type (regrettably) "dt_ahashent_t ***".  (Regrettable because
1744          * '*' -- like '_' and 'X' -- should never appear in triplicate in
1745          * an ideal world.)
1746          */
1747         bundle = (dt_ahashent_t ***)sorted;
1748
1749         for (i = 1, start = 0; i <= nentries; i++) {
1750                 if (i < nentries &&
1751                     dt_aggregate_keycmp(&sorted[i], &sorted[i - 1]) == 0)
1752                         continue;
1753
1754                 /*
1755                  * We have a bundle boundary.  Everything from start to
1756                  * (i - 1) belongs in one bundle.
1757                  */
1758                 assert(i - start <= naggvars);
1759                 bundlesize = (naggvars + 2) * sizeof (dt_ahashent_t *);
1760
1761                 if ((nbundle = dt_zalloc(dtp, bundlesize)) == NULL) {
1762                         (void) pthread_mutex_unlock(&dt_qsort_lock);
1763                         goto out;
1764                 }
1765
1766                 for (j = start; j < i; j++) {
1767                         dtrace_aggvarid_t id = dt_aggregate_aggvarid(sorted[j]);
1768
1769                         assert(id <= max);
1770                         assert(map[id] != 0);
1771                         assert(map[id] - 1 < naggvars);
1772                         assert(nbundle[map[id] - 1] == NULL);
1773                         nbundle[map[id] - 1] = sorted[j];
1774
1775                         if (nbundle[naggvars] == NULL)
1776                                 nbundle[naggvars] = sorted[j];
1777                 }
1778
1779                 for (j = 0; j < naggvars; j++) {
1780                         if (nbundle[j] != NULL)
1781                                 continue;
1782
1783                         /*
1784                          * Before we assume that this aggregation variable
1785                          * isn't present (and fall back to using the
1786                          * zero-filled data allocated earlier), check the
1787                          * remap.  If we have a remapping, we'll drop it in
1788                          * here.  Note that we might be remapping an
1789                          * aggregation variable that isn't present for this
1790                          * key; in this case, the aggregation data that we
1791                          * copy will point to the zeroed data.
1792                          */
1793                         if (remap != NULL && remap[j]) {
1794                                 assert(remap[j] - 1 < j);
1795                                 assert(nbundle[remap[j] - 1] != NULL);
1796                                 nbundle[j] = nbundle[remap[j] - 1];
1797                         } else {
1798                                 nbundle[j] = &zaggdata[j];
1799                         }
1800                 }
1801
1802                 bundle[nbundles++] = nbundle;
1803                 start = i;
1804         }
1805
1806         /*
1807          * Now we need to re-sort based on the first value.
1808          */
1809         dt_aggregate_qsort(dtp, bundle, nbundles, sizeof (dt_ahashent_t **),
1810             dt_aggregate_bundlecmp);
1811
1812         (void) pthread_mutex_unlock(&dt_qsort_lock);
1813
1814         /*
1815          * We're done!  Now we just need to go back over the sorted bundles,
1816          * calling the function.
1817          */
1818         data = alloca((naggvars + 1) * sizeof (dtrace_aggdata_t *));
1819
1820         for (i = 0; i < nbundles; i++) {
1821                 for (j = 0; j < naggvars; j++)
1822                         data[j + 1] = NULL;
1823
1824                 for (j = 0; j < naggvars; j++) {
1825                         int ndx = j - sortpos;
1826
1827                         if (ndx < 0)
1828                                 ndx += naggvars;
1829
1830                         assert(bundle[i][ndx] != NULL);
1831                         data[j + 1] = &bundle[i][ndx]->dtahe_data;
1832                 }
1833
1834                 for (j = 0; j < naggvars; j++)
1835                         assert(data[j + 1] != NULL);
1836
1837                 /*
1838                  * The representative key is the last element in the bundle.
1839                  * Assert that we have one, and then set it to be the first
1840                  * element of data.
1841                  */
1842                 assert(bundle[i][j] != NULL);
1843                 data[0] = &bundle[i][j]->dtahe_data;
1844
1845                 if ((rval = func(data, naggvars + 1, arg)) == -1)
1846                         goto out;
1847         }
1848
1849         rval = 0;
1850 out:
1851         for (i = 0; i < nbundles; i++)
1852                 dt_free(dtp, bundle[i]);
1853
1854         if (zaggdata != NULL) {
1855                 for (i = 0; i < naggvars; i++)
1856                         dt_free(dtp, zaggdata[i].dtahe_data.dtada_data);
1857         }
1858
1859         dt_free(dtp, zaggdata);
1860         dt_free(dtp, sorted);
1861         dt_free(dtp, remap);
1862         dt_free(dtp, map);
1863
1864         return (rval);
1865 }
1866
1867 int
1868 dtrace_aggregate_print(dtrace_hdl_t *dtp, FILE *fp,
1869     dtrace_aggregate_walk_f *func)
1870 {
1871         dt_print_aggdata_t pd;
1872
1873         pd.dtpa_dtp = dtp;
1874         pd.dtpa_fp = fp;
1875         pd.dtpa_allunprint = 1;
1876
1877         if (func == NULL)
1878                 func = dtrace_aggregate_walk_sorted;
1879
1880         if ((*func)(dtp, dt_print_agg, &pd) == -1)
1881                 return (dt_set_errno(dtp, dtp->dt_errno));
1882
1883         return (0);
1884 }
1885
1886 void
1887 dtrace_aggregate_clear(dtrace_hdl_t *dtp)
1888 {
1889         dt_aggregate_t *agp = &dtp->dt_aggregate;
1890         dt_ahash_t *hash = &agp->dtat_hash;
1891         dt_ahashent_t *h;
1892         dtrace_aggdata_t *data;
1893         dtrace_aggdesc_t *aggdesc;
1894         dtrace_recdesc_t *rec;
1895         int i, max_cpus = agp->dtat_maxcpu;
1896
1897         for (h = hash->dtah_all; h != NULL; h = h->dtahe_nextall) {
1898                 aggdesc = h->dtahe_data.dtada_desc;
1899                 rec = &aggdesc->dtagd_rec[aggdesc->dtagd_nrecs - 1];
1900                 data = &h->dtahe_data;
1901
1902                 bzero(&data->dtada_data[rec->dtrd_offset], rec->dtrd_size);
1903
1904                 if (data->dtada_percpu == NULL)
1905                         continue;
1906
1907                 for (i = 0; i < max_cpus; i++)
1908                         bzero(data->dtada_percpu[i], rec->dtrd_size);
1909         }
1910 }
1911
1912 void
1913 dt_aggregate_destroy(dtrace_hdl_t *dtp)
1914 {
1915         dt_aggregate_t *agp = &dtp->dt_aggregate;
1916         dt_ahash_t *hash = &agp->dtat_hash;
1917         dt_ahashent_t *h, *next;
1918         dtrace_aggdata_t *aggdata;
1919         int i, max_cpus = agp->dtat_maxcpu;
1920
1921         if (hash->dtah_hash == NULL) {
1922                 assert(hash->dtah_all == NULL);
1923         } else {
1924                 free(hash->dtah_hash);
1925
1926                 for (h = hash->dtah_all; h != NULL; h = next) {
1927                         next = h->dtahe_nextall;
1928
1929                         aggdata = &h->dtahe_data;
1930
1931                         if (aggdata->dtada_percpu != NULL) {
1932                                 for (i = 0; i < max_cpus; i++)
1933                                         free(aggdata->dtada_percpu[i]);
1934                                 free(aggdata->dtada_percpu);
1935                         }
1936
1937                         free(aggdata->dtada_data);
1938                         free(h);
1939                 }
1940
1941                 hash->dtah_hash = NULL;
1942                 hash->dtah_all = NULL;
1943                 hash->dtah_size = 0;
1944         }
1945
1946         free(agp->dtat_buf.dtbd_data);
1947         free(agp->dtat_cpus);
1948 }