1/*
2 * Copyright (C) 2007 Michael Brown <mbrown@fensystems.co.uk>.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of the
7 * License, or any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17 */
18
19FILE_LICENCE ( GPL2_OR_LATER );
20
21/**
22 * @file
23 *
24 * External memory allocation
25 *
26 */
27
28#include <limits.h>
29#include <errno.h>
30#include <gpxe/uaccess.h>
31#include <gpxe/hidemem.h>
32#include <gpxe/memmap.h>
33#include <gpxe/umalloc.h>
34
35/** Alignment of external allocated memory */
36#define EM_ALIGN ( 4 * 1024 )
37
38/** Equivalent of NOWHERE for user pointers */
39#define UNOWHERE ( ~UNULL )
40
41/** An external memory block */
42struct external_memory {
43	/** Size of this memory block (excluding this header) */
44	size_t size;
45	/** Block is currently in use */
46	int used;
47};
48
49/** Top of heap */
50static userptr_t top = UNULL;
51
52/** Bottom of heap (current lowest allocated block) */
53static userptr_t bottom = UNULL;
54
55/**
56 * Initialise external heap
57 *
58 * @ret rc		Return status code
59 */
60static int init_eheap ( void ) {
61	struct memory_map memmap;
62	unsigned long heap_size = 0;
63	unsigned int i;
64
65	DBG ( "Allocating external heap\n" );
66
67	get_memmap ( &memmap );
68	for ( i = 0 ; i < memmap.count ; i++ ) {
69		struct memory_region *region = &memmap.regions[i];
70		unsigned long r_start, r_end;
71		unsigned long r_size;
72
73		DBG ( "Considering [%llx,%llx)\n", region->start, region->end);
74
75		/* Truncate block to 4GB */
76		if ( region->start > UINT_MAX ) {
77			DBG ( "...starts after 4GB\n" );
78			continue;
79		}
80		r_start = region->start;
81		if ( region->end > UINT_MAX ) {
82			DBG ( "...end truncated to 4GB\n" );
83			r_end = 0; /* =4GB, given the wraparound */
84		} else {
85			r_end = region->end;
86		}
87
88		/* Use largest block */
89		r_size = ( r_end - r_start );
90		if ( r_size > heap_size ) {
91			DBG ( "...new best block found\n" );
92			top = bottom = phys_to_user ( r_end );
93			heap_size = r_size;
94		}
95	}
96
97	if ( ! heap_size ) {
98		DBG ( "No external heap available\n" );
99		return -ENOMEM;
100	}
101
102	DBG ( "External heap grows downwards from %lx\n",
103	      user_to_phys ( top, 0 ) );
104	return 0;
105}
106
107/**
108 * Collect free blocks
109 *
110 */
111static void ecollect_free ( void ) {
112	struct external_memory extmem;
113
114	/* Walk the free list and collect empty blocks */
115	while ( bottom != top ) {
116		copy_from_user ( &extmem, bottom, -sizeof ( extmem ),
117				 sizeof ( extmem ) );
118		if ( extmem.used )
119			break;
120		DBG ( "EXTMEM freeing [%lx,%lx)\n", user_to_phys ( bottom, 0 ),
121		      user_to_phys ( bottom, extmem.size ) );
122		bottom = userptr_add ( bottom,
123				       ( extmem.size + sizeof ( extmem ) ) );
124	}
125}
126
127/**
128 * Reallocate external memory
129 *
130 * @v old_ptr		Memory previously allocated by umalloc(), or UNULL
131 * @v new_size		Requested size
132 * @ret new_ptr		Allocated memory, or UNULL
133 *
134 * Calling realloc() with a new size of zero is a valid way to free a
135 * memory block.
136 */
137static userptr_t memtop_urealloc ( userptr_t ptr, size_t new_size ) {
138	struct external_memory extmem;
139	userptr_t new = ptr;
140	size_t align;
141	int rc;
142
143	/* Initialise external memory allocator if necessary */
144	if ( bottom == top ) {
145		if ( ( rc = init_eheap() ) != 0 )
146			return UNULL;
147	}
148
149	/* Get block properties into extmem */
150	if ( ptr && ( ptr != UNOWHERE ) ) {
151		/* Determine old size */
152		copy_from_user ( &extmem, ptr, -sizeof ( extmem ),
153				 sizeof ( extmem ) );
154	} else {
155		/* Create a zero-length block */
156		ptr = bottom = userptr_add ( bottom, -sizeof ( extmem ) );
157		DBG ( "EXTMEM allocating [%lx,%lx)\n",
158		      user_to_phys ( ptr, 0 ), user_to_phys ( ptr, 0 ) );
159		extmem.size = 0;
160	}
161	extmem.used = ( new_size > 0 );
162
163	/* Expand/shrink block if possible */
164	if ( ptr == bottom ) {
165		/* Update block */
166		new = userptr_add ( ptr, - ( new_size - extmem.size ) );
167		align = ( user_to_phys ( new, 0 ) & ( EM_ALIGN - 1 ) );
168		new_size += align;
169		new = userptr_add ( new, -align );
170		DBG ( "EXTMEM expanding [%lx,%lx) to [%lx,%lx)\n",
171		      user_to_phys ( ptr, 0 ),
172		      user_to_phys ( ptr, extmem.size ),
173		      user_to_phys ( new, 0 ),
174		      user_to_phys ( new, new_size ));
175		memmove_user ( new, 0, ptr, 0, ( ( extmem.size < new_size ) ?
176						 extmem.size : new_size ) );
177		extmem.size = new_size;
178		bottom = new;
179	} else {
180		/* Cannot expand; can only pretend to shrink */
181		if ( new_size > extmem.size ) {
182			/* Refuse to expand */
183			DBG ( "EXTMEM cannot expand [%lx,%lx)\n",
184			      user_to_phys ( ptr, 0 ),
185			      user_to_phys ( ptr, extmem.size ) );
186			return UNULL;
187		}
188	}
189
190	/* Write back block properties */
191	copy_to_user ( new, -sizeof ( extmem ), &extmem,
192		       sizeof ( extmem ) );
193
194	/* Collect any free blocks and update hidden memory region */
195	ecollect_free();
196	hide_umalloc ( user_to_phys ( bottom, -sizeof ( extmem ) ),
197		       user_to_phys ( top, 0 ) );
198
199	return ( new_size ? new : UNOWHERE );
200}
201
202PROVIDE_UMALLOC ( memtop, urealloc, memtop_urealloc );
203