From 8554af7b6c3350a7bd644661868b38aa4fdb924e Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Wed, 10 Jun 2009 17:53:12 -0300 Subject: [PATCH] =?utf8?q?Agregar=20descripci=C3=B3n=20del=20GC=20actual?= =?utf8?q?=20de=20D?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Se completa la introducción al GC actual de D, la descripción de la organización del *heap* y la fase de marcado del algoritmo de recolección. --- source/dgc.rst | 472 ++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 465 insertions(+), 7 deletions(-) diff --git a/source/dgc.rst b/source/dgc.rst index 15d1b72..dc32223 100644 --- a/source/dgc.rst +++ b/source/dgc.rst @@ -28,21 +28,479 @@ TODO Recolector de basura actual de D ---------------------------------------------------------------------------- -TODO +Como paso básico fundamental para poder mejorar el recolector de basura de D_, +primero hay que entender la implementación actual, de forma de conocer sus +puntos fuertes, problemas y limitaciones, de manera tal de poder analizar +formas de mejorarlo. + +Como se mencionó en la sección :ref:`d_lang`, en D_ hay dos bibliotecas base +para soportar el lenguaje (*runtimes*): Phobos_ y Tango_. La primera es la +biblioteca estándar de D_, la segunda un proyecto más abierto y dinámico que +surgió como alternativa a Phobos_ debido a que Phobos_ es muy desprolija y que +era muy difícil impulsar cambios en ella. Ahora Phobos_ tiene el agravante de +estar *congelada* en su versión 1 (solo se realizan correcciones de errores). + +Dado que Tango_ está mejor organizada, su desarrollo es más abierto (aceptan +cambios y mejoras) y que hay una mayor disponibilidad de programas +y bibliotecas escritos para Tango_, en este trabajo se decide tomar esta +biblioteca *runtime* como base para el análisis y mejoras propuestas, a pesar +de ser Phobos_ la estándar. De todas formas el recolector de basura de Tango_ +es prácticamente el mismo que el de Phobos_, por lo tanto éste análisis en +particular es válido para cualquiera de las dos. + +El recolector actual es un recolector :ref:`indirecto `, :ref:`no +incremental ` que realiza un :ref:`marcado y barrido ` +relativamente básico. A diferencia del algoritmo clásico presentado éste +realiza un marcado no recursivo. La fase de marcado es :ref:`stop-the-world +`; si +bien posee alguna información de tipos (distingue entre celdas que pueden +tener punteros y celdas que definitivamente no los tienen, pero no dispone de +información sobre qué campos de las celdas son punteros y cuales no). Además +no tiene soporte alguno de :ref:`recolección particionada `. + +Si bien el recolector es bastante básico, posee una :ref:`organización de +memoria ` relativamente moderna (utiliza una :ref:`lista de libres +` con un *two level allocator*) y algunas optimizaciones +particulares para amortiguar casos patológicos. + + +.. _dgc_org: + +Organización del *heap* +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +La memoria del *heap* está organizada en *pools*. Un *pool* es una región de +*páginas* contíguas. Una página es, en general, la unidad mínima de memoria que +maneja un sistema operativo con soporte de memoria virtual. Cada página dentro +de un *pool* sirve a su vez como contenedora de bloques (llamados *bin* en la +:ref:`implementación `) de tamaño fijo. Todos los bloques +pertenecientes a la misma página tienen el mismo tamaño de bloque (ver figura +:vref:`fig:dgc-org`). Los tamaños de bloque posibles son potencias de 2 desde +16 bytes hasta 4096 (el tamaño típico de una página), es decir: 16, 32, 64, +128, 256, 512, 1024, 2048 y 4096 [#dgcpageplus]_. Todos los objetos, arreglos +o celdas en general se ubican en estos bloques (en uno del tamaño más pequeño +que haya que sea suficientemente grande como para almacenar dicho objeto). En +caso de que un objeto sea mayor a una página, se utilizan la menor cantidad de +páginas contíguas de un pool que tengan espacio suficiente para almacenar +dicho objeto. + +.. [#dgcpageplus] Además existe otro tamaño de bloque especial que se utiliza + para indicar la continuación de un objeto grande (que ocupan más de una + página). + +.. fig:: fig:dgc-org + + Organización del *heap* del recolector de basura actual de D. + + Organización del *heap*. En este ejemplo todos los *pools* tienen 2 páginas + excepto el *pool* 2 que tiene una sola. El tamaño de bloque que almacena + cada página varía entre 64 bytes (página 0 del *pool* 2) hasta 4096 (ambas + páginas del *pool* N) que es una página completa. + + .. aafig:: + :scale: 1.4 + + +----------------------------------------------------------------------+ + | Heap | + +======================================================================+ + | "Pool 0" "Pool 1" "Pool 2" "Pool 3" ... "Pool N" | + | +----------+ +----------+ +----------+ +----------+ +----------+ | + | | Página 0 | | Página 0 | | Página 0 | | Página 0 | ... | Página 0 | | + | | (8x512) | | (4x1024) | | (64x64) | | (2x2048) | ... | (1x4096) | | + | |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| || Bloque || ||qqqqqqqq|| || || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| || Bloque || ||qqqqqqqq|| || || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| |+--------+| ||qqqqqqqq|| |+--------+| || Bloque || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| || Bloque || ||qqqqqqqq|| || || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| || Bloque || ||qqqqqqqq|| || || || || | + | || Bloque || || || ||qqqqqqqq|| || || || || | + | |+--------+| |+--------+| |+--------+| |+--------+| |+--------+| | + | | Página 1 | | Página 1 | +----------+ | Página 1 | ... | Página 1 | | + | | (16x256) | | (8x512) | | (32x128) | ... | (1x4096) | | + | |+--------+| |+--------+| |+--------+| |+--------+| | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || Bloque || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| ||nnnnnnnn|| || || | + | |+--------+| || Bloque || ||nnnnnnnn|| || || | + | |+--------+| |+--------+| |+--------+| ... |+--------+| | + | +----------+ +----------+ +----------+ +----------+ | + +----------------------------------------------------------------------+ + +Cada página de un *pool* puede estar asignada a contener bloques de un tamaño +específico o puede estar libre. A su vez, cada bloque puede estar ocupado por +una celda o estar libre. Los bloques libres de un tamaño específico (a +excepción de aquellos bloques que ocupen una página entera) además forman +parte de una :ref:`lista de libres ` (ver figura +:vref:`fig:dgc-free-list`). Esto permite asignar objetos relativamente +pequeños de forma bastante eficiente. + +.. fig:: fig:dgc-free-list + + Ejemplo de listas de libres. + + .. digraph:: dgc_free_list + + margin = 0; + rankdir = LR; + ratio = fill; + size = "4.6,3.6"; + node [ shape = record, width = 0, height = 0 ]; + + subgraph cluster_heap { + style = solid; + color = black; + + free [ label = "Libres| 16| 32| 64| 128| 256| 512| 1024| 2048" ]; + + free:p16 -> b1 -> b2 -> b3; + free:p32 -> b4 -> b5 -> b6 -> b7 -> b8; + // free:p64 is empty + free:p128 -> b9; + free:p256 -> b10 -> b11; + free:p512 -> b12; + free:p1024 -> b13 -> b14; + free:p2048 -> b15 -> b16 -> b17; + } + + +Atributos de *pool* +^^^^^^^^^^^^^^^^^^^ +Cada *pool* tiene la siguiente información asociada: + +*number_of_pages*: + cantidad de páginas que tiene. Esta cantidad es fija en toda la vida de un + *pool*. + +*pages*: + bloque de memoria contíguo de tamaño ``PAGE_SIZE * number_of_pages`` + (siendo ``PAGE_SIZE`` el tamaño de página, que normalmente son 4096 bytes). + + +Atributos de página +^^^^^^^^^^^^^^^^^^^ +Cada página dentro de un *pool* tiene un único atributo asociado: *block_size*. +Se trata del tamaño de los bloques que almacena esta página. + +Una página siempre almacena bloques del mismo tamaño, que pueden ser 16, 32, +64, 128, 256, 512, 1024, 2048 o 4096 (llamado con el nombre especial +``PAGE``). Además hay dos tamaños de bloque símbólicos que tienen un +significado especial: + +``FREE``: + indica que la página está completamente libre y que la página está + disponible para albergar cualquier tamaño de bloque que sea necesario (pero + una vez que se le asignó un nuevo tamaño de bloque ya no puede ser cambiado + hasta que la página vuelva a liberarse por completo). + +``CONTINUATION``: + indica que esta página es la continuación de un objeto grande (es decir, + que ocupa una o más páginas). Luego se presentan más detalles sobre objetos + grandes. + +Las páginas con esto tamaños de bloque especiales (conceptualmente) no +contienen bloques. + + +Atributos de bloque +^^^^^^^^^^^^^^^^^^^ +Cada bloque tiene asociados varios atributos: + +*mark*: + utilizado en la fase de :ref:`marcado `, indica que un nodo + ya fue visitado (serían las celdas *negras* en la :ref:`abstracción + tricolor `). + +*scan*: + utilizado también en la fase de :ref:`marcado `, indica que + una celda visitada todavía tiene *hijas* sin marcar (serían las celdas + *grises* en la :ref:`abstracción tricolor `). + +*free*: + indica que el bloque está libre (no está siendo utilizado por ningún objeto + *vivo*). Esto es necesario solo por la forma en la que realiza el + :ref:`marcado ` y :ref:`barrido ` en el + :ref:`algoritmo actual ` (las celdas con el atributo este + atributo son tomadas como *basura* aunque estén marcadas con *mark*). +*final*: + indica que el bloque contiene un objeto que tiene un destructor (que debe + ser llamado cuando la celda pasa de *viva* a *basura*). -Diseño -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +*noscan*: + indica que el bloque contiene un objeto que no tiene punteros y por lo + tanto no debe ser marcado de forma conservativa (no tiene *hijas*). -.. Acá iría básicamente lo que escribí en el blog sobre la implmentación - actual -TODO +Objetos grandes +^^^^^^^^^^^^^^^ +El recolector de basura actual de D_ trata de forma diferente a los objetos +grandes. Todo objeto grande empieza en un bloque con tamaño ``PAGE`` +y (opcionalmente) continúa en los bloques contíguos subsiguientes que tengan +el tamaño de bloque ``CONTINUATION`` (si el objeto ocupa más que una página). +El fin de un objeto grande queda marcado por el fin del *pool* o una página +con tamaño de bloque distinto a ``CONTINUATION`` (lo que suceda primero). +Cuando un objeto grande se convierte en *basura*, todas sus páginas se liberan +por completo, siendo marcadas con tamaño ``FREE`` para que puedan ser +almacenado en ellas otros objetos grandes o incluso nuevos bloques de un +tamaño determinado. -Implementación + +.. _dgc_algo: + +Algoritmos del recolector +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +A continuación se explica como provee el recolector actual de D_ los servicios +básicos que debe proveer cualquier recolector, como se presentó en la sección +:ref:`gc_intro_services`. + +Cabe aclarar que se presenta una versión simplificada del algoritmo, o más +precisamente, de la implementación del algoritmo, ya que no se exponen en esta +sección muchas optimizaciones que harían muy compleja la tarea de explicar +como funciona conceptualmente. En la siguiente sección, :ref:`dgc_impl`, se +darán más detalles sobre las optimizaciones importantes y diferencias con el +algoritmo aquí presentado, junto con detalles sobre como se implementa la +organización del *heap* que se explicó en la sección anterior. + + +.. _dgc_algo_collect: + +Recolección +^^^^^^^^^^^ +A grandes razgos el algoritmo de recolección puede resumirse de las dos fases +básicas de cualquier algoritmo de :ref:`marcado y barrido `:: + + function collect() is + mark_phase() + sweep_phase() + + +.. _dgc_algo_mark: + +Fase de marcado +^^^^^^^^^^^^^^^ +Esta fase consiste de varios pasos, que pueden resumirse en el siguiente +algoritmo:: + + function mark_phase() is + more_to_scan = false + stop_the_world() + clear_mark_scan_bits() + mark_free_lists() + mark_static_data() + push_registers_into_stack() + mark_stacks() + mark_user_roots() + mark_heap() + start_the_world() + +La variable **global** ``more_to_scan`` indica al algoritmo iterativo cuando +debe finalizar: la función ``mark()`` (que veremos más adelante) lo pone en +``true`` cuando una nueva celda debe ser visitada, por lo tanto la iteración +se interrumpe cuando no hay más celdas por visitar. + +Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente +pausan y reanudan todos los hilos respectivamente:: + + function stop_the_world() is + foreach thread in threads + thread.pause() + + function start_the_world() is + foreach thread in threads + thread.resume() + +La función ``clear_mark_scan_bits()`` se encarga de resetear todos los +atributos *mark* y *scan* de cada bloque del *heap*:: + + function clear_mark_scan_bits() is + foreach pool in heap + foreach page in pool + foreach block in page + block.mark = false + block.scan = false + +La función ``mark_free_lists()`` por su parte se encarga de activar el bit +*mark* de todos los bloques de las listas de libres de manera de que la fase +de marcado (que es iterativa y realiza varias pasadas sobre **todo** el +*heap*, incluyendo las celdas libres) no visite las celdas libres perdiendo +tiempo sin sentido y potencialmente manteniendo *vivas* celdas que en +realdidad son *basura* (falsos positivos):: + + function mark_free_lists() is + foreach free_list in heap + foreach block in free_list + block.mark = true + block.free = true + +Notar que los bloques libres quedan entonces marcados aunque sean *basura* por +definición. Para evitar que en la etapa de barrido se tomen estos bloques como +celdas vivas, a todos los bloques en la lista de libres también se los marca +con el bit *free*, así el barrido puede tomar como *basura* estos bloques +aunque estén marcados. + +El *root set* está compuesto por el área de memoria estática (variables +globales), los *stacks* de todos los hilos y los registros del procesador. +Primero se marca el área de memoria estática de manera :ref:`conservativa +` (es decir, tomando cada *word* como si fuera un puntero):: + + function mark_static_data() is + foreach word in static_data + pointer = cast(void*) word + mark(pointer) + +Para poder tomar los registros como parte del *root set* primero se apilan +en el *stack* a través de la función:: + + function push_registers_into_stack() is + foreach register in registers + push(register) + +Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos +los threads para terminar de marcar el *root set*:: + + function mark_stacks() is + foreach thread in threads + foreach word in thread.stack + pointer = cast(void*) word + mark(pointer) + +Dado que D_ soporta manejo de memoria manual al mismo tiempo que memoria +automática, es posible que existan celdas de memoria que no estén en el *root +set* convencional ni en el *heap* del recolector. Para evitar que se libere +alguna celda que estaba siendo referenciada desde memoria administrada por el +usuario, éste debe informarle al recolector sobre la existencia de estoas +nuevas raíces. Es por esto que para concluir el marcado del *root set* +completo se procede a marcar las raíces definidas por el usuario:: + + function mark_user_roots() is + foreach pointer in user_roots + mark(pointer) + +El algoritmo de marcado no es recursivo sino iterativo por lo tanto al marcar +una celda (o bloque) no se siguen sus *hijas*, solo se activa el bit de *scan* +(a menos que la celda no contenga punteros, es decir, tenga el bit *noscan*):: + + function mark(pointer) is + [pool, page, block] = find_block(pointer) + if block is not null and block.mark is false + block.mark = true + if block.noscan is false + block.scan = true + more_to_scan = true + +Por lo tanto en este punto, tenemos todas las celdas inmediatamente +alcanzables desde el *root set* marcadas y con el bit *scan* activado si la +celda puede contener punteros. Por lo tanto solo resta marcar (nuevamente de +forma conservativa) iterativamente todo el *heap* hasta que no hayan más +celdas para visitar (con el bit *scan* activo):: + + function mark_heap() is + while more_to_scan + more_to_scan = false + foreach pool in heap + foreach page in pool + if page.block_size <= PAGE // saltea FREE y CONTINUATION + foreach block in page + if block.scan is true + block.scan = false + if page.block_size is PAGE // objeto grande + start = cast(byte*) page + end = find_big_object_end(pool, page) + foreach word in start..end + pointer = cast(void*) word + mark(pointer) + else // objeto pequeño + foreach word in block + pointer = cast(void*) word + mark(pointer) + +Aquí puede verse, con un poco de esfuerzo, la utilización de la +:ref:`abtracción tricolor `: todas las celdas alcanzables +desde el *root set* son pintadas de *gris* (tienen los bits *mark* y *scan* +activados), excepto aquellas celdas atómicas (es decir, que se sabe que no +tienen punteros) que son marcadas directamente de *negro*. Luego se van +obteniendo celdas del conjunto de las *grises*, se las pinta de *negro* (es +decir, se desactiva el big *scan*) y se pintan todas sus *hijas* de *gris* (o +*negro* directamente si no tienen punteros). Este procedimiento se repite +mientras el conjunto de celdas *grises* no sea vacío (es decir, que +``more_to_scan`` sea ``true``). + +A continuación se presenta la implementación de las funciones suplementarias +utilizadas en la fase de marcado:: + + function find_big_object_end(pool, page) is + pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages) + do + page = cast(byte*) page + PAGE_SIZE + while page.block_size is CONTINUATION and page < pool_end + return page + + function find_block(pointer) is + foreach pool in heap + foreach page in pool + if page.block_size is PAGE + big_object_start = cast(byte*) page + big_object_end = find_big_object_end(pool, page) + if big_object_start <= pointer < big_object_end + return [pool, page, big_object_start] + else if page.bloc_size < PAGE + foreach block in page + block_start = cast(byte*) block + block_end = block_start + page.block_size + if block_start <= pointer < block_end + return [pool, page, block_start] + return [null, null, null] + +Cabe destacar que la función ``find_block()`` devuelve el pool, la página y el +comienzo del bloque al que apunta el puntero, es decir, soporta punteros +*interiores*. + + +.. _dgc_algo_sweep: + +Fase de barrido +^^^^^^^^^^^^^^^ +Esta fase es considerablemente más sencilla que el marcado; el algoritmo puede +dividirse en dos pasos básicos:: + + function sweep_phase() is + sweep() + rebuild_free_lists() + +El barrido se realiza con una pasada por sobre todo el heap + + + +.. _dgc_impl: + +Detalles de implementación ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. Acá diría por qué hay que reescribirlo para usar lo que está -- 2.43.0