source: trunk/libs/libalmos-mkh/almos-mkh-memory.c @ 444

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

add newlib,libalmos-mkh, restructure shared_syscalls.h and mini-libc

File size: 19.6 KB
Line 
1/*
2 * malloc.h - User space memory allocator implementation.
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#include <stdio.h>
25#include <hal_user.h>
26#include <almos-mkh.h>
27#include <string.h>
28#include <sys/mman.h>
29#include <syscalls_numbers.h>
30#include <pthread.h>
31
32#define  MALLOC_DEBUG  0
33 
34/////////////////////////////////////////////////////////////////////////////////////////
35// Global variable defining the allocator array (one per cluster)
36// This array (about 16 Kbytes ) will be stored in the data segment
37// of any application linked with this malloc libray.
38/////////////////////////////////////////////////////////////////////////////////////////
39
40malloc_store_t   store[MALLOC_MAX_CLUSTERS];
41
42// Macro returning the smallest power of 2 larger or equal to size value
43
44#define GET_SIZE_INDEX(size)                (size <= 0x00000001) ? 0  :\
45                                            (size <= 0x00000002) ? 1  :\
46                                            (size <= 0x00000004) ? 2  :\
47                                            (size <= 0x00000008) ? 3  :\
48                                            (size <= 0x00000010) ? 4  :\
49                                            (size <= 0x00000020) ? 5  :\
50                                            (size <= 0x00000040) ? 6  :\
51                                            (size <= 0x00000080) ? 7  :\
52                                            (size <= 0x00000100) ? 8  :\
53                                            (size <= 0x00000200) ? 9  :\
54                                            (size <= 0x00000400) ? 10 :\
55                                            (size <= 0x00000800) ? 11 :\
56                                            (size <= 0x00001000) ? 12 :\
57                                            (size <= 0x00002000) ? 13 :\
58                                            (size <= 0x00004000) ? 14 :\
59                                            (size <= 0x00008000) ? 15 :\
60                                            (size <= 0x00010000) ? 16 :\
61                                            (size <= 0x00020000) ? 17 :\
62                                            (size <= 0x00040000) ? 18 :\
63                                            (size <= 0x00080000) ? 19 :\
64                                            (size <= 0x00100000) ? 20 :\
65                                            (size <= 0x00200000) ? 21 :\
66                                            (size <= 0x00400000) ? 22 :\
67                                            (size <= 0x00800000) ? 23 :\
68                                            (size <= 0x01000000) ? 24 :\
69                                            (size <= 0x02000000) ? 25 :\
70                                            (size <= 0x04000000) ? 26 :\
71                                            (size <= 0x08000000) ? 27 :\
72                                            (size <= 0x10000000) ? 28 :\
73                                            (size <= 0x20000000) ? 29 :\
74                                            (size <= 0x40000000) ? 30 :\
75                                            (size <= 0x80000000) ? 31 :\
76                                                                   32
77
78////////////////////////////////////////////////////////////////////////////////////////////
79// This static function display the current state of the allocator in cluster <cxy>.
80////////////////////////////////////////////////////////////////////////////////////////////
81
82#if 0
83static void display_free_array( unsigned int cxy )
84{
85    unsigned int next;
86    unsigned int id;
87    unsigned int iter;
88
89    printf("\n*****   store[%x] base = %x / size = %x\n",
90    cxy , store[cxy].store_base, store[cxy].store_size );
91    for ( id = 0 ; id < 32 ; id++ )
92    {
93        next = store[cxy].free[id];
94        printf(" - free[%d] = " , id );
95        iter = 0;
96        while ( next != 0 )
97        {
98            printf("%x | ", next );
99            next = (*(unsigned int*)next);
100            iter++;
101        }
102        printf("0\n");
103    }
104}  // end display_free_array()
105#endif
106
107
108////////////////////////////////////////////////////////////////////i//////////////////////
109// This static function initialises the store in the cluster identified by the <cxy>
110// arguments. It is called by the malloc() or remote_malloc when a specific store(x,y)
111// is accessed for the first time by a remote() or remote_malloc() request.
112// It uses the mmap( MAP_REMOTE ) syscall to allocate a new vseg mapped in cluster (cxy).
113////////////////////////////////////////////////////////////////////i//////////////////////
114// @ cxy        : target cluster identifier (fixed format).
115// @ store_size : store size (bytes).
116// # return without setting the initialized field in store(cxy) if failure.
117////////////////////////////////////////////////////////////////////i//////////////////////
118static void store_init( unsigned int cxy,
119                        unsigned int store_size )
120{
121    unsigned int   store_base;       // store base address
122    unsigned int   free_index;       // index in free[array]
123
124    unsigned int   alloc_base;       // alloc[] array base
125    unsigned int   alloc_size;       // alloc[] array size
126    unsigned int   alloc_index;      // index in alloc[array]
127
128    unsigned int   iter;             // iterator
129
130#if MALLOC_DEBUG
131printf("\n[MALLOC] %s : enter for store[%x] / size = %x\n",
132__FUNCTION__, cxy, store_size );
133#endif
134
135    // get index in free[] array from size
136    free_index = GET_SIZE_INDEX( store_size );
137
138    // check store size power of 2
139    if( store_size != (1<<free_index) )
140    {
141        printf("\n[ERROR] in %s : store[%x] size not power of 2 / size = %x\n",
142        __FUNCTION__, cxy , store_size );
143        return;
144    }
145
146    // allocate store in virtual space
147    void * vadr = mmap( NULL,                     // MAP_FIXED not supported
148                        store_size,
149                        PROT_READ | PROT_WRITE,
150                        MAP_REMOTE| MAP_SHARED,
151                        cxy,                      // fd is cluster identifier
152                        0 );                      // offset unused
153
154    if( vadr == NULL )
155    {
156        printf("\n[ERROR] in %s : cannot mmap store[%x]\n",
157        __FUNCTION__, cxy );
158        return;
159    }
160
161    store_base = (unsigned int)vadr;
162
163    // check allocated store alignment
164    if( store_base % store_size )
165    {
166        printf("\n[ERROR] in %s : store[%x] not aligned / base = %x / size = %x\n",
167        __FUNCTION__, cxy , store_base , store_size );
168        return;
169    }
170
171#if MALLOC_DEBUG
172printf("\n[MALLOC] %s : mmap done for store[%x] / base = %x\n",
173__FUNCTION__, cxy, store_base );
174#endif
175
176    // compute size of block containing alloc[] array
177    alloc_size = store_size / MALLOC_MIN_BLOCK_SIZE;
178    if ( alloc_size < MALLOC_MIN_BLOCK_SIZE) alloc_size = MALLOC_MIN_BLOCK_SIZE;
179
180    // get index for the corresponding block
181    alloc_index = GET_SIZE_INDEX( alloc_size );
182
183    // compute alloc[] array base address
184    alloc_base = store_base + store_size - alloc_size;
185
186    // reset the free[] array
187    for ( iter = 0 ; iter < 32 ; iter++ )
188    {
189        store[cxy].free[iter] = 0;
190    }
191
192    // DEPRECATED: we don't reset the alloc_size array
193    // because we don't want to allocate the physical memory
194    // when the heap is created  [AG]
195    // memset( (void *)alloc_base , 0 , alloc_size );
196 
197    // split the store into various sizes blocks,
198    // initializes the free[] array and NEXT pointers
199    // base is the block base address
200    unsigned int   base = store_base;
201    unsigned int * ptr;
202    for ( iter = free_index-1 ; iter >= alloc_index ; iter-- )
203    {
204        store[cxy].free[iter] = base;
205        ptr = (unsigned int*)base;
206        *ptr = 0;
207        base = base + (1<<iter);
208    }
209
210    // initialize store mutex
211    if( pthread_mutex_init( &store[cxy].mutex , NULL ) )
212    {
213        printf("\n[ERROR] in %s : cannot initialize mutex for store[%x]\n", 
214        __FUNCTION__, cxy );
215        return;
216    }
217
218    store[cxy].cxy         = cxy;
219    store[cxy].store_base  = store_base;
220    store[cxy].store_size  = store_size;
221    store[cxy].alloc_size  = alloc_size;
222    store[cxy].alloc_base  = alloc_base;
223    store[cxy].initialized = MALLOC_INITIALIZED;
224
225
226#if MALLOC_DEBUG
227printf("\n[MALLOC] %s : completes store[%x] initialisation\n",
228__FUNCTION__, cxy );
229
230display_free_array( cxy );
231#endif
232
233}  // end store_init()
234
235////////////////////////////////////////////////////////
236static unsigned int split_block( malloc_store_t * store,
237                                 unsigned int     vaddr, 
238                                 unsigned int     searched_index,
239                                 unsigned int     requested_index )
240{
241    // push the upper half block into free[searched_index-1]
242    unsigned int* new            = (unsigned int*)(vaddr + (1<<(searched_index-1)));
243    *new                         = store->free[searched_index-1]; 
244    store->free[searched_index-1] = (unsigned int)new;
245       
246    if ( searched_index == requested_index + 1 )  // terminal case: return lower half block
247    {
248        return vaddr;
249    }
250    else            // non terminal case : lower half block must be split again
251    {                               
252        return split_block( store, vaddr, searched_index-1, requested_index );
253    }
254} // end split_block()
255
256//////////////////////////////////////////////////////
257static unsigned int get_block( malloc_store_t * store,
258                               unsigned int     searched_index,
259                               unsigned int     requested_index )
260{
261    // test terminal case
262    if ( (1<<searched_index) > store->store_size )  // failure : return a NULL value
263    {
264        return 0;
265    }
266    else                            // search a block in free[searched_index]
267    {
268        unsigned int vaddr = store->free[searched_index];
269        if ( vaddr == 0 )     // block not found : search in free[searched_index+1]
270        {
271            return get_block( store, searched_index+1, requested_index );
272        }
273        else                // block found : pop it from free[searched_index]
274        {
275            // pop the block from free[searched_index]
276            unsigned int next = *((unsigned int*)vaddr); 
277            store->free[searched_index] = next;
278           
279            // test if the block must be split
280            if ( searched_index == requested_index )  // no split required
281            {
282                return vaddr;
283            }
284            else                                      // split is required
285            {
286                return split_block( store, vaddr, searched_index, requested_index );
287            }
288        } 
289    }
290} // end get_block()
291
292////////////////////////////////////////
293void * remote_malloc( unsigned int size,
294                      unsigned int cxy )
295{
296
297#if MALLOC_DEBUG
298printf("\n[MALLOC] %s : enter for size = %x / cxy = %x\n",
299__FUNCTION__ , size , cxy );
300#endif
301
302    // check arguments
303    if( size == 0 )
304    {
305        printf("\n[ERROR] in %s : requested size = 0 \n",
306        __FUNCTION__ );
307        return NULL;
308    }
309    if( cxy >= MALLOC_MAX_CLUSTERS )
310    {
311        printf("\n[ERROR] in %s : illegal cluster %x\n",
312        __FUNCTION__ , cxy );
313        return NULL;
314    }
315
316    // initializes target store if required
317    if( store[cxy].initialized != MALLOC_INITIALIZED )
318    {
319        store_init( cxy , MALLOC_LOCAL_STORE_SIZE );
320
321        if( store[cxy].initialized != MALLOC_INITIALIZED )
322        {
323            printf("\n[ERROR] in %s : cannot allocate store in cluster %x\n",
324            __FUNCTION__ , cxy );
325            return NULL;
326        }
327    }
328
329    // normalize size
330    if ( size < MALLOC_MIN_BLOCK_SIZE ) size = MALLOC_MIN_BLOCK_SIZE;
331
332    // compute requested_index for the free[] array
333    unsigned int requested_index = GET_SIZE_INDEX( size );
334
335    // take the lock protecting access to store[cxy]
336    pthread_mutex_lock( &store[cxy].mutex );
337
338    // call the recursive function get_block
339    unsigned int base = get_block( &store[cxy], 
340                                   requested_index, 
341                                   requested_index );
342
343    // check block found
344    if (base == 0)
345    {
346        pthread_mutex_unlock( &store[cxy].mutex );
347        printf("\n[ERROR] in %s : no more space in cluster %x\n",
348        __FUNCTION__ , cxy );
349        return NULL;
350    }
351
352    // compute pointer in alloc[] array
353    unsigned        offset = (base - store[cxy].store_base) / MALLOC_MIN_BLOCK_SIZE;
354    unsigned char * ptr    = (unsigned char*)(store[cxy].alloc_base + offset);
355
356    // DEPRECATED : we don't check the alloc[] array,
357    // because it has not been initialised, to avoid
358    // physical memory allocation at heap creation [AG]
359    // if ( *ptr != 0 )
360    // {
361    //    pthread_mutex_unlock( &store[cxy].mutex );
362    //    printf("\n[PANIC] in %s : allocate an already allocated block...\n",
363    //    __FUNCTION__ );
364    //    return NULL;
365    // }
366
367    // update alloc_array
368    *ptr = requested_index;
369
370    // release the lock
371    pthread_mutex_unlock( &store[cxy].mutex );
372 
373#if MALLOC_DEBUG
374printf("\n[MALLOC] %s : exit / base = %x / size = %x / from store[%x]\n",
375__FUNCTION__, base , size , cxy );
376#endif
377
378    return (void*) base;
379
380} // end remote_malloc()
381
382
383
384//////////////////////////////////////////
385void * remote_calloc ( unsigned int count,
386                       unsigned int size,
387                       unsigned int cxy )
388{
389    void * ptr = remote_malloc( count * size , cxy );
390    memset( ptr , 0 , count * size );
391    return ptr;
392}
393
394//////////////////////////////////
395void * remote_realloc( void * ptr,
396                       unsigned int size,
397                       unsigned int cxy )
398{
399    // simple allocation when (ptr == NULL)
400    if( ptr == NULL )
401    {
402        return remote_malloc( size , cxy );
403    }
404
405    // simple free when (size == 0)
406    if( size == 0 )
407    {
408        remote_free( ptr , cxy );
409        return NULL;
410    }
411
412    // check cxy and ptr in general case
413    if( cxy >= MALLOC_MAX_CLUSTERS )
414    {
415        printf("\n[ERROR] in %s : illegal cluster index %x\n",
416        __FUNCTION__ , cxy );
417        return NULL;
418    }
419
420    unsigned int base = (unsigned int)ptr;
421
422    if( (base < store[cxy].store_base) || 
423        (base >= (store[cxy].store_base + store[cxy].store_size)) )
424    {
425        printf("\n[ERROR] in %s : illegal pointer = %x\n",
426        __FUNCTION__, ptr );
427        return NULL;
428    }
429 
430    // compute index in free[] array
431    int index = (base - store[cxy].store_base) / MALLOC_MIN_BLOCK_SIZE;
432
433    // compute old size
434    char * pchar = (char *) (store[cxy].alloc_base + index);
435    int old_size = 1 << ((int) *pchar);
436
437    // allocate a new block
438    void * new_ptr = remote_malloc( size , cxy );
439
440    // save old data to new block
441    int min_size = (size < old_size) ? size : old_size;
442    memcpy( new_ptr, ptr, min_size );
443
444    // release old block
445    remote_free( ptr , cxy );
446
447    return new_ptr;
448}
449
450//////////////////////////////////////////////////////
451static void update_free_array( malloc_store_t * store,
452                               unsigned int     base,
453                               unsigned int     size_index )
454{
455    // This recursive function try to merge the released block
456    // with the companion block if this companion block is free.
457    // This companion has the same size, and almost the same address
458    // (only one address bit is different)
459    // - If the companion is not in free[size_index],
460    //   the released block is pushed in free[size_index].
461    // - If the companion is found, it is evicted from free[size_index]
462    //   and the merged bloc is pushed in the free[size_index+1].
463
464
465    // compute released block size
466    unsigned int size = 1<<size_index;
467
468    // compute companion block and merged block base addresses
469    unsigned int companion_base; 
470    unsigned int merged_base; 
471
472    if ( (base & size) == 0 )   // the released block is aligned on (2*size)
473    {
474        companion_base  = base + size;
475        merged_base     = base;
476    }
477    else
478    {
479        companion_base  = base - size;
480        merged_base     = base - size;
481    }
482
483    // scan all blocks in free[size_index]
484    // the iter & prev variables are actually addresses
485    unsigned int  found = 0;
486    unsigned int  iter  = store->free[size_index];
487    unsigned int  prev  = (unsigned int)&store->free[size_index];
488    while ( iter ) 
489    {
490        if ( iter == companion_base ) 
491        {
492            found = 1;
493            break;
494        }
495        prev = iter;
496        iter = *(unsigned int*)iter;
497    }
498
499    if ( found == 0 )  // Companion not found => push in free[size_index] 
500    {
501        *(unsigned int*)base   = store->free[size_index];
502        store->free[size_index] = base;
503    }
504    else               // Companion found : merge
505    {
506        // evict the searched block from free[size_index]
507        *(unsigned int*)prev = *(unsigned int*)iter;
508
509        // call the update_free() function for free[size_index+1]
510        update_free_array( store, merged_base , size_index+1 );
511    }
512}  // end update_free_array()
513
514////////////////////////////////////
515void remote_free( void        * ptr,
516                  unsigned int  cxy )
517{
518
519#if MALLOC_DEBUG
520printf("\n[MALLOC] %s : enter for block = %x / cxy = %x\n",
521__FUNCTION__, ptr, cxy );
522#endif
523
524    unsigned int base = (unsigned int)ptr;
525
526    // check cxy value
527    if( cxy >= MALLOC_MAX_CLUSTERS )
528    {
529        printf("\n[ERROR] in %s : illegal cluster index %x\n",
530        __FUNCTION__ , cxy );
531        return;
532    }
533
534    // check ptr value
535    if( (base < store[cxy].store_base) || 
536        (base >= (store[cxy].store_base + store[cxy].store_size)) )
537    {
538        printf("\n[ERROR] in %s : illegal pointer for released block = %x\n",
539        __FUNCTION__, ptr );
540        return;
541    }
542 
543    // get the lock protecting store[cxy]
544    pthread_mutex_lock( &store[cxy].mutex );
545
546    // compute released block index in alloc[] array
547    unsigned index = (base - store[cxy].store_base ) / MALLOC_MIN_BLOCK_SIZE;
548 
549    // get the released block size_index
550    unsigned char* pchar      = (unsigned char*)(store[cxy].alloc_base + index);
551    unsigned int   size_index = (unsigned int)*pchar;
552
553    // check block is allocated
554    if ( size_index == 0 )
555    {
556        pthread_mutex_unlock( &store[cxy].mutex );
557        printf("\n[ERROR] in %s : released block not allocated / ptr = %x\n",
558        __FUNCTION__, ptr );
559        return;
560    }
561
562    // check released block alignment
563    if ( base % (1 << size_index) )
564    {
565        pthread_mutex_unlock( &store[cxy].mutex );
566        printf("\n[ERROR] in %s : released block not aligned / ptr = %x\n",
567        __FUNCTION__, ptr );
568        return;
569    }
570
571    // reset the alloc[index] entry
572    *pchar = 0;
573
574    // call the recursive function update_free_array()
575    update_free_array( &store[cxy], base, size_index ); 
576
577    // release the lock
578    pthread_mutex_unlock( &store[cxy].mutex );
579
580#if MALLOC_DEBUG
581printf("\n[MALLOC] %s : conmpletes for block = %x / cxy = %x\n",
582__FUNCTION__, ptr, cxy );
583#endif
584
585} // end remote_free()
586
587// Local Variables:
588// tab-width: 4
589// c-basic-offset: 4
590// c-file-offsets:((innamespace . 0)(inline-open . 0))
591// indent-tabs-mode: nil
592// End:
593// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
594
595
596
Note: See TracBrowser for help on using the repository browser.