[RFC] fsnotify: allow sleepable child dentry flag update

  Hi Jan, Amir, Al - this is a quite ugly patch but I want to discuss the idea
behind it, to see whether we can find something workable. I apologize for the
length of text here, but I think it's necessary to give full context and ideas.

For background, on machines with lots of memory and weird workloads,
__fsnotify_update_child_dentry_flags() has been a real thorn in our side. It
grabs a couple spinlocks and iterates over the whole d_subdirs list. If that
list is long, this can take a while. The list can be long due to lots of
negative dentries (which can easily number in the hundreds of millions if you
have a process that's relatively frequently looking up nonexisting files). But
the list can also be long due to *positive* dentries. I've seen directories with
~7 million positive dentry children falling victim to this function before (XFS
allows lots of files per dir)! Positive dentries take longer to process in this
function (since they're actually locked and written to), so you don't need as
many for them to be a problem.

Anyway, if you have a huge d_subdirs list, then you can have problems with soft
lockups. From my measurements with ftrace, 100 million negative dentries means
that the function takes about 6 seconds to complete (varies wildly by CPU and
kernel config/version). That's bad, but it can get *much worse*. Imagine that
there are many frequently accessed files in such a directory, and you have an
inotify watch. As soon as that watch is removed, the last fsnotify connector
goes away, and i_fsnotify_mask becomes 0. System calls accessing dentries still
see DCACHE_FSNOTIFY_PARENT_WATCHED, so they fall into __fsnotify_parent and will
try to update the dentry flags. In my experience, a thundering herd of CPUs race
to __fsnotify_update_child_dentry_flags(). The winner begins updating and the
rest spin waiting for the parent inode's i_lock. Many CPUs make it to that
point, and they *all* will proceed to iterate through d_subdirs, regardless of
how long the list is, even though only the first CPU needed to do it. So now
your 6 second spin gets multiplied by 5-10. And since the directory is
frequently accessed, all the dget/dputs from other CPUs will all spin for this
long time. This amounts to a nearly unusable system.

Previously I've tried to generally limit or manage the number of negative
dentries in the dcache, which as a general problem is very difficult to get
concensus on. I've also tried the patches to reorder dentries in d_subdirs so
negative dentries are at the end, which has some difficult issues interacting
with d_walk. Neither of those ideas would help for a directory full of positive
dentries either.

So I have two more narrowly scoped strategies to improve the situation. Both are
included in the hacky, awful patch below.

First, is to let __fsnotify_update_child_dentry_flags() sleep. This means nobody
is holding the spinlock for several seconds at a time. We can actually achieve
this via a cursor, the same way that simple_readdir() is implemented. I think
this might require moving the declaration of d_alloc_cursor() and maybe
exporting it. I had to #include fs/internal.h which is not ok.

On its own, that actually makes problems worse, because it allows several tasks
to update at the same time, and they're constantly locking/unlocking, which
makes contention worse.

So second is to add an inode flag saying that
__fsnotify_update_child_dentry_flags() is already in progress. This prevents
concurrent execution, and it allows the caller to skip updating since they know
it's being handled, so it eliminates the thundering herd problem.

The patch works great! It eliminates the chances of soft lockups and makes the
system responsive under those weird loads. But now, I know I've added a new
issue. Updating dentry flags is no longer atomic, and we've lost the guarantee
that after fsnotify_recalc_mask(), child dentries are all flagged when
necessary. It's possible that after __fsnotify_update_child_dentry_flags() will
skip executing since it sees it's already happening, and inotify_add_watch()
would return without the watch being fully ready.

I think the approach can still be salvaged, we just need a way to resolve this.
EG a wait queue or mutex in the connector would allow us to preserve the
guarantee that the child dentries are flagged when necessary. But I know that's
a big addition, so I wanted to get some feedback from you as the maintainers. Is
the strategy here stupid? Am I missing an easier option? Is some added
synchronization in the connector workable?

Thanks!
Stephen

---

You may find it useful to create negative dentries with [1] while using this
patch. Create 100 million dentries as follows. Then use [2] to create userspace
load that's accessing files in the same directory. Finally, inotifywait will
setup a watch, terminate after one event, and tear it down. Without the patch,
the thundering herd of userspace tasks all line up to update the flags, and
lockup the system.

  ./negdentcreate -p /tmp/dir -c 100000000 -t 4
  touch /tmp/dir/file{1..10}
  for i in {1..10}; do ./openclose /tmp/dir/file$i & done
  inotifywait /tmp/dir

[1] https://github.com/brenns10/kernel_stuff/tree/master/negdentcreate
[2] https://github.com/brenns10/kernel_stuff/tree/master/openclose

 fs/notify/fsnotify.c | 96 ++++++++++++++++++++++++++++++++++----------
 include/linux/fs.h   |  4 ++
 2 files changed, 78 insertions(+), 22 deletions(-)
  

On Thu, Oct 13, 2022 at 03:27:19PM -0700, Stephen Brennan wrote:

> So I have two more narrowly scoped strategies to improve the situation. Both are
> included in the hacky, awful patch below.
> 
> First, is to let __fsnotify_update_child_dentry_flags() sleep. This means nobody
> is holding the spinlock for several seconds at a time. We can actually achieve
> this via a cursor, the same way that simple_readdir() is implemented. I think
> this might require moving the declaration of d_alloc_cursor() and maybe
> exporting it. I had to #include fs/internal.h which is not ok.

Er...  Won't that expose every filesystem to having to deal with cursors?
Currently it's entirely up to the filesystem in question and I wouldn't
be a dime on everyone being ready to cope with such surprises...
  

On Fri, Oct 14, 2022 at 1:27 AM Stephen Brennan
<stephen.s.brennan@oracle.com> wrote:
>
> Hi Jan, Amir, Al - this is a quite ugly patch but I want to discuss the idea
> behind it, to see whether we can find something workable. I apologize for the
> length of text here, but I think it's necessary to give full context and ideas.
>

Hi Stephen!

> For background, on machines with lots of memory and weird workloads,
> __fsnotify_update_child_dentry_flags() has been a real thorn in our side. It
> grabs a couple spinlocks and iterates over the whole d_subdirs list. If that
> list is long, this can take a while. The list can be long due to lots of
> negative dentries (which can easily number in the hundreds of millions if you
> have a process that's relatively frequently looking up nonexisting files). But
> the list can also be long due to *positive* dentries. I've seen directories with
> ~7 million positive dentry children falling victim to this function before (XFS
> allows lots of files per dir)! Positive dentries take longer to process in this
> function (since they're actually locked and written to), so you don't need as
> many for them to be a problem.
>
> Anyway, if you have a huge d_subdirs list, then you can have problems with soft
> lockups. From my measurements with ftrace, 100 million negative dentries means
> that the function takes about 6 seconds to complete (varies wildly by CPU and
> kernel config/version). That's bad, but it can get *much worse*. Imagine that
> there are many frequently accessed files in such a directory, and you have an
> inotify watch. As soon as that watch is removed, the last fsnotify connector
> goes away, and i_fsnotify_mask becomes 0. System calls accessing dentries still
> see DCACHE_FSNOTIFY_PARENT_WATCHED, so they fall into __fsnotify_parent and will
> try to update the dentry flags. In my experience, a thundering herd of CPUs race
> to __fsnotify_update_child_dentry_flags(). The winner begins updating and the
> rest spin waiting for the parent inode's i_lock. Many CPUs make it to that
> point, and they *all* will proceed to iterate through d_subdirs, regardless of
> how long the list is, even though only the first CPU needed to do it. So now
> your 6 second spin gets multiplied by 5-10. And since the directory is
> frequently accessed, all the dget/dputs from other CPUs will all spin for this
> long time. This amounts to a nearly unusable system.
>
> Previously I've tried to generally limit or manage the number of negative
> dentries in the dcache, which as a general problem is very difficult to get
> concensus on. I've also tried the patches to reorder dentries in d_subdirs so
> negative dentries are at the end, which has some difficult issues interacting
> with d_walk. Neither of those ideas would help for a directory full of positive
> dentries either.
>
> So I have two more narrowly scoped strategies to improve the situation. Both are
> included in the hacky, awful patch below.
>
> First, is to let __fsnotify_update_child_dentry_flags() sleep. This means nobody
> is holding the spinlock for several seconds at a time. We can actually achieve
> this via a cursor, the same way that simple_readdir() is implemented. I think
> this might require moving the declaration of d_alloc_cursor() and maybe
> exporting it. I had to #include fs/internal.h which is not ok.
>
> On its own, that actually makes problems worse, because it allows several tasks
> to update at the same time, and they're constantly locking/unlocking, which
> makes contention worse.
>
> So second is to add an inode flag saying that
> __fsnotify_update_child_dentry_flags() is already in progress. This prevents
> concurrent execution, and it allows the caller to skip updating since they know
> it's being handled, so it eliminates the thundering herd problem.
>
> The patch works great! It eliminates the chances of soft lockups and makes the
> system responsive under those weird loads. But now, I know I've added a new
> issue. Updating dentry flags is no longer atomic, and we've lost the guarantee

Just between us ;) the update of the inode event mask is not atomic anyway,
because the test for 'parent_watched' and fsnotify_inode_watches_children()
in __fsnotify_parent() are done without any memory access synchronization.

IOW, the only guarantee for users is that *sometime* after adding events
to a mark mask, events will start being delivered and *sometime* after
removing events from a mark mask, events will stop being delivered.
Some events may have implicit memory barriers that make event delivery
more deterministic, but others may not.

This may not be considered an issue for asynchronous events, but actually,
for permission events, I would like to fix that.
To understand my motivations you can look at:
https://github.com/amir73il/fsnotify-utils/wiki/Hierarchical-Storage-Management-API#Evicting_file_content

> that after fsnotify_recalc_mask(), child dentries are all flagged when
> necessary. It's possible that after __fsnotify_update_child_dentry_flags() will
> skip executing since it sees it's already happening, and inotify_add_watch()
> would return without the watch being fully ready.
>
> I think the approach can still be salvaged, we just need a way to resolve this.
> EG a wait queue or mutex in the connector would allow us to preserve the
> guarantee that the child dentries are flagged when necessary. But I know that's
> a big addition, so I wanted to get some feedback from you as the maintainers. Is
> the strategy here stupid? Am I missing an easier option?

I think you may be missing an easier option.

The call to __fsnotify_update_child_dentry_flags() in
__fsnotify_parent() is a very aggressive optimization
and I think it may be an overkill, and a footgun, according
to your analysis.

If only called from the context of fsnotify_recalc_mask()
(i.e. update mark mask), __fsnotify_update_child_dentry_flags()
can take the dir inode_lock() to synchronize.

I don't think that the dir inode spin lock needs to be held
at all during children iteration.

I think that d_find_any_alias() should be used to obtain
the alias with elevated refcount instead of the awkward
d_u.d_alias iteration loop.

In the context of __fsnotify_parent(), I think the optimization
should stick with updating the flags for the specific child dentry
that had the false positive parent_watched indication,
leaving the rest of the siblings alone.

Would that address the performance issues of your workload?

Jan,

Can you foresee any problems with this change?

Thanks,
Amir.
  

Amir Goldstein <amir73il@gmail.com> writes:
> On Fri, Oct 14, 2022 at 1:27 AM Stephen Brennan
> <stephen.s.brennan@oracle.com> wrote:
>>
>> Hi Jan, Amir, Al - this is a quite ugly patch but I want to discuss the idea
>> behind it, to see whether we can find something workable. I apologize for the
>> length of text here, but I think it's necessary to give full context and ideas.
>>
>
> Hi Stephen!
>
>> For background, on machines with lots of memory and weird workloads,
>> __fsnotify_update_child_dentry_flags() has been a real thorn in our side. It
>> grabs a couple spinlocks and iterates over the whole d_subdirs list. If that
>> list is long, this can take a while. The list can be long due to lots of
>> negative dentries (which can easily number in the hundreds of millions if you
>> have a process that's relatively frequently looking up nonexisting files). But
>> the list can also be long due to *positive* dentries. I've seen directories with
>> ~7 million positive dentry children falling victim to this function before (XFS
>> allows lots of files per dir)! Positive dentries take longer to process in this
>> function (since they're actually locked and written to), so you don't need as
>> many for them to be a problem.
>>
>> Anyway, if you have a huge d_subdirs list, then you can have problems with soft
>> lockups. From my measurements with ftrace, 100 million negative dentries means
>> that the function takes about 6 seconds to complete (varies wildly by CPU and
>> kernel config/version). That's bad, but it can get *much worse*. Imagine that
>> there are many frequently accessed files in such a directory, and you have an
>> inotify watch. As soon as that watch is removed, the last fsnotify connector
>> goes away, and i_fsnotify_mask becomes 0. System calls accessing dentries still
>> see DCACHE_FSNOTIFY_PARENT_WATCHED, so they fall into __fsnotify_parent and will
>> try to update the dentry flags. In my experience, a thundering herd of CPUs race
>> to __fsnotify_update_child_dentry_flags(). The winner begins updating and the
>> rest spin waiting for the parent inode's i_lock. Many CPUs make it to that
>> point, and they *all* will proceed to iterate through d_subdirs, regardless of
>> how long the list is, even though only the first CPU needed to do it. So now
>> your 6 second spin gets multiplied by 5-10. And since the directory is
>> frequently accessed, all the dget/dputs from other CPUs will all spin for this
>> long time. This amounts to a nearly unusable system.
>>
>> Previously I've tried to generally limit or manage the number of negative
>> dentries in the dcache, which as a general problem is very difficult to get
>> concensus on. I've also tried the patches to reorder dentries in d_subdirs so
>> negative dentries are at the end, which has some difficult issues interacting
>> with d_walk. Neither of those ideas would help for a directory full of positive
>> dentries either.
>>
>> So I have two more narrowly scoped strategies to improve the situation. Both are
>> included in the hacky, awful patch below.
>>
>> First, is to let __fsnotify_update_child_dentry_flags() sleep. This means nobody
>> is holding the spinlock for several seconds at a time. We can actually achieve
>> this via a cursor, the same way that simple_readdir() is implemented. I think
>> this might require moving the declaration of d_alloc_cursor() and maybe
>> exporting it. I had to #include fs/internal.h which is not ok.
>>
>> On its own, that actually makes problems worse, because it allows several tasks
>> to update at the same time, and they're constantly locking/unlocking, which
>> makes contention worse.
>>
>> So second is to add an inode flag saying that
>> __fsnotify_update_child_dentry_flags() is already in progress. This prevents
>> concurrent execution, and it allows the caller to skip updating since they know
>> it's being handled, so it eliminates the thundering herd problem.
>>
>> The patch works great! It eliminates the chances of soft lockups and makes the
>> system responsive under those weird loads. But now, I know I've added a new
>> issue. Updating dentry flags is no longer atomic, and we've lost the guarantee
>
> Just between us ;) the update of the inode event mask is not atomic anyway,
> because the test for 'parent_watched' and fsnotify_inode_watches_children()
> in __fsnotify_parent() are done without any memory access synchronization.
>
> IOW, the only guarantee for users is that *sometime* after adding events
> to a mark mask, events will start being delivered and *sometime* after
> removing events from a mark mask, events will stop being delivered.
> Some events may have implicit memory barriers that make event delivery
> more deterministic, but others may not.

I did wonder about whether it was truly atomic even without the
sleeping... the sleeping just makes matters much worse. But without the
sleeping, I feel like it wouldn't take much memory synchronization.
The dentry flags modification is protected by a spinlock, I assume we
would just need a memory barrier to pair with the unlock?

(But then again, I really need to read and then reread the memory model
document, and think about it when it's not late for me.)

> This may not be considered an issue for asynchronous events, but actually,
> for permission events, I would like to fix that.
> To understand my motivations you can look at:
> https://github.com/amir73il/fsnotify-utils/wiki/Hierarchical-Storage-Management-API#Evicting_file_content

I'll take a deeper look in (my) morning! It definitely helps for me to
better understand use cases since I really don't know much beyond
inotify.

>> that after fsnotify_recalc_mask(), child dentries are all flagged when
>> necessary. It's possible that after __fsnotify_update_child_dentry_flags() will
>> skip executing since it sees it's already happening, and inotify_add_watch()
>> would return without the watch being fully ready.
>>
>> I think the approach can still be salvaged, we just need a way to resolve this.
>> EG a wait queue or mutex in the connector would allow us to preserve the
>> guarantee that the child dentries are flagged when necessary. But I know that's
>> a big addition, so I wanted to get some feedback from you as the maintainers. Is
>> the strategy here stupid? Am I missing an easier option?
>
> I think you may be missing an easier option.
>
> The call to __fsnotify_update_child_dentry_flags() in
> __fsnotify_parent() is a very aggressive optimization
> and I think it may be an overkill, and a footgun, according
> to your analysis.

Agreed!

> If only called from the context of fsnotify_recalc_mask()
> (i.e. update mark mask), __fsnotify_update_child_dentry_flags()
> can take the dir inode_lock() to synchronize.
>
> I don't think that the dir inode spin lock needs to be held
> at all during children iteration.

Definitely a sleeping lock is better than the spin lock. And if we did
something like that, it would be worth keeping a little bit of state in
the connector to keep track of whether the dentry flags are set or not.
This way, if several marks are added in a row, you don't repeatedly
iterate over the children to do the same operation over and over again.

No matter what, we have to hold the parent dentry's spinlock, and that's
expensive. So if we can make the update happen only when it would
actually enable or disable the flags, that's worth a few bits of state.

> I think that d_find_any_alias() should be used to obtain
> the alias with elevated refcount instead of the awkward
> d_u.d_alias iteration loop.

D'oh! Much better idea :)
Do you think the BUG_ON would still be worthwhile?

> In the context of __fsnotify_parent(), I think the optimization
> should stick with updating the flags for the specific child dentry
> that had the false positive parent_watched indication,
> leaving the rest of 

> WOULD that address the performance issues of your workload?

I think synchronizing the __fsnotify_update_child_dentry_flags() with a
mutex and getting rid of the call from __fsnotify_parent() would go a
*huge* way (maybe 80%?) towards resolving the performance issues we've
seen. To be clear, I'm representing not one single workload, but a few
different customer workloads which center around this area.

There are some extreme cases I've seen, where the dentry list is so
huge, that even iterating over it once with the parent dentry spinlock
held is enough to trigger softlockups - no need for several calls to
__fsnotify_update_child_dentry_flags() queueing up as described in the
original mail. So ideally, I'd love to try make *something* work with
the cursor idea as well. But I think the two ideas can be separated
easily, and I can discuss with Al further about if cursors can be
salvaged at all.

Thanks so much for the detailed look at this!
Stephen
  

Hi guys!

On Fri 14-10-22 11:01:39, Amir Goldstein wrote:
> On Fri, Oct 14, 2022 at 1:27 AM Stephen Brennan
> <stephen.s.brennan@oracle.com> wrote:
> >
> > Hi Jan, Amir, Al - this is a quite ugly patch but I want to discuss the idea
> > behind it, to see whether we can find something workable. I apologize for the
> > length of text here, but I think it's necessary to give full context and ideas.
> 
> > For background, on machines with lots of memory and weird workloads,
> > __fsnotify_update_child_dentry_flags() has been a real thorn in our side. It
> > grabs a couple spinlocks and iterates over the whole d_subdirs list. If that
> > list is long, this can take a while. The list can be long due to lots of
> > negative dentries (which can easily number in the hundreds of millions if you
> > have a process that's relatively frequently looking up nonexisting files). But
> > the list can also be long due to *positive* dentries. I've seen directories with
> > ~7 million positive dentry children falling victim to this function before (XFS
> > allows lots of files per dir)! Positive dentries take longer to process in this
> > function (since they're actually locked and written to), so you don't need as
> > many for them to be a problem.
> >
> > Anyway, if you have a huge d_subdirs list, then you can have problems with soft
> > lockups. From my measurements with ftrace, 100 million negative dentries means
> > that the function takes about 6 seconds to complete (varies wildly by CPU and
> > kernel config/version). That's bad, but it can get *much worse*. Imagine that
> > there are many frequently accessed files in such a directory, and you have an
> > inotify watch. As soon as that watch is removed, the last fsnotify connector
> > goes away, and i_fsnotify_mask becomes 0. System calls accessing dentries still
> > see DCACHE_FSNOTIFY_PARENT_WATCHED, so they fall into __fsnotify_parent and will
> > try to update the dentry flags. In my experience, a thundering herd of CPUs race
> > to __fsnotify_update_child_dentry_flags(). The winner begins updating and the
> > rest spin waiting for the parent inode's i_lock. Many CPUs make it to that
> > point, and they *all* will proceed to iterate through d_subdirs, regardless of
> > how long the list is, even though only the first CPU needed to do it. So now
> > your 6 second spin gets multiplied by 5-10. And since the directory is
> > frequently accessed, all the dget/dputs from other CPUs will all spin for this
> > long time. This amounts to a nearly unusable system.
> >
> > Previously I've tried to generally limit or manage the number of negative
> > dentries in the dcache, which as a general problem is very difficult to get
> > concensus on. I've also tried the patches to reorder dentries in d_subdirs so
> > negative dentries are at the end, which has some difficult issues interacting
> > with d_walk. Neither of those ideas would help for a directory full of positive
> > dentries either.
> >
> > So I have two more narrowly scoped strategies to improve the situation. Both are
> > included in the hacky, awful patch below.
> >
> > First, is to let __fsnotify_update_child_dentry_flags() sleep. This means nobody
> > is holding the spinlock for several seconds at a time. We can actually achieve
> > this via a cursor, the same way that simple_readdir() is implemented. I think
> > this might require moving the declaration of d_alloc_cursor() and maybe
> > exporting it. I had to #include fs/internal.h which is not ok.
> >
> > On its own, that actually makes problems worse, because it allows several tasks
> > to update at the same time, and they're constantly locking/unlocking, which
> > makes contention worse.
> >
> > So second is to add an inode flag saying that
> > __fsnotify_update_child_dentry_flags() is already in progress. This prevents
> > concurrent execution, and it allows the caller to skip updating since they know
> > it's being handled, so it eliminates the thundering herd problem.
> >
> > The patch works great! It eliminates the chances of soft lockups and makes the
> > system responsive under those weird loads. But now, I know I've added a new
> > issue. Updating dentry flags is no longer atomic, and we've lost the guarantee
> 
> Just between us ;) the update of the inode event mask is not atomic anyway,
> because the test for 'parent_watched' and fsnotify_inode_watches_children()
> in __fsnotify_parent() are done without any memory access synchronization.
> 
> IOW, the only guarantee for users is that *sometime* after adding events
> to a mark mask, events will start being delivered and *sometime* after
> removing events from a mark mask, events will stop being delivered.
> Some events may have implicit memory barriers that make event delivery
> more deterministic, but others may not.

This holds even for fsnotify_inode_watches_children() call in
__fsnotify_update_child_dentry_flags(). In principle we can have racing
calls to __fsnotify_update_child_dentry_flags() which result in temporary
inconsistency of child dentry flags with the mask in parent's connector.

> > that after fsnotify_recalc_mask(), child dentries are all flagged when
> > necessary. It's possible that after __fsnotify_update_child_dentry_flags() will
> > skip executing since it sees it's already happening, and inotify_add_watch()
> > would return without the watch being fully ready.
> >
> > I think the approach can still be salvaged, we just need a way to resolve this.
> > EG a wait queue or mutex in the connector would allow us to preserve the
> > guarantee that the child dentries are flagged when necessary. But I know that's
> > a big addition, so I wanted to get some feedback from you as the maintainers. Is
> > the strategy here stupid? Am I missing an easier option?
> 
> I think you may be missing an easier option.
> 
> The call to __fsnotify_update_child_dentry_flags() in
> __fsnotify_parent() is a very aggressive optimization
> and I think it may be an overkill, and a footgun, according
> to your analysis.
> 
> If only called from the context of fsnotify_recalc_mask()
> (i.e. update mark mask), __fsnotify_update_child_dentry_flags()
> can take the dir inode_lock() to synchronize.

This will nest inode lock into fsnotify group lock though. I'm not aware of
any immediate lock ordering problem with that but it might be problematic.
Otherwise this seems workable.

BTW if we call __fsnotify_update_child_dentry_flags() only from
fsnotify_recalc_mask(), I don't think we even need more state in the
connector to detect whether dentry flags update is needed or not.
fsnotify_recalc_mask() knows the old & new mask state so it has all the
information it needs to detect whether dentry flags update is needed or
not. We just have to resolve the flags update races first to avoid
maintaining the inconsistent flags state for a long time.

> I don't think that the dir inode spin lock needs to be held
> at all during children iteration.
> 
> I think that d_find_any_alias() should be used to obtain
> the alias with elevated refcount instead of the awkward
> d_u.d_alias iteration loop.
> 
> In the context of __fsnotify_parent(), I think the optimization
> should stick with updating the flags for the specific child dentry
> that had the false positive parent_watched indication,
> leaving the rest of the siblings alone.

Yep, that looks sensible to me. Essentially this should be just an uncommon
fixup path until the full child dentry walk from fsnotify_recalc_mask()
catches up with synchronizing all child dentry flags.

								Honza
  

On Mon, Oct 17, 2022 at 10:59 AM Stephen Brennan
<stephen.s.brennan@oracle.com> wrote:
>
> Amir Goldstein <amir73il@gmail.com> writes:
> > On Fri, Oct 14, 2022 at 1:27 AM Stephen Brennan
> > <stephen.s.brennan@oracle.com> wrote:
> >>
> >> Hi Jan, Amir, Al - this is a quite ugly patch but I want to discuss the idea
> >> behind it, to see whether we can find something workable. I apologize for the
> >> length of text here, but I think it's necessary to give full context and ideas.
> >>
> >
> > Hi Stephen!
> >
> >> For background, on machines with lots of memory and weird workloads,
> >> __fsnotify_update_child_dentry_flags() has been a real thorn in our side. It
> >> grabs a couple spinlocks and iterates over the whole d_subdirs list. If that
> >> list is long, this can take a while. The list can be long due to lots of
> >> negative dentries (which can easily number in the hundreds of millions if you
> >> have a process that's relatively frequently looking up nonexisting files). But
> >> the list can also be long due to *positive* dentries. I've seen directories with
> >> ~7 million positive dentry children falling victim to this function before (XFS
> >> allows lots of files per dir)! Positive dentries take longer to process in this
> >> function (since they're actually locked and written to), so you don't need as
> >> many for them to be a problem.
> >>
> >> Anyway, if you have a huge d_subdirs list, then you can have problems with soft
> >> lockups. From my measurements with ftrace, 100 million negative dentries means
> >> that the function takes about 6 seconds to complete (varies wildly by CPU and
> >> kernel config/version). That's bad, but it can get *much worse*. Imagine that
> >> there are many frequently accessed files in such a directory, and you have an
> >> inotify watch. As soon as that watch is removed, the last fsnotify connector
> >> goes away, and i_fsnotify_mask becomes 0. System calls accessing dentries still
> >> see DCACHE_FSNOTIFY_PARENT_WATCHED, so they fall into __fsnotify_parent and will
> >> try to update the dentry flags. In my experience, a thundering herd of CPUs race
> >> to __fsnotify_update_child_dentry_flags(). The winner begins updating and the
> >> rest spin waiting for the parent inode's i_lock. Many CPUs make it to that
> >> point, and they *all* will proceed to iterate through d_subdirs, regardless of
> >> how long the list is, even though only the first CPU needed to do it. So now
> >> your 6 second spin gets multiplied by 5-10. And since the directory is
> >> frequently accessed, all the dget/dputs from other CPUs will all spin for this
> >> long time. This amounts to a nearly unusable system.
> >>
> >> Previously I've tried to generally limit or manage the number of negative
> >> dentries in the dcache, which as a general problem is very difficult to get
> >> concensus on. I've also tried the patches to reorder dentries in d_subdirs so
> >> negative dentries are at the end, which has some difficult issues interacting
> >> with d_walk. Neither of those ideas would help for a directory full of positive
> >> dentries either.
> >>
> >> So I have two more narrowly scoped strategies to improve the situation. Both are
> >> included in the hacky, awful patch below.
> >>
> >> First, is to let __fsnotify_update_child_dentry_flags() sleep. This means nobody
> >> is holding the spinlock for several seconds at a time. We can actually achieve
> >> this via a cursor, the same way that simple_readdir() is implemented. I think
> >> this might require moving the declaration of d_alloc_cursor() and maybe
> >> exporting it. I had to #include fs/internal.h which is not ok.
> >>
> >> On its own, that actually makes problems worse, because it allows several tasks
> >> to update at the same time, and they're constantly locking/unlocking, which
> >> makes contention worse.
> >>
> >> So second is to add an inode flag saying that
> >> __fsnotify_update_child_dentry_flags() is already in progress. This prevents
> >> concurrent execution, and it allows the caller to skip updating since they know
> >> it's being handled, so it eliminates the thundering herd problem.
> >>
> >> The patch works great! It eliminates the chances of soft lockups and makes the
> >> system responsive under those weird loads. But now, I know I've added a new
> >> issue. Updating dentry flags is no longer atomic, and we've lost the guarantee
> >
> > Just between us ;) the update of the inode event mask is not atomic anyway,
> > because the test for 'parent_watched' and fsnotify_inode_watches_children()
> > in __fsnotify_parent() are done without any memory access synchronization.
> >
> > IOW, the only guarantee for users is that *sometime* after adding events
> > to a mark mask, events will start being delivered and *sometime* after
> > removing events from a mark mask, events will stop being delivered.
> > Some events may have implicit memory barriers that make event delivery
> > more deterministic, but others may not.
>
> I did wonder about whether it was truly atomic even without the
> sleeping... the sleeping just makes matters much worse. But without the
> sleeping, I feel like it wouldn't take much memory synchronization.
> The dentry flags modification is protected by a spinlock, I assume we
> would just need a memory barrier to pair with the unlock?
>

Haha "just" cannot be used here :)
Yes, some sort of memory barrier is missing.
The trick is not hurting performance in the common fast path
where the event subscription mask has not been changed.

This is especially true considering that all applications to date
did just fine without atomic semantics for updating mark masks.
Some applications may have been living in blissful ignorance ...

> (But then again, I really need to read and then reread the memory model
> document, and think about it when it's not late for me.)
>
> > This may not be considered an issue for asynchronous events, but actually,
> > for permission events, I would like to fix that.
> > To understand my motivations you can look at:
> > https://github.com/amir73il/fsnotify-utils/wiki/Hierarchical-Storage-Management-API#Evicting_file_content
>
> I'll take a deeper look in (my) morning! It definitely helps for me to
> better understand use cases since I really don't know much beyond
> inotify.
>

Don't stress yourself over this doc, it's a WIP, but it describes
a system where the atomic update of mark masks would be
important for correctness.

The document does provide a method of working around
the atomic mask update requirement (making sure that
sb event mask includes the needed event), which should be
good enough for the described use case.

> >> that after fsnotify_recalc_mask(), child dentries are all flagged when
> >> necessary. It's possible that after __fsnotify_update_child_dentry_flags() will
> >> skip executing since it sees it's already happening, and inotify_add_watch()
> >> would return without the watch being fully ready.
> >>
> >> I think the approach can still be salvaged, we just need a way to resolve this.
> >> EG a wait queue or mutex in the connector would allow us to preserve the
> >> guarantee that the child dentries are flagged when necessary. But I know that's
> >> a big addition, so I wanted to get some feedback from you as the maintainers. Is
> >> the strategy here stupid? Am I missing an easier option?
> >
> > I think you may be missing an easier option.
> >
> > The call to __fsnotify_update_child_dentry_flags() in
> > __fsnotify_parent() is a very aggressive optimization
> > and I think it may be an overkill, and a footgun, according
> > to your analysis.
>
> Agreed!
>
> > If only called from the context of fsnotify_recalc_mask()
> > (i.e. update mark mask), __fsnotify_update_child_dentry_flags()
> > can take the dir inode_lock() to synchronize.
> >
> > I don't think that the dir inode spin lock needs to be held
> > at all during children iteration.
>
> Definitely a sleeping lock is better than the spin lock. And if we did
> something like that, it would be worth keeping a little bit of state in
> the connector to keep track of whether the dentry flags are set or not.
> This way, if several marks are added in a row, you don't repeatedly
> iterate over the children to do the same operation over and over again.
>
> No matter what, we have to hold the parent dentry's spinlock, and that's
> expensive. So if we can make the update happen only when it would
> actually enable or disable the flags, that's worth a few bits of state.
>

As Jan wrote, this state already exists in i_fsnotify_mask.
fsnotify_recalc_mask() is very capable of knowing when the
state described by fsnotify_inode_watches_children() is
going to change.

> > I think that d_find_any_alias() should be used to obtain
> > the alias with elevated refcount instead of the awkward
> > d_u.d_alias iteration loop.
>
> D'oh! Much better idea :)
> Do you think the BUG_ON would still be worthwhile?
>

Which BUG_ON()?
In general no, if there are ever more multiple aliases for
a directory inode, updating dentry flags would be the last
of our problems.


> > In the context of __fsnotify_parent(), I think the optimization
> > should stick with updating the flags for the specific child dentry
> > that had the false positive parent_watched indication,
> > leaving the rest of
>
> > WOULD that address the performance issues of your workload?
>
> I think synchronizing the __fsnotify_update_child_dentry_flags() with a
> mutex and getting rid of the call from __fsnotify_parent() would go a
> *huge* way (maybe 80%?) towards resolving the performance issues we've
> seen. To be clear, I'm representing not one single workload, but a few
> different customer workloads which center around this area.
>
> There are some extreme cases I've seen, where the dentry list is so
> huge, that even iterating over it once with the parent dentry spinlock
> held is enough to trigger softlockups - no need for several calls to
> __fsnotify_update_child_dentry_flags() queueing up as described in the
> original mail. So ideally, I'd love to try make *something* work with
> the cursor idea as well. But I think the two ideas can be separated
> easily, and I can discuss with Al further about if cursors can be
> salvaged at all.
>

Assuming that you take the dir inode_lock() in
__fsnotify_update_child_dentry_flags(), then I *think* that children
dentries cannot be added to dcache and children dentries cannot
turn from positive to negative and vice versa.

Probably the only thing that can change d_subdirs is children dentries
being evicted from dcache(?), so I *think* that once in N children
if you can dget(child), drop alias->d_lock, cond_resched(),
and then continue d_subdirs iteration from child->d_child.

Thanks,
Amir.
  

Amir Goldstein <amir73il@gmail.com> writes:

> On Mon, Oct 17, 2022 at 10:59 AM Stephen Brennan
> <stephen.s.brennan@oracle.com> wrote:
>>
>> Amir Goldstein <amir73il@gmail.com> writes:
[snip]
>> > I think that d_find_any_alias() should be used to obtain
>> > the alias with elevated refcount instead of the awkward
>> > d_u.d_alias iteration loop.
>>
>> D'oh! Much better idea :)
>> Do you think the BUG_ON would still be worthwhile?
>>
>
> Which BUG_ON()?
> In general no, if there are ever more multiple aliases for
> a directory inode, updating dentry flags would be the last
> of our problems.

Sorry, I meant the one in my patch which asserts that the dentry is the
only alias for that inode. I suppose you're right about having bigger
problems in that case -- but the existing code "handles" it by iterating
over the alias list.

>
>> > In the context of __fsnotify_parent(), I think the optimization
>> > should stick with updating the flags for the specific child dentry
>> > that had the false positive parent_watched indication,
>> > leaving the rest of
>>
>> > WOULD that address the performance issues of your workload?
>>
>> I think synchronizing the __fsnotify_update_child_dentry_flags() with a
>> mutex and getting rid of the call from __fsnotify_parent() would go a
>> *huge* way (maybe 80%?) towards resolving the performance issues we've
>> seen. To be clear, I'm representing not one single workload, but a few
>> different customer workloads which center around this area.
>>
>> There are some extreme cases I've seen, where the dentry list is so
>> huge, that even iterating over it once with the parent dentry spinlock
>> held is enough to trigger softlockups - no need for several calls to
>> __fsnotify_update_child_dentry_flags() queueing up as described in the
>> original mail. So ideally, I'd love to try make *something* work with
>> the cursor idea as well. But I think the two ideas can be separated
>> easily, and I can discuss with Al further about if cursors can be
>> salvaged at all.
>>
>
> Assuming that you take the dir inode_lock() in
> __fsnotify_update_child_dentry_flags(), then I *think* that children
> dentries cannot be added to dcache and children dentries cannot
> turn from positive to negative and vice versa.
>
> Probably the only thing that can change d_subdirs is children dentries
> being evicted from dcache(?), so I *think* that once in N children
> if you can dget(child), drop alias->d_lock, cond_resched(),
> and then continue d_subdirs iteration from child->d_child.

This sounds like an excellent idea. I can't think of anything which
would remove a dentry from d_subdirs without the inode lock held.
Cursors wouldn't move without the lock held in read mode. Temporary
dentries from d_alloc_parallel are similar - they need the inode locked
shared in order to be removed from the parent list.

I'll try implementing it (along with the fsnotify changes we've
discussed in this thread). I'll add a BUG_ON after we wake up from
COND_RESCHED() to guarantee that the parent is the same dentry as
expected - just in case the assumption is wrong.

Al - if you've read this far :) - does this approach sound reasonable,
compared to the cursor? I'll send out some concrete patches as soon as
I've implemented and done a few tests on them.

Thanks,
Stephen
  

On Mon, Oct 17, 2022 at 8:00 PM Stephen Brennan
<stephen.s.brennan@oracle.com> wrote:
>
> Amir Goldstein <amir73il@gmail.com> writes:
>
> > On Mon, Oct 17, 2022 at 10:59 AM Stephen Brennan
> > <stephen.s.brennan@oracle.com> wrote:
> >>
> >> Amir Goldstein <amir73il@gmail.com> writes:
> [snip]
> >> > I think that d_find_any_alias() should be used to obtain
> >> > the alias with elevated refcount instead of the awkward
> >> > d_u.d_alias iteration loop.
> >>
> >> D'oh! Much better idea :)
> >> Do you think the BUG_ON would still be worthwhile?
> >>
> >
> > Which BUG_ON()?
> > In general no, if there are ever more multiple aliases for
> > a directory inode, updating dentry flags would be the last
> > of our problems.
>
> Sorry, I meant the one in my patch which asserts that the dentry is the
> only alias for that inode. I suppose you're right about having bigger
> problems in that case -- but the existing code "handles" it by iterating
> over the alias list.
>

It is not important IMO.

> >
> >> > In the context of __fsnotify_parent(), I think the optimization
> >> > should stick with updating the flags for the specific child dentry
> >> > that had the false positive parent_watched indication,
> >> > leaving the rest of
> >>
> >> > WOULD that address the performance issues of your workload?
> >>
> >> I think synchronizing the __fsnotify_update_child_dentry_flags() with a
> >> mutex and getting rid of the call from __fsnotify_parent() would go a
> >> *huge* way (maybe 80%?) towards resolving the performance issues we've
> >> seen. To be clear, I'm representing not one single workload, but a few
> >> different customer workloads which center around this area.
> >>
> >> There are some extreme cases I've seen, where the dentry list is so
> >> huge, that even iterating over it once with the parent dentry spinlock
> >> held is enough to trigger softlockups - no need for several calls to
> >> __fsnotify_update_child_dentry_flags() queueing up as described in the
> >> original mail. So ideally, I'd love to try make *something* work with
> >> the cursor idea as well. But I think the two ideas can be separated
> >> easily, and I can discuss with Al further about if cursors can be
> >> salvaged at all.
> >>
> >
> > Assuming that you take the dir inode_lock() in
> > __fsnotify_update_child_dentry_flags(), then I *think* that children
> > dentries cannot be added to dcache and children dentries cannot
> > turn from positive to negative and vice versa.
> >
> > Probably the only thing that can change d_subdirs is children dentries
> > being evicted from dcache(?), so I *think* that once in N children
> > if you can dget(child), drop alias->d_lock, cond_resched(),
> > and then continue d_subdirs iteration from child->d_child.
>
> This sounds like an excellent idea. I can't think of anything which
> would remove a dentry from d_subdirs without the inode lock held.
> Cursors wouldn't move without the lock held in read mode. Temporary
> dentries from d_alloc_parallel are similar - they need the inode locked
> shared in order to be removed from the parent list.
>
> I'll try implementing it (along with the fsnotify changes we've
> discussed in this thread). I'll add a BUG_ON after we wake up from
> COND_RESCHED() to guarantee that the parent is the same dentry as
> expected - just in case the assumption is wrong.

BUG_ON() is almost never a good idea.
If anything you should use if (WARN_ON_ONCE())
and break out of the loop either returning an error
to fanotify_mark() or not.
I personally think that as an unexpected code assertion
returning an error to the user is not a must in this case.

Thanks,
Amir.

>
> Al - if you've read this far :) - does this approach sound reasonable,
> compared to the cursor? I'll send out some concrete patches as soon as
> I've implemented and done a few tests on them.
>
> Thanks,
> Stephen
  

On Tue, Oct 18, 2022 at 7:12 AM Stephen Brennan
<stephen.s.brennan@oracle.com> wrote:
>
> Hi Jan, Amir, Al,
>
> Here's my first shot at implementing what we discussed. I tested it using the
> negative dentry creation tool I mentioned in my previous message, with a similar
> workflow. Rather than having a bunch of threads accessing the directory to
> create that "thundering herd" of CPUs in __fsnotify_update_child_dentry_flags, I
> just started a lot of inotifywait tasks:
>
> 1. Create 100 million negative dentries in a dir
> 2. Use trace-cmd to watch __fsnotify_update_child_dentry_flags:
>    trace-cmd start -p function_graph -l __fsnotify_update_child_dentry_flags
>    sudo cat /sys/kernel/debug/tracing/trace_pipe
> 3. Run a lot of inotifywait tasks: for i in {1..10} inotifywait $dir & done
>
> With step #3, I see only one execution of __fsnotify_update_child_dentry_flags.
> Once that completes, all the inotifywait tasks say "Watches established".
> Similarly, once an access occurs in the directory, a single
> __fsnotify_update_child_dentry_flags execution occurs, and all the tasks exit.
> In short: it works great!
>
> However, while testing this, I've observed a dentry still in use warning during
> unmount of rpc_pipefs on the "nfs" dentry during shutdown. NFS is of course in
> use, and I assume that fsnotify must have been used to trigger this. The error
> is not there on mainline without my patch so it's definitely caused by this
> code. I'll continue debugging it but I wanted to share my first take on this so
> you could take a look.
>
> [ 1595.197339] BUG: Dentry 000000005f5e7197{i=67,n=nfs}  still in use (2) [unmount of rpc_pipefs rpc_pipefs]
>

Hmm, the assumption we made about partial stability of d_subdirs
under dir inode lock looks incorrect for rpc_pipefs.
None of the functions that update the rpc_pipefs dcache take the parent
inode lock.

The assumption looks incorrect for other pseudo fs as well.

The other side of the coin is that we do not really need to worry
about walking a huge list of pseudo fs children.

The question is how to classify those pseudo fs and whether there
are other cases like this that we missed.

Perhaps having simple_dentry_operationsis a good enough
clue, but perhaps it is not enough. I am not sure.

It covers all the cases of pseudo fs that I know about, so you
can certainly use this clue to avoid going to sleep in the
update loop as a first approximation.

I can try to figure this out, but I prefer that Al will chime in to
provide reliable answers to those questions.

Thanks,
Amir.
  

Amir Goldstein <amir73il@gmail.com> writes:
> On Tue, Oct 18, 2022 at 7:12 AM Stephen Brennan
> <stephen.s.brennan@oracle.com> wrote:
>>
>> Hi Jan, Amir, Al,
>>
>> Here's my first shot at implementing what we discussed. I tested it using the
>> negative dentry creation tool I mentioned in my previous message, with a similar
>> workflow. Rather than having a bunch of threads accessing the directory to
>> create that "thundering herd" of CPUs in __fsnotify_update_child_dentry_flags, I
>> just started a lot of inotifywait tasks:
>>
>> 1. Create 100 million negative dentries in a dir
>> 2. Use trace-cmd to watch __fsnotify_update_child_dentry_flags:
>>    trace-cmd start -p function_graph -l __fsnotify_update_child_dentry_flags
>>    sudo cat /sys/kernel/debug/tracing/trace_pipe
>> 3. Run a lot of inotifywait tasks: for i in {1..10} inotifywait $dir & done
>>
>> With step #3, I see only one execution of __fsnotify_update_child_dentry_flags.
>> Once that completes, all the inotifywait tasks say "Watches established".
>> Similarly, once an access occurs in the directory, a single
>> __fsnotify_update_child_dentry_flags execution occurs, and all the tasks exit.
>> In short: it works great!
>>
>> However, while testing this, I've observed a dentry still in use warning during
>> unmount of rpc_pipefs on the "nfs" dentry during shutdown. NFS is of course in
>> use, and I assume that fsnotify must have been used to trigger this. The error
>> is not there on mainline without my patch so it's definitely caused by this
>> code. I'll continue debugging it but I wanted to share my first take on this so
>> you could take a look.
>>
>> [ 1595.197339] BUG: Dentry 000000005f5e7197{i=67,n=nfs}  still in use (2) [unmount of rpc_pipefs rpc_pipefs]
>>
>
> Hmm, the assumption we made about partial stability of d_subdirs
> under dir inode lock looks incorrect for rpc_pipefs.
> None of the functions that update the rpc_pipefs dcache take the parent
> inode lock.

That may be, but I'm confused how that would trigger this issue. If I'm
understanding correctly, this warning indicates a reference counting
bug.

If __fsnotify_update_child_dentry_flags() had gone to sleep and the list
were edited, then it seems like there could be only two possibilities
that could cause bugs:

1. The dentry we slept holding a reference to was removed from the list,
and maybe moved to a different one, or just removed. If that were the
case, we're quite unlucky, because we'll start looping indefinitely as
we'll never get back to the beginning of the list, or worse.

2. A dentry adjacent to the one we held a reference to was removed. In
that case, our dentry's d_child pointers should get rearranged, and when
we wake, we should see those updates and continue.

In neither of those cases do I understand where we could have done a
dget() unpaired with a dput(), which is what seemingly would trigger
this issue.

I'm probably wrong, but without understanding the mechanism behind the
error, I'm not sure how to approach it.

> The assumption looks incorrect for other pseudo fs as well.
>
> The other side of the coin is that we do not really need to worry
> about walking a huge list of pseudo fs children.
>
> The question is how to classify those pseudo fs and whether there
> are other cases like this that we missed.
>
> Perhaps having simple_dentry_operationsis a good enough
> clue, but perhaps it is not enough. I am not sure.
>
> It covers all the cases of pseudo fs that I know about, so you
> can certainly use this clue to avoid going to sleep in the
> update loop as a first approximation.

I would worry that it would become an exercise of whack-a-mole.
Allow/deny-listing certain filesystems for certain behavior seems scary.

> I can try to figure this out, but I prefer that Al will chime in to
> provide reliable answers to those questions.

I have a core dump from the warning (with panic_on_warn=1) and will see
if I can trace or otherwise identify the exact mechanism myself.

> Thanks,
> Amir.
>

Thanks for your detailed review of both the patches. I didn't get much
time today to update the patches and test them. Your feedback looks very
helpful though, and I'll hope to send out an updated revision tomorrow.

In the absolute worst case (and I don't want to concede defeat just
yet), keeping patch 1 without patch 2 (sleepable iteration) would still
be a major win, since it resolves the thundering herd problem which is
what compounds problem of the long lists. 

Thanks!
Stephen
  

On Wed, Oct 19, 2022 at 2:52 AM Stephen Brennan
<stephen.s.brennan@oracle.com> wrote:
>
> Amir Goldstein <amir73il@gmail.com> writes:
> > On Tue, Oct 18, 2022 at 7:12 AM Stephen Brennan
> > <stephen.s.brennan@oracle.com> wrote:
> >>
> >> Hi Jan, Amir, Al,
> >>
> >> Here's my first shot at implementing what we discussed. I tested it using the
> >> negative dentry creation tool I mentioned in my previous message, with a similar
> >> workflow. Rather than having a bunch of threads accessing the directory to
> >> create that "thundering herd" of CPUs in __fsnotify_update_child_dentry_flags, I
> >> just started a lot of inotifywait tasks:
> >>
> >> 1. Create 100 million negative dentries in a dir
> >> 2. Use trace-cmd to watch __fsnotify_update_child_dentry_flags:
> >>    trace-cmd start -p function_graph -l __fsnotify_update_child_dentry_flags
> >>    sudo cat /sys/kernel/debug/tracing/trace_pipe
> >> 3. Run a lot of inotifywait tasks: for i in {1..10} inotifywait $dir & done
> >>
> >> With step #3, I see only one execution of __fsnotify_update_child_dentry_flags.
> >> Once that completes, all the inotifywait tasks say "Watches established".
> >> Similarly, once an access occurs in the directory, a single
> >> __fsnotify_update_child_dentry_flags execution occurs, and all the tasks exit.
> >> In short: it works great!
> >>
> >> However, while testing this, I've observed a dentry still in use warning during
> >> unmount of rpc_pipefs on the "nfs" dentry during shutdown. NFS is of course in
> >> use, and I assume that fsnotify must have been used to trigger this. The error
> >> is not there on mainline without my patch so it's definitely caused by this
> >> code. I'll continue debugging it but I wanted to share my first take on this so
> >> you could take a look.
> >>
> >> [ 1595.197339] BUG: Dentry 000000005f5e7197{i=67,n=nfs}  still in use (2) [unmount of rpc_pipefs rpc_pipefs]
> >>
> >
> > Hmm, the assumption we made about partial stability of d_subdirs
> > under dir inode lock looks incorrect for rpc_pipefs.
> > None of the functions that update the rpc_pipefs dcache take the parent
> > inode lock.
>
> That may be, but I'm confused how that would trigger this issue. If I'm
> understanding correctly, this warning indicates a reference counting
> bug.

Yes.
On generic_shutdown_super() there should be no more
references to dentries.

>
> If __fsnotify_update_child_dentry_flags() had gone to sleep and the list
> were edited, then it seems like there could be only two possibilities
> that could cause bugs:
>
> 1. The dentry we slept holding a reference to was removed from the list,
> and maybe moved to a different one, or just removed. If that were the
> case, we're quite unlucky, because we'll start looping indefinitely as
> we'll never get back to the beginning of the list, or worse.
>
> 2. A dentry adjacent to the one we held a reference to was removed. In
> that case, our dentry's d_child pointers should get rearranged, and when
> we wake, we should see those updates and continue.
>
> In neither of those cases do I understand where we could have done a
> dget() unpaired with a dput(), which is what seemingly would trigger
> this issue.
>

I got the same impression.

> I'm probably wrong, but without understanding the mechanism behind the
> error, I'm not sure how to approach it.
>
> > The assumption looks incorrect for other pseudo fs as well.
> >
> > The other side of the coin is that we do not really need to worry
> > about walking a huge list of pseudo fs children.
> >
> > The question is how to classify those pseudo fs and whether there
> > are other cases like this that we missed.
> >
> > Perhaps having simple_dentry_operationsis a good enough
> > clue, but perhaps it is not enough. I am not sure.
> >
> > It covers all the cases of pseudo fs that I know about, so you
> > can certainly use this clue to avoid going to sleep in the
> > update loop as a first approximation.
>
> I would worry that it would become an exercise of whack-a-mole.
> Allow/deny-listing certain filesystems for certain behavior seems scary.
>

Totally agree.

> > I can try to figure this out, but I prefer that Al will chime in to
> > provide reliable answers to those questions.
>
> I have a core dump from the warning (with panic_on_warn=1) and will see
> if I can trace or otherwise identify the exact mechanism myself.
>

Most likely the refcount was already leaked earlier, but
worth trying.

>
> Thanks for your detailed review of both the patches. I didn't get much
> time today to update the patches and test them. Your feedback looks very
> helpful though, and I'll hope to send out an updated revision tomorrow.
>
> In the absolute worst case (and I don't want to concede defeat just
> yet), keeping patch 1 without patch 2 (sleepable iteration) would still
> be a major win, since it resolves the thundering herd problem which is
> what compounds problem of the long lists.
>

Makes sense.
Patch 1 logic is solid.

Hope my suggestions won't complicate you too much,
if they do, I am sure Jan will find a way to simplify ;)

Thanks,
Amir.
  

Amir Goldstein <amir73il@gmail.com> writes:
> On Wed, Oct 19, 2022 at 2:52 AM Stephen Brennan
> <stephen.s.brennan@oracle.com> wrote:
>>
>> Amir Goldstein <amir73il@gmail.com> writes:
>> > On Tue, Oct 18, 2022 at 7:12 AM Stephen Brennan
>> > <stephen.s.brennan@oracle.com> wrote:
>> >>
>> >> Hi Jan, Amir, Al,
>> >>
>> >> Here's my first shot at implementing what we discussed. I tested it using the
>> >> negative dentry creation tool I mentioned in my previous message, with a similar
>> >> workflow. Rather than having a bunch of threads accessing the directory to
>> >> create that "thundering herd" of CPUs in __fsnotify_update_child_dentry_flags, I
>> >> just started a lot of inotifywait tasks:
>> >>
>> >> 1. Create 100 million negative dentries in a dir
>> >> 2. Use trace-cmd to watch __fsnotify_update_child_dentry_flags:
>> >>    trace-cmd start -p function_graph -l __fsnotify_update_child_dentry_flags
>> >>    sudo cat /sys/kernel/debug/tracing/trace_pipe
>> >> 3. Run a lot of inotifywait tasks: for i in {1..10} inotifywait $dir & done
>> >>
>> >> With step #3, I see only one execution of __fsnotify_update_child_dentry_flags.
>> >> Once that completes, all the inotifywait tasks say "Watches established".
>> >> Similarly, once an access occurs in the directory, a single
>> >> __fsnotify_update_child_dentry_flags execution occurs, and all the tasks exit.
>> >> In short: it works great!
>> >>
>> >> However, while testing this, I've observed a dentry still in use warning during
>> >> unmount of rpc_pipefs on the "nfs" dentry during shutdown. NFS is of course in
>> >> use, and I assume that fsnotify must have been used to trigger this. The error
>> >> is not there on mainline without my patch so it's definitely caused by this
>> >> code. I'll continue debugging it but I wanted to share my first take on this so
>> >> you could take a look.
>> >>
>> >> [ 1595.197339] BUG: Dentry 000000005f5e7197{i=67,n=nfs}  still in use (2) [unmount of rpc_pipefs rpc_pipefs]
>> >>
>> >
>> > Hmm, the assumption we made about partial stability of d_subdirs
>> > under dir inode lock looks incorrect for rpc_pipefs.
>> > None of the functions that update the rpc_pipefs dcache take the parent
>> > inode lock.
>>
>> That may be, but I'm confused how that would trigger this issue. If I'm
>> understanding correctly, this warning indicates a reference counting
>> bug.
>
> Yes.
> On generic_shutdown_super() there should be no more
> references to dentries.
>
>>
>> If __fsnotify_update_child_dentry_flags() had gone to sleep and the list
>> were edited, then it seems like there could be only two possibilities
>> that could cause bugs:
>>
>> 1. The dentry we slept holding a reference to was removed from the list,
>> and maybe moved to a different one, or just removed. If that were the
>> case, we're quite unlucky, because we'll start looping indefinitely as
>> we'll never get back to the beginning of the list, or worse.
>>
>> 2. A dentry adjacent to the one we held a reference to was removed. In
>> that case, our dentry's d_child pointers should get rearranged, and when
>> we wake, we should see those updates and continue.
>>
>> In neither of those cases do I understand where we could have done a
>> dget() unpaired with a dput(), which is what seemingly would trigger
>> this issue.
>>
>
> I got the same impression.

Well I feel stupid. The reason behind this seems to be... that
d_find_any_alias() returns a reference to the dentry, and I promptly
leaked that. I'll have it fixed in v3 which I'm going through testing
now.

Stephen
  

>
> Well I feel stupid. The reason behind this seems to be... that
> d_find_any_alias() returns a reference to the dentry, and I promptly
> leaked that. I'll have it fixed in v3 which I'm going through testing
> now.
>

I reckon if you ran the LTP fsnotify tests you would have seen this
warning a lot more instead of just one random pseudo filesystem
that some process is probably setting a watch on...

You should run the existing LTP test to check for regressions.
The fanotify/inotify test cases in LTP are easy to run, for example:
run make in testcases/kernel/syscalls/fanotify and execute individual
./fanotify* executable.

If you point me to a branch, I can run the tests until you get
your LTP setup ready.

Thanks,
Amir.
  

Al Viro <viro@zeniv.linux.org.uk> writes:
> On Thu, Oct 13, 2022 at 03:27:19PM -0700, Stephen Brennan wrote:
>
>> So I have two more narrowly scoped strategies to improve the situation. Both are
>> included in the hacky, awful patch below.
>> 
>> First, is to let __fsnotify_update_child_dentry_flags() sleep. This means nobody
>> is holding the spinlock for several seconds at a time. We can actually achieve
>> this via a cursor, the same way that simple_readdir() is implemented. I think
>> this might require moving the declaration of d_alloc_cursor() and maybe
>> exporting it. I had to #include fs/internal.h which is not ok.
>
> Er...  Won't that expose every filesystem to having to deal with cursors?
> Currently it's entirely up to the filesystem in question and I wouldn't
> be a dime on everyone being ready to cope with such surprises...

Hi Al,

I wanted to follow-up on this. Yeah, I didn't realize that this could
cause issues for some filesystems when I wrote it, since I hadn't
considered that rather few filesystems use dcache_readdir(), and so most
aren't prepared to encounter a cursor. Thanks for that catch.

I think I came up with a better solution, which you can see in context
in v3 [1]. The only change I have from the posting there is to eliminate
the unnecssary "child->d_parent != parent" check. So the new idea is to
take a reference to the current child and then go to sleep. That alone
should be enough to prevent dentry_kill() from removing the child from
its parent's list. However, it wouldn't prevent d_move() from moving it
to a new list, nor would it prevent it from moving along the list if it
were a cursor. However, in this situation, we also hold the parent
i_rwsem in write mode, which means that no concurrent rename or readdir
can happen. You can see my full analysis here [2]. So here's the new
approach, if you can call out anything I've missod or confirm that it's
sound, I'd really appreciate it!


/* Must be called with inode->i_rwsem in held in write mode */
static bool __fsnotify_update_children_dentry_flags(struct inode *inode)
{
	struct dentry *child, *alias, *last_ref = NULL;
	alias = d_find_any_alias(inode);

	/*
	 * These lists can get very long, so we may need to sleep during
	 * iteration. Normally this would be impossible without a cursor,
	 * but since we have the inode locked exclusive, we're guaranteed
	 * that the directory won't be modified, so whichever dentry we
	 * pick to sleep on won't get moved.
	 */
	spin_lock(&alias->d_lock);
	list_for_each_entry(child, &alias->d_subdirs, d_child) {
		if (need_resched()) {
			/*
			 * We need to hold a reference while we sleep. But when
			 * we wake, dput() could free the dentry, invalidating
			 * the list pointers. We can't look at the list pointers
			 * until we re-lock the parent, and we can't dput() once
			 * we have the parent locked. So the solution is to hold
			 * onto our reference and free it the *next* time we drop
			 * alias->d_lock: either at the end of the function, or
			 * at the time of the next sleep.
			 */
			dget(child);
			spin_unlock(&alias->d_lock);
			dput(last_ref);
			last_ref = child;
			cond_resched();
			spin_lock(&alias->d_lock);
		}

		if (!child->d_inode)
			continue;

		spin_lock_nested(&child->d_lock, DENTRY_D_LOCK_NESTED);
		if (watched)
			child->d_flags |= DCACHE_FSNOTIFY_PARENT_WATCHED;
		else
			child->d_flags &= ~DCACHE_FSNOTIFY_PARENT_WATCHED;
		spin_unlock(&child->d_lock);
	}
	spin_unlock(&alias->d_lock);
	dput(last_ref);
	dput(alias);
	return watched;
}

Thanks,
Stephen

[1]: https://lore.kernel.org/linux-fsdevel/20221028001016.332663-4-stephen.s.brennan@oracle.com/
[2]: https://lore.kernel.org/linux-fsdevel/874jvigye9.fsf@oracle.com/