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.
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.
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]
22 * Copyright (c) 2012 Pawel Jakub Dawidek <pawel@dawidek.net>.
23 * All rights reserved.
26 #include <sys/zfs_context.h>
27 #include <sys/spa_impl.h>
28 #include <sys/vdev_impl.h>
29 #include <sys/trim_map.h>
33 * Calculate the zio end, upgrading based on ashift which would be
34 * done by zio_vdev_io_start.
36 * This makes free range consolidation much more effective
37 * than it would otherwise be as well as ensuring that entire
38 * blocks are invalidated by writes.
40 #define TRIM_ZIO_END(vd, offset, size) (offset + \
41 P2ROUNDUP(size, 1ULL << vd->vdev_top->vdev_ashift))
43 /* Maximal segment size for ATA TRIM. */
44 #define TRIM_MAP_SIZE_FACTOR (512 << 16)
46 #define TRIM_MAP_SEGS(size) (1 + (size) / TRIM_MAP_SIZE_FACTOR)
48 #define TRIM_MAP_ADD(tm, ts) do { \
49 list_insert_tail(&(tm)->tm_head, (ts)); \
50 (tm)->tm_pending += TRIM_MAP_SEGS((ts)->ts_end - (ts)->ts_start); \
53 #define TRIM_MAP_REM(tm, ts) do { \
54 list_remove(&(tm)->tm_head, (ts)); \
55 (tm)->tm_pending -= TRIM_MAP_SEGS((ts)->ts_end - (ts)->ts_start); \
58 typedef struct trim_map {
59 list_t tm_head; /* List of segments sorted by txg. */
60 avl_tree_t tm_queued_frees; /* AVL tree of segments waiting for TRIM. */
61 avl_tree_t tm_inflight_frees; /* AVL tree of in-flight TRIMs. */
62 avl_tree_t tm_inflight_writes; /* AVL tree of in-flight writes. */
63 list_t tm_pending_writes; /* Writes blocked on in-flight frees. */
65 uint64_t tm_pending; /* Count of pending TRIMs. */
68 typedef struct trim_seg {
69 avl_node_t ts_node; /* AVL node. */
70 list_node_t ts_next; /* List element. */
71 uint64_t ts_start; /* Starting offset of this segment. */
72 uint64_t ts_end; /* Ending offset (non-inclusive). */
73 uint64_t ts_txg; /* Segment creation txg. */
74 hrtime_t ts_time; /* Segment creation time. */
77 extern boolean_t zfs_trim_enabled;
79 static u_int trim_txg_delay = 32; /* Keep deleted data up to 32 TXG */
80 static u_int trim_timeout = 30; /* Keep deleted data up to 30s */
81 static u_int trim_max_interval = 1; /* 1s delays between TRIMs */
82 static u_int trim_vdev_max_pending = 10000; /* Keep up to 10K segments */
84 SYSCTL_DECL(_vfs_zfs);
85 SYSCTL_NODE(_vfs_zfs, OID_AUTO, trim, CTLFLAG_RD, 0, "ZFS TRIM");
87 SYSCTL_UINT(_vfs_zfs_trim, OID_AUTO, txg_delay, CTLFLAG_RWTUN, &trim_txg_delay,
88 0, "Delay TRIMs by up to this many TXGs");
89 SYSCTL_UINT(_vfs_zfs_trim, OID_AUTO, timeout, CTLFLAG_RWTUN, &trim_timeout, 0,
90 "Delay TRIMs by up to this many seconds");
91 SYSCTL_UINT(_vfs_zfs_trim, OID_AUTO, max_interval, CTLFLAG_RWTUN,
92 &trim_max_interval, 0,
93 "Maximum interval between TRIM queue processing (seconds)");
95 SYSCTL_DECL(_vfs_zfs_vdev);
96 SYSCTL_UINT(_vfs_zfs_vdev, OID_AUTO, trim_max_pending, CTLFLAG_RWTUN,
97 &trim_vdev_max_pending, 0,
98 "Maximum pending TRIM segments for a vdev");
100 static void trim_map_vdev_commit_done(spa_t *spa, vdev_t *vd);
103 trim_map_seg_compare(const void *x1, const void *x2)
105 const trim_seg_t *s1 = x1;
106 const trim_seg_t *s2 = x2;
108 if (s1->ts_start < s2->ts_start) {
109 if (s1->ts_end > s2->ts_start)
113 if (s1->ts_start > s2->ts_start) {
114 if (s1->ts_start < s2->ts_end)
122 trim_map_zio_compare(const void *x1, const void *x2)
124 const zio_t *z1 = x1;
125 const zio_t *z2 = x2;
127 if (z1->io_offset < z2->io_offset) {
128 if (z1->io_offset + z1->io_size > z2->io_offset)
132 if (z1->io_offset > z2->io_offset) {
133 if (z1->io_offset < z2->io_offset + z2->io_size)
141 trim_map_create(vdev_t *vd)
145 ASSERT(zfs_trim_enabled && !vd->vdev_notrim &&
146 vd->vdev_ops->vdev_op_leaf);
148 tm = kmem_zalloc(sizeof (*tm), KM_SLEEP);
149 mutex_init(&tm->tm_lock, NULL, MUTEX_DEFAULT, NULL);
150 list_create(&tm->tm_head, sizeof (trim_seg_t),
151 offsetof(trim_seg_t, ts_next));
152 list_create(&tm->tm_pending_writes, sizeof (zio_t),
153 offsetof(zio_t, io_trim_link));
154 avl_create(&tm->tm_queued_frees, trim_map_seg_compare,
155 sizeof (trim_seg_t), offsetof(trim_seg_t, ts_node));
156 avl_create(&tm->tm_inflight_frees, trim_map_seg_compare,
157 sizeof (trim_seg_t), offsetof(trim_seg_t, ts_node));
158 avl_create(&tm->tm_inflight_writes, trim_map_zio_compare,
159 sizeof (zio_t), offsetof(zio_t, io_trim_node));
160 vd->vdev_trimmap = tm;
164 trim_map_destroy(vdev_t *vd)
169 ASSERT(vd->vdev_ops->vdev_op_leaf);
171 if (!zfs_trim_enabled)
174 tm = vd->vdev_trimmap;
179 * We may have been called before trim_map_vdev_commit_done()
180 * had a chance to run, so do it now to prune the remaining
183 trim_map_vdev_commit_done(vd->vdev_spa, vd);
185 mutex_enter(&tm->tm_lock);
186 while ((ts = list_head(&tm->tm_head)) != NULL) {
187 avl_remove(&tm->tm_queued_frees, ts);
188 TRIM_MAP_REM(tm, ts);
189 kmem_free(ts, sizeof (*ts));
191 mutex_exit(&tm->tm_lock);
193 avl_destroy(&tm->tm_queued_frees);
194 avl_destroy(&tm->tm_inflight_frees);
195 avl_destroy(&tm->tm_inflight_writes);
196 list_destroy(&tm->tm_pending_writes);
197 list_destroy(&tm->tm_head);
198 mutex_destroy(&tm->tm_lock);
199 kmem_free(tm, sizeof (*tm));
200 vd->vdev_trimmap = NULL;
204 trim_map_segment_add(trim_map_t *tm, uint64_t start, uint64_t end, uint64_t txg)
207 trim_seg_t tsearch, *ts_before, *ts_after, *ts;
208 boolean_t merge_before, merge_after;
211 ASSERT(MUTEX_HELD(&tm->tm_lock));
215 tsearch.ts_start = start;
216 tsearch.ts_end = end;
218 ts = avl_find(&tm->tm_queued_frees, &tsearch, &where);
220 if (start < ts->ts_start)
221 trim_map_segment_add(tm, start, ts->ts_start, txg);
222 if (end > ts->ts_end)
223 trim_map_segment_add(tm, ts->ts_end, end, txg);
227 ts_before = avl_nearest(&tm->tm_queued_frees, where, AVL_BEFORE);
228 ts_after = avl_nearest(&tm->tm_queued_frees, where, AVL_AFTER);
230 merge_before = (ts_before != NULL && ts_before->ts_end == start);
231 merge_after = (ts_after != NULL && ts_after->ts_start == end);
233 if (merge_before && merge_after) {
234 avl_remove(&tm->tm_queued_frees, ts_before);
235 TRIM_MAP_REM(tm, ts_before);
236 TRIM_MAP_REM(tm, ts_after);
237 ts_after->ts_start = ts_before->ts_start;
238 ts_after->ts_txg = txg;
239 ts_after->ts_time = time;
240 TRIM_MAP_ADD(tm, ts_after);
241 kmem_free(ts_before, sizeof (*ts_before));
242 } else if (merge_before) {
243 TRIM_MAP_REM(tm, ts_before);
244 ts_before->ts_end = end;
245 ts_before->ts_txg = txg;
246 ts_before->ts_time = time;
247 TRIM_MAP_ADD(tm, ts_before);
248 } else if (merge_after) {
249 TRIM_MAP_REM(tm, ts_after);
250 ts_after->ts_start = start;
251 ts_after->ts_txg = txg;
252 ts_after->ts_time = time;
253 TRIM_MAP_ADD(tm, ts_after);
255 ts = kmem_alloc(sizeof (*ts), KM_SLEEP);
256 ts->ts_start = start;
260 avl_insert(&tm->tm_queued_frees, ts, where);
261 TRIM_MAP_ADD(tm, ts);
266 trim_map_segment_remove(trim_map_t *tm, trim_seg_t *ts, uint64_t start,
270 boolean_t left_over, right_over;
272 ASSERT(MUTEX_HELD(&tm->tm_lock));
274 left_over = (ts->ts_start < start);
275 right_over = (ts->ts_end > end);
277 TRIM_MAP_REM(tm, ts);
278 if (left_over && right_over) {
279 nts = kmem_alloc(sizeof (*nts), KM_SLEEP);
281 nts->ts_end = ts->ts_end;
282 nts->ts_txg = ts->ts_txg;
283 nts->ts_time = ts->ts_time;
285 avl_insert_here(&tm->tm_queued_frees, nts, ts, AVL_AFTER);
286 TRIM_MAP_ADD(tm, ts);
287 TRIM_MAP_ADD(tm, nts);
288 } else if (left_over) {
290 TRIM_MAP_ADD(tm, ts);
291 } else if (right_over) {
293 TRIM_MAP_ADD(tm, ts);
295 avl_remove(&tm->tm_queued_frees, ts);
296 kmem_free(ts, sizeof (*ts));
301 trim_map_free_locked(trim_map_t *tm, uint64_t start, uint64_t end, uint64_t txg)
305 ASSERT(MUTEX_HELD(&tm->tm_lock));
307 zsearch.io_offset = start;
308 zsearch.io_size = end - start;
310 zs = avl_find(&tm->tm_inflight_writes, &zsearch, NULL);
312 trim_map_segment_add(tm, start, end, txg);
315 if (start < zs->io_offset)
316 trim_map_free_locked(tm, start, zs->io_offset, txg);
317 if (zs->io_offset + zs->io_size < end)
318 trim_map_free_locked(tm, zs->io_offset + zs->io_size, end, txg);
322 trim_map_free(vdev_t *vd, uint64_t offset, uint64_t size, uint64_t txg)
324 trim_map_t *tm = vd->vdev_trimmap;
326 if (!zfs_trim_enabled || vd->vdev_notrim || tm == NULL)
329 mutex_enter(&tm->tm_lock);
330 trim_map_free_locked(tm, offset, TRIM_ZIO_END(vd, offset, size), txg);
331 mutex_exit(&tm->tm_lock);
335 trim_map_write_start(zio_t *zio)
337 vdev_t *vd = zio->io_vd;
338 trim_map_t *tm = vd->vdev_trimmap;
339 trim_seg_t tsearch, *ts;
340 boolean_t left_over, right_over;
343 if (!zfs_trim_enabled || vd->vdev_notrim || tm == NULL)
346 start = zio->io_offset;
347 end = TRIM_ZIO_END(zio->io_vd, start, zio->io_size);
348 tsearch.ts_start = start;
349 tsearch.ts_end = end;
351 mutex_enter(&tm->tm_lock);
354 * Checking for colliding in-flight frees.
356 ts = avl_find(&tm->tm_inflight_frees, &tsearch, NULL);
358 list_insert_tail(&tm->tm_pending_writes, zio);
359 mutex_exit(&tm->tm_lock);
363 ts = avl_find(&tm->tm_queued_frees, &tsearch, NULL);
366 * Loop until all overlapping segments are removed.
369 trim_map_segment_remove(tm, ts, start, end);
370 ts = avl_find(&tm->tm_queued_frees, &tsearch, NULL);
371 } while (ts != NULL);
373 avl_add(&tm->tm_inflight_writes, zio);
375 mutex_exit(&tm->tm_lock);
381 trim_map_write_done(zio_t *zio)
383 vdev_t *vd = zio->io_vd;
384 trim_map_t *tm = vd->vdev_trimmap;
387 * Don't check for vdev_notrim, since the write could have
388 * started before vdev_notrim was set.
390 if (!zfs_trim_enabled || tm == NULL)
393 mutex_enter(&tm->tm_lock);
395 * Don't fail if the write isn't in the tree, since the write
396 * could have started after vdev_notrim was set.
398 if (zio->io_trim_node.avl_child[0] ||
399 zio->io_trim_node.avl_child[1] ||
400 AVL_XPARENT(&zio->io_trim_node) ||
401 tm->tm_inflight_writes.avl_root == &zio->io_trim_node)
402 avl_remove(&tm->tm_inflight_writes, zio);
403 mutex_exit(&tm->tm_lock);
407 * Return the oldest segment (the one with the lowest txg / time) or NULL if:
408 * 1. The list is empty
409 * 2. The first element's txg is greater than txgsafe
410 * 3. The first element's txg is not greater than the txg argument and the
411 * the first element's time is not greater than time argument
414 trim_map_first(trim_map_t *tm, uint64_t txg, uint64_t txgsafe, hrtime_t time,
419 ASSERT(MUTEX_HELD(&tm->tm_lock));
420 VERIFY(txgsafe >= txg);
422 ts = list_head(&tm->tm_head);
423 if (ts != NULL && ts->ts_txg <= txgsafe &&
424 (ts->ts_txg <= txg || ts->ts_time <= time || force))
430 trim_map_vdev_commit(spa_t *spa, zio_t *zio, vdev_t *vd)
432 trim_map_t *tm = vd->vdev_trimmap;
434 uint64_t size, offset, txgtarget, txgsafe;
438 ASSERT(vd->vdev_ops->vdev_op_leaf);
443 timelimit = gethrtime() - (hrtime_t)trim_timeout * NANOSEC;
444 if (vd->vdev_isl2cache) {
445 txgsafe = UINT64_MAX;
446 txgtarget = UINT64_MAX;
448 txgsafe = MIN(spa_last_synced_txg(spa), spa_freeze_txg(spa));
449 if (txgsafe > trim_txg_delay)
450 txgtarget = txgsafe - trim_txg_delay;
455 mutex_enter(&tm->tm_lock);
457 if (tm->tm_pending > trim_vdev_max_pending)
458 hard = (tm->tm_pending - trim_vdev_max_pending) / 4;
459 soft = P2ROUNDUP(hard + tm->tm_pending / trim_timeout + 1, 64);
460 /* Loop until we have sent all outstanding free's */
462 (ts = trim_map_first(tm, txgtarget, txgsafe, timelimit, hard > 0))
464 TRIM_MAP_REM(tm, ts);
465 avl_remove(&tm->tm_queued_frees, ts);
466 avl_add(&tm->tm_inflight_frees, ts);
467 size = ts->ts_end - ts->ts_start;
468 offset = ts->ts_start;
470 * We drop the lock while we call zio_nowait as the IO
471 * scheduler can result in a different IO being run e.g.
472 * a write which would result in a recursive lock.
474 mutex_exit(&tm->tm_lock);
476 zio_nowait(zio_trim(zio, spa, vd, offset, size));
478 soft -= TRIM_MAP_SEGS(size);
479 hard -= TRIM_MAP_SEGS(size);
480 mutex_enter(&tm->tm_lock);
482 mutex_exit(&tm->tm_lock);
486 trim_map_vdev_commit_done(spa_t *spa, vdev_t *vd)
488 trim_map_t *tm = vd->vdev_trimmap;
490 list_t pending_writes;
492 uint64_t start, size;
495 ASSERT(vd->vdev_ops->vdev_op_leaf);
500 mutex_enter(&tm->tm_lock);
501 if (!avl_is_empty(&tm->tm_inflight_frees)) {
503 while ((ts = avl_destroy_nodes(&tm->tm_inflight_frees,
505 kmem_free(ts, sizeof (*ts));
508 list_create(&pending_writes, sizeof (zio_t), offsetof(zio_t,
510 list_move_tail(&pending_writes, &tm->tm_pending_writes);
511 mutex_exit(&tm->tm_lock);
513 while ((zio = list_remove_head(&pending_writes)) != NULL) {
514 zio_vdev_io_reissue(zio);
517 list_destroy(&pending_writes);
521 trim_map_commit(spa_t *spa, zio_t *zio, vdev_t *vd)
528 if (vd->vdev_ops->vdev_op_leaf) {
529 trim_map_vdev_commit(spa, zio, vd);
531 for (c = 0; c < vd->vdev_children; c++)
532 trim_map_commit(spa, zio, vd->vdev_child[c]);
537 trim_map_commit_done(spa_t *spa, vdev_t *vd)
544 if (vd->vdev_ops->vdev_op_leaf) {
545 trim_map_vdev_commit_done(spa, vd);
547 for (c = 0; c < vd->vdev_children; c++)
548 trim_map_commit_done(spa, vd->vdev_child[c]);
553 trim_thread(void *arg)
559 (void) snprintf(curthread->td_name, sizeof(curthread->td_name),
560 "trim %s", spa_name(spa));
564 mutex_enter(&spa->spa_trim_lock);
565 if (spa->spa_trim_thread == NULL) {
566 spa->spa_trim_thread = curthread;
567 cv_signal(&spa->spa_trim_cv);
568 mutex_exit(&spa->spa_trim_lock);
572 (void) cv_timedwait(&spa->spa_trim_cv, &spa->spa_trim_lock,
573 hz * trim_max_interval);
574 mutex_exit(&spa->spa_trim_lock);
576 zio = zio_root(spa, NULL, NULL, ZIO_FLAG_CANFAIL);
578 spa_config_enter(spa, SCL_STATE, FTAG, RW_READER);
579 trim_map_commit(spa, zio, spa->spa_root_vdev);
580 (void) zio_wait(zio);
581 trim_map_commit_done(spa, spa->spa_root_vdev);
582 spa_config_exit(spa, SCL_STATE, FTAG);
587 trim_thread_create(spa_t *spa)
590 if (!zfs_trim_enabled)
593 mutex_init(&spa->spa_trim_lock, NULL, MUTEX_DEFAULT, NULL);
594 cv_init(&spa->spa_trim_cv, NULL, CV_DEFAULT, NULL);
595 mutex_enter(&spa->spa_trim_lock);
596 spa->spa_trim_thread = thread_create(NULL, 0, trim_thread, spa, 0, &p0,
597 TS_RUN, minclsyspri);
598 mutex_exit(&spa->spa_trim_lock);
602 trim_thread_destroy(spa_t *spa)
605 if (!zfs_trim_enabled)
607 if (spa->spa_trim_thread == NULL)
610 mutex_enter(&spa->spa_trim_lock);
611 /* Setting spa_trim_thread to NULL tells the thread to stop. */
612 spa->spa_trim_thread = NULL;
613 cv_signal(&spa->spa_trim_cv);
614 /* The thread will set it back to != NULL on exit. */
615 while (spa->spa_trim_thread == NULL)
616 cv_wait(&spa->spa_trim_cv, &spa->spa_trim_lock);
617 spa->spa_trim_thread = NULL;
618 mutex_exit(&spa->spa_trim_lock);
620 cv_destroy(&spa->spa_trim_cv);
621 mutex_destroy(&spa->spa_trim_lock);
625 trim_thread_wakeup(spa_t *spa)
628 if (!zfs_trim_enabled)
630 if (spa->spa_trim_thread == NULL)
633 mutex_enter(&spa->spa_trim_lock);
634 cv_signal(&spa->spa_trim_cv);
635 mutex_exit(&spa->spa_trim_lock);