3

I'm interested in the technique used by Sean Barrett to make a dynamic array in C for any type. Comments in the current version claims the code is safe to use with strict-aliasing optimizations: https://github.com/nothings/stb/blob/master/stb_ds.h#L332

You use it like:

int *array = NULL;
arrput(array, 2);
arrput(array, 3);

The allocation it does holds both the array data + a header struct:

typedef struct
{
  size_t      length;
  size_t      capacity;
  void      * hash_table;
  ptrdiff_t   temp;
} stbds_array_header;

The macros/functions all take a void* to the array and access the header by casting the void* array and moving back one:

#define stbds_header(t)  ((stbds_array_header *) (t) - 1)

I'm sure Sean Barrett is far more knowledgeable than the average programmer. I'm just having trouble following how this type of code is not undefined behavior because of the strict aliasing rules in modern C. If this does avoid problems I'd love to understand why it does so I can incorporate it myself (maybe with a few less macros).

cecil
  • 317
  • 2
  • 8
  • It seems to only ever store/retrieve elements of one type (`int` in your case), so where would a possible aliasing violation be? – user17732522 Jan 22 '23 at 21:37
  • @user17732522 It works for any type. arrput is a macro. The allocation is for both your data (ints in this case) and its header data. – cecil Jan 22 '23 at 21:56
  • Yes, but it does not seem to intent e.g. `int *array = NULL; arrput(array, 2); arrpop(array); arrput((double*)array, 3.0);`. So in memory there is always only one type at a location (plus the header type at the header location). Aliasing violations can only occur if the (effective) type in memory is different to the type you use to access the memory. – user17732522 Jan 22 '23 at 21:59
  • @user17732522 So if 2 pointers refer to different addresses within a malloc they can each write their own type? That me be so. But is this still true if you acquire a pointer to the header via a pointer to the data by casting it to the header's type? – cecil Jan 22 '23 at 22:07
  • That would be a question about pointer arithmetic, not aliasing. My expertise is C++, not really C, so I'll leave that language-lawyering to others. – user17732522 Jan 22 '23 at 22:11
  • King of. But the issue is not about landing on the correct byte. The issue is if strict-aliasing rules will cause undefined behavior when doing that. – cecil Jan 22 '23 at 22:16

1 Answers1

2

Lets follow the expansions of arrput in https://github.com/nothings/stb/blob/master/stb_ds.h :

#define STBDS_REALLOC(c,p,s) realloc(p,s)

#define arrput      stbds_arrput

#define stbds_header(t)  ((stbds_array_header *) (t) - 1)

#define stbds_arrput(a,v)      (stbds_arrmaybegrow(a,1), (a)[stbds_header(a)->length++] = (v))

#define stbds_arrmaybegrow(a,n)  ((!(a) || stbds_header(a)->length + (n) > stbds_header(a)->capacity) \
                                  ? (stbds_arrgrow(a,n,0),0) : 0)

#define stbds_arrgrow(a,b,c)   ((a) = stbds_arrgrowf_wrapper((a), sizeof *(a), (b), (c)))

#define stbds_arrgrowf_wrapper            stbds_arrgrowf

void *stbds_arrgrowf(void *a, size_t elemsize, size_t addlen, size_t min_cap)
{
      ...
      b = STBDS_REALLOC(NULL, (a) ? stbds_header(a) : 0, elemsize * min_cap + sizeof(stbds_array_header));
      //if (num_prev < 65536) prev_allocs[num_prev++] = (int *) (char *) b;
      b = (char *) b + sizeof(stbds_array_header);
      if (a == NULL) {
        stbds_header(b)->length = 0;
        stbds_header(b)->hash_table = 0;
        stbds_header(b)->temp = 0;
      } else {
        STBDS_STATS(++stbds_array_grow);
      }
      stbds_header(b)->capacity = min_cap;

      return b;
}

how this type of code is not undefined behavior because of the strict aliasing

Strict aliasing is about accessing data that has different effective type than data stored there. I would argue that the data stored in the memory region pointed to by stbds_header(array) has the effective type of the stbds_array_header structure, so accessing it is fine. The structure members are allocated by realloc and initialized one by one inside stbds_arrgrowf by stbds_header(b)->length = 0; lines.

how this type of code is not undefined behavior

I think the pointer arithmetic is fine. You can say that the result of realloc points to an array of one stbds_array_header structure. In other words, when doing the first stbds_header(b)->length = inside stbds_arrgrowf function the memory returned by realloc "becomes" an array of one element of stbds_array_header structures, as If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access from https://port70.net/~nsz/c/c11/n1570.html#6.5p6 .

int *array is assigned inside stbds_arrgrow to point to "one past the last element of an array" of one stbds_array_header structure. (Well, this is also the same place where an int array starts). ((stbds_array_header *) (array) - 1) calculates the address of the last array element by subtracting one from "one past the last element of an array". I would rewrite it as (char *)(void *)t - sizeof(stbds_array_header) anyway, as (stbds_array_header *) (array) sounds like it would generate a compiler warning.

Assigning to int *array in expansion of stbds_arrgrow a pointer to (char *)result_of_realloc + sizeof(stbds_array_header) may very theoretically potentially be not properly aligned to int array type, breaking If the resulting pointer is not correctly aligned for the referenced type, the behavior is undefined from https://port70.net/~nsz/c/c11/n1570.html#6.3.2.3p7 . This is very theoretical, as stbds_array_header structure has size_t and void * and ptrdiff_t members, in any normal architecture it will have good alignment to access int (or any other normal type) after it.

I have only inspected the code in expansions of arrput. This is a 2000 lines of code, there may be other undefined behavior anywhere.

KamilCuk
  • 120,984
  • 8
  • 59
  • 111
  • So there's no issue reading/writing ints using `int* array` ? Even though that memory is a result of realloc that points to an array of one stbds_array_header structure? Because that is how it ends up being used by the caller. Just like a normal array of ints except for additions/removals. – cecil Jan 22 '23 at 22:36
  • This is similar to https://stackoverflow.com/questions/55014685/multiple-structures-in-a-single-malloc-invoking-undefined-behaviour , https://stackoverflow.com/questions/58495625/can-one-malloc-call-be-used-to-allocate-two-arrays , https://stackoverflow.com/questions/40809602/malloc-once-then-distribute-memory-over-struct-arrays optionB , https://stackoverflow.com/questions/73266300/can-we-use-single-malloc-block-to-represent-two-different-types . `there's no issue reading/writing ints using int* array ?` I say it's fine. Let's see if I'll get more upvotes. – KamilCuk Jan 22 '23 at 22:46
  • I hope you are right. I find this strict alias stuff terrible to deal with. – cecil Jan 22 '23 at 23:15
  • @cecil: According to the published Rationale, the rules were written to allow compilers to generate code which would be incorrect *in the language the Standard was chartered to describe*, in cases where such code generation would not interfere with what their customers had to do. The C89 Standard would have been soundly vetoed if people had known how compliers like gcc and clang would abuse it. – supercat Jan 22 '23 at 23:28
  • @supercat I'd prefer to live in a world where such dangerous optimizations were not the default but were instead opt in with things like the restrict keyword for pointers. Recently learning about strict aliasing is poisoning my love of the C language. – cecil Jan 22 '23 at 23:30
  • @cecil: Recognize that "the C language" isn't really a single language, but rather a collection of dialects which extend a common core language in ways tailored to meet different use cases. The clang and gcc optimizers are designed to process a dialect which prioritizes a few extremely narrow use cases at the expense of making it less suitable for most other cases than it otherwise would be, but what's great about C is that it allows for such dialects. What's unfortunate is that people mistake the highly specialzied dialect processed by clang and gcc for "the C language". – supercat Jan 22 '23 at 23:42
  • @cecil: Perhaps what's needed is a retronym to describe the core language which has historically been shared among non-optimizing compilers, and which the authors of the Standard would have expected that general-purpose optimizing compilers would seek to process *in cases that would matter to their customers*. – supercat Jan 22 '23 at 23:45
  • @cecil: BTW, while `restrict` is a great concept, the "formal" specification centers around the concept of a pointer being "based upon" another, and is almost certainly meant to say that 1. no object written via pointer *which is unambiguously* (WIU) based upon `p` may accessed via pointers or lvalue *WIU* not based upon `p`, and 2. no object written via pointer or lvalue *WIU* not based upon `p` may be accessed via pointer *WIU* based upon `p`, but is written in a way that presumes all pointers may be unambiguously classified without providing an unambiguous definition. – supercat Jan 23 '23 at 00:15
  • Note, that technically memory from `malloc()` is never set to array type because there it is not possible to assign array-typed l-value (except *maybe* `memcpy`). As result pretty much **any** pointer arithmetic with `malloc`-ed memory is UB! – tstanisl Jan 23 '23 at 12:47
  • @tstanisl: Another detail is that, at least in the clang/gcc interpretation of the rules, if one writes to allocated memory using one type #1 and later as an incompatible type #2, compilers are allowed to assume that the storage will never be read using non-character types that aren't compatible with #1, and also that storage will never be read using non-character types that aren't compatible with type #2. In other words, the storage will never be read using *any non-character types ta all*. That's not just a theoretical interpretation; clang and gcc are designed around it. – supercat Jan 23 '23 at 15:50
  • @supercat If that were true you couldn't make your own allocator. And that's done all the time. – cecil Jan 23 '23 at 17:20
  • `you couldn't make your own allocator` On that https://stackoverflow.com/questions/38515179/is-it-possible-to-write-a-conformant-implementation-of-malloc-in-c – KamilCuk Jan 23 '23 at 17:28
  • @supercat, another funny issue is if `a->b = 1` sets an effective type for `a` or rather for `a::b` only. – tstanisl Jan 23 '23 at 17:42
  • @cecil: In the dialect processed by clang and gcc, if a region of storage holds a certain bit pattern as type T1, any later action which is recognized as causing the storage to hold the same bit pattern may cause its effective type to revert to T1, even if that action wrote the storage using type T2. – supercat Jan 23 '23 at 17:47
  • 1
    @tstanisl: The only time such issues would matter is if the Standard is viewed as a full and complete description of all the things programmers will ever need to do in all application fields. The real problem is that the Committee has ever reached a consensus as to whether the Standard is intended to be such a description (in which case it should define many more cases than it does), or if it is merely intended to define a core language whose semantics should be extended by general-purpose implementations defining behaviors in more cases than mandated by the Standard. – supercat Jan 23 '23 at 18:04