xref: /netbsd-src/external/gpl3/gdb/dist/libctf/ctf-link.c (revision 53b02e147d4ed531c0d2a5ca9b3e8026ba3e99b5)
1 /* CTF linking.
2    Copyright (C) 2019-2020 Free Software Foundation, Inc.
3 
4    This file is part of libctf.
5 
6    libctf is free software; you can redistribute it and/or modify it under
7    the terms of the GNU General Public License as published by the Free
8    Software Foundation; either version 3, or (at your option) any later
9    version.
10 
11    This program is distributed in the hope that it will be useful, but
12    WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14    See the GNU General Public License for more details.
15 
16    You should have received a copy of the GNU General Public License
17    along with this program; see the file COPYING.  If not see
18    <http://www.gnu.org/licenses/>.  */
19 
20 #include <ctf-impl.h>
21 #include <string.h>
22 
23 #if defined (PIC)
24 #pragma weak ctf_open
25 #endif
26 
27 /* Type tracking machinery.  */
28 
29 /* Record the correspondence between a source and ctf_add_type()-added
30    destination type: both types are translated into parent type IDs if need be,
31    so they relate to the actual container they are in.  Outside controlled
32    circumstances (like linking) it is probably not useful to do more than
33    compare these pointers, since there is nothing stopping the user closing the
34    source container whenever they want to.
35 
36    Our OOM handling here is just to not do anything, because this is called deep
37    enough in the call stack that doing anything useful is painfully difficult:
38    the worst consequence if we do OOM is a bit of type duplication anyway.  */
39 
40 void
41 ctf_add_type_mapping (ctf_file_t *src_fp, ctf_id_t src_type,
42 		      ctf_file_t *dst_fp, ctf_id_t dst_type)
43 {
44   if (LCTF_TYPE_ISPARENT (src_fp, src_type) && src_fp->ctf_parent)
45     src_fp = src_fp->ctf_parent;
46 
47   src_type = LCTF_TYPE_TO_INDEX(src_fp, src_type);
48 
49   if (LCTF_TYPE_ISPARENT (dst_fp, dst_type) && dst_fp->ctf_parent)
50     dst_fp = dst_fp->ctf_parent;
51 
52   dst_type = LCTF_TYPE_TO_INDEX(dst_fp, dst_type);
53 
54   /* This dynhash is a bit tricky: it has a multivalued (structural) key, so we
55      need to use the sized-hash machinery to generate key hashing and equality
56      functions.  */
57 
58   if (dst_fp->ctf_link_type_mapping == NULL)
59     {
60       ctf_hash_fun f = ctf_hash_type_key;
61       ctf_hash_eq_fun e = ctf_hash_eq_type_key;
62 
63       if ((dst_fp->ctf_link_type_mapping = ctf_dynhash_create (f, e, free,
64 							       NULL)) == NULL)
65 	return;
66     }
67 
68   ctf_link_type_key_t *key;
69   key = calloc (1, sizeof (struct ctf_link_type_key));
70   if (!key)
71     return;
72 
73   key->cltk_fp = src_fp;
74   key->cltk_idx = src_type;
75 
76   /* No OOM checking needed, because if this doesn't work the worst we'll do is
77      add a few more duplicate types (which will probably run out of memory
78      anyway).  */
79   ctf_dynhash_insert (dst_fp->ctf_link_type_mapping, key,
80 		      (void *) (uintptr_t) dst_type);
81 }
82 
83 /* Look up a type mapping: return 0 if none.  The DST_FP is modified to point to
84    the parent if need be.  The ID returned is from the dst_fp's perspective.  */
85 ctf_id_t
86 ctf_type_mapping (ctf_file_t *src_fp, ctf_id_t src_type, ctf_file_t **dst_fp)
87 {
88   ctf_link_type_key_t key;
89   ctf_file_t *target_fp = *dst_fp;
90   ctf_id_t dst_type = 0;
91 
92   if (LCTF_TYPE_ISPARENT (src_fp, src_type) && src_fp->ctf_parent)
93     src_fp = src_fp->ctf_parent;
94 
95   src_type = LCTF_TYPE_TO_INDEX(src_fp, src_type);
96   key.cltk_fp = src_fp;
97   key.cltk_idx = src_type;
98 
99   if (target_fp->ctf_link_type_mapping)
100     dst_type = (uintptr_t) ctf_dynhash_lookup (target_fp->ctf_link_type_mapping,
101 					       &key);
102 
103   if (dst_type != 0)
104     {
105       dst_type = LCTF_INDEX_TO_TYPE (target_fp, dst_type,
106 				     target_fp->ctf_parent != NULL);
107       *dst_fp = target_fp;
108       return dst_type;
109     }
110 
111   if (target_fp->ctf_parent)
112     target_fp = target_fp->ctf_parent;
113   else
114     return 0;
115 
116   if (target_fp->ctf_link_type_mapping)
117     dst_type = (uintptr_t) ctf_dynhash_lookup (target_fp->ctf_link_type_mapping,
118 					       &key);
119 
120   if (dst_type)
121     dst_type = LCTF_INDEX_TO_TYPE (target_fp, dst_type,
122 				   target_fp->ctf_parent != NULL);
123 
124   *dst_fp = target_fp;
125   return dst_type;
126 }
127 
128 /* Linker machinery.
129 
130    CTF linking consists of adding CTF archives full of content to be merged into
131    this one to the current file (which must be writable) by calling
132    ctf_link_add_ctf().  Once this is done, a call to ctf_link() will merge the
133    type tables together, generating new CTF files as needed, with this one as a
134    parent, to contain types from the inputs which conflict.
135    ctf_link_add_strtab() takes a callback which provides string/offset pairs to
136    be added to the external symbol table and deduplicated from all CTF string
137    tables in the output link; ctf_link_shuffle_syms() takes a callback which
138    provides symtab entries in ascending order, and shuffles the function and
139    data sections to match; and ctf_link_write() emits a CTF file (if there are
140    no conflicts requiring per-compilation-unit sub-CTF files) or CTF archives
141    (otherwise) and returns it, suitable for addition in the .ctf section of the
142    output.  */
143 
144 /* Return the name of the compilation unit this CTF dict or its parent applies
145    to, or a non-null string otherwise: prefer the parent.  Used in debugging
146    output.  Sometimes used for outputs too.  */
147 const char *
148 ctf_link_input_name (ctf_file_t *fp)
149 {
150   if (fp->ctf_parent && fp->ctf_parent->ctf_cuname)
151     return fp->ctf_parent->ctf_cuname;
152   else if (fp->ctf_cuname)
153     return fp->ctf_cuname;
154   else
155     return "(unnamed)";
156 }
157 
158 /* The linker inputs look like this.  clin_fp is used for short-circuited
159    CU-mapped links that can entirely avoid the first link phase in some
160    situations in favour of just passing on the contained ctf_file_t: it is
161    always the sole ctf_file_t inside the corresponding clin_arc.  If set, it
162    gets assigned directly to the final link inputs and freed from there, so it
163    never gets explicitly freed in the ctf_link_input.  */
164 typedef struct ctf_link_input
165 {
166   const char *clin_filename;
167   ctf_archive_t *clin_arc;
168   ctf_file_t *clin_fp;
169   int n;
170 } ctf_link_input_t;
171 
172 static void
173 ctf_link_input_close (void *input)
174 {
175   ctf_link_input_t *i = (ctf_link_input_t *) input;
176   if (i->clin_arc)
177     ctf_arc_close (i->clin_arc);
178   free (i);
179 }
180 
181 /* Like ctf_link_add_ctf, below, but with no error-checking, so it can be called
182    in the middle of an ongoing link.  */
183 static int
184 ctf_link_add_ctf_internal (ctf_file_t *fp, ctf_archive_t *ctf,
185 			   ctf_file_t *fp_input, const char *name)
186 {
187   ctf_link_input_t *input = NULL;
188   char *dupname = NULL;
189 
190   if ((input = calloc (1, sizeof (ctf_link_input_t))) == NULL)
191     goto oom;
192 
193   if ((dupname = strdup (name)) == NULL)
194     goto oom;
195 
196   input->clin_arc = ctf;
197   input->clin_fp = fp_input;
198   input->clin_filename = dupname;
199   input->n = ctf_dynhash_elements (fp->ctf_link_inputs);
200 
201   if (ctf_dynhash_insert (fp->ctf_link_inputs, dupname, input) < 0)
202     goto oom;
203 
204   return 0;
205  oom:
206   free (input);
207   free (dupname);
208   return ctf_set_errno (fp, ENOMEM);
209 }
210 
211 /* Add a file, memory buffer, or unopened file (by name) to a link.
212 
213    You can call this with:
214 
215     CTF and NAME: link the passed ctf_archive_t, with the given NAME.
216     NAME alone: open NAME as a CTF file when needed.
217     BUF and NAME: open the BUF (of length N) as CTF, with the given NAME.  (Not
218     yet implemented.)
219 
220     Passed in CTF args are owned by the dictionary and will be freed by it.
221     The BUF arg is *not* owned by the dictionary, and the user should not free
222     its referent until the link is done.
223 
224     The order of calls to this function influences the order of types in the
225     final link output, but otherwise is not important.
226 
227     Private for now, but may in time become public once support for BUF is
228     implemented.  */
229 
230 static int
231 ctf_link_add (ctf_file_t *fp, ctf_archive_t *ctf, const char *name,
232 	      void *buf _libctf_unused_, size_t n _libctf_unused_)
233 {
234   if (buf)
235     return (ctf_set_errno (fp, ECTF_NOTYET));
236 
237   if (!((ctf && name && !buf)
238 	|| (name && !buf && !ctf)
239 	|| (buf && name && !ctf)))
240     return (ctf_set_errno (fp, EINVAL));
241 
242   /* We can only lazily open files if libctf.so is in use rather than
243      libctf-nobfd.so.  This is a little tricky: in shared libraries, we can use
244      a weak symbol so that -lctf -lctf-nobfd works, but in static libraries we
245      must distinguish between the two libraries explicitly.  */
246 
247 #if defined (PIC)
248   if (!buf && !ctf && name && !ctf_open)
249     return (ctf_set_errno (fp, ECTF_NEEDSBFD));
250 #elif NOBFD
251   if (!buf && !ctf && name)
252     return (ctf_set_errno (fp, ECTF_NEEDSBFD));
253 #endif
254 
255   if (fp->ctf_link_outputs)
256     return (ctf_set_errno (fp, ECTF_LINKADDEDLATE));
257   if (fp->ctf_link_inputs == NULL)
258     fp->ctf_link_inputs = ctf_dynhash_create (ctf_hash_string,
259 					      ctf_hash_eq_string, free,
260 					      ctf_link_input_close);
261 
262   if (fp->ctf_link_inputs == NULL)
263     return (ctf_set_errno (fp, ENOMEM));
264 
265   return ctf_link_add_ctf_internal (fp, ctf, NULL, name);
266 }
267 
268 /* Add an opened CTF archive or unopened file (by name) to a link.
269    If CTF is NULL and NAME is non-null, an unopened file is meant:
270    otherwise, the specified archive is assumed to have the given NAME.
271 
272     Passed in CTF args are owned by the dictionary and will be freed by it.
273 
274     The order of calls to this function influences the order of types in the
275     final link output, but otherwise is not important.  */
276 
277 int
278 ctf_link_add_ctf (ctf_file_t *fp, ctf_archive_t *ctf, const char *name)
279 {
280   return ctf_link_add (fp, ctf, name, NULL, 0);
281 }
282 
283 /* Return a per-CU output CTF dictionary suitable for the given CU, creating and
284    interning it if need be.  */
285 
286 static ctf_file_t *
287 ctf_create_per_cu (ctf_file_t *fp, const char *filename, const char *cuname)
288 {
289   ctf_file_t *cu_fp;
290   const char *ctf_name = NULL;
291   char *dynname = NULL;
292 
293   /* First, check the mapping table and translate the per-CU name we use
294      accordingly.  We check both the input filename and the CU name.  Only if
295      neither are set do we fall back to the input filename as the per-CU
296      dictionary name.  We prefer the filename because this is easier for likely
297      callers to determine.  */
298 
299   if (fp->ctf_link_in_cu_mapping)
300     {
301       if (((ctf_name = ctf_dynhash_lookup (fp->ctf_link_in_cu_mapping,
302 					   filename)) == NULL) &&
303 	  ((ctf_name = ctf_dynhash_lookup (fp->ctf_link_in_cu_mapping,
304 					   cuname)) == NULL))
305 	ctf_name = filename;
306     }
307 
308   if (ctf_name == NULL)
309     ctf_name = filename;
310 
311   if ((cu_fp = ctf_dynhash_lookup (fp->ctf_link_outputs, ctf_name)) == NULL)
312     {
313       int err;
314 
315       if ((cu_fp = ctf_create (&err)) == NULL)
316 	{
317 	  ctf_err_warn (fp, 0, err, _("cannot create per-CU CTF archive for "
318 				      "CU %s from input file %s"),
319 			cuname, filename);
320 	  ctf_set_errno (fp, err);
321 	  return NULL;
322 	}
323 
324       if ((dynname = strdup (ctf_name)) == NULL)
325 	goto oom;
326       if (ctf_dynhash_insert (fp->ctf_link_outputs, dynname, cu_fp) < 0)
327 	goto oom;
328 
329       ctf_import_unref (cu_fp, fp);
330       ctf_cuname_set (cu_fp, cuname);
331       ctf_parent_name_set (cu_fp, _CTF_SECTION);
332     }
333   return cu_fp;
334 
335  oom:
336   free (dynname);
337   ctf_file_close (cu_fp);
338   ctf_set_errno (fp, ENOMEM);
339   return NULL;
340 }
341 
342 /* Add a mapping directing that the CU named FROM should have its
343    conflicting/non-duplicate types (depending on link mode) go into a container
344    named TO.  Many FROMs can share a TO.
345 
346    We forcibly add a container named TO in every case, even though it may well
347    wind up empty, because clients that use this facility usually expect to find
348    every TO container present, even if empty, and malfunction otherwise.  */
349 
350 int
351 ctf_link_add_cu_mapping (ctf_file_t *fp, const char *from, const char *to)
352 {
353   int err;
354   char *f = NULL, *t = NULL;
355   ctf_dynhash_t *one_out;
356 
357   if (fp->ctf_link_in_cu_mapping == NULL)
358     fp->ctf_link_in_cu_mapping = ctf_dynhash_create (ctf_hash_string,
359 						     ctf_hash_eq_string, free,
360 						     free);
361   if (fp->ctf_link_in_cu_mapping == NULL)
362     goto oom;
363 
364   if (fp->ctf_link_out_cu_mapping == NULL)
365     fp->ctf_link_out_cu_mapping = ctf_dynhash_create (ctf_hash_string,
366 						      ctf_hash_eq_string, free,
367 						      (ctf_hash_free_fun)
368 						      ctf_dynhash_destroy);
369   if (fp->ctf_link_out_cu_mapping == NULL)
370     goto oom;
371 
372   f = strdup (from);
373   t = strdup (to);
374   if (!f || !t)
375     goto oom;
376 
377   /* Track both in a list from FROM to TO and in a list from TO to a list of
378      FROM.  The former is used to create TUs with the mapped-to name at need:
379      the latter is used in deduplicating links to pull in all input CUs
380      corresponding to a single output CU.  */
381 
382   if ((err = ctf_dynhash_insert (fp->ctf_link_in_cu_mapping, f, t)) < 0)
383     {
384       ctf_set_errno (fp, err);
385       goto oom_noerrno;
386     }
387 
388   /* f and t are now owned by the in_cu_mapping: reallocate them.  */
389   f = strdup (from);
390   t = strdup (to);
391   if (!f || !t)
392     goto oom;
393 
394   if ((one_out = ctf_dynhash_lookup (fp->ctf_link_out_cu_mapping, t)) == NULL)
395     {
396       if ((one_out = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
397 					 free, NULL)) == NULL)
398 	goto oom;
399       if ((err = ctf_dynhash_insert (fp->ctf_link_out_cu_mapping,
400 				     t, one_out)) < 0)
401 	{
402 	  ctf_dynhash_destroy (one_out);
403 	  ctf_set_errno (fp, err);
404 	  goto oom_noerrno;
405 	}
406     }
407   else
408     free (t);
409 
410   if (ctf_dynhash_insert (one_out, f, NULL) < 0)
411     {
412       ctf_set_errno (fp, err);
413       goto oom_noerrno;
414     }
415 
416   return 0;
417 
418  oom:
419   ctf_set_errno (fp, errno);
420  oom_noerrno:
421   free (f);
422   free (t);
423   return -1;
424 }
425 
426 /* Set a function which is called to transform the names of archive members.
427    This is useful for applying regular transformations to many names, where
428    ctf_link_add_cu_mapping applies arbitrarily irregular changes to single
429    names.  The member name changer is applied at ctf_link_write time, so it
430    cannot conflate multiple CUs into one the way ctf_link_add_cu_mapping can.
431    The changer function accepts a name and should return a new
432    dynamically-allocated name, or NULL if the name should be left unchanged.  */
433 void
434 ctf_link_set_memb_name_changer (ctf_file_t *fp,
435 				ctf_link_memb_name_changer_f *changer,
436 				void *arg)
437 {
438   fp->ctf_link_memb_name_changer = changer;
439   fp->ctf_link_memb_name_changer_arg = arg;
440 }
441 
442 typedef struct ctf_link_in_member_cb_arg
443 {
444   /* The shared output dictionary.  */
445   ctf_file_t *out_fp;
446 
447   /* The filename of the input file, and an fp to each dictionary in that file
448      in turn.  */
449   const char *in_file_name;
450   ctf_file_t *in_fp;
451 
452   /* The CU name of the dict being processed.  */
453   const char *cu_name;
454   int in_input_cu_file;
455 
456   /* The parent dictionary in the input, and whether it's been processed yet.
457      Not needed by ctf_link_one_type / ctf_link_one_variable, only by higher
458      layers.  */
459   ctf_file_t *in_fp_parent;
460   int done_parent;
461 
462   /* If true, this is the CU-mapped portion of a deduplicating link: no child
463      dictionaries should be created.  */
464   int cu_mapped;
465 } ctf_link_in_member_cb_arg_t;
466 
467 /* Link one type into the link.  We rely on ctf_add_type() to detect
468    duplicates.  This is not terribly reliable yet (unnmamed types will be
469    mindlessly duplicated), but will improve shortly.  */
470 
471 static int
472 ctf_link_one_type (ctf_id_t type, int isroot _libctf_unused_, void *arg_)
473 {
474   ctf_link_in_member_cb_arg_t *arg = (ctf_link_in_member_cb_arg_t *) arg_;
475   ctf_file_t *per_cu_out_fp;
476   int err;
477 
478   if (arg->in_fp->ctf_link_flags != CTF_LINK_SHARE_UNCONFLICTED)
479     {
480       ctf_err_warn (arg->out_fp, 0, ECTF_NOTYET,
481 		    _("share-duplicated mode not yet implemented"));
482       return ctf_set_errno (arg->out_fp, ECTF_NOTYET);
483     }
484 
485   /* Simply call ctf_add_type: if it reports a conflict and we're adding to the
486      main CTF file, add to the per-CU archive member instead, creating it if
487      necessary.  If we got this type from a per-CU archive member, add it
488      straight back to the corresponding member in the output.  */
489 
490   if (!arg->in_input_cu_file)
491     {
492       if (ctf_add_type (arg->out_fp, arg->in_fp, type) != CTF_ERR)
493 	return 0;
494 
495       err = ctf_errno (arg->out_fp);
496       if (err != ECTF_CONFLICT)
497 	{
498 	  if (err != ECTF_NONREPRESENTABLE)
499 	    ctf_err_warn (arg->out_fp, 1, 0,
500 			  _("cannot link type %lx from input file %s, CU %s "
501 			    "into output link"), type, arg->cu_name,
502 			  arg->in_file_name);
503 	  /* We must ignore this problem or we end up losing future types, then
504 	     trying to link the variables in, then exploding.  Better to link as
505 	     much as possible.  */
506 	  return 0;
507 	}
508       ctf_set_errno (arg->out_fp, 0);
509     }
510 
511   if ((per_cu_out_fp = ctf_create_per_cu (arg->out_fp, arg->in_file_name,
512 					  arg->cu_name)) == NULL)
513     return -1;					/* Errno is set for us.  */
514 
515   if (ctf_add_type (per_cu_out_fp, arg->in_fp, type) != CTF_ERR)
516     return 0;
517 
518   err = ctf_errno (per_cu_out_fp);
519   if (err != ECTF_NONREPRESENTABLE)
520     ctf_err_warn (arg->out_fp, 1, 0,
521 		  _("cannot link type %lx from input file %s, CU %s "
522 		    "into output per-CU CTF archive member %s: %s: skipped"),
523 		  type, ctf_link_input_name (arg->in_fp), arg->in_file_name,
524 		  ctf_link_input_name (per_cu_out_fp), ctf_errmsg (err));
525   if (err == ECTF_CONFLICT)
526       /* Conflicts are possible at this stage only if a non-ld user has combined
527 	 multiple TUs into a single output dictionary.  Even in this case we do not
528 	 want to stop the link or propagate the error.  */
529       ctf_set_errno (arg->out_fp, 0);
530 
531   return 0;					/* As above: do not lose types.  */
532 }
533 
534 /* Set a function which is used to filter out unwanted variables from the link.  */
535 int
536 ctf_link_set_variable_filter (ctf_file_t *fp, ctf_link_variable_filter_f *filter,
537 			      void *arg)
538 {
539   fp->ctf_link_variable_filter = filter;
540   fp->ctf_link_variable_filter_arg = arg;
541   return 0;
542 }
543 
544 /* Check if we can safely add a variable with the given type to this container.  */
545 
546 static int
547 check_variable (const char *name, ctf_file_t *fp, ctf_id_t type,
548 		ctf_dvdef_t **out_dvd)
549 {
550   ctf_dvdef_t *dvd;
551 
552   dvd = ctf_dynhash_lookup (fp->ctf_dvhash, name);
553   *out_dvd = dvd;
554   if (!dvd)
555     return 1;
556 
557   if (dvd->dvd_type != type)
558     {
559       /* Variable here.  Wrong type: cannot add.  Just skip it, because there is
560 	 no way to express this in CTF.  Don't even warn: this case is too
561 	 common.  (This might be the parent, in which case we'll try adding in
562 	 the child first, and only then give up.)  */
563       ctf_dprintf ("Inexpressible duplicate variable %s skipped.\n", name);
564     }
565 
566   return 0;				      /* Already exists.  */
567 }
568 
569 /* Link one variable in.  */
570 
571 static int
572 ctf_link_one_variable (const char *name, ctf_id_t type, void *arg_)
573 {
574   ctf_link_in_member_cb_arg_t *arg = (ctf_link_in_member_cb_arg_t *) arg_;
575   ctf_file_t *per_cu_out_fp;
576   ctf_id_t dst_type = 0;
577   ctf_file_t *check_fp;
578   ctf_dvdef_t *dvd;
579 
580   /* See if this variable is filtered out.  */
581 
582   if (arg->out_fp->ctf_link_variable_filter)
583     {
584       void *farg = arg->out_fp->ctf_link_variable_filter_arg;
585       if (arg->out_fp->ctf_link_variable_filter (arg->in_fp, name, type, farg))
586 	return 0;
587     }
588 
589   /* In unconflicted link mode, if this type is mapped to a type in the parent
590      container, we want to try to add to that first: if it reports a duplicate,
591      or if the type is in a child already, add straight to the child.  */
592 
593   check_fp = arg->out_fp;
594 
595   dst_type = ctf_type_mapping (arg->in_fp, type, &check_fp);
596   if (dst_type != 0)
597     {
598       if (check_fp == arg->out_fp)
599 	{
600 	  if (check_variable (name, check_fp, dst_type, &dvd))
601 	    {
602 	      /* No variable here: we can add it.  */
603 	      if (ctf_add_variable (check_fp, name, dst_type) < 0)
604 		return (ctf_set_errno (arg->out_fp, ctf_errno (check_fp)));
605 	      return 0;
606 	    }
607 
608 	  /* Already present?  Nothing to do.  */
609 	  if (dvd && dvd->dvd_type == dst_type)
610 	    return 0;
611 	}
612     }
613 
614   /* Can't add to the parent due to a name clash, or because it references a
615      type only present in the child.  Try adding to the child, creating if need
616      be.  If we can't do that, skip it.  Don't add to a child if we're doing a
617      CU-mapped link, since that has only one output.  */
618 
619   if (arg->cu_mapped)
620     {
621       ctf_dprintf ("Variable %s in input file %s depends on a type %lx hidden "
622 		   "due to conflicts: skipped.\n", name, arg->in_file_name,
623 		   type);
624       return 0;
625     }
626 
627   if ((per_cu_out_fp = ctf_create_per_cu (arg->out_fp, arg->in_file_name,
628 					  arg->cu_name)) == NULL)
629     return -1;					/* Errno is set for us.  */
630 
631   /* If the type was not found, check for it in the child too. */
632   if (dst_type == 0)
633     {
634       check_fp = per_cu_out_fp;
635       dst_type = ctf_type_mapping (arg->in_fp, type, &check_fp);
636 
637       if (dst_type == 0)
638 	{
639 	  ctf_err_warn (arg->out_fp, 1, 0,
640 			_("type %lx for variable %s in input file %s "
641 			  "not found: skipped"), type, name,
642 			arg->in_file_name);
643 	  /* Do not terminate the link: just skip the variable.  */
644 	  return 0;
645 	}
646     }
647 
648   if (check_variable (name, per_cu_out_fp, dst_type, &dvd))
649     if (ctf_add_variable (per_cu_out_fp, name, dst_type) < 0)
650       return (ctf_set_errno (arg->out_fp, ctf_errno (per_cu_out_fp)));
651   return 0;
652 }
653 
654 /* Merge every type (and optionally, variable) in this archive member into the
655    link, so we can relink things that have already had ld run on them.  We use
656    the archive member name, sans any leading '.ctf.', as the CU name for
657    ambiguous types if there is one and it's not the default: otherwise, we use
658    the name of the input file.  */
659 static int
660 ctf_link_one_input_archive_member (ctf_file_t *in_fp, const char *name, void *arg_)
661 {
662   ctf_link_in_member_cb_arg_t *arg = (ctf_link_in_member_cb_arg_t *) arg_;
663   int err = 0;
664 
665   if (strcmp (name, _CTF_SECTION) == 0)
666     {
667       /* This file is the default member of this archive, and has already been
668 	 explicitly processed.
669 
670 	 In the default sharing mode of CTF_LINK_SHARE_UNCONFLICTED, it does no
671 	 harm to rescan an existing shared repo again: all the types will just
672 	 end up in the same place.  But in CTF_LINK_SHARE_DUPLICATED mode, this
673 	 causes the system to erroneously conclude that all types are duplicated
674 	 and should be shared, even if they are not.  */
675 
676       if (arg->done_parent)
677 	return 0;
678     }
679   else
680     {
681       /* Get ambiguous types from our parent.  */
682       ctf_import (in_fp, arg->in_fp_parent);
683       arg->in_input_cu_file = 1;
684     }
685 
686   arg->cu_name = name;
687   if (strncmp (arg->cu_name, ".ctf.", strlen (".ctf.")) == 0)
688     arg->cu_name += strlen (".ctf.");
689   arg->in_fp = in_fp;
690 
691   if ((err = ctf_type_iter_all (in_fp, ctf_link_one_type, arg)) > -1)
692     if (!(in_fp->ctf_link_flags & CTF_LINK_OMIT_VARIABLES_SECTION))
693       err = ctf_variable_iter (in_fp, ctf_link_one_variable, arg);
694 
695   arg->in_input_cu_file = 0;
696 
697   if (err < 0)
698       return -1;				/* Errno is set for us.  */
699 
700   return 0;
701 }
702 
703 /* Dump the unnecessary link type mapping after one input file is processed.  */
704 static void
705 empty_link_type_mapping (void *key _libctf_unused_, void *value,
706 			 void *arg _libctf_unused_)
707 {
708   ctf_file_t *fp = (ctf_file_t *) value;
709 
710   if (fp->ctf_link_type_mapping)
711     ctf_dynhash_empty (fp->ctf_link_type_mapping);
712 }
713 
714 /* Lazily open a CTF archive for linking, if not already open.
715 
716    Returns the number of files contained within the opened archive (0 for none),
717    or -1 on error, as usual.  */
718 static ssize_t
719 ctf_link_lazy_open (ctf_file_t *fp, ctf_link_input_t *input)
720 {
721   size_t count;
722   int err;
723 
724   if (input->clin_arc)
725     return ctf_archive_count (input->clin_arc);
726 
727   if (input->clin_fp)
728     return 1;
729 
730   /* See ctf_link_add_ctf.  */
731 #if defined (PIC) || !NOBFD
732   input->clin_arc = ctf_open (input->clin_filename, NULL, &err);
733 #else
734   ctf_err_warn (fp, 0, ECTF_NEEDSBFD, _("cannot open %s lazily"),
735 		input->clin_filename);
736   ctf_set_errno (fp, ECTF_NEEDSBFD);
737   return -1;
738 #endif
739 
740   /* Having no CTF sections is not an error.  We just don't need to do
741      anything.  */
742 
743   if (!input->clin_arc)
744     {
745       if (err == ECTF_NOCTFDATA)
746 	return 0;
747 
748       ctf_err_warn (fp, 0, err, _("opening CTF %s failed"),
749 		    input->clin_filename);
750       ctf_set_errno (fp, err);
751       return -1;
752     }
753 
754   if ((count = ctf_archive_count (input->clin_arc)) == 0)
755     ctf_arc_close (input->clin_arc);
756 
757   return (ssize_t) count;
758 }
759 
760 /* Close an input, as a ctf_dynhash_iter iterator.  */
761 static void
762 ctf_link_close_one_input_archive (void *key _libctf_unused_, void *value,
763 				  void *arg _libctf_unused_)
764 {
765   ctf_link_input_t *input = (ctf_link_input_t *) value;
766   if (input->clin_arc)
767     ctf_arc_close (input->clin_arc);
768   input->clin_arc = NULL;
769 }
770 
771 /* Link one input file's types into the output file.  */
772 static void
773 ctf_link_one_input_archive (void *key, void *value, void *arg_)
774 {
775   const char *file_name = (const char *) key;
776   ctf_link_input_t *input = (ctf_link_input_t *)value;
777   ctf_link_in_member_cb_arg_t *arg = (ctf_link_in_member_cb_arg_t *) arg_;
778   int err = 0;
779 
780   if (!input->clin_arc)
781     {
782       err = ctf_link_lazy_open (arg->out_fp, input);
783       if (err == 0)				/* Just no CTF.  */
784 	return;
785 
786       if (err < 0)
787 	return;					/* errno is set for us.  */
788     }
789 
790   arg->in_file_name = file_name;
791   arg->done_parent = 0;
792   if ((arg->in_fp_parent = ctf_arc_open_by_name (input->clin_arc, NULL,
793 						 &err)) == NULL)
794     if (err != ECTF_ARNNAME)
795       {
796 	ctf_err_warn (arg->out_fp, 1, 0,
797 		      _("cannot open main archive member in input file %s "
798 			"in the link: skipping: %s"), arg->in_file_name,
799 		      ctf_errmsg (err));
800 	goto out;
801       }
802 
803   if (ctf_link_one_input_archive_member (arg->in_fp_parent,
804 					 _CTF_SECTION, arg) < 0)
805     {
806       ctf_file_close (arg->in_fp_parent);
807       goto out;
808     }
809   arg->done_parent = 1;
810   if (ctf_archive_iter (input->clin_arc, ctf_link_one_input_archive_member,
811 			arg) < 0)
812     ctf_err_warn (arg->out_fp, 0, 0, _("cannot traverse archive in input file "
813 				       "%s: link cannot continue"),
814 		  arg->in_file_name);
815   else
816     {
817       /* The only error indication to the caller is the errno: so ensure that it
818 	 is zero if there was no actual error from the caller.  */
819       ctf_set_errno (arg->out_fp, 0);
820     }
821   ctf_file_close (arg->in_fp_parent);
822 
823  out:
824   ctf_link_close_one_input_archive (key, value, NULL);
825 }
826 
827 typedef struct link_sort_inputs_cb_arg
828 {
829   int is_cu_mapped;
830   ctf_file_t *fp;
831 } link_sort_inputs_cb_arg_t;
832 
833 /* Sort the inputs by N (the link order).  For CU-mapped links, this is a
834    mapping of input to output name, not a mapping of input name to input
835    ctf_link_input_t: compensate accordingly.  */
836 static int
837 ctf_link_sort_inputs (const ctf_next_hkv_t *one, const ctf_next_hkv_t *two,
838 		      void *arg)
839 {
840   ctf_link_input_t *input_1;
841   ctf_link_input_t *input_2;
842   link_sort_inputs_cb_arg_t *cu_mapped = (link_sort_inputs_cb_arg_t *) arg;
843 
844   if (!cu_mapped || !cu_mapped->is_cu_mapped)
845     {
846       input_1 = (ctf_link_input_t *) one->hkv_value;
847       input_2 = (ctf_link_input_t *) two->hkv_value;
848     }
849   else
850     {
851       const char *name_1 = (const char *) one->hkv_key;
852       const char *name_2 = (const char *) two->hkv_key;
853 
854       input_1 = ctf_dynhash_lookup (cu_mapped->fp->ctf_link_inputs, name_1);
855       input_2 = ctf_dynhash_lookup (cu_mapped->fp->ctf_link_inputs, name_2);
856 
857       /* There is no guarantee that CU-mappings actually have corresponding
858 	 inputs: the relative ordering in that case is unimportant.  */
859       if (!input_1)
860 	return -1;
861       if (!input_2)
862 	return 1;
863     }
864 
865   if (input_1->n < input_2->n)
866     return -1;
867   else if (input_1->n > input_2->n)
868     return 1;
869   else
870     return 0;
871 }
872 
873 /* Count the number of input dicts in the ctf_link_inputs, or that subset of the
874    ctf_link_inputs given by CU_NAMES if set.  Return the number of input dicts,
875    and optionally the name and ctf_link_input_t of the single input archive if
876    only one exists (no matter how many dicts it contains).  */
877 static ssize_t
878 ctf_link_deduplicating_count_inputs (ctf_file_t *fp, ctf_dynhash_t *cu_names,
879 				     ctf_link_input_t **only_one_input)
880 {
881   ctf_dynhash_t *inputs = fp->ctf_link_inputs;
882   ctf_next_t *i = NULL;
883   void *name, *input;
884   ctf_link_input_t *one_input = NULL;
885   const char *one_name = NULL;
886   ssize_t count = 0, narcs = 0;
887   int err;
888 
889   if (cu_names)
890     inputs = cu_names;
891 
892   while ((err = ctf_dynhash_next (inputs, &i, &name, &input)) == 0)
893     {
894       ssize_t one_count;
895 
896       one_name = (const char *) name;
897       /* If we are processing CU names, get the real input.  */
898       if (cu_names)
899 	one_input = ctf_dynhash_lookup (fp->ctf_link_inputs, one_name);
900       else
901 	one_input = (ctf_link_input_t *) input;
902 
903       if (!one_input)
904 	continue;
905 
906       one_count = ctf_link_lazy_open (fp, one_input);
907 
908       if (one_count < 0)
909 	{
910 	  ctf_next_destroy (i);
911 	  return -1;				/* errno is set for us.  */
912 	}
913 
914       count += one_count;
915       narcs++;
916     }
917   if (err != ECTF_NEXT_END)
918     {
919       ctf_err_warn (fp, 0, err, _("iteration error counting deduplicating "
920 				  "CTF link inputs"));
921       ctf_set_errno (fp, err);
922       return -1;
923     }
924 
925   if (!count)
926     return 0;
927 
928   if (narcs == 1)
929     {
930       if (only_one_input)
931 	*only_one_input = one_input;
932     }
933   else if (only_one_input)
934     *only_one_input = NULL;
935 
936   return count;
937 }
938 
939 /* Allocate and populate an inputs array big enough for a given set of inputs:
940    either a specific set of CU names (those from that set found in the
941    ctf_link_inputs), or the entire ctf_link_inputs (if cu_names is not set).
942    The number of inputs (from ctf_link_deduplicating_count_inputs, above) is
943    passed in NINPUTS: an array of uint32_t containing parent pointers
944    (corresponding to those members of the inputs that have parents) is allocated
945    and returned in PARENTS.
946 
947    The inputs are *archives*, not files: the archive can have multiple members
948    if it is the result of a previous incremental link.  We want to add every one
949    in turn, including the shared parent.  (The dedup machinery knows that a type
950    used by a single dictionary and its parent should not be shared in
951    CTF_LINK_SHARE_DUPLICATED mode.)
952 
953    If no inputs exist that correspond to these CUs, return NULL with the errno
954    set to ECTF_NOCTFDATA.  */
955 static ctf_file_t **
956 ctf_link_deduplicating_open_inputs (ctf_file_t *fp, ctf_dynhash_t *cu_names,
957 				    ssize_t ninputs, uint32_t **parents)
958 {
959   ctf_dynhash_t *inputs = fp->ctf_link_inputs;
960   ctf_next_t *i = NULL;
961   void *name, *input;
962   link_sort_inputs_cb_arg_t sort_arg;
963   ctf_file_t **dedup_inputs = NULL;
964   ctf_file_t **walk;
965   uint32_t *parents_ = NULL;
966   int err;
967 
968   if (cu_names)
969     inputs = cu_names;
970 
971   if ((dedup_inputs = calloc (ninputs, sizeof (ctf_file_t *))) == NULL)
972     goto oom;
973 
974   if ((parents_ = calloc (ninputs, sizeof (uint32_t))) == NULL)
975     goto oom;
976 
977   walk = dedup_inputs;
978 
979   /* Counting done: push every input into the array, in the order they were
980      passed to ctf_link_add_ctf (and ultimately ld).  */
981 
982   sort_arg.is_cu_mapped = (cu_names != NULL);
983   sort_arg.fp = fp;
984 
985   while ((err = ctf_dynhash_next_sorted (inputs, &i, &name, &input,
986 					 ctf_link_sort_inputs, &sort_arg)) == 0)
987     {
988       const char *one_name = (const char *) name;
989       ctf_link_input_t *one_input;
990       ctf_file_t *one_fp;
991       ctf_file_t *parent_fp = NULL;
992       uint32_t parent_i;
993       ctf_next_t *j = NULL;
994 
995       /* If we are processing CU names, get the real input.  All the inputs
996 	 will have been opened, if they contained any CTF at all.  */
997       if (cu_names)
998 	one_input = ctf_dynhash_lookup (fp->ctf_link_inputs, one_name);
999       else
1000 	one_input = (ctf_link_input_t *) input;
1001 
1002       if (!one_input || (!one_input->clin_arc && !one_input->clin_fp))
1003 	continue;
1004 
1005       /* Short-circuit: if clin_fp is set, just use it.   */
1006       if (one_input->clin_fp)
1007 	{
1008 	  parents_[walk - dedup_inputs] = walk - dedup_inputs;
1009 	  *walk = one_input->clin_fp;
1010 	  walk++;
1011 	  continue;
1012 	}
1013 
1014       /* Get and insert the parent archive (if any), if this archive has
1015 	 multiple members.  We assume, as elsewhere, that the parent is named
1016 	 _CTF_SECTION.  */
1017 
1018       if ((parent_fp = ctf_arc_open_by_name (one_input->clin_arc,
1019 					     _CTF_SECTION, &err)) == NULL)
1020 	{
1021 	  if (err != ECTF_NOMEMBNAM)
1022 	    {
1023 	      ctf_next_destroy (i);
1024 	      ctf_set_errno (fp, err);
1025 	      goto err;
1026 	    }
1027 	}
1028       else
1029 	{
1030 	  *walk = parent_fp;
1031 	  parent_i = walk - dedup_inputs;
1032 	  walk++;
1033 	}
1034 
1035       /* We disregard the input archive name: either it is the parent (which we
1036 	 already have), or we want to put everything into one TU sharing the
1037 	 cuname anyway (if this is a CU-mapped link), or this is the final phase
1038 	 of a relink with CU-mapping off (i.e. ld -r) in which case the cuname
1039 	 is correctly set regardless.  */
1040       while ((one_fp = ctf_archive_next (one_input->clin_arc, &j, NULL,
1041 					 1, &err)) != NULL)
1042 	{
1043 	  if (one_fp->ctf_flags & LCTF_CHILD)
1044 	    {
1045 	      /* The contents of the parents array for elements not
1046 		 corresponding to children is undefined.  If there is no parent
1047 		 (itself a sign of a likely linker bug or corrupt input), we set
1048 		 it to itself.  */
1049 
1050 	      ctf_import (one_fp, parent_fp);
1051 	      if (parent_fp)
1052 		parents_[walk - dedup_inputs] = parent_i;
1053 	      else
1054 		parents_[walk - dedup_inputs] = walk - dedup_inputs;
1055 	    }
1056 	  *walk = one_fp;
1057 	  walk++;
1058 	}
1059       if (err != ECTF_NEXT_END)
1060 	{
1061 	  ctf_next_destroy (i);
1062 	  goto iterr;
1063 	}
1064     }
1065   if (err != ECTF_NEXT_END)
1066     goto iterr;
1067 
1068   *parents = parents_;
1069 
1070   return dedup_inputs;
1071 
1072  oom:
1073   err = ENOMEM;
1074 
1075  iterr:
1076   ctf_set_errno (fp, err);
1077 
1078  err:
1079   free (dedup_inputs);
1080   free (parents_);
1081   ctf_err_warn (fp, 0, 0, _("error in deduplicating CTF link "
1082 			    "input allocation"));
1083   return NULL;
1084 }
1085 
1086 /* Close INPUTS that have already been linked, first the passed array, and then
1087    that subset of the ctf_link_inputs archives they came from cited by the
1088    CU_NAMES.  If CU_NAMES is not specified, close all the ctf_link_inputs in one
1089    go, leaving it empty.  */
1090 static int
1091 ctf_link_deduplicating_close_inputs (ctf_file_t *fp, ctf_dynhash_t *cu_names,
1092 				     ctf_file_t **inputs, ssize_t ninputs)
1093 {
1094   ctf_next_t *it = NULL;
1095   void *name;
1096   int err;
1097   ssize_t i;
1098 
1099   /* This is the inverse of ctf_link_deduplicating_open_inputs: so first, close
1100      all the individual input dicts, opened by the archive iterator.  */
1101   for (i = 0; i < ninputs; i++)
1102     ctf_file_close (inputs[i]);
1103 
1104   /* Now close the archives they are part of.  */
1105   if (cu_names)
1106     {
1107       while ((err = ctf_dynhash_next (cu_names, &it, &name, NULL)) == 0)
1108 	{
1109 	  /* Remove the input from the linker inputs, if it exists, which also
1110 	     closes it.  */
1111 
1112 	  ctf_dynhash_remove (fp->ctf_link_inputs, (const char *) name);
1113 	}
1114       if (err != ECTF_NEXT_END)
1115 	{
1116 	  ctf_err_warn (fp, 0, err, _("iteration error in deduplicating link "
1117 				      "input freeing"));
1118 	  ctf_set_errno (fp, err);
1119 	}
1120     }
1121   else
1122     ctf_dynhash_empty (fp->ctf_link_inputs);
1123 
1124   return 0;
1125 }
1126 
1127 /* Do a deduplicating link of all variables in the inputs.  */
1128 static int
1129 ctf_link_deduplicating_variables (ctf_file_t *fp, ctf_file_t **inputs,
1130 				  size_t ninputs, int cu_mapped)
1131 {
1132   ctf_link_in_member_cb_arg_t arg;
1133   size_t i;
1134 
1135   arg.cu_mapped = cu_mapped;
1136   arg.out_fp = fp;
1137   arg.in_input_cu_file = 0;
1138 
1139   for (i = 0; i < ninputs; i++)
1140     {
1141       arg.in_fp = inputs[i];
1142       if (ctf_cuname (inputs[i]) != NULL)
1143 	arg.in_file_name = ctf_cuname (inputs[i]);
1144       else
1145 	arg.in_file_name = "unnamed-CU";
1146       arg.cu_name = arg.in_file_name;
1147       if (ctf_variable_iter (arg.in_fp, ctf_link_one_variable, &arg) < 0)
1148 	return ctf_set_errno (fp, ctf_errno (arg.in_fp));
1149 
1150       /* Outputs > 0 are per-CU.  */
1151       arg.in_input_cu_file = 1;
1152     }
1153   return 0;
1154 }
1155 
1156 /* Do the per-CU part of a deduplicating link.  */
1157 static int
1158 ctf_link_deduplicating_per_cu (ctf_file_t *fp)
1159 {
1160   ctf_next_t *i = NULL;
1161   int err;
1162   void *out_cu;
1163   void *in_cus;
1164 
1165   /* Links with a per-CU mapping in force get a first pass of deduplication,
1166      dedupping the inputs for a given CU mapping into the output for that
1167      mapping.  The outputs from this process get fed back into the final pass
1168      that is carried out even for non-CU links.  */
1169 
1170   while ((err = ctf_dynhash_next (fp->ctf_link_out_cu_mapping, &i, &out_cu,
1171 				  &in_cus)) == 0)
1172     {
1173       const char *out_name = (const char *) out_cu;
1174       ctf_dynhash_t *in = (ctf_dynhash_t *) in_cus;
1175       ctf_file_t *out = NULL;
1176       ctf_file_t **inputs;
1177       ctf_file_t **outputs;
1178       ctf_archive_t *in_arc;
1179       ssize_t ninputs;
1180       ctf_link_input_t *only_input;
1181       uint32_t noutputs;
1182       uint32_t *parents;
1183 
1184       if ((ninputs = ctf_link_deduplicating_count_inputs (fp, in,
1185 							  &only_input)) == -1)
1186 	goto err_open_inputs;
1187 
1188       /* CU mapping with no inputs?  Skip.  */
1189       if (ninputs == 0)
1190 	continue;
1191 
1192       if (labs ((long int) ninputs) > 0xfffffffe)
1193 	{
1194 	  ctf_err_warn (fp, 0, EFBIG, _("too many inputs in deduplicating "
1195 					"link: %li"), (long int) ninputs);
1196 	  ctf_set_errno (fp, EFBIG);
1197 	  goto err_open_inputs;
1198 	}
1199 
1200       /* Short-circuit: a cu-mapped link with only one input archive with
1201 	 unconflicting contents is a do-nothing, and we can just leave the input
1202 	 in place: we do have to change the cuname, though, so we unwrap it,
1203 	 change the cuname, then stuff it back in the linker input again, via
1204 	 the clin_fp short-circuit member.  ctf_link_deduplicating_open_inputs
1205 	 will spot this member and jam it straight into the next link phase,
1206 	 ignoring the corresponding archive.  */
1207       if (only_input && ninputs == 1)
1208 	{
1209 	  ctf_next_t *ai = NULL;
1210 	  int err;
1211 
1212 	  /* We can abuse an archive iterator to get the only member cheaply, no
1213 	     matter what its name.  */
1214 	  only_input->clin_fp = ctf_archive_next (only_input->clin_arc,
1215 						  &ai, NULL, 0, &err);
1216 	  if (!only_input->clin_fp)
1217 	    {
1218 	      ctf_err_warn (fp, 0, err, _("cannot open archive %s in "
1219 					  "CU-mapped CTF link"),
1220 			    only_input->clin_filename);
1221 	      ctf_set_errno (fp, err);
1222 	      goto err_open_inputs;
1223 	    }
1224 	  ctf_next_destroy (ai);
1225 
1226 	  if (strcmp (only_input->clin_filename, out_name) != 0)
1227 	    {
1228 	      /* Renaming. We need to add a new input, then null out the
1229 		 clin_arc and clin_fp of the old one to stop it being
1230 		 auto-closed on removal.  The new input needs its cuname changed
1231 		 to out_name, which is doable only because the cuname is a
1232 		 dynamic property which can be changed even in readonly
1233 		 dicts. */
1234 
1235 	      ctf_cuname_set (only_input->clin_fp, out_name);
1236 	      if (ctf_link_add_ctf_internal (fp, only_input->clin_arc,
1237 					     only_input->clin_fp,
1238 					     out_name) < 0)
1239 		{
1240 		  ctf_err_warn (fp, 0, 0, _("cannot add intermediate files "
1241 					    "to link"));
1242 		  goto err_open_inputs;
1243 		}
1244 	      only_input->clin_arc = NULL;
1245 	      only_input->clin_fp = NULL;
1246 	      ctf_dynhash_remove (fp->ctf_link_inputs,
1247 				  only_input->clin_filename);
1248 	    }
1249 	  continue;
1250 	}
1251 
1252       /* This is a real CU many-to-one mapping: we must dedup the inputs into
1253 	 a new output to be used in the final link phase.  */
1254 
1255       if ((inputs = ctf_link_deduplicating_open_inputs (fp, in, ninputs,
1256 							&parents)) == NULL)
1257 	{
1258 	  ctf_next_destroy (i);
1259 	  goto err_inputs;
1260 	}
1261 
1262       if ((out = ctf_create (&err)) == NULL)
1263 	{
1264 	  ctf_err_warn (fp, 0, err, _("cannot create per-CU CTF archive "
1265 				      "for %s"),
1266 			out_name);
1267 	  ctf_set_errno (fp, err);
1268 	  goto err_inputs;
1269 	}
1270 
1271       /* Share the atoms table to reduce memory usage.  */
1272       out->ctf_dedup_atoms = fp->ctf_dedup_atoms_alloc;
1273 
1274       /* No ctf_imports at this stage: this per-CU dictionary has no parents.
1275 	 Parent/child deduplication happens in the link's final pass.  However,
1276 	 the cuname *is* important, as it is propagated into the final
1277 	 dictionary.  */
1278       ctf_cuname_set (out, out_name);
1279 
1280       if (ctf_dedup (out, inputs, ninputs, parents, 1) < 0)
1281 	{
1282 	  ctf_set_errno (fp, ctf_errno (out));
1283 	  ctf_err_warn (fp, 0, 0, _("CU-mapped deduplication failed for %s"),
1284 			out_name);
1285 	  goto err_inputs;
1286 	}
1287 
1288       if ((outputs = ctf_dedup_emit (out, inputs, ninputs, parents,
1289 				     &noutputs, 1)) == NULL)
1290 	{
1291 	  ctf_set_errno (fp, ctf_errno (out));
1292 	  ctf_err_warn (fp, 0, 0, _("CU-mapped deduplicating link type emission "
1293 				     "failed for %s"), out_name);
1294 	  goto err_inputs;
1295 	}
1296       if (!ctf_assert (fp, noutputs == 1))
1297 	goto err_inputs_outputs;
1298 
1299       if (!(fp->ctf_link_flags & CTF_LINK_OMIT_VARIABLES_SECTION)
1300 	  && ctf_link_deduplicating_variables (out, inputs, ninputs, 1) < 0)
1301 	{
1302 	  ctf_set_errno (fp, ctf_errno (out));
1303 	  ctf_err_warn (fp, 0, 0, _("CU-mapped deduplicating link variable "
1304 				    "emission failed for %s"), out_name);
1305 	  goto err_inputs_outputs;
1306 	}
1307 
1308       if (ctf_link_deduplicating_close_inputs (fp, in, inputs, ninputs) < 0)
1309 	{
1310 	  free (inputs);
1311 	  free (parents);
1312 	  goto err_outputs;
1313 	}
1314       free (inputs);
1315       free (parents);
1316 
1317       /* Splice any errors or warnings created during this link back into the
1318 	 dict that the caller knows about.  */
1319       ctf_list_splice (&fp->ctf_errs_warnings, &outputs[0]->ctf_errs_warnings);
1320 
1321       /* This output now becomes an input to the next link phase, with a name
1322 	 equal to the CU name.  We have to wrap it in an archive wrapper
1323 	 first.  */
1324 
1325       if ((in_arc = ctf_new_archive_internal (0, 0, NULL, outputs[0], NULL,
1326 					      NULL, &err)) == NULL)
1327 	{
1328 	  ctf_set_errno (fp, err);
1329 	  goto err_outputs;
1330 	}
1331 
1332       if (ctf_link_add_ctf_internal (fp, in_arc, NULL,
1333 				     ctf_cuname (outputs[0])) < 0)
1334 	{
1335 	  ctf_err_warn (fp, 0, 0, _("cannot add intermediate files to link"));
1336 	  goto err_outputs;
1337 	}
1338 
1339       ctf_file_close (out);
1340       free (outputs);
1341       continue;
1342 
1343     err_inputs_outputs:
1344       ctf_list_splice (&fp->ctf_errs_warnings, &outputs[0]->ctf_errs_warnings);
1345       ctf_file_close (outputs[0]);
1346       free (outputs);
1347     err_inputs:
1348       ctf_link_deduplicating_close_inputs (fp, in, inputs, ninputs);
1349       ctf_file_close (out);
1350       free (inputs);
1351       free (parents);
1352     err_open_inputs:
1353       ctf_next_destroy (i);
1354       return -1;
1355 
1356     err_outputs:
1357       ctf_list_splice (&fp->ctf_errs_warnings, &outputs[0]->ctf_errs_warnings);
1358       ctf_file_close (outputs[0]);
1359       free (outputs);
1360       ctf_next_destroy (i);
1361       return -1;				/* Errno is set for us.  */
1362     }
1363   if (err != ECTF_NEXT_END)
1364     {
1365       ctf_err_warn (fp, 0, err, _("iteration error in CU-mapped deduplicating "
1366 				  "link"));
1367       return ctf_set_errno (fp, err);
1368     }
1369 
1370   return 0;
1371 }
1372 
1373 /* Do a deduplicating link using the ctf-dedup machinery.  */
1374 static void
1375 ctf_link_deduplicating (ctf_file_t *fp)
1376 {
1377   size_t i;
1378   ctf_file_t **inputs, **outputs = NULL;
1379   ssize_t ninputs;
1380   uint32_t noutputs;
1381   uint32_t *parents;
1382 
1383   if (ctf_dedup_atoms_init (fp) < 0)
1384     {
1385       ctf_err_warn (fp, 0, 0, _("allocating CTF dedup atoms table"));
1386       return;					/* Errno is set for us.  */
1387     }
1388 
1389   if (fp->ctf_link_out_cu_mapping
1390       && (ctf_link_deduplicating_per_cu (fp) < 0))
1391     return;					/* Errno is set for us.  */
1392 
1393   if ((ninputs = ctf_link_deduplicating_count_inputs (fp, NULL, NULL)) < 0)
1394     return;					/* Errno is set for us.  */
1395 
1396   if ((inputs = ctf_link_deduplicating_open_inputs (fp, NULL, ninputs,
1397 						    &parents)) == NULL)
1398     return;					/* Errno is set for us.  */
1399 
1400   if (ninputs == 1 && ctf_cuname (inputs[0]) != NULL)
1401     ctf_cuname_set (fp, ctf_cuname (inputs[0]));
1402 
1403   if (ctf_dedup (fp, inputs, ninputs, parents, 0) < 0)
1404     {
1405       ctf_err_warn (fp, 0, 0, _("deduplication failed for %s"),
1406 		    ctf_link_input_name (fp));
1407       goto err;
1408     }
1409 
1410   if ((outputs = ctf_dedup_emit (fp, inputs, ninputs, parents, &noutputs,
1411 				 0)) == NULL)
1412     {
1413       ctf_err_warn (fp, 0, 0, _("deduplicating link type emission failed "
1414 				"for %s"), ctf_link_input_name (fp));
1415       goto err;
1416     }
1417 
1418   if (!ctf_assert (fp, outputs[0] == fp))
1419     goto err;
1420 
1421   for (i = 0; i < noutputs; i++)
1422     {
1423       char *dynname;
1424 
1425       /* We already have access to this one.  Close the duplicate.  */
1426       if (i == 0)
1427 	{
1428 	  ctf_file_close (outputs[0]);
1429 	  continue;
1430 	}
1431 
1432       if ((dynname = strdup (ctf_cuname (outputs[i]))) == NULL)
1433 	goto oom_one_output;
1434 
1435       if (ctf_dynhash_insert (fp->ctf_link_outputs, dynname, outputs[i]) < 0)
1436 	goto oom_one_output;
1437 
1438       continue;
1439 
1440     oom_one_output:
1441       ctf_set_errno (fp, ENOMEM);
1442       ctf_err_warn (fp, 0, 0, _("out of memory allocating link outputs"));
1443       free (dynname);
1444 
1445       for (; i < noutputs; i++)
1446 	ctf_file_close (outputs[i]);
1447       goto err;
1448     }
1449 
1450   if (!(fp->ctf_link_flags & CTF_LINK_OMIT_VARIABLES_SECTION)
1451       && ctf_link_deduplicating_variables (fp, inputs, ninputs, 0) < 0)
1452     {
1453       ctf_err_warn (fp, 0, 0, _("deduplicating link variable emission failed for "
1454 				"%s"), ctf_link_input_name (fp));
1455       for (i = 1; i < noutputs; i++)
1456 	ctf_file_close (outputs[i]);
1457       goto err;
1458     }
1459 
1460   /* Now close all the inputs, including per-CU intermediates.  */
1461 
1462   if (ctf_link_deduplicating_close_inputs (fp, NULL, inputs, ninputs) < 0)
1463     return;					/* errno is set for us.  */
1464 
1465   ninputs = 0;					/* Prevent double-close.  */
1466   ctf_set_errno (fp, 0);
1467 
1468   /* Fall through.  */
1469 
1470  err:
1471   for (i = 0; i < (size_t) ninputs; i++)
1472     ctf_file_close (inputs[i]);
1473   free (inputs);
1474   free (parents);
1475   free (outputs);
1476   return;
1477 }
1478 
1479 /* Merge types and variable sections in all files added to the link
1480    together.  All the added files are closed.  */
1481 int
1482 ctf_link (ctf_file_t *fp, int flags)
1483 {
1484   ctf_link_in_member_cb_arg_t arg;
1485   ctf_next_t *i = NULL;
1486   int err;
1487 
1488   memset (&arg, 0, sizeof (struct ctf_link_in_member_cb_arg));
1489   arg.out_fp = fp;
1490   fp->ctf_link_flags = flags;
1491 
1492   if (fp->ctf_link_inputs == NULL)
1493     return 0;					/* Nothing to do. */
1494 
1495   if (fp->ctf_link_outputs == NULL)
1496     fp->ctf_link_outputs = ctf_dynhash_create (ctf_hash_string,
1497 					       ctf_hash_eq_string, free,
1498 					       (ctf_hash_free_fun)
1499 					       ctf_file_close);
1500 
1501   if (fp->ctf_link_outputs == NULL)
1502     return ctf_set_errno (fp, ENOMEM);
1503 
1504   /* Create empty CUs if requested.  We do not currently claim that multiple
1505      links in succession with CTF_LINK_EMPTY_CU_MAPPINGS set in some calls and
1506      not set in others will do anything especially sensible.  */
1507 
1508   if (fp->ctf_link_out_cu_mapping && (flags & CTF_LINK_EMPTY_CU_MAPPINGS))
1509     {
1510       void *v;
1511 
1512       while ((err = ctf_dynhash_next (fp->ctf_link_out_cu_mapping, &i, &v,
1513 				      NULL)) == 0)
1514 	{
1515 	  const char *to = (const char *) v;
1516 	  if (ctf_create_per_cu (fp, to, to) == NULL)
1517 	    {
1518 	      ctf_next_destroy (i);
1519 	      return -1;			/* Errno is set for us.  */
1520 	    }
1521 	}
1522       if (err != ECTF_NEXT_END)
1523 	{
1524 	  ctf_err_warn (fp, 1, err, _("iteration error creating empty CUs"));
1525 	  ctf_set_errno (fp, err);
1526 	  return -1;
1527 	}
1528     }
1529 
1530   if ((flags & CTF_LINK_NONDEDUP) || (getenv ("LD_NO_CTF_DEDUP")))
1531     ctf_dynhash_iter (fp->ctf_link_inputs, ctf_link_one_input_archive,
1532 		      &arg);
1533   else
1534     ctf_link_deduplicating (fp);
1535 
1536   /* Discard the now-unnecessary mapping table data from all the outputs.  */
1537   if (fp->ctf_link_type_mapping)
1538     ctf_dynhash_empty (fp->ctf_link_type_mapping);
1539   ctf_dynhash_iter (fp->ctf_link_outputs, empty_link_type_mapping, NULL);
1540 
1541   if ((ctf_errno (fp) != 0) && (ctf_errno (fp) != ECTF_NOCTFDATA))
1542     return -1;
1543   return 0;
1544 }
1545 
1546 typedef struct ctf_link_out_string_cb_arg
1547 {
1548   const char *str;
1549   uint32_t offset;
1550   int err;
1551 } ctf_link_out_string_cb_arg_t;
1552 
1553 /* Intern a string in the string table of an output per-CU CTF file.  */
1554 static void
1555 ctf_link_intern_extern_string (void *key _libctf_unused_, void *value,
1556 			       void *arg_)
1557 {
1558   ctf_file_t *fp = (ctf_file_t *) value;
1559   ctf_link_out_string_cb_arg_t *arg = (ctf_link_out_string_cb_arg_t *) arg_;
1560 
1561   fp->ctf_flags |= LCTF_DIRTY;
1562   if (!ctf_str_add_external (fp, arg->str, arg->offset))
1563     arg->err = ENOMEM;
1564 }
1565 
1566 /* Repeatedly call ADD_STRING to acquire strings from the external string table,
1567    adding them to the atoms table for this CU and all subsidiary CUs.
1568 
1569    If ctf_link() is also called, it must be called first if you want the new CTF
1570    files ctf_link() can create to get their strings dedupped against the ELF
1571    strtab properly.  */
1572 int
1573 ctf_link_add_strtab (ctf_file_t *fp, ctf_link_strtab_string_f *add_string,
1574 		     void *arg)
1575 {
1576   const char *str;
1577   uint32_t offset;
1578   int err = 0;
1579 
1580   while ((str = add_string (&offset, arg)) != NULL)
1581     {
1582       ctf_link_out_string_cb_arg_t iter_arg = { str, offset, 0 };
1583 
1584       fp->ctf_flags |= LCTF_DIRTY;
1585       if (!ctf_str_add_external (fp, str, offset))
1586 	err = ENOMEM;
1587 
1588       ctf_dynhash_iter (fp->ctf_link_outputs, ctf_link_intern_extern_string,
1589 			&iter_arg);
1590       if (iter_arg.err)
1591 	err = iter_arg.err;
1592     }
1593 
1594   return -err;
1595 }
1596 
1597 /* Not yet implemented.  */
1598 int
1599 ctf_link_shuffle_syms (ctf_file_t *fp _libctf_unused_,
1600 		       ctf_link_iter_symbol_f *add_sym _libctf_unused_,
1601 		       void *arg _libctf_unused_)
1602 {
1603   return 0;
1604 }
1605 
1606 typedef struct ctf_name_list_accum_cb_arg
1607 {
1608   char **names;
1609   ctf_file_t *fp;
1610   ctf_file_t **files;
1611   size_t i;
1612   char **dynames;
1613   size_t ndynames;
1614 } ctf_name_list_accum_cb_arg_t;
1615 
1616 /* Accumulate the names and a count of the names in the link output hash.  */
1617 static void
1618 ctf_accumulate_archive_names (void *key, void *value, void *arg_)
1619 {
1620   const char *name = (const char *) key;
1621   ctf_file_t *fp = (ctf_file_t *) value;
1622   char **names;
1623   ctf_file_t **files;
1624   ctf_name_list_accum_cb_arg_t *arg = (ctf_name_list_accum_cb_arg_t *) arg_;
1625 
1626   if ((names = realloc (arg->names, sizeof (char *) * ++(arg->i))) == NULL)
1627     {
1628       (arg->i)--;
1629       ctf_set_errno (arg->fp, ENOMEM);
1630       return;
1631     }
1632 
1633   if ((files = realloc (arg->files, sizeof (ctf_file_t *) * arg->i)) == NULL)
1634     {
1635       (arg->i)--;
1636       ctf_set_errno (arg->fp, ENOMEM);
1637       return;
1638     }
1639 
1640   /* Allow the caller to get in and modify the name at the last minute.  If the
1641      caller *does* modify the name, we have to stash away the new name the
1642      caller returned so we can free it later on.  (The original name is the key
1643      of the ctf_link_outputs hash and is freed by the dynhash machinery.)  */
1644 
1645   if (fp->ctf_link_memb_name_changer)
1646     {
1647       char **dynames;
1648       char *dyname;
1649       void *nc_arg = fp->ctf_link_memb_name_changer_arg;
1650 
1651       dyname = fp->ctf_link_memb_name_changer (fp, name, nc_arg);
1652 
1653       if (dyname != NULL)
1654 	{
1655 	  if ((dynames = realloc (arg->dynames,
1656 				  sizeof (char *) * ++(arg->ndynames))) == NULL)
1657 	    {
1658 	      (arg->ndynames)--;
1659 	      ctf_set_errno (arg->fp, ENOMEM);
1660 	      return;
1661 	    }
1662 	    arg->dynames = dynames;
1663 	    name = (const char *) dyname;
1664 	}
1665     }
1666 
1667   arg->names = names;
1668   arg->names[(arg->i) - 1] = (char *) name;
1669   arg->files = files;
1670   arg->files[(arg->i) - 1] = fp;
1671 }
1672 
1673 /* Change the name of the parent CTF section, if the name transformer has got to
1674    it.  */
1675 static void
1676 ctf_change_parent_name (void *key _libctf_unused_, void *value, void *arg)
1677 {
1678   ctf_file_t *fp = (ctf_file_t *) value;
1679   const char *name = (const char *) arg;
1680 
1681   ctf_parent_name_set (fp, name);
1682 }
1683 
1684 /* Write out a CTF archive (if there are per-CU CTF files) or a CTF file
1685    (otherwise) into a new dynamically-allocated string, and return it.
1686    Members with sizes above THRESHOLD are compressed.  */
1687 unsigned char *
1688 ctf_link_write (ctf_file_t *fp, size_t *size, size_t threshold)
1689 {
1690   ctf_name_list_accum_cb_arg_t arg;
1691   char **names;
1692   char *transformed_name = NULL;
1693   ctf_file_t **files;
1694   FILE *f = NULL;
1695   int err;
1696   long fsize;
1697   const char *errloc;
1698   unsigned char *buf = NULL;
1699 
1700   memset (&arg, 0, sizeof (ctf_name_list_accum_cb_arg_t));
1701   arg.fp = fp;
1702 
1703   if (fp->ctf_link_outputs)
1704     {
1705       ctf_dynhash_iter (fp->ctf_link_outputs, ctf_accumulate_archive_names, &arg);
1706       if (ctf_errno (fp) < 0)
1707 	{
1708 	  errloc = "hash creation";
1709 	  goto err;
1710 	}
1711     }
1712 
1713   /* No extra outputs? Just write a simple ctf_file_t.  */
1714   if (arg.i == 0)
1715     return ctf_write_mem (fp, size, threshold);
1716 
1717   /* Writing an archive.  Stick ourselves (the shared repository, parent of all
1718      other archives) on the front of it with the default name.  */
1719   if ((names = realloc (arg.names, sizeof (char *) * (arg.i + 1))) == NULL)
1720     {
1721       errloc = "name reallocation";
1722       goto err_no;
1723     }
1724   arg.names = names;
1725   memmove (&(arg.names[1]), arg.names, sizeof (char *) * (arg.i));
1726 
1727   arg.names[0] = (char *) _CTF_SECTION;
1728   if (fp->ctf_link_memb_name_changer)
1729     {
1730       void *nc_arg = fp->ctf_link_memb_name_changer_arg;
1731 
1732       transformed_name = fp->ctf_link_memb_name_changer (fp, _CTF_SECTION,
1733 							 nc_arg);
1734 
1735       if (transformed_name != NULL)
1736 	{
1737 	  arg.names[0] = transformed_name;
1738 	  ctf_dynhash_iter (fp->ctf_link_outputs, ctf_change_parent_name,
1739 			    transformed_name);
1740 	}
1741     }
1742 
1743   if ((files = realloc (arg.files,
1744 			sizeof (struct ctf_file *) * (arg.i + 1))) == NULL)
1745     {
1746       errloc = "ctf_file reallocation";
1747       goto err_no;
1748     }
1749   arg.files = files;
1750   memmove (&(arg.files[1]), arg.files, sizeof (ctf_file_t *) * (arg.i));
1751   arg.files[0] = fp;
1752 
1753   if ((f = tmpfile ()) == NULL)
1754     {
1755       errloc = "tempfile creation";
1756       goto err_no;
1757     }
1758 
1759   if ((err = ctf_arc_write_fd (fileno (f), arg.files, arg.i + 1,
1760 			       (const char **) arg.names,
1761 			       threshold)) < 0)
1762     {
1763       errloc = "archive writing";
1764       ctf_set_errno (fp, err);
1765       goto err;
1766     }
1767 
1768   if (fseek (f, 0, SEEK_END) < 0)
1769     {
1770       errloc = "seeking to end";
1771       goto err_no;
1772     }
1773 
1774   if ((fsize = ftell (f)) < 0)
1775     {
1776       errloc = "filesize determination";
1777       goto err_no;
1778     }
1779 
1780   if (fseek (f, 0, SEEK_SET) < 0)
1781     {
1782       errloc = "filepos resetting";
1783       goto err_no;
1784     }
1785 
1786   if ((buf = malloc (fsize)) == NULL)
1787     {
1788       errloc = "CTF archive buffer allocation";
1789       goto err_no;
1790     }
1791 
1792   while (!feof (f) && fread (buf, fsize, 1, f) == 0)
1793     if (ferror (f))
1794       {
1795 	errloc = "reading archive from temporary file";
1796 	goto err_no;
1797       }
1798 
1799   *size = fsize;
1800   free (arg.names);
1801   free (arg.files);
1802   free (transformed_name);
1803   if (arg.ndynames)
1804     {
1805       size_t i;
1806       for (i = 0; i < arg.ndynames; i++)
1807 	free (arg.dynames[i]);
1808       free (arg.dynames);
1809     }
1810   fclose (f);
1811   return buf;
1812 
1813  err_no:
1814   ctf_set_errno (fp, errno);
1815  err:
1816   free (buf);
1817   if (f)
1818     fclose (f);
1819   free (arg.names);
1820   free (arg.files);
1821   free (transformed_name);
1822   if (arg.ndynames)
1823     {
1824       size_t i;
1825       for (i = 0; i < arg.ndynames; i++)
1826 	free (arg.dynames[i]);
1827       free (arg.dynames);
1828     }
1829   ctf_err_warn (fp, 0, 0, _("cannot write archive in link: %s failure"),
1830 		errloc);
1831   return NULL;
1832 }
1833