Lines Matching +full:root +full:- +full:node
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2014-2016 Christoph Hellwig.
13 ext_node(struct rb_node *node) in ext_node() argument
15 return rb_entry(node, struct pnfs_block_extent, be_node); in ext_node()
19 ext_tree_first(struct rb_root *root) in ext_tree_first() argument
21 struct rb_node *node = rb_first(root); in ext_tree_first() local
22 return node ? ext_node(node) : NULL; in ext_tree_first()
28 struct rb_node *node = rb_prev(&be->be_node); in ext_tree_prev() local
29 return node ? ext_node(node) : NULL; in ext_tree_prev()
35 struct rb_node *node = rb_next(&be->be_node); in ext_tree_next() local
36 return node ? ext_node(node) : NULL; in ext_tree_next()
42 return be->be_f_offset + be->be_length; in ext_f_end()
46 __ext_tree_search(struct rb_root *root, sector_t start) in __ext_tree_search() argument
48 struct rb_node *node = root->rb_node; in __ext_tree_search() local
51 while (node) { in __ext_tree_search()
52 be = ext_node(node); in __ext_tree_search()
53 if (start < be->be_f_offset) in __ext_tree_search()
54 node = node->rb_left; in __ext_tree_search()
56 node = node->rb_right; in __ext_tree_search()
62 if (start < be->be_f_offset) in __ext_tree_search()
75 if (be1->be_state != be2->be_state) in ext_can_merge()
77 if (be1->be_device != be2->be_device) in ext_can_merge()
80 if (be1->be_f_offset + be1->be_length != be2->be_f_offset) in ext_can_merge()
83 if (be1->be_state != PNFS_BLOCK_NONE_DATA && in ext_can_merge()
84 (be1->be_v_offset + be1->be_length != be2->be_v_offset)) in ext_can_merge()
87 if (be1->be_state == PNFS_BLOCK_INVALID_DATA && in ext_can_merge()
88 be1->be_tag != be2->be_tag) in ext_can_merge()
95 ext_try_to_merge_left(struct rb_root *root, struct pnfs_block_extent *be) in ext_try_to_merge_left() argument
100 left->be_length += be->be_length; in ext_try_to_merge_left()
101 rb_erase(&be->be_node, root); in ext_try_to_merge_left()
102 nfs4_put_deviceid_node(be->be_device); in ext_try_to_merge_left()
111 ext_try_to_merge_right(struct rb_root *root, struct pnfs_block_extent *be) in ext_try_to_merge_right() argument
116 be->be_length += right->be_length; in ext_try_to_merge_right()
117 rb_erase(&right->be_node, root); in ext_try_to_merge_right()
118 nfs4_put_deviceid_node(right->be_device); in ext_try_to_merge_right()
130 nfs4_put_deviceid_node(be->be_device); in __ext_put_deviceids()
136 __ext_tree_insert(struct rb_root *root, in __ext_tree_insert() argument
139 struct rb_node **p = &root->rb_node, *parent = NULL; in __ext_tree_insert()
146 if (new->be_f_offset < be->be_f_offset) { in __ext_tree_insert()
148 be->be_f_offset = new->be_f_offset; in __ext_tree_insert()
149 if (be->be_state != PNFS_BLOCK_NONE_DATA) in __ext_tree_insert()
150 be->be_v_offset = new->be_v_offset; in __ext_tree_insert()
151 be->be_length += new->be_length; in __ext_tree_insert()
152 be = ext_try_to_merge_left(root, be); in __ext_tree_insert()
155 p = &(*p)->rb_left; in __ext_tree_insert()
156 } else if (new->be_f_offset >= ext_f_end(be)) { in __ext_tree_insert()
158 be->be_length += new->be_length; in __ext_tree_insert()
159 be = ext_try_to_merge_right(root, be); in __ext_tree_insert()
162 p = &(*p)->rb_right; in __ext_tree_insert()
168 rb_link_node(&new->be_node, parent, p); in __ext_tree_insert()
169 rb_insert_color(&new->be_node, root); in __ext_tree_insert()
172 nfs4_put_deviceid_node(new->be_device); in __ext_tree_insert()
177 __ext_tree_remove(struct rb_root *root, in __ext_tree_remove() argument
185 be = __ext_tree_search(root, start); in __ext_tree_remove()
188 if (be->be_f_offset >= end) in __ext_tree_remove()
191 orig_v_offset = be->be_v_offset; in __ext_tree_remove()
192 orig_len = be->be_length; in __ext_tree_remove()
194 if (start > be->be_f_offset) in __ext_tree_remove()
195 len1 = start - be->be_f_offset; in __ext_tree_remove()
197 len2 = ext_f_end(be) - end; in __ext_tree_remove()
205 return -ENOMEM; in __ext_tree_remove()
207 be->be_length = len1; in __ext_tree_remove()
209 new->be_f_offset = end; in __ext_tree_remove()
210 if (be->be_state != PNFS_BLOCK_NONE_DATA) { in __ext_tree_remove()
211 new->be_v_offset = in __ext_tree_remove()
212 orig_v_offset + orig_len - len2; in __ext_tree_remove()
214 new->be_length = len2; in __ext_tree_remove()
215 new->be_state = be->be_state; in __ext_tree_remove()
216 new->be_tag = be->be_tag; in __ext_tree_remove()
217 new->be_device = nfs4_get_deviceid(be->be_device); in __ext_tree_remove()
219 __ext_tree_insert(root, new, true); in __ext_tree_remove()
221 be->be_f_offset = end; in __ext_tree_remove()
222 if (be->be_state != PNFS_BLOCK_NONE_DATA) { in __ext_tree_remove()
223 be->be_v_offset = in __ext_tree_remove()
224 orig_v_offset + orig_len - len2; in __ext_tree_remove()
226 be->be_length = len2; in __ext_tree_remove()
230 be->be_length = len1; in __ext_tree_remove()
237 rb_erase(&be->be_node, root); in __ext_tree_remove()
238 list_add_tail(&be->be_list, tmp); in __ext_tree_remove()
242 if (be && be->be_f_offset < end) { in __ext_tree_remove()
243 len1 = ext_f_end(be) - end; in __ext_tree_remove()
244 be->be_f_offset = end; in __ext_tree_remove()
245 if (be->be_state != PNFS_BLOCK_NONE_DATA) in __ext_tree_remove()
246 be->be_v_offset += be->be_length - len1; in __ext_tree_remove()
247 be->be_length = len1; in __ext_tree_remove()
258 struct rb_root *root; in ext_tree_insert() local
261 switch (new->be_state) { in ext_tree_insert()
264 root = &bl->bl_ext_rw; in ext_tree_insert()
268 root = &bl->bl_ext_ro; in ext_tree_insert()
272 return -EINVAL; in ext_tree_insert()
275 spin_lock(&bl->bl_ext_lock); in ext_tree_insert()
277 be = __ext_tree_search(root, new->be_f_offset); in ext_tree_insert()
278 if (!be || be->be_f_offset >= ext_f_end(new)) { in ext_tree_insert()
279 __ext_tree_insert(root, new, true); in ext_tree_insert()
280 } else if (new->be_f_offset >= be->be_f_offset) { in ext_tree_insert()
282 nfs4_put_deviceid_node(new->be_device); in ext_tree_insert()
285 sector_t new_len = ext_f_end(new) - ext_f_end(be); in ext_tree_insert()
286 sector_t diff = new->be_length - new_len; in ext_tree_insert()
288 new->be_f_offset += diff; in ext_tree_insert()
289 new->be_v_offset += diff; in ext_tree_insert()
290 new->be_length = new_len; in ext_tree_insert()
294 new->be_length = be->be_f_offset - new->be_f_offset; in ext_tree_insert()
295 __ext_tree_insert(root, new, true); in ext_tree_insert()
298 sector_t new_len = ext_f_end(new) - ext_f_end(be); in ext_tree_insert()
299 sector_t diff = new->be_length - new_len; in ext_tree_insert()
303 err = -EINVAL; in ext_tree_insert()
307 split->be_length = be->be_f_offset - split->be_f_offset; in ext_tree_insert()
308 split->be_device = nfs4_get_deviceid(new->be_device); in ext_tree_insert()
309 __ext_tree_insert(root, split, true); in ext_tree_insert()
311 new->be_f_offset += diff; in ext_tree_insert()
312 new->be_v_offset += diff; in ext_tree_insert()
313 new->be_length = new_len; in ext_tree_insert()
317 spin_unlock(&bl->bl_ext_lock); in ext_tree_insert()
322 __ext_tree_lookup(struct rb_root *root, sector_t isect, in __ext_tree_lookup() argument
325 struct rb_node *node; in __ext_tree_lookup() local
328 node = root->rb_node; in __ext_tree_lookup()
329 while (node) { in __ext_tree_lookup()
330 be = ext_node(node); in __ext_tree_lookup()
331 if (isect < be->be_f_offset) in __ext_tree_lookup()
332 node = node->rb_left; in __ext_tree_lookup()
334 node = node->rb_right; in __ext_tree_lookup()
350 spin_lock(&bl->bl_ext_lock); in ext_tree_lookup()
352 found = __ext_tree_lookup(&bl->bl_ext_ro, isect, ret); in ext_tree_lookup()
354 found = __ext_tree_lookup(&bl->bl_ext_rw, isect, ret); in ext_tree_lookup()
355 spin_unlock(&bl->bl_ext_lock); in ext_tree_lookup()
366 spin_lock(&bl->bl_ext_lock); in ext_tree_remove()
367 err = __ext_tree_remove(&bl->bl_ext_ro, start, end, &tmp); in ext_tree_remove()
369 err2 = __ext_tree_remove(&bl->bl_ext_rw, start, end, &tmp); in ext_tree_remove()
373 spin_unlock(&bl->bl_ext_lock); in ext_tree_remove()
380 ext_tree_split(struct rb_root *root, struct pnfs_block_extent *be, in ext_tree_split() argument
384 sector_t orig_len = be->be_length; in ext_tree_split()
388 return -ENOMEM; in ext_tree_split()
390 be->be_length = split - be->be_f_offset; in ext_tree_split()
392 new->be_f_offset = split; in ext_tree_split()
393 if (be->be_state != PNFS_BLOCK_NONE_DATA) in ext_tree_split()
394 new->be_v_offset = be->be_v_offset + be->be_length; in ext_tree_split()
395 new->be_length = orig_len - be->be_length; in ext_tree_split()
396 new->be_state = be->be_state; in ext_tree_split()
397 new->be_tag = be->be_tag; in ext_tree_split()
398 new->be_device = nfs4_get_deviceid(be->be_device); in ext_tree_split()
400 __ext_tree_insert(root, new, false); in ext_tree_split()
408 struct rb_root *root = &bl->bl_ext_rw; in ext_tree_mark_written() local
414 spin_lock(&bl->bl_ext_lock); in ext_tree_mark_written()
418 err = __ext_tree_remove(&bl->bl_ext_ro, start, end, &tmp); in ext_tree_mark_written()
425 for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) { in ext_tree_mark_written()
426 if (be->be_f_offset >= end) in ext_tree_mark_written()
429 if (be->be_state != PNFS_BLOCK_INVALID_DATA || be->be_tag) in ext_tree_mark_written()
432 if (be->be_f_offset < start) { in ext_tree_mark_written()
436 sector_t diff = start - be->be_f_offset; in ext_tree_mark_written()
438 left->be_length += diff; in ext_tree_mark_written()
440 be->be_f_offset += diff; in ext_tree_mark_written()
441 be->be_v_offset += diff; in ext_tree_mark_written()
442 be->be_length -= diff; in ext_tree_mark_written()
444 err = ext_tree_split(root, be, start); in ext_tree_mark_written()
454 sector_t diff = end - be->be_f_offset; in ext_tree_mark_written()
456 be->be_length -= diff; in ext_tree_mark_written()
458 right->be_f_offset -= diff; in ext_tree_mark_written()
459 right->be_v_offset -= diff; in ext_tree_mark_written()
460 right->be_length += diff; in ext_tree_mark_written()
462 err = ext_tree_split(root, be, end); in ext_tree_mark_written()
468 if (be->be_f_offset >= start && ext_f_end(be) <= end) { in ext_tree_mark_written()
469 be->be_tag = EXTENT_WRITTEN; in ext_tree_mark_written()
470 be = ext_try_to_merge_left(root, be); in ext_tree_mark_written()
471 be = ext_try_to_merge_right(root, be); in ext_tree_mark_written()
475 if (bl->bl_lwb < lwb) in ext_tree_mark_written()
476 bl->bl_lwb = lwb; in ext_tree_mark_written()
477 spin_unlock(&bl->bl_ext_lock); in ext_tree_mark_written()
485 if (bl->bl_scsi_layout) in ext_tree_layoutupdate_size()
494 if (arg->layoutupdate_pages != &arg->layoutupdate_page) { in ext_tree_free_commitdata()
498 put_page(arg->layoutupdate_pages[i]); in ext_tree_free_commitdata()
499 vfree(arg->start_p); in ext_tree_free_commitdata()
500 kfree(arg->layoutupdate_pages); in ext_tree_free_commitdata()
502 put_page(arg->layoutupdate_page); in ext_tree_free_commitdata()
508 p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data, in encode_block_extent()
510 p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT); in encode_block_extent()
511 p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT); in encode_block_extent()
519 p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT); in encode_scsi_range()
520 return xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT); in encode_scsi_range()
529 spin_lock(&bl->bl_ext_lock); in ext_tree_encode_commit()
530 for (be = ext_tree_first(&bl->bl_ext_rw); be; be = ext_tree_next(be)) { in ext_tree_encode_commit()
531 if (be->be_state != PNFS_BLOCK_INVALID_DATA || in ext_tree_encode_commit()
532 be->be_tag != EXTENT_WRITTEN) in ext_tree_encode_commit()
538 ret = -ENOSPC; in ext_tree_encode_commit()
542 if (bl->bl_scsi_layout) in ext_tree_encode_commit()
546 be->be_tag = EXTENT_COMMITTING; in ext_tree_encode_commit()
548 *lastbyte = bl->bl_lwb - 1; in ext_tree_encode_commit()
549 bl->bl_lwb = 0; in ext_tree_encode_commit()
550 spin_unlock(&bl->bl_ext_lock); in ext_tree_encode_commit()
558 struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout); in ext_tree_prepare_commit()
565 arg->layoutupdate_page = alloc_page(GFP_NOFS); in ext_tree_prepare_commit()
566 if (!arg->layoutupdate_page) in ext_tree_prepare_commit()
567 return -ENOMEM; in ext_tree_prepare_commit()
568 start_p = page_address(arg->layoutupdate_page); in ext_tree_prepare_commit()
569 arg->layoutupdate_pages = &arg->layoutupdate_page; in ext_tree_prepare_commit()
572 ret = ext_tree_encode_commit(bl, start_p + 1, buffer_size, &count, &arg->lastbytewritten); in ext_tree_prepare_commit()
579 arg->layoutupdate_pages = in ext_tree_prepare_commit()
582 if (!arg->layoutupdate_pages) in ext_tree_prepare_commit()
583 return -ENOMEM; in ext_tree_prepare_commit()
587 kfree(arg->layoutupdate_pages); in ext_tree_prepare_commit()
588 return -ENOMEM; in ext_tree_prepare_commit()
595 arg->layoutupdate_len = ext_tree_layoutupdate_size(bl, count); in ext_tree_prepare_commit()
597 if (unlikely(arg->layoutupdate_pages != &arg->layoutupdate_page)) { in ext_tree_prepare_commit()
598 void *p = start_p, *end = p + arg->layoutupdate_len; in ext_tree_prepare_commit()
602 arg->start_p = start_p; in ext_tree_prepare_commit()
605 arg->layoutupdate_pages[i++] = page; in ext_tree_prepare_commit()
617 struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout); in ext_tree_mark_committed()
618 struct rb_root *root = &bl->bl_ext_rw; in ext_tree_mark_committed() local
623 ext_tree_free_commitdata(arg, arg->layoutupdate_len); in ext_tree_mark_committed()
625 spin_lock(&bl->bl_ext_lock); in ext_tree_mark_committed()
626 for (be = ext_tree_first(root); be; be = ext_tree_next(be)) { in ext_tree_mark_committed()
627 if (be->be_state != PNFS_BLOCK_INVALID_DATA || in ext_tree_mark_committed()
628 be->be_tag != EXTENT_COMMITTING) in ext_tree_mark_committed()
637 be->be_tag = EXTENT_WRITTEN; in ext_tree_mark_committed()
639 be->be_state = PNFS_BLOCK_READWRITE_DATA; in ext_tree_mark_committed()
640 be->be_tag = 0; in ext_tree_mark_committed()
643 be = ext_try_to_merge_left(root, be); in ext_tree_mark_committed()
644 be = ext_try_to_merge_right(root, be); in ext_tree_mark_committed()
646 spin_unlock(&bl->bl_ext_lock); in ext_tree_mark_committed()