2 files changed, 98 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 );
diff --git a/src/mesa/drivers/dri/common/texmem.h b/src/mesa/drivers/dri/common/texmem.h
index 266afd8bb66..705cd4d3445 100644
--- a/src/mesa/drivers/dri/common/texmem.h
+++ b/src/mesa/drivers/dri/common/texmem.h
@@ -216,6 +216,23 @@ struct dri_tex_heap {
 	 * framebuffer.  
 	 */
         unsigned timestamp;
+
+	/** \brief Kick/upload weight
+	 *
+	 * When not enough free space is available this weight
+	 * influences the choice of the heap from which textures are
+	 * kicked. By default the weight is equal to the heap size.
+	 */
+	double weight;
+
+	/** \brief Kick/upload duty
+	 *
+	 * The heap with the highest duty will be chosen for kicking
+	 * textures if not enough free space is available. The duty is
+	 * reduced by the amount of data kicked. Rebalancing of
+	 * negative duties takes the weights into account.
+	 */
+	int duty;
 };