source: soft/giet_vm/giet_common/kernel_malloc.c @ 467

Last change on this file since 467 was 466, checked in by alain, 10 years ago

1) Introducing a hierarchical, distributed lock, implemented as a

Sliced Binary Tree (sbt_lock_t) in the locks.c and locks.h files.

2) Introducing a kernel level distributed, remote_malloc() service,

In the kernel_malloc.c and kernel_malloc.h files.
This service requires one heap[x][y] global vseg per cluster.
This service is used by the distributed lock.

  • Property svn:executable set to *
File size: 14.5 KB
Line 
1////////////////////////////////////////////////////////////////////////////////
2// File     : kernel_malloc.c
3// Date     : 05/12/2014
4// Author   : alain greiner
5// Copyright (c) UPMC-LIP6
6////////////////////////////////////////////////////////////////////////////////
7//   Implementation note:
8// - As this code is used to implement the SBT lock ptotecting TTY0,
9//   all functions here use the kernel _nolock_printf() function.
10// - It must exist one vseg with the HEAP type in each cluster. The length
11//   must be a power of 2, and the base address must be aligned.
12// - All allocated blocks have a size that is a power of 2, larger or equal
13//   to MIN_BLOCK_SIZE (typically 64 bytes), and are aligned.
14// - All free blocks are pre-classed in 32 linked lists of free blocks, where
15//   all blocks in the same list have the same size.
16// - The NEXT pointer implementing those linked lists is written
17//   in the 4 first bytes of the block itself, using the unsigned int type.
18// - The pointers on the first free block for each size are stored in an
19//   array of pointers free[32] in the heap[x][y) structure itself.
20// - Each kernel_heap[x][y] structure is protected by a specific
21//   queuing spin-lock.
22// - The block size required can be any value, but the allocated block size
23//   is the smallest power of 2 value larger or equal to the requested size.
24// - It pop the linked list of free blocks corresponding to size,
25//   and returns the block B if the list[size] is not empty.
26// - If the list[size] is empty, it pop the list[size * 2].
27//   If a block B' is found, it break this block in 2 B/2 blocks, returns
28//   the first B/2 block and push the other B/2 block into list[size].
29// - If the list[size * 2] is empty, it pop the list[size * 4].
30//   If a block B is found, it break this block in 3 blocks B/4, B/4 and B/2,
31//   returns the first B/4 block, push the other blocks B/4 and B/2 into
32//   the proper lists. etc...
33////////////////////////////////////////////////////////////////////////////////
34
35#include "giet_config.h"
36#include "hard_config.h"
37#include "mapping_info.h"
38#include "kernel_malloc.h"
39#include "locks.h"
40#include "tty0.h"
41#include "utils.h"
42
43///////////////////////////////////////////////////////////////////////////////
44// Global variables defining the heap descriptors array (one heap per cluster)
45///////////////////////////////////////////////////////////////////////////////
46
47extern kernel_heap_t kernel_heap[X_SIZE][Y_SIZE];
48
49///////////////////////////////////////////////////////////////////////////////
50// Macro returning the smallest power of 2 larger or equal to size value
51///////////////////////////////////////////////////////////////////////////////
52#define GET_SIZE_INDEX(size)                (size <= 0x00000001) ? 0  :\
53                                            (size <= 0x00000002) ? 1  :\
54                                            (size <= 0x00000004) ? 2  :\
55                                            (size <= 0x00000008) ? 3  :\
56                                            (size <= 0x00000010) ? 4  :\
57                                            (size <= 0x00000020) ? 5  :\
58                                            (size <= 0x00000040) ? 6  :\
59                                            (size <= 0x00000080) ? 7  :\
60                                            (size <= 0x00000100) ? 8  :\
61                                            (size <= 0x00000200) ? 9  :\
62                                            (size <= 0x00000400) ? 10 :\
63                                            (size <= 0x00000800) ? 11 :\
64                                            (size <= 0x00001000) ? 12 :\
65                                            (size <= 0x00002000) ? 13 :\
66                                            (size <= 0x00004000) ? 14 :\
67                                            (size <= 0x00008000) ? 15 :\
68                                            (size <= 0x00010000) ? 16 :\
69                                            (size <= 0x00020000) ? 17 :\
70                                            (size <= 0x00040000) ? 18 :\
71                                            (size <= 0x00080000) ? 19 :\
72                                            (size <= 0x00100000) ? 20 :\
73                                            (size <= 0x00200000) ? 21 :\
74                                            (size <= 0x00400000) ? 22 :\
75                                            (size <= 0x00800000) ? 23 :\
76                                            (size <= 0x01000000) ? 24 :\
77                                            (size <= 0x02000000) ? 25 :\
78                                            (size <= 0x04000000) ? 26 :\
79                                            (size <= 0x08000000) ? 27 :\
80                                            (size <= 0x10000000) ? 28 :\
81                                            (size <= 0x20000000) ? 29 :\
82                                            (size <= 0x40000000) ? 30 :\
83                                            (size <= 0x80000000) ? 31 :\
84                                                                   32
85#if GIET_DEBUG_SYS_MALLOC
86////////////////////////////////////////////////
87static void _display_free_array( unsigned int x,
88                                 unsigned int y )
89{
90    _nolock_printf(" Kernel Heap[%d][%d]\n"
91                   " - heap_base   = %x\n"
92                   " - heap_size   = %x\n"
93                   " - free[0]     = %x\n"
94                   " - free[1]     = %x\n"
95                   " - free[2]     = %x\n"
96                   " - free[3]     = %x\n"
97                   " - free[4]     = %x\n"
98                   " - free[5]     = %x\n"
99                   " - free[6]     = %x\n"
100                   " - free[7]     = %x\n"
101                   " - free[8]     = %x\n"
102                   " - free[9]     = %x\n"
103                   " - free[10]    = %x\n"
104                   " - free[11]    = %x\n"
105                   " - free[12]    = %x\n"
106                   " - free[13]    = %x\n"
107                   " - free[14]    = %x\n"
108                   " - free[15]    = %x\n"
109                   " - free[16]    = %x\n"
110                   " - free[17]    = %x\n"
111                   " - free[18]    = %x\n"
112                   " - free[19]    = %x\n"
113                   " - free[20]    = %x\n"
114                   " - free[21]    = %x\n"
115                   " - free[22]    = %x\n"
116                   " - free[23]    = %x\n",
117                   kernel_heap[x][y].x, kernel_heap[x][y].y, 
118                   kernel_heap[x][y].heap_base, kernel_heap[x][y].heap_size, 
119                   kernel_heap[x][y].free[0] , kernel_heap[x][y].free[1], 
120                   kernel_heap[x][y].free[2] , kernel_heap[x][y].free[3],
121                   kernel_heap[x][y].free[4] , kernel_heap[x][y].free[5],
122                   kernel_heap[x][y].free[6] , kernel_heap[x][y].free[7],
123                   kernel_heap[x][y].free[8] , kernel_heap[x][y].free[9],
124                   kernel_heap[x][y].free[10], kernel_heap[x][y].free[11],
125                   kernel_heap[x][y].free[12], kernel_heap[x][y].free[13],
126                   kernel_heap[x][y].free[14], kernel_heap[x][y].free[15],
127                   kernel_heap[x][y].free[16], kernel_heap[x][y].free[17],
128                   kernel_heap[x][y].free[18], kernel_heap[x][y].free[19],
129                   kernel_heap[x][y].free[20], kernel_heap[x][y].free[21],
130                   kernel_heap[x][y].free[22], kernel_heap[x][y].free[23]);
131}  // end display_free array()
132#endif
133
134
135
136
137/////////////////////////////////////////////
138void _get_heap_info( unsigned int* heap_base,
139                     unsigned int* heap_size,
140                     unsigned int  x,
141                     unsigned int  y )
142{
143    mapping_header_t  * header   = (mapping_header_t *)SEG_BOOT_MAPPING_BASE;
144    mapping_vseg_t    * vsegs    = _get_vseg_base(header);
145    mapping_vobj_t    * vobjs    = _get_vobj_base(header);
146    mapping_pseg_t    * psegs    = _get_pseg_base(header);
147    mapping_cluster_t * clusters = _get_cluster_base(header);
148
149    unsigned int vseg_id;
150    unsigned int vobj_id;
151    unsigned int pseg_id;
152    unsigned int cluster_id;
153
154    // checking coordinates
155    if ( (x >= X_SIZE) || (y >= Y_SIZE) )
156    {
157        _nolock_printf("[GIET ERROR] _get_heap_info() illegal (%d,%d) coordinates\n",
158                       x , y );
159        _exit();
160    }
161
162    // scan all global vsegs
163    for ( vseg_id = 0 ; vseg_id < header->globals ; vseg_id++ )
164    {
165        pseg_id    = vsegs[vseg_id].psegid;
166        cluster_id = psegs[pseg_id].clusterid;
167        vobj_id    = vsegs[vseg_id].vobj_offset;
168        if ( (vobjs[vobj_id].type == VOBJ_TYPE_HEAP) &&
169             (clusters[cluster_id].x == x) && 
170             (clusters[cluster_id].y == y) )
171        {
172            *heap_base = vsegs[vseg_id].vbase;
173            *heap_size = vobjs[vobj_id].length;
174            return;
175        }
176    }
177
178    // exit if not found
179    _nolock_printf("[GIET ERROR] _get_heap_info() heap[%d][%d] vseg not found\n",
180                   x , y );
181    _exit();
182
183} // end _get_heap_info()
184
185
186
187/////////////////
188void _heap_init()
189{
190    unsigned int heap_base;
191    unsigned int heap_size;
192    unsigned int heap_index;
193
194    unsigned int index;
195    unsigned int x;
196    unsigned int y;
197
198    for ( x = 0 ; x < X_SIZE ; x++ )
199    {
200        for ( y = 0 ; y < Y_SIZE ; y++ )
201        {
202            // get heap_base, heap size, and heap index
203            _get_heap_info( &heap_base, &heap_size, x, y );
204            heap_index = GET_SIZE_INDEX( heap_size );
205
206            // checking heap segment constraints
207            if ( heap_size != (1<<heap_index) )
208            {
209                _nolock_printf("[GIET ERROR] in _heap_init()"
210                        " kernel_heap[‰d,‰d] not power of 2\n", x , y );
211                _exit();
212            }
213            if ( heap_base % heap_size ) 
214            {
215                _nolock_printf("[GIET ERROR] in _heap_init()"
216                        " kernel_heap[‰d,‰d] not aligned\n", x , y );
217                _exit();
218            }
219
220            // initialise the free[] array
221            for ( index = 0 ; index < 32 ; index++ ) 
222            {
223                if (index == heap_index) kernel_heap[x][y].free[index] = heap_base;
224                else                     kernel_heap[x][y].free[index] = 0;
225            }
226            unsigned int* ptr = (unsigned int*)heap_base;
227            *ptr = 0;
228
229            // initialise kernel_heap[x][y] descriptor
230            kernel_heap[x][y].x          = x;
231            kernel_heap[x][y].y          = y;
232            kernel_heap[x][y].heap_base  = heap_base;
233            kernel_heap[x][y].heap_size  = heap_size;
234
235            _spin_lock_init( &kernel_heap[x][y].lock );
236
237#if GIET_DEBUG_SYS_MALLOC
238_nolock_printf("\n[DEBUG KERNEL_MALLOC] Completing kernel_heap[%d][%d] initialisation\n",
239               x, y );
240_display_free_array(x,y);
241#endif
242               
243        }
244    }
245}  // end _heap_init()
246
247
248
249//////////////////////////////////////////////
250unsigned int split_block( kernel_heap_t* heap,
251                          unsigned int   vaddr, 
252                          unsigned int   searched_index,
253                          unsigned int   requested_index )
254{
255    // push the upper half block into free[searched_index-1]
256    unsigned int* new            = (unsigned int*)(vaddr + (1<<(searched_index-1)));
257    *new                         = heap->free[searched_index-1]; 
258    heap->free[searched_index-1] = (unsigned int)new;
259       
260    if ( searched_index == requested_index + 1 )  // terminal case: return lower half block
261    {
262        return vaddr;
263    }
264    else            // non terminal case : lower half block must be split again
265    {                               
266        return split_block( heap, vaddr, searched_index-1, requested_index );
267    }
268} // end split_block()
269
270
271
272/////////////////////////////////////////////
273unsigned int get_block( kernel_heap_t* heap,
274                        unsigned int   searched_index,
275                        unsigned int   requested_index )
276{
277    // test terminal case
278    if ( (1<<searched_index) > heap->heap_size )  // failure : return a NULL value
279    {
280        return 0;
281    }
282    else                            // search a block in free[searched_index]
283    {
284        unsigned int vaddr = heap->free[searched_index];
285        if ( vaddr == 0 )     // block not found : search in free[searched_index+1]
286        {
287            return get_block( heap, searched_index+1, requested_index );
288        }
289        else                // block found : pop it from free[searched_index]
290        {
291            // pop the block from free[searched_index]
292            unsigned int next = *((unsigned int*)vaddr); 
293            heap->free[searched_index] = next;
294           
295            // test if the block must be split
296            if ( searched_index == requested_index )  // no split required
297            {
298                return vaddr;
299            }
300            else                                      // split is required
301            {
302                return split_block( heap, vaddr, searched_index, requested_index );
303            }
304        } 
305    }
306} // end get_block()
307
308
309
310////////////////////////////////////////
311void* _remote_malloc( unsigned int size,
312                      unsigned int x,
313                      unsigned int y ) 
314{
315    // checking arguments
316    if (size == 0) 
317    {
318        _nolock_printf("[GIET ERROR] _remote_malloc() : requested size = 0 \n");
319        _exit();
320    }
321    if ( x >= X_SIZE )
322    {
323        _nolock_printf("[GIET ERROR] _remote_malloc() : x coordinate too large\n");
324        _exit();
325    }
326    if ( y >= Y_SIZE )
327    {
328        _nolock_printf("[GIET ERROR] _remote_malloc() : y coordinate too large\n");
329        _exit();
330    }
331
332    // normalize size
333    if ( size < MIN_BLOCK_SIZE ) size = MIN_BLOCK_SIZE;
334
335    // compute requested_index for the free[] array
336    unsigned int requested_index = GET_SIZE_INDEX( size );
337
338    // take the lock
339    _spin_lock_acquire( &kernel_heap[x][y].lock );
340
341    // call the recursive function get_block
342    unsigned int base = get_block( &kernel_heap[x][y], 
343                                   requested_index, 
344                                   requested_index );
345    // release the lock
346    _spin_lock_release( &kernel_heap[x][y].lock );
347 
348#if GIET_DEBUG_SYS_MALLOC
349_nolock_printf("\n[DEBUG KERNEL_MALLOC] malloc vaddr %x from kernel_heap[%d][%d]\n", 
350               base , x , y );
351_display_free_array(x,y);
352#endif
353
354    return (void*)base;
355
356} // end remote_malloc()
357
358
359
360// Local Variables:
361// tab-width: 4
362// c-basic-offset: 4
363// c-file-offsets:((innamespace . 0)(inline-open . 0))
364// indent-tabs-mode: nil
365// End:
366// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
367
368
369
Note: See TracBrowser for help on using the repository browser.