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
48 static map_t
map_create(off_t start,off_t size,int type)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
map_destroy(map_t m)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 *
map_type(int t)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
map_add(gpt_t gpt,off_t start,off_t size,int type,void * data,int alloc)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
map_alloc(gpt_t gpt,off_t start,off_t size,off_t alignment)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
map_resize(gpt_t gpt,map_t m,off_t size,off_t alignment)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 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
359 map_t
map_find(gpt_t gpt,int type)360 map_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
370 map_t
map_first(gpt_t gpt)371 map_first(gpt_t gpt)
372 {
373 return gpt->mediamap;
374 }
375
376 map_t
map_last(gpt_t gpt)377 map_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
387 off_t
map_free(gpt_t gpt,off_t start,off_t size)388 map_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
403 int
map_init(gpt_t gpt,off_t size)404 map_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