ROSE  0.11.2.0
ExtentMap.C
1 /* The ExtentMap class. This class is similar std::map<rose_addr_t,rose_addr_t> where the two addresses are the starting
2  * offset and size. The main difference is that if two adjacent extents are added to the map they will be condensed into a
3  * single extent. This class is used to keep track of what parts of a binary file have been parsed, and is also used to
4  * manage string table free lists, among other things. */
5 #include <rosePublicConfig.h>
6 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
7 #include "sage3basic.h"
8 
9 #include <boost/foreach.hpp>
10 
11 using namespace Rose;
12 
13 Extent toExtent(const AddressInterval &x) {
14  return x.isEmpty() ? Extent() : Extent::inin(x.least(), x.greatest());
15 }
16 
17 AddressInterval toAddressInterval(const Extent &x) {
18  return x.empty() ? AddressInterval() : AddressInterval::hull(x.first(), x.last());
19 }
20 
21 ExtentMap toExtentMap(const AddressIntervalSet &x) {
22  ExtentMap retval;
23  BOOST_FOREACH (const AddressInterval &interval, x.intervals())
24  retval.insert(toExtent(interval));
25  return retval;
26 }
27 
28 AddressIntervalSet toAddressIntervalSet(const ExtentMap &x) {
29  AddressIntervalSet retval;
30  for (ExtentMap::const_iterator iter=x.begin(); iter!=x.end(); ++iter)
31  retval.insert(toAddressInterval(iter->first));
32  return retval;
33 }
34 
35 std::ostream& operator<<(std::ostream &out, const AddressInterval &x) {
36  if (x.isEmpty()) {
37  out <<"empty";
38  } else if (x.isSingleton()) {
40  } else {
41  out <<"[" <<StringUtility::addrToString(x.least()) <<"," <<StringUtility::addrToString(x.greatest()) <<"]";
42  }
43  return out;
44 }
45 
46 std::ostream& operator<<(std::ostream &out, const AddressIntervalSet &x) {
47  out <<"{";
48  BOOST_FOREACH (const AddressInterval &interval, x.intervals())
49  out <<" " <<interval;
50  out <<" }";
51  return out;
52 }
53 
63 char
64 ExtentMap::category(const Extent &a, const Extent &b)
65 {
66  if (a.relaxed_first()==b.relaxed_first() && a.size()==b.size())
67  return 'C';
68  if (a.relaxed_first()+a.size() <= b.relaxed_first())
69  return 'L';
70  if (a.relaxed_first() >= b.relaxed_first()+b.size())
71  return 'R';
72  if (a.relaxed_first() <= b.relaxed_first() && a.relaxed_first()+a.size() >= b.relaxed_first()+b.size())
73  return 'O';
74  if (a.relaxed_first() >= b.relaxed_first() && a.relaxed_first()+a.size() <= b.relaxed_first()+b.size())
75  return 'I';
76  if (a.relaxed_first() <= b.relaxed_first()) /*already know a.first+a.size > b.first*/
77  return 'B';
78  return 'E';
79 }
80 
82 Extent
84 {
85  iterator found = best_fit(size, begin());
86  if (found==end())
87  throw std::bad_alloc();
88  Extent retval(found->first.first(), size);
89  erase(retval);
90  return retval;
91 }
92 
94 Extent
96 {
97  iterator found = first_fit(size, begin());
98  if (found==end())
99  throw std::bad_alloc();
100  Extent retval(found->first.first(), size);
101  erase(retval);
102  return retval;
103 }
104 
106 void
108 {
109  ROSE_ASSERT(subtract_from(request).size()==0); /*entire request should be on free list*/
110  erase(request);
111 }
112 
113 #if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */
114 
117 void
118 ExtentMap::precipitate(rose_addr_t reagent)
119 {
120  abort(); // NOT IMPLEMENTED
121  ExtentMap result;
122  for (iterator i=begin(); i!=end(); /*void*/) {
123  ExtentPair left = *i++;
124  for (/*void*/; i!=end() && left.first+left.second+reagent >= i->first; i++)
125  left.second = (i->first + i->second) - left.first;
126  result.insert(left);
127  }
128  *this = result;
129 }
130 #endif
131 
132 #if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */
133 
134 ExtentPair
135 ExtentMap::find_address(rose_addr_t addr) const
136 {
137  const_iterator i = upper_bound(addr);
138  RangeMapType::const_iterator i2 = ranges.find(addr);
139  if (i==begin()) {
140  assert(i2==ranges.end());
141  throw std::bad_alloc();
142  }
143  --i;
144  if (i->first+i->second <= addr) {
145  assert(i2==ranges.end());
146  throw std::bad_alloc();
147  }
148 
149  assert(i->first==i2->first.begin);
150  assert(i->second==i2->first.size);
151  return *i;
152 }
153 #endif
154 
155 #if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */
156 
158 bool
159 ExtentMap::exists_all(ExtentPair what) const
160 {
161  while (what.second>0) {
162  try {
163  ExtentPair found = find_address(what.first);
164  assert(found.second > 0);
165  assert(found.first <= what.first);
166  assert(what.first <= found.first + found.second);
167  rose_addr_t nfound = std::min(what.second, found.second-(what.first-found.first));
168  what.first = found.first + found.second;
169  what.second -= nfound;
170  } catch (const std::bad_alloc&) { // thrown by find_address()
171  assert(!ranges.contains(RangeType(what.first, what.second)));
172  return false;
173  }
174  }
175  assert(ranges.contains(RangeType(what.first, what.second)));
176  return true;
177 }
178 #endif
179 
180 void
181 ExtentMap::dump_extents(std::ostream &o, const std::string &prefix, const std::string &label) const
182 {
183  using namespace StringUtility;
184  size_t idx=0;
185  for (const_iterator i=begin(); i!=end(); ++i, ++idx) {
186  o <<prefix <<(label.empty()?std::string("Extent"):label) <<"[" <<idx <<"]"
187  <<" = offset " <<unsignedToHex(i->first.first())
188  <<" for " <<unsignedToHex(i->first.size()) <<(1==i->first.size()?" byte":" bytes")
189  <<" ending at " <<unsignedToHex(i->first.first() + i->first.size()) <<"\n";
190  }
191 }
192 
193 
195 void
196 ExtentMap::dump_extents(FILE *f, const char *prefix, const char *label, bool pad) const
197 {
198  char p[4096];
199  size_t idx=0;
200  for (const_iterator i=begin(); i!=end(); ++i, ++idx) {
201  if (!label) label = "Extent";
202  sprintf(p, "%s%s[%zd]", prefix, label, idx);
203  int w = pad ? std::max(1, DUMP_FIELD_WIDTH-(int)strlen(p)) : 1;
204  fprintf(f, "%s%-*s = offset 0x%08" PRIx64 " (%" PRIu64 "),"
205  " for 0x%08" PRIx64 " (%" PRIu64 ") byte%s,"
206  " ending at 0x%08" PRIx64 " (%" PRIu64 ")\n",
207  p, w, "", i->first.first(), i->first.first(),
208  i->first.size(), i->first.size(), 1==i->first.size()?"":"s",
209  i->first.first()+i->first.size(), i->first.first()+i->first.size());
210  }
211 }
212 
213 #endif
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:197
Extent allocate_first_fit(const rose_addr_t size)
Allocate an extent of the specified size (first fit) from the extent map, removing the returned exten...
Definition: ExtentMap.C:95
A contiguous range of values.
Definition: rangemap.h:50
bool isSingleton() const
True if interval is a singleton.
Definition: Interval.h:200
Main namespace for the ROSE library.
Value relaxed_first() const
Accessor for the first value of a range.
Definition: rangemap.h:115
void allocate_at(const Extent &request)
Allocate the specified extent, which must be in the free list.
Definition: ExtentMap.C:107
void insert(const Interval2 &interval)
Insert specified values.
Definition: IntervalSet.h:532
static char category(const Extent &a, const Extent &b)
Class method comparing two extents.
Definition: ExtentMap.C:64
iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true)
Insert a range/value pair into the map.
Definition: rangemap.h:1192
T least() const
Returns lower limit.
Definition: Interval.h:185
ROSE_UTIL_API std::string addrToString(uint64_t value, size_t nbits=0)
Convert a virtual address to a string.
iterator begin()
First-item iterator.
Definition: rangemap.h:905
Value size() const
Returns the number of values represented by the range.
Definition: rangemap.h:147
bool empty() const
Returns true if this range is empty.
Definition: rangemap.h:249
iterator end()
End-item iterator.
Definition: rangemap.h:917
std::string unsignedToHex(T value)
Convert a number to a hexadecimal and decimal string.
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterator range for all intervals actually stored by this set.
Definition: IntervalSet.h:225
Extent allocate_best_fit(const rose_addr_t size)
Allocate an extent of the specified size (best fit first) from the extent map, removing the returned ...
Definition: ExtentMap.C:83
T greatest() const
Returns upper limit.
Definition: Interval.h:191