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