From: Leandro Lucarella <llucax@gmail.com>
Date: Mon, 15 Jun 2009 05:55:15 +0000 (-0300)
Subject: Agregar Detalles de implementación del recolector actual
X-Git-Tag: entrega-2010-10-08~45
X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/commitdiff_plain/a12d176928b68dd84292540dba539cdb75e6f102?ds=inline

Agregar Detalles de implementación del recolector actual
---

diff --git a/source/dgc.rst b/source/dgc.rst
index 941a4fd..f3327bd 100644
--- a/source/dgc.rst
+++ b/source/dgc.rst
@@ -790,12 +790,440 @@ objetos sean finalizados.
 Detalles de implementación
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-.. Acá diría por qué hay que reescribirlo para usar lo que está
+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á construído 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 la eficiencia es crítica 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.
 
-TODO
+   .. aafig::
+      :scale: 1.4
+      :aspect: 0.45
+
+                /---  "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 contínua 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 comunmente 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 están considerablemente menos
+modularizados 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**
+
+   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 estas funciones:
+
+   *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``.
+
+   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**
+
+   Recordar que la ``pooltable`` siempre se mantiene ordenada según la
+   dirección de la primera página.
+
+   *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).
+
+**Recolección**
+
+   *mark(pbot, ptop)*:
+      marca un rango de memoria. Este método es análogo al ``mark()``
+      presentado en la sección :ref:`dgc_algo_mark` pero marca un rango
+      completo de memoria, lo que permite que sea considerablemente más
+      eficiente.
+
+   *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 desapilar, 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
+      considerablemente menos modularizada, 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-encomentada*. 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_problems:
+
 Problemas y limitaciones
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~