1 789 ahrens /* 2 789 ahrens * CDDL HEADER START 3 789 ahrens * 4 789 ahrens * The contents of this file are subject to the terms of the 5 1544 eschrock * Common Development and Distribution License (the "License"). 6 1544 eschrock * You may not use this file except in compliance with the License. 7 789 ahrens * 8 789 ahrens * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 789 ahrens * or http://www.opensolaris.org/os/licensing. 10 789 ahrens * See the License for the specific language governing permissions 11 789 ahrens * and limitations under the License. 12 789 ahrens * 13 789 ahrens * When distributing Covered Code, include this CDDL HEADER in each 14 789 ahrens * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 789 ahrens * If applicable, add the following below this CDDL HEADER, with the 16 789 ahrens * fields enclosed by brackets "[]" replaced with your own identifying 17 789 ahrens * information: Portions Copyright [yyyy] [name of copyright owner] 18 789 ahrens * 19 789 ahrens * CDDL HEADER END 20 789 ahrens */ 21 789 ahrens /* 22 9480 George * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 23 789 ahrens * Use is subject to license terms. 24 789 ahrens */ 25 789 ahrens 26 789 ahrens #include <sys/zfs_context.h> 27 789 ahrens #include <sys/spa.h> 28 789 ahrens #include <sys/dmu.h> 29 1732 bonwick #include <sys/zio.h> 30 789 ahrens #include <sys/space_map.h> 31 789 ahrens 32 789 ahrens /* 33 789 ahrens * Space map routines. 34 789 ahrens * NOTE: caller is responsible for all locking. 35 789 ahrens */ 36 789 ahrens static int 37 789 ahrens space_map_seg_compare(const void *x1, const void *x2) 38 789 ahrens { 39 789 ahrens const space_seg_t *s1 = x1; 40 789 ahrens const space_seg_t *s2 = x2; 41 789 ahrens 42 789 ahrens if (s1->ss_start < s2->ss_start) { 43 789 ahrens if (s1->ss_end > s2->ss_start) 44 789 ahrens return (0); 45 789 ahrens return (-1); 46 789 ahrens } 47 789 ahrens if (s1->ss_start > s2->ss_start) { 48 789 ahrens if (s1->ss_start < s2->ss_end) 49 789 ahrens return (0); 50 789 ahrens return (1); 51 789 ahrens } 52 789 ahrens return (0); 53 789 ahrens } 54 789 ahrens 55 789 ahrens void 56 1732 bonwick space_map_create(space_map_t *sm, uint64_t start, uint64_t size, uint8_t shift, 57 789 ahrens kmutex_t *lp) 58 789 ahrens { 59 1732 bonwick bzero(sm, sizeof (*sm)); 60 1732 bonwick 61 8214 Ricardo cv_init(&sm->sm_load_cv, NULL, CV_DEFAULT, NULL); 62 8214 Ricardo 63 789 ahrens avl_create(&sm->sm_root, space_map_seg_compare, 64 789 ahrens sizeof (space_seg_t), offsetof(struct space_seg, ss_node)); 65 1732 bonwick 66 789 ahrens sm->sm_start = start; 67 789 ahrens sm->sm_size = size; 68 789 ahrens sm->sm_shift = shift; 69 789 ahrens sm->sm_lock = lp; 70 789 ahrens } 71 789 ahrens 72 789 ahrens void 73 789 ahrens space_map_destroy(space_map_t *sm) 74 789 ahrens { 75 1732 bonwick ASSERT(!sm->sm_loaded && !sm->sm_loading); 76 789 ahrens VERIFY3U(sm->sm_space, ==, 0); 77 789 ahrens avl_destroy(&sm->sm_root); 78 8214 Ricardo cv_destroy(&sm->sm_load_cv); 79 789 ahrens } 80 789 ahrens 81 789 ahrens void 82 789 ahrens space_map_add(space_map_t *sm, uint64_t start, uint64_t size) 83 789 ahrens { 84 789 ahrens avl_index_t where; 85 789 ahrens space_seg_t ssearch, *ss_before, *ss_after, *ss; 86 789 ahrens uint64_t end = start + size; 87 789 ahrens int merge_before, merge_after; 88 789 ahrens 89 789 ahrens ASSERT(MUTEX_HELD(sm->sm_lock)); 90 789 ahrens VERIFY(size != 0); 91 789 ahrens VERIFY3U(start, >=, sm->sm_start); 92 1732 bonwick VERIFY3U(end, <=, sm->sm_start + sm->sm_size); 93 789 ahrens VERIFY(sm->sm_space + size <= sm->sm_size); 94 789 ahrens VERIFY(P2PHASE(start, 1ULL << sm->sm_shift) == 0); 95 789 ahrens VERIFY(P2PHASE(size, 1ULL << sm->sm_shift) == 0); 96 789 ahrens 97 789 ahrens ssearch.ss_start = start; 98 789 ahrens ssearch.ss_end = end; 99 789 ahrens ss = avl_find(&sm->sm_root, &ssearch, &where); 100 789 ahrens 101 3713 ahrens if (ss != NULL && ss->ss_start <= start && ss->ss_end >= end) { 102 3713 ahrens zfs_panic_recover("zfs: allocating allocated segment" 103 3713 ahrens "(offset=%llu size=%llu)\n", 104 3713 ahrens (longlong_t)start, (longlong_t)size); 105 3713 ahrens return; 106 3713 ahrens } 107 3713 ahrens 108 789 ahrens /* Make sure we don't overlap with either of our neighbors */ 109 789 ahrens VERIFY(ss == NULL); 110 789 ahrens 111 789 ahrens ss_before = avl_nearest(&sm->sm_root, where, AVL_BEFORE); 112 789 ahrens ss_after = avl_nearest(&sm->sm_root, where, AVL_AFTER); 113 789 ahrens 114 789 ahrens merge_before = (ss_before != NULL && ss_before->ss_end == start); 115 789 ahrens merge_after = (ss_after != NULL && ss_after->ss_start == end); 116 789 ahrens 117 789 ahrens if (merge_before && merge_after) { 118 789 ahrens avl_remove(&sm->sm_root, ss_before); 119 9480 George if (sm->sm_pp_root) { 120 9480 George avl_remove(sm->sm_pp_root, ss_before); 121 9480 George avl_remove(sm->sm_pp_root, ss_after); 122 9480 George } 123 789 ahrens ss_after->ss_start = ss_before->ss_start; 124 789 ahrens kmem_free(ss_before, sizeof (*ss_before)); 125 9480 George ss = ss_after; 126 789 ahrens } else if (merge_before) { 127 789 ahrens ss_before->ss_end = end; 128 9480 George if (sm->sm_pp_root) 129 9480 George avl_remove(sm->sm_pp_root, ss_before); 130 9480 George ss = ss_before; 131 789 ahrens } else if (merge_after) { 132 789 ahrens ss_after->ss_start = start; 133 9480 George if (sm->sm_pp_root) 134 9480 George avl_remove(sm->sm_pp_root, ss_after); 135 9480 George ss = ss_after; 136 789 ahrens } else { 137 789 ahrens ss = kmem_alloc(sizeof (*ss), KM_SLEEP); 138 789 ahrens ss->ss_start = start; 139 789 ahrens ss->ss_end = end; 140 789 ahrens avl_insert(&sm->sm_root, ss, where); 141 789 ahrens } 142 9480 George 143 9480 George if (sm->sm_pp_root) 144 9480 George avl_add(sm->sm_pp_root, ss); 145 789 ahrens 146 789 ahrens sm->sm_space += size; 147 789 ahrens } 148 789 ahrens 149 789 ahrens void 150 789 ahrens space_map_remove(space_map_t *sm, uint64_t start, uint64_t size) 151 789 ahrens { 152 789 ahrens avl_index_t where; 153 789 ahrens space_seg_t ssearch, *ss, *newseg; 154 789 ahrens uint64_t end = start + size; 155 789 ahrens int left_over, right_over; 156 789 ahrens 157 789 ahrens ASSERT(MUTEX_HELD(sm->sm_lock)); 158 789 ahrens VERIFY(size != 0); 159 789 ahrens VERIFY(P2PHASE(start, 1ULL << sm->sm_shift) == 0); 160 789 ahrens VERIFY(P2PHASE(size, 1ULL << sm->sm_shift) == 0); 161 789 ahrens 162 789 ahrens ssearch.ss_start = start; 163 789 ahrens ssearch.ss_end = end; 164 789 ahrens ss = avl_find(&sm->sm_root, &ssearch, &where); 165 789 ahrens 166 789 ahrens /* Make sure we completely overlap with someone */ 167 3713 ahrens if (ss == NULL) { 168 3713 ahrens zfs_panic_recover("zfs: freeing free segment " 169 3713 ahrens "(offset=%llu size=%llu)", 170 3713 ahrens (longlong_t)start, (longlong_t)size); 171 3713 ahrens return; 172 3713 ahrens } 173 789 ahrens VERIFY3U(ss->ss_start, <=, start); 174 789 ahrens VERIFY3U(ss->ss_end, >=, end); 175 789 ahrens VERIFY(sm->sm_space - size <= sm->sm_size); 176 789 ahrens 177 789 ahrens left_over = (ss->ss_start != start); 178 789 ahrens right_over = (ss->ss_end != end); 179 789 ahrens 180 9480 George if (sm->sm_pp_root) 181 9480 George avl_remove(sm->sm_pp_root, ss); 182 9480 George 183 789 ahrens if (left_over && right_over) { 184 789 ahrens newseg = kmem_alloc(sizeof (*newseg), KM_SLEEP); 185 789 ahrens newseg->ss_start = end; 186 789 ahrens newseg->ss_end = ss->ss_end; 187 789 ahrens ss->ss_end = start; 188 789 ahrens avl_insert_here(&sm->sm_root, newseg, ss, AVL_AFTER); 189 9480 George if (sm->sm_pp_root) 190 9480 George avl_add(sm->sm_pp_root, newseg); 191 789 ahrens } else if (left_over) { 192 789 ahrens ss->ss_end = start; 193 789 ahrens } else if (right_over) { 194 789 ahrens ss->ss_start = end; 195 789 ahrens } else { 196 789 ahrens avl_remove(&sm->sm_root, ss); 197 789 ahrens kmem_free(ss, sizeof (*ss)); 198 9480 George ss = NULL; 199 789 ahrens } 200 9480 George 201 9480 George if (sm->sm_pp_root && ss != NULL) 202 9480 George avl_add(sm->sm_pp_root, ss); 203 789 ahrens 204 789 ahrens sm->sm_space -= size; 205 789 ahrens } 206 789 ahrens 207 8241 Jeff boolean_t 208 789 ahrens space_map_contains(space_map_t *sm, uint64_t start, uint64_t size) 209 789 ahrens { 210 789 ahrens avl_index_t where; 211 789 ahrens space_seg_t ssearch, *ss; 212 789 ahrens uint64_t end = start + size; 213 789 ahrens 214 789 ahrens ASSERT(MUTEX_HELD(sm->sm_lock)); 215 789 ahrens VERIFY(size != 0); 216 789 ahrens VERIFY(P2PHASE(start, 1ULL << sm->sm_shift) == 0); 217 789 ahrens VERIFY(P2PHASE(size, 1ULL << sm->sm_shift) == 0); 218 789 ahrens 219 789 ahrens ssearch.ss_start = start; 220 789 ahrens ssearch.ss_end = end; 221 789 ahrens ss = avl_find(&sm->sm_root, &ssearch, &where); 222 789 ahrens 223 789 ahrens return (ss != NULL && ss->ss_start <= start && ss->ss_end >= end); 224 789 ahrens } 225 789 ahrens 226 789 ahrens void 227 789 ahrens space_map_vacate(space_map_t *sm, space_map_func_t *func, space_map_t *mdest) 228 789 ahrens { 229 789 ahrens space_seg_t *ss; 230 789 ahrens void *cookie = NULL; 231 789 ahrens 232 789 ahrens ASSERT(MUTEX_HELD(sm->sm_lock)); 233 789 ahrens 234 789 ahrens while ((ss = avl_destroy_nodes(&sm->sm_root, &cookie)) != NULL) { 235 789 ahrens if (func != NULL) 236 789 ahrens func(mdest, ss->ss_start, ss->ss_end - ss->ss_start); 237 789 ahrens kmem_free(ss, sizeof (*ss)); 238 789 ahrens } 239 789 ahrens sm->sm_space = 0; 240 789 ahrens } 241 789 ahrens 242 789 ahrens void 243 1732 bonwick space_map_walk(space_map_t *sm, space_map_func_t *func, space_map_t *mdest) 244 789 ahrens { 245 789 ahrens space_seg_t *ss; 246 789 ahrens 247 8241 Jeff ASSERT(MUTEX_HELD(sm->sm_lock)); 248 8241 Jeff 249 789 ahrens for (ss = avl_first(&sm->sm_root); ss; ss = AVL_NEXT(&sm->sm_root, ss)) 250 789 ahrens func(mdest, ss->ss_start, ss->ss_end - ss->ss_start); 251 789 ahrens } 252 789 ahrens 253 1732 bonwick /* 254 1732 bonwick * Wait for any in-progress space_map_load() to complete. 255 1732 bonwick */ 256 1732 bonwick void 257 1732 bonwick space_map_load_wait(space_map_t *sm) 258 1732 bonwick { 259 1732 bonwick ASSERT(MUTEX_HELD(sm->sm_lock)); 260 1732 bonwick 261 10922 Jeff while (sm->sm_loading) { 262 10922 Jeff ASSERT(!sm->sm_loaded); 263 1732 bonwick cv_wait(&sm->sm_load_cv, sm->sm_lock); 264 10922 Jeff } 265 1732 bonwick } 266 1732 bonwick 267 1732 bonwick /* 268 1732 bonwick * Note: space_map_load() will drop sm_lock across dmu_read() calls. 269 1732 bonwick * The caller must be OK with this. 270 1732 bonwick */ 271 789 ahrens int 272 1732 bonwick space_map_load(space_map_t *sm, space_map_ops_t *ops, uint8_t maptype, 273 1732 bonwick space_map_obj_t *smo, objset_t *os) 274 789 ahrens { 275 789 ahrens uint64_t *entry, *entry_map, *entry_map_end; 276 3761 billm uint64_t bufsize, size, offset, end, space; 277 789 ahrens uint64_t mapstart = sm->sm_start; 278 5329 gw25295 int error = 0; 279 789 ahrens 280 789 ahrens ASSERT(MUTEX_HELD(sm->sm_lock)); 281 10921 Tim ASSERT(!sm->sm_loaded); 282 10921 Tim ASSERT(!sm->sm_loading); 283 1732 bonwick 284 1732 bonwick sm->sm_loading = B_TRUE; 285 3761 billm end = smo->smo_objsize; 286 3761 billm space = smo->smo_alloc; 287 1732 bonwick 288 1732 bonwick ASSERT(sm->sm_ops == NULL); 289 789 ahrens VERIFY3U(sm->sm_space, ==, 0); 290 789 ahrens 291 789 ahrens if (maptype == SM_FREE) { 292 789 ahrens space_map_add(sm, sm->sm_start, sm->sm_size); 293 789 ahrens space = sm->sm_size - space; 294 789 ahrens } 295 1732 bonwick 296 1732 bonwick bufsize = 1ULL << SPACE_MAP_BLOCKSHIFT; 297 1732 bonwick entry_map = zio_buf_alloc(bufsize); 298 1732 bonwick 299 1732 bonwick mutex_exit(sm->sm_lock); 300 1732 bonwick if (end > bufsize) 301 1732 bonwick dmu_prefetch(os, smo->smo_object, bufsize, end - bufsize); 302 1732 bonwick mutex_enter(sm->sm_lock); 303 789 ahrens 304 789 ahrens for (offset = 0; offset < end; offset += bufsize) { 305 789 ahrens size = MIN(end - offset, bufsize); 306 789 ahrens VERIFY(P2PHASE(size, sizeof (uint64_t)) == 0); 307 789 ahrens VERIFY(size != 0); 308 789 ahrens 309 789 ahrens dprintf("object=%llu offset=%llx size=%llx\n", 310 789 ahrens smo->smo_object, offset, size); 311 1732 bonwick 312 1732 bonwick mutex_exit(sm->sm_lock); 313 9512 Neil error = dmu_read(os, smo->smo_object, offset, size, entry_map, 314 9512 Neil DMU_READ_PREFETCH); 315 1732 bonwick mutex_enter(sm->sm_lock); 316 5329 gw25295 if (error != 0) 317 6227 vl146290 break; 318 789 ahrens 319 789 ahrens entry_map_end = entry_map + (size / sizeof (uint64_t)); 320 789 ahrens for (entry = entry_map; entry < entry_map_end; entry++) { 321 789 ahrens uint64_t e = *entry; 322 789 ahrens 323 789 ahrens if (SM_DEBUG_DECODE(e)) /* Skip debug entries */ 324 789 ahrens continue; 325 789 ahrens 326 789 ahrens (SM_TYPE_DECODE(e) == maptype ? 327 789 ahrens space_map_add : space_map_remove)(sm, 328 789 ahrens (SM_OFFSET_DECODE(e) << sm->sm_shift) + mapstart, 329 789 ahrens SM_RUN_DECODE(e) << sm->sm_shift); 330 789 ahrens } 331 789 ahrens } 332 789 ahrens 333 6227 vl146290 if (error == 0) { 334 6227 vl146290 VERIFY3U(sm->sm_space, ==, space); 335 6227 vl146290 336 6227 vl146290 sm->sm_loaded = B_TRUE; 337 6227 vl146290 sm->sm_ops = ops; 338 6227 vl146290 if (ops != NULL) 339 6227 vl146290 ops->smop_load(sm); 340 6227 vl146290 } else { 341 6227 vl146290 space_map_vacate(sm, NULL, NULL); 342 6227 vl146290 } 343 6227 vl146290 344 1732 bonwick zio_buf_free(entry_map, bufsize); 345 1732 bonwick 346 1732 bonwick sm->sm_loading = B_FALSE; 347 1732 bonwick 348 1732 bonwick cv_broadcast(&sm->sm_load_cv); 349 789 ahrens 350 5329 gw25295 return (error); 351 789 ahrens } 352 789 ahrens 353 789 ahrens void 354 1732 bonwick space_map_unload(space_map_t *sm) 355 1732 bonwick { 356 1732 bonwick ASSERT(MUTEX_HELD(sm->sm_lock)); 357 1732 bonwick 358 1732 bonwick if (sm->sm_loaded && sm->sm_ops != NULL) 359 1732 bonwick sm->sm_ops->smop_unload(sm); 360 1732 bonwick 361 1732 bonwick sm->sm_loaded = B_FALSE; 362 1732 bonwick sm->sm_ops = NULL; 363 1732 bonwick 364 1732 bonwick space_map_vacate(sm, NULL, NULL); 365 9480 George } 366 9480 George 367 9480 George uint64_t 368 9480 George space_map_maxsize(space_map_t *sm) 369 9480 George { 370 11146 George ASSERT(sm->sm_ops != NULL); 371 11146 George return (sm->sm_ops->smop_max(sm)); 372 1732 bonwick } 373 1732 bonwick 374 1732 bonwick uint64_t 375 1732 bonwick space_map_alloc(space_map_t *sm, uint64_t size) 376 1732 bonwick { 377 1732 bonwick uint64_t start; 378 1732 bonwick 379 1732 bonwick start = sm->sm_ops->smop_alloc(sm, size); 380 1732 bonwick if (start != -1ULL) 381 1732 bonwick space_map_remove(sm, start, size); 382 1732 bonwick return (start); 383 1732 bonwick } 384 1732 bonwick 385 1732 bonwick void 386 1732 bonwick space_map_claim(space_map_t *sm, uint64_t start, uint64_t size) 387 1732 bonwick { 388 1732 bonwick sm->sm_ops->smop_claim(sm, start, size); 389 1732 bonwick space_map_remove(sm, start, size); 390 1732 bonwick } 391 1732 bonwick 392 1732 bonwick void 393 1732 bonwick space_map_free(space_map_t *sm, uint64_t start, uint64_t size) 394 1732 bonwick { 395 1732 bonwick space_map_add(sm, start, size); 396 1732 bonwick sm->sm_ops->smop_free(sm, start, size); 397 1732 bonwick } 398 1732 bonwick 399 1732 bonwick /* 400 1732 bonwick * Note: space_map_sync() will drop sm_lock across dmu_write() calls. 401 1732 bonwick */ 402 1732 bonwick void 403 1732 bonwick space_map_sync(space_map_t *sm, uint8_t maptype, 404 1732 bonwick space_map_obj_t *smo, objset_t *os, dmu_tx_t *tx) 405 789 ahrens { 406 789 ahrens spa_t *spa = dmu_objset_spa(os); 407 789 ahrens void *cookie = NULL; 408 789 ahrens space_seg_t *ss; 409 789 ahrens uint64_t bufsize, start, size, run_len; 410 789 ahrens uint64_t *entry, *entry_map, *entry_map_end; 411 789 ahrens 412 789 ahrens ASSERT(MUTEX_HELD(sm->sm_lock)); 413 789 ahrens 414 789 ahrens if (sm->sm_space == 0) 415 789 ahrens return; 416 789 ahrens 417 789 ahrens dprintf("object %4llu, txg %llu, pass %d, %c, count %lu, space %llx\n", 418 789 ahrens smo->smo_object, dmu_tx_get_txg(tx), spa_sync_pass(spa), 419 789 ahrens maptype == SM_ALLOC ? 'A' : 'F', avl_numnodes(&sm->sm_root), 420 789 ahrens sm->sm_space); 421 789 ahrens 422 1732 bonwick if (maptype == SM_ALLOC) 423 1732 bonwick smo->smo_alloc += sm->sm_space; 424 1732 bonwick else 425 1732 bonwick smo->smo_alloc -= sm->sm_space; 426 1732 bonwick 427 789 ahrens bufsize = (8 + avl_numnodes(&sm->sm_root)) * sizeof (uint64_t); 428 1732 bonwick bufsize = MIN(bufsize, 1ULL << SPACE_MAP_BLOCKSHIFT); 429 1732 bonwick entry_map = zio_buf_alloc(bufsize); 430 789 ahrens entry_map_end = entry_map + (bufsize / sizeof (uint64_t)); 431 789 ahrens entry = entry_map; 432 789 ahrens 433 789 ahrens *entry++ = SM_DEBUG_ENCODE(1) | 434 789 ahrens SM_DEBUG_ACTION_ENCODE(maptype) | 435 789 ahrens SM_DEBUG_SYNCPASS_ENCODE(spa_sync_pass(spa)) | 436 789 ahrens SM_DEBUG_TXG_ENCODE(dmu_tx_get_txg(tx)); 437 789 ahrens 438 789 ahrens while ((ss = avl_destroy_nodes(&sm->sm_root, &cookie)) != NULL) { 439 789 ahrens size = ss->ss_end - ss->ss_start; 440 789 ahrens start = (ss->ss_start - sm->sm_start) >> sm->sm_shift; 441 789 ahrens 442 789 ahrens sm->sm_space -= size; 443 789 ahrens size >>= sm->sm_shift; 444 789 ahrens 445 789 ahrens while (size) { 446 789 ahrens run_len = MIN(size, SM_RUN_MAX); 447 789 ahrens 448 789 ahrens if (entry == entry_map_end) { 449 1732 bonwick mutex_exit(sm->sm_lock); 450 789 ahrens dmu_write(os, smo->smo_object, smo->smo_objsize, 451 789 ahrens bufsize, entry_map, tx); 452 1732 bonwick mutex_enter(sm->sm_lock); 453 789 ahrens smo->smo_objsize += bufsize; 454 789 ahrens entry = entry_map; 455 789 ahrens } 456 789 ahrens 457 789 ahrens *entry++ = SM_OFFSET_ENCODE(start) | 458 789 ahrens SM_TYPE_ENCODE(maptype) | 459 789 ahrens SM_RUN_ENCODE(run_len); 460 789 ahrens 461 789 ahrens start += run_len; 462 789 ahrens size -= run_len; 463 789 ahrens } 464 789 ahrens kmem_free(ss, sizeof (*ss)); 465 789 ahrens } 466 789 ahrens 467 789 ahrens if (entry != entry_map) { 468 789 ahrens size = (entry - entry_map) * sizeof (uint64_t); 469 1732 bonwick mutex_exit(sm->sm_lock); 470 789 ahrens dmu_write(os, smo->smo_object, smo->smo_objsize, 471 789 ahrens size, entry_map, tx); 472 1732 bonwick mutex_enter(sm->sm_lock); 473 789 ahrens smo->smo_objsize += size; 474 789 ahrens } 475 789 ahrens 476 1732 bonwick zio_buf_free(entry_map, bufsize); 477 789 ahrens 478 789 ahrens VERIFY3U(sm->sm_space, ==, 0); 479 789 ahrens } 480 789 ahrens 481 789 ahrens void 482 1732 bonwick space_map_truncate(space_map_obj_t *smo, objset_t *os, dmu_tx_t *tx) 483 789 ahrens { 484 1732 bonwick VERIFY(dmu_free_range(os, smo->smo_object, 0, -1ULL, tx) == 0); 485 789 ahrens 486 789 ahrens smo->smo_objsize = 0; 487 1732 bonwick smo->smo_alloc = 0; 488 789 ahrens } 489 8241 Jeff 490 8241 Jeff /* 491 8241 Jeff * Space map reference trees. 492 8241 Jeff * 493 8241 Jeff * A space map is a collection of integers. Every integer is either 494 8241 Jeff * in the map, or it's not. A space map reference tree generalizes 495 8241 Jeff * the idea: it allows its members to have arbitrary reference counts, 496 8241 Jeff * as opposed to the implicit reference count of 0 or 1 in a space map. 497 8241 Jeff * This representation comes in handy when computing the union or 498 8241 Jeff * intersection of multiple space maps. For example, the union of 499 8241 Jeff * N space maps is the subset of the reference tree with refcnt >= 1. 500 8241 Jeff * The intersection of N space maps is the subset with refcnt >= N. 501 8241 Jeff * 502 8241 Jeff * [It's very much like a Fourier transform. Unions and intersections 503 8241 Jeff * are hard to perform in the 'space map domain', so we convert the maps 504 8241 Jeff * into the 'reference count domain', where it's trivial, then invert.] 505 8241 Jeff * 506 8241 Jeff * vdev_dtl_reassess() uses computations of this form to determine 507 8241 Jeff * DTL_MISSING and DTL_OUTAGE for interior vdevs -- e.g. a RAID-Z vdev 508 8241 Jeff * has an outage wherever refcnt >= vdev_nparity + 1, and a mirror vdev 509 8241 Jeff * has an outage wherever refcnt >= vdev_children. 510 8241 Jeff */ 511 8241 Jeff static int 512 8241 Jeff space_map_ref_compare(const void *x1, const void *x2) 513 8241 Jeff { 514 8241 Jeff const space_ref_t *sr1 = x1; 515 8241 Jeff const space_ref_t *sr2 = x2; 516 8241 Jeff 517 8241 Jeff if (sr1->sr_offset < sr2->sr_offset) 518 8241 Jeff return (-1); 519 8241 Jeff if (sr1->sr_offset > sr2->sr_offset) 520 8241 Jeff return (1); 521 8241 Jeff 522 8241 Jeff if (sr1 < sr2) 523 8241 Jeff return (-1); 524 8241 Jeff if (sr1 > sr2) 525 8241 Jeff return (1); 526 8241 Jeff 527 8241 Jeff return (0); 528 8241 Jeff } 529 8241 Jeff 530 8241 Jeff void 531 8241 Jeff space_map_ref_create(avl_tree_t *t) 532 8241 Jeff { 533 8241 Jeff avl_create(t, space_map_ref_compare, 534 8241 Jeff sizeof (space_ref_t), offsetof(space_ref_t, sr_node)); 535 8241 Jeff } 536 8241 Jeff 537 8241 Jeff void 538 8241 Jeff space_map_ref_destroy(avl_tree_t *t) 539 8241 Jeff { 540 8241 Jeff space_ref_t *sr; 541 8241 Jeff void *cookie = NULL; 542 8241 Jeff 543 8241 Jeff while ((sr = avl_destroy_nodes(t, &cookie)) != NULL) 544 8241 Jeff kmem_free(sr, sizeof (*sr)); 545 8241 Jeff 546 8241 Jeff avl_destroy(t); 547 8241 Jeff } 548 8241 Jeff 549 8241 Jeff static void 550 8241 Jeff space_map_ref_add_node(avl_tree_t *t, uint64_t offset, int64_t refcnt) 551 8241 Jeff { 552 8241 Jeff space_ref_t *sr; 553 8241 Jeff 554 8241 Jeff sr = kmem_alloc(sizeof (*sr), KM_SLEEP); 555 8241 Jeff sr->sr_offset = offset; 556 8241 Jeff sr->sr_refcnt = refcnt; 557 8241 Jeff 558 8241 Jeff avl_add(t, sr); 559 8241 Jeff } 560 8241 Jeff 561 8241 Jeff void 562 8241 Jeff space_map_ref_add_seg(avl_tree_t *t, uint64_t start, uint64_t end, 563 8241 Jeff int64_t refcnt) 564 8241 Jeff { 565 8241 Jeff space_map_ref_add_node(t, start, refcnt); 566 8241 Jeff space_map_ref_add_node(t, end, -refcnt); 567 8241 Jeff } 568 8241 Jeff 569 8241 Jeff /* 570 8241 Jeff * Convert (or add) a space map into a reference tree. 571 8241 Jeff */ 572 8241 Jeff void 573 8241 Jeff space_map_ref_add_map(avl_tree_t *t, space_map_t *sm, int64_t refcnt) 574 8241 Jeff { 575 8241 Jeff space_seg_t *ss; 576 8241 Jeff 577 8241 Jeff ASSERT(MUTEX_HELD(sm->sm_lock)); 578 8241 Jeff 579 8241 Jeff for (ss = avl_first(&sm->sm_root); ss; ss = AVL_NEXT(&sm->sm_root, ss)) 580 8241 Jeff space_map_ref_add_seg(t, ss->ss_start, ss->ss_end, refcnt); 581 8241 Jeff } 582 8241 Jeff 583 8241 Jeff /* 584 8241 Jeff * Convert a reference tree into a space map. The space map will contain 585 8241 Jeff * all members of the reference tree for which refcnt >= minref. 586 8241 Jeff */ 587 8241 Jeff void 588 8241 Jeff space_map_ref_generate_map(avl_tree_t *t, space_map_t *sm, int64_t minref) 589 8241 Jeff { 590 8241 Jeff uint64_t start = -1ULL; 591 8241 Jeff int64_t refcnt = 0; 592 8241 Jeff space_ref_t *sr; 593 8241 Jeff 594 8241 Jeff ASSERT(MUTEX_HELD(sm->sm_lock)); 595 8241 Jeff 596 8241 Jeff space_map_vacate(sm, NULL, NULL); 597 8241 Jeff 598 8241 Jeff for (sr = avl_first(t); sr != NULL; sr = AVL_NEXT(t, sr)) { 599 8241 Jeff refcnt += sr->sr_refcnt; 600 8241 Jeff if (refcnt >= minref) { 601 8241 Jeff if (start == -1ULL) { 602 8241 Jeff start = sr->sr_offset; 603 8241 Jeff } 604 8241 Jeff } else { 605 8241 Jeff if (start != -1ULL) { 606 8241 Jeff uint64_t end = sr->sr_offset; 607 8241 Jeff ASSERT(start <= end); 608 8241 Jeff if (end > start) 609 8241 Jeff space_map_add(sm, start, end - start); 610 8241 Jeff start = -1ULL; 611 8241 Jeff } 612 8241 Jeff } 613 8241 Jeff } 614 8241 Jeff ASSERT(refcnt == 0); 615 8241 Jeff ASSERT(start == -1ULL); 616 8241 Jeff } 617
Indexes created Wed Nov 25 18:51:33 UTC 2009
Terms of Use |
Privacy |
Trademarks |
Copyright Policy |
Site Guidelines |
Help
Your use of this web site or any of its content or software indicates your agreement to be bound by these Terms of Use.
Copyright © 1995-2008 Sun Microsystems, Inc.