qsort clobbering memory location

[William Buch]

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

MEMORY LOCATION OK HERE
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table)
{
printf("NULL Table call.\n");
return;
}
linkTable = table;
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);

printf("%x\n", list); NOT OK!!!!!!!!

//printf("%i\n", cmp);
qsort (table, ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[k] != table[j]) {
k = k + 1;
table[k] = table[j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[ptab[j]] = k;
}

printf("%x\n", list); NOT OK!!!!!!!!!!!!!!

printf("Compression Complete %i.\n", k);
table[k+1] = -1; /* End of table Marker */
sizeTab = k+1;
entries += k+1;
printf("Before Blah\n");

printf("In use %x\n", list); NOT OK!!!!!!!!!!!!!!!!

printf("Blah\n");
}


I tried list as static and "unstatic" but always global. Could that
be the problem? Any help would be greatly appreciated ASAP!

 

[Artie Gold]

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

MEMORY LOCATION OK HERE
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table)
{
printf("NULL Table call.\n");
return;
}
linkTable = table;
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);

printf("%x\n", list); NOT OK!!!!!!!!

//printf("%i\n", cmp);
qsort (table, ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[k] != table[j]) {
k = k + 1;
table[k] = table[j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[ptab[j]] = k;
}

printf("%x\n", list); NOT OK!!!!!!!!!!!!!!

printf("Compression Complete %i.\n", k);
table[k+1] = -1; /* End of table Marker */
sizeTab = k+1;
entries += k+1;
printf("Before Blah\n");

printf("In use %x\n", list); NOT OK!!!!!!!!!!!!!!!!

printf("Blah\n");
}


I tried list as static and "unstatic" but always global. Could that
be the problem? Any help would be greatly appreciated ASAP!

Well, obviously there's a bug in the program. How, may I ask, is
*anyone* supposed to know where the problem is without seeing the
relevant declarations?

Present code that can be compiled and run; it greatly enhances your
chance of receiving appropriate help.

[One thing to look for is `off-by-one' errors -- one variety of which is
writing past the end of an array.]

HTH,
--ag

 

[Jack Klein]

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

MEMORY LOCATION OK HERE
for (i = 0; i < list->in_use; i++) {

[snip]

printf("%x\n", list); NOT OK!!!!!!!!

[snip]

printf("%x\n", list); NOT OK!!!!!!!!!!!!!!

[snip]

printf("In use %x\n", list); NOT OK!!!!!!!!!!!!!!!!

Unless the first line of your snippet above has a serious error,
'list' is a pointer to a structure or union type. Passing it to
printf() with a %x conversion specifier produces undefined behavior.

This is not likely to be the cause of your problem, it is probably in
the code you didn't post.

 

[pete]

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program.

Since you can only run the program four times, once,
(then it becomes the fifth time and the sixth time, etc.)
what do you mean by "ALWAYS the fourth time running the program"?

 

[Michel Bardiaux]

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)

if(item1<=item2)
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

HTH,

 

[pete]

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)

if(item1<=item2)
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

 

[William Buch]

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)
http://alpha.searchlimo.com/
if(item1<=item2)
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

My apologies for not including the comparison functions. They are as
follows:


static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

int32 *linkTable;

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

And again here is the snippet:

static void
buildExitTable (list_t *list, int32 ***table_p, int32 ***permuTab_p,
int32 **sizeTab_p)
{
int32 ciCount = phoneCiCount();
int32 i, j, k;
char triphoneStr[128];
int32 silContext = 0;
int32 triphoneContext = 0;
int32 noContext = 0;
int32 entries = 0;
int32 **table;
int32 **permuTab;
int32 *sizeTab;
int32 ptab[128];

*table_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1, sizeof
(int32 *));
table = *table_p;
*permuTab_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1,
sizeof (int32 *));
permuTab = *permuTab_p;
*sizeTab_p = (int32 *) CM_calloc (list->in_use, sizeof (int32 *));
sizeTab = *sizeTab_p;

//printf("Exit Context table contains\n\t%6d entries\n",
list->in_use);
E_INFO("\t%6d possible cross word triphones.\n", list->in_use *
ciCount);

printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {

for (j = 0; j < ciCount; j++) {
/*
* Look for the triphone
*/
sprintf (triphoneStr, list->list, phone_from_id (j));
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
triphoneContext++;
/*
* If we can't find the desired context use "SIL"
*/
if (table[j] < 0) {
sprintf (triphoneStr, list->list, "SIL");
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
silContext++;
}
/*
* If we can't find "SIL" use context indepedent
*/
if (table[j] < 0) {
char stmp[32];
char *p;
strcpy (stmp, list->list);
p = strchr (stmp, '(');
*p = '\0';
table[j] = phone_to_id (stmp, TRUE);
noContext++;
}
table[j] = hmm_pid2sid(phone_map(table[j]));
}
}
//printf("About to compress the table.\n");
/*
* Now compress the table to eliminate duplicate entries.
*/
printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table)
{
printf("NULL Table call.\n");
return;
}
linkTable = table;
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);
printf("%x\n", list);
//printf("%i\n", cmp);
qsort (table, ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[k] != table[j]) {
k = k + 1;
table[k] = table[j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[ptab[j]] = k;
}
printf("%x\n", list);
printf("Compression Complete %i.\n", k);
table[k+1] = -1; /* End of table Marker */
sizeTab = k+1;
entries += k+1;
printf("Before Blah\n");
printf("In use %x\n", list);
printf("Blah\n");
}
//printf("\t%6d triphones\n\t%6d pseudo diphones\n\t%6d
uniphones\n",
//triphoneContext, silContext, noContext);
E_INFO("\t%6d right context entries\n", entries);
E_INFO("\t%6d ave entries per exit context\n",
((list->in_use == 0) ? 0 : entries/list->in_use));
}

I run this program in a loop, with each iteration after some input.
The first three times the program functions properly. One the fourth
time of initializing the system, when running the qsort program,
everything bombs. My question is how qsort allocates memory? Could
it be possible that something is not being freed, thus qsort (or my
program) is allocating more and more memory and eventually overwrites
the variable in question? I am a little out of my league when it
comes to debugging problems like these.

 

[pete]

William Buch wrote:

static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

The difference between two signed integers is unsuitable
for a compar of random array elements.
The result can overflow.

 

[Rob Thorpe]

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code
[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)
http://alpha.searchlimo.com/
if(item1<=item2)
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

My apologies for not including the comparison functions. They are as
follows:


static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

int32 *linkTable;

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

And again here is the snippet:

static void
buildExitTable (list_t *list, int32 ***table_p, int32 ***permuTab_p,
int32 **sizeTab_p)
{
int32 ciCount = phoneCiCount();
int32 i, j, k;
char triphoneStr[128];
int32 silContext = 0;
int32 triphoneContext = 0;
int32 noContext = 0;
int32 entries = 0;
int32 **table;
int32 **permuTab;
int32 *sizeTab;
int32 ptab[128];

*table_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1, sizeof
(int32 *));
table = *table_p;
*permuTab_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1,
sizeof (int32 *));
permuTab = *permuTab_p;
*sizeTab_p = (int32 *) CM_calloc (list->in_use, sizeof (int32 *));
sizeTab = *sizeTab_p;

//printf("Exit Context table contains\n\t%6d entries\n",
list->in_use);
E_INFO("\t%6d possible cross word triphones.\n", list->in_use *
ciCount);

printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {

for (j = 0; j < ciCount; j++) {
/*
* Look for the triphone
*/
sprintf (triphoneStr, list->list, phone_from_id (j));
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
triphoneContext++;
/*
* If we can't find the desired context use "SIL"
*/
if (table[j] < 0) {
sprintf (triphoneStr, list->list, "SIL");
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
silContext++;
}
/*
* If we can't find "SIL" use context indepedent
*/
if (table[j] < 0) {
char stmp[32];
char *p;
strcpy (stmp, list->list);
p = strchr (stmp, '(');
*p = '\0';
table[j] = phone_to_id (stmp, TRUE);
noContext++;
}
table[j] = hmm_pid2sid(phone_map(table[j]));
}
}
//printf("About to compress the table.\n");
/*
* Now compress the table to eliminate duplicate entries.
*/
printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table)
{
printf("NULL Table call.\n");
return;
}
linkTable = table;
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);
printf("%x\n", list);
//printf("%i\n", cmp);
qsort (table, ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[k] != table[j]) {
k = k + 1;
table[k] = table[j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[ptab[j]] = k;
}
printf("%x\n", list);
printf("Compression Complete %i.\n", k);
table[k+1] = -1; /* End of table Marker */
sizeTab = k+1;
entries += k+1;
printf("Before Blah\n");
printf("In use %x\n", list);
printf("Blah\n");
}
//printf("\t%6d triphones\n\t%6d pseudo diphones\n\t%6d
uniphones\n",
//triphoneContext, silContext, noContext);
E_INFO("\t%6d right context entries\n", entries);
E_INFO("\t%6d ave entries per exit context\n",
((list->in_use == 0) ? 0 : entries/list->in_use));
}

I run this program in a loop, with each iteration after some input.
The first three times the program functions properly. One the fourth
time of initializing the system, when running the qsort program,
everything bombs. My question is how qsort allocates memory? Could
it be possible that something is not being freed, thus qsort (or my
program) is allocating more and more memory and eventually overwrites
the variable in question? I am a little out of my league when it
comes to debugging problems like these.

I can't understand your program, I doubt many people can. Avoid
things like "int32 ***" if you can (I understand you have inherited
this). Consider rewriting this function.
I can help you with one thing: it is very unlikely to be a bug in
qsort, qsort is used very frequently on every platform. Also it
probably uses stack memory not heap (even if it's not recursive).

There is definitely something very wrong going on:

this line

qsort (ptab, ciCount, sizeof(int32), cmpPT);

sorts the array ptab, which contains all integers from 0 to ciCount.
It's not erm, normal to sort a sequence.

but it sorts it with this:

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

Call me pathetic, but it's a brave man who sorts an array based not on
the information in it, but information somewhere else entirely.

 

[pete]

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code
[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)
http://alpha.searchlimo.com/
if(item1<=item2)
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

My apologies for not including the comparison functions. They are as
follows:

static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

int32 *linkTable;

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

And again here is the snippet:

static void
buildExitTable (list_t *list, int32 ***table_p, int32 ***permuTab_p,
int32 **sizeTab_p)
{
int32 ciCount = phoneCiCount();
int32 i, j, k;
char triphoneStr[128];
int32 silContext = 0;
int32 triphoneContext = 0;
int32 noContext = 0;
int32 entries = 0;
int32 **table;
int32 **permuTab;
int32 *sizeTab;
int32 ptab[128];

*table_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1, sizeof
(int32 *));
table = *table_p;
*permuTab_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1,
sizeof (int32 *));
permuTab = *permuTab_p;
*sizeTab_p = (int32 *) CM_calloc (list->in_use, sizeof (int32 *));
sizeTab = *sizeTab_p;

//printf("Exit Context table contains\n\t%6d entries\n",
list->in_use);
E_INFO("\t%6d possible cross word triphones.\n", list->in_use *
ciCount);

printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {

for (j = 0; j < ciCount; j++) {
/*
* Look for the triphone
*/
sprintf (triphoneStr, list->list, phone_from_id (j));
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
triphoneContext++;
/*
* If we can't find the desired context use "SIL"
*/
if (table[j] < 0) {
sprintf (triphoneStr, list->list, "SIL");
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
silContext++;
}
/*
* If we can't find "SIL" use context indepedent
*/
if (table[j] < 0) {
char stmp[32];
char *p;
strcpy (stmp, list->list);
p = strchr (stmp, '(');
*p = '\0';
table[j] = phone_to_id (stmp, TRUE);
noContext++;
}
table[j] = hmm_pid2sid(phone_map(table[j]));
}
}
//printf("About to compress the table.\n");
/*
* Now compress the table to eliminate duplicate entries.
*/
printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table)
{
printf("NULL Table call.\n");
return;
}
linkTable = table;
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);
printf("%x\n", list);
//printf("%i\n", cmp);
qsort (table, ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[k] != table[j]) {
k = k + 1;
table[k] = table[j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[ptab[j]] = k;
}
printf("%x\n", list);
printf("Compression Complete %i.\n", k);
table[k+1] = -1; /* End of table Marker */
sizeTab = k+1;
entries += k+1;
printf("Before Blah\n");
printf("In use %x\n", list);
printf("Blah\n");
}
//printf("\t%6d triphones\n\t%6d pseudo diphones\n\t%6d
uniphones\n",
//triphoneContext, silContext, noContext);
E_INFO("\t%6d right context entries\n", entries);
E_INFO("\t%6d ave entries per exit context\n",
((list->in_use == 0) ? 0 : entries/list->in_use));
}

I run this program in a loop, with each iteration after some input.
The first three times the program functions properly. One the fourth
time of initializing the system, when running the qsort program,
everything bombs. My question is how qsort allocates memory?

qsort is not allowed to fail if the arguments to qsort are valid.

 

[Peter Slootweg]

see inline

pete <[email protected]> wrote in message

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code
[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)
http://alpha.searchlimo.com/
if(item1<=item2)
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

My apologies for not including the comparison functions. They are as
follows:


static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

int32 *linkTable;

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

And again here is the snippet:

static void
buildExitTable (list_t *list, int32 ***table_p, int32 ***permuTab_p,
int32 **sizeTab_p)
{
int32 ciCount = phoneCiCount();
int32 i, j, k;
char triphoneStr[128];
int32 silContext = 0;
int32 triphoneContext = 0;
int32 noContext = 0;
int32 entries = 0;
int32 **table;
int32 **permuTab;
int32 *sizeTab;
int32 ptab[128];

*table_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1, sizeof
(int32 *));

should probably be sizeof(int32) - assuming you need to pass in the size of
the element in your simulated 2d array

table = *table_p;
*permuTab_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1,
sizeof (int32 *));

should probably be sizeof(int32) - assuming you need to pass in the size of
the element in your simulated 2d array

permuTab = *permuTab_p;
*sizeTab_p = (int32 *) CM_calloc (list->in_use, sizeof (int32 *));

should probably be sizeof(int32) - assuming you need to pass in the size of
the element in your 1d array

sizeTab = *sizeTab_p;

//printf("Exit Context table contains\n\t%6d entries\n",
list->in_use);
E_INFO("\t%6d possible cross word triphones.\n", list->in_use *
ciCount);

printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {

for (j = 0; j < ciCount; j++) {
/*
* Look for the triphone
*/
sprintf (triphoneStr, list->list, phone_from_id (j));
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
triphoneContext++;
/*
* If we can't find the desired context use "SIL"
*/
if (table[j] < 0) {
sprintf (triphoneStr, list->list, "SIL");
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
silContext++;
}
/*
* If we can't find "SIL" use context indepedent
*/
if (table[j] < 0) {
char stmp[32];
char *p;
strcpy (stmp, list->list);
p = strchr (stmp, '(');
*p = '\0';
table[j] = phone_to_id (stmp, TRUE);
noContext++;
}
table[j] = hmm_pid2sid(phone_map(table[j]));
}
}
//printf("About to compress the table.\n");
/*
* Now compress the table to eliminate duplicate entries.
*/
printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}

is ciCount ever greater than 128 (your size of ptab)?
add a call to print ciCount here to confirm it isn't larger than ptab's size
i.e.
printf("%ul\n",(unsigned long)ciCount);

if(!table)
{
printf("NULL Table call.\n");
return;
}
linkTable = table;
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);

add a call to print list address here to confirm it isn't already corrupted
i.e.
printf("list before qsort=%p\n", (void*)list);

//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);
printf("%x\n", list);
//printf("%i\n", cmp);
qsort (table, ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[k] != table[j]) {
k = k + 1;
table[k] = table[j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[ptab[j]] = k;
}
printf("list=%x\n", list);

fix call to print list address here to confirm it has been corrupted
i.e.
printf("%p\n", (void*)list);

printf("Compression Complete %i.\n", k);
table[k+1] = -1; /* End of table Marker */
sizeTab = k+1;
entries += k+1;
printf("Before Blah\n");
printf("In use %x\n", list);
printf("Blah\n");
}
//printf("\t%6d triphones\n\t%6d pseudo diphones\n\t%6d
uniphones\n",
//triphoneContext, silContext, noContext);
E_INFO("\t%6d right context entries\n", entries);
E_INFO("\t%6d ave entries per exit context\n",
((list->in_use == 0) ? 0 : entries/list->in_use));
}

I run this program in a loop, with each iteration after some input.
The first three times the program functions properly. One the fourth
time of initializing the system, when running the qsort program,
everything bombs. My question is how qsort allocates memory? Could
it be possible that something is not being freed, thus qsort (or my
program) is allocating more and more memory and eventually overwrites
the variable in question? I am a little out of my league when it
comes to debugging problems like these.

 

[Peter Shaggy Haywood]

Groovy hepcat William Buch was jivin' on 27 Jan 2004 12:37:43 -0800 in
comp.lang.c.
Re: qsort clobbering memory location's a cool scene! Dig it!

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code
[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)
http://alpha.searchlimo.com/
if(item1<=item2)
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

My apologies for not including the comparison functions. They are as
follows:

Please provide code that will compile. We cannot do anything with
the following fragments, except comment on what errors are apparent.
If your actual program is too long to post here, then cut it down to
the smallest *complete* program that still shows the problem. It would
also help to know what it is supposed to do and how.

static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);

That is a bad way to implement a comparison function. See the FAQ
(which you should have done on first entering this newsgroup.)

}

int32 *linkTable;

What is int32? And why is this variable defined at file scope and
with external linkage (ie., a global variable)? This is usually a bad
idea.

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

And again here is the snippet:

static void
buildExitTable (list_t *list, int32 ***table_p, int32 ***permuTab_p,
int32 **sizeTab_p)

Ye gads!
How is this function called? What is passed to it? At what do all
these pointers point?

{
int32 ciCount = phoneCiCount();

What is phoneCiCount()?

int32 i, j, k;
char triphoneStr[128];
int32 silContext = 0;
int32 triphoneContext = 0;
int32 noContext = 0;
int32 entries = 0;
int32 **table;
int32 **permuTab;
int32 *sizeTab;
int32 ptab[128];

*table_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1, sizeof
(int32 *));

What is CM_2dcalloc()? It is probably a bad idea to cast its return
value. (It usually is a bad idea to go casting things.)

table = *table_p;
*permuTab_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1,
sizeof (int32 *));
permuTab = *permuTab_p;
*sizeTab_p = (int32 *) CM_calloc (list->in_use, sizeof (int32 *));

What is CM_calloc()? It is probably a bad idea to cast its return
value. (It usually is a bad idea to go casting things.)

sizeTab = *sizeTab_p;

//printf("Exit Context table contains\n\t%6d entries\n",
list->in_use);

I have two issues if contention here. First, when posting code here
in Usenet, only use C style comments, not C++ style ones (even though
they're legal in C99), because they have a nasty tendancy to wrap,
which makes copy, paste & compile operations a pain! And secondly, if
you comment code out, remove it when you post; otherwise it just
clutters the place up.

E_INFO("\t%6d possible cross word triphones.\n", list->in_use *
ciCount);

What is E_INFO? You do realise that this is an invasion of
implementation name space (unless it is an implementation provided
function or macro, in which case it is non-standard and renders your
code off topic), don't you?

printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {

OK, list must be a pointer to a struct or union type. That much we
know. But what struct or union type? Yes, I saw the declaration (as a
parameter) at the top of this function (list_t *list), but what is a
list_t?

for (j = 0; j < ciCount; j++) {
/*
* Look for the triphone
*/
sprintf (triphoneStr, list->list, phone_from_id (j));

What is list->list? What is phone_from_id()? Where's the format
string? (It looks like list->list is supposed to be the format
string.) Have you remembered to include stdio.h?

table[j] = phone_to_id (triphoneStr, FALSE);

What is phone_to_id()?

if (table[j] >= 0)
triphoneContext++;

Don't mix tabs and spaces for code indenting. Be consistent with
your indenting. Remember, not everyone has their tab stops set the
same as you. What looks properly indented to you looks all over the
place to me.

/*
* If we can't find the desired context use "SIL"
*/
if (table[j] < 0) {
sprintf (triphoneStr, list->list, "SIL");
table[j] = phone_to_id (triphoneStr, FALSE);
if (table[j] >= 0)
silContext++;
}
/*
* If we can't find "SIL" use context indepedent
*/
if (table[j] < 0) {
char stmp[32];
char *p;
strcpy (stmp, list->list);
p = strchr (stmp, '(');
*p = '\0';
table[j] = phone_to_id (stmp, TRUE);
noContext++;
}
table[j] = hmm_pid2sid(phone_map(table[j]));

What is hmm_pid2sid()? What is phone_map()?

}
}
//printf("About to compress the table.\n");
/*
* Now compress the table to eliminate duplicate entries.
*/
printf("%x\n", list);

You were told about this earlier in the thread! Pay attention! Now,
list is a pointer to list_t, but you're using the conversion specifier
for unsigned int. BANG! Undefined behaviour! You need to cast list to
void * (this is one of the rare cases in which it makes sense to cast
- in fact it's necessary) and use the coresponding conversion
specifier (%p).

for (i = 0; i < list->in_use; i++) {

What is list->in_use?

/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table)
{
printf("NULL Table call.\n");
return;
}
linkTable = table;
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);
printf("%x\n", list);
//printf("%i\n", cmp);
qsort (table, ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[k] != table[j]) {
k = k + 1;
table[k] = table[j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[ptab[j]] = k;
}
printf("%x\n", list);
printf("Compression Complete %i.\n", k);
table[k+1] = -1; /* End of table Marker */
sizeTab = k+1;
entries += k+1;
printf("Before Blah\n");
printf("In use %x\n", list);
printf("Blah\n");
}
//printf("\t%6d triphones\n\t%6d pseudo diphones\n\t%6d
uniphones\n",
//triphoneContext, silContext, noContext);
E_INFO("\t%6d right context entries\n", entries);
E_INFO("\t%6d ave entries per exit context\n",
((list->in_use == 0) ? 0 : entries/list->in_use));
}

I run this program in a loop, with each iteration after some input.

What do you mean you run this program in a loop? Do you, perchance,
mean that you run this *function* in a loop? If so, then say so, and
show us some code that does so. You must give us something that will
compile!

The first three times the program functions properly. One the fourth

You mean the *function* functions properly the first three times?

time of initializing the system, when running the qsort program,

Initialising what system? What are you talking about?

everything bombs. My question is how qsort allocates memory? Could

It doesn't. qsort() is an array sorting function, not a memory
allocation function.

it be possible that something is not being freed, thus qsort (or my
program) is allocating more and more memory and eventually overwrites
the variable in question? I am a little out of my league when it

Of course, if the allocation system is corrupted, then anything's
possible. However, allocating memory in a correct program running on a
stable system cannot overwrite a variable.
Your problem could be in the code you didn't post (after being told
several times to post a complete program). Or it could be in the
incomprehensible mess you did post. Who knows? Without seeing a
cleaned up, full program and a description of what it is supposed to
do and how it is supposed to work, it is very difficult to know what
might be wrong.

--

Dig the even newer still, yet more improved, sig!

http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?