source: trunk/libs/mini-libc/malloc.c @ 441

Last change on this file since 441 was 439, checked in by satin@…, 7 years ago

Introduice new distributed Makefile architecture.
Remove deprecated sys/ directory

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