]>
Commit | Line | Data |
---|---|---|
7414a03f AJ |
1 | /* |
2 | * Copyright (C) 2011 STRATO. All rights reserved. | |
3 | * | |
4 | * This program is free software; you can redistribute it and/or | |
5 | * modify it under the terms of the GNU General Public | |
6 | * License v2 as published by the Free Software Foundation. | |
7 | * | |
8 | * This program is distributed in the hope that it will be useful, | |
9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
11 | * General Public License for more details. | |
12 | * | |
13 | * You should have received a copy of the GNU General Public | |
14 | * License along with this program; if not, write to the | |
15 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
16 | * Boston, MA 021110-1307, USA. | |
17 | */ | |
18 | ||
19 | #include <linux/sched.h> | |
20 | #include <linux/pagemap.h> | |
21 | #include <linux/writeback.h> | |
22 | #include <linux/blkdev.h> | |
23 | #include <linux/rbtree.h> | |
24 | #include <linux/slab.h> | |
25 | #include <linux/workqueue.h> | |
26 | #include "ctree.h" | |
27 | #include "volumes.h" | |
28 | #include "disk-io.h" | |
29 | #include "transaction.h" | |
8dabb742 | 30 | #include "dev-replace.h" |
7414a03f AJ |
31 | |
32 | #undef DEBUG | |
33 | ||
34 | /* | |
35 | * This is the implementation for the generic read ahead framework. | |
36 | * | |
37 | * To trigger a readahead, btrfs_reada_add must be called. It will start | |
38 | * a read ahead for the given range [start, end) on tree root. The returned | |
39 | * handle can either be used to wait on the readahead to finish | |
40 | * (btrfs_reada_wait), or to send it to the background (btrfs_reada_detach). | |
41 | * | |
42 | * The read ahead works as follows: | |
43 | * On btrfs_reada_add, the root of the tree is inserted into a radix_tree. | |
44 | * reada_start_machine will then search for extents to prefetch and trigger | |
45 | * some reads. When a read finishes for a node, all contained node/leaf | |
46 | * pointers that lie in the given range will also be enqueued. The reads will | |
47 | * be triggered in sequential order, thus giving a big win over a naive | |
48 | * enumeration. It will also make use of multi-device layouts. Each disk | |
49 | * will have its on read pointer and all disks will by utilized in parallel. | |
50 | * Also will no two disks read both sides of a mirror simultaneously, as this | |
51 | * would waste seeking capacity. Instead both disks will read different parts | |
52 | * of the filesystem. | |
53 | * Any number of readaheads can be started in parallel. The read order will be | |
54 | * determined globally, i.e. 2 parallel readaheads will normally finish faster | |
55 | * than the 2 started one after another. | |
56 | */ | |
57 | ||
7414a03f AJ |
58 | #define MAX_IN_FLIGHT 6 |
59 | ||
60 | struct reada_extctl { | |
61 | struct list_head list; | |
62 | struct reada_control *rc; | |
63 | u64 generation; | |
64 | }; | |
65 | ||
66 | struct reada_extent { | |
67 | u64 logical; | |
68 | struct btrfs_key top; | |
7414a03f | 69 | struct list_head extctl; |
99621b44 | 70 | int refcnt; |
7414a03f | 71 | spinlock_t lock; |
94598ba8 | 72 | struct reada_zone *zones[BTRFS_MAX_MIRRORS]; |
7414a03f | 73 | int nzones; |
895a11b8 | 74 | int scheduled; |
7414a03f AJ |
75 | }; |
76 | ||
77 | struct reada_zone { | |
78 | u64 start; | |
79 | u64 end; | |
80 | u64 elems; | |
81 | struct list_head list; | |
82 | spinlock_t lock; | |
83 | int locked; | |
84 | struct btrfs_device *device; | |
94598ba8 SB |
85 | struct btrfs_device *devs[BTRFS_MAX_MIRRORS]; /* full list, incl |
86 | * self */ | |
7414a03f AJ |
87 | int ndevs; |
88 | struct kref refcnt; | |
89 | }; | |
90 | ||
91 | struct reada_machine_work { | |
d458b054 | 92 | struct btrfs_work work; |
7414a03f AJ |
93 | struct btrfs_fs_info *fs_info; |
94 | }; | |
95 | ||
96 | static void reada_extent_put(struct btrfs_fs_info *, struct reada_extent *); | |
97 | static void reada_control_release(struct kref *kref); | |
98 | static void reada_zone_release(struct kref *kref); | |
99 | static void reada_start_machine(struct btrfs_fs_info *fs_info); | |
100 | static void __reada_start_machine(struct btrfs_fs_info *fs_info); | |
101 | ||
102 | static int reada_add_block(struct reada_control *rc, u64 logical, | |
1e7970c0 | 103 | struct btrfs_key *top, u64 generation); |
7414a03f AJ |
104 | |
105 | /* recurses */ | |
106 | /* in case of err, eb might be NULL */ | |
02873e43 ZL |
107 | static void __readahead_hook(struct btrfs_fs_info *fs_info, |
108 | struct reada_extent *re, struct extent_buffer *eb, | |
bcdc51b2 | 109 | int err) |
7414a03f | 110 | { |
7414a03f AJ |
111 | int nritems; |
112 | int i; | |
113 | u64 bytenr; | |
114 | u64 generation; | |
7414a03f | 115 | struct list_head list; |
7414a03f | 116 | |
7414a03f AJ |
117 | spin_lock(&re->lock); |
118 | /* | |
119 | * just take the full list from the extent. afterwards we | |
120 | * don't need the lock anymore | |
121 | */ | |
122 | list_replace_init(&re->extctl, &list); | |
895a11b8 | 123 | re->scheduled = 0; |
7414a03f AJ |
124 | spin_unlock(&re->lock); |
125 | ||
57f16e08 ZL |
126 | /* |
127 | * this is the error case, the extent buffer has not been | |
128 | * read correctly. We won't access anything from it and | |
129 | * just cleanup our data structures. Effectively this will | |
130 | * cut the branch below this node from read ahead. | |
131 | */ | |
132 | if (err) | |
133 | goto cleanup; | |
7414a03f | 134 | |
57f16e08 ZL |
135 | /* |
136 | * FIXME: currently we just set nritems to 0 if this is a leaf, | |
137 | * effectively ignoring the content. In a next step we could | |
138 | * trigger more readahead depending from the content, e.g. | |
139 | * fetch the checksums for the extents in the leaf. | |
140 | */ | |
04998b33 | 141 | if (!btrfs_header_level(eb)) |
57f16e08 ZL |
142 | goto cleanup; |
143 | ||
144 | nritems = btrfs_header_nritems(eb); | |
145 | generation = btrfs_header_generation(eb); | |
7414a03f AJ |
146 | for (i = 0; i < nritems; i++) { |
147 | struct reada_extctl *rec; | |
148 | u64 n_gen; | |
149 | struct btrfs_key key; | |
150 | struct btrfs_key next_key; | |
151 | ||
152 | btrfs_node_key_to_cpu(eb, &key, i); | |
153 | if (i + 1 < nritems) | |
154 | btrfs_node_key_to_cpu(eb, &next_key, i + 1); | |
155 | else | |
156 | next_key = re->top; | |
157 | bytenr = btrfs_node_blockptr(eb, i); | |
158 | n_gen = btrfs_node_ptr_generation(eb, i); | |
159 | ||
160 | list_for_each_entry(rec, &list, list) { | |
161 | struct reada_control *rc = rec->rc; | |
162 | ||
163 | /* | |
164 | * if the generation doesn't match, just ignore this | |
165 | * extctl. This will probably cut off a branch from | |
166 | * prefetch. Alternatively one could start a new (sub-) | |
167 | * prefetch for this branch, starting again from root. | |
168 | * FIXME: move the generation check out of this loop | |
169 | */ | |
170 | #ifdef DEBUG | |
171 | if (rec->generation != generation) { | |
02873e43 ZL |
172 | btrfs_debug(fs_info, |
173 | "generation mismatch for (%llu,%d,%llu) %llu != %llu", | |
174 | key.objectid, key.type, key.offset, | |
175 | rec->generation, generation); | |
7414a03f AJ |
176 | } |
177 | #endif | |
178 | if (rec->generation == generation && | |
179 | btrfs_comp_cpu_keys(&key, &rc->key_end) < 0 && | |
180 | btrfs_comp_cpu_keys(&next_key, &rc->key_start) > 0) | |
1e7970c0 | 181 | reada_add_block(rc, bytenr, &next_key, n_gen); |
7414a03f AJ |
182 | } |
183 | } | |
57f16e08 ZL |
184 | |
185 | cleanup: | |
7414a03f AJ |
186 | /* |
187 | * free extctl records | |
188 | */ | |
189 | while (!list_empty(&list)) { | |
190 | struct reada_control *rc; | |
191 | struct reada_extctl *rec; | |
192 | ||
193 | rec = list_first_entry(&list, struct reada_extctl, list); | |
194 | list_del(&rec->list); | |
195 | rc = rec->rc; | |
196 | kfree(rec); | |
197 | ||
198 | kref_get(&rc->refcnt); | |
199 | if (atomic_dec_and_test(&rc->elems)) { | |
200 | kref_put(&rc->refcnt, reada_control_release); | |
201 | wake_up(&rc->wait); | |
202 | } | |
203 | kref_put(&rc->refcnt, reada_control_release); | |
204 | ||
205 | reada_extent_put(fs_info, re); /* one ref for each entry */ | |
206 | } | |
7414a03f | 207 | |
6e39dbe8 | 208 | return; |
7414a03f AJ |
209 | } |
210 | ||
d48d71aa | 211 | int btree_readahead_hook(struct extent_buffer *eb, int err) |
7414a03f | 212 | { |
d48d71aa | 213 | struct btrfs_fs_info *fs_info = eb->fs_info; |
6e39dbe8 ZL |
214 | int ret = 0; |
215 | struct reada_extent *re; | |
7414a03f | 216 | |
6e39dbe8 ZL |
217 | /* find extent */ |
218 | spin_lock(&fs_info->reada_lock); | |
219 | re = radix_tree_lookup(&fs_info->reada_tree, | |
fc2e901f | 220 | eb->start >> PAGE_SHIFT); |
6e39dbe8 ZL |
221 | if (re) |
222 | re->refcnt++; | |
223 | spin_unlock(&fs_info->reada_lock); | |
224 | if (!re) { | |
225 | ret = -1; | |
226 | goto start_machine; | |
227 | } | |
7414a03f | 228 | |
bcdc51b2 | 229 | __readahead_hook(fs_info, re, eb, err); |
6e39dbe8 | 230 | reada_extent_put(fs_info, re); /* our ref */ |
7414a03f | 231 | |
6e39dbe8 ZL |
232 | start_machine: |
233 | reada_start_machine(fs_info); | |
7414a03f AJ |
234 | return ret; |
235 | } | |
236 | ||
0ceaf282 | 237 | static struct reada_zone *reada_find_zone(struct btrfs_device *dev, u64 logical, |
21ca543e | 238 | struct btrfs_bio *bbio) |
7414a03f | 239 | { |
0ceaf282 | 240 | struct btrfs_fs_info *fs_info = dev->fs_info; |
7414a03f | 241 | int ret; |
7414a03f AJ |
242 | struct reada_zone *zone; |
243 | struct btrfs_block_group_cache *cache = NULL; | |
244 | u64 start; | |
245 | u64 end; | |
246 | int i; | |
247 | ||
7414a03f AJ |
248 | zone = NULL; |
249 | spin_lock(&fs_info->reada_lock); | |
250 | ret = radix_tree_gang_lookup(&dev->reada_zones, (void **)&zone, | |
09cbfeaf | 251 | logical >> PAGE_SHIFT, 1); |
c37f49c7 | 252 | if (ret == 1 && logical >= zone->start && logical <= zone->end) { |
7414a03f | 253 | kref_get(&zone->refcnt); |
7414a03f | 254 | spin_unlock(&fs_info->reada_lock); |
c37f49c7 | 255 | return zone; |
7414a03f AJ |
256 | } |
257 | ||
c37f49c7 ZL |
258 | spin_unlock(&fs_info->reada_lock); |
259 | ||
7414a03f AJ |
260 | cache = btrfs_lookup_block_group(fs_info, logical); |
261 | if (!cache) | |
262 | return NULL; | |
263 | ||
264 | start = cache->key.objectid; | |
265 | end = start + cache->key.offset - 1; | |
266 | btrfs_put_block_group(cache); | |
267 | ||
ed0244fa | 268 | zone = kzalloc(sizeof(*zone), GFP_KERNEL); |
7414a03f AJ |
269 | if (!zone) |
270 | return NULL; | |
271 | ||
cc8385b5 DS |
272 | ret = radix_tree_preload(GFP_KERNEL); |
273 | if (ret) { | |
274 | kfree(zone); | |
275 | return NULL; | |
276 | } | |
277 | ||
7414a03f AJ |
278 | zone->start = start; |
279 | zone->end = end; | |
280 | INIT_LIST_HEAD(&zone->list); | |
281 | spin_lock_init(&zone->lock); | |
282 | zone->locked = 0; | |
283 | kref_init(&zone->refcnt); | |
284 | zone->elems = 0; | |
285 | zone->device = dev; /* our device always sits at index 0 */ | |
21ca543e | 286 | for (i = 0; i < bbio->num_stripes; ++i) { |
7414a03f | 287 | /* bounds have already been checked */ |
21ca543e | 288 | zone->devs[i] = bbio->stripes[i].dev; |
7414a03f | 289 | } |
21ca543e | 290 | zone->ndevs = bbio->num_stripes; |
7414a03f AJ |
291 | |
292 | spin_lock(&fs_info->reada_lock); | |
293 | ret = radix_tree_insert(&dev->reada_zones, | |
09cbfeaf | 294 | (unsigned long)(zone->end >> PAGE_SHIFT), |
7414a03f | 295 | zone); |
7414a03f | 296 | |
8c9c2bf7 | 297 | if (ret == -EEXIST) { |
7414a03f | 298 | kfree(zone); |
8c9c2bf7 | 299 | ret = radix_tree_gang_lookup(&dev->reada_zones, (void **)&zone, |
09cbfeaf | 300 | logical >> PAGE_SHIFT, 1); |
8e9aa51f | 301 | if (ret == 1 && logical >= zone->start && logical <= zone->end) |
8c9c2bf7 | 302 | kref_get(&zone->refcnt); |
8e9aa51f ZL |
303 | else |
304 | zone = NULL; | |
7414a03f | 305 | } |
8c9c2bf7 | 306 | spin_unlock(&fs_info->reada_lock); |
cc8385b5 | 307 | radix_tree_preload_end(); |
7414a03f AJ |
308 | |
309 | return zone; | |
310 | } | |
311 | ||
2ff7e61e | 312 | static struct reada_extent *reada_find_extent(struct btrfs_fs_info *fs_info, |
7414a03f | 313 | u64 logical, |
1e7970c0 | 314 | struct btrfs_key *top) |
7414a03f AJ |
315 | { |
316 | int ret; | |
7414a03f | 317 | struct reada_extent *re = NULL; |
8c9c2bf7 | 318 | struct reada_extent *re_exist = NULL; |
21ca543e | 319 | struct btrfs_bio *bbio = NULL; |
7414a03f | 320 | struct btrfs_device *dev; |
207a232c | 321 | struct btrfs_device *prev_dev; |
7414a03f | 322 | u64 length; |
7cb2c420 | 323 | int real_stripes; |
7414a03f | 324 | int nzones = 0; |
09cbfeaf | 325 | unsigned long index = logical >> PAGE_SHIFT; |
8dabb742 | 326 | int dev_replace_is_ongoing; |
31945021 | 327 | int have_zone = 0; |
7414a03f | 328 | |
7414a03f AJ |
329 | spin_lock(&fs_info->reada_lock); |
330 | re = radix_tree_lookup(&fs_info->reada_tree, index); | |
331 | if (re) | |
99621b44 | 332 | re->refcnt++; |
7414a03f AJ |
333 | spin_unlock(&fs_info->reada_lock); |
334 | ||
8c9c2bf7 | 335 | if (re) |
7414a03f AJ |
336 | return re; |
337 | ||
ed0244fa | 338 | re = kzalloc(sizeof(*re), GFP_KERNEL); |
7414a03f AJ |
339 | if (!re) |
340 | return NULL; | |
341 | ||
7414a03f | 342 | re->logical = logical; |
7414a03f AJ |
343 | re->top = *top; |
344 | INIT_LIST_HEAD(&re->extctl); | |
345 | spin_lock_init(&re->lock); | |
99621b44 | 346 | re->refcnt = 1; |
7414a03f AJ |
347 | |
348 | /* | |
349 | * map block | |
350 | */ | |
994a5d2b | 351 | length = fs_info->nodesize; |
cf8cddd3 CH |
352 | ret = btrfs_map_block(fs_info, BTRFS_MAP_GET_READ_MIRRORS, logical, |
353 | &length, &bbio, 0); | |
994a5d2b | 354 | if (ret || !bbio || length < fs_info->nodesize) |
7414a03f AJ |
355 | goto error; |
356 | ||
94598ba8 | 357 | if (bbio->num_stripes > BTRFS_MAX_MIRRORS) { |
0b246afa | 358 | btrfs_err(fs_info, |
efe120a0 FH |
359 | "readahead: more than %d copies not supported", |
360 | BTRFS_MAX_MIRRORS); | |
7414a03f AJ |
361 | goto error; |
362 | } | |
363 | ||
7cb2c420 OS |
364 | real_stripes = bbio->num_stripes - bbio->num_tgtdevs; |
365 | for (nzones = 0; nzones < real_stripes; ++nzones) { | |
7414a03f AJ |
366 | struct reada_zone *zone; |
367 | ||
21ca543e | 368 | dev = bbio->stripes[nzones].dev; |
7aff8cf4 ZL |
369 | |
370 | /* cannot read ahead on missing device. */ | |
371 | if (!dev->bdev) | |
372 | continue; | |
373 | ||
0ceaf282 | 374 | zone = reada_find_zone(dev, logical, bbio); |
7414a03f | 375 | if (!zone) |
6a159d2a | 376 | continue; |
7414a03f | 377 | |
6a159d2a | 378 | re->zones[re->nzones++] = zone; |
7414a03f AJ |
379 | spin_lock(&zone->lock); |
380 | if (!zone->elems) | |
381 | kref_get(&zone->refcnt); | |
382 | ++zone->elems; | |
383 | spin_unlock(&zone->lock); | |
384 | spin_lock(&fs_info->reada_lock); | |
385 | kref_put(&zone->refcnt, reada_zone_release); | |
386 | spin_unlock(&fs_info->reada_lock); | |
387 | } | |
6a159d2a | 388 | if (re->nzones == 0) { |
7414a03f AJ |
389 | /* not a single zone found, error and out */ |
390 | goto error; | |
391 | } | |
392 | ||
7ef70b4d DS |
393 | ret = radix_tree_preload(GFP_KERNEL); |
394 | if (ret) | |
395 | goto error; | |
396 | ||
7414a03f | 397 | /* insert extent in reada_tree + all per-device trees, all or nothing */ |
73beece9 | 398 | btrfs_dev_replace_lock(&fs_info->dev_replace, 0); |
7414a03f AJ |
399 | spin_lock(&fs_info->reada_lock); |
400 | ret = radix_tree_insert(&fs_info->reada_tree, index, re); | |
8c9c2bf7 AJ |
401 | if (ret == -EEXIST) { |
402 | re_exist = radix_tree_lookup(&fs_info->reada_tree, index); | |
99621b44 | 403 | re_exist->refcnt++; |
8c9c2bf7 | 404 | spin_unlock(&fs_info->reada_lock); |
73beece9 | 405 | btrfs_dev_replace_unlock(&fs_info->dev_replace, 0); |
7ef70b4d | 406 | radix_tree_preload_end(); |
8c9c2bf7 AJ |
407 | goto error; |
408 | } | |
7414a03f AJ |
409 | if (ret) { |
410 | spin_unlock(&fs_info->reada_lock); | |
73beece9 | 411 | btrfs_dev_replace_unlock(&fs_info->dev_replace, 0); |
7ef70b4d | 412 | radix_tree_preload_end(); |
7414a03f AJ |
413 | goto error; |
414 | } | |
7ef70b4d | 415 | radix_tree_preload_end(); |
207a232c | 416 | prev_dev = NULL; |
8dabb742 SB |
417 | dev_replace_is_ongoing = btrfs_dev_replace_is_ongoing( |
418 | &fs_info->dev_replace); | |
6a159d2a ZL |
419 | for (nzones = 0; nzones < re->nzones; ++nzones) { |
420 | dev = re->zones[nzones]->device; | |
421 | ||
207a232c AJ |
422 | if (dev == prev_dev) { |
423 | /* | |
424 | * in case of DUP, just add the first zone. As both | |
425 | * are on the same device, there's nothing to gain | |
426 | * from adding both. | |
427 | * Also, it wouldn't work, as the tree is per device | |
428 | * and adding would fail with EEXIST | |
429 | */ | |
430 | continue; | |
431 | } | |
7aff8cf4 ZL |
432 | if (!dev->bdev) |
433 | continue; | |
434 | ||
8dabb742 SB |
435 | if (dev_replace_is_ongoing && |
436 | dev == fs_info->dev_replace.tgtdev) { | |
437 | /* | |
438 | * as this device is selected for reading only as | |
439 | * a last resort, skip it for read ahead. | |
440 | */ | |
441 | continue; | |
442 | } | |
207a232c | 443 | prev_dev = dev; |
7414a03f AJ |
444 | ret = radix_tree_insert(&dev->reada_extents, index, re); |
445 | if (ret) { | |
6a159d2a ZL |
446 | while (--nzones >= 0) { |
447 | dev = re->zones[nzones]->device; | |
7414a03f | 448 | BUG_ON(dev == NULL); |
ff023aac | 449 | /* ignore whether the entry was inserted */ |
7414a03f AJ |
450 | radix_tree_delete(&dev->reada_extents, index); |
451 | } | |
7414a03f AJ |
452 | radix_tree_delete(&fs_info->reada_tree, index); |
453 | spin_unlock(&fs_info->reada_lock); | |
73beece9 | 454 | btrfs_dev_replace_unlock(&fs_info->dev_replace, 0); |
7414a03f AJ |
455 | goto error; |
456 | } | |
31945021 | 457 | have_zone = 1; |
7414a03f AJ |
458 | } |
459 | spin_unlock(&fs_info->reada_lock); | |
73beece9 | 460 | btrfs_dev_replace_unlock(&fs_info->dev_replace, 0); |
7414a03f | 461 | |
31945021 ZL |
462 | if (!have_zone) |
463 | goto error; | |
464 | ||
6e9606d2 | 465 | btrfs_put_bbio(bbio); |
7414a03f AJ |
466 | return re; |
467 | ||
468 | error: | |
6a159d2a | 469 | for (nzones = 0; nzones < re->nzones; ++nzones) { |
7414a03f AJ |
470 | struct reada_zone *zone; |
471 | ||
7414a03f AJ |
472 | zone = re->zones[nzones]; |
473 | kref_get(&zone->refcnt); | |
474 | spin_lock(&zone->lock); | |
475 | --zone->elems; | |
476 | if (zone->elems == 0) { | |
477 | /* | |
478 | * no fs_info->reada_lock needed, as this can't be | |
479 | * the last ref | |
480 | */ | |
481 | kref_put(&zone->refcnt, reada_zone_release); | |
482 | } | |
483 | spin_unlock(&zone->lock); | |
484 | ||
485 | spin_lock(&fs_info->reada_lock); | |
486 | kref_put(&zone->refcnt, reada_zone_release); | |
487 | spin_unlock(&fs_info->reada_lock); | |
488 | } | |
6e9606d2 | 489 | btrfs_put_bbio(bbio); |
7414a03f | 490 | kfree(re); |
8c9c2bf7 | 491 | return re_exist; |
7414a03f AJ |
492 | } |
493 | ||
7414a03f AJ |
494 | static void reada_extent_put(struct btrfs_fs_info *fs_info, |
495 | struct reada_extent *re) | |
496 | { | |
497 | int i; | |
09cbfeaf | 498 | unsigned long index = re->logical >> PAGE_SHIFT; |
7414a03f AJ |
499 | |
500 | spin_lock(&fs_info->reada_lock); | |
99621b44 | 501 | if (--re->refcnt) { |
7414a03f AJ |
502 | spin_unlock(&fs_info->reada_lock); |
503 | return; | |
504 | } | |
505 | ||
506 | radix_tree_delete(&fs_info->reada_tree, index); | |
507 | for (i = 0; i < re->nzones; ++i) { | |
508 | struct reada_zone *zone = re->zones[i]; | |
509 | ||
510 | radix_tree_delete(&zone->device->reada_extents, index); | |
511 | } | |
512 | ||
513 | spin_unlock(&fs_info->reada_lock); | |
514 | ||
515 | for (i = 0; i < re->nzones; ++i) { | |
516 | struct reada_zone *zone = re->zones[i]; | |
517 | ||
518 | kref_get(&zone->refcnt); | |
519 | spin_lock(&zone->lock); | |
520 | --zone->elems; | |
521 | if (zone->elems == 0) { | |
522 | /* no fs_info->reada_lock needed, as this can't be | |
523 | * the last ref */ | |
524 | kref_put(&zone->refcnt, reada_zone_release); | |
525 | } | |
526 | spin_unlock(&zone->lock); | |
527 | ||
528 | spin_lock(&fs_info->reada_lock); | |
529 | kref_put(&zone->refcnt, reada_zone_release); | |
530 | spin_unlock(&fs_info->reada_lock); | |
531 | } | |
7414a03f AJ |
532 | |
533 | kfree(re); | |
534 | } | |
535 | ||
536 | static void reada_zone_release(struct kref *kref) | |
537 | { | |
538 | struct reada_zone *zone = container_of(kref, struct reada_zone, refcnt); | |
539 | ||
540 | radix_tree_delete(&zone->device->reada_zones, | |
09cbfeaf | 541 | zone->end >> PAGE_SHIFT); |
7414a03f AJ |
542 | |
543 | kfree(zone); | |
544 | } | |
545 | ||
546 | static void reada_control_release(struct kref *kref) | |
547 | { | |
548 | struct reada_control *rc = container_of(kref, struct reada_control, | |
549 | refcnt); | |
550 | ||
551 | kfree(rc); | |
552 | } | |
553 | ||
554 | static int reada_add_block(struct reada_control *rc, u64 logical, | |
1e7970c0 | 555 | struct btrfs_key *top, u64 generation) |
7414a03f | 556 | { |
c28f158e | 557 | struct btrfs_fs_info *fs_info = rc->fs_info; |
7414a03f AJ |
558 | struct reada_extent *re; |
559 | struct reada_extctl *rec; | |
560 | ||
c28f158e | 561 | /* takes one ref */ |
2ff7e61e | 562 | re = reada_find_extent(fs_info, logical, top); |
7414a03f AJ |
563 | if (!re) |
564 | return -1; | |
565 | ||
ed0244fa | 566 | rec = kzalloc(sizeof(*rec), GFP_KERNEL); |
7414a03f | 567 | if (!rec) { |
c28f158e | 568 | reada_extent_put(fs_info, re); |
ddd664f4 | 569 | return -ENOMEM; |
7414a03f AJ |
570 | } |
571 | ||
572 | rec->rc = rc; | |
573 | rec->generation = generation; | |
574 | atomic_inc(&rc->elems); | |
575 | ||
576 | spin_lock(&re->lock); | |
577 | list_add_tail(&rec->list, &re->extctl); | |
578 | spin_unlock(&re->lock); | |
579 | ||
580 | /* leave the ref on the extent */ | |
581 | ||
582 | return 0; | |
583 | } | |
584 | ||
585 | /* | |
586 | * called with fs_info->reada_lock held | |
587 | */ | |
588 | static void reada_peer_zones_set_lock(struct reada_zone *zone, int lock) | |
589 | { | |
590 | int i; | |
09cbfeaf | 591 | unsigned long index = zone->end >> PAGE_SHIFT; |
7414a03f AJ |
592 | |
593 | for (i = 0; i < zone->ndevs; ++i) { | |
594 | struct reada_zone *peer; | |
595 | peer = radix_tree_lookup(&zone->devs[i]->reada_zones, index); | |
596 | if (peer && peer->device != zone->device) | |
597 | peer->locked = lock; | |
598 | } | |
599 | } | |
600 | ||
601 | /* | |
602 | * called with fs_info->reada_lock held | |
603 | */ | |
604 | static int reada_pick_zone(struct btrfs_device *dev) | |
605 | { | |
606 | struct reada_zone *top_zone = NULL; | |
607 | struct reada_zone *top_locked_zone = NULL; | |
608 | u64 top_elems = 0; | |
609 | u64 top_locked_elems = 0; | |
610 | unsigned long index = 0; | |
611 | int ret; | |
612 | ||
613 | if (dev->reada_curr_zone) { | |
614 | reada_peer_zones_set_lock(dev->reada_curr_zone, 0); | |
615 | kref_put(&dev->reada_curr_zone->refcnt, reada_zone_release); | |
616 | dev->reada_curr_zone = NULL; | |
617 | } | |
618 | /* pick the zone with the most elements */ | |
619 | while (1) { | |
620 | struct reada_zone *zone; | |
621 | ||
622 | ret = radix_tree_gang_lookup(&dev->reada_zones, | |
623 | (void **)&zone, index, 1); | |
624 | if (ret == 0) | |
625 | break; | |
09cbfeaf | 626 | index = (zone->end >> PAGE_SHIFT) + 1; |
7414a03f AJ |
627 | if (zone->locked) { |
628 | if (zone->elems > top_locked_elems) { | |
629 | top_locked_elems = zone->elems; | |
630 | top_locked_zone = zone; | |
631 | } | |
632 | } else { | |
633 | if (zone->elems > top_elems) { | |
634 | top_elems = zone->elems; | |
635 | top_zone = zone; | |
636 | } | |
637 | } | |
638 | } | |
639 | if (top_zone) | |
640 | dev->reada_curr_zone = top_zone; | |
641 | else if (top_locked_zone) | |
642 | dev->reada_curr_zone = top_locked_zone; | |
643 | else | |
644 | return 0; | |
645 | ||
646 | dev->reada_next = dev->reada_curr_zone->start; | |
647 | kref_get(&dev->reada_curr_zone->refcnt); | |
648 | reada_peer_zones_set_lock(dev->reada_curr_zone, 1); | |
649 | ||
650 | return 1; | |
651 | } | |
652 | ||
5721b8ad | 653 | static int reada_start_machine_dev(struct btrfs_device *dev) |
7414a03f | 654 | { |
5721b8ad | 655 | struct btrfs_fs_info *fs_info = dev->fs_info; |
7414a03f AJ |
656 | struct reada_extent *re = NULL; |
657 | int mirror_num = 0; | |
658 | struct extent_buffer *eb = NULL; | |
659 | u64 logical; | |
7414a03f AJ |
660 | int ret; |
661 | int i; | |
7414a03f AJ |
662 | |
663 | spin_lock(&fs_info->reada_lock); | |
664 | if (dev->reada_curr_zone == NULL) { | |
665 | ret = reada_pick_zone(dev); | |
666 | if (!ret) { | |
667 | spin_unlock(&fs_info->reada_lock); | |
668 | return 0; | |
669 | } | |
670 | } | |
671 | /* | |
672 | * FIXME currently we issue the reads one extent at a time. If we have | |
673 | * a contiguous block of extents, we could also coagulate them or use | |
674 | * plugging to speed things up | |
675 | */ | |
676 | ret = radix_tree_gang_lookup(&dev->reada_extents, (void **)&re, | |
09cbfeaf | 677 | dev->reada_next >> PAGE_SHIFT, 1); |
50378530 | 678 | if (ret == 0 || re->logical > dev->reada_curr_zone->end) { |
7414a03f AJ |
679 | ret = reada_pick_zone(dev); |
680 | if (!ret) { | |
681 | spin_unlock(&fs_info->reada_lock); | |
682 | return 0; | |
683 | } | |
684 | re = NULL; | |
685 | ret = radix_tree_gang_lookup(&dev->reada_extents, (void **)&re, | |
09cbfeaf | 686 | dev->reada_next >> PAGE_SHIFT, 1); |
7414a03f AJ |
687 | } |
688 | if (ret == 0) { | |
689 | spin_unlock(&fs_info->reada_lock); | |
690 | return 0; | |
691 | } | |
da17066c | 692 | dev->reada_next = re->logical + fs_info->nodesize; |
99621b44 | 693 | re->refcnt++; |
7414a03f AJ |
694 | |
695 | spin_unlock(&fs_info->reada_lock); | |
696 | ||
a3f7fde2 | 697 | spin_lock(&re->lock); |
895a11b8 | 698 | if (re->scheduled || list_empty(&re->extctl)) { |
a3f7fde2 ZL |
699 | spin_unlock(&re->lock); |
700 | reada_extent_put(fs_info, re); | |
701 | return 0; | |
702 | } | |
895a11b8 | 703 | re->scheduled = 1; |
a3f7fde2 ZL |
704 | spin_unlock(&re->lock); |
705 | ||
7414a03f AJ |
706 | /* |
707 | * find mirror num | |
708 | */ | |
709 | for (i = 0; i < re->nzones; ++i) { | |
710 | if (re->zones[i]->device == dev) { | |
711 | mirror_num = i + 1; | |
712 | break; | |
713 | } | |
714 | } | |
715 | logical = re->logical; | |
7414a03f | 716 | |
7414a03f | 717 | atomic_inc(&dev->reada_in_flight); |
2ff7e61e | 718 | ret = reada_tree_block_flagged(fs_info, logical, mirror_num, &eb); |
7414a03f | 719 | if (ret) |
bcdc51b2 | 720 | __readahead_hook(fs_info, re, NULL, ret); |
7414a03f | 721 | else if (eb) |
bcdc51b2 | 722 | __readahead_hook(fs_info, re, eb, ret); |
7414a03f AJ |
723 | |
724 | if (eb) | |
725 | free_extent_buffer(eb); | |
726 | ||
895a11b8 | 727 | atomic_dec(&dev->reada_in_flight); |
b257cf50 ZL |
728 | reada_extent_put(fs_info, re); |
729 | ||
7414a03f AJ |
730 | return 1; |
731 | ||
732 | } | |
733 | ||
d458b054 | 734 | static void reada_start_machine_worker(struct btrfs_work *work) |
7414a03f AJ |
735 | { |
736 | struct reada_machine_work *rmw; | |
737 | struct btrfs_fs_info *fs_info; | |
3d136a11 | 738 | int old_ioprio; |
7414a03f AJ |
739 | |
740 | rmw = container_of(work, struct reada_machine_work, work); | |
741 | fs_info = rmw->fs_info; | |
742 | ||
743 | kfree(rmw); | |
744 | ||
3d136a11 SB |
745 | old_ioprio = IOPRIO_PRIO_VALUE(task_nice_ioclass(current), |
746 | task_nice_ioprio(current)); | |
747 | set_task_ioprio(current, BTRFS_IOPRIO_READA); | |
7414a03f | 748 | __reada_start_machine(fs_info); |
3d136a11 | 749 | set_task_ioprio(current, old_ioprio); |
2fefd558 ZL |
750 | |
751 | atomic_dec(&fs_info->reada_works_cnt); | |
7414a03f AJ |
752 | } |
753 | ||
754 | static void __reada_start_machine(struct btrfs_fs_info *fs_info) | |
755 | { | |
756 | struct btrfs_device *device; | |
757 | struct btrfs_fs_devices *fs_devices = fs_info->fs_devices; | |
758 | u64 enqueued; | |
759 | u64 total = 0; | |
760 | int i; | |
761 | ||
762 | do { | |
763 | enqueued = 0; | |
ce7791ff | 764 | mutex_lock(&fs_devices->device_list_mutex); |
7414a03f AJ |
765 | list_for_each_entry(device, &fs_devices->devices, dev_list) { |
766 | if (atomic_read(&device->reada_in_flight) < | |
767 | MAX_IN_FLIGHT) | |
5721b8ad | 768 | enqueued += reada_start_machine_dev(device); |
7414a03f | 769 | } |
ce7791ff | 770 | mutex_unlock(&fs_devices->device_list_mutex); |
7414a03f AJ |
771 | total += enqueued; |
772 | } while (enqueued && total < 10000); | |
773 | ||
774 | if (enqueued == 0) | |
775 | return; | |
776 | ||
777 | /* | |
778 | * If everything is already in the cache, this is effectively single | |
779 | * threaded. To a) not hold the caller for too long and b) to utilize | |
780 | * more cores, we broke the loop above after 10000 iterations and now | |
781 | * enqueue to workers to finish it. This will distribute the load to | |
782 | * the cores. | |
783 | */ | |
2fefd558 | 784 | for (i = 0; i < 2; ++i) { |
7414a03f | 785 | reada_start_machine(fs_info); |
2fefd558 ZL |
786 | if (atomic_read(&fs_info->reada_works_cnt) > |
787 | BTRFS_MAX_MIRRORS * 2) | |
788 | break; | |
789 | } | |
7414a03f AJ |
790 | } |
791 | ||
792 | static void reada_start_machine(struct btrfs_fs_info *fs_info) | |
793 | { | |
794 | struct reada_machine_work *rmw; | |
795 | ||
ed0244fa | 796 | rmw = kzalloc(sizeof(*rmw), GFP_KERNEL); |
7414a03f AJ |
797 | if (!rmw) { |
798 | /* FIXME we cannot handle this properly right now */ | |
799 | BUG(); | |
800 | } | |
9e0af237 LB |
801 | btrfs_init_work(&rmw->work, btrfs_readahead_helper, |
802 | reada_start_machine_worker, NULL, NULL); | |
7414a03f AJ |
803 | rmw->fs_info = fs_info; |
804 | ||
736cfa15 | 805 | btrfs_queue_work(fs_info->readahead_workers, &rmw->work); |
2fefd558 | 806 | atomic_inc(&fs_info->reada_works_cnt); |
7414a03f AJ |
807 | } |
808 | ||
809 | #ifdef DEBUG | |
810 | static void dump_devs(struct btrfs_fs_info *fs_info, int all) | |
811 | { | |
812 | struct btrfs_device *device; | |
813 | struct btrfs_fs_devices *fs_devices = fs_info->fs_devices; | |
814 | unsigned long index; | |
815 | int ret; | |
816 | int i; | |
817 | int j; | |
818 | int cnt; | |
819 | ||
820 | spin_lock(&fs_info->reada_lock); | |
821 | list_for_each_entry(device, &fs_devices->devices, dev_list) { | |
ab8d0fc4 | 822 | btrfs_debug(fs_info, "dev %lld has %d in flight", device->devid, |
7414a03f AJ |
823 | atomic_read(&device->reada_in_flight)); |
824 | index = 0; | |
825 | while (1) { | |
826 | struct reada_zone *zone; | |
827 | ret = radix_tree_gang_lookup(&device->reada_zones, | |
828 | (void **)&zone, index, 1); | |
829 | if (ret == 0) | |
830 | break; | |
62e85577 | 831 | pr_debug(" zone %llu-%llu elems %llu locked %d devs", |
ab8d0fc4 JM |
832 | zone->start, zone->end, zone->elems, |
833 | zone->locked); | |
7414a03f | 834 | for (j = 0; j < zone->ndevs; ++j) { |
62e85577 | 835 | pr_cont(" %lld", |
7414a03f AJ |
836 | zone->devs[j]->devid); |
837 | } | |
838 | if (device->reada_curr_zone == zone) | |
62e85577 | 839 | pr_cont(" curr off %llu", |
7414a03f | 840 | device->reada_next - zone->start); |
62e85577 | 841 | pr_cont("\n"); |
09cbfeaf | 842 | index = (zone->end >> PAGE_SHIFT) + 1; |
7414a03f AJ |
843 | } |
844 | cnt = 0; | |
845 | index = 0; | |
846 | while (all) { | |
847 | struct reada_extent *re = NULL; | |
848 | ||
849 | ret = radix_tree_gang_lookup(&device->reada_extents, | |
850 | (void **)&re, index, 1); | |
851 | if (ret == 0) | |
852 | break; | |
62e85577 | 853 | pr_debug(" re: logical %llu size %u empty %d scheduled %d", |
da17066c | 854 | re->logical, fs_info->nodesize, |
895a11b8 | 855 | list_empty(&re->extctl), re->scheduled); |
7414a03f AJ |
856 | |
857 | for (i = 0; i < re->nzones; ++i) { | |
62e85577 | 858 | pr_cont(" zone %llu-%llu devs", |
7414a03f AJ |
859 | re->zones[i]->start, |
860 | re->zones[i]->end); | |
861 | for (j = 0; j < re->zones[i]->ndevs; ++j) { | |
62e85577 | 862 | pr_cont(" %lld", |
7414a03f AJ |
863 | re->zones[i]->devs[j]->devid); |
864 | } | |
865 | } | |
62e85577 | 866 | pr_cont("\n"); |
09cbfeaf | 867 | index = (re->logical >> PAGE_SHIFT) + 1; |
7414a03f AJ |
868 | if (++cnt > 15) |
869 | break; | |
870 | } | |
871 | } | |
872 | ||
873 | index = 0; | |
874 | cnt = 0; | |
875 | while (all) { | |
876 | struct reada_extent *re = NULL; | |
877 | ||
878 | ret = radix_tree_gang_lookup(&fs_info->reada_tree, (void **)&re, | |
879 | index, 1); | |
880 | if (ret == 0) | |
881 | break; | |
895a11b8 | 882 | if (!re->scheduled) { |
09cbfeaf | 883 | index = (re->logical >> PAGE_SHIFT) + 1; |
7414a03f AJ |
884 | continue; |
885 | } | |
62e85577 | 886 | pr_debug("re: logical %llu size %u list empty %d scheduled %d", |
da17066c | 887 | re->logical, fs_info->nodesize, |
895a11b8 | 888 | list_empty(&re->extctl), re->scheduled); |
7414a03f | 889 | for (i = 0; i < re->nzones; ++i) { |
62e85577 | 890 | pr_cont(" zone %llu-%llu devs", |
7414a03f AJ |
891 | re->zones[i]->start, |
892 | re->zones[i]->end); | |
8afd6841 | 893 | for (j = 0; j < re->zones[i]->ndevs; ++j) { |
62e85577 | 894 | pr_cont(" %lld", |
8afd6841 | 895 | re->zones[i]->devs[j]->devid); |
7414a03f AJ |
896 | } |
897 | } | |
62e85577 | 898 | pr_cont("\n"); |
09cbfeaf | 899 | index = (re->logical >> PAGE_SHIFT) + 1; |
7414a03f AJ |
900 | } |
901 | spin_unlock(&fs_info->reada_lock); | |
902 | } | |
903 | #endif | |
904 | ||
905 | /* | |
906 | * interface | |
907 | */ | |
908 | struct reada_control *btrfs_reada_add(struct btrfs_root *root, | |
909 | struct btrfs_key *key_start, struct btrfs_key *key_end) | |
910 | { | |
911 | struct reada_control *rc; | |
912 | u64 start; | |
913 | u64 generation; | |
ddd664f4 | 914 | int ret; |
7414a03f AJ |
915 | struct extent_buffer *node; |
916 | static struct btrfs_key max_key = { | |
917 | .objectid = (u64)-1, | |
918 | .type = (u8)-1, | |
919 | .offset = (u64)-1 | |
920 | }; | |
921 | ||
ed0244fa | 922 | rc = kzalloc(sizeof(*rc), GFP_KERNEL); |
7414a03f AJ |
923 | if (!rc) |
924 | return ERR_PTR(-ENOMEM); | |
925 | ||
c28f158e | 926 | rc->fs_info = root->fs_info; |
7414a03f AJ |
927 | rc->key_start = *key_start; |
928 | rc->key_end = *key_end; | |
929 | atomic_set(&rc->elems, 0); | |
930 | init_waitqueue_head(&rc->wait); | |
931 | kref_init(&rc->refcnt); | |
932 | kref_get(&rc->refcnt); /* one ref for having elements */ | |
933 | ||
934 | node = btrfs_root_node(root); | |
935 | start = node->start; | |
7414a03f AJ |
936 | generation = btrfs_header_generation(node); |
937 | free_extent_buffer(node); | |
938 | ||
1e7970c0 | 939 | ret = reada_add_block(rc, start, &max_key, generation); |
ddd664f4 | 940 | if (ret) { |
ff023aac | 941 | kfree(rc); |
ddd664f4 | 942 | return ERR_PTR(ret); |
ff023aac | 943 | } |
7414a03f AJ |
944 | |
945 | reada_start_machine(root->fs_info); | |
946 | ||
947 | return rc; | |
948 | } | |
949 | ||
950 | #ifdef DEBUG | |
951 | int btrfs_reada_wait(void *handle) | |
952 | { | |
953 | struct reada_control *rc = handle; | |
c28f158e | 954 | struct btrfs_fs_info *fs_info = rc->fs_info; |
7414a03f AJ |
955 | |
956 | while (atomic_read(&rc->elems)) { | |
4fe7a0e1 ZL |
957 | if (!atomic_read(&fs_info->reada_works_cnt)) |
958 | reada_start_machine(fs_info); | |
7414a03f AJ |
959 | wait_event_timeout(rc->wait, atomic_read(&rc->elems) == 0, |
960 | 5 * HZ); | |
0b246afa | 961 | dump_devs(fs_info, atomic_read(&rc->elems) < 10 ? 1 : 0); |
7414a03f AJ |
962 | } |
963 | ||
0b246afa | 964 | dump_devs(fs_info, atomic_read(&rc->elems) < 10 ? 1 : 0); |
7414a03f AJ |
965 | |
966 | kref_put(&rc->refcnt, reada_control_release); | |
967 | ||
968 | return 0; | |
969 | } | |
970 | #else | |
971 | int btrfs_reada_wait(void *handle) | |
972 | { | |
973 | struct reada_control *rc = handle; | |
c28f158e | 974 | struct btrfs_fs_info *fs_info = rc->fs_info; |
7414a03f AJ |
975 | |
976 | while (atomic_read(&rc->elems)) { | |
4fe7a0e1 ZL |
977 | if (!atomic_read(&fs_info->reada_works_cnt)) |
978 | reada_start_machine(fs_info); | |
979 | wait_event_timeout(rc->wait, atomic_read(&rc->elems) == 0, | |
980 | (HZ + 9) / 10); | |
7414a03f AJ |
981 | } |
982 | ||
983 | kref_put(&rc->refcnt, reada_control_release); | |
984 | ||
985 | return 0; | |
986 | } | |
987 | #endif | |
988 | ||
989 | void btrfs_reada_detach(void *handle) | |
990 | { | |
991 | struct reada_control *rc = handle; | |
992 | ||
993 | kref_put(&rc->refcnt, reada_control_release); | |
994 | } |