Skip to contentSkip to conversation

lib/list_sort: fix function type mismatches

PATCH In review Sami Tolvanen 3 participants 6 messages Jan 10, 2020 – Jan 11, 2020 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib/list_sort: fix function type mismatches

Casting the comparison function to a different type trips indirect call Control-Flow Integrity (CFI) checking. Remove the additional consts from cmp_func, and the now unneeded casts.

Fixes 043b3f7b6388 ("lib/list_sort: simplify and remove MAX_LIST_LENGTH_BITS")
---
 lib/list_sort.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
lib/list_sort.c +4 -4
index 52f0c258c895..b14accf4ef83 100644
@@ -8,7 +8,7 @@
 #include <linux/list.h>
 
 typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,
-		struct list_head const *, struct list_head const *);
+		struct list_head *, struct list_head *);
 
 /*
  * Returns a list organized in an intermediate format suited
@@ -227,7 +227,7 @@ void list_sort(void *priv, struct list_head *head,
 		if (likely(bits)) {
 			struct list_head *a = *tail, *b = a->prev;
 
-			a = merge(priv, (cmp_func)cmp, b, a);
+			a = merge(priv, cmp, b, a);
 			/* Install the merged result in place of the inputs */
 			a->prev = b->prev;
 			*tail = a;
@@ -249,10 +249,10 @@ void list_sort(void *priv, struct list_head *head,
 
 		if (!next)
 			break;
-		list = merge(priv, (cmp_func)cmp, pending, list);
+		list = merge(priv, cmp, pending, list);
 		pending = next;
 	}
 	/* The final merge, rebuilding prev links */
-	merge_final(priv, (cmp_func)cmp, head, pending, list);
+	merge_final(priv, cmp, head, pending, list);
 }
 EXPORT_SYMBOL(list_sort);

base-commit: ac61145a725ab0411c5f8ed9aeca6202076ecfd8

Signature · 1 line
2.25.0.rc1.283.g88dfdc4193-goog
#1 lore raw

lib/list_sort.c line 11

Quoted 3 lines

typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,

lib/list_sort.c +1 -1
-		struct list_head const *, struct list_head const *);
+		struct list_head *, struct list_head *);

I'd prefer to leave the const there for documentation. Does anyone object to fixing it in the other direction by *adding* const to all the call sites?

Andy Shevchenko posted a patch last 7 October that did that. <[email protected]>

(You could also try taking a second look at why __pure doesn't work, per AKPM's message of 16 April <[email protected]>)

#2 lore raw
Quoted 6 lines · George Spelvin

lib/list_sort.c line 11

Quoted 4 lines

typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,

lib/list_sort.c +1 -1
-             struct list_head const *, struct list_head const *);
+             struct list_head *, struct list_head *);

I'd prefer to leave the const there for documentation.

Not only. It's useful to show that we are not going to change those parameters.

Quoted 2 lines

Does anyone object to fixing it in the other direction by *adding* const to all the call sites?

Agree.
Actually we have cmp_r_funct_t which might be used here (I didn't check for the possibility, though).

Quoted 7 lines

Andy Shevchenko posted a patch last 7 October that did that. <[email protected]>

(You could also try taking a second look at why __pure doesn't work, per AKPM's message of 16 April <[email protected]>)

Hint: When you post Message-Id you may prefix them with
https://lore.kernel.org/r/ which makes search a bit more convenient and faster.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#3 lore raw
Quoted 8 lines · Andy Shevchenko
Quoted 6 lines · George Spelvin

lib/list_sort.c line 11

Quoted 4 lines

typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,

lib/list_sort.c +1 -1
-             struct list_head const *, struct list_head const *);
+             struct list_head *, struct list_head *);

I'd prefer to leave the const there for documentation.

Quoted 8 lines

Not only. It's useful to show that we are not going to change those parameters.

Quoted 2 lines

Does anyone object to fixing it in the other direction by *adding* const to all the call sites?

Agree.
Actually we have cmp_r_funct_t which might be used here (I didn't check for the possibility, though).

For the record, I have just checked users of list_sort() in regard to constify of priv parameter and only ACPI HMAT is using it as not const. UBIFS and XFS do not change the data (if I didn't miss anything).

But the amount of changes there perhaps not worth of doing. So, maybe new type like
cmp_w_func_t where priv is not const would be good enough for merge().

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#4 lore raw
In reply to Andy Shevchenko
Quoted 3 lines · Andy Shevchenko

Hint: When you post Message-Id you may prefix them with
https://lore.kernel.org/r/ which makes search a bit more convenient and faster.

I just learned that https://marc.info/?i= also works, so
https://lore.kernel.org/r/[email protected]
https://marc.info/[email protected]

https://lore.kernel.org/r/[email protected]
https://marc.info/[email protected]

Quoted 4 lines

For the record, I have just checked users of list_sort() in regard to constify of priv parameter and only ACPI HMAT is using it as not const. UBIFS and XFS do not change the data (if I didn't miss anything).

Yes, that initiator_cmp() at drivers/acpi/hmat/hmat.c:526 is... interesting.

Basically, it wants to fill in a bitmap of all of the processor_pxm identifiers, so it avoids having a separate list traversal by setting bits in the compare function (which is guaranteed to visit each list element at least once).

It ends up setting each bit 2*log2(n) times (since there are an average of log2(n) compares per element and each compare sets two bits), but it makes the code smaller. And although it make the aggressive performance optimizer in me cringe, I have to agree this is not performance-critical code and so it's a reasonable thing to do.

I do note, however, that the list_sort is almost immediately followed by a list_for_each_entry() loop and maybe the bitmap computation could be folded in there. Basically start the loop with:

	unsigned int pxm = -1u;	/* Invalid sentinel value */
	list_for_each_entry(initiator, &initiators, node) {
		u32 value;

		if (initiator->processor_pxm != pxm) {
			pxm = initiator->processor_pxm;
			set_bit(pxm, p_nodes);
		} else if (!test_bit(pxm, p_nodes)) {
			continue;
		}

... but oh, whoops, that won't work. The "almost immediately" glosses over a second loop, so there are multiple passes over the initiators list, while we want the bitmap set up only once.

Cc: to Keith Busch <[email protected]>, who wrote that code. Keith, is there a way we could avoid the non-const priv parameter, just for the sake of code cleanliness in <list_sort.h>?

#5 lore raw

(Resend with corrected e-mail address and more thoughts.)

Quoted 3 lines · Andy Shevchenko

Hint: When you post Message-Id you may prefix them with
https://lore.kernel.org/r/ which makes search a bit more convenient and faster.

I just learned that https://marc.info/?i= also works, so
https://lore.kernel.org/r/[email protected]
https://marc.info/[email protected]

https://lore.kernel.org/r/[email protected]
https://marc.info/[email protected]

Quoted 4 lines

For the record, I have just checked users of list_sort() in regard to constify of priv parameter and only ACPI HMAT is using it as not const. UBIFS and XFS do not change the data (if I didn't miss anything).

Yes, that initiator_cmp() at drivers/acpi/hmat/hmat.c:526 is... interesting.

Basically, it wants to fill in a bitmap of all of the processor_pxm identifiers, so it avoids having a separate list traversal by setting bits in the compare function (which is guaranteed to visit each list element at least once).

It ends up setting each bit 2*log2(n) times (since there are an average of log2(n) compares per element and each compare sets two bits), but it makes the code smaller. And although it make the aggressive performance optimizer in me cringe, I have to agree this is not performance-critical code and so it's a reasonable thing to do.

I do note, however, that the list_sort is almost immediately followed by a list_for_each_entry() loop and maybe the bitmap computation could be folded in there. Basically start the loop with:

	unsigned int pxm = -1u;	/* Invalid sentinel value */
	list_for_each_entry(initiator, &initiators, node) {
		u32 value;

		if (initiator->processor_pxm != pxm) {
			pxm = initiator->processor_pxm;
			set_bit(pxm, p_nodes);
		} else if (!test_bit(pxm, p_nodes)) {
			continue;
		}

... but oh, whoops, that won't work. The "almost immediately" glosses over a second loop, so there are multiple passes over the initiators list, while we want the bitmap set up only once.

What we should probably do is just cast away the const in the cmp function. That's a strange thing to do, which is appropriate because the code is doing something strange.

It might be too subtle, but given the semantics guaranteed by list_sort, it would suffice to set only the bit corresponding to the *second* argument to cmp(), plus the bit corresponding to the first element of the input (not yet sorted) list.

Cc: to Keith Busch <[email protected]>, who wrote that code. Keith, is there a better way we could avoid the non-const priv parameter, just for the sake of code cleanliness in <list_sort.h>?