Problem with free(int *)

[ferbar]

Hi all,

I'm working on a program that tests a random number generator -rand()-
in this case. Runs and Chi square test have to be applied to see if the
numbers generated are random.. anyway, I'm using malloc and then free.
When doing free, I get a segmentation fault.. I'm looking into the
code, but I cannot find the problem..

concretely, the problem is with >>> free(s_intervals);
Here's the stack & below the code:

I appreciate any help!

Thanks,
FBM

Cygwin GDB Debugger (9/26/05 10:10 PM) (Suspended)
Thread [1] (Suspended: Signal 'SIGSEGV' received. Description:
Segmentation fault.)
6 setstate()
5 lsearch()
4 cygwin1!aclcheck()
3 exit()
2 dll_crt0@0()
1 <symbol is not available>
Thread [2] (Suspended)
5 <symbol is not available>
4 ntdll!ZwReadFile()
3 ReadFile()
2 <symbol is not available>
1 <symbol is not available>


#define N 200
#define MAXRUNUPS 6
#define K 101

#include <fcntl.h>
#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>

/******* GLOBAL VARIABLES *********/

double A_values[6][6] = {
{4529.4, 9044.9, 13568, 18091, 22615, 27892},
{9044.9, 18097, 27139, 36187, 45234, 55789},
{13568, 27139, 40721, 54281, 67852, 83685},
{18091, 36187, 54281, 72414, 90470, 111580},
{22615, 45234, 67852, 90470, 113262, 139476},
{27892, 55789, 83685, 111580, 139476, 172860}
};

double B_values[6] = {0.16666667, 0.20833333, 0.55, 0.02638889,
0.00575396, 0.00119047};
/************************************/

void obtain_sample(double * ssample) {
int i;
double drand;
for (i=0; i < N; i++) {
drand = ((double) rand()) / RAND_MAX;
ssample = drand;
// printf("Random number %d: %f\n", i, drand);
}

}

void obtain_runups(double * ssample, double * runups_i) {
int i;
double elem_sample, lrunup = 0;

for (i=0; i < N; i++) {
elem_sample = ssample;
if (elem_sample < ssample[i+1])
lrunup += 1;
else {
if (lrunup < 6) {
runups_i[(int)lrunup] += 1;
lrunup = 0;
}
else {
runups_i[MAXRUNUPS-1] += 1;
lrunup = 0;
}
}
}
}

double obtain_R(double * runups) {
int i, j;
double runup_i, first_elem_sum, second_elem_sum, sum_ij = 0,
sum_ij_tmp = 0, R;
double n = N;
for (i=0; i < 6; i++) {
runup_i = runups;
for (j=0; j < 6; j++) {
first_elem_sum = runup_i - (N*B_values);
second_elem_sum = runups[j] - (N*B_values[j]);
sum_ij_tmp = first_elem_sum * second_elem_sum * A_values[j];
sum_ij += sum_ij_tmp;
}
}
R = (1/n) * sum_ij;
return R;
}

void divide_interval_01(double * interval) {
int i;
float k = K;
float interval_i = 1;

interval_i = (1 / k);
interval[0] = 0;
for (i=1; i <= k; i++)
interval = interval_i * (i);

}

void find_f_i(double * ssample, double * intervals, int * s_intervals)
{
int i, j;
double elem_i, k = K;
for (i=0; i < N; i++) {
elem_i = ssample;
for (j=0; j < k; j++)
if ((elem_i >= intervals[j]) && (elem_i < intervals[j+1])) {
s_intervals[j] += 1;
break;
}
}
}

double obtain_chi_square(int * s_intervals) {
double chi_2, sum_i=0, sum_tmp=0, mean, n = N;
int i, f_i, k = K;

for (i=0; i < k; i++) {
f_i = s_intervals;
mean = (n / k);
sum_tmp = pow((f_i - mean), 2);
sum_i += sum_tmp;
}
chi_2 = (k / n) * sum_i;
return chi_2;
}

int main(int argc, char** argv) {
double * sample, * intervals;
int * s_intervals;
double R_value, Chi_2;
// double sample2[] = {
// 0.5, 0.6,
// 0.2, 0.4, 0.45, 0.5, 0.6,
// 0.46,
// 0.45,
// 0.3, 0.31, 0.315, 0.32, 0.321, 0.322, 0.33, 0.34,
// 0.10, 0.11, 0.12, 0.131, 0.132, 0.133, 0.134, 0.135, 0.136
// };
double runups_i[MAXRUNUPS] = {0};

sample = (double*) malloc(N*sizeof(double));
intervals = (double*) malloc(K*sizeof(double));
s_intervals = (int*) malloc(K*sizeof(int));

srand(1); /* seed */
obtain_sample(sample);

/* Runs test */
obtain_runups(sample, runups_i);
R_value = obtain_R(runups_i);
printf("R: %f\n", R_value);

/* Chi-square test */
divide_interval_01(intervals);
find_f_i(sample, intervals, s_intervals);
Chi_2 = obtain_chi_square(s_intervals);
printf("Chi square: %f\n", Chi_2);

free(sample);
free(intervals);
********free(s_intervals);********
exit(0);
}

 

[Gordon Burditt]

I'm working on a program that tests a random number generator -rand()-

in this case. Runs and Chi square test have to be applied to see if the
numbers generated are random.. anyway, I'm using malloc and then free.
When doing free, I get a segmentation fault.. I'm looking into the
code, but I cannot find the problem..

The problem is often a subscript out of range, or scribbling beyond
the end of allocated memory.

A loop like:

for (i = 0; i <= k; i++) {

where i is used as a subscript of an array allocated
with malloc(k*sizeof(something)) is a red flag.

Gordon L. Burditt

 

[Old Wolf]

I'm using malloc and then free.
When doing free, I get a segmentation fault.. I'm looking into
the code, but I cannot find the problem..

You have three buffer overflows.

#include <fcntl.h>
#include <sys/time.h>
#include <unistd.h>

You don't actually use any of those files, and they are
non-standard anyway, so don't include them.

sample = (double*) malloc(N*sizeof(double));
intervals = (double*) malloc(K*sizeof(double));
s_intervals = (int*) malloc(K*sizeof(int));

You should not use casts with malloc, it has no benefits
at all, and it has down-sides (such as hiding important
compiler warnings).

sample = malloc(N * sizeof *sample);
intervals = malloc(K * sizeof *intervals);
s_intervals = malloc(K * sizeof *s_intervals);

for (i=0; i < N; i++) {
elem_sample = ssample;
if (elem_sample < ssample[i+1])

This causes an access over-run: when i is N-1, you
access ssample[N], which is beyond the array bounds.

void divide_interval_01(double * interval) {
int i;
float k = K;
float interval_i = 1;

Why float ? It's less accurate than double.

interval_i = (1 / k);
interval[0] = 0;
for (i=1; i <= k; i++)
interval = interval_i * (i);

This actually writes beyond the bounds of your malloc'd memory,
when i == K. You malloc'd K doubles for "interval", their indices
are interval[0], interval[1], ..., interval[K-1].
This is probably the source of your segfault.

Also you should never use a floating point value as a loop index
or termination condition, as they often cannot represent values
exactly, so the loop may run one more time or one fewer time
than you expect.

void find_f_i(double * ssample, double * intervals, int * s_intervals)
{
int i, j;
double elem_i, k = K;
for (i=0; i < N; i++) {
elem_i = ssample;
for (j=0; j < k; j++)
if ((elem_i >= intervals[j]) &&
(elem_i < intervals[j+1])) {
s_intervals[j] += 1;
break;
}
}

This reads past the end of intervals[] when j == K-1.

Again, use the capital K in the loop test condition, to
avoid floating point errors.

free(sample);
free(intervals);
********free(s_intervals);********

Segfaults on free() usually show that you overran one of
the malloc'd buffers (not necessarily s_intervals).

One way to debug this sort of problem is
to allocate more memory then you need, and fill up the
buffer with some distinct value (eg. 0xEE). Then, just
before you do the free(), inspect the ends of the buffers
and check they still contain 0xEE. If they don't, then
you must have overflowed what you thought you were using.

 

[ferbar]

Thank you. I am going to revise your notes and do the changes. Thanks
also for the 0xEE idea.. it seems very nice.

FBM