Agregar liberación y finalización del algoritmo actual

[z.facultad/75.00/informe.git] / source / dgc.rst

.. 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


.. _dgc:

Recolección de basura en D
============================================================================

TODO



Dificultades para recolectar basura en D
----------------------------------------------------------------------------

TODO



.. _dgc_actual:

Recolector de basura actual de D
----------------------------------------------------------------------------

Como paso básico fundamental para poder mejorar el recolector de basura de D_,
primero hay que entender la implementación actual, de forma de conocer sus
puntos fuertes, problemas y limitaciones, de manera tal de poder analizar
formas de mejorarlo.

Como se mencionó en la sección :ref:`d_lang`, en D_ hay dos bibliotecas base
para soportar el lenguaje (*runtimes*): Phobos_ y Tango_. La primera es la
biblioteca estándar de D_, la segunda un proyecto más abierto y dinámico que
surgió como alternativa a Phobos_ debido a que Phobos_ es muy desprolija y que
era muy difícil impulsar cambios en ella. Ahora Phobos_ tiene el agravante de
estar *congelada* en su versión 1 (solo se realizan correcciones de errores).

Dado que Tango_ está mejor organizada, su desarrollo es más abierto (aceptan
cambios y mejoras) y que hay una mayor disponibilidad de programas
y bibliotecas escritos para Tango_, en este trabajo se decide tomar esta
biblioteca *runtime* como base para el análisis y mejoras propuestas, a pesar
de ser Phobos_ la estándar. De todas formas el recolector de basura de Tango_
es prácticamente el mismo que el de Phobos_, por lo tanto éste análisis en
particular es válido para cualquiera de las dos.

El recolector actual es un recolector :ref:`indirecto <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:

Organización del *heap*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

La memoria del *heap* está organizada en *pools*. Un *pool* es una región de
*páginas* contíguas. Una página es, en general, la unidad mínima de memoria que
maneja un sistema operativo con soporte de memoria virtual. Cada página dentro
de un *pool* sirve a su vez como contenedora de bloques (llamados *bin* en la
:ref:`implementación <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 contíguas de un pool que tengan espacio suficiente para almacenar
dicho objeto.

.. [#dgcpageplus] Además existe otro tamaño de bloque especial que se utiliza
   para indicar la continuación de un objeto grande (que ocupan más de una
   página).

.. fig:: fig:dgc-org

   Organización del *heap* del recolector de basura actual de D.

   Organización del *heap*. En este ejemplo todos los *pools* tienen 2 páginas
   excepto el *pool* 2 que tiene una sola.  El tamaño de bloque que almacena
   cada página varía entre 64 bytes (página 0 del *pool* 2) hasta 4096 (ambas
   páginas del *pool* N) que es una página completa.

   .. aafig::
      :scale: 1.4

      +----------------------------------------------------------------------+
      |                                 Heap                                 |
      +======================================================================+
      |   "Pool 0"     "Pool 1"     "Pool 2"     "Pool 3"   ...   "Pool N"   |
      | +----------+ +----------+ +----------+ +----------+     +----------+ |
      | | Página 0 | | Página 0 | | Página 0 | | Página 0 | ... | Página 0 | |
      | |  (8x512) | | (4x1024) | |  (64x64) | | (2x2048) | ... | (1x4096) | |
      | |+--------+| |+--------+| |+--------+| |+--------+|     |+--------+| |
      | || Bloque || ||        || ||qqqqqqqq|| ||        ||     ||        || |
      | |+--------+| || Bloque || ||qqqqqqqq|| ||        ||     ||        || |
      | || Bloque || ||        || ||qqqqqqqq|| ||        ||     ||        || |
      | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque ||     ||        || |
      | || Bloque || ||        || ||qqqqqqqq|| ||        ||     ||        || |
      | |+--------+| || Bloque || ||qqqqqqqq|| ||        ||     ||        || |
      | || Bloque || ||        || ||qqqqqqqq|| ||        ||     ||        || |
      | |+--------+| |+--------+| ||qqqqqqqq|| |+--------+|     || Bloque || |
      | || Bloque || ||        || ||qqqqqqqq|| ||        ||     ||        || |
      | |+--------+| || Bloque || ||qqqqqqqq|| ||        ||     ||        || |
      | || Bloque || ||        || ||qqqqqqqq|| ||        ||     ||        || |
      | |+--------+| |+--------+| ||qqqqqqqq|| || Bloque ||     ||        || |
      | || Bloque || ||        || ||qqqqqqqq|| ||        ||     ||        || |
      | |+--------+| || Bloque || ||qqqqqqqq|| ||        ||     ||        || |
      | || Bloque || ||        || ||qqqqqqqq|| ||        ||     ||        || |
      | |+--------+| |+--------+| |+--------+| |+--------+|     |+--------+| |
      | | Página 1 | | Página 1 | +----------+ | Página 1 | ... | Página 1 | |
      | | (16x256) | |  (8x512) |              | (32x128) | ... | (1x4096) | |
      | |+--------+| |+--------+|              |+--------+|     |+--------+| |
      | |+--------+| || Bloque ||              ||nnnnnnnn||     ||        || |
      | |+--------+| |+--------+|              ||nnnnnnnn||     ||        || |
      | |+--------+| || Bloque ||              ||nnnnnnnn||     ||        || |
      | |+--------+| |+--------+|              ||nnnnnnnn||     ||        || |
      | |+--------+| || Bloque ||              ||nnnnnnnn||     ||        || |
      | |+--------+| |+--------+|              ||nnnnnnnn||     ||        || |
      | |+--------+| || Bloque ||              ||nnnnnnnn||     ||        || |
      | |+--------+| |+--------+|              ||nnnnnnnn||     || Bloque || |
      | |+--------+| || Bloque ||              ||nnnnnnnn||     ||        || |
      | |+--------+| |+--------+|              ||nnnnnnnn||     ||        || |
      | |+--------+| || Bloque ||              ||nnnnnnnn||     ||        || |
      | |+--------+| |+--------+|              ||nnnnnnnn||     ||        || |
      | |+--------+| || Bloque ||              ||nnnnnnnn||     ||        || |
      | |+--------+| |+--------+|              ||nnnnnnnn||     ||        || |
      | |+--------+| || Bloque ||              ||nnnnnnnn||     ||        || |
      | |+--------+| |+--------+|              |+--------+| ... |+--------+| |
      | +----------+ +----------+              +----------+     +----------+ |
      +----------------------------------------------------------------------+

Cada página de un *pool* puede estar asignada a contener bloques de un tamaño
específico o puede estar libre. A su vez, cada bloque puede estar ocupado por
una celda o estar libre. Los bloques libres de un tamaño específico (a
excepción de aquellos bloques que ocupen una página entera) además forman
parte de una :ref:`lista de libres <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 contíguo de tamaño ``PAGE_SIZE * number_of_pages``
   (siendo ``PAGE_SIZE`` el tamaño de página, que normalmente son 4096 bytes).


Atributos de página
^^^^^^^^^^^^^^^^^^^
Cada página dentro de un *pool* tiene un único atributo asociado: *block_size*.
Se trata del tamaño de los bloques que almacena esta página.

Una página siempre almacena bloques del mismo tamaño, que pueden ser 16, 32,
64, 128, 256, 512, 1024, 2048 o 4096 (llamado con el nombre especial
``PAGE``). Además hay dos tamaños de bloque símbólicos que tienen un
significado especial:

``FREE``:
   indica que la página está completamente libre y que la página está
   disponible para albergar cualquier tamaño de bloque que sea necesario (pero
   una vez que se le asignó un nuevo tamaño de bloque ya no puede ser cambiado
   hasta que la página vuelva a liberarse por completo).

``CONTINUATION``:
   indica que esta página es la continuación de un objeto grande (es decir,
   que ocupa una o más páginas). Luego se presentan más detalles sobre objetos
   grandes.

Las páginas con esto tamaños de bloque especiales (conceptualmente) no
contienen bloques.


Atributos de bloque
^^^^^^^^^^^^^^^^^^^
Cada bloque tiene asociados varios atributos:

*mark*:
   utilizado en la fase de :ref:`marcado <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 contíguos subsiguientes que tengan
el tamaño de bloque ``CONTINUATION`` (si el objeto ocupa más que una página).
El fin de un objeto grande queda marcado por el fin del *pool* o una página
con tamaño de bloque distinto a ``CONTINUATION`` (lo que suceda primero).

Cuando un objeto grande se convierte en *basura*, todas sus páginas se liberan
por completo, siendo marcadas con tamaño ``FREE`` para que puedan ser
almacenado en ellas otros objetos grandes o incluso nuevos bloques de un
tamaño determinado.



.. _dgc_algo:

Algoritmos del recolector
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

A continuación se explica como provee el recolector actual de D_ los servicios
básicos que debe proveer cualquier recolector, como se presentó en la sección
:ref:`gc_intro_services`.

Cabe aclarar que se presenta una versión simplificada del algoritmo, o más
precisamente, de la implementación del algoritmo, ya que no se exponen en esta
sección muchas optimizaciones que harían muy compleja la tarea de explicar
como funciona conceptualmente. En la siguiente sección, :ref:`dgc_impl`, se
darán más detalles sobre las optimizaciones importantes y diferencias con el
algoritmo aquí presentado, junto con detalles sobre como se implementa la
organización del *heap* que se explicó en la sección anterior.


.. _dgc_algo_collect:

Recolección
^^^^^^^^^^^
A grandes razgos el algoritmo de recolección puede resumirse de las dos fases
básicas de cualquier algoritmo de :ref:`marcado y barrido <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
      more_to_scan = false
      stop_the_world()
      clear_mark_scan_bits()
      mark_free_lists()
      mark_static_data()
      push_registers_into_stack()
      mark_stacks()
      mark_user_roots()
      mark_heap()
      start_the_world()

La variable **global** ``more_to_scan`` indica al algoritmo iterativo cuando
debe finalizar: la función ``mark()`` (que veremos más adelante) lo pone en
``true`` cuando una nueva celda debe ser visitada, por lo tanto la iteración
se interrumpe cuando no hay más celdas por visitar.

Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente
pausan y reanudan todos los hilos respectivamente::

   function stop_the_world() is
      foreach thread in threads
         thread.pause()

   function start_the_world() is
      foreach thread in threads
         thread.resume()

La función ``clear_mark_scan_bits()`` se encarga de resetear todos los
atributos *mark* y *scan* de cada bloque del *heap*::

   function clear_mark_scan_bits() is
      foreach pool in heap
         foreach page in pool
            foreach block in page
               block.mark = false
               block.scan = false

La función ``mark_free_lists()`` por su parte se encarga de activar el bit
*mark* de todos los bloques de las listas de libres de manera de que la fase
de marcado (que es iterativa y realiza varias pasadas sobre **todo** el
*heap*, incluyendo las celdas libres) no visite las celdas libres perdiendo
tiempo sin sentido y potencialmente manteniendo *vivas* celdas que en
realdidad son *basura* (falsos positivos)::

   function mark_free_lists() is
      foreach free_list in heap
         foreach block in free_list
            block.mark = true
            block.free = true

Notar que los bloques libres quedan entonces marcados aunque sean *basura* por
definición. Para evitar que en la etapa de barrido se tomen estos bloques como
celdas vivas, a todos los bloques en la lista de libres también se los marca
con el bit *free*, así el barrido puede tomar como *basura* estos bloques
aunque estén marcados.

El *root set* está compuesto por el área de memoria estática (variables
globales), los *stacks* de todos los hilos y los registros del procesador.
Primero se marca el área de memoria estática de manera :ref:`conservativa
<gc_conserv>` (es decir, tomando cada *word* como si fuera un puntero)::

   function mark_static_data() is
      foreach word in static_data
         pointer = cast(void*) word
         mark(pointer)

Para poder tomar los registros como parte del *root set* primero se apilan
en el *stack* a través de la función::

   function push_registers_into_stack() is
      foreach register in registers
         push(register)

Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos
los threads para terminar de marcar el *root set*::

   function mark_stacks() is
      foreach thread in threads
         foreach word in thread.stack
            pointer = cast(void*) word
            mark(pointer)

Dado que D_ soporta manejo de memoria manual al mismo tiempo que memoria
automática, es posible que existan celdas de memoria que no estén en el *root
set* convencional ni en el *heap* del recolector. Para evitar que se libere
alguna celda que estaba siendo referenciada desde memoria administrada por el
usuario, éste debe informarle al recolector sobre la existencia de estoas
nuevas raíces. Es por esto que para concluir el marcado del *root set*
completo se procede a marcar las raíces definidas por el usuario::

   function mark_user_roots() is
      foreach pointer in user_roots
         mark(pointer)

El algoritmo de marcado no es recursivo sino iterativo por lo tanto al marcar
una celda (o bloque) no se siguen sus *hijas*, solo se activa el bit de *scan*
(a menos que la celda no contenga punteros, es decir, tenga el bit *noscan*)::

   function mark(pointer) is
      [pool, page, block] = find_block(pointer)
      if block is not null and block.mark is false
         block.mark = true
         if block.noscan is false
            block.scan = true
            more_to_scan = true

Por lo tanto en este punto, tenemos todas las celdas inmediatamente
alcanzables desde el *root set* marcadas y con el bit *scan* activado si la
celda puede contener punteros. Por lo tanto solo resta marcar (nuevamente de
forma conservativa) iterativamente todo el *heap* hasta que no hayan más
celdas para visitar (con el bit *scan* activo)::

   function mark_heap() is
      while more_to_scan
         more_to_scan = false
         foreach pool in heap
            foreach page in pool
               if page.block_size <= PAGE // saltea FREE y CONTINUATION
                  foreach block in page
                     if block.scan is true
                        block.scan = false
                        if page.block_size is PAGE // objeto grande
                           start = cast(byte*) page
                           end = find_big_object_end(pool, page)
                           foreach word in start..end
                                 pointer = cast(void*) word
                                 mark(pointer)
                        else // objeto pequeño
                           foreach word in block
                              pointer = cast(void*) word
                              mark(pointer)

Aquí puede verse, con un poco de esfuerzo, la utilización de la
:ref:`abtracción tricolor <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 big *scan*) y se pintan todas sus *hijas* de *gris* (o
*negro* directamente si no tienen punteros). Este procedimiento se repite
mientras el conjunto de celdas *grises* no sea vacío (es decir, que
``more_to_scan`` sea ``true``).

A continuación se presenta la implementación de las funciones suplementarias
utilizadas en la fase de marcado::

   function find_big_object_end(pool, page) is
      pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
      do
         page = cast(byte*) page + PAGE_SIZE
      while page.block_size is CONTINUATION and page < pool_end
      return page

   function find_block(pointer) is
      foreach pool in heap
         foreach page in pool
            if page.block_size is PAGE
               big_object_start = cast(byte*) page
               big_object_end = find_big_object_end(pool, page)
               if big_object_start <= pointer < big_object_end
                  return [pool, page, big_object_start]
            else if page.bloc_size < PAGE
               foreach block in page
                  block_start = cast(byte*) block
                  block_end = block_start + page.block_size
                  if block_start <= pointer < block_end
                     return [pool, page, block_start]
      return [null, null, null]

Cabe destacar que la función ``find_block()`` devuelve el pool, la página y el
comienzo del bloque al que apunta el puntero, es decir, soporta punteros
*interiores*.


.. _dgc_algo_sweep:

Fase de barrido
^^^^^^^^^^^^^^^
Esta fase es considerablemente más sencilla que el marcado; el algoritmo puede
dividirse en dos pasos básicos::

   function sweep_phase() is
      sweep()
      rebuild_free_lists()

El barrido se realiza con una pasada por sobre todo el *heap* 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
mojorada debido a que asignaciones de memoria proximas 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 asgina 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
asginan 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 contíguas, 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
contíguas 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 contíguas), 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
saltéa el mecanismo de recolección, y es utilizado para dar soporte a menejo
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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. Acá diría por qué hay que reescribirlo para usar lo que está

TODO



Problemas y limitaciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

TODO




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]_.

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).



Soluciones Propuestas

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

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.



Problemas para Implementar Colectores con Movimiento

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]_



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]_.


.. include:: links.rst

.. vim: set ts=3 sts=3 sw=3 et tw=78 :