Print this page
4374 dn_free_ranges should use range_tree_t
Reviewed by: George Wilson <george.wilson@delphix.com>
Reviewed by: Max Grossman <max.grossman@delphix.com>
Reviewed by: Christopher Siden <christopher.siden@delphix.com
Reviewed by: Garrett D'Amore <garrett@damore.org>
Reviewed by: Dan McDonald <danmcd@omniti.com>
Approved by: Dan McDonald <danmcd@omniti.com>
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/uts/common/fs/zfs/range_tree.c
+++ new/usr/src/uts/common/fs/zfs/range_tree.c
1 1 /*
2 2 * CDDL HEADER START
3 3 *
4 4 * The contents of this file are subject to the terms of the
5 5 * Common Development and Distribution License (the "License").
6 6 * You may not use this file except in compliance with the License.
7 7 *
8 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 9 * or http://www.opensolaris.org/os/licensing.
10 10 * See the License for the specific language governing permissions
11 11 * and limitations under the License.
12 12 *
13 13 * When distributing Covered Code, include this CDDL HEADER in each
14 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 15 * If applicable, add the following below this CDDL HEADER, with the
|
↓ open down ↓ |
15 lines elided |
↑ open up ↑ |
16 16 * fields enclosed by brackets "[]" replaced with your own identifying
17 17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 18 *
19 19 * CDDL HEADER END
20 20 */
21 21 /*
22 22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 23 * Use is subject to license terms.
24 24 */
25 25 /*
26 - * Copyright (c) 2013 by Delphix. All rights reserved.
26 + * Copyright (c) 2013, 2014 by Delphix. All rights reserved.
27 27 */
28 28
29 29 #include <sys/zfs_context.h>
30 30 #include <sys/spa.h>
31 31 #include <sys/dmu.h>
32 32 #include <sys/dnode.h>
33 33 #include <sys/zio.h>
34 34 #include <sys/range_tree.h>
35 35
36 36 static kmem_cache_t *range_seg_cache;
37 37
38 38 void
39 39 range_tree_init(void)
40 40 {
41 41 ASSERT(range_seg_cache == NULL);
42 42 range_seg_cache = kmem_cache_create("range_seg_cache",
43 43 sizeof (range_seg_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
44 44 }
45 45
46 46 void
47 47 range_tree_fini(void)
48 48 {
49 49 kmem_cache_destroy(range_seg_cache);
50 50 range_seg_cache = NULL;
51 51 }
52 52
|
↓ open down ↓ |
16 lines elided |
↑ open up ↑ |
53 53 void
54 54 range_tree_stat_verify(range_tree_t *rt)
55 55 {
56 56 range_seg_t *rs;
57 57 uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
58 58 int i;
59 59
60 60 for (rs = avl_first(&rt->rt_root); rs != NULL;
61 61 rs = AVL_NEXT(&rt->rt_root, rs)) {
62 62 uint64_t size = rs->rs_end - rs->rs_start;
63 - int idx = highbit(size) - 1;
63 + int idx = highbit64(size) - 1;
64 64
65 65 hist[idx]++;
66 66 ASSERT3U(hist[idx], !=, 0);
67 67 }
68 68
69 69 for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
70 70 if (hist[i] != rt->rt_histogram[i]) {
71 71 zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu",
72 72 i, hist, hist[i], rt->rt_histogram[i]);
73 73 }
74 74 VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
75 75 }
76 76 }
77 77
78 78 static void
79 79 range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
80 80 {
81 81 uint64_t size = rs->rs_end - rs->rs_start;
82 - int idx = highbit(size) - 1;
82 + int idx = highbit64(size) - 1;
83 83
84 84 ASSERT3U(idx, <,
85 85 sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
86 86
87 87 ASSERT(MUTEX_HELD(rt->rt_lock));
88 88 rt->rt_histogram[idx]++;
89 89 ASSERT3U(rt->rt_histogram[idx], !=, 0);
90 90 }
91 91
92 92 static void
93 93 range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
94 94 {
95 95 uint64_t size = rs->rs_end - rs->rs_start;
96 - int idx = highbit(size) - 1;
96 + int idx = highbit64(size) - 1;
97 97
98 98 ASSERT3U(idx, <,
99 99 sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
100 100
101 101 ASSERT(MUTEX_HELD(rt->rt_lock));
102 102 ASSERT3U(rt->rt_histogram[idx], !=, 0);
103 103 rt->rt_histogram[idx]--;
104 104 }
105 105
106 106 /*
107 107 * NOTE: caller is responsible for all locking.
108 108 */
109 109 static int
110 110 range_tree_seg_compare(const void *x1, const void *x2)
111 111 {
112 112 const range_seg_t *r1 = x1;
113 113 const range_seg_t *r2 = x2;
114 114
115 115 if (r1->rs_start < r2->rs_start) {
116 116 if (r1->rs_end > r2->rs_start)
117 117 return (0);
118 118 return (-1);
119 119 }
120 120 if (r1->rs_start > r2->rs_start) {
121 121 if (r1->rs_start < r2->rs_end)
122 122 return (0);
123 123 return (1);
124 124 }
125 125 return (0);
126 126 }
127 127
128 128 range_tree_t *
129 129 range_tree_create(range_tree_ops_t *ops, void *arg, kmutex_t *lp)
130 130 {
131 131 range_tree_t *rt;
132 132
133 133 rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP);
134 134
135 135 avl_create(&rt->rt_root, range_tree_seg_compare,
136 136 sizeof (range_seg_t), offsetof(range_seg_t, rs_node));
137 137
138 138 rt->rt_lock = lp;
139 139 rt->rt_ops = ops;
140 140 rt->rt_arg = arg;
141 141
142 142 if (rt->rt_ops != NULL)
143 143 rt->rt_ops->rtop_create(rt, rt->rt_arg);
144 144
145 145 return (rt);
146 146 }
147 147
148 148 void
149 149 range_tree_destroy(range_tree_t *rt)
150 150 {
151 151 VERIFY0(rt->rt_space);
152 152
153 153 if (rt->rt_ops != NULL)
154 154 rt->rt_ops->rtop_destroy(rt, rt->rt_arg);
155 155
156 156 avl_destroy(&rt->rt_root);
157 157 kmem_free(rt, sizeof (*rt));
158 158 }
159 159
160 160 void
161 161 range_tree_add(void *arg, uint64_t start, uint64_t size)
162 162 {
163 163 range_tree_t *rt = arg;
164 164 avl_index_t where;
165 165 range_seg_t rsearch, *rs_before, *rs_after, *rs;
166 166 uint64_t end = start + size;
167 167 boolean_t merge_before, merge_after;
168 168
169 169 ASSERT(MUTEX_HELD(rt->rt_lock));
170 170 VERIFY(size != 0);
171 171
172 172 rsearch.rs_start = start;
173 173 rsearch.rs_end = end;
174 174 rs = avl_find(&rt->rt_root, &rsearch, &where);
175 175
176 176 if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end) {
177 177 zfs_panic_recover("zfs: allocating allocated segment"
178 178 "(offset=%llu size=%llu)\n",
179 179 (longlong_t)start, (longlong_t)size);
180 180 return;
181 181 }
182 182
183 183 /* Make sure we don't overlap with either of our neighbors */
184 184 VERIFY(rs == NULL);
185 185
186 186 rs_before = avl_nearest(&rt->rt_root, where, AVL_BEFORE);
187 187 rs_after = avl_nearest(&rt->rt_root, where, AVL_AFTER);
188 188
189 189 merge_before = (rs_before != NULL && rs_before->rs_end == start);
190 190 merge_after = (rs_after != NULL && rs_after->rs_start == end);
191 191
192 192 if (merge_before && merge_after) {
193 193 avl_remove(&rt->rt_root, rs_before);
194 194 if (rt->rt_ops != NULL) {
195 195 rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
196 196 rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
197 197 }
198 198
199 199 range_tree_stat_decr(rt, rs_before);
200 200 range_tree_stat_decr(rt, rs_after);
201 201
202 202 rs_after->rs_start = rs_before->rs_start;
203 203 kmem_cache_free(range_seg_cache, rs_before);
204 204 rs = rs_after;
205 205 } else if (merge_before) {
206 206 if (rt->rt_ops != NULL)
207 207 rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
208 208
209 209 range_tree_stat_decr(rt, rs_before);
210 210
211 211 rs_before->rs_end = end;
212 212 rs = rs_before;
213 213 } else if (merge_after) {
214 214 if (rt->rt_ops != NULL)
215 215 rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
216 216
217 217 range_tree_stat_decr(rt, rs_after);
218 218
219 219 rs_after->rs_start = start;
220 220 rs = rs_after;
221 221 } else {
222 222 rs = kmem_cache_alloc(range_seg_cache, KM_SLEEP);
223 223 rs->rs_start = start;
224 224 rs->rs_end = end;
225 225 avl_insert(&rt->rt_root, rs, where);
226 226 }
227 227
228 228 if (rt->rt_ops != NULL)
229 229 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
230 230
231 231 range_tree_stat_incr(rt, rs);
232 232 rt->rt_space += size;
233 233 }
234 234
235 235 void
236 236 range_tree_remove(void *arg, uint64_t start, uint64_t size)
237 237 {
238 238 range_tree_t *rt = arg;
239 239 avl_index_t where;
240 240 range_seg_t rsearch, *rs, *newseg;
241 241 uint64_t end = start + size;
242 242 boolean_t left_over, right_over;
243 243
244 244 ASSERT(MUTEX_HELD(rt->rt_lock));
245 245 VERIFY3U(size, !=, 0);
246 246 VERIFY3U(size, <=, rt->rt_space);
247 247
248 248 rsearch.rs_start = start;
249 249 rsearch.rs_end = end;
250 250 rs = avl_find(&rt->rt_root, &rsearch, &where);
251 251
252 252 /* Make sure we completely overlap with someone */
253 253 if (rs == NULL) {
254 254 zfs_panic_recover("zfs: freeing free segment "
255 255 "(offset=%llu size=%llu)",
256 256 (longlong_t)start, (longlong_t)size);
257 257 return;
258 258 }
259 259 VERIFY3U(rs->rs_start, <=, start);
260 260 VERIFY3U(rs->rs_end, >=, end);
261 261
262 262 left_over = (rs->rs_start != start);
263 263 right_over = (rs->rs_end != end);
264 264
265 265 range_tree_stat_decr(rt, rs);
266 266
267 267 if (rt->rt_ops != NULL)
268 268 rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
269 269
270 270 if (left_over && right_over) {
271 271 newseg = kmem_cache_alloc(range_seg_cache, KM_SLEEP);
272 272 newseg->rs_start = end;
273 273 newseg->rs_end = rs->rs_end;
274 274 range_tree_stat_incr(rt, newseg);
275 275
276 276 rs->rs_end = start;
277 277
278 278 avl_insert_here(&rt->rt_root, newseg, rs, AVL_AFTER);
279 279 if (rt->rt_ops != NULL)
280 280 rt->rt_ops->rtop_add(rt, newseg, rt->rt_arg);
281 281 } else if (left_over) {
282 282 rs->rs_end = start;
283 283 } else if (right_over) {
284 284 rs->rs_start = end;
285 285 } else {
286 286 avl_remove(&rt->rt_root, rs);
287 287 kmem_cache_free(range_seg_cache, rs);
288 288 rs = NULL;
289 289 }
290 290
291 291 if (rs != NULL) {
|
↓ open down ↓ |
185 lines elided |
↑ open up ↑ |
292 292 range_tree_stat_incr(rt, rs);
293 293
294 294 if (rt->rt_ops != NULL)
295 295 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
296 296 }
297 297
298 298 rt->rt_space -= size;
299 299 }
300 300
301 301 static range_seg_t *
302 -range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size,
303 - avl_index_t *wherep)
302 +range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size)
304 303 {
305 - range_seg_t rsearch, *rs;
304 + avl_index_t where;
305 + range_seg_t rsearch;
306 306 uint64_t end = start + size;
307 307
308 308 ASSERT(MUTEX_HELD(rt->rt_lock));
309 309 VERIFY(size != 0);
310 310
311 311 rsearch.rs_start = start;
312 312 rsearch.rs_end = end;
313 - rs = avl_find(&rt->rt_root, &rsearch, wherep);
313 + return (avl_find(&rt->rt_root, &rsearch, &where));
314 +}
314 315
315 - if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end)
316 +static range_seg_t *
317 +range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size)
318 +{
319 + range_seg_t *rs = range_tree_find_impl(rt, start, size);
320 + if (rs != NULL && rs->rs_start <= start && rs->rs_end >= start + size)
316 321 return (rs);
317 322 return (NULL);
318 323 }
319 324
320 325 void
321 326 range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size)
322 327 {
323 328 range_seg_t *rs;
324 - avl_index_t where;
325 329
326 330 mutex_enter(rt->rt_lock);
327 - rs = range_tree_find(rt, off, size, &where);
331 + rs = range_tree_find(rt, off, size);
328 332 if (rs != NULL)
329 333 panic("freeing free block; rs=%p", (void *)rs);
330 334 mutex_exit(rt->rt_lock);
331 335 }
332 336
333 337 boolean_t
334 338 range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
335 339 {
336 - avl_index_t where;
340 + return (range_tree_find(rt, start, size) != NULL);
341 +}
337 342
338 - return (range_tree_find(rt, start, size, &where) != NULL);
343 +/*
344 + * Ensure that this range is not in the tree, regardless of whether
345 + * it is currently in the tree.
346 + */
347 +void
348 +range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size)
349 +{
350 + range_seg_t *rs;
351 +
352 + while ((rs = range_tree_find_impl(rt, start, size)) != NULL) {
353 + uint64_t free_start = MAX(rs->rs_start, start);
354 + uint64_t free_end = MIN(rs->rs_end, start + size);
355 + range_tree_remove(rt, free_start, free_end - free_start);
356 + }
339 357 }
340 358
341 359 void
342 360 range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
343 361 {
344 362 range_tree_t *rt;
345 363
346 364 ASSERT(MUTEX_HELD((*rtsrc)->rt_lock));
347 365 ASSERT0(range_tree_space(*rtdst));
348 366 ASSERT0(avl_numnodes(&(*rtdst)->rt_root));
349 367
350 368 rt = *rtsrc;
351 369 *rtsrc = *rtdst;
352 370 *rtdst = rt;
353 371 }
354 372
355 373 void
356 374 range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)
357 375 {
358 376 range_seg_t *rs;
359 377 void *cookie = NULL;
360 378
361 379 ASSERT(MUTEX_HELD(rt->rt_lock));
362 380
363 381 if (rt->rt_ops != NULL)
364 382 rt->rt_ops->rtop_vacate(rt, rt->rt_arg);
365 383
366 384 while ((rs = avl_destroy_nodes(&rt->rt_root, &cookie)) != NULL) {
367 385 if (func != NULL)
368 386 func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
369 387 kmem_cache_free(range_seg_cache, rs);
370 388 }
371 389
372 390 bzero(rt->rt_histogram, sizeof (rt->rt_histogram));
373 391 rt->rt_space = 0;
374 392 }
375 393
376 394 void
377 395 range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg)
378 396 {
379 397 range_seg_t *rs;
380 398
381 399 ASSERT(MUTEX_HELD(rt->rt_lock));
382 400
383 401 for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs))
384 402 func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
385 403 }
386 404
387 405 uint64_t
388 406 range_tree_space(range_tree_t *rt)
389 407 {
390 408 return (rt->rt_space);
391 409 }
|
↓ open down ↓ |
43 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX