1 // SPDX-License-Identifier: CDDL-1.0
2 /*
3 * This file and its contents are supplied under the terms of the
4 * Common Development and Distribution License ("CDDL"), version 1.0.
5 * You may only use this file in accordance with the terms of version
6 * 1.0 of the CDDL.
7 *
8 * A full copy of the text of the CDDL should have accompanied this
9 * source. A copy of the CDDL is also available via the Internet at
10 * https://opensource.org/license/CDDL-1.0.
11 */
12 /*
13 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
14 * Copyright (c) 2013, 2017 by Delphix. All rights reserved.
15 * Copyright 2014 HybridCluster. All rights reserved.
16 */
17
18 #include <sys/dbuf.h>
19 #include <sys/dmu.h>
20 #include <sys/dmu_impl.h>
21 #include <sys/dmu_objset.h>
22 #include <sys/dmu_tx.h>
23 #include <sys/dnode.h>
24 #include <sys/zap.h>
25 #include <sys/zfeature.h>
26 #include <sys/dsl_dataset.h>
27
28 /*
29 * Each of the concurrent object allocators will grab
30 * 2^dmu_object_alloc_chunk_shift dnode slots at a time. The default is to
31 * grab 128 slots, which is 4 blocks worth. This was experimentally
32 * determined to be the lowest value that eliminates the measurable effect
33 * of lock contention from this code path.
34 */
35 uint_t dmu_object_alloc_chunk_shift = 7;
36
37 static uint64_t
dmu_object_alloc_impl(objset_t * os,dmu_object_type_t ot,int blocksize,int indirect_blockshift,dmu_object_type_t bonustype,int bonuslen,int dnodesize,dnode_t ** allocated_dnode,const void * tag,dmu_tx_t * tx)38 dmu_object_alloc_impl(objset_t *os, dmu_object_type_t ot, int blocksize,
39 int indirect_blockshift, dmu_object_type_t bonustype, int bonuslen,
40 int dnodesize, dnode_t **allocated_dnode, const void *tag, dmu_tx_t *tx)
41 {
42 uint64_t object;
43 uint64_t L1_dnode_count = DNODES_PER_BLOCK <<
44 (DMU_META_DNODE(os)->dn_indblkshift - SPA_BLKPTRSHIFT);
45 dnode_t *dn = NULL;
46 int dn_slots = dnodesize >> DNODE_SHIFT;
47 boolean_t restarted = B_FALSE;
48 uint64_t *cpuobj = NULL;
49 uint_t dnodes_per_chunk = 1 << dmu_object_alloc_chunk_shift;
50 int error;
51
52 cpuobj = &os->os_obj_next_percpu[CPU_SEQID_UNSTABLE %
53 os->os_obj_next_percpu_len];
54
55 if (dn_slots == 0) {
56 dn_slots = DNODE_MIN_SLOTS;
57 } else {
58 ASSERT3S(dn_slots, >=, DNODE_MIN_SLOTS);
59 ASSERT3S(dn_slots, <=, DNODE_MAX_SLOTS);
60 }
61
62 /*
63 * The "chunk" of dnodes that is assigned to a CPU-specific
64 * allocator needs to be at least one block's worth, to avoid
65 * lock contention on the dbuf. It can be at most one L1 block's
66 * worth, so that the "rescan after polishing off a L1's worth"
67 * logic below will be sure to kick in.
68 */
69 if (dnodes_per_chunk < DNODES_PER_BLOCK)
70 dnodes_per_chunk = DNODES_PER_BLOCK;
71 if (dnodes_per_chunk > L1_dnode_count)
72 dnodes_per_chunk = L1_dnode_count;
73
74 /*
75 * The caller requested the dnode be returned as a performance
76 * optimization in order to avoid releasing the hold only to
77 * immediately reacquire it. Since they caller is responsible
78 * for releasing the hold they must provide the tag.
79 */
80 if (allocated_dnode != NULL) {
81 ASSERT3P(tag, !=, NULL);
82 } else {
83 ASSERT0P(tag);
84 tag = FTAG;
85 }
86
87 object = *cpuobj;
88 for (;;) {
89 /*
90 * If we finished a chunk of dnodes, get a new one from
91 * the global allocator.
92 */
93 if ((P2PHASE(object, dnodes_per_chunk) == 0) ||
94 (P2PHASE(object + dn_slots - 1, dnodes_per_chunk) <
95 dn_slots)) {
96 DNODE_STAT_BUMP(dnode_alloc_next_chunk);
97 mutex_enter(&os->os_obj_lock);
98 ASSERT0(P2PHASE(os->os_obj_next_chunk,
99 dnodes_per_chunk));
100 object = os->os_obj_next_chunk;
101
102 /*
103 * Each time we polish off a L1 bp worth of dnodes
104 * (2^12 objects), move to another L1 bp that's
105 * still reasonably sparse (at most 1/4 full). Look
106 * from the beginning at most once per txg. If we
107 * still can't allocate from that L1 block, search
108 * for an empty L0 block, which will quickly skip
109 * to the end of the metadnode if no nearby L0
110 * blocks are empty. This fallback avoids a
111 * pathology where full dnode blocks containing
112 * large dnodes appear sparse because they have a
113 * low blk_fill, leading to many failed allocation
114 * attempts. In the long term a better mechanism to
115 * search for sparse metadnode regions, such as
116 * spacemaps, could be implemented.
117 *
118 * os_scan_dnodes is set during txg sync if enough
119 * objects have been freed since the previous
120 * rescan to justify backfilling again.
121 *
122 * Note that dmu_traverse depends on the behavior
123 * that we use multiple blocks of the dnode object
124 * before going back to reuse objects. Any change
125 * to this algorithm should preserve that property
126 * or find another solution to the issues described
127 * in traverse_visitbp.
128 */
129 if (P2PHASE(object, L1_dnode_count) == 0) {
130 uint64_t offset;
131 uint64_t blkfill;
132 int minlvl;
133 if (os->os_rescan_dnodes) {
134 offset = 0;
135 os->os_rescan_dnodes = B_FALSE;
136 } else {
137 offset = object << DNODE_SHIFT;
138 }
139 blkfill = restarted ? 1 : DNODES_PER_BLOCK >> 2;
140 minlvl = restarted ? 1 : 2;
141 restarted = B_TRUE;
142 error = dnode_next_offset(DMU_META_DNODE(os),
143 DNODE_FIND_HOLE, &offset, minlvl,
144 blkfill, 0);
145 if (error == 0) {
146 object = offset >> DNODE_SHIFT;
147 }
148 }
149 /*
150 * Note: if "restarted", we may find a L0 that
151 * is not suitably aligned.
152 */
153 os->os_obj_next_chunk =
154 P2ALIGN_TYPED(object, dnodes_per_chunk, uint64_t) +
155 dnodes_per_chunk;
156 (void) atomic_swap_64(cpuobj, object);
157 mutex_exit(&os->os_obj_lock);
158 }
159
160 /*
161 * The value of (*cpuobj) before adding dn_slots is the object
162 * ID assigned to us. The value afterwards is the object ID
163 * assigned to whoever wants to do an allocation next.
164 */
165 object = atomic_add_64_nv(cpuobj, dn_slots) - dn_slots;
166
167 /*
168 * XXX We should check for an i/o error here and return
169 * up to our caller. Actually we should pre-read it in
170 * dmu_tx_assign(), but there is currently no mechanism
171 * to do so.
172 */
173 error = dnode_hold_impl(os, object, DNODE_MUST_BE_FREE,
174 dn_slots, tag, &dn);
175 if (error == 0) {
176 rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
177 /*
178 * Another thread could have allocated it; check
179 * again now that we have the struct lock.
180 */
181 if (dn->dn_type == DMU_OT_NONE) {
182 dnode_allocate(dn, ot, blocksize,
183 indirect_blockshift, bonustype,
184 bonuslen, dn_slots, tx);
185 rw_exit(&dn->dn_struct_rwlock);
186 dmu_tx_add_new_object(tx, dn);
187
188 /*
189 * Caller requested the allocated dnode be
190 * returned and is responsible for the hold.
191 */
192 if (allocated_dnode != NULL)
193 *allocated_dnode = dn;
194 else
195 dnode_rele(dn, tag);
196
197 return (object);
198 }
199 rw_exit(&dn->dn_struct_rwlock);
200 dnode_rele(dn, tag);
201 DNODE_STAT_BUMP(dnode_alloc_race);
202 }
203
204 /*
205 * Skip to next known valid starting point on error. This
206 * is the start of the next block of dnodes.
207 */
208 if (dmu_object_next(os, &object, B_TRUE, 0) != 0) {
209 object = P2ROUNDUP(object + 1, DNODES_PER_BLOCK);
210 DNODE_STAT_BUMP(dnode_alloc_next_block);
211 }
212 (void) atomic_swap_64(cpuobj, object);
213 }
214 }
215
216 uint64_t
dmu_object_alloc(objset_t * os,dmu_object_type_t ot,int blocksize,dmu_object_type_t bonustype,int bonuslen,dmu_tx_t * tx)217 dmu_object_alloc(objset_t *os, dmu_object_type_t ot, int blocksize,
218 dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
219 {
220 return dmu_object_alloc_impl(os, ot, blocksize, 0, bonustype,
221 bonuslen, 0, NULL, NULL, tx);
222 }
223
224 uint64_t
dmu_object_alloc_ibs(objset_t * os,dmu_object_type_t ot,int blocksize,int indirect_blockshift,dmu_object_type_t bonustype,int bonuslen,dmu_tx_t * tx)225 dmu_object_alloc_ibs(objset_t *os, dmu_object_type_t ot, int blocksize,
226 int indirect_blockshift, dmu_object_type_t bonustype, int bonuslen,
227 dmu_tx_t *tx)
228 {
229 return dmu_object_alloc_impl(os, ot, blocksize, indirect_blockshift,
230 bonustype, bonuslen, 0, NULL, NULL, tx);
231 }
232
233 uint64_t
dmu_object_alloc_dnsize(objset_t * os,dmu_object_type_t ot,int blocksize,dmu_object_type_t bonustype,int bonuslen,int dnodesize,dmu_tx_t * tx)234 dmu_object_alloc_dnsize(objset_t *os, dmu_object_type_t ot, int blocksize,
235 dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
236 {
237 return (dmu_object_alloc_impl(os, ot, blocksize, 0, bonustype,
238 bonuslen, dnodesize, NULL, NULL, tx));
239 }
240
241 /*
242 * Allocate a new object and return a pointer to the newly allocated dnode
243 * via the allocated_dnode argument. The returned dnode will be held and
244 * the caller is responsible for releasing the hold by calling dnode_rele().
245 */
246 uint64_t
dmu_object_alloc_hold(objset_t * os,dmu_object_type_t ot,int blocksize,int indirect_blockshift,dmu_object_type_t bonustype,int bonuslen,int dnodesize,dnode_t ** allocated_dnode,const void * tag,dmu_tx_t * tx)247 dmu_object_alloc_hold(objset_t *os, dmu_object_type_t ot, int blocksize,
248 int indirect_blockshift, dmu_object_type_t bonustype, int bonuslen,
249 int dnodesize, dnode_t **allocated_dnode, const void *tag, dmu_tx_t *tx)
250 {
251 return (dmu_object_alloc_impl(os, ot, blocksize, indirect_blockshift,
252 bonustype, bonuslen, dnodesize, allocated_dnode, tag, tx));
253 }
254
255 int
dmu_object_claim(objset_t * os,uint64_t object,dmu_object_type_t ot,int blocksize,dmu_object_type_t bonustype,int bonuslen,dmu_tx_t * tx)256 dmu_object_claim(objset_t *os, uint64_t object, dmu_object_type_t ot,
257 int blocksize, dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
258 {
259 return (dmu_object_claim_dnsize(os, object, ot, blocksize, bonustype,
260 bonuslen, 0, tx));
261 }
262
263 int
dmu_object_claim_dnsize(objset_t * os,uint64_t object,dmu_object_type_t ot,int blocksize,dmu_object_type_t bonustype,int bonuslen,int dnodesize,dmu_tx_t * tx)264 dmu_object_claim_dnsize(objset_t *os, uint64_t object, dmu_object_type_t ot,
265 int blocksize, dmu_object_type_t bonustype, int bonuslen,
266 int dnodesize, dmu_tx_t *tx)
267 {
268 dnode_t *dn;
269 int dn_slots = dnodesize >> DNODE_SHIFT;
270 int err;
271
272 if (dn_slots == 0)
273 dn_slots = DNODE_MIN_SLOTS;
274 ASSERT3S(dn_slots, >=, DNODE_MIN_SLOTS);
275 ASSERT3S(dn_slots, <=, DNODE_MAX_SLOTS);
276
277 if (object == DMU_META_DNODE_OBJECT && !dmu_tx_private_ok(tx))
278 return (SET_ERROR(EBADF));
279
280 err = dnode_hold_impl(os, object, DNODE_MUST_BE_FREE, dn_slots,
281 FTAG, &dn);
282 if (err)
283 return (err);
284
285 dnode_allocate(dn, ot, blocksize, 0, bonustype, bonuslen, dn_slots, tx);
286 dmu_tx_add_new_object(tx, dn);
287
288 dnode_rele(dn, FTAG);
289
290 return (0);
291 }
292
293 int
dmu_object_reclaim(objset_t * os,uint64_t object,dmu_object_type_t ot,int blocksize,dmu_object_type_t bonustype,int bonuslen,dmu_tx_t * tx)294 dmu_object_reclaim(objset_t *os, uint64_t object, dmu_object_type_t ot,
295 int blocksize, dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
296 {
297 return (dmu_object_reclaim_dnsize(os, object, ot, blocksize, bonustype,
298 bonuslen, DNODE_MIN_SIZE, B_FALSE, tx));
299 }
300
301 int
dmu_object_reclaim_dnsize(objset_t * os,uint64_t object,dmu_object_type_t ot,int blocksize,dmu_object_type_t bonustype,int bonuslen,int dnodesize,boolean_t keep_spill,dmu_tx_t * tx)302 dmu_object_reclaim_dnsize(objset_t *os, uint64_t object, dmu_object_type_t ot,
303 int blocksize, dmu_object_type_t bonustype, int bonuslen, int dnodesize,
304 boolean_t keep_spill, dmu_tx_t *tx)
305 {
306 dnode_t *dn;
307 int dn_slots = dnodesize >> DNODE_SHIFT;
308 int err;
309
310 if (dn_slots == 0)
311 dn_slots = DNODE_MIN_SLOTS;
312
313 if (object == DMU_META_DNODE_OBJECT)
314 return (SET_ERROR(EBADF));
315
316 err = dnode_hold_impl(os, object, DNODE_MUST_BE_ALLOCATED, 0,
317 FTAG, &dn);
318 if (err)
319 return (err);
320
321 dnode_reallocate(dn, ot, blocksize, bonustype, bonuslen, dn_slots,
322 keep_spill, tx);
323
324 dnode_rele(dn, FTAG);
325 return (err);
326 }
327
328 int
dmu_object_rm_spill(objset_t * os,uint64_t object,dmu_tx_t * tx)329 dmu_object_rm_spill(objset_t *os, uint64_t object, dmu_tx_t *tx)
330 {
331 dnode_t *dn;
332 int err;
333
334 err = dnode_hold_impl(os, object, DNODE_MUST_BE_ALLOCATED, 0,
335 FTAG, &dn);
336 if (err)
337 return (err);
338
339 rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
340 if (dn->dn_phys->dn_flags & DNODE_FLAG_SPILL_BLKPTR) {
341 dbuf_rm_spill(dn, tx);
342 dnode_rm_spill(dn, tx);
343 }
344 rw_exit(&dn->dn_struct_rwlock);
345
346 dnode_rele(dn, FTAG);
347 return (err);
348 }
349
350 int
dmu_object_free(objset_t * os,uint64_t object,dmu_tx_t * tx)351 dmu_object_free(objset_t *os, uint64_t object, dmu_tx_t *tx)
352 {
353 dnode_t *dn;
354 int err;
355
356 ASSERT(object != DMU_META_DNODE_OBJECT || dmu_tx_private_ok(tx));
357
358 err = dnode_hold_impl(os, object, DNODE_MUST_BE_ALLOCATED, 0,
359 FTAG, &dn);
360 if (err)
361 return (err);
362
363 ASSERT(dn->dn_type != DMU_OT_NONE);
364 /*
365 * If we don't create this free range, we'll leak indirect blocks when
366 * we get to freeing the dnode in syncing context.
367 */
368 dnode_free_range(dn, 0, DMU_OBJECT_END, tx);
369 dnode_free(dn, tx);
370 dnode_rele(dn, FTAG);
371
372 return (0);
373 }
374
375 /*
376 * Return (in *objectp) the next object which is allocated (or a hole)
377 * after *object, taking into account only objects that may have been modified
378 * after the specified txg.
379 */
380 int
dmu_object_next(objset_t * os,uint64_t * objectp,boolean_t hole,uint64_t txg)381 dmu_object_next(objset_t *os, uint64_t *objectp, boolean_t hole, uint64_t txg)
382 {
383 uint64_t offset;
384 uint64_t start_obj;
385 struct dsl_dataset *ds = os->os_dsl_dataset;
386 int error;
387
388 if (*objectp == 0) {
389 start_obj = 1;
390 } else if (ds && dsl_dataset_feature_is_active(ds,
391 SPA_FEATURE_LARGE_DNODE)) {
392 uint64_t i = *objectp + 1;
393 uint64_t last_obj = *objectp | (DNODES_PER_BLOCK - 1);
394 dmu_object_info_t doi;
395
396 /*
397 * Scan through the remaining meta dnode block. The contents
398 * of each slot in the block are known so it can be quickly
399 * checked. If the block is exhausted without a match then
400 * hand off to dnode_next_offset() for further scanning.
401 */
402 while (i <= last_obj) {
403 if (i == 0)
404 return (SET_ERROR(ESRCH));
405 error = dmu_object_info(os, i, &doi);
406 if (error == ENOENT) {
407 if (hole) {
408 *objectp = i;
409 return (0);
410 } else {
411 i++;
412 }
413 } else if (error == EEXIST) {
414 i++;
415 } else if (error == 0) {
416 if (hole) {
417 i += doi.doi_dnodesize >> DNODE_SHIFT;
418 } else {
419 *objectp = i;
420 return (0);
421 }
422 } else {
423 return (error);
424 }
425 }
426
427 start_obj = i;
428 } else {
429 start_obj = *objectp + 1;
430 }
431
432 offset = start_obj << DNODE_SHIFT;
433
434 error = dnode_next_offset(DMU_META_DNODE(os),
435 (hole ? DNODE_FIND_HOLE : 0), &offset, 0, DNODES_PER_BLOCK, txg);
436
437 *objectp = offset >> DNODE_SHIFT;
438
439 return (error);
440 }
441
442 /*
443 * Turn this object from old_type into DMU_OTN_ZAP_METADATA, and bump the
444 * refcount on SPA_FEATURE_EXTENSIBLE_DATASET.
445 *
446 * Only for use from syncing context, on MOS objects.
447 */
448 void
dmu_object_zapify(objset_t * mos,uint64_t object,dmu_object_type_t old_type,dmu_tx_t * tx)449 dmu_object_zapify(objset_t *mos, uint64_t object, dmu_object_type_t old_type,
450 dmu_tx_t *tx)
451 {
452 dnode_t *dn;
453
454 ASSERT(dmu_tx_is_syncing(tx));
455
456 VERIFY0(dnode_hold(mos, object, FTAG, &dn));
457 if (dn->dn_type == DMU_OTN_ZAP_METADATA) {
458 dnode_rele(dn, FTAG);
459 return;
460 }
461 ASSERT3U(dn->dn_type, ==, old_type);
462 ASSERT0(dn->dn_maxblkid);
463
464 /*
465 * We must initialize the ZAP data before changing the type,
466 * so that concurrent calls to *_is_zapified() can determine if
467 * the object has been completely zapified by checking the type.
468 */
469 mzap_create_impl(dn, 0, 0, tx);
470
471 dn->dn_next_type[tx->tx_txg & TXG_MASK] = dn->dn_type =
472 DMU_OTN_ZAP_METADATA;
473 dnode_setdirty(dn, tx);
474 dnode_rele(dn, FTAG);
475
476 spa_feature_incr(dmu_objset_spa(mos),
477 SPA_FEATURE_EXTENSIBLE_DATASET, tx);
478 }
479
480 void
dmu_object_free_zapified(objset_t * mos,uint64_t object,dmu_tx_t * tx)481 dmu_object_free_zapified(objset_t *mos, uint64_t object, dmu_tx_t *tx)
482 {
483 dnode_t *dn;
484 dmu_object_type_t t;
485
486 ASSERT(dmu_tx_is_syncing(tx));
487
488 VERIFY0(dnode_hold(mos, object, FTAG, &dn));
489 t = dn->dn_type;
490 dnode_rele(dn, FTAG);
491
492 if (t == DMU_OTN_ZAP_METADATA) {
493 spa_feature_decr(dmu_objset_spa(mos),
494 SPA_FEATURE_EXTENSIBLE_DATASET, tx);
495 }
496 VERIFY0(dmu_object_free(mos, object, tx));
497 }
498
499 EXPORT_SYMBOL(dmu_object_alloc);
500 EXPORT_SYMBOL(dmu_object_alloc_ibs);
501 EXPORT_SYMBOL(dmu_object_alloc_dnsize);
502 EXPORT_SYMBOL(dmu_object_alloc_hold);
503 EXPORT_SYMBOL(dmu_object_claim);
504 EXPORT_SYMBOL(dmu_object_claim_dnsize);
505 EXPORT_SYMBOL(dmu_object_reclaim);
506 EXPORT_SYMBOL(dmu_object_reclaim_dnsize);
507 EXPORT_SYMBOL(dmu_object_rm_spill);
508 EXPORT_SYMBOL(dmu_object_free);
509 EXPORT_SYMBOL(dmu_object_next);
510 EXPORT_SYMBOL(dmu_object_zapify);
511 EXPORT_SYMBOL(dmu_object_free_zapified);
512
513 ZFS_MODULE_PARAM(zfs, , dmu_object_alloc_chunk_shift, UINT, ZMOD_RW,
514 "CPU-specific allocator grabs 2^N objects at once");
515