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