Changeset 651 for trunk/kernel/mm

Timestamp:

Nov 14, 2019, 11:50:09 AM (5 years ago)

Author:

alain

Message:

1) Improve the VMM MMAP allocator: implement the "buddy" algorithm
to allocate only aligned blocks.
2) fix a bug in the pthread_join() / pthread_exit() mmechanism.

Location:

trunk/kernel/mm

Files:

• mapper.c (modified) (2 diffs)
• ppm.c (modified) (1 diff)
• vmm.c (modified) (20 diffs)
• vmm.h (modified) (6 diffs)
• vseg.c (modified) (1 diff)
• vseg.h (modified) (2 diffs)

trunk/kernel/mm/mapper.c

@@ -442 +442 @@
         if ( page_xp == XPTR_NULL ) return -1;
 
-        // compute extended pointer in kernel mapper
+        // compute extended pointer on kernel mapper
         xptr_t     map_xp  = ppm_page2base( page_xp ) + page_offset;
 
@@ -448 +448 @@
 if( DEBUG_MAPPER_MOVE_USER < cycle )
 printk("\n[%s] thread[%x,%x] : get buffer(%x,%x) in mapper\n",
-__FUNCTION__, this->process->pid, this->trdid, map_cxy, map_ptr );
+__FUNCTION__, this->process->pid, this->trdid, GET_CXY(map_xp), GET_PTR(map_xp) );
 #endif
         // compute pointer in user buffer

trunk/kernel/mm/ppm.c

@@ -296 +296 @@
                 current_size >>= 1;
 
-        // update order fiels in new free block
+        // update order fields in new free block
                 current_block = found_block + current_size;
                 current_block->order = current_order;

trunk/kernel/mm/vmm.c

@@ -55 +55 @@
 
 ////////////////////////////////////////////////////////////////////////////////////////////
+// This static function is called by the vmm_user_init() function.
+// It initialises the free lists of vsegs used by the VMM MMAP allocator.
+// It makes the assumption that HEAP_BASE == 1 Gbytes and HEAP_SIZE == 2 Gbytes.
+////////////////////////////////////////////////////////////////////////////////////////////
+static void vmm_stack_init( vmm_t * vmm )
+{
+
+// check STACK zone
+assert( ((CONFIG_VMM_STACK_SIZE * CONFIG_THREADS_MAX_PER_CLUSTER) <=
+(CONFIG_VMM_VSPACE_SIZE - CONFIG_VMM_STACK_BASE)) , "STACK zone too small\n");
+
+    // get pointer on STACK allocator 
+    stack_mgr_t * mgr = &vmm->stack_mgr;
+
+    mgr->bitmap   = 0;
+    mgr->vpn_base = CONFIG_VMM_STACK_BASE;
+    busylock_init( &mgr->lock , LOCK_VMM_STACK );
+
+}
+
+////////////////////////////////////////////////////////////////////////////////////////////
 // This static function is called by the vmm_create_vseg() function, and implements
-// the VMM STACK specific allocator.
+// the VMM STACK specific allocator. Depending on the local thread index <ltid>,
+// it ckeks availability of the corresponding slot in the process STACKS region,
+// allocates a vseg descriptor, and initializes the "vpn_base" and "vpn_size" fields.
 ////////////////////////////////////////////////////////////////////////////////////////////
 // @ vmm      : [in]  pointer on VMM.
 // @ ltid     : [in]  requested slot == local user thread identifier.
-// @ vpn_base : [out] first allocated page
-// @ vpn_size : [out] number of allocated pages
 ////////////////////////////////////////////////////////////////////////////////////////////
-static void vmm_stack_alloc( vmm_t  * vmm,
-                             ltid_t   ltid,
-                             vpn_t  * vpn_base,
-                             vpn_t  * vpn_size )
+static vseg_t * vmm_stack_alloc( vmm_t  * vmm,
+                                 ltid_t   ltid )
 {
 
@@ -76 +95 @@
     stack_mgr_t * mgr = &vmm->stack_mgr;
 
-    // get lock on stack allocator
+    // get lock protecting stack allocator
     busylock_acquire( &mgr->lock );
 
@@ -83 +102 @@
 "slot index %d already allocated", ltid );
 
+    // allocate a vseg descriptor
+    vseg_t * vseg = vseg_alloc();
+
+    if( vseg == NULL )
+        {
+        // release lock protecting free lists
+        busylock_release( &mgr->lock );
+
+        printk("\n[ERROR] %s cannot allocate memory for vseg in cluster %x\n",
+        __FUNCTION__ , local_cxy );
+
+        return NULL;
+    }
+
     // update bitmap
     bitmap_set( &mgr->bitmap , ltid );
@@ -89 +122 @@
     busylock_release( &mgr->lock );
 
-    // returns vpn_base, vpn_size (first page non allocated)
-    *vpn_base = mgr->vpn_base + ltid * CONFIG_VMM_STACK_SIZE + 1;
-    *vpn_size = CONFIG_VMM_STACK_SIZE - 1;
+    // set "vpn_base" & "vpn_size" fields (first page non allocated)
+    vseg->vpn_base = mgr->vpn_base + (ltid * CONFIG_VMM_STACK_SIZE) + 1;
+    vseg->vpn_size = CONFIG_VMM_STACK_SIZE - 1;
+
+    return vseg;
 
 } // end vmm_stack_alloc()
@@ -98 +133 @@
 // This static function is called by the vmm_remove_vseg() function, and implements
 // the VMM STACK specific desallocator.
+// It updates the bitmap to release the corresponding slot in the process STACKS region,
+// and releases memory allocated to vseg descriptor.
 ////////////////////////////////////////////////////////////////////////////////////////////
 // @ vmm      : [in] pointer on VMM.
@@ -128 +165 @@
     busylock_release( &mgr->lock );
 
+    // release memory allocated to vseg descriptor
+    vseg_free( vseg );
+
 }  // end vmm_stack_free()
+
+
+
+////////////////////////////////////////////////////////////////////////////////////////////
+// This function display the current state of the VMM MMAP allocator of a process VMM
+// identified by the <vmm> argument.
+////////////////////////////////////////////////////////////////////////////////////////////
+void vmm_mmap_display( vmm_t * vmm )
+{
+    uint32_t  order;
+    xptr_t    root_xp;
+    xptr_t    iter_xp;
+
+    // get pointer on process
+    process_t * process = (process_t *)(((char*)vmm) - OFFSETOF( process_t , vmm ));
+
+    // get process PID
+    pid_t pid = process->pid;
+
+    // get pointer on VMM MMAP allocator
+    mmap_mgr_t * mgr = &vmm->mmap_mgr;
+
+    // display header
+    printk("***** VMM MMAP allocator / process %x *****\n", pid );
+
+    // scan the array of free lists of vsegs
+    for( order = 0 ; order <= CONFIG_VMM_HEAP_MAX_ORDER ; order++ )
+    {
+        root_xp = XPTR( local_cxy , &mgr->free_list_root[order] );
+
+        if( !xlist_is_empty( root_xp ) )
+        {
+            printk(" - %d (%x pages) : ", order , 1<<order );
+
+            XLIST_FOREACH( root_xp , iter_xp )
+            {
+                xptr_t   vseg_xp = XLIST_ELEMENT( iter_xp , vseg_t , xlist );
+                vseg_t * vseg    = GET_PTR( vseg_xp );
+
+                printk("%x | ", vseg->vpn_base );
+            }
+
+            printk("\n");
+        }
+    }
+}  // end vmm_mmap_display()
+
+////////////////////////////////////////////////////////////////////////////////////////////
+// This static function is called by the vmm_user_init() function.
+// It initialises the free lists of vsegs used by the VMM MMAP allocator.
+// TODO this function is only valid for 32 bits cores, and makes three assumptions:
+// HEAP_BASE == 1 Gbytes / HEAP_SIZE == 2 Gbytes / MMAP_MAX_SIZE == 1 Gbytes
+////////////////////////////////////////////////////////////////////////////////////////////
+void vmm_mmap_init( vmm_t * vmm )
+{
+
+// check HEAP base and size 
+assert( (CONFIG_VMM_HEAP_BASE == 0x40000) & (CONFIG_VMM_STACK_BASE == 0xc0000),
+"CONFIG_VMM_HEAP_BASE != 0x40000 or CONFIG_VMM_STACK_BASE != 0xc0000" );
+
+// check  MMAP vseg max order 
+assert( (CONFIG_VMM_HEAP_MAX_ORDER == 18), "max mmap vseg size is 256K pages" );
+
+    // get pointer on MMAP allocator 
+    mmap_mgr_t * mgr = &vmm->mmap_mgr;
+
+    // initialize HEAP base and size
+    mgr->vpn_base        = CONFIG_VMM_HEAP_BASE;
+    mgr->vpn_size        = CONFIG_VMM_STACK_BASE - CONFIG_VMM_HEAP_BASE;
+
+    // initialize lock
+    busylock_init( &mgr->lock , LOCK_VMM_MMAP );
+
+    // initialize free lists
+    uint32_t   i;
+    for( i = 0 ; i <= CONFIG_VMM_HEAP_MAX_ORDER ; i++ )
+    {
+        xlist_root_init( XPTR( local_cxy , &mgr->free_list_root[i] ) );
+    }
+
+    // allocate and register first 1 Gbytes vseg
+    vseg_t * vseg0 = vseg_alloc();
+
+assert( (vseg0 != NULL) , "cannot allocate vseg" );
+
+    vseg0->vpn_base = CONFIG_VMM_HEAP_BASE;
+    vseg0->vpn_size = CONFIG_VMM_HEAP_BASE;
+
+    xlist_add_first( XPTR( local_cxy , &mgr->free_list_root[CONFIG_VMM_HEAP_MAX_ORDER] ),
+                     XPTR( local_cxy , &vseg0->xlist ) );
+
+    // allocate and register second 1 Gbytes vseg
+    vseg_t * vseg1 = vseg_alloc();
+
+assert( (vseg1 != NULL) , "cannot allocate vseg" );
+
+    vseg1->vpn_base = CONFIG_VMM_HEAP_BASE << 1;
+    vseg1->vpn_size = CONFIG_VMM_HEAP_BASE;
+
+    xlist_add_first( XPTR( local_cxy , &mgr->free_list_root[CONFIG_VMM_HEAP_MAX_ORDER] ),
+                     XPTR( local_cxy , &vseg1->xlist ) );
+
+#if DEBUG_VMM_MMAP
+thread_t * this = CURRENT_THREAD;
+uint32_t cycle = (uint32_t)hal_get_cycles();
+printk("\n[%s] thread[%x,%x] / cycle %d\n",
+__FUNCTION__, this->process->pid, this->trdid, cycle );
+vmm_mmap_display( vmm );
+#endif
+
+}  // end vmm_mmap_init()
 
 ////////////////////////////////////////////////////////////////////////////////////////////
 // This static function is called by the vmm_create_vseg() function, and implements
-// the VMM MMAP specific allocator.
+// the VMM MMAP specific allocator.  Depending on the requested number of pages <npages>,
+// it get a free vseg from the relevant free_list, and initializes the "vpn_base" and
+// "vpn_size" fields.
 ////////////////////////////////////////////////////////////////////////////////////////////
 // @ vmm      : [in] pointer on VMM.
 // @ npages   : [in] requested number of pages.
-// @ vpn_base : [out] first allocated page.
-// @ vpn_size : [out] actual number of allocated pages.
+// @ returns local pointer on vseg if success / returns NULL if failure.
 ////////////////////////////////////////////////////////////////////////////////////////////
-static error_t vmm_mmap_alloc( vmm_t * vmm,
-                               vpn_t   npages,
-                               vpn_t * vpn_base,
-                               vpn_t * vpn_size )
+static vseg_t * vmm_mmap_alloc( vmm_t * vmm,
+                                vpn_t   npages )
 {
-    uint32_t   order;
-    xptr_t     vseg_xp;
-    vseg_t   * vseg;
-    vpn_t      base;
-    vpn_t      size;
-    vpn_t      free;
-
-#if DEBUG_VMM_MMAP_ALLOC
+
+#if DEBUG_VMM_MMAP
 thread_t * this = CURRENT_THREAD;
 uint32_t cycle = (uint32_t)hal_get_cycles();
-if( DEBUG_VMM_MMAP_ALLOC < cycle )
-printk("\n[%s] thread[%x,%x] enter / cycle %d\n",
-__FUNCTION__, this->process->pid, this->trdid, cycle );
+if( DEBUG_VMM_MMAP < cycle )
+printk("\n[%s] thread[%x,%x] for %x pages / cycle %d\n",
+__FUNCTION__, this->process->pid, this->trdid, npages, cycle );
 #endif
 
     // number of allocated pages must be power of 2
     // compute actual size and order 
-    size  = POW2_ROUNDUP( npages );
-    order = bits_log2( size );
+    vpn_t    required_vpn_size = POW2_ROUNDUP( npages );
+    uint32_t required_order    = bits_log2( required_vpn_size );
 
     // get mmap allocator pointer
     mmap_mgr_t * mgr = &vmm->mmap_mgr;
 
-    // build extended pointer on root of zombi_list[order]
-    xptr_t root_xp = XPTR( local_cxy , &mgr->zombi_list[order] );
-
-    // take lock protecting zombi_lists
+    // take lock protecting free lists in MMAP allocator
     busylock_acquire( &mgr->lock );
 
-    // get vseg from zombi_list or from mmap zone
-    if( xlist_is_empty( root_xp ) )                   // from mmap zone
-    {
-        // check overflow
-        free = mgr->first_free_vpn;
-        if( (free + size) > mgr->vpn_size ) return -1;
-
-        // update MMAP allocator
-        mgr->first_free_vpn += size;
-
-        // compute base
-        base = free;
-    }
-    else                                              // from zombi_list
-    {
-        // get pointer on zombi vseg from zombi_list
-        vseg_xp = XLIST_FIRST( root_xp , vseg_t , xlist );
-        vseg    = GET_PTR( vseg_xp );
-
-        // remove vseg from free-list
-        xlist_unlink( XPTR( local_cxy , &vseg->xlist ) );
-
-        // compute base
-        base = vseg->vpn_base;
-    }
-
-    // release lock 
-    busylock_release( &mgr->lock );
-
-#if DEBUG_VMM_MMAP_ALLOC
-cycle = (uint32_t)hal_get_cycles();
-if( DEBUG_VMM_DESTROY < cycle )
-printk("\n[%s] thread[%x,%x] exit / vpn_base %x / vpn_size %x / cycle %d\n",
-__FUNCTION__, this->process->pid, this->trdid, base, size, cycle );
-#endif
-
-    // returns vpn_base, vpn_size
-    *vpn_base = base;
-    *vpn_size = size;
-    return 0;
+    // initialises the while loop variables
+    uint32_t   current_order = required_order;
+    vseg_t   * current_vseg  = NULL;
+
+    // search a free vseg equal or larger than requested size
+        while( current_order <= CONFIG_VMM_HEAP_MAX_ORDER )
+        {
+        // build extended pointer on free_pages_root[current_order]
+        xptr_t root_xp = XPTR( local_cxy , &mgr->free_list_root[current_order] );
+
+                if( !xlist_is_empty( root_xp ) )
+                {
+            // get extended pointer on first vseg in this free_list
+                        xptr_t current_vseg_xp = XLIST_FIRST( root_xp , vseg_t , xlist );
+            current_vseg = GET_PTR( current_vseg_xp );
+
+            // build extended pointer on xlist field in vseg descriptor
+            xptr_t list_entry_xp = XPTR( local_cxy , &current_vseg->xlist );
+
+            // remove this vseg from the free_list
+                        xlist_unlink( list_entry_xp );
+
+                        break;  
+                }
+
+        // increment loop index
+        current_order++;
+
+    }  // end while loop 
+
+    if( current_vseg == NULL )  // return failure 
+    {
+        // release lock protecting free lists
+        busylock_release( &mgr->lock );
+
+        printk("\n[ERROR] %s cannot allocate ) %d page(s) in cluster %x\n",
+        __FUNCTION__, npages , local_cxy );
+
+        return NULL;
+    }
+
+        // split recursively the found vseg in smaller vsegs
+    // if required, and update the free-lists accordingly
+        while( current_order > required_order )
+        {
+        // get found vseg base and size
+        vpn_t  vpn_base = current_vseg->vpn_base;
+        vpn_t  vpn_size = current_vseg->vpn_size;
+        
+        // allocate a new vseg for the upper half of current vseg
+            vseg_t * new_vseg = vseg_alloc();
+
+            if( new_vseg == NULL )
+        {
+                // release lock protecting free lists
+            busylock_release( &mgr->lock );
+
+            printk("\n[ERROR] %s cannot allocate memory for vseg in cluster %x\n",
+            __FUNCTION__ , local_cxy );
+
+            return NULL;
+            }
+
+        // initialise new vseg (upper half of found vseg)
+        new_vseg->vmm      = vmm;
+        new_vseg->vpn_base = vpn_base + (vpn_size >> 1);
+        new_vseg->vpn_size = vpn_size >> 1;
+
+        // insert new vseg in relevant free_list
+                xlist_add_first( XPTR( local_cxy , &mgr->free_list_root[current_order-1] ),
+                         XPTR( local_cxy , &new_vseg->xlist ) );
+
+        // update found vseg
+        current_vseg->vpn_size = vpn_size>>1; 
+
+        // update order
+                current_order --;
+        }
+
+        // release lock protecting free lists
+        busylock_release( &mgr->lock );
+
+#if DEBUG_VMM_MMAP
+vmm_mmap_display( vmm );
+#endif
+
+    return current_vseg;
 
 }  // end vmm_mmap_alloc()
@@ -219 +407 @@
 // This static function implements the VMM MMAP specific desallocator.
 // It is called by the vmm_remove_vseg() function.
+// It releases the vseg to the relevant free_list, after trying (recursively) to
+// merge it to the buddy vseg.
 ////////////////////////////////////////////////////////////////////////////////////////////
 // @ vmm      : [in] pointer on VMM.
@@ -226 +416 @@
                            vseg_t * vseg )
 {
-    // get pointer on mmap allocator
+
+#if DEBUG_VMM_MMAP
+thread_t * this = CURRENT_THREAD;
+uint32_t cycle = (uint32_t)hal_get_cycles();
+if( DEBUG_VMM_MMAP < cycle )
+printk("\n[%s] thread[%x,%x] for vpn_base %x / vpn_size %x / cycle %d\n",
+__FUNCTION__, this->process->pid, this->trdid, vseg->vpn_base, vseg->vpn_size, cycle );
+#endif
+
+    vseg_t * buddy_vseg;
+
+    // get mmap allocator pointer
     mmap_mgr_t * mgr = &vmm->mmap_mgr;
 
-    // compute zombi_list order
-    uint32_t order = bits_log2( vseg->vpn_size );
-
-    // take lock protecting zombi lists
+    // take lock protecting free lists
     busylock_acquire( &mgr->lock );
 
-    // update relevant zombi_list
-    xlist_add_first( XPTR( local_cxy , &mgr->zombi_list[order] ),
-                     XPTR( local_cxy , &vseg->xlist ) );
+    // initialise loop variables 
+    // released_vseg is the currently released vseg
+    vseg_t * released_vseg     = vseg;
+    uint32_t released_order    = bits_log2( vseg->vpn_size );
+
+        // iteratively merge the released vseg to the buddy vseg
+        // release the current page and exit when buddy not found
+    while( released_order <= CONFIG_VMM_HEAP_MAX_ORDER )
+    {
+        // compute buddy_vseg vpn_base 
+                vpn_t buddy_vpn_base = released_vseg->vpn_base ^ (1 << released_order);
+        
+        // build extended pointer on free_pages_root[current_order]
+        xptr_t root_xp = XPTR( local_cxy , &mgr->free_list_root[released_order] );
+
+        // scan this free list to find the buddy vseg
+        xptr_t   iter_xp;
+        buddy_vseg = NULL;
+        XLIST_FOREACH( root_xp , iter_xp )
+        {
+            xptr_t   current_vseg_xp = XLIST_ELEMENT( iter_xp , vseg_t , xlist );
+            vseg_t * current_vseg    = GET_PTR( current_vseg_xp );
+
+            if( current_vseg->vpn_base == buddy_vpn_base )
+            {
+                buddy_vseg = current_vseg;
+                break;
+            }
+        }
+        
+        if( buddy_vseg != NULL )     // buddy found => merge released & buddy
+        {
+            // update released vseg fields
+            released_vseg->vpn_size = buddy_vseg->vpn_size<<1;
+            if( released_vseg->vpn_base > buddy_vseg->vpn_base) 
+                released_vseg->vpn_base = buddy_vseg->vpn_base;
+
+            // remove buddy vseg from free_list
+            xlist_unlink( XPTR( local_cxy , &buddy_vseg->xlist ) );
+
+            // release memory allocated to buddy descriptor
+            vseg_free( buddy_vseg );
+        }
+        else                         // buddy not found => register & exit
+        {
+            // register released vseg in free list
+            xlist_add_first( root_xp , XPTR( local_cxy , &released_vseg->xlist ) );
+
+            // exit while loop
+            break;
+        }
+
+        // increment released_order
+        released_order++;
+    }
 
     // release lock
     busylock_release( &mgr->lock );
 
-}  // end of vmm_mmap_free()
+#if DEBUG_VMM_MMAP
+vmm_mmap_display( vmm );
+#endif
+
+}  // end vmm_mmap_free()
 
 ////////////////////////////////////////////////////////////////////////////////////////////
@@ -288 +542 @@
 error_t vmm_user_init( process_t * process )
 {
-    uint32_t  i;
 
 #if DEBUG_VMM_USER_INIT
@@ -306 +559 @@
          "UTILS zone too small\n" );
 
-// check STACK zone
-assert( ((CONFIG_VMM_STACK_SIZE * CONFIG_THREADS_MAX_PER_CLUSTER) <=
-(CONFIG_VMM_VSPACE_SIZE - CONFIG_VMM_STACK_BASE)) ,
-"STACK zone too small\n");
-
-    // initialize the lock protecting the VSL 
+    // initialize lock protecting the VSL 
         remote_queuelock_init( XPTR( local_cxy , &vmm->vsl_lock ) , LOCK_VMM_VSL );
 
+
+    // initialize STACK allocator
+    vmm_stack_init( vmm );
+
+    // initialize MMAP allocator
+    vmm_mmap_init( vmm );
+
+    // initialize instrumentation counters
+        vmm->false_pgfault_nr    = 0;
+        vmm->local_pgfault_nr    = 0;
+        vmm->global_pgfault_nr   = 0;
+        vmm->false_pgfault_cost  = 0;
+        vmm->local_pgfault_cost  = 0;
+        vmm->global_pgfault_cost = 0;
 
 /*
@@ -356 +618 @@
     vmm->envs_vpn_base = base;
 */
-    // initialize STACK allocator
-    vmm->stack_mgr.bitmap   = 0;
-    vmm->stack_mgr.vpn_base = CONFIG_VMM_STACK_BASE;
-    busylock_init( &vmm->stack_mgr.lock , LOCK_VMM_STACK );
-
-    // initialize MMAP allocator
-    vmm->mmap_mgr.vpn_base        = CONFIG_VMM_HEAP_BASE;
-    vmm->mmap_mgr.vpn_size        = CONFIG_VMM_STACK_BASE - CONFIG_VMM_HEAP_BASE;
-    vmm->mmap_mgr.first_free_vpn  = CONFIG_VMM_HEAP_BASE;
-    busylock_init( &vmm->mmap_mgr.lock , LOCK_VMM_MMAP );
-    for( i = 0 ; i < 32 ; i++ )
-    {
-        xlist_root_init( XPTR( local_cxy , &vmm->mmap_mgr.zombi_list[i] ) );
-    }
-
-    // initialize instrumentation counters
-        vmm->false_pgfault_nr    = 0;
-        vmm->local_pgfault_nr    = 0;
-        vmm->global_pgfault_nr   = 0;
-        vmm->false_pgfault_cost  = 0;
-        vmm->local_pgfault_cost  = 0;
-        vmm->global_pgfault_cost = 0;
-
     hal_fence();
 
@@ -1158 +1397 @@
     remote_queuelock_release( parent_lock_xp );
 
+/* deprecated [AG] : this is already done by the vmm_user_init() funcfion
+
     // initialize the child VMM STACK allocator
-    child_vmm->stack_mgr.bitmap   = 0;
-    child_vmm->stack_mgr.vpn_base = CONFIG_VMM_STACK_BASE;
+    vmm_stack_init( child_vmm );
 
     // initialize the child VMM MMAP allocator
-    uint32_t i;
-    child_vmm->mmap_mgr.vpn_base        = CONFIG_VMM_HEAP_BASE;
-    child_vmm->mmap_mgr.vpn_size        = CONFIG_VMM_STACK_BASE - CONFIG_VMM_HEAP_BASE;
-    child_vmm->mmap_mgr.first_free_vpn  = CONFIG_VMM_HEAP_BASE;
-    for( i = 0 ; i < 32 ; i++ ) 
-    {
-        xlist_root_init( XPTR( local_cxy , &child_vmm->mmap_mgr.zombi_list[i] ) );
-    }
+    vmm_mmap_init( child_vmm );
 
     // initialize instrumentation counters
@@ -1179 +1412 @@
         child_vmm->local_pgfault_cost  = 0;
         child_vmm->global_pgfault_cost = 0;
-
+*/
     // copy base addresses from parent VMM to child VMM
     child_vmm->args_vpn_base = (vpn_t)hal_remote_lpt(XPTR(parent_cxy, &parent_vmm->args_vpn_base));
@@ -1260 +1493 @@
     remote_queuelock_release( vsl_lock_xp );
 
-    // remove all registered MMAP vsegs
-    // from zombi_lists in MMAP allocator
+    // remove all registered MMAP vsegs from free_lists in MMAP allocator
     uint32_t i;
-    for( i = 0 ; i<32 ; i++ )
-    {
-        // build extended pointer on zombi_list[i]
-        xptr_t root_xp = XPTR( local_cxy , &vmm->mmap_mgr.zombi_list[i] );
+    for( i = 0 ; i <= CONFIG_VMM_HEAP_MAX_ORDER ; i++ )
+    {
+        // build extended pointer on free list root
+        xptr_t root_xp = XPTR( local_cxy , &vmm->mmap_mgr.free_list_root[i] );
   
         // scan zombi_list[i]
@@ -1343 +1575 @@
                           cxy_t         cxy )
 {
-    vseg_t     * vseg;          // created vseg pointer
-    vpn_t        vpn_base;      // first page index
-    vpn_t        vpn_size;      // number of pages covered by vseg
-        error_t      error;
+    vseg_t     * vseg;          // pointer on allocated vseg descriptor 
 
 #if DEBUG_VMM_CREATE_VSEG
@@ -1364 +1593 @@
         vmm_t * vmm    = &process->vmm;
 
-    // compute base, size, vpn_base, vpn_size, depending on vseg type
-    // we use the VMM specific allocators for "stack", "file", "anon", & "remote" vsegs
-
+    // allocate a vseg descriptor and initialize it, depending on type
+    // we use specific allocators for "stack" and "mmap" types
+
+    /////////////////////////////
     if( type == VSEG_TYPE_STACK )
     {
-        // get vpn_base and vpn_size from STACK allocator
-        vmm_stack_alloc( vmm , base , &vpn_base , &vpn_size );
-
-        // compute vseg base and size from vpn_base and vpn_size
-        base = vpn_base << CONFIG_PPM_PAGE_SHIFT;
-        size = vpn_size << CONFIG_PPM_PAGE_SHIFT;
-    }
-    else if( type == VSEG_TYPE_FILE )
-    {
-        // compute page index (in mapper) for first byte
-        vpn_t    vpn_min    = file_offset >> CONFIG_PPM_PAGE_SHIFT;
-
-        // compute page index (in mapper) for last byte
-        vpn_t    vpn_max    = (file_offset + size - 1) >> CONFIG_PPM_PAGE_SHIFT;
-
-        // compute offset in first page
-        uint32_t offset = file_offset & CONFIG_PPM_PAGE_MASK;
-
-        // compute number of pages required in virtual space
-        vpn_t    npages      = vpn_max - vpn_min + 1;
-
-        // get vpn_base and vpn_size from MMAP allocator
-        error = vmm_mmap_alloc( vmm , npages , &vpn_base , &vpn_size );
-        if( error )
+        // get vseg from STACK allocator
+        vseg = vmm_stack_alloc( vmm , base );    // base == ltid
+       
+        if( vseg == NULL )
         {
-            printk("\n[ERROR] in %s : no vspace for mmap vseg / process %x in cluster %x\n",
-                   __FUNCTION__ , process->pid , local_cxy );
+            printk("\n[ERROR] %s cannot create %s vseg for process %x in cluster %x\n",
+            __FUNCTION__ , vseg_type_str( type ) , process->pid , local_cxy );
             return NULL;
         }
 
-        // set the vseg base (not always aligned for FILE)
-        base = (vpn_base << CONFIG_PPM_PAGE_SHIFT) + offset; 
-    }
-    else if( (type == VSEG_TYPE_ANON) ||
-             (type == VSEG_TYPE_REMOTE) )
+        // initialize vseg
+        vseg->type = type;
+        vseg->vmm  = vmm;
+        vseg->min  = vseg->vpn_base << CONFIG_PPM_PAGE_SHIFT;
+        vseg->max  = vseg->min + (vseg->vpn_size << CONFIG_PPM_PAGE_SHIFT);
+        vseg->cxy  = cxy;
+
+        vseg_init_flags( vseg , type );
+    }
+    /////////////////////////////////
+    else if( type == VSEG_TYPE_FILE )
+    {
+        // compute page index (in mapper) for first and last byte
+        vpn_t    vpn_min    = file_offset >> CONFIG_PPM_PAGE_SHIFT;
+        vpn_t    vpn_max    = (file_offset + size - 1) >> CONFIG_PPM_PAGE_SHIFT;
+
+        // compute offset in first page and number of pages
+        uint32_t offset = file_offset & CONFIG_PPM_PAGE_MASK;
+        vpn_t    npages      = vpn_max - vpn_min + 1;
+
+        // get vseg from MMAP allocator
+        vseg = vmm_mmap_alloc( vmm , npages );
+
+        if( vseg == NULL )
+        {
+            printk("\n[ERROR] %s cannot create %s vseg for process %x in cluster %x\n",
+            __FUNCTION__ , vseg_type_str( type ) , process->pid , local_cxy );
+            return NULL;
+        }
+
+        // initialize vseg 
+        vseg->type        = type;
+        vseg->vmm         = vmm;
+        vseg->min         = (vseg->vpn_base << CONFIG_PPM_PAGE_SHIFT) + offset; 
+        vseg->max         = vseg->min + size;
+        vseg->file_offset = file_offset;
+        vseg->file_size   = file_size;
+        vseg->mapper_xp   = mapper_xp;
+        vseg->cxy         = cxy;
+
+        vseg_init_flags( vseg , type );
+    }
+    /////////////////////////////////////////////////////////////////
+    else if( (type == VSEG_TYPE_ANON) || (type == VSEG_TYPE_REMOTE) )
     {
         // compute number of required pages in virtual space
@@ -1409 +1658 @@
         if( size & CONFIG_PPM_PAGE_MASK) npages++;
         
-        // get vpn_base and vpn_size from MMAP allocator
-        error = vmm_mmap_alloc( vmm , npages , &vpn_base , &vpn_size );
-        if( error )
+        // allocate vseg from MMAP allocator
+        vseg = vmm_mmap_alloc( vmm , npages );
+
+        if( vseg == NULL )
         {
-            printk("\n[ERROR] in %s : no vspace for mmap vseg / process %x in cluster %x\n",
-                   __FUNCTION__ , process->pid , local_cxy );
+            printk("\n[ERROR] %s cannot create %s vseg for process %x in cluster %x\n",
+            __FUNCTION__ , vseg_type_str( type ) , process->pid , local_cxy );
             return NULL;
         }
 
-        // set vseg base (always aligned for ANON or REMOTE)
-        base = vpn_base << CONFIG_PPM_PAGE_SHIFT;
-    }
+        // initialize vseg
+        vseg->type = type;
+        vseg->vmm  = vmm;
+        vseg->min  = vseg->vpn_base << CONFIG_PPM_PAGE_SHIFT;
+        vseg->max  = vseg->min + (vseg->vpn_size << CONFIG_PPM_PAGE_SHIFT);
+        vseg->cxy  = cxy;
+
+        vseg_init_flags( vseg , type );
+    }
+    /////////////////////////////////////////////////////////////////
     else    // VSEG_TYPE_DATA, VSEG_TYPE_CODE or KERNEL vseg
     {
@@ -1426 +1683 @@
         uint32_t vpn_max = (base + size - 1) >> CONFIG_PPM_PAGE_SHIFT;
 
-        vpn_base = vpn_min;
-            vpn_size = vpn_max - vpn_min + 1;
+        // allocate vseg descriptor
+            vseg = vseg_alloc();
+
+            if( vseg == NULL )
+            {
+            printk("\n[ERROR] %s cannot create %s vseg for process %x in cluster %x\n",
+            __FUNCTION__ , vseg_type_str( type ) , process->pid , local_cxy );
+            return NULL;
+            }
+        // initialize vseg
+        vseg->type        = type;
+        vseg->vmm         = vmm;
+        vseg->min         = base;
+        vseg->max         = base + size;
+        vseg->vpn_base    = base >> CONFIG_PPM_PAGE_SHIFT;
+        vseg->vpn_size    = vpn_max - vpn_min + 1;
+        vseg->file_offset = file_offset;
+        vseg->file_size   = file_size;
+        vseg->mapper_xp   = mapper_xp;
+        vseg->cxy         = cxy;
+
+        vseg_init_flags( vseg , type );
     }
 
     // check collisions
-    vseg = vmm_check_conflict( process , vpn_base , vpn_size );
-
-    if( vseg != NULL )
-    {
-        printk("\n[ERROR] in %s for process %x : new vseg [vpn_base %x / vpn_size %x]\n"
-               "  overlap existing vseg [vpn_base %x / vpn_size %x]\n",
-        __FUNCTION__ , process->pid, vpn_base, vpn_size, vseg->vpn_base, vseg->vpn_size );
+    vseg_t * existing_vseg = vmm_check_conflict( process , vseg->vpn_base , vseg->vpn_size );
+
+    if( existing_vseg != NULL )
+    {
+        printk("\n[ERROR] in %s for process %x : new vseg %s [vpn_base %x / vpn_size %x]\n"
+               "        overlap existing vseg %s [vpn_base %x / vpn_size %x]\n",
+        __FUNCTION__ , process->pid, vseg_type_str(vseg->type), vseg->vpn_base, vseg->vpn_size, 
+        vseg_type_str(existing_vseg->type), existing_vseg->vpn_base, existing_vseg->vpn_size );
+        vseg_free( vseg );
         return NULL;
     }
-
-    // allocate physical memory for vseg descriptor
-        vseg = vseg_alloc();
-        if( vseg == NULL )
-        {
-            printk("\n[ERROR] in %s for process %x : cannot allocate memory for vseg\n",
-        __FUNCTION__ , process->pid );
-        return NULL;
-        }
-
-#if (DEBUG_VMM_CREATE_VSEG & 1)
-if( DEBUG_VMM_CREATE_VSEG < cycle )
-printk("\n[%s] thread[%x,%x] : base %x / size %x / vpn_base %x / vpn_size %x\n",
-__FUNCTION__, this->process->pid, this->trdid, base, size, vpn_base, vpn_size );
-#endif
-
-    // initialize vseg descriptor
-        vseg_init( vseg,
-               type,
-               base,
-               size,
-               vpn_base,
-               vpn_size,
-               file_offset,
-               file_size,
-               mapper_xp,
-               cxy );
 
     // build extended pointer on VSL lock
@@ -1480 +1732 @@
     remote_queuelock_release( lock_xp );
 
-#if DEBUG_VMM_CREATE_VSEG
+#if DEBUG_VMM_CREATE_VSEG 
 cycle = (uint32_t)hal_get_cycles();
-// if( DEBUG_VMM_CREATE_VSEG < cycle )
-if( type == VSEG_TYPE_REMOTE )
-printk("\n[%s] thread[%x,%x] exit / process %x / %s / base %x / cxy %x / cycle %d\n",
-__FUNCTION__, this->process->pid, this->trdid, 
-process->pid, vseg_type_str(type), base, cxy, cycle );
+if( DEBUG_VMM_CREATE_VSEG < cycle )
+printk("\n[%s] thread[%x,%x] exit / %s / vpn_base %x / vpn_size %x / cycle %d\n",
+__FUNCTION__, this->process->pid, this->trdid,
+vseg_type_str(type), vseg->vpn_base, vseg->vpn_size, cycle );
 #endif
 
@@ -1654 +1905 @@
         // release slot to local stack allocator
         vmm_stack_free( vmm , vseg );
-
-        // release vseg descriptor to local kmem
-        vseg_free( vseg );
     }
     else if( (vseg_type == VSEG_TYPE_ANON) || 

trunk/kernel/mm/vmm.h

@@ -64 +64 @@
 
 /*********************************************************************************************
- * This structure defines the MMAP allocator used by the VMM to dynamically handle  
- * MMAP vsegs requested or released by an user process.
- * This allocator should be only used in the reference cluster.
- * - allocation policy : all allocated vsegs occupy an integer number of pages that is
- *   power of 2, and are aligned on a page boundary. The requested number of pages is
- *   rounded if required. The first_free_vpn variable defines completely the MMAP zone state.
- *   It is never decremented, as the released vsegs are simply registered in a zombi_list.
- *   The relevant zombi_list is checked first for each allocation request.
- * - release policy : a released MMAP vseg is registered in an array of zombi_lists.
- *   This array is indexed by ln(number of pages), and each entry contains the root of
- *   a local list of zombi vsegs that have the same size. The physical memory allocated
- *   for a zombi vseg descriptor is not released, to use the "list" field.
- *   This physical memory allocated for MMAP vseg descriptors is actually released
- *   when the VMM is destroyed.
+ * This structure defines the MMAP allocator used by the VMM to dynamically handle MMAP vsegs
+ * requested or released by an user process. It must be called in the reference cluster.
+ * - allocation policy : 
+ *   This allocator implements the buddy algorithm. All allocated vsegs occupy an integer
+ *   number of pages, that is power of 2, and are aligned (vpn_base is multiple of vpn_size).
+ *   The requested number of pages is rounded if required. The global allocator state is
+ *   completely defined by the free_pages_root[] array indexed by the vseg order.
+ *   These free lists are local, but are implemented as xlist because we use the existing
+ *   vseg.xlist to register a free vseg in its free list.
+ * - release policy : 
+ *   A released vseg is recursively merged with the "buddy" vseg when it is free, in
+ *   order to build the largest possible aligned free vsegs. The resulting vseg.vpn_size
+ *   field is updated.
+ * Implementation note:
+ * The only significant (and documented) fiels in the vsegs registered in the MMAP allocator
+ * free lists are "xlist", "vpn_base", and "vpn_size".
  ********************************************************************************************/
 
@@ -85 +87 @@
     vpn_t          vpn_base;           /*! first page of MMAP zone                          */
     vpn_t          vpn_size;           /*! number of pages in MMAP zone                     */
-    vpn_t          first_free_vpn;     /*! first free page in MMAP zone                     */
-    xlist_entry_t  zombi_list[32];     /*! array of roots of released vsegs lists           */
+    xlist_entry_t  free_list_root[CONFIG_VMM_HEAP_MAX_ORDER + 1];  /* roots of free lists   */
 }
 mmap_mgr_t;
@@ -103 +104 @@
  * 2. The VSL contains only local vsegs, but it is implemented as an xlist, and protected by
  *    a remote_rwlock, because it can be accessed by a thread running in a remote cluster.
- *    An exemple is the vmm_fork_copy() function.
+ *    An example is the vmm_fork_copy() function.
  * 3. The GPT in the reference cluster can be directly accessed by remote threads to handle
  *    false page-fault (page is mapped in the reference GPT, but the PTE copy is missing
@@ -119 +120 @@
 
     stack_mgr_t        stack_mgr;           /*! embedded STACK vsegs allocator              */
+
     mmap_mgr_t         mmap_mgr;            /*! embedded MMAP vsegs allocator               */
 
@@ -156 +158 @@
  * call to the vmm_user_init() function after an exec() syscall.
  * It removes from the VMM of the process identified by the <process> argument all
- * non kernel vsegs (i.e. all user vsegs), by calling the vmm_remove_vseg() function.
+ * all user vsegs, by calling the vmm_remove_vseg() function.
  * - the vsegs are removed from the VSL.
  * - the corresponding GPT entries are removed from the GPT.
@@ -279 +281 @@
 /*********************************************************************************************
  * This function allocates memory for a vseg descriptor, initialises it, and register it
- * in the VSL of the local process descriptor, that must be the reference process.
- * - For the FILE, ANON, & REMOTE types, it does not use the <base> and <size> arguments,
- *   but uses the specific MMAP virtual memory allocator.
+ * in the VSL of the local process descriptor.
+ * - For the FILE, ANON, & REMOTE types, it does not use the <base> argument, but uses 
+ *   the specific VMM MMAP allocator.
  * - For the STACK type, it does not use the <base> and <size> arguments,  but uses the
- *   and the <base> argument the specific STACK virtual memory allocator.
+ *   the specific VMM STACK allocator.
  * It checks collision with pre-existing vsegs.
  * To comply with the "on-demand" paging policy, this function does NOT modify the GPT,

trunk/kernel/mm/vseg.c

@@ -81 +81 @@
 }
 
-///////////////////////////////////
-void vseg_init( vseg_t      * vseg,
-                vseg_type_t   type,
-                    intptr_t      base,
-                uint32_t      size,
-                vpn_t         vpn_base,
-                vpn_t         vpn_size,
-                        uint32_t      file_offset,
-                uint32_t      file_size,
-                xptr_t        mapper_xp,
-                cxy_t         cxy )
+/////////////////////////////////////////
+void vseg_init_flags( vseg_t      * vseg,
+                      vseg_type_t   type )
 {
-    vseg->type        = type;
-        vseg->min         = base;
-        vseg->max         = base + size;
-    vseg->vpn_base    = vpn_base;
-        vseg->vpn_size    = vpn_size;
-    vseg->file_offset = file_offset;
-    vseg->file_size   = file_size;
-        vseg->mapper_xp   = mapper_xp;
-    vseg->cxy         = cxy;
-
     // set vseg flags depending on type
-        if     ( type == VSEG_TYPE_CODE )
+        if( type == VSEG_TYPE_CODE )
     {
         vseg->flags = VSEG_USER    |

trunk/kernel/mm/vseg.h

@@ -41 +41 @@
 typedef enum
 {
-    VSEG_TYPE_CODE   = 0,          /*! executable user code     / private / localized     */
-    VSEG_TYPE_DATA   = 1,          /*! initialized user data    / public  / distributed   */
-    VSEG_TYPE_STACK  = 2,          /*! execution user stack     / private / localized     */
-    VSEG_TYPE_ANON   = 3,          /*! anonymous mmap           / public  / localized     */
-    VSEG_TYPE_FILE   = 4,          /*! file mmap                / public  / localized     */
-    VSEG_TYPE_REMOTE = 5,          /*! remote mmap              / public  / localized     */
+    VSEG_TYPE_CODE   = 1,          /*! executable user code     / private / localized     */
+    VSEG_TYPE_DATA   = 2,          /*! initialized user data    / public  / distributed   */
+    VSEG_TYPE_STACK  = 3,          /*! execution user stack     / private / localized     */
+    VSEG_TYPE_ANON   = 4,          /*! anonymous mmap           / public  / localized     */
+    VSEG_TYPE_FILE   = 5,          /*! file mmap                / public  / localized     */
+    VSEG_TYPE_REMOTE = 6,          /*! remote mmap              / public  / localized     */
 
-    VSEG_TYPE_KCODE  = 6,          /*! executable kernel code   / private / localized     */
-    VSEG_TYPE_KDATA  = 7,          /*! initialized kernel data  / private / localized     */
-    VSEG_TYPE_KDEV   = 8,          /*! kernel peripheral device / public  / localized     */
+    VSEG_TYPE_KCODE  = 7,          /*! executable kernel code   / private / localized     */
+    VSEG_TYPE_KDATA  = 8,          /*! initialized kernel data  / private / localized     */
+    VSEG_TYPE_KDEV   = 9,          /*! kernel peripheral device / public  / localized     */
 }
 vseg_type_t;
@@ -115 +115 @@
 
 /*******************************************************************************************
- * This function initializes a local vseg descriptor, from the arguments values.
- * It does NOT register the vseg in the local VMM.
+ * This function initializes the "flags" field for a local <vseg> descriptor,
+ * depending on the vseg <type>. 
  *******************************************************************************************
  * @ vseg      : pointer on the vseg descriptor.
- * @ base      : vseg base address.
- * @ size      : vseg size (bytes).
- * @ vpn_base  : first page index.
- * @ vpn_size  : number of pages.
  * @ type      : vseg type.
- * @ cxy       : target cluster for physical mapping.
  ******************************************************************************************/
-void vseg_init( vseg_t      * vseg,
-                    vseg_type_t   type,
-                intptr_t      base,
-                    uint32_t      size,
-                vpn_t         vpn_base,
-                vpn_t         vpn_size,
-                uint32_t      file_offset,
-                uint32_t      file_size,
-                xptr_t        mapper_xp,
-                cxy_t         cxy );
+void vseg_init_flags( vseg_t      * vseg,
+                          vseg_type_t   type );
 
 /*******************************************************************************************