[PATCH 1/3] staging: greybus: loopback.c: remove unused gb_loopback::lbid

[PATCH 1/3] staging: greybus: loopback.c: remove unused gb_loopback::lbid

[Rasmus Villemoes]

It's not obvious how the code prevents adding more than 31 elements to
the list and thus invoking undefined behaviour in the 1 << new_lbid
expression, and in practice causing ->lbid values to repeat every 32
elements.

But the definition of struct gb_loopback is local to loopback.c, and the
lbid field is entirely unused outside of this function, so it seems we
can just drop it entirely.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
Since lbid isn't mentioned anywhere else in greybus/, it's hard to
figure out how it was meant to be used. It does seem like entirely
dead (write-only) code.

 drivers/staging/greybus/loopback.c | 8 --------
 1 file changed, 8 deletions(-)

diff --git a/drivers/staging/greybus/loopback.c b/drivers/staging/greybus/loopback.c
index 42f6f3de967c..7080294f705c 100644
--- a/drivers/staging/greybus/loopback.c
+++ b/drivers/staging/greybus/loopback.c
@@ -97,7 +97,6 @@ struct gb_loopback {
 	u32 timeout_min;
 	u32 timeout_max;
 	u32 outstanding_operations_max;
-	u32 lbid;
 	u64 elapsed_nsecs;
 	u32 apbridge_latency_ts;
 	u32 gbphy_latency_ts;
@@ -1014,16 +1013,9 @@ static int gb_loopback_bus_id_compare(void *priv, struct list_head *lha,
 
 static void gb_loopback_insert_id(struct gb_loopback *gb)
 {
-	struct gb_loopback *gb_list;
-	u32 new_lbid = 0;
-
 	/* perform an insertion sort */
 	list_add_tail(&gb->entry, &gb_dev.list);
 	list_sort(NULL, &gb_dev.list, gb_loopback_bus_id_compare);
-	list_for_each_entry(gb_list, &gb_dev.list, entry) {
-		gb_list->lbid = 1 << new_lbid;
-		new_lbid++;
-	}
 }
 
 #define DEBUGFS_NAMELEN 32
-- 
2.19.0

[PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n)

[Rasmus Villemoes]

"Append to the list and do a merge sort" is not really an insertion
sort. While a few more lines of code, we can keep the list sorted doing
at most n comparisons by iterating until we find the first element
strictly greater than gb.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
I have no idea if the performance matters (it probably doesn't). Feel
free to ignore this and the followup cleanup.

 drivers/staging/greybus/loopback.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/drivers/staging/greybus/loopback.c b/drivers/staging/greybus/loopback.c
index 7080294f705c..89c3f6fd8ddf 100644
--- a/drivers/staging/greybus/loopback.c
+++ b/drivers/staging/greybus/loopback.c
@@ -1013,9 +1013,19 @@ static int gb_loopback_bus_id_compare(void *priv, struct list_head *lha,
 
 static void gb_loopback_insert_id(struct gb_loopback *gb)
 {
-	/* perform an insertion sort */
-	list_add_tail(&gb->entry, &gb_dev.list);
-	list_sort(NULL, &gb_dev.list, gb_loopback_bus_id_compare);
+	struct gb_loopback *gb_list;
+
+	/*
+	 * Keep the list sorted. Insert gb before the first element it
+	 * compares strictly less than. If no such element exists, the
+	 * loop terminates with &gb_list->entry being &gb_dev.list,
+	 * and we thus insert at the end.
+	 */
+	list_for_each_entry(gb_list, &gb_dev.list, entry) {
+		if (gb_loopback_bus_id_compare(NULL, &gb->entry, &gb_list->entry) < 0)
+			break;
+	}
+	list_add_tail(&gb->entry, &gb_list->entry);
 }
 
 #define DEBUGFS_NAMELEN 32
-- 
2.19.0

Re: [PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n)

[Bryan O'Donoghue]

On 05/10/2018 15:28, Rasmus Villemoes wrote:
> Signed-off-by: Rasmus Villemoes<linux@rasmusvillemoes.dk>
> ---
> I have no idea if the performance matters (it probably doesn't). Feel
> free to ignore this and the followup cleanup.

What's the problem you're fixing here ?

Is it tested ?

Re: [PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n)

[Rasmus Villemoes]

On 2018-10-11 01:03, Bryan O'Donoghue wrote:
> On 05/10/2018 15:28, Rasmus Villemoes wrote:
>> Signed-off-by: Rasmus Villemoes<linux@rasmusvillemoes.dk>
>> ---
>> I have no idea if the performance matters (it probably doesn't). Feel
>> free to ignore this and the followup cleanup.
> 
> What's the problem you're fixing here ?

No problem, really, other than my inner Paul Hogan telling me "That's
not an insertion sort, ...".

> Is it tested ?

Compile-tested. As I said, if the performance (and inaccurate comment)
is irrelevant, just drop it.

Rasmus

Re: [PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n)

[Rasmus Villemoes]

On 2018-10-11 01:03, Bryan O'Donoghue wrote:
> On 05/10/2018 15:28, Rasmus Villemoes wrote:
>> Signed-off-by: Rasmus Villemoes<linux@rasmusvillemoes.dk>
>> ---
>> I have no idea if the performance matters (it probably doesn't). Feel
>> free to ignore this and the followup cleanup.
> 
> What's the problem you're fixing here ?
> 
> Is it tested ?

I got curious why one would want to keep a linked list sorted in the
first place (it can't be for doing binary searches). But it seems that
gb_loopback_device::list is unused, along with the list_op_async. Given
that the below compiles, doesn't that prove that the code is
dead/unused, or what am I missing?

diff --git a/drivers/staging/greybus/loopback.c
b/drivers/staging/greybus/loopback.c
index 7080294f705c..e4d42c1dc284 100644
--- a/drivers/staging/greybus/loopback.c
+++ b/drivers/staging/greybus/loopback.c
@@ -47,8 +47,6 @@ struct gb_loopback_device {

 	/* We need to take a lock in atomic context */
 	spinlock_t lock;
-	struct list_head list;
-	struct list_head list_op_async;
 	wait_queue_head_t wq;
 };

@@ -68,7 +66,6 @@ struct gb_loopback {
 	struct kfifo kfifo_lat;
 	struct mutex mutex;
 	struct task_struct *task;
-	struct list_head entry;
 	struct device *dev;
 	wait_queue_head_t wq;
 	wait_queue_head_t wq_completion;
@@ -987,37 +984,6 @@ static const struct file_operations
gb_loopback_debugfs_latency_ops = {
 	.release	= single_release,
 };

-static int gb_loopback_bus_id_compare(void *priv, struct list_head *lha,
-				      struct list_head *lhb)
-{
-	struct gb_loopback *a = list_entry(lha, struct gb_loopback, entry);
-	struct gb_loopback *b = list_entry(lhb, struct gb_loopback, entry);
-	struct gb_connection *ca = a->connection;
-	struct gb_connection *cb = b->connection;
-
-	if (ca->bundle->intf->interface_id < cb->bundle->intf->interface_id)
-		return -1;
-	if (cb->bundle->intf->interface_id < ca->bundle->intf->interface_id)
-		return 1;
-	if (ca->bundle->id < cb->bundle->id)
-		return -1;
-	if (cb->bundle->id < ca->bundle->id)
-		return 1;
-	if (ca->intf_cport_id < cb->intf_cport_id)
-		return -1;
-	else if (cb->intf_cport_id < ca->intf_cport_id)
-		return 1;
-
-	return 0;
-}
-
-static void gb_loopback_insert_id(struct gb_loopback *gb)
-{
-	/* perform an insertion sort */
-	list_add_tail(&gb->entry, &gb_dev.list);
-	list_sort(NULL, &gb_dev.list, gb_loopback_bus_id_compare);
-}
-
 #define DEBUGFS_NAMELEN 32

 static int gb_loopback_probe(struct gb_bundle *bundle,
@@ -1113,7 +1079,6 @@ static int gb_loopback_probe(struct gb_bundle *bundle,
 	}

 	spin_lock_irqsave(&gb_dev.lock, flags);
-	gb_loopback_insert_id(gb);
 	gb_dev.count++;
 	spin_unlock_irqrestore(&gb_dev.lock, flags);

@@ -1169,7 +1134,6 @@ static void gb_loopback_disconnect(struct
gb_bundle *bundle)

 	spin_lock_irqsave(&gb_dev.lock, flags);
 	gb_dev.count--;
-	list_del(&gb->entry);
 	spin_unlock_irqrestore(&gb_dev.lock, flags);

 	device_unregister(gb->dev);
@@ -1196,8 +1160,6 @@ static int loopback_init(void)
 {
 	int retval;

-	INIT_LIST_HEAD(&gb_dev.list);
-	INIT_LIST_HEAD(&gb_dev.list_op_async);
 	spin_lock_init(&gb_dev.lock);
 	gb_dev.root = debugfs_create_dir("gb_loopback", NULL);

Re: [PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n)

[Bryan O'Donoghue]

On 23/10/2018 17:20, Rasmus Villemoes wrote:
> On 2018-10-11 01:03, Bryan O'Donoghue wrote:
>> On 05/10/2018 15:28, Rasmus Villemoes wrote:
>>> Signed-off-by: Rasmus Villemoes<linux@rasmusvillemoes.dk>
>>> ---
>>> I have no idea if the performance matters (it probably doesn't). Feel
>>> free to ignore this and the followup cleanup.
>>
>> What's the problem you're fixing here ?
>>
>> Is it tested ?
> 
> I got curious why one would want to keep a linked list sorted in the
> first place (it can't be for doing binary searches). But it seems that
> gb_loopback_device::list is unused, along with the list_op_async. Given
> that the below compiles, doesn't that prove that the code is
> dead/unused, or what am I missing?
> 
> diff --git a/drivers/staging/greybus/loopback.c
> b/drivers/staging/greybus/loopback.c
> index 7080294f705c..e4d42c1dc284 100644
> --- a/drivers/staging/greybus/loopback.c
> +++ b/drivers/staging/greybus/loopback.c
> @@ -47,8 +47,6 @@ struct gb_loopback_device {
> 
>   	/* We need to take a lock in atomic context */
>   	spinlock_t lock;
> -	struct list_head list;
> -	struct list_head list_op_async;
>   	wait_queue_head_t wq;
>   };
> 
> @@ -68,7 +66,6 @@ struct gb_loopback {
>   	struct kfifo kfifo_lat;
>   	struct mutex mutex;
>   	struct task_struct *task;
> -	struct list_head entry;
>   	struct device *dev;
>   	wait_queue_head_t wq;
>   	wait_queue_head_t wq_completion;
> @@ -987,37 +984,6 @@ static const struct file_operations
> gb_loopback_debugfs_latency_ops = {
>   	.release	= single_release,
>   };
> 
> -static int gb_loopback_bus_id_compare(void *priv, struct list_head *lha,
> -				      struct list_head *lhb)
> -{
> -	struct gb_loopback *a = list_entry(lha, struct gb_loopback, entry);
> -	struct gb_loopback *b = list_entry(lhb, struct gb_loopback, entry);
> -	struct gb_connection *ca = a->connection;
> -	struct gb_connection *cb = b->connection;
> -
> -	if (ca->bundle->intf->interface_id < cb->bundle->intf->interface_id)
> -		return -1;
> -	if (cb->bundle->intf->interface_id < ca->bundle->intf->interface_id)
> -		return 1;
> -	if (ca->bundle->id < cb->bundle->id)
> -		return -1;
> -	if (cb->bundle->id < ca->bundle->id)
> -		return 1;
> -	if (ca->intf_cport_id < cb->intf_cport_id)
> -		return -1;
> -	else if (cb->intf_cport_id < ca->intf_cport_id)
> -		return 1;
> -
> -	return 0;
> -}
> -
> -static void gb_loopback_insert_id(struct gb_loopback *gb)
> -{
> -	/* perform an insertion sort */
> -	list_add_tail(&gb->entry, &gb_dev.list);
> -	list_sort(NULL, &gb_dev.list, gb_loopback_bus_id_compare);
> -}
> -
>   #define DEBUGFS_NAMELEN 32
> 
>   static int gb_loopback_probe(struct gb_bundle *bundle,
> @@ -1113,7 +1079,6 @@ static int gb_loopback_probe(struct gb_bundle *bundle,
>   	}
> 
>   	spin_lock_irqsave(&gb_dev.lock, flags);
> -	gb_loopback_insert_id(gb);
>   	gb_dev.count++;
>   	spin_unlock_irqrestore(&gb_dev.lock, flags);
> 
> @@ -1169,7 +1134,6 @@ static void gb_loopback_disconnect(struct
> gb_bundle *bundle)
> 
>   	spin_lock_irqsave(&gb_dev.lock, flags);
>   	gb_dev.count--;
> -	list_del(&gb->entry);
>   	spin_unlock_irqrestore(&gb_dev.lock, flags);
> 
>   	device_unregister(gb->dev);
> @@ -1196,8 +1160,6 @@ static int loopback_init(void)
>   {
>   	int retval;
> 
> -	INIT_LIST_HEAD(&gb_dev.list);
> -	INIT_LIST_HEAD(&gb_dev.list_op_async);
>   	spin_lock_init(&gb_dev.lock);
>   	gb_dev.root = debugfs_create_dir("gb_loopback", NULL);
> 

Looks like dead code alright.

Reviewed-by: Bryan O'Donoghue <pure.logic@nexus-software.ie>

[PATCH 3/3] staging: greybus: loopback.c: simplify prototype of gb_loopback_bus_id_compare

[Rasmus Villemoes]

gb_loopback_bus_id_compare only has a single caller, and it no longer
needs to have a prototype compatible with being a callback for
list_sort.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 drivers/staging/greybus/loopback.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/drivers/staging/greybus/loopback.c b/drivers/staging/greybus/loopback.c
index 89c3f6fd8ddf..2c7bad66bb31 100644
--- a/drivers/staging/greybus/loopback.c
+++ b/drivers/staging/greybus/loopback.c
@@ -987,11 +987,8 @@ static const struct file_operations gb_loopback_debugfs_latency_ops = {
 	.release	= single_release,
 };
 
-static int gb_loopback_bus_id_compare(void *priv, struct list_head *lha,
-				      struct list_head *lhb)
+static int gb_loopback_bus_id_compare(struct gb_loopback *a, struct gb_loopback *b)
 {
-	struct gb_loopback *a = list_entry(lha, struct gb_loopback, entry);
-	struct gb_loopback *b = list_entry(lhb, struct gb_loopback, entry);
 	struct gb_connection *ca = a->connection;
 	struct gb_connection *cb = b->connection;
 
@@ -1022,7 +1019,7 @@ static void gb_loopback_insert_id(struct gb_loopback *gb)
 	 * and we thus insert at the end.
 	 */
 	list_for_each_entry(gb_list, &gb_dev.list, entry) {
-		if (gb_loopback_bus_id_compare(NULL, &gb->entry, &gb_list->entry) < 0)
+		if (gb_loopback_bus_id_compare(gb, gb_list) < 0)
 			break;
 	}
 	list_add_tail(&gb->entry, &gb_list->entry);
-- 
2.19.0

Re: [PATCH 1/3] staging: greybus: loopback.c: remove unused gb_loopback::lbid

[Bryan O'Donoghue]

On 05/10/2018 15:28, Rasmus Villemoes wrote:
> Since lbid isn't mentioned anywhere else in greybus/, it's hard to
> figure out how it was meant to be used. It does seem like entirely
> dead (write-only) code.
> 

yep, dead code

Reviewed-by: Bryan O'Donoghue <pure.logic@nexus-software.ie>

[PATCH v2] staging: greybus: loopback.c: remove unused lists

[Rasmus Villemoes]

gb_loopback_device::list_op_async is never used except for the
LIST_INIT. The ::list field appears to have a few more uses, but on
closer inspection the linked list of struct gb_loopbacks that it heads
is never used for anything, so there's no reason to maintain it, much
less to keep it sorted.

Reviewed-by: Bryan O'Donoghue <pure.logic@nexus-software.ie>
Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
Sending as a proper patch. Marked v2 since this replaces earlier 2/3
and 3/3 patches. Applies on top of
b4fc4e8340784e000030c5a59bf0791f9c3ce15e (staging: greybus:
loopback.c: remove unused gb_loopback::lbid).

 drivers/staging/greybus/loopback.c | 38 ------------------------------
 1 file changed, 38 deletions(-)

diff --git a/drivers/staging/greybus/loopback.c b/drivers/staging/greybus/loopback.c
index 7080294f705c..e4d42c1dc284 100644
--- a/drivers/staging/greybus/loopback.c
+++ b/drivers/staging/greybus/loopback.c
@@ -47,8 +47,6 @@ struct gb_loopback_device {
 
 	/* We need to take a lock in atomic context */
 	spinlock_t lock;
-	struct list_head list;
-	struct list_head list_op_async;
 	wait_queue_head_t wq;
 };
 
@@ -68,7 +66,6 @@ struct gb_loopback {
 	struct kfifo kfifo_lat;
 	struct mutex mutex;
 	struct task_struct *task;
-	struct list_head entry;
 	struct device *dev;
 	wait_queue_head_t wq;
 	wait_queue_head_t wq_completion;
@@ -987,37 +984,6 @@ static const struct file_operations gb_loopback_debugfs_latency_ops = {
 	.release	= single_release,
 };
 
-static int gb_loopback_bus_id_compare(void *priv, struct list_head *lha,
-				      struct list_head *lhb)
-{
-	struct gb_loopback *a = list_entry(lha, struct gb_loopback, entry);
-	struct gb_loopback *b = list_entry(lhb, struct gb_loopback, entry);
-	struct gb_connection *ca = a->connection;
-	struct gb_connection *cb = b->connection;
-
-	if (ca->bundle->intf->interface_id < cb->bundle->intf->interface_id)
-		return -1;
-	if (cb->bundle->intf->interface_id < ca->bundle->intf->interface_id)
-		return 1;
-	if (ca->bundle->id < cb->bundle->id)
-		return -1;
-	if (cb->bundle->id < ca->bundle->id)
-		return 1;
-	if (ca->intf_cport_id < cb->intf_cport_id)
-		return -1;
-	else if (cb->intf_cport_id < ca->intf_cport_id)
-		return 1;
-
-	return 0;
-}
-
-static void gb_loopback_insert_id(struct gb_loopback *gb)
-{
-	/* perform an insertion sort */
-	list_add_tail(&gb->entry, &gb_dev.list);
-	list_sort(NULL, &gb_dev.list, gb_loopback_bus_id_compare);
-}
-
 #define DEBUGFS_NAMELEN 32
 
 static int gb_loopback_probe(struct gb_bundle *bundle,
@@ -1113,7 +1079,6 @@ static int gb_loopback_probe(struct gb_bundle *bundle,
 	}
 
 	spin_lock_irqsave(&gb_dev.lock, flags);
-	gb_loopback_insert_id(gb);
 	gb_dev.count++;
 	spin_unlock_irqrestore(&gb_dev.lock, flags);
 
@@ -1169,7 +1134,6 @@ static void gb_loopback_disconnect(struct gb_bundle *bundle)
 
 	spin_lock_irqsave(&gb_dev.lock, flags);
 	gb_dev.count--;
-	list_del(&gb->entry);
 	spin_unlock_irqrestore(&gb_dev.lock, flags);
 
 	device_unregister(gb->dev);
@@ -1196,8 +1160,6 @@ static int loopback_init(void)
 {
 	int retval;
 
-	INIT_LIST_HEAD(&gb_dev.list);
-	INIT_LIST_HEAD(&gb_dev.list_op_async);
 	spin_lock_init(&gb_dev.lock);
 	gb_dev.root = debugfs_create_dir("gb_loopback", NULL);
 
-- 
2.19.1.6.gbde171bbf5