Есть ли реализация malloc, которая делает бухгалтерию вне своей кучи?

Question

Мне нужно управлять кучей памяти с ограничением, в которое эта память должна только записываться, а не считываться, т. Е. Реализация malloc должна хранить бухгалтерскую информацию отдельно от кучи, которой она управляет, в обычной куче и должна вФакт, никогда не касайтесь конкретной кучи, которой он управляет.Я надеялся использовать протестированное, оптимизированное, готовое решение для этого, если таковое имеется.Примеры использования включают VBO OpenGL и память на внешних блоках встраиваемых систем.

Я посмотрел на dlmalloc, и из документации, кажется, помечает блоки памяти, которые он выделяет с обеих сторон, бухгалтерской информацией.Поиск в Google тоже не принес ничего хорошего - возможно, у меня нет правильных ключевых слов, чтобы найти то, что я ищу.

Пояснения: как отдельная куча, я имею в виду то, что я определяю как кучу.Я хочу плотно использовать память с небольшими выделениями в пределах одного или небольшого количества предварительно выделенных блоков.Меня даже не волнует, больше ли бухгалтерская информация (за пределами управляемой кучи), чем данные внутри :) Более того, само приложение будет использовать для своей работы запасы malloc и heap и использовать эти блоки только для специального назначения, котороесводится к областям памяти для разговоров с внешним оборудованием, где запись из приложения является целью, чтение невозможно или дорого.Это не общий вопрос malloc, я просто надеялся использовать что-то, в чем было много исследований и испытаний.

Answer 1

Это не готовая к использованию библиотека, но код управления ресурсами в ядре Linux делает именно это для управления такими ресурсами, как адресное пространство PCI.

Answer 2

и фактически никогда не должен касаться конкретной кучи, которой он управляет.

Что если он не управляет кучей?Посмотрите на эту функцию malloc, использующую конкретную реализацию, которая не управляет областью [heap] (ср. /proc/$$/maps) и не сохраняет ее метаданные в адресной памяти, и, тем не менее, предоставляет вашей программе уникальную адресную память.

void *mymalloc(size_t len)
{
        void *x = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        return (x == (void *)-1) ? NULL : x;
}

А теперь для откровения убийцы: glibc использует именно это для достаточно больших выделений.

Answer 3

Просто используйте Buddy System .

Answer 4

Должен ли менеджер иметь ту же семантику, что и malloc / free? Все было бы значительно упрощено, если бы вы могли заставить свою функцию allocate возвращать указатель на структуру, которая, в свою очередь, указывала бы на фактическую память; функция deallocate будет принимать указатель на структуру, а не указатель на память.

Помимо этого, на способ распределения будут сильно влиять ваши шаблоны использования. Что можно сказать о размерах выделений и структуре распределения и освобождения блоков памяти?

Answer 5

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

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

Answer 6

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

void *malloc(size_t n) { return sbrk(n); }
void free(void *p) { }
void *realloc(void *p, size_t n }
{
    void *q = malloc(n);
    if (q) memcpy(q, p, n);
    return q;
}

Если вам нужны более реалистичные идеи, одно простое решение - выбрать наименьшую единицу памяти для выделения (8 или 16 байт может быть разумным) и разделить управляемую кучу на блоки такого размера, а затем сохранить, какие из них свободны в битовой карте (например, один бит на 16 байтов, для 1/128, издержки <1%). Поиск свободного пространства - это тогда <code>O(n), но вы можете придумать, как его улучшить с помощью многомасштабных карт.

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