История изменений

Зачем пузырек? Я поддерживал упорядоченность свободных блоков по базовым адресам. Таким образом free должен был просто пробежаться по списку свободных блоков, пока не найдёт нужное место для вставки, а затем проверить ровно два кандидата на слияние - предыдущий и следующий свободный блок. Никакого O(N^2), обычный O(N) для худшего случая. Malloc же брал первый попавшийся блок подходящего размера, опять же O(N) в худшем случае, на практике если куча не совсем фрагментирована, то гораздо быстрее (обычно в начале кучи был огромный блок, который никак не мог кончиться, поэтому поиск на нём оканчивался).

O(N) вполне приемлемо для базового аллокатора. Конечно, дальше можно наворачивать оптимизации типа поддержания разных списков свободных блоков для разных размеров (slab allocator) или сделать дерево вместо линейного списка (для уменьшения сложности free с O(N) до O(logN), не знаю используется ли это где-то, просто первое что пришло в голову), но для игрушечной ОС это избыточно. И такие менеджеры точно так же могут часть своих структур хранить в освобождённый памяти.

Мой пойнт в том, что free может портить данные в освобожденной памяти даже в очень триаиальной реализации аллокатора (и раз я до неё сходу догадался в 17 лет и она даёт выигрыш по памяти, то деды 30 лет назад тоже должны были). Так что без всяких mmap обращаться по освобожденному адресу плохая идея. Там может быть какая-то структура учёта свободных блоков вместо твоих данных.

Зачем пузырек? Я поддерживал упорядоченность свободных блоков по базовым адресам. Таким образом free должен был просто пробежаться по списку свободных блоков, пока не найдёт нужное место для вставки, а затем проверить ровно два кандидата на слияние - предыдущий и следующий свободный блок. Никакого O(N^2), обычный O(N) для худшего случая. Malloc же брал первый попавшийся блок подходящего размера, опять же O(N) в худшем случае, на практике если куча не совсем фрагментирована, то гораздо быстрее (обычно в начале кучи был огромный блок, который никак не мог кончиться, поэтому поиск на нём оканчивался).

O(N) вполне приемлемо для базового аллокатора. Конечно, дальше можно наворачивать оптимизации типа поддержания разных списков свободных блоков для разных размеров (slab allocator) или сделать дерево вместо линейного списка (для уменьшения сложности free с O(N) до O(logN), не знаю используется ли это где-то, просто первое что пришло в голову), но для игрушечной ОС это избыточно. И такие менеджеры точно так же могут часть своих структур хранить в освобождённый памяти.

Мой пойнт в том, что free может портить данные в освобожденной памяти даже в очень триаиальной реализации аллокатора (и раз я до неё сходу догадался и она даёт выигрыш по памяти, то деды 30 лет назад тоже должны были). Так что без всяких mmap обращаться по освобожденному адресу плохая идея. Там может быть какая-то структура учёта свободных блоков вместо твоих данных.

Зачем пузырек? Я поддерживал упорядоченность свободных блоков по базовым адресам. Таким образом free должен был просто пробежаться по списку свободных блоков, пока не найдёт нужное место для вставки, а затем проверить ровно два кандидата на слияние - предыдущий и следующий свободный блок. Никакого O(N^2), обычный O(N) для худшего случая. Malloc же брал первый попавшийся блок подходящего размера, опять же O(N) в худшем случае, на практике если куча не совсем фрагментирована, то гораздо быстрее (обычно в начале кучи был огромный блок, который никак не мог кончиться, поэтому поиск на нём оканчивался).

O(N) вплоне приемлемо для базового аллокатора. Конечно, дальше можно наворачивать оптимизации типа поддержания разных списков свободных блоков для разных размеров (slab allocator) или сделать дерево вместо линейного списка (для уменьшения сложности free с O(N) до O(logN), не знаю используется ли это где-то, просто первое что пришло в голову), но для игрушечной ОС это избыточно. И такие менеджеры точно так же могут часть своих структур хранить в освобождённый памяти.

Мой пойнт в том, что free может портить данные в освобожденной памяти даже в очень триаиальной реализации аллокатора (и раз я до неё сходу догадался и она даёт выигрыш по памяти, то деды 30 лет назад тоже должны были). Так что без всяких mmap обращаться по освобожденному адресу плохая идея. Там может быть какая-то структура учёта свободных блоков вместо твоих данных.

Зачем пузырек? Я поддерживал упорядоченность свободных блоков по базовым адресам. Таким образом free должен был просто пробежаться по списку свободных блоков, пока не найдёт нужное место для вставки, а затем проверить ровно два кандидата на слияние - предыдущий и следующий блок. Никакого O(N^2), обычный O(N) для худшего случая. Malloc же брал первый попавшийся блок подходящего размера, опять же O(N) в худшем случае, на практике если куча не совсем фрагментирована, то гораздо быстрее (обычно в начале кучи был огромный блок, который никак не мог кончиться, поэтому поиск на нём оканчивался).

O(N) вплоне приемлемо для базового аллокатора. Конечно, дальше можно наворачивать оптимизации типа поддержания разных списков свободных блоков для разных размеров (slab allocator) или сделать дерево вместо линейного списка (для уменьшения сложности free с O(N) до O(logN), не знаю используется ли это где-то, просто первое что пришло в голову), но для игрушечной ОС это избыточно. И такие менеджеры точно так же могут часть своих структур хранить в освобождённый памяти.

Мой пойнт в том, что free может портить данные в освобожденной памяти даже в очень триаиальной реализации аллокатора (и раз я до неё сходу догадался и она даёт выигрыш по памяти, то деды 30 лет назад тоже должны были). Так что без всяких mmap обращаться по освобожденному адресу плохая идея. Там может быть какая-то структура учёта свободных блоков вместо твоих данных.

Зачем пузырек? Я поддерживал упорядоченность свободных блоков по базовым адресам. Таким образом free должен был просто пробежаться по списку свободных блоков, пока не найдёт нужное место для вставки, а затем проверить ровно два кандидата на слияние - предыдущий и следующий блок. Никакого O(N^2), обычный O(N) для худшего случая. Malloc же брал первый попавшийся блок подходящего размера, опять же O(N) в худшем случае, на практике если куча не совсем фрагментирована, то гораздо быстрее (обычно в начале кучи был огромный блок, который никак не мог кончиться, поэтому поиск на нём оканчивался).

O(N) вплоне приемлемо для базового аллокатора. Конечно, дальше можно наворачивать оптимизации типа поддержания разных списков свободных блоков для разных размеров (slab allocator) или сделать дерево вместо линейного списка (для уменьшения сложности free с O(N) до O(logN), не знаю используется ли это где-то, просто первое что пришло в голову), но для игрушечной ОС это избыточно. И такие менеджеры точно так же могут часть своих структур хранить в освобождённый памяти.

Мой пойнт в том, что free может портить данные в освобожденной памяти даже в очень триаиальной реализации аллокатора (и раз я до неё сходу догадался и она даёт выигрыш по памяти, то деды 30 лет назад тоже должны были). Так что без всяких mmap обращаться по освобожденному адресу плохая идея.

Зачем пузырек? Я поддерживал упорядоченность свободных блоков по базовым адресам. Таким образом free должен был просто пробежаться по списку свободных блоков, пока не найдёт нужное место для вставки, а затем проверить ровно два кандидата на слияние - предыдущий и следующий блок. Никакого O(N^2), обычный O(N) для худшего случая. Malloc же брал первый попавшийся блок подходящего размера, опять же O(N) в худшем случае, на практике если куча не совсем фрагментирована, то гораздо быстрее (обычно в начале кучи был огромный блок, который никак не мог кончиться, поэтому поиск на нём оканчивался).

O(N) вплоне приемлемо для базового аллокатора. Конечно, дальше можно наворачивать оптимизации типа поддержания разных списков свободных блоков для разных размеров (slab allocator) или сделать дерево вместо линейного списка (для уменьшения сложности free с O(N) до O(logN), не знаю используется ли это где-то, просто первое что пришло в голову), но для игрушечной ОС это избыточно. И такие менеджеры точно так же могут часть своих структур хранить в освобождённый памяти.

Мой пойнт в том, что free может портить данные в освобожденной памяти даже в очень триаиальной реализации аллокатора. Так что без всяких mmap обращаться по освобожденному адресу плохая идея.

Зачем пузырек? Я поддерживал упорядоченность свободных блоков по базовым адресам. Таким образом free должен был просто пробежаться по списку свободных блоков, пока не найдёт нужное место для вставки, а затем проверить ровно два кандидата на слияние - предыдущий и следующий блок. Никакого O(N^2), обычный O(N) для худшего случая. Malloc же брал первый попавшийся блок подходящего размера, опять же O(N) в худшем случае, на практике если куча не совсем фрагментирована, то гораздо быстрее (обычно в начале кучи был огромный блок, который никак не мог кончиться, поэтому поиск на нём оканчивался).

Зачем пузырек? Я поддерживал упорядоченность свободных блоков по базовым адресам. Таким образом free должен был просто пробежаться по списку свободных блоков, пока не найдёт нужное место для вставки, а затем проверить ровно два кандидата на слияние - предыдущий и следующий блок. Никакого O(N^2), обычный O(N) для худшего случая. Malloc же брал первый попавшийся блок подходящего размера, опять же O(N) в худшем случае, на практике если куча не совсем фрагментирована, то гораздо быстрее (обычно в начале кучи был огромный блок, который никак не мог кончиться).