nfs/blocklayout/extent_tree.c

26 ext_tree_prev(struct pnfs_block_extent *be)
28 	struct rb_node *node = rb_prev(&be->be_node);
33 ext_tree_next(struct pnfs_block_extent *be)
35 	struct rb_node *node = rb_next(&be->be_node);
40 ext_f_end(struct pnfs_block_extent *be)
42 	return be->be_f_offset + be->be_length;
49 	struct pnfs_block_extent *be = NULL;
52 		be = ext_node(node);
53 		if (start < be->be_f_offset)
55 		else if (start >= ext_f_end(be))
58 			return be;
61 	if (be) {
62 		if (start < be->be_f_offset)
63 			return be;
65 		if (start >= ext_f_end(be))
66 			return ext_tree_next(be);
95 ext_try_to_merge_left(struct rb_root *root, struct pnfs_block_extent *be)
97 	struct pnfs_block_extent *left = ext_tree_prev(be);
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);
107 	return be;
111 ext_try_to_merge_right(struct rb_root *root, struct pnfs_block_extent *be)
113 	struct pnfs_block_extent *right = ext_tree_next(be);
115 	if (right && ext_can_merge(be, right)) {
116 		be->be_length += right->be_length;
122 	return be;
127 	struct pnfs_block_extent *be, *tmp;
129 	list_for_each_entry_safe(be, tmp, head, be_list) {
130 		nfs4_put_deviceid_node(be->be_device);
131 		kfree(be);
140 	struct pnfs_block_extent *be;
144 		be = ext_node(parent);
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);
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);
180 	struct pnfs_block_extent *be;
185 	be = __ext_tree_search(root, start);
186 	if (!be)
188 	if (be->be_f_offset >= end)
191 	orig_v_offset = be->be_v_offset;
192 	orig_len = be->be_length;
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;
207 			be->be_length = len1;
210 			if (be->be_state != PNFS_BLOCK_NONE_DATA) {
215 			new->be_state = be->be_state;
216 			new->be_tag = be->be_tag;
217 			new->be_device = nfs4_get_deviceid(be->be_device);
221 			be->be_f_offset = end;
222 			if (be->be_state != PNFS_BLOCK_NONE_DATA) {
223 				be->be_v_offset =
226 			be->be_length = len2;
230 			be->be_length = len1;
231 			be = ext_tree_next(be);
234 		while (be && ext_f_end(be) <= end) {
235 			struct pnfs_block_extent *next = ext_tree_next(be);
237 			rb_erase(&be->be_node, root);
238 			list_add_tail(&be->be_list, tmp);
239 			be = next;
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;
257 	struct pnfs_block_extent *be;
277 	be = __ext_tree_search(root, new->be_f_offset);
278 	if (!be || be->be_f_offset >= ext_f_end(new)) {
280 	} else if (new->be_f_offset >= be->be_f_offset) {
281 		if (ext_f_end(new) <= ext_f_end(be)) {
285 			sector_t new_len = ext_f_end(new) - ext_f_end(be);
293 	} else if (ext_f_end(new) <= ext_f_end(be)) {
294 		new->be_length = be->be_f_offset - new->be_f_offset;
298 		sector_t new_len = ext_f_end(new) - ext_f_end(be);
307 		split->be_length = be->be_f_offset - split->be_f_offset;
326 	struct pnfs_block_extent *be;
330 		be = ext_node(node);
331 		if (isect < be->be_f_offset)
333 		else if (isect >= ext_f_end(be))
336 			*ret = *be;
380 ext_tree_split(struct rb_root *root, struct pnfs_block_extent *be,
384 	sector_t orig_len = be->be_length;
390 	be->be_length = split - be->be_f_offset;
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);
410 	struct pnfs_block_extent *be;
425 	for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) {
426 		if (be->be_f_offset >= end)
429 		if (be->be_state != PNFS_BLOCK_INVALID_DATA || be->be_tag)
432 		if (be->be_f_offset < start) {
433 			struct pnfs_block_extent *left = ext_tree_prev(be);
435 			if (left && ext_can_merge(left, be)) {
436 				sector_t diff = start - be->be_f_offset;
440 				be->be_f_offset += diff;
441 				be->be_v_offset += diff;
442 				be->be_length -= diff;
444 				err = ext_tree_split(root, be, start);
450 		if (ext_f_end(be) > end) {
451 			struct pnfs_block_extent *right = ext_tree_next(be);
453 			if (right && ext_can_merge(be, right)) {
454 				sector_t diff = end - be->be_f_offset;
456 				be->be_length -= diff;
462 				err = ext_tree_split(root, be, end);
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);
506 static __be32 *encode_block_extent(struct pnfs_block_extent *be, __be32 *p)
508 	p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data,
510 	p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
511 	p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
517 static __be32 *encode_scsi_range(struct pnfs_block_extent *be, __be32 *p)
519 	p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
520 	return xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
526 	struct pnfs_block_extent *be;
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)
543 			p = encode_scsi_range(be, p);
545 			p = encode_block_extent(be, p);
546 		be->be_tag = EXTENT_COMMITTING;
619 	struct pnfs_block_extent *be;
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)
637 			be->be_tag = EXTENT_WRITTEN;
639 			be->be_state = PNFS_BLOCK_READWRITE_DATA;
640 			be->be_tag = 0;
643 		be = ext_try_to_merge_left(root, be);
644 		be = ext_try_to_merge_right(root, be);