Фрагментация памяти в FireFox (?) и как бороться

Как же, всё-таки, free на таком указателе будет работать?

>Если падения прекратятся, то все ясно...

Паданеия у firefox 1.5 с glib 2.10 прекратились,
и память отдает,
правда работает неторопливо, простые тесты показывают что
malloc/realloc/free из OpenBSD примерно в два раза медленней
чем из glibc.

Работает неторопливо, наверное, из-за медленных pthread_mutex.

А вот как free на серединах кусков отрабатывает, пока не понятно.

>Как же, всё-таки, free на таком указателе будет работать?

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

2mr:

>>Если падения прекратятся, то все ясно...

>Так вроде с той posix_memalign с firefox нет никаких ворнингов и сам firefox на вид работает нормально.

Дался вам этот posix_memalign! (Кстати, приведенный тобой код posix_memalign() неверный).

Я предлагаю просто вставить по 8 байт в концы отдаваемого malloc()'ом чанка (8 -- чтобы выравнивание на 8 не нарушать). Можно туда записывать некие волшебные слова, и пусть free() проверяет, не поломал ли их кто.

Если поломано, пусть выводит (на stderr, например) оба слова.

Направляем вывод в файл, потом анализируем его. Допустим, видим, что 4 байта от заднего волшебного слова кто-то (glib?) систематически жует.

Ок, подправляем твой маллок так, чтобы он эти 4 байта в хвосте придерживал, и ошибка подперта костылем -- можно юзать...

> Работает неторопливо, наверное, из-за медленных pthread_mutex.

Да нет, просто mmap-based манагеры по жизни тормозят, это к них имманентно и от конкретной реализации зависит мало.

Вдогонку:

> Ок, подправляем твой маллок так, чтобы он эти 4 байта в хвосте придерживал, и ошибка подперта костылем -- можно юзать...

Разумеется, это надо делать runtime-configurable, типа, через окружение.

Да, а все семейство memalign нарисовать самому, как ты сделал, только правильно ;)

Ну это костыль... вообще зашибись. Лишние несколько байт на каждую аллокацию? Да и вообще, откуда уверенность, что glib (или кто там) будет фиксированное число байт откусывать, а вдруг оно куда угодно залезать будет? Нет, такой костыль слишком уж костылистый :))

Да, хорошо написать posix_memalign -- вот что нам нужно!

>Да нет, просто mmap-based манагеры по жизни тормозят, это к них >имманентно и от конкретной реализации зависит мало.

Кстати, пересобрал с оптимизаций и вуаля:

$ make
cc -g -Wall -O2 -o wild-malloc wild-malloc.c malloc.c
$ time ./wild-malloc

real 0m1.581s
user 0m0.692s
sys 0m0.764s
$ time ./wild-malloc

real 0m1.433s
user 0m0.720s
sys 0m0.712s

с glibc malloc, собранной статически
$ make
cc -static -static-libgcc -g -Wall -O2 -o wild-malloc wild-malloc.c
$ time ./wild-malloc

real 0m0.723s
user 0m0.432s
sys 0m0.288s
$ time ./wild-malloc

real 0m0.719s
user 0m0.448s
sys 0m0.268s

с -O2 firefox на глаз также быстро работает может и быстрее,

а тест конечно нежизненный, но выигрыш в 7 раз аллокатора openbsd впечетляет, может ребята все-таки что-то недокрутили в своей реализации?

хм мой вариант posix_memalign:

int posix_memalign(void **memptr, size_t alignment, size_t size)
{
	long valsiz = alignment, j;
	void *cp = malloc(size + (valsiz-1));

	if (!cp)
		return ENOMEM;
	j = ((long)cp + (valsiz-1)) &~ (valsiz-1);
	*memptr = ((void *)j);
	return 0;
}


я думаю самая правильная идея это подтолкнуть *BSD людей к реализации posix_memalign, а не строить костыли.

>Работает неторопливо, наверное, из-за медленных pthread_mutex.

Нет. Из-за самих mmap(). (mmap() в linux медленнее sbrk???) Заведомо медленнее, чем вернуть указатель на уже готовый свободный chunk из непрерывной кучи в glibc malloc.

Sorry, уже ответили.

> Ну это костыль... вообще зашибись. Лишние несколько байт на каждую аллокацию?

Костыль полезен для отладки glib, это подарок гномщикам на самом деле :)

2mr:

> Лишние несколько байт на каждую аллокацию?

Дык, оно ж все равно в среднем как минимум на 4 байта больше дает! Будет на 8...

> Да и вообще, откуда уверенность, что glib (или кто там) будет фиксированное число байт откусывать, а вдруг оно куда угодно залезать будет?

1. Я ж предлагаю сначала вопрос поисследовать! Какой смысл тестировать "твой" маллок, если мы уверены, что проблема в ЖеЛибе?

2. Если б оно из середины откусывало, оно бы под любым манагером падало!

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

Ты ж говорил сам, что это неправильно?

Я вот подумал: а ведь для valloc это работает, потому что там делается аллокация > pagesize, которая соотв. размещается на отдельном mmap'нутом куске, т.е. получается cp == j в valloc.

А для posix_memalign с alignment много меньше 4096 такого не будет.

какая отладка glib?
все прекрасно работает, если реализовать posix_memalign,
по крайней мере у меня, ничего не никуда не падает.

теперь вопрос не как реализовать на коленке, а как правильно
реализовать posix_memalign

Лучше 1. понять, почему с таким posix_memalign работает 2. сделать нормальный posix_memalign

И тогда никаких костылей не понадобится, скорее всего.

anonymous (*) (21.06.2006 17:45:36):

> mmap() в linux медленнее sbrk???

Оно, типа, везде медленнее. И munmap медленный. Надо ж по каждой странице пройти!

> чем вернуть указатель на уже готовый свободный chunk из непрерывной кучи в glibc malloc.

Ключевое слово -- "непрерывной". В mmapнутых аллокаторах куча сама по себе фрагментирована.

>cp == j в valloc.

зачем же они его потом округляют до pagesize?

>Ты ж говорил сам, что это неправильно

а в чем противоречие? да это неправильно,
оно как-то работает, в основном из-за того что glib как раз около pagsize куски и просит.

а эта просто для демонстрации того что вся проблема в posix_memalign.

надо связывать с openbsdшниками и пытаться реализовать правильную версия.

>1. понять, почему с таким posix_memalign

так вроде уже все поняли?

Не очень понятно, почему mmap медленней sbrk, кстати.

mr

> Лучше 1. понять, почему с таким posix_memalign работает 2. сделать нормальный posix_memalign

А я что предлагаю?

Подумай, я именно это и предлагаю, только без лишних тормозов и оверхэда от posix_memalign - базированных обвязок.

Где это все поняли? Я нифига не понял. Объясни.

>Где это все поняли? Я нифига не понял. Объясни.

Хм.. я вроде сделал это несколько постов назад, и Die-Hard тоже.

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

в нашем случае posix_memalign принадлежала glibc,
а free openbsd_malloc, что и порождало проблему

> хм мой вариант posix_memalign ...

надо добавить проверку:

int if_power_of_2 (size_t a) {
size_t b;
for (b = 1U << sizeof(size_t)*8-1; b > 1; b >>= 1)
if (b == a)
return 1;
return 0;
}

...
if (!if_power_of_2(alignment) || alignment % sizeof(void*) != 0) {
fputs("posix_memalign: alignment must be a power of 2 and a multiple of sizeof(void*)",stderr);
return NULL;
}
...

Вообще-то я спрашиваю, почему оно с таким вариантом posix_memalign _работает_, а не почему оно не работало, когда она была вообще не определена.

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

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

Выравнивает гарантированно только на 16 байт.

zov.

anonymous (*) (21.06.2006 18:20:37) aka zov:

> Выравнивает гарантированно только на 16 байт.

Это так написано. Но что-то меня сомнения берут, глядя на код... А mr сказал, что на 8...

Надо просто проверить!

mr:

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

Я и предлагаю это сделать, понимаешь?

Вместо обвязки вставить в маллок и фри проверялку! 5 строчек кода!

Блин, мне сейчас совершенно некогда...

>Вообще-то я спрашиваю, почему оно с таким вариантом posix_memalign >_работает_

посмотрел исходники,

ifree вызывает pdir_lookup,

pdir_lookup это судя по виду хорошо оптимизированный
для данного случая бинарный поиск,
возвращаемое значение pdir_lookup,
как -то нашел он точно то что нужно, или меньше больше не проверяется,
вернее только если
#define MALLOC_EXTRA_SANITY
будет провекра,
а дальше все прекрасно освобождается.

не вру, это он страницу находит,
free_pages или free_bytes

> Надо просто проверить!

Дык проверено экспериментально.

if ((u_long) ptr & ((1UL << (info->shift)) - 1)) {

судя по этой проверке, где info->shift == 5,
адрес выравнен по 16 байтам

Вставил проверку на равенство:

int posix_memalign(void **memptr, size_t alignment, size_t size)
{
    long valsiz = alignment, j;
    void *cp = malloc(size + (valsiz-1));

  if (!cp)
      return ENOMEM;
    j = ((long)cp + (valsiz-1)) &~ (valsiz-1);
    *memptr = ((void *)j);
    if(cp==*memptr)
    fprintf(stderr," alignment=%d size=%d cp=%d *memptr=%d\n",alignment,size,cp,*memptr);
    else
      fprintf(stderr," alignment=%d size=%d cp=%d *memptr=%d Hey! Hey! Hey!\n",alignment,size,cp,*memptr);
    return 0;
}

Оказалось, что очень редко, даже не в каждом сеансе firefox, происходит неравенство cp и *memptr.
Теперь понятно, почему такой код работает -- видимо чисто вероятностно free не запускается в таких случаях.
Итак, такой posix_malign оказывается ещё и ненадёжным => надо писать нормальный.

>Итак, такой posix_malign оказывается ещё и ненадёжным => надо писать >нормальный.

ну, судя по free_bytes,
для маленьких кусочков используется
карта аллокированных 32 байтных блоков,

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

что не фатально, но неприятно.

Не понятно, как они могут остаться висеть. Ведь функция free() либо освободит их, либо приведёт к падению всей программы, если в середину куска ткнёт.

Кстати, те аллокации, для которых cp и *memptr не совпадают, это

alignment=8192 size=8184 cp=-1234825216 *memptr=-1234821120 Hey! Hey! Hey!

alignment=8192 size=8184 cp=-1263783936 *memptr=-1263779840 Hey! Hey! Hey!

anonymous (*) (21.06.2006 18:43:57):

>> Надо просто проверить!

> Дык проверено экспериментально.

Проверено, что не падает при исползовании некоторой обвязки.

Я предлагаю написАть 10 строчек кода и получить полную картину того, что происходит.

fghj (*) (21.06.2006 18:53:23):

> судя по этой проверке, где info->shift == 5, адрес выравнен по 16 байтам

Да, согласен.

А что будет, если выставить malloc_minsize в 8UL? (в смысле, будет ли работать вообще и как это скажется на частоте падений)

На самом деле, в общих чертах это уже и так понятно. Там, фактически, происходит нужное нам выравнивание для блоков соотв. размера. Другой случай (редкий) -- случай больших блоков, когда выравнивание происходит, очевидно, по 4096 байт, и это может быть нехорошо, но нам это сходит с рук. Далее надо немного разобраться в коде аллокатора и сразу же написать необходимый posix_malign, и это должно быть несложно. Вот...

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

ну если вообще это попробовать:

int
main (void)
{
	int size = 8184, valsiz = 8192;
	void *p = malloc(size + (valsiz-1));
	long j = ((long)p + (valsiz-1)) &~ (valsiz-1);
	printf("%lu %lu\n", (unsigned long)p, (unsigned long)j);
	free((void *)j);
	return 0;
}

то какой-нибудь простой тест, типа

for i in `seq 1 100`; do ./tst-malloc; done

где tst-malloc приведет выше приведет к падению.

а может кто нить попробует прикрутить FF к boehm gc ? Заменить все malloc-и на gcmalloc, и убрать все free ? Ну еще и добавить везде #include gc.h :)

а?

>а может кто нить попробует прикрутить FF к boehm gc ?

возьми и попробуй.

ЗЫ

судя по коду мозилы, где присутсвует garbage collector,
попытки были, судя по README.linux - неудачные.

Я слышал, что его раньше там использовали, а теперь отказались, потому что утечки отловили -- сейчас в firefox мало утечек памяти, проблемы с памятью не из-за этого.

Кстати, аллокатор openbsd размещает переменные таким образом: аллокации в 1-16, 17-32, 33-64, ..., 1025-2048 размещаются раздельно друг от друга, т.е. на разных страницах, причём с выравниванием в 16, 32, 64, ..., 2048 байт соответственно; аллокации в 2049 байт и больше размещаются на отдельных страницах, т.е. как бы с выравниванием в 4096 байт.

А это значит, что для выравниваний не более чем в 4096 байт в фунции posix_memalign достаточно сделать malloc(maximum(alignment,size)).

А вот с выравниваниями в 8192 байта и больше -- сложнее, чтобы их правильно сделать, надо слазить непосредственно в код аллокатора. Что я, собственно, и пытаюсь сделать :-)

>А вот с выравниваниями в 8192 байта и больше

А что он делает, если запросить у него, скажем, malloc(8192)?

Очевидно, mmapит 8192 байт, т.е. получается 2 подряд страницы памяти.

2mr:

Два вопроса.

Ты, как я понимаю, увлекся написанием posix_memalign, правильно?

Если да, то второй вопрос -- а зачем?

>Ты, как я понимаю, увлекся написанием posix_memalign, правильно?

Да, я уже почти понял, как быть с большими выравниваниями, сейчас попытаюсь воткнуть их...

>Если да, то второй вопрос -- а зачем?

Чтобы glib надёжно работала. Тогда всё точно будет работать правильно. Ведь даже с той затравочной функцией, неправильно работающей с большими (>=8192) выравниваниями ворнинги прекратились.