xref: /freebsd/sys/contrib/openzfs/module/zfs/dmu_zfetch.c (revision 3332f1b444d4a73238e9f59cca27bfc95fe936bd)
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 http://www.opensolaris.org/os/licensing.
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 /*
27  * Copyright (c) 2013, 2017 by Delphix. All rights reserved.
28  */
29 
30 #include <sys/zfs_context.h>
31 #include <sys/dnode.h>
32 #include <sys/dmu_objset.h>
33 #include <sys/dmu_zfetch.h>
34 #include <sys/dmu.h>
35 #include <sys/dbuf.h>
36 #include <sys/kstat.h>
37 #include <sys/wmsum.h>
38 
39 /*
40  * This tunable disables predictive prefetch.  Note that it leaves "prescient"
41  * prefetch (e.g. prefetch for zfs send) intact.  Unlike predictive prefetch,
42  * prescient prefetch never issues i/os that end up not being needed,
43  * so it can't hurt performance.
44  */
45 
46 int zfs_prefetch_disable = B_FALSE;
47 
48 /* max # of streams per zfetch */
49 unsigned int	zfetch_max_streams = 8;
50 /* min time before stream reclaim */
51 unsigned int	zfetch_min_sec_reap = 2;
52 /* max bytes to prefetch per stream (default 8MB) */
53 unsigned int	zfetch_max_distance = 8 * 1024 * 1024;
54 /* max bytes to prefetch indirects for per stream (default 64MB) */
55 unsigned int	zfetch_max_idistance = 64 * 1024 * 1024;
56 /* max number of bytes in an array_read in which we allow prefetching (1MB) */
57 unsigned long	zfetch_array_rd_sz = 1024 * 1024;
58 
59 typedef struct zfetch_stats {
60 	kstat_named_t zfetchstat_hits;
61 	kstat_named_t zfetchstat_misses;
62 	kstat_named_t zfetchstat_max_streams;
63 	kstat_named_t zfetchstat_io_issued;
64 } zfetch_stats_t;
65 
66 static zfetch_stats_t zfetch_stats = {
67 	{ "hits",			KSTAT_DATA_UINT64 },
68 	{ "misses",			KSTAT_DATA_UINT64 },
69 	{ "max_streams",		KSTAT_DATA_UINT64 },
70 	{ "io_issued",		KSTAT_DATA_UINT64 },
71 };
72 
73 struct {
74 	wmsum_t zfetchstat_hits;
75 	wmsum_t zfetchstat_misses;
76 	wmsum_t zfetchstat_max_streams;
77 	wmsum_t zfetchstat_io_issued;
78 } zfetch_sums;
79 
80 #define	ZFETCHSTAT_BUMP(stat)					\
81 	wmsum_add(&zfetch_sums.stat, 1)
82 #define	ZFETCHSTAT_ADD(stat, val)				\
83 	wmsum_add(&zfetch_sums.stat, val)
84 
85 
86 kstat_t		*zfetch_ksp;
87 
88 static int
89 zfetch_kstats_update(kstat_t *ksp, int rw)
90 {
91 	zfetch_stats_t *zs = ksp->ks_data;
92 
93 	if (rw == KSTAT_WRITE)
94 		return (EACCES);
95 	zs->zfetchstat_hits.value.ui64 =
96 	    wmsum_value(&zfetch_sums.zfetchstat_hits);
97 	zs->zfetchstat_misses.value.ui64 =
98 	    wmsum_value(&zfetch_sums.zfetchstat_misses);
99 	zs->zfetchstat_max_streams.value.ui64 =
100 	    wmsum_value(&zfetch_sums.zfetchstat_max_streams);
101 	zs->zfetchstat_io_issued.value.ui64 =
102 	    wmsum_value(&zfetch_sums.zfetchstat_io_issued);
103 	return (0);
104 }
105 
106 void
107 zfetch_init(void)
108 {
109 	wmsum_init(&zfetch_sums.zfetchstat_hits, 0);
110 	wmsum_init(&zfetch_sums.zfetchstat_misses, 0);
111 	wmsum_init(&zfetch_sums.zfetchstat_max_streams, 0);
112 	wmsum_init(&zfetch_sums.zfetchstat_io_issued, 0);
113 
114 	zfetch_ksp = kstat_create("zfs", 0, "zfetchstats", "misc",
115 	    KSTAT_TYPE_NAMED, sizeof (zfetch_stats) / sizeof (kstat_named_t),
116 	    KSTAT_FLAG_VIRTUAL);
117 
118 	if (zfetch_ksp != NULL) {
119 		zfetch_ksp->ks_data = &zfetch_stats;
120 		zfetch_ksp->ks_update = zfetch_kstats_update;
121 		kstat_install(zfetch_ksp);
122 	}
123 }
124 
125 void
126 zfetch_fini(void)
127 {
128 	if (zfetch_ksp != NULL) {
129 		kstat_delete(zfetch_ksp);
130 		zfetch_ksp = NULL;
131 	}
132 
133 	wmsum_fini(&zfetch_sums.zfetchstat_hits);
134 	wmsum_fini(&zfetch_sums.zfetchstat_misses);
135 	wmsum_fini(&zfetch_sums.zfetchstat_max_streams);
136 	wmsum_fini(&zfetch_sums.zfetchstat_io_issued);
137 }
138 
139 /*
140  * This takes a pointer to a zfetch structure and a dnode.  It performs the
141  * necessary setup for the zfetch structure, grokking data from the
142  * associated dnode.
143  */
144 void
145 dmu_zfetch_init(zfetch_t *zf, dnode_t *dno)
146 {
147 	if (zf == NULL)
148 		return;
149 	zf->zf_dnode = dno;
150 	zf->zf_numstreams = 0;
151 
152 	list_create(&zf->zf_stream, sizeof (zstream_t),
153 	    offsetof(zstream_t, zs_node));
154 
155 	mutex_init(&zf->zf_lock, NULL, MUTEX_DEFAULT, NULL);
156 }
157 
158 static void
159 dmu_zfetch_stream_fini(zstream_t *zs)
160 {
161 	ASSERT(!list_link_active(&zs->zs_node));
162 	zfs_refcount_destroy(&zs->zs_callers);
163 	zfs_refcount_destroy(&zs->zs_refs);
164 	kmem_free(zs, sizeof (*zs));
165 }
166 
167 static void
168 dmu_zfetch_stream_remove(zfetch_t *zf, zstream_t *zs)
169 {
170 	ASSERT(MUTEX_HELD(&zf->zf_lock));
171 	list_remove(&zf->zf_stream, zs);
172 	zf->zf_numstreams--;
173 	membar_producer();
174 	if (zfs_refcount_remove(&zs->zs_refs, NULL) == 0)
175 		dmu_zfetch_stream_fini(zs);
176 }
177 
178 /*
179  * Clean-up state associated with a zfetch structure (e.g. destroy the
180  * streams).  This doesn't free the zfetch_t itself, that's left to the caller.
181  */
182 void
183 dmu_zfetch_fini(zfetch_t *zf)
184 {
185 	zstream_t *zs;
186 
187 	mutex_enter(&zf->zf_lock);
188 	while ((zs = list_head(&zf->zf_stream)) != NULL)
189 		dmu_zfetch_stream_remove(zf, zs);
190 	mutex_exit(&zf->zf_lock);
191 	list_destroy(&zf->zf_stream);
192 	mutex_destroy(&zf->zf_lock);
193 
194 	zf->zf_dnode = NULL;
195 }
196 
197 /*
198  * If there aren't too many streams already, create a new stream.
199  * The "blkid" argument is the next block that we expect this stream to access.
200  * While we're here, clean up old streams (which haven't been
201  * accessed for at least zfetch_min_sec_reap seconds).
202  */
203 static void
204 dmu_zfetch_stream_create(zfetch_t *zf, uint64_t blkid)
205 {
206 	zstream_t *zs_next;
207 	hrtime_t now = gethrtime();
208 
209 	ASSERT(MUTEX_HELD(&zf->zf_lock));
210 
211 	/*
212 	 * Clean up old streams.
213 	 */
214 	for (zstream_t *zs = list_head(&zf->zf_stream);
215 	    zs != NULL; zs = zs_next) {
216 		zs_next = list_next(&zf->zf_stream, zs);
217 		/*
218 		 * Skip if still active.  1 -- zf_stream reference.
219 		 */
220 		if (zfs_refcount_count(&zs->zs_refs) != 1)
221 			continue;
222 		if (((now - zs->zs_atime) / NANOSEC) >
223 		    zfetch_min_sec_reap)
224 			dmu_zfetch_stream_remove(zf, zs);
225 	}
226 
227 	/*
228 	 * The maximum number of streams is normally zfetch_max_streams,
229 	 * but for small files we lower it such that it's at least possible
230 	 * for all the streams to be non-overlapping.
231 	 *
232 	 * If we are already at the maximum number of streams for this file,
233 	 * even after removing old streams, then don't create this stream.
234 	 */
235 	uint32_t max_streams = MAX(1, MIN(zfetch_max_streams,
236 	    zf->zf_dnode->dn_maxblkid * zf->zf_dnode->dn_datablksz /
237 	    zfetch_max_distance));
238 	if (zf->zf_numstreams >= max_streams) {
239 		ZFETCHSTAT_BUMP(zfetchstat_max_streams);
240 		return;
241 	}
242 
243 	zstream_t *zs = kmem_zalloc(sizeof (*zs), KM_SLEEP);
244 	zs->zs_blkid = blkid;
245 	zs->zs_pf_blkid1 = blkid;
246 	zs->zs_pf_blkid = blkid;
247 	zs->zs_ipf_blkid1 = blkid;
248 	zs->zs_ipf_blkid = blkid;
249 	zs->zs_atime = now;
250 	zs->zs_fetch = zf;
251 	zs->zs_missed = B_FALSE;
252 	zfs_refcount_create(&zs->zs_callers);
253 	zfs_refcount_create(&zs->zs_refs);
254 	/* One reference for zf_stream. */
255 	zfs_refcount_add(&zs->zs_refs, NULL);
256 	zf->zf_numstreams++;
257 	list_insert_head(&zf->zf_stream, zs);
258 }
259 
260 static void
261 dmu_zfetch_stream_done(void *arg, boolean_t io_issued)
262 {
263 	zstream_t *zs = arg;
264 
265 	if (zfs_refcount_remove(&zs->zs_refs, NULL) == 0)
266 		dmu_zfetch_stream_fini(zs);
267 }
268 
269 /*
270  * This is the predictive prefetch entry point.  dmu_zfetch_prepare()
271  * associates dnode access specified with blkid and nblks arguments with
272  * prefetch stream, predicts further accesses based on that stats and returns
273  * the stream pointer on success.  That pointer must later be passed to
274  * dmu_zfetch_run() to initiate the speculative prefetch for the stream and
275  * release it.  dmu_zfetch() is a wrapper for simple cases when window between
276  * prediction and prefetch initiation is not needed.
277  * fetch_data argument specifies whether actual data blocks should be fetched:
278  *   FALSE -- prefetch only indirect blocks for predicted data blocks;
279  *   TRUE -- prefetch predicted data blocks plus following indirect blocks.
280  */
281 zstream_t *
282 dmu_zfetch_prepare(zfetch_t *zf, uint64_t blkid, uint64_t nblks,
283     boolean_t fetch_data, boolean_t have_lock)
284 {
285 	zstream_t *zs;
286 	int64_t pf_start, ipf_start;
287 	int64_t pf_ahead_blks, max_blks;
288 	int max_dist_blks, pf_nblks, ipf_nblks;
289 	uint64_t end_of_access_blkid, maxblkid;
290 	end_of_access_blkid = blkid + nblks;
291 	spa_t *spa = zf->zf_dnode->dn_objset->os_spa;
292 
293 	if (zfs_prefetch_disable)
294 		return (NULL);
295 	/*
296 	 * If we haven't yet loaded the indirect vdevs' mappings, we
297 	 * can only read from blocks that we carefully ensure are on
298 	 * concrete vdevs (or previously-loaded indirect vdevs).  So we
299 	 * can't allow the predictive prefetcher to attempt reads of other
300 	 * blocks (e.g. of the MOS's dnode object).
301 	 */
302 	if (!spa_indirect_vdevs_loaded(spa))
303 		return (NULL);
304 
305 	/*
306 	 * As a fast path for small (single-block) files, ignore access
307 	 * to the first block.
308 	 */
309 	if (!have_lock && blkid == 0)
310 		return (NULL);
311 
312 	if (!have_lock)
313 		rw_enter(&zf->zf_dnode->dn_struct_rwlock, RW_READER);
314 
315 	/*
316 	 * A fast path for small files for which no prefetch will
317 	 * happen.
318 	 */
319 	maxblkid = zf->zf_dnode->dn_maxblkid;
320 	if (maxblkid < 2) {
321 		if (!have_lock)
322 			rw_exit(&zf->zf_dnode->dn_struct_rwlock);
323 		return (NULL);
324 	}
325 	mutex_enter(&zf->zf_lock);
326 
327 	/*
328 	 * Find matching prefetch stream.  Depending on whether the accesses
329 	 * are block-aligned, first block of the new access may either follow
330 	 * the last block of the previous access, or be equal to it.
331 	 */
332 	for (zs = list_head(&zf->zf_stream); zs != NULL;
333 	    zs = list_next(&zf->zf_stream, zs)) {
334 		if (blkid == zs->zs_blkid) {
335 			break;
336 		} else if (blkid + 1 == zs->zs_blkid) {
337 			blkid++;
338 			nblks--;
339 			break;
340 		}
341 	}
342 
343 	/*
344 	 * If the file is ending, remove the matching stream if found.
345 	 * If not found then it is too late to create a new one now.
346 	 */
347 	if (end_of_access_blkid >= maxblkid) {
348 		if (zs != NULL)
349 			dmu_zfetch_stream_remove(zf, zs);
350 		mutex_exit(&zf->zf_lock);
351 		if (!have_lock)
352 			rw_exit(&zf->zf_dnode->dn_struct_rwlock);
353 		return (NULL);
354 	}
355 
356 	/* Exit if we already prefetched this block before. */
357 	if (nblks == 0) {
358 		mutex_exit(&zf->zf_lock);
359 		if (!have_lock)
360 			rw_exit(&zf->zf_dnode->dn_struct_rwlock);
361 		return (NULL);
362 	}
363 
364 	if (zs == NULL) {
365 		/*
366 		 * This access is not part of any existing stream.  Create
367 		 * a new stream for it.
368 		 */
369 		dmu_zfetch_stream_create(zf, end_of_access_blkid);
370 		mutex_exit(&zf->zf_lock);
371 		if (!have_lock)
372 			rw_exit(&zf->zf_dnode->dn_struct_rwlock);
373 		ZFETCHSTAT_BUMP(zfetchstat_misses);
374 		return (NULL);
375 	}
376 
377 	/*
378 	 * This access was to a block that we issued a prefetch for on
379 	 * behalf of this stream. Issue further prefetches for this stream.
380 	 *
381 	 * Normally, we start prefetching where we stopped
382 	 * prefetching last (zs_pf_blkid).  But when we get our first
383 	 * hit on this stream, zs_pf_blkid == zs_blkid, we don't
384 	 * want to prefetch the block we just accessed.  In this case,
385 	 * start just after the block we just accessed.
386 	 */
387 	pf_start = MAX(zs->zs_pf_blkid, end_of_access_blkid);
388 	if (zs->zs_pf_blkid1 < end_of_access_blkid)
389 		zs->zs_pf_blkid1 = end_of_access_blkid;
390 	if (zs->zs_ipf_blkid1 < end_of_access_blkid)
391 		zs->zs_ipf_blkid1 = end_of_access_blkid;
392 
393 	/*
394 	 * Double our amount of prefetched data, but don't let the
395 	 * prefetch get further ahead than zfetch_max_distance.
396 	 */
397 	if (fetch_data) {
398 		max_dist_blks =
399 		    zfetch_max_distance >> zf->zf_dnode->dn_datablkshift;
400 		/*
401 		 * Previously, we were (zs_pf_blkid - blkid) ahead.  We
402 		 * want to now be double that, so read that amount again,
403 		 * plus the amount we are catching up by (i.e. the amount
404 		 * read just now).
405 		 */
406 		pf_ahead_blks = zs->zs_pf_blkid - blkid + nblks;
407 		max_blks = max_dist_blks - (pf_start - end_of_access_blkid);
408 		pf_nblks = MIN(pf_ahead_blks, max_blks);
409 	} else {
410 		pf_nblks = 0;
411 	}
412 
413 	zs->zs_pf_blkid = pf_start + pf_nblks;
414 
415 	/*
416 	 * Do the same for indirects, starting from where we stopped last,
417 	 * or where we will stop reading data blocks (and the indirects
418 	 * that point to them).
419 	 */
420 	ipf_start = MAX(zs->zs_ipf_blkid, zs->zs_pf_blkid);
421 	max_dist_blks = zfetch_max_idistance >> zf->zf_dnode->dn_datablkshift;
422 	/*
423 	 * We want to double our distance ahead of the data prefetch
424 	 * (or reader, if we are not prefetching data).  Previously, we
425 	 * were (zs_ipf_blkid - blkid) ahead.  To double that, we read
426 	 * that amount again, plus the amount we are catching up by
427 	 * (i.e. the amount read now + the amount of data prefetched now).
428 	 */
429 	pf_ahead_blks = zs->zs_ipf_blkid - blkid + nblks + pf_nblks;
430 	max_blks = max_dist_blks - (ipf_start - zs->zs_pf_blkid);
431 	ipf_nblks = MIN(pf_ahead_blks, max_blks);
432 	zs->zs_ipf_blkid = ipf_start + ipf_nblks;
433 
434 	zs->zs_blkid = end_of_access_blkid;
435 	/* Protect the stream from reclamation. */
436 	zs->zs_atime = gethrtime();
437 	zfs_refcount_add(&zs->zs_refs, NULL);
438 	/* Count concurrent callers. */
439 	zfs_refcount_add(&zs->zs_callers, NULL);
440 	mutex_exit(&zf->zf_lock);
441 
442 	if (!have_lock)
443 		rw_exit(&zf->zf_dnode->dn_struct_rwlock);
444 
445 	ZFETCHSTAT_BUMP(zfetchstat_hits);
446 	return (zs);
447 }
448 
449 void
450 dmu_zfetch_run(zstream_t *zs, boolean_t missed, boolean_t have_lock)
451 {
452 	zfetch_t *zf = zs->zs_fetch;
453 	int64_t pf_start, pf_end, ipf_start, ipf_end;
454 	int epbs, issued;
455 
456 	if (missed)
457 		zs->zs_missed = missed;
458 
459 	/*
460 	 * Postpone the prefetch if there are more concurrent callers.
461 	 * It happens when multiple requests are waiting for the same
462 	 * indirect block.  The last one will run the prefetch for all.
463 	 */
464 	if (zfs_refcount_remove(&zs->zs_callers, NULL) != 0) {
465 		/* Drop reference taken in dmu_zfetch_prepare(). */
466 		if (zfs_refcount_remove(&zs->zs_refs, NULL) == 0)
467 			dmu_zfetch_stream_fini(zs);
468 		return;
469 	}
470 
471 	mutex_enter(&zf->zf_lock);
472 	if (zs->zs_missed) {
473 		pf_start = zs->zs_pf_blkid1;
474 		pf_end = zs->zs_pf_blkid1 = zs->zs_pf_blkid;
475 	} else {
476 		pf_start = pf_end = 0;
477 	}
478 	ipf_start = MAX(zs->zs_pf_blkid1, zs->zs_ipf_blkid1);
479 	ipf_end = zs->zs_ipf_blkid1 = zs->zs_ipf_blkid;
480 	mutex_exit(&zf->zf_lock);
481 	ASSERT3S(pf_start, <=, pf_end);
482 	ASSERT3S(ipf_start, <=, ipf_end);
483 
484 	epbs = zf->zf_dnode->dn_indblkshift - SPA_BLKPTRSHIFT;
485 	ipf_start = P2ROUNDUP(ipf_start, 1 << epbs) >> epbs;
486 	ipf_end = P2ROUNDUP(ipf_end, 1 << epbs) >> epbs;
487 	ASSERT3S(ipf_start, <=, ipf_end);
488 	issued = pf_end - pf_start + ipf_end - ipf_start;
489 	if (issued > 1) {
490 		/* More references on top of taken in dmu_zfetch_prepare(). */
491 		for (int i = 0; i < issued - 1; i++)
492 			zfs_refcount_add(&zs->zs_refs, NULL);
493 	} else if (issued == 0) {
494 		/* Some other thread has done our work, so drop the ref. */
495 		if (zfs_refcount_remove(&zs->zs_refs, NULL) == 0)
496 			dmu_zfetch_stream_fini(zs);
497 		return;
498 	}
499 
500 	if (!have_lock)
501 		rw_enter(&zf->zf_dnode->dn_struct_rwlock, RW_READER);
502 
503 	issued = 0;
504 	for (int64_t blk = pf_start; blk < pf_end; blk++) {
505 		issued += dbuf_prefetch_impl(zf->zf_dnode, 0, blk,
506 		    ZIO_PRIORITY_ASYNC_READ, ARC_FLAG_PREDICTIVE_PREFETCH,
507 		    dmu_zfetch_stream_done, zs);
508 	}
509 	for (int64_t iblk = ipf_start; iblk < ipf_end; iblk++) {
510 		issued += dbuf_prefetch_impl(zf->zf_dnode, 1, iblk,
511 		    ZIO_PRIORITY_ASYNC_READ, ARC_FLAG_PREDICTIVE_PREFETCH,
512 		    dmu_zfetch_stream_done, zs);
513 	}
514 
515 	if (!have_lock)
516 		rw_exit(&zf->zf_dnode->dn_struct_rwlock);
517 
518 	if (issued)
519 		ZFETCHSTAT_ADD(zfetchstat_io_issued, issued);
520 }
521 
522 void
523 dmu_zfetch(zfetch_t *zf, uint64_t blkid, uint64_t nblks, boolean_t fetch_data,
524     boolean_t missed, boolean_t have_lock)
525 {
526 	zstream_t *zs;
527 
528 	zs = dmu_zfetch_prepare(zf, blkid, nblks, fetch_data, have_lock);
529 	if (zs)
530 		dmu_zfetch_run(zs, missed, have_lock);
531 }
532 
533 /* BEGIN CSTYLED */
534 ZFS_MODULE_PARAM(zfs_prefetch, zfs_prefetch_, disable, INT, ZMOD_RW,
535 	"Disable all ZFS prefetching");
536 
537 ZFS_MODULE_PARAM(zfs_prefetch, zfetch_, max_streams, UINT, ZMOD_RW,
538 	"Max number of streams per zfetch");
539 
540 ZFS_MODULE_PARAM(zfs_prefetch, zfetch_, min_sec_reap, UINT, ZMOD_RW,
541 	"Min time before stream reclaim");
542 
543 ZFS_MODULE_PARAM(zfs_prefetch, zfetch_, max_distance, UINT, ZMOD_RW,
544 	"Max bytes to prefetch per stream");
545 
546 ZFS_MODULE_PARAM(zfs_prefetch, zfetch_, max_idistance, UINT, ZMOD_RW,
547 	"Max bytes to prefetch indirects for per stream");
548 
549 ZFS_MODULE_PARAM(zfs_prefetch, zfetch_, array_rd_sz, ULONG, ZMOD_RW,
550 	"Number of bytes in a array_read");
551 /* END CSTYLED */
552