Adding some debugging stuff
[dyninst.git] / paradyn / src / PCthread / PCsearch.C
1 /*
2  * Copyright (c) 1996 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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 /*
43  * PCsearch.C
44  * 
45  * class PCsearch
46  *
47  * $Log: PCsearch.C,v $
48  * Revision 1.25  1997/03/29 02:05:04  sec
49  * Adding some debugging stuff
50  *
51  * Revision 1.24  1997/03/16 23:17:46  lzheng
52  * Changes made for the value of observed cost
53  *
54  * Revision 1.23  1997/02/06 20:47:52  karavan
55  * changed MaxActiveExperiments constant to guard against deadlock.
56  *
57  * Revision 1.22  1996/08/16 21:03:41  tamches
58  * updated copyright for release 1.1
59  *
60  * Revision 1.21  1996/07/26 18:02:37  karavan
61  * added display of status if search throttled back.
62  *
63  * Revision 1.20  1996/07/24 20:10:37  karavan
64  * Fixed error in numActiveExperiments calculation; numActiveCurrentExperiments
65  * now zero'd at phase boundary.
66  *
67  * Revision 1.19  1996/07/23 20:28:05  karavan
68  * second part of two-part commit.
69  *
70  * implements new search strategy which retests false nodes under certain
71  * circumstances.
72  *
73  * change in handling of high-cost nodes blocking the ready queue.
74  *
75  * code cleanup.
76  *
77  * Revision 1.18  1996/07/22 18:55:44  karavan
78  * part one of two-part commit for new PC functionality of restarting searches.
79  *
80  * Revision 1.17  1996/05/16 06:58:37  karavan
81  * increased max num experiments and also min time to conclusion.
82  *
83  * Revision 1.16  1996/05/15 04:35:17  karavan
84  * bug fixes: changed pendingCost pendingSearches and numexperiments to
85  * break down by phase type, so starting a new current phase updates these
86  * totals correctly; fixed error in estimated cost propagation.
87  *
88  * Revision 1.15  1996/05/11 01:58:03  karavan
89  * fixed bug in PendingCost calculation.
90  *
91  * Revision 1.14  1996/05/08 07:35:26  karavan
92  * Changed enable data calls to be fully asynchronous within the performance consultant.
93  *
94  * some changes to cost handling, with additional limit on number of outstanding enable requests.
95  *
96  */
97
98 #include "PCintern.h"
99 #include "PCsearch.h"
100 #include "PCfilter.h"
101 #include "PCshg.h"
102 #include "PCmetric.h"
103
104 #include <iostream.h>
105 #include <fstream.h>
106
107 // for debugging purposes
108 #ifdef MYPCDEBUG
109 extern double TESTgetTime();
110 #endif
111
112 extern void initPChypos();
113 extern void initPCmetrics();
114 extern sampleValue DivideEval (focus, sampleValue *data, int dataSize);
115
116 unsigned int PCunhash (const unsigned &val) {return (val >> 3);} 
117
118 unsigned PCsearch::PCactiveCurrentPhase = 0;  // init to undefined
119 dictionary_hash<unsigned, PCsearch*> PCsearch::AllPCSearches(PCunhash);
120 PriorityQueue<SearchQKey, searchHistoryNode*> PCsearch::GlobalSearchQueue;
121 PriorityQueue<SearchQKey, searchHistoryNode*> PCsearch::CurrentSearchQueue;
122 PriorityQueue<SearchQKey, searchHistoryNode*> *PCsearch::q = &PCsearch::GlobalSearchQueue;
123 int PCsearch::numActiveGlobalExperiments = 0;
124 int PCsearch::numActiveCurrentExperiments = 0;
125 bool PCsearch::GlobalSearchPaused = false;
126 bool PCsearch::CurrentSearchPaused = false;
127 costModule *PCsearch::costTracker = NULL;
128 float PCsearch::PendingCurrentCost = 0.0;
129 float PCsearch::PendingGlobalCost = 0.0;
130 int PCsearch::PendingGlobalSearches = 0;
131 int PCsearch::PendingCurrentSearches = 0;
132 bool PCsearch::SearchThrottledBack = false;
133 searchHistoryNode *PCsearch::SearchThrottleNode = NULL;
134
135 //** this is currently being studied!! (klk)
136 const float costFudge = 0.1;
137 const int MaxPendingSearches = 30;
138 const int MaxActiveExperiments = 100;
139 //
140 // remove from search queues and start up as many experiments as we can 
141 // without exceeding our cost limit.  
142 //
143 void 
144 PCsearch::expandSearch (sampleValue estimatedCost)
145 {
146   bool costLimitReached = false;
147   searchHistoryNode *curr;
148   float candidateCost = 0.0;
149
150 #ifdef PCDEBUG
151   cout << "START OF EXPAND" << endl;
152   cout << "Global Qsize: " << GlobalSearchQueue.size() << 
153     " Current Qsize: " << CurrentSearchQueue.size() << endl;
154 #endif
155
156   // alternate between two queues for fairness
157   while (!costLimitReached 
158          && (PCsearch::getNumPendingSearches() < MaxPendingSearches)
159          && (PCsearch::getNumActiveExperiments() < MaxActiveExperiments)) {
160     // switch queues for fairness, if possible; never use q if empty or that 
161     // search is paused
162     if (q == &CurrentSearchQueue) {
163         if ( !(GlobalSearchQueue.empty() || GlobalSearchPaused))
164           q = &GlobalSearchQueue;
165         else
166           if (q->empty() || CurrentSearchPaused) 
167             // no queue is ready
168             break;
169     } else {
170       if ( !(CurrentSearchQueue.empty() || CurrentSearchPaused)) 
171         q = &CurrentSearchQueue;
172       else
173         if (q->empty() || GlobalSearchPaused) 
174           // no queue is ready 
175           break;
176     }
177     curr = q->peek_first_data();
178     candidateCost = curr->getEstimatedCost();
179 #ifdef PCDEBUG
180     cout << " considering node with cost: " << candidateCost
181          << " name = " << curr->getHypoName() << endl;
182 //    cout << " considering node with cost: " << candidateCost << endl;
183 #endif
184     sampleValue predMax = performanceConsultant::predictedCostLimit;
185     if (1/(1-candidateCost) > predMax) {
186       // **for now just get it out of the way
187       int dispToken = curr->getGuiToken();
188       q->delete_first();
189       string *ds = new string 
190         ("WARNING:  Predicted Node Search Code exceeds limit.  Skipped Node:\n\t");
191       *ds += curr->getShortName();
192       *ds += "||";
193       *ds += curr->getHypoName();
194       *ds += "\n";
195       uiMgr->updateStatusDisplay(dispToken, ds);
196     } else if ((1 / (1 - estimatedCost - candidateCost - 
197                      PCsearch::getPendingCost())) > predMax) {
198       costLimitReached = true;
199       // print status to display but just once per blockage
200       if ( !PCsearch::SearchThrottledBack && 
201           (curr != PCsearch::SearchThrottleNode)) {
202         int dispToken = curr->getGuiToken();
203         string *ds = new string ("Search Slowed:  Cost Limit Reached.\n");
204         uiMgr->updateStatusDisplay(dispToken, ds);
205         PCsearch::SearchThrottleNode = curr;
206         PCsearch::SearchThrottledBack = true;
207       }
208     } else {
209       curr->startExperiment();
210       if (PCsearch::SearchThrottledBack) {
211         int dispToken = curr->getGuiToken();
212         string *ds = new string ("Search Resumed.\n");
213         uiMgr->updateStatusDisplay(dispToken, ds);
214         PCsearch::SearchThrottledBack = false;
215         PCsearch::SearchThrottleNode = NULL;
216       }
217       if (q == &GlobalSearchQueue) {
218         PCsearch::PendingGlobalSearches += 1;
219         PCsearch::PendingGlobalCost += candidateCost;
220       } else {
221         PCsearch::PendingCurrentSearches += 1;
222         PCsearch::PendingCurrentCost += candidateCost;
223       }
224       q->delete_first();
225     }
226   }   
227   if ((PCsearch::getNumActiveExperiments() >=  MaxActiveExperiments) 
228       && (!PCsearch::SearchThrottledBack)) {
229     int dispToken = curr->getGuiToken();
230     string *ds = new string ("Search Slowed:  max active nodes reached.\n");
231     uiMgr->updateStatusDisplay(dispToken, ds);
232     PCsearch::SearchThrottledBack = true;
233   } else if ((PCsearch::getNumPendingSearches() >=  MaxPendingSearches)
234              && (!PCsearch::SearchThrottledBack)) {
235     int dispToken = curr->getGuiToken();
236     string *ds = new string ("Search Slowed:  max pending nodes.\n");
237     uiMgr->updateStatusDisplay(dispToken, ds);
238     PCsearch::SearchThrottledBack = true;
239   }
240 #ifdef PCDEBUG
241   cout << "END OF EXPAND" << endl;
242   cout << "cost limit: " << performanceConsultant::predictedCostLimit << endl;
243   cout << "total observed cost: " << estimatedCost << 
244     "/" << (1-costFudge)*performanceConsultant::predictedCostLimit << endl;
245   cout << "numActiveExperiments: " << PCsearch::getNumActiveExperiments() << endl;
246   cout << "pendingEnables: " << PCsearch::getNumPendingSearches() << endl;
247   cout << "pendingCost = " << PCsearch::getPendingCost() << endl;
248 #endif
249 }
250
251 PCsearch::PCsearch(unsigned phaseID, phaseType phase_type)
252 : searchStatus(schNeverRun),  phaseToken(phaseID), phType(phase_type)
253 {
254   if (phaseID == GlobalPhaseID)
255     database = performanceConsultant::globalPCMetricServer;
256   else 
257     database = new PCmetricInstServer(phaseID);  
258   shg = new searchHistoryGraph (this, phaseID);
259 }
260
261 PCsearch::~PCsearch()
262 {
263   delete database;
264   delete shg;
265 }
266
267 void 
268 PCsearch::initCostTracker () 
269 {
270   bool err = true;
271   PCmetric *pcm;
272   assert (PCmetric::AllPCmetrics.defines("normSmoothCost"));
273
274   pcm = PCmetric::AllPCmetrics ["normSmoothCost"];
275   PCsearch::costTracker = new costModule;
276   PCmetricInstServer *miserve = new PCmetricInstServer (GlobalPhase);
277   costTracker->costFilter = 
278     miserve->createPcmi(pcm, topLevelFocus, &err);
279   assert(costTracker->costFilter);
280   costTracker->costFilter->addSubscription(costTracker);
281 }
282
283 bool
284 PCsearch::addSearch(unsigned phaseID)
285 {
286   string *msg;
287   phaseType pType;
288   // we can't use the dm token really, cause there's no dm token for 
289   // global search, which throws our part of the universe into total 
290   // confusion.  So, internally and in communication with the UI, we always
291   // use dm's number plus one, and 0 for global phase.  
292   if (phaseID > 0) {
293     // non-global search
294     performanceConsultant::currentPhase = phaseID;
295     msg = new string ("Initializing Search for Current Phase ");
296     *msg += (phaseID-1);
297     *msg += string(".\n");
298     pType = CurrentPhase;
299   } else {
300     msg =  new string ("Initializing Search for Global Phase.\n");
301     pType = GlobalPhase;
302   }
303
304   // if this is first search, initialize all PC metrics and hypotheses
305   if (!performanceConsultant::PChyposDefined) {
306     initPCmetrics();
307     initPChypos();
308     performanceConsultant::PChyposDefined = true;
309     initCostTracker();
310   }
311
312   PCsearch *newkid = new PCsearch(phaseID , pType);
313   AllPCSearches[phaseID] = newkid;
314
315   // * initialize PC displays *
316   newkid->updateDisplayedStatus(msg);
317
318   // display root node with style 1 
319   uiMgr->DAGaddNode (phaseID, 0, searchHistoryGraph::InactiveUnknownNodeStyle, 
320                      "TopLevelHypothesis", 
321                      "TopLevelHypothesis", 1);
322   return true;
323 }
324   
325 //
326 // start instrumentation requests for the first time 
327 //
328 void
329 PCsearch::startSearching()
330 {
331   shg->initPersistentNodes();
332   searchStatus = schRunning;
333 }
334
335 //
336 // to pause a search we disable all instrumentation requests
337 //
338 void 
339 PCsearch::pause() 
340 {     
341   if (searchStatus == schRunning) {
342     searchStatus = schPaused;
343     if (phType == GlobalPhase) 
344       // no nodes will be started off the global search queue until false
345       GlobalSearchPaused = true;
346     else 
347       // no nodes will be started off the current search queue until false
348       CurrentSearchPaused = true;
349     shg->updateDisplayedStatus ("Search Paused by User.\n");
350     database->unsubscribeAllRawData();
351   }
352 }
353
354 void 
355 PCsearch::resume() 
356 {
357   if (searchStatus == schPaused) {
358     searchStatus = schRunning;
359     if (phType == GlobalPhase)
360       GlobalSearchPaused = false;
361     else
362       CurrentSearchPaused = false;
363     database->resubscribeAllRawData();
364     shg->updateDisplayedStatus ("Search Resumed.\n");
365   }
366 }
367
368 //
369 // this permanently ends a search, it can never be restarted
370 //
371 void 
372 PCsearch::terminate(timeStamp searchEndTime) {
373   searchStatus = schEnded;
374   // need to flush search nodes for this defunct search from the queue
375   if (phType == CurrentPhase) {
376     while (!PCsearch::CurrentSearchQueue.empty()) {
377       CurrentSearchQueue.delete_first();
378     }
379     PCsearch::PendingCurrentCost = 0;
380     PCsearch::PendingCurrentSearches = 0;
381     PCsearch::numActiveCurrentExperiments = 0;
382   } else {
383     while (!PCsearch::GlobalSearchQueue.empty()) {
384       GlobalSearchQueue.delete_first();
385     }
386     PCsearch::PendingGlobalCost = 0;
387     PCsearch::PendingGlobalSearches = 0;
388     PCsearch::numActiveGlobalExperiments = 0;
389   }
390   shg->finalizeSearch(searchEndTime);
391 }
392
393 void 
394 PCsearch::updateCurrentPhase (unsigned newPhaseID, timeStamp phaseEndTime) 
395 {
396   unsigned phaseID = performanceConsultant::currentPhase;
397   // the UI may be notified of the new phase, and the user select a 
398   // search for it, before the PC gets this callback from the DM.  So
399   // we must check here if we are already searching this "new" phase.
400   if (phaseID == newPhaseID) return;
401   // here if this is the first we're hearing of this phase.  If a search
402   // is in progress for the old current phase, we need to end it.
403   if (phaseID && AllPCSearches.defines(phaseID) ) {
404     // this one's done for good
405     AllPCSearches[phaseID]->terminate(phaseEndTime); 
406   }
407   // 0 indicates no current phase search in progress
408   performanceConsultant::currentPhase = 0;
409   PCsearch::numActiveCurrentExperiments = 0;
410 }
411
412 bool 
413 PCsearch::getNodeInfo(int nodeID, shg_node_info *theInfo)
414 {
415   searchHistoryNode *const currNode = shg->getNode(nodeID);
416   if (! currNode)
417     return false;
418
419   currNode->getInfo (theInfo);
420   return true;
421 }
422
423 PCsearch *
424 PCsearch::findSearch (phaseType pt)
425 {
426   if (pt == GlobalPhase) 
427     return PCsearch::AllPCSearches[0];
428   else {
429     if (performanceConsultant::currentPhase && 
430         PCsearch::AllPCSearches.defines(performanceConsultant::currentPhase))
431       return PCsearch::AllPCSearches[performanceConsultant::currentPhase];
432     else
433       return (PCsearch *)NULL;
434   }
435 }