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