EXA: Improve the algorithm used for tracking offscreen pixmap use.

Replace the current score keeping algorithm with a rolling counter that's
incremented in ExaOffscreenMarkUsed, with the previous value being stored
in the area.  exaOffscreenAlloc uses the difference between the counter
value and the value in the area when deciding which area to evict.
It now also takes the size of the areas into account, and favors evicting
smaller areas.

The credit for these ideas goes to Michel Dänzer.
(cherry picked from commit 93d876891dbba41b920a9a29a5de77f647f43928)

3 files changed, 16 insertions, 23 deletions

diff --git a/exa/exa.h b/exa/exa.h
index 0774a700a..97ae6c0a5 100644
--- a/exa/exa.h
+++ b/exa/exa.h
@@ -56,7 +56,7 @@ struct _ExaOffscreenArea {
     int                 base_offset;	/* allocation base */
     int                 offset;         /* aligned offset */
     int                 size;           /* total allocation size */
-    int                 score;
+    unsigned            last_use;
     pointer             privData;
 
     ExaOffscreenSaveProc save;
diff --git a/exa/exa_offscreen.c b/exa/exa_offscreen.c
index c666b001b..2701e84cf 100644
--- a/exa/exa_offscreen.c
+++ b/exa/exa_offscreen.c
@@ -71,6 +71,8 @@ ExaOffscreenKickOut (ScreenPtr pScreen, ExaOffscreenArea *area)
     return exaOffscreenFree (pScreen, area);
 }
 
+#define AREA_SCORE(area) (area->size / (double)(pExaScr->offScreenCounter - area->last_use))
+
 /**
  * exaOffscreenAlloc allocates offscreen memory
  *
@@ -98,7 +100,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
 {
     ExaOffscreenArea *area, *begin, *best;
     ExaScreenPriv (pScreen);
-    int tmp, real_size = 0, best_score;
+    int tmp, real_size = 0;
 #if DEBUG_OFFSCREEN
     static int number = 0;
     ErrorF("================= ============ allocating a new pixmap %d\n", ++number);
@@ -143,6 +145,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
 
     if (!area)
     {
+	double best_score;
 	/*
 	 * Kick out existing users to make space.
 	 *
@@ -151,11 +154,12 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
 
 	/* prev points at the first object to boot */
 	best = NULL;
-	best_score = INT_MAX;
+	best_score = UINT_MAX;
 	for (begin = pExaScr->info->offScreenAreas; begin != NULL;
 	     begin = begin->next)
 	{
-	    int avail, score;
+	    int avail;
+	    double score;
 	    ExaOffscreenArea *scan;
 
 	    if (begin->state == ExaOffscreenLocked)
@@ -177,8 +181,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
 		    begin = scan;
 		    break;
 		}
-		/* Score should only be non-zero for ExaOffscreenRemovable */
-		score += scan->score;
+		score += AREA_SCORE(scan);
 		avail += scan->size;
 		if (avail >= real_size)
 		    break;
@@ -230,7 +233,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
 	new_area->size = area->size - real_size;
 	new_area->state = ExaOffscreenAvail;
 	new_area->save = NULL;
-	new_area->score = 0;
+	new_area->last_use = 0;
 	new_area->next = area->next;
 	area->next = new_area;
 	area->size = real_size;
@@ -244,7 +247,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
 	area->state = ExaOffscreenRemovable;
     area->privData = privData;
     area->save = save;
-    area->score = 0;
+    area->last_use = pExaScr->offScreenCounter++;
     area->offset = (area->base_offset + align - 1);
     area->offset -= area->offset % align;
 
@@ -395,7 +398,7 @@ exaOffscreenFree (ScreenPtr pScreen, ExaOffscreenArea *area)
 
     area->state = ExaOffscreenAvail;
     area->save = NULL;
-    area->score = 0;
+    area->last_use = 0;
     /*
      * Find previous area
      */
@@ -427,23 +430,11 @@ ExaOffscreenMarkUsed (PixmapPtr pPixmap)
 {
     ExaPixmapPriv (pPixmap);
     ExaScreenPriv (pPixmap->drawable.pScreen);
-    static int iter = 0;
 
     if (!pExaPixmap || !pExaPixmap->area)
 	return;
 
-    /* The numbers here are arbitrary.  We may want to tune these. */
-    pExaPixmap->area->score += 100;
-    if (++iter == 10) {
-	ExaOffscreenArea *area;
-	for (area = pExaScr->info->offScreenAreas; area != NULL;
-	     area = area->next)
-	{
-	    if (area->state == ExaOffscreenRemovable)
-		area->score = (area->score * 7) / 8;
-	}
-	iter = 0;
-    }
+    pExaPixmap->area->last_use = pExaScr->offScreenCounter++;
 }
 
 /**
@@ -472,10 +463,11 @@ exaOffscreenInit (ScreenPtr pScreen)
     area->size = pExaScr->info->memorySize - area->base_offset;
     area->save = NULL;
     area->next = NULL;
-    area->score = 0;
+    area->last_use = 0;
 
     /* Add it to the free areas */
     pExaScr->info->offScreenAreas = area;
+    pExaScr->offScreenCounter = 1;
 
     ExaOffscreenValidate (pScreen);
 
diff --git a/exa/exa_priv.h b/exa/exa_priv.h
index 89f47184f..e41f46aba 100644
--- a/exa/exa_priv.h
+++ b/exa/exa_priv.h
@@ -120,6 +120,7 @@ typedef struct {
     Bool			 checkDirtyCorrectness;
     unsigned			 disableFbCount;
     Bool			 optimize_migration;
+    unsigned			 offScreenCounter;
 } ExaScreenPrivRec, *ExaScreenPrivPtr;
 
 /*