Skip to contentSkip to conversation

lib/sort: adjust types

PATCH In review Jan Beulich 2 participants 3 messages Dec 22, 2020 – Dec 23, 2020

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib/sort: adjust types

First and foremost do away with the use of plain int for sizes or size- derived values. Use size_t, despite this requiring some adjustment to the logic. Also replace u32 by uint32_t.

While not directly related also drop a leftover #ifdef from x86's swap_ex - this was needed only back when 32-bit Xen was still a thing.

xen/arch/x86/extable.c +1 -3
@@ -37,8 +37,7 @@ static int init_or_livepatch cmp_ex(cons
 	return 0;
 }
 
-#ifndef swap_ex
-static void init_or_livepatch swap_ex(void *a, void *b, int size)
+static void init_or_livepatch swap_ex(void *a, void *b, size_t size)
 {
 	struct exception_table_entry *l = a, *r = b, tmp;
 	long delta = b - a;
@@ -49,7 +48,6 @@ static void init_or_livepatch swap_ex(vo
 	r->addr = tmp.addr - delta;
 	r->cont = tmp.cont - delta;
 }
-#endif
 
 void init_or_livepatch sort_exception_table(struct exception_table_entry *start,
                                  const struct exception_table_entry *stop)
xen/include/xen/sort.h +1 -1
@@ -5,6 +5,6 @@
 
 void sort(void *base, size_t num, size_t size,
           int (*cmp)(const void *, const void *),
-          void (*swap)(void *, void *, int));
+          void (*swap)(void *, void *, size_t));
 
 #endif /* __XEN_SORT_H__ */
xen/lib/sort.c +12 -10
@@ -6,14 +6,15 @@
 
 #include <xen/types.h>
 
-static void u32_swap(void *a, void *b, int size)
+static void u32_swap(void *a, void *b, size_t size)
 {
-    u32 t = *(u32 *)a;
-    *(u32 *)a = *(u32 *)b;
-    *(u32 *)b = t;
+    uint32_t t = *(uint32_t *)a;
+
+    *(uint32_t *)a = *(uint32_t *)b;
+    *(uint32_t *)b = t;
 }
 
-static void generic_swap(void *a, void *b, int size)
+static void generic_swap(void *a, void *b, size_t size)
 {
     char t;
 
@@ -43,18 +44,18 @@ static void generic_swap(void *a, void *
 
 void sort(void *base, size_t num, size_t size,
           int (*cmp)(const void *, const void *),
-          void (*swap)(void *, void *, int size))
+          void (*swap)(void *, void *, size_t size))
 {
     /* pre-scale counters for performance */
-    int i = (num / 2 - 1) * size, n = num * size, c, r;
+    size_t i = (num / 2) * size, n = num * size, c, r;
 
     if ( !swap )
         swap = (size == 4 ? u32_swap : generic_swap);
 
     /* heapify */
-    for ( ; i >= 0; i -= size )
+    while ( i > 0 )
     {
-        for ( r = i; r * 2 + size < n; r  = c )
+        for ( r = i -= size; r * 2 + size < n; r  = c )
         {
             c = r * 2 + size;
             if ( (c < n - size) && (cmp(base + c, base + c + size) < 0) )
@@ -66,8 +67,9 @@ void sort(void *base, size_t num, size_t
     }
 
     /* sort */
-    for ( i = n - size; i >= 0; i -= size )
+    for ( i = n; i > 0; )
     {
+        i -= size;
         swap(base, base + i, size);
         for ( r = 0; r * 2 + size < i; r = c )
         {
Acked-by on v1 1/1
#1 lore raw
Quoted 8 lines · Jan Beulich

First and foremost do away with the use of plain int for sizes or size- derived values. Use size_t, despite this requiring some adjustment to the logic. Also replace u32 by uint32_t.

While not directly related also drop a leftover #ifdef from x86's swap_ex - this was needed only back when 32-bit Xen was still a thing.

Its a shame that we've got exactly two users of sort() (ought to be named heapsort), one in arm/io.c which ought to be replaced with a generalised version of my sorted-array logic for VMCS load/save lists, and the other in x86's sort_exception_table() which ought to become build-time logic.

Quoted 64 lines
xen/arch/x86/extable.c +1 -3
@@ -37,8 +37,7 @@ static int init_or_livepatch cmp_ex(cons
 	return 0;
 }
 
-#ifndef swap_ex
-static void init_or_livepatch swap_ex(void *a, void *b, int size)
+static void init_or_livepatch swap_ex(void *a, void *b, size_t size)
 {
 	struct exception_table_entry *l = a, *r = b, tmp;
 	long delta = b - a;
@@ -49,7 +48,6 @@ static void init_or_livepatch swap_ex(vo
 	r->addr = tmp.addr - delta;
 	r->cont = tmp.cont - delta;
 }
-#endif
 
 void init_or_livepatch sort_exception_table(struct exception_table_entry *start,
                                  const struct exception_table_entry *stop)
xen/include/xen/sort.h +1 -1
@@ -5,6 +5,6 @@
 
 void sort(void *base, size_t num, size_t size,
           int (*cmp)(const void *, const void *),
-          void (*swap)(void *, void *, int));
+          void (*swap)(void *, void *, size_t));
 
 #endif /* __XEN_SORT_H__ */
xen/lib/sort.c +8 -7
@@ -6,14 +6,15 @@
 
 #include <xen/types.h>
 
-static void u32_swap(void *a, void *b, int size)
+static void u32_swap(void *a, void *b, size_t size)
 {
-    u32 t = *(u32 *)a;
-    *(u32 *)a = *(u32 *)b;
-    *(u32 *)b = t;
+    uint32_t t = *(uint32_t *)a;
+
+    *(uint32_t *)a = *(uint32_t *)b;
+    *(uint32_t *)b = t;
 }
 
-static void generic_swap(void *a, void *b, int size)
+static void generic_swap(void *a, void *b, size_t size)
 {
     char t;
 
@@ -43,18 +44,18 @@ static void generic_swap(void *a, void *
 
 void sort(void *base, size_t num, size_t size,
           int (*cmp)(const void *, const void *),
-          void (*swap)(void *, void *, int size))
+          void (*swap)(void *, void *, size_t size))
 {
     /* pre-scale counters for performance */
-    int i = (num / 2 - 1) * size, n = num * size, c, r;
+    size_t i = (num / 2) * size, n = num * size, c, r;

xen/lib/sort.c static void generic_swap(void *a, void * · line 58

Quoted 10 lines
xen/lib/sort.c +2 -2
 
     if ( !swap )
         swap = (size == 4 ? u32_swap : generic_swap);
 
     /* heapify */
-    for ( ; i >= 0; i -= size )
+    while ( i > 0 )
     {
-        for ( r = i; r * 2 + size < n; r  = c )
+        for ( r = i -= size; r * 2 + size < n; r  = c )

Aren't some compilers going to complain at the lack of brackets for this setup of r?

Also as you're editing the line, the "r  = c" part should lose one space.

~Andrew

Quoted 14 lines
xen/lib/sort.c +2 -1
         {
             c = r * 2 + size;
             if ( (c < n - size) && (cmp(base + c, base + c + size) < 0) )
@@ -66,8 +67,9 @@ void sort(void *base, size_t num, size_t
     }
 
     /* sort */
-    for ( i = n - size; i >= 0; i -= size )
+    for ( i = n; i > 0; )
     {
+        i -= size;
         swap(base, base + i, size);
         for ( r = 0; r * 2 + size < i; r = c )
         {
#2 lore raw
Quoted 11 lines · Andrew Cooper
Quoted 8 lines · Jan Beulich

First and foremost do away with the use of plain int for sizes or size- derived values. Use size_t, despite this requiring some adjustment to the logic. Also replace u32 by uint32_t.

While not directly related also drop a leftover #ifdef from x86's swap_ex - this was needed only back when 32-bit Xen was still a thing.

Thanks.

Quoted 37 lines
Quoted 37 lines
xen/lib/sort.c +8 -7
@@ -6,14 +6,15 @@
 
 #include <xen/types.h>
 
-static void u32_swap(void *a, void *b, int size)
+static void u32_swap(void *a, void *b, size_t size)
 {
-    u32 t = *(u32 *)a;
-    *(u32 *)a = *(u32 *)b;
-    *(u32 *)b = t;
+    uint32_t t = *(uint32_t *)a;
+
+    *(uint32_t *)a = *(uint32_t *)b;
+    *(uint32_t *)b = t;
 }
 
-static void generic_swap(void *a, void *b, int size)
+static void generic_swap(void *a, void *b, size_t size)
 {
     char t;
 
@@ -43,18 +44,18 @@ static void generic_swap(void *a, void *
 
 void sort(void *base, size_t num, size_t size,
           int (*cmp)(const void *, const void *),
-          void (*swap)(void *, void *, int size))
+          void (*swap)(void *, void *, size_t size))
 {
     /* pre-scale counters for performance */
-    int i = (num / 2 - 1) * size, n = num * size, c, r;
+    size_t i = (num / 2) * size, n = num * size, c, r;
 
     if ( !swap )
         swap = (size == 4 ? u32_swap : generic_swap);
 
Quoted 9 lines

xen/lib/sort.c static void generic_swap(void *a, void * · line 58

Quoted 6 lines
xen/lib/sort.c +2 -2
     /* heapify */
-    for ( ; i >= 0; i -= size )
+    while ( i > 0 )
     {
-        for ( r = i; r * 2 + size < n; r  = c )
+        for ( r = i -= size; r * 2 + size < n; r  = c )

Aren't some compilers going to complain at the lack of brackets for this setup of r?

I've never seen any warning on this type of construct. It's no different from "a = b = c;".

Quoted 1 line

Also as you're editing the line, the "r  = c" part should lose one space.

Oh, indeed.

Jan