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