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