Modificaciones propuestas
----------------------------------------------------------------------------
-TODO
+Se decide realizar todas las modificaciones al recolector actual de forma
+progresiva e incremental, partiendo como base del recolector de la versión
+0.99.9 de Tango_. Las razones que motivan esta decisión son varias; por un
+lado es lo más apropiado dados los requerimientos claves mencionados al
+principio de este capítulo. Por ejemplo, al hacer cambios incrementales es más
+fácil comprobar que la eficiencia no se aleja mucho del actual con cada
+modificación y una modificación gradual impone menos resistencia a la
+aceptación del nuevo recolector.
+
+Además la construcción de un recolector de cero es una tarea difícil
+considerando que un error en el recolector es extremadamente complejo de
+rastrear, dado que en general el error se detecta en el *mutator* y en una
+instancia muy posterior al origen real del error. Esto ha sido comprobado de
+forma práctica, dado que, a modo de ejercicio para interiorizarse en el
+funcionamiento del *runtime* de D_, primero se ha construido desde cero una
+implementación de un recolector *naïve*, resultando muy difícil su depuración
+por las razones mencionadas. Por el contrario, comenzar con un recolector en
+funcionamiento como base hace más sencillo tanto probar cada pequeña
+modificación para asegurar que no introduce fallos, como encontrar y reparar
+los fallos cuando estos se producen, ya que el código incorrecto introducido
+está bien aislado e identificado.
+
+A continuación se hace un recorrido sobre cada una de las mejoras propuestas,
+y en los casos en los que la mejora propone un cambio algorítmico, se analiza
+la corrección del algoritmo resultante, partiendo de la base de que el
+algoritmo tomado como punto de partida es un marcado y barrido que utiliza la
+abstracción tricolor para hacer la fase de marcado de forma iterativa (ver
+:ref:`gc_mark_sweep` y :ref:`gc_intro_tricolor`), cuya corrección ya está
+probada en la literatura preexistente.
+
+
+.. _sol_config:
+
+Configurabilidad
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Una de las primeras mejoras propuestas es la posibilidad de configurar el
+recolector de forma más sencilla. El requerimiento mínimo es la posibilidad de
+configurar el recolector sin necesidad de recompilarlo. La complejidad de esto
+surge de que el recolector debe ser transparente para el programa del usuario.
+
+Configurar el recolector en tiempo de compilación del programa del usuario
+probablemente requeriría modificar el compilador, y además, si bien es una
+mejora sustancial a la configuración en tiempo de compilación del recolector,
+no termina de ser completamente conveniente para realizar pruebas reiteradas
+con un mismo programa para encontrar los mejores valores de configuración para
+ese programa en particular.
+
+Por otro lado, permitir configurar el recolector en tiempo de ejecución, una
+vez que su estructura interna ya fue definida y creada, puede ser no solo
+tedioso y complejo, además ineficiente, por lo tanto esta opción también se
+descarta.
+
+Finalmente, lo que parece ser más apropiado para un recolector, es permitir la
+configuración en tiempo de inicialización. Es decir, configurar el recolectar
+sin necesidad de recompilar ni el programa del usuario ni el recolector, pero
+antes de que el programa del usuario inicie, de manera que una vez iniciado el
+recolector con ciertos parámetros, éstos no cambien nunca más en durante la
+vida del programa.
+
+Este esquema provee la mejor relación entre configurabilidad, conveniencia,
+eficiencia y simplicidad. Una posibilidad para lograr esto es utilizar
+parámetros de línea de comandos, sin embargo no parece ni sencillo (proveer
+una forma de leer los parámetros de línea de comandos requiere cambios en el
+*runtime*) ni apropiado (el recolector debería ser lo más transparente posible
+para el programa del usuario).
+
+Otra posibilidad es utilizar variables de entorno, que parece ser la opción
+más sencilla y apropiada. Sencilla porque las variables de entorno pueden ser
+leídas directamente al inicializar el recolector sin necesidad de cooperación
+alguna del *runtime*, a través de :manpage:`getenv(3)`. Apropiada porque, si
+bien el problema de invasión del programa del usuario también existe, es una
+práctica más frecuente y aceptada la configuración de módulos internos
+o bibliotecas compartidas a través de variables de entorno.
+
+Por último, antes de comenzar a usar este esquema de configuración, se
+verifica que tomar ciertas decisiones en tiempo de ejecución no impacten en la
+eficiencia del recolector. Para esto se convierten algunas opciones que antes
+eran solo seleccionables en tiempo de compilación del recolector para que
+puedan ser seleccionables en tiempo de inicialización y se comprueba que no
+hay una penalización apreciable.
+
+
+.. _sol_config_spec:
+
+Especificación de opciones
+^^^^^^^^^^^^^^^^^^^^^^^^^^
+Para especificar opciones de configuración, hay que hacerlo a través de la
+variable de entorno de nombre :envvar:`D_GC_OPTS`. El valor de esa variable es
+interpretado de la siguiente manera (en formato similar a :term:`BNF`):
+
+.. productionlist::
+ D_GC_OPTS: `option` ( ':' `option` )* <lista de opciones>
+ option: `name` [ '=' `value` ]
+ name: `namec` `namec`* <nombre de la opción>
+ value: `valuec`* <valor de la opción>
+ namec: `valuec` - '='
+ valuec: [0x01-0xFF] - ':' <cualquiera salvo '\0' y ':'>
+
+Es decir, se compone de una lista de opciones separadas por **:**. Cada opción
+se especifica con un nombre, opcionalmente seguido por un valor (separados por
+**=**).
+
+El valor de una opción puede ser un texto arbitrario (exceptuando los
+caracteres ``'\0'`` y ``':'`` y de longitud máxima 255), pero cada opción lo
+interpreta de forma particular. Como caso general, hay opciones booleanas, que
+toman como valor verdadero un cualquier número distinto de 0 (o si el valor es
+vació, es decir, solo se indica el nombre de la opción), y como valor falso
+cualquier otro texto.
+
+A continuación se listan las opciones reconocidas por el recolector (indicando
+el formato del valor de la opción de tener uno especial):
+
+``mem_stomp``
+ Esta es una opción (booleana) disponible en el recolector original, pero
+ que se cambia para que sea configurable en tiempo de inicialización
+ (estando desactivada por omisión). Activa la opción ``MEMSTOMP`` descripta
+ en :ref:`dgc_debug`.
+
+``sentinel``
+ Esta opción es también booleana (desactivada por omisión), está disponible
+ en el recolector original, y se la cambia para sea configurable en tiempo
+ de inicialización. Activa la opción ``SENTINEL`` descripta en
+ :ref:`dgc_debug`.
+
+``pre_alloc``
+ Esta opción permite crear una cierta cantidad de *pools* de un tamaño
+ determinado previo a que inicie el programa. Si se especifica solo un
+ número, se crea un *pool* con ese tamaño en MiB. Si, en cambio, se
+ especifica una cadena del tipo ``3x1``, el primer número indica la cantidad
+ de *pools* y el segundo el tamaño en MiB de cada uno (3 *pools* de 1MiB en
+ este caso). Ver :ref:`sol_pre_alloc` para más detalles sobre la utilidad de
+ esta opción.
+
+``min_free``
+ El valor de esta opción indica el porcentaje mínimo porcentaje del *heap*
+ que debe quedar libre luego de una recolección. Siendo un porcentaje, solo
+ se aceptan valores entre 0 y 100, siendo su valor por omisión 5. Ver
+ :ref:`sol_ocup` para más detalles sobre su propósito.
+
+``malloc_stats_file``
+ Esta opción sirve para especificar un archivo en el cual escribir un
+ reporte de todas la operaciones de pedido de memoria realizadas por el
+ programa (durante su tiempo de vida). Ver :ref:`sol_stats` para más
+ detalles sobre la información provista y el formato del reporte.
+
+``collect_stats_file``
+ Esta opción sirve para especificar un archivo en el cual escribir un
+ reporte de todas las recolecciones hechas durante el tiempo de vida del
+ programa. Ver :ref:`sol_stats` para más detalles sobre la información
+ provista y el formato del reporte.
+
+``conservative``
+ Esta opción booleana permite desactivar el escaneo preciso del *heap*,
+ forzando al recolector a ser completamente conservativo (excepto por los
+ bloques con el atributo ``NO_SCAN`` que siguen sin ser escaneados). Ver
+ :ref:`sol_precise` para más detalles sobre la existencia de esta opción.
+
+``fork``
+ Esta opción booleana (activada por omisión) permite seleccionar si el
+ recolector debe correr la fase de marcado en paralelo o no (es decir, si el
+ recolector corre de forma concurrente con el *mutator*). Para más detalles
+ ver :ref:`sol_fork`.
+
+``eager_alloc``
+ Esta opción booleana (activada por omisión), sólo puede estar activa si
+ ``fork`` también está activa y sirve para indicar al recolector que reserve
+ un nuevo *pool* de memoria cuando una petición no puede ser satisfecha,
+ justo antes de lanzar la recolección concurrente. Ver
+ :ref:`sol_eager_alloc` para más detalles sobre el propósito de esta opción.
+
+``early_collect``
+ Esta opción booleana (desactivada por omisión), también sólo puede estar
+ activa si ``fork`` está activa y sirve para indicar al recolector que lance
+ una recolección (concurrente) antes de que la memoria libre se termine (la
+ recolección temprana será disparada cuando el porcentaje de memoria libre
+ sea menor a ``min_free``). Ver :ref:`sol_early_collect` para más detalles
+ sobre el propósito de esta opción.
+
+Cualquier opción o valor no reconocido es ignorado por el recolector. Se
+utilizan los valores por omisión de las opciones que no fueron especificadas,
+o cuyos valores no pudieron ser interpretados correctamente.
+
+Para cambiar la configuración del recolector se puede invocar el programa de
+la siguiente manera (usando un intérprete de comandos del tipo *bourne
+shell*):
+
+.. code-block:: none
+
+ D_GC_OPTS=conservative:eager_alloc=0:early_collect=1:pre_alloc=2x5 ./programa
+
+En este ejemplo, se activan las opciones ``conservative`` y ``early_collect``,
+se desactiva ``eager_alloc`` y se crean 2 *pools* de 5MiB cada uno al
+inicializar el recolector.
+
+
+Reestructuración y cambios menores
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Si bien se decide no comenzar una implementación desde cero, se ha mostrado
+(ver :ref:`dgc_bad_code`) que la implementación actual es lo suficientemente
+desprolija como para complicar su modificación. Es por esto que se hacen
+algunas reestructuraciones básicas del código, reescribiendo o saneando de
+forma incremental todas aquellas partes que complican su evolución.
+
+Además de las modificaciones puramente estéticas (aunque no por eso menos
+valuables, ya que la legibilidad y simplicidad del código son un factor
+fundamental a la hora de ser mantenido o extendido), se hacen otras pequeñas
+mejoras, que se detallan a continuación.
+
+Remoción de memoria encomendada
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Si bien a nivel de eficiencia este cambio no tuvo impacto alguno (cuando en un
+principio se especuló con que podría dar alguna ganancia en este sentido), se
+elimina el concepto de memoria *encomendada* para quitar complejidad al
+código.
+
+Esta mejora no afecta a la corrección del algoritmo, ya que a nivel lógico el
+recolector solo ve la memoria *encomendada*.
+
+Micro-optimizaciones
+^^^^^^^^^^^^^^^^^^^^
+Si bien se realizan varias micro-optimizaciones, probablemente la más
+relevante es la inclusión de un caché de tamaño de bloque para el método
+``findSize()`` de un *pool*. Esto acelera considerablemente las operaciones
+que necesitan pedir el tamaño de un bloque reiteradamente, por ejemplo, al
+añadir nuevos elementos a un arreglo dinámico.
+
+Esta mejora tampoco afecta a la corrección del algoritmo, ya que nuevamente no
+afecta su comportamiento a nivel lógico, solo cambia detalles en la
+implementación de forma transparentes para el algoritmo de recolección.
+
+Optimizaciones sobre ``findPool()``
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Al analizar los principales cuellos de botella del recolector, es notoria la
+cantidad de tiempo que pasa ejecutando la función ``findPool()``, que dado un
+puntero devuelve el *pool* de memoria al cual pertenece. Es por esto que se
+minimiza el uso de esta función. Además, dado que los *pools* de memoria están
+ordenados por el puntero de comienzo del bloque de memoria manejado por el
+*pool*, se cambia la búsqueda (originalmente lineal) por una búsqueda binaria.
+Finalmente, dado que la lista de libre está construida almacenando el puntero
+al siguiente en las mismas celdas que componen la lista, se almacena también
+el puntero al *pool* al que dicha celda pertenece (dado que la celda más
+pequeña es de 16 bytes, podemos garantizar que caben dos punteros, incluso
+para arquitecturas de 64 bits). De esta manera no es necesario usar
+``findPool()`` al quitar una celda de la lista de libres.
+
+Una vez más, la mejora no afecta la corrección del código.
+
+.. _sol_pre_alloc:
+
+Pre-asignación de memoria
+^^^^^^^^^^^^^^^^^^^^^^^^^
+Esta opción permite crear una cierta cantidad de *pools* de un tamaño
+determinado previo a que inicie el programa. Normalmente el recolector no
+reserva memoria hasta que el programa lo pida. Esto puede llegar a evitar
+que un programa haga muchas recolecciones al comenzar, hasta que haya
+cargado su conjunto de datos de trabajo.
+
+Se han analizado varios valores por omisión pero ninguno es consistentemente
+mejor que comenzar sin memoria asignada, por lo tanto no se cambia el
+comportamiento original, pero se agrega una opción (ver ``pre_alloc`` en
+:ref:`sol_config_spec`) para que el usuario pueda experimentar con cada
+programa en particular si esta opción es beneficiosa.
+
+Esta opción tampoco cambia la corrección del algoritmo de recolección, solo
+sus condiciones iniciales.
+
+.. _sol_ocup:
+
+Mejora del factor de ocupación del *heap*
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+El factor de ocupación del *heap* debe ser apropiado por dos razones. Por un
+lado, si el *heap* está demasiado ocupado todo el tiempo, serán necesarias
+muchas recolecciones que, aunque pequeñas dado que la memoria utilizada es
+poca, puede llegar a ser extremadamente ineficiente en casos patológicos (ver
+:ref:`dgc_bad_ocup`). Por otro lado, si el tamaño del *heap* es extremadamente
+grande (en comparación con el tamaño real del grupo de trabajo del programa),
+se harán pocas recolecciones pero cada una es muy costosa, porque el algoritmo
+de marcado y barrido es :math:`O(\lvert Heap \rvert)` (ver
+:ref:`gc_mark_sweep`). Además la afinidad del caché va a ser extremadamente
+pobre.
+
+Para mantener el factor de ocupación dentro de límites razonables, se agrega
+la opción ``min_free`` (ver :ref:`sol_config_spec`). Esta opción indica el
+recolector cual debe ser el porcentaje mínimo del *heap* que debe quedar libre
+luego de una recolección. En caso de no cumplirse, se pide más memoria al
+sistema operativo para cumplir este requerimiento. Además, luego de cada
+recolección se verifica que el tamaño del *heap* no sea mayor a ``min_free``,
+para evitar que el *heap* crezca de forma descontrolada. Si es mayor
+a ``min_free`` se intenta minimizar el uso de memoria liberando *pools* que
+estén completamente desocupados, mientras que el factor de ocupación siga
+siendo mayor a ``min_free``. Si liberar un *pool* implica pasar ese límite, no
+se libera y se pasa a analizar el siguiente y así sucesivamente.
+
+Esta modificación no afecta a la corrección del algoritmo, ya que no lo afecta
+directamente.
+
+Modificaciones descartadas
+^^^^^^^^^^^^^^^^^^^^^^^^^^
+Se realizan varias otras modificaciones, con la esperanza de mejorar la
+eficiencia del recolector, pero que, al contrario de lo esperado, empeoran la
+eficiencia o la mejoran de forma muy marginal en comparación con la
+complejidad agregada.
+
+Probablemente el caso más significativo, y por tanto el único que vale la pena
+mencionar, es la conversión de marcado iterativo a marcado recursivo y luego
+a un esquema híbrido. Como se describe en :ref:`dgc_bad`, el marcado iterativo
+tiene sus ventajas, pero tiene desventajas también. Al convertirlo a puramente
+recursivo, se impracticable por resultar en errores de desbordamiento de pila.
+
+Por lo tanto se prueba con un esquema híbrido, poniendo un límite a la
+recursividad, volviendo al algoritmo iterativo cuando se alcanza este límite.
+
+La implementación del algoritmo híbrido consiste en los siguientes cambios
+sobre el algoritmo original (ver :ref:`dgc_algo_mark`)::
+
+ function mark_phase() is
+ global more_to_scan = false
+ global depth = 0 // Agregado
+ stop_the_world()
+ clear_mark_scan_bits()
+ mark_free_lists()
+ mark_static_data()
+ push_registers_into_stack()
+ thread_self.stack.end = get_stack_top()
+ mark_stacks()
+ pop_registers_from_stack()
+ mark_user_roots()
+ mark_heap()
+ start_the_world()
+
+ function mark_range(begin, end) is
+ pointer = begin
+ global depth++ // Agregado
+ 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
+ if (global depth > MAX_DEPTH) //
+ more_to_scan = true //
+ else // Agregado
+ foreach ptr in block.words //
+ mark(ptr) //
+ global depth-- //
+
+Al analizar los resultados de de esta modificación, se observa una mejoría muy
+level, para valores de ``MAX_DEPTH`` mayores a cero (en algunos casos bastante
+mayores) y en general para ``MAX_DEPTH`` cero (es decir, usando el algoritmo
+de forma completamente iterativa) los resultados son peores, dado que se paga
+el trabajo extra sin ganancia alguna. En la figura :vref:`fig:sol-mark-rec` se
+puede ver, por ejemplo, el tiempo total de ejecución de Dil_ al generar la
+documentación completa del código de Tango_, según varía el valor de
+``MAX_DEPTH``.
+
+.. fig:: fig:sol-mark-rec
+
+ Análisis de tiempo total de ejecución en función del valor de
+ ``MAX_DEPTH``.
+
+ Tiempo total de ejecución de Dil_ al generar la documentación completa del
+ código de Tango_ en función del valor de ``MAX_DEPTH``. El rombo no
+ pertenece a ningún nivel de recursividad, representa el tiempo de ejecución
+ del algoritmo original (puramente iterativo).
+
+ .. image:: sol-mark-rec-dil.pdf
+
+
+Dado que aumentar el nivel máximo de recursividad significa un uso mayor del
+*stack*, y que esto puede impactar en el usuario (si el usuario tuviera un
+programa que esté al borde de consumir todo el *stack*, el recolector podría
+hacer fallar al programa de una forma inesperada para el usuario, problema que
+sería muy difícil de depurar para éste), y que los resultados obtenidos no son
+rotundamente superiores a los resultados sin esta modificación, se opta por no
+incluir este cambio. Tampoco vale la pena incluirlo como una opción con valor
+por omisión 0 porque, como se ha dicho, para este caso el resultado es incluso
+peor que sin la modificación.
+
+Esta modificación mantiene la corrección del recolector dado que tampoco
+modifica el algoritmo sino su implementación. Además ambos casos extremos son
+correctos (si ``MAX_DEPTH`` es 0, el algoritmo es puramente iterativo y si
+pudiera ser infinito resultaría en el algoritmo puramente recursivo).
+
+
+.. _sol_stats:
+
+Recolección de estadísticas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Un requerimiento importante, tanto para evaluar los resultados de este trabajo
+como para analizar el comportamiento de los programas estudiados, es la
+recolección de estadísticas. Hay muchos aspectos que pueden ser analizados
+a la hora de evaluar un recolector, y es por esto que se busca que la
+recolección de datos sea lo más completa posible.
+
+Con este objetivo, se decide recolectar datos sobre lo que, probablemente,
+sean las operaciones más importantes del recolector: asignación de memoria
+y recolección.
+
+Todos los datos recolectados son almacenados en archivos que se especifican
+a través de opciones del recolector (ver :ref:`sol_config_spec`). Los archivos
+especificados debe poder ser escritos (y creados de ser necesario) por el
+recolector (de otra forma se ignora la opción). El conjunto de datos
+recolectados son almacenados en formato :term:`CSV` en el archivo, comenzando
+con una cabecera que indica el significado de cada columna.
+
+Los datos recolectados tienen en general 4 tipos de valores diferentes:
+
+Tiempo
+ Se guarda en segundos como número de punto flotante (por ejemplo ``0.12``).
+
+Puntero
+ Se guarda en forma hexadecimal (por ejemplo ``0xa1b2c3d4``).
+
+Tamaño
+ Se guarda como un número decimal, expresado en bytes (por ejemplo ``32``).
+
+Indicador
+ Se guarda como el número ``0`` si es falso o ``1`` si es verdadero.
+
+Esta modificación mantiene la corrección del recolector dado que no hay cambio
+algorítmico alguno.
+
+Asignación de memoria
+^^^^^^^^^^^^^^^^^^^^^
+La recolección de datos sobre asignación de memoria se activa asignando un
+nombre de archivo a la opción ``malloc_stats_file``. Por cada asignación de
+memoria pedida por el programa (es decir, por cada llamada a la función
+``gc_malloc()``) se guarda una fila con los siguientes datos:
+
+1. Cantidad de segundos que pasaron desde que empezó el programa (*timestamp*).
+2. Tiempo total que tomó la asignación de memoria.
+3. Valor del puntero devuelto por la asignación.
+4. Tamaño de la memoria pedida por el programa.
+5. Si esta petición de memoria disparó una recolección o no.
+6. Si debe ejecutarse un *finalizador* sobre el objeto (almacenado en la
+ memoria pedida) cuando ésta no sea más alcanzable (cuando sea barrido).
+7. Si objeto carece de punteros (es decir, no debe ser escaneada).
+8. Si objeto no debe ser movido por el recolector.
+9. Puntero a la información sobre la ubicación de los punteros del objeto.
+10. Tamaño del tipo del objeto.
+11. Primera palabra con los bits que indican que palabras del tipo deben ser
+ escaneados punteros y cuales no (en hexadecimal).
+12. Primera palabra con los bits que indican que palabras del tipo son
+ punteros garantizados (en hexadecimal).
+
+Como puede apreciarse, la mayor parte de esta información sirve más para
+analizar el programa que el recolector. Probablemente solo el punto 2 sea de
+interés para analizar como se comporta el recolector.
+
+El punto 8 es completamente inútil, ya que el compilador nunca provee esta
+información, pero se la deja por si en algún momento comienza a hacerlo. Los
+puntos 9 a 12 provee información sobre el tipo del objeto almacenado, útil
+para un marcado preciso (ver :ref:`sol_precise`).
+
+El punto 6 indica, indirectamente, cuales de los objetos asignados son
+*pesados*, ya que éstos son los únicos que pueden tener un *finalizador*.
+Además, a través de los puntos 4 y 10 es posible inferir si lo que va
+almacenarse es un objeto solo o un arreglo de objetos.
+
+Recolección de basura
+^^^^^^^^^^^^^^^^^^^^^
+Los datos sobre las recolecciones realizadas se guardan al asignar un nombre
+de archivo a la opción ``collect_stats_file``. Cada vez que se dispara una
+recolección [#solcollect]_ (es decir, cada vez que se llama a la función
+``fullcollect()``) se guarda una fila con los siguientes datos:
+
+1. Cantidad de segundos que pasaron desde que empezó el programa (*timestamp*).
+2. Tiempo total que tomó la asignación de memoria que disparó la recolección.
+3. Tiempo total que tomó la recolección.
+4. Tiempo total que deben pausarse todos los hilos (tiempo de
+ *stop-the-world*).
+5. Cantidad de memoria usada antes de la recolección.
+6. Cantidad de memoria libre antes de la recolección.
+7. Cantidad de memoria desperdiciada antes de la recolección.
+8. Cantidad de memoria utilizada por el mismo recolector antes de la
+ recolección (para sus estructuras internas).
+9. Cantidad de memoria usada después de la recolección.
+10. Cantidad de memoria libre después de la recolección.
+11. Cantidad de memoria desperdiciada [#solwaste]_ después de la recolección.
+12. Cantidad de memoria utilizada por el mismo recolector después de la
+ recolección.
+
+Si bien el punto 4 parece ser el más importante para un programa que necesita
+baja latencia, dado el *lock* global del recolector, el punto 2 es
+probablemente el valor más significativo en este aspecto, dado que, a menos
+que el programa en cuestión utilice muy poco el recolector en distintos hilos,
+los hilos se verán pausados de todas formas cuando necesiten utilizar el
+recolector.
+
+.. [#solcollect] Esto es en el sentido más amplio posible. Por ejemplo, cuando
+ se utiliza marcado concurrente (ver :ref:`sol_fork`), se guarda esta
+ información incluso si ya hay una recolección activa, pero el tiempo de
+ pausa de los hilos será -1 para indicar que en realidad nunca fueron
+ pausados.
+
+.. [#solwaste] Memoria *desperdiciada* se refiere a memoria que directamente
+ no puede utilizarse debido a la fragmentación. Si por ejemplo, se piden 65
+ bytes de memoria, dada la organización del *heap* en bloques (ver
+ :ref:`dgc_org`), el recolector asignará un bloque de 128 bytes, por lo
+ tanto 63 bytes quedarán desperdiciados.
+
+
+.. _sol_precise:
+
+Marcado preciso
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+En paralelo con este trabajo, David Simcha comienza a explorar la posibilidad
+de agregar precisión parcial al recolector, generando información sobre la
+ubicación de los punteros para cada tipo [DBZ3463]_. Su trabajo se limita
+a una implementación a nivel biblioteca de usuario y sobre `D 2.0`_.
+Desafortunadamente su trabajo pasa desapercibido por un buen tiempo.
+
+Luego Vincent Lang (mejor conocido como *wm4* en la comunidad de D_), retoma
+este trabajo, pero modificando el compilador DMD_ y trabajando con `D 1.0`_
+y Tango_, al igual que este trabajo. Dado el objetivo y entorno común, se abre
+la posibilidad de adaptar los cambios de Vincent Lang a este trabajo,
+utilizando una versión modificada de DMD_ (dado que los cambios aún no son
+integrados al compilador oficial).
+
+Información de tipos provista por el compilador
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Con éstas modificaciones, el compilador en cada asignación le pasa al
+recolector información sobre los punteros del tipo para el cual se pide la
+memoria. Esta información se pasa como un puntero a un arreglo de palabras con
+la estructura mostrada en la figura :vref:`fig:sol-ptrmap` y que se describe
+a continuación.
+
+.. fig:: fig:sol-ptrmap
+
+ Estructura de la información de tipos provista por el compilador.
+
+ .. aafig::
+ :scale: 110
+
+ /----- ptrmap
+ |
+ V
+ +-------------+----------------------------+----------------------------+
+ | "Tamaño en" | "Bits indicando si la" | "Bits indicando si" |
+ | "cantidad" | "palabra en una posición" | "la palabra en una" |
+ | "de" | "debe escanearse como" | "posición es" |
+ | "palabras" | "si fuera un puntero" | "un puntero" |
+ +-------------+----------------------------+----------------------------+
+
+ | | | |
+ +----- 1 -----+------- ceil(N/BPW) --------+------- ceil(N/BPW) --------+
+ | | | |
+
+* La primera palabra indica el tamaño, en **cantidad de palabras**, del tipo
+ para el cual se pide la memoria (:math:`N`).
+* Las siguientes :math:`ceil(\frac{N}{BPW})` palabras indican,
+ como un conjunto de bits, qué palabras deben ser escaneadas por el
+ recolector como si fueran punteros (donde :math:`BPW` indica la cantidad de
+ bits por palabra, por ejemplo 32 para x86).
+* Las siguientes :math:`ceil(\frac{N}{BPW})` palabras son otro conjunto de
+ bits indicando qué palabras son realmente punteros.
+
+Los conjuntos de bits guardan la información sobre la primera palabra en el
+bit menos significativo. Dada la complejidad de la representación, se ilustra
+con un ejemplo. Dada la estructura::
+
+ union U {
+ ubyte ub;
+ void* ptr;
+ }
+
+ struct S
+ {
+ void* begin1; // 1 word
+ byte[size_t.sizeof * 14 + 1] bytes; // 15 words
+ // el compilador agrega bytes de "padding" para alinear
+ void* middle; // 1 word
+ size_t[14] ints; // 14 words
+ void* end1; // 1 words
+ // hasta acá se almacenan los bits en la primera palabra
+ void* begin2; // 1 words
+ int i; // 1 word
+ U u; // 1 word
+ S* s; // 1 word
+ }
+
+El compilador genera la estructura que se muestra en la figura
+:vref:`fig:sol-ptrmap-example` (asumiendo una arquitectura de 32 bits). Como
+puede apreciarse, el miembro ``u``, al ser una unión entre un puntero y un
+dato común, el compilador no puede asegurar que lo que se guarda en esa
+palabra sea realmente un puntero, pero indica que debe ser escaneado. El
+recolector debe debe ser conservativo en este caso, y escanear esa palabra
+como si fuera un puntero.
+
+.. fig:: fig:sol-ptrmap-example
+
+ Ejemplo de estructura de información de tipos generada para el tipo ``S``.
+
+ .. aafig::
+ :textual:
+ :aspect: 55
+ :scale: 110
+
+ /---- "bit de 'end1'"
+ |
+ | /---- "bit de 'middle'"
+ | |
+ | "bits de" | "bits de" /---- "bit de 'begin1'"
+ | "'ints'" | "'bytes'" |
+ |/------------\|/-------------\|
+ V| |V| |V
+ +----------------------------------+
+ | 00000000000000000000000000100100 | "Tamaño en cantidad de palabras (36)"
+ +==================================+ --\
+ | 10000000000000010000000000000001 | | "Bits que indican si hay que"
+ +----------------------------------+ | "escanear una palabra según"
+ | 00000000000000000000000000001101 | | "su posición"
+ +==================================+ --+
+ | 10000000000000010000000000000001 | | "Bits que indican si hay un"
+ +----------------------------------+ | "puntero en la palabra según"
+ | 00000000000000000000000000001001 | | "su posición"
+ +----------------------------------+ --/
+ | |AAAA
+ \--------------------------/||||
+ "bits de relleno" ||||
+ ||||
+ "bit de 's'" ||||
+ | ||||
+ \---------------/||\---- "bit de 'begin2'"
+ ||
+ /---------------/\---- "bit de 'i'"
+ |
+ "bit de 'u'"
+
+Si una implementación quisiera mover memoria (ver :ref:`gc_moving`), debería
+mantener inmóvil a cualquier objeto que sea apuntado por una palabra de estas
+características, ya que no es seguro actualizar la palabra con la nueva
+posición el objeto movido. Es por esta razón que se provee desglosada la
+información sobre lo que hay que escanear, y lo que es realmente un puntero
+(que puede ser actualizado de forma segura por el recolector de ser
+necesario).
+
+Implementación en el recolector
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+La implementación está basada en la idea original de David Simcha, pero
+partiendo de la implementación de Vincent Lang (que está basada en Tango_)
+y consiste en almacenar el puntero a la estructura con la descripción del tipo
+generada por el compilador al final del bloque de datos. Este puntero solo se
+almacena si el bloque solicitado no tiene el atributo ``NO_SCAN``, dado que en
+ese caso no hace falta directamente escanear ninguna palabra del bloque.
+
+En la figura :vref:`fig:sol-ptrmap-blk` se puede ver, como continuación del
+ejemplo anterior, como se almacenaría en memoria un objeto del tipo ``S``.
+
+.. fig:: fig:sol-ptrmap-blk
+
+ Ejemplo de bloque que almacena un objeto de tipo ``S`` con información de
+ tipo.
+
+ .. aafig::
+ :scale: 110
+
+ | |
+ +------------------------ 256 bytes -----------------------------+
+ | |
+
+ +----------------------------------+-----------------------+-----+
+ | | | |
+ | Objeto | Desperdicio | Ptr |
+ | | | |
+ +----------------------------------+-----------------------+-----+
+
+ | | | |
+ +------------ 144 bytes -----------+------ 108 bytes ------+- 4 -+
+ | | | |
+
+Un problema evidente de este esquema es que si el tamaño de un objeto se
+aproxima mucho al tamaño de bloque (difiere en menos de una palabra), el
+objeto ocupará el doble de memoria.
+
+El algoritmo de marcado se cambia de la siguiente forma::
+
+ // Agregado
+ global conservative_scan = [1, 1, 0]
+
+ // Agregado
+ function must_scan_word(pos, bits) is
+ return bits[pos / BITS_PER_WORD] & (1 << (pos % BITS_PER_WORD))
+
+ function mark_range(begin, end, ptrmap) is // Modificado
+ number_of_words_in_type = ptrmap[0] // Agregado
+ size_t* scan_bits = ptrmap + 1 // Agregado
+ pointer = begin
+ while pointer < end
+ foreach word_pos in 0..number_of_words_in_type //
+ if not must_scan_word(n, scan_bits) // Agregado
+ continue //
+ [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 += number_of_words_in_type // Modificado
+
+ 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 // obj grande //
+ begin = cast(byte*) page //
+ end = find_big_object_end(pool, page) //
+ else // objeto pequeño //
+ begin = block.begin //
+ end = block.end // Modificado
+ ptrmap = global conservative_scan //
+ if NO_SCAN not in block.attrs //
+ end -= size_t.sizeof //
+ ptrmap = cast(size_t*) *end //
+ mark_range(begin, end, ptrmap) //
+
+ function mark_static_data() is
+ mark_range(static_data.begin, static_data.end,
+ global conservative_scan) // Agregado
+
+ function mark_stacks() is
+ foreach thread in threads
+ mark_range(thread.stack.begin, thread.stack.end,
+ global conservative_scan) // Agregado
+
+ function mark_user_roots() is
+ foreach root_range in user_roots
+ mark_range(root_range.begin, root_range.end,
+ global conservative_scan) // Agregado
+
+Las funciones de asignación de memoria se modifican de forma similar, para
+guardar el puntero a la información de tipos. Esta implementación utiliza solo
+la información sobre que palabras hay que tratar como punteros (deben ser
+escaneadas); la información sobre qué palabras son efectivamente punteros no
+se utiliza ya que no se mueven celdas.
+
+El algoritmo sigue siendo correcto, puesto que solamente se dejan de escanear
+palabras que el compilador sabe que no pueden ser punteros. Si bien el
+lenguaje permite almacenar punteros en una variable que no lo sea, esto es
+comportamiento indefinido por lo tanto un programa que lo hace no es
+considerado correcto, por lo cual el recolector tampoco debe ser correcto en
+esas circunstancias.
+
+Cabe destacar que la información de tipos solo se provee para objetos
+almacenados en el *heap*, el área de memoria estática, registros del
+procesador y la pila de todos los hilos siguen siendo escaneados de forma
+completamente conservativa. Se puede forzar el escaneo puramente conservativo
+utilizando la opción ``conservative`` (ver :ref:`sol_config_spec`).
+
+
+.. _sol_fork:
+
+Marcado concurrente
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Finalmente se procede al objetivo primario de este trabajo, hacer que la fase
+más costosa del recolector (el marcado) pueda correr de manera concurrente con
+el *mutator*, con el objeto principal de disminuir el tiempo de pausa.
+
+Cabe aclarar, una vez más, que si bien los recolectores concurrentes buscan
+disminuir solo el tiempo de *stop-the-world*, en este caso es también
+fundamental disminuir el tiempo máximo que está tomado el *lock* global, dado
+que ese tiempo puede convertirse en una pausa para todos los threads que
+requieran servicios del recolector.
+
+Se decide basar la implementación en el *paper* "Non-intrusive Cloning Garbage
+Collector with Stock Operating System Support" [RODR97]_ por las siguientes
+razones principales:
+
+* Su implementación encaja de forma bastante natural con el diseño del
+ recolector actual, por lo que requiere pocos cambios, lo que hace más
+ factible su aceptación.
+* Está basado en la llamada al sistema :manpage:`fork(2)`, que no solo está
+ muy bien soportada (y de manera muy eficiente) en Linux_, debe estar
+ soportada en cualquier sistema operativo :term:`POSIX`.
+* No necesita instrumentar el código incluyendo barreras de memoria para
+ informar al recolector cuando cambia el grafo de conectividad. Este es un
+ aspecto fundamental, dada la filosofía de D_ de no pagar el precio de cosas
+ que no se usan. La penalización en la eficiencia solo se paga cuando corre
+ el recolector. Este aspecto también es crítico a la hora de evaluar la
+ aceptación de la solución por parte de la comunidad.
+* Dada su sencillez general, no es difícil ofrecer el algoritmo concurrente
+ como una opción, de manera que el usuario pueda optar por usarlo o no.
+
+Llamada al sistema *fork*
+^^^^^^^^^^^^^^^^^^^^^^^^^
+El término *fork* proviene del inglés y significa *tenedor* de manera textual,
+pero se lo utiliza como analogía de una bifurcación. La operación crea una
+copia (llamada *hijo*) del proceso que la ejecuta (llamado *padre*).
+
+El punto más importante es que se crea un espacio de direcciones de memoria
+separado para el proceso hijo y una copia exacta de todos los segmentos de
+memoria del proceso padre. Es por esto que cualquier modificación que se haga
+en el proceso padre, no se refleja en el proceso hijo (y viceversa), a menos
+que la memoria sea compartida entre los procesos de forma explícita.
+
+Esto, sin embargo, no significa que la memoria física sea realmente duplicada;
+en general todos los sistemas operativos modernos (como Linux_) utilizan una
+técnica llamada *copy-on-write* (*copiar-al-escribir* en castellano) que
+retrasa la copia de memoria hasta que alguno de los dos procesos escribe en un
+segmento. Recién en ese momento el sistema operativo realiza la copia de **ese
+segmento solamente**. Es por esto que la operación puede ser muy eficiente,
+y la copia de memoria es proporcional a la cantidad de cambios que hayan.
+
+:manpage:`fork(2)` tiene otra propiedad importante de mencionar: detiene todos
+los hilos de ejecución en el proceso hijo. Es decir, el proceso hijo se crear
+con un solo hilo (el hilo que ejecutó la operación de :manpage:`fork(2)`).
+
+Algoritmo
+^^^^^^^^^
+Lo que propone el algoritmo es muy sencillo, utilizar la llamada al sistema
+:manpage:`fork(2)` para crear una *fotografía* de la memoria del proceso en un
+nuevo proceso. En el proceso padre sigue corriendo el *mutator* y en el
+proceso hijo se corre la fase de marcado. El *mutator* puede modificar el
+grafo de conectividad pero los cambios quedan aislados el hijo (el marcado),
+que tiene una visión consistente e inmutable de la memoria. El sistema
+operativo duplica las páginas que modifica el padre bajo demanda, por lo tanto
+la cantidad de memoria física realmente copiada es proporcional a la cantidad
+y dispersión de los cambios que haga el *mutator*.
+
+La corrección del algoritmo se mantiene gracias a que la siguiente invariante
+se preserva:
+
+ Cuando una celda se convierte en basura, permanece como basura hasta ser
+ reciclada por el recolector.
+
+Es decir, el *mutator* no puede *resucitar* una celda *muerta* y esta
+invariante se mantiene al correr la fase de marcado sobre una vista inmutable
+de la memoria. El único efecto introducido es que el algoritmo toma una
+aproximación más conservativa. Es decir, lo que sí puede pasar es que una
+celda que pasó a estar *muerta* una vez que la fase de marcado se inició, pero
+antes de que ésta termine, la celda no se reciclará hasta la próxima
+recolección, dado que este algoritmo no incluye una comunicación entre
+*mutator* y recolector para notificar cambios en el grafo de conectividad.
+Pero esto no afecta la corrección del algoritmo, ya que un recolector es
+correcto cuando nunca recicla celdas *vivas*.
+
+La única comunicación necesaria entre el *mutator* y el recolector son los
+bits de marcado (ver :ref:`dgc_impl`), dado que la fase de barrido debe correr
+en el proceso padre. No es necesaria ningún tipo de sincronización entre
+*mutator* y recolector más allá de que uno espera a que el otro finalice.
+
+Además de almacenar el conjunto de bits ``mark`` en memoria compartida entre
+el proceso padre e hijo (necesario para la fase de barrido), las
+modificaciones necesarias para hacer la fase de marcado concurrente son las
+siguientes [#solforkerr]_::
+
+ function collect() is
+ stop_the_world()
+ child_pid = fork()
+ fflush(null) // evita que se duplique la salida de los FILE* abiertos
+ if child_pid is 0 // proceso hijo
+ mark_phase()
+ exit(0) // termina el proceso hijo
+ // proceso padre
+ start_the_world()
+ wait(child_pid)
+ sweep()
+
+ function mark_phase() is
+ global more_to_scan = false
+ // Borrado: stop_the_world()
+ clear_mark_scan_bits()
+ mark_free_lists()
+ mark_static_data()
+ push_registers_into_stack()
+ thread_self.stack.end = get_stack_top()
+ mark_stacks()
+ pop_registers_from_stack()
+ mark_user_roots()
+ mark_heap()
+ // Borrado: start_the_world()
+
+Como se puede observar, el cambio es extremadamente sencillo. Sigue siendo
+necesario un tiempo mínimo de pausa (básicamente el tiempo que tarda la
+llamada al sistema operativo :manpage:`fork(2)`) para guardar una vista
+consistente de los registros del CPU y *stacks* de los hilos. Si bien el
+conjunto de bits ``mark`` es compartido por el proceso padre e hijo dado que
+es necesario para *comunicar* las fases de marcado y barrido, cabe notar que
+nunca son utilizados de forma concurrente (la fase de barrido espera que la
+fase de marcado termine antes de usar dichos bits), por lo tanto no necesitan
+ningún tipo de sincronización y nunca habrá más de una recolección en proceso
+debido al *lock* global del recolector.
+
+A pesar de que con estos cambios el recolector técnicamente corre de forma
+concurrente, se puede apreciar que para un programa con un solo hilo el
+tiempo máximo de pausa seguirá siendo muy grande, incluso más grande que antes
+dado el trabajo extra que impone crear un nuevo proceso y duplicar las páginas
+de memoria modificadas. Lo mismo le pasará a cualquier hilo que necesite hacer
+uso del recolector mientras hay una recolección en proceso, debido al *lock*
+global.
+
+Para bajar este tiempo de pausa se experimenta con dos nuevas mejoras, que se
+describen a continuación, cuyo objetivo es correr la fase de marcado de forma
+concurrente a **todos** los hilos, incluyendo el hilo que la disparó.
+
+.. [#solforkerr] Se omite el manejo de errores y la activación/desactivación
+ del marcado concurrente a través de opciones del recolector para facilitar
+ la comprensión del algoritmo y los cambios realizados. Si devuelve con
+ error la llamada a ``fork()`` o ``waitpid()``, se vuelve al esquema
+ *stop-the-world* como si se hubiera desactivado el marcado concurrente
+ utilizando la opción del recolector ``fork=0``.
+
+
+.. _sol_eager_alloc:
+
+Creación ansiosa de *pools*
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Esta mejora, que puede ser controlada a través de la opción ``eager_alloc``
+(ver :ref:`sol_config_spec`), consiste en crear un nuevo *pool* cuando un
+pedido de memoria no puede ser satisfecho, justo después de lanzar la
+recolección. Esto permite al recolector satisfacer la petición de memoria
+inmediatamente, corriendo la fase de marcado de forma realmente concurrente,
+incluso para programas con un solo hilo o programas cuyos hilos usan
+frecuentemente servicios del recolector. El precio a pagar es un mayor uso de
+memoria de forma temporal (y el trabajo extra de crear y eliminar *pools* más
+frecuentemente), pero es esperable que el tiempo máximo de pausa **real** se
+vea drásticamente disminuido.
+
+A simple vista las modificaciones necesarias para su implementación parecieran
+ser las siguientes::
+
+ // Agregado
+ global mark_pid = 0
+
+ // Agregado
+ function mark_is_running() is
+ return global mark_pid != 0
+
+ function collect() is
+ if mark_is_running() //
+ finished = try_wait(global mark_pid) //
+ if finished // Agregado
+ mark_pid = 0 //
+ sweep() //
+ return //
+ stop_the_world()
+ child_pid = fork()
+ fflush(null)
+ if child_pid is 0 // proceso hijo
+ mark_phase()
+ exit(0)
+ // proceso padre
+ start_the_world()
+ // Borrado: wait(child_pid)
+ global mark_pid = child_pid
+
+Sin embargo con sólo estas modificaciones el algoritmo deja de ser correcto,
+ya que tres cosas problemáticas pueden suceder:
+
+1. Puede llamarse a la función ``minimize()`` mientras hay una fase de marcado
+ corriendo en paralelo. Esto puede provocar que se libere un *pool* mientras
+ se lo está usando en la fase de marcado, lo que no sería un problema
+ (porque el proceso de marcado tiene una copia) si no fuera porque los bits
+ de marcado, que son compartidos por los procesos, se liberan con el *pool*.
+2. Si un bloque libre es asignado después de que la fase de marcado comienza,
+ pero antes de que termine, ese bloque será barrido dado la función
+ ``rebuild_free_lists()`` puede reciclar páginas si todos sus bloques tienen
+ el bit ``freebits`` activo (ver :ref:`dgc_algo_sweep`).
+3. El *pool* creado ansiosamente, tendrá sus bits de marcado sin activar, por
+ lo que en la fase de barrido será interpretado como memoria libre, incluso
+ cuando puedan estar siendo utilizados por el *mutator*.
+
+El punto 1 sencillamente hace que el programa finalice con una violación de
+segmento (en el mejor caso) y 2 y 3 pueden desembocar en la liberación de una
+celda alcanzable por el *mutator*.
+
+El punto 1 se resuelve a través de la siguiente modificación::
+
+ function minimize() is
+ if mark_is_running() // Agregado
+ return //
+ 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)
+
+La resolución del punto 2 es un poco más laboriosa, ya que hay que mantener
+actualizado los ``freebits``, de forma que las celdas asignadas después de
+empezar la fase de marcado no sean barridas por tener ese bit activo::
+
+ 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.free = true // Agregado
+ pages[0].block_size = PAGE
+ foreach page in pages[1..end]
+ page.block_size = CONTINUATION
+ return pages[0]
+
+ 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
+ block.free = true // Agregado
+ free_lists[page.block_size].link(block)
+
+ function mark_phase() is
+ global more_to_scan = false
+ // Borrado: clear_mark_scan_bits()
+ // Borrado: mark_free_lists()
+ clear_scan_bits() // Agregado
+ mark_free() //
+ mark_static_data()
+ push_registers_into_stack()
+ thread_self.stack.end = get_stack_top()
+ mark_stacks()
+ pop_registers_from_stack()
+ mark_user_roots()
+ mark_heap()
+
+ // Agregado
+ function clear_scan_bits() is
+ // La implementación real limpia los bits en bloques de forma eficiente
+ foreach pool in heap
+ foreach page in pool
+ foreach block in page
+ block.scan = false
+
+ // Agregado
+ function mark_free() is
+ // La implementación real copia los bits en bloques de forma eficiente
+ foreach pool in heap
+ foreach page in pool
+ foreach block in page
+ block.mark = block.free
+
+ function free_big_object(pool, page) is
+ pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
+ do
+ page.block_size = FREE
+ page.block.free = true // Agregado
+ page = cast(byte*) page + PAGE_SIZE
+ while page < pool_end and page.block_size is CONTINUATION
+
+ 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
+ block.free = false // Agregado
+ return cast(void*) block
+
+ 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)
+ foreach page in pool
+ page.block_size = FREE
+ foreach block in page //
+ block.free = true // Agregado
+ block.mark = true //
+ return pool
+
+Finalmente, el punto número tres puede ser solucionado con el siguiente
+pequeño cambio::
+
+ 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)
+ foreach page in pool
+ page.block_size = FREE
+ foreach block in page // Agregado
+ block.mark = true //
+ return pool
+
+La solución es conservativa porque, por un lado evita la liberación de *pools*
+mientras haya una recolección en curso (lo que puede hacer que el consumo de
+memoria sea un poco mayor al requerido) y por otro asegura que, como se
+mencionó anteriormente, los cambios hechos al grafo de conectividad luego de
+iniciar la fase de marcado y antes de que ésta termine, no serán detectados
+por el recolector hasta la próxima recolección (marcar todos los bloques de
+un nuevo *pool* como el bit ``mark`` asegura que que la memoria no sea
+recolectada por la fase de barrido cuando termine el marcado).
+
+Estas modificaciones son las que hacen que el algoritmo siga siendo correcto,
+asegurando que no se van a liberar celdas *vivas* (a expensas de diferir la
+liberación de algunas celdas *muertas* por algún tiempo).
+
+
+.. _sol_early_collect:
+
+Recolección temprana
+^^^^^^^^^^^^^^^^^^^^
+Esta mejora, que puede ser controlada a través de la opción ``early_collect``
+(ver :ref:`sol_config_spec`), consiste en lanzar una recolección preventiva,
+antes de que una petición de memoria falle. El momento en que se lanza la
+recolección es controlado por la opción ``min_free`` (ver :ref:`sol_ocup`).
+
+De esta forma también puede correr de forma realmente concurrente el *mutator*
+y el recolector, al menos hasta que se acabe la memoria, en cuyo caso, a menos
+que la opción ``eager_alloc`` (ver :ref:`sol_eager_alloc`) también esté
+activada, se deberá esperar a que la fase de marcado termine para recuperar
+memoria en la fase de barrido.
+
+Para facilitar la comprensión de esta mejora se muestran sólo los cambios
+necesarios si no se utiliza la opción ``eager_alloc``::
+
+ function collect(early = false) is // Modificado
+ if mark_is_running()
+ finished = try_wait(global mark_pid)
+ if finished
+ mark_pid = 0
+ sweep()
+ return //
+ else if early // Agregado
+ return //
+ stop_the_world()
+ child_pid = fork()
+ fflush(null)
+ if child_pid is 0 // proceso hijo
+ mark_phase()
+ exit(0)
+ // proceso padre
+ start_the_world()
+ if early //
+ global mark_pid = child_pid //
+ else // Agregado
+ wait(child_pid) //
+ sweep() //
+
+ // Agregado
+ function early_collect() is
+ if not collect_in_progress() and (percent_free < min_free)
+ collect(true)
+
+ 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
+ early_collect() // Agregado
+ return cast(void*) block
+
+Es de esperarse que cuando no está activa la opción ``eager_alloc`` por un
+lado el tiempo de pausa máximo no sea tan chico como cuando sí lo está (dado
+que si la recolección no se lanza de forma suficientemente temprana se va
+a tener que esperar que la fase de marcado termine), y por otro que se hagan
+más recolecciones de lo necesario (cuando pasa lo contrario, se recolecta más
+temprano de lo que se debería). Sin embargo, también es de esperarse que el
+consumo de memoria sea un poco menor que al usar la opción ``eager_alloc``.
+
+En cuanto a la corrección del algoritmo, éste solamente presenta los problemas
+número 1 y 2 mencionados en :ref:`sol_eager_alloc`, dado que jamás se crean
+nuevos *pools* y la solución es la ya presentada, por lo tanto el algoritmo
+sigue siendo correcto con los cuidados pertinentes.
projects / z.facultad / 75.00 / informe.git / commitdiff