Updated READMEs
[dyninst.git] / stackwalk / src / steppergroup.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #include "stackwalk/h/steppergroup.h"
32 #include "stackwalk/h/framestepper.h"
33 #include "stackwalk/h/swk_errors.h"
34 #include "stackwalk/src/sw.h"
35
36 using namespace Dyninst;
37 using namespace Dyninst::Stackwalker;
38 using namespace std;
39
40 StepperGroup::StepperGroup(Walker *new_walker) :
41     walker(new_walker)
42 {
43     assert(walker);
44 }
45
46 StepperGroup::~StepperGroup() 
47 {
48 }
49
50 Walker *StepperGroup::getWalker() const 
51 {
52     assert(walker);
53     return walker;
54 }
55
56 void StepperGroup::newLibraryNotification(LibAddrPair *libaddr,
57                                           lib_change_t change)
58 {
59    std::set<FrameStepper *>::iterator i = steppers.begin();
60    for (; i != steppers.end(); i++)
61    {
62       (*i)->newLibraryNotification(libaddr, change);
63    }
64 }
65
66 void StepperGroup::registerStepper(FrameStepper *stepper)
67 {
68    steppers.insert(stepper);
69    stepper->registerStepperGroup(this);
70 }
71
72 class Dyninst::Stackwalker::AddrRangeGroupImpl
73 {
74 public:
75    addrRangeTree<addrRange> range_map;
76 };
77
78
79 AddrRangeGroup::AddrRangeGroup(Walker *new_walker) :
80    StepperGroup(new_walker)
81 {
82    sw_printf("[%s:%u] - Constructing new AddrRangeGroup at %p\n",
83               FILE__, __LINE__, this);
84    impl = new AddrRangeGroupImpl();
85 }
86
87 bool AddrRangeGroup::findStepperForAddr(Address addr, FrameStepper* &out, 
88                                         const FrameStepper *last_tried)
89 {
90    addrRange *range;
91    sw_printf("[%s:%u] - AddrRangeGroup trying to find stepper at %lx " 
92              "(last_tried = %s)\n", FILE__, __LINE__, addr, 
93              last_tried ? last_tried->getName() : "<NONE>");
94
95    bool result = impl->range_map.find(addr, range);
96     if (!result) {
97       sw_printf("[%s:%u] - Couldn't find a FrameStepper at %lx\n",
98                  FILE__, __LINE__, addr);
99       setLastError(err_nostepper, "No FrameStepper found at the given address");
100         return false;
101     }
102
103    AddrRangeStepper *stepper_set = dynamic_cast<AddrRangeStepper*>(range);
104    assert(stepper_set);
105
106    if (!last_tried) {
107       assert(stepper_set->steppers.size());
108       StepperSet::iterator iter = stepper_set->steppers.begin();
109       out = *(iter);
110       sw_printf("[%s:%u] - Found FrameStepper %s at address %lx\n",
111                 FILE__, __LINE__, out->getName(), addr);
112       return true;
113     }
114
115    FrameStepper *last_tried_nc = const_cast<FrameStepper *>(last_tried);
116    StepperSet::iterator iter = stepper_set->steppers.find(last_tried_nc);
117    if (iter == stepper_set->steppers.end()) {
118       setLastError(err_badparam, "last_tried points to an invalid FrameStepper");
119       return false;
120    }
121
122    iter++;
123    if (iter == stepper_set->steppers.end()) {
124       setLastError(err_nostepper, "No FrameStepper was able to walk through " 
125                    "the given address");
126       return false;
127    }
128     
129    out = *iter;
130    sw_printf("[%s:%u] - Found FrameStepper %s at address %lx\n",
131              FILE__, __LINE__, out->getName(), addr);
132    return true;
133 }
134
135 bool AddrRangeGroup::addStepper(FrameStepper *stepper, Address start, Address end)
136 {
137    std::vector<addrRange *> ranges;
138    bool result = impl->range_map.find(start, end, ranges);
139
140    if (!stepper || end <= start)
141    {
142       sw_printf("[%s:%u] - addStepper called with bad params: %s, %lx, %lx\n",
143                 FILE__, __LINE__, stepper->getName(), start, end);
144       setLastError(err_badparam, "Invalid parameters");
145       return false;
146    }
147
148    steppers.insert(stepper);
149    sw_printf("[%s:%u] - Adding stepper %s to address ranges %lx -> %lx\n",
150              FILE__, __LINE__, stepper->getName(), start, end);
151    if (!result) {
152       //We don't have anything that overlaps.  Just add the stepper.
153       AddrRangeStepper *new_range = new AddrRangeStepper(start, end);
154       new_range->steppers.insert(stepper);
155       impl->range_map.insert(new_range);
156       return true;
157    }
158    assert(ranges.size());
159
160    Address cur = start;
161    unsigned i = 0;
162    while (cur < end)
163    {
164       if (i >= ranges.size())
165       {
166          //We have an empty space in the address range starting at cur and
167          //ending at end, fill it in with one range that fills the empty 
168          //space and only contains the new stepper
169          AddrRangeStepper *new_range = new AddrRangeStepper(cur, end);
170          new_range->steppers.insert(stepper);
171          impl->range_map.insert(new_range);
172          cur = end;
173          continue;         
174       }
175       if (cur < ranges[i]->get_address()) {
176          //We have an empty space in the address range starting at cur and
177          //ending at ranges[i]->get_address(), fill it in with one range 
178          // that fills the empty space and only contains the new stepper
179          AddrRangeStepper *new_range;
180          new_range = new AddrRangeStepper(cur, ranges[i]->get_address());
181          new_range->steppers.insert(stepper);
182          impl->range_map.insert(new_range);
183          cur = ranges[i]->get_address();
184          continue;
185       }
186       if (cur > ranges[i]->get_address())
187       {
188          //Ranges[i] starts before cur.  We'll shorten ranges[i] to start and
189          // add a new range with the same stepper set as ranges[i] to 
190          // (start, ranges[i]->end].  This should only happen on the first time 
191          // through this loop.
192          assert(i == 0 && cur == start);
193          AddrRangeStepper *old_range = dynamic_cast<AddrRangeStepper*>(ranges[i]);
194          Address old_end = old_range->end;
195          old_range->end = start;
196
197          AddrRangeStepper *new_range = new AddrRangeStepper(start, old_end);
198          new_range->steppers = old_range->steppers;
199          impl->range_map.insert(new_range);
200          
201          //We'll cheat.  We should add the new_range into our ranges
202          // vector and operate on it during the next loop iteration.
203          // However, we're done with ranges[i], so let's just override
204          // it with new_range and not bother incrementing i.
205          ranges[i] = new_range;
206          continue;
207       }
208       assert(cur == ranges[i]->get_address());
209       if (ranges[i]->get_address() + ranges[i]->get_size() < end)
210       {
211          //Ranges[i] is contained within the total range.  No need
212          // to add new things or resize, we'll just add stepper to its set.
213          AddrRangeStepper *ars = dynamic_cast<AddrRangeStepper*>(ranges[i]);
214          ars->steppers.insert(stepper);
215          cur = ranges[i]->get_address() + ranges[i]->get_size();
216          i++;
217          continue;
218       }
219
220       if (ranges[i]->get_address() + ranges[i]->get_size() >= end)
221       {
222          //Ranges[i] overflows past end.  We'll break it into two parts: 
223          // [ranges[i].start, end) and [end, ranges[i].end).  The first range
224          // will get the stepper added to it.  This should only happen on the last case.
225          assert(i == ranges.size() - 1);
226          AddrRangeStepper *old_range = dynamic_cast<AddrRangeStepper*>(ranges[i]);
227          Address old_end = old_range->end;
228          old_range->end = end;
229          
230          AddrRangeStepper *new_range = new AddrRangeStepper(end, old_end);
231          new_range->steppers = old_range->steppers;
232          impl->range_map.insert(new_range);
233
234          old_range->steppers.insert(stepper);
235          cur = end;
236          continue;
237       }
238       assert(0);
239    }
240    return true;
241 }
242
243 AddrRangeGroup::~AddrRangeGroup()
244 {
245   delete impl;
246 }
247
248 void StepperGroup::getSteppers(std::set<FrameStepper *> &steps)
249 {
250   steps = steppers;
251 }