1/*-
2 * Copyright (c) 2002 Marcel Moolenaar
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#if HAVE_NBTOOL_CONFIG_H
28#include "nbtool_config.h"
29#endif
30
31#include <sys/cdefs.h>
32#ifdef __FBSDID
33__FBSDID("$FreeBSD: src/sbin/gpt/map.c,v 1.6 2005/08/31 01:47:19 marcel Exp $");
34#endif
35#ifdef __RCSID
36__RCSID("$NetBSD: map.c,v 1.16 2023/12/05 17:23:19 tsutsui Exp $");
37#endif
38
39#include <sys/types.h>
40#include <err.h>
41#include <stdio.h>
42#include <stdlib.h>
43
44#include "map.h"
45#include "gpt.h"
46#include "gpt_private.h"
47
48static map_t
49map_create(off_t start, off_t size, int type)
50{
51	map_t m;
52
53	m = calloc(1, sizeof(*m));
54	if (m == NULL)
55		return NULL;
56	m->map_start = start;
57	m->map_size = size;
58	m->map_next = m->map_prev = NULL;
59	m->map_type = type;
60	m->map_index = 0;
61	m->map_data = NULL;
62	m->map_alloc = 0;
63	return m;
64}
65
66static void
67map_destroy(map_t m)
68{
69	if (m == NULL)
70		return;
71	if (m->map_alloc)
72		free(m->map_data);
73	free(m);
74}
75
76static const char *maptypes[] = {
77	"unused",
78	"mbr",
79	"mbr partition",
80	"primary gpt header",
81	"secondary gpt header",
82	"primary gpt table",
83	"secondary gpt table",
84	"gpt partition",
85	"protective mbr",
86};
87
88static const char *
89map_type(int t)
90{
91	if ((size_t)t >= __arraycount(maptypes))
92		return "*unknown*";
93	return maptypes[t];
94}
95
96map_t
97map_add(gpt_t gpt, off_t start, off_t size, int type, void *data, int alloc)
98{
99	map_t m, n, p;
100
101#ifdef DEBUG
102	printf("add: %s %#jx %#jx\n", map_type(type), (uintmax_t)start,
103	    (uintmax_t)size);
104	for (n = gpt->mediamap; n; n = n->map_next)
105		printf("have: %s %#jx %#jx\n", map_type(n->map_type),
106		    (uintmax_t)n->map_start, (uintmax_t)n->map_size);
107#endif
108
109	n = gpt->mediamap;
110	while (n != NULL && n->map_start + n->map_size <= start)
111		n = n->map_next;
112	if (n == NULL) {
113		if (!(gpt->flags & GPT_QUIET))
114			gpt_warnx(gpt, "Can't find map");
115		return NULL;
116	}
117
118	if (n->map_start + n->map_size < start + size) {
119		if (!(gpt->flags & GPT_QUIET))
120			gpt_warnx(gpt, "map entry doesn't fit media: "
121			    "new start + new size < start + size\n"
122			    "(%jx + %jx < %jx + %jx)",
123			    n->map_start, n->map_size, start, size);
124		return NULL;
125	}
126
127	if (n->map_start == start && n->map_size == size) {
128		if (n->map_type != MAP_TYPE_UNUSED) {
129			if (n->map_type != MAP_TYPE_MBR_PART ||
130			    type != MAP_TYPE_GPT_PART) {
131				if (!(gpt->flags & GPT_QUIET))
132					gpt_warnx(gpt,
133					    "partition(%ju,%ju) mirrored",
134					    (uintmax_t)start, (uintmax_t)size);
135			}
136		}
137		n->map_type = type;
138		n->map_data = data;
139		n->map_alloc = alloc;
140		return n;
141	}
142
143	if (n->map_type != MAP_TYPE_UNUSED) {
144		if (n->map_type != MAP_TYPE_MBR_PART ||
145		    type != MAP_TYPE_GPT_PART) {
146			gpt_warnx(gpt, "bogus map current=%s new=%s",
147			    map_type(n->map_type), map_type(type));
148			return NULL;
149		}
150		n->map_type = MAP_TYPE_UNUSED;
151	}
152
153	m = map_create(start, size, type);
154	if (m == NULL)
155		goto oomem;
156
157	m->map_data = data;
158	m->map_alloc = alloc;
159
160	if (start == n->map_start) {
161		m->map_prev = n->map_prev;
162		m->map_next = n;
163		if (m->map_prev != NULL)
164			m->map_prev->map_next = m;
165		else
166			gpt->mediamap = m;
167		n->map_prev = m;
168		n->map_start += size;
169		n->map_size -= size;
170	} else if (start + size == n->map_start + n->map_size) {
171		p = n;
172		m->map_next = p->map_next;
173		m->map_prev = p;
174		if (m->map_next != NULL)
175			m->map_next->map_prev = m;
176		p->map_next = m;
177		p->map_size -= size;
178	} else {
179		p = map_create(n->map_start, start - n->map_start, n->map_type);
180		if (p == NULL)
181			goto oomem;
182		n->map_start += p->map_size + m->map_size;
183		n->map_size -= (p->map_size + m->map_size);
184		p->map_prev = n->map_prev;
185		m->map_prev = p;
186		n->map_prev = m;
187		m->map_next = n;
188		p->map_next = m;
189		if (p->map_prev != NULL)
190			p->map_prev->map_next = p;
191		else
192			gpt->mediamap = p;
193	}
194
195	return m;
196oomem:
197	map_destroy(m);
198	gpt_warn(gpt, "Can't create map");
199	return NULL;
200}
201
202map_t
203map_alloc(gpt_t gpt, off_t start, off_t size, off_t alignment)
204{
205	off_t delta;
206	map_t m;
207
208	if (alignment > 0) {
209		if ((start % alignment) != 0)
210			start = (start + alignment) / alignment * alignment;
211		if ((size % alignment) != 0)
212			size = (size + alignment) / alignment * alignment;
213	}
214
215	for (m = gpt->mediamap; m != NULL; m = m->map_next) {
216		if (m->map_type != MAP_TYPE_UNUSED || m->map_start < 2)
217			continue;
218		if (start != 0 && m->map_start > start)
219			return NULL;
220
221		if (start != 0)
222			delta = start - m->map_start;
223		else if (alignment > 0 && m->map_start % alignment != 0)
224			delta = (m->map_start + alignment) /
225			        alignment * alignment - m->map_start;
226		else
227			delta = 0;
228
229                if (size == 0 || m->map_size - delta >= size) {
230			if (m->map_size - delta < alignment)
231				continue;
232			if (size == 0) {
233				if (alignment > 0 &&
234				    (m->map_size - delta) % alignment != 0)
235					size = (m->map_size - delta) /
236					    alignment * alignment;
237				else
238					size = m->map_size - delta;
239			}
240			return map_add(gpt, m->map_start + delta, size,
241			    MAP_TYPE_GPT_PART, NULL, 0);
242		}
243	}
244
245	return NULL;
246}
247
248off_t
249map_resize(gpt_t gpt, map_t m, off_t size, off_t alignment)
250{
251	map_t n, o;
252	off_t alignsize, prevsize;
253
254	n = m->map_next;
255
256	if (size < 0 || alignment < 0) {
257		gpt_warnx(gpt, "negative size or alignment");
258		return -1;
259	}
260	/* Size == 0 means to use whole region of the following unused map */
261	if (size == 0) {
262		if (n == NULL) {
263			// XXX: we could just turn the map to UNUSED!
264			gpt_warnx(gpt, "Can't delete, next map is not found");
265			return -1;
266		}
267		if (n->map_type != MAP_TYPE_UNUSED) {
268			gpt_warnx(gpt, "Can't delete, next map is in use");
269			return -1;
270		}
271		if (alignment == 0) {
272			size = m->map_size + n->map_size;
273			m->map_size = size;
274			m->map_next = n->map_next;
275			if (n->map_next != NULL)
276				n->map_next->map_prev = m;
277			map_destroy(n);
278			return size;
279		} else { /* alignment > 0 */
280			prevsize = m->map_size;
281			size = ((m->map_size + n->map_size) / alignment)
282			    * alignment;
283			if (size == prevsize) {
284				m->map_size = size;
285				return size;
286			} else if (size < prevsize) {
287				gpt_warnx(gpt, "Can't coalesce %ju <= %ju",
288				    (uintmax_t)prevsize, (uintmax_t)size);
289				return -1;
290			}
291			m->map_size = size;
292			n->map_start += size - prevsize;
293			n->map_size -= size - prevsize;
294			if (n->map_size == 0) {
295				m->map_next = n->map_next;
296				if (n->map_next != NULL)
297					n->map_next->map_prev = m;
298				map_destroy(n);
299			}
300			return size;
301		}
302	}
303
304	alignsize = size;
305	if (alignment % size != 0)
306		alignsize = (size + alignment) / alignment * alignment;
307
308	if (alignsize < m->map_size) {		/* shrinking */
309		prevsize = m->map_size;
310		m->map_size = alignsize;
311		if (n == NULL || n->map_type != MAP_TYPE_UNUSED) {
312			o = map_create(m->map_start + alignsize,
313				  prevsize - alignsize, MAP_TYPE_UNUSED);
314			if (o == NULL) {
315				gpt_warn(gpt, "Can't create map");
316				return -1;
317			}
318			m->map_next = o;
319			o->map_prev = m;
320			o->map_next = n;
321			if (n != NULL)
322				n->map_prev = o;
323			return alignsize;
324		} else {
325			n->map_start -= alignsize;
326			n->map_size += alignsize;
327			return alignsize;
328		}
329	} else if (alignsize > m->map_size) {		/* expanding */
330		if (n == NULL) {
331			gpt_warnx(gpt, "Can't expand map, no space after it");
332			return -1;
333		}
334		if (n->map_type != MAP_TYPE_UNUSED) {
335			gpt_warnx(gpt,
336			    "Can't expand map, next map after it in use");
337			return -1;
338		}
339		if (n->map_size < alignsize - m->map_size) {
340			gpt_warnx(gpt,
341			    "Can't expand map, not enough space in the"
342			    " next map after it");
343			return -1;
344		}
345		n->map_size -= alignsize - m->map_size;
346		n->map_start += alignsize - m->map_size;
347		if (n->map_size == 0) {
348			m->map_next = n->map_next;
349			if (n->map_next != NULL)
350				n->map_next->map_prev = m;
351			map_destroy(n);
352		}
353		m->map_size = alignsize;
354		return alignsize;
355	} else						/* correct size */
356		return alignsize;
357}
358
359map_t
360map_find(gpt_t gpt, int type)
361{
362	map_t m;
363
364	m = gpt->mediamap;
365	while (m != NULL && m->map_type != type)
366		m = m->map_next;
367	return m;
368}
369
370map_t
371map_first(gpt_t gpt)
372{
373	return gpt->mediamap;
374}
375
376map_t
377map_last(gpt_t gpt)
378{
379	map_t m;
380
381	m = gpt->mediamap;
382	while (m != NULL && m->map_next != NULL)
383		m = m->map_next;
384	return m;
385}
386
387off_t
388map_free(gpt_t gpt, off_t start, off_t size)
389{
390	map_t m;
391
392	m = gpt->mediamap;
393
394	while (m != NULL && m->map_start + m->map_size <= start)
395		m = m->map_next;
396	if (m == NULL || m->map_type != MAP_TYPE_UNUSED)
397		return 0LL;
398	if (size)
399		return (m->map_start + m->map_size >= start + size) ? 1 : 0;
400	return m->map_size - (start - m->map_start);
401}
402
403int
404map_init(gpt_t gpt, off_t size)
405{
406	char buf[32];
407
408	gpt->mediamap = map_create(0LL, size, MAP_TYPE_UNUSED);
409	if (gpt->mediamap == NULL) {
410		gpt_warn(gpt, "Can't create map");
411		return -1;
412	}
413	gpt->lbawidth = snprintf(buf, sizeof(buf), "%ju", (uintmax_t)size);
414	if (gpt->lbawidth < 5)
415		gpt->lbawidth = 5;
416	return 0;
417}
418