This is the logical continuation of sort improvements by George Spelvin
"lib/sort & lib/list_sort: faster and smaller" series
(added to the linux-next really recently).
Patches from 1 to 4 replace simple swap functions with the built-in
(which is now much faster) and grouped by subsystem (after that only
3 files implement custom swap - arch/x86/kernel/unwind_orc.c,
kernel/jump_label.c and lib/extable.c).
Patch #5 replaces the int type with the size_t type of the size argument
in the swap function.
Andrey Abramov (5):
arch/arc: unwind.c: replace swap function with built-in one
powerpc: module_[32|64].c: replace swap function with built-in one
ocfs2: dir,refcounttree,xattr: replace swap functions with built-in
one
ubifs: find.c: replace swap function with built-in one
Lib: sort.h: replace int size with size_t size in the swap function
arch/arc/kernel/unwind.c | 20 ++------------------
arch/powerpc/kernel/module_32.c | 17 +----------------
arch/powerpc/kernel/module_64.c | 17 +----------------
arch/x86/kernel/unwind_orc.c | 2 +-
fs/ocfs2/dir.c | 13 +------------
fs/ocfs2/refcounttree.c | 13 +++----------
fs/ocfs2/xattr.c | 15 +++------------
fs/ubifs/find.c | 9 +--------
include/linux/sort.h | 2 +-
kernel/jump_label.c | 2 +-
lib/extable.c | 2 +-
lib/sort.c | 6 +++---
12 files changed, 19 insertions(+), 99 deletions(-)
--
2.21.0
Replace swap_eh_frame_hdr_table_entries with built-in one, because
swap_eh_frame_hdr_table_entries does a simple byte to byte swap.
Signed-off-by: Andrey Abramov <[email protected]>
---
arch/arc/kernel/unwind.c | 20 ++------------------
1 file changed, 2 insertions(+), 18 deletions(-)
diff --git a/arch/arc/kernel/unwind.c b/arch/arc/kernel/unwind.c
index 271e9fafa479..7610fe84afea 100644
--- a/arch/arc/kernel/unwind.c
+++ b/arch/arc/kernel/unwind.c
@@ -248,20 +248,6 @@ static int cmp_eh_frame_hdr_table_entries(const void *p1, const void *p2)
return (e1->start > e2->start) - (e1->start < e2->start);
}
-static void swap_eh_frame_hdr_table_entries(void *p1, void *p2, int size)
-{
- struct eh_frame_hdr_table_entry *e1 = p1;
- struct eh_frame_hdr_table_entry *e2 = p2;
- unsigned long v;
-
- v = e1->start;
- e1->start = e2->start;
- e2->start = v;
- v = e1->fde;
- e1->fde = e2->fde;
- e2->fde = v;
-}
-
static void init_unwind_hdr(struct unwind_table *table,
void *(*alloc) (unsigned long))
{
@@ -354,10 +340,8 @@ static void init_unwind_hdr(struct unwind_table *table,
}
WARN_ON(n != header->fde_count);
- sort(header->table,
- n,
- sizeof(*header->table),
- cmp_eh_frame_hdr_table_entries, swap_eh_frame_hdr_table_entries);
+ sort(header->table, n,
+ sizeof(*header->table), cmp_eh_frame_hdr_table_entries, NULL);
table->hdrsz = hdrSize;
smp_wmb();
--
2.21.0
Replace relaswap with built-in one, because of relaswap
does a simple byte to byte swap.
Signed-off-by: Andrey Abramov <[email protected]>
---
arch/powerpc/kernel/module_32.c | 17 +----------------
arch/powerpc/kernel/module_64.c | 17 +----------------
2 files changed, 2 insertions(+), 32 deletions(-)
diff --git a/arch/powerpc/kernel/module_32.c b/arch/powerpc/kernel/module_32.c
index 88d83771f462..c311e8575d10 100644
--- a/arch/powerpc/kernel/module_32.c
+++ b/arch/powerpc/kernel/module_32.c
@@ -79,21 +79,6 @@ static int relacmp(const void *_x, const void *_y)
return 0;
}
-static void relaswap(void *_x, void *_y, int size)
-{
- uint32_t *x, *y, tmp;
- int i;
-
- y = (uint32_t *)_x;
- x = (uint32_t *)_y;
-
- for (i = 0; i < sizeof(Elf32_Rela) / sizeof(uint32_t); i++) {
- tmp = x[i];
- x[i] = y[i];
- y[i] = tmp;
- }
-}
-
/* Get the potential trampolines size required of the init and
non-init sections */
static unsigned long get_plt_size(const Elf32_Ehdr *hdr,
@@ -130,7 +115,7 @@ static unsigned long get_plt_size(const Elf32_Ehdr *hdr,
*/
sort((void *)hdr + sechdrs[i].sh_offset,
sechdrs[i].sh_size / sizeof(Elf32_Rela),
- sizeof(Elf32_Rela), relacmp, relaswap);
+ sizeof(Elf32_Rela), relacmp, NULL);
ret += count_relocs((void *)hdr
+ sechdrs[i].sh_offset,
diff --git a/arch/powerpc/kernel/module_64.c b/arch/powerpc/kernel/module_64.c
index 8661eea78503..0c833d7f36f1 100644
--- a/arch/powerpc/kernel/module_64.c
+++ b/arch/powerpc/kernel/module_64.c
@@ -231,21 +231,6 @@ static int relacmp(const void *_x, const void *_y)
return 0;
}
-static void relaswap(void *_x, void *_y, int size)
-{
- uint64_t *x, *y, tmp;
- int i;
-
- y = (uint64_t *)_x;
- x = (uint64_t *)_y;
-
- for (i = 0; i < sizeof(Elf64_Rela) / sizeof(uint64_t); i++) {
- tmp = x[i];
- x[i] = y[i];
- y[i] = tmp;
- }
-}
-
/* Get size of potential trampolines required. */
static unsigned long get_stubs_size(const Elf64_Ehdr *hdr,
const Elf64_Shdr *sechdrs)
@@ -269,7 +254,7 @@ static unsigned long get_stubs_size(const Elf64_Ehdr *hdr,
*/
sort((void *)sechdrs[i].sh_addr,
sechdrs[i].sh_size / sizeof(Elf64_Rela),
- sizeof(Elf64_Rela), relacmp, relaswap);
+ sizeof(Elf64_Rela), relacmp, NULL);
relocs += count_relocs((void *)sechdrs[i].sh_addr,
sechdrs[i].sh_size
--
2.21.0
Replace dx_leaf_sort_swap, swap_refcount_rec and swap_xe functions
with built-in one, because they do only a simple byte to byte swap.
Signed-off-by: Andrey Abramov <[email protected]>
---
fs/ocfs2/dir.c | 13 +------------
fs/ocfs2/refcounttree.c | 13 +++----------
fs/ocfs2/xattr.c | 15 +++------------
3 files changed, 7 insertions(+), 34 deletions(-)
diff --git a/fs/ocfs2/dir.c b/fs/ocfs2/dir.c
index c121abbdfc7d..4b86b181df0a 100644
--- a/fs/ocfs2/dir.c
+++ b/fs/ocfs2/dir.c
@@ -3529,16 +3529,6 @@ static int dx_leaf_sort_cmp(const void *a, const void *b)
return 0;
}
-static void dx_leaf_sort_swap(void *a, void *b, int size)
-{
- struct ocfs2_dx_entry *entry1 = a;
- struct ocfs2_dx_entry *entry2 = b;
-
- BUG_ON(size != sizeof(*entry1));
-
- swap(*entry1, *entry2);
-}
-
static int ocfs2_dx_leaf_same_major(struct ocfs2_dx_leaf *dx_leaf)
{
struct ocfs2_dx_entry_list *dl_list = &dx_leaf->dl_list;
@@ -3799,8 +3789,7 @@ static int ocfs2_dx_dir_rebalance(struct ocfs2_super *osb, struct inode *dir,
* This block is changing anyway, so we can sort it in place.
*/
sort(dx_leaf->dl_list.de_entries, num_used,
- sizeof(struct ocfs2_dx_entry), dx_leaf_sort_cmp,
- dx_leaf_sort_swap);
+ sizeof(struct ocfs2_dx_entry), dx_leaf_sort_cmp, NULL);
ocfs2_journal_dirty(handle, dx_leaf_bh);
diff --git a/fs/ocfs2/refcounttree.c b/fs/ocfs2/refcounttree.c
index 1dc9a08e8bdc..7bbc94d23a0c 100644
--- a/fs/ocfs2/refcounttree.c
+++ b/fs/ocfs2/refcounttree.c
@@ -1400,13 +1400,6 @@ static int cmp_refcount_rec_by_cpos(const void *a, const void *b)
return 0;
}
-static void swap_refcount_rec(void *a, void *b, int size)
-{
- struct ocfs2_refcount_rec *l = a, *r = b;
-
- swap(*l, *r);
-}
-
/*
* The refcount cpos are ordered by their 64bit cpos,
* But we will use the low 32 bit to be the e_cpos in the b-tree.
@@ -1482,7 +1475,7 @@ static int ocfs2_divide_leaf_refcount_block(struct buffer_head *ref_leaf_bh,
*/
sort(&rl->rl_recs, le16_to_cpu(rl->rl_used),
sizeof(struct ocfs2_refcount_rec),
- cmp_refcount_rec_by_low_cpos, swap_refcount_rec);
+ cmp_refcount_rec_by_low_cpos, NULL);
ret = ocfs2_find_refcount_split_pos(rl, &cpos, &split_index);
if (ret) {
@@ -1507,11 +1500,11 @@ static int ocfs2_divide_leaf_refcount_block(struct buffer_head *ref_leaf_bh,
sort(&rl->rl_recs, le16_to_cpu(rl->rl_used),
sizeof(struct ocfs2_refcount_rec),
- cmp_refcount_rec_by_cpos, swap_refcount_rec);
+ cmp_refcount_rec_by_cpos, NULL);
sort(&new_rl->rl_recs, le16_to_cpu(new_rl->rl_used),
sizeof(struct ocfs2_refcount_rec),
- cmp_refcount_rec_by_cpos, swap_refcount_rec);
+ cmp_refcount_rec_by_cpos, NULL);
*split_cpos = cpos;
return 0;
diff --git a/fs/ocfs2/xattr.c b/fs/ocfs2/xattr.c
index 3a24ce3deb01..b3e6f42baf78 100644
--- a/fs/ocfs2/xattr.c
+++ b/fs/ocfs2/xattr.c
@@ -4175,15 +4175,6 @@ static int cmp_xe(const void *a, const void *b)
return 0;
}
-static void swap_xe(void *a, void *b, int size)
-{
- struct ocfs2_xattr_entry *l = a, *r = b, tmp;
-
- tmp = *l;
- memcpy(l, r, sizeof(struct ocfs2_xattr_entry));
- memcpy(r, &tmp, sizeof(struct ocfs2_xattr_entry));
-}
-
/*
* When the ocfs2_xattr_block is filled up, new bucket will be created
* and all the xattr entries will be moved to the new bucket.
@@ -4249,7 +4240,7 @@ static void ocfs2_cp_xattr_block_to_bucket(struct inode *inode,
trace_ocfs2_cp_xattr_block_to_bucket_end(offset, size, off_change);
sort(target + offset, count, sizeof(struct ocfs2_xattr_entry),
- cmp_xe, swap_xe);
+ cmp_xe, NULL);
}
/*
@@ -4444,7 +4435,7 @@ static int ocfs2_defrag_xattr_bucket(struct inode *inode,
*/
sort(entries, le16_to_cpu(xh->xh_count),
sizeof(struct ocfs2_xattr_entry),
- cmp_xe_offset, swap_xe);
+ cmp_xe_offset, NULL);
/* Move all name/values to the end of the bucket. */
xe = xh->xh_entries;
@@ -4486,7 +4477,7 @@ static int ocfs2_defrag_xattr_bucket(struct inode *inode,
/* sort the entries by their name_hash. */
sort(entries, le16_to_cpu(xh->xh_count),
sizeof(struct ocfs2_xattr_entry),
- cmp_xe, swap_xe);
+ cmp_xe, NULL);
buf = bucket_buf;
for (i = 0; i < bucket->bu_blocks; i++, buf += blocksize)
--
2.21.0
Replace int type with size_t type of the size argument
in the swap function, also affect all its dependencies.
Signed-off-by: Andrey Abramov <[email protected]>
---
arch/x86/kernel/unwind_orc.c | 2 +-
include/linux/sort.h | 2 +-
kernel/jump_label.c | 2 +-
lib/extable.c | 2 +-
lib/sort.c | 6 +++---
5 files changed, 7 insertions(+), 7 deletions(-)
diff --git a/arch/x86/kernel/unwind_orc.c b/arch/x86/kernel/unwind_orc.c
index 89be1be1790c..1078c287198c 100644
--- a/arch/x86/kernel/unwind_orc.c
+++ b/arch/x86/kernel/unwind_orc.c
@@ -176,7 +176,7 @@ static struct orc_entry *orc_find(unsigned long ip)
return orc_ftrace_find(ip);
}
-static void orc_sort_swap(void *_a, void *_b, int size)
+static void orc_sort_swap(void *_a, void *_b, size_t size)
{
struct orc_entry *orc_a, *orc_b;
struct orc_entry orc_tmp;
diff --git a/include/linux/sort.h b/include/linux/sort.h
index 2b99a5dd073d..aea39d552ff7 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -6,6 +6,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
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index bad96b476eb6..340b788571fb 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -45,7 +45,7 @@ static int jump_label_cmp(const void *a, const void *b)
return 0;
}
-static void jump_label_swap(void *a, void *b, int size)
+static void jump_label_swap(void *a, void *b, size_t size)
{
long delta = (unsigned long)a - (unsigned long)b;
struct jump_entry *jea = a;
diff --git a/lib/extable.c b/lib/extable.c
index f54996fdd0b8..db2888342cd7 100644
--- a/lib/extable.c
+++ b/lib/extable.c
@@ -28,7 +28,7 @@ static inline unsigned long ex_to_insn(const struct exception_table_entry *x)
#ifndef ARCH_HAS_RELATIVE_EXTABLE
#define swap_ex NULL
#else
-static void swap_ex(void *a, void *b, int size)
+static void swap_ex(void *a, void *b, size_t size)
{
struct exception_table_entry *x = a, *y = b, tmp;
int delta = b - a;
diff --git a/lib/sort.c b/lib/sort.c
index 50855ea8c262..60fbbc29104a 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -114,7 +114,7 @@ static void swap_bytes(void *a, void *b, size_t n)
} while (n);
}
-typedef void (*swap_func_t)(void *a, void *b, int size);
+typedef void (*swap_func_t)(void *a, void *b, size_t size);
/*
* The values are arbitrary as long as they can't be confused with
@@ -138,7 +138,7 @@ static void do_swap(void *a, void *b, size_t size, swap_func_t swap_func)
else if (swap_func == SWAP_BYTES)
swap_bytes(a, b, size);
else
- swap_func(a, b, (int)size);
+ swap_func(a, b, size);
}
/**
@@ -187,7 +187,7 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size)
*/
void sort(void *base, size_t num, size_t size,
int (*cmp_func)(const void *, const void *),
- void (*swap_func)(void *, void *, int size))
+ void (*swap_func)(void *, void *, size_t size))
{
/* pre-scale counters for performance */
size_t n = num * size, a = (num/2) * size;
--
2.21.0
Replace swap_dirty_idx function with built-in one,
because swap_dirty_idx does only a simple byte to byte swap.
Signed-off-by: Andrey Abramov <[email protected]>
---
fs/ubifs/find.c | 9 +--------
1 file changed, 1 insertion(+), 8 deletions(-)
diff --git a/fs/ubifs/find.c b/fs/ubifs/find.c
index f9646835b026..5deaae7fcead 100644
--- a/fs/ubifs/find.c
+++ b/fs/ubifs/find.c
@@ -747,12 +747,6 @@ static int cmp_dirty_idx(const struct ubifs_lprops **a,
return lpa->dirty + lpa->free - lpb->dirty - lpb->free;
}
-static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b,
- int size)
-{
- swap(*a, *b);
-}
-
/**
* ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
* @c: the UBIFS file-system description object
@@ -772,8 +766,7 @@ int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)
sizeof(void *) * c->dirty_idx.cnt);
/* Sort it so that the dirtiest is now at the end */
sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),
- (int (*)(const void *, const void *))cmp_dirty_idx,
- (void (*)(void *, void *, int))swap_dirty_idx);
+ (int (*)(const void *, const void *))cmp_dirty_idx, NULL);
dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt);
if (c->dirty_idx.cnt)
dbg_find("dirtiest index LEB is %d with dirty %d and free %d",
--
2.21.0
Great work; that is indeed a logical follow-on.
Reviewed by: George Spelvin <[email protected]>
I you feel even more ambitious, you could try impementing Rasmus
Villemoes' idea of having generic *compare* functions. (It's on
my to-do list, but I haven't made meaningful progress yet, and I'm
happy to pawn it off.)
A significant fraction of the time, the sort key is a 4- or 8-byte
integer field in a structure at a small offset from the base or
list_head.
A function pointer < 4096 could be interpreted as encoding:
- Key size (1 bit)
- Key signedness (1 bit)
- Sort direction (1 bit)
- Offset (9 bits; +/-256 words = +/-1024 bytes, or 0..511 words from start)
With the correct level of preprocessor hackery,
SIMPLE_CMP_ASCENDING(struct type, key_field)
SIMPLE_LIST_CMP_ASCENDING(struct type, list_field, key_field)
SIMPLE_CMP_DESCENDING(struct type, key_field)
SIMPLE_LIST_CMP_DESCENDING(struct type, list_field, key_field)
could encode all that and cause a compile-time error if the key
is the wrong type or the offset is out of range.
On Sat, 30 Mar 2019 at 19:38:26 +0100 greh k-h wrote;
> On Sat, Mar 30, 2019 at 07:43:53PM +0300, Andrey Abramov wrote:
>> Replace int type with size_t type of the size argument
>> in the swap function, also affect all its dependencies.
>
> This says _what_ the patch does, but it gives no clue as to _why_ you
> are doing this. Neither did your 0/5 patch :(
>
> Why make this change? Nothing afterward depends on it from what I can
> tell, so why is it needed?
It's just a minor cleanup, making things less surprising for future
programmers. As I wrote in a comment in my patches, using a signed type
for an object size is definitely a wart; ever since C89 it's expected
you'd use size_t for the purpose.
The connection is that it's a natural consequence of doing a pass over
every call site.
You're right it could be dropped from the series harmlessly, but it
comes from the same work. But it's all of *three* call sites in the kernel
which are affected. Surely that's not an unreasonable amount of churn
to clean up a wart?
On Sat, Mar 30, 2019 at 08:15:49PM +0000, George Spelvin wrote:
> On Sat, 30 Mar 2019 at 19:38:26 +0100 greh k-h wrote;
> > On Sat, Mar 30, 2019 at 07:43:53PM +0300, Andrey Abramov wrote:
> >> Replace int type with size_t type of the size argument
> >> in the swap function, also affect all its dependencies.
> >
> > This says _what_ the patch does, but it gives no clue as to _why_ you
> > are doing this. Neither did your 0/5 patch :(
> >
> > Why make this change? Nothing afterward depends on it from what I can
> > tell, so why is it needed?
>
> It's just a minor cleanup, making things less surprising for future
> programmers. As I wrote in a comment in my patches, using a signed type
> for an object size is definitely a wart; ever since C89 it's expected
> you'd use size_t for the purpose.
You did not say that in this commit log :)
> The connection is that it's a natural consequence of doing a pass over
> every call site.
>
> You're right it could be dropped from the series harmlessly, but it
> comes from the same work. But it's all of *three* call sites in the kernel
> which are affected. Surely that's not an unreasonable amount of churn
> to clean up a wart?
If you think it is a wart, wonderful, yes, let's fix it up. But again,
a changelog comment should explain _why_ a commit is needed, not _what_
it does, as we can see from the diff itself exactly what the commit
does.
thanks,
greg k-h
On Sat, 30 Mar 2019 at 21:24:18 +0100, Greg KH wrote:
> On Sat, Mar 30, 2019 at 08:15:49PM +0000, George Spelvin wrote:
>> On Sat, 30 Mar 2019 at 19:38:26 +0100 Greh KH wrote;
>> > On Sat, Mar 30, 2019 at 07:43:53PM +0300, Andrey Abramov wrote:
>>>> Replace int type with size_t type of the size argument
>>>> in the swap function, also affect all its dependencies.
>>>
>>> This says _what_ the patch does, but it gives no clue as to _why_ you
>>> are doing this. Neither did your 0/5 patch :(
>>>
>>> Why make this change? Nothing afterward depends on it from what I can
>>> tell, so why is it needed?
>>
>> It's just a minor cleanup, making things less surprising for future
>> programmers. As I wrote in a comment in my patches, using a signed type
>> for an object size is definitely a wart; ever since C89 it's expected
>> you'd use size_t for the purpose.
>
> You did not say that in this commit log :)
Just to clarify: Not My Patch. I approve, but it's Andrey's patch.
Your point is taken that the commit message needs to be improved
to explain why. I just answered because it wasn't clear how much
of your question was rhetorical.
> If you think it is a wart, wonderful, yes, let's fix it up. But again,
> a changelog comment should explain _why_ a commit is needed, not _what_
> it does, as we can see from the diff itself exactly what the commit
> does.
It was so obvious to me that I didn't question it, but you have a
good point and I'm sure Andrey can clarify. Thanks for the attention!
30.03.2019, 23:17, "George Spelvin" <[email protected]>:
> On Sat, 30 Mar 2019 at 19:38:26 +0100 greh k-h wrote;
>> On Sat, Mar 30, 2019 at 07:43:53PM +0300, Andrey Abramov wrote:
>>> Replace int type with size_t type of the size argument
>>> in the swap function, also affect all its dependencies.
>>
>> This says _what_ the patch does, but it gives no clue as to _why_ you
>> are doing this. Neither did your 0/5 patch :(
>>
>> Why make this change? Nothing afterward depends on it from what I can
>> tell, so why is it needed?
>
> It's just a minor cleanup, making things less surprising for future
> programmers. As I wrote in a comment in my patches, using a signed type
> for an object size is definitely a wart; ever since C89 it's expected
> you'd use size_t for the purpose.
>
> The connection is that it's a natural consequence of doing a pass over
> every call site.
>
> You're right it could be dropped from the series harmlessly, but it
> comes from the same work. But it's all of *three* call sites in the kernel
> which are affected. Surely that's not an unreasonable amount of churn
> to clean up a wart?
George Spelvin is absolutely right: "It's just a minor cleanup, making things less surprising for future programmers."
31.03.2019, 00:51, "George Spelvin" <[email protected]>:
> It was so obvious to me that I didn't question it, but you have a
> good point and I'm sure Andrey can clarify. Thanks for the attention!
I thought that it is obvious enough (argument called "size" should be of type size_t in the 90% of cases).
Should I resend this patch with better explanation "why"?
--
With Best Regards,
Andrey Abramov
On Sun, Mar 31, 2019 at 10:00:18AM +0300, Andrey Abramov wrote:
> 30.03.2019, 23:17, "George Spelvin" <[email protected]>:
> > On Sat, 30 Mar 2019 at 19:38:26 +0100 greh k-h wrote;
> >> ?On Sat, Mar 30, 2019 at 07:43:53PM +0300, Andrey Abramov wrote:
> >>> ?Replace int type with size_t type of the size argument
> >>> ?in the swap function, also affect all its dependencies.
> >>
> >> ?This says _what_ the patch does, but it gives no clue as to _why_ you
> >> ?are doing this. Neither did your 0/5 patch :(
> >>
> >> ?Why make this change? Nothing afterward depends on it from what I can
> >> ?tell, so why is it needed?
> >
> > It's just a minor cleanup, making things less surprising for future
> > programmers. As I wrote in a comment in my patches, using a signed type
> > for an object size is definitely a wart; ever since C89 it's expected
> > you'd use size_t for the purpose.
> >
> > The connection is that it's a natural consequence of doing a pass over
> > every call site.
> >
> > You're right it could be dropped from the series harmlessly, but it
> > comes from the same work. But it's all of *three* call sites in the kernel
> > which are affected. Surely that's not an unreasonable amount of churn
> > to clean up a wart?
>
> George Spelvin is absolutely right: "It's just a minor cleanup, making
> things less surprising for future programmers."
Then document it.
> 31.03.2019, 00:51, "George Spelvin" <[email protected]>:
> > It was so obvious to me that I didn't question it, but you have a
> > good point and I'm sure Andrey can clarify. Thanks for the attention!
>
> I thought that it is obvious enough (argument called "size" should be
> of type size_t in the 90% of cases). Should I resend this patch with
> better explanation "why"?
Yes, "int" is a very nice variable for "size", you need to explain why
it is better to use size_t here please.
thanks,
greg k-h
From: [email protected]
> Sent: 31 March 2019 11:54
...
> Yes, "int" is a very nice variable for "size", you need to explain why
> it is better to use size_t here please.
Actually, on x86_64 you probably want 'unsigned int' to avoid the
compiler having to generate a sign-extending register move if the
value is ever used in a 64bit expression (eg an address calculation).
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
On 4/1/19 7:46 AM, David Laight wrote:
> From: [email protected]
>> Sent: 31 March 2019 11:54
> ...
>> Yes, "int" is a very nice variable for "size", you need to explain why
>> it is better to use size_t here please.
> Actually, on x86_64 you probably want 'unsigned int' to avoid the
> compiler having to generate a sign-extending register move if the
> value is ever used in a 64bit expression (eg an address calculation).
Thats likely true for non x86 arches too (for certain on ARC). That is also the
reason I dislike "bool", despite its "software engineering" benefits. Per ARC ABI
(and likely others too) it is signed 8 bits and any use thereof, requires the
compiler to generate an additional EXTB instruction to promote to 32-bit int with
sign extension before using the value.
-Vineet
01.04.2019, 21:02, "Vineet Gupta" <[email protected]>:
> On 4/1/19 7:46 AM, David Laight wrote:
>> From: [email protected]
>>> Sent: 31 March 2019 11:54
>> ...
>>> Yes, "int" is a very nice variable for "size", you need to explain why
>>> it is better to use size_t here please.
>> Actually, on x86_64 you probably want 'unsigned int' to avoid the
>> compiler having to generate a sign-extending register move if the
>> value is ever used in a 64bit expression (eg an address calculation).
>
> Thats likely true for non x86 arches too (for certain on ARC). That is also the
> reason I dislike "bool", despite its "software engineering" benefits. Per ARC ABI
> (and likely others too) it is signed 8 bits and any use thereof, requires the
> compiler to generate an additional EXTB instruction to promote to 32-bit int with
> sign extension before using the value.
>
> -Vineet
George Spelvin wrote "So how about *deleting* the parameter instead?
That simplifies everything.", and he is right,
so I am just going to completely remove it.
Any objections?
--
With Best Regards,
Andrey Abramov
On 4/1/19 11:14 AM, Andrey Abramov wrote:
> George Spelvin wrote "So how about *deleting* the parameter instead?
> That simplifies everything.", and he is right,
> so I am just going to completely remove it.
>
> Any objections?
LGTM.
[trimming cc list]
On 30/03/2019 18.16, George Spelvin wrote:
> Great work; that is indeed a logical follow-on.
>
> Reviewed by: George Spelvin <[email protected]>
>
> I you feel even more ambitious, you could try impementing Rasmus
> Villemoes' idea of having generic *compare* functions. (It's on
> my to-do list, but I haven't made meaningful progress yet, and I'm
> happy to pawn it off.)
>
> A significant fraction of the time, the sort key is a 4- or 8-byte
> integer field in a structure at a small offset from the base or
> list_head.
>
> A function pointer < 4096 could be interpreted as encoding:
> - Key size (1 bit)
> - Key signedness (1 bit)
> - Sort direction (1 bit)
> - Offset (9 bits; +/-256 words = +/-1024 bytes, or 0..511 words from start)
>
> With the correct level of preprocessor hackery,
> SIMPLE_CMP_ASCENDING(struct type, key_field)
> SIMPLE_LIST_CMP_ASCENDING(struct type, list_field, key_field)
> SIMPLE_CMP_DESCENDING(struct type, key_field)
> SIMPLE_LIST_CMP_DESCENDING(struct type, list_field, key_field)
So, first of all, I don't think there's any reason to do the descending
thing, at least until there's a (or better, a handful) of potential users.
Second, I don't think the user should be concerned with the encoding,
and I'd avoid the shouting, even if it happens to be implemented as
macros because of the need to do type inspection. So I'd do
sort_by_key(base, count, key)
where base must be of type "struct foo *" and key must be the name of a
member of struct foo. [I think most would be just fine with the default
swap - if not, that could be added, or we could add another macro also
taking a swap argument.] So this would expand to
sort(base, count, sizeof(*base), the-encoding-stuff, NULL)
Similarly, for list_sort, I'd do
list_sort_by_key(head, type, list-member, key-member)
which would expand to
list_sort((long)offset_diff, head, encode typeof(type->key));
The latter is the easier one to do because we have the context argument
that goes unused in the case of a trivial comparison function. The
former would be just as easy if we decide that we only care about the
majority which are happy with the default swap function, because in that
case the offsetof(type, key) could go in the swap argument, and the cmp
argument would just be the same as for list_sort. Having the two share
the logic for "key is one of the types we support, or build bug" would
be good. Perhaps the two tiny list_sort.h and sort.h headers should be
squashed.
Rasmus
01.04.2019, 13:11, "Michael Ellerman" <[email protected]>:
> This looks OK. It's a bit of a pity to replace the 8-byte-at-a-time copy
> with a byte-at-a-time copy, but I suspect it's insignificant compared to
> the overhead of calling the comparison and swap functions.
>
> And we could always add a generic 8-byte-at-a-time swap function if it's
> a bottleneck.
I am sorry, I forgot to quickly comment on your letter.
Now (after George Spelvin's patches) the generic swap is able
to use u64 or u32 if the alignment and size are divisible
by 4 or 8, so we lose nothing here.