X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/cd72488b3ee04f5e0f47b3ead9303c5bf96b5879..refs/heads/master:/source/dgc.rst?ds=sidebyside diff --git a/source/dgc.rst b/source/dgc.rst index cb59594..497e20e 100644 --- a/source/dgc.rst +++ b/source/dgc.rst @@ -1,145 +1,2121 @@ -.. Describe más detalladamente los problemas actuales del recolector de - basura de D, sentando las bases para el análisis de los requerimientos - de recolección de basura en dicho lenguaje (se explica por qué las - particularidades descriptas en la sección anterior complican la - recolección de basura y cuales son las que más molestan). - ESTADO: SIN EMPEZAR, REVISAR LO HECHO - - -.. _ref_dgc: +.. _dgc: Recolección de basura en D ============================================================================ -TODO +D_ propone un nuevo desafío en cuanto al diseño de un recolector de basura, +debido a la gran cantidad de características que tiene y paradigmas que +soporta. + +D_ ya cuenta con un recolector que hace lo necesario para funcionar de forma +aceptable, pero su diseño e implementación son relativamente sencillos +comparados con el :ref:`estado del arte ` de la recolección de basura +en general. Además la implementación actual presenta una serie de problemas +que se evidencia en las quejas que regularmente la comunidad de usuarios de D_ +menciona en el grupo de noticias. +En esta sección se analizarán las necesidades particulares de D_ con respecto +a la recolección de basura. También se analiza el diseño e implementación del +recolector actual, presentando sus fortalezas y debilidades. Finalmente se +analiza la viabilidad de los diferentes algoritmos vistos en :ref:`gc_art`. -Dificultades para recolectar basura en D + +.. _dgc_needs: + +Características y necesidades particulares de D_ ---------------------------------------------------------------------------- -TODO +En esta sección se hará un recorrido por las características y necesidades +particulares que tiene D_ como lenguaje con respecto a la recolección de +basura. + + + +.. _dgc_prob_low_level: + +Programación de bajo nivel (*system programming*) +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Sin dudas las características de D_ que lo hacen más complejo a la hora de +implementar un recolector de basura son sus capacidades de programación de +bajo nivel (ver :ref:`d_low_level`). + +Al proveer acceso a *assembly*, permitir estructuras de tipo *union* y ser +compatible con C/C++, el recolector de basura tiene muchas restricciones. Por +ejemplo debe tratar de forma conservativa los registros y el *stack*, ya que +es la única forma de interactuar de forma segura con C/C++ y *assembly*. + +Además debe poder interactuar con manejo de memoria explícito, ya sea +omitiendo por completo el *heap* del recolector o liberando explícitamente +memoria de éste. Esta característica es muy inusual en un recolector, +a excepción de recolectores conservativos diseñados para C/C++ que tienen las +mismas (o más) limitaciones. + +La posibilidad de controlar la alineación de memoria es otra complicación +sobre el recolector de basura, incluso aunque éste sea conservativo. Dado que +tratar la memoria de forma conservativa byte a byte sería impracticable (tanto +por la cantidad de *falsos positivos* que esto provocaría como por el impacto +en el rendimiento por el exceso de posibles punteros a revisar, además de lo +ineficiente que es operar sobre memoria no alineada), en general el recolector +asume que el usuario nunca va a tener la única referencia a un objeto en una +estructura no alineada al tamaño de palabra. + + + +.. _d_prob_high_level: + +Programación de alto nivel +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Las características de programación de alto nivel también impone dificultades +o restricciones al recolector de basura (ver :ref:`d_high_level`). Por ejemplo +el soporte de rebanado (*slicing*) de arreglos hace que el recolector deba +soportar punteros *interiores* [#dgcinterior]_ (esto también es necesario +porque en general en D_ o en cualquier lenguaje de bajo nivel se puede tener +un puntero a cualquier parte de una celda). + +.. [#dgcinterior] Los punteros *interiores* son aquellos que en vez de apuntar + al inicio de una celda, apuntan a una dirección arbitraria dentro de ella. + Esto no es posible en muchos lenguajes de programación, como por ejemplo + Java_, lo que simplifica la recolección de basura. + +Los arreglos dinámicos y asociativos en particular dependen fuertemente del +recolector de basura, en particular cuando se agregan elementos (o se +concatenan dos arreglos). + +Dado que los *strings* son arreglos dinámicos y que el lenguaje provee un buen +soporte de arreglos dinámicos y asociativos y *slicing*, es de esperarse que +el recolector deba comportarse de forma correcta y eficiente ante las +operaciones más típicas de estas estructuras que dependan de él. + +.. _dgc_prob_types: -.. _ref_dgc_actual: +Información de tipos +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Hasta aquí D_ comparte todas las restricciones con respecto a la recolección +de basura con los lenguajes de bajo nivel que no tienen ningún soporte para +recolectar basura. Sin embargo, a diferencia de éstos, D_ tiene una +información de tipos más rica. Al momento de asignar memoria D_ puede proveer +cierta información sobre el objeto a asignar (como si puede contener punteros +o no) que puede ser utilizada por el recolector para realizar una recolección +más precisa (ver :ref:`gc_conserv`). + +En general esta información no es suficiente como para implementar un +recolector completamente preciso (no al menos sin agregar un mejor soporte de +reflexión al lenguaje) pero puede ser de ayuda considerable para el +recolector. + + + +.. _dgc_prob_final: + +Orientación a objetos y finalización +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +D_ soporta el paradigma de orientación a objetos, donde es común permitir que +un objeto, al ser destruido, realice alguna tarea de finalización (a través de +una función miembro llamada *destructor*, o ``~this()`` en D_). Esto significa +que el recolector, al encontrar que no hay más referencias a un objeto, debe +ejecutar el destructor. + +La especificación dice [DWDE]_: + + The garbage collector is not guaranteed to run the destructor for all + unreferenced objects. Furthermore, the order in which the garbage collector + calls destructors for unreference objects is not specified. This means that + when the garbage collector calls a destructor for an object of a class that + has members that are references to garbage collected objects, those + references may no longer be valid. This means that destructors cannot + reference sub objects. + +Afortunadamente el orden de finalización no está definido, ya que esto sería +extremadamente difícil de proveer por un recolector (si no imposible). Esto +significa que si bien se ejecutan los destructores de los objetos que dejan de +ser alcanzables desde el *root set*, no se define en que orden se hace, y por +lo tanto un objeto no puede acceder a sus atributos que sean referencias +a otros objetos en un destructor. + +Esta restricción en realidad se ve relaja con el soporte de *RAII*. Si se +utiliza la palabra clave ``scope`` al crear una serie de objetos, estos serán +destruidos determinísticamente al finalizar el *scope* actual en el orden +inverso al que fueron creados y, por lo tanto, un usuario podría hacer uso de +los atributos que sean referencias a otros objetos creados con ``scope`` si el +orden en que fueron creados (y por lo tanto en que serán destruidos) se lo +permite. + +Sin embargo no hay forma actualmente de saber dentro de un destructor si éste +fue llamado determinísticamente o no, por lo tanto es virtualmente imposible +hacer uso de esta distinción, a menos que una clase sea declarada para ser +creada solamente utilizando la palabra reservada ``scope``. + +Cabe aclarar que, estrictamente hablando y según la especificación de D_, el +recolector no debe garantizar la finalización de objetos bajo ninguna +circunstancia, es decir, el recolector podría no llamar a ningún destructor. +Sin embargo esto es probablemente una vaguedad en la redacción y dadas las +garantías que provee la implementación actual la comunidad de D_ cuenta con +ellas. + + + +.. _dgc_actual: 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. +Como se mencionó en la sección :ref:`d_lang`, 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_ dado que estaba muy descuidada 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. -Diseño +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* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -.. Acá iría básicamente lo que escribí en el blog sobre la implmentación - actual +La memoria del *heap* está organizada en *pools*. Un *pool* es una región de +*páginas* contiguas. 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 contiguas 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). + +.. flt:: 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: 120 + + +----------------------------------------------------------------------+ + | 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 tener asignado un tamaño de bloque 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. + +.. flt:: 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 contiguo 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 simbólicos que tienen un +significado especial: + +``FREE`` + Indica que la página está completamente libre y 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 dos o más páginas). Luego se presentan más detalles sobre objetos + grandes. + +Las páginas con estos 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 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*). + +*noscan* + Indica que el bloque contiene un objeto que no tiene punteros y por lo + tanto no debe ser escaneado (no tiene *hijas*). + + +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 contiguos 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. + + + +.. _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 rasgos 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 describirse con el siguiente +algoritmo:: + + function mark_phase() is + global more_to_scan = false + stop_the_world() + clear_mark_scan_bits() + mark_free_lists() + mark_static_data() + push_registers_into_stack(thread_self) + thread_self.stack.end = get_stack_top() + mark_stacks() + pop_registers_from_stack(thread_self) + 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_range()`` (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()`` pausan y reanudan +todos los hilos respectivamente (salvo el actual). Al pausar los hilos además +se apilan los registros del procesador en el *stack* y se guarda la posición +actual del *stack* para que la fase de marcado pueda recorrerlos [#dgcstw]_:: + + function stop_the_world() is + foreach thread in threads + if thread is thread_self + continue + thread.pause() + push_registers_into_stack(thread) + thread.stack.end = get_stack_top() + + function start_the_world() is + foreach thread in reversed(threads) + if thread is thread_self + continue + pop_registers_from_stack(thread) + thread.resume() + +.. [#dgcstw] El procedimiento para apilar y desapilar los registros en el + *stack* se realiza en realidad utilizando las señales ``SIGUSR1`` + y ``SIGUSR2`` (respectivamente). Es el manejador de la señal el que en + realidad apila y desapila los registros y guarda el puntero al *stack*. Se + omiten los detalles para simplificar la explicación del algoritmo. + +La función ``clear_mark_scan_bits()`` se encarga de restablecer 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 +realidad son *basura* (*falsos positivos*):: + + function mark_free_lists() is + foreach free_list in free_lists + 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 + mark_range(static_data.begin, static_data.end) + +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(thread) is + foreach register in thread.registers + push(register) + +Y luego, al reiniciar los hilos cuando se termina de marcar, se descartan +sacándolos de la pila (no es necesario ni correcto restablecer los valores ya +que podrían tener nuevos valores):: + + function pop_registers_from_stack(thread) is + foreach register in reverse(thread.registers) + pop() + +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 + mark_range(thread.stack.begin, thread.stack.end) + +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 a la cual todavía existen referencias desde memoria administrada +por el usuario, éste debe informarle al recolector sobre la existencia de +estas 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 root_range in user_roots + mark_range(root_range.begin, root_range.end) + +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_range(begin, end) is + pointer = begin + while pointer < end + [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 + global more_to_scan = true + pointer++ + +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 global more_to_scan + global 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 + begin = cast(byte*) page + end = find_big_object_end(pool, page) + mark_range(begin, end) + else // objeto pequeño + mark_range(block.begin, block.end) + +Aquí puede verse, con un poco de esfuerzo, la utilización de la +:ref:`abstracció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 bit *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.block_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* de la siguiente +manera:: + + function sweep() is + foreach pool in heap + foreach page in pool + if page.block_size <= PAGE // saltea FREE y CONTINUATION + foreach block in page + if block.mark is false + if block.final is true + finalize(block) + block.free = true + block.final = false + block.noscan = false + if page.block_size is PAGE // objeto grande + free_big_object(pool, page) + +Como se observa, se recorre todo el *heap* en busca de bloques y páginas +libres. Los bloques libres son marcados con el atributo ``free`` y las páginas +libres son marcadas con el tamaño de bloque simbólico ``FREE``. Para los +objetos grandes se marcan todas las páginas que utilizaban como ``FREE``:: + + function free_big_object(pool, page) is + pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages) + do + page.block_size = FREE + page = cast(byte*) page + PAGE_SIZE + while page < pool_end and page.block_size is CONTINUATION + +Además, los bloques que tienen en atributo ``final`` son finalizados llamando +a la función ``finalize()``. Esta función es un servicio que provee la +biblioteca *runtime* y en última instancia llama al destructor del objeto +almacenado en el bloque a liberar. + +Una vez marcados todos los bloques y páginas con ``free``, se procede +a reconstruir las listas de libres. Como parte de este proceso se buscan las +páginas que tengan todos los bloques libres para marcar la página completa +como libre (de manera que pueda utilizarse para albergar otro tamaño de bloque +u objetos grandes de ser necesario):: + + function rebuild_free_lists() is + foreach free_list in free_lists + free_list.clear() + foreach pool in heap + foreach page in pool + if page.block_size < PAGE // objetos pequeños + if is_page_free(page) + page.block_size = FREE + else + foreach block in page + if block.free is true + free_lists[page.block_size].link(block) + +Esta reorganización de listas libres además mejoran la localidad de +referencia y previenen la fragmentación. La localidad de referencia se ve +mejorada debido a que asignaciones de memoria próximas en el tiempo serán +también próximas en espacio porque pertenecerán a la misma página (al menos si +las asignaciones son todas del mismo tamaño). La fragmentación se minimiza por +el mismo efecto, primero se asignarán todos los bloques de la misma página. + +A continuación se presenta la implementación de una de las funciones +suplementarias de la fase de barrido:: + + function is_page_free(page) is + foreach block in page + if block.free is false + return false + return true + +Las demás funciones suplementarias pertenecen a la manipulación de listas +libres que no son más que operaciones sobre una lista simplemente enlazada. En +la sección :ref:`dgc_impl` se verá con más detalles como las implementa el +recolector actual. + + +.. _dgc_algo_alloc: + +Asignación de memoria +^^^^^^^^^^^^^^^^^^^^^ +La asignación de memoria del recolector es relativamente compleja, excepto +cuando se asigna un objeto pequeño y ya existe algún bloque con el tamaño +preciso en la lista de libres. Para el resto de los casos la cantidad de +trabajo que debe hacer el recolector para asignar la memoria es considerable. + +El algoritmo de asignación de memoria se puede resumir así:: + + function new(size, attrs) is + block_size = find_block_size(size) + if block_size < PAGE + block = new_small(block_size) + else + block = new_big(size) + if block is null + throw out_of_memory + if final in attrs + block.final = true + if noscan in attrs + block.noscan = true + return cast(void*) block + +La función ``find_block_size()`` sencillamente busca el tamaño de bloque se +mejor se ajuste al tamaño solicitado (es decir, el bloque más pequeño lo +suficientemente grande como para poder almacenar el tamaño solicitado). Una +vez más el algoritmo distingue objetos grandes de pequeños. Los pequeños se +asignan de las siguiente manera:: + + function new_small(block_size) is + block = find_block_with_size(block_size) + if block is null + collect() + block = find_block_with_size(block_size) + if block is null + new_pool() + block = find_block_with_size(block_size) + return block + +Se intenta reiteradas veces conseguir un bloque del tamaño correcto libre, +realizando diferentes acciones si no se tiene éxito. Primero se intenta hacer +una :ref:`recolección ` y si no se puede encontrar +suficiente espacio luego de ella se intenta crear un nuevo *pool* de memoria +pidiendo memoria al *low level allocator* (el sistema operativo generalmente). + +Para intentar buscar un bloque de memoria libre se realiza lo siguiente:: + + function find_block_with_size(block_size) is + block = free_lists[block_size].pop_first() + if block is null + assign_page(block_size) + block = free_lists[block_size].pop_first() + return block + +Donde ``pop_first()`` retorna ``null`` si la lista estaba vacía. Si no se +puede obtener un bloque de la lista de libres correspondiente, se busca +asignar una página libre al tamaño de bloque deseado de forma de *alimentar* +la lista de libres con dicho tamaño:: + + function assign_page(block_size) is + foreach pool in heap + foreach page in pool + if page.block_size is FREE + page.block_size = block_size + foreach block in page + free_lists[page.block_size].link(block) + +Cuando todo ello falla, el último recurso consiste en pedir memoria al sistema +operativo, creando un nuevo *pool*:: + + function new_pool(number_of_pages = 1) is + pool = alloc(pool.sizeof) + if pool is null + return null + pool.number_of_pages = number_of_pages + pool.pages = alloc(number_of_pages * PAGE_SIZE) + if pool.pages is null + free(pool) + return null + heap.add(pool) + foreach page in pool + page.block_size = FREE + return pool + +Se recuerda que la función ``alloc()`` es un :ref:`servicio +` provisto por el *low level allocator* y en la +implementación actual de D_ en general es el sistema operativo (aunque +opcionalmente puede utilizarse la biblioteca estándar de C, que a su vez +utiliza el sistema operativo). + +Cualquier error en estas funciones es propagado y en última instancia, cuando +todo falla, la función ``new()`` termina lanzando una excepción indicando que +se agotó la memoria. + +Si el tamaño de bloque necesario para cumplir con la asignación de memoria es +de una o más páginas, entonces se utiliza otro algoritmo para alocar un objeto +grande:: + + function new_big(size) is + number_of_pages = ceil(size / PAGE_SIZE) + pages = find_pages(number_of_pages) + if pages is null + collect() + pages = find_pages(number_of_pages) + if pages is null + minimize() + pool = new_pool(number_of_pages) + if pool is null + return null + pages = assign_pages(pool, number_of_pages) + pages[0].block_size = PAGE + foreach page in pages[1..end] + page.block_size = CONTINUATION + return pages[0] + +De forma similar a la asignación de objetos pequeños, se intenta encontrar una +serie de páginas contiguas, dentro de un mismo *pool*, suficientes para +almacenar el tamaño requerido y si esto falla, se realizan diferentes pasos +y se vuelve a intentar. Puede observarse que, a diferencia de la asignación de +objetos pequeños, si luego de la recolección no se pudo encontrar lugar +suficiente, se trata de minimizar el uso de memoria física utilizando la +siguiente función, que devuelve al *low level allocator* los *pools* +completamente libres:: + + function minimize() is + foreach pool in heap + all_free = true + foreach page in pool + if page.block_size is not FREE + all_free = false + break + if all_free is true + free(pool.pages) + free(pool) + heap.remove(pool) + +Volviendo a la función ``new_big()``, para hallar una serie de páginas +contiguas se utiliza el siguiente algoritmo:: + + function find_pages(number_of_pages) is + foreach pool in heap + pages = assign_pages(pool, number_of_pages) + if pages + return pages + return null + +Como se dijo, las páginas deben estar contenidas en un mismo *pool* (para +tener la garantía de que sean contiguas), por lo tanto se busca *pool* por +*pool* dicha cantidad de páginas libres consecutivas a través del siguiente +algoritmo:: + + function assign_pages(pool, number_of_pages) is + pages_found = 0 + first_page = null + foreach page in pool + if page.block_size is FREE + if pages_found is 0 + pages_found = 1 + first_page = page + else + pages_found = pages_found + 1 + if pages_found is number_of_pages + return [first_page .. page] + else + pages_found = 0 + first_page = null + return null + +Una vez más, cuando todo ello falla (incluso luego de una recolección), se +intenta alocar un nuevo *pool*, esta vez con una cantidad de páginas +suficientes como para almacenar el objeto grande y si esto falla el error se +propaga hasta la función ``new()`` que lanza una excepción. + + +.. _dgc_algo_free: + +Liberación de memoria +^^^^^^^^^^^^^^^^^^^^^ +La liberación de la memoria asignada puede hacerse explícitamente. Esto +saltea el mecanismo de recolección, y es utilizado para dar soporte a manejo +explícito de memoria asignada en el *heap* del recolector. En general el +usuario no debe utilizar liberación explícita, pero puede ser útil en casos +muy particulares:: + + function delete(pointer) is + [pool, page, block_start] = find_block(pointer) + if block is not null + block.free = true + block.final = false + block.noscan = false + if page.block_size is PAGE // objeto grande + free_big_object(pool, page) + else // objeto pequeño + free_lists[page.block_size].link(block) + +Como se puede observar, si el objeto es pequeño se enlaza a la lista de libres +correspondiente y si es grande se liberan todas las páginas asociadas a éste, +de forma similar a la :ref:`fase de barrido `. A diferencia de +ésta, no se finaliza el objeto (es decir, no se llama a su destructor). + + +.. _dgc_algo_final: + +Finalización +^^^^^^^^^^^^ +Al finalizar el programa, el recolector es finalizado también y lo que realiza +actualmente, además de liberar la memoria propia del recolector, es realizar +una recolección. Es decir, si hay objetos que son todavía alcanzables desde el +*root set*, esos objetos no son finalizados (y por lo tanto sus destructores +no son ejecutados). + +Como se ha visto, esto es perfectamente válido ya que D_ no garantiza que los +objetos sean finalizados. + + + +.. _dgc_impl: + +Detalles de implementación +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Hay varias diferencias a nivel de implementación entre lo que se presentó en +las secciones anteriores y como está escrito realmente el recolector actual. +Con los conceptos e ideas principales ya explicadas, se procede a ahondar con +más detalle en como está construido el recolector y algunas de sus +optimizaciones principales. + +Vale aclarar que el recolector de basura actual está implementado en D_. + + +Estructuras de datos del recolector +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +El recolector está principalmente contenido en la estructura llamada ``Gcx``. +Dicha estructura tiene los siguientes atributos (divididos en categorías para +facilitar la comprensión): + +Raíces definidas por el usuario + *roots* (*nroots*, *rootdim*) + Arreglo variable de punteros simples que son tomados como raíces + provistas por el usuario. + + *ranges* (*nranges*, *rangedim*) + Arreglo variable de rangos de memoria que deben ser revisados (de forma + conservativa) como raíces provistas por el usuario. Un rango es una + estructura con dos punteros: ``pbot`` y ``ptop``. Toda la memoria entre + estos dos punteros se toma, palabra por palabra, como una raíz del + recolector. + +Estado interno del recolector + *anychanges* + Variable que indica si en la fase de marcado se encontraron nuevas + celdas con punteros que deban ser visitados. Otra forma de verlo es como + un indicador de si el conjunto de celdas *grises* está vacío luego de + una iteración de marcado (utilizando la :ref:`abstracción tricolor + `). Es análoga a la variable ``more_to_scan`` + presentada en :ref:`dgc_algo_mark`. + + *inited* (sic) + Indica si el recolector fue inicializado. + + *stackBottom* + Puntero a la base del *stack* (asumiendo que el stack crece hacia arriba). + Se utiliza para saber por donde comenzar a visitar el *stack* de forma + conservativa, tomándolo con una raíz del recolector. + + *Pools* (*pooltable*, *npools*) + Arreglo variable de punteros a estructuras ``Pool`` (ver más adelante). + Este arreglo se mantiene siempre ordenado de menor a mayor según la + dirección de memoria de la primera página que almacena. + + *bucket* + Listas de libres. Es un arreglo de estructuras ``List`` utilizadas para + guardar la listas de libres de todos los tamaños de bloques posibles (ver + más adelante). -TODO +Atributos que cambian el comportamiento + *noStack* + Indica que no debe tomarse al *stack* como raíz del recolector. Esto es + muy poco seguro y no debería ser utilizado nunca, salvo casos + extremadamente excepcionales. + *log* + Indica si se debe guardar un registro de la actividad del recolector. Es + utilizado principalmente para depuración. + *disabled* + Indica que no se deben realizar recolecciones implícitamente. Si al + tratar de asignar memoria no se puede hallar celdas libres en el *heap* + del recolector, se pide más memoria al sistema operativo sin correr una + recolección para intentar recuperar espacio. Esto es particularmente + útil para secciones de un programa donde el rendimiento es crítico y no + se pueden tolerar grandes pausas como las que puede provocar el + recolector. -Implementación +Optimizaciones + *p_cache*, *size_cache* + Caché del tamaño de bloque para un puntero dado. Obtener el tamaño de un + bloque es una tarea costosa y común. Para evitarla en casos donde se + calcula de forma sucesiva el tamaño del mismo bloque (como puede ocurrir + al concatenar arreglos dinámicos) se guarda en un caché (de un solo + elemento) el último valor calculado. + + *minAddr*, *maxAddr* + Punteros al principio y fin del *heap*. Pueden haber *huecos* entre + estos dos punteros que no pertenezcan al *heap* pero siempre se cumple + que si un puntero apunta al *heap* debe estar en este rango. Esto es + útil para hacer un cálculo rápido para descartar punteros que fueron + tomados de forma conservativa y en realidad no apuntan al *heap* (ver la + función ``find_block()`` en :ref:`dgc_algo_mark`). + + +*Pools* +^^^^^^^ +La primera diferencia es como está organizado el *heap*. Si bien la +explicación presentada en la sección :ref:`dgc_org` es correcta, la forma en +la que está implementado no es tan *naïve* como los algoritmos presentados en +:ref:`dgc_algo` sugieren. + +El recolector guarda un arreglo variable de estructuras ``Pool``. Cabe +destacar que para implementar el recolector no se pueden utilizar los arreglos +dinámicos de D_ (ver sección :ref:`d_high_level`) dado que éstos utilizan de +forma implícita el recolector de basura, por lo tanto todos los arreglos +variables del recolector se implementan utilizando las funciones de +C :manpage:`malloc(3)`, :manpage:`realloc(3)` y :manpage:`free(3)` +directamente. + + +La estructura ``Pool`` está compuesta por los siguientes atributos (ver figura +:vref:`fig:dgc-pool`): + +.. flt:: fig:dgc-pool + + Vista gráfica de la estructura de un *pool* de memoria + + .. aafig:: + :scale: 120 + + /--- "baseAddr" "ncommitted = i" "topAddr" ---\ + | V | + |/ |/ |/ + +---- "committed" -----+------- "no committed" ----------+ + /| /| /| + V V V + +--------+--------+-----+--------+-----+-------------------+ + páginas | 0 | 0 | ... | i | ... | "npages - 1" | + +--------+--------+-----+--------+-----+-------------------+ + A A A A A A + | | | | | | + +--------+--------+-----+--------+-----+-------------------+ + pagetable | Bins 0 | Bins 1 | ... | Bins i | ... | "Bins (npages-1)" | + +--------+--------+-----+--------+-----+-------------------+ + +*baseAddr* y *topAddr* + Punteros al comienzo y fin de la memoria que almacena todas las páginas del + *pool* (*baseAddr* es análogo al atributo *pages* utilizado en las + secciones anteriores para mayor claridad). + +*mark*, *scan*, *freebits*, *finals*, *noscan* + Conjuntos de bits (*bitsets*) para almacenar los indicadores descriptos en + :ref:`dgc_org` para todos los bloques de todas las páginas del *pool*. + *freebits* es análogo a *free* y *finals* a *final* en los atributos + descriptos en las secciones anteriores. + +*npages* + Cantidad de páginas que contiene este *pool* (fue nombrado + *number_of_pages* en las secciones anteriores para mayor claridad). + +*ncommitted* + Cantidad de páginas *encomendadas* al sistema operativo (*committed* en + inglés). Este atributo no se mencionó anteriormente porque el manejo de + páginas encomendadas le agrega una complejidad bastante notable al + recolector y es solo una optimización para un sistema operativo en + particular (Microsoft Windows). + +*pagetable* + Arreglo de indicadores de tamaño de bloque de cada página de este *pool*. + Los indicadores válidos son ``B_16`` a ``B_2048`` (pasando por los valores + posibles de bloque mencionados anteriormente, todos con el prefijo + "``B_``"), ``B_PAGE``, ``B_PAGEPLUS`` (análogo a ``CONTINUATION``), + ``B_UNCOMMITTED`` (valor que tienen las páginas que no fueron encomendadas + aún) y ``B_FREE``. + +Como se observa, además de la información particular del *pool* se almacena +toda la información de páginas y bloques enteramente en el *pool* también. +Esto simplifica el manejo de lo que es memoria *pura* del *heap*, ya que queda +una gran porción continua de memoria sin estar intercalada con +meta-información del recolector. + +Para poder acceder a los bits de un bloque en particular, se utiliza la +siguiente cuenta para calcular el índice en el *bitset*: + +.. math:: + + index(p) = \frac{p - baseAddr}{16} + +Donde ``p`` es la dirección de memoria del bloque. Esto significa que, sin +importar cual es el tamaño de bloque de las páginas del *pool*, el *pool* +siempre reserva suficientes bits como para que todas las páginas puedan tener +tamaño de bloque de 16 bytes. Esto puede ser desperdiciar bastante espacio si +no predomina un tamaño de bloque pequeño. + + +Listas de libres +^^^^^^^^^^^^^^^^ +Las listas de libres se almacenan en el recolector como un arreglo de +estructuras ``List``, que se compone solamente de un atributo ``List* next`` +(es decir, un puntero al siguiente). Entonces cada elemento de ese arreglo es +un puntero al primer elemento de la lista en particular. + +La implementación utiliza a los bloques de memoria como nodos directamente. +Como los bloques siempre pueden almacenar una palabra (el bloque de menor +tamaño es de 16 bytes y una palabra ocupa comúnmente entre 4 y 8 bytes según +se trabaje sobre arquitecturas de 32 o 64 bits respectivamente), se almacena +el puntero al siguiente en la primera palabra del bloque. + + +Algoritmos +^^^^^^^^^^ +Los algoritmos en la implementación real son considerablemente menos modulares +que los presentados en la sección :ref:`dgc_algo`. Por ejemplo, la función +``collect()`` es una gran función de 300 líneas de código fuente. + +A continuación se resumen las funciones principales, separadas en categorías +para facilitar la comprensión. Los siguientes son métodos de la estructura +``Gcx``: + +Inicialización y terminación + *initialize()* + Inicializa las estructuras internas del recolector para que pueda ser + utilizado. Esta función la llama la biblioteca *runtime* antes de que el + programa comience a correr. + + *Dtor()* + Libera todas las estructuras que utiliza el recolector. + +Manipulación de raíces definidas por el usuario + *addRoot(p)*, *removeRoot(p)*, *rootIter(dg)* + Agrega, remueve e itera sobre las raíces simples definidas por el + usuario. + + *addRange(pbot, ptop)*, *remove range(pbot)*, *rangeIter(dg)* + Agrega, remueve e itera sobre los rangos de raíces definidas por el + usuario. + +Manipulación de bits indicadores + *getBits(pool, biti)* + Obtiene los indicadores especificados para el bloque de índice ``biti`` + en el *pool* ``pool``. + + *setBits(pool, biti, mask)* + Establece los indicadores especificados en ``mask`` para el bloque de + índice ``biti`` en el *pool* ``pool``. + + *clrBits(pool, biti, mask)* + Limpia los indicadores especificados en ``mask`` para el bloque de + índice ``biti`` en el *pool* ``pool``. + + Cada bloque (*bin* en la terminología de la implementación del recolector) + tiene ciertos indicadores asociados. Algunos de ellos pueden ser + manipulados (indirectamente) por el usuario utilizando las funciones + mencionadas arriba. + + El parámetro ``mask`` debe ser una máscara de bits que puede estar + compuesta por la conjunción de los siguientes valores: + + *FINALIZE* + El objeto almacenado en el bloque tiene un destructor (indicador + *finals*). + + *NO_SCAN* + El objeto almacenado en el bloque no contiene punteros (indicador + *noscan*). + + *NO_MOVE* + El objeto almacenado en el bloque no debe ser movido [#dgcmove]_. + +.. [#dgcmove] Si bien el recolector actual no tiene la capacidad de mover + objetos, la interfaz del recolector hacer que sea posible una + implementación que lo haga, ya que a través de este indicador se pueden + fijar objetos apuntados desde algún segmento no conservativo (objeto + *pinned*). + +Búsquedas + *findPool(p)* + Busca el *pool* al que pertenece el objeto apuntado por ``p``. + + *findBase(p)* + Busca la dirección base (el inicio) del bloque apuntado por ``p`` + (``find_block()`` según la sección :ref:`dgc_algo_mark`). + + *findSize(p)* + Busca el tamaño del bloque apuntado por ``p``. + + *getInfo(p)* + Obtiene información sobre el bloque apuntado por ``p``. Dicha + información se retorna en una estructura ``BlkInfo`` que contiene los + siguientes atributos: ``base`` (dirección del inicio del bloque), + ``size`` (tamaño del bloque) y ``attr`` (atributos o indicadores del + bloque, los que se pueden obtener con ``getBits()``). + + *findBin(size)* + Calcula el tamaño de bloque más pequeño que pueda contener un objeto de + tamaño ``size`` (``find_block_size()`` según lo visto en + :ref:`dgc_algo_alloc`). + +Asignación de memoria + *reserve(size)* + Reserva un nuevo *pool* de al menos ``size`` bytes. El algoritmo nunca + crea un *pool* con menos de 256 páginas (es decir, 1 MiB). + + *minimize()* + Minimiza el uso de la memoria retornando *pools* sin páginas usadas al + sistema operativo. + + *newPool(n)* + Reserva un nuevo *pool* con al menos ``n`` páginas. Junto con + ``Pool.initialize()`` es análoga a ``new_pool()``, solo que esta función + siempre incrementa el número de páginas a, al menos, 256 páginas (es + decir, los *pools* son siempre mayores a 1 MiB). Si la cantidad de + páginas pedidas supera 256, se incrementa el número de páginas en un 50% + como para que sirva para futuras asignaciones también. Además a medida + que la cantidad de *pools* crece, también trata de obtener cada vez más + memoria. Si ya había un *pool*, el 2do tendrá como mínimo 2 MiB, el 3ro + 3 MiB y así sucesivamente hasta 8 MiB. A partir de ahí siempre crea + *pools* de 8 MiB o la cantidad pedida, si ésta es mayor. + + *Pool.initialize(n_pages)* + Inicializa un nuevo *pool* de memoria. Junto con ``newPool()`` es + análoga a ``new_pool()``. Mientras ``newPool()`` es la encargada de + calcular la cantidad de páginas y crear el objeto *pool*, esta función + es la que pide la memoria al sistema operativo. Además inicializa los + conjuntos de bits: ``mark``, ``scan``, ``freebits``, ``noscan``. + ``finals`` se inicializa de forma perezosa, cuando se intenta asignar el + atributo ``FINALIZE`` a un bloque, se inicializa el conjunto de bits + ``finals`` de todo el *pool*. + + *allocPage(bin)* + Asigna a una página libre el tamaño de bloque ``bin`` y enlaza los + nuevos bloques libres a la lista de libres correspondiente (análogo + a ``assign_page()``). + + *allocPages(n)* + Busca ``n`` cantidad de páginas consecutivas libres (análoga + a ``find_pages(n)``). + + *malloc(size, bits)* + Asigna memoria para un objeto de tamaño ``size`` bytes. Análoga al + algoritmo ``new(size, attr)`` presentado, excepto que introduce además + un caché para no recalcular el tamaño de bloque necesario si se realizan + múltiples asignaciones consecutivas de objetos del mismo tamaño y que la + asignación de objetos pequeños no está separada en una función aparte. + + *bigAlloc(size)* + Asigna un objeto grande (análogo a ``new_big()``). La implementación es + mucho más compleja que la presentada en ``new_big()``, pero la semántica + es la misma. La única diferencia es que esta función aprovecha que + ``fullcollectshell()`` / ``fullcollect()`` retornan la cantidad de + páginas liberadas en la recolección por lo que puede optimizar levemente + el caso en que no se liberaron suficientes páginas para asignar el + objeto grande y pasar directamente a crear un nuevo *pool*. + + *free(p)* + Libera la memoria apuntada por ``p`` (análoga a ``delete()`` de la + sección anterior). + + Recordar que la ``pooltable`` siempre se mantiene ordenada según la + dirección de la primera página. + +Recolección + *mark(pbot, ptop)* + Marca un rango de memoria. Este método es análogo al ``mark_range()`` + presentado en la sección :ref:`dgc_algo_mark`. + + *fullcollectshell()* + Guarda los registros del procesador asignado al hilo actual en su + *stack* y llama a ``fullcollect()``. El resto de los hilos son pausados + y sus registros apilados por la función del *runtime* + ``thread_suspendAll()`` (y restablecidos y reiniciados por + ``thread_resumeAll()``. + + *fullcollect(stackTop)* + Realiza la recolección de basura. Es análoga a ``collect()`` pero es + considerablemente menos modular, todos los pasos se hacen directamente + en esta función: marcado del *root set*, marcado iterativo del *heap*, + barrido y reconstrucción de la lista de libres. Además devuelve la + cantidad de páginas que se liberaron en la recolección, lo que permite + optimizar levemente la función ``bigAlloc()``. + + +Finalización +^^^^^^^^^^^^ +El recolector actual, por omisión, solamente efectúa una recolección al +finalizar. Por lo tanto, no se ejecutan los destructores de todos aquellos +objetos que son alcanzables desde el *root set* en ese momento. Existe la +opción de no realizar una recolección al finalizar el recolector, pero no de +finalizar *todos* los objetos (alcanzables o no desde el *root set*). Si bien +la especificación de D_ permite este comportamiento (de hecho la +especificación de D_ es tan vaga que permite un recolector que no llame jamás +a ningún destructor), para el usuario puede ser una garantía muy débil +y proveer finalización asegurada puede ser muy deseable. + + +.. _dgc_committed: + +Memoria *encomendada* +^^^^^^^^^^^^^^^^^^^^^ +El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada* +(*committed* en inglés) y *no-encomendada*. Esto se debe a que originalmente +el compilador de D_ DMD_ solo funcionaba en Microsoft Windows y este sistema +operativo puede asignar memoria en dos niveles. En principio se puede asignar +al proceso un espacio de memoria (*address space*) pero sin asignarle la +memoria virtual correspondiente. En un paso posterior se puede *encomendar* la +memoria (es decir, asignar realmente la memoria virtual). + +Para aprovechar esta característica el recolector diferencia estos dos +niveles. Sin embargo, esta diferenciación introduce una gran complejidad (que +se omitió en las secciones anteriores para facilitar la comprensión), +y convierte lo que es una ventaja en un sistema operativo en una desventaja +para todos los demás (ya que los cálculos extra se realizan pero sin ningún +sentido). De hecho hay sistemas operativos, como Linux_, que realizan este +trabajo automáticamente (la memoria no es asignada realmente al programa hasta +que el programa no haga uso de ella; a esta capacidad se la denomina +*overcommit*). + +Como se vio en la figura :vref:`fig:dgc-pool`, las páginas de un *pool* se +dividen en *committed* y *uncommitted*. Siempre que el recolector recorre un +*pool* en busca de una página o bloque, lo hace hasta la memoria *committed*, +porque la *uncommitted* es como si jamás se hubiera pedido al sistema +operativo a efectos prácticos. Además, al buscar páginas libres, si no se +encuentran entre las *encomendadas* se intenta primero *encomendar* páginas +nuevas antes de crear un nuevo *pool*. + + +Sincronización +^^^^^^^^^^^^^^ +Si bien el recolector no es paralelo ni concurrente (ver :ref:`gc_art`), +soporta múltiples *mutator*\ s. La forma de implementarlo es la más simple. +Todas las operaciones sobre el recolector que se llaman externamente están +sincronizadas utilizando un *lock* global (excepto cuando hay un solo hilo +*mutator*, en cuyo caso se omite la sincronización). Esto afecta también a la +asignación de memoria y cualquier otro servicio provisto por el recolector. + + + +.. _dgc_good: + +Características destacadas ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -.. Acá diría por qué hay que reescribirlo para usar lo que está +Si bien el recolector en términos generales no se aleja mucho de un +:ref:`marcado y barrido clásico `, tiene algunas mejoras por +sobre el algoritmo más básicos que vale la pena destacar: + + +Organización del *heap* +^^^^^^^^^^^^^^^^^^^^^^^ +El *heap* está organizado de una forma que, si bien no emplea las técnicas más +modernas que pueden observarse en el estado del arte (como :ref:`regiones +`), es relativamente sofisticada. El esquema de *pools* +y bloques permite disminuir considerablemente los problemas de *fragmentación* +de memoria y evita búsquedas de *huecos* que pueden ser costosas (como +*best-fit* [#dgcbestfit]_) o desperdiciar mucho espacio (como *first-fit* +[#dgcfirstfit]_), logrando un buen equilibrio entre velocidad y espacio +desperdiciado. + +.. [#dgcbestfit] Las búsquedas de tipo *best-fit* son aquellas donde se busca + el *hueco* en el *heap* (es decir, una región contínua de memoria + libre) que mejor se ajuste al tamaño del objeto a asignar. Es decir, el + *hueco* más pequeño lo suficientemente grande como para almacenarlo. + +.. [#dgcfirstfit] Las búsquedas de tipo *first-fit* son aquellas donde se busca + el primer *hueco* en el *heap* (es decir, una región contínua de memoria + libre) que sea lo suficientemente grande como para almacenar el objeto + a asignar. + + +Fase de marcado iterativa +^^^^^^^^^^^^^^^^^^^^^^^^^ +A diferencia del algoritmo clásico recursivo, el algoritmo del recolector +actual es iterativo. El algoritmo recursivo tiene un problema fundamental: se +puede llegar a un desbordamiento de pila (o *stack overflow*). La cantidad de +recursiones necesarias es, en el peor caso, :math:`O(|Live \thickspace set|)` +(por ejemplo, si todas las celdas del *heap* formaran una lista simplemente +enlazada). Hay muchas técnicas para lidiar con este problema, algunas que +podrían aplicarse a D_ y otras que no (como *pointer reversal*) [JOLI96]_. El +recolector actual, sin embargo, cambia complejidad en espacio por complejidad +en tiempo, utilizando un algoritmo iterativo que es constante (:math:`O(1)`) +en espacio, pero que requiere varias pasada sobre el *heap* en vez de una (la +cantidad de pasadas en el peor caso es :math:`O(|Live \thickspace set|)`, al +igual que la profundidad del algoritmo recursivo, pero cada pasada se realiza +sobre todo el *heap*). + + +Conjuntos de bits para indicadores +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +El algoritmo clásico propone almacenar en la propia celda la marca (para la +fase de marcado) y otros indicadores. El algoritmo del recolector actual +utiliza conjuntos de bits. Esto trae dos ventajas principales: + +* Permite minimizar el espacio requerido, ya que de otra forma en general se + desperdicia una palabra entera como cabecera de celda para guardar este tipo + de información. + +* Mejora la localidad de referencia, ya que los indicadores se escriben de + forma muy compacta y en una región de memoria contigua que generalmente + puede entrar en el cache o en pocas páginas de memoria acelerando + considerablemente la fase de marcado. + + +.. _dgc_debug: + +Herramientas para depuración +^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +El recolector provee algunas opciones para simplificar el diagnóstico +y depuración de problemas, tanto del mismo recolector como del programa del +usuario. + +Las opciones más importantes son: + + +``MEMSTOMP`` + Su función es escribir un patrón determinado de bits en todos los bytes de + un bloque de memoria según se haya: + + * Pedido un bloque menor a una página (``0xF0``). + * Pedido un bloque mayor a una página (``0xF1``). + * Dejado de usar debido a un pedido de achicamiento de un bloque + (``0xF2``). + * Pedido más páginas debido a un pedido de agrandamiento de un bloque + (``0xF0``). + * Liberado intencionalmente por el usuario (``0xF2``). + * Barrido (``0xF3``). + + Esto permite al diagnosticar un problema saber, por ejemplo, si un + determinado área de memoria fue recolectada recientemente, o liberada por + el usuario, o recién adquirida, etc. con tan solo ver si un patrón de bits + determinado está presente. Por supuesto puede existir *falsos positivos* + pero su probabilidad es lo suficientemente baja como para que sea útil en + la práctica. + +``SENTINEL`` + Su función detectar errores producidos por escribir más allá (o antes) del + área de memoria solicitada. Está implementado reservando un poco más de + memoria de la que pide el usuario y devolviendo un puntero a un bloque + ubicado dentro del bloque real reservado (en vez de al inicio). Escribiendo + un patrón de bits en los extremos del bloque real (ver figura + :vref:`fig:sentinel`) se puede verificar, en distintas situaciones (como + por ejemplo al barrer el bloque), que esas guardas con los patrones de bits + estén intactas (en caso contrario se ha escrito por fuera de los límites + del bloque solicitado). Esto permite detectar de forma temprana errores + tanto en el recolector como en el programa del usuario. + + .. flt:: fig:sentinel + + Esquema de un bloque cuando está activada la opción ``SENTINEL`` + + .. aafig:: + :textual: + + | | | | | + +-- Palabra ---+-- Palabra ---+-- Tamaño bloque de usuario --+- Byte -+ + | | | | | + + +--------------+--------------+------------------------------+--------+ + | "Tamaño del" | Pre | | Post | + | "bloque de" | | Bloque de usuario | | + | "usuario" | 0xF4F4F4F4 | | 0xF5 | + +--------------+--------------+------------------------------+--------+ + A + | + Puntero devuleto ---/ -TODO +Ambas opciones son seleccionables sólo en tiempo de compilación del +recolector, por lo que su utilidad real, al menos para el usuario, se ve +severamente reducida. +.. _dgc_bad: Problemas y limitaciones ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -TODO +A continuación se presentan los principales problemas encontrados en la +implementación actual del recolector de basura de D_. Estos problemas surgen +principalmente de la observación del código y de aproximadamente tres años de +participación y observación del grupo de noticias, de donde se obtuvieron los +principales problemas percibidos por la comunidad que utiliza el lenguaje. + + +.. _dgc_bad_code: + +Complejidad del código y documentación +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +El análisis del código fue muy complicado debido a la falta de documentación +y desorganización del código. Además se nota que el recolector ha sido escrito +en una fase muy temprana y que a ido evolucionando a partir de ello de forma +descuidada y sin ser rescrito nunca para aprovechar las nuevas características +que el lenguaje fue incorporando (por ejemplo *templates*). + +Estos dos problemas (código complicado y falta de documentación) producen un +efecto de círculo vicioso, porque provocan que sea complejo entender el +recolector actual y en consecuencia sea muy complicado escribir documentación +o mejorarlo. Esto a su vez provoca que, al no disponer de una implementación +de referencia sencilla, sea muy difícil implementar un recolector nuevo. + +.. highlight:: d + +Este es, probablemente, la raíz de todos los demás problemas del recolector +actual. Para ilustrar la dimensión del problema se presenta la implementación +real de la función ``bigAlloc()``:: + + /** + * Allocate a chunk of memory that is larger than a page. + * Return null if out of memory. + */ + void *bigAlloc(size_t size) + { + Pool* pool; + size_t npages; + size_t n; + size_t pn; + size_t freedpages; + void* p; + int state; + + npages = (size + PAGESIZE - 1) / PAGESIZE; + + for (state = 0; ; ) + { + // This code could use some refinement when repeatedly + // allocating very large arrays. + + for (n = 0; n < npools; n++) + { + pool = pooltable[n]; + pn = pool.allocPages(npages); + if (pn != OPFAIL) + goto L1; + } + + // Failed + switch (state) + { + case 0: + if (disabled) + { state = 1; + continue; + } + // Try collecting + freedpages = fullcollectshell(); + if (freedpages >= npools * ((POOLSIZE / PAGESIZE) / 4)) + { state = 1; + continue; + } + // Release empty pools to prevent bloat + minimize(); + // Allocate new pool + pool = newPool(npages); + if (!pool) + { state = 2; + continue; + } + pn = pool.allocPages(npages); + assert(pn != OPFAIL); + goto L1; + case 1: + // Release empty pools to prevent bloat + minimize(); + // Allocate new pool + pool = newPool(npages); + if (!pool) + goto Lnomemory; + pn = pool.allocPages(npages); + assert(pn != OPFAIL); + goto L1; + case 2: + goto Lnomemory; + default: + assert(false); + } + } + + L1: + pool.pagetable[pn] = B_PAGE; + if (npages > 1) + cstring.memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1); + p = pool.baseAddr + pn * PAGESIZE; + cstring.memset(cast(char *)p + size, 0, npages * PAGESIZE - size); + debug (MEMSTOMP) cstring.memset(p, 0xF1, size); + //debug(PRINTF) printf("\tp = %x\n", p); + return p; + + Lnomemory: + return null; // let mallocNoSync handle the error + } + +Se recuerda que la semántica de dicha función es la misma que la de la función +``new_big()`` presentada en :ref:`dgc_algo_alloc`. + +Además, como se comentó en la sección anterior, los algoritmos en la +implementación real son considerablemente menos modulares que los presentados +en la sección :ref:`dgc_algo`. Por ejemplo, la función ``fullcollect()`` tiene +300 líneas de código fuente. + + +Memoria *encomendada* +^^^^^^^^^^^^^^^^^^^^^ +Como se comentó en la sección anterior, diferenciar entre memoria +*encomendada* de memoria *no-encomendada* es complejo y levemente costoso (en +particular para sistemas operativos que no hacen esta distinción, al menos +explícitamente, donde no hay ningún beneficio en realizar esta distinción). + +Incluso para Microsoft Windows, la ventaja de realizar esta distinción debería +ser comprobada. + + +Precisión +^^^^^^^^^ +Este fue históricamente uno de los problemas principales del recolector de D_ +[NGD46407]_ [NGD35364]_. Sin embargo, desde que, en la versión 1.001, se ha +incorporado la capacidad de marcar un bloque como de datos puros (no contiene +punteros, el atributo ``NO_SCAN``) [NGA6842]_, la gravedad de esos problemas ha +disminuido considerablemente, aunque siguieron reportándose problemas más +esporádicamente [NGD54084]_ [NGL13744]_. + +De todas maneras queda mucho lugar para mejoras, y es un tema recurrente en el +grupo de noticias de D_ y se han discutido formas de poder hacer que, al menos +el *heap* sea preciso [NGD44607]_ [NGD29291]_. Además se mostró un interés +general por tener un recolector más preciso [NGD87831]_, pero no han habido +avances al respecto hasta hace muy poco tiempo. + +Otra forma de minimizar los efectos de la falta de precisión que se ha +sugerido reiteradamente en el grupo es teniendo la +posibilidad de indicar cuando no pueden haber punteros interiores a un bloque +[NGD89394]_ [NGD71869]_. Esto puede ser de gran utilidad para objetos grandes +y en particular para mejorar la implementación de de arreglos asociativos. + + +Referencias débiles +^^^^^^^^^^^^^^^^^^^ +Si bien el recolector de Tango_ tiene un soporte limitado de *referencias +débiles* [#dgcweakref]_, el de Phobos_ no dispone de ningún soporte (por lo +tanto no está contemplado oficialmente el lenguaje). Sin embargo hay una +demanda apreciable [NGD86840]_ [NGD13301]_ [NGL8264]_ [NGD69761]_ [NGD74624]_ +[NGD88065]_. + +.. [#dgcweakref] Una referencia débil (o *weak reference* en inglés) es + aquella que que no protege al objeto referenciado de ser reciclado por el + recolector. + +Para cubrir esta demanda, se han implementado soluciones como biblioteca para +suplir la inexistencia de una implementación oficial [NGA9103]_ (la +implementación de Tango_ es otro ejemplo). + +Sin embargo éstas son en general poco robustas, extremadamente dependientes de +la implementación del recolector y, en general, presentan problemas muy +sutiles [NGD88065]_. Por esta razón se ha discutido la posibilidad de incluir +la implementación de *referencias débiles* como parte del lenguaje +[NGD88559]_. + + +Concurrencia +^^^^^^^^^^^^ +El soporte actual de concurrencia, en todos sus aspectos, es muy primitivo. El +recolector apenas soporta múltiples *mutators* pero con un nivel de +sincronización excesivo. + +Se ha sugerido en el pasado el uso de *pools* y listas de libres específicos +de hilos, de manera de disminuir la contención, al menos para la asignación de +memoria [NGD75952]_ [NGD87831]_. + +Además se ha mostrado un interés por tener un nivel de concurrencia aún mayor +en el recolector, para aumentar la eficiencia en ambientes *multi-core* en +general pero en particular para evitar grandes pausas en programas con +requerimientos de tiempo real, históricamente una de las principales críticas +al lenguaje [NGD87831]_ [NGL3937]_ [NGD22968]_ [NGA15246]_ [NGD5622]_ +[NGD2547]_ [NGD18354]_. + + +Finalización +^^^^^^^^^^^^ +El recolector actual no garantiza la finalización de objetos. En particular +los objetos no son finalizados (es decir, no se llama a sus destructores) si +aún alcanzables desde el *root set* cuando el programa termina. Cabe destacar +que esto puede darse porque hay una referencia real desde el *root set* (en +cuyo caso queda bajo el control del usuario) pero también, dado que el *root +set* se visita de forma conservativa, se puede deber a un *falso positivo*, en +cuyo caso la omisión de la finalización queda por completo fuera del control +del usuario (y lo que es aún peor, el usuario no puede ser siquiera notificado +de esta anomalía). + +Si bien la especificación de D_ no requiere esta capacidad, no hay mayores +problemas para implementar un recolector que dé este tipo de garantías +[NGD88298]_. + +Además los objetos pueden ser finalizados tanto determinísticamente +(utilizando ``delete`` o ``scope``; ver secciones :ref:`d_low_level` +y :ref:`d_dbc`) como no determinísticamente (cuando son finalizados por el +recolector). En el primer caso se puede, por ejemplo, acceder sus atributos +u otra memoria que se conozca *viva*, mientras que en el segundo no. Sin +embargo un destructor no puede hacer uso de esta distinción, haciendo que la +finalización determinística tenga a fines prácticos las mismas restricciones +que la finalización no determinística. Es por esto que se ha sugerido permitir +al destructor distinguir estos dos tipos de finalización [NGD89302]_. + + +Eficiencia +^^^^^^^^^^ +El rendimiento en general del recolector es una de las críticas frecuentes. Si +bien hay muchos problemas que han sido resueltos, en especial por la inclusión +de un mínimo grado de precisión en la versión 1.001, en la actualidad se +siguen encontrando en el grupo de noticias críticas respecto a esto +[NGD43991]_ [NGD67673]_ [NGD63541]_ [NGD90977]_. + +La principal causa del bajo rendimiento del recolector actual es, +probablemente, lo simple de su algoritmo principal de recolección. Más allá de +una organización del *heap* moderadamente apropiada y de utilizar conjuntos de +bits para la fase de marcado, el resto del algoritmo es casi la versión más +básica de marcado y barrido. Hay mucho lugar para mejoras en este sentido. + + +Configurabilidad +^^^^^^^^^^^^^^^^ +Si bien el recolector actual tiene algunas características configurables, +todas son seleccionables sólo en tiempo de compilación del recolector (no del +programa del usuario), como por ejemplo las opciones descriptas en +:ref:`dgc_debug`. Por lo tanto, a nivel práctico, es como si no tuviera +posibilidad alguna de ser configurado por el usuario, ya que no es parte del +ciclo de desarrollo normal el recompilar el recolector o *runtime* de un +lenguaje. + +Dado que es imposible que un recolector sea óptimo para todo tipo de +programas, es muy deseable permitir una configuración de parámetros del +recolector que permitan al usuario ajustarlos a las necesidades particulares +de sus aplicaciones. + + +.. _dgc_bad_ocup: + +Factor de ocupación del *heap* +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Otro problema potencialmente importante del recolector actual es que no se +tiene ningún cuidado con respecto a que, luego de una recolección, se haya +recuperado una buena parte del *heap*. Por lo tanto, en casos extremos, el +recolector tiene que hacer una recolección por cada petición de memoria, lo +que es extremadamente ineficiente. + +Para evitar esto, habría que usar algún esquema para evaluar cuando una +recolección no fue lo suficientemente *exitosa* y en ese caso pedir más +memoria al sistema operativo. + + +Detalles +^^^^^^^^ +Finalmente hay varios detalles en la implementación actual que podrían +mejorarse: + +Listas de libres + Hay 12 listas de libres, como para guardar bloques de tamaño de ``B_16`` + a ``B_2048``, ``B_PAGE``, ``B_PAGEPLUS``, ``B_UNCOMMITTED`` y ``B_FREE``; + sin embargo solo tienen sentido los bloques de tamaño ``B_16`` + a ``B_2048``, por lo que 4 de esas listas no se utilizan. + +Conjuntos de bits para indicadores + Los indicadores para la fase de marcado y otras propiedades de un bloque + son almacenados en conjuntos de bits que almacenan los indicadores de todos + los bloques de un *pool*. Si bien se ha mencionado esto como una ventaja, + hay lugar todavía como para algunas mejoras. Como un *pool* tiene páginas + con distintos tamaños de bloque, se reserva una cantidad de bits igual a la + mayor cantidad posible de bloques que puede haber en el *pool*; es decir, + se reserva 1 bit por cada 16 bytes del *pool*. Para un *pool* de 1 MiB + (tamaño mínimo), teniendo en cuenta que se utilizan 5 conjuntos de bits + (``mark``, ``scan``, ``finals``, ``freebits`` y ``noscan``), se utilizan 40 + KiB de memoria para conjuntos de bits (un 4% de *desperdicio* si, por + ejemplo, ese *pool* estuviera destinado por completo a albergar un solo + objeto grande; lo que equivaldría al 2560 objetos de 16 bytes + desperdiciados en bits inutilizados). + +Repetición de código + Hay algunos fragmentos de código repetidos innecesariamente. Por ejemplo en + varios lugares se utilizan arreglos de tamaño variable que se implementan + repetidas veces (en general como un puntero al inicio del arreglo más el + tamaño actual del arreglo más el tamaño de la memoria total asignada + actualmente). Esto es propenso a errores y difícil de mantener. + +Uso de señales + El recolector actual utiliza las señales del sistema operativo ``SIGUSR1`` + y ``SIGUSR2`` para pausar y reanudar los hilos respectivamente. Esto + puede traer inconvenientes a usuarios que desean utilizar estas + señales en sus programas (o peor aún, si interactúan con bibliotecas + de C que hacen uso de estas señales) [NGD5821]_. + +Marcado iterativo + Si bien esto se mencionó como algo bueno del recolector actual, es un + compromiso entre tiempo y espacio, y puede ser interesante analizar otros + métodos para evitar la recursión que no requieran tantas pasadas sobre el + *heap*. + + + +.. _dgc_via: + +Análisis de viabilidad +---------------------------------------------------------------------------- + +Ya conociendo el lenguaje de programación D_ (con sus necesidades +particulares), el estado del arte en recolección de basura y el recolector +actual de D_ es posible evaluar la viabilidad de los distintos algoritmos +vistos en el capítulo :ref:`gc`. Se recuerda que dentro del análisis de +viabilidad de considera de gran importancia la viabilidad social y política de +la mejora, es decir, se presta particular atención en encontrar una mejora que +tenga una buena probabilidad de ser aceptada por la comunidad de D_. + + +.. _dgc_via_classic: + +Algoritmos clásicos +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +En esta sección se presenta un análisis de los :ref:`algoritmos clásicos +`, de forma de poder analizar a grandes rasgos las principales +familias para ir determinando la dirección principal de la solución. + + +.. _dgc_via_rc: + +Conteo de referencias +^^^^^^^^^^^^^^^^^^^^^ +Ya se ha propuesto en el pasado la utilización de conteo de referencias en D_ +pero no se ha demostrado un interés real, más allá de soluciones en +bibliotecas [NGD38689]_. Las razones para no utilizar conteo de referencia son +más o menos las mismas que las desventajas mencionadas en la sección +:ref:`gc_rc` (en el capítulo :ref:`gc`), siendo la principal la incapacidad de +recolectar ciclos. Sin embargo hay otras razones importantes. + +Una de ellas es la inter-operatividad con C. El utilizar un contador de +referencias requiere la manipulación del contador por parte del código C con +el que se interactúe. Si bien este problema ya está presente si código +C guarda en su *headp* un puntero a un objeto almacenado en el *heap* del +recolector de D_, esto es poco común. Sin embargo, mientras que una función de +C se está ejecutando, es extremadamente común que pueda almacenar en el +*stack* una referencia a un objeto de D_ y en ese caso el recolector actual +puede manejarlo (mientras la función de C esté corriendo en un hilo creado por +D_). Sin embargo al usar un conteo de referencias esto es más problemático, ya +que no se mantiene la invariante del algoritmo si no son actualizados siempre +los contadores. + +Otro problema es que al liberarse una celda, existe la posibilidad de tener +que liberar todo el sub-grafo conectado a ésta. Cuando este sub-grafo es +grande, se puede observar una gran pausa. + +Si bien estas razones son suficientes como para considerar que el conteo de +referencias no es un algoritmo que sea viable en D_, hay muchas técnicas +y optimizaciones para minimizarlas (como liberación perezosa, conteo de +referencias pospuesto, etc. [JOLI96]_). Sin embargo hay otra razón importante +que descarta esta familia de algoritmos ya que todas las variaciones de conteo +de referencias implican, en mayor o menor medida, el entrelazado del trabajo +del recolector con el del *mutator*. Si bien esta es una característica en +general muy deseable (porque hace que el recolector sea :ref:`incremental +`), en D_ no lo es porque tiene como requerimiento no hacer pagar el +precio de cosas que no se usan. En D_ debe ser posible no utilizar el +recolector de basura y, al no hacerlo, no tener ningún tipo de trabajo extra +asociado a éste. De usarse conteo de referencias esto no sería posible. + +Si bien este requerimiento puede ser discutible técnicamente, hay una gran +resistencia social y política ante cualquier tipo de recolector que imponga +una penalización de rendimiento a alguien que no quiera usarlo [NGD38689]_. +Además requiere un cambio complejo y profundo en el compilador, siendo éste +uno de los eslabones con mayor resistencia a introducir cambios. + +Por lo tanto se concluye que el conteo de referencias no es un algoritmo +viable para este trabajo. + + +.. _dgc_via_mark_sweep: + +Marcado y barrido +^^^^^^^^^^^^^^^^^ +El marcado y barrido es un algoritmo evidentemente viable debido a que es la +base del algoritmo del recolector de basura actual. + +En general en la comunidad de D_ no hay mayores críticas al marcado y barrido +en sí, si no más bien a problemas asociados a la implementación actual, +principalmente a las grandes pausas o la falta de :ref:`precisión +` [NGD54084]_ [NGL13744]_ [NGD44607]_ [NGD29291]_ [NGD87831]_ +[NGD87831]_ [NGL3937]_ [NGD22968]_ [NGA15246]_ [NGD5622]_ [NGD2547]_ +[NGD18354]_. + +Esta familia de algoritmos se adapta bien a los requerimientos principales de +D_ en cuanto a recolección de basura (ver :ref:`dgc_needs`), por ejemplo +permite recolectar de forma conservativa, no impone un *overhead* a menos que +se utilice el recolector, permite liberar memoria manualmente, se adapta de +forma simple para soportar punteros *interiores* y permite finalizar objetos +(con las limitaciones mencionadas en :ref:`dgc_prob_final`). + +Sin embargo muchas de las limitaciones del recolector actual (ver +:ref:`dgc_bad`), no son inherentes al marcado y barrido, por lo que aún +conservando la base del algoritmo, es posible realizar una cantidad de mejoras +considerable. + +Una de las principales mejoras que pueden realizarse es hacer al recolector +:ref:`concurrente ` y más :ref:`preciso `. Estas +dos mejoras solamente alcanzarían para mejorar de forma notable el tiempo de +pausa en las recolecciones y la cantidad de memoria retenida debido a *falsos +positivos*. + +Más adelante veremos detalles sobre algunos de estos aspectos y sobre algunos +algoritmos particulares que permiten hacer concurrente al recolector actual. + + +Copia de semi-espacio +^^^^^^^^^^^^^^^^^^^^^ +La copia de semi-espacio, al igual que cualquier otro tipo de recolector con +movimiento, requiere (en la mayoría de los casos) disponer de una +:ref:`precisión ` casi completa. Las celdas para las cuales hay +alguna referencia que no es precisa no pueden ser movidas, ya que al no estar +seguros que la referencia sea tal, ésta no puede ser actualizada con la +dirección de la nueva ubicación de la celda movida porque de no ser una +referencia se estarían alterando datos del usuario, corrompiéndolos. + +Es por esto que si el recolector no es mayormente preciso, las celdas que +pueden ser movidas son muy pocas y, por lo tanto, se pierden las principales +ventajas de esta familia de recolectores (como la capacidad de asignar nueva +memoria mediante *pointer bump allocation*). + +Este aumento de precisión, sin embargo, es bastante realizable. Es posible, en +teoría, hacer que al menos el *heap* sea preciso, aunque es discutible si en +la práctica es aceptable el *overhead* en espacio necesario para almacenar la +información del tipo de una celda. Esto se analiza en más detalle al evaluar +la recolección precisa en la siguiente sección. + +Si bien las principales herramientas para que sea viable un recolector por +copia de semi-espacio están disponibles en D_ (como la posibilidad de hacer +*pinning* the celdas o el potencial incremento de precisión), este lenguaje +nunca va a poder proveer precisión total, haciendo que no sea posible +implementar un recolector por copia de semi-espacio puro. Siempre habrá que +disponer un esquema híbrido para poder manejar las celdas que no puedan +moverse, incrementado mucho la complejidad del recolector. + +Si bien un esquema híbrido es algo técnicamente posible, nuevamente la +resistencia social a un cambio de esta envergadura es de importancia +suficiente como para inclinarse por una solución menos drástica. + + +.. _dgc_via_art: + +Principales categorías del estado del arte +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +En esta sección se realiza un análisis de la viabilidad de las principales +categorías de recolectores según se presentaron en la sección :ref:`gc_art`. + +Recolección directa / indirecta +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Como se ha visto al analizar el conteo de referencias, lo más apropiado para +D_ pareciera ser continuar con el esquema de recolección indirecta, de forma +tal de que el precio de la recolección solo deba ser pagado cuando el +*mutator* realmente necesita del recolector. Es por esto que no parece ser una +opción viable introducir recolección directa en este trabajo. + + +Recolección incremental +^^^^^^^^^^^^^^^^^^^^^^^ +La recolección incremental puede ser beneficiosa para D_, dado que puede +servir para disminuir el tiempo de pausa del recolector. Sin embargo, en +general es necesario instrumentar el *mutator* para reportar cambios en el +grafo del conectividad al recolector. Además puede contar con los mismos +problemas que la recolección directa, puede hacer que el usuario tenga que +pagar el precio de la recolección, incluso cuando no la necesita, si por cada +asignación el recolector realiza parte de una recolección que no fue +solicitada. + +Recolección concurrente / paralela / *stop-the-world* +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +El recolector actual es *stop-the-world*, sin embargo esta es una de las +principales críticas que tiene. El recolector se podría ver beneficiado de +recolección paralela, tanto para realizar la recolección más velozmente en +ambientes *multi-core*, como para disminuir el tiempo de pausa, un factor muy +importante para programas que necesiten tener baja latencia, como programas +*real-time*. +En general los recolectores concurrentes necesitan también instrumentar el +*mutator* para reportar cambios en el grafo de conectividad al recolector, +como sucede con la recolección directa o incremental, sin embargo hay +algoritmos que no tienen este requerimiento, utilizando servicios del sistema +operativo para tener una *fotografía* de la memoria para que la fase de +marcado pueda realizarse sin perturbar al *mutator* ni requerir de su +cooperación [RODR97]_. Este tipo de algoritmos serían un buen candidato para +D_, dado que requiere pocos cambios y es transparente al *mutator*. +Recolección conservativa / precisa +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Si bien D_ puede proveer al recolector de basura información de tipos para los +objetos almacenados en el *heap*, todo recolector para D_ deberá soportar +cierto grado de recolección conservativa (ver :ref:`gc_conserv`), debido a las +siguientes razones: -Como se ha visto, D_ es un lenguaje de programación muy completo, -pero aún tiene algunos aspectos inconclusos. Su recolector de basura -está en un estado de evolución muy temprana. Se trata de un marcado y -barrido (*mark and sweep*) conservativo que, en ciertas circunstancias, -no se comporta como es debido, ya que revisa toda la memoria del programa -en busca de referencias a objetos en el *heap* (en vez de revisar sólo -las partes que almacenan punteros). Esto produce que, en ciertos casos, -por ejemplo al almacenar arreglos de número o *strings* en la pila, el -recolector de basura se encuentre con *falsos positivos*, pensando que -un área del *heap* está siendo utilizada cuando en realidad el puntero -que hacía referencia a ésta no era tal. Este efecto puede llevar a la -pérdida de memoria masiva, llegando al límite de que eventualmente -el sistema operativo tenga que matar al programa por falta de memoria -[DNG46407]_. Aún cuando el programa no tenga estos problemas de por sí, -por usar datos que no pueden ser confundidos con direcciones de memoria, -este problema podría ser explotado por ataques de seguridad, inyectando -valores que sí sean punteros válidos y provocando el efecto antes -mencionado que deriva en la terminación abrupta del programa [DNG35364]_. -Finalmente, a estos problemas se suman los problemas de *performance* -[DNG43991]_. +* Si bien D_ podría incorporar información de tipos para el *stack* + (utilizando, por ejemplo, la técnica de *shadow stack* [HEND02]_), para + poder interactuar con C/C++, el recolector debe poder interpretar los *stack + frames* [#dgcstackframe]_ de estos lenguajes, que no disponen de información + de tipos. -Es difícil que D_ pueda ser un lenguaje de programación exitoso si -no provee un recolector de basura eficiente y que realmente evite la -pérdida masiva de memoria. Por otro lado, D_ podría atraer a una base de -usuarios mucho más amplia, si la gama de estrategias de recolección es -más amplia, pudiendo lograr adaptarse a más casos de uso sin llegar al -límite de tener que caer en el manejo explícito de memoria y perder por -completo las ventajas de la recolección de basura (con la consecuencia -ya mencionada de que el manejo de memoria tenga que pasar a ser parte -de las interfaces y la complejidad que esto agrega al diseño -y uso- -de una biblioteca). +* Los registros del procesador tienen un problema similar, con la diferencia + de que el costo de implementar algo similar a *shadow stack* para los + registros sería impracticable, más allá de que exista la misma limitación + que con el *stack* para poder interactuar con C/C++. +* D_ soporta uniones (ver :ref:`d_low_level`). Para una unión es imposible + determinar si un campo es un puntero o no. Por ejemplo:: + union U { + size_t x; + void* p; + } -Soluciones Propuestas + Aquí el recolector no puede saber nunca si el valor almacenado será un + ``size_t`` o un ``void*``, por lo tanto deberá tratar **siempre** esa + palabra de forma conservativa (es decir, interpretarla como un *posible* + puntero). Este requerimiento puede ser relajado si el usuario proveyera + alguna forma de determinar que tipo está almacenando la unión en un + determinado momento. Sin embargo el costo de pedir al usuario este tipo de + restricción puede ser muy alto. -Para poder implementar un recolector de basura no conservativo es -necesario disponer de un soporte de reflexión (en tiempo de compilación -[DNG44607]_ y de ejecución [DNG29291]_) bastante completo . De otra forma -es imposible distinguir si un área de memoria de la pila es utilizada -como un puntero o como un simple conjunto de datos. D_ provee algún -grado de reflexión, pero muy limitado como para poder obtener este -tipo de información. Ya hay un plan para agregar mayores capacidades -de reflexibilidad [DNG6842]_, y un pequeño avance en este sentido en la -`versión 1.001`_, pero con algunos problemas [DNG6890]_ [DNG6893]_. +Durante el desarrollo de este trabajo se encontra un trabajo relacionado +avanzando en este sentido, que agrega precisión al marcado del *heap*. David +Simcha comienza explorando la posibilidad de agregar precisión parcial al +recolector, generando información sobre la ubicación de los punteros para cada +tipo [DBZ3463]_. Su trabajo se limita a una implementación a nivel biblioteca +de usuario y sobre `D 2.0`_. Desafortunadamente su trabajo pasa desapercibido +por un buen tiempo. -.. _`versión 1.001`: http://www.digitalmars.com/d/changelog.html#new1_001 +Sin embargo un tiempo después Vincent Lang (mejor conocido como *wm4* en la +comunidad de D_), retoma este trabajo, pero modificando el compilador DMD_ +y trabajando con `D 1.0`_ y Tango_. Es por esto que el aumento de precisión +parece ser un área fértil para este trabajo, en particular si se colabora con +el trabajo realizado por David y Vincent. -Se han propuesto otros métodos e implementaciones de recolector de basura, -por ejemplo colectores con movimiento (*moving collectors*) [DNG42557]_ -y conteo de referencias [DNG38689]_. Pero D_ es un lenguaje muy particular -en cuanto a la recolección de basura (al permitir :ref:d_low_level hay -muchas consideraciones a las que otros lenguajes no deben enfrentarse) y no -es sencillo pensar en otras implementaciones sin hacer modificaciones de -base al lenguaje. +.. [#dgcstackframe] Un *stack frame* (*marco de la pila* en castellano), + también conocido como *activation record* (o *registro de activación* en + castellano) es una estructura de datos dependiente de la arquitectura que + contiene información del estado de una función, incluyendo, por ejemplo, + sus variables locales, parámetros y dirección de retorno. +Recolección con movimiento de celdas +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Esta posibilidad ya se ha discutido al analizar la posibilidad de utilizar +recolección con copia de semi-espacios. El trabajo mencionado en la sub-sección +anterior agrega información suficiente como poder diferenciar que celdas se +pueden mover y cuales no, sin embargo queda como incógnita qué proporción de +celdas deben permanecer inmovilizadas como para evaluar si un cambio tan +grande puede rendir frutos o no. -Problemas para Implementar Colectores con Movimiento +A priori, pareciera que la relación cantidad y complejidad de cambios sobre +beneficios potenciales no fuera muy favorable a esta mejora. -El principal problema es la capacidad de D_ de manipular punteros y -otras estructuras de bajo nivel, como uniones. O incluso la capacidad -de interactuar con C. Al mover un objeto de un área de memoria a otro, -es necesario actualizar todos los punteros que apuntan a éste. En D_ -esta tarea no es trivial [DNG42564]_ +Lista de libres / *pointer bump allocation* +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Como consecuencia de los puntos anteriores, no es técnicamente posible +realizar *pointer bump allocation* pura en D_. Al haber objetos *pinned*, +siempre es necesario o bien contar con una lista de libres, o detectar +*huecos* en un esquema de *pointer bump allocation*. Es por esto que parece +ser más viable conservar el esquema de listas de libres. +Esta mejora también entra en la categoría de opciones viables pero cuya +complejidad no parece valer la pena dada la limitada utilidad que se espera +dadas las particulares características de D_ en cuanto a precisión de +información de tipos de *stack*, uniones, etc. -Problemas para Implementar Conteo de Referencias -Este tipo de recolectores reparten la carga de la recolección de forma -uniforme a lo largo (y a la par) de la ejecución del programa. El -problema principal para implementar este tipo de recolección es -la necesidad de soporte en el compilador (cada asignación debe ser -acompañada por el incremento/decremento de contadores de referencia), a -menos que se implemente en una biblioteca. Por otro lado, características -como el rebanado de arreglos (ver :ref:d_high_level) son -difíciles de proveer con el conteo de referencias, entre otros problemas -[DNG38704]_. +Recolección por particiones / generacional +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Una vez más la recolección por particiones, en particular la generacional, +requiere de la instrumentación del *mutator* para comunicar cambios en el +grafo de conectividad al recolector, por lo que es poco viable. Aunque existen +algoritmos que no necesitan este tipo de comunicación dado que está +garantizado que no existan conexiones entre celdas de las distintas +particiones, requiere grandes cambios en el compilador y realizar análisis +estático bastante complejo [HIRZ03]_. Además al ser D_ un lenguaje de bajo +nivel, es muy difícil garantizar que estas conexiones inter-particiones no +puedan existir realmente; y de hacerlo, podría ser demasiado restrictivo. .. include:: links.rst -.. vim: set ts=3 sts=3 sw=3 et tw=78 : +.. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :