Index: /soft/giet_vm/giet_common/kernel_malloc.c =================================================================== --- /soft/giet_vm/giet_common/kernel_malloc.c (revision 466) +++ /soft/giet_vm/giet_common/kernel_malloc.c (revision 466) @@ -0,0 +1,369 @@ +//////////////////////////////////////////////////////////////////////////////// +// File : kernel_malloc.c +// Date : 05/12/2014 +// Author : alain greiner +// Copyright (c) UPMC-LIP6 +//////////////////////////////////////////////////////////////////////////////// +// Implementation note: +// - As this code is used to implement the SBT lock ptotecting TTY0, +// all functions here use the kernel _nolock_printf() function. +// - It must exist one vseg with the HEAP type in each cluster. The length +// must be a power of 2, and the base address must be aligned. +// - All allocated blocks have a size that is a power of 2, larger or equal +// to MIN_BLOCK_SIZE (typically 64 bytes), and are aligned. +// - All free blocks are pre-classed in 32 linked lists of free blocks, where +// all blocks in the same list have the same size. +// - The NEXT pointer implementing those linked lists is written +// in the 4 first bytes of the block itself, using the unsigned int type. +// - The pointers on the first free block for each size are stored in an +// array of pointers free[32] in the heap[x][y) structure itself. +// - Each kernel_heap[x][y] structure is protected by a specific +// queuing spin-lock. +// - The block size required can be any value, but the allocated block size +// is the smallest power of 2 value larger or equal to the requested size. +// - It pop the linked list of free blocks corresponding to size, +// and returns the block B if the list[size] is not empty. +// - If the list[size] is empty, it pop the list[size * 2]. +// If a block B' is found, it break this block in 2 B/2 blocks, returns +// the first B/2 block and push the other B/2 block into list[size]. +// - If the list[size * 2] is empty, it pop the list[size * 4]. +// If a block B is found, it break this block in 3 blocks B/4, B/4 and B/2, +// returns the first B/4 block, push the other blocks B/4 and B/2 into +// the proper lists. etc... +//////////////////////////////////////////////////////////////////////////////// + +#include "giet_config.h" +#include "hard_config.h" +#include "mapping_info.h" +#include "kernel_malloc.h" +#include "locks.h" +#include "tty0.h" +#include "utils.h" + +/////////////////////////////////////////////////////////////////////////////// +// Global variables defining the heap descriptors array (one heap per cluster) +/////////////////////////////////////////////////////////////////////////////// + +extern kernel_heap_t kernel_heap[X_SIZE][Y_SIZE]; + +/////////////////////////////////////////////////////////////////////////////// +// Macro returning the smallest power of 2 larger or equal to size value +/////////////////////////////////////////////////////////////////////////////// +#define GET_SIZE_INDEX(size) (size <= 0x00000001) ? 0 :\ + (size <= 0x00000002) ? 1 :\ + (size <= 0x00000004) ? 2 :\ + (size <= 0x00000008) ? 3 :\ + (size <= 0x00000010) ? 4 :\ + (size <= 0x00000020) ? 5 :\ + (size <= 0x00000040) ? 6 :\ + (size <= 0x00000080) ? 7 :\ + (size <= 0x00000100) ? 8 :\ + (size <= 0x00000200) ? 9 :\ + (size <= 0x00000400) ? 10 :\ + (size <= 0x00000800) ? 11 :\ + (size <= 0x00001000) ? 12 :\ + (size <= 0x00002000) ? 13 :\ + (size <= 0x00004000) ? 14 :\ + (size <= 0x00008000) ? 15 :\ + (size <= 0x00010000) ? 16 :\ + (size <= 0x00020000) ? 17 :\ + (size <= 0x00040000) ? 18 :\ + (size <= 0x00080000) ? 19 :\ + (size <= 0x00100000) ? 20 :\ + (size <= 0x00200000) ? 21 :\ + (size <= 0x00400000) ? 22 :\ + (size <= 0x00800000) ? 23 :\ + (size <= 0x01000000) ? 24 :\ + (size <= 0x02000000) ? 25 :\ + (size <= 0x04000000) ? 26 :\ + (size <= 0x08000000) ? 27 :\ + (size <= 0x10000000) ? 28 :\ + (size <= 0x20000000) ? 29 :\ + (size <= 0x40000000) ? 30 :\ + (size <= 0x80000000) ? 31 :\ + 32 +#if GIET_DEBUG_SYS_MALLOC +//////////////////////////////////////////////// +static void _display_free_array( unsigned int x, + unsigned int y ) +{ + _nolock_printf(" Kernel Heap[%d][%d]\n" + " - heap_base = %x\n" + " - heap_size = %x\n" + " - free[0] = %x\n" + " - free[1] = %x\n" + " - free[2] = %x\n" + " - free[3] = %x\n" + " - free[4] = %x\n" + " - free[5] = %x\n" + " - free[6] = %x\n" + " - free[7] = %x\n" + " - free[8] = %x\n" + " - free[9] = %x\n" + " - free[10] = %x\n" + " - free[11] = %x\n" + " - free[12] = %x\n" + " - free[13] = %x\n" + " - free[14] = %x\n" + " - free[15] = %x\n" + " - free[16] = %x\n" + " - free[17] = %x\n" + " - free[18] = %x\n" + " - free[19] = %x\n" + " - free[20] = %x\n" + " - free[21] = %x\n" + " - free[22] = %x\n" + " - free[23] = %x\n", + kernel_heap[x][y].x, kernel_heap[x][y].y, + kernel_heap[x][y].heap_base, kernel_heap[x][y].heap_size, + kernel_heap[x][y].free[0] , kernel_heap[x][y].free[1], + kernel_heap[x][y].free[2] , kernel_heap[x][y].free[3], + kernel_heap[x][y].free[4] , kernel_heap[x][y].free[5], + kernel_heap[x][y].free[6] , kernel_heap[x][y].free[7], + kernel_heap[x][y].free[8] , kernel_heap[x][y].free[9], + kernel_heap[x][y].free[10], kernel_heap[x][y].free[11], + kernel_heap[x][y].free[12], kernel_heap[x][y].free[13], + kernel_heap[x][y].free[14], kernel_heap[x][y].free[15], + kernel_heap[x][y].free[16], kernel_heap[x][y].free[17], + kernel_heap[x][y].free[18], kernel_heap[x][y].free[19], + kernel_heap[x][y].free[20], kernel_heap[x][y].free[21], + kernel_heap[x][y].free[22], kernel_heap[x][y].free[23]); +} // end display_free array() +#endif + + + + +///////////////////////////////////////////// +void _get_heap_info( unsigned int* heap_base, + unsigned int* heap_size, + unsigned int x, + unsigned int y ) +{ + mapping_header_t * header = (mapping_header_t *)SEG_BOOT_MAPPING_BASE; + mapping_vseg_t * vsegs = _get_vseg_base(header); + mapping_vobj_t * vobjs = _get_vobj_base(header); + mapping_pseg_t * psegs = _get_pseg_base(header); + mapping_cluster_t * clusters = _get_cluster_base(header); + + unsigned int vseg_id; + unsigned int vobj_id; + unsigned int pseg_id; + unsigned int cluster_id; + + // checking coordinates + if ( (x >= X_SIZE) || (y >= Y_SIZE) ) + { + _nolock_printf("[GIET ERROR] _get_heap_info() illegal (%d,%d) coordinates\n", + x , y ); + _exit(); + } + + // scan all global vsegs + for ( vseg_id = 0 ; vseg_id < header->globals ; vseg_id++ ) + { + pseg_id = vsegs[vseg_id].psegid; + cluster_id = psegs[pseg_id].clusterid; + vobj_id = vsegs[vseg_id].vobj_offset; + if ( (vobjs[vobj_id].type == VOBJ_TYPE_HEAP) && + (clusters[cluster_id].x == x) && + (clusters[cluster_id].y == y) ) + { + *heap_base = vsegs[vseg_id].vbase; + *heap_size = vobjs[vobj_id].length; + return; + } + } + + // exit if not found + _nolock_printf("[GIET ERROR] _get_heap_info() heap[%d][%d] vseg not found\n", + x , y ); + _exit(); + +} // end _get_heap_info() + + + +///////////////// +void _heap_init() +{ + unsigned int heap_base; + unsigned int heap_size; + unsigned int heap_index; + + unsigned int index; + unsigned int x; + unsigned int y; + + for ( x = 0 ; x < X_SIZE ; x++ ) + { + for ( y = 0 ; y < Y_SIZE ; y++ ) + { + // get heap_base, heap size, and heap index + _get_heap_info( &heap_base, &heap_size, x, y ); + heap_index = GET_SIZE_INDEX( heap_size ); + + // checking heap segment constraints + if ( heap_size != (1<free[searched_index-1]; + heap->free[searched_index-1] = (unsigned int)new; + + if ( searched_index == requested_index + 1 ) // terminal case: return lower half block + { + return vaddr; + } + else // non terminal case : lower half block must be split again + { + return split_block( heap, vaddr, searched_index-1, requested_index ); + } +} // end split_block() + + + +///////////////////////////////////////////// +unsigned int get_block( kernel_heap_t* heap, + unsigned int searched_index, + unsigned int requested_index ) +{ + // test terminal case + if ( (1< heap->heap_size ) // failure : return a NULL value + { + return 0; + } + else // search a block in free[searched_index] + { + unsigned int vaddr = heap->free[searched_index]; + if ( vaddr == 0 ) // block not found : search in free[searched_index+1] + { + return get_block( heap, searched_index+1, requested_index ); + } + else // block found : pop it from free[searched_index] + { + // pop the block from free[searched_index] + unsigned int next = *((unsigned int*)vaddr); + heap->free[searched_index] = next; + + // test if the block must be split + if ( searched_index == requested_index ) // no split required + { + return vaddr; + } + else // split is required + { + return split_block( heap, vaddr, searched_index, requested_index ); + } + } + } +} // end get_block() + + + +//////////////////////////////////////// +void* _remote_malloc( unsigned int size, + unsigned int x, + unsigned int y ) +{ + // checking arguments + if (size == 0) + { + _nolock_printf("[GIET ERROR] _remote_malloc() : requested size = 0 \n"); + _exit(); + } + if ( x >= X_SIZE ) + { + _nolock_printf("[GIET ERROR] _remote_malloc() : x coordinate too large\n"); + _exit(); + } + if ( y >= Y_SIZE ) + { + _nolock_printf("[GIET ERROR] _remote_malloc() : y coordinate too large\n"); + _exit(); + } + + // normalize size + if ( size < MIN_BLOCK_SIZE ) size = MIN_BLOCK_SIZE; + + // compute requested_index for the free[] array + unsigned int requested_index = GET_SIZE_INDEX( size ); + + // take the lock + _spin_lock_acquire( &kernel_heap[x][y].lock ); + + // call the recursive function get_block + unsigned int base = get_block( &kernel_heap[x][y], + requested_index, + requested_index ); + // release the lock + _spin_lock_release( &kernel_heap[x][y].lock ); + +#if GIET_DEBUG_SYS_MALLOC +_nolock_printf("\n[DEBUG KERNEL_MALLOC] malloc vaddr %x from kernel_heap[%d][%d]\n", + base , x , y ); +_display_free_array(x,y); +#endif + + return (void*)base; + +} // end remote_malloc() + + + +// Local Variables: +// tab-width: 4 +// c-basic-offset: 4 +// c-file-offsets:((innamespace . 0)(inline-open . 0)) +// indent-tabs-mode: nil +// End: +// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 + + + Index: /soft/giet_vm/giet_common/kernel_malloc.h =================================================================== --- /soft/giet_vm/giet_common/kernel_malloc.h (revision 466) +++ /soft/giet_vm/giet_common/kernel_malloc.h (revision 466) @@ -0,0 +1,61 @@ +////////////////////////////////////////////////////////////////////////////////// +// File : kernel_malloc.h +// Date : 05/12/2014 +// Author : alain greiner +// Copyright (c) UPMC-LIP6 +////////////////////////////////////////////////////////////////////////////////// +// The kernel_malloc.c and kernel_malloc.h files are part of the giet_vm kernel. +////////////////////////////////////////////////////////////////////////////////// + +#ifndef KERNEL_MALLOC_H_ +#define KERNEL_MALLOC_H_ + +#include "locks.h" +#include "hard_config.h" + + +#define MIN_BLOCK_SIZE 0x40 + + +////////////////////////////////////////////////////////////////////////////////// +// heap descriptor (one per cluster) +////////////////////////////////////////////////////////////////////////////////// + +typedef struct kernel_heap_s +{ + spin_lock_t lock; // lock protecting exclusive access + unsigned int x; // cluster X coordinate + unsigned int y; // cluster Y coordinate + unsigned int heap_base; // heap base address + unsigned int heap_size; // heap size (bytes) + unsigned int free[32]; // array of base addresses of free blocks + // (address of first block of a given size) +} kernel_heap_t; + +////////////////////////////////////////////////////////////////////////////////// +// global variables +////////////////////////////////////////////////////////////////////////////////// + +extern kernel_heap_t kernel_heap[X_SIZE][Y_SIZE]; + +////////////////////////////////////////////////////////////////////////////////// +// access functions +////////////////////////////////////////////////////////////////////////////////// + +extern void* _remote_malloc( unsigned int size, + unsigned int x, + unsigned int y ); + +extern void _heap_init(); + + +#endif + +// Local Variables: +// tab-width: 4 +// c-basic-offset: 4 +// c-file-offsets:((innamespace . 0)(inline-open . 0)) +// indent-tabs-mode: nil +// End: +// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 + Index: /soft/giet_vm/giet_common/locks.c =================================================================== --- /soft/giet_vm/giet_common/locks.c (revision 465) +++ /soft/giet_vm/giet_common/locks.c (revision 466) @@ -8,5 +8,8 @@ #include "locks.h" #include "giet_config.h" +#include "hard_config.h" #include "utils.h" +#include "tty0.h" +#include "kernel_malloc.h" /////////////////////////////////////////////////// @@ -32,98 +35,21 @@ } -//////////////////////////////////// -void _lock_init( spin_lock_t* lock ) -{ - lock->current = 0; - lock->free = 0; - -#if GIET_DEBUG_SYS_LOCK +/////////////////////////////////////////////////////////////////////////////////// +// Simple lock access functions +/////////////////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////// +void _simple_lock_acquire( simple_lock_t* lock ) +{ + +#if GIET_DEBUG_SIMPLE_LOCK unsigned int gpid = _get_procid(); unsigned int x = gpid >> (Y_WIDTH + P_WIDTH); unsigned int y = (gpid >> P_WIDTH) & ((1<current, lock->free ); -#endif - -} - - -//////////////////////////////////////// -void _lock_acquire( spin_lock_t* lock ) -{ - // get next free slot index fromlock - unsigned int ticket = _atomic_increment( &lock->free, 1 ); - -#if GIET_DEBUG_SYS_LOCK -unsigned int gpid = _get_procid(); -unsigned int x = gpid >> (Y_WIDTH + P_WIDTH); -unsigned int y = (gpid >> P_WIDTH) & ((1<current, lock->free ); -#endif - - - // poll the spin_lock current slot index - asm volatile("5678: \n" - "lw $10, 0(%0) \n" - "move $11, %1 \n" - "bne $10, $11, 5678b \n" - : - : "r"(lock), "r"(ticket) - : "$10", "$11" ); - -#if GIET_DEBUG_SYS_LOCK -_printf("\n[SYS_LOCK DEBUG] P[%d,%d,%d] get lock = %x" - " at cycle %d (current = %d / free = %d)\n", - x, y, l, (unsigned int)lock, - _get_proctime(), lock->current, lock->free ); -#endif - -} - -//////////////////////////////////////// -void _lock_release( spin_lock_t* lock ) -{ - unsigned int current = lock->current; - - if ( current == (GIET_LOCK_MAX_TICKET - 1) ) current = 0; - else current = current + 1; - - asm volatile ( "sync \n" /* for consistency */ - "sw %1, 0(%0) \n" /* release lock */ - : - : "r"(lock), "r"(current) - : "memory" ); - - -#if GIET_DEBUG_SYS_LOCK -unsigned int gpid = _get_procid(); -unsigned int x = gpid >> (Y_WIDTH + P_WIDTH); -unsigned int y = (gpid >> P_WIDTH) & ((1<current, lock->free ); -#endif - -} - - - - - - - - -//////////////////////////////////////////////// -void _simple_lock_acquire( simple_lock_t* lock ) -{ +_nolock_printf("\n[DEBUG SIMPLE_LOCK] P[%d,%d,%d] enters acquire() at cycle %d\n", + x , y , l , _get_proctime() ); +#endif + asm volatile ( "1515: \n" "lw $2, 0(%0) \n" /* $2 <= lock current value */ @@ -137,4 +63,10 @@ : "r"(lock) : "$2", "$3", "memory" ); + +#if GIET_DEBUG_SIMPLE_LOCK +_nolock_printf("\n[DEBUG SIMPLE_LOCK] P[%d,%d,%d] exit acquire() at cycle %d\n", + x , y , l , _get_proctime() ); +#endif + } @@ -147,6 +79,411 @@ : "r"(lock) : "memory" ); -} - + +#if GIET_DEBUG_SIMPLE_LOCK +unsigned int gpid = _get_procid(); +unsigned int x = gpid >> (Y_WIDTH + P_WIDTH); +unsigned int y = (gpid >> P_WIDTH) & ((1<current = 0; + lock->free = 0; + +#if GIET_DEBUG_SPIN_LOCK +unsigned int gpid = _get_procid(); +unsigned int x = gpid >> (Y_WIDTH + P_WIDTH); +unsigned int y = (gpid >> P_WIDTH) & ((1<free, 1 ); + +#if GIET_DEBUG_SPIN_LOCK +unsigned int gpid = _get_procid(); +unsigned int x = gpid >> (Y_WIDTH + P_WIDTH); +unsigned int y = (gpid >> P_WIDTH) & ((1<current; + + if ( current == (GIET_LOCK_MAX_TICKET - 1) ) current = 0; + else current = current + 1; + + asm volatile ( "sync \n" /* for consistency */ + "sw %1, 0(%0) \n" /* release lock */ + : + : "r"(lock), "r"(current) + : "memory" ); + + +#if GIET_DEBUG_SPIN_LOCK +unsigned int gpid = _get_procid(); +unsigned int x = gpid >> (Y_WIDTH + P_WIDTH); +unsigned int y = (gpid >> P_WIDTH) & ((1<> (Y_WIDTH + P_WIDTH); +unsigned int py = (gpid >> P_WIDTH) & ((1<node[x][y][level]; + + if (level == 0 ) // terminal case + { + // initializes target node + node->taken = 0; + node->level = level; + node->parent = parent; + node->child0 = NULL; + node->child1 = NULL; + node->x = x; + node->y = y; + +#if GIET_DEBUG_SBT_LOCK +_nolock_printf("\n[DEBUG SBT_LOCK] P[%d,%d,%d] initialises SBT node[%d,%d,%d] : " + "parent = %x / childO = %x / child1 = %x\n", + px , py , pl , node->x , node->y , node->level , + (unsigned int)node->parent , (unsigned int)node->child0 , (unsigned int)node->child1 ); +#endif + + } + else // non terminal case + { + unsigned int x0; // x coordinate for child0 + unsigned int y0; // y coordinate for child0; + unsigned int x1; // x coordinate for child1; + unsigned int y1; // y coordinate for child1; + + // the child0 coordinates are equal to the parent coordinates + // the child1 coordinates are incremented depending on the level value + if ( level & 0x1 ) // odd level => X binary tree + { + x0 = x; + y0 = y; + x1 = x + (1 << ((level-1)>>1)); + y1 = y; + } + else // even level => Y binary tree + { + x0 = x; + y0 = y; + x1 = x; + y1 = y + (1 << ((level-1)>>1)); + } + + // initializes target node + node->taken = 0; + node->level = level; + node->parent = parent; + node->child0 = lock->node[x0][y0][level-1]; + node->child1 = lock->node[x1][y1][level-1]; + +#if GIET_DEBUG_SBT_LOCK +_nolock_printf("\n[DEBUG SBT_LOCK] P[%d,%d,%d] initialises SBT node[%d,%d,%d] : " + "parent = %x / childO = %x / child1 = %x\n", + px , py , pl , x , y , level , + (unsigned int)node->parent , (unsigned int)node->child0 , (unsigned int)node->child1 ); +#endif + + // recursive calls for children nodes + _sbt_lock_build( lock , x0 , y0 , level-1 , node ); + _sbt_lock_build( lock , x1 , y1 , level-1 , node ); + } + +} // end _sbt_lock_build() + +////////////////////////////////////////////////////////////////////////////////// +// This recursive function is used by the sbt_lock_acquire() function to +// get the SBT lock: It tries to get each "partial" lock on the path from bottom +// to top, using an atomic LL/SC, and starting from bottom. +// It is blocking : it poll each "partial lock until it can be taken. +// The lock is finally obtained when all "partial" locks, at all levels are taken. +////////////////////////////////////////////////////////////////////////////////// +static void _sbt_lock_take( lock_node_t* node ) +{ + // try to take "partial" lock + unsigned int* taken = &node->taken; + + asm volatile ( "1945: \n" + "lw $2, 0(%0) \n" /* $2 <= lock current value */ + "bnez $2, 1945b \n" /* retry if lock already taken */ + "ll $2, 0(%0) \n" /* ll_buffer <= lock current value */ + "bnez $2, 1945b \n" /* retry if lock already taken */ + "li $3, 1 \n" /* $3 <= argument for sc */ + "sc $3, 0(%0) \n" /* try to set lock */ + "beqz $3, 1945b \n" /* retry if sc failure */ + : + : "r"(taken) + : "$2", "$3", "memory" ); + +#if GIET_DEBUG_SBT_LOCK +unsigned int gpid = _get_procid(); +unsigned int px = gpid >> (Y_WIDTH + P_WIDTH); +unsigned int py = (gpid >> P_WIDTH) & ((1<x , node->y , node->level , (unsigned int)node ); +#endif + + // try to take the parent node lock until top is reached + if ( node->parent != NULL ) _sbt_lock_take( node->parent ); + +} // end _sbt_lock_take() + + +///////////////////////////////////////////////////////////////////////////////// +// This recursive function is used by the sbt_lock_release() function to +// release the SBT lock: It reset all "partial" locks on the path from bottom +// to top, using a normal write, and starting from bottom. +///////////////////////////////////////////////////////////////////////////////// +static void _sbt_lock_free( lock_node_t* node ) +{ + // reset "partial" lock + node->taken = 0; + +#if GIET_DEBUG_SBT_LOCK +unsigned int gpid = _get_procid(); +unsigned int px = gpid >> (Y_WIDTH + P_WIDTH); +unsigned int py = (gpid >> P_WIDTH) & ((1<x , node->y , node->level , (unsigned int)node ); +#endif + + // reset parent node until top is reached + if ( node->parent != NULL ) _sbt_lock_free( node->parent ); + +} // end _sbt_lock_free() + +////////////////////////////////////////////////////////////////////////////////// +// This external function initialises the distributed SBT lock. +////////////////////////////////////////////////////////////////////////////////// +void _sbt_lock_init( sbt_lock_t* lock ) +{ + unsigned int levels = 0; // depth of the SBT (number of levels) + + // compute SBT levels + if ((X_SIZE == 1 ) && (Y_SIZE == 1 )) levels = 1; + else if ((X_SIZE == 2 ) && (Y_SIZE == 1 )) levels = 2; + else if ((X_SIZE == 2 ) && (Y_SIZE == 2 )) levels = 3; + else if ((X_SIZE == 4 ) && (Y_SIZE == 2 )) levels = 4; + else if ((X_SIZE == 4 ) && (Y_SIZE == 4 )) levels = 5; + else if ((X_SIZE == 8 ) && (Y_SIZE == 4 )) levels = 6; + else if ((X_SIZE == 8 ) && (Y_SIZE == 8 )) levels = 7; + else if ((X_SIZE == 16) && (Y_SIZE == 8 )) levels = 8; + else if ((X_SIZE == 16) && (Y_SIZE == 16)) levels = 9; + else + { + _nolock_printf("\n[GIET ERROR] _sbt_lock_init() :illegal X_SIZE/Y_SIZE \n"); + _exit(); + } + +#if GIET_DEBUG_SBT_LOCK +unsigned int gpid = _get_procid(); +unsigned int px = gpid >> (Y_WIDTH + P_WIDTH); +unsigned int py = (gpid >> P_WIDTH) & ((1<node[x][y][l] = (lock_node_t*)_remote_malloc( sizeof(lock_node_t), + x, y ); + +#if GIET_DEBUG_SBT_LOCK +_nolock_printf("\n[DEBUG SBT_LOCK] P[%d,%d,%d] allocates SBT node[%d,%d,%d] : vaddr = %x\n", + px , py , pl , x , y , l , (unsigned int)lock->node[x][y][l] ); +#endif + } + } + } + } + +#if GIET_DEBUG_SBT_LOCK +_nolock_printf("\n[DEBUG SBT_LOCK] SBT nodes initialisation starts\n"); +#endif + + // recursively initialize all SBT nodes from root to bottom + _sbt_lock_build( lock, // pointer on the SBT lock descriptor + 0, // x coordinate + 0, // y coordinate + levels-1, // level in SBT + NULL ); // pointer on the parent node + + asm volatile ("sync" ::: "memory"); + +#if GIET_DEBUG_SBT_LOCK +_nolock_printf("\n[DEBUG SBT_LOCK] SBT nodes initialisation completed\n"); +#endif + +} // end _sbt_lock_init() + +////////////////////////////////////////////////////////////////////////////////// +// This external function get thes SBT lock. +// Returns only when the lock has been taken. +///////////////////////////////////////////////////////////////////////////////// +void _sbt_lock_acquire( sbt_lock_t* lock ) +{ + // get cluster coordinates + unsigned int gpid = _get_procid(); + unsigned int x = (gpid >> (Y_WIDTH + P_WIDTH)) & ((1<> P_WIDTH) & ((1<node[x][y][0] ); +} + + +///////////////////////////////////////////////////////////////////////////////// +// This external function releases the SBT lock. +///////////////////////////////////////////////////////////////////////////////// +void _sbt_lock_release( sbt_lock_t* lock ) +{ + // get cluster coordinates + unsigned int gpid = _get_procid(); + unsigned int x = (gpid >> (Y_WIDTH + P_WIDTH)) & ((1<> P_WIDTH) & ((1<node[x][y][0] ); +} // Local Variables: Index: /soft/giet_vm/giet_common/locks.h =================================================================== --- /soft/giet_vm/giet_common/locks.h (revision 465) +++ /soft/giet_vm/giet_common/locks.h (revision 466) @@ -6,6 +6,5 @@ /////////////////////////////////////////////////////////////////////////////////// // The locks.c and locks.h files are part of the GIET-VM nano-kernel. -// They define both atomic increment operations and locks. -// The locks used gy the GIET_VM are spin-locks with a waiting queue. +// They define both atomic increment operations and three types of locks. /////////////////////////////////////////////////////////////////////////////////// @@ -13,7 +12,22 @@ #define GIET_LOCKS_H +#include "hard_config.h" + /////////////////////////////////////////////////////////////////////////////////// -// This structure implements a spin-lock with waiting file. -// There is at most one lock per cache line. +// Simple lock structure and access functions +/////////////////////////////////////////////////////////////////////////////////// + +typedef struct simple_lock_s +{ + unsigned int value; // lock taken if non zero + unsigned int padding[15]; // for 64 bytes alignment +} simple_lock_t; + +extern void _simple_lock_acquire( simple_lock_t* lock ); + +extern void _simple_lock_release( simple_lock_t* lock ); + +/////////////////////////////////////////////////////////////////////////////////// +// Queuing lock structure and access functions /////////////////////////////////////////////////////////////////////////////////// @@ -21,30 +35,44 @@ { unsigned int current; // current slot index - unsigned int free; // next free slot index + unsigned int free; // next free tiket index unsigned int padding[14]; // for 64 bytes alignment } spin_lock_t; - -typedef struct simple_lock_s -{ - unsigned int value; - unsigned int padding[15]; -} simple_lock_t; - -/////////////////////////////////////////////////////////////////////////////////// -// Locks access functions -/////////////////////////////////////////////////////////////////////////////////// extern unsigned int _atomic_increment( unsigned int* ptr, unsigned int increment ); -extern void _lock_init( spin_lock_t* lock ); +extern void _spin_lock_init( spin_lock_t* lock ); -extern void _lock_acquire( spin_lock_t* lock ); +extern void _spin_lock_acquire( spin_lock_t* lock ); -extern void _lock_release( spin_lock_t* lock ); +extern void _spin_lock_release( spin_lock_t* lock ); -extern void _simple_lock_acquire( simple_lock_t* lock ); +////////////////////////////////////////////////////////////////////////////////// +// SBT lock structures and access functions +////////////////////////////////////////////////////////////////////////////////// -extern void _simple_lock_release( simple_lock_t* lock ); +typedef struct lock_node_s +{ + unsigned int taken; // lock taken if non zero + unsigned int level; // hierarchical level (0 is bottom) + struct lock_node_s* parent; // pointer on parent node (NULL for root) + struct lock_node_s* child0; // pointer on children node + struct lock_node_s* child1; // pointer on children node + unsigned int x; // cluster x coordinate + unsigned int y; // cluster y coordinate + unsigned int padding[9]; // for 64 bytes alignment +} lock_node_t; + +typedef struct sbt_lock_s +{ + unsigned int ntasks; // total number of expected tasks + lock_node_t* node[X_SIZE][Y_SIZE][9]; // array of pointers on SBT nodes +} sbt_lock_t; + +extern void _sbt_lock_init( sbt_lock_t* lock ); + +extern void _sbt_lock_acquire( sbt_lock_t* lock ); + +extern void _sbt_lock_release( sbt_lock_t* lock ); #endif Index: /soft/giet_vm/giet_common/tty0.c =================================================================== --- /soft/giet_vm/giet_common/tty0.c (revision 465) +++ /soft/giet_vm/giet_common/tty0.c (revision 466) @@ -10,6 +10,6 @@ #include #include +#include #include -#include #include #include @@ -114,14 +114,7 @@ } -////////////////////////////////// -void _printf( char * format, ... ) -{ - va_list ap; - va_start(ap, format); - unsigned int save_sr; // to save SR value in critical section - - // get TTY lock - _it_disable( &save_sr ); - _simple_lock_acquire( &_tty_tx_lock[0] ); +////////////////////////////////////////////////////////// +static void _kernel_printf( char * format, va_list* args ) +{ printf_text: @@ -143,9 +136,4 @@ } - // release TTY lock - _simple_lock_release( &_tty_tx_lock[0] ); - _it_restore( &save_sr ); - - va_end(ap); return; @@ -163,5 +151,5 @@ case ('c'): /* char conversion */ { - int val = va_arg( ap, int ); + int val = va_arg( *args , int ); len = 1; buf[0] = val; @@ -171,5 +159,5 @@ case ('d'): /* 32 bits decimal signed */ { - int val = va_arg( ap, int ); + int val = va_arg( *args , int ); if (val < 0) { @@ -188,5 +176,5 @@ case ('u'): /* 32 bits decimal unsigned */ { - unsigned int val = va_arg( ap, unsigned int ); + unsigned int val = va_arg( *args , unsigned int ); for(i = 0; i < 10; i++) { @@ -200,5 +188,5 @@ case ('x'): /* 32 bits hexadecimal unsigned */ { - unsigned int val = va_arg( ap, unsigned int ); + unsigned int val = va_arg( *args , unsigned int ); if ( _tty0_write( "0x" , 2 ) ) goto return_error; for(i = 0; i < 8; i++) @@ -213,5 +201,5 @@ case ('l'): /* 64 bits hexadecimal unsigned */ { - unsigned long long val = va_arg( ap, unsigned long long ); + unsigned long long val = va_arg( *args , unsigned long long ); if ( _tty0_write( "0x" , 2 ) ) goto return_error; for(i = 0; i < 16; i++) @@ -226,5 +214,5 @@ case ('s'): /* string */ { - char* str = va_arg( ap, char* ); + char* str = va_arg( *args , char* ); while (str[len]) { @@ -246,14 +234,9 @@ { - // release TTY lock - _simple_lock_release( &_tty_tx_lock[0] ); - _it_restore( &save_sr ); - - // try to print a non protected error message... + // try to print an error message and exit... unsigned int procid = _get_procid(); unsigned int x = (procid >> (Y_WIDTH + P_WIDTH)) & ((1<> P_WIDTH) & ((1<