1 // Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef CHROMIUMOS_WIDE_PROFILING_ADDRESS_MAPPER_H_
6 #define CHROMIUMOS_WIDE_PROFILING_ADDRESS_MAPPER_H_
7 
8 #include <stddef.h>
9 #include <stdint.h>
10 
11 #include <list>
12 #include <map>
13 
14 namespace quipper {
15 
16 class AddressMapper {
17  private:
18   struct MappedRange;
19 
20  public:
21   AddressMapper() : page_alignment_(0) {}
22 
23   // Copy constructor: copies mappings from |source| to this AddressMapper. This
24   // is useful for copying mappings from parent to child process upon fork(). It
25   // is also useful to copy kernel mappings to any process that is created.
26   AddressMapper(const AddressMapper& other);
27 
28   typedef std::list<MappedRange> MappingList;
29 
30   // Maps a new address range [real_addr, real_addr + length) to quipper space.
31   // |id| is an identifier value to be stored along with the mapping.
32   // AddressMapper does not care whether it is unique compared to all other IDs
33   // passed in. That is up to the caller to keep track of.
34   // |offset_base| represents the offset within the original region at which the
35   // mapping begins. The original region can be much larger than the mapped
36   // region.
37   // e.g. Given a mapped region with base=0x4000 and size=0x2000 mapped with
38   // offset_base=0x10000, then the address 0x5000 maps to an offset of 0x11000
39   // (0x5000 - 0x4000 + 0x10000).
40   // |remove_existing_mappings| indicates whether to remove old mappings that
41   // collide with the new range in real address space, indicating it has been
42   // unmapped.
43   // Returns true if mapping was successful.
44   bool MapWithID(const uint64_t real_addr, const uint64_t size,
45                  const uint64_t id, const uint64_t offset_base,
46                  bool remove_existing_mappings);
47 
48   // Looks up |real_addr| and returns the mapped address and MappingList
49   // iterator.
50   bool GetMappedAddressAndListIterator(const uint64_t real_addr,
51                                        uint64_t* mapped_addr,
52                                        MappingList::const_iterator* iter) const;
53 
54   // Uses MappingList iterator to fetch and return the mapping's ID and offset
55   // from the start of the mapped space.
56   // |real_addr_iter| must be valid and not at the end of the list.
57   void GetMappedIDAndOffset(const uint64_t real_addr,
58                             MappingList::const_iterator real_addr_iter,
59                             uint64_t* id, uint64_t* offset) const;
60 
61   // Returns true if there are no mappings.
62   bool IsEmpty() const { return mappings_.empty(); }
63 
64   // Returns the number of address ranges that are currently mapped.
65   size_t GetNumMappedRanges() const { return mappings_.size(); }
66 
67   // Returns the maximum length of quipper space containing mapped areas.
68   // There may be gaps in between blocks.
69   // If the result is 2^64 (all of quipper space), this returns 0.  Call
70   // IsEmpty() to distinguish this from actual emptiness.
71   uint64_t GetMaxMappedLength() const;
72 
73   // Sets the page alignment size. Set to 0 to disable page alignment.
74   // The alignment value must be a power of two. Any other value passed in will
75   // have no effect. Changing this value in between mappings results in
76   // undefined behavior.
77   void set_page_alignment(uint64_t alignment) {
78     // This also includes the case of 0.
79     if ((alignment & (alignment - 1)) == 0) page_alignment_ = alignment;
80   }
81 
82   // Dumps the state of the address mapper to logs. Useful for debugging.
83   void DumpToLog() const;
84 
85  private:
86   typedef std::map<uint64_t, MappingList::iterator> MappingMap;
87 
88   struct MappedRange {
89     uint64_t real_addr;
90     uint64_t mapped_addr;
91     uint64_t size;
92 
93     uint64_t id;
94     uint64_t offset_base;
95 
96     // Length of unmapped space after this range.
97     uint64_t unmapped_space_after;
98 
99     // Determines if this range intersects another range in real space.
100     inline bool Intersects(const MappedRange& range) const {
101       return (real_addr <= range.real_addr + range.size - 1) &&
102              (real_addr + size - 1 >= range.real_addr);
103     }
104 
105     // Determines if this range fully covers another range in real space.
106     inline bool Covers(const MappedRange& range) const {
107       return (real_addr <= range.real_addr) &&
108              (real_addr + size - 1 >= range.real_addr + range.size - 1);
109     }
110 
111     // Determines if this range fully contains another range in real space.
112     // This is different from Covers() in that the boundaries cannot overlap.
113     inline bool Contains(const MappedRange& range) const {
114       return (real_addr < range.real_addr) &&
115              (real_addr + size - 1 > range.real_addr + range.size - 1);
116     }
117 
118     // Determines if this range contains the given address |addr|.
119     inline bool ContainsAddress(uint64_t addr) const {
120       return (addr >= real_addr && addr <= real_addr + size - 1);
121     }
122   };
123 
124   // Returns an iterator to a MappedRange in |mappings_| that contains
125   // |real_addr|. Returns |mappings_.end()| if no range contains |real_addr|.
126   MappingList::const_iterator GetRangeContainingAddress(
127       uint64_t real_addr) const;
128 
129   // Removes an existing address mapping, given by an iterator pointing to an
130   // element of |mappings_|.
131   void Unmap(MappingList::iterator mapping_iter);
132 
133   // Given an address, and a nonzero, power-of-two |page_alignment_| value,
134   // returns the offset of the address from the start of the page it is on.
135   // Equivalent to |addr % page_alignment_|. Should not be called if
136   // |page_alignment_| is zero.
137   uint64_t GetAlignedOffset(uint64_t addr) const {
138     return addr & (page_alignment_ - 1);
139   }
140 
141   // Container for all the existing mappings.
142   MappingList mappings_;
143 
144   // Maps real addresses to iterators pointing to entries within |mappings_|.
145   // Must maintain a 1:1 entry correspondence with |mappings_|.
146   MappingMap real_addr_to_mapped_range_;
147 
148   // If set to nonzero, use this as a mapping page boundary. If a mapping does
149   // not begin at a multiple of this value, the remapped address should be given
150   // an offset that is the remainder.
151   //
152   // e.g. if alignment=0x1000 and a mapping starts at 0x520100, then the
153   // remapping should treat the mapping as starting at 0x520000, but addresses
154   // are only valid starting at 0x520100.
155   uint64_t page_alignment_;
156 };
157 
158 }  // namespace quipper
159 
160 #endif  // CHROMIUMOS_WIDE_PROFILING_ADDRESS_MAPPER_H_
161