=head1 ЗАГОЛОВОК Паррот: Внутреннее устройство памяти =head1 ВЕРСИЯ 0.0.9 Dec 2002 =head1 РЕЗЮМЕ Этот документ пытается объяснить внутреннее устройство структур Паррота, связанных с управлением памятью. =head1 ОБЗОР Все размещаемые в памяти элементы находятся в пулах. Пулы памяти хранят наборы схожих элементов и могут быть грубо поделены на 2 вида: хранящие элементы с фиксированным размером, и произвольным. Пул организуется как связанный список больших фрагментов, хранящих большое количество элементов одного вида. =head2 Аббревиатуры, используемые в этом документе DOD ... dead object detection (определение мертвых объектов), детали смотрите в F. Все объекты найденные при сканировании в регистрах интерпретатора, стеках и в стеке процессора помечаются как "живые". Остальные объекты считаются мертвыми. =head1 Сверху вниз: итнерпретатор Общая структура управления памяти интерпретатора выглядит следующим образом: typedef struct Parrot_Interp { ... struct Arenas *arena_base; ... } Interp; Все объекто подобные вещи, размещаемые во время выполнения байт-кода Паррота, хранятся в таких структурах. =head1 Арены I хранит указатели на различные подвиды, хранящейся памяти. Упрощенно эту структуру можно представить как: struct Arenas { struct Memory_Pool *memory_pool; ... struct Small_Object_Pool * header_pool; } I и I являются пулами переменного и фиксированного размера соответственно. =head1 Memory_Pool Здесь располагаются все элементы переменного размера, хранящиеся в связанном списке I (смотртите ниже). =head1 Small_Object_Pool Структуры I обеспечивают место для хранения объектов фиксированного размера. =head1 Элементы фиксированного размера Данные элементы являются либо объектами, например, I, либо заголовочными структурами, как I. Основным объектом этого вида является объект аналогичный буферу, который состоит из I или I в начале и переменной - части фиксированного размера следующей за буферной структурой. Примерами объектов такого вида явялются I и I. Буферо подобные объекты одинакового размера находятся в пулах I, которые хранят объекты одинакового размера в одном слоте. Все объекты фиксированного размера размещаются с помощью C, Сперва объекты попадают в C<свободный список(free_list)> пула. Затем когда возникает необходимость в новом объекте, он вытаскивается из свободного списка, и позднее, когда DOD определяет, что объект больше не используется, он помещается обратно в свободный список. Если свободный список пуст, запускается DOD, который может обнаружить неиспользуемые объекты и пополнить ими свободный список. Если DOD не удается обнаружить таких объектов, то размещается новый пул большего размера. Память объектов фиксированного размера никогда не высвобождается в течение жизненного цикла интерпретатора, они просто повторно используются. =head2 Основная структура буферо подобных элементов struct parrot_object_t { struct { void *bufstart; size_t buflen; } b; unsigned flags; ... } PObj; Этот фрагмент не отражает полностью текущую реализацию, а только основную идею объектов. Вышепоказанная структура включает I<флаги(flags)> и является текущим буфером. Если к этой структуре добавить несколько полей типа I and I, можно получить I. Добавление I (и некоторых других членов структуры) дает I. =head1 Элементы переменного размера Эти элементы не живут в одиночестве, они являются частью структуры I, описанной выше и размещаются возле I. Такое размещение используется при управлении свободным списком буфера, причем I указывает на следующий объект. Элементы хранятся в двух различных пулах: I и I. Первый хранит все элементы переменного размера, последний - только строковые константы слово "string", так как у нас нет других константных элементов переменного размера для сохранения. Ниже указаны различные схемы размещения памяти: =head2 Копирующая сборка мусора(Copying GC) I<Пул памяти(memory_pool)> размещается в больших блоках, а именно I. Когда появляется необходимость во фрагмента памяти, например, для сохранения строки, то этот фрагмент вырезается из блока памяти, пока его память не будет полностью задействованна. Тогда всупает в действие сборка мусора(garbage collection(GC)). При сборке все живые элементы всех используемых блоков памяти помещаются в один новый блок, который после этого будет хранить только используемые элементы плотно упакованные вместе. Старые блоки памяти, содержащие разбросанные неиспользуемые фрагменты и используемые фрагменты, которые уже скопированны в новое место, высвобождаются. Если GC не может дать достоточно сбодного места для нового элемента. то к пулу памяти добавляется новый блок. Это также подразумевает, то что буферы перемещаются во время своей жизни. Поэтому пользователям буферов не позволено сохранять указатели на буфера на участках кода, которые могут вызывать запуск GC, как например, C или C. =head2 Дефрагментирующий аллокатор(Defragmentating allocator) Альтернативой предыдущей схеме является использование аллокатора памяти. Эта схема не уступает в скорости предыдущей и повторно использует высвобожденные элементы памяти сберегающем способом. На самом деле, такая схема обеспечивается реализацией malloc некоторых системных библиотек I, например, glibc malloc, основанный на аллокаторе Дуга Леа(Doug Lea). При использовании такого аллокатора, все элементы переменного размера либо просто размещаются с помощью обычного вызова malloc(), либо realloc() изменяет их размеры. Позднее, элементы высвобождаются, когда DOD обнаруживает, что заголовок хранимого буфера больше не используется. Нижележащий аллокатор собирает эти элементы, объединяет их в более крупные фрагменты, если это возможно, и помещает их в свободный список, отсортированный по размеру элементов. Со временем, когда прийдет новый запрос на размещение, они могут вернуться обратно. Таким образом, при такой схеме I для элементов переменного размера не используется. Вы можете полагать, что данный пул существует внутри аллокатора. Буфера, размещаемые по такой схеме перемещаются только при переразмещении. Опция I<--gc> сценария B позволяет вам выбрать любую из этих двух схем. =head2 Buffer_Tail и COW В обоих реализациях есть одна и та же проблема: при копировании строк (I) или частей строк(после вызова substr()) не размещается новое пространство в пуле памяти под новую строку или часть строки, а просто используется new_string_header(), устанавливается указатель на настоящую строку и записывается ее длина в I. Все это хорошо до тех пор, пока настоящая строка и ее "ленивая" копия не модифицируются. Все это известно как COW (копирование при записи). Проблема возникает потом, во время сборки мусора(или высвобождения буферов), а именно "кому принадлежит строка". Вы не должны копировать ту же самую строку в разные места, высвобождать одну и ту же строку более чем один раз (ваш отладчик скажет вам почему ...). Поэтому обе схемы используют часть размещаемой строки для своей бухгалтерии. Копирующая сборка мусора(copying GC) использует I в конце строки и помечает ее как COW с помощью I, сохраняет новый адрес в заголовке буфера, чтобы другие пользователи смогли дальше использовать сироку после ее обновления. При схеме malloc()/free() в I сохраняется общее число ссылок (refcount) на строку. Все мертвые объекты найденные в ходе DOD уменьшают счетчик, а живые - увеличивают. Когда счетчик становится равным нулю, память, связанная со строкой высвобождается. =head1 Упрощенное представление +---------+ +------------------<--| Арены |<-----------+ | +---------+-->--+ | | | | | +------+ +------------+ | +===============+ | | S0 |<--| Регистры |<--)--| Интерпретатор | | +------+ +------------+ | +===============+ | +---| S1 | | | | +------+ +----------+ +-------+ | | | Blk 1 |--)-->+----------+ +--------------+ +---------+ +-------+ | | Буфер 1 | | Строка1Строк | | Блок 1 | | Blk 2 | | +----------+ | а2Строка3.. | +---------+ +-------+ | | Буфер 2 | | ..СтрокаN.. |<--| Блок 2 | | . | | +----------+ +--------------+ +---------+ +-------+ | | ... | ^ ^ | ... | Пул | +----------+ | | +---------+ маленьких +-->| Буфер N |--------+----+ Пул памяти объектов +----------+ Блок памяти (Memory pool) (Small Obj Буфера (Memory Block) Pool) Теперь представьте, что I будет I, который живет в I нижележащего интерпретатора, который в данный момент запускает файл B, а теперь вернитесь к представлению и заполните там все пустые места ;-) =head1 ФАЙЛЫ smallobject.[ch], headers.c, resources.[ch], res_lea.c, dod.c, string.[ch], pobj.h. =head1 АВТОР Leopold Tцtsch