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.16 2023/12/05 17:23:19 tsutsui 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 48static map_t 49map_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 66static void 67map_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 76static 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 88static const char * 89map_type(int t) 90{ 91 if ((size_t)t >= __arraycount(maptypes)) 92 return "*unknown*"; 93 return maptypes[t]; 94} 95 96map_t 97map_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; 196oomem: 197 map_destroy(m); 198 gpt_warn(gpt, "Can't create map"); 199 return NULL; 200} 201 202map_t 203map_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 248off_t 249map_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 to use whole region of the following unused map */ 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 m->map_size = size; 285 return size; 286 } else if (size < prevsize) { 287 gpt_warnx(gpt, "Can't coalesce %ju <= %ju", 288 (uintmax_t)prevsize, (uintmax_t)size); 289 return -1; 290 } 291 m->map_size = size; 292 n->map_start += size - prevsize; 293 n->map_size -= size - prevsize; 294 if (n->map_size == 0) { 295 m->map_next = n->map_next; 296 if (n->map_next != NULL) 297 n->map_next->map_prev = m; 298 map_destroy(n); 299 } 300 return size; 301 } 302 } 303 304 alignsize = size; 305 if (alignment % size != 0) 306 alignsize = (size + alignment) / alignment * alignment; 307 308 if (alignsize < m->map_size) { /* shrinking */ 309 prevsize = m->map_size; 310 m->map_size = alignsize; 311 if (n == NULL || n->map_type != MAP_TYPE_UNUSED) { 312 o = map_create(m->map_start + alignsize, 313 prevsize - alignsize, MAP_TYPE_UNUSED); 314 if (o == NULL) { 315 gpt_warn(gpt, "Can't create map"); 316 return -1; 317 } 318 m->map_next = o; 319 o->map_prev = m; 320 o->map_next = n; 321 if (n != NULL) 322 n->map_prev = o; 323 return alignsize; 324 } else { 325 n->map_start -= alignsize; 326 n->map_size += alignsize; 327 return alignsize; 328 } 329 } else if (alignsize > m->map_size) { /* expanding */ 330 if (n == NULL) { 331 gpt_warnx(gpt, "Can't expand map, no space after it"); 332 return -1; 333 } 334 if (n->map_type != MAP_TYPE_UNUSED) { 335 gpt_warnx(gpt, 336 "Can't expand map, next map after it in use"); 337 return -1; 338 } 339 if (n->map_size < alignsize - m->map_size) { 340 gpt_warnx(gpt, 341 "Can't expand map, not enough space in the" 342 " next map after it"); 343 return -1; 344 } 345 n->map_size -= alignsize - m->map_size; 346 n->map_start += alignsize - m->map_size; 347 if (n->map_size == 0) { 348 m->map_next = n->map_next; 349 if (n->map_next != NULL) 350 n->map_next->map_prev = m; 351 map_destroy(n); 352 } 353 m->map_size = alignsize; 354 return alignsize; 355 } else /* correct size */ 356 return alignsize; 357} 358 359map_t 360map_find(gpt_t gpt, int type) 361{ 362 map_t m; 363 364 m = gpt->mediamap; 365 while (m != NULL && m->map_type != type) 366 m = m->map_next; 367 return m; 368} 369 370map_t 371map_first(gpt_t gpt) 372{ 373 return gpt->mediamap; 374} 375 376map_t 377map_last(gpt_t gpt) 378{ 379 map_t m; 380 381 m = gpt->mediamap; 382 while (m != NULL && m->map_next != NULL) 383 m = m->map_next; 384 return m; 385} 386 387off_t 388map_free(gpt_t gpt, off_t start, off_t size) 389{ 390 map_t m; 391 392 m = gpt->mediamap; 393 394 while (m != NULL && m->map_start + m->map_size <= start) 395 m = m->map_next; 396 if (m == NULL || m->map_type != MAP_TYPE_UNUSED) 397 return 0LL; 398 if (size) 399 return (m->map_start + m->map_size >= start + size) ? 1 : 0; 400 return m->map_size - (start - m->map_start); 401} 402 403int 404map_init(gpt_t gpt, off_t size) 405{ 406 char buf[32]; 407 408 gpt->mediamap = map_create(0LL, size, MAP_TYPE_UNUSED); 409 if (gpt->mediamap == NULL) { 410 gpt_warn(gpt, "Can't create map"); 411 return -1; 412 } 413 gpt->lbawidth = snprintf(buf, sizeof(buf), "%ju", (uintmax_t)size); 414 if (gpt->lbawidth < 5) 415 gpt->lbawidth = 5; 416 return 0; 417} 418