Force iteration over FieldDecls and RecordDecls in deterministic order.

[zturner]

Summary

Previously we were, in many places in the code, using a DenseMap<> to hold FieldDecls representing class members, and RecordDecls representing bases and virtual bases.

In some instances, we would try to copy records by iterating over their fields and bases and adding each one to a new AST. This yields a non-deterministic ordering of the results, and leads to invalid record layout. Specifically, clang expects field index order to be in offset order, and the field index order is determined by the order you add items to a record. So when synthesizing a new AST, you *must* add items in field offset order. Therefore, copying by iterating over a DenseMap of FieldDecls or RecordDecls for bases and inserting them this way yields invalid record layout.

This bug is present on all platforms and all ABIs, but was only surfaced on Windows with the MS ABI record layout because of extra checks and asserts present in MicrosoftRecordLayoutBuilder::layoutField. Also, this requirement of importing in a deterministic order applies to bases and virtual bases too, not just fields.

The fix employed here is to change all occurrences of DenseMap<A,B> as it pertains to ASTs to std::vector<std::pair<A, B>>. There were only a very few instances of anyone using the DenseMaps for lookup, and given the typical number of fields a class has, it seems like a reasonable tradeoff to ensure that this kind of problem can never happen again. A std::vector<> should also require less memory than a DenseMap. I'm not sure if there are tons of SymbolFileDWARF::LayoutInfos lying around in memory, but if there are this could have an impact on memory footprint too.

Since this problem was present everywhere it's unclear how -- if at all -- it was manifesting or what types of issues this might fix for everyone else. The problem may have been masked if ASLR was disabled or depending on what allocator was used. On Windows it definitely fixes a whole slew of test failures. I know Linux has been seeing some non-deterministic failures as well, so one of the Linux people shoudl see if this patch makes a difference.

[zturner]

source/Expression/ClangASTSource.cpp

1543

Since I didn't call it out specifically in the CL, this is the line that was introducing the non-determinism when a DenseMap is used.

It would be possible to fix this by only copying the elements of the DenseMap<> out to a temporary list and sorting the list, but since iterating in a non-deterministic order is perilous, I will propose this change first.

[amccarth]

Nice find.

source/Expression/ClangASTSource.cpp

1543

Nit: I assume fi was and abbreviation for "field iterator". Since this is no longer and iterator and just (a reference to) the field, perhaps rename it.

[rnk]

Nice! If you actually need fast lookup, you can use llvm::MapVector, but based on your analysis it looks like std::vector is more appropriate.

[ovyalov]

Do we need to use operator[] on vector? I'm wondering whether list can be used instead of vector.

source/Expression/ClangASTSource.cpp

1541

Minor thing - destination_list.reserve(source_list.size())

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

2675

Could you use cbegin and replace such a long type name with sth like
auto pos = layout_info.field_offsets.cbegin(), end = layout_info.field_offsets.cend();

[zturner]

Fixed some of the issues that were pointed out. Will try to upload this tomorrow if there's no further comments.

[clayborg]

Adding Sean as a reviewer now that he is back.

[spyffe]

The abstract interface for ExternalASTSource has a layoutRecordType() function (llvm/tools/clang/include/clang/AST/ExternalASTSource.h):

virtual bool layoutRecordType(
    const RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
    llvm::DenseMap<const FieldDecl *, uint64_t> &FieldOffsets,
    llvm::DenseMap<const CXXRecordDecl *, CharUnits> &BaseOffsets,
    llvm::DenseMap<const CXXRecordDecl *, CharUnits> &VirtualBaseOffsets);

We're conforming to that. I'm concerned that by changing the signature of layoutRecordType() in LLDB, you're causing our version to not be called at all. Unless I'm missing something, this doesn't look like the right fix.

[spyffe]

As an aside, when laying out a RecordDecl, you have the ordering for its fields right in the RecordDecl. If MicrosoftRecordLayoutBuilder relying on the llvm::DenseMap for ordering, I think it's MicrosoftRecordLayoutBuilder that has the bug. By my understanding of how record layout works, it should only be using the map to go from fields/bases to offsets – nothing else.

[zturner]

This bug isn't specific to Microsoft layout. Clang as a general rule
requires fields to be added in offset order, and iterating over a dense map
doesn't give you that.

I'll let majnemer or rnk comment on the ExternalASTSource interface

[zturner]

Also the layout builder never gets the dense map. So Microsoft Layout
Builder doesn't know anything about the dense map. It's ClangASTSource that
iterates over the map, and all the layout builder sees is fields being
added in the wrong order

[zturner]

I see what you mean about the interface. I guess that settles that then,
the interface needs to be consistent. I'll add override keywords so the
compiler can catch that for me in the future.

But our implementation still needs to add fields in the correct order, so
iterating over the DenseMap is still not the right approach

[zturner]

I talked to some of the clang guys here and they said to go back to
DenseMaps to conform to the ExternalASTSource interface, but make sure you
iterate over fields and bases in offset order, which means sorting the list
before doing the insertion. So I will submit a patch to do that today.

include/lldb/Expression/ClangASTSource.h

 #define liblldb_ClangASTSource_h_
 
 #include <set>
+#include <vector>
 
 #include "clang/Basic/IdentifierTable.h"
 #include "lldb/Symbol/ClangExternalASTSourceCommon.h"

 
 #include "llvm/ADT/SmallSet.h"
 
+namespace clang
+{
+class CharUnits;
+class FieldDecl;
+}
+
 namespace lldb_private {
     
 //----------------------------------------------------------------------

     FindExternalLexicalDecls (const clang::DeclContext *DC,
                               bool (*isKindWeWant)(clang::Decl::Kind),
                               llvm::SmallVectorImpl<clang::Decl*> &Decls);
-    
+    typedef std::vector<std::pair<const clang::FieldDecl *, uint64_t>> FieldOffsetList;
+    typedef std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> BaseOffsetList;
+
     //------------------------------------------------------------------
     /// Specify the layout of the contents of a RecordDecl.
     ///

     ///
     /// @return
     ///     True <=> the layout is valid.
-    //-----------------------------------------------------------------    
-    bool 
-    layoutRecordType(const clang::RecordDecl *Record,
-                     uint64_t &Size, 
-                     uint64_t &Alignment,
-                     llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets);
-    
+    //-----------------------------------------------------------------
+    bool layoutRecordType(const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+                          FieldOffsetList &FieldOffsets, BaseOffsetList &BaseOffsets,
+                          BaseOffsetList &VirtualBaseOffsets);
+
     //------------------------------------------------------------------
     /// Complete a TagDecl.
     ///

         {
             return m_original.CompleteType(Class);
         }
-        
-        bool 
-        layoutRecordType(const clang::RecordDecl *Record,
-                         uint64_t &Size, 
-                         uint64_t &Alignment,
-                         llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                         llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                         llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets)
+        bool
+        layoutRecordType(const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+                         FieldOffsetList &FieldOffsets, BaseOffsetList &BaseOffsets, BaseOffsetList &VirtualBaseOffsets)
         {
             return m_original.layoutRecordType(Record,
                                                Size, 

include/lldb/Symbol/ClangExternalASTSourceCallbacks.h

     typedef void (*CompleteTagDeclCallback)(void *baton, clang::TagDecl *);
     typedef void (*CompleteObjCInterfaceDeclCallback)(void *baton, clang::ObjCInterfaceDecl *);
     typedef void (*FindExternalVisibleDeclsByNameCallback)(void *baton, const clang::DeclContext *DC, clang::DeclarationName Name, llvm::SmallVectorImpl <clang::NamedDecl *> *results);
-    typedef bool (*LayoutRecordTypeCallback)(void *baton, 
-                                             const clang::RecordDecl *Record,
-                                             uint64_t &Size, 
-                                             uint64_t &Alignment,
-                                             llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                                             llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                                             llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets);
+    typedef bool (*LayoutRecordTypeCallback)(
+        void *baton, const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+        std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+        std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+        std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
 
     ClangExternalASTSourceCallbacks (CompleteTagDeclCallback tag_decl_callback,
                                      CompleteObjCInterfaceDeclCallback objc_decl_callback,

     
     virtual void
     CompleteType (clang::ObjCInterfaceDecl *objc_decl);
-    
-    bool 
-    layoutRecordType(const clang::RecordDecl *Record,
-                     uint64_t &Size, 
-                     uint64_t &Alignment,
-                     llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets);
+    bool layoutRecordType(const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+                          std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                          std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                          std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
     void
     SetExternalSourceCallbacks (CompleteTagDeclCallback tag_decl_callback,
                                 CompleteObjCInterfaceDeclCallback objc_decl_callback,

source/Expression/ClangASTSource.cpp

     while(0);
 }
 
-typedef llvm::DenseMap <const FieldDecl *, uint64_t> FieldOffsetMap;
-typedef llvm::DenseMap <const CXXRecordDecl *, CharUnits> BaseOffsetMap;
-
 template <class D, class O>
 static bool
-ImportOffsetMap (llvm::DenseMap <const D*, O> &destination_map,
-                 llvm::DenseMap <const D*, O> &source_map,
-                 ClangASTImporter *importer,
+ImportOffsetList(std::vector<std::pair<const D *, O>> &destination_list,
+                 const std::vector<std::pair<const D *, O>> &source_list, ClangASTImporter *importer,
                  ASTContext &dest_ctx)
 {
-    typedef llvm::DenseMap <const D*, O> MapType;
+    typedef std::vector<std::pair<const D *, O>> ListType;
 
-    for (typename MapType::iterator fi = source_map.begin(), fe = source_map.end();
-         fi != fe;
-         ++fi)
+    for (const auto &fi : source_list)
     {
-        DeclFromUser <D> user_decl(const_cast<D*>(fi->first));
+        DeclFromUser<D> user_decl(const_cast<D *>(fi.first));
         DeclFromParser <D> parser_decl(user_decl.Import(importer, dest_ctx));
         if (parser_decl.IsInvalid())
             return false;
-        destination_map.insert(std::pair<const D *, O>(parser_decl.decl, fi->second));
+        destination_list.push_back(std::pair<const D *, O>(parser_decl.decl, fi.second));
     }
 
     return true;
 }
 
-template <bool IsVirtual> bool ExtractBaseOffsets (const ASTRecordLayout &record_layout,
-                                                   DeclFromUser<const CXXRecordDecl> &record,
-                                                   BaseOffsetMap &base_offsets)
+template <bool IsVirtual>
+bool
+ExtractBaseOffsets(const ASTRecordLayout &record_layout, DeclFromUser<const CXXRecordDecl> &record,
+                   ClangASTSource::BaseOffsetList &base_offsets)
 {
-    for (CXXRecordDecl::base_class_const_iterator
-            bi = (IsVirtual ? record->vbases_begin() : record->bases_begin()),
-            be = (IsVirtual ? record->vbases_end() : record->bases_end());
-         bi != be;
-         ++bi)
+    for (const auto &base : (IsVirtual ? record->vbases() : record->bases()))
     {
-        if (!IsVirtual && bi->isVirtual())
+        if (!IsVirtual && base.isVirtual())
             continue;
 
-        const clang::Type *origin_base_type = bi->getType().getTypePtr();
+        const clang::Type *origin_base_type = base.getType().getTypePtr();
         const clang::RecordType *origin_base_record_type = origin_base_type->getAs<RecordType>();
 
         if (!origin_base_record_type)

         else
             base_offset = record_layout.getBaseClassOffset(origin_base_cxx_record.decl);
 
-        base_offsets.insert(std::pair<const CXXRecordDecl *, CharUnits>(origin_base_cxx_record.decl, base_offset));
+        base_offsets.push_back(std::make_pair(origin_base_cxx_record.decl, base_offset));
     }
 
     return true;
 }
 
 bool
-ClangASTSource::layoutRecordType(const RecordDecl *record,
-                                 uint64_t &size,
-                                 uint64_t &alignment,
-                                 FieldOffsetMap &field_offsets,
-                                 BaseOffsetMap &base_offsets,
-                                 BaseOffsetMap &virtual_base_offsets)
+ClangASTSource::layoutRecordType(const RecordDecl *record, uint64_t &size, uint64_t &alignment,
+                                 FieldOffsetList &field_offsets, BaseOffsetList &base_offsets,
+                                 BaseOffsetList &virtual_base_offsets)
 {
     ClangASTMetrics::RegisterRecordLayout();
 

     if (origin_record.IsInvalid())
         return false;
 
-    FieldOffsetMap origin_field_offsets;
-    BaseOffsetMap origin_base_offsets;
-    BaseOffsetMap origin_virtual_base_offsets;
+    FieldOffsetList origin_field_offsets;
+    BaseOffsetList origin_base_offsets;
+    BaseOffsetList origin_virtual_base_offsets;
 
     ClangASTContext::GetCompleteDecl(&origin_record->getASTContext(), const_cast<RecordDecl*>(origin_record.decl));
 

 
     int field_idx = 0, field_count = record_layout.getFieldCount();
 
-    for (RecordDecl::field_iterator fi = origin_record->field_begin(), fe = origin_record->field_end();
-         fi != fe;
-         ++fi)
+    origin_field_offsets.reserve(field_count);
+    for (const auto &field : origin_record->fields())
     {
         if (field_idx >= field_count)
             return false; // Layout didn't go well.  Bail out.
 
         uint64_t field_offset = record_layout.getFieldOffset(field_idx);
 
-        origin_field_offsets.insert(std::pair<const FieldDecl *, uint64_t>(*fi, field_offset));
+        origin_field_offsets.push_back(std::pair<const FieldDecl *, uint64_t>(field, field_offset));
 
         field_idx++;
     }

             return false;
     }
 
-    if (!ImportOffsetMap(field_offsets, origin_field_offsets, m_ast_importer, parser_ast_context) ||
-        !ImportOffsetMap(base_offsets, origin_base_offsets, m_ast_importer, parser_ast_context) ||
-        !ImportOffsetMap(virtual_base_offsets, origin_virtual_base_offsets, m_ast_importer, parser_ast_context))
+    if (!ImportOffsetList(field_offsets, origin_field_offsets, m_ast_importer, parser_ast_context) ||
+        !ImportOffsetList(base_offsets, origin_base_offsets, m_ast_importer, parser_ast_context) ||
+        !ImportOffsetList(virtual_base_offsets, origin_virtual_base_offsets, m_ast_importer, parser_ast_context))
         return false;
 
     size = record_layout.getSize().getQuantity() * m_ast_context->getCharWidth();

              fi != fe;
              ++fi)
         {
-            log->Printf("LRT[%u]     (FieldDecl*)%p, Name = '%s', Offset = %" PRId64 " bits",
-                        current_id, static_cast<void*>(*fi),
-                        fi->getNameAsString().c_str(), field_offsets[*fi]);
+
+            log->Printf("LRT[%u]     (FieldDecl*)%p, Name = '%s', Offset = %" PRId64 " bits", current_id,
+                        static_cast<void *>(*fi), fi->getNameAsString().c_str(),
+                        record_layout.getFieldOffset(fi->getFieldIndex()));
         }
         DeclFromParser <const CXXRecordDecl> parser_cxx_record = DynCast<const CXXRecordDecl>(parser_record);
         if (parser_cxx_record.IsValid())

                 DeclFromParser <RecordDecl> base_record(base_record_type->getDecl());
                 DeclFromParser <CXXRecordDecl> base_cxx_record = DynCast<CXXRecordDecl>(base_record);
 
-                log->Printf("LRT[%u]     %s(CXXRecordDecl*)%p, Name = '%s', Offset = %" PRId64 " chars",
-                            current_id, (is_virtual ? "Virtual " : ""),
-                            static_cast<void*>(base_cxx_record.decl),
-                            base_cxx_record.decl->getNameAsString().c_str(),
-                            (is_virtual
-                                ? virtual_base_offsets[base_cxx_record.decl].getQuantity()
-                                : base_offsets[base_cxx_record.decl].getQuantity()));
+                clang::CharUnits base_offset = is_virtual ? record_layout.getVBaseClassOffset(base_cxx_record.decl)
+                                                          : record_layout.getBaseClassOffset(base_cxx_record.decl);
+                log->Printf("LRT[%u]     %s(CXXRecordDecl*)%p, Name = '%s', Offset = %" PRId64 " chars", current_id,
+                            (is_virtual ? "Virtual " : ""), static_cast<void *>(base_cxx_record.decl),
+                            base_cxx_record.decl->getNameAsString().c_str(), base_offset);
             }
         }
         else

source/Plugins/LanguageRuntime/ObjC/AppleObjCRuntime/AppleObjCDeclVendor.cpp

     }
 
     bool
-    layoutRecordType(const clang::RecordDecl *Record,
-                     uint64_t &Size,
-                     uint64_t &Alignment,
-                     llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                     llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets)
+    layoutRecordType(const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+                     std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets)
     {
         return false;
     }

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

                                     clang::DeclarationName Name,
                                     llvm::SmallVectorImpl <clang::NamedDecl *> *results);
 
-    static bool 
-    LayoutRecordType (void *baton, 
-                      const clang::RecordDecl *record_decl,
-                      uint64_t &size, 
-                      uint64_t &alignment,
-                      llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets);
-
-    bool 
-    LayoutRecordType (const clang::RecordDecl *record_decl,
-                      uint64_t &size, 
-                      uint64_t &alignment,
-                      llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets);
+    static bool
+    LayoutRecordType(void *baton, const clang::RecordDecl *record_decl, uint64_t &size, uint64_t &alignment,
+                     std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
+
+    bool LayoutRecordType(const clang::RecordDecl *record_decl, uint64_t &size, uint64_t &alignment,
+                          std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                          std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                          std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
 
     struct LayoutInfo
     {

         }
         uint64_t bit_size;
         uint64_t alignment;
-        llvm::DenseMap <const clang::FieldDecl *, uint64_t> field_offsets;
-        llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> base_offsets;
-        llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> vbase_offsets;
+        std::vector<std::pair<const clang::FieldDecl *, uint64_t>> field_offsets;
+        std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> base_offsets;
+        std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> vbase_offsets;
     };
     //------------------------------------------------------------------
     // PluginInterface protocol

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

                                                                                                                              GetClangASTContext().GetBuiltinTypeForEncodingAndBitSize(eEncodingSint, word_width),
                                                                                                                              accessibility,
                                                                                                                              anon_field_info.bit_size);
-                                            
-                                            layout_info.field_offsets.insert(std::make_pair(unnamed_bitfield_decl, anon_field_info.bit_offset));
+                                            layout_info.field_offsets.push_back(
+                                                std::make_pair(unnamed_bitfield_decl, anon_field_info.bit_offset));
                                         }
                                     }
                                     last_field_info = this_field_info;

                                                                                     bit_size);
                                 
                                 GetClangASTContext().SetMetadataAsUserID (field_decl, MakeUserID(die->GetOffset()));
-                                
-                                layout_info.field_offsets.insert(std::make_pair(field_decl, field_bit_offset));
 
+                                layout_info.field_offsets.push_back(std::make_pair(field_decl, field_bit_offset));
                             }
                             else
                             {

                         }
                         else
                         {
-                            layout_info.base_offsets.insert(std::make_pair(base_class_clang_type.GetAsCXXRecordDecl(),
-                                                                           clang::CharUnits::fromQuantity(member_byte_offset)));
+                            layout_info.base_offsets.push_back(
+                                std::make_pair(base_class_clang_type.GetAsCXXRecordDecl(),
+                                               clang::CharUnits::fromQuantity(member_byte_offset)));
                         }
                     }
                 }

                                                                   static_cast<uint32_t>(layout_info.base_offsets.size()),
                                                                   static_cast<uint32_t>(layout_info.vbase_offsets.size()));
 
-                        uint32_t idx;
-                        {
-                        llvm::DenseMap <const clang::FieldDecl *, uint64_t>::const_iterator pos, end = layout_info.field_offsets.end();
-                        for (idx = 0, pos = layout_info.field_offsets.begin(); pos != end; ++pos, ++idx)
+                        for (const auto &entry : layout_info.field_offsets)
                         {
-                            GetObjectFile()->GetModule()->LogMessage (log,
-                                                                      "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) field[%u] = { bit_offset=%u, name='%s' }",
-                                                                      static_cast<void*>(clang_type.GetOpaqueQualType()),
-                                                                      idx,
-                                                                      static_cast<uint32_t>(pos->second),
-                                                                      pos->first->getNameAsString().c_str());
-                        }
+                            GetObjectFile()->GetModule()->LogMessage(
+                                log, "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) field[%u] = "
+                                     "{ bit_offset=%u, name='%s' }",
+                                static_cast<void *>(clang_type.GetOpaqueQualType()), entry.first->getFieldIndex(),
+                                static_cast<uint32_t>(entry.second), entry.first->getNameAsString().c_str());
                         }
 
+                        uint32_t idx = 0;
+                        for (const auto &entry : layout_info.base_offsets)
                         {
-                        llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits>::const_iterator base_pos, base_end = layout_info.base_offsets.end();
-                        for (idx = 0, base_pos = layout_info.base_offsets.begin(); base_pos != base_end; ++base_pos, ++idx)
-                        {
-                            GetObjectFile()->GetModule()->LogMessage (log,
-                                                                      "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) base[%u] = { byte_offset=%u, name='%s' }",
-                                                                      clang_type.GetOpaqueQualType(),
-                                                                      idx,
-                                                                      (uint32_t)base_pos->second.getQuantity(),
-                                                                      base_pos->first->getNameAsString().c_str());
+                            GetObjectFile()->GetModule()->LogMessage(
+                                log, "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) base[%u] = { "
+                                     "byte_offset=%u, name='%s' }",
+                                clang_type.GetOpaqueQualType(), idx, (uint32_t)entry.second.getQuantity(),
+                                entry.first->getNameAsString().c_str());
+                            ++idx;
                         }
-                        }
-                        {
-                        llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits>::const_iterator vbase_pos, vbase_end = layout_info.vbase_offsets.end();
-                        for (idx = 0, vbase_pos = layout_info.vbase_offsets.begin(); vbase_pos != vbase_end; ++vbase_pos, ++idx)
+
+                        idx = 0;
+                        for (const auto &entry : layout_info.vbase_offsets)
                         {
-                            GetObjectFile()->GetModule()->LogMessage (log,
-                                                                      "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) vbase[%u] = { byte_offset=%u, name='%s' }",
-                                                                      static_cast<void*>(clang_type.GetOpaqueQualType()),
-                                                                      idx,
-                                                                      static_cast<uint32_t>(vbase_pos->second.getQuantity()),
-                                                                      vbase_pos->first->getNameAsString().c_str());
-                        }
+                            GetObjectFile()->GetModule()->LogMessage(
+                                log, "SymbolFileDWARF::ResolveClangOpaqueTypeDefinition (clang_type = %p) vbase[%u] = "
+                                     "{ byte_offset=%u, name='%s' }",
+                                static_cast<void *>(clang_type.GetOpaqueQualType()), idx,
+                                static_cast<uint32_t>(entry.second.getQuantity()),
+                                entry.first->getNameAsString().c_str());
+                            ++idx;
                         }
                     }
                     m_record_decl_to_layout_map.insert(std::make_pair(record_decl, layout_info));

     }
 }
 
-bool 
-SymbolFileDWARF::LayoutRecordType (void *baton, 
-                                   const clang::RecordDecl *record_decl,
-                                   uint64_t &size, 
-                                   uint64_t &alignment,
-                                   llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                                   llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                                   llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets)
+bool
+SymbolFileDWARF::LayoutRecordType(void *baton, const clang::RecordDecl *record_decl, uint64_t &size,
+                                  uint64_t &alignment,
+                                  std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &field_offsets,
+                                  std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &base_offsets,
+                                  std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &vbase_offsets)
 {
     SymbolFileDWARF *symbol_file_dwarf = (SymbolFileDWARF *)baton;
     return symbol_file_dwarf->LayoutRecordType (record_decl, size, alignment, field_offsets, base_offsets, vbase_offsets);
 }
 
-
-bool 
-SymbolFileDWARF::LayoutRecordType (const clang::RecordDecl *record_decl,
-                                   uint64_t &bit_size, 
-                                   uint64_t &alignment,
-                                   llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                                   llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                                   llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets)
+bool
+SymbolFileDWARF::LayoutRecordType(const clang::RecordDecl *record_decl, uint64_t &bit_size, uint64_t &alignment,
+                                  std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &field_offsets,
+                                  std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &base_offsets,
+                                  std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &vbase_offsets)
 {
     Log *log (LogChannelDWARF::GetLogIfAll(DWARF_LOG_DEBUG_INFO));
     RecordDeclToLayoutMap::iterator pos = m_record_decl_to_layout_map.find (record_decl);

source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h

     
     static void
     CompleteObjCInterfaceDecl (void *baton, clang::ObjCInterfaceDecl *);
-    
-    static bool 
-    LayoutRecordType (void *baton, 
-                      const clang::RecordDecl *record_decl,
-                      uint64_t &size, 
-                      uint64_t &alignment,
-                      llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                      llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets);
 
+    static bool
+    LayoutRecordType(void *baton, const clang::RecordDecl *record_decl, uint64_t &size, uint64_t &alignment,
+                     std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+                     std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets);
 
     //------------------------------------------------------------------
     // PluginInterface protocol

source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp

     }
 }
 
-bool 
-SymbolFileDWARFDebugMap::LayoutRecordType (void *baton, 
-                                           const clang::RecordDecl *record_decl,
-                                           uint64_t &size, 
-                                           uint64_t &alignment,
-                                           llvm::DenseMap <const clang::FieldDecl *, uint64_t> &field_offsets,
-                                           llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &base_offsets,
-                                           llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &vbase_offsets)
+bool
+SymbolFileDWARFDebugMap::LayoutRecordType(
+    void *baton, const clang::RecordDecl *record_decl, uint64_t &size, uint64_t &alignment,
+    std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &field_offsets,
+    std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &base_offsets,
+    std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &vbase_offsets)
 {
     SymbolFileDWARFDebugMap *symbol_file_dwarf = (SymbolFileDWARFDebugMap *)baton;
     SymbolFileDWARF *oso_dwarf;

source/Symbol/ClangExternalASTSourceCallbacks.cpp

         m_callback_objc_decl (m_callback_baton, objc_decl);
 }
 
-bool 
-ClangExternalASTSourceCallbacks::layoutRecordType(const clang::RecordDecl *Record,
-                                                  uint64_t &Size, 
-                                                  uint64_t &Alignment,
-                                                  llvm::DenseMap <const clang::FieldDecl *, uint64_t> &FieldOffsets,
-                                                  llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &BaseOffsets,
-                                                  llvm::DenseMap <const clang::CXXRecordDecl *, clang::CharUnits> &VirtualBaseOffsets)
+bool
+ClangExternalASTSourceCallbacks::layoutRecordType(
+    const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
+    std::vector<std::pair<const clang::FieldDecl *, uint64_t>> &FieldOffsets,
+    std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &BaseOffsets,
+    std::vector<std::pair<const clang::CXXRecordDecl *, clang::CharUnits>> &VirtualBaseOffsets)
 {
     if (m_callback_layout_record_type)
         return m_callback_layout_record_type(m_callback_baton,

test/functionalities/data-formatter/data-formatter-stl/libcxx/vbool/TestDataFormatterLibcxxVBool.py

         self.data_formatter_commands()
 
     @skipIfLinux # No standard locations for libc++ on Linux, so skip for now 
-    @skipIfWindows # http://llvm.org/pr21800
+    @skipIfWindows # Windows doesn't have libcxx
     @dwarf_test
     def test_with_dwarf_and_run_command(self):
         """Test data formatter commands."""

test/functionalities/data-formatter/data-formatter-stl/libstdcpp/vbool/TestDataFormatterStdVBool.py

 
     @expectedFailureFreeBSD("llvm.org/pr20548") # fails to build on lab.llvm.org buildbot
     @dwarf_test
-    @skipIfWindows # http://llvm.org/pr21800
     @skipIfDarwin
     def test_with_dwarf_and_run_command(self):
         """Test data formatter commands."""

test/lang/c/bitfields/TestBitfields.py

         self.bitfields_variable_python()
 
     @dwarf_test
-    @unittest2.skipIf(sys.platform.startswith("win32"), "BitFields exhibit crashes in record layout on Windows (http://llvm.org/pr21800)")
     def test_with_dwarf_and_run_command(self):
         """Test 'frame variable ...' on a variable with bitfields."""
         self.buildDwarf()

 
     @python_api_test
     @dwarf_test
-    @unittest2.skipIf(sys.platform.startswith("win32"), "BitFields exhibit crashes in record layout on Windows (http://llvm.org/pr21800)")
     @expectedFailureGcc # GCC (4.6/4.7) generates incorrect code with unnamed bitfields.
     def test_with_dwarf_and_python_api(self):
         """Use Python APIs to inspect a bitfields variable."""