Может обрабатывать страницы памяти вставки в середине mmapped пространства?

Question

Дистиллированный сценарий:

Программа для использования в пространстве пользователя требует миллионов структурированных страниц (т. Е. 4k для большинства систем Linux). Он также требует быстрого произвольного доступа к структурам. Иногда программе необходимо вставить новую структуру в середину массива. Заказ важен.

struct { char data[PAGE_SIZE]; } page_sized_t; 
size_t N = 1 * 1000 * 1000; 
size_t X = INSERT_INDEX; 

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

struct page_sized_t **array = malloc(sizeof(array[0]) * N); 
... 
array = realloc(array, sizeof(array[0]) * (N+1)); 
memmove(&array[X+1], &array[X], N-X); 
array[X] = malloc(sizeof(array[X][0])); 
... 

Теперь мой вопрос в этом. Было бы практично реализовать такую ​​программу с точки зрения наличия одной большой области памяти. Где каждая структура будет размещаться на одной странице. Тогда вставка может быть реализована следующим образом: программа может попросить ядро ​​вставить новую страницу между другими. В основном ядро ​​выполняет работу, описанную в предыдущем абзаце.

struct page_sized_t *array = mmap(0, sizeof(array[0]) * N, 
            PROT_READ|PROT_WRITE, MAP_ANONYMOUS, -1, 0); 
... 
// imaginary syscall: m_insert_map(old_address, old_size, insert_address, insert_size) 
array = m_insert_map(array, sizeof(array[0]) * N, sizeof(array[0]) * X, sizeof(array[0])); 
... 

Я думаю, что с текущими системными вызовами это невозможно. Можно только mremap - так что в некотором смысле только вставлять страницы в конец.

Подведение итогов: Можно ли внедрить страницы памяти в ядро ​​Linux? Было бы целесообразным использовать такой интерфейс вместо реализации пользовательского пространства? Есть ли система, которая реализована?

Answer 1

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

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

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

Было бы практичным реализовать такую ​​программу с точки зрения наличия одной большой области памяти.

Нет. На ваших собственных условиях у вас есть одна страница для каждой структуры. Чтобы вставить страницу посередине, необходимо обновить остальные записи в таблице страниц. Это будет медленно.

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

struct page_sized_t **array; 

, то нет никакой реальной причины, чтобы переместить содержимое вокруг; просто обновите указатели. Да, это означает, что для перемещения элемента j индексировать i с i < j, вам нужно

struct page_sized_t *temp = array[j]; 
memmove(array + i + 1, array + 1, (j - i) * sizeof array[0]); 
array[i] = temp; 

array[j] Обратите внимание, что имеет тип struct page_sized_t *, так что это перемещает указатели вокруг, а не содержимое. Изменение указателей всегда будет быстрее, чем изменение количества записей в таблице страниц.(Даже если используются огромные страницы, логика, необходимая для слияния/разделения их на обычные страницы по мере необходимости, почти наверняка непрактична. Возможно, вы сможете создать микробиблиотеку, где она будет работать лучше, чем простая memmove (хотя, если вы это сделали, будет удивлены из моих носков), но во всех сценариях реальной жизни таких таблиц страниц махинация просто добавить накладные расходы.

Может вставка страниц памяти будет реализован в ядре Linux? будет ли это практично использовать такой интерфейс вместо реализации пользовательского пространства?

Вы уже можете сделать это с помощью mremap().

Вы перенаправляете регион, начиная с точки ввода, используя mremap(array + index, pagesize * (size - index), pagesize * (size - index + 1), MREMAP_FIXED, array + index + 1). Затем вы используете либо mremap(array, pagesize * index, pagesize * (index + 1), 0), чтобы увеличить начальную часть, чтобы закрыть отверстие, либо mmap(array + index, pagesize, PROT_READ | PROT_WRITE, MAP_PRIVATE, -1, 0), чтобы заглушить отверстие.

Это очень похоже на то, как вы будете делать то же самое, используя memmove(), действительно.

Однако вы должны убедиться, что ни один другой поток не будет создавать новые распределения памяти (через mmap()) во время двух вызовов, так как в противном случае ядро ​​может предоставить «отверстие» для другого вызова выделения памяти, нарушая схему. Это полностью проблема с пользовательским пространством, и в однопоточном приложении это должно быть тривиально (поскольку для использования функций распределения памяти в обработчиках сигналов не является безопасным по отношению к асинхронному сигналу), но для многопоточных программ это может быть сложно или даже невозможно - даже некоторые функции библиотеки C выполняют неявное/внутреннее распределение динамической памяти.

Резюмируя:

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

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