93193616205a6bc39d88addf6a5b3ac1b6fda237
[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_v_offset;
169         sector_t orig_len;
170
171         be = __ext_tree_search(root, start);
172         if (!be)
173                 return 0;
174         if (be->be_f_offset >= end)
175                 return 0;
176
177         orig_v_offset = be->be_v_offset;
178         orig_len = be->be_length;
179
180         if (start > be->be_f_offset)
181                 len1 = start - be->be_f_offset;
182         if (ext_f_end(be) > end)
183                 len2 = ext_f_end(be) - end;
184
185         if (len2 > 0) {
186                 if (len1 > 0) {
187                         struct pnfs_block_extent *new;
188
189                         new = kzalloc(sizeof(*new), GFP_ATOMIC);
190                         if (!new)
191                                 return -ENOMEM;
192
193                         be->be_length = len1;
194
195                         new->be_f_offset = end;
196                         if (be->be_state != PNFS_BLOCK_NONE_DATA) {
197                                 new->be_v_offset =
198                                         orig_v_offset + orig_len - len2;
199                         }
200                         new->be_length = len2;
201                         new->be_state = be->be_state;
202                         new->be_tag = be->be_tag;
203                         new->be_device = nfs4_get_deviceid(be->be_device);
204
205                         __ext_tree_insert(root, new, true);
206                 } else {
207                         be->be_f_offset = end;
208                         if (be->be_state != PNFS_BLOCK_NONE_DATA) {
209                                 be->be_v_offset =
210                                         orig_v_offset + orig_len - len2;
211                         }
212                         be->be_length = len2;
213                 }
214         } else {
215                 if (len1 > 0) {
216                         be->be_length = len1;
217                         be = ext_tree_next(be);
218                 }
219
220                 while (be && ext_f_end(be) <= end) {
221                         struct pnfs_block_extent *next = ext_tree_next(be);
222
223                         rb_erase(&be->be_node, root);
224                         nfs4_put_deviceid_node(be->be_device);
225                         kfree(be);
226                         be = next;
227                 }
228
229                 if (be && be->be_f_offset < end) {
230                         len1 = ext_f_end(be) - end;
231                         be->be_f_offset = end;
232                         if (be->be_state != PNFS_BLOCK_NONE_DATA)
233                                 be->be_v_offset += be->be_length - len1;
234                         be->be_length = len1;
235                 }
236         }
237
238         return 0;
239 }
240
241 int
242 ext_tree_insert(struct pnfs_block_layout *bl, struct pnfs_block_extent *new)
243 {
244         struct pnfs_block_extent *be;
245         struct rb_root *root;
246         int err = 0;
247
248         switch (new->be_state) {
249         case PNFS_BLOCK_READWRITE_DATA:
250         case PNFS_BLOCK_INVALID_DATA:
251                 root = &bl->bl_ext_rw;
252                 break;
253         case PNFS_BLOCK_READ_DATA:
254         case PNFS_BLOCK_NONE_DATA:
255                 root = &bl->bl_ext_ro;
256                 break;
257         default:
258                 dprintk("invalid extent type\n");
259                 return -EINVAL;
260         }
261
262         spin_lock(&bl->bl_ext_lock);
263 retry:
264         be = __ext_tree_search(root, new->be_f_offset);
265         if (!be || be->be_f_offset >= ext_f_end(new)) {
266                 __ext_tree_insert(root, new, true);
267         } else if (new->be_f_offset >= be->be_f_offset) {
268                 if (ext_f_end(new) <= ext_f_end(be)) {
269                         nfs4_put_deviceid_node(new->be_device);
270                         kfree(new);
271                 } else {
272                         sector_t new_len = ext_f_end(new) - ext_f_end(be);
273                         sector_t diff = new->be_length - new_len;
274
275                         new->be_f_offset += diff;
276                         new->be_v_offset += diff;
277                         new->be_length = new_len;
278                         goto retry;
279                 }
280         } else if (ext_f_end(new) <= ext_f_end(be)) {
281                 new->be_length = be->be_f_offset - new->be_f_offset;
282                 __ext_tree_insert(root, new, true);
283         } else {
284                 struct pnfs_block_extent *split;
285                 sector_t new_len = ext_f_end(new) - ext_f_end(be);
286                 sector_t diff = new->be_length - new_len;
287
288                 split = kmemdup(new, sizeof(*new), GFP_ATOMIC);
289                 if (!split) {
290                         err = -EINVAL;
291                         goto out;
292                 }
293
294                 split->be_length = be->be_f_offset - split->be_f_offset;
295                 split->be_device = nfs4_get_deviceid(new->be_device);
296                 __ext_tree_insert(root, split, true);
297
298                 new->be_f_offset += diff;
299                 new->be_v_offset += diff;
300                 new->be_length = new_len;
301                 goto retry;
302         }
303 out:
304         spin_unlock(&bl->bl_ext_lock);
305         return err;
306 }
307
308 static bool
309 __ext_tree_lookup(struct rb_root *root, sector_t isect,
310                 struct pnfs_block_extent *ret)
311 {
312         struct rb_node *node;
313         struct pnfs_block_extent *be;
314
315         node = root->rb_node;
316         while (node) {
317                 be = ext_node(node);
318                 if (isect < be->be_f_offset)
319                         node = node->rb_left;
320                 else if (isect >= ext_f_end(be))
321                         node = node->rb_right;
322                 else {
323                         *ret = *be;
324                         return true;
325                 }
326         }
327
328         return false;
329 }
330
331 bool
332 ext_tree_lookup(struct pnfs_block_layout *bl, sector_t isect,
333             struct pnfs_block_extent *ret, bool rw)
334 {
335         bool found = false;
336
337         spin_lock(&bl->bl_ext_lock);
338         if (!rw)
339                 found = __ext_tree_lookup(&bl->bl_ext_ro, isect, ret);
340         if (!found)
341                 found = __ext_tree_lookup(&bl->bl_ext_rw, isect, ret);
342         spin_unlock(&bl->bl_ext_lock);
343
344         return found;
345 }
346
347 int ext_tree_remove(struct pnfs_block_layout *bl, bool rw,
348                 sector_t start, sector_t end)
349 {
350         int err, err2;
351
352         spin_lock(&bl->bl_ext_lock);
353         err = __ext_tree_remove(&bl->bl_ext_ro, start, end);
354         if (rw) {
355                 err2 = __ext_tree_remove(&bl->bl_ext_rw, start, end);
356                 if (!err)
357                         err = err2;
358         }
359         spin_unlock(&bl->bl_ext_lock);
360
361         return err;
362 }
363
364 static int
365 ext_tree_split(struct rb_root *root, struct pnfs_block_extent *be,
366                 sector_t split)
367 {
368         struct pnfs_block_extent *new;
369         sector_t orig_len = be->be_length;
370
371         new = kzalloc(sizeof(*new), GFP_ATOMIC);
372         if (!new)
373                 return -ENOMEM;
374
375         be->be_length = split - be->be_f_offset;
376
377         new->be_f_offset = split;
378         if (be->be_state != PNFS_BLOCK_NONE_DATA)
379                 new->be_v_offset = be->be_v_offset + be->be_length;
380         new->be_length = orig_len - be->be_length;
381         new->be_state = be->be_state;
382         new->be_tag = be->be_tag;
383         new->be_device = nfs4_get_deviceid(be->be_device);
384
385         __ext_tree_insert(root, new, false);
386         return 0;
387 }
388
389 int
390 ext_tree_mark_written(struct pnfs_block_layout *bl, sector_t start,
391                 sector_t len)
392 {
393         struct rb_root *root = &bl->bl_ext_rw;
394         sector_t end = start + len;
395         struct pnfs_block_extent *be;
396         int err = 0;
397
398         spin_lock(&bl->bl_ext_lock);
399         /*
400          * First remove all COW extents or holes from written to range.
401          */
402         err = __ext_tree_remove(&bl->bl_ext_ro, start, end);
403         if (err)
404                 goto out;
405
406         /*
407          * Then mark all invalid extents in the range as written to.
408          */
409         for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) {
410                 if (be->be_f_offset >= end)
411                         break;
412
413                 if (be->be_state != PNFS_BLOCK_INVALID_DATA || be->be_tag)
414                         continue;
415
416                 if (be->be_f_offset < start) {
417                         struct pnfs_block_extent *left = ext_tree_prev(be);
418
419                         if (left && ext_can_merge(left, be)) {
420                                 sector_t diff = start - be->be_f_offset;
421
422                                 left->be_length += diff;
423
424                                 be->be_f_offset += diff;
425                                 be->be_v_offset += diff;
426                                 be->be_length -= diff;
427                         } else {
428                                 err = ext_tree_split(root, be, start);
429                                 if (err)
430                                         goto out;
431                         }
432                 }
433
434                 if (ext_f_end(be) > end) {
435                         struct pnfs_block_extent *right = ext_tree_next(be);
436
437                         if (right && ext_can_merge(be, right)) {
438                                 sector_t diff = end - be->be_f_offset;
439
440                                 be->be_length -= diff;
441
442                                 right->be_f_offset -= diff;
443                                 right->be_v_offset -= diff;
444                                 right->be_length += diff;
445                         } else {
446                                 err = ext_tree_split(root, be, end);
447                                 if (err)
448                                         goto out;
449                         }
450                 }
451
452                 if (be->be_f_offset >= start && ext_f_end(be) <= end) {
453                         be->be_tag = EXTENT_WRITTEN;
454                         be = ext_try_to_merge_left(root, be);
455                         be = ext_try_to_merge_right(root, be);
456                 }
457         }
458 out:
459         spin_unlock(&bl->bl_ext_lock);
460         return err;
461 }
462
463 static void ext_tree_free_commitdata(struct nfs4_layoutcommit_args *arg,
464                 size_t buffer_size)
465 {
466         if (arg->layoutupdate_pages != &arg->layoutupdate_page) {
467                 int nr_pages = DIV_ROUND_UP(buffer_size, PAGE_SIZE), i;
468
469                 for (i = 0; i < nr_pages; i++)
470                         put_page(arg->layoutupdate_pages[i]);
471                 kfree(arg->layoutupdate_pages);
472         } else {
473                 put_page(arg->layoutupdate_page);
474         }
475 }
476
477 static int ext_tree_encode_commit(struct pnfs_block_layout *bl, __be32 *p,
478                 size_t buffer_size, size_t *count)
479 {
480         struct pnfs_block_extent *be;
481         int ret = 0;
482
483         spin_lock(&bl->bl_ext_lock);
484         for (be = ext_tree_first(&bl->bl_ext_rw); be; be = ext_tree_next(be)) {
485                 if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
486                     be->be_tag != EXTENT_WRITTEN)
487                         continue;
488
489                 (*count)++;
490                 if (*count * BL_EXTENT_SIZE > buffer_size) {
491                         /* keep counting.. */
492                         ret = -ENOSPC;
493                         continue;
494                 }
495
496                 p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data,
497                                 NFS4_DEVICEID4_SIZE);
498                 p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
499                 p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
500                 p = xdr_encode_hyper(p, 0LL);
501                 *p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);
502
503                 be->be_tag = EXTENT_COMMITTING;
504         }
505         spin_unlock(&bl->bl_ext_lock);
506
507         return ret;
508 }
509
510 int
511 ext_tree_prepare_commit(struct nfs4_layoutcommit_args *arg)
512 {
513         struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
514         size_t count = 0, buffer_size = PAGE_SIZE;
515         __be32 *start_p;
516         int ret;
517
518         dprintk("%s enter\n", __func__);
519
520         arg->layoutupdate_page = alloc_page(GFP_NOFS);
521         if (!arg->layoutupdate_page)
522                 return -ENOMEM;
523         start_p = page_address(arg->layoutupdate_page);
524         arg->layoutupdate_pages = &arg->layoutupdate_page;
525
526 retry:
527         ret = ext_tree_encode_commit(bl, start_p + 1, buffer_size, &count);
528         if (unlikely(ret)) {
529                 ext_tree_free_commitdata(arg, buffer_size);
530
531                 buffer_size = sizeof(__be32) + BL_EXTENT_SIZE * count;
532                 count = 0;
533
534                 arg->layoutupdate_pages =
535                         kcalloc(DIV_ROUND_UP(buffer_size, PAGE_SIZE),
536                                 sizeof(struct page *), GFP_NOFS);
537                 if (!arg->layoutupdate_pages)
538                         return -ENOMEM;
539
540                 start_p = __vmalloc(buffer_size, GFP_NOFS, PAGE_KERNEL);
541                 if (!start_p) {
542                         kfree(arg->layoutupdate_pages);
543                         return -ENOMEM;
544                 }
545
546                 goto retry;
547         }
548
549         *start_p = cpu_to_be32(count);
550         arg->layoutupdate_len = sizeof(__be32) + BL_EXTENT_SIZE * count;
551
552         if (unlikely(arg->layoutupdate_pages != &arg->layoutupdate_page)) {
553                 __be32 *p = start_p;
554                 int i = 0;
555
556                 for (p = start_p;
557                      p < start_p + arg->layoutupdate_len;
558                      p += PAGE_SIZE) {
559                         arg->layoutupdate_pages[i++] = vmalloc_to_page(p);
560                 }
561         }
562
563         dprintk("%s found %zu ranges\n", __func__, count);
564         return 0;
565 }
566
567 void
568 ext_tree_mark_committed(struct nfs4_layoutcommit_args *arg, int status)
569 {
570         struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
571         struct rb_root *root = &bl->bl_ext_rw;
572         struct pnfs_block_extent *be;
573
574         dprintk("%s status %d\n", __func__, status);
575
576         ext_tree_free_commitdata(arg, arg->layoutupdate_len);
577
578         spin_lock(&bl->bl_ext_lock);
579         for (be = ext_tree_first(root); be; be = ext_tree_next(be)) {
580                 if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
581                     be->be_tag != EXTENT_COMMITTING)
582                         continue;
583
584                 if (status) {
585                         /*
586                          * Mark as written and try again.
587                          *
588                          * XXX: some real error handling here wouldn't hurt..
589                          */
590                         be->be_tag = EXTENT_WRITTEN;
591                 } else {
592                         be->be_state = PNFS_BLOCK_READWRITE_DATA;
593                         be->be_tag = 0;
594                 }
595
596                 be = ext_try_to_merge_left(root, be);
597                 be = ext_try_to_merge_right(root, be);
598         }
599         spin_unlock(&bl->bl_ext_lock);
600 }