[PATCH v3 0/2] io_uring: Add KASAN support for alloc caches

[PATCH v3 0/2] io_uring: Add KASAN support for alloc caches

[Breno Leitao]

This patchset enables KASAN for alloc cache buffers. These buffers are
used by apoll and netmsg code path. These buffers will now be poisoned
when not used, so, if randomly touched, a KASAN warning will pop up.

This patchset moves the alloc_cache from using double linked list to single
linked list, so, we do not need to touch the poisoned node when adding
or deleting a sibling node.

Changes from v1 to v2:
   * Get rid of an extra "struct io_wq_work_node" variable in
     io_alloc_cache_get() (suggested by Pavel Begunkov)
   * Removing assignement during "if" checks (suggested by Pavel Begunkov
     and Jens Axboe)
   * Do not use network structs if CONFIG_NET is disabled (as reported
     by kernel test robot)

Changes from v2 to v3:
   * Store elem_size in the io_alloc_cache, so, we don't need to pass
     the size when getting the cache element.


Breno Leitao (2):
  io_uring: Move from hlist to io_wq_work_node
  io_uring: Add KASAN support for alloc_caches

 include/linux/io_uring_types.h |  3 ++-
 io_uring/alloc_cache.h         | 30 ++++++++++++++++++------------
 io_uring/io_uring.c            |  4 ++--
 io_uring/net.h                 |  5 ++++-
 4 files changed, 26 insertions(+), 16 deletions(-)

-- 
2.30.2

[PATCH v3 1/2] io_uring: Move from hlist to io_wq_work_node

[Breno Leitao]

Having cache entries linked using the hlist format brings no benefit, and
also requires an unnecessary extra pointer address per cache entry.

Use the internal io_wq_work_node single-linked list for the internal
alloc caches (async_msghdr and async_poll)

This is required to be able to use KASAN on cache entries, since we do
not need to touch unused (and poisoned) cache entries when adding more
entries to the list.

Suggested-by: Pavel Begunkov <asml.silence@gmail.com>
Signed-off-by: Breno Leitao <leitao@debian.org>
---
 include/linux/io_uring_types.h |  2 +-
 io_uring/alloc_cache.h         | 24 +++++++++++++-----------
 2 files changed, 14 insertions(+), 12 deletions(-)

diff --git a/include/linux/io_uring_types.h b/include/linux/io_uring_types.h
index 0efe4d784358..efa66b6c32c9 100644
--- a/include/linux/io_uring_types.h
+++ b/include/linux/io_uring_types.h
@@ -188,7 +188,7 @@ struct io_ev_fd {
 };
 
 struct io_alloc_cache {
-	struct hlist_head	list;
+	struct io_wq_work_node	list;
 	unsigned int		nr_cached;
 };
 
diff --git a/io_uring/alloc_cache.h b/io_uring/alloc_cache.h
index 729793ae9712..301855e94309 100644
--- a/io_uring/alloc_cache.h
+++ b/io_uring/alloc_cache.h
@@ -7,7 +7,7 @@
 #define IO_ALLOC_CACHE_MAX	512
 
 struct io_cache_entry {
-	struct hlist_node	node;
+	struct io_wq_work_node node;
 };
 
 static inline bool io_alloc_cache_put(struct io_alloc_cache *cache,
@@ -15,7 +15,7 @@ static inline bool io_alloc_cache_put(struct io_alloc_cache *cache,
 {
 	if (cache->nr_cached < IO_ALLOC_CACHE_MAX) {
 		cache->nr_cached++;
-		hlist_add_head(&entry->node, &cache->list);
+		wq_stack_add_head(&entry->node, &cache->list);
 		return true;
 	}
 	return false;
@@ -23,11 +23,12 @@ static inline bool io_alloc_cache_put(struct io_alloc_cache *cache,
 
 static inline struct io_cache_entry *io_alloc_cache_get(struct io_alloc_cache *cache)
 {
-	if (!hlist_empty(&cache->list)) {
-		struct hlist_node *node = cache->list.first;
+	if (cache->list.next) {
+		struct io_cache_entry *entry;
 
-		hlist_del(node);
-		return container_of(node, struct io_cache_entry, node);
+		entry = container_of(cache->list.next, struct io_cache_entry, node);
+		cache->list.next = cache->list.next->next;
+		return entry;
 	}
 
 	return NULL;
@@ -35,18 +36,19 @@ static inline struct io_cache_entry *io_alloc_cache_get(struct io_alloc_cache *c
 
 static inline void io_alloc_cache_init(struct io_alloc_cache *cache)
 {
-	INIT_HLIST_HEAD(&cache->list);
+	cache->list.next = NULL;
 	cache->nr_cached = 0;
 }
 
 static inline void io_alloc_cache_free(struct io_alloc_cache *cache,
 					void (*free)(struct io_cache_entry *))
 {
-	while (!hlist_empty(&cache->list)) {
-		struct hlist_node *node = cache->list.first;
+	while (1) {
+		struct io_cache_entry *entry = io_alloc_cache_get(cache);
 
-		hlist_del(node);
-		free(container_of(node, struct io_cache_entry, node));
+		if (!entry)
+			break;
+		free(entry);
 	}
 	cache->nr_cached = 0;
 }
-- 
2.30.2

Re: [PATCH v3 1/2] io_uring: Move from hlist to io_wq_work_node

[Gabriel Krisman Bertazi]

Breno Leitao <leitao@debian.org> writes:

> Having cache entries linked using the hlist format brings no benefit, and
> also requires an unnecessary extra pointer address per cache entry.
>
> Use the internal io_wq_work_node single-linked list for the internal
> alloc caches (async_msghdr and async_poll)
>
> This is required to be able to use KASAN on cache entries, since we do
> not need to touch unused (and poisoned) cache entries when adding more
> entries to the list.
>

Looking at this patch, I wonder if it could go in the opposite direction
instead, and drop io_wq_work_node entirely in favor of list_head. :)

Do we gain anything other than avoiding the backpointer with a custom
linked implementation, instead of using the interface available in
list.h, that developers know how to use and has other features like
poisoning and extra debug checks?


>  static inline struct io_cache_entry *io_alloc_cache_get(struct io_alloc_cache *cache)
>  {
> -	if (!hlist_empty(&cache->list)) {
> -		struct hlist_node *node = cache->list.first;
> +	if (cache->list.next) {
> +		struct io_cache_entry *entry;
>  
> -		hlist_del(node);
> -		return container_of(node, struct io_cache_entry, node);
> +		entry = container_of(cache->list.next, struct io_cache_entry, node);
> +		cache->list.next = cache->list.next->next;
> +		return entry;
>  	}

From a quick look, I think you could use wq_stack_extract() here

-- 
Gabriel Krisman Bertazi

Re: [PATCH v3 1/2] io_uring: Move from hlist to io_wq_work_node

[Jens Axboe]

On 2/23/23 12:02?PM, Gabriel Krisman Bertazi wrote:
> Breno Leitao <leitao@debian.org> writes:
> 
>> Having cache entries linked using the hlist format brings no benefit, and
>> also requires an unnecessary extra pointer address per cache entry.
>>
>> Use the internal io_wq_work_node single-linked list for the internal
>> alloc caches (async_msghdr and async_poll)
>>
>> This is required to be able to use KASAN on cache entries, since we do
>> not need to touch unused (and poisoned) cache entries when adding more
>> entries to the list.
>>
> 
> Looking at this patch, I wonder if it could go in the opposite direction
> instead, and drop io_wq_work_node entirely in favor of list_head. :)
> 
> Do we gain anything other than avoiding the backpointer with a custom
> linked implementation, instead of using the interface available in
> list.h, that developers know how to use and has other features like
> poisoning and extra debug checks?

list_head is twice as big, that's the main motivation. This impacts
memory usage (obviously), but also caches when adding/removing
entries.

-- 
Jens Axboe

Re: [PATCH v3 1/2] io_uring: Move from hlist to io_wq_work_node

[Gabriel Krisman Bertazi]

Jens Axboe <axboe@kernel.dk> writes:

> On 2/23/23 12:02?PM, Gabriel Krisman Bertazi wrote:
>> Breno Leitao <leitao@debian.org> writes:
>> 
>>> Having cache entries linked using the hlist format brings no benefit, and
>>> also requires an unnecessary extra pointer address per cache entry.
>>>
>>> Use the internal io_wq_work_node single-linked list for the internal
>>> alloc caches (async_msghdr and async_poll)
>>>
>>> This is required to be able to use KASAN on cache entries, since we do
>>> not need to touch unused (and poisoned) cache entries when adding more
>>> entries to the list.
>>>
>> 
>> Looking at this patch, I wonder if it could go in the opposite direction
>> instead, and drop io_wq_work_node entirely in favor of list_head. :)
>> 
>> Do we gain anything other than avoiding the backpointer with a custom
>> linked implementation, instead of using the interface available in
>> list.h, that developers know how to use and has other features like
>> poisoning and extra debug checks?
>
> list_head is twice as big, that's the main motivation. This impacts
> memory usage (obviously), but also caches when adding/removing
> entries.

Right. But this is true all around the kernel.  Many (Most?)  places
that use list_head don't even need to touch list_head->prev.  And
list_head is usually embedded in larger structures where the cost of
the extra pointer is insignificant.  I suspect the memory
footprint shouldn't really be the problem.

This specific patch is extending io_wq_work_node to io_cache_entry,
where the increased size will not matter.  In fact, for the cached
structures, the cache layout and memory footprint don't even seem to
change, as io_cache_entry is already in a union larger than itself, that
is not crossing cachelines, (io_async_msghdr, async_poll).

The other structures currently embedding struct io_work_node are
io_kiocb (216 bytes long, per request) and io_ring_ctx (1472 bytes long,
per ring). so it is not like we are saving a lot of memory with a single
linked list. A more compact cache line still makes sense, though, but I
think the only case (if any) where there might be any gain is io_kiocb?

I don't severely oppose this patch, of course. But I think it'd be worth
killing io_uring/slist.h entirely in the future instead of adding more
users.  I intend to give that approach a try, if there's a way to keep
the size of io_kiocb.

-- 
Gabriel Krisman Bertazi

Re: [PATCH v3 1/2] io_uring: Move from hlist to io_wq_work_node

[Jens Axboe]

On 2/24/23 11:32?AM, Gabriel Krisman Bertazi wrote:
> Jens Axboe <axboe@kernel.dk> writes:
> 
>> On 2/23/23 12:02?PM, Gabriel Krisman Bertazi wrote:
>>> Breno Leitao <leitao@debian.org> writes:
>>>
>>>> Having cache entries linked using the hlist format brings no benefit, and
>>>> also requires an unnecessary extra pointer address per cache entry.
>>>>
>>>> Use the internal io_wq_work_node single-linked list for the internal
>>>> alloc caches (async_msghdr and async_poll)
>>>>
>>>> This is required to be able to use KASAN on cache entries, since we do
>>>> not need to touch unused (and poisoned) cache entries when adding more
>>>> entries to the list.
>>>>
>>>
>>> Looking at this patch, I wonder if it could go in the opposite direction
>>> instead, and drop io_wq_work_node entirely in favor of list_head. :)
>>>
>>> Do we gain anything other than avoiding the backpointer with a custom
>>> linked implementation, instead of using the interface available in
>>> list.h, that developers know how to use and has other features like
>>> poisoning and extra debug checks?
>>
>> list_head is twice as big, that's the main motivation. This impacts
>> memory usage (obviously), but also caches when adding/removing
>> entries.
> 
> Right. But this is true all around the kernel.  Many (Most?)  places
> that use list_head don't even need to touch list_head->prev.  And
> list_head is usually embedded in larger structures where the cost of
> the extra pointer is insignificant.  I suspect the memory
> footprint shouldn't really be the problem.

I may be in the minority here in caring deeply about even little details
in terms of memory foot print and how many cachelines we touch... Eg if
we can embed 8 bytes rather than 16, then why not? Particularly for
cases where we may have a lot of these structures.

But it's of course always a tradeoff.

> This specific patch is extending io_wq_work_node to io_cache_entry,
> where the increased size will not matter.  In fact, for the cached
> structures, the cache layout and memory footprint don't even seem to
> change, as io_cache_entry is already in a union larger than itself, that
> is not crossing cachelines, (io_async_msghdr, async_poll).

True, for the caching case, the member size doesn't matter. At least
immediately. Sometimes things are shuffled around and optimized further,
and then you may need to find 8 bytes to avoid bloating the struct.

> The other structures currently embedding struct io_work_node are
> io_kiocb (216 bytes long, per request) and io_ring_ctx (1472 bytes long,
> per ring). so it is not like we are saving a lot of memory with a single
> linked list. A more compact cache line still makes sense, though, but I
> think the only case (if any) where there might be any gain is io_kiocb?

Yeah, the ring is already pretty big. It is still handled in cachelines
for the bits that matter, so nice to keep them as small for the
sections. Maybe bumping it will waste an extra cacheline. Or, more
commonly, later additions now end up bumping into the next cacheline
rather than still fitting.

> I don't severely oppose this patch, of course. But I think it'd be worth
> killing io_uring/slist.h entirely in the future instead of adding more
> users.  I intend to give that approach a try, if there's a way to keep
> the size of io_kiocb.

At least it's consistent within io_uring, which also means something.
I'd be fine with taking a look at such a patch, but let's please keep it
outside the scope of this change.

-- 
Jens Axboe

Re: [PATCH v3 1/2] io_uring: Move from hlist to io_wq_work_node

[Breno Leitao]

Hello Krisman, thanks for the review

On Thu, Feb 23, 2023 at 04:02:25PM -0300, Gabriel Krisman Bertazi wrote:
> Breno Leitao <leitao@debian.org> writes:

> >  static inline struct io_cache_entry *io_alloc_cache_get(struct io_alloc_cache *cache)
> >  {
> > -	if (!hlist_empty(&cache->list)) {
> > -		struct hlist_node *node = cache->list.first;
> > +	if (cache->list.next) {
> > +		struct io_cache_entry *entry;
> >  
> > -		hlist_del(node);
> > -		return container_of(node, struct io_cache_entry, node);
> > +		entry = container_of(cache->list.next, struct io_cache_entry, node);
> > +		cache->list.next = cache->list.next->next;
> > +		return entry;
> >  	}
> 
> From a quick look, I think you could use wq_stack_extract() here

True, we can use wq_stack_extract() in this patch, but, we would need to
revert to back to this code in the next patch. Remember that
wq_stack_extract() touches the stack->next->next, which will be
poisoned, causing a KASAN warning.

Here is relevant part of the code:

	struct io_wq_work_node *wq_stack_extract(struct io_wq_work_node *stack)
	{
		struct io_wq_work_node *node = stack->next;
		stack->next = node->next;

[PATCH v3 2/2] io_uring: Add KASAN support for alloc_caches

[Breno Leitao]

Add support for KASAN in the alloc_caches (apoll and netmsg_cache).
Thus, if something touches the unused caches, it will raise a KASAN
warning/exception.

It poisons the object when the object is put to the cache, and unpoisons
it when the object is gotten or freed.

Signed-off-by: Breno Leitao <leitao@debian.org>
---
 include/linux/io_uring_types.h | 1 +
 io_uring/alloc_cache.h         | 6 +++++-
 io_uring/io_uring.c            | 4 ++--
 io_uring/net.h                 | 5 ++++-
 4 files changed, 12 insertions(+), 4 deletions(-)

diff --git a/include/linux/io_uring_types.h b/include/linux/io_uring_types.h
index efa66b6c32c9..35ebcfb46047 100644
--- a/include/linux/io_uring_types.h
+++ b/include/linux/io_uring_types.h
@@ -190,6 +190,7 @@ struct io_ev_fd {
 struct io_alloc_cache {
 	struct io_wq_work_node	list;
 	unsigned int		nr_cached;
+	size_t			elem_size;
 };
 
 struct io_ring_ctx {
diff --git a/io_uring/alloc_cache.h b/io_uring/alloc_cache.h
index 301855e94309..3aba7b356320 100644
--- a/io_uring/alloc_cache.h
+++ b/io_uring/alloc_cache.h
@@ -16,6 +16,8 @@ static inline bool io_alloc_cache_put(struct io_alloc_cache *cache,
 	if (cache->nr_cached < IO_ALLOC_CACHE_MAX) {
 		cache->nr_cached++;
 		wq_stack_add_head(&entry->node, &cache->list);
+		/* KASAN poisons object */
+		kasan_slab_free_mempool(entry);
 		return true;
 	}
 	return false;
@@ -27,6 +29,7 @@ static inline struct io_cache_entry *io_alloc_cache_get(struct io_alloc_cache *c
 		struct io_cache_entry *entry;
 
 		entry = container_of(cache->list.next, struct io_cache_entry, node);
+		kasan_unpoison_range(entry, cache->elem_size);
 		cache->list.next = cache->list.next->next;
 		return entry;
 	}
@@ -34,10 +37,11 @@ static inline struct io_cache_entry *io_alloc_cache_get(struct io_alloc_cache *c
 	return NULL;
 }
 
-static inline void io_alloc_cache_init(struct io_alloc_cache *cache)
+static inline void io_alloc_cache_init(struct io_alloc_cache *cache, size_t size)
 {
 	cache->list.next = NULL;
 	cache->nr_cached = 0;
+	cache->elem_size = size;
 }
 
 static inline void io_alloc_cache_free(struct io_alloc_cache *cache,
diff --git a/io_uring/io_uring.c b/io_uring/io_uring.c
index 80b6204769e8..7a30a3e72fcc 100644
--- a/io_uring/io_uring.c
+++ b/io_uring/io_uring.c
@@ -309,8 +309,8 @@ static __cold struct io_ring_ctx *io_ring_ctx_alloc(struct io_uring_params *p)
 	INIT_LIST_HEAD(&ctx->sqd_list);
 	INIT_LIST_HEAD(&ctx->cq_overflow_list);
 	INIT_LIST_HEAD(&ctx->io_buffers_cache);
-	io_alloc_cache_init(&ctx->apoll_cache);
-	io_alloc_cache_init(&ctx->netmsg_cache);
+	io_alloc_cache_init(&ctx->apoll_cache, sizeof(struct async_poll));
+	io_alloc_cache_init(&ctx->netmsg_cache, sizeof(struct io_async_msghdr));
 	init_completion(&ctx->ref_comp);
 	xa_init_flags(&ctx->personalities, XA_FLAGS_ALLOC1);
 	mutex_init(&ctx->uring_lock);
diff --git a/io_uring/net.h b/io_uring/net.h
index 5ffa11bf5d2e..191009979bcb 100644
--- a/io_uring/net.h
+++ b/io_uring/net.h
@@ -5,8 +5,8 @@
 
 #include "alloc_cache.h"
 
-#if defined(CONFIG_NET)
 struct io_async_msghdr {
+#if defined(CONFIG_NET)
 	union {
 		struct iovec		fast_iov[UIO_FASTIOV];
 		struct {
@@ -22,8 +22,11 @@ struct io_async_msghdr {
 	struct sockaddr __user		*uaddr;
 	struct msghdr			msg;
 	struct sockaddr_storage		addr;
+#endif
 };
 
+#if defined(CONFIG_NET)
+
 struct io_async_connect {
 	struct sockaddr_storage		address;
 };
-- 
2.30.2

Re: [PATCH v3 2/2] io_uring: Add KASAN support for alloc_caches

[Gabriel Krisman Bertazi]

Breno Leitao <leitao@debian.org> writes:

> Add support for KASAN in the alloc_caches (apoll and netmsg_cache).
> Thus, if something touches the unused caches, it will raise a KASAN
> warning/exception.
>
> It poisons the object when the object is put to the cache, and unpoisons
> it when the object is gotten or freed.
>
> Signed-off-by: Breno Leitao <leitao@debian.org>
> ---
>  include/linux/io_uring_types.h | 1 +
>  io_uring/alloc_cache.h         | 6 +++++-
>  io_uring/io_uring.c            | 4 ++--
>  io_uring/net.h                 | 5 ++++-
>  4 files changed, 12 insertions(+), 4 deletions(-)
>
> diff --git a/include/linux/io_uring_types.h b/include/linux/io_uring_types.h
> index efa66b6c32c9..35ebcfb46047 100644
> --- a/include/linux/io_uring_types.h
> +++ b/include/linux/io_uring_types.h
> @@ -190,6 +190,7 @@ struct io_ev_fd {
>  struct io_alloc_cache {
>  	struct io_wq_work_node	list;
>  	unsigned int		nr_cached;
> +	size_t			elem_size;
>  };
>  
>  struct io_ring_ctx {
> diff --git a/io_uring/alloc_cache.h b/io_uring/alloc_cache.h
> index 301855e94309..3aba7b356320 100644
> --- a/io_uring/alloc_cache.h
> +++ b/io_uring/alloc_cache.h
> @@ -16,6 +16,8 @@ static inline bool io_alloc_cache_put(struct io_alloc_cache *cache,
>  	if (cache->nr_cached < IO_ALLOC_CACHE_MAX) {
>  		cache->nr_cached++;
>  		wq_stack_add_head(&entry->node, &cache->list);
> +		/* KASAN poisons object */
> +		kasan_slab_free_mempool(entry);
>  		return true;
>  	}
>  	return false;
> @@ -27,6 +29,7 @@ static inline struct io_cache_entry *io_alloc_cache_get(struct io_alloc_cache *c
>  		struct io_cache_entry *entry;
>  
>  		entry = container_of(cache->list.next, struct io_cache_entry, node);
> +		kasan_unpoison_range(entry, cache->elem_size);

I kind of worry there is no type checking at the same time we are
unpoisoning a constant-size range.  Seems easy to misuse the API.  But it
does look much better now with elem_size cached inside io_alloc_cache.

>  
> -#if defined(CONFIG_NET)
>  struct io_async_msghdr {
> +#if defined(CONFIG_NET)
>  	union {
>  		struct iovec		fast_iov[UIO_FASTIOV];
>  		struct {
> @@ -22,8 +22,11 @@ struct io_async_msghdr {
>  	struct sockaddr __user		*uaddr;
>  	struct msghdr			msg;
>  	struct sockaddr_storage		addr;
> +#endif
>  };
>  
> +#if defined(CONFIG_NET)
> +

Nit, but you could have added an empty definition in the #else section
that already exists in the file, or just guarded the caching code
entirely when CONFIG_NET=n.

Just nits, and overall it is good to have this KASAN support!

Reviewed-by: Gabriel Krisman Bertazi <krisman@suse.de>

-- 
Gabriel Krisman Bertazi

Re: [PATCH v3 0/2] io_uring: Add KASAN support for alloc caches

[Jens Axboe]

On Thu, 23 Feb 2023 08:43:51 -0800, Breno Leitao wrote:
> This patchset enables KASAN for alloc cache buffers. These buffers are
> used by apoll and netmsg code path. These buffers will now be poisoned
> when not used, so, if randomly touched, a KASAN warning will pop up.
> 
> This patchset moves the alloc_cache from using double linked list to single
> linked list, so, we do not need to touch the poisoned node when adding
> or deleting a sibling node.
> 
> [...]

Applied, thanks!

[1/2] io_uring: Move from hlist to io_wq_work_node
      commit: 80d5ea4e019d5ac0257c9bf06a7bcf30c9500adc
[2/2] io_uring: Add KASAN support for alloc_caches
      commit: 80d5ea4e019d5ac0257c9bf06a7bcf30c9500adc

Best regards,
-- 
Jens Axboe