path: root/dwarfdump/checkutil.c

/* 
  Copyright (C) 2011 SN Systems Ltd. All Rights Reserved.
  Portions Copyright (C) 2011 David Anderson. All Rights Reserved.

  This program is free software; you can redistribute it and/or modify it
  under the terms of version 2 of the GNU General Public License as
  published by the Free Software Foundation.

  This program is distributed in the hope that it would be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

  Further, this software is distributed without any warranty that it is
  free of the rightful claim of any third person regarding infringement
  or the like.  Any license provided herein, whether implied or
  otherwise, applies only to this software file.  Patent licenses, if
  any, provided herein do not apply to combinations of this program with
  other software, or any other product whatsoever.

  You should have received a copy of the GNU General Public License along
  with this program; if not, write the Free Software Foundation, Inc., 51
  Franklin Street - Fifth Floor, Boston MA 02110-1301, USA.

*/
/*

   These simple list-processing functions are in support
   of checking DWARF for compiler-errors of various sorts.


*/

#include "globals.h"
#include <assert.h>

/* Private function */
static void DumpFullBucketGroup(Bucket_Group *pBucketGroup);
static int FindDataIndexInBucket(Bucket_Group *pBucketGroup,
    Bucket_Data *pBucketData);
static void PrintBucketData(Bucket_Group *pBucketGroup,
    Bucket_Data *pBucketData);
static void ProcessBucketGroup(Bucket_Group *pBucketGroup,
    void (*pFunction)(Bucket_Group *pBucketGroup,Bucket_Data *pBucketData));

Bucket_Group *
AllocateBucketGroup(int kind)
{
    Bucket_Group *pBucketGroup = (Bucket_Group *)calloc(1,sizeof(Bucket_Group));
    pBucketGroup->kind = kind;
    return pBucketGroup;
}

void 
ReleaseBucketGroup(Bucket_Group *pBucketGroup)
{
    Bucket *pBucket = 0;
    Bucket *pNext = 0;

    assert(pBucketGroup);
    for (pBucket = pBucketGroup->pHead; pBucket; /*pBucket = pBucket->pNext*/) {
        pNext = pBucket->pNext;
        free(pBucket);
        pBucket = pNext;
    }
    pBucketGroup->pHead = NULL;
    pBucketGroup->pTail = NULL;
    free(pBucketGroup);
}

void 
ResetBucketGroup(Bucket_Group *pBucketGroup)
{
    Bucket *pBucket = 0;

    assert(pBucketGroup);
    for (pBucket = pBucketGroup->pHead; pBucket; pBucket = pBucket->pNext) {
        pBucket->nEntries = 0;
    }
    ResetSentinelBucketGroup(pBucketGroup);
}

/* Reset sentinels in a Bucket Group. */
void 
ResetSentinelBucketGroup(Bucket_Group *pBucketGroup)
{
    /* Sanity checks */
    assert(pBucketGroup);
    pBucketGroup->pFirst = NULL;
    pBucketGroup->pLast = NULL;
}

void PrintBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Bool bFull)
{
    assert(pBucketGroup);
    if (bFull) {
        DumpFullBucketGroup(pBucketGroup);
    } else {
        if (pBucketGroup->pFirst && pBucketGroup->pLast) {
            printf("\nBegin Traversing, First = 0x%08" DW_PR_DUx 
                ", Last = 0x%08" DW_PR_DUx "\n",
            pBucketGroup->pFirst->key,pBucketGroup->pLast->key);
            ProcessBucketGroup(pBucketGroup,PrintBucketData);
        }
    }
}

static void 
PrintBucketData(Bucket_Group *pBucketGroup,Bucket_Data *pBucketData)
{
    int nCount = 0;
    assert(pBucketGroup);
    assert(pBucketData);

    nCount = FindDataIndexInBucket(pBucketGroup,pBucketData);
    printf("[%06d] Key = 0x%08" DW_PR_DUx ", Base = 0x%08" DW_PR_DUx
        ", Low = 0x%08" DW_PR_DUx ", High = 0x%08" DW_PR_DUx 
        ", Flag = %d, Name = '%s'\n",
        ++nCount,
        pBucketData->key,
        pBucketData->base,
        pBucketData->low,
        pBucketData->high,
        pBucketData->bFlag,
        pBucketData->name);
}

static void 
DumpFullBucketGroup(Bucket_Group *pBucketGroup)
{
    int nBucketNo = 1;
    int nIndex = 0;
    int nCount = 0;
    Bucket *pBucket = 0;
    Bucket_Data *pBucketData = 0;

    assert(pBucketGroup);
    for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
        pBucket = pBucket->pNext) {

        printf("\nLowPC & HighPC records for bucket %d, at 0x%08lx\n",
            nBucketNo++,(unsigned long)pBucket);
        for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
            pBucketData = &pBucket->Entries[nIndex];
            printf("[%06d] Key = 0x%08" DW_PR_DUx ", Base = 0x%08" DW_PR_DUx
                ", Low = 0x%08" DW_PR_DUx ", High = 0x%08" DW_PR_DUx 
                ", Flag = %d, Name = '%s'\n",
                ++nCount,
                pBucketData->key,
                pBucketData->base,
                pBucketData->low,
                pBucketData->high,
                pBucketData->bFlag,
                pBucketData->name);
        }
    }
}

/* Insert entry into Bucket Group. 
   We make no check for duplicate information. */
void 
AddEntryIntoBucketGroup(Bucket_Group *pBucketGroup,
    Dwarf_Addr key,Dwarf_Addr base,
    Dwarf_Addr low,Dwarf_Addr high,
    const char *name,
    Dwarf_Bool bFlag)
{
    Bucket *pBucket = 0;
    Bucket_Data data;

    data.bFlag = bFlag;
    data.name = name;
    data.key = key;
    data.base = base;
    data.low = low;
    data.high = high;

    assert(pBucketGroup);
    if (!pBucketGroup->pHead) {
        /* Allocate first bucket */
        pBucket = (Bucket *)calloc(1,sizeof(Bucket));
        pBucketGroup->pHead = pBucket;
        pBucketGroup->pTail = pBucket;
        pBucket->nEntries = 1;
        pBucket->Entries[0] = data;
        return;
    }

    pBucket = pBucketGroup->pTail;

    /*  Check if we have a previous allocated set of 
        buckets (have been cleared */
    if (pBucket->nEntries) {
        if (pBucket->nEntries < BUCKET_SIZE) {
            pBucket->Entries[pBucket->nEntries++] = data;
        } else {
            /* Allocate new bucket */
            pBucket = (Bucket *)calloc(1,sizeof(Bucket));
            pBucketGroup->pTail->pNext = pBucket;
            pBucketGroup->pTail = pBucket;
            pBucket->nEntries = 1;
            pBucket->Entries[0] = data;
        }
    } else {
        /*  We have an allocated bucket with zero entries; search for the
            first available bucket to be used as the current 
            insertion point */
        for (pBucket = pBucketGroup->pHead; pBucket; 
            pBucket = pBucket->pNext) {

            if (pBucket->nEntries < BUCKET_SIZE) {
                pBucket->Entries[pBucket->nEntries++] = data;
                break;
            }
        }
    }
}

/* For Groups where entries are individually deleted, this does
   that work.  */
Dwarf_Bool 
DeleteKeyInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr key)
{
    int nIndex = 0;
    Bucket *pBucket = 0;
    Bucket_Data *pBucketData = 0;
  
    /* Sanity checks */
    assert(pBucketGroup);
  
    /* For now do a linear search */
    for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
        pBucket = pBucket->pNext) {

        for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
            pBucketData = &pBucket->Entries[nIndex];
            if (pBucketData->key == key) {
                Bucket_Data data = {FALSE,NULL,0,0,0,0};
                int nStart;
                for (nStart = nIndex + 1; nStart < pBucket->nEntries; 
                    ++nStart) {

                    pBucket->Entries[nIndex] = pBucket->Entries[nStart];
                    ++nIndex;
                }
                pBucket->Entries[nIndex] = data;
                --pBucket->nEntries;
                return TRUE;
            }
        }
    }
    return FALSE;
}

/*  Search to see if the address is in the range between 
    low and high addresses in some Bucked Data record.
    This matches == if high is exact match (which usually means
    one-past-true-high).  */
Dwarf_Bool 
FindAddressInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr address)
{
    int nIndex = 0;
    Bucket *pBucket = 0;
    Bucket_Data *pBucketData = 0;

    assert(pBucketGroup);
    /* For now do a linear search */
    for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
        pBucket = pBucket->pNext) {

        for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
            pBucketData = &pBucket->Entries[nIndex];
            if (address >= pBucketData->low && 
                address <= pBucketData->high) {
                return TRUE;
            }
        }
    }
    return FALSE;
}

/*  Search an entry (Bucket Data) in the Bucket Set */
Bucket_Data *FindDataInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr key)
{
    int mid = 0;
    int low = 0;
    int high = 0;
    Bucket *pBucket = 0;
    Bucket_Data *pBucketData = 0;

    assert(pBucketGroup);

    for (pBucket = pBucketGroup->pHead; pBucket; pBucket = pBucket->pNext) {
        /* Get lower and upper references */
        if (pBucket->nEntries) {
            low = 0;
            high = pBucket->nEntries;
            while (low < high) {
                mid = low + (high - low) / 2;
                if (pBucket->Entries[mid].key < key) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            if ((low < pBucket->nEntries) && 
                (pBucket->Entries[low].key == key)) {

                pBucketData = &pBucket->Entries[low];
                /* Update sentinels to allow traversing the table */
                if (!pBucketGroup->pFirst) {
                    pBucketGroup->pFirst = pBucketData;
                }
                pBucketGroup->pLast = pBucketData;
                return pBucketData;
            }
        }
    }
    return (Bucket_Data *)NULL;
}

/*  Find the Bucket that contains a given Bucket Data 
    and return its local index. Else return -1.  */
static int 
FindDataIndexInBucket(Bucket_Group *pBucketGroup,Bucket_Data *pBucketData)
{
    Bucket *pBucket = 0;
    Bucket_Data *pLower = 0;
    Bucket_Data *pUpper = 0;

    /* Sanity checks */
    assert(pBucketGroup);
    assert(pBucketData);

    /* Use sentinels if any. */
    if (pBucketGroup->pFirst && pBucketGroup->pLast && 
        pBucketData >= pBucketGroup->pFirst && 
        pBucketData <= pBucketGroup->pLast) {

        /* Find bucket that contains the first sentinel */
        for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
            pBucket = pBucket->pNext) {

            pLower = &pBucket->Entries[0];
            pUpper = &pBucket->Entries[pBucket->nEntries - 1];

            /* Check if the first sentinel is in this bucket. */
            if (pBucketGroup->pFirst >= pLower && 
                pBucketGroup->pFirst <= pUpper) {
                /* We have found the bucket, return the index. */
                return pBucketData - pBucketGroup->pFirst;
            }
        }
    } else {
        /* Find bucket that contains the entry */
        for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
            pBucket = pBucket->pNext) {

            pLower = &pBucket->Entries[0];
            pUpper = &pBucket->Entries[pBucket->nEntries - 1];

            /* Check if the first sentinel is in this bucket */
            if (pBucketData >= pLower && pBucketData <= pUpper) {
                /* We have found the bucket, return the index */
                return pBucketData - pLower;
            }
        }
    }
    /* Invalid data; just return index indicating not-found */
    return -1;
}

/*  Search an entry (Bucket Data) in the Bucket Group.
    The key is an offset, a DIE offset 
    within Visited info. */
Bucket_Data *FindKeyInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr key)
{
    int nIndex = 0;
    Bucket *pBucket = 0;
    Bucket_Data *pBucketData = 0;

    /* Sanity checks */
    assert(pBucketGroup);

    /* For now do a linear search */
    for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
        pBucket = pBucket->pNext) {
        for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
            pBucketData = &pBucket->Entries[nIndex];
            if (pBucketData->key == key) {
                return pBucketData;
            }
        }
    }
    return (Bucket_Data *)NULL;
}

/*  Search an entry (Bucket Data) in the Bucket Set by name.
    Used to find link-once section names. */
Bucket_Data *
FindNameInBucketGroup(Bucket_Group *pBucketGroup,char *name)
{
    int nIndex = 0;
    Bucket *pBucket = 0;
    Bucket_Data *pBucketData = 0;

    assert(pBucketGroup);
    /* For now do a linear search. */
    for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
        pBucket = pBucket->pNext) {
        for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
            pBucketData = &pBucket->Entries[nIndex];
            if (!strcmp(pBucketData->name,name)) {
                return pBucketData;
            }
        }
    }
    return (Bucket_Data *)NULL;
}

/*  Check if an address valid or not. That is,
    check if it is in  the lower -> upper range of a bucket. 
    It checks <= and >= so the lower end
    and  one-past on the upper end matches.
*/
Dwarf_Bool 
IsValidInBucketGroup(Bucket_Group *pBucketGroup,Dwarf_Addr address)
{
    Bucket *pBucket = 0;
    Bucket_Data *pBucketData = 0;
    int nIndex = 0;

    assert(pBucketGroup);
    /* Check the address is within the allowed limits */
    if (address >= pBucketGroup->lower && address <= pBucketGroup->upper) {
        for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
            pBucket = pBucket->pNext) {

            for (nIndex = 0; nIndex < pBucket->nEntries; ++nIndex) {
                pBucketData = &pBucket->Entries[nIndex];
                if (address >= pBucketData->low && 
                    address <= pBucketData->high) {
                    return TRUE;
                }
            }
        }
    }
    return FALSE;
}

/*  Reset limits for values in the Bucket Set */
void 
ResetLimitsBucketSet(Bucket_Group *pBucketGroup)
{
    assert(pBucketGroup);
    pBucketGroup->lower = 0;
    pBucketGroup->upper = 0;
}

/*  Limits are set only for ranges, so only in pRangesInfo. */
void 
SetLimitsBucketGroup(Bucket_Group *pBucketGroup,
    Dwarf_Addr lower,Dwarf_Addr upper)
{
    assert(pBucketGroup);
    if (lower < upper) {
        pBucketGroup->lower = lower;
        pBucketGroup->upper = upper;
    }
}

/* Traverse Bucket Set and execute a supplied function */
static void 
ProcessBucketGroup(Bucket_Group *pBucketGroup,
    void (*pFunction)(Bucket_Group *pBucketGroup,Bucket_Data *pBucketData))
{
    int nIndex = 0;
    int nStart = 0;
    Bucket *pBucket = 0;
    Bucket_Data *pBucketData = 0;
    Bucket_Data *pLower = 0;
    Bucket_Data *pUpper = 0;
    Dwarf_Bool bFound = FALSE;

    /* Sanity checks */
    assert(pBucketGroup);

    /* No sentinels present; do nothing */
    if (!pBucketGroup->pFirst || !pBucketGroup->pLast) {
        return;
    }

    /* Find bucket that contains the first sentinel */
    for (pBucket = pBucketGroup->pHead; pBucket && pBucket->nEntries; 
        pBucket = pBucket->pNext) {

        pLower = &pBucket->Entries[0];
        pUpper = &pBucket->Entries[pBucket->nEntries - 1];
  
        /* Check if the first sentinel is in this bucket */
        if (pBucketGroup->pFirst >= pLower && pBucketGroup->pFirst <= pUpper) {
            /* Low sentinel is in this bucket */
            bFound = TRUE;
            break;
        }
    }

    /* Invalid sentinel; do nothing */
    if (!bFound) {
        return;
    }

    /* Calculate index for first sentinel */
    nStart = pBucketGroup->pFirst - pLower;

    /* Start traversing from found bucket */
    for (; pBucket && pBucket->nEntries; pBucket = pBucket->pNext) {
        for (nIndex = nStart; nIndex < pBucket->nEntries; ++nIndex) {
            pBucketData = &pBucket->Entries[nIndex];
            if (pBucketData > pBucketGroup->pLast) {
                return;
            }
            /* Call the user supplied function */
            if (pFunction) {
                pFunction(pBucketGroup,pBucketData);
            }
        }
        /* For next bucket start with first entry */
        nStart = 0;
    }
}

/*  Check if a given (lopc,hipc) are valid for a linkonce. 
    We pass in the linkonce  (instead of
    referencing the global pLinkonceInfo) as that means 
    searches for pLinkonceInfo find all the uses, 
    making understanding of the code a tiny bit easier. 
    The section name created is supposed to be the appropriate
    linkonce section name.
*/
Dwarf_Bool IsValidInLinkonce(Bucket_Group *pLo,
    const char *name,Dwarf_Addr lopc,Dwarf_Addr hipc)
{
#define SECTION_NAME_LEN 2048 /* Guessing a sensible length */
    static char section_name[SECTION_NAME_LEN]; 
    Bucket_Data *pBucketData = 0;
    /*  Since text is quite uniformly just this name, no need to get it
        from elsewhere, though it will not work for non-elf.  */
    const char *lo_text = ".text";

    /*  Build the name that represents the linkonce section (.text). 
        This is not defined in DWARF so not correct for all
        compilers. */
    snprintf(section_name,sizeof(section_name),"%s%s",lo_text,name);
  
    pBucketData = FindNameInBucketGroup(pLo,section_name);
    if (pBucketData) {
        if (lopc >= pBucketData->low && lopc <= pBucketData->high) {
            if (hipc >= pBucketData->low && hipc <= pBucketData->high) {
                return TRUE;
            }
        }
    }
    return FALSE;
}