1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
28067253cSChristoph Hellwig /*
3d9186c03SChristoph Hellwig * Copyright (c) 2014-2016 Christoph Hellwig.
48067253cSChristoph Hellwig */
58067253cSChristoph Hellwig
6b262b35cSStephen Rothwell #include <linux/vmalloc.h>
7b262b35cSStephen Rothwell
88067253cSChristoph Hellwig #include "blocklayout.h"
98067253cSChristoph Hellwig
108067253cSChristoph Hellwig #define NFSDBG_FACILITY NFSDBG_PNFS_LD
118067253cSChristoph Hellwig
128067253cSChristoph Hellwig static inline struct pnfs_block_extent *
ext_node(struct rb_node * node)138067253cSChristoph Hellwig ext_node(struct rb_node *node)
148067253cSChristoph Hellwig {
158067253cSChristoph Hellwig return rb_entry(node, struct pnfs_block_extent, be_node);
168067253cSChristoph Hellwig }
178067253cSChristoph Hellwig
188067253cSChristoph Hellwig static struct pnfs_block_extent *
ext_tree_first(struct rb_root * root)198067253cSChristoph Hellwig ext_tree_first(struct rb_root *root)
208067253cSChristoph Hellwig {
218067253cSChristoph Hellwig struct rb_node *node = rb_first(root);
228067253cSChristoph Hellwig return node ? ext_node(node) : NULL;
238067253cSChristoph Hellwig }
248067253cSChristoph Hellwig
258067253cSChristoph Hellwig static struct pnfs_block_extent *
ext_tree_prev(struct pnfs_block_extent * be)268067253cSChristoph Hellwig ext_tree_prev(struct pnfs_block_extent *be)
278067253cSChristoph Hellwig {
288067253cSChristoph Hellwig struct rb_node *node = rb_prev(&be->be_node);
298067253cSChristoph Hellwig return node ? ext_node(node) : NULL;
308067253cSChristoph Hellwig }
318067253cSChristoph Hellwig
328067253cSChristoph Hellwig static struct pnfs_block_extent *
ext_tree_next(struct pnfs_block_extent * be)338067253cSChristoph Hellwig ext_tree_next(struct pnfs_block_extent *be)
348067253cSChristoph Hellwig {
358067253cSChristoph Hellwig struct rb_node *node = rb_next(&be->be_node);
368067253cSChristoph Hellwig return node ? ext_node(node) : NULL;
378067253cSChristoph Hellwig }
388067253cSChristoph Hellwig
398067253cSChristoph Hellwig static inline sector_t
ext_f_end(struct pnfs_block_extent * be)408067253cSChristoph Hellwig ext_f_end(struct pnfs_block_extent *be)
418067253cSChristoph Hellwig {
428067253cSChristoph Hellwig return be->be_f_offset + be->be_length;
438067253cSChristoph Hellwig }
448067253cSChristoph Hellwig
458067253cSChristoph Hellwig static struct pnfs_block_extent *
__ext_tree_search(struct rb_root * root,sector_t start)468067253cSChristoph Hellwig __ext_tree_search(struct rb_root *root, sector_t start)
478067253cSChristoph Hellwig {
488067253cSChristoph Hellwig struct rb_node *node = root->rb_node;
498067253cSChristoph Hellwig struct pnfs_block_extent *be = NULL;
508067253cSChristoph Hellwig
518067253cSChristoph Hellwig while (node) {
528067253cSChristoph Hellwig be = ext_node(node);
538067253cSChristoph Hellwig if (start < be->be_f_offset)
548067253cSChristoph Hellwig node = node->rb_left;
558067253cSChristoph Hellwig else if (start >= ext_f_end(be))
568067253cSChristoph Hellwig node = node->rb_right;
578067253cSChristoph Hellwig else
588067253cSChristoph Hellwig return be;
598067253cSChristoph Hellwig }
608067253cSChristoph Hellwig
618067253cSChristoph Hellwig if (be) {
628067253cSChristoph Hellwig if (start < be->be_f_offset)
638067253cSChristoph Hellwig return be;
648067253cSChristoph Hellwig
658067253cSChristoph Hellwig if (start >= ext_f_end(be))
668067253cSChristoph Hellwig return ext_tree_next(be);
678067253cSChristoph Hellwig }
688067253cSChristoph Hellwig
698067253cSChristoph Hellwig return NULL;
708067253cSChristoph Hellwig }
718067253cSChristoph Hellwig
728067253cSChristoph Hellwig static bool
ext_can_merge(struct pnfs_block_extent * be1,struct pnfs_block_extent * be2)738067253cSChristoph Hellwig ext_can_merge(struct pnfs_block_extent *be1, struct pnfs_block_extent *be2)
748067253cSChristoph Hellwig {
758067253cSChristoph Hellwig if (be1->be_state != be2->be_state)
768067253cSChristoph Hellwig return false;
7720d655d6SChristoph Hellwig if (be1->be_device != be2->be_device)
788067253cSChristoph Hellwig return false;
798067253cSChristoph Hellwig
808067253cSChristoph Hellwig if (be1->be_f_offset + be1->be_length != be2->be_f_offset)
818067253cSChristoph Hellwig return false;
828067253cSChristoph Hellwig
838067253cSChristoph Hellwig if (be1->be_state != PNFS_BLOCK_NONE_DATA &&
848067253cSChristoph Hellwig (be1->be_v_offset + be1->be_length != be2->be_v_offset))
858067253cSChristoph Hellwig return false;
868067253cSChristoph Hellwig
878067253cSChristoph Hellwig if (be1->be_state == PNFS_BLOCK_INVALID_DATA &&
888067253cSChristoph Hellwig be1->be_tag != be2->be_tag)
898067253cSChristoph Hellwig return false;
908067253cSChristoph Hellwig
918067253cSChristoph Hellwig return true;
928067253cSChristoph Hellwig }
938067253cSChristoph Hellwig
948067253cSChristoph Hellwig static struct pnfs_block_extent *
ext_try_to_merge_left(struct rb_root * root,struct pnfs_block_extent * be)958067253cSChristoph Hellwig ext_try_to_merge_left(struct rb_root *root, struct pnfs_block_extent *be)
968067253cSChristoph Hellwig {
978067253cSChristoph Hellwig struct pnfs_block_extent *left = ext_tree_prev(be);
988067253cSChristoph Hellwig
998067253cSChristoph Hellwig if (left && ext_can_merge(left, be)) {
1008067253cSChristoph Hellwig left->be_length += be->be_length;
1018067253cSChristoph Hellwig rb_erase(&be->be_node, root);
10220d655d6SChristoph Hellwig nfs4_put_deviceid_node(be->be_device);
1038067253cSChristoph Hellwig kfree(be);
1048067253cSChristoph Hellwig return left;
1058067253cSChristoph Hellwig }
1068067253cSChristoph Hellwig
1078067253cSChristoph Hellwig return be;
1088067253cSChristoph Hellwig }
1098067253cSChristoph Hellwig
1108067253cSChristoph Hellwig static struct pnfs_block_extent *
ext_try_to_merge_right(struct rb_root * root,struct pnfs_block_extent * be)1118067253cSChristoph Hellwig ext_try_to_merge_right(struct rb_root *root, struct pnfs_block_extent *be)
1128067253cSChristoph Hellwig {
1138067253cSChristoph Hellwig struct pnfs_block_extent *right = ext_tree_next(be);
1148067253cSChristoph Hellwig
1158067253cSChristoph Hellwig if (right && ext_can_merge(be, right)) {
1168067253cSChristoph Hellwig be->be_length += right->be_length;
1178067253cSChristoph Hellwig rb_erase(&right->be_node, root);
11820d655d6SChristoph Hellwig nfs4_put_deviceid_node(right->be_device);
1198067253cSChristoph Hellwig kfree(right);
1208067253cSChristoph Hellwig }
1218067253cSChristoph Hellwig
1228067253cSChristoph Hellwig return be;
1238067253cSChristoph Hellwig }
1248067253cSChristoph Hellwig
__ext_put_deviceids(struct list_head * head)125d9c0ce0eSBenjamin Coddington static void __ext_put_deviceids(struct list_head *head)
126d9c0ce0eSBenjamin Coddington {
127d9c0ce0eSBenjamin Coddington struct pnfs_block_extent *be, *tmp;
128d9c0ce0eSBenjamin Coddington
129d9c0ce0eSBenjamin Coddington list_for_each_entry_safe(be, tmp, head, be_list) {
130d9c0ce0eSBenjamin Coddington nfs4_put_deviceid_node(be->be_device);
131d9c0ce0eSBenjamin Coddington kfree(be);
132d9c0ce0eSBenjamin Coddington }
133d9c0ce0eSBenjamin Coddington }
134d9c0ce0eSBenjamin Coddington
1358067253cSChristoph Hellwig static void
__ext_tree_insert(struct rb_root * root,struct pnfs_block_extent * new,bool merge_ok)1368067253cSChristoph Hellwig __ext_tree_insert(struct rb_root *root,
1378067253cSChristoph Hellwig struct pnfs_block_extent *new, bool merge_ok)
1388067253cSChristoph Hellwig {
1398067253cSChristoph Hellwig struct rb_node **p = &root->rb_node, *parent = NULL;
1408067253cSChristoph Hellwig struct pnfs_block_extent *be;
1418067253cSChristoph Hellwig
1428067253cSChristoph Hellwig while (*p) {
1438067253cSChristoph Hellwig parent = *p;
1448067253cSChristoph Hellwig be = ext_node(parent);
1458067253cSChristoph Hellwig
1468067253cSChristoph Hellwig if (new->be_f_offset < be->be_f_offset) {
1478067253cSChristoph Hellwig if (merge_ok && ext_can_merge(new, be)) {
1488067253cSChristoph Hellwig be->be_f_offset = new->be_f_offset;
1498067253cSChristoph Hellwig if (be->be_state != PNFS_BLOCK_NONE_DATA)
1508067253cSChristoph Hellwig be->be_v_offset = new->be_v_offset;
1518067253cSChristoph Hellwig be->be_length += new->be_length;
1528067253cSChristoph Hellwig be = ext_try_to_merge_left(root, be);
15320d655d6SChristoph Hellwig goto free_new;
1548067253cSChristoph Hellwig }
1558067253cSChristoph Hellwig p = &(*p)->rb_left;
1568067253cSChristoph Hellwig } else if (new->be_f_offset >= ext_f_end(be)) {
1578067253cSChristoph Hellwig if (merge_ok && ext_can_merge(be, new)) {
1588067253cSChristoph Hellwig be->be_length += new->be_length;
1598067253cSChristoph Hellwig be = ext_try_to_merge_right(root, be);
16020d655d6SChristoph Hellwig goto free_new;
1618067253cSChristoph Hellwig }
1628067253cSChristoph Hellwig p = &(*p)->rb_right;
1638067253cSChristoph Hellwig } else {
1648067253cSChristoph Hellwig BUG();
1658067253cSChristoph Hellwig }
1668067253cSChristoph Hellwig }
1678067253cSChristoph Hellwig
1688067253cSChristoph Hellwig rb_link_node(&new->be_node, parent, p);
1698067253cSChristoph Hellwig rb_insert_color(&new->be_node, root);
17020d655d6SChristoph Hellwig return;
17120d655d6SChristoph Hellwig free_new:
17220d655d6SChristoph Hellwig nfs4_put_deviceid_node(new->be_device);
17320d655d6SChristoph Hellwig kfree(new);
1748067253cSChristoph Hellwig }
1758067253cSChristoph Hellwig
1768067253cSChristoph Hellwig static int
__ext_tree_remove(struct rb_root * root,sector_t start,sector_t end,struct list_head * tmp)177d9c0ce0eSBenjamin Coddington __ext_tree_remove(struct rb_root *root,
178d9c0ce0eSBenjamin Coddington sector_t start, sector_t end, struct list_head *tmp)
1798067253cSChristoph Hellwig {
1808067253cSChristoph Hellwig struct pnfs_block_extent *be;
1818067253cSChristoph Hellwig sector_t len1 = 0, len2 = 0;
1828067253cSChristoph Hellwig sector_t orig_v_offset;
1838067253cSChristoph Hellwig sector_t orig_len;
1848067253cSChristoph Hellwig
1858067253cSChristoph Hellwig be = __ext_tree_search(root, start);
1868067253cSChristoph Hellwig if (!be)
1878067253cSChristoph Hellwig return 0;
1888067253cSChristoph Hellwig if (be->be_f_offset >= end)
1898067253cSChristoph Hellwig return 0;
1908067253cSChristoph Hellwig
1918067253cSChristoph Hellwig orig_v_offset = be->be_v_offset;
1928067253cSChristoph Hellwig orig_len = be->be_length;
1938067253cSChristoph Hellwig
1948067253cSChristoph Hellwig if (start > be->be_f_offset)
1958067253cSChristoph Hellwig len1 = start - be->be_f_offset;
1968067253cSChristoph Hellwig if (ext_f_end(be) > end)
1978067253cSChristoph Hellwig len2 = ext_f_end(be) - end;
1988067253cSChristoph Hellwig
1998067253cSChristoph Hellwig if (len2 > 0) {
2008067253cSChristoph Hellwig if (len1 > 0) {
2018067253cSChristoph Hellwig struct pnfs_block_extent *new;
2028067253cSChristoph Hellwig
2038067253cSChristoph Hellwig new = kzalloc(sizeof(*new), GFP_ATOMIC);
2048067253cSChristoph Hellwig if (!new)
2058067253cSChristoph Hellwig return -ENOMEM;
2068067253cSChristoph Hellwig
2078067253cSChristoph Hellwig be->be_length = len1;
2088067253cSChristoph Hellwig
2098067253cSChristoph Hellwig new->be_f_offset = end;
2108067253cSChristoph Hellwig if (be->be_state != PNFS_BLOCK_NONE_DATA) {
2118067253cSChristoph Hellwig new->be_v_offset =
2128067253cSChristoph Hellwig orig_v_offset + orig_len - len2;
2138067253cSChristoph Hellwig }
2148067253cSChristoph Hellwig new->be_length = len2;
2158067253cSChristoph Hellwig new->be_state = be->be_state;
2168067253cSChristoph Hellwig new->be_tag = be->be_tag;
21720d655d6SChristoph Hellwig new->be_device = nfs4_get_deviceid(be->be_device);
2188067253cSChristoph Hellwig
2198067253cSChristoph Hellwig __ext_tree_insert(root, new, true);
2208067253cSChristoph Hellwig } else {
2218067253cSChristoph Hellwig be->be_f_offset = end;
2228067253cSChristoph Hellwig if (be->be_state != PNFS_BLOCK_NONE_DATA) {
2238067253cSChristoph Hellwig be->be_v_offset =
2248067253cSChristoph Hellwig orig_v_offset + orig_len - len2;
2258067253cSChristoph Hellwig }
2268067253cSChristoph Hellwig be->be_length = len2;
2278067253cSChristoph Hellwig }
2288067253cSChristoph Hellwig } else {
2298067253cSChristoph Hellwig if (len1 > 0) {
2308067253cSChristoph Hellwig be->be_length = len1;
2318067253cSChristoph Hellwig be = ext_tree_next(be);
2328067253cSChristoph Hellwig }
2338067253cSChristoph Hellwig
2348067253cSChristoph Hellwig while (be && ext_f_end(be) <= end) {
2358067253cSChristoph Hellwig struct pnfs_block_extent *next = ext_tree_next(be);
2368067253cSChristoph Hellwig
2378067253cSChristoph Hellwig rb_erase(&be->be_node, root);
238d9c0ce0eSBenjamin Coddington list_add_tail(&be->be_list, tmp);
2398067253cSChristoph Hellwig be = next;
2408067253cSChristoph Hellwig }
2418067253cSChristoph Hellwig
2428067253cSChristoph Hellwig if (be && be->be_f_offset < end) {
2438067253cSChristoph Hellwig len1 = ext_f_end(be) - end;
2448067253cSChristoph Hellwig be->be_f_offset = end;
2458067253cSChristoph Hellwig if (be->be_state != PNFS_BLOCK_NONE_DATA)
2468067253cSChristoph Hellwig be->be_v_offset += be->be_length - len1;
2478067253cSChristoph Hellwig be->be_length = len1;
2488067253cSChristoph Hellwig }
2498067253cSChristoph Hellwig }
2508067253cSChristoph Hellwig
2518067253cSChristoph Hellwig return 0;
2528067253cSChristoph Hellwig }
2538067253cSChristoph Hellwig
2548067253cSChristoph Hellwig int
ext_tree_insert(struct pnfs_block_layout * bl,struct pnfs_block_extent * new)2558067253cSChristoph Hellwig ext_tree_insert(struct pnfs_block_layout *bl, struct pnfs_block_extent *new)
2568067253cSChristoph Hellwig {
2578067253cSChristoph Hellwig struct pnfs_block_extent *be;
2588067253cSChristoph Hellwig struct rb_root *root;
2598067253cSChristoph Hellwig int err = 0;
2608067253cSChristoph Hellwig
2618067253cSChristoph Hellwig switch (new->be_state) {
2628067253cSChristoph Hellwig case PNFS_BLOCK_READWRITE_DATA:
2638067253cSChristoph Hellwig case PNFS_BLOCK_INVALID_DATA:
2648067253cSChristoph Hellwig root = &bl->bl_ext_rw;
2658067253cSChristoph Hellwig break;
2668067253cSChristoph Hellwig case PNFS_BLOCK_READ_DATA:
2678067253cSChristoph Hellwig case PNFS_BLOCK_NONE_DATA:
2688067253cSChristoph Hellwig root = &bl->bl_ext_ro;
2698067253cSChristoph Hellwig break;
2708067253cSChristoph Hellwig default:
2718067253cSChristoph Hellwig dprintk("invalid extent type\n");
2728067253cSChristoph Hellwig return -EINVAL;
2738067253cSChristoph Hellwig }
2748067253cSChristoph Hellwig
2758067253cSChristoph Hellwig spin_lock(&bl->bl_ext_lock);
2768067253cSChristoph Hellwig retry:
2778067253cSChristoph Hellwig be = __ext_tree_search(root, new->be_f_offset);
2788067253cSChristoph Hellwig if (!be || be->be_f_offset >= ext_f_end(new)) {
2798067253cSChristoph Hellwig __ext_tree_insert(root, new, true);
2808067253cSChristoph Hellwig } else if (new->be_f_offset >= be->be_f_offset) {
2818067253cSChristoph Hellwig if (ext_f_end(new) <= ext_f_end(be)) {
28220d655d6SChristoph Hellwig nfs4_put_deviceid_node(new->be_device);
2838067253cSChristoph Hellwig kfree(new);
2848067253cSChristoph Hellwig } else {
2858067253cSChristoph Hellwig sector_t new_len = ext_f_end(new) - ext_f_end(be);
2868067253cSChristoph Hellwig sector_t diff = new->be_length - new_len;
2878067253cSChristoph Hellwig
2888067253cSChristoph Hellwig new->be_f_offset += diff;
2898067253cSChristoph Hellwig new->be_v_offset += diff;
2908067253cSChristoph Hellwig new->be_length = new_len;
2918067253cSChristoph Hellwig goto retry;
2928067253cSChristoph Hellwig }
2938067253cSChristoph Hellwig } else if (ext_f_end(new) <= ext_f_end(be)) {
2948067253cSChristoph Hellwig new->be_length = be->be_f_offset - new->be_f_offset;
2958067253cSChristoph Hellwig __ext_tree_insert(root, new, true);
2968067253cSChristoph Hellwig } else {
2978067253cSChristoph Hellwig struct pnfs_block_extent *split;
2988067253cSChristoph Hellwig sector_t new_len = ext_f_end(new) - ext_f_end(be);
2998067253cSChristoph Hellwig sector_t diff = new->be_length - new_len;
3008067253cSChristoph Hellwig
3018067253cSChristoph Hellwig split = kmemdup(new, sizeof(*new), GFP_ATOMIC);
3028067253cSChristoph Hellwig if (!split) {
3038067253cSChristoph Hellwig err = -EINVAL;
3048067253cSChristoph Hellwig goto out;
3058067253cSChristoph Hellwig }
3068067253cSChristoph Hellwig
3078067253cSChristoph Hellwig split->be_length = be->be_f_offset - split->be_f_offset;
30820d655d6SChristoph Hellwig split->be_device = nfs4_get_deviceid(new->be_device);
3098067253cSChristoph Hellwig __ext_tree_insert(root, split, true);
3108067253cSChristoph Hellwig
3118067253cSChristoph Hellwig new->be_f_offset += diff;
3128067253cSChristoph Hellwig new->be_v_offset += diff;
3138067253cSChristoph Hellwig new->be_length = new_len;
3148067253cSChristoph Hellwig goto retry;
3158067253cSChristoph Hellwig }
3168067253cSChristoph Hellwig out:
3178067253cSChristoph Hellwig spin_unlock(&bl->bl_ext_lock);
3188067253cSChristoph Hellwig return err;
3198067253cSChristoph Hellwig }
3208067253cSChristoph Hellwig
3218067253cSChristoph Hellwig static bool
__ext_tree_lookup(struct rb_root * root,sector_t isect,struct pnfs_block_extent * ret)3228067253cSChristoph Hellwig __ext_tree_lookup(struct rb_root *root, sector_t isect,
3238067253cSChristoph Hellwig struct pnfs_block_extent *ret)
3248067253cSChristoph Hellwig {
3258067253cSChristoph Hellwig struct rb_node *node;
3268067253cSChristoph Hellwig struct pnfs_block_extent *be;
3278067253cSChristoph Hellwig
3288067253cSChristoph Hellwig node = root->rb_node;
3298067253cSChristoph Hellwig while (node) {
3308067253cSChristoph Hellwig be = ext_node(node);
3318067253cSChristoph Hellwig if (isect < be->be_f_offset)
3328067253cSChristoph Hellwig node = node->rb_left;
3338067253cSChristoph Hellwig else if (isect >= ext_f_end(be))
3348067253cSChristoph Hellwig node = node->rb_right;
3358067253cSChristoph Hellwig else {
3368067253cSChristoph Hellwig *ret = *be;
3378067253cSChristoph Hellwig return true;
3388067253cSChristoph Hellwig }
3398067253cSChristoph Hellwig }
3408067253cSChristoph Hellwig
3418067253cSChristoph Hellwig return false;
3428067253cSChristoph Hellwig }
3438067253cSChristoph Hellwig
3448067253cSChristoph Hellwig bool
ext_tree_lookup(struct pnfs_block_layout * bl,sector_t isect,struct pnfs_block_extent * ret,bool rw)3458067253cSChristoph Hellwig ext_tree_lookup(struct pnfs_block_layout *bl, sector_t isect,
3468067253cSChristoph Hellwig struct pnfs_block_extent *ret, bool rw)
3478067253cSChristoph Hellwig {
3488067253cSChristoph Hellwig bool found = false;
3498067253cSChristoph Hellwig
3508067253cSChristoph Hellwig spin_lock(&bl->bl_ext_lock);
3518067253cSChristoph Hellwig if (!rw)
3528067253cSChristoph Hellwig found = __ext_tree_lookup(&bl->bl_ext_ro, isect, ret);
3538067253cSChristoph Hellwig if (!found)
3548067253cSChristoph Hellwig found = __ext_tree_lookup(&bl->bl_ext_rw, isect, ret);
3558067253cSChristoph Hellwig spin_unlock(&bl->bl_ext_lock);
3568067253cSChristoph Hellwig
3578067253cSChristoph Hellwig return found;
3588067253cSChristoph Hellwig }
3598067253cSChristoph Hellwig
ext_tree_remove(struct pnfs_block_layout * bl,bool rw,sector_t start,sector_t end)3608067253cSChristoph Hellwig int ext_tree_remove(struct pnfs_block_layout *bl, bool rw,
3618067253cSChristoph Hellwig sector_t start, sector_t end)
3628067253cSChristoph Hellwig {
3638067253cSChristoph Hellwig int err, err2;
364d9c0ce0eSBenjamin Coddington LIST_HEAD(tmp);
3658067253cSChristoph Hellwig
3668067253cSChristoph Hellwig spin_lock(&bl->bl_ext_lock);
367d9c0ce0eSBenjamin Coddington err = __ext_tree_remove(&bl->bl_ext_ro, start, end, &tmp);
3688067253cSChristoph Hellwig if (rw) {
369d9c0ce0eSBenjamin Coddington err2 = __ext_tree_remove(&bl->bl_ext_rw, start, end, &tmp);
3708067253cSChristoph Hellwig if (!err)
3718067253cSChristoph Hellwig err = err2;
3728067253cSChristoph Hellwig }
3738067253cSChristoph Hellwig spin_unlock(&bl->bl_ext_lock);
3748067253cSChristoph Hellwig
375d9c0ce0eSBenjamin Coddington __ext_put_deviceids(&tmp);
3768067253cSChristoph Hellwig return err;
3778067253cSChristoph Hellwig }
3788067253cSChristoph Hellwig
3798067253cSChristoph Hellwig static int
ext_tree_split(struct rb_root * root,struct pnfs_block_extent * be,sector_t split)3808067253cSChristoph Hellwig ext_tree_split(struct rb_root *root, struct pnfs_block_extent *be,
3818067253cSChristoph Hellwig sector_t split)
3828067253cSChristoph Hellwig {
3838067253cSChristoph Hellwig struct pnfs_block_extent *new;
3848067253cSChristoph Hellwig sector_t orig_len = be->be_length;
3858067253cSChristoph Hellwig
3868067253cSChristoph Hellwig new = kzalloc(sizeof(*new), GFP_ATOMIC);
3878067253cSChristoph Hellwig if (!new)
3888067253cSChristoph Hellwig return -ENOMEM;
3898067253cSChristoph Hellwig
3908067253cSChristoph Hellwig be->be_length = split - be->be_f_offset;
3918067253cSChristoph Hellwig
3928067253cSChristoph Hellwig new->be_f_offset = split;
3938067253cSChristoph Hellwig if (be->be_state != PNFS_BLOCK_NONE_DATA)
3948067253cSChristoph Hellwig new->be_v_offset = be->be_v_offset + be->be_length;
3958067253cSChristoph Hellwig new->be_length = orig_len - be->be_length;
3968067253cSChristoph Hellwig new->be_state = be->be_state;
3978067253cSChristoph Hellwig new->be_tag = be->be_tag;
39820d655d6SChristoph Hellwig new->be_device = nfs4_get_deviceid(be->be_device);
3998067253cSChristoph Hellwig
4008067253cSChristoph Hellwig __ext_tree_insert(root, new, false);
4018067253cSChristoph Hellwig return 0;
4028067253cSChristoph Hellwig }
4038067253cSChristoph Hellwig
4048067253cSChristoph Hellwig int
ext_tree_mark_written(struct pnfs_block_layout * bl,sector_t start,sector_t len,u64 lwb)4058067253cSChristoph Hellwig ext_tree_mark_written(struct pnfs_block_layout *bl, sector_t start,
40641963c10SBenjamin Coddington sector_t len, u64 lwb)
4078067253cSChristoph Hellwig {
4088067253cSChristoph Hellwig struct rb_root *root = &bl->bl_ext_rw;
4098067253cSChristoph Hellwig sector_t end = start + len;
4108067253cSChristoph Hellwig struct pnfs_block_extent *be;
4118067253cSChristoph Hellwig int err = 0;
412d9c0ce0eSBenjamin Coddington LIST_HEAD(tmp);
4138067253cSChristoph Hellwig
4148067253cSChristoph Hellwig spin_lock(&bl->bl_ext_lock);
4158067253cSChristoph Hellwig /*
4168067253cSChristoph Hellwig * First remove all COW extents or holes from written to range.
4178067253cSChristoph Hellwig */
418d9c0ce0eSBenjamin Coddington err = __ext_tree_remove(&bl->bl_ext_ro, start, end, &tmp);
4198067253cSChristoph Hellwig if (err)
4208067253cSChristoph Hellwig goto out;
4218067253cSChristoph Hellwig
4228067253cSChristoph Hellwig /*
4238067253cSChristoph Hellwig * Then mark all invalid extents in the range as written to.
4248067253cSChristoph Hellwig */
4258067253cSChristoph Hellwig for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) {
4268067253cSChristoph Hellwig if (be->be_f_offset >= end)
4278067253cSChristoph Hellwig break;
4288067253cSChristoph Hellwig
4298067253cSChristoph Hellwig if (be->be_state != PNFS_BLOCK_INVALID_DATA || be->be_tag)
4308067253cSChristoph Hellwig continue;
4318067253cSChristoph Hellwig
4328067253cSChristoph Hellwig if (be->be_f_offset < start) {
4338067253cSChristoph Hellwig struct pnfs_block_extent *left = ext_tree_prev(be);
4348067253cSChristoph Hellwig
4358067253cSChristoph Hellwig if (left && ext_can_merge(left, be)) {
4368067253cSChristoph Hellwig sector_t diff = start - be->be_f_offset;
4378067253cSChristoph Hellwig
4388067253cSChristoph Hellwig left->be_length += diff;
4398067253cSChristoph Hellwig
4408067253cSChristoph Hellwig be->be_f_offset += diff;
4418067253cSChristoph Hellwig be->be_v_offset += diff;
4428067253cSChristoph Hellwig be->be_length -= diff;
4438067253cSChristoph Hellwig } else {
4448067253cSChristoph Hellwig err = ext_tree_split(root, be, start);
4458067253cSChristoph Hellwig if (err)
4468067253cSChristoph Hellwig goto out;
4478067253cSChristoph Hellwig }
4488067253cSChristoph Hellwig }
4498067253cSChristoph Hellwig
4508067253cSChristoph Hellwig if (ext_f_end(be) > end) {
4518067253cSChristoph Hellwig struct pnfs_block_extent *right = ext_tree_next(be);
4528067253cSChristoph Hellwig
4538067253cSChristoph Hellwig if (right && ext_can_merge(be, right)) {
4548067253cSChristoph Hellwig sector_t diff = end - be->be_f_offset;
4558067253cSChristoph Hellwig
4568067253cSChristoph Hellwig be->be_length -= diff;
4578067253cSChristoph Hellwig
4588067253cSChristoph Hellwig right->be_f_offset -= diff;
4598067253cSChristoph Hellwig right->be_v_offset -= diff;
4608067253cSChristoph Hellwig right->be_length += diff;
4618067253cSChristoph Hellwig } else {
4628067253cSChristoph Hellwig err = ext_tree_split(root, be, end);
4638067253cSChristoph Hellwig if (err)
4648067253cSChristoph Hellwig goto out;
4658067253cSChristoph Hellwig }
4668067253cSChristoph Hellwig }
4678067253cSChristoph Hellwig
4688067253cSChristoph Hellwig if (be->be_f_offset >= start && ext_f_end(be) <= end) {
4698067253cSChristoph Hellwig be->be_tag = EXTENT_WRITTEN;
4708067253cSChristoph Hellwig be = ext_try_to_merge_left(root, be);
4718067253cSChristoph Hellwig be = ext_try_to_merge_right(root, be);
4728067253cSChristoph Hellwig }
4738067253cSChristoph Hellwig }
4748067253cSChristoph Hellwig out:
47541963c10SBenjamin Coddington if (bl->bl_lwb < lwb)
47641963c10SBenjamin Coddington bl->bl_lwb = lwb;
4778067253cSChristoph Hellwig spin_unlock(&bl->bl_ext_lock);
478d9c0ce0eSBenjamin Coddington
479d9c0ce0eSBenjamin Coddington __ext_put_deviceids(&tmp);
4808067253cSChristoph Hellwig return err;
4818067253cSChristoph Hellwig }
4828067253cSChristoph Hellwig
ext_tree_layoutupdate_size(struct pnfs_block_layout * bl,size_t count)483d9186c03SChristoph Hellwig static size_t ext_tree_layoutupdate_size(struct pnfs_block_layout *bl, size_t count)
48429662fa6SChristoph Hellwig {
485d9186c03SChristoph Hellwig if (bl->bl_scsi_layout)
486d9186c03SChristoph Hellwig return sizeof(__be32) + PNFS_SCSI_RANGE_SIZE * count;
487d9186c03SChristoph Hellwig else
488d9186c03SChristoph Hellwig return sizeof(__be32) + PNFS_BLOCK_EXTENT_SIZE * count;
48929662fa6SChristoph Hellwig }
49029662fa6SChristoph Hellwig
ext_tree_free_commitdata(struct nfs4_layoutcommit_args * arg,size_t buffer_size)49134dc93c2SChristoph Hellwig static void ext_tree_free_commitdata(struct nfs4_layoutcommit_args *arg,
49234dc93c2SChristoph Hellwig size_t buffer_size)
49334dc93c2SChristoph Hellwig {
49434dc93c2SChristoph Hellwig if (arg->layoutupdate_pages != &arg->layoutupdate_page) {
49534dc93c2SChristoph Hellwig int nr_pages = DIV_ROUND_UP(buffer_size, PAGE_SIZE), i;
49634dc93c2SChristoph Hellwig
49734dc93c2SChristoph Hellwig for (i = 0; i < nr_pages; i++)
49834dc93c2SChristoph Hellwig put_page(arg->layoutupdate_pages[i]);
499c8975706SKinglong Mee vfree(arg->start_p);
50034dc93c2SChristoph Hellwig kfree(arg->layoutupdate_pages);
50134dc93c2SChristoph Hellwig } else {
50234dc93c2SChristoph Hellwig put_page(arg->layoutupdate_page);
50334dc93c2SChristoph Hellwig }
50434dc93c2SChristoph Hellwig }
50534dc93c2SChristoph Hellwig
encode_block_extent(struct pnfs_block_extent * be,__be32 * p)506d9186c03SChristoph Hellwig static __be32 *encode_block_extent(struct pnfs_block_extent *be, __be32 *p)
507d9186c03SChristoph Hellwig {
508d9186c03SChristoph Hellwig p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data,
509d9186c03SChristoph Hellwig NFS4_DEVICEID4_SIZE);
510d9186c03SChristoph Hellwig p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
511d9186c03SChristoph Hellwig p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
512d9186c03SChristoph Hellwig p = xdr_encode_hyper(p, 0LL);
513d9186c03SChristoph Hellwig *p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);
514d9186c03SChristoph Hellwig return p;
515d9186c03SChristoph Hellwig }
516d9186c03SChristoph Hellwig
encode_scsi_range(struct pnfs_block_extent * be,__be32 * p)517d9186c03SChristoph Hellwig static __be32 *encode_scsi_range(struct pnfs_block_extent *be, __be32 *p)
518d9186c03SChristoph Hellwig {
519d9186c03SChristoph Hellwig p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
520d9186c03SChristoph Hellwig return xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
521d9186c03SChristoph Hellwig }
522d9186c03SChristoph Hellwig
ext_tree_encode_commit(struct pnfs_block_layout * bl,__be32 * p,size_t buffer_size,size_t * count,__u64 * lastbyte)52334dc93c2SChristoph Hellwig static int ext_tree_encode_commit(struct pnfs_block_layout *bl, __be32 *p,
52441963c10SBenjamin Coddington size_t buffer_size, size_t *count, __u64 *lastbyte)
5258067253cSChristoph Hellwig {
5268067253cSChristoph Hellwig struct pnfs_block_extent *be;
5278067253cSChristoph Hellwig int ret = 0;
5288067253cSChristoph Hellwig
5298067253cSChristoph Hellwig spin_lock(&bl->bl_ext_lock);
5308067253cSChristoph Hellwig for (be = ext_tree_first(&bl->bl_ext_rw); be; be = ext_tree_next(be)) {
5318067253cSChristoph Hellwig if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
5328067253cSChristoph Hellwig be->be_tag != EXTENT_WRITTEN)
5338067253cSChristoph Hellwig continue;
5348067253cSChristoph Hellwig
53534dc93c2SChristoph Hellwig (*count)++;
536d9186c03SChristoph Hellwig if (ext_tree_layoutupdate_size(bl, *count) > buffer_size) {
53734dc93c2SChristoph Hellwig /* keep counting.. */
5388067253cSChristoph Hellwig ret = -ENOSPC;
53934dc93c2SChristoph Hellwig continue;
5408067253cSChristoph Hellwig }
5418067253cSChristoph Hellwig
542d9186c03SChristoph Hellwig if (bl->bl_scsi_layout)
543d9186c03SChristoph Hellwig p = encode_scsi_range(be, p);
544d9186c03SChristoph Hellwig else
545d9186c03SChristoph Hellwig p = encode_block_extent(be, p);
5468067253cSChristoph Hellwig be->be_tag = EXTENT_COMMITTING;
5478067253cSChristoph Hellwig }
54841963c10SBenjamin Coddington *lastbyte = bl->bl_lwb - 1;
54941963c10SBenjamin Coddington bl->bl_lwb = 0;
5508067253cSChristoph Hellwig spin_unlock(&bl->bl_ext_lock);
5518067253cSChristoph Hellwig
5528067253cSChristoph Hellwig return ret;
5538067253cSChristoph Hellwig }
5548067253cSChristoph Hellwig
55534dc93c2SChristoph Hellwig int
ext_tree_prepare_commit(struct nfs4_layoutcommit_args * arg)55634dc93c2SChristoph Hellwig ext_tree_prepare_commit(struct nfs4_layoutcommit_args *arg)
5578067253cSChristoph Hellwig {
55834dc93c2SChristoph Hellwig struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
55934dc93c2SChristoph Hellwig size_t count = 0, buffer_size = PAGE_SIZE;
56034dc93c2SChristoph Hellwig __be32 *start_p;
56134dc93c2SChristoph Hellwig int ret;
56234dc93c2SChristoph Hellwig
56334dc93c2SChristoph Hellwig dprintk("%s enter\n", __func__);
56434dc93c2SChristoph Hellwig
56534dc93c2SChristoph Hellwig arg->layoutupdate_page = alloc_page(GFP_NOFS);
56634dc93c2SChristoph Hellwig if (!arg->layoutupdate_page)
56734dc93c2SChristoph Hellwig return -ENOMEM;
56834dc93c2SChristoph Hellwig start_p = page_address(arg->layoutupdate_page);
56934dc93c2SChristoph Hellwig arg->layoutupdate_pages = &arg->layoutupdate_page;
57034dc93c2SChristoph Hellwig
57134dc93c2SChristoph Hellwig retry:
57241963c10SBenjamin Coddington ret = ext_tree_encode_commit(bl, start_p + 1, buffer_size, &count, &arg->lastbytewritten);
57334dc93c2SChristoph Hellwig if (unlikely(ret)) {
57434dc93c2SChristoph Hellwig ext_tree_free_commitdata(arg, buffer_size);
57534dc93c2SChristoph Hellwig
576d9186c03SChristoph Hellwig buffer_size = ext_tree_layoutupdate_size(bl, count);
57734dc93c2SChristoph Hellwig count = 0;
57834dc93c2SChristoph Hellwig
57934dc93c2SChristoph Hellwig arg->layoutupdate_pages =
58034dc93c2SChristoph Hellwig kcalloc(DIV_ROUND_UP(buffer_size, PAGE_SIZE),
58134dc93c2SChristoph Hellwig sizeof(struct page *), GFP_NOFS);
58234dc93c2SChristoph Hellwig if (!arg->layoutupdate_pages)
58334dc93c2SChristoph Hellwig return -ENOMEM;
58434dc93c2SChristoph Hellwig
58588dca4caSChristoph Hellwig start_p = __vmalloc(buffer_size, GFP_NOFS);
58634dc93c2SChristoph Hellwig if (!start_p) {
58734dc93c2SChristoph Hellwig kfree(arg->layoutupdate_pages);
58834dc93c2SChristoph Hellwig return -ENOMEM;
58934dc93c2SChristoph Hellwig }
59034dc93c2SChristoph Hellwig
59134dc93c2SChristoph Hellwig goto retry;
59234dc93c2SChristoph Hellwig }
59334dc93c2SChristoph Hellwig
59434dc93c2SChristoph Hellwig *start_p = cpu_to_be32(count);
595d9186c03SChristoph Hellwig arg->layoutupdate_len = ext_tree_layoutupdate_size(bl, count);
59634dc93c2SChristoph Hellwig
59734dc93c2SChristoph Hellwig if (unlikely(arg->layoutupdate_pages != &arg->layoutupdate_page)) {
59868596bd1SChristoph Hellwig void *p = start_p, *end = p + arg->layoutupdate_len;
599c8975706SKinglong Mee struct page *page = NULL;
60034dc93c2SChristoph Hellwig int i = 0;
60134dc93c2SChristoph Hellwig
602c8975706SKinglong Mee arg->start_p = start_p;
603c8975706SKinglong Mee for ( ; p < end; p += PAGE_SIZE) {
604c8975706SKinglong Mee page = vmalloc_to_page(p);
605c8975706SKinglong Mee arg->layoutupdate_pages[i++] = page;
606c8975706SKinglong Mee get_page(page);
607c8975706SKinglong Mee }
60834dc93c2SChristoph Hellwig }
60934dc93c2SChristoph Hellwig
61034dc93c2SChristoph Hellwig dprintk("%s found %zu ranges\n", __func__, count);
61134dc93c2SChristoph Hellwig return 0;
61234dc93c2SChristoph Hellwig }
61334dc93c2SChristoph Hellwig
61434dc93c2SChristoph Hellwig void
ext_tree_mark_committed(struct nfs4_layoutcommit_args * arg,int status)61534dc93c2SChristoph Hellwig ext_tree_mark_committed(struct nfs4_layoutcommit_args *arg, int status)
61634dc93c2SChristoph Hellwig {
61734dc93c2SChristoph Hellwig struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
6188067253cSChristoph Hellwig struct rb_root *root = &bl->bl_ext_rw;
6198067253cSChristoph Hellwig struct pnfs_block_extent *be;
6208067253cSChristoph Hellwig
6218067253cSChristoph Hellwig dprintk("%s status %d\n", __func__, status);
6228067253cSChristoph Hellwig
62334dc93c2SChristoph Hellwig ext_tree_free_commitdata(arg, arg->layoutupdate_len);
62434dc93c2SChristoph Hellwig
6258067253cSChristoph Hellwig spin_lock(&bl->bl_ext_lock);
6268067253cSChristoph Hellwig for (be = ext_tree_first(root); be; be = ext_tree_next(be)) {
6278067253cSChristoph Hellwig if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
6288067253cSChristoph Hellwig be->be_tag != EXTENT_COMMITTING)
6298067253cSChristoph Hellwig continue;
6308067253cSChristoph Hellwig
6318067253cSChristoph Hellwig if (status) {
6328067253cSChristoph Hellwig /*
6338067253cSChristoph Hellwig * Mark as written and try again.
6348067253cSChristoph Hellwig *
6358067253cSChristoph Hellwig * XXX: some real error handling here wouldn't hurt..
6368067253cSChristoph Hellwig */
6378067253cSChristoph Hellwig be->be_tag = EXTENT_WRITTEN;
6388067253cSChristoph Hellwig } else {
6398067253cSChristoph Hellwig be->be_state = PNFS_BLOCK_READWRITE_DATA;
6408067253cSChristoph Hellwig be->be_tag = 0;
6418067253cSChristoph Hellwig }
6428067253cSChristoph Hellwig
6438067253cSChristoph Hellwig be = ext_try_to_merge_left(root, be);
6448067253cSChristoph Hellwig be = ext_try_to_merge_right(root, be);
6458067253cSChristoph Hellwig }
6468067253cSChristoph Hellwig spin_unlock(&bl->bl_ext_lock);
6478067253cSChristoph Hellwig }
648