1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 
  26 /*
  27  * Given several files containing CTF data, merge and uniquify that data into
  28  * a single CTF section in an output file.
  29  *
  30  * Merges can proceed independently.  As such, we perform the merges in parallel
  31  * using a worker thread model.  A given glob of CTF data (either all of the CTF
  32  * data from a single input file, or the result of one or more merges) can only
  33  * be involved in a single merge at any given time, so the process decreases in
  34  * parallelism, especially towards the end, as more and more files are
  35  * consolidated, finally resulting in a single merge of two large CTF graphs.
  36  * Unfortunately, the last merge is also the slowest, as the two graphs being
  37  * merged are each the product of merges of half of the input files.
  38  *
  39  * The algorithm consists of two phases, described in detail below.  The first
  40  * phase entails the merging of CTF data in groups of eight.  The second phase
  41  * takes the results of Phase I, and merges them two at a time.  This disparity
  42  * is due to an observation that the merge time increases at least quadratically
  43  * with the size of the CTF data being merged.  As such, merges of CTF graphs
  44  * newly read from input files are much faster than merges of CTF graphs that
  45  * are themselves the results of prior merges.
  46  *
  47  * A further complication is the need to ensure the repeatability of CTF merges.
  48  * That is, a merge should produce the same output every time, given the same
  49  * input.  In both phases, this consistency requirement is met by imposing an
  50  * ordering on the merge process, thus ensuring that a given set of input files
  51  * are merged in the same order every time.
  52  *
  53  *   Phase I
  54  *
  55  *   The main thread reads the input files one by one, transforming the CTF
  56  *   data they contain into tdata structures.  When a given file has been read
  57  *   and parsed, it is placed on the work queue for retrieval by worker threads.
  58  *
  59  *   Central to Phase I is the Work In Progress (wip) array, which is used to
  60  *   merge batches of files in a predictable order.  Files are read by the main
  61  *   thread, and are merged into wip array elements in round-robin order.  When
  62  *   the number of files merged into a given array slot equals the batch size,
  63  *   the merged CTF graph in that array is added to the done slot in order by
  64  *   array slot.
  65  *
  66  *   For example, consider a case where we have five input files, a batch size
  67  *   of two, a wip array size of two, and two worker threads (T1 and T2).
  68  *
  69  *    1. The wip array elements are assigned initial batch numbers 0 and 1.
  70  *    2. T1 reads an input file from the input queue (wq_queue).  This is the
  71  *       first input file, so it is placed into wip[0].  The second file is
  72  *       similarly read and placed into wip[1].  The wip array slots now contain
  73  *       one file each (wip_nmerged == 1).
  74  *    3. T1 reads the third input file, which it merges into wip[0].  The
  75  *       number of files in wip[0] is equal to the batch size.
  76  *    4. T2 reads the fourth input file, which it merges into wip[1].  wip[1]
  77  *       is now full too.
  78  *    5. T2 attempts to place the contents of wip[1] on the done queue
  79  *       (wq_done_queue), but it can't, since the batch ID for wip[1] is 1.
  80  *       Batch 0 needs to be on the done queue before batch 1 can be added, so
  81  *       T2 blocks on wip[1]'s cv.
  82  *    6. T1 attempts to place the contents of wip[0] on the done queue, and
  83  *       succeeds, updating wq_lastdonebatch to 0.  It clears wip[0], and sets
  84  *       its batch ID to 2.  T1 then signals wip[1]'s cv to awaken T2.
  85  *    7. T2 wakes up, notices that wq_lastdonebatch is 0, which means that
  86  *       batch 1 can now be added.  It adds wip[1] to the done queue, clears
  87  *       wip[1], and sets its batch ID to 3.  It signals wip[0]'s cv, and
  88  *       restarts.
  89  *
  90  *   The above process continues until all input files have been consumed.  At
  91  *   this point, a pair of barriers are used to allow a single thread to move
  92  *   any partial batches from the wip array to the done array in batch ID order.
  93  *   When this is complete, wq_done_queue is moved to wq_queue, and Phase II
  94  *   begins.
  95  *
  96  *      Locking Semantics (Phase I)
  97  *
  98  *      The input queue (wq_queue) and the done queue (wq_done_queue) are
  99  *      protected by separate mutexes - wq_queue_lock and wq_done_queue.  wip
 100  *      array slots are protected by their own mutexes, which must be grabbed
 101  *      before releasing the input queue lock.  The wip array lock is dropped
 102  *      when the thread restarts the loop.  If the array slot was full, the
 103  *      array lock will be held while the slot contents are added to the done
 104  *      queue.  The done queue lock is used to protect the wip slot cv's.
 105  *
 106  *      The pow number is protected by the queue lock.  The master batch ID
 107  *      and last completed batch (wq_lastdonebatch) counters are protected *in
 108  *      Phase I* by the done queue lock.
 109  *
 110  *   Phase II
 111  *
 112  *   When Phase II begins, the queue consists of the merged batches from the
 113  *   first phase.  Assume we have five batches:
 114  *
 115  *      Q:      a b c d e
 116  *
 117  *   Using the same batch ID mechanism we used in Phase I, but without the wip
 118  *   array, worker threads remove two entries at a time from the beginning of
 119  *   the queue.  These two entries are merged, and are added back to the tail
 120  *   of the queue, as follows:
 121  *
 122  *      Q:      a b c d e       # start
 123  *      Q:      c d e ab        # a, b removed, merged, added to end
 124  *      Q:      e ab cd         # c, d removed, merged, added to end
 125  *      Q:      cd eab          # e, ab removed, merged, added to end
 126  *      Q:      cdeab           # cd, eab removed, merged, added to end
 127  *
 128  *   When one entry remains on the queue, with no merges outstanding, Phase II
 129  *   finishes.  We pre-determine the stopping point by pre-calculating the
 130  *   number of nodes that will appear on the list.  In the example above, the
 131  *   number (wq_ninqueue) is 9.  When ninqueue is 1, we conclude Phase II by
 132  *   signaling the main thread via wq_done_cv.
 133  *
 134  *      Locking Semantics (Phase II)
 135  *
 136  *      The queue (wq_queue), ninqueue, and the master batch ID and last
 137  *      completed batch counters are protected by wq_queue_lock.  The done
 138  *      queue and corresponding lock are unused in Phase II as is the wip array.
 139  *
 140  *   Uniquification
 141  *
 142  *   We want the CTF data that goes into a given module to be as small as
 143  *   possible.  For example, we don't want it to contain any type data that may
 144  *   be present in another common module.  As such, after creating the master
 145  *   tdata_t for a given module, we can, if requested by the user, uniquify it
 146  *   against the tdata_t from another module (genunix in the case of the SunOS
 147  *   kernel).  We perform a merge between the tdata_t for this module and the
 148  *   tdata_t from genunix.  Nodes found in this module that are not present in
 149  *   genunix are added to a third tdata_t - the uniquified tdata_t.
 150  *
 151  *   Additive Merges
 152  *
 153  *   In some cases, for example if we are issuing a new version of a common
 154  *   module in a patch, we need to make sure that the CTF data already present
 155  *   in that module does not change.  Changes to this data would void the CTF
 156  *   data in any module that uniquified against the common module.  To preserve
 157  *   the existing data, we can perform what is known as an additive merge.  In
 158  *   this case, a final uniquification is performed against the CTF data in the
 159  *   previous version of the module.  The result will be the placement of new
 160  *   and changed data after the existing data, thus preserving the existing type
 161  *   ID space.
 162  *
 163  *   Saving the result
 164  *
 165  *   When the merges are complete, the resulting tdata_t is placed into the
 166  *   output file, replacing the .SUNW_ctf section (if any) already in that file.
 167  *
 168  * The person who changes the merging thread code in this file without updating
 169  * this comment will not live to see the stock hit five.
 170  */
 171 
 172 #include <stdio.h>
 173 #include <stdlib.h>
 174 #include <unistd.h>
 175 #include <pthread.h>
 176 #include <assert.h>
 177 #include <synch.h>
 178 #include <signal.h>
 179 #include <libgen.h>
 180 #include <string.h>
 181 #include <errno.h>
 182 #include <alloca.h>
 183 #include <sys/param.h>
 184 #include <sys/types.h>
 185 #include <sys/mman.h>
 186 #include <sys/sysconf.h>
 187 
 188 #include "ctf_headers.h"
 189 #include "ctftools.h"
 190 #include "ctfmerge.h"
 191 #include "traverse.h"
 192 #include "memory.h"
 193 #include "fifo.h"
 194 #include "barrier.h"
 195 
 196 #pragma init(bigheap)
 197 
 198 #define MERGE_PHASE1_BATCH_SIZE         8
 199 #define MERGE_PHASE1_MAX_SLOTS          5
 200 #define MERGE_INPUT_THROTTLE_LEN        10
 201 
 202 const char *progname;
 203 static char *outfile = NULL;
 204 static char *tmpname = NULL;
 205 static int dynsym;
 206 int debug_level = DEBUG_LEVEL;
 207 static size_t maxpgsize = 0x400000;
 208 
 209 
 210 void
 211 usage(void)
 212 {
 213         (void) fprintf(stderr,
 214             "Usage: %s [-fstv] -l label | -L labelenv -o outfile file ...\n"
 215             "       %s [-fstv] -l label | -L labelenv -o outfile -d uniqfile\n"
 216             "       %*s [-D uniqlabel] file ...\n"
 217             "       %s [-fstv] -l label | -L labelenv -o outfile -w withfile "
 218             "file ...\n"
 219             "       %s -c srcfile destfile\n"
 220             "\n"
 221             "  Note: if -L labelenv is specified and labelenv is not set in\n"
 222             "  the environment, a default value is used.\n",
 223             progname, progname, strlen(progname), " ",
 224             progname, progname);
 225 }
 226 
 227 static void
 228 bigheap(void)
 229 {
 230         size_t big, *size;
 231         int sizes;
 232         struct memcntl_mha mha;
 233 
 234         /*
 235          * First, get the available pagesizes.
 236          */
 237         if ((sizes = getpagesizes(NULL, 0)) == -1)
 238                 return;
 239 
 240         if (sizes == 1 || (size = alloca(sizeof (size_t) * sizes)) == NULL)
 241                 return;
 242 
 243         if (getpagesizes(size, sizes) == -1)
 244                 return;
 245 
 246         while (size[sizes - 1] > maxpgsize)
 247                 sizes--;
 248 
 249         /* set big to the largest allowed page size */
 250         big = size[sizes - 1];
 251         if (big & (big - 1)) {
 252                 /*
 253                  * The largest page size is not a power of two for some
 254                  * inexplicable reason; return.
 255                  */
 256                 return;
 257         }
 258 
 259         /*
 260          * Now, align our break to the largest page size.
 261          */
 262         if (brk((void *)((((uintptr_t)sbrk(0) - 1) & ~(big - 1)) + big)) != 0)
 263                 return;
 264 
 265         /*
 266          * set the preferred page size for the heap
 267          */
 268         mha.mha_cmd = MHA_MAPSIZE_BSSBRK;
 269         mha.mha_flags = 0;
 270         mha.mha_pagesize = big;
 271 
 272         (void) memcntl(NULL, 0, MC_HAT_ADVISE, (caddr_t)&mha, 0, 0);
 273 }
 274 
 275 static void
 276 finalize_phase_one(workqueue_t *wq)
 277 {
 278         int startslot, i;
 279 
 280         /*
 281          * wip slots are cleared out only when maxbatchsz td's have been merged
 282          * into them.  We're not guaranteed that the number of files we're
 283          * merging is a multiple of maxbatchsz, so there will be some partial
 284          * groups in the wip array.  Move them to the done queue in batch ID
 285          * order, starting with the slot containing the next batch that would
 286          * have been placed on the done queue, followed by the others.
 287          * One thread will be doing this while the others wait at the barrier
 288          * back in worker_thread(), so we don't need to worry about pesky things
 289          * like locks.
 290          */
 291 
 292         for (startslot = -1, i = 0; i < wq->wq_nwipslots; i++) {
 293                 if (wq->wq_wip[i].wip_batchid == wq->wq_lastdonebatch + 1) {
 294                         startslot = i;
 295                         break;
 296                 }
 297         }
 298 
 299         assert(startslot != -1);
 300 
 301         for (i = startslot; i < startslot + wq->wq_nwipslots; i++) {
 302                 int slotnum = i % wq->wq_nwipslots;
 303                 wip_t *wipslot = &wq->wq_wip[slotnum];
 304 
 305                 if (wipslot->wip_td != NULL) {
 306                         debug(2, "clearing slot %d (%d) (saving %d)\n",
 307                             slotnum, i, wipslot->wip_nmerged);
 308                 } else
 309                         debug(2, "clearing slot %d (%d)\n", slotnum, i);
 310 
 311                 if (wipslot->wip_td != NULL) {
 312                         fifo_add(wq->wq_donequeue, wipslot->wip_td);
 313                         wq->wq_wip[slotnum].wip_td = NULL;
 314                 }
 315         }
 316 
 317         wq->wq_lastdonebatch = wq->wq_next_batchid++;
 318 
 319         debug(2, "phase one done: donequeue has %d items\n",
 320             fifo_len(wq->wq_donequeue));
 321 }
 322 
 323 static void
 324 init_phase_two(workqueue_t *wq)
 325 {
 326         int num;
 327 
 328         /*
 329          * We're going to continually merge the first two entries on the queue,
 330          * placing the result on the end, until there's nothing left to merge.
 331          * At that point, everything will have been merged into one.  The
 332          * initial value of ninqueue needs to be equal to the total number of
 333          * entries that will show up on the queue, both at the start of the
 334          * phase and as generated by merges during the phase.
 335          */
 336         wq->wq_ninqueue = num = fifo_len(wq->wq_donequeue);
 337         while (num != 1) {
 338                 wq->wq_ninqueue += num / 2;
 339                 num = num / 2 + num % 2;
 340         }
 341 
 342         /*
 343          * Move the done queue to the work queue.  We won't be using the done
 344          * queue in phase 2.
 345          */
 346         assert(fifo_len(wq->wq_queue) == 0);
 347         fifo_free(wq->wq_queue, NULL);
 348         wq->wq_queue = wq->wq_donequeue;
 349 }
 350 
 351 static void
 352 wip_save_work(workqueue_t *wq, wip_t *slot, int slotnum)
 353 {
 354         pthread_mutex_lock(&wq->wq_donequeue_lock);
 355 
 356         while (wq->wq_lastdonebatch + 1 < slot->wip_batchid)
 357                 pthread_cond_wait(&slot->wip_cv, &wq->wq_donequeue_lock);
 358         assert(wq->wq_lastdonebatch + 1 == slot->wip_batchid);
 359 
 360         fifo_add(wq->wq_donequeue, slot->wip_td);
 361         wq->wq_lastdonebatch++;
 362         pthread_cond_signal(&wq->wq_wip[(slotnum + 1) %
 363             wq->wq_nwipslots].wip_cv);
 364 
 365         /* reset the slot for next use */
 366         slot->wip_td = NULL;
 367         slot->wip_batchid = wq->wq_next_batchid++;
 368 
 369         pthread_mutex_unlock(&wq->wq_donequeue_lock);
 370 }
 371 
 372 static void
 373 wip_add_work(wip_t *slot, tdata_t *pow)
 374 {
 375         if (slot->wip_td == NULL) {
 376                 slot->wip_td = pow;
 377                 slot->wip_nmerged = 1;
 378         } else {
 379                 debug(2, "%d: merging %p into %p\n", pthread_self(),
 380                     (void *)pow, (void *)slot->wip_td);
 381 
 382                 merge_into_master(pow, slot->wip_td, NULL, 0);
 383                 tdata_free(pow);
 384 
 385                 slot->wip_nmerged++;
 386         }
 387 }
 388 
 389 static void
 390 worker_runphase1(workqueue_t *wq)
 391 {
 392         wip_t *wipslot;
 393         tdata_t *pow;
 394         int wipslotnum, pownum;
 395 
 396         for (;;) {
 397                 pthread_mutex_lock(&wq->wq_queue_lock);
 398 
 399                 while (fifo_empty(wq->wq_queue)) {
 400                         if (wq->wq_nomorefiles == 1) {
 401                                 pthread_cond_broadcast(&wq->wq_work_avail);
 402                                 pthread_mutex_unlock(&wq->wq_queue_lock);
 403 
 404                                 /* on to phase 2 ... */
 405                                 return;
 406                         }
 407 
 408                         pthread_cond_wait(&wq->wq_work_avail,
 409                             &wq->wq_queue_lock);
 410                 }
 411 
 412                 /* there's work to be done! */
 413                 pow = fifo_remove(wq->wq_queue);
 414                 pownum = wq->wq_nextpownum++;
 415                 pthread_cond_broadcast(&wq->wq_work_removed);
 416 
 417                 assert(pow != NULL);
 418 
 419                 /* merge it into the right slot */
 420                 wipslotnum = pownum % wq->wq_nwipslots;
 421                 wipslot = &wq->wq_wip[wipslotnum];
 422 
 423                 pthread_mutex_lock(&wipslot->wip_lock);
 424 
 425                 pthread_mutex_unlock(&wq->wq_queue_lock);
 426 
 427                 wip_add_work(wipslot, pow);
 428 
 429                 if (wipslot->wip_nmerged == wq->wq_maxbatchsz)
 430                         wip_save_work(wq, wipslot, wipslotnum);
 431 
 432                 pthread_mutex_unlock(&wipslot->wip_lock);
 433         }
 434 }
 435 
 436 static void
 437 worker_runphase2(workqueue_t *wq)
 438 {
 439         tdata_t *pow1, *pow2;
 440         int batchid;
 441 
 442         for (;;) {
 443                 pthread_mutex_lock(&wq->wq_queue_lock);
 444 
 445                 if (wq->wq_ninqueue == 1) {
 446                         pthread_cond_broadcast(&wq->wq_work_avail);
 447                         pthread_mutex_unlock(&wq->wq_queue_lock);
 448 
 449                         debug(2, "%d: entering p2 completion barrier\n",
 450                             pthread_self());
 451                         if (barrier_wait(&wq->wq_bar1)) {
 452                                 pthread_mutex_lock(&wq->wq_queue_lock);
 453                                 wq->wq_alldone = 1;
 454                                 pthread_cond_signal(&wq->wq_alldone_cv);
 455                                 pthread_mutex_unlock(&wq->wq_queue_lock);
 456                         }
 457 
 458                         return;
 459                 }
 460 
 461                 if (fifo_len(wq->wq_queue) < 2) {
 462                         pthread_cond_wait(&wq->wq_work_avail,
 463                             &wq->wq_queue_lock);
 464                         pthread_mutex_unlock(&wq->wq_queue_lock);
 465                         continue;
 466                 }
 467 
 468                 /* there's work to be done! */
 469                 pow1 = fifo_remove(wq->wq_queue);
 470                 pow2 = fifo_remove(wq->wq_queue);
 471                 wq->wq_ninqueue -= 2;
 472 
 473                 batchid = wq->wq_next_batchid++;
 474 
 475                 pthread_mutex_unlock(&wq->wq_queue_lock);
 476 
 477                 debug(2, "%d: merging %p into %p\n", pthread_self(),
 478                     (void *)pow1, (void *)pow2);
 479                 merge_into_master(pow1, pow2, NULL, 0);
 480                 tdata_free(pow1);
 481 
 482                 /*
 483                  * merging is complete.  place at the tail of the queue in
 484                  * proper order.
 485                  */
 486                 pthread_mutex_lock(&wq->wq_queue_lock);
 487                 while (wq->wq_lastdonebatch + 1 != batchid) {
 488                         pthread_cond_wait(&wq->wq_done_cv,
 489                             &wq->wq_queue_lock);
 490                 }
 491 
 492                 wq->wq_lastdonebatch = batchid;
 493 
 494                 fifo_add(wq->wq_queue, pow2);
 495                 debug(2, "%d: added %p to queue, len now %d, ninqueue %d\n",
 496                     pthread_self(), (void *)pow2, fifo_len(wq->wq_queue),
 497                     wq->wq_ninqueue);
 498                 pthread_cond_broadcast(&wq->wq_done_cv);
 499                 pthread_cond_signal(&wq->wq_work_avail);
 500                 pthread_mutex_unlock(&wq->wq_queue_lock);
 501         }
 502 }
 503 
 504 /*
 505  * Main loop for worker threads.
 506  */
 507 static void *
 508 worker_thread(void *ptr)
 509 {
 510         workqueue_t *wq = ptr;
 511 
 512         worker_runphase1(wq);
 513 
 514         debug(2, "%d: entering first barrier\n", pthread_self());
 515 
 516         if (barrier_wait(&wq->wq_bar1)) {
 517 
 518                 debug(2, "%d: doing work in first barrier\n", pthread_self());
 519 
 520                 finalize_phase_one(wq);
 521 
 522                 init_phase_two(wq);
 523 
 524                 debug(2, "%d: ninqueue is %d, %d on queue\n", pthread_self(),
 525                     wq->wq_ninqueue, fifo_len(wq->wq_queue));
 526         }
 527 
 528         debug(2, "%d: entering second barrier\n", pthread_self());
 529 
 530         (void) barrier_wait(&wq->wq_bar2);
 531 
 532         debug(2, "%d: phase 1 complete\n", pthread_self());
 533 
 534         worker_runphase2(wq);
 535         return (NULL);
 536 }
 537 
 538 /*
 539  * Pass a tdata_t tree, built from an input file, off to the work queue for
 540  * consumption by worker threads.
 541  */
 542 static int
 543 merge_ctf_cb(tdata_t *td, char *name, void *arg)
 544 {
 545         workqueue_t *wq = arg;
 546 
 547         debug(3, "Adding tdata %p for processing\n", (void *)td);
 548 
 549         pthread_mutex_lock(&wq->wq_queue_lock);
 550         while (fifo_len(wq->wq_queue) > wq->wq_ithrottle) {
 551                 debug(2, "Throttling input (len = %d, throttle = %d)\n",
 552                     fifo_len(wq->wq_queue), wq->wq_ithrottle);
 553                 pthread_cond_wait(&wq->wq_work_removed, &wq->wq_queue_lock);
 554         }
 555 
 556         fifo_add(wq->wq_queue, td);
 557         debug(1, "Thread %d announcing %s\n", pthread_self(), name);
 558         pthread_cond_broadcast(&wq->wq_work_avail);
 559         pthread_mutex_unlock(&wq->wq_queue_lock);
 560 
 561         return (1);
 562 }
 563 
 564 /*
 565  * This program is intended to be invoked from a Makefile, as part of the build.
 566  * As such, in the event of a failure or user-initiated interrupt (^C), we need
 567  * to ensure that a subsequent re-make will cause ctfmerge to be executed again.
 568  * Unfortunately, ctfmerge will usually be invoked directly after (and as part
 569  * of the same Makefile rule as) a link, and will operate on the linked file
 570  * in place.  If we merely exit upon receipt of a SIGINT, a subsequent make
 571  * will notice that the *linked* file is newer than the object files, and thus
 572  * will not reinvoke ctfmerge.  The only way to ensure that a subsequent make
 573  * reinvokes ctfmerge, is to remove the file to which we are adding CTF
 574  * data (confusingly named the output file).  This means that the link will need
 575  * to happen again, but links are generally fast, and we can't allow the merge
 576  * to be skipped.
 577  *
 578  * Another possibility would be to block SIGINT entirely - to always run to
 579  * completion.  The run time of ctfmerge can, however, be measured in minutes
 580  * in some cases, so this is not a valid option.
 581  */
 582 static void
 583 handle_sig(int sig)
 584 {
 585         terminate("Caught signal %d - exiting\n", sig);
 586 }
 587 
 588 static void
 589 terminate_cleanup(void)
 590 {
 591         int dounlink = getenv("CTFMERGE_TERMINATE_NO_UNLINK") ? 0 : 1;
 592 
 593         if (tmpname != NULL && dounlink)
 594                 unlink(tmpname);
 595 
 596         if (outfile == NULL)
 597                 return;
 598 
 599         if (dounlink) {
 600                 fprintf(stderr, "Removing %s\n", outfile);
 601                 unlink(outfile);
 602         }
 603 }
 604 
 605 static void
 606 copy_ctf_data(char *srcfile, char *destfile)
 607 {
 608         tdata_t *srctd;
 609 
 610         if (read_ctf(&srcfile, 1, NULL, read_ctf_save_cb, &srctd, 1) == 0)
 611                 terminate("No CTF data found in source file %s\n", srcfile);
 612 
 613         tmpname = mktmpname(destfile, ".ctf");
 614         write_ctf(srctd, destfile, tmpname, CTF_COMPRESS);
 615         if (rename(tmpname, destfile) != 0) {
 616                 terminate("Couldn't rename temp file %s to %s", tmpname,
 617                     destfile);
 618         }
 619         free(tmpname);
 620         tdata_free(srctd);
 621 }
 622 
 623 static void
 624 wq_init(workqueue_t *wq, int nfiles)
 625 {
 626         int throttle, nslots, i;
 627 
 628         if (getenv("CTFMERGE_MAX_SLOTS"))
 629                 nslots = atoi(getenv("CTFMERGE_MAX_SLOTS"));
 630         else
 631                 nslots = MERGE_PHASE1_MAX_SLOTS;
 632 
 633         if (getenv("CTFMERGE_PHASE1_BATCH_SIZE"))
 634                 wq->wq_maxbatchsz = atoi(getenv("CTFMERGE_PHASE1_BATCH_SIZE"));
 635         else
 636                 wq->wq_maxbatchsz = MERGE_PHASE1_BATCH_SIZE;
 637 
 638         nslots = MIN(nslots, (nfiles + wq->wq_maxbatchsz - 1) /
 639             wq->wq_maxbatchsz);
 640 
 641         wq->wq_wip = xcalloc(sizeof (wip_t) * nslots);
 642         wq->wq_nwipslots = nslots;
 643         wq->wq_nthreads = MIN(sysconf(_SC_NPROCESSORS_ONLN) * 3 / 2, nslots);
 644         wq->wq_thread = xmalloc(sizeof (pthread_t) * wq->wq_nthreads);
 645 
 646         if (getenv("CTFMERGE_INPUT_THROTTLE"))
 647                 throttle = atoi(getenv("CTFMERGE_INPUT_THROTTLE"));
 648         else
 649                 throttle = MERGE_INPUT_THROTTLE_LEN;
 650         wq->wq_ithrottle = throttle * wq->wq_nthreads;
 651 
 652         debug(1, "Using %d slots, %d threads\n", wq->wq_nwipslots,
 653             wq->wq_nthreads);
 654 
 655         wq->wq_next_batchid = 0;
 656 
 657         for (i = 0; i < nslots; i++) {
 658                 pthread_mutex_init(&wq->wq_wip[i].wip_lock, NULL);
 659                 wq->wq_wip[i].wip_batchid = wq->wq_next_batchid++;
 660         }
 661 
 662         pthread_mutex_init(&wq->wq_queue_lock, NULL);
 663         wq->wq_queue = fifo_new();
 664         pthread_cond_init(&wq->wq_work_avail, NULL);
 665         pthread_cond_init(&wq->wq_work_removed, NULL);
 666         wq->wq_ninqueue = nfiles;
 667         wq->wq_nextpownum = 0;
 668 
 669         pthread_mutex_init(&wq->wq_donequeue_lock, NULL);
 670         wq->wq_donequeue = fifo_new();
 671         wq->wq_lastdonebatch = -1;
 672 
 673         pthread_cond_init(&wq->wq_done_cv, NULL);
 674 
 675         pthread_cond_init(&wq->wq_alldone_cv, NULL);
 676         wq->wq_alldone = 0;
 677 
 678         barrier_init(&wq->wq_bar1, wq->wq_nthreads);
 679         barrier_init(&wq->wq_bar2, wq->wq_nthreads);
 680 
 681         wq->wq_nomorefiles = 0;
 682 }
 683 
 684 static void
 685 start_threads(workqueue_t *wq)
 686 {
 687         sigset_t sets;
 688         int i;
 689 
 690         sigemptyset(&sets);
 691         sigaddset(&sets, SIGINT);
 692         sigaddset(&sets, SIGQUIT);
 693         sigaddset(&sets, SIGTERM);
 694         pthread_sigmask(SIG_BLOCK, &sets, NULL);
 695 
 696         for (i = 0; i < wq->wq_nthreads; i++) {
 697                 pthread_create(&wq->wq_thread[i], NULL,
 698                     worker_thread, wq);
 699         }
 700 
 701         sigset(SIGINT, handle_sig);
 702         sigset(SIGQUIT, handle_sig);
 703         sigset(SIGTERM, handle_sig);
 704         pthread_sigmask(SIG_UNBLOCK, &sets, NULL);
 705 }
 706 
 707 static void
 708 join_threads(workqueue_t *wq)
 709 {
 710         int i;
 711 
 712         for (i = 0; i < wq->wq_nthreads; i++) {
 713                 pthread_join(wq->wq_thread[i], NULL);
 714         }
 715 }
 716 
 717 static int
 718 strcompare(const void *p1, const void *p2)
 719 {
 720         char *s1 = *((char **)p1);
 721         char *s2 = *((char **)p2);
 722 
 723         return (strcmp(s1, s2));
 724 }
 725 
 726 /*
 727  * Core work queue structure; passed to worker threads on thread creation
 728  * as the main point of coordination.  Allocate as a static structure; we
 729  * could have put this into a local variable in main, but passing a pointer
 730  * into your stack to another thread is fragile at best and leads to some
 731  * hard-to-debug failure modes.
 732  */
 733 static workqueue_t wq;
 734 
 735 int
 736 main(int argc, char **argv)
 737 {
 738         tdata_t *mstrtd, *savetd;
 739         char *uniqfile = NULL, *uniqlabel = NULL;
 740         char *withfile = NULL;
 741         char *label = NULL;
 742         char **ifiles, **tifiles;
 743         int verbose = 0, docopy = 0;
 744         int write_fuzzy_match = 0;
 745         int require_ctf = 0;
 746         int nifiles, nielems;
 747         int c, i, idx, tidx, err;
 748 
 749         progname = basename(argv[0]);
 750 
 751         ctf_altexec("CTFMERGE_ALTEXEC", argc, argv);
 752 
 753         if (getenv("CTFMERGE_DEBUG_LEVEL"))
 754                 debug_level = atoi(getenv("CTFMERGE_DEBUG_LEVEL"));
 755 
 756         err = 0;
 757         while ((c = getopt(argc, argv, ":cd:D:fl:L:o:tvw:s")) != EOF) {
 758                 switch (c) {
 759                 case 'c':
 760                         docopy = 1;
 761                         break;
 762                 case 'd':
 763                         /* Uniquify against `uniqfile' */
 764                         uniqfile = optarg;
 765                         break;
 766                 case 'D':
 767                         /* Uniquify against label `uniqlabel' in `uniqfile' */
 768                         uniqlabel = optarg;
 769                         break;
 770                 case 'f':
 771                         write_fuzzy_match = CTF_FUZZY_MATCH;
 772                         break;
 773                 case 'l':
 774                         /* Label merged types with `label' */
 775                         label = optarg;
 776                         break;
 777                 case 'L':
 778                         /* Label merged types with getenv(`label`) */
 779                         if ((label = getenv(optarg)) == NULL)
 780                                 label = CTF_DEFAULT_LABEL;
 781                         break;
 782                 case 'o':
 783                         /* Place merged types in CTF section in `outfile' */
 784                         outfile = optarg;
 785                         break;
 786                 case 't':
 787                         /* Insist *all* object files built from C have CTF */
 788                         require_ctf = 1;
 789                         break;
 790                 case 'v':
 791                         /* More debugging information */
 792                         verbose = 1;
 793                         break;
 794                 case 'w':
 795                         /* Additive merge with data from `withfile' */
 796                         withfile = optarg;
 797                         break;
 798                 case 's':
 799                         /* use the dynsym rather than the symtab */
 800                         dynsym = CTF_USE_DYNSYM;
 801                         break;
 802                 default:
 803                         usage();
 804                         exit(2);
 805                 }
 806         }
 807 
 808         /* Validate arguments */
 809         if (docopy) {
 810                 if (uniqfile != NULL || uniqlabel != NULL || label != NULL ||
 811                     outfile != NULL || withfile != NULL || dynsym != 0)
 812                         err++;
 813 
 814                 if (argc - optind != 2)
 815                         err++;
 816         } else {
 817                 if (uniqfile != NULL && withfile != NULL)
 818                         err++;
 819 
 820                 if (uniqlabel != NULL && uniqfile == NULL)
 821                         err++;
 822 
 823                 if (outfile == NULL || label == NULL)
 824                         err++;
 825 
 826                 if (argc - optind == 0)
 827                         err++;
 828         }
 829 
 830         if (err) {
 831                 usage();
 832                 exit(2);
 833         }
 834 
 835         if (uniqfile && access(uniqfile, R_OK) != 0) {
 836                 warning("Uniquification file %s couldn't be opened and "
 837                     "will be ignored.\n", uniqfile);
 838                 uniqfile = NULL;
 839         }
 840         if (withfile && access(withfile, R_OK) != 0) {
 841                 warning("With file %s couldn't be opened and will be "
 842                     "ignored.\n", withfile);
 843                 withfile = NULL;
 844         }
 845         if (outfile && access(outfile, R_OK|W_OK) != 0)
 846                 terminate("Cannot open output file %s for r/w", outfile);
 847 
 848         /*
 849          * This is ugly, but we don't want to have to have a separate tool
 850          * (yet) just for copying an ELF section with our specific requirements,
 851          * so we shoe-horn a copier into ctfmerge.
 852          */
 853         if (docopy) {
 854                 copy_ctf_data(argv[optind], argv[optind + 1]);
 855 
 856                 exit(0);
 857         }
 858 
 859         set_terminate_cleanup(terminate_cleanup);
 860 
 861         /* Sort the input files and strip out duplicates */
 862         nifiles = argc - optind;
 863         ifiles = xmalloc(sizeof (char *) * nifiles);
 864         tifiles = xmalloc(sizeof (char *) * nifiles);
 865 
 866         for (i = 0; i < nifiles; i++)
 867                 tifiles[i] = argv[optind + i];
 868         qsort(tifiles, nifiles, sizeof (char *), (int (*)())strcompare);
 869 
 870         ifiles[0] = tifiles[0];
 871         for (idx = 0, tidx = 1; tidx < nifiles; tidx++) {
 872                 if (strcmp(ifiles[idx], tifiles[tidx]) != 0)
 873                         ifiles[++idx] = tifiles[tidx];
 874         }
 875         nifiles = idx + 1;
 876 
 877         /* Make sure they all exist */
 878         if ((nielems = count_files(ifiles, nifiles)) < 0)
 879                 terminate("Some input files were inaccessible\n");
 880 
 881         /* Prepare for the merge */
 882         wq_init(&wq, nielems);
 883 
 884         start_threads(&wq);
 885 
 886         /*
 887          * Start the merge
 888          *
 889          * We're reading everything from each of the object files, so we
 890          * don't need to specify labels.
 891          */
 892         if (read_ctf(ifiles, nifiles, NULL, merge_ctf_cb,
 893             &wq, require_ctf) == 0) {
 894                 /*
 895                  * If we're verifying that C files have CTF, it's safe to
 896                  * assume that in this case, we're building only from assembly
 897                  * inputs.
 898                  */
 899                 if (require_ctf)
 900                         exit(0);
 901                 terminate("No ctf sections found to merge\n");
 902         }
 903 
 904         pthread_mutex_lock(&wq.wq_queue_lock);
 905         wq.wq_nomorefiles = 1;
 906         pthread_cond_broadcast(&wq.wq_work_avail);
 907         pthread_mutex_unlock(&wq.wq_queue_lock);
 908 
 909         pthread_mutex_lock(&wq.wq_queue_lock);
 910         while (wq.wq_alldone == 0)
 911                 pthread_cond_wait(&wq.wq_alldone_cv, &wq.wq_queue_lock);
 912         pthread_mutex_unlock(&wq.wq_queue_lock);
 913 
 914         join_threads(&wq);
 915 
 916         /*
 917          * All requested files have been merged, with the resulting tree in
 918          * mstrtd.  savetd is the tree that will be placed into the output file.
 919          *
 920          * Regardless of whether we're doing a normal uniquification or an
 921          * additive merge, we need a type tree that has been uniquified
 922          * against uniqfile or withfile, as appropriate.
 923          *
 924          * If we're doing a uniquification, we stuff the resulting tree into
 925          * outfile.  Otherwise, we add the tree to the tree already in withfile.
 926          */
 927         assert(fifo_len(wq.wq_queue) == 1);
 928         mstrtd = fifo_remove(wq.wq_queue);
 929 
 930         if (verbose || debug_level) {
 931                 debug(2, "Statistics for td %p\n", (void *)mstrtd);
 932 
 933                 iidesc_stats(mstrtd->td_iihash);
 934         }
 935 
 936         if (uniqfile != NULL || withfile != NULL) {
 937                 char *reffile, *reflabel = NULL;
 938                 tdata_t *reftd;
 939 
 940                 if (uniqfile != NULL) {
 941                         reffile = uniqfile;
 942                         reflabel = uniqlabel;
 943                 } else
 944                         reffile = withfile;
 945 
 946                 if (read_ctf(&reffile, 1, reflabel, read_ctf_save_cb,
 947                     &reftd, require_ctf) == 0) {
 948                         terminate("No CTF data found in reference file %s\n",
 949                             reffile);
 950                 }
 951 
 952                 savetd = tdata_new();
 953 
 954                 if (CTF_TYPE_ISCHILD(reftd->td_nextid))
 955                         terminate("No room for additional types in master\n");
 956 
 957                 savetd->td_nextid = withfile ? reftd->td_nextid :
 958                     CTF_INDEX_TO_TYPE(1, TRUE);
 959                 merge_into_master(mstrtd, reftd, savetd, 0);
 960 
 961                 tdata_label_add(savetd, label, CTF_LABEL_LASTIDX);
 962 
 963                 if (withfile) {
 964                         /*
 965                          * savetd holds the new data to be added to the withfile
 966                          */
 967                         tdata_t *withtd = reftd;
 968 
 969                         tdata_merge(withtd, savetd);
 970 
 971                         savetd = withtd;
 972                 } else {
 973                         char uniqname[MAXPATHLEN];
 974                         labelent_t *parle;
 975 
 976                         parle = tdata_label_top(reftd);
 977 
 978                         savetd->td_parlabel = xstrdup(parle->le_name);
 979 
 980                         strncpy(uniqname, reffile, sizeof (uniqname));
 981                         uniqname[MAXPATHLEN - 1] = '\0';
 982                         savetd->td_parname = xstrdup(basename(uniqname));
 983                 }
 984 
 985         } else {
 986                 /*
 987                  * No post processing.  Write the merged tree as-is into the
 988                  * output file.
 989                  */
 990                 tdata_label_free(mstrtd);
 991                 tdata_label_add(mstrtd, label, CTF_LABEL_LASTIDX);
 992 
 993                 savetd = mstrtd;
 994         }
 995 
 996         tmpname = mktmpname(outfile, ".ctf");
 997         write_ctf(savetd, outfile, tmpname,
 998             CTF_COMPRESS | write_fuzzy_match | dynsym);
 999         if (rename(tmpname, outfile) != 0)
1000                 terminate("Couldn't rename output temp file %s", tmpname);
1001         free(tmpname);
1002 
1003         return (0);
1004 }