pnfs/blocklayout: use the device id cache
[karo-tx-linux.git] / fs / nfs / blocklayout / extent_tree.c
1 /*
2  * Copyright (c) 2014 Christoph Hellwig.
3  */
4
5 #include "blocklayout.h"
6
7 #define NFSDBG_FACILITY         NFSDBG_PNFS_LD
8
9 static inline struct pnfs_block_extent *
10 ext_node(struct rb_node *node)
11 {
12         return rb_entry(node, struct pnfs_block_extent, be_node);
13 }
14
15 static struct pnfs_block_extent *
16 ext_tree_first(struct rb_root *root)
17 {
18         struct rb_node *node = rb_first(root);
19         return node ? ext_node(node) : NULL;
20 }
21
22 static struct pnfs_block_extent *
23 ext_tree_prev(struct pnfs_block_extent *be)
24 {
25         struct rb_node *node = rb_prev(&be->be_node);
26         return node ? ext_node(node) : NULL;
27 }
28
29 static struct pnfs_block_extent *
30 ext_tree_next(struct pnfs_block_extent *be)
31 {
32         struct rb_node *node = rb_next(&be->be_node);
33         return node ? ext_node(node) : NULL;
34 }
35
36 static inline sector_t
37 ext_f_end(struct pnfs_block_extent *be)
38 {
39         return be->be_f_offset + be->be_length;
40 }
41
42 static struct pnfs_block_extent *
43 __ext_tree_search(struct rb_root *root, sector_t start)
44 {
45         struct rb_node *node = root->rb_node;
46         struct pnfs_block_extent *be = NULL;
47
48         while (node) {
49                 be = ext_node(node);
50                 if (start < be->be_f_offset)
51                         node = node->rb_left;
52                 else if (start >= ext_f_end(be))
53                         node = node->rb_right;
54                 else
55                         return be;
56         }
57
58         if (be) {
59                 if (start < be->be_f_offset)
60                         return be;
61
62                 if (start >= ext_f_end(be))
63                         return ext_tree_next(be);
64         }
65
66         return NULL;
67 }
68
69 static bool
70 ext_can_merge(struct pnfs_block_extent *be1, struct pnfs_block_extent *be2)
71 {
72         if (be1->be_state != be2->be_state)
73                 return false;
74         if (be1->be_device != be2->be_device)
75                 return false;
76
77         if (be1->be_f_offset + be1->be_length != be2->be_f_offset)
78                 return false;
79
80         if (be1->be_state != PNFS_BLOCK_NONE_DATA &&
81             (be1->be_v_offset + be1->be_length != be2->be_v_offset))
82                 return false;
83
84         if (be1->be_state == PNFS_BLOCK_INVALID_DATA &&
85             be1->be_tag != be2->be_tag)
86                 return false;
87
88         return true;
89 }
90
91 static struct pnfs_block_extent *
92 ext_try_to_merge_left(struct rb_root *root, struct pnfs_block_extent *be)
93 {
94         struct pnfs_block_extent *left = ext_tree_prev(be);
95
96         if (left && ext_can_merge(left, be)) {
97                 left->be_length += be->be_length;
98                 rb_erase(&be->be_node, root);
99                 nfs4_put_deviceid_node(be->be_device);
100                 kfree(be);
101                 return left;
102         }
103
104         return be;
105 }
106
107 static struct pnfs_block_extent *
108 ext_try_to_merge_right(struct rb_root *root, struct pnfs_block_extent *be)
109 {
110         struct pnfs_block_extent *right = ext_tree_next(be);
111
112         if (right && ext_can_merge(be, right)) {
113                 be->be_length += right->be_length;
114                 rb_erase(&right->be_node, root);
115                 nfs4_put_deviceid_node(right->be_device);
116                 kfree(right);
117         }
118
119         return be;
120 }
121
122 static void
123 __ext_tree_insert(struct rb_root *root,
124                 struct pnfs_block_extent *new, bool merge_ok)
125 {
126         struct rb_node **p = &root->rb_node, *parent = NULL;
127         struct pnfs_block_extent *be;
128
129         while (*p) {
130                 parent = *p;
131                 be = ext_node(parent);
132
133                 if (new->be_f_offset < be->be_f_offset) {
134                         if (merge_ok && ext_can_merge(new, be)) {
135                                 be->be_f_offset = new->be_f_offset;
136                                 if (be->be_state != PNFS_BLOCK_NONE_DATA)
137                                         be->be_v_offset = new->be_v_offset;
138                                 be->be_length += new->be_length;
139                                 be = ext_try_to_merge_left(root, be);
140                                 goto free_new;
141                         }
142                         p = &(*p)->rb_left;
143                 } else if (new->be_f_offset >= ext_f_end(be)) {
144                         if (merge_ok && ext_can_merge(be, new)) {
145                                 be->be_length += new->be_length;
146                                 be = ext_try_to_merge_right(root, be);
147                                 goto free_new;
148                         }
149                         p = &(*p)->rb_right;
150                 } else {
151                         BUG();
152                 }
153         }
154
155         rb_link_node(&new->be_node, parent, p);
156         rb_insert_color(&new->be_node, root);
157         return;
158 free_new:
159         nfs4_put_deviceid_node(new->be_device);
160         kfree(new);
161 }
162
163 static int
164 __ext_tree_remove(struct rb_root *root, sector_t start, sector_t end)
165 {
166         struct pnfs_block_extent *be;
167         sector_t len1 = 0, len2 = 0;
168         sector_t orig_f_offset;
169         sector_t orig_v_offset;
170         sector_t orig_len;
171
172         be = __ext_tree_search(root, start);
173         if (!be)
174                 return 0;
175         if (be->be_f_offset >= end)
176                 return 0;
177
178         orig_f_offset = be->be_f_offset;
179         orig_v_offset = be->be_v_offset;
180         orig_len = be->be_length;
181
182         if (start > be->be_f_offset)
183                 len1 = start - be->be_f_offset;
184         if (ext_f_end(be) > end)
185                 len2 = ext_f_end(be) - end;
186
187         if (len2 > 0) {
188                 if (len1 > 0) {
189                         struct pnfs_block_extent *new;
190
191                         new = kzalloc(sizeof(*new), GFP_ATOMIC);
192                         if (!new)
193                                 return -ENOMEM;
194
195                         be->be_length = len1;
196
197                         new->be_f_offset = end;
198                         if (be->be_state != PNFS_BLOCK_NONE_DATA) {
199                                 new->be_v_offset =
200                                         orig_v_offset + orig_len - len2;
201                         }
202                         new->be_length = len2;
203                         new->be_state = be->be_state;
204                         new->be_tag = be->be_tag;
205                         new->be_device = nfs4_get_deviceid(be->be_device);
206
207                         __ext_tree_insert(root, new, true);
208                 } else {
209                         be->be_f_offset = end;
210                         if (be->be_state != PNFS_BLOCK_NONE_DATA) {
211                                 be->be_v_offset =
212                                         orig_v_offset + orig_len - len2;
213                         }
214                         be->be_length = len2;
215                 }
216         } else {
217                 if (len1 > 0) {
218                         be->be_length = len1;
219                         be = ext_tree_next(be);
220                 }
221
222                 while (be && ext_f_end(be) <= end) {
223                         struct pnfs_block_extent *next = ext_tree_next(be);
224
225                         rb_erase(&be->be_node, root);
226                         nfs4_put_deviceid_node(be->be_device);
227                         kfree(be);
228                         be = next;
229                 }
230
231                 if (be && be->be_f_offset < end) {
232                         len1 = ext_f_end(be) - end;
233                         be->be_f_offset = end;
234                         if (be->be_state != PNFS_BLOCK_NONE_DATA)
235                                 be->be_v_offset += be->be_length - len1;
236                         be->be_length = len1;
237                 }
238         }
239
240         return 0;
241 }
242
243 int
244 ext_tree_insert(struct pnfs_block_layout *bl, struct pnfs_block_extent *new)
245 {
246         struct pnfs_block_extent *be;
247         struct rb_root *root;
248         int err = 0;
249
250         switch (new->be_state) {
251         case PNFS_BLOCK_READWRITE_DATA:
252         case PNFS_BLOCK_INVALID_DATA:
253                 root = &bl->bl_ext_rw;
254                 break;
255         case PNFS_BLOCK_READ_DATA:
256         case PNFS_BLOCK_NONE_DATA:
257                 root = &bl->bl_ext_ro;
258                 break;
259         default:
260                 dprintk("invalid extent type\n");
261                 return -EINVAL;
262         }
263
264         spin_lock(&bl->bl_ext_lock);
265 retry:
266         be = __ext_tree_search(root, new->be_f_offset);
267         if (!be || be->be_f_offset >= ext_f_end(new)) {
268                 __ext_tree_insert(root, new, true);
269         } else if (new->be_f_offset >= be->be_f_offset) {
270                 if (ext_f_end(new) <= ext_f_end(be)) {
271                         nfs4_put_deviceid_node(new->be_device);
272                         kfree(new);
273                 } else {
274                         sector_t new_len = ext_f_end(new) - ext_f_end(be);
275                         sector_t diff = new->be_length - new_len;
276
277                         new->be_f_offset += diff;
278                         new->be_v_offset += diff;
279                         new->be_length = new_len;
280                         goto retry;
281                 }
282         } else if (ext_f_end(new) <= ext_f_end(be)) {
283                 new->be_length = be->be_f_offset - new->be_f_offset;
284                 __ext_tree_insert(root, new, true);
285         } else {
286                 struct pnfs_block_extent *split;
287                 sector_t new_len = ext_f_end(new) - ext_f_end(be);
288                 sector_t diff = new->be_length - new_len;
289
290                 split = kmemdup(new, sizeof(*new), GFP_ATOMIC);
291                 if (!split) {
292                         err = -EINVAL;
293                         goto out;
294                 }
295
296                 split->be_length = be->be_f_offset - split->be_f_offset;
297                 split->be_device = nfs4_get_deviceid(new->be_device);
298                 __ext_tree_insert(root, split, true);
299
300                 new->be_f_offset += diff;
301                 new->be_v_offset += diff;
302                 new->be_length = new_len;
303                 goto retry;
304         }
305 out:
306         spin_unlock(&bl->bl_ext_lock);
307         return err;
308 }
309
310 static bool
311 __ext_tree_lookup(struct rb_root *root, sector_t isect,
312                 struct pnfs_block_extent *ret)
313 {
314         struct rb_node *node;
315         struct pnfs_block_extent *be;
316
317         node = root->rb_node;
318         while (node) {
319                 be = ext_node(node);
320                 if (isect < be->be_f_offset)
321                         node = node->rb_left;
322                 else if (isect >= ext_f_end(be))
323                         node = node->rb_right;
324                 else {
325                         *ret = *be;
326                         return true;
327                 }
328         }
329
330         return false;
331 }
332
333 bool
334 ext_tree_lookup(struct pnfs_block_layout *bl, sector_t isect,
335             struct pnfs_block_extent *ret, bool rw)
336 {
337         bool found = false;
338
339         spin_lock(&bl->bl_ext_lock);
340         if (!rw)
341                 found = __ext_tree_lookup(&bl->bl_ext_ro, isect, ret);
342         if (!found)
343                 found = __ext_tree_lookup(&bl->bl_ext_rw, isect, ret);
344         spin_unlock(&bl->bl_ext_lock);
345
346         return found;
347 }
348
349 int ext_tree_remove(struct pnfs_block_layout *bl, bool rw,
350                 sector_t start, sector_t end)
351 {
352         int err, err2;
353
354         spin_lock(&bl->bl_ext_lock);
355         err = __ext_tree_remove(&bl->bl_ext_ro, start, end);
356         if (rw) {
357                 err2 = __ext_tree_remove(&bl->bl_ext_rw, start, end);
358                 if (!err)
359                         err = err2;
360         }
361         spin_unlock(&bl->bl_ext_lock);
362
363         return err;
364 }
365
366 static int
367 ext_tree_split(struct rb_root *root, struct pnfs_block_extent *be,
368                 sector_t split)
369 {
370         struct pnfs_block_extent *new;
371         sector_t orig_len = be->be_length;
372
373         dprintk("%s: need split for 0x%lx:0x%lx at 0x%lx\n",
374                 __func__, be->be_f_offset, ext_f_end(be), split);
375
376         new = kzalloc(sizeof(*new), GFP_ATOMIC);
377         if (!new)
378                 return -ENOMEM;
379
380         be->be_length = split - be->be_f_offset;
381
382         new->be_f_offset = split;
383         if (be->be_state != PNFS_BLOCK_NONE_DATA)
384                 new->be_v_offset = be->be_v_offset + be->be_length;
385         new->be_length = orig_len - be->be_length;
386         new->be_state = be->be_state;
387         new->be_tag = be->be_tag;
388         new->be_device = nfs4_get_deviceid(be->be_device);
389
390         dprintk("%s: got 0x%lx:0x%lx!\n",
391                 __func__, be->be_f_offset, ext_f_end(be));
392         dprintk("%s: got 0x%lx:0x%lx!\n",
393                 __func__, new->be_f_offset, ext_f_end(new));
394
395         __ext_tree_insert(root, new, false);
396         return 0;
397 }
398
399 int
400 ext_tree_mark_written(struct pnfs_block_layout *bl, sector_t start,
401                 sector_t len)
402 {
403         struct rb_root *root = &bl->bl_ext_rw;
404         sector_t end = start + len;
405         struct pnfs_block_extent *be;
406         int err = 0;
407
408         spin_lock(&bl->bl_ext_lock);
409         /*
410          * First remove all COW extents or holes from written to range.
411          */
412         err = __ext_tree_remove(&bl->bl_ext_ro, start, end);
413         if (err)
414                 goto out;
415
416         /*
417          * Then mark all invalid extents in the range as written to.
418          */
419         for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) {
420                 if (be->be_f_offset >= end)
421                         break;
422
423                 if (be->be_state != PNFS_BLOCK_INVALID_DATA || be->be_tag)
424                         continue;
425
426                 if (be->be_f_offset < start) {
427                         struct pnfs_block_extent *left = ext_tree_prev(be);
428
429                         if (left && ext_can_merge(left, be)) {
430                                 sector_t diff = start - be->be_f_offset;
431
432                                 left->be_length += diff;
433
434                                 be->be_f_offset += diff;
435                                 be->be_v_offset += diff;
436                                 be->be_length -= diff;
437                         } else {
438                                 err = ext_tree_split(root, be, start);
439                                 if (err)
440                                         goto out;
441                         }
442                 }
443
444                 if (ext_f_end(be) > end) {
445                         struct pnfs_block_extent *right = ext_tree_next(be);
446
447                         if (right && ext_can_merge(be, right)) {
448                                 sector_t diff = end - be->be_f_offset;
449
450                                 be->be_length -= diff;
451
452                                 right->be_f_offset -= diff;
453                                 right->be_v_offset -= diff;
454                                 right->be_length += diff;
455                         } else {
456                                 err = ext_tree_split(root, be, end);
457                                 if (err)
458                                         goto out;
459                         }
460                 }
461
462                 if (be->be_f_offset >= start && ext_f_end(be) <= end) {
463                         be->be_tag = EXTENT_WRITTEN;
464                         be = ext_try_to_merge_left(root, be);
465                         be = ext_try_to_merge_right(root, be);
466                 }
467         }
468 out:
469         spin_unlock(&bl->bl_ext_lock);
470         return err;
471 }
472
473 int
474 ext_tree_encode_commit(struct pnfs_block_layout *bl, struct xdr_stream *xdr)
475 {
476         struct pnfs_block_extent *be;
477         unsigned int count = 0;
478         __be32 *p, *xdr_start;
479         int ret = 0;
480
481         dprintk("%s enter\n", __func__);
482
483         xdr_start = xdr_reserve_space(xdr, 8);
484         if (!xdr_start)
485                 return -ENOSPC;
486
487         spin_lock(&bl->bl_ext_lock);
488         for (be = ext_tree_first(&bl->bl_ext_rw); be; be = ext_tree_next(be)) {
489                 if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
490                     be->be_tag != EXTENT_WRITTEN)
491                         continue;
492
493                 p = xdr_reserve_space(xdr, 7 * sizeof(__be32) +
494                                         NFS4_DEVICEID4_SIZE);
495                 if (!p) {
496                         printk("%s: out of space for extent list\n", __func__);
497                         ret = -ENOSPC;
498                         break;
499                 }
500
501                 p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data,
502                                 NFS4_DEVICEID4_SIZE);
503                 p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
504                 p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
505                 p = xdr_encode_hyper(p, 0LL);
506                 *p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);
507
508                 be->be_tag = EXTENT_COMMITTING;
509                 count++;
510         }
511         spin_unlock(&bl->bl_ext_lock);
512
513         xdr_start[0] = cpu_to_be32((xdr->p - xdr_start - 1) * 4);
514         xdr_start[1] = cpu_to_be32(count);
515
516         dprintk("%s found %i ranges\n", __func__, count);
517         return ret;
518 }
519
520 void
521 ext_tree_mark_committed(struct pnfs_block_layout *bl, int status)
522 {
523         struct rb_root *root = &bl->bl_ext_rw;
524         struct pnfs_block_extent *be;
525
526         dprintk("%s status %d\n", __func__, status);
527
528         spin_lock(&bl->bl_ext_lock);
529         for (be = ext_tree_first(root); be; be = ext_tree_next(be)) {
530                 if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
531                     be->be_tag != EXTENT_COMMITTING)
532                         continue;
533
534                 if (status) {
535                         /*
536                          * Mark as written and try again.
537                          *
538                          * XXX: some real error handling here wouldn't hurt..
539                          */
540                         be->be_tag = EXTENT_WRITTEN;
541                 } else {
542                         be->be_state = PNFS_BLOCK_READWRITE_DATA;
543                         be->be_tag = 0;
544                 }
545
546                 be = ext_try_to_merge_left(root, be);
547                 be = ext_try_to_merge_right(root, be);
548         }
549         spin_unlock(&bl->bl_ext_lock);
550 }