]>
Commit | Line | Data |
---|---|---|
34dc7c2f BB |
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 | |
1d3ba0bf | 9 | * or https://opensource.org/licenses/CDDL-1.0. |
34dc7c2f BB |
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 | /* | |
9babb374 | 22 | * Copyright 2009 Sun Microsystems, Inc. All rights reserved. |
34dc7c2f BB |
23 | * Use is subject to license terms. |
24 | */ | |
c99c9001 | 25 | /* |
93e28d66 | 26 | * Copyright (c) 2012, 2019 by Delphix. All rights reserved. |
c99c9001 | 27 | */ |
34dc7c2f | 28 | |
34dc7c2f BB |
29 | #include <sys/zfs_context.h> |
30 | #include <sys/spa.h> | |
31 | #include <sys/dmu.h> | |
93cf2076 GW |
32 | #include <sys/dmu_tx.h> |
33 | #include <sys/dnode.h> | |
34 | #include <sys/dsl_pool.h> | |
34dc7c2f BB |
35 | #include <sys/zio.h> |
36 | #include <sys/space_map.h> | |
93cf2076 | 37 | #include <sys/zfeature.h> |
34dc7c2f BB |
38 | |
39 | /* | |
d2734cce SD |
40 | * Note on space map block size: |
41 | * | |
96358617 | 42 | * The data for a given space map can be kept on blocks of any size. |
4d044c4c SD |
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 | |
96358617 | 45 | * when only a few blocks have changed since the last transaction group. |
34dc7c2f | 46 | */ |
34dc7c2f | 47 | |
4d044c4c SD |
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 | ||
3a549dc7 MA |
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 | ||
4d044c4c SD |
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 | ||
34dc7c2f | 81 | /* |
a1d477c2 | 82 | * Iterate through the space map, invoking the callback on each (non-debug) |
425d3237 | 83 | * space map entry. Stop after reading 'end' bytes of the space map. |
34dc7c2f BB |
84 | */ |
85 | int | |
425d3237 | 86 | space_map_iterate(space_map_t *sm, uint64_t end, sm_cb_t callback, void *arg) |
34dc7c2f | 87 | { |
425d3237 SD |
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))); | |
4d044c4c | 93 | |
425d3237 | 94 | dmu_prefetch(sm->sm_os, space_map_object(sm), 0, 0, end, |
4d044c4c SD |
95 | ZIO_PRIORITY_SYNC_READ); |
96 | ||
34dc7c2f | 97 | int error = 0; |
6774931d | 98 | uint64_t txg = 0, sync_pass = 0; |
425d3237 | 99 | for (uint64_t block_base = 0; block_base < end && error == 0; |
4d044c4c SD |
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); | |
34dc7c2f | 106 | |
4d044c4c | 107 | uint64_t *block_start = db->db_data; |
425d3237 | 108 | uint64_t block_length = MIN(end - block_base, blksz); |
4d044c4c SD |
109 | uint64_t *block_end = block_start + |
110 | (block_length / sizeof (uint64_t)); | |
34dc7c2f | 111 | |
4d044c4c SD |
112 | VERIFY0(P2PHASE(block_length, sizeof (uint64_t))); |
113 | VERIFY3U(block_length, !=, 0); | |
114 | ASSERT3U(blksz, ==, db->db_size); | |
34dc7c2f | 115 | |
4d044c4c SD |
116 | for (uint64_t *block_cursor = block_start; |
117 | block_cursor < block_end && error == 0; block_cursor++) { | |
118 | uint64_t e = *block_cursor; | |
34dc7c2f | 119 | |
6774931d MA |
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 | } | |
4d044c4c | 141 | continue; |
6774931d | 142 | } |
34dc7c2f | 143 | |
4d044c4c SD |
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 | } | |
34dc7c2f | 165 | |
4d044c4c SD |
166 | uint64_t entry_offset = (raw_offset << sm->sm_shift) + |
167 | sm->sm_start; | |
168 | uint64_t entry_run = raw_run << sm->sm_shift; | |
34dc7c2f | 169 | |
4d044c4c SD |
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); | |
34dc7c2f | 177 | |
4d044c4c SD |
178 | space_map_entry_t sme = { |
179 | .sme_type = type, | |
180 | .sme_vdev = vdev_id, | |
181 | .sme_offset = entry_offset, | |
6774931d MA |
182 | .sme_run = entry_run, |
183 | .sme_txg = txg, | |
184 | .sme_sync_pass = sync_pass | |
4d044c4c SD |
185 | }; |
186 | error = callback(&sme, arg); | |
187 | } | |
188 | dmu_buf_rele(db, FTAG); | |
189 | } | |
190 | return (error); | |
191 | } | |
34dc7c2f | 192 | |
4d044c4c SD |
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 = | |
425d3237 | 214 | sm->sm_phys->smp_length - sizeof (uint64_t); |
4d044c4c SD |
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); | |
93cf2076 | 219 | |
4d044c4c SD |
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 = | |
425d3237 | 227 | (sm->sm_phys->smp_length - db->db_offset) / sizeof (uint64_t); |
4d044c4c SD |
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--; | |
34dc7c2f BB |
255 | } |
256 | } | |
257 | ||
4d044c4c SD |
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); | |
a1d477c2 MA |
265 | return (error); |
266 | } | |
267 | ||
d2734cce SD |
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 | { | |
4d044c4c SD |
278 | uint64_t bufsz = MAX(sm->sm_blksz, SPA_MINBLOCKSIZE); |
279 | uint64_t *buf = zio_buf_alloc(bufsz); | |
d2734cce SD |
280 | |
281 | dmu_buf_will_dirty(sm->sm_dbuf, tx); | |
282 | ||
283 | /* | |
4d044c4c SD |
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]). | |
d2734cce | 290 | * |
4d044c4c SD |
291 | * As a result, we destroy its entries incrementally starting from |
292 | * the end after applying the callback to each of them. | |
d2734cce | 293 | * |
4d044c4c SD |
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]. | |
d2734cce | 311 | */ |
4d044c4c SD |
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); | |
d2734cce SD |
317 | if (error != 0) |
318 | break; | |
319 | ||
4d044c4c | 320 | ASSERT3U(nwords, <=, bufsz / sizeof (uint64_t)); |
d2734cce | 321 | |
4d044c4c SD |
322 | for (uint64_t i = 0; i < nwords; i++) { |
323 | uint64_t e = buf[i]; | |
d2734cce | 324 | |
4d044c4c | 325 | if (sm_entry_is_debug(e)) { |
425d3237 | 326 | sm->sm_phys->smp_length -= sizeof (uint64_t); |
d2734cce SD |
327 | continue; |
328 | } | |
329 | ||
4d044c4c SD |
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; | |
d2734cce SD |
358 | |
359 | VERIFY0(P2PHASE(entry_offset, 1ULL << sm->sm_shift)); | |
4d044c4c | 360 | VERIFY0(P2PHASE(entry_run, 1ULL << sm->sm_shift)); |
d2734cce | 361 | VERIFY3U(entry_offset, >=, sm->sm_start); |
4d044c4c SD |
362 | VERIFY3U(entry_offset, <, sm->sm_start + sm->sm_size); |
363 | VERIFY3U(entry_run, <=, sm->sm_size); | |
364 | VERIFY3U(entry_offset + entry_run, <=, | |
d2734cce SD |
365 | sm->sm_start + sm->sm_size); |
366 | ||
4d044c4c SD |
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); | |
d2734cce SD |
374 | if (error != 0) |
375 | break; | |
376 | ||
377 | if (type == SM_ALLOC) | |
4d044c4c | 378 | sm->sm_phys->smp_alloc -= entry_run; |
d2734cce | 379 | else |
4d044c4c | 380 | sm->sm_phys->smp_alloc += entry_run; |
425d3237 | 381 | sm->sm_phys->smp_length -= words * sizeof (uint64_t); |
d2734cce | 382 | } |
d2734cce SD |
383 | } |
384 | ||
4d044c4c | 385 | if (space_map_length(sm) == 0) { |
d2734cce | 386 | ASSERT0(error); |
425d3237 | 387 | ASSERT0(space_map_allocated(sm)); |
d2734cce SD |
388 | } |
389 | ||
4d044c4c | 390 | zio_buf_free(buf, bufsz); |
d2734cce SD |
391 | return (error); |
392 | } | |
393 | ||
a1d477c2 MA |
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 | |
4d044c4c | 401 | space_map_load_callback(space_map_entry_t *sme, void *arg) |
a1d477c2 MA |
402 | { |
403 | space_map_load_arg_t *smla = arg; | |
4d044c4c SD |
404 | if (sme->sme_type == smla->smla_type) { |
405 | VERIFY3U(range_tree_space(smla->smla_rt) + sme->sme_run, <=, | |
a1d477c2 | 406 | smla->smla_sm->sm_size); |
4d044c4c | 407 | range_tree_add(smla->smla_rt, sme->sme_offset, sme->sme_run); |
a1d477c2 | 408 | } else { |
4d044c4c | 409 | range_tree_remove(smla->smla_rt, sme->sme_offset, sme->sme_run); |
a1d477c2 MA |
410 | } |
411 | ||
412 | return (0); | |
413 | } | |
414 | ||
415 | /* | |
425d3237 SD |
416 | * Load the spacemap into the rangetree, like space_map_load. But only |
417 | * read the first 'length' bytes of the spacemap. | |
a1d477c2 MA |
418 | */ |
419 | int | |
425d3237 SD |
420 | space_map_load_length(space_map_t *sm, range_tree_t *rt, maptype_t maptype, |
421 | uint64_t length) | |
a1d477c2 | 422 | { |
a1d477c2 MA |
423 | space_map_load_arg_t smla; |
424 | ||
425 | VERIFY0(range_tree_space(rt)); | |
a1d477c2 | 426 | |
425d3237 | 427 | if (maptype == SM_FREE) |
a1d477c2 | 428 | range_tree_add(rt, sm->sm_start, sm->sm_size); |
a1d477c2 MA |
429 | |
430 | smla.smla_rt = rt; | |
431 | smla.smla_sm = sm; | |
432 | smla.smla_type = maptype; | |
425d3237 SD |
433 | int err = space_map_iterate(sm, length, |
434 | space_map_load_callback, &smla); | |
a1d477c2 | 435 | |
425d3237 | 436 | if (err != 0) |
93cf2076 | 437 | range_tree_vacate(rt, NULL, NULL); |
34dc7c2f | 438 | |
a1d477c2 | 439 | return (err); |
34dc7c2f BB |
440 | } |
441 | ||
425d3237 SD |
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 | ||
34dc7c2f | 452 | void |
93cf2076 | 453 | space_map_histogram_clear(space_map_t *sm) |
34dc7c2f | 454 | { |
93cf2076 GW |
455 | if (sm->sm_dbuf->db_size != sizeof (space_map_phys_t)) |
456 | return; | |
34dc7c2f | 457 | |
861166b0 AZ |
458 | memset(sm->sm_phys->smp_histogram, 0, |
459 | sizeof (sm->sm_phys->smp_histogram)); | |
93cf2076 | 460 | } |
34dc7c2f | 461 | |
93cf2076 GW |
462 | boolean_t |
463 | space_map_histogram_verify(space_map_t *sm, range_tree_t *rt) | |
464 | { | |
93cf2076 GW |
465 | /* |
466 | * Verify that the in-core range tree does not have any | |
467 | * ranges smaller than our sm_shift size. | |
468 | */ | |
1c27024e | 469 | for (int i = 0; i < sm->sm_shift; i++) { |
93cf2076 GW |
470 | if (rt->rt_histogram[i] != 0) |
471 | return (B_FALSE); | |
472 | } | |
473 | return (B_TRUE); | |
34dc7c2f BB |
474 | } |
475 | ||
93cf2076 GW |
476 | void |
477 | space_map_histogram_add(space_map_t *sm, range_tree_t *rt, dmu_tx_t *tx) | |
9babb374 | 478 | { |
93cf2076 | 479 | int idx = 0; |
93cf2076 | 480 | |
93cf2076 GW |
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)); | |
93cf2076 GW |
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 | */ | |
1c27024e | 498 | for (int i = sm->sm_shift; i < RANGE_TREE_HISTOGRAM_SIZE; i++) { |
93cf2076 GW |
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 | */ | |
f3a7f661 | 518 | if (idx < SPACE_MAP_HISTOGRAM_SIZE - 1) { |
93cf2076 GW |
519 | ASSERT3U(idx + sm->sm_shift, ==, i); |
520 | idx++; | |
f3a7f661 | 521 | ASSERT3U(idx, <, SPACE_MAP_HISTOGRAM_SIZE); |
93cf2076 GW |
522 | } |
523 | } | |
9babb374 BB |
524 | } |
525 | ||
4d044c4c SD |
526 | static void |
527 | space_map_write_intro_debug(space_map_t *sm, maptype_t maptype, dmu_tx_t *tx) | |
34dc7c2f | 528 | { |
4d044c4c SD |
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 | ||
425d3237 | 536 | dmu_write(sm->sm_os, space_map_object(sm), sm->sm_phys->smp_length, |
4d044c4c SD |
537 | sizeof (dentry), &dentry, tx); |
538 | ||
425d3237 | 539 | sm->sm_phys->smp_length += sizeof (dentry); |
4d044c4c SD |
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 | |
ca577779 PD |
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, | |
dd66857d | 552 | const void *tag, dmu_tx_t *tx) |
4d044c4c SD |
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); | |
34dc7c2f | 559 | |
93cf2076 | 560 | /* |
4d044c4c SD |
561 | * if this is a single word entry, ensure that no vdev was |
562 | * specified. | |
93cf2076 | 563 | */ |
4d044c4c SD |
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 + | |
425d3237 | 572 | (sm->sm_phys->smp_length - db->db_offset) / sizeof (uint64_t); |
4d044c4c SD |
573 | |
574 | ASSERT3P(block_cursor, <=, block_end); | |
575 | ||
ca577779 PD |
576 | uint64_t size = (rend - rstart) >> sm->sm_shift; |
577 | uint64_t start = (rstart - sm->sm_start) >> sm->sm_shift; | |
4d044c4c SD |
578 | uint64_t run_max = (words == 2) ? SM2_RUN_MAX : SM_RUN_MAX; |
579 | ||
ca577779 PD |
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); | |
4d044c4c SD |
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 | ||
425d3237 | 595 | uint64_t next_word_offset = sm->sm_phys->smp_length; |
4d044c4c SD |
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++; | |
425d3237 | 625 | sm->sm_phys->smp_length += sizeof (uint64_t); |
4d044c4c SD |
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 | } | |
425d3237 | 656 | sm->sm_phys->smp_length += words * sizeof (uint64_t); |
4d044c4c SD |
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 | ||
6d8da841 | 678 | #ifdef ZFS_DEBUG |
4d044c4c SD |
679 | /* |
680 | * We do this right after we write the intro debug entry | |
681 | * because the estimate does not take it into account. | |
682 | */ | |
425d3237 | 683 | uint64_t initial_objsize = sm->sm_phys->smp_length; |
4d044c4c SD |
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 | |
34dc7c2f | 688 | |
93cf2076 | 689 | /* |
4d044c4c SD |
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. | |
93cf2076 | 693 | */ |
425d3237 | 694 | uint64_t next_word_offset = sm->sm_phys->smp_length; |
4d044c4c SD |
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 | ||
ca577779 PD |
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; | |
4d044c4c SD |
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, | |
3a549dc7 MA |
717 | * or the vdev_id is set (meaning not equal to |
718 | * SM_NO_VDEVID). | |
4d044c4c SD |
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 && | |
29274c9f | 730 | random_in_range(100) == 0))) |
4d044c4c SD |
731 | words = 2; |
732 | ||
ca577779 PD |
733 | space_map_write_seg(sm, rs_get_start(rs, rt), rs_get_end(rs, |
734 | rt), maptype, vdev_id, words, &db, FTAG, tx); | |
93cf2076 | 735 | } |
4d044c4c SD |
736 | |
737 | dmu_buf_rele(db, FTAG); | |
738 | ||
6d8da841 | 739 | #ifdef ZFS_DEBUG |
4d044c4c SD |
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 | */ | |
425d3237 | 746 | ASSERT3U(estimated_final_objsize, >=, sm->sm_phys->smp_length); |
4d044c4c | 747 | #endif |
34dc7c2f BB |
748 | } |
749 | ||
4d044c4c SD |
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 | */ | |
34dc7c2f | 755 | void |
93cf2076 | 756 | space_map_write(space_map_t *sm, range_tree_t *rt, maptype_t maptype, |
4d044c4c | 757 | uint64_t vdev_id, dmu_tx_t *tx) |
34dc7c2f | 758 | { |
4d044c4c | 759 | ASSERT(dsl_pool_sync_context(dmu_objset_pool(sm->sm_os))); |
93cf2076 | 760 | VERIFY3U(space_map_object(sm), !=, 0); |
4d044c4c | 761 | |
93cf2076 | 762 | dmu_buf_will_dirty(sm->sm_dbuf, tx); |
34dc7c2f | 763 | |
93cf2076 GW |
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; | |
34dc7c2f | 770 | |
d2734cce | 771 | if (range_tree_is_empty(rt)) { |
93cf2076 GW |
772 | VERIFY3U(sm->sm_object, ==, sm->sm_phys->smp_object); |
773 | return; | |
774 | } | |
34dc7c2f BB |
775 | |
776 | if (maptype == SM_ALLOC) | |
93cf2076 | 777 | sm->sm_phys->smp_alloc += range_tree_space(rt); |
34dc7c2f | 778 | else |
93cf2076 | 779 | sm->sm_phys->smp_alloc -= range_tree_space(rt); |
34dc7c2f | 780 | |
ca577779 | 781 | uint64_t nodes = zfs_btree_numnodes(&rt->rt_root); |
4d044c4c | 782 | uint64_t rt_space = range_tree_space(rt); |
93cf2076 | 783 | |
4d044c4c | 784 | space_map_write_impl(sm, rt, maptype, vdev_id, tx); |
34dc7c2f | 785 | |
55d85d5a GW |
786 | /* |
787 | * Ensure that the space_map's accounting wasn't changed | |
788 | * while we were in the middle of writing it out. | |
789 | */ | |
ca577779 | 790 | VERIFY3U(nodes, ==, zfs_btree_numnodes(&rt->rt_root)); |
93cf2076 | 791 | VERIFY3U(range_tree_space(rt), ==, rt_space); |
34dc7c2f BB |
792 | } |
793 | ||
93cf2076 GW |
794 | static int |
795 | space_map_open_impl(space_map_t *sm) | |
34dc7c2f | 796 | { |
93cf2076 GW |
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); | |
34dc7c2f | 803 | |
93cf2076 GW |
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); | |
34dc7c2f | 807 | } |
fb5f0bc8 | 808 | |
93cf2076 GW |
809 | int |
810 | space_map_open(space_map_t **smp, objset_t *os, uint64_t object, | |
a1d477c2 | 811 | uint64_t start, uint64_t size, uint8_t shift) |
fb5f0bc8 | 812 | { |
93cf2076 GW |
813 | space_map_t *sm; |
814 | int error; | |
fb5f0bc8 | 815 | |
93cf2076 GW |
816 | ASSERT(*smp == NULL); |
817 | ASSERT(os != NULL); | |
818 | ASSERT(object != 0); | |
fb5f0bc8 | 819 | |
79c76d5b | 820 | sm = kmem_alloc(sizeof (space_map_t), KM_SLEEP); |
fb5f0bc8 | 821 | |
93cf2076 GW |
822 | sm->sm_start = start; |
823 | sm->sm_size = size; | |
824 | sm->sm_shift = shift; | |
93cf2076 GW |
825 | sm->sm_os = os; |
826 | sm->sm_object = object; | |
93cf2076 GW |
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 | } | |
93cf2076 GW |
836 | *smp = sm; |
837 | ||
838 | return (0); | |
fb5f0bc8 BB |
839 | } |
840 | ||
841 | void | |
93cf2076 | 842 | space_map_close(space_map_t *sm) |
fb5f0bc8 | 843 | { |
93cf2076 GW |
844 | if (sm == NULL) |
845 | return; | |
fb5f0bc8 | 846 | |
93cf2076 GW |
847 | if (sm->sm_dbuf != NULL) |
848 | dmu_buf_rele(sm->sm_dbuf, sm); | |
849 | sm->sm_dbuf = NULL; | |
850 | sm->sm_phys = NULL; | |
fb5f0bc8 | 851 | |
93cf2076 | 852 | kmem_free(sm, sizeof (*sm)); |
fb5f0bc8 BB |
853 | } |
854 | ||
fb5f0bc8 | 855 | void |
d2734cce | 856 | space_map_truncate(space_map_t *sm, int blocksize, dmu_tx_t *tx) |
fb5f0bc8 | 857 | { |
93cf2076 GW |
858 | objset_t *os = sm->sm_os; |
859 | spa_t *spa = dmu_objset_spa(os); | |
93cf2076 | 860 | dmu_object_info_t doi; |
93cf2076 GW |
861 | |
862 | ASSERT(dsl_pool_sync_context(dmu_objset_pool(os))); | |
863 | ASSERT(dmu_tx_is_syncing(tx)); | |
3b7f360c | 864 | VERIFY3U(dmu_tx_get_txg(tx), <=, spa_final_dirty_txg(spa)); |
93cf2076 | 865 | |
93cf2076 GW |
866 | dmu_object_info_from_db(sm->sm_dbuf, &doi); |
867 | ||
96358617 MA |
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)) || | |
3a549dc7 MA |
878 | doi.doi_data_block_size != blocksize || |
879 | doi.doi_metadata_block_size != 1 << space_map_ibs) { | |
a887d653 | 880 | zfs_dbgmsg("txg %llu, spa %s, sm %px, reallocating " |
8e739b2c RE |
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); | |
96358617 MA |
886 | |
887 | space_map_free(sm, tx); | |
888 | dmu_buf_rele(sm->sm_dbuf, sm); | |
889 | ||
d2734cce | 890 | sm->sm_object = space_map_alloc(sm->sm_os, blocksize, tx); |
96358617 MA |
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 | */ | |
861166b0 | 900 | memset(sm->sm_phys->smp_histogram, 0, |
96358617 | 901 | sizeof (sm->sm_phys->smp_histogram)); |
93cf2076 GW |
902 | } |
903 | ||
904 | dmu_buf_will_dirty(sm->sm_dbuf, tx); | |
425d3237 | 905 | sm->sm_phys->smp_length = 0; |
93cf2076 | 906 | sm->sm_phys->smp_alloc = 0; |
fb5f0bc8 BB |
907 | } |
908 | ||
93cf2076 | 909 | uint64_t |
d2734cce | 910 | space_map_alloc(objset_t *os, int blocksize, dmu_tx_t *tx) |
93cf2076 GW |
911 | { |
912 | spa_t *spa = dmu_objset_spa(os); | |
93cf2076 GW |
913 | uint64_t object; |
914 | int bonuslen; | |
915 | ||
fa86b5db MA |
916 | if (spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM)) { |
917 | spa_feature_incr(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM, tx); | |
93cf2076 GW |
918 | bonuslen = sizeof (space_map_phys_t); |
919 | ASSERT3U(bonuslen, <=, dmu_bonus_max()); | |
920 | } else { | |
921 | bonuslen = SPACE_MAP_SIZE_V0; | |
922 | } | |
923 | ||
3a549dc7 MA |
924 | object = dmu_object_alloc_ibs(os, DMU_OT_SPACE_MAP, blocksize, |
925 | space_map_ibs, DMU_OT_SPACE_MAP_HEADER, bonuslen, tx); | |
93cf2076 GW |
926 | |
927 | return (object); | |
fb5f0bc8 BB |
928 | } |
929 | ||
fb5f0bc8 | 930 | void |
a1d477c2 | 931 | space_map_free_obj(objset_t *os, uint64_t smobj, dmu_tx_t *tx) |
fb5f0bc8 | 932 | { |
a1d477c2 | 933 | spa_t *spa = dmu_objset_spa(os); |
fa86b5db | 934 | if (spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM)) { |
93cf2076 | 935 | dmu_object_info_t doi; |
fb5f0bc8 | 936 | |
a1d477c2 | 937 | VERIFY0(dmu_object_info(os, smobj, &doi)); |
93cf2076 | 938 | if (doi.doi_bonus_size != SPACE_MAP_SIZE_V0) { |
fa86b5db MA |
939 | spa_feature_decr(spa, |
940 | SPA_FEATURE_SPACEMAP_HISTOGRAM, tx); | |
fb5f0bc8 BB |
941 | } |
942 | } | |
93cf2076 | 943 | |
a1d477c2 MA |
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); | |
93cf2076 GW |
954 | sm->sm_object = 0; |
955 | } | |
956 | ||
4d044c4c SD |
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 | ||
93cf2076 GW |
1084 | uint64_t |
1085 | space_map_object(space_map_t *sm) | |
1086 | { | |
1087 | return (sm != NULL ? sm->sm_object : 0); | |
1088 | } | |
1089 | ||
425d3237 | 1090 | int64_t |
93cf2076 GW |
1091 | space_map_allocated(space_map_t *sm) |
1092 | { | |
425d3237 | 1093 | return (sm != NULL ? sm->sm_phys->smp_alloc : 0); |
93cf2076 GW |
1094 | } |
1095 | ||
93cf2076 GW |
1096 | uint64_t |
1097 | space_map_length(space_map_t *sm) | |
1098 | { | |
425d3237 | 1099 | return (sm != NULL ? sm->sm_phys->smp_length : 0); |
fb5f0bc8 | 1100 | } |
93e28d66 SD |
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 | } |