Оригинальный ответ
{
void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
}
Фиксированный ответ
{
void *mem = malloc(1024+15);
void *ptr = ((uintptr_t)mem+15) & ~ (uintptr_t)0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
}
Объяснение по запросу
Первый шаг - выделить достаточно свободного места на всякий случай. Поскольку память должна быть выровнена на 16 байтов (это означает, что адрес начального байта должен быть кратным 16), добавление 16 дополнительных байтов гарантирует, что у нас будет достаточно места. Где-то в первых 16 байтах есть 16-байтовый выровненный указатель. (Обратите внимание, что malloc() должен возвращать указатель, который достаточно хорошо выровнен для любой цели. Однако значение 'any' в первую очередь относится к таким вещам, как базовые типы - long, double , long double, long long, а также указатели на объекты и указатели на функции. Когда вы выполняете более специализированные действия, например, играете с графическими системами, им может потребоваться более строгое выравнивание, чем в остальной системе - отсюда такие вопросы и ответы это.)
Следующим шагом является преобразование пустого указателя в указатель на символ; GCC, несмотря на это, вы не должны выполнять арифметику указателей на пустых указателях (и GCC имеет опции предупреждения, чтобы сообщить вам, когда вы злоупотребляете им). Затем добавьте 16 к стартовому указателю. Предположим, что malloc() вернул вам неверно выровненный указатель: 0x800001. Добавление 16 дает 0x800011. Теперь я хочу округлить до 16-байтовой границы - поэтому я хочу сбросить последние 4 бита до 0. 0x0F имеет последние 4 бита, равные единице; следовательно, ~0x0F имеет все биты, установленные в один, кроме последних четырех. И, что с 0x800011 дает 0x800010. Вы можете перебрать другие смещения и увидеть, что работает та же арифметика.
Последний шаг, free(), прост: вы всегда и только возвращаете free() значение, которое вам вернулось из malloc(), calloc() или realloc() - все остальное - катастрофа , Вы правильно указали mem для хранения этого значения - спасибо. Бесплатно выпускает его.
Наконец, если вы знаете о внутренних компонентах пакета malloc вашей системы, вы можете догадаться, что он вполне может вернуть 16-байтовые данные (или 8-байтовые). Если бы он был выровнен по 16 байтам, вам не пришлось бы копаться со значениями. Однако это хитроумно и непереносимо - другие пакеты malloc имеют различное минимальное выравнивание, и поэтому одно допущение, когда он делает что-то другое, приведет к дампам ядра. В широких пределах это решение переносимо.
Кто-то еще упомянул posix_memalign() как еще один способ получить выровненную память; это не доступно везде, но часто может быть реализовано с использованием этого в качестве основы. Обратите внимание, что было удобно, чтобы выравнивание было степенью 2; другие выравнивания сложнее.
Еще один комментарий - этот код не проверяет, что выделение прошло успешно.
Поправка
Программист Windows отметил, что вы не можете выполнять операции с битовой маской для указателей, и, действительно, GCC (протестированные 3.4.6 и 4.3.1) действительно жалуется на это. Итак, исправленная версия основного кода - преобразованная в основную программу, следует. Я также позволил себе добавить только 15 вместо 16, как было указано. Я использую uintptr_t, так как C99 существует достаточно долго, чтобы быть доступным на большинстве платформ. Если бы не использование PRIXPTR в операторах printf(), было бы достаточно #include <stdint.h> вместо использования #include <inttypes.h>. [Этот код включает исправление, обозначенное CR , которое повторяло точку, впервые высказанную Биллом K несколько лет назад, которую мне удалось пропустить до сих пор. ]
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void memset_16aligned(void *space, char byte, size_t nbytes)
{
assert((nbytes & 0x0F) == 0);
assert(((uintptr_t)space & 0x0F) == 0);
memset(space, byte, nbytes); // Not a custom implementation of memset()
}
int main(void)
{
void *mem = malloc(1024+15);
void *ptr = (void *)(((uintptr_t)mem+15) & ~ (uintptr_t)0x0F);
printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
memset_16aligned(ptr, 0, 1024);
free(mem);
return(0);
}
А вот немного более обобщенная версия, которая будет работать для размеров, имеющих степень 2:
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void memset_16aligned(void *space, char byte, size_t nbytes)
{
assert((nbytes & 0x0F) == 0);
assert(((uintptr_t)space & 0x0F) == 0);
memset(space, byte, nbytes); // Not a custom implementation of memset()
}
static void test_mask(size_t align)
{
uintptr_t mask = ~(uintptr_t)(align - 1);
void *mem = malloc(1024+align-1);
void *ptr = (void *)(((uintptr_t)mem+align-1) & mask);
assert((align & (align - 1)) == 0);
printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
memset_16aligned(ptr, 0, 1024);
free(mem);
}
int main(void)
{
test_mask(16);
test_mask(32);
test_mask(64);
test_mask(128);
return(0);
}
Чтобы преобразовать test_mask() в функцию распределения общего назначения, единственное возвращаемое значение от распределителя должно было бы кодировать адрес освобождения, как указали несколько человек в своих ответах.
Проблемы с интервьюерами
Uri прокомментировал: Может быть, у меня сегодня утром проблема с пониманием прочитанного, но если вопрос об интервью конкретно говорит: «Как бы вы распределили 1024 байта памяти», а вы явно выделяете больше, чем это. Разве это не будет автоматический сбой интервьюера?
Мой ответ не помещается в комментарий из 300 символов ...
Это зависит, я полагаю. Я думаю, что большинство людей (включая меня) восприняли вопрос так: «Как бы вы распределили пространство, в котором можно хранить 1024 байта данных, и где базовый адрес кратен 16 байтам». Если интервьюер действительно имел в виду, как вы можете выделить 1024 байта (только) и выровнять его по 16 байтов, то параметры более ограничены.
- Очевидно, что одна возможность состоит в том, чтобы выделить 1024 байта и затем дать этому адресу «обработку выравнивания»; проблема с этим подходом состоит в том, что фактическое доступное пространство не является должным образом определенным (используемое пространство находится между 1008 и 1024 байтами, но не было механизма, позволяющего указать, какой размер), что делает его менее полезным.
- Другая возможность состоит в том, что вы должны написать полный распределитель памяти и убедиться, что возвращаемый вами 1024-байтовый блок соответствующим образом выровнен. Если это так, вы, вероятно, в конечном итоге выполните операцию, аналогичную той, которая была предложена, но вы скрываете ее в распределителе.
Однако, если бы интервьюер ожидал любого из этих ответов, я бы ожидал, что они признают, что это решение отвечает на тесно связанный вопрос, а затем пересмотрят свой вопрос, чтобы направить разговор в правильном направлении. (Кроме того, если интервьюер стал действительно неуклюжим, я бы не хотел эту работу; если ответ на недостаточно точное требование сгорел без исправления, тогда интервьюер - это не тот, для кого безопасно работать.)
мир движется
Название вопроса недавно изменилось. Это было Решить вопрос о выравнивании памяти в вопросе об интервью C, которое поставило меня в тупик . Пересмотренный заголовок ( Как выделить выровненную память только с использованием стандартной библиотеки? ) требует слегка пересмотренного ответа - это дополнение содержит его.
C11 (ISO / IEC 9899: 2011) добавлена функция aligned_alloc():
7.22.3.1 Функция aligned_alloc
Конспект
#include <stdlib.h>
void *aligned_alloc(size_t alignment, size_t size);
Описание
Функция aligned_alloc выделяет пространство для объекта, выравнивание которого
определяется alignment, размер которого указан size, а значение равно
неопределенный. Значение alignment должно быть действительным выравниванием, поддерживаемым реализацией, а значение size должно быть целым кратным alignment.
Возвращает
Функция aligned_alloc возвращает либо нулевой указатель, либо указатель на выделенное пространство.
И POSIX определяет posix_memalign():
#include <stdlib.h>
int posix_memalign(void **memptr, size_t alignment, size_t size);
ОПИСАНИЕ
Функция posix_memalign() должна выделять size байтов, выровненных по границе, указанной в alignment, и должна возвращать указатель на выделенную память в memptr. Значение alignment должно быть кратно sizeof(void *).
.
После успешного завершения значение, на которое указывает memptr, должно быть кратно alignment.
Если размер запрошенного пространства равен 0, поведение определяется реализацией; значение, возвращаемое в memptr, должно быть либо нулевым, либо уникальным указателем.
Функция free() освобождает память, ранее выделенную posix_memalign().
ВОЗВРАЩАЕМОЕ ЗНАЧЕНИЕ
После успешного завершения posix_memalign() возвращает ноль; в противном случае возвращается номер ошибки, чтобы указать на ошибку.
Любой или оба из них могут быть использованы для ответа на вопрос сейчас, но только функция POSIX была опцией, когда на вопрос был первоначально дан ответ.
За кулисами новая выровненная функция памяти выполняет почти ту же работу, что и описанную в вопросе, за исключением того, что она способна упростить принудительное выравнивание и отслеживает начало выровненной памяти внутри, чтобы код не нужно специально разбираться - он просто освобождает память, возвращаемую использованной функцией выделения.