+
+.. _dgc_algo:
+
+Algoritmos del recolector
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+A continuación se explica como provee el recolector actual de D_ los servicios
+básicos que debe proveer cualquier recolector, como se presentó en la sección
+:ref:`gc_intro_services`.
+
+Cabe aclarar que se presenta una versión simplificada del algoritmo, o más
+precisamente, de la implementación del algoritmo, ya que no se exponen en esta
+sección muchas optimizaciones que harían muy compleja la tarea de explicar
+como funciona conceptualmente. En la siguiente sección, :ref:`dgc_impl`, se
+darán más detalles sobre las optimizaciones importantes y diferencias con el
+algoritmo aquí presentado, junto con detalles sobre como se implementa la
+organización del *heap* que se explicó en la sección anterior.
+
+
+.. _dgc_algo_collect:
+
+Recolección
+^^^^^^^^^^^
+A grandes razgos el algoritmo de recolección puede resumirse de las dos fases
+básicas de cualquier algoritmo de :ref:`marcado y barrido <gc_mark_sweep>`::
+
+ function collect() is
+ mark_phase()
+ sweep_phase()
+
+
+.. _dgc_algo_mark:
+
+Fase de marcado
+^^^^^^^^^^^^^^^
+Esta fase consiste de varios pasos, que pueden resumirse en el siguiente
+algoritmo::
+
+ function mark_phase() is
+ more_to_scan = false
+ stop_the_world()
+ clear_mark_scan_bits()
+ mark_free_lists()
+ mark_static_data()
+ push_registers_into_stack()
+ mark_stacks()
+ mark_user_roots()
+ mark_heap()
+ start_the_world()
+
+La variable **global** ``more_to_scan`` indica al algoritmo iterativo cuando
+debe finalizar: la función ``mark()`` (que veremos más adelante) lo pone en
+``true`` cuando una nueva celda debe ser visitada, por lo tanto la iteración
+se interrumpe cuando no hay más celdas por visitar.
+
+Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente
+pausan y reanudan todos los hilos respectivamente::
+
+ function stop_the_world() is
+ foreach thread in threads
+ thread.pause()
+
+ function start_the_world() is
+ foreach thread in threads
+ thread.resume()
+
+La función ``clear_mark_scan_bits()`` se encarga de resetear todos los
+atributos *mark* y *scan* de cada bloque del *heap*::
+
+ function clear_mark_scan_bits() is
+ foreach pool in heap
+ foreach page in pool
+ foreach block in page
+ block.mark = false
+ block.scan = false
+
+La función ``mark_free_lists()`` por su parte se encarga de activar el bit
+*mark* de todos los bloques de las listas de libres de manera de que la fase
+de marcado (que es iterativa y realiza varias pasadas sobre **todo** el
+*heap*, incluyendo las celdas libres) no visite las celdas libres perdiendo
+tiempo sin sentido y potencialmente manteniendo *vivas* celdas que en
+realdidad son *basura* (falsos positivos)::
+
+ function mark_free_lists() is
+ foreach free_list in heap
+ foreach block in free_list
+ block.mark = true
+ block.free = true
+
+Notar que los bloques libres quedan entonces marcados aunque sean *basura* por
+definición. Para evitar que en la etapa de barrido se tomen estos bloques como
+celdas vivas, a todos los bloques en la lista de libres también se los marca
+con el bit *free*, así el barrido puede tomar como *basura* estos bloques
+aunque estén marcados.
+
+El *root set* está compuesto por el área de memoria estática (variables
+globales), los *stacks* de todos los hilos y los registros del procesador.
+Primero se marca el área de memoria estática de manera :ref:`conservativa
+<gc_conserv>` (es decir, tomando cada *word* como si fuera un puntero)::
+
+ function mark_static_data() is
+ foreach word in static_data
+ pointer = cast(void*) word
+ mark(pointer)
+
+Para poder tomar los registros como parte del *root set* primero se apilan
+en el *stack* a través de la función::
+
+ function push_registers_into_stack() is
+ foreach register in registers
+ push(register)
+
+Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos
+los threads para terminar de marcar el *root set*::
+
+ function mark_stacks() is
+ foreach thread in threads
+ foreach word in thread.stack
+ pointer = cast(void*) word
+ mark(pointer)
+
+Dado que D_ soporta manejo de memoria manual al mismo tiempo que memoria
+automática, es posible que existan celdas de memoria que no estén en el *root
+set* convencional ni en el *heap* del recolector. Para evitar que se libere
+alguna celda que estaba siendo referenciada desde memoria administrada por el
+usuario, éste debe informarle al recolector sobre la existencia de estoas
+nuevas raíces. Es por esto que para concluir el marcado del *root set*
+completo se procede a marcar las raíces definidas por el usuario::
+
+ function mark_user_roots() is
+ foreach pointer in user_roots
+ mark(pointer)
+
+El algoritmo de marcado no es recursivo sino iterativo por lo tanto al marcar
+una celda (o bloque) no se siguen sus *hijas*, solo se activa el bit de *scan*
+(a menos que la celda no contenga punteros, es decir, tenga el bit *noscan*)::
+
+ function mark(pointer) is
+ [pool, page, block] = find_block(pointer)
+ if block is not null and block.mark is false
+ block.mark = true
+ if block.noscan is false
+ block.scan = true
+ more_to_scan = true
+
+Por lo tanto en este punto, tenemos todas las celdas inmediatamente
+alcanzables desde el *root set* marcadas y con el bit *scan* activado si la
+celda puede contener punteros. Por lo tanto solo resta marcar (nuevamente de
+forma conservativa) iterativamente todo el *heap* hasta que no hayan más
+celdas para visitar (con el bit *scan* activo)::
+
+ function mark_heap() is
+ while more_to_scan
+ more_to_scan = false
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size <= PAGE // saltea FREE y CONTINUATION
+ foreach block in page
+ if block.scan is true
+ block.scan = false
+ if page.block_size is PAGE // objeto grande
+ start = cast(byte*) page
+ end = find_big_object_end(pool, page)
+ foreach word in start..end
+ pointer = cast(void*) word
+ mark(pointer)
+ else // objeto pequeño
+ foreach word in block
+ pointer = cast(void*) word
+ mark(pointer)
+
+Aquí puede verse, con un poco de esfuerzo, la utilización de la
+:ref:`abtracción tricolor <gc_intro_tricolor>`: todas las celdas alcanzables
+desde el *root set* son pintadas de *gris* (tienen los bits *mark* y *scan*
+activados), excepto aquellas celdas atómicas (es decir, que se sabe que no
+tienen punteros) que son marcadas directamente de *negro*. Luego se van
+obteniendo celdas del conjunto de las *grises*, se las pinta de *negro* (es
+decir, se desactiva el big *scan*) y se pintan todas sus *hijas* de *gris* (o
+*negro* directamente si no tienen punteros). Este procedimiento se repite
+mientras el conjunto de celdas *grises* no sea vacío (es decir, que
+``more_to_scan`` sea ``true``).
+
+A continuación se presenta la implementación de las funciones suplementarias
+utilizadas en la fase de marcado::
+
+ function find_big_object_end(pool, page) is
+ pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
+ do
+ page = cast(byte*) page + PAGE_SIZE
+ while page.block_size is CONTINUATION and page < pool_end
+ return page
+
+ function find_block(pointer) is
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size is PAGE
+ big_object_start = cast(byte*) page
+ big_object_end = find_big_object_end(pool, page)
+ if big_object_start <= pointer < big_object_end
+ return [pool, page, big_object_start]
+ else if page.bloc_size < PAGE
+ foreach block in page
+ block_start = cast(byte*) block
+ block_end = block_start + page.block_size
+ if block_start <= pointer < block_end
+ return [pool, page, block_start]
+ return [null, null, null]
+
+Cabe destacar que la función ``find_block()`` devuelve el pool, la página y el
+comienzo del bloque al que apunta el puntero, es decir, soporta punteros
+*interiores*.
+
+
+.. _dgc_algo_sweep:
+
+Fase de barrido
+^^^^^^^^^^^^^^^
+Esta fase es considerablemente más sencilla que el marcado; el algoritmo puede
+dividirse en dos pasos básicos::
+
+ function sweep_phase() is
+ sweep()
+ rebuild_free_lists()
+
+El barrido se realiza con una pasada por sobre todo el heap
+
+
+
+.. _dgc_impl:
+
+Detalles de implementación
projects / z.facultad / 75.00 / informe.git / blobdiff