Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (c) 2014-2016 Christoph Hellwig.
0004  */
0005 
0006 #include <linux/vmalloc.h>
0007 
0008 #include "blocklayout.h"
0009 
0010 #define NFSDBG_FACILITY     NFSDBG_PNFS_LD
0011 
0012 static inline struct pnfs_block_extent *
0013 ext_node(struct rb_node *node)
0014 {
0015     return rb_entry(node, struct pnfs_block_extent, be_node);
0016 }
0017 
0018 static struct pnfs_block_extent *
0019 ext_tree_first(struct rb_root *root)
0020 {
0021     struct rb_node *node = rb_first(root);
0022     return node ? ext_node(node) : NULL;
0023 }
0024 
0025 static struct pnfs_block_extent *
0026 ext_tree_prev(struct pnfs_block_extent *be)
0027 {
0028     struct rb_node *node = rb_prev(&be->be_node);
0029     return node ? ext_node(node) : NULL;
0030 }
0031 
0032 static struct pnfs_block_extent *
0033 ext_tree_next(struct pnfs_block_extent *be)
0034 {
0035     struct rb_node *node = rb_next(&be->be_node);
0036     return node ? ext_node(node) : NULL;
0037 }
0038 
0039 static inline sector_t
0040 ext_f_end(struct pnfs_block_extent *be)
0041 {
0042     return be->be_f_offset + be->be_length;
0043 }
0044 
0045 static struct pnfs_block_extent *
0046 __ext_tree_search(struct rb_root *root, sector_t start)
0047 {
0048     struct rb_node *node = root->rb_node;
0049     struct pnfs_block_extent *be = NULL;
0050 
0051     while (node) {
0052         be = ext_node(node);
0053         if (start < be->be_f_offset)
0054             node = node->rb_left;
0055         else if (start >= ext_f_end(be))
0056             node = node->rb_right;
0057         else
0058             return be;
0059     }
0060 
0061     if (be) {
0062         if (start < be->be_f_offset)
0063             return be;
0064 
0065         if (start >= ext_f_end(be))
0066             return ext_tree_next(be);
0067     }
0068 
0069     return NULL;
0070 }
0071 
0072 static bool
0073 ext_can_merge(struct pnfs_block_extent *be1, struct pnfs_block_extent *be2)
0074 {
0075     if (be1->be_state != be2->be_state)
0076         return false;
0077     if (be1->be_device != be2->be_device)
0078         return false;
0079 
0080     if (be1->be_f_offset + be1->be_length != be2->be_f_offset)
0081         return false;
0082 
0083     if (be1->be_state != PNFS_BLOCK_NONE_DATA &&
0084         (be1->be_v_offset + be1->be_length != be2->be_v_offset))
0085         return false;
0086 
0087     if (be1->be_state == PNFS_BLOCK_INVALID_DATA &&
0088         be1->be_tag != be2->be_tag)
0089         return false;
0090 
0091     return true;
0092 }
0093 
0094 static struct pnfs_block_extent *
0095 ext_try_to_merge_left(struct rb_root *root, struct pnfs_block_extent *be)
0096 {
0097     struct pnfs_block_extent *left = ext_tree_prev(be);
0098 
0099     if (left && ext_can_merge(left, be)) {
0100         left->be_length += be->be_length;
0101         rb_erase(&be->be_node, root);
0102         nfs4_put_deviceid_node(be->be_device);
0103         kfree(be);
0104         return left;
0105     }
0106 
0107     return be;
0108 }
0109 
0110 static struct pnfs_block_extent *
0111 ext_try_to_merge_right(struct rb_root *root, struct pnfs_block_extent *be)
0112 {
0113     struct pnfs_block_extent *right = ext_tree_next(be);
0114 
0115     if (right && ext_can_merge(be, right)) {
0116         be->be_length += right->be_length;
0117         rb_erase(&right->be_node, root);
0118         nfs4_put_deviceid_node(right->be_device);
0119         kfree(right);
0120     }
0121 
0122     return be;
0123 }
0124 
0125 static void __ext_put_deviceids(struct list_head *head)
0126 {
0127     struct pnfs_block_extent *be, *tmp;
0128 
0129     list_for_each_entry_safe(be, tmp, head, be_list) {
0130         nfs4_put_deviceid_node(be->be_device);
0131         kfree(be);
0132     }
0133 }
0134 
0135 static void
0136 __ext_tree_insert(struct rb_root *root,
0137         struct pnfs_block_extent *new, bool merge_ok)
0138 {
0139     struct rb_node **p = &root->rb_node, *parent = NULL;
0140     struct pnfs_block_extent *be;
0141 
0142     while (*p) {
0143         parent = *p;
0144         be = ext_node(parent);
0145 
0146         if (new->be_f_offset < be->be_f_offset) {
0147             if (merge_ok && ext_can_merge(new, be)) {
0148                 be->be_f_offset = new->be_f_offset;
0149                 if (be->be_state != PNFS_BLOCK_NONE_DATA)
0150                     be->be_v_offset = new->be_v_offset;
0151                 be->be_length += new->be_length;
0152                 be = ext_try_to_merge_left(root, be);
0153                 goto free_new;
0154             }
0155             p = &(*p)->rb_left;
0156         } else if (new->be_f_offset >= ext_f_end(be)) {
0157             if (merge_ok && ext_can_merge(be, new)) {
0158                 be->be_length += new->be_length;
0159                 be = ext_try_to_merge_right(root, be);
0160                 goto free_new;
0161             }
0162             p = &(*p)->rb_right;
0163         } else {
0164             BUG();
0165         }
0166     }
0167 
0168     rb_link_node(&new->be_node, parent, p);
0169     rb_insert_color(&new->be_node, root);
0170     return;
0171 free_new:
0172     nfs4_put_deviceid_node(new->be_device);
0173     kfree(new);
0174 }
0175 
0176 static int
0177 __ext_tree_remove(struct rb_root *root,
0178         sector_t start, sector_t end, struct list_head *tmp)
0179 {
0180     struct pnfs_block_extent *be;
0181     sector_t len1 = 0, len2 = 0;
0182     sector_t orig_v_offset;
0183     sector_t orig_len;
0184 
0185     be = __ext_tree_search(root, start);
0186     if (!be)
0187         return 0;
0188     if (be->be_f_offset >= end)
0189         return 0;
0190 
0191     orig_v_offset = be->be_v_offset;
0192     orig_len = be->be_length;
0193 
0194     if (start > be->be_f_offset)
0195         len1 = start - be->be_f_offset;
0196     if (ext_f_end(be) > end)
0197         len2 = ext_f_end(be) - end;
0198 
0199     if (len2 > 0) {
0200         if (len1 > 0) {
0201             struct pnfs_block_extent *new;
0202 
0203             new = kzalloc(sizeof(*new), GFP_ATOMIC);
0204             if (!new)
0205                 return -ENOMEM;
0206 
0207             be->be_length = len1;
0208 
0209             new->be_f_offset = end;
0210             if (be->be_state != PNFS_BLOCK_NONE_DATA) {
0211                 new->be_v_offset =
0212                     orig_v_offset + orig_len - len2;
0213             }
0214             new->be_length = len2;
0215             new->be_state = be->be_state;
0216             new->be_tag = be->be_tag;
0217             new->be_device = nfs4_get_deviceid(be->be_device);
0218 
0219             __ext_tree_insert(root, new, true);
0220         } else {
0221             be->be_f_offset = end;
0222             if (be->be_state != PNFS_BLOCK_NONE_DATA) {
0223                 be->be_v_offset =
0224                     orig_v_offset + orig_len - len2;
0225             }
0226             be->be_length = len2;
0227         }
0228     } else {
0229         if (len1 > 0) {
0230             be->be_length = len1;
0231             be = ext_tree_next(be);
0232         }
0233 
0234         while (be && ext_f_end(be) <= end) {
0235             struct pnfs_block_extent *next = ext_tree_next(be);
0236 
0237             rb_erase(&be->be_node, root);
0238             list_add_tail(&be->be_list, tmp);
0239             be = next;
0240         }
0241 
0242         if (be && be->be_f_offset < end) {
0243             len1 = ext_f_end(be) - end;
0244             be->be_f_offset = end;
0245             if (be->be_state != PNFS_BLOCK_NONE_DATA)
0246                 be->be_v_offset += be->be_length - len1;
0247             be->be_length = len1;
0248         }
0249     }
0250 
0251     return 0;
0252 }
0253 
0254 int
0255 ext_tree_insert(struct pnfs_block_layout *bl, struct pnfs_block_extent *new)
0256 {
0257     struct pnfs_block_extent *be;
0258     struct rb_root *root;
0259     int err = 0;
0260 
0261     switch (new->be_state) {
0262     case PNFS_BLOCK_READWRITE_DATA:
0263     case PNFS_BLOCK_INVALID_DATA:
0264         root = &bl->bl_ext_rw;
0265         break;
0266     case PNFS_BLOCK_READ_DATA:
0267     case PNFS_BLOCK_NONE_DATA:
0268         root = &bl->bl_ext_ro;
0269         break;
0270     default:
0271         dprintk("invalid extent type\n");
0272         return -EINVAL;
0273     }
0274 
0275     spin_lock(&bl->bl_ext_lock);
0276 retry:
0277     be = __ext_tree_search(root, new->be_f_offset);
0278     if (!be || be->be_f_offset >= ext_f_end(new)) {
0279         __ext_tree_insert(root, new, true);
0280     } else if (new->be_f_offset >= be->be_f_offset) {
0281         if (ext_f_end(new) <= ext_f_end(be)) {
0282             nfs4_put_deviceid_node(new->be_device);
0283             kfree(new);
0284         } else {
0285             sector_t new_len = ext_f_end(new) - ext_f_end(be);
0286             sector_t diff = new->be_length - new_len;
0287 
0288             new->be_f_offset += diff;
0289             new->be_v_offset += diff;
0290             new->be_length = new_len;
0291             goto retry;
0292         }
0293     } else if (ext_f_end(new) <= ext_f_end(be)) {
0294         new->be_length = be->be_f_offset - new->be_f_offset;
0295         __ext_tree_insert(root, new, true);
0296     } else {
0297         struct pnfs_block_extent *split;
0298         sector_t new_len = ext_f_end(new) - ext_f_end(be);
0299         sector_t diff = new->be_length - new_len;
0300 
0301         split = kmemdup(new, sizeof(*new), GFP_ATOMIC);
0302         if (!split) {
0303             err = -EINVAL;
0304             goto out;
0305         }
0306 
0307         split->be_length = be->be_f_offset - split->be_f_offset;
0308         split->be_device = nfs4_get_deviceid(new->be_device);
0309         __ext_tree_insert(root, split, true);
0310 
0311         new->be_f_offset += diff;
0312         new->be_v_offset += diff;
0313         new->be_length = new_len;
0314         goto retry;
0315     }
0316 out:
0317     spin_unlock(&bl->bl_ext_lock);
0318     return err;
0319 }
0320 
0321 static bool
0322 __ext_tree_lookup(struct rb_root *root, sector_t isect,
0323         struct pnfs_block_extent *ret)
0324 {
0325     struct rb_node *node;
0326     struct pnfs_block_extent *be;
0327 
0328     node = root->rb_node;
0329     while (node) {
0330         be = ext_node(node);
0331         if (isect < be->be_f_offset)
0332             node = node->rb_left;
0333         else if (isect >= ext_f_end(be))
0334             node = node->rb_right;
0335         else {
0336             *ret = *be;
0337             return true;
0338         }
0339     }
0340 
0341     return false;
0342 }
0343 
0344 bool
0345 ext_tree_lookup(struct pnfs_block_layout *bl, sector_t isect,
0346         struct pnfs_block_extent *ret, bool rw)
0347 {
0348     bool found = false;
0349 
0350     spin_lock(&bl->bl_ext_lock);
0351     if (!rw)
0352         found = __ext_tree_lookup(&bl->bl_ext_ro, isect, ret);
0353     if (!found)
0354         found = __ext_tree_lookup(&bl->bl_ext_rw, isect, ret);
0355     spin_unlock(&bl->bl_ext_lock);
0356 
0357     return found;
0358 }
0359 
0360 int ext_tree_remove(struct pnfs_block_layout *bl, bool rw,
0361         sector_t start, sector_t end)
0362 {
0363     int err, err2;
0364     LIST_HEAD(tmp);
0365 
0366     spin_lock(&bl->bl_ext_lock);
0367     err = __ext_tree_remove(&bl->bl_ext_ro, start, end, &tmp);
0368     if (rw) {
0369         err2 = __ext_tree_remove(&bl->bl_ext_rw, start, end, &tmp);
0370         if (!err)
0371             err = err2;
0372     }
0373     spin_unlock(&bl->bl_ext_lock);
0374 
0375     __ext_put_deviceids(&tmp);
0376     return err;
0377 }
0378 
0379 static int
0380 ext_tree_split(struct rb_root *root, struct pnfs_block_extent *be,
0381         sector_t split)
0382 {
0383     struct pnfs_block_extent *new;
0384     sector_t orig_len = be->be_length;
0385 
0386     new = kzalloc(sizeof(*new), GFP_ATOMIC);
0387     if (!new)
0388         return -ENOMEM;
0389 
0390     be->be_length = split - be->be_f_offset;
0391 
0392     new->be_f_offset = split;
0393     if (be->be_state != PNFS_BLOCK_NONE_DATA)
0394         new->be_v_offset = be->be_v_offset + be->be_length;
0395     new->be_length = orig_len - be->be_length;
0396     new->be_state = be->be_state;
0397     new->be_tag = be->be_tag;
0398     new->be_device = nfs4_get_deviceid(be->be_device);
0399 
0400     __ext_tree_insert(root, new, false);
0401     return 0;
0402 }
0403 
0404 int
0405 ext_tree_mark_written(struct pnfs_block_layout *bl, sector_t start,
0406         sector_t len, u64 lwb)
0407 {
0408     struct rb_root *root = &bl->bl_ext_rw;
0409     sector_t end = start + len;
0410     struct pnfs_block_extent *be;
0411     int err = 0;
0412     LIST_HEAD(tmp);
0413 
0414     spin_lock(&bl->bl_ext_lock);
0415     /*
0416      * First remove all COW extents or holes from written to range.
0417      */
0418     err = __ext_tree_remove(&bl->bl_ext_ro, start, end, &tmp);
0419     if (err)
0420         goto out;
0421 
0422     /*
0423      * Then mark all invalid extents in the range as written to.
0424      */
0425     for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) {
0426         if (be->be_f_offset >= end)
0427             break;
0428 
0429         if (be->be_state != PNFS_BLOCK_INVALID_DATA || be->be_tag)
0430             continue;
0431 
0432         if (be->be_f_offset < start) {
0433             struct pnfs_block_extent *left = ext_tree_prev(be);
0434 
0435             if (left && ext_can_merge(left, be)) {
0436                 sector_t diff = start - be->be_f_offset;
0437 
0438                 left->be_length += diff;
0439 
0440                 be->be_f_offset += diff;
0441                 be->be_v_offset += diff;
0442                 be->be_length -= diff;
0443             } else {
0444                 err = ext_tree_split(root, be, start);
0445                 if (err)
0446                     goto out;
0447             }
0448         }
0449 
0450         if (ext_f_end(be) > end) {
0451             struct pnfs_block_extent *right = ext_tree_next(be);
0452 
0453             if (right && ext_can_merge(be, right)) {
0454                 sector_t diff = end - be->be_f_offset;
0455 
0456                 be->be_length -= diff;
0457 
0458                 right->be_f_offset -= diff;
0459                 right->be_v_offset -= diff;
0460                 right->be_length += diff;
0461             } else {
0462                 err = ext_tree_split(root, be, end);
0463                 if (err)
0464                     goto out;
0465             }
0466         }
0467 
0468         if (be->be_f_offset >= start && ext_f_end(be) <= end) {
0469             be->be_tag = EXTENT_WRITTEN;
0470             be = ext_try_to_merge_left(root, be);
0471             be = ext_try_to_merge_right(root, be);
0472         }
0473     }
0474 out:
0475     if (bl->bl_lwb < lwb)
0476         bl->bl_lwb = lwb;
0477     spin_unlock(&bl->bl_ext_lock);
0478 
0479     __ext_put_deviceids(&tmp);
0480     return err;
0481 }
0482 
0483 static size_t ext_tree_layoutupdate_size(struct pnfs_block_layout *bl, size_t count)
0484 {
0485     if (bl->bl_scsi_layout)
0486         return sizeof(__be32) + PNFS_SCSI_RANGE_SIZE * count;
0487     else
0488         return sizeof(__be32) + PNFS_BLOCK_EXTENT_SIZE * count;
0489 }
0490 
0491 static void ext_tree_free_commitdata(struct nfs4_layoutcommit_args *arg,
0492         size_t buffer_size)
0493 {
0494     if (arg->layoutupdate_pages != &arg->layoutupdate_page) {
0495         int nr_pages = DIV_ROUND_UP(buffer_size, PAGE_SIZE), i;
0496 
0497         for (i = 0; i < nr_pages; i++)
0498             put_page(arg->layoutupdate_pages[i]);
0499         vfree(arg->start_p);
0500         kfree(arg->layoutupdate_pages);
0501     } else {
0502         put_page(arg->layoutupdate_page);
0503     }
0504 }
0505 
0506 static __be32 *encode_block_extent(struct pnfs_block_extent *be, __be32 *p)
0507 {
0508     p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data,
0509             NFS4_DEVICEID4_SIZE);
0510     p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
0511     p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
0512     p = xdr_encode_hyper(p, 0LL);
0513     *p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);
0514     return p;
0515 }
0516 
0517 static __be32 *encode_scsi_range(struct pnfs_block_extent *be, __be32 *p)
0518 {
0519     p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
0520     return xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
0521 }
0522 
0523 static int ext_tree_encode_commit(struct pnfs_block_layout *bl, __be32 *p,
0524         size_t buffer_size, size_t *count, __u64 *lastbyte)
0525 {
0526     struct pnfs_block_extent *be;
0527     int ret = 0;
0528 
0529     spin_lock(&bl->bl_ext_lock);
0530     for (be = ext_tree_first(&bl->bl_ext_rw); be; be = ext_tree_next(be)) {
0531         if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
0532             be->be_tag != EXTENT_WRITTEN)
0533             continue;
0534 
0535         (*count)++;
0536         if (ext_tree_layoutupdate_size(bl, *count) > buffer_size) {
0537             /* keep counting.. */
0538             ret = -ENOSPC;
0539             continue;
0540         }
0541 
0542         if (bl->bl_scsi_layout)
0543             p = encode_scsi_range(be, p);
0544         else
0545             p = encode_block_extent(be, p);
0546         be->be_tag = EXTENT_COMMITTING;
0547     }
0548     *lastbyte = bl->bl_lwb - 1;
0549     bl->bl_lwb = 0;
0550     spin_unlock(&bl->bl_ext_lock);
0551 
0552     return ret;
0553 }
0554 
0555 int
0556 ext_tree_prepare_commit(struct nfs4_layoutcommit_args *arg)
0557 {
0558     struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
0559     size_t count = 0, buffer_size = PAGE_SIZE;
0560     __be32 *start_p;
0561     int ret;
0562 
0563     dprintk("%s enter\n", __func__);
0564 
0565     arg->layoutupdate_page = alloc_page(GFP_NOFS);
0566     if (!arg->layoutupdate_page)
0567         return -ENOMEM;
0568     start_p = page_address(arg->layoutupdate_page);
0569     arg->layoutupdate_pages = &arg->layoutupdate_page;
0570 
0571 retry:
0572     ret = ext_tree_encode_commit(bl, start_p + 1, buffer_size, &count, &arg->lastbytewritten);
0573     if (unlikely(ret)) {
0574         ext_tree_free_commitdata(arg, buffer_size);
0575 
0576         buffer_size = ext_tree_layoutupdate_size(bl, count);
0577         count = 0;
0578 
0579         arg->layoutupdate_pages =
0580             kcalloc(DIV_ROUND_UP(buffer_size, PAGE_SIZE),
0581                 sizeof(struct page *), GFP_NOFS);
0582         if (!arg->layoutupdate_pages)
0583             return -ENOMEM;
0584 
0585         start_p = __vmalloc(buffer_size, GFP_NOFS);
0586         if (!start_p) {
0587             kfree(arg->layoutupdate_pages);
0588             return -ENOMEM;
0589         }
0590 
0591         goto retry;
0592     }
0593 
0594     *start_p = cpu_to_be32(count);
0595     arg->layoutupdate_len = ext_tree_layoutupdate_size(bl, count);
0596 
0597     if (unlikely(arg->layoutupdate_pages != &arg->layoutupdate_page)) {
0598         void *p = start_p, *end = p + arg->layoutupdate_len;
0599         struct page *page = NULL;
0600         int i = 0;
0601 
0602         arg->start_p = start_p;
0603         for ( ; p < end; p += PAGE_SIZE) {
0604             page = vmalloc_to_page(p);
0605             arg->layoutupdate_pages[i++] = page;
0606             get_page(page);
0607         }
0608     }
0609 
0610     dprintk("%s found %zu ranges\n", __func__, count);
0611     return 0;
0612 }
0613 
0614 void
0615 ext_tree_mark_committed(struct nfs4_layoutcommit_args *arg, int status)
0616 {
0617     struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
0618     struct rb_root *root = &bl->bl_ext_rw;
0619     struct pnfs_block_extent *be;
0620 
0621     dprintk("%s status %d\n", __func__, status);
0622 
0623     ext_tree_free_commitdata(arg, arg->layoutupdate_len);
0624 
0625     spin_lock(&bl->bl_ext_lock);
0626     for (be = ext_tree_first(root); be; be = ext_tree_next(be)) {
0627         if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
0628             be->be_tag != EXTENT_COMMITTING)
0629             continue;
0630 
0631         if (status) {
0632             /*
0633              * Mark as written and try again.
0634              *
0635              * XXX: some real error handling here wouldn't hurt..
0636              */
0637             be->be_tag = EXTENT_WRITTEN;
0638         } else {
0639             be->be_state = PNFS_BLOCK_READWRITE_DATA;
0640             be->be_tag = 0;
0641         }
0642 
0643         be = ext_try_to_merge_left(root, be);
0644         be = ext_try_to_merge_right(root, be);
0645     }
0646     spin_unlock(&bl->bl_ext_lock);
0647 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!