diff mbox

[v2,6/6] drm/i915: Improve hash function for the command parser

Message ID 1448016961-25331-7-git-send-email-chris@chris-wilson.co.uk
State New, archived
Headers show

Commit Message

Chris Wilson Nov. 20, 2015, 10:56 a.m. UTC
The existing code's hashfunction is very suboptimal (most 3D commands
use the same bucket degrading the hash to a long list). The code even
acknowledge that the issue was known and the fix simple:

/*
 * If we attempt to generate a perfect hash, we should be able to look at bits
 * 31:29 of a command from a batch buffer and use the full mask for that
 * client. The existing INSTR_CLIENT_MASK/SHIFT defines can be used for this.
 */

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
---
 drivers/gpu/drm/i915/i915_cmd_parser.c | 45 +++++++++++++++++++++-------------
 1 file changed, 28 insertions(+), 17 deletions(-)

Comments

Ville Syrjala Nov. 20, 2015, 3:13 p.m. UTC | #1
On Fri, Nov 20, 2015 at 10:56:01AM +0000, Chris Wilson wrote:
> The existing code's hashfunction is very suboptimal (most 3D commands
> use the same bucket degrading the hash to a long list). The code even
> acknowledge that the issue was known and the fix simple:

Do we have any statistics/some easy way to gather them to see how
the hash is performing?

> 
> /*
>  * If we attempt to generate a perfect hash, we should be able to look at bits
>  * 31:29 of a command from a batch buffer and use the full mask for that
>  * client. The existing INSTR_CLIENT_MASK/SHIFT defines can be used for this.
>  */
> 
> Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> ---
>  drivers/gpu/drm/i915/i915_cmd_parser.c | 45 +++++++++++++++++++++-------------
>  1 file changed, 28 insertions(+), 17 deletions(-)
> 
> diff --git a/drivers/gpu/drm/i915/i915_cmd_parser.c b/drivers/gpu/drm/i915/i915_cmd_parser.c
> index ea9df2bb87de..7a0250c1d201 100644
> --- a/drivers/gpu/drm/i915/i915_cmd_parser.c
> +++ b/drivers/gpu/drm/i915/i915_cmd_parser.c
> @@ -86,24 +86,24 @@
>   * general bitmasking mechanism.
>   */
>  
> -#define STD_MI_OPCODE_MASK  0xFF800000
> -#define STD_3D_OPCODE_MASK  0xFFFF0000
> -#define STD_2D_OPCODE_MASK  0xFFC00000
> -#define STD_MFX_OPCODE_MASK 0xFFFF0000
> +#define STD_MI_OPCODE_SHIFT  (32 - 9)
> +#define STD_3D_OPCODE_SHIFT  (32 - 16)
> +#define STD_2D_OPCODE_SHIFT  (32 - 10)
> +#define STD_MFX_OPCODE_SHIFT (32 - 16)
>  
>  #define CMD(op, opm, f, lm, fl, ...)				\
>  	{							\
>  		.flags = (fl) | ((f) ? CMD_DESC_FIXED : 0),	\
> -		.cmd = { (op), (opm) },				\
> +		.cmd = { (op), ~0 << (opm) }, 			\
>  		.length = { (lm) },				\
>  		__VA_ARGS__					\
>  	}
>  
>  /* Convenience macros to compress the tables */
> -#define SMI STD_MI_OPCODE_MASK
> -#define S3D STD_3D_OPCODE_MASK
> -#define S2D STD_2D_OPCODE_MASK
> -#define SMFX STD_MFX_OPCODE_MASK
> +#define SMI STD_MI_OPCODE_SHIFT
> +#define S3D STD_3D_OPCODE_SHIFT
> +#define S2D STD_2D_OPCODE_SHIFT
> +#define SMFX STD_MFX_OPCODE_SHIFT
>  #define F true
>  #define S CMD_DESC_SKIP
>  #define R CMD_DESC_REJECT
> @@ -627,12 +627,24 @@ static bool validate_regs_sorted(struct intel_engine_cs *ring)
>   * non-opcode bits being set. But if we don't include those bits, some 3D
>   * commands may hash to the same bucket due to not including opcode bits that
>   * make the command unique. For now, we will risk hashing to the same bucket.
> - *
> - * If we attempt to generate a perfect hash, we should be able to look at bits
> - * 31:29 of a command from a batch buffer and use the full mask for that
> - * client. The existing INSTR_CLIENT_MASK/SHIFT defines can be used for this.
>   */
> -#define CMD_HASH_MASK STD_MI_OPCODE_MASK
> +static inline u32 cmd_header_key(u32 x)
> +{
> +	u32 shift;
> +	switch (x >> INSTR_CLIENT_SHIFT) {
> +	default:
> +	case INSTR_MI_CLIENT:
> +		shift = STD_MI_OPCODE_SHIFT;
> +		break;
> +	case INSTR_RC_CLIENT:
> +		shift = STD_3D_OPCODE_SHIFT;
> +		break;
> +	case INSTR_BC_CLIENT:
> +		shift = STD_2D_OPCODE_SHIFT;
> +		break;
> +	}
> +	return x >> shift;
> +}
>  
>  static int init_hash_table(struct intel_engine_cs *ring,
>  			   const struct drm_i915_cmd_table *cmd_tables,
> @@ -648,7 +660,7 @@ static int init_hash_table(struct intel_engine_cs *ring,
>  		for (j = 0; j < table->count; j++) {
>  			struct drm_i915_cmd_descriptor *desc = &table->table[j];
>  			hash_add(ring->cmd_hash, &desc->node[ring->id],
> -				 desc->cmd.value & CMD_HASH_MASK);
> +				 cmd_header_key(desc->cmd.value));
>  		}
>  	}
>  
> @@ -776,10 +788,9 @@ find_cmd_in_table(struct intel_engine_cs *ring,
>  	const struct drm_i915_cmd_descriptor *desc;
>  
>  	hash_for_each_possible(ring->cmd_hash, desc, node[ring->id],
> -			       cmd_header & CMD_HASH_MASK) {
> +			       cmd_header_key(cmd_header))
>  		if (((cmd_header ^ desc->cmd.value) & desc->cmd.mask) == 0)
>  			return desc;
> -	}
>  
>  	return NULL;
>  }
> -- 
> 2.6.2
> 
> _______________________________________________
> Intel-gfx mailing list
> Intel-gfx@lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/intel-gfx
diff mbox

Patch

diff --git a/drivers/gpu/drm/i915/i915_cmd_parser.c b/drivers/gpu/drm/i915/i915_cmd_parser.c
index ea9df2bb87de..7a0250c1d201 100644
--- a/drivers/gpu/drm/i915/i915_cmd_parser.c
+++ b/drivers/gpu/drm/i915/i915_cmd_parser.c
@@ -86,24 +86,24 @@ 
  * general bitmasking mechanism.
  */
 
-#define STD_MI_OPCODE_MASK  0xFF800000
-#define STD_3D_OPCODE_MASK  0xFFFF0000
-#define STD_2D_OPCODE_MASK  0xFFC00000
-#define STD_MFX_OPCODE_MASK 0xFFFF0000
+#define STD_MI_OPCODE_SHIFT  (32 - 9)
+#define STD_3D_OPCODE_SHIFT  (32 - 16)
+#define STD_2D_OPCODE_SHIFT  (32 - 10)
+#define STD_MFX_OPCODE_SHIFT (32 - 16)
 
 #define CMD(op, opm, f, lm, fl, ...)				\
 	{							\
 		.flags = (fl) | ((f) ? CMD_DESC_FIXED : 0),	\
-		.cmd = { (op), (opm) },				\
+		.cmd = { (op), ~0 << (opm) }, 			\
 		.length = { (lm) },				\
 		__VA_ARGS__					\
 	}
 
 /* Convenience macros to compress the tables */
-#define SMI STD_MI_OPCODE_MASK
-#define S3D STD_3D_OPCODE_MASK
-#define S2D STD_2D_OPCODE_MASK
-#define SMFX STD_MFX_OPCODE_MASK
+#define SMI STD_MI_OPCODE_SHIFT
+#define S3D STD_3D_OPCODE_SHIFT
+#define S2D STD_2D_OPCODE_SHIFT
+#define SMFX STD_MFX_OPCODE_SHIFT
 #define F true
 #define S CMD_DESC_SKIP
 #define R CMD_DESC_REJECT
@@ -627,12 +627,24 @@  static bool validate_regs_sorted(struct intel_engine_cs *ring)
  * non-opcode bits being set. But if we don't include those bits, some 3D
  * commands may hash to the same bucket due to not including opcode bits that
  * make the command unique. For now, we will risk hashing to the same bucket.
- *
- * If we attempt to generate a perfect hash, we should be able to look at bits
- * 31:29 of a command from a batch buffer and use the full mask for that
- * client. The existing INSTR_CLIENT_MASK/SHIFT defines can be used for this.
  */
-#define CMD_HASH_MASK STD_MI_OPCODE_MASK
+static inline u32 cmd_header_key(u32 x)
+{
+	u32 shift;
+	switch (x >> INSTR_CLIENT_SHIFT) {
+	default:
+	case INSTR_MI_CLIENT:
+		shift = STD_MI_OPCODE_SHIFT;
+		break;
+	case INSTR_RC_CLIENT:
+		shift = STD_3D_OPCODE_SHIFT;
+		break;
+	case INSTR_BC_CLIENT:
+		shift = STD_2D_OPCODE_SHIFT;
+		break;
+	}
+	return x >> shift;
+}
 
 static int init_hash_table(struct intel_engine_cs *ring,
 			   const struct drm_i915_cmd_table *cmd_tables,
@@ -648,7 +660,7 @@  static int init_hash_table(struct intel_engine_cs *ring,
 		for (j = 0; j < table->count; j++) {
 			struct drm_i915_cmd_descriptor *desc = &table->table[j];
 			hash_add(ring->cmd_hash, &desc->node[ring->id],
-				 desc->cmd.value & CMD_HASH_MASK);
+				 cmd_header_key(desc->cmd.value));
 		}
 	}
 
@@ -776,10 +788,9 @@  find_cmd_in_table(struct intel_engine_cs *ring,
 	const struct drm_i915_cmd_descriptor *desc;
 
 	hash_for_each_possible(ring->cmd_hash, desc, node[ring->id],
-			       cmd_header & CMD_HASH_MASK) {
+			       cmd_header_key(cmd_header))
 		if (((cmd_header ^ desc->cmd.value) & desc->cmd.mask) == 0)
 			return desc;
-	}
 
 	return NULL;
 }