//////////////////////////////////////////////////////////////////////////////// // 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