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.2 2006/10/15 22:36:29 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: bogus map"); 76 return (0); 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) 145 { 146 off_t delta; 147 map_t *m; 148 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 : 0; 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 return (map_add(m->map_start + delta, size, 161 MAP_TYPE_GPT_PART, NULL)); 162 } 163 } 164 165 return (NULL); 166 } 167 168 map_t * 169 map_find(int type) 170 { 171 map_t *m; 172 173 m = mediamap; 174 while (m != NULL && m->map_type != type) 175 m = m->map_next; 176 return (m); 177 } 178 179 map_t * 180 map_first(void) 181 { 182 return mediamap; 183 } 184 185 map_t * 186 map_last(void) 187 { 188 map_t *m; 189 190 m = mediamap; 191 while (m != NULL && m->map_next != NULL) 192 m = m->map_next; 193 return (m); 194 } 195 196 off_t 197 map_free(off_t start, off_t size) 198 { 199 map_t *m; 200 201 m = mediamap; 202 203 while (m != NULL && m->map_start + m->map_size <= start) 204 m = m->map_next; 205 if (m == NULL || m->map_type != MAP_TYPE_UNUSED) 206 return (0LL); 207 if (size) 208 return ((m->map_start + m->map_size >= start + size) ? 1 : 0); 209 return (m->map_size - (start - m->map_start)); 210 } 211 212 void 213 map_init(off_t size) 214 { 215 char buf[32]; 216 217 mediamap = mkmap(0LL, size, MAP_TYPE_UNUSED); 218 lbawidth = sprintf(buf, "%llu", (long long)size); 219 if (lbawidth < 5) 220 lbawidth = 5; 221 } 222