+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`).
projects / z.facultad / 75.00 / informe.git / blobdiff