/* * malloc.h - User space memory allocator. * * Author Alain Greiner (2016,2017) * * Copyright (c) UPMC Sorbonne Universites * * This file is part of ALMOS-MKH. * * ALMOS-MKH is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2.0 of the License. * * ALMOS-MKH is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with ALMOS-MKH; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ //////////////////////////////////////////////////////////////////////////////// // General principles: // - In user space the HEAP zone spread between the ELF zone and the STACK zone, // as defined in the kernel_config.h file. // - The malloc library uses the mmap() syscall to create - on demand - // one vseg in a given cluster. The size of this vseg is defined below // by the MALLOC_LOCAL_STORE_SIZE parameter. // - For a standard malloc(), the target cluster is the cluster containing // the core running the client thread. // - For a remote_malloc(), the target cluster is explicitely defined // by the argument. // - In each cluster, the available storage in virtual space is handled by a // local allocator using the buddy algorithm. // // TODO : In this first implementation one single - fixed size - vseg // is allocated on demand in each cluster. // We should introduce the possibility to dynamically allocate // several vsegs in each cluster, using several mmap when required. //////////////////////////////////////////////////////////////////////////////// // Free blocks organisation in each cluster : // - All free blocks have a size that is a power of 2, larger or equal // to MALLOC_MIN_BLOCK_SIZE (typically 64 bytes). // - All free blocks are aligned. // - They are pre-classed in an array of linked lists, where all blocks in a // given list have the same size. // - The NEXT pointer implementing those linked lists is written // in the first bytes of the block itself, using the unsigned int type. // - The pointers on the first free block for each size are stored in an // array of pointers free[32] in the storage(x,y) descriptor. //////////////////////////////////////////////////////////////////////////////// // Allocation policy: // - The block size required by the user can be any value, but the allocated // block size can be larger than the requested size: // - The allocator computes actual_size, that is the smallest power of 2 // value larger or equal to the requested size AND larger or equal to // MALLOC_MIN_BLOCK_SIZE. // - It pop the linked list of free blocks corresponding to actual_size, // and returns the block B if the list[actual_size] is not empty. // - If the list[actual_size] is empty, it pop the list[actual_size * 2]. // If a block B' is found, it breaks this block in 2 B/2 blocks, returns // the first B/2 block and push the other B/2 block into list[actual_size]. // - If the list[actual_size * 2] is empty, it pop the list[actual_size * 4]. // If a block B is found, it break this block in 3 blocks B/4, B/4 and B/2, // returns the first B/4 block, push the other blocks B/4 and B/2 into // the proper lists. etc... // - If no block satisfying the request is available it returns a failure // (NULL pointer). // - This allocation policy has the nice following property: // If the vseg is aligned (the vseg base is a multiple of the // vseg size), all allocated blocks are aligned on the actual_size. //////////////////////////////////////////////////////////////////////////////// // Free policy: // - Each allocated block is registered in an alloc[] array of unsigned char. // - This registration is required by the free() operation, because the size // of the allocated block must be obtained from the base address of the block. // - The number of entries in this array is equal to the max number // of allocated block : MALLOC_LOCAL_STORE_SIZE / MALLOC_MIN_BLOCK_SIZE. // - For each allocated block, the value registered in the alloc[] array // is log2( size_of_allocated_block ). // - The index in this array is computed from the allocated block base address: // index = (block_base - vseg_base) / MALLOC_MIN_BLOCK_SIZE // - The alloc[] array is stored at the end of heap segment. This consume // (1 / MALLOC_MIN_BLOCK_SIZE) of the total storage capacity. //////////////////////////////////////////////////////////////////////////////// #ifndef _MALLOC_H_ #define _MALLOC_H_ #include "pthread.h" #define MALLOC_INITIALIZED 0xBABEF00D // magic number when initialised #define MALLOC_MIN_BLOCK_SIZE 0x40 // 64 bytes #define MALLOC_LOCAL_STORE_SIZE 0x800000 // 8 Mbytes #define MALLOC_MAX_CLUSTERS 0x100 // 256 clusters //////////////////////////////////////////////////////////////////////////////// // store(x,y) descriptor (one per cluster) //////////////////////////////////////////////////////////////////////////////// typedef struct malloc_store_s { pthread_mutex_t mutex; // lock protecting exclusive access unsigned int initialized; // initialised when value == MALLOC_INITIALIZED unsigned int cxy; // cluster identifier unsigned int store_base; // store base address unsigned int store_size; // store size (bytes) unsigned int alloc_base; // alloc[] array base address unsigned int alloc_size; // alloc[] array size (bytes) unsigned int free[32]; // array of addresses of first free block } malloc_store_t; /***************************************************************************************** * This function allocates bytes of memory in user space and returns a pointer * on the allocated buffer. The physical memory is allocated from store located in * the calling core cluster. ***************************************************************************************** * @ size : number of requested bytes. * @ returns a pointer on the allocated buffer if success / returns NULL if failure ****************************************************************************************/ void * malloc( unsigned int size ); /***************************************************************************************** * This function allocates bytes of memory in user space, and returns a pointer * to the allocated buffer. The pysical memory is allocated from store located in * cluster identified by the argument. ***************************************************************************************** * @ size : number of requested bytes. * @ cxy : target cluster identifier. * @ returns a pointer on the allocated buffer if success / returns NULL if failure ****************************************************************************************/ void * remote_malloc( unsigned int size, unsigned int cxy ); /***************************************************************************************** * This function releases the memory buffer identified by the argument, * to the store located in the calling core cluster. * It displays an error message, but does nothing if the ptr is illegal. ***************************************************************************************** * @ ptr : pointer on the released buffer. ****************************************************************************************/ void free( void * ptr ); /***************************************************************************************** * This function releases the memory buffer identified by the argument, * to the store identified by the argument. * It displays an error message, but does nothing if the ptr is illegal. ***************************************************************************************** * @ ptr : pointer on the released buffer. * @ cxy : target cluster identifier. ****************************************************************************************/ void remote_free( void * ptr, unsigned int cxy ); /***************************************************************************************** * This function releases the memory buffer identified by the argument, * to the store located in the calling core cluster, and allocates a new buffer * containing bytes from this store. * The content of the old buffer is copied to the new buffer, up to bytes. * It displays an error message, but does nothing if the ptr is illegal. ***************************************************************************************** * @ ptr : pointer on the released buffer. * @ size : new buffer requested size (bytes). * @ return a pointer on allocated buffer if success / return NULL if failure ****************************************************************************************/ void * realloc( void * ptr, unsigned int size ); /***************************************************************************************** * This function releases the memory buffer identified by the argument, * to the store located in cluster identified by the argument, and allocates * a new buffer containing bytes from this store. * The content of the old buffer is copied to the new buffer, up to bytes. * It displays an error message, but does nothing if the ptr is illegal. ***************************************************************************************** * @ ptr : pointer on the released buffer. * @ size : new buffer requested size (bytes). * @ cxy : target cluster identifier. * @ return a pointer on allocated buffer if success / return NULL if failure ****************************************************************************************/ void * remote_realloc( void * ptr, unsigned int size, unsigned int cxy ); /***************************************************************************************** * This function allocates enough space for objects that are bytes * of memory each from the store located in the calling core cluster. * The allocated memory is filled with bytes of value zero. ***************************************************************************************** * @ count : number of requested objects. * @ size : number of bytes per object. * @ returns a pointer on allocated buffer if success / returns NULL if failure ****************************************************************************************/ void * calloc( unsigned int count, unsigned int size ); /***************************************************************************************** * This function allocates enough space for objects that are bytes * of memory each from the store located in cluster identied by the argument. * The allocated memory is filled with bytes of value zero. ***************************************************************************************** * @ count : number of requested objects. * @ size : number of bytes per object. * @ cxy : target cluster identifier. * @ returns a pointer on allocated buffer if success / returns NULL if failure ****************************************************************************************/ void * remote_calloc( unsigned int count, unsigned int size, unsigned int cxy ); #endif // Local Variables: // tab-width: 4 // c-basic-offset: 4 // c-file-offsets:((innamespace . 0)(inline-open . 0)) // indent-tabs-mode: nil // End: // vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4