ROSE  0.9.9.139
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 
6 #include "sage3basic.h"
7 #include <boost/foreach.hpp>
8 
9 using namespace Rose;
10 
11 Extent toExtent(const AddressInterval &x) {
12  return x.isEmpty() ? Extent() : Extent::inin(x.least(), x.greatest());
13 }
14 
15 AddressInterval toAddressInterval(const Extent &x) {
16  return x.empty() ? AddressInterval() : AddressInterval::hull(x.first(), x.last());
17 }
18 
19 ExtentMap toExtentMap(const AddressIntervalSet &x) {
20  ExtentMap retval;
21  BOOST_FOREACH (const AddressInterval &interval, x.intervals())
22  retval.insert(toExtent(interval));
23  return retval;
24 }
25 
26 AddressIntervalSet toAddressIntervalSet(const ExtentMap &x) {
27  AddressIntervalSet retval;
28  for (ExtentMap::const_iterator iter=x.begin(); iter!=x.end(); ++iter)
29  retval.insert(toAddressInterval(iter->first));
30  return retval;
31 }
32 
33 std::ostream& operator<<(std::ostream &out, const AddressInterval &x) {
34  if (x.isEmpty()) {
35  out <<"empty";
36  } else if (x.isSingleton()) {
38  } else {
39  out <<"[" <<StringUtility::addrToString(x.least()) <<"," <<StringUtility::addrToString(x.greatest()) <<"]";
40  }
41  return out;
42 }
43 
44 std::ostream& operator<<(std::ostream &out, const AddressIntervalSet &x) {
45  out <<"{";
46  BOOST_FOREACH (const AddressInterval &interval, x.intervals())
47  out <<" " <<interval;
48  out <<" }";
49  return out;
50 }
51 
61 char
62 ExtentMap::category(const Extent &a, const Extent &b)
63 {
64  if (a.relaxed_first()==b.relaxed_first() && a.size()==b.size())
65  return 'C';
66  if (a.relaxed_first()+a.size() <= b.relaxed_first())
67  return 'L';
68  if (a.relaxed_first() >= b.relaxed_first()+b.size())
69  return 'R';
70  if (a.relaxed_first() <= b.relaxed_first() && a.relaxed_first()+a.size() >= b.relaxed_first()+b.size())
71  return 'O';
72  if (a.relaxed_first() >= b.relaxed_first() && a.relaxed_first()+a.size() <= b.relaxed_first()+b.size())
73  return 'I';
74  if (a.relaxed_first() <= b.relaxed_first()) /*already know a.first+a.size > b.first*/
75  return 'B';
76  return 'E';
77 }
78 
80 Extent
82 {
83  iterator found = best_fit(size, begin());
84  if (found==end())
85  throw std::bad_alloc();
86  Extent retval(found->first.first(), size);
87  erase(retval);
88  return retval;
89 }
90 
92 Extent
94 {
95  iterator found = first_fit(size, begin());
96  if (found==end())
97  throw std::bad_alloc();
98  Extent retval(found->first.first(), size);
99  erase(retval);
100  return retval;
101 }
102 
104 void
106 {
107  ROSE_ASSERT(subtract_from(request).size()==0); /*entire request should be on free list*/
108  erase(request);
109 }
110 
111 #if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */
112 
115 void
116 ExtentMap::precipitate(rose_addr_t reagent)
117 {
118  abort(); // NOT IMPLEMENTED
119  ExtentMap result;
120  for (iterator i=begin(); i!=end(); /*void*/) {
121  ExtentPair left = *i++;
122  for (/*void*/; i!=end() && left.first+left.second+reagent >= i->first; i++)
123  left.second = (i->first + i->second) - left.first;
124  result.insert(left);
125  }
126  *this = result;
127 }
128 #endif
129 
130 #if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */
131 
132 ExtentPair
133 ExtentMap::find_address(rose_addr_t addr) const
134 {
135  const_iterator i = upper_bound(addr);
136  RangeMapType::const_iterator i2 = ranges.find(addr);
137  if (i==begin()) {
138  assert(i2==ranges.end());
139  throw std::bad_alloc();
140  }
141  --i;
142  if (i->first+i->second <= addr) {
143  assert(i2==ranges.end());
144  throw std::bad_alloc();
145  }
146 
147  assert(i->first==i2->first.begin);
148  assert(i->second==i2->first.size);
149  return *i;
150 }
151 #endif
152 
153 #if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */
154 
156 bool
157 ExtentMap::exists_all(ExtentPair what) const
158 {
159  while (what.second>0) {
160  try {
161  ExtentPair found = find_address(what.first);
162  assert(found.second > 0);
163  assert(found.first <= what.first);
164  assert(what.first <= found.first + found.second);
165  rose_addr_t nfound = std::min(what.second, found.second-(what.first-found.first));
166  what.first = found.first + found.second;
167  what.second -= nfound;
168  } catch (const std::bad_alloc&) { // thrown by find_address()
169  assert(!ranges.contains(RangeType(what.first, what.second)));
170  return false;
171  }
172  }
173  assert(ranges.contains(RangeType(what.first, what.second)));
174  return true;
175 }
176 #endif
177 
178 void
179 ExtentMap::dump_extents(std::ostream &o, const std::string &prefix, const std::string &label) const
180 {
181  using namespace StringUtility;
182  size_t idx=0;
183  for (const_iterator i=begin(); i!=end(); ++i, ++idx) {
184  o <<prefix <<(label.empty()?std::string("Extent"):label) <<"[" <<idx <<"]"
185  <<" = offset " <<unsignedToHex(i->first.first())
186  <<" for " <<unsignedToHex(i->first.size()) <<(1==i->first.size()?" byte":" bytes")
187  <<" ending at " <<unsignedToHex(i->first.first() + i->first.size()) <<"\n";
188  }
189 }
190 
191 
193 void
194 ExtentMap::dump_extents(FILE *f, const char *prefix, const char *label, bool pad) const
195 {
196  char p[4096];
197  size_t idx=0;
198  for (const_iterator i=begin(); i!=end(); ++i, ++idx) {
199  if (!label) label = "Extent";
200  sprintf(p, "%s%s[%zd]", prefix, label, idx);
201  int w = pad ? std::max(1, DUMP_FIELD_WIDTH-(int)strlen(p)) : 1;
202  fprintf(f, "%s%-*s = offset 0x%08" PRIx64 " (%" PRIu64 "),"
203  " for 0x%08" PRIx64 " (%" PRIu64 ") byte%s,"
204  " ending at 0x%08" PRIx64 " (%" PRIu64 ")\n",
205  p, w, "", i->first.first(), i->first.first(),
206  i->first.size(), i->first.size(), 1==i->first.size()?"":"s",
207  i->first.first()+i->first.size(), i->first.first()+i->first.size());
208  }
209 }
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:93
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:105
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:62
iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true)
Insert a range/value pair into the map.
Definition: rangemap.h:1193
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:906
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:918
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:81
T greatest() const
Returns upper limit.
Definition: Interval.h:191