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