On Mon, Aug 19, 2024 at 11:14:02AM -0400, Kent Overstreet wrote: > On Mon, Aug 19, 2024 at 07:03:05AM GMT, Paul E. McKenney wrote: > > On Mon, Aug 19, 2024 at 12:46:34AM -0400, Kent Overstreet wrote: > > > On Sun, Aug 18, 2024 at 09:40:27PM GMT, Paul E. McKenney wrote: > > > > On Mon, Aug 19, 2024 at 12:16:42AM -0400, Kent Overstreet wrote: > > > > > You can't use a fixed number of callback heads if there's going to be an > > > > > unbounded number of callback heads outstanding. > > > > > > > > The number of rcu_head structures is your choice, based on your choice > > > > of data structure. You can for example link together data elements that > > > > have the same value of get_state_synchronize_rcu() cookie, and use a > > > > single rcu_head structure for that group. You could then do whatever > > > > you want for the linking. > > > > > > > > But even if you do choose to have a large number of rcu_head structures, > > > > perhaps one per data element, there is no law saying that each and every > > > > one of them needs to be passed to call_rcu(). For example, kfree_rcu() > > > > requires an rcu_head structure in the objects passed to it, but in the > > > > common (non-OOM) case, those structures go unused in favor of pages > > > > of pointers. > > > > > > > > So what were you really trying to get across to me here? > > > > > > Like I said, this needs to run in a fixed amount of memory, so your > > > proposed algorithm doesn't work for having one rcu_head per seq with > > > pending objects. > > > > Please define "fixed amount of memory" in this context. Given the > > information you have provided me, you might mean any number of things, > > including the following: > > > > 1. An upper bound on the time from the end of a grace period to > > the point at which you are notified of the end of that grace > > period. > > > > 2. An upper bound on the time from the end of a grace period to > > the point at which you are notified of the end of that grace > > period when there is a "flood" of blocks of memory that start > > waiting for their grace period. > > > > 3. An upper bound on the memory waiting to be freed as a function > > of the maximum duration of any reader, assuming some maximum rate > > at which blocks of memory start waiting for their grace period. > > > > 4. An upper bound on the memory waiting to be freed as a function > > of the maximum duration of any reader, independent of the rate > > at which blocks of memory start waiting for their grace period. > > > > 5. A guarantee that any block that is not actively in use by some > > reader can be freed, albeit at some additional read-side and > > update-side expense, and some added read-side complexity. > > > > 6. Beyond this point, as far as I know, you would need to be living > > in a different universe having rather different laws of physics. > > > > The definition I was working with is #2 above. > > No, none of those - you're overthinking. Just in case there is any doubt, I have a somewhat different interpretation of our interaction. ;-) > As I keep saying, it's about > tracking _pending objects for different grace period sequence numbers_. > The number of outstanding grace period sequence numbers is the thing we > need a bound on. By "number of outstanding grace period sequence numbers" you mean the number of outstanding grace period sequence numbers that have memory blocks that have not yet been processed? If so, how could that possibly matter more than the total number of memory blocks that have not been processed, regardless of which grace-period number they are associated with? Why would a huge number of memory blocks fail to cause an OOM simply because they happen to be associated with a single grace-period number? Or, to put it another way, suppose that same number of memory blocks were distributed over a large number of grace-period sequence numbers? How could this possibly cause an OOM to be more likely than if the same nubmer of memory blocks were associated with a single grace-period number? > This will be clearer when I post code, probably later today. Nevertheless, I look forward to seeing what you come up with. Thanx, Paul
