No tienes permitido ver los links.
Registrarse o Entrar a mi cuenta
Hola buenas, soy Desmon y soy un usuario nuevo en este foro, no se si incumpla alguna de las reglas del foro en este post pero si así que alguien me lo reporte para corregirlo cuanto antes.
Bueno, viniendo a lo que vengo. Estaba o mejor dicho, quería diseñar un allocator de memoria con GC(garbage collection), cual es la salsa del asunto, bueno, quiero hacerlo lo mas eficiente posible, multiplataforma, funcional, con protecciones de memoria y de acceso y quería hacerlo usando C puro, usando las libC lo menos posible y sus cabeceras(esto implica implementar las funciones necesarias para obtener largos de cadenas, imprimir texto, copiar bloques de memoria y etc).
Hoy lo que vengo a preguntar mas concretamente es si conocen algoritmos eficientes para la tarea de diseñar tal pieza de software, o si me recomiendan alguno en especifico.
Necesito uno o varios algoritmos para poder reorganizar la memoria si hay bloques liberados, o que hacer cuando hay memoria liberada de por medio y hay que reorganizar todo para poder hacer buen uso de ella.
Algoritmos para la recolección de basura, pues si, he visto algoritmos y tal, pero no el como se podría crear una implementación como tal por que me falta documentación, información o etc. Si alguien tiene DOC de haber realizado un proyecto similar, o que tiene algún consejo o etc, cualquier cosa es bien venida.
Por ahora he visto varias funciones para reservar memoria, una de ellas es "NtAllocateVirtualMemory" en el caso de Windows, esta la podemos situar en ntdll.dll, lo que estoy haciendo es cargarla en run time si se encuentra en Windows.
Yo estoy haciendo uso de una subrutina constructora que se llama antes que el main sin que el programador convencional lo sepa ni tenga que ser consciente de ello:
primero voy a decir que la macro __DEBUG__ solo la defino a la hora de compilar con -D__DEBUG__ para que pueda ir viendo la información de todo mientras se corre la aplicación que hace uso de esta. La defunción de ntdll esta definido en mi header MemoryAddressBase.h como "HMODULE ntdll;", y el pedazo de codigo que acabáis de ver se encuentra en MemoryAddressBase.c.
La declaración de la función __init1__ se encuentra en el header principal como:
al igual la rutina destructora. Volviendo a nuestra subrutina constructora, usamos LoadLibraryA, una función de la WinApi que carga ntdll.dll en tiempo de ejecución, como es LoadLibraryA se esta usando la versión ANSI de la función. Si al cargarla da algun error ntdll queda con valor nulo y se ejecuta un ROW_ERROR_RET se este definiendo __DEBUG__ o no. TROW_ERROR_RET se define en el header "ErrorAllocator.h" de la siguiente manera:
una simple definición que hace uso de un printf para mostrar el error y un return;. El error ERROR_LOAD_LIB se define en la misma header mediante un enum que podemos ver:
Adicionalmente decir que tenemos una función "printErrorAllocator" que recibe el codigo de error y imprime un mensaje acorde a este:
Volviendo a la función constructora, en el caso de que se use la macro __DEBUG__ usamos GET_LAST_ERROR_WIN que se define en MemoryAddressBase.h de la siguiente manera:
Dicha me permite obtener información mas detallada sobre el error que se produjo al cargar la librería. Prosiguiendo con la subrutina, se obtiene la dirección "NtAllocateVirtualMemory" usando la función GetProcAddress, NtAllocateVirtualMemory y NtAllocateVirtualMemory_t se definen en el header principal de la siguiente manera:
y de igual manera hacemos con "NtFreeVirtualMemory", aquí sus declaraciones:
Esto es en el caso de windows, pero en el caso de linux en un inicio he pensado usar mmap, una syscall que permite al kernel pedir memoria para tratarla como queramos, se podria decir que es la función NtAllocateVirtualMemory para linux.
Se que dicha funcion se puede usar con sus cabeceras, pero no lo quise, en su lugar opte mejor usar Assembly si era posible, entonces primero veamos la declaración de mmap en nuestro header principal como:
y su respectiva declaración para Linux en arquitectura de 32 y 64 bits:
Los lectores atentos habrán visto que hay una ultima directiva #elif al final, hago uso de esta para, en el caso de que no se pueda detectar el tamaño de palabra como 32 o 64bits, usar un comportamiento default donde se usa syscall y __NR_mmap definidas en cabeceras de C para usar mmap sin tener que hacerlo en asm, podría incluir una condicional mas al elif para que se use esta opción si la maquina en la que se esta compilando no es x86, lo que lo haría mas portable en teoría. Por lo demas, la función mmap_syscall es definida con una versión de 32bits donde se usa registros de 32bits (eax, ebx, ...) y la mas conocida interrupción 80h. En el caso de estar compilándose el código en 64bits(-m64), tenemos una versión que usa los registros de 64bits (rax, rbx, ...) y usamos la instrucción syscall exclusiva de maquinas x86 de 64bits en lugar de int.
Ahora, habréis notado que ambas syscall's, la versión de linux y la versión de windows reciben una serie de argumentos, bastante similares en cuanto a su uso, por ejemplo tenemos un argumento para definir la cantidad de memoria que queremos reservar, lo que seria ¿una pagina de memoria quizas? habría que verlo, pero el campo que nos interesa es ULONG Protect en el caso de "NtAllocateVirtualMemory" o "int prot" en el caso de "mmap". Estos campos se usan para lo mismo y es básicamente para definir los permisos que tiene la "sección" de memoria que queremos pedir al kernel. Esto lo podría especificar el programador y para ello, hemos creado un enum que apenas cambia independientemente de la plataforma para especificar los permisos, aqui podemos verlo, y se situa en la header principal:
Cabe mencionar que estos son permisos de PAGINAS y creo que esto es necesario recalcarlo. Si mal no he visto, estos permisos se especifican de igual manera en Linux como en Windows, que es con valores enteros, 0(nada)(-), 1(leer)(r), 2(escribir)(w) y 4(ejecutar)(x). Los mas linuxeros apreciaran que esto es como los valores octales en chmod. Podemos combinar permisos simplemente sumando valores, por ejemplo para tener permisos de lectura y escritura, sumamos el valor 1(leer) con el valor 2(escribir), lo que da el valor 3(leer y escribir pero no ejecutar). De igual manera podemos dar todos los permisos sumando 1(leer), 2(escribir), 4(ejecutar), lo que da como resultado 7(1+2+4=rwx), lo que se corresponde al 7 de cuando ponemos "chmod 777 <file>" por ejemplo.
Ahora, entremos en declaraciones de los bloques de memoria y etc:
Cabe mencionar que aquí el concepto de "bloque" no es mas que una abstracción de una representación de datos guardados en la misma memoria de la pagina, donde alojamos información de los permisos que tiene una "seccion" que pedimos al allocator, lo que vendria siendo en C el puntero que nos retorna malloc, algo similar, solo que nuestro malloc en teoria debería ser mas complejo. Dichos bloques se alojan en tablas, tablas de bloques valga la redundancia y las tablas se alojan en paginas de memoria, podemos tener una o mas tablas de memoria con distintos permisos y distintos bloques a lo largo de nuestro programa. Y claro, como no, decir que una paginas puede tener mas de una tabla, esto va a depende de si la tabla es mas grande que la pagina, en ese caso necesitaremos mas de una pagina para guardar una tabla. Si la tabla es 1/4 de la pagina, pues en una misma pagina puede entrar 4 tablas, entonces aqui debemos hacer un diseño razonablemente inteligente mas adelante.
Prosigamos, cada bloque de memoria tiene un header, una cabecera de bloque para que nos entendamos, y esta la hemos visto ya en la definición de block_memory:
En la cabecera guardaríamos un id de 64bits, aunque estoy pensando en cambiar estos valores de 64bits a datos que cambien entre 32, 64 y etc dependiendo del largo de palabra del procesador. Este ID, es un ID relativo entorno a una tabla, que quiero decir con esto. Pues que puede haber mas de un bloque de memoria que tenga el ID 1, mientras se han tablas diferentes, pero en una misma tabla, solo puede haber un bloque con el mismo ID que identifique a este mismo, sera su DNI en la table. Tambien tenemos un campo para indicar el tamaño del bloque, esto lo hacemos para conocer el offset de cada bloque de memoria, y a lo largo de nuestro allocator no pasarnos escribiendo memoria. is_free seria otro valor que indicaría el espacio libre en el bloque. Si size y is_free tienen el mismo valor podemos deducir que el bloque no tiene nada dentro, esta vacio, o que el bloque tiene un tamaño de 0. El tamaño ocupado lo podríamos obtener mediante una simple resta, que seria size-is_free, eso nos daría el tamaño ya ocupado del bloque. El siguiente miembro es next, que es un puntero de la estructura block_memory donde se especificaría la dirección del siguiente bloque de memoria con su propia cabecera. Hay que decir que esto es similar a una lista enlazada, tal vez agregue el que sea una doble lista enlaza, para eso habría que incluir un mismo puntero al bloque anterior. Otro miembro de la cabecera de bloque es el de PermissionBlock, este es un valor el cual indica los permisos que hay en dicho bloque de memoria, hay que decir que sus permisos no pueden ser superior a los permisos de la tabla, eso quiere decir que si la tabla solo tiene permisos de lectura, no podemos hacer que el bloque tenga permisos de ejecución, sino que además todos los bloques de esta solo tendrán permisos de lectura o ninguno, los permisos pueden ser los mismos o inferiores, pero NUNCA SUPERIORES. Esto lo hacemos como un posible mecanismo de seguridad, cabe mencionar que tendremos que ser nosotros luego el que nos aseguremos que no se violen estos permisos.
Ahora, el bloque de memoria aparte del header, tiene un puntero void donde tiene que ser un puntero que cumpla algunas características, como que tenga el tamaño adecuado(size) y que no invada las direcciones de otros bloques, por que en ese caso estaríamos sobrescribiendo bloques y esto es una falla muy gorda. El miembro addr_memory seria como tal el puntero que el programador usara de forma directa u indirecta para lo que el quiera, como puede ser guardar estructuras o leer archivos entre otros.
Veamos como seria la definicion de table_blocks, o tabla de bloques:
Los comentarios deben hablar por si mismo, pero aun asi os explicare. Como ya hemos mencionado los bloques se alojan en tablas y las tablas en paginas. numbre_blocks es un miembro donde especificamos la cantidad de bloques, podríamos hacer también un campo donde especificar la cantidad de bloques máxima que podemos tener en la tabla. Otro miembro es first y last. El primer mencionado es un puntero al primer bloque de la tabla, y el segundo, es un puntero al ultimo bloque, esto tal vez podemos hacerlo para hacer sorting, o simplemente para conocer como se aloja nuestros bloques en la tabla. Hay que mencionar que el miembro last cambiara cada vez que añadamos un bloque nuevo al final de la tabla, y que first cambiara si el bloque al que apunta es eliminado.
PermissionTable podéis deducir que hace(especificar los permisos de la tabla). Y un puntero importante es next, este al igual que en header, hacer referencia a la siguiente tabla, tal vez también este bien hacer una doble lista enlazada.
Luego tendriamos un registro de tablas donde se guardaria las direcciones de cada tabla, este registro tendria que permitir que se actualice elimando y añadiendo tablas, sin que las demas se vean afectadas, actualmente y posiblemente temporalmente esta definida asi:
Ahora bien, algunas declaraciones de funciones que hay por ahora:
get_info_system es una función que retorna información acerca de la plataforma actual, esta se retorna en forma de una estructura de tipo info_os la cual varia segun sea windows o linux. Declaraciones:
Para Linux:
Para Windows:
typedef struct info_os
{
LPSYSTEM_INFO info;
} info_os;
y aqui su definicion:
Como podéis ver hace uso de las funciones de sus propios sistemas para obtener información útil.
La siguiente función seria create_table_blocks, esta recibira un valor de 64bits que seria el tamaño maximo para la tabla de bloques, y un argumento donde se le especifica los permisos de la tabla. Esta funcion se encarga de inicializar una tabla de bloques con los permisos y memoria necesaria. Por ahora la definición sin desarrollar se ve asi:
La función is_free es de mis favoritas por su simplificad:
Simplemente ejercemos la resta tal como hemos mencionado en la parte de arriba, y si el resultado de la resta es 0 es que esta libre, me recuerda a la resta que hace cmp por alguna razon JSJSJJS.
get_real_size_block daria el tamaño del bloque real, eso quiere decir, que no se te dara el tamaño que como programador pediste, si no una suma de este y el tamaño de la cabecera:
Lo que hacemos es solo sumarle lo que el programador especifico "size" el tamaño del header. De igual manera tenemos get_size_block que retorna el pseudo-tamaño del bloque, un tamaño que el programador pueda usar, ya que get_real_size_block es raro que lo use el usuario, esta función debería usarla mas el allocator para comprender el tamaño real que se esta reservando, ya que en los allocator reales, aunque nosotros en malloc realicemos malloc(16), no se esta reservando únicamente el 16Bytes, sino que internamente esta misma función reserva memoria para sus propias estructuras, solo que como usuario de mas alto nivel no apreciamos esto.
Otra función importante, y que como tal seria la que usualmente quizas usaría el programador:
Esta función cogería una tabla que recibe como argumento, y un valor de 64bits(size) el cual seria el tamaño del bloque de memoria. Se me olvido agregar otro para especificar los permisos pero bueno. Esta función se encargaría de entre otras cosas, ver si en la tabla queda memoria para dicho bloque, y en cado contrario retornar NULL. También aumentaría en 1 el tamaño de bloques si el valor no es 0, en ese caso tmb deberíamos actualizar el miembro next del anterior bloque, al bloque actual por ejemplo. En el caso de que la tabla este vacia, la inicializamos si no lo esta, y en next colocaríamos NULL pues no hay bloque de memoria al que apuntar o como mucho, le pondríamos que apunte a el mismo.
Ahora, una función a tener en cuenta es create_hash_align, esta función es algo característica. Esta se encarga de que, dada x entrada(data), se cree un hash que puede estar alineado en memoria y del largo de palabra del procesador, independientemente de la función hash usada. Cabe mencionar que la utilidad de esta función no es completamente criptografica, se usara mas para la comprobación de errores por ejemplo, o para la detención de alteraciones de memoria, seria algo así como nuestro checksum y que este alineado con la memoria seria opcional.
Todo se especifica mediante de un enum type_hash:
en el primer miembro de type_hash, el miembro type_hash, se usa para especificar el algoritmo hash que he implementado a usar. cabe mencionar que MurmurHash128Bits_x86_64 y MurmurHash128Bits_x86_32 son versiones de Murmur hash de claves de 128bits optimizadas para sus correspondientes arquitecturas. Tenemos MurmurHash32Bits que seria una versión de la misma pero con una clave de 32 bits, la posibilidad de usar la función MD5 y MD4 y la conocida función SHA256.
El siguiente campo es create_hash_align donde se le especifica si queremos un hash del largo de palabra del procesador para su alineación en memoria o si preferimos que el largo se defina por la función y el miembro hash.
El miembro hash, es un miembro donde se guarda el hash si no es alineado, en caso de que el hash este alineado, se retorna desde la función como un valor size_t. Estos campos miembros se define para claves de 16, 32 y 128 bits que son las que necesarias para las funciones hash. Decir que la función create_hash_align no esta terminada:
Esto lo hacemos, por que alinear la memoria mejora el acceso a la memoria, permite que se acceda con mayor velocidad que es algo importante en un allocator.
Para alinear una direccion de memoria o un valor o cualquier otro podemos usar la siguiente formula:
básicamente es hacer una operación NOT y AND con un par de resta y una suma.
Para crear un hash de tamaño de palabra de procesador, se crea un array hash con el tamaño que se define por SIZE_WORD, este valor cambia si se compila para 16bits(-m16), 32bits(-m32) o 64bits(-m64) y se define haciendo uso de la macro CPU_BITS_X86 que se define en una header personal he indica la cantidad de bits del procesador.
Este array se inicializa en 0, usamos la funcion hash especificada por argumento y la guardamos en un segundo array, y aposterior realizamos una serie de operaciones XOR con los valores del hash para obtener un hash de tamaño constante, independientemente del tamaño del hash de entrada.
Tengo que decir, que este codigo no os funcionara por varias razones, algunas de ellas es que obviamente es código de POC, es decir, mayormente son comentarios diciendo que debería hacerse, definiciones de funciones, estructuras y etc. Pero aparte, usa una serie de headers que son propias y no puedo seguir mostrando aqui por que este post daria para un pequeño libro de un par de cuantas paginas, pero son las siguientes como curiosidad:
Las primeras 4 son implementaciones propias de los distintos hash's. string_c es una cabecera personal para manejar arrays de forma dinámica en C. operators_logics.h seria una cabecera donde se define operaciones binarias a nivel de Bits como son OR, XOR, NAND, desplazamiento de bits izquierdos y derechos y etc. Ademas de definicion de macros para la impresion de numeros en formato binario(poco optimizado). Una header importante type_data_c.h donde defino entre otras cosas tipos de datos propios multiplataforma y que no cambian de tamaño independientemente del sistema, compilador o tamaño de palabra del procesador, se define macros para identificar la arquitectura, saber si la maquina es little o big endian, definir limites de tipos de datos, definiciones estándares como las de stdbool.h pero propias, definiciones de tipos de datos de windows, por si queremos usar cosas como DWORD en codigos no destinados a windows. definición de tipos de datos tipo NASM, con db, dw, dd, o dq. definición de estructuras de datos de tamaño constante, definición de estructuras anonimas para multi-tipos de datos, definición para la obtención del byte alto y bajo y otras
Hola buenas, soy Desmon y soy un usuario nuevo en este foro, no se si incumpla alguna de las reglas del foro en este post pero si así que alguien me lo reporte para corregirlo cuanto antes.
Bueno, viniendo a lo que vengo. Estaba o mejor dicho, quería diseñar un allocator de memoria con GC(garbage collection), cual es la salsa del asunto, bueno, quiero hacerlo lo mas eficiente posible, multiplataforma, funcional, con protecciones de memoria y de acceso y quería hacerlo usando C puro, usando las libC lo menos posible y sus cabeceras(esto implica implementar las funciones necesarias para obtener largos de cadenas, imprimir texto, copiar bloques de memoria y etc).
Hoy lo que vengo a preguntar mas concretamente es si conocen algoritmos eficientes para la tarea de diseñar tal pieza de software, o si me recomiendan alguno en especifico.
Necesito uno o varios algoritmos para poder reorganizar la memoria si hay bloques liberados, o que hacer cuando hay memoria liberada de por medio y hay que reorganizar todo para poder hacer buen uso de ella.
Algoritmos para la recolección de basura, pues si, he visto algoritmos y tal, pero no el como se podría crear una implementación como tal por que me falta documentación, información o etc. Si alguien tiene DOC de haber realizado un proyecto similar, o que tiene algún consejo o etc, cualquier cosa es bien venida.
Por ahora he visto varias funciones para reservar memoria, una de ellas es "NtAllocateVirtualMemory" en el caso de Windows, esta la podemos situar en ntdll.dll, lo que estoy haciendo es cargarla en run time si se encuentra en Windows.
Yo estoy haciendo uso de una subrutina constructora que se llama antes que el main sin que el programador convencional lo sepa ni tenga que ser consciente de ello:
primero voy a decir que la macro __DEBUG__ solo la defino a la hora de compilar con -D__DEBUG__ para que pueda ir viendo la información de todo mientras se corre la aplicación que hace uso de esta. La defunción de ntdll esta definido en mi header MemoryAddressBase.h como "HMODULE ntdll;", y el pedazo de codigo que acabáis de ver se encuentra en MemoryAddressBase.c.
La declaración de la función __init1__ se encuentra en el header principal como:
al igual la rutina destructora. Volviendo a nuestra subrutina constructora, usamos LoadLibraryA, una función de la WinApi que carga ntdll.dll en tiempo de ejecución, como es LoadLibraryA se esta usando la versión ANSI de la función. Si al cargarla da algun error ntdll queda con valor nulo y se ejecuta un ROW_ERROR_RET se este definiendo __DEBUG__ o no. TROW_ERROR_RET se define en el header "ErrorAllocator.h" de la siguiente manera:
una simple definición que hace uso de un printf para mostrar el error y un return;. El error ERROR_LOAD_LIB se define en la misma header mediante un enum que podemos ver:
Adicionalmente decir que tenemos una función "printErrorAllocator" que recibe el codigo de error y imprime un mensaje acorde a este:
Volviendo a la función constructora, en el caso de que se use la macro __DEBUG__ usamos GET_LAST_ERROR_WIN que se define en MemoryAddressBase.h de la siguiente manera:
Dicha me permite obtener información mas detallada sobre el error que se produjo al cargar la librería. Prosiguiendo con la subrutina, se obtiene la dirección "NtAllocateVirtualMemory" usando la función GetProcAddress, NtAllocateVirtualMemory y NtAllocateVirtualMemory_t se definen en el header principal de la siguiente manera:
y de igual manera hacemos con "NtFreeVirtualMemory", aquí sus declaraciones:
Esto es en el caso de windows, pero en el caso de linux en un inicio he pensado usar mmap, una syscall que permite al kernel pedir memoria para tratarla como queramos, se podria decir que es la función NtAllocateVirtualMemory para linux.
Se que dicha funcion se puede usar con sus cabeceras, pero no lo quise, en su lugar opte mejor usar Assembly si era posible, entonces primero veamos la declaración de mmap en nuestro header principal como:
y su respectiva declaración para Linux en arquitectura de 32 y 64 bits:
Los lectores atentos habrán visto que hay una ultima directiva #elif al final, hago uso de esta para, en el caso de que no se pueda detectar el tamaño de palabra como 32 o 64bits, usar un comportamiento default donde se usa syscall y __NR_mmap definidas en cabeceras de C para usar mmap sin tener que hacerlo en asm, podría incluir una condicional mas al elif para que se use esta opción si la maquina en la que se esta compilando no es x86, lo que lo haría mas portable en teoría. Por lo demas, la función mmap_syscall es definida con una versión de 32bits donde se usa registros de 32bits (eax, ebx, ...) y la mas conocida interrupción 80h. En el caso de estar compilándose el código en 64bits(-m64), tenemos una versión que usa los registros de 64bits (rax, rbx, ...) y usamos la instrucción syscall exclusiva de maquinas x86 de 64bits en lugar de int.
Ahora, habréis notado que ambas syscall's, la versión de linux y la versión de windows reciben una serie de argumentos, bastante similares en cuanto a su uso, por ejemplo tenemos un argumento para definir la cantidad de memoria que queremos reservar, lo que seria ¿una pagina de memoria quizas? habría que verlo, pero el campo que nos interesa es ULONG Protect en el caso de "NtAllocateVirtualMemory" o "int prot" en el caso de "mmap". Estos campos se usan para lo mismo y es básicamente para definir los permisos que tiene la "sección" de memoria que queremos pedir al kernel. Esto lo podría especificar el programador y para ello, hemos creado un enum que apenas cambia independientemente de la plataforma para especificar los permisos, aqui podemos verlo, y se situa en la header principal:
Cabe mencionar que estos son permisos de PAGINAS y creo que esto es necesario recalcarlo. Si mal no he visto, estos permisos se especifican de igual manera en Linux como en Windows, que es con valores enteros, 0(nada)(-), 1(leer)(r), 2(escribir)(w) y 4(ejecutar)(x). Los mas linuxeros apreciaran que esto es como los valores octales en chmod. Podemos combinar permisos simplemente sumando valores, por ejemplo para tener permisos de lectura y escritura, sumamos el valor 1(leer) con el valor 2(escribir), lo que da el valor 3(leer y escribir pero no ejecutar). De igual manera podemos dar todos los permisos sumando 1(leer), 2(escribir), 4(ejecutar), lo que da como resultado 7(1+2+4=rwx), lo que se corresponde al 7 de cuando ponemos "chmod 777 <file>" por ejemplo.
Ahora, entremos en declaraciones de los bloques de memoria y etc:
Cabe mencionar que aquí el concepto de "bloque" no es mas que una abstracción de una representación de datos guardados en la misma memoria de la pagina, donde alojamos información de los permisos que tiene una "seccion" que pedimos al allocator, lo que vendria siendo en C el puntero que nos retorna malloc, algo similar, solo que nuestro malloc en teoria debería ser mas complejo. Dichos bloques se alojan en tablas, tablas de bloques valga la redundancia y las tablas se alojan en paginas de memoria, podemos tener una o mas tablas de memoria con distintos permisos y distintos bloques a lo largo de nuestro programa. Y claro, como no, decir que una paginas puede tener mas de una tabla, esto va a depende de si la tabla es mas grande que la pagina, en ese caso necesitaremos mas de una pagina para guardar una tabla. Si la tabla es 1/4 de la pagina, pues en una misma pagina puede entrar 4 tablas, entonces aqui debemos hacer un diseño razonablemente inteligente mas adelante.
Prosigamos, cada bloque de memoria tiene un header, una cabecera de bloque para que nos entendamos, y esta la hemos visto ya en la definición de block_memory:
En la cabecera guardaríamos un id de 64bits, aunque estoy pensando en cambiar estos valores de 64bits a datos que cambien entre 32, 64 y etc dependiendo del largo de palabra del procesador. Este ID, es un ID relativo entorno a una tabla, que quiero decir con esto. Pues que puede haber mas de un bloque de memoria que tenga el ID 1, mientras se han tablas diferentes, pero en una misma tabla, solo puede haber un bloque con el mismo ID que identifique a este mismo, sera su DNI en la table. Tambien tenemos un campo para indicar el tamaño del bloque, esto lo hacemos para conocer el offset de cada bloque de memoria, y a lo largo de nuestro allocator no pasarnos escribiendo memoria. is_free seria otro valor que indicaría el espacio libre en el bloque. Si size y is_free tienen el mismo valor podemos deducir que el bloque no tiene nada dentro, esta vacio, o que el bloque tiene un tamaño de 0. El tamaño ocupado lo podríamos obtener mediante una simple resta, que seria size-is_free, eso nos daría el tamaño ya ocupado del bloque. El siguiente miembro es next, que es un puntero de la estructura block_memory donde se especificaría la dirección del siguiente bloque de memoria con su propia cabecera. Hay que decir que esto es similar a una lista enlazada, tal vez agregue el que sea una doble lista enlaza, para eso habría que incluir un mismo puntero al bloque anterior. Otro miembro de la cabecera de bloque es el de PermissionBlock, este es un valor el cual indica los permisos que hay en dicho bloque de memoria, hay que decir que sus permisos no pueden ser superior a los permisos de la tabla, eso quiere decir que si la tabla solo tiene permisos de lectura, no podemos hacer que el bloque tenga permisos de ejecución, sino que además todos los bloques de esta solo tendrán permisos de lectura o ninguno, los permisos pueden ser los mismos o inferiores, pero NUNCA SUPERIORES. Esto lo hacemos como un posible mecanismo de seguridad, cabe mencionar que tendremos que ser nosotros luego el que nos aseguremos que no se violen estos permisos.
Ahora, el bloque de memoria aparte del header, tiene un puntero void donde tiene que ser un puntero que cumpla algunas características, como que tenga el tamaño adecuado(size) y que no invada las direcciones de otros bloques, por que en ese caso estaríamos sobrescribiendo bloques y esto es una falla muy gorda. El miembro addr_memory seria como tal el puntero que el programador usara de forma directa u indirecta para lo que el quiera, como puede ser guardar estructuras o leer archivos entre otros.
Veamos como seria la definicion de table_blocks, o tabla de bloques:
Los comentarios deben hablar por si mismo, pero aun asi os explicare. Como ya hemos mencionado los bloques se alojan en tablas y las tablas en paginas. numbre_blocks es un miembro donde especificamos la cantidad de bloques, podríamos hacer también un campo donde especificar la cantidad de bloques máxima que podemos tener en la tabla. Otro miembro es first y last. El primer mencionado es un puntero al primer bloque de la tabla, y el segundo, es un puntero al ultimo bloque, esto tal vez podemos hacerlo para hacer sorting, o simplemente para conocer como se aloja nuestros bloques en la tabla. Hay que mencionar que el miembro last cambiara cada vez que añadamos un bloque nuevo al final de la tabla, y que first cambiara si el bloque al que apunta es eliminado.
PermissionTable podéis deducir que hace(especificar los permisos de la tabla). Y un puntero importante es next, este al igual que en header, hacer referencia a la siguiente tabla, tal vez también este bien hacer una doble lista enlazada.
Luego tendriamos un registro de tablas donde se guardaria las direcciones de cada tabla, este registro tendria que permitir que se actualice elimando y añadiendo tablas, sin que las demas se vean afectadas, actualmente y posiblemente temporalmente esta definida asi:
Ahora bien, algunas declaraciones de funciones que hay por ahora:
get_info_system es una función que retorna información acerca de la plataforma actual, esta se retorna en forma de una estructura de tipo info_os la cual varia segun sea windows o linux. Declaraciones:
Para Linux:
Para Windows:
typedef struct info_os
{
LPSYSTEM_INFO info;
} info_os;
y aqui su definicion:
Como podéis ver hace uso de las funciones de sus propios sistemas para obtener información útil.
La siguiente función seria create_table_blocks, esta recibira un valor de 64bits que seria el tamaño maximo para la tabla de bloques, y un argumento donde se le especifica los permisos de la tabla. Esta funcion se encarga de inicializar una tabla de bloques con los permisos y memoria necesaria. Por ahora la definición sin desarrollar se ve asi:
La función is_free es de mis favoritas por su simplificad:
Simplemente ejercemos la resta tal como hemos mencionado en la parte de arriba, y si el resultado de la resta es 0 es que esta libre, me recuerda a la resta que hace cmp por alguna razon JSJSJJS.
get_real_size_block daria el tamaño del bloque real, eso quiere decir, que no se te dara el tamaño que como programador pediste, si no una suma de este y el tamaño de la cabecera:
Lo que hacemos es solo sumarle lo que el programador especifico "size" el tamaño del header. De igual manera tenemos get_size_block que retorna el pseudo-tamaño del bloque, un tamaño que el programador pueda usar, ya que get_real_size_block es raro que lo use el usuario, esta función debería usarla mas el allocator para comprender el tamaño real que se esta reservando, ya que en los allocator reales, aunque nosotros en malloc realicemos malloc(16), no se esta reservando únicamente el 16Bytes, sino que internamente esta misma función reserva memoria para sus propias estructuras, solo que como usuario de mas alto nivel no apreciamos esto.
Otra función importante, y que como tal seria la que usualmente quizas usaría el programador:
Esta función cogería una tabla que recibe como argumento, y un valor de 64bits(size) el cual seria el tamaño del bloque de memoria. Se me olvido agregar otro para especificar los permisos pero bueno. Esta función se encargaría de entre otras cosas, ver si en la tabla queda memoria para dicho bloque, y en cado contrario retornar NULL. También aumentaría en 1 el tamaño de bloques si el valor no es 0, en ese caso tmb deberíamos actualizar el miembro next del anterior bloque, al bloque actual por ejemplo. En el caso de que la tabla este vacia, la inicializamos si no lo esta, y en next colocaríamos NULL pues no hay bloque de memoria al que apuntar o como mucho, le pondríamos que apunte a el mismo.
Ahora, una función a tener en cuenta es create_hash_align, esta función es algo característica. Esta se encarga de que, dada x entrada(data), se cree un hash que puede estar alineado en memoria y del largo de palabra del procesador, independientemente de la función hash usada. Cabe mencionar que la utilidad de esta función no es completamente criptografica, se usara mas para la comprobación de errores por ejemplo, o para la detención de alteraciones de memoria, seria algo así como nuestro checksum y que este alineado con la memoria seria opcional.
Todo se especifica mediante de un enum type_hash:
en el primer miembro de type_hash, el miembro type_hash, se usa para especificar el algoritmo hash que he implementado a usar. cabe mencionar que MurmurHash128Bits_x86_64 y MurmurHash128Bits_x86_32 son versiones de Murmur hash de claves de 128bits optimizadas para sus correspondientes arquitecturas. Tenemos MurmurHash32Bits que seria una versión de la misma pero con una clave de 32 bits, la posibilidad de usar la función MD5 y MD4 y la conocida función SHA256.
El siguiente campo es create_hash_align donde se le especifica si queremos un hash del largo de palabra del procesador para su alineación en memoria o si preferimos que el largo se defina por la función y el miembro hash.
El miembro hash, es un miembro donde se guarda el hash si no es alineado, en caso de que el hash este alineado, se retorna desde la función como un valor size_t. Estos campos miembros se define para claves de 16, 32 y 128 bits que son las que necesarias para las funciones hash. Decir que la función create_hash_align no esta terminada:
Esto lo hacemos, por que alinear la memoria mejora el acceso a la memoria, permite que se acceda con mayor velocidad que es algo importante en un allocator.
Para alinear una direccion de memoria o un valor o cualquier otro podemos usar la siguiente formula:
básicamente es hacer una operación NOT y AND con un par de resta y una suma.
Para crear un hash de tamaño de palabra de procesador, se crea un array hash con el tamaño que se define por SIZE_WORD, este valor cambia si se compila para 16bits(-m16), 32bits(-m32) o 64bits(-m64) y se define haciendo uso de la macro CPU_BITS_X86 que se define en una header personal he indica la cantidad de bits del procesador.
Este array se inicializa en 0, usamos la funcion hash especificada por argumento y la guardamos en un segundo array, y aposterior realizamos una serie de operaciones XOR con los valores del hash para obtener un hash de tamaño constante, independientemente del tamaño del hash de entrada.
Tengo que decir, que este codigo no os funcionara por varias razones, algunas de ellas es que obviamente es código de POC, es decir, mayormente son comentarios diciendo que debería hacerse, definiciones de funciones, estructuras y etc. Pero aparte, usa una serie de headers que son propias y no puedo seguir mostrando aqui por que este post daria para un pequeño libro de un par de cuantas paginas, pero son las siguientes como curiosidad:
Las primeras 4 son implementaciones propias de los distintos hash's. string_c es una cabecera personal para manejar arrays de forma dinámica en C. operators_logics.h seria una cabecera donde se define operaciones binarias a nivel de Bits como son OR, XOR, NAND, desplazamiento de bits izquierdos y derechos y etc. Ademas de definicion de macros para la impresion de numeros en formato binario(poco optimizado). Una header importante type_data_c.h donde defino entre otras cosas tipos de datos propios multiplataforma y que no cambian de tamaño independientemente del sistema, compilador o tamaño de palabra del procesador, se define macros para identificar la arquitectura, saber si la maquina es little o big endian, definir limites de tipos de datos, definiciones estándares como las de stdbool.h pero propias, definiciones de tipos de datos de windows, por si queremos usar cosas como DWORD en codigos no destinados a windows. definición de tipos de datos tipo NASM, con db, dw, dd, o dq. definición de estructuras de datos de tamaño constante, definición de estructuras anonimas para multi-tipos de datos, definición para la obtención del byte alto y bajo y otras