объяснение согласованной реализации malloc

Это не домашнее задание, это чисто мое личное образование.

Я не мог понять, как реализовать выровненный malloc, поэтому посмотрел онлайн и нашелэтот сайт, Для удобства чтения я выложу код ниже:

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

void* aligned_malloc(size_t required_bytes, size_t alignment)
{
    void* p1; // original block
    void** p2; // aligned block
    int offset = alignment - 1 + sizeof(void*);
    if ((p1 = (void*)malloc(required_bytes + offset)) == NULL)
    {
       return NULL;
    }
    p2 = (void**)(((size_t)(p1) + offset) & ~(alignment - 1));
    p2[-1] = p1;
    return p2;
}

void aligned_free(void *p)
{
    free(((void**)p)[-1]);
}

void main (int argc, char *argv[])
{
    char **endptr;
    int *p = aligned_malloc (100, strtol(argv[1], endptr, 10));

    printf ("%s: %p\n", argv[1], p);
    aligned_free (p);
}

Реализация работает, но я, честно говоря, не могу понять, как она работает.

Вот что я не могу понять:

Почему нам нужно смещение?Что делает с~(alignment - 1) выполнятьp2 это двойной указатель Почему мы можем вернуть его из функции, которая должна возвращать только один указатель?Каков общий подход к решению этой проблемы?

Любая помощь очень ценится.

РЕДАКТИРОВАТЬ

Это не дубликатКак выделить выровненную память только с использованием стандартной библиотеки? потому что мне также нужно знать, как освободить выровненную память.

 Paul Hankin29 июн. 2016 г., 04:01
Также:size_t (в строке, которая устанавливаетp2) должно бытьuintptr_t, Там нет никакой гарантии, чтоsize_t достаточно велик, чтобы представлять значения указателя.
 Paul Hankin30 июн. 2016 г., 01:41
@flashburn Линияp2[-1] = p1 требует, чтобыp2 выравнивается с любым значением, необходимым для записиvoid* ценности через это. Но, глядя на код еще раз, я думаю, что я ошибся, что это выравнивание нарушается, еслиaligned меньше, чем это значение:p2 всегда заканчивается теми же гарантиями выравнивания, что иmalloc.
 flashburn29 июн. 2016 г., 20:11
@PaulHankin В своем первом комментарии вы сказали:it assumes your alignment is at least as large as required for void*, Я не уверен, что понимаю это утверждение. Можете ли вы рассказать подробнее?
 Paul Hankin29 июн. 2016 г., 03:51
Это работает только еслиaligned это степень 2, и это предполагает, что ваше выравнивание, по крайней мере, так велико, как требуется дляvoid*.
 chux29 июн. 2016 г., 15:51
@Daniel Rudy Предложенный дубликат хорошо ответит, каквыделять выровненная память. Он не рассматривает и не отвечает, как освободить эту память, как пытается сделать этот код. В предложенном дублировании освобождение выполняется с оригинальным указателем, а его хранение не детализировано. Здесь код пытается сохранить / восстановить исходный указатель в выделенном блоке.

Ответы на вопрос(3)

Возможно, но я не был бы слишком уверен. ИМО, тебе лучше работать с первыми принципами. С места в карьер,

p1 = (void*)malloc

это красный флаг.malloc возвращаетсяvoid, В C любой указатель может быть назначен изvoid *, Кастинг отmalloc обычно считается плохой формой, потому что любой эффект, который он имеет, может быть только плохим.

Почему нам нужно смещение

Смещение предоставляет место для хранения указателя, возвращенногоmalloc, использованный позжеfree.

p1 извлекается изmalloc, Позже, это должно быть предоставленоfree будет выпущен.aligned_malloc резервыsizeof(void*) байт вp1, тайникиp1 там и возвращаетсяp2 (первый «выровненный» адрес в блоке, которыйp1 указывает на). Позже, когда звонящий проходитp2 вaligned_freeконвертируетp2 в действительностиvoid *p2[]и получает оригиналp1 используя -1 в качестве индекса.

Что достигается с помощью ~ (выравнивание - 1)

Это то, что ставитp2 на границе. Скажем, выравнивание 16;alignment -1 15, 0xF.~OxF все биты, кроме последних 4. Для любого указателяP, P & ~0xF будет кратным 16.

p2 это двойной указатель

указательschmointer. malloc возвращаетсяvoid*, Это блок памяти; вы обращаетесь к нему как хотите. Вы не будете моргать на

char **args = calloc(7, sizeof(char*));

выделить массив из 7char * указатели, не так ли? Код выбирает какое-то «выровненное» местоположение как минимумsizeof(void*) байты изp1 и для целейfree, трактует это какvoid **.

Каков общий подход

Там нет одного ответа. Лучше всего использовать стандартную (или популярную) библиотеку. Если вы строите на вершинеmallocвыделение достаточного количества для сохранения «реального» указателя и возвращение выровненного указателя довольно стандартно, хотя я бы кодировал его по-другому. Системный вызовmmap возвращает выровненный указатель страницы, который будет удовлетворять большинству критериев для «выровненного». В зависимости от необходимости, это может быть лучше или хуже, чем спекуляция наmalloc.

 flashburn29 июн. 2016 г., 18:35
@chux Что означает аббревиатура UB?
 flashburn29 июн. 2016 г., 20:18
@James K. Lowden Мне все еще неясно, почему возврат двойного указателя из функции, которая должна возвращать только один указатель, не вызывает ошибку. Не могли бы вы подробнее остановиться на этом? Похоже, мне не хватает чего-то важного в Си, но я не совсем понимаю, что это такое.
 flashburn29 июн. 2016 г., 20:15
@chux Не могли бы вы подробнее рассказать о том, почему void ** нужно выравнивать. Почему для этого случая его нужно выровнять? Я думаю, что конкретный пример может помочь.
 chux29 июн. 2016 г., 22:49
 flashburn29 июн. 2016 г., 20:52
@ Chux Я даже не понимаю, если он выровнен дляchar ** Можете ли вы объяснить, почему он должен быть приведен в соответствиеchar **
 flashburn29 июн. 2016 г., 21:45
@chuxThat value must be aligned for a char *, Можете ли вы объяснить, почемуchar * должны быть выровнены? Почему бы и нетint * или простоint или почему нетshort *почему конкретноchar *?
 flashburn29 июн. 2016 г., 21:48
@chux, чтобы перевести обсуждение в чат, нам нужно сделать это. Я не уверен, как это сделать без этого. Я думаю, мы могли бы опубликовать больше сообщений, а затем просто удалить их.

p1 = (void*)malloc Вы не приводите возвращаемое значение malloc.free(((void**)p)[-1]); Вы не разыгрываете бесплатно.if ((p1 = (void*)malloc(required_bytes + offset)) == NULL) Не помещайте присваивание внутри сравнения оператора if. Я знаю, что многие люди делают это, но, на мой взгляд, это просто дурной тон и затрудняет чтение кода.

То, что они делают здесь, хранит оригинальный указатель внутри выделенного блока. Это означает, что только выровненный указатель возвращается пользователю. Фактический указатель, который возвращает malloc, пользователь никогда не видит. Вы должны сохранить этот указатель, потому что он нужен, чтобы освободить блок от выделенного списка и поместить его в свободный список. Во главе каждого блока памяти malloc помещает некоторую служебную информацию. Такие вещи, как указатели next / prev, размер, состояние размещения и т. Д. .... Некоторые отладочные версии malloc используют защитные слова, чтобы проверить, не переполнилось ли что-либо в буфере. Выравнивание, которое передается в рутинуДОЛЖЕН быть силой 2.

Когда я написал свою собственную версию malloc для использования в распределителе пула, минимальный размер блока, который я использовал, составлял 8 байт. Таким образом, включая заголовок для 32-разрядной системы, общая сумма составила 28 байт (20 байт для заголовка). В 64-битной системе это было 40 байтов (32 байта для заголовка). Большинство систем имеют повышенную производительность, когда данные выровнены по некоторому значению адреса (4 или 8 байтов в современных компьютерных системах). Причина этого в том, что машина может захватить все слово за один цикл шины, если оно выровнено. Если нет, то для получения всего слова требуется два шинных цикла, а затем его нужно построить. Вот почему компиляторы выравнивают переменные по 4 или 8 байтов. Это означает, что последние 2 или 3 бита адресной шины равны нулю.

Я знаю, что есть некоторые аппаратные ограничения, которые требуют большего выравнивания, чем стандартные 4 или 8. Система Nvidia CUDA, если я правильно помню, требует, чтобы вещи были выровнены по 256 байтам ... и это требование к оборудованию.

Об этом уже спрашивали раньше. Увидеть:Как выделить выровненную память только с использованием стандартной библиотеки?

Надеюсь это поможет.

 chux29 июн. 2016 г., 15:41
Код используетfree(((void**)p)[-1]); найти оригинальный указатель. Если следовать «не бросать бесплатно», как бы вы кодaligned_free()?

если вы хотите поддерживать выравнивания сверх того, что есть в вашей системеmalloc() делает. Например, если ваша системаmalloc() выравнивает до 8-байтовых границ, и вы хотите выровнять до 16 байт, вы запрашиваете 15 дополнительных байтов, поэтому вы точно знаете, что можете изменить результат, чтобы выровнять его по запросу. Вы также добавляетеsizeof(void*) до размера, который вы передаетеmalloc() оставить место для бухгалтерии.

~(alignment - 1) это то, что гарантирует выравнивание. Например, если выравнивание равно 16, то вычтите 1, чтобы получить 15, то есть 0xF, затем отрицание его дает 0xFF..FF0, которая является маской, необходимой для выравнивания для любого возвращаемого указателя изmalloc(), Обратите внимание, что этот трюк предполагает, что выравнивание является степенью 2 (что обычно бывает, но на самом деле должна быть проверка).

Этоvoid**, Функция возвращаетvoid*, Это нормально, потому что указатель на void - это «указатель на любой тип», и в этом случае этот типvoid*, Другими словами, преобразованиеvoid* и из других типов указателей допускается, и двойной указатель по-прежнему является указателем.

Общая схема здесь заключается в том, чтобы сохранить исходный указатель до того, который будет возвращен вызывающей стороне. Некоторые реализации стандартаmalloc() сделать то же самое: спрятать бухгалтерскую информацию перед возвращенным блоком. Это позволяет легко узнать, сколько места нужно вернуть, когдаfree() называется.

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

 Paul Hankin29 июн. 2016 г., 03:58
Вы можете отметить, что в 2alignment должно быть степень 2. Лично я бы просто использовал% а не суетиться здесь -malloc это уже относительно дорого, и дополнительный разрыв не будет иметь никакого значения для производительности.
 Paul Hankin29 июн. 2016 г., 03:56
Это может быть полезно: выравнивание данных по строкам кэша и подготовка данных для странного оборудования (например, некоторых специализированных графических устройств) - это два, которые я видел в реальном мире.

Ваш ответ на вопрос