source: trunk/libs/malloc.c @ 416

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

Improve sys_exec.

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