source: trunk/libs/malloc.h @ 412

Last change on this file since 412 was 412, checked in by alain, 4 years ago

Introduce user libraries

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