Revisiting Slab Movable Objects
Subsystems (2)
Hi folks,
As a long term project, I'm starting to look into resurrecting Slab Movable Objects. The goal is to make certain types of slab memory movable and thus enable targeted reclamation, migration, and defragmentation.
The main purpose of this posting is to briefly review what's been tried in the past, ask people why prior efforts have stalled (due to lack of time or insufficient justification for additional complexity?), and discuss what's feasible today.
Please add anyone I may have missed to Cc. :)
Previous Work on Slab Movable Objects
=====================================
Christoph Lameter, Slab Defragmentation Reduction, 2007-2017 (V16: [2]):
Christoph Lameter, Slab object migration for xarray, 2017-2018 (V2: [3]):
Christoph's long-standing effort (since 2007) aiming to defragment slab memory in cases where sparsely populated slabs occupy excessive amount of memory.
Early versions of the work focused on defragmenting slab caches for filesystem data structures such as inode, dentry, and buffer head. updatedb was suggested as the standard way to trigger for generating sparsely populated slabs on file servers.
However, defragmenting slabs for filesystem data structures has proven to be very difficult to fully solve, because inodes and dentries are neither reclaimable nor migratable, limiting the effectiveness of defragmentation.
In late 2018, the effort was revived with a new focus on migrating XArray nodes. However, it appears the work was discontinued after V2 [3]?
Tobin C. Harding, Slab Movable Objects, 2019 (First Non-RFC: [5])
- Tobin C. Harding revived Christoph's earlier work and introduced a few enhancements, including partial shrinking of dentries, moving objects to and from a specific NUMA node, and balancing objects across all NUMA nodes.
Also appears to be discontinued after the first non-RFC version [5]?
At LSFMM 2017, Andrea Arcangeli suggested [6] virtually mapped slabs, which might be useful since migrating them does not require changing the address of objects. But as Rik van Riel pointed out at that time, it isn't really useful for defragmentation. Andrea Arcangeli responded that it can be beneficial for memory hotplug, compaction and out-of-memory avoidance.
The exact mechanism wasn't described in [6], but I assume it'll involve
1) unmap a slab (and page faults after unmap need to wait for migration to complete), 2) copy objects to a new slab, and 3) map the new slab? But the idea hasn't gained enough attention for anyone to actually implement it.
Potential Candidates of SMO
===========================
Basic Rules
-----------
- Slab memory can only be reclaimed or migrated if the user of the slab provides a way to isolate / migrate objects.
- If objects can be reclaimed, it makes sense to simply reclaim them instead of migrating them (unless we know it's better to keep that object in memory).
- Some objects can't be reclaimed, but migrating them is (if possible) still useful for defragmentation and compaction.
- However it is not always feasible
Potential candidates include (but not limited to):
--------------------------------------------------
- XArray nodes can be migrated (can't be reclaimed as they're being used)
- Can be reclaimed if it only includes shadow entries.
- Maple tree nodes (if without external locking) and VMAs can be migrated and obviously can't be reclaimed.
- Negative dentry should be reclaimed, instead of being migrated.
- Only unused dentries can be reclaimed without high cost.
- Dentries with nonzero refcount are not really relocatable? (per [1])
- Even unused inodes can't be reclaimed nor relocated due to external references? (per [4])
Al Viro made it clear [1] that inodes / dentries are not really relocatable. He also mentioned:
Quoted 9 lines
So from the correctness POV
* you can kick out everything with zero refcount not
on shrink lists.
* you _might_ tryshrink_dcache_parent()on directory
dentries, in hope to drive their refcount to zero. However, that's almost certainly going to hit too hard and be too costly.
*d_invalidate()is no-go; if anything, you want something
weaker thanshrink_dcache_parent(), not stronger.
Quoted 6 lines
For anything beyond "just kick out everything in that page that happens to have zero refcount" I would really like to see the stats - how much does it help, how costly it is _and_ how much of the cache does it throw away (see above re running into a root dentry of some filesystem and essentially trimming dcache for that fs down to the unevictable stuff).
Dave Chinner mentioned [4] why it is hard to reclaim or migrate (in a targeted manner) even inodes with no active references:
Quoted 23 lines · Christoph Lameter
Quoted 3 lines
This is a patchset on top of Matthew Wilcox Xarray code and implements object migration of xarray nodes. The migration is integrated into the defragmetation and shrinking logic of the slab allocator.
.....
Quoted 2 lines
This is only possible for xarray for now but it would be worthwhile to extend this to dentries and inodes.
Christoph, you keep saying this is the goal, but I'm yet to see a solution proposed for the atomic replacement of all the pointers to an inode from external objects. An inode that has no active references still has an awful lot of passive and internal references that need to be dealt with.
e.g. racing page operations accessing
mapping->host, the inode in various lists (e.g. superblock inode list, writeback lists, etc), the inode lookup cache(s), backpointers from LSMs, fsnotify marks, crypto information, internal filesystem pointers (e.g. log items, journal handles, buffer references, etc) and so on. And each filesystem has a different set of passive references, too.Oh, and I haven't even mentioned deadlocks yet, either. :P
Quoted 9 lines
IOWs, just saying "it would be worthwhile to extend this to dentries and inodes" completely misrepresents the sheer complexity of doing so. We've known that atomic replacement is the big problem for defragging inodes and dentries since this work was started, what, more than 10 years? And while there's been many revisions of the core defrag code since then, there has been no credible solution presented for atomic replacement of objects with complex external references. This is a show-stopper for inode/dentry slab defrag, and I don't see that this new patchset is any different...
[1] https://lore.kernel.org/linux-mm/[email protected]
[2] https://lore.kernel.org/linux-mm/[email protected]
[3] https://marc.info/?l=linux-mm&m=154533371911133
[4] https://lore.kernel.org/linux-mm/20171228222419.GQ1871@rh
[5] https://lore.kernel.org/linux-mm/[email protected]
[6] https://lwn.net/Articles/717650
Signature · 2 lines
Cheers, Harry / Hyeonggon
Quoted 2 lines · Harry Yoo
Hi folks,
Hi Harry,
Some passing thoughts...
Quoted 50 lines
As a long term project, I'm starting to look into resurrecting Slab Movable Objects. The goal is to make certain types of slab memory movable and thus enable targeted reclamation, migration, and defragmentation.
The main purpose of this posting is to briefly review what's been tried in the past, ask people why prior efforts have stalled (due to lack of time or insufficient justification for additional complexity?), and discuss what's feasible today.
Please add anyone I may have missed to Cc. :)
Previous Work on Slab Movable Objects
=====================================Christoph Lameter, Slab Defragmentation Reduction, 2007-2017 (V16: [2]):
Christoph Lameter, Slab object migration for xarray, 2017-2018 (V2: [3]):
Christoph's long-standing effort (since 2007) aiming to defragment slab memory in cases where sparsely populated slabs occupy excessive amount of memory.Early versions of the work focused on defragmenting slab caches for filesystem data structures such as inode, dentry, and buffer head. updatedb was suggested as the standard way to trigger for generating sparsely populated slabs on file servers.
However, defragmenting slabs for filesystem data structures has proven to be very difficult to fully solve, because inodes and dentries are neither reclaimable nor migratable, limiting the effectiveness of defragmentation.
In late 2018, the effort was revived with a new focus on migrating XArray nodes. However, it appears the work was discontinued after V2 [3]?
Tobin C. Harding, Slab Movable Objects, 2019 (First Non-RFC: [5])
- Tobin C. Harding revived Christoph's earlier work and introduced a few enhancements, including partial shrinking of dentries, moving objects to and from a specific NUMA node, and balancing objects across all NUMA nodes.Also appears to be discontinued after the first non-RFC version [5]?
At LSFMM 2017, Andrea Arcangeli suggested [6] virtually mapped slabs, which might be useful since migrating them does not require changing the address of objects. But as Rik van Riel pointed out at that time, it isn't really useful for defragmentation. Andrea Arcangeli responded that it can be beneficial for memory hotplug, compaction and out-of-memory avoidance.
Quoted 5 lines
The exact mechanism wasn't described in [6], but I assume it'll involve
1) unmap a slab (and page faults after unmap need to wait for migration to complete), 2) copy objects to a new slab, and 3) map the new slab? But the idea hasn't gained enough attention for anyone to actually implement it.
I don't think this is a silver bullet. It opens a whole separate can of worms while maintaining similar issues. But instead of worrying about updating pointers, you're worrying about locking out _any_ sort of access, which would involve stop_machine(). You can't even atomically replace a PTE without running into issues (arm requires BBM, thus this doesn't work) so it cannot be applied to anything that can't page fault (xarray and the maple tree are used in IRQ paths, if I'm not mistaken).
Quoted 4 lines
Potential Candidates of SMO
===========================
Quoted 8 lines
Basic Rules
------------ Slab memory can only be reclaimed or migrated if the user of the slab provides a way to isolate / migrate objects.
- If objects can be reclaimed, it makes sense to simply reclaim them instead of migrating them (unless we know it's better to keep that object in memory).
In any case I think you want to give subsystems the power to decide between {RECLAIMED, MIGRATED, SKIPPED}.
Quoted 7 lines
- Some objects can't be reclaimed, but migrating them is (if possible) still useful for defragmentation and compaction.
- However it is not always feasiblePotential candidates include (but not limited to):
--------------------------------------------------
Quoted 6 lines
- XArray nodes can be migrated (can't be reclaimed as they're being used)
- Can be reclaimed if it only includes shadow entries.
- Maple tree nodes (if without external locking) and VMAs can be migrated and obviously can't be reclaimed.
- Negative dentry should be reclaimed, instead of being migrated.
- Only unused dentries can be reclaimed without high cost.
Unused dentries can also have a high cost if they're accessed in the future (and the dentry LRU has some difficulty in... LRU'ing - thus the negative dentry problem).
In any case, it would be interesting to see if the existing shrinker interface could be used for this stuff. We already best-effort-reclaim objects, maybe we could best-effort-migrate objects too? The problem of reclaiming is adjacent to migrating, and we already have infrastructure for it...
Signature · 1 line
Pedro
Quoted 7 lines · Pedro Falcato
Quoted 2 lines · Harry Yoo
Hi folks,
Hi Harry,
Some passing thoughts...
Hi Pedro, thanks for taking a look.
Quoted 56 lines
Quoted 50 lines
As a long term project, I'm starting to look into resurrecting Slab Movable Objects. The goal is to make certain types of slab memory movable and thus enable targeted reclamation, migration, and defragmentation.
The main purpose of this posting is to briefly review what's been tried in the past, ask people why prior efforts have stalled (due to lack of time or insufficient justification for additional complexity?), and discuss what's feasible today.
Please add anyone I may have missed to Cc. :)
Previous Work on Slab Movable Objects
=====================================Christoph Lameter, Slab Defragmentation Reduction, 2007-2017 (V16: [2]):
Christoph Lameter, Slab object migration for xarray, 2017-2018 (V2: [3]):
Christoph's long-standing effort (since 2007) aiming to defragment slab memory in cases where sparsely populated slabs occupy excessive amount of memory.Early versions of the work focused on defragmenting slab caches for filesystem data structures such as inode, dentry, and buffer head. updatedb was suggested as the standard way to trigger for generating sparsely populated slabs on file servers.
However, defragmenting slabs for filesystem data structures has proven to be very difficult to fully solve, because inodes and dentries are neither reclaimable nor migratable, limiting the effectiveness of defragmentation.
In late 2018, the effort was revived with a new focus on migrating XArray nodes. However, it appears the work was discontinued after V2 [3]?
Tobin C. Harding, Slab Movable Objects, 2019 (First Non-RFC: [5])
- Tobin C. Harding revived Christoph's earlier work and introduced a few enhancements, including partial shrinking of dentries, moving objects to and from a specific NUMA node, and balancing objects across all NUMA nodes.Also appears to be discontinued after the first non-RFC version [5]?
At LSFMM 2017, Andrea Arcangeli suggested [6] virtually mapped slabs, which might be useful since migrating them does not require changing the address of objects. But as Rik van Riel pointed out at that time, it isn't really useful for defragmentation. Andrea Arcangeli responded that it can be beneficial for memory hotplug, compaction and out-of-memory avoidance.
Quoted 5 lines
The exact mechanism wasn't described in [6], but I assume it'll involve
1) unmap a slab (and page faults after unmap need to wait for migration to complete), 2) copy objects to a new slab, and 3) map the new slab? But the idea hasn't gained enough attention for anyone to actually implement it.
Quoted 3 lines
I don't think this is a silver bullet. It opens a whole separate can of worms while maintaining similar issues. But instead of worrying about updating pointers, you're worrying about locking out _any_ sort of access, which would involve
stop_machine().
Haha, yes. When I read the LWN article I was like "Wait, can the kernel really synchronize access to slab objects while migrating the underlying pages?" and I sketched a very rough 'mecanism' in previous email without carefully considering correctness or feasibility.
stop_machine() just to migrate slab objects sounds like a disaster.
Quoted 3 lines
You can't even atomically replace a PTE without running into issues (arm requires BBM, thus this doesn't work) so it cannot be applied to anything that can't page fault (xarray and the maple tree are used in IRQ paths, if I'm not mistaken).
Yeah, while the idea is very simple, I can't think of any sane way to correctly implement this given that slab objects can be accessed in _any_ context.
Quoted 7 lines
Quoted 7 lines
Potential Candidates of SMO
===========================Basic Rules
-----------
Quoted 8 lines
Quoted 5 lines
- Slab memory can only be reclaimed or migrated if the user of the slab provides a way to isolate / migrate objects.
- If objects can be reclaimed, it makes sense to simply reclaim them instead of migrating them (unless we know it's better to keep that object in memory).In any case I think you want to give subsystems the power to decide between {RECLAIMED, MIGRATED, SKIPPED}.
Totally agreed.
Quoted 14 lines
Quoted 7 lines
- Some objects can't be reclaimed, but migrating them is (if possible) still useful for defragmentation and compaction.
- However it is not always feasiblePotential candidates include (but not limited to):
--------------------------------------------------Quoted 6 lines
- XArray nodes can be migrated (can't be reclaimed as they're being used)
- Can be reclaimed if it only includes shadow entries.
- Maple tree nodes (if without external locking) and VMAs can be migrated and obviously can't be reclaimed.
- Negative dentry should be reclaimed, instead of being migrated.
- Only unused dentries can be reclaimed without high cost.
Quoted 2 lines
Unused dentries can also have a high cost if they're accessed in the future (and the dentry LRU has some difficulty in... LRU'ing - thus the negative dentry problem).
If that's the case it can decide to migrate objects and return MIGRATED?
Quoted 4 lines
In any case, it would be interesting to see if the existing shrinker interface could be used for this stuff. We already best-effort-reclaim objects, maybe we could best-effort-migrate objects too? The problem of reclaiming is adjacent to migrating, and we already have infrastructure for it...
You mean best-effort-migrate objects for defragmentation via shrinker interface?
Signature · 2 lines
Cheers, Harry / Hyeonggon
Quoted 3 lines · Pedro Falcato
You can't even atomically replace a PTE without running into issues (arm requires BBM, thus this doesn't work) so it cannot be applied to anything that can't page fault (xarray and the maple tree are used in IRQ paths, if I'm not mistaken).
Newer ARM64 processors support changing a PTE with a a new cpu feature FEAT_BBML2.
An implementation has been submitted by Yang Shi and we hope that it is going to be merged for 6.17. This is a performance issue on ARM since it forces the kernel 1-1 map to be done with 4K PTEs.
Quoted 7 lines · Harry Yoo
Hi folks,
As a long term project, I'm starting to look into resurrecting Slab Movable Objects. The goal is to make certain types of slab memory movable and thus enable targeted reclamation, migration, and defragmentation.
Quoted 6 lines
The main purpose of this posting is to briefly review what's been tried in the past, ask people why prior efforts have stalled (due to lack of time or insufficient justification for additional complexity?), and discuss what's feasible today.
Please add anyone I may have missed to Cc. :)
Adding -fsdevel because dentry/inode cache discussion needs to be visible to all the fs/VFS developers.
I'm going to cut straight to the chase here, but I'll leave the rest of the original email quoted below for -fsdevel readers.
Quoted 2 lines
Previous Work on Slab Movable Objects
=====================================
<snip>
Without including any sort of viable proposal for dentry/inode relocation (i.e. the showstopper for past attempts), what is the point of trying to ressurect this?
I don't have a solution for the dentry cache reference issues - the dentry cache maintains the working set of files, so anything that randomly shoots down unused dentries for compaction is likely to have negative performance implications for dentry cache intensive workloads.
However, I can think of two possible solutions to the untracked external inode reference issue.
The first is that external inode references need to take an active reference to the inode (like a dentry does), and this prevents inodes from being relocated whilst such external references exist.
Josef has proposed an active/passive reference counting mechanism for all references to inodes recently on -fsdevel here:
https://lore.kernel.org/linux-fsdevel/20250303170029.GA3964340@perftesting/
However, the ability to revoke external references and/or resolve internal references atomically has not really been considered at this point in time.
To allow referenced inodes to be relocated, I'd suggest that any subsystem that takes an external reference to the inode needs to provide something like a SRCU notifier block to allow the external reference to be dynamically removed. Once the relocation is done, another notifier method can be called allowing the external reference to be updated with the new inode address. Any attempt to access the inode whilst it is being relocated through that external mechanism should probably block.
[ Note: this could be leveraged as a general ->revoke mechanism for external inode references. Instead of the external access blocking after reference recall, it would return an error if access revocation has occurred. This mechanism could likely also solve some of the current lifetime issues with fsnotify and landlock objects. ]
This leaves internal (passive) references that can be resolved by locking the inode itself. e.g. getting rid of mapping tree references (e.g. folio->mapping->host) by invalidating the inode page cache.
The other solution is to prevent excessive inode slab cache fragmentation in the first place. i.e. *stop caching unreferenced inodes*. In this case, the inode LRU goes away and we rely fully on the dentry cache pinning inodes to maintain the working set of inodes in memory. This works with/without Josef's proposed reference counting changes - though Josef's proposed changes make getting rid of the inode LRU a lot easier.
I talk about some of that stuff in the discussion of this superblock inode list iteration patchset here:
https://lore.kernel.org/linux-fsdevel/[email protected]/
-Dave.
Quoted 137 lines
Previous Work on Slab Movable Objects
=====================================Christoph Lameter, Slab Defragmentation Reduction, 2007-2017 (V16: [2]):
Christoph Lameter, Slab object migration for xarray, 2017-2018 (V2: [3]):
Christoph's long-standing effort (since 2007) aiming to defragment slab memory in cases where sparsely populated slabs occupy excessive amount of memory.Early versions of the work focused on defragmenting slab caches for filesystem data structures such as inode, dentry, and buffer head. updatedb was suggested as the standard way to trigger for generating sparsely populated slabs on file servers.
However, defragmenting slabs for filesystem data structures has proven to be very difficult to fully solve, because inodes and dentries are neither reclaimable nor migratable, limiting the effectiveness of defragmentation.
In late 2018, the effort was revived with a new focus on migrating XArray nodes. However, it appears the work was discontinued after V2 [3]?
Tobin C. Harding, Slab Movable Objects, 2019 (First Non-RFC: [5])
- Tobin C. Harding revived Christoph's earlier work and introduced a few enhancements, including partial shrinking of dentries, moving objects to and from a specific NUMA node, and balancing objects across all NUMA nodes.Also appears to be discontinued after the first non-RFC version [5]?
At LSFMM 2017, Andrea Arcangeli suggested [6] virtually mapped slabs, which might be useful since migrating them does not require changing the address of objects. But as Rik van Riel pointed out at that time, it isn't really useful for defragmentation. Andrea Arcangeli responded that it can be beneficial for memory hotplug, compaction and out-of-memory avoidance.
The exact mechanism wasn't described in [6], but I assume it'll involve
1) unmap a slab (and page faults after unmap need to wait for migration to complete), 2) copy objects to a new slab, and 3) map the new slab? But the idea hasn't gained enough attention for anyone to actually implement it.Potential Candidates of SMO
===========================Basic Rules
------------ Slab memory can only be reclaimed or migrated if the user of the slab provides a way to isolate / migrate objects.
- If objects can be reclaimed, it makes sense to simply reclaim them instead of migrating them (unless we know it's better to keep that object in memory).
- Some objects can't be reclaimed, but migrating them is (if possible) still useful for defragmentation and compaction.
- However it is not always feasiblePotential candidates include (but not limited to):
--------------------------------------------------- XArray nodes can be migrated (can't be reclaimed as they're being used)
- Can be reclaimed if it only includes shadow entries.
- Maple tree nodes (if without external locking) and VMAs can be migrated and obviously can't be reclaimed.
- Negative dentry should be reclaimed, instead of being migrated.
- Only unused dentries can be reclaimed without high cost.
- Dentries with nonzero refcount are not really relocatable? (per [1])
- Even unused inodes can't be reclaimed nor relocated due to external references? (per [4])Al Viro made it clear [1] that inodes / dentries are not really relocatable. He also mentioned:
Quoted 9 lines
So from the correctness POV
* you can kick out everything with zero refcount not
on shrink lists.
* you _might_ tryshrink_dcache_parent()on directory
dentries, in hope to drive their refcount to zero. However, that's almost certainly going to hit too hard and be too costly.
*d_invalidate()is no-go; if anything, you want something
weaker thanshrink_dcache_parent(), not stronger.Quoted 6 lines
For anything beyond "just kick out everything in that page that happens to have zero refcount" I would really like to see the stats - how much does it help, how costly it is _and_ how much of the cache does it throw away (see above re running into a root dentry of some filesystem and essentially trimming dcache for that fs down to the unevictable stuff).
Dave Chinner mentioned [4] why it is hard to reclaim or migrate (in a targeted manner) even inodes with no active references:
Quoted 23 lines · Christoph Lameter
Quoted 3 lines
This is a patchset on top of Matthew Wilcox Xarray code and implements object migration of xarray nodes. The migration is integrated into the defragmetation and shrinking logic of the slab allocator.
.....
Quoted 2 lines
This is only possible for xarray for now but it would be worthwhile to extend this to dentries and inodes.
Christoph, you keep saying this is the goal, but I'm yet to see a solution proposed for the atomic replacement of all the pointers to an inode from external objects. An inode that has no active references still has an awful lot of passive and internal references that need to be dealt with.
e.g. racing page operations accessing
mapping->host, the inode in various lists (e.g. superblock inode list, writeback lists, etc), the inode lookup cache(s), backpointers from LSMs, fsnotify marks, crypto information, internal filesystem pointers (e.g. log items, journal handles, buffer references, etc) and so on. And each filesystem has a different set of passive references, too.Oh, and I haven't even mentioned deadlocks yet, either. :P
Quoted 9 lines
IOWs, just saying "it would be worthwhile to extend this to dentries and inodes" completely misrepresents the sheer complexity of doing so. We've known that atomic replacement is the big problem for defragging inodes and dentries since this work was started, what, more than 10 years? And while there's been many revisions of the core defrag code since then, there has been no credible solution presented for atomic replacement of objects with complex external references. This is a show-stopper for inode/dentry slab defrag, and I don't see that this new patchset is any different...
[1] https://lore.kernel.org/linux-mm/[email protected]
[2] https://lore.kernel.org/linux-mm/[email protected]
[3] https://marc.info/?l=linux-mm&m=154533371911133
[4] https://lore.kernel.org/linux-mm/20171228222419.GQ1871@rh
[5] https://lore.kernel.org/linux-mm/[email protected]
[6] https://lwn.net/Articles/717650Signature · 2 lines
Cheers, Harry / Hyeonggon
Signature · 2 lines
Dave Chinner [email protected]
Al Viro
maintainerQuoted 5 lines · Dave Chinner
I don't have a solution for the dentry cache reference issues - the dentry cache maintains the working set of files, so anything that randomly shoots down unused dentries for compaction is likely to have negative performance implications for dentry cache intensive workloads.
Just to restate the obvious: _relocation_ of dentries is hopeless for many, many reasons - starting with "hash of dentry depends upon the address of its parent dentry". Freeing anything with zero refcount... sure, no problem - assuming that you are holding rcu_read_lock(),
if (READ_ONCE(dentry->d_count) == 0) {
spin_lock(&dentry->d_lock);
if (dentry->d_count == 0)
to_shrink_list(dentry, list);
spin_unlock(&dentry->d_lock);
}followed by rcu_read_unlock() and shrink_dentry_list(&list) once you are done collecting the candidates. If you want to wait for them to actually freed, synchronize_rcu() after rcu_read_unlock() (freeing is RCU-delayed).
Performance implications are separate story - it really depends upon a lot of details. But simple "I want all unused dentries in this page kicked out" is doable. And in-use dentries are no-go, no matter what.
Quoted 11 lines · Al Viro
Quoted 5 lines · Dave Chinner
I don't have a solution for the dentry cache reference issues - the dentry cache maintains the working set of files, so anything that randomly shoots down unused dentries for compaction is likely to have negative performance implications for dentry cache intensive workloads.
Just to restate the obvious: _relocation_ of dentries is hopeless for many, many reasons - starting with "hash of dentry depends upon the address of its parent dentry".
If we can't migrate or reclaim dentries with a nonzero refcount, can we at least prevent slab pages from containing a mix of dentries with zero and nonzero refcounts?
An idea: "Migrate a dentry (and inode?) _before_ it becomes unrelocatable" This is somewhat similar to "Migrate a page out of the movable area before pinning it" in MM.
For example, suppose we have two slab caches for dentry:dentry_cache_unref and dentry_cache_ref.
When a dentry with a zero refcount is about to have its refcount incremented, the VFS allocates a new object from dentry_cache_ref, copies the dentry into it, frees the original dentry back to dentry_cache_unref, and returns the newly allocated object.
Similarly when a dentry with a nonzero refcount drops to zero, it is migrated to dentry_cache_unref. This should be handled on the VFS side rather than by the slab allocator.
This approach could, at least, help reduce fragmentation.
Quoted 13 lines
Freeing anything with zero refcount...
sure, no problem - assuming that you are holdingrcu_read_lock(),if (READ_ONCE(dentry->d_count) == 0) { spin_lock(&dentry->d_lock); if (dentry->d_count == 0) to_shrink_list(dentry, list); spin_unlock(&dentry->d_lock); }followed by
rcu_read_unlock()andshrink_dentry_list(&list)once you are done collecting the candidates. If you want to wait for them to actually freed,synchronize_rcu()afterrcu_read_unlock()(freeing is RCU-delayed).
Quoted 4 lines
Performance implications are separate story - it really depends upon a lot of details. But simple "I want all unused dentries in this page kicked out" is doable. And in-use dentries are no-go, no matter what.
Thank you for the detailed guidance and confirming that it's doable! It will be very helpful when implementing this.
Signature · 2 lines
Cheers, Harry / Hyeonggon
Al Viro
maintainerQuoted 16 lines · Harry Yoo
If we can't migrate or reclaim dentries with a nonzero refcount, can we at least prevent slab pages from containing a mix of dentries with zero and nonzero refcounts?
An idea: "Migrate a dentry (and inode?) _before_ it becomes unrelocatable" This is somewhat similar to "Migrate a page out of the movable area before pinning it" in MM.
For example, suppose we have two slab caches for dentry:
dentry_cache_unrefanddentry_cache_ref.When a dentry with a zero refcount is about to have its refcount incremented, the VFS allocates a new object from
dentry_cache_ref, copies the dentry into it, frees the original dentry back todentry_cache_unref, and returns the newly allocated object.
Quoted 5 lines
Similarly when a dentry with a nonzero refcount drops to zero, it is migrated to
dentry_cache_unref. This should be handled on the VFS side rather than by the slab allocator.This approach could, at least, help reduce fragmentation.
No. This is utterly insane - you'd need to insert RCU delay on each of those transitions and that is not to mention the frequency with which those will happen on a lot of loads (any kind of builds included). Not a chance.
Quoted 21 lines · Dave Chinner
Quoted 7 lines · Harry Yoo
Hi folks,
As a long term project, I'm starting to look into resurrecting Slab Movable Objects. The goal is to make certain types of slab memory movable and thus enable targeted reclamation, migration, and defragmentation.
Quoted 6 lines
The main purpose of this posting is to briefly review what's been tried in the past, ask people why prior efforts have stalled (due to lack of time or insufficient justification for additional complexity?), and discuss what's feasible today.
Please add anyone I may have missed to Cc. :)
Adding -fsdevel because dentry/inode cache discussion needs to be visible to all the fs/VFS developers.
I'm going to cut straight to the chase here, but I'll leave the rest of the original email quoted below for -fsdevel readers.
Quoted 8 lines
Quoted 2 lines
Previous Work on Slab Movable Objects
=====================================<snip>
Without including any sort of viable proposal for dentry/inode relocation (i.e. the showstopper for past attempts), what is the point of trying to ressurect this?
Migrating slabs still makes sense for other objects such as xarray / maple tree nodes, and VMAs.
Of course, if filesystem folks could enhance it further and make more of dentry/inode objects that would be very welcome.
Quoted 7 lines
However, I can think of two possible solutions to the untracked external inode reference issue.
The first is that external inode references need to take an active reference to the inode (like a dentry does), and this prevents inodes from being relocated whilst such external references exist.
Quoted 8 lines
Josef has proposed an active/passive reference counting mechanism for all references to inodes recently on -fsdevel here:
https://lore.kernel.org/linux-fsdevel/20250303170029.GA3964340@perftesting/
However, the ability to revoke external references and/or resolve internal references atomically has not really been considered at this point in time.
...alright, I expect that'll be more tricker part.
Quoted 15 lines
To allow referenced inodes to be relocated, I'd suggest that any subsystem that takes an external reference to the inode needs to provide something like a SRCU notifier block to allow the external reference to be dynamically removed. Once the relocation is done, another notifier method can be called allowing the external reference to be updated with the new inode address. Any attempt to access the inode whilst it is being relocated through that external mechanism should probably block.
[ Note: this could be leveraged as a general ->revoke mechanism for external inode references. Instead of the external access blocking after reference recall, it would return an error if access revocation has occurred. This mechanism could likely also solve some of the current lifetime issues with fsnotify and landlock objects. ]
Quoted 4 lines
This leaves internal (passive) references that can be resolved by locking the inode itself. e.g. getting rid of mapping tree references (e.g.
folio->mapping->host) by invalidating the inode page cache.
Thank you so much for such a detailed writeup.
The former approach would allow allocating them from movable areas, help mm/compaction.c to build high-order folios, and help slab to reduce fragmentation.
Quoted 8 lines
The other solution is to prevent excessive inode slab cache fragmentation in the first place. i.e. *stop caching unreferenced inodes*. In this case, the inode LRU goes away and we rely fully on the dentry cache pinning inodes to maintain the working set of inodes in memory. This works with/without Josef's proposed reference counting changes - though Josef's proposed changes make getting rid of the inode LRU a lot easier.
Quoted 4 lines
I talk about some of that stuff in the discussion of this superblock inode list iteration patchset here:
The latter approach, while it does not make them relocatable, will reduce fragmentation at least.
Unfortunately, as an MM developer, I don’t have enough experience with filesystems to assess which proposal is more feasible. It would be really helpful to get consensus from the FS folks before we push this path forward—whether it's relocating inode entries or avoiding their fragmentation.
Signature · 2 lines
Cheers, Harry / Hyeonggon
Quoted 25 lines · Harry Yoo
Quoted 24 lines · Dave Chinner
Quoted 7 lines · Harry Yoo
Hi folks,
As a long term project, I'm starting to look into resurrecting Slab Movable Objects. The goal is to make certain types of slab memory movable and thus enable targeted reclamation, migration, and defragmentation.
Quoted 6 lines
The main purpose of this posting is to briefly review what's been tried in the past, ask people why prior efforts have stalled (due to lack of time or insufficient justification for additional complexity?), and discuss what's feasible today.
Please add anyone I may have missed to Cc. :)
Adding -fsdevel because dentry/inode cache discussion needs to be visible to all the fs/VFS developers.
I'm going to cut straight to the chase here, but I'll leave the rest of the original email quoted below for -fsdevel readers.
Quoted 2 lines
Previous Work on Slab Movable Objects
=====================================
Quoted 8 lines
Quoted 5 lines
<snip>
Without including any sort of viable proposal for dentry/inode relocation (i.e. the showstopper for past attempts), what is the point of trying to ressurect this?
Migrating slabs still makes sense for other objects such as xarray / maple tree nodes, and VMAs.
Do we have examples of how much memory is actually wasted on sparsely-used slabs, and which slabs this happens in, from some real workloads?
If sparsely-used slabs are a sufficiently big problem, maybe another big hammer we have is to use smaller slab pages, or something along those lines? Though of course a straightforward implementation of that would probably have negative effects on the performance of SLUB fastpaths, and depending on object size it might waste more memory on padding.
(An adventurous idea would be to try to align kmem_cache::size such that objects start at some subpage boundaries of SLUB folios, and then figure out a way to shatter SLUB folios into smaller folios at runtime while they contain objects... but getting the SLUB locking right for that without slowing down the fastpath for freeing an object would probably be a large pain.)
Quoted 32 lines · Jann Horn
Quoted 31 lines · Harry Yoo
Quoted 29 lines · Dave Chinner
Quoted 7 lines · Harry Yoo
Hi folks,
As a long term project, I'm starting to look into resurrecting Slab Movable Objects. The goal is to make certain types of slab memory movable and thus enable targeted reclamation, migration, and defragmentation.
Quoted 6 lines
The main purpose of this posting is to briefly review what's been tried in the past, ask people why prior efforts have stalled (due to lack of time or insufficient justification for additional complexity?), and discuss what's feasible today.
Please add anyone I may have missed to Cc. :)
Adding -fsdevel because dentry/inode cache discussion needs to be visible to all the fs/VFS developers.
I'm going to cut straight to the chase here, but I'll leave the rest of the original email quoted below for -fsdevel readers.
Quoted 2 lines
Previous Work on Slab Movable Objects
=====================================<snip>
Without including any sort of viable proposal for dentry/inode relocation (i.e. the showstopper for past attempts), what is the point of trying to ressurect this?
Quoted 6 lines
Quoted 2 lines
Migrating slabs still makes sense for other objects such as xarray / maple tree nodes, and VMAs.
Do we have examples of how much memory is actually wasted on sparsely-used slabs, and which slabs this happens in, from some real workloads?
Workloads that uses a large amount of reclaimable slab memory (inode, dentry, etc.) and triggers reclamation can observe this problem.
On my laptop, I can reproduce the problem by running 'updatedb' command that touches many files and triggering reclamation by running programs that consume large amount of memory. As slab memory is reclaimed, it becomes sparsely populated (as slab memory is not reclaimed folio by folio)
During reclamation, the total slab memory utilization drops from 95% to 50%. For very sparsely populated caches, the cache utilization is between 12% and 33%. (ext4_inode_cache, radix_tree_node, dentry, trace_event_file, and some kmalloc caches on my machine).
At the time OOM-killer is invoked, there's about 50% slab memory wasted due to sparsely populated slabs, which is about 236 MiB on my laptop. I would say it's a sufficiently big problem to solve.
I wonder how worse this problem would be on large file servers, but I don't run such servers :-)
Quoted 6 lines
If sparsely-used slabs are a sufficiently big problem, maybe another big hammer we have is to use smaller slab pages, or something along those lines? Though of course a straightforward implementation of that would probably have negative effects on the performance of SLUB fastpaths, and depending on object size it might waste more memory on padding.
So it'll be something like prefering low orders when in calculate_order() while keeping fractional waste reasonably.
One problem could be making n->list_lock contention much worse on larger machines as you need to grab more slabs from the list?
Quoted 6 lines
(An adventurous idea would be to try to align
kmem_cache::sizesuch that objects start at some subpage boundaries of SLUB folios, and then figure out a way to shatter SLUB folios into smaller folios at runtime while they contain objects... but getting the SLUB locking right for that without slowing down the fastpath for freeing an object would probably be a large pain.)
You can't make virt_to_slab() work if you shatter a slab folio into smaller ones?
A more general question: will either shattering or allocating smaller slabs help free more memory anyway? It likely depends on the spatial pattern of how the objects are reclaimed and remain populated within a slab?
Signature · 2 lines
Cheers, Harry / Hyeonggon
Quoted 67 lines · Harry Yoo
Quoted 32 lines · Jann Horn
Quoted 31 lines · Harry Yoo
Quoted 29 lines · Dave Chinner
Quoted 7 lines · Harry Yoo
Hi folks,
As a long term project, I'm starting to look into resurrecting Slab Movable Objects. The goal is to make certain types of slab memory movable and thus enable targeted reclamation, migration, and defragmentation.
Quoted 6 lines
The main purpose of this posting is to briefly review what's been tried in the past, ask people why prior efforts have stalled (due to lack of time or insufficient justification for additional complexity?), and discuss what's feasible today.
Please add anyone I may have missed to Cc. :)
Adding -fsdevel because dentry/inode cache discussion needs to be visible to all the fs/VFS developers.
I'm going to cut straight to the chase here, but I'll leave the rest of the original email quoted below for -fsdevel readers.
Quoted 2 lines
Previous Work on Slab Movable Objects
=====================================<snip>
Without including any sort of viable proposal for dentry/inode relocation (i.e. the showstopper for past attempts), what is the point of trying to ressurect this?
Quoted 6 lines
Quoted 2 lines
Migrating slabs still makes sense for other objects such as xarray / maple tree nodes, and VMAs.
Do we have examples of how much memory is actually wasted on sparsely-used slabs, and which slabs this happens in, from some real workloads?
Workloads that uses a large amount of reclaimable slab memory (inode, dentry, etc.) and triggers reclamation can observe this problem.
On my laptop, I can reproduce the problem by running 'updatedb' command that touches many files and triggering reclamation by running programs that consume large amount of memory. As slab memory is reclaimed, it becomes sparsely populated (as slab memory is not reclaimed folio by folio)
During reclamation, the total slab memory utilization drops from 95% to 50%. For very sparsely populated caches, the cache utilization is between 12% and 33%. (
ext4_inode_cache,radix_tree_node, dentry,trace_event_file, and some kmalloc caches on my machine).At the time OOM-killer is invoked, there's about 50% slab memory wasted due to sparsely populated slabs, which is about 236 MiB on my laptop. I would say it's a sufficiently big problem to solve.
I wonder how worse this problem would be on large file servers, but I don't run such servers :-)
Quoted 6 lines
If sparsely-used slabs are a sufficiently big problem, maybe another big hammer we have is to use smaller slab pages, or something along those lines? Though of course a straightforward implementation of that would probably have negative effects on the performance of SLUB fastpaths, and depending on object size it might waste more memory on padding.
Quoted 5 lines
So it'll be something like prefering low orders when in
calculate_order()while keeping fractional waste reasonably.One problem could be making
n->list_lockcontention much worse on larger machines as you need to grab more slabs from the list?
Maybe. I imagine using batched operations could help, such that the amount of managed memory that is transferred per locking operation stays the same...
Quoted 9 lines
Quoted 6 lines
(An adventurous idea would be to try to align
kmem_cache::sizesuch that objects start at some subpage boundaries of SLUB folios, and then figure out a way to shatter SLUB folios into smaller folios at runtime while they contain objects... but getting the SLUB locking right for that without slowing down the fastpath for freeing an object would probably be a large pain.)You can't make
virt_to_slab()work if you shatter a slab folio into smaller ones?
Yeah, I think that would be hard. We could maybe avoid the virt_to_slab() on the active-slab fastpath, and maybe there is some kind of RCU-transition scheme that could be used on the path for non-active slabs (a bit similarly to how percpu refcounts transition to atomic mode, with a transition period where objects are allowed to still go on the freelist of the former head page)...
Quoted 4 lines
A more general question: will either shattering or allocating smaller slabs help free more memory anyway? It likely depends on the spatial pattern of how the objects are reclaimed and remain populated within a slab?
Probably, yeah.
As a crude thought experiment, if you (somewhat pessimistically?) assume that the spatial pattern is "we first allocate a lot of objects, then for each object we roll a random number and free it with a 90% probability", and you have something like a kmalloc-512 slab (normal order 2, which fits 32 objects), then the probability that an entire order-2 page will be empty would bepow(0.9, 32) ~= 3.4%
while the probability that an individual order-0 page is empty would be pow(0.9, 8) ~= 43%
There could be patterns that are worse, like "we preserve exactly every fourth object"; though SLUB's freelist randomization (if CONFIG_SLAB_FREELIST_RANDOM is enabled) would probably transform that into a different pattern, so that it's not actually a sequential pattern where every fourth object is allocated.
In case you want to do more detailed experiments with this: FYI, I have a branch "slub-binary-snapshot" at https://github.com/thejh/linux
with a draft patch that provides a debugfs API for getting a binary dump of SLUB allocations (I wrote that patch for another project):
https://github.com/thejh/linux/commit/685944dc69fd21e92bf110713b491d5c050328af
- maybe with some changes that would be useful for analyzing SLUB fragmentation from userspace.
But IDK if that's a good way to experiment with this, or if it'd be easier to directly analyze fragmentation in debugfs code in SLUB.
Quoted 2 lines · Harry Yoo
A more general question: will either shattering or allocating smaller slabs help free more memory anyway?
In general, no.
Quoted 3 lines
It likely depends on
the spatial pattern of how the objects are reclaimed and remain populated within a slab?
Right - the pattern of inode/dentry residency in slab pages is defined by temporal access patterns of any given inode/dentry. If an application creates a new file and then holds it open, then that slab page is pinned in memory until the application closes that file.
Hence if we mix short term file accesses (e.g. access once files (like updatedb) or short term temp files (like object files during a code build) with long term open files, the slabs get fragmented because of the few pinned long term objects in each slab page.
IOWs, the moment we start mixing objects with different temporal access patterns within a single slab page during rapid cache growth, we will get fragmentation of the cache as reclaim only removes the short term objects during subsequent rapid cache shrinkage....
The unsolvable problem here is that we do not know (and cannot know) what the life time of the object is going to be at object instantiation time (i.e. path lookup). Hence the temporal access patterns of objects in the slab pages are going to be largely random. Experience tells me that even single page slabs (old skool SLAB cache) had these fragmentation problems (esp. with dentries) because even a 20:1 ratio of short:long term accesses will leave a single long term dentry per 4kB slab backing page...
Hence using smaller slabs and/or shattering larger slabs isn't likely to have all that much impact on the fragmentation of the slabs because it doesn't do anything to solve the underlying object lifetime interleaving that causes the fragmentation in the first place...
-Dave.
Signature · 2 lines
Dave Chinner [email protected]
On Mon, Apr 21, 2025, at 23:47, Harry Yoo wrote:
[snip]
Quoted 7 lines
Tobin C. Harding, Slab Movable Objects, 2019 (First Non-RFC: [5])
- Tobin C. Harding revived Christoph's earlier work and introduced a few enhancements, including partial shrinking of dentries, moving objects to and from a specific NUMA node, and balancing objects across all NUMA nodes.Also appears to be discontinued after the first non-RFC version [5]?
You are correct, I stopped working on this patch set after the first non-RFC version.
Good luck,
Tobin