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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
projects / z.facultad / 75.00 / informe.git / commitdiff