[RFC PATCH 0/4] kstrdup optimization

[RFC PATCH 0/4] kstrdup optimization

[Andrzej Hajda]

Hi,

kstrdup if often used to duplicate strings where neither source neither
destination will be ever modified. In such case we can just reuse the source
instead of duplicating it. The problem is that we must be sure that
the source is non-modifiable and its life-time is long enough.

I suspect the good candidates for such strings are strings located in kernel
.rodata section, they cannot be modifed because the section is read-only and
their life-time is equal to kernel life-time.

This small patchset proposes alternative version of kstrdup - kstrdup_const,
which returns source string if it is located in .rodata otherwise it fallbacks
to kstrdup.
To verify if the source is in .rodata function checks if the address is between
sentinels __start_rodata, __end_rodata, I think it is OK, but maybe sombebody
with deeper knowledge can say if it is OK for all supported architectures and
configuration options.

The main patch is accompanied by three patches constifying kstrdup for cases
where situtation described above happens frequently.

The patchset is based on next-20141226.

As I have tested it on mobile platform (exynos4210-trats) it saves above 2600
string duplications. Below simple stats about the most frequent duplications:
Count String
  880 power
  874 subsystem
  130 device
  126 parameters
   61 iommu_group
   40 driver
   28 bdi
   28 none
   25 sclk_mpll
   23 sclk_usbphy0
   23 sclk_hdmi24m
   23 xusbxti
   22 sclk_vpll
   22 sclk_epll
   22 xxti
   20 sclk_hdmiphy
   11 aclk100

Regards
Andrzej


Andrzej Hajda (4):
  mm/util: add kstrdup_const
  kernfs: use kstrdup_const for node name allocation
  clk: use kstrdup_const for clock name allocations
  mm/slab: use kstrdup_const for allocating cache names

 drivers/clk/clk.c      | 12 ++++++------
 fs/kernfs/dir.c        | 12 ++++++------
 include/linux/string.h |  3 +++
 mm/slab_common.c       |  6 +++---
 mm/util.c              | 22 ++++++++++++++++++++++
 5 files changed, 40 insertions(+), 15 deletions(-)

-- 
1.9.1

[RFC PATCH 1/4] mm/util: add kstrdup_const

[Andrzej Hajda]

The patch adds alternative version of kstrdup which returns pointer
to constant char array. The function checks if input string is in
persistent and read-only memory section, if yes it returns the input string,
otherwise it fallbacks to kstrdup.
kstrdup_const is accompanied by kfree_const performing conditional memory
deallocation of the string.

Signed-off-by: Andrzej Hajda <a.hajda@samsung.com>
---
 include/linux/string.h |  3 +++
 mm/util.c              | 22 ++++++++++++++++++++++
 2 files changed, 25 insertions(+)

diff --git a/include/linux/string.h b/include/linux/string.h
index a0c6fd5..c9cd44e 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -115,7 +115,10 @@ extern void * memchr(const void *,int,__kernel_size_t);
 #endif
 void *memchr_inv(const void *s, int c, size_t n);
 
+extern void kfree_const(const void *x);
+
 extern char *kstrdup(const char *s, gfp_t gfp);
+extern const char *kstrdup_const(const char *s, gfp_t gfp);
 extern char *kstrndup(const char *s, size_t len, gfp_t gfp);
 extern char *kstrimdup(const char *s, gfp_t gfp);
 extern void *kmemdup(const void *src, size_t len, gfp_t gfp);
diff --git a/mm/util.c b/mm/util.c
index d25558b..7fc0094 100644
--- a/mm/util.c
+++ b/mm/util.c
@@ -13,10 +13,24 @@
 #include <linux/hugetlb.h>
 #include <linux/vmalloc.h>
 
+#include <asm/sections.h>
 #include <asm/uaccess.h>
 
 #include "internal.h"
 
+static inline int is_kernel_rodata(unsigned long addr)
+{
+	return addr >= (unsigned long)__start_rodata &&
+		addr < (unsigned long)__end_rodata;
+}
+
+void kfree_const(const void *x)
+{
+	if (!is_kernel_rodata((unsigned long)x))
+		kfree(x);
+}
+EXPORT_SYMBOL(kfree_const);
+
 /**
  * kstrdup - allocate space for and copy an existing string
  * @s: the string to duplicate
@@ -38,6 +52,14 @@ char *kstrdup(const char *s, gfp_t gfp)
 }
 EXPORT_SYMBOL(kstrdup);
 
+const char *kstrdup_const(const char *s, gfp_t gfp)
+{
+	if (is_kernel_rodata((unsigned long)s))
+		return s;
+
+	return kstrdup(s, gfp);
+}
+
 /**
  * kstrndup - allocate space for and copy an existing string
  * @s: the string to duplicate
-- 
1.9.1

[RFC PATCH 2/4] kernfs: use kstrdup_const for node name allocation

[Andrzej Hajda]

sysfs frequently performs duplication of strings located
in read-only memory section. Replacing kstrdup by kstrdup_const
allows to avoid such operations.

Signed-off-by: Andrzej Hajda <a.hajda@samsung.com>
---
 fs/kernfs/dir.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/fs/kernfs/dir.c b/fs/kernfs/dir.c
index 37989f0..259e92a 100644
--- a/fs/kernfs/dir.c
+++ b/fs/kernfs/dir.c
@@ -408,7 +408,7 @@ void kernfs_put(struct kernfs_node *kn)
 	if (kernfs_type(kn) == KERNFS_LINK)
 		kernfs_put(kn->symlink.target_kn);
 	if (!(kn->flags & KERNFS_STATIC_NAME))
-		kfree(kn->name);
+		kfree_const(kn->name);
 	if (kn->iattr) {
 		if (kn->iattr->ia_secdata)
 			security_release_secctx(kn->iattr->ia_secdata,
@@ -502,12 +502,12 @@ static struct kernfs_node *__kernfs_new_node(struct kernfs_root *root,
 					     const char *name, umode_t mode,
 					     unsigned flags)
 {
-	char *dup_name = NULL;
+	const char *dup_name = NULL;
 	struct kernfs_node *kn;
 	int ret;
 
 	if (!(flags & KERNFS_STATIC_NAME)) {
-		name = dup_name = kstrdup(name, GFP_KERNEL);
+		name = dup_name = kstrdup_const(name, GFP_KERNEL);
 		if (!name)
 			return NULL;
 	}
@@ -534,7 +534,7 @@ static struct kernfs_node *__kernfs_new_node(struct kernfs_root *root,
  err_out2:
 	kmem_cache_free(kernfs_node_cache, kn);
  err_out1:
-	kfree(dup_name);
+	kfree_const(dup_name);
 	return NULL;
 }
 
@@ -1260,7 +1260,7 @@ int kernfs_rename_ns(struct kernfs_node *kn, struct kernfs_node *new_parent,
 	/* rename kernfs_node */
 	if (strcmp(kn->name, new_name) != 0) {
 		error = -ENOMEM;
-		new_name = kstrdup(new_name, GFP_KERNEL);
+		new_name = kstrdup_const(new_name, GFP_KERNEL);
 		if (!new_name)
 			goto out;
 	} else {
@@ -1293,7 +1293,7 @@ int kernfs_rename_ns(struct kernfs_node *kn, struct kernfs_node *new_parent,
 	kernfs_link_sibling(kn);
 
 	kernfs_put(old_parent);
-	kfree(old_name);
+	kfree_const(old_name);
 
 	error = 0;
  out:
-- 
1.9.1

[RFC PATCH 3/4] clk: use kstrdup_const for clock name allocations

[Andrzej Hajda]

Clock subsystem frequently performs duplication of strings located
in read-only memory section. Replacing kstrdup by kstrdup_const
allows to avoid such operations.

Signed-off-by: Andrzej Hajda <a.hajda@samsung.com>
---
 drivers/clk/clk.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/drivers/clk/clk.c b/drivers/clk/clk.c
index f4963b7..27e644a 100644
--- a/drivers/clk/clk.c
+++ b/drivers/clk/clk.c
@@ -2048,7 +2048,7 @@ struct clk *clk_register(struct device *dev, struct clk_hw *hw)
 		goto fail_out;
 	}
 
-	clk->name = kstrdup(hw->init->name, GFP_KERNEL);
+	clk->name = kstrdup_const(hw->init->name, GFP_KERNEL);
 	if (!clk->name) {
 		pr_err("%s: could not allocate clk->name\n", __func__);
 		ret = -ENOMEM;
@@ -2075,7 +2075,7 @@ struct clk *clk_register(struct device *dev, struct clk_hw *hw)
 
 	/* copy each string name in case parent_names is __initdata */
 	for (i = 0; i < clk->num_parents; i++) {
-		clk->parent_names[i] = kstrdup(hw->init->parent_names[i],
+		clk->parent_names[i] = kstrdup_const(hw->init->parent_names[i],
 						GFP_KERNEL);
 		if (!clk->parent_names[i]) {
 			pr_err("%s: could not copy parent_names\n", __func__);
@@ -2090,10 +2090,10 @@ struct clk *clk_register(struct device *dev, struct clk_hw *hw)
 
 fail_parent_names_copy:
 	while (--i >= 0)
-		kfree(clk->parent_names[i]);
+		kfree_const(clk->parent_names[i]);
 	kfree(clk->parent_names);
 fail_parent_names:
-	kfree(clk->name);
+	kfree_const(clk->name);
 fail_name:
 	kfree(clk);
 fail_out:
@@ -2112,10 +2112,10 @@ static void __clk_release(struct kref *ref)
 
 	kfree(clk->parents);
 	while (--i >= 0)
-		kfree(clk->parent_names[i]);
+		kfree_const(clk->parent_names[i]);
 
 	kfree(clk->parent_names);
-	kfree(clk->name);
+	kfree_const(clk->name);
 	kfree(clk);
 }
 
-- 
1.9.1

[RFC PATCH 4/4] mm/slab: use kstrdup_const for allocating cache names

[Andrzej Hajda]

slab frequently performs duplication of strings located
in read-only memory section. Replacing kstrdup by kstrdup_const
allows to avoid such operations.

Signed-off-by: Andrzej Hajda <a.hajda@samsung.com>
---
 mm/slab_common.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/mm/slab_common.c b/mm/slab_common.c
index e03dd6f..2d94d1a 100644
--- a/mm/slab_common.c
+++ b/mm/slab_common.c
@@ -390,7 +390,7 @@ kmem_cache_create(const char *name, size_t size, size_t align,
 	if (s)
 		goto out_unlock;
 
-	cache_name = kstrdup(name, GFP_KERNEL);
+	cache_name = kstrdup_const(name, GFP_KERNEL);
 	if (!cache_name) {
 		err = -ENOMEM;
 		goto out_unlock;
@@ -401,7 +401,7 @@ kmem_cache_create(const char *name, size_t size, size_t align,
 				 flags, ctor, NULL, NULL);
 	if (IS_ERR(s)) {
 		err = PTR_ERR(s);
-		kfree(cache_name);
+		kfree_const(cache_name);
 	}
 
 out_unlock:
@@ -494,7 +494,7 @@ static int memcg_cleanup_cache_params(struct kmem_cache *s)
 
 void slab_kmem_cache_release(struct kmem_cache *s)
 {
-	kfree(s->name);
+	kfree_const(s->name);
 	kmem_cache_free(kmem_cache, s);
 }
 
-- 
1.9.1

Re: [RFC PATCH 0/4] kstrdup optimization

[Andi Kleen]

Andrzej Hajda <a.hajda@samsung.com> writes:

> kstrdup if often used to duplicate strings where neither source neither
> destination will be ever modified. In such case we can just reuse the source
> instead of duplicating it. The problem is that we must be sure that
> the source is non-modifiable and its life-time is long enough.

What happens if someone is to kfree() these strings?

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only

Re: [RFC PATCH 0/4] kstrdup optimization

[Andrzej Hajda]

On 12/30/2014 07:45 AM, Andi Kleen wrote:
> Andrzej Hajda <a.hajda@samsung.com> writes:
>
>> kstrdup if often used to duplicate strings where neither source neither
>> destination will be ever modified. In such case we can just reuse the source
>> instead of duplicating it. The problem is that we must be sure that
>> the source is non-modifiable and its life-time is long enough.
> What happens if someone is to kfree() these strings?
>
> -Andi
>
kstrdup_const must be accompanied by kfree_const, I did not mention it
in cover letter
but it is described in the 1st patch commit message.
Simpler alternative (but I am not sure if better) would be to add
similar check
(ie. if pointer is in .rodata) to kfree itself.

Regards
Andrzej

Re: [RFC PATCH 0/4] kstrdup optimization

[Andreas Mohr]

Hi,

Andrzej Hajda wrote:
> On 12/30/2014 07:45 AM, Andi Kleen wrote:
> > What happens if someone is to kfree() these strings?
> >
> > -Andi
> >
> kstrdup_const must be accompanied by kfree_const, I did not mention it
> in cover letter
> but it is described in the 1st patch commit message.
> Simpler alternative (but I am not sure if better) would be to add
> similar check
> (ie. if pointer is in .rodata) to kfree itself.

Seems like a large potential programmer-side (a)symmetry issue to me
(not unsimilar to the new/delete vs. malloc/free asymmetry PITA
encountered in case of "dirty C++ habits").

This symmetry issue probably could be cleanly avoided only
by having kfree() itself contain such an identifying check, as you suggest
(thereby slowing down kfree() performance).
(OTOH we do have nice helpers such as Coccinelle
to near-sufficiently deal with such issues,
albeit in a less preferrable/elegant/automatic manner).

If we decide to want to avoid this rats nest via clean builtin identification
but in case such a kfree-side .rodata check is unjustifiably expensive,
one could try to have *builtin* (i.e., fully or at least almost *non*-runtime)
branching of their differing handling,
by marking _const-originated "allocations" via a special easily checkable flag -
but since in such kalloc/kfree API cases
we're dealing with simple raw pointer results
rather than more complex structs,
such identification markup probably could only be achieved
via internal mapping overhead (of management structs) -
unless those APIs happen to have internal bookkeeping already
(in which case the only penalty would either be setting/evaluating a flag
of common shared bookkeeping structs,
or full/clean branching into distinctly handled management parts,
which might be able to cause less runtime overhead).

Andreas Mohr

-- 
GNU/Linux. It's not the software that's free, it's you.

Re: [RFC PATCH 0/4] kstrdup optimization

[Andi Kleen]

> This symmetry issue probably could be cleanly avoided only
> by having kfree() itself contain such an identifying check, as you suggest
> (thereby slowing down kfree() performance).

It actually shouldn't slow it down. kfree already complains if you free
a non slab page, this could be just in front of the error check.

The bigger concern is that it may hide some programing errors elsewhere
though. So it's probably better to keep it a separate function.

-Andi

Re: [RFC PATCH 0/4] kstrdup optimization

[Andrzej Hajda]

On 12/29/2014 03:48 PM, Andrzej Hajda wrote:

(...)

> As I have tested it on mobile platform (exynos4210-trats) it saves above 2600
> string duplications. Below simple stats about the most frequent duplications:
> Count String
>   880 power
>   874 subsystem
>   130 device
>   126 parameters
>    61 iommu_group
>    40 driver
>    28 bdi
>    28 none
>    25 sclk_mpll
>    23 sclk_usbphy0
>    23 sclk_hdmi24m
>    23 xusbxti
>    22 sclk_vpll
>    22 sclk_epll
>    22 xxti
>    20 sclk_hdmiphy
>    11 aclk100

Minor update, printk buffer was too short during tests so I have not
catched everything. In fact the patchset saves 3260 duplications. Below
stats per kstrdup_const caller:
   2260 __kernfs_new_node+0x28/0xc4
    631 clk_register+0xc8/0x1b8
    318 clk_register+0x34/0x1b8
     51 kmem_cache_create+0x7c/0x1c8

Regards
Andrzej

Re: [RFC PATCH 0/4] kstrdup optimization

[Andrzej Hajda]

Hi Andi, Andreas,

Thanks for comments.

On 12/30/2014 10:29 PM, Andi Kleen wrote:
>> This symmetry issue probably could be cleanly avoided only
>> by having kfree() itself contain such an identifying check, as you suggest
>> (thereby slowing down kfree() performance).
> 
> It actually shouldn't slow it down. kfree already complains if you free
> a non slab page, this could be just in front of the error check.
> 
> The bigger concern is that it may hide some programing errors elsewhere
> though. So it's probably better to keep it a separate function.

Shall I interpret it as preliminary ack?

If yes, I can repost it without RFC prefix. Anyway I need to:
- add EXPORT_SYMBOL(kstrdup_const),
- add kerneldocs for both functions.

I can also add patch constifying mnt->mnt_devname in alloc_vfsmnt,
on my test platform it could save 13 additional allocations.

Regards
Andrzej