Bug 132066 – [3.4/ICE] gcc crahes with a segfault compiling a small file.

• Status: RESOLVED WORKSFORME
• Product: Gentoo Linux

[Description joe_saunders 2006-05-02 15:44:14 UTC]

jsaunders@gentoo ~/dev/base/prod_rtp/libs/framework/src/unitTests $ g++ -I ../ kmp.cc -o kmp
/tmp/ccZCY80j.o(.gnu.linkonce.t._ZN10PoolObjectI4PoolLZ18KMPFindBetweenPoolEEdlEPvj+0x10): In function `g++: Internal error: Segmentation fault (program collect2)
Please submit a full bug report.
See <URL:http://bugs.gentoo.org/> for instructions.


Portage 2.0.51.22-r2 (default-linux/x86/2005.1, gcc-3.4.4, glibc-2.3.5-r1, 2.6.12-gentoo-r10 i686)
=================================================================
System uname: 2.6.12-gentoo-r10 i686 Intel(R) Xeon(TM) CPU 3.20GHz
Gentoo Base System version 1.6.12
dev-lang/python:     2.2.3-r6, 2.3.5
sys-apps/sandbox:    1.2.11
sys-devel/autoconf:  2.13, 2.59-r6
sys-devel/automake:  1.4_p6, 1.5, 1.6.3, 1.7.9-r1, 1.8.5-r3, 1.9.5
sys-devel/binutils:  2.15.92.0.2-r10
sys-devel/libtool:   1.5.18-r1
virtual/os-headers:  2.6.11-r2
ACCEPT_KEYWORDS="x86 ~x86"
AUTOCLEAN="yes"
CBUILD="i686-pc-linux-gnu"
CFLAGS="-march=pentium4 -mtune=pentium4 -pipe -O3 -fweb -frename-registers -fforce-addr -momit-leaf-frame-pointer -fomit-frame-pointer -ftracer"
CHOST="i686-pc-linux-gnu"
CONFIG_PROTECT="/etc /usr/kde/2/share/config /usr/kde/3.4/env /usr/kde/3.4/share/config /usr/kde/3.4/shutdown /usr/kde/3/share/config /usr/lib/X11/xkb /usr/share/config /var/qmail/control"
CONFIG_PROTECT_MASK="/etc/gconf /etc/terminfo /etc/env.d"
CXXFLAGS="-march=pentium4 -mtune=pentium4 -pipe -O3 -fweb -frename-registers -fforce-addr -momit-leaf-frame-pointer -fomit-frame-pointer -ftracer -fvisibility-inlines-hidden"
DISTDIR="/usr/portage/distfiles"
FEATURES="autoconfig ccache distlocks fixpackages sandbox sfperms strict"
GENTOO_MIRRORS="http://distro.ibiblio.org/pub/linux/distributions/gentoo/"
MAKEOPTS="-j5"
PKGDIR="/usr/portage/packages"
PORTAGE_TMPDIR="/var/tmp"
PORTDIR="/usr/portage"
SYNC="rsync://rsync.gentoo.org/gentoo-portage"
USE="x86 X acpi alsa apm arts audiofile avi berkdb bitmap-fonts ccache cross crypt cscope cups curl eds emboss encode ethereal exim fam flac foomaticdb fortran ftp gdbm gif gphoto2 gpm gstreamer gtk gtk2 gtkhtml icq imap imlib ipv6 java jpeg jpeg2k junit kde ldap libg++ libwww mad mikmod mime motif mp3 mpeg msn ncurses nls nptl nptlonly nvidia ogg oggvorbis opengl oss pam pdf pdflib perforce perl png python qt quicktime readline samba sdl soap spell ssl subversion tcpd tiff truetype truetype-fonts type1-fonts unicode usb vorbis xine xml xml2 xmms xscreensaver xv xvid zlib userland_GNU kernel_linux elibc_glibc"
Unset:  ASFLAGS, CTARGET, LANG, LC_ALL, LDFLAGS, LINGUAS, PORTDIR_OVERLAY



gentoo unitTests # cat kmp.cc
////////////////////////////////////////////////////////////////////////
//
//        KMPSearch Unit Test
//
//
// Main
//
// Copyright (c) 2002 by Caw Networks Inc.
// Proprietary Information. All right reserved
//
///////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include "cawTypes.h"                   // Caw Networks Data Type Abstractions
#include "Exception.h"                  // Caw Exception Class
#include "KMPSearch.h"

//#define REQUEST_DETAIL_TRACE

using namespace std;

/*
// Make local copy of string to seach for
const char * saveString(const char * s, int slen = -1)
{
    if (s == 0)
        return 0;
    if (slen < 0)
        slen = strlen(s);
    char * newString = new char[slen + 1];
    if (newString == 0)
        return 0;
    memcpy(newString, s, slen);
    newString[slen] = '\0';
    return newString;
}
*/

//////////////////////////////////////////////////////////////
// Constructor:
// Instantiates and builds the index table used in KMP search as well as
// saving away the search characters.
KMPSearch::KMPSearch(const char * target, int targetLen)
{
    //mTarget = saveString(target, targetLen);
    mTarget = target;

    //News and builds the index table.
    mReTarget = BuildReTarget(mTarget);

    // Set search index to zero
    mIndex = 0;
}

//////////////////////////////////////////////////////////////
// Destructor
// Deletes the index table created in the constructor.
KMPSearch::~KMPSearch()
{
    delete mReTarget;
}

//////////////////////////////////////////////////////////////
// Make jump table for mismatches (the usual finite state automaton).
//
// The inner loop works by checking the prefixes of the next character of
// the target and can continue, longest first, chaining back by way of the
// previously filled retarget entries, until it either finds one that
// matches (the != clause) or runs out of prefixes (the > 0 clause).
int * KMPSearch::BuildReTarget(const char * target)
{
    // Check that match string is not null
    if (target == 0)
        return 0;

    // Create a in
    int * retarget = new int[strlen(target)+1];

    if (retarget == 0)
        return 0;


    retarget[0] = -1;           // set up for loop below; unused by match()

    for (int i = 0; target[i] != '\0'; i++) {
        retarget[i + 1] = retarget[i] + 1;
        while (retarget[i + 1] > 0 &&
               target[i] != target[retarget[i + 1] - 1])
            retarget[i + 1] = retarget[retarget[i + 1] - 1] + 1;
    }
    return retarget;
}



//////////////////////////////////////////////////////////////
// Pattern match the passed in character to the current operation
// slowly walking the match string, continuing at mIndex.
int
KMPSearch::Match(char c)
{
    if (mReTarget == 0)
        return 0;

    while (c != mTarget[mIndex]) {
        if (mIndex == 0)
            return 0; // fell all the way back, have to give up
        mIndex = mReTarget[mIndex]; // more positions to fall back to, keep trying
    }
    if (mTarget[++mIndex] != '\0')
        return 0;       // partial match
    else {
        mIndex = mReTarget[mIndex]; // full match, but keep going
        return 1;
    }
}

//////////////////////////////////////////////////////////////
// KMPFindBetween
// Class to locate a string which is locate between two user specified
// strings.  Uses KMP to match the pre and post strings;  PreOccurrance
// and PostOccurance parameter allows for the matching of the string
// after a certain occurance of the match has occurred.  I.E. specifying
// 3 for the PreOccurance will result in confirmation of the preString
// match on the THIRD occurance of the preString.
KMPFindBetween::KMPFindBetween( string &preString, int preOccurance, string &postString, int postOccurance )
    : mPreString(preString.c_str(), preString.length()),
      mPreOccurance(preOccurance),
      mPreOccuranceInitial(preOccurance),
      mPreFound(false),
      mPostString(postString.c_str(), postString.length()),
      mPostOccurance(postOccurance),
      mPostOccuranceInitial(postOccurance),
      mValue(""),
      mNonOverlapMatch(false)
{
    /*
      cout << __FUNCTION__ << endl
           << "mPreString = " << preString << endl
           << "mPreOccuranceInitial = " << mPreOccuranceInitial << endl
           << "mPostString = " << postString << endl
           << "mPostOccurance = " << mPostOccurance << endl
           << "mPostOccuranceInitial = " << mPostOccuranceInitial << endl
           << "*************************************" << endl;
   */

    if (0 == preString.length())
    {
        mPreFoundEmpty = true;
    }
    else
    {
        mPreFoundEmpty = false;
    }

    mPreFound = mPreFoundEmpty;

}

//////////////////////////////////////////////////////////////
// Resets the search strings of both the PreString and PostString
// as well as the value found.
void KMPFindBetween::Reset(void)
{
    mPreFound = mPreFoundEmpty;


    mValue = "";
    mNonOverlapMatch = false;
    mPreString.Reset();
    mPostString.Reset();

    mPreOccurance = mPreOccuranceInitial;
    mPostOccurance = mPostOccuranceInitial;

}
//////////////////////////////////////////////////////////////
// Search the patterns with character c.
// 1. Start matching against the PreString till found.
// 2. Save away all characters after finding PreString into mValue
// 3. Start matching against the PostString till found.
// 4. Remove PostString from end of mValue
bool KMPFindBetween::Match(char c)
{
    bool postFound = false;

    if ( !mPreFound ) {
        // looking for prestring condition
        if (mPreString.Match(c)) {
            mPreOccurance--;
            if (mPreOccurance == 0) {
                mPreFound = true;
#ifdef REQUEST_DETAIL_TRACE
        cout << __FUNCTION__ << " found prestring = " << mPreString.Target() << endl;
#endif

        } else
                mPreString.Reset();
        }
    } else {
        // Save characters into value and look for post string
        mValue += c;
        if (mPostString.Match(c)) {
            mPostOccurance--;
        if (mPostOccurance == 0) {
            // Remove post string from the value.
            // Using resize to avoid string copy.
            mValue.resize( mValue.length() - strlen(mPostString.Target()) );
            //                  mValue = mValue.substr( 0, mValue.length() - strlen(mPostString.Target()) );
#ifdef REQUEST_DETAIL_TRACE
            cout << __FUNCTION__ << " found prestring = " << mPostString.Target() << endl;
#endif
            postFound = true;
        } else
                mPostString.Reset();
        }
    }
    return postFound;
}

//////////////////////////////////////////////////////////////
// The difference between this and the above Match() method
// is that this will find only non-overlapping substrings
//
// This method is somewhat kludgy in that it actually has two
// types of return values
//      -       When the pre-occurrance being looked for has been found
//              this function returns true and does not maintain any state.
//      -       When some occurrance was found but the exact pre-occurrance
//              has not been seen it saves the last seen substring and
//              records state that at least one match was found.
//              Once the character stream has ended, a client can inquire
//              whether some match was found and act accordingly.
//See Also:
//      SessionVariable::IsNonOverlapMatchFound()
//      HttpTransaction::PacketReceived()
bool KMPFindBetween::NonOverlapMatch(char c)
{
    bool postFound = false;

    if ( !mPreFound )
        {
                // looking for prestring condition
                if (mPreString.Match(c))
                {
            /*
            cout << __FUNCTION__ << ": mPreString     == " << mPreString.Target() << endl;
                        cout << __FUNCTION__ << ": mPreoccurance  == " << mPreOccurance << "\n";
            */
                mPreOccurance--;
                        mPreFound = true;
                        mValue = "";    //clean out saved string
                }
    }
        else
        {
                // Save characters into value and look for post string
                mValue += c;
                if (mPostString.Match(c))
                {
                mPostOccurance--;
            /*
            cout << __FUNCTION__ << ": ************** == " << endl;
            cout << __FUNCTION__ << ": mPostString    == " << mPostString.Target() << endl;
                        cout << __FUNCTION__ << ": mPreoccurance  == " << mPreOccurance << "\n";
                        cout << __FUNCTION__ << ": mPostOccurance == " << mPostOccurance << "\n";
            cout << __FUNCTION__ << ": mValue         == " << mValue << "\n";
            */
                if (mPostOccurance == 0)
                        {
                                // Remove post string from the value.
                        // Using resize to avoid string copy.
                                mValue.resize( mValue.length() - strlen(mPostString.Target()) );
                                mNonOverlapMatch = true;
                                //cout << __FUNCTION__ << ": mValue     == " << mValue << "\n";

                                //since we count down on preoccurance, if we
                                //reach 0, that means we have reached the last
                                //one seen; else continue searching for next substring
                                if(mPreOccurance > 0)
                                {
                                        mPreFound = false;      //for next match
                                        postFound = false;
                                        mPostOccurance = mPostOccuranceInitial;
                    /*
                                        cout << __FUNCTION__ << ": match notfound == \n";
                    cout << __FUNCTION__ << ": ************** == " << endl;
                    cout << __FUNCTION__ << ": mPostString    == " << mPostString.Target() << endl;
                    cout << __FUNCTION__ << ": mPreoccurance  == " << mPreOccurance << "\n";
                    cout << __FUNCTION__ << ": mPostOccurance == " << mPostOccurance << "\n";
                    cout << __FUNCTION__ << ": mValue         == " << mValue << "\n";
                    */
                                }
                                else
                                {
                    /*
                                        cout << __FUNCTION__ << ": match found\n";
                    cout << __FUNCTION__ << ": ************** == " << endl;
                    cout << __FUNCTION__ << ": mPostString    == " << mPostString.Target() << endl;
                    cout << __FUNCTION__ << ": mPreoccurance  == " << mPreOccurance << "\n";
                    cout << __FUNCTION__ << ": mPostOccurance == " << mPostOccurance << "\n";
                    cout << __FUNCTION__ << ": mValue         == " << mValue << "\n";
                    */
                                        postFound = true;
                                        //we return true here, so no need to
                                        //keep state for future recheck
                                        mNonOverlapMatch = false;
                                }

                }
                }
    }
    return postFound;
}



const string KMPFindString::sNoValue("");

//////////////////////////////////////////////////////////////
// KMPFindString
// Class to locate a string which is user specified.
// Uses KMPSearch to locate the string.
KMPFindString::KMPFindString( string &target, int occurrence )
    : mTarget(target.c_str(), target.length()),
      mOccurance(occurrence),
      mOccuranceInitial(occurrence)
{
}

//////////////////////////////////////////////////////////////
// Resets the search.
void KMPFindString::Reset(void)
{
    mTarget.Reset();
    mOccurance = mOccuranceInitial;
}

//////////////////////////////////////////////////////////////
// Matches the character c to the pattern.
bool KMPFindString::Match(char c)
{
    bool found = false;
    if (mTarget.Match(c)) {
        mOccurance--;
        if (mOccurance == 0)
            found = true;
        else
            mTarget.Reset();
    }
    return found;
}

int BasicFunctionalTest(int argc, char **argv);
int ExceptionTests( void );
int LimitTests( void );

Uint32 gVerbosity=0;

int main( int argc, char **argv )
{

  cout << "\n<KMPSearch> - Unit Test starting\n";
  // BASIC FUNCTIONAL TESTS

  // 1. File with all valid entries
  cout << "Basic Functional Test\n";
  if ( BasicFunctionalTest(argc, argv) == -1 )
    return -1;


  // EXCEPTION TESTS

  // 1. Verify a non existent file generates an error
  cout << "Exception Test\n";
  if ( ExceptionTests() == -1 )
    return -1;

  // LIMIT TESTS

  // 1. Verify a non existent file generates an error
  cout << "Limit Test\n";
  if ( LimitTests() == -1 )
    return -1;

  cout << "Unit Test completed OK\n";
  return 0;
}
string TestString[] = {"This is so STOOOPID",
                             "This is even MORE STOOOPID",
                             "This is pretty smart",
                             "This is even much smarter"};
string PreString[]  = {"This", "This", "This", "This"};
string PostString[] = {"STOOOPID", "STOOOPID", "smart", "smarter"};

//=====================================================================================
//
// unit test program / BasicFunctionalTest
//
//=====================================================================================
int BasicFunctionalTest(int argc, char **argv)
{
    int retVal=0;
    KMPFindString *findStringArray[4];
    // Instantiate the necessary KMPFindString objects
    for (int i = 0; i < 4; i++)
    {
        cout << "Created new KMPFindString " << endl;
        cout << "PreString[" << i << "]: " << PreString[i] << endl;
        findStringArray[i] = new KMPFindString(PreString[i], 1);
    }

    cout << "Performing match " << endl;
    // Do actual validation.
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < (int)TestString[i].size(); j++)
        {
            if (findStringArray[i]->Match(TestString[i].at(j)))
            {
                cout << "Found match for: '" << PreString[i]
                     << "' at index " << i
                     <<" of string '" << TestString[i] << endl;
                break;
            }
        }
    }

    cout << endl << endl;

    // Instantiate the necessary KMPFindString objects
    for (int i = 0; i < 4; i++)
    {
        delete findStringArray[i];
        cout << "Created new KMPFindString " << endl;
        cout << "PostString[" << i << "]: " << PostString[i] << endl;
        findStringArray[i] = new KMPFindString(PostString[i], 1);
    }

    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < (int)TestString[i].size(); j++)
        {
            if (findStringArray[i]->Match(TestString[i].at(j)))
            {
                cout << "Found match for: '" << PostString[i]
                     << "' at index " << i
                     <<" of string '" << TestString[i] << endl;
                break;
            }
        }
    }


    cout << endl << endl;

    KMPFindBetween *findBetweenArray[4];

    // Instantiate the necessary KMPFindString objects
    for (int i = 0; i < 4; i++)
    {
        cout << "Created new KMPFindBetween " << endl;
        cout << "PreString[" << i << "]: " << PreString[i] <<"\t"
             << "PostString[" <<i << "]: " << PostString[i] << endl;
        findBetweenArray[i] = new KMPFindBetween(PreString[i], 1, PostString[i], 1);
    }

    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < (int)TestString[i].size(); j++)
        {
            if (findBetweenArray[i]->Match(TestString[i].at(j)))
            {
                cout << "String: " << TestString[i] << endl;
                cout << "PreString: " << PreString[i] << endl;
                cout << "PostString: " << PostString[i] << endl;
                cout << "Value = " << findBetweenArray[i]->GetValue() << endl << endl;
                break;
            }
        }
    }


    return retVal;
}

//=====================================================================================
//
// unit test program / ExceptionTests
//
//=====================================================================================
int ExceptionTests( void )
{
    int retVal=0;
    return retVal;
}

//=====================================================================================
//
// unit test program / LimitTests
//
//=====================================================================================
int LimitTests( void )
{
    int retVal=0;
    return retVal;
}
gentoo unitTests #

[Comment 1 Jakub Moc (RETIRED) 2006-05-02 23:35:31 UTC]

Please, don't restrict bugs without any reason.

[Comment 2 SpanKY 2006-05-03 16:26:35 UTC]

post the file as an *attachment*

inlining it in the comments makes it useless

[Comment 3 Mark Loeser (RETIRED) 2006-05-10 14:19:37 UTC]

Please attach the preprocessed source.  Also, try the latest version of gcc instead of 3.4.4.  Reopen after you attached the preprocessed source if you can still reproduce it.

[Comment 4 joe_saunders 2006-05-10 15:17:16 UTC]

Created attachment 86571 [details]
Pre-processed file used to generate segfault...

This is the preprocesssed file that causes the compilation system to segfault...

I will try the latest gcc...

-Joe

[Comment 5 joe_saunders 2006-05-10 15:31:47 UTC]

Attached the pre-processed file that caused segfault...

[Comment 6 Mark Loeser (RETIRED) 2006-05-10 17:22:23 UTC]

Works for me with 3.4.6.  Reopen the bug if that is not the case.  3.4.5-r1 (current stable) still ICEs for me.