* [PATCH 1/5] arch/arc: unwind.c: replace swap function with built-in one
2019-03-30 16:37 [PATCH 0/5] simple sort swap function usage improvements Andrey Abramov
@ 2019-03-30 16:40 ` Andrey Abramov
2019-03-30 16:41 ` [PATCH 2/5] powerpc: module_[32|64].c: " Andrey Abramov
` (4 subsequent siblings)
5 siblings, 0 replies; 18+ messages in thread
From: Andrey Abramov @ 2019-03-30 16:40 UTC (permalink / raw)
To: vgupta, benh, paulus, mpe, tglx, mingo, bp, hpa, x86, mark,
jlbec, richard, dedekind1, adrian.hunter, gregkh, naveen.n.rao,
jpoimboe, Dave Chinner, darrick.wong, ard.biesheuvel,
George Spelvin, linux-snps-arc, Linux Kernel Mailing List,
linuxppc-dev, ocfs2-devel, linux-mtd, sfr
Cc: rppt, Morton Andrew, mhocko, malat, npiggin, yamada.masahiro,
jannh, jslaby, ge.changwei, jiangyiwen, piaojun, amir73il,
ashish.samant, yuehaibing, lchen, jiang.biao2, gustavo, peterz,
keescook, Rasmus Villemoes, Andy Shevchenko, kamalesh
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 <st5pub@yandex.ru>
---
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
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [PATCH 2/5] powerpc: module_[32|64].c: replace swap function with built-in one
2019-03-30 16:37 [PATCH 0/5] simple sort swap function usage improvements Andrey Abramov
2019-03-30 16:40 ` [PATCH 1/5] arch/arc: unwind.c: replace swap function with built-in one Andrey Abramov
@ 2019-03-30 16:41 ` Andrey Abramov
[not found] ` <87zhpaox14.fsf@concordia.ellerman.id.au>
2019-03-30 16:42 ` [PATCH 3/5] ocfs2: dir,refcounttree,xattr: replace swap functions " Andrey Abramov
` (3 subsequent siblings)
5 siblings, 1 reply; 18+ messages in thread
From: Andrey Abramov @ 2019-03-30 16:41 UTC (permalink / raw)
To: vgupta, benh, paulus, mpe, tglx, mingo, bp, hpa, x86, mark,
jlbec, richard, dedekind1, adrian.hunter, gregkh, naveen.n.rao,
jpoimboe, Dave Chinner, darrick.wong, ard.biesheuvel,
George Spelvin, linux-snps-arc, Linux Kernel Mailing List,
linuxppc-dev, ocfs2-devel, linux-mtd, sfr
Cc: rppt, Morton Andrew, mhocko, malat, npiggin, yamada.masahiro,
jannh, jslaby, ge.changwei, jiangyiwen, piaojun, amir73il,
ashish.samant, yuehaibing, lchen, jiang.biao2, gustavo, peterz,
keescook, Rasmus Villemoes, Andy Shevchenko, kamalesh
Replace relaswap with built-in one, because of relaswap
does a simple byte to byte swap.
Signed-off-by: Andrey Abramov <st5pub@yandex.ru>
---
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
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [PATCH 3/5] ocfs2: dir,refcounttree,xattr: replace swap functions with built-in one
2019-03-30 16:37 [PATCH 0/5] simple sort swap function usage improvements Andrey Abramov
2019-03-30 16:40 ` [PATCH 1/5] arch/arc: unwind.c: replace swap function with built-in one Andrey Abramov
2019-03-30 16:41 ` [PATCH 2/5] powerpc: module_[32|64].c: " Andrey Abramov
@ 2019-03-30 16:42 ` Andrey Abramov
2019-03-30 16:43 ` [PATCH 4/5] ubifs: find.c: replace swap function " Andrey Abramov
` (2 subsequent siblings)
5 siblings, 0 replies; 18+ messages in thread
From: Andrey Abramov @ 2019-03-30 16:42 UTC (permalink / raw)
To: vgupta, benh, paulus, mpe, tglx, mingo, bp, hpa, x86, mark,
jlbec, richard, dedekind1, adrian.hunter, gregkh, naveen.n.rao,
jpoimboe, Dave Chinner, darrick.wong, ard.biesheuvel,
George Spelvin, linux-snps-arc, Linux Kernel Mailing List,
linuxppc-dev, ocfs2-devel, linux-mtd, sfr
Cc: rppt, Morton Andrew, mhocko, malat, npiggin, yamada.masahiro,
jannh, jslaby, ge.changwei, jiangyiwen, piaojun, amir73il,
ashish.samant, yuehaibing, lchen, jiang.biao2, gustavo, peterz,
keescook, Rasmus Villemoes, Andy Shevchenko, kamalesh
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 <st5pub@yandex.ru>
---
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
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [PATCH 4/5] ubifs: find.c: replace swap function with built-in one
2019-03-30 16:37 [PATCH 0/5] simple sort swap function usage improvements Andrey Abramov
` (2 preceding siblings ...)
2019-03-30 16:42 ` [PATCH 3/5] ocfs2: dir,refcounttree,xattr: replace swap functions " Andrey Abramov
@ 2019-03-30 16:43 ` Andrey Abramov
2019-03-30 16:43 ` [PATCH 5/5] Lib: sort.h: replace int size with size_t size in the swap function Andrey Abramov
2019-03-30 17:16 ` [PATCH 0/5] simple sort swap function usage improvements George Spelvin
5 siblings, 0 replies; 18+ messages in thread
From: Andrey Abramov @ 2019-03-30 16:43 UTC (permalink / raw)
To: vgupta, benh, paulus, mpe, tglx, mingo, bp, hpa, x86, mark,
jlbec, richard, dedekind1, adrian.hunter, gregkh, naveen.n.rao,
jpoimboe, Dave Chinner, darrick.wong, ard.biesheuvel,
George Spelvin, linux-snps-arc, Linux Kernel Mailing List,
linuxppc-dev, ocfs2-devel, linux-mtd, sfr
Cc: rppt, Morton Andrew, mhocko, malat, npiggin, yamada.masahiro,
jannh, jslaby, ge.changwei, jiangyiwen, piaojun, amir73il,
ashish.samant, yuehaibing, lchen, jiang.biao2, gustavo, peterz,
keescook, Rasmus Villemoes, Andy Shevchenko, kamalesh
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 <st5pub@yandex.ru>
---
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
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [PATCH 5/5] Lib: sort.h: replace int size with size_t size in the swap function
2019-03-30 16:37 [PATCH 0/5] simple sort swap function usage improvements Andrey Abramov
` (3 preceding siblings ...)
2019-03-30 16:43 ` [PATCH 4/5] ubifs: find.c: replace swap function " Andrey Abramov
@ 2019-03-30 16:43 ` Andrey Abramov
[not found] ` <20190330183826.GB21828@kroah.com>
2019-03-30 17:16 ` [PATCH 0/5] simple sort swap function usage improvements George Spelvin
5 siblings, 1 reply; 18+ messages in thread
From: Andrey Abramov @ 2019-03-30 16:43 UTC (permalink / raw)
To: vgupta, benh, paulus, mpe, tglx, mingo, bp, hpa, x86, mark,
jlbec, richard, dedekind1, adrian.hunter, gregkh, naveen.n.rao,
jpoimboe, Dave Chinner, darrick.wong, ard.biesheuvel,
George Spelvin, linux-snps-arc, Linux Kernel Mailing List,
linuxppc-dev, ocfs2-devel, linux-mtd, sfr
Cc: rppt, Morton Andrew, mhocko, malat, npiggin, yamada.masahiro,
jannh, jslaby, ge.changwei, jiangyiwen, piaojun, amir73il,
ashish.samant, yuehaibing, lchen, jiang.biao2, gustavo, peterz,
keescook, Rasmus Villemoes, Andy Shevchenko, kamalesh
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 <st5pub@yandex.ru>
---
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
^ permalink raw reply related [flat|nested] 18+ messages in thread
* Re: [PATCH 0/5] simple sort swap function usage improvements
2019-03-30 16:37 [PATCH 0/5] simple sort swap function usage improvements Andrey Abramov
` (4 preceding siblings ...)
2019-03-30 16:43 ` [PATCH 5/5] Lib: sort.h: replace int size with size_t size in the swap function Andrey Abramov
@ 2019-03-30 17:16 ` George Spelvin
2019-04-01 21:08 ` Rasmus Villemoes
5 siblings, 1 reply; 18+ messages in thread
From: George Spelvin @ 2019-03-30 17:16 UTC (permalink / raw)
To: adrian.hunter, ard.biesheuvel, benh, bp, darrick.wong, dchinner,
dedekind1, gregkh, hpa, jlbec, jpoimboe, linux-kernel, linux-mtd,
linux-snps-arc, linuxppc-dev, lkml, mark, mingo, mpe,
naveen.n.rao, ocfs2-devel, paulus, richard, sfr, st5pub, tglx,
vgupta, x86
Cc: akpm, amir73il, andriy.shevchenko, ashish.samant, ge.changwei,
gustavo, jannh, jiang.biao2, jiangyiwen, jslaby, kamalesh,
keescook, lchen, linux, malat, mhocko, npiggin, peterz, piaojun,
rppt, yamada.masahiro, yuehaibing
Great work; that is indeed a logical follow-on.
Reviewed by: George Spelvin <lkml@sdf.org>
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.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH 0/5] simple sort swap function usage improvements
2019-03-30 17:16 ` [PATCH 0/5] simple sort swap function usage improvements George Spelvin
@ 2019-04-01 21:08 ` Rasmus Villemoes
0 siblings, 0 replies; 18+ messages in thread
From: Rasmus Villemoes @ 2019-04-01 21:08 UTC (permalink / raw)
To: George Spelvin; +Cc: Andrey Abramov, Andy Shevchenko, LKML
[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 <lkml@sdf.org>
>
> 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
^ permalink raw reply [flat|nested] 18+ messages in thread