source: trunk/libs/malloc.h@ 428

/*
 * 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 <size> 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 <size> 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 <cxy> 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 <ptr> 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 <ptr> argument,
 * to the store identified by the <cxy> 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 <ptr> argument,
 * to the store located in the calling core cluster, and allocates a new buffer
 * containing <size> bytes from this store. 
 * The content of the old buffer is copied to the new buffer, up to <size> 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 <ptr> argument,
 * to the store located in cluster identified by the <cxy> argument, and allocates
 * a new buffer containing <size> bytes from this store. 
 * The content of the old buffer is copied to the new buffer, up to <size> 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 <count> objects that are <size> 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 <count> objects that are <size> bytes
 * of memory each from the store located in cluster identied by the <cxy> 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