789
|
1 |
/*
|
|
2 |
* CDDL HEADER START
|
|
3 |
*
|
|
4 |
* The contents of this file are subject to the terms of the
|
1544
|
5 |
* Common Development and Distribution License (the "License").
|
|
6 |
* You may not use this file except in compliance with the License.
|
789
|
7 |
*
|
|
8 |
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
|
|
9 |
* or http://www.opensolaris.org/os/licensing.
|
|
10 |
* See the License for the specific language governing permissions
|
|
11 |
* and limitations under the License.
|
|
12 |
*
|
|
13 |
* When distributing Covered Code, include this CDDL HEADER in each
|
|
14 |
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
|
|
15 |
* If applicable, add the following below this CDDL HEADER, with the
|
|
16 |
* fields enclosed by brackets "[]" replaced with your own identifying
|
|
17 |
* information: Portions Copyright [yyyy] [name of copyright owner]
|
|
18 |
*
|
|
19 |
* CDDL HEADER END
|
|
20 |
*/
|
|
21 |
/*
|
1544
|
22 |
* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
|
789
|
23 |
* Use is subject to license terms.
|
|
24 |
*/
|
|
25 |
|
|
26 |
#pragma ident "%Z%%M% %I% %E% SMI"
|
|
27 |
|
|
28 |
#include <sys/zfs_context.h>
|
|
29 |
#include <sys/spa.h>
|
|
30 |
#include <sys/dmu.h>
|
|
31 |
#include <sys/space_map.h>
|
|
32 |
|
|
33 |
/*
|
|
34 |
* Space map routines.
|
|
35 |
* NOTE: caller is responsible for all locking.
|
|
36 |
*/
|
|
37 |
static int
|
|
38 |
space_map_seg_compare(const void *x1, const void *x2)
|
|
39 |
{
|
|
40 |
const space_seg_t *s1 = x1;
|
|
41 |
const space_seg_t *s2 = x2;
|
|
42 |
|
|
43 |
if (s1->ss_start < s2->ss_start) {
|
|
44 |
if (s1->ss_end > s2->ss_start)
|
|
45 |
return (0);
|
|
46 |
return (-1);
|
|
47 |
}
|
|
48 |
if (s1->ss_start > s2->ss_start) {
|
|
49 |
if (s1->ss_start < s2->ss_end)
|
|
50 |
return (0);
|
|
51 |
return (1);
|
|
52 |
}
|
|
53 |
return (0);
|
|
54 |
}
|
|
55 |
|
|
56 |
void
|
|
57 |
space_map_create(space_map_t *sm, uint64_t start, uint64_t size, uint64_t shift,
|
|
58 |
kmutex_t *lp)
|
|
59 |
{
|
|
60 |
avl_create(&sm->sm_root, space_map_seg_compare,
|
|
61 |
sizeof (space_seg_t), offsetof(struct space_seg, ss_node));
|
|
62 |
sm->sm_start = start;
|
|
63 |
sm->sm_end = start + size;
|
|
64 |
sm->sm_size = size;
|
|
65 |
sm->sm_shift = shift;
|
|
66 |
sm->sm_space = 0;
|
|
67 |
sm->sm_lock = lp;
|
|
68 |
}
|
|
69 |
|
|
70 |
void
|
|
71 |
space_map_destroy(space_map_t *sm)
|
|
72 |
{
|
|
73 |
VERIFY3U(sm->sm_space, ==, 0);
|
|
74 |
avl_destroy(&sm->sm_root);
|
|
75 |
}
|
|
76 |
|
|
77 |
void
|
|
78 |
space_map_add(space_map_t *sm, uint64_t start, uint64_t size)
|
|
79 |
{
|
|
80 |
avl_index_t where;
|
|
81 |
space_seg_t ssearch, *ss_before, *ss_after, *ss;
|
|
82 |
uint64_t end = start + size;
|
|
83 |
int merge_before, merge_after;
|
|
84 |
|
|
85 |
ASSERT(MUTEX_HELD(sm->sm_lock));
|
|
86 |
VERIFY(size != 0);
|
|
87 |
VERIFY3U(start, >=, sm->sm_start);
|
|
88 |
VERIFY3U(end, <=, sm->sm_end);
|
|
89 |
VERIFY(sm->sm_space + size <= sm->sm_size);
|
|
90 |
VERIFY(P2PHASE(start, 1ULL << sm->sm_shift) == 0);
|
|
91 |
VERIFY(P2PHASE(size, 1ULL << sm->sm_shift) == 0);
|
|
92 |
|
|
93 |
ssearch.ss_start = start;
|
|
94 |
ssearch.ss_end = end;
|
|
95 |
ss = avl_find(&sm->sm_root, &ssearch, &where);
|
|
96 |
|
|
97 |
/* Make sure we don't overlap with either of our neighbors */
|
|
98 |
VERIFY(ss == NULL);
|
|
99 |
|
|
100 |
ss_before = avl_nearest(&sm->sm_root, where, AVL_BEFORE);
|
|
101 |
ss_after = avl_nearest(&sm->sm_root, where, AVL_AFTER);
|
|
102 |
|
|
103 |
merge_before = (ss_before != NULL && ss_before->ss_end == start);
|
|
104 |
merge_after = (ss_after != NULL && ss_after->ss_start == end);
|
|
105 |
|
|
106 |
if (merge_before && merge_after) {
|
|
107 |
avl_remove(&sm->sm_root, ss_before);
|
|
108 |
ss_after->ss_start = ss_before->ss_start;
|
|
109 |
kmem_free(ss_before, sizeof (*ss_before));
|
|
110 |
} else if (merge_before) {
|
|
111 |
ss_before->ss_end = end;
|
|
112 |
} else if (merge_after) {
|
|
113 |
ss_after->ss_start = start;
|
|
114 |
} else {
|
|
115 |
ss = kmem_alloc(sizeof (*ss), KM_SLEEP);
|
|
116 |
ss->ss_start = start;
|
|
117 |
ss->ss_end = end;
|
|
118 |
avl_insert(&sm->sm_root, ss, where);
|
|
119 |
}
|
|
120 |
|
|
121 |
sm->sm_space += size;
|
|
122 |
}
|
|
123 |
|
|
124 |
void
|
|
125 |
space_map_remove(space_map_t *sm, uint64_t start, uint64_t size)
|
|
126 |
{
|
|
127 |
avl_index_t where;
|
|
128 |
space_seg_t ssearch, *ss, *newseg;
|
|
129 |
uint64_t end = start + size;
|
|
130 |
int left_over, right_over;
|
|
131 |
|
|
132 |
ASSERT(MUTEX_HELD(sm->sm_lock));
|
|
133 |
VERIFY(size != 0);
|
|
134 |
VERIFY(P2PHASE(start, 1ULL << sm->sm_shift) == 0);
|
|
135 |
VERIFY(P2PHASE(size, 1ULL << sm->sm_shift) == 0);
|
|
136 |
|
|
137 |
ssearch.ss_start = start;
|
|
138 |
ssearch.ss_end = end;
|
|
139 |
ss = avl_find(&sm->sm_root, &ssearch, &where);
|
|
140 |
|
|
141 |
/* Make sure we completely overlap with someone */
|
|
142 |
VERIFY(ss != NULL);
|
|
143 |
VERIFY3U(ss->ss_start, <=, start);
|
|
144 |
VERIFY3U(ss->ss_end, >=, end);
|
|
145 |
VERIFY(sm->sm_space - size <= sm->sm_size);
|
|
146 |
|
|
147 |
left_over = (ss->ss_start != start);
|
|
148 |
right_over = (ss->ss_end != end);
|
|
149 |
|
|
150 |
if (left_over && right_over) {
|
|
151 |
newseg = kmem_alloc(sizeof (*newseg), KM_SLEEP);
|
|
152 |
newseg->ss_start = end;
|
|
153 |
newseg->ss_end = ss->ss_end;
|
|
154 |
ss->ss_end = start;
|
|
155 |
avl_insert_here(&sm->sm_root, newseg, ss, AVL_AFTER);
|
|
156 |
} else if (left_over) {
|
|
157 |
ss->ss_end = start;
|
|
158 |
} else if (right_over) {
|
|
159 |
ss->ss_start = end;
|
|
160 |
} else {
|
|
161 |
avl_remove(&sm->sm_root, ss);
|
|
162 |
kmem_free(ss, sizeof (*ss));
|
|
163 |
}
|
|
164 |
|
|
165 |
sm->sm_space -= size;
|
|
166 |
}
|
|
167 |
|
|
168 |
int
|
|
169 |
space_map_contains(space_map_t *sm, uint64_t start, uint64_t size)
|
|
170 |
{
|
|
171 |
avl_index_t where;
|
|
172 |
space_seg_t ssearch, *ss;
|
|
173 |
uint64_t end = start + size;
|
|
174 |
|
|
175 |
ASSERT(MUTEX_HELD(sm->sm_lock));
|
|
176 |
VERIFY(size != 0);
|
|
177 |
VERIFY(P2PHASE(start, 1ULL << sm->sm_shift) == 0);
|
|
178 |
VERIFY(P2PHASE(size, 1ULL << sm->sm_shift) == 0);
|
|
179 |
|
|
180 |
ssearch.ss_start = start;
|
|
181 |
ssearch.ss_end = end;
|
|
182 |
ss = avl_find(&sm->sm_root, &ssearch, &where);
|
|
183 |
|
|
184 |
return (ss != NULL && ss->ss_start <= start && ss->ss_end >= end);
|
|
185 |
}
|
|
186 |
|
|
187 |
void
|
|
188 |
space_map_vacate(space_map_t *sm, space_map_func_t *func, space_map_t *mdest)
|
|
189 |
{
|
|
190 |
space_seg_t *ss;
|
|
191 |
void *cookie = NULL;
|
|
192 |
|
|
193 |
ASSERT(MUTEX_HELD(sm->sm_lock));
|
|
194 |
|
|
195 |
while ((ss = avl_destroy_nodes(&sm->sm_root, &cookie)) != NULL) {
|
|
196 |
if (func != NULL)
|
|
197 |
func(mdest, ss->ss_start, ss->ss_end - ss->ss_start);
|
|
198 |
kmem_free(ss, sizeof (*ss));
|
|
199 |
}
|
|
200 |
sm->sm_space = 0;
|
|
201 |
}
|
|
202 |
|
|
203 |
void
|
|
204 |
space_map_iterate(space_map_t *sm, space_map_func_t *func, space_map_t *mdest)
|
|
205 |
{
|
|
206 |
space_seg_t *ss;
|
|
207 |
|
|
208 |
for (ss = avl_first(&sm->sm_root); ss; ss = AVL_NEXT(&sm->sm_root, ss))
|
|
209 |
func(mdest, ss->ss_start, ss->ss_end - ss->ss_start);
|
|
210 |
}
|
|
211 |
|
|
212 |
void
|
|
213 |
space_map_merge(space_map_t *src, space_map_t *dest)
|
|
214 |
{
|
|
215 |
space_map_vacate(src, space_map_add, dest);
|
|
216 |
}
|
|
217 |
|
|
218 |
void
|
|
219 |
space_map_excise(space_map_t *sm, uint64_t start, uint64_t size)
|
|
220 |
{
|
|
221 |
avl_tree_t *t = &sm->sm_root;
|
|
222 |
avl_index_t where;
|
|
223 |
space_seg_t *ss, search;
|
|
224 |
uint64_t end = start + size;
|
|
225 |
uint64_t rm_start, rm_end;
|
|
226 |
|
|
227 |
ASSERT(MUTEX_HELD(sm->sm_lock));
|
|
228 |
|
|
229 |
search.ss_start = start;
|
|
230 |
search.ss_end = start;
|
|
231 |
|
|
232 |
for (;;) {
|
|
233 |
ss = avl_find(t, &search, &where);
|
|
234 |
|
|
235 |
if (ss == NULL)
|
|
236 |
ss = avl_nearest(t, where, AVL_AFTER);
|
|
237 |
|
|
238 |
if (ss == NULL || ss->ss_start >= end)
|
|
239 |
break;
|
|
240 |
|
|
241 |
rm_start = MAX(ss->ss_start, start);
|
|
242 |
rm_end = MIN(ss->ss_end, end);
|
|
243 |
|
|
244 |
space_map_remove(sm, rm_start, rm_end - rm_start);
|
|
245 |
}
|
|
246 |
}
|
|
247 |
|
|
248 |
/*
|
|
249 |
* Replace smd with the union of smd and sms.
|
|
250 |
*/
|
|
251 |
void
|
|
252 |
space_map_union(space_map_t *smd, space_map_t *sms)
|
|
253 |
{
|
|
254 |
avl_tree_t *t = &sms->sm_root;
|
|
255 |
space_seg_t *ss;
|
|
256 |
|
|
257 |
ASSERT(MUTEX_HELD(smd->sm_lock));
|
|
258 |
|
|
259 |
/*
|
|
260 |
* For each source segment, remove any intersections with the
|
|
261 |
* destination, then add the source segment to the destination.
|
|
262 |
*/
|
|
263 |
for (ss = avl_first(t); ss != NULL; ss = AVL_NEXT(t, ss)) {
|
|
264 |
space_map_excise(smd, ss->ss_start, ss->ss_end - ss->ss_start);
|
|
265 |
space_map_add(smd, ss->ss_start, ss->ss_end - ss->ss_start);
|
|
266 |
}
|
|
267 |
}
|
|
268 |
|
|
269 |
int
|
|
270 |
space_map_load(space_map_t *sm, space_map_obj_t *smo, uint8_t maptype,
|
|
271 |
objset_t *os, uint64_t end, uint64_t space)
|
|
272 |
{
|
|
273 |
uint64_t *entry, *entry_map, *entry_map_end;
|
|
274 |
uint64_t bufsize, size, offset;
|
|
275 |
uint64_t mapstart = sm->sm_start;
|
|
276 |
|
|
277 |
ASSERT(MUTEX_HELD(sm->sm_lock));
|
|
278 |
VERIFY3U(sm->sm_space, ==, 0);
|
|
279 |
|
|
280 |
bufsize = MIN(end, SPACE_MAP_CHUNKSIZE);
|
|
281 |
entry_map = kmem_alloc(bufsize, KM_SLEEP);
|
|
282 |
|
|
283 |
if (maptype == SM_FREE) {
|
|
284 |
space_map_add(sm, sm->sm_start, sm->sm_size);
|
|
285 |
space = sm->sm_size - space;
|
|
286 |
}
|
|
287 |
|
|
288 |
for (offset = 0; offset < end; offset += bufsize) {
|
|
289 |
size = MIN(end - offset, bufsize);
|
|
290 |
VERIFY(P2PHASE(size, sizeof (uint64_t)) == 0);
|
|
291 |
VERIFY(size != 0);
|
|
292 |
|
|
293 |
dprintf("object=%llu offset=%llx size=%llx\n",
|
|
294 |
smo->smo_object, offset, size);
|
1544
|
295 |
VERIFY(0 == dmu_read(os, smo->smo_object, offset, size,
|
|
296 |
entry_map));
|
789
|
297 |
|
|
298 |
entry_map_end = entry_map + (size / sizeof (uint64_t));
|
|
299 |
for (entry = entry_map; entry < entry_map_end; entry++) {
|
|
300 |
uint64_t e = *entry;
|
|
301 |
|
|
302 |
if (SM_DEBUG_DECODE(e)) /* Skip debug entries */
|
|
303 |
continue;
|
|
304 |
|
|
305 |
(SM_TYPE_DECODE(e) == maptype ?
|
|
306 |
space_map_add : space_map_remove)(sm,
|
|
307 |
(SM_OFFSET_DECODE(e) << sm->sm_shift) + mapstart,
|
|
308 |
SM_RUN_DECODE(e) << sm->sm_shift);
|
|
309 |
}
|
|
310 |
}
|
|
311 |
VERIFY3U(sm->sm_space, ==, space);
|
|
312 |
|
|
313 |
kmem_free(entry_map, bufsize);
|
|
314 |
|
|
315 |
return (0);
|
|
316 |
}
|
|
317 |
|
|
318 |
void
|
|
319 |
space_map_sync(space_map_t *sm, space_map_t *dest, space_map_obj_t *smo,
|
|
320 |
uint8_t maptype, objset_t *os, dmu_tx_t *tx)
|
|
321 |
{
|
|
322 |
spa_t *spa = dmu_objset_spa(os);
|
|
323 |
void *cookie = NULL;
|
|
324 |
space_seg_t *ss;
|
|
325 |
uint64_t bufsize, start, size, run_len;
|
|
326 |
uint64_t *entry, *entry_map, *entry_map_end;
|
|
327 |
|
|
328 |
ASSERT(MUTEX_HELD(sm->sm_lock));
|
|
329 |
|
|
330 |
if (sm->sm_space == 0)
|
|
331 |
return;
|
|
332 |
|
|
333 |
dprintf("object %4llu, txg %llu, pass %d, %c, count %lu, space %llx\n",
|
|
334 |
smo->smo_object, dmu_tx_get_txg(tx), spa_sync_pass(spa),
|
|
335 |
maptype == SM_ALLOC ? 'A' : 'F', avl_numnodes(&sm->sm_root),
|
|
336 |
sm->sm_space);
|
|
337 |
|
|
338 |
bufsize = (8 + avl_numnodes(&sm->sm_root)) * sizeof (uint64_t);
|
|
339 |
bufsize = MIN(bufsize, SPACE_MAP_CHUNKSIZE);
|
|
340 |
entry_map = kmem_alloc(bufsize, KM_SLEEP);
|
|
341 |
entry_map_end = entry_map + (bufsize / sizeof (uint64_t));
|
|
342 |
entry = entry_map;
|
|
343 |
|
|
344 |
*entry++ = SM_DEBUG_ENCODE(1) |
|
|
345 |
SM_DEBUG_ACTION_ENCODE(maptype) |
|
|
346 |
SM_DEBUG_SYNCPASS_ENCODE(spa_sync_pass(spa)) |
|
|
347 |
SM_DEBUG_TXG_ENCODE(dmu_tx_get_txg(tx));
|
|
348 |
|
|
349 |
while ((ss = avl_destroy_nodes(&sm->sm_root, &cookie)) != NULL) {
|
|
350 |
size = ss->ss_end - ss->ss_start;
|
|
351 |
start = (ss->ss_start - sm->sm_start) >> sm->sm_shift;
|
|
352 |
|
|
353 |
if (dest)
|
|
354 |
space_map_add(dest, ss->ss_start, size);
|
|
355 |
|
|
356 |
sm->sm_space -= size;
|
|
357 |
size >>= sm->sm_shift;
|
|
358 |
|
|
359 |
while (size) {
|
|
360 |
run_len = MIN(size, SM_RUN_MAX);
|
|
361 |
|
|
362 |
if (entry == entry_map_end) {
|
|
363 |
dmu_write(os, smo->smo_object, smo->smo_objsize,
|
|
364 |
bufsize, entry_map, tx);
|
|
365 |
smo->smo_objsize += bufsize;
|
|
366 |
entry = entry_map;
|
|
367 |
}
|
|
368 |
|
|
369 |
*entry++ = SM_OFFSET_ENCODE(start) |
|
|
370 |
SM_TYPE_ENCODE(maptype) |
|
|
371 |
SM_RUN_ENCODE(run_len);
|
|
372 |
|
|
373 |
start += run_len;
|
|
374 |
size -= run_len;
|
|
375 |
}
|
|
376 |
kmem_free(ss, sizeof (*ss));
|
|
377 |
}
|
|
378 |
|
|
379 |
if (entry != entry_map) {
|
|
380 |
size = (entry - entry_map) * sizeof (uint64_t);
|
|
381 |
dmu_write(os, smo->smo_object, smo->smo_objsize,
|
|
382 |
size, entry_map, tx);
|
|
383 |
smo->smo_objsize += size;
|
|
384 |
}
|
|
385 |
|
|
386 |
kmem_free(entry_map, bufsize);
|
|
387 |
|
|
388 |
VERIFY3U(sm->sm_space, ==, 0);
|
|
389 |
}
|
|
390 |
|
|
391 |
void
|
|
392 |
space_map_write(space_map_t *sm, space_map_obj_t *smo, objset_t *os,
|
|
393 |
dmu_tx_t *tx)
|
|
394 |
{
|
|
395 |
uint64_t oldsize = smo->smo_objsize;
|
|
396 |
|
1544
|
397 |
VERIFY(0 == dmu_free_range(os, smo->smo_object, 0,
|
|
398 |
smo->smo_objsize, tx));
|
789
|
399 |
|
|
400 |
smo->smo_objsize = 0;
|
|
401 |
|
|
402 |
VERIFY3U(sm->sm_space, ==, smo->smo_alloc);
|
|
403 |
space_map_sync(sm, NULL, smo, SM_ALLOC, os, tx);
|
|
404 |
|
|
405 |
dprintf("write sm object %llu from %llu to %llu bytes in txg %llu\n",
|
|
406 |
smo->smo_object, oldsize, smo->smo_objsize, dmu_tx_get_txg(tx));
|
|
407 |
}
|