Commit | Line | Data |
---|---|---|
0f0c11f7 NA |
1 | /* CTF type deduplication. |
2 | Copyright (C) 2019 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 | #include <errno.h> | |
23 | #include <assert.h> | |
24 | #include "hashtab.h" | |
25 | ||
26 | /* (In the below, relevant functions are named in square brackets.) */ | |
27 | ||
28 | /* Type deduplication is a three-phase process: | |
29 | ||
30 | [ctf_dedup, ctf_dedup_hash_type, ctf_dedup_rhash_type] | |
31 | 1) come up with unambiguous hash values for all types: no two types may have | |
32 | the same hash value, and any given type should have only one hash value | |
33 | (for optimal deduplication). | |
34 | ||
35 | [ctf_dedup, ctf_dedup_detect_name_ambiguity, | |
36 | ctf_dedup_conflictify_unshared, ctf_dedup_mark_conflicting_hash] | |
37 | 2) mark those distinct types with names that collide (and thus cannot be | |
38 | declared simultaneously in the same translation unit) as conflicting, and | |
39 | recursively mark all types that cite one of those types as conflicting as | |
40 | well. Possibly mark all types cited in only one TU as conflicting, if | |
41 | the CTF_LINK_SHARE_DUPLICATED link mode is active. | |
42 | ||
43 | [ctf_dedup_emit, ctf_dedup_emit_struct_members, ctf_dedup_id_to_target] | |
44 | 3) emit all the types, one hash value at a time. Types not marked | |
45 | conflicting are emitted once, into the shared dictionary: types marked | |
46 | conflicting are emitted once per TU into a dictionary corresponding to | |
47 | each TU in which they appear. Structs marked conflicting get at the very | |
48 | least a forward emitted into the shared dict so that other dicts can cite | |
49 | it if needed. | |
50 | ||
51 | [id_to_packed_id] | |
52 | This all works over an array of inputs (usually in the same order as the | |
53 | inputs on the link line). We don't use the ctf_link_inputs hash directly | |
54 | because it is convenient to be able to address specific input types as a | |
55 | *global type ID* or 'GID', a pair of an array offset and a ctf_id_t. Since | |
56 | both are already 32 bits or less or can easily be constrained to that range, | |
57 | we can pack them both into a single 64-bit hash word for easy lookups, which | |
58 | would be much more annoying to do with a ctf_file_t * and a ctf_id_t. (On | |
59 | 32-bit platforms, we must do that anyway, since pointers, and thus hash keys | |
60 | and values, are only 32 bits wide). We track which inputs are parents of | |
61 | which other inputs so that we can correctly recognize that types we have | |
62 | traversed in children may cite types in parents, and so that we can process | |
63 | the parents first.) | |
64 | ||
65 | Note that thanks to ld -r, the deduplicator can be fed its own output, so the | |
66 | inputs may themselves have child dicts. Since we need to support this usage | |
67 | anyway, we can use it in one other place. If the caller finds translation | |
68 | units to be too small a unit ambiguous types, links can be 'cu-mapped', where | |
69 | the caller provides a mapping of input TU names to output child dict names. | |
70 | This mapping can fuse many child TUs into one potential child dict, so that | |
71 | ambiguous types in any of those input TUs go into the same child dict. | |
72 | When a many:1 cu-mapping is detected, the ctf_dedup machinery is called | |
73 | repeatedly, once for every output name that has more than one input, to fuse | |
74 | all the input TUs associated with a given output dict into one, and once again | |
75 | as normal to deduplicate all those intermediate outputs (and any 1:1 inputs) | |
76 | together. This has much higher memory usage than otherwise, because in the | |
77 | intermediate state, all the output TUs are in memory at once and cannot be | |
78 | lazily opened. It also has implications for the emission code: if types | |
79 | appear ambiguously in multiple input TUs that are all mapped to the same | |
80 | child dict, we cannot put them in children in the cu-mapping link phase | |
81 | because this output is meant to *become* a child in the next link stage and | |
82 | parent/child relationships are only one level deep: so instead, we just hide | |
83 | all but one of the ambiguous types. | |
84 | ||
85 | There are a few other subtleties here that make this more complex than it | |
86 | seems. Let's go over the steps above in more detail. | |
87 | ||
88 | 1) HASHING. | |
89 | ||
90 | [ctf_dedup_hash_type, ctf_dedup_rhash_type] | |
91 | Hashing proceeds recursively, mixing in the properties of each input type | |
92 | (including its name, if any), and then adding the hash values of every type | |
93 | cited by that type. The result is stashed in the cd_type_hashes so other | |
94 | phases can find the hash values of input types given their IDs, and so that | |
95 | if we encounter this type again while hashing we can just return its hash | |
96 | value: it is also stashed in the *output mapping*, a mapping from hash value | |
97 | to the set of GIDs corresponding to that type in all inputs. We also keep | |
98 | track of the GID of the first appearance of the type in any input (in | |
99 | cd_output_first_gid), and the GID of structs, unions, and forwards that only | |
100 | appear in one TU (in cd_struct_origin). See below for where these things are | |
101 | used. | |
102 | ||
103 | Everything in this phase is time-critical, because it is operating over | |
104 | non-deduplicated types and so may have hundreds or thousands of times the | |
105 | data volume to deal with than later phases. Trace output is hidden behind | |
106 | ENABLE_LIBCTF_HASH_DEBUGGING to prevent the sheer number of calls to | |
107 | ctf_dprintf from slowing things down (tenfold slowdowns are observed purely | |
108 | from the calls to ctf_dprintf(), even with debugging switched off), and keep | |
109 | down the volume of output (hundreds of gigabytes of debug output are not | |
110 | uncommon on larger links). | |
111 | ||
112 | We have to do *something* about potential cycles in the type graph. We'd | |
113 | like to avoid emitting forwards in the final output if possible, because | |
114 | forwards aren't much use: they have no members. We are mostly saved from | |
115 | needing to worry about this at emission time by ctf_add_struct*() | |
116 | automatically replacing newly-created forwards when the real struct/union | |
117 | comes along. So we only have to avoid getting stuck in cycles during the | |
118 | hashing phase, while also not confusing types that cite members that are | |
119 | structs with each other. It is easiest to solve this problem by noting two | |
120 | things: | |
121 | ||
122 | - all cycles in C depend on the presence of tagged structs/unions | |
123 | - all tagged structs/unions have a unique name they can be disambiguated by | |
124 | ||
125 | [ctf_dedup_is_stub] | |
126 | This means that we can break all cycles by ceasing to hash in cited types at | |
127 | every tagged struct/union and instead hashing in a stub consisting of the | |
128 | struct/union's *decorated name*, which is the name preceded by "s " or "u " | |
129 | depending on the namespace (cached in cd_decorated_names). Forwards are | |
130 | decorated identically (so a forward to "struct foo" would be represented as | |
131 | "s foo"): this means that a citation of a forward to a type and a citation of | |
132 | a concrete definition of a type with the same name ends up getting the same | |
133 | hash value. | |
134 | ||
135 | Of course, it is quite possible to have two TUs with structs with the same | |
136 | name and different definitions, but that's OK because when we scan for types | |
137 | with ambiguous names we will identify these and mark them conflicting. | |
138 | ||
139 | We populate one thing to help conflictedness marking. No unconflicted type | |
140 | may cite a conflicted one, but this means that conflictedness marking must | |
141 | walk from types to the types that cite them, which is the opposite of the | |
142 | usual order. We can make this easier to do by constructing a *citers* graph | |
143 | in cd_citers, which points from types to the types that cite them: because we | |
144 | emit forwards corresponding to every conflicted struct/union, we don't need | |
145 | to do this for citations of structs/unions by other types. This is very | |
146 | convenient for us, because that's the only type we don't traverse | |
147 | recursively: so we can construct the citers graph at the same time as we | |
148 | hash, rather than needing to add an extra pass. (This graph is a dynhash of | |
149 | *type hash values*, so it's small: in effect it is automatically | |
150 | deduplicated.) | |
151 | ||
152 | 2) COLLISIONAL MARKING. | |
153 | ||
154 | [ctf_dedup_detect_name_ambiguity, ctf_dedup_mark_conflicting_hash] | |
155 | We identify types whose names collide during the hashing process, and count | |
156 | the rough number of uses of each name (caching may throw it off a bit: this | |
157 | doesn't need to be accurate). We then mark the less-frequently-cited types | |
158 | with each names conflicting: the most-frequently-cited one goes into the | |
159 | shared type dictionary, while all others are duplicated into per-TU | |
160 | dictionaries, named after the input TU, that have the shared dictionary as a | |
161 | parent. For structures and unions this is not quite good enough: we'd like | |
162 | to have citations of forwards to ambiguously named structures and unions | |
163 | *stay* as citations of forwards, so that the user can tell that the caller | |
164 | didn't actually know which structure definition was meant: but if we put one | |
165 | of those structures into the shared dictionary, it would supplant and replace | |
166 | the forward, leaving no sign. So structures and unions do not take part in | |
167 | this popularity contest: if their names are ambiguous, they are just | |
168 | duplicated, and only a forward appears in the shared dict. | |
169 | ||
170 | [ctf_dedup_propagate_conflictedness] | |
171 | The process of marking types conflicted is itself recursive: we recursively | |
172 | traverse the cd_citers graph populated in the hashing pass above and mark | |
173 | everything that we encounter conflicted (without wasting time re-marking | |
174 | anything that is already marked). This naturally terminates just where we | |
175 | want it to (at types that are cited by no other types, and at structures and | |
176 | unions) and suffices to ensure that types that cite conflicted types are | |
177 | always marked conflicted. | |
178 | ||
179 | [ctf_dedup_conflictify_unshared, ctf_dedup_multiple_input_dicts] | |
180 | When linking in CTF_LINK_SHARE_DUPLICATED mode, we would like all types that | |
181 | are used in only one TU to end up in a per-CU dict. The easiest way to do | |
182 | that is to mark them conflicted. ctf_dedup_conflictify_unshared does this, | |
183 | traversing the output mapping and using ctf_dedup_multiple_input_dicts to | |
184 | check the number of input dicts each distinct type hash value came from: | |
185 | types that only came from one get marked conflicted. One caveat here is that | |
186 | we need to consider both structs and forwards to them: a struct that appears | |
187 | in one TU and has a dozen citations to an opaque forward in other TUs should | |
188 | *not* be considered to be used in only one TU, because users would find it | |
189 | useful to be able to traverse into opaque structures of that sort: so we use | |
190 | cd_struct_origin to check both structs/unions and the forwards corresponding | |
191 | to them. | |
192 | ||
193 | 3) EMISSION. | |
194 | ||
195 | [ctf_dedup_walk_output_mapping, ctf_dedup_rwalk_output_mapping, | |
196 | ctf_dedup_rwalk_one_output_mapping] | |
197 | Emission involves another walk of the entire output mapping, this time | |
198 | traversing everything other than struct members, recursively. Types are | |
199 | emitted from leaves to trunk, emitting all types a type cites before emitting | |
200 | the type itself. We sort the output mapping before traversing it, for | |
201 | reproducibility and also correctness: the input dicts may have parent/child | |
202 | relationships, so we simply sort all types that first appear in parents | |
203 | before all children, then sort types that first appear in dicts appearing | |
204 | earlier on the linker command line before those that appear later, then sort | |
205 | by input ctf_id_t. (This is where we use cd_output_first_gid, collected | |
206 | above.) | |
207 | ||
208 | The walking is done using a recursive traverser which arranges to not revisit | |
209 | any type already visited and to call its callback once per input GID for | |
210 | input GIDs corresponding to conflicted output types. The traverser only | |
211 | finds input types and calls a callback for them as many times as the output | |
212 | needs to appear: it doesn't try to figure out anything about where the output | |
213 | might go. That's done by the callback based on whether the type is | |
214 | marked conflicted or not. | |
215 | ||
216 | [ctf_dedup_emit_type, ctf_dedup_id_to_target, ctf_dedup_synthesize_forward] | |
217 | ctf_dedup_emit_type is the (sole) callback for ctf_dedup_walk_output_mapping. | |
218 | Conflicted types have all necessary dictionaries created, and then we emit | |
219 | the type into each dictionary in turn, working over each input CTF type | |
220 | corresponding to each hash value and using ctf_dedup_id_to_target to map each | |
221 | input ctf_id_t into the corresponding type in the output (dealing with input | |
222 | ctf_id_t's with parents in the process by simply chasing to the parent dict | |
223 | if the type we're looking up is in there). Emitting structures involves | |
224 | simply noting that the members of this structure need emission later on: | |
225 | because you cannot cite a single structure member from another type, we avoid | |
226 | emitting the members at this stage to keep recursion depths down a bit. | |
227 | ||
228 | At this point, if we have by some mischance decided that two different types | |
229 | with child types that hash to different values have in fact got the same hash | |
230 | value themselves and *not* marked it conflicting, the type walk will walk | |
231 | only *one* of them and in all likelihood we'll find that we are trying to | |
232 | emit a type into some child dictionary that references a type that was never | |
233 | emitted into that dictionary and assertion-fail. This always indicates a bug | |
234 | in the conflictedness marking machinery or the hashing code, or both. | |
235 | ||
236 | ctf_dedup_id_to_target calls ctf_dedup_synthesize_forward to do one extra | |
237 | thing, alluded to above: if this is a conflicted tagged structure or union, | |
238 | and the target is the shared dict (i.e., the type we're being asked to emit | |
239 | is not itself conflicted so can't just point straight at the conflicted | |
240 | type), we instead synthesise a forward with the same name, emit it into the | |
241 | shared dict, record it in cd_output_emission_conflicted_forwards so that we | |
242 | don't re-emit it, and return it. This means that cycles that contain | |
243 | conflicts do not cause the entire cycle to be replicated in every child: only | |
244 | that piece of the cycle which takes you back as far as the closest tagged | |
245 | struct/union needs to be replicated. This trick means that no part of the | |
246 | deduplicator needs a cycle detector: every recursive walk can stop at tagged | |
247 | structures. | |
248 | ||
249 | [ctf_dedup_emit_struct_members] | |
250 | The final stage of emission is to walk over all structures with members | |
251 | that need emission and emit all of them. Every type has been emitted at | |
252 | this stage, so emission cannot fail. | |
253 | ||
254 | [ctf_dedup_populate_type_mappings, ctf_dedup_populate_type_mapping] | |
255 | Finally, we update the input -> output type ID mappings used by the ctf-link | |
256 | machinery to update all the other sections. This is surprisingly expensive | |
257 | and may be replaced with a scheme which lets the ctf-link machinery extract | |
258 | the needed info directly from the deduplicator. */ | |
259 | ||
260 | /* Possible future optimizations are flagged with 'optimization opportunity' | |
261 | below. */ | |
262 | ||
263 | /* Global optimization opportunity: a GC pass, eliminating types with no direct | |
264 | or indirect citations from the other sections in the dictionary. */ | |
265 | ||
266 | /* Internal flag values for ctf_dedup_hash_type. */ | |
267 | ||
268 | /* Child call: consider forwardable types equivalent to forwards or stubs below | |
269 | this point. */ | |
270 | #define CTF_DEDUP_HASH_INTERNAL_CHILD 0x01 | |
271 | ||
272 | /* Transform references to single ctf_id_ts in passed-in inputs into a number | |
273 | that will fit in a uint64_t. Needs rethinking if CTF_MAX_TYPE is boosted. | |
274 | ||
275 | On 32-bit platforms, we pack things together differently: see the note | |
276 | above. */ | |
277 | ||
278 | #if UINTPTR_MAX < UINT64_MAX | |
279 | # define IDS_NEED_ALLOCATION 1 | |
280 | # define CTF_DEDUP_GID(fp, input, type) id_to_packed_id (fp, input, type) | |
281 | # define CTF_DEDUP_GID_TO_INPUT(id) packed_id_to_input (id) | |
282 | # define CTF_DEDUP_GID_TO_TYPE(id) packed_id_to_type (id) | |
283 | #else | |
284 | # define CTF_DEDUP_GID(fp, input, type) \ | |
285 | (void *) (((uint64_t) input) << 32 | (type)) | |
286 | # define CTF_DEDUP_GID_TO_INPUT(id) ((int) (((uint64_t) id) >> 32)) | |
287 | # define CTF_DEDUP_GID_TO_TYPE(id) (ctf_id_t) (((uint64_t) id) & ~(0xffffffff00000000ULL)) | |
288 | #endif | |
289 | ||
290 | #ifdef IDS_NEED_ALLOCATION | |
291 | ||
292 | /* This is the 32-bit path, which stores GIDs in a pool and returns a pointer | |
293 | into the pool. It is notably less efficient than the 64-bit direct storage | |
294 | approach, but with a smaller key, this is all we can do. */ | |
295 | ||
296 | static void * | |
297 | id_to_packed_id (ctf_file_t *fp, int input_num, ctf_id_t type) | |
298 | { | |
299 | const void *lookup; | |
300 | ctf_type_id_key_t *dynkey = NULL; | |
301 | ctf_type_id_key_t key = { input_num, type }; | |
302 | ||
303 | if (!ctf_dynhash_lookup_kv (fp->ctf_dedup.cd_id_to_file_t, | |
304 | &key, &lookup, NULL)) | |
305 | { | |
306 | if ((dynkey = malloc (sizeof (ctf_type_id_key_t))) == NULL) | |
307 | goto oom; | |
308 | memcpy (dynkey, &key, sizeof (ctf_type_id_key_t)); | |
309 | ||
310 | if (ctf_dynhash_insert (fp->ctf_dedup.cd_id_to_file_t, dynkey, NULL) < 0) | |
311 | goto oom; | |
312 | ||
313 | ctf_dynhash_lookup_kv (fp->ctf_dedup.cd_id_to_file_t, | |
314 | dynkey, &lookup, NULL); | |
315 | } | |
316 | /* We use a raw assert() here because there isn't really a way to get any sort | |
317 | of error back from this routine without vastly complicating things for the | |
318 | much more common case of !IDS_NEED_ALLOCATION. */ | |
319 | assert (lookup); | |
320 | return (void *) lookup; | |
321 | ||
322 | oom: | |
323 | free (dynkey); | |
324 | ctf_set_errno (fp, ENOMEM); | |
325 | return NULL; | |
326 | } | |
327 | ||
328 | static int | |
329 | packed_id_to_input (const void *id) | |
330 | { | |
331 | const ctf_type_id_key_t *key = (ctf_type_id_key_t *) id; | |
332 | ||
333 | return key->ctii_input_num; | |
334 | } | |
335 | ||
336 | static ctf_id_t | |
337 | packed_id_to_type (const void *id) | |
338 | { | |
339 | const ctf_type_id_key_t *key = (ctf_type_id_key_t *) id; | |
340 | ||
341 | return key->ctii_type; | |
342 | } | |
343 | #endif | |
344 | ||
345 | /* Make an element in a dynhash-of-dynsets, or return it if already present. */ | |
346 | ||
347 | static ctf_dynset_t * | |
348 | make_set_element (ctf_dynhash_t *set, const void *key) | |
349 | { | |
350 | ctf_dynset_t *element; | |
351 | ||
352 | if ((element = ctf_dynhash_lookup (set, key)) == NULL) | |
353 | { | |
354 | if ((element = ctf_dynset_create (htab_hash_string, | |
355 | ctf_dynset_eq_string, | |
356 | NULL)) == NULL) | |
357 | return NULL; | |
358 | ||
359 | if (ctf_dynhash_insert (set, (void *) key, element) < 0) | |
360 | { | |
361 | ctf_dynset_destroy (element); | |
362 | return NULL; | |
363 | } | |
364 | } | |
365 | ||
366 | return element; | |
367 | } | |
368 | ||
369 | /* Initialize the dedup atoms table. */ | |
370 | int | |
371 | ctf_dedup_atoms_init (ctf_file_t *fp) | |
372 | { | |
373 | if (fp->ctf_dedup_atoms) | |
374 | return 0; | |
375 | ||
376 | if (!fp->ctf_dedup_atoms_alloc) | |
377 | { | |
378 | if ((fp->ctf_dedup_atoms_alloc | |
379 | = ctf_dynset_create (htab_hash_string, ctf_dynset_eq_string, | |
380 | free)) == NULL) | |
381 | return ctf_set_errno (fp, ENOMEM); | |
382 | } | |
383 | fp->ctf_dedup_atoms = fp->ctf_dedup_atoms_alloc; | |
384 | return 0; | |
385 | } | |
386 | ||
387 | /* Intern things in the dedup atoms table. */ | |
388 | ||
389 | static const char * | |
390 | intern (ctf_file_t *fp, char *atom) | |
391 | { | |
392 | const void *foo; | |
393 | ||
394 | if (atom == NULL) | |
395 | return NULL; | |
396 | ||
397 | if (!ctf_dynset_exists (fp->ctf_dedup_atoms, atom, &foo)) | |
398 | { | |
399 | if (ctf_dynset_insert (fp->ctf_dedup_atoms, atom) < 0) | |
400 | { | |
401 | ctf_set_errno (fp, ENOMEM); | |
402 | return NULL; | |
403 | } | |
404 | foo = atom; | |
405 | } | |
406 | else | |
407 | free (atom); | |
408 | ||
409 | return (const char *) foo; | |
410 | } | |
411 | ||
412 | /* Add an indication of the namespace to a type name in a way that is not valid | |
413 | for C identifiers. Used to maintain hashes of type names to other things | |
414 | while allowing for the four C namespaces (normal, struct, union, enum). | |
415 | Return a new dynamically-allocated string. */ | |
416 | static const char * | |
417 | ctf_decorate_type_name (ctf_file_t *fp, const char *name, int kind) | |
418 | { | |
419 | ctf_dedup_t *d = &fp->ctf_dedup; | |
420 | const char *ret; | |
421 | const char *k; | |
422 | char *p; | |
423 | size_t i; | |
424 | ||
425 | switch (kind) | |
426 | { | |
427 | case CTF_K_STRUCT: | |
428 | k = "s "; | |
429 | i = 0; | |
430 | break; | |
431 | case CTF_K_UNION: | |
432 | k = "u "; | |
433 | i = 1; | |
434 | break; | |
435 | case CTF_K_ENUM: | |
436 | k = "e "; | |
437 | i = 2; | |
438 | break; | |
439 | default: | |
440 | k = ""; | |
441 | i = 3; | |
442 | } | |
443 | ||
444 | if ((ret = ctf_dynhash_lookup (d->cd_decorated_names[i], name)) == NULL) | |
445 | { | |
446 | char *str; | |
447 | ||
448 | if ((str = malloc (strlen (name) + strlen (k) + 1)) == NULL) | |
449 | goto oom; | |
450 | ||
451 | p = stpcpy (str, k); | |
452 | strcpy (p, name); | |
453 | ret = intern (fp, str); | |
454 | if (!ret) | |
455 | goto oom; | |
456 | ||
457 | if (ctf_dynhash_cinsert (d->cd_decorated_names[i], name, ret) < 0) | |
458 | goto oom; | |
459 | } | |
460 | ||
461 | return ret; | |
462 | ||
463 | oom: | |
464 | ctf_set_errno (fp, ENOMEM); | |
465 | return NULL; | |
466 | } | |
467 | ||
468 | /* Hash a type, possibly debugging-dumping something about it as well. */ | |
469 | static inline void | |
470 | ctf_dedup_sha1_add (ctf_sha1_t *sha1, const void *buf, size_t len, | |
471 | const char *description _libctf_unused_, | |
472 | unsigned long depth _libctf_unused_) | |
473 | { | |
474 | ctf_sha1_add (sha1, buf, len); | |
475 | ||
476 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
477 | ctf_sha1_t tmp; | |
478 | char tmp_hval[CTF_SHA1_SIZE]; | |
479 | tmp = *sha1; | |
480 | ctf_sha1_fini (&tmp, tmp_hval); | |
481 | ctf_dprintf ("%lu: after hash addition of %s: %s\n", depth, description, | |
482 | tmp_hval); | |
483 | #endif | |
484 | } | |
485 | ||
486 | static const char * | |
487 | ctf_dedup_hash_type (ctf_file_t *fp, ctf_file_t *input, | |
488 | ctf_file_t **inputs, uint32_t *parents, | |
489 | int input_num, ctf_id_t type, int flags, | |
490 | unsigned long depth, | |
491 | int (*populate_fun) (ctf_file_t *fp, | |
492 | ctf_file_t *input, | |
493 | ctf_file_t **inputs, | |
494 | int input_num, | |
495 | ctf_id_t type, | |
496 | void *id, | |
497 | const char *decorated_name, | |
498 | const char *hash)); | |
499 | ||
500 | /* Determine whether this type is being hashed as a stub (in which case it is | |
501 | unsafe to cache it). */ | |
502 | static int | |
503 | ctf_dedup_is_stub (const char *name, int kind, int fwdkind, int flags) | |
504 | { | |
505 | /* We can cache all types unless we are recursing to children and are hashing | |
506 | in a tagged struct, union or forward, all of which are replaced with their | |
507 | decorated name as a stub and will have different hash values when hashed at | |
508 | the top level. */ | |
509 | ||
510 | return ((flags & CTF_DEDUP_HASH_INTERNAL_CHILD) && name | |
511 | && (kind == CTF_K_STRUCT || kind == CTF_K_UNION | |
512 | || (kind == CTF_K_FORWARD && (fwdkind == CTF_K_STRUCT | |
513 | || fwdkind == CTF_K_UNION)))); | |
514 | } | |
515 | ||
516 | /* Populate struct_origin if need be (not already populated, or populated with | |
517 | a different origin), in which case it must go to -1, "shared".) | |
518 | ||
519 | Only called for forwards or forwardable types with names, when the link mode | |
520 | is CTF_LINK_SHARE_DUPLICATED. */ | |
521 | static int | |
522 | ctf_dedup_record_origin (ctf_file_t *fp, int input_num, const char *decorated, | |
523 | void *id) | |
524 | { | |
525 | ctf_dedup_t *d = &fp->ctf_dedup; | |
526 | void *origin; | |
527 | int populate_origin = 0; | |
528 | ||
529 | if (ctf_dynhash_lookup_kv (d->cd_struct_origin, decorated, NULL, &origin)) | |
530 | { | |
531 | if (CTF_DEDUP_GID_TO_INPUT (origin) != input_num | |
532 | && CTF_DEDUP_GID_TO_INPUT (origin) != -1) | |
533 | { | |
534 | populate_origin = 1; | |
535 | origin = CTF_DEDUP_GID (fp, -1, -1); | |
536 | } | |
537 | } | |
538 | else | |
539 | { | |
540 | populate_origin = 1; | |
541 | origin = id; | |
542 | } | |
543 | ||
544 | if (populate_origin) | |
545 | if (ctf_dynhash_cinsert (d->cd_struct_origin, decorated, origin) < 0) | |
546 | return ctf_set_errno (fp, errno); | |
547 | return 0; | |
548 | } | |
549 | ||
550 | /* Do the underlying hashing and recursion for ctf_dedup_hash_type (which it | |
551 | calls, recursively). */ | |
552 | ||
553 | static const char * | |
554 | ctf_dedup_rhash_type (ctf_file_t *fp, ctf_file_t *input, ctf_file_t **inputs, | |
555 | uint32_t *parents, int input_num, ctf_id_t type, | |
556 | void *type_id, const ctf_type_t *tp, const char *name, | |
557 | const char *decorated, int kind, int flags, | |
558 | unsigned long depth, | |
559 | int (*populate_fun) (ctf_file_t *fp, | |
560 | ctf_file_t *input, | |
561 | ctf_file_t **inputs, | |
562 | int input_num, | |
563 | ctf_id_t type, | |
564 | void *id, | |
565 | const char *decorated_name, | |
566 | const char *hash)) | |
567 | { | |
568 | ctf_dedup_t *d = &fp->ctf_dedup; | |
569 | ctf_next_t *i = NULL; | |
570 | ctf_sha1_t hash; | |
571 | ctf_id_t child_type; | |
572 | char hashbuf[CTF_SHA1_SIZE]; | |
573 | const char *hval = NULL; | |
574 | const char *whaterr; | |
575 | int err; | |
576 | ||
577 | const char *citer = NULL; | |
578 | ctf_dynset_t *citers = NULL; | |
579 | ||
580 | /* Add a citer to the citers set. */ | |
581 | #define ADD_CITER(citers, hval) \ | |
582 | do \ | |
583 | { \ | |
926c9e76 | 584 | whaterr = N_("error updating citers"); \ |
0f0c11f7 NA |
585 | if (!citers) \ |
586 | if ((citers = ctf_dynset_create (htab_hash_string, \ | |
587 | ctf_dynset_eq_string, \ | |
588 | NULL)) == NULL) \ | |
589 | goto oom; \ | |
590 | if (ctf_dynset_cinsert (citers, hval) < 0) \ | |
591 | goto oom; \ | |
592 | } while (0) | |
593 | ||
594 | /* If this is a named struct or union or a forward to one, and this is a child | |
595 | traversal, treat this type as if it were a forward -- do not recurse to | |
596 | children, ignore all content not already hashed in, and hash in the | |
597 | decorated name of the type instead. */ | |
598 | ||
599 | if (ctf_dedup_is_stub (name, kind, tp->ctt_type, flags)) | |
600 | { | |
601 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
602 | ctf_dprintf ("Struct/union/forward citation: substituting forwarding " | |
603 | "stub with decorated name %s\n", decorated); | |
604 | ||
605 | #endif | |
606 | ctf_sha1_init (&hash); | |
607 | ctf_dedup_sha1_add (&hash, decorated, strlen (decorated) + 1, | |
608 | "decorated struct/union/forward name", depth); | |
609 | ctf_sha1_fini (&hash, hashbuf); | |
610 | ||
611 | if ((hval = intern (fp, strdup (hashbuf))) == NULL) | |
612 | { | |
926c9e76 NA |
613 | ctf_err_warn (fp, 0, 0, _("%s (%i): out of memory during forwarding-" |
614 | "stub hashing for type with GID %p"), | |
615 | ctf_link_input_name (input), input_num, type_id); | |
0f0c11f7 NA |
616 | return NULL; /* errno is set for us. */ |
617 | } | |
618 | ||
926c9e76 | 619 | /* In share-duplicated link mode, make sure the origin of this type is |
0f0c11f7 NA |
620 | recorded, even if this is a type in a parent dict which will not be |
621 | directly traversed. */ | |
622 | if (d->cd_link_flags & CTF_LINK_SHARE_DUPLICATED | |
623 | && ctf_dedup_record_origin (fp, input_num, decorated, type_id) < 0) | |
624 | return NULL; /* errno is set for us. */ | |
625 | ||
626 | return hval; | |
627 | } | |
628 | ||
629 | /* Now ensure that subsequent recursive calls (but *not* the top-level call) | |
630 | get this treatment. */ | |
631 | flags |= CTF_DEDUP_HASH_INTERNAL_CHILD; | |
632 | ||
633 | /* If this is a struct, union, or forward with a name, record the unique | |
634 | originating input TU, if there is one. */ | |
635 | ||
636 | if (decorated && (ctf_forwardable_kind (kind) || kind != CTF_K_FORWARD)) | |
637 | if (d->cd_link_flags & CTF_LINK_SHARE_DUPLICATED | |
638 | && ctf_dedup_record_origin (fp, input_num, decorated, type_id) < 0) | |
639 | return NULL; /* errno is set for us. */ | |
640 | ||
641 | /* Mix in invariant stuff, transforming the type kind if needed. Note that | |
642 | the vlen is *not* hashed in: the actual variable-length info is hashed in | |
643 | instead, piecewise. The vlen is not part of the type, only the | |
644 | variable-length data is: identical types with distinct vlens are quite | |
645 | possible. Equally, we do not want to hash in the isroot flag: both the | |
646 | compiler and the deduplicator set the nonroot flag to indicate clashes with | |
647 | *other types in the same TU* with the same name: so two types can easily | |
648 | have distinct nonroot flags, yet be exactly the same type.*/ | |
649 | ||
650 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
651 | ctf_dprintf ("%lu: hashing thing with ID %i/%lx (kind %i): %s.\n", | |
652 | depth, input_num, type, kind, name ? name : ""); | |
653 | #endif | |
654 | ||
655 | ctf_sha1_init (&hash); | |
656 | if (name) | |
657 | ctf_dedup_sha1_add (&hash, name, strlen (name) + 1, "name", depth); | |
658 | ctf_dedup_sha1_add (&hash, &kind, sizeof (uint32_t), "kind", depth); | |
659 | ||
660 | /* Hash content of this type. */ | |
661 | switch (kind) | |
662 | { | |
663 | case CTF_K_UNKNOWN: | |
664 | /* No extra state. */ | |
665 | break; | |
666 | case CTF_K_FORWARD: | |
667 | ||
668 | /* Add the forwarded kind, stored in the ctt_type. */ | |
669 | ctf_dedup_sha1_add (&hash, &tp->ctt_type, sizeof (tp->ctt_type), | |
670 | "forwarded kind", depth); | |
671 | break; | |
672 | case CTF_K_INTEGER: | |
673 | case CTF_K_FLOAT: | |
674 | { | |
675 | ctf_encoding_t ep; | |
676 | memset (&ep, 0, sizeof (ctf_encoding_t)); | |
677 | ||
678 | ctf_dedup_sha1_add (&hash, &tp->ctt_size, sizeof (uint32_t), "size", | |
679 | depth); | |
680 | if (ctf_type_encoding (input, type, &ep) < 0) | |
681 | { | |
926c9e76 | 682 | whaterr = N_("error getting encoding"); |
0f0c11f7 NA |
683 | goto err; |
684 | } | |
685 | ctf_dedup_sha1_add (&hash, &ep, sizeof (ctf_encoding_t), "encoding", | |
686 | depth); | |
687 | break; | |
688 | } | |
689 | /* Types that reference other types. */ | |
690 | case CTF_K_TYPEDEF: | |
691 | case CTF_K_VOLATILE: | |
692 | case CTF_K_CONST: | |
693 | case CTF_K_RESTRICT: | |
694 | case CTF_K_POINTER: | |
695 | /* Hash the referenced type, if not already hashed, and mix it in. */ | |
696 | child_type = ctf_type_reference (input, type); | |
697 | if ((hval = ctf_dedup_hash_type (fp, input, inputs, parents, input_num, | |
698 | child_type, flags, depth, | |
699 | populate_fun)) == NULL) | |
700 | { | |
926c9e76 | 701 | whaterr = N_("error doing referenced type hashing"); |
0f0c11f7 NA |
702 | goto err; |
703 | } | |
704 | ctf_dedup_sha1_add (&hash, hval, strlen (hval) + 1, "referenced type", | |
705 | depth); | |
706 | citer = hval; | |
707 | ||
708 | break; | |
709 | ||
710 | /* The slices of two types hash identically only if the type they overlay | |
711 | also has the same encoding. This is not ideal, but in practice will work | |
712 | well enough. We work directly rather than using the CTF API because | |
713 | we do not want the slice's normal automatically-shine-through | |
714 | semantics to kick in here. */ | |
715 | case CTF_K_SLICE: | |
716 | { | |
717 | const ctf_slice_t *slice; | |
718 | const ctf_dtdef_t *dtd; | |
719 | ssize_t size; | |
720 | ssize_t increment; | |
721 | ||
722 | child_type = ctf_type_reference (input, type); | |
723 | ctf_get_ctt_size (input, tp, &size, &increment); | |
724 | ctf_dedup_sha1_add (&hash, &size, sizeof (ssize_t), "size", depth); | |
725 | ||
726 | if ((hval = ctf_dedup_hash_type (fp, input, inputs, parents, input_num, | |
727 | child_type, flags, depth, | |
728 | populate_fun)) == NULL) | |
729 | { | |
926c9e76 | 730 | whaterr = N_("error doing slice-referenced type hashing"); |
0f0c11f7 NA |
731 | goto err; |
732 | } | |
733 | ctf_dedup_sha1_add (&hash, hval, strlen (hval) + 1, "sliced type", | |
734 | depth); | |
735 | citer = hval; | |
736 | ||
737 | if ((dtd = ctf_dynamic_type (input, type)) != NULL) | |
738 | slice = &dtd->dtd_u.dtu_slice; | |
739 | else | |
740 | slice = (ctf_slice_t *) ((uintptr_t) tp + increment); | |
741 | ||
742 | ctf_dedup_sha1_add (&hash, &slice->cts_offset, | |
743 | sizeof (slice->cts_offset), "slice offset", depth); | |
744 | ctf_dedup_sha1_add (&hash, &slice->cts_bits, | |
745 | sizeof (slice->cts_bits), "slice bits", depth); | |
746 | break; | |
747 | } | |
748 | ||
749 | case CTF_K_ARRAY: | |
750 | { | |
751 | ctf_arinfo_t ar; | |
752 | ||
753 | if (ctf_array_info (input, type, &ar) < 0) | |
754 | { | |
926c9e76 | 755 | whaterr = N_("error getting array info"); |
0f0c11f7 NA |
756 | goto err; |
757 | } | |
758 | ||
759 | if ((hval = ctf_dedup_hash_type (fp, input, inputs, parents, input_num, | |
760 | ar.ctr_contents, flags, depth, | |
761 | populate_fun)) == NULL) | |
762 | { | |
926c9e76 | 763 | whaterr = N_("error doing array contents type hashing"); |
0f0c11f7 NA |
764 | goto err; |
765 | } | |
766 | ctf_dedup_sha1_add (&hash, hval, strlen (hval) + 1, "array contents", | |
767 | depth); | |
768 | ADD_CITER (citers, hval); | |
769 | ||
770 | if ((hval = ctf_dedup_hash_type (fp, input, inputs, parents, input_num, | |
771 | ar.ctr_index, flags, depth, | |
772 | populate_fun)) == NULL) | |
773 | { | |
926c9e76 | 774 | whaterr = N_("error doing array index type hashing"); |
0f0c11f7 NA |
775 | goto err; |
776 | } | |
777 | ctf_dedup_sha1_add (&hash, hval, strlen (hval) + 1, "array index", | |
778 | depth); | |
779 | ctf_dedup_sha1_add (&hash, &ar.ctr_nelems, sizeof (ar.ctr_nelems), | |
780 | "element count", depth); | |
781 | ADD_CITER (citers, hval); | |
782 | ||
783 | break; | |
784 | } | |
785 | case CTF_K_FUNCTION: | |
786 | { | |
787 | ctf_funcinfo_t fi; | |
788 | ctf_id_t *args; | |
789 | uint32_t j; | |
790 | ||
791 | if (ctf_func_type_info (input, type, &fi) < 0) | |
792 | { | |
926c9e76 | 793 | whaterr = N_("error getting func type info"); |
0f0c11f7 NA |
794 | goto err; |
795 | } | |
796 | ||
797 | if ((hval = ctf_dedup_hash_type (fp, input, inputs, parents, input_num, | |
798 | fi.ctc_return, flags, depth, | |
799 | populate_fun)) == NULL) | |
800 | { | |
926c9e76 | 801 | whaterr = N_("error getting func return type"); |
0f0c11f7 NA |
802 | goto err; |
803 | } | |
804 | ctf_dedup_sha1_add (&hash, hval, strlen (hval) + 1, "func return", | |
805 | depth); | |
806 | ctf_dedup_sha1_add (&hash, &fi.ctc_argc, sizeof (fi.ctc_argc), | |
807 | "func argc", depth); | |
808 | ctf_dedup_sha1_add (&hash, &fi.ctc_flags, sizeof (fi.ctc_flags), | |
809 | "func flags", depth); | |
810 | ADD_CITER (citers, hval); | |
811 | ||
812 | if ((args = calloc (fi.ctc_argc, sizeof (ctf_id_t))) == NULL) | |
813 | { | |
926c9e76 | 814 | whaterr = N_("error doing memory allocation"); |
0f0c11f7 NA |
815 | goto err; |
816 | } | |
817 | ||
818 | if (ctf_func_type_args (input, type, fi.ctc_argc, args) < 0) | |
819 | { | |
820 | free (args); | |
926c9e76 | 821 | whaterr = N_("error getting func arg type"); |
0f0c11f7 NA |
822 | goto err; |
823 | } | |
824 | for (j = 0; j < fi.ctc_argc; j++) | |
825 | { | |
826 | if ((hval = ctf_dedup_hash_type (fp, input, inputs, parents, | |
827 | input_num, args[j], flags, depth, | |
828 | populate_fun)) == NULL) | |
829 | { | |
830 | free (args); | |
926c9e76 | 831 | whaterr = N_("error doing func arg type hashing"); |
0f0c11f7 NA |
832 | goto err; |
833 | } | |
834 | ctf_dedup_sha1_add (&hash, hval, strlen (hval) + 1, "func arg type", | |
835 | depth); | |
836 | ADD_CITER (citers, hval); | |
837 | } | |
838 | free (args); | |
839 | break; | |
840 | } | |
841 | case CTF_K_ENUM: | |
842 | { | |
843 | int val; | |
844 | const char *ename; | |
845 | ||
846 | ctf_dedup_sha1_add (&hash, &tp->ctt_size, sizeof (uint32_t), | |
847 | "enum size", depth); | |
848 | while ((ename = ctf_enum_next (input, type, &i, &val)) != NULL) | |
849 | { | |
850 | ctf_dedup_sha1_add (&hash, ename, strlen (ename) + 1, "enumerator", | |
851 | depth); | |
852 | ctf_dedup_sha1_add (&hash, &val, sizeof (val), "enumerand", depth); | |
853 | } | |
854 | if (ctf_errno (input) != ECTF_NEXT_END) | |
855 | { | |
926c9e76 | 856 | whaterr = N_("error doing enum member iteration"); |
0f0c11f7 NA |
857 | goto err; |
858 | } | |
859 | break; | |
860 | } | |
861 | /* Top-level only. */ | |
862 | case CTF_K_STRUCT: | |
863 | case CTF_K_UNION: | |
864 | { | |
865 | ssize_t offset; | |
866 | const char *mname; | |
867 | ctf_id_t membtype; | |
868 | ssize_t size; | |
869 | ||
870 | ctf_get_ctt_size (input, tp, &size, NULL); | |
871 | ctf_dedup_sha1_add (&hash, &size, sizeof (ssize_t), "struct size", | |
872 | depth); | |
873 | ||
874 | while ((offset = ctf_member_next (input, type, &i, &mname, | |
875 | &membtype)) >= 0) | |
876 | { | |
877 | if (mname == NULL) | |
878 | mname = ""; | |
879 | ctf_dedup_sha1_add (&hash, mname, strlen (mname) + 1, | |
880 | "member name", depth); | |
881 | ||
882 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
883 | ctf_dprintf ("%lu: Traversing to member %s\n", depth, mname); | |
884 | #endif | |
885 | if ((hval = ctf_dedup_hash_type (fp, input, inputs, parents, | |
886 | input_num, membtype, flags, depth, | |
887 | populate_fun)) == NULL) | |
888 | { | |
926c9e76 | 889 | whaterr = N_("error doing struct/union member type hashing"); |
0f0c11f7 NA |
890 | goto iterr; |
891 | } | |
892 | ||
893 | ctf_dedup_sha1_add (&hash, hval, strlen (hval) + 1, "member hash", | |
894 | depth); | |
895 | ctf_dedup_sha1_add (&hash, &offset, sizeof (offset), "member offset", | |
896 | depth); | |
897 | ADD_CITER (citers, hval); | |
898 | } | |
899 | if (ctf_errno (input) != ECTF_NEXT_END) | |
900 | { | |
926c9e76 | 901 | whaterr = N_("error doing struct/union member iteration"); |
0f0c11f7 NA |
902 | goto err; |
903 | } | |
904 | break; | |
905 | } | |
906 | default: | |
926c9e76 | 907 | whaterr = N_("error: unknown type kind"); |
0f0c11f7 NA |
908 | goto err; |
909 | } | |
910 | ctf_sha1_fini (&hash, hashbuf); | |
911 | ||
912 | if ((hval = intern (fp, strdup (hashbuf))) == NULL) | |
913 | { | |
926c9e76 | 914 | whaterr = N_("cannot intern hash"); |
0f0c11f7 NA |
915 | goto oom; |
916 | } | |
917 | ||
918 | /* Populate the citers for this type's subtypes, now the hash for the type | |
919 | itself is known. */ | |
926c9e76 | 920 | whaterr = N_("error tracking citers"); |
0f0c11f7 NA |
921 | |
922 | if (citer) | |
923 | { | |
924 | ctf_dynset_t *citer_hashes; | |
925 | ||
926 | if ((citer_hashes = make_set_element (d->cd_citers, citer)) == NULL) | |
927 | goto oom; | |
928 | if (ctf_dynset_cinsert (citer_hashes, hval) < 0) | |
929 | goto oom; | |
930 | } | |
931 | else if (citers) | |
932 | { | |
933 | const void *k; | |
934 | ||
935 | while ((err = ctf_dynset_cnext (citers, &i, &k)) == 0) | |
936 | { | |
937 | ctf_dynset_t *citer_hashes; | |
938 | citer = (const char *) k; | |
939 | ||
940 | if ((citer_hashes = make_set_element (d->cd_citers, citer)) == NULL) | |
941 | goto oom; | |
942 | ||
943 | if (ctf_dynset_exists (citer_hashes, hval, NULL)) | |
944 | continue; | |
945 | if (ctf_dynset_cinsert (citer_hashes, hval) < 0) | |
946 | goto oom; | |
947 | } | |
948 | if (err != ECTF_NEXT_END) | |
949 | goto err; | |
950 | ctf_dynset_destroy (citers); | |
951 | } | |
952 | ||
953 | return hval; | |
954 | ||
955 | iterr: | |
956 | ctf_next_destroy (i); | |
957 | err: | |
958 | ctf_sha1_fini (&hash, NULL); | |
926c9e76 NA |
959 | ctf_err_warn (fp, 0, 0, _("%s (%i): %s: during type hashing for type %lx, " |
960 | "kind %i"), ctf_link_input_name (input), | |
961 | input_num, gettext (whaterr), type, kind); | |
0f0c11f7 NA |
962 | return NULL; |
963 | oom: | |
964 | ctf_set_errno (fp, errno); | |
926c9e76 NA |
965 | ctf_err_warn (fp, 0, 0, _("%s (%i): %s: during type hashing for type %lx, " |
966 | "kind %i"), ctf_link_input_name (input), | |
967 | input_num, gettext (whaterr), type, kind); | |
0f0c11f7 NA |
968 | return NULL; |
969 | } | |
970 | ||
971 | /* Hash a TYPE in the INPUT: FP is the eventual output, where the ctf_dedup | |
972 | state is stored. INPUT_NUM is the number of this input in the set of inputs. | |
973 | Record its hash in FP's cd_type_hashes once it is known. PARENTS is | |
974 | described in the comment above ctf_dedup. | |
975 | ||
976 | (The flags argument currently accepts only the flag | |
977 | CTF_DEDUP_HASH_INTERNAL_CHILD, an implementation detail used to prevent | |
978 | struct/union hashing in recursive traversals below the TYPE.) | |
979 | ||
980 | We use the CTF API rather than direct access wherever possible, because types | |
981 | that appear identical through the API should be considered identical, with | |
982 | one exception: slices should only be considered identical to other slices, | |
983 | not to the corresponding unsliced type. | |
984 | ||
985 | The POPULATE_FUN is a mandatory hook that populates other mappings with each | |
986 | type we see (excepting types that are recursively hashed as stubs). The | |
987 | caller should not rely on the order of calls to this hook, though it will be | |
988 | called at least once for every non-stub reference to every type. | |
989 | ||
990 | Returns a hash value (an atom), or NULL on error. */ | |
991 | ||
992 | static const char * | |
993 | ctf_dedup_hash_type (ctf_file_t *fp, ctf_file_t *input, | |
994 | ctf_file_t **inputs, uint32_t *parents, | |
995 | int input_num, ctf_id_t type, int flags, | |
996 | unsigned long depth, | |
997 | int (*populate_fun) (ctf_file_t *fp, | |
998 | ctf_file_t *input, | |
999 | ctf_file_t **inputs, | |
1000 | int input_num, | |
1001 | ctf_id_t type, | |
1002 | void *id, | |
1003 | const char *decorated_name, | |
1004 | const char *hash)) | |
1005 | { | |
1006 | ctf_dedup_t *d = &fp->ctf_dedup; | |
1007 | const ctf_type_t *tp; | |
1008 | void *type_id; | |
1009 | const char *hval = NULL; | |
1010 | const char *name; | |
1011 | const char *whaterr; | |
1012 | const char *decorated = NULL; | |
1013 | uint32_t kind, fwdkind; | |
1014 | ||
1015 | depth++; | |
1016 | ||
1017 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
1018 | ctf_dprintf ("%lu: ctf_dedup_hash_type (%i, %lx, flags %x)\n", depth, input_num, type, flags); | |
1019 | #endif | |
1020 | ||
1021 | /* The unimplemented type doesn't really exist, but must be noted in parent | |
1022 | hashes: so it gets a fixed, arbitrary hash. */ | |
1023 | if (type == 0) | |
1024 | return "00000000000000000000"; | |
1025 | ||
1026 | /* Possible optimization: if the input type is in the parent type space, just | |
1027 | copy recursively-cited hashes from the parent's types into the output | |
1028 | mapping rather than rehashing them. */ | |
1029 | ||
1030 | type_id = CTF_DEDUP_GID (fp, input_num, type); | |
1031 | ||
1032 | if ((tp = ctf_lookup_by_id (&input, type)) == NULL) | |
1033 | { | |
926c9e76 NA |
1034 | ctf_set_errno (fp, ctf_errno (input)); |
1035 | ctf_err_warn (fp, 0, 0, _("%s (%i): lookup failure for type %lx: " | |
1036 | "flags %x"), ctf_link_input_name (input), | |
1037 | input_num, type, flags); | |
0f0c11f7 NA |
1038 | return NULL; /* errno is set for us. */ |
1039 | } | |
1040 | ||
1041 | kind = LCTF_INFO_KIND (input, tp->ctt_info); | |
1042 | name = ctf_strraw (input, tp->ctt_name); | |
1043 | ||
1044 | if (tp->ctt_name == 0 || !name || name[0] == '\0') | |
1045 | name = NULL; | |
1046 | ||
1047 | /* Treat the unknown kind just like the unimplemented type. */ | |
1048 | if (kind == CTF_K_UNKNOWN) | |
1049 | return "00000000000000000000"; | |
1050 | ||
1051 | /* Decorate the name appropriately for the namespace it appears in: forwards | |
1052 | appear in the namespace of their referent. */ | |
1053 | ||
1054 | fwdkind = kind; | |
1055 | if (name) | |
1056 | { | |
1057 | if (kind == CTF_K_FORWARD) | |
1058 | fwdkind = tp->ctt_type; | |
1059 | ||
1060 | if ((decorated = ctf_decorate_type_name (fp, name, fwdkind)) == NULL) | |
1061 | return NULL; /* errno is set for us. */ | |
1062 | } | |
1063 | ||
1064 | /* If not hashing a stub, we can rely on various sorts of caches. | |
1065 | ||
1066 | Optimization opportunity: we may be able to avoid calling the populate_fun | |
1067 | sometimes here. */ | |
1068 | ||
1069 | if (!ctf_dedup_is_stub (name, kind, fwdkind, flags)) | |
1070 | { | |
1071 | if ((hval = ctf_dynhash_lookup (d->cd_type_hashes, type_id)) != NULL) | |
1072 | { | |
1073 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
1074 | ctf_dprintf ("%lu: Known hash for ID %i/%lx: %s\n", depth, input_num, | |
1075 | type, hval); | |
1076 | #endif | |
1077 | populate_fun (fp, input, inputs, input_num, type, type_id, | |
1078 | decorated, hval); | |
1079 | ||
1080 | return hval; | |
1081 | } | |
1082 | } | |
1083 | ||
1084 | /* We have never seen this type before, and must figure out its hash and the | |
1085 | hashes of the types it cites. | |
1086 | ||
1087 | Hash this type, and call ourselves recursively. (The hashing part is | |
1088 | optional, and is disabled if overidden_hval is set.) */ | |
1089 | ||
1090 | if ((hval = ctf_dedup_rhash_type (fp, input, inputs, parents, input_num, | |
1091 | type, type_id, tp, name, decorated, | |
1092 | kind, flags, depth, populate_fun)) == NULL) | |
1093 | return NULL; /* errno is set for us. */ | |
1094 | ||
1095 | /* The hash of this type is now known: record it unless caching is unsafe | |
1096 | because the hash value will change later. This will be the final storage | |
1097 | of this type's hash, so we call the population function on it. */ | |
1098 | ||
1099 | if (!ctf_dedup_is_stub (name, kind, fwdkind, flags)) | |
1100 | { | |
1101 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
1102 | ctf_dprintf ("Caching %lx, ID %p (%s), %s in final location\n", type, | |
1103 | type_id, name ? name : "", hval); | |
1104 | #endif | |
1105 | ||
1106 | if (ctf_dynhash_cinsert (d->cd_type_hashes, type_id, hval) < 0) | |
1107 | { | |
926c9e76 | 1108 | whaterr = N_("error hash caching"); |
0f0c11f7 NA |
1109 | goto oom; |
1110 | } | |
1111 | ||
1112 | if (populate_fun (fp, input, inputs, input_num, type, type_id, | |
1113 | decorated, hval) < 0) | |
1114 | { | |
926c9e76 | 1115 | whaterr = N_("error calling population function"); |
0f0c11f7 NA |
1116 | goto err; /* errno is set for us. */ |
1117 | } | |
1118 | } | |
1119 | ||
1120 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
1121 | ctf_dprintf ("%lu: Returning final hash for ID %i/%lx: %s\n", depth, | |
1122 | input_num, type, hval); | |
1123 | #endif | |
1124 | return hval; | |
1125 | ||
1126 | oom: | |
1127 | ctf_set_errno (fp, errno); | |
1128 | err: | |
926c9e76 NA |
1129 | ctf_err_warn (fp, 0, 0, _("%s (%i): %s: during type hashing, " |
1130 | "type %lx, kind %i"), | |
1131 | ctf_link_input_name (input), input_num, | |
1132 | gettext (whaterr), type, kind); | |
0f0c11f7 NA |
1133 | return NULL; |
1134 | } | |
1135 | ||
1136 | /* Populate a number of useful mappings not directly used by the hashing | |
1137 | machinery: the output mapping, the cd_name_counts mapping from name -> hash | |
1138 | -> count of hashval deduplication state for a given hashed type, and the | |
1139 | cd_output_first_tu mapping. */ | |
1140 | ||
1141 | static int | |
1142 | ctf_dedup_populate_mappings (ctf_file_t *fp, ctf_file_t *input _libctf_unused_, | |
1143 | ctf_file_t **inputs _libctf_unused_, | |
1144 | int input_num _libctf_unused_, | |
1145 | ctf_id_t type _libctf_unused_, void *id, | |
1146 | const char *decorated_name, | |
1147 | const char *hval) | |
1148 | { | |
1149 | ctf_dedup_t *d = &fp->ctf_dedup; | |
1150 | ctf_dynset_t *type_ids; | |
1151 | ctf_dynhash_t *name_counts; | |
1152 | long int count; | |
1153 | ||
1154 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
1155 | ctf_dprintf ("Hash %s, %s, into output mapping for %i/%lx @ %s\n", | |
1156 | hval, decorated_name ? decorated_name : "(unnamed)", | |
1157 | input_num, type, ctf_link_input_name (input)); | |
1158 | ||
1159 | const char *orig_hval; | |
1160 | ||
1161 | /* Make sure we never map a single GID to multiple hash values. */ | |
1162 | ||
1163 | if ((orig_hval = ctf_dynhash_lookup (d->cd_output_mapping_guard, id)) != NULL) | |
1164 | { | |
1165 | /* We can rely on pointer identity here, since all hashes are | |
1166 | interned. */ | |
1167 | if (!ctf_assert (fp, orig_hval == hval)) | |
1168 | return -1; | |
1169 | } | |
1170 | else | |
1171 | if (ctf_dynhash_cinsert (d->cd_output_mapping_guard, id, hval) < 0) | |
1172 | return ctf_set_errno (fp, errno); | |
1173 | #endif | |
1174 | ||
1175 | /* Record the type in the output mapping: if this is the first time this type | |
1176 | has been seen, also record it in the cd_output_first_gid. Because we | |
1177 | traverse types in TU order and we do not merge types after the hashing | |
1178 | phase, this will be the lowest TU this type ever appears in. */ | |
1179 | ||
1180 | if ((type_ids = ctf_dynhash_lookup (d->cd_output_mapping, | |
1181 | hval)) == NULL) | |
1182 | { | |
1183 | if (ctf_dynhash_cinsert (d->cd_output_first_gid, hval, id) < 0) | |
1184 | return ctf_set_errno (fp, errno); | |
1185 | ||
1186 | if ((type_ids = ctf_dynset_create (htab_hash_pointer, | |
1187 | htab_eq_pointer, | |
1188 | NULL)) == NULL) | |
1189 | return ctf_set_errno (fp, errno); | |
1190 | if (ctf_dynhash_insert (d->cd_output_mapping, (void *) hval, | |
1191 | type_ids) < 0) | |
1192 | { | |
1193 | ctf_dynset_destroy (type_ids); | |
1194 | return ctf_set_errno (fp, errno); | |
1195 | } | |
1196 | } | |
1197 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
1198 | { | |
1199 | /* Verify that all types with this hash are of the same kind, and that the | |
1200 | first TU a type was seen in never falls. */ | |
1201 | ||
1202 | int err; | |
1203 | const void *one_id; | |
1204 | ctf_next_t *i = NULL; | |
1205 | int orig_kind = ctf_type_kind_unsliced (input, type); | |
1206 | int orig_first_tu; | |
1207 | ||
1208 | orig_first_tu = CTF_DEDUP_GID_TO_INPUT | |
1209 | (ctf_dynhash_lookup (d->cd_output_first_gid, hval)); | |
1210 | if (!ctf_assert (fp, orig_first_tu <= CTF_DEDUP_GID_TO_INPUT (id))) | |
1211 | return -1; | |
1212 | ||
1213 | while ((err = ctf_dynset_cnext (type_ids, &i, &one_id)) == 0) | |
1214 | { | |
1215 | ctf_file_t *foo = inputs[CTF_DEDUP_GID_TO_INPUT (one_id)]; | |
1216 | ctf_id_t bar = CTF_DEDUP_GID_TO_TYPE (one_id); | |
1217 | if (ctf_type_kind_unsliced (foo, bar) != orig_kind) | |
1218 | { | |
926c9e76 | 1219 | ctf_err_warn (fp, 1, 0, "added wrong kind to output mapping " |
0f0c11f7 NA |
1220 | "for hash %s named %s: %p/%lx from %s is " |
1221 | "kind %i, but newly-added %p/%lx from %s is " | |
1222 | "kind %i", hval, | |
1223 | decorated_name ? decorated_name : "(unnamed)", | |
1224 | (void *) foo, bar, | |
1225 | ctf_link_input_name (foo), | |
1226 | ctf_type_kind_unsliced (foo, bar), | |
1227 | (void *) input, type, | |
1228 | ctf_link_input_name (input), orig_kind); | |
1229 | if (!ctf_assert (fp, ctf_type_kind_unsliced (foo, bar) | |
1230 | == orig_kind)) | |
1231 | return -1; | |
1232 | } | |
1233 | } | |
1234 | if (err != ECTF_NEXT_END) | |
1235 | return ctf_set_errno (fp, err); | |
1236 | } | |
1237 | #endif | |
1238 | ||
1239 | /* This function will be repeatedly called for the same types many times: | |
1240 | don't waste time reinserting the same keys in that case. */ | |
1241 | if (!ctf_dynset_exists (type_ids, id, NULL) | |
1242 | && ctf_dynset_insert (type_ids, id) < 0) | |
1243 | return ctf_set_errno (fp, errno); | |
1244 | ||
1245 | /* The rest only needs to happen for types with names. */ | |
1246 | if (!decorated_name) | |
1247 | return 0; | |
1248 | ||
1249 | /* Count the number of occurrences of the hash value for this GID. */ | |
1250 | ||
1251 | hval = ctf_dynhash_lookup (d->cd_type_hashes, id); | |
1252 | ||
1253 | /* Mapping from name -> hash(hashval, count) not already present? */ | |
1254 | if ((name_counts = ctf_dynhash_lookup (d->cd_name_counts, | |
1255 | decorated_name)) == NULL) | |
1256 | { | |
1257 | if ((name_counts = ctf_dynhash_create (ctf_hash_string, | |
1258 | ctf_hash_eq_string, | |
1259 | NULL, NULL)) == NULL) | |
1260 | return ctf_set_errno (fp, errno); | |
1261 | if (ctf_dynhash_cinsert (d->cd_name_counts, decorated_name, | |
1262 | name_counts) < 0) | |
1263 | { | |
1264 | ctf_dynhash_destroy (name_counts); | |
1265 | return ctf_set_errno (fp, errno); | |
1266 | } | |
1267 | } | |
1268 | ||
1269 | /* This will, conveniently, return NULL (i.e. 0) for a new entry. */ | |
1270 | count = (long int) (uintptr_t) ctf_dynhash_lookup (name_counts, hval); | |
1271 | ||
1272 | if (ctf_dynhash_cinsert (name_counts, hval, | |
1273 | (const void *) (uintptr_t) (count + 1)) < 0) | |
1274 | return ctf_set_errno (fp, errno); | |
1275 | ||
1276 | return 0; | |
1277 | } | |
1278 | ||
1279 | /* Mark a single hash as corresponding to a conflicting type. Mark all types | |
1280 | that cite it as conflicting as well, terminating the recursive walk only when | |
1281 | types that are already conflicted or types do not cite other types are seen. | |
1282 | (Tagged structures and unions do not appear in the cd_citers graph, so the | |
1283 | walk also terminates there, since any reference to a conflicting structure is | |
1284 | just going to reference an unconflicting forward instead: see | |
1285 | ctf_dedup_maybe_synthesize_forward.) */ | |
1286 | ||
1287 | static int | |
1288 | ctf_dedup_mark_conflicting_hash (ctf_file_t *fp, const char *hval) | |
1289 | { | |
1290 | ctf_dedup_t *d = &fp->ctf_dedup; | |
1291 | ctf_next_t *i = NULL; | |
1292 | int err; | |
1293 | const void *k; | |
1294 | ctf_dynset_t *citers; | |
1295 | ||
1296 | /* Mark conflicted if not already so marked. */ | |
1297 | if (ctf_dynset_exists (d->cd_conflicting_types, hval, NULL)) | |
1298 | return 0; | |
1299 | ||
1300 | ctf_dprintf ("Marking %s as conflicted\n", hval); | |
1301 | ||
1302 | if (ctf_dynset_cinsert (d->cd_conflicting_types, hval) < 0) | |
1303 | { | |
1304 | ctf_dprintf ("Out of memory marking %s as conflicted\n", hval); | |
1305 | ctf_set_errno (fp, errno); | |
1306 | return -1; | |
1307 | } | |
1308 | ||
1309 | /* If any types cite this type, mark them conflicted too. */ | |
1310 | if ((citers = ctf_dynhash_lookup (d->cd_citers, hval)) == NULL) | |
1311 | return 0; | |
1312 | ||
1313 | while ((err = ctf_dynset_cnext (citers, &i, &k)) == 0) | |
1314 | { | |
1315 | const char *hv = (const char *) k; | |
1316 | ||
1317 | if (ctf_dynset_exists (d->cd_conflicting_types, hv, NULL)) | |
1318 | continue; | |
1319 | ||
1320 | if (ctf_dedup_mark_conflicting_hash (fp, hv) < 0) | |
1321 | { | |
1322 | ctf_next_destroy (i); | |
1323 | return -1; /* errno is set for us. */ | |
1324 | } | |
1325 | } | |
1326 | if (err != ECTF_NEXT_END) | |
1327 | return ctf_set_errno (fp, err); | |
1328 | ||
1329 | return 0; | |
1330 | } | |
1331 | ||
1332 | /* Look up a type kind from the output mapping, given a type hash value. */ | |
1333 | static int | |
1334 | ctf_dedup_hash_kind (ctf_file_t *fp, ctf_file_t **inputs, const char *hash) | |
1335 | { | |
1336 | ctf_dedup_t *d = &fp->ctf_dedup; | |
1337 | void *id; | |
1338 | ctf_dynset_t *type_ids; | |
1339 | ||
1340 | /* Precondition: the output mapping is populated. */ | |
1341 | if (!ctf_assert (fp, ctf_dynhash_elements (d->cd_output_mapping) > 0)) | |
1342 | return -1; | |
1343 | ||
1344 | /* Look up some GID from the output hash for this type. (They are all | |
1345 | identical, so we can pick any). Don't assert if someone calls this | |
1346 | function wrongly, but do assert if the output mapping knows about the hash, | |
1347 | but has nothing associated with it. */ | |
1348 | ||
1349 | type_ids = ctf_dynhash_lookup (d->cd_output_mapping, hash); | |
1350 | if (!type_ids) | |
1351 | { | |
1352 | ctf_dprintf ("Looked up type kind by nonexistent hash %s.\n", hash); | |
1353 | return ctf_set_errno (fp, ECTF_INTERNAL); | |
1354 | } | |
1355 | id = ctf_dynset_lookup_any (type_ids); | |
1356 | if (!ctf_assert (fp, id)) | |
1357 | return -1; | |
1358 | ||
1359 | return ctf_type_kind_unsliced (inputs[CTF_DEDUP_GID_TO_INPUT (id)], | |
1360 | CTF_DEDUP_GID_TO_TYPE (id)); | |
1361 | } | |
1362 | ||
1363 | /* Used to keep a count of types: i.e. distinct type hash values. */ | |
1364 | typedef struct ctf_dedup_type_counter | |
1365 | { | |
1366 | ctf_file_t *fp; | |
1367 | ctf_file_t **inputs; | |
1368 | int num_non_forwards; | |
1369 | } ctf_dedup_type_counter_t; | |
1370 | ||
1371 | /* Add to the type counter for one name entry from the cd_name_counts. */ | |
1372 | static int | |
1373 | ctf_dedup_count_types (void *key_, void *value _libctf_unused_, void *arg_) | |
1374 | { | |
1375 | const char *hval = (const char *) key_; | |
1376 | int kind; | |
1377 | ctf_dedup_type_counter_t *arg = (ctf_dedup_type_counter_t *) arg_; | |
1378 | ||
1379 | kind = ctf_dedup_hash_kind (arg->fp, arg->inputs, hval); | |
1380 | ||
1381 | /* We rely on ctf_dedup_hash_kind setting the fp to -ECTF_INTERNAL on error to | |
1382 | smuggle errors out of here. */ | |
1383 | ||
1384 | if (kind != CTF_K_FORWARD) | |
1385 | { | |
1386 | arg->num_non_forwards++; | |
1387 | ctf_dprintf ("Counting hash %s: kind %i: num_non_forwards is %i\n", | |
1388 | hval, kind, arg->num_non_forwards); | |
1389 | } | |
1390 | ||
1391 | /* We only need to know if there is more than one non-forward (an ambiguous | |
1392 | type): don't waste time iterating any more than needed to figure that | |
1393 | out. */ | |
1394 | ||
1395 | if (arg->num_non_forwards > 1) | |
1396 | return 1; | |
1397 | ||
1398 | return 0; | |
1399 | } | |
1400 | ||
1401 | /* Detect name ambiguity and mark ambiguous names as conflicting, other than the | |
1402 | most common. */ | |
1403 | static int | |
1404 | ctf_dedup_detect_name_ambiguity (ctf_file_t *fp, ctf_file_t **inputs) | |
1405 | { | |
1406 | ctf_dedup_t *d = &fp->ctf_dedup; | |
1407 | ctf_next_t *i = NULL; | |
1408 | void *k; | |
1409 | void *v; | |
1410 | int err; | |
926c9e76 | 1411 | const char *whaterr; |
0f0c11f7 NA |
1412 | |
1413 | /* Go through cd_name_counts for all CTF namespaces in turn. */ | |
1414 | ||
1415 | while ((err = ctf_dynhash_next (d->cd_name_counts, &i, &k, &v)) == 0) | |
1416 | { | |
1417 | const char *decorated = (const char *) k; | |
1418 | ctf_dynhash_t *name_counts = (ctf_dynhash_t *) v; | |
1419 | ctf_next_t *j = NULL; | |
1420 | ||
1421 | /* If this is a forwardable kind or a forward (which we can tell without | |
1422 | consulting the type because its decorated name has a space as its | |
1423 | second character: see ctf_decorate_type_name), we are only interested | |
1424 | in whether this name has many hashes associated with it: any such name | |
1425 | is necessarily ambiguous, and types with that name are conflicting. | |
1426 | Once we know whether this is true, we can skip to the next name: so use | |
1427 | ctf_dynhash_iter_find for efficiency. */ | |
1428 | ||
1429 | if (decorated[0] != '\0' && decorated[1] == ' ') | |
1430 | { | |
1431 | ctf_dedup_type_counter_t counters = { fp, inputs, 0 }; | |
1432 | ctf_dynhash_t *counts = (ctf_dynhash_t *) v; | |
1433 | ||
1434 | ctf_dynhash_iter_find (counts, ctf_dedup_count_types, &counters); | |
1435 | ||
1436 | /* Check for assertion failure and pass it up. */ | |
1437 | if (ctf_errno (fp) == ECTF_INTERNAL) | |
1438 | goto assert_err; | |
1439 | ||
1440 | if (counters.num_non_forwards > 1) | |
1441 | { | |
1442 | const void *hval_; | |
1443 | ||
1444 | while ((err = ctf_dynhash_cnext (counts, &j, &hval_, NULL)) == 0) | |
1445 | { | |
1446 | const char *hval = (const char *) hval_; | |
1447 | ctf_dynset_t *type_ids; | |
1448 | void *id; | |
1449 | int kind; | |
1450 | ||
1451 | /* Dig through the types in this hash to find the non-forwards | |
1452 | and mark them ambiguous. */ | |
1453 | ||
1454 | type_ids = ctf_dynhash_lookup (d->cd_output_mapping, hval); | |
1455 | ||
1456 | /* Nonexistent? Must be a forward with no referent. */ | |
1457 | if (!type_ids) | |
1458 | continue; | |
1459 | ||
1460 | id = ctf_dynset_lookup_any (type_ids); | |
1461 | ||
1462 | kind = ctf_type_kind (inputs[CTF_DEDUP_GID_TO_INPUT (id)], | |
1463 | CTF_DEDUP_GID_TO_TYPE (id)); | |
1464 | ||
1465 | if (kind != CTF_K_FORWARD) | |
1466 | { | |
1467 | ctf_dprintf ("Marking %p, with hash %s, conflicting: one " | |
1468 | "of many non-forward GIDs for %s\n", id, | |
1469 | hval, (char *) k); | |
1470 | ctf_dedup_mark_conflicting_hash (fp, hval); | |
1471 | } | |
1472 | } | |
1473 | if (err != ECTF_NEXT_END) | |
1474 | { | |
926c9e76 | 1475 | whaterr = N_("error marking conflicting structs/unions"); |
0f0c11f7 NA |
1476 | goto iterr; |
1477 | } | |
1478 | } | |
1479 | } | |
1480 | else | |
1481 | { | |
1482 | /* This is an ordinary type. Find the most common type with this | |
1483 | name, and mark it unconflicting: all others are conflicting. (We | |
1484 | cannot do this sort of popularity contest with forwardable types | |
1485 | because any forwards to that type would be immediately unified with | |
1486 | the most-popular type on insertion, and we want conflicting structs | |
1487 | et al to have all forwards left intact, so the user is notified | |
1488 | that this type is conflicting. TODO: improve this in future by | |
1489 | setting such forwards non-root-visible.) */ | |
1490 | ||
1491 | const void *key; | |
1492 | const void *count; | |
1493 | const char *hval; | |
1494 | long max_hcount = -1; | |
1495 | const char *max_hval = NULL; | |
1496 | ||
1497 | if (ctf_dynhash_elements (name_counts) <= 1) | |
1498 | continue; | |
1499 | ||
1500 | /* First find the most common. */ | |
1501 | while ((err = ctf_dynhash_cnext (name_counts, &j, &key, &count)) == 0) | |
1502 | { | |
1503 | hval = (const char *) key; | |
1504 | if ((long int) (uintptr_t) count > max_hcount) | |
1505 | { | |
1506 | max_hcount = (long int) (uintptr_t) count; | |
1507 | max_hval = hval; | |
1508 | } | |
1509 | } | |
1510 | if (err != ECTF_NEXT_END) | |
1511 | { | |
926c9e76 | 1512 | whaterr = N_("error finding commonest conflicting type"); |
0f0c11f7 NA |
1513 | goto iterr; |
1514 | } | |
1515 | ||
1516 | /* Mark all the others as conflicting. */ | |
1517 | while ((err = ctf_dynhash_cnext (name_counts, &j, &key, NULL)) == 0) | |
1518 | { | |
1519 | hval = (const char *) key; | |
1520 | if (strcmp (max_hval, hval) == 0) | |
1521 | continue; | |
1522 | ||
1523 | ctf_dprintf ("Marking %s, an uncommon hash for %s, conflicting\n", | |
1524 | hval, (const char *) k); | |
1525 | if (ctf_dedup_mark_conflicting_hash (fp, hval) < 0) | |
1526 | { | |
926c9e76 | 1527 | whaterr = N_("error marking hashes as conflicting"); |
0f0c11f7 NA |
1528 | goto err; |
1529 | } | |
1530 | } | |
1531 | if (err != ECTF_NEXT_END) | |
1532 | { | |
926c9e76 | 1533 | whaterr = N_("marking uncommon conflicting types"); |
0f0c11f7 NA |
1534 | goto iterr; |
1535 | } | |
1536 | } | |
1537 | } | |
1538 | if (err != ECTF_NEXT_END) | |
1539 | { | |
926c9e76 | 1540 | whaterr = N_("scanning for ambiguous names"); |
0f0c11f7 NA |
1541 | goto iterr; |
1542 | } | |
1543 | ||
1544 | return 0; | |
1545 | ||
1546 | err: | |
1547 | ctf_next_destroy (i); | |
926c9e76 NA |
1548 | ctf_err_warn (fp, 0, 0, "%s", gettext (whaterr)); |
1549 | return -1; /* errno is set for us. */ | |
0f0c11f7 NA |
1550 | |
1551 | iterr: | |
926c9e76 | 1552 | ctf_err_warn (fp, 0, err, _("iteration failed: %s"), gettext (whaterr)); |
0f0c11f7 NA |
1553 | return ctf_set_errno (fp, err); |
1554 | ||
1555 | assert_err: | |
1556 | ctf_next_destroy (i); | |
1557 | return -1; /* errno is set for us. */ | |
1558 | } | |
1559 | ||
1560 | /* Initialize the deduplication machinery. */ | |
1561 | ||
1562 | static int | |
1563 | ctf_dedup_init (ctf_file_t *fp) | |
1564 | { | |
1565 | ctf_dedup_t *d = &fp->ctf_dedup; | |
1566 | size_t i; | |
1567 | ||
1568 | if (ctf_dedup_atoms_init (fp) < 0) | |
1569 | goto oom; | |
1570 | ||
1571 | #if IDS_NEED_ALLOCATION | |
1572 | if ((d->cd_id_to_file_t = ctf_dynhash_create (ctf_hash_type_id_key, | |
1573 | ctf_hash_eq_type_id_key, | |
1574 | free, NULL)) == NULL) | |
1575 | goto oom; | |
1576 | #endif | |
1577 | ||
1578 | for (i = 0; i < 4; i++) | |
1579 | { | |
1580 | if ((d->cd_decorated_names[i] = ctf_dynhash_create (ctf_hash_string, | |
1581 | ctf_hash_eq_string, | |
1582 | NULL, NULL)) == NULL) | |
1583 | goto oom; | |
1584 | } | |
1585 | ||
1586 | if ((d->cd_name_counts | |
1587 | = ctf_dynhash_create (ctf_hash_string, | |
1588 | ctf_hash_eq_string, NULL, | |
1589 | (ctf_hash_free_fun) ctf_dynhash_destroy)) == NULL) | |
1590 | goto oom; | |
1591 | ||
1592 | if ((d->cd_type_hashes | |
1593 | = ctf_dynhash_create (ctf_hash_integer, | |
1594 | ctf_hash_eq_integer, | |
1595 | NULL, NULL)) == NULL) | |
1596 | goto oom; | |
1597 | ||
1598 | if ((d->cd_struct_origin | |
1599 | = ctf_dynhash_create (ctf_hash_string, | |
1600 | ctf_hash_eq_string, | |
1601 | NULL, NULL)) == NULL) | |
1602 | goto oom; | |
1603 | ||
1604 | if ((d->cd_citers | |
1605 | = ctf_dynhash_create (ctf_hash_string, | |
1606 | ctf_hash_eq_string, NULL, | |
1607 | (ctf_hash_free_fun) ctf_dynset_destroy)) == NULL) | |
1608 | goto oom; | |
1609 | ||
1610 | if ((d->cd_output_mapping | |
1611 | = ctf_dynhash_create (ctf_hash_string, | |
1612 | ctf_hash_eq_string, NULL, | |
1613 | (ctf_hash_free_fun) ctf_dynset_destroy)) == NULL) | |
1614 | goto oom; | |
1615 | ||
1616 | if ((d->cd_output_first_gid | |
1617 | = ctf_dynhash_create (ctf_hash_string, | |
1618 | ctf_hash_eq_string, | |
1619 | NULL, NULL)) == NULL) | |
1620 | goto oom; | |
1621 | ||
1622 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
1623 | if ((d->cd_output_mapping_guard | |
1624 | = ctf_dynhash_create (ctf_hash_integer, | |
1625 | ctf_hash_eq_integer, NULL, NULL)) == NULL) | |
1626 | goto oom; | |
1627 | #endif | |
1628 | ||
1629 | if ((d->cd_emission_struct_members | |
1630 | = ctf_dynhash_create (ctf_hash_integer, | |
1631 | ctf_hash_eq_integer, | |
1632 | NULL, NULL)) == NULL) | |
1633 | goto oom; | |
1634 | ||
1635 | if ((d->cd_conflicting_types | |
1636 | = ctf_dynset_create (htab_hash_string, | |
1637 | ctf_dynset_eq_string, NULL)) == NULL) | |
1638 | goto oom; | |
1639 | ||
1640 | return 0; | |
1641 | ||
1642 | oom: | |
926c9e76 NA |
1643 | ctf_err_warn (fp, 0, ENOMEM, _("ctf_dedup_init: cannot initialize: " |
1644 | "out of memory")); | |
0f0c11f7 NA |
1645 | return ctf_set_errno (fp, ENOMEM); |
1646 | } | |
1647 | ||
1648 | void | |
1649 | ctf_dedup_fini (ctf_file_t *fp, ctf_file_t **outputs, uint32_t noutputs) | |
1650 | { | |
1651 | ctf_dedup_t *d = &fp->ctf_dedup; | |
1652 | size_t i; | |
1653 | ||
1654 | /* ctf_dedup_atoms is kept across links. */ | |
1655 | #if IDS_NEED_ALLOCATION | |
1656 | ctf_dynhash_destroy (d->cd_id_to_file_t); | |
1657 | #endif | |
1658 | for (i = 0; i < 4; i++) | |
1659 | ctf_dynhash_destroy (d->cd_decorated_names[i]); | |
1660 | ctf_dynhash_destroy (d->cd_name_counts); | |
1661 | ctf_dynhash_destroy (d->cd_type_hashes); | |
1662 | ctf_dynhash_destroy (d->cd_struct_origin); | |
1663 | ctf_dynhash_destroy (d->cd_citers); | |
1664 | ctf_dynhash_destroy (d->cd_output_mapping); | |
1665 | ctf_dynhash_destroy (d->cd_output_first_gid); | |
1666 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
1667 | ctf_dynhash_destroy (d->cd_output_mapping_guard); | |
1668 | #endif | |
1669 | ctf_dynhash_destroy (d->cd_emission_struct_members); | |
1670 | ctf_dynset_destroy (d->cd_conflicting_types); | |
1671 | ||
1672 | /* Free the per-output state. */ | |
1673 | if (outputs) | |
1674 | { | |
1675 | for (i = 0; i < noutputs; i++) | |
1676 | { | |
1677 | ctf_dedup_t *od = &outputs[i]->ctf_dedup; | |
1678 | ctf_dynhash_destroy (od->cd_output_emission_hashes); | |
1679 | ctf_dynhash_destroy (od->cd_output_emission_conflicted_forwards); | |
1680 | ctf_file_close (od->cd_output); | |
1681 | } | |
1682 | } | |
1683 | memset (d, 0, sizeof (ctf_dedup_t)); | |
1684 | } | |
1685 | ||
1686 | /* Return 1 if this type is cited by multiple input dictionaries. */ | |
1687 | ||
1688 | static int | |
1689 | ctf_dedup_multiple_input_dicts (ctf_file_t *output, ctf_file_t **inputs, | |
1690 | const char *hval) | |
1691 | { | |
1692 | ctf_dedup_t *d = &output->ctf_dedup; | |
1693 | ctf_dynset_t *type_ids; | |
1694 | ctf_next_t *i = NULL; | |
1695 | void *id; | |
1696 | ctf_file_t *found = NULL, *relative_found = NULL; | |
1697 | const char *type_id; | |
1698 | ctf_file_t *input_fp; | |
1699 | ctf_id_t input_id; | |
1700 | const char *name; | |
1701 | const char *decorated; | |
1702 | int fwdkind; | |
1703 | int multiple = 0; | |
1704 | int err; | |
1705 | ||
1706 | type_ids = ctf_dynhash_lookup (d->cd_output_mapping, hval); | |
1707 | if (!ctf_assert (output, type_ids)) | |
1708 | return -1; | |
1709 | ||
1710 | /* Scan across the IDs until we find proof that two disjoint dictionaries | |
1711 | are referenced. Exit as soon as possible. Optimization opportunity, but | |
1712 | possibly not worth it, given that this is only executed in | |
1713 | CTF_LINK_SHARE_DUPLICATED mode. */ | |
1714 | ||
1715 | while ((err = ctf_dynset_next (type_ids, &i, &id)) == 0) | |
1716 | { | |
1717 | ctf_file_t *fp = inputs[CTF_DEDUP_GID_TO_INPUT (id)]; | |
1718 | ||
1719 | if (fp == found || fp == relative_found) | |
1720 | continue; | |
1721 | ||
1722 | if (!found) | |
1723 | { | |
1724 | found = fp; | |
1725 | continue; | |
1726 | } | |
1727 | ||
1728 | if (!relative_found | |
1729 | && (fp->ctf_parent == found || found->ctf_parent == fp)) | |
1730 | { | |
1731 | relative_found = fp; | |
1732 | continue; | |
1733 | } | |
1734 | ||
1735 | multiple = 1; | |
1736 | ctf_next_destroy (i); | |
1737 | break; | |
1738 | } | |
1739 | if ((err != ECTF_NEXT_END) && (err != 0)) | |
1740 | { | |
926c9e76 NA |
1741 | ctf_err_warn (output, 0, err, _("iteration error " |
1742 | "propagating conflictedness")); | |
1743 | return ctf_set_errno (output, err); | |
0f0c11f7 NA |
1744 | } |
1745 | ||
1746 | if (multiple) | |
1747 | return multiple; | |
1748 | ||
1749 | /* This type itself does not appear in multiple input dicts: how about another | |
1750 | related type with the same name (e.g. a forward if this is a struct, | |
1751 | etc). */ | |
1752 | ||
1753 | type_id = ctf_dynset_lookup_any (type_ids); | |
1754 | if (!ctf_assert (output, type_id)) | |
1755 | return -1; | |
1756 | ||
1757 | input_fp = inputs[CTF_DEDUP_GID_TO_INPUT (type_id)]; | |
1758 | input_id = CTF_DEDUP_GID_TO_TYPE (type_id); | |
1759 | fwdkind = ctf_type_kind_forwarded (input_fp, input_id); | |
1760 | name = ctf_type_name_raw (input_fp, input_id); | |
1761 | ||
1762 | if ((fwdkind == CTF_K_STRUCT || fwdkind == CTF_K_UNION) | |
1763 | && name && name[0] != '\0') | |
1764 | { | |
1765 | const void *origin; | |
1766 | ||
1767 | if ((decorated = ctf_decorate_type_name (output, name, | |
1768 | fwdkind)) == NULL) | |
1769 | return -1; /* errno is set for us. */ | |
1770 | ||
1771 | origin = ctf_dynhash_lookup (d->cd_struct_origin, decorated); | |
1772 | if ((origin != NULL) && (CTF_DEDUP_GID_TO_INPUT (origin) < 0)) | |
1773 | multiple = 1; | |
1774 | } | |
1775 | ||
1776 | return multiple; | |
1777 | } | |
1778 | ||
1779 | /* Demote unconflicting types which reference only one input, or which reference | |
1780 | two inputs where one input is the parent of the other, into conflicting | |
1781 | types. Only used if the link mode is CTF_LINK_SHARE_DUPLICATED. */ | |
1782 | ||
1783 | static int | |
1784 | ctf_dedup_conflictify_unshared (ctf_file_t *output, ctf_file_t **inputs) | |
1785 | { | |
1786 | ctf_dedup_t *d = &output->ctf_dedup; | |
1787 | ctf_next_t *i = NULL; | |
1788 | int err; | |
1789 | const void *k; | |
1790 | ctf_dynset_t *to_mark = NULL; | |
1791 | ||
1792 | if ((to_mark = ctf_dynset_create (htab_hash_string, ctf_dynset_eq_string, | |
1793 | NULL)) == NULL) | |
1794 | goto err_no; | |
1795 | ||
1796 | while ((err = ctf_dynhash_cnext (d->cd_output_mapping, &i, &k, NULL)) == 0) | |
1797 | { | |
1798 | const char *hval = (const char *) k; | |
1799 | int conflicting; | |
1800 | ||
1801 | /* Types referenced by only one dict, with no type appearing under that | |
1802 | name elsewhere, are marked conflicting. */ | |
1803 | ||
1804 | conflicting = !ctf_dedup_multiple_input_dicts (output, inputs, hval); | |
1805 | ||
1806 | if (conflicting < 0) | |
1807 | goto err; /* errno is set for us. */ | |
1808 | ||
1809 | if (conflicting) | |
1810 | if (ctf_dynset_cinsert (to_mark, hval) < 0) | |
1811 | goto err; | |
1812 | } | |
1813 | if (err != ECTF_NEXT_END) | |
1814 | goto iterr; | |
1815 | ||
1816 | while ((err = ctf_dynset_cnext (to_mark, &i, &k)) == 0) | |
1817 | { | |
1818 | const char *hval = (const char *) k; | |
1819 | ||
1820 | if (ctf_dedup_mark_conflicting_hash (output, hval) < 0) | |
1821 | goto err; | |
1822 | } | |
1823 | if (err != ECTF_NEXT_END) | |
1824 | goto iterr; | |
1825 | ||
1826 | ctf_dynset_destroy (to_mark); | |
1827 | ||
1828 | return 0; | |
1829 | ||
1830 | err_no: | |
1831 | ctf_set_errno (output, errno); | |
1832 | err: | |
1833 | err = ctf_errno (output); | |
1834 | ctf_next_destroy (i); | |
1835 | iterr: | |
0f0c11f7 | 1836 | ctf_dynset_destroy (to_mark); |
926c9e76 NA |
1837 | ctf_err_warn (output, 0, err, _("conflictifying unshared types")); |
1838 | return ctf_set_errno (output, err); | |
0f0c11f7 NA |
1839 | } |
1840 | ||
1841 | /* The core deduplicator. Populate cd_output_mapping in the output ctf_dedup | |
1842 | with a mapping of all types that belong in this dictionary and where they | |
1843 | come from, and cd_conflicting_types with an indication of whether each type | |
1844 | is conflicted or not. OUTPUT is the top-level output: INPUTS is the array of | |
1845 | input dicts; NINPUTS is the size of that array; PARENTS is an NINPUTS-element | |
1846 | array with each element corresponding to a input which is a child dict set to | |
1847 | the number in the INPUTS array of that input's parent. | |
1848 | ||
1849 | If CU_MAPPED is set, this is a first pass for a link with a non-empty CU | |
1850 | mapping: only one output will result. | |
1851 | ||
1852 | Only deduplicates: does not emit the types into the output. Call | |
1853 | ctf_dedup_emit afterwards to do that. */ | |
1854 | ||
1855 | int | |
1856 | ctf_dedup (ctf_file_t *output, ctf_file_t **inputs, uint32_t ninputs, | |
1857 | uint32_t *parents, int cu_mapped) | |
1858 | { | |
1859 | ctf_dedup_t *d = &output->ctf_dedup; | |
1860 | size_t i; | |
1861 | ctf_next_t *it = NULL; | |
1862 | ||
1863 | for (i = 0; i < ninputs; i++) | |
1864 | ctf_dprintf ("Input %i: %s\n", (int) i, ctf_link_input_name (inputs[i])); | |
1865 | ||
1866 | if (ctf_dedup_init (output) < 0) | |
1867 | return -1; /* errno is set for us. */ | |
1868 | ||
1869 | /* Some flags do not apply when CU-mapping: this is not a duplicated link, | |
1870 | because there is only one output and we really don't want to end up marking | |
1871 | all nonconflicting but appears-only-once types as conflicting (which in the | |
1872 | CU-mapped link means we'd mark them all as non-root-visible!). */ | |
1873 | d->cd_link_flags = output->ctf_link_flags; | |
1874 | if (cu_mapped) | |
1875 | d->cd_link_flags &= ~(CTF_LINK_SHARE_DUPLICATED); | |
1876 | ||
1877 | /* Compute hash values for all types, recursively, treating child structures | |
1878 | and unions equivalent to forwards, and hashing in the name of the referent | |
1879 | of each such type into structures, unions, and non-opaque forwards. | |
1880 | Populate a mapping from decorated name (including an indication of | |
1881 | struct/union/enum namespace) to count of type hash values in | |
1882 | cd_name_counts, a mapping from and a mapping from hash values to input type | |
1883 | IDs in cd_output_mapping. */ | |
1884 | ||
1885 | ctf_dprintf ("Computing type hashes\n"); | |
1886 | for (i = 0; i < ninputs; i++) | |
1887 | { | |
1888 | ctf_id_t id; | |
1889 | ||
1890 | while ((id = ctf_type_next (inputs[i], &it, NULL, 1)) != CTF_ERR) | |
1891 | { | |
1892 | ctf_dedup_hash_type (output, inputs[i], inputs, parents, | |
1893 | i, id, 0, 0, ctf_dedup_populate_mappings); | |
1894 | } | |
1895 | if (ctf_errno (inputs[i]) != ECTF_NEXT_END) | |
1896 | { | |
926c9e76 NA |
1897 | ctf_set_errno (output, ctf_errno (inputs[i])); |
1898 | ctf_err_warn (output, 0, 0, _("iteration failure " | |
1899 | "computing type hashes")); | |
1900 | return -1; | |
0f0c11f7 NA |
1901 | } |
1902 | } | |
1903 | ||
1904 | /* Go through the cd_name_counts name->hash->count mapping for all CTF | |
1905 | namespaces: any name with many hashes associated with it at this stage is | |
1906 | necessarily ambiguous. Mark all the hashes except the most common as | |
1907 | conflicting in the output. */ | |
1908 | ||
1909 | ctf_dprintf ("Detecting type name ambiguity\n"); | |
1910 | if (ctf_dedup_detect_name_ambiguity (output, inputs) < 0) | |
1911 | return -1; /* errno is set for us. */ | |
1912 | ||
1913 | /* If the link mode is CTF_LINK_SHARE_DUPLICATED, we change any unconflicting | |
1914 | types whose output mapping references only one input dict into a | |
1915 | conflicting type, so that they end up in the per-CU dictionaries. */ | |
1916 | ||
1917 | if (d->cd_link_flags & CTF_LINK_SHARE_DUPLICATED) | |
1918 | { | |
1919 | ctf_dprintf ("Conflictifying unshared types\n"); | |
1920 | if (ctf_dedup_conflictify_unshared (output, inputs) < 0) | |
1921 | return -1; /* errno is set for us. */ | |
1922 | } | |
1923 | return 0; | |
1924 | } | |
1925 | ||
1926 | static int | |
1927 | ctf_dedup_rwalk_output_mapping (ctf_file_t *output, ctf_file_t **inputs, | |
1928 | uint32_t ninputs, uint32_t *parents, | |
1929 | ctf_dynset_t *already_visited, | |
1930 | const char *hval, | |
1931 | int (*visit_fun) (const char *hval, | |
1932 | ctf_file_t *output, | |
1933 | ctf_file_t **inputs, | |
1934 | uint32_t ninputs, | |
1935 | uint32_t *parents, | |
1936 | int already_visited, | |
1937 | ctf_file_t *input, | |
1938 | ctf_id_t type, | |
1939 | void *id, | |
1940 | int depth, | |
1941 | void *arg), | |
1942 | void *arg, unsigned long depth); | |
1943 | ||
1944 | /* Like ctf_dedup_rwalk_output_mapping (which see), only takes a single target | |
1945 | type and visits it. */ | |
1946 | static int | |
1947 | ctf_dedup_rwalk_one_output_mapping (ctf_file_t *output, | |
1948 | ctf_file_t **inputs, uint32_t ninputs, | |
1949 | uint32_t *parents, | |
1950 | ctf_dynset_t *already_visited, | |
1951 | int visited, void *type_id, | |
1952 | const char *hval, | |
1953 | int (*visit_fun) (const char *hval, | |
1954 | ctf_file_t *output, | |
1955 | ctf_file_t **inputs, | |
1956 | uint32_t ninputs, | |
1957 | uint32_t *parents, | |
1958 | int already_visited, | |
1959 | ctf_file_t *input, | |
1960 | ctf_id_t type, | |
1961 | void *id, | |
1962 | int depth, | |
1963 | void *arg), | |
1964 | void *arg, unsigned long depth) | |
1965 | { | |
1966 | ctf_dedup_t *d = &output->ctf_dedup; | |
1967 | ctf_file_t *fp; | |
1968 | int input_num; | |
1969 | ctf_id_t type; | |
1970 | int ret; | |
1971 | const char *whaterr; | |
1972 | ||
1973 | input_num = CTF_DEDUP_GID_TO_INPUT (type_id); | |
1974 | fp = inputs[input_num]; | |
1975 | type = CTF_DEDUP_GID_TO_TYPE (type_id); | |
1976 | ||
1977 | ctf_dprintf ("%lu: Starting walk over type %s, %i/%lx (%p), from %s, " | |
1978 | "kind %i\n", depth, hval, input_num, type, (void *) fp, | |
1979 | ctf_link_input_name (fp), ctf_type_kind_unsliced (fp, type)); | |
1980 | ||
1981 | /* Get the single call we do if this type has already been visited out of the | |
1982 | way. */ | |
1983 | if (visited) | |
1984 | return visit_fun (hval, output, inputs, ninputs, parents, visited, fp, | |
1985 | type, type_id, depth, arg); | |
1986 | ||
1987 | /* This macro is really ugly, but the alternative is repeating this code many | |
1988 | times, which is worse. */ | |
1989 | ||
1990 | #define CTF_TYPE_WALK(type, errlabel, errmsg) \ | |
1991 | do { \ | |
1992 | void *type_id; \ | |
1993 | const char *hashval; \ | |
1994 | int cited_type_input_num = input_num; \ | |
1995 | \ | |
1996 | if ((fp->ctf_flags & LCTF_CHILD) && (LCTF_TYPE_ISPARENT (fp, type))) \ | |
1997 | cited_type_input_num = parents[input_num]; \ | |
1998 | \ | |
1999 | type_id = CTF_DEDUP_GID (output, cited_type_input_num, type); \ | |
2000 | \ | |
2001 | if (type == 0) \ | |
2002 | { \ | |
2003 | ctf_dprintf ("Walking: unimplemented type\n"); \ | |
2004 | break; \ | |
2005 | } \ | |
2006 | \ | |
2007 | ctf_dprintf ("Looking up ID %i/%lx in type hashes\n", \ | |
2008 | cited_type_input_num, type); \ | |
2009 | hashval = ctf_dynhash_lookup (d->cd_type_hashes, type_id); \ | |
2010 | if (!ctf_assert (output, hashval)) \ | |
2011 | { \ | |
926c9e76 | 2012 | whaterr = N_("error looking up ID in type hashes"); \ |
0f0c11f7 NA |
2013 | goto errlabel; \ |
2014 | } \ | |
2015 | ctf_dprintf ("ID %i/%lx has hash %s\n", cited_type_input_num, type, \ | |
2016 | hashval); \ | |
2017 | \ | |
2018 | ret = ctf_dedup_rwalk_output_mapping (output, inputs, ninputs, parents, \ | |
2019 | already_visited, hashval, \ | |
2020 | visit_fun, arg, depth); \ | |
2021 | if (ret < 0) \ | |
2022 | { \ | |
2023 | whaterr = errmsg; \ | |
2024 | goto errlabel; \ | |
2025 | } \ | |
2026 | } while (0) | |
2027 | ||
2028 | switch (ctf_type_kind_unsliced (fp, type)) | |
2029 | { | |
2030 | case CTF_K_UNKNOWN: | |
2031 | /* Just skip things of unknown kind. */ | |
2032 | return 0; | |
2033 | case CTF_K_FORWARD: | |
2034 | case CTF_K_INTEGER: | |
2035 | case CTF_K_FLOAT: | |
2036 | case CTF_K_ENUM: | |
2037 | /* No types referenced. */ | |
2038 | break; | |
2039 | ||
2040 | case CTF_K_TYPEDEF: | |
2041 | case CTF_K_VOLATILE: | |
2042 | case CTF_K_CONST: | |
2043 | case CTF_K_RESTRICT: | |
2044 | case CTF_K_POINTER: | |
2045 | case CTF_K_SLICE: | |
2046 | CTF_TYPE_WALK (ctf_type_reference (fp, type), err, | |
926c9e76 | 2047 | N_("error during referenced type walk")); |
0f0c11f7 NA |
2048 | break; |
2049 | ||
2050 | case CTF_K_ARRAY: | |
2051 | { | |
2052 | ctf_arinfo_t ar; | |
2053 | ||
2054 | if (ctf_array_info (fp, type, &ar) < 0) | |
2055 | { | |
926c9e76 | 2056 | whaterr = N_("error during array info lookup"); |
0f0c11f7 NA |
2057 | goto err_msg; |
2058 | } | |
2059 | ||
926c9e76 NA |
2060 | CTF_TYPE_WALK (ar.ctr_contents, err, |
2061 | N_("error during array contents type walk")); | |
2062 | CTF_TYPE_WALK (ar.ctr_index, err, | |
2063 | N_("error during array index type walk")); | |
0f0c11f7 NA |
2064 | break; |
2065 | } | |
2066 | ||
2067 | case CTF_K_FUNCTION: | |
2068 | { | |
2069 | ctf_funcinfo_t fi; | |
2070 | ctf_id_t *args; | |
2071 | uint32_t j; | |
2072 | ||
2073 | if (ctf_func_type_info (fp, type, &fi) < 0) | |
2074 | { | |
926c9e76 | 2075 | whaterr = N_("error during func type info lookup"); |
0f0c11f7 NA |
2076 | goto err_msg; |
2077 | } | |
2078 | ||
926c9e76 NA |
2079 | CTF_TYPE_WALK (fi.ctc_return, err, |
2080 | N_("error during func return type walk")); | |
0f0c11f7 NA |
2081 | |
2082 | if ((args = calloc (fi.ctc_argc, sizeof (ctf_id_t))) == NULL) | |
2083 | { | |
926c9e76 | 2084 | whaterr = N_("error doing memory allocation"); |
0f0c11f7 NA |
2085 | goto err_msg; |
2086 | } | |
2087 | ||
2088 | if (ctf_func_type_args (fp, type, fi.ctc_argc, args) < 0) | |
2089 | { | |
926c9e76 | 2090 | whaterr = N_("error doing func arg type lookup"); |
0f0c11f7 NA |
2091 | free (args); |
2092 | goto err_msg; | |
2093 | } | |
2094 | ||
2095 | for (j = 0; j < fi.ctc_argc; j++) | |
926c9e76 NA |
2096 | CTF_TYPE_WALK (args[j], err_free_args, |
2097 | N_("error during Func arg type walk")); | |
0f0c11f7 NA |
2098 | free (args); |
2099 | break; | |
2100 | ||
2101 | err_free_args: | |
2102 | free (args); | |
2103 | goto err; | |
2104 | } | |
2105 | case CTF_K_STRUCT: | |
2106 | case CTF_K_UNION: | |
2107 | /* We do not recursively traverse the members of structures: they are | |
2108 | emitted later, in a separate pass. */ | |
2109 | break; | |
2110 | default: | |
926c9e76 NA |
2111 | whaterr = N_("CTF dict corruption: unknown type kind"); |
2112 | goto err_msg; | |
0f0c11f7 NA |
2113 | } |
2114 | ||
2115 | return visit_fun (hval, output, inputs, ninputs, parents, visited, fp, type, | |
2116 | type_id, depth, arg); | |
2117 | ||
2118 | err_msg: | |
2119 | ctf_set_errno (output, ctf_errno (fp)); | |
926c9e76 NA |
2120 | ctf_err_warn (output, 0, 0, _("%s in input file %s at type ID %lx"), |
2121 | gettext (whaterr), ctf_link_input_name (fp), type); | |
0f0c11f7 NA |
2122 | err: |
2123 | return -1; | |
2124 | } | |
2125 | /* Recursively traverse the output mapping, and do something with each type | |
2126 | visited, from leaves to root. VISIT_FUN, called as recursion unwinds, | |
2127 | returns a negative error code or zero. Type hashes may be visited more than | |
2128 | once, but are not recursed through repeatedly: ALREADY_VISITED tracks whether | |
2129 | types have already been visited. */ | |
2130 | static int | |
2131 | ctf_dedup_rwalk_output_mapping (ctf_file_t *output, ctf_file_t **inputs, | |
2132 | uint32_t ninputs, uint32_t *parents, | |
2133 | ctf_dynset_t *already_visited, | |
2134 | const char *hval, | |
2135 | int (*visit_fun) (const char *hval, | |
2136 | ctf_file_t *output, | |
2137 | ctf_file_t **inputs, | |
2138 | uint32_t ninputs, | |
2139 | uint32_t *parents, | |
2140 | int already_visited, | |
2141 | ctf_file_t *input, | |
2142 | ctf_id_t type, | |
2143 | void *id, | |
2144 | int depth, | |
2145 | void *arg), | |
2146 | void *arg, unsigned long depth) | |
2147 | { | |
2148 | ctf_dedup_t *d = &output->ctf_dedup; | |
2149 | ctf_next_t *i = NULL; | |
2150 | int err; | |
2151 | int visited = 1; | |
2152 | ctf_dynset_t *type_ids; | |
2153 | void *id; | |
2154 | ||
2155 | depth++; | |
2156 | ||
2157 | type_ids = ctf_dynhash_lookup (d->cd_output_mapping, hval); | |
2158 | if (!type_ids) | |
2159 | { | |
926c9e76 NA |
2160 | ctf_err_warn (output, 0, ECTF_INTERNAL, |
2161 | _("looked up type kind by nonexistent hash %s"), hval); | |
0f0c11f7 NA |
2162 | return ctf_set_errno (output, ECTF_INTERNAL); |
2163 | } | |
2164 | ||
2165 | /* Have we seen this type before? */ | |
2166 | ||
2167 | if (!ctf_dynset_exists (already_visited, hval, NULL)) | |
2168 | { | |
2169 | /* Mark as already-visited immediately, to eliminate the possibility of | |
2170 | cycles: but remember we have not actually visited it yet for the | |
2171 | upcoming call to the visit_fun. (All our callers handle cycles | |
2172 | properly themselves, so we can just abort them aggressively as soon as | |
2173 | we find ourselves in one.) */ | |
2174 | ||
2175 | visited = 0; | |
2176 | if (ctf_dynset_cinsert (already_visited, hval) < 0) | |
2177 | { | |
926c9e76 NA |
2178 | ctf_err_warn (output, 0, ENOMEM, |
2179 | _("out of memory tracking already-visited types")); | |
0f0c11f7 NA |
2180 | return ctf_set_errno (output, ENOMEM); |
2181 | } | |
2182 | } | |
2183 | ||
2184 | /* If this type is marked conflicted, traverse members and call | |
2185 | ctf_dedup_rwalk_output_mapping_once on all the unique ones: otherwise, just | |
2186 | pick a random one and use it. */ | |
2187 | ||
2188 | if (!ctf_dynset_exists (d->cd_conflicting_types, hval, NULL)) | |
2189 | { | |
2190 | id = ctf_dynset_lookup_any (type_ids); | |
2191 | if (!ctf_assert (output, id)) | |
2192 | return -1; | |
2193 | ||
2194 | return ctf_dedup_rwalk_one_output_mapping (output, inputs, ninputs, | |
2195 | parents, already_visited, | |
2196 | visited, id, hval, visit_fun, | |
2197 | arg, depth); | |
2198 | } | |
2199 | ||
2200 | while ((err = ctf_dynset_next (type_ids, &i, &id)) == 0) | |
2201 | { | |
2202 | int ret; | |
2203 | ||
2204 | ret = ctf_dedup_rwalk_one_output_mapping (output, inputs, ninputs, | |
2205 | parents, already_visited, | |
2206 | visited, id, hval, | |
2207 | visit_fun, arg, depth); | |
2208 | if (ret < 0) | |
2209 | { | |
2210 | ctf_next_destroy (i); | |
2211 | return ret; /* errno is set for us. */ | |
2212 | } | |
2213 | } | |
2214 | if (err != ECTF_NEXT_END) | |
2215 | { | |
926c9e76 | 2216 | ctf_err_warn (output, 0, err, _("cannot walk conflicted type")); |
0f0c11f7 NA |
2217 | return ctf_set_errno (output, err); |
2218 | } | |
2219 | ||
2220 | return 0; | |
2221 | } | |
2222 | ||
2223 | typedef struct ctf_sort_om_cb_arg | |
2224 | { | |
2225 | ctf_file_t **inputs; | |
2226 | uint32_t ninputs; | |
2227 | ctf_dedup_t *d; | |
2228 | } ctf_sort_om_cb_arg_t; | |
2229 | ||
2230 | /* Sort the output mapping into order: types first appearing in earlier inputs | |
2231 | first, parents preceding children: if types first appear in the same input, | |
2232 | sort those with earlier ctf_id_t's first. */ | |
2233 | static int | |
2234 | sort_output_mapping (const ctf_next_hkv_t *one, const ctf_next_hkv_t *two, | |
2235 | void *arg_) | |
2236 | { | |
2237 | ctf_sort_om_cb_arg_t *arg = (ctf_sort_om_cb_arg_t *) arg_; | |
2238 | ctf_dedup_t *d = arg->d; | |
2239 | const char *one_hval = (const char *) one->hkv_key; | |
2240 | const char *two_hval = (const char *) two->hkv_key; | |
2241 | void *one_gid, *two_gid; | |
2242 | uint32_t one_ninput; | |
2243 | uint32_t two_ninput; | |
2244 | ctf_file_t *one_fp; | |
2245 | ctf_file_t *two_fp; | |
2246 | ctf_id_t one_type; | |
2247 | ctf_id_t two_type; | |
2248 | ||
2249 | one_gid = ctf_dynhash_lookup (d->cd_output_first_gid, one_hval); | |
2250 | two_gid = ctf_dynhash_lookup (d->cd_output_first_gid, two_hval); | |
2251 | ||
2252 | one_ninput = CTF_DEDUP_GID_TO_INPUT (one_gid); | |
2253 | two_ninput = CTF_DEDUP_GID_TO_INPUT (two_gid); | |
2254 | ||
2255 | one_type = CTF_DEDUP_GID_TO_TYPE (one_gid); | |
2256 | two_type = CTF_DEDUP_GID_TO_TYPE (two_gid); | |
2257 | ||
2258 | /* It's kind of hard to smuggle an assertion failure out of here. */ | |
2259 | assert (one_ninput < arg->ninputs && two_ninput < arg->ninputs); | |
2260 | ||
2261 | one_fp = arg->inputs[one_ninput]; | |
2262 | two_fp = arg->inputs[two_ninput]; | |
2263 | ||
2264 | /* Parents before children. */ | |
2265 | ||
2266 | if (!(one_fp->ctf_flags & LCTF_CHILD) | |
2267 | && (two_fp->ctf_flags & LCTF_CHILD)) | |
2268 | return -1; | |
2269 | else if ((one_fp->ctf_flags & LCTF_CHILD) | |
2270 | && !(two_fp->ctf_flags & LCTF_CHILD)) | |
2271 | return 1; | |
2272 | ||
2273 | /* ninput order, types appearing in earlier TUs first. */ | |
2274 | ||
2275 | if (one_ninput < two_ninput) | |
2276 | return -1; | |
2277 | else if (two_ninput < one_ninput) | |
2278 | return 1; | |
2279 | ||
2280 | /* Same TU. Earliest ctf_id_t first. They cannot be the same. */ | |
2281 | ||
2282 | assert (one_type != two_type); | |
2283 | if (one_type < two_type) | |
2284 | return -1; | |
2285 | else | |
2286 | return 1; | |
2287 | } | |
2288 | ||
2289 | /* The public entry point to ctf_dedup_rwalk_output_mapping, above. */ | |
2290 | static int | |
2291 | ctf_dedup_walk_output_mapping (ctf_file_t *output, ctf_file_t **inputs, | |
2292 | uint32_t ninputs, uint32_t *parents, | |
2293 | int (*visit_fun) (const char *hval, | |
2294 | ctf_file_t *output, | |
2295 | ctf_file_t **inputs, | |
2296 | uint32_t ninputs, | |
2297 | uint32_t *parents, | |
2298 | int already_visited, | |
2299 | ctf_file_t *input, | |
2300 | ctf_id_t type, | |
2301 | void *id, | |
2302 | int depth, | |
2303 | void *arg), | |
2304 | void *arg) | |
2305 | { | |
2306 | ctf_dynset_t *already_visited; | |
2307 | ctf_next_t *i = NULL; | |
2308 | ctf_sort_om_cb_arg_t sort_arg; | |
2309 | int err; | |
2310 | void *k; | |
2311 | ||
2312 | if ((already_visited = ctf_dynset_create (htab_hash_string, | |
2313 | ctf_dynset_eq_string, | |
2314 | NULL)) == NULL) | |
2315 | return ctf_set_errno (output, ENOMEM); | |
2316 | ||
2317 | sort_arg.inputs = inputs; | |
2318 | sort_arg.ninputs = ninputs; | |
2319 | sort_arg.d = &output->ctf_dedup; | |
2320 | ||
2321 | while ((err = ctf_dynhash_next_sorted (output->ctf_dedup.cd_output_mapping, | |
2322 | &i, &k, NULL, sort_output_mapping, | |
2323 | &sort_arg)) == 0) | |
2324 | { | |
2325 | const char *hval = (const char *) k; | |
2326 | ||
2327 | err = ctf_dedup_rwalk_output_mapping (output, inputs, ninputs, parents, | |
2328 | already_visited, hval, visit_fun, | |
2329 | arg, 0); | |
2330 | if (err < 0) | |
2331 | { | |
2332 | ctf_next_destroy (i); | |
2333 | goto err; /* errno is set for us. */ | |
2334 | } | |
2335 | } | |
2336 | if (err != ECTF_NEXT_END) | |
2337 | { | |
926c9e76 | 2338 | ctf_err_warn (output, 0, err, _("cannot recurse over output mapping")); |
0f0c11f7 NA |
2339 | ctf_set_errno (output, err); |
2340 | goto err; | |
2341 | } | |
2342 | ctf_dynset_destroy (already_visited); | |
2343 | ||
2344 | return 0; | |
2345 | err: | |
2346 | ctf_dynset_destroy (already_visited); | |
2347 | return -1; | |
2348 | } | |
2349 | ||
2350 | /* Possibly synthesise a synthetic forward in TARGET to subsitute for a | |
2351 | conflicted per-TU type ID in INPUT with hash HVAL. Return its CTF ID, or 0 | |
2352 | if none was needed. */ | |
2353 | static ctf_id_t | |
2354 | ctf_dedup_maybe_synthesize_forward (ctf_file_t *output, ctf_file_t *target, | |
2355 | ctf_file_t *input, ctf_id_t id, | |
2356 | const char *hval) | |
2357 | { | |
2358 | ctf_dedup_t *od = &output->ctf_dedup; | |
2359 | ctf_dedup_t *td = &target->ctf_dedup; | |
2360 | int kind; | |
2361 | int fwdkind; | |
2362 | const char *name; | |
2363 | const char *decorated; | |
2364 | void *v; | |
2365 | ctf_id_t emitted_forward; | |
2366 | ||
2367 | if (!ctf_dynset_exists (od->cd_conflicting_types, hval, NULL) | |
2368 | || target->ctf_flags & LCTF_CHILD | |
2369 | || !ctf_type_name_raw (input, id) | |
2370 | || (((kind = ctf_type_kind_unsliced (input, id)) != CTF_K_STRUCT | |
2371 | && kind != CTF_K_UNION && kind != CTF_K_FORWARD))) | |
2372 | return 0; | |
2373 | ||
2374 | fwdkind = ctf_type_kind_forwarded (input, id); | |
2375 | name = ctf_type_name_raw (input, id); | |
2376 | ||
2377 | ctf_dprintf ("Using synthetic forward for conflicted struct/union with " | |
2378 | "hval %s\n", hval); | |
2379 | ||
2380 | if (!ctf_assert (output, name)) | |
2381 | return CTF_ERR; | |
2382 | ||
2383 | if ((decorated = ctf_decorate_type_name (output, name, fwdkind)) == NULL) | |
2384 | return CTF_ERR; | |
2385 | ||
2386 | if (!ctf_dynhash_lookup_kv (td->cd_output_emission_conflicted_forwards, | |
2387 | decorated, NULL, &v)) | |
2388 | { | |
2389 | if ((emitted_forward = ctf_add_forward (target, CTF_ADD_ROOT, name, | |
2390 | fwdkind)) == CTF_ERR) | |
2391 | { | |
2392 | ctf_set_errno (output, ctf_errno (target)); | |
2393 | return CTF_ERR; | |
2394 | } | |
2395 | ||
2396 | if (ctf_dynhash_cinsert (td->cd_output_emission_conflicted_forwards, | |
2397 | decorated, (void *) (uintptr_t) | |
2398 | emitted_forward) < 0) | |
2399 | { | |
2400 | ctf_set_errno (output, ENOMEM); | |
2401 | return CTF_ERR; | |
2402 | } | |
2403 | } | |
2404 | else | |
2405 | emitted_forward = (ctf_id_t) (uintptr_t) v; | |
2406 | ||
2407 | ctf_dprintf ("Cross-TU conflicted struct: passing back forward, %lx\n", | |
2408 | emitted_forward); | |
2409 | ||
2410 | return emitted_forward; | |
2411 | } | |
2412 | ||
2413 | /* Map a GID in some INPUT dict, in the form of an input number and a ctf_id_t, | |
2414 | into a GID in a target output dict. If it returns 0, this is the | |
2415 | unimplemented type, and the input type must have been 0. The OUTPUT dict is | |
2416 | assumed to be the parent of the TARGET, if it is not the TARGET itself. | |
2417 | ||
2418 | Returns CTF_ERR on failure. Responds to an incoming CTF_ERR as an 'id' by | |
2419 | returning CTF_ERR, to simplify callers. Errors are always propagated to the | |
2420 | input, even if they relate to the target, for the same reason. (Target | |
2421 | errors are expected to be very rare.) | |
2422 | ||
2423 | If the type in question is a citation of a conflicted type in a different TU, | |
2424 | emit a forward of the right type in its place (if not already emitted), and | |
2425 | record that forward in cd_output_emission_conflicted_forwards. This avoids | |
2426 | the need to replicate the entire type graph below this point in the current | |
2427 | TU (an appalling waste of space). | |
2428 | ||
2429 | TODO: maybe replace forwards in the same TU with their referents? Might | |
2430 | make usability a bit better. */ | |
2431 | ||
2432 | static ctf_id_t | |
2433 | ctf_dedup_id_to_target (ctf_file_t *output, ctf_file_t *target, | |
2434 | ctf_file_t **inputs, uint32_t ninputs, | |
2435 | uint32_t *parents, ctf_file_t *input, int input_num, | |
2436 | ctf_id_t id) | |
2437 | { | |
2438 | ctf_dedup_t *od = &output->ctf_dedup; | |
2439 | ctf_dedup_t *td = &target->ctf_dedup; | |
2440 | ctf_file_t *err_fp = input; | |
2441 | const char *hval; | |
2442 | void *target_id; | |
2443 | ctf_id_t emitted_forward; | |
2444 | ||
2445 | /* The target type of an error is an error. */ | |
2446 | if (id == CTF_ERR) | |
2447 | return CTF_ERR; | |
2448 | ||
2449 | /* The unimplemented type's ID never changes. */ | |
2450 | if (!id) | |
2451 | { | |
2452 | ctf_dprintf ("%i/%lx: unimplemented type\n", input_num, id); | |
2453 | return 0; | |
2454 | } | |
2455 | ||
2456 | ctf_dprintf ("Mapping %i/%lx to target %p (%s)\n", input_num, | |
2457 | id, (void *) target, ctf_link_input_name (target)); | |
2458 | ||
2459 | /* If the input type is in the parent type space, and this is a child, reset | |
2460 | the input to the parent (which must already have been emitted, since | |
2461 | emission of parent dicts happens before children). */ | |
2462 | if ((input->ctf_flags & LCTF_CHILD) && (LCTF_TYPE_ISPARENT (input, id))) | |
2463 | { | |
2464 | if (!ctf_assert (output, parents[input_num] <= ninputs)) | |
2465 | return -1; | |
2466 | input = inputs[parents[input_num]]; | |
2467 | input_num = parents[input_num]; | |
2468 | } | |
2469 | ||
2470 | hval = ctf_dynhash_lookup (od->cd_type_hashes, | |
2471 | CTF_DEDUP_GID (output, input_num, id)); | |
2472 | ||
2473 | if (!ctf_assert (output, hval && td->cd_output_emission_hashes)) | |
2474 | return -1; | |
2475 | ||
2476 | /* If this type is a conflicted tagged structure, union, or forward, | |
2477 | substitute a synthetic forward instead, emitting it if need be. Only do | |
2478 | this if the target is in the parent dict: if it's in the child dict, we can | |
2479 | just point straight at the thing itself. Of course, we might be looking in | |
2480 | the child dict right now and not find it and have to look in the parent, so | |
2481 | we have to do this check twice. */ | |
2482 | ||
2483 | emitted_forward = ctf_dedup_maybe_synthesize_forward (output, target, | |
2484 | input, id, hval); | |
2485 | switch (emitted_forward) | |
2486 | { | |
2487 | case 0: /* No forward needed. */ | |
2488 | break; | |
2489 | case -1: | |
2490 | ctf_set_errno (err_fp, ctf_errno (output)); | |
926c9e76 NA |
2491 | ctf_err_warn (err_fp, 0, 0, _("cannot add synthetic forward for type " |
2492 | "%i/%lx"), input_num, id); | |
0f0c11f7 NA |
2493 | return -1; |
2494 | default: | |
2495 | return emitted_forward; | |
2496 | } | |
2497 | ||
2498 | ctf_dprintf ("Looking up %i/%lx, hash %s, in target\n", input_num, id, hval); | |
2499 | ||
2500 | target_id = ctf_dynhash_lookup (td->cd_output_emission_hashes, hval); | |
2501 | if (!target_id) | |
2502 | { | |
2503 | /* Must be in the parent, so this must be a child, and they must not be | |
2504 | the same dict. */ | |
2505 | ctf_dprintf ("Checking shared parent for target\n"); | |
2506 | if (!ctf_assert (output, (target != output) | |
2507 | && (target->ctf_flags & LCTF_CHILD))) | |
2508 | return -1; | |
2509 | ||
2510 | target_id = ctf_dynhash_lookup (od->cd_output_emission_hashes, hval); | |
2511 | ||
2512 | emitted_forward = ctf_dedup_maybe_synthesize_forward (output, output, | |
2513 | input, id, hval); | |
2514 | switch (emitted_forward) | |
2515 | { | |
2516 | case 0: /* No forward needed. */ | |
2517 | break; | |
2518 | case -1: | |
926c9e76 NA |
2519 | ctf_err_warn (err_fp, 0, ctf_errno (output), |
2520 | _("cannot add synthetic forward for type %i/%lx"), | |
2521 | input_num, id); | |
2522 | return ctf_set_errno (err_fp, ctf_errno (output)); | |
0f0c11f7 NA |
2523 | default: |
2524 | return emitted_forward; | |
2525 | } | |
2526 | } | |
2527 | if (!ctf_assert (output, target_id)) | |
2528 | return -1; | |
2529 | return (ctf_id_t) (uintptr_t) target_id; | |
2530 | } | |
2531 | ||
2532 | /* Emit a single deduplicated TYPE with the given HVAL, located in a given | |
2533 | INPUT, with the given (G)ID, into the shared OUTPUT or a | |
2534 | possibly-newly-created per-CU dict. All the types this type depends upon | |
2535 | have already been emitted. (This type itself may also have been emitted.) | |
2536 | ||
2537 | If the ARG is 1, this is a CU-mapped deduplication round mapping many | |
2538 | ctf_file_t's into precisely one: conflicting types should be marked | |
2539 | non-root-visible. If the ARG is 0, conflicting types go into per-CU | |
2540 | dictionaries stored in the input's ctf_dedup.cd_output: otherwise, everything | |
2541 | is emitted directly into the output. No struct/union members are emitted. | |
2542 | ||
2543 | Optimization opportunity: trace the ancestry of non-root-visible types and | |
2544 | elide all that neither have a root-visible type somewhere towards their root, | |
2545 | nor have the type visible via any other route (the function info section, | |
2546 | data object section, backtrace section etc). */ | |
2547 | ||
2548 | static int | |
2549 | ctf_dedup_emit_type (const char *hval, ctf_file_t *output, ctf_file_t **inputs, | |
2550 | uint32_t ninputs, uint32_t *parents, int already_visited, | |
2551 | ctf_file_t *input, ctf_id_t type, void *id, int depth, | |
2552 | void *arg) | |
2553 | { | |
2554 | ctf_dedup_t *d = &output->ctf_dedup; | |
2555 | int kind = ctf_type_kind_unsliced (input, type); | |
2556 | const char *name; | |
2557 | ctf_file_t *target = output; | |
2558 | ctf_file_t *real_input; | |
2559 | const ctf_type_t *tp; | |
2560 | int input_num = CTF_DEDUP_GID_TO_INPUT (id); | |
2561 | int output_num = (uint32_t) -1; /* 'shared' */ | |
2562 | int cu_mapped = *(int *)arg; | |
2563 | int isroot = 1; | |
2564 | int is_conflicting; | |
2565 | ||
2566 | ctf_next_t *i = NULL; | |
2567 | ctf_id_t new_type; | |
2568 | ctf_id_t ref; | |
2569 | ctf_id_t maybe_dup = 0; | |
2570 | ctf_encoding_t ep; | |
926c9e76 | 2571 | const char *errtype; |
0f0c11f7 NA |
2572 | int emission_hashed = 0; |
2573 | ||
2574 | /* We don't want to re-emit something we've already emitted. */ | |
2575 | ||
2576 | if (already_visited) | |
2577 | return 0; | |
2578 | ||
2579 | ctf_dprintf ("%i: Emitting type with hash %s from %s: determining target\n", | |
2580 | depth, hval, ctf_link_input_name (input)); | |
2581 | ||
2582 | /* Conflicting types go into a per-CU output dictionary, unless this is a | |
2583 | CU-mapped run. The import is not refcounted, since it goes into the | |
2584 | ctf_link_outputs dict of the output that is its parent. */ | |
2585 | is_conflicting = ctf_dynset_exists (d->cd_conflicting_types, hval, NULL); | |
2586 | ||
2587 | if (is_conflicting && !cu_mapped) | |
2588 | { | |
2589 | ctf_dprintf ("%i: Type %s in %i/%lx is conflicted: " | |
2590 | "inserting into per-CU target.\n", | |
2591 | depth, hval, input_num, type); | |
2592 | ||
2593 | if (input->ctf_dedup.cd_output) | |
2594 | target = input->ctf_dedup.cd_output; | |
2595 | else | |
2596 | { | |
2597 | int err; | |
2598 | ||
2599 | if ((target = ctf_create (&err)) == NULL) | |
2600 | { | |
926c9e76 NA |
2601 | ctf_err_warn (output, 0, err, |
2602 | _("cannot create per-CU CTF archive for CU %s"), | |
2603 | ctf_link_input_name (input)); | |
2604 | return ctf_set_errno (output, err); | |
0f0c11f7 NA |
2605 | } |
2606 | ||
2607 | ctf_import_unref (target, output); | |
2608 | if (ctf_cuname (input) != NULL) | |
2609 | ctf_cuname_set (target, ctf_cuname (input)); | |
2610 | else | |
2611 | ctf_cuname_set (target, "unnamed-CU"); | |
2612 | ctf_parent_name_set (target, _CTF_SECTION); | |
2613 | ||
2614 | input->ctf_dedup.cd_output = target; | |
2615 | } | |
2616 | output_num = input_num; | |
2617 | } | |
2618 | ||
2619 | real_input = input; | |
2620 | if ((tp = ctf_lookup_by_id (&real_input, type)) == NULL) | |
2621 | { | |
926c9e76 NA |
2622 | ctf_err_warn (output, 0, ctf_errno (input), |
2623 | _("%s: lookup failure for type %lx"), | |
2624 | ctf_link_input_name (real_input), type); | |
2625 | return ctf_set_errno (output, ctf_errno (input)); | |
0f0c11f7 NA |
2626 | } |
2627 | ||
2628 | name = ctf_strraw (real_input, tp->ctt_name); | |
2629 | ||
2630 | /* Hide conflicting types, if we were asked to: also hide if a type with this | |
2631 | name already exists and is not a forward. */ | |
2632 | if (cu_mapped && is_conflicting) | |
2633 | isroot = 0; | |
2634 | else if (name | |
2635 | && (maybe_dup = ctf_lookup_by_rawname (target, kind, name)) != 0) | |
2636 | { | |
2637 | if (ctf_type_kind (target, maybe_dup) != CTF_K_FORWARD) | |
2638 | isroot = 0; | |
2639 | } | |
2640 | ||
2641 | ctf_dprintf ("%i: Emitting type with hash %s (%s), into target %i/%p\n", | |
2642 | depth, hval, name ? name : "", input_num, (void *) target); | |
2643 | ||
2644 | if (!target->ctf_dedup.cd_output_emission_hashes) | |
2645 | if ((target->ctf_dedup.cd_output_emission_hashes | |
2646 | = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string, | |
2647 | NULL, NULL)) == NULL) | |
2648 | goto oom_hash; | |
2649 | ||
2650 | if (!target->ctf_dedup.cd_output_emission_conflicted_forwards) | |
2651 | if ((target->ctf_dedup.cd_output_emission_conflicted_forwards | |
2652 | = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string, | |
2653 | NULL, NULL)) == NULL) | |
2654 | goto oom_hash; | |
2655 | ||
2656 | switch (kind) | |
2657 | { | |
2658 | case CTF_K_UNKNOWN: | |
2659 | /* These are types that CTF cannot encode, marked as such by the compile. | |
2660 | We intentionally do not re-emit these. */ | |
2661 | new_type = 0; | |
2662 | break; | |
2663 | case CTF_K_FORWARD: | |
2664 | /* This will do nothing if the type to which this forwards already exists, | |
2665 | and will be replaced with such a type if it appears later. */ | |
2666 | ||
926c9e76 | 2667 | errtype = _("forward"); |
0f0c11f7 NA |
2668 | if ((new_type = ctf_add_forward (target, isroot, name, |
2669 | ctf_type_kind_forwarded (input, type))) | |
2670 | == CTF_ERR) | |
2671 | goto err_target; | |
2672 | break; | |
2673 | ||
2674 | case CTF_K_FLOAT: | |
2675 | case CTF_K_INTEGER: | |
926c9e76 | 2676 | errtype = _("float/int"); |
0f0c11f7 NA |
2677 | if (ctf_type_encoding (input, type, &ep) < 0) |
2678 | goto err_input; /* errno is set for us. */ | |
2679 | if ((new_type = ctf_add_encoded (target, isroot, name, &ep, kind)) | |
2680 | == CTF_ERR) | |
2681 | goto err_target; | |
2682 | break; | |
2683 | ||
2684 | case CTF_K_ENUM: | |
2685 | { | |
2686 | int val; | |
926c9e76 | 2687 | errtype = _("enum"); |
0f0c11f7 NA |
2688 | if ((new_type = ctf_add_enum (target, isroot, name)) == CTF_ERR) |
2689 | goto err_input; /* errno is set for us. */ | |
2690 | ||
2691 | while ((name = ctf_enum_next (input, type, &i, &val)) != NULL) | |
2692 | { | |
2693 | if (ctf_add_enumerator (target, new_type, name, val) < 0) | |
2694 | { | |
926c9e76 NA |
2695 | ctf_err_warn (target, 0, ctf_errno (target), |
2696 | _("%s (%i): cannot add enumeration value %s " | |
2697 | "from input type %lx"), | |
0f0c11f7 | 2698 | ctf_link_input_name (input), input_num, name, |
926c9e76 | 2699 | type); |
0f0c11f7 NA |
2700 | ctf_next_destroy (i); |
2701 | return ctf_set_errno (output, ctf_errno (target)); | |
2702 | } | |
2703 | } | |
2704 | if (ctf_errno (input) != ECTF_NEXT_END) | |
2705 | goto err_input; | |
2706 | break; | |
2707 | } | |
2708 | ||
2709 | case CTF_K_TYPEDEF: | |
926c9e76 | 2710 | errtype = _("typedef"); |
0f0c11f7 NA |
2711 | |
2712 | ref = ctf_type_reference (input, type); | |
2713 | if ((ref = ctf_dedup_id_to_target (output, target, inputs, ninputs, | |
2714 | parents, input, input_num, | |
2715 | ref)) == CTF_ERR) | |
2716 | goto err_input; /* errno is set for us. */ | |
2717 | ||
2718 | if ((new_type = ctf_add_typedef (target, isroot, name, ref)) == CTF_ERR) | |
2719 | goto err_target; /* errno is set for us. */ | |
2720 | break; | |
2721 | ||
2722 | case CTF_K_VOLATILE: | |
2723 | case CTF_K_CONST: | |
2724 | case CTF_K_RESTRICT: | |
2725 | case CTF_K_POINTER: | |
926c9e76 | 2726 | errtype = _("pointer or cvr-qual"); |
0f0c11f7 NA |
2727 | |
2728 | ref = ctf_type_reference (input, type); | |
2729 | if ((ref = ctf_dedup_id_to_target (output, target, inputs, ninputs, | |
2730 | parents, input, input_num, | |
2731 | ref)) == CTF_ERR) | |
2732 | goto err_input; /* errno is set for us. */ | |
2733 | ||
2734 | if ((new_type = ctf_add_reftype (target, isroot, ref, kind)) == CTF_ERR) | |
2735 | goto err_target; /* errno is set for us. */ | |
2736 | break; | |
2737 | ||
2738 | case CTF_K_SLICE: | |
926c9e76 | 2739 | errtype = _("slice"); |
0f0c11f7 NA |
2740 | |
2741 | if (ctf_type_encoding (input, type, &ep) < 0) | |
2742 | goto err_input; /* errno is set for us. */ | |
2743 | ||
2744 | ref = ctf_type_reference (input, type); | |
2745 | if ((ref = ctf_dedup_id_to_target (output, target, inputs, ninputs, | |
2746 | parents, input, input_num, | |
2747 | ref)) == CTF_ERR) | |
2748 | goto err_input; | |
2749 | ||
2750 | if ((new_type = ctf_add_slice (target, isroot, ref, &ep)) == CTF_ERR) | |
2751 | goto err_target; | |
2752 | break; | |
2753 | ||
2754 | case CTF_K_ARRAY: | |
2755 | { | |
2756 | ctf_arinfo_t ar; | |
2757 | ||
926c9e76 | 2758 | errtype = _("array info"); |
0f0c11f7 NA |
2759 | if (ctf_array_info (input, type, &ar) < 0) |
2760 | goto err_input; | |
2761 | ||
2762 | ar.ctr_contents = ctf_dedup_id_to_target (output, target, inputs, | |
2763 | ninputs, parents, input, | |
2764 | input_num, ar.ctr_contents); | |
2765 | ar.ctr_index = ctf_dedup_id_to_target (output, target, inputs, ninputs, | |
2766 | parents, input, input_num, | |
2767 | ar.ctr_index); | |
2768 | ||
2769 | if (ar.ctr_contents == CTF_ERR || ar.ctr_index == CTF_ERR) | |
2770 | goto err_input; | |
2771 | ||
2772 | if ((new_type = ctf_add_array (target, isroot, &ar)) == CTF_ERR) | |
2773 | goto err_target; | |
2774 | ||
2775 | break; | |
2776 | } | |
2777 | ||
2778 | case CTF_K_FUNCTION: | |
2779 | { | |
2780 | ctf_funcinfo_t fi; | |
2781 | ctf_id_t *args; | |
2782 | uint32_t j; | |
2783 | ||
926c9e76 | 2784 | errtype = _("function"); |
0f0c11f7 NA |
2785 | if (ctf_func_type_info (input, type, &fi) < 0) |
2786 | goto err_input; | |
2787 | ||
2788 | fi.ctc_return = ctf_dedup_id_to_target (output, target, inputs, ninputs, | |
2789 | parents, input, input_num, | |
2790 | fi.ctc_return); | |
2791 | if (fi.ctc_return == CTF_ERR) | |
2792 | goto err_input; | |
2793 | ||
2794 | if ((args = calloc (fi.ctc_argc, sizeof (ctf_id_t))) == NULL) | |
2795 | { | |
2796 | ctf_set_errno (input, ENOMEM); | |
2797 | goto err_input; | |
2798 | } | |
2799 | ||
926c9e76 | 2800 | errtype = _("function args"); |
0f0c11f7 NA |
2801 | if (ctf_func_type_args (input, type, fi.ctc_argc, args) < 0) |
2802 | { | |
2803 | free (args); | |
2804 | goto err_input; | |
2805 | } | |
2806 | ||
2807 | for (j = 0; j < fi.ctc_argc; j++) | |
2808 | { | |
2809 | args[j] = ctf_dedup_id_to_target (output, target, inputs, ninputs, | |
2810 | parents, input, input_num, | |
2811 | args[j]); | |
2812 | if (args[j] == CTF_ERR) | |
2813 | goto err_input; | |
2814 | } | |
2815 | ||
2816 | if ((new_type = ctf_add_function (target, isroot, | |
2817 | &fi, args)) == CTF_ERR) | |
2818 | { | |
2819 | free (args); | |
2820 | goto err_target; | |
2821 | } | |
2822 | free (args); | |
2823 | break; | |
2824 | } | |
2825 | ||
2826 | case CTF_K_STRUCT: | |
2827 | case CTF_K_UNION: | |
2828 | { | |
2829 | size_t size = ctf_type_size (input, type); | |
2830 | void *out_id; | |
2831 | /* Insert the structure itself, so other types can refer to it. */ | |
2832 | ||
926c9e76 | 2833 | errtype = _("structure/union"); |
0f0c11f7 NA |
2834 | if (kind == CTF_K_STRUCT) |
2835 | new_type = ctf_add_struct_sized (target, isroot, name, size); | |
2836 | else | |
2837 | new_type = ctf_add_union_sized (target, isroot, name, size); | |
2838 | ||
2839 | if (new_type == CTF_ERR) | |
2840 | goto err_target; | |
2841 | ||
2842 | out_id = CTF_DEDUP_GID (output, output_num, new_type); | |
2843 | ctf_dprintf ("%i: Noting need to emit members of %p -> %p\n", depth, | |
2844 | id, out_id); | |
2845 | /* Record the need to emit the members of this structure later. */ | |
2846 | if (ctf_dynhash_insert (d->cd_emission_struct_members, id, out_id) < 0) | |
2847 | goto err_target; | |
2848 | break; | |
2849 | } | |
2850 | default: | |
926c9e76 NA |
2851 | ctf_err_warn (output, 0, ECTF_CORRUPT, _("%s: unknown type kind for " |
2852 | "input type %lx"), | |
0f0c11f7 | 2853 | ctf_link_input_name (input), type); |
926c9e76 | 2854 | return ctf_set_errno (output, ECTF_CORRUPT); |
0f0c11f7 NA |
2855 | } |
2856 | ||
2857 | if (!emission_hashed | |
2858 | && new_type != 0 | |
2859 | && ctf_dynhash_cinsert (target->ctf_dedup.cd_output_emission_hashes, | |
2860 | hval, (void *) (uintptr_t) new_type) < 0) | |
2861 | { | |
926c9e76 NA |
2862 | ctf_err_warn (output, 0, ENOMEM, _("out of memory tracking deduplicated " |
2863 | "global type IDs")); | |
0f0c11f7 NA |
2864 | return ctf_set_errno (output, ENOMEM); |
2865 | } | |
2866 | ||
2867 | if (!emission_hashed && new_type != 0) | |
2868 | ctf_dprintf ("%i: Inserted %s, %i/%lx -> %lx into emission hash for " | |
2869 | "target %p (%s)\n", depth, hval, input_num, type, new_type, | |
2870 | (void *) target, ctf_link_input_name (target)); | |
2871 | ||
2872 | return 0; | |
2873 | ||
2874 | oom_hash: | |
926c9e76 NA |
2875 | ctf_err_warn (output, 0, ENOMEM, _("out of memory creating emission-tracking " |
2876 | "hashes")); | |
0f0c11f7 NA |
2877 | return ctf_set_errno (output, ENOMEM); |
2878 | ||
2879 | err_input: | |
926c9e76 NA |
2880 | ctf_err_warn (output, 0, ctf_errno (input), |
2881 | _("%s (%i): while emitting deduplicated %s, error getting " | |
2882 | "input type %lx"), ctf_link_input_name (input), | |
2883 | input_num, errtype, type); | |
2884 | return ctf_set_errno (output, ctf_errno (input)); | |
0f0c11f7 | 2885 | err_target: |
926c9e76 NA |
2886 | ctf_err_warn (output, 0, ctf_errno (target), |
2887 | _("%s (%i): while emitting deduplicated %s, error emitting " | |
2888 | "target type from input type %lx"), | |
2889 | ctf_link_input_name (input), input_num, | |
2890 | errtype, type); | |
2891 | return ctf_set_errno (output, ctf_errno (target)); | |
0f0c11f7 NA |
2892 | } |
2893 | ||
2894 | /* Traverse the cd_emission_struct_members and emit the members of all | |
2895 | structures and unions. All other types are emitted and complete by this | |
2896 | point. */ | |
2897 | ||
2898 | static int | |
2899 | ctf_dedup_emit_struct_members (ctf_file_t *output, ctf_file_t **inputs, | |
2900 | uint32_t ninputs, uint32_t *parents) | |
2901 | { | |
2902 | ctf_dedup_t *d = &output->ctf_dedup; | |
2903 | ctf_next_t *i = NULL; | |
2904 | void *input_id, *target_id; | |
2905 | int err; | |
2906 | ctf_file_t *err_fp, *input_fp; | |
2907 | int input_num; | |
2908 | ctf_id_t err_type; | |
2909 | ||
2910 | while ((err = ctf_dynhash_next (d->cd_emission_struct_members, &i, | |
2911 | &input_id, &target_id)) == 0) | |
2912 | { | |
2913 | ctf_next_t *j = NULL; | |
2914 | ctf_file_t *target; | |
2915 | uint32_t target_num; | |
2916 | ctf_id_t input_type, target_type; | |
2917 | ssize_t offset; | |
2918 | ctf_id_t membtype; | |
2919 | const char *name; | |
2920 | ||
2921 | input_num = CTF_DEDUP_GID_TO_INPUT (input_id); | |
2922 | input_fp = inputs[input_num]; | |
2923 | input_type = CTF_DEDUP_GID_TO_TYPE (input_id); | |
2924 | ||
2925 | /* The output is either -1 (for the shared, parent output dict) or the | |
2926 | number of the corresponding input. */ | |
2927 | target_num = CTF_DEDUP_GID_TO_INPUT (target_id); | |
2928 | if (target_num == (uint32_t) -1) | |
2929 | target = output; | |
2930 | else | |
2931 | { | |
2932 | target = inputs[target_num]->ctf_dedup.cd_output; | |
2933 | if (!ctf_assert (output, target)) | |
2934 | { | |
2935 | err_fp = output; | |
2936 | err_type = input_type; | |
2937 | goto err_target; | |
2938 | } | |
2939 | } | |
2940 | target_type = CTF_DEDUP_GID_TO_TYPE (target_id); | |
2941 | ||
2942 | while ((offset = ctf_member_next (input_fp, input_type, &j, &name, | |
2943 | &membtype)) >= 0) | |
2944 | { | |
2945 | err_fp = target; | |
2946 | err_type = target_type; | |
2947 | if ((membtype = ctf_dedup_id_to_target (output, target, inputs, | |
2948 | ninputs, parents, input_fp, | |
2949 | input_num, | |
2950 | membtype)) == CTF_ERR) | |
2951 | { | |
2952 | ctf_next_destroy (j); | |
2953 | goto err_target; | |
2954 | } | |
2955 | ||
2956 | if (name == NULL) | |
2957 | name = ""; | |
2958 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
2959 | ctf_dprintf ("Emitting %s, offset %zi\n", name, offset); | |
2960 | #endif | |
2961 | if (ctf_add_member_offset (target, target_type, name, | |
2962 | membtype, offset) < 0) | |
2963 | { | |
2964 | ctf_next_destroy (j); | |
2965 | goto err_target; | |
2966 | } | |
2967 | } | |
2968 | if (ctf_errno (input_fp) != ECTF_NEXT_END) | |
2969 | { | |
2970 | err = ctf_errno (input_fp); | |
2971 | ctf_next_destroy (i); | |
2972 | goto iterr; | |
2973 | } | |
2974 | } | |
2975 | if (err != ECTF_NEXT_END) | |
2976 | goto iterr; | |
2977 | ||
2978 | return 0; | |
2979 | err_target: | |
2980 | ctf_next_destroy (i); | |
926c9e76 NA |
2981 | ctf_err_warn (output, 0, ctf_errno (err_fp), |
2982 | _("%s (%i): error emitting members for structure type %lx"), | |
2983 | ctf_link_input_name (input_fp), input_num, err_type); | |
2984 | return ctf_set_errno (output, ctf_errno (err_fp)); | |
0f0c11f7 | 2985 | iterr: |
926c9e76 NA |
2986 | ctf_err_warn (output, 0, err, _("iteration failure emitting " |
2987 | "structure members")); | |
2988 | return ctf_set_errno (output, err); | |
0f0c11f7 NA |
2989 | } |
2990 | ||
2991 | /* Populate the type mapping used by the types in one FP (which must be an input | |
2992 | dict containing a non-null cd_output resulting from a ctf_dedup_emit_type | |
2993 | walk). */ | |
2994 | static int | |
2995 | ctf_dedup_populate_type_mapping (ctf_file_t *shared, ctf_file_t *fp, | |
2996 | ctf_file_t **inputs) | |
2997 | { | |
2998 | ctf_dedup_t *d = &shared->ctf_dedup; | |
2999 | ctf_file_t *output = fp->ctf_dedup.cd_output; | |
3000 | const void *k, *v; | |
3001 | ctf_next_t *i = NULL; | |
3002 | int err; | |
3003 | ||
3004 | /* The shared dict (the output) stores its types in the fp itself, not in a | |
3005 | separate cd_output dict. */ | |
3006 | if (shared == fp) | |
3007 | output = fp; | |
3008 | ||
3009 | /* There may be no types to emit at all, or all the types in this TU may be | |
3010 | shared. */ | |
3011 | if (!output || !output->ctf_dedup.cd_output_emission_hashes) | |
3012 | return 0; | |
3013 | ||
3014 | while ((err = ctf_dynhash_cnext (output->ctf_dedup.cd_output_emission_hashes, | |
3015 | &i, &k, &v)) == 0) | |
3016 | { | |
3017 | const char *hval = (const char *) k; | |
3018 | ctf_id_t id_out = (ctf_id_t) (uintptr_t) v; | |
3019 | ctf_next_t *j = NULL; | |
3020 | ctf_dynset_t *type_ids; | |
3021 | const void *id; | |
3022 | ||
3023 | type_ids = ctf_dynhash_lookup (d->cd_output_mapping, hval); | |
3024 | if (!ctf_assert (shared, type_ids)) | |
3025 | return -1; | |
3026 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
3027 | ctf_dprintf ("Traversing emission hash: hval %s\n", hval); | |
3028 | #endif | |
3029 | ||
3030 | while ((err = ctf_dynset_cnext (type_ids, &j, &id)) == 0) | |
3031 | { | |
3032 | ctf_file_t *input = inputs[CTF_DEDUP_GID_TO_INPUT (id)]; | |
3033 | ctf_id_t id_in = CTF_DEDUP_GID_TO_TYPE (id); | |
3034 | ||
3035 | #ifdef ENABLE_LIBCTF_HASH_DEBUGGING | |
3036 | ctf_dprintf ("Adding mapping from %i/%lx to %lx\n", | |
3037 | CTF_DEDUP_GID_TO_INPUT (id), id_in, id_out); | |
3038 | #endif | |
3039 | ctf_add_type_mapping (input, id_in, output, id_out); | |
3040 | } | |
3041 | if (err != ECTF_NEXT_END) | |
3042 | { | |
3043 | ctf_next_destroy (i); | |
3044 | goto err; | |
3045 | } | |
3046 | } | |
3047 | if (err != ECTF_NEXT_END) | |
3048 | goto err; | |
3049 | ||
3050 | return 0; | |
3051 | ||
3052 | err: | |
926c9e76 | 3053 | ctf_err_warn (shared, 0, err, _("iteration error populating the type mapping")); |
0f0c11f7 NA |
3054 | return ctf_set_errno (shared, err); |
3055 | } | |
3056 | ||
3057 | /* Populate the type mapping machinery used by the rest of the linker, | |
3058 | by ctf_add_type, etc. */ | |
3059 | static int | |
3060 | ctf_dedup_populate_type_mappings (ctf_file_t *output, ctf_file_t **inputs, | |
3061 | uint32_t ninputs) | |
3062 | { | |
3063 | size_t i; | |
3064 | ||
3065 | if (ctf_dedup_populate_type_mapping (output, output, inputs) < 0) | |
3066 | { | |
926c9e76 NA |
3067 | ctf_err_warn (output, 0, 0, _("cannot populate type mappings for shared " |
3068 | "CTF dict")); | |
0f0c11f7 NA |
3069 | return -1; /* errno is set for us. */ |
3070 | } | |
3071 | ||
3072 | for (i = 0; i < ninputs; i++) | |
3073 | { | |
3074 | if (ctf_dedup_populate_type_mapping (output, inputs[i], inputs) < 0) | |
3075 | { | |
926c9e76 NA |
3076 | ctf_err_warn (output, 0, ctf_errno (inputs[i]), |
3077 | _("cannot populate type mappings for per-CU CTF dict")); | |
0f0c11f7 NA |
3078 | return ctf_set_errno (output, ctf_errno (inputs[i])); |
3079 | } | |
3080 | } | |
3081 | ||
3082 | return 0; | |
3083 | } | |
3084 | ||
3085 | /* Emit deduplicated types into the outputs. The shared type repository is | |
3086 | OUTPUT, on which the ctf_dedup function must have already been called. The | |
3087 | PARENTS array contains the INPUTS index of the parent dict for every child | |
3088 | dict at the corresponding index in the INPUTS (for non-child dicts, the value | |
3089 | is undefined). | |
3090 | ||
3091 | Return an array of fps with content emitted into them (starting with OUTPUT, | |
3092 | which is the parent of all others, then all the newly-generated outputs). | |
3093 | ||
3094 | If CU_MAPPED is set, this is a first pass for a link with a non-empty CU | |
3095 | mapping: only one output will result. */ | |
3096 | ||
3097 | ctf_file_t ** | |
3098 | ctf_dedup_emit (ctf_file_t *output, ctf_file_t **inputs, uint32_t ninputs, | |
3099 | uint32_t *parents, uint32_t *noutputs, int cu_mapped) | |
3100 | { | |
3101 | size_t num_outputs = 1; /* Always at least one output: us. */ | |
3102 | ctf_file_t **outputs; | |
3103 | ctf_file_t **walk; | |
3104 | size_t i; | |
3105 | ||
3106 | ctf_dprintf ("Triggering emission.\n"); | |
3107 | if (ctf_dedup_walk_output_mapping (output, inputs, ninputs, parents, | |
3108 | ctf_dedup_emit_type, &cu_mapped) < 0) | |
3109 | return NULL; /* errno is set for us. */ | |
3110 | ||
3111 | ctf_dprintf ("Populating struct members.\n"); | |
3112 | if (ctf_dedup_emit_struct_members (output, inputs, ninputs, parents) < 0) | |
3113 | return NULL; /* errno is set for us. */ | |
3114 | ||
3115 | if (ctf_dedup_populate_type_mappings (output, inputs, ninputs) < 0) | |
3116 | return NULL; /* errno is set for us. */ | |
3117 | ||
3118 | for (i = 0; i < ninputs; i++) | |
3119 | { | |
3120 | if (inputs[i]->ctf_dedup.cd_output) | |
3121 | num_outputs++; | |
3122 | } | |
3123 | ||
3124 | if (!ctf_assert (output, !cu_mapped || (cu_mapped && num_outputs == 1))) | |
3125 | return NULL; | |
3126 | ||
3127 | if ((outputs = calloc (num_outputs, sizeof (ctf_file_t *))) == NULL) | |
3128 | { | |
926c9e76 NA |
3129 | ctf_err_warn (output, 0, ENOMEM, |
3130 | _("out of memory allocating link outputs array")); | |
0f0c11f7 NA |
3131 | ctf_set_errno (output, ENOMEM); |
3132 | return NULL; | |
3133 | } | |
3134 | *noutputs = num_outputs; | |
3135 | ||
3136 | walk = outputs; | |
3137 | *walk = output; | |
3138 | output->ctf_refcnt++; | |
3139 | walk++; | |
3140 | ||
3141 | for (i = 0; i < ninputs; i++) | |
3142 | { | |
3143 | if (inputs[i]->ctf_dedup.cd_output) | |
3144 | { | |
3145 | *walk = inputs[i]->ctf_dedup.cd_output; | |
3146 | inputs[i]->ctf_dedup.cd_output = NULL; | |
3147 | walk++; | |
3148 | } | |
3149 | } | |
3150 | ||
3151 | ctf_dedup_fini (output, outputs, num_outputs); | |
3152 | return outputs; | |
3153 | } |