xref: /netbsd-src/sbin/gpt/map.c (revision d909946ca08dceb44d7d0f22ec9488679695d976) 
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.13 2015/12/03 21:30:54 christos 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 		return NULL;
122 	}
123 
124 	if (n->map_start == start && n->map_size == size) {
125 		if (n->map_type != MAP_TYPE_UNUSED) {
126 			if (n->map_type != MAP_TYPE_MBR_PART ||
127 			    type != MAP_TYPE_GPT_PART) {
128 				if (!(gpt->flags & GPT_QUIET))
129 					gpt_warnx(gpt,
130 					    "partition(%ju,%ju) mirrored",
131 					    (uintmax_t)start, (uintmax_t)size);
132 			}
133 		}
134 		n->map_type = type;
135 		n->map_data = data;
136 		n->map_alloc = alloc;
137 		return n;
138 	}
139 
140 	if (n->map_type != MAP_TYPE_UNUSED) {
141 		if (n->map_type != MAP_TYPE_MBR_PART ||
142 		    type != MAP_TYPE_GPT_PART) {
143 			gpt_warnx(gpt, "bogus map current=%s new=%s",
144 			    map_type(n->map_type), map_type(type));
145 			return NULL;
146 		}
147 		n->map_type = MAP_TYPE_UNUSED;
148 	}
149 
150 	m = map_create(start, size, type);
151 	if (m == NULL)
152 		goto oomem;
153 
154 	m->map_data = data;
155 	m->map_alloc = alloc;
156 
157 	if (start == n->map_start) {
158 		m->map_prev = n->map_prev;
159 		m->map_next = n;
160 		if (m->map_prev != NULL)
161 			m->map_prev->map_next = m;
162 		else
163 			gpt->mediamap = m;
164 		n->map_prev = m;
165 		n->map_start += size;
166 		n->map_size -= size;
167 	} else if (start + size == n->map_start + n->map_size) {
168 		p = n;
169 		m->map_next = p->map_next;
170 		m->map_prev = p;
171 		if (m->map_next != NULL)
172 			m->map_next->map_prev = m;
173 		p->map_next = m;
174 		p->map_size -= size;
175 	} else {
176 		p = map_create(n->map_start, start - n->map_start, n->map_type);
177 		if (p == NULL)
178 			goto oomem;
179 		n->map_start += p->map_size + m->map_size;
180 		n->map_size -= (p->map_size + m->map_size);
181 		p->map_prev = n->map_prev;
182 		m->map_prev = p;
183 		n->map_prev = m;
184 		m->map_next = n;
185 		p->map_next = m;
186 		if (p->map_prev != NULL)
187 			p->map_prev->map_next = p;
188 		else
189 			gpt->mediamap = p;
190 	}
191 
192 	return m;
193 oomem:
194 	map_destroy(m);
195 	gpt_warn(gpt, "Can't create map");
196 	return NULL;
197 }
198 
199 map_t
200 map_alloc(gpt_t gpt, off_t start, off_t size, off_t alignment)
201 {
202 	off_t delta;
203 	map_t m;
204 
205 	if (alignment > 0) {
206 		if ((start % alignment) != 0)
207 			start = (start + alignment) / alignment * alignment;
208 		if ((size % alignment) != 0)
209 			size = (size + alignment) / alignment * alignment;
210 	}
211 
212 	for (m = gpt->mediamap; m != NULL; m = m->map_next) {
213 		if (m->map_type != MAP_TYPE_UNUSED || m->map_start < 2)
214 			continue;
215 		if (start != 0 && m->map_start > start)
216 			return NULL;
217 
218 		if (start != 0)
219 			delta = start - m->map_start;
220 		else if (alignment > 0 && m->map_start % alignment != 0)
221 			delta = (m->map_start + alignment) /
222 			        alignment * alignment - m->map_start;
223 		else
224 			delta = 0;
225 
226                 if (size == 0 || m->map_size - delta >= size) {
227 			if (m->map_size - delta < alignment)
228 				continue;
229 			if (size == 0) {
230 				if (alignment > 0 &&
231 				    (m->map_size - delta) % alignment != 0)
232 					size = (m->map_size - delta) /
233 					    alignment * alignment;
234 				else
235 					size = m->map_size - delta;
236 			}
237 			return map_add(gpt, m->map_start + delta, size,
238 			    MAP_TYPE_GPT_PART, NULL, 0);
239 		}
240 	}
241 
242 	return NULL;
243 }
244 
245 off_t
246 map_resize(gpt_t gpt, map_t m, off_t size, off_t alignment)
247 {
248 	map_t n, o;
249 	off_t alignsize, prevsize;
250 
251 	n = m->map_next;
252 
253 	if (size < 0 || alignment < 0) {
254 		gpt_warnx(gpt, "negative size or alignment");
255 		return -1;
256 	}
257 	/* Size == 0 means delete, if the next map is unused */
258 	if (size == 0) {
259 		if (n == NULL) {
260 			// XXX: we could just turn the map to UNUSED!
261 			gpt_warnx(gpt, "Can't delete, next map is not found");
262 			return -1;
263 		}
264 		if (n->map_type != MAP_TYPE_UNUSED) {
265 			gpt_warnx(gpt, "Can't delete, next map is in use");
266 			return -1;
267 		}
268 		if (alignment == 0) {
269 			size = m->map_size + n->map_size;
270 			m->map_size = size;
271 			m->map_next = n->map_next;
272 			if (n->map_next != NULL)
273 				n->map_next->map_prev = m;
274 			map_destroy(n);
275 			return size;
276 		} else { /* alignment > 0 */
277 			prevsize = m->map_size;
278 			size = ((m->map_size + n->map_size) / alignment)
279 			    * alignment;
280 			if (size <= prevsize) {
281 				gpt_warnx(gpt, "Can't coalesce %ju <= %ju",
282 				    (uintmax_t)prevsize, (uintmax_t)size);
283 				return -1;
284 			}
285 			m->map_size = size;
286 			n->map_start += size - prevsize;
287 			n->map_size -= size - prevsize;
288 			if (n->map_size == 0) {
289 				m->map_next = n->map_next;
290 				if (n->map_next != NULL)
291 					n->map_next->map_prev = m;
292 				map_destroy(n);
293 			}
294 			return size;
295 		}
296 	}
297 
298 	alignsize = size;
299 	if (alignment % size != 0)
300 		alignsize = (size + alignment) / alignment * alignment;
301 
302 	if (alignsize < m->map_size) {		/* shrinking */
303 		prevsize = m->map_size;
304 		m->map_size = alignsize;
305 		if (n == NULL || n->map_type != MAP_TYPE_UNUSED) {
306 			o = map_create(m->map_start + alignsize,
307 				  prevsize - alignsize, MAP_TYPE_UNUSED);
308 			if (o == NULL) {
309 				gpt_warn(gpt, "Can't create map");
310 				return -1;
311 			}
312 			m->map_next = o;
313 			o->map_prev = m;
314 			o->map_next = n;
315 			if (n != NULL)
316 				n->map_prev = o;
317 			return alignsize;
318 		} else {
319 			n->map_start -= alignsize;
320 			n->map_size += alignsize;
321 			return alignsize;
322 		}
323 	} else if (alignsize > m->map_size) {		/* expanding */
324 		if (n == NULL) {
325 			gpt_warnx(gpt, "Can't expand map, no space after it");
326 			return -1;
327 		}
328 		if (n->map_type != MAP_TYPE_UNUSED) {
329 			gpt_warnx(gpt,
330 			    "Can't expand map, next map after it in use");
331 			return -1;
332 		}
333 		if (n->map_size < alignsize - m->map_size) {
334 			gpt_warnx(gpt,
335 			    "Can't expand map, not enough space in the"
336 			    " next map after it");
337 			return -1;
338 		}
339 		n->map_size -= alignsize - m->map_size;
340 		n->map_start += alignsize - m->map_size;
341 		if (n->map_size == 0) {
342 			m->map_next = n->map_next;
343 			if (n->map_next != NULL)
344 				n->map_next->map_prev = m;
345 			map_destroy(n);
346 		}
347 		m->map_size = alignsize;
348 		return alignsize;
349 	} else						/* correct size */
350 		return alignsize;
351 }
352 
353 map_t
354 map_find(gpt_t gpt, int type)
355 {
356 	map_t m;
357 
358 	m = gpt->mediamap;
359 	while (m != NULL && m->map_type != type)
360 		m = m->map_next;
361 	return m;
362 }
363 
364 map_t
365 map_first(gpt_t gpt)
366 {
367 	return gpt->mediamap;
368 }
369 
370 map_t
371 map_last(gpt_t gpt)
372 {
373 	map_t m;
374 
375 	m = gpt->mediamap;
376 	while (m != NULL && m->map_next != NULL)
377 		m = m->map_next;
378 	return m;
379 }
380 
381 off_t
382 map_free(gpt_t gpt, off_t start, off_t size)
383 {
384 	map_t m;
385 
386 	m = gpt->mediamap;
387 
388 	while (m != NULL && m->map_start + m->map_size <= start)
389 		m = m->map_next;
390 	if (m == NULL || m->map_type != MAP_TYPE_UNUSED)
391 		return 0LL;
392 	if (size)
393 		return (m->map_start + m->map_size >= start + size) ? 1 : 0;
394 	return m->map_size - (start - m->map_start);
395 }
396 
397 int
398 map_init(gpt_t gpt, off_t size)
399 {
400 	char buf[32];
401 
402 	gpt->mediamap = map_create(0LL, size, MAP_TYPE_UNUSED);
403 	if (gpt->mediamap == NULL) {
404 		gpt_warn(gpt, "Can't create map");
405 		return -1;
406 	}
407 	gpt->lbawidth = snprintf(buf, sizeof(buf), "%ju", (uintmax_t)size);
408 	if (gpt->lbawidth < 5)
409 		gpt->lbawidth = 5;
410 	return 0;
411 }
412