I should have commit rights. I will make the changes you requested and upload.
Thanks for the review! On Wed, Jun 25, 2014 at 11:07 AM, Sean Callanan <[email protected]> wrote: > The IntersectsAllocation logic looks fine to me. > > I would change the second, four-argument version that you added be (a) > static and (b) named differently (e.g., “AllocationsIntersect”) to make it > clear that this is not performing the same service as the first function. > > Making the two-argument version of IntersectsAllocation const is good. > Thanks for the cleanup. > > The algorithmic cleanup looks fine too. > > Please provide an updated patch and I’ll commit if you don’t have that > right. > > Sean > > > On Jun 25, 2014, at 1:09 AM, Zachary Turner <[email protected]> wrote: > > > > The IRMemoryMap represents a set of disjoint allocations, stored as an > interval map. A bug in its allocation algorithm would cause this disjoint > property to be violated, resulting in overlapping intervals in the map. > > > > Consider the following scenario: > > > > Allocation 1: 8 bytes, address 8192 is chosen by the allocator > > Allocation 2: 524288, address 0 is probed > > > > Without this patch, the IntersectsAllocation() method would behave as > follows: > > > > 1) lower_bound(0) returns an iterator referring to allocation 1 > > 2) 0 is compared against 8192, and since 0 < 8192, it says there is no > intersection. > > > > With the patch, it does proper interval tests. > > > > http://reviews.llvm.org/D4286 > > > > Files: > > include/lldb/Expression/IRMemoryMap.h > > source/Expression/IRMemoryMap.cpp > > > > Index: include/lldb/Expression/IRMemoryMap.h > > =================================================================== > > --- include/lldb/Expression/IRMemoryMap.h > > +++ include/lldb/Expression/IRMemoryMap.h > > @@ -27,7 +27,8 @@ > > /// This class encapsulates a group of memory objects that must be > readable > > /// or writable from the host process regardless of whether the process > > /// exists. This allows the IR interpreter as well as JITted code to > access > > -/// the same memory. > > +/// the same memory. All allocations made by this class are > represented as > > +/// disjoint intervals. > > /// > > /// Point queries against this group of memory objects can be made by the > > /// address in the tar at which they reside. If the inferior does not > > @@ -118,7 +119,12 @@ > > lldb::addr_t FindSpace (size_t size); > > bool ContainsHostOnlyAllocations (); > > AllocationMap::iterator FindAllocation (lldb::addr_t addr, size_t > size); > > - bool IntersectsAllocation (lldb::addr_t addr, size_t size); > > + > > + // Returns true if the given allocation intersects any allocation > in the memory map. > > + bool IntersectsAllocation (lldb::addr_t addr, size_t size) const; > > + > > + // Returns true if the two given allocations intersect each other. > > + bool IntersectsAllocation (lldb::addr_t addr1, size_t size1, > lldb::addr_t addr2, size_t size2) const; > > }; > > > > } > > Index: source/Expression/IRMemoryMap.cpp > > =================================================================== > > --- source/Expression/IRMemoryMap.cpp > > +++ source/Expression/IRMemoryMap.cpp > > @@ -125,33 +125,48 @@ > > } > > > > bool > > -IRMemoryMap::IntersectsAllocation (lldb::addr_t addr, size_t size) > > +IRMemoryMap::IntersectsAllocation (lldb::addr_t addr, size_t size) const > > { > > if (addr == LLDB_INVALID_ADDRESS) > > return false; > > > > - AllocationMap::iterator iter = m_allocations.lower_bound (addr); > > + AllocationMap::const_iterator iter = m_allocations.lower_bound > (addr); > > > > - if (iter == m_allocations.end() || > > - iter->first > addr) > > - { > > - if (iter == m_allocations.begin()) > > - return false; > > - > > - iter--; > > + // Since we only know that the returned interval begins at a > location greater than or > > + // equal to where the given interval begins, it's possible that the > given interval > > + // intersects either the returned interval or the previous > interval. Thus, we need to > > + // check both. Note that we only need to check these two intervals. > Since all intervals > > + // are disjoint it is not possible that an adjacent interval does > not intersect, but a > > + // non-adjacent interval does intersect. > > + if (iter != m_allocations.end()) { > > + if (IntersectsAllocation(addr, size, > iter->second.m_process_start, iter->second.m_size)) > > + return true; > > } > > - > > - while (iter != m_allocations.end() && iter->second.m_process_alloc > < addr + size) > > - { > > - if (iter->second.m_process_start + iter->second.m_size > addr) > > + > > + if (iter != m_allocations.begin()) { > > + --iter; > > + if (IntersectsAllocation(addr, size, > iter->second.m_process_start, iter->second.m_size)) > > return true; > > - > > - ++iter; > > } > > - > > + > > return false; > > } > > > > +bool > > +IRMemoryMap::IntersectsAllocation(lldb::addr_t addr1, size_t size1, > lldb::addr_t addr2, size_t size2) const { > > + // Given two half open intervals [A, B) and [X, Y), the only 6 > permutations that satisfy > > + // A<B and X<Y are the following: > > + // A B X Y > > + // A X B Y (intersects) > > + // A X Y B (intersects) > > + // X A B Y (intersects) > > + // X A Y B (intersects) > > + // X Y A B > > + // The first is B <= X, and the last is Y <= A. > > + // So the condition is !(B <= X || Y <= A)), or (X < B && A < Y) > > + return (addr2 < (addr1 + size1)) && (addr1 < (addr2 + size2)); > > +} > > + > > lldb::ByteOrder > > IRMemoryMap::GetByteOrder() > > { > > <D4286.10822.patch>_______________________________________________ > > lldb-commits mailing list > > [email protected] > > http://lists.cs.uiuc.edu/mailman/listinfo/lldb-commits > >
_______________________________________________ lldb-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/lldb-commits
