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 * $FreeBSD: src/sbin/gpt/map.c,v 1.6 2005/08/31 01:47:19 marcel Exp $ 27 * $DragonFly: src/sbin/gpt/map.c,v 1.2 2007/06/17 08:34:59 dillon Exp $ 28 */ 29 30 #include <sys/types.h> 31 #include <err.h> 32 #include <stdio.h> 33 #include <stdlib.h> 34 35 #include "map.h" 36 37 #define ROUNDTO 2048 // must be a power of two 38 #define ROUNDDOWN(x) ((x-1) & ~(ROUNDTO-1)) 39 #define ROUNDUP(x) (ROUNDDOWN(x) + ROUNDTO) 40 41 int lbawidth; 42 43 static map_t *mediamap; 44 45 static map_t * 46 mkmap(off_t start, off_t size, int type) 47 { 48 map_t *m; 49 50 m = malloc(sizeof(*m)); 51 if (m == NULL) 52 return (NULL); 53 m->map_start = start; 54 m->map_size = size; 55 m->map_next = m->map_prev = NULL; 56 m->map_type = type; 57 m->map_index = NOENTRY; 58 m->map_data = NULL; 59 return (m); 60 } 61 62 map_t * 63 map_add(off_t start, off_t size, int type, void *data) 64 { 65 map_t *m, *n, *p; 66 67 n = mediamap; 68 while (n != NULL && n->map_start + n->map_size <= start) 69 n = n->map_next; 70 if (n == NULL) 71 return (NULL); 72 73 if (n->map_start + n->map_size < start + size) { 74 warnx("error: bogus map"); 75 return (0); 76 } 77 78 if (n->map_start == start && n->map_size == size) { 79 if (n->map_type != MAP_TYPE_UNUSED) { 80 if (n->map_type != MAP_TYPE_MBR_PART || 81 type != MAP_TYPE_GPT_PART) { 82 warnx("warning: partition(%llu,%llu) mirrored", 83 (long long)start, (long long)size); 84 } 85 } 86 n->map_type = type; 87 n->map_data = data; 88 return (n); 89 } 90 91 if (n->map_type != MAP_TYPE_UNUSED) { 92 if (n->map_type != MAP_TYPE_MBR_PART || 93 type != MAP_TYPE_GPT_PART) { 94 warnx("error: bogus map"); 95 return (0); 96 } 97 n->map_type = MAP_TYPE_UNUSED; 98 } 99 100 m = mkmap(start, size, type); 101 if (m == NULL) 102 return (NULL); 103 104 m->map_data = data; 105 106 if (start == n->map_start) { 107 m->map_prev = n->map_prev; 108 m->map_next = n; 109 if (m->map_prev != NULL) 110 m->map_prev->map_next = m; 111 else 112 mediamap = m; 113 n->map_prev = m; 114 n->map_start += size; 115 n->map_size -= size; 116 } else if (start + size == n->map_start + n->map_size) { 117 p = n; 118 m->map_next = p->map_next; 119 m->map_prev = p; 120 if (m->map_next != NULL) 121 m->map_next->map_prev = m; 122 p->map_next = m; 123 p->map_size -= size; 124 } else { 125 p = mkmap(n->map_start, start - n->map_start, n->map_type); 126 n->map_start += p->map_size + m->map_size; 127 n->map_size -= (p->map_size + m->map_size); 128 p->map_prev = n->map_prev; 129 m->map_prev = p; 130 n->map_prev = m; 131 m->map_next = n; 132 p->map_next = m; 133 if (p->map_prev != NULL) 134 p->map_prev->map_next = p; 135 else 136 mediamap = p; 137 } 138 139 return (m); 140 } 141 142 map_t * 143 map_alloc(off_t start, off_t size) 144 { 145 off_t delta; 146 map_t *m; 147 148 if (start == 0 && size != 0) 149 size = ROUNDUP(size); 150 for (m = mediamap; m != NULL; m = m->map_next) { 151 if (m->map_type != MAP_TYPE_UNUSED || m->map_start < 2) 152 continue; 153 if (start != 0 && m->map_start > start) 154 return (NULL); 155 delta = (start != 0) ? start - m->map_start : ROUNDUP(m->map_start) - m->map_start; 156 if (size == 0 || m->map_size - delta >= size) { 157 if (m->map_size - delta <= 0) 158 continue; 159 if (size == 0) { 160 size = m->map_size - delta; 161 if (start == 0) 162 size = ROUNDDOWN(size); 163 } 164 return (map_add(m->map_start + delta, size, 165 MAP_TYPE_GPT_PART, NULL)); 166 } 167 } 168 169 return (NULL); 170 } 171 172 map_t * 173 map_find(int type) 174 { 175 map_t *m; 176 177 m = mediamap; 178 while (m != NULL && m->map_type != type) 179 m = m->map_next; 180 return (m); 181 } 182 183 map_t * 184 map_first(void) 185 { 186 return mediamap; 187 } 188 189 map_t * 190 map_last(void) 191 { 192 map_t *m; 193 194 m = mediamap; 195 while (m != NULL && m->map_next != NULL) 196 m = m->map_next; 197 return (m); 198 } 199 200 off_t 201 map_free(off_t start, off_t size) 202 { 203 map_t *m; 204 205 m = mediamap; 206 207 while (m != NULL && m->map_start + m->map_size <= start) 208 m = m->map_next; 209 if (m == NULL || m->map_type != MAP_TYPE_UNUSED) 210 return (0LL); 211 if (size) 212 return ((m->map_start + m->map_size >= start + size) ? 1 : 0); 213 return (m->map_size - (start - m->map_start)); 214 } 215 216 void 217 map_init(off_t size) 218 { 219 char buf[32]; 220 221 mediamap = mkmap(0LL, size, MAP_TYPE_UNUSED); 222 lbawidth = sprintf(buf, "%llu", (long long)size); 223 if (lbawidth < 5) 224 lbawidth = 5; 225 } 226