elfutils-devel September 2010

elfutils-devel@lists.fedorahosted.org

34 participants
37 discussions

dwarf_output overview
by Roland McGrath 05 Jan '11

05 Jan '11

https://fedorahosted.org/elfutils/wiki/DwarfOutput is still accurate in its basic description about the collector (class dwarf_output_collector). We don't really need to get into right now why it's a separate object from dwarf_output. For uses in the time being, we'll use one collector with one dwarf_output for one input file. The simple attribute values, and some bits of interface glue, are shared via template use from dwarf_data, with dwarf_edit. The only difference is that in dwarf_output we never have mutable versions of thse objects, only const pointers/references to immutable copies sitting in the collector. Whereas dwarf_edit has mutable containers, there is no modification you can do to a dwarf_output object once it's created. Instead, like dwarf_edit you can copy-construct a dwarf_output object from any dwarf-compatible class (i.e. dwarf, dwarf_edit, or dwarf_output)--this is the only way to get a nonempty dwarf_output object. The dwarf_output constructor takes two arguments, unlike the simple dwarf_edit constructor. The second argument is the collector object. This actually uses a second helper object, whose only purpose is to live as long as copy construction is going on. That's dwarf_output::copier, which is actually dwarf_output::copier<input> parameterized by the particular top-level input type (dwarf or dwarf_edit). (This will one day be exposed outside dwarf_output for some of the same cases where a separate collector is really useful, but we won't get into that now.) The copy construction is doing the whole file, or at least a whole CU, from the root of the tree down to the leaves and all attribute values. The copier holds some bookkeeping and some caches during that process. The essential method is that the tree from the CU on down has its debug_info_entry objects constructed recursively, with debug_info_entry::attr_value objects being constructed for each node. Each attr_value on up to each debug_info_entry is "constructed" by finding its exact match stored in the collector, inserting it only if it's not already there, and then returning the pointer (i.e. actually all C++ references) to the (now) existing data structure. The copier's part in this is twofold. First, there is some simple caching related to copying the simple attribute values. (All the value types other than references are "simple".) Second, there is all the hairy bookkeeping for the complexity brought on by references. The copier's caching is a simple optimization, so I'll describe it first. This is for strings, identifier strings (which we distinguish from other strings, though they are just strings in DWARF), and source files. In one input file, even across many CUs (because of linker SHF_MERGE|SHF_STRINGS merging), every DW_AT_name "foobar" will point to point to the same "foobar" in the .debug_str table. Likewise, a dwarf::source_file object that represents a source file from the .debug_line table is what we get for every DW_AT_decl_file attribute on the input tree, but there will be many DIEs with that attribute pointing to the same file entry (same index into the CU's .debug_ling table, so getting the same dwarf::source_file again and again). Hence, we expect to see the actual same pointer (in a dwarf reader object, really the same pointer into the mmapped DWARF file data) appearing many times in the input tree's attr_values. Matching pointers you've seen before is quicker than matching string values you've seen before. So the copier keeps maps keyed by these string (and file entry) pointers into the input data, to find exact attr_value's already found/created to match other instances of the same input string (or file entry). (This sped things up a fair bit when I added it, though I don't recall the details.) For all the simple attribute values the method is simple. For each flavor of attr_value, the collector holds a set of values seen before. The subr::value_set container type is used for this. It's based on the STL unordered_set, which is a hash table where we supply the key type and the hash and comparison functions on that type. In these sets, our key types are dwarf_output::value::value_*, which are the flavor-specific subtypes that an attr_value actually points to. So, each of those types has to provide an integer hash function (a "hasher" inner class) and a comparison function (operator==). The copier does a set insertion of the input value object, which installs a new dwarf_output::value::value_foobar object if none matched, or doesn't if one did, and then produces an attr_value that points to that. Note that since this is the only way any dwarf_output::attr_value objects can ever get created, within one dwarf_output object (really, one collector), simple pointer equality is exactly correct as a semantic equality check for the non-reference attribute values. A corollary is that just this pointer value itself can be used as the hash value for the attr_value object (a perfect hash function). If there are no reference attributes to consider, then it proceeds from the bottom up in the same straightforward way. That is, the entire map of attributes (considered as a sequence of <int name, attr_value> pairs in a canonical name-keyed order) can be hashed together to get a hash value for the attributes container. Then a leaf node can combine the tag into the that hash value to get a hash value for the whole DIE. Then, a sequence of sibling leaf nodes' hash values are combined to form a hash value for the whole children container. Then that hash value is combined with the tag and the attribute map hash value to form a hash value for the whole DIE. Then on up. So this is what we do. The simple attribute values are hashed on the actual values (string data, integer values, etc.), and then those pointer values along with the attribute name (integers) in a canonical order are combined with the DIE tag into a single integer hash. The _m_attr_sets set (i.e. hash table) holds these <attribute map, tag integer> pairs. Then children vectors, starting with the empty vector for leaf DIEs, are hashed into the _m_broods set. (The empty vector has hash value zero.) Finally, a dwarf_output::debug_info_entry just consists of pointers to the attributes map and children vector, and the DIE tag integer. We just combine those two pointer values and the tag to make the integer hash of the debug_info_entry object itself. _m_unique holds the set of unique debug_info_entry objects. So, a leaf DIE gets created with an attributes map pointer and a pointer to the one and only empty children vector object. Then a non-empty children vector is simply a vector of pointers to debug_info_entry objects like that one. Like for the other sets, a pointer to a particular debug_info_entry in the collector serves as a perfect integer hash, since by definition pointer equality of the debug_info_entry object exactly maps to semantic equivalence. So, the children vector is a simple container of pointers, and the vector itself has a hash value made just by combining the pointer values as so many constituent integer hash values. So, it's like that when no attribute values are references. The exact control flow between the constructors of the dwarf_output inner classes and dwarf_output::copier is extremely hairy. But the extreme template weirdness is mostly just to get the copier pointer passed down the levels of constructors to where it calls an add_* method on the copier. It's there, and the collector methods they call, where the real work happens. It's even like that when there are some references, for simple cases. So, start with a completely simple leaf node: <base_type name="int" byte_size=0x4 encoding=signed/> That's all simple, so its attribute values, map, empty children vector, debug_info_entry will all be hashed and inserted in the collector as above. Now there is a known debug_info_entry pointer for that DIE. Next, say you are copying: <variable name="x" type="#int" location=.../> The various simple attributes all resolve to known value pointers. The type="#int" attribute is the only reference value, pointing to the DIE we just mentioned. Since that's a fully resolved known DIE now, we can in fact treat it the same way as we treat simple attribute values. Along with the one debug_info_entry object in the collector, we only need to have exactly one dwarf_output::value::value_reference object that points to it. So here, that value object pointer is perfect hash and equality test for a reference attribute that refers to a DIE identical to the "int" above, just like the value object pointers for the simple value flavors are. If that's all there were to do, it would be easy. Of course, there are circular references. So say we have: <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> Now, the structure_type's own attribute map is simple, so that hashes up nicely. But, the member's attribute map includes a circular reference. So, what we do is still hash up the whole attribute map, but use zero as the hash value for the reference value. Now <member/> as a whole has a hash value that contributes to the children vector hash value, and that contributes to the structure_type's overall hash value. Two entries that look like this but have different references in the type attribute--but both circular references in the overall graph--would have the same hash value. So when comparing those, we'd get a hash collision and have to do a full comparison. That would find the two attribute maps identical, so look at the two children vectors. The corresponding member entries' attribute maps would then be compared for equivalence, the non-reference attribute values (i.e. name="next") matching by simple pointer comparison. But for the reference, we have to do a ref-walking comparison in the manner of dwarf_comparator. This plan means that for <pointer_type type="something circular"/> and <reference_type type="something circular"/>, we'll actually have dozens to thousands of entries with the same hash value--basically every single pointer_type to a nontrivial class/struct is a hash collision with every other. If that's the plan, then the ref-walking comparisons we do have to be very well-optimized. We'll be doing many, many of them every time we come across another pointer_type entry in the input. Picayune as I've been, this is just the broad overview. It seems solid, and the obvious thing to do, up to the point of the plan for circular references. It's not entirely clear that having so many hash collisions in this approach is a reasonable way to go. But I don't know what a different plan would be for efficiently identifying equivalent subtrees in the presence of circular references. Most of the real complexity in the copier has to do with handling forward references in attributes, including circular references. Aside from the simple-value mapping caches I described earlier, everything else is pretty much just interface glue for making the dwarf_output constructors work. The possibility of forward references means we have to partially construct entries while waiting to resolve their references, so there are lots of internal data structures for that. In valid input data, a single entire (logical) CU tree has no dangling references. So all the partially-built tracking data structures only need to live (at most) during the construction of one compile_unit tree in the dwarf_output object. The only things that live longer in the copier are just caches keyed on parts of the input that might be shared across input logical CUs (like the strings, but also input DIEs--for when eventually reading compressed format input). For following the control flow, you can start at dwarf_output::copier::make_unit. You can read the classes it calls to see how it's all organized. (Note how at various levels, most of the actual work happens inside a foo_copier constructor.) For all of the entry-copying hair inside dwarf_output::copier, I think it will be easiest to just answer questions as you read through the code, rather than trying to describe a structure and a plan. I can explain it all piece by piece, but at this point will largely be recovering the knowledge from re-reading the code anyway, so we can read it together. How that all works is quite ad hoc (and about the third generation of how I organized it), and I probably couldn't articulate an overall algorithm it is implementing. There is: #if 0 // Toggle this to enable massive debugging spew during construction. and making that 1 will get you quite a lot of spew that may help get a handle on how the partial entry resolution control flow goes. The usual ways to drive a test of this is: tests/dwarf-print --output file For nontrivial CUs in the input file, the debugging spew is truly massive. Thanks, Roland

2 30

Spam on the list
by Kurt Roeckx 25 Oct '10

25 Oct '10

Hi, I've been seeing alot of spam on this list the past week or something. Could someone please check the filters? Mine would have catched most of this if I didn't trust the mailinglist. Kurt

4 11

Re: dwarflint
by Tom Tromey 14 Oct '10

14 Oct '10

Roland> https://fedorahosted.org/elfutils/wiki/DwarfLint Roland> Please follow up on elfutils-devel(a)lists.fedorahosted.org about Roland> details. Roland> If you have any more suggestions for checks, please post them to Roland> elfutils-devel and we'll get them onto the TODO list. Roland> Especially, if you have come across bad data emitted by GCC that is not Roland> listed on SuspiciousDebuginfoCases, then let us know--and no less so if Roland> GCC has already been fixed. Here, I recommend simply searching for "GCC" in src/gdb/dwarf2read.c. This will yield a number of PRs (some open, some closed) and other oddities. Searching through the "debug" bugs in GCC bugzilla would also yield some stuff. Some other things: check_debug_aranges We saw cases in the wild where an arange entry was terminated early. That is, the 0,0 entry occurred before the end of the particular arange buffer. There is a bug, maybe closed, in Red Hat bugzilla for this. Consider checking that every CU has an arange entry. This is not strictly required, but it is nicer for consumers. ISTR filing a bug about this in GCC bugzilla. check_debug_pubnames / pubtypes FWIW, GCC doesn't emit these any more. So, IMO anyway, they are not very important to check. They were never all that usable in the first place. But, if you want to check these, then check that they are complete and correct. In the past we noticed that names were not always fully qualified (I forget if it was namespace- or class- qualification that GCC didn't do properly). I'm sure I filed a GCC bug for this. Tom

3 9

dwarflint --stats
by Roland McGrath 05 Oct '10

05 Oct '10

(Petr is on vacation, so it will most likely be at least a few weeks before anyone starts to work on this.) Jakub was interested in sampling some DWARF data to compare what one compiler vs another is doing with some broad statistics of semantic interest. The first particular thing to measure is how much location/value information we are getting for variables and parameters. This is not at all an error check, but I think it fits well enough into dwarflint as a special option to request statistics reports (in future perhaps several different kinds of things) either in addition to or instead of the normal warnings/errors. The first kind of statistic of interest is in stuff that I think dwarflint looks at already for some of its checks. So, it would go something like this: Consider each DW_TAG_variable or DW_TAG_formal_parameter that might have a location. That is, ignore variables with DW_AT_declaration and ignore the formal_parameter children of subprograms with DW_AT_declaration. Look at all the rest, and tally. (Double-check the cases with no DW_AT_location or DW_AT_const_value at all to see if there is some other exclusion from "might have a location" that I'm overlooking at the moment.) For each, compute what percentage of the variable's scope has locations or values. An extern global has DW_AT_external and no location at all, but is not missing any info. So exclude those from the tally. Globals (with DW_AT_external) and statics (without) are identified by having a non-list DW_AT_location that is a singleton DW_OP_addr expression. Perhaps (optionally?) exclude these from the tally entirely, so they don't dilute the cumulative percentages. Every compiler always just emits those locations regardless of optimization or debuginfo fanciness, so for comparing compilers it is probably more meaningful to measure only among the pool of variables with dynamic extent. If it has DW_AT_const_value, then call that 100%. If it has a non-list DW_AT_location with a nonempty expression, also call that 100%. If it has no DW_AT_location or a non-list DW_AT_location with an empty expression, call that 0%. Otherwise, it's a location list. So, first find the "scope" ranges set for this DIE. That is, if the DIE itself has a DW_AT_start_scope that is a rangelistptr, then exactly that is the set. If the DIE itself has DW_AT_{ranges,high_pc} then that's the set (but it won't). Otherwise, look back up parent DIEs until one has ranges/high_pc. If the variable DIE has a DW_AT_start_scope that is a constant, then exclude the portion of the range before it (see DWARFv4 3.3.8.2 item 11). If the location list covers any address bytes outside the "scope" set, then exclude those portions from the location list set for further consideration. I think dwarflint might already have a warning about that happening, or if not perhaps it should (though perhaps it is also an OK thing in the data, it remains unclear). Exclude any location list entries whose expression is empty. (You might already have a warning about those too, since they are superfluous entries to have.) Finally, count up the cumulative bytes covered by the scope set and those covered by the location set. Tally the ratio of those two counts as a percentage. Perhaps produce a scatter plot with x axis the location/scope rounded to an integer percentage and y axis the percentage of the DIEs considered whose ratio is x. And perhaps say min/max/avg(/median?) ratios seen. Another variant would be to also tally what portion of available locations is mutable vs immutable (or distribution of the ratios, or whatever). That is, DW_AT_const_value is immutable. A location expression is immutable if it ends in DW_OP_implicit_value or DW_OP_stack_value. If an expression uses DW_OP_{,bit_}piece, then it can be partially mutable and partially immutable. You can probably just choose arbitrarily to count those on one side or the other, or perhaps tally them as a separate third statistic. Jakub can say better than I which statistical analyses he is most interested in seeing. Thanks, Roland

3 9

Derniers jours des prix cassés,Tee-shirts et livraison gratuite
by contact＠tiao.fr 01 Oct '10

01 Oct '10

Pour être sûr de recevoir tous nos emails, ajoutez-nous à votre carnet d'adresses. Si ce mail ne s'affiche pas correctement, suivez ce lien ( http://www.emkg.net/D1/QVO-fzZ/QqhxAiwf6/QmESw6IZG_X.aspx )

1 0

dwarflint doesn't always catch a bad label PC
by Josh Stone 30 Sep '10

30 Sep '10

Hi, I tried dwarflint on the testcase given in rhbz634284, and it doesn't complain about the label PC which is out of its parent DIE's range. https://bugzilla.redhat.com/show_bug.cgi?id=634284 dwarflint does complain about the labels in Roland's more complicated implicitptr.c (linked at the end of the bz), so I would expect for my simpler case it should also complain. Any idea why it doesn't? Thanks, Josh

2 1

," shouted the nigger who was driving, or som
by Simitian Iliff 29 Sep '10

29 Sep '10

as I thumped; but when the door was opened in a few minutes, everything in the hall seemed very proper and prim, while the maid who came looked as stiff and disagreeable as could be. "For Miss Mimpriss, from Sir John Drinkwater," I said; "and I'll wait for an answer." "Very well," says the woman shortly. "I'll wait for an answer," I said, for she was shutting the door. "Yes; I heard," she says, and the door was shut in my face. "Hang all old maids!" I said. "They needn't be afraid of me;" and there I waited till I heard steps again and the door was opened; and the ill-looking woman says in a snappish tone: "Miss Adela Mimpriss's compliments, and she'll come across directly." "Any one would think I was a wild beast," I said to myself, as I went back and gave my message, finding all three in the room just as I had left them when I went away. STORY TWO, CHAPTER FIVE. JAMES BURDON SMELLS FIRE. Mr Barclay followed me out, and as soon as we were in the hall, "Burdon," he says, "you have a bunch of small keys, haven't you?" "Yes, Master Barclay, down in my pantry." "Lend them to me: I want to try if one of them will fit a lock of mine." He followed me down; and I was just handing them to him, when there was a d

1 0

Votre annonce Gratuite
by Dent Blanche 29 Sep '10

29 Sep '10

Document sans nom Ne plus recevoir de mails, se desinscrire

1 0

Avez-vous trouvé LA solution repas pour votre entreprise ?
by Aramis Auto via Datamel 29 Sep '10

29 Sep '10

Ajoutez nous à vos contacts pour être certain de recevoir nos e-mails Si vous avez du mal à lire ce message, cliquez ici http://p3tre.emv3.com/HM?a=DNX7Cr5_wxC-8SA9MJnTtu_nGHxKFzprNw3j Ticket Restaurant® - La grande idée pour tous - Donnons au déjeuner l'importance qu'il mérite [IMG] Vous n'avez pas de solution repas ? Vous disposez déjà d'une solution - 2/3 des entreprises où il fait bon repas ? - Choisissez les garanties vivre en France l'utilisent !* du leader et comparez ! - Cliquez Découvrez-la ! - Cliquez ici ! ici ! EN *UVRANT POUR L'AMÉLIORATION DES CONDITIONS DE TRAVAIL, VOUS AUGMENTEZ LA PERFORMANCE DE VOTRE ENTREPRISE ! Cliquez ici Ticket Restaurant est une marque enregistrée et propriété de Edenred Edenred S.A. ACCOR SERVICES FRANCE, S.A.S au capital de 388 036 640 €, siège social : 166-180 boulevard Gabriel Péri - 92245 Malakoff - 393.365.135 RCS NANTERRE - TVA intracommunautaire : FR 13 393 365 13 *Source : Palmarès 2010 de l'Institut Great Place to work - Le Figaro Economie-Mars 2010 Conformément à la loi «Informatique et Libertés» du 6 janvier 1978, vous disposez d'un droit d'accès, de rectification et d'opposition, aux informations qui vous concernent. Vous pouvez exercer ce droit auprès de l'émetteur en répondant directement à cet email. Vous pouvez également obtenir à cette adresse des informations concernant les transferts de données mentionnés ci-dessus. Si vous ne souhaitez pas recevoir des propositions commerciales de notre part ou de nos partenaires par voie électronique, merci de procéder à votre désinscription http://p3tre.emv3.com/HD?a=DNX7Cr5_wxC-8SA9MJnTtu_nGHxKFzprNA3i

1 0

Suite à notre dernier contact par mail
by Christian Gimbert 28 Sep '10

28 Sep '10

( "http://www.mediavisite.tv" ) Et si votre visibilité vous apportait de nouveau client ? Grâce à son concept unique, Médiavisite réalise votre vidéo à moindre coûts et augmente votre visibilité en vous livrant une vidéo prête à être diffusée sur votre site internet. En plus, cette vidéo peut être facilement diffusée sur toutes les plateformes sociales telles que Youtube, Facebook, Linkedin ... Une réalisation formatée, sans contraintes pour vous. Aucune contrainte de tournage (météo, déplacement d'équipe et de matériel) ... pas de perturbations de vos activités ! Vous nous fournissez quelques une des plus belles photos de votre entreprise, votre boutique, de vos biens immobiliers ou tout autre chose que vous souhaitez mettre en avant. Vous écrivez ensuite le texte de votre vidéo sur chacune des photos puis vous spécifiez si vous souhaitez un comédien ou une comédienne. Nos équipes vous apporteront des conseils pour rendre vidéo encore plus attractive, plus compréhensible, et ce dans le but de toucher votre coeur de cible. Votre vidéo ... ailleurs que sur internet ? Vous souhaitez diffuser votre message en boucle sur un salon ? Avoir votre film avec vous sur votre Smartphone, iPhone ou iPad ? Nos équipes de spécialistes vidéo pourrons vous conseiller et vous préparer les fichiers dont vous avez besoin. ( "http://www.mediavisite.tv/catalogue/7-video_daccueil_de_site_internet/372-m…" ) Quelques exemples ( "http://www.mediavisite.tv/videospromotionnelles/commerces/index.php?demo=im…" ) VISITE IMMOBILIÈRE Présentez vos biens ou projets immobiliers. ( "http://www.mediavisite.tv/videospromotionnelles/commerces/index.php?demo=im…" ) ( "http://www.mediavisite.tv/catalogue/6-video_dentreprise/205-carrosserie_lav…" ) CARROSSERIE LAVOISIER Créez le buzz en présentant votre entreprise de façon décalée ( "http://www.mediavisite.tv/catalogue/6-video_dentreprise/205-carrosserie_lav…" ) ( "http://www.mediavisite.tv/catalogue/6-video_dentreprise/335-arum_et_libellu…" ) ARUM ET LIBELLULE Présentation d'un décorateur floral à Aix-en-Provence ( "http://www.mediavisite.tv/catalogue/6-video_dentreprise/335-arum_et_libellu…" ) ( "http://www.mediavisite.tv/catalogue/8-video_de_formation/207-logic_immo-la_…" ) LA PUB EXPRESS Vidéo de formation d'un outil en ligne pour vos clients ( "http://www.mediavisite.tv/catalogue/8-video_de_formation/207-logic_immo-la_…" ) ( "http://www.mediavisite.tv/catalogue/5-video_produit_teleachat/10-bc_europe-…" ) ROLLUP SERVICES Présentation produit du Roll-Up, l'affiche publicitaire tout-en-un ( "http://www.mediavisite.tv/catalogue/5-video_produit_teleachat/10-bc_europe-…" ) ( "http://www.mediavisite.tv/catalogue/3-video_de_site_touristique/11-boinard-…" ) HOMELIDAYS Visitez votre location et ses environs avant même de vous y rendre. ( "http://www.mediavisite.tv/catalogue/3-video_de_site_touristique/11-boinard-…" ) ( "http://www.mediavisite.tv/catalogue/6-video_dentreprise/208-marque_and_co-a…" ) AGENCE MARQUE & CO Présentation de savoir-faire d'entreprise. ( "http://www.mediavisite.tv/catalogue/6-video_dentreprise/208-marque_and_co-a…" ) Contactez nous au +33(0) 979 392 218 ou par notre formulaire de contact ( "http://www.mediavisite.tv/nous_contacter/" ) Pour vous désinscrire, veuillez cliquer ici

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

elfutils-devel September 2010