[Devel] [PATCH rh7] ploop: push_backup: optimize ploop_pb_put_reported()

[Maxim Patlasov]

To process an extent [clu, clu + len) coming from userspace, let's firstly
find the leftmost preq in the tree matching this interval.

Then, we can iterate to the right by rb_next() until we meet a preq that
doesn't match.

That's it because any preq to the right would have any higher req_cluster,
and hence doesn't match too.

https://jira.sw.ru/browse/PSBM-45000

Signed-off-by: Maxim Patlasov <mpatlasov at virtuozzo.com>
---
 drivers/block/ploop/dev.c         |    9 +--
 drivers/block/ploop/push_backup.c |  107 +++++++++++++++++++++++++------------
 2 files changed, 73 insertions(+), 43 deletions(-)

diff --git a/drivers/block/ploop/dev.c b/drivers/block/ploop/dev.c
index c103b79..e2c5d9e 100644
--- a/drivers/block/ploop/dev.c
+++ b/drivers/block/ploop/dev.c
@@ -4627,13 +4627,8 @@ static int ploop_push_backup_io_write(struct ploop_device *plo, unsigned long ar
 		goto io_write_done;
 
 	rc = 0;
-	for (i = 0; i < ctl->n_extents; i++) {
-		cluster_t j;
-		for (j = e[i].clu; j < e[i].clu + e[i].len; j++)
-			ploop_pb_put_reported(plo->pbd, j, 1);
-                /* OPTIMIZE ME LATER: like this:
-		 * ploop_pb_put_reported(plo->pbd, e[i].clu, e[i].len); */
-	}
+	for (i = 0; i < ctl->n_extents; i++)
+		ploop_pb_put_reported(plo->pbd, e[i].clu, e[i].len);
 
 io_write_done:
 	kfree(e);
diff --git a/drivers/block/ploop/push_backup.c b/drivers/block/ploop/push_backup.c
index 3a46339..98e2f1e 100644
--- a/drivers/block/ploop/push_backup.c
+++ b/drivers/block/ploop/push_backup.c
@@ -329,11 +329,23 @@ static void ploop_pb_add_req_to_reported(struct ploop_pushbackup_desc *pbd,
 	ploop_pb_add_req_to_tree(preq, &pbd->reported_tree);
 }
 
+static inline bool preq_match(struct ploop_request *preq, cluster_t clu,
+			      cluster_t len)
+{
+	return preq &&
+		clu <= preq->req_cluster &&
+		preq->req_cluster < clu + len;
+}
+
+/* returns leftmost preq which req_cluster >= clu */
 static struct ploop_request *ploop_pb_get_req_from_tree(struct rb_root *tree,
-							cluster_t clu)
+						cluster_t clu, cluster_t len,
+						struct ploop_request **npreq)
 {
 	struct rb_node *n = tree->rb_node;
-	struct ploop_request *p;
+	struct ploop_request *p = NULL;
+
+	*npreq = NULL;
 
 	while (n) {
 		p = rb_entry(n, struct ploop_request, reloc_link);
@@ -342,11 +354,31 @@ static struct ploop_request *ploop_pb_get_req_from_tree(struct rb_root *tree,
 			n = n->rb_left;
 		else if (clu > p->req_cluster)
 			n = n->rb_right;
-		else {
+		else { /* perfect match */
+			n = rb_next(n);
+			if (n)
+				*npreq = rb_entry(n, struct ploop_request,
+						  reloc_link);
 			rb_erase(&p->reloc_link, tree);
 			return p;
 		}
 	}
+	/* here p is not perfect, but it's closest */
+
+	if (p && p->req_cluster < clu) {
+		n = rb_next(&p->reloc_link);
+		if (n)
+			p = rb_entry(n, struct ploop_request, reloc_link);
+	}
+
+	if (preq_match(p, clu, len)) {
+		n = rb_next(&p->reloc_link);
+		if (n)
+			*npreq = rb_entry(n, struct ploop_request, reloc_link);
+		rb_erase(&p->reloc_link, tree);
+		return p;
+	}
+
 	return NULL;
 }
 
@@ -393,20 +425,6 @@ ploop_pb_get_first_req_from_reported(struct ploop_pushbackup_desc *pbd)
 	return ploop_pb_get_first_req_from_tree(&pbd->reported_tree, NULL);
 }
 
-static struct ploop_request *
-ploop_pb_get_req_from_pending(struct ploop_pushbackup_desc *pbd,
-			      cluster_t clu)
-{
-	return ploop_pb_get_req_from_tree(&pbd->pending_tree, clu);
-}
-
-static struct ploop_request *
-ploop_pb_get_req_from_reported(struct ploop_pushbackup_desc *pbd,
-			       cluster_t clu)
-{
-	return ploop_pb_get_req_from_tree(&pbd->reported_tree, clu);
-}
-
 int ploop_pb_preq_add_pending(struct ploop_pushbackup_desc *pbd,
 			       struct ploop_request *preq)
 {
@@ -552,27 +570,46 @@ get_pending_unlock:
 	return err;
 }
 
+static void ploop_pb_process_extent(struct rb_root *tree, cluster_t clu,
+				    cluster_t len, struct list_head *ready_list,
+				    int *n_found)
+{
+	struct ploop_request *preq, *npreq;
+
+	preq = ploop_pb_get_req_from_tree(tree, clu, len, &npreq);
+
+	while (preq) {
+		struct rb_node *n;
+
+		__set_bit(PLOOP_REQ_PUSH_BACKUP, &preq->state);
+		list_add(&preq->list, ready_list);
+
+		if (n_found)
+			(*n_found)++;
+
+		if (!preq_match(npreq, clu, len))
+			break;
+
+		preq = npreq;
+		n = rb_next(&preq->reloc_link);
+		if (n)
+			npreq = rb_entry(n, struct ploop_request, reloc_link);
+		else
+			npreq = NULL;
+		rb_erase(&preq->reloc_link, tree);
+	}
+}
+
 void ploop_pb_put_reported(struct ploop_pushbackup_desc *pbd,
 			   cluster_t clu, cluster_t len)
 {
-	struct ploop_request *preq;
 	int n_found = 0;
-
-	/* OPTIMIZE ME LATER: find leftmost item for [clu, clu+len),
-	 * then rb_next() while req_cluster < clu+len.
-	 * Do this firstly for reported, then for pending */
-	BUG_ON(len != 1);
+	LIST_HEAD(ready_list);
 
 	spin_lock(&pbd->ppb_lock);
 
-	preq = ploop_pb_get_req_from_reported(pbd, clu);
-	if (!preq)
-		preq = ploop_pb_get_req_from_pending(pbd, clu);
-	else
-		n_found++;
-
-	if (preq)
-		__set_bit(PLOOP_REQ_PUSH_BACKUP, &preq->state);
+	ploop_pb_process_extent(&pbd->reported_tree, clu, len, &ready_list, &n_found);
+	ploop_pb_process_extent(&pbd->pending_tree, clu, len, &ready_list, NULL);
 
 	/*
 	 * If preq not found above, it's unsolicited report. Then it's
@@ -600,13 +637,11 @@ void ploop_pb_put_reported(struct ploop_pushbackup_desc *pbd,
 
 	spin_unlock(&pbd->ppb_lock);
 
-	if (preq) {
-		struct ploop_device *plo = preq->plo;
-		BUG_ON(preq->req_cluster != clu);
-		BUG_ON(plo != pbd->plo);
+	if (!list_empty(&ready_list)) {
+		struct ploop_device *plo = pbd->plo;
 
 		spin_lock_irq(&plo->lock);
-		list_add_tail(&preq->list, &plo->ready_queue);
+		list_splice(&ready_list, plo->ready_queue.prev);
 		if (test_bit(PLOOP_S_WAIT_PROCESS, &plo->state))
 			wake_up_interruptible(&plo->waitq);
 		spin_unlock_irq(&plo->lock);