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