Как в линуксе ищется свободная память

>вначале запускается дефрагментатор

Не запускается. C — не джава и перемещать память мы права не имеем.

Можешь почитать Иртегова про это)

Есть же в природе O(1)-аллокатор.

Я полагаю, вот так-то.

Главное - чтобы работало.

У нас слоев абстракции дофигища, поэтому фиг знает где эта самая память физически будет расположена.

Можно поговорить с Иртеговым про это ;)
Мы не можем перемещать — операционная система и ее планировщик памяти может. В этом и есть смысл free chain, что работа с фрагментацией от нас спрятана.

Как ОС переместит тебе блок памяти? Нужно же обновить все ссылки. А списка всех ссылок нет и быть в сях не может.

и правда, http://rtportal.upv.es/rtmalloc/
как же это работает?

> Мы не можем перемещать — операционная система и ее планировщик памяти может.

Так ты про распределение памяти внутри процесса или на уровне ядра?

В этом и есть смысл free chain, что работа с фрагментацией от нас спрятана.

Это какое-то очень сильное колдунство. Можно ссылки на документацию?

Физическая память -> линейная виртуальная память. Какие ещё слои?

настоящей документации (ака MSDN) нагуглить ниасилил, но вот что ищется из ненастоящей: http://www.realcoding.net/article/view/2747

> как же это работает?

Просто он не ищет подходящий кусок, а сразу берёт с запасом — из списка блоков, чей размер гарантировано удовлетворит запрос. Ну а дальше куча хитрых оптимизаций для реализации всего это дела.

По ссылке какая-то ерунда, не помогающая понять, что же имелось ввиду под «работа с фрагментацией от нас спрятана».

Ну положим, она и так спрятана в реализации libc. Но дефрагментировать выделенную память libc не может, а освобождённую — просто сливает вместе соседние куски.

http://ru.wikipedia.org/wiki/Сегментная_адресация_памяти же

> просто сливает вместе соседние куски

т.е. он не может слить не-соседние куски шоле? о_О

Как ты себе это представляешь?

Ну это же костыль костылей и не используется нигде.

> т.е. он не может слить не-соседние куски шоле? о_О

На уровне физической памяти, которой ядро рулит — хоть из отдельных страниц, рассеянных по всему адресному диапазону, настрогать тебе блок нужного размера. На уровне аллокатора libc — нет, не может.

Дефрагментация часто применяется при автоматической сборке мусора, в тех случаях, когда вместо указателей везде лежат хэндлы/дескриторы/как-угодно-это-назови, а сами указатели собраны в одном месте. Можно пройтись по всему списку и исправить адреса.

пруф?!

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

нагуглилось поиском по лору:

Сегментная модель защищёного режима появилась на i80286, а страничной там не было. Дескриптор сегмента для того процессора описывал область памяти с 24 бит начальным адресом и 16 бит размером (до 64 кБайт). Потом эти поля расширили до 32 бит адрес и 20 бит размер (1 Мбайт). И добавили страничный режим, когда размер сегмента указывается в страницах и адресация к физической памяти идёт через страничное преобразование. Потом добавили большие страницы (4 Мбайт, вроде) и PAE. PAE по факту является более хитрым страничным преобразованием, что позволяет адресовать до 64 ГБ памяти.

> пруф?!

Ну а какой тут может быть пруф, кроме грепания исходников всех известных нам опенсорсных ос?

Реально сегменты в защищенном режиме необходимы для работы оного. Поэтому нарезается, не помню уже сколько точно, вроде штук 6 — минимальное количество. Все они обычно указывают на полный диапазон 0-0xFFFFFFFF, т.е. сегментов всё равно что нет.

При разработке 64-битного режима AMD выпилила эта говно мамонта, оставив кое-какие рудиментарные регистры.

и как тогда для новых amd64 кошерно дефрагментировать память?

А какое отношение сегменты имеют к дефрагментации памяти вообще?

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

Вот в языках со сборщиком мусора другое дело, да.

На сколько мне известно, на каждый процес у ядра есть таблица с соответсием виртуальных и физических адресов страниц. Те, что не аллоцированы указывают на нулевую страницу, по-этому когда процес обращается по адресам, которые не алоцированы, происходит обращение к нулевой странице, дальше исключение, ядро получает контроль и пинает нафиг весь процес.
Размер страниц бывает 2(64 бита или PAE), 4 кб(32 бита без PAE) и 4 МБ (huge pages).
Так вот выделяется всегда по n страниц, где n - целое число. Ядро ищет свободные страницы. Находя - записывает их физ адрес в вышеупомянутую таблицу. Если страниц несколько - записывает из адреса последовательно в таблицу по последовательно идущим виртуальным адресам. Даже есть они физически в разных частях памяти находятся - всё равно для процеса они будут continuous.
Если свободных страниц нет, то ядро пытается раздобыть парочку, сбрасывая грязные страницы кеша фс на диск. Или размер кеша уменьшает, тут я не знаю точно. А если и после этого страниц нету - то тогда приходить злой и страшный OOK.

Я что-то не пойму каким местом здесь фрагментация памяти? И где она тут вообще?

Ответом на этот вопрос будет:
* либо «добрые человеки» в этом треде под веществами,
* либо я не в теме.

Подзреваю второе. Тогда кто-нибудь мне объясните пожалуйста где здесь фрагментация?

Дефрагментировать можно свободную память. Например, после освобождения двух блоков по 8 байт можно заметить, что они рядом и слить их в один 16-байтный.

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

первый человек, который со мной согласен. А то я начал ощущать, что схожу с ума ;)

В чём он с тобой согласен-то?

В том, что никакой «дефрагментации» нет? ;)

Это делается автоматически с помощью алгоритма парных меток

Мы выделили 3 блока по 16 кбайт, затем освободили средний, затем просим блок 17 кбайт. Как он тебе чего-то «настругает»?

А, опять джаверы с сисарпмонолюбителями говорят о дефрагметации памяти сборщиком мусора? Да, слыхал про такое.
Говорите им что бы освоили С, и что там дефрагментацией занимается ядро. Когда они спросят как оно это делает, посоветуйте им книжку хорошую про ядро. Или про физическую/логическую/dma/виртуальную адресацию им расскажите.

легко.
физически есть 128 страницы памяти по 4 кб. Дальше первой цифрой обозначается физический адрес (номера страниц для упрощения), а второй виртуальный (тоже номера).

делаем malloc(16k) три раза. тебе возравщается виртуальный адрес 1, 5 и 9. В ядрёной таблице страниц для процеса имеем

1 1 первые 16 кб
2 2
3 3
4 4
5 5 вторые 16 кб
6 6
7 7
8 8
9 9 трети 16 кб
10 10
11 11
12 12

1 1 
2 2
3 3
4 4
0 5 вирт. ад. с 5 по 8 указывает на nullpage (segfault при обращении)
0 6
0 7
0 8
9 9
10 10
11 11
12 12

1 1 первая 16 кб
2 2
3 3
4 4
0 5 виртуальные адреса с 5 по 8 никуда не указывают
0 6
0 7
0 8
9 9 третья 16 кб
10 10
11 11
12 12
5 13 твои 17 кб с хвостиком.
6 14
7 15
8 16
13 17

А теперь откойте пожалуйста глаза и увидите, что заняты физические страницы от 1ой до 13й последовательно. Где фрагментация?

> теперь ты освобождаешь второй блок, т.е. виртуальные адрес с 5 по 8 включительно

А теперь откойте пожалуйста глаза и увидите, что заняты физические страницы от 1ой до 13й последовательно.

/0

а теперь внимание вопрос: вы физические и виртуальные адраса различаете?

Я — различаю. А вы?

Фрагментация же состоит в том, что у тебя в адресном пространстве процесса может быть распределено всего 1 гиг из 3-х, но при этом ты оставшиеся 2 гига не сможешь выделить никак одним куском приложению, потому что свободные диапазоны адресов будут нарезаны мелкими ломтиками.

Впрочем, не заметил слова физические в цитате. Ок. Но про них речь и не шла в треде, насколько я понимаю. Физически память можно стругать постранично как угодно.

Но ведь на практике после free() glibc не стучит ядро, значит не делает этого. На практике оно при первом malloc() забирает чуть больше 128 кбайт с помощью brk, а отдаёт только в самом конце.

Мне тоже самое сказал товарищь, не помню с кем я тогда вёл дискуссию, что, мол, я выдилил много-много страниц, а потом освободил по пол страницы. И тогда вроде память есть, но выделить её одним куском не получится. Я с ним согласен, и с вам тоже. Но дальше этот товарищь сам признался, что пример, который он привёл, на столько гипотетичен, что он и сам начал сомневаться в актуальностит этой проблемы.

Итого:

Дефрагментация физических адресов отсутсвует как явление.
Дефрагментация виртуальных адресов хоть и присутствует, но только в настолько изощрённых примерах, что фантазии позавидует любой писатель фантаст-антиутопист.

На чём я тред заканчиваю, ибо хочу домой.

s/товарищь/добрый_человек/

О, ситуация прояснилась ;) Проблема в том, что настругивание памяти - дорогущая операция. Поэтому есть всякие стратегии как сделать так, чтобы она не запускалась когда не надо. Например, выделяя вдвое больше, чем нужно. Вот это я и предлагал обсудить ;)

> Реально сегменты в защищенном режиме необходимы для работы оного. Поэтому нарезается, не помню уже сколько точно, вроде штук 6 — минимальное количество. Все они обычно указывают на полный диапазон 0-0xFFFFFFFF, т.е. сегментов всё равно что нет.

Сегментов этих ровно шесть — CS (код), SS (стек), DS, ES, FS, GS (данные). Описываются они парой селектор-дескриптор. Селектор — это регистр, содержащий индекс в таблице дескрипторов GDT или LDT, бит таблицы и уровень привилегий. В дескрипторе помимо базы и лимита сегмента есть еще всякие атрибуты. Когда база = 0, а лимит = 0xffffffff — это называется flat моделью.

При разработке 64-битного режима AMD выпилила эта говно мамонта, оставив кое-какие рудиментарные регистры.

Выпилили только базы и лимиты. Да и то, лимиты потом вернули.

> Размер страниц бывает 2(64 бита или PAE), 4 кб(32 бита без PAE) и 4 МБ (huge pages).

Страница размером 2 кБ? Я хочу это видеть. :)

> Сегментов этих ровно шесть — CS (код), SS (стек), DS, ES, FS, GS (данные).

Это сегментные регистры, а самих дескрипторов сегментов можно в GDT и LTDs создавать до посинения. Я вообще не про то. Нам для запуска надо, щас посчитаем, — дескриптор под код режима ядра, дескриптор под непривилегированный код, и под данные. Три, что ли получается необходимый минимум? Лень мне вспоминать, в общем, да и не важно.

Выпилили только базы и лимиты. Да и то, лимиты потом вернули.

Я мануал на их архитектуру просмотрел один раз по диагонали и закрыл, поэтому не в курсе. А регистры-то сегментные работают в длинном режиме? Святую четверку CS SS DS ES они разве не выпилили?

> Проблема в том, что настругивание памяти - дорогущая операция.

Какое именно, в каком алгоритме? Моя опять ваша не понимать.

А, под данные же тоже надо раздельно держать привилегированный и не привилегированный сегменты. Тогда минимум 4 получается. Плюс еще можно один заюзать как псевдоуказатель на thread local storage или еще какие-нибудь системные данные.

> Какое именно, в каком алгоритме? Моя опять ваша не понимать.

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

> А с тем куском какой есть, вытворять разные непотребства, например, выбрать подходящий алгоритм, который будет в него ужиматься.

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

> А регистры-то сегментные работают в длинном режиме? Святую четверку CS SS DS ES они разве не выпилили?

Работают так же как и в 32-битном режиме. Но база и лимит в дескрипторе игнорируются. Для FS и GS базу можно задать через соответствующие MSRы. Еще допускается использование нулевых селекторов для всех сегментов, включая CS.

> Плюс еще можно один заюзать как псевдоуказатель на thread local storage или еще какие-нибудь системные данные.

Для этого GS юзают. Есть такой MSR — Kernel_GS_base — при помощи инструкции swapgs можно обменять его содержимое с базой GS. Очень удобно делать это на входе и выходе из ядра, т.к. нет необходимости обращаться к данным.

Размер страниц бывает 2(64 бита или PAE), 4 кб(32 бита без PAE) и 4 МБ (huge pages).

Страница размером 2 кБ? Я хочу это видеть. :)

Там, по ходу, 2Мб должно стоять. Пропустил просто когда писал.