delete[] C++

> Про твой ответ, с дебажным выводм glibc-а про double free: glibc-ы разные бывают.

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

> "я malloc-ом выделил 4096 байт".

Прекрасно. Выделяйте дальше, пока кэш у libc не кончится, и оно не дёрнет brk (старый glibc или негнутый libc) или mmap (современный glibc). В обоих случаях одну страницу у ядра libc запрашивать не будет, а в первом случае получить дырку до выделенной памяти (на линуксе) вообще невозможно.

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

Напротив. Я именно про расширение писал.

> glibc хранит информацию о выделенной памяти не в перемежку с самой выделенной памятью (загляните в исходники, там, если память не изменяет, красно-чёрное дерево).

Н-да....

Ты путаешь пул свободной памяти и выделенную память. Подумай сам немного -- КАК можно хранить информацию о _выделенной_ памяти в "дереве"? Чисто теоретически! Я говорю free(0xFF2266) -- И? Система кидается искать, есть ли по адресу 0xFF2266 (под-)корень дерева?

> Я именно про расширение писал.

А в топике речь идет не о расширении, а о _выделении_: и malloc(), и delete, вообще говоря, имеют дело с памятью, уже принадлежащей процессу.

> Ты путаешь пул свободной памяти и выделенную память.

Ничего я не путаю.

> Подумай сам немного -- КАК можно хранить информацию о _выделенной_ памяти в "дереве"? Чисто теоретически!

Делаешь malloc(n), в дерево добавляется узел с информацией об адресе выделенной памяти и её размере.

> Я говорю free(0xFF2266) -- И? Система кидается искать, есть ли по адресу 0xFF2266 (под-)корень дерева?

Ты будешь удивлён, но примерно так: glibc ищёт нужный узел в дереве. Glibc я давно смотрел, но если ты с fmj так настаиваешь, то могу и ещё посмотреть.

> glibc хранит информацию о выделенной памяти не в перемежку с самой выделенной памятью (загляните в исходники, там, если память не изменяет, красно-чёрное дерево).

Опять-же, глибцы разные бывают, да и вообще libc-ы, не надо зацикливатся на одном linux-е. В исходных данных не было ссылок на ту или иную реализацию libc, а в общем случае код крешится, при вызове free на середине массива. Я перепробовал несклоько libc-ов сейчас, встречаются как такие, где перед выделяемыми кусками нет никаких линков, так и те, где такие линки есть.

Если же вернутся к совсем исходным данным, то вспомним, что речь изначально шла о плюсовом дефолтном void operator delete(void *ptr, size_t sz); Плюсовый аллокатор должен сам уметь запоминать, сколько памяти было выделено под массив обьектов, и по этой причине, должен сам запоминать "мета-информацию", в любом случае вызов массива по указателю, отличному от исходного, может привести к неверному считыванию этой "мета-информации", и соответственно к неверному предположению о размере массива, так что деструктор вдруг вызовется не 3-м обьектам: а нескольким тысячам, никогда не созданных. Последний абзац - полный AFAIK.

> Прекрасно. Выделяйте дальше, пока кэш у libc не кончится, и оно не дёрнет brk (старый glibc или негнутый libc) или mmap (современный glibc). В обоих случаях одну страницу у ядра libc запрашивать не будет, а в первом случае получить дырку до выделенной памяти (на линуксе) вообще невозможно.

Сценарий, для тех, кто с IQ < 60:

я запрашиваю malloc(4096);

либа дебажная делает

void *bptr = malloc(4096/*выровненный запрашиваемый размер*/ + 2*4096);

void *user_ptr = ((char*)ptr) + 4096;

void *eptr = ((char*)ptr) + 4096 + 4096;

mprotect(bptr, 4096, PROT_NONE);

mprotect(eptr, 4096, PROT_NONE);

// Фантастика?

> Опять-же, глибцы разные бывают, да и вообще libc-ы, не надо зацикливатся на одном linux-е. В исходных данных не было ссылок на ту или иную реализацию libc, а в общем случае код крешится, при вызове free на середине массива. Я перепробовал несклоько libc-ов сейчас, встречаются как такие, где перед выделяемыми кусками нет никаких линков, так и те, где такие линки есть.

Ну ладно, будет считать, что произошло недоразумение. GNU libc, кстати, одна

> Если же вернутся к совсем исходным данным,

Про плюсы я вообще ничего не писал.

> // Фантастика?

Ну если очень сильно захотеть... Правда, дебажная либа mmap вместо malloc делает, иначе трюк с mprotect не пройдёт, но не суть.

> Ну если очень сильно захотеть... Правда, дебажная либа mmap вместо malloc делает, иначе трюк с mprotect не пройдёт, но не суть.

Не суть, в линуксовом мане по mprotect сказано, что его можно применять к любому адресу, т.е. как угодно аллокированному (brk/mmap/что-нибудь еще (загруженный загрузчиком execv-а код например) (except for the kernel vsyscall area).

>> ...встречаются как такие, где перед выделяемыми кусками нет никаких линков,

Я не представляю чисто теоретически, как такое можно реализовать. А главное, зачем... Можно ссылку -- просто из любопытства?

> Ну ладно, будет считать, что произошло недоразумение. GNU libc, кстати, одна

У меня как раз под рукой исходники завалялись. Следующим постом лови кусочек (форматирование).

   malloc_chunk details:

    (The following includes lightly edited explanations by Colin Plumb.)

    Chunks of memory are maintained using a `boundary tag' method as
    described in e.g., Knuth or Standish.  (See the paper by Paul
    Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
    survey of such techniques.)  Sizes of free chunks are stored both
    in the front of each chunk and at the end.  This makes
    consolidating fragmented chunks into bigger chunks very fast.  The
    size fields also hold bits representing whether chunks are free or
    in use.

    An allocated chunk looks like this:


    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if allocated            | |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                         |P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_space() bytes)                     .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk                                     |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

> Не суть, в линуксовом мане по mprotect сказано, что его можно применять к любому адресу, т.е. как угодно аллокированному (brk/mmap/что-нибудь еще (загруженный загрузчиком execv-а код например) (except for the kernel vsyscall area).

Можно-то можно, но не факт, что после malloc'а тебе вернётся выровненный на границу страницы адрес, а mprotect обязательно сругается на это. Но не суть.

Да, файл

glibc-2.2.5/malloc/malloc.c

> но не факт, что после malloc'а тебе вернётся выровненный на границу страницы адрес,...

Несколькими постами выше ты утверждал, что гранулирование идет страницами (чушь, конечно).

> Да, файл

> glibc-2.2.5/malloc/malloc.c

Да, уже посмотрел. Признаю ошибку. С чем-то перепутал.

> Несколькими постами выше ты утверждал, что гранулирование идет страницами (чушь, конечно).

По всей видимости, ты не понимаешь, на что отвечаешь :( Гранулирование физической памяти, само собой, к malloc и free никакого отношение не имеет. Если хочешь пообщаться на эту тему, выдвигай список претензий.

Заявленный mprotect уже точно работает со страницами.

> Я не представляю чисто теоретически, как такое можно реализовать.

ну никто не мешает вести базу данных (дерево) по выделенной памяти. Другое дело, что по производительности и расходу памяти это плохо.

> Признаю ошибку. С чем-то перепутал.

А кстати, тут некая принципиальная загогулина: если бы _принципиально_ можно было бы освобождать оператором delete [] память, выделенную оператором new, из _середины_, то вопрос топикстартера был бы правомочен. А так -- читайте Страуструпа, там написано...

> ну никто не мешает вести базу данных (дерево) по выделенной памяти. Другое дело, что по производительности и расходу памяти это плохо.

Ядро так хранит конфигурацию памяти процесса.

> ...никто не мешает вести базу данных (дерево) по выделенной памяти.

На каждый free() лазить по дереву, и на каждый malloc() это дерево балансировать?

Кстати, тут хэш таблица была бы сподручнее -- но все равно глупо. Просто не вижу смысла!

В ядре так и делается (это точно ;). А ещё можно делать split_vma, в результате которого из одного куска памяти получается два. Т.е. можно сделать hole посередине ранее занятой памяти.

> Ядро так хранит конфигурацию памяти процесса.

Там _страницы_! Они _большие_! И их можно маппить произвольным образом на уровне железяки.

То же самое с файловой системой. Но это _совсем_ другая история! Если на каждый байт распределять страницу, то не очень здорово получится.

> Там _страницы_! Они _большие_! И их можно маппить произвольным образом на уровне железяки.

Принципиальной разницы нет, страницы фиксированной длины или чанки произвольного размера. Кстати, кое где есть ещё и hugetlb странички с другим размером...

> Принципиальной разницы нет

Есть.

Во-первых, пул кучи процесса принадлежит только ему, а страницы надо защищать.

Во-вторых, траницы, все же, больше. Если бы не было принципиальной разницы, не было бы проблем с ГНУлибсишным маллоком с его мерзкой фрагментацией.

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

> Но это _совсем_ другая история! Если на каждый байт распределять страницу, то не очень здорово получится.

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

К тому же, если на 64-битной машине с большим количеством памяти делать vmalloc(PAGE_SIZE) много раз, то дерево получится очень больших размеров (vmalloc для профилактики оставляет hole размером в страницу после выделенного куска, поэтому два рядом находящихся vma в один слить нельзя). Распределитель в ядре работает идеологически неправильно?

> Во-вторых, траницы, все же, больше. Если бы не было принципиальной разницы, не было бы проблем с ГНУлибсишным маллоком с его мерзкой фрагментацией.

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

Проблема с фрагментацией в ядре тоже очень остро стоит. Правда, vmalloc'а это не касается, а вот kmalloc'а - очень даже.

> Я не представляю чисто теоретически, как такое можно реализовать. А главное, зачем... Можно ссылку -- просто из любопытства?

Я просто видимо не совсем корректно проинтерпретировал результаты эксперемента, когда увидел перед выделенным блоком памяти только 8 байт, из них 4 - нули, а другие 4 - хрянят небольшой int "чуть больше аллокированного", хотя МБ я просто не очень хорошо смотрел.

Хотя мне больше нравится vm_allocate в связке с vm_protect

> Не суть, в линуксовом мане по mprotect сказано, что его можно применять к любому адресу, т.е. как угодно аллокированному (brk/mmap/что-нибудь еще (загруженный загрузчиком execv-а код например) (except for the kernel vsyscall area).

brk, mmap, что-нибудь ещё работает со страницами. Наверное, имелось в виду, что можно любой области защиту менять.

sys_mprotect(unsigned long start, size_t len, unsigned long prot) { unsigned long vm_flags, nstart, end, tmp, reqprot; struct vm_area_struct *vma, *prev; int error = -EINVAL; const int grows = prot & (PROT_GROWSDOWN|PROT_GROWSUP); prot &= ~(PROT_GROWSDOWN|PROT_GROWSUP); if (grows == (PROT_GROWSDOWN|PROT_GROWSUP)) /* can't be both */ return -EINVAL; if (start & ~PAGE_MASK) return -EINVAL;

С невыровненным адресом mprotect просто EINVAL вернёт.

> С невыровненным адресом mprotect просто EINVAL вернёт.

Я не про невыровненность, а именно про любую область и говорил