Update copyright to LGPL on all files
[dyninst.git] / stackwalk / src / steppergroup.C
1 /*
2  * Copyright (c) 1996-2009 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 = %p)\n", __FILE__, __LINE__, addr, last_tried);
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 %p at address %lx\n",
111                  __FILE__, __LINE__, out, 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 %p at address %lx\n",
131               __FILE__, __LINE__, out, 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: %p, %lx, %lx\n",
143                 __FILE__, __LINE__, stepper, start, end);
144       setLastError(err_badparam, "Invalid parameters");
145       return false;
146    }
147
148    steppers.insert(stepper);
149    sw_printf("[%s:%u] - Adding stepper %p to address ranges %lx -> %lx\n",
150               __FILE__, __LINE__, stepper, 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 }
246
247 void StepperGroup::getSteppers(std::set<FrameStepper *> &steps)
248 {
249   steps = steppers;
250 }