4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
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 /*
22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 #include <sys/zfs_context.h>
27 #include <sys/spa.h>
28 #include <sys/dmu.h>
29 #include <sys/zio.h>
30 #include <sys/space_map.h>
31
32 /*
33 * Space map routines.
34 * NOTE: caller is responsible for all locking.
35 */
36 static int
37 space_map_seg_compare(const void *x1, const void *x2)
38 {
39 const space_seg_t *s1 = x1;
40 const space_seg_t *s2 = x2;
41
42 if (s1->ss_start < s2->ss_start) {
43 if (s1->ss_end > s2->ss_start)
44 return (0);
45 return (-1);
56 space_map_create(space_map_t *sm, uint64_t start, uint64_t size, uint8_t shift,
57 kmutex_t *lp)
58 {
59 bzero(sm, sizeof (*sm));
60
61 cv_init(&sm->sm_load_cv, NULL, CV_DEFAULT, NULL);
62
63 avl_create(&sm->sm_root, space_map_seg_compare,
64 sizeof (space_seg_t), offsetof(struct space_seg, ss_node));
65
66 sm->sm_start = start;
67 sm->sm_size = size;
68 sm->sm_shift = shift;
69 sm->sm_lock = lp;
70 }
71
72 void
73 space_map_destroy(space_map_t *sm)
74 {
75 ASSERT(!sm->sm_loaded && !sm->sm_loading);
76 VERIFY3U(sm->sm_space, ==, 0);
77 avl_destroy(&sm->sm_root);
78 cv_destroy(&sm->sm_load_cv);
79 }
80
81 void
82 space_map_add(space_map_t *sm, uint64_t start, uint64_t size)
83 {
84 avl_index_t where;
85 space_seg_t ssearch, *ss_before, *ss_after, *ss;
86 uint64_t end = start + size;
87 int merge_before, merge_after;
88
89 ASSERT(MUTEX_HELD(sm->sm_lock));
90 VERIFY(size != 0);
91 VERIFY3U(start, >=, sm->sm_start);
92 VERIFY3U(end, <=, sm->sm_start + sm->sm_size);
93 VERIFY(sm->sm_space + size <= sm->sm_size);
94 VERIFY(P2PHASE(start, 1ULL << sm->sm_shift) == 0);
95 VERIFY(P2PHASE(size, 1ULL << sm->sm_shift) == 0);
96
269 * The caller must be OK with this.
270 */
271 int
272 space_map_load(space_map_t *sm, space_map_ops_t *ops, uint8_t maptype,
273 space_map_obj_t *smo, objset_t *os)
274 {
275 uint64_t *entry, *entry_map, *entry_map_end;
276 uint64_t bufsize, size, offset, end, space;
277 uint64_t mapstart = sm->sm_start;
278 int error = 0;
279
280 ASSERT(MUTEX_HELD(sm->sm_lock));
281 ASSERT(!sm->sm_loaded);
282 ASSERT(!sm->sm_loading);
283
284 sm->sm_loading = B_TRUE;
285 end = smo->smo_objsize;
286 space = smo->smo_alloc;
287
288 ASSERT(sm->sm_ops == NULL);
289 VERIFY3U(sm->sm_space, ==, 0);
290
291 if (maptype == SM_FREE) {
292 space_map_add(sm, sm->sm_start, sm->sm_size);
293 space = sm->sm_size - space;
294 }
295
296 bufsize = 1ULL << SPACE_MAP_BLOCKSHIFT;
297 entry_map = zio_buf_alloc(bufsize);
298
299 mutex_exit(sm->sm_lock);
300 if (end > bufsize)
301 dmu_prefetch(os, smo->smo_object, bufsize, end - bufsize);
302 mutex_enter(sm->sm_lock);
303
304 for (offset = 0; offset < end; offset += bufsize) {
305 size = MIN(end - offset, bufsize);
306 VERIFY(P2PHASE(size, sizeof (uint64_t)) == 0);
307 VERIFY(size != 0);
308
309 dprintf("object=%llu offset=%llx size=%llx\n",
458 SM_TYPE_ENCODE(maptype) |
459 SM_RUN_ENCODE(run_len);
460
461 start += run_len;
462 size -= run_len;
463 }
464 kmem_free(ss, sizeof (*ss));
465 }
466
467 if (entry != entry_map) {
468 size = (entry - entry_map) * sizeof (uint64_t);
469 mutex_exit(sm->sm_lock);
470 dmu_write(os, smo->smo_object, smo->smo_objsize,
471 size, entry_map, tx);
472 mutex_enter(sm->sm_lock);
473 smo->smo_objsize += size;
474 }
475
476 zio_buf_free(entry_map, bufsize);
477
478 VERIFY3U(sm->sm_space, ==, 0);
479 }
480
481 void
482 space_map_truncate(space_map_obj_t *smo, objset_t *os, dmu_tx_t *tx)
483 {
484 VERIFY(dmu_free_range(os, smo->smo_object, 0, -1ULL, tx) == 0);
485
486 smo->smo_objsize = 0;
487 smo->smo_alloc = 0;
488 }
489
490 /*
491 * Space map reference trees.
492 *
493 * A space map is a collection of integers. Every integer is either
494 * in the map, or it's not. A space map reference tree generalizes
495 * the idea: it allows its members to have arbitrary reference counts,
496 * as opposed to the implicit reference count of 0 or 1 in a space map.
497 * This representation comes in handy when computing the union or
498 * intersection of multiple space maps. For example, the union of
|
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
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 /*
22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 *
25 */
26
27 /*
28 * Copyright (c) 2012 by Delphix. All rights reserved.
29 */
30
31 #include <sys/zfs_context.h>
32 #include <sys/spa.h>
33 #include <sys/dmu.h>
34 #include <sys/zio.h>
35 #include <sys/space_map.h>
36
37 /*
38 * Space map routines.
39 * NOTE: caller is responsible for all locking.
40 */
41 static int
42 space_map_seg_compare(const void *x1, const void *x2)
43 {
44 const space_seg_t *s1 = x1;
45 const space_seg_t *s2 = x2;
46
47 if (s1->ss_start < s2->ss_start) {
48 if (s1->ss_end > s2->ss_start)
49 return (0);
50 return (-1);
61 space_map_create(space_map_t *sm, uint64_t start, uint64_t size, uint8_t shift,
62 kmutex_t *lp)
63 {
64 bzero(sm, sizeof (*sm));
65
66 cv_init(&sm->sm_load_cv, NULL, CV_DEFAULT, NULL);
67
68 avl_create(&sm->sm_root, space_map_seg_compare,
69 sizeof (space_seg_t), offsetof(struct space_seg, ss_node));
70
71 sm->sm_start = start;
72 sm->sm_size = size;
73 sm->sm_shift = shift;
74 sm->sm_lock = lp;
75 }
76
77 void
78 space_map_destroy(space_map_t *sm)
79 {
80 ASSERT(!sm->sm_loaded && !sm->sm_loading);
81 VERIFY0(sm->sm_space);
82 avl_destroy(&sm->sm_root);
83 cv_destroy(&sm->sm_load_cv);
84 }
85
86 void
87 space_map_add(space_map_t *sm, uint64_t start, uint64_t size)
88 {
89 avl_index_t where;
90 space_seg_t ssearch, *ss_before, *ss_after, *ss;
91 uint64_t end = start + size;
92 int merge_before, merge_after;
93
94 ASSERT(MUTEX_HELD(sm->sm_lock));
95 VERIFY(size != 0);
96 VERIFY3U(start, >=, sm->sm_start);
97 VERIFY3U(end, <=, sm->sm_start + sm->sm_size);
98 VERIFY(sm->sm_space + size <= sm->sm_size);
99 VERIFY(P2PHASE(start, 1ULL << sm->sm_shift) == 0);
100 VERIFY(P2PHASE(size, 1ULL << sm->sm_shift) == 0);
101
274 * The caller must be OK with this.
275 */
276 int
277 space_map_load(space_map_t *sm, space_map_ops_t *ops, uint8_t maptype,
278 space_map_obj_t *smo, objset_t *os)
279 {
280 uint64_t *entry, *entry_map, *entry_map_end;
281 uint64_t bufsize, size, offset, end, space;
282 uint64_t mapstart = sm->sm_start;
283 int error = 0;
284
285 ASSERT(MUTEX_HELD(sm->sm_lock));
286 ASSERT(!sm->sm_loaded);
287 ASSERT(!sm->sm_loading);
288
289 sm->sm_loading = B_TRUE;
290 end = smo->smo_objsize;
291 space = smo->smo_alloc;
292
293 ASSERT(sm->sm_ops == NULL);
294 VERIFY0(sm->sm_space);
295
296 if (maptype == SM_FREE) {
297 space_map_add(sm, sm->sm_start, sm->sm_size);
298 space = sm->sm_size - space;
299 }
300
301 bufsize = 1ULL << SPACE_MAP_BLOCKSHIFT;
302 entry_map = zio_buf_alloc(bufsize);
303
304 mutex_exit(sm->sm_lock);
305 if (end > bufsize)
306 dmu_prefetch(os, smo->smo_object, bufsize, end - bufsize);
307 mutex_enter(sm->sm_lock);
308
309 for (offset = 0; offset < end; offset += bufsize) {
310 size = MIN(end - offset, bufsize);
311 VERIFY(P2PHASE(size, sizeof (uint64_t)) == 0);
312 VERIFY(size != 0);
313
314 dprintf("object=%llu offset=%llx size=%llx\n",
463 SM_TYPE_ENCODE(maptype) |
464 SM_RUN_ENCODE(run_len);
465
466 start += run_len;
467 size -= run_len;
468 }
469 kmem_free(ss, sizeof (*ss));
470 }
471
472 if (entry != entry_map) {
473 size = (entry - entry_map) * sizeof (uint64_t);
474 mutex_exit(sm->sm_lock);
475 dmu_write(os, smo->smo_object, smo->smo_objsize,
476 size, entry_map, tx);
477 mutex_enter(sm->sm_lock);
478 smo->smo_objsize += size;
479 }
480
481 zio_buf_free(entry_map, bufsize);
482
483 VERIFY0(sm->sm_space);
484 }
485
486 void
487 space_map_truncate(space_map_obj_t *smo, objset_t *os, dmu_tx_t *tx)
488 {
489 VERIFY(dmu_free_range(os, smo->smo_object, 0, -1ULL, tx) == 0);
490
491 smo->smo_objsize = 0;
492 smo->smo_alloc = 0;
493 }
494
495 /*
496 * Space map reference trees.
497 *
498 * A space map is a collection of integers. Every integer is either
499 * in the map, or it's not. A space map reference tree generalizes
500 * the idea: it allows its members to have arbitrary reference counts,
501 * as opposed to the implicit reference count of 0 or 1 in a space map.
502 * This representation comes in handy when computing the union or
503 * intersection of multiple space maps. For example, the union of
|