История изменений
Исправление KivApple, (текущая версия) :
malloc округляет запрошенный размер до размера структуры свободного блока. Так что у free не будет проблем положить туда свои данные при освобождении. Но пока он их туда не положил, мы можем дать юзеру использовать эту память в своих целях вместо резервирования её.
Пусть адрес 4 байта, структура занятого блока 4 байта (только размер), структура свободного блока 8 байт (размер и указатель на следующий свободный блок). Юзер запросил 1 байт, округляем до (8 - 4) = 4 (разница между свободным и занятым заголовком блока), прибавляем 4 (размер занятого заголовка), снова округляем уже до 8 (размер свободного заголовка). В итоге реально выделяем 8 байт, инициализируем заголовок занятого блока, возвращаем юзеру базовый адрес + 4. При освобождении читаем заголовок занятого блока и инициализируем заголовок свободного, мы знаем, что блоков меньше реальных 8 байт не существует, поэтому можем свободно инициализировать структуру большего размера, чем заголовок занятого блока. При этом мы портим тот самый 1 байт, которые там хранил пользователь, но мы имеем на это право - после free пользователь не должен обращаться к блоку по контракту этой функции. Если этот блок снова выделяется malloc, то он удаляется из списка свободных и вновь инициализируется маленький заголовок занятого блока. Теперь эти вторые 4 байта блока вновь не используются менеджером и юзер снова может в них писать.
В реальном менеджере есть несколько граничных случаев. Malloc может не только вернуть исходно свободный блок на 8 байт, но и отрезать 8 байт от свободного блока большего размера, однако из-за округление всех размеров до 8, остаток после отрезания гарантированно сохранит кратность 8. Free может не только создать свободный блок, но и приклеить к смежному, если он есть, но склеивание двух блоков с размером кратным 8 гарантированно породит блок размера кратного 8. Здесь тоже никаких проблем.
Исправление KivApple, :
malloc округляет запрошенный размер до размера структуры свободного блока. Так что у free не будет проблем положить туда свои данные при освобождении. Но пока он их туда не положил, мы можем дать юзеру использовать эту память в своих целях вместо резервирования её.
Пусть адрес 4 байта, структура занятого блока 4 байта (только размер), структура свободного блока 8 байт (размер и указатель на следующий свободный блок). Юзер запросил 1 байт, округляем до (8 - 4) = 4 (разница между свободным и занятым заголовком блока), прибавляем 4 (размер занятого заголовка). В итоге реально выделяем 8 байт, инициализируем заголовок занятого блока, возвращаем юзеру базовый адрес + 4. При освобождении читаем заголовок занятого блока и инициализируем заголовок свободного, мы знаем, что блоков меньше реальных 8 байт не существует, поэтому можем свободно инициализировать структуру большего размера, чем заголовок занятого блока. При этом мы портим тот самый 1 байт, которые там хранил пользователь, но мы имеем на это право - после free пользователь не должен обращаться к блоку по контракту этой функции. Если этот блок снова выделяется malloc, то он удаляется из списка свободных и вновь инициализируется маленький заголовок занятого блока. Теперь эти вторые 4 байта блока вновь не используются менеджером и юзер снова может в них писать.
В реальном менеджере есть несколько граничных случаев. Malloc может не только вернуть исходно свободный блок на 8 байт, но и отрезать 8 байт от свободного блока большего размера, однако из-за округление всех размеров до 8, остаток после отрезания гарантированно сохранит кратность 8. Free может не только создать свободный блок, но и приклеить к смежному, если он есть, но склеивание двух блоков с размером кратным 8 гарантированно породит блок размера кратного 8. Здесь тоже никаких проблем.
Исправление KivApple, :
malloc округляет запрошенный размер до размера структуры свободного блока. Так что у free не будет проблем положить туда свои данные при освобождении. Но пока он их туда не положил, мы можем дать юзеру использовать эту память в своих целях вместо резервирования её.
Пусть адрес 4 байта, структура занятого блока 4 байта (только размер), структура свободного блока 8 байт (размер и указатель на следующий свободный блок). Юзер запросил 1 байт, округляем до (8 - 4) = 4 (разница между свободным и занятым заголовком блока), прибавляем 4 (размер занятого заголовка). В итоге реально выделяем 8 байт, инициализируем заголовок занятого блока, возвращаем юзеру базовый адрес + 4. При освобождении читаем заголовок занятого блока и инициализируем заголовок свободного, мы знаем, что блоков меньше реальных 8 байт не существует, поэтому можем свободно инициализировать структуру большего размера, чем заголовок занятого блока. При этом мы портим тот самый 1 байт, которые там хранил пользователь, но мы имеем на это право - после free пользователь не должен обращаться к блоку по контракту этой функции. Если этот блок снова выделяется malloc, то он удаляется из списка свободных и вновь инициализируется маленький заголовок занятого блока. Теперь эти вторые 4 байта блока вновь не используются менеджером и юзер снова может в них писать.
Исправление KivApple, :
malloc округляет запрошенный размер до размера структуры свободного блока. Так что у free не будет проблем положить туда свои данные при освобождении. Но пока он их туда не положил, мы можем дать юзеру использовать эту память в своих целях вместо резервирования её.
Пусть адрес 4 байта, структура занятого блока 4 байта (только размер), структура свободного блока 8 байт (размер и указатель на следующий свободный блок). Юзер запросил 1 байт, округляем до (8 - 4) = 4 (разница между свободным и занятым заголовком блока), прибавляем 4 (размер занятого заголовка). В итоге реально выделяем 8 байт, инициализируем заголовок занятого дока, возвращаем юзеру базовый адрес + 4. При освобождении читаем заголовок занятого блока и инициализируем заголовок свободного, мы знаем, что блоков меньше реальных 8 байт не существует, поэтому можем свободно инициализировать структуру большего размера, чем заголовок занятого блока. При этом мы портим тот самый 1 байт, которые там хранил пользователь, но мы имеем на это право - после free пользователь не должен обращаться к блоку по контракту этой функции. Если этот блок снова выделяется malloc, то он удаляется из списка свободных и вновь инициализируется маленький заголовок занятого блока. Теперь эти вторые 4 байта блока вновь не используются менеджером и юзер снова может в них писать.
Исходная версия KivApple, :
malloc округляет запрошенный размер до размера структуры свободного блока. Так что у free не будет проблем положить туда свои данные при освобождении. Но пока он их туда не положил, мы можем дать юзеру использовать эту память в своих целях вместо резервирования её.
Адрес 4 байта, структура занятого блока 4 байта (только размер), структура свободного блока 8 байт (размер и указатель на следующий свободный блок). Юзер запросил 1 байт, округляем до (8 - 4) = 4 (разница между свободным и занятым заголовком блока), прибавляем 4 (размер занятого заголовка). В итоге реально выделяем 8 байт, инициализируем заголовок занятого дока, возвращаем юзеру базовый адрес + 4. При освобождении читаем заголовок занятого блока и инициализируем заголовок свободного, мы знаем, что блоков меньше реальных 8 байт не существует, поэтому можем свободно инициализировать структуру большего размера, чем заголовок занятого блока. При этом мы портим тот самый 1 байт, которые там хранил пользователь, но мы имеем на это право - после free пользователь не должен обращаться к блоку по контракту этой функции. Если этот блок снова выделяется malloc, то он удаляется из списка свободных и вновь инициализируется маленький заголовок занятого блока. Теперь эти вторые 4 байта блока вновь не используются менеджером и юзер снова может в них писать.