[RFC][PATCH 1/4] IRQ: IRQ groups for multiqueue devices

[RFC][PATCH 1/4] IRQ: IRQ groups for multiqueue devices

[Ben Hutchings]

When initiating I/O on multiqueue devices, we usually want to select a
queue for which the response will be handled on the same or a nearby
CPU.  IRQ groups hold a mapping of CPU to IRQ which will be updated
based on the inverse of IRQ CPU-affinities plus CPU topology
information.
---
 include/linux/irq.h |   52 ++++++++++++++++++
 kernel/irq/manage.c |  149 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 201 insertions(+), 0 deletions(-)

diff --git a/include/linux/irq.h b/include/linux/irq.h
index c03243a..bbddd5f 100644
--- a/include/linux/irq.h
+++ b/include/linux/irq.h
@@ -196,6 +196,8 @@ struct irq_desc {
 #ifdef CONFIG_SMP
 	cpumask_var_t		affinity;
 	const struct cpumask	*affinity_hint;
+	struct irq_group	*group;
+	u16			group_index;
 	unsigned int		node;
 #ifdef CONFIG_GENERIC_PENDING_IRQ
 	cpumask_var_t		pending_mask;
@@ -498,6 +500,33 @@ static inline void free_desc_masks(struct irq_desc *old_desc,
 #endif
 }
 
+/**
+ * struct irq_group - IRQ group for multiqueue devices
+ * @closest: For each CPU, the index and distance to the closest IRQ,
+ *	based on affinity masks
+ * @size: Size of the group
+ * @used: Number of IRQs currently included in the group
+ * @irq: Descriptors for IRQs in the group
+ */
+struct irq_group {
+	struct {
+		u16	index;
+		u16	dist;
+	} closest[NR_CPUS];
+	unsigned int	size, used;
+	struct irq_desc *irq[0];
+};
+#define IRQ_CPU_DIST_INF 0xffff
+
+extern struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags);
+extern void free_irq_group(struct irq_group *group);
+extern void irq_group_add(struct irq_group *group, unsigned int irq);
+
+static inline u16 irq_group_get_index(struct irq_group *group, int cpu)
+{
+	return group->closest[cpu].index;
+}
+
 #else /* !CONFIG_SMP */
 
 static inline bool alloc_desc_masks(struct irq_desc *desc, int node,
@@ -519,6 +548,29 @@ static inline void free_desc_masks(struct irq_desc *old_desc,
 				   struct irq_desc *new_desc)
 {
 }
+
+struct irq_group {
+};
+
+static inline struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags)
+{
+	static struct irq_group dummy;
+	return &dummy;
+}
+
+static inline void free_irq_group(struct irq_group *group)
+{
+}
+
+static inline void irq_group_add(struct irq_group *group, unsigned int irq)
+{
+}
+
+static inline u16 irq_group_get_index(struct irq_group *group, int cpu)
+{
+	return 0;
+}
+
 #endif	/* CONFIG_SMP */
 
 #endif /* _LINUX_IRQ_H */
diff --git a/kernel/irq/manage.c b/kernel/irq/manage.c
index c3003e9..3f2b1a9 100644
--- a/kernel/irq/manage.c
+++ b/kernel/irq/manage.c
@@ -100,6 +100,154 @@ void irq_set_thread_affinity(struct irq_desc *desc)
 	}
 }
 
+static void irq_group_update_neigh(struct irq_group *group,
+				   const struct cpumask *mask,
+				   u16 index, u16 dist)
+{
+	int cpu;
+
+	for_each_cpu(cpu, mask) {
+		if (dist < group->closest[cpu].dist) {
+			group->closest[cpu].index = index;
+			group->closest[cpu].dist = dist;
+		}
+	}
+}
+
+static bool irq_group_copy_neigh(struct irq_group *group, int cpu,
+				 const struct cpumask *mask, u16 dist)
+{
+	int neigh;
+
+	for_each_cpu(neigh, mask) {
+		if (group->closest[neigh].dist <= dist) {
+			group->closest[cpu].index = group->closest[neigh].index;
+			group->closest[cpu].dist = dist;
+			return true;
+		}
+	}
+	return false;
+}
+
+/* Update the per-CPU closest IRQs following a change of affinity */
+static void
+irq_update_group(struct irq_desc *desc, const struct cpumask *affinity)
+{
+	struct irq_group *group = desc->group;
+	unsigned index = desc->group_index;
+	int cpu;
+
+	if (!group)
+		return;
+
+	/* Invalidate old distances to this IRQ */
+	for_each_online_cpu(cpu)
+		if (group->closest[cpu].index == index)
+			group->closest[cpu].dist = IRQ_CPU_DIST_INF;
+
+	/*
+	 * Set this as the closest IRQ for all CPUs in the affinity mask,
+	 * plus the following CPUs if they don't have a closer IRQ:
+	 * - all other threads in the same core (distance 1);
+	 * - all other cores in the same package (distance 2);
+	 * - all other packages in the same NUMA node (distance 3).
+	 */
+	for_each_cpu(cpu, affinity) {
+		group->closest[cpu].index = index;
+		group->closest[cpu].dist = 0;
+		irq_group_update_neigh(group, topology_thread_cpumask(cpu),
+				       index, 1);
+		irq_group_update_neigh(group, topology_core_cpumask(cpu),
+				       index, 2);
+		irq_group_update_neigh(group, cpumask_of_node(cpu_to_node(cpu)),
+				       index, 3);
+	}
+
+	/* Find new closest IRQ for any CPUs left with invalid distances */
+	for_each_online_cpu(cpu) {
+		if (!(group->closest[cpu].index == index &&
+		      group->closest[cpu].dist == IRQ_CPU_DIST_INF))
+			continue;
+		if (irq_group_copy_neigh(group, cpu,
+					 topology_thread_cpumask(cpu), 1))
+			continue;
+		if (irq_group_copy_neigh(group, cpu,
+					 topology_core_cpumask(cpu), 2))
+			continue;
+		if (irq_group_copy_neigh(group, cpu,
+					 cpumask_of_node(cpu_to_node(cpu)), 3))
+			continue;
+		/* We could continue into NUMA node distances, but for now
+		 * we give up. */
+	}
+}
+
+/**
+ *	alloc_irq_group - allocate IRQ group
+ *	@size:		Size of the group
+ *	@flags:		Allocation flags e.g. %GFP_KERNEL
+ */
+struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags)
+{
+	struct irq_group *group =
+		kzalloc(sizeof(*group) + size * sizeof(group->irq[0]), flags);
+	int cpu;
+
+	if (!group)
+		return NULL;
+
+	/* Initially assign CPUs to IRQs on a rota */
+	for (cpu = 0; cpu < NR_CPUS; cpu++) {
+		group->closest[cpu].index = cpu % size;
+		group->closest[cpu].dist = IRQ_CPU_DIST_INF;
+	}
+
+	group->size = size;
+	return group;
+}
+EXPORT_SYMBOL(alloc_irq_group);
+
+/**
+ *	free_irq_group - free IRQ group
+ *	@group:		IRQ group allocated with alloc_irq_group(), or %NULL
+ */
+void free_irq_group(struct irq_group *group)
+{
+	struct irq_desc *desc;
+	unsigned int i;
+
+	if (!group)
+		return;
+
+	/* Remove all descriptors from the group */
+	for (i = 0; i < group->used; i++) {
+		desc = group->irq[i];
+		BUG_ON(desc->group != group || desc->group_index != i);
+		desc->group = NULL;
+	}
+
+	kfree(group);
+}
+EXPORT_SYMBOL(free_irq_group);
+
+/**
+ *	irq_group_add - add IRQ to a group
+ *	@group:		IRQ group allocated with alloc_irq_group()
+ *	@irq:		Interrupt to add to group
+ */
+void irq_group_add(struct irq_group *group, unsigned int irq)
+{
+	struct irq_desc *desc = irq_to_desc(irq);
+
+	BUG_ON(desc->group);
+	BUG_ON(group->used >= group->size);
+
+	desc->group = group;
+	desc->group_index = group->used;
+	group->irq[group->used++] = desc;
+}
+EXPORT_SYMBOL(irq_group_add);
+
 /**
  *	irq_set_affinity - Set the irq affinity of a given irq
  *	@irq:		Interrupt to set affinity
@@ -134,6 +282,7 @@ int irq_set_affinity(unsigned int irq, const struct cpumask *cpumask)
 	}
 #endif
 	desc->status |= IRQ_AFFINITY_SET;
+	irq_update_group(desc, cpumask);
 	raw_spin_unlock_irqrestore(&desc->lock, flags);
 	return 0;
 }
-- 
1.7.2.1



-- 
Ben Hutchings, Senior Software Engineer, Solarflare Communications
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [RFC][PATCH 1/4] IRQ: IRQ groups for multiqueue devices

[Thomas Gleixner]

Ben,

On Mon, 20 Sep 2010, Ben Hutchings wrote:

it would have been nice if I'd been cc'ed on that, but of course it's
my fault that there is no entry in MAINTAINERS. No, it's not.

> When initiating I/O on multiqueue devices, we usually want to select a

"we usually" is pretty useless for people not familiar with the
problem at hand. A [PATCH 0/4] intro would have been helpful along
with the users (aka [PATCH 2-4/4]) of the new facility.

Don't take it personally and I'm sure that you're solving a real world
problem, but I'm starting to get grumpy that especially networking
folks (aside of various driver developers) believe that adding random
stuff to kernel/irq is their private pleasure. Is it that hard to talk
to me upfront ?

> queue for which the response will be handled on the same or a nearby
> CPU.  IRQ groups hold a mapping of CPU to IRQ which will be updated
> based on the inverse of IRQ CPU-affinities plus CPU topology
> information.

Can you please explain, why you need that reverse mapping including
the below code ? What problem does this solve which can not be deduced
by the exisiting information/infrastructure ? And why is that reverse
mapping tied to interrupts and not something which we want to see in
some generic available (library) code ?

More comments inline.

> ---
>  include/linux/irq.h |   52 ++++++++++++++++++
>  kernel/irq/manage.c |  149 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 201 insertions(+), 0 deletions(-)
> 
> diff --git a/include/linux/irq.h b/include/linux/irq.h
> index c03243a..bbddd5f 100644
> --- a/include/linux/irq.h
> +++ b/include/linux/irq.h
> @@ -196,6 +196,8 @@ struct irq_desc {
>  #ifdef CONFIG_SMP
>  	cpumask_var_t		affinity;
>  	const struct cpumask	*affinity_hint;

  How about updating the kernel doc above the struct ?

> +	struct irq_group	*group;

  Grr, how does this compile ? That needs at least a forward
  declaration of struct irq_group. RFC is _NOT_ an excuse

> +	u16			group_index;

  What's group_index doing and what's the point of an u16 here ?

>  	unsigned int		node;
>  #ifdef CONFIG_GENERIC_PENDING_IRQ
>  	cpumask_var_t		pending_mask;
> @@ -498,6 +500,33 @@ static inline void free_desc_masks(struct irq_desc *old_desc,
>  #endif
>  }
>  
> +/**
> + * struct irq_group - IRQ group for multiqueue devices
> + * @closest: For each CPU, the index and distance to the closest IRQ,
> + *	based on affinity masks

  index of what ?

  Btw, please follow the style of the other kernel doc comments in this
  file where the explanation is aligned for readability sake

> + * @size: Size of the group
> + * @used: Number of IRQs currently included in the group
> + * @irq: Descriptors for IRQs in the group

  That's an array of pointers to irq descriptors, right ?

  Insert some sensible decription what irq groups are and for which
  problem space they are useful if at all.

> + */
> +struct irq_group {
> +	struct {
> +		u16	index;
> +		u16	dist;
> +	} closest[NR_CPUS];
> +	unsigned int	size, used;

  Separate lines please

> +	struct irq_desc *irq[0];
> +};

  Please separate this with a newline and add some useful comment
  about the meaning and purpose of this not selfexplaining constant.

> +#define IRQ_CPU_DIST_INF 0xffff

> +static inline u16 irq_group_get_index(struct irq_group *group, int cpu)
> +{
> +	return group->closest[cpu].index;
> +}
> +

  So you have an accessor function for closest[cpu].index. Are the
  other members meant to be accessible directly by random driver ?

>  #else /* !CONFIG_SMP */
>  
>  static inline bool alloc_desc_masks(struct irq_desc *desc, int node,
> @@ -519,6 +548,29 @@ static inline void free_desc_masks(struct irq_desc *old_desc,
>  				   struct irq_desc *new_desc)
>  {
>  }
> +
> +struct irq_group {
> +};
> +
> +static inline struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags)
> +{
> +	static struct irq_group dummy;

  That will create one static instance per callsite. Is that on
  purpose? If yes, it needs a damned good comment.

> +	return &dummy;

>  #endif	/* CONFIG_SMP */
>  
>  #endif /* _LINUX_IRQ_H */
> diff --git a/kernel/irq/manage.c b/kernel/irq/manage.c
> index c3003e9..3f2b1a9 100644
> --- a/kernel/irq/manage.c
> +++ b/kernel/irq/manage.c
> @@ -100,6 +100,154 @@ void irq_set_thread_affinity(struct irq_desc *desc)
>  	}
>  }
>  
> +static void irq_group_update_neigh(struct irq_group *group,
> +				   const struct cpumask *mask,
> +				   u16 index, u16 dist)
> +{
> +	int cpu;
> +
> +	for_each_cpu(cpu, mask) {
> +		if (dist < group->closest[cpu].dist) {
> +			group->closest[cpu].index = index;
> +			group->closest[cpu].dist = dist;
> +		}
> +	}
> +}

  I have not the faintest idea how group, index and dist are related
  to each other. And I have no intention to decode the information
  about that piecewise by reverse engineering that obfuscated code.

> +static bool irq_group_copy_neigh(struct irq_group *group, int cpu,
> +				 const struct cpumask *mask, u16 dist)
> +{
> +	int neigh;
> +
> +	for_each_cpu(neigh, mask) {
> +		if (group->closest[neigh].dist <= dist) {
> +			group->closest[cpu].index = group->closest[neigh].index;
> +			group->closest[cpu].dist = dist;
> +			return true;
> +		}
> +	}
> +	return false;

  What's the reason for copying or not ?

> +}
> +
> +/* Update the per-CPU closest IRQs following a change of affinity */
> +static void
> +irq_update_group(struct irq_desc *desc, const struct cpumask *affinity)
> +{
> +	struct irq_group *group = desc->group;
> +	unsigned index = desc->group_index;
> +	int cpu;
> +
> +	if (!group)
> +		return;
> +
> +	/* Invalidate old distances to this IRQ */
> +	for_each_online_cpu(cpu)
> +		if (group->closest[cpu].index == index)
> +			group->closest[cpu].dist = IRQ_CPU_DIST_INF;
> +
> +	/*
> +	 * Set this as the closest IRQ for all CPUs in the affinity mask,
> +	 * plus the following CPUs if they don't have a closer IRQ:
> +	 * - all other threads in the same core (distance 1);
> +	 * - all other cores in the same package (distance 2);
> +	 * - all other packages in the same NUMA node (distance 3).
> +	 */
> +	for_each_cpu(cpu, affinity) {
> +		group->closest[cpu].index = index;
> +		group->closest[cpu].dist = 0;
> +		irq_group_update_neigh(group, topology_thread_cpumask(cpu),
> +				       index, 1);
> +		irq_group_update_neigh(group, topology_core_cpumask(cpu),
> +				       index, 2);
> +		irq_group_update_neigh(group, cpumask_of_node(cpu_to_node(cpu)),
> +				       index, 3);
> +	}
> +
> +	/* Find new closest IRQ for any CPUs left with invalid distances */
> +	for_each_online_cpu(cpu) {
> +		if (!(group->closest[cpu].index == index &&
> +		      group->closest[cpu].dist == IRQ_CPU_DIST_INF))
> +			continue;
> +		if (irq_group_copy_neigh(group, cpu,
> +					 topology_thread_cpumask(cpu), 1))
> +			continue;
> +		if (irq_group_copy_neigh(group, cpu,
> +					 topology_core_cpumask(cpu), 2))
> +			continue;
> +		if (irq_group_copy_neigh(group, cpu,
> +					 cpumask_of_node(cpu_to_node(cpu)), 3))
> +			continue;
> +		/* We could continue into NUMA node distances, but for now
> +		 * we give up. */

  What are the consequences of giving up ? Does not happen ? Should
  not happen ? Will break ? Don't care ? ....

> +	}

  This is called from irq_set_affinity() with desc->lock held and
  interrupts disabled. You're not serious about that, are you ?

  Damned, there are two iterations over each online cpu and another
  one over the affinity mask. Did you ever extrapolate how long that
  runs on a really large machine ?

  If CPU affinity of an IRQ changes, then it does not matter if one or
  two interrupts end up in the wrong space. Those changes are not
  happening every other interrupt.

> +}
> +
> +/**
> + *	alloc_irq_group - allocate IRQ group
> + *	@size:		Size of the group

  size of what ? I guess number of interrupts, right ?

> + *	@flags:		Allocation flags e.g. %GFP_KERNEL
> + */
> +struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags)
> +{
> +	struct irq_group *group =
> +		kzalloc(sizeof(*group) + size * sizeof(group->irq[0]), flags);
> +	int cpu;
> +
> +	if (!group)
> +		return NULL;
> +
> +	/* Initially assign CPUs to IRQs on a rota */
> +	for (cpu = 0; cpu < NR_CPUS; cpu++) {
> +		group->closest[cpu].index = cpu % size;

  So here we randomly assign index with the lower cpu numbers no
  matter whether they are online or possible ?

> +		group->closest[cpu].dist = IRQ_CPU_DIST_INF;
> +	}
> +
> +	group->size = size;
> +	return group;
> +}
> +EXPORT_SYMBOL(alloc_irq_group);

  EXPORT_SYMBOL_GPL if at all. Same for the other exports

> +
> +/**
> + *	free_irq_group - free IRQ group
> + *	@group:		IRQ group allocated with alloc_irq_group(), or %NULL

  How is this serialized or sanity checked against free_irq() ?

> + */
> +void free_irq_group(struct irq_group *group)
> +{
> +	struct irq_desc *desc;
> +	unsigned int i;
> +
> +	if (!group)
> +		return;
> +
> +	/* Remove all descriptors from the group */
> +	for (i = 0; i < group->used; i++) {
> +		desc = group->irq[i];
> +		BUG_ON(desc->group != group || desc->group_index != i);
> +		desc->group = NULL;
> +	}
> +
> +	kfree(group);
> +}
> +EXPORT_SYMBOL(free_irq_group);
> +
> +/**
> + *	irq_group_add - add IRQ to a group
> + *	@group:		IRQ group allocated with alloc_irq_group()
> + *	@irq:		Interrupt to add to group
> + */
> +void irq_group_add(struct irq_group *group, unsigned int irq)
> +{
> +	struct irq_desc *desc = irq_to_desc(irq);

  Again, how is this serialized against anything else fiddling with
  irq_desc[irq]?

> +	BUG_ON(desc->group);
> +	BUG_ON(group->used >= group->size);
> +
> +	desc->group = group;
> +	desc->group_index = group->used;
> +	group->irq[group->used++] = desc;
> +}
> +EXPORT_SYMBOL(irq_group_add);

Thanks,

	tglx

Re: [RFC][PATCH 1/4] IRQ: IRQ groups for multiqueue devices

[Ben Hutchings]

On Mon, 2010-09-20 at 23:27 +0200, Thomas Gleixner wrote:
> Ben,
> 
> On Mon, 20 Sep 2010, Ben Hutchings wrote:
> 
> it would have been nice if I'd been cc'ed on that, but of course it's
> my fault that there is no entry in MAINTAINERS. No, it's not.
> 
> > When initiating I/O on multiqueue devices, we usually want to select a
> 
> "we usually" is pretty useless for people not familiar with the
> problem at hand. A [PATCH 0/4] intro would have been helpful along
> with the users (aka [PATCH 2-4/4]) of the new facility.

There was an intro on the netdev list
<http://article.gmane.org/gmane.linux.network/172427> but it probably
doesn't tell you what you want to know anyway.

> Don't take it personally and I'm sure that you're solving a real world
> problem, but I'm starting to get grumpy that especially networking
> folks (aside of various driver developers) believe that adding random
> stuff to kernel/irq is their private pleasure. Is it that hard to talk
> to me upfront ?
> 
> > queue for which the response will be handled on the same or a nearby
> > CPU.  IRQ groups hold a mapping of CPU to IRQ which will be updated
> > based on the inverse of IRQ CPU-affinities plus CPU topology
> > information.
> 
> Can you please explain, why you need that reverse mapping including
> the below code ? What problem does this solve which can not be deduced
> by the exisiting information/infrastructure ? And why is that reverse
> mapping tied to interrupts and not something which we want to see in
> some generic available (library) code ?

Are you thinking of a per-CPU distance map?  That seems like it would be
useful to have.  I wonder about the storage requirements on larger
systems.

> More comments inline.
> 
> > ---
> >  include/linux/irq.h |   52 ++++++++++++++++++
> >  kernel/irq/manage.c |  149 +++++++++++++++++++++++++++++++++++++++++++++++++++
> >  2 files changed, 201 insertions(+), 0 deletions(-)
> > 
> > diff --git a/include/linux/irq.h b/include/linux/irq.h
> > index c03243a..bbddd5f 100644
> > --- a/include/linux/irq.h
> > +++ b/include/linux/irq.h
> > @@ -196,6 +196,8 @@ struct irq_desc {
> >  #ifdef CONFIG_SMP
> >  	cpumask_var_t		affinity;
> >  	const struct cpumask	*affinity_hint;
> 
>   How about updating the kernel doc above the struct ?
> 
> > +	struct irq_group	*group;
> 
>   Grr, how does this compile ? That needs at least a forward
>   declaration of struct irq_group. RFC is _NOT_ an excuse

Naming a struct in a function parameter declarator is not a valid
forward declaration, but this is.

> > +	u16			group_index;
> 
>   What's group_index doing and what's the point of an u16 here ?

Index of this IRQ within the group.

> >  	unsigned int		node;
> >  #ifdef CONFIG_GENERIC_PENDING_IRQ
> >  	cpumask_var_t		pending_mask;
> > @@ -498,6 +500,33 @@ static inline void free_desc_masks(struct irq_desc *old_desc,
> >  #endif
> >  }
> >  
> > +/**
> > + * struct irq_group - IRQ group for multiqueue devices
> > + * @closest: For each CPU, the index and distance to the closest IRQ,
> > + *	based on affinity masks
> 
>   index of what ?

Index within the group of the closest IRQ for this CPU; also the queue
index.

[...]
> > +static inline u16 irq_group_get_index(struct irq_group *group, int cpu)
> > +{
> > +	return group->closest[cpu].index;
> > +}
> > +
> 
>   So you have an accessor function for closest[cpu].index. Are the
>   other members meant to be accessible directly by random driver ?

No, they should not be touched at all.

> >  #else /* !CONFIG_SMP */
> >  
> >  static inline bool alloc_desc_masks(struct irq_desc *desc, int node,
> > @@ -519,6 +548,29 @@ static inline void free_desc_masks(struct irq_desc *old_desc,
> >  				   struct irq_desc *new_desc)
> >  {
> >  }
> > +
> > +struct irq_group {
> > +};
> > +
> > +static inline struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags)
> > +{
> > +	static struct irq_group dummy;
> 
>   That will create one static instance per callsite. Is that on
>   purpose? If yes, it needs a damned good comment.

Which uses no storage, or maybe 1 byte.  I'm open to suggestions for a
better dummy implementation.

> > +	return &dummy;
> 
> >  #endif	/* CONFIG_SMP */
> >  
> >  #endif /* _LINUX_IRQ_H */
> > diff --git a/kernel/irq/manage.c b/kernel/irq/manage.c
> > index c3003e9..3f2b1a9 100644
> > --- a/kernel/irq/manage.c
> > +++ b/kernel/irq/manage.c
> > @@ -100,6 +100,154 @@ void irq_set_thread_affinity(struct irq_desc *desc)
> >  	}
> >  }
> >  
> > +static void irq_group_update_neigh(struct irq_group *group,
> > +				   const struct cpumask *mask,
> > +				   u16 index, u16 dist)
> > +{
> > +	int cpu;
> > +
> > +	for_each_cpu(cpu, mask) {
> > +		if (dist < group->closest[cpu].dist) {
> > +			group->closest[cpu].index = index;
> > +			group->closest[cpu].dist = dist;
> > +		}
> > +	}
> > +}
> 
>   I have not the faintest idea how group, index and dist are related
>   to each other. And I have no intention to decode the information
>   about that piecewise by reverse engineering that obfuscated code.

I'm happy to write more comments.

index is the index of the IRQ being updated within the group.  dist is
the maximum distance of that IRQ from the CPUs in the mask.

> > +static bool irq_group_copy_neigh(struct irq_group *group, int cpu,
> > +				 const struct cpumask *mask, u16 dist)
> > +{
> > +	int neigh;
> > +
> > +	for_each_cpu(neigh, mask) {
> > +		if (group->closest[neigh].dist <= dist) {
> > +			group->closest[cpu].index = group->closest[neigh].index;
> > +			group->closest[cpu].dist = dist;
> > +			return true;
> > +		}
> > +	}
> > +	return false;
> 
>   What's the reason for copying or not ?

We're trying to find closer IRQs for the CPUs which were removed from
the affinity of the IRQ currently being moved.

[...]
> > +		/* We could continue into NUMA node distances, but for now
> > +		 * we give up. */
> 
>   What are the consequences of giving up ? Does not happen ? Should
>   not happen ? Will break ? Don't care ? ....

Poor choice of closest IRQ.  Nothing disastrous.

> > +	}
> 
>   This is called from irq_set_affinity() with desc->lock held and
>   interrupts disabled. You're not serious about that, are you ?
> 
>   Damned, there are two iterations over each online cpu and another
>   one over the affinity mask. Did you ever extrapolate how long that
>   runs on a really large machine ?

No, and I know this sucks.  So, do you want to suggest anything better?
Should I look at building those CPU distance maps (trading space for
time)?

>   If CPU affinity of an IRQ changes, then it does not matter if one or
>   two interrupts end up in the wrong space. Those changes are not
>   happening every other interrupt.
> 
> > +}
> > +
> > +/**
> > + *	alloc_irq_group - allocate IRQ group
> > + *	@size:		Size of the group
> 
>   size of what ? I guess number of interrupts, right ?

Right.

> > + *	@flags:		Allocation flags e.g. %GFP_KERNEL
> > + */
> > +struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags)
> > +{
> > +	struct irq_group *group =
> > +		kzalloc(sizeof(*group) + size * sizeof(group->irq[0]), flags);
> > +	int cpu;
> > +
> > +	if (!group)
> > +		return NULL;
> > +
> > +	/* Initially assign CPUs to IRQs on a rota */
> > +	for (cpu = 0; cpu < NR_CPUS; cpu++) {
> > +		group->closest[cpu].index = cpu % size;
> 
>   So here we randomly assign index with the lower cpu numbers no
>   matter whether they are online or possible ?

Doesn't matter, because we're mapping CPUs to IRQs not the other way
round.

> > +		group->closest[cpu].dist = IRQ_CPU_DIST_INF;
> > +	}
> > +
> > +	group->size = size;
> > +	return group;
> > +}
> > +EXPORT_SYMBOL(alloc_irq_group);
> 
>   EXPORT_SYMBOL_GPL if at all. Same for the other exports
> 
> > +
> > +/**
> > + *	free_irq_group - free IRQ group
> > + *	@group:		IRQ group allocated with alloc_irq_group(), or %NULL
> 
>   How is this serialized or sanity checked against free_irq() ?

free_irq() should be called first, for all IRQs in the group.  The IRQs
should then be really freed with pci_disable_msix() or similar.

> > + */
> > +void free_irq_group(struct irq_group *group)
> > +{
> > +	struct irq_desc *desc;
> > +	unsigned int i;
> > +
> > +	if (!group)
> > +		return;
> > +
> > +	/* Remove all descriptors from the group */
> > +	for (i = 0; i < group->used; i++) {
> > +		desc = group->irq[i];
> > +		BUG_ON(desc->group != group || desc->group_index != i);
> > +		desc->group = NULL;
> > +	}
> > +
> > +	kfree(group);
> > +}
> > +EXPORT_SYMBOL(free_irq_group);
> > +
> > +/**
> > + *	irq_group_add - add IRQ to a group
> > + *	@group:		IRQ group allocated with alloc_irq_group()
> > + *	@irq:		Interrupt to add to group
> > + */
> > +void irq_group_add(struct irq_group *group, unsigned int irq)
> > +{
> > +	struct irq_desc *desc = irq_to_desc(irq);
> 
>   Again, how is this serialized against anything else fiddling with
>   irq_desc[irq]?

The driver should call this after allocating IRQs with pci_enable_msix()
or similar and before setting the handlers with request_irq().  Is that
sufficient?

Ben.

> > +	BUG_ON(desc->group);
> > +	BUG_ON(group->used >= group->size);
> > +
> > +	desc->group = group;
> > +	desc->group_index = group->used;
> > +	group->irq[group->used++] = desc;
> > +}
> > +EXPORT_SYMBOL(irq_group_add);
> 
> Thanks,
> 
> 	tglx

-- 
Ben Hutchings, Senior Software Engineer, Solarflare Communications
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [RFC][PATCH 1/4] IRQ: IRQ groups for multiqueue devices

[Thomas Gleixner]

On Tue, 21 Sep 2010, Ben Hutchings wrote:
> On Mon, 2010-09-20 at 23:27 +0200, Thomas Gleixner wrote:
> > > queue for which the response will be handled on the same or a nearby
> > > CPU.  IRQ groups hold a mapping of CPU to IRQ which will be updated
> > > based on the inverse of IRQ CPU-affinities plus CPU topology
> > > information.
> > 
> > Can you please explain, why you need that reverse mapping including
> > the below code ? What problem does this solve which can not be deduced
> > by the exisiting information/infrastructure ? And why is that reverse
> > mapping tied to interrupts and not something which we want to see in
> > some generic available (library) code ?
> 
> Are you thinking of a per-CPU distance map?  That seems like it would be
> useful to have.  I wonder about the storage requirements on larger
> systems.

  That might be a problem, but we should at least look into this.

  But even if a prebuilt map is too expensive storage wise, then the
  functions which build the lookup map might be useful for similar
  distance lookup scenarios as well.

> > > +static inline struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags)
> > > +{
> > > +	static struct irq_group dummy;
> > 
> >   That will create one static instance per callsite. Is that on
> >   purpose? If yes, it needs a damned good comment.
> 
> Which uses no storage, or maybe 1 byte.  I'm open to suggestions for a
> better dummy implementation.
> 
> > > +	return &dummy;

  Why does it need to return a real struct instead of NULL ?
 
> > > +	}
> > 
> >   This is called from irq_set_affinity() with desc->lock held and
> >   interrupts disabled. You're not serious about that, are you ?
> > 
> >   Damned, there are two iterations over each online cpu and another
> >   one over the affinity mask. Did you ever extrapolate how long that
> >   runs on a really large machine ?
> 
> No, and I know this sucks.  So, do you want to suggest anything better?
> Should I look at building those CPU distance maps (trading space for
> time)?

  The point is that there is no reason why this code needs to run in a
  spinlocked irq disabled reason. I know why your implementation needs
  it, because it protects you against module unload etc. Come on, we
  have enough infrastructure to control the lifetime of objects in
  sane ways and not by hijacking a heavy lock and disabling
  interrupts.

  Btw, how does this code deal with concurrent affinity setting of
  multiple irqs in the group ? Random number generator ?

> > > + *	@flags:		Allocation flags e.g. %GFP_KERNEL

  Why do we need flags here? That code gets called in a device setup
  routine and not from random context.

> > > + */
> > > +struct irq_group *alloc_irq_group(unsigned int size, gfp_t flags)
> > > +{

> > > +
> > > +/**
> > > + *	free_irq_group - free IRQ group
> > > + *	@group:		IRQ group allocated with alloc_irq_group(), or %NULL
> > 
> >   How is this serialized or sanity checked against free_irq() ?
> 
> free_irq() should be called first, for all IRQs in the group.  The IRQs
> should then be really freed with pci_disable_msix() or similar.

  I explained that several times, that I do not care about what should
  be called in which order and what not. Driver coders get it wrong
  all the time, then it explodes in the genirq code and I get the crap
  to debug. No, thanks.

  Also if you call free_irq() first, then you still have a reference
  to that very irq descriptor in your group and a reference to the
  group in the irq descriptor. Brilliant, as the irq descriptor can be
  reused immediately after free_irq().

  Also it's not only problematic against free_irq, it's damned racy
  against a concurrent affinity setting as well. And that's not
  controlled by "should be called" at all.

> > > +/**
> > > + *	irq_group_add - add IRQ to a group
> > > + *	@group:		IRQ group allocated with alloc_irq_group()
> > > + *	@irq:		Interrupt to add to group
> > > + */
> > > +void irq_group_add(struct irq_group *group, unsigned int irq)
> > > +{
> > > +	struct irq_desc *desc = irq_to_desc(irq);
> > 
> >   Again, how is this serialized against anything else fiddling with
> >   irq_desc[irq]?
> 
> The driver should call this after allocating IRQs with pci_enable_msix()
> or similar and before setting the handlers with request_irq().  Is that
> sufficient?

  "should call" is _NEVER_ sufficient. fiddling with irq_desc w/o
  holding the lock is a nono, period.

> > > +	BUG_ON(desc->group);
> > > +	BUG_ON(group->used >= group->size);
> > > +
> > > +	desc->group = group;
> > > +	desc->group_index = group->used;
> > > +	group->irq[group->used++] = desc;

  Forgot to ask yesterday. Why do we need to store irq desc in the
  group ? For free_irq_group() I guess, but I explained already why
  this code is broken. And it's even more broken when an irq is moved
  to a different node and CONFIG_NUMA_IRQ_DESC=y.

Lemme summarize what I understand so far. For multiqueue devices with
several queues and interrupts you want to lookup the closest queue/irq
to the cpu on which you are currently running to avoid expensive cross
node memory access. Now you need to follow affinity changes for this
lookup table.

The basic idea of your code is ok. The lookup table itself is fine,
but the integration into the genirq code sucks. What needs to be done:

1) Remove the references to irq_desc in the group. They are not needed
   and will never work. The group does not need any information about
   the irq number and the irq descriptor.

2) Add proper refcounting to struct irq_group so it can be accessed
   outside of irq_desc->lock.

3) Move the update of the map outside of irq_desc->lock and the irq
   disabled region. Update the map in setup_affinity() as well. That
   code can be called from various atomic contexts, so it's probably
   the best thing to delegate the update to a workqueue or such unless
   you come up with a nice prebuilt lookup table.

4) Add comments so the code is understandable for mere mortals

5) Add proper install/free handling. Hint: affinity_hint

6) All modifications of irq_desc need a check whether irq_to_desc
   returned a valid pointer and must hold desc->lock

7) Deal with concurrent updates of multiple irqs in a group (at least
   a comment why the code does not need serialization)

8) Move the code to kernel/irq/irqgroup.c or some other sensible name
   and make it configurable so embedded folks don't have to carry it
   around as useless binary bloat.

Thanks,

	tglx

Re: [RFC][PATCH 1/4] IRQ: IRQ groups for multiqueue devices

[Thomas Gleixner]

On Tue, 21 Sep 2010, Thomas Gleixner wrote:
> On Tue, 21 Sep 2010, Ben Hutchings wrote:
> > On Mon, 2010-09-20 at 23:27 +0200, Thomas Gleixner wrote:
> Lemme summarize what I understand so far. For multiqueue devices with
> several queues and interrupts you want to lookup the closest queue/irq
> to the cpu on which you are currently running to avoid expensive cross
> node memory access. Now you need to follow affinity changes for this
> lookup table.
> 
> The basic idea of your code is ok. The lookup table itself is fine,
> but the integration into the genirq code sucks. What needs to be done:
> 
> 1) Remove the references to irq_desc in the group. They are not needed
>    and will never work. The group does not need any information about
>    the irq number and the irq descriptor.
> 
> 2) Add proper refcounting to struct irq_group so it can be accessed
>    outside of irq_desc->lock.
> 
> 3) Move the update of the map outside of irq_desc->lock and the irq
>    disabled region. Update the map in setup_affinity() as well. That
>    code can be called from various atomic contexts, so it's probably
>    the best thing to delegate the update to a workqueue or such unless
>    you come up with a nice prebuilt lookup table.
> 
> 4) Add comments so the code is understandable for mere mortals
> 
> 5) Add proper install/free handling. Hint: affinity_hint
> 
> 6) All modifications of irq_desc need a check whether irq_to_desc
>    returned a valid pointer and must hold desc->lock
> 
> 7) Deal with concurrent updates of multiple irqs in a group (at least
>    a comment why the code does not need serialization)
> 
> 8) Move the code to kernel/irq/irqgroup.c or some other sensible name
>    and make it configurable so embedded folks don't have to carry it
>    around as useless binary bloat.

Talked to Peter about it and we came to the conclusion, that we should
just provide a callback infrastructure in the irq code which does not
care about the action behind it. That's going to solve #1,#2,#3,#5,#6
and parts of #8

That queue/index map code should move to lib/ or some other
appropriate place so it can be shared with storage or whatever is
going to grow multiqueue. comments #4, #7, #8 (s@kernel/irq@lib/@)
above still apply :)

The modification to the genirq code would be based on registering

struct irq_affinity_callback {
	unsigned int irq;
	struct kref kref;
	struct work work;
	void (*callback)(struct irq_affinity_callback *, const cpumask_t *mask);
	void (*release)(struct kref *ref);
};

for an interrupt via 

int irq_set_affinity_callback(unsigned int irq,
    			      struct irq_affinity_callback *cb);

That function can be called with cb=NULL to remove the callback. if
cb!=NULL, irq, kref and work are initialized.

The genirq code schedules work when affinity changes and the callback
struct pointer is non NULL. The callback is then called from the
worker thread with a copy of the irq affinity mask.

So on any affinity change, we do with desc->lock held:

   if (desc->affinity_callback) {
      	kref_get(&desc->affinity_callback->kref);
	schedule_work(&desc->affinity_callback->work);
   }

The worker function in the genirq code does:
{
    struct irq_affinity_callback *cb;
    struct irq_desc *desc;
    cpu_mask_t cpumask;

    cb = container_of(work, struct irq_affinity_callback, work);

    desc = irq_to_desc(cb->irq);
    if (!desc)
       goto out;

    if (!alloc_cpumask_var(&cpumask, GFP_KERNEL)
       goto out;

    raw_spin_lock_irqsave(&desc->lock, flags);
    cpumask_copy(cpumask, desc->affinity);
    raw_spin_unlock_irqrestore(&desc->lock, flags);

    cb->callback(cb, cpumask);

    free_cpumask_var(cpumask);
out:
    kref_put(&cb->kref, cb->release);
}

That allows you to do all kind of magic in thread context, updating
the queue map, reallocating queue memory when the node affinity
changes (I know that you want to), go wild.

Thoughts ?

	 tglx

Re: [RFC][PATCH 1/4] IRQ: IRQ groups for multiqueue devices

[Ben Hutchings]

On Tue, 2010-09-21 at 21:04 +0200, Thomas Gleixner wrote:
[...]
> Talked to Peter about it and we came to the conclusion, that we should
> just provide a callback infrastructure in the irq code which does not
> care about the action behind it. That's going to solve #1,#2,#3,#5,#6
> and parts of #8
> 
> That queue/index map code should move to lib/ or some other
> appropriate place so it can be shared with storage or whatever is
> going to grow multiqueue. comments #4, #7, #8 (s@kernel/irq@lib/@)
> above still apply :)

OK.

> The modification to the genirq code would be based on registering
> 
> struct irq_affinity_callback {
> 	unsigned int irq;
> 	struct kref kref;
> 	struct work work;
> 	void (*callback)(struct irq_affinity_callback *, const cpumask_t *mask);
> 	void (*release)(struct kref *ref);
> };
> 
> for an interrupt via 
> 
> int irq_set_affinity_callback(unsigned int irq,
>     			      struct irq_affinity_callback *cb);
> 
> That function can be called with cb=NULL to remove the callback. if
> cb!=NULL, irq, kref and work are initialized.

When should it be called, relative to {request,free}_irq() and
pci_{disable,enable}_msix()?

[...]
> That allows you to do all kind of magic in thread context, updating
> the queue map, reallocating queue memory when the node affinity
> changes (I know that you want to), go wild.

I definitely don't want to reallocate queues if node affinity of the IRQ
is changed by irqbalance, because this will disrupt traffic.  So
changing the node affinity of queues has to be a separate operation.

> Thoughts ?

This does look like something I can use, thanks.

Ben.

-- 
Ben Hutchings, Senior Software Engineer, Solarflare Communications
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [RFC][PATCH 1/4] IRQ: IRQ groups for multiqueue devices

[Thomas Gleixner]

On Wed, 22 Sep 2010, Ben Hutchings wrote:

> On Tue, 2010-09-21 at 21:04 +0200, Thomas Gleixner wrote:
> [...]
> > Talked to Peter about it and we came to the conclusion, that we should
> > just provide a callback infrastructure in the irq code which does not
> > care about the action behind it. That's going to solve #1,#2,#3,#5,#6
> > and parts of #8
> > 
> > That queue/index map code should move to lib/ or some other
> > appropriate place so it can be shared with storage or whatever is
> > going to grow multiqueue. comments #4, #7, #8 (s@kernel/irq@lib/@)
> > above still apply :)
> 
> OK.
> 
> > The modification to the genirq code would be based on registering
> > 
> > struct irq_affinity_callback {
> > 	unsigned int irq;
> > 	struct kref kref;
> > 	struct work work;
> > 	void (*callback)(struct irq_affinity_callback *, const cpumask_t *mask);
> > 	void (*release)(struct kref *ref);
> > };
> > 
> > for an interrupt via 
> > 
> > int irq_set_affinity_callback(unsigned int irq,
> >     			      struct irq_affinity_callback *cb);
> > 
> > That function can be called with cb=NULL to remove the callback. if
> > cb!=NULL, irq, kref and work are initialized.
> 
> When should it be called, relative to {request,free}_irq() and
> pci_{disable,enable}_msix()?

It should be called before request_irq and before free_irq. free_irq
will warn when the pointer is !NULL.
 
> [...]
> > That allows you to do all kind of magic in thread context, updating
> > the queue map, reallocating queue memory when the node affinity
> > changes (I know that you want to), go wild.
> 
> I definitely don't want to reallocate queues if node affinity of the IRQ
> is changed by irqbalance, because this will disrupt traffic.  So
> changing the node affinity of queues has to be a separate operation.

Fair enough.
 
> > Thoughts ?
> 
> This does look like something I can use, thanks.

Will look into it in the next days.

Thanks,

	tglx