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