xref: /netbsd-src/sbin/gpt/map.c (revision bdc22b2e01993381dcefeff2bc9b56ca75a4235c) 
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.14 2018/04/11 07:14:23 mrg 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 
48 static map_t
49 map_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 
66 static void
67 map_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 
76 static 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 
88 static const char *
89 map_type(int t)
90 {
91 	if ((size_t)t >= __arraycount(maptypes))
92 		return "*unknown*";
93 	return maptypes[t];
94 }
95 
96 map_t
97 map_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;
196 oomem:
197 	map_destroy(m);
198 	gpt_warn(gpt, "Can't create map");
199 	return NULL;
200 }
201 
202 map_t
203 map_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 
248 off_t
249 map_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 delete, if the next map is unused */
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 				gpt_warnx(gpt, "Can't coalesce %ju <= %ju",
285 				    (uintmax_t)prevsize, (uintmax_t)size);
286 				return -1;
287 			}
288 			m->map_size = size;
289 			n->map_start += size - prevsize;
290 			n->map_size -= size - prevsize;
291 			if (n->map_size == 0) {
292 				m->map_next = n->map_next;
293 				if (n->map_next != NULL)
294 					n->map_next->map_prev = m;
295 				map_destroy(n);
296 			}
297 			return size;
298 		}
299 	}
300 
301 	alignsize = size;
302 	if (alignment % size != 0)
303 		alignsize = (size + alignment) / alignment * alignment;
304 
305 	if (alignsize < m->map_size) {		/* shrinking */
306 		prevsize = m->map_size;
307 		m->map_size = alignsize;
308 		if (n == NULL || n->map_type != MAP_TYPE_UNUSED) {
309 			o = map_create(m->map_start + alignsize,
310 				  prevsize - alignsize, MAP_TYPE_UNUSED);
311 			if (o == NULL) {
312 				gpt_warn(gpt, "Can't create map");
313 				return -1;
314 			}
315 			m->map_next = o;
316 			o->map_prev = m;
317 			o->map_next = n;
318 			if (n != NULL)
319 				n->map_prev = o;
320 			return alignsize;
321 		} else {
322 			n->map_start -= alignsize;
323 			n->map_size += alignsize;
324 			return alignsize;
325 		}
326 	} else if (alignsize > m->map_size) {		/* expanding */
327 		if (n == NULL) {
328 			gpt_warnx(gpt, "Can't expand map, no space after it");
329 			return -1;
330 		}
331 		if (n->map_type != MAP_TYPE_UNUSED) {
332 			gpt_warnx(gpt,
333 			    "Can't expand map, next map after it in use");
334 			return -1;
335 		}
336 		if (n->map_size < alignsize - m->map_size) {
337 			gpt_warnx(gpt,
338 			    "Can't expand map, not enough space in the"
339 			    " next map after it");
340 			return -1;
341 		}
342 		n->map_size -= alignsize - m->map_size;
343 		n->map_start += alignsize - m->map_size;
344 		if (n->map_size == 0) {
345 			m->map_next = n->map_next;
346 			if (n->map_next != NULL)
347 				n->map_next->map_prev = m;
348 			map_destroy(n);
349 		}
350 		m->map_size = alignsize;
351 		return alignsize;
352 	} else						/* correct size */
353 		return alignsize;
354 }
355 
356 map_t
357 map_find(gpt_t gpt, int type)
358 {
359 	map_t m;
360 
361 	m = gpt->mediamap;
362 	while (m != NULL && m->map_type != type)
363 		m = m->map_next;
364 	return m;
365 }
366 
367 map_t
368 map_first(gpt_t gpt)
369 {
370 	return gpt->mediamap;
371 }
372 
373 map_t
374 map_last(gpt_t gpt)
375 {
376 	map_t m;
377 
378 	m = gpt->mediamap;
379 	while (m != NULL && m->map_next != NULL)
380 		m = m->map_next;
381 	return m;
382 }
383 
384 off_t
385 map_free(gpt_t gpt, off_t start, off_t size)
386 {
387 	map_t m;
388 
389 	m = gpt->mediamap;
390 
391 	while (m != NULL && m->map_start + m->map_size <= start)
392 		m = m->map_next;
393 	if (m == NULL || m->map_type != MAP_TYPE_UNUSED)
394 		return 0LL;
395 	if (size)
396 		return (m->map_start + m->map_size >= start + size) ? 1 : 0;
397 	return m->map_size - (start - m->map_start);
398 }
399 
400 int
401 map_init(gpt_t gpt, off_t size)
402 {
403 	char buf[32];
404 
405 	gpt->mediamap = map_create(0LL, size, MAP_TYPE_UNUSED);
406 	if (gpt->mediamap == NULL) {
407 		gpt_warn(gpt, "Can't create map");
408 		return -1;
409 	}
410 	gpt->lbawidth = snprintf(buf, sizeof(buf), "%ju", (uintmax_t)size);
411 	if (gpt->lbawidth < 5)
412 		gpt->lbawidth = 5;
413 	return 0;
414 }
415