Home | History | Annotate | Line # | Download | only in gpt
map.c revision 1.11 
      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.11 2015/12/01 09:05:33 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 mkmap(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 	return (m);
     63 }
     64 
     65 static const char *maptypes[] = {
     66 	"unused",
     67 	"mbr",
     68 	"mbr partition",
     69 	"primary gpt header",
     70 	"secondary gpt header",
     71 	"primary gpt table",
     72 	"secondary gpt table",
     73 	"gpt partition",
     74 	"protective mbr",
     75 };
     76 
     77 static const char *
     78 map_type(int t)
     79 {
     80 	if ((size_t)t >= __arraycount(maptypes))
     81 		return "*unknown*";
     82 	return maptypes[t];
     83 }
     84 
     85 map_t
     86 map_add(gpt_t gpt, off_t start, off_t size, int type, void *data)
     87 {
     88 	map_t m, n, p;
     89 
     90 #ifdef DEBUG
     91 	printf("add: %s %#jx %#jx\n", map_type(type), (uintmax_t)start,
     92 	    (uintmax_t)size);
     93 	for (n = gpt->mediamap; n; n = n->map_next)
     94 		printf("have: %s %#jx %#jx\n", map_type(n->map_type),
     95 		    (uintmax_t)n->map_start, (uintmax_t)n->map_size);
     96 #endif
     97 
     98 	n = gpt->mediamap;
     99 	while (n != NULL && n->map_start + n->map_size <= start)
    100 		n = n->map_next;
    101 	if (n == NULL) {
    102 		if (!(gpt->flags & GPT_QUIET))
    103 			gpt_warnx(gpt, "Can't find map");
    104 		return (NULL);
    105 	}
    106 
    107 	if (n->map_start + n->map_size < start + size) {
    108 		if (!(gpt->flags & GPT_QUIET))
    109 			gpt_warnx(gpt, "map entry doesn't fit media");
    110 		return (NULL);
    111 	}
    112 
    113 	if (n->map_start == start && n->map_size == size) {
    114 		if (n->map_type != MAP_TYPE_UNUSED) {
    115 			if (n->map_type != MAP_TYPE_MBR_PART ||
    116 			    type != MAP_TYPE_GPT_PART) {
    117 				if (!(gpt->flags & GPT_QUIET))
    118 					gpt_warnx(gpt, "partition(%ju,%ju) mirrored",
    119 					    (uintmax_t)start, (uintmax_t)size);
    120 			}
    121 		}
    122 		n->map_type = type;
    123 		n->map_data = data;
    124 		return (n);
    125 	}
    126 
    127 	if (n->map_type != MAP_TYPE_UNUSED) {
    128 		if (n->map_type != MAP_TYPE_MBR_PART ||
    129 		    type != MAP_TYPE_GPT_PART) {
    130 			gpt_warnx(gpt, "bogus map current=%s new=%s",
    131 			    map_type(n->map_type), map_type(type));
    132 			return (NULL);
    133 		}
    134 		n->map_type = MAP_TYPE_UNUSED;
    135 	}
    136 
    137 	m = mkmap(start, size, type);
    138 	if (m == NULL)
    139 		return (NULL);
    140 
    141 	m->map_data = data;
    142 
    143 	if (start == n->map_start) {
    144 		m->map_prev = n->map_prev;
    145 		m->map_next = n;
    146 		if (m->map_prev != NULL)
    147 			m->map_prev->map_next = m;
    148 		else
    149 			gpt->mediamap = m;
    150 		n->map_prev = m;
    151 		n->map_start += size;
    152 		n->map_size -= size;
    153 	} else if (start + size == n->map_start + n->map_size) {
    154 		p = n;
    155 		m->map_next = p->map_next;
    156 		m->map_prev = p;
    157 		if (m->map_next != NULL)
    158 			m->map_next->map_prev = m;
    159 		p->map_next = m;
    160 		p->map_size -= size;
    161 	} else {
    162 		p = mkmap(n->map_start, start - n->map_start, n->map_type);
    163 		n->map_start += p->map_size + m->map_size;
    164 		n->map_size -= (p->map_size + m->map_size);
    165 		p->map_prev = n->map_prev;
    166 		m->map_prev = p;
    167 		n->map_prev = m;
    168 		m->map_next = n;
    169 		p->map_next = m;
    170 		if (p->map_prev != NULL)
    171 			p->map_prev->map_next = p;
    172 		else
    173 			gpt->mediamap = p;
    174 	}
    175 
    176 	return (m);
    177 }
    178 
    179 map_t
    180 map_alloc(gpt_t gpt, off_t start, off_t size, off_t alignment)
    181 {
    182 	off_t delta;
    183 	map_t m;
    184 
    185 	if (alignment > 0) {
    186 		if ((start % alignment) != 0)
    187 			start = (start + alignment) / alignment * alignment;
    188 		if ((size % alignment) != 0)
    189 			size = (size + alignment) / alignment * alignment;
    190 	}
    191 
    192 	for (m = gpt->mediamap; m != NULL; m = m->map_next) {
    193 		if (m->map_type != MAP_TYPE_UNUSED || m->map_start < 2)
    194 			continue;
    195 		if (start != 0 && m->map_start > start)
    196 			return (NULL);
    197 
    198 		if (start != 0)
    199 			delta = start - m->map_start;
    200 		else if (alignment > 0 && m->map_start % alignment != 0)
    201 			delta = (m->map_start + alignment) /
    202 			        alignment * alignment - m->map_start;
    203 		else
    204 			delta = 0;
    205 
    206                 if (size == 0 || m->map_size - delta >= size) {
    207 			if (m->map_size - delta < alignment)
    208 				continue;
    209 			if (size == 0) {
    210 				if (alignment > 0 &&
    211 				    (m->map_size - delta) % alignment != 0)
    212 					size = (m->map_size - delta) /
    213 					    alignment * alignment;
    214 				else
    215 					size = m->map_size - delta;
    216 			}
    217 			return map_add(gpt, m->map_start + delta, size,
    218 				    MAP_TYPE_GPT_PART, NULL);
    219 		}
    220 	}
    221 
    222 	return NULL;
    223 }
    224 
    225 off_t
    226 map_resize(gpt_t gpt, map_t m, off_t size, off_t alignment)
    227 {
    228 	map_t n, o;
    229 	off_t alignsize, prevsize;
    230 
    231 	n = m->map_next;
    232 
    233 	if (size < 0 || alignment < 0) {
    234 		gpt_warnx(gpt, "negative size or alignment");
    235 		return 0;
    236 	}
    237 	if (size == 0 && alignment == 0) {
    238 		if (n == NULL || n->map_type != MAP_TYPE_UNUSED)
    239 			return 0;
    240 		else {
    241 			size = m->map_size + n->map_size;
    242 			m->map_size = size;
    243 			m->map_next = n->map_next;
    244 			if (n->map_next != NULL)
    245 				n->map_next->map_prev = m;
    246 			if (n->map_data != NULL)
    247 				free(n->map_data);
    248 			free(n);
    249 			return size;
    250 		}
    251 	}
    252 
    253 	if (size == 0 && alignment > 0) {
    254 		if (n == NULL || n->map_type != MAP_TYPE_UNUSED)
    255 			return 0;
    256 		else {
    257 			prevsize = m->map_size;
    258 			size = (m->map_size + n->map_size) /
    259 			       alignment * alignment;
    260 			if (size <= prevsize)
    261 				return 0;
    262 			m->map_size = size;
    263 			n->map_start += size - prevsize;
    264 			n->map_size -= size - prevsize;
    265 			if (n->map_size == 0) {
    266 				m->map_next = n->map_next;
    267 				if (n->map_next != NULL)
    268 					n->map_next->map_prev = m;
    269 				if (n->map_data != NULL)
    270 					free(n->map_data);
    271 				free(n);
    272 			}
    273 			return size;
    274 		}
    275 	}
    276 
    277 	alignsize = size;
    278 	if (alignment % size != 0)
    279 		alignsize = (size + alignment) / alignment * alignment;
    280 
    281 	if (alignsize < m->map_size) {		/* shrinking */
    282 		prevsize = m->map_size;
    283 		m->map_size = alignsize;
    284 		if (n == NULL || n->map_type != MAP_TYPE_UNUSED) {
    285 			o = mkmap(m->map_start + alignsize,
    286 				  prevsize - alignsize, MAP_TYPE_UNUSED);
    287 			m->map_next = o;
    288 			o->map_prev = m;
    289 			o->map_next = n;
    290 			if (n != NULL)
    291 				n->map_prev = o;
    292 			return alignsize;
    293 		} else {
    294 			n->map_start -= alignsize;
    295 			n->map_size += alignsize;
    296 			return alignsize;
    297 		}
    298 	} else if (alignsize > m->map_size) {		/* expanding */
    299 		if (n == NULL || n->map_type != MAP_TYPE_UNUSED ||
    300 		    n->map_size < alignsize - m->map_size) {
    301 			return 0;
    302 		}
    303 		n->map_size -= alignsize - m->map_size;
    304 		n->map_start += alignsize - m->map_size;
    305 		if (n->map_size == 0) {
    306 			m->map_next = n->map_next;
    307 			if (n->map_next != NULL)
    308 				n->map_next->map_prev = m;
    309 			if (n->map_data != NULL)
    310 				free(n->map_data);
    311 			free(n);
    312 		}
    313 		m->map_size = alignsize;
    314 		return alignsize;
    315 	} else						/* correct size */
    316 		return alignsize;
    317 }
    318 
    319 map_t
    320 map_find(gpt_t gpt, int type)
    321 {
    322 	map_t m;
    323 
    324 	m = gpt->mediamap;
    325 	while (m != NULL && m->map_type != type)
    326 		m = m->map_next;
    327 	return (m);
    328 }
    329 
    330 map_t
    331 map_first(gpt_t gpt)
    332 {
    333 	return gpt->mediamap;
    334 }
    335 
    336 map_t
    337 map_last(gpt_t gpt)
    338 {
    339 	map_t m;
    340 
    341 	m = gpt->mediamap;
    342 	while (m != NULL && m->map_next != NULL)
    343 		m = m->map_next;
    344 	return (m);
    345 }
    346 
    347 off_t
    348 map_free(gpt_t gpt, off_t start, off_t size)
    349 {
    350 	map_t m;
    351 
    352 	m = gpt->mediamap;
    353 
    354 	while (m != NULL && m->map_start + m->map_size <= start)
    355 		m = m->map_next;
    356 	if (m == NULL || m->map_type != MAP_TYPE_UNUSED)
    357 		return (0LL);
    358 	if (size)
    359 		return ((m->map_start + m->map_size >= start + size) ? 1 : 0);
    360 	return (m->map_size - (start - m->map_start));
    361 }
    362 
    363 void
    364 map_init(gpt_t gpt, off_t size)
    365 {
    366 	char buf[32];
    367 
    368 	gpt->mediamap = mkmap(0LL, size, MAP_TYPE_UNUSED);
    369 	gpt->lbawidth = snprintf(buf, sizeof(buf), "%ju", (uintmax_t)size);
    370 	if (gpt->lbawidth < 5)
    371 		gpt->lbawidth = 5;
    372 }
    373