kmalloc [LWN.net]

kmalloc

Posted Jan 27, 2011 4:41 UTC (Thu) by ncm (guest, #165)
Parent article: Concurrent code and expensive instructions

a given pair of invocations of kmalloc() invocations will be SNC only if it is possible for them to be satisfied by the same block of memory

If the number of bytes requested is different for the two calls, they are not SNC. This seems to argue for providing a different allocator for each size, or anyway for a collection of useful sizes, on the assumption that with enough sizes in play, two requests for the same amount will be rare.

A reliable kmalloc can be constructed from an unreliable kmalloc and a loop. If the unreliable kmalloc can be made just reliable enough, that's almost as good.

to post comments

kmalloc and SNC

Posted Jan 27, 2011 22:35 UTC (Thu) by PaulMcKenney (✭ supporter ✭, #9624) [Link]

Even for allocators that segregate memory on a per-request-size basis, different-sized calls can be SNC — especially if the allocator can recycle memory that was of one size to satisfy future requests of another size. However, SNC behavior can occur even in the absence of such recycling. To see this, consider an initially empty allocator in which the first pair of requests arrive concurrently and have different request sizes. It is then quite possible that the two requests might be satisfied by the same block of memory, given that the initial request will normally allocate a large block (e.g., a page) and break it up into blocks of the requested size.

All that aside, it is true that per-size caching is an example of privatization that further reduces the probability that a given allocation/free request will need to execute an expensive instruction.

Your point about calling an unreliable kmalloc() in a loop is a good one (real-time heartburn notwithstanding), although given my scenario it would loop forever — or until an interrupt handler running on that same CPU happened to free a block of the desired size.