1

I'm a software engineer getting my master's degree and I'm coding a program in C that implements the Lloyd Algorithm. However, I'm stuck in this segmentation fault 11.. I'm working with big numbers, that's why it's breaking but I've tried to render it as much as possible and I'm still getting this error.

These are the structs implemented:

struct point{
    float x;
    float y;
};

struct cluster{
    float x;
    float y;
    float* points;
};

This is my code:

struct point* initPoint(){
    struct point* point = malloc(sizeof(struct point));
    point->x = 0.0;
    point->y = 0.0;
    return point;
}

struct cluster* initCluster(int NP){
    struct cluster* cluster = malloc(sizeof(struct cluster));
    cluster->x = 0.0;
    cluster->y = 0.0;
    cluster->points = malloc(sizeof(float)*NP);
    return cluster;
}

void init(int NP, int NC, struct point* points[NP], struct cluster* clusters[NC]) {
    for(int p = 0; p < NP; p++){
        points[p] = initPoint();
    }
    for(int i = 0; i < NC; i++){
        clusters[i] = initCluster(NP);
    }
    srand(10);
    for(int p = 0; p < NP; p++) {
        points[p]->x = (float) rand() / RAND_MAX;       // coordinate X
        points[p]->y = (float) rand() / RAND_MAX;       // coordinate Y
    }
    for(int i = 0; i < NC; i++) {
        clusters[i]->x = points[i]->x;
        clusters[i]->y = points[i]->y;
    }
}

void free_structs(int NP, int NC, struct point* points[NP], struct cluster* clusters[NC]){
    for(int i = 0; i < NP; i++){
        free(points[i]);
    }
    for(int i = 0; i < NC; i++){
        free(clusters[i]->points);
        free(clusters[i]);
    }
}

In the main file:

#define N 10000000      // number of points   (NP)
#define K 4             // number of clusters (NC)

int main(){
    struct point* points[N];
    struct cluster* clusters[K];
    init(N,K,points,clusters);
    /*
    for(int i = 0; i < K; i++){
        printf("Cluster --> %d: \n",i);
        printf("Coordinate X: %f\n",clusters[i]->x);
        printf("Coordinate Y: %f\n\n",clusters[i]->y);
    }*/
    free_structs(N,K,points,clusters);
    return 0;
}

Can you give me a hand, please?

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
Ana Henriques
  • 11
  • 1
  • 2
    I'm suspecting a stack overflow at `struct point* points[N];` - Skip the VLA and `malloc` the array instead. – Ted Lyngmo Oct 18 '22 at 08:35
  • 1
    ...which needs 80Mb of stack space. – Weather Vane Oct 18 '22 at 08:37
  • 2
    The common way to store local variables is on the process stack. The stack is a limited resource, on e.g. Linux it's usually 8 MiB, on Windows only one single MiB. Your array `points` in the `main` function will be `N * sizeof(struct point *)` bytes, which is *way* larger than that (by an order of magnitude, at least). – Some programmer dude Oct 18 '22 at 08:38
  • 2
    You clearly seem to know how `malloc` works, so... `struct point** points = malloc(N * sizeof *points);` (note the type of `points`, btw). – WhozCraig Oct 18 '22 at 08:39

1 Answers1

1

The problem is most probably that you try to allocate too much on the stack. I suggest that you allocate the memory for your large arrays dynamically (on the heap) instead.

In main, change from :

struct point* points[N];
struct cluster* clusters[K]; // K is only 4, but I expect you may increase it later

to

struct point** points = malloc(N * sizeof *points);
struct cluster** clusters = malloc(K * sizeof *clusters);

// then at the end of main:

free(clusters);
free(points);

Also, to make init portable with implementations not supporting VLAs, change from:

void init(int NP, int NC, struct point* points[NP], struct cluster* clusters[NC]) {

to

void init(int NP, int NC, struct point* points[], struct cluster* clusters[]) {
Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
  • It looks like the C11 brainfarts regarding making VLA optional will get fixed in C23, so that at least pointer to VLA will become a mandatory feature once more. Therefore I wouldn't concern myself about portability to compilers not supporting pointer to VLA unless you explicitly need C89 dinosaur mode portability (in which case the whole of the OP's code has to be rewritten anyway). – Lundin Oct 18 '22 at 10:36
  • @Lundin Oh, that's nice! I think the portability note will still be useful for as long as there are C11-C18 code bases alive, so I'll leave in there - unless you think it hurts more than helps? – Ted Lyngmo Oct 18 '22 at 12:23
  • As far as I know there exist no compilers that define both `__STDC__` and `__STDC_NO_VLA__`. Maybe some obscure embedded compiler I don't know about. There's a few of them that have VLA disabled per default but allows it with some option enabled. But you wouldn't be using `malloc` either for those kind of systems. – Lundin Oct 18 '22 at 12:43
  • (Actually it seems that some versions of IAR and Keil might have both of those defined at once, per default.) – Lundin Oct 18 '22 at 13:02
  • @Lundin I was hoping even MSVC would get both defined in C17 mode, but they closed [this issue](https://developercommunity.visualstudio.com/t/stdc17-and-stdc11-define-stdc-version-but-not-stdc/1407009) as a duplicate to a ticket that doesn't mention the macros at all - and `__STDC__` still remains undefined in C17 mode even though `__STDC_VERSION__` _is_ defined as 201710. :-( Oh, well, it's (supposedly) a C11-C17 compiler that doesn't have VLA support, so for users of that compiler (and those you mentioned) the note may have some value. – Ted Lyngmo Oct 18 '22 at 13:15
  • MSVC doesn't define `__STDC__` because it's non-conforming crap, that's why... it doesn't even conform to ISO 9899:1990+AMD1:1995 so it does not conform to _any_ C language standard published in modern times. Unlike the mentioned IAR and Keil that should be up to date with at least C11. – Lundin Oct 18 '22 at 13:37
  • @Lundin That explains that then :-) They do define it in `/Za` (c89/90) mode though ... but perhaps they shouldn't. – Ted Lyngmo Oct 18 '22 at 13:48
  • "The /Za compiler option disables and emits errors for Microsoft extensions to C that aren't compatible with ANSI C89/ISO C90" Great! So lets try to the simplest of tests and add `// /Za is broken` to some code and compile with MSVC `/Za`. Did we get the mandatory diagnostic message for syntax error according to ISO 9899:1990? No. Is the compiler non-conforming crap in this mode as well? Yes. – Lundin Oct 18 '22 at 14:13
  • @Lundin :-) Got it! – Ted Lyngmo Oct 18 '22 at 14:21