]> git.llucax.com Git - z.facultad/75.00/informe.git/blobdiff - source/dgc.rst
Agregar Factor de ocupación del heap como problema del GC actual
[z.facultad/75.00/informe.git] / source / dgc.rst
index 929d48c46a30d2b09cf1cfffa15470958e277d22..d6d5878777e44a82271781d8acc25dae2d2ba676 100644 (file)
@@ -4,7 +4,7 @@
    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
+   ESTADO: TERMINADO, CORREGIDO
 
 
 .. _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 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 sencillas
+comparadas con el :ref:`estado del arte <gc_art>` 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 y finalmente se presenta una recompilación de los
+principales problemas que presenta.
 
-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.
+
+El control sobre 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:
+
+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:
+
+   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 el 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 este
+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, 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 un problema de redacción vaga y dadas las
+garantías que provee la implementación actual la comunidad de D_ cuenta con
+ellas porque además son deseables (y sencillas de implementar).
 
 
 
@@ -28,118 +174,1631 @@ TODO
 Recolector de basura actual de D
 ----------------------------------------------------------------------------
 
-TODO
+Como paso básico fundamental para poder mejorar el recolector de basura de D_,
+primero hay que entender la implementación actual, de forma de conocer sus
+puntos fuertes, problemas y limitaciones, de manera tal de poder analizar
+formas de mejorarlo.
+
+Como se mencionó en la sección :ref:`d_lang`, en D_ hay dos bibliotecas base
+para soportar el lenguaje (*runtimes*): Phobos_ y Tango_. La primera es la
+biblioteca estándar de D_, la segunda un proyecto más abierto y dinámico que
+surgió como alternativa a Phobos_ debido a que Phobos_ es muy 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.
+
+El recolector actual es un recolector :ref:`indirecto <gc_direct>`, :ref:`no
+incremental <gc_inc>` que realiza un :ref:`marcado y barrido <gc_mark_sweep>`
+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
+<gc_concurrent` mientras que la fase de barrido corre en paralelo con el
+*mutator*, excepto el hilo que disparó la recolección que es quien efectúa el
+barrido (además los hilos que intenten asignar nueva memoria o interactuar con
+el recolector de cualquier otra forma se bloquean hasta que la fase de barrido
+concluya). El marcado es casi totalmente :ref:`conservativo <gc_conserv>`; 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 <gc_part>`.
+
+Si bien el recolector es bastante básico, posee una :ref:`organización de
+memoria <dgc_org>` relativamente moderna (utiliza una :ref:`lista de libres
+<gc_free_list>` con un *two level allocator*) y algunas optimizaciones
+particulares para amortiguar casos patológicos.
 
 
+.. _dgc_org:
 
-Diseño
+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 <dgc_impl>`) 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).
+
+.. fig:: fig:dgc-org
+
+   Organización del *heap* del recolector de basura actual de D.
+
+   Organización del *heap*. En este ejemplo todos los *pools* tienen 2 páginas
+   excepto el *pool* 2 que tiene una sola.  El tamaño de bloque que almacena
+   cada página varía entre 64 bytes (página 0 del *pool* 2) hasta 4096 (ambas
+   páginas del *pool* N) que es una página completa.
+
+   .. aafig::
+      :scale: 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 estar asignada a contener bloques de un tamaño
+específico o puede estar libre. A su vez, cada bloque puede estar ocupado por
+una celda o estar libre. Los bloques libres de un tamaño específico (a
+excepción de aquellos bloques que ocupen una página entera) además forman
+parte de una :ref:`lista de libres <gc_free_list>` (ver figura
+:vref:`fig:dgc-free-list`). Esto permite asignar objetos relativamente
+pequeños de forma bastante eficiente.
+
+.. fig:: fig:dgc-free-list
+
+   Ejemplo de listas de libres.
+
+   .. digraph:: dgc_free_list
+
+      margin  = 0;
+      rankdir = LR;
+      ratio   = fill;
+      size    = "4.6,3.6";
+      node [ shape = record, width = 0, height = 0 ];
+
+      subgraph cluster_heap {
+         style = solid;
+         color = black;
+
+         free [ label = "Libres|<p16> 16|<p32> 32|<p64> 64|<p128> 128|<p256> 256|<p512> 512|<p1024> 1024|<p2048> 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 que la página está
+   disponible para albergar cualquier tamaño de bloque que sea necesario (pero
+   una vez que se le asignó un nuevo tamaño de bloque ya no puede ser cambiado
+   hasta que la página vuelva a liberarse por completo).
+
+``CONTINUATION``
+   indica que esta página es la continuación de un objeto grande (es decir,
+   que ocupa una o más páginas). Luego se presentan más detalles sobre objetos
+   grandes.
+
+Las páginas con esto tamaños de bloque especiales (conceptualmente) no
+contienen bloques.
+
+
+Atributos de bloque
+^^^^^^^^^^^^^^^^^^^
+Cada bloque tiene asociados varios atributos:
+
+*mark*
+   utilizado en la fase de :ref:`marcado <dgc_algo_mark>`, indica que un nodo
+   ya fue visitado (serían las celdas *negras* en la :ref:`abstracción
+   tricolor <gc_intro_tricolor>`).
+
+*scan*
+   utilizado también en la fase de :ref:`marcado <dgc_algo_mark>`, indica que
+   una celda visitada todavía tiene *hijas* sin marcar (serían las celdas
+   *grises* en la :ref:`abstracción tricolor <gc_intro_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 <dgc_algo_mark>` y :ref:`barrido <dgc_algo_sweep>` en el
+   :ref:`algoritmo actual <dgc_algo>` (las celdas con el atributo este
+   atributo son tomadas como *basura* aunque estén marcadas con *mark*).
+
+*final*
+   indica que el bloque contiene un objeto que tiene un destructor (que debe
+   ser llamado cuando la celda pasa de *viva* a *basura*).
+
+*noscan*
+   indica que el bloque contiene un objeto que no tiene punteros y por lo
+   tanto no debe ser marcado de forma conservativa (no tiene *hijas*).
+
+
+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.
 
-TODO
 
 
+.. _dgc_algo:
 
-Implementación
+Algoritmos del recolector
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-.. Acá diría por qué hay que reescribirlo para usar lo que está
+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 <gc_mark_sweep>`::
+
+   function collect() is
+      mark_phase()
+      sweep_phase()
+
+
+.. _dgc_algo_mark:
+
+Fase de marcado
+^^^^^^^^^^^^^^^
+Esta fase consiste de varios pasos, que pueden resumirse en el siguiente
+algoritmo::
+
+   function mark_phase() is
+      global more_to_scan = false
+      stop_the_world()
+      clear_mark_scan_bits()
+      mark_free_lists()
+      mark_static_data()
+      push_registers_into_stack()
+      mark_stacks()
+      mark_user_roots()
+      mark_heap()
+      start_the_world()
+
+La variable **global** ``more_to_scan`` indica al algoritmo iterativo cuando
+debe finalizar: la función ``mark_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()`` sencillamente
+pausan y reanudan todos los hilos respectivamente::
+
+   function stop_the_world() is
+      foreach thread in threads
+         thread.pause()
+
+   function start_the_world() is
+      foreach thread in threads
+         thread.resume()
+
+La función ``clear_mark_scan_bits()`` se encarga de 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 heap
+         foreach block in free_list
+            block.mark = true
+            block.free = true
+
+Notar que los bloques libres quedan entonces marcados aunque sean *basura* por
+definición. Para evitar que en la etapa de barrido se tomen estos bloques como
+celdas vivas, a todos los bloques en la lista de libres también se los marca
+con el bit *free*, así el barrido puede tomar como *basura* estos bloques
+aunque estén marcados.
+
+El *root set* está compuesto por el área de memoria estática (variables
+globales), los *stacks* de todos los hilos y los registros del procesador.
+Primero se marca el área de memoria estática de manera :ref:`conservativa
+<gc_conserv>` (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() is
+      foreach register in registers
+         push(register)
+
+Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos
+los threads para terminar de marcar el *root set*::
+
+   function mark_stacks() is
+      foreach thread in threads
+         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 <gc_intro_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.bloc_size < PAGE
+               foreach block in page
+                  block_start = cast(byte*) block
+                  block_end = block_start + page.block_size
+                  if block_start <= pointer < block_end
+                     return [pool, page, block_start]
+      return [null, null, null]
+
+Cabe destacar que la función ``find_block()`` devuelve el *pool*, la página
+y el comienzo del bloque al que apunta el puntero, es decir, soporta punteros
+*interiores*.
+
+
+.. _dgc_algo_sweep:
+
+Fase de barrido
+^^^^^^^^^^^^^^^
+Esta fase es considerablemente más sencilla que el marcado; el algoritmo puede
+dividirse en dos pasos básicos::
+
+   function sweep_phase() is
+      sweep()
+      rebuild_free_lists()
+
+El barrido se realiza con una pasada por sobre todo el *heap* 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 = cast(byte*) page + PAGE_SIZE
+         page.block_size = FREE
+      while page.block_size is CONTINUATION and page < pool_end
+
+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 como libre, se procede
+a reconstruir las listas de libres. En el proceso 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 heap
+         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 null
+         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 <dgc_algo_collect>` 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
+
+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*::
+
+      funciones 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)
+         return pool
+
+Se recuerda que la función ``alloc()`` es un :ref:`servicio
+<gc_intro_services>` 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 página, 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
+      for pool in heap
+         all_free = true
+         for 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:
 
-TODO
+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 <dgc_algo_sweep>`. 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á implementado realmente el recolector
+actual. Con los conceptos e ideas principales del 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
+      <gc_intro_tricolor>`). Es análoga a la variable ``more_to_scan``
+      presentada en :ref:`dgc_algo_mark`.
+
+   *inited*
+      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).
+
+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.
+
+Optimizaciones
+   *p_cache*, *size_cache*
+      obtener el tamaño de un bloque dado un puntero 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 el último calculado en estas variables a modo de
+      *caché*.
+
+   *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 ``malloc()``, ``realloc()`` y ``free()`` directamente.
+
+
+La estructura ``Pool`` está compuesta por los siguientes atributos (ver figura
+:vref:`fig:dgc-pool`):
+
+*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*
+   conjunto 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``.
+
+.. fig:: 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)" |
+                +--------+--------+-----+--------+-----+-------------------+
+
+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 que lo 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 ``Lista``, 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.
+
+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 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 en el *stack* y llama a ``fullcollect()``. El
+      algoritmo presentado en :ref:`dgc_algo_mark` es simbólico, ya que si los
+      registros se apilaran en el *stack* dentro de otra función, al salir de
+      esta se volverían a des-apilar, por lo tanto debe ser hecho en la misma
+      función ``collect()`` o en una función que luego la llame (como en este
+      caso).
+
+   *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.
+
+
+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. Por un lado puede asignar al
+proceso un espacio de memoria (*address space*) pero sin asignarle la memoria
+correspondiente. En un paso posterior se puede *encomendar* la memoria (es
+decir, asignar realmente la memoria).
+
+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; esta capacidad se denomina *overcommit*).
+
+Como se vio en la figura :vref:`fig:dgc-pool`, lás 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.
+
+
+
+.. _dgc_good:
+
+Características destacadas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Si bien el recolector en términos generales no se aleja mucho de un
+:ref:`marcado y barrido clásico <gc_mark_sweep>`, 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
+<gc_free_list>`), 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 es en el peor caso, al igual que la cantidad de
+recursiones del algoritmo recursivo, :math:`O(|Live \thickspace set|)`, pero
+cada pasada se realiza por 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 y está implementado reservando un poco más de
+   memoria de la que pide el usuario, devolviendo un puntero a un bloque
+   ubicado dentro del bloque real reservado (en vez de al inicio) y finalmente
+   escribiendo un patrón de bits en los extremos del borde real (ver figura
+   :vref:`fig:sentinel`), de forma de poder verificar en distintas situación
+   (por ejemplo al barrer el bloque) que esas áreas de más con los patrones de
+   bits estén intactas. Esto permite detectar de forma temprana errores tanto
+   en el recolector como en el programa del usuario.
+
+   .. fig:: fig:sentinel
+
+      Esquema de un bloque cuando está activada la opción ``SENTINEL``.
+
+      .. aafig::
+
+         |              |              |                              |        |
+         +-- Palabra ---+-- Palabra ---+-- Tamaño bloque de usuario --+- Byte -+
+         |              |              |                              |        |
+
+         +--------------+--------------+------------------------------+--------+
+         |  Tamaño del  |     Pre      |                              |  Post  |
+         |  bloque  de  |              |      Bloque de usuario       |        |
+         |    usuario   |  0xF4F4F4F4  |                              |  0xF5  |
+         +--------------+--------------+------------------------------+--------+
+                                       A
+                                       |
+                   Puntero devuleto ---/
+
+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.
+
+
+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.
+
+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()`` son
+300 líneas de código.
+
+
+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 es
+discutible.
+
+
+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 [NGDN87831]_, pero no han habido
+avances al respecto.
+
+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
+^^^^^^^^^^^^^^^^^^^
+El recolector actual no dispone de soporte de *referencias débiles*
+[#dgcweakref]_, 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]_.
+
+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]_ [NGDN87831]_.
+
+Además se ha mostrado un interés por tener un nivel de concurrencia aún mayor
+en el recolector, para aumentar la concurrencia 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 [NGDN87831]_ [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 (de hecho,
+rigurosamente hablando la especificación de D_ no garantiza la finalización de
+objetos bajo ninguna circunstancia), no hay mayores problemas para implementar
+un recolector que de 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]_.
 
 
-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]_.
+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]_.
 
-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).
+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.
 
-Soluciones Propuestas
+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 ajustarlo a las necesidades particulares de
+sus programas.
 
-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]_.
 
-.. _`versión 1.001`: http://www.digitalmars.com/d/changelog.html#new1_001
+.. _dgc_bad_ocup:
 
-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.
+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.
 
 
-Problemas para Implementar Colectores con Movimiento
+Detalles
+^^^^^^^^
+Finalmente hay varios detalles en la implementación actual que podrían
+mejorarse:
 
-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]_
+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.
 
-Problemas para Implementar Conteo de Referencias
+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]_.
 
-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]_.
+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*.
 
 
 .. 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 :