1 /*
2 Copyright (C) 2011 SN Systems Ltd. All Rights Reserved.
3 Portions Copyright (C) 2011-2012 David Anderson. All Rights Reserved.
4 Portions Copyright 2012 SN Systems Ltd. All rights reserved.
5
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of version 2 of the GNU General Public License as
8 published by the Free Software Foundation.
9
10 This program is distributed in the hope that it would be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
13
14 Further, this software is distributed without any warranty that it is
15 free of the rightful claim of any third person regarding infringement
16 or the like. Any license provided herein, whether implied or
17 otherwise, applies only to this software file. Patent licenses, if
18 any, provided herein do not apply to combinations of this program with
19 other software, or any other product whatsoever.
20
21 You should have received a copy of the GNU General Public License along
22 with this program; if not, write the Free Software Foundation, Inc., 51
23 Franklin Street - Fifth Floor, Boston MA 02110-1301, USA.
24
25 */
26 /*
27
28 These simple list-processing functions are in support
29 of checking DWARF for compiler-errors of various sorts.
30
31
32 */
33
34 #include "globals.h"
35 #include <assert.h>
36
37 /* Private function */
38 static void DumpFullBucketGroup(Bucket_Group *pBucketGroup);
39 static int FindDataIndexInBucket(Bucket_Group *pBucketGroup,
40 Bucket_Data *pBucketData);
41 static void PrintBucketData(Bucket_Group *pBucketGroup,
42 Bucket_Data *pBucketData);
43 static void ProcessBucketGroup(Bucket_Group *pBucketGroup,
44 void (*pFunction)(Bucket_Group *pBucketGroup,Bucket_Data *pBucketData));
45
46 Bucket_Group *
AllocateBucketGroup(int kind)47 AllocateBucketGroup(int kind)
48 {
49 Bucket_Group *pBucketGroup = (Bucket_Group *)calloc(1,sizeof(Bucket_Group));
50 pBucketGroup->kind = kind;
51 return pBucketGroup;
52 }
53
54 void
ReleaseBucketGroup(Bucket_Group * pBucketGroup)55 ReleaseBucketGroup(Bucket_Group *pBucketGroup)
56 {
57 Bucket *pBucket = 0;
58 Bucket *pNext = 0;
59
60 assert(pBucketGroup);
61 for (pBucket = pBucketGroup->pHead; pBucket; /*pBucket = pBucket->pNext*/) {
62 pNext = pBucket->pNext;
63 free(pBucket);
64 pBucket = pNext;
65 }
66 pBucketGroup->pHead = NULL;
67 pBucketGroup->pTail = NULL;
68 free(pBucketGroup);
69 }
70
71 void
ResetBucketGroup(Bucket_Group * pBucketGroup)72 ResetBucketGroup(Bucket_Group *pBucketGroup)
73 {
74 Bucket *pBucket = 0;
75
76 assert(pBucketGroup);
77 for (pBucket = pBucketGroup->pHead; pBucket; pBucket = pBucket->pNext) {
78 pBucket->nEntries = 0;
79 }
80 ResetSentinelBucketGroup(pBucketGroup);
81 }
82
83 /* Reset sentinels in a Bucket Group. */
84 void
ResetSentinelBucketGroup(Bucket_Group * pBucketGroup)85 ResetSentinelBucketGroup(Bucket_Group *pBucketGroup)
86 {
87 /* Sanity checks */
88 assert(pBucketGroup);
89 pBucketGroup->pFirst = NULL;
90 pBucketGroup->pLast = NULL;
91 }
92
PrintBucketGroup(Bucket_Group * pBucketGroup,Dwarf_Bool bFull)93 void PrintBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Bool bFull)
94 {
95 if (pBucketGroup) {
96 if (bFull) {
97 DumpFullBucketGroup(pBucketGroup);
98 } else {
99 if (pBucketGroup->pFirst && pBucketGroup->pLast) {
100 printf("\nBegin Traversing, First = 0x%08" DW_PR_DUx
101 ", Last = 0x%08" DW_PR_DUx "\n",
102 pBucketGroup->pFirst->key,pBucketGroup->pLast->key);
103 ProcessBucketGroup(pBucketGroup,PrintBucketData);
104 }
105 }
106 }
107 }
108
109 static void
PrintBucketData(Bucket_Group * pBucketGroup,Bucket_Data * pBucketData)110 PrintBucketData(Bucket_Group *pBucketGroup,Bucket_Data *pBucketData)
111 {
112 int nCount = 0;
113 assert(pBucketGroup);
114 assert(pBucketData);
115
116 nCount = FindDataIndexInBucket(pBucketGroup,pBucketData);
117 printf("[%06d] Key = 0x%08" DW_PR_DUx ", Base = 0x%08" DW_PR_DUx
118 ", Low = 0x%08" DW_PR_DUx ", High = 0x%08" DW_PR_DUx
119 ", Flag = %d, Name = '%s'\n",
120 ++nCount,
121 pBucketData->key,
122 pBucketData->base,
123 pBucketData->low,
124 pBucketData->high,
125 pBucketData->bFlag,
126 pBucketData->name);
127 }
128
129 static void
DumpFullBucketGroup(Bucket_Group * pBucketGroup)130 DumpFullBucketGroup(Bucket_Group *pBucketGroup)
131 {
132 int nBucketNo = 1;
133 int nIndex = 0;
134 int nCount = 0;
135 Bucket *pBucket = 0;
136 Bucket_Data *pBucketData = 0;
137
138 assert(pBucketGroup);
139 printf("\nBucket Group at 0x%lx [lower 0x%lx upper 0x%lx]\n",
140 (unsigned long)pBucketGroup,
141 (unsigned long)pBucketGroup->lower,
142 (unsigned long)pBucketGroup->upper);
143 for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries;
144 pBucket = pBucket->pNext) {
145
146 printf("LowPC & HighPC records for bucket %d, at 0x%08lx\n",
147 nBucketNo++,(unsigned long)pBucket);
148 for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
149 pBucketData = &pBucket->Entries[nIndex];
150 printf("[%06d] Key = 0x%08" DW_PR_DUx ", Base = 0x%08" DW_PR_DUx
151 ", Low = 0x%08" DW_PR_DUx ", High = 0x%08" DW_PR_DUx
152 ", Flag = %d, Name = '%s'\n",
153 ++nCount,
154 pBucketData->key,
155 pBucketData->base,
156 pBucketData->low,
157 pBucketData->high,
158 pBucketData->bFlag,
159 pBucketData->name);
160 }
161 }
162 }
163
164 /* Insert entry into Bucket Group.
165 We make no check for duplicate information. */
166 void
AddEntryIntoBucketGroup(Bucket_Group * pBucketGroup,Dwarf_Addr key,Dwarf_Addr base,Dwarf_Addr low,Dwarf_Addr high,const char * name,Dwarf_Bool bFlag)167 AddEntryIntoBucketGroup(Bucket_Group *pBucketGroup,
168 Dwarf_Addr key,Dwarf_Addr base,
169 Dwarf_Addr low,Dwarf_Addr high,
170 const char *name,
171 Dwarf_Bool bFlag)
172 {
173 Bucket *pBucket = 0;
174 Bucket_Data data;
175
176 data.bFlag = bFlag;
177 data.name = name;
178 data.key = key;
179 data.base = base;
180 data.low = low;
181 data.high = high;
182
183 assert(pBucketGroup);
184 if (!pBucketGroup->pHead) {
185 /* Allocate first bucket */
186 pBucket = (Bucket *)calloc(1,sizeof(Bucket));
187 pBucketGroup->pHead = pBucket;
188 pBucketGroup->pTail = pBucket;
189 pBucket->nEntries = 1;
190 pBucket->Entries[0] = data;
191 return;
192 }
193
194 pBucket = pBucketGroup->pTail;
195
196 /* Check if we have a previous allocated set of
197 buckets (have been cleared */
198 if (pBucket->nEntries) {
199 if (pBucket->nEntries < BUCKET_SIZE) {
200 pBucket->Entries[pBucket->nEntries++] = data;
201 } else {
202 /* Allocate new bucket */
203 pBucket = (Bucket *)calloc(1,sizeof(Bucket));
204 pBucketGroup->pTail->pNext = pBucket;
205 pBucketGroup->pTail = pBucket;
206 pBucket->nEntries = 1;
207 pBucket->Entries[0] = data;
208 }
209 } else {
210 /* We have an allocated bucket with zero entries; search for the
211 first available bucket to be used as the current
212 insertion point */
213 for (pBucket = pBucketGroup->pHead; pBucket;
214 pBucket = pBucket->pNext) {
215
216 if (pBucket->nEntries < BUCKET_SIZE) {
217 pBucket->Entries[pBucket->nEntries++] = data;
218 break;
219 }
220 }
221 }
222 }
223
224 /* For Groups where entries are individually deleted, this does
225 that work. */
226 Dwarf_Bool
DeleteKeyInBucketGroup(Bucket_Group * pBucketGroup,Dwarf_Addr key)227 DeleteKeyInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr key)
228 {
229 int nIndex = 0;
230 Bucket *pBucket = 0;
231 Bucket_Data *pBucketData = 0;
232
233 /* Sanity checks */
234 assert(pBucketGroup);
235
236 /* For now do a linear search */
237 for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries;
238 pBucket = pBucket->pNext) {
239
240 for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
241 pBucketData = &pBucket->Entries[nIndex];
242 if (pBucketData->key == key) {
243 Bucket_Data data = {FALSE,NULL,0,0,0,0};
244 int nStart;
245 for (nStart = nIndex + 1; nStart < pBucket->nEntries;
246 ++nStart) {
247
248 pBucket->Entries[nIndex] = pBucket->Entries[nStart];
249 ++nIndex;
250 }
251 pBucket->Entries[nIndex] = data;
252 --pBucket->nEntries;
253 return TRUE;
254 }
255 }
256 }
257 return FALSE;
258 }
259
260 /* Search to see if the address is in the range between
261 low and high addresses in some Bucked Data record.
262 This matches == if high is exact match (which usually means
263 one-past-true-high). */
264 Dwarf_Bool
FindAddressInBucketGroup(Bucket_Group * pBucketGroup,Dwarf_Addr address)265 FindAddressInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr address)
266 {
267 int nIndex = 0;
268 Bucket *pBucket = 0;
269 Bucket_Data *pBucketData = 0;
270
271 assert(pBucketGroup);
272 /* For now do a linear search */
273 for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries;
274 pBucket = pBucket->pNext) {
275
276 for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
277 pBucketData = &pBucket->Entries[nIndex];
278 if (address >= pBucketData->low &&
279 address <= pBucketData->high) {
280 return TRUE;
281 }
282 }
283 }
284 return FALSE;
285 }
286
287 /* Search an entry (Bucket Data) in the Bucket Set */
FindDataInBucketGroup(Bucket_Group * pBucketGroup,Dwarf_Addr key)288 Bucket_Data *FindDataInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr key)
289 {
290 int mid = 0;
291 int low = 0;
292 int high = 0;
293 Bucket *pBucket = 0;
294 Bucket_Data *pBucketData = 0;
295
296 assert(pBucketGroup);
297
298 for (pBucket = pBucketGroup->pHead; pBucket; pBucket = pBucket->pNext) {
299 /* Get lower and upper references */
300 if (pBucket->nEntries) {
301 low = 0;
302 high = pBucket->nEntries;
303 while (low < high) {
304 mid = low + (high - low) / 2;
305 if (pBucket->Entries[mid].key < key) {
306 low = mid + 1;
307 } else {
308 high = mid;
309 }
310 }
311 if ((low < pBucket->nEntries) &&
312 (pBucket->Entries[low].key == key)) {
313
314 pBucketData = &pBucket->Entries[low];
315 /* Update sentinels to allow traversing the table */
316 if (!pBucketGroup->pFirst) {
317 pBucketGroup->pFirst = pBucketData;
318 }
319 pBucketGroup->pLast = pBucketData;
320 return pBucketData;
321 }
322 }
323 }
324 return (Bucket_Data *)NULL;
325 }
326
327 /* Find the Bucket that contains a given Bucket Data
328 and return its local index. Else return -1. */
329 static int
FindDataIndexInBucket(Bucket_Group * pBucketGroup,Bucket_Data * pBucketData)330 FindDataIndexInBucket(Bucket_Group *pBucketGroup,Bucket_Data *pBucketData)
331 {
332 Bucket *pBucket = 0;
333 Bucket_Data *pLower = 0;
334 Bucket_Data *pUpper = 0;
335
336 /* Sanity checks */
337 assert(pBucketGroup);
338 assert(pBucketData);
339
340 /* Use sentinels if any. */
341 if (pBucketGroup->pFirst && pBucketGroup->pLast &&
342 pBucketData >= pBucketGroup->pFirst &&
343 pBucketData <= pBucketGroup->pLast) {
344
345 /* Find bucket that contains the first sentinel */
346 for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries;
347 pBucket = pBucket->pNext) {
348
349 pLower = &pBucket->Entries[0];
350 pUpper = &pBucket->Entries[pBucket->nEntries - 1];
351
352 /* Check if the first sentinel is in this bucket. */
353 if (pBucketGroup->pFirst >= pLower &&
354 pBucketGroup->pFirst <= pUpper) {
355 /* We have found the bucket, return the index. */
356 return pBucketData - pBucketGroup->pFirst;
357 }
358 }
359 } else {
360 /* Find bucket that contains the entry */
361 for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries;
362 pBucket = pBucket->pNext) {
363
364 pLower = &pBucket->Entries[0];
365 pUpper = &pBucket->Entries[pBucket->nEntries - 1];
366
367 /* Check if the first sentinel is in this bucket */
368 if (pBucketData >= pLower && pBucketData <= pUpper) {
369 /* We have found the bucket, return the index */
370 return pBucketData - pLower;
371 }
372 }
373 }
374 /* Invalid data; just return index indicating not-found */
375 return -1;
376 }
377
378 /* Search an entry (Bucket Data) in the Bucket Group.
379 The key is an offset, a DIE offset
380 within Visited info. */
FindKeyInBucketGroup(Bucket_Group * pBucketGroup,Dwarf_Addr key)381 Bucket_Data *FindKeyInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr key)
382 {
383 int nIndex = 0;
384 Bucket *pBucket = 0;
385 Bucket_Data *pBucketData = 0;
386
387 /* Sanity checks */
388 assert(pBucketGroup);
389
390 /* For now do a linear search */
391 for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries;
392 pBucket = pBucket->pNext) {
393 for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
394 pBucketData = &pBucket->Entries[nIndex];
395 if (pBucketData->key == key) {
396 return pBucketData;
397 }
398 }
399 }
400 return (Bucket_Data *)NULL;
401 }
402
403 /* Search an entry (Bucket Data) in the Bucket Set by name.
404 Used to find link-once section names. */
405 Bucket_Data *
FindNameInBucketGroup(Bucket_Group * pBucketGroup,char * name)406 FindNameInBucketGroup(Bucket_Group *pBucketGroup,char *name)
407 {
408 int nIndex = 0;
409 Bucket *pBucket = 0;
410 Bucket_Data *pBucketData = 0;
411
412 assert(pBucketGroup);
413 /* For now do a linear search. */
414 for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries;
415 pBucket = pBucket->pNext) {
416 for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
417 pBucketData = &pBucket->Entries[nIndex];
418 if (!strcmp(pBucketData->name,name)) {
419 return pBucketData;
420 }
421 }
422 }
423 return (Bucket_Data *)NULL;
424 }
425
426 /* Check if an address valid or not. That is,
427 check if it is in the lower -> upper range of a bucket.
428 It checks <= and >= so the lower end
429 and one-past on the upper end matches.
430 */
431 Dwarf_Bool
IsValidInBucketGroup(Bucket_Group * pBucketGroup,Dwarf_Addr address)432 IsValidInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr address)
433 {
434 Bucket *pBucket = 0;
435 Bucket_Data *pBucketData = 0;
436 int nIndex = 0;
437
438 assert(pBucketGroup);
439 /* Check the address is within the allowed limits */
440 if (address >= pBucketGroup->lower &&
441 address <= pBucketGroup->upper) {
442 for (pBucket = pBucketGroup->pHead;
443 pBucket && pBucket->nEntries;
444 pBucket = pBucket->pNext) {
445 for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
446 pBucketData = &pBucket->Entries[nIndex];
447 if (address >= pBucketData->low &&
448 address <= pBucketData->high) {
449 return TRUE;
450 }
451 }
452 }
453 }
454 return FALSE;
455 }
456
457 /* Reset limits for values in the Bucket Set */
458 void
ResetLimitsBucketSet(Bucket_Group * pBucketGroup)459 ResetLimitsBucketSet(Bucket_Group *pBucketGroup)
460 {
461 assert(pBucketGroup);
462 pBucketGroup->lower = 0;
463 pBucketGroup->upper = 0;
464 }
465
466 /* Limits are set only for ranges, so only in pRangesInfo. */
467 void
SetLimitsBucketGroup(Bucket_Group * pBucketGroup,Dwarf_Addr lower,Dwarf_Addr upper)468 SetLimitsBucketGroup(Bucket_Group *pBucketGroup,
469 Dwarf_Addr lower,Dwarf_Addr upper)
470 {
471 assert(pBucketGroup);
472 if (lower < upper) {
473 pBucketGroup->lower = lower;
474 pBucketGroup->upper = upper;
475 }
476 }
477
478 /* Traverse Bucket Set and execute a supplied function */
479 static void
ProcessBucketGroup(Bucket_Group * pBucketGroup,void (* pFunction)(Bucket_Group * pBucketGroup,Bucket_Data * pBucketData))480 ProcessBucketGroup(Bucket_Group *pBucketGroup,
481 void (*pFunction)(Bucket_Group *pBucketGroup,Bucket_Data *pBucketData))
482 {
483 int nIndex = 0;
484 int nStart = 0;
485 Bucket *pBucket = 0;
486 Bucket_Data *pBucketData = 0;
487 Bucket_Data *pLower = 0;
488 Bucket_Data *pUpper = 0;
489 Dwarf_Bool bFound = FALSE;
490
491 /* Sanity checks */
492 assert(pBucketGroup);
493
494 /* No sentinels present; do nothing */
495 if (!pBucketGroup->pFirst || !pBucketGroup->pLast) {
496 return;
497 }
498
499 /* Find bucket that contains the first sentinel */
500 for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries;
501 pBucket = pBucket->pNext) {
502
503 pLower = &pBucket->Entries[0];
504 pUpper = &pBucket->Entries[pBucket->nEntries - 1];
505
506 /* Check if the first sentinel is in this bucket */
507 if (pBucketGroup->pFirst >= pLower && pBucketGroup->pFirst <= pUpper) {
508 /* Low sentinel is in this bucket */
509 bFound = TRUE;
510 break;
511 }
512 }
513
514 /* Invalid sentinel; do nothing */
515 if (!bFound) {
516 return;
517 }
518
519 /* Calculate index for first sentinel */
520 nStart = pBucketGroup->pFirst - pLower;
521
522 /* Start traversing from found bucket */
523 for (; pBucket && pBucket->nEntries; pBucket = pBucket->pNext) {
524 for (nIndex = nStart; nIndex < pBucket->nEntries; ++nIndex) {
525 pBucketData = &pBucket->Entries[nIndex];
526 if (pBucketData > pBucketGroup->pLast) {
527 return;
528 }
529 /* Call the user supplied function */
530 if (pFunction) {
531 pFunction(pBucketGroup,pBucketData);
532 }
533 }
534 /* For next bucket start with first entry */
535 nStart = 0;
536 }
537 }
538
539 /* Check if a given (lopc,hipc) are valid for a linkonce.
540 We pass in the linkonce (instead of
541 referencing the global pLinkonceInfo) as that means
542 searches for pLinkonceInfo find all the uses,
543 making understanding of the code a tiny bit easier.
544 The section name created is supposed to be the appropriate
545 linkonce section name.
546 */
IsValidInLinkonce(Bucket_Group * pLo,const char * name,Dwarf_Addr lopc,Dwarf_Addr hipc)547 Dwarf_Bool IsValidInLinkonce(Bucket_Group *pLo,
548 const char *name,Dwarf_Addr lopc,Dwarf_Addr hipc)
549 {
550 #define SECTION_NAME_LEN 2048 /* Guessing a sensible length */
551 static char section_name[SECTION_NAME_LEN];
552 Bucket_Data *pBucketData = 0;
553 /* Since text is quite uniformly just this name, no need to get it
554 from elsewhere, though it will not work for non-elf. */
555 const char *lo_text = ".text.";
556
557 /* Build the name that represents the linkonce section (.text).
558 This is not defined in DWARF so not correct for all
559 compilers. */
560 snprintf(section_name,sizeof(section_name),"%s%s",lo_text,name);
561
562 pBucketData = FindNameInBucketGroup(pLo,section_name);
563 if (pBucketData) {
564 if (lopc >= pBucketData->low && lopc <= pBucketData->high) {
565 if (hipc >= pBucketData->low && hipc <= pBucketData->high) {
566 return TRUE;
567 }
568 }
569 }
570 return FALSE;
571 }
572
573