Re: [PATCH v4 44/48] mm: shrinker: add a secondary array for shrinker_info::{map, nr_deferred}
Hi Dave, On 2023/8/8 10:12, Dave Chinner wrote: On Mon, Aug 07, 2023 at 07:09:32PM +0800, Qi Zheng wrote: Currently, we maintain two linear arrays per node per memcg, which are shrinker_info::map and shrinker_info::nr_deferred. And we need to resize them when the shrinker_nr_max is exceeded, that is, allocate a new array, and then copy the old array to the new array, and finally free the old array by RCU. For shrinker_info::map, we do set_bit() under the RCU lock, so we may set the value into the old map which is about to be freed. This may cause the value set to be lost. The current solution is not to copy the old map when resizing, but to set all the corresponding bits in the new map to 1. This solves the data loss problem, but bring the overhead of more pointless loops while doing memcg slab shrink. For shrinker_info::nr_deferred, we will only modify it under the read lock of shrinker_rwsem, so it will not run concurrently with the resizing. But after we make memcg slab shrink lockless, there will be the same data loss problem as shrinker_info::map, and we can't work around it like the map. For such resizable arrays, the most straightforward idea is to change it to xarray, like we did for list_lru [1]. We need to do xa_store() in the list_lru_add()-->set_shrinker_bit(), but this will cause memory allocation, and the list_lru_add() doesn't accept failure. A possible solution is to pre-allocate, but the location of pre-allocation is not well determined. So you implemented a two level array that preallocates leaf nodes to work around it? It's remarkable complex for what it does, Yes, here I have implemented a two level array like the following: +---+++-+ | shrinker_info | unit 0 | unit 1 | ... | (secondary array) +---+++-+ ^ | +---+-+ | nr_deferred[] | map | (leaf array) +---+-+ (shrinker_info_unit) The leaf array is never freed unless the memcg is destroyed. The secondary array will be resized every time the shrinker id exceeds shrinker_nr_max. I can't help but think a radix tree using a special holder for nr_deferred values of zero would end up being simpler... I tried. If the shrinker uses list_lru, then we can preallocate xa node where list_lru_one is pre-allocated. But for other types of shrinkers, the location of pre-allocation is not easy to determine (Such as deferred_split_shrinker). And we can't force all memcg aware shrinkers to use list_lru, so I gave up using xarray and implemented the above two-level array. Therefore, this commit chooses to introduce a secondary array for shrinker_info::{map, nr_deferred}, so that we only need to copy this secondary array every time the size is resized. Then even if we get the old secondary array under the RCU lock, the found map and nr_deferred are also true, so no data is lost. I don't understand what you are trying to describe here. If we get the old array, then don't we get either a stale nr_deferred value, or the update we do gets lost because the next shrinker lookup will find the new array and os the deferred value stored to the old one is never seen again? As shown above, the leaf array will not be freed when shrinker_info is expanded, so the shrinker_info_unit can be indexed from both the old and the new shrinker_info->unit[x]. So the updated nr_deferred and map will not be lost. [1]. https://lore.kernel.org/all/20220228122126.37293-13-songmuc...@bytedance.com/ Signed-off-by: Qi Zheng Reviewed-by: Muchun Song --- . diff --git a/mm/shrinker.c b/mm/shrinker.c index a27779ed3798..1911c06b8af5 100644 --- a/mm/shrinker.c +++ b/mm/shrinker.c @@ -12,15 +12,50 @@ DECLARE_RWSEM(shrinker_rwsem); #ifdef CONFIG_MEMCG static int shrinker_nr_max; -/* The shrinker_info is expanded in a batch of BITS_PER_LONG */ -static inline int shrinker_map_size(int nr_items) +static inline int shrinker_unit_size(int nr_items) { - return (DIV_ROUND_UP(nr_items, BITS_PER_LONG) * sizeof(unsigned long)); + return (DIV_ROUND_UP(nr_items, SHRINKER_UNIT_BITS) * sizeof(struct shrinker_info_unit *)); } -static inline int shrinker_defer_size(int nr_items) +static inline void shrinker_unit_free(struct shrinker_info *info, int start) { - return (round_up(nr_items, BITS_PER_LONG) * sizeof(atomic_long_t)); + struct shrinker_info_unit **unit; + int nr, i; + + if (!info) + return; + + unit = info->unit; + nr = DIV_ROUND_UP(info->map_nr_max, SHRINKER_UNIT_BITS); + + for (i = start; i < nr; i++) { + if (!unit[i]) + break; + + kvfree(unit[i]); + unit[i] = NULL; + } +} + +static inline int shrinker_unit_alloc(struct shrinker_info *new, + struct shrinker_info *old, int
Re: [PATCH v4 44/48] mm: shrinker: add a secondary array for shrinker_info::{map, nr_deferred}
On Mon, Aug 07, 2023 at 07:09:32PM +0800, Qi Zheng wrote: > Currently, we maintain two linear arrays per node per memcg, which are > shrinker_info::map and shrinker_info::nr_deferred. And we need to resize > them when the shrinker_nr_max is exceeded, that is, allocate a new array, > and then copy the old array to the new array, and finally free the old > array by RCU. > > For shrinker_info::map, we do set_bit() under the RCU lock, so we may set > the value into the old map which is about to be freed. This may cause the > value set to be lost. The current solution is not to copy the old map when > resizing, but to set all the corresponding bits in the new map to 1. This > solves the data loss problem, but bring the overhead of more pointless > loops while doing memcg slab shrink. > > For shrinker_info::nr_deferred, we will only modify it under the read lock > of shrinker_rwsem, so it will not run concurrently with the resizing. But > after we make memcg slab shrink lockless, there will be the same data loss > problem as shrinker_info::map, and we can't work around it like the map. > > For such resizable arrays, the most straightforward idea is to change it > to xarray, like we did for list_lru [1]. We need to do xa_store() in the > list_lru_add()-->set_shrinker_bit(), but this will cause memory > allocation, and the list_lru_add() doesn't accept failure. A possible > solution is to pre-allocate, but the location of pre-allocation is not > well determined. So you implemented a two level array that preallocates leaf nodes to work around it? It's remarkable complex for what it does, I can't help but think a radix tree using a special holder for nr_deferred values of zero would end up being simpler... > Therefore, this commit chooses to introduce a secondary array for > shrinker_info::{map, nr_deferred}, so that we only need to copy this > secondary array every time the size is resized. Then even if we get the > old secondary array under the RCU lock, the found map and nr_deferred are > also true, so no data is lost. I don't understand what you are trying to describe here. If we get the old array, then don't we get either a stale nr_deferred value, or the update we do gets lost because the next shrinker lookup will find the new array and os the deferred value stored to the old one is never seen again? > > [1]. > https://lore.kernel.org/all/20220228122126.37293-13-songmuc...@bytedance.com/ > > Signed-off-by: Qi Zheng > Reviewed-by: Muchun Song > --- . > diff --git a/mm/shrinker.c b/mm/shrinker.c > index a27779ed3798..1911c06b8af5 100644 > --- a/mm/shrinker.c > +++ b/mm/shrinker.c > @@ -12,15 +12,50 @@ DECLARE_RWSEM(shrinker_rwsem); > #ifdef CONFIG_MEMCG > static int shrinker_nr_max; > > -/* The shrinker_info is expanded in a batch of BITS_PER_LONG */ > -static inline int shrinker_map_size(int nr_items) > +static inline int shrinker_unit_size(int nr_items) > { > - return (DIV_ROUND_UP(nr_items, BITS_PER_LONG) * sizeof(unsigned long)); > + return (DIV_ROUND_UP(nr_items, SHRINKER_UNIT_BITS) * sizeof(struct > shrinker_info_unit *)); > } > > -static inline int shrinker_defer_size(int nr_items) > +static inline void shrinker_unit_free(struct shrinker_info *info, int start) > { > - return (round_up(nr_items, BITS_PER_LONG) * sizeof(atomic_long_t)); > + struct shrinker_info_unit **unit; > + int nr, i; > + > + if (!info) > + return; > + > + unit = info->unit; > + nr = DIV_ROUND_UP(info->map_nr_max, SHRINKER_UNIT_BITS); > + > + for (i = start; i < nr; i++) { > + if (!unit[i]) > + break; > + > + kvfree(unit[i]); > + unit[i] = NULL; > + } > +} > + > +static inline int shrinker_unit_alloc(struct shrinker_info *new, > +struct shrinker_info *old, int nid) > +{ > + struct shrinker_info_unit *unit; > + int nr = DIV_ROUND_UP(new->map_nr_max, SHRINKER_UNIT_BITS); > + int start = old ? DIV_ROUND_UP(old->map_nr_max, SHRINKER_UNIT_BITS) : 0; > + int i; > + > + for (i = start; i < nr; i++) { > + unit = kvzalloc_node(sizeof(*unit), GFP_KERNEL, nid); A unit is 576 bytes. Why is this using kvzalloc_node()? > + if (!unit) { > + shrinker_unit_free(new, start); > + return -ENOMEM; > + } > + > + new->unit[i] = unit; > + } > + > + return 0; > } > > void free_shrinker_info(struct mem_cgroup *memcg) > @@ -32,6 +67,7 @@ void free_shrinker_info(struct mem_cgroup *memcg) > for_each_node(nid) { > pn = memcg->nodeinfo[nid]; > info = rcu_dereference_protected(pn->shrinker_info, true); > + shrinker_unit_free(info, 0); > kvfree(info); > rcu_assign_pointer(pn->shrinker_info, NULL); > } Why is this safe? The info and maps are looked up by RCU, so why is freeing them without a RCU grace
[PATCH v4 44/48] mm: shrinker: add a secondary array for shrinker_info::{map, nr_deferred}
Currently, we maintain two linear arrays per node per memcg, which are shrinker_info::map and shrinker_info::nr_deferred. And we need to resize them when the shrinker_nr_max is exceeded, that is, allocate a new array, and then copy the old array to the new array, and finally free the old array by RCU. For shrinker_info::map, we do set_bit() under the RCU lock, so we may set the value into the old map which is about to be freed. This may cause the value set to be lost. The current solution is not to copy the old map when resizing, but to set all the corresponding bits in the new map to 1. This solves the data loss problem, but bring the overhead of more pointless loops while doing memcg slab shrink. For shrinker_info::nr_deferred, we will only modify it under the read lock of shrinker_rwsem, so it will not run concurrently with the resizing. But after we make memcg slab shrink lockless, there will be the same data loss problem as shrinker_info::map, and we can't work around it like the map. For such resizable arrays, the most straightforward idea is to change it to xarray, like we did for list_lru [1]. We need to do xa_store() in the list_lru_add()-->set_shrinker_bit(), but this will cause memory allocation, and the list_lru_add() doesn't accept failure. A possible solution is to pre-allocate, but the location of pre-allocation is not well determined. Therefore, this commit chooses to introduce a secondary array for shrinker_info::{map, nr_deferred}, so that we only need to copy this secondary array every time the size is resized. Then even if we get the old secondary array under the RCU lock, the found map and nr_deferred are also true, so no data is lost. [1]. https://lore.kernel.org/all/20220228122126.37293-13-songmuc...@bytedance.com/ Signed-off-by: Qi Zheng Reviewed-by: Muchun Song --- include/linux/memcontrol.h | 12 +- include/linux/shrinker.h | 17 +++ mm/shrinker.c | 250 +++-- 3 files changed, 172 insertions(+), 107 deletions(-) diff --git a/include/linux/memcontrol.h b/include/linux/memcontrol.h index 11810a2cfd2d..b49515bb6fbd 100644 --- a/include/linux/memcontrol.h +++ b/include/linux/memcontrol.h @@ -21,6 +21,7 @@ #include #include #include +#include struct mem_cgroup; struct obj_cgroup; @@ -88,17 +89,6 @@ struct mem_cgroup_reclaim_iter { unsigned int generation; }; -/* - * Bitmap and deferred work of shrinker::id corresponding to memcg-aware - * shrinkers, which have elements charged to this memcg. - */ -struct shrinker_info { - struct rcu_head rcu; - atomic_long_t *nr_deferred; - unsigned long *map; - int map_nr_max; -}; - struct lruvec_stats_percpu { /* Local (CPU and cgroup) state */ long state[NR_VM_NODE_STAT_ITEMS]; diff --git a/include/linux/shrinker.h b/include/linux/shrinker.h index 025c8070dd86..eb342994675a 100644 --- a/include/linux/shrinker.h +++ b/include/linux/shrinker.h @@ -5,6 +5,23 @@ #include #include +#define SHRINKER_UNIT_BITS BITS_PER_LONG + +/* + * Bitmap and deferred work of shrinker::id corresponding to memcg-aware + * shrinkers, which have elements charged to the memcg. + */ +struct shrinker_info_unit { + atomic_long_t nr_deferred[SHRINKER_UNIT_BITS]; + DECLARE_BITMAP(map, SHRINKER_UNIT_BITS); +}; + +struct shrinker_info { + struct rcu_head rcu; + int map_nr_max; + struct shrinker_info_unit *unit[]; +}; + /* * This struct is used to pass information from page reclaim to the shrinkers. * We consolidate the values for easier extension later. diff --git a/mm/shrinker.c b/mm/shrinker.c index a27779ed3798..1911c06b8af5 100644 --- a/mm/shrinker.c +++ b/mm/shrinker.c @@ -12,15 +12,50 @@ DECLARE_RWSEM(shrinker_rwsem); #ifdef CONFIG_MEMCG static int shrinker_nr_max; -/* The shrinker_info is expanded in a batch of BITS_PER_LONG */ -static inline int shrinker_map_size(int nr_items) +static inline int shrinker_unit_size(int nr_items) { - return (DIV_ROUND_UP(nr_items, BITS_PER_LONG) * sizeof(unsigned long)); + return (DIV_ROUND_UP(nr_items, SHRINKER_UNIT_BITS) * sizeof(struct shrinker_info_unit *)); } -static inline int shrinker_defer_size(int nr_items) +static inline void shrinker_unit_free(struct shrinker_info *info, int start) { - return (round_up(nr_items, BITS_PER_LONG) * sizeof(atomic_long_t)); + struct shrinker_info_unit **unit; + int nr, i; + + if (!info) + return; + + unit = info->unit; + nr = DIV_ROUND_UP(info->map_nr_max, SHRINKER_UNIT_BITS); + + for (i = start; i < nr; i++) { + if (!unit[i]) + break; + + kvfree(unit[i]); + unit[i] = NULL; + } +} + +static inline int shrinker_unit_alloc(struct shrinker_info *new, + struct shrinker_info *old, int nid) +{ + struct shrinker_info_unit *unit; + int nr =