[Nauty] Undefined behavior in nauty (Going over bounds)

[keith.briggs at bt.com]

Could this not be done by having int* p in the struct, and using two malloc calls when creating a new permnode?
Keith

________________________________
From: Nauty <nauty-bounces at anu.edu.au> on behalf of Mathieu Dutour <mathieu.dutour at gmail.com>
Sent: 16 November 2020 11:10
To: Brendan McKay <Brendan.McKay at anu.edu.au>; nauty-list at cs.anu.edu.au <nauty-list at cs.anu.edu.au>
Subject: Re: [Nauty] Undefined behavior in nauty (Going over bounds)

>
> Not so fast.
>
Yes, indeed I was too fast.

There is a structural type declared like this:
>
> typedef struct permnodestruct
> {
>      struct permnodestruct *prev,*next;   /* prev&next in circular list */
>      unsigned long refcount;              /* number of references */
>      int nalloc;                          /* size of p[] in ints,
>                                              <= 0 for a perm marker */
>      int mark;                            /* a mark, 0 unless changed */
>      int p[2];                            /* actual vector, extended to
>                                              nalloc enties */
> } permnode;
>
> Variables of this type are allocated in newpermnode() thus:
>
>      malloc(sizeof(permnode)+(n-2)*sizeof(int));
>
> This allocates enough space for the member p to hold n ints. (The case
> n=1 doesn't occur, but I don't remember why I used [2] instead of [1].)
>
Thank you, I did not know about this construction. The name is "struct
hack".

This is a traditional way of having a dynamically-sized array in a
> structure.
>
Yes, it is popular and traditional. However, it does appear to be
undefined behavior.
See, e.g.
https://eur02.safelinks.protection.outlook.com/?url=http%3A%2F%2Fc-faq.com%2Fstruct%2Fstructhack.html&data=04%7C01%7Ckeith.briggs%40bt.com%7Ce4c471672d7b4f3f5f0e08d88a214154%7Ca7f356889c004d5eba4129f146377ab0%7C0%7C0%7C637411222723815374%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=pdgz6q6MmmplfO6hjXThIjkO42A7ZTI3RT7%2BGfQA5Gk%3D&reserved=0
https://eur02.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.open-std.org%2Fjtc1%2Fsc22%2Fwg14%2Fwww%2Fdocs%2Fdr_051.html&data=04%7C01%7Ckeith.briggs%40bt.com%7Ce4c471672d7b4f3f5f0e08d88a214154%7Ca7f356889c004d5eba4129f146377ab0%7C0%7C0%7C637411222723815374%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=%2FlOC1dZxjWzghsnnpG%2BAikG209AOisE1qRB75%2FwjM%2F0%3D&reserved=0
https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fstackoverflow.com%2Fquestions%2F3711233%2Fis-the-struct-hack-technically-undefined-behavior&data=04%7C01%7Ckeith.briggs%40bt.com%7Ce4c471672d7b4f3f5f0e08d88a214154%7Ca7f356889c004d5eba4129f146377ab0%7C0%7C0%7C637411222723815374%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=PhVxQhhOFSQvQ56jdgtaKiDON%2BB1k%2BnZ%2BLv9lV2aAv8%3D&reserved=0

But here we see an awkward portability problem.  In the C99 standard,
> the correct way to achieve this is to use an "incomplete array", like this:
>
>      int p[];
>
Those are named "flexible array members" and they were introduced in C99.

The ANSI C standard and
> ISO C (C89/90) explicitly forbade structure members of incomplete type.
>
Yes, the flexible array members were introduced as a solution to the struct
hack
problem.

I don't know about C95 or post-C99 standards.
>
> See here for some discussion:
> https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgcc.gnu.org%2Fonlinedocs%2Fgcc%2FZero-Length.html&data=04%7C01%7Ckeith.briggs%40bt.com%7Ce4c471672d7b4f3f5f0e08d88a214154%7Ca7f356889c004d5eba4129f146377ab0%7C0%7C0%7C637411222723815374%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=k7p6iL7wH09n2%2FPyXLlfsKbLClT1I8f4Tn3SaL7SldE%3D&reserved=0
>
> I'm not going to require nauty users to have C99-compatible compilers,
> and I know as a fact that many don't.

I understand your wish. However, my wish is to run conformant code
without undefined behavior since those may cause some problem at one
point or another.

I try conservatively to not use
> features newer than ANSI C unless necessary.

I completely understand your wish.


> Perhaps I should add this issue to the configuration script.

That would be much welcome. A defined statement like C99_CONFORMANT
would be very useful.


> On the other hand, I can't see anything
> in the C99 standard to forbid my usage

I think the https://eur02.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.open-std.org%2Fjtc1%2Fsc22%2Fwg14%2Fwww%2Fdocs%2Fdr_051.html&data=04%7C01%7Ckeith.briggs%40bt.com%7Ce4c471672d7b4f3f5f0e08d88a214154%7Ca7f356889c004d5eba4129f146377ab0%7C0%7C0%7C637411222723815374%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=%2FlOC1dZxjWzghsnnpG%2BAikG209AOisE1qRB75%2FwjM%2F0%3D&reserved=0
is quite explicit about it not being legal.
The solution adopted by the C standard was "flexible array members". Thus
I think that struct arrays were never legal.


> and the sanitizers in gcc+clang
> do not define what is legal.
>
The definition of what is legal or not is not in the saninitizer, but in
the norm.

Thank you very much for your explanations and of course for nauty!

  Mathieu
_______________________________________________
Nauty mailing list
Nauty at anu.edu.au
https://eur02.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmailman.anu.edu.au%2Fmailman%2Flistinfo%2Fnauty&data=04%7C01%7Ckeith.briggs%40bt.com%7Ce4c471672d7b4f3f5f0e08d88a214154%7Ca7f356889c004d5eba4129f146377ab0%7C0%7C0%7C637411222723815374%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=QN%2Ba%2FrPmPQGk1PfF3Xc4xjlLZNVx3KDSMFZtdtTvzaA%3D&reserved=0