Пользовательский дизайн заголовка реализации malloc () - PullRequest
Новая
       33

Пользовательский дизайн заголовка реализации malloc ()

6 голосов
/ 09 ноября 2009

Я пытаюсь написать собственный распределитель для целей отладки (как упражнение) на C, где я буду использовать один связанный список для скрепления свободного списка памяти с использованием алгоритма First Fit. Ниже показана структура, которую я хотел бы создать в «Пустом узле памяти».

Как мне записать блок заголовка (объединение, чтобы быть конкретным) в первые несколько байтов памяти, которые я получаю (я использую malloc () для первоначального получения порции памяти), чтобы оставшиеся байты были свободными

Это объединение, которое я использую: 

/*Define Header Structure for proper alignment*/
union header {
struct{
    union header* next;
    unsigned size ; /*Make it size_t*/
}s; 
double dummy_align_var;
};

-------------------------------------------------------------------------------
|Next        |Size of  |16Byte| User is concerned only about |16Byte|         |
|Free Memory |Allocated|Header| this portion  of memory      |Footer|Checksum |
|Address     |Block    |Picket| and has no knowledge of rest |Picket|         |
-------------------------------------------------------------------------------
|-------Header---------|      ^Address Returned to user
                              ^------User Requested Size-----^
^-------------Memory Obtained From The Operating System-----------------------^
*/

[EDIT] Изменена структура блока в соответствии с предоставленными предложениями.

Ответы [ 7 ]

3 голосов
/ 10 ноября 2009

Для отладки malloc рассмотрите возможность размещения отступа между вашей структурой управления и началом пользовательских данных, а также между концом пользовательских данных и контрольной суммой. Один байт заполнения должен быть нулевым байтом 0x00 - поэтому строковые операции останавливаются; рассмотрите возможность добавления другого как 0xFF. Если у вас есть фиксированный шаблон и вы заметили, что он изменился, вы знаете, что что-то вышло за пределы допустимого - но есть большая вероятность, что ваши конфиденциальные контрольные данные не будут растоптаны. Если вы используете 16 байтов заполнения по обе стороны от пространства, выделенного пользователю, вы можете пойти так далеко, чтобы поставить 4 байта с нулями, соответствующим образом выровненных (отсюда и 4-байтовое целое число ноль) и, возможно, 0xFFFFFFFF для -1. Кроме того, поскольку вы, вероятно, округлите запрошенный размер до значения, кратного базовому размеру блока, установите для байтов, которые пользователь не должен использовать, известное значение - и подтвердите, что они остаются неизменными. Это позволит обнаружить модификации «один на выделенной длине» или всего несколько байтов на выделенной длине, которые в противном случае могут остаться незамеченными.

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

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

Предполагая, что вы получаете блок памяти из 'malloc ()', вы должны сделать - примерно: 

void *my_malloc(size_t nbytes)
{
    size_t reqblocks = (nbytes + sizeof(header) - 1) / sizeof(header);
    size_t reqspace  = (reqblocks + 2) * sizeof(header) + 2 * sizeof(padding);
    void *space = malloc(reqspace);
    if (space == 0)
        return space;
    void *retval = (char *)space + sizeof(header) + sizeof(padding);
    header *head = space;
    head->next = ...next...;
    head->size = nbytes;
    ...set head padding to chosen value...
    ...set tail padding to chosen value...
    ...set gap between nbytes and block boundary to chosen value...
    return retval;
}

Осталось сделать некоторую интерпретацию ...

2 голосов
/ 09 ноября 2009

Я бы сделал что-то вроде 

#define MEM_ALIGN 4 // 8 on 64b eventually

struct header {
    union aligned_header {
        struct _s {
            union aligned_header* next;
            size_t size;
        } data;
        char dummy_align_var[sizeof(struct _s) + sizeof(struct _s)%MEM_ALIGN];
    } header_data;
    char user_address;
};

и возврат &user_address.

2 голосов
/ 09 ноября 2009

Почему вы используете профсоюз? Просто используйте struct и верните пользователю &dummy_align_var в качестве начала свободного блока.

О, и так как это для отладки, я предлагаю добавить mungwall: поместите 16 байтов с каждой стороны пользовательской области и заполните их каким-нибудь шаблоном (например, 0xdeadbeef, повторенный четыре раза). Во время free() убедитесь, что эти байты не изменились.

[EDIT] Вот какой-то псевдокод: 

struct header {
    struct header * next;
    unsigned size;
    // put mungwall here
    double user_data;
};

init()
    int blockSize = 1024;
    char * bigMem = original_malloc(blockSize);
    struct header * first = (struct header *)bigMem;
    first->next = NULL;
    first->size = blockSize - (sizeof(struct header) - sizeof(double));
1 голос
/ 10 ноября 2009

Вы можете использовать свой оригинальный союз, если хотите, например: 

union header *hdr = malloc(total_size);
void *user_ptr = hdr + 1;
char *trailer_ptr = (char *)user_ptr + user_size;

Это установит user_ptr в том месте, где начнется следующий union header, если блок malloc ed рассматривается как массив этих объединений. Так что это значение, которое вы возвращаете пользователю.

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

1 голос
/ 09 ноября 2009

Предлагаю, было бы полезно: Несколько лет назад мне нужно было выполнить резервное копирование средства malloc () для целей отладки (распределитель трассировки и т. Д.) ... И было довольно просто взять реализацию FreeBSD из их libstdc. Это было, как я помню, поздние выпуски FreeBSSD 5.0 ​​или даже 4.x, но забавно то, что их средство было изолировано в модуле простой библиотеки malloc.o, поэтому перегрузка этого слоя была очень простой копией и вставкой, и реализация была действительно хорошей.

Вы действительно делаете всю эту работу? Да, это только пункт, чтобы проверить, я не претендую, что это решение является лучшим.

1 голос
/ 09 ноября 2009

Вы также можете объявить dummy_align_var как union header* prev, чтобы вы могли поместить свободные блоки памяти в двусвязный список.

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

И, наконец, вы не упоминаете об этом, поскольку сортировка списка по размеру позволяет быстрее находить лучший блок для распределения по заданному запросу, а сортировка по адресу облегчает объединение освобожденных блоков. Если вы хотите сделать то и другое, сделайте пользовательскую часть размером не менее 3 header*, чтобы она соответствовала указателям, необходимым при освобождении блока.

В дополнение к упомянутым Аароном границам, перезаписывайте освобожденные буферы с тем же шаблоном. Это облегчает распознавание кода, который использует уже освобожденные буферы.

0 голосов
/ 09 ноября 2009

Если вы не хотите использовать malloc (), вы должны посмотреть на sbrk

...