4 * This file and its contents are supplied under the terms of the
5 * Common Development and Distribution License ("CDDL"), version 1.0.
6 * You may only use this file in accordance with the terms of version
9 * A full copy of the text of the CDDL should have accompanied this
10 * source. A copy of the CDDL is also available via the Internet at
11 * http://www.illumos.org/license/CDDL.
17 * Copyright (c) 2015 by Delphix. All rights reserved.
20 #include <sys/dmu_tx.h>
21 #include <sys/dsl_pool.h>
23 #include <sys/vdev_impl.h>
24 #include <sys/vdev_indirect_mapping.h>
25 #include <sys/zfeature.h>
26 #include <sys/dmu_objset.h>
30 vdev_indirect_mapping_verify(vdev_indirect_mapping_t *vim)
34 ASSERT(vim->vim_object != 0);
35 ASSERT(vim->vim_objset != NULL);
36 ASSERT(vim->vim_phys != NULL);
37 ASSERT(vim->vim_dbuf != NULL);
39 EQUIV(vim->vim_phys->vimp_num_entries > 0,
40 vim->vim_entries != NULL);
41 if (vim->vim_phys->vimp_num_entries > 0) {
42 ASSERTV(vdev_indirect_mapping_entry_phys_t *last_entry =
43 &vim->vim_entries[vim->vim_phys->vimp_num_entries - 1]);
44 ASSERTV(uint64_t offset =
45 DVA_MAPPING_GET_SRC_OFFSET(last_entry));
46 ASSERTV(uint64_t size = DVA_GET_ASIZE(&last_entry->vimep_dst));
48 ASSERT3U(vim->vim_phys->vimp_max_offset, >=, offset + size);
50 if (vim->vim_havecounts) {
51 ASSERT(vim->vim_phys->vimp_counts_object != 0);
59 vdev_indirect_mapping_num_entries(vdev_indirect_mapping_t *vim)
61 ASSERT(vdev_indirect_mapping_verify(vim));
63 return (vim->vim_phys->vimp_num_entries);
67 vdev_indirect_mapping_max_offset(vdev_indirect_mapping_t *vim)
69 ASSERT(vdev_indirect_mapping_verify(vim));
71 return (vim->vim_phys->vimp_max_offset);
75 vdev_indirect_mapping_object(vdev_indirect_mapping_t *vim)
77 ASSERT(vdev_indirect_mapping_verify(vim));
79 return (vim->vim_object);
83 vdev_indirect_mapping_bytes_mapped(vdev_indirect_mapping_t *vim)
85 ASSERT(vdev_indirect_mapping_verify(vim));
87 return (vim->vim_phys->vimp_bytes_mapped);
91 * The length (in bytes) of the mapping object array in memory and
92 * (logically) on disk.
94 * Note that unlike most of our accessor functions,
95 * we don't assert that the struct is consistent; therefore it can be
96 * called while there may be concurrent changes, if we don't care about
97 * the value being immediately stale (e.g. from spa_removal_get_stats()).
100 vdev_indirect_mapping_size(vdev_indirect_mapping_t *vim)
102 return (vim->vim_phys->vimp_num_entries * sizeof (*vim->vim_entries));
106 * Compare an offset with an indirect mapping entry; there are three
107 * possible scenarios:
109 * 1. The offset is "less than" the mapping entry; meaning the
110 * offset is less than the source offset of the mapping entry. In
111 * this case, there is no overlap between the offset and the
112 * mapping entry and -1 will be returned.
114 * 2. The offset is "greater than" the mapping entry; meaning the
115 * offset is greater than the mapping entry's source offset plus
116 * the entry's size. In this case, there is no overlap between
117 * the offset and the mapping entry and 1 will be returned.
119 * NOTE: If the offset is actually equal to the entry's offset
120 * plus size, this is considered to be "greater" than the entry,
121 * and this case applies (i.e. 1 will be returned). Thus, the
122 * entry's "range" can be considered to be inclusive at its
123 * start, but exclusive at its end: e.g. [src, src + size).
125 * 3. The last case to consider is if the offset actually falls
126 * within the mapping entry's range. If this is the case, the
127 * offset is considered to be "equal to" the mapping entry and
128 * 0 will be returned.
130 * NOTE: If the offset is equal to the entry's source offset,
131 * this case applies and 0 will be returned. If the offset is
132 * equal to the entry's source plus its size, this case does
133 * *not* apply (see "NOTE" above for scenario 2), and 1 will be
137 dva_mapping_overlap_compare(const void *v_key, const void *v_array_elem)
139 const uint64_t *key = v_key;
140 const vdev_indirect_mapping_entry_phys_t *array_elem =
142 uint64_t src_offset = DVA_MAPPING_GET_SRC_OFFSET(array_elem);
144 if (*key < src_offset) {
146 } else if (*key < src_offset + DVA_GET_ASIZE(&array_elem->vimep_dst)) {
154 * Returns the mapping entry for the given offset.
156 * It's possible that the given offset will not be in the mapping table
157 * (i.e. no mapping entries contain this offset), in which case, the
158 * return value value depends on the "next_if_missing" parameter.
160 * If the offset is not found in the table and "next_if_missing" is
161 * B_FALSE, then NULL will always be returned. The behavior is intended
162 * to allow consumers to get the entry corresponding to the offset
163 * parameter, iff the offset overlaps with an entry in the table.
165 * If the offset is not found in the table and "next_if_missing" is
166 * B_TRUE, then the entry nearest to the given offset will be returned,
167 * such that the entry's source offset is greater than the offset
168 * passed in (i.e. the "next" mapping entry in the table is returned, if
169 * the offset is missing from the table). If there are no entries whose
170 * source offset is greater than the passed in offset, NULL is returned.
172 static vdev_indirect_mapping_entry_phys_t *
173 vdev_indirect_mapping_entry_for_offset_impl(vdev_indirect_mapping_t *vim,
174 uint64_t offset, boolean_t next_if_missing)
176 ASSERT(vdev_indirect_mapping_verify(vim));
177 ASSERT(vim->vim_phys->vimp_num_entries > 0);
179 vdev_indirect_mapping_entry_phys_t *entry = NULL;
181 uint64_t last = vim->vim_phys->vimp_num_entries - 1;
185 * We don't define these inside of the while loop because we use
186 * their value in the case that offset isn't in the mapping.
191 while (last >= base) {
192 mid = base + ((last - base) >> 1);
194 result = dva_mapping_overlap_compare(&offset,
195 &vim->vim_entries[mid]);
198 entry = &vim->vim_entries[mid];
200 } else if (result < 0) {
207 if (entry == NULL && next_if_missing) {
208 ASSERT3U(base, ==, last + 1);
209 ASSERT(mid == base || mid == last);
210 ASSERT3S(result, !=, 0);
213 * The offset we're looking for isn't actually contained
214 * in the mapping table, thus we need to return the
215 * closest mapping entry that is greater than the
216 * offset. We reuse the result of the last comparison,
217 * comparing the mapping entry at index "mid" and the
218 * offset. The offset is guaranteed to lie between
219 * indices one less than "mid", and one greater than
220 * "mid"; we just need to determine if offset is greater
221 * than, or less than the mapping entry contained at
231 ASSERT3U(index, <=, vim->vim_phys->vimp_num_entries);
233 if (index == vim->vim_phys->vimp_num_entries) {
235 * If "index" is past the end of the entries
236 * array, then not only is the offset not in the
237 * mapping table, but it's actually greater than
238 * all entries in the table. In this case, we
239 * can't return a mapping entry greater than the
240 * offset (since none exist), so we return NULL.
243 ASSERT3S(dva_mapping_overlap_compare(&offset,
244 &vim->vim_entries[index - 1]), >, 0);
249 * Just to be safe, we verify the offset falls
250 * in between the mapping entries at index and
251 * one less than index. Since we know the offset
252 * doesn't overlap an entry, and we're supposed
253 * to return the entry just greater than the
254 * offset, both of the following tests must be
257 ASSERT3S(dva_mapping_overlap_compare(&offset,
258 &vim->vim_entries[index]), <, 0);
259 IMPLY(index >= 1, dva_mapping_overlap_compare(&offset,
260 &vim->vim_entries[index - 1]) > 0);
262 return (&vim->vim_entries[index]);
269 vdev_indirect_mapping_entry_phys_t *
270 vdev_indirect_mapping_entry_for_offset(vdev_indirect_mapping_t *vim,
273 return (vdev_indirect_mapping_entry_for_offset_impl(vim, offset,
277 vdev_indirect_mapping_entry_phys_t *
278 vdev_indirect_mapping_entry_for_offset_or_next(vdev_indirect_mapping_t *vim,
281 return (vdev_indirect_mapping_entry_for_offset_impl(vim, offset,
287 vdev_indirect_mapping_close(vdev_indirect_mapping_t *vim)
289 ASSERT(vdev_indirect_mapping_verify(vim));
291 if (vim->vim_phys->vimp_num_entries > 0) {
292 uint64_t map_size = vdev_indirect_mapping_size(vim);
293 vmem_free(vim->vim_entries, map_size);
294 vim->vim_entries = NULL;
297 dmu_buf_rele(vim->vim_dbuf, vim);
299 vim->vim_objset = NULL;
301 vim->vim_dbuf = NULL;
302 vim->vim_phys = NULL;
304 kmem_free(vim, sizeof (*vim));
308 vdev_indirect_mapping_alloc(objset_t *os, dmu_tx_t *tx)
311 ASSERT(dmu_tx_is_syncing(tx));
312 uint64_t bonus_size = VDEV_INDIRECT_MAPPING_SIZE_V0;
314 if (spa_feature_is_enabled(os->os_spa, SPA_FEATURE_OBSOLETE_COUNTS)) {
315 bonus_size = sizeof (vdev_indirect_mapping_phys_t);
318 object = dmu_object_alloc(os,
319 DMU_OTN_UINT64_METADATA, SPA_OLD_MAXBLOCKSIZE,
320 DMU_OTN_UINT64_METADATA, bonus_size,
323 if (spa_feature_is_enabled(os->os_spa, SPA_FEATURE_OBSOLETE_COUNTS)) {
325 vdev_indirect_mapping_phys_t *vimp;
327 VERIFY0(dmu_bonus_hold(os, object, FTAG, &dbuf));
328 dmu_buf_will_dirty(dbuf, tx);
329 vimp = dbuf->db_data;
330 vimp->vimp_counts_object = dmu_object_alloc(os,
331 DMU_OTN_UINT32_METADATA, SPA_OLD_MAXBLOCKSIZE,
333 spa_feature_incr(os->os_spa, SPA_FEATURE_OBSOLETE_COUNTS, tx);
334 dmu_buf_rele(dbuf, FTAG);
341 vdev_indirect_mapping_t *
342 vdev_indirect_mapping_open(objset_t *os, uint64_t mapping_object)
344 vdev_indirect_mapping_t *vim = kmem_zalloc(sizeof (*vim), KM_SLEEP);
345 dmu_object_info_t doi;
346 VERIFY0(dmu_object_info(os, mapping_object, &doi));
348 vim->vim_objset = os;
349 vim->vim_object = mapping_object;
351 VERIFY0(dmu_bonus_hold(os, vim->vim_object, vim,
353 vim->vim_phys = vim->vim_dbuf->db_data;
355 vim->vim_havecounts =
356 (doi.doi_bonus_size > VDEV_INDIRECT_MAPPING_SIZE_V0);
358 if (vim->vim_phys->vimp_num_entries > 0) {
359 uint64_t map_size = vdev_indirect_mapping_size(vim);
360 vim->vim_entries = vmem_alloc(map_size, KM_SLEEP);
361 VERIFY0(dmu_read(os, vim->vim_object, 0, map_size,
362 vim->vim_entries, DMU_READ_PREFETCH));
365 ASSERT(vdev_indirect_mapping_verify(vim));
371 vdev_indirect_mapping_free(objset_t *os, uint64_t object, dmu_tx_t *tx)
373 vdev_indirect_mapping_t *vim = vdev_indirect_mapping_open(os, object);
374 if (vim->vim_havecounts) {
375 VERIFY0(dmu_object_free(os, vim->vim_phys->vimp_counts_object,
377 spa_feature_decr(os->os_spa, SPA_FEATURE_OBSOLETE_COUNTS, tx);
379 vdev_indirect_mapping_close(vim);
381 VERIFY0(dmu_object_free(os, object, tx));
385 * Append the list of vdev_indirect_mapping_entry_t's to the on-disk
386 * mapping object. Also remove the entries from the list and free them.
387 * This also implicitly extends the max_offset of the mapping (to the end
388 * of the last entry).
391 vdev_indirect_mapping_add_entries(vdev_indirect_mapping_t *vim,
392 list_t *list, dmu_tx_t *tx)
394 vdev_indirect_mapping_entry_phys_t *mapbuf;
396 uint32_t *countbuf = NULL;
397 vdev_indirect_mapping_entry_phys_t *old_entries;
399 uint64_t entries_written = 0;
401 ASSERT(vdev_indirect_mapping_verify(vim));
402 ASSERT(dmu_tx_is_syncing(tx));
403 ASSERT(dsl_pool_sync_context(dmu_tx_pool(tx)));
404 ASSERT(!list_is_empty(list));
406 old_size = vdev_indirect_mapping_size(vim);
407 old_entries = vim->vim_entries;
408 old_count = vim->vim_phys->vimp_num_entries;
410 dmu_buf_will_dirty(vim->vim_dbuf, tx);
412 mapbuf = vmem_alloc(SPA_OLD_MAXBLOCKSIZE, KM_SLEEP);
413 if (vim->vim_havecounts) {
414 countbuf = vmem_alloc(SPA_OLD_MAXBLOCKSIZE, KM_SLEEP);
415 ASSERT(spa_feature_is_active(vim->vim_objset->os_spa,
416 SPA_FEATURE_OBSOLETE_COUNTS));
418 while (!list_is_empty(list)) {
421 * Write entries from the list to the
422 * vdev_im_object in batches of size SPA_OLD_MAXBLOCKSIZE.
424 for (i = 0; i < SPA_OLD_MAXBLOCKSIZE / sizeof (*mapbuf); i++) {
425 vdev_indirect_mapping_entry_t *entry =
426 list_remove_head(list);
431 DVA_GET_ASIZE(&entry->vime_mapping.vimep_dst);
432 uint64_t src_offset =
433 DVA_MAPPING_GET_SRC_OFFSET(&entry->vime_mapping);
436 * We shouldn't be adding an entry which is fully
439 ASSERT3U(entry->vime_obsolete_count, <, size);
440 IMPLY(entry->vime_obsolete_count != 0,
441 vim->vim_havecounts);
443 mapbuf[i] = entry->vime_mapping;
444 if (vim->vim_havecounts)
445 countbuf[i] = entry->vime_obsolete_count;
447 vim->vim_phys->vimp_bytes_mapped += size;
448 ASSERT3U(src_offset, >=,
449 vim->vim_phys->vimp_max_offset);
450 vim->vim_phys->vimp_max_offset = src_offset + size;
454 vmem_free(entry, sizeof (*entry));
456 dmu_write(vim->vim_objset, vim->vim_object,
457 vim->vim_phys->vimp_num_entries * sizeof (*mapbuf),
458 i * sizeof (*mapbuf),
460 if (vim->vim_havecounts) {
461 dmu_write(vim->vim_objset,
462 vim->vim_phys->vimp_counts_object,
463 vim->vim_phys->vimp_num_entries *
465 i * sizeof (*countbuf), countbuf, tx);
467 vim->vim_phys->vimp_num_entries += i;
469 vmem_free(mapbuf, SPA_OLD_MAXBLOCKSIZE);
470 if (vim->vim_havecounts)
471 vmem_free(countbuf, SPA_OLD_MAXBLOCKSIZE);
474 * Update the entry array to reflect the new entries. First, copy
475 * over any old entries then read back the new entries we just wrote.
477 uint64_t new_size = vdev_indirect_mapping_size(vim);
478 ASSERT3U(new_size, >, old_size);
479 ASSERT3U(new_size - old_size, ==,
480 entries_written * sizeof (vdev_indirect_mapping_entry_phys_t));
481 vim->vim_entries = vmem_alloc(new_size, KM_SLEEP);
483 bcopy(old_entries, vim->vim_entries, old_size);
484 vmem_free(old_entries, old_size);
486 VERIFY0(dmu_read(vim->vim_objset, vim->vim_object, old_size,
487 new_size - old_size, &vim->vim_entries[old_count],
490 zfs_dbgmsg("txg %llu: wrote %llu entries to "
491 "indirect mapping obj %llu; max offset=0x%llx",
492 (u_longlong_t)dmu_tx_get_txg(tx),
493 (u_longlong_t)entries_written,
494 (u_longlong_t)vim->vim_object,
495 (u_longlong_t)vim->vim_phys->vimp_max_offset);
499 * Increment the relevant counts for the specified offset and length.
500 * The counts array must be obtained from
501 * vdev_indirect_mapping_load_obsolete_counts().
504 vdev_indirect_mapping_increment_obsolete_count(vdev_indirect_mapping_t *vim,
505 uint64_t offset, uint64_t length, uint32_t *counts)
507 vdev_indirect_mapping_entry_phys_t *mapping;
510 mapping = vdev_indirect_mapping_entry_for_offset(vim, offset);
513 ASSERT3P(mapping, !=, NULL);
515 index = mapping - vim->vim_entries;
518 ASSERT3U(index, <, vdev_indirect_mapping_num_entries(vim));
520 uint64_t size = DVA_GET_ASIZE(&mapping->vimep_dst);
521 uint64_t inner_offset = offset -
522 DVA_MAPPING_GET_SRC_OFFSET(mapping);
523 VERIFY3U(inner_offset, <, size);
524 uint64_t inner_size = MIN(length, size - inner_offset);
526 VERIFY3U(counts[index] + inner_size, <=, size);
527 counts[index] += inner_size;
529 offset += inner_size;
530 length -= inner_size;
536 typedef struct load_obsolete_space_map_arg {
537 vdev_indirect_mapping_t *losma_vim;
538 uint32_t *losma_counts;
539 } load_obsolete_space_map_arg_t;
542 load_obsolete_sm_callback(maptype_t type, uint64_t offset, uint64_t size,
545 load_obsolete_space_map_arg_t *losma = arg;
546 ASSERT3S(type, ==, SM_ALLOC);
548 vdev_indirect_mapping_increment_obsolete_count(losma->losma_vim,
549 offset, size, losma->losma_counts);
555 * Modify the counts (increment them) based on the spacemap.
558 vdev_indirect_mapping_load_obsolete_spacemap(vdev_indirect_mapping_t *vim,
559 uint32_t *counts, space_map_t *obsolete_space_sm)
561 load_obsolete_space_map_arg_t losma;
562 losma.losma_counts = counts;
563 losma.losma_vim = vim;
564 VERIFY0(space_map_iterate(obsolete_space_sm,
565 load_obsolete_sm_callback, &losma));
569 * Read the obsolete counts from disk, returning them in an array.
572 vdev_indirect_mapping_load_obsolete_counts(vdev_indirect_mapping_t *vim)
574 ASSERT(vdev_indirect_mapping_verify(vim));
576 uint64_t counts_size =
577 vim->vim_phys->vimp_num_entries * sizeof (uint32_t);
578 uint32_t *counts = vmem_alloc(counts_size, KM_SLEEP);
579 if (vim->vim_havecounts) {
580 VERIFY0(dmu_read(vim->vim_objset,
581 vim->vim_phys->vimp_counts_object,
583 counts, DMU_READ_PREFETCH));
585 bzero(counts, counts_size);
591 vdev_indirect_mapping_free_obsolete_counts(vdev_indirect_mapping_t *vim,
594 ASSERT(vdev_indirect_mapping_verify(vim));
596 vmem_free(counts, vim->vim_phys->vimp_num_entries * sizeof (uint32_t));
599 #if defined(_KERNEL) && defined(HAVE_SPL)
600 EXPORT_SYMBOL(vdev_indirect_mapping_add_entries);
601 EXPORT_SYMBOL(vdev_indirect_mapping_alloc);
602 EXPORT_SYMBOL(vdev_indirect_mapping_bytes_mapped);
603 EXPORT_SYMBOL(vdev_indirect_mapping_close);
604 EXPORT_SYMBOL(vdev_indirect_mapping_entry_for_offset);
605 EXPORT_SYMBOL(vdev_indirect_mapping_entry_for_offset_or_next);
606 EXPORT_SYMBOL(vdev_indirect_mapping_free);
607 EXPORT_SYMBOL(vdev_indirect_mapping_free_obsolete_counts);
608 EXPORT_SYMBOL(vdev_indirect_mapping_increment_obsolete_count);
609 EXPORT_SYMBOL(vdev_indirect_mapping_load_obsolete_counts);
610 EXPORT_SYMBOL(vdev_indirect_mapping_load_obsolete_spacemap);
611 EXPORT_SYMBOL(vdev_indirect_mapping_max_offset);
612 EXPORT_SYMBOL(vdev_indirect_mapping_num_entries);
613 EXPORT_SYMBOL(vdev_indirect_mapping_object);
614 EXPORT_SYMBOL(vdev_indirect_mapping_open);
615 EXPORT_SYMBOL(vdev_indirect_mapping_size);