sweep()
rebuild_free_lists()
-El barrido se realiza con una pasada por sobre todo el heap
+El barrido se realiza con una pasada por sobre todo el *heap* de la siguiente
+manera::
+
+ function sweep() is
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size <= PAGE // saltea FREE y CONTINUATION
+ foreach block in page
+ if block.mark is false
+ if block.final is true
+ finalize(block)
+ block.free = true
+ block.final = false
+ block.noscan = false
+ if page.block_size is PAGE // objeto grande
+ free_big_object(pool, page)
+
+Como se observa, se recorre todo el *heap* en busca de bloques y páginas
+libres. Los bloques libres son marcados con el atributo ``free`` y las páginas
+libres son marcadas con el tamaño de bloque simbólico ``FREE``. Para los
+objetos grandes se marcan todas las páginas que utilizaban como ``FREE``::
+
+ function free_big_object(pool, page) is
+ pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
+ do
+ page = cast(byte*) page + PAGE_SIZE
+ page.block_size = FREE
+ while page.block_size is CONTINUATION and page < pool_end
+
+Además, los bloques que tienen en atributo ``final`` son finalizados llamando
+a la función ``finalize()``. Esta función es un servicio que provee la
+biblioteca *runtime* y en última instancia llama al destructor del objeto
+almacenado en el bloque a liberar.
+
+Una vez marcados todos los bloques y páginas como libre, se procede
+a reconstruir las listas de libres. En el proceso buscan las páginas que
+tengan todos los bloques libres para marcar la página completa como libre (de
+manera que pueda utilizarse para albergar otro tamaño de bloque u objetos
+grandes de ser necesario)::
+
+ function rebuild_free_lists() is
+ foreach free_list in heap
+ free_list.clear()
+ foreach pool in heap
+ foreach page in pool
+ if page.block_size < PAGE // objetos pequeños
+ if is_page_free(page)
+ page.block_size = FREE
+ else
+ foreach block in page
+ if block.free is true
+ free_lists[page.block_size].link(block)
+
+Esta reorganización de listas libres además mejoran la localidad de
+referencia y previenen la fragmentación. La localidad de referencia se ve
+mojorada debido a que asignaciones de memoria proximas en el tiempo serán
+también próximas en espacio porque pertenecerán a la misma página (al menos si
+las asignaciones son todas del mismo tamaño). La fragmentación se minimiza por
+el mismo efecto, primero se asignarán todos los bloques de la misma página.
+
+A continuación se presenta la implementación de una de las funciones
+suplementarias de la fase de barrido::
+
+ function is_page_free(page) is
+ foreach block in page
+ if block.free is false
+ return false
+ return true
+
+Las demás funciones suplementarias pertenecen a la manipulación de listas
+libres que no son más que operaciones sobre una lista simplemente enlazada. En
+la sección :ref:`dgc_impl` se verá con más detalles como las implementa el
+recolector actual.
+
+
+.. _dgc_algo_alloc:
+
+Asignación de memoria
+^^^^^^^^^^^^^^^^^^^^^
+La asignación de memoria del recolector es relativamente compleja, excepto
+cuando se asgina un objeto pequeño y ya existe algún bloque con el tamaño
+preciso en la lista de libres. Para el resto de los casos la cantidad de
+trabajo que debe hacer el recolector para asignar la memoria es considerable.
+
+El algoritmo de asignación de memoria se puede resumir así::
+
+ 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
+ return cast(void*) block
+
+La función ``find_block_size()`` sencillamente busca el tamaño de bloque se
+mejor se ajuste al tamaño solicitado (es decir, el bloque más pequeño lo
+suficientemente grande como para poder almacenar el tamaño solicitado). Una
+vez más el algoritmo distingue objetos grandes de pequeños. Los pequeños se
+asginan de las siguiente manera::
+
+ function new_small(block_size) is
+ block = find_block_with_size(block_size)
+ if block is null
+ collect()
+ block = find_block_with_size(block_size)
+ if block is null
+ new_pool()
+ block = find_block_with_size(block_size)
+ return null
+ return block
+
+Se intenta reiteradas veces conseguir un bloque del tamaño correcto libre,
+realizando diferentes acciones si no se tiene éxito. Primero se intenta hacer
+una :ref:`recolección <dgc_algo_collect>` y si no se puede encontrar
+suficiente espacio luego de ella se intenta crear un nuevo *pool* de memoria
+pidiendo memoria al *low level allocator* (el sistema operativo generalmente).
+
+Para intentar buscar un bloque de memoria libre se realiza lo siguiente::
+
+ function find_block_with_size(block_size) is
+ block = free_lists[block_size].pop_first()
+ if block is null
+ assign_page(block_size)
+ block = free_lists[block_size].pop_first()
+ return block
+
+Si no se puede obtener un bloque de la lista de libres correspondiente, se
+busca asignar una página libre al tamaño de bloque deseado de forma de
+*alimentar* la lista de libres con dicho tamaño::
+
+ 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
+ free_lists[page.block_size].link(block)
+
+Cuando todo ello falla, el último recurso consiste en pedir memoria al sistema
+operativo, creando un nuevo *pool*::
+
+ 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)
+ return pool
+
+Se recuerda que la función ``alloc()`` es un :ref:`servicio
+<gc_intro_services>` provisto por el *low level allocator* y en la
+implementación actual de D_ en general es el sistema operativo (aunque
+opcionalmente puede utilizarse la biblioteca estándar de C, que a su vez
+utiliza el sistema operativo).
+
+Cualquier error en estas funciones es propagado y en última instancia, cuando
+todo falla, la función ``new()`` termina lanzando una excepción indicando que
+se agotó la memoria.
+
+Si el tamaño de bloque necesario para cumplir con la asignación de memoria es
+de una página, entonces se utiliza otro algoritmo para alocar un objeto
+grande::
+
+ 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_size = PAGE
+ foreach page in pages[1..end]
+ page.block_size = CONTINUATION
+ return pages[0]
+
+De forma similar a la asignación de objetos pequeños, se intenta encontrar una
+serie de páginas contíguas, dentro de un mismo *pool*, suficientes para
+almacenar el tamaño requerido y si esto falla, se realizan diferentes pasos
+y se vuelve a intentar. Puede observarse que, a diferencia de la asignación de
+objetos pequeños, si luego de la recolección no se pudo encontrar lugar
+suficiente, se trata de minimizar el uso de memoria física utilizando la
+siguiente función, que devuelve al *low level allocator* los *pools*
+completamente libres::
+
+ function minimize() is
+ 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)
+
+Volviendo a la función ``new_big()``, para hallar una serie de páginas
+contíguas se utiliza el siguiente algoritmo::
+
+ function find_pages(number_of_pages) is
+ foreach pool in heap
+ pages = assign_pages(pool, number_of_pages)
+ if pages
+ return pages
+ return null
+
+Como se dijo, las páginas deben estar contenidas en un mismo *pool* (para
+tener la garantía de que sean contíguas), por lo tanto se busca *pool* por
+*pool* dicha cantidad de páginas libres consecutivas a través del siguiente
+algoritmo::
+
+ function assign_pages(pool, number_of_pages) is
+ pages_found = 0
+ first_page = null
+ foreach page in pool
+ if page.block_size is FREE
+ if pages_found is 0
+ pages_found = 1
+ first_page = page
+ else
+ pages_found = pages_found + 1
+ if pages_found is number_of_pages
+ return [first_page .. page]
+ else
+ pages_found = 0
+ first_page = null
+ return null
+
+Una vez más, cuando todo ello falla (incluso luego de una recolección), se
+intenta alocar un nuevo *pool*, esta vez con una cantidad de páginas
+suficientes como para almacenar el objeto grande y si esto falla el error se
+propaga hasta la función ``new()`` que lanza una excepción.
projects / z.facultad / 75.00 / informe.git / blobdiff