Двумерный массив и очередной UB

Question

В свое время дал на вопрос о двумерном массиве такой ответ. Вчера дал на него ссылку в другом ответе. Но вчерашняя же дискуссия об UB при вычислении смещения поля в структуре (которое, хоть и считается официально UB, но мне таковым не кажется... но это мое личное мнение) заставила задуматься — не даю ли я некорректные в этой точки зрения советы?

Просто я стандарт, как прапорщик устав, наизусть не знаю, особенно в части особо тонких моментов с указателями, поэтому прошу гуру в ~~уставе~~стандарте проверить этот код на корректность в плане UB. И если таковое имеет место, то помочь от него избавиться.

Итак, суперзадача — двумерный массив в С, который носит с собой свои размеры — перед указателем на данные, память под которые тоже выделяется одним куском: сначала массив указателей на строки, потом сами строки массива. Чтобы выделение-освобождение памяти было единственное, а передавать в разные функции можно было только один указатель.

Вот этот код (T — произвольный тип элементов массива, никак не параметр шаблона :) — напомню, это С).

T** create(int N, int M)
{
    T** arr = (T**)malloc(2*sizeof(int)+N*(sizeof(T*)+M*sizeof(T)));
    *((int*)arr)   = N;
    *((int*)arr+1) = M;
    arr = (T**)((char*)arr+2*sizeof(int));

    for(int i = N, ofs = N*sizeof(T*);
        i-->0; ofs += M*sizeof(T))
        arr[i] = (T*)((char*)arr + ofs);

    return arr;
}

void kill(T** arr)
{
    free((char*)arr-2*sizeof(int));
}

int rows(T**arr)
{
    return *(int*)((char*)arr-2*sizeof(int));
}

int cols(T**arr)
{
    return *(int*)((char*)arr-sizeof(int));
}

Практически-то все нормально, а вот теоретически как?

Answer 1

К сожалению, препроцессор не знает значений sizeof, поэтому предполагаем, что int занимает 4 байта.

Тогда, с учетом того, что для обеспечения выравнивания данных после массива указателей в общем объеме выделенной памяти возможно придется добавить дополнительный промежуток, получается что-то в таком духе

#include <stdio.h>
#include <stdlib.h>

#if Arch1
#define ALI 4
#elif Arch2
#define ALI 64
#elif Arch3
#define ALI 32
#endif

#ifndef ALI  
#define ALI 16
#endif

// в предположении, что sizeof(int) == 4
#if ALI < 8
#undef ALI
#define ALI (2 * sizeof(int))
#endif

T **
create_a (int N, int M)
{
  printf("create_a: ALI %d\n", (int)ALI);
  // такое количество памяти нужно под указатели на строки и pad для выравнивания данных на ALI
  size_t data_ofs = (N * sizeof(T *) + ALI - 1) & ~(ALI - 1);
  int *d = malloc(ALI + data_ofs + N * M * sizeof(T));

  if (!d)
    return 0;
  d[0] = N, d[1] = M;

  printf("malloc = %p\n", d);
  return (T**)((char *)d + ALI);
}


T **
create_array (int N, int M)
{
  T **arr = create_a(N, M);
  if (!arr)
    return 0;

  for (int i = 0, ofs = (N * sizeof(T *) + ALI - 1) & ~(ALI - 1);
       i < N;
       i++, ofs += M * sizeof(T))
    arr[i] = (T*)((char*)arr + ofs);

  return arr;
}


void
kill_a (T **a)
{
  free((void *)a - ALI);
}

int
rows_a (T **a)
{
  int *d = (void *)a - ALI; 
  return d[0];
}

int
cols_a (T **a)
{
  int *d = (void *)a - ALI;
  return d[1];
}


int
main ()
{
  printf("T sizeof: %ld\n", sizeof(T));

  T **arr;
  printf("arr ptrs: %p\n", arr = create_array(N, M));
  printf("rows: %d  cols: %d\n", rows_a(arr), cols_a(arr));
  kill_a(arr);
    
  return puts("End") == EOF;
}

Результаты запусков

avp@avp-desktop:~/avp/hashcode$ gcc ttt.c -DT='long double' -DArch1
avp@avp-desktop:~/avp/hashcode$ ./a.out
T sizeof: 16
create_a: ALI 8
malloc = 0x7f4eb3e49010
arr ptrs: 0x7f4eb3e49018
rows: 100  cols: 200
End
avp@avp-desktop:~/avp/hashcode$ gcc ttt.c -DT='long double' -DArch3
avp@avp-desktop:~/avp/hashcode$ 
avp@avp-desktop:~/avp/hashcode$ ./a.out
T sizeof: 16
create_a: ALI 32
malloc = 0x7ff0539a5010
arr ptrs: 0x7ff0539a5030
rows: 100  cols: 200
End
avp@avp-desktop:~/avp/hashcode$ gcc ttt.c -DT='long double'
avp@avp-desktop:~/avp/hashcode$ ./a.out
T sizeof: 16
create_a: ALI 16
malloc = 0x7fae10586010
arr ptrs: 0x7fae10586020
rows: 100  cols: 200
End
avp@avp-desktop:~/avp/hashcode$

Answer 2

Учитывая, что основное, что вызывает беспокойство — это корректное выравнивание выравнивание указателей и данных, то я бы сделал это как-то так:

#include <stddef.h>
#include <stdlib.h>
#include <stdalign.h>


struct matrix_head {
  int N;
  int M;
  T *arr[];
};

struct matrix_head* arr2mh(T** arr) {
    return ((void*)arr - offsetof(struct matrix_head, arr));
}

T** create(int N, int M) {
    // Размер заголовка матрицы вместе с массивом указателей
    size_t matrix_head_sz = sizeof(struct matrix_head)+N*sizeof(T);
    // Маска выравнивания например для alignof(T)==16 => 0x0..00f
    const unsigned long align_mask = alignof(T)-1;
    // Вычисление, сколько потребуется дополнительного паддинга,
    // чтобы получить корректное выравнивание для массива данных.
    size_t data_padding = matrix_head_sz & align_mask ?
                          alignof(T) - (matrix_head_sz & align_mask) : 0;

    struct matrix_head* mh = malloc( matrix_head_sz + data_padding + N*M*sizeof(T) );
    mh->N = N;
    mh->M = M;

    T* data = (void*)mh + matrix_head_sz + data_padding;

    for(int i = 0; i<N; i++) {
        mh->arr[i] = data + i*M;
    }

    return mh->arr;
}

void kill(T** arr)
{
    free(arr2mh(arr));
}

int rows(T**arr)
{
    return arr2mh(arr)->N;
}

int cols(T**arr)
{
    return arr2mh(arr)->M;
}

Замечания:

Код не отлаживался и может содержать ошибки
Гибкие массивы-члены (Flexible array member) — часть стандарта со времён C99, но AFAIK как расширение поддерживались компиляторами (как минимум, gcc и msvc) и раньше; для древних компиляторов можно использовать arr[0] или arr[1]; в последнем случае единичку из sizeof() придётся вычитать вручную.
Компилятор сам заботится о выравнивании массива указателей в такой структуре
Выравнивание массива данных придётся делать вручную
alignof() добавлен только в C11
offsetof() в стандарте со времён царя Гороха
Мне не нравится использование ненужного массива указателей: я бы убрал его и использовал бы для адресации либо макросы (через i*M+j), либо VLA, но раз такая структура данных в ТЗ, то кто я такой, чтобы с этим спорить…

БЛОГ НА HUSL

Двумерный массив и очередной UB

Ответы (2 шт):