Use all texture heaps in a fair way when textures need to be kicked in

order to make room for new textures. In particular this fixes texture
trashing on the first heap when the second heap is occupied by
currently unused textures (observed with Torcs and the Savage driver).

Heaps are weighted by their sizes by default but drivers can override
these and apply their own weights based on relative texture upload
speeds to the respective heaps.

1 files changed, 81 insertions, 24 deletions

diff --git a/src/mesa/drivers/dri/common/texmem.c b/src/mesa/drivers/dri/common/texmem.c
index bc12021411e..8fdad874124 100644
--- a/src/mesa/drivers/dri/common/texmem.c
+++ b/src/mesa/drivers/dri/common/texmem.c
@@ -477,6 +477,8 @@ void driAgeTextures( driTexHeap * heap )
 
 
 
+#define INDEX_ARRAY_SIZE 6 /* I'm not aware of driver with more than 2 heaps */
+
 /**
  * Allocate memory from a texture heap to hold a texture object.  This
  * routine will attempt to allocate memory for the texture from the heaps
@@ -528,39 +530,91 @@ driAllocateTexture( driTexHeap * const * heap_array, unsigned nr_heaps,
     */
 
    if ( t->memBlock == NULL ) {
-      for ( id = 0 ; (t->memBlock == NULL) && (id < nr_heaps) ; id++ ) {
+      unsigned index[INDEX_ARRAY_SIZE];
+      unsigned nrGoodHeaps = 0;
+
+      /* Trying to avoid dynamic memory allocation. If you have more
+       * heaps, increase INDEX_ARRAY_SIZE. I'm not aware of any
+       * drivers with more than 2 tex heaps. */
+      assert( nr_neaps < INDEX_ARRAY_SIZE );
+
+      /* Sort large enough heaps by duty. Insertion sort should be
+       * fast enough for such a short array. */
+      for ( id = 0 ; id < nr_heaps ; id++ ) {
 	 heap = heap_array[ id ];
 
-	 if ( heap == NULL )
-	    continue;
+	 if ( heap != NULL && t->totalSize <= heap->size ) {
+	    unsigned j;
 
-	 if ( t->totalSize <= heap->size ) { 
+	    for ( j = 0 ; j < nrGoodHeaps; j++ ) {
+	       if ( heap->duty > heap_array[ index[ j ] ]->duty )
+		  break;
+	    }
 
-	    for ( cursor = heap->texture_objects.prev, temp = cursor->prev;
-		  cursor != &heap->texture_objects ; 
-		  cursor = temp, temp = cursor->prev ) {
-	       
-	       /* The the LRU element.  If the texture is bound to one of
-		* the texture units, then we cannot kick it out.
-		*/
-	       if ( cursor->bound /* || cursor->reserved */ ) {
-		  continue;
-	       }
+	    if ( j < nrGoodHeaps ) {
+	       memmove( &index[ j+1 ], &index[ j ],
+			sizeof(index[ 0 ]) * (nrGoodHeaps - j) );
+	    }
+
+	    index[ j ] = id;
 
-	       /* If this is a placeholder, there's no need to keep it */
-	       if (cursor->tObj)
-		   driSwapOutTextureObject( cursor );
-	       else
-		   driDestroyTextureObject( cursor );
+	    nrGoodHeaps++;
+	 }
+      }
 
-	       t->memBlock = mmAllocMem( heap->memory_heap, t->totalSize, 
-					 heap->alignmentShift, 0 );
+      for ( id = 0 ; (t->memBlock == NULL) && (id < nrGoodHeaps) ; id++ ) {
+	 heap = heap_array[ index[ id ] ];
 
-	       if (t->memBlock)
-		  break;
+	 for ( cursor = heap->texture_objects.prev, temp = cursor->prev;
+	       cursor != &heap->texture_objects ; 
+	       cursor = temp, temp = cursor->prev ) {
+	       
+	    /* The the LRU element.  If the texture is bound to one of
+	     * the texture units, then we cannot kick it out.
+	     */
+	    if ( cursor->bound /* || cursor->reserved */ ) {
+	       continue;
 	    }
-	 }     /* if ( t->totalSize <= heap->size ) ... */
+
+	    if ( cursor->memBlock )
+	       heap->duty -= cursor->memBlock->size;
+
+	    /* If this is a placeholder, there's no need to keep it */
+	    if (cursor->tObj)
+	       driSwapOutTextureObject( cursor );
+	    else
+	       driDestroyTextureObject( cursor );
+
+	    t->memBlock = mmAllocMem( heap->memory_heap, t->totalSize, 
+				      heap->alignmentShift, 0 );
+
+	    if (t->memBlock)
+	       break;
+	 }
       }
+
+      /* Rebalance duties. If a heap kicked more data than its duty,
+       * then all other heaps get that amount multiplied with their
+       * relative weight added to their duty. The negative duty is
+       * reset to 0. In the end all heaps have a duty >= 0.
+       *
+       * CAUTION: we must not change the heap pointer here, because it
+       * is used below to update the texture object.
+       */
+      for ( id = 0 ; id < nr_heaps ; id++ )
+	 if ( heap_array[ id ] != NULL && heap_array[ id ]->duty < 0) {
+	    int duty = -heap_array[ id ]->duty;
+	    double weight = heap_array[ id ]->weight;
+	    unsigned j;
+
+	    for ( j = 0 ; j < nr_heaps ; j++ )
+	       if ( j != id && heap_array[ j ] != NULL ) {
+		  heap_array[ j ]->duty += (double) duty *
+		     heap_array[ j ]->weight / weight;
+	       }
+
+	    heap_array[ id ]->duty = 0;
+	 }
    }
 
 
@@ -679,6 +733,9 @@ driCreateTextureHeap( unsigned heap_id, void * context, unsigned size,
 
 	 make_empty_list( & heap->texture_objects );
 	 driSetTextureSwapCounterLocation( heap, NULL );
+
+	 heap->weight = heap->size;
+	 heap->duty = 0;
       }
       else {
 	 FREE( heap );