Is there a reason we don't have kvfree_rcu()?

Is there a reason we don't have kvfree_rcu()?

[George Spelvin]

kvfree() is a superset of kfree(), so there's nothing obvious stopping 
kfree_rcu() from simply changing to kvfree() and everything will keep 
working.

I'd probably add a kvfree_rcu() alias, just for documentation's sake and
to make code that depends on the new feature explode at compile time, but
it could be identical behind the scenes.

There's an existing user in mm/list_lru.c already.

I was just thinking of using kvmalloc() in a module, and realized that the 
lack of a core kvfree_rcu() helper meant I'd have to synchronize_rcu() on 
module unload.

Re: Is there a reason we don't have kvfree_rcu()?

[Paul E. McKenney]

On Thu, Mar 12, 2020 at 04:27:30PM +0000, George Spelvin wrote:
> kvfree() is a superset of kfree(), so there's nothing obvious stopping 
> kfree_rcu() from simply changing to kvfree() and everything will keep 
> working.
> 
> I'd probably add a kvfree_rcu() alias, just for documentation's sake and
> to make code that depends on the new feature explode at compile time, but
> it could be identical behind the scenes.
> 
> There's an existing user in mm/list_lru.c already.
> 
> I was just thinking of using kvmalloc() in a module, and realized that the 
> lack of a core kvfree_rcu() helper meant I'd have to synchronize_rcu() on 
> module unload.

There was a recent proposal to do just that, but current patches in -rcu
use kfree_bulk().  It doesn't look to me that this works for kfvree()
under the covers in its current form.  Could it be upgraded to handle
this case?

Adding Vlad on CC for his thoughts.

							Thanx, Paul

Re: Is there a reason we don't have kvfree_rcu()?

[Uladzislau Rezki]

On Thu, Mar 12, 2020 at 11:11:38AM -0700, Paul E. McKenney wrote:
> On Thu, Mar 12, 2020 at 04:27:30PM +0000, George Spelvin wrote:
> > kvfree() is a superset of kfree(), so there's nothing obvious stopping 
> > kfree_rcu() from simply changing to kvfree() and everything will keep 
> > working.
> > 
> > I'd probably add a kvfree_rcu() alias, just for documentation's sake and
> > to make code that depends on the new feature explode at compile time, but
> > it could be identical behind the scenes.
> > 
> > There's an existing user in mm/list_lru.c already.
> > 
> > I was just thinking of using kvmalloc() in a module, and realized that the 
> > lack of a core kvfree_rcu() helper meant I'd have to synchronize_rcu() on 
> > module unload.
> 
> There was a recent proposal to do just that, but current patches in -rcu
> use kfree_bulk().  It doesn't look to me that this works for kfvree()
> under the covers in its current form.  Could it be upgraded to handle
> this case?
> 
> Adding Vlad on CC for his thoughts.
> 
Paul, see below my view:

Answering to topic's question it looks like we need kvfree_rcu() support :)

It is easy to add it actually. But if we are talking about the case when
an object has rcu_head inside. From the other hand recent discussion showed
that we would like to have head-less variant of the kvfree_rcu() functionality:

https://lkml.org/lkml/2020/2/18/566

for example, as Ted pointed, he would go with head-less case(for ext4) only.
The reason is nobody wants to modify internal structures injecting rcu_head
there. Also there are many other places in the kernel where it would be good
to have kfree_rcu() head-less variant as well.

I spent some time implementing it together with Joel. It is ready from my
side but only for RCU-tree case. Next step is RCU-tiny support, so i am
working on it.  

I can send out an RFC for RCU-tree only support, so we can discuss it
and agree on how to move forward. After that i or Joel or together can
update RCU-tine.

Joel: What do you think?

Another thought. We can add kvfree_rcu(ptr, rcu) first, because it is
easy and after that implement head-less case.

--
Vlad Rezki

Re: Is there a reason we don't have kvfree_rcu()?

[George Spelvin]

> There was a recent proposal to do just that, but current patches in -rcu
> use kfree_bulk().  It doesn't look to me that this works for kfvree()
> under the covers in its current form.  Could it be upgraded to handle
> this case?

It would take a bit more fiddling, but nothing too difficult.

// from include/linux/mm.h
static inline bool is_vmalloc_addr(const void *x)
{
	unsigned long addr = (unsigned long)x;

	return addr >= VMALLOC_START && addr < VMALLOC_END;
}
// ... which could also be written as (addr - VMALLOC_START) < VMALLOC_TOTAL

// from mm/util.c
void kvfree(const void *addr)
{
	if (is_vmalloc_addr(addr))
		vfree(addr);
	else
		kfree(addr);
}

... so you could easily do the filtering yourself while forming the
kfree_bulk array.

vfree(p) itself is a wrapper around __vunmap(p, 1).  After some 
error-checking, it checks if it's called in interrupt context,
If not, it does the __vunmap synchronously.  If it *is* in interrupt
context, the freed object is put on a linked list and a work queue
does the __vunmap later.

Re: Is there a reason we don't have kvfree_rcu()?

[Joel Fernandes]

On Thu, Mar 12, 2020 at 08:10:09PM +0100, Uladzislau Rezki wrote:
> On Thu, Mar 12, 2020 at 11:11:38AM -0700, Paul E. McKenney wrote:
> > On Thu, Mar 12, 2020 at 04:27:30PM +0000, George Spelvin wrote:
> > > kvfree() is a superset of kfree(), so there's nothing obvious stopping 
> > > kfree_rcu() from simply changing to kvfree() and everything will keep 
> > > working.
> > > 
> > > I'd probably add a kvfree_rcu() alias, just for documentation's sake and
> > > to make code that depends on the new feature explode at compile time, but
> > > it could be identical behind the scenes.
> > > 
> > > There's an existing user in mm/list_lru.c already.
> > > 
> > > I was just thinking of using kvmalloc() in a module, and realized that the 
> > > lack of a core kvfree_rcu() helper meant I'd have to synchronize_rcu() on 
> > > module unload.
> > 
> > There was a recent proposal to do just that, but current patches in -rcu
> > use kfree_bulk().  It doesn't look to me that this works for kfvree()
> > under the covers in its current form.  Could it be upgraded to handle
> > this case?
> > 
> > Adding Vlad on CC for his thoughts.
> > 
> Paul, see below my view:
> 
> Answering to topic's question it looks like we need kvfree_rcu() support :)
> 
> It is easy to add it actually. But if we are talking about the case when
> an object has rcu_head inside. From the other hand recent discussion showed
> that we would like to have head-less variant of the kvfree_rcu() functionality:
> 
> https://lkml.org/lkml/2020/2/18/566
> 
> for example, as Ted pointed, he would go with head-less case(for ext4) only.
> The reason is nobody wants to modify internal structures injecting rcu_head
> there. Also there are many other places in the kernel where it would be good
> to have kfree_rcu() head-less variant as well.
> 
> I spent some time implementing it together with Joel. It is ready from my
> side but only for RCU-tree case. Next step is RCU-tiny support, so i am
> working on it.  
> 
> I can send out an RFC for RCU-tree only support, so we can discuss it
> and agree on how to move forward. After that i or Joel or together can
> update RCU-tine.
> 
> Joel: What do you think?

Yes, your sending an RFC with what you have sounds good. I can prepare a tree
for both of us then and we can develop on that. I was actually waiting on
your patches so I can add more on top.

One more thing I want to add is the shrinker interface to prevent OOM during
kfree_rcu() flood. I sent patches to fix that. It works well. We can prepare
a tree with all these features and develop on that so there's no conflict.

For -tiny and lack of rcu_head, I think we discussed that we would
always dynamically allocate rcu_head for that case.

> Another thought. We can add kvfree_rcu(ptr, rcu) first, because it is
> easy and after that implement head-less case.

Yes, that is also fine. We can start simple and then keep improving it. I
think we have now 3 users who want head-less interface so ultimately we can
shoot for that goal (at later stage).

thanks,

 - Joel

Re: Is there a reason we don't have kvfree_rcu()?

[George Spelvin]

I'd just like to mention that the is_vmalloc_addr() test depends only on 
the virtual address, so can be done when the memory is queued, before the 
grace period.  That is, you could have kfree_rcu(), vfree_rcu(), and a 
kvfree_rcu() function which decides between them.

One advantage of that would be that you could put the vfree() sanity
checks into vfree_rcu(), so errors would have a useful backtrace,
and just do the __vunmap when the grace period expires.

Or you could build a mixed queue and do the is_vmalloc_addr() test at
the end of the grace period.  That was my original idea, because it
avoids the need for a separate queue.  (In the _rcu_bulk_data structure,
you can do a quicksort-style partitioning on is_vmalloc_addr(), so
the kfree_bulk() pointers are all contiguous.)

Just an implementation option.

Re: Is there a reason we don't have kvfree_rcu()?

[Uladzislau Rezki]

On Thu, Mar 12, 2020 at 11:58:09PM -0400, Joel Fernandes wrote:
> On Thu, Mar 12, 2020 at 08:10:09PM +0100, Uladzislau Rezki wrote:
> > On Thu, Mar 12, 2020 at 11:11:38AM -0700, Paul E. McKenney wrote:
> > > On Thu, Mar 12, 2020 at 04:27:30PM +0000, George Spelvin wrote:
> > > > kvfree() is a superset of kfree(), so there's nothing obvious stopping 
> > > > kfree_rcu() from simply changing to kvfree() and everything will keep 
> > > > working.
> > > > 
> > > > I'd probably add a kvfree_rcu() alias, just for documentation's sake and
> > > > to make code that depends on the new feature explode at compile time, but
> > > > it could be identical behind the scenes.
> > > > 
> > > > There's an existing user in mm/list_lru.c already.
> > > > 
> > > > I was just thinking of using kvmalloc() in a module, and realized that the 
> > > > lack of a core kvfree_rcu() helper meant I'd have to synchronize_rcu() on 
> > > > module unload.
> > > 
> > > There was a recent proposal to do just that, but current patches in -rcu
> > > use kfree_bulk().  It doesn't look to me that this works for kfvree()
> > > under the covers in its current form.  Could it be upgraded to handle
> > > this case?
> > > 
> > > Adding Vlad on CC for his thoughts.
> > > 
> > Paul, see below my view:
> > 
> > Answering to topic's question it looks like we need kvfree_rcu() support :)
> > 
> > It is easy to add it actually. But if we are talking about the case when
> > an object has rcu_head inside. From the other hand recent discussion showed
> > that we would like to have head-less variant of the kvfree_rcu() functionality:
> > 
> > https://lkml.org/lkml/2020/2/18/566
> > 
> > for example, as Ted pointed, he would go with head-less case(for ext4) only.
> > The reason is nobody wants to modify internal structures injecting rcu_head
> > there. Also there are many other places in the kernel where it would be good
> > to have kfree_rcu() head-less variant as well.
> > 
> > I spent some time implementing it together with Joel. It is ready from my
> > side but only for RCU-tree case. Next step is RCU-tiny support, so i am
> > working on it.  
> > 
> > I can send out an RFC for RCU-tree only support, so we can discuss it
> > and agree on how to move forward. After that i or Joel or together can
> > update RCU-tine.
> > 
> > Joel: What do you think?
> 
> Yes, your sending an RFC with what you have sounds good. I can prepare a tree
> for both of us then and we can develop on that. I was actually waiting on
> your patches so I can add more on top.
> 
OK. Let's setup something. Currently i am working based on dev.2020.02.16a
branch. If you can, please do it and let me know so we can avoid of conflicts.

> One more thing I want to add is the shrinker interface to prevent OOM during
> kfree_rcu() flood. I sent patches to fix that. It works well. We can prepare
> a tree with all these features and develop on that so there's no conflict.
> 
> For -tiny and lack of rcu_head, I think we discussed that we would
> always dynamically allocate rcu_head for that case.
> 
We can do dynamic attaching. Later on, i think we can implement "arrays" logic
like we do for RCU-tree but without any batching. Simple array pointer store  
mechanism for head-less case.

> > Another thought. We can add kvfree_rcu(ptr, rcu) first, because it is
> > easy and after that implement head-less case.
> 
> Yes, that is also fine. We can start simple and then keep improving it. I
> think we have now 3 users who want head-less interface so ultimately we can
> shoot for that goal (at later stage).
> 
OK. Then, i think i will make kvfree_rcu(ptr, rcu) interface and all the
rest on top.

--
Vlad Rezki

Re: Is there a reason we don't have kvfree_rcu()?

[Joel Fernandes]

On Fri, Mar 13, 2020 at 02:21:24PM +0100, Uladzislau Rezki wrote:
> On Thu, Mar 12, 2020 at 11:58:09PM -0400, Joel Fernandes wrote:
> > On Thu, Mar 12, 2020 at 08:10:09PM +0100, Uladzislau Rezki wrote:
> > > On Thu, Mar 12, 2020 at 11:11:38AM -0700, Paul E. McKenney wrote:
> > > > On Thu, Mar 12, 2020 at 04:27:30PM +0000, George Spelvin wrote:
> > > > > kvfree() is a superset of kfree(), so there's nothing obvious stopping 
> > > > > kfree_rcu() from simply changing to kvfree() and everything will keep 
> > > > > working.
> > > > > 
> > > > > I'd probably add a kvfree_rcu() alias, just for documentation's sake and
> > > > > to make code that depends on the new feature explode at compile time, but
> > > > > it could be identical behind the scenes.
> > > > > 
> > > > > There's an existing user in mm/list_lru.c already.
> > > > > 
> > > > > I was just thinking of using kvmalloc() in a module, and realized that the 
> > > > > lack of a core kvfree_rcu() helper meant I'd have to synchronize_rcu() on 
> > > > > module unload.
> > > > 
> > > > There was a recent proposal to do just that, but current patches in -rcu
> > > > use kfree_bulk().  It doesn't look to me that this works for kfvree()
> > > > under the covers in its current form.  Could it be upgraded to handle
> > > > this case?
> > > > 
> > > > Adding Vlad on CC for his thoughts.
> > > > 
> > > Paul, see below my view:
> > > 
> > > Answering to topic's question it looks like we need kvfree_rcu() support :)
> > > 
> > > It is easy to add it actually. But if we are talking about the case when
> > > an object has rcu_head inside. From the other hand recent discussion showed
> > > that we would like to have head-less variant of the kvfree_rcu() functionality:
> > > 
> > > https://lkml.org/lkml/2020/2/18/566
> > > 
> > > for example, as Ted pointed, he would go with head-less case(for ext4) only.
> > > The reason is nobody wants to modify internal structures injecting rcu_head
> > > there. Also there are many other places in the kernel where it would be good
> > > to have kfree_rcu() head-less variant as well.
> > > 
> > > I spent some time implementing it together with Joel. It is ready from my
> > > side but only for RCU-tree case. Next step is RCU-tiny support, so i am
> > > working on it.  
> > > 
> > > I can send out an RFC for RCU-tree only support, so we can discuss it
> > > and agree on how to move forward. After that i or Joel or together can
> > > update RCU-tine.
> > > 
> > > Joel: What do you think?
> > 
> > Yes, your sending an RFC with what you have sounds good. I can prepare a tree
> > for both of us then and we can develop on that. I was actually waiting on
> > your patches so I can add more on top.
> > 
> OK. Let's setup something. Currently i am working based on dev.2020.02.16a
> branch. If you can, please do it and let me know so we can avoid of conflicts.

Ok, I based the kfree_rcu shrinker patches on an 'rcu/kfree' branch in my git
tree: https://github.com/joelagnel/linux-kernel/tree/rcu/kfree

I will apply your patches to this branch once I have them.

> > One more thing I want to add is the shrinker interface to prevent OOM during
> > kfree_rcu() flood. I sent patches to fix that. It works well. We can prepare
> > a tree with all these features and develop on that so there's no conflict.
> > 
> > For -tiny and lack of rcu_head, I think we discussed that we would
> > always dynamically allocate rcu_head for that case.
> > 
> We can do dynamic attaching. Later on, i think we can implement "arrays" logic
> like we do for RCU-tree but without any batching. Simple array pointer store  
> mechanism for head-less case.

Yep, sounds good.

> > > Another thought. We can add kvfree_rcu(ptr, rcu) first, because it is
> > > easy and after that implement head-less case.
> > 
> > Yes, that is also fine. We can start simple and then keep improving it. I
> > think we have now 3 users who want head-less interface so ultimately we can
> > shoot for that goal (at later stage).
> > 
> OK. Then, i think i will make kvfree_rcu(ptr, rcu) interface and all the
> rest on top.

Ok, sounds good.

thanks,

 - Joel

> 
> --
> Vlad Rezki
> 

Re: Is there a reason we don't have kvfree_rcu()?

[Uladzislau Rezki]

On Fri, Mar 13, 2020 at 05:06:59AM +0000, George Spelvin wrote:
> I'd just like to mention that the is_vmalloc_addr() test depends only on 
> the virtual address, so can be done when the memory is queued, before the 
> grace period.  That is, you could have kfree_rcu(), vfree_rcu(), and a 
> kvfree_rcu() function which decides between them.
> 
> One advantage of that would be that you could put the vfree() sanity
> checks into vfree_rcu(), so errors would have a useful backtrace,
> and just do the __vunmap when the grace period expires.
> 
> Or you could build a mixed queue and do the is_vmalloc_addr() test at
> the end of the grace period.  That was my original idea, because it
> avoids the need for a separate queue.  (In the _rcu_bulk_data structure,
> you can do a quicksort-style partitioning on is_vmalloc_addr(), so
> the kfree_bulk() pointers are all contiguous.)
> 
> Just an implementation option.
Thanks for your input. Mixed queue would require sorting, one node can
contain up to ~509 elements if PAGE_SIZE is 4096, so i am not sure how
it would impact performance under heavy load. But anyway, thanks again.

--
Vlad Rezki

Re: Is there a reason we don't have kvfree_rcu()?

[Paul E. McKenney]

On Fri, Mar 13, 2020 at 05:06:59AM +0000, George Spelvin wrote:
> I'd just like to mention that the is_vmalloc_addr() test depends only on 
> the virtual address, so can be done when the memory is queued, before the 
> grace period.  That is, you could have kfree_rcu(), vfree_rcu(), and a 
> kvfree_rcu() function which decides between them.
> 
> One advantage of that would be that you could put the vfree() sanity
> checks into vfree_rcu(), so errors would have a useful backtrace,
> and just do the __vunmap when the grace period expires.
> 
> Or you could build a mixed queue and do the is_vmalloc_addr() test at
> the end of the grace period.  That was my original idea, because it
> avoids the need for a separate queue.  (In the _rcu_bulk_data structure,
> you can do a quicksort-style partitioning on is_vmalloc_addr(), so
> the kfree_bulk() pointers are all contiguous.)
> 
> Just an implementation option.

I would guess that sorting them before the grace period might improve
cache locality and thus performance.  So it does seem like an excellent
thing to try, at the very least as an experiment.

							Thanx, Paul

Re: Is there a reason we don't have kvfree_rcu()?

[George Spelvin]

On Fri, Mar 13, 2020 at 06:54:00AM -0700, Paul E. McKenney wrote:
> I would guess that sorting them before the grace period might improve
> cache locality and thus performance.  So it does seem like an excellent
> thing to try, at the very least as an experiment.

That doesn't seem at all obvious.  Processing them in separate batches
would improve I-cache locality, but you could sort them after the
grace period just as well as before.  Especially if you have arrays of 
500 pointers to work with.

Indeed, one thing that seems worth trying is sorting by address, which 
would improve D-cache locality, since you have a significant chance for 
consecutive frees to be in the same slab or otherwise reference the same 
overhead data structures.

Sorting by (address - VMALLOC_START) automatically groups the vallocated 
poiners together at the front, too.  Since there's no vfree_bulk, you can 
iterate over them until you run out, then kfree_bulk the rest.

(This idea came from a memory that bulk file operations can be 
made faster by sorting by inode number.)

P.S. if you want to fit one extra pointer in the array, an array index
identifying the first unused slot is distinguishable from a pointer,
so if the last slot is a pointer, the page is full.  If it's an index,
the page is not full.

Re: Is there a reason we don't have kvfree_rcu()?

[Paul E. McKenney]

On Fri, Mar 13, 2020 at 04:52:19PM +0000, George Spelvin wrote:
> On Fri, Mar 13, 2020 at 06:54:00AM -0700, Paul E. McKenney wrote:
> > I would guess that sorting them before the grace period might improve
> > cache locality and thus performance.  So it does seem like an excellent
> > thing to try, at the very least as an experiment.
> 
> That doesn't seem at all obvious.  Processing them in separate batches
> would improve I-cache locality, but you could sort them after the
> grace period just as well as before.  Especially if you have arrays of 
> 500 pointers to work with.
> 
> Indeed, one thing that seems worth trying is sorting by address, which 
> would improve D-cache locality, since you have a significant chance for 
> consecutive frees to be in the same slab or otherwise reference the same 
> overhead data structures.
> 
> Sorting by (address - VMALLOC_START) automatically groups the vallocated 
> poiners together at the front, too.  Since there's no vfree_bulk, you can 
> iterate over them until you run out, then kfree_bulk the rest.
> 
> (This idea came from a memory that bulk file operations can be 
> made faster by sorting by inode number.)
> 
> P.S. if you want to fit one extra pointer in the array, an array index
> identifying the first unused slot is distinguishable from a pointer,
> so if the last slot is a pointer, the page is full.  If it's an index,
> the page is not full.

Another approach would be to terminate with a NULL pointer, or with the
end of the array, as the case may be.

							Thanx, Paul

Re: Is there a reason we don't have kvfree_rcu()?

[George Spelvin]

On Fri, Mar 13, 2020 at 11:19:17AM -0700, Paul E. McKenney wrote:
> Another approach would be to terminate with a NULL pointer, or with the
> end of the array, as the case may be.

That's the basic idea, but you want to be able to append a pointer
in O(1) time, and a simple null-termination requires a linear search.

It's obfuscation for negligible gain, however, so I'm sorry I
bothered mentioning it.

Re: Is there a reason we don't have kvfree_rcu()?

[Paul E. McKenney]

On Fri, Mar 13, 2020 at 06:46:41PM +0000, George Spelvin wrote:
> On Fri, Mar 13, 2020 at 11:19:17AM -0700, Paul E. McKenney wrote:
> > Another approach would be to terminate with a NULL pointer, or with the
> > end of the array, as the case may be.
> 
> That's the basic idea, but you want to be able to append a pointer
> in O(1) time, and a simple null-termination requires a linear search.

Fair point!

> It's obfuscation for negligible gain, however, so I'm sorry I
> bothered mentioning it.

I am with you on keeping it simple, especially initially, all evidence
to the contrary notwithstanding.

							Thanx, Paul