176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Copyright (C) 2007 Michael Brown <mbrown@fensystems.co.uk>. 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This program is free software; you can redistribute it and/or 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * modify it under the terms of the GNU General Public License as 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * published by the Free Software Foundation; either version 2 of the 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * License, or any later version. 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This program is distributed in the hope that it will be useful, but 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * WITHOUT ANY WARRANTY; without even the implied warranty of 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * General Public License for more details. 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * You should have received a copy of the GNU General Public License 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * along with this program; if not, write to the Free Software 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1976d05dc695b06c4e987bb8078f78032441e1430cGreg HartmanFILE_LICENCE ( GPL2_OR_LATER ); 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @file 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * External memory allocation 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <limits.h> 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <errno.h> 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <gpxe/uaccess.h> 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <gpxe/hidemem.h> 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <gpxe/memmap.h> 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <gpxe/umalloc.h> 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** Alignment of external allocated memory */ 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define EM_ALIGN ( 4 * 1024 ) 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** Equivalent of NOWHERE for user pointers */ 3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define UNOWHERE ( ~UNULL ) 4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** An external memory block */ 4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstruct external_memory { 4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /** Size of this memory block (excluding this header) */ 4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman size_t size; 4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /** Block is currently in use */ 4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int used; 4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}; 4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** Top of heap */ 5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic userptr_t top = UNULL; 5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** Bottom of heap (current lowest allocated block) */ 5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic userptr_t bottom = UNULL; 5476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 5676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Initialise external heap 5776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 5876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @ret rc Return status code 5976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 6076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic int init_eheap ( void ) { 6176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct memory_map memmap; 6276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long heap_size = 0; 6376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned int i; 6476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "Allocating external heap\n" ); 6676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman get_memmap ( &memmap ); 6876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for ( i = 0 ; i < memmap.count ; i++ ) { 6976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct memory_region *region = &memmap.regions[i]; 7076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long r_start, r_end; 7176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long r_size; 7276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "Considering [%llx,%llx)\n", region->start, region->end); 7476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Truncate block to 4GB */ 7676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( region->start > UINT_MAX ) { 7776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "...starts after 4GB\n" ); 7876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman continue; 7976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 8076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman r_start = region->start; 8176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( region->end > UINT_MAX ) { 8276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "...end truncated to 4GB\n" ); 8376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman r_end = 0; /* =4GB, given the wraparound */ 8476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 8576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman r_end = region->end; 8676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 8776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Use largest block */ 8976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman r_size = ( r_end - r_start ); 9076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( r_size > heap_size ) { 9176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "...new best block found\n" ); 9276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman top = bottom = phys_to_user ( r_end ); 9376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman heap_size = r_size; 9476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 9576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 9676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( ! heap_size ) { 9876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "No external heap available\n" ); 9976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return -ENOMEM; 10076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 10176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 10276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "External heap grows downwards from %lx\n", 10376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( top, 0 ) ); 10476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return 0; 10576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 10676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 10776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 10876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Collect free blocks 10976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 11076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 11176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void ecollect_free ( void ) { 11276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct external_memory extmem; 11376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 11476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Walk the free list and collect empty blocks */ 11576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while ( bottom != top ) { 11676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copy_from_user ( &extmem, bottom, -sizeof ( extmem ), 11776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sizeof ( extmem ) ); 11876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( extmem.used ) 11976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman break; 12076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "EXTMEM freeing [%lx,%lx)\n", user_to_phys ( bottom, 0 ), 12176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( bottom, extmem.size ) ); 12276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman bottom = userptr_add ( bottom, 12376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ( extmem.size + sizeof ( extmem ) ) ); 12476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 12576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 12676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 12876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Reallocate external memory 12976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 13076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @v old_ptr Memory previously allocated by umalloc(), or UNULL 13176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @v new_size Requested size 13276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @ret new_ptr Allocated memory, or UNULL 13376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 13476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Calling realloc() with a new size of zero is a valid way to free a 13576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * memory block. 13676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 13776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic userptr_t memtop_urealloc ( userptr_t ptr, size_t new_size ) { 13876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct external_memory extmem; 13976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman userptr_t new = ptr; 14076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman size_t align; 14176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int rc; 14276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 14376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Initialise external memory allocator if necessary */ 14476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( bottom == top ) { 14576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( ( rc = init_eheap() ) != 0 ) 14676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return UNULL; 14776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 14876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 14976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Get block properties into extmem */ 15076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( ptr && ( ptr != UNOWHERE ) ) { 15176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Determine old size */ 15276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copy_from_user ( &extmem, ptr, -sizeof ( extmem ), 15376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sizeof ( extmem ) ); 15476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 15576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Create a zero-length block */ 15676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ptr = bottom = userptr_add ( bottom, -sizeof ( extmem ) ); 15776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "EXTMEM allocating [%lx,%lx)\n", 15876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( ptr, 0 ), user_to_phys ( ptr, 0 ) ); 15976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman extmem.size = 0; 16076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 16176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman extmem.used = ( new_size > 0 ); 16276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 16376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Expand/shrink block if possible */ 16476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( ptr == bottom ) { 16576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Update block */ 16676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new = userptr_add ( ptr, - ( new_size - extmem.size ) ); 16776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman align = ( user_to_phys ( new, 0 ) & ( EM_ALIGN - 1 ) ); 16876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new_size += align; 16976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new = userptr_add ( new, -align ); 17076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "EXTMEM expanding [%lx,%lx) to [%lx,%lx)\n", 17176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( ptr, 0 ), 17276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( ptr, extmem.size ), 17376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( new, 0 ), 17476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( new, new_size )); 17576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman memmove_user ( new, 0, ptr, 0, ( ( extmem.size < new_size ) ? 17676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman extmem.size : new_size ) ); 17776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman extmem.size = new_size; 17876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman bottom = new; 17976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 18076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Cannot expand; can only pretend to shrink */ 18176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if ( new_size > extmem.size ) { 18276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Refuse to expand */ 18376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DBG ( "EXTMEM cannot expand [%lx,%lx)\n", 18476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( ptr, 0 ), 18576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( ptr, extmem.size ) ); 18676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return UNULL; 18776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 18876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 18976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 19076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Write back block properties */ 19176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copy_to_user ( new, -sizeof ( extmem ), &extmem, 19276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sizeof ( extmem ) ); 19376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 19476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Collect any free blocks and update hidden memory region */ 19576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ecollect_free(); 19676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman hide_umalloc ( user_to_phys ( bottom, -sizeof ( extmem ) ), 19776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman user_to_phys ( top, 0 ) ); 19876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 19976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return ( new_size ? new : UNOWHERE ); 20076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 20176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 20276d05dc695b06c4e987bb8078f78032441e1430cGreg HartmanPROVIDE_UMALLOC ( memtop, urealloc, memtop_urealloc ); 203