source: trunk/libs/malloc.c @ 412

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

Introduce user libraries

  • Property svn:executable set to *
File size: 20.2 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// @ 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    // reset the alloc_size array
188    // memset( (void *)alloc_base , 0 , alloc_size );
189 
190    // split the store into various sizes blocks,
191    // initializes the free[] array and NEXT pointers
192    // base is the block base address
193    unsigned int   base = store_base;
194    unsigned int * ptr;
195    for ( iter = free_index-1 ; iter >= alloc_index ; iter-- )
196    {
197        store[cxy].free[iter] = base;
198        ptr = (unsigned int*)base;
199        *ptr = 0;
200        base = base + (1<<iter);
201    }
202
203    // initialize store mutex
204    if( pthread_mutex_init( &store[cxy].mutex , NULL ) )
205    {
206        printf("\n[ERROR] in %s : cannot initialize mutex for store[%x]\n", 
207        __FUNCTION__, cxy );
208        return;
209    }
210
211    store[cxy].cxy         = cxy;
212    store[cxy].store_base  = store_base;
213    store[cxy].store_size  = store_size;
214    store[cxy].alloc_size  = alloc_size;
215    store[cxy].alloc_base  = alloc_base;
216    store[cxy].initialized = MALLOC_INITIALIZED;
217
218#if MALLOC_DEBUG
219printf("\n[MALLOC] %s completes store[%x] initialisation\n",
220__FUNCTION__, cxy );
221#endif
222
223}  // end store_init()
224
225////////////////////////////////////////////////////////
226static unsigned int split_block( malloc_store_t * store,
227                                 unsigned int     vaddr, 
228                                 unsigned int     searched_index,
229                                 unsigned int     requested_index )
230{
231    // push the upper half block into free[searched_index-1]
232    unsigned int* new            = (unsigned int*)(vaddr + (1<<(searched_index-1)));
233    *new                         = store->free[searched_index-1]; 
234    store->free[searched_index-1] = (unsigned int)new;
235       
236    if ( searched_index == requested_index + 1 )  // terminal case: return lower half block
237    {
238        return vaddr;
239    }
240    else            // non terminal case : lower half block must be split again
241    {                               
242        return split_block( store, vaddr, searched_index-1, requested_index );
243    }
244} // end split_block()
245
246//////////////////////////////////////////////////////
247static unsigned int get_block( malloc_store_t * store,
248                               unsigned int     searched_index,
249                               unsigned int     requested_index )
250{
251    // test terminal case
252    if ( (1<<searched_index) > store->store_size )  // failure : return a NULL value
253    {
254        return 0;
255    }
256    else                            // search a block in free[searched_index]
257    {
258        unsigned int vaddr = store->free[searched_index];
259        if ( vaddr == 0 )     // block not found : search in free[searched_index+1]
260        {
261            return get_block( store, searched_index+1, requested_index );
262        }
263        else                // block found : pop it from free[searched_index]
264        {
265            // pop the block from free[searched_index]
266            unsigned int next = *((unsigned int*)vaddr); 
267            store->free[searched_index] = next;
268           
269            // test if the block must be split
270            if ( searched_index == requested_index )  // no split required
271            {
272                return vaddr;
273            }
274            else                                      // split is required
275            {
276                return split_block( store, vaddr, searched_index, requested_index );
277            }
278        } 
279    }
280} // end get_block()
281
282////////////////////////////////////////
283void * remote_malloc( unsigned int size,
284                      unsigned int cxy )
285{
286
287#if MALLOC_DEBUG
288printf("\n[MALLOC] %s : enter for size = %x / cxy = %x\n",
289__FUNCTION__ , size , cxy );
290#endif
291
292    // check arguments
293    if( size == 0 )
294    {
295        printf("\n[ERROR] in %s : requested size = 0 \n",
296        __FUNCTION__ );
297        return NULL;
298    }
299    if( cxy >= MALLOC_MAX_CLUSTERS )
300    {
301        printf("\n[ERROR] in %s : illegal cluster %x\n",
302        __FUNCTION__ , cxy );
303        return NULL;
304    }
305
306    // initializes target store if required
307    if( store[cxy].initialized != MALLOC_INITIALIZED )
308    {
309        store_init( cxy , MALLOC_LOCAL_STORE_SIZE );
310
311        if( store[cxy].initialized != MALLOC_INITIALIZED )
312        {
313            printf("\n[ERROR] in %s : cannot allocate store in cluster %x\n",
314            __FUNCTION__ , cxy );
315            return NULL;
316        }
317    }
318
319    // normalize size
320    if ( size < MALLOC_MIN_BLOCK_SIZE ) size = MALLOC_MIN_BLOCK_SIZE;
321
322    // compute requested_index for the free[] array
323    unsigned int requested_index = GET_SIZE_INDEX( size );
324
325    // take the lock protecting access to store[cxy]
326    pthread_mutex_lock( &store[cxy].mutex );
327
328    // call the recursive function get_block
329    unsigned int base = get_block( &store[cxy], 
330                                   requested_index, 
331                                   requested_index );
332
333    // check block found
334    if (base == 0)
335    {
336        pthread_mutex_unlock( &store[cxy].mutex );
337        printf("\n[ERROR] in %s : no more space in cluster %x\n",
338        __FUNCTION__ , cxy );
339        return NULL;
340    }
341
342    // compute pointer in alloc[] array
343    unsigned        offset = (base - store[cxy].store_base) / MALLOC_MIN_BLOCK_SIZE;
344    unsigned char * ptr    = (unsigned char*)(store[cxy].alloc_base + offset);
345
346    // check the alloc[] array
347    if ( *ptr != 0 )
348    {
349        pthread_mutex_unlock( &store[cxy].mutex );
350        printf("\n[PANIC] in %s : allocate an already allocated block...\n",
351        __FUNCTION__ );
352        return NULL;
353    }
354
355    // update alloc_array
356    *ptr = requested_index;
357
358    // release the lock
359    pthread_mutex_unlock( &store[cxy].mutex );
360 
361#if MALLOC_DEBUG
362printf("\n[MALLOC] %s : exit / base = %x / size = %x / from store[%x]\n",
363__FUNCTION__, base , size , cxy );
364#endif
365
366    return (void*) base;
367
368} // end remote_malloc()
369
370
371//////////////////////////////////
372void * malloc( unsigned int size )
373{
374    // get cluster identifier
375    unsigned int cxy;
376    unsigned int lid;
377    get_core( &cxy , &lid );
378
379    return remote_malloc( size, cxy );
380} 
381
382
383//////////////////////////////////////////
384void * remote_calloc ( unsigned int count,
385                       unsigned int size,
386                       unsigned int cxy )
387{
388    void * ptr = remote_malloc( count * size , cxy );
389    memset( ptr , 0 , count * size );
390    return ptr;
391}
392
393///////////////////////////////////
394void * calloc ( unsigned int count,
395                unsigned int size )
396{
397    // get calling core cluster identifier
398    unsigned int cxy;
399    unsigned int lid;
400    get_core( &cxy , &lid );
401
402    return remote_calloc( count , size , cxy );
403}
404
405//////////////////////////////////
406void * remote_realloc( void * ptr,
407                       unsigned int size,
408                       unsigned int cxy )
409{
410    // simple allocation when (ptr == NULL)
411    if( ptr == NULL )
412    {
413        return remote_malloc( size , cxy );
414    }
415
416    // simple free when (size == 0)
417    if( size == 0 )
418    {
419        remote_free( ptr , cxy );
420        return NULL;
421    }
422
423    // check cxy and ptr in general case
424    if( cxy >= MALLOC_MAX_CLUSTERS )
425    {
426        printf("\n[ERROR] in %s : illegal cluster index %x\n",
427        __FUNCTION__ , cxy );
428        return NULL;
429    }
430
431    unsigned int base = (unsigned int)ptr;
432
433    if( (base < store[cxy].store_base) || 
434        (base >= (store[cxy].store_base + store[cxy].store_size)) )
435    {
436        printf("\n[ERROR] in %s : illegal pointer = %x\n",
437        __FUNCTION__, ptr );
438        return NULL;
439    }
440 
441    // compute index in free[] array
442    int index = (base - store[cxy].store_base) / MALLOC_MIN_BLOCK_SIZE;
443
444    // compute old size
445    char * pchar = (char *) (store[cxy].alloc_base + index);
446    int old_size = 1 << ((int) *pchar);
447
448    // allocate a new block
449    void * new_ptr = remote_malloc( size , cxy );
450
451    // save old data to new block
452    int min_size = (size < old_size) ? size : old_size;
453    memcpy( new_ptr, ptr, min_size );
454
455    // release old block
456    remote_free( ptr , cxy );
457
458    return new_ptr;
459}
460
461///////////////////////////////////
462void * realloc ( void        * ptr,
463                 unsigned int  size )
464{
465    // get calling core cluster identifier
466    unsigned int cxy;
467    unsigned int lid;
468    get_core( &cxy , &lid );
469
470    return remote_realloc( ptr , size , cxy );
471}
472
473
474
475//////////////////////////////////////////////////////
476static void update_free_array( malloc_store_t * store,
477                               unsigned int     base,
478                               unsigned int     size_index )
479{
480    // This recursive function try to merge the released block
481    // with the companion block if this companion block is free.
482    // This companion has the same size, and almost the same address
483    // (only one address bit is different)
484    // - If the companion is not in free[size_index],
485    //   the released block is pushed in free[size_index].
486    // - If the companion is found, it is evicted from free[size_index]
487    //   and the merged bloc is pushed in the free[size_index+1].
488
489
490    // compute released block size
491    unsigned int size = 1<<size_index;
492
493    // compute companion block and merged block base addresses
494    unsigned int companion_base; 
495    unsigned int merged_base; 
496
497    if ( (base & size) == 0 )   // the released block is aligned on (2*size)
498    {
499        companion_base  = base + size;
500        merged_base     = base;
501    }
502    else
503    {
504        companion_base  = base - size;
505        merged_base     = base - size;
506    }
507
508    // scan all blocks in free[size_index]
509    // the iter & prev variables are actually addresses
510    unsigned int  found = 0;
511    unsigned int  iter  = store->free[size_index];
512    unsigned int  prev  = (unsigned int)&store->free[size_index];
513    while ( iter ) 
514    {
515        if ( iter == companion_base ) 
516        {
517            found = 1;
518            break;
519        }
520        prev = iter;
521        iter = *(unsigned int*)iter;
522    }
523
524    if ( found == 0 )  // Companion not found => push in free[size_index] 
525    {
526        *(unsigned int*)base   = store->free[size_index];
527        store->free[size_index] = base;
528    }
529    else               // Companion found : merge
530    {
531        // evict the searched block from free[size_index]
532        *(unsigned int*)prev = *(unsigned int*)iter;
533
534        // call the update_free() function for free[size_index+1]
535        update_free_array( store, merged_base , size_index+1 );
536    }
537}  // end update_free_array()
538
539////////////////////////////////////
540void remote_free( void        * ptr,
541                  unsigned int  cxy )
542{
543
544#if MALLOC_DEBUG
545printf("\n[MALLOC] %s : enter for block = %x / cxy = %x\n",
546__FUNCTION__, ptr, cxy );
547#endif
548
549    unsigned int base = (unsigned int)ptr;
550
551    // check cxy value
552    if( cxy >= MALLOC_MAX_CLUSTERS )
553    {
554        printf("\n[ERROR] in %s : illegal cluster index %x\n",
555        __FUNCTION__ , cxy );
556        return;
557    }
558
559    // check ptr value
560    if( (base < store[cxy].store_base) || 
561        (base >= (store[cxy].store_base + store[cxy].store_size)) )
562    {
563        printf("\n[ERROR] in %s : illegal pointer for released block = %x\n",
564        __FUNCTION__, ptr );
565        return;
566    }
567 
568    // get the lock protecting store[cxy]
569    pthread_mutex_lock( &store[cxy].mutex );
570
571    // compute released block index in alloc[] array
572    unsigned index = (base - store[cxy].store_base ) / MALLOC_MIN_BLOCK_SIZE;
573 
574    // get the released block size_index
575    unsigned char* pchar      = (unsigned char*)(store[cxy].alloc_base + index);
576    unsigned int   size_index = (unsigned int)*pchar;
577
578    // check block is allocated
579    if ( size_index == 0 )
580    {
581        pthread_mutex_unlock( &store[cxy].mutex );
582        printf("\n[ERROR] in %s : released block not allocated / ptr = %x\n",
583        __FUNCTION__, ptr );
584        return;
585    }
586
587    // check released block alignment
588    if ( base % (1 << size_index) )
589    {
590        pthread_mutex_unlock( &store[cxy].mutex );
591        printf("\n[ERROR] in %s : released block not aligned / ptr = %x\n",
592        __FUNCTION__, ptr );
593        return;
594    }
595
596    // reset the alloc[index] entry
597    *pchar = 0;
598
599    // call the recursive function update_free_array()
600    update_free_array( &store[cxy], base, size_index ); 
601
602    // release the lock
603    pthread_mutex_unlock( &store[cxy].mutex );
604
605#if MALLOC_DEBUG
606printf("\n[MALLOC] %s : conmpletes for block = %x / cxy = %x\n",
607__FUNCTION__, ptr, cxy );
608#endif
609
610} // end remote_free()
611
612///////////////////////
613void free( void * ptr )
614{
615    // get calling core cluster identifier
616    unsigned int cxy;
617    unsigned int lid;
618    get_core( &cxy , &lid );
619
620    remote_free( ptr , cxy );
621}
622
623   
624// Local Variables:
625// tab-width: 4
626// c-basic-offset: 4
627// c-file-offsets:((innamespace . 0)(inline-open . 0))
628// indent-tabs-mode: nil
629// End:
630// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
631
632
633
Note: See TracBrowser for help on using the repository browser.