Home | History | Annotate | Line # | Download | only in gpt 
      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
     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 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
    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
    371 map_first(gpt_t gpt)
    372 {
    373 	return gpt->mediamap;
    374 }
    375 
    376 map_t
    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
    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
    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