1/* ----------------------------------------------------------------------- *
2 *
3 *   Copyright 2007-2009 H. Peter Anvin - All Rights Reserved
4 *   Copyright 2009 Intel Corporation; author: H. Peter Anvin
5 *
6 *   Permission is hereby granted, free of charge, to any person
7 *   obtaining a copy of this software and associated documentation
8 *   files (the "Software"), to deal in the Software without
9 *   restriction, including without limitation the rights to use,
10 *   copy, modify, merge, publish, distribute, sublicense, and/or
11 *   sell copies of the Software, and to permit persons to whom
12 *   the Software is furnished to do so, subject to the following
13 *   conditions:
14 *
15 *   The above copyright notice and this permission notice shall
16 *   be included in all copies or substantial portions of the Software.
17 *
18 *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 *   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 *   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 *   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 *   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 *   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 *   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 *   OTHER DEALINGS IN THE SOFTWARE.
26 *
27 * ----------------------------------------------------------------------- */
28
29/*
30 * zonelist.c
31 *
32 * Deal with syslinux_memmap's, which are data structures designed to
33 * hold memory maps.  A zonelist is a sorted linked list of memory
34 * ranges, with the guarantee that no two adjacent blocks have the
35 * same range type.  Additionally, all unspecified memory have a range
36 * type of zero.
37 */
38
39#include <stdlib.h>
40#include <syslinux/align.h>
41#include <syslinux/movebits.h>
42#include <dprintf.h>
43
44/*
45 * Create an empty syslinux_memmap list.
46 */
47struct syslinux_memmap *syslinux_init_memmap(void)
48{
49    struct syslinux_memmap *sp, *ep;
50
51    sp = malloc(sizeof(*sp));
52    if (!sp)
53	return NULL;
54
55    ep = malloc(sizeof(*ep));
56    if (!ep) {
57	free(sp);
58	return NULL;
59    }
60
61    sp->start = 0;
62    sp->type = SMT_UNDEFINED;
63    sp->next = ep;
64
65    ep->start = 0;		/* Wrap around... */
66    ep->type = SMT_END;		/* End of chain */
67    ep->next = NULL;
68
69    return sp;
70}
71
72/*
73 * Add an item to a syslinux_memmap list, potentially overwriting
74 * what is already there.
75 */
76int syslinux_add_memmap(struct syslinux_memmap **list,
77			addr_t start, addr_t len,
78			enum syslinux_memmap_types type)
79{
80    addr_t last;
81    struct syslinux_memmap *mp, **mpp;
82    struct syslinux_memmap *range;
83    enum syslinux_memmap_types oldtype;
84
85    dprintf("Input memmap:\n");
86    syslinux_dump_memmap(*list);
87
88    /* Remove this to make len == 0 mean all of memory */
89    if (len == 0)
90	return 0;
91
92    /* Last byte -- to avoid rollover */
93    last = start + len - 1;
94
95    mpp = list;
96    oldtype = SMT_END;		/* Impossible value */
97    while (mp = *mpp, start > mp->start && mp->type != SMT_END) {
98	oldtype = mp->type;
99	mpp = &mp->next;
100    }
101
102    if (start < mp->start || mp->type == SMT_END) {
103	if (type != oldtype) {
104	    /* Splice in a new start token */
105	    range = malloc(sizeof(*range));
106	    if (!range)
107		return -1;
108
109	    range->start = start;
110	    range->type = type;
111	    *mpp = range;
112	    range->next = mp;
113	    mpp = &range->next;
114	}
115    } else {
116	/* mp is exactly aligned with the start of our region */
117	if (type != oldtype) {
118	    /* Reclaim this entry as our own boundary marker */
119	    oldtype = mp->type;
120	    mp->type = type;
121	    mpp = &mp->next;
122	}
123    }
124
125    while (mp = *mpp, last > mp->start - 1) {
126	oldtype = mp->type;
127	*mpp = mp->next;
128	free(mp);
129    }
130
131    if (last < mp->start - 1) {
132	if (oldtype != type) {
133	    /* Need a new end token */
134	    range = malloc(sizeof(*range));
135	    if (!range)
136		return -1;
137
138	    range->start = last + 1;
139	    range->type = oldtype;
140	    *mpp = range;
141	    range->next = mp;
142	}
143    } else {
144	if (mp->type == type) {
145	    /* Merge this region with the following one */
146	    *mpp = mp->next;
147	    free(mp);
148	}
149    }
150
151    dprintf("After adding (%#x,%#x,%d):\n", start, len, type);
152    syslinux_dump_memmap(*list);
153
154    return 0;
155}
156
157/*
158 * Verify what type a certain memory region is.  This function returns
159 * SMT_ERROR if the memory region has multiple types, except that
160 * SMT_FREE can be demoted to SMT_TERMINAL.
161 */
162enum syslinux_memmap_types syslinux_memmap_type(struct syslinux_memmap *list,
163						addr_t start, addr_t len)
164{
165    addr_t last, llast;
166
167    last = start + len - 1;
168
169    while (list->type != SMT_END) {
170	llast = list->next->start - 1;
171	if (list->start <= start) {
172	    if (llast >= last) {
173		return list->type;	/* Region has a well-defined type */
174	    } else if (llast >= start) {
175		/* Crosses region boundary */
176		while (valid_terminal_type(list->type)) {
177		    list = list->next;
178		    llast = list->next->start - 1;
179		    if (llast >= last)
180			return SMT_TERMINAL;
181		}
182		return SMT_ERROR;
183	    }
184	}
185	list = list->next;
186    }
187
188    return SMT_ERROR;		/* Internal error? */
189}
190
191/*
192 * Find the largest zone of a specific type.  Returns -1 on failure.
193 */
194int syslinux_memmap_largest(struct syslinux_memmap *list,
195			    enum syslinux_memmap_types type,
196			    addr_t * start, addr_t * len)
197{
198    addr_t size, best_size = 0;
199    struct syslinux_memmap *best = NULL;
200
201    while (list->type != SMT_END) {
202	size = list->next->start - list->start;
203
204	if (list->type == type && size > best_size) {
205	    best = list;
206	    best_size = size;
207	}
208
209	list = list->next;
210    }
211
212    if (!best)
213	return -1;
214
215    *start = best->start;
216    *len = best_size;
217
218    return 0;
219}
220
221/*
222 * Find the highest zone of a specific type that satisfies the
223 * constraints.
224 *
225 * 'start' is updated with the highest address on success. 'start' can
226 * be used to set a minimum address to begin searching from.
227 *
228 * Returns -1 on failure.
229 */
230int syslinux_memmap_highest(const struct syslinux_memmap *list,
231			    enum syslinux_memmap_types type,
232			    addr_t *start, addr_t len,
233			    addr_t ceiling, addr_t align)
234{
235    addr_t size, best;
236
237    for (best = 0; list->type != SMT_END; list = list->next) {
238	size = list->next->start - list->start;
239
240	if (list->type != type)
241	    continue;
242
243	if (list->start + size <= *start)
244	    continue;
245
246	if (list->start + len >= ceiling)
247	    continue;
248
249	if (list->start + size < ceiling)
250	    best = ALIGN_DOWN(list->start + size - len, align);
251	else
252	    best = ALIGN_DOWN(ceiling - len, align);
253
254	if (best < *start)
255	    best = 0;
256    }
257
258    if (!best)
259	return -1;
260
261    *start = best;
262
263    return 0;
264}
265
266/*
267 * Find the first (lowest address) zone of a specific type and of
268 * a certain minimum size, with an optional starting address.
269 * The input values of start and len are used as minima.
270 */
271int syslinux_memmap_find_type(struct syslinux_memmap *list,
272			      enum syslinux_memmap_types type,
273			      addr_t * start, addr_t * len, addr_t align)
274{
275    addr_t min_start = *start;
276    addr_t min_len = *len;
277
278    while (list->type != SMT_END) {
279	if (list->type == type) {
280	    addr_t xstart, xlen;
281	    xstart = min_start > list->start ? min_start : list->start;
282	    xstart = ALIGN_UP(xstart, align);
283
284	    if (xstart < list->next->start) {
285		xlen = list->next->start - xstart;
286		if (xlen >= min_len) {
287		    *start = xstart;
288		    *len = xlen;
289		    return 0;
290		}
291	    }
292	}
293	list = list->next;
294    }
295
296    return -1;			/* Not found */
297}
298
299/*
300 * Free a zonelist.
301 */
302void syslinux_free_memmap(struct syslinux_memmap *list)
303{
304    struct syslinux_memmap *ml;
305
306    while (list) {
307	ml = list;
308	list = list->next;
309	free(ml);
310    }
311}
312
313/*
314 * Duplicate a zonelist.  Returns NULL on failure.
315 */
316struct syslinux_memmap *syslinux_dup_memmap(struct syslinux_memmap *list)
317{
318    struct syslinux_memmap *newlist = NULL, **nlp = &newlist;
319    struct syslinux_memmap *ml;
320
321    while (list) {
322	ml = malloc(sizeof(*ml));
323	if (!ml) {
324	    syslinux_free_memmap(newlist);
325	    return NULL;
326	}
327	ml->start = list->start;
328	ml->type = list->type;
329	ml->next = NULL;
330	*nlp = ml;
331	nlp = &ml->next;
332
333	list = list->next;
334    }
335
336    return newlist;
337}
338
339/*
340 * Find a memory region, given a set of heuristics and update 'base' if
341 * successful.
342 */
343int syslinux_memmap_find(struct syslinux_memmap *mmap,
344			 addr_t *base, size_t size,
345			 bool relocate, size_t align,
346			 addr_t start_min, addr_t start_max,
347			 addr_t end_min, addr_t end_max)
348{
349    const struct syslinux_memmap *mp;
350    enum syslinux_memmap_types type;
351    bool ok;
352
353    if (!size)
354	return 0;
355
356    type = syslinux_memmap_type(mmap, *base, size);
357
358    /* This assumes SMT_TERMINAL is OK if we can get the exact address */
359    if (valid_terminal_type(type))
360	return 0;
361
362    if (!relocate) {
363	dprintf("Cannot relocate\n");
364	return -1;
365    }
366
367    ok = false;
368    for (mp = mmap; mp && mp->type != SMT_END; mp = mp->next) {
369	addr_t start, end;
370	start = mp->start;
371	end = mp->next->start;
372
373	if (mp->type != SMT_FREE)
374	    continue;
375
376	/* min */
377	if (end <= end_min)
378	    continue;	/* Only relocate upwards */
379
380	if (start < start_min)
381	    start = start_min;
382
383	/* max */
384	if (end > end_max)
385	    end = end_max;
386
387	start = ALIGN_UP(start, align);
388	if (start > start_max || start >= end)
389	    continue;
390
391	if (end - start >= size) {
392	    *base = start;
393	    ok = true;
394	    break;
395	}
396    }
397
398    if (!ok)
399	return -1;
400
401    return 0;
402}
403