source: trunk/libs/mini-libc/malloc.h @ 440

Last change on this file since 440 was 439, checked in by satin@…, 6 years ago

Introduice new distributed Makefile architecture.
Remove deprecated sys/ directory

File size: 11.9 KB
Line 
1/*
2 * malloc.h - User space memory allocator.
3 *
4 * Author     Alain Greiner (2016,2017)
5 *
6 * Copyright (c) UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
14 * ALMOS-MKH is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24////////////////////////////////////////////////////////////////////////////////
25// General principles:
26// - In user space the HEAP zone spread between the ELF zone and the STACK zone,
27//   as defined in the kernel_config.h file.
28// - The malloc library uses the mmap() syscall to create - on demand -
29//   one vseg in a given cluster. The size of this vseg is defined below
30//   by the MALLOC_LOCAL_STORE_SIZE parameter.
31// - For a standard malloc(), the target cluster is the cluster containing
32//   the core running the client thread.
33// - For a remote_malloc(), the target cluster is explicitely defined
34//   by the argument.
35// - In each cluster, the available storage in virtual space is handled by a
36//   local allocator using the buddy algorithm.
37//
38// TODO : In this first implementation one single - fixed size - vseg
39//        is allocated on demand in each cluster.
40//        We should introduce the possibility to dynamically allocate
41//        several vsegs in each cluster, using several mmap when required.
42////////////////////////////////////////////////////////////////////////////////
43// Free blocks organisation in each cluster :
44// - All free blocks have a size that is a power of 2, larger or equal
45//   to MALLOC_MIN_BLOCK_SIZE (typically 64 bytes).
46// - All free blocks are aligned.
47// - They are pre-classed in an array of linked lists, where all blocks in a
48//   given list have the same size.
49// - The NEXT pointer implementing those linked lists is written
50//   in the first bytes of the block itself, using the unsigned int type.
51// - The pointers on the first free block for each size are stored in an
52//   array of pointers free[32] in the storage(x,y) descriptor.
53////////////////////////////////////////////////////////////////////////////////
54// Allocation policy:
55// - The block size required by the user can be any value, but the allocated
56//   block size can be larger than the requested size:
57// - The allocator computes actual_size, that is the smallest power of 2
58//   value larger or equal to the requested size AND larger or equal to
59//   MALLOC_MIN_BLOCK_SIZE.
60// - It pop the linked list of free blocks corresponding to actual_size,
61//   and returns the block B if the list[actual_size] is not empty.
62// - If the list[actual_size] is empty, it pop the list[actual_size * 2].
63//   If a block B' is found, it breaks this block in 2 B/2 blocks, returns
64//   the first B/2 block and push the other B/2 block into list[actual_size].
65// - If the list[actual_size * 2] is empty, it pop the list[actual_size * 4].
66//   If a block B is found, it break this block in 3 blocks B/4, B/4 and B/2,
67//   returns the first B/4 block, push the other blocks B/4 and B/2 into
68//   the proper lists. etc...
69// - If no block satisfying the request is available it returns a failure
70//   (NULL pointer).
71// - This allocation policy has the nice following property:
72//   If the vseg is aligned (the vseg base is a multiple of the
73//   vseg size), all allocated blocks are aligned on the actual_size.
74////////////////////////////////////////////////////////////////////////////////
75// Free policy:
76// - Each allocated block is registered in an alloc[] array of unsigned char.
77// - This registration is required by the free() operation, because the size
78//   of the allocated block must be obtained from the base address of the block. 
79// - The number of entries in this array is equal to the max number
80//   of allocated block : MALLOC_LOCAL_STORE_SIZE / MALLOC_MIN_BLOCK_SIZE.
81// - For each allocated block, the value registered in the alloc[] array
82//   is log2( size_of_allocated_block ).
83// - The index in this array is computed from the allocated block base address:
84//      index = (block_base - vseg_base) / MALLOC_MIN_BLOCK_SIZE
85// - The alloc[] array is stored at the end of heap segment. This consume
86//   (1 / MALLOC_MIN_BLOCK_SIZE) of the total storage capacity.
87////////////////////////////////////////////////////////////////////////////////
88
89#ifndef _MALLOC_H_
90#define _MALLOC_H_
91
92#include "pthread.h"
93
94#define MALLOC_INITIALIZED         0xBABEF00D   // magic number when initialised
95#define MALLOC_MIN_BLOCK_SIZE      0x40         // 64 bytes
96#define MALLOC_LOCAL_STORE_SIZE    0x800000     // 8 Mbytes     
97#define MALLOC_MAX_CLUSTERS        0x100        // 256 clusters
98
99////////////////////////////////////////////////////////////////////////////////
100// store(x,y) descriptor (one per cluster)
101////////////////////////////////////////////////////////////////////////////////
102
103typedef struct malloc_store_s
104{
105    pthread_mutex_t mutex;           // lock protecting exclusive access
106    unsigned int    initialized;     // initialised when value == MALLOC_INITIALIZED
107    unsigned int    cxy;             // cluster identifier 
108    unsigned int    store_base;      // store base address
109    unsigned int    store_size;      // store size (bytes)
110    unsigned int    alloc_base;      // alloc[] array base address
111    unsigned int    alloc_size;      // alloc[] array size (bytes)
112    unsigned int    free[32];        // array of addresses of first free block
113} 
114malloc_store_t;
115
116/*****************************************************************************************
117 * This function allocates <size> bytes of memory in user space and returns a pointer
118 * on the allocated buffer. The physical memory is allocated from store located in
119 * the calling core cluster.
120 *****************************************************************************************
121 * @ size    : number of requested bytes.
122 * @ returns a pointer on the allocated buffer if success / returns NULL if failure
123 ****************************************************************************************/
124void * malloc( unsigned int size );
125
126/*****************************************************************************************
127 * This function allocates <size> bytes of memory in user space, and returns a pointer
128 * to the allocated buffer. The pysical memory is allocated from store located in
129 * cluster identified by the <cxy> argument.
130 *****************************************************************************************
131 * @ size    : number of requested bytes.
132 * @ cxy     : target cluster identifier.
133 * @ returns a pointer on the allocated buffer if success / returns NULL if failure
134 ****************************************************************************************/
135void * remote_malloc( unsigned int size, 
136                      unsigned int cxy );
137
138/*****************************************************************************************
139 * This function releases the memory buffer identified by the <ptr> argument,
140 * to the store located in the calling core cluster.
141 * It displays an error message, but does nothing if the ptr is illegal.
142 *****************************************************************************************
143 * @ ptr   : pointer on the released buffer.
144 ****************************************************************************************/
145void free( void * ptr );
146
147/*****************************************************************************************
148 * This function releases the memory buffer identified by the <ptr> argument,
149 * to the store identified by the <cxy> argument.
150 * It displays an error message, but does nothing if the ptr is illegal.
151 *****************************************************************************************
152 * @ ptr   : pointer on the released buffer.
153 * @ cxy   : target cluster identifier.
154 ****************************************************************************************/
155void remote_free( void        * ptr,
156                  unsigned int  cxy );
157
158/*****************************************************************************************
159 * This function releases the memory buffer identified by the <ptr> argument,
160 * to the store located in the calling core cluster, and allocates a new buffer
161 * containing <size> bytes from this store.
162 * The content of the old buffer is copied to the new buffer, up to <size> bytes.
163 * It displays an error message, but does nothing if the ptr is illegal.
164 *****************************************************************************************
165 * @ ptr   : pointer on the released buffer.
166 * @ size  : new buffer requested size (bytes).
167 * @ return a pointer on allocated buffer if success / return NULL if failure
168 ****************************************************************************************/
169void * realloc( void        * ptr,
170                unsigned int  size );
171
172/*****************************************************************************************
173 * This function releases the memory buffer identified by the <ptr> argument,
174 * to the store located in cluster identified by the <cxy> argument, and allocates
175 * a new buffer containing <size> bytes from this store.
176 * The content of the old buffer is copied to the new buffer, up to <size> bytes.
177 * It displays an error message, but does nothing if the ptr is illegal.
178 *****************************************************************************************
179 * @ ptr     : pointer on the released buffer.
180 * @ size    : new buffer requested size (bytes).
181 * @ cxy     : target cluster identifier.
182 * @ return a pointer on allocated buffer if success / return NULL if failure
183 ****************************************************************************************/
184void * remote_realloc( void        * ptr,
185                       unsigned int  size,
186                       unsigned int  cxy );
187
188/*****************************************************************************************
189 * This function allocates enough space for <count> objects that are <size> bytes
190 * of memory each from the store located in the calling core cluster.
191 * The allocated memory is filled with bytes of value zero.
192 *****************************************************************************************
193 * @ count   : number of requested objects.
194 * @ size    : number of bytes per object.
195 * @ returns a pointer on allocated buffer if success / returns NULL if failure
196 ****************************************************************************************/
197void * calloc( unsigned int count,
198               unsigned int size );
199
200/*****************************************************************************************
201 * This function allocates enough space for <count> objects that are <size> bytes
202 * of memory each from the store located in cluster identied by the <cxy> argument.
203 * The allocated memory is filled with bytes of value zero.
204 *****************************************************************************************
205 * @ count   : number of requested objects.
206 * @ size    : number of bytes per object.
207 * @ cxy     : target cluster identifier.
208 * @ returns a pointer on allocated buffer if success / returns NULL if failure
209 ****************************************************************************************/
210void * remote_calloc( unsigned int count,
211                      unsigned int size,
212                      unsigned int cxy );
213
214#endif
215
216// Local Variables:
217// tab-width: 4
218// c-basic-offset: 4
219// c-file-offsets:((innamespace . 0)(inline-open . 0))
220// indent-tabs-mode: nil
221// End:
222// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
223
Note: See TracBrowser for help on using the repository browser.