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 *
mkmap(off_t start,off_t size,int type)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 *
map_add(off_t start,off_t size,int type,void * data)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 *
map_alloc(off_t start,off_t size)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 *
map_find(int type)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 *
map_first(void)183 map_first(void)
184 {
185 return mediamap;
186 }
187
188 map_t *
map_last(void)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
map_free(off_t start,off_t size)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
map_init(off_t size)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