xref: /titanic_51/usr/src/tools/ctf/cvt/ctfmerge.c (revision ce0d9371c4da921f289a8bc7fd846d3bf1b8cca7)
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(workqueue_t *wq)
509 {
510 	worker_runphase1(wq);
511 
512 	debug(2, "%d: entering first barrier\n", pthread_self());
513 
514 	if (barrier_wait(&wq->wq_bar1)) {
515 
516 		debug(2, "%d: doing work in first barrier\n", pthread_self());
517 
518 		finalize_phase_one(wq);
519 
520 		init_phase_two(wq);
521 
522 		debug(2, "%d: ninqueue is %d, %d on queue\n", pthread_self(),
523 		    wq->wq_ninqueue, fifo_len(wq->wq_queue));
524 	}
525 
526 	debug(2, "%d: entering second barrier\n", pthread_self());
527 
528 	(void) barrier_wait(&wq->wq_bar2);
529 
530 	debug(2, "%d: phase 1 complete\n", pthread_self());
531 
532 	worker_runphase2(wq);
533 }
534 
535 /*
536  * Pass a tdata_t tree, built from an input file, off to the work queue for
537  * consumption by worker threads.
538  */
539 static int
540 merge_ctf_cb(tdata_t *td, char *name, void *arg)
541 {
542 	workqueue_t *wq = arg;
543 
544 	debug(3, "Adding tdata %p for processing\n", (void *)td);
545 
546 	pthread_mutex_lock(&wq->wq_queue_lock);
547 	while (fifo_len(wq->wq_queue) > wq->wq_ithrottle) {
548 		debug(2, "Throttling input (len = %d, throttle = %d)\n",
549 		    fifo_len(wq->wq_queue), wq->wq_ithrottle);
550 		pthread_cond_wait(&wq->wq_work_removed, &wq->wq_queue_lock);
551 	}
552 
553 	fifo_add(wq->wq_queue, td);
554 	debug(1, "Thread %d announcing %s\n", pthread_self(), name);
555 	pthread_cond_broadcast(&wq->wq_work_avail);
556 	pthread_mutex_unlock(&wq->wq_queue_lock);
557 
558 	return (1);
559 }
560 
561 /*
562  * This program is intended to be invoked from a Makefile, as part of the build.
563  * As such, in the event of a failure or user-initiated interrupt (^C), we need
564  * to ensure that a subsequent re-make will cause ctfmerge to be executed again.
565  * Unfortunately, ctfmerge will usually be invoked directly after (and as part
566  * of the same Makefile rule as) a link, and will operate on the linked file
567  * in place.  If we merely exit upon receipt of a SIGINT, a subsequent make
568  * will notice that the *linked* file is newer than the object files, and thus
569  * will not reinvoke ctfmerge.  The only way to ensure that a subsequent make
570  * reinvokes ctfmerge, is to remove the file to which we are adding CTF
571  * data (confusingly named the output file).  This means that the link will need
572  * to happen again, but links are generally fast, and we can't allow the merge
573  * to be skipped.
574  *
575  * Another possibility would be to block SIGINT entirely - to always run to
576  * completion.  The run time of ctfmerge can, however, be measured in minutes
577  * in some cases, so this is not a valid option.
578  */
579 static void
580 handle_sig(int sig)
581 {
582 	terminate("Caught signal %d - exiting\n", sig);
583 }
584 
585 static void
586 terminate_cleanup(void)
587 {
588 	int dounlink = getenv("CTFMERGE_TERMINATE_NO_UNLINK") ? 0 : 1;
589 
590 	if (tmpname != NULL && dounlink)
591 		unlink(tmpname);
592 
593 	if (outfile == NULL)
594 		return;
595 
596 	if (dounlink) {
597 		fprintf(stderr, "Removing %s\n", outfile);
598 		unlink(outfile);
599 	}
600 }
601 
602 static void
603 copy_ctf_data(char *srcfile, char *destfile)
604 {
605 	tdata_t *srctd;
606 
607 	if (read_ctf(&srcfile, 1, NULL, read_ctf_save_cb, &srctd, 1) == 0)
608 		terminate("No CTF data found in source file %s\n", srcfile);
609 
610 	tmpname = mktmpname(destfile, ".ctf");
611 	write_ctf(srctd, destfile, tmpname, CTF_COMPRESS);
612 	if (rename(tmpname, destfile) != 0) {
613 		terminate("Couldn't rename temp file %s to %s", tmpname,
614 		    destfile);
615 	}
616 	free(tmpname);
617 	tdata_free(srctd);
618 }
619 
620 static void
621 wq_init(workqueue_t *wq, int nfiles)
622 {
623 	int throttle, nslots, i;
624 
625 	if (getenv("CTFMERGE_MAX_SLOTS"))
626 		nslots = atoi(getenv("CTFMERGE_MAX_SLOTS"));
627 	else
628 		nslots = MERGE_PHASE1_MAX_SLOTS;
629 
630 	if (getenv("CTFMERGE_PHASE1_BATCH_SIZE"))
631 		wq->wq_maxbatchsz = atoi(getenv("CTFMERGE_PHASE1_BATCH_SIZE"));
632 	else
633 		wq->wq_maxbatchsz = MERGE_PHASE1_BATCH_SIZE;
634 
635 	nslots = MIN(nslots, (nfiles + wq->wq_maxbatchsz - 1) /
636 	    wq->wq_maxbatchsz);
637 
638 	wq->wq_wip = xcalloc(sizeof (wip_t) * nslots);
639 	wq->wq_nwipslots = nslots;
640 	wq->wq_nthreads = MIN(sysconf(_SC_NPROCESSORS_ONLN) * 3 / 2, nslots);
641 	wq->wq_thread = xmalloc(sizeof (pthread_t) * wq->wq_nthreads);
642 
643 	if (getenv("CTFMERGE_INPUT_THROTTLE"))
644 		throttle = atoi(getenv("CTFMERGE_INPUT_THROTTLE"));
645 	else
646 		throttle = MERGE_INPUT_THROTTLE_LEN;
647 	wq->wq_ithrottle = throttle * wq->wq_nthreads;
648 
649 	debug(1, "Using %d slots, %d threads\n", wq->wq_nwipslots,
650 	    wq->wq_nthreads);
651 
652 	wq->wq_next_batchid = 0;
653 
654 	for (i = 0; i < nslots; i++) {
655 		pthread_mutex_init(&wq->wq_wip[i].wip_lock, NULL);
656 		wq->wq_wip[i].wip_batchid = wq->wq_next_batchid++;
657 	}
658 
659 	pthread_mutex_init(&wq->wq_queue_lock, NULL);
660 	wq->wq_queue = fifo_new();
661 	pthread_cond_init(&wq->wq_work_avail, NULL);
662 	pthread_cond_init(&wq->wq_work_removed, NULL);
663 	wq->wq_ninqueue = nfiles;
664 	wq->wq_nextpownum = 0;
665 
666 	pthread_mutex_init(&wq->wq_donequeue_lock, NULL);
667 	wq->wq_donequeue = fifo_new();
668 	wq->wq_lastdonebatch = -1;
669 
670 	pthread_cond_init(&wq->wq_done_cv, NULL);
671 
672 	pthread_cond_init(&wq->wq_alldone_cv, NULL);
673 	wq->wq_alldone = 0;
674 
675 	barrier_init(&wq->wq_bar1, wq->wq_nthreads);
676 	barrier_init(&wq->wq_bar2, wq->wq_nthreads);
677 
678 	wq->wq_nomorefiles = 0;
679 }
680 
681 static void
682 start_threads(workqueue_t *wq)
683 {
684 	sigset_t sets;
685 	int i;
686 
687 	sigemptyset(&sets);
688 	sigaddset(&sets, SIGINT);
689 	sigaddset(&sets, SIGQUIT);
690 	sigaddset(&sets, SIGTERM);
691 	pthread_sigmask(SIG_BLOCK, &sets, NULL);
692 
693 	for (i = 0; i < wq->wq_nthreads; i++) {
694 		pthread_create(&wq->wq_thread[i], NULL,
695 		    (void *(*)(void *))worker_thread, wq);
696 	}
697 
698 	sigset(SIGINT, handle_sig);
699 	sigset(SIGQUIT, handle_sig);
700 	sigset(SIGTERM, handle_sig);
701 	pthread_sigmask(SIG_UNBLOCK, &sets, NULL);
702 }
703 
704 static void
705 join_threads(workqueue_t *wq)
706 {
707 	int i;
708 
709 	for (i = 0; i < wq->wq_nthreads; i++) {
710 		pthread_join(wq->wq_thread[i], NULL);
711 	}
712 }
713 
714 static int
715 strcompare(const void *p1, const void *p2)
716 {
717 	char *s1 = *((char **)p1);
718 	char *s2 = *((char **)p2);
719 
720 	return (strcmp(s1, s2));
721 }
722 
723 /*
724  * Core work queue structure; passed to worker threads on thread creation
725  * as the main point of coordination.  Allocate as a static structure; we
726  * could have put this into a local variable in main, but passing a pointer
727  * into your stack to another thread is fragile at best and leads to some
728  * hard-to-debug failure modes.
729  */
730 static workqueue_t wq;
731 
732 int
733 main(int argc, char **argv)
734 {
735 	tdata_t *mstrtd, *savetd;
736 	char *uniqfile = NULL, *uniqlabel = NULL;
737 	char *withfile = NULL;
738 	char *label = NULL;
739 	char **ifiles, **tifiles;
740 	int verbose = 0, docopy = 0;
741 	int write_fuzzy_match = 0;
742 	int require_ctf = 0;
743 	int nifiles, nielems;
744 	int c, i, idx, tidx, err;
745 
746 	progname = basename(argv[0]);
747 
748 	if (getenv("CTFMERGE_DEBUG_LEVEL"))
749 		debug_level = atoi(getenv("CTFMERGE_DEBUG_LEVEL"));
750 
751 	err = 0;
752 	while ((c = getopt(argc, argv, ":cd:D:fl:L:o:tvw:s")) != EOF) {
753 		switch (c) {
754 		case 'c':
755 			docopy = 1;
756 			break;
757 		case 'd':
758 			/* Uniquify against `uniqfile' */
759 			uniqfile = optarg;
760 			break;
761 		case 'D':
762 			/* Uniquify against label `uniqlabel' in `uniqfile' */
763 			uniqlabel = optarg;
764 			break;
765 		case 'f':
766 			write_fuzzy_match = CTF_FUZZY_MATCH;
767 			break;
768 		case 'l':
769 			/* Label merged types with `label' */
770 			label = optarg;
771 			break;
772 		case 'L':
773 			/* Label merged types with getenv(`label`) */
774 			if ((label = getenv(optarg)) == NULL)
775 				label = CTF_DEFAULT_LABEL;
776 			break;
777 		case 'o':
778 			/* Place merged types in CTF section in `outfile' */
779 			outfile = optarg;
780 			break;
781 		case 't':
782 			/* Insist *all* object files built from C have CTF */
783 			require_ctf = 1;
784 			break;
785 		case 'v':
786 			/* More debugging information */
787 			verbose = 1;
788 			break;
789 		case 'w':
790 			/* Additive merge with data from `withfile' */
791 			withfile = optarg;
792 			break;
793 		case 's':
794 			/* use the dynsym rather than the symtab */
795 			dynsym = CTF_USE_DYNSYM;
796 			break;
797 		default:
798 			usage();
799 			exit(2);
800 		}
801 	}
802 
803 	/* Validate arguments */
804 	if (docopy) {
805 		if (uniqfile != NULL || uniqlabel != NULL || label != NULL ||
806 		    outfile != NULL || withfile != NULL || dynsym != 0)
807 			err++;
808 
809 		if (argc - optind != 2)
810 			err++;
811 	} else {
812 		if (uniqfile != NULL && withfile != NULL)
813 			err++;
814 
815 		if (uniqlabel != NULL && uniqfile == NULL)
816 			err++;
817 
818 		if (outfile == NULL || label == NULL)
819 			err++;
820 
821 		if (argc - optind == 0)
822 			err++;
823 	}
824 
825 	if (err) {
826 		usage();
827 		exit(2);
828 	}
829 
830 	if (uniqfile && access(uniqfile, R_OK) != 0) {
831 		warning("Uniquification file %s couldn't be opened and "
832 		    "will be ignored.\n", uniqfile);
833 		uniqfile = NULL;
834 	}
835 	if (withfile && access(withfile, R_OK) != 0) {
836 		warning("With file %s couldn't be opened and will be "
837 		    "ignored.\n", withfile);
838 		withfile = NULL;
839 	}
840 	if (outfile && access(outfile, R_OK|W_OK) != 0)
841 		terminate("Cannot open output file %s for r/w", outfile);
842 
843 	/*
844 	 * This is ugly, but we don't want to have to have a separate tool
845 	 * (yet) just for copying an ELF section with our specific requirements,
846 	 * so we shoe-horn a copier into ctfmerge.
847 	 */
848 	if (docopy) {
849 		copy_ctf_data(argv[optind], argv[optind + 1]);
850 
851 		exit(0);
852 	}
853 
854 	set_terminate_cleanup(terminate_cleanup);
855 
856 	/* Sort the input files and strip out duplicates */
857 	nifiles = argc - optind;
858 	ifiles = xmalloc(sizeof (char *) * nifiles);
859 	tifiles = xmalloc(sizeof (char *) * nifiles);
860 
861 	for (i = 0; i < nifiles; i++)
862 		tifiles[i] = argv[optind + i];
863 	qsort(tifiles, nifiles, sizeof (char *), (int (*)())strcompare);
864 
865 	ifiles[0] = tifiles[0];
866 	for (idx = 0, tidx = 1; tidx < nifiles; tidx++) {
867 		if (strcmp(ifiles[idx], tifiles[tidx]) != 0)
868 			ifiles[++idx] = tifiles[tidx];
869 	}
870 	nifiles = idx + 1;
871 
872 	/* Make sure they all exist */
873 	if ((nielems = count_files(ifiles, nifiles)) < 0)
874 		terminate("Some input files were inaccessible\n");
875 
876 	/* Prepare for the merge */
877 	wq_init(&wq, nielems);
878 
879 	start_threads(&wq);
880 
881 	/*
882 	 * Start the merge
883 	 *
884 	 * We're reading everything from each of the object files, so we
885 	 * don't need to specify labels.
886 	 */
887 	if (read_ctf(ifiles, nifiles, NULL, merge_ctf_cb,
888 	    &wq, require_ctf) == 0) {
889 		/*
890 		 * If we're verifying that C files have CTF, it's safe to
891 		 * assume that in this case, we're building only from assembly
892 		 * inputs.
893 		 */
894 		if (require_ctf)
895 			exit(0);
896 		terminate("No ctf sections found to merge\n");
897 	}
898 
899 	pthread_mutex_lock(&wq.wq_queue_lock);
900 	wq.wq_nomorefiles = 1;
901 	pthread_cond_broadcast(&wq.wq_work_avail);
902 	pthread_mutex_unlock(&wq.wq_queue_lock);
903 
904 	pthread_mutex_lock(&wq.wq_queue_lock);
905 	while (wq.wq_alldone == 0)
906 		pthread_cond_wait(&wq.wq_alldone_cv, &wq.wq_queue_lock);
907 	pthread_mutex_unlock(&wq.wq_queue_lock);
908 
909 	join_threads(&wq);
910 
911 	/*
912 	 * All requested files have been merged, with the resulting tree in
913 	 * mstrtd.  savetd is the tree that will be placed into the output file.
914 	 *
915 	 * Regardless of whether we're doing a normal uniquification or an
916 	 * additive merge, we need a type tree that has been uniquified
917 	 * against uniqfile or withfile, as appropriate.
918 	 *
919 	 * If we're doing a uniquification, we stuff the resulting tree into
920 	 * outfile.  Otherwise, we add the tree to the tree already in withfile.
921 	 */
922 	assert(fifo_len(wq.wq_queue) == 1);
923 	mstrtd = fifo_remove(wq.wq_queue);
924 
925 	if (verbose || debug_level) {
926 		debug(2, "Statistics for td %p\n", (void *)mstrtd);
927 
928 		iidesc_stats(mstrtd->td_iihash);
929 	}
930 
931 	if (uniqfile != NULL || withfile != NULL) {
932 		char *reffile, *reflabel = NULL;
933 		tdata_t *reftd;
934 
935 		if (uniqfile != NULL) {
936 			reffile = uniqfile;
937 			reflabel = uniqlabel;
938 		} else
939 			reffile = withfile;
940 
941 		if (read_ctf(&reffile, 1, reflabel, read_ctf_save_cb,
942 		    &reftd, require_ctf) == 0) {
943 			terminate("No CTF data found in reference file %s\n",
944 			    reffile);
945 		}
946 
947 		savetd = tdata_new();
948 
949 		if (CTF_TYPE_ISCHILD(reftd->td_nextid))
950 			terminate("No room for additional types in master\n");
951 
952 		savetd->td_nextid = withfile ? reftd->td_nextid :
953 		    CTF_INDEX_TO_TYPE(1, TRUE);
954 		merge_into_master(mstrtd, reftd, savetd, 0);
955 
956 		tdata_label_add(savetd, label, CTF_LABEL_LASTIDX);
957 
958 		if (withfile) {
959 			/*
960 			 * savetd holds the new data to be added to the withfile
961 			 */
962 			tdata_t *withtd = reftd;
963 
964 			tdata_merge(withtd, savetd);
965 
966 			savetd = withtd;
967 		} else {
968 			char uniqname[MAXPATHLEN];
969 			labelent_t *parle;
970 
971 			parle = tdata_label_top(reftd);
972 
973 			savetd->td_parlabel = xstrdup(parle->le_name);
974 
975 			strncpy(uniqname, reffile, sizeof (uniqname));
976 			uniqname[MAXPATHLEN - 1] = '\0';
977 			savetd->td_parname = xstrdup(basename(uniqname));
978 		}
979 
980 	} else {
981 		/*
982 		 * No post processing.  Write the merged tree as-is into the
983 		 * output file.
984 		 */
985 		tdata_label_free(mstrtd);
986 		tdata_label_add(mstrtd, label, CTF_LABEL_LASTIDX);
987 
988 		savetd = mstrtd;
989 	}
990 
991 	tmpname = mktmpname(outfile, ".ctf");
992 	write_ctf(savetd, outfile, tmpname,
993 	    CTF_COMPRESS | write_fuzzy_match | dynsym);
994 	if (rename(tmpname, outfile) != 0)
995 		terminate("Couldn't rename output temp file %s", tmpname);
996 	free(tmpname);
997 
998 	return (0);
999 }
1000