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

Question

Я пытаюсь написать пользовательский распределитель для целей отладки (как упражнение) на 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] Изменена структура блока в соответствии с предложениями услуг.

Answer 1

Почему вы используете союз? Просто используйте 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)); 

Answer 2

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

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

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

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

Answer 3

Если вы хотите, чтобы не использовать таНос(), вы должны взглянуть на sbrk

Answer 4

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

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

Answer 5

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

#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.

Answer 6

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

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

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

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

Answer 7

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

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

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

---

Предполагая, что вы получите ваш блок памяти из «таНос()», то вы могли бы сделать - грубо:

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; 
} 

Существует некоторая интерпретация осталось сделать ...