Allocator en C/C++ y ¿tal vez assembly?

desmon_hak · Abril 29, 2023, 04:40:43 PM

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:

Código: c

void __init1__()
{

#ifndef __DEBUG__
    LPSTR errorText = NULL;
    DWORD error = NULL;
#endif

#if defined(WIN32) || defined(_WIN32) || defined(_WIN64) || defined(__WIN32__) || defined(__NT__)
    // cargar la ntdll
    ntdll = LoadLibraryA("ntdll.dll");
    if (ntdll == NULL)
    {
#ifdef __DEBUG__
        GET_LAST_ERROR_WIN()
        printf("Error: %s", errorText);
        printf("Error %p: No se pudo obtener el handle de la libreria ntdll.dll.\n", error);
        printf("Error al cargar ntdll.dll\n");
#endif
        ROW_ERROR_RET(ERROR_LOAD_LIB)
    }

    // cargar la funcion NtAllocateVirtualMemory de ntdll
    NtAllocateVirtualMemory = (NtAllocateVirtualMemory_t)GetProcAddress(ntdll, "NtAllocateVirtualMemory");
    if (NtAllocateVirtualMemory == NULL)
    {
#ifdef __DEBUG__
        GET_LAST_ERROR_WIN()
        printf("Error: %s", errorText);
        printf("Error %p: No se pudo obtener NtAllocateVirtualMemory de ntdll.dll.\n", error);

        printf("Error al obtener puntero a NtAllocateVirtualMemory\n");
#endif
        TROW_ERROR_RET(ERROR_LOAD_FUNC)
    }
#endif
    NtFreeVirtualMemory = (NtFreeVirtualMemory_t)GetProcAddress(ntdll, "NtFreeVirtualMemory");
    if (NtFreeVirtualMemory == NULL)
    {
#ifdef __DEBUG__
        GET_LAST_ERROR_WIN()
        printf("Error: %s", errorText);
        printf("Error %p: No se pudo obtener NtFreeVirtualMemory de ntdll.dll.\n", error);

        printf("Error al obtener puntero a NtFreeVirtualMemory\n");
#endif
        TROW_ERROR_RET(ERROR_LOAD_FUNC)
    }

#ifdef __DEBUG__
    debug_print("__init1__ __attribute__((constructor))")
#endif
        RegistroTablas.n_tablas = (_uint64_t){0};
    RegistroTablas.tablas = NULL;
    /*
     *  Usar create_table_blocks() para reservar la primera memoria del programa
     *  y que el pogramador no necesite crear una por su cuenta
     *  sino que pueda reservar memoria en ella directamente
     */
    return;
}

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:

Código: php

void __attribute__((constructor)) __attribute__((visibility("hidden"))) __init1__();
void __attribute__((destructor)) __attribute__((visibility("hidden"))) __end1__();

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:

Código: c

#define TROW_ERROR_RET(ERROR)                   \
    printf("Error(ErrorAllocator): %p", ERROR); \
    return;

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:

Código: php

typedef enum ErrorAllocator
{
    SUCESS,
    ERROR_LOAD_LIB,
    ERROR_LOAD_FUNC
} ErrorAllocator;

Adicionalmente decir que tenemos una función "printErrorAllocator" que recibe el codigo de error y imprime un mensaje acorde a este:

Código: c

void printErrorAllocator(ErrorAllocator err)
{

    switch (err)
    {
    case SUCESS:
        puts(MSG_ERROR_SUCESS);
        return;
    case ERROR_LOAD_LIB:
        puts(MSG_ERROR_LOAD_LIB);
        return;
    case ERROR_LOAD_FUNC:
        puts(MSG_ERROR_LOAD_FUNC);
        return;
    default:
        puts(MSG_ERROR_UNKNOW_ERROR);
        return;
    }
}

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:

Código: c

#ifdef __DEBUG__
    LPSTR errorText = NULL;
    DWORD error = NULL;
#endif
#define GET_LAST_ERROR_WIN() error = GetLastError(); \
    FormatMessage( \
        FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_ALLOCATE_BUFFER | FORMAT_MESSAGE_IGNORE_INSERTS, \
        NULL,\
        error, \
        MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),\
        (LPSTR)&errorText, \
        0,\
        NULL \
    );

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:

Código: c

typedef NTSTATUS(__stdcall *NtAllocateVirtualMemory_t)(
    HANDLE ProcessHandle,
    PVOID *BaseAddress,
    ULONG_PTR ZeroBits,
    PSIZE_T RegionSize,
    ULONG AllocationType,
    ULONG Protect);
NtAllocateVirtualMemory_t NtAllocateVirtualMemory;

y de igual manera hacemos con "NtFreeVirtualMemory", aquí sus declaraciones:

Código: c

typedef NTSTATUS(__stdcall *NtFreeVirtualMemory_t)(
    HANDLE ProcessHandle,
    PVOID *BaseAddress,
    PSIZE_T RegionSize,
    ULONG FreeType);
NtFreeVirtualMemory_t NtFreeVirtualMemory;

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:

Código: c

void *mmap_syscall(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

y su respectiva declaración para Linux en arquitectura de 32 y 64 bits:

Código: c

#if CPU_BITS_X86 == 32 && defined(__linux__)
void *mmap_syscall(void *addr, size_t length, int prot, int flags, int fd, off_t offset){
    void *result;
    asm(
        "mov %1, %%eax\n\t"      // Carga el número de llamada del sistema
        "mov %2, %%ebx\n\t"      // addr -> ebx
        "mov %3, %%ecx\n\t"      // length -> ecx
        "mov %4, %%edx\n\t"      // prot -> edx
        "mov %5, %%esi\n\t"      // flags -> esi
        "mov %6, %%edi\n\t"      // fd -> edi
        "mov %7, %%ebp\n\t"      // offset -> ebp
        "int $0x80\n\t"          // Llama al sistema
        "mov %%eax, %0\n\t"      // Guarda el resultado
        : "=r" (result)          // Salida
        : "i" (__NR_mmap), "r" (addr), "r" (length), "r" (prot), "r" (flags), "r" (fd), "r" (offset) // Entradas
        : "%eax", "%ebx", "%ecx", "%edx", "%esi", "%edi", "%ebp" // Registros modificados
    );
    return result;
}
#elif CPU_BITS_X86 == 64 && defined(__linux__)
void *mmap_syscall(void *addr, size_t length, int prot, int flags, int fd, off_t offset) {
    void *result;
    asm(
        "mov %1, %%rax\n\t"      // Carga el número de llamada del sistema
        "mov %2, %%rdi\n\t"      // addr -> rdi
        "mov %3, %%rsi\n\t"      // length -> rsi
        "mov %4, %%rdx\n\t"      // prot -> rdx
        "mov %5, %%r10\n\t"      // flags -> r10
        "mov %6, %%r8\n\t"       // fd -> r8
        "mov %7, %%r9\n\t"       // offset -> r9
        "syscall\n\t"            // Llama al sistema
        "mov %%rax, %0\n\t"      // Guarda el resultado
        : "=r" (result)          // Salida
        : "i" (__NR_mmap), "r" (addr), "r" (length), "r" (prot), "r" (flags), "r" (fd), "r" (offset) // Entradas
        : "%rax", "%rdi", "%rsi", "%rdx", "%r10", "%r8", "%r9", "memory" // Registros modificados
    );
    return result;
}
#elif defined(__linux__)
#warning  "La arquitectura actual no es de 64bits o 32bits"
void *mmap_syscall(void *addr, size_t length, int prot, int flags, int fd, off_t offset) {
    return (void*) syscall(__NR_mmap, addr, length, prot, flags, fd, offset);
}

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:

Código: c

// permisos permitidos para mmap y NtAllocateVirtualMemory 
typedef enum PermissionMemory 
{
    /*
     *  get_permission_memory:
     *      Obtener los permisos de un bloque.
     *  set_permission_memory:
     *      Cambiar los permisos de un bloque.
     * get_char_permission_memory:
     *      Obtener los permisos de un bloque pero
     *      representado con los caracteres (r,w,x).
     */

    NONE,            // 0 + 0 + 0 = --- = 0
    READ,            // 0 + 0 + 1 = r-- = 1
    WRITE,           // 0 + 0 + 2 = -w- = 2

    READ_WRITE,      // 0 + 1 + 2 = rw- = 3
    EXEC,            // 0 + 0 + 4 = --x = 4
    READ_EXEC,       // 0 + 4 + 1 = r-x = 5
    WRITE_EXEC,      // 0 + 2 + 4 = -wx = 6
    READ_WRITE_EXEC, // 1 + 2 + 4 = rwx = 7

    #ifdef __linux__
    GROWSDOWN = 0x01000000,
    GROWSUP   = 0x02000000,
    SEM       = 0x04000000,
    LOOSE     = 0x10000000,
    HUGETLB   = 0x00040000,
    SAO       = 0x08000000,
    #endif

} PermissionMemory;

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:

Código: c

typedef struct block_memory
{
    struct
    {                                     // cabecera de los bloques
        _uint64_t id;                     // id del bloque.
        _uint64_t size;                   // tamaño del bloque escluyendo la cabecera. sizeof(addr_memory)
        _uint64_t is_free;                // espacio libre del bloque (size == is_free[el bloque no fue usado])
        struct block_memory *next;        // direcion del siguiente bloque de memoria
        PermissionMemory PermissionBlock; // permisos del bloque.
    } cabecera_bloque;                    // datos de cabecera del bloque
    void *addr_memory;                    // direccion de memoria donde se almacenan los datos del bloque
} block_memory;
#define size_block_memory sizeof(block_memory)

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:

Código: c

#define size_block_memory sizeof(block_memory)

typedef struct header
{                                     // cabecera de los bloques
    _uint64_t id;                     // id del bloque
    _uint64_t size;                   // tamaño del bloque escluyendo la cabecera
    _uint64_t is_free;                // espacio libre del bloque (size == is_free[el bloque no fue usado])
    block_memory *next;               // direcion del siguiente bloque de memoria
    PermissionMemory PermissionBlock; // permisos del bloque.
} header;
#define size_header sizeof(header)

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:

Código: c

typedef struct table_blocks
{                                     // tabla de bloques para el allocator
    _uint64_t numbre_blocks;          // cantidad de bloques dentro de la tabla
    block_memory *first;              // primer bloque
    block_memory *last;               // ultimo bloque
    PermissionMemory PermissionTable; // Permisos de la tabla.
    struct table_blocks *next;        // siguiente tabla
} table_blocks;

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:

Código: c

static struct
{
    table_blocks **tablas; // lista donde se almacenan todas las tablas en run time
    _uint64_t n_tablas;    // Numero de tablas almacenadas a lo  largo del programa
} RegistroTablas;

Ahora bien, algunas declaraciones de funciones que hay por ahora:

Código: c

info_os get_info_system();
table_blocks create_table_blocks(ui64 size_memory_resb, PermissionMemory permisos);

bool is_free(block_memory bloque_memoria);

uint64_t get_real_size_block(block_memory bloque_memoria);
uint64_t get_size_block(block_memory bloque_memoria);

block_memory*malloc_c(table_blocks _table_blocks, ui64 size);
size_t create_hash_align(ui8 *data, type_hash type_hash);

void __attribute__((constructor)) __attribute__((visibility("hidden"))) __init1__();
void __attribute__((destructor)) __attribute__((visibility("hidden"))) __end1__();

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:

Código: c

typedef struct info_os
{
    struct sysinfo info;
    struct utsname sysinfo;
} info_os;

Para Windows:
typedef struct info_os
{
LPSYSTEM_INFO info;
} info_os;

y aqui su definicion:

Código: c


info_os get_info_system()
{
    info_os data;
#if defined(WIN32) || defined(_WIN32) || defined(__WIN32__) || defined(__NT__)
    // Si el sistema es windows, GetSystemInfo guarda la info posible
    // en la estructura info_os la cual varia entre plataforma.
    GetSystemInfo(data.info);
    /*
     *  void GetSystemInfo([out] LPSYSTEM_INFO lpSystemInfo);
     *
     *  typedef struct _SYSTEM_INFO {
     *
     *      union {
     *          DWORD dwOemId;
     *          struct {
     *
     *              WORD wProcessorArchitecture;
     *              WORD wReserved;
     *
     *          } DUMMYSTRUCTNAME;
     *      } DUMMYUNIONNAME;
     *
     *      DWORD     dwPageSize;
     *      LPVOID    lpMinimumApplicationAddress;
     *      LPVOID    lpMaximumApplicationAddress;
     *      DWORD_PTR dwActiveProcessorMask;
     *      DWORD     dwNumberOfProcessors;
     *      DWORD     dwProcessorType;
     *      DWORD     dwAllocationGranularity;
     *      WORD      wProcessorLevel;
     *      WORD      wProcessorRevision;
     *  } SYSTEM_INFO, *LPSYSTEM_INFO;
     *
     */
#elif __linux__
    /*
     *  #include <sys/sysinfo.h>
     *  int sysinfo(struct sysinfo *info);
     *
     *  Until Linux 2.3.16:
     *  struct sysinfo
     *  {
     *      long uptime;             // Seconds since boot
     *      unsigned long loads[3];  // 1, 5, and 15 minute load averages
     *      unsigned long totalram;  // Total usable main memory size
     *      unsigned long freeram;   // Available memory size
     *      unsigned long sharedram; // Amount of shared memory
     *      unsigned long bufferram; // Memory used by buffers
     *      unsigned long totalswap; // Total swap space size
     *      unsigned long freeswap;  // Swap space still available
     *      unsigned short procs;    // Number of current processes
     *      char _f[22];             // Pads structure to 64 bytes
     *  };
     *
     *  Since Linux 2.3.23 (i386) and Linux 2.3.48 (all architectures) the structure is
     *  struct sysinfo {
     *      long uptime;             // Seconds since boot
     *      unsigned long loads[3];  // 1, 5, and 15 minute load averages
     *      unsigned long totalram;  // Total usable main memory size
     *      unsigned long freeram;   // Available memory size
     *      unsigned long sharedram; // Amount of shared memory
     *      unsigned long bufferram; // Memory used by buffers
     *      unsigned long totalswap; // Total swap space size
     *      unsigned long freeswap;  // Swap space still available
     *      unsigned short procs;    // Number of current processes
     *      unsigned long totalhigh; // Total high memory size
     *      unsigned long freehigh;  // Available high memory size
     *      unsigned int mem_unit;   // Memory unit size in bytes
     *      char _f[20-2*sizeof(long)-sizeof(int)]; //Padding to 64 bytes
     *  };
     *
     *
     *  #include <sys/utsname.h>
     *  int uname(struct utsname *buf);
     *  struct utsname {
     *      char sysname[];    // Operating system name (e.g., "Linux")
     *      char nodename[];   // Name within "some implementation-defined network"
     *      char release[];    // Operating system release (e.g., "2.6.28")
     *      char version[];    // Operating system version
     *      char machine[];    // Hardware identifier
     *      #ifdef _GNU_SOURCE
     *          char domainname[]; // NIS or YP domain name
     *      #endif
     *  };
     */
    // si el sistema es linux, se usa la funcion uname y sysinfo
    // para obtener informacion
    uname(&data.sysinfo);
    sysinfo(&data.info);
#endif
    return data;
}

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:

Código: c

table_blocks create_table_blocks(ui64 size_memory_resb, PermissionMemory permisos)
{
    /*
     * - Esta funcion crea una primera tabla con una
     *      cantidad determinada de buffer(SIZE_TABLE_DEFAULT).
     *
     *  size_memory_resb: memoria a reservar. 0 es reservar
     *                      una tabla con SIZE_TABLE_DEFAULT.
     *                      Un valor distinto impplica reserva
     *                      esa cantidad de bytes.
     */

    if (size_memory_resb == 0)
        size_memory_resb = SIZE_TABLE_DEFAULT;

    // se tiene que almacenar en memoria, y pasarse a tabla
    block_memory bloqueNULL = {
        // falta desarollar:
        //.addr_memory = resb_memory(size_memory_resb); // Esta funcion reserva memoria(conceptualmente)
        .cabecera_bloque = {
            .id = 0,                     // ID 0 para el primer bloque
            .is_free = size_memory_resb, // inicialmente al primer bloque se le asigna la memoria de toda la tabla
            .size = size_memory_resb,
            .next = NULL,           // Aun no se a agregado un primer bloque.
            .PermissionBlock = NONE // Este bloque no tiene ningun tipo de permiso
        }};

    table_blocks tabla = {
        .numbre_blocks = 1,          // numero de bloques iniciales.
        .PermissionTable = permisos, // tabla con los permisos especificados por argumentos
        .first = bloqueNULL,         // primer bloque
        .last = bloqueNULL           // ultimo bloque.
    };
}

La función is_free es de mis favoritas por su simplificad:

Código: c

bool is_free(block_memory bloque_memoria)
{
    /*
     *  - Esta funcion retorna 1 si el bloque esta "vacio" o si tiene algo.
     *  Se recibe un bloque de memoria y se compara el tamano del bloque(size) con la cantidad
     *  de espacio libre(is_free), es deducible que si la cantidad libre es igual al tamano del
     *  bloque quiere decir que el mismo esta vacio, o mejor dicho no contiene nada exceptuando
     * la cabecera.
     */
    if ((bloque_memoria.cabecera_bloque.size._uint64_t - bloque_memoria.cabecera_bloque.is_free._uint64_t) == 0)
        return true;
    else
        return false;
}

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:

Código: c

#define get_real_size_block_DEF(bloque_memoria) bloque_memoria.cabecera_bloque.size._uint64_t+ size_header

uint64_t get_real_size_block(block_memory bloque_memoria)
{
    /*
     *  - Esta funcion devuelve el tamano real del bloque incluyendo la cabecera del bloque.
     *  Para la operacion se obtendra el tamano ocupado del bloque(size-is_free) y se le suma
     *  el tamano de la cabecera.
     */
    return get_real_size_block_DEF(bloque_memoria);
}

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:

Código: c

block_memory *malloc_c(table_blocks _table_blocks, ui64 size)
{
    /*
     *
     *  table_blocks _table_blocks: esta estructura es una tabla que contiene los distintos
     *                              datos almacenador por el programa en forma de bloques.
     *                              El programa puede estar formado por un array de tablas
     *                              que contenda cada uno colecciones de bloques de memoria.
     *
     * ui64 size: permite especificar el tamaño de bloque a reservar en la tabla.
     *
     */
    block_memory *ptr = NULL;

    if (_table_blocks.numbre_blocks._uint64_t != 0)
    {
        // aumentar en uno la cantidad de bloques si no esta vacia
        _table_blocks.numbre_blocks._uint64_t++;
    }
    else
    {
        // si la tabla esta vacia
    }

    return ptr;
}

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:

Código: c

typedef struct type_hash
{
    enum
    {
        MurmurHash128Bits_x86_32,
        MurmurHash128Bits_x86_64,
        MurmurHash32Bits,
        MD5,
        md4,
        sha256
    } type_hash;
    enum
    {
        no,
        yes
    } create_hash_align;
    union
    {
        ui64 hash_128bits[2];
        ui32 hash_32bits;
        ui16 hash_16bits;
    } hash;

} 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:

Código: c

size_t create_hash_align(ui8 *data, type_hash type_hash)
{
    /*
     * Se creara una func hash que recibe un vector.
     * El vector a de ser mayor o igual que el tamano
     * de palabra del procesador. En el caso de no ser asi
     * se usara un padding de 0's para llegar a completar el vector.
     * Una vez se tiene el vetor, se le aplicar una funcion H() para
     * obtener un hash h. h = H(x). Donde x es el vector.
     * h sera del tamano de palabra del procesador, es decir, en un
     * procesador de 32bits, h es de 32/8bits=4 y en uno de 64bits
     * h es 64/8=8bytes.
     *
     * 32bits => 0000_0000.0000_0000
     *
     * 32bits => 0000_0000.0000_0000.0000_0000.0000_0000
     *
     * 64bits => 0000_0000.0000_0000.0000_0000.0000_0000
     *           0000_0000.0000_0000.0000_0000.0000_0000
     */

#if CPU_BITS_X86 == 64
#define SIZE_WORD 8
    ui8 hash[SIZE_WORD] = {0, 0, 0, 0, 0, 0, 0, 0};
#elif CPU_BITS_X86 == 32
#define SIZE_WORD 4
    ui8 hash[SIZE_WORD] = {0, 0, 0, 0};
#elif CPU_BITS_X86 == 16
#define SIZE_WORD 2
    ui8 hash[SIZE_WORD] = {0, 0};
#endif
    if (type_hash.create_hash_align == yes)
    {
        ui32 size = ((_uint32_t)strlen_c((string_c)data))._uint32_t;
        ui32 size_ = size + ((SIZE_WORD - (size % SIZE_WORD)) % SIZE_WORD);

        switch (type_hash.type_hash)
        {
        case MurmurHash128Bits_x86_32:
#ifdef __DEBUG__
            printf("Aplicando MurmurHash128Bits_x86_32\n");
#endif
            MurmurHash3_x32_128(data, size, size, type_hash.hash.hash_128bits);
            /*
            uint32_t value = 0xaabbccdd;
            uint8_t num[4];
            memcpy(num, &value, sizeof(value));
            */
            data = (ui8 *)type_hash.hash.hash_128bits;
            size = sizeof(type_hash.hash.hash_128bits);
            size_ = size + ((SIZE_WORD - (size % SIZE_WORD)) % SIZE_WORD);
#ifdef __DEBUG__
            printf("hash %llx%llx\n", type_hash.hash.hash_128bits[0], type_hash.hash.hash_128bits[1]);
#endif
            break;
        case MurmurHash128Bits_x86_64:
#ifdef __DEBUG__
            printf("Aplicando MurmurHash128Bits_x86_64\n");
#endif
            MurmurHash3_x64_128(data, size, size, type_hash.hash.hash_128bits);
            data = (ui8 *)type_hash.hash.hash_128bits;
            size = sizeof(type_hash.hash.hash_128bits);
            size_ = size + ((SIZE_WORD - (size % SIZE_WORD)) % SIZE_WORD);
#ifdef __DEBUG__
            printf("hash %llx%llx\n", type_hash.hash.hash_128bits[0], type_hash.hash.hash_128bits[1]);
#endif
            break;
        case MurmurHash32Bits:
#ifdef __DEBUG__
            printf("Aplicando MurmurHash32Bits\n");
#endif
            type_hash.hash.hash_32bits = murmur3_32(data, size, size);
            data = (ui8 *)type_hash.hash.hash_32bits;
            size = sizeof(type_hash.hash.hash_32bits);
            size_ = size + ((SIZE_WORD - (size % SIZE_WORD)) % SIZE_WORD);
#ifdef __DEBUG__
            printf("hash %x\n", type_hash.hash.hash_32bits);
#endif
            break;
        case MD5:
            ui8 *a = (ui8 *)&type_hash.hash.hash_32bits;
#ifdef __DEBUG__
            printf("Aplicando md5\n");
#endif

            md5(data, (_uint32_t){size}, a);
            data = a;
            size = sizeof(type_hash.hash.hash_32bits);
            size_ = size + ((SIZE_WORD - (size % SIZE_WORD)) % SIZE_WORD);
#ifdef __DEBUG__
            printf("hash %x\n", type_hash.hash.hash_32bits);
#endif
            break;
        case md4:
#ifdef __DEBUG__
            printf("Aplicando md4\n");
#endif
            break;
        case sha256:
#ifdef __DEBUG__
            printf("Aplicando sha256\n");
#endif
            break;
            /*default MurmurHash128Bits_x86_64:
                break;*/
        }

#ifdef __DEBUG__

        printf("Aplicando create_hash_align, size: %d %d\n", size, size_);
#endif
        for (ui32 i = 0; i < size_; i++)
        {

            if (size < i)
            {
                hash[i % SIZE_WORD] = XOR_operator(hash[i % SIZE_WORD], 0b01010101); // data[i];//
            }
            else
            {
                hash[i % SIZE_WORD] = XOR_operator(hash[i % SIZE_WORD], data[i + 1]); // data[i];//
                hash[i % SIZE_WORD + 1] = XOR_operator(hash[i % SIZE_WORD], data[i]); // data[i];//
            }

#if CPU_BITS_X86 == 64 && __DEBUG__
            printf("HASH bin \t-> " bin_pattern_ui64 " i = %d %d %c\n", bin_ui64(*((size_t *)hash)), i % SIZE_WORD, i, data[i]);
#elif CPU_BITS_X86 == 32 && __DEBUG__
            printf("HASH bin \t-> " bin_pattern_ui32 " i = %d %d %c\n", bin_ui32(*((size_t *)hash)), i % SIZE_WORD, i, data[i]);
#elif CPU_BITS_X86 == 16 && __DEBUG__
            printf("HASH bin \t-> " bin_pattern_ui16 " i = %d %d %c\n", bin_ui16(*((size_t *)hash)), i % SIZE_WORD, i, data[i]);
#endif
        }
    }
    return *((size_t *)hash);
}

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:

Código: php

#define MEMORY_ALIGN(to_be_aligned) AND_operator((to_be_aligned + sizeof(size_t) - 1), NOT_operator(sizeof(size_t) - 1));

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:

Código: php

#include "MurmurHash.h"
#include "md4.h"
#include "md5.h"
#include "sha256.h"
#include "string_c.h"
#include "type_data_c.h"
#include "operators_logics.h"
#include "ErrorAllocator.h"

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

DtxdF · Abril 29, 2023, 10:08:38 PM

Hola No tienes permitido ver los links. Registrarse o Entrar a mi cuenta

Está buena la iniciativa de revivir la programación a bajo nivel y otros temas interesantes que no en todos lados se habla actualmente de forma recurrente

Es recomendable organizar los códigos (source y headers) colocando su nombre (ver el ejemplo a continuación), pero sobre todo colocar los códigos completos para que así se puedan probar y verificar para brindar apoyo.

bar.c:

Código: c

#include <stdlib.h>

#include "foo.h"

int
main(void)
{
    foo_bar();
    return EXIT_SUCCESS;
}

foo.h:

Código: c

#ifndef FOO_H
#define FOO_H

void    foo_bar(void);

#endif

Si notas que son muchos archivos, tal vez te sería más sencillo proveer un enlace a tu repositorio.

---

Hay varios artículos y tutoriales interesantes, que tal vez te hayas encontrado:

*.- No tienes permitido ver los links. Registrarse o Entrar a mi cuenta
*.- No tienes permitido ver los links. Registrarse o Entrar a mi cuenta
*.- No tienes permitido ver los links. Registrarse o Entrar a mi cuenta
*.- No tienes permitido ver los links. Registrarse o Entrar a mi cuenta

Pero tal vez te sea mucho más útil un proyecto ya propiamente creado:

*.- No tienes permitido ver los links. Registrarse o Entrar a mi cuenta

No obstante, lo que te recomiendo es que trates de hacer las cosas lo más simple que puedas, no solamente para este, sino para los siguientes proyectos, porque veo que estás tratando de abarcar varias cosas al mismo tiempo: 1.- hacer el proyecto multiplataforma, 2.- Tratar de usar lo menos posible las funciones del ANSI C, lo cual implica, 4.- Implementar esas funciones, 5.- Hacer que sea eficiente, 6.- Y demás añadidos, como protección de memoria. Esto te está desviando del objetivo principal que es crear el GC, yo te recomiendo implementar el más básico que puedas, así no sea el mejor, pero que lo comprendas de pie a cabeza, y después irlo mejorando poco a poco.

Lo anterior te hará la vida más sencilla, como por ejemplo, si tratas de hacerlo multiplataforma, tienes que lidiar con las syscalls, ya que en este caso las estás usando, y veo que estás agregando código ASM, por lo que la portabilidad te dará una jugarreta más. Usa una sola plataforma, la que conozcas mejor; no obstante te recomiendo Linux porque hay más información para el proyecto que estás haciendo.

No te preocupes por la eficiencia o no optimices de forma prematura, esto acarrea a más problemas que beneficios, en especial porque el desarrollo inicial siempre se cambian muchas cosas, y hará que tengas que depurar más seguido. Y este punto también tiene que ver con lo de no usar las funciones del C Standard, ya que por lo general, los compiladores implementan esas funciones lo más eficiente posible, normalmente en ASM, inclusive, por lo que recrearlas usando C hará que tu código sea más lento de cualquier manera, aparte de que tendrás más lugares por los que depurar. Usa las librerías del estándar C y si estás en una plataforma compatible con POSIX, también usalas, ya que por lo general son bastante útiles, aunque no portables para sistemas que no siguen el estándar POSIX.

Una forma de hacer amena la implementación de tu proyecto para los cambios futuros y en especial para cuando quieres hacerla multiplataforma es abstrayendo los tipos de datos usando Abstract Data Types, encapsulando (aunque en C es limitado, pero funcional) y en general usando funciones para manipular todo lo que se tenga que manipular, así el programa que use tus rutinas no se tiene que preocupar por los cambios internos. Ve el proyecto tgc, que tratar de abordar los puntos antes aclarados.

~DtxdF

Allocator en C/C++ y ¿tal vez assembly?

desmon_hak

Abril 29, 2023, 04:40:43 PM Ultima modificación: Abril 29, 2023, 05:38:25 PM por AXCESS

DtxdF

Abril 29, 2023, 10:08:38 PM #1