source: trunk/libs/malloc.c @ 426

Last change on this file since 426 was 426, checked in by alain, 6 years ago

The "nostdio" library has been integrated in the stdio library.

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