sna/damage: Only track the mode globally

As damage accumulation is handled modally, we do not need to track the
mode per elt and so attempt to simplify the code.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

2 files changed, 125 insertions, 118 deletions

diff --git a/src/sna/sna_damage.c b/src/sna/sna_damage.c
index b5d00846..0194f5ca 100644
--- a/src/sna/sna_damage.c
+++ b/src/sna/sna_damage.c
@@ -31,6 +31,23 @@ SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 #include "sna.h"
 #include "sna_damage.h"
 
+/*
+ * sna_damage is a batching layer on top of the regular pixman_region_t.
+ * It is required as the ever-growing accumulation of invidual small
+ * damage regions is an O(n^2) operation. Instead the accumulation of a
+ * batch can be done in closer to O(n.lgn), and so prevents abysmal
+ * performance in x11perf -copywinwin10.
+ *
+ * As with the core of SNA, damage is handled modally. That is, it
+ * accumulates whilst rendering and then subtracts during migration of the
+ * pixmap from GPU to CPU or vice versa. As such we can track the current
+ * mode globally and when that mode switches perform the update of the region
+ * in a single operation.
+ *
+ * Furthermore, we can track whether the whole pixmap is damaged and so
+ * cheapy discard no-ops.
+ */
+
 #if DEBUG_DAMAGE
 #undef DBG
 #define DBG(x) ErrorF x
@@ -121,10 +138,6 @@ struct sna_damage_box {
 };
 
 struct sna_damage_elt {
-	enum mode {
-		ADD,
-		SUBTRACT,
-	} mode;
 	BoxPtr box;
 	uint16_t n;
 };
@@ -134,13 +147,12 @@ static struct sna_damage *_sna_damage_create(void)
 	struct sna_damage *damage;
 
 	damage = malloc(sizeof(*damage));
-	damage->all = 0;
 	damage->n = 0;
 	damage->size = 16;
 	damage->elts = malloc(sizeof(*damage->elts) * damage->size);
 	list_init(&damage->boxes);
 	damage->last_box = NULL;
-	damage->mode = ADD;
+	damage->mode = DAMAGE_ADD;
 	pixman_region_init(&damage->region);
 	damage->extents.x1 = damage->extents.y1 = MAXSHORT;
 	damage->extents.x2 = damage->extents.y2 = MINSHORT;
@@ -180,18 +192,15 @@ static BoxPtr _sna_damage_create_boxes(struct sna_damage *damage,
 
 static void
 _sna_damage_create_elt(struct sna_damage *damage,
-		       enum mode mode,
 		       const BoxRec *boxes, int count)
 {
 	struct sna_damage_elt *elt;
 
-	DBG(("    %s(%s): n=%d, prev=(%s, remain %d)\n", __FUNCTION__,
-	     mode == ADD ? "add" : "subtract",
+	DBG(("    %s: n=%d, prev=(remain %d)\n", __FUNCTION__,
 	     damage->n,
-	     damage->n ? damage->elts[damage->n-1].mode == ADD ? "add" : "subtract" : "none",
 	     damage->last_box ? damage->last_box->remain : 0));
 
-	if (damage->last_box && damage->elts[damage->n-1].mode == mode) {
+	if (damage->last_box) {
 		int n;
 
 		n = count;
@@ -225,7 +234,6 @@ _sna_damage_create_elt(struct sna_damage *damage,
 	DBG(("    %s(): new elt\n", __FUNCTION__));
 
 	elt = damage->elts + damage->n++;
-	elt->mode = mode;
 	elt->n = count;
 	elt->box = memcpy(_sna_damage_create_boxes(damage, count),
 			  boxes, count * sizeof(BoxRec));
@@ -233,20 +241,17 @@ _sna_damage_create_elt(struct sna_damage *damage,
 
 static void
 _sna_damage_create_elt_with_translation(struct sna_damage *damage,
-					enum mode mode,
 					const BoxRec *boxes, int count,
 					int16_t dx, int16_t dy)
 {
 	struct sna_damage_elt *elt;
 	int i;
 
-	DBG(("    %s(%s): n=%d, prev=(%s, remain %d)\n", __FUNCTION__,
-	     mode == ADD ? "add" : "subtract",
+	DBG(("    %s: n=%d, prev=(remain %d)\n", __FUNCTION__,
 	     damage->n,
-	     damage->n ? damage->elts[damage->n-1].mode == ADD ? "add" : "subtract" : "none",
 	     damage->last_box ? damage->last_box->remain : 0));
 
-	if (damage->last_box && damage->elts[damage->n-1].mode == mode) {
+	if (damage->last_box) {
 		int n;
 		BoxRec *b;
 
@@ -287,7 +292,6 @@ _sna_damage_create_elt_with_translation(struct sna_damage *damage,
 	DBG(("    %s(): new elt\n", __FUNCTION__));
 
 	elt = damage->elts + damage->n++;
-	elt->mode = mode;
 	elt->n = count;
 	elt->box = _sna_damage_create_boxes(damage, count);
 	for (i = 0; i < count; i++) {
@@ -309,64 +313,35 @@ static void free_list(struct list *head)
 
 static void __sna_damage_reduce(struct sna_damage *damage)
 {
-	int n, m, j;
-	int nboxes;
+	int n, nboxes;
 	BoxPtr boxes;
 	pixman_region16_t tmp, *region = &damage->region;
 
-	assert(!damage->all);
+	assert(damage->mode != DAMAGE_ALL);
+	assert(damage->n);
 
 	DBG(("    reduce: before damage.n=%d region.n=%d\n",
 	     damage->n, REGION_NUM_RECTS(region)));
 
-	m = 0;
 	nboxes = damage->elts[0].n;
-	boxes = damage->elts[0].box;
-	for (n = 1; n < damage->n; n++) {
-		if (damage->elts[n].mode != damage->elts[m].mode) {
-			if (!boxes) {
-				boxes = malloc(sizeof(BoxRec)*nboxes);
-				nboxes = 0;
-				for (j = m; j < n; j++) {
-					memcpy(boxes+nboxes,
-					       damage->elts[j].box,
-					       damage->elts[j].n*sizeof(BoxRec));
-					nboxes += damage->elts[j].n;
-				}
-			}
-
-			pixman_region_init_rects(&tmp, boxes, nboxes);
-			if (damage->elts[m].mode == ADD)
-				pixman_region_union(region, region, &tmp);
-			else
-				pixman_region_subtract(region, region, &tmp);
-			pixman_region_fini(&tmp);
-
-			if (boxes != damage->elts[m].box)
-				free(boxes);
-
-			m = n;
-			boxes = damage->elts[n].box;
-			nboxes = damage->elts[n].n;
-		} else {
-			boxes = NULL;
+	if (damage->n == 1) {
+		boxes = damage->elts[0].box;
+	} else {
+		for (n = 1; n < damage->n; n++)
 			nboxes += damage->elts[n].n;
-		}
-	}
 
-	if (!boxes) {
 		boxes = malloc(sizeof(BoxRec)*nboxes);
 		nboxes = 0;
-		for (j = m; j < n; j++) {
+		for (n = 0; n < damage->n; n++) {
 			memcpy(boxes+nboxes,
-			       damage->elts[j].box,
-			       damage->elts[j].n*sizeof(BoxRec));
-			nboxes += damage->elts[j].n;
+			       damage->elts[n].box,
+			       damage->elts[n].n*sizeof(BoxRec));
+			nboxes += damage->elts[n].n;
 		}
 	}
 
 	pixman_region_init_rects(&tmp, boxes, nboxes);
-	if (damage->elts[m].mode == ADD)
+	if (damage->mode == DAMAGE_ADD)
 		pixman_region_union(region, region, &tmp);
 	else
 		pixman_region_subtract(region, region, &tmp);
@@ -374,13 +349,13 @@ static void __sna_damage_reduce(struct sna_damage *damage)
 
 	damage->extents = region->extents;
 
-	if (boxes != damage->elts[m].box)
+	if (boxes != damage->elts[0].box)
 		free(boxes);
 
 	damage->n = 0;
+	damage->mode = DAMAGE_ADD;
 	free_list(&damage->boxes);
 	damage->last_box = NULL;
-	damage->mode = ADD;
 
 	DBG(("    reduce: after region.n=%d\n", REGION_NUM_RECTS(region)));
 }
@@ -393,13 +368,14 @@ inline static struct sna_damage *__sna_damage_add(struct sna_damage *damage,
 
 	if (!damage)
 		damage = _sna_damage_create();
-
-	if (damage->all)
+	else switch (damage->mode) {
+	case DAMAGE_ALL:
 		return damage;
-
-	if (damage->mode == SUBTRACT)
+	case DAMAGE_SUBTRACT:
 		__sna_damage_reduce(damage);
-	damage->mode = ADD;
+	case DAMAGE_ADD:
+		break;
+	}
 
 	if (REGION_NUM_RECTS(&damage->region) <= 1) {
 		pixman_region_union(&damage->region, &damage->region, region);
@@ -411,9 +387,8 @@ inline static struct sna_damage *__sna_damage_add(struct sna_damage *damage,
 					     &region->extents) == PIXMAN_REGION_IN)
 		return damage;
 
-	_sna_damage_create_elt(damage, ADD,
-			       REGION_RECTS(region),
-			       REGION_NUM_RECTS(region));
+	_sna_damage_create_elt(damage,
+			       REGION_RECTS(region), REGION_NUM_RECTS(region));
 
 	if (damage->extents.x1 > region->extents.x1)
 		damage->extents.x1 = region->extents.x1;
@@ -486,29 +461,34 @@ __sna_damage_add_boxes(struct sna_damage *damage,
 
 	if (!damage)
 		damage = _sna_damage_create();
-
-	if (damage->all)
+	else switch (damage->mode) {
+	case DAMAGE_ALL:
 		return damage;
-
-	if (damage->mode == SUBTRACT)
+	case DAMAGE_SUBTRACT:
 		__sna_damage_reduce(damage);
-	damage->mode = ADD;
+	case DAMAGE_ADD:
+		break;
+	}
 
 	if (pixman_region_contains_rectangle(&damage->region,
 					     &extents) == PIXMAN_REGION_IN)
 		return damage;
 
-	_sna_damage_create_elt_with_translation(damage, ADD, box, n, dx, dy);
+	_sna_damage_create_elt_with_translation(damage, box, n, dx, dy);
 
-	if (damage->extents.x1 > extents.x1)
-		damage->extents.x1 = extents.x1;
-	if (damage->extents.x2 < extents.x2)
-		damage->extents.x2 = extents.x2;
-
-	if (damage->extents.y1 > extents.y1)
-		damage->extents.y1 = extents.y1;
-	if (damage->extents.y2 < extents.y2)
-		damage->extents.y2 = extents.y2;
+	if (REGION_NUM_RECTS(&damage->region) <= 1) {
+		__sna_damage_reduce(damage);
+	} else {
+		if (damage->extents.x1 > extents.x1)
+			damage->extents.x1 = extents.x1;
+		if (damage->extents.x2 < extents.x2)
+			damage->extents.x2 = extents.x2;
+
+		if (damage->extents.y1 > extents.y1)
+			damage->extents.y1 = extents.y1;
+		if (damage->extents.y2 < extents.y2)
+			damage->extents.y2 = extents.y2;
+	}
 
 	return damage;
 }
@@ -524,7 +504,7 @@ struct sna_damage *_sna_damage_add_boxes(struct sna_damage *damage,
 	     _debug_describe_damage(damage_buf, sizeof(damage_buf), damage),
 	     box->x1, box->y1, box->x2, box->y2, n));
 
-	damage = __sna_damage_add_box(damage, boxes, n, dx, dy);
+	damage = __sna_damage_add_boxes(damage, boxes, n, dx, dy);
 
 	ErrorF("  = %s\n",
 	       _debug_describe_damage(damage_buf, sizeof(damage_buf), damage));
@@ -540,6 +520,12 @@ struct sna_damage *_sna_damage_add_boxes(struct sna_damage *damage,
 }
 #endif
 
+static void _pixman_region_union_box(RegionRec *region, const BoxRec *box)
+{
+	RegionRec u = { *box, NULL };
+	pixman_region_union(region, region, &u);
+}
+
 inline static struct sna_damage *__sna_damage_add_box(struct sna_damage *damage,
 						      const BoxRec *box)
 {
@@ -548,25 +534,31 @@ inline static struct sna_damage *__sna_damage_add_box(struct sna_damage *damage,
 
 	if (!damage)
 		damage = _sna_damage_create();
-
-	if (damage->all)
+	else switch (damage->mode) {
+	case DAMAGE_ALL:
 		return damage;
-
-	if (damage->mode == SUBTRACT)
+	case DAMAGE_SUBTRACT:
 		__sna_damage_reduce(damage);
-	damage->mode = ADD;
+	case DAMAGE_ADD:
+		break;
+	}
 
-	if (REGION_NUM_RECTS(&damage->region) == 0) {
+	switch (REGION_NUM_RECTS(&damage->region)) {
+	case 0:
 		pixman_region_init_rects(&damage->region, box, 1);
 		damage->extents = *box;
 		return damage;
+	case 1:
+		_pixman_region_union_box(&damage->region, box);
+		damage->extents = damage->region.extents;
+		return damage;
 	}
 
 	if (pixman_region_contains_rectangle(&damage->region,
 					     (BoxPtr)box) == PIXMAN_REGION_IN)
 		return damage;
 
-	_sna_damage_create_elt(damage, ADD, box, 1);
+	_sna_damage_create_elt(damage, box, 1);
 
 	if (damage->extents.x1 > box->x1)
 		damage->extents.x1 = box->x1;
@@ -621,8 +613,7 @@ struct sna_damage *_sna_damage_all(struct sna_damage *damage,
 
 	pixman_region_init_rect(&damage->region, 0, 0, width, height);
 	damage->extents = damage->region.extents;
-	damage->mode = ADD;
-	damage->all = 1;
+	damage->mode = DAMAGE_ALL;
 
 	return damage;
 }
@@ -632,9 +623,6 @@ struct sna_damage *_sna_damage_is_all(struct sna_damage *damage,
 {
 	BoxRec box;
 
-	if (damage->mode == SUBTRACT)
-		return damage;
-
 	box.x1 = box.y1 = 0;
 	box.x2 = width;
 	box.y2 = height;
@@ -677,7 +665,10 @@ static struct sna_damage *__sna_damage_subtract(struct sna_damage *damage,
 	if (!sna_damage_maybe_contains_box(damage, &region->extents))
 		return damage;
 
-	if (damage->n == 0) {
+	if (damage->mode != DAMAGE_SUBTRACT) {
+		if (damage->n)
+			__sna_damage_reduce(damage);
+
 		if (pixman_region_equal(region, &damage->region)) {
 			__sna_damage_destroy(damage);
 			return NULL;
@@ -694,16 +685,15 @@ static struct sna_damage *__sna_damage_subtract(struct sna_damage *damage,
 					       &damage->region,
 					       region);
 			damage->extents = damage->region.extents;
-			damage->all = 0;
+			damage->mode = DAMAGE_ADD; /* reduce from ALL */
 			return damage;
 		}
+
+		damage->mode = DAMAGE_SUBTRACT;
 	}
 
-	damage->all = 0;
-	damage->mode = SUBTRACT;
-	_sna_damage_create_elt(damage, SUBTRACT,
-			       REGION_RECTS(region),
-			       REGION_NUM_RECTS(region));
+	_sna_damage_create_elt(damage,
+			       REGION_RECTS(region), REGION_NUM_RECTS(region));
 
 	return damage;
 }
@@ -748,7 +738,10 @@ inline static struct sna_damage *__sna_damage_subtract_box(struct sna_damage *da
 	if (!sna_damage_maybe_contains_box(damage, box))
 		return damage;
 
-	if (damage->n == 0) {
+	if (damage->mode != DAMAGE_SUBTRACT) {
+		if (damage->n)
+			__sna_damage_reduce(damage);
+
 		if (!pixman_region_not_empty(&damage->region)) {
 			__sna_damage_destroy(damage);
 			return NULL;
@@ -762,15 +755,14 @@ inline static struct sna_damage *__sna_damage_subtract_box(struct sna_damage *da
 					       &damage->region,
 					       &region);
 			damage->extents = damage->region.extents;
-			damage->all = 0;
+			damage->mode = DAMAGE_ADD;
 			return damage;
 		}
-	}
 
-	damage->all = 0;
-	damage->mode = SUBTRACT;
-	_sna_damage_create_elt(damage, SUBTRACT, box, 1);
+		damage->mode = DAMAGE_SUBTRACT;
+	}
 
+	_sna_damage_create_elt(damage, box, 1);
 	return damage;
 }
 
@@ -805,14 +797,14 @@ static int _sna_damage_contains_box(struct sna_damage *damage,
 	if (!damage)
 		return PIXMAN_REGION_OUT;
 
-	if (damage->all)
+	if (damage->mode == DAMAGE_ALL)
 		return PIXMAN_REGION_IN;
 
 	if (!sna_damage_maybe_contains_box(damage, box))
 		return PIXMAN_REGION_OUT;
 
 	if (damage->n) {
-		if (damage->mode != SUBTRACT) {
+		if (damage->mode != DAMAGE_SUBTRACT) {
 			int ret = pixman_region_contains_rectangle(&damage->region,
 								   (BoxPtr)box);
 			if (ret == PIXMAN_REGION_IN)
@@ -859,6 +851,11 @@ static Bool _sna_damage_intersect(struct sna_damage *damage,
 	if (!damage)
 		return FALSE;
 
+	if (damage->mode == DAMAGE_ALL) {
+		RegionCopy(result, region);
+		return TRUE;
+	}
+
 	if (region->extents.x2 <= damage->extents.x1 ||
 	    region->extents.x1 >= damage->extents.x2)
 		return FALSE;
diff --git a/src/sna/sna_damage.h b/src/sna/sna_damage.h
index 454ad84a..c402304f 100644
--- a/src/sna/sna_damage.h
+++ b/src/sna/sna_damage.h
@@ -4,15 +4,20 @@
 #include <regionstr.h>
 #include <list.h>
 
-#define fastcall __attribute__((regparm(3)))
+#include "compiler.h"
 
 struct sna_damage_elt;
 struct sna_damage_box;
 
 struct sna_damage {
 	BoxRec extents;
-	int n, size, mode, all;
 	pixman_region16_t region;
+	enum sna_damage_mode {
+		DAMAGE_ADD = 0,
+		DAMAGE_SUBTRACT,
+		DAMAGE_ALL,
+	} mode;
+	int n, size;
 	struct sna_damage_elt *elts;
 	struct sna_damage_box *last_box;
 	struct list boxes;
@@ -52,11 +57,16 @@ static inline bool sna_damage_is_all(struct sna_damage **damage,
 	if (*damage == NULL)
 		return false;
 
-	if ((*damage)->all)
+	switch ((*damage)->mode) {
+	case DAMAGE_ALL:
 		return true;
-
-	*damage = _sna_damage_is_all(*damage, width, height);
-	return (*damage)->all;
+	case DAMAGE_SUBTRACT:
+		return false;
+	default:
+	case DAMAGE_ADD:
+		*damage = _sna_damage_is_all(*damage, width, height);
+		return (*damage)->mode == DAMAGE_ALL;
+	}
 }
 
 struct sna_damage *_sna_damage_all(struct sna_damage *damage,