Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/contrib/openzfs/module/zfs/space_map.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /* 2 * CDDL HEADER START 3 * 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 https://opensource.org/licenses/CDDL-1.0. 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 * Copyright (c) 2012, 2019 by Delphix. All rights reserved. 27 */ 28 29 #include <sys/zfs_context.h> 30 #include <sys/spa.h> 31 #include <sys/dmu.h> 32 #include <sys/dmu_tx.h> 33 #include <sys/dnode.h> 34 #include <sys/dsl_pool.h> 35 #include <sys/zio.h> 36 #include <sys/space_map.h> 37 #include <sys/zfeature.h> 38 39 /* 40 * Note on space map block size: 41 * 42 * The data for a given space map can be kept on blocks of any size. 43 * Larger blocks entail fewer I/O operations, but they also cause the 44 * DMU to keep more data in-core, and also to waste more I/O bandwidth 45 * when only a few blocks have changed since the last transaction group. 46 */ 47 48 /* 49 * Enabled whenever we want to stress test the use of double-word 50 * space map entries. 51 */ 52 boolean_t zfs_force_some_double_word_sm_entries = B_FALSE; 53 54 /* 55 * Override the default indirect block size of 128K, instead use 16K for 56 * spacemaps (2^14 bytes). This dramatically reduces write inflation since 57 * appending to a spacemap typically has to write one data block (4KB) and one 58 * or two indirect blocks (16K-32K, rather than 128K). 59 */ 60 int space_map_ibs = 14; 61 62 boolean_t 63 sm_entry_is_debug(uint64_t e) 64 { 65 return (SM_PREFIX_DECODE(e) == SM_DEBUG_PREFIX); 66 } 67 68 boolean_t 69 sm_entry_is_single_word(uint64_t e) 70 { 71 uint8_t prefix = SM_PREFIX_DECODE(e); 72 return (prefix != SM_DEBUG_PREFIX && prefix != SM2_PREFIX); 73 } 74 75 boolean_t 76 sm_entry_is_double_word(uint64_t e) 77 { 78 return (SM_PREFIX_DECODE(e) == SM2_PREFIX); 79 } 80 81 /* 82 * Iterate through the space map, invoking the callback on each (non-debug) 83 * space map entry. Stop after reading 'end' bytes of the space map. 84 */ 85 int 86 space_map_iterate(space_map_t *sm, uint64_t end, sm_cb_t callback, void *arg) 87 { 88 uint64_t blksz = sm->sm_blksz; 89 90 ASSERT3U(blksz, !=, 0); 91 ASSERT3U(end, <=, space_map_length(sm)); 92 ASSERT0(P2PHASE(end, sizeof (uint64_t))); 93 94 dmu_prefetch(sm->sm_os, space_map_object(sm), 0, 0, end, 95 ZIO_PRIORITY_SYNC_READ); 96 97 int error = 0; 98 uint64_t txg = 0, sync_pass = 0; 99 for (uint64_t block_base = 0; block_base < end && error == 0; 100 block_base += blksz) { 101 dmu_buf_t *db; 102 error = dmu_buf_hold(sm->sm_os, space_map_object(sm), 103 block_base, FTAG, &db, DMU_READ_PREFETCH); 104 if (error != 0) 105 return (error); 106 107 uint64_t *block_start = db->db_data; 108 uint64_t block_length = MIN(end - block_base, blksz); 109 uint64_t *block_end = block_start + 110 (block_length / sizeof (uint64_t)); 111 112 VERIFY0(P2PHASE(block_length, sizeof (uint64_t))); 113 VERIFY3U(block_length, !=, 0); 114 ASSERT3U(blksz, ==, db->db_size); 115 116 for (uint64_t *block_cursor = block_start; 117 block_cursor < block_end && error == 0; block_cursor++) { 118 uint64_t e = *block_cursor; 119 120 if (sm_entry_is_debug(e)) { 121 /* 122 * Debug entries are only needed to record the 123 * current TXG and sync pass if available. 124 * 125 * Note though that sometimes there can be 126 * debug entries that are used as padding 127 * at the end of space map blocks in-order 128 * to not split a double-word entry in the 129 * middle between two blocks. These entries 130 * have their TXG field set to 0 and we 131 * skip them without recording the TXG. 132 * [see comment in space_map_write_seg()] 133 */ 134 uint64_t e_txg = SM_DEBUG_TXG_DECODE(e); 135 if (e_txg != 0) { 136 txg = e_txg; 137 sync_pass = SM_DEBUG_SYNCPASS_DECODE(e); 138 } else { 139 ASSERT0(SM_DEBUG_SYNCPASS_DECODE(e)); 140 } 141 continue; 142 } 143 144 uint64_t raw_offset, raw_run, vdev_id; 145 maptype_t type; 146 if (sm_entry_is_single_word(e)) { 147 type = SM_TYPE_DECODE(e); 148 vdev_id = SM_NO_VDEVID; 149 raw_offset = SM_OFFSET_DECODE(e); 150 raw_run = SM_RUN_DECODE(e); 151 } else { 152 /* it is a two-word entry */ 153 ASSERT(sm_entry_is_double_word(e)); 154 raw_run = SM2_RUN_DECODE(e); 155 vdev_id = SM2_VDEV_DECODE(e); 156 157 /* move on to the second word */ 158 block_cursor++; 159 e = *block_cursor; 160 VERIFY3P(block_cursor, <=, block_end); 161 162 type = SM2_TYPE_DECODE(e); 163 raw_offset = SM2_OFFSET_DECODE(e); 164 } 165 166 uint64_t entry_offset = (raw_offset << sm->sm_shift) + 167 sm->sm_start; 168 uint64_t entry_run = raw_run << sm->sm_shift; 169 170 VERIFY0(P2PHASE(entry_offset, 1ULL << sm->sm_shift)); 171 VERIFY0(P2PHASE(entry_run, 1ULL << sm->sm_shift)); 172 ASSERT3U(entry_offset, >=, sm->sm_start); 173 ASSERT3U(entry_offset, <, sm->sm_start + sm->sm_size); 174 ASSERT3U(entry_run, <=, sm->sm_size); 175 ASSERT3U(entry_offset + entry_run, <=, 176 sm->sm_start + sm->sm_size); 177 178 space_map_entry_t sme = { 179 .sme_type = type, 180 .sme_vdev = vdev_id, 181 .sme_offset = entry_offset, 182 .sme_run = entry_run, 183 .sme_txg = txg, 184 .sme_sync_pass = sync_pass 185 }; 186 error = callback(&sme, arg); 187 } 188 dmu_buf_rele(db, FTAG); 189 } 190 return (error); 191 } 192 193 /* 194 * Reads the entries from the last block of the space map into 195 * buf in reverse order. Populates nwords with number of words 196 * in the last block. 197 * 198 * Refer to block comment within space_map_incremental_destroy() 199 * to understand why this function is needed. 200 */ 201 static int 202 space_map_reversed_last_block_entries(space_map_t *sm, uint64_t *buf, 203 uint64_t bufsz, uint64_t *nwords) 204 { 205 int error = 0; 206 dmu_buf_t *db; 207 208 /* 209 * Find the offset of the last word in the space map and use 210 * that to read the last block of the space map with 211 * dmu_buf_hold(). 212 */ 213 uint64_t last_word_offset = 214 sm->sm_phys->smp_length - sizeof (uint64_t); 215 error = dmu_buf_hold(sm->sm_os, space_map_object(sm), last_word_offset, 216 FTAG, &db, DMU_READ_NO_PREFETCH); 217 if (error != 0) 218 return (error); 219 220 ASSERT3U(sm->sm_object, ==, db->db_object); 221 ASSERT3U(sm->sm_blksz, ==, db->db_size); 222 ASSERT3U(bufsz, >=, db->db_size); 223 ASSERT(nwords != NULL); 224 225 uint64_t *words = db->db_data; 226 *nwords = 227 (sm->sm_phys->smp_length - db->db_offset) / sizeof (uint64_t); 228 229 ASSERT3U(*nwords, <=, bufsz / sizeof (uint64_t)); 230 231 uint64_t n = *nwords; 232 uint64_t j = n - 1; 233 for (uint64_t i = 0; i < n; i++) { 234 uint64_t entry = words[i]; 235 if (sm_entry_is_double_word(entry)) { 236 /* 237 * Since we are populating the buffer backwards 238 * we have to be extra careful and add the two 239 * words of the double-word entry in the right 240 * order. 241 */ 242 ASSERT3U(j, >, 0); 243 buf[j - 1] = entry; 244 245 i++; 246 ASSERT3U(i, <, n); 247 entry = words[i]; 248 buf[j] = entry; 249 j -= 2; 250 } else { 251 ASSERT(sm_entry_is_debug(entry) || 252 sm_entry_is_single_word(entry)); 253 buf[j] = entry; 254 j--; 255 } 256 } 257 258 /* 259 * Assert that we wrote backwards all the 260 * way to the beginning of the buffer. 261 */ 262 ASSERT3S(j, ==, -1); 263 264 dmu_buf_rele(db, FTAG); 265 return (error); 266 } 267 268 /* 269 * Note: This function performs destructive actions - specifically 270 * it deletes entries from the end of the space map. Thus, callers 271 * should ensure that they are holding the appropriate locks for 272 * the space map that they provide. 273 */ 274 int 275 space_map_incremental_destroy(space_map_t *sm, sm_cb_t callback, void *arg, 276 dmu_tx_t *tx) 277 { 278 uint64_t bufsz = MAX(sm->sm_blksz, SPA_MINBLOCKSIZE); 279 uint64_t *buf = zio_buf_alloc(bufsz); 280 281 dmu_buf_will_dirty(sm->sm_dbuf, tx); 282 283 /* 284 * Ideally we would want to iterate from the beginning of the 285 * space map to the end in incremental steps. The issue with this 286 * approach is that we don't have any field on-disk that points 287 * us where to start between each step. We could try zeroing out 288 * entries that we've destroyed, but this doesn't work either as 289 * an entry that is 0 is a valid one (ALLOC for range [0x0:0x200]). 290 * 291 * As a result, we destroy its entries incrementally starting from 292 * the end after applying the callback to each of them. 293 * 294 * The problem with this approach is that we cannot literally 295 * iterate through the words in the space map backwards as we 296 * can't distinguish two-word space map entries from their second 297 * word. Thus we do the following: 298 * 299 * 1] We get all the entries from the last block of the space map 300 * and put them into a buffer in reverse order. This way the 301 * last entry comes first in the buffer, the second to last is 302 * second, etc. 303 * 2] We iterate through the entries in the buffer and we apply 304 * the callback to each one. As we move from entry to entry we 305 * we decrease the size of the space map, deleting effectively 306 * each entry. 307 * 3] If there are no more entries in the space map or the callback 308 * returns a value other than 0, we stop iterating over the 309 * space map. If there are entries remaining and the callback 310 * returned 0, we go back to step [1]. 311 */ 312 int error = 0; 313 while (space_map_length(sm) > 0 && error == 0) { 314 uint64_t nwords = 0; 315 error = space_map_reversed_last_block_entries(sm, buf, bufsz, 316 &nwords); 317 if (error != 0) 318 break; 319 320 ASSERT3U(nwords, <=, bufsz / sizeof (uint64_t)); 321 322 for (uint64_t i = 0; i < nwords; i++) { 323 uint64_t e = buf[i]; 324 325 if (sm_entry_is_debug(e)) { 326 sm->sm_phys->smp_length -= sizeof (uint64_t); 327 continue; 328 } 329 330 int words = 1; 331 uint64_t raw_offset, raw_run, vdev_id; 332 maptype_t type; 333 if (sm_entry_is_single_word(e)) { 334 type = SM_TYPE_DECODE(e); 335 vdev_id = SM_NO_VDEVID; 336 raw_offset = SM_OFFSET_DECODE(e); 337 raw_run = SM_RUN_DECODE(e); 338 } else { 339 ASSERT(sm_entry_is_double_word(e)); 340 words = 2; 341 342 raw_run = SM2_RUN_DECODE(e); 343 vdev_id = SM2_VDEV_DECODE(e); 344 345 /* move to the second word */ 346 i++; 347 e = buf[i]; 348 349 ASSERT3P(i, <=, nwords); 350 351 type = SM2_TYPE_DECODE(e); 352 raw_offset = SM2_OFFSET_DECODE(e); 353 } 354 355 uint64_t entry_offset = 356 (raw_offset << sm->sm_shift) + sm->sm_start; 357 uint64_t entry_run = raw_run << sm->sm_shift; 358 359 VERIFY0(P2PHASE(entry_offset, 1ULL << sm->sm_shift)); 360 VERIFY0(P2PHASE(entry_run, 1ULL << sm->sm_shift)); 361 VERIFY3U(entry_offset, >=, sm->sm_start); 362 VERIFY3U(entry_offset, <, sm->sm_start + sm->sm_size); 363 VERIFY3U(entry_run, <=, sm->sm_size); 364 VERIFY3U(entry_offset + entry_run, <=, 365 sm->sm_start + sm->sm_size); 366 367 space_map_entry_t sme = { 368 .sme_type = type, 369 .sme_vdev = vdev_id, 370 .sme_offset = entry_offset, 371 .sme_run = entry_run 372 }; 373 error = callback(&sme, arg); 374 if (error != 0) 375 break; 376 377 if (type == SM_ALLOC) 378 sm->sm_phys->smp_alloc -= entry_run; 379 else 380 sm->sm_phys->smp_alloc += entry_run; 381 sm->sm_phys->smp_length -= words * sizeof (uint64_t); 382 } 383 } 384 385 if (space_map_length(sm) == 0) { 386 ASSERT0(error); 387 ASSERT0(space_map_allocated(sm)); 388 } 389 390 zio_buf_free(buf, bufsz); 391 return (error); 392 } 393 394 typedef struct space_map_load_arg { 395 space_map_t *smla_sm; 396 range_tree_t *smla_rt; 397 maptype_t smla_type; 398 } space_map_load_arg_t; 399 400 static int 401 space_map_load_callback(space_map_entry_t *sme, void *arg) 402 { 403 space_map_load_arg_t *smla = arg; 404 if (sme->sme_type == smla->smla_type) { 405 VERIFY3U(range_tree_space(smla->smla_rt) + sme->sme_run, <=, 406 smla->smla_sm->sm_size); 407 range_tree_add(smla->smla_rt, sme->sme_offset, sme->sme_run); 408 } else { 409 range_tree_remove(smla->smla_rt, sme->sme_offset, sme->sme_run); 410 } 411 412 return (0); 413 } 414 415 /* 416 * Load the spacemap into the rangetree, like space_map_load. But only 417 * read the first 'length' bytes of the spacemap. 418 */ 419 int 420 space_map_load_length(space_map_t *sm, range_tree_t *rt, maptype_t maptype, 421 uint64_t length) 422 { 423 space_map_load_arg_t smla; 424 425 VERIFY0(range_tree_space(rt)); 426 427 if (maptype == SM_FREE) 428 range_tree_add(rt, sm->sm_start, sm->sm_size); 429 430 smla.smla_rt = rt; 431 smla.smla_sm = sm; 432 smla.smla_type = maptype; 433 int err = space_map_iterate(sm, length, 434 space_map_load_callback, &smla); 435 436 if (err != 0) 437 range_tree_vacate(rt, NULL, NULL); 438 439 return (err); 440 } 441 442 /* 443 * Load the space map disk into the specified range tree. Segments of maptype 444 * are added to the range tree, other segment types are removed. 445 */ 446 int 447 space_map_load(space_map_t *sm, range_tree_t *rt, maptype_t maptype) 448 { 449 return (space_map_load_length(sm, rt, maptype, space_map_length(sm))); 450 } 451 452 void 453 space_map_histogram_clear(space_map_t *sm) 454 { 455 if (sm->sm_dbuf->db_size != sizeof (space_map_phys_t)) 456 return; 457 458 memset(sm->sm_phys->smp_histogram, 0, 459 sizeof (sm->sm_phys->smp_histogram)); 460 } 461 462 boolean_t 463 space_map_histogram_verify(space_map_t *sm, range_tree_t *rt) 464 { 465 /* 466 * Verify that the in-core range tree does not have any 467 * ranges smaller than our sm_shift size. 468 */ 469 for (int i = 0; i < sm->sm_shift; i++) { 470 if (rt->rt_histogram[i] != 0) 471 return (B_FALSE); 472 } 473 return (B_TRUE); 474 } 475 476 void 477 space_map_histogram_add(space_map_t *sm, range_tree_t *rt, dmu_tx_t *tx) 478 { 479 int idx = 0; 480 481 ASSERT(dmu_tx_is_syncing(tx)); 482 VERIFY3U(space_map_object(sm), !=, 0); 483 484 if (sm->sm_dbuf->db_size != sizeof (space_map_phys_t)) 485 return; 486 487 dmu_buf_will_dirty(sm->sm_dbuf, tx); 488 489 ASSERT(space_map_histogram_verify(sm, rt)); 490 /* 491 * Transfer the content of the range tree histogram to the space 492 * map histogram. The space map histogram contains 32 buckets ranging 493 * between 2^sm_shift to 2^(32+sm_shift-1). The range tree, 494 * however, can represent ranges from 2^0 to 2^63. Since the space 495 * map only cares about allocatable blocks (minimum of sm_shift) we 496 * can safely ignore all ranges in the range tree smaller than sm_shift. 497 */ 498 for (int i = sm->sm_shift; i < RANGE_TREE_HISTOGRAM_SIZE; i++) { 499 500 /* 501 * Since the largest histogram bucket in the space map is 502 * 2^(32+sm_shift-1), we need to normalize the values in 503 * the range tree for any bucket larger than that size. For 504 * example given an sm_shift of 9, ranges larger than 2^40 505 * would get normalized as if they were 1TB ranges. Assume 506 * the range tree had a count of 5 in the 2^44 (16TB) bucket, 507 * the calculation below would normalize this to 5 * 2^4 (16). 508 */ 509 ASSERT3U(i, >=, idx + sm->sm_shift); 510 sm->sm_phys->smp_histogram[idx] += 511 rt->rt_histogram[i] << (i - idx - sm->sm_shift); 512 513 /* 514 * Increment the space map's index as long as we haven't 515 * reached the maximum bucket size. Accumulate all ranges 516 * larger than the max bucket size into the last bucket. 517 */ 518 if (idx < SPACE_MAP_HISTOGRAM_SIZE - 1) { 519 ASSERT3U(idx + sm->sm_shift, ==, i); 520 idx++; 521 ASSERT3U(idx, <, SPACE_MAP_HISTOGRAM_SIZE); 522 } 523 } 524 } 525 526 static void 527 space_map_write_intro_debug(space_map_t *sm, maptype_t maptype, dmu_tx_t *tx) 528 { 529 dmu_buf_will_dirty(sm->sm_dbuf, tx); 530 531 uint64_t dentry = SM_PREFIX_ENCODE(SM_DEBUG_PREFIX) | 532 SM_DEBUG_ACTION_ENCODE(maptype) | 533 SM_DEBUG_SYNCPASS_ENCODE(spa_sync_pass(tx->tx_pool->dp_spa)) | 534 SM_DEBUG_TXG_ENCODE(dmu_tx_get_txg(tx)); 535 536 dmu_write(sm->sm_os, space_map_object(sm), sm->sm_phys->smp_length, 537 sizeof (dentry), &dentry, tx); 538 539 sm->sm_phys->smp_length += sizeof (dentry); 540 } 541 542 /* 543 * Writes one or more entries given a segment. 544 * 545 * Note: The function may release the dbuf from the pointer initially 546 * passed to it, and return a different dbuf. Also, the space map's 547 * dbuf must be dirty for the changes in sm_phys to take effect. 548 */ 549 static void 550 space_map_write_seg(space_map_t *sm, uint64_t rstart, uint64_t rend, 551 maptype_t maptype, uint64_t vdev_id, uint8_t words, dmu_buf_t **dbp, 552 const void *tag, dmu_tx_t *tx) 553 { 554 ASSERT3U(words, !=, 0); 555 ASSERT3U(words, <=, 2); 556 557 /* ensure the vdev_id can be represented by the space map */ 558 ASSERT3U(vdev_id, <=, SM_NO_VDEVID); 559 560 /* 561 * if this is a single word entry, ensure that no vdev was 562 * specified. 563 */ 564 IMPLY(words == 1, vdev_id == SM_NO_VDEVID); 565 566 dmu_buf_t *db = *dbp; 567 ASSERT3U(db->db_size, ==, sm->sm_blksz); 568 569 uint64_t *block_base = db->db_data; 570 uint64_t *block_end = block_base + (sm->sm_blksz / sizeof (uint64_t)); 571 uint64_t *block_cursor = block_base + 572 (sm->sm_phys->smp_length - db->db_offset) / sizeof (uint64_t); 573 574 ASSERT3P(block_cursor, <=, block_end); 575 576 uint64_t size = (rend - rstart) >> sm->sm_shift; 577 uint64_t start = (rstart - sm->sm_start) >> sm->sm_shift; 578 uint64_t run_max = (words == 2) ? SM2_RUN_MAX : SM_RUN_MAX; 579 580 ASSERT3U(rstart, >=, sm->sm_start); 581 ASSERT3U(rstart, <, sm->sm_start + sm->sm_size); 582 ASSERT3U(rend - rstart, <=, sm->sm_size); 583 ASSERT3U(rend, <=, sm->sm_start + sm->sm_size); 584 585 while (size != 0) { 586 ASSERT3P(block_cursor, <=, block_end); 587 588 /* 589 * If we are at the end of this block, flush it and start 590 * writing again from the beginning. 591 */ 592 if (block_cursor == block_end) { 593 dmu_buf_rele(db, tag); 594 595 uint64_t next_word_offset = sm->sm_phys->smp_length; 596 VERIFY0(dmu_buf_hold(sm->sm_os, 597 space_map_object(sm), next_word_offset, 598 tag, &db, DMU_READ_PREFETCH)); 599 dmu_buf_will_dirty(db, tx); 600 601 /* update caller's dbuf */ 602 *dbp = db; 603 604 ASSERT3U(db->db_size, ==, sm->sm_blksz); 605 606 block_base = db->db_data; 607 block_cursor = block_base; 608 block_end = block_base + 609 (db->db_size / sizeof (uint64_t)); 610 } 611 612 /* 613 * If we are writing a two-word entry and we only have one 614 * word left on this block, just pad it with an empty debug 615 * entry and write the two-word entry in the next block. 616 */ 617 uint64_t *next_entry = block_cursor + 1; 618 if (next_entry == block_end && words > 1) { 619 ASSERT3U(words, ==, 2); 620 *block_cursor = SM_PREFIX_ENCODE(SM_DEBUG_PREFIX) | 621 SM_DEBUG_ACTION_ENCODE(0) | 622 SM_DEBUG_SYNCPASS_ENCODE(0) | 623 SM_DEBUG_TXG_ENCODE(0); 624 block_cursor++; 625 sm->sm_phys->smp_length += sizeof (uint64_t); 626 ASSERT3P(block_cursor, ==, block_end); 627 continue; 628 } 629 630 uint64_t run_len = MIN(size, run_max); 631 switch (words) { 632 case 1: 633 *block_cursor = SM_OFFSET_ENCODE(start) | 634 SM_TYPE_ENCODE(maptype) | 635 SM_RUN_ENCODE(run_len); 636 block_cursor++; 637 break; 638 case 2: 639 /* write the first word of the entry */ 640 *block_cursor = SM_PREFIX_ENCODE(SM2_PREFIX) | 641 SM2_RUN_ENCODE(run_len) | 642 SM2_VDEV_ENCODE(vdev_id); 643 block_cursor++; 644 645 /* move on to the second word of the entry */ 646 ASSERT3P(block_cursor, <, block_end); 647 *block_cursor = SM2_TYPE_ENCODE(maptype) | 648 SM2_OFFSET_ENCODE(start); 649 block_cursor++; 650 break; 651 default: 652 panic("%d-word space map entries are not supported", 653 words); 654 break; 655 } 656 sm->sm_phys->smp_length += words * sizeof (uint64_t); 657 658 start += run_len; 659 size -= run_len; 660 } 661 ASSERT0(size); 662 663 } 664 665 /* 666 * Note: The space map's dbuf must be dirty for the changes in sm_phys to 667 * take effect. 668 */ 669 static void 670 space_map_write_impl(space_map_t *sm, range_tree_t *rt, maptype_t maptype, 671 uint64_t vdev_id, dmu_tx_t *tx) 672 { 673 spa_t *spa = tx->tx_pool->dp_spa; 674 dmu_buf_t *db; 675 676 space_map_write_intro_debug(sm, maptype, tx); 677 678 #ifdef ZFS_DEBUG 679 /* 680 * We do this right after we write the intro debug entry 681 * because the estimate does not take it into account. 682 */ 683 uint64_t initial_objsize = sm->sm_phys->smp_length; 684 uint64_t estimated_growth = 685 space_map_estimate_optimal_size(sm, rt, SM_NO_VDEVID); 686 uint64_t estimated_final_objsize = initial_objsize + estimated_growth; 687 #endif 688 689 /* 690 * Find the offset right after the last word in the space map 691 * and use that to get a hold of the last block, so we can 692 * start appending to it. 693 */ 694 uint64_t next_word_offset = sm->sm_phys->smp_length; 695 VERIFY0(dmu_buf_hold(sm->sm_os, space_map_object(sm), 696 next_word_offset, FTAG, &db, DMU_READ_PREFETCH)); 697 ASSERT3U(db->db_size, ==, sm->sm_blksz); 698 699 dmu_buf_will_dirty(db, tx); 700 701 zfs_btree_t *t = &rt->rt_root; 702 zfs_btree_index_t where; 703 for (range_seg_t *rs = zfs_btree_first(t, &where); rs != NULL; 704 rs = zfs_btree_next(t, &where, &where)) { 705 uint64_t offset = (rs_get_start(rs, rt) - sm->sm_start) >> 706 sm->sm_shift; 707 uint64_t length = (rs_get_end(rs, rt) - rs_get_start(rs, rt)) >> 708 sm->sm_shift; 709 uint8_t words = 1; 710 711 /* 712 * We only write two-word entries when both of the following 713 * are true: 714 * 715 * [1] The feature is enabled. 716 * [2] The offset or run is too big for a single-word entry, 717 * or the vdev_id is set (meaning not equal to 718 * SM_NO_VDEVID). 719 * 720 * Note that for purposes of testing we've added the case that 721 * we write two-word entries occasionally when the feature is 722 * enabled and zfs_force_some_double_word_sm_entries has been 723 * set. 724 */ 725 if (spa_feature_is_active(spa, SPA_FEATURE_SPACEMAP_V2) && 726 (offset >= (1ULL << SM_OFFSET_BITS) || 727 length > SM_RUN_MAX || 728 vdev_id != SM_NO_VDEVID || 729 (zfs_force_some_double_word_sm_entries && 730 random_in_range(100) == 0))) 731 words = 2; 732 733 space_map_write_seg(sm, rs_get_start(rs, rt), rs_get_end(rs, 734 rt), maptype, vdev_id, words, &db, FTAG, tx); 735 } 736 737 dmu_buf_rele(db, FTAG); 738 739 #ifdef ZFS_DEBUG 740 /* 741 * We expect our estimation to be based on the worst case 742 * scenario [see comment in space_map_estimate_optimal_size()]. 743 * Therefore we expect the actual objsize to be equal or less 744 * than whatever we estimated it to be. 745 */ 746 ASSERT3U(estimated_final_objsize, >=, sm->sm_phys->smp_length); 747 #endif 748 } 749 750 /* 751 * Note: This function manipulates the state of the given space map but 752 * does not hold any locks implicitly. Thus the caller is responsible 753 * for synchronizing writes to the space map. 754 */ 755 void 756 space_map_write(space_map_t *sm, range_tree_t *rt, maptype_t maptype, 757 uint64_t vdev_id, dmu_tx_t *tx) 758 { 759 ASSERT(dsl_pool_sync_context(dmu_objset_pool(sm->sm_os))); 760 VERIFY3U(space_map_object(sm), !=, 0); 761 762 dmu_buf_will_dirty(sm->sm_dbuf, tx); 763 764 /* 765 * This field is no longer necessary since the in-core space map 766 * now contains the object number but is maintained for backwards 767 * compatibility. 768 */ 769 sm->sm_phys->smp_object = sm->sm_object; 770 771 if (range_tree_is_empty(rt)) { 772 VERIFY3U(sm->sm_object, ==, sm->sm_phys->smp_object); 773 return; 774 } 775 776 if (maptype == SM_ALLOC) 777 sm->sm_phys->smp_alloc += range_tree_space(rt); 778 else 779 sm->sm_phys->smp_alloc -= range_tree_space(rt); 780 781 uint64_t nodes = zfs_btree_numnodes(&rt->rt_root); 782 uint64_t rt_space = range_tree_space(rt); 783 784 space_map_write_impl(sm, rt, maptype, vdev_id, tx); 785 786 /* 787 * Ensure that the space_map's accounting wasn't changed 788 * while we were in the middle of writing it out. 789 */ 790 VERIFY3U(nodes, ==, zfs_btree_numnodes(&rt->rt_root)); 791 VERIFY3U(range_tree_space(rt), ==, rt_space); 792 } 793 794 static int 795 space_map_open_impl(space_map_t *sm) 796 { 797 int error; 798 u_longlong_t blocks; 799 800 error = dmu_bonus_hold(sm->sm_os, sm->sm_object, sm, &sm->sm_dbuf); 801 if (error) 802 return (error); 803 804 dmu_object_size_from_db(sm->sm_dbuf, &sm->sm_blksz, &blocks); 805 sm->sm_phys = sm->sm_dbuf->db_data; 806 return (0); 807 } 808 809 int 810 space_map_open(space_map_t **smp, objset_t *os, uint64_t object, 811 uint64_t start, uint64_t size, uint8_t shift) 812 { 813 space_map_t *sm; 814 int error; 815 816 ASSERT(*smp == NULL); 817 ASSERT(os != NULL); 818 ASSERT(object != 0); 819 820 sm = kmem_alloc(sizeof (space_map_t), KM_SLEEP); 821 822 sm->sm_start = start; 823 sm->sm_size = size; 824 sm->sm_shift = shift; 825 sm->sm_os = os; 826 sm->sm_object = object; 827 sm->sm_blksz = 0; 828 sm->sm_dbuf = NULL; 829 sm->sm_phys = NULL; 830 831 error = space_map_open_impl(sm); 832 if (error != 0) { 833 space_map_close(sm); 834 return (error); 835 } 836 *smp = sm; 837 838 return (0); 839 } 840 841 void 842 space_map_close(space_map_t *sm) 843 { 844 if (sm == NULL) 845 return; 846 847 if (sm->sm_dbuf != NULL) 848 dmu_buf_rele(sm->sm_dbuf, sm); 849 sm->sm_dbuf = NULL; 850 sm->sm_phys = NULL; 851 852 kmem_free(sm, sizeof (*sm)); 853 } 854 855 void 856 space_map_truncate(space_map_t *sm, int blocksize, dmu_tx_t *tx) 857 { 858 objset_t *os = sm->sm_os; 859 spa_t *spa = dmu_objset_spa(os); 860 dmu_object_info_t doi; 861 862 ASSERT(dsl_pool_sync_context(dmu_objset_pool(os))); 863 ASSERT(dmu_tx_is_syncing(tx)); 864 VERIFY3U(dmu_tx_get_txg(tx), <=, spa_final_dirty_txg(spa)); 865 866 dmu_object_info_from_db(sm->sm_dbuf, &doi); 867 868 /* 869 * If the space map has the wrong bonus size (because 870 * SPA_FEATURE_SPACEMAP_HISTOGRAM has recently been enabled), or 871 * the wrong block size (because space_map_blksz has changed), 872 * free and re-allocate its object with the updated sizes. 873 * 874 * Otherwise, just truncate the current object. 875 */ 876 if ((spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM) && 877 doi.doi_bonus_size != sizeof (space_map_phys_t)) || 878 doi.doi_data_block_size != blocksize || 879 doi.doi_metadata_block_size != 1 << space_map_ibs) { 880 zfs_dbgmsg("txg %llu, spa %s, sm %px, reallocating " 881 "object[%llu]: old bonus %llu, old blocksz %u", 882 (u_longlong_t)dmu_tx_get_txg(tx), spa_name(spa), sm, 883 (u_longlong_t)sm->sm_object, 884 (u_longlong_t)doi.doi_bonus_size, 885 doi.doi_data_block_size); 886 887 space_map_free(sm, tx); 888 dmu_buf_rele(sm->sm_dbuf, sm); 889 890 sm->sm_object = space_map_alloc(sm->sm_os, blocksize, tx); 891 VERIFY0(space_map_open_impl(sm)); 892 } else { 893 VERIFY0(dmu_free_range(os, space_map_object(sm), 0, -1ULL, tx)); 894 895 /* 896 * If the spacemap is reallocated, its histogram 897 * will be reset. Do the same in the common case so that 898 * bugs related to the uncommon case do not go unnoticed. 899 */ 900 memset(sm->sm_phys->smp_histogram, 0, 901 sizeof (sm->sm_phys->smp_histogram)); 902 } 903 904 dmu_buf_will_dirty(sm->sm_dbuf, tx); 905 sm->sm_phys->smp_length = 0; 906 sm->sm_phys->smp_alloc = 0; 907 } 908 909 uint64_t 910 space_map_alloc(objset_t *os, int blocksize, dmu_tx_t *tx) 911 { 912 spa_t *spa = dmu_objset_spa(os); 913 uint64_t object; 914 int bonuslen; 915 916 if (spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM)) { 917 spa_feature_incr(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM, tx); 918 bonuslen = sizeof (space_map_phys_t); 919 ASSERT3U(bonuslen, <=, dmu_bonus_max()); 920 } else { 921 bonuslen = SPACE_MAP_SIZE_V0; 922 } 923 924 object = dmu_object_alloc_ibs(os, DMU_OT_SPACE_MAP, blocksize, 925 space_map_ibs, DMU_OT_SPACE_MAP_HEADER, bonuslen, tx); 926 927 return (object); 928 } 929 930 void 931 space_map_free_obj(objset_t *os, uint64_t smobj, dmu_tx_t *tx) 932 { 933 spa_t *spa = dmu_objset_spa(os); 934 if (spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM)) { 935 dmu_object_info_t doi; 936 937 VERIFY0(dmu_object_info(os, smobj, &doi)); 938 if (doi.doi_bonus_size != SPACE_MAP_SIZE_V0) { 939 spa_feature_decr(spa, 940 SPA_FEATURE_SPACEMAP_HISTOGRAM, tx); 941 } 942 } 943 944 VERIFY0(dmu_object_free(os, smobj, tx)); 945 } 946 947 void 948 space_map_free(space_map_t *sm, dmu_tx_t *tx) 949 { 950 if (sm == NULL) 951 return; 952 953 space_map_free_obj(sm->sm_os, space_map_object(sm), tx); 954 sm->sm_object = 0; 955 } 956 957 /* 958 * Given a range tree, it makes a worst-case estimate of how much 959 * space would the tree's segments take if they were written to 960 * the given space map. 961 */ 962 uint64_t 963 space_map_estimate_optimal_size(space_map_t *sm, range_tree_t *rt, 964 uint64_t vdev_id) 965 { 966 spa_t *spa = dmu_objset_spa(sm->sm_os); 967 uint64_t shift = sm->sm_shift; 968 uint64_t *histogram = rt->rt_histogram; 969 uint64_t entries_for_seg = 0; 970 971 /* 972 * In order to get a quick estimate of the optimal size that this 973 * range tree would have on-disk as a space map, we iterate through 974 * its histogram buckets instead of iterating through its nodes. 975 * 976 * Note that this is a highest-bound/worst-case estimate for the 977 * following reasons: 978 * 979 * 1] We assume that we always add a debug padding for each block 980 * we write and we also assume that we start at the last word 981 * of a block attempting to write a two-word entry. 982 * 2] Rounding up errors due to the way segments are distributed 983 * in the buckets of the range tree's histogram. 984 * 3] The activation of zfs_force_some_double_word_sm_entries 985 * (tunable) when testing. 986 * 987 * = Math and Rounding Errors = 988 * 989 * rt_histogram[i] bucket of a range tree represents the number 990 * of entries in [2^i, (2^(i+1))-1] of that range_tree. Given 991 * that, we want to divide the buckets into groups: Buckets that 992 * can be represented using a single-word entry, ones that can 993 * be represented with a double-word entry, and ones that can 994 * only be represented with multiple two-word entries. 995 * 996 * [Note that if the new encoding feature is not enabled there 997 * are only two groups: single-word entry buckets and multiple 998 * single-word entry buckets. The information below assumes 999 * two-word entries enabled, but it can easily applied when 1000 * the feature is not enabled] 1001 * 1002 * To find the highest bucket that can be represented with a 1003 * single-word entry we look at the maximum run that such entry 1004 * can have, which is 2^(SM_RUN_BITS + sm_shift) [remember that 1005 * the run of a space map entry is shifted by sm_shift, thus we 1006 * add it to the exponent]. This way, excluding the value of the 1007 * maximum run that can be represented by a single-word entry, 1008 * all runs that are smaller exist in buckets 0 to 1009 * SM_RUN_BITS + shift - 1. 1010 * 1011 * To find the highest bucket that can be represented with a 1012 * double-word entry, we follow the same approach. Finally, any 1013 * bucket higher than that are represented with multiple two-word 1014 * entries. To be more specific, if the highest bucket whose 1015 * segments can be represented with a single two-word entry is X, 1016 * then bucket X+1 will need 2 two-word entries for each of its 1017 * segments, X+2 will need 4, X+3 will need 8, ...etc. 1018 * 1019 * With all of the above we make our estimation based on bucket 1020 * groups. There is a rounding error though. As we mentioned in 1021 * the example with the one-word entry, the maximum run that can 1022 * be represented in a one-word entry 2^(SM_RUN_BITS + shift) is 1023 * not part of bucket SM_RUN_BITS + shift - 1. Thus, segments of 1024 * that length fall into the next bucket (and bucket group) where 1025 * we start counting two-word entries and this is one more reason 1026 * why the estimated size may end up being bigger than the actual 1027 * size written. 1028 */ 1029 uint64_t size = 0; 1030 uint64_t idx = 0; 1031 1032 if (!spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_V2) || 1033 (vdev_id == SM_NO_VDEVID && sm->sm_size < SM_OFFSET_MAX)) { 1034 1035 /* 1036 * If we are trying to force some double word entries just 1037 * assume the worst-case of every single word entry being 1038 * written as a double word entry. 1039 */ 1040 uint64_t entry_size = 1041 (spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_V2) && 1042 zfs_force_some_double_word_sm_entries) ? 1043 (2 * sizeof (uint64_t)) : sizeof (uint64_t); 1044 1045 uint64_t single_entry_max_bucket = SM_RUN_BITS + shift - 1; 1046 for (; idx <= single_entry_max_bucket; idx++) 1047 size += histogram[idx] * entry_size; 1048 1049 if (!spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_V2)) { 1050 for (; idx < RANGE_TREE_HISTOGRAM_SIZE; idx++) { 1051 ASSERT3U(idx, >=, single_entry_max_bucket); 1052 entries_for_seg = 1053 1ULL << (idx - single_entry_max_bucket); 1054 size += histogram[idx] * 1055 entries_for_seg * entry_size; 1056 } 1057 return (size); 1058 } 1059 } 1060 1061 ASSERT(spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_V2)); 1062 1063 uint64_t double_entry_max_bucket = SM2_RUN_BITS + shift - 1; 1064 for (; idx <= double_entry_max_bucket; idx++) 1065 size += histogram[idx] * 2 * sizeof (uint64_t); 1066 1067 for (; idx < RANGE_TREE_HISTOGRAM_SIZE; idx++) { 1068 ASSERT3U(idx, >=, double_entry_max_bucket); 1069 entries_for_seg = 1ULL << (idx - double_entry_max_bucket); 1070 size += histogram[idx] * 1071 entries_for_seg * 2 * sizeof (uint64_t); 1072 } 1073 1074 /* 1075 * Assume the worst case where we start with the padding at the end 1076 * of the current block and we add an extra padding entry at the end 1077 * of all subsequent blocks. 1078 */ 1079 size += ((size / sm->sm_blksz) + 1) * sizeof (uint64_t); 1080 1081 return (size); 1082 } 1083 1084 uint64_t 1085 space_map_object(space_map_t *sm) 1086 { 1087 return (sm != NULL ? sm->sm_object : 0); 1088 } 1089 1090 int64_t 1091 space_map_allocated(space_map_t *sm) 1092 { 1093 return (sm != NULL ? sm->sm_phys->smp_alloc : 0); 1094 } 1095 1096 uint64_t 1097 space_map_length(space_map_t *sm) 1098 { 1099 return (sm != NULL ? sm->sm_phys->smp_length : 0); 1100 } 1101 1102 uint64_t 1103 space_map_nblocks(space_map_t *sm) 1104 { 1105 if (sm == NULL) 1106 return (0); 1107 return (DIV_ROUND_UP(space_map_length(sm), sm->sm_blksz)); 1108 }
Cache object: d2b3366741817cba690b6c074beb0863
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]