Home | History | Annotate | Line # | Download | only in gpt
map.c revision 1.14 
      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