On 21.03.2018 18:26, Matthew Wilcox wrote: > On Wed, Mar 21, 2018 at 06:12:17PM +0300, Kirill Tkhai wrote: >> On 21.03.2018 17:56, Matthew Wilcox wrote: >>> Why use your own bitmap here? Why not use an IDA which can grow and >>> shrink automatically without you needing to play fun games with RCU? >> >> Bitmap allows to use unlocked set_bit()/clear_bit() to maintain the map >> of not empty shrinkers. >> >> So, the reason to use IDR here is to save bitmap memory? Does this mean >> IDA works fast with sparse identifiers? It seems they require per-memcg >> lock to call IDR primitives. I just don't have information about this. >> >> If so, which IDA primitive can be used to set particular id in bitmap? >> There is idr_alloc_cyclic(idr, NULL, id, id+1, GFP_KERNEL) only I see >> to do that. > > You're confusing IDR and IDA in your email, which is unfortunate. > > You can set a bit in an IDA by calling ida_simple_get(ida, n, n, GFP_FOO); > You clear it by calling ida_simple_remove(ida, n); I moved to IDR in the message, since IDA uses global spinlock. It will be taken every time a first object is added to list_lru, or last is removed. These may be frequently called operations, and they may scale not good on big machines. Using IDR will allow us to introduce memcg-related locks, but I'm still not sure it's easy to introduce them in scalable-way. Simple set_bit()/clear_bit() do not require locks at all. > The identifiers aren't going to be all that sparse; after all you're > allocating them from a global IDA. Up to 62 identifiers will allocate > no memory; 63-1024 identifiers will allocate a single 128 byte chunk. > Between 1025 and 65536 identifiers, you'll allocate a 576-byte chunk > and then 128-byte chunks for each block of 1024 identifiers (*). One of > the big wins with the IDA is that it will shrink again after being used. > I didn't read all the way through your patchset to see if you bother to > shrink your bitmap after it's no longer used, but most resizing bitmaps > we have in the kernel don't bother with that part. > > (*) Actually it's more complex than that... between 1025 and 1086, > you'll have a 576 byte chunk, a 128-byte chunk and then use 62 bits of > the next pointer before allocating a 128 byte chunk when reaching ID > 1087. Similar things happen for the 62 bits after 2048, 3076 and so on. > The individual chunks aren't shrunk until they're empty so if you set ID > 1025 and then ID 1100, then clear ID 1100, the 128-byte chunk will remain > allocated until ID 1025 is cleared. This probably doesn't matter to you. Sound great, thanks for explaining this. The big problem I see is that IDA/IDR add primitives allocate memory, while they will be used in the places, where they mustn't fail. There is list_lru_add(), and it's called unconditionally in current kernel code. The patchset makes the bitmap be populated in this function. So, we can't use IDR there. Thanks, Kirill
